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
Page 132
132 Unit 4 8 MULTIPLEXER AND DEMULTIPLEXER Unit Structure 8.0 Multiplexer 8.1 Demultiplexer 8.2 Decoder 8.3 Encoder 8.4 Arithmetic Logic 8.5 Unit Questions 8.6 Further Reading 8.0 OBJECTIVE This chapter takes a comprehensive look at another class of building blocks used to design more complex combinational circuits, and covers building blocks such as multiplexers and demultiplexers and other derived devices such as encoders and decoders. Particular emphasis is given to the operational basics and use of these devices to design more complex combinational circuits. 8.1 MULTIPLEXER • Multiplex means many into one. • A digital multiplexer is a combinational circuit that selects binary information from one of many input lines and directs it to a single output line. • The selection of a particular input line is controlled by a set of selection lines. • It is also called a data selector is a device that selects between several analog or digital input signals and forwards it to a single output line munotes.in
Page 133
133 Block Diagram :
Fig.1 Block Diagram The circuit has n input signals, m select signals and 1 output signal. Note that, m control signals can select at the most 2m input signals thus n <=2m 4x1 Multiplexer
Fig.2 4x1 multiplexer block diagram The circuit diagram of a 4-to-l multiplexer is shown in Fig. Depending on control inputs S1 & S0, one of the four inputs Do to D3 is steered to output Y. Let us write the logic equation of this circuit. Clearly, it will give a SOP representation, each AND gate generating a product term, which finally are summed by OR gate. Thus, Y=S1′S0′D0 + S1′S0D1 + S1S0′D2 + S1S0D3 If S1=0 and S0= 0 munotes.in
Page 134
134 Y=0′ 0′ D0 + 0′ 0 D1 + 0 0′ D2 + 0 0 D3 Y=1.1 D0 + 1.0 D1 + 0.1 D2 + 0.0 D3 ( 0 ’ = 1 ) Y= D0 In other words, for S1S0 = 00, the first AND gate to which D0 is connected remains active and equal to D0 a n d a l l o t h e r A N D g a t e a r e inactive with output held at logic 0. Thus, multiplexer output Y is same as D0. If D0 =0, Y=0 and if D0 = 1, Y= 1. Control Signals Output S1 S0 Y 0 0 D0 0 1 D1 1 0 D2 1 1 D3 A logic diagram of 4-line to 1-line multiplexer is shown in figure 3 Each of the four input lines, D0 to D3, is applied to one input of an AND gate. Selection lines s1 and s0 are decoded to select a particular AND gate. The function table in the figure lists the input-to-output path for each possible bit combination of the selection lines. To demonstrate the circuit operation, consider the case when s1s0 = 10. The AND gate associated with input D2 has two of its inputs equal to 1 and the third input connected to D2. The other three AND gates have at least one input equal to 0, which makes their output equal to 0. The OR-gate output is now equal to the value of D2, thus providing a path from the selected input to the output.
Fig.3 logic diagram of 4 to 1 multiplexer munotes.in
Page 135
135 8.2 DEMULTIPLEXER • Demultiplex means one into many. • A demultiplexer is a circuit that receives information on a single line and transmits this information on one of 2n possible output lines. • The selection of a specific output line is controlled by the bit values of n selection lines. Select lines
Fig.4. Demultiplexer Block diagram Demultiplexer has single data input (D) and n outputs (Y0 – Yn-1). While number of Select lines depends on number of outputs. If ‘n’ is number of outputs and ‘m’ is number of select lines then the relation between them is given by n = 2m. 1 to 4 Demultiplexer:
Fig. 5 Block diagram 1 to 4 Demultiplexer The truth table of this type of demultiplexer is given below. Input Control Signals Output S1 S0 Y3 Y2 Y1 Y0 D 0 0 0 0 0 D D 0 1 0 0 D 0 D 1 0 0 D 0 0 D 1 1 D 0 0 0 munotes.in
Page 136
136 From the truth table it is clear that, when S1=0 and S0= 0, the data input is connected to output Y0 and when S1= 0 and S0=1, then the data input is connected to output Y1. Similarly, other outputs are connected to the input f o r o t h e r t w o combinations of select lines. 01 0Y. DSS= 11 0Y. DSS= 21 0Y. DSS= 31 0Y. DSS=
Fig.6 Logic Diagram 1 to 4 Demultiplexer Decoder: • A decoder is similar to a demultiplexer, with one exception-there is no data input. • The only inputs are the Select signals. • Decoder is a logic circuit that converts n-bit binary input code into m output lines. • The decoders presented here are called n-to-m line decoders where m < 2n. • Each output line will be activated for only one of the possible combination of inputs. munotes.in
Page 137
137
Fig. 7 Block diagram 2 to 4 Decoder:
The two inputs are decoded into four outputs, each output representing one of the minterms of the 2-input variables. The two inverters provide the complement of the inputs, and each one of the four AND gates generates one of the minterms. A particular application of this decoder would be a binary-to-octal conversion. The input variables may represent a binary number, and the outputs will then represent the four digits. However, a 2-to-4 line decoder can be used for decoding any 2-bit code to provide four outputs, one for each element of the code. 01 0Y.SS= 11 0Y.SS= 21 0Y.SS= 31 0Y.SS= Inputs Outputs S1 S0 Y3 Y2 Y1 Y0 X X 0 0 0 0 0 0 0 0 0 1 munotes.in
Page 138
138 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0
Encoder: • An Encoder is a combinational circuit that performs t h e r e v e r s e operation of Decoder. • An encoder converts an active input signal into a coded output signal • There are n input lines, only one of which is active. • Internal logic within the encoder converts this active input to a coded binary output with m bits.
Decimal-to-BCD Encoder: Figure shows a common type of encoder-the decimal-to-BCD encoder. The switches are push-button switches like those of a pocket calculator. When button 3 is pressed, the C and D OR gates have h i g h i n p u t s ; therefore, the output is ABCD=0011 munotes.in
Page 139
139 If button 5 is pressed, the output becomes ABCD=0101 When switch 9 is pressed, ABCD= 1001
Encoders Decoders Encoders may have more than one input line active and may have more than one output line active at any given time Decoders may have more than one input line active at any given time but only one output line will be active Number of input lines is more than number of output lines Number of output lines is more than number of input lines Number of input lines = 2Number of output lines Number of output lines = 2Number of input lines Encoder is logic device used to create binary code for given decimal input Decoder is logic device used to decode binary input to give decimal output Priority Encoder: A priority encoder is a practical form of an encoder. The encoders available in IC form are all priority encoders. In this type of encoder, a priority is assigned to each input so that, when more than one input is simultaneously active, the input with the highest priority is encoded. munotes.in
Page 140
140 In previous cases we saw that if two or more input lines are activated then output code is invalid. Therefore we h a v e t o m o d i f y t h e circuit. The modification is we have to define the priority of given number. It means whenever two or more inputs are applied at a time, internal hardware will check this condition and if priority is set such that higher input is to be taken into account and remaining are considered as don’t care then output code that will appear is of higher input. Arithmetic Logic Unit (ALU): The arithmetic logic unit (ALU) is a digital building block capable of performing both arithmetic as well as logic operations. Arithmetic logic units that can perform a variety of arithmetic operations such as addition, subtraction, etc., and logic functions such as ANDing, ORing, EX-ORing, etc., on two four-bit numbers are usually available i n I C f o r m . T h e function to be performed is selectable from function select pins. Functional details of these ICs are given in the latter part of the chapter under the heading of Application-Relevant Information. More than one such IC can always be connected in cascade to perform arithmetic and logic operations on larger bit numbers. 8.5 QUESTIONS 1. Define Multiplexer. 2. Write short note on 4 –to- 1 Channel Multiplexer. 3. Explain 4- to -2 Channel Multiplexer With help of suitable diagram. 4. What is De-Multiplexer? 5. What is Digital Encoder? Explain 4- to -2 Bit Binary Encoder with help of suitable diagram. 6. What is Priority Encoder? Explain 8- to -3 Priority Encoder with the help of suitable diagram. ***** munotes.in
Page 141
141 9 FLIP-FLOPS Unit Structure 9.0 Objective 9.1 Introduction to Sequential Circuits 9.2 SR Flip-Flop 9.3 D Flip-Flop 9.4 JK Flip-Flop 9.5 Race Around Condition 9.6 Master Slave JK Flip-Flop 9.7 T Flip-Flop 9.8 Conversion of flip-flop from one type to another 9.9 Applications of Flip-Flop 9.0 OBJECTIVE • After completing this chapter, you will be able to: Understand the basics of Sequential Logic Circuits. • Learn different types of Flips –Flops, their working and applications with the help of suitable diagrams. 9.1 INTRODUCTION TO SEQUENTIAL CIRCUITS Sequential Circuits: D i g i t a l e l e c t r o n i c s i s c l a s s i f i e d i n t o combinational logic and sequential logic. Combinational logic output depends on the inputs levels, whereas sequential logic output depends on stored levels and also the input levels. Sequential logic elements perform as many different f u n c t i o n s a s combinational logic elements; however, they do carry out certain well-defined functions, which have been given names. Latch: A latch is a 1-bit memory element. You can capture a single bit in a latch at one instant and then use it later; for example, when adding munotes.in
Page 142
142 numbers, you can capture the carry-out in a latch and use it as a carry-in in the next calculation. Register: The register is just m latches in a row and is able to store an m-bit word; that is, the register is a device that stores one memory word. A computer’s memory is just a very large array of registers. Flip-flop: In the electronics world, a flip-flop is a type of circuit that has two states (i.e., on or off, 1 or 0). These circuits are often used to store state information. By sending a signal to the flip-flop, the state can be changed. Flip-flops are used in many electronics, including computers and communications equipment. Flip-flops and latches are used as data storage elements. Such data storage can be used for storage of state, and such a circuit is described as sequential logic. When used in a finite-state machine, the output and next state depend not only on its current input, but also on its current state (and hence, previous inputs). It can also be used for counting of pulses, and for synchronizing variably-timed input signals to some reference timing signal. A flip-flop can be symbolically represented as shown below:
Generally, Set and Reset Pins are input pins; whereas Q and Q` are output pins. When Set Pin= logic 1, the output Q is SET to 1. (Q`= 0) When Reset Pin=logic 1, the output Q is RESET to 0. (Q`=1) Note that Q` is complement of Q at all times. 9.2 SR FLIP- FLOP The R-S flip-flop is the most basic of all flip-flops. The letters ‘‘R’’ and ‘‘S’’ here stand for RESET and SET. It is constructed by feeding the outputs of two NOR gates back to the munotes.in
Page 143
143 other NOR gates as shown below: RS Flip-Flop composed of two NOR Gates:
To understand the operation of the RS-flip-flop (or RS-latch) consider the following scenarios: • S=1 and R=0: • The output of the bottom NOR gate is equal to zero, Q'=0. • Hence both inputs to the top NOR gate are equal to one, thus, Q=1. • Hence, the input combination S=1 and R=0 leads to the flip-flop being set to Q=1. • S=0 and R=1: • The output of the top NOR gate is equal to zero, Q=0. • Hence, the inputs to the bottom NOR gate are equal to 1, thus • Q`=1 • We say that the flip-flop is reset, that is reset to Q=0. • S=0 and R=0: • Assume the flip-flop is set (Q=0 and Q'=1), then the output of the top NOR gate remains at Q=1 and the bottom NOR gate stays at Q'=0. • Similarly, when the flip-flop is in a reset state (Q=1 and Q'=0), it will remain there with this input combination. • Therefore, with inputs S=0 and R=0, the flip-flop remains in its state. • S=1 and R=1 • We can summarize the operation of the RS-flip-flop by the following truth table. • This input combination must be avoided munotes.in
Page 144
144 We can summarize the operation of the RS-flip-flop by the following truth table. R S Q Q Comment 0 0 Q Q` Hold State 0 1 1 Q` Set 1 0 0 1 Reset 1 1 ? ? Avoid Note, the output Q' is simply the inverse of Q. An RS flip-flop can also be constructed from NAND gates. S-R Flip-Flop Using NAND Gate: A basic NAND gate SR flip-flop circuit provides feedback from both of its outputs back to its opposing inputs. The term “Flip-flop” means that the output can be “flipped” into one logic Set state or “flopped” back into the opposing logic Reset state. The NAND Gate SR Flip-Flop Basic SR Flip-Flop Circuit:
The Set State: To understand the operation of the RS-flip-flop (or RS-latch) consider the following scenarios: S`=1 and R`=0: • In a NAND gate, if one of the input =0, then output o f N A N D gate=1. • Using this logic, the lower NAND gate Y will be Q’=1, assuming B=0. munotes.in
Page 145
145 • Let us consider the upper NAND gate X now. A=0 since Q’=1 from above, but S’=1. Therefore, output of X will be 0, that is Q=0. This is exactly what we had assumed when we said let B=0. • Thus, the SR flip-flop is said to be RESET to 1. Q=0. Q’=1 S`=0 and R`=1: • Using the same logic, the upper NAND gate X will be Q = 1 , assuming A=0. • Let us consider the lower NAND gate Y now. B=1 since Q=1 from above, but R`=1. Therefore, output of Y will be 0, that is Q`=0. This is exactly what we had assumed when we said let A=0. • We say that the flip-flop is set, that is set to Q=1. Q`=0. S’=0 and R`=0: • S`=0 and R`=0 is not desired or invalid condition. This must be avoided. This condition will cause both Q and Q` to go high together to logic 1. In such a case, the flip-flop will become unstable. S`=1 and R`=1: • When both S` and R` are equal to logic HIGH, the outputs Q and Q` can be at 1 or 0 logic level. This depends on the states of S` and R` before this input condition existed. Thus, S`=R`=1 results in no change of state of the outputs. Truth Table for this Set-Reset Function S` R` Q Q` State 1 1 Previous state Previous state No change 1 0 0 1 RESET 0 1 1 0 SET 0 0 ? ? Forbidden 9.3 D FLIP-FLOP The Delay Flip-Flop or D Flip-flop is easily formed from SR flip-flop by adding a NOT gate(inverter) as shown in the logic diagram We have observed that S’=0, R’=0 is a forbidden condition in SR NAND gate flip-flop. We can prevent this from happening by connecting a NOT gate between S and R inputs. munotes.in
Page 146
146 The D flip-flop ensures that S and R can never be simultaneously equal to each other. The single input then is called the Data input or simply D input. D-type Flip-Flop Circuit:
If D=1, then S=1 in the above circuit resulting in Q=1 and Q’=0 If D=0, then R=1 in the above circuit resulting in Q’=1 and Q=0. Thus, the D input condition is copied to the output Q w h e n t h e clock input is active. Once the clock input goes low, the output at Q and Q` will remain unchanged. We say that the output is “latched” at logic 0 or logic 1. Truth Table for the D-type Flip Flop: Clk D Q Q` Description ↓ » 0 X Q Q` Memory no change ↑ » 1 0 0 1 Reset Q » 0 ↑ » 1 1 1 0 Set Q » 1 Note that: ↓ and ↑ indicates direction of clock pulse as it is assumed D-type flip flops are edge triggered 9.4 JK FLIP-FLOP We have seen that S=0 and R=0 condition in SR NAND flip-flop is forbidden and should be avoided. Also, while Enable input is HIGH, the correct latching may not occur, if S or R changes state during this period. To overcome these two problems, the JK flip-flop was developed. The inputs J and K are derived from its inventor Jack Kilby. munotes.in
Page 147
147 The operation of JK flip-flop is same as the SR flip-flop for same S and R inputs. The difference is that it has no forbidden or invalid states of SR flip-flop. The JK flip flop is obtained by adding two NAND gates to SR NAND gate flip-flop as shown below: The Basic JK Flip-flop:
Both the S and the R inputs of the previous SR bi-stable have now been replaced by two inputs called the J and K inputs. Thus, J = S and K = R. The two 2-input AND gates of the gated SR bi-stable have now been replaced by two 3-input NAND gates with the third input of each gate connected to the outputs at Q and Q’. This cross coupling of the SR flip-flop allows the previously invalid condition of S = “1” and R = “1” state to be used to produce a “toggle action” as the two inputs are now interlocked. If the circuit is now “SET”, then the J input is inhibited by the “0” status of Q through the lower NAND gate. If the circuit is “RESET” the K input is inhibited by the “0” status of Q through the upper NAND gate. As Q and Q’ are always different we can use them to control the input. When both inputs J and K are equal to logic “1”, the JK flip flop toggles as shown in the following truth table munotes.in
Page 148
148 The Truth Table for the JK Function:
9.5 RACE-AROUND CONDITION Before getting into the race around condition, let us have a look at the JK flip-flop’s truth table. I n p u t O u t p u t s J K Q Q` 0 X X S a m e a s previous S a m e a s previous No change Clock Input comments 1 0 0 S a m e a s previous S a m e a s previous No change munotes.in
Page 149
149 1 0 1 0 1 R e s e t 1 1 0 1 0 s e t 1 1 1 Opposite of previous T o g g l e Here, Q is the present state and Q` is the next state. As you can see, when J, K and Clock are equal to 1, toggling takes place, i.e. The next state will be equal to the complement of the present state. Now, let us look at the timing diagram of JK flip-flop.
Here, T is the time period of the clock whereas delta t is the propagation delay. The delay between input and output is called a propagation delay. This is what was expected, but the output may not be like this all the time. This is where Race around condition comes into the play. Let us look at the timing diagram of JK flip-flop when the race around condition is considered
munotes.in
Page 150
150 When J, K and Clock are equal to 1, toggling takes place. Here, propagation delay has also been reduced, so the output will be given out at the instant input is given. So there is a toggling again. Therefore, whenever Clock is equal to 1 there are consecutive toggling. This condition is called as Race around condition. To put it in words, “For JK flip-flop if J, K and Clock are equal to 1 the state of flip-flop keeps on toggling which leads to uncertainty in determining the output of the flip-flop. This problem is called Race around condition. “’’ This condition also exists in T flip-flop since T flip-flop also has toggling options. 9.6 MASTER-SLAVE JK FLIP-FLOP • The master slave JK flip flop is a combination of a clocked JK flip-flop and a clocked SR flip-flop. The clocked JK flip-flop acts as the master and the clocked SR flip-flop acts as the slave. • Master is positive level triggered and due to the presence of an inverter in the clock line, the slave is negative level edge triggered. Hence when clock=1, the master is active and slave is inactive. Vice versa happens when clock=0.
• The following is truth table of master slave flip flop. Case Input Output Remark CLK J K Qn+1
n+1 I X 0 0 Qn
n No Change II (1) 0 0 Qn
n No Change III (1) 0 1 0 1 Reset IV (1) 1 0 1 0 Set v (1) 1 1
n Qn T o g g l e Fig 7 Truth table of Master slave jk FF munotes.in
Page 151
151 Operation: Case I: When clock is not given, both master and slave are inactive and there will be no change in outputs. Case II: For clock=1, master is active, slave inactive. As J=K=0, output of master Q and Q' will not change. As soon as clock goes to 0, slave becomes active, and master is inactive. But since input to slave S and R is same, output of slave will also remain same. Case III: For clock=1, master is active and slave is inactive. When J=0 and K=1, outputs of master will be Q=0, Q'=1, which w i l l b e i n p u t s t o slave. When clock=0, slave becomes active and takes i n p u t s 0 , 1 t o g i ve output Q=0, Q'=1. This output will not change if clock is again made 1and then 0. Hence we get a stable output from master and slave. Case IV: For clock=1, master is active and slave is inactive. When J=1 and K=0, outputs of master will be Q=1, Q'=0, which w i l l b e i n p u t s t o slave. When clock=0, slave becomes active and takes i n p u t s 1 , 0 t o g i ve output Q=1, Q'=0. This output will not change if clock is again made 1 and then 0. Hence we get a stable output from master and slave. Case V: When clock =1, J=K=1, master output will toggle. So S and R will invert. But slave remains inactive all this time since clock is 1. As soon as clock becomes 0, slave becomes active and master becomes inactive. So slave will also toggle. These changed outputs are returned through feedback to the master, but master does not r e s p o n d t o t h e m because clock is now 0 and master is inactive. Thus, in one clock period, master and slave both toggle only once, avoiding race condition caused by multiple toggling 9.7 T FLIP-FLOP We can construct a T flip – flop by any of the following methods (1) Connecting the output feedback to the input, in SR flip – flop. (2) Connecting the XOR of T input and Q PREVIOUS output to the Data input, in D flip – flop. (3) Wiring the J and K inputs together and connecting it to T input, in JK flip – flop. This is illustrated in the figures below munotes.in
Page 152
152
Figure (1) From SR flip flop
Figure (2) From D Flip flop
Figure (3) From JK Flip flop Working: Toggle Flip flop changes its output whenever it is edge-triggered. What it means is that whenever the clock changes its state from low to high or high to low. Truth Table of T flip – flop P r e v i o u s N e x t T QPrev Q `Prev QNext Q `Next 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 munotes.in
Page 153
153 The disadvantage of T flip flop is that the state of the flip-flop at an applied trigger is known only when read with the previous state. T flip flops are not available as Integrated Circuits(ICs). But, they can be easily constructed using SR flip-flop, JK flip-flop or D flip-flop as shown above. 9.8 CONVERSION OF FLIP-FLOP FROM ONE TYPE TO ANOTHER We have discussed four flip-flops-SR, D, JK and T flip-flops so far. It is possible to convert one flip-flop from one type to another very easily. The steps required for such conversion are: 1. Consider the truth table of the desired flip-flop. 2. Fill in the excitation values of the flip-flop in hand for each combination of present and next state. 3. Get a simplified expression for each input using Karnaugh Maps. 4. Draw the logic circuit diagram of the flip-flop t o b e f o r m e d according to the simplified expression. Use flip-flop in hand and logic gates to achieve this Let us understand this with an example. Let us consider converting SR flip- flop to a D flip flop. Step 1. Prepare truth table of desired flip flop, that is D flip flop. Input Present state Next state D Q (t) Q (t+1) 0 0 1 0 1 0 1 0 1 1 1 1 Step 2. SR flip-flop has two inputs S and R. Write the excitation values of SR flip flop for each combination of present state and next state. The above table will now be modified to Input Present state Next state SR flip-flop inputs D Q(t) Q(t+1) S R 0 0 1 0 X munotes.in
Page 154
154 0 1 0 0 1 1 0 1 1 0 1 1 1 X 0 Step 3. From the above table, we can write the Boolean functions for each input as below. S=m2+d3S=m2+d3 R=m1+d0R=m1+d0 We can use 2 variable K-Maps for getting simplified expressions for these inputs. The k-Maps for S & R are shown below
So, we got S = D & R = D' after simplifying Step 4. The circuit diagram of D flip-flop is shown in the following figure
This circuit contains a NOT gate connected in addition to SR flip-flop. Other conversions can be similarly worked out. 9.9 APPLICATIONS OF FLIP-FLOP Flip-flops are used in numerous applications, such as munotes.in
Page 155
155 (1) Registers (2) Counters (3) Event Detectors (4) Data Synchronizers (5) Frequency Divider 1) Registers: Registers are storage devices used to store memory. Each flip-flop can store a single bit. Figure 1 shows cascading three D flip-flops to store 3-bit information.
The data can be shifted within registers in/out of the register by applying clock pulses. These registers are called shift registers and can be pictorially represented as in Figure 2.
2) Counters: Counters are used for the purpose of counting. A series of flip –flops are cascaded to form counters. These counters can be synchronous or asynchronous. They can be positive-edge triggered or negative-edge triggered. Counters are used as up-counter, down counter, ring counter, munotes.in
Page 156
156 Johnson counter etc. Figure 3 shows a 3-bit asynchronous positive edge triggered up-counter.
3) Event Detectors: These are circuits which are used to find occurrence of a particular event. Flip-flops do not change their state unless triggered. This can be used to detect and store occurrence of an event. Figure 4a shows one such event detector which detects the event of switching ‘‘ON’’ of lig ht. The working is illustrated in Figure 4b.
4) Data Synchronizers: Outputs of a particular combinational circuit should change their states simultaneously. Using Data synchronizers, this can be easily achieved as illustrated in Figure 5 below munotes.in
Page 157
157
5) Frequency Divider: Consider a positive edge triggered JK flip-flop as shown in Figure 6 below
The output of JK flip-flop will toggle for each positive-edge of the clock. It is clearly seen from the waveforms that if Tin is the input clock period, then Tout= 2Tin. In other words, fout=fin/2. This is how frequency division takes place using flip-flops. ***** munotes.in
Page 158
158 Unit 5 10 COUNTERS Unit Structure 10.0 Objectives 10.1 Introduction 10.2 Asynchronous counter 10.3 Terms related to counters 10.4 IC 7493 (4-bit binary counter) 10.5 Synchronous counter 10.6 Bushing 10.7 Type T Design 10.8 Type JK Design 10.9 Presettable counter 10.10 IC 7490 10.11 IC 7492 10.12 Synchronous counter ICs 10.13 Analysis of counter circuits 10.14 Summary 10.15 Reference for further reading 10.0 OBJECTIVES This chapter would make you understand the following concepts What is counter? Different types of counters – Asynchronous and synchronous counter. Terms related to counters. IC 7493 (4-bit binary counter) Synchronous counter, Bushing, Type T Design, Type JK Design. Presettable counter, IC 7490, IC 7492. Synchronous counter ICs, Analysis of counter circuits. munotes.in
Page 159
159 10.1 INTRODUCTION In the design of counters and registers FFs (flip-flops) are most widely used. The FF is the basic building block of any sequential logic system. FF and combinational circuit are used in the design of any sequential system. Counter is a sequential circuit. A counter is a device that stores the number of times a particular event or process has occurred, often in relationship to CLK (a clock) pulse. Counters are used in digital electronics for counting purpose, they can count specific event happening in the circuit. 10.1.1 Definition: A digital circuit which is used for counting pulses i s k n o w n counter. Counter is the widest application of FFs. It is a group of FFs with a CLK pulse applied. Counter is a register that goes through a prescribed series of states. Counter is a circuit which cycle through state sequence. 10.1.2 Types of Counters: A digital circuit which is used for counting pulses i s k n o w n counter. Counter is the widest application of FFs. It is a group of FFs with a CLK pulse applied. Counter is a register that goes through a prescribed series of states. Counter is a circuit which cycle through state sequence. 10.1.3 Types of Counters: The number of FFs used and the way in which they are connected determines the number of states and also the specific sequence of states that the counter goes through during each complete cycle. Counters are classified according to the way they are clocked: Asynchronous or ripple counters and Synchronous counters Asynchronous counter Synchronous counter 1. It is also called as serial counter. 2. Simple and straight forward in operation. 3. Slower than synchronous. 4. Next FF is triggered by previous FF. 5. Problem of glitch. 6. Settling time is more. 1. It is also called as parallel counter. 2. Complex in operation as compared to asynchronous. 3. Faster than asynchronous. 4. All FFs are triggered simultaneously by external CLK. 5. No problem of glitch. 6. Settling time is less. munotes.in
Page 160
160 Synchronous / asynchronous counter can be further divided in to following sub-type: 1. Regular Counter: FFs are used to build the regular counter, in which the number of FFs determines the number of states means there is direct relation between number of FFs used and number of states of counter. Suppose ‘N’ is number of States in counter and ‘m’ is number of FFs then the relation is N (number of States) = 2 m (# of FFs) Let’s say m (# of FFs) = 3 then N = 2m = 23 = 8 ∴ Number of States (N) in counter = 8 Consider one additional variable ‘n’, which indicates the number of actual states of counter. In regular counter, number of actual states of counter (n) and number of states of counter (N) are equal i.e. n = N. 2. Truncated counter: i n t h i s c o u n t e r , n u m b e r o f a c t u a l s t a t e s o f counter (n) are always less than number of states of counter (N) i.e. n < N. If FFs are 3, then N = 2m = 8 but n < 8. 3. S e q u e n t i a l C o u n t e r : in this counter, states of counter are sequential i.e. 0, 1, 2, 3, 4, 5, 6, … so on. 4. Non-sequential Counter: in this counter, states of counter are not sequential means states are irregular. e.g. 0, 3, 9, 8, 2, 1, 7. 10.2 ASYNCHRONOUS OR RIPPLE COUNTERS Asynchronous counter is a cascaded arrangement of FFs where the output of one FF drives the CLK input of the following FF. The number of FFs in the cascaded arrangement depends upon the number of different logic states that it goes through before it repeats the sequence, a parameter known as the modulus of the counter. Asynchronous counter, also called ripple counter or a s e r i a l counter, the CLK input is applied only to the first FF, also called the input FF, in the cascaded arrangement. The CLK input to any subsequent FF comes from the output of its immediately preceding FF. For instance, the output of the first FF acts as the CLK input to the second FF, the output of the second FF feeds the CLK input of the third FF and so on. In general, in an arrangement of ‘n’ FFs, the CLK input to the nth FF comes from the output of the (n−1)th FF for n>1. munotes.in
Page 161
161 Figure 10.2 shows the generalized block diagram of an n-bit binary ripple counter. As a natural consequence of this, not all FFs change state at the same time. The second FF can change state only after the output of the first FF has changed its state. That is, the second FF would change state a certain time delay after the occurrence of the input CLK pulse owing to the fact that it gets its own CLK input from the output of the first FF and not from the input CLK. This time delay here equals t h e s u m o f propagation delays of two FFs, the first and the second FFs. In general, the nth FF will change state only after a delay equal to n times the propagation delay of one FF. The term ‘ripple counter’ comes from the mode in which the CLK information ripples through the counter. It i s a l s o c a l l e d a n ‘asynchronous counter’ as different FFs comprising the counter do not change state in synchronization with the input CLK. In a counter like this, after the occurrence of each CLK input pulse, the counter has to wait for a time period equal to the sum of propagation delays of all FFs before the next CLK pulse can be applied. The propagation delay of each FF, of course, will depend upon the logic family to which it belongs.
Figure 10.2: Block diagram of an n-bit binary ripple counter 10.2.3 Bit Ripple Counter: A binary ripple counter can be constructed using clocked JK FFs. Figure 10.2.1(a) shows three negative edge – triggered, JK FFs connected in cascade. The system clock, a square wave, drives FF A. The output of A drives FF B, and the output of B drives FF C. All the J and K inputs are tied to +VCC. This means that each FF will change state (toggle) with a negative transition at its clock input. When the output of a FF is used as the clock input for the next FF, we call the counter a ripple counter, or asynchronous counter. The A FF must change state before it can trigger the B FF, and the B FF has to change state before it can trigger the C FF. The triggers move through the FFs like a ripple in water. Because of this, the overall propagation delay time is the sum of the individual delays. For instance, if each FF in this three- FF counter has a propagation delay time of 10 ns, the overall propagation delay time for the counter is 30 ns. munotes.in
Page 162
162
Figure 10.2.1: 3 - bit Ripple Counter The waveforms given in Fig. 10.2.1(b) show the action of the counter as the clock runs. Let's assume that the FFs are all initially reset to produce 0 outputs. If we consider A to be the least-significant bit (LSB) and C the most-significant bit (MSB), we can say the contents of the counter is CBA = 000. Every time there is a clock NT (Negative Transition), FF A will change state. This is indicated by the small arrows (↓) on the time line. Thus at point a on the time line, A goes high, at point b it goes back low, at c it goes back high, and so on. Notice that the waveform at the output of FF A is one-half the clock frequency. Since A acts as the clock for B, each time the waveform at A goes low, FF B will toggle. Thus at point b on the time line, B goes high; it then goes low at point d and toggles back high again at point f Notice that the waveform at the output of FF B is one-half the frequency of A and one-fourth the clock frequency. Since B acts as the clock for C, each time the waveform at B goes low, FF C will toggle. Thus C goes high at point d on the time line and goes back low again at point h. The frequency of the waveform at C is one-half that at B, but it is only one-eighth the clock frequency. munotes.in
Page 163
163 10.3 TERMS RELATED TO COUNTERS Before we proceed further, we would like to study few things related to counter. 10.3.1 State Diagram: State diagram means graphical representation of the s t a t e s o f counter circuit. For example state diagram for 3 bit binary ripple up counter and 3 bit binary ripple down counter can be as shown in Figures 10.3.1(a) and 10.3.1(b) respectively.
Figure 10.3.1(a): 3 bit binary ripple up counter Figure 10.3.1(b): 3 bit binary ripple down Counter 10.3.2 Module N Counter: If it is desired to have modulo N (mod – N) counter, the number of FFs required is determined by, N ≤ 2m where m = number of FFs Let say m = 4, therefore N = 16. But if we require only 10 states out of 16, it is called as modulus – 10 (Mod – 10) counter, but required FFs will be 4 only. Mod – N can be achieved by resetting the FF. This should be done at the N state. In Mod – 10, counter will count from 0 to 9, and at 10th state it will reset back to 0. Mod – 10 counter is also called as decade counter. Up till now we have seen that counter is sequential and number of states provided are N = 2m. Now let us take a case of truncated ripple counter when n (number of actual state) < N. Example 1: Design mod – 3 ripple counter munotes.in
Page 164
164 Solution: 1) State diagram = 3 states → 0 to 2 2) No of actual states are n = 3 n < N = 2m 3 ≤ 2m therefore m = 2 Hence 2 FFs are required. 3) Here FF used should have clear terminal for resetting or clearing. 4) Assumption: considering FF and gates are having 0 propagation delay. 5) Reset logic circuit required to terminate count after 2. 6) 2 FFs are used therefore N = 4
Figure 10.3.2.1(a): state diagram QB QA 0 0 0 0 1 1 1 0 2 1 1 3 Normally CLR terminal is ACTIVE LOW therefore Design a reset logic combinational circuit such that output Y should be 1 when valid states are there and Y = 0 when Invalid states are present.
Valid States Invalid State so whenever this state occurs countershould beCLEARED(Reset) munotes.in
Page 165
165 Circuit Diagram:
Figure 10.3.2.1(b): mod – 3 ripple counter: circuit diagram Counter is up counter, therefore FF should be –ve edge triggered, cascade Q O/P and final O/P is taken from Q. The final circuit diagram is therefore shown in figure 10.3.2.1(b). Wave form for the same is shown in following figure 10.3.2.1(c).
Figure 10.3.2.1(c): mod – 3 ripple counter: wave form Working: to check the working refer the figures 10.3.2.1(b) and 10.3.2.1(c) (QB QA = B A) 1) Initially all FFs are cleared. ∴ BA = 00; ∴ Y = 1 2) When 1st negative CLK edge hits, A toggles ∴ A = 1, ∴ BA = 01; Y = 1 3) At 2nd hit of CLK edge, A toggles from 1 → 0 (negative edge), ∴ B also toggles from 0 → 1. ∴ BA = 10 ∴ Y = 1 munotes.in
Page 166
166 4) When 3rd CLK edge hits, A will toggle from 0 → 1(positive edge) ∴ B = u n c h a n g e d ∴ BA = 11 ∴ Y = 0 . A s Y = 0 , a l l F F s w i l l b e c l e a r e d . a n d B A = 0 0 . A s B A = 0 0 , Y = 1 a g a i n . The sequence from BA = 11 to BA = 00, is so fast (as propagation delay is considered 0 ᶯ sec) that, it is not possible to observe 11 condition of waveform. Y waveform pulse is also very sharp and of very, very small duration. Thus counter will run 0 → 1 → 2 → 0. Example 2: Design mod – 6 ripple counter Solution: 1) State diagram = 6 states → 0 to 5
Figure 10.3.2.2(a): state diagram 2) No. of states = 6 therefore n < N = 2m 6 < 2m therefore m = 3 3) Design of reset circuit. Truth table is, N = 2m = 23 = 8, but n = 6 Truth Table:
munotes.in
Page 167
167 K-map:
Points: 1) Counter is up counter, therefore we have to cascade Q output, -ve edge triggered FF and final output from Q. 2) FF should have ACTIVE LOW reset (clear) terminal. 3) Propagation delay presently assumed 0 n sec. Circuit diagram:
Figure 10.3.2.2(b): mod – 6 ripple counter - circuit diagram
Figure 10.3.2.2(c): mod – 6 ripple counter - wave form munotes.in
Page 168
168 10.3.3 Problems involved in Ripple Counter: Mainly there are two problems involved in ripple counter. 1) Glitch operation – propagation delay of Reset logic. 2) Propagation delay – propagation delay of FF Glitch operation: In example 1 assumption was made that propagation delay through FF and reset circuit is 0 ᶯ sec. But practically this situation does not exist, therefore glitch operation occurs. Let’s consider propagation delay of reset logic. For analysis let‘s consider example 1 in which states are 0, 1, 2. Redraw the waveforms considering propagation delay of reset CLK.
Figure 10.3.3(a): mod – 3 ripple counter - wave form Working: Refer Figure 12.3.3(a) and example 1 (QA = A QB = B) 1) Initially all FFs are reset ∴ BA = 00 ∴ Y = 1 2) When 1st CLK edge hits, A will toggle ∴ BA = 01, ∴ Y = 1 3) At 2nd CLK edge, A will toggle from 1 → 0 (negative edge), B also toggles. ∴ BA = 10. ∴Y = 1 4) When 3rd CLK edge hits, A will toggle from 0 → 1 (positive edge), ∴B is unchanged. ∴ BA = 11 Reset circuit is designed in such a way that, when 11 occurs Y = 0. But appearing of logic 11 at NAND input, getting settled, then propagates through NAND and appear at output, then resetting the FF will take some time in ᶯ sec. During this period BA = 11. This condition is invalid condition and as in Figure 10.3.3(a), QA produces unwanted short duration pulse called glitch. munotes.in
Page 169
169 Propagation Delay in Ripple counter: Basic principle of operation of a synchronous counter is, each FF is triggered by the transition at the output of preceding FF. Each FF has internal propagation delay, means second FF will not respond unless and until propagation delay time, after the first FF receives an active clock transition. ∴ T h i r d F F w i l l n o t r e s p o n d u n t i l a t i m e e q u a l t o t wice propagation delay (2 x tpd) after that clock transition. Thus propagation delay of FF accumulates so that Nth cannot change state unless and until, time equals to N x tpd after the CLK transition occurs. To understand this refers waveforms in following figure 10.3.3(b).
Figure 10.3.3(b): mod – 3 ripple counter: wave form Refer figure 12.3.3(b), (QA = A, QB = B) propagation delay of one FF = 10 ᶯ sec. 1) Initially both output BA = 00 2) When the first CLK edge hits, A changes from 0 → 1. As shown QA changes states 10 ᶯ sec after CLK edge hits. (Part (a)). 3) In Second CLK edge QA changes from 1 → 0. Transition occurs, 10 ᶯ sec after CLK edge hits. QA provides negative transition (1 → 0) to B FF. ∴ QB changes the state from 0 → 1, 10 ᶯ sec after the transition of QA. ∴ With respect to CLK edge QB changes state after 20 ᶯ sec. (Part (b)). i.e. 2 FF x 10 ᶯ sec = 20 ᶯ sec This propagation delay causes limitation on CLK frequency input, so for ripple counter, following equation provides relationship between CLK period, number of FFs used and propagation delay of FF. munotes.in
Page 170
170 Time period of CLK (TCLK) ≥ N x tpd Where, tpd= propagation delay N = No. of FFs max11pdfCLK Nt∴= = 10.3.4 Power on Reset Circuit: Whenever counter working was discussed, it was assumed that initially everything is reset. Whenever power supply is switched ON; one cannot predict the output state of FF. Therefore clear terminal is provided. But clear terminal requires some external circuitry to force it self ‘LOW’ so that it can provide Q = 0 (some known state). This external circuitry is nothing but power ON reset circuit. Refer following figure 10.3.4.
Figure 10.3.4: mod – 3 counter with power ON Reset circuit As shown in figure 10.3.4 (counter states are 0, 1, 2). In addition one RC n/w with AND gate is used. So either of the input is LOW output of AND gate is LOW, FFs will be cleared
figure 10.3.4(a) figure 10.3.4(b). munotes.in
Page 171
171 Working: Refer figure 10.3.4(a) and 10.3.4(b). When power supply is switched ON, VCC w i l l a p p e a r a c r o s s R C n/w at time t0. ∴ C a p a c i t o r w i l l s t a r t c h a r g i n g . T h e c h a r g i n g s l o p e depends upon RC time constant. When capacitor voltage (Voutput) reaches to level VTH ( T h r e s h o l d v o l t a g e) , c h i p (I C) w i l l c o n s i d e r i t HIGH logic. Below threshold it is considered as LOW logic. ∴ For duration t1 – t0 output of AND gate is ‘0’∴ FFs are cleared. When counter steps through states and AB = 11, output of NAND is equal to 0. ().0CLEAR CLK∴=as AND output is ‘0’ ∴FF will reset. 10.4 IC 7493 (4-BIT BINARY COUNTER) Let’s study TTC MSI circuit of 4 bit ripple counter i m p l e m e n t e d i n I C 7493.
Figure 10.4.1: IC 7493 munotes.in
Page 172
172 In IC 7493, QD QC QB QA → Binary output of FF. Input A → CLK IN of FFA Input B → CLK IN of FFB R0 (1), R0 (2) → Reset pin When R0 (1) = R0 (2) = 1 Reset will occur Figure 10.4.1 shows logic diagram of IC 7493, It shows that FFA is independent i.e. output is not cascaded to next FF, But FF B, C and D are cascaded. Therefore we have individual, internally two counters, ÷2 (Mod 2) and ÷ 8 (Mod 8). If we combine both counters we get 2 x 8 = 16 state counter of mod 16 counter or ÷ 16 counter. When we connect QA output to input B and CLK IN given to Input A only, it becomes simple 4 bit binary ripple counter. Truth table is as follows R01/02 CLK QD QC QB QA 1 X 0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 Example 3: Implement ÷ 9 counter using IC 7493. Solution: Procedure is same as when we design mod – N ripple counter. 1) ÷ 9 means mod - 9, ∴ required states are 9 (0 to 8) ∴ FF used are 4. munotes.in
Page 173
173 2) Reset circuit should generate ‘0’ output for valid states (0 to 8) and ‘1’ output for invalid states (9 to 15), because if R0 (1) and R0 (2) both are 1, then only IC 7493 resets. 3) Design reset circuit, Draw K-map.
4) Circuit diagram:
Figure 10.4.2: mod - 9 counter using IC 7493 - circuit diagram munotes.in
Page 174
174 10.5 SYNCHRONOUS COUNTERS In asynchronous counter mainly two problems were present, glitch and delay in counter. To avoid this, synchronous counter came into picture. Synchronous counter is now most widely used. Generalized block diagram of synchronous counter shown in figure 10.5
Figure 10.5: Generalized block diagram of synchronous counter Observation from block diagram of Synchronous counter 1) CLK pin of all FFs are tied together, so that FF changes output in synchronism. 2) O/p Q given to combinational logic circuit. This circuit is designed in such a way that GA GB GC generated from it, applies proper logic to input of FF, so that we get correct next state. 3) O/p Q depends upon previous input of FF, when CLK edge hits. Presently in block diagram, JK is tied together. But this will not be the case every time. JK can be controlled separately by combinational circuit. 10.6 BUSHING If you observe examples solved up till now, in full sequence ‘0’ is always present and once counter enters in valid state, it will continue the chain unless and until power supply is switched off. To enter in the chain we use power on reset circuit, therefore first state is normally ‘0’. Problem: 1) In some of the applications we don’t require ‘0’ state at all. 2) Secondly due to power supply fluctuation (glitch of power supply), Electromagnetic inference and RFI (radio frequency interference), it may happen that counter will enter in invalid state. munotes.in
Page 175
175 If due to problem stated above it enters in to invalid condition then what will happen? Then here your luck factor counts 1. Lock Out State (If Luck Is Bad): It may happen that counter will lock itself in invalid states only. Let’s say in above case counter enters into state 1; because of logic circuit next state happens to be 6. After 6 next state happens to be 1. Then counter will toggle between two states only, as shown in state diagram figure 10.6(a).
Figure 10.6(a): State diagram (2) If you are lucky enough after entering into invalid state it may switch over to valid state. But don’t try to check your luck. Take precaution. As a precautionary step we implement bushing to state diagram. Bushing means branches. We are going to branch invalid state in such a way that even though it enters into invalid state a f t e r o n e , t w o o r three CLK ticks it will enter into valid state chain. Following are some of the examples for implementing bushing in Example 5
Figure 10.6 (b-e): Implementation of Bushing munotes.in
Page 176
176 Thus one can have ‘n’ number of combinations. Choice depends upon designer 10.7 TYPE T DESIGN Let’s start designing synchronous counter using T FF. Example 4: Design mod – 4 regular sequential synchronous up counter by using T FF. Solution: 1. No. of states are 4, for mod – 4 counter. 2. Regular means n = N. 3. No. of FF required will be 4 ≤ 2m ∴ m = 2 4. Sequential and up means 0, 1, 2, 3. 5. ∴ State design is Figure 10.7(a). 6. FF A and B are used. GA and GB are output from combinational circuit to provide input to T FF. ∴ C i r c u i t w i l l b e a s s h o w n i n Figure 10.7(b). 7. Design of combinational circuit to generate GA, GB
Figure 10.7(a): State diagram
Figure 10.7(b): Circuit diagram Step 1: For generation of truth table, depending upon number of bits (FF), write down sequentially all states. In our case 2 bits (FF) are used, ∴ state are 4. munotes.in
Page 177
177 A 0 0 1 1 ; A=MSB B 0 1 0 1 ; B = LSB decimal 0 1 2 3 Here QA = A, QB = B for simplicity Step 2: Now below this you write down required output. A 0 0 1 1 B 0 1 0 1 ( P r e v ) ( N e x t ) GA GB Step 3: Now start from state of counter. Treat this state as previous state. Take next state of counter from state diagram, and it will be obviously next state. In our case 1st state = AB = 00 → Previous state. 2nd state = AB = 01→ Next state. Step 4: Now refer excitation table of T FF, treat change of state for A and B individually and write down GA and GB the step is explained as follows: A B 0 0 0 1 0 0 1 0 1 1 GA GB 0 1 As A changes from 0 → 0 ∴ GA (TA) = 0 B changes from 0 → 1 ∴ GB (TB) = 1 Step 5: Now treat previously next as previous state. i.e. AB = 01 which was next state previously, will be Now previous state. Refer state diagram and find next state. In our case it will be AB = 10. Again the procedure is same as STEP 4. A B 0 0 0 1 [Prev.) 1 0 [Next] 1 1 munotes.in
Page 178
178 GA GB 0 1 1 1 As A changes from 0 → 1, ∴ GA (TA) = 1 B changes from 1 → 0, ∴ GB (TB) = 1 Step 6: Now previous state = AB = 10 and Next state = AB = 11, again follow STEP4 A B 0 0 0 1 1 0 [Prev.] 1 1 [Next] GA GB 0 1 1 1 0 1 As A changes from 1 → 1, ∴ GA (TA) = 0 B changes from 0 → 1, ∴ GB (TB) = 1 Step 7: Finally previous state = 11 and next state = 00. Next we are completing full chain of counter. Follow step 4. A B 0 0 [Next] 0 1 1 0 1 1 [Prev.] GA GB 0 1 1 1 0 1 As A changes from 1→ 0, ∴ GA (TA) = 1 B changes from 1→ 0, ∴ GB (TB) = 1 Step 8: After filling truth table, next step is to draw K-Map munotes.in
Page 179
179
Step 9: Draw final circuit diagram. Already we have drawn half circuit as shown in Figure 10.7(b). Only this is to replace combinational block by directly some connection.
Figure 10.7(c): Final circuit diagram Let us draw the waveforms and analyze the working of the circuit
Figure 10.7(d): Waveforms Working: 1. Initially counter is Reset, ∴ AB = 00 2. At 1st CLK edge, TA = 0 as B = 0, TB = 1. ∴A remains constant as QB toggles from 0 → 1. ∴ AB = 01 3. At 2nd CLK edge, as TA = 1 (because B = 1) TB = 1, ∴A and B both will toggle, giving ∴ AB = 10 4. At 3rd CLK edge, TA = 0 as B = 0 and TA = 1, ∴ A = unchanged, B = toggle ∴ AB = 11 munotes.in
Page 180
180 5. Finally at 4th CLK edge TA = 1 and B = 1, TB = 1 ∴ A and B will toggle from 1 → 0 ∴ AB = 00 Now the point 2, 3, 4 and 5 will continue till CLK is present, and counter generates required states. If you compare the waveform in Figure 10.7(d) with waveforms of ripple counter. You will find that falling edge is shown only on CLK, not on QA or QB output, because CLK is synchronized. Counter changes state ONLY when CLK edge hits. Example 5: Design synchronous, non-sequential counter Solution:
Figure 10.7.1: State diagram 1. Counter is non sequential as well as truncated. 2. While designing non sequential counter, instead of number of state you should consider maximum count of the state. In our case maximum count of the state is 7. To represent 7 in binary we require 3 bits (111) and therefore m = 3. As m = 3, n = 23 = 8 3. While writing truth table as told in Example – 4 step 1, depending upon number of bits (FF), write down states sequentially. In our case N = 8 as m = 3. So we are supposed to write 0 to 7 sequentially, refer Figure 10.7.1(a) Truth table 4. Truth table.
Figure 10.7.1(a): Truth table munotes.in
Page 181
181 5. K – map:
6. Circuit diagram:
Figure 10.7.1(b): Circuit diagram Step 1: Write standard table A, B, C and GA, GB, GC. Step 2: Write 0 – 7 states sequentially under A, B, C. Step 3: Write down X (don’t care) for invalid states. For our case invalid states are 1, 2, 4, 6, ∴ for 1, 2, 6, GA, GB, and GC are X (don’t care). Step 4: Now the steps are standard. Start from 1st state of s t a t e diagram i.e. 0. Next state is 7. So the transition is shown in Figure 12.7.1(a) by (a). Previous state of ABC = 000, Next state of ABC = 111. ∴ GA, GB, and GC = 111, written under column '0 – 7' (shown in Figure 10.7.1(a)). Step 5: 2nd transition is from 7 – 5 (shown by arrow (b)). ABC changes from 111 to 101 ∴ GA = 0, GB = 1 and GC = 0. Written under column '7 – 5'. munotes.in
Page 182
182 Step 6: 3rd t r a n s i t i o n i s f r o m ‘ 5 – 3 ’ ( s h o w n b y a r r o w ( c ) ) A BC changes from 101 to 011 ∴ GA = 1 , GB = 1 a n d GC = 0 , written under column ‘5 – 3’. Step 7: Final transition is from 3 to 0 (3 – 0) shown by arrow (d). ABC changes from 011 to 000 ∴ GA = 0, GB = 1 and GC = 1, written under column ‘3 – 0’ Step 8: After going through one full cycle draw K – map. Example 6: Design synchronous counter for state diagram shown in figure 10.7.2
Figure 10.7.2: state diagram Solution: 1. Counter is sequence but truncated. 2. Number of states n = 6. ∴ n = 6 ≤ 2m , ∴ m = 3 As m = 3, 23 = 8 = N ∴ n < N (truncated counter) 3. Up counter (observe from given state diagram) 4. Truth table for designing combinational logic circuit.
Figure 10.7.2(a): Truth table As shown in Figure 10.7.2(a) truth table, valid states are only 0, 1, 2, 3, 4 and 5. Therefore, for invalid states i.e. 6 and 7, GA, GB and GC are takes don’t care conditions because we know that these states are not going to occur. munotes.in
Page 183
183 5. K – Map for GA, GB and GC:
6. Circuit diagram:
Figure 10.7.2(b): Circuit diagram 7. Waveforms:
Figure 10.7.2(c): Waveforms. munotes.in
Page 184
184 10.8 TYPE JK DESIGN Counter design using JK-FF is most widely used. Here J and K terminals are controlled separately. We have already generated excitation table for JK-FF. As far as counter design goes, method is same as we followed up till now. Figure 10.8 shows generalized block diagram for counter using JK.
Figure 10.8: Generalized block diagram As shown in Figure 10.8 1. CLK IN of all FFs is tied together. (synchronous counter) 2. QA, QB, QC output are fed to combinational circuit. 3. Depending upon next state combinational circuit g e n e r a t e s p r o p e r J and K input for A, B and C FF. Example 7: Design a modulo – 6 counter using JK FF. Explain its action by writing a truth table and draw waveforms for the o u t p u t s o f t h e f l i p flops. Solution: 1. State diagram, modulo 6 mean 0 to 5.
Figure 10.8.1(a): State diagram 2. Number of FFs required will be 3. ∴ N=2m = 23 = 8. munotes.in
Page 185
185 3. Truth table
4. K-Map:
munotes.in
Page 186
186 5. Circuit Diagram:
Figure 10.8.1(b): Circuit diagram 6. Waveforms:
Figure 10.8.1(c): Waveforms Example 8: Implement synchronous counter using JK FF. for the state diagram shown in Figure 10.8.2
Figure 10.8.2: State diagram Solution: 1. Counter is with bushing 2. Number of FFs required will be 2. munotes.in
Page 187
187 3. Truth table:
4. K – Map:
5. Circuit diagram:
Figure 10.8.2(a): Circuit diagram 10.9 PRESETTABLE COUNTER As we have discussed previously that sometime counter will not start from ‘0’ state. It will start from some predefined state. Let’s say we want to down count from decimal 10. So preset counter to start 10, apply CLK pulses, so it will count down to 9, 8, 7, ... to 0. After that it will again start from 10. munotes.in
Page 188
188 Counters can be preset to any desired starting count either synchronously or asynchronously. This can be done using PRESET and CLEAR terminals of FF Figure 10.9 shows 3 bit parallel presettable up counter. 1. Counter is synchronous. 2. Asynchronous inputs, preset and clear, are controlled through load signal. 3. Steps for 'Preset', (a) Apply required count (step) to P2, P1, P0. Let's say P2, P1, P0 = 101 (b) Apply 'LOW' going signal to 'LOAD' pin (c) ∴ Output of NAND1, NAND3 = 0 and NAND2 = 1 at the s a m e t i m e NAND4, N A N D 6 = 1 and NAND5 = 0. ∴ FF B will be reset and AC will be preset ∴ ABC = 101. d) CLK is not going to affect above action. 4. After presenting applies CLK pulse so that counter can start next count.
Figure 10.9:3 bit parallel presettable up counter 10.10 IC 7490 IC 7490 is TT1 MSI decade counter. It contains four M/S FF and additional gating to provide divide by 2 counter (Mod-2) and three stage binary counter which provides divide by 5 counter (Mod-5). Figure 10.10 shows block diagram of IC 7490. munotes.in
Page 189
189
Figure 10.10: Block diagram of IC 7490 7490 have gated zero reset (R0(1), R0(2)) and gated set to nine inputs R9(1), R9(2) for use in BCD nine's complement applications
Figure 10.10(a): Pin Configuration - IC 7490
Figure 10.10(b): Truth table - IC 7490 As shown in truth table when R0 (1) = R0 (2) = 1, IC 7490 Reset. When R9 (1) = R9 (2) = IC 7490 sets to 1001 (9 decimal). So one has to provide logic 1 to these input temporarily, set / reset it, and lower the input terminals so IC 7490 can start counting as CLK pulses applied to munotes.in
Page 190
190 Example 9: Implement sequential decade counter using IC 7490 and write counter states Solution: In IC 7490 mod-2 counter and mod-5 counter is available ∴ 2 x 5 = 10 ∴ gives decade counter. As mentioned in above example, requirement is sequential decade counter. ∴ Apply CLK IN to INPUT A pin. Output QA is connected to INPUT B i.e. input of mod-5 counter. Output terminals are QD Qc QB QA, where QD = MSB, QB = LSB connections are shown in Figure 10.10.1(a).
Figure 10.10.1(a): Sequential decade counter Important point to be remembered is, now at each falling edge of QA O/P, mod 5 counter will increment. And QA change at falling edge of CLK input. The count sequence can be written as,
Figure 10.10.1(b): Count Sequence of Sequential decade counter munotes.in
Page 191
191 If you observe Figure 10.10.1(b), concentrate on QD, QB, Qc and QA separately initially QD, Qc, QB = 000. When QA changed from 1 → QD, Qc, QB changed to 001. For 2nd CLK period state of QD, Qc, QB remains unchanged. 10.11 IC 7492 IC 7492 is TTL, MSI divide by 12 counter. IC 7492 is having 2 counter inside it. mod 2 (÷ 2) and mod 6 (÷ 6) counter. ∴ Combination of both gives 2 x 6 = 12 ∴ ÷ 12 counter. Block diagram of IC 7492:
Figure 10.11: Block diagram of IC 7492 Figure 10.11 shows block diagram of IC 7492. For mod 6 counter IC 7492 counts from 0, I, 2, 4, 5, 6, 0. (Observe sequence carefully, state 3 is absent).
Figure 10.11(a): Pin diagram of IC 7492 Example 10: (a) Write down truth table for Mod 6 counter in IC 7492. (b) Write down truth table for Mod 12 counter in IC 7492, if CLK IN is given to Input A and Input B QA is shorted. munotes.in
Page 192
192 Solution: (a) Truth table of IC 7492 for mod 6 counter. As we know that internally IC has mod 2 and mod 6 counter. So use only mod 6 counter. CLK IN gives to Input B and outputs are QD QC QB only. States are as shown in Figure 10.10.1(a).
Figure 10.11.1(a): Truth table – IC 7492 mod 6 counter (b) In this part, (i) Give CLK IN to Input A (ii) Conned Input B to QA. ∴ Circuit will be as shown in Figure 10.11.1(b)
Figure 10.10.1(b): Circuit diagram - IC 7492 mod 6 counter Point to be remembered. (1) QA toggles at each falling edge of CLK IN. (2) QB QC QD will change state at each falling edge of QA. Working: Refer Figure 10.11.1(a) (1) Initially QD QC QB QA (DCBA) = 0000 (2) At first CLK edge, a changes from 0 → 1 (rising edge.) ∴ = 000 ∴ DCBA = 0001. munotes.in
Page 193
193 (3) At 2nd CLK edge, A. toggles from 1 → 0 (falling edge.) ∴ DCB will change from 000 to 001. (From Figure 10.10.1(a)) DCBA = 0010. (4) 3rd C L K e d g e , A changes from 0 → 1 (rising edge), ∴ DCBA = 0010. (5) 4 th CLK edge, A changes from 1 → 0 (falling edge). ∴ DCB changes from 001 to 010 ∴ DCBA = 0100. (6) At 5 th CLK edge, A changes from 0 → 1 (rising edge), ∴ DCB = unchanged∴. DCBA = 0101. (7) At 6 th CLK edge, A changes from 1 → 0 (falling edge), ∴ DCB changes from 010 to 100 (Decimal count 011 is not present in mod 6 refer Figure 10.11.1(a) ∴ DCBA = 1000 (8) At 7 th CLK edge, A changes from 0 → 1, ∴ DCB = unchanged. ∴DCBA = 1001. (9) At 8th CLK edge, A changes from 1 → 0, ∴ DCB changes from 100 to 101. ∴ DCBA = 1010 (10) At 9 t h C L K e d g e , A c h a n g e s f r o m 0 → 1, ∴ DCB unchanged, ∴DCBA = 1011. (11) At 10th CLK edge, A changes from 1 → 0, ∴ DCB changes from 101 to 110 ∴ DCBA = 110 (12) Finally at 11 th CLK edge, A changes from 0 → 1, ∴ DCB unchanged, DCBA = 1101. Truth table is written as follows CLK edge QD QC QD QA DECIMAL EQUIVALENT 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 munotes.in
Page 194
194 10 1 0 1 0 10 11 12 13 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 0 0 0 0 0 Figure 10.11.1(c): Truth table - IC 7492 mod 12 counter 10.12 SYNCHRONOUS COUNTER ICS Let's study some synchronous counter ICs IC 74190: IC 74190 is UP/DOWN decade counter with preset and ripple clock. It is a reversible BCD (8421) decade counter featuring synchronous counting and asynchronous presetting. Reversible BCD means it can count 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 i.e. up and 9, 8, 7, 6, 5, 4, 3, 2, 1, 0. 9 i.e. down. Asynchronous presetting means parallel input data can be loaded at any instant, it is not dependent upon CLK input. Pin configuration and logic symbol is as shown in Figure 10.12 (a) & (b)
Figure 10.12: Pin configuration and logic symbol – IC 74190 Let us see the Pin names and functions NAMES DESCRIPTION
Count enable input (Active low)
Clock pulse input (Active rising edge)
Parallel data input
Asynchronous parallel load input (Active low) munotes.in
Page 195
195
Up / Down count control input 0 – up count 1 – down count
Flip Flop outputs
Ripple clock output (Active low)
Terminal count output (Active HIGH) Basically 74190 is decade counter. Internally four JK FFs are used, output is 4 bit Q0 – Q3. It may happen because of supply fluctuation or noise it may enter in invalid state i.e. 10 – 15, then how 74190 behaves? This point can be explained by using state diagram. Refer figure 10.12(c) 1) When counter counts up (Shown by dark line Main loop is → …. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 … Bushing branches are (1) 14, 15, 2 (2) 12, 13, 4 (3) 10, 11, 6 Where 2, 4 and 6 are valid states. Worst case counter will take maximum three CLK Cycle to enter in main loop. 2) When counter counts down (shown by dotted line): Main loop is → …. 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9 … Bushing branch is → 15, 14, 13, 12, 11, 9. Here we have only one branch. In worst case situation counter will take maximum 7 CLK cycles to enter valid states.
Figure 10.12(c): State diagram munotes.in
Page 196
196 Different Modes of 74190: 74190 has different modes of operation. Modes are selected by ,, /PL CE U D Model Select Table Inputs Mode PL CE UD C/P 1 0 0 Count Up 1 0 1 Count Down 0 X X X Preset(Async.) 1 1 X X NC (Hold) We will study all these modes step by step. COUNT UP:
Figure 10.12(d): UP Counter using IC 74190 For counter counting up one has to tie 1PL= and CE U D== 0. Apply clock pulse and counter counts up. The circuit is as shown in figure 10.12(d) munotes.in
Page 197
197 COUNT DOWN: For counter counting down tie 1ccPL V==and 1, 0 ,ccUD V C E== =apply clock pulses and counter will start counting down. The circuit is as shown in figure 10.12(e).
Figure 10.12(e): Down Counter using IC 74190 PRESET MODE: When you need programmable divider one should PRESET output Q0–Q3 to the required count and start counting. The figure 10.12(f) shows experimental setup for studying presettable Up/down counter. Case 1: Presettable Up counter. Step 1: Close switch S2 Step 2: Apply the count to which you want to PRESET the counter to P0 – P3 input. Step 3: Close switch S1. Moment switch is closed P0 – P3 contents will appear at Q3 – Q0. You can see it as LED glows. Step 4: Apply clock pulses. (The pulses should be of low frequency so that you can see output LED changing) Step 5: Release (open) S1 switch. munotes.in
Page 198
198 Step 6: Now counter will start counting from presetted count. Let's say Q3 – Q0 = 0101 = (5)10. Then it will count 5, 6, 7, 8, 9 and back to ‘0’. It won’t again preset to zero unless and until S1 is closed again. If we want that after 9, counter again preset to ‘5’ (or presetted count) then we have to add combinational circuit.
Figure 10.12(f): Presettable up / down counter. Case 2: Presettable down counter. Step 1: Open switch S2. Step 2: Steps written in case 1 from (2) to (5) is same here also. Step 3: Now counter will, start counting from presetted count. Let's say Q3 – Q0 = 0101 = (5)10. Then counter will count 5, 4, 3, 2, 1, 0 and back to 9. It won't preset again to 5 in this circuit unless and until S1 is closed again. HOLD: To HOLD or LATCH the count in the counter make 1PL CE U D==1 /D and CP, both pins are treated as don’t care IC 74191: IC 74191 is binary up/down counter with preset and ripple clock. If you compare it with 74190, IC 74190 is decade counter, whereas 74191 counts 0 to 15. This IC can count up or down synchronously and has a munotes.in
Page 199
199 synchronous preset. Preset feature allows the chip to be used in dividers. The pin configuration and logic symbol is as shown in figure 10.12.1
Figure 10.12.1: Pinout and Logic Symbol – IC 74191 Pin names are as follows Pin Names Description CE Count enable input (Active low) CP Clock pulse input (Active rising edge) P0-P3 Parallel data inputs PL Asynchronous parallel load input (Active low) UD Up/Down count control input Q0-Q3 Flip Flop outputs RC Ripple clock output (Active low) TC Terminal count output (Active HIGH) State diagram for chip is as shown in Figure 10.12.1(a) 74191 counts up from 0 to 15 (shown by dark line) and also counts down from 15 – 0 (shown by dotted line). 74191 can be operated in different modes
Figure 10.12.1(a): State diagram – IC 74191 Out munotes.in
Page 200
200 Following is the Mode select table for IC 74191 INPUTS MODE PL CE UD CP Count down 1 0 0
Count Up 1 0 1
Preset (Async) 0 X X X No Change (HOLD) 1 1 X X Following is the RC Truth table Inputs Output CE TC CP RC 0 1 1 X X 1 X 0 X 1 The modes are same as 74190, therefore the explanation given in 74190 holds for 74191 also. For cascading or multistage counter, the configuration explained in 74190 holds for 74191 also. RC truth table is also similar. 10.13 ANALYSIS OF COUNTER CIRCUITS Up till now we have solved some example based on T, D and JK FF design. This part was designing the counter circuit or synthesis of counter, where we were given state diagram and we have to find circuit for the same. Now it is analysis, i.e. circuit will be given to you and we have to find state diagram, and some time unused state will be given to us and we have to find how counter is going to behave. The method is very simple. Explained it point by point munotes.in
Page 201
201 (1) Firstly present state will be given to you e.g. say presently counter is in CBA = 010, now next states. By chance if the state is not given, you assume some state. The thumb rule is to start from 000. (2) This present state is now previous state for us. (3) You have to now find out, I/ps to all the FFs, because of this previous state. (4) After finding out inputs of all FFs. assume that CLK edge hits. Now you already know the input, you know the truth table of each FF. So find out what will be Q output of FF. This 'new' state will be next state of the FF. (5) Now von assume the next state as previous and start from point 3. This chain should be combined unless and until you get next state, which already exists previously. For example, We started with slate 4. From 4 next state is 6. From 6 next is 8. From 8 next is 9 and from 9 next state is 4. Means '4' has occurred twice so chain is complete. If you want you can draw state diagram as shown in Figure 10.13(a).
Figure 10.13(a): State diagram In above example it may happen that you get 6, after 9.6 is already present. But now state diagram will be different. It is as shown in Figure 10.13(b). ∴ 4 is bushing.
Figure 10.13(b): State diagram Thus you go on trying different combination and find next states. To make analysis simple, all 5 points can be combined in 'one' table. You keep the table standard now onwards.
munotes.in
Page 202
202 10.14 SUMMARY In this chapter we have studied in detail about counters which includes asynchronous, synchronous counters, terms related to counters, IC 7493 (4-bit binary counter), Bushing, Type T Design, Type JK Design, Presettable counter , IC 7490, IC 7492, and Synchronous counter ICs with examples. 10.15 REFERENCE FOR FURTHER READING For further detailed study following are books prescribed by the University 1. Digital Electronics and Logic Design by N. G. Palan 2. Modern Digital Electronics by R. P. Jain 3. Digital Principles and Applications by Malvino and Leach ***** munotes.in
Page 203
203 11 REGISTERS Unit Structure 11.0 Objectives 11.1 Introduction 11.2 Parallel and Shift registers 11.3 Serial Shifting 11.4 Serial - in Serial - out (SISO) 11.5 Serial - in Parallel - out 11.6 Parallel - in Parallel - out 11.7 Ring counter 11.8 Johnson counter 11.9 Application of shift registers 11.10 Pseudo-random binary sequence generator 11.11 IC7495 11.12 Seven Segment displays 11.13 Analysis of shift counters. 11.14 Summary 11.15 Reference for further reading 11.0 OBJECTIVES This chapter would make you understand the following concepts What is register? • Different types of registers – Parallel and Shift registers. • Serial Shifting, • Ring counter, Johnson Counter. • Applications of Shift Register. • Pseudo-random binary sequence generator • IC7495, Analysis of Shift Counter munotes.in
Page 204
204 11.1 INTRODUCTION Till this point, we have studied different flip-flops and conversion from one to another. Now let's concentrate on application part of flip-flops. The most common use of FF is a simple Register (OR a n bit memory storage device). In this section, we will start with basic definition of register and slowly move on to shift register. Register is a group of memory element that works together as a unit. Register simply stores a binary word. When register accepts parallel data and outputs parallel data, the same is referred as Parallel register or buffer register. About shift register, it is nothing but memory element with facility of shifting left and right, bit by bit. Before going deep into shift register, let's see structure of buffer register. 11.2 PARALLEL AND SHIFT REGISTERS 11.2.1 Buffer Register: Buffer register is simplest kind of register and stores digital word. The structure of buffer register, built with the edge triggered D type FF is shown in Figure 11.2
Figure 11.2: Buffer Register Working: (1) Initially, consider Q3 Q2 Q1 Q0 = 0 0 0 0 (2) Apply data to be stored at input terminals Y3 – Y0. Let's say Y3 Y2 Y1 Y0 = 1010. (3) Apply clock pulse. (4) When first clock edge arrives, Y3 Y2 Y1 Y0 = Q3 Q2 Q1 Q0 = 1010 munotes.in
Page 205
205 (5) Even though if now Y3 Y2 Y1 Y0 = 0 0 0 0, Q3 Q2 Q1 Q0 = 1010 i.e. latched Conclusion: From Fig. 11.2 and WORKING we conclude that, (1) There must be one FF for each bit in binary number. ∴ For 4 bit we require 4 FFs. (2) Simultaneously Y3 – Y0 was applied and loaded to Q3 - Q0 by single clock pulse. i.e. at a time Q3 to Q0 was loaded. (3) Therefore, the way we applied input and taken output, is called parallel in - parallel out (PIPO). The block schematic representation is shown in Figure 11.2.1. This is also called as Parallel Shifting.
Figure 11.2.1: Parallel in – Parallel out (PIPO) 11.3 SERIAL SHIFTING One more method of loading or shifting the data is called Serial Shifting. What do you mean by serial? Serial means bit by bit data flow, serially, on single line. Serial shifting has only single bit data line, not 4 or 8 as in parallel loading. The serial shifting can be represented by block schematically, as shown in Figure 11.3. Single bit data is entered in register and serially single data bit is taken out, through register. A group of flip-flops connected to provide serial out, when serial input is given, is called as Shift register munotes.in
Page 206
206
Figure 11.3: Serial Shifting Basically if you see, loading parallel data is much faster than the serial. Secondly, normally we work with 8 bit, 16 bit, and 32 bit parallel data bits. So one can ask, why you think of serial data? The answer for the question is very simple. If you see, up till now we are looking of loading the registers, but now think of loading or transmitting data at distant end. Fig. 11.3.1 shows parallel and serial data transmission.
Figure 11.3.1: Parallel and Serial data transmission As shown in Figure 11.3.1 parallel transmission requires 8 lines, serial requires single line. Now think of distance between A and B location is in meters and kilometers. At such a large distance just increasing length of the wire is not the solutions because now wire is Transmission line, so reflection, impedance matching, power required etc. parameter, we have to consider. Increasing power will increase total power consumption of the system. In parallel, power for 8 lines has to be increased; ∴ p o w e r consumed is much, in comparison with single line of serial. ∴ Normally serial transmission is preferred over parallel. At this point you must be eager to know how serial data looks like. It is shown in figure 11.3.2
Figure 11.3.2: Format of Serial data As shown in Figure 11.3.2, data is represented on time axis is bit by bit, not full 8 bit or 16 bit as in parallel. Time ‘t’ for each bit is same. Data stream shown is, ..0, 1, 1, 0, 0, 1,… munotes.in
Page 207
207 Therefore serial communication has become common and most widely used media for communication. But our systems are normally dealing with parallel (8 bit, 16 bit and so on), ∴ o n e h a s t o c o n v e r t parallel to serial. This function is also called as parallel input and serial output (PISO). Serial data is now transrnitted to location B. On receiving side (B side), one has to convert serial data back to parallel. This function of conversion is called serial in and parallel out (SIPO). Finally one may require serial in and serial out (SISO). Figure 11.3.3 shows generalized block schematic of four functions.
Figure 11.3.3: Generalized block schematic of four functions. 11.4 SERIAL IN – SERIAL OUT (SISO) In SISO, two main operations are performed, serial left shifting and serial right shifting Serial Left Shift Figure 11.4 shows serial operation, built using D Flip-Flop. To know data shifts left we temporarily take output of Q2 Q1 and Q0 also
Figure 11.4: Serial operation munotes.in
Page 208
208 Working: (1) Initially all FFs are reset ∴ Q3 Q2 Q1 Q0 = 0 0 0 0 (2) Make Data IN = 1. (a) At 1st CLK edge, output will be Q3 Q2 Q1 Q0 = 0 0 0 1 (Refer truth table of D FF). (b) At 2nd CLK edge, output will be Q3 Q2 Q1 Q0 = 0 0 1 1 (c) At 3rd CLK edge, output will be Q3 Q2 Q1 Q0 = 0 1 1 1 (d) At 4th CLK edge, output will be Q3 Q2 Q1 Q0 = 1 1 1 1 (3) Now the Data IN = 0. (e) At 5th CLK edge, output will be Q3 Q2 Q1 Q0 = 1 1 1 0 (f) At 6th CLK edge, output will be Q3 Q2 Q1 Q0 = 1 1 0 0 (g) At 7th CLK edge, output will be Q3 Q2 Q1 Q0 = 1 0 0 0 (h) At 8th CLK edge, output will be Q3 Q2 Q1 Q0 = 0 0 0 0
Figure 11.4.1: Waveforms If you observe, 1 or 0 travels from right hand to left hand, ∴ called left shifting. Let's observe waveforms for the same. Waveforms are self-explanatory. Refer Figure 11.4.1. Shift Right: Figure 11.4.2 shows serial right shift circuit, built using D FF. munotes.in
Page 209
209
Figure 11.4.2: Serial right shift circuit Working: (1) Initially all FFs are cleared ∴ Q3 Q2 Q1 Q0 = 0 0 0 0 (2) Make Data In = 1 (a) 1st CLK edge, output will be, Q3 Q2 Q1 Q0 = 1 0 0 0 (b) 2nd CLK edge, output will be, Q3 Q2 Q1 Q0 = 1 1 0 0 (c) 3rd CLK edge, output will be, Q3 Q2 Q1 Q0 = 1 1 1 0 (d) 4th CLK edge, output will be, Q3 Q2 Q1 Q0 = 1 1 1 1 (3) Now apply Data In = 0. (e) 5th CLK edge, output will be, Q3 Q2 Q1 Q0 = 0 1 1 1 (f) 6th CLK edge, output will be, Q3 Q2 Q1 Q0 = 0 0 1 1 (g) 7th CLK edge, output will be, Q3 Q2 Q1 Q0 = 0 0 0 1 (h) 8th CLK edge, output will be, Q3 Q2 Q1 Q0 = 0 0 0 0 Thus 1 and 0, travel from left to right, ∴ right shifting. 11.5 Serial in - Parallel out In this function, data is entered serially and taken out in parallel. To take data parallel out, it is necessary to have all data bits available as output, at the same time and therefore output of each FF is taken.
Figure 11.5: Circuit diagram Serial in – Parallel out munotes.in
Page 210
210 If you observe the diagram carefully you will find that, (1) Clock of all FFs are tied together, therefore all FF changes state at same time. (2) Asynchronous input, CLEAR, is given to all FF. S o t h a t w h e n CLEAR = 0, all FFs are resetted, ∴ output Q = 0000 0000. (3) A and B are data inputs, either of the terminal can be used as control line. When A = 0, irrespective of B, input to FF will be 0. At each CLOCK edge 0 travels from left to right and after 8 CLOCK pulses. Q output = 0000 0000. It means if B = Data In, data will get inhibited. When A = 1, NAND gates enabled and data Input B passes through NAND gate inverted. The input data shifted serially in the register. (4) Output of all FFs are taken as final output. O/P is Q, not. Output appears at a time, ∴ It is parallel output. (5) Data inputs may be changed while CLOCK is either low or high. 11.6 PARALLEL IN – PARALLEL OUT This type we have already studied in section 11.2.1, buffer register. In that Y3 - Y0 was inputted parallel and Q3 - Q0 taken out parallel. 11.7 RING COUNTER Refer figure 11.4 in that circuit if Q3 is connected to Serial Data In. then circuit is going to circulate injected pulse. The way circuit behaves, it is named as 'Ring Counter'.
Figure 11.7: Ring counter Working: Basically ring counter resembles shift register because the bits are shifted left one position per positive clock edge. Only change is feedback line. i.e. output of Q3 given to Q0. munotes.in
Page 211
211 (1) Initially CLOCK goes low then back to high. F3, F2, F1 will be reset and F0 is preset giving ∴ output Q3 Q2 Q1 Q0 = 0 0 0 1. (2) At 1st positive CLOCK edge, MSB moves to LSB, Q3 → Q0, Q2 → Q3, Q1 → Q2 and Q0 → Q1 ∴ output Q3 Q2 Q1 Q0 = 0 0 1 0 (3) At 2nd positive CLOCK edge, with respect to second point, bits will shift left. ∴ Output Q3 Q2 Q1 Q0 = 0 1 0 0. (4) At 3rd positive CLOCK edge, with respect to 3rd point, bits will shift left. ∴ Output Q3 Q2 Q1 Q0 = 1 0 0 0 (5) At 4th positive CLOCK edge, with respect to 4th point, bits will shift left. ∴ Output Q3 Q2 Q1 Q0 = 0 0 0 1 Thus presetted '1' follows circular path or makes ring. ∴ It is called as ring counter. Observe waveform for the same. Refer Fig. 11.7 (a)
Figure 11.7 (a): Waveform – Ring counter Conclusion: (1) Number of FFs used are 4. (2) Number of states for ring counter is also 4. i.e. 0001, 0010, 0100, 1000 and chain repeats. (3) Number of 1‘s s is single. Let's write output Q for 8 bit. So for 8 bit, 8 FFs will be used. Initially Q = 0000 0010 1st clock edges, Q = 0000 0010 2nd clock edges, Q = 0000 0100 3rd clock edges, Q = 0000 1000 4th clock edges, Q = 0001 0000 5th clock edges, Q = 0010 0000 munotes.in
Page 212
212 6th clock edges, Q = 0100 0000 7th clock edges, Q = 1000 0000 8th clock edges, Q = 0000 0001 → Repeat, If you require you can also take output from
, ∴ For 4 bit Refer Figure 11.7 Initially when CLOCK = 0, Q = 0001 ∴
= 1110 1st CLOCK edge Q = 1101 2nd CLOCK edge Q = 1011 3rd CLOCK edge Q = 0111 4th CLOCK edge Q = 1110 Application: Ring counters are invaluable when it is necessary to control sequence of operation. Mainly ring counters are used in microprocessor. Relationship of number of states and FFs: In ring counter number of FFs and number of states are equal. Ring counter using JK FF is shown in Figure 11.7.1. The working of circuit is same as that of, when D FF is used
Figure 11.7.1: Ring counter using JK FF 11.8 JOHNSON COUNTER (TWISTED RING COUNTER) In ring counter output shift register was fed back to input of first FF, that technique was referred as direct feedback. But if outputs of last FF are crossed and then connected to inputs of first FF. the technique is munotes.in
Page 213
213 called inverse feedback. The counter we get from this technique is called Johnson counter or twisted ring counter Circuit: Let's draw circuit of Johnson counter using positive edge triggered JK FF.
Figure 11.8: 4 bit Johnson counter CLOCK QD QC QB QA State Decimal Equivalent Initially 0 0 0 0 1 0 1 0 0 0 1 1 1 2 0 0 1 1 3 3 3 0 1 1 1 4 7 4 1 1 1 1 5 15 5 1 1 1 0 6 14 6 1 1 0 0 7 12 7 1 0 0 0 8 8 8 0 0 0 0 1 0 Figure 11.8(a): Truth table Working: Refer Figures 11.8 and 11.8(a). (1) Initially
is made low and then high after some time. ∴ a l l F F s w i l l b e c l e a r e d a n d o u t p u t QD QC QB QA = D C B A = 0000. (2) Now Inputs JD = JC = JB = 0, KD = KC = KB = 1 and JA = 1, KA = 0. So CLOCK edge hits. A will change from 0 ∴1 BCD are unchanged ∴ DCBA = 0001. (3) Inputs JD = JC = 0, KD = KC = 1. But JA = JB = 1, KA = KB = 0. ∴ the moment CLOCK edge hits D and C are unchanged. A is also unchanged. But B changes from 0 ∴ 1. ∴ DCBA = 0011. (4) Inputs JD = 0 KD = 0, JA = JB = JC = 1 and KA = KB = KC = 0 and ∴ the CLOCK edge will change output C from 0 ∴ 1, A, B and D are unchanged. ∴ DCBA = 0111. munotes.in
Page 214
214 (5) Inputs JD = JC = JB = JA and KD = KC = KB = KA = 0 ∴ n e x t CLOCK edge changes D from 0 ∴ 1, ∴ DCBA = 1111 (6) Because of change of state of D from 0 ∴ 1. Now I/P to JA = 0 and KA = 1, JD = JC = JB = 1 and KD = KC = KB = 0. ∴ next CLOCK edge changes A from 1 ∴ 0 ∴ DCBA = 1110. (7) Now input to JA = JB = 0 and KA = KB = 1 and JD = JC = 1 and KD = KC = 1 ∴ next CLOCK edge changes B from 1 ∴ 0. ∴ DCBA = 1100 means A, D, C are unchanged. (8) At this stage input to JA = JB = JC = 0 and KA = KB = KC = 1, JD = 1 and KD = 0. ∴ next CLOCK edge keeps A, B and D unchanged, C changes from 1 0. ∴ DCBA = 1000. (9) Finally input to JA = JB = JC = JD = 0 and KA = KB = KC = KD = 1 ∴ at next CLOCK edge D changes from 1 ∴ 0. ∴ DCBA = 0000, Now cycle will repeat from point 2 onwards. As we have seen in working of Johnson counter and observing truth table, we conclude that number of states of Johnson counter are double of number of FFs. Therefore for 4 FFs states will be 8. 5 FFs states will be 10 and for 8 FFs states will be 16. Johnson counter using D FF:
Figure 11.8(b): Johnson counter using D FF The working of the circuit is same as what we have seen 11.9 APPLICATIONS OF SHIFT REGISTERS Shift registers can be used for: (1) Generating sequence (pulse generator) (2) Counters (3) Random bit generator. munotes.in
Page 215
215 (1) Sequence Generator (Pulse Generator): Block schematic structure is shown in Figure 11.9
Figure 11.9: Block diagram – Sequence generator Basically shift register sequence generator contains basic two blocks: (1) 'N' bit shift register (SIPO type). (2) Combination logic circuit. Combinational logic circuit has input QN-1 to Q0. From this it will decide, what should be the next serial input for shift register block, should be generated, so that new state or sequence will appear. Now we will take an example to design sequence generator. Example 1: The following pulse train is to be generated by using a shift register. Explain the steps in designing and draw logic diagram. pulse train ... 1011010110 ... Solution: (1) Observe the pulse train carefully and you will find that main pulse train, which is repeating, is 10110. i.e Re...1011010110 ...Maim peating (2) Calculate number of distinct timing intervals. In short you calculate number of bits of pulse train. In our case it is 5 ( 1 0 1 1 0 ) 1 2 3 4 5 … . . (3) Number of FFs can be given by 21Ns≤− Where N = Number of FFs. S = Number of distinct timing intervals. ∴ S ≤ 2N – 1 ∴ 6 ≤ 2N ∴ N = 3 ∴ 3 FFs are required. munotes.in
Page 216
216 (4) Preparing state table for sequence generator: Make table, containing number of states, decimal equivalent and 3 output of FF (N = 3)
Figure 11.9(a): State table Procedure for preparing State table: (a) Write the format of table as shown in Figure 11.9(a). i.e. states, output of 'N' number of FF and decimal equivalent. (b) Under column 1st (Normally MSB is selected) write down sequence 'vertically'. (c) Now just imagine that sequence is having ring structure and shift the full sequence by y one bit. ∴ If sequence is 10110, rotate it left by one bit so we will get 01101. Write down shifted version under column 2. (d) Again shift the sequence by one bit. Therefore w i t h r e s p e c t t o original it will be shifted twice. Sequence under column 2 is 01101. Shift left by one bit. ∴ Sequence is 11010. Write it under column 3. (e) Continue shifting of sequence unless you reach to LSB column. After shifting (Rolling) sequence now find out decimal equivalent of binary sequence. For our case we got 5, 3, 6, 5, 2. In this decimal sequence, decimal number 5 is repeated twice, ∴ states are not distinct, ∴ we have to increase number of FFs to get distinct states. Therefore make state table again with four FFs. munotes.in
Page 217
217
Figure 11.9(b): State table Procedure for making truth table is same as we discussed just now. If we observe the decimal equivalent, it is coming out to be 11, 6, 13, 10, 5. All states are distinct. (5) Design of Combinational circuit: Here we have to find out O/P Y of combinational circuit, given to shift register, so that state changes from previous to next. For example let's say DCBA = 1011 (1 decimal), what should be input to shift register, so that DCBA will be 0110. Means we have to apply '0' to input of shift register or in short Y should be 0. Same way you find Y for each state. The format of table is shown in Figure 11.9(c) State table State QD QC Q1 1 1 0 1 2 0 1 1 3 1 1 0 4 1 0 1 5 0 1 0 MSB Column Figure 11.9(c): State table As shown in Figure 11.9 (c). Output Y of combinational circuit is again nothing but 1 bit shifted version of LSB column. munotes.in
Page 218
218 (6) K-Map: Valid states are 11, 6, 13, 10, 5, remaining states a r e d o n‘ t ca r e . States reached to 13, four variable K-Map should be used.
Figure 11.9(d): K – Map (7) Logic diagram:
Figure 11.9(e): Logic diagram 11.10 PSEUDO – RANDOM BINARY SEQUENCE (PRBS) GENERATOR One important application of shift register is pseudo-random generator. It is basically used to generate random sequence. Due to random sequence generation the same can be used for generating noise, as well as used for data encryption. By generating random noise, one can test immunity given by his / her design to the noise. By encrypting data, it becomes difficult job for a person who hacks the data in between. Basically, the sequence generated is not truly random because it cycles through all possible combinations once every 2n — 1 clock cycles (n= number of FFs). Generation of pseudo random sequence is based on feedback given to shift register through Combinational logic circuit. Figure 11.10 depicts noise generator based on pseudo-random sequence. The combinational circuit used is simple EX-OR gate. munotes.in
Page 219
219
Figure 11.10: Noise generator based on pseudo-random sequence It uses, 31 stage shift register provided with linear feedback to produce maximum length pseudo-random bit sequence. One of the significant features of pseudo-random sequence is that the noise produced from there is repeatable. The spectral density of the noise output of this circuit is uniform to within ±1 dB over the frequency range 20Hz to 20 kHZ. The maximum length of sequence (MLS) generated will be 2n – 1 ∴2n – 1 = 231 – 1, sufficient length to encrypt the data. 11.11 IC7495 We are going to study now TTL MSI Chip 7495. 4 bit shift register with serial and parallel synchronous operating mode. Features of the chip are: (1) Synchronous shift left capability. (2) Synchronous parallel load. (3) Separate shift and load clock inputs. (4) Synchronous expandable shift right. Let's see internal block of IC 7495 and Pin configuration. munotes.in
Page 220
220
Figure 11.11(a): Pin Configuration – IC 7495
Figure 11.11(b): Logic diagram (Universal Shift Register) We are going to perform basically three functions using 7495: (1) Parallel load (2) Shift left (3) Shift right 1. Parallel Load: a) Make mode control = 1, therefore AND gate 2, 4, 6, 8 will get enabled. (b) Apply input ABCD. munotes.in
Page 221
221 (c) In this case clock 2 input (pin number 8) is enabled. Therefore a HIGH to LOW transition on clock and input will transfer parallel data ABCD inputs to Q0 – Q3. (d) Here clock 1 input is don’t case. DS is also don’t care. 2. Shift Right: (a) Make mode control = 0, therefore AND gate 1, 3, 5 , 7 w i l l b e enabled and AND gate 2, 4, 6, 8 will get disabled. (b) The data input to FF QA is now at serial input (DS). (c) Clock and input is don’t care. ABCD inputs are don’t care. (d) Apply CLOCK input to clock 1. (e) A HIGH to LOW transition on enabled clock 1 input transfers data serially from from DS to QA, QA t o QB, QB t o QC a n d QC to QD respectively (right shift). 3. Shift Left: a) For shift left operation external connection are to b e p e r f o r m e d . Connect QD to C, QC to B and QB to A. as shown in figure 11.11.1
Figure 11.11.1: Three functions using 7495 11.12 SEVEN SEGMENT DISPLAYS 7 Segment display is one of the oldest methods of displaying values in electronic devices. The combination of 7 LEDs makes the whole display. Every time a single pin gets the power of a specific range it starts glowing. The pattern and drawing of LED make the decimal digit 8. Then turning on/off the specific pins make the 7-segment t o s h o w t h e o t h e r decimal numbers. The LED has a total of 10 input pins. It also comes in two types; one is the cathode and the other one is the anode. In both types, munotes.in
Page 222
222 one gives the common anode and the other has a common cathode. The 7-segment is useable directly by any low voltage device. As 7-segment displays are very common components of d i g i t a l devices, it is good to be familiar with the ‘driving’ circuits behind them, and the 4511 is a good example of a typical driver IC. Its operating principle is to input a four-bit BCD (Binary-Coded Decimal) value and energize the proper output lines t o f o r m t h e corresponding decimal digit on the 7-segment LED display. The BCD inputs are designated A, B, C, and D in order from least-significant to most-significant. Outputs are labeled a, b, c, d, e, f, and g, each letter corresponding to a standardized segment designation f o r 7 - s e g m e n t displays. Of course, since each LED segment requires its own dropping resistor, we must use seven 470 Ω resistors placed in series between the 4511’s output terminals and the corresponding terminals of the display unit. Most 7-segment displays also provide for a decimal point (sometimes two), a separate LED and terminal designated for its operation. All LEDs inside the display unit are made common to each other on one side, either cathode or anode. The 4511 display driver IC requires a common-cathode 7-segment display unit, and so that is what is used here. After building the circuit and applying power, operate the four switches in a binary counting sequence (0000 to 1111), noting the 7-segment display. A 0000 input should result in a decimal ‘0’ display, a 0001 input should result in a decimal ‘1’ display, and so on through 1001 (decimal ‘9’). What happens for the binary numbers 1010 (10) through 1111 (15)? Read the data sheet on the 4511 IC and see what the manufacturer specifies for operation above an input value of 9. In the BCD code, there is no real meaning for 1010, 1011, 1100, 1101, 1110, or 1111. These are binary values beyond the range of a single decimal digit, and so have no function in a BCD system. The 4511 IC is built to recognize this, and output (or not output accordingly. Three inputs on the 4511 chip have been permanently connected to either Vdd or ground: the ‘Lamp Test,’ ‘Blanking Input,’ and “Latch Enable.” To learn what these inputs do, remove the short jumpers connecting them to either power supply rail (one at a time!), and replace the short jumper with a longer one that can reach the other power supply rail. For example, remove the short jumper connecting the ‘ L a t c h Enable’ input (pin #5) to ground, and replace it with a long jumper wire munotes.in
Page 223
223 that can reach all the way to the Vdd power supply rail. Experiment with making this input ‘high’ and ‘low,’ observing the results on the 7-segment display as you alter the BCD code with the four input switches. After you have learned what the input‘s function is, connect it to the power supply rail enabling normal operation, and proceed to experiment with the next input (either ‘Lamp Test’ or ‘Blanking Input’). Once again, the manufacturer‘s datasheet will be informative as to the purpose of each of these three inputs. Note that the ‘Lamp Test’ (LT) and ‘Blanking Input’ (BI) input labels are written with Boolean complementation bars over the abbreviations. Bar symbols designate these inputs as active-low, meaning that you must make each one ‘low’ in order to invoke its particular function. Making an active-low input ‘high’ places that particular input into a “passive’’ state where its function will not be invoked. Conversely, the “Latch Enable” (LE) input has no complementation bar written over its abbreviation, and correspondingly it is shown connected to ground (“low”) in the schematic so as to not invoke that function. The “Latch Enable” input is an active-high input, which means it must be made “high” (connected to Vdd) in order to invoke its function
Figure 11.12 Schematic diagram of Seven Segment display with display driver 11.13 ANALYSIS OF SHIFT COUNTERS In this circuit will be given and one has to find states through which shift register passes. To understand this let's solve example. Example 2: A shift register with associated combinational logic circuit is shown in Figure 11.13. Explain its action by drawing waveforms for the munotes.in
Page 224
224 outputs of shift register (ABCD). Assume that initially shift register is in state ABCD = 1111.
Figure 11.13: circuit diagram Solution: (1) Write equation for output Y. (2) Basically output Y is serial in for shift register, shift is left shift, ∴ serial in placed in LSB i.e. D. So make table. CLOCK edge Serial In A B C D ()OP Y = A B C D⊕+ - - 1 1 1 1 0 1st 0 1 1 1 0 0 2nd 0 1 1 0 0 1 3rd 1 1 0 0 1 1 4th 1 0 0 1 1 0 5th 0 0 1 1 0 1 6th 1 1 1 0 1 0 7th 0 1 0 1 0 1 8th 1 0 1 0 1 1 9th 1 1 0 1 1 1 10th 1 0 1 1 1 1 11th 1 1 1 1 1 0 Figure 11.13(a): truth table Explanation: (Refer Figure 11.13(b)) Initially ABCD = 1111, ∴ Y = (1 ⊕ 1) + = 0 + 0 = 0 ∴ Y = serial in = 0, ∴ w h e n 1 s t C L O C K e d g e h i t s , ABCD = 1110 (Legit shift) Now ABCD = 1110, ∴ Y = (1 ⊕ 1) + = 0 + 0 = 0 munotes.in
Page 225
225 ∴ Y = serial in = 0, ∴ w h e n 2nd CLOCK edge hits, ABCD = 1100 Thus you proceed till you get initial condition ABCD = 1111. From table (Figure 11.13(a)) we found that counter, counts through 15, 14, 12, 9, 3, 6, 13, 10, 5, 11, 7 and 15. Thus generates sequence → 1 1 1 1 0 0 1 1 0 1 0 1 W a v e f o r m s ( W a v e f o r m s a r e as shown in Figure 11.13(b)).
Figure 11.13(b): waveform 11.14 SUMMARY In this chapter we have studied in detail about registers which includes parallel and shift registers, serial shifting, serial-in serial-out, serial-in parallel-out, parallel-in parallel-out, Ring counter, Johnson counter, Application of shift registers, Pseudo-random binary sequence generator, IC7495, Seven Segment displays and analysis of shift counters with examples. 11.15 REFERENCE FOR FURTHER READING For further detailed study following are books prescribed by the University 1. Digital Electronics and Logic Design by N. G. Palan 2. Modern Digital Electronics by R. P. Jain 3. Digital Principles and Applications by Malvino and Leach ***** munotes.in