Lecture 8: Combinatorial Logic Circuits
1. Systematically design combinatorial logic circuits.
2. Simplify combinatorial logic circuits by Karnaugh maps.
Combinatorial Logic Circuits
Implementation of Boolean Expressions:
Boolean expressions can be implemented by interconnection of AND gates, OR gates, and inverters.
We can manipulate a logic expression to find an equivalent expression that is simpler.
DE E
D A C
DE D
D CE D
C AC
DE D
D CE D
C B B AC
DE D
D CE D
C ABC C
B A
E D D C ABC C
B A F
+ + +
=
+ +
+ +
=
+ +
+ +
+
=
+ +
+ +
+
=
+ +
+ +
=
) (
) (
) )(
(
De Morgan’s Laws
ABC = A + B + C
( D + E + F ) = D E F
If the variables in a logic expression are replaced by their inverses, the AND operation is replaced by OR, the OR operation is replaced by AND, and the entire expression is inverted, the resulting logic expression yields the same values as before the changes.
An important implication of De Morgan’s laws in that we can implement any logic function by using AND gates and inverters, since OR operation can be replaced by AND operation and logic inversions.
Similarly, any logic function by using OR gates and inverters, since AND operation can be replaced by OR operation and logic inversions.
3
Additional Logic Gates
The NAND gate is equivalent to an AND gate followed by an inverter. Notice that the symbol is the same as for an AND gate, with a bubble at the output terminal to indicate that the output has been inverted after the AND operation. Similarly, the NOR
o logic variables A and B is represented by
gate is equivalent to an OR gate followed by an inverter. The exclusive-OR (XOR) operation for tw
B
A ⊕
, defined by1
0
1
1
1
0
0
0
0
=
⊕
=
⊕
=
⊕
0
1
1 ⊕ =
XOR is also called modulo-two addition. Note XOR produces a
The equivalence gate produces a high output only if both the
has a single input and produces an output with the same value as the input. It is commonly used to provide more
n-outs.
high output only if the two inputs have different value.
two inputs have the same value. A buffer
fa
Logical Sufficiency of NAND Gates (or NOR Gates)
5
Synthesis of Logic Circuits
In this section, we consider methods to implement logic circuits given the specification for the output in terms of the inputs. Generally, the initial specification is translated into a truth table or a Boolean logic expression that can be manipulated to find a practical implementation.
Sum-of-products Implementation
Product terms that include all of the input variables (or their inverses) are called minterms.
In a sum-of-products expression, we form a product of all the input variables (or their inverses) for each row of the truth table for which the result is logic 1. The output is the sum of these products.
Product-of-Sums Implementation
Sum terms that include all of the input variables (or their inverses) are called maxterms.
In a product-of-sums expression, we form a sum of all the input variables (or their inverses) for each row of the truth table for which the result is logic 0. The output is the product of these sums.
7
Combinatorial Logic Circuit Design
Example: The control logic for a residential heating systems is to operate as following: During the daytime, heating is required only if the temperature falls below 68F. At night, heating is required only for temperatures below 62F. Design a logic circuit that produces an output signal F that is high only when heating is required.
Assume:
D: 1 (daytime); 0 (night)
H: 1 (Temperature>68F); 0 (Temperature ≤68F) L: 1 (Temperature>62F); 0 (Temperature ≤62F)
9
Example: Show two ways to realize the XOR operation by using AND, OR, and NOT gates.
Example: Half Adder
Half adder is for the addition of two binary bits (without taking a carry from a preceding operation).
A B S (Sum) C (Carry)
0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1
11
Example: Full Adder
Full adder is for the complete addition of two binary bits, with taking a carry from a preceding operation.
A B C S (Sum) C (Carry)
0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 C represents the carry from a preceding operation.
Minimization of Logic Circuits
Karnaugh Maps
Each cell in a Karaugh maps contain a minterm, that is, a product of the N variables that appears in our logic expression (in either un-inverted or inverted form). As shown in the figure, the row and column assignment for two or more variables are arranged so that all adjacent terms change by only one variable.
13
We call two squares that have a common edge a 2-cube (or subcube). Similarly, four squares with common edges are called a 4-cube. In locating cubes, the maps should be considered to fold around from the top to bottom and from left to right. Therefore, the squares on the right-hand side are considered to be adjacent to those on the left-hand side, and the top of the map is adjacent to the bottom. Consequently, the four squares in the map corners form a 4-cube. Note that a cube consists of 2N cells.
In general, try to find the largest possible cubes to cover all the 1 entries in the map. Then the output can be written as sum of products of cubes, and each product consists of the variables appearing only in un-inverted or inverted forms.
15
Some more examples of cubes:
17
Rules:
1. Begin with isolated cells.
2. Find all cells that are adjacent to only one other cell, forming two-cell cubes.
Example:
_ jpg
19
AD
D
C
C
B
D
B
A
y = + + +
Example:
)
(
)
(
)
( xz y z y z
y = + +
21
Don’t Care Conditions
Another simplification technique may be employed whenever the value of the logic function to be implemented can be either a 1 or 1 0. This condition may result from the specification of the problem. When it does not matter whether a position in the map is filled by a 1 or a 0, we use a don’t care entry, denoted by an x. Then the don’t care can be used as either a 1 or a 0, depending on which results in a greater simplification.
Example:
D
C
A
C
B
D
B
y = + +
23
Example:
C
B
A
y = +
Example:
Applications of Combinatorial Logic Circuits
Many useful combinatorial circuits known as decoders,
information to be displayed in binary-coded decimal (BCD) form. Thus 0000 is
becomes 1101101. Hence, BCD-to-seven- segment decoder is a combinatorial circuit having four inputs
nd seven outputs.
Decoders, Encoders, and Translators
encoders, or translators are available as integrated circuits. In a calculator or watch, we may represent
for 0, 0001 is for 1, 0010 is for 2, and so on.
The calculator display typically consists of liquid crystals with seven segments, as illustrated in the following figure. The digits 0 through 9 are displayed by turning on appropriate segments. Thus a decoder is needed to translate the four-bit binary-coded decimal words into seven-bit words of the form ABCDEFG, for which A is high if segment A of the display is required to be on, B is high if segment B is required to be on, and so on. Thus, 0000 is translated to 1111110 because all segments except G are on to display the symbol for zero. Similarly, 0001 becomes 0110000, and 0010
a
25
The truth table of BCD-to-seven-segment decoder:
Decimal I3 I2 I1 I0 A B C D E F G
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
3 0 0 1 1 1 1 1 1 0 0 1
4 0 1 0 0 0 1 1 0 0 1 1
5 0 1 0 1 1 0 1 1 0 1 1
6 0 1 1 0 0 0 1 1 1 1 1
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
Another example is the three-to-eight-line decoder that has a three-bit input and eight output lines. The three-bit input word selects one of the output lines and that output becomes high. The truth table and a circuit implementation are shown in following.
27
Multiplexers
Multiplexers, or data selectors, are combinational logic circuits that permit the selection of one of many inputs. A typical multiplexer (MUX) has 2n data lines, n address (or data select) lines, and one output. In addition, other control inputs (e.g. enables) may exist. The MUX allows for one of the 2n inputs to be selected as the data output; the selection of which input is to appear to the output is made by way of the address lines. The following figure depicts the block diagram of a four-input MUX. The input data lines are labeled D0, D1, D2, and D3; the data select (or address) lines are labeled I0 and I1; and the output is available in both uncomplemented (un-inverted) form and complemented (inverted) is thus labeled F and F . Finally, an enable input, labeled E, is also provided, as a means of enabling or disabling the MUX: if E=1, the MUX is disables; if E=0, it is enabled. (Note that the bubble in the enable input represents a complement operation, which means 0 enabling the module.)
I1 I0 D3 D2 D1 D0 F
0 0 x x x 0 0
0 0 x x x 1 1
0 1 x x 0 x 0
0 1 x x 1 x 1
1 0 x 0 x x 0
1 0 x 1 x x 1
1 1 0 x x x 0
1 1 1 x x x 1
In the design of digital systems (e.g., microprocessors), a single line is often required to carry two or more different digital signals. However, only one signal at a time can be placed on the line. A MUX allows us to select, at different instants, the signal we wish to place on this single signal line.
29
Read-Only Memory (ROM)
A ROM is a logic circuit that holds information in storage in the form of binary numbers, which can not be altered but read by a logic circuit. It is an array of memory cells, each of which can store either a 1 or 0. The array consists of 2m×n cells, where n is the number of bits in each word stored in ROM. To access the information stored in ROM, m address lines are required. When an address is selected, in a fashion similar to the operation of the MUX, the binary word corresponding to the address selected appears at the output, which consists of n bits, that is, the same number of the bits as the stored words. In some sense, a ROM can be thought of as a MUX that has an output consisting of a word instead of a single bit.
Gate Arrays and Programmable Logic Devices
Digital logic design is performed today primarily using programmable logic devices (PLDs). These are arrays of gates having interconnections that can be programmed to perform a specific logic function. PLDs are large combinational logic modules consisting of arrays of AND and OR gates that can be programmed using special programming languages called Hardware description languages (HDLs). The following figure shows the block diagram of one type of high density PLD.
31
