Unit 5: Introduction to Combinational Logic Circuits

A combinational logic circuit is a type of digital circuit where the output at any instant is a function of the present combination of inputs only. These circuits have no memory; the previous state of the inputs has no effect on the current output. They are built using basic logic gates like AND, OR, NOT, NAND, NOR, and XOR.

Key Characteristics:

• The output depends solely on the current inputs.
• They do not have memory elements (like flip-flops).
• They do not have feedback paths (from output back to input).
• They are faster than sequential circuits because they don't require a clock signal for state transitions.

1. Adders

Adders are fundamental combinational circuits that perform the arithmetic addition of binary numbers.

1.1 Half Adder

A Half Adder is a circuit that adds two single binary digits (bits). It has two inputs (A and B) and two outputs: Sum (S) and Carry (C).

• Inputs: A, B (the two bits to be added)
• Outputs: Sum (S), Carry (C)

Truth Table

| A | B | Sum (S) | Carry (C) |
|---|---|---------|-----------|
| 0 | 0 |    0    |     0     |
| 0 | 1 |    1    |     0     |
| 1 | 0 |    1    |     0     |
| 1 | 1 |    0    |     1     |

Boolean Expressions

From the truth table, we can derive the Boolean expressions for Sum and Carry.

• Sum (S): The Sum output is 1 when A is 0 and B is 1, or when A is 1 and B is 0. This is the definition of an XOR operation.
  S = A'B + AB' = A ⊕ B
• Carry (C): The Carry output is 1 only when both A and B are 1. This is the definition of an AND operation.
  C = A ⋅ B

Logic Circuit Diagram

1.2 Full Adder

A Half Adder cannot handle a carry-in from a previous addition stage, which is necessary for adding multi-bit numbers. A Full Adder solves this by adding three single bits: two input bits (A, B) and a carry-in bit (Cin).

• Inputs: A, B, Cin (Carry-in)
• Outputs: Sum (S), Cout (Carry-out)

Truth Table

| A | B | Cin | Sum (S) | Cout |
|---|---|-----|---------|------|
| 0 | 0 |  0  |    0    |   0  |
| 0 | 0 |  1  |    1    |   0  |
| 0 | 1 |  0  |    1    |   0  |
| 0 | 1 |  1  |    0    |   1  |
| 1 | 0 |  0  |    1    |   0  |
| 1 | 0 |  1  |    0    |   1  |
| 1 | 1 |  0  |    0    |   1  |
| 1 | 1 |  1  |    1    |   1  |

Boolean Expressions

• Sum (S): The Sum is 1 when there is an odd number of 1s in the inputs. This is a 3-input XOR operation.
  S = A'B'Cin + A'BCin' + AB'Cin' + ABCin = A ⊕ B ⊕ Cin
• Carry-out (Cout): The Carry-out is 1 if at least two of the inputs are 1.
  Cout = A'BCin + AB'Cin + ABCin' + ABCin
  This can be simplified to:
  Cout = AB + BCin + ACin or Cout = AB + Cin(A ⊕ B)

Logic Circuit Diagram

A Full Adder can be constructed using two Half Adders and an OR gate.

1.3 Parallel Binary Adder (Ripple-Carry Adder)

To add multi-bit numbers (e.g., 4-bit numbers), we can cascade Full Adders. The Carry-out of one stage becomes the Carry-in of the next higher-order stage. This is called a Ripple-Carry Adder.

Example: 4-bit Ripple-Carry Adder
This circuit adds two 4-bit numbers, A (A3A2A1A0) and B (B3B2B1B0).

• The least significant bits A0 and B0 are added by the first Full Adder (or a Half Adder if Cin is assumed to be 0).
• The Cout from the first stage is fed as the Cin to the second stage, which adds A1, B1, and the incoming carry.
• This continues for all bits. The final Cout from the most significant bit stage (adding A3, B3) is the overall carry-out of the addition.

2. Subtractors

Subtractors perform binary subtraction. Like adders, they come in Half and Full versions.

2.1 Half Subtractor

A Half Subtractor subtracts one bit from another. It has two inputs (A, B) and two outputs: Difference (D) and Borrow (Bout). It computes A - B.

• Inputs: A, B
• Outputs: Difference (D), Borrow (Bout)

Truth Table

| A | B | Difference (D) | Borrow (Bout) |
|---|---|----------------|---------------|
| 0 | 0 |        0       |       0       |
| 0 | 1 |        1       |       1       |
| 1 | 0 |        1       |       0       |
| 1 | 1 |        0       |       0       |

Boolean Expressions

• Difference (D): D = A'B + AB' = A ⊕ B
• Borrow (Bout): Bout = A'B

Logic Circuit Diagram

2.2 Full Subtractor

A Full Subtractor performs subtraction involving three bits: two input bits (A, B) and a borrow-in bit (Bin) from a lower stage. It computes A - B - Bin.

• Inputs: A, B, Bin (Borrow-in)
• Outputs: Difference (D), Bout (Borrow-out)

Truth Table

| A | B | Bin | Difference (D) | Bout |
|---|---|-----|----------------|------|
| 0 | 0 |  0  |        0       |   0  |
| 0 | 0 |  1  |        1       |   1  |
| 0 | 1 |  0  |        1       |   1  |
| 0 | 1 |  1  |        0       |   1  |
| 1 | 0 |  0  |        1       |   0  |
| 1 | 0 |  1  |        0       |   0  |
| 1 | 1 |  0  |        0       |   0  |
| 1 | 1 |  1  |        1       |   1  |

Boolean Expressions

• Difference (D): D = A ⊕ B ⊕ Bin
• Borrow-out (Bout): Bout = A'B + A'Bin + BBin (Simplified: Bout = A'B + Bin(A ⊕ B)')

Logic Circuit Diagram

Similar to a Full Adder, a Full Subtractor can be built from two Half Subtractors and an OR gate.

Note on Subtraction using Adders: In practice, subtraction is almost always performed using 2's complement addition. An adder/subtractor circuit can be built by using an adder and XOR gates. The XOR gates act as controlled inverters. When the SUB control line is 1, the B inputs are inverted, and a 1 is added via Cin (completing the 2's complement), thus performing A - B. When SUB is 0, the B inputs pass through unchanged, and Cin is 0, performing A + B.

3. Comparators

A digital comparator is a circuit that compares two binary numbers (A and B) and determines their relative magnitude.

3.1 1-Bit Comparator

A 1-bit comparator takes two single bits (A, B) as input and produces three outputs: A > B, A = B, and A < B.

Truth Table

| A | B | A > B | A = B | A < B |
|---|---|-------|-------|-------|
| 0 | 0 |   0   |   1   |   0   |
| 0 | 1 |   0   |   0   |   1   |
| 1 | 0 |   1   |   0   |   0   |
| 1 | 1 |   0   |   1   |   0   |

Boolean Expressions

• A > B: A ⋅ B'
• A = B: This is true when A and B are the same. This is an XNOR operation. (A ⋅ B) + (A' ⋅ B') = A ⊙ B
• A < B: A' ⋅ B

Logic Circuit Diagram

3.2 N-Bit Comparator (e.g., 4-bit)

Comparing multi-bit numbers is more complex. A 4-bit comparator (like the standard IC 7485) compares two 4-bit numbers A (A3A2A1A0) and B (B3B2B1B0).

The logic works by checking from the most significant bit (MSB) downwards:

• Equality (A = B): This is true only if all corresponding bits are equal.
  A=B if (A3=B3) AND (A2=B2) AND (A1=B1) AND (A0=B0)
  The (An=Bn) term is implemented with an XNOR gate.
• Greater Than (A > B): This is true if the MSB of A is greater than the MSB of B (A3>B3), OR if the MSBs are equal (A3=B3) AND the next bit of A is greater than the next bit of B (A2>B2), and so on.
  A>B if (A3>B3) OR (A3=B3 AND A2>B2) OR (A3=B3 AND A2=B2 AND A1>B1) OR ...
• Less Than (A < B): The logic is similar to the "Greater Than" case.

Such comparators often have cascading inputs (A>B_in, A=B_in, A<B_in) to allow for the comparison of numbers larger than 4 bits by chaining multiple ICs.

4. Multiplexers and De-multiplexers

4.1 Multiplexer (MUX)

A Multiplexer (also known as a MUX or Data Selector) is a combinational circuit that selects one of several analog or digital input signals and forwards the selected input into a single output line. The selection is directed by a separate set of digital inputs known as select lines.

• If there are n select lines, the MUX can select from 2^n input lines.
• It functions like a digitally controlled rotary switch.
• Commonly referred to as a "many-to-one" device.

2:1 Multiplexer

• Inputs: 2 data lines (I0, I1)
• Select Lines: 1 (S)
• Output: 1 (Y)

Truth Table / Function Table:

| S | Y (Output) |
|---|------------|
| 0 |     I0     |
| 1 |     I1     |

Boolean Expression: Y = S'⋅I0 + S⋅I1

Logic Circuit Diagram:

4:1 Multiplexer

• Inputs: 4 data lines (I0, I1, I2, I3)
• Select Lines: 2 (S1, S0)
• Output: 1 (Y)

Function Table:

| S1 | S0 | Y (Output) |
|----|----|------------|
| 0  | 0  |     I0     |
| 0  | 1  |     I1     |
| 1  | 0  |     I2     |
| 1  | 1  |     I3     |

Boolean Expression: Y = S1'S0'⋅I0 + S1'S0⋅I1 + S1S0'⋅I2 + S1S0⋅I3

Logic Circuit Diagram:

4.2 De-multiplexer (DEMUX)

A De-multiplexer (or DEMUX) is the functional opposite of a MUX. It takes a single input signal and distributes it over one of several output lines. The select lines determine which output line is connected to the input.

• If there are n select lines, the DEMUX can route the input to one of 2^n output lines.
• It acts as a "one-to-many" data distributor.

1:4 De-multiplexer

• Input: 1 data line (D_in)
• Select Lines: 2 (S1, S0)
• Outputs: 4 (Y0, Y1, Y2, Y3)

Function Table:

| S1 | S0 | Selected Output |
|----|----|-----------------|
| 0  | 0  |     Y0 = D_in   |
| 0  | 1  |     Y1 = D_in   |
| 1  | 0  |     Y2 = D_in   |
| 1  | 1  |     Y3 = D_in   |

Boolean Expressions:

• Y0 = S1'S0' ⋅ D_in
• Y1 = S1'S0 ⋅ D_in
• Y2 = S1S0' ⋅ D_in
• Y3 = S1S0 ⋅ D_in

Logic Circuit Diagram:

5. Decoders

A Decoder is a combinational circuit that converts a binary code (like BCD or n-bit binary) into a specific output signal. It has n input lines and a maximum of 2^n output lines. For any given input combination, only one output line is activated (usually asserted HIGH or LOW).

2:4 Decoder

This decoder has 2 input lines (A1, A0) and 4 output lines (Y0, Y1, Y2, Y3).

• An optional Enable (E) input is often included. The decoder only functions when E is active (e.g., E=1). If E=0, all outputs are disabled (e.g., all 0).

Truth Table (with Active-High Enable)

| E | A1 | A0 | Y3 | Y2 | Y1 | Y0 |
|---|----|----|----|----|----|----|
| 0 | x  | x  | 0  | 0  | 0  | 0  | <-- Disabled
| 1 | 0  | 0  | 0  | 0  | 0  | 1  | <-- Y0 is Active
| 1 | 0  | 1  | 0  | 0  | 1  | 0  | <-- Y1 is Active
| 1 | 1  | 0  | 0  | 1  | 0  | 0  | <-- Y2 is Active
| 1 | 1  | 1  | 1  | 0  | 0  | 0  | <-- Y3 is Active

Boolean Expressions

• Y0 = E ⋅ A1' ⋅ A0'
• Y1 = E ⋅ A1' ⋅ A0
• Y2 = E ⋅ A1 ⋅ A0'
• Y3 = E ⋅ A1 ⋅ A0

Logic Circuit Diagram

Application: Decoders are used in memory address decoding, data de-multiplexing, and implementing Boolean functions. Any n-variable Sum-of-Products (SOP) expression can be implemented using an n-to-2^n decoder and an OR gate.

6. Encoders

An Encoder performs the reverse operation of a decoder. It has 2^n (or fewer) input lines and n output lines. It converts an active input signal into a coded binary output. It is assumed that only one input line is active at any given time.

4:2 Encoder

This encoder has 4 input lines (D0, D1, D2, D3) and 2 output lines (Y1, Y0).

Truth Table

| D3 | D2 | D1 | D0 | Y1 | Y0 |
|----|----|----|----|----|----|
| 0  | 0  | 0  | 1  | 0  | 0  | <-- D0 active -> 00
| 0  | 0  | 1  | 0  | 0  | 1  | <-- D1 active -> 01
| 0  | 1  | 0  | 0  | 1  | 0  | <-- D2 active -> 10
| 1  | 0  | 0  | 0  | 1  | 1  | <-- D3 active -> 11

Boolean Expressions

• Y0 = D1 + D3
• Y1 = D2 + D3

The Problem with Simple Encoders

• If no inputs are active, the output is 00, which is the same as when D0 is active. This is an ambiguity.
• If more than one input is active (e.g., D1 and D2), the output becomes Y1=1, Y0=1, which is the code for D3. This is incorrect.

Priority Encoder

A Priority Encoder solves these problems. If multiple inputs are active, the encoder produces the code corresponding to the input with the highest priority. A Valid (V) output is often included to indicate whether any input is active.

4:2 Priority Encoder

Let's assume D3 has the highest priority and D0 has the lowest.

Truth Table

| D3 | D2 | D1 | D0 | Y1 | Y0 | V |
|----|----|----|----|----|----|---|
| 0  | 0  | 0  | 0  | x  | x  | 0 | <-- No input, output invalid
| 0  | 0  | 0  | 1  | 0  | 0  | 1 |
| 0  | 0  | 1  | x  | 0  | 1  | 1 | <-- D1 active (D0 doesn't matter)
| 0  | 1  | x  | x  | 1  | 0  | 1 | <-- D2 active (D1,D0 don't matter)
| 1  | x  | x  | x  | 1  | 1  | 1 | <-- D3 active (others don't matter)

Boolean Expressions (Simplified)

• Y1 = D3 + D2
• Y0 = D3 + D2'D1
• V = D3 + D2 + D1 + D0

Application: Used in microprocessors to handle multiple interrupt requests, where the priority of the interrupt must be determined.

7. Parity Circuits

Parity is a simple method of error detection in digital data transmission. A single extra bit, the parity bit, is added to a binary word.

• Even Parity: The total number of 1s in the word (including the parity bit) is made to be an even number.
• Odd Parity: The total number of 1s in the word (including the parity bit) is made to be an odd number.

Parity circuits are built using XOR gates, as the XOR function acts as an "odd function" (its output is 1 if an odd number of inputs are 1).

7.1 Parity Generator

A Parity Generator is a circuit at the transmitter's end that creates the parity bit for a given data word.

3-Bit Even Parity Generator

This circuit takes a 3-bit data word (A, B, C) and generates an Even Parity bit (P).

Truth Table:

| A | B | C | P (Even Parity) | Total 1s (A,B,C,P) |
|---|---|---|-----------------|--------------------|
| 0 | 0 | 0 |        0        |          0         |
| 0 | 0 | 1 |        1        |          2         |
| 0 | 1 | 0 |        1        |          2         |
| 0 | 1 | 1 |        0        |          2         |
| 1 | 0 | 0 |        1        |          2         |
| 1 | 0 | 1 |        0        |          2         |
| 1 | 1 | 0 |        0        |          2         |
| 1 | 1 | 1 |        1        |          4         |

Boolean Expression: The parity bit P must be 1 if the data word (A, B, C) contains an odd number of 1s. This is the definition of the 3-input XOR function.
P = A ⊕ B ⊕ C

Logic Circuit: A 3-input XOR gate (or cascaded 2-input XOR gates).

7.2 Parity Checker

A Parity Checker is a circuit at the receiver's end that checks if the received data (data bits + parity bit) has the correct parity.

4-Bit Even Parity Checker

This circuit receives a 4-bit word (e.g., the 3-bit data A, B, C and the parity bit P) and outputs an error signal.

Logic: If the received word has even parity, there is no single-bit error. If it has odd parity, an error has occurred. The checker output (let's call it Error_Check) should be 1 when an error is detected (i.e., when the total number of 1s is odd).

Boolean Expression:
Error_Check = A ⊕ B ⊕ C ⊕ P

Operation:

• If the received 4-bit word has an even number of 1s (no error), the result of the 4-input XOR will be 0.
• If the received 4-bit word has an odd number of 1s (a single-bit error occurred), the result of the 4-input XOR will be 1, signaling an error.

Limitation of Parity: Parity checking can only detect an odd number of bit errors (1, 3, 5, etc.). It cannot detect an even number of bit errors (e.g., if two bits flip, the parity remains the same, and the error goes undetected).