Lecture 11
EC381
Digital Systems I
University of Tripoli
Combinational Circuits
A combinational logic circuit has:
• A set of m Boolean inputs,
• A set of n Boolean outputs, and
• n switching functions, each mapping the 2m input
combinations to an output such that the current output
depends only on the current input values
Block diagram:
Combinatorial
Logic
Circuit
m Boolean Inputs n Boolean Outputs
Combinational Logic Design Part 1 – 2
Design Procedure
1. Specification
• Write a specification for the circuit if one is not
already available
2. Formulation
• Derive a truth table or initial Boolean equations
that define the required relationships between the
inputs and outputs, if not in the specification
3. Optimization
• Apply 2-level and multiple-level optimization
• Draw a logic diagram or provide a netlist for the
resulting circuit using ANDs, ORs, and inverters
Combinational Logic Design Part 1 – 3
Design Procedure
4. Technology Mapping
• Map the logic diagram or netlist to the
implementation technology selected
5. Verification
• Verify the correctness of the final design
manually or using simulation
Combinational Logic Design Part 1 – 4
Design Example (Example)
1. Specification
BCD to Excess-3 code converter
• Transforms BCD code for the decimal digits to
Excess-3 code for the decimal digits
• BCD code words for digits 0 through 9:
4-bit patterns 0000 to 1001, respectively
• Excess-3 code words for digits 0 through 9:
4-bit patterns consisting of 3 (binary 0011)
added to each BCD code word
• Implementation:
multiple-level circuit
NAND gates (including inverters)
Combinational Logic Design Part 1 – 5
Design Example (continued)
2. Formulation
• Conversion of 4-bit codes can be most easily
formulated by a truth table
• Variables Input BCD Output Excess-3
- BCD: ABCD WXYZ
A,B,C,D 0000 0011
0001 0100
• Variables 0010 0101
- Excess-3 0011 0110
W,X,Y,Z 0100 0111
0101 1000
• Don’t Cares 0110 1001
- BCD 1010 to 1111 0111 1010
1000 1011
1001 1011
Combinational Logic Design Part 1 – 6
Design Example (continued)
3. Optimization
a. 2-level using
K-maps
W = A + BC + BD
X = B C + B D + BC D
Y = CD + C D
Z=D
Combinational Logic Design Part 1 – 7
Design Example (continued)
3. Optimization (continued)
b. Multiple-level using transformations
W = A + BC + BD
X = B C + B D + BC D
Y = CD + C D
Z= D G = 7 + 10 + 6 + 0 = 23 (GN=26)
• Perform extraction, finding factor:
T1 = C + D
W = A + BT1
X = B T1 + B C D
Y = CD + C D
Z= D G = 2 + 4 + 7 + 6 + 0 = 19
Combinational Logic Design Part 1 – 8
Design Example (continued)
3. Optimization (continued)
b. Multiple-level using transformations
T1 = C + D
W = A + BT1
X = B T1 + BC D
Y = CD + C D
Z =D G = 19
• An additional extraction not shown in the text since it
uses a Boolean transformation: (C D = C + D = T1 ):
W = A + BT1 G = 2 (T1) + 4 (W) + 6 (X) + 4 (Y)
X = B T1 + B T1 + 0(Z) = 16
Y = CD + T1
Z= D GN=19
Combinational Logic Design Part 1 – 9
Design Example (continued)
4. Technology Mapping
• Mapping with a library containing inverters and 2-input
NAND.
A
W
B X
C Y
D
Z
Combinational Logic Design Part 1 – 10
Design Example (Example 3-2)
BCD-to-Seven-Segment Decoder
7-Segment display
BCD
code BCD to 7-
segmant
Decoder
Display
Combinational Logic Design Part 1 – 11
Truth Table
a =?
b =?
c =?
d =?
e =?
f =?
g =?
Combinational Logic Design Part 1 – 12
3-4 Verification
Verification - show that the final circuit
designed implements the original
specification
Simple specifications are:
• truth tables
• Boolean equations
• HDL code
If the circuit does not meet its
specification, then it is incorrect. We
should redesign the circuit.
Combinational Logic Design Part 1 – 13
Basic Verification Methods
Manual Logic Analysis
• Find the truth table or Boolean equations for the final circuit
• Compare the final circuit truth table with the specified truth
table, or
• Show that the Boolean equations for the final circuit are equal
to the specified Boolean equations
Simulation
• Simulate the final circuit (or its netlist, possibly written as an
HDL) and the specified truth table, equations, or HDL
description using test input values that fully validate
correctness.
• The obvious test for a combinational circuit is application of all
possible “care” input combinations from the specification
Combinational Logic Design Part 1 – 14
Binary half-adder circuit
Basic definition of addition is to take two bits, and
add them, producing a sum and a carry out.
• The circuit that produces these two outputs is called a
binary half-adder.
Combinational Logic Design Part 1 – 15
Binary half‐adder implementation
We can draw different implementations of a binary half-
adder (depends on availability of XOR gates):
Combinational Logic Design Part 1 – 16
Binary full‐adders
Most commonly, we are interested in adding n‐bit numbers.
Therefore, we need to be able to also handle a carry in signal.
The circuit implementing these two functions is known as a binary
full‐adder.
Combinational Logic Design Part 1 – 17
Combinational Logic Design Part 1 – 18
Full-Adder
S = x'y'z+x'yz'+ xy'z'+xyz
C = xy+xz+yz
S = z(xy) = z’(xy'+x'y)+z(xy'+x'y)'= z'xy'+z'x'y+z((x'+y)(x+y')) =
xy'z'+x'yz'+xyz+x'y'z
C = z(xy'+x'y)+xy = xy'z+x'yz+ xy
Digital Systems 19