USIT102-Digital-Electronic-munotes

Page 1

1 Unit 1 01 NUMBER SYSTEM Unit Structure 1.0 Objectives 1.1 Introduction 1.2 Analog system, digital system 1.3 Numbering system 1.4 Conversion from one number system to another 1.5 Floating point numbers 1.6 Weighted codes binary coded decimal 1.7 Non-weighted codes Excess 3 code 1.8 Gray code 1.9 Alphanumeric codes 1.10 Error detection and correction 1.11 Universal Product Code 1.12 Code conversion 1.0 OBJECTIVES This chapter would make you understand the following concepts • What is difference between analog and digital system? • Different numbering system. • Conversion from one number system to another • Floating point numbers • Weighted codes binary coded decimal • Non-weighted codes Excess 3 code • Gray code and Alphanumeric codes • Error detection and correction • Universal Product Code and Code conversion 1.1 INTRODUCTION The study of number systems is important from the viewpoint of understanding how data are represented before they can be processed by munotes.in

Page 2

2 any digital system including a digital computer. In t h i s c h a p t e r w e w i l l discuss different number systems commonly used to represent data such as the binary, octal and hexadecimal number systems. 1.2 ANALOG SYSTEM, DIGITAL SYSTEM Digital as well as Analog System, both are used to transmit signals from one place to another like audio/video. Digital s y s t e m u s e s b i n a r y format as 0 and 1 whereas analog system uses electronic pulses with varying magnitude to send data. 1.2.1 Analog system: A signal is defined as any physical quantity that varies with time, space, or any other independent variable or variables. Mathematically signal can be function of one or more independent variables, for example, S1 (t) = 10 t S2 (t) = 10 t2 Most of the signals find in science and engineering a r e a n a l o g i n nature i.e. the signals are functions of a continuous variable, such as time or space, and usually take on values in continuous range. The most common example of analog signal is sinusoidal waveform as shown Fig. 1.2.1 The expression for the signal can be written as()()St= A s i n t +θω ()()St= A s i n t +θω Where, A = Amplitude ω = Radian/sec θ = Phase T = Time duration of one cycle F = Frequency = 1/T
To measure an analog signal analog multimeter is used. The main problem with an analog signal is continuously varying with respect to time; the person has to be expert in Time domain analysis to find out perfect result. 1.2.2 Digital system: To overcome the problems of an analog system; the digital system developed. Digital system requires digital information. Digital information munotes.in

Page 3

3 can be represented by fixed number of non – continuous or discrete symbols called as Digits. In digital system binary system is used which has only two digits ‘‘0’’ and ‘‘1’’. Binary system: as we are using binary in digital system which restricts the digital signal to have only two distinct values. Advantages of Binary system: 1. Most information processing systems are constructed by using switches (binary devices). 2. Binary signal are more reliable. 3. The basic decision making processes required of d i g i t a l s y s t e m s a r e binary. Bits: As binary quantities are encountered in many different physical forms, it is convenient to have a common way of representing binary states by using digit symbols ‘‘0’’ and ‘‘1’’ to represent two possible values of binary quantity at any time. These symbols are called as ‘‘bits’’, abbreviation of term ‘‘Binary digits’’. Fig. 1.2.2 shows digital and analog signal. We use ‘‘1’’ to denote ‘‘IGH’’ and ‘‘0’’ to denote ‘‘LOW’’ level of the signal. Binary voltage values VH and VL are represented as ‘‘1’’ and ‘‘0’’ respectively.
Convention: In binary system two states 1 and 0 are present. The voltage levels are predefined by the manufactures of chip and user c a n n o t c h a n g e i t . Generally HIGH LOGIC = 1 = VCC = +5 volt and LOW LOGIC = 0 = GND = 0 volt Currently we are in the digital world. The widest application of digital system is computers and to learn inside of the computers digital system is the base also it is easy to implement and in around 90% cases you will find that analog systems are replaced by digital systems. munotes.in

Page 4

4 1.3 NUMBERING SYSTEM We will begin our discussion on various number systems by briefly describing the parameters that are common to all number systems. Positional Number: A number system is defined by digits or numerals. We can combine digits as per our requirement to represent full range. The number system with which we are normally familiar is Arabic Numerals, consists of 10 digits such as 0, 1, 2,…, 9. Decimal Number System: The 10 Arabic digits can be combined in various ways to represent any number. Fundamental way of constructing a number is to form a sequence or string of digits in which consecutive digits represent consecutive power of 10. For example take 3 digit number 876. The 876 represent, from left to right, hundreds (8), tens (7) and unit (6). We can decompose the number as 8 7 6 = 8 x 1 02 + 7 x 101 + 6 x 100 … (1) This system is decimal number system which is a good example of positional number system. Here each digit of multi-digit number has fixed value (or weight) determined by its position. T h e n u m b e r i s a l s o called as weighted number system. Presently in the above example we have considered only integer part. One may require to represent fractional part also. Here fractional part is denoted by sequences of digits whose weights are negative powers of 10. The integer part a n d f r a c t i o n a l p a r t represents the full number for example 1.414, both integer and fractional part are separated by special symbol ‘.’ called a decimal point. The number can be decomposed as 1 . 4 1 4 = 1 x 1 00 + 4 x 10-1 + 1 x 10-2 + 4 x 10-3 … (2) Number Base: The decimal number notation can be written in generalized form where quantity 10 is replaced by ‘r’ called as base or radix, of the number system. We will represent number x2 x1 x0 . x-1 x-2 as x2 x1 x0 . x-1 x-2 = x2 X r2 + x1 X r1 + x0 X r0. x-1 X r-1 + x-2 X r-2 … (3) Following table shows various number systems of our interest. System Name Base ‘r’ Digits / symbols used in the system Decimal 10 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 munotes.in

Page 5

5 Binary 2 0, 1 Octal 8 0, 1, 2, 3, 4, 5, 6, 7 Hexadecimal 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F 1.3.1 Binary number system: We have already seen that binary number system has base / radix 2, which means it has only two digits, namely ‘‘0’’ and ‘‘1’’. The weights for binary number can be given by Binary number 24 23 22 21 20 2-1 2-2 2-3 … Equivalent decimal 16 8 4 2 1 0.5 0.25 0.125 … By putting r = 2 in equation (3) we can get equation for binary as follows x2 x 22 + x1 x 21 + x0 x 20 + x-1 x 2-1 + x-2 x 2-2 … (4) Let’s have one example, If Binary number is (101)2, then x2 x1 x0 = 101 x2 x 22 + x1 x 21 + x0 x 20 = 1 x 22 + 0 x 21 + 1 x 20 = 4 + 0 + 1 = ( 5 )10 ∴ (101)2 = (5)10 1.3.2 Octal number system: The octal number system has a base 8 and consists of 8 different digits or symbols such as 0 to 7. As there are 8 digits, 3 bits (23 = 8) are sufficient to represent any octal number in binary format. Following table shows 3 bit binary equivalent for each octal number 3-bit binary equivalent Octal Number 0 0 0 0 0 0 1 1 0 1 0 2 0 1 1 3 1 0 0 4 1 0 1 5 1 1 0 6 1 1 1 7 The weights for actual number system can be given by Octal number 83 82 81 80 8-1 8-2 8-3 ---- Equivalent decimal 512 64 8 1 1/8 = 0.125 1/64 = 0.01562 1/512 = 0.00195 ---- By putting r = 8 in equation (4) we can get equation for octal as follows munotes.in

Page 6

6 x2 x 82 + x1 x 81 + x0 x 80 + x-1 x 8-1 + x-2 x 8-2 … (5) Let’s have one example, If Octal number is (357)8, then x2 x1 x0 = 357 x2 x 82 + x1 x 81 + x0 x 80 = 3 x 82 + 5 x 81 + 7 x 80 = 1 9 2 + 4 0 + 7 = ( 2 3 9 )10 ∴ (357)8 = (239)10 1.3.3 Hexadecimal number system: The Hexadecimal number system has a base 16 and consists of 16 different digits or symbols. First ten digits or symbols are from decimal number system i.e. 0, 1, 2, …, 9 and next six are A, B, C, D, E and F representing 10, 11, 12, 13, 14 and 15 respectively. As there are 16 digits or symbols, 4 bits (24 = 1 6 ) a r e s u f f i c i e n t t o r e p r e s e n t a ny h e x a d e c i m a l number in binary format. Following table shows 4 bit binary equivalent for each hexadecimal number. 4-bit binary equivalent Hexadecimal Number 0 0 0 0 0 0 0 0 1 1 0 0 1 0 2 0 0 1 1 3 0 1 0 0 4 0 1 0 1 5 0 1 1 0 6 0 1 1 1 7 1 0 0 0 8 1 0 0 1 9 1 0 1 0 10 = A 1 0 1 1 11 = B 1 1 0 0 12 = C 1 1 0 1 13 = D 1 1 1 0 14 = E 1 1 1 1 15 = F The weights for actual number system can be given by: Hexadecimal number 162 161 160 16-1 16-2 … Equivalent decimal 256 16 1 1/16= 0.0625 1/256 = 0.00390 … By putting r = 16 in equation (5) we can get equation for hexadecimal as follows x2 x 162 + x1 x 161 + x0 x 160 + x-1 x 16-1 + x-2 x 16-2 ……… (6) munotes.in

Page 7

7 Let’s have one example, If Hexadecimal number is (1AF)16, then x2 x1 x0 = 1 A F x2 x 162 + x1 x 161 + x0 x 160 = 1 x 1 62 + A x 161 + F x 160 = 2 5 6 + ( 1 0 x 1 6 ) + ( 1 5 x 1 ) = 2 5 6 + 1 6 0 + 1 5 = ( 4 3 1 )10 ∴ (1AF)16 = (431)10 1.4 CONVERSION FROM ONE NUMBER SYSTEM TO ANOTHER In this section we are going to study conversion from one type of number system to another i.e. decimal to binary / octal / hexadecimal or vice versa and hexadecimal to octal, hexadecimal to binary, binary to octal etc. There are many methods or techniques which can be used to convert numbers from one base to another. In this chapter, we'll demonstrate the following Decimal to Other Base System • Other Base System to Decimal • Other Base System to Non-Decimal • Binary to Octal • Octal to Binary • Binary to Hexadecimal • Hexadecimal to Binary 1.4.1 Decimal to Other Base System: Step 1 : Divide the decimal number to be converted by the value of the new base. Step 2 : G e t t h e r e m a i n d e r f r o m S t e p 1 a s t h e r i g h t m o s t d i git (least significant digit) of the new base number. Step 3 : Divide the quotient of the previous divide by the new base. Step 4 : Record the remainder from Step 3 as the next digit (to the left) o f t h e n e w b a s e n u m b e r . Repeat Steps 3 and 4, getting remainders from right to left, until the quotient becomes zero in Step 3. The last remainder thus obtained will be the Most Significant Digit (MSD) of the new base number. munotes.in

Page 8

8 Example: Decimal Number : 2910 Calculating Binary Equivalent: Step Operation Result Remainder Step 1 29 / 2 14 1 Step 2 14 / 2 7 0 Step 3 7 / 2 3 1 Step 4 3 / 2 1 1 Step 5 1 / 2 0 1 As mentioned in Steps 2 and 4, the remainders have to be arranged in the reverse order so that the first remainder becomes the Least Significant Digit (LSD) and the last remainder becomes the Most Significant Digit (MSD). D e c i m a l N u m b e r : 2 910 = Binary Number : 111012 1.4.2 Other Base System to Decimal System: Step 1 : Determine the column (positional) value of each digit (this depends on the position of the digit and the base of the number system). Step 2 : Multiply the obtained column values (in Step 1) by the digits in the corresponding columns. Step 3 : S u m t h e p r o d u c t s c a l c u l a t e d i n S t e p 2 . T h e t o t a l is the Equivalent value in decimal. Example: Binary Number: 111012 Calculating Decimal Equivalent: Step Binary Number Decimal Number Step 1 111012 ( ( 1 x 24) + (1 x 23) + (1 x 22) + (0 x 21) + (1 x 20))10 Step 2 111012 ( 1 6 + 8 + 4 + 0 + 1 )10 Step 3 111012 2 910 Binary Number : 111012 = Decimal Number : 2910 1.4.3 Binary to Octal: Step 1 : Divide the binary digits into groups of three (starting from the right). Step 2 : Convert each group of three binary digits to one octal digit. munotes.in

Page 9

9 Example : Binary Number : 101012 Calculating Octal Equivalent: Step Binary Number Octal Number Step 1 101012 010 101 Step 2 101012 28 58 Step 3 101012 258 Binary Number : 101012 = Octal Number : 258 1.4.4 Octal to Binary: Step 1 : Convert each octal digit to a 3-digit binary number (the octal digits may be treated as decimal for this conversion). Step 2 : Combine all the resulting binary groups (of 3 digits each) into a single binary number. Example: Octal Number : 258 Calculating Binary Equivalent: Step Octal Number Binary Number Step 1 258 210 510 Step 2 258 0 1 02 1012 Step 3 258 0 1 0 1 0 12 Octal Number : 258 = Binary Number : 101012 1.4.5 Hexadecimal to Binary: Step 1 : Convert each hexadecimal digit to a 4-digit binary number (the hexadecimal digits may be treated as decimal for this conversion). Step 2 : Combine all the resulting binary groups (of 4 digits each) into a s i n g l e b i n a r y n u m b e r . Example: Hexadecimal Number : 1516 Calculating Binary Equivalent Step Hexadecimal Number Binary Number Step 1 1516 110 510 Step 2 1516 00012 01012 Step 3 1516 000101012 munotes.in

Page 10

10 1.5 FLOATING POINT NUMBER Floating point numbers are used to represent non integer fractional numbers and are used in technical calculations. E.g. 3.256, 2.1 and 0.0036. The most commonly used floating point standard is the IEEE standard. According to this standard, floating point numbers are represented with 32 bits (single precision) or 64 bits (double precision). It is an arithmetic operations consist of addition, s u b t r a c t i o n , multiplication and division. These operations are done with algorithms similar to those used on sign magnitude integers (because of the similarity of representation) example, only add numbers of the same sign. If the numbers are of opposite sign, must do subtraction. Addition: Example on decimal value given in scientific notation: 3 . 2 5 x 1 0 * * 3 + 2.63 x 10 ** -1 - - - - - - - - - - - - - - - - - - - - First step: align decimal points Second step: add 3 . 2 5 x 1 0 * * 3 + 0 . 0 0 0 2 6 3 x 1 0 * * 3 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3 . 2 5 0 2 6 3 x 1 0 * * 3 (presumes use of infinite precision, without regard for accuracy) Third step : n o r m a l i z e t h e r e s u l t ( a l r e a d y n o r m a l i z e d ! ) Example on fl pt. value given in binary: S E F . 2 5 = 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 = 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 to add these fl. pt. representations, Step 1 : align radix points shifting the mantissa LEFT by 1 bit DECREASES THE EXPONENT by 1 shifting the mantissa RIGHT by 1 bit INCREASES THE EXPONENT by 1 we want to shift the mantissa right, because the bits that fall off the end should come from the least significant end of the mantissa munotes.in

Page 11

11 -> choose to shift the .25, since we want to increase it's exponent. -> shift by 10000101 0 1 1 1 1 1 0 1 - - - - - - - - - - - - - - - 0 0 0 0 1 0 0 0 ( 8 ) p l a c e s . with hidden bit and radix point shown, for clarity 0 01111101 00000000000000000000000 (original value) 0 01111110 10000000000000000000000 (shifted 1 place) ( n o t e t h a t h i d d e n b i t i s s h i f t e d i n t o m s b o f m a n tissa) 0 01111111 01000000000000000000000 (shifted 2 places) 0 10000000 00100000000000000000000 (shifted 3 places) 0 10000001 00010000000000000000000 (shifted 4 places) 0 10000010 00001000000000000000000 (shifted 5 places) 0 10000011 00000100000000000000000 (shifted 6 places) 0 10000100 00000010000000000000000 (shifted 7 places) 0 10000101 00000001000000000000000 (shifted 8 places) Step 2 : add (don't forget the hidden bit for the 100) 0 1 0 0 0 0 1 0 1 1 . 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ( 1 0 0 ) + 0 10000101 0.00000001000000000000000 (.25) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ----- 0 1 0 0 0 0 1 0 1 1 . 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Step 3 : normalize the result (get the "hidden bit" to be a 1) it already is for this example. result is 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 suppose that the result of an addition of aligned mantissas gives 10.11110000000000000000000 and the exponent to go with this is 10000000. We must put the mantissa back in the normalized form. Shift the mantissa to the right by one place, and increase the exponent by 1. The exponent and mantissa become 10000001 1.01111000000000000000000 0 (1 bit is lost off the least significant end) Subtraction: Like addition as far as alignment of radix points then the algorithm for subtraction of sign mag. numbers takes over. munotes.in

Page 12

12 Before subtracting, • Compare magnitudes (don't forget the hidden bit!) • Change sign bit if order of operands is changed. Don't forget to normalize number afterward. Example : 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ( t h e r e p r e s e n t ations) - 0 10000000 11100000000000000000000 ------------------------------------------------------------------- Step 1 : align radix points 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 b e c o m e s 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (notice hidden bit shifted in) 0 1 0 0 0 0 0 0 1 1 . 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 1 0 0 0 0 0 0 1 0 . 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ---------- Step 2 : subtract mantissa 1 . 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 . 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 . 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Step 3 : put result in normalized form Shift mantissa left by 1 place, implying a subtraction of 1 from the exponent. 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Multiplication: example on decimal values given in scientific notation: 3.0 x 10 ** 1 + 0 . 5 x 1 0 * * 2 - - - - - - - - - - - - - - - - - - - - - - - algorithm: multiply mantissas add exponents 3 . 0 x 1 0 * * 1 + 0 . 5 x 1 0 * * 2 - - - - - - - - - - - - - - - - - - - - - - - - - - 1 . 5 0 x 1 0 * * 3 example in binary: use a mantissa that is only 4 bits so that I don't spend all day just doing the multiplication part. munotes.in

Page 13

13 0 10000100 0100 x 1 0 0 1 1 1 1 0 0 1 1 0 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - mantissa multiplication: 1.0100 (don't forget hidden bit) x 1.1100 - - - - - - - - - - - - 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 - - - - - - - - - - - 1 0 0 0 1 1 0 0 0 0 becomes 10.00110000 add exponents: always add true exponents (otherwise the bias gets added in twice) biased: 1 0 0 0 0 1 0 0 + 00111100 ------------------- 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 ( s w i t c h t h e o r d e r o f t h e s u b traction, - 01111111 - 00111100 so that we can get a negative value) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 true exp true exp is 5. is -67 add true exponents 5 + (-67) is -62. re-bias exponent: -62 + 127 is 65. unsigned representation for 65 is 01000001. put the result back together (and add sign bit). 1 01000001 10.00110000 normalize the result: ( m o v i n g t h e r a d i x p o i n t o n e p l a c e t o t h e l e f t i n c reases t h e e x p o n e n t b y 1 . ) 1 01000001 10.00110000 becomes 1 01000010 1.000110000 this is the value stored (not the hidden bit!): 1 01000010 000110000 munotes.in

Page 14

14 Division: It is similar to multiplication. true division: • do unsigned division on the mantissas (don't forget the hidden bit) • subtract TRUE exponents The IEEE standard is very specific about how all this is done. Unfortunately, the hardware to do all this is pretty slow. Some comparisons of approximate times: • 2's complement integer add 1 time unit • fl. pt add 4 time units • fl. pt multiply 6 time units • fl. pt. Divide 13 time units There is a faster way to do division. It is called division by reciprocal approximation. It takes about the same time as a fl. pt. multiply. Unfortunately, the results are not always the same as with true division. Division by reciprocal approximation: instead of doing a / b they do a x 1/b. figure out a reciprocal for b, and then use the fl. pt. multiplication hardware. example of a result that isn't the same as with true division. true division: 3/3 = 1 (exactly) reciprocal approx: 1/3 = .33333333 3 x . 3 3 3 3 3 3 3 3 = . 9 9 9 9 9 9 9 9 , n o t 1 It is not always possible to get a perfectly accurate reciprocal 1.6 WEIGHTED CODES BINARY CODED DECIMAL, NON-WEIGHTED CODES EXCESS 3 CODE Binary code: T h e d i g i t a l d a t a i s r e p r e s e n t e d , s t o r e d a n d t r a n s mitted as group of binary bits. This group is also called as binary code. • The binary code is represented by the number as well as alphanumeric letter. • The group of symbols is called as a code. munotes.in

Page 15

15 Binary Codes for Decimal digits: The following table shows the various binary codes for decimal digits 0 to 9. Decimal Digit 8421 Code 2421 Code 84-2-1 Code Excess 3 Code 0 0000 0000 0000 0011 1 0001 0001 0111 0100 2 0010 0010 0110 0101 3 0011 0011 0101 0110 4 0100 0100 0100 0111 5 0101 1011 1011 1000 6 0110 1100 1010 1001 7 0111 1101 1001 1010 8 1000 1110 1000 1011 9 1001 1111 1111 1100 We have 10 digits in decimal number system. To represent these 10 digits in binary, we require minimum of 4 bits. But, with 4 bits there will be 16 unique combinations of zeros and ones. Since, w e h a v e o n l y 1 0 decimal digits, the other 6 combinations of zeros and ones are not required. 8 4 2 1 code: • The weights of this code are 8, 4, 2 and 1. • This code has all positive weights. So, it is a positively weighted code. • This code is also called as natural BCD Binary Coded decimal code Example: Let us find the BCD equivalent of the decimal number 786. This number has 3 decimal digits 7, 8 and 6. From the table, we can write the BCD 84218421 codes of 7, 8 and 6 are 0111, 1000 and 0110 respectively. ∴ 78678610 = 011110000110011110000110BCD There are 12 bits in BCD representation, since each BCD code of decimal digit has 4 bits. 2 4 2 1 code: • The weights of this code are 2, 4, 2 and 1. • This code has all positive weights. So, it is a positively weighted code. • It is an unnatural BCD code. Sum of weights of unnatural BCD codes is equal to 9. munotes.in

Page 16

16 • It is a self-complementing code. Self-complementing codes provide the 9’s complement of a decimal number, just by interchanging 1’s and 0’s in its equivalent 2421 representation. Example: Let us find the 2421 equivalent of the decimal number 786. This number has 3 decimal digits 7, 8 and 6. From the table, we can write the 2421 codes of 7, 8 and 6 are 1101, 1110 and 1100 respectively. Therefore, the 2421 equivalent of the decimal number 786 is 110111101100. 8 4 -2 -1 code: • The weights of this code are 8, 4, -2 and -1. • This code has negative weights along with positive weights. So, it is a negatively weighted code. • It is an unnatural BCD code. • It is a self-complementing code. Example: Let us find the 8 4-2-1 equivalent of the decimal number 786. This number has 3 decimal digits 7, 8 and 6. From the table, we can write the 8 4 -2 -1 codes of 7, 8 and 6 are 1001, 1000 and 1010 respectively. Therefore, the 8 4 -2 -1 equivalent of the decimal number 786 is 100110001010. Excess 3 code: • This code doesn’t have any weights. So, it is an un-weighted code. • We will get the Excess 3 code of a decimal number by adding three 00110011 to the binary equivalent of that decimal number. Hence, it is called as Excess 3 code. • It is a self-complementing code. Example: Let us find the Excess 3 equivalent of the decimal number 786. This number has 3 decimal digits 7, 8 and 6. From the table, we can write the Excess 3 codes of 7, 8 and 6 are 1010, 1011 and 1001 respectively. Therefore, the Excess 3 equivalent of the decimal number 786 is 101010111001 munotes.in

Page 17

17 1.7 GRAY CODE A binary code used to represent digits generated from a mechanical sensor that may be prone to error. Used in telegraphy in the late 1800s, and also known as "reflected binary code," Gray code was patented by Bell Labs researcher Frank Gray in 1947. Only Change One Bit: In Gray code, there is only one bit location different between numeric increments, which make mechanical transitions from one digit to the next less error prone. The following table shows the 4-bit Gray codes corresponding to each 4-bit binary code. Decimal Number Binary Code Gray Code 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 13 1101 1011 14 1110 1001 15 1111 1000 • This code doesn’t have any weights. So, it is an un-weighted code. • In the above table, the successive Gray codes are differed in one bit position only. Hence, this code is called as unit distance code. Binary code to Gray Code Conversion: Follow these steps for converting a binary code into its equivalent Gray code. • Consider the given binary code and place a zero to the left of MSB. • Compare the successive two bits starting from zero. If the 2 bits are same, then the output is zero. Otherwise, output is one. • Repeat the above step till the LSB of Gray code is obtained. munotes.in

Page 18

18 Example: From the table, we know that the Gray code corresponding to binary code 1000 is 1100. Now, let us verify it by using the above procedure. Given, binary code is 1000. Step 1 : B y p l a c i n g z e r o t o t h e l e f t o f M S B , t h e b i n a r y c o de will 01000. Step 2 : By comparing successive two bits of new binary code, we will get the gray code as 1100. 1.8 ALPHANUMERIC CODES Alphanumeric codes are sometimes called character codes due to their certain properties. Now these codes are basically binary codes. We can write alphanumeric data, including data, letters of the alphabet, numbers, mathematical symbols and punctuation marks b y t h i s c o d e which can be easily understandable and can be processed by the computers. Input output devices such as keyboards, monitors, mouse can be interfaced using these codes. 12-bit Hollerith code is the better known and perhaps the first effective code in the days of evolving computers in early days. During this period punch cards were used as the inputting and outputting data. But nowadays these codes are termed obsolete as many other modern codes have evolved. The most common alphanumeric codes used these days are ASCII code, EBCDIC code and Unicode. Now we will discuss about them briefly. 1.8.1 ASCII code: The full form of ASCII code is American Standard Code for Information Interchange. It is a seven bit code based on the English alphabet. In 1967 this code was first published and since then it is being modified and updated. ASCII code has 128 characters some of which are enlisted below to get familiar with the code. DEC OCT HEX BIN Symbol Description 0 000 00 00000000 NUL Null char 1 001 01 00000001 SOH Start of Heading 2 002 02 00000010 STX Start of Text 3 003 03 00000011 ETX End of Text 4 004 04 00000100 EOT End of Transmission 5 005 05 00000101 ENQ Enquiry 6 006 06 00000110 ACK Acknowledgment 7 007 07 00000111 BEL Bell 8 010 08 00001000 BS Back Space munotes.in

Page 19

19 9 011 09 00001001 HT Horizontal Tab 10 012 0A 00001010 LF Line Feed 11 013 0B 00001011 VT Vertical Tab 12 014 0C 00001100 FF Form Feed 13 015 0D 00001101 CR Carriage Return 14 016 0E 00001110 SO Shift Out / X-On 15 017 0F 00001111 SI Shift In / X-O There are many more codes which are not included here. 1.8.2 EBCDIC: The EBCDIC stands for Extended Binary Coded Decimal Interchange Code. IBM invented this code to extend the Binary Coded Decimal which existed at that time. All the IBM computers and peripherals use this code. It is an 8 bit code and therefore can accommodate 256 characters. Below is given some characters of EBCDIC code to get familiar with it. 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 1001 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 D1 Y 1110 1000 E8 + … … K 1101 0010 D2 Z 1110 1001 E9 $ … … L 1101 D3 0 1111 0000 F0 * … … munotes.in

Page 20

20 0011 M1101 0100 D4 1 1111 0001 F1 ) … … N 1101 0101 D5 2 1111 0010 F2 – … … O 1101 0110 D6 3 1111 0011 F3 1.8.3 ISCII Code: ISCII stands for Indian Script Code for Information I n t e r c h a n g e . IISCII was developed to support Indian languages on computer. Language supported by IISCI include Devanagari, Tamil, Bangla, Gujarati, Gurmukhi, Tamil, Telugu, etc. IISCI is mostly used by government departments and before it could catch on, a new universal encoding standard called Unicode was introduced. 1.8.4 Hollerith code: In 1896, Herman Hollerith formed a company called the Tabulating Machine Company. This company developed a line of machines that used punched cards for tabulation. After a number of mergers, this company was formed into the IBM, Inc. We often refer to the punched-cards used in computer systems as Hollerith cards and the 12-bit code used on a punched-card is called the Hollerith code. A Hollerith string is a sequence of l2-bit characters; they are encoded as two ASCII characters, containing 6 bits each. The first character contains punches 12,0,2,4,6,8 and the second character contains punches 11, 1, 3, 5, 7, 9. Interleaving the two characters gives the original 12 bits. To make the characters printable on ASCII terminals, bit 7 is always set to 0 and bit 6 is said to the complement of bit 5. These two bits are ignored when reading Hollerith cards. Today, as punched cards are mostly obsolete and replaced with other storage medias so the Hollerith code is rendered obsolete. 1.8.5 Morse code: The Morse code, invented in 1837 by Samuel F.B. Morse, was the first alphanumeric code used in telecommunication. It uses a standardized sequence of short and long elements to represent letters, numerals and special characters of a given message. The short and long elements can be formed by sounds, marks, pulses, on off keying and are commonly known as dots and dashes. For example : The letter ‘‘A’’ is formed by a dot followed by a dash. The digit 5 is formed by 5 dots i n s u c c e s s i o n . T h e munotes.in

Page 21

21 International Morse code treats a dash equal to three dots. To see the details of Morse code table you can refer the Internet search engines. Due to variable length of Morse code characters, the morse code could not adapt to automated circuits. In most electronic communication, the Baudot code and ASCII code are used. Morse code has limited applications. It is used in communication using telegraph lines, radio circuits. Pilots and air traffic controllers also use them to transmit their identity and other information 1.8.6 Teletypewriter (TTY): A teletypewriter (TTY) is an input device that allows alphanumeric character to be typed in and sent, usually one at a time as they are typed, to a computer or a printer. The Teletype Corporation developed the teletypewriter, which was an early interface to computers. Teletype mode is the capability of a keyboard, computer, application, printer, display, or modem to handle teletypewriter input and output. Basically, this is a one-character-at-a-time mode of sending, receiving, or handling data, although it is often modified to handle a line of characters at a time. Since this mode requires little programming logic, it is often used w h e r e m e m o r y i s limited. The Basic Input/Output Operating System ( BIOS ) sends messages to a PC display using teletype mode. Most printers offer a teletype mode. The simplest video display output format is text in teletype mode. Many modems today continue to include support f o r a T T Y interface. 1.9 ERROR DETECTION AND CORRECTION What is Error?: Error is a condition when the output information does not match with the input information. During transmission, digital signals suffer from noise that can introduce errors in the binary bits travelling from one system to other. That means a 0 bit may change to 1 or a 1 bit may change to 0.
munotes.in

Page 22

22 Error-Detecting codes: Whenever a message is transmitted, it may get scrambled by noise or data may get corrupted. To avoid this, we use error-detecting codes which are additional data added to a given digital message to help us detect if an error occurred during transmission of the message. A simple example of error-detecting code is parity check. Error-Correcting codes: Along with error-detecting code, we can also pass some data to figure out the original message from the corrupt message that we received. This type of code is called an error-correcting code. Error-correcting codes also deploy the same strategy as error-detecting codes but additionally, such codes also detect the exact location of the corrupt bit. In error-correcting codes, parity check has a simple way to detect errors along with a sophisticated mechanism to determine the corrupt bit location. Once the corrupt bit is located, its value is reverted (from 0 to 1 or 1 to 0) to get the original message 1.10 UNIVERSAL PRODUCT CODE A UPC, short for universal product code, is a type of code printed on retail product packaging to aid in identifying a particular item. It consists of two parts – the machine-readable barcode, which is a series of unique black bars, and the unique 12-digit number beneath it. The purpose of UPCs is to make it easy to identify product features, such as the brand name, item, size, and color, when an item is scanned at checkout. In fact, that’s why they were created in the first place – to speed up the checkout process at grocery stores. UPCs are a l s o h e l p f u l i n tracking inventory within a store or warehouse. To obtain a UPC for use on a product a company has to first apply to become part of the system. GS1 US, the Global Standards Organization, formerly known as the Uniform Code Council, manages the assigning of UPCs within the US. Parts of a UPC: After paying a fee to join, GS1 assigns a 6-digit manufacturer identification number, which becomes the first six digits in the UPC on all the company’s products. That number identifies the particular manufacturer of the item. munotes.in

Page 23

23 The next five digits of the UPC is called an item number. It refers to the actual product itself. Within each company is a person responsible for issuing item numbers, to ensure that the same number isn‟t used more than once and that old numbers referring to discontinued products are phased out. Many consumer products have several variations, based on, for example, size, flavor, or color. Each variety requires its own item number. So a box of 24 one-inch nails has a different item number than a box of 24 two-inch nails, or a box of 50 one-inch nails. The last digit in the 12-digit UPC is called the check digit. It is the product of several calculations – adding and multiplying several digits in the code – to confirm to the checkout scanner that the UPC is valid. If the check digit code is incorrect, the UPC won’t scan properly. Advantages of UPCs: • UPCs have a number of advantages to businesses and consumers. Because they make it possible for barcode scanners to immediately identify a product and its associated price, UPCs improve speed. • They improve efficiency and productivity, by eliminating the need to manually enter product information. • They also make it possible to track inventory much more accurately than hand counting, to know when more product is needed on retail shelves or in warehouses. Or when there is an issue w i t h a p a r t i c u l a r product and consumers who purchased it need to be alerted or a recall issued, UPCs allow products to be tracked through production to distribution to retail stores and even into consumer homes. 1.11 CODE CONVERSION In this section we are going to lean the following code conversions: 1 Binary to BCD 2 BCD to Binary 3 BCD to Excess-3 4 Excess-3 to BCD 1.11.1 Binary to BCD: For the binary to BCD conversation the steps to be followed are as given below: Step 1 : Convert the binary number to decimal Step 2 : Convert decimal number into BCD Example: Convert the binary number (110101)2 into BCD Solution: Step 1 : Convert the binary number to decimal munotes.in

Page 24

24 1 1 0 1 0 1 25 + 24 + 03 + 22 + 01 + 20 32 + 16 + 0 + 4 + 0 + 1 =(53)10 Step 2 : Convert decimal number into BCD 5 3 (0 1 0 1) 0 0 1 1) ∴ (110101)2 = (01010011) BCD 1.11.2 BCD to Binary: Steps to be followed are as given below: Step 1 : Convert the BCD number to decimal Step 2 : Convert decimal number into binary Example : Convert the BCD number (0101 0011)BCD into binary Solution: Step 1 : Convert the BCD number to decimal BCD → 1 1 0 1 0 0 1 ↓ ↓ 5 3 ← D e c i m a l Step 2 : Convert decimal number into binary U s e t h e l o n g d i v i s i o n m e t h o d f o r d e c i m a l t o b i n a ry conversation ( 5 3 )10 = (110101)2 ( 0 1 0 1 0 0 1 1 )BCD = (110 101)2 1.11.3 BCD to Excess-3: Steps to be followed are as given below: Step 1 : C o n v e r t B C D t o d e c i m a l Step 2 : A d d ( 3 )10 to this decimal number Step 2 : C o n v e r t t h e d e c i m a l n u m b e r o f s t e p 2 i n t o b i n a r y , t o g e t t h e excess -3 code munotes.in

Page 25

25 Example : Convert (1001)BCD to excess -3 Solution: BCD 1 0 0 1 ↓ Decimal 9 Add 3 + 3 ( 1 2 ) 1 0 C o v e r t ( 1 1 0 0 )2 t o B i n a r y Therefore ∴ (1001)BCD = (1100)ex-3 1.11.4 Excess-3 to BCD Conversion: Subtract (0011)2 from each 4 bit excess-3 digit to obtain the corresponding BCD code. Given XS- 3 number 1001 1010 Subtract (0011)2 -0011 0011 1 1 1 1 1 BCD 0110 0111 ( 1 0 0 1 1 0 1 0 )XS-3 =(0110 0111)BCD UNIT END QUESTIONS 1. State the difference between analog and digital signals 2. Explain numbering system in brief 3. Explain floating point numbers with suitable example 4. Explain Universal Product Code 5. What is an error correction code? 6. Explain binary to decimal with suitable example 7. Explain decimal to binary with suitable example 8. Explain code conversion with suitable example 9. Convert the following fractional decimal numbers to equivalent binary number (show the step by step) 1. 0.5682 2. 0.6954 3. 0.1235 4. 0.4754 ***** munotes.in

Page 26

26 2 BINARY ARITHMETIC Unit Structure 2.0 Objectives 2.1 Introduction 2.2 Binary addition 2.3 Binary subtraction 2.4 Negative number representation 2.4.1 Subtraction using 1’s complement and 2’s complement 2.5 Binary multiplication 2.6 Binary division 2.7 Arithmetic in octal number system 2.8 Arithmetic in hexadecimal number system 2.9 BCD arithmetic 2.10 Excess 3 arithmetic 2.0 OBJECTIVE This chapter would make you understand the following concepts • What is binary arithmetic? • Binary addition, subtraction, multiplication and division. • Negative number representation • Arithmetic in octal number system • Arithmetic in hexadecimal number system • BCD arithmetic • Excess 3 arithmetic • Examples on conversion 2.1 INTRODUCTION Binary arithmetic is used in digital systems mainly b e c a u s e t h e numbers (decimal and floating-point numbers) are stored in binary format in most computer systems. All arithmetic operations s u c h a s a d d i t i o n , subtraction, multiplication, and division are done in binary representation munotes.in

Page 27

27 of numbers. It is necessary to understand the binary number representation to figure out binary arithmetic in digital computers. Binary arithmetic is essential part of all the digital computers and many other digital systems. 2.2 BINARY ADDITION • Binary addition is the key for binary multiplication, subtraction and division. The four most basic cases of binary addition are shown in Table 2.1. Table 2.1 : Four cases of binary addition:
For cases 1, 2 and 3 of Table 2.1, the binary addition takes place by following the rules of decimal addition. • But concentrate on case 4. Addition of binary 1 + 1 r e p r e s e n t t h e combining of one pebble and one pebble to obtain a total of two pebble. 1 + 1 = • • two pebbles • Since binary 10 stands for • • two pebbles, the result of binary addition 1 + 1 is 10. ∴ 1 + 1= (10)2 2.1.1 Sum and Carry : • Thus, the fourth case yields a binary two (10). When the binary numbers are added, the fourth case in Table 2.1 creates a sum of 0 in the given column and a carry of 1 over to the next column. • The four basic rules of binary addition in terms of sum and carry are as follows : Table 2.2 Rules for binary addition Rule A B Sum Carry 1 0 + 0 = 0 0 2 0 + 1 = 1 0 3 1 + 0 = 1 0 4 1 + 1 = 0 1 munotes.in

Page 28

28 2.3 BINARY SUBTRACTION Rules for subtraction: In order to understand the binary subtraction, we should remember some of the important rules of decimal subtraction. They are as follows: 1. To carry out the subtraction (A – B) where A and B are the two single digit decimal numbers. We have to consider two cases, 2. Case I : Digit A > Digit B :
3. Case II : Digit A < Digit B : If A = (3)10 and B = (5)10 then we cannot perform (3 - 5) because we cannot take out 5 pebbles from 3. Therefore, we have to borrow 1. After borrowing, the subtraction is charged to,
2.3.1 Subtraction and Borrow: • These two words will be used very frequently for the binary subtraction. For binary subtraction we have to remember the following four cases given in Table 2. 3 Table 2.3 : Four basic rules for binary subtraction: Case A B Subtraction Borrow Comment 1 0 - 0 0 0 Same as decimal 2 1 - 0 1 0 Same as decimal 3 1 - 1 0 0 Same as decimal 4 0 - 1 1 1 Borrow needs to be taken • Consider case 4 in Table 2. 3. it is [0 - 1]. Hence a logic 1 borrowed. This will change the subtraction from [0 - 1] to [10 - 1] that means [ •• - •] = • = 1. munotes.in

Page 29

29 2.4 NEGATIVE NUMBER REPRESENTATION Binary Subtraction using 1’s and 2’s Complements: • The direct binary subtraction becomes complicated as the number size increases. • Therefore we can represent the subtraction of A - B i n t h e f o r m o f addition as: A+( - B). • We can represent number B (which is to be subtracted) in its 1’s complement or 2’s complement form and use addition instead of subtraction to get the result of A - B. 2.4.1 Subtraction using 1’s Complement : The steps to be followed for subtraction (A)2 - (B)2 using 1’s complement are as follows : Step 1 : Convert number to be subtracted (B)2 to its 1's complement. Step 2 : Add (A)2 and 1’s complement of (B)2 using the rules of binary a d d i t i o n . Step 3 : If final carry is 1, then add it to the result of addition obtained i n s t e p 2 t o g e t t h e f i n a l r e s u l t o f ( A )2 - (B)2. Note that if the f i n a l c a r r y i s 1 t h e n t h e s u b t r a c t i o n i s p o s i t i v e and i in its true f o r m . Step 4 : If the final carry produced in step 2 is 0, then the result o b t a i n e d i n s t e p 2 i s n e g a t i v e a n d i n t h e 1 ' s c o mplement form. S o , c o n v e r t i t i n t o t h e t r u e f o r m b y c o m p l e m e n t i ng all the bits. The following examples will make the concept of subtraction using 1‟s complement crystal clear. There are four possible cases depending on the magnitude and sign of the numbers involved. Case 1: Number A and B, both positive and A > B. Case 2: A and B both positive and A < B. Case 3: Both numbers are negative. Case 4: A = B. Let us discuss them one by one. Case 1 : A and B, both positive and A > B Ex. 2.1 : Perform (9)10 - (4)10 using 1’s complement method Soln.: Step1 : Convert (4)10 into 1’s complement: munotes.in

Page 30

30 (4)10 = (0 1 0 0)2 and 1’s complement of (0100)2 = (1 0 1 1)2 Step2 : Add (9)10 and 1’s complement of (4)10: 1 0 0 1 + 1 0 1 1 1 0 1 0 0 Result Step 3 : Add the final carry to the result obtained in step 2: (9)10 1 0 0 1 1’s complement of (4)10: + 1 0 1 1 Final carry is generated 1 0 1 0 0 Result 1 0 1 0 1 A n s w e r i s p o s i t i v e and in true form Thus the answer is (0101)2. Note: When the final carry is produced the answer is positive and in its true form. (9)10 - (4)10 = (5)10 = (0101)2 which we have obtained. Case 2 : A and B both positive with A < B Ex.2.2 : Subtract (9)10 from (4)10 using 1’ s complement method Soln. : Given : A = (4)10 = (0100)2 B = (9)10 = (1001)2 Step 1 : Obtain 1’s complement of (9)10 : 1's complement of (9)10 or (1001)2 is (0110)2. Step 2 : Add (4)10 and 1’s complement of (9)10. : (4)10 0 1 0 0 1’s complement of (9)10 + 0 1 1 0 Final carry 0 1 0 1 0 Note: As the final carry is 0, the answer is negative and its 1's complement form. So convert the answer into its true form, as follows: 1 0 1 0 I n v e r t a l l b i t s 0 1 0 1 Answer munotes.in

Page 31

31 But (0 1 0 1)2 = (5)10 ∴ (4)10 - (9)10 = (- 5)10 Case 3 : Both number negative: Ex. 2.3 : Perform (- 4)10 - (- 8)10 using 1's complement method. Soln. : (- 4)10 - (- 8)10 = (- 4)10 + ( 8)10 Here number A i.e. (- 4)10 is negative and B is positive. So we have to take the 1’s complement of A. Step 1 : Convert number A to 1’s complements: ( 4 )10 = (0100)2 1's complement of (0100)2 = (1011)2 Step2 : Add 1’s complement of A to number B: 1’s complement of (4)10 = 1 0 1 1 (8)10 = + 1 0 0 0 Final carry 1 0 0 0 1 Result 1 Step2 : Add the final carry 1 A n s w e r i n t h e t r u e f o r m = 0 1 0 0 = ( 4 )10 T h u s , t h e a n s w e r i s p o s i t i v e a n d i n t h e t r u e f o r m ∴ (- 4)10 - (- 8)10 = (4)10 Case 4: Equal and opposite numbers: The last possibility in subtraction of numbers is to subtract a number from itself. Refer previous example to understand the result of this subtraction. Ex. 2.4 Subtract (5)10 from (5)10 using 1’s complement. Soln. : We are supposed to perform (5)10 - (5)10 . Step 1 : Obtain1’s complement of (5)10 : 1’s complement of (5)10 or (0 1 01)2 is (1010)2. munotes.in

Page 32

32 Step 2 : Add (5)10 and 1’s complement of (5)10. : (5)10 0 1 0 1 1’s complement of (5)10 + 1 0 1 0 0 1 1 1 1 T h e a n s w e r i s i n 1 ’ s complement form Step 3 : Convert the answer to its true form. : 1 1 1 1 i n v e r t 0 0 0 0 Answer in its true form ∴ (5)10 - (5)10 = (0)10 2.4.2 Binary Subtraction using 2’s Complement Method: If the subtraction of two binary numbers A and B is to be performed using the 2’s complement, then the following steps are to be followed. Steps to be followed: Step 1 : Add (A)2 to the 2's complement of (B)2 Step 2 : If the carry is generated then the result is positive and in its t r u e f o r m . Step3 : If the carry is not produced, then the result is negative and in i t s 2 ’ s c o m p l e m e n t s f o r m . Note: Carry is always to be discarded in the subtraction using 2's complement. Depending on the magnitude and polarity of numbers A and B we will deal with different possibilities as follows: Case 1 : B o t h A a n d B a r e p o s i t i v e w i t h A > B . Case 2 : Both A and B are positive with A B The subtraction (A - B) for A > B is illustrated in Ex. 2.5 Ex.2.5: Perform (9)10 - (5)10 using 2’s complement method. munotes.in

Page 33

33 Soln. : Step1 : Obtain 2’s complement of (5)10 : Decimal Binary 2’s complement (5)10 (0101)2 1011 Step 2 : Add (9)10 to 2’s complement of (5)10 : (9)10 1 0 0 1 to 2’s complement of (5)10 + 1 0 1 1 Carry 1 1 Discard Carry 1 0 1 0 0 ( 4 )10 Final indicates that A n s w e r The answer is positive and in its true form. ∴ (9)10 - (5)10 = (4)10 Note : The final carry bit acts as assign bit for the answer. It is 1 then the answer is positive, and it is 0 then the answer is negative. Case 2 : A and B both positive with A < B Ex. 2.6 : Perform (4)10 - (9)10 using 2’s complement method. Soln. : Convert both the numbers to binary ( 4 )10 = (1000)2 and (9)10 = (1001)2 Step 1 : Obtain 2’s complement of (9)10 : Decimal Binary 2’s complement (9)10 (1001)2 (0111) Step 2 : Add (4)10 to 2’s complement of (9)10 : (4)10 0 1 0 0 2’s complement of (9)10 + 0 1 1 1 carry 1 Final carry 0 1 0 1 1 Answer is negative and in 2’s complement form ‘0’ indicates that the result is negative and in its 2’s complement form munotes.in

Page 34

34 Step 3 : Convert the answer in its true form: Answer 1 0 1 1 In 2’s complement Subtract 1 : - 1 1 0 1 0 I n v e r t s a l l b i t s 0 1 0 1 Thus the answer is – (0101)2 i.e. (- 5)10. Case 3 : A and B both negative Ex. 2.8 : Perform (- 4)10 - (- 6)10 using 2’s complement method. Soln. : So we have to perform (- 4)10 + (6)10 Step 1 : Convert number A to 2’s complement of : Decimal Binary 2’s complement (4)10 (0100)2 (1100) Step 2 : Add to 2’s complement of (4)10 and (6)10 : 2’s complement of (4)10 1 1 0 0 (6)10 + 0 1 1 0 Discard carry 1 0 0 1 0 Result in true form Final carry 1 indicates that the result is positive and in the true form ∴ Answer : 0010 = (2)10 ∴ (- 4)10 + (6)10 = (2)10 Ex. 2.9 : Perform (- 6)10 - (- 2)10 using 2’s complement method Soln. : So we have to perform (- 6)10 + (2)10 Step 1 : Obtain 2’s complement of (6)10 : Decimal Binary 2’s complement (6)10 (0110)2 (1010) munotes.in

Page 35

35 Step 2 : Add (2)10 to 2’s complement of (6)10 : 2’s complement of (6)10 1 0 1 0 (2)10 + 0 0 1 0 carry 1 Final carry 0 1 1 0 0 A n s w e r i n t h e 2 ’ s c o m p l e m e n t f o r m F i n a l c a r r y i n d i c a t e s t h a t t h e a n s w e r is negative Step 3 : Bring the answer into its true form : Answer 1 1 0 0 In 2’s complement Subtract 1 - 1 1 0 1 1 A n s w e r i n 1 ’ s c o m p l e m e n t I n v e r t a l l b i t s 0 1 0 0 Answer in true from ∴ Answer = (0100)2 = (4)10 and it is negative ∴ (6)10- (2) 10= - (4)10 Case 4 : A = B Ex. 2.10 : Perform (6)10 - (6)10 using 2’s complement method. Soln. : Step 1 : Obtain 2’s complement of (6)10 Decimal Binary 2’s complement (6)10 ( 0 1 1 0 )2 ( 1 0 1 0 ) Step 2 : Obtain the binary equivalent of (6)10 A d d 2 ’ s co m p l e m e n t o f (6)10 to it: (6)10 0 1 1 0 2’s complement of (6)10 + 1 0 1 0 carry 1 1 Final carry 1 0 0 0 0 Answer in the true form F i n a l c a r r y 1 i n d i c a t e s that the answer is positive and in true form ∴ (6)10 - (6)10 = 0 munotes.in

Page 36

36 Ex. 2.11 : perform the subtraction using 1 . 1 ’ s c o m p l i m e n t m e t h o d 2 . 2 ’ s c o m p l i m e n t ( 1 1 0 1 0 ) – ( 1 0 0 0 0 ) Soln. : (1 1 0 1 0 ) – (1 0 0 0 0) Using 1’s compliment method: Step 1 : Obtain1’s complement of (1 0 0 0 0)2 Binary 1’s compliment 1 0 0 0 0 0 1 1 1 1 Step 2 : Add (1 1 0 1 0 ) and 1’s complement of (1 0 0 0 0)2 : 1 1 0 1 0 0 1 1 1 1 Final carry 1 0 1 0 0 1 Final carry=1, Add the carry + 1 0 1 0 1 0 11010 10000 01010∴−= 2’s Compliment method: Step 1 : Obtain 2’s compliment of 1 0 0 0 0: Binary 1 0 0 0 0 2’s compliment 1 0 0 0 0 Step 2 : Add(1 1 0 1 0 ) and 1’s complement of (1 0 0 0 0 )2 : 1 1 0 1 0 1 1 0 1 0 + 1 0 0 0 0 Final carry 1 0 1 0 1 0 Final carry = 1 Discard the carry. The carry indicates that result is positive and its true form ∴ ( 1 1 0 1 0 )- (1 0 0 0 0 ) = ( 1 0 1 0) Ex. 2.12 : Perform the subtraction using 1’s compliment method ( 0 0 1 1 . 1 0 0 1 )2 - (0 0 0 1 . 1 1 1 0)2 Step 1 : Obtain 1's complement of (0001.1110) 2 : B i n a r y 1 ’ s c o m p l e m e n t . 0 0 0 1 . 1 1 1 0 1 1 1 0 . 0 0 0 1 Step 2 : Add(0011.1001)2 and 1's complement of (0001.1110) 2 munotes.in

Page 37

37 Ex. 2.12 : Perform the subtraction using 1’s compliment method ( 0 0 1 1 . 1 0 0 1 )2 - (0 0 0 1 . 1 1 1 0)2 Step 1 : Obtain 1's complement of (0001.1110) 2 : B i n a r y 1 ’ s c o m p l e m e n t . 0 0 0 1 . 1 1 1 0 1 1 1 0 . 0 0 0 1 Step 2 : Add(0011.1001) 2 and 1's complement of (0001.1110) 2 1 1 1 0 . 0 0 0 1 + 0 0 1 1 . 1 0 0 1 Final carry (1) 0 0 0 1 . 1 0 1 0 + 1 0 0 0 1 . 1 0 1 0 ( 0 0 1 1 . 1 0 0 1 )2 - (0001.1110)2 = (0001.1011)2 Ex. 2.13 : Perform the subtraction using 1’s and 2’s compliment method (1010)2 – (1011)2 Solution : 1. Subtraction using 1’s complement method ( 1 0 1 0 )2 – (1011)2 Step 1 : Obtain 1’s complement of (1011)2 1 ’ s c o m p l e m e n t 1 0 1 1 - - - - - - - - - - - - - - - - 0100 Step 2 : Add (1010)2 and 1’s complement of (1011)2 : First Number : 1 0 1 0 1st complement of second number : + 0 1 0 0 Final carry 0 1 1 1 0 Answer As carry is not generated answer is negative and in 1’s complements form. Step 3 : Convert the answer into its true form: I n v e r t 1 1 1 0 - - - - - - - - - - - - - -> 0001 T h u s t h e a n s w e r i s - ( 0 0 0 1 )2 2. Subtraction using 2’s complement method ( 1 0 1 0 )2 - (1011)2 Step1 : Obtain 2’s complement of (1011)2: 2 ’ s c o m p l e m e n t ( 1 0 1 1 ) - - - - - - - - - - - > ( 0 1 0 1 ) Step2 : Add (1010)2 and 2’s complement of (1011)2 1 s t n u m b e r : 1 0 1 0 2 ’ s c o m p l e m e n t o f 2 n d n u m b e r : + 0 1 0 1 - - - - - - - - - - - - - - - - - F i n a l l y c a r r y [ 0 ] 1 1 1 1 Answer munotes.in

Page 38

38 As the final carry is not generated the answer is negative and in 2’s complements form. Step3 : Covert the answer into its true form: 2 ’ s c o m p l e m e n t 1 1 1 1 - - - - - - - - - - - - - - - - - > 0 0 0 1 T h u s t h e a n s w e r i s – ( 0 0 0 1 )2 Ex. 2.14 : Perform following binary operation using 2’ compliment m e t h o d 1 . (1010)2 – (101)2 2. (1001)2 – (1101)2 1. (1010)2 – (101)2 Let A = (1010)2 and B= (0101)2 Step 1 : Obtain 2’s complement of (0101) 2 I n v e r t A d d - 1 0 1 0 1 - - - - - - - - - > 1 0 1 0 - - - - - - - - - > 1 0 1 1
2’s complement of (0101)2 is (1011) Step 2 : Add A to 2’s complement of B: A : 1 0 1 0 2 ’ s c o m p l e m e n t o f B : + 1 0 1 1 - - - - - - - - - - - - D i s c a r d c a r r y : ( 1 ) 0 1 0 1 As final carry is generated answer is positive and in true form. As final carry is generated answer is positive and in true form. Thus (1010)2 – (101)2 = (101)2 2. (1001)2 – (1101)2 Let A = (1001)2 and B= (1101)2 Step 1 : Obtain 2’s complement of B 2 ’ s c o m p l e m e n t ( 1 1 0 1 ) - - - - - - - - - - - - - - - > ( 0 0 1 1 ) Step 2 : Add A to 2’s complement of B: A : 1 0 0 1 2's complement of B: 0011 - - - - - - - - - - - - - D i s c a r d c a r r y : ( D ) 1 1 0 0 As final carry is generated answer is positive and in true form. munotes.in

Page 39

39 Step 3 : Convert answer in true form : Answer True form. Subtract Invert 1100 1011 0100 Thus, answer is – (0100)2 As final carry is not generated answer is negative and 2’s complement form. 2.5 BINARY MULTIPLICATION • The procedure used for binary multiplication is exactly same as that for the decimal multiplication. • In fact binary multiplication is simpler than decimal ultiplication because only 0s and 1s are involved. Rules of binary multiplication are as follows: 0 x 0 = 0 0 x 1 = 0 1 x 0 = 0 1 x 1 = 1 Generalized multiplication of two binary numbers: L e t t h e t w o b i n a r y n u m b e r s t o b e m u l t i p l i e d b y 4 - bit numbers (A)2 = A3 A2 A1 A0 and (B)2 = B3 B2 B1 B0. With A0 and B0 being LSBs. The generalized multiplication is shown in Fig.2.1. MSB L SB A3 A2 A1 A0 X B3 B2 B1 B0 Multiply(A3A2A1A0)XB0 A3 B0 A2 B0 A1 B0 A0B0 + Multiply by B1 : A3 B1 A2 B1 A1 B1 A0B1 - Shift left by 1 position + Multiply by B2 : A3 B2 A2 B2 A1 B2 A0 B2 - - Shift left by 2 position + Multiply by B3 : A3 B3 A2 B3 A1B3 A0 B3 S h i f t l e f t by 3position Addition with carry represents the results Fig. 2.1 : Generalized multiplication of two binary numbers munotes.in

Page 40

40 • The process of multiplication is illustrated in Fig. 2.1. • Always start from LSB. Multiply = A3, A2, A1 and A0 to obtain A3 B0, A3 B0, A3 B0, A3 B0 respectively. • Shift left by 1 position by writing a “0” in the rightmost column and multiply (A3 A2 A1 A0) by B1. • Repeat the procedure for B2 and B3 with shifting left by 2 position and 3 positions respectively as shown Fig. 2.1. • Add the entire product terms columns by column to obtain the answer Ex. 2.15 : Multiply (9)10 by (8)10: Soln. : Let A = A3A2A A0 = (1001)2 And B = B3B2B1B0 = (1000)2A
Cross check : The decimal equivalent of the answer is obtain as follow: Answer: 1 0 0 1 0 0 0 Binary weights: 64 32 16 8 4 2 1 Decimal Equivalent: 64+8 =72 9X8 munotes.in

Page 41

41 Ex 2.16 : Perform the binary multiplication 101.11x 111.01 A 1 0 1 . 1 1 B x 1 1 1. 0 1 1 1 1 1 1 0 0 0 0 - + 1 0 1 1 1 - - Shift 1 by position + 1 0 1 1 1 - - - Shift 2 by position + 1 0 1 1 1 - - - - Shift 3 by position 1 0 1 0 0 1 1 0 1 1 Shift 4 by position The binary point is placed after 4 position from LSB. ∴∴∴∴ Ans : 1 0 1 0 0 1 . 1 0 1 1 Cross check : A = ( 1 0 1 . 1 1 )2 = (5.75)10 and B = (111.01)2 = (7.25)10 ∴ A x B = (41.6875)10
Thus we have the correct answer 2.6 BINARY DIVISION The division of binary numbers takes place in a similar way as that of decimal number. It called as the long division procedure. Ex. 2.17 : Perform the following binary division 110 + 10 Soln.: 1 1 10 1 1 0 1 0 110 = (6)10 1 0 10 = (2)10 - 1 0 ∴6+2=8 0 0 (11)2 = (3) 10 munotes.in

Page 42

42 Ex. 2.18 : Divide 1100 by 10 Soln. : 1 1 Q u o t i e n t 100 ) 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 R e m a i n d e r ∴∴∴∴Ans. : (11)2 Ex. 2.19 : Perform the division of (110 110)2 + (101)2 Soln.: 1 0 1 0 Q u o t i e n t 101 ) 1 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 0 R e m a i n d e r ∴ Quotient = (1010)2 = (10)10 Remainder = (0100)2 = (4)10 Ex. 2.20 : Perform the following multiplication in binary number s y s t e m : ( 1 5 )10 x (8)10 Cross check the answer Soln. : A = (15)10 = (1111)2 and B = (8)10 = (1000)2 B munotes.in

Page 43

43 1 1 1 1 x 1 0 0 0 Multiply by B0 0 0 0 0 Multiply by B1 + 0 0 0 0 - Multiply by B2 + 0 0 0 0 - - Multiply by B3 + 1 1 1 1 - - - Answer : 1 1 1 1 0 0 0 1 1 1 1 0 0 0 (1 x 26) +(1 x 25) +(1 x 24) +(1 x 23) + 0 + 0 + 0 = 64 + 32 + 16 + 8 = (120)10 ∴ (15)10 x (8)10 = (120)10 …Ans. 2.7 ARITHMETIC IN OCTAL NUMBER SYSTEM 2.7.1 Octal Addition: • The result of sum of two octal numbers is same as sum of their decimal equivalents as long as the decimal sum is less than 8. • But if the decimal sum is equal to or greater than 8 then subtract 8 from it (in order to obtain the octal digit, and generate a carry 1. The octal addition is illustrated in Ex. 2.21 Ex.2.21 : Perform the addition of (2)8 and (4)8 Soln. : Note that the subscript 8 indicates that the numbers are octal n u m b e r s . ∴ (2) 8 + (4)8 = (6)8 Note: 1. The addition takes place similar to that of decimal numbers. 2. As (6)8 Is less than 8, no correction is necessary. Ex.2.22 : Add (7)8 and (4) 8 Soln. : Step 1 : Add the numbers by assuming them to be decimal : (7) + (4) = (11)10 munotes.in

Page 44

44 Step 2 : Correct the result, as it is greater than 8: Two corrections will have to be carried out as follows: 1. Subtract 8 from the result: (1 1 )10 - (8)10 = 3. 2. Generate a carry = 1. ∴ (7)8 + (4)8 Carry 1 3 ∴ (7) 8 + (4)8 = (13)8 6 3 4 N o t e : W h e n e v e r c o l u m n a d d i t i o n is greater than or equal to 8, subtract 8 and generate carry 1 and add this to next column + 1 5 2 Carry 1 1 8 8 6 - - 1 0 1 0 c a r r y c a r r y 1 0 0 6 Answer Ex. 2.23 : Add (634) 8 and (152)8 Solution : The addition takes place as shown below 6 3 4 N o t e : W h e n e v e r c o l u m n a d d i t i o n is greater than or equal to 8, subtract 8 and generate carry 1. Add this carry to next column. + 1 5 2 Carry 1 1 8 8 6 - - 1 0 1 0 C a r r y C a r r y 1 0 0 6 Answer Hence (634)8+(152)8 =(1006)8 munotes.in

Page 45

45 Ex. 2.24 : Add the octal number 3548, 2668, 1238 Solution : 3 5 48 + 2 6 68 Note: Whenever column addition is greater than or equal to 8, subtract 8 and generate carry 1. Add this carry to next column. + 1 2 38 Carry : 1 1 7 1 4 1 3 - 8 - 8 1 6 1 5 C a r r y C a r r y 7 6 5 Final Answer (354)8 + (266)8 + (123)8= (765)8 2.7.2 Subtraction of Octal Numbers: The following methods can be used for octal subtraction: 1. Direct subtraction. 2. Convert the numbers to binary, perform the subtraction and convert the result back to octal. 3. Use the 7’s complement method. 4. Use the 8’s complement method 2.7.3 Method 1 : Direct Subtraction: • In the direct subtraction of octal numbers, we use the same rules as used in decimal subtraction. • That means, if the Minuend (number for which second number is to be subtracted) is less than the subtrahend (number to be subtracted) then we take borrow and return carry. • The direct subtraction of octal numbers is illustrated in the following example. Ex. 2.25 : Perform (75)8 – (68)8 without conversion. Soln. : A= (75)8 B= (68)8 Borrow: 6 A: 7 5 - B: 6 8 Carry:  Result: 0 5 ∴∴∴∴(75)8 - (68)8 =(05)8
f f(13)10 (7)10 munotes.in

Page 46

46 2.7.4 Octal Multiplication: Now we are going to learn multiplication in octal system. If you directly multiply octal number it becomes bit complicated therefore normal procedure followed is as follows: Step1 : Convert octal to binary. (both, multiplier and multiplicand.) Step 2 : Perform simple binary multiplication. Step 3 : After performing multiplication, whatever answer you get in binary, convert it to equivalent octal. Ex. 2.26 : Perform (12) 8 x (7)8 Soln. : Step 1 : Convert both octal number to binary: ( 1 2 ) 8 = (0 0 1 0 1 0) = (1 0 1 0)2 ( 7 )8 = (1 1 1)2 = (1 1 1)2 Step 2 : Perform binary multiplication : 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 - 1 0 1 0 - - 1 0 0 0 1 1 0 Binary 1 0 6 (106) 8 To cross check. (12)8 x (7)8 = (1 x 81 + 2 x 80) x [7 x 80] = (10)10 x (7)10 = (70)10 Consider result i.e. (106)8 (106)8 = 1 x 82 + 0 x 8 1+ 6 x 80 = (64 + 0 + 6)10 = (70)10 2.7.5 Octal Division: For division in octal system, we follow the same steps i.e. Step 1 : Convert octal to binary (both the given numbers). Step 2 : Perform binary division. Step 3 : Convert given binary quotient and remainder to octal. munotes.in

Page 47

47 Ex. 2.27 : perform (24)8 ÷ (4)8 Soln. : Step 1 : Convert both numbers to binary 2 4 octal 4 101 Quotient 010 100 Binary 100 Divisor 100) 10100 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 R e m a i n d e r 2.8 HEXADECIMAL ARITHMETIC In this section we are going to discuss the hexadecimal addition and subtraction. 2.8.1 Hex Addition: 1. The sum of two hex numbers is same as the sum of their decimal equivalents as long as a decimal sum is less than 16. (i. e. from 0 to 15) 2. But if the decimal sum is equal to or greater than 16 then subtract 16 from it (in order to obtain the hex digit) and generate a carry 1. The hex addition is illustrated in Ex. 2.28 Ex. 2.28 : Perform the addition of (8)H and (5)H. Soln. : T h e s u b s c r i p t H i n d i c a t e s t h a t b o t h t h e n u m b e r s a re hex n u m b e r s . ∴ 8H + 5H = (13)10 = DH Note : 1. The addition takes place similar to that of decimal numbers. 2 . A s DH is less than 16, no correction is necessary. Ex. 2.29 : Add 9H and 8H. Soln. : Step 1 : Add the numbers by assuming them to be decimal numbers: 9 + 8 = (17)10 Step 2 : Correct the result because it is greater than 16. Two corrections will have to be carried out as follows: 1. Subtract 16 from the result : (17)10 – (16)10 = 1 2. Generate a carry = 1. ∴ 9H + 8H Carry 1 7
munotes.in

Page 48

48 Ex 2.30 : Add C2H and 3E H Soln : Step 1 : Add the digits by assuming them to be digital: C 2 - - - - - - - - - > ( 1 2 )10 ( 2 )10 + + 3 E --------- > (3)10 ( 1 4 )10 Step 2 : C o r r e c t t h e r e s u l t : ( 1 5 )10 ( 1 6 )10 +  - ( 1 6 )10 ( 1 6 )10  - (16)10  0 F i n a l A n s w e r ( 1 0 0 ) 16 H e n c e (C2)H + (3E)H= (100)H 2.8.2 Hex Subtraction: There are various methods used to perform the hex subtraction. They are as follows: 1. Direct subtraction. 2. Subtraction by converting the given numbers into binary. 3. Subtraction using 15’s complement. 4. Subtraction using 16's complement. 2.8.3 Method 1: Direct Subtraction: • This method is similar to the direct octal subtraction. • If the Minuend is less than the subtrahend then we have to take borrow and return carry. • The concept of direct hex subtraction is illustrated in the following examples. Ex 2.31 (A) : Perform the following hex subtraction without converting t h e n u m b e r s . ( a ) ( A )16 – (8)16 (b) (73)H – (1C)H Soln. : A) (A)16 – (8)16 : Borrow : A : A10} B : 8 (A)16 - (8)16 = (2)16 Carry : Result : 2 munotes.in

Page 49

49 (b) (73)16 – (1C)16 : Borrow : 16 A : 7 3 B : -1 c Carry : 1 Result : 5 7 2.8.4 Hexadecimal Multiplication: If you directly multiply hex numbers, the thing becomes bit complicated. Therefore it will be better if one follows following steps Step 1 : Convert hex to binary. (Multiplier and Multiplicand both). Step 2 : Perform Simple binary multiplication. Step 3 : After performing multiplication, whatever answer you get in b i n a r y , c o n v e r t i t t o e q u i v a l e n t h e x . T h i s y o u c an achieve by g r o u p i n g 4 b i n a r y b i t s . A d d e x t r a z e r o s w h e r e r e quired. Ex 2.32 : Multiply (72)16 and (39)16 Soln. : Step1 : Convert hex to binary : ( 7 2 )16 = (0 1 1 1 0 0 1 0)2 = (1 1 1 0 0 1 0)2 ( 3 9 )16 = (0 0 1 1 1 0 0 1)2 = (1 1 1 0 0 1 )2 Step 2 : perform binary multiplication : 1 1 1 0 0 1 0 + 1 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 - 0 0 0 0 0 0 0 - - 1 1 1 0 0 1 0 - - - 1 1 1 0 0 1 0 - - - - 1 1 1 0 0 1 0 - - - - - 1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 b i n a r y Step 3 : Convert binary to hex:
(19)10 (2)10 (12)10 munotes.in

Page 50

50 Ex 2.33 : Perform (A2C)16 and (B42)16 Soln. : Step1 : Convert hex to binary : ( A 2 C )16 = (1 0 1 0 0 0 1 0 1 1 0 0)2 ( B 4 2 )16 = (1 0 1 1 0 1 0 0 0 0 1 0)2 1 0 1 0 0 0 1 0 1 1 0 0 x 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 - 0 0 0 0 0 0 0 0 0 0 0 0 - - 0 0 0 0 0 0 0 0 0 0 0 0 - - - 0 0 0 0 0 0 0 0 0 0 0 0 - - - - 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - 1 0 1 0 0 0 1 0 1 1 0 0 - - - - - - 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - - - 1 0 1 0 0 0 1 0 1 1 0 0 - - - - - - - - 1 0 1 0 0 0 1 0 1 1 0 0 - - - - - - - - - 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - - - - - 1 0 1 0 0 0 1 0 1 1 0 0 - - - - - - - - - - 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 Ex 2.34 : Perform (FA.2)16 and (11.D)16 Soln. : Step1 : Convert hex to binary : (FA.2)16 = (1111 1010 . 0010)2 = ( 1 1 1 1 1 0 1 0 . 0 0 1 )2 ( 1 1 . D )16 = (0001 0001 . 1101)2 = ( 1 0 0 0 1 . 1 1 0 1 )2 Perform binary multiplication: 1 1 1 1 1 0 1 0 0 0 1 0 x 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 - 1 1 1 1 1 0 1 0 0 0 0 0 - - 1 1 1 1 1 0 1 0 0 0 1 0 - - - 1 1 1 1 1 0 1 0 0 0 1 0 - - - - 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - - 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - - - 1 1 1 1 1 1 0 0 0 0 1 0 - - - - - - - - 1 0 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 0 munotes.in

Page 51

51 Step 2 : Convert binary to hex: 0001 0001 0110 0111 0101 1010 1 1 6 7 5 A ∴ Ans. : (1167.5A)16 2.8.5 Hex Division: To perform division in hex number you have to follow steps given below : Step 1 : Convert hex number to equivalent binary. Step 2 : Perform binary division. Step 3 : Convert final answer in binary i.e. Quotient and Remainder to e q u i v a l e n t h e x . Ex. 2.35 : Perform (24)H + (8)H. Step 1 : Convert both numbers into binary : 2 4 Hex 8 0010 0100 Binary 1000 Step 2 : Perform division 1 0 0 Q u o t i e n t 1000) 100100 1 0 0 0 1 0 0 R e m a i n d e r Step 3 : Convert the answer into hex Q u o t i e n t : 1 0 0 = ( 0 1 0 0 )2 = (4)H R e m a i n d e r : 1 0 0 = ( 0 1 0 0 )2 = (4)H 2.9 BCD ARITHMETIC BCD is a binary code of the ten decimal digits. It is not a binary equivalent. To perform BCD addition: • Add the BCD digits as regular binary numbers. • If the sum is 9 or less and no carry was generated, it is a valid BCD digit. • If the sum produces a carry, the sum is invalid and t h e n u m b e r 6 (0110) must be added to the digit. • If the sum is greater than nine, the sum is invalid a n d t h e n u m b e r 6 (0110) must be added to the digit. • Repeat for each of the BCD digits. munotes.in

Page 52

52 Addition: There are four basic rules to adding two binary digits. 0 + 0 = 0 carry 0 0 + 1 = 1 carry 0 1 + 0 = 1 carry 0 1 + 1 = 0 carry 1 • Binary digits are added two at a time and any carry must be carried over to the next higher column of digits. • To get the sum of three digits, add the first two and then add the sum to the third digit. • To add large binary numbers add one column of digits starting with the least significant position. Add any carry into the next significant column. For Example: Add the binary numbers 00111 and 10101 and show the e q u i v a l e n t decimal addition 0 1 1 0 0 1 1 1 7 1 0 1 0 1 2 1 1 1 1 0 0 = 2 8 Subtraction: There are four possible combinations when subtracting two binary digits. 0 – 0 = 0 borrow 0 0 – 1 = 1 borrow 1 1 – 0 = 1 borrow 0 1 – 1 = 0 borrow 0 • The borrow from a column of digits must be subtracted from the next most significant column. • To subtract a large binary number from another large binary number, a borrow may need to be carried over several bit positions. For Example: Subtract the binary number 00111 from 10101 and show the equivalent decimal subtraction. 1 1 1 1 0 1 0 1 2 1 0 0 1 1 1 7 1 1 1 0 0 = 1 4 munotes.in

Page 53

53 2.10 EXCESS-3 ARITHMETIC 2.10.1 Excess - 3 Addition: To add the two excess - 3 numbers A and B follow the procedure given below : Steps to be followed : Step1 : Add the two excess - 3 numbers using the rules of binary addition. Step2 : If carry is 1, then add (0011)2 or (3)10 to the sum. Step3 : If carry is 0, then subtract (0011)3 or (3)10 from the sum. Ex. 2.36 : Add (7)10 and (6)10 in excess - 3. Soln. : Convert (7)10 and (6)10 in excess - 3. ( 7 )10 = (1010)XS-3 and (6)10 = (1001) XS-3 Step 1 : Add two excess - 3 numbers : 1 0 1 0 → Excess - 3 for (7)10 + 1 0 0 1 → Excess - 3 for (6)10 Final carry → 1 0 0 1 1 → Sum Step 2 : Carry = 1 so add 0011 to the sum : 0 0 0 1 0 0 1 1 sum 0 0 1 1 0 0 1 1 Add(3) 0 1 0 0 0 1 1 0 101 103 ()()()10 10 107 6 13∴+ = Ex. 2.37 : Add (2)10 and (3)10 in excess - 3. Soln. : Convert (2)10 and (3)10 in excess - 3. ( 2 )10 = (0 1 0 1)XS-3’ (3)10 =(0 1 1 0) XS-3 Step 1 : Add two excess - 3 numbers : 1 0 1 0 E x c e s s – 3 f o r ( 7 )10 + 1 0 0 1 E x c e s s – 3 f o r ( 6 )10 Final carry 1 0 0 1 1 Sum Step 2 : Carry = 0 so subtract 0011 from the sum : 1 0 1 1 Sum 0 0 1 1 Subtract (3) 1 0 0 0 ( 5 )10 ()()()10 10 10235∴+= munotes.in

Page 54

54 2.10.2 Excess - 3 Subtraction: The steps to be followed for the Excess - 3 subtraction A - B are as follows : Steps to be followed : Step 1 : Take the complement of B (subtrahend). Step 2 : Add A (minuend) and complement of B using the rules of b i n a r y a d d i t i o n . Step 3 : If carry = 1, then add (3)10 to the result and end around the c a r r y . T h e r e s u l t i s p o s i t i v e . Step 4 : If carry = 0, then subtract (3)10 from the sum obtained in step 2 a n d t a k e t h e c o m p l e m e n t . T h e r e s u l t i s n e g a t i v e. Ex. 2.38 : Perform the subtraction (8)10 – (3)10 in excess - 3. Soln. : Step1 : Convert the numbers into excess 3 : ( 8 )10 = ( 1 0 1 1 )XS-3 and (3)10 = ( 0 1 1 0 )XS-3 Step2 : Take complement of ( 0 1 1 0 ) : N u m b e r B = 0 1 1 0 C o m p l e m e n t o f B = 1 0 0 1 Step 3 : Add A and complement of B : 1 0 1 1 E x c e s s - 3 f o r ( 8 )10 + 1 0 0 1 Complement of B + 1 1 Final carry 1 0 1 0 0 S u m Step 4 : If carry = 1, then add (3)10 to the sum and end around c a r r y : 1 0 1 0 0 S u m + 1 0 0 1 A d d ( 3 )10 Add end around carry 1 0 1 1 1 1 1 1 1 1 0 0 0 Final answer in excess -3 (5)10 munotes.in

Page 55

55 Ex. 2.39 : Perform the subtraction (3)10 – (8)10 in excess - 3. Soln.: Step1 : Convert the numbers into excess 3 : ( 3 )10 = ( 0 1 1 0)XS-3 and (8)10 = ( 1 0 1 1 )XS-3 Step2 : Take complement of ( 1 0 1 1 ) : Number B = 1 0 1 1 Complement of B =0 1 0 0 Step 3 : Add A and complement of B : 0 1 1 0 A + 0 1 0 0 C o m p l e m e n t o f B - - - - - - - - - - - - - - - - - - - F i n a l c a r r y = 0 1 0 1 0 Step 4 : Final carry = 0, then subtract (3)10 from sum : 1 0 1 0 S u m - 0 0 1 1 Add (3)10 0 1 1 1 F i n a l c a r r y i s n e g a t i v e a n d i n complemented excess -3form Step 5 : Take complement of final answer: 0 1 1 1 Answer in compliment XS-3 for compliment 1 0 0 0 Answer in true XS-3 and negative (-5)10 Thus, (3)10 – (8)10 = ( - 5)10 Ex. 2.40 : Perform the following addition in excess – 3 code. ( 9 )10 + (6)10 Sol. : 9 + 6 D e c i m a l E x c e s s - 3 9 1 1 0 0 + 6 1001 1 5 F i n a l C a r r y (1) 0101 Carry = 1, so add 3 to sum and carry + 0 0 1 1 0 0 1 1 Add 3 1 1 1 1 1 0 1 0 0 1 0 0 0 Final answer in excess - 3 (1)10 (- 5)10 ()()()10 10 109 6 15∴+ = munotes.in

Page 56

56 Ex. 2.41 : Subtract (168)10 from in (234)10 in Excess – 3. Soln : Step 1 : Obtain the excess - 3 equivalent of given numbers: N u m b e r B : ( 1 6 8 )10 = 0100 1001 1011 N u m b e r A : ( 2 3 4 )10 = 0101 0110 0111 Step 2 : Take the complement of number B : N u m b e r B = 0 1 0 0 1 0 0 1 1 0 1 1 C o m p l i m e n t o f N u m b e r B = 1 0 1 1 0 1 1 0 0 1 0 0 Step 3 : Add A and compliment of B : Decimal Excess 3 234 0101 0110 0111 168 + 1011 0110 0100 Compliment of B 66 111 11 1 Final carry =1 1 0000 1100 1011 Thus the answer positive add the end around + carry 1 0 0 0 0 1 1 0 0 1 1 0 0 S u m Step 4 : Add or subtract 011 for correction : Add 0011 to 0000 because carry = 1 was produced along with 0000 0 0 0 0 1 1 0 0 1 1 0 0 S u m i n s t e p 3 + 0011 Add 0011 0 0 1 1 1 1 0 0 1 1 0 0 Now subtract 0011 from 1100 as the carry =0 along with them 0011 1100 1100 Sum in step 3 - 0011 0011 Subtract 0011 0011 1001 1001 Answer in XS -3 form 0 6 6 REVIEW QUESTIONS Q. 1 Explain binary arithmetic in brief Q. 2 Explain binary arithmetic with suitable example Q. 3 Solve following examples munotes.in

Page 57

57 1. (10101)2 + (10111)2 2. (11101)2 + (101010)2 3. (11111)2 - (10111)2 4. (1110)2 / (10)2 5. (1011) 2 *(111)2 Q.4 Explain arithmetic’s in octal number with suitable example Q. 5 Explain arithmetic’s in hexadecimal number with suitable example Q. 6 What is BCD arithmetic? ***** munotes.in

Page 58

58 Unit 2 3 LOGIC GATES Unit Structure 3.0 Introduction 3.1 OR Gate 3.2 AND Gate 3.3 NOT Gate 3.4 NAND Gate 3.5 NOR Gate 3.6 Laws of Boolean Algebra 3.7 Exclusive-or Gate(EX-OR) 3.8 Exclusive-Nor Gate(EX-NOR) 3.9 Universal Gate 3.10 De Morgan’s Theorms 3.11 Unit End Question 3.0 INTRODUCTION • The logic gate is the most basic building block of any digital system, including computers. Each one of the basic logic gates is a piece of hardware or an electronic circuit that can be used to implement some basic logic expression. • While laws of Boolean algebra could be used to do manipulation with binary variables and simplify logic expressions, these are actually implemented in a digital system with the help of electronic circuits called logic gates. The three basic logic gates are the OR gate, the AND gate and the NOT gate. 3.1 OR GATE • An OR gate performs an ORing operation on two or more than two logic variables. • The OR operation on two independent logic variables A a n d B i s written as “Y = A+B “ and reads as Y equals A OR B. munotes.in

Page 59

59 • An OR gate is a logic circuit with two or more inputs and one output. • The output of an OR gate is LOW only when all of its inputs are LOW. For all other possible input combinations, the output is HIGH. • Figure below shows the circuit symbol and the truth table of a two-input OR gate. The operation of a two-input OR gate is explained by the logic expression: Boolean Expression : Y = A+B
Symbol for OR gate TRUTH TABLE: Input Output Y= A+B A B 0 0 0 0 1 1 1 0 1 1 1 1 3.2 AND GATE • An AND gate is a logic circuit having two or more inputs and one output. • The AND operation on two independent logic variables A and B is written as “Y = A• B “ and reads as Y equals “A AND B” • The output of an AND gate is HIGH only when all of its inputs are in the HIGH state. In all other cases, the output is LOW. • When interpreted for a positive logic system, this means that the output of the AND gate is a logic ‘‘1’’ only when all of its inputs are in logic ‘‘1’’ state. In all other cases, the output is logic ‘‘0’’. • The Boolean expression, logic symbol and truth table of a two-input AND gate are shown below; munotes.in

Page 60

60 Boolean Expression : Y = A• B
Symbol for AND Gate TRUTH TABLE: Input A B Output Y= A•B 0 0 0 0 1 0 1 0 0 1 1 1 3.3 NOT GATE • A NOT gate is a one-input, one-output logic circuit whose output is always the complement of the input. • That is, a LOW input produces a HIGH output, and vice versa. • When interpreted for a positive logic system, a logic ‘‘0’’ at the input produces a logic ‘‘1’’ at the output, and vice versa. • It is also known as a ‘‘complementing circuit’’ or an ‘‘inverting circuit’’ or hex inverter’’. The Boolean expression, logic symbol and truth table of a NOT gate are shown below; Boolean Expression : Y = A
Symbol for NOT gate munotes.in

Page 61

61 TRUTH TABLE: Input Output Y=A 0 1 1 0 Symbol for NOT gate 3.4 NAND GATE • A NAND gate is a logic circuit having two or more inputs and one output. • The NAND operation on two independent logic variables A and B is written as ''YA Bο= • “Y =A.B “ and reads as Y equals “A AND B the whole BAR” • The output of an NAND gate is HIGH when any one of its input is low • The Boolean expression, logic symbol and truth table of a two-input AND gate are shown below; Boolean Expression :

Symbol for NAND Gate Truth Table: Input Output
A B 0 0 1 0 1 1 1 0 1 1 1 0 3.5 NOR GATE • A NOR gate performs an complementary operation of OR gate on two or more than two logic variables. munotes.in

Page 62

62 • The NOR operation on two independent logic variables A and B is written as • '' ''YA B=+ “ and reads as Y equals “A OR B the whole BAR”. • The output of an OR gate is HIGH only when all of its inputs are LOW. For all other possible input combinations, the output is LOW. • Figure below shows the circuit symbol and the truth table of a two-input OR gate. The operation of a two-input OR gate is explained by the logic expression: Boolean Expression '' ''YA B=+
Symbol for NOR gate TRUTH TABLE: Input Output '' ''YA B=+ A B 0 0 1 0 1 0 1 0 0 1 1 0 3.6 LAWS OF BOOLEAN ALGEBRA Name AND form OR form Identity Law 1 • A = A 0 + A = A Null Law 0 • A = 0 1 + A = 1 Idempotent Law A • A = A A + A = A Inverse Law A • Ā = 0 A + Ā = 1 Commutative Law A B = B A A + B = B + A Associative Law (A B)C = A(B C) (A + B)+C = A+(B+C) Distributive Law A + B C = (A+B)(A+C) A(B+C) = AB + AC Absorption Law A(A+B) = A A + AB = A De Morgan’s Law AB A B=+ AB A B+= munotes.in

Page 63

63 Question : Drawing logic diagram for Boolean expression given below 1) (A + B) C 2) A + BC +D 3) AB + AC 4) ()()A+BCD C+
3.7 EXCLUSIVE-OR Gate(EX-OR) • An EX-OR gate is a logic circuit having two or more inputs and one output. • The EX-OR operation on two independent logic variables A and B is written as “Y = A ⊕ B ’’ and reads as Y equals “ EX-OR B”. • The output of an EX-OR gate is a logic ‘1’ when the i n p u t s a r e unlike and a logic ‘0’ when the inputs are like for two input EX-OR gate, while if the input is more than two then output is logic “1” when odd number of inputs are “HIGH” and logic “0” when even number of inputs are “LOW”. • The Boolean expression, logic symbol and truth table of a two-input EX-OR gate are shown below; munotes.in

Page 64

64 Boolean Expression : Y = A ⊕ B = ABA B+
Two Input EX-OR Gate Symbol Two Input TRUTH TABLE: Input Output Y = A ⊕ B A B 0 0 1 0 1 0 1 0 0 1 1 1 3.8 EXCLUSIVE-NOR Gate(EX-NOR) • The EX-OR operation on two independent logic variables A and B is written as “Y = A ⊕ B “and reads as Y equals “ EX-NOR B”. • The output of an EX-NOR gate is a logic ‘1’ when the inputs are like and a logic ‘0’ when the inputs are unlike for two input EX-OR gate, while if the input is more than two then output is logic “1” when even number of inputs are “HIGH” and logic “0” when odd number of inputs are “LOW”. • The Boolean expression, logic symbol and truth table of a two-input EX-NOR gate are shown below; Boolean Expression : Y = AB⊕
Two Input EX-NOR Gate Symbol munotes.in

Page 65

65 Two Input TRUTH TABLE: Input Output Y = AB⊕ A B 0 0 1 0 1 0 1 0 0 1 1 1 3.9 UNIVERSAL GATE • OR, AND and NOT gates are the three basic logic gates as they together can be used to construct the logic circuit f o r a n y g i v e n Boolean expression. • NOR and NAND gates have the property that they individually can be used to hardware-implement a logic circuit corresponding to any given Boolean expression. That is, it is possible to use either only NAND gates or only NOR gates to implement any Boolean expression. • This is so because a combination of NAND gates or a combination of NOR gates can be used to perform functions of any of the basic logic gates. • It is for this reason that NAND and NOR gates are universal gates NAND as NOT:
NAND as AND:
munotes.in

Page 66

66 NAND as OR:
NOR as NOT:
NOR as AND:
NOR as OR:
3.10 DE MORGAN’S THEORMS First Theorem: • It states that, the complement of a sum equals the product of complements. OR • It states that, the output of NOR gate is equal to the output of bubbled AND gate. munotes.in

Page 67

67
Truth Table: Input L.H.S.A+B R.H.SA.B A B 1 1 0 0 0 0 0 1 0 0 1 0 0 0 Second Theorem: • It states that, the complement of a product equals the sum of complements. OR • It states that, the output of NAND gate is equal to t h e o u t p u t o f bubbled OR gate.
munotes.in

Page 68

68 Truth Table:
3.11 UNIT END QUESTION 1. For the logic expression Y=AB’+A’B. Obtain the truth table, name the gate and operation performed and symbol for it also realize this using AND,OR,NOT gates. 2. Prove the given Boolean expression using Boolean laws and draw the circuit for it using NAND gates only. A.B+A’B+A’B’=A’+B 3. State and prove De-Morgan’s theorem and realize i t u s i n g b a s i c gates. 4. What is meant by universal logic gate? Draw logic circuits showing construction of Ex-OR gate using NAND gate and using NOR gate. 5. Draw logic circuit and make truth table to prove the following Boolean theorems i) A.0=0 ii) (A.B)C=A(B.C) 6. Using rules of Boolean algebra, solve y = (x+z)(x’+y+z). Draw a logic circuit using suitable gates to implement the s i m p l i f i e d equation. ***** munotes.in

Page 69

69 4 SOP AND POS REPRESENTATION OF LOGICAL EXPRESSIONS AND KARNAUGH MAP Unit Structure 4.0 Sop And Pos Representation of Logical Expressions: 4.1 Concept of Minterm and Maxterm 4.2 Minimization With Karnaugh Maps 4.3 Way of Grouping (Pairs, Quads, Octets) 4.4 Minimization of Logical Functions Not Specified I n Minterms/Maxterms 4.5 Quine-Mccluskey Minimization Technique 4.0 SOP AND POS REPRESENTATION OF LOGICAL EXPRESSIONS • Any logic expression can be expressed in the following two standard forms: i) Sum-Of-Products (SOP) form ii) Product of Sums (POS) form Sum-Of-Products (SOP) form: Y = AB + BC + AC • The above expression is a Sum of three Product terms i.e., • A.B, B.C and A.C. • Therefore such expressions are called expressions in Sum-Of-Products (SOP) form. • In a SOP sums are logical OR functions while products are logical AND functions. • In above expression A, B and C are literals or inputs while Y is output of a combinational circuit. • Some more examples of SOP are as follows: • Y=ABC+A.B.D+B.D+A.B.C munotes.in

Page 70

70 • X=PQ+P.Q.R+P.R • Thus in an SOP in each product term there can be one or more than literals ANDed together and then these product terms are logically ORed. Product-of-Sums (POS) form: Y = (A+B), (B+C), (A+C) • The above expression is a Product of three Sum terms i.e., (A+B), (B+C) and (A+C). • Therefore such expressions are called expressions in Product-Of-Sum (POS) form. • In a POS sums are logical OR functions while products are logical AND functions. • In above expression A, B and C are literals or inputs while Y is output of a combinational circuit. • Some more examples of POS are as follows • ()()X= A+B+C .(A+C+D). A+B+C • ()()M= X+Y .(X+Y+Z). X+Y • Thus in a POS in each sum term there can be one or more than literals ORed together and then these Sum terms are l o g i c a l l y ANDed • Standard SOP and POS forms: In a standard SOP or POS each term may contain one, t w o o r a n y number of literals. It is not necessary that each term should contain all the literals. • Canonical SOP and POS forms: In a canonical SOP or POS each term contains all the literals in their complimented or uncomplemented forms. Sr. No. Expressions Types 1. ..Y=A . B+A . BC A . BC+ Standard SOP 2. Y=A . B+A . B A . B+ Canonical SO 3. ()()()..Y= A C A B C A +B C++ + + Standard POS 4. ()()()..Y= A B C A +B C A B C++ + ++ Canonical POS munotes.in

Page 71

71 4.1 CONCEPT OF MINTERM AND MAXTERM • Each individual term in a canonical SOP form is called as Minterm. • Each individual term in the canonical POS is called as Maxterm Canonical SOP .. .. + ..YA B C A B CA B C=+ Each individual term is called Minterm Canonical POS ()(). YA BA B=+ +     Each individual term is called Maxterm • The following table shows the minterms and maxterms f o r a t h r e e variable logic function Y=F (A, B, C). Let Y be the output and A, B, C be the inputs. • The number of minterms and maxterms is 23 = 8 In general for ‘n’ number of variables the number of minterms or maxterms will be 2n. • Each minterm is represented by mi and each maxterm is represented by Mi where i 0, 1,… ,2n – 1. In this case i 0, 1, …, 7 Variables Minterms Maxterms A B C im iM 0 0 0 0A.B.C m= 0A+B+C M= 0 0 1 1A.B.C m= 1A+B+C M= 0 1 0 2A.B.C m= 2A+B+C M= 0 1 1 3A.B.C m= 3A+B+C M= 1 0 0 4A.B.C m= 4A+B+C M= 1 0 1 5A.B.C m= 5A+B+C M= 1 1 0 6A.B.C m= 6A+B+C M= 1 1 1 7A.B.C m= 0A+B+C M= As we can see, minterm is product of given variables where logic 0 is represented by complemented variable, while logic 1 is represented by uncomplemented variable. Whereas maxterm is sum of given variables munotes.in

Page 72

72 where logic 1 is represented by complemented variable, while logic 0 is represented by uncomplemented variable. 4.2 MINIMIZATION WITH KARNAUGH MAPS • Karnaugh map technique which provides a systematic method for simplifying and manipulating Boolean expressions. • In this technique, the information contained in a truth table or available in POS or SOP form is represented on Karnaugh map (K-map). • This is perhaps the most extensively used tool for simplification of Boolean functions. • Although the technique may be used for any number of variables, it is generally used up to six variables beyond which it becomes very cumbersome. • Below figures shows the K-maps for two, three and four variable.
munotes.in

Page 73

73
4.2 WAY OF GROUPING (PAIRS, QUADS, OCTETS) • Pairs: group of two adjacent 1’s in SOP K-map or two adjacent 0’s in OS K-map) • Quads: A group of four adjacent 1’s in SOP K-map or four adjacent 0’s in (POS K-map) • Octets: group of eight adjacent 1’s in SOP K-map or eight adjacent 0’s in (POS K-map) Grouping for eight adjacent Ones (Octets): • Group the adjacent 1s in the given K-map and write the common variables eliminating uncommon variables. In reduction technique by forming octet three variables gets eliminated. • Possible Octets in 4-variable K-map: (Note: octet is not possible in 2 variables K-map. While in 3-variable K map octet will select all the blocks making it equal to 1) Adjacent Horizontal:
munotes.in

Page 74

74 Adjacent vertical:
Fold-back:

Grouping for four adjacent Ones (Quads): • Group the adjacent 1s in the given K-map and write the common variables eliminating uncommon variables. In reduction technique by forming pair two variables gets eliminated. Possible Quads in 3-variable K-map: Adjacent Horizontal:
munotes.in

Page 75

75 Adjacent squares:
Fold-back:
Possible Quads in 4-variable K-map: 1. Adjacent Horizontal 2. Adjacent Vertical

munotes.in

Page 76

76 Adjacent squares:



Fold-backs:

munotes.in

Page 77

77

Grouping for two adjacent Ones (Pairs): • Group the adjacent 1s in the given K-map and write the common variables eliminating uncommon variables. In reduction technique by forming pairs one variable gets eliminated. • Possible pairs in 2-variable K-map:
Possible pairs in 3-variable K-map: Horizontal Adjacent:
munotes.in

Page 78

78
2. Vertical adjacent:

3. Fold-backs :
munotes.in

Page 79

79 Possible pairs in 4-variable K-map: Horizontal Adjacent:

Vertical Adjacent:

Fold-backs:

Example 1: Solve: ̅ YA . B + A . B= munotes.in

Page 80

80 Solution: Hence Y = m0 + m1 We need 2-variable K-map
Here pair variable “B” is eliminated Hence, YA= Example 2: Solve: YA . B + A . B + A . B= Solution: Hence Y = m0 + m1 + m3
(Variable B is eliminated) (Variable A is eliminated) Hence Y A.B= Example 3: Solve: YA . B . C + A . B . C + A . B . C A . B . C=+YA . B + A . B + A . B= Solution : Y = m0 + m1 + m2 + m6 Hence we need 3-variable (8 places) K-map. munotes.in

Page 81

81
(Variable A is eliminated)
Hence YA . B + B . C= Example 4: Solve: YA . B . C + A . B . C + A . B . C A . B . C=+ Solution : Y = m0 + m2 + m3 + m5
Hence Y A.B+A.C A.B.C=+ Example 5: Solve: YA . B . C . D + A . B . C . D A . B . C . D A . B . C . D + A . B . C . D+A.B.C.D+A.B.C.D+A.B.C.D A.B.C.D=+++ Solution: Y = m0 + m1 + m2 + m3 + m5 + m7 + m9 + m10 + m13 (Since group is not formed no variable eliminated (Variable B is eliminated) (Variable C is eliminated munotes.in

Page 82

82 we need 4-variable (16 places) K-map.
Hence Y A.B+A.D C.D+A.B.C.D=+ 4.2 MINIMIZATION OF LOGICAL FUNCTIONS NOT SPECIFIED IN MINTERMS/MAXTERMS If the function is specified in one of the two standard forms, its K-map can be prepared and the function can be minimized. Now we consider the cases where the functions are not specified in standard forms. In such cases, the equations can be converted into standard f o r m s u s i n g t h e techniques, the K-maps obtained and minimized. Alternately, we can directly prepare K-map using the following algorithm: i. Enter ones for minterms and zeros for maxterms. ii. Enter a pair of ones/zeros for each of the terms with one variable less than the total number of variables. iii. Enter four adjacent ones/zeros for terms with two variables less than the total number of variables. iv. Repeat for other terms in the similar way. Once the K-map is prepared the minimization procedure is same as discussed earlier. The following examples will help in understanding the above procedure: Example 1 : Minimize the four variable logic function ()fA , B , C , D A B C D + A . B . C . D A . B . C A . B . D + A . C + A . B . C+B=++ munotes.in

Page 83

83 Solution : The method for obtaining K-map is i. Enter 1 in the cell with A = 1, B = 1, C = 0, D = 1 corresponding to the minterm ABCD ii. Enter 1 in the cell with A = 0, B = 1, C = 1, D = 1 corresponding to the minterm ABCD . iii. Enter 1’s in the two cells with A = 0, B =0 iv. Enter 1's in the two cells with A = 0, B = 0, D = 0 (one of these is already entered) corresponding to the term. ABD v. Enter 1's in the two cells with A = 1, B = 0, C = 1 corresponding to the term ABC vi. Enter 1's in the four cells with A = l, C = 0 (one of them is already entered) corresponding to the term AC vii. Enter 1's in the eight cells with B = 0 (all of them except one have already been entered) corresponding to the term B.
4.3 QUINE-Mc CLUSKEY MINIMIZATION TECHNIQUE Modem digital systems are designed using complex programmable logic devices (CPLDs), field-programmable gate arrays (FPGAs), and other very large scale integrated circuits that can be configured by the end user. These devices are highly complex and therefore, the techniques required for designing digital systems using these devices have to be computer driven rather than manual. A logic minimization technique which has the following characteristics is therefore, required: 1. It should have the capability of handling large number of variables. munotes.in

Page 84

84 2. It should not depend on the ability of a human user for recognising prime-implicants. 3. It should ensure minimized expression. 4. It should be suitable for computer solution. The Quine-McCluskey minimization technique satisfies the above requirements and hence can be effectively used for the design of logic circuits. The K-map technique is not suitable for handling the design of complex digital systems because of the following disadvantages: 1. Minimization of logic functions involving more than six variables is unwieldy. 2. Recognition of prime-implicants that may form part of the simplified function relies on the ability of the human user making it difficult to be sure whether the best selection has been made. The Quine-McCluskey method consists of two parts: 1. To find by an exhaustive search all the prime-implicants that may form part of the simplified function. 2. To identify essential prime-implicants obtained f r o m p a r t 1 a n d choose among the remaining prime-implicants those that give an expression with the least number of literals The method can be best understood with the help of examples. This method is also known as Tabular method. Example 1: Simplify the logic function ()Y(A,B,C,D)= 0,1,3,7,8,9,11,15m∑the Quine-McCluskey minimization technique Solution: ()Y(A,B,C,D)= 0,1,3,7,8,9,11,15m∑ Step 1: The logic function to be minimized here is in the minterm form, therefore, we go to step 2. Step 2: Arrange all the minterms of the function in binary representation form in a Table according to the number of ones contained and form the groups containing no ones, one 1, two 1s, three 1s and so on. The groups are separated by horizontal lines. Below Table shows the arrangement of groups, minterms, and the variables. Here group 0 contains no 1s {0}; group 1 c o n t a i n s m i n t e r m s having a single 1 {1, 8}; group 2 contains minterms with two 1s {3, 9}; group 3 contains minterms with three 1s {7, 11}; and group 4 contains minterms with four 1s {15}. munotes.in

Page 85

85 Group Minterm Variables Setup3 A B C D √ 0 0 0 0 0 0 √ 1 1 0 0 0 1 √ 8 1 0 0 0 √ 2 3 0 0 1 1 √ 9 1 0 0 1 √ 3 7 0 1 1 1 √ 1 1 1 0 1 1 √ 4 17 1 1 1 1 √ Step 3 : The Boolean algebraic theorem A+Ā = 1 (Tneorem 1.7) is applied to pairs of minterms in which only one variable is different and all the other variables are same. This kind of relationship will be applicable only to the minterms belonging to adjacent groups of minterms. For this search, compare each minterm in group (n+1) with each minterm in group and identify the matched pairs. Put a check (√ ) on each matched pair as shown in Table 5.15. The detailed procedure for comparison and matched pairs for Table 5.16 is given below and another Table 5.17 is prepared, (i) The minterm 0 from group 0 is compared with the minterm 1 in the adjacent group 1. The three variables A, B, C are same in both with value 0 and the variable D is 0 in minterm 0 and 1 in minterm 1. Check (√ ) marks are placed on both the terms in Table 5.16 and a new term is generated as a result of the matching of these two terms which will contain A = 0, 8 = 0. C = 0 and a dash (-) mark is placed in D. Since the variable D differs and hence it gets eliminated and the resulting combination of these two terms is ABC. (ii) Next the minterm 0 is compared with the minterm 8. The minterms match and their combination results in a term BCD. Check mark is placed on minterm 8 in Table 5.16, check mark on minterm 0 has already been placed. A - is placed under variable A. (iii) Similarly, comparison of minterm 1 with 3 results in A = 0, B = 0, C = -, and D = 1 The minterm 3 is checked in Table 5.16. (iv) Comparison of minterm 1 with minterm 9 yields A = -, B = 0, C = 0, and D = 1 and the minterm 9 is checked (v) Now compare 8 with 3 and 9. The minterms 8 and 3 do not match. The comparison of minterms 8 and 9 results in A = 1, B = 0, C = 0, and D = - (vi) Next compare the minterms 3 and 7, it results in A = 0, B = -, C = 1, and D = 1 and the minterm 7 is checked in Table 5.16. (vii) Comparison of the minterms 3 and 11 results in A = -, B = 0, C = 1, and D = 1 and the minterm 11 is checked in Table 5.16 munotes.in

Page 86

86 (viii) The minterms 9 and 7 do not match. (ix) Comparison of the minterms 9 and 11 results in A = 1, B = 0, C = -, and D = 1 (x) Next compare the minterms 7 and 15, the result is A = -, B = 1, C = 1, and D = 1 and the minterm 15 is checked in Table 5.16 (xi) Comparison of the minterms 11 and 15 results in A = 1, S = -, C = 1, and D = 1 (xi) Table 5.17 lists the results of all the above matchings and all of the minterms in each group have been compared to those in the next higher group. Table 5.17 : Combination of minterm groups of two Group Minterm Variables Setup3 A B C D √ 0 0,1 0 0 0 - √ 0 , 8 - 0 0 0 √ 1 1,3 0 0 - 1 √ 1 , 9 - 0 0 - √ 8 , 9 1 0 0 1 √ 2 3,7 0 - 1 1 √ 3 , 1 1 - 0 1 1 √ 9 , 1 1 1 0 - 1 √ 3 7,15 - 1 1 1 √ 1 1 , 1 5 1 - 1 1 √ Step 4 : N e xt a l l t h e m i n t e r m s i n t h e a d j a c e n t g r o u p s i n T able 5.17 are compared to see if groups of four can be made by matching. For this the dashes must be in the same bit position in the groups of two and only one variable must differ (0 in one group and 1 in the other). The matched pairs of minterms are checked in Table 5.17 and a new Table 5-18 is created. In Table 5.18 we observe that in each group the two t e r m s a r e s a m e , therefore, only one is to be taken in each group. Table 5.18 : Combination of minterm groups of four Group Minterm Variables A B C D 0 0,1,8,9 - 0 0 - 0 , 8 , 1 , 9 - 0 0 - 1 1,3,9,11 - 0 - 1 1 , 9 , 3 , 1 1 - 0 - 1 2 3,7,11,15 - - 1 1 3 , 1 1 , 7 , 1 5 - - 1 1 munotes.in

Page 87

87 Step 5: Repeat the Process of Grouping of 8 miniterms. In this case both dashes must be in the same bit position and only one other variable must be different for matching. Since, there is no matching possible here, therefore, the process is complete. In general, this same process is repeated until no further combinations of minterm groups is possible. Step 6: All nonchecked minterm groups in Tables 5.16, 5.17, and 5.18 are the prime-implicants of the function. The function can now be written as ()YA , B , C , D B C + B C D . . . . . . . . ( 5 . 5 2 )D=+ Step 7: N e x t a p r i m e - i m p l i c a n t t a b l e i s p r e p a r e d l i s t i n g each of the minterms contained in the original function, PI terms, and the decimal numbers of minterms that make up the PL Put cross (x) marks in the table in each row under the minterms contained in that PI. Table 5.19 is the PI table for the logic equation Eq. (5.21). Find the minterms that contain only one x in its column. These x's are encircled and (he corresponding PI terms are checked ( ) Table 5.19 : PI table PL Terms Decimal No Minterms 0 1 3 7 8 9 1 1 1 5 BC 0,1,8,9 ⊗ × ⊗ × BD 1,3,9,11 × × × × BD 3,7,11,15 × ⊗ × ⊗ The minterms 0 and 8 are contained in only one PI BC the minterms 7 and 15 are contained in only PI CD. Therefore, the prime-implicants BC and CD are essential prime-implicants. Now observe the other mfnterms and see whether these are contained in EPIs or not. Here, the minterms 1 and 9 are contained in BCand 7 and 11 are contained in CD. Therefore, all the minterms of the original function are included in the two EPIs and the minimized expression will be Y=(A,B,C,D)=BC+ CD …..5.53 Practice Questions: 1. Using Karnaugh’s map simplify the following SO function and implement it with basic gates F(A,B,C,D)=(2,3,6,7,8,10,11,12)+d(14,15) 2. Realize the given Boolean expression using NOR gates only. munotes.in

Page 88

88 ()()()()Y= A'+B+C . A+B'+C' . A'+B'+C' . A'+B+C' 3. Obtain product of sum expression for the following function and implement it using NOR gates F(P,Q,R,S)=(1,3,5,6,7,12,13) 4. ()()F A,B,C,D 0,1,2,5,6,7,12,13,15m=∑Draw k-map and find minimized Boolean expressions. 5. What is meant by don’t care conditions? Explain how they are used in simplifying an expression using a k-map. Use the following example- F(A,B,C,D)= Σm (1,4,8,12,13,15) d (3,14) 6. What are disadvantages of k-map? Explain the Q-M method. Discuss the terms ‘prime impeccant’, ‘code word’ and ‘reduction table ***** munotes.in

Page 89

89 Unit 3 5 COMBINATIONAL LOGIC CIRCUITS Unit Structure 5.0 Introduction- Combinational Logic Circuits 5.1 Multi Input Combinational Circuit 5.2 Multi Output Combinational Circuit 5.3 Code Converters Design and Implementation 5.0 INTRODUCTION COMBINATIONAL LOGIC CIRCUITS Combinational Logic Circuits are circuits designed by using different types of logic gates. A logic gate is a fundamental building block of any electronic circuit. In other word Combinational Logic Circuits are memoryless digital logic circuits whose output at any instant in time depends only on the combination of its inputs. Means these circuits do not make use of any memory or storage device. The digital system consists of two types of circuits as - a) Combinational circuits b) Sequential circuits 2 Combinational circuit consists of logic gates whose output at any time is determined from the present combination of inputs. The logic gate is the most basic building block of combinational logic circuit. A combinational circuit consists of: • Input variables • Logic gates • Output variables The logic gates accept signals from inputs and output signals are generated according to the logic circuits working in it. Binary information from the given data transforms to preferred output data in this process. Both input and output are apparently the binary signals, i.e. both the input and output signals are of two probable states, logic ‘1’ and logic ‘0’. Logical function performed by a combinational circuit is completely defined by a set of Boolean expressions. munotes.in

Page 90

90 The function implemented by combinational circuit is depend upon the Boolean expressions. Below figure shown the combinational circuit having ‘n’ inputs and ‘m’ outputs. The ‘n’ number of inputs shows that there are 2n possible combinations of bits at the input.
Fig. : Combinational circuit having ‘n’ inputs and ‘m’outputs Combinational logic circuits may be very simple or very complicated and any combinational circuit can be implemented with only NAND and NOR gates as these are classified as universal gates Design Procedure: At all combinational circuit can be designed by the f o l l o w i n g s t e p s o f design process- 3 1. Stated problem 2. Ascertain the input and output variables 3. The input and output variables are allocated letter symbols 4. Construction of a truth table to encounter input -output requirements 5. Writing Boolean expressions for numerous output v a r i a b l e s i n relations of input variables. 6. The basic Boolean expression is acquired by any m e t h o d o f minimization — algebraic, or tabulation method. orKarnaugh map method. 7. A logic diagram is understood from the simplified Boolean expression using logic gates. The logic gates are combined in such a way that the output state depends completely on the input states. Combinational logic circuits have no memory, timing or feedback loops, there operation is prompt. A combinational logic circuit performs an operation assigned logically by a Boolean expression or truth table. The three main methods of specifying the function of a combinational logic circuit as- 1. Boolean Algebra: This forms the algebraic expression viewing the operation of the logic circuit for each input variable whicheverTrue or False that results in a logic ‘‘1’’ output. munotes.in

Page 91

91 2. Truth Table: A truth table expresses the function of a logic gate by providing a brief list that shows all the output states in tabular form for each possible combination of input variable that the gate could meet. 3. Logic Diagram : This is a graphical representation of a logic circuit that displays the wiring and connections of each individual logic gate, signified by a specific graphical symbol that i m p l e m e n t s t h e logic circuit. These logic circuit representations are shown as-
()()QA . B . A + B . C= C B A Q 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 Fig. : Combinational Circuit Diagram, Boolean Expression & truth Table As combinational logic circuits are made up from discrete logic gates only, they can also be considered as decision m a k i n g c i r c u i t s a n d combinational logic is nearby combining logic gates t o g e t h e r t o p r o c e s s two or more signals in order to produce at least one output signal according to the logical function of each logic gate. General combinational circuits made up from individual logic gates that carry out a anticipated application comprise Full and Half Adders Multiplexers, De-multiplexers, Encoders, Decoders etc. Classification of Combinational Logic: Combinational Logic Circuit Arithmetic & Logical Functions Data Transmission Code Converters Adders Subtracotrs Comparitors Plds M u l t i p l e x e r s , De-multiplexers Encoders Decoders B i n a r y BCD 7-segment Fig. Classification of Combinational Logic munotes.in

Page 92

92 One of the greatest uses of combinational logic is in Multiplexer and De-multiplexer type circuits. Here, multiple inputs o r o u t p u t s a r e connected to a common signal stripe and logic gates are used to decode an address to select a single data input or output switch. 5.1 MULTI INPUT COMBINATIONAL CIRCUIT In processor designs, transistors are protected down for specific functions. To overcome the restriction of fixed structures of static architecture in the next generation of computer is an important issue to the real-world applications. A reconfigurable technique w i t h d y n a m i c architecture has made it possible to break through the stable limitations of the current computer systems. In dynamic architecture, systems can flexibly change their hardware configurations during the course of computation according to the demands of various functions. Multi input gates can be made by constructing gates of the same t y p e w i t h f e w e r inputs. The figure below shown how a three input AND gate can be made out of two input AND gates. The same logical standard applies - the output goes ‘‘low’’ (0) if any of the inputs are made “high” (1). Combinational Logic Circuits are made up from basic logic NAND, NOR or NOT gates that are connected together to produce more complex switching circuits. These logic gates are the building blocks of combinational logic circuits. An example of a combinational circuit-Decoder, which converts the binary code data present at its input into a number of diverse output lines, one at a time producing an equivalent decimal code at its output.
Fig. Multi Input Combinational Circuit The number of possible input states is equal to two t o t h e p o we r o f t h e number of inputs: 6 Number of possible input states = 2n Where, n = Number or inputs This increase in the number of possible input states obviously allows for more complex gate performance. Instead of simply inverting a single “high” or “low” logic level, the output of the gate will be determined by whatsoever combination of 1‘s and 0‘s is present at the input stations. munotes.in

Page 93

93 Since many combinations are possible with just a limited input stations, there are many different types of multiple-input gates, unlike single-input gates which can simply be inverters. Each basic gate type will be shown as its standard symbol, truth table, andoperation. Types of different Multi Input Combinational Circuit a) AND Gate b) NAND Gate c) Negative AND Gate d) OR Gate e) NOR Gate f) Negative OR Gate g) Exclusive OR Gate h) Encoder i) Multiplexer a) AND Gate: The simple multiple-input gates to recognize is the AND gate, the output of this gate will be ‘‘high’’ (1) if and only if all inputs are “high” (1). If any input(s) is ‘‘low’’ (0), the output is certain to be in a “low” state. Two input AND gate Three input AND gate Truth Table


AND Gate Circuit Operation: The truth table means in practical terms is shown in the following sequence as, with the 2-input AND gate exposed to all possibilities of input logic levels. An LED provides visual signal of the output logic level. Circuit Diagram



munotes.in

Page 94

94 It is only with all inputs raised to ‘‘high’’ logic levels that the AND gate’s output goes ‘‘high,’’ thus stimulating the LED for only one out of the four input combination states. b) NAND Gate: A distinction on the idea of the AND gate is called t h e N A N D gate. The term ‘‘NAND’’ is a verbal contraction of the words NOT and AND. Fundamentally, a NAND gate performs the same as an AND gate with a NOT gate connected to the output terminal. To represent this output signal inversion, the NAND gate symbol has a bubble on the output line. The truth table for a NAND gate is as one might expect, precisely opposite as that of an AND gate NAND gate Truth Table

As with AND gates, NAND gates are made with more than two inputs. In such cases, the same over-all standard relates: the output will be “low” (0) if and only if all inputs are ‘‘high’’ (1). If any input is ‘‘low’’ (0), the output will go “high” (1). c) Negative AND Gate: A Negative-AND gate purposes the same as an AND gate with all its inputs inverted (connected through NOT gates). In trust with standard gate symbol convention, these inverted inputs are showed b y b u b b l e s . Opposing to most publics‘ first nature, the logical conduct of a Negative-AND gate is not the same as a NAND gate. Its truth table, essentially, is matching to a NOR gate: Negative AND gate Truth Table Circuit Diagram


munotes.in

Page 95

95 d) OR Gate: Next gate to study is the OR gate, so-called because the output of this gate will be ‘‘high’’ (1) if any of the inputs a r e ‘ ‘ h i g h ’ ’ ( 1 ) . T h e output of an OR gate goes ‘‘low’’ (0) if and only if all inputs are ‘‘low’’ (0). Two input Three Input Truth Table


A two-input OR gate’s truth table appearances like the following sequence of drawings proves the OR gate’s function, w i t h t h e 2 - i n p u t s undergoing all possible logic levels. An LED delivers visual indication of the gate’s output logic level Circuit Diagram



A condition of any input being outstretched to a ‘‘high’’ logic level makes the OR gate’s output go ‘‘high,’’ thus stimulating the LED for three out of the four input combination states. e) NOR gate: The NOR gate is an OR gate with its output inverted, just like a NAND gate is an AND gate with an inverted output NOR Gate Truth Table Circuit Diagram

munotes.in

Page 96

96 NOR gates, like all the other multiple-input gates realized thus outlying, can be synthetic with more than two inputs. Still, the same logical standard applies. The output goes ‘‘low’’ (0) if any of the inputs are made ‘‘high’’ (1). The output is ‘‘high’’ (1) only when all inputs are ‘‘low’’ (0) f) Negative-OR Gate: A Negative-OR gate functions the same as an OR gate with all its inputs inverted. In possession with standard gate symbol convention, these inverted inputs are showed by bubbles. The performance and truth table of a Negative-OR gate is the same as for a NAND gate: NOR Gate Truth Table Circuit Diagram


g) Exclusive OR Gate: This gate is direct variations on three basic functions- AND, OR, and NOT. The Exclusive-OR gate, however, is approximately fairly different. Exclusive-OR gates output a ‘‘high’’ (1) logic level if the inputs are at different logic levels, either 0 and 1 11 inputs are at the same logic levels. or 1 and 0. Contrariwise, the output a ‘‘low’’ (0) logic level if the The Exclusive-OR ( XOR) gate has both a symbol and a truth table pattern that is distinctive: Exclusive OR Gate Truth table

There are equivalent circuits for an Exclusive-OR gate made up of AND, OR, and NOT gates, impartial as there were for NAND, NOR, and the negative-input gates. A somewhat direct method to simulating an Exclusive-OR gate is to start with a regular OR gate, then add additional gates to avoid the output from going ‘‘HIGH’’ (1) when both inputs are ‘‘HIGH’’ (1): munotes.in

Page 97

97 h) Encoder: An encoder is a digital circuit that achieves the inverse operation of a decoder. Therefore, the opposite of the decoding process is called encoding. An encoder is a combinational circuit that converts binary information from 2n i n p u t l i n e s t o a m a x i m u m o f ‘ n ’ e x c l u s i v e o u t p u t lines.
It has 2n i n p u t l i n e s , o n l y o n e ‘ ‘ 1 ’ ’ i s a c t i v e a t a n y t i m e and ‘n’ output lines. It encodes one active inputs to a coded binary output with ‘n’ bits. In an encoder, the number of outputs is less than the number of inputs. i) Octal-to-Binary Encoder: It has eight inputs and the three outputs that produce the equivalent binary number. It is assumed that only one input has a value of ‘1’ at any given time Inputs Outputs D0 D1 D2 D3 D4 D5 D6 D7 A B C 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 Table: Input / Output of Octal-to-‘Binary Encoder’ The encoder can be implemented with OR gates whose inputs are determined straight from the truth table. Output z is equal to 1, when the input octal digit is 1 or 3 or 5 or 7. Output y is 1 for octal digits 2, 3, 6, or 7 and the output is 1 for digits 4, 5, 6 or 7. These conditions can be expressed by the following output Boolean functions: z= D1+ D3+ D5+ D7 y= D2+ D3+ D6+ D7 x= D4+ D5+ D6+ D7 munotes.in

Page 98

98 The encoder can be applied with three OR gates. The e n c o d e r defined in the below table, has the restriction that only one input can be active at any given time. If two inputs are active concurrently, the output produces an approximate combination. For eg. if D3 a n d D6 a r e 1 c o n c u r r e n t ly , t h e o u t p u t o f t h e e n c o d e r may be 111. This does not represent either D6 o r D3. To resolve this problem, encoder circuits must establish an input priority to ensure that only one input is encoded. If we establish a higher priority for inputs with higher subscript numbers and if D3 a n d D6 a r e 1 a t t h e s a m e t i m e , t h e output will be 110 because D6 has higher priority than D3.
Fig. Circuit diagram of Octal-to-Binary Encoder Another issue in the octal-to-binary encoder is that an output with all 0’s is produced when all the inputs are 0; this output is same as when D0 is equal to 1. The inconsistency can be resolved by providing one more output to indicate that at least one input is equal to 1. i) Multiplexer: (Data Selector): A multiplexer or MUX, is a combinational circuit with more than one input line, one output line and more than one selection line. A multiplexer selects binary information present from o n e o f m a n y i n p u t lines, depending upon the logic status of the selection inputs, and directions it to the output line. Generally, there are 2n i n p u t l i n e s a n d n selection lines whose bit combinations determine which input is selected. The multiplexer is labelled as MUX in block diagrams. A multiplexer is also called a data selector, since it selects one of many inputs and leads the binary information to the output line. munotes.in

Page 99

99
Fig. multiplexer j) 2-to-1- line Multiplexer: This circuit has two data input lines, one output line and one selection line. When S= 0, the upper AND gate is enabled and I0 h a s a path to the output. When S=1, the lower AND gate is enabled and I1 has a path to the output
Fig.Circuit diagram 2-to-1- line Multiplexer The multiplexer acts like an electronic switch that selects one of the two sources. S Y 0 I0 1 I1 Table: Truth table ii) 4-to-1-line Multiplexer: A 4-to-1-line multiplexer has four (2n) input lines, two (n) select lines and one output line. It is the multiplexer comprising of four input channels and information of one of the station can be selected and transmitted to an output line according to the select inputs combinations. Selection of one of the four input station is possible by two selection inputs. munotes.in

Page 100

100 Each of the four inputs I0 through I3, is applied to one input of AND gate. Selection lines S1 and S0 are decoded to select a particular AND gate. The outputs of the AND gate are applied to a single OR gate that provides the 1-line output.
Fig. Circuit diagram of 4-to-1-line Multiplexer S1 S0 Y 0 0 I0 0 1 I1 1 0 I2 1 1 I3 Table: Truth table 4-to-1-line Multiplexer To establish the circuit operation, consider the case when S1S0= 10. The AND gate associated with input I2 has two of its inputs equal to 1 and the third input connected to I2. The other three AND gates have at least one input equal to 0, which makes their outputs equal to 0. The OR output is now equal to the value of I2, providing a path from the selected input to the output. The data output is equal to I0 only if S1= 0 and S0 = 0; Y= I0S1‘S0’. The data output is equal to I1 only if S1= 0 and S0 = 1; Y= I1S1‘S0’. The data output is equal to I2 only if S1= 1 and S0= 0; Y= I2S1S0. The data output is equal to I3 only if S1= 1 and S0= 1; Y= I3S1S0. When these terms are ORed, the total expression for the data output is, Y= I0S1’S0’+ I1S1’S0 +I2S1S0’+ I3S1S0. In decoder, multiplexers may have an enable input to control the operation of the unit. When the enable input is in the inactive state, the munotes.in

Page 101

101 outputs are disabled, and when it is in the active state, the circuit functions as multiplexer. 5.2 MULTI OUTPUT COMBINATIONAL CIRCUIT A combinational circuit has output values that depend only on the current input values irrespective of presence or absence of responses.Circuits that implement these functions may be combined into expensive single circuit with multiple outputs by sharing some gates desirable in the implementation of the single functions. Boolean expressions are used to output a Boolean function of number of variables. There are circuits which have multiple outputs and multiple inputs. Conventional combinational circuits are normally acyclic but these circuits can have feedbacks (cycles) which will give more minimized expressions as compared to usual combinational circuits. Thoughtful integration of such cycles or feedbacks in usual combinational circuits eventually results in reduction in number of literals in the expression of the combinational circuits. The reduction in literal counts decreases t h e n u m b e r o f g a t e s required to implement the expressions of the combinational circuits. Hence, the decrease in number of gates leads to reduction in transistor counts. A cyclic combinational circuit is defined as the circuit whose output depends on present inputs only, but at the same time contains one or more feedbacks (cycles) Types of multiple-output circuits: i) Decoder a) 2 to 4 decoder b) 3- to-8 Line Decoder ii) Demultiplexer a) 1 to 4 Demultiplexer b) 3 to 8 Demultiplxer i) Decoder: A decoder is a combinational circuit that converts binary information from ‘n’ input lines to a maximum of ‘‘2n’’ unique output lines. The general structure of decoder circuit is 17
Fig. Decoder block diagram munotes.in

Page 102

102 The encoded information is presented as ‘n’ inputs producing 2n possible outputs. The 2n output values are from 0 through 2n-1. A decoder is provided with enable inputs to activate decoded output based on data inputs. When any one enable input is unasserted, all outputs of decoder are disabled a) Binary Decoder (2 to 4 decoder): A binary decoder has ‘n’ bit binary input and a one a c t i v a t e d output out of 2n outputs. A binary decoder is used when it is necessary to activate exactly one of 2n outputs based on an n-bit input value.
Fig. 2 to 4 decoder circuit diagram Here the 2 inputs are decoded into 4 outputs, each output signifying one of the minterms of the two input variables.
Fig.Truth table 2 to 4 decoder circuit As shown in the truth table, if enable input is 1 (EN= 1) only one of the outputs (Y0 – Y3), is active for a given input. The output Y0 i s a c t i v e , i . e . , Y0= 1 when inputs A= B= 0, Y1 i s a c t i v e when inputs, A= 0 and B= 1, munotes.in

Page 103

103 b) 3- to-8 Line Decoder: A 3-to-8 line decoder has three inputs (A, B, C) and eight outputs (Y0- Y7). Based on the 3 inputs one of the eight outputs is selected The three inputs are decoded into eight outputs, each output signifying one of the minterms of the 3-input variables. This decoder is used for binary-to-octal conversion. The input variables may represent a binary number and the outputs will signify the eight digits in the octal number system. The output variables are mutually exclusive because only one output can be equal to 1 at any one time. The output line whose value is equal to 1 signifies the minterm equivalent of the binary number currently accessible in the input lines.
Fig.Truth table 3- to-8 Line Decoder
Fig. 3- to-8 Line Decoder munotes.in

Page 104

104 ii) Demultiplexer: Demultiplex means one into many. Demultiplexing is the process of taking information from one input and transmitting the same over one of several outputs. A demultiplexer is a combinational l o g i c c i r c u i t t h a t receives information on a single input and transmits the same information over one of several (2n) output lines
Fig. Demultiplexer circuit The block diagram of a demultiplexer which is opposite to a multiplexer in its operation is shown above. The circuit has one input signal, ‘n’ select signals and 2n output signals. The select inputs determine to which output the data input will be connected. As the serial data is changed to parallel data, i.e., the input produced to appear on one of the n output lines, the demultiplexer is also called a ―data distributer. i) 1-to-4 Demultiplexer: A 1-to-4 demultiplexer has a single input, Din, four outputs (Y0 to Y3) and two select inputs (S1 and S0).
Fig. 1-to-4 Demultiplexer The input variable Din has a path to all four outputs, but the input information is directed to only one of the output lines. The truth table of the 1-to-4 demultiplexer is shown below. munotes.in

Page 105

105
Table: Input /Output of 1-to-4 Demultiplexer From the truth table, it is clear that the data input, Din is connected to the output Y0, when S1= 0 and S0= 0 and the data input is connected to output Y1 when S1= 0 and S0= 1. Similarly, the data input is connected to output Y2 a n d Y3 w h e n S1= 1 and S0= 0 and when S1= 1 and S0= 1, respectively. From the truth table, the expression for outputs can be written as follows, Y0= S1‘S0‘Din Y1= S1‘S0Din Y2= S1S0‘Din Y3= S1S0Din
Fig. Circuit diagram 1-to-4 Demultiplexer Now, using the above expressions, a 1-to-4 demultiplexer can be applied using four 3-input AND gates and two NOT gates. Here, the input data line Din, is connected to all the AND gates. The two select lines S1, S0 enable only one gate at a time and the data that appears on the input line passes through the selected gate to the associated output line. b)1-to-8 Demultiplexer : A 1-to-8 demultiplexer has a single input, Din, eight outputs (Y0 to Y7) and three select inputs (S2, S1 and S0). It distributes one input line to Dn munotes.in

Page 106

106 eight output lines based on the select inputs. The truth table of 1-to-8 demultiplexer is shown below. Din S2 S1 S0 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0 0 X X X 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 Table: Input/output of 1-to-8 Demultiplexer From the above truth table, it is clear that the data input is connected with one of the eight outputs based on the select inputs. Now from this truth table, the expression for eight outputs can be written as follows Y0 = S2’S1’S0’ Din Y4 = S2 S1’S0’ Din Y1 = S2’S1’S0 Din Y5 = S2 S1’S0’ Din Y2 = S2’S1S0’ Din Y6 = S2 S1 S0’ Din Y3 = S2’S1S0 Din Y7 = S2 S1 S0’ Din Now using the above expressions, the logic diagram of a 1-to-8 demultiplexer can be drawn as shown below. Here, the single data line, Din is connected to all the eight AND gates, but only one of the eight AND gates will be enabled by the select input lines. For example, if S2S1S0= 000, then only AND gate-0 will be enabled and thereby the data input, Din will appear at Y0. Similarly, the different combinations of the select inputs, the input Din will appear at the respective output.
Fig.Circuit diagram 1-to-8 Demultiplexer munotes.in

Page 107

107 5.3 CODE CONVERTERS DESIGN AND IMPLEMENTATION Introduction: The converters, which convert one code to another code are called as code converters. These code converters basically consist of Logic gates. The availability of a large variety of codes for the same distinct elements of information outcomes in the use of different codes by different digital systems. It is necessary to use the output of one system as the input to the other. Thus a conversion circuit must be introduced b e t w e e n t h e t w o systems if each uses different codes for the same information. A code converter is a circuit that makes the two systems well-matched even though each uses the different codes. Code converters are used for protecting private information from detectives. They are also used to enhance data portability and tractability. Code converters have found applications in algorithm generation and communication. Some of the major codes are as follows: Binary Code: A s y m b o l i c r e p r e s e n t a t i o n o f d a t a / i n f o r m a t i o n i s called code. The base or radix of the binary number is 2. Hence, it has two independent symbols. The symbols used are 0 and 1. A binary digit is called a bit. A binary number consists of sequence of bits, each of which is either a 0 or 1. Each bit carries a weight based on its position comparative to the binary point. The weight of each bit position is one power of 2 greater than the weight of the position to its immediate right. Code Converters Design and Implementation done with t h e h e l p o f following way as below- a) Binary code to Gray code converter b) Parity Bit Generator i) Even Parity Generator ii) Odd Party Generator c) Parity Checker i) Even Parity Checker ii) Odd Party Checker a) Binary code to Gray code converter: Let us implement a converter, which converts a 4-bit binary code WXYZ into its equivalent Gray code ABCD. The following table shows the Truth table of a 4-bit binary code to Gray code converter. munotes.in

Page 108

108 Binary code WXYZ WXYZ Gray code ABCD 0000 0000 0001 0001 0010 0011 0011 0010 0100 0110 0101 0111 0110 0101 0111 0100 1000 1100 1001 1101 1010 1111 1011 1110 1100 1010 1101 1011 1110 1001 1111 1000 Fig. -bit binary code to Gray code converter Boolean Expression: From Truth table, we can write the Boolean functions for each output bit of Gray code as below A = Σm(8,9,10,11,12,13,14,15) B = Σm(4,5,6,7,8,9,10,11) C = Σm(2,3,4,5,10,11,12,13) D = Σm(1,2,5,6,9,10,13,14) Let us simplify the above functions using 4 variable K-Maps. K-Map: Let us simplify the above functions using 4 variable K-Maps. The following figure shows the 4 variable K-Map for simplifying Boolean function, A. munotes.in

Page 109

109
Fig. 4 variable K-Maps By grouping 8 adjacent ones, we got A=WA=W. The following figure shows the 4 variable K-Map for simplifying Boolean function, B.
Fig. Simplification of 4 variable –K-Map There are two groups of 4 adjacent ones. After grouping, we will get B as B=W′X+WX′=W⊕XB=W′X+WX′=W⊕X Similarly, we will get the following Boolean functions for C & D after simplifying. C=X′Y+XY′=X⊕YC=X′Y+XY′=X⊕Y D=Y′Z+YZ′=Y⊕ZD=Y′Z+YZ′=Y⊕Z Circuit Diagram: The following figure shows the circuit diagram of 4-bit binary code to Gray code converter.
Fig. 4-bit binary code to Gray code converter munotes.in

Page 110

110 Since the outputs depend only on the present inputs, this 4-bit Binary code to Gray code converter is a combinational circuit. Similarly, you can implement other code converters. b) Parity Bit Generator: There are two types of parity bit generators based on the type of parity bit being generated. Even parity generator generates an even parity bit. Similarly, odd parity generator generates an odd parity bit. i) Even Parity Generator ii) Odd Party Generator i) Even Parity Generator: Let us implement an even parity generator for a 3-bit binary input, WXY. It generates an even parity bit, P. If odd number of ones present in the input, then even parity bit, P should be ‘1’ so that the resultant word contains even number of ones. For other combinations of input, even parity bit, P should be ‘0’. The following table shows the Truth table of even parity generator. Binary Input WXY Even Parity bit P 000 0 001 1 010 1 011 0 100 1 101 0 110 0 111 1 Table. Even parity generator From the above Truth table, we can write the Boolean function for even parity bit as P=W′X′Y+W′XY′+WX′Y′+WXYP=W′X′Y+W′XY′+WX′Y′+WXY ⇒P=W′(X′Y+XY′)+W(X′Y′+XY)⇒P=W′(X′Y+XY′)+W(X′Y′+XY) ⇒P=W′(X⊕Y)+W(X⊕Y)′=W⊕X⊕Y⇒P=W′(X⊕Y)+W(X⊕Y)′=W⊕X⊕Y The following figure shows the circuit diagram of even parity generator.
Fig. circuit diagram of even parity generator munotes.in

Page 111

111 This circuit consists of two Exclusive-OR gates having two inputs each. First Exclusive OR gate having two inputs W & X and produces an output W ⊕ X. This output is given as one input of second Exclusive-OR gate. The other input of this second Exclusive-OR gate is Y and produces an output of W ⊕ X ⊕ Y. ii) Odd Parity Generator: If even number of ones present in the input, then odd parity bit, P should be ‘1’ so that the resultant word contains odd number of ones. For other combinations of input, odd parity bit, P should be ‘0’.Follow the same procedure of even parity generator for implementing odd parity generator. The circuit diagram of odd parity generator is shown in the following figure.
Fig: circuit diagram of odd parity generator The above circuit diagram consists of Ex-OR gate in first level and Ex-NOR gate in second level. Since the odd parity is just opposite to even parity, we can place an inverter at the output of even parity generator. In that case, the first and second levels contain an Ex-OR gate in each level and third level consist of an inverter c) Parity Checker: There are two types of parity checkers based on the type of parity has to be checked. Even parity checker checks error i n t h e t r a n s m i t t e d data, which contains message bits along with even parity. Similarly, odd parity checker checks error in the transmitted data, which contains message bits along with odd parity i) Even Parity Checker ii) Odd Party Checker i) Even parity checker: Let us implement an even parity checker circuit. Consider a 3-bit binary input, WXY is transmitted along with an even parity bit, P. So, the resultant word data contains 4 bits, which will be received as the input of even parity checker. munotes.in

Page 112

112 It generates an even parity check bit, E. This bit will be zero, if the received data contains an even number of ones. That m e a n s , t h e r e i s n o error in the received data. This even parity check bit will be one, if the received data contains an odd number of ones. That means, there is an error in the received data. The following table shows the Truth table of an even parity checker. 4-bit Received Data WXYP Even Parity Check bit E 0000 0 0001 1 0010 1 0011 0 0100 1 0101 0 0110 0 0111 1 1000 1 1001 0 1010 0 1011 1 1100 0 1101 1 1110 1 1111 0 Table: Truth Table - even parity checker From the above Truth table, we can perceive that the even parity check bit value is ‘1’, when odd number of ones present in the received data. That means the Boolean function of even parity check bit is an odd function. Exclusive-OR function satisfies this condition. Hence, we can directly write the Boolean function of even parity check bit as =W⊕X⊕Y⊕PE=W⊕X⊕Y⊕P The following figure shows the circuit diagram of even parity checker.
Fig: circuit diagram of even parity checker munotes.in

Page 113

113 This circuit consists of three Exclusive-OR gates having two inputs each. The first level gates produce outputs of W⊕XW⊕X & Y⊕PY⊕P. The Exclusive-OR gate, which is in second level produces an output of W⊕X⊕Y⊕PW⊕X⊕Y⊕P Odd Parity Checker: Consider a 3-bit binary input, WXY is transmitted along with odd parity bit, P. So, the resultant word data contains 4 b i t s , w h i c h w i l l b e received as the input of odd parity checker. It generates an odd parity check bit, E. This bit will be zero, if the received data contains an odd number of ones. That means, there is no error in the received data. This odd parity check bit will be one, if the received data contains even number of ones. That means, there is an error in the received data. Follow the same procedure of an even parity checker for implementing an odd parity checker. The circuit diagram of odd parity checker is shown in the following figure.
Fig: circuit diagram of odd parity checker The above circuit diagram consists of Ex-OR gates in first level and Ex-NOR gate in second level. Since the odd parity is just opposite to even parity, we can place an inverter at the output of even parity checker. In that case, the first, second and third levels contain two Ex-OR gates, one Ex-OR gate and one inverter correspondingly. ***** munotes.in

Page 114

114 6 ARITHMETIC CIRCUITS Unit Structure 6.1 Arithmetic Circuits 6.2 Introduction to arithmetic circuits 6.3 Adder 6.4 BCD Adder 6.5 Excess-3 Adder 6.6 Binary Subtractors 6.7 BCD Subtractors 6.1 INTRODUCTION Combinational circuit is a circuit in which we have to combine the different gates in the circuit, for example encoder, decoder, multiplexer and demultiplexer. Some of the characteristics of combinational circuits are as below – • The output of combinational circuit at any instant of time, depends only on the stages present at input stations. • The combinational circuit do not use any memory. The previous state of input does not have any effect on the present state of the circuit. • A combinational circuit can have an ‘n’ number of inputs and ‘m’ number of outputs. Following are the various types of arithmetic circuits – Adder, BCDAdder, Binarysubtractor, BCDsubtractor etc. 6.2 ADDER Adder arithmetic circuit can classified into two main types as – a) Half Adder b) Full Adder munotes.in

Page 115

115 a) Half Adder: Introduction: Half adder is a combinational logic circuit with two inputs and two outputs. The half adder circuit is designed to add two single bit binary number A and B. It is the basic building block for addition of two single bit numbers. This circuit has two outputs carry and sum. Block Diagram Truth Table Circuit diagram

b) Full Adder: Introduction: Full adder is designed to overcome the drawback of Half Adder circuit. It can add two one-bit numbers A and B, and carry C. The full adder is a three input and two output combinational circuit Block Diagram Truth Table Circuit diagram
Inputs Output A B Cin S Co 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1
N-Bit Parallel Adder: Introduction: The Full Adder is capable of adding only two single d i g i t b i n a r y number along with a carry input. But in practical we need to add binary munotes.in

Page 116

116 numbers which are much longer than just one bit. To add two n-bit binary numbers, we need to use the n-bit parallel adder. It uses a number of full adders in cataract. The carry output of the previous full adder is connected to carry input of the next full adder. 4. Bit Parallel Adder: Introduction: `In the block diagram, A0 a n d B0 r e p r e s e n t t h e L e a s t S i g n i f i c a n t Bits(LSB) of the four bit words A and B. Hence Full Adder-0 is the lowest stage. Hence its Cin h a s b e e n p e r m a n e n t l y m a d e 0 . T h e r e s t o f t h e connections are precisely same as those of n-bit parallel adder is shown in fig. The four bit parallel adder is a very common logic circuit. Block diagram:
6.4 BCD ADDER Introduction: A 4-bit binary adder that is accomplished of adding two 4-bit words having a BCD (binary-coded decimal) format. The result of the addition is a BCD-format 4- bit output word, demonstrating the decimal sum of the addend and augend, and a carry that is generated if t h i s s u m e x c e e d s a decimal value of 9. Use of BCD Adder: A BCD 1-digit adder is a circuit that adds two BCD digits in parallel and also produces the Sum digit in BCD along with the essential correction logic. It can be seen that a 4-bit binary adder is used originally to add two BCD digits with a carry-input. When the binary sum is less than or equal to 9, it also correctly represents the sum in BCD. When the binary sum is greater than 9, however, it does not represent the correct BCD sum. The sum in BCD is to be attained by adding 6 to it. munotes.in

Page 117

117 In the BCD representation system each digit is encoded into its binary equivalent with four (4) bits. Decimal BCD 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 Table: BCD representation system Observe that only 10 of the 16 possible bit-patterns are used in BCD. That means the remaining 6 patterns could be treated as don't-care cases. For the arithmetic addition of two decimal digits in BCD, the maximum value that may be produced as the result is 9 + 9 + 1 = 19 (two largest operands plus the carry). If we try to add two decimal digits in BCD with a 4-bit ripple-carry adder we will get a binary sum extending from 0 to 19. When the binary sum is less than or equal to 9, it may represents the sum in BCD. When the binary sum is greater than 9, however, it does not represent the correct BCD sum. The sum in BCD is to be obtained by adding 6 to it. Perform the following addition in BCD as explained above 1) 7 + 4 2) 3 + 2 3) 9 + 9 The above examples should benefit you realize when the conversion is necessary and what should be done to perform the conversion correctly. Here is a block diagram of a 1-digit BCD adder
Fig. Block diagram of a 1-digit BCD adder munotes.in

Page 118

118 Complete the truth table below Inputs Binary Sum BCD Sum Decimal Number Cin X Y Cout Z Cout S 0 0000 0000 0 0000 0 0000 0 0 0000 0001 0 0001 0 0001 1 0 0001 0001 0 0101 0100 0 0101 0101 0 0101 0110 0 1000 1000 1 0000 1 0110 16 0 1000 1001 0 1001 1001 1 1001 1001 Table: Truth table - 1-digit BCD adder Upon an examination of the 1-digit BCD adder block diagram shown above, you should notice that the only block you do not have a circuit for is the ―Sum > 9”? block. Having the circuit just excitingly appear on your circuit diagrams 3.4.4 Excess-3 Adder: The excess-3 code is a non-weighted code used to express code used to express decimal numbers. It is a self-complementary Binary Coded Decimal (BCD) code and numerical system which has partial representation. The primary benefit of excess-3 coding over non-biased coding is that a decimal number can be nines' complemented as easily as a binary number can be ones' complemented, just by inverting all bits.Excess-3 is a modified form of a BCD number. The excess-3 code can be derived from the natural BCD code by adding 3 to each coded number. For example, decimal 12 can be represented in BCD as 0001 0010. Now adding 3 to each digit we get excess-3 code as 0100 0101 (12 in decimal). With this information the truth table for BCD to Excess-3 code converter can be determined as- munotes.in

Page 119

119
Table: Truth Table - Excess-3 Adder From the truth table, the logic expression for the Excess-3 code outputs can be written as, E3 = Σm (5, 6, 7, 8, 9) + Σd (10, 11, 12, 13, 14, 15) E2 = Σm (1, 2, 3, 4, 9) + Σd (10, 11, 12, 13, 14, 15) E1 = Σm (0, 3, 4, 7, 8) + Σd (10, 11, 12, 13, 14, 15) E0 = Σm (0, 2, 4, 6, 8) + Σd (10, 11, 12, 13, 14, 15) K-map Simplification:
munotes.in

Page 120

120 Circuit Diagram:
Fig.Excess-3 Adder circuit 6.6 BINARY SUBTRACTORS Introduction: The subtraction can be carried out by taking the 1's or 2's complement of the number to be subtracted. For example we can perform the subtraction (A-B) by adding either 1's or 2's complement of B to A. That means we can use a binary adder to perform the binary subtraction. 4. Bit Parallel Subtractor: Introduction: The number to be subtracted (B) is first accepted through inverters to obtain its 1's complement. The 4-bit adder then adds A and 2's complement of B to produce the subtraction. S3 S2 S1 S0 r e p r e s e n t s t h e result of binary subtraction (A-B) and carry output Cout r e p r e s e n t s t h e polarity of the result. If A > B then Cout = 0 and the result of binary form (A-B) then Cout = 1 and the result is in the 2's complement form. Block diagram:
Fig. 4 Bit Parallel Subtractor munotes.in

Page 121

121 Types of Subtractors: Subtractors circuit can classified into two main category as- a) Half Subtractor b) Full Subtractors a) Half Subtractors: Introduction: Half subtractor is a combination circuit with two inputs and two outputs. It produces the difference between the two binary bits at the input and also produces an output to indicate if a 1 has been borrowed. In the subtraction (A-B), A is called as Minuend bit and B i s c a l l e d a s Subtrahend bit. Truth Table Circuit Diagram

a) Full Subtractors Introduction: The drawback of a half subtractor is overcome by full subtractor. The full subtractor is a combinational circuit with three inputs A,B,C and two output D and C'. A is the 'minuend', B is 'subtrahend', C is the 'borrow' produced by the previous stage, D is the difference o u t p u t a n d C ' i s t h e borrow output. Truth Table Circuit Diagram

munotes.in

Page 122

122 6.7 BCD Subtractor Introduction: A Binary Coded Decimal (BCD) adder is a circuit which adds two 4-bit BCD numbers in parallel and produces a 4-bit BCD result. The block diagram of conventional BCD adder. The circuit must i n c l u d e t h e correction logic to produce valid BCD output.subtractor an electronic logic circuit for calculating the difference between two binary numbers, the minuend and the number to be subtracted, the subtrahend . A full subtractor performs this calculation with three inputs- subtrahend bit, minuend bit, and borrow bit BCD Subtraction: Addition of signed BCD numbers can be accomplished by using 9’s or 10’s complement methods. A negative BCD number can be expressed by taking the 9’s or 10’s complement.The BCD Subtraction using 9’s Complement and BCD Subtraction using 10‘s Complement numbers and BCD Subtraction process using it. 9s Complement: The 9’s complement of a decimal number is found by subtracting each digit in the number from 9. The 9’s complement o f e a c h o f t h e decimal digits is as follows: Digit 9’s Complement 0 9 1 8 2 7 3 6 4 5 5 4 6 3 7 2 8 1 9 0 Table: 9’s Complement BCD Subtraction using 9’s Complement: In 9’s Complement subtraction when 9’s Complement of smaller number is added to the larger number carry is produced. It is essential to add this carry to the result. When larger number is subtracted from smaller one, there is no carry, and the result is in 9’s complement form and negative. This is demonstrated in following ways as: munotes.in

Page 123

123 Regular subtraction 9’s Complement Subtraction (a) 8 8 - 2 + 7 9’s complement of 2 6 1 5 + 1 Add carry to result 6 (b) 2 8 2 8 - 1 3 + 8 6 1 5 1 1 4 9 ’ s c o m p l e m e n t o f 1 3 + 1 1 5 (c) 1 8 1 8 - 2 4 + 7 5 9’s complement of 24 - 6 9 3 9’s complement of result (No carry indicates that the answer is negative and in complement form) - 0 6 The 10’s complement of a decimal number is equal to the 9’s complement plus 1. BCD Subtraction using 10s Complement: The BCD Subtraction using 10’s Complement can be used to accomplish subtraction by adding the minuend to the 10’s Complement of the subtrahend and dropping the carry. This is demonstrated in following ways as: Regular subtraction 10’s Complement Subtraction (a) 8 8 - 2 + 8 10’s complement of 2 6 1 6 Drop carry (b) 2 8 2 8 - 1 3 + 8 7 10’s complement of 13 1 5 1 1 5 Drop carry (c) 1 8 1 8 - 2 4 + 7 5 10’s complement of 24 - 6 9 4 10’s complement of result (No carry indicates that the answer is negative and in complement form) 0 6 munotes.in

Page 124

124 From the above examples we can review steps for 9’s Complement BCD subtraction as follows: • Find the 9’s complement of a negative number • Add two numbers using BCD addition • If carry is generated add carry to the result otherwise find the 9s complement of the result.
Fig.4 bit BCD substractor using 9’s complement munotes.in

Page 125

125 Above figure demonstrate the logic diagram of the circuit to implement above stated steps to perform BCD subtraction using 9’s Complement method. First binary adder finds the 9’s Complement of the negative number. It does this by inverting each bit o f B C D n u m b e r a n d adding 10 (1 0 1 02) to it. Let us find the 9’s complement of 2 0 0 1 0 B C D f o r 2 1 1 0 1 I n v e r t i n g e a c h b i t 1 0 1 0 A d d 1 0 ( 1 0 1 02) Ignore carry 1 0 1 1 1 9’s complement for 2 Next two 4-bit binary adders accomplish the BCD addition. The last adder finds the 9’s Complement of the result if carry is not generated after BCD addition otherwise it adds carry in the result. From the above examples we can summarize steps for 10s complement BCD subtraction as: • Find the 10’s complement of a negative number • Add two numbers using BCD addition • If carry is not generated find the 10s Complement of the result.
Fig.4 bit BCD substractorusing 10’s complement munotes.in

Page 126

126 The logic diagram of the circuit to implement above stated steps to perform subtraction using 10s Complement method. First binary adder finds the 10’s Complement of the negative number (9’s complement + 1). Next two 4-bit binary adders perform the BCD addition. Lastly, last 4-bit binary adder finds the 10’s complement of the number if carry is not generated after BCD addition. ***** munotes.in

Page 127

127 7 MULTIPLEXER Unit Structure 7.1 Introduction 7.2 Multiplier 7.3 Comparator 7.1 INTRODUCTION Multiplexer is a distinct type of combinational circuit. There are ‘n’ data inputs, one output and ‘m’ select inputs with 2m = ‘n’. It is a digital circuit which selects one of the ‘n’ data inputs and routes it to the output. The selection of one of the ‘n’ inputs is done by the selected inputs. Depending on the digital code applied at the selected inputs, one out of ‘n’ data sources is selected and transmitted to the single output ‘Y’. ‘E’ is called the strobe or enable input which is useful for the cascading. It is commonly an active low terminal that means it will complete the required operation when it is low. Block diagram:
Fig: n:1 Multiplexer Types of Multiplexer: Multiplexers come in multiple variations a) 2 : 1 multiplexer b) 4 : 1 multiplexer munotes.in

Page 128

128 c) 16 : 1 multiplexer d) 32 : 1 multiplexer a) 2 : 1 multiplexer: Block Diagram:
Fig.2:1 multiplexer Truth Table:
Table: Truth Table Demultiplexers: Introduction: A demultiplexer achieves the reverse operation of a multiplexer i.e. it receives one input and distributes it over several outputs. It has only one input, n outputs, m select input. At a time only one output line is selected by the select lines and the input is transmitted to the selected output line. Types of demultiplexer: Demultiplexers comes in multiple variations a) 1 : 2 demultiplexer b) 1 : 4 demultiplexer c) 1 : 16 demultiplexer munotes.in

Page 129

129 d) 1 : 32 demultiplexer a) 1 : 2 demultiplexer Block diagram:
Fig. 1:2 Demux Truth Table: Enable Select Output E S Y0 Y1 0 X 0 0 1 0 0 Din 1 1 Din 0 Table : 1:2 Demux truth table 7.6 COMPARATOR Introduction: Comparator is a combinational logic circuit that compares the magnitudes of two binary quantities to determine which one has the greater magnitude. In other word, a comparator determines the association of two binary quantities. An ex-OR gate can be used a s a b a s i c comparator. Digital comparators are also called as binary or logic comparators. Usage: This logic circuit is used for testing whether the binary number at one input is greater than or less than or equal to another binary number. In other word, Comparator is a very useful combinational circuit capable of comparing two numbers as input in binary form and determines whether one number is greater than, less than or equal to other number. Comparators can also be used as window detectors. A comparator is used to compare two voltages and determine whether a given input voltage is under voltage or over voltage. Comparators are used in central processing unit (CPUs) and microcontrollers (MCUs). munotes.in

Page 130

130 Types of Comparators: There are two types of comparators: 1. Equality or Identity Comparator 2. Magnitude or inequality comparator 1. Equality or Identity Comparator: Identity Comparator is a digital comparator that has only one output. The circuit of the equality comparator is made up from an exclusive NOR gate (XNOR) per pair of input bits. If the two inputs are equal (both logic 1 or both logic 0) then a logic 1 is output Consider two 4-bit binary numbers A and B so A = A3A2A1A0 B = B3B2B1B0
Fig. Identity Comparator Here each subscript represents one of the digits in the numbers. Equality: The binary numbers A and B will be equal if all the p a i r s o f significant digits of both numbers are equal, i.e., A3=B3, A2= B2, A1=B1 and A0 = B0 Since the numbers are binary, the digits are either 0 o r 1 a n d t h e Boolean function for equality of any two digits Ai and Bi can be expressed as xi = Ai Bi + iiAB+ we can also replace it by XNOR gate in digital electronics. X i is 1 only if Ai and Bi are equal For the equality of A and B, all variables (for i=0,1,2,3) must be 1. So the equality condition of A and B can be implemented using the AND operation as X i is 1 only if Ai and Bi are equal munotes.in

Page 131

131 The binary variable (A=B) is 1 only if all pairs of d i g i t s o f t h e t w o numbers are equal 2. Magnitude or inequality comparator: To manually determine the greater of two binary numbers, you have inspect the relative magnitudes of pairs of significant digits, starting from the most significant bit, gradually proceeding towards lower significant bits until an inequality is found. When an inequality is found, if the corresponding bit of A is 1 and that of B is 0 then we conclude that A>B. This sequential comparison can be expressed logically as: Fig.2 ()33 322 3 2 11 3 2 1 00AB A B x A B x x A B x x x A B>= + + + ()32 1 033 23 2 13 2 1 0AB A B x A B x x A B x x x A B<= + + +
Fig.2 inequality comparator (A>B) and (A < B) are output binary variables, which are equal to 1 when A>B or A