Combinational logic design case studies
Arithmetic circuits
integer representations
addition/subtraction
arithmetic/logic units
General design procedure
Case studies
BCD to 7-segment display controller
Leap-year flag calculator
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 1
General design procedure
for combinational logic
1. Understand the problem
what is the circuit supposed to do?
write down inputs (data, control) and outputs
draw block diagram or other picture
2. Formulate the problem using a suitable design representation
truth table or waveform diagram are typical
may require encoding of symbolic inputs and outputs
3. Choose implementation target
programmable logic: FPGA, ROM, PAL, PLA
mux, decoder and OR-gate
discrete gates
4. Follow implementation procedure
HDL to be synthesized, K-maps for two-level logic, multi-level logic tools
design tools and hardware description language (e.g., Verilog) are crucial
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 2
BCD to 7-segment
c0
display controller c5 c1
c6
c4 c2
Understanding the problem
c3
input is a 4 bit bcd digit (A, B, C, D) c0 c1 c2 c3 c4 c5 c6
output is the control signals
for the display (7 outputs C0 – C6) BCD to 7–segment
Block diagram control signal
decoder
A B C D
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 3
Formalize the problem
Truth table
show don't cares
A B C D C0 C1 C2 C3 C4 C5 C6
Choose implementation target 0 0 0 0 1 1 1 1 1 1 0
if ROM, we are done 0 0 0 1 0 1 1 0 0 0 0
don't cares imply PAL/PLA 0 0 1 0 1 1 0 1 1 0 1
may be attractive 0 0 1 1 1 1 1 1 0 0 1
0 1 0 0 0 1 1 0 0 1 1
Follow implementation procedure 0 1 0 1 1 0 1 1 0 1 1
minimization using K-maps 0 1 1 0 1 0 1 1 1 1 1
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 0 0 1 1
1 0 1 – – – – – – – –
1 1 – – – – – – – – –
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 4
Implementation as minimized sum-of-products
15 unique product terms when minimized individually
A A A A A
1 0 X 1 1 1 X 1 1 1 X 1 1 0 X 1 1 0 X 1
0 1 X 1 1 0 X 1 1 1 X 1 0 1 X 0 0 0 X 0
D D D D D
C 1 1 X X C 1 1 X X C 1 1 X X C 1 0 X X C 0 0 X X
1 1 X X 1 0 X X 0 1 X X 1 1 X X 1 1 X X
B B B B B
A A
1 1 X 1 0 1 X 1 C0 = A + B D + C + B' D'
0 1 X 1
D
0 1 X 1
D C1 = C' D' + C D + B'
C 0 0 X X C 1 0 X X C2 = B + C' + D
C3 = B' D' + C D' + B C' D + B' C
0 1 X X 1 1 X X
C4 = B' D' + C D'
B B C5 = A + C' D' + B D' + B C'
C6 = A + C D' + B C' + B' C
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 5
Implementation as minimized S-o-P (cont'd)
Can do better
9 unique product terms (instead of 15)
share terms among outputs
each output not necessarily in minimized form
A A
C2 1 1 X 1
C2 1 1 X 1
1 1 X 1 1 1 X 1
D D
C 1 1 X X C 1 1 X X
0 1 X X 0 1 X X
B B
C0 = A + B D + C + B' D' C0 = B C' D + C D + B' D' + B C D' + A
C1 = C' D' + C D + B' C1 = B' D + C' D' + C D + B' D'
C2 = B + C' + D C2 = B' D + B C' D + C' D' + C D + B C D'
C3 = B' D' + C D' + B C' D + B' C C3 = B C' D + B' D + B' D' + B C D'
C4 = B' D' + C D' C4 = B' D' + B C D'
C5 = A + C' D' + B D' + B C' C5 = B C' D + C' D' + A + B C D'
C6 = A + C D' + B C' + B' C C6 = B' C + B C' + B C D' + A
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 6
PLA implementation
A B C D
BC'
B'C
B'D
BC'D
C'D'
CD
B'D'
A
BCD'
C0 C1 C2 C3 C4 C5 C6 C7
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 7
PAL implementation vs.
Discrete gate implementation
Limit of 4 product terms per output
decomposition of functions with larger number of terms
do not generally share terms in PAL anyway (although there are exceptions)
C2 = B + C' + D
C2 = B' D + B C' D + C' D' + C D + B C D'
C2 = B' D + B C' D + C' D' + W need another input and another output
W = C D + B C D'
decompose into multi-level logic (hopefully with CAD support)
find common sub-expressions among functions
C0 = C3 + A' B X' + A D Y
C1 = Y + A' C5' + C' D' C6
C2 = C5 + A' B' D + A' C D X = C' + D'
C3 = C4 + B D C5 + A' B' X' Y = B' C'
C4 = D' Y + A' C D'
C5 = C' C4 + A Y + A' B X
C6 = A C4 + C C5 + C4' C5 + A' B' C
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 8
Activity: divisible-by-4 circuit
BCD coded year (digits for thousands, hundreds, tens, and ones)
YM8 YM4 YM2 YM1 , YH8 YH4 YH2 YH1 , YT8 YT4 YT2 YT1 , YO8 YO4 YO2 YO1
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 9
Activity: divisible-by-4 circuit
BCD coded year (digits for thousands, hundreds, tens, and ones)
YM8 YM4 YM2 YM1 , YH8 YH4 YH2 YH1 , YT8 YT4 YT2 YT1 , YO8 YO4 YO2 YO1
Only need to look at low-order two digits of the year
all years ending in 00, 04, 08, 12, 16, 20, etc. are divisible by 4
if tens digit is even, then divisible by 4 if ones digit is 0, 4, or 8
if tens digit is odd, then divisible by 4 if the ones digit is 2 or 6
Translates into the following Boolean expression:
YT1’ (YO8’ YO4’ YO2’ YO1’ + YO8’ YO4 YO2’ YO1’ + YO8 YO4’ YO2’ YO1’ )
+ YT1 (YO8’ YO4’ YO2 YO1’ + YO8’ YO4 YO2 YO1’ )
Digits with values from 10 to 15 will never occur, simplify further to yield:
YT1’ ( YO == 0 | YO == 4 | YO == 8 | YO == 12)
+ YT1 (YO == 2 | YO == 6 | YO == 10 | YO == 14)
YT1’ YO2’ YO1’ + YT1 YO2 YO1’
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 10
Divisible-by-100 and divisible-by-400 circuits
Divisible-by-100 just requires checking that all bits of two low-order
digits are all 0:
YT8’ YT4’ YT2’ YT1’ • YO8’ YO4’ YO2’ YO1’
Divisible-by-400 combines the divisible-by-4 (applied to the
thousands and hundreds digits) and divisible-by-100 circuits:
(YM1’ YH2’ YH1’ + YM1 YH2 YH1’)
• (YT8’ YT4’ YT2’ YT1’ • YO8’ YO4’ YO2’ YO1’ )
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 11
Combining to determine leap year flag
Label outputs of the previous three circuits: D4, D100, and D400
leap_year_flag = D4 • D100’ + D400
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 12
Implementation of leap year flag
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 13
Implementation of leap year flag in FPGA
6 4-input LUTs
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 14
Summary for examples of combinational logic
Combinational logic design process
formalize problem: encodings, truth-table, equations
choose implementation technology (FPGA, ROM, PAL, PLA, discrete gates)
implement by following the design procedure for that technology
Binary number representation
positive numbers the same
difference is in how negative numbers are represented
2s complement easiest to handle: one representation for zero, slightly
complicated complementation, simple addition
Circuits for binary addition
basic half-adder and full-adder
carry lookahead logic
carry-select
Autumn 2010 CSE370 - XII - Combinational Logic Case Studies 15
