Combinational logic

Logic circuits for digital systems are two

types:
• combinational circuits:
• A combinational circuit consists of logic gates whose outputs at any time are
determined from only the present combination of inputs.
• A combinational circuit performs an operation that can be specified logically
by a set of Boolean functions.
• sequential circuits:
• employ storage elements in addition to logic gates.
• Their outputs are a function of the inputs and the state of the storage
elements.
• Because the state of the storage elements is a function of previous inputs, the
outputs of a sequential circuit depend not only on present values of inputs,
but also on past inputs.
• For n input variables, there are 2n possible combinations of the binary
inputs.
• For each possible input combination, there is one possible value for each
output variable.
• A combinational circuit can be specified with a truth table that lists the
output values for each combination of input variables.
• A combinational circuit also can be described by m Boolean functions, one
for each output variable. Each output function is expressed in terms of the
n input variables.
Analysis Procedure
• The analysis of a combinational circuit requires that we determine the
function that the circuit implements.

• The diagram of a combinational circuit has logic gates with no feedback

paths or memory elements .
• A feedback path is a connection from the output of one gate to the
input of a second gate whose output forms part of the input to the
first gate.
• Feedback paths in a digital circuit define a sequential circuit and must
be analyzed by special methods and will not be considered here.
e.g. Obtain the output Boolean functions from a logic diagram:
e.g. Obtain the output Boolean functions from a logic diagram:
Design Procedure
1. Determine the required number of inputs and outputs and assign a
symbol to each.
2. Derive the truth table that defines the required relationship
between inputs and outputs.
3. Obtain the simplified Boolean functions for each output as a
function of the input variables.
4. Draw the logic diagram.
Code Conversion Example
Design a combinational circuit to convert binary coded decimal (BCD)
to the excess-3 code for the decimal digits.
Hint: excess-3 code= BCD code+ 0011
4 inputs
24 combinations

4 outputs
4 output functions
m6 = 0
Draw the logic diagram

B(C+D)'

B'(C+D)
Binary adder-subtractor
Half adder
A combinational circuit that performs the addition of two bits is called
a half adder
Full adder
A combinational circuit that performs the addition of three bits (two
significant bits and a previous carry)
𝑆 = 𝑧 𝑥 ′ 𝑦 ′ + 𝑥𝑦 + 𝑧 ′ 𝑥 ′ 𝑦 + 𝑥𝑦 ′ H’=(𝑥⨁𝑦)′ = 𝑥 ′ 𝑦 ′ + 𝑥𝑦
H=𝑥⨁𝑦 = 𝑥 ′ 𝑦 + 𝑥𝑦 ′
𝑆 = 𝑧 𝑥 ′ 𝑦 ′ + 𝑥𝑦 + 𝑧 ′ 𝑥 ′ 𝑦 + 𝑥𝑦 ′

𝑆 = 𝑧𝐻 ′ + 𝑧 ′ 𝐻 = 𝑧⨁𝐻 = 𝑥⨁𝑦⨁𝑧
Two half adders can be employed to implement a
full adder
 𝑥⨁𝑦 = 𝑥 ′ 𝑦 + 𝑥𝑦 ′
𝐶 = 𝑥𝑦 + 𝑥𝑧 + 𝑦𝑧
= 𝑥𝑦 + 𝑥𝑧(y+y’) + 𝑦𝑧(x+x’)
= 𝑥𝑦 + 𝑥𝑦𝑧 + 𝑥𝑧𝑦′ +(yzx+yzx’)
=xy+xyz+zxy’+zyx’
=xy(1+z)+z(xy’+x’y)
=xy+z(x ⨁y)
Addition of n-bit numbers requires a chain of n full adders or a chain of
one-half adder and n - 1 full adders.
• example, consider the two binary numbers A = 1011 and B = 0011.
Their sum S = 1110 is formed with the four-bit adder as follows:
The sum of two n-bit binary numbers A and B can be generated in
two ways:
• Serial: one full adder and a storage device to hold the carry
• Parallel: n full adder circuit
• The output carry from one full adder is connected to the input carry of the full
adder one position to its left
• An n bit parallel adder requires n full adders
4-bit parallel adder
n bit parallel adder
4-bit parallel
subtractor
4 bit parallel adder/subtractor:
Line M to control the circuit as follows:
XOR(X,1)=X'
• Adder if M=0
• Subtractor if M=1
A-B OR A+B XOR(X,0)=X
M Bi

0 0 0

0 1 1

1 0 1

1 1 0
Two-bit by two-bit binary multiplier
Magnitude Comparator
• Design a combinational circuit that compares two bits
GT: A is greater than B
• Two Inputs: A, B EQ: A is equal to B
• Three outputs: LT: A is less than B

• A > B (GT output) GT = A > B

A m-bit
m
• A = B (EQ output) Magnitude EQ = A = B
B Comparator
• A < B (LT output) m
LT = A < B

• Exactly one of the three outputs must be equal to 1

• While the remaining two outputs must be equal to 0
Magnitude Comparator
• A combinational circuit that compares two unsigned integers
• Two Inputs: GT: A is greater than B
EQ: A is equal to B
• Unsigned integer A (m-bit number)
LT: A is less than B
• Unsigned integer B (m-bit number)

• Three outputs: GT = A > B

A[m–1:0] m-bit
• A > B (GT output) m
Magnitude EQ = A = B
• A = B (EQ output) B[m–1:0]
m Comparator
• A < B (LT output) LT = A < B

• Exactly one of the three outputs must be equal to 1

• While the remaining two outputs must be equal to 0
Example: 4-bit Magnitude Comparator
• Inputs:
• 𝐴 = 𝐴3 𝐴2 𝐴1 𝐴0
• 𝐵 = 𝐵3 𝐵2 𝐵1 𝐵0
• 8 bits in total  256 possible combinations
• Not simple to design using conventional K-map techniques
• The magnitude comparator can be designed at a
higher level
• Let us implement first the 𝐸𝑄 output (𝐴 is equal to 𝐵)
• 𝐸𝑄 = 1 ↔ 𝐴3 = 𝐵3 , 𝐴2 = 𝐵2 , 𝐴1 = 𝐵1 , and 𝐴0 = 𝐵0
• Define: 𝐸𝑖 = 𝐴𝑖 𝐵𝑖 + 𝐴′𝑖 𝐵𝑖′
• Therefore, 𝐸𝑄 = 𝐸3 𝐸2 𝐸1 𝐸0
The Greater Than Output
• Given the 4-bit input numbers: 𝐴 and 𝐵
1. If 𝐴3 > 𝐵3 then 𝐺𝑇 = 1, irrespective of the lower bits of 𝐴 and 𝐵
Define: 𝐺3 = 𝐴3 𝐵3′ (𝐴3 = 1 and 𝐵3 = 0)
2. If 𝐴3 = 𝐵3 (𝐸3 = 1), we compare 𝐴2 with 𝐵2
Define: 𝐺2 = 𝐴2 𝐵2′ (𝐴2 = 1 and 𝐵2 = 0)
3. If 𝐴3 = 𝐵3 and 𝐴2 = 𝐵2 , we compare 𝐴1 with 𝐵1
Define: 𝐺1 = 𝐴1 𝐵1′ (𝐴1 = 1 and 𝐵1 = 0)
4. If 𝐴3 = 𝐵3 and 𝐴2 = 𝐵2 and 𝐴1 = 𝐵1 , we compare 𝐴0 with 𝐵0
Define: 𝐺0 = 𝐴0 𝐵0′ (𝐴0 = 1 and 𝐵0 = 0)

• Therefore, 𝐺𝑇 = 𝐺3 + 𝐸3 𝐺2 + 𝐸3 𝐸2 𝐺1 + 𝐸3 𝐸2 𝐸1 𝐺0
The Less Than Output
• We can derive the expression for the 𝐿𝑇 output, similar to
𝐺𝑇
Given the 4-bit input numbers: 𝐴 and 𝐵
1. If 𝐴3 < 𝐵3 then 𝐿𝑇 = 1, irrespective of the lower bits of 𝐴 and 𝐵
Define: 𝐿3 = 𝐴′3 𝐵3 (𝐴3 = 0 and 𝐵3 = 1)
2. If 𝐴3 = 𝐵3 (𝐸3 = 1), we compare 𝐴2 with 𝐵2
Define: 𝐿2 = 𝐴′2 𝐵2 (𝐴2 = 0 and 𝐵2 = 1)
3. Define: 𝐿1 = 𝐴1′ 𝐵1 (𝐴1 = 0 and 𝐵1 = 1)
4. Define: 𝐿0 = 𝐴′0 𝐵0 (𝐴0 = 0 and 𝐵0 = 1)

• Therefore, 𝐿𝑇 = 𝐿3 + 𝐸3 𝐿2 + 𝐸3 𝐸2 𝐿1 + 𝐸3 𝐸2 𝐸1 𝐿0
Knowing 𝐺𝑇 and 𝐸𝑄, we can also derive 𝐿𝑇 = (𝐺𝑇 + 𝐸𝑄)′
BCD to 7-Segment Decoder
• Seven-Segment Display:
• Made of Seven segments: light-emitting diodes (LED)
• Found in electronic devices: such as clocks, calculators, etc.

a
A BCD to b
B c
7-Segment d
C e
 BCD to 7-Segment Decoder Decoder f
D
g
 Accepts as input a BCD decimal digit (0 to 9)
 Generates output to the seven LED segments to display the BCD digit
 Each segment can be turned on or off separately
Designing a BCD to 7-Segment Decoder
1. Specification: Truth Table
• Input: 4-bit BCD (A, B, C, D) BCD input 7-Segment decoder
A B C D a b c d e f g
• Output: 7-bit (a, b, c, d, e, f, g)
0 0 0 0 1 1 1 1 1 1 0
• Display should be OFF for 0 0 0 1 0 1 1 0 0 0 0
Non-BCD input codes 0 0 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 1 0 0 1
2. Formulation 0 1 0 0 0 1 1 0 0 1 1
• Done with a truth table 0 1 0 1 1 0 1 1 0 1 1
0 1 1 0 1 0 1 1 1 1 1
• Output is zero for 1010 to 1111
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 1 0 1 1
1010 to 1111 0 0 0 0 0 0 0
Designing a BCD to 7-Segment Decoder
3. Logic Minimization Using K-Maps
𝐶𝐷 K-map for 𝑎 𝐶𝐷 K-map for 𝑏 𝐶𝐷 K-map for 𝑐
00 01 11 10 00 01 11 10 00 01 11 10
𝐴𝐵 𝐴𝐵 𝐴𝐵
00 1 1 1 00 1 1 1 1 00 1 1 1
01 1 1 1 01 1 1 01 1 1 1 1
11 11 11
10 1 1 10 1 1 10 1 1

𝑎 = 𝐴′ 𝐶 + 𝐴′ 𝐵𝐷 + 𝐴𝐵 ′ 𝐶 ′ + 𝐵 ′ 𝐶 ′ 𝐷′
Optimized Logic Expressions
𝑏 = 𝐴′ 𝐵 ′ + 𝐵 ′ 𝐶 ′ + 𝐴′ 𝐶 ′ 𝐷′ + 𝐴′ 𝐶𝐷
𝑎 = 𝐴′ 𝐶 + 𝑇1 𝐷 + 𝑇2 𝐴 + 𝑇2 𝐷′
𝑐 = 𝐴′ 𝐵 + 𝐵 ′ 𝐶 ′ + 𝐴′ 𝐷
𝑏 = 𝐴′ 𝐵 ′ + 𝑇2 + 𝐴′ 𝐶 ′ 𝐷′ + 𝑇3 𝐶
Extracting common terms 𝑐 = 𝑇1 + 𝑇2 + 𝑇3
Let 𝑇1 = 𝐴′ 𝐵, 𝑇2 = 𝐵 ′ 𝐶 ′ , 𝑇3 = 𝐴′ 𝐷 𝑇1 , 𝑇2 , 𝑇3 are shared gates
 Designing a BCD to 7-Segment Decoder
3. Logic Minimization Using K-Maps
𝐶𝐷 K-map for 𝑑 𝐶𝐷 K-map for 𝑒 𝐶𝐷 K-map for 𝑓 𝐶𝐷 K-map for 𝑔
00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10
𝐴𝐵 𝐴𝐵 𝐴𝐵 𝐴𝐵
00 1 1 1 00 1 1 00 1 00 1 1
01 1 1 01 1 01 1 1 1 01 1 1 1
11 11 11 11
10 1 1 10 1 10 1 1 10 1 1

Common AND Terms Optimized Logic Expressions

 Shared Gates 𝑑 = 𝑇4 + 𝑇5 + 𝑇6 + 𝑇7 + 𝑇8 𝐷
𝑇4 = 𝐴𝐵 ′ 𝐶 ′ , 𝑇5 = 𝐵 ′ 𝐶 ′ 𝐷′ 𝑒 = 𝑇5 + 𝑇7
𝑇6 = 𝐴′ 𝐵 ′ 𝐶, 𝑇7 = 𝐴′ 𝐶𝐷′ 𝑓 = 𝑇4 + 𝑇5 + 𝑇8 + 𝑇9
𝑇8 = 𝐴′ 𝐵𝐶 ′ , 𝑇9 = 𝐴′ 𝐵𝐷′ 𝑔 = 𝑇4 + 𝑇6 + 𝑇8 + 𝑇9
Designing a BCD to 7-Segment Decoder
4. Technology Mapping A T4
B'
T2
Many Common AND terms: 𝑇0 thru 𝑇9 C'
𝑇0 = 𝐴′ 𝐶, 𝑇1 = 𝐴′ 𝐵, 𝑇2 = 𝐵 ′ 𝐶 ′ D' T5
𝑇3 = 𝐴′ 𝐷, 𝑇4 = 𝐴𝐵 ′ 𝐶 ′ , 𝑇5 = 𝐵 ′ 𝐶 ′ 𝐷′ B' T6
𝑇6 = 𝐴′ 𝐵 ′ 𝐶, 𝑇7 = 𝐴′ 𝐶𝐷′ A'
T0
𝑇8 = 𝐴′ 𝐵𝐶 ′ , 𝑇9 = 𝐴′ 𝐵𝐷′ C
D' T7
Optimized Logic Expressions
𝑎 = 𝑇0 + 𝑇1 𝐷 + 𝑇4 + 𝑇5 C' T8
A'
𝑏 = 𝐴′ 𝐵 ′ + 𝑇2 + 𝐴′ 𝐶 ′ 𝐷′ + 𝑇3 𝐶 T1
B
𝑐 = 𝑇1 + 𝑇2 + 𝑇3 D' T9
𝑑 = 𝑇4 + 𝑇5 + 𝑇6 + 𝑇7 + 𝑇8 𝐷
𝑒 = 𝑇5 + 𝑇7
𝑓 = 𝑇4 + 𝑇5 + 𝑇8 + 𝑇9 Showing only
𝑔 = 𝑇4 + 𝑇6 + 𝑇8 + 𝑇9 Outputs e, f, g e f g