Combinational Logic

Chapter 4
 Chapter Objectives
 Given its logic diagram, know how to analyze a
combinational logic circuit.
 Understand the functionality of a half adder and a full-
adder.
 Understand the concepts of overflow and underflow.
 Understand the implementation of a binary adder.
 Understand the implementation of a binary coded
decimal (BCD) adder.
 Understand the implementation of a binary multiplier.
 Understand fundamental combinational logic circuits:
decoder, encoder, priority encoder, multiplexer, and
three-state gate.

Combinational Logic 4- 2
 Chapter Objectives
 Know how to implement a Boolean function with a
multiplexer.
 Understand the distinction between gate-level, dataflow,
and a behavioral modeling with HDLs.
 Be able to write a gate-level Verilog or VHDL model of a
fundamental logic circuit.
 Be able to write a hierarchical hardware description
language (HDL) model of a combinational logic circuit.
 Be able to write a dataflow model of a fundamental
combinational logic circuit.
 Be able to write a Verilog continuous assignment
statement, or a VHDL signal assignment statement.

Combinational Logic 4- 3
 Chapter Objectives
 Know how to declare a Verilog procedural block, or a
VHDL process.
 Be able to write a simple testbench.

Combinational Logic 4- 4
4.1 Introduction
 Logic circuits for digital systems may be
combinational or sequential.
 A combinational circuit consists of logic gates
whose outputs at any time are determined
from only the present combination of inputs.

Combinational Logic 4- 5
4.2 Combinational Circuits
 Logic circuits for digital system
 Sequential circuits
 contain memory elements
 the outputs are a function of the current inputs and the
state of the memory elements
 the outputs also depend on past inputs

Combinational Logic 4- 6
 A combinational circuits
n
 2 possible combinations of input values

 Specific functions
 Adders, subtractors, comparators, decoders, encoders,
and multiplexers
 MSI circuits or standard cells

Combinational Logic 4- 7
4.3 Analysis of Combinational Circuit
 A combinational circuit
 make sure that it is combinational not sequential
 No feedback path
 derive its Boolean functions (truth table)
 design verification
 a verbal explanation of its function

Combinational Logic 4- 8
  A straight-forward procedure

F2 = AB+AC+BC
T1 = A+B+C
T2 = ABC
T3 = F2'T1
F1 = T3+T2

Figure 4.2
Logic diagram for analysis example.
Combinational Logic 4- 9
 F1 = T3+T2 = F2'T1+ABC
= (AB+AC+BC)'(A+B+C)+ABC
= (A'+B')(A'+C')(B'+C')(A+B+C)+ABC
= (A'+B'C')(AB'+AC'+BC'+B'C)+ABC
= A'BC'+A'B'C+AB'C'+ABC
 A full-adder
 F1: the sum
 F2: the carry

Combinational Logic 4-10

 The truth table

Combinational Logic 4-11

 4.4 Design Procedure
 The design procedure of combinational circuits
 State the problem (system spec.)
 determine the inputs and outputs
 the input and output variables are assigned symbols
 derive the truth table
 derive the simplified Boolean functions
 draw the logic diagram and verify the correctness

Combinational Logic 4-12

 Functional description
 Boolean function
 HDL (Hardware description language)
 Verilog HDL
 VHDL
 Schematic entry
 Logic minimization
 number of gates
 number of inputs to a gate
 propagation delay
 number of interconnection
 limitations of the driving capabilities

Combinational Logic 4-13

Code conversion example
 BCD to excess-3 code
 The truth table

Combinational Logic 4-14

 The maps

Combinational Logic 4-15

 The simplified functions
 z = D'
y = CD +C'D'
x = B'C + B'D+BC'D'
w = A+BC+BD
 Another implementation
 z = D'
y = CD +C'D' = CD + (C+D)'
x = B'C + B'D+BC'D‘ = B'(C+D) +B(C+D)'
w = A+BC+BD

Combinational Logic 4-16

 The logic diagram

Combinational Logic 4-17

4.5 Binary Adder-Subtractor
 Half adder
 0 + 0 = 0 ; 0 + 1 = 1 ; 1 + 0 = 1 ; 1 + 1 = 10
 two input variables: x, y
 two output variables: C (carry), S (sum)
 truth table

Combinational Logic 4-18

 S = x'y+xy'
C = xy
 the flexibility for implementation
 S=x⊕y
 S = (x+y)(x'+y')
 S' = xy+x'y'
S = (C+x'y')'
 C = xy = (x'+y')'

Combinational Logic 4-19

Combinational Logic 4-20
 Full-Adder
 The arithmetic sum of three input bits
 three input bits
 x, y: two significant bits
 z: the carry bit from the previous lower significant bit
 Two output bits: C, S

Combinational Logic 4-21

Combinational Logic 4-22
Combinational Logic 4-23
 S = x'y'z+x'yz'+ xy'z'+xyz
C = xy + xz + yz
 S = z⊕ (x⊕y)
= 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

Combinational Logic 4-24

 Binary adder

Combinational Logic 4-25

 Carry propagation
 when the correct outputs are available
 the critical path counts (the worst case)
 (A1,B1,C1) > C2 > C3 > C4 > (C5,S4)
 > 8 gate levels

Combinational Logic 4-26

 Reduce the carry propagation delay
 employ faster gates
 look-ahead carry (more complex mechanism, yet
faster)
 carry propagate: Pi = Ai⊕Bi
 carry generate: Gi = AiBi
 sum: Si = Pi⊕Ci
 carry: Ci+1 = Gi+PiCi
 C1 = G0+P0C0
 C2 = G1+P1C1 = G1+P1(G0+P0C0)
= G1+P1G0+P1P0C0
 C3 = G2+P2C2 = G2+P2G1+P2P1G0+ P2P1P0C0
Combinational Logic 4-27
 Logic diagram

Combinational Logic 4-28

 4-bit carry-look ahead adder
 propagation delay

Combinational Logic 4-29

Binary subtractor
 A-B = A+(2’s complement of B)
 4-bit Adder-subtractor
 M=0, A+B; M=1, A+B’+1

Combinational Logic 4-30

  Overflow
 The storage is limited
 Add two positive numbers and obtain a negative
number
 Add two negative numbers and obtain a positive
number
 V = 0, no overflow; V = 1, overflow
Example:

Combinational Logic 4-31

4.6 Decimal Adder
 Add two BCD's
 9 inputs: two BCD's and one carry-in
 5 outputs: one BCD and one carry-out
 Design approaches
 A truth table with 2^9 entries
 use binary full Adders
 the sum <= 9 + 9 + 1 = 19
 binary to BCD

Combinational Logic 4-32

 BCD Adder: The truth table

Combinational Logic 4-33

 Modifications are needed if the sum > 9
 C=1
 K=1
 Z8Z4 = 1
 Z8Z2 = 1
 modification: −(10)d or +6
C = K +Z8Z4 + Z8Z2

Combinational Logic 4-34

 Block diagram

Combinational Logic 4-35

Binary Multiplier
 Partial products
– AND operations

Combinational Logic 4-36

 4-bit by 3-bit binary multiplier

Combinational Logic 4-37

4.8 Magnitude Comparator
 The comparison of two numbers
 outputs: A>B, A=B, A<B
 Design Approaches
 the truth table
2n
 2 entries - too cumbersome for large n
 use inherent regularity of the problem
 reduce design efforts
 reduce human errors

Combinational Logic 4-38

 Algorithm -> logic
 A = A3A2A1A0 ; B = B3B2B1B0
 A=B if A3=B3, A2=B2, A1=B1and A1=B1
 equality: xi= AiBi+Ai'Bi', for i = 0, 1, 2, 3
 (A=B) = x3x2x1x0
 (A>B) = A3B3'+x3A2B2'+x3x2A1B1'+x3x2x1 A0B0'
 (A>B) = A3'B3+x3A2'B2+x3x2A1'B1+x3x2x1 A0'B0
 Implementation
 xi = (AiBi'+Ai'Bi)'

Combinational Logic 4-39

Combinational Logic 4-40
4.9 Decoders
 A n-to-m decoder
n
 a binary code of n bits = 2 distinct information
n
 n input variables; up to 2 output lines
 only one output can be active (high) at any time

Combinational Logic 4-41

 An implementation

Combinational Logic 4-42

 Combinational logic implementation
 each output = a minterm
 use a decoder and an external OR gate to
implement any Boolean function of n input
variables

Combinational Logic 4-43

 Demultiplexers
 a decoder with an enable input
 receive information on a single line and transmits
n
it on one of 2 possible output lines

Figure 4.19
Two-to-four-line decoder with enable input.

Combinational Logic 4-44

 Expansion
 two 3-to-8 decoder: a 4-to-16 deocder

 a 5-to-32 decoder? Combinational Logic 4-45

 Combination Logic Implementation
 each output = a minterm
 use a decoder and an external OR gate to
implement any Boolean function of n input
variables
 A full-adder
 S(x,y,x)=Σ(1,2,4,7)
C(x,y,z)= Σ(3,5,6,7)

Combinational Logic 4-46

 two possible approaches using decoder
 OR(minterms of F): k inputs
n
 NOR(minterms of F'): 2 − k inputs
 In general, it is not a practical implementation

Combinational Logic 4-47

4.10 Encoders
 The inverse function of
a decoder

z = D1 + D3 + D5 + D7
y = D2 + D3 + D6 + D7 The encoder can be implemented
with three OR gates.
x = D4 + D5 + D6 + D7 Combinational Logic 4-48
Priority Encoder
 resolve the ambiguity of illegal inputs
 only one of the input is encoded

 D3 has the highest priority

 D0 has the lowest priority
 X: don't-care conditions
 V: valid output indicator Combinational Logic 4-49
■ The maps for simplifying outputs x and y

Combinational Logic 4-50

■ Implementation of priority

x = D2 + D3
y = D3 + D1D2′
V = D0 + D1 + D2 + D3
Combinational Logic 4-51
4.11 Multiplexers
 select binary information from one of many input
lines and direct it to a single output line
n
 2 input lines, n selection lines and one output line
 e.g.: 2-to-1-line multiplexer

Combinational Logic 4-52

 4-to-1-line multiplexer

Combinational Logic 4-53

Boolean function implementation
 MUX: a decoder + an OR gate
n
 2 -to-1 MUX can implement any Boolean function
of n input variable
 a better solution: implement any Boolean function
of n+1 input variable
 n of these variables: the selection lines
 the remaining variable: the inputs

Combinational Logic 4-54

Combinational Logic 4-55
 Procedure:
 assign an ordering sequence of the input variable
 the rightmost variable (D) will be used for the input
lines
 assign the remaining n-1 variables to the selection
lines w.r.t. their corresponding sequence
 construct the truth table
 consider a pair of consecutive minterms starting
from m0
 determine the input lines

Combinational Logic 4-56

Three-state gates
 A multiplexer can be constructed with three-state
gates
 Output state: 0, 1, and high-impedance (open ckts)

Combinational Logic 4-57

 4-12 HDL Models of Combinational Circuits

▓ Modeling Styles:
• Gate-level modeling, also called structural modeling,
using instantiations of predefined and user-defined
primitive gates.
• Dataflow modeling using continuous assignment
statements with the keyword assign.
• Behavioral modeling using procedural assignment
statements with the keyword always.

Combinational Logic 4-58

Combinational Logic 4-59
 Verilog—Construct corresponding to each of
three “classical” approaches to designing
combinational logics
 Continuous assignments (Boolean equations)
 Built-in primitives (logic diagrams)
 user-defined primitives (truth tables)
 VHDL—Constructs for describing
combinational logic using Boolean equation
and logic diagrams (schematics)

Combinational Logic 4-60

Figure 4.32
Relationship of VHDL constructs to truth tables, Boolean equations, and
schematics three-state gates.
Combinational Logic 4-61
 Gate-level Modeling

▓ The four-valued logic truth tables for the and, or, xor, and
not primitives

Combinational Logic 4-62

Hierarchical Modeling
 A hierarchical system can be composed of
multiple design objects organized in a
hierarchical structure.
 Parental module (Verilog)
 Parental design entity (VHDL)
 Underlying objects called children
 Two basic type: top-down or bottom-up
designs

Combinational Logic 4-63

 Hierarchical Modeling

Figure 4.33
Design hierarchy of an 8-bit ripple-carry adder. For simplicity, some
blocks are omitted where they replicate what is already shown.
Combinational Logic 4-64
 Hierarchical Modeling

Figure 4.34
Decomposition of an 8-bit ripple carry adder into a
chain of two 4-bit adders;9 each 4-bit adder consists
of a chain of four full adders. The full adders are
composed of half adders and one OR gate; the half
adders are composed of logic gates.
Combinational Logic 4-65
 HDL Models of Three-State Gates

■ Statement:
gate name (output, input, control);

Figure 4.35
Three-state gates.

Combinational Logic 4-66

Figure 4.36
Two-to-one-line multiplexer
with three-state buffers.
Combinational Logic 4-67
VHDL (User-Defined Buffers and Inverters)

註：請修改為
'1' else

Combinational Logic 4-68

Dataflow Modeling

Combinational Logic 4-69

 Dataflow Modeling

Table 4.11a
SystemVerilog Assignment Operators15.

Combinational Logic 4-70

 Dataflow Modeling

assign Y = (A && S) ||(B && (!S))

Table 4.11b
SystemVerilog Increment/Decrement Operators.

Combinational Logic 4-71

Table 4.12
Predefined VHDL Data Types.

Combinational Logic 4-72

 Table 4.13
VHDL Operators.

[註：表4.13有兩個符號需要修正；Relational 的符號修改為 = /= < <= > > =；

Multiplication Operator 的符號修改為 . / mod rem ] Combinational Logic 4-73
Figure 4.37
Interaction between testbench and Verilog
design unit.

註：請修改為
, m_out Combinational Logic 4-74
Figure 4.38
Interaction between testbench and
VHDL design unit.

[註：此圖內有黃色底色註記的文
字的修正如下：
Some_Design_Unit  Design_Unit
；select  sel；t_select  t_sel]

Combinational Logic 4-75

Figure 4.39
Circuit for event-driven simulation.

Combinational Logic 4-76

Figure 4.40
Representation of event-driven
simulation (with zero delay).

Combinational Logic 4-77

Figure 4.41
Representation of event-driven simulation
(with propagation delay).

Combinational Logic 4-78