Chapter 6 Digital Electronics: Combinational Circuits
Chapter 6 — Digital Electronics: Combinational Circuits
Theory, worked examples and 39 previous-year questions with full solutions — IIT-JAM, GATE, JEST and CSIR NET-JRF, 2020 onwards.
Theory
The circuits of the preceding chapters process signals that vary continuously. A digital circuit, by contrast, recognises only two levels of voltage, a HIGH level and a LOW level, which we label 1 and 0. Any quantity it handles must therefore be coded as a string of 1’s and 0’s, and any operation it performs must be expressed in the algebra of two-valued variables. In this chapter we first develop the number systems and codes used to represent information in binary form, together with binary arithmetic and the representation of signed numbers. We then introduce Boolean algebra, the logic gates that realise its operations, the universal NAND and NOR gates, the standard sum-of-products and product-of-sums forms of a logic function, and the Karnaugh map, which gives a systematic method of reducing a logic function to its simplest form.
6.1 Number systems
Four number systems are important in digital electronics: the decimal, binary, octal and hexadecimal systems. All four are positional systems, differing only in the number of symbols they use, which is called the base or radix of the system. We indicate the base by a subscript, as in \((1011)_2\) or \((3574)_8\).
(a) The decimal number system
The decimal number system is called the base-10 system because it is composed of ten numerals or symbols, \(0,1,2,3,4,5,6,7,8\) and \(9\). It is a positional value system, in which the value of a digit depends on its position. Consider, for example, the decimal number 6897, which can be expressed as
The digit 6 represents six thousands, the digit 8 eight hundreds, the digit 9 nine tens and the digit 7 seven units. Since the digit 6 carries the greatest weight it is called the most-significant digit (MSD), while the digit 7, which carries the least weight, is called the least-significant digit (LSD). The same idea extends to the right of the decimal point. For example,
which is 2 tens plus 7 units plus 9 tenths plus 2 hundredths. The positions on either side of the decimal point therefore carry weights that are powers of 10, positive to the left of the point and negative to the right, as shown in Figure 6.1.
Figure 6.1 Position values of the digits of the decimal number 3547.216.
(b) The binary number system
The binary number system has only two digits, 0 and 1, which are called bits (binary digits). It too is a positional system, in which the weight of each bit is a power of 2, as shown in Figure 6.2. The leftmost bit is the most-significant bit (MSB) and the rightmost bit the least-significant bit (LSB).
Figure 6.2 Position values of the bits of the binary number 1101.101.
An \(n\)-bit binary number has \(2^n\) distinct values. Since the smallest is \(0\), the largest decimal value that can be represented by an \(n\)-bit binary number is
\[\boxed{N_{\max}=2^{n}-1}.\]
For example, with \(n=8\) we can count from \(0\) to \(2^{8}-1=256-1=255\), and with \(n=16\) from \(0\) to \(2^{16}-1=65536-1=65535\).
(c) The octal and hexadecimal number systems
The octal number system is composed of the eight digits \(0,1,2,3,4,5,6\) and \(7\). To count beyond 7 we continue with \(10,11,12,13,14,15,16,17,20,21,\dots\) and so on. The weight of each position is a power of 8, as shown in Figure 6.3.
Figure 6.3 Position weights in the octal number system.
The hexadecimal system is composed of sixteen digits, which include both numerals and alphabetic characters: \(0,1,2,3,4,5,6,7,8,9,\text{A},\text{B},\text{C},\text{D},\text{E}\) and \(\text{F}\). The letters stand for the decimal values \(\text{A}=10\), \(\text{B}=11\), \(\text{C}=12\), \(\text{D}=13\), \(\text{E}=14\) and \(\text{F}=15\), and the weight of each position is a power of 16. Because \(8=2^3\) and \(16=2^4\), each octal digit corresponds to exactly three bits and each hexadecimal digit to exactly four bits; this is why the two systems are used as compact ways of writing long binary numbers.
(d) Conversion to decimal
A number in any base is converted to decimal by multiplying each digit by its positional weight and adding the products. For the binary number \(11011.1010\) the weights of the integer bits are \(16,8,4,2,1\) and those of the fractional bits are \(\tfrac12,\tfrac14,\tfrac18,\tfrac1{16}\). Hence
The integer part of a decimal number is converted to base \(b\) by the successive-division method. The number is divided by \(b\), the quotient is divided again by \(b\), and so on until the quotient is zero; the remainders, read from the last to the first, are the digits of the number in base \(b\). The reason is that each division by \(b\) strips off the lowest digit as the remainder. For \((52)_{10}\) the divisions by 2 are as follows.
Division
Quotient
Remainder
\(52\div2\)
26
0 (LSB)
\(26\div2\)
13
0
\(13\div2\)
6
1
\(6\div2\)
3
0
\(3\div2\)
1
1
\(1\div2\)
0
1 (MSB)
Reading the remainders from the bottom upwards gives \((52)_{10}=(110100)_2\).
The fractional part is converted by the successive-multiplication method. The fraction is multiplied by \(b\); the integer part of the product is the first digit after the point, and the fractional part of the product is multiplied by \(b\) again, and so on. The digits are now read from the first to the last. For \((0.85)_{10}\),
so that \((0.85)_{10}\approx(0.110110)_2\) to six binary places. The fraction \(0.4\) has now reappeared, so the pattern \(0110\) repeats indefinitely: a terminating decimal fraction need not terminate in binary, and the conversion is stopped at the precision required.
A mixed number is converted by treating its integer and fractional parts separately. For \((24.625)_{10}\) the successive divisions of 24 by 2 leave the remainders \(0,0,0,1,1\), so that \(24=(11000)_2\), while
so that \(0.625=(0.101)_2\) exactly. Hence \((24.625)_{10}=(11000.101)_2\).
The same methods give the octal and hexadecimal forms, with 8 or 16 in place of 2. For \((234)_{10}\) we have \(234\div8=29\) remainder \(2\), \(29\div8=3\) remainder \(5\) and \(3\div8=0\) remainder \(3\), so that \((234)_{10}=(352)_8\). For \((2988.6875)_{10}\) the divisions give
Division
Quotient
Remainder
\(2988\div8\)
373
4
\(373\div8\)
46
5
\(46\div8\)
5
6
\(5\div8\)
0
5
and the multiplications give \(0.6875\times8=5.5\rightarrow5\) and \(0.5\times8=4.0\rightarrow4\), so that \((2988.6875)_{10}=(5654.54)_8\). Similarly, to convert \((2598.675)_{10}\) to hexadecimal we find \(2598\div16=162\) remainder \(6\), \(162\div16=10\) remainder \(2\) and \(10\div16=0\) remainder \(10=\text{A}\), while
and the digit C now repeats. Hence \((2598.675)_{10}=(\text{A26.ACC}\dots)_{16}\).
(f) Conversions among binary, octal and hexadecimal
Since \(8=2^3\), three bits are needed to represent each octal digit, according to the following table.
Octal
Binary
Octal
Binary
0
000
4
100
1
001
5
101
2
010
6
110
3
011
7
111
An octal number is therefore converted to binary simply by replacing each octal digit by its three-bit equivalent. Thus \(3\to011\), \(5\to101\), \(7\to111\), \(4\to100\) give \((3574)_8=(011\,101\,111\,100)_2\). In the same way \((34.562)_8=(011\,100.101\,110\,010)_2\), and \((2702)_8=(010\,111\,000\,010)_2=(10111000010)_2\) once the leading zero is dropped.
Conversely, a binary number is converted to octal by dividing its bits into groups of three, starting from the binary point and working both to the left and to the right, adding zeros at either end where necessary to complete a group, and replacing each group by its octal digit. Thus
and similarly \((370.526)_8=(11111000.101010110)_2\) and \((111\,110\,110\,011)_2=(7663)_8\).
Since \(16=2^4\), four bits are needed to represent each hexadecimal digit.
Hexadecimal
Binary
Hexadecimal
Binary
0
0000
8
1000
1
0001
9
1001
2
0010
A
1010
3
0011
B
1011
4
0100
C
1100
5
0101
D
1101
6
0110
E
1110
7
0111
F
1111
Thus \((9\text{AF})_{16}=(1001\,1010\,1111)_2\) and \((\text{FB3})_{16}=(1111\,1011\,0011)_2\). To convert from binary to hexadecimal the bits are grouped in fours from the binary point:
These groupings also provide a quick route from a large decimal number to binary: we first convert to octal or hexadecimal, which needs far fewer divisions, and then expand each digit into bits. For \((363)_{10}\), \(363\div8=45\) remainder \(3\), \(45\div8=5\) remainder \(5\), and \(5\div8=0\) remainder \(5\), so that
\[(363)_{10}=(553)_8=(101\,101\,011)_2.\]
For \((49056)_{10}\) we divide by 16:
Division
Quotient
Remainder
\(49056\div16\)
3066
0
\(3066\div16\)
191
10 = A
\(191\div16\)
11
15 = F
\(11\div16\)
0
11 = B
so that \((49056)_{10}=(\text{BFA0})_{16}=(1011\,1111\,1010\,0000)_2\).
Conversion between octal and hexadecimal is made through binary. To convert \((547)_8\) to hexadecimal we write \((547)_8=(101\,100\,111)_2\), regroup the bits in fours as \((0001\,0110\,0111)_2\), and read off \((167)_{16}\). In the same way, to convert hexadecimal to octal we first convert to binary and then regroup in threes:
The positional rule also allows us to find an unknown base from an equation between numbers, as the following examples show. In each case we expand both sides in powers of their bases and remember that every digit must be smaller than its base.
Example 6.1. If \((16)_{10}=(100)_b\), find \(b\).
Since the digit 4 appears in base \(x\), we need \(x>4\); since \(y\) is a digit in base 8, we need \(0\le y<8\). The values \(y=0,1,2\) give \(x=0,2,4\), which are not allowed, while \(y=3,4,5,6,7\) give \(x=6,8,10,12,14\), all of which are allowed. There are therefore five solutions.
Example 6.4. Find the number of possible solutions of \((123)_5=(x8)_y\), where \(x\) and \(y\) are positive integers.
Because the digits \(x\) and \(8\) appear in base \(y\), we need \(y>8\) and \(y>x\). The factorisations of 30 with \(y>8\) are \(x=1,\,y=30\); \(x=2,\,y=15\); and \(x=3,\,y=10\), all of which also satisfy \(y>x\), while \(x=5,\,y=6\) fails because \(y<8\). There are therefore three solutions.
6.2 Complements and signed binary numbers
(a) The 1’s and 2’s complements
The 1’s complement of a binary number is formed by changing every 1 to 0 and every 0 to 1. For example, the 1’s complement of \(1011000\) is \(0100111\), and the 1’s complement of \(0101101\) is \(1010010\).
The 2’s complement is obtained by adding 1 to the 1’s complement. Equivalently, it can be formed by leaving all the least-significant 0’s and the first 1 unchanged, and replacing 1’s by 0’s and 0’s by 1’s in all the higher-significant digits. For example, the 2’s complement of \(1101100\) is \(0010100\), and the 2’s complement of \(0110111\) is \(1001001\). For an \(n\)-bit number \(N\) the 1’s complement is \((2^{n}-1)-N\) and the 2’s complement is \(2^{n}-N\), which is why the 2’s complement behaves as the negative of \(N\) when the carry out of the \(n\)th bit is discarded.
(b) Signed binary numbers
If a binary number is assumed to be unsigned, its leftmost bit is simply its most-significant bit. If it is signed, the leftmost bit represents the sign and the remaining bits represent the number. The convention is to make the sign bit 0 for a positive number and 1 for a negative number. The same bit pattern therefore has different values according to the convention used, as the following table shows for the sign-magnitude form described below.
Given number
Value if unsigned
Value if signed (sign-magnitude)
01001
+9
+9
01101
+13
+13
1111
+15
−7
110110
54
−22
There are three common ways of representing a negative number. In the sign-magnitude form the sign bit is followed by the magnitude in ordinary binary. Thus, since \(41=(101001)_2\),
Positive numbers are written in the same way in all three representations. In the 1’s complement representation a negative number is the 1’s complement of the corresponding positive number (sign bit included), or, equivalently, the sign-magnitude form with every bit except the sign bit inverted. In the 2’s complement representation a negative number is the 2’s complement of the corresponding positive number, that is its 1’s complement representation plus 1 in the LSB. The 2’s complement form is the one used in practice, because it has a single representation of zero and allows subtraction to be performed by addition. An \(n\)-bit 2’s complement number ranges from \(-2^{n-1}\) to \(+(2^{n-1}-1)\).
Example 6.5. Write \(-41\) in the 1’s complement and 2’s complement representations.
Solution. We first write the positive number in sign-magnitude form, \(+41=0\,101001\). Inverting every bit gives the 1’s complement representation,
\[-41=1\,010110\qquad(\text{1's complement}),\]
whose sign bit is 1, as it must be. Adding 1 to the LSB gives the 2’s complement representation,
Example 6.6. Express \(-45\) in an 8-bit configuration by the 2’s complement method.
Solution. In 8 bits, \(+45=00101101\), and the sign-magnitude form of \(-45\) is \(10101101\). Taking the 1’s complement of the magnitude bits while keeping the sign bit, and then adding 1, we obtain
Solution. Since \(28=(11100)_2\), in 16 bits \(+28=0000\,0000\,0001\,1100\). Its 1’s complement is \(1111\,1111\,1110\,0011\), and adding 1 gives
\[-28=1111\,1111\,1110\,0100.\]
The answer is (d).
Example 6.8. Represent \(-44\) in 2’s complement representation using 8 bits.
Solution. We first find the binary equivalent of 44 by successive division.
Division
Quotient
Remainder
\(44\div2\)
22
0
\(22\div2\)
11
0
\(11\div2\)
5
1
\(5\div2\)
2
1
\(2\div2\)
1
0
\(1\div2\)
0
1
Hence \((44)_{10}=(101100)_2\), and adding two 0’s on the left to make 8 bits, \((+44)_{10}=(00101100)_2\). Replacing every 0 by 1 and every 1 by 0 gives the 1’s complement \(11010011\), and adding 1 gives the 2’s complement representation
\[(-44)_{10}=11010011+1=11010100.\]
6.3 Binary arithmetic
(a) Binary addition
Binary addition follows four rules:
\[0+0=0,\qquad0+1=1,\qquad1+0=1,\qquad1+1=0\ \text{with a carry of }1.\]
The carry is added into the next more significant column, exactly as in decimal addition, and when a column contains \(1+1\) plus a carry the result is 1 with a carry of 1. For example,
which in decimal are \(9-5=4\) and \(6.125-5.75=0.375\). In a digital system subtraction is usually performed instead by adding the 2’s complement of the subtrahend and discarding the final carry: for instance, in four bits \(1001-0101=1001+1011=1\,0100\), and discarding the carry leaves \(0100\).
(c) Binary multiplication and division
Binary multiplication is carried out exactly as decimal long multiplication, with the simplification that each partial product is either the multiplicand itself (for a multiplier bit 1) or zero (for a multiplier bit 0). For \(1010\times1001\),
which is \(10\times9=90\) in decimal. Binary division is likewise long division, in which at each step the divisor either goes once into the partial dividend or does not go at all. Dividing \(10011011\) by \(100\),
Only the ten combinations \(0000\) to \(1001\) are used; the six combinations \(1010\) to \(1111\) are invalid in BCD. BCD is therefore less economical than binary, but it is easily converted to and from decimal and is used in counters and displays. When two BCD digits are added and the sum exceeds 9, or a carry is produced, the result must be corrected by adding \(0110\) (six) to skip the six invalid codes. For example, \(7+5\) gives \(0111+0101=1100\), which is invalid, and adding \(0110\) gives \(1\,0010\), that is \(0001\,0010=12\) in BCD.
(b) The excess-3 code
The excess-3 code of a decimal digit is the 4-bit binary code of the digit plus 3. Thus 0 is coded as \(0011\), 5 as \(1000\) and 9 as \(1100\), and the number 59 is coded digit by digit as \(1000\;1100\). The code is unweighted, but it is self-complementing: the 1’s complement of the code of a digit \(d\) is the code of \(9-d\) (for example, \(2\to0101\) and its complement \(1010\) is the code of 7), which simplifies decimal subtraction.
(c) The Gray code
In the Gray code successive numbers differ in only one bit. This avoids the momentary false codes that arise when several bits of an ordinary binary count change at once (for instance from \(0111\) to \(1000\)), and makes the code useful in shaft encoders. The same property fixes the order of rows and columns of the Karnaugh map in Section 6.10. A binary number \(b_3b_2b_1b_0\) is converted to Gray code \(g_3g_2g_1g_0\) by keeping the MSB and then adding each pair of adjacent bits without carry (the exclusive-OR operation \(\oplus\) of Section 6.6, which gives 1 when the two bits differ):
Conversely, a Gray code is converted back to binary by keeping the MSB and adding each Gray bit to the binary bit just found: \(b_3=g_3\), \(b_2=b_3\oplus g_2\), \(b_1=b_2\oplus g_1\), \(b_0=b_1\oplus g_0\). For example, binary \(1011\) gives the Gray code \(1,\,1\oplus0,\,0\oplus1,\,1\oplus1=1110\), and Gray \(1110\) gives back \(1,\,1\oplus1=0,\,0\oplus1=1,\,1\oplus0=1\), that is \(1011\). The three codes are compared in the following table.
Decimal
Binary
BCD (8421)
Excess-3
Gray
0
0000
0000
0011
0000
1
0001
0001
0100
0001
2
0010
0010
0101
0011
3
0011
0011
0110
0010
4
0100
0100
0111
0110
5
0101
0101
1000
0111
6
0110
0110
1001
0101
7
0111
0111
1010
0100
8
1000
1000
1011
1100
9
1001
1001
1100
1101
10
1010
0001 0000
0100 0011
1111
11
1011
0001 0001
0100 0100
1110
12
1100
0001 0010
0100 0101
1010
13
1101
0001 0011
0100 0110
1011
14
1110
0001 0100
0100 0111
1001
15
1111
0001 0101
0100 1000
1000
6.5 Boolean algebra
Boolean algebra, also called the algebra of switching circuits, is the algebra of variables that can take only the two values 0 and 1. It provides the language in which the function of a logic circuit is described, and the rules by which that function can be identified and minimised. Its three basic operations are OR, written as a sum \(A+B\); AND, written as a product \(A\cdot B\) or simply \(AB\); and NOT, or complementation, written \(\overline{A}\).
(a) Rules of Boolean algebra
The following rules follow directly from the definitions of the three operations, and can each be checked by substituting \(A=0\) and \(A=1\).
OR operation
AND operation
NOT operation
\(A+A=A\)
\(A\cdot1=A\)
\(\overline{1}=0\)
\(A+0=A\)
\(A\cdot0=0\)
\(\overline{0}=1\)
\(1+A=1\)
\(A\cdot A=A\)
\(\overline{\overline{A}}=A\)
\(A+\overline{A}=1\)
\(A\cdot\overline{A}=0\)
(b) Basic laws
The basic laws and theorems of Boolean algebra are collected in the following table.
The second distributive law, which has no analogue in ordinary algebra, follows from the first: \((A+B)(A+C)=A+AC+AB+BC=A(1+C+B)+BC=A+BC\). The redundant literal law follows from it at once, since \(A+\overline{A}B=(A+\overline{A})(A+B)=A+B\). The consensus theorem is proved by multiplying the redundant term by \(1=A+\overline{A}\):
De Morgan’s laws state that the complement of a sum is the product of the complements, and the complement of a product is the sum of the complements. They extend to any number of variables, \(\overline{A+B+C+\cdots}=\overline{A}\,\overline{B}\,\overline{C}\cdots\) and \(\overline{ABC\cdots}=\overline{A}+\overline{B}+\overline{C}+\cdots\), and they are the basis of the equivalence between gates described in Section 6.6.
Solution. By the second distributive law, \(x+yz=(x+y)(x+z)\), so (b) is correct. By absorption, \(x+xy+yz=x(1+y)+yz=x+yz\), so (c) is also correct. On the other hand, \(x+xz+xy=x(1+z+y)=x\), which differs from \(x+yz\) when \(x=0\), \(y=z=1\), and \(x+z\) differs from \(x+yz\) when \(x=y=0\), \(z=1\). Options (b) and (c) are correct.
Example 6.10. Simplify \(A+B+C+D+\overline{ABCD}\).
(a) 0 (b) 1 (c) \(A+B\) (d) \(A+C\)
Solution. By De Morgan’s law \(\overline{ABCD}=\overline{A}+\overline{B}+\overline{C}+\overline{D}\), so that
Example 6.12. Determine which of the following expressions are equivalent to \(A\oplus B\) and which to \(A\odot B\), where \(A\oplus B=\overline{A}B+A\overline{B}\) and \(A\odot B=AB+\overline{A}\,\overline{B}\) (Section 6.6).
Thus (b), (c) and (f) are equivalent to \(A\oplus B\), and (a), (d) and (e) to \(A\odot B\). Complementing one input of an XOR or XNOR interchanges the two functions, while complementing both inputs leaves the function unchanged.
Example 6.13. If \(A\oplus B=C\), find (i) \(B\oplus C\) and (ii) \(A\oplus B\oplus C\).
Solution. (i) Using \(\overline{A\oplus B}=A\odot B=AB+\overline{A}\,\overline{B}\),
(ii) Writing \(Z=A\oplus B\), we have \(A\oplus B\oplus C=Z\oplus Z=\overline{Z}Z+Z\overline{Z}=0\).
6.6 Logic gates
Logic gates are the basic elements of a digital or switching circuit. They can be classified as fundamental and derived gates. There are three fundamental logical operations, AND, OR and NOT, from which all other functions, however complex, can be built. The other gates, NOR, NAND, exclusive-OR (XOR) and exclusive-NOR (XNOR), are derived gates. Each gate has a standard symbol and a clearly defined behaviour, which we describe by its truth table, a list of the output for every possible combination of inputs; by its pulsed operation, the output waveform produced by given input waveforms; and by an electrical equivalent built from switches and a lamp. The NOR and NAND gates are also known as universal gates, because any logic function can be built from either alone, while the XOR and XNOR gates can be regarded as special gates.
(a) The OR gate
The OR gate performs logical addition, the OR function. It has two or more inputs and a single output. If the inputs are the Boolean variables \(A\) and \(B\), the output is
\[Y=A+B.\]
The symbols of two-input and three-input OR gates are shown in Figure 6.4.
Figure 6.4 Logic symbols of the two-input OR gate, \(Y=A+B\), and the three-input OR gate, \(Y=A+B+C\).
The output of an OR gate is HIGH when any or all of the inputs are HIGH, and LOW only when no input is HIGH, as the truth table for two inputs shows.
\(A\)
\(B\)
\(Y=A+B\)
0
0
0
0
1
1
1
0
1
1
1
1
The pulsed operation is shown in Figure 6.5: the output goes HIGH as soon as either input goes HIGH and stays HIGH while at least one input remains HIGH.
Figure 6.5 Pulsed operation of the OR gate.
The electrical equivalent of the OR gate, Figure 6.6, consists of two switches \(S_A\) and \(S_B\) in parallel, in series with a battery \(V\) and a lamp \(Y\). A closed switch represents the input 1 and a glowing lamp the output 1. The lamp is lit when either switch, or both, is closed.
Figure 6.6 Electrical equivalent of the OR gate: two switches in parallel.
\(S_A\)
\(S_B\)
Lamp \(Y\)
Open
Open
OFF
Open
Closed
ON
Closed
Open
ON
Closed
Closed
ON
(b) The AND gate
The AND gate performs logical multiplication, the AND function. It is composed of two or more inputs and a single output, as indicated by the standard symbols of Figure 6.7, in which the inputs are on the left and the output on the right. For inputs \(A\) and \(B\) the output is \(Y=A\cdot B\).
Figure 6.7 Logic symbols of the two-input AND gate, \(Y=A\cdot B\), and the three-input AND gate, \(Y=A\cdot B\cdot C\).
The output of the AND gate is HIGH only when all of the inputs are HIGH; when any of the inputs is LOW, the output is LOW.
\(A\)
\(B\)
\(Y=A\cdot B\)
0
0
0
0
1
0
1
0
0
1
1
1
In the pulsed operation of Figure 6.8 the output is HIGH only during the intervals in which both inputs are HIGH.
Figure 6.8 Pulsed operation of the AND gate.
The electrical equivalent, Figure 6.9, consists of two switches in series with the battery and the lamp, which is lit only when both switches are closed.
Figure 6.9 Electrical equivalent of the AND gate: two switches in series.
\(S_A\)
\(S_B\)
Lamp \(Y\)
Open
Open
OFF
Open
Closed
OFF
Closed
Open
OFF
Closed
Closed
ON
(c) The NOT gate
The inverter, or NOT gate, performs the basic logic function called inversion or complementation. Its purpose is to change one logic level to the opposite level; in terms of bits, it changes a 1 to 0 and a 0 to 1. Its symbol is shown in Figure 6.10 and its output is \(Y=\overline{A}\).
Figure 6.10 Logic symbol of the NOT gate (inverter), \(Y=\overline{A}\).
When a HIGH level is applied to the input of an inverter, a LOW level appears at its output, and when a LOW level is applied, a HIGH level appears. This operation is summarised in the truth table.
\(A\)
\(Y=\overline{A}\)
0
1
1
0
The output waveform of Figure 6.11 is therefore the input waveform turned upside down.
Figure 6.11 Pulsed operation of the NOT gate.
In the electrical equivalent, Figure 6.12, the switch \(S_A\) is connected across the lamp. When the switch is open the current flows through the lamp, which glows; when it is closed the lamp is short-circuited and goes out. (A small resistance in the supply lead, not shown, limits the current when the switch is closed.)
Figure 6.12 Electrical equivalent of the NOT gate: a switch across the lamp.
\(S_A\)
Lamp \(Y\)
Open
ON
Closed
OFF
(d) The NOR gate
The term NOR is a contraction of NOT-OR and implies an OR function with an inverted output, \(Y=\overline{A+B}\). The standard symbol of a two-input NOR gate, and its equivalent, an OR gate followed by an inverter, are shown in Figure 6.13. The bubble at the output of the symbol denotes inversion.
Figure 6.13 The two-input NOR gate, \(Y=\overline{A+B}\), and its equivalent, an OR gate followed by an inverter.
The output of the NOR gate is HIGH only when all the inputs are LOW; if any one input is HIGH the output is LOW.
\(A\)
\(B\)
\(Y=\overline{A+B}\)
0
0
1
0
1
0
1
0
0
1
1
0
Figure 6.14 Pulsed operation of the NOR gate.
The pulsed operation is shown in Figure 6.14. In the electrical equivalent, Figure 6.15, two switches in parallel are connected across the lamp, so that closing either switch short-circuits the lamp.
Figure 6.15 Electrical equivalent of the NOR gate: two parallel switches across the lamp.
\(S_A\)
\(S_B\)
Lamp \(Y\)
Open
Open
ON
Open
Closed
OFF
Closed
Open
OFF
Closed
Closed
OFF
(e) The NAND gate
The term NAND is a contraction of NOT-AND and implies an AND function with a complemented (inverted) output, \(Y=\overline{A\cdot B}\). The standard symbol of a two-input NAND gate, and its equivalence to an AND gate followed by an inverter, are shown in Figure 6.16.
Figure 6.16 The two-input NAND gate, \(Y=\overline{A\cdot B}\), and its equivalent, an AND gate followed by an inverter.
The output of the NAND gate is LOW only when all the inputs are HIGH.
\(A\)
\(B\)
\(Y=\overline{A\cdot B}\)
0
0
1
0
1
1
1
0
1
1
1
0
Figure 6.17 Pulsed operation of the NAND gate.
The pulsed operation is shown in Figure 6.17. In the electrical equivalent, Figure 6.18, two switches in series are connected across the lamp, so that the lamp is short-circuited only when both switches are closed.
Figure 6.18 Electrical equivalent of the NAND gate: two series switches across the lamp.
\(S_A\)
\(S_B\)
Lamp \(Y\)
Open
Open
ON
Open
Closed
ON
Closed
Open
ON
Closed
Closed
OFF
(f) The bubbled AND and bubbled OR gates
A gate whose inputs are inverted is drawn with bubbles at its inputs. By De Morgan’s laws, a bubbled AND gate is equivalent to a NOR gate and a bubbled OR gate is equivalent to a NAND gate:
Figure 6.21 Logic symbol of the exclusive-OR gate, \(Y=A\oplus B=\overline{A}B+A\overline{B}\).
The output of a two-input XOR gate is HIGH when the two inputs are unequal and LOW when they are equal; this is why the gate is called an inequality comparator.
\(A\)
\(B\)
\(Y=A\oplus B\)
0
0
0
0
1
1
1
0
1
1
1
0
Figure 6.22 Pulsed operation of the exclusive-OR gate.
The pulsed operation is shown in Figure 6.22. A three-input XOR function is obtained by cascading two two-input gates, as in Figure 6.23, and its truth table is built by first forming \(A\oplus B\).
\(A\)
\(B\)
\(A\oplus B\)
\(C\)
\(Y=A\oplus B\oplus C\)
0
0
0
0
0
0
0
0
1
1
0
1
1
0
1
0
1
1
1
0
1
0
1
0
1
1
0
1
1
0
1
1
0
0
0
1
1
0
1
1
Figure 6.23 A three-input exclusive-OR function built from two two-input XOR gates.
The output \(A\oplus B\oplus C\) is 1 when an odd number of the inputs are 1. The XOR function is both commutative and associative, so that a chain of XOR gates computes the parity of its inputs, whatever the order in which they are combined.
(h) The exclusive-NOR gate (equality comparator)
The exclusive-NOR (XNOR) gate is an XOR gate with an inverted output. Its output is HIGH when the two inputs are equal, so that it acts as an equality comparator.
\(A\)
\(B\)
\(Y=A\odot B\)
0
0
1
0
1
0
1
0
0
1
1
1
Figure 6.24 Pulsed operation of the exclusive-NOR gate.
The pulsed operation is shown in Figure 6.24, and the symbol in Figure 6.25. The output is
Figure 6.25 Logic symbol of the exclusive-NOR gate, \(Y=A\odot B=\overline{A\oplus B}=\overline{A}\,\overline{B}+AB\).
For two inputs the XNOR is simply the complement of the XOR. For three inputs, however, this is not so. Cascading two XNOR gates as in Figure 6.26 gives the truth table below, built by first forming \(A\odot B\).
Figure 6.26 A three-input exclusive-NOR function built from two two-input XNOR gates.
\(A\)
\(B\)
\(A\odot B\)
\(C\)
\(Y=A\odot B\odot C\)
0
0
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
1
1
1
1
1
The output column is identical to that of \(A\oplus B\oplus C\). Hence
In general, an XNOR chain of \(n\) variables equals the XOR chain when \(n\) is odd and its complement when \(n\) is even, because each XNOR stage contributes one inversion.
Exam tip.\(A\odot B\odot C=A\oplus B\oplus C\): a three-input (or any odd-input) XNOR chain is not the complement of the XOR chain.
6.7 Universal gates
A gate is called universal if any logic function can be realised with gates of that type alone. Since every function can be written in terms of AND, OR and NOT, it is enough to show that these three can be built from the gate; in practice it is also useful to have the NOR, NAND, XOR and XNOR functions in the same form.
(a) The NAND gate as a universal gate
NOT gate. If the two inputs of a NAND gate are joined, the output is \(\overline{A\cdot A}=\overline{A}\), as in Figure 6.27.
Figure 6.27 NOT gate using a NAND gate.
AND gate. A NAND gate followed by a NAND inverter restores the AND function, \(\overline{\overline{AB}}=AB\), as in Figure 6.28; two gates are needed.
Figure 6.28 AND gate using two NAND gates.
OR gate. If \(A\) and \(B\) are first inverted by NAND inverters and then applied to a NAND gate, De Morgan’s law gives \(\overline{\overline{A}\cdot\overline{B}}=A+B\), as in Figure 6.29; three gates are needed.
Figure 6.29 OR gate using three NAND gates.
NOR gate. Inverting the output of the OR circuit with a fourth NAND gate gives \(\overline{A+B}\), Figure 6.30.
Figure 6.30 NOR gate using four NAND gates.
XOR gate. The XOR function needs four NAND gates, connected as in Figure 6.31. The first gate gives \(\overline{AB}=\overline{A}+\overline{B}\). The upper gate then gives
and the lower gate, similarly, \(\overline{B\cdot\overline{AB}}=\overline{(\overline{A}+\overline{B})B}=\overline{\overline{A}B}=A+\overline{B}\). The output gate gives
XNOR gate. A fifth NAND gate, used as an inverter on the output of the XOR circuit, gives \(Y=\overline{A\oplus B}=A\odot B\), Figure 6.32.
Figure 6.32 XNOR gate using five NAND gates.
(b) The NOR gate as a universal gate
NOT gate. Joining the inputs of a NOR gate gives \(\overline{A+A}=\overline{A}\), Figure 6.33.
Figure 6.33 NOT gate using a NOR gate.
OR gate. A NOR gate followed by a NOR inverter gives \(\overline{\overline{A+B}}=A+B\), Figure 6.34; two gates are needed.
Figure 6.34 OR gate using two NOR gates.
AND gate. If \(A\) and \(B\) are first inverted by NOR inverters and then applied to a NOR gate, the output is \(\overline{\overline{A}+\overline{B}}=\overline{\overline{A}}\cdot\overline{\overline{B}}=A\cdot B\), Figure 6.35; three gates are needed.
Figure 6.35 AND gate using three NOR gates.
NAND gate. Inverting the output of the AND circuit with a fourth NOR gate gives \(\overline{A\cdot B}\), Figure 6.36.
Figure 6.36 NAND gate using four NOR gates.
XNOR gate. The arrangement of Figure 6.37, the dual of the NAND circuit for XOR, gives the XNOR function with four NOR gates. The first gate gives \(\overline{A+B}=\overline{A}\,\overline{B}\). The upper gate gives
XOR gate. A fifth NOR gate, used as an inverter on the output of the XNOR circuit, gives \(Y=\overline{A\odot B}=A\oplus B\), Figure 6.38.
Figure 6.38 XOR gate using five NOR gates.
The numbers of gates required are worth remembering. With NAND gates, NOT needs 1, AND 2, OR 3, NOR 4, XOR 4 and XNOR 5; with NOR gates, NOT needs 1, OR 2, AND 3, NAND 4, XNOR 4 and XOR 5.
6.8 Analysis of logic circuits
To find the function of a circuit of gates we write the output of each gate in terms of its inputs, working from the inputs towards the output, and then simplify the final expression with the rules of Section 6.5.
Example 6.14. Find the combination of inputs \(A,B,C\) that gives the output \(Y=1\) in the circuit of Figure 6.39.
Figure 6.39 An XOR gate, an XNOR gate and a three-input AND gate.
(a) 0, 0, 1 (b) 1, 0, 1 (c) 1, 1, 1 (d) 0, 1, 1
Solution. The XOR gate gives \(A\oplus B=\overline{A}B+A\overline{B}\), the XNOR gate gives \(B\odot C=\overline{B}\,\overline{C}+BC\), and \(C\) is applied directly to the third input of the AND gate. Hence
