PadhaikoAll subjects

Combinational Logic Circuits

Digital Logic (ENEX 152)

Open in the Padhaiko app

4.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

  1. Read the problem and decide the number of inputs and outputs.
  2. Assign letters to inputs and outputs.
  3. Write the truth table for every output.
  4. Simplify each output with a K-map (or Boolean algebra).
  5. Draw the logic diagram, using the gate types that are available.
  6. 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.

Half Adder Truth Table
ABSum SCarry C
0000
0110
1010
1101

From the table: and . A half adder is one XOR gate and one AND gate.

Full Adder Truth Table
ABCinSum SCarry out Cout
00000
00110
01010
01101
10010
10101
11001
11111

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 .

Half and Full Subtractor Equations
CircuitDifferenceBorrow
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

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.

4:1 Multiplexer
S1S0Output Y
00I0
01I1
10I2
11I3

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.

4-to-2 Priority Encoder (D3 has highest priority)
D3D2D1D0Y1Y0V
0000XX0
0001001
001X011
01XX101
1XXX111

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.

Segment Table for Digits 0 to 9 (1 = segment on)
DigitABCDabcdefg
000001111110
100010110000
200101101101
300111111001
401000110011
501011011011
601101011111
701111110000
810001111111
910011111011

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

Example 1

1 (10 marks)

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.

Answer:

(13), carries .

Example 2

2 (8 marks)

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 .

Answer:

with , .

Example 3

3 (8 marks)

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.

Answer:

, , ; for 0110 the output is , .


Exercises

Exercises: Combinational Logic Circuits

Question 1

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 ).

Answer:

, ; for 011 the outputs are , .

Question 2

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 .

Answer:

and with two 4-input OR gates.

Question 3

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.

K-map for segment a (X = don't care)
AB / CD00011110
001011
010111
11XXXX
1011XX

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.

Answer:

Question 4

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.

Answer:

Equations as above; , gives ; gives .

Question 5

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 .

Answer:

(17); , , carries .

← Boolean Algebra and K-MapsSequential Logic Circuits →