Unit 1 PDF

UNIT – I
Number System and Boolean algebra And Switching
Functions:
Review of number systems,
Complements of Numbers,
Codes- Binary Codes,
Binary Coded Decimal Code and its Properties,
Unit Distance Codes,
Error Detecting and Correcting Codes.
Boolean Algebra:
Basic Theorems and Properties,
Switching Functions,
Canonical and Standard Form,
Algebraic Simplification of Digital Logic Gates,
Properties of XOR Gates,
Universal Gates,
Multilevel NAND/NOR realizations.
1
CHAPTER
NUMBER SYSTEMS AND CODES
1.0 INTRODUCTION
Inside today’s computers, data is represented as 1’s and 0’s. These 1’s and 0’s might be
stored magnetically on a disk, or as a state in a transistor, co re, or vacuum tube. To perform
useful operations on these 1’s and 0’s one have to organize them together into patterns that
make up codes. Modern digital systems do not represent numeric values using the decimal
system. Instead, they typically use a binary or two’s complement numbering system. To
understand the digital system arithmetic, one must understand how digital systems represent
numbers.
This chapter discusses several important concepts including the binary, octal and hexadeci-
mal numbering systems, binary data organization (bits, nibbles, bytes, words, and double
words), signed and unsigned numbering systems. If one is already familiar with these terms
he should at least skim this material.
1.1 A REVIEW OF THE DECIMAL SYSTEM

People have been using the decimal (base 10) numbering system for so long that they
probably take it for granted. When one see a number like “123”, he don’t think about the
value 123; rather, he generate a mental image of how many items this value represents. In
reality, however, the number 123 represents:
1*102 + 2*101 + 3*100
or 100 + 20 + 3
Each digit appearing to the left of the decimal point represents a value between zero and
nine times an increasing power of ten. Digits appearing to the right of the decimal point
represent a value between zero and nine times an increasing negative power of ten. For
example, the value 123.456 means:
1*102 + 2*101 + 3*100 + 4*10–1 + 5*10–2 + 6*10–3
or 100 + 20 + 3 + 0.4 + 0.05 + 0.006
1.2 BINARY NUMBERING SYSTEM

Most modern digital systems operate using binary logic. The digital systems represents
values using two voltage levels (usually 0 v and +5 v). With two such levels one can represent
1
2 FOUNDATION OF SWITCHING THEORY AND LOGIC DESIGN
exactly two different values. These could be any two different values, but by convention we
use the values zero and one. These two values, coincidentally, correspond to the two digits
used by the binary numbering system.
1.2.1 Binary to Decimal Conversion

The binary numbering system works just like the decimal numbering system, with two
exceptions: binary only allows the digits 0 and 1 (rather than 0–9), and binary uses powers
of two rather than powers of ten. Therefore, it is very easy to convert a binary number to
decimal. For each “1” in the binary string, add 2n where “n” is the bit position in the binary
string (0 to n–1 for n bit binary string).
For example, the binary value 10102 represents the decimal 10 which can be obtained
through the procedure shown in the table 1:
Table 1
Binary No. 1 0 1 0
Bit Position (n) 3rd 2nd 1st 0th
Weight Factor (2n) 23 22 21 20
bit * 2n 1*23 0*22 1*21 0*20
Decimal Value 8 0 2 0
Decimal Number 8 + 0 + 2 + 0 = 10
All the steps in above procedure can be summarized in short as
1*23 + 0*22 + 1*21 + 0*20 = 8 + 0 + 2 + 0 = 1010
i.e.,
1. Multiply each digit of the binary number by its positional weight and then add up
the result.
2. If any digit is 0, its positional weight is not to be taken into account.
1.2.2 Decimal to Binary Conversion

The inverse problem would be to find out the binary equivalent of given decimal
number for instance let us find out binary of 1910 (decimal 19)
Division Dividend Remainder

1
19 / 2 9
9/2 4 1
4/2 2 0
2/2 1 0
1/2 0 1
1 0 0 1 1
Dividend is 0, stop the procedure.

NUMBER SYSTEMS AND CODES 3
Our final number is (10011)2.

i.e.,
1. Divide the decimal number by 2 producing a dividend and a remainder. This number
is the LSB (least significant bit of the desired binary number).
2. Again divide the dividend obtained above by 2. This produces another dividend and
remainder. The remainder is the next digit of the binary number.
3. Continue this process of division until the dividend becomes 0. The remainder
obtained in the final division is the MSB (most significant bit of the binary number).
1.2.3 Binary Formats

In the purest sense, every binary number contains an infinite number of digits (or bits
which is short for binary digits). Because any number of leading zero bits may precede the
binary number without changing its value. For example, one can represent the number seven
by:
111 00000111 ..0000000000111 000000000000111
Often several values are packed together into the same binary number. For convenience,
a numeric value is assign to each bit position. Each bit is numbered as follows:
1. The rightmost bit in a binary number is bit position zero.
2. Each bit to the left is given the next successive bit number.
An eight-bit binary value uses bits zero through seven:
X7 X6 X5 X4 X3 X2 X1 X0
A 16-bit binary value uses bit positions zero through fifteen:
X15 X14 X13 X12 X11 X10 X9 X8 X7 X6 X5 X4 X3 X2 X1 X0
Bit zero is usually referred to as the low order bit. The left-most bit is typically called
the high order bit. The intermediate bits are referred by their respective bit numbers. The
low order bit which is X0 is called LEAST SIGNIFICANT BIT (LSB). The high order bit or
left most bit. i.e., X15 is called MOST SIGNIFICANT BIT (MSB).
1.2.4 Data Organization

In pure mathematics a value may take an arbitrary number of bits. Digital systems, on the
other hand, generally work with some specific number of bits. Common collections are single bits,
groups of four bits (called nibbles), groups of eight bits (called bytes), groups of 16 bits (called
words), and more. The sizes are not arbitrary. There is a good reason for these particular values.
Bits
The smallest “unit” of data on a binary computer or digital system is a single bit. Bit,
an abbreviation for Binary Digit, can hold either a 0 or a 1. A bit is the smallest unit of
information a computer can understand. Since a single bit is capable of representing only two
different values (typically zero or one) one may get the impression that there are a very small
number of items one can represent with a single bit. That’s not true! There are an infinite
number of items one can represent with a single bit.
With a single bit, one can represent any two distinct items. Examples include zero or
one, true or false, on or off, male or female, and right or wrong. However, one are not limited
to representing binary data types (that is, those objects which have only two distinct
values). One could use a single bit to represent the numbers 321 and 1234. Or perhaps 6251
and 2. One could also use a single bit to represent the colours green and blue. One could
even represent two unrelated objects with a single bit. For example, one could represent
the colour red and the number 3256 with a single bit. One can represent any two different
values with a single bit. However, one can represent only two different values with a
single bit.
To confuse things even more, different bits can represent different things. For example,
one bit might be used to represent the values zero and one, while an adjacent bit might be
used to represent the values true and false. How can one tell by looking at the bits? The
answer, of course, is that one can’t. But this illustrates the whole idea behind computer data
structures: data is what one define it to be. If one uses a bit to represent a boolean (true/false)
value then that bit (by definition) represents true or false. For the bit to have any true
meaning, one must be consistent. That is, if one is using a bit to represent true or false at
one point in his program, he shouldn’t use the true/false value stored in that bit to represent
green or blue later.
Since most items one will be trying to model require more than two different values,
single bit values aren’t the most popular data type used. However, since everything else
consists of groups of bits, bits will play an important role in programs. Of course, there are
several data types that require two distinct values, so it would seem that bits are important
by themselves. However, individual bits are difficult to manipulate, so other data types are
often used to represent boolean values.
Nibbles
A nibble is a collection of four bits. It wouldn’t be a particularly interesting data structure
except for two items: BCD (binary coded decimal) numbers and hexadecimal numbers. It
takes four bits to represent a single BCD or hexadecimal digit. With a nibble, one can
represent up to 16 distinct values. In the case of hexadecimal numbers, the values 0, 1,
2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F are represented with four bits (see “The
Hexadecimal Numbering System”). BCD uses ten different digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
and requires four bits. In fact, any sixteen distinct values can be represented with a
nibble, but hexadecimal and BCD digits are the primary items we can represent with a
single nibble.
Bytes
Computer memory must be able to store letters, numbers, and symbols. A single bit by
itself cannot be of much use. Bits are combined to represent some meaningful data. A group
of eight bits is called a byte. It can represent a character and is the smallest addressable
datum (data item) on the most of the digital systems (e.g. 80 × 86 microprocessor). The most
important data type is the byte. Main memory and input/output addresses on the 80 × 86 are
all byte addresses. This means that the smallest item that can be individually accessed by an
80 × 86 program is an eight-bit value. To access anything smaller requires that you read the
byte containing the data and mask out the unwanted bits. The bits in a byte are normally
numbered from zero to seven using the convention in Fig. 1.1.
Bit 0 is the low order bit or least significant bit, bit 7 is the high order bit or most
significant bit of the byte. All other bits are referred by their number.
7 6 5 4 3 2 1 0
Fig. 1.1 Bit numbering in a byte
Note: That a byte also contains exactly two nibbles (see Fig. 1.2).
7 6 5 4 3 2 1 0
High Nibble Low Nibble

Fig. 1.2 The two nibbles in a byte
Bits 0–3 comprise the low order nibble, bits 4–7 form the high order nibble. Since a byte
contains exactly two nibbles, byte values require two hexadecimal digits.
Since a byte contains eight bits, it can represent 28, or 256, different values. Generally,
a byte is used to represent numeric values in the range 0.255, signed numbers in the range
–128.. + 127 (refer “Signed binary representation”). Many data types have fewer than 256
items so eight bits is usually sufficient.
For a byte addressable machine, it turns out to be more efficient to manipulate a whole
byte than an individual bit or nibble. For this reason, most programmers use a whole byte
to represent data types that require no more than 256 items, even if fewer than eight bits
would suffice. For example, we’ll often represent the boolean values true and false by 000000012
and 000000002 (respectively).
Probably the most important use for a byte is holding a character code. Characters typed
at the keyboard, displayed on the screen, and printed on the printer all have numeric values.
Words
A word is a group of 16 bits. Bits in a word are numbered starting from zero on up to
fifteen. The bit numbering appears in Fig. 1.3.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Fig. 1.3 Bit numbers in a word
Like the byte, bit 0 is the low order bit and bit 15 is the high order bit. When referencing
the other bits in a word use their bit position number.
Notice that a word contains exactly two bytes. Bits 0 through 7 form the low order byte,
bits 8 through 15 form the high order byte (see Fig. 1.4).
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
High Byte Low Byte

Fig. 1.4 The two bytes in a word
Naturally, a word may be further broken down into four nibbles as shown in Fig. 1.5.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Nibble 3 Nibble 2 Nibble 1 Nibble 0

Higher Nibble Lower Nibble
Fig. 1.5 Nibbles in a word
Nibble zero is the low order nibble in the word and nibble three is the high order nibble
of the word. The other two nibbles are “nibble one” and “nibble two”.
With 16 bits, 216 (65,536) different values can be represented. These could be the values
in the range 0 to 65,535 (or –32,768 to +32,767) or any other data type with no more than
65,536 values.
Words can represent integer values in the range 0 to 65,535 or –32,768 to 32,767.
Unsigned numeric values are represented by the binary value corresponding to the bits in the
word. Signed numeric values use the two’s complement form for numeric values (refer
“Signed binary representation”).
Double Words
A double word is exactly what its name implies, a pair of words. Therefore, a double word
quantity is 32 bits long as shown in Fig. 1.6.
31 23 15 7 0
Fig. 1.6 Bit numbers in a double word
This double word can be divided into a high order word and a low order word, or four
different bytes, or eight different nibbles (see Fig. 1.7).
31 23 15 7 0
High order word Low order word
31 23 15 7 0
Higher Byte Byte 2 Byte 1 Lower Byte
31 23 15 7 0
7 6 5 4 3 2 1 0
Higher Nibble Lower Nibble
Fig. 1.7 Nibbles, bytes, and words in a double word

1.3 OCTAL NUMBERING SYSTEM

The octal number system uses base 8 instead of base 10 or base 2. This is sometimes
convenient since many computer operations are based on bytes (8 bits). In octal, we have 8
digits at our disposal, 0–7.
Decimal Octal
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 10
9 11
10 12
11 13
12 14
13 15
14 16
15 17
16 20
1.3.1 Octal to Decimal, Decimal to Octal Conversion

Converting octal to decimal is just like converting binary to decimal, except instead of
powers of 2, we use powers of 8. That is, the LSB is 80, the next is 81, then 82, etc.
To convert 172 in octal to decimal:
1 7 2
82 81 80
Weight = 1*82 + 7*81 + 2*80
= 1*64 + 7*8 + 2*1
= 12210
Converting decimal to octal is just like converting decimal to binary, except instead of
dividing by 2, we divide by 8. To convert 122 to octal:
122/8 = 15 remainder 2
1/8 = 0 remainder 1
= 1728
If using a calculator to perform the divisions, the result will include a decimal fraction
instead of a remainder. The remainder can be obtained by multiplying the decimal fraction
by 8. For example, 122/8 = 15.25. Then multiply 0.25 * 8 to get a remainder of 2.
1.3.2 Octal to Binary, Binary to Octal Conversion

Octal becomes very useful in converting to binary, because it is quite simple. The
conversion can be done by looking at 3 bit combinations, and then concatenating them
together. Here is the equivalent for each individual octal digit and binary representation:
Octal Binary
1 001
2 010
3 011
4 100
5 101
6 110
7 111
To convert back and forth between octal and binary, simply substitute the proper pattern
for each octal digit with the corresponding three binary digits.
For example, 372 in octal becomes 010 111 010 or 010111010 in binary.
777 in octal becomes 111 111 111 or 111111111 in binary.
The same applies in the other direction:
100111010 in binary becomes 100 111 010 or 472 in octal.
Since it is so easy to convert back and forth between octal and binary, octal is sometimes
used to represent binary codes. Octal is most useful if the binary code happens to be a
multiple of 3 bits long. Sometimes it is quicker to convert decimal to binary by first convert-
ing decimal to octal, and then octal to binary.
1.4 HEXADECIMAL NUMBERING SYSTEM

The hexadecimal numbering system is the most common system seen today in repre-
senting raw computer data. This is because it is very convenient to represent groups of 4 bits.
Consequently, one byte (8 bits) can be represented by two groups of four bits easily in
hexadecimal.
Hexadecimal uses a base 16 numbering system. This means that we have 16 symbols to
use for digits. Consequently, we must invent new digits beyond 9. The digits used in hex are
the letters A, B, C, D, E, and F. If we start counting, we get the table below:
Decimal Hexadecimal Binary
0 0 0000
1 1 0001
2 2 0010
3 3 0011
4 4 0100
.....Contd
Decimal Hexadecimal Binary

5 5 0101
6 6 0110
7 7 0111
8 8 1000
9 9 1001
10 A 1010
11 B 1011
12 C 1100
13 D 1101
14 E 1110
15 F 1111
16 10 10000
17 11 10001
18 …
1.4.1 Hex to Decimal and Decimal to Hex Conversion

Converting hex to decimal is just like converting binary to decimal, except instead of
powers of 2, we use powers of 16. That is, the LSB is 160, the next is 161, then 162, etc.
To convert 15E in hex to decimal:
1 5 E
16 2 16 1 160
Weight = 1*162 + 5*161 + 14*160
= 1*256 + 5*16 + 14*1
= 35010
Converting decimal to hex is just like converting decimal to binary, except instead of
dividing by 2, we divide by 16. To convert 350 to hex:
350/16 = 21 remainder 14 = E
So we get 15E for 350.
Again, note that if a calculator is being used, you may multiple the fraction remainder by
16 to produce the remainder. 350/16 = 21.875. Then to get the remainder, 0.875 * 16 = 14.
1.4.2 Hex to Binary and Binary to Hex Conversion

Going from hex to binary is similar to the process of converting from octal to binary. One
must simply look up or compute the binary pattern of 4 bits for each hex code, and concatenate
the codes together.
To convert AE to binary:
A = 1010
E = 1110
So AE in binary is 1010 1110

The same process applies in reverse by grouping together 4 bits at a time and then look
up the hex digit for each group.
Binary 11000100101 broken up into groups of 4:
0110 0010 0101 (note the 0 added as padding on the MSB to get up to 4 bits)
6 2 5
= 62516
1.4.3 Hex to Octal and Octal to Hex Conversion

These conversions are done through the binary conversion. Recall that, a group of 4-bits
represent a hexadecimal digit and a group of 3-bits represent an octal digit.
Hex to Octal Conversion

1. Convert the given hexadecimal number into binary.
2. Starting from right make groups of 3-bits and designate each group an octal digit.
Example. Convert (1A3)16 into octal.
Solution.
1. Converting hex to binary
(1 A 3)16 = 0001 1010 0011

1 A 3
2. Grouping of 3-bits
(1A3)16 = 000 110 100 011
0 6 4 3
so (1A3)16 = (0643)8 ≡ (643)8
Octal to Hex Conversion

1. Convert the given octal number into binary.
2. Starting from right make groups of 4-bits and designate each group as a Hexadeci-
mal digit.
Example. Convert (76)8 into hexadecimal.
Solution. 1. Converting octal to binary
(76)8 = 111 110

7 6
2. Grouping of 4-bits
(76)8 = 11 1110 0011 1110
3 E 3 E
∴ (76)8 = (3E)16
1.5 RANGE OF NUMBER REPRESENTATION

The range of numbers that can be represented is determined by the number of digits (or
bits in binary) used to represent a number. Let us consider decimal number system to
understand the idea.
Highest decimal number represented by 2 digits = 99
But 99 = 100 – 1 = 102 – 1. The power of 10 (in 102 – 1)
indicates that it is 2 digit representation.
So, highest 2-digit decimal number = 102 – 1
and lowest 2-digit decimal number = 00
Thus, range of 2-digit decimal number = 00 to 102 – 1
It is evident that a total of 100 or 102 numbers (00 to 99) can be represented by 2-digits.
So, we conclude that for n-digit representation
range of decimal numbers = 0 to 10n – 1
highest decimal number = 10n – 1
total numbers that can be represented = 10n
Note that highest n-digit decimal number can be represented by n 9s (i.e., 10 – 1) e.g.,
highest 2 digit decimal number is represented by 2 9s which is 99.
The above discussion can be generalized by taking base-r number system instead of base-
10 (or decimal) number system. Thus, with n-digit representation–
Total distinct numbers that can be represented = rn
Highest decimal Number = rn – 1
Range of Numbers = 0 to rn – 1
where, r = base or radix of Number system

n = Number of digits used for representation
It is worth noting that highest decimal number can be represented by n (r – 1)s in base-
r system.
Let us consider the base-2 or binary number system. Thus 2n distinct quantities, in the
range 0 to 2n – 1, can be represented with n-bit. If n = 4-bits, total distinct quantities (i.e.,
numbers) that can be represented
= N = 24 = 16
the range of numbers = 0 to 24 – 1 = 0 to 15
and Highest decimal number = 24 – 1 = 15
The highest decimal number 15, is represented by our 1s i.e., 1111. The range 0 to 15
corresponds to 0000 to 1111 in binary.
If we want to represent a decimal number M using n-bits, then the number M should
lie in the range 0 to 2n–1 i.e.,
0 < M < 2n – 1
or 2n – 1 > M
or 2n > M + 1
or n > log2 (M + 1)
where M and n are integers.
In the similar way, if we want to represent N distinct quantities in binary then N should
not exceed 2n.
2n > N
or n > log2N Both n and N are integers
Example 1. How many bits are required to represent
(i) 16-distinct levels
(ii) 10 distinct levels
(iii) 32 distinct levels
Solution. (i) We have, 2n > N
or 2n > 16 ⇒ 2n > 24
or n > 4⇒ n = 4
Thus, atleast 4-bits are required to represent 16 distinct levels, ranging from 0 to 15.
(ii) We have, n > log2 N
or n > log210 ⇒ n > 3.32
but n should be integer, so take next higher integer value
i.e., n = 4 bits
So, minimum 4-bits are required to represent 10 distinct levels, ranging from 0 to 9.
(iii) n > log2 N
or n > log232 ⇒ n > log2 25
or n > 5 ⇒ n = 5
So, minimum 5-bits are required to represent 32 levels, ranging from 0 to 31.
Example 2. Calculate the minimum no. of bits required to represent decimal numbers
(i) 16 (ii) 63
Solution. (i) We have, n > log2(M + 1) where M = given number
so n > log2(16 + 1) ⇒ n > log2(17)
or n > 4.09
taking next higher integer i.e., n = 5 bits.
Thus, atleast 5-bits are required to represent decimal number 16.
(ii) n > log2 (M + 1)
n > log2 (63 + 1) ⇒ n > log264
or n > log226 or n > 6 bits
So, minimum 6-bits are needed to represent decimal 63.
Example 3. In a base-5 number system, 3 digit representation is used. Find out
(i) Number of distinct quantities that can be represented.
(ii) Representation of highest decimal number in base-5.
Solution. Given radix of number system r = 5

digits of representation n = 3
digits in base-5 would be 0, 1, 2, 3, 4
(i) we have relation
no of distinct quantities = rn
= 53 = 125
So, 125 distinct levels (quantities) can be represented.
(ii) Highest decimal Number can be represented by n(r – 1)s i.e., by three 4s.
So, highest decimal Number = 444.
1.6 BINARY ARITHMETIC

The binary arithmetic operations such as addition, subtraction, multiplication and divi-
sion are similar to the decimal number system. Binary arithmetics are simpler than decimal
because they involve only two digits (bits) 1 and 0.
Binary Addition
Rules for binary addition are summarized in the table shown in Fig. 1.8.
Augend Addend Sum Carry Result
0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 0 1 10
Fig. 1.8 Rules for binary addition
As shown in 4th row adding 1 to 1 gives 9 carry which, is given to next binary position,
similar to decimal system. This is explained in examples below:
Example 1. (i) Add 1010 and 0011 (ii) Add 0101 and 1111
Solution.
Binary Subtraction
The rules for binary subtraction is summarized in the table shown in Fig. 1.9.
Minuend Subtrahend Difference Borrow
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
Fig. 1.9 Rules for binary subtraction
The process of subtraction is very similar to decimal system in which if a borrow is

needed it is taken from next higher binary position, as shown in row 2.
Example 2. Subtract 0100 from 1011
Solution. 1 ← Borrow
1 0 1 1 ← Minuend
−0 1 0 0 ← Subtrahend
0 1 1 1 ← Difference
↑ ↑ ↑ ↑
C3 C2 C1 C0
There is no problem in column C0 and C1. In column C2 we made 0 –1, so result = 1 and
borrow = 1. Then this borrow = 1 is marked in column C3. So result in column C2 is 1. Then
in column C3 we first made 1 – 0 to get result = 1 and then we subtracted borrow from result,
thus we get 0 in column C3.
“Thus in subtraction, first subtract the subtrahend bit from minuend and then subtract
borrow from the result.”
Watch out the next example to further clarify the concept.
Example 3. Subtract 0110 from 1001
Solution. 1 1 ← Borrow
1 0 0 1 ← Minuend
−0 1 1 0 ← Subtrahend
0 0 1 1 ← Difference
↑ ↑ ↑ ↑
C3 C2 C1 C0
Here, in column C1 we get difference = 1 and borrow = 1. This borrow is marked in
column C2, and difference = 1 is shown in the column C1. We now come to column C2. Here
by 0–1 we get difference = 1 and borrow = 1. Now this borrow is marked in column C3. But
in column C2 already we have 9 borrow so this borrow = 1 is subtracted from difference
= 1 which results in 0. Thus the difference = 0 is marked in column C2.
In the similar way we process column C3 and we get difference = 0 in column C3.
Binary Multiplication
Binary multiplication is also similar to decimal multiplication. In binary multiplication if
multiplier bit is 0 then partial product is all 0 and if multiplier bit is 1 then partial product
is 1. The same is illustrated in example below:
Example 4.
Binary Division
Binary division is also similar to decimal division as illustrated in example below:
Example 5.
1 0 1
Divisor 1 0 0 1 1 0 1 1 0 1 Dividend
1 0 0 1
× × 1 0 0 1
1 0 0 1
× × × ×
1.7 NEGATIVE NUMBERS AND THEIR ARITHMETIC

So far we have discussed straight forward number representation which are nothing but
positive number. The negative numbers have got two representation
(i) complement representation.
(ii) sign magnitude representation.
We will discuss both the representation in following subsections.
1.7.1 1’s and 2’s Complement

These are the complements used for binary numbers. Their representation are very
important as digital systems work on binary numbers only.
1’s Complement
1’s complement of a binary number is obtained simply by replacing each 1 by 0 and each 0
by 1. Alternately, 1’s complement of a binary can be obtained by subtracting each bit from 1.
Example 1. Find 1’s complement of (i) 011001 (ii) 00100111
Solution. (i) Replace each 1 by 0 and each 0 by 1
0 1 1 0 0 1
↓ ↓ ↓ ↓ ↓ ↓
1 0 0 1 1 0
So, 1’s complement of 011001 is 100110.
(ii) Subtract each binary bit from 1.
1 1 1 1 1 1 1 1
–0 0 1 0 0 1 1 1
1 1 0 1 1 0 0 0 ← 1’s complement
one can see that both the method gives same result.
2’s Complement
2’s complement of a binary number can be obtained by adding 1 to its 1’s complement.
Example 1. Find 2’s complement of (i) 011001 (ii) 0101100
Solution. (i) 0 1 1 0 0 1 ← Number

1 0 0 1 1 0 ← 1’s complement
+ 1 ← Add 1 to 1’s complement
1 0 0 1 1 1 ← 2’s complement
(ii) 0 1 0 1 1 0 0 ← Number
1 0 1 0 0 1 1 ← 1’s complement
+ 1 ← Add 1 to 1’s complement
1 0 1 0 1 0 0 ← 2’s complement
There is an efficient method to find 2’s complement based upon the observation made on the
above 2 examples. Consider the number and its 2’s complement of example (ii) as shown below:
0 1 0 1 1 0 0 Number
1 0 1 0 1 0 0 2s Complement
1s Same as
complement number
Fig. 1.10 Number and its 2’s complement
The above figure clearly shows that to find 2’s complement of a binary number start from
right towards left till the first 1 appears in the number. Take these bits (including first 1) as
it is and take 1’s complement of rest of the bits. Workout below examples to enhance your
understanding.
Example 2. Find 2’s complement of (i) 101100 (ii) 10010 (iii) 01001
Solution. (i) Number = 101100
First 1 from right
1 0 1 1 0 0 NUMBER
1s complement
0 1 0 1 0 0 2s complement
(ii) Number = 10010
First 1 from right
1 0 0 1 0 NUMBER
1s complement
0 1 1 1 0 2s complement
(iii) Number = 01001
First 1 from right
0 1 0 0 1 NUMBER
Take 1s As it is
complement
1 0 1 1 1 2s complement
It is interesting to note that taking complement twice leaves the number as it is. This
is illustrated in below Fig. 1.11.
1001 2s 0111 2s

complement complement 1001
Fig. 1.11 Effect of taking complement twice

To represent a negative number using complements the process involves two steps.
(1) obtain the binary representation of equivalent positive number for given negative
number. e.g., if given number is –2 then obtain binary representation of +2.
(2) Take the appropriate complement of representation obtained in step 1.
Example 3. Obtain 1’s and 2’s complement representation of –5 and –7.
Solution. (i) –5
1. binary of +5 = (0101)2
2. 1’s complement of (0101)2 = (1010)2 ← Represents (–5)10
2’s complement of (0101)2 = (1011)2 ← Represents (–5)10
(ii) –7
1. binary of +7 = (0111)2
2. 1’s complement of (0111)2 = (1000)2 Represents (–7)10
2’s complement of (0111)2 = (1001)2 Represents (–7)10
Note that in above two examples, for positive numbers we obtained such a binary
representation in which MSB is 0. e.g., for +7 we obtained (0111)2 not just (111)2. It is because
for all positive numbers MSB must be 0 and for negative numbers MSB should be 1. This will
be more clear in subsection 1.7.3.
1.7.2 Subtraction Using 1’s and 2’s Complement

Before using any complement method for subtraction equate the length of both minuend
and subtrahend by introducing leading zeros.
1’s complement subtraction following are the rules for subtraction using 1’s complement.
1. Take 1’s complement of subtrahend.
2. Add 1’s complement of subtrahend to minuend.
3. If a carry is produced by addition then add this carry to the LSB of result. This is
called as end around carry (EAC).
4. If carry is generated from MSB in step 2 then result is positive. If no carry
generated result is negative, and is in 1’s complement form.
Example 1. Perform following subtraction using 1’s complement.
(i) 7 – 3 (ii) 3 – 7
Solution. (i) 7 – 3: binary of 7 = (0111)2
both numbers have equal length.
binary of 3 = (0011)2
Step 1. 1’s complement of (0011)2 = (1100)2
Step 2. Perform addition of minuend and 1’s complement of subtrahend
0 1 1 1 (7)
+ 1 1 0 0 (3 or 1s complement of + 3)
Final
Carry 1 0 0 1 1
Step 3. EAC + 1 (EAC)
0 1 0 0
Step 4. Since carry is generated in step 2 the result is positive.
since (0100)2 = (4)10
so, result = +4 which is correct answer
(ii) 3 – 7:
binary of 3 = 0011
binary of 7 = 0111
Step 1. 1’s complement of 0111 = 1000
Step 2. Perform addition of minuend and 1’s complement of subtrahend
Step 3. No carry produced so no EAC operation.

Step 4. Since no carry produced in step 2, result is negative and is in complemented
form. So we must take 1’s complement of result to find correct magnitude of result.
1’s complement of result (1011)2 = (0100)2
so, final result = –(0100)2 or –(4)10
Note that when (in example (ii) the result was negative (step 2), MSB of the result was
1. When (in example (i)) the result was positive the MSB was 0. The same can be observed
in 2’s complement subtraction.
2’s complement Subtraction Method of 2’s complement is similar to 1’s complement
subtraction except the end around carry (EAC). The rules are listed below:
1. Take 2’s complement of subtrahend.
2. Add 2’s complement of subtrahend to minuend.
3. If a carry is produced, then discard the carry and the result is positive. If no carry
is produced result is negative and is in 2’s compliment form.
Example 2. Perform following subtraction using 2’s complement.
(i) 7 – 5 (ii) 5 – 7
Solution. (i) 7 – 5: binary of 7 = (0111)2 OP both the numbers should
binary of 5 = (0101)2 Q have equal length.
Step 1. 2’s complement of subtrahend (=0101)2 = (1011)2.
Step 2. Perform addition of minuend and 2’s complement of subtrahend.
Step 3. Since a final carry is produced in step 2 (which is discarded) the result is positive.
So,
result = (0010)2 = (2)10
(ii) 5 – 7:
binary of 5 = (0101)2
binary of 7 = (0111)2
Step 1. 2’s complement of subtrahend (= 0111) = 1001.
Step 2. Addition of minuend and 2’s complement of subtrahend.
Step 3. Since final carry is not generated in step 2, the result is negative and is in 2’s
complement form. So we must take 2’s complement of result obtained in step 2 to find correct
magnitude of result.
2’s complement of result (1110)2 = (0010)2
so, final result = – (0010)2 = – (2)10
1.7.3 Signed Binary Representation

Untill now we have discussed representation of unsigned (or positive) numbers, except
one or two places. In computer systems sign (+ve or –ve) of a number should also be
represented by binary bits.
The accepted convention is to use 1 for negative sign and 0 for positive sign. In signed
representation MSB of the given binary string represents the sign of the number, in all types
of representation. We have two types of signed representation:
1. Signed Magnitude Representation
2. Signed Complement Representation
In a signed-magnitude representation, the MSB represent the sign and rest of the bits
represent the magnitude. e.g.,
Note that positive number is represented similar to unsigned number. From the example
it is also evident that out of 4-bits, only 3-bits are used to represent the magnitude. Thus in
general, n – 1 bits are used to denote the magnitude. So, the range of signed representation
becomes –(2n–1 – 1) to (2n–1 – 1).
In a signed-complement representation the positive numbers are represented in true
binary form with MSB as 0. Whereas the negative numbers are represented by taking
appropriate complement of equivalent positive number, including the sign bit. Both 1’s and
2’s complements can be used for this purpose e.g.,
+5 = (0101)2
–5 = (1010)2 ←in 1’s complement
= (1011)2 ←in 2’s complement
Note that in signed complement representation the fact remains same that n – 1 bits are
used for magnitude. The range of numbers
In 1’s complement 0 to (2n–1 – 1) Positive Numbers
– 0 to –(2n–1 – 1) Negative Numbers
In 2’s complement 0 to (2n–1 – 1) Positive Numbers
– 1 to –2n–1 Negative Numbers
To illustrate the effect of these 3 representations, we consider 4-bit binary representation
and draw the below table. Carefully observe the differences in three methods.
Decimal Signed 1’s complement 2’s complement
Magnitude
+0 0 0 0 0 0 0 0 0 0 0 0 0
+1 0 0 0 1 0 0 0 1 0 0 0 1
+2 0 0 1 0 0 0 1 0 0 0 1 0
+3 0 0 1 1 0 0 1 1 0 0 1 1
+4 0 1 0 0 0 1 0 0 0 1 0 0
+5 0 1 0 1 0 1 0 1 0 1 0 1
+6 0 1 1 0 0 1 1 0 0 1 1 0
+7 0 1 1 1 0 1 1 1 0 1 1 1
–8 — — 1 0 0 0
–7 1 1 1 1 1 0 0 0 1 0 0 1
–6 1 1 1 0 1 0 0 1 1 0 1 0
–5 1 1 0 1 1 0 1 0 1 0 1 1
–4 1 1 0 0 1 0 1 1 1 1 0 0
–3 1 0 1 1 1 1 0 0 1 1 0 1
–2 1 0 1 0 1 1 0 1 1 1 1 0
–1 1 0 0 1 1 1 1 0 1 1 1 1
–0 1 0 0 0 1 1 1 1 —
Fig. 1.12 Different signed representation
From the table, it is evident that both signed Magnitude and 1’s complement methods
introduce two zeros +0 and – 0 which is awkward. This is not the case with 2’s complement.
This is one among the reasons that why all the modern digital systems use 2’s complement
method for the purpose of signed representation. From the above table, it is also evident that
2n 2n
in signed representation positive numbers and negative numbers can be represented
2 2
2n
with n-bits. Out of 2n combinations of n-bits, first combinations are used to denote the
2
2n
positive numbers and next combinations represent the negative numbers.
2
Example 1. In a signed representation given binary string is (11101)2. What will be the
sign and magnitude of the number represented by this string in signed magnitude, 1’s
complement and 2’s complement representation.
Solution.
The number N = (11101)2
since MSB = 1 the given number is negative.
(i) In signed Magnitude MSB denotes sign and rest of the bits represent magnitude. So,
(ii) In 1’s complement if number is negative (i.e., MSB = 1) then the magnitude is
obtained by taking 1’s complement of given number.
1’s complement of (11101)2 = (00010)2
so, (11101)2 = –2 in 1’s complement.
(iii) In 2’s complement if number is negative (i.e., MSB = 1) then magnitude is obtained
by taking 2’s complement of given number.
2’s complement of (11101)2 = (00011)2
= 3
so, (11101)2 = –3 in 2’s complement.
Example 2. Obtain an 8-bit representation of –9 in signed Magnitude, 1’s complement
and 2’s complement representation.
Solution. We first find binary of 9 i.e., (9)10 = (1001)2
Next we represent 9 using 8-bits. So, N = (00001001)2
= (9)10
(i) In signed Magnitude, MSB shows sign and rest of the bits shows true magnitude. So,
(–9)10 = (10001001)2
(ii) In 1’s complement, negative number is represented by taking 1’s complement of
positive number. So,
(–9)10 = 1’s complement of (00001001)2
= (11110110)2
(iii) In 2’s complement

(–9)10 = 2’s complement of (00001001)2
= (11110111)2
1.7.4 Arithmetic Overflow

When the result of an arithmetic operation requires n+1 bits, upon operating on n-bits
number, an overflow occurs. Alternately, if result exceeds the range 0 to 2n – 1, an overflow
occurs.
Let us consider the addition of two 4-bit numbers
Thus, addition of two 4-bits numbers requires 5-bits (n+1 bits) to represent the sum.
Alternately, the result of addition of 4-bits, falls outside the range 0 to 15 (i.e., 0 to 24–1).
Thus, overflow has occured.
In case of signed arithmetic the overflow causes the sign bit of the answer to change.
In this case an overflow occurs if the result does not lie in the range –2n–1 to 2n–1 – 1. In
signed arithmetic overflow can occur only when two positive numbers or two negative num-
bers are added.
Let us consider 4-bit signed 2’s complement representation.
1. Addition of two positive numbers +6 and +5
Since, MSB of result is 1, if reflects a negative result which is incorrect. It happened

because overflow has changed the sign of result.
2. Addition of two negative numbers –6 and –5
In 2’s complement if a carry is generated after the addition then carry is discarded and
result is declared positive. Thus, result = (0101)2 = +5 which is wrong, because addition of
two negative numbers should give a negative result. This happened due to overflow.
Note that overflow is a problem that occurs when result of an operation exceeds the
capacity of storage device. In a computer system, the programmer must check the overflow
after each arithmetic operation.
1.7.5 9’s and 10’s Complement

9’s and 10’s complements are the methods used for the representation of decimal num-
bers. They are identical to the 1’s and 2’s complements used for binary numbers.
9’s complement: 9’s complement of a decimal number is defined as (10n – 1) – N, where n

is no. of digits and N is given decimal numbers. Alternately, 9’s complement of a decimal number
can be obtained by subtracting each digit from 9.
9’s complement of N = (10n–1) – N.
Example 1. Find out the 9’s complement of following decimal numbers.
(i) 459 (ii) 36 (iii) 1697
n
Solution. (i) By using (10 –1) – N; But, n = 3 in this case
So, (10n–1) – N = (103 – 1) – 459 = 540
Thus, 9’s complement of 459 = 540
(ii) By subtracting each digit from 9
9 9
–3 6
6 3
So, 9’s complement of 36 is 63.
(iii) We have N = 1697, so n = 4
Thus, 10 –1 = 104 – 1 = 9999
n
So, (10n–1) – N = (104–1) – 1697 = 9999 – 1697

= 8302
Thus, 9’s complement of 1697 = 8302
10’s complement: 10’s complement of a decimal number is defined as 10n – N.
10’s complement of N = 10n – N
but 10n – N = (10n – 1) – N + 1
= 9’s complement of N + 1
Thus, 10’s complement of a decimal number can also be obtained by adding 1 to its 9’s
complement.
Example 2. Find out the 10’s complement of following decimal numbers. (i) 459 (ii) 36.
Solution. (i) By using 10n – N; We have N = 459 so n = 3
So, 10n – N = 103 – 459 = 541
So, 10’s is complement of 459 = 541
(ii) By adding 1 to 9’s complement
9’s complement of 36 = 99 – 36
= 63
Hence, 10’s complement of 36 = 63 + 1
= 64
1.7.6 r’s Complement and (r – 1)’s Complement

The r’s and (r – 1)’s complements are generalized representation of the complements, we
have studied in previous subsections. r stands for radix or base of the number system, thus
r’s complement is referred as radix complement and (r – 1)’s complement is referred as
diminished radix complement. Examples of r’s complements are 2’s complement and 10’s
complement. Examples of (r – 1)’s complement are 1’s complement and 9’s complement.
In a base-r system, the r’s and (r – 1)’s complement of the number N having n digits,
can be defined as:
(r – 1)’s complement of N = (rn – 1) – N
and r’s complement of N = rn – N

= (r – 1)’s complement of N + 1
The (r – 1)’s complement can also be obtained by subtracting each digit of N from
r–1. Using the above methodology we can also define the 7’s and 8’s complement for octal
system and 15’s and 16’s complement for hexadecimal system.
1.7.7 Rules for Subtraction using (r–1)’s Complement

Let M (minuend) and S (subtrahend) be the two numbers to be used to evaluate the
difference D = M – S by (r – 1)’s complement and either or both the numbers may be signed
or unsigned.
Until and unless specified the given rules are equally applied for both signed and un-
signed arithmetic. For the clarity of process, let us assume that two data sets are:
Unsigned data— Mu = 1025, Su = 50 and Du = Mu – Su
Signed data— Ms = –370, Ss = 4312 and Ds = Ms – Ss
Step 1. Equate the Length

Find out the length of both the numbers (no. of digit) and see if both are equal. If not,
then make the both the numbers equal by placing leading zeroes.
Mu = 1025, Su = 50 → Su = 0050
Ms = –370, Ss = 4312 → Ms = –0370
Step 2. Represent Negative Operands (for Negative Numbers only)

If either or both of operands are negative then take the (r – 1)’s complement of the
number as obtained in step 1.
Ms = –370 (r – 1)’s of Ms = 9999 – 0370 = 9629
Ss = 4312
Step 3. Complement the Subtrahend

In order to evaluate difference take the (r – 1)’s complement of the representation
obtained for the subtrahend Su in step 1 and Ss in step 2.
Su = 0050, (r – 1)’s of Su = 9999 – 0050 = 9949 and Mu = 1025
Ss = 4312, (r – 1)’s of Ss = 9999 – 4312 = 5687 and Ms = 9629
Step 4. Addition and the Carry (CY)

Add the two numbers in the step 3 and check whether or not carry generated from MSB
due to addition.
Mu = 1025, Su = 9949 → Du = Mu – Su = 10974
↓
CY
Ms = 9629, Ss = 5687 → Ds = Ms – Ss = 15316

↓
CY
Step 5. Process the Carry (CY)

In step 4, we obtained result as CY, D. The CY from MSB contains some useful
information especially in some unsigned arithmetic. Processing of carry for (r – 1)’s comple-
ment is
• In this case if a carry is generated from MSB in step 4, add this carry to the LSB
of the result. In step 4, we got CY = 1, Du = 0974 also CY = 1, Ds = 5316. After
adding carry to the LSB (generated in step 4) we get, Du = 0974 + 1 → 0975 and
Ds = 5316 + 1 → 5317. The carry in this case is called “end-around carry”.
Step 6. Result Manipulation

The way result is manipulated is different for signed and unsigned arithmetic.
(a) UNSIGNED
1. If a carry is generated in step 4 then the result is positive(+) and the digits in the
result shows the correct magnitude of result.
2. If there is no carry from MSB in step 4 then the result is negative (–) and the digits
in result is not showing the correct magnitude. So, we must go for a post processing
of result (Step 7) of result to determine the correct magnitude of the result.
(b) SIGNED
1. If the MSB of result obtained in step 5 is lesser than the half radix (i.e., MSB <
r/2) then the result is +ve and representing the correct magnitude. Thus, no post
processing is required.
2. If the MSB of result obtained in step 5 is not lesser than the half radix (i.e., MSB
> r/2) = then the result is –ve and correct magnitude of which must be obtained
by post processing (Step 7).
Step 7. Post Processing and Result Declaration

By the step 6(a) – 1 and the step 6(b) – 1 we know that if the result is positive (+ve) it
represents the correct magnitude whether it is signed or unsigned arithmetic. However, the
negative results are not showing correct magnitudes so post processing in principle is needed
for declaration of negative results.
(a) Declare positive results. As per the rules the result of the unsigned arithmetic is
positive. Therefore,
Du = +0975
(b) Process and declare negative results. As per the rules result of signed arithmetic
is negative and is in complemented form. Take the (r – 1)’s complement to find the
complement and declare the result.
(r – 1)’s of Ds = 9999 – 5317 = –4682
Therefore, Ds = –4682
1.7.8 Rules for Subtraction using r’s Complement

For better understanding and clarity, let us assume the same data sets for (r – 1)’s
complement method:
Unsigned data— Mu = 1025, Su = 50 and Du = Mu – Su
Signed data— Ms = –370, Ss = 4312 and Ds = Ms – Ss
Step 1. Equate the Length

Same as for (r – 1)’s complement i.e.
Mu = 1025, Su = 50 → Su = 0050
Ms = –370, Ss = 4312 → Ms = –0370
Step 2. Represent Negative Operands

Take the r’s complement of negative operands
Ms = –370, r’s of Ms = 9999 – 370 + 1 = 9630
Ss = 4312
Step 3. Complement the Subtrahend

Take the r’s complement of the representation obtained for the subtrahend Su in step
1 and Ss in step 2 to evaluate the difference
Su = 0050, r’s of Su = 10000 – 0050 = 9950 and Mu = 1025
Ss = 4312, r’s of Ss = 10000 – 4312 = 5688 and Ms = 9630
Step 4. Addition and Carry (CY)

Add the two numbers in the step 3 and check whether or not carry generated from MSB
due to addition. (Same as (r – 1)’s complement).
Mu = 1025, Su = 9950 → Du= 10975
↓
CY
Ms = 9630, Ss = 5688 → Ds = 15318
↓
CY
Step 5. Process the Carry (CY)

If there is carry from MSB in step 4 then simply discard it. In step 4, we got CY = 1,
Du = 0975 also CY = 1, Ds = 5318. After discarding the carry we get, Du = 0975 and Ds = 5318.
Step 6. Result Manipulation

The way result is manipulated is different for signed and unsigned arithmetic.
(a) UNSIGNED
1. If a carry is generated in step 4 then the result is positive(+) and the digits in the
result shows the correct magnitude of result.
2. If there is no carry from MSB in step 4 then the result is negative (–) and the digits
in result is not showing the correct magnitude. So, we must go for a post processing
of result (Step 7) of result to determine the correct magnitude of the result.
(b) SIGNED
1. If the MSB of result obtained in step 5 is lesser than the half radix (i.e., MSB <
r/2) then the result is +ve and representing the correct magnitude. Thus no post
processing is required.
2. If the MSB of result obtained in step 5 is not lesser than the half radix (i.e., MSB
> r/2) = then the result is –ve and correct magnitude of which must be obtained
by post processing (Step 7).
Step 7. Post Processing and Result Declaration

(a) Declare positive results. As per the rules, the positive result shows the correct
magnitude. Since, the result of the unsigned arithmetic is positive. Therefore,
Du = +0975
(b) Process and declare negative results. As per the rule, the result obtained of signed
arithmetic is negative and is in complemented form. Take the r’s complement to
find the complement and declare the result.
r’s of Ds = 10000 – 5318 = –4682
Therefore, Ds = –4682
1.8 BINARY CODED DECIMAL (BCD) AND ITS ARITHMETIC

The BCD is a group of four binary bits that represent a decimal digit. In this repre-
sentation each digit of a decimal number is replaced by a 4-bit binary number (i.e., a
nibble). Since a decimal digit is a number from 0 to 9, a nibble representing a number
greater than 9 is invalid BCD. For example (1010)2 is invalid BCD as it represents a
number greater than 9. The table shown in Fig. 1.13 lists the binary and BCD represen-
tation of decimal numbers 0 to 15. Carefully observe the difference between binary and
BCD representation.
Decimal Binary Representation BCD Representation
Number
0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 1
2 0 0 1 0 0 0 1 0
3 0 0 1 1 0 0 1 1
4 0 1 0 0 0 1 0 0
5 0 1 0 1 0 1 0 1
6 0 1 1 0 0 1 1 0
7 0 1 1 1 0 1 1 1
8 1 0 0 0 1 0 0 0
9 1 0 0 1 1 0 0 1
10 1 0 1 0 0 0 0 1 0 0 0 0
11 1 0 1 1 0 0 0 1 0 0 0 1
12 1 1 0 0 0 0 0 1 0 0 1 0
13 1 1 0 1 0 0 0 1 0 0 1 1
14 1 1 1 0 0 0 0 1 0 1 0 0
15 1 1 1 1 0 0 0 1 0 1 0 1
Fig. 1.13 Binary and BCD representation of decimal numbers
BCD Addition: In many application it is required to add two BCD numbers. But the
adder circuits used are simple binary adders, which does not take care of peculiarity of BCD
representation. Thus one must verify the result for valid BCD by using following rules:
1. If Nibble (i.e., group of 4-bits) is less than or equal to 9, it is a valid BCD number.
2. If Nibble is greater than 9, it is invalid. Add 6 (0110) to the nibble, to make it valid.
Or
If a carry was generated from the nibble during the addition, it is invalid. Add 6
(0110) to the nibble, to make it valid.
3. If a carry is generated when 6 is added, add this carry to next nibble.
Example 1. Add the following BCD numbers. (i) 1000 and 0101 (ii) 00011001 and 00011000
Solution. (i)
Since, (1101)2 > (9)10 add 6 (0110) to it

So,
So, result = 00010011
(ii)
Since, a carry is generated from right most nibble we must add 6 (0110) to it.
So,
So, result = 00110111

BCD Subtraction. The best way to cary out the BCD subtraction is to use comple-
ments. The 9’s and 10’s complement, studied in subsection 1.7.5, are exclusively used for this
purpose. Although any of the two complements can be used, we prefer 10’s complement for
subtraction. Following are the steps to be followed for BCD subtraction using 10’s comple-
ment:
1. Add the 10’s complement of subtrahend to minuend.
2. Apply the rules of BCD addition to verify that result of addition is valid BCD.
3. Apply the rules of 10’s complement on the result obtained in step 2, to declare the
final result i.e., to declare the result of subtraction.
Example 2. Subtract 61 from 68 using BCD.
Solution. To illustrate the process first we perform the subtraction using 10’s comple-
ment in decimal system. After that we go for BCD subtraction.
we have, D = 68 – 61
So, 10’s complement of 61 = 99 – 61 + 1 = 39
So, 68
+ 3 9
1 0 7
↑
Carry
In 10’s complement if an end carry is produced then it is discarded and result is declared
positive. So,
D = +07
by using BCD
1.
2. Check for valid BCD– since a carry is generated from right most nibble, we must add
6 (0110) to it. Since the left most nibble is greater than 9, we must add 6(0110) to it.
Thus,
3. Declaration of result – We got end carry is step 2. In 10’s complement arithmetic, end
carry is discarded and result is declared positive. Hence,
D = (00000111)2 = (7)10
1.9 CODES
Coding and encoding is the process of assigning a group of binary digits, commonly
referred to as ‘bits’, to represent, identify, or relate to a multivalued items of information. By
assigning each item of information a unique combination of bits (1’s and o’s), we transform
some given information into another form. In short, a code is a symbolic representation of
an information transform. The bit combination are referred to as ‘CODEWORDS’.
There are many different coding schemes, each having some particular advantages and
characteristics. One of the main efforts in coding is to standardize a set of universal codes
that can be used by all.
In a broad sense we can classify the codes into five groups:
(i) Weighted Binary codes
(ii) Non-weighted codes
(iii) Error–detecting codes
(iv) Error–correcting codes
(v) Alphanumeric codes.
1.9.1 Weighted Binary Codes
In weighted binary codes, each position of a number represents a specific weight. The
bits are multiplied by the weights indicated; and the sum of these weighted bits gives the
equivalent decimal digit. We have been familiar with the binary number system, so we shall
start with straight binary codes.
(a) Straight Binary coding is a method of representing a decimal number by its binary
equivalent. A straight binary code representing decimal 0 through 7 is given in Table 2.
Table 2
Decimal Three bit straight Weights MOI Sum
Binary Code 22 21 20
0 000 0 0 0 0
1 001 0 0 1 1
2 010 0 2 0 2
3 011 0 2 1 3
4 100 4 0 0 4
5 101 4 0 1 5
6 110 4 2 0 6
7 111 4 2 1 7
In this particular example, we have used three bits to represent 8 distinct elements of
information i.e., 0 through 7 in decimal form.
Now the question arises, if n elements of information are to be coded with binary (two
valued bits), then how many bits are required to assign each element of information a unique
code word (bit combination). Unique is important, otherwise the code would be ambiguous.
The best approach is to evaluate how many code words can be derived from a combina-
tion of n bits.
For example: Let n = no. of bits in the codeword and x = no. of unique words
Now, if n = 1, then x = 2 (0, 1)
n = 2, then x = 4 (00, 01, 10, 11)
n = 3, then x = 8 (000, 001, ..., 111)

and in general, n = j, then x = 2 j
that is, if we have available j no. of bits in the code word, we can uniquely encode max 2 j
distinct elements of information.
Inversely, if we are given x elements of information to code into binary coded format,
the following condition must hold:
x < 2j
or j > log2 x
or j > 3.32 log10 x
where j = number of bits in code word.
Example 1. How many bits would be required to code the 26 alphabetic characters plus
the 10 decimal digits.
Solution. Here we have total 36 discrete elements of information.
i.e., x = 36
Now j > log2 x
therefore, j > log2 36 or j > 3.32 log10 36
or j > 5.16 bits
Since bits are not defined in fractional parts, we know j > 6.
In other words, a minimum of 6 bit code is required that leaves 28 unused code words
out of the 64 which are possible (26 = 64 and 64 – 36 = 28).
This system of straight binary coding has the disadvantage that the large numbers
require a great deal of hardware to handle with. For example if we have to convert decimal
2869594 to straight binary code a regrous division of this number by 2 is required untill we
get remainder 0 or 1.
The above difficulty is overcomed by using another coding scheme called as BCD codes.
(b) Binary Codes Decimal Codes (BCD codes). In BCD codes, individual decimal
digits are coded in binary notation and are operated upon singly. Thus binary codes represent-
ing 0 to 9 decimal digits are allowed. Therefore, all BCD codes have at least four bits (∵ min.
no. of bits required to encode to decimal digits = 4)
For example, decimal 364 in BCD
3 → 0011
6 → 0110
4 → 0100
364 → 0011 0110 0100
However, we should realize that with 4 bits, total 16 combinations are possible (0000,
0001, ..., 11 11) but only 10 are used (0 to 9). The remaining 6 combinations are unvalid and
commonly referred to as ‘UNUSED CODES’.
There are many binary coded decimal codes (BCD) all of which are used to represent
decimal digits. Therefore, all BCD codes have atleast 4 bits and at least 6 unassigned or
unused code words shown in Table 3.
Some example of BCD codes are:
(a) 8421 BCD code, sometimes referred to as the Natural Binary Coded Decimal Code
(NBCD);
(b)* Excess-3 code (XS3);
(c)** 84 –2 –1 code (+8, +4, –2, –1);
(d) 2 4 2 1 code
Example 2. Lowest [643]10 into XS3 code
Decimal 6 4 3
Add 3 to each 3 3 3
Sum 9 7 6
Converting the sum into BCD code we have
9 7 6
↓ ↓ ↓
1001 0111 0110
Hence, XS3 for [643]10 = 1001 0111 0110
Table 3. BCD codes
Decimal 8421 Excess-3 84–2–1 2421
Digit (NBCD) code (XS3) code code
0 0000 0011 0000 0000

1 0001 0100 0111 0001
2 0010 0101 0110 0010
3 0011 0110 0101 0011
4 0100 0111 0100 0100
5 0101 1000 1011 1011
6 0110 1001 1010 1100
7 0111 1010 1001 1101
8 1000 1011 1000 1110
9 1001 1100 1111 1111
* XS3 is an example of nonweighted code but is a type of BCD code. It is obtained by adding 3 to a
decimal number. For example to encode the decimal number 7 into an excess 3 code. We must first add
3 to obtain 10. The 10 is then encoded in its equivalent 4 bit binary code 1010. Thus as the name
indicates, the XS3 represents a decimal number in binary form, as a number greater than 3.
** Dashes (–) are minus signs.
There are many BCD codes that one can develop by assigning each column or bit position
in the code, some weighting factor in such a manner that all of the decimal digits can be coded
by simply adding the assigned weights of the 1 bits in the code word.
For example: 7 is coded 0111 in NBCD, which is interpreted as

0 × 8 + 1 × 4 + 1 × 2 + 1 × 1 = 7
The NBCD code is most widely used code for the representation of decimal quantities in
a binary coded formet.
For example: (26.98) would be represented in NBCD as
2 6 9 8
(26.98)10 = (0010 0110. 1001 1000) NBCD
It should be noted that on the per digit basis the NBCD code is the binary numeral
equivalent of the decimal digit it represents.
Self complementing BCD codes

The excess 3, 8 4–2–1 and 2421 BCD codes are also known as self complementing
codes.
Self complementing property– 9’s complement of the decimal number is easily obtained
by changing 1’0 to 0’s and 0’s to 1’s in corresponding codeword or the 9’s complement of self
complementing code word is the same as its logical complement.
When arithmetic is to be performed, often an arithmetic “complement” of the numbers
will be used in the computations. So these codes have a particular advantage in machines that
use decimal arithmetic.
Example 3. The decimal digit 3 in 8.4–2–1 code is coded as 0101. The 9’s complement
of 3 is 6. The decimal digit 6 is coded as 1010 that is 1’s complement of the code for 3. This
is termed as self complementing property.
1.9.2 Non-Weighted Codes

These codes are not positionally weighted. This means that each position within a binary
number is not assigned a fixed value. Excess-3 codes and Gray codes are examples of non-
weighted codes.
We have already discussed XS3 code.
Gray code (Unit Distance code or Reflective code)

There are applications in which it is desirable to represent numerical as well as other
information with a code that changes in only one bit position from one code word to the next
adjacent word. This class of code is called a unit distance code (UDC). These are sometimes
also called as ‘cyclic’, ‘reflective’ or ‘gray’ code. These codes finds great applications in Boolean
function minimization using Karnaugh map.
The gray code shown in Table 4 is both reflective and unit distance.
Table 4. Gray codes*

Decimal Three bit Four bit
Digit Gray code Gray code
0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 1
2 0 1 1 0 0 1 1
3 0 1 0 0 0 1 0
4 1 1 0 0 1 1 0
5 1 1 1 0 1 1 1
6 1 0 1 0 1 0 1
7 1 0 0 0 1 0 0
8 – 1 1 0 0
9 – 1 1 0 1
10 – 1 1 1 1
11 – 1 1 1 0
12 – 1 0 1 0
13 – 1 0 1 1
14 – 1 0 0 1
15 – 1 0 0 0
Binary to Gray Conversion

(1) Place a leading zero before the most significant bit (MSB) in the binary number.
(2) Exclusive-OR (EXOR) adjacent bits together starting from the left of this number
will result in the Gray code equivalent of the binary number.
Exclusive–OR– If the two bits EX–OR’d are identical, the result is 0; if the two bits differ,
the result is 1.
*Gray codes are formed by reflection. The technique is as follows: 0 0 0

In binary we have two digits 0 and 1. 0 1 1
Step I. Write 0 and 1 and put a mirror, we first see 1 and 1 1 2
then 0. Place 0’s above mirror and 1’s below mirror 1 0 3
We have got gray code for decimal digits 0 through 4.
Step II. Write these 4 codes and again put a mirror. The code 0 00 0
will look in the order 10, 11, 01 and 00. Then place 0’s above 0 01 1
mirror and 1’s below mirror. 0 11 2
Proceeding intactively in the same manner. We can form Gray 0 10 3
code for any decimal digit.
1 10 4
1 11 5
1 01 6
1 00 7
Example. Convert binary 1010010 to Gray code word.
Gray to Binary Conversion

Scan the gray code word from left to right. The first 1 encountered is copied exactly as
it stands. From then on, 1’s will be written untill the next 1 is encountered, in which case
a 0 is written. Then 0’s are written untill the next 1 is encountered, in which case a 1 is
written, and so on.
Example 1. Convert Gray code word 1111011 into binary.
1 1 1 1 0 1 1
↓ ↓ ↓ ↓ ↓ ↓ ↓ ⇒ (1111011)Gray = (1010010)2.
1 0 1 0 0 1 0
Example 2. Convert Gray code word 10001011 into binary.
1 0 0 0 1 0 1 1
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
1 1 1 1 0 0 1 0
⇒ (10001011)Gray = (11110010)2.
1.9.3 Error Detecting Codes

Binary information is transmitted from one device to another by electric wires or other
communication medium. A system that can not guarantee that the data received by one
device are identical to the data transmitted by another device is essentially useless. Yet
anytime data are transmitted from source to destination, they can become corrupted in
passage. Many factors, including external noise, may change some of the bits from 0 to 1 or
viceversa. Reliable systems must have a mechanism for detecting and correcting such errors.
Binary information or data is transmitted in the form of electromagnetic signal over a
channel whenever an electromagnetic signal flows from one point to another, it is subject to
unpredictable interference from heat, magnetism, and other forms of electricity. This inter-
ference can change the shape or timing of signal. If the signal is carrying encoded binary data,
such changes can alter the meaning of data.
In a single bit error, a 0 is changed to a 1 or a 1 is changed to a 0.
In a burst error, multiple (two or more) bits are changed.
The purpose of error detection code is to detect such bit reversal errors. Error detection
uses the concept of redundancy which means adding extra bits for detecting errors at the
destination.
Four types of redundancy checks are used: Parity check (vertial redundancy check)
(VRC), longitudinal redundancy check (LRC), cyclic redundancy check (CRC), and checksum.
For a single bit error detection, the most common way to achieve error detection is by
means of a parity bit.
A parity bit is an extra bit (redundant bit) included with a message to make the total
number of 1’s transmitted either odd or even.
Table 5 shows a message of three bits and its corresponding odd and even parity bits.
If an odd parity is adopted, P bit is choosen such that the total no. of 1’s is odd in four
bit that constitute message bits and P.
If an even parity is adopted, the P bit is choosen such that the total number of 1’s is even.
Table 5. Parity bit generation
Message Odd Even Parity
x y z Parity (P) bit bit (P)
0 0 0 1 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 0 1
The message with the parity bit (either odd or even) is transmitted to its destination. The
parity of the received data is checked at the receiving end. If the parity of the received data is
changed (from that of transmitted parity), it means that at least one bit has changed their value
during transmission. Though the parity code is meant for single error detection, it can detect any
odd number of errors. However, in both the cases the original codeword can not be found.
If there is even combination of errors (means some bits are changed but parity remains
same) it remains undetected.
Longitudinal Redundancy Check (LRC)

In LRC, a block of bits is organised in rows and columns (table). For example, a block
of 16 bits can be organised in two rows and eight columns as shown in Fig. 1.14. We then
calcualte the parity bit (even parity/odd parity, here we are using even parity) for each column
and create a new row of 8 bits, which are the parity bits for the whole block.
11011101 00111001 Original data
11011101
00111001
LRC 11100100
11011101 00111001 11100100 Original data with LRC
Fig. 1.14
Cyclic Redundancy Check

CRC is most powerful of the redundancy checking techniques. Cyclic redundancy check
is based on binary division. A sequence of redundant bits called CRC or CRC remainder is
appended to the end of a data unit. After adding CRC remainder, the resulting data unit
becomes exactly divisible by another predetermined binary number. At the destination this
data unit is divided by the same binary number. If there is no remainder, then there is no
error. The question is how to obtain correct CRC? CRC is the remainder obtained by dividing
the data unit by a predtermined divisor if it has exactly one bit less than divisor and by
appending the CRC to the data string make it completely divisible by the divisior.
The CRC generator and CRC checker are shown in Fig. 1.15(a) and Fig. 1.15(b) respectively.
n bits
Data 00.............0
Using modulo-2 division
Divisor (n + 1) bits
CRC Remainder
(n bits) Code word
Data CRC
Fig. 1.15(a) CRC generator
Code word
Data CRC
Using modulo-2 division
Divisor
Remainder 0 shows no errors
Fig. 1.15(b) CRC checker

Example 1. For the divisor 10101, check whether there are errors in the received code-
word 1100 1001 01011.
Solution. As shown in Fig. 1.15(b).
Code word: 1100 1001 01011.
Divisor : 10101
Using modulo-2 division, we obtain
111110001
Divisor ® 10101 1100100101011 Received code word
Modulo-2 sum 10101
11000
10101
11010
10101
11111
10101
10100
10101
00011011
10101
1110 Remainder
Since, remainder is non-zero shows that there is errors in the received code word.
Example 2. Generate the CRC code for the data word of 1100 10101. The divisor is 10101.
Solution. As shown in Fig. 1.15(a).
Data word: 1100 10101.
Divisor : 10101
The no. of data bits (k) = 9
The no. of bits in divisor (n + 1) = 5
Therefore, no. of zeroes to be appended at the end of data word will be n = 4
Hence, dividend = 1100101010000
(data word + number of zeroes)
Carry out the modulo-2 division
111110111
10101 1100101010000
10101
11000
10101
11011
10101
11100
10101
10011
10101
01100
00000
11000
10101
11010
10101
11110
10101
1011 CRC
Therefore, the CRC will be 1011.
Hence, code word = Data + CRC
= 1100101011011
Checksums
The checksum method is used to detect double errors in bits. Since, the double error will
not change the parity of the bits, the parity checker will not indicate any error.
In the checksums method, initially a word A (let 11001010) is transmitted, next word B
(let 00101101) is transmitted. The sum of these two words is retained in the transmitter. Then
a word C is transmitted and added to the previous sum; and the new sum is retained.
Similarly, each word is added to the previous sum; after transmission of all the words, the
final sum called the checksum is also transmitted. The same operation is done at the receiv-
ing end and the final sum obtained here is checked against the transmitted checksum. If the
two sums are equal there is no error.
Burst Error Detection

So far we have considered detecting or correcting errors that occur independently or
randomly in digit positions. But disturbances can wipe out an entire block of digits. For
example, a stroke of lightenning or a human made electrical disturbance can affect several
transmitted digits. Burst errors are those errors that wipe out some or all of a sequential set
of digits.
A burst of length b is defined as a sequence of digits in which the first digit and bth digit
are in error, with the b-2 digits in between either in error or received correctly.
It can be shown that for detecting all burst errors of length b or less; b parity check bits
are necessary and sufficient.
To construct such a code, lets group k data digits into segment of b digits in length as
shown Fig. 1.16:
1101 0101 1110 0100 0010

b digits
k data bits Parity check bits
Fig. 1.16 Burst error detection
To this we add a last segment of b parity check digits, which are determined as follows:
“The modulo-2 sum* of the ith digit in each segment (including the parity check segment)
must be zero.”
It is easy to see that if a single sequence of length b or less is in error, parity will be
violated and the error will be detected and the reciever can request retransmission of code.
1.9.4 Error Correcting Codes

The mechanism that we have covered upto this point detect errors but do not correct
them. Error correction can be handled in two ways. In one, when an error is encountered
the receiver can request the sender to retransmit entire data unit. In the other, a receiver
can use an error correcting code, which automatically corrects certain errors.
In theory, it is possible to correct any binary code errors automatically using error
correcting codes, however they require more reductant bits than error detecting codes.
The number of bits required to correct a multiple-bit or burst error is so high that in most
cases, it is inefficient to do so. For this reason, most error correction is limited to one,
two, or three-bit errors. However, we shall confine our discussion to only single bit error
correction.
As we saw earlier, single bit errors can be detected by the addition of a redundant (parity)
bit to the data (information) unit. This provides sufficient base to introduce a very popular
error detection as well correction codes, known as Block codes.
Block codes: [(n, k) codes] In block codes, each block of k message bits is encoded into
a larger block of n bits (n > k), as shown in Fig. 1.17. These are also known as (n, k) codes.
* Modulo–2 sum denoted by symbol ⊕ with the rules of addition as follows:
R|0 ⊕ 0 = 0U|
|S0 ⊕ 1 = 1 |V
||1 ⊕ 0 = 1 ||
T1 ⊕ 1 = 0 W
The reductant* (parity) bits ‘r’ are derived from message bits ‘k’ and are added to them.
The ‘n’ bit block of encoder output is called a codeword.
Message Code
block block
ENCODER
Message Message Redundant bits
k bits k bits r bits

Code n bits = (k + r) bits
Fig. 1.17
The simplest possible block code is when the number of reductant or parity bits is one.
This is known as parity check code. It is very clear that what we have studied in single bit
error detection is nothing but a class of ‘Block codes’.
R.W. Hamming developed a system that provides a methodical way to add one or more
parity bit to data unit to detect and correct errors weight of a code.
Hamming distance and minimum distance

The weight of a code word is defined as the number of nonzero components in it. For example,
Code word Weight
010110 3
101000 2
000000 0
The ‘Hamming distance’ between two code words is defined as the number of components
in which they differ.
For example, Let U = 1010
V = 0111
W = 1001
Then, D (U, V) = distance between U and V = 3
Similarly, D (V, W) = 3
and D (U, W) = 2
The ‘minimum distance’ (Dmin) of a block code is defined is the smallest distance between
any pair of codewords in the code.
From Hamming’s analysis of code distances, the following important properties have
been derived. If Dmin is the minimum distance of a block code then
(i) ‘t’ number of errors can be detected if
Dmin = t + 1
(ii) ‘t’ number of errors can be corrected if
Dmin = 2t + 1
It means, we need a minimum distance (Dmin) of at least 3 to correct single error and
with this minimum distance we can detect upto 2 errors.
*The ‘r’ bit are not necessarily appear after ‘k’ bits. They may appear at the starting, end or in between
‘k’ data bits.
Now coming to our main objective i.e., error correction, we can say that an error occurs
when the receiver reads 1 bit as a 0 or a 0 bit as a 1. To correct the error, the reciever simply
reverses the value of the altered bit. To do so, however, it must know which bit is in error.
The secret of error correction, therefore, is to locate the invalid bit or bits.
For example, to correct a single bit error in a seven bit data unit, the error correction code
must determine, which of the seven data bits has changed. In the case we have to distinguish
between eight different states: no error, error in position 1, error in position 2, and so on, upto
error in position 7. To do so requires enough redudant bits to show all eight states.
At first glance, it appears that a 3-bit redundant code should be adequate because three
bits can show eight different states (000 to 111) and can thus indicate the locations of eight
different possibilities. But what if an error occurs in the redundant bits themselves. Seven
bits of data plus three bits of redundancy equals 10 bits. Three bits, however, can identify only
eight possibilities. Additional bits are necessary to cover all possible error locations.
Redundant Bits
To calculate the number of redundant bits (r) required to correct a given no. of data bits
(k), we must find a relationship between k and r. Fig. 1.18 shows k bits of data with r bits
of redundancy added to them. The length of the resulting code is thus n = k + r.
If the total no. of bits in code is k + r, then r must be able to indicate at least k + r + 1
different states. Of these, one state means no error and k + r states indicate the location of
an error in each of the k + r positions.
Redundant
Data (k) bits
(r) bits
Total k + r = n bits
Fig. 1.18
Alternatively, we can say the k + r + 1 status must be discoverable by r bits; and r bits
can indicate 2r different states. Therefore, 2r must be equal to or greater than k + r + 1:
2r > k + r + 1
The value of r can be determined by plugging in the value of k (the length of data unit).
For example, if the value of k is 7 (⇒ seven bit data), the smallest r value that can satisfy
this equation is 4:
24 > 7 + 4 + 1
and 23 > 7 + 4 + 1
1.9.5 Hamming Code

So far, we have examined the number of bits required to cover all of the possible single
bit error states in a transmission. But how do we manipulate those bits to discover which state
has occured ? A technique developed by R.W. Hamming provides a practical solution, Hamming
code is a class of block code (n, k) and we are going to discuss (11, 7) Hamming code.
Positioning the Redundant Bits

The ‘Hamming code’ can be applied to data units of any length and uses the relationship
between data and redundant bits as discussed above. As we have seen, a 7 bit data unit
(k = 7) requires 4 redundant bits (r = 4) that can be added to the end of data unit (or
interspersed with data bits). Such that a code word of length 11 bits (n = 11) is formed.
In Fig. 1.19 these bits are placed in positions 1, 2, 4 and 8 (the positions in an 11-bit
sequence that are powers of 2). We refer these bits as r1, r2, r4 and r8.
11 10 9 8 7 6 5 4 3 2 1 Bits (n)
d7 d6 d5 r4 d4 d3 d2 r3 d1 r2 r1
Redundant bits
Fig. 1.19
In the Hamming code, each r bit is the redundant bit for one combination* of data bits.
The combinations (modulo-2 additions) used to calculate each of four r values (viz, r1, r2, r4
and r8) for a 7 bit data sequence d1 through d7 are as follows:
r 1 : bits 1, 3, 5, 7, 9, 11
r 2 : bits 2, 3, 6, 7, 10, 11
r 4 : bits 4, 5, 6, 7
r 8 : bits 8, 9, 10, 11
Each data bit may be included in more than one redundant bit calculation. In the sequences
above, for example, each of the original data bits is included in at least two sets, while the
r bits are included in only one.
To see the pattern behind this strategy, look at the binary representation of each bit
position. The r1 bit is calculated using all bit positions whose binary representation includes
a 1 in the right most position. The r2 bit is calculated using all bit positions with a 1 in the
second position, and so on. (see Fig. 1.20)
r1 will take care
of these bits
1011 1001 0111 0101 0011 0001

11 9 7 5 3 1
d7 d6 d5 r8 d4 d3 d2 r4 d1 r2 r1
r2 will take care

of these bits
1011 1010 0111 0110 0011 0010

11 10 7 6 3 2
d7 d6 d5 r8 d4 d3 d2 r4 d1 r2 r1
*In codes combination of bits means modulo 2 addition of data bits. Modulo-2 addition applies
in binary field with following rules.
0⊕0 = 0 Modulo 2 → ⊕
0⊕1 = 1
1⊕ 0 = 1
1⊕1 = 0
r4 will take care

of these bits
0111 0110 0101 0100

7 6 5 4
d7 d6 d5 r8 d4 d3 d2 r4 d1 r2 r1
r8 will take care

of these bits
1011 1010 1001 1000

11 10 9 8
d7 d6 d5 r8 d4 d3 d2 r4 d1 r2 r1
Fig. 1.20
Calculating the r values

Fig. 1.21 shows a Hamming code implementation for a 7 bit data unit. In the first step;
we place each bit of original data unit in its appropriate position in the 11-bit unit. For
example, let the data unit be 1001101.
In the subsequent steps; we calculate the EVEN parities for the various bit combina-
tions. The even parity value for each combination is the value of corresponding r bit. For
example, the value of r1 is calculated to provide even parity for a combination of bits 3, 5,
7, 9 and 11.
i.e., 1011 1001 0111 0101 0011 0001
Here the total no. of 1’s are 13. Thus to provide even parity r1 = 1.
Similarly the value of r2 is calculated to provide even parity with bits 3, 6, 7, 10, 11, r4
with bits 5, 6, 7 and r8 with bits 9, 10, 11. The final 11-bit code is sent.
Data → 1001101
Data 1 0 0 r8 1 1 0 r4 1 r2 r1
11 10 9 8 7 6 5 4 3 2 1
Adding 1 0 0 r8 1 1 0 r4 1 r2 1
r1 r1 = 1
11 10 9 8 7 6 5 4 3 2 1
r2 = 0
r4 = 0
r8 = 1
Adding 1 0 0 r8 1 1 0 r4 1 0 1
r2 Thus
11 10 9 8 7 6 5 4 3 2 1 r8 r4 r2 r1 = 1 0 0 1
Sender’s
parity
Adding 1 0 0 r8 1 1 0 0 1 0 1
r4
11 10 9 8 7 6 5 4 3 2 1
Adding 1 0 0 1 1 1 0 0 1 0 1
r8
11 10 9 8 7 6 5 4 3 2 1
Code : 1001 110 0101

Fig. 1.21
Error detection and correction – Suppose above generated code is received with the
error at bit number 7 ⇒ bit has changed from 1 to 0 see Fig. 1.22.
Received Sent
1 0 0 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 0 1 0 1
Error
Fig. 1.22
The receiver receives the code and recalculate four new4 redundant bits (r1, r2, r4 and
r8) using the same set of bits used by sender plus the relevant parity bit for each set shown
in Fig. 1.23.
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 0 1 0 0 1 0 1
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 0 1 0 0 1 0 1
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 0 1 0 0 1 0 1
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 0 1 0 0 1 0 1
r8 r4 r2 r1
0 1 1 1
The bit in position 7 is in Error ← 7 in decimal

Fig. 1.23
Then it assembles the new parity values into a binary number in order of r position
(r8, r4, r2, r1). In our example, this step gives us the binary number 0111 (7 in decimal), which
is the precise location of the bit in error.
Once the bit is identified, the reciever can reverse its value and correct the error.
Note: If the new parity assembled is same as the parity at sender’s end mean no error.
1.9.6 Cyclic Codes

Binary cyclic codes form a subclass of linear block codes.
An (n, k) linear block code is called the cyclic code if it satisfies the following property:
If an n tuple (a row vector of n elements), V = (V0, V1, V2, . . ., Vn–1)
is a code vector or V, then the n tuple (Vn–1, V0, V1, . . ., Vn–2)
is obtained by shifting V cyclically one place to the right (it may be left also) is also a code
vector of V.
V1 = (Vn–1, V0, V1, . . ., Vn–2). From above definition it is clear that

V(i) = (Vn–i, Vn–i+1, . . ., V0, V1, . . . Vn–i–1).
An example of cyclic code:
1 1 0 1
1 1 1 0
0 1 1 1
1 0 1 1
1 1 0 1
It can be seen that 1101, 1110, 0111, 1011 is obtained by a cyclic shift of n-tuple 1101
(n = 4). The code obtained by rearranging the four words is also a cyclic code. Thus 1110, 0111,
1011 are also cyclic codes.
This property of cyclic code allows to treat the codewords as a polynomial form. A
procedure for generating an (n, k) cyclic code is as follows:
The bits of uncoded word (message), let D = [d0, d1, d2 ... dk–1] are written as the
coefficients of polynomial of degree k – 1.
D(x) = d0 x0 ⊕ d1x1 ⊕ d2x2 ⊕ ... ⊕ dk–1 xk–1
Similarly, the coded word, let V = [v0, v1, v2, ..., vn–1] are written as the coefficients of
polynomial of degree n – 1.
V(x) = v0x0 ⊕ v1x1 ⊕ v2x2 ⊕ . . . ⊕ vn–1 xn–1
The coefficients of the polynomials are 0’s and 1’s and they belong to the binary field with
the modulo-2 rules for addition as described in Hamming codes.
Now, we will state a theorem* which is used for cyclic code generation.
Theorem. If g(x) is a polynomial of degree (n–k) and is a factor of xn+1, then g(x)
generates an (n, k) cyclic code in which the code polynomial V(x) for a data polynomial D(x)
is given by
V(x) = D(x). g(x)
where V(x) – Code word polynomial of degree (n – 1)
D(x) – Data word polynomial of degree (k – 1)
g(x) – Generator polynomial of degree (n – k)
Example. Consider a (7, 4) cyclic code. The generator polynomial for this code is given
as g(x) = 1 + x + x3. Find all the code words of this code.
Solution. It is a (7, 4) cyclic code
n = No. of bits in coded word = 7
and k = No. of bits in data word = 4.
(n – k) = No. of redundant bits in code word = 3
It implies that, there are 16 different messages that are possible (0000, 0001, 0010
. . . 1110, 1111). Correspondingly, there will be 16 different codes (of 7 bits).
Now, according to above theorem, the generator polynomial g(x) must be a factor of
(xn + 1)** and of degree (n – k).
xn + 1 = x7 + 1
If we factorize this polynomial we get
x7+1 = (x + 1) (x3 + x + 1) (x3 + x2 + 1)
I II III
*Without giving proof that is beyond the scope of this book.
**+ means modulo-2 operation ⊕ in binary codes.
I Factor → x + 1
II Factor → x3 + x + 1
III Factor → x3 + x2 + 1
The I factor does not satisfy the requirement that it must be of degree (n – k) but the
II and III do satisfy.
Therefore, we can either choose II Factor or III Factor as generator polynomial g(x).
However, the set of codewords will naturally be different for these two polynomial.
In this example, we have taken g(x) as 1 + x + x3.
i.e., we have to encode the 16 messages using generator polynomial.
g(x) = 1 + x + x3.
Consider, for example, a data word 1010.
D = (d0, d1, d2, d3) = (1010)
Because the length is four, the data polynomial D(x)
will be of the form d0 + d1x + d2x2 + d3x3
D(x) = 1 + 0.x + 1.x2 + 0.x3 = 1 + x2
The code polynomial V(x) = D(x) . g(x)
= (1 + x2) . (1 + x + x3)
x3 + x3
= 1 + x + x2 + + x5
0
i.e., V(x) = 1 + x + x2 + x5
Because if x = 1 then x3 = 1
or if x = 0 then x3 = 0
0 ⊕ 0 = 1 ⊕ 1 = 0
Because the length of codeword and (n) is 7.
So the standard polynomial will be of the form.
V(x) = V0 + V1x + V2x2 + V3x3 + V4x4 +V5x5 + V6x6
Comparing this standard polynomial with above poly. for V(x)
we get V = [1110010]
In a similar way, all code vectors can be found out.
1.9.7 Alphanumeric Codes

For the inherently binary world of the computer, it is necessary to put all symbols, letters,
numbers, etc. into binary form. The most commonly used alphanumeric code is the ASCII code,
with other like the EBCDIC code being applied in some communication applications.
ASCII Alphanumeric Code

The American Standard Code for Information Interchange (ASCII) is the standard alpha-
numeric code for keyboards and a host of other data interchange tasks. Letters, numbers, and
single keystroke commands are represented by a seven-bit word. Typically, a strobe bit or
start bit is sent first, followed by the code with LSB first. Being a 7-bit code, it has 2^7 or
128 possible code groups.
LSB
MSB
LSB
MSB
Stop Stop
Start bit Start bit
bits bits
K = 100 1011 j = 110 1011
MSB
MSB
LSB
LSB
ASCII Alphanumeric Code
Char 7 bit ASCII HEX Char 7 bit ASCII HEX Char 7 bit ASCII HEX
A 100 0001 41 a 1100001 61 0 0110000 30
B 100 0010 42 b 1100010 62 1 0110001 31
C 100 0011 43 c 1100011 63 2 0110010 32
D 100 0100 44 d 1100100 64 3 0110011 33
E 100 0101 45 e 1100101 65 4 0110100 34
F 100 0110 46 f 1100110 66 5 0110101 35
G 100 0111 47 g 1100111 67 6 0110110 36
H 100 1000 48 h 1101000 68 7 0110111 37
I 100 1001 49 i 1101001 69 8 01l 1000 38
J 100 1010 4A j 1101010 6A 9 01l 1001 39
K 100 1011 4B k 1101011 6B blank 0100000 20
L 100 1100 4C 1 110 1100 6C . 010 1110 2E
M 100 1101 4D m 110 1101 6D ( 010 1000 28
N 100 1110 4E n 110 1110 6E + 010 1011 2B
O 100 1111 4F o 110 1111 6F $ 010 0100 24
P 101 0000 50 p 111 0000 70 * 010 1010 2A
Q 101 0001 51 q 111 0001 71 ) 010 1001 29
R 101 0010 52 r 111 0010 72 - 010 1101 2D
S 101 0011 53 s 111 0011 73 / 010 1111 2F
T 101 0100 54 t 111 0100 74 , 010 1100 2C
U 101 0101 55 u 111 0101 75 = 011 1101 3D
V 101 0110 56 v 111 0110 76 RETURN 000 1101 0D
W 101 0111 57 w 111 0111 77 LNFEED 000 1010 0A
X 101 1000 58 x 111 1000 78 0 011 0000 30
Y 101 1001 59 y 111 1001 79 0 011 0000 30
Z 101 1010 5A z 111 1010 7A 0 011 0000 30
EBCDIC Alphanumeric Code

The extended binary coded decimal interchange code (EBCDIC) is an 8-bit alphanumeric
code which has been extensively used by IBM in its mainframe applications.
EBCDIC Code
Char EBCDIC HEX Char EBCDIC HEX Char EBCDIC HEX
A 1100 0001 C1 P 1101 0111 D7 4 1111 0100 F4
B 1100 0010 C2 Q 1101 1000 D8 5 1111 0101 F5
C 1100 0011 C3 R 1101 1001 D9 6 1111 0110 F6
D 1100 0100 C4 S 1110 0010 E2 7 1111 0111 F7
E 1100 0101 C5 T 1110 0011 E3 8 1111 1000 F8
F 1100 0110 C6 U 1110 0100 E4 9 1111 10001 F9
G 1100 0111 C7 V 1110 0101 E5 blank ... ...
H 1100 1000 C8 W 1110 0110 E6 . ... ...
I 1100 1001 C9 X 1110 0111 E7 ( ... ...
J 1101 0001 Dl Y 1110 1000 E8 + ... ...
K 1101 0010 D2 Z 1110 1001 E9 $ ... ...
L 1101 0011 D3 0 1111 0000 F0 * ... ...
M 1101 0100 D4 1 1111 0001 F1 ) ... ...
N 1101 0101 D5 2 1111 0010 F2 - ... ...
O 1101 0110 D6 3 1111 0011 F3 / ... ...
1.10 SOLVED EXAMPLES

Example 1. Convert each binary number to the decimal:
(a) (11)2 (b) (.11)2
(1011)2 (.111)2
(10111)2 (.1011)2
(1111)2 (.10101)2
(11010111)2 (.0101)2
(1001)2 (.110)2
(c) (11.11)2
(1011.1011)2
(1111.0101)2
(11010111.110)2
(1001.10101)2
Solution. (a) (11)2 = 1 × 21 + 1 × 20
= 2 + 1 = 3
(1011)2 = 1 × 23 + 0 × 22 + 1 × 21 + 1 × 20
= 8 + 0 + 2 + 1 = 11
(10111)2 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 1 × 20
= 16 + 0 + 4 + 2 + 1 = 23
(1111)2 = 1 × 23 + 1 × 22 + 1 × 21 + 1 × 20
= 8 + 4 + 2 + 1 = 15
(11010111)2 = 1 × 27 + 1 × 26 + 0 × 25 + 1 × 24 + 0 × 23 + 1 × 22 +
1 × 21 + 1 × 20
= 128 + 64 + 0 + 16 + 0 + 4 + 2 + 1 = 215
(1001)2 = 1 × 23 + 0 × 22 + 0 × 21 + 1 × 20
= 8 + 0 + 0 + 1 = 9
(b) (.11)2 = 1 × 2–1 + 1 × 2–2
= .5 + .25 = (.75)10
(.111)2 = 1 × 2–1 + 1 × 2–2 + 1 × 2–3
= .5 + .25 + .125 = (.875)10
(.1011)2 = 1 × 2–1 + 0 × 2–2 + 1 × 2–3 + 1 × 2–4
= .5 + 0 + .125 + .0625 = (.6875)10
(.10101)2 = 1 × 2–1 + 0 × 2–2 + 1 × 2–3 + 0 × 2–4 + 1 × 2–5
= .5 + 0 + .125 + 0 + .03125 = (.65625)10
(.0101)2 = 0 × 2–1 + 1 × 2–2 + 0 × 2–3 + 1 × 2–4
= 0 + .25 + 0 + .0625 = (.3125)10
(.110)2 = 1 × 2–1 + 1 × 2–2 + 0 × 2–3
= .5 + .25 + 0 = (.75)10
(c) 11.11 = ?
From part (a) and part (b), we see that
11 = 3
11 = .75
Therefore, (11.11)2 = (3.75)10
1011.1011 = ?
(1011)2 = 11
(.1011)2 = .6875
Therefore, (1011.1011)2 = (.6875)10
1111.0101 = ?
(1111)2 = 15
(.0101)2 = .3125
Therefore, (1111.0101)2 = (15.3125)10
11010111.110 = ?
11010111 = 215
.110 = .75
(11010111.110)2 = (215.75)10
1001.10101 = ?
1001 = 9
.10101 = .65625
(1001.10101)2 = (9.65625)10
Example 2. How many bits are required to represent the following decimal numbers,
represent them in binary.
(I) (17)10 (II) (27)10 (III) (81)10 (IV) (112)10 (V) (215)10
Solution. (I) Let n bits required
n should be such that
2n > Given Number (N)

Therefore, 2n > 17
i.e., n > 5
Therefore, minimum number of bits required = 5.
(II) (27)10
The minimum number of bits required is given by
2n > N (given number)
2n > 27
i.e., n > 5
(III) (81)10
2n > N
2n > 81
i.e., n = 7
(IV) (112)10
The minimum number of required is given by
2n > N
2n > 112
i.e., n = 7
(V) (215)10
2n > 215
i.e., n = 8
Example 3. Convert the following numbers as indicated:

(a) decimal 225.225 to binary, octal and hexadecimal.
(b) binary 11010111.110 to decimal, octal and hexadecimal.
(c) octal 623.77 to decimal, binary and hexadecimal.
(d) hexadecimal 2AC5.D to decimal, octal and binary.
Solution. (a) 225.225 = (?)2
(.225)10 = (?)2
.225 × 2 = 0.450
.450 × 2 = 0.900
.900 × 2 = 1.800
.800 × 2 = 1.600
.600 × 2 = 1.200
.200 × 2 = 0.400
.400 × 2 = 0.800
.800 × 2 = 1.600
.600 × 2 = 1.200
Fraction part = 001110011
Therefore,
(225.225)10 = 11100001.001110011
(225.225)10 = (?)8
From the previous step we know the binary equivalent of decimal no. as 11100001.001110011.
For octal number, binary number is partitioned into group of three digit each starting
from right to left and replacing decimal equivalent of each group.
(225.225)10 = (341.163)8
(225.225)10 = (?)16
For hexadecimal number, instead of three four digits are grouped.
(225.225)10 = E1.398
(b) (11010111.110)2 = (?)10
From example 1.6.1
(11010111.110)2 = (215.75)10
(11010111.110)2 = (?)8
= 327
= 6
(11010111.110)2 = (327.6)8
(11010111.110)2 = (?)16
= D7
= C
(11010111.110)2 = (D7.C)16
(c) (623.77)8 = (?)2
623 = 110010011
.77 = 111111
(623.77)8 = (110010011.111111)2
(623.77)8 = (?)16
= 193
= FC
(623.77)8 = (193.FC)16
(623.77)8 = (?)10
623 = 6 × 82 + 2 × 81 + 3 × 80
= 384 + 16 + 3
= 403
.77 = 7 × 8–1 + 7 × 8–2
= 7 × .125 + 7 × .015625
= .875 + .109375
= 0.9843
(623.77)8 = (403.9843)10
(d) (2AC5.D)16 = (?)2
2AC5 = 0010101011000101
D = 1101
(2AC5.D)16 = (10101011000101.1101)2
(2AC5.D)16 = (?)8
(2AC5.D)16 = (25305.64)8
(2AC5.D)16 = (?)10
2AC5 = 2 × 163 + 10 × 162 + 12 × 161 + 5 × 160
= 2 × 4096 + 10 × 256 + 12 × 16 + 5 × 1
= 8192 + 2560 + 192 + 5
= 10949
D = 13 × 16–1
= 13 × .0625
= .8125
(2AC5.D)16 = (10949.8125)10
Example 4. Obtain the 9’s and 10’s complement of the following decimal numbers.
(i) 10000, (ii) 00000, (iii) 13469, (iv) 90099, (v) 09900
Solution. 9’s complement
10’s complement = 9’s complement + 1 (LSB)

Example 5. Perform the subtraction with the decimal numbers given using
(1) 10’s complement.
(2) 9’s complement.
Check the answer by straight subtraction
(a) 5249 – 320 (b) 3571 – 2101.
Solution. (a) Using 10’s complement. 10’s complement of 320
Therefore, 5249 – 320 = 5249

+9680
CY →
discarded
Result = 4929
Using 9’s complement. 9’s complement of 320
Therefore, 5249 – 320 = 5249

+ 9679
CY →
Result = 4929
By straight subtraction
Hence, results are same by each method.

(b) Using 10’s complement
10’s complement of 2101 =
Therefore, 3571 – 2101 = 3571

+7899
CY →
discarded
Result = 470
Using 9’s complement

9’s complement of 2101 = 7898
Therefore, 3571 – 2101 = 3571
+7898
CY →
By straight subtraction
Hence, results are same by each method.

Example 6. Obtain the 1’s and 2’s complement of the following binary numbers
(I) 11100101 (II) 0111000 (III) 1010101 (IV) 10000 (V) 00000.
Solution.
(I) 1’s complement = 00011010
2’s complement = 1’s complement + 1 = 00011011
(II) 1’s complement = 1000111
2’s complement = 1000111
1
(III) 1’s complement = 0101010

(IV) 1’s complement = 01111
(V) 1’s complement = 11111
1.11 EXERCISES
1. Write 9’s and 10’s complement of the following numbers:
+9090
–3578
+136.8
–136.28
2. (a) Convert the decimal integer’s +21 and –21 into 10’s complement and 9’s comple-
ment.
(b) Convert the above two numbers in binary and express them in six bit (total)
signed magnitude and 2’s complement.
3. (a) Find the decimal equivalent of the following binary numbers assuming signed
magnitude representation of the binary number:
(I) 001000 (II) 1111
(b) Write the procedure for the subtraction of two numbers with (r – 1)’s comple-
ment.
(c) Perform the subtraction with the following binary numbers using
2’s complement and 1’s complement respectively.
(I) 11010 – 1101 (II) 10010 – 10011
(d) Perform the subtraction with following decimal numbers using
10’s complement and 9’s complement respectively.
(I) 5294 – 749 (II) 27 – 289
4. Convert:
(I) (225.225)12 to Hexadecimal number.
(II) (2AC5.15)16 to Octal number.
5. Perform the following using 6’s complement:
(I) (126)7 + (42)7
(II) (126)7 – (42)7
6. Represent the following decimal numbers in two’s complement format:
(I) +5 (II) +25 (III) –5 (IV) –25 (V) –9
7. Represent the decimal numbers of question 6 in ones complement format.
8. Find the decimal equivalent of each of the following numbers assuming them to be
in two’s complement format.
(a) 1000 (b) 0110 (c) 10010 (d) 00110111
9. Convert the following octal numbers into equivalent decimal numbers:
(a) 237 (b) 0.75 (c) 237.75
10. Represent the following decimal numbers in sign-magnitude format:
(a) –11 (b) –7 (c) +12 (d) +25
2
CHAPTER
DIGITAL DESIGN FUNDAMENTALS—
BOOLEAN ALGEBRA AND LOGIC GATES
2.0 INTRODUCTORY CONCEPTS OF DIGITAL DESIGN

George Boole, in his work entitled ‘An Investigation of the Laws of Thought’, on which
are founded the Mathematical Theories of Logic and Probability (1854), introduced the
fundamental concepts of a two-values (binary) system called Boolean Algebra. This work was
later organized and systemized by Claude Shannon in ‘Symbolic Analysis of Relay and
Switching Circuits (1938)’. Digital design since that time has been pretty much standard and
advanced, following Boole’s and Shannon’s fundamentals, with added refinements here and
there as new knowledge has been unearthed and more exotic logic devices have been
developed.
Digital design is the field of study relating the adoptation of Logic concepts to the design
of recognizable, realizable, and reliable degital hardware.
When we begin study of logic, digital logic, binary systems, switching circuits, or any
other field of study that can be classified as being related to digital design, we must
concern ourselves with learning some philosophical premises from which we must launch
our studies. In order to reach a desirable theoretical, as well as conceptual, understanding
of digital design, you must grasp some fundamental definitions and insight giving con-
cepts.
Generally speaking, being involved in digital design is dealing in “LOGIC” a term that
certainly needs some definition. LOGIC, by definition, is a process of classifying information.
Information is intelligence related to ideas, meanings, and actions which can be processed or
transformed into other forms. For example, NEWS is information by virtue of the fact that
it is intelligence related to ACTIONS, be it good news or bad news. News can be heard, read,
seen or even felt or any combination of all four, indicating the possibility of its transformation
into different forms.
“BINARY LOGIC,” or two-valued logic, is a process of classifying information into two
classes. Traditionally, binary arguments, or that information which can be definitely classified
as two valued, has been delivered either TRUE or FALSE. Thus, the Boolean variable is
unlike the algebraic variables of the field of real numbers in that any Boolean variable can
take on only two values, the TRUE or the FALSE. Traditionally, it is standard to use the
shorthand symbols 1 for TRUE and 0 for the FALSE.
57
2.1 TRUTH TABLE

A Boolean variable can take on only two values, not an infinite number as, the variable
of the real number system, can. This basic difference allows us to illustrate all possible logic
conditions of a Boolean variable or a collection of Boolean variables using a finite tabuler
format called a ‘truth-table’. Further, the nontrivial decisions in digital design are based on
more than one-two valued variable. Thus, if an output is to be completely specified as a
function of two inputs, there are four input combinations that must be considered. If there
are three inputs, then eight combinations must be considered and from this we see that n
inputs will require 2n combinations to be considered.
A TRUTH-TABLE as suggested is a tabular or graphical technique for listing all possible
combinations of input variables, arguments, or whatever they may be called, in a vertical
order, listing each input combination one row at a time (Table 2.1). For example,
(i) Let we have a TV that operates with a switch. The TV, becomes on or off with the
switch on or off respectively.
Table 2.1(a)
I/P O/P
(Switch) (TV)
Off 0 Off 0
On 1 On 1
(ii) Let we have a TV that operates with two switches. When both the switches are
‘ON’ then only TV becomes ‘ON’ and in all other cases TV is ‘Off ’.
Table 2.1(b)
S.1 S.2 TV
0 0 0 OFF
0 1 0 OFF
1 0 0 OFF
1 1 1 ON
(iii) Let the TV operate with three switches. The condition now is that when at least
two switches are ‘ON’ the TV becomes ‘ON’ and in all other conditions ‘TV’ is ‘OFF’.
Table 2.1(c)
S.1 S.2 S.3 TV
0 0 0 0 OFF
0 0 1 0 OFF
0 1 0 0 OFF
0 1 1 1 ON
1 0 0 0 OFF
1 0 1 1 ON
1 1 0 1 ON
1 1 1 0 ON
Table 2.1(a) illustrates the use of a one variable T.T. and how the output or combined
interaction is manually listed to the right of each possible combination. Table 2.1(b) and Table
DIGITAL DESIGN FUNDAMENTALS—BOOLEAN ALGEBRA AND LOGIC GATES 59
2.1(c) show the standard form for two and three variable truth-tables. In review, what is
suggested here is that after all the input variables have been identified, and all the possible
combinations of these variables have been listed in the truth-table on the left, then each row
should be studied to determine what output or combined interaction is desired for that input
combination. Further, note that the input combinations are listed in ascending order, starting
with the binary equivalent of zero. The TRUTH-TABLE also allows us to establish or prove
Boolean identities without detailed mathematical proofs, as will be shown latter.
2.2 AXIOMATIC SYSTEMS AND BOOLEAN ALGEBRA

The AND, OR, and INVERTER functions make up a sufficient set to define a two valued
Boolean Algebra. Now, we introduce some formal treatment to this two-valued Boolean algebra.
Axiomatic Systems
Axiomatic systems are founded on some fundamental statements reffered to as ‘axioms’
and ‘postulates.’ As you delve deeper into the origin of axioms and postualtes, you find these
to be predicted on a set of undefined objects that are accepted on faith.
Axioms or postulates are statements that make up the framework from which new
systems can be developed. They are the basis from which theorems and the proofs of these
theorems are derived. For example, proofs are justified on the basis of a more primitive proof.
Thus, we use the statement—‘From this we justify this’. Again, we find a process that is based
on some point for which there exist no furhter primitive proofs. Hence, we need a starting
point and that starting point is a set of axioms or postulates.
Axioms are formulated by combining intelligence and empirical evidence and should have
some basic properties. These are:
1. They are statements about a set of undefined objects.
2. They must be consistent, that is, they must not be self-contradictory.
3. They should be simple but useful, that is, not lengthy or complex.
4. They should be independent, that is, these statements should not be interdependent.
The study of axiomatic systems related to logic motivated the creation of the set of
postulates known as the ‘HUNTINGTON POSTULATES’. E.V. Huntigton (1904) formulated
this set of postulates that have the basic properties described desirable, consistant, simple and
independent. These postulates as set forth can be used to evaluate proposed systems and
those systems that meet the criteria set forth by these posutlates become known as Huntigton
System. Further, once a proposed system meets the criteria set forth by the Huntington
Postulates, automatically all theorems and properties related to other Huntigton systems
become immediately applicable to the new system.
Thus, we propose a Boolean algebra and test it with the Huntigton postulates to deter-
mine its structure. We do this so that we can utilize the theorems and properities of other
Huntigton system for a new system that is defined over a set of voltge levels and hardware
operators. Boolean algebra, like other axiomatic systems, is based on several operators de-
fined over a set of undefined elements. A SET is any collection of elements having some
common property; and these elements need not be defined. The set of elements we will be
dealing with is {0, 1}. The 0 and 1, as far as we are concerned, are some special symbols. They
are simply some objects we are going to make some statements about. An operation (., +) is
defined as a rule defining the results of an operation on two elements of the set. Becuase these
operators operate on two elements, they are commonly reflected to as “binary operators”.
2.2.1 Huntington’s Postulates

1. A set of elements S is closed with respect to an operator if for every pair of elements
in S the operator specifies a unique result (element) which is also in the set S.
Or
For the operator + the result of A + B must be found in S if A and B are in S; and for
the operator the result of A. B must also be found in S if A and B are elements in S.
2. (a) There exists an element 0 in S such that for every A in S, A + 0 = A.
2. (b) There exists an element 1 in S such that for every A in S, A.1 = A.
3. (a) UV
A + B = B + A Commutative Law
3. (b) A. B = B . A W
4. (a) A . (B + C) = (A . B) + (A . C) UV
Distributive Law
4. (b) A + (B . C) = (A + B) . (A + C) W
5. For every element A in S, there exists an element A′ such that A. A = 0 and A + A = 1
6. There exist at least two elements A and B in S such that A is not equivalent to B.
Therefore, if we propose the following two values. Boolean algebra system, that is, if we
define the set S = {0, 1} and prescribe the rules for ., + and INVERTER as follows:
Rules for “ . ” Rules for “+”
. 0 1 A B A.B + 0 1 A B A+B
0 0 0 or 0 0 0 0 0 1 or 0 0 0
1 0 1 0 1 0 1 1 1 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
INVERT FUNCTION (COMPLEMENT)
A A′
0 1
1 0
and test our system with postulates, we find
1. Closure is obvious—no results other than the 0 and 1 are defined.
2. From the tables (a) 0 + 0 = 0 0 + 1 = 1 + 0 = 1
(b) 1.1 = 1 1.0 = 0.1 = 0
3. The commutative laws are obvious by the symmetry of the operator tables.
4. (a) The distributive law can be proven by a TRUTH-TABLE.
A B C B+C A.(B + C) A.B A.C (A.B) + (A.C)
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1
4. (b) Can be shown by a similar table.

5. From the INVERTER function table
(COMPLEMENT)
1. 1 = 1.0 = 0, 0. 0 = 0.1 = 0
1 + 1 = 1 + 0 = 1, 0 + 0 =0 +1=1
6. It is obvious that the set S = {0, 1} fulfills the minimum requirements of having at
least two elements where 0 ≠ 1.
From this study the following postulates can be listed below:
Table 2.2
Postulate 2 (a) A + 0 = A (b) A.1 = A Intersection Law
Postulate 3 (a) A + B = B + A (b) A.B = B.A Commutating Law
Postulate 4 (a) A(B + C) = AB + AC (b) A + BC = (A + B) (A + C) Distributive Law
Postulate 5 (a) A + A = 1 (b) A.A′ = 0 Complements Law
We have just established a two valued Boolean algebra having a set of two elements, 1
and 0, two binary operators with operation rules equivalent to the AND or OR operations, and
a complement operator equivalent to the NOT operator. Thus, Boolean algebra has been
defined in a formal mathematical manner and has been shown to be equivalent to the binary
logic. The presentation is helpful in understanding the application of Boolean algebra in gate
type circuits. The formal presentation is necessary for developing the theorems and proper-
ties of the algebraic system.
2.2.2 Basic Theorems and Properties of Boolean Algebra

Duality. The Huntington postulates have been listed in pairs and designated by part (a)
and (b) in Table 2.3. One part may be obtained from other if the binary operators (+ and .)
and identity elements (0 and 1) are interchanged. This important property of Boolean algebra
is called the duality principle. It states that every algebraic expression deducible from the
postulates of Boolean algebra remain valid if the operators and identity elements are inter-
changed. In a two valued Boolean algebra, the identity elements and the elements of the set
are same: 1 and 0.
Basic Theorems. Table 2.3 lists six theorems of Boolean algebra. The theorems, like the
postulates, are listed in pairs; each relation is the dual of the one paired with it. The
postulates are basic axioms of the algebraic structure and need no proof. The theorems must
be proven from the postulates.
Table 2.3 Theorems of Boolean Algebra
Theorem
1. (a) A + A = A (b) A.A = A Tautology Law
2. (a) A + 1 = 1 (b) A.0 = 0 Union Law
3. (A′)′ = A Involution Law
4. (a) A + (B + C) = (A + B) + C (b) A.(B.C) = (A.B).C Associative Law
5. (a) (A + B)′ = A′B′ (b) (A.B)′ = A′ + B′ De Morgan’s Law
6. (a) A + AB = A (b) A(A + B) = A Absorption Law

7. (a) A + A′B = A + B (b) A(A′ + B) = AB
8. (a) AB + AB′ = A (b) (A + B) (A + B′) = A Logical adjancy
9. (a) AB + A′C + BC = AB + A′C (b) (A + B) (A′ + C) (B + C) = (A + B)
Consensus Law
The proofs of the theorem are presented below. At the right is listed the number of
postulate which justifies each step of proof.
Theorem 1(a) A+A = A
A+A = (A + A).1 by postulate 2(b)
= (A + A) (A + A′) 5(a)
= A + AA′ 4(b)
= A+0 5(b)
= A 2(a)
Theorem 1(b) A.A = A.
A.A = A.A + 0 by postulate 2(a)
= A.A + A.A′ 5(b)
= A(A + A′) 4(a)
= A.1 5(a)
= A 2(b)
Note that theorem 1(b) is the dual of theorem 1(a) and that each step the proof in part
(b) is the dual of part (a). Any dual theorem can be similarly derived from the proof of its
corresponding pair.
Theorem 2(a) A+A = 1
A + 1 = 1.(A + 1) by postulate 2(b)
= (A + A′) (A + 1) 5(a)
= A + A′.1 4(b)
= A + A′ 2(b)
= 1 5(a)
Theorem 2(b) A.0 = 0 by duality.
Theorem 3. (A′)′ = A From postulate 5, we have
A + A′ = 1 and A.A′ = 0, which defines the complement of A. The complement of A′ is
A and is also (A′)′. Therefore, since the complement is unique, we have that (A′)′ = A.
Theorem 4(a) A + (B + C) = (A + B) + C
We can prove this by perfect induction method shown in table 2.4 below:
Table 2.4
A B C (B + C) A + (B + C) (A + B) (A + B) + C
0 0 0 0 0 0 0
0 0 1 1 1 0 1
0 1 0 1 1 1 1
0 1 1 1 1 1 1
(Contd.)...
A B C (B + C) A + (B + C) (A + B) (A + B) + C
1 0 0 0 1 1 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1
We can observe that A + (B + C) = (A + B) + C
*Theorem 4(b)—can be proved in similar fashion.
*Theorem 5(a) and 5(b)—can also be proved by perfect induction method.
Theorem 6(a) A + AB = A
A + AB = A (1 + B)
= A (1)
= A
6(b) A.(A + B) = A By duality.
Theorem 7(a) A + A′B = A + B
A + A′B = A.1 + A′B
= A (B + B′) + A′B
= AB + AB′ + A′B
= AB + AB + AB′ + A′B
= A(B + B′) + B(A + A′)
= A + B.
7(b) A.(A′ + B) = A.B By duality.
Theorem 8(a) AB + AB′ = A
AB + AB′ = A(B +B′)
= A
8(b) (A + B) . (A + B′) = A By duality.
Theorem 9(a) AB + A′C + BC = AB + A′C
AB + A′C + BC = AB + A′C + BC(A + A′)
= AB + A′C + ABC + A′BC
= AB (1 + C) + A′C (1 + B)
= AB + A′C
9(b) (A + B) (A′ + C) (B + C) = (A + B) (A′ + C) By duality.
2.3 BOOLEAN FUNCTIONS

A binary variable can take the value of 0 or 1. A Boolean function is an expression formed
with binary variable, the two binary operators OR and AND, the unary operator NOT,
parantheses and an equal sign. For a given value of the variables, the function can be either
0 or 1. Consider, for example, the Boolean function
F 1 = xy′z
*The proof of 4(b), 5(a) and 5(b) is left as an exercise for the reader.
The function F is equal to 1 when x = 1, y = 0 and z = 1; otherwise F1 = 0. This is an example

of a Boolean function represented as an algebraic expression. A Boolean function may also be
represented in a truth table. To represent a function in a truth table, we need a list of the 2n
combinations of 1’s and 0’s of n binary variables, and a column showing the combinations for
which the function is equal to 1 or 0 as discussed previously. As shown in Table 2.5, there
are eight possible distinct combination for assigning bits to three variables. The table 2.5 shows
that the function F1 is euqal to 1 only when x = 1, y = 0 and z = 1 and equal to 0 otherwise.
Consider now the function
F 2 = x′y′z + x′yz + xy′
F2 = 1 if x = 0, y = 0, z = 1 or
x = 0, y = 1, z = 1 or
x = 1, y = 0, z = 0 or
x = 1, y = 0, z = 1
F2 = 0, otherwise.
Table 2.5
x y z F1 F2 F3
0 0 0 0 0 0
0 0 1 0 1 1
0 1 0 0 0 0
0 1 1 0 1 1
1 0 0 0 1 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 0 0 0
The number of rows in the table is 2n, where n is the number of binary variables in the
function.
The question now arises, Is an algebraic expression of a given Boolean function unique?
Or, is it possible to find two algebraic expressions that specify the same function? The answer
is yes. Consider for example a third function.
F 3 = xy′ + x′z
F3 = 1 if x = 1, y = 0, z = 0 or
x = 1, y = 0, z = 1 or
x = 0, y = 0, z = 1 or
x = 0, y = 1, z = 1
F3 = 0, otherwise.
From table, we find that F3 is same as F2 since both have identical 1’s and 0’s for each
combination of values of the three binary variables. In general, two functions of n binary
variables are said to be equal if they have the same value for all possible 2n combinations of
the n variables.
As a matter of fact, the manipulation of Boolean algebra is applied mostly to the problem
of finding simpler expressions for the same function.
2.3.1 Transformation of Boolean Function into Logic Diagram

A Boolean function may be transformed from an algebraic expresion into a logic diagram
composed of AND, OR and NOT gates. Now we shall implement the three functions discussed
above as shown in Fig. 2.1.
• Here we are using inverters (NOT gates) for complementing a single variable. In
general however, it is assumed that we have both the normal and complement
forms available.
• There is an AND gate for each product term in the expression.
• An OR gate is used to combine two or more terms.
X
x
z F1 Y
Z
y
(a)
F2
(b)
x
y
F3
z
(c)
Fig. 2.1 (a, b, c)
From the Fig. 2.1, it is obvious that the implementation of F3 requires fewer gates and
fewer inputs than F2. Since F3 and F2 are equal Boolean functions, it is more economical to
implement F3 form than the F2 form. To find simpler circuits, we must know how to manipu-
late Boolean functions to obtain equal and simpler expression. These simplification (or mini-
mization) techniques will be discuss in detail in next chapter.
2.3.2 Complement of a Function

The complement of a function F is F′ and is obtained from an interchange of 0’s for 1’s
and 1’s for 0’s in the value of F. The complement of a function may be derived algebraically
through De Morgan’s theorem. De Morgan’s theorem can be extended to three or more
variables. The three-variable form of the De Morgan’s theorem is derived below:
(A + B + C)′ = (A + X)′ Let B + C = X
= A′X′ by theorem 5(a)
= A′.(B + C)′ substituting B + C = X
= A′.(B′C′) theorem 5(a)
= A′B′C′ theorem 4(a)
This theorem can be generalized as

(A + B + C + D + ... F)′ = A′B′C′D′....F′
and its DUAL
(ABCD .... F)′ = A′ + B′ + C′ + D′ + ... + F′
The generalized form of De Morgan’s theorem states that the complement of a function
is obtained by interchaning AND and OR operators and complementing each literal.
Example. Determine the complements of the following function:
F 1 = AB′ + C′D
Solution. F 1 = AB′ + C′D
F 1 ′ = (AB′ + C′D)′
= (AB′)′ . (C′D)′
= (A′ + B) . (C + D′)
2.4 REPRESENTATION OF BOOLEAN FUNCTIONS

Boolean functions (logical functions) are generally expressed in terms of logical vari-
ables. Values taken on by the logical functions and logical variables are in the binary form.
Any logical variable can take on only one of the two values 0 and 1 or any logical variable
(binary variable) may appear either in its normal form (A) or in its complemented form (A′).
As we will see shortly latter that an arbitrary logic function can be expressed in the
following forms:
(i) Sum of Products (SOP)
(ii) Product of Sums (POS)
Product Term
The AND function is reffered to as product. The logical product of several variables on
which a function depends is considered to be a product term. The variables in a product term
can appear either in complemented or uncomplemented (normal) form. For example AB′C is
a product form.
Sum Term
The OR function is generally used to refer a sum. The logical sum of several variables
on which a function depends is considered to be a sum term. Variables in a sum term also
can appear either in normal or complemented form. For example A + B + C′, is a sum
term.
Sum of Products (SOP)

The logic sum of two or more product terms is called a ‘sum of product’ expression. It
is basically an OR operation of AND operated variables such as F = A′B + B′C + A′BC.
Product of Sums (POS)

The logical product of two or more sum terms is called a ‘product of sum’ expression. It is
basically an AND operation of OR operated variables such as F = (A′ + B). (B′ + C) . (A′ + B + C).
2.4.1 Minterm and Maxterm Realization

Consider two binary variables A and B combined with an AND operation. Since each
variable may appear in either form (normal or complemented), there are four combinations,
that are possible—AB, A′B, AB′, A′B′.
Each of these four AND terms represent one of the four distinct combinations and is
called a minterm, or a standard product or fundamental product.
Now consider three variable—A, B and C. For a three variable function there are 8
minterms as shown in Table 2.6(a). (Since there are 8 combinations possible). The binary
numbers from 0 to 7 are listed under three varibles. Each minterm is obtained from an AND
term of the three variables, with each variable being primed (complemented form) if the
corresponding bit of the binary number is a 0 and unprimed (normal form) if a 1. The
symbol is mj, where j denotes the decimal equivalent of the binary number of the minterm
disignated.
In a similar manner, n variables can be combined to form 2n minterms. The 2n different
minterms may be determined by a method similar to the one shown in table for three variables.
Similarly n variables forming an OR term, with each variable being primed or unprimed,
provide 2n possible combinations, called maxterms or standard sums.
Each maxterm is obtained from an OR term of the n variables, with each variable being
unprimed if the corresponding bit is a 0 and primed if a 1.
It is intersting to note that each maxterm is the complement of its corresponding
minterm and vice versa.
Now we have reached to a level where we are able to understand two very important
properties of Boolean algebra through an example.
Table 2.6(a) Minterm and Maxterm for three binary variables
MINTERMS MAXTERMS
Decimal Eqt. A B C Term Designation Term Designation
0 0 0 0 A′B′C′ m0 A+B+C M0
1 0 0 1 A′B′C m1 A + B + C′ M1
2 0 1 0 A′BC′ m2 A + B′ + C M2
3 0 1 1 A′BC m3 A + B′ + C′ M3
4 1 0 0 AB′C′ m4 A′ + B + C M4
5 1 0 1 AB′C m5 A′ + B + C′ M5
6 1 1 0 ABC′ m6 A′ + B′ + C M6
7 1 1 1 ABC m7 A′ + B′ + C′ M7
Let we have a TV that is connected with three switches. TV becomes ‘ON’ only when
atleast two of the three switches are ‘ON’ (or high) and in all other conditions TV is ‘OFF’
(or low). The example is same as we have already discussed in section (2.1) TT.
Let the three switches are represented by three variable A, B and C. The output of TV
is represented by F. Since there are three switches (three variables), there are 8 distinct
combinations possible that is shown in TT. (Table 2.6(b)).
Table 2.6(b)
SWITCHES TV (o/p) HIGH (ON) → 1
A B C F LOW (OFF) → 0.
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
The TV becomes ‘ON’ at four combinations. These are 011, 101, 110 and 111. We can say
that F is determined by expressing the combinations A′BC, AB′C, ABC′ and ABC. Since each
of these minterms result in F = 1, we should have
F = A′BC + AB′C + ABC′ + ABC
= m3 + m5 + m6 + m7.
This demonstrates an important property of Boolean algebra that ‘Any Boolean function
can be expressed as sum of minterms or as ‘Sum of product’. However, there is no guarantee
that this SOP expression will be a minimal expression. In other words, SOP expressions are
likely to have reduandancies that lead to systems which requires more hardware that is
necessary. This is where the role of theorems and other reduction techniques come into play
as will be shown in next chapter.
As mentioned, any TRUTH-TABLE INPUT/OUTPUT specifications can be expressed in
a SOP expression. To facilitate this a shorthand symbology has been developed to specify such
expressions. This is done by giving each row (MINTERM) in the TRUTH-TABLE a decimal
number that is equivalent to the binary code of that row, and specifying the expression thus:
F = Σ(m3, m5, m6, m7)
which reads: F = the sum-of-products of MINTERMS 3, 5, 6 and 7. This shorthand notation
can be furhter shortend by the following acceptable symbology:
F = Σ(3, 5, 6, 7)
Expression such as these serve as great aids to the simplification process, as shown in
next chapter.
Now, continuing with the same example, consider the complement of Boolean function
that can be read from Truth-table by forming a minterm for each combination that produces
0 in the function and by 0Ring
F′ = A′B′C′ + A′B′C + A′BC′ + AB′C′
Now, if we take the complement of F′, we get F.
F = (A + B + C) . (A + B + C′) . (A + B′ + C) (A′ + B + C)
= M0 M1 M2 M4
This demonstrates a second important property of the Boolean algebra that ‘Any Boolean
function can be expressed as product-of-maxterms or as product of sums’. The procedure for

obtaining the product of maxterms directly from Truth-table is as; Form a maxterm for
each combination of the variables that produces a 0 in the function, and then form the AND
of all those functions. Output will be equal to F because in case of maxterms 0 is unprimed.
The shortend symbology for POS expressions is as follows—
F = Π(M0, M1, M2, M4)
or F = Π(0, 1, 2, 4)
Boolean functions expressed as sum of minterms (sum of product terms) SOP or product
of maxterms, (Product of sum terms) POS are said to be in CANONICAL form or STANDARD
form.
2.4.2 Standard Forms

We have seen that for n binary variables, we can obtain 2n distinct mintersms, and that
any Boolean function can be expressed as a sum of minterms or product of maxterms. It is
sometimes convenient to express the Boolean function in one of its standard form (SOP or
POS). If not in this form, it can me made as follows:
1. Sum of Product. First we expand the expression into a sum of AND terms. Each
term is then inspected to see if it contains all the variable. If it misses one or more
variables, it is ANDed with an expression such as A + A′, where A is one of the missing
variables.
Example 1. Express the Boolean function F = x + y′z in a sum of product (sum of
minterms) form.
Solution. The function has three variables x, y and z. The first term x is missing two
variables; therefore
x = x (y + y′) = xy + xy
This is still missing one variable:
x = xy (z + z′) + xy′ (z + z′)
= xyz + xyz′ + xy′z + xy′z′
The second term y′z is missing one variable:
y′z = y′z (x + x′) = xy′z + x′y′z
Combining all terms, we have
F = x + y′z = xyz + xyz′ + xy′z + xy′z′ + xy′z + x′y′z
But xy′z appears twice, and according to theorem 1 (A + A = A), it is possible to remove
one of them. Rearranging the min terms in ascending order, we have:
F = x′y′z + xy′z′ + xy′z + xyz′ + xyz
= m1 + m4 + m5 + m6 + m7.
F(x, y, z) = Σ(1, 4, 5, 6, 7)
An alternative method for driving product terms (minterms) is to make a T.T. directly
from function. F = x + y′z. From T.T., we can see directly five minterms where the value of
function is equal to 1. Thus,
F(x, y, z) = Σ(1, 4, 5, 6, 7)
x y z F = x + y′z
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
2. Product of Sums. To express the Boolean function as product of sums, it must first
be brought into a form of OR terms. This may be done by using the distributive law A + BC
= (A + B) . (A + C). Then any missing variable A in each OR term is 0Red with AA′.
Example 2. Express the Boolean function F = AB + A′C in a product of sum (product
of mixterm) form.
Solution. First convert the function into OR terms using distributive law.
F = AB + A′C = (AB + A′) (AB + C)
= (A + A′) (B + A′) (A + C) (B + C)
= (A′ + B) (A + C) (B + C)
The function has three variables A, B and C. Each OR term is missing one variable
therefore:
A′ + B = A′ + B + CC′ = (A′ + B + C) (A′ + B + C′)
A + C = A + C + BB′ = (A + B + C) (A + B′ + C)
B + C = B + C + AA′ = (A + B + C) (A′ + B + C)
Combining all these terms and removing those that appear more than once.
F = (A + B + C) (A + B′ + C) (A′ + B + C) (A′ + B + C′)
M0 M2 M4 M5
F(x, y, z) = Π(0, 2, 4, 5)
An alternative method for deriving sum terms (maxterms) again is to make a TT directly
from function.
F = AB + A′C
From TT, we can see directly four maxterms where the value of function is equal to 0.
Thus, F(A, B, C) = Π(0, 2, 4, 5)
A B C F = AB + A′C
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
(Contd.)...
A B C F = AB + A′C
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
2.4.3 Conversion between Standard Forms

Consider the table 2.6(b) shown in section 2.4.1 to help you establish the relationship
between the MAXTERM and MINTERM numbers.
From table we see that mj = M j
An interesting point can be made in relationship between MAXTERM lists and MINTERMS
lists. The subscript number of the terms in the MAXTERM list correspond to the same
subscript numbers for MINTERMS that are not included in the MINTERM list. From this we
can say the following:
Π (Set of MAXTERM numbers)
We know that the function derived from this list will yield precisely the same result as
the following:
Σ(set of MINTERMS numbers that are not included in the MAXTERM list)
For example:
Given, F(A, B, C) = Π(0, 1, 4, 6)
We know immediately that
F(A, B, C) = Σ(2, 3, 5, 7)
2.5 LOGIC GATES

We have seen that the foundation of logic design is seated in a well defined axiomatic
system called Boolean algebra, which was shown to be what is known as a “Huntington system”.
In this axiomatic system the definition of AND and OR operators or functions was set forth and
these were found to be well defined operators having certain properties that allow us to extend
their definition to Hardware applications. These AND and OR operators, sometimes reffered to
as connectives, actually suggest a function that can be emulated by some H/W logic device. The
Hardware logic devices just mentioned are commonly reffered to as “gates”.
Keep in mind that the usage of “gate” refers to an actual piece of Hardware where
“function” or “operation” refers to a logic operator AND. On the other hand, when we refer
to a “gate” we are reffering directly to a piece of hardware called a gate. The main point to
remember is ‘Don’t confuse gates with logic operators’.
2.5.1 Positive and Negative Logic Designation

The binary signals at the inputs or outputs of any gate can have one of the two values
except during transition. One signal levels represents logic 1 and the other logic 0. Since
two signal values are assigned two logic values, there exist two different assignments of
signals to logic.
Logics 1 and 0 are generally represented by different voltage levels. Consider the two
values of a binary signal as shown in Fig. 2.2. One value must be higher than the other since
the two values must be different in order to distinguish between them. We designate the
higher voltage level by H and lower voltage level by L. There are two choices for logic values
assignment. Choosing the high-level (H) to represent logic 1 as shown in (a) defines a positive
logic system. Choosing the low level L to represent logic-1 as shown in (b), defines a negative
logic system.
Logic Signal Logic Signal
value value value value
1 H 0 H
0 L 1 L
(a) Positive logic (b) Negative logic
Fig. 2.2
The terms positive and negative are somewhat misleading since both signal values may
be positive or both may be negative. Therefore, it is not signal polarity that determines the
type of logic, but rather the assignment of logic values according to the relative amplitudes
of the signals.
The effect of changing from one logic designation to the other equivalent to complement-
ing the logic function because of the principle of duality of Boolean algebra.
2.5.2 Gate Definition

A ‘gate’ is defined as a multi-input (> 2) hardware device that has a two-level output. The
output level (1–H/0–L) of the gate is a strict and repeatable function of the two-level
(1–H/0–L) combinations applied to its inputs. Fig. 2.3 shows a general model of a gate.
n inputs, each of Two level output that

which can take on Gate is a strict function of
one of two levels (Hardware) two-level input
(HIGH/LOW) combinations
Fig. 2.3 The general model of a gate

The term “logic” is usually used to refer to a decision making process. A logic gate, then,
is a circuit that can decide to say yes or no at the output based upon inputs.
We apply voltage as the input to any gate, therefore the Boolean (logic) 0 and 1 do not
represent actual number but instead represent the state of a voltage variable or what is called
its logic level. Sometimes logic 0 and logic 1 may be called as shown in table 2.7.
Table 2.7
Logic 0 Logic 1
False True
Off On
Low High
No Yes
Open switch Close switch
2.5.3 The AND Gate

The AND gate is sometimes called the “all or nothing gate”. To show the AND gate we
use the logic symbol in Fig. 2.4(a). This is the standard symbol to memorize and use from
now on for AND gates.
INPUTS
SWITCHES B A OUTPUT
A
Inputs Y output
B A
Y
B
(a)
(b)
Fig. 2.4 (a) AND Gate logic symbol. (b) Practical AND gate circuit
Now, let us consider Fig. 2.4(b). The AND gate in this figure is connnected to input
switches A and B. The output indicator is an LED. If a low voltage (Ground, GND) appears
at inputs, A and B, then the output LED is not glow. This situation is illustrated in table 2.8.
Line 1 indicates that if the inputs are binary 0 and 0, then the output will be binary 0. Notice
that only binary 1s at both A and B will produce a binary 1 at the output.
Table 2.8 AND Truth Table
INPUTS OUTPUTS
A B Y
Switch Binary Switch Binary Light Binary
Voltage Voltage
Low 0 Low 0 No 0
Low 0 High 1 No 0
High 1 Low 0 No 0
High 1 High 1 Yes 1
It is a +5V compared to GND appearing at
A, B, or Y that is called a binary 1 or a HIGH Boolean AND Symbol
voltage. A binary 0, or Low voltage, is defined Expression
A.B=Y
as a GND voltage (near 0V compared to GND)
appearing at A, B or Y. We are using positive
Logic A
logic because it takes a positive +5V to produce Symbol Y
B
what we call a binary 1.
The truth table is said to discribe the AND
A B Y
function. The unique output from the AND gate 0 0 0
is a HIGH only when all inputs are HIGH. Truth
0 1 0
Table
1 0 0
Fig. 2.4 (c) shows the ways to express that 1 1 1
input A is ANDed with input B to produce out-
put Y.
Fig. 2.4 (c)
Pulsed Operation
In many applications, the inputs to a gate may be voltage that change with time between
the two logic levels and are called as pulsed waveforms. In studying the pulsed operation of
an AND gate, we consider the inputs with respect to each other in order to determine the
output level at any given time. Following example illustrates this operation:
Example. Determine the output Y from the AND gate for the given input waveform
shown in Fig. 2.5.
INPUTS
0 0 1 1
A
t1 t2 t3 t4 B Y →?
Fig. 2.5
Solution. The output of an AND gate is determined by realizing that it will be high only
when both inputs are high at the same time. For the inputs the outputs is high only during
t3 period. In remaining times, the outputs is 0 as shown in Fig. 2.6.
0 0 1 0
OUTPUT Y →
t1 t2 t3 t4
Fig. 2.6
2.5.4 The OR Gate

The OR gate is sometimes called the “any or all gate”. To show the OR gate we use the
logical symbol in Fig. 2.7(a).
INPUTS
B A SWITCHES OUTPUT
A
INPUTS Y output
B A
Y
B
(a)
(b)
Fig. 2.7 (a) OR gate logic symbol. (b) Practical OR gate circuit
A truth-table for the ‘OR’ gate is shown below according to Fig. 2.7(b). The truth-table
lists the switch and light conditions for the OR gate. The unique output from the OR gate
is a LOW only when all inputs are low. The output column in Table (2.9) shows that only the
first line generates a 0 while all others are 1.
Table 2.9
INPUTS OUTPUTS
A B Y
Switch Binary Switch Binary Light Binary
Low 0 Low 0 No 0
Low 0 High 1 Yes 1
High 1 Low 0 Yes 1
High 1 High 1 Yes 1
Fig. 2.7(c) shows the ways to express that input A is ORed with input B to produce
output Y.
Boolean OR Symbol
Expression ↑
A+B=Y
Logic A
Symbol Y
B
A B Y
0 0 0
Truth
0 1 1
Table
1 0 1
1 1 1
Fig. 2.7 (c)

Example 1. Determine the output Y from the OR gate for the given input waveform
shown in Fig. 2.8.
INPUTS
0 0 1
A
t1 t2 t3 B Y →?
1 0 1
Fig. 2.8
Solution. The output of an OR gate is determined by realizing that it will be low only
when both inputs are low at the same time. For the inputs the outputs is low only during
period t2. In remaining time output is 1 as shown in Fig. 2.9.
t1 t2 t3
OUTPUT Y →
1 0 1
Fig. 2.9
We are now familiar with AND and OR gates. At this stage, to illustrate at least in part
how a word statement can be formulated into a mathematical statement (Boolean expression)
and then to hardware network, consider the following example:
Example 2. Utkarsha will go to school if Anand and Sawan go to school, or Anand and
Ayush go to school.
Solution. → This statement can be symbolized as a Boolean expression as follows:
U IF A AND S
Utkarsha - U
Anand - A
or U = (A . S) + (A . AY) Sawan - S
¯ ¯ ¯ Ayush - AY
AND OR AND
Symbol Symbol Symbol
The next step is to transform this Boolean expression into a Hardware network and this
is where AND and OR gates are used.
A A.S
1
S
(A.S) + (A.AY)
3 U
A.AY
2
AY
The output of gate 1 is high only if both the inputs A and S are high (mean both Anand
and Sawan go to school). This is the first condition for Utkarsha to go to school.
The output of gate 2 is high only if both the inputs A and AY are high (means both Anand
and Ayush go to school). This is the second condition for Utkarsha to go to school.
According to example atleast one condition must be fullfilled in order that Utkarsha goes
to school. The output of gate 3 is high when any of the input to gate 3 is high means at least
one condition is fulfilled or both the inputs to gate 3 are high means both the conditions are
fulfilled.
The example also demonstrates that Anand has to go to school in any condition otherwise
Utkarsha will not go to school.
2.5.5 The Inverter and Buffer

Since an Inverter is a single input device, it performs no logic interaction function
between two variables, and to say that merely changing a voltage level constitute a logic
operation would be misleading. Therefore we define it as an Inverter function rather than a
logic operator like the AND and OR operators. The NOT circuit performs the basic logical
function called inversion or complementation. That is why, it is also known as Inverter. The
NOT circuit has only input and one ouput. The purpose of this gate is to give an output that
is not the same as the input. When a HIGH level is applied to an inverter, a LOW level appears
at its output and vice versa. The logic symbol for the inverter is shown in Fig. 2.5.5(a).
If we were to put in a logic at 1 and input
INPUT A Y OUTPUT
A in Fig. 2.10(a), we would get out the oppo-
site, or a logical 0, at output Y. Y = A¢ or A
Fig. 2.10 (a) A logic symbol and Boolean
expression for an inverter
The truth-table for the inverter is shown in Fig. 2.10(b). If the voltage at the input of
the inverter is LOW, then the output voltage is HIGH, if the input voltage is HIGH, then the
output is LOW. We can say that output is always negated. The terms “negated”, “comple-
mented” and “inverted”, then mean the same things.
INPUT OUTPUT
A B
Voltages Binary Voltages Binary
LOW 0 HIGH 1
HIGH 1 LOW 0
Fig. 2.10 (b) Truth-table for an inverter
Now consider the logic diagram as shown in Fig. 2.10(c), that shows an arrangement
where input A is run through two inverters. Input A is first inverted to produce a “not A” (A)
and then inverted a second time for “double not A” (A) . In terms of binary digits, we find that
when the input 1 is inverted twice, we end up with original digit. Therefore, we find A = A.
INPUT A OUTPUT
A A
INVERT INVERT
Logical 1 Logical 0 Logical 1
⇒A = A
Fig. 2.10 (c) Effect of double inverting
The symbol shown in figure 2.11(a) is that of a non-inverting buffer/driver. A buffer
produces the transfer function but does not produce any logical operation, since the binary
value of the ouput is equal to the binary value of the input. The circuit is used merely for
power amplification of the signal and is equivalent to two inverters connected in cascade. Fig.
2.11(b) shows the T.T. for the buffer.
INPUT OUTPUT
A A
Fig. 2.11 (a) Non-inverting buffer/driver logic symbol.
INPUT OUTPUT
A B
Voltages Binary Voltage Binary
HIGH 1 HIGH 1
LOW 0 LOW 0
Fig. 2.11 (b) Truth table for buffer
Example. Determine the output Y from the inverter for the given input waveform shown
in Fig. 2.12.
INPUTS
0 1 0 1 1 1 0 A
Y →?
t1 t2 t3 t4 t5 t6 t7
Fig. 2.12
Solution. The output of an Inverter is determined by realizing that it will be high when
input is low and it will be low when input is high as shown in Fig. 2.13.
1 0 1 0 0 0 1
OUTPUT Y →
t1 t2 t3 t4 t5 t6 t7
Fig. 2.13
2.5.6 Other Gates and Their Functions

The AND, OR, and the inverter are the three basic circuits that make up all digital
circuits. Now, it should prove interesting to examine the other 14 possible ouput specification
(except AND and OR) for an arbitrary two-input gate.
Consider Table 2.10.
Table 2.10: Input/Output specifications for the 16 possible outputs derived from
two-input gates
A B GND F 1 F2 F3 F4 F5 F6 F7 F8 F9 F 10 F11 F 12 F 13 F 14 +V
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
↓ ↓ ↓ ↓ ↓ ↓
N E N A E
O X A N X O
R O N D N R
R D O
R
Scanning the table for gates that exhibit the Boolean AND and OR operator, we see that
F1 (NOR), F7 (NAND), F8 (AND) and F14 (OR) are the only outputs from gates which manifest
the AND and OR operators. We shall see very shortly that both NAND and NOR gates can
be used as AND and OR gates. Because of this, they are found in integrated circuit form. All
the rest are more complex and deemed unuseful for AND/OR implementation and are not
normally found in gate form, with two exceptions. They are F6 and F9. F6 is the Input/output
specification for a gate called the EXCLUSIVE OR gate and F9 is the specification for the
COINCIDENCE, EQUIVALENCE, or EXNOR gate, also referred to as an EXCLUSIVE NOR.
2.5.7 Universal Gates

NAND and NOR gates. The NAND and NOR gates are widely used and are readily
available in most integrated circuits. A major reason for the widespread use of these gates
is that they are both UNIVERSAL gates, universal in the sense that both can be used for
AND operators, OR operators, as well as Inverter. Thus, we see that a complex digital system
can be completely synthesized using only NAND gates or NOR gates.
The NAND Gate. The NAND gate is a NOT AND, or an inverted AND function. The
standard logic symbol for the NAND gate is shown in Fig. 2.14(a). The little invert bubble
(small circle) on the right end of the symbol means to invert the output of AND.
INPUTS OUTPUTS
A A A.B
Y (A.B)¢
B B
(a) (b)
Fig. 2.14 (a) NAND gate logic symbol (b) A Boolean expression for the output of a NAND gate
Figure 2.14(b) shows a separate AND gate and inverter being used to produce the NAND
logic function. Also notice that the Boolean expression for the AND gate, (A.B) and the NAND
(A.B)′ are shown on the logic diagram of Fig. 2.14(b).
The truth-table for the NAND gate is shown in Fig. 2.14(c). The truth-table for the
NAND gate is developed by inverting the output of the AND gate. ‘The unique output from
the NAND gate is a LOW only when all inputs are HIGH.
INPUT OUTPUT
A B AND NAND
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
Fig. 2.14 (c) Truth-table for AND and NAND gates

Fig. 2.14 (d) shows the ways to express that input A is NANDed with input B yielding
output Y.
NOT Symbol or AB = Y
Boolean
Expression A . B = Y
AND Symbol or (AB)¢ = Y
Logic A
Symbol Y
B
A B Y
0 0 1
Truth
0 1 1
Table
1 0 1
1 1 0
Fig. 2.14 (d)

Example 1. Determine the output Y from the NAND gate from the given input waveform
shown in Fig. 2.15.
INPUTS
0 1 0 1
A OUTPUT
Y
t1 t2 t3 t4 B ?
0 1 0 0
Fig. 2.15
Solution. The output of NAND gate is determined by realizing that it will be low only
when both the inputs are high and in all other conditions it will be high. The ouput Y is
shown in Fig. 2.16.
t1 t2 t3 t4
OUTPUT Y →
1 0 1 1
Fig. 2.16
The NAND gate as a UNIVERSAL Gate
The chart in Fig. 2.17 shows how would you wire NAND gates to create any of the other
basic logic functions. The logic function to be performed is listed in the left column of the
table; the customary symbol for that function is listed in the center column. In the right
column, is a symbol diagram of how NAND gates would be wired to perform the logic
function.
Logic Symbol Circuit using NAND gates only

Function
A
Inverter A A¢ A¢
A
A
AND A.B B
B A.B
A
A
OR A+B
B A+B
B
Fig. 2.17
The NOR gate. The NOR gate is actually a NOT OR gate or an inverted OR function.
The standard logic symbol for the NOR gate is shown in Fig. 2.18(a).
INPUTS OUTPUTS
A A A+B
Y (A + B)¢
B B
(a) (b)
Fig. 2.18 (a) NOR gate logic symbol (b) Boolean expression for the output of NOR gate.
Note that the NOR symbol is an OR symbol with a small invert bubble on the right side.
The NOR function is being performed by an OR gate and an inverter in Fig. 2.18(b). The
Boolean function for the OR function is shown (A + B), the Boolean expression for the final
NOR function is (A + B)′.
The truth-table for the NOR gate is shown in Fig. 2.18(c). Notice that the NOR gate truth
table is just the complement of the output of the OR gate. The unique output from the NOR
gate is a HIGH only when all inputs are LOW.
INPUTS OUTPUTS
A B OR NOR
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
Fig. 2.18 (c) Truth-table for OR and NOR gates
Figure 2.18(d) shows the ways to express that input A is ORed with input B yielding
output Y.
NOT Symbol
Boolean
Expression A + B = Y or (A + B)′ = Y
OR Symbol
Logic A
Symbol Y
B
A B Y
0 0 1
Truth
0 1 0
Table
1 0 0
1 1 0
Fig. 2.18 (d)

Example 2. Determine the output Y from the NOR gate from the given input waveform
shown in Fig. 2.19.
INPUTS
0 1 0 1
A OUTPUT
t1 t2 t3 t4 Y
B ?
1 1 0 0
Fig. 2.19
Solution. The output of NOR gate is determined by realizing that it will be HIGH only
when both the inputs are LOW and in all other conditions it will be high. The output Y is
shown in Fig. 2.20.
t1 t2 t3 t4
OUTPUT Y ®
0 0 1 0
Fig. 2.20
The NOR gate as a UNIVERSAL gate.

The chart in Fig. 2.21 shows how would your wire NOR gates to create any of the other
basic logic functions.
Logic Symbol Circuit using NOR gates only
Function
A
Inverter A A¢ A¢
A
A
AND A.B A.B
B
B
A A
OR A+B B
B A+B
Fig. 2.21
2.5.8 The Exclusive OR Gate

The exclusive OR gate is sometimes referred to as the “Odd but not the even gate”. It
is often shortend as “XOR gate”. The logic diagram is shown in Fig. 2.22 (a) with its Boolean
expression. The symbol ⊕ means the terms are XORed together.
A
Y = A ⊕B
B
= AB′ + A′B
Fig. 2.22 (a)
The truth table for XOR gate is shown in Fig. 2.22 (b). Notice that if any but not all the
inputs are 1, then the output will be 1. ‘The unique characteristic of the XOR gates that it
produces a HIGH output only when the odd no. of HIGH inputs are present.’
INPUTS OUTPUTS
A B A ⊕ B = AB′ + A′B
0 0 0
0 1 1
1 0 1
1 1 0
Fig. 2.22 (b)
To demonstrate this, Fig. 2.22 (c) shows a three input XOR gate logic symbol and the truth
table of Fig. 2.22 (d). The Boolean expression for a three input XOR gate can be written as
Y = (A ⊕ B) ⊕ C
= (AB′ + A′B) ⊕ C
Now, Let X = AB′ + A′B
Therefore, X ⊕ C = XC′ + X′C
A
B Y = A⊕B ⊕C
C
Fig. 2.22 (c)
INPUTS OUTPUTS
A B C Y
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
Fig. 2.22 (d)
Putting the value of X, we get
Y = (AB′ + A′B)C′ + (A′B′ + AB).C
Y = AB′C′ + A′BC′ + A′B′C + ABC
The HIGH outputs are generated only when odd number of HIGH inputs are present (see
T.T.)
‘This is why XOR function is also known as odd function’.
Fig. 2.22 (e) shows the ways to express that input A is XORed with input B yielding
output Y.
Boolean A Å B = Y
Expression XOR Symbol
Logic A
Symbol Y
B
A B Y
0 0 0
Truth
0 1 1
Table
1 0 1
1 1 0
Fig. 2.22 (e)

The XOR gate using AND-OR-NOT gates:
we know A ⊕ B = AB′ + A′B
A AB¢
A ÅB
B A¢B
As we know NAND and NOR are universal gates means any logic diagram can be made
using only NAND gates or using only NOR gates.
XOR gate using NAND gates only.
A
A ⊕B
B
XOR using NOR gates only.
A
A ⊕B
B
The procedure for implementing any logic function using only universal gate (only NAND
gates or only NOR gates) will be treated in detail in section 2.6.
Example. Determine the output Y from the XOR gate from the given input waveform
shown in Fig. 2.23.
0 1 1 0 0
A
B Y
0 0 0 1 1 ?
C
0 0 1 1 0
t1 t2 t3 t4 t5
Fig. 2.23
Solution. The output XOR gate is determined by realizing that it will be HIGH only
when the odd number of high inputs are present therefore the output Y is high for time
period t2 and t5 as shown in Fig. 2.24.
OUTPUT Y →
0 1 0 0 1
t1 t2 t3 t4 t5
Fig. 2.24
2.5.9 The Exclusive NOR gate

The Exclusive NOR gate is sometimes reffered to as the ‘COINCIDENCE’ or ‘EQUIVA-
LENCE’ gate. This is often shortened as ‘XNOR’ gate. The logic diagram is shown in Fig. 2.25(a).
A
Y=A . B
B = AB + A¢B¢
Fig. 2.25 (a)
Observe that it is the XOR symbol with the added invert bubble on the output side. The
Boolean expression for XNOR is therefore, the invert of XOR function denoted by symbol O..
AO. B = (A ⊕ B)′
= (AB′ + A′B)′
= (A′ + B) . (A + B′)
= AA′ + A′B′ + AB + BB′
= AB + A′B′.
The truth table for XNOR gate is shown in Fig. 2.25 (b).
INPUTS OUTPUTS
A B .
A O B = AB + A′B′
0 0 1
0 1 0
1 0 0
1 1 1
Fig. 2.25 (b)
Notice that the output of XNOR gate is the complement of XOR truth table.
‘The unique output of the XNOR gate is a LOW only when an odd number of input are HIGH’.
A
B Y=A . B . C
C
Fig. 2.25 (c)
INPUTS OUTPUTS
A B C Y
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Fig. 2.25 (d)
To demonstrate this, Fig. 2.25 (c) shows a three input XNOR gate logic symbol and the
truth-table 2.25 (d).
Fig. 2.25 (e) shows the ways to express that input A is XNORed with input B yielding
output Y.
Boolean A . B = Y
Expression
Logic A
Symbol Y
B
A B Y
0 0 1
Truth
0 1 0
Table
1 0 0
1 1 1
Fig. 2.25 (e)

Now at this point, it is left as an exercise for the reader to make XNOR gate using AND-
OR-NOT gates, using NAND gates only and using NOR gates only.
Example. Determine the output Y from the XNOR gate from the given input waveform
shown in Fig. 2.26.
0 1 1 0 0
Y
1 1 1 0 0 ?
0 0 1 1 0
t1 t2 t3 t4 t5
Fig. 2.26
Solution. The output of XNOR gate is
determined by realizing that it will be HIGH 0 1 0 0 1
only when the even-number of high inputs are
OUTPUT Y → t1 t2 t3 t4 t5
present, therefore the output Y is high for time
period t2 and t5 as shown in Fig. 2.27. Fig. 2.27
2.5.10 Extension to Multiple Inputs in Logic Gates

The gates we have studied, except for the inverter and buffer can be extended to have
more than two inputs.
A gate can be extended to have multiple inputs the binary operation it represents is
commutative and associative.
The AND and OR operations defined in Boolean algebra, posseses these two properties.
For the NAD function, we have
x.y = y.x Commutative
and x.(yz) = (x.y).z Associative
Similarly for the OR function,
x + y = y + x Commutative
and (x + y) + z = x + (y + z) Associative
It means that the gate inputs can be interchanged and that the AND and OR function
can be extended to the or more variables.
The NAND and NOR operations are commutative but not associative. For example
*(x ↑ y) = (y ↑ x) ⇒ x′ + y′ = y′ + x′ commutative
But x ↑ (y ↑ z) ≠ (x ↑ y) ↑ z
[x.(yz)′]′ ≠ [(x.y)′.z)]′
x′ + yz ≠ xy + z′
Similarly,
**(x ↓ y) = (y ↓ x) ⇒ x′y′ = y′x′ → commutative
But x↓(y ↓ z) ≠ (x ↓ y) ↓ z
[x + (y + z)′]′ ≠ [(x + y)′ + z]′
x′y + x′z ≠ xz′ + yz′
This difficulty can be overcomed by slightly modifying the definition of operation. We
define the multiple NAND (or NOR) gate as complemented AND (or OR) gate.
Thus by this new definition, we have
x ↑ y ↑ z = (xyz)′
x ↓ y ↓ z = (x + y + z)′
The graphic symbol for 3-input NAND and NOR gates is shown in Fig. 2.28(a) and 2.28(b).
x x
y (xyz)¢ y (x + y + z)¢
z z
(a) Three-input (b) Three-input NOR gate
NAND gate
Fig. 2.28
The exclusive–OR and equivalence gates are both commentative and associative and can
be extended to more than two inputs.
The reader is suggested to verify that, both X-OR and X-NOR possess commutative and
associative property.
* NAND symbol
** NOR symbol
MORE EXAMPLES
Example 1. Give the concluding statement of all the logic gates, we have studied in this
chapter.
Solution. AND: The output is HIGH only when all the inputs are HIGH, otherwise
output is LOW.
OR: The output is LOW only when all the inputs are LOW, otherwise output is HIGH.
NOT: The output is complement of input.
NAND: The output is LOW only when all the inputs are HIGH, otherwise the output
is HIGH.
NOR: The output is HIGH only when all the inputs are LOW, otherwise output is LOW.
EX-OR: The output is HIGH only when both the inputs are not same, otherwise output
is Low.
OR
The output is HIGH only when odd number of inputs are HIGH, otherwise output is
LOW.
EX-NOR: The output is HIGH only when both the inputs are same, otherwise output
is LOW.
OR
The output is HIGH only when even number of inputs are HIGH, otherwise output is
LOW.
Example 2. Show how an EX-OR gate can be used as NOT gate or inverter.
Solution. The expression for NOT gate is
y = A where y = output and A = input
The expression for EX-OR gate is
y = AB + AB A
Y
where A and B are inputs.
In the expression of EX-OR we see that the first term AB
can give the complement of input A, if B = 1 and second term Logic 1
AB = 0 . So we connect the B input to logic HIGH (i.e., logic 1) Fig. 2.29 EX-OR Gate
to full fill the requirements above stated. i.e., connected as NOT Gate
From Fig. 2.29

y = A.1 + A.0
or y = A i.e., complement
Thus, above connection acts as inverter or NOT gate.
Example 3. Show, how an AND gate and an OR gate can be masked.
Solution. Masking of gates means disabling the gate. It is the process of connecting a
gate in such a way that the output is not affected by any change in inputs i.e., the output
remains fixed to a logic state irrespective of inputs.
A Y = 0 always
B
Logic 0
A Y = 1 always
B
Logic 1
Fig. 2.30 Masking of AND gate and OR gate
AND gate can be masked by connecting one of its input to logic LOW (i.e. logic 0) and
OR gate can be masked by connecting one of its input to logic HIGH (i.e. logic 1)
Example 4. Below shown waveforms (Fig. 2.31) are applied at the input of 2-input logic gate.
1 1 1 1
0 0 0 0
A
1
B
1 1
0 0 0
Fig. 2.31
Draw the output waveform if the gate is (a) AND gate (b) OR gate (c) EX-OR gate (d)
NAND gate (e) NOR gate.
Solution. The waveforms can be drawn by recalling the concluding statements of logic
gates given in example 1.
1 1 1 1
0 0 0 0
A
1
B
1 1
0 0 0
Output Waveforms
1 1 1 1
0 0 0 0 0 0
AND
OR
1 1 1 1 1
0
EX-OR
1 1 1 1 1 1
0 0 0 0
NAND
1 1 1 1 1 1
0 0 0 0
1
0 0 0 0 0 0 0 0
NOR
Fig. 2.32
Example 5. Show how a 2 input AND gate, OR gate, EX-OR gate and EX-NOR gate can
be made transparent.
Solution. Transparent gate means a gate that passes the input as it is to the output i.e.
the output logic level will be same as the logic level applied at input. Let the two inputs are
A and B and output is y. We will connect the gates in such a way that it gives y = A.
For AND gate we have expression A Y=A
y = A.B B
if B =1 Logic 1
y =A Fig. 2.33 (a) Transp-
arent AND gate
So, connect input B to logic 1.
For OR gate we have y =A+B A Y=A
B
if B =0
y =A Logic 0
So connect input B to logic 0. Fig. 2.33 (b) Transparent
OR gate
For EX-OR gate we have y = AB + AB
A Y=A
if B = 0, B
then AB = A, and AB = 0
Logic 0
and y =A Fig. 2.33 (c) Transparent
Hence, connect input B to logic 0. EX-OR gate
For EX-NOR gate we have y = AB + AB A Y=A
if B = 1, B
then AB = 0 and AB = A
Logic 1
so y = A
Fig. 2.33 (d) Transparent
Hence, connect input B to logic 1 EX-NOR gate
It we take multiple input logic gates then connecting them as above is called enabling
a gate.
Example 6. Determine the purpose of digital circuit of Fig. 2.34.
A
Y1
Y0
Y2
Y3
B
Fig. 2.34
Solution. From the Fig. 2.34 we see that
y0 = A ⊕ B = AB + AB
y1 = A.y0
y2 = y0
y3 = B.y0
Now we draw three truth tables, one for each of the outputs y1, y2, and y3 to determine
the purpose of the circuit. Table (i)
(i) From the table (i), it is evident that A B Y0 Y1
y1 = 1, only when A = 1 and B = 0. 0 0 0 0
It means that y1 is HIGH only when 0 1 1 0
1 0 1 1
A > B, as shown in third row of
1 1 0 0
Table (i).
Table (ii)
(ii) It is evident from Table (ii) that A B Y0 Y1
y2 = 1 if A = B = 0 and A = B = 1. 0 0 0 1
Thus y2 goes HIGH only when A = 0 1 1 0
B, as shown by first and last row of 1 0 1 0
Table (ii). 1 1 0 1
(iii) It is evident from Table (iii) that Table (iii)

y3 = 1 if A = 0 and B = 1. Thus y3 A B Y0 Y1
0 0 0 0
goes HIGH only when A < B (or B >
0 1 1 1
A), as shown by the second row of 1 0 1 0
table (iii). 1 1 0 0
Thus from the above discussion it can be concluded that the given circuit is 1-bit
data comparator. In this circuit, y1 indicates A > B, y2 indicate the equality of two
datas, and y3 indicates A < B.
2.6 NAND AND NOR IMPLEMENTATION

In section 2.5.7 we have seen that NAND and NOR are universal gates. Any basic logic
function (AND, OR and NOT) can be implemented using these gates only. Therefore digital
circuits are more frequently constructed with NAND or NOR gates than with AND, OR and
NOT gates. Moreover NAND and NOR gates are easier to fabricate with electronic compo-
nents and are the basic gates used in all IC digital logic families. Because of this prominence,
rules and procedures have been developed for implementation of Boolean functions by using
either NAND gates only or NOR gates only.
2.6.1 Implementation of a Multistage (or Multilevel) Digital Circuit using NAND

Gates Only
To facilitate the implementation using NAND gates only, we first define two graphic
symbols for these gates as follows-shown in Fig. 2.35(a) and (b).
(a) The AND-invert symbol (b) The invert-OR symbol
x x
y F = (xyz)¢ y F = x¢ + y¢ + z¢
z z = (xyz)¢
(a) (b)
(a) This symbol we have been difined in section (2.5). It consists of an AND
grpahic symbol followed by a small circle.
(b) This is an OR graphic symbol proceded by small circtes in all the inputs.
Fig. 2.35
To obtain a multilevel NAND circuit from a given Boolean function, the procedure is as
follows:
1. From the given Boolean function, draw the logic diagam using basic gates (AND, OR
and NOT). In implementing digital circuit, it is assumed that both normal and invented
inputs are available. (e.g., If x and x′ both are given in function, we can apply then
directly that is there is no need to use an inverter or NOT gate to obtain x′ from x).
2. Convert all AND gates to NAND using AND-invert symbol.
3. Convert all OR gates to NAND using Invert-OR symbol.
4. Since each symbol used for NAND gives inverted output, therefore it is necessary
to check that if we are getting the same value as it was at input. [For example if
the input is in its normal from say x, the output must also be x, not x′ (inverted
or complemented value). Similarly if input is in its complemented form say x′, the
ouput must also be x′, not x (normal value)].
If it is not so, then for every small circle that is not compensated by another small
circle in the same line, insert an inverter (i.e., one input NAND gate) or comple-
ment the input variable.
Now consider a Boolean function to demonstrate the procedure:
Y = A + (B′ + C) (D′E + F)
Step 1. We first draw the logic diagram using basic gates shown in Fig. 2.36. (It is
assumed that both normal and complemented forms are available i.e., no need of inverter).
A
Y
B′
C
D′
E
F
I Level II Level III Level IV Level
Fig. 2.36
There are four levels of gating in the circuits.
Step 2 and 3
A
Y
B¢
C
D¢
E
F
Fig. 2.37
Here, we have converted all AND gates to NAND using AND-invert and all OR gates to
NAND using invert OR symbol shown in Fig. 2.37.
Step 4. From the Fig. 2.37 obtained from step 2 and 3, it is very clear that only two
inputs D′ and E are emerging in the original forms at the output. Rest i.e., A, B′, C and F
are emerging as the complement of their original form. So we need an inverter after inputs
A, B′, C and F or alternatively we can complement these variables as shown in Fig. 2.38.
A¢
Y
B
C¢
D¢
E
F¢
Fig. 2.38
Now because both the symbols AND-invert and invert-OR represent a NAND gate, Fig.
2.38 can be converted into one symbol diagram shown in Fig. 2.39. The two symbols were
taken just for simplicity of implementation.
A′
Y
B
C′
D′
E
F′
Fig. 2.39
After a sufficient practice, you can directly implement any Boolean function a shown in
Fig. 2.39.
2.6.2 Implementation of a Multilevel digital circuit using NOR Gates only

We first define two basic graphic symbols for NOR gates as shown in Fig. 2.40 (a)
and (b).
(a) The OR-invert symbol (b) The invert-AND symbol
x x
y F = (x + y + z)¢ y F = x¢ y¢ z¢
z z = (x + y + z)¢
(a) This is an OR graphic symbol (b) This is an AND graphic symbol proceded
followed by a small circle. by small circles in all the inputs.
Fig. 2.40 (a) (b)

Procedure to obtain a multilevel NOR circuit from a given Boolean function is as follows:
1. Draw the AND-OR logic diagram from the given expression. Assume that both
normal and complemented forms are available.
2. Convert all OR gates to NOR gates using OR-invert symbol.
3. Convert all AND gates to NOR gates using invert-AND symbol.
4. Any small circle that is not complement by another small circle along the same line
needs an inverter (one input NOR gate) or the complementation of input variable.
Consider a Boolean expression to demonstrate the procedure:
Y = (A ′ + B) .(C + D′ ) E + (F + G ′ )
Step 1. We first draw the AND-OR logic diagram shown in Fig. 2.41.
A′
B
C
D′
E
Y
F
G′
I Level II Level III Level IV Level
Fig. 2.41
There are four levels of gating in the circuit.
Step 2 and 3. Here we have to convert all OR gates to NOR using OR-invert and all
AND gates to NOR using invert AND symbol. This is shown in Fig. 2.42.
A′
B
C
D′
E
Y
F
G′
Fig. 2.42
Step 4. From Fig. 2.42, it is clear that all the input variables are imerging in the same
form at the ouput Y as they were at input. Therefore there is no need of inverter at inputs
or complementing the input variables.
Here again, both symbols OR-invert and invent-AND represent a NOR gate, so the
diagram of Fig. 2.42 can be converted into one symble shown in Fig. 2.43.
A′ (A′ + B)′
B
C (C + D′)′
D′
E
Y
F
G′
Fig. 2.43
2.7 EXERCISE
1. Write Boolean equations for F1 and F2.
A B C F1 A B C F2
0 0 0 1 0 0 0 0
0 0 1 0 0 0 1 1
0 1 0 0 0 1 0 1
0 1 1 0 0 1 1 1
1 0 0 0 1 0 0 0
1 0 1 1 1 0 1 1
1 1 0 0 1 1 0 1
1 1 1 1 1 1 1 0
2. Consider 2-bit binary numbers, say A, B and C, D. A function X is true only when
the two numbers are different construct a truth table for X.
3. Draw truth table and write Boolean expression for the following:
(a) X is a 1 only if A is a 1 and B is a 1 or if A is 0 and B is a 0.
(b) X is a 0 if any of the three variables A, B and C are 1’s. X is a 1 for all other
conditions.
4. Prove the following identities by writing the truth tables for both sides:
(a) A.(B + C) = (A.B) + (A.C)
(b) (A.B.C)′ = A′ + B′ + C′
(c) A.(A + B) = A
(d) A + A′B = A + B
5. Prove the following:
(a) (X + Y) (X + Y ′ ) = X
(b) XY + X ′ Z + YZ = XY + X ′ Z
(c) ( X + Y ′ ) = X. Y
(d) ( X + Y ) ( X + Z) = X + Y + Z
(e) ( X + Y + Z) ( X + Y + Z ′ ) = X + Y
6. Without formally deriving can logic expression, deduct the value of each function
W, X, Y, Z.
A B C W X Y Z
0 0 0 0 1 0 1
0 0 1 0 1 0 0
0 1 0 0 1 0 1
0 1 1 0 1 0 0
1 0 0 0 1 1 1
1 0 1 0 1 1 0
1 1 0 0 1 1 0
1 1 1 0 1 1 0
7. A large room has three doors, A, B and C, each with a light switch that can tura
the room light ON or OFF. Flipping any switch will change the condition of the
light. Assuming that the light switch is off when the switch variables have the
values 0, 0, 0 write a truth table for a function LIGHT that can be used to direct
the behaviour of the light. Derive a logic equation for light.
8. Use DeMorgan’s theorm to complement the following Boolean expression.
(a) Z = Z = x. ( y + w. v)
(b) Z = x. y. w + y( w′ + v′ )
(c) Z = x′ + yΥ
(d) F = ( AB + CD)′′
(e) b
F = (A + B′ ) (C′ + D ′ g
(f) F = b ( A + B′ ) (C + D) g ′
(g) F = b (ABC) ′ (EFG) ′ g ′ + b ( HIJ) ′ (KLM) ′ g′ ′
(h) F = b (A + B) ′ ( C + D) ′ ( E + F) ′ ( G + H) ′ g ′ ′
9. A certain proposition is true when it is not true that the conditions A and B both
hold. It is also true when conditions A and B both hold but condition C does not.
Is the proposition true when it is not true that conditions B and C both hold? Use
Boolean algebra to justify your answer.
10. Define the following terms:
(a) Connical
(b) Minterm
(c) Mexterm
(d) Sum-of-sums form
(e) Product-of-sum form
(f) Connical sum-of-product
(g) Connical product-of-sums
11. Write the standard SOP and the standard POS form for the truth tables:
(a) x y z F (b) x y z F
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 0
0 1 0 1 0 1 0 0
0 1 1 0 0 1 1 1
1 0 0 1 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 1
12. Convert the following expressions into their respective connical forms:
(a) AC + A ′ BD + ACD′
(b) (A + B +C′ ) (A + D)
13. Which of the following expressions is in sum of product form? Which is in product
of sums form?
(a) A + (B.D)′
(b) C.D′ .E + F ′ + D
(c) (A + B).C
14. Find the connical s-of-p form for the following logic expressions:
(a) W = ABC + BC′ D
(b) F = VXW ′ Y + W ′ XYZ
15. Write down the connical s-of-p form and the p-of-s form for the logic expression
whose TT is each of the following.
(a) x1 y2 z3 Z (b) W X Y Z F
0 0 0 1 0 0 0 0 1
0 0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 0 1
0 1 1 1 0 0 1 1 0
1 0 0 1 0 1 0 0 1
1 0 1 1 0 1 0 1 0
1 1 0 0 0 1 1 0 1
1 1 1 1 0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
16. Convert the following expressions to sum-of-product forms:

(a) AB + CD (AB′ + CD)
(b) AB (B′ C′ + BC)
(c) A + B AC + (B + C) ′ D
17. Given a Truth table
(a) Express W1 and W2 as a sum of minterms
(b) Express W1 and W2 as product of minterms
(c) Simplify the sum of minterm expressions for W1 and W2 using Boolean algebra.
18. Draw logic circuits using AND, OR and NOT gates to represent the following:
(a) AB′ + A ′ B (b) AB + A ′ B′ + A ′ BC
(c) A + B C + D (B + C′ ) (d) A + BC′ + D (E′ + F ′ )
(e) (AB) ′ (CD) ′ ′

19. Produce a graphical realization of Inverter, AND, OR and XOR using:
(a) NAND gates
(b) NOR gates
20. Implement the Boolean function
F = AB′ CD′ + A ′ BCD′ + AB′ C′ D + A ′ BC′ D with exclusive-OR and AND gates.
21. Draw the logic circuits for the following functions.
22. A warning busser is to sound when the following conditions apply:
(a) Switches A, B, C are on.
(b) Switches A and B are on but switch C is off.
(c) Switches A and C are on but switch B is off.
(d) Switches B and C are on but switch A is off.
Draw a truth table and obtain a Boolean expression for all conditions. Also draw the
logic diagram for it using (i) NAND gates (ii) NOR gates. If the delay of a NAND
gate is 15 ns and that of a NOR gate is 12 ns, which implementation is tester.
23. Obtain the following operations using only NOR gates.
(a) NOT (b) OR (c) AND
24. Obtain the following operations using only NAND gates.
(a) NOT (b) AND (c) OR
25. Find the operation performed for each of the gets shown in figure below, with the
help the truth table.
A A
(a) Y (b) Y
B B
A A
(c) Y (d) Y
B B
26. Write the expression for EX-OR operation and obtain

(i) The truth table
(ii) Realize this operation using AND, OR, NOT gates.
(iii) Realize this operation using only NOR gates.
27. Varify that the (i) NAND (ii) NOR operations are commutative but not associate.
28. Varify that the (i) AND (ii) OR (iii) EX-OR operations are commutative as well as
associative.
29. Prove that
(i) A positive logic AND operation is equivalent to a negative logic OR operation
and vice versa.
(ii) A positive logic NAND operation is equivalent to a negative logic NOR opera-
tion and vice versa.
30. Prove the logic equations using the Boolean algebraic (switching algebraic) theo-
rems.
(i) A + AB + AB = A + B
(ii) AB + AB + AB = AB
Varify these equations with truth table approach.
31. Prove De Morgan’s theorems.
32. Using NAND gates produce a graphical realization of
(a) Inverter
(b) AND
(c) OR
(d) XOR
33. Using NOR gates also produce a graphical realization of
(a) Inverter
(b) AND
(c) OR
34. Prove (X + Y) (X + Y′) = X
35. XY + X′Z + YZ = XY + X′Z
36. Prove the following:
37. (a) (A + B)′ = A.B (b) (A + B) (A + C) = A + BC
38. Prove the identifies:
(i) A = (A + B) (A + B)¢
(ii) A + B = (A + B + C) (A + B + C′)
39. Obtain the simplified expressions in s-of-p for the following Boolean functions:
(a) xy + x′ yz ′ + x′ yz ′
(b) ABD + A ′ C′ D′ + A ′ B + A ′ CD′ + AB′ D ′
(c) x′ z + w′ xy ′ + w ( x′ y + xy ′ )
(d) F ( x, y, z) = Σ ( 2, 3, 6, 7)
(e) F (A, B, C′ ) (A + D)
40. Convert the following expressions into their respective Canonical forms
(a) AC + A'BD + ACD'
(b) (A + B + C') (A + D)
41. Write the standard SOP and the standard POS form for the truth tables
(a) (b)
x y z F(x, y, z) x y z F(x, y, z)
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 0
0 1 0 1 0 1 0 0
0 1 1 0 0 1 1 1
1 0 0 1 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 1
42. Consider 2-bit binary numbers, say A, B and C, D. A function X is true only when
the two numbers are different.
(a) Construct a truth table for X
(b) Construct a four-variable K-Map for X, directly from the word definition of X
(c) Derive a simplified logic expression for X.
43. Show an implementation of the half-adder using NAND gates only.
44. A three-bit message is to be transmitted with an even-parity bit.
(i) Design the logic circuit for the parity generator.
(ii) Design the logic circuit for the parity checker.
45. Implement the Boolean function: F = AB′CD′ + A′BCD′ + AB′C′D + A′BC′D′ with
exclusive-OR and AND gates.
46. Construct a 3-to-8 line decoder.
47. Construct a 3 × 8 multiplexer.
48. Construct a 8 × 3 ROM using a decoder and OR gates.
49. Construct a 16 × 4 ROM using a decoder and OR gates.
50. Determine which of the following diodes below are conducting and which are non
conducting.
–5v
–5v
–12v D1
D1 D2
+5v D2
R
R
–10v –5v
51. Determine which transistors are ON are which are OFF.

+5v –10v +10v
–5v –6v
–15v –2v
52. Construct voltage and logic truth tables for the circuits shown below. Determine
(i) (ii)
D1
A +5v
D2
B
R
D3
C D1
(i) A
Output
1 = +5v D2
0 = –5v R
B
1 = 0v
D3 0 = –5v
–10v C
the logic operation performed by each. Assume ideal diodes i.e., –neglect the volt-
age drop across each diode when it is forward biased.
53. Draw the logic circuits for the following functions:
(a) B.(A.C′ ) + D + E′
(b) (A + B) ′ . C + D
(c) (A + B) .(C′ + D)
54. Prove the following identities by writing the truth tables for both sides.
(a) A.(B + C) == (A.B) + (A.C)
(b) (A.B.C)′ == A′ + B′ + C′
(c) A.(A + B) == A
(d) A + A′.B == A + B
55. A warningbuzzer is to sound when the following conditions apply:
• Switches A, B, C are on.
• Switches A and B are on but switch c is off.
• Switches A and C are on but switch B is off.
• Switches C and B are on but switch A is off.
Draw a truth table for this situation and obtain a Boolean expression for it. Mini-
mize this expression and draw a logic diagram for it using only (a) NAND (b) NOR
gates. If the delay of a NAND gate is 15ns and that of a NOR gate is 12ns, which
implementation is faster.
56. Which of the following expressions is in sum of products form? Which is in product
of sums form?
(a) A.+(B.D)′
(b) C.D′.E + F′ + D
(c) (A + B).C
57. Without formally deriving an logic expressions, deduce the value of each function
W, X, Y and Z.
A B C W X Y Z
0 0 0 0 1 0 1
0 0 1 0 1 0 0
0 1 0 0 1 0 1
0 1 1 0 1 0 0
1 0 0 0 1 1 1
1 0 1 0 1 1 0
1 1 0 0 1 1 1
1 1 1 0 1 1 0
58. Define the following terms:
(a) Canonical
(b) Minterm
(c) Maxterm
(d) Sum-of-products form
(e) Product-of-sum form
(f) Canonical sum-of-products
(g) Canonical product-of-sums
59. An audio (beeper) is to be activated when the key has been removed from the
ignition of a car and the headlights are left on. The signal is also to be activated
if the key is in the ignition lock and the driver’s door is opened. A 1 level is
produced when the headlight switch is on. A 1 level is also produced from the
ignition lock when the key is in the lock, and a 1 level is available from the driver’s
door when it is open. Write the Boolean equation and truth table for this problem.
60. A car has two seat switches to detect the presence of a passenger and two seat belt
switches to detect fastened seat belts. Each switch produces a 1 output when
activated. A signal light is to flash when the ignition when the ignition is switched
on any passenger present without his or her seat belt fastened. Design a suitable
logic circuit.
61. Draw logic diagrams for the simplified expressions found in Question 37 using.
• NAND gates only.
• NOR gates only.
Assume both A and A′, B and B′ .. etc. are available as inputs.
62. You are installing an alarm bell to help protect a room at a museum form unau-
thorized entry. Sensor devices provide the following logic signals:
ARMED = the control system is active
DOOR = the room door is closed
OPEN = the museum is open to the public
MOTION = There is motion in the room
Devise a sensible logic expression for ringing the alarm bell.
63. A large room has three doors, A, B and C, each with a light switch that can turn the
room light ON or OFF. Flipping any switch will change the condition of the light.
Assuming that the light switch is off when the switch variables have the values 0,
0, 0 write a truth table for a function LIGHT that can be used to direct the behaviour
of the light. Derive a logic equation for LIGHT. Can you simplify this equation?
64. Design a combinational circuit that accepts a three-bit number and generates an
output binary number equal to the square of the input number.
65. Design a combinational circuit whose input is a four-bit number and whose output
is the 2’s compliment of the input number.
66. A combinational circuit has four inputs and one output. The output is equal to 1
when (I) all the inputs are equal to 1 or (II) none of the inputs are equal to 1 or
(III) an odd number of inputs are equal to 1.
(i) Obtain the truth table.
(ii) Find the simplified output function in SOP
(iii) Find the simplified output function in POS
(iv) Draw the two logic diagrams.
67. Find the canonical s-of-p form the following logic expressions:
(a) W = ABC + BC′D
(b) F = VXW′Y + W′XYZ
68. A certain proposition is true when it is not true that the conditions A and B both
hold. It is also true when conditions A and B both hold but condition C does not.
Is the proposition true when it is true that conditions B and C both hold ? Use
Boolean algebra to justify your answer.
69. Write down the canonical s-of-p form and the p-of-s form for the logic expression
whose truth table is each of the following.
(I) X1 X2 X3 Z (II) A B C W
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 1 0 0 0 1 0 1
0 1 1 1 0 1 1 0
1 0 0 1 1 0 0 1
1 0 1 1 1 0 1 0
1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 1
(III) W X Y Z F
0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 1 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
70. Use Question 5.
(a) Using K-maps, obtain the simplified logic expressions for both s-of-p and p-of-s
for each truth table in the question 5 above.
(b) From the p-of-s expressions, work backwards using a K-map to obtain the
s-of-p canonical expression for each truth table.
71. Apply De-Morgan’s theorems to each expression
(a) A + B (b) AB (c) A + B + C (d) A B C
(e) A (B + C) (f) AB + CD (g) AB + CD (h) (A + B) + ( C + D)

(i) ( ABC) (EFG) + ( HIJ) (KLM) (j) A + BC + CD + BC
(k) ( A + B) ( C + D) ( E + F) ( G + H)
72. Convert the following expressions to sum-of-products forms:
(a) AB + CD (AB + CD) (b) AB (B C + BC) (c) A + B [AC + (B + C) D]

73. Write a Boolean expression for the following
(a) X is a 1 only if a is a 1 and B is a 1 or if A is a 0 and B is a 0
(b) X is a 0 if any of the three variables A, B and C are 1’s. X is a 1 for all other
conditions.
74. Draw logic circuits using AND, OR and NOT elements to represent the following
(a) AB + AB (b) AB + AB + ABC (c) A + B [C + D(B + C)]
(d) A + BC + D(E + F) (e) (AB) (CD) (f) [(A + B) (C + D)]E + FG
75. Use Duality to derive new Boolean identities from the ones you obtained by sim-
plification in the previous question.
76. Use De Morgan’s Theorem to complement the following Boolean expressions
(a) z = x.( y + w. v)
(b) z = x. y. w + y.( w + v )
x
Prove this imlements XOR.

(c) z= x+ y
(d) z = x + y. w
(e) z = ( x + y). w
(f) z = x + y. w
77. Using Boolean Algebra verify that the circuit in figure 1 implements an exclusive
OR (XOR) function
(a) Express z1 and z2 as a sum of minterms
(b) Express z1 and z2 as a product of maxterms
(c) Simplify the sum of the minterm for z1 and z2 using Boolean algebra.

Unit 1 PDF

Uploaded by

Copyright:

Available Formats

Unit 1 PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 1 PDF

Uploaded by

Copyright:

Available Formats

UNIT – I

Number System and Boolean algebra And Switching

1.1 A REVIEW OF THE DECIMAL SYSTEM

1.2 BINARY NUMBERING SYSTEM

1.2.1 Binary to Decimal Conversion

1.2.2 Decimal to Binary Conversion

Division Dividend Remainder

Dividend is 0, stop the procedure.

Our final number is (10011)2.

1.2.3 Binary Formats

1.2.4 Data Organization

Fig. 1.1 Bit numbering in a byte

High Nibble Low Nibble

Fig. 1.3 Bit numbers in a word

High Byte Low Byte

Nibble 3 Nibble 2 Nibble 1 Nibble 0

Fig. 1.6 Bit numbers in a double word

High order word Low order word

Higher Byte Byte 2 Byte 1 Lower Byte

Fig. 1.7 Nibbles, bytes, and words in a double word

1.3 OCTAL NUMBERING SYSTEM

1.3.1 Octal to Decimal, Decimal to Octal Conversion

1.3.2 Octal to Binary, Binary to Octal Conversion

1.4 HEXADECIMAL NUMBERING SYSTEM

Decimal Hexadecimal Binary

1.4.1 Hex to Decimal and Decimal to Hex Conversion

1.4.2 Hex to Binary and Binary to Hex Conversion

So AE in binary is 1010 1110

1.4.3 Hex to Octal and Octal to Hex Conversion

Hex to Octal Conversion

(1 A 3)16 = 0001 1010 0011

(1A3)16 = 000 110 100 011

Octal to Hex Conversion

(76)8 = 111 110

(76)8 = 11 1110 0011 1110

1.5 RANGE OF NUMBER REPRESENTATION

Highest decimal Number = rn – 1

where, r = base or radix of Number system

Solution. Given radix of number system r = 5

1.6 BINARY ARITHMETIC

The process of subtraction is very similar to decimal system in which if a borrow is

1.7 NEGATIVE NUMBERS AND THEIR ARITHMETIC

1.7.1 1’s and 2’s Complement

Solution. (i) 0 1 1 0 0 1 ← Number

1001 2s 0111 2s

Fig. 1.11 Effect of taking complement twice

1.7.2 Subtraction Using 1’s and 2’s Complement

Step 2. Perform addition of minuend and 1’s complement of subtrahend

Step 3. No carry produced so no EAC operation.

1.7.3 Signed Binary Representation

(iii) In 2’s complement

1.7.4 Arithmetic Overflow

Since, MSB of result is 1, if reflects a negative result which is incorrect. It happened

1.7.5 9’s and 10’s Complement

9’s complement: 9’s complement of a decimal number is defined as (10n – 1) – N, where n

So, (10n–1) – N = (104–1) – 1697 = 9999 – 1697

1.7.6 r’s Complement and (r – 1)’s Complement

and r’s complement of N = rn – N

1.7.7 Rules for Subtraction using (r–1)’s Complement

1001 2s 0111 2s