Unit 1 (DLD&CO) R22

UNIT-1
Number system:
In number system modern method of representing numbers symbolically is based on positional notations.
In this method, each number is represented by a string of symbols where each symbol is associated with a specific weight depending upon its
positions. The total number of different symbols which are used in a particular number system is called the base or radix of the system and the weight
of each position of a particular number is expressed as a power of the base. When a number is formed with the combination of the symbols, each
symbol is then called a digit and the position of each symbol is referred to as the digit position.
Thus if a number system has symbols starting from 0, and the digits of the system are 0, 1, 2, ….. (r - 1) then the base or radix is r. If a number D of
this system be represented by
D = d₀ d₀ ……. d₀…….. d₁ d
then the magnitude of this number is given by
|D| = dn-1 rn-1 + dn-2 rn-2 + …… di ri + …… d1 r1 + d0 r0
Where each d₀ ranges from 0 to r - 1, such that

0 ≤ d₀ ≤ r - 1, i = 0, 1, 2 ...... (n - 1).
The digit at the extreme left has the highest positional value and is generally called the Most Significant Digit, or in short MSD; similarly, the digit
occupying the extreme right position has the least positional value and is referred to as the Least Significant Digit or LSD.
What is Decimal Number System?
Decimal number system is the most common example of positional notational number system and all the arithmetical calculations undertaken by
human being are carried out on the basis of this number system. In this system, the symbols used are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and the base is 10. Thus
the number
dn-1 dn-2…..d 1 d0 means dn-1 10n-1 + dn-2 10n-2 + ……. + d1 101 + d0 100
and this is an n-digit number. If the number be extended to the right of the decimal point, then the powers of the base will be negative starting from -
1.
For example, the number 3528 has the magnitude
3528 = 3 × 103 + 5 × 102 + 2 × 101 + 8 × 100
and the number 26.57 has the magnitude
26.57 = 2 × 10 + 6 × 100 + 5 × 10-1 + 7 × 10-2
Binary number system?
Here we will discuss about the binary number system we already know binary numbers play a vital role in the design of digital computers.
Hence a detailed discussion of binary number system is given in this section. Binary number system uses two symbols 0 and 1 and its radix is 2. The
symbols 0 and 1 are generally called BITS which is a contraction of the two words Binary digits.
An n-bit binary number of the form an-1 an-2 ….. a1 a0 where each ai (i = 0, 1, …. n - 1) is either 0 or 1 has the magnitude.
an-1 2n-1 + an-2 2n-2 + …….+ a1 21 + a020.
For fractional binary numbers, the base has negative integral powers starting with -1 for the bit position just after the binary point.
57
The bit at the extreme left of a binary number has the highest positional value and is usually called the Most Significant Bit or MSB. Similarly, the
bit occupying the extreme right position of a given binary number has the least positional value and is referred to as the Least Significant
Bit or LSB.
To facilitate the distinction between different number systems, we generally use the respective radix as a subscript of the number. However the
subscript will not be used when there is no scope of confusion.
In binary number system a few examples on binary numbers and their decimal equivalents are given below:
1011012 = 1 × 25 + 0 × 24 + 1 × 23 + 1 × 22 + 0 × 21 + 1 × 20
= 32 + 0 + 8 + 4 + 0 + 1
= 4510
The above results can be more clearly expressed in the following manner:
Binary point
111.10112
= 1 × 22 + 1 × 21 + 1 × 20 + 1 × 2-1 + 0 × 2-2 + 1 × 2-3 + 1 × 2-4
= 4 + 2 + 1 + .5 + 0 + .125 + .0625
= 7.687510
The above results can be more clearly expressed in the following manner:
57
These are the basic examples shown above.
Binary to decimal conversion:
There are several traditional methods of converting the numbers from binary to decimal conversion. We shall discuss here the two most commonly
used methods, namely; “Expansion method and Value Box method”.
(i) Expansion Method:
In this method, the given number is expressed as a summation of terms each of which is the product of a bit (0 or 1) and a power of 2. The power of
2 is determined from the bit position.
Thus the decimal equivalent of a binary number has the general form;
an-1 an-2 …. ai ….. a1 ….. a0 ∙ a-1 a-2 ….. a-p
= an-1 × 2n-1 + an-2 x 2n-2 + ….. +ai x 2i + …. + a1 x 21 + a0 x 20 + a-1 x 2-1 + a-2 x 2-2 + …. + a-p x 2-p
(ii) Multiplication and Division Method:
The value box method of converting numbers from decimal to binary is laborious and time consuming and is suitable for small numbers when it can
be performed mentally. It is advisable not to use it for large numbers. The conversion of large numbers may be conveniently done by multiplication
and division method which is described below.
To effect the conversion of positive integers of the decimal system to binary numbers the decimal number is repeatedly divided by the base of the
binary number system, i.e., by 2. The division is to be carried until the quotient is zero and the remainder of each division is recorded on the right.
The binary equivalent of the decimal number is then obtained by writing down the successive remainders. The first remainder is the least significant
bit and the last one is the most significant bit of the binary number. Thus the binary equivalent is written from the bottom upwards.
Octal number system:
Octal number system has a base or radix 8. Eight different symbols, namely 0, 1, 2, 3, 4, 5, 6, 7 are used to represent octal numbers. Conversion of
octal numbers to their decimal equivalents can be accomplished by using the same rule which was followed to convert binary numbers to decimal
numbers, except that we now have a radix 8 instead of 2. Thus the octal number 273 has the decimal equivalent.
57
2738
= 2 × 82 + 7 × 81 + 3 × 80
= 128 + 56 + 3
= 18710
Conversion of decimal I integers to octal can be performed by successively dividing number by 8 and using each remainder as a digit of the desired
octal number. We note that the first remainder is the least significant digit and the last one is the most significant digit. In the case of decimal
fractions, we use the same method which was used in converting decimal fractions to binary fractions.
Few examples on octal number system are explained with this method:
Convert the decimal numbers to their octal equivalents:
(a) 2980
Solution:
2980
Hence 298010 = 56448
(b) 0.685
Solution:
0.685
Decimal Numbers to Binary Number Conversion Table
Multiplication Integer Fraction
0.685 × 8 = 5.480 5 .48
0.48 × 8 = 3.84 3 .84
.84 × 8 = 6.72 6 .72
.72 × 8 = 5.76 5 .76
Therefore, 0.68510 = (0.5365…)8
Hexa-decimal number system
57
The hexa-decimal number system has a radix or base 16. It requires 16 symbols to represent a number in this system. The symbols are 0 to 9, A, B,
C, D, E, F where the symbols A, B, C, D, E, F represent the decimal numbers 10, 11, 12, 13, 14, 15 respectively. Let us recall the conversion table for
the decimal numbers 0 to 15 and their binary, octal and hexa-decimal equivalents.
The conversion of hexa-decimal numbers to their decimal equivalents is straight-forward and follows the same rules as that of octal or binary to
decimal. Similarly, conversion of decimal to hexa-decimal may be worked out with the help of division or multiplication, as the case may be, by the
radix 16.
The example on hexa-decimal number system will help us to understand the procedure:
1. Convert B6A16 to its decimal equivalent.
Solution:
B6A16
= 11 × 162 + 6 × 161 + 10 × 160
= 2816 + 96 + 10
= 292210
Therefore, B6A16 = 292210
2. Convert 391710 to its hexa-decimal equivalent
Solution:
391710
Therefore, 391710 = F4D16
Following examples on number conversion :
1. Convert 421510 to its binary equivalent
Solution:
Therefore, 421510 =10000011101112
57
The conversion of decimal fractions to binary fractions is accomplished by multiplying repeatedly the decimal fraction by the base 2 of the binary
number. The integral part after each multiplication is either 0 or 1. The equivalent binary fraction is obtained by writing the integral parts of each
product to the right of the binary point in the same sequence. If the fractional part of the product becomes exactly zero at a certain stage, then the
binary fraction is finite, otherwise, the fraction is non-terminating and then we find the binary fraction upto the desired degree of accuracy. We
explain the process with the help of the following examples.
2. Convert the following decimal numbers to their binary equivalents:
(a) 0.375
Solution:
0.375 × 2 = 0.75 0 .75
0.75 × 2 = 1.5 1 .5
.5 × 2 = 1.0 1 0
Therefore, 0.37510 = 0.0112
(b) 0.435
Solution:
0.435 × 2 = 0.87 0 .87
0.87 × 2 = 1.74 1 .74
.74 × 2 = 1.48 1 .48
.48 × 2 = 0.96 0 .96
.96 × 2 = 1.92 1 .92
Therefore, 0.43510 = (0.01101…)2
Fox mixed number, we will have to separate the number into its integral and fractional parts and find the binary equivalent of each part
independently.
Finally, we add the two parts to get the binary equivalent of the given number.
3. Convert (56.75)10 to its binary equivalent.
Solution:
57
At first we find the binary equivalent of 56.
Therefore, 5610 = 1110002
The binary equivalent of 0.75 is obtained below:
0.75 × 2 = 1.5 1 .5
0.5 × 2 = 1.0 1 0
Therefore, 0.7510 = 0.1110
Hence 56.7510 = 111000.1110
What is Signed-magnitude Representation?
The representation of decimal numbers in everyday business is commonly called the signed-magnitude representation.
In this system, a number consists of a magnitude and a symbol which indicates whether the magnitude is positive or negative.
Thus the decimal numbers + 79, - 82, - 25.2 etc. are interpreted in the usual manner.
This mode of representation can be incorporated to binary numbers quite easily by using an extra bit position to represent the sign. This extra bit is
called the SIGN BIT and is placed before the magnitude of the number to be represented. Generally, the MSB is the sign bit and the convention is
that when the sign bit is 0, the number represented is positive and when the sign bit is 1, the number is negative.
A few examples of 8-bit signed-magnitude binary numbers along with their decimal equivalents are given below to show the point.
(i) (01101101)2 = +(109)10
(ii) (11101101)2 = -(109)10
(iii) (00101011)2 = +(43)10
(iv) (10101011)2 = -(43)10
(v) (00000000)2 = +(0)10
57
(vi) (10000000)2 = -(0)10
We note that in signed-magnitude representation two possible representations of zero may be obtained.
Radix Complement Representation:
In the decimal number system, the radix complement is the 10’s complement. In radix complement representation system, the complement of an n-
digit number is obtained by subtracting the number from 10n.
Let us consider some examples of 3-digit numbers and their radix complement in decimal system.
Decimal Number Radix Complement
948 52
607 393
155 845
735 265
br>From the above discussion we find that a subtraction operation is to be preformed to get the 10’s complement of a number, say, N. This
subtraction operation can be avoided by rewriting 10n as (10n - 1) + 1 and 10n - N as {(10n - 1) - N} + 1. The number 10n - 1 is of the form 999...99
consisting of n digits. If the complement of a digit be defined as (9 - the concerned digit), then (10 n - 1) - N is obtained by complementing the digits
of N.
Therefore, the 10’s complement of the number N is obtained by subtracting each digit of the number from 9 and then adding 1 to the LSD of the
number so formed.
For instance, the 10’s complement of 172 is (827 + 1) or 828 and that of 405 is (594 + 1) or 595.
For the binary number system the radix complement is the two’s complement. The 2’s complement of a binary number is obtained by subtracting
each bit of the number from the radix diminished by 1 i.e. from (2 - 1) or 1 and adding an 1 to the LSB. The application of this rule is very simple.
We have to just change 1 to 0 and 0 to 1 in every bit and then add 1 to the LSB of the number so formed. For example, the 2’s complement of the
binary number 11011 is (00100 + 1) or 00101 and that of 10110 is (01001 + 1) or 01010.
If the number be in signed magnitude representation, it is positive if the MSB is 0 and negative if the MSB is 1. The decimal equivalent of a 2’s
complement binary number, in the case of signed-magnitude representation, is computed in the same way as for an unsigned number except that the
weight of the MSB is -2n-1 instead of +2n-1 for an n-bit binary number.
Let us observe some examples of 8-bit binary numbers and their 2’s complement are shown below:
Binary Number Decimal equivalent
Sign bit 01101101 + 109
Complement: 10010010
+1
10010011 - 128 + 19 = -109
Diminished Radix Complement Representation:
In the decimal number system the diminished radix complement is 9’s complement. This is obtained by subtracting each digit of the number from 9.
Decimal Number 9’s Complement
57
59 40
894 105
6578 3421
2063 7936
The diminished radix complement of binary numbers is called 1’s complement. The 1’s complement of a binary number is formed by replacing each
1 in the number by a 0 and each 0 by 1.
For example, 1’s complements of some binary numbers are;
Binary Number 1’s Complement
1011 0100
1101 0010
In the case of signed magnitude representation of binary numbers, the MSB is the sign bit.
Positive number representations are same for both 1’s and 2’s complement. But representation of negative numbers differs by 1. A weight of -(2 n-1 -
1) rather than -2n-1 is given to the MSB while computing the decimal equivalent of 1’s complement of a binary number.
A few examples of 8-bit binary numbers and their 1’s complement are given below;
Binary Number Decimal Equivalent
(i) 01010001 +81
1’s complement 10101110 -127 + 46 = -81
(ii) 10101000 -127 + 40 = -87
1’s complement 01010111 +87
Binary addition
Binary addition is preformed in the same manner as decimal addition.
The rules of binary addition are as follows:
Binary Addition Table

0+0=0
0+1=1 + 0 1
0 0 1
1+0=1 1 1 10
1 + 1 = 0 with a carry-over of 1
“Carry-overs” of binary addition are performed in the same manner as in decimal addition. With the help of the above rules addition of three or
more binary numbers can be worked out but this has little use in digital computers.
For addition of fractional binary numbers, the binary point of the two numbers are placed one below the other just like the decimal points and the
usual rules are followed.
57
A clear concept on few examples will make the procedure of binary addition:
Find the sum of the following numbers:
i) 10101 and 11011
Solution:
10101 and 11011
1111 Carry overs

10101
11011
110000
ii) ii) 11001 and 111
Solution:
11001 and 111
1111 Carry overs

11001
111
100000
iii) 10101.101 and 1101.011
Solution:
10101.101 and 1101.011
1 1 1 1 1 1 Carry overs
10101.101
1101.011
100011.000
iv) 111.0111 and 10011.001
Solution:
111.0111 and 10011.001
111 11 Carry overs
111.0111
10011.001
11010.1001
Binary subtraction
Binary subtraction is also similar to that of decimal subtraction with the difference that when 1 is subtracted from 0, it is necessary to borrow 1 from
the next higher order bit and that bit is reduced by 1 (or 1 is added to the next bit of subtrahend) and the remainder is 1.
Thus the rules of binary subtraction are as follows:
Binary Subtraction Table
0-0=0 - 0 1
0 0 1
1-0=1 1 1 0
1-1=0
57
0 - 1 = 1 with a borrow of 1
For fractional numbers, the rules of subtraction are the same with the binary point properly placed.
A clear concept on few examples will make the procedure of binary subtraction:
Subtract the following numbers:
i) 101 from 1001
Solution:
101 from 1001
1 Borrow
1001
101
100
ii) 111 from 1000

Solution:
111 from 1000
1 Borrow
1000
111
0001
iii) 1010101.10 from 1111011.11
Solution:
1010101.10 from 1111011.11
1 Borrow
1111011.11
1010101.10
100110.01
iv) 11010.101 from 101100.011
Solution:
11010.101 from 101100.011
1 1 1 Borrow
101100.011
11010.101
10001.110
Subtraction by 2’s complement
With the help of subtraction by 2’s complement method we can easily subtract two binary numbers.
The operation is carried out by means of the following steps:
57
(i) At first, 2’s complement of the subtrahend is found.
(ii) Then it is added to the minuend.
(iii) If the final carry over of the sum is 1, it is dropped and the result is positive.
(iv) If there is no carry over, the two’s complement of the sum will be the result and it is negative.
The following examples on subtraction by 2’s complement will make the procedure clear:
Evaluate:
(i) 110110 - 10110
Solution:
The numbers of bits in the subtrahend is 5 while that of minuend is 6. We make the number of bits in the subtrahend equal to that of minuend by
taking a `0’ in the sixth place of the subtrahend.
Now, 2’s complement of 010110 is (101101 + 1) i.e.101010. Adding this with the minuend.
1 10110 Minuend
1 01010 2’s complement of subtrahend
Carry over 1 1 00000 Result of addition
After dropping the carry over we get the result of subtraction to be 100000.
(ii) 10110 – 11010
Solution:
2’s complement of 11010 is (00101 + 1) i.e. 00110. Hence
Minued - 10110
2’s complement of subtrahend - 00110
Result of addition - 11100
As there is no carry over, the result of subtraction is negative and is obtained by writing the 2’s complement of 11100 i.e.(00011 + 1) or 00100.
Hence the difference is – 100.
(iii) 1010.11 – 1001.01
Solution:
2’s complement of 1001.01 is 0110.11. Hence
Minued - 1010.11
2’s complement of subtrahend - 0110.11
Carry over 1 0001.10
After dropping the carry over we get the result of subtraction as 1.10.
(iv) 10100.01 – 11011.10
Solution:
2’s complement of 11011.10 is 00100.10. Hence
57
Minued - 10100.01
Result of addition - 11000.11
As there is no carry over the result of subtraction is negative and is obtained by writing the 2’s complement of 11000.11.
Hence the required result is – 00111.01.
Subtraction by 1’s complement
In subtraction by 1’s complement we subtract two binary numbers using carried by 1’s complement.
The steps to be followed in subtraction by 1’s complement are:
i) To write down 1’s complement of the subtrahend.
ii) To add this with the minuend.
iii) If the result of addition has a carry over then it is dropped and an 1 is added in the last bit.
iv) If there is no carry over, then 1’s complement of the result of addition is obtained to get the final result and it is negative.
Evaluate:
(i) 110101 – 100101
Solution:
1’s complement of 10011 is 011010. Hence
Minued - 110101
1’s complement of subtrahend - 011010
Carry over - 1 001111
1
010000
The required difference is 10000
(ii) 101011 – 111001
Solution:
1’s complement of 111001 is 000110. Hence
Minued - 101011
1’s complement - 000110
110001
Hence the difference is – 1 1 1 0
(iii) 1011.001 – 110.10
Solution:
1’s complement of 0110.100 is 1001.011 Hence
Minued - 1011.001
Carry over - 1 0100.100
1
0100.101
Hence the required difference is 100.101
57
(iv) 10110.01 – 11010.10
Solution:
1’s complement of 11010.10 is 00101.01
10110.01
00101.01
11011.10
Hence the required difference is – 00100.01 i.e. – 100.01
Binary addition using 1’s complement
A. Addition of a positive and a negative binary number
We discuss the following cases under this.
Case I: When the positive number has greater magnitude.
In this case addition of numbers is performed after taking 1’s complement of the negative number and the end-around carry of the sum is added to the
least significant bit.
The following examples will illustrate this method in binary addition using 1’s complement:
1. Find the sum of the following binary numbers:
(i) + 1110 and - 1101
Solution:
+1110 ⇒ 01110
-1101 ⇒ 10010 (taking 1’s complement)
00000
1 carry
00001
Hence the required sum is + 0001.
(ii) + 1101 and - 1011
(Assume that the representation is in a signed 5-bit register).
Solution:
+1101 ⇒ 01101
-1011 ⇒ 10100 (taking 1’s complement)
00001
1 carry
00010
Hence the required sum is + 0010.
Case II: When the negative number has greater magnitude.
In this case the addition is carried in the same way as in case 1 but there will be non end-around carry. The sum is obtained by taking 1’s complement
of the magnitude bits of the result and it will be negative.
Find the sum of the following binary numbers represented in a sign-plus-magnitude 5-bit register:
57
(i) + 1010 and - 1100
Solution:
+1010 ⇒ 01010
-1100 ⇒ 10011 (1’s complement)
11101
Hence the required sum is – 0010.
(ii) + 0011 and - 1101.
Solution:
+0011 ⇒ 00011
-1101 ⇒ 10010 (1’s complement)
10101
B. When the two numbers are negative
For the addition of two negative numbers 1’s complements of both the numbers are to be taken and then added. In this case an end-around carry will
always appear. This along with a carry from the MSB (i.e. the 4th bit in the case of sign-plus-magnitude 5-bit register) will generate a 1 in the sign
bit. 1’s complement of the magnitude bits of the result of addition will give the final sum.
Find the sum of the following negative numbers represented in a sign-plus-magnitude 5-bit register:
(i) -1010 and -0101
Solution:
-1010 ⇒ 10101 (1’s complement)

-0101 ⇒ 11010 (1’s complement)
01111
1 carry
10000
1’s complement of the magnitude bits of sum is 1111 and the sign bit is 1.
Hence the required sum is -1111.
(ii) -0110 and -0111.
Solution:
-0110 ⇒ 11001 (1’s complement)

-0111 ⇒ 11000 (1’s complement)
10001
1 carry
10010
1’s complement of 0010 is 1101 and the sign bit is 1.
Hence the required sum is - 1101.
Binary addition using 2’s complement
When negative numbers are expressed in binary addition using 2’s complement the addition of binary numbers becomes easier. This operation is
almost similar to that in 1’s complement system and is explained with examples given below:
A. Addition of a positive number and a negative number.
57
We consider the following cases.
Case I: When the positive number has a greater magnitude
In this case the carry which will be generated is discarded and the final result is the result of addition.
In a 5-bit register find the sum of the following by using 2’s complement:
(i) -1011 and -0101
Solution:
+1011 ⇒ 01011
-0101 ⇒ 1 1 0 1 1 (2’s complement)
(Carry 1 discarded) 00110
Hence the sum is + 0110.
(ii) + 0111 and – 0011.
Solution:
+0111 ⇒ 00111
-0011 ⇒ 11101
Hence the sum is + 0100.
Case II: When the negative number is greater.
When the negative numbers is greater no carry will be generated in the sign bit. The result of addition will be negative and the final result is obtained
by taking 2’s complement of the magnitude bits of the result.
(i) + 0 0 1 1 and - 0 1 0 1
Solution:
+0011 ⇒ 00011
-0101 ⇒ 11011 (2’s complement)
11110
2’s complement of 1110 is (0001 + 0001) or 0010.
Hence the required sum is - 0010.
(ii) + 0 1 0 0 and - 0 1 1 1
Solution:
+0100 ⇒ 00100
-0111 ⇒ 11001 (2’s complement)
11101
2’s complement of 1101 is 0011.
B. When the numbers are negative.
57
When two negative numbers are added a carry will be generated from the sign bit which will be discarded. 2’s complement of the magnitude bits of
the operation will be the final sum.
(i) – 0011 and – 0101
Solution:
-0011 ⇒ 11101 (2’s complement)

-0101 ⇒ 11011 (2’s complement)
2’s complement of 1000 is (0111 + 0001) or 1000.
(ii) -0111 and – 0010.
Solution:
-0111 ⇒ 11001 (2’s complement)

-0010 ⇒ 11110 (2’s complement)
2’s complement of 0111 is 1001.
Binary Codes
Binary codes are codes which are represented in binary system with modification from the original ones. Below we will be seeing the following:
 Weighted Binary Systems

 Non Weighted Codes
Weighted Binary Systems
Weighted binary codes are those which obey the positional weighting principles, each position of the number represents a specific weight. The
binary counting sequence is an example.
Decimal 8421 2421 5211 Excess-3
0 0000 0000 0000 0011
1 0001 0001 0001 0100
2 0010 0010 0011 0101
3 0011 0011 0101 0110
4 0100 0100 0111 0111
5 0101 1011 1000 1000
6 0110 1100 1010 1001
7 0111 1101 1100 1010
8 1000 1110 1110 1011
9 1001 1111 1111 1100
8421 Code/BCDCode
The BCD (Binary Coded Decimal) is a straight assignment of the binary equivalent. It is possible to assign weights to the binary bits according to
their positions. The weights in the BCD code are8,4,2,1.
57
Example: The bit assignment 1001, can be seen by its weights to represent the decimal 9because:
1x8+0x4+0x2+1x1 =9
2421Code
This is a weighted code, its weights are 2, 4, 2 and 1. A decimal number is represented in 4-bit form and the total four bits weight is 2 + 4 + 2 + 1
= 9. Hence the 2421 code represents the decimal numbers from 0 to9.
5211Code
This is a weighted code, its weights are 5, 2, 1 and 1. A decimal number is represented in 4-bit form and the total four bits weight is 5 + 2 + 1 + 1
= 9. Hence the 5211 code represents the decimal numbers from 0 to9.
Reflective Code
A code is said to be reflective when code for 9 is complement for the code for 0, and so is for 8 and 1 codes, 7 and 2, 6 and 3, 5 and 4. Codes
2421, 5211, and excess-3 are reflective, whereas the 8421 code isnot.
Sequential Codes
A code is said to be sequential when two subsequent codes, seen as numbers in binary representation, differ by one. This greatly aids
mathematical manipulation of data. The 8421 and Excess-3 codes are sequential, whereas the 2421 and 5211 codes are not.
Non Weighted Codes
Non weighted codes are codes that are not positional weighted. That is, each position within the binary number is not assigned a fixed value.
Excess-3Code
Excess-3 is a non weighted code used to express decimal numbers. The code derives its name from the fact that each binary code is the
corresponding 8421 code plus0011(3).
Example: 1000 of 8421 = 1011 inExcess-3
Gray Code
The gray code belongs to a class of codes called minimum change codes, in which only one bit in the code changes when moving from one code
to the next. The Gray code is non-weighted code, as the position of bit does not contain any weight. The gray code is a reflective digital code
which has the special property that any two subsequent numbers codes differ by only one bit. This is also called a unit-distance code. In digital
Gray code has got a specialplace.
DecimalNumber BinaryCode GrayCode

0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
57
13 1101 1011
14 1110 1001
15 1111 1000
Binary to Gray Conversion
• Gray Code MSB is binary code MSB.

• Gray Code MSB-1 is the XOR of binary code MSB andMSB-1.
• MSB-2 bit of gray code is XOR of MSB-1 and MSB-2 bit of binary code.
• MSB-N bit of gray code is XOR of MSB-N-1 and MSB-N bit of binary code.
Error Detecting and Correction Codes
For reliable transmission and storage of digital data, error detection and correction is required. Below are a few examples of codes which permit
error detection and error correction after detection.
Error Detecting Codes

When data is transmitted from one point to another, like in wireless transmission, or it is just stored, like in hard disks and memories, there are
chances that data may get corrupted. To detect these data errors, we use special codes, which are error detection codes.
Parity
In parity codes, every data byte, or nibble (according to how user wants to use it) is checked if they have even number of ones or even number of
zeros. Based on this information an additional bit is appended to the original data. Thus if we consider 8-bit data, adding the parity bit will make it
9 bit long.At the receiver side, once again parity is calculated and matched with the received parity (bit 9), and if they match, data is ok, otherwise
data is corrupt.
There are two types of parity:
• Even parity: Checks if there is an even number of ones; if so, parity bit is zero. When the number of ones is odd then parity bit is set
to1.
• Odd Parity: Checks if there is an odd number of ones; if so, parity bit is zero. When number of ones is even then parity bit is set to1.
Checksums
The parity method is calculated over byte, word or double word. But when errors need to be checked over 128 bytes or more (basically blocks of
data), then calculating parity is not the right way. So we have checksum, which allows checking for errors on block of data. There are many
variations of checksum.
• Adding all bytes
• CRC
• Fletcher's checksum
• Adler-32
The simplest form of checksum, which simply adds up the asserted bits in the data, cannot detect a number of types of errors. In particular, such a
checksum is not changed by:
• Reordering of the bytes in the message
• Inserting or deleting zero-valued bytes
• Multiple errors which sum to zero
Example of Checksum: Given 4 bytes of data (can be done with any number of bytes): 25h, 62h, 3Fh,52h
• Adding all bytes together gives118h.
• Drop the Carry Nibble to give you18h.
Get the two's complement of the 18h to get E8h. This is the checksum byte
To Test the Checksum byte simply adds it to the original group of bytes. This should give you 200h.
Drop the carry nibble again giving 00h. Since it is 00h this means the checksum means the bytes were probably not changed.
Error-Correcting Codes
Error-correcting codes not only detect errors, but also correct them. This is used normally in Satellite communication, where turn-around delay is
very high as is the probability of data getting corrupt.
57
ECC (Error correcting codes) are used also in memories, networking, Hard disk, CDROM, DVD etc. Normally in networking chips (ASIC), we
have 2 Error detection bits and 1 Error correction bit.
HammingCode
Hamming code adds a minimum number of bits to the data transmitted in a noisy channel, to be able to correct every possible one-bit error. It can
detect (not correct) two-bits errors and cannot distinguish between 1-bit and 2-bits inconsistencies. It can't - in general - detect 3(or more)-bits
errors.
The idea is that the failed bit position in an n-bit string (which we'll call X) can be represented in binary with log2(n) bits, hence we'll try to get it
adding just log2(n)bits.
First, we set m = n + log2(n) to the encoded string length and we number each bit position starting from 1 through m. Then we place these
additional bits at power-of-two positions, that is 1, 2, 4, 8..., while remaining ones (3, 5, 6, 7...) hold the bit string in the originalorder.
Now we set each added bit to the parity of a group of bits. We group bits this way: we form a group for every parity bit, where the following
relationholds:
position(bit) AND position(parity) =position(parity)

(Note that: AND is the bit-wise boolean AND; parity bits are included in the groups; each bit can belong to one or moregroups.)
So bit 1 groups bits 1, 3, 5, 7... while bit 2 groups bits 2, 3, 6, 7, 10... , bit 4 groups bits 4, 5, 6,7,
12, 13... and soon.
Thus, by definition, X (the failed bit position defined above) is the sum of the incorrect parity bits positions (0 for noerrors).
To understand why it is so, let's call Xn the nth bit of X in binary representation. Now consider that each parity bit is tied to a bit of X: parity1 ->
X1, parity2 -> X2, parity4 -> X3, parity8 -> X4 and so on - for programmers: they are the respective AND masks -. By construction, the failed bit
makes fail only the parity bits which correspond to the 1s in X, so each bit of X is 1 if the corresponding parity is wrong and 0 if it iscorrect.
Note that the longer the string, the higher the throughput n/m and the lower the probability that no more than one bit fails. So the string to be sent
should be broken into blocks whose length depends on the transmission channel quality (the cleaner the channel, the bigger the block). Also,
unless it's guaranteed that at most one bit per block fails, a checksum or some other form of data integrity check should beadded.
AlphanumericCodes
The binary codes that can be used to represent all the letters of the alphabet, numbers and mathematical symbols, punctuation marks, are known as
alphanumeric codes or character codes. These codes enable us to interface the input-output devices like the keyboard, printers, video displays with
thecomputer.
ASCIICode
ASCII stands for American Standard Code for Information Interchange. It has become a world standard alphanumeric code for microcomputers
and computers. It is a 7-bit code representing 27 = 128 different characters. These characters represent 26 upper case letters (A to Z), 26
lowercase letters (a to z), 10 numbers (0 to 9), 33 special characters and symbols and 33 controlcharacters.
The 7-bit code is divided into two portions, The leftmost 3 bits portion is called zone bits and the 4-bit portion on the right is called numericbits.
An 8-bit version of ASCII code is known as USACC-II 8 or ASCII-8. The 8-bit version can represent a maximum of 256characters.
EBCDICCode
EBCDIC stands for Extended Binary Coded Decimal Interchange. It is mainly used with large computer systems like mainframes. EBCDIC is an
8-bit code and thus accomodates up to 256 characters. An EBCDIC code is divided into two portions: 4 zone bits (on the left) and 4 numeric bits
(on theright).
Boolean Algebra
Boolean algebra is a type of algebra that is created by operating the binary system. In the year 1854, George Boole, an English mathematician,
proposed this algebra. This is a variant of Aristotle’s propositional logic that uses the symbols 0 and 1, or True and False. Boolen algebra is
concerned with binary variables and logic operations.
57
Boolean Algebra is fundamental in the development of digital electronics systems as they all use the concept of Boolean Algebra to execute
commands. Apart from digital electronics this algebra also finds its application in Set Theory, Statistics, and other branches of mathematics.
In this we learn about, basic Boolean operations, Boolean expressions, Truth Tables, Boolean laws, and others in detail.
Boolean Algebra Operations

There are various operations that are used in Boolean algebra but the basic operations that form the base of Boolean Algebra are,
 Negation or NOT Operation

 Conjunction or AND Operation
 Disjunction or OR Operation

These operations have their own symbols and precedence and the table added below shows the symbol and the precedence of these operators.
Operator Symbol Precedence
NOT ‘ (or) ⇁ First
AND . (or) ∧ Second
OR + (or) ∨ Third
We can easily define these operations using two boolean variables. Let’s take two boolean variables A and B that can have any of the two
values 0 or 1, i.e. they can be either OFF or ON. Then these operations are explained as,
Negation or NOT Operation
Using the NOT operation reverse the value of the Boolean variable from 0 to 1 or vice-versa. This can be understood as:
 If A = 1, then using NOT operation we have (A)’ = 0

 If A = 0, then using the NOT operation we have (A)’ = 1
We also represent the negation operation as ~A, i.e if A = 1, ~A = 0
Conjunction or AND Operation
Using the AND operation satisfies the condition if both the value of the individual variables are true and if any of the value is false then this
operation gives the negative result. This can be understood as,
 If A = True, B = True, then A . B = True

 If A = True, B = False, Or A = false, B = True, then A . B = False
 If A = False, B = False, then A . B = False
Disjunction (OR) Operation
Using the OR operation satisfies the condition if any value of the individual variables are true, it only gives a negative result if both the values
are false. This can be understood as,
 If A = True, B = True, then A + B = True

 If A = True, B = False, Or A = false, B = True, then A + B = True
 If A = False, B = False, then A + B = False
Boolean Expression and Variables
Boolean expression is an expression that produces a Boolean value when evaluated, i.e. it produces either a true value or a false value. Whereas
boolean variables are variables that store Boolean numbers.
57
P + Q = R is a Boolean phrase in which P, Q, and R are Boolean variables that can only store two values: 0 and 1. The 0 and 1 are the synonyms
for false and True and are used in Boolen Algebra, sometimes we also use “Yes” in place of True and “No” in place of False.
Thus, we can say that statements using Boolean variables and operating on Boolean operations are Boolean Expressions. Some examples of
Boolean expressions are,
 A + B = True
 A.B = True
 (A)’ = False
Boolean Algebra Terminologies

There are various terminologies related to Boolean Algebra, which are used to explain various parameters of Boolen Algebra. That includes,
 Boolean Algebra
 Boolean Variables
 Boolean Function
 Literal
 Complement
 Truth Table
Now, we will discuss the important terminologies of Boolean algebra in the article below,
Boolean Algebra
The branch of algebra that deals with binary operations or logical operations is called Boolean Algebra.
Boolean Variables
Variables used in Boolean algebra that store the logical value of 0 and 1 are called the boolean variables. They are used to store either true or
false values.
Boolean Function
A function of the Boolean Algebra that is formed by the use of Boolean variables and Boolean operators is called the Boolean function.
Literal
A variable or the complement of the variable in Boolean Algebra is called the Literal.
Complement
The inverse of the boolean variable is called the complement of the variable. The complement of 0 is 1 and the complement of 1 is 0. It is
represented by ‘ over the variable.
Truth Table
Table containing all the possible values of the logical variables and the combination of the variable along with the given operation is called the
truth table. The number of rows in the truth table depends on the total boolean variables used in that function. It is given by using the formula,
57
Number of Rows in Truth Table = 2n
where “n” is the number of boolean variables used.
Truth Tables in Boolean Algebra

A truth table represents all the combinations of input values and outputs in a tabular manner. All the possibilities of the input and output are
shown in it and hence the name truth table. In logic problems, truth tables are commonly used to represent various cases. T or 1 denotes ‘True’ &
F or 0 denotes ‘False’ in the truth table.
Example: Draw the truth table of the conditions A + B and A.B where A and b are boolean variables.
Solution:
The required Truth Table is,
A B X=A+B Y = A.B
T T T T
T F T F
F T T F
F F F F
Laws for Boolean Algebra

The basic laws of the Boolean Algebra are added in the table added below,
Law OR form AND form
Identity Law P+0=P P.1 = P
Idempotent Law P+P=P P.P = P
Commutative Law P+Q=Q+P P.Q = Q.P
Associative Law P + (Q + R) = (P + Q) + R P.(Q.R) = (P.Q).R
Distributive Law P + QR = (P + Q).(P + R) P.(Q + R) = P.Q + P.R
Inversion Law (A’)’ = A (A’)’ = A
De Morgan’s Law (P + Q)’ = (P)’.(Q)’ (P.Q)’ = (P)’ + (Q)’
Let’s learn about these laws in detail.
Identity Law
57
In the Boolean Algebra, we have identity elements for both AND(.) and OR(+) operations. The identity law state that in boolean algebra we have
such variables that on operating with AND and OR operation we get the same result, i.e.
 A+0=A
 A.1 = A
Commutative Law
Binary variables in Boolean Algebra follow the commutative law. This law states that operating boolean variables A and B is similar to
operating boolean variables B and A. That is,
 A. B = B. A
 A+B=B+A
Associative Law
Associative law state that the order of performing Boolean operator is illogical as their result is always the same. This can be understood as,
 (A.B).C=A.(B.C)
 ( A + B ) + C = A + ( B + C)
Distributive Law
Boolean Variables also follow the distributive law and the expression for Distributive law is given as:
 A . ( B + C) = (A . B) + (A . C)
Inversion Law
Inversion law is the unique law of Boolean algebra this law states that, the complement of the complement of any number is the number itself.
 (A’)’ = A
Apart from these other laws are mentioned below:
AND Law
AND law of the Boolean algebra uses AND operator and the AND law is,
 A.0=0
 A.1=A
 A.A=A
OR Law
OR law of the Boolean algebra uses OR operator and the OR law is,
 A+0=A
 A+1=1
 A+A=A
De Morgan’s Laws are also called Demorgan’s Theorem. They are the most important laws in Boolen Algebra and these are added below under
the heading Boolean Algebra Theorem
Boolean Algebra Theorems

There are two basic theorems of great importance in Boolean Algebra, which are De Morgan’s First Laws, and De Morgan’s Second Laws.
These are also called De Morgan’s Theorems. Now let’s learn about both in detail.
57
De Morgan’s First laws
De Morgan’s Law states that,
Statement: The complement of the product (AND) of two Boolean variables (or expressions) is equal to the sum(OR) of the complement of each
Boolean variable (or expression).
(P.Q)’ = (P)’ + (Q)’
The truth table for the same is given below:
P Q (P)’ (Q)’ (P.Q)’ (P)’ + (Q)’
T T F F F F
T F F T T T
F T T F T T
F F T T T T
We can clearly see that truth values for (P.Q)’ are equal to truth values for (P)’ + (Q)’, corresponding to the same input. Thus, De Morgan’s First
Law is true.
De Morgan’s Second laws
Statement: The Complement of the sum (OR) of two Boolean variables (or expressions) is equal to the product(AND) of the complement of
each Boolean variable (or expression).
(P + Q)’ = (P)’.(Q)’
Proof :
The truth table for the same is given below:
P Q (P)’ (Q)’ (P + Q)’ (P)’.(Q)’
T T F F F F
T F F T F F
F T T F F F
F F T T T T
We can clearly see that truth values for (P + Q)’ are equal to truth values for (P)’.(Q)’, corresponding to the same input. Thus, De Morgan’s
Second Law is true.
Solved Examples on Boolean Algebra

Example 1: Draw Truth Table for P + P.Q = P
57
Solution:
The truth table for P + P.Q = P
P Q P.Q P + P.Q
T T T T
T F F T
F T F F
F F F F
In the truth table, we can see that the truth values for P + P.Q is exactly the same as P.
Example 2: Draw Truth Table for P.Q + P + Q
Solution:
The truth table for P.Q + P + Q
P Q P. P.Q + P + Q
Q
T T T T
T F F T
F T F T
F F F F
FAQs on Boolean Algebra
1. What is Boolean Algebra?
Boolean Algebra also called Logical Algebra is a branch of mathematics that deals with Boolean Varaibles such as, 0 and
1.
2. What are Main Boolean Operators?
There are three main Boolean Operators that are,
 AND (Conjunction)
 OR (Disjunction)
 NOT (Negation)
3. What are Applications of Boolean Algebra?
57
Boolean Algebra has various applications. It is used to simplify logical circuits that are the backbone of modern
technology.
4. What does “0” Represent in Boolean Algebra?
The “0” in Boolen Algebra represent a False condition or it represent the Switch Off condition.
5. What does “1” Represent in Boolean Algebra?
The “1” in Boolen Algebra represent a Truecondition or it represent the Switch On condition.
6. What is Boolean Algebra laws?
Boolean algebra laws are fundamental rules for working with true/false or binary variables. Key laws include:
– Identity: A AND 1 = A, A OR 0 = A
– Null: A AND 0 = 0, A OR 1 = 1
– Complement: A AND A’ = 0, A OR A’ = 1
– Commutative: A AND B = B AND A, A OR B = B OR A
– Distributive: A AND (B OR C) = (A AND B) OR (A AND C), A OR (B AND C) = (A OR B) AND (A OR C)
– De Morgan’s: (A AND B)’ = A’ OR B’, (A OR B)’ = A’ AND B’
These laws are vital for simplifying logical expressions and designing digital circuits.
7. What is Boolean Algebra laws?
Boolean algebra typically encompasses 12 fundamental rules, which are:
1. Identity Law for AND: A AND 1 = A
2. Identity Law for OR: A OR 0 = A
3. Null Law for AND: A AND 0 = 0
4. Null Law for OR: A OR 1 = 1
5. Complement Law for AND: A AND A’ = 0
6. Complement Law for OR: A OR A’ = 1
7. Idempotent Law for AND: A AND A = A
8. Idempotent Law for OR: A OR A = A
9. Inverse Law for AND: A AND A’ = 0
10. Inverse Law for OR: A OR A’ = 1
57
11. Commutative Law for AND: A AND B = B AND A
12. Commutative Law for OR: A OR B = B OR A
8. What are the 5 laws of Boolean algebra?
Boolean algebra is governed by five primary laws, which serve as the foundation for manipulating logical expressions:
1. Identity Law for AND: The AND operation with true (1) leaves a variable unchanged.
– A AND 1 = A
2. Identity Law for OR: The OR operation with false (0) leaves a variable unchanged.
– A OR 0 = A
3. Complement Law for AND: The AND operation with false (0) results in false.
– A AND 0 = 0
4. Complement Law for OR: The OR operation with true (1) results in true.
– A OR 1 = 1
5. Idempotent Law: Repeated operations on a variable with itself do not change its value.
– A AND A = A
– A OR A = A
9. What are the 3 laws in Boolean logic?
Boolean logic, also known as Boolean algebra, is governed by three fundamental laws:
Commutative Law: This law states that the order of operands in an operation does not affect the result.
For AND: A AND B = B AND A
For OR: A OR B = B OR A
Associative Law: This law dictates that the grouping of operands in an operation does not change the result.
For AND: (A AND B) AND C = A AND (B AND C)
For OR: (A OR B) OR C = A OR (B OR C)
Distributive Law: This law describes how one operation (AND or OR) distributes over the other operation.
For AND over OR: A AND (B OR C) = (A AND B) OR (A AND C)
For OR over AND: A OR (B AND C) = (A OR B) AND (A OR C)
10. What is De Morgan’s theorem?
De Morgan’s theorem is a fundamental principle in Boolean algebra that provides a way to simplify the complement
(negation) of a logical expression involving both AND and OR operations. There are two forms of De Morgan’s theorem,
one for negating an AND operation and another for negating an OR operation. These theorems are named after the British
mathematician and logician Augustus De Morgan.
De Morgan’s Theorem for AND Operations:
The theorem states that the complement of the AND operation between two or more variables is equivalent to the OR
operation of their complements.
Mathematically, for variables A and B (and possibly more):
57
– NOT (A AND B) = (NOT A) OR (NOT B)
This means that if you want to find the complement of the AND operation of two or more variables, you can take the
complement of each variable individually and then use the OR operation between their complements.
De Morgan’s Theorem for OR Operations:
The theorem states that the complement of the OR operation between two or more variables is equivalent to the AND
operation of their complements.
Mathematically, for variables A and B (and possibly more):
– NOT (A OR B) = (NOT A) AND (NOT B)
This means that if you want to find the complement of the OR operation of two or more variables, you can take the
complement of each variable individually and then use the AND operation between their complements.
Minterms andMaxterms
Any boolean expression may be expressed in terms of either minterms or maxterms. To do this we must first define the concept of a
literal. A literal is a single variable within a term which may or may not be complemented. For an expression with N variables,
minterms and maxterms are defined as follows:
A minterm is the product of N distinct literals where each literal occurs exactly once.
A maxterm is the sum of N distinct literals where each literal occurs exactly once For a two-variable expression, the minterms and maxterms are
asfollows
For a three-variable expression, the minterms and maxterms are asfollows
X Y Z Minterm Maxterm
0 0 0 X'.Y'.Z' X+Y+Z
0 0 1 X'.Y'.Z X+Y+Z'
0 1 0 X'.Y.Z' X+Y'+Z
0 1 1 X'.Y.Z X+Y'+Z'
1 0 0 X.Y'.Z' X'+Y+Z
1 0 1 X.Y'.Z X'+Y+Z'
1 1 0 X.Y.Z' X'+Y'+Z
1 1 1 X.Y.Z X'+Y'+Z'
This allows us to represent expressions in either Sum of Products or Product of Sums forms
Sum Of Products(SOP)
The Sum of Products form represents an expression as a sum ofminterms.
F(X, Y, ...) = Sum(ak.mk)
where ak is 0 or 1 and mk is aminterm.
To derive the Sum of Products form from a truth table, OR together all of the minterms which give a value of1.
Example -SOP
Consider the truthtable
X Y F Minterm
0 0 0 X'.Y'
0 1 0 X'Y
57
1 0 1 X.Y'
1 1 1 X.Y
Here SOP is f(X.Y) = X.Y' +X.Y
57
Product Of Sum(POS)
The Product of Sums form represents an expression as a product of maxterms. F(X, Y, .......) = Product (b k + Mk), where bk is 0 or
1 and Mk is amaxterm.
To derive the Product of Sums form from a truth table, AND together all of themaxterms
which give a value of0.
Example -POS
Consider the truth table from the previousexample.
X Y F Maxterm
0 0 1 X+Y
0 1 0 X+Y'
1 0 1 X'+Y
1 1 1 X'+Y'
Here POS is F(X,Y) =(X+Y')
Exercise
Give the expression represented by the following truth table in both Sum of Products and Product of Sumsforms.
X Y Z F(X,Y,X)
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
57
Conversion between POS andSOP
Conversion between the two forms is done by application of DeMorgansLaws.
Simplification
As with any other form of algebra you have encountered, simplification of expressions can be performed with Booleanalgebra.
Example
Show that X.Y.Z' + X'.Y.Z' + Y.Z = Y X.Y.Z' + X'.Y.Z' + Y.Z
= Y.Z' + Y.Z =Y
Example
Show that (X.Y' + Z).(X + Y).Z = X.Z +Y.Z
(X.Y' + Z).(X +Y).Z

= (X.Y' + Z.X +Y'.Z).Z
= X.Y'Z + Z.X +Y'.Z
= Z.(X.Y' + X +Y')
=Z.(X+Y')
Digital LogicGates
LogicGates
A logic gate is an electronic circuit/device which makes the logical decisions. To arrive at this decisions, the most common logic gates used are
OR, AND, NOT, NAND, and NOR gates. The NAND and NOR gates are called universal gates. The exclusive-OR gate is another logic gate
which can be constructed using AND, OR and NOTgate.
Logic gates have one or more inputs and only one output. The output is active only for certain input combinations. Logic gates are the building
blocks of any digital circuit. Logic gates arealso
called switches. With the advent of integrated circuits, switches have been replaced by TTL (Transistor Transistor Logic) circuits and CMOS
circuits. Here I give example circuits on how to construct simplesgates.
SymbolicLogic
Boolean algebra derives its name from the mathematician George Boole. Symbolic Logic uses values, variables andoperations.
Inversion
A small circle on an input or an output indicates inversion. See the NOT, NAND and NOR gates given below forexamples.
Multiple InputGates
Given commutative and associative laws, many logic gates can be implemented with more than two inputs, and for reasons of space in
circuits, usually multiple input, complex gates are made. You will encounter such gates in real world (maybe you could analyze an
ASIC lib to findthis).
GatesTypes
 AND
 OR
 NOT
 BUF
 NAND
 NOR
 XOR
 XNOR
ANDGate
61
The AND gate performs logical multiplication, commonly known as AND function. The AND gate has two or more inputs and single output.
The output of AND gate is HIGH only when all its inputs are HIGH (i.e. even if one input is LOW, Output will beLOW).
If X and Y are two inputs, then output F can be represented mathematically as F = X.Y, Here dot (.) denotes the AND operation. Truth table and
symbol of the AND gate is shown in the figurebelow.
Symbol
TruthTable
X Y F=(X.Y)
0 0 0
0 1 0
1 0 0
1 1 1
Two input AND gate using "diode-resistor" logic is shown in figure below, where X, Y are inputs and F is theoutput.
Circuit
71
If X = 0 and Y = 0, then both diodes D1 and D2 are forward biased and thus both diodes conduct and pull Flow.
If X = 0 and Y = 1, D2 is reverse biased, thus does not conduct. But D1 is forward biased, thus conducts and thus pulls Flow.
If X = 1 and Y = 0, D1 is reverse biased, thus does not conduct. But D2 is forward biased, thus conducts and thus pulls Flow.
If X = 1 and Y = 1, then both diodes D1 and D2 are reverse biased and thus both the diodes are in cut-off and thus there is no drop in voltage at F. Thus F
isHIGH.
Switch Representation of ANDGate
In the figure below, X and Y are two switches which have been connected in series (or just cascaded) with the load LED and source battery. When both
switches are closed, current flows toLED.
Three Input ANDgate

Since we have already seen how a AND gate works and I will just list the truth table of a 3 input AND gate. The figure below shows its symbol and
truthtable.
Circuit
TruthTable
X Y Z F=X.Y.Z
0 0 0 0
0 0 1 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
ORGate
The OR gate performs logical addition, commonly known as OR function. The OR gate has two or more inputs and single output. The output of OR gate
is HIGH only when any one of its inputs are HIGH (i.e. even if one input is HIGH, Output will beHIGH).
71
If X and Y are two inputs, then output F can be represented mathematically as F = X+Y. Here plus sign (+) denotes the OR operation. Truth table and
symbol of the OR gate is shown in the figurebelow.
Symbol
TruthTable
X Y F=(X+Y)
0 0 0
0 1 1
1 0 1
1 1 1
Two input OR gate using "diode-resistor" logic is shown in figure below, where X, Y are inputs and F is theoutput.
Circuit
If X = 0 and Y = 0, then both diodes D1 and D2 are reverse biased and thus both the diodes are in cut-off and thus F islow.
If X = 0 and Y = 1, D1 is reverse biased, thus does not conduct. But D2 is forward biased, thus conducts and thus pulling F toHIGH.
If X = 1 and Y = 0, D2 is reverse biased, thus does not conduct. But D1 is forward biased, thus conducts and thus pulling F toHIGH.
If X = 1 and Y = 1, then both diodes D1 and D2 are forward biased and thus both the diodes conduct and thus F isHIGH.
Switch Representation of ORGate
In the figure, X and Y are two switches which have been connected in parallel, and this is connected in series with the load LED and source battery. When
both switches are open, current does not flow to LED, but when any switch is closed then currentflows.
71
Three Input ORgate
Since we have already seen how an OR gate works, I will just list the truth table of a 3-input OR gate. The figure below shows its circuit and truthtable.
TruthTable
X Y Z F=X+Y+Z
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
NOTGate
The NOT gate performs the basic logical function called inversion or complementation. NOT gate is also called inverter. The purpose of this gate is to
convert one logic level into the opposite logic level. It has one input and one output. When a HIGH level is applied to an inverter, a LOW level appears on
its output and viceversa.
If X is the input, then output F can be represented mathematically as F = X', Here apostrophe (') denotes the NOT (inversion) operation. There are a couple
of other ways to represent inversion, F= !X, here ! represents inversion. Truth table and NOT gate symbol is shown in the figurebelow.
Symbol
TruthTable
X Y=X'
0 1
1 0
71
NOT gate using "transistor-resistor" logic is shown in the figure below, where X is the input and F is theoutput.
Circuit
When X = 1, The transistor input pin 1 is HIGH, this produces the forward bias across the emitter base junction and so the transistor conducts. As the
collector current flows, the voltage drop across RL increases and hence F isLOW.
When X = 0, the transistor input pin 2 is LOW: this produces no bias voltage across the transistor base emitter junction. Thus Voltage at F isHIGH.
BUFGate
Buffer or BUF is also a gate with the exception that it does not perform any logical operation on its input. Buffers just pass input to output. Buffers are
used to increase the drive strength or sometime just to introduce delay. We will look at this in detaillater.
If X is the input, then output F can be represented mathematically as F = X. Truth table and symbol of the Buffer gate is shown in the figurebelow.
Symbol
TruthTable
X Y=X
0 0
1 1
NANDGate
NAND gate is a cascade of AND gate and NOT gate, as shown in the figure below. It has two or more inputs and only one output. The output of NAND
gate is HIGH when any one of its input is LOW (i.e. even if one input is LOW, Output will beHIGH).
NAND From AND andNOT
71
If X and Y are two inputs, then output F can be represented mathematically as F = (X.Y)', Here dot (.) denotes the AND operation and (') denotes
inversion. Truth table and symbol of the N AND gate is shown in the figurebelow.
Symbol
TruthTable
X Y F=(X.Y)'
0 0 1
0 1 1
1 0 1
1 1 0
NOR Gate
NOR gate is a cascade of OR gate and NOT gate, as shown in the figure below. It has two or more inputs and only one output. The output of NOR gate is
HIGH when any all its inputs are LOW (i.e. even if one input is HIGH, output will beLOW).
Symbol
If X and Y are two inputs, then output F can be represented mathematically as F = (X+Y)'; here plus (+) denotes the OR operation and (') denotes
inversion. Truth table and symbol of the NOR gate is shown in the figurebelow.
TruthTable
71
X Y F=(X+Y)'
0 0 1
0 1 0
1 0 0
1 1 0
XORGate
An Exclusive-OR (XOR) gate is gate with two or three or more inputs and one output. The output of a two-input XOR gate assumes a HIGH state if one
and only one input assumes a HIGH state. This is equivalent to saying that the output is HIGH if either input X or input Y is HIGH exclusively, and LOW
when both are 1 or 0simultaneously.
If X and Y are two inputs, then output F can be represented mathematically asF= X Y, Here denotes the XOR operation. Y and is equivalent to
X.Y' + X'.Y. Truth table and symbol of the XOR gate is shown in the figurebelow.
XOR From Simplegates
Symbol
TruthTable
X Y F=(X Y)
0 0 0
0 1 1
1 0 1
1 1 0
XNOR Gate
An Exclusive-NOR (XNOR) gate is gate with two or three or more inputs and one output. The output of a two-input XNOR gate assumes a HIGH state if
all the inputs assumes same state. This is equivalent to saying that the output is HIGH if both input X and input Y is HIGH exclusively or same as input X
and input Y is LOW exclusively, and LOW when both are notsame.
If X and Y are two inputs, then output F can be represented mathematically asF= X Y, Here denotes the XNOR operation. Y and is equivalent
to X.Y + X'.Y'. Truth table and symbol of the XNOR gate is shown in the figurebelow.
71
Symbol
TruthTable
X Y F=(X Y)'
0 0 1
0 1 0
1 0 0
1 1 1
UniversalGates
Universal gates are the ones which can be used for implementing any gate like AND, OR and NOT, or any combination of these basic gates; NAND and
NOR gates are universal gates. But there are some rules that need to be followed when implementing NAND or NOR basedgates.
To facilitate the conversion to NAND and NOR logic, we have two new graphic symbols for thesegates.
NANDGate
NOR Gate
Realization of logic function usingNANDgates
AnylogicfunctioncanbeimplementedusingNANDgates.Toachievethis,firstthelogic function has to be written in Sum of Product (SOP) form. Once logic
function is converted to SOP, then is very easy to implement using NAND gate. In other words any logic circuit with AND gates in first level and OR
gates in second level can be converted into a NAND-NAND gatecircuit.
71
Consider the following SOPexpression
F = W.X.Y + X.Y.Z +Y.Z.W
The above expression can be implemented with three AND gates in first stage and one OR gate in second stage as shown infigure.
If bubbles are introduced at AND gates output and OR gates inputs (the same for NOR gates), the above circuit becomes as shown infigure.
Now replace OR gate with input bubble with the NAND gate. Now we have circuit which is fully implemented with just NANDgates.
Realization of logic gates usingNANDgates
Implementing an inverter using NANDgate
Input Output Rule

(X.X)' =X' Idempotent
71
Implementing AND using NANDgates
Input Output Rule
((XY)'(XY)')' =((XY)')' Idempotent
=(XY) Involution
Implementing OR using NANDgates
Input Output Rule
((XX)'(YY)')' =(X'Y')' Idempotent
=X''+Y'' DeMorgan
=X+Y Involution
Implementing NOR using NANDgates
Input Output Rule
((XX)'(YY)')' =(X'Y')' Idempotent
=X''+Y'' DeMorgan
=X+Y Involution
=(X+Y)' Idempotent
71
Realization of logic function using NORgates
Any logic function can be implemented using NOR gates. To achieve this, first the logic function has to be written in Product of Sum (POS) form. Once it
is converted to POS, then it's very easy to implement using NOR gate. In other words any logic circuit with OR gates in first level and AND gates in
second level can be converted into a NOR- NOR gatecircuit.
Consider the following POS expression F = (X+Y) .(Y+Z)
The above expression can be implemented with three OR gates in first stage and one AND gate in second stage as shown infigure.
If bubble are introduced at the output of the OR gates and the inputs of AND gate, the above circuit becomes as shown infigure.
Now replace AND gate with input bubble with the NOR gate. Now we have circuit which is fully implemented with just NORgates.
Realization of logic gates usingNORgates
71
Implementing an inverter using NORgate
Input Output Rule
(X+X)' =X' Idempotent
Implementing AND using NORgates
Input Output Rule
((X+X)'+(Y+Y)')' =(X'+Y')' Idempotent
=X''.Y'' DeMorgan
=(X.Y) Involution
Implementing OR using NORgates
Input Output Rule
((X+Y)'+(X+Y)')' =((X+Y)')' Idempotent
=X+Y Involution
Implementing NAND using NORgates
Input Output Rule
((X+Y)'+(X+Y)')' =((X+Y)')' Idempotent
=X+Y Involution
=(X+Y)' Idempotent
71
CANONICAL AND STANDARDFORMS
A binary variable may appear either in its normal form (x) or in its complement form(x_).Now consider two binary variables x and y combined with an
AND operation.Sinceeachvariable may appear in either form, there are four possible combinations: x_y_, x_y,xy_,and xy. Each of these four AND terms
is called a minterm, or a standard product.Inasimilar manner, n variables can be combined to form 2n minterms. The 2n different mintermsmay be
determined by a method similar to the one shown in Table 2.3 for three variables.Thebinarynumbersfrom0to2n-1arelistedunderthenvariables.Eachminterm
is obtained from an AND term of the n variables, with each variable being primed if the corresponding bit of the binary number is a 0 and unprimed if a 1.
A symbolfor each minterm is also shown in the table and is of the form mj, where the subscriptjdenotes the decimal equivalent of the binary number of the
mintermdesignated.In a similar fashion, n variables forming an OR term, with each variable being primedor unprimed, provide 2 n possible combinations,
called maxterms, or standard sums.The eight maxterms for three variables, together with their symbolic designations, are listedin Table 2.3 . Any 2 n
maxterms for n variables may be determined similarly. It is importantto note that (1) 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, and (2)each maxterm is the complement of its corresponding minterm and
viceversa.A Boolean function can be expressed algebraically from a given truth table by forminga minterm for each combination of the variables
that produces a 1 in the functionand then taking the OR of all those terms. For example, the function f1 in Tableisdetermined by expressing the
combinations 001, 100, and 111 as x_y_z, xy_z_,andxyz,respectively. Since each one of these minterms results in f1 = 1,
wehavef1=x_y_z+xy_z_+xyz=m1+m4+m7
ERROR DETECTION ANDCORRECTION

The dynamic physical interaction of the electrical signals affecting the data path of amemory unit may cause occasional errors in storing and retrieving the
binary information.The reliability of a memory unit may be improved by employing error‐detecting and error‐correcting codes. The most common error
detection scheme is the parity bit.(See Section 3.9.) A parity bit is generated and stored along with the data word in memory. The parityof the word is
checked after reading it from memory. The data wordis accepted if the parity of the bits read out is correct. If the parity checked results in an
inversion, an error is detected, but it cannot becorrected.An error‐correcting code generates multiple parity check bits that are stored with the data word
in memory. Each check bit is a parity over a group of bits in the data word. When the word is read back from memory, the associated parity bits are also
read from memory and compared with a new set of check bits generated from the data
that have been read. If the check bits are correct, no error has occurred. If the check bits do not match the stored parity, they generate a unique pattern,
called a syndrome,that can be used to identify the bit that is in error. A single error occurs when a bit changes in value from 1 to 0 or from 0 to 1 during
the write or read operation. If thespecific bit in error is identified, then the error can be corrected bycomplementing the erroneousbit.
HammingCode
71
One of the most common error‐correcting codes used in RAMs was devised by R. W.Hamming. In the Hamming code, k parity bits are added to an n ‐bit
data word, forminga new word of n + k bits. The bit positions are numbered in sequence from 1 to n+k.Those positions numbered as a power of 2 are
reserved for the parity bits. The remainingbits are the data bits. The code can be used with words of any length. Before giving the general characteristics
of the code, we will illustrate its operation with a data wordof eightbits. Consider, for example:the 8‐bit data word 11000100. We include 4 parity bits
with the 8‐bit word and arrange the 12 bits asfollows:
Bitposition: 1 2 3 4 5 6 7 8 9 10 11 12
P1 P2 1 P4 1 0 0 P8 0 1 0 0
71
KarnaughMaps
Karnaugh maps provide a systematic method to obtain simplified sum-of-products (SOPs) Boolean expressions. This is a compact way of
representing a truth table and is a technique that is used to simplify logic expressions. It is ideally suited for four or less variables, becoming
cumbersome for five or more variables. Each square represents either a minterm or maxterm. A K-map of n variables will have 2 squares. For a
Boolean expression, product terms are denoted by 1's, while sum terms are denoted by 0's - but 0's are often leftblank.
A K-map consists of a grid of squares, each square representing one canonical minterm combination of the variables or their inverse. The map is
arranged so that squares representing minterms which differ by only one variable are adjacent both vertically and horizontally. Therefore XY'Z'
would be adjacent to X'Y'Z' and would also adjacent to XY'Z andXYZ'.
MinimizationTechnique
 Based on the Unifying Theorem: X + X' =1

 The expression to be minimized should generally be in sum-of-product form (If necessary, the conversion process is applied to create
the sum-of-productform).
 The function is mapped onto the K-map by marking a 1 in those squares corresponding to the terms in the expression to be simplified
(The other squares may be filled with0's).
 Pairs of 1's on the map which are adjacent are combined using the theorem Y(X+X') = Y where Y is any Boolean expression (If two
pairs are also adjacent, then these can also be combined using the sametheorem).
 The minimization procedure consists of recognizing those pairs and multiple pairs.
o These are circled indicating reducedterms.
1 2 3
o Groups which can be circled are those which have two (2 ) 1's, four (2 ) 1's, eight (2 ) 1's, and soon.
o Note that because squares on one edge of the map are considered adjacent to those on the opposite edge, group can be
formed with these squares.
o Groups are allowed tooverlap.
 The objective is to cover all the 1's on the map in the fewest number of groups and to create the largest groups to dothis.
 Once all possible groups have been formed, the corresponding terms are identified.
o A group of two 1's eliminates one variable from the originalminterm.
o A group of four 1's eliminates two variables from the originalminterm.
o A group of eight 1's eliminates three variables from the original minterm, and soon.
o The variables eliminated are those which are different in the original minterms of thegroup.
2-VariableK-Map
In any K-Map, each square represents a minterm. Adjacent squares always differ by just one literal (So that the unifying theorem may apply: X +
X' = 1). For the 2-variable case (e.g.: variables X, Y), the map can be drawn as below. Two variable map is the one which has got only two
variables asinput.
Equivalentlabeling
K- map needs not follow the ordering as shown in the figure above. What this means is that we can change the position of m0, m1, m2, m3
of the above figure as shown in the two figuresbelow.
Position assignment is the same as the default k-maps positions. This is the one which we will be using throughout thistutorial.
This figure is with changed position of m0, m1, m2,m3.
The K-map for a function is specified by putting a '1' in the square corresponding to a minterm, a '0'otherwise.
Example- Carry and Sum of a halfadder
In this example we have the truth table as input, and we have two output functions. Generally we may have n output functions for m input
variables. Since we have two output functions, we need to draw two k-maps (i.e. one for each function). Truth table of 1 bit adder is shown
below. Draw the k-map for Carry and Sum as shownbelow.
X Y Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Grouping/CirclingK-maps
The power of K-maps is in minimizing the terms, K-maps can be minimized with the help of grouping the terms to form single terms. When
forming groups of squares, observe/consider thefollowing:
 Every square containing 1 must be considered at leastonce.

 A square containing 1 can be included in as many groups asdesired.
 A group must be as large aspossible.
 If a square containing 1 cannot be placed in a group, then leave it out to include in finalexpression.
 The number of squares in a group must be equal to2
 , i.e.2,4,8,.
 The map is considered to be folded or spherical, therefore squares at the end of a row or column are treated as adjacentsquares.
 The simplified logic expression obtained from a K-map is not always unique. Groupings can be made in differentways.
 Before drawing a K-map the logic expression must be in canonicalform.
L-
M-
N-
O- In the next few pages we will see some examples ongrouping.
P-
Q- Exa
mple of invalidgroups
R-
S-Example -X'Y+XY
In this example we have the equation as input, and we have one output function. Draw the k-map for function F with marking 1 for X'Y and XY
position. Now combine two 1's as shown in figure to form the single term. As you can see X and X' get canceled and only Yremains.
F =Y
Example -X'Y+XY+XY'
In this example we have the equation as input, and we have one output function. Draw the k-map for function F with marking 1 for X'Y, XY and
XY position. Now combine two 1's as shown in figure to form the two singleterms.
F=X+Y
3- VariableK-Map
There are 8 minterms for 3 variables (X, Y, Z). Therefore, there are 8 cells in a 3- variable K-map. One important thing to note is that K-maps
follow the gray code sequence, not the binaryone.
Using gray code arrangement ensures that minterms of adjacent cells differ by only ONE literal. (Other arrangements which
satisfy this criterion may also beused.)
Each cell in a 3-variable K-map has 3 adjacent neighbours. In general, each cell in an n- variable K-map has n
adjacentneighbours.
Example
F =XYZ'+XYZ+X'YZ
F = XY +YZ
Example
F(X,Y,Z) = (1,3,4,5,6,7)
F = X +Z
3- VariableK-Map
There are 16 cells in a 4-variable (W, X, Y, Z); K-map as shown in the figurebelow.
There are 2 wrap-around: a horizontal wrap-around and a vertical wrap-around. Every cell thus has 4 neighbours. For
example, the cell corresponding to minterm m0 has neighbours m1, m2, m4 andm8.
Example
F(W,X,Y,Z) =(1,5,12,13)
F = WY'Z +W'Y'Z
Example
F(W,X,Y,Z) = (4, 5, 10, 11, 14,15)
F = W'XY' +WY
MinimizationTechnique
 The expression is represented in the canonical SOP form if not already in that form.
 The function is converted into numericnotation.
 The numbers are converted into binaryform.
 The minterms are arranged in a column divided intogroups.
 Begin with the minimizationprocedure.
o Each minterm of one group is compared with each minterm in the group immediatelybelow.
o Each time a number is found in one group which is the same as a number in the group below except for
one digit, the numbers pair is ticked and a new composite iscreated.
o This composite number has the same number of digits as the numbers in the pair except the digit
different which is replaced by an"x".
 The above procedure is repeated on the second column to generate a third column.
 The next step is to identify the essential prime implicants, which can be done using a prime implicantchart.
o Where a prime implicant covers a minterm, the intersection of the corresponding row and column is
marked with across.
o Those columns with only one cross identify the essential primeimplicants.
-> These prime implicants must be in the finalanswer.
o The single crosses on a column are circled and all the crosses on the same row are also circled,
indicating that these crosses are covered by the prime implicantsselected.
o Once one cross on a column is circled, all the crosses on that column can be circled since the minterm
is nowcovered.
o If any non-essential prime implicant has all its crosses circled, the prime implicant is redundant and
need not be consideredfurther.
 Next, a selection must be made from the remaining nonessential prime implicants, by considering how the non-
circled crosses can be coveredbest.
o One generally would take those prime implicants which cover the greatest number of crosses on
theirrow.
o If all the crosses in one row also occur on another row which includes further crosses, then the latter is
said to dominate the former and can be selected.
o The dominated prime implicant can then bedeleted.
Example
Find the minimal sum of products for theBoolean expression, f= (1,2,3,7,8,9,10,11,14,15), using Quine-
McCluskeymethod.
Firstly these minterms are represented in the binary form as shown in the table below. The above binary representations are
grouped into a number of sections in terms of the number of 1's as shown in the tablebelow.
Binary representation ofminterms
Minterms U V W X
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
14 1 1 1 0
15 1 1 1 1
Group of minterms for different number of1's
No of1's Minterms U V W X
1 1 0 0 0 1
1 2 0 0 1 0
1 8 1 0 0 0
2 3 0 0 1 1
2 9 1 0 0 1
2 10 1 0 1 0
3 7 0 1 1 1
3 11 1 0 1 1
3 14 1 1 1 0
4 15 1 1 1 1
Any two numbers in these groups which differ from each other by only one variable can be chosen and combined, to get 2-
cell combination, as shown in the tablebelow.
2-Cellcombinations
Combinations U V W X
(1,3) 0 0 - 1
(1,9) - 0 0 1
(2,3) 0 0 1 -
(2,10) - 0 1 0
(8,9) 1 0 0 -
(8,10) 1 0 - 0
(3,7) 0 - 1 1
(3,11) - 0 1 1
(9,11) 1 0 - 1
(10,11) 1 0 1 -
(10,14) 1 - 1 0
(7,15) - 1 1 1
(11,15) 1 - 1 1
(14,15) 1 1 1 -
From the 2-cell combinations, one variable and dash in the same position can be combined to form 4-cell combinations as
shown in the figurebelow.
4-Cellcombinations
Combinations U V W X
(1,3,9,11) - 0 - 1
(2,3,10,11) - 0 1 -
(8,9,10,11) 1 0 - -
(3,7,11,15) - - 1 1
(10,11,14,15) 1 - 1 -
The cells (1,3) and (9,11) form the same 4-cell combination as the cells (1,9) and (3,11). The order in which the cells are
placed in a combination does not have any effect. Thus the (1,3,9,11) combination could be written as(1,9,3,11).
From above 4-cell combination table, the prime implicants table can be plotted as shown in tablebelow.
Prime ImplicantsTable
Prime Implicants
1 2 3 7 8 9 10 11 14 15
(1,3,9,11) X - X - - X - X - -
(2,3,10,11) - X X - - - X X - -
(8,9,10,11) - - - - X X X X - -
(3,7,11,15) - - - - - - X X X X
- X X - X X - - - X -
The columns having only one cross mark correspond to essential prime implicants. A yellow cross is used against every
essential prime implicant. The prime implicants sum gives the function in its minimal SOPform.
Y = V'X + V'W + UV' + WX +UW
AlgebraicManipulation
Minterms andMaxterms
Any boolean expression may be expressed in terms of either minterms or maxterms. To do this we must first define the
concept of a literal. A literal is a single variable within a term which may or may not be complemented. For an expression
with N variables, minterms and maxterms are defined as follows:
 A minterm is the product of N distinct literals where each literal occurs exactly once.
 A maxterm is the sum of N distinct literals where each literal occurs exactlyonce
5-For a two-variable expression, the minterms and maxterms are asfollows

6-
X Y Minterm Maxterm
0 0 X'.Y' X+Y
0 1 X'.Y X+Y'
1 0 X.Y' X'+Y
1 1 X.Y X'+Y'
7-
8-
9-For a three-variable expression, the minterms and maxterms are asfollows
10-
X Y Z Minterm Maxterm
0 0 0 X'.Y'.Z' X+Y+Z
0 0 1 X'.Y'.Z X+Y+Z'
0 1 0 X'.Y.Z' X+Y'+Z
0 1 1 X'.Y.Z X+Y'+Z'
1 0 0 X.Y'.Z' X'+Y+Z
1 0 1 X.Y'.Z X'+Y+Z'
1 1 0 X.Y.Z' X'+Y'+Z
1 1 1 X.Y.Z X'+Y'+Z'
11-
12-
13- This allows us to represent expressions in either Sum of Products or Product of Sums forms
14-
15- Sum Of Pr
16- The Sum of Products form represents an expression as a sum ofminterms.
17-
18- F(X, Y, ...) = Sum(ak.mk)
19-
20- where ak is 0 or 1 and mk is aminterm.
21-
22- To derive the Sum of Products form from a truth table, OR together all of the minterms which give a value of1.
23-
24- Example -S
25-
26- Consider the truthtable
27-
X Y F Minterm
0 0 0 X'.Y'
0 1 0 X'Y
1 0 1 X.Y'
1 1 1 X.Y
Here SOP is f(X.Y) = X.Y' +X.Y
Product Of Sum(POS)
The Product of Sums form represents an expression as a product ofmaxterms. F(X, Y, .......) = Product (b k + Mk),
where bk is 0 or 1 and Mk is amaxterm.
To derive the Product of Sums form from a truth table, AND together all of themaxterms
which give a value of0.
Example -POS
Consider the truth table from the previousexample.
X Y F Maxterm
0 0 1 X+Y
0 1 0 X+Y'
1 0 1 X'+Y
1 1 1 X'+Y'
Here POS is F(X,Y) =(X+Y')
Exercise
Give the expression represented by the following truth table in both Sum of Products and Product of Sumsforms.
X Y Z F(X,Y,X)
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
Conversion between POS andSOP
Conversion between the two forms is done by application of DeMorgansLaws.
Simplification
As with any other form of algebra you have encountered, simplification of expressions can be performed with
Booleanalgebra.
Example
Show that X.Y.Z' + X'.Y.Z' + Y.Z = Y
X.Y.Z' + X'.Y.Z' + Y.Z = Y.Z' + Y.Z =Y
Example
Show that (X.Y' + Z).(X + Y).Z = X.Z +Y.Z
(X.Y' + Z).(X +Y).Z

= (X.Y' + Z.X +Y'.Z).Z
= X.Y'Z + Z.X +Y'.Z
= Z.(X.Y' + X +Y')
=Z.(X+Y')
DON’T-CARECONDITIONS
The logical sum of the minterms associated with a Boolean function specifies the conditions
under which the function is equal to 1. The function is equal to 0 for the restof
the minterms. This pair of conditions assumes that all the combinations of the values
for the variables of the function are valid. In practice, in some applications the function
is not specified for certain combinations of the variables. As an example, the four- bit
binary code for the decimal digits has six combinations that are not used and consequently
are considered to be unspecified. Functions that have unspecified outputsfor
some input combinations are called incompletely specified functions . In most applications,
we simply don‟t care what value is assumed by the function for the unspecified minterms. For this reason, it is customary to
call the unspecified minterms of a function
don’t-care conditions . These don‟t-care conditions can be used on a map to provide
further simplification of the Booleanexpression.

A don‟t-care minterm is a combination of variables whose logical value is not specified.
Such a minterm cannot be marked with a 1 in the map, because it would require that the function always be a 1 for such a
combination. Likewise, putting a 0 on the square requires the function to be 0. To distinguish the don‟t-care condition from
1‟sand
0‟s, an X is used. Thus, an X inside a square in the map indicates that we don‟t care
whether the value of 0 or 1 is assigned to F for the particularminterm.
In choosing adjacent squares to simplify the function in a map, the don‟t-care minterms may be assumed to be either 0 or 1.
When simplifying the function, we can choose to include each don‟t-care minterm with either the 1‟s or the 0‟s, depending
on which combination gives the simplestexpression.
Simplify the Booleanfunction
F (w, x, y, z) = _(1, 3, 7, 11, 15) which has the don‟t-care conditions d (w, x, y, z)=
_(0, 2, 5).
The min terms of F are the variable combinations that make the function equal to
1. The Min terms of d are the don‟t-care min terms that may be assigned either 0or
1. The map simplification is shown in Fig. 3.15 . The min terms of F are marked by 1‟s, those of d are marked by X‟s, and
the remainingsquares are filled with 0‟s. To get the simplified expression in sum-of-products form, we must include allfive
1‟s in the map, but we may or may not include any of the X‟s, depending on the way the function is simplified. The term yz
covers the four min terms in the third column. The remaining min term, m1, can becombined.
with min term m3 to give the three-literal term w_x_z. However, by including one or two adjacent X‟s we can combine four
adjacent squares to give a two-literal term. In Fig. 3.15(a), don‟t-care min terms 0 and 2 are included with the 1‟s, resulting in
the simplifiedfunction
F = yz + w_x_ In Fig. 3.15(b), don‟t-care minterm 5 is included with the 1‟s, and the simplified function is now F = yz +w_z
Either one of the preceding two expressions satisfies the conditions stated for this example.
■
The previous example has shown that the don‟t-care minterms in the map are initially
marked with X‟s and are considered as being either 0 or 1. The choice between 0 and 1 is made depending on the way the
incompletely specified function is simplified.
Once the choice is made, the simplified function obtained will consist of a sum of minterms
that includes those minterms which were initially unspecified and have been chosen to be included with the 1‟s. Consider the
two simplified expressions
in Example 3.8 : F (w, x, y, z) = yz + w_x_ = _(0, 1, 2, 3, 7, 11,15)
F (w, x, y, z) = yz + w_z = _(1, 3, 5, 7, 11,15)
Both expressions include minterms 1, 3, 7, 11, and 15 that make the function F equal to 1. The don‟t-care minterms 0, 2, and 5
are treated differently in each expression. The first expression includes minterms 0 and 2 with the 1‟s and leaves
minterm5withthe0‟s.Thesecondexpressionincludesminterm5withthe1‟sand leaves minterms 0 and 2 with the 0‟s. The two
expressions represent two functions that are not algebraically equal. Both cover the specified minterms of the function, but each
covers different don‟t-care minterms. As far as the incompletely specified function is concerned, either expression is
acceptable because the only difference is in the value of F for the don‟t-care minterms. It is also possible to obtain a
simplified product-of-sums expression for the function of Fig. 3.15 . In this case, the only way to combine the 0‟s is to include
don‟t-care minterms 0 and 2 with the 0‟s to give a simplified complemented function: F_ = z_ + wy_ Taking the complement
of F_ gives the simplified expression in product-of-sumsform:
F (w, x, y, z) = z(w_ + y) = _(1, 3, 5, 7, 11,15)
Inthiscase,weincludeminterms0and2withthe0‟sandminterm5withthe1‟s.

Unit 1 (DLD&CO) R22

Uploaded by

Copyright:

Available Formats

Unit 1 (DLD&CO) R22

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 (DLD&CO) R22

Uploaded by

Copyright:

Available Formats

UNIT-1

then the magnitude of this number is given by

|D| = dn-1 rn-1 + dn-2 rn-2 + …… di ri + …… d1 r1 + d0 r0

Where each d₀ ranges from 0 to r - 1, such that

What is Decimal Number System?

For example, the number 3528 has the magnitude

3528 = 3 × 103 + 5 × 102 + 2 × 101 + 8 × 100

and the number 26.57 has the magnitude

26.57 = 2 × 10 + 6 × 100 + 5 × 10-1 + 7 × 10-2

Binary number system?

an-1 2n-1 + an-2 2n-2 + …….+ a1 21 + a020.

= 1 × 22 + 1 × 21 + 1 × 20 + 1 × 2-1 + 0 × 2-2 + 1 × 2-3 + 1 × 2-4

Binary to decimal conversion:

(i) Expansion Method:

an-1 an-2 …. ai ….. a1 ….. a0 ∙ a-1 a-2 ….. a-p

(ii) Multiplication and Division Method:

Octal number system:

Convert the decimal numbers to their octal equivalents:

Hence 298010 = 56448

Decimal Numbers to Binary Number Conversion Table

Multiplication Integer Fraction

0.685 × 8 = 5.480 5 .48

0.48 × 8 = 3.84 3 .84

.84 × 8 = 6.72 6 .72

.72 × 8 = 5.76 5 .76

Therefore, 0.68510 = (0.5365…)8

Hexa-decimal number system

1. Convert B6A16 to its decimal equivalent.

= 11 × 162 + 6 × 161 + 10 × 160

Therefore, B6A16 = 292210

2. Convert 391710 to its hexa-decimal equivalent

Therefore, 391710 = F4D16

Following examples on number conversion :

1. Convert 421510 to its binary equivalent

Therefore, 421510 =10000011101112

2. Convert the following decimal numbers to their binary equivalents:

Decimal Numbers to Binary Number Conversion Table

Multiplication Integer Fraction

0.375 × 2 = 0.75 0 .75

Therefore, 0.37510 = 0.0112

Decimal Numbers to Binary Number Conversion Table

Multiplication Integer Fraction

0.435 × 2 = 0.87 0 .87

0.87 × 2 = 1.74 1 .74

.74 × 2 = 1.48 1 .48

.48 × 2 = 0.96 0 .96

.96 × 2 = 1.92 1 .92

Therefore, 0.43510 = (0.01101…)2

3. Convert (56.75)10 to its binary equivalent.

Therefore, 5610 = 1110002

The binary equivalent of 0.75 is obtained below:

Decimal Numbers to Binary Number Conversion Table

Multiplication Integer Fraction

Therefore, 0.7510 = 0.1110

Hence 56.7510 = 111000.1110

What is Signed-magnitude Representation?

(i) (01101101)2 = +(109)10

(ii) (11101101)2 = -(109)10

(iii) (00101011)2 = +(43)10