Unit 4 - Notes

ECE249

Unit 4: Introduction to Combinational Logic Circuits

1. Overview of Combinational Logic Circuits

A combinational logic circuit is a digital system where the output at any instant depends only on the present combination of inputs. Unlike sequential circuits, combinational circuits have no memory element, feedback loops, or clock signals.

Key Characteristics:

Speed: Generally faster than sequential circuits (limited only by propagation delay).
Building Blocks: Logic gates (AND, OR, NOT, NAND, NOR, XOR).
Function: Defined by Boolean equations or Truth Tables.
Block Diagram: $n$ input variables $\rightarrow$ Logic Circuit $\rightarrow$ $m$ output variables.

2. Arithmetic Circuits: Adders

Adders are combinational circuits used to perform binary addition.

2.1 Half Adder

A Half Adder adds two single binary digits ( $A$ and $B$ ) and produces two outputs: Sum ( $S$ ) and Carry ( $C$ ).

Inputs: $A, B$
Outputs: $S$ (Sum), $C$ (Carry)

Truth Table:

Input A	Input B	Carry (C)	Sum (S)
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Boolean Expressions:

Sum ( $S$ ): $A \oplus B$ (XOR operation)
Carry ( $C$ ): $A \cdot B$ (AND operation)

Logic Implementation:

1 XOR gate for the Sum.
1 AND gate for the Carry.

2.2 Full Adder

A Half Adder cannot handle the carry coming from a previous lower significant bit. A Full Adder adds three bits: input bits $A$ and $B$ , and a Carry Input ( $C_{in}$ ).

Inputs: $A, B, C_{in}$
Outputs: $S$ (Sum), $C_{out}$ (Carry Out)

Truth Table:

A	B	$C_{in}$	$C_{out}$	S
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Boolean Expressions:

Sum ( $S$ ): $A \oplus B \oplus C_{in}$
Carry ( $C_{out}$ ): $A \cdot B + B \cdot C_{in} + A \cdot C_{in}$ (Majority function)

Implementation using Half Adders:
A Full Adder can be constructed using two Half Adders and one OR gate.

3. Arithmetic Circuits: Subtractors

Subtractors perform binary subtraction.

3.1 Half Subtractor

Used to subtract one bit ( $B$ ) from another ( $A$ ). It produces a Difference ( $D$ ) and a Borrow ( $B_{out}$ ).

Operation: $A - B$
Inputs: $A$ (Minuend), $B$ (Subtrahend)
Outputs: $D$ (Difference), $B_{out}$ (Borrow)

Truth Table:

A	B	Borrow ( $B_{out}$ )	Difference (D)
0	0	0	0
0	1	1	1
1	0	0	1
1	1	0	0

Boolean Expressions:

Difference ( $D$ ): $A \oplus B$
Borrow ( $B_{out}$ ): $\bar{A} \cdot B$ (NOT A AND B)

3.2 Full Subtractor

Performs subtraction involving three bits: $A$ (Minuend), $B$ (Subtrahend), and $B_{in}$ (Borrow from the previous stage).

Inputs: $A, B, B_{in}$
Outputs: $D$ (Difference), $B_{out}$ (Borrow Out)

Boolean Expressions:

Difference ( $D$ ): $A \oplus B \oplus B_{in}$
Borrow ( $B_{out}$ ): $\bar{A}B + (\overline{A \oplus B})B_{in}$ OR simpler form: $\bar{A}B + \bar{A}B_{in} + BB_{in}$

4. Multiplexers (MUX)

A Multiplexer is a Data Selector. It selects one of the many input lines and directs it to a single output line based on the status of select lines.

Inputs: $2^n$ data inputs ( $I_0$ to $I_{2^n-1}$ ).
Select Lines: $n$ selection lines ( $S_0$ to $S_{n-1}$ ).
Output: 1 output line ( $Y$ ).
Analogy: A rotary switch.

4:1 Multiplexer

Data Inputs: $I_0, I_1, I_2, I_3$ ( $4 = 2^2$ , so $n=2$ ).
Select Lines: $S_1, S_0$ .
Output: $Y$ .

Function Table:

$S_1$	$S_0$	Output (Y)
0	0	$I_0$
0	1	$I_1$
1	0	$I_2$
1	1	$I_3$

Boolean Expression:

Y = \bar{S_1}\bar{S_0}I_0 + \bar{S_1}S_0I_1 + S_1\bar{S_0}I_2 + S_1S_0I_3

5. De-multiplexers (DEMUX)

A De-multiplexer is a Data Distributor. It takes a single input and distributes it over several outputs. It is the reverse process of a MUX.

Inputs: 1 data input ( $D$ ).
Select Lines: $n$ selection lines.
Outputs: $2^n$ output lines.

1:4 De-multiplexer

Input: $D$
Select Lines: $S_1, S_0$
Outputs: $Y_0, Y_1, Y_2, Y_3$

Logic Function:

If $S_1S_0 = 00$ , $Y_0 = D$ (Others 0)
If $S_1S_0 = 01$ , $Y_1 = D$ (Others 0)
If $S_1S_0 = 10$ , $Y_2 = D$ (Others 0)
If $S_1S_0 = 11$ , $Y_3 = D$ (Others 0)

Boolean Expressions:

$Y_0 = \bar{S_1}\bar{S_0}D$
$Y_1 = \bar{S_1}S_0D$
$Y_2 = S_1\bar{S_0}D$
$Y_3 = S_1S_0D$

6. Decoders

A Decoder converts binary information from $n$ input lines to a maximum of $2^n$ unique output lines. It detects the presence of a specific binary code.

Inputs: $n$
Outputs: $2^n$
Enable Pin (E): Usually included to activate the chip.

2-to-4 Line Decoder

Inputs: $A, B$
Outputs: $Y_0, Y_1, Y_2, Y_3$
Logic: Only one output is High (1) for a given input combination (assuming Active High outputs).

Truth Table (Active High):

Enable	A	B	$Y_3$	$Y_2$	$Y_1$	$Y_0$
0	X	X	0	0	0	0
1	0	0	0	0	0	1
1	0	1	0	0	1	0
1	1	0	0	1	0	0
1	1	1	1	0	0	0

(Note: In commercial ICs like 74138, outputs are often Active Low, meaning the selected output goes to 0 while others stay at 1).

7. Encoders

An Encoder performs the inverse operation of a decoder. It converts an active input signal into a coded binary output signal.

Inputs: $2^n$ (Only one input is high at a time).
Outputs: $n$ binary lines.

Octal-to-Binary Encoder (8-to-3 Encoder)

Inputs: $D_0$ to $D_7$ (corresponding to Octal digits).
Outputs: $X, Y, Z$ (Binary representation).

Boolean Logic:

$Z$ (LSB) = $D_1 + D_3 + D_5 + D_7$
$Y$ = $D_2 + D_3 + D_6 + D_7$
$X$ (MSB) = $D_4 + D_5 + D_6 + D_7$

Drawback of Standard Encoders:
If two inputs are high simultaneously (e.g., $D_3$ and $D_6$ ), the output is invalid. This is resolved using a Priority Encoder, which encodes only the input with the highest priority.

8. Digital Comparators (Magnitude Comparators)

A comparator compares two binary numbers ( $A$ and $B$ ) and determines their relative magnitudes.

Standard Outputs:

$A > B$ (A is greater than B)
$A = B$ (A is equal to B)
$A < B$ (A is less than B)

8.1 1-Bit Comparator

Compares single bits $A$ and $B$ .

Logic Equations:

Equality ( $A = B$ ): High if both are 0 or both are 1.
- $E = A \odot B$ (XNOR gate)
Greater Than ( $A > B$ ): High if and .
- $G = A \cdot \bar{B}$
Less Than ( $A < B$ ): High if and .
- $L = \bar{A} \cdot B$

8.2 2-Bit Comparator

Compares two 2-bit numbers: $A = A_1 A_0$ and $B = B_1 B_0$ .
Here, $A_1/B_1$ are the Most Significant Bits (MSB) and $A_0/B_0$ are the Least Significant Bits (LSB).

Logic for Equality ( $A = B$ ):
Both bit positions must be equal.

(A = B) \implies (A_1 = B_1) \text{ AND } (A_0 = B_0)

Let

x_1 = (A_1 \odot B_1)

and

x_0 = (A_0 \odot B_0)

.
Equation:

(A=B) = x_1 \cdot x_0

Logic for Greater Than ( $A > B$ ):
$A$ is greater than $B$ if:

The MSB of $A$ is greater than the MSB of $B$ ( $A_1 > B_1$ ).
OR, the MSBs are equal ( $A_1 = B_1$ ) AND the LSB of $A$ is greater than the LSB of $B$ ( $A_0 > B_0$ ).

Equation:

(A > B) = (A_1\bar{B_1}) + (x_1 \cdot A_0\bar{B_0})

Logic for Less Than ( $A < B$ ):
$A$ is less than $B$ if:

The MSB of $A$ is less than the MSB of $B$ ( $A_1 < B_1$ ).
OR, the MSBs are equal ( $A_1 = B_1$ ) AND the LSB of $A$ is less than the LSB of $B$ ( $A_0 < B_0$ ).

Equation:

(A < B) = (\bar{A_1}B_1) + (x_1 \cdot \bar{A_0}B_0)

Unit 4 - Notes

Table of Contents

Unit 4: Introduction to Combinational Logic Circuits

1. Overview of Combinational Logic Circuits

2. Arithmetic Circuits: Adders

2.1 Half Adder

2.2 Full Adder

3. Arithmetic Circuits: Subtractors

3.1 Half Subtractor

3.2 Full Subtractor

4. Multiplexers (MUX)

4:1 Multiplexer

5. De-multiplexers (DEMUX)

1:4 De-multiplexer

6. Decoders

2-to-4 Line Decoder

7. Encoders

Octal-to-Binary Encoder (8-to-3 Encoder)

8. Digital Comparators (Magnitude Comparators)

8.1 1-Bit Comparator

8.2 2-Bit Comparator