Combinational Circuit Design

Part I: Design Procedure and

Examples

Part II : Arithmetic Circuits

Part III : Multiplexer, Decoder,
Encoder, Hamming Code

1
 Combinational Circuits

n inputs Combinational m outputs

Circuits

A combinational circuit has:

• n Boolean inputs (1 or more),
• m Boolean outputs (1 or more)
• logic gates mapping the inputs
to the outputs
2
 Design Procedure
1. Specification
 Write a complete specification for the circuit
 Specify/Label input and output
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
 Apply hierarchical design if appropriate
3. Optimization
 Apply 2-level and multiple-level optimization
(Boolean Algebra, K-Map, software)
 Draw a logic diagram for the resulting circuit
using necessary logic gates. 3
 Design Procedure (Cont.)

4. Technology Mapping
• Map the logic diagram to the implementation
technology selected (e.g. map into NANDs)
5. Verification
• Verify the correctness of the final design
manually or using a simulation tool

Practical Considerations:
• Cost of gates (Number)
• Maximum allowed delay
• Fan-in/Fan-out (# of Input ports/Output
ports provided by devices)

4
 Example 1
 Question: Design a circuit that has a 3-
bit binary input and a single output (f)
specified as follows:
• F = 0, when the input is less than (5)10
• F = 1, otherwise
 Solution:
 Step 1 (Specification):
• Label the inputs (3 bits) as X, Y, Z
• X is the most significant bit, Z is the least
significant bit
• The output (1 bit) is F:
• F = 1  (101)2, (110)2, (111)2
• F = 0  other inputs
5
 Example 1 (cont.)

Step 2 Step 3
(Formulation) (Optimization)
Obtain Truth table
F = XY’Z+XYZ’+XYZ
X Y Z F
= XY’Z+XYZ’+XYZ+XZ+XY
0 0 0 0
= XZ + XY
0 0 1 0
(Use consensus theorem)
0 1 0 0
0 1 1 0
Circuit Diagram
1 0 0 0
1 0 1 1
X
1 1 0 1 Z
1 1 1 1 F
X
Boolean Expression: Y
F = XY’Z+XYZ’+XYZ
6
 Example 2
 Question (BCD to Excess-3 Code
Converter)

• Code converters convert from one code

to another (BCD to Excess-3 in this
example)
• The inputs are defined by the code that is
to be converted (BCD in this example)
• The outputs are defined by the converted
code (Excess-3 in this example)
• Excess-3 code is a decimal digit plus
three converted into binary, i.e., 0 is
0011, 1 is 0100, etc.
7
 Example 2 (cont.)
Step 1 (Specification)
 4-bit BCD input (A,B,C,D)
 4-bit E-3 output (W,X,Y,Z) BCD Input Excess 3 Output
Decimal A B C D W X Y Z
Step 2 (Formulation) 0 0 0 0 0 0 0 1 1
Obtain Truth table 1 0 0 0 1 0 1 0 0
2 0 0 1 0 0 1 0 1
3 0 0 1 1 0 1 1 0
4 0 1 0 0 0 1 1 1
5 0 1 0 1 1 0 0 0
6 0 1 1 0 1 0 0 1
7 0 1 1 1 1 0 1 0
8 1 0 0 0 1 0 1 1
9 1 0 0 1 1 1 0 0
10-15 All other inputs X X X 8X
Example 2 (cont.)
Step 3 (Optimization)

source: Mano’s book

9
 Example 3
Question (BCD-to-Seven-Segment
Decoder)

src: Mano’s book

 A seven-segment display is digital readout found in

electronic devices like clocks, TVs, etc.
 Made of seven light-emitting diodes (LED) segments;
each segment is controlled separately.
 A BCD-to-Seven-Segment decoder is a
combinational circuit
 Accepts a decimal digit in BCD (input)
 Generates appropriate outputs for the segments to
display the input decimal digit (output)

10
 Example 3 (cont.)
Step 1 (Specification):
a b c d e f g
 4 inputs (A, B, C, D)
 7 outputs (a, b, c, d, e, f, g)
Step 2 (Formulation) BCD-to-Seven-
BCD Input 7 Segment Decoder Segment
Decimal A B C D a b c d e f g Decoder
0 0 0 0 0 1 1 1 1 1 1 0
1 0 0 0 1 0 1 1 0 0 0 0
2 0 0 1 0 1 1 0 1 1 0 1 A B C D

3 0 0 1 1 1 1 1 1 0 0 1
4 0 1 0 0 0 1 1 0 0 1 1 Invalid
BCD
5 0 1 0 1 1 0 1 1 0 1 1 codes
6 0 1 1 0 1 0 1 1 1 1 1 =
No Light
7 0 1 1 1 1 1 1 0 0 0 0
8 1 0 0 0 1 1 1 1 1 1 1
9 1 0 0 1 1 1 1 0 0 1 1
10-15 All Other Inputs 0 0 0 0 0 0 0 11
 Example 3 (cont.)
Step 3 (Optimization)

a b c d

e f g 12
 Example 3 (cont.)
Step 3 (Optimization) (cont.)

a = A’C + A’BD + AB’C’ + B’C’D’

b = A’B’ + A’C’D’ + A’CD + B’C’
c = A’B + B’C’ + A’C’ + A’D
d = A’CD’ + A’B’C +
B’C’D’+AB’C’+A’BC’D
e = A’CD’ + B’C’D’
f = A’BC’ + A’C’D’ + A’BD’ + AB’C’
g = A’CD’ + A’B’C + A’BC’ + AB’C’

Exercise: Draw the circuit

13
Part II Arithmetic Circuits
 Adder
 Subtractor
 Carry Look Ahead Adder
 BCD Adder
 Multiplier

14
 Half Adder

Design a half-Adder for 1-bit numbers

 1. Specification: 3. Logic Diagram
Optimization/Circuit
2 inputs (X,Y)
2 outputs (C,S)
 2. Formulation:
x y c s
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0 Graphical Symbol

15
 Full Adder
A combinational circuit that adds 3 input bits (xi,
yi, cin) to generate a Sum bit and a Carry-out bit

16
From Brown’s Fundamentals of digital logic
Full Adder Logic Diagram

17
From Brown’s Fundamentals of digital logic
 Full Adder = 2 Half Adders

Block diagram

Circuit
Exercise : Verify this full-adder implementation.
18
From Brown’s Fundamentals of digital logic
 Bigger Adders
 How to build an adder for n-bit
numbers?
 Example: 4-Bit Adder
 Inputs ? 9 inputs
 Outputs ? 5 outputs
 What is the size of the truth table?
512 rows!
 How many functions to optimize? 5
functions

19
 Ripple Carry Adder

Note:
• Carry signal “ripples” through the full-adder stages.
• Delay can be an issue.

20
Subtraction (2’s Complement)

 How to build a subtractor using 2’s

complement?

Src: Mano’s Book

S = A + ( -B)
21
 Adder/Subtractor

0 : Add
1: subtract

Src: Mano’s Book

Using full adders and XOR we can build an Adder/Subtractor!

22
 Full-Adder (Review)

si = xi ⊕ yi ⊕ ci ; ci +1 = xi yi + xi ci + yi ci
23
Carry-Lookahead Adder (CLA)

Define g i = xi yi ; pi = xi + yi
Then ci +1 = g i + pi ci
 gi is called “generate” function and
pi is called “propagate” function.
 Rewriting ci+1 in terms of i-1 terms
yields
ci +1 = g i + pi ( g i −1 + pi −1ci −1 )
= g i + pi g i −1 + pi pi −1ci −1
24
 CLA (cont.)

 Repeating until 0 term yields

ci +1 = g i + pi g i −1 + pi pi −1 g i − 2 + L + pi pi −1 L p2 p1 g 0
+ pi pi −1 L p2 p1 p0 c0

 ci+1can be implemented in 2-level

AND-OR circuits.
 A Carry-Lookahead Adder is based
on this expression.
25
Ripple-carry Adder Delay

Only First 2
stages shown

LSB:
(x0 , y0) = (0,1)

Delay: 5 gates

For n stages:
Delay: 2n+1 gates

26
From Brown’s Fundamentals of digital logic
CLA Delay
Only First 2
stages shown
LSB:
(x0 , y0) = (0,1)

c1 = g 0 + p0 c0
c2 = g1 + p1 g 0
+ p1 p0 c0

Delay: 3 gates
For n stages:
Delay: 3 gates27
 CLA Implementation

 Total delay : 4 gates (1 for all gi ,pi , 2 for

all carry, 1 for the final XOR to compute
all si)
 Becomes very complex when n large.
 Hierarchical CLA with ripple-carry

28
CLA : A better implementation
Consider c8 out of block 0:
c8 = g 7 + p7 g 6 + p7 p6 g 5 + L + p7 p6 L p2 p1 g 0
+ p7 p6 L p2 p1 p0 c0
Recall that c1 = g 0 + p0 c0
If define P0 = p7 p6 p5 p4 p3 p2 p1 p0 c0
G0 = g 7 + p7 g 6 + p7 p6 g 5 + L+ p7 p6 L p2 p1 g 0
Then can write c8 = G0 + P0 c0
Likewise c16 = G1 + P1G0 + P1 P0 c0
c16 = G2 + P2G1 + P2 P1G0 + P2 P1 P0 c0
c32 = G3 + P3G2 + P3 P2G1 + P3 P2 P1G0 + P3 P2 P1 P0 c0
29
CLA : A better implementation

30
BCD Addition

31
BCD Adder

Adjust=0 -> S = Z + 0
Adjust=1 -> S = Z + 6

32
4-bit Comparator

0 1 1 0 0 0 1 0 1
0101111
0 1 0 1 1 1 0 0
1 0 0 0 0 1 1 1

3-(-5)=-8 -5-4=7 33
 4-bit Comparator
 X<Y
 Same sign: No overflow (V=0) and N=1
 Different sign: V=0 && N=1, OR V=1
(overflow) && N=0 (positive)
 Thus, condition is N⊕
⊕V=1.
 X = Y -> Z = 1
 X>Y
 Same sign: No overflow (V=0) and N=0
 Different sign: V=0 && N=0, OR V=1
(overflow) && N=1 (negative)
 Thus, condition is N⊕
⊕V=0, i.e., the
complement of N⊕ ⊕V, (N⊕
⊕V)’.
34
 2-to-1 Multiplexer (MUX)

Multiplexer has multiple

inputs and one output; it
passes the signal on one
input to the output.
Symbol Truth Table

SOP circuit
Circuit with transmission gates
35
 4-to-1 Multiplexer

f = s1 ' s0 ' w0 + s1 ' s0 w1 + s1s0 ' w2 + s1s0 w3

36
 4-to-1 Multiplexer

4-to-1 mux using

2-to-1 mux
16-to-1 mux using
4-to-1 mux

37
 2×
×2 crossbar switch

 2 inputs, 2 outputs
 s = 0 -> connect x1->y1, x2->y2
 s = 1 -> connect x1->y2, x2->y1

38
Synthesis of Logic Functions

f = w1 ⊕ w2

39
3-input XOR

Using
2-to-1 MUX

Using
4-to-1 MUX

40
 3-input Majority Function
 Get 3 inputs and output 1 if # of 1’s
greater than # of 0’s.

41
 Shannon’s Expansion
 Shannon’s Expansion Theorem
f ( w1 , w2 ,K, wn ) = w1 ' f (0, w2 ,K, wn ) + w1 f (1, w2 ,K, wn )
= w1 ' f w1 ' + w1 f w1 f w1 ' , f w1 : cofactors

 Example : 3-input majority function

f = w1 ' w2 w3 + w1w2 ' w3 + w1w2 w3 '+ w1w2 w3 = w1w2 + w2 w3 + w1w3
Can be rewritten as
f = w1w2 + w2 w3 + w1w3 = w1 ' ( w2 w3 ) + w1 ( w2 + w3 )

42
 Shannon’s Expansion

Using
2-to-1 MUX

 3-input XOR
f = w1 ⊕ w2 ⊕ w3 = w1 ' ( w2 ⊕ w3 ) + w1 (w2 ⊕ w3 )'
43
 Shannon’s Expansion

 In general : expand by wi
f (w1 , w2 ,K, wn ) = wi ' f ( w1 , w2 ,K,0,K, wn ) + wi f ( w1 , w2 ,K,1,K, wn )
= wi ' f wi ' + wi f wi

 2-variable expansion:
f ( w1 , w2 ,K, wn ) = w1 ' w2 ' f (0,0, w3 ,K, wn ) + w1 ' w2 f (0,1, w3 ,K, wn )
+ w1w2 ' f (1,0, w3 ,K, wn ) + w1w2 f (1,1, w3 ,K, wn )

which can be implemented by a 4-to-1

MUX.
44
 Example 1
f = w1 ' w3 '+ w1w2 + w1w3
= w1 ' w3 '+ w1 ( w2 + w3 )
= w1 ' w2 ' w3 '+ w1 ' w2 w3 '+ w1w2 ' w3 + w1w2 (1)

Using
Using 4-to-1 MUX
2-to-1 MUX

45
 3-input majority function

f = w1w2 + w2 w3 + w1w3 = w1 ' ( w2 w3 ) + w1 ( w2 + w3 )

Let g = w2w3, h = w2+w3, then
g = w2 ' (0) + w2 w3 ; h = w2 ' w3 + w2 (1)

46
 Decoder
 Main function: decode “encoded” data.
n-to-2n decoder

2-to-4 decoder 47
 Decoder

3-to-8 decoder using

2-to-4 decoder

4-to-1 MUX using

2-to-4 decoder

48
4-to-16 Decoder

49
 Demultiplexer (DEMUX)

A 2m ×m ROM Block

50
 Encoder

2n-to-n encoder

4-to-2 binary encoder

51
 Hamming Code

 In “linear block code” family.

 Can correct 1-bit error or detect
2-bit error.
 Add parity bits to message bits.
 Typically use notation (n,k)
Hamming code, which means n
total bits, k message bits.
 Clearly there are (n-k) parity bits.

52
(7,4) Hamming Code

System Structure
53
 Codewords

Codeword : a3a2a1a0r2r1r0 with

r0 = a0 ⊕ a1 ⊕ a2 ; r1 = a1 ⊕ a2 ⊕ a3 ; r2 = a0 ⊕ a1 ⊕ a3 54
 Syndrome

 Error pattern is given by “syndrome”, i.e., s2s1s0

(=s) where
s0 = b0 ⊕ b1 ⊕ b2 ⊕ q0 ; s1 = b1 ⊕ b2 ⊕ b3 ⊕ q1 ; s2 = b0 ⊕ b1 ⊕ b3 ⊕ q2

 Example : Send 0110100

 Receive 0110100 -> s = 000 -> No error
 Receive 0111100 -> s = 101 -> Error at b0
 Receive 0010100 -> s = 011 -> Error at b2

55
(7,4) Hamming Encoder

Exercise : Design the

(7,4) Hamming Decoder
56
Gate Arrays (Programmable Logic Device)

Basic
Structure
(AND-OR GA)

57
Example
f = a’b’ + abc
g = a’b’c’ + ab + bc
h = a’b’ + c

58
Simplified Diagram

59
Using ROM
W ( A, B, C , D ) = ∑ m(3,7,8,9,11,15)
X ( A, B, C , D ) = ∑ m(3,4,5,7,10,14,15)
Y ( A, B, C , D) = ∑ m(1,5,7,11,15)

60
 Using PLA
W ( A, B, C , D) = ∑ m(3,7,8,9,11,15); X ( A, B, C , D) = ∑ m(3,4,5,7,10,14,15)
Y ( A, B, C , D) = ∑ m(1,5,7,11,15)

W = AB' C '+CD = AB' C '+ A' CD + ACD

X = A' BC '+ ACD'+ A' CD + {BCD or ABC}
Y = A' C ' D + ACD + {BCD or A' BD}
61
Using PLA (2)

62
Using Programmable Array Logic

63