Combinational Logic Circuits
Open in the Padhaiko app4.1 Design procedures
A combinational circuit has outputs that depend only on the present inputs (no memory). It is built from gates with no feedback.
Design procedure
- Read the problem and decide the number of inputs and outputs.
- Assign letters to inputs and outputs.
- Write the truth table for every output.
- Simplify each output with a K-map (or Boolean algebra).
- Draw the logic diagram, using the gate types that are available.
- Test the circuit for every input combination.
4.2 Half-adder and full-adder
A half adder (HA) adds two bits and and gives a sum and a carry . A full adder (FA) also accepts a carry-in , so that stages can be chained.
| A | B | Sum S | Carry C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
From the table: and . A half adder is one XOR gate and one AND gate.
| A | B | Cin | Sum S | Carry out 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 |
The K-maps give and , equivalent to . A full adder is two half adders and one OR gate: the first half adder adds and , the second adds the result to , and the two carries are ORed.
4.3 Half-subtractor and full-subtractor
A half subtractor finds and produces a difference and a borrow . A full subtractor also takes a borrow-in .
| Circuit | Difference | Borrow |
|---|---|---|
| Half subtractor | ||
| Full subtractor |
Compared with the adder, only the borrow differs: the half subtractor uses instead of . A borrow is generated whenever the subtrahend (with its borrow-in) is larger than the minuend bit.
4.4 Ripple carry adders and fast adders
An -bit ripple carry adder joins full adders so that the carry out of each stage feeds the carry in of the next. It is simple but slow: the final sum is valid only after the carry has rippled through all stages, so the delay is about times the carry delay of one full adder (for a gate-level full adder, two gate delays per stage).
A fast adder removes the ripple delay by computing the carries directly from the inputs. The carry look-ahead adder (CLA) defines for each stage
- generate (a carry is produced regardless of the input carry), and
- propagate (the input carry is passed on).
Then , which expands to
, , , .
All carries are produced in the same two gate levels, so the delay does not grow with (but the gates get wider). The sum is .
4.5 Multiplexers design
A multiplexer (MUX) is a data selector: it connects one of data inputs to a single output according to select lines.
| S1 | S0 | Output Y |
|---|---|---|
| 0 | 0 | I0 |
| 0 | 1 | I1 |
| 1 | 0 | I2 |
| 1 | 1 | I3 |
The output equation is : four AND gates, an OR gate and two inverters. A 2:1 MUX is . Larger multiplexers are built by combining smaller ones (an 8:1 MUX from two 4:1 MUXes and one 2:1 MUX).
Implementing a function: a :1 MUX can realise any function of variables: use variables as selects and connect each data input to , , the last variable or its complement, read from the truth table.
4.6 Demultiplexers design
A demultiplexer (DEMUX) does the opposite: it sends one data input to one of outputs chosen by the select lines. For a 1:4 DEMUX: , , , . A DEMUX is the same circuit as a decoder with the data input used as the enable.
4.7 Basic encoders
An encoder has inputs and outputs; exactly one input is active, and the output is its binary code. In a 4-to-2 encoder with inputs : and . It fails if two inputs are active together, or if no input is active (the output 00 is then ambiguous with ).
4.8 Priority encoders
A priority encoder gives the code of the highest-priority active input when several are active, and adds a valid output V to show that at least one input is 1.
| D3 | D2 | D1 | D0 | Y1 | Y0 | V |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | X | X | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | X | 0 | 1 | 1 |
| 0 | 1 | X | X | 1 | 0 | 1 |
| 1 | X | X | X | 1 | 1 | 1 |
K-maps with don't cares give , and .
4.9 Encoder designs
Design steps for an encoder are those of 4.1. For an octal-to-binary (8-to-3) encoder: , and , that is, each output is the OR of the inputs whose binary code has a 1 in that position. A decimal-to-BCD encoder has 10 inputs and 4 outputs: , , , . Making it a priority encoder removes the problem of simultaneous keys (a keyboard encoder).
4.10 Decoder designs
A decoder has inputs and up to outputs; for each input code exactly one output is active. A 2-to-4 decoder with enable has where is the minterm of the inputs. Because a decoder generates all minterms, any function can be built from a decoder and an OR gate (or a NAND gate for active-low outputs). Larger decoders are made from smaller ones: a 4-to-16 decoder uses five 2-to-4 decoders (one decoding two bits to enable one of four others) or two 3-to-8 decoders with the fourth input as enable.
4.11 BCD-to-decimal decoder
A BCD-to-decimal decoder (for example IC 7442) has 4 inputs ( = BCD digit) and 10 outputs, one for each digit 0 to 9. The outputs are active-low in the IC: the selected output is 0 and the rest are 1. The codes 1010 to 1111 are invalid and activate no output. The output for decimal 7 is in active-low form (with the MSB).
4.12 Seven-segment decoder
A seven-segment display shows a digit with segments to (a at the top, going clockwise to f, and g in the middle). A BCD to seven-segment decoder (IC 7447 drives a common-anode, 7448 a common-cathode display) turns the 4-bit BCD input ( = MSB) into seven outputs.
| Digit | ABCD | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|---|
| 0 | 0000 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0001 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0010 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 3 | 0011 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 4 | 0100 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 5 | 0101 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 6 | 0110 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 7 | 0111 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 8 | 1000 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 9 | 1001 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
The codes 1010 to 1111 are don't cares. Minimising each column with a K-map gives, for example, , , and .
4.13 Magnitude comparators
A magnitude comparator compares two binary numbers and and gives three outputs: , and .
For 1 bit: is (XNOR), is and is .
For 2 bits ( against ) let (bit equal). Then
- ,
- ,
- .
The comparison starts at the most significant bit: the first unequal bit decides. The IC 7485 is a 4-bit comparator with cascading inputs.
Worked Examples
1
Add the 4-bit numbers (6) and (7) with a ripple carry adder built from full adders, and show the carry and sum of every stage. Then use carry look-ahead to find to for the same numbers.
Stage by stage (C0 = 0). Bit 0: , , : and . Bit 1: , , : and . Bit 2: , , : and . Bit 3: , , : and .
Result. The sum is with , which agrees with .
Carry look-ahead. Generate and propagate : , ; , ; , ; , . Using : . . . . These match the ripple values but were found without waiting for the earlier stages.
(13), carries .
2
Implement using a 4:1 multiplexer with and as the select lines.
Split the truth table by the select inputs. With and the four groups are the rows (minterms 0 and 1), (2 and 3), (4 and 5), (6 and 7).
Find each data input as a function of . For : when and when , so . For : (minterm 2) and (minterm 3), so . For : minterms 4 and 5 are both 0, so . For : minterms 6 and 7 are both 1, so .
Connections. , (one inverter), (ground), (). The output is .
with , .
3
Design a 4-to-2 priority encoder with as the highest priority and a valid output . Give the minimised equations and test them for the input .
Truth table. Take the table of section 4.8 with don't cares for the lower-priority inputs.
Minimise. for the output codes 10 and 11, which occur exactly when or , so . for code 01 (, , ) and 11 (), so . .
Test with 0110. , , , . , , . The output code is , so the highest active input was encoded and was ignored.
, , ; for 0110 the output is , .
Exercises
Exercises: Combinational Logic Circuits
Design a full subtractor: write its truth table, derive the difference and borrow equations, and verify with .
Truth table logic. modulo 2 and when . The rows with are and the rows with are .
Equations. and (from the K-map: pairs for , and ).
Check. For : and . Indeed with a borrow of 1 (that is ).
, ; for 011 the outputs are , .
Implement a full adder using a 3-to-8 decoder and two OR gates.
A 3-to-8 decoder with inputs gives the minterms .
From the full adder truth table and . So connect to a 4-input OR gate for and to another 4-input OR gate for .
and with two 4-input OR gates.
Minimise segment of a BCD to seven-segment decoder (on for digits 0, 2, 3, 5, 6, 7, 8, 9) using a K-map with don't cares for 10 to 15.
| AB / CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 1 | 1 |
| 01 | 0 | 1 | 1 | 1 |
| 11 | X | X | X | X |
| 10 | 1 | 1 | X | X |
With the don't cares: the octet 8 to 15 (the cells 8, 9 and the X cells 10 to 15) has fixed and gives . The octet of cells 2, 3, 6, 7, 10, 11, 14, 15 has fixed and gives . The quad 5, 7, 13, 15 has and gives . The four corners 0, 2, 8, 10 give . Together they cover 0, 2, 3, 5, 6, 7, 8, 9.
Design a 2-bit comparator and test it for and , and for , .
Let and . Then , and .
For , : , so is 1; makes and zero. For : , so , and both and are 0, so the other outputs are 0.
Equations as above; , gives ; gives .
Find the sum and carry out of the 4-bit addition () with carry look-ahead: compute every , , the carries and the sum bits.
and (bit 0 is the right-most). : , , , . : , , , .
. . . .
Sum bits : , , , . So with carry out , that is .
(17); , , carries .