WELCOME Digital Circuits and Logic Design Name of the CourseLTPC Digital Circuits and Logic Design (Common to ECE, CSE and IT) 3003 Course objectives: - презентация

1 WELCOME

2 Digital Circuits and Logic Design

3 Name of the CourseLTPC Digital Circuits and Logic Design (Common to ECE, CSE and IT) 3003 Course objectives: To understand common forms of number representation in digital circuits and Boolean algebra. To learn basic techniques for the design of digital circuits and fundamental concepts used in the design of digital systems and simplify logic expressions using basic theorems, K-map and Tabular methods. To understand the concept of Combinational logic design and realize logic expressions using MUX and Decoder Illustrate the concept of sequential logic design; analyze the operation of flip-flop and conversion from one flip-flop to another, and application of flip-flop. To impart to student the concepts of sequential machines of digital system.

4 Introduction Logic design is one of the disciplines that has enabled digital revolution, which has dramatically altered our economics, communication, and life in general! Cars are growingly more computers!

5 Computers are every-where!

6 What is Design? Design is the process of coming up with a solution to a problem: – Need to understand the problem – Need to understand the constraints We desire an efficient design! Consider, the problem of building an university: – Create an xyz sq ft of floor area, where say 10,000 people can work efficiently. – Constraints: Dimensions Aesthetics Departments, rooms Other services Lifts Parking Space Emergency Exits… Money and Time

7 Digital Logic Design A digital designer uses components from digital electronics to solve problems in real life. Transistors from CMOS (Complementary MOS) forms the core. A digital designer abstracts it like a switch. Circuit: An inter-connected collection of switches

8 GatePath 0Closed 1Open Gate Drain Source Gate Source Drain GatePath 0Open 1Closed pMOS nMOS Transmits 1 well Transmits 0 poorly Transmits 0 well Transmits 1 poorly Transistors as Switches: 1 st Abstraction

9 An Example Problem: Make a two-way switch for a bulb.

10 An Example Problem: Make a two-way switch for a bulb.

11 An Example Problem: Make a two-way switch for a bulb.

12 An Example Problem: Make a two-way switch for a bulb.

13 Digital Versus Analog Systems – A Digital system recognizes, process and outputs only a finite or discrete number of values (say, 0, 1, 2, 3,…) of some parameter. – E.g.: A digital watch recognizes, process and displays only some discrete time values (say, upto a precision of 1 second) between 0:00 and 24:00 hours, for example, 12:32:44 pm – An Analog System recognizes, process and outputs a continuum (infinite number) of values of some parameter within a specified range. – E.g.: An analog watch displays all tunes between 0:00 and 24:00 hours, for example, 2:32: pm (though you may not be able to detect it!)

14 Digital Versus Analog

15 Digital Circuits and Logic Design Unit-I: Number Systems and Boolean Algebra Number systems: Introduction to different number system and their conversions, Complement of number system and subtraction using complement method, Floating-Point Representation, Weighted and Non-weighted codes and its Properties, Error detection and correction codes. Boolean Algebra: Boolean algebra and logic gates, Basic theorems and properties of Boolean Algebra, Boolean functions, canonical and standard forms, Universal Gates.

16 Unit-II: Minimization Methods of Boolean functions Minimization of logic expressions by algebraic method, Sum of Products (SOP), Product of Sums (POS), K-Map Method (upto five variables), Dont Care Combinations, Multilevel NAND/NOR realizations, Prime and essential Prime Implicants, Tabular Method, Prime Implicants Chart, Simplification Rules.

17 Unit-III: Combinational Circuits Design procedure, Half/full adders, Half / full substractors, Carry look ahead adder, BCD adder, Multiplexer/De- Multiplexer, Encoder / Decoder, Priority encoders, Implementation of Higher - Order Device Using Lower Order devices, Implementation of combinational logic using MUX/Decoder, Magnitude Comparator, Programmable logic devices.

18 Unit-IV: Sequential Circuits Sequential Circuits Fundamentals: Basic Architectural Distinctions between Combinational and Sequential circuits, SR Latch, Flip Flops: SR, JK, JK Master Slave, D and T Type Flip Flops, Excitation Table of all Flip Flops, Timing and Triggering Consideration, Conversion from one type of Flip-Flop to another. Registers and Counters: Shift Registers Left, Right and Bidirectional Shift Registers, Applications of Shift Registers, Design and Operation of Ring and Twisted Ring Counter, Operation of Asynchronous and Synchronous Counters.

19 Unit-V: Sequential Machines Finite State Machines, Synthesis of Synchronous Sequential Circuits, Mealy and Moore models, Serial Binary Adder, Sequence Detector, Parity bit Generator Synchronous Modulo N – Counters, Finite state machine capabilities and limitations.

20 Number systems A number system is defined as a system of writing to express numbers. It is the mathematical notation for representing numbers of a given set by using digits or other symbols in a consistent manner. It provides a unique representation of every number and represents the arithmetic and algebraic structure of the figures. It also allows us to operate arithmetic operations like addition, subtraction and division.

21 Number systems The value of any digit in a number can be determined by: – The digit – Its position in the number – The base of the number system There are various types of number system in mathematics. The four most common number system types are: – Decimal number system (Base - 10):0,1,2,3,4,5,6,7,8,9 (,,,,,,,,, ) – Binary number system (Base - 2): 0,1 – Octal number system (Base - 8): 0,1,2,3,4,5,6,7 – Hexadecimal number system (Base - 16) 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F Telugu number digits

22 Characteristics of Numbering Systems 1)The digits are consecutive. 2)The number of digits is equal to the size of the base. 3)Zero is always the first digit. 4)(Base -1) is the last digit 5)The base number is never a digit. 6)When 1 is added to the largest digit, a sum of zero and a carry of one results. 7)Numeric values are determined by the implicit positional values of the digits.

23 Decimal odometer Counting First digit Place Value is (Base) 0 Second digit place value is (Base) 1 Third digit place value is (Base) 2 …….

24 A B C D OE OF DecimalBinaryOctalHexadecimal

25 Number Value 1234 Unit Place value is face value of the number system = Face value X (base) 0 =4X(10) 0 =4 Second Place value = Face value X (base) 1 =3X(10) 0 =30 Third Place value = Face value X (base) 2 =2X(10) 2 =200 Fourth Place value = Face value X (base) 3 =1X(10) 3 = = 1234 = one thousand two hundred thirty four

26 26 Base- b Number Systems Our ordinary decimal (base ten) number system can be used to represent any number while using only ten different digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 But, theres nothing special about the number ten! – We only use base ten because we have ten fingers! Given any integer b > 1, we can describe an alternative base b (or radix b ) number system, in which: – There are exactly b different digit symbols The values of the digits are 0, 1, …, b 1 – An arbitrary integer N > 0 can be written uniquely as a sequence of k digits like ( d k 1 d k 2 … d 2 d 1 d 0 ) b, where 0 d i 0. This is called the base b expansion of N. – The value of N is given by the expression:

27 Alternate Bases Most Widely Used in Computer Engineering Base 2 (binary): – The only digit values are 0 and 1 – Used internally in all modern computers Base 8 (octal): – Digits are 0, 1, 2, 3, 4, 5, 6, 7 – Each octal digit represents a sequence of 3 bits Base 16 (hexadecimal or just hex): – Digits are 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F Where A=ten, B=eleven, …, F=fifteen. – Each hex digit represents a sequence of 4 bits

28 Decimal-to-Radix r Conversions There are two methods for converting a number N from an radix 10(decimal) to a new radix r (Base of converting number system). Method 1: Repeatedly divide N (decimal number) by new radix - r the remainders are the new digits, reading from bottom to top and arrange left to right. Method 2: Repeatedly divide N by the largest power of radix r less than N ; the quotients are the new digits, reading from left to right.

29 N 10 = (255) 10 =(?) Method 1: Repeatedly divide N (decimal number) by new radix - r the remainders are the new digits, reading from bottom to top and arrange left to right. Conversion steps: Divide the number by r. Get the integer quotient for the next iteration. Get the remainder for the r digit. Repeat the steps until the quotient is equal to

30 N 10 = (255) 10 =(?) 2 =(?) 8 =(?) 16 1÷201 DivisionQuotientReminder 255 ÷ ÷ ÷ ÷ ÷271 7÷231 3÷211 ( ) 2 = (255) 10 DivisionQR 255 ÷1615F (15) ÷160F (15) 10 (FF) 16 = (255) 10 (377) 8 = (255) 10

31 Base Powers to Memorize For base conversion and checking of results, as well as many other purposes, you should try to memorize the following: – Powers of 2 up to at least 2 16 : 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, – Powers of 8 up to at least 8 5 : 1, 8, 64, 512, 4096, – Powers of 16 up to 16 8 : 1; 16; 256; 4,096; 65,536; 1,048,576; 16,777,216; 268,435,456; 4,294,967,296 One K (kibi) = 2 10 One Meg (mebi) = 2 20 Four Gigs (gibis) = = Kilo = Mega = Giga = Tera = Peta = Exa = Zeta = Yotta 10 24

32 Method 2: Repeatedly divide N by the largest power of radix r less than N ; the quotients are the new digits, reading from left to right. DivisionReminderQuotient 255 ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷1 0 1 ( ) 2 = (255) 10

33 Method 2 Variation When converting from binary, the divides in method 2 can be replaced by simple subtraction of the powers of 2. Example: – Convert to binary = = = = = =

34 Radix r-to-Decimal Conversions Two methods for conversion using arithmetic in the new base B: Method 1: Directly evaluate the polynomial expression for N b. Method 2: (Horners rule) Repeatedly multiply by b and add digits of N, from left to right until unit place.

35 35 Summary DecBinHex DecBinHex A B C D E F

36 Method 1: Directly evaluate the polynomial expression for N b. Convert to base 10. = 1× × × × × × × × ×2 0 = 1×64 +0×2 + 0×64+ 1×32+ 0×16+ 1×8 + 0×4 + 1×2 + 1×1 = = Convert 3D96 16 to base 10. 3D96 16 = 3× × × ×16 0 = 3×4, × ×16 + 6×1 = 12, , = 15,766 10

37 Method 2: (Horners rule) Repeatedly multiply by b and add digits of N, from left to right until unit place. Convert to base 10. – 1×2 + 0 = 2×2 + 1 = 5×2 + 1 = 11×2 + 0 = 22×2 + 1= 45×2 + 0 = 90×2 + 1 = 181×2 + 1 = Convert 3D96 16 to base 10. – 3×16 = = 61×16 = = 985×16 = = =1X10=10+2=12X10= 120+3=123X10= =1234

38 38 Binary to Hexadecimal Conversion 1.Divide binary number into 4-bit groups 2.Substitute hex digit for each group Pad with 0s if last group less than 4 bits C Decimal Hexadecimal ABCDEF Binary

39 Hexadecimal to Binary Conversion Convert each hexadecimal digit into equivalent of 4-bit group binary number 61C 16 Decimal Hexadecimal ABCDEF Binary

40 40 Binary to Octal Conversion 1.Divide binary number into 3-bit groups 2.Substitute hex digit for each group Pad with 0s if last group less than 3 bits Decimal OCTAL Binary

41 Octal to Binary Conversion Convert each octal digit into equivalent of 3-bit group binary number Decimal Octal Binary

42 Radix Fractions In decimal, we write digits after the decimal point to denote coefficients of negative powers of 10. – Example: means: 3× × × × × ×10 5 By the same token, in any base b, digits after the radix point denote coefficients of negative powers of b. – General form: d k1 d k2 …d 2 d 1 d 0. d 1 d 2 d 3 …d j+1 dj k digits before the radix point j digits after the radix point Radix Point

43 Converting Decimal fractions to Radix r fractions Conversion steps: Multiply decimal fraction number by radix r Get the integer for the new r digit arrange left to right from radix point Get the fraction part for the next iteration. Repeat the steps until the fraction part is equal to 0 (or ~5 digits).

44 Converting Decimal Fractions to Radix r Fractions DivisionQuotientReminder 12 ÷260 Example: (12.345) 10 =(?) 2 =(?) 8 =(?) 16 Integer part = (12) 10 =(?) 2, Fraction part= (0.345) 10 =(?) 2 6 ÷230 3 ÷211 1 ÷201 (12) 10 =(1100) 2 MultiplyIntegerFraction * * * * * * ( ) 2 (0.345) 10 (12.345) 10 ( ) 2 (12.345) 10 ( ) 2 = (14.26) 8 (12.345) 10 ( ) 2 = (C.58) 16

45 Range of Number Representation The range of numbers that can be represented is determined by the number of digits used to represent a number. Largest decimal number represented by 2 digits = 99 = 100 – 1 = 10 2 – 1 = b The largest n digits of radix r Number = r n – 1. Range of Numbers = 0 to r n – 1 Total distinct numbers that can be represented = r n Example: Decimal : 3 digits Range : 000 – Distinct no.s : Binary : 3 digits Range : 0000 – = Distinct no.s : = 8 10 Hexadecimal : 3 digits Range : 000 – FFF 2 = Distinct no.s : = Octal : 3 digits Range : 0000 – = Distinct no.s : =

46 Arithmetic Operations Augend: Addend: Sum: Carry: Decimal Addition Binary Addition Augend+AddendSumCarry Augend: Addend: Sum: Carry: Binary Addition Augend: Addend: Sum: Carry: Octal Addition Augend: Addend: Sum: A8F9 0 Carry: 161E0E0C0 Hexadecimal Addition

47 Arithmetic Operations Decimal Subtraction Minuend : Difference : Barrow: Subtrahend : X X X X X X X +6 = =

48 Binary Subtraction Minuend - SubtrahendDifferenceBarrow Minuend : Difference : Barrow: Subtrahend : = = = =0X2 4 +1X2 2 +1X2 1 +0X2 0 = = X2 3

49 Binary Subtraction Minuend : Difference : Barrow: Subtrahend : = = = = =

50 Unsigned Binary Non-negative integers (greater or equal to zero) – Range from 0 (smallest) to 2 n -1 (largest) for an n-bit representation We can construct an unsigned binary sequence using the algorithm – Build up starting from 0. – Add 1 to the previous number. – Repeat previous step until a string of 1s of length L is reached. BinaryDec BinaryDec

51 Signed Number Representations In digital systems, we often need to represent signed (positive or negative) numbers. – On paper, a signed base- b number can be denoted by just writing down a + or sign in front of it. But, how are signed numbers to be coded using bits? There are many possible methods. Well discuss: – Sign-magnitude representations – Biased representations – Ones-complement representations – Twos-complement representations This is the one that is most commonly used today in digital systems, due to the simplicity of its implementation

52 Sign-Magnitude Representation To represent signed numbers in the range [ 2 n-1 + 1, 2 n-1 1], we can use one bit for the sign and (n-1) bits for the unsigned magnitude (absolute value) of the number. – Most common convention for meaning of sign bit: 0 = positive, 1 = negative. BinaryDec BinaryDec The extra 0 code still requires corrections.

53 Storing Negative Integers 1 method is Sign/Magnitude /- MSBMSB is a Negative, 0 is a Positive

54 Biased Representations In a biased or shifted signed number representation, we represent integers in the range [ n, p ] by using unsigned numbers in the range [0, n + p ]. – To convert signed to unsigned: Add n. – To convert unsigned to signed: Subtract n. – When adding biased numbers, we must subtract the bias. To avoid double-counting it! Example: – Can represent numbers in the range [ 8, 7] using the number range [0, 15] by adding 8 to every number. Numbers in [0, 15] can be represented using 4 bits.

55 Ones-Complement Representation To obtain the representation of x, flip or invert all the bits in the representation of x. – i.e., change all 1s to 0s, and 0s to 1s. – Like sign-magnitude, encodes the range [ 2 n-1 + 1, +2 n-1 1] in n +1 bits, uses the high-order bit as the sign bit, and has redundant codes for 0. BinaryDec BinaryDec

56 Twos Complement Most common scheme of representing negative numbers in computers Affords natural arithmetic (no special rules!) To represent a negative number in 2s complement notation… 1.Decide upon the number of bits ( n ) 2.Find the binary representation of the positive value in n - bits 3.Flip all the bits (change 1s to 0s and vice versa) 4.Add 1

57 Twos Complement Example Represent –5 in binary using 2s complement notation 1.Decide on the number of bits 2.Find the binary representation of the +ve value in 6 bits 3.Flip all the bits 4.Add 1 6 (for example)

58 Sign Bit In 2s complement notation, the MSB is the sign bit (as with sign-magnitude notation) – 0 = positive value – 1 = negative value -5: ve 1*2 5 = : ve 0*2 5 5 = 1*2 2 +1*2 1 27=1*2 4 +1*2 3 +1*2 1 +1* =-5 0+5=5

59 Complementary Notation Conversions between positive and negative numbers are easy For binary (base 2)… +ve -ve 2s C

60 Example +5 2s C -5 2s C Complement of Complement is same number

61 Another Way for 2s Complement Leave all of the least significant 0s and first 1 unchanged and then flip or complement the bits for all other digits. Example: = MSB bit is added 0 for Positive numbers = Leave all of the least significant 0s and first 1 unchanged flip or complement the bits for all other digits ones complement is and add 1 we get 2s complement:

62 Exercise – 2s C conversions What is -20 expressed as an 8-bit binary number in 2s complement notation? – Answer: is a 7-bit binary number in 2s complement notation. What is the decimal value? – Answer: = =2s complement of 20 = = -1*2 6 +1*2 5 +1*2 1 +1*2 0 = =-64+35= -29 or s complement is = +29 therefore before is

63 Using The 2s Compliment Process 9 + (-5) 4 (-9) (-9) + (-5) POS + POS POS POS + NEG POS NEG + POS NEG NEG + NEG NEG Use the 2s complement process to add together the following numbers.

64 POS + POS POS Answer If no 2s complement is needed, use regular binary addition

65 POS + NEG POS Answer Take the 2s complement of the negative number and use regular binary addition (-5) s Complement Process 1] th Bit = 0: Answer is Positive Disregard 9 th Bit

66 POS + NEG NEG Answer 66 Take the 2s complement of the negative number and use regular binary addition (-9) s Complement Process th Bit = 1: Answer is Negative To Check: Perform 2s Complement On Answer

67 NEG + NEG NEG Answer 67 Take the 2s complement of both negative numbers and use regular binary addition (-9) + (-5) s Complement Numbers, See Conversion Process In Previous Slides 1] th Bit = 1: Answer is Negative Disregard 9 th Bit To Check: Perform 2s Complement On Answer

68 r's and (r – 1)'s Complements There are two types of complements for each base-r system: the radix complement (r's ) and diminished radix (r – 1)'s complement. Diminished Radix Complement (r – 1)'s : – Given a number N in case r having n digits, the (r – 1 ) s complement of N is defined as (r n – 1) – N. – For Binary numbers, r = 2 and r – 1 = 1 – For Example N is – the 1s complement of N is (2 4 -1) = (16-1) = = = – For decimal numbers, r = 10 and r – 1 = 9, so the 9s complement is (10 n – 1) – N. – For Example N is – the 1s complement of N is ( ) = ( ) = = Note : Diminished Radix Complement we get, every digit of N subtracted from maximum coefficient of base-r

69 r's and (r – 1)'s Complements Radix Complement – The r's complement of an n-digit number N in base r is defined as r n – N for N 0 and as 0 for N = 0. – Comparing with the (r 1) 's complement, we note that the r's complement is obtained by adding 1 to the (r 1) 's complement. – Since r n – N = [(r n 1) – N] + 1. – Example: Base-10 The 10's complement of is The 10's complement of is – Example: Base-2 The 2's complement of is The 2's complement of is

70 Problems 1.The subtraction of a binary number Y from another binary number X, done by adding the 2's complement of Y to X, results in a binary number without overflow. This implies that the result is____ 2.2's complement representation of a 16-bit number (one sign bit and 15 magnitude bits) if FFFF. Its magnitude in decimal representation is ___ 3.A signed integer has been stored in a byte using the 2's complement format. We wish to store the same integer in a 16 bit word. We should ____ 4.An equivalent 2's complement representation of the 2's complement number 1101 is ____ 5.The 2's complement representation of -17 is _____ 6.4-bit 2's complement representation of a decimal number is The number _____ 7.The range of signed decimal numbers that can be represented by 6-bit l's complement number is _____

71 Subtraction with Complements The efficient method for subtraction is used complement. The subtraction of two n-digit numbers M-N can be : If use (r-1)s complement [1s 9s 7s 15s]: – If the sum produce an end carry which can be added to the sum. – If the sum does not produce an end carry take the (r-1)s comp. of the sum and place – sign. If use (r)s complement [2s 10s 8s 16s]: – If the sum produce an end carry which can be discarded. – If the sum does not produce an end carry take the (r)s comp. of the sum and place – sign.

72 Example : Subtract the following binary number : a) b) Solution : 1)Using 1s comp. 2)Using 2s comp. a) b) a) b) s= s= ( ) discarded -( )

73 Subtract the following decimal number : )Using 9s comp. 2)Using 10s comp discarded

74 Floating Point Representation Fixed point number Consists of integer and fraction parts. It can be written in the positional number representation as d k1 d k2 …d 2 d 1 d 0. d 1 d 2 d 3 …d j+1 dj = The position of the radix point is assumed to be fixed, hence the name fixed-point number. Fixed point numbers have a range that is limited by the significant digits used to represent the number. In scientific applications it is often necessary to deal with numbers that are very large or very small. Instead of using the fixed-point representation, which would require many significant digits, it is better to use the floating- point representation.

75 Floating Point Representation In which numbers are represented by a mantissa comprising the significant digits and an exponent of the radix R. The formal is: Mantissa * R exponent Example : is written as : *10 3 = 25678*10 -2 = *10 2 … = *2 -2 = *2 -1 = *2 4 … Binary floating-point representation has been standardized by the Institute of Electrical and Electronic Engineers (IEEE). Two sizes of formats are specified, that are single precision 32-bit format and a double- precision 64-bit format.

76 IEEE Floating Point Format for Binary Numbers The IEEE floating point format represent as N = ±1.M*2 E-bias value where M is normalized mantissa, which means the most- significant bit is always equal to 1. Thus it is not necessary to include this bit explicitly in the mantissa field. Therefore, if M is the bit vector in the mantissa field, the actual value of the mantissa is 1.M. E is the biased exponent can be represent always positive, the exponent field is in plain binary format which also represents negative exponents with an encoding to positive. A bias of (2 n-1 – 1), where n is number of bits used in exponent, is added to the exponent to get biased exponent ( E ) i.e.: Exponent = E – biased value or E = Exponent + Biased value

77 77 IEEE-754 Format Single Precision 32 bits for single precision Sign of M =1 bit Biased Exponent (E) =8 bits Mantissa (M = 23 bits) For example, the rational number 9÷2 can be converted to single precision float format as following, 9 (10) ÷ 2 (10) = +4.5 (10) = (2) The result said to be normalized, if it is represented with leading 1 bit, i.e (2) x 2 2. Omitting this implied 1 on left extreme gives us the mantissa of float number i.e Where the exponent field is 2, yet encoded as 129 (( )+2) called biased exponent i.e

78 78 IEEE-754 Format Double Precision 64 bits for double precision Sign of M =1 bit Biased Exponent (E) =11 bits Mantissa (M = 52 bits)

79 Number System Classification Positional (or Weighted) Number System Non-Positional (or Non-weighted) Number System Each digit position has a weight or value. The sum of all digits multiplied by a weight gives a total amount being represented. Gray code Excess-3 Decimal number system Binary number system Octal number system Hexadecimal number system BCD(8421) The bit positions in the code groups do not have any specific weight assign to them.

80 BCD code (8421 code) : each decimal digit is replaced by its 4-bit binary equivalent. Example1: is represented by (937.25) 10 = ( ) BCD Convert BCD to its decimal equivalent. Divide the BCD number into four-bit groups and convert each to decimal: BCD =

81 BINARY CODE DECIMAL (BCD) Some codes are unused, like 1010 BCD, 1011 BCD, … 1111 BCD. These codes are considered as errors. Easy to convert, but arithmetic operations are more complicated. Suitable for interfaces such as keypad inputs. Decimal digit BCD

82 Excess-3 Code It is a 4-bit code. It can be derived from BCD code by adding 3 to each coded number. It is an unweighted code. It is a self complementing code i.e the 1s complement of an excess-3 number is the excess-3 code or the 9s complement of the corresponding decimal number. Ex: (395) 10 = ( ) excess-3 (604) 10 = ( ) excess-3 9s complementself-complementing

83 Decimal Ex Unused Combinations

84 Gray Code It is a very useful code also called minimum change codes in which only one bit in the code group changes when going from one step to the next. It is also known as Reflected code. It is an unweighted code, meaning that the bit positions in the code groups do not have any specific weight assign to them. This code is not well suited for arithmetic operations but finds application in input/output devices. These are used in instrumentation such as shaft encoders to measures angular displacement or in linear encoders for measurement of linear displacement.

85 Binary – to - Gray Conversion MSB in the gray code is same as corresponding digit in binary number. Starting from Left to Right, add each adjacent pair of binary digits to get next and gray code digit. (Discard the carry if generated) MSB of Binary is same as that of gray code. Add each binary digit to the generated gray digit in the next adjacent position (discard the carry if generated) Binary Gray Binary

86 GRAY CODE DecimalBinaryGray CodeDecimalBinaryGray code

87 Alphanumeric Codes In many situations, digital systems are required to handle data that may consist of numericals, letters and special symbols. The digital systems should recognize the codes that represent these alphanumeric data. These codes are called Alphanumeric cades. It is used in many computers to represent alphanumeric characters and symbols internally and so it is also called Internal code. Two codes which are normally used are: (I) Extended BCD Interchange Code (EBCDIC). (ii) American Standard Code for Information Interchange (ASCII).

88 88 ASCII Features Developed by ANSI (American National Standards Institute) Defined in ANSI document X bit code 8 th bit is unused (or used for a parity bit or to indicate extended character set) 2 7 = 128 different codes Two general types of codes: – 95 are Printing codes (displayable on a console) – 33 are Control codes (control features of the console or communications channel) Represents – Latin alphabet, Arabic numerals, standard punctuation characters – Plus small set of accents and other European special characters (Latin-I ASCII)

89 ASCII Table Most significant bit Least significant bit

90 ASCII Table e.g., a =

91 ASCII Table 95 Printing codes

92 ASCII Table 33 Control codes

93 ASCII Table Alphabetic codes

94 ASCII Table Numeric codes

95 ASCII Table Punctuation, etc.

96 ASCII Table MSD LSD SOHDC1!1AQaW 2STXDC22BRbr 3ETXDC3#3CScs 4EOTDC4$4DTdt 5ENQNAK%5EUeu 6ACJSYN&6FVfv 7BELETB7GWgw 8BSCAN(8HXhx 9HTEM)9IYiy ALFSUB*:JZjz BVTESC+;K[k { CFFFS,N^n~ FSIUS/?O_oDEL

97 97 Example: Hello, world ======================== Binary Hexadecimal C 6F 2C C 64 Decimal Hello, worldHello, world ======================== ========================

98 EBCDIC 8-bit code Developed by IBM IBM and compatible mainframes only Rarely used today (common in archival data) – Character codes differ from ASCII Conversion software to/from ASCII available ASCIIEBCDIC Space A41 16 C1 16 b

99 EBCDIC Table (1 out of 2)

100 EBCDIC Table (2 out of 2)

101 Error Detecting Code When information (digital data) is transmitted from transmitter (T x ) to Receiver (R x ) there is a possibility that errors can occur due to electrical noise One of the simplest and most widely used schemes for error detection is the PARITY METHOD For detection of error an extra bit known as parity bit is attached to each code word to make the number of ones in the code even (even parity) or odd (odd parity) Even parity method : The value of the parity bit is added so that the total number of ones in the code group (including parity bit) is an even number. Odd parity method: The value of the parity bit is added so that the total number of ones in the code group (including parity bit) is an odd number.

102 Example: We have, ( ) By even parity method By odd parity method It should be apparent that this parity method would not work if two bits were in error. because two errors would not change the oddness or evenness of the number of ones in the code. In practice the parity method is used only in situation where the probability of a single error is very low and probability of double errors is essentially zero.

103 Error Correction Error correction can be handled in two ways When an error is discovered, the receiver ask to the sender retransmit the entire data unit A receiver can use an error-correcting code, which automatically corrects certain errors.

104 A simple error-detecting code Lets start simple: suppose messages are one bit long Take the message bit, and repeat it once – This is called a Two-repetition code Suppose the network causes no bit error Receiver removes repetition to correctly decode the message bits Sender: Receiver:Network:

105 Detecting one bit error Suppose the network causes up to one bit error The receiver can detect the error: – It received a non-code word Can the receiver correct the error? – No! The other codeword could have been sent as well Sender:Receiver:Network: Error detected 01 10

106 Reception with two bit errors Can receiver detect presence of two bit errors? – No: It has no way of telling which codeword was sent! Enough bit errors that the sent codeword jumped over the space between code words Sender:Receiver:Network: Space between codewords:

107 Error Correction Consider a scenario where retransmissions are not practical and error rate is high – Example: Space-based communication We would like to add redundancy such that data is useful despite errors – Not only to detect but also to recover from – Similar to noisy telephone conversation on a known topic Assume there are only 1-bit errors and we want to recover from errors Solution: Declare some of the bit combinations invalid – Example: 2-bit messages protected from 1-bit errors – So, how much redundancy is needed to correct d errors?

108 Hamming Distance Hamming Distance: The number of bit positions two codewords differ – XOR (adding bit by bit only consider sum discard carry) two code words, count 1s in the result – = Hamming distance = 2 Minimum Distance: Given a set of codewords, take the minimum of Hamming distances of all valid codeword pairs – To detect d-bit errors, minimum distance of d+1 is needed – To correct d-bit errors, minimum distance of 2d+1 is needed

109 Hamming Distance How to decode received codewords – If codeword is valid, accept as it is – If codeword is invalid, map it to the closest valid codeword Only darker points are valid codewords Lighter ones are invalid Sender:Receiver:Network: 001 Fix error Decision boundary

110 Can We Correct Single Bit Error? Try Obvious Brute Force MethodSend 3 copies of every bit! – Suppose data is – Send Can we correct burst errors? Yes, with trick – Send Cant we do better than that?

111 Theoretical Limits of Hamming Code What is the minimum number of check bits (r) needed to correct a single bit error? – m message bits 2 m legal messages – r check bits – n = m+r codeword length – Around a valid codeword, we have n invalid codewords (obtained by inverting each bit individually) – Each bit pattern requires n+1 dedicated codewords – (n+1)2 m 2 n (m+r+1) 2 r Number of Data Bits (m) Number of Redundancy Bits (r) Total Bits (m+r)

112 Hamming Codes Positions of redundancy r bits in Hamming code are 2 0, 2 1, 2 2, …,2 r-1 in codeword and remaining bits are message bits (m) r rd rddd rddd Redundancy bits calculation: r 1 = d 3 d 5 d 7 d 9 d 11 r 2 = d 3 d 6 d 7 d 10 d 11 r 4 = d 5 d 6 d 7 r 8 = d 9 d 10 d 11 r8r8 r4r4 r2r2 r1r1 Position(d n ) r1 00 r r r

113 Hamming Codes Code Generation and Decoding : Example of message bits are : m is 7 and r is 4 and n is 11 (m+r) rr1r011r e 1 = r 1 d 3 d 5 d 7 d 9 d 11 = = 1 e 2 = r 2 d 3 d 6 d 7 d 10 d 11 = = 1 e 4 = r 4 d 5 d 6 d 7 = = 1 e 8 = r 8 d 9 d 10 d 11 = = Error Position of the error LSB MSB 7 Redundancy bits calculation: r 1 = d 3 d 5 d 7 d 9 d 11 = = r 2 = d 3 d 6 d 7 d 10 d 11 = = r 4 = d 5 d 6 d 7 = = r 8 = d 9 d 10 d 11 = =

114 Hamming Codes Hamming codes solve single error correction problem Can we correct burst errors using Hamming codes? – Yes, with a trick!

115 Boolean Algebra A Boolean algebra is a closed algebraic system containing a set B of two or more elements and the two operators i.e. AND (Dot/Multiplication) & OR (Plus/Addition) Boolean Algebra is a tool for the analysis and design of digital systems. In this Algebra, there are no fractions, no negative numbers, no square roots, no cubes roots, no decimals, no logarithms etc. For reasoning about whether propositions (statements) are true (T) or false (F). – The truth value of the proposition. George Boole

116 Boolean Algebra Postulate Boolean algebra defined with a set of elements, a set of operators, and a number of unproved axioms or postulates. A set of elements is any collection of objects, usually having a common property. The postulates of a mathematical system form the basic assumptions from which it is possible to deduce the rules, theorems, and properties of the system. The most common postulates used to formulate various algebraic structures are as follows: Closure, Associative law, Commutative law, Identity element, Inverse, and Distributive law. Algebra Boolean contains element set B, with two operations binary OR{+}, AND{ } and unary operator NOT{ ' or ¯ }

117 Boolean Operations The complement is denoted by a apostrophe or bar ( ' or ¯ ). It is defined by 0 ' = 1 and 1 ' = 0. The Boolean sum, denoted by + or by OR, has the following values: = 1, = 1, = 1, = 0 The Boolean product, denoted by or by AND, has the following values: 1 1 = 1, 1 0 = 0, 0 1 = 0, 0 0 = 0

118 Axiomatic Definition Of Boolean Algebra 1.a)The structure is closed with respect to the operator + b) The structure is closed with respect to the operator 2.a)The element 0 is an identity element with respect to +; that is, x + 0 = 0 + x = x. b) The element 1 is an identity element with respect to. ; that is, x 1 = 1 x = x. 3.a)The structure is commutative with respect to +; that is, x + y = y + x. b) The structure is commutative with respect to. ; that is, x y = y x. 4.a) The operator. is distributive over +; that is, x (y + z) = (x y) + (x z). b) The operator + is distributive over. ; that is, x + (y z) = (x + y) (x + z). 5.For every element x є B, there exists an element x є B (called the complement of x) such that a)x + x' = 1 and b) x x' = 0. 6.There exist at least two elements x, y є B such that x y.

119 Duality Principal Duality principal – each Boolean expression will be certified if identity of operators and elements are interchangeable Example: Given expression a+(b c)=(a+b) (b+c) therefore duality expression is a (b+c)=(a b)+(b c) Duality principal give free theorem buy one, free one. You only need to prove one theorem and get another one free. If (x+y+z)' = x' y' z' is certified, therefore the duality is also certified (x y z)' = x'+y'+z' If x+1=1 is certified, therefore the duality is also certified x 0=0

120 Boolean Algebra: Basic Theorem Apart from the postulate, there are useful several theorem Theorem 1 : Idempotency a) x+x=xb)x x = x Prove: x+x= (x+x) 1(identity) = (x+x) (x+x')(complement) = x+ (x x')(distributive) = x+0(complement) = x(identity) b) by Duality: x x = x

121 Boolean Algebra: Basic Theorem Theorem 2 : NULL element for + and. operator a) x+1=1 b) x 0=0 Prove: x+1= (x + 1) 1(identity) = (x + 1) (x + x')(complement) = x + (1 x')(distributive) = x + x'(identity) = 1(identity) b) by Duality: x 0=0

122 3. Involution (x ' ) ' =x 4.Absorption a) x+x y=xb) x (x+y)=x 5.Absorption (variant) a) x+x ' y=x+yb) x (x ' +y)=x.y 6.DeMorgan a) (x+y) ' =x ' y ' b) (x y) ' =x ' +y ' 7.Consensus a) xy+x ' z+yz=xy+x z b) (x+y)(x ' +z)(y+z)=(x+y)(x ' +z) = xy + x ' z + yz = xy + x ' z + yz 1 = xy + x ' z + yz (x + x ' ) = xy + x ' z + xyz + x ' yz = xy(1 + z) + x ' z(1 + y) = xy + x ' z

123 Boolean Functions and Expressions A Boolean functions can be transformed from an algebraic expression into a circuit diagram composed of logic gates. Definition: Let B = {0,1}. The variable x is called a Boolean variable if it assumes values only from B. A function from B n, the set {(x 1, x 2, …, x n )|x i B, 1 i n}, to B is called a Boolean function of degree n. Boolean functions can be represented using expressions made up from the variables and Boolean operations

124 Question: How many different Boolean functions of degree 1 are there? Solution: There are four of them, F 1, F 2, F 3, and F 4 : 01 F 1 =Constant0 00 F 2 =x = Transfer 01 F 3 =Complement 10 F 4 =Constant1 11 Boolean Functions and Expressions X Function

125 Question: How many different Boolean functions of degree 2 are there? Solution: There are 16 of them, F 1, F 2, …, F 16 : Boolean Functions and Expressions Functions X0101 Y0011 F 1 = Constant O00000 F 2 = AND X Y 0001 F 3 = y AND NOT X X' Y 0010 F 4 = YY0011 F 5 = X AND NOT Y X Y' 0100 F 6 = XX0101 F 7 = XORX Y0110 F 8 = ORX+Y0111 F 9 = NOR(X+Y)'1000 F 10 = XNOR(X Y)1001 F 11 = NOT XX'1010 F 12 = IF Y OR NOT XX' + Y1011 F 13 = NOT YY'1100 F 14 = IF X OR NOT YX + Y'1101 F 15 = NAND (X Y)' 1110 F 16 = Constant Question: How many different Boolean functions of degree n are there? Solution: A Boolean function is an assignment of 0 or 1 to each of these 2 n different n-tuples. Therefore, there are 2 2 n different Boolean functions.

126 Boolean Functions and Expressions Example: Give a Boolean expression for the Boolean function F(x, y) as defined by the following table: Possible solution: F(x, y) = ( x' + y') (x' + y) (x + y') (x + y) or (x ' y) xyF(x, y)

127 Boolean Functions and Expressions There is a simple method for deriving a Boolean expression for a function that is defined by a table. This method is based on Minterms or Maxterms. A minterm of n variables = product of n literals in which each variable appears exactly once either in T or F form, but not in both. (Also known as a standard product term) Each minterm has value 1 for exactly one combination of values of variables. Notation of minterm is m i, EX: X'Y', X'Y, XY', XY = 00, 01, 10, 11 = m 0, m 1, m 2, m 3 A maxterm of n variables = sum of n literals in which each variable appears exactly once in T or F from, but not in both. Each maxterm has a value of 0 for exactly one combination of values of variables. Notation of maxterm is M i, EX: X'+Y', X'+Y, X+Y', X+Y = 11, 10, 01, 00 = M 0, M 1, M 2, M 3

128 Truth Table notation for Minterms and Maxterms Minterms and Maxterms are easy to denote using a truth table. Example: Assume 3 variables x,y,z (order is fixed) xyzMinterm (Truth Value =1) Maxterm (Truth Value =0) 000x'y'z' = m 0 x+y+z = M 0 001x'y'z = m 1 x+y+z' = M 1 010x'yz' = m 2 x+y'+z = M 2 011x'yz = m 3 x+y'+z' = M 3 100xy'z' = m 4 x'+y+z = M 4 101xy'z = m 5 x'+y+z' = M 5 110xyz' = m 6 x'+y'+z = M 6 111xyz = m 7 x'+y'+z' = M 7

129 Canonical Forms (Unique) Any Boolean function F( ) can be expressed as a unique sum of minterms and a unique product of maxterms (under a fixed variable ordering). If you have a truth table for a function, you can write a sum of minterms expression just by picking out the rows of the table where the function output is 1 (1-minterm). If you have a truth table for a function, you can write a product of maxterms expression just by picking out the rows of the table where the function output is 0 (0-maxterm).

130 Example Truth table for f 1 (a,b,c) at right The canonical sum-of-products form for f 1 is f 1 (a,b,c) = m 1 + m 2 + m 4 + m 6 = a'b'c + a'bc'+ ab'c' + abc' The canonical product-of-sums form for f 1 is f 1 (a,b,c) = M 0 M 3 M 5 M 7 = (a+b+c)(a+b'+c') (a'+b+c')(a'+b'+c'). Observe that: m i = M i ' or m i ' = M i f contains all the minterms not in f abcf1f1 mimi MiMi 0000m0m0 M0M0 0011m1m1 M1M1 0101m2m2 M2M2 0110m3m3 M3M3 1001m4m4 M4M4 1010m5m5 M5M5 1101m6m6 M6M6 1110m7m7 M7M7

131 Shorthand: and f 1 (a,b,c) = m(1,2,4,6), where indicates that this is a sum-of-products form, and m(1,2,4,6) indicates that the minterms to be included are m 1, m 2, m 4, and m 6. f 1 (a,b,c) = M(0,3,5,7), where indicates that this is a product-of-sums form, and M(0,3,5,7) indicates that the maxterms to be included are M 0, M 3, M 5, and M 7. Since m i = M i ' for any i, m(1,2,4,6) = M(0,3,5,7) = f 1 (a,b,c) Replace with (or vice versa ) and replace those i s that appeared in the original form with those that do not. Example: f 1 (a,b,c)= a ' b ' c + a ' bc ' + ab ' c ' + abc ' = m 1 + m 2 + m 4 + m 6 = (1,2,4,6) = (0,3,5,7) = M 0 M 3 M 4 M 6 = (a+b+c)(a+b ' +c ' )(a ' +b+c ' )(a ' +b ' +c ' )

132 Standard Forms (NOT Unique) Standard forms are like canonical forms, all variables need appear in the individual product (SOP) or sum (POS) terms. Expand non-canonical terms by inserting equivalent of 1 in each missing variable x: (x + x') = 1 in SOP and xx' =0 in POS and Remove duplicate minterms and maxterms Example: f 1 (a,b,c) = a'b'c + bc' + ac' is a standard sum-of- products form f 1 (a,b,c) = a'b'c + bc' + ac' = a'b'c + (a+a')bc'+ a(b+b')c' = a'b'c + abc' + a'bc'+ abc'+ ab'c' = a'b'c + abc' + a'bc + ab'c' f 1 (a,b,c) = (a+b+c)(b'+c')(a'+c') is a standard product-of-sums form. f 1 (a,b,c) = (a+b+c)(b'+c')(a'+c') = (a+b+c){(aa')+(b'+c')}{(bb')+(a'+c')} = (a+b+c){(a+b'+c') (a'+b'+c')}{(b+a'+c') (b'+a'+c')} = (a+b+c)(a+b'+c')(a'+b'+c')(a'+b+c')(a'+b'+c') = (a+b+c)(a+b'+c')(a'+b'+c')(a'+b+c')

133 Logic Gates Logic Gates are most fundamental digital circuits that can be constructed from diodes, transistors and resistors connected in such a way that the circuit output is the result of a basic logic operation (OR. AND, NOT) performed on the inputs. It is simply a device that has two or more inputs and one output. The function of each logic gate will be represented by Boolean expression. Logic Gates Basic Logic Gates (AND. OR, NOT) Universal Logic Gates (NAND, NOR) Other Logic Gates (EXOR,EXNOR)

134 The output of an AND gate is 1 if and only if ALL its input signals are 1s, otherwise it is 0. A truth table is a means for describing how a logic circuits output depends on the logic levels present at circuits input. The number of input combinations will equal 2 n for an n-input truth table. The logic symbol for a two input AND gate is shown in below. The AND logic can be further illustrated using what is known as the Venn diagram Basic Logic Gate (AND) 2-Input AND A B F F = AB = AB ABY Truth Table

135 The output of an OR gate is 0 if and only if ALL its input signals are 0s, otherwise it is 1. A truth table is shown in below. The logic symbol for a two input OR gate is shown in below. The OR logic can be further illustrated using what is known as the Venn diagram Basic Logic Gate (OR) 2-Input OR A B F F = A+B ABY Truth Table

136 NOT is a unary operator. This gate can be performed on a single input variable and resulting single output variable. The NOT operation is also referred to as INVERSION or COMPLEMENT. Its output logic level is always opposite to the logic level of this input. The NOT logic can be further illustrated using what is known as the Venn diagram Basic Logic Gate (NOT) NOT (Inverter) AY Truth Table AF F = A F = A' Presence of small circle called bubble always denotes inversion

137 Timing Diagram A B F=A B + G=A + B H=A 10 t0t0 t1t1 t2t2 t3t3 t4t4 t5t5 t6t6 Gate Input signals Gate Output Signals Basic Assumption: Zero time for signals to propagate Through gates Transitions

138 The output of an NAND gate is 1 if and only if ALL its input signals are 0s, otherwise it is 1 or Complement of AND A truth table is a means for describing how a logic circuits output depends on the logic levels present at circuits input. The NAND logic can be further illustrated using what is known as the symbol and Venn diagram Universal Logic Gate (NAND=AND+NOT) 2-Input NAND A B F F = (AB) = A+B F = (AB)' = A'+B' ABY Truth Table

139 The output of an NOR gate is 1 if and only if ALL its input signals are 0s, otherwise it is 1 or Complement of OR. A truth table is shown in below. The logic symbol for a two input OR gate is shown in below. The OR logic can be further illustrated using what is known as the Venn diagram Universal Logic Logic Gate (NOR=OR+NOT) 2-Input NOR A B F F = (A+B) = AB F = (A+B)' = A'B' ABY Truth Table

140 Logic 1 iff either A=1 or B=1, but not both. It acts like as an odd no. of 1s detector in the input. It is also called stair case switch It is mostly used in parity generation and detection. A truth table is shown in below. The logic symbol for a two input XOR gate is shown in below. The XOR logic can be further illustrated using what is known as the Venn diagram Other Logic Logic Gate (EXOR or XOR) (Exclusive OR) 2-Input XOR A B F F = AB+AB = (A B) F = A'B+AB' = (A B) ABY Truth Table

141 Logic 1 iff A and B either 0 or 1. It acts like as an even no. of 1s detector in the input. It is mostly used in parity generation and detection. A truth table is shown in below. The logic symbol for a two input XNOR gate is shown in below. The XNOR logic can be further illustrated using what is known as the Venn diagram Other Logic Logic Gate (EXNOR or XNOR) (Exclusive NOR) 2-Input XNOR A B F F = AB+AB = (A B) F = AB+A'B' = (A B) ABY Truth Table

142 Universal Gates Known as a universal gate because ANY digital circuit can be implemented with NAND or NOR gates alone. A NOT gate is made by joining the inputs of a NAND gate together. Q= (AA)'=(A)' An AND gate is made by inverting the output of a NAND gate as shown below. Q = (AB)''=(AB) To be an OR gate, however, the output must be 1 if any input is 1. Therefore, if the inputs are inverted, any high input will trigger a high output. Q=(A'B')'=A''+B''=A+B A NOR gate is an OR gate with an inverted output. Output is high when neither input A nor input B is high.

143 Universal Gates An XOR gate is made by connecting four NAND gates as shown below. This construction entails a propagation delay three times that of a single NAND gate. Q = (A'B)+(AB')=(A+B)(A'+B')=(A+B)(AB)'=A(AB)'+B(AB)'={{A(AB)'}'{B(AB)'}'}' =NAND{{NAND(NAND)} {NAND(NAND)}}

144