Digital Integrated Circuit Design

Digital Integrated Circuit Design

I N T R O D U C T I O N T O LO G I C D E S I G N Chapter 1 Digital Systems and Binary Numbers grtayemiiolu 2 OUTLINE OF CHAPTER 1 Digital Systems Binary Numbers Complements Signed Binary Numbers Sunday, January 26, 2020 Binary Arithmetic Number-base Octal & Conversions Hexadecimal Numbers Binary Codes

Binary Storage Binary Logic & Registers INTRODUCTION TO LOGIC DESIGN 1.1 DIGITAL SYSTEMS 4 D I G I TA L S Y S T E M S Digital age and information age Digital computers General purposes Many scientific, industrial and commercial applications Digital systems Telephone switching exchanges Digital camera Electronic calculators, PDA's Digital TV Discrete information-processing systems Manipulate discrete elements of information

For example, {1, 2, 3, } and {A, B, C, } Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 5 D I G I TA L S Y S T E M S D I G I TA L S I G N A L The physical signals can quantities assume discrete values. X(t) Greater or only

The physical quantities or signals may vary continuously over a specified range. accuracy X(t) t Sunday, January 26, 2020 A N A LO G S I G N A L t D I G I TA L I N T E G RAT E D C I RC U I T D E S I G N 6 D I G I TA L S Y S T E M S Binary digital signal An information variable represented by physical quantity. For digital systems, the variable takes on discrete values. Two level, or binary values are the most prevalent values.

Binary values are represented abstractly by: Digits 0 and 1 Words (symbols) False (F) and True (T) Words (symbols) Low (L) and High (H) And words On and Off Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 7 D I G I TA L S Y S T E M S Binary values are represented by values or ranges of values of physical quantities. V(t) Logic 1 undefine Logic 0 t Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 1.2 BINARY NUMBERS 9 B I N A RY N U M B E R S

Decimal Number System Base (also called radix) = 10 5 1 2 7 4 10 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 102 101 100 10-1 10-2 100 10 1 0.1

0.01 Digit Position Integer & fraction 5x100 1x10 Digit Weight Weight = (Base) Position Magnitude Sum of Digit x Weight Formal Notation Sunday, January 26, 2020 500 + 1 0 + 2x1 7x0.1 4x0.01 2 0. 0.0

+ 7 4 d2 x B2 + d1 x B1 + d0 x B0+d-1 x B-1+d-2x B-2 (512.74)10 INTRODUCTION TO LOGIC DESIGN 10 B I N A RY N U M B E R S Octal Number System Base = 8 8 digits { 0, 1, 2, 3, 4, 5, 6, 7} Weights Weight = (Base) Position Magnitude Sum of Digit x Weight Formal Notation 5

1 2 7 4 82 81 80 8-1 8-2 64 8 1 1/8 1/64 5x64 1x8 2x1

7x1/8 4x1/64 320 + 8 + 2 0.87 0.062 + 5 5 o2 x B2 + o1 x B1 + o0 x B0 + o-1 x B-1+o-2 x B-2 (330.9375)10 (512.74)8 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 11 B I N A RY N U M B E R S Hexadecimal Number System Base = 16 16 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}

Magnitude Formal Notation Sunday, January 26, 2020 5 7 A 162 161 160 16-1 16-2 256 16 1 1/16 1/256 5x1

7x1/16 10x1/256 Position Sum of bit x Weight E 1x256 14x16 Weights Weight = (Base) 1 25 22 0.437 0.03 + + 5 + 6 4 5 9 H2 x B2 + H1 x B1 + H0 x B0+H-1 x B-1+H-2x B-2 (458.4765625)10 (1E5.7A)16 INTRODUCTION TO LOGIC DESIGN

12 B I N A RY N U M B E R S Binary Number System Base = 2 2 digits { 0, 1 }, called binary digits or bits Weights Weight = (Base) Position Magnitude Sum of bit x Weight Formal Notation Groups of bits 4 bits = Nibble, 8 bits = Byte Sunday, January 26, 2020 1 0

1 0 1 22 21 20 2-1 2-2 4 2 1 0.5 0.25 1x4 0x2 1x1 0x0.5 1x0.25

0.2 5 b2 x B2 + b1 x B1 + b0 x B0+b-1 x B-1+b-2x B-2 4 + 0 + 1 0 + (5.25)10 (101.01)2 INTRODUCTION TO LOGIC DESIGN 13 B I N A RY N U M B E R S The power of 2 n 2n n 2n 0 20=1

8 28=256 1 21=2 9 29=512 2 22=4 10 210=1024 3 23=8 11 211=2048 4 24=16 12

212=4096 5 25=32 20 220=1M 6 26=64 30 230=1G 7 27=128 40 240=1T Sunday, January 26, 2020 D I G I TA L I N T E G RAT E D C I RC U I T D E S I G N 1.3 BINARY ARITHMETIC

15 B I N A RY A R I T H M E T I C ADDITION Decimal Addition 1 + 1 1 Carry 5 5 5 5 1 0 = Ten Base Sunday, January 26, 2020 Subtract a Base

INTRODUCTION TO LOGIC DESIGN 16 B I N A RY A R I T H M E T I C ADDITION Binary Addition - Column Addition 1 1 1 1 1 1 1 1 1 1 0 1 + 1 0 1 1 1 1 0 1 0 1 0 0 = 61 = 23 = 84 (2)10 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 17 B I N A RY A R I T H M E T I C SUBTRACTION Binary Subtraction - Borrow a Base when needed

1 2 0 2 2 0 0 2 = (10)2 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 Sunday, January 26, 2020 = 77 = 23 = 54 INTRODUCTION TO LOGIC DESIGN 18 B I N A RY A R I T H M E T I C 1 0 1 1 1 MULTIPLICATION Binary Multiplication Bit by bit

x 1 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 1 0 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 1.4 NUMBER-BASE CONVERSION 20 NUMBER BASE CONVERSION e luat e a v E d nitu g a M Decimal (Base 10)

Eva Mag luate nitu de Sunday, January 26, 2020 Octal (Base 8) Evaluate Magnitude Binary (Base 2) Hexadecimal (Base 16) INTRODUCTION TO LOGIC DESIGN 21 NUMBER BASE CONVERSION Decimal to binary conversion Divide the number by the Base (=2) Take the remainder (either 0 or 1) as a coefficient Take the quotient and repeat the division

Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 22 NUMBER BASE CONVERSION Decimal (integer) to binary conversion Example: (13)10 13/ 2 6/ 2 3/ 2 1/ 2 QuotientRemainderCoefficient = 6 1 a0 = 1 = 3 0 a1 = 0 = 1 1 a2 = 1 = 0 1 a3 = 1

Answer: (13)10 = (a3 a2 a1 a0)2 = (1101)2 MSB LSB Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 23 NUMBER BASE CONVERSION Decimal (fraction) to binary conversion Multiply the number by the Base (=2) Take the integer (either 0 or 1) as a coefficient Take the resultant fraction and repeat the division Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 24

NUMBER BASE CONVERSION Decimal (fraction) to binary conversion Example: (0.625)10 Integer Fraction Coefficient a-1 = 1 0.625 *2= 1 . 25 0.25* 2 = 0 . 5 a-2 = 0 0.5 * 2 = 1 . 0 a =1 -3 Answer: (0.625)10 = (0.a-1 a-2 a-3)2 = (0.101)2 MSB LSB Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 25

NUMBER BASE CONVERSION Decimal (integer) to octal conversion Example: (175)10 QuotientRemainderCoefficient 175 /8= 21 7 a0 = 7 21 /8= 2 5 a1 = 5 2/ 8 = 0 2 a2 = 2 Answer: (175)10 = (a3 a2 a1 a0)2 = (257)8 MSB LSB Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 26 NUMBER BASE CONVERSION Decimal (fraction) to octal conversion

Example: (0.3125)10 Integer Fraction Coefficient a-1 = 2 0.3125 *8= 2 . 5 0.5 * 8 = 4 . 0 a-2 = 4 Answer: (0.3125)10 = (0.a-1 a-2 a-3)2 = (0.24)8 MSB LSB Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 1.5 OCTAL & HEXADECIMAL NUMBERS 28 O C TA L & H E X A D E C I M A L N U M B E R S

Binary to octal conversion 8 = 23 Each group of 3 bits represents an octal digit Example: Assume Zeros ( 1 00 1 1 0 . 00 1 )2 ( 2 6 . 2 )8 Octal Binary 0 000 1 001

2 010 3 011 4 100 5 101 6 110 7 111 Works both ways (Binary to Octal & Octal to Binary) Sunday, January 26, 2020 D I G I TA L I N T E G RAT E D C I RC U I T D E S I G N 29 O C TA L & H E X A D E C I M A L N U M B E R S

Binary to hexadecimal conversion 16 = 24 Each group of 4 bits represents a hexadecimal digit Example: Assume Zeros (00 1 0 1 1 0 .00 01 0 )2 ( 1 6 . 4 )16 Works both ways (Binary to Hex & Hex to Binary) Sunday, January 26, 2020 Hex Binary 0 0000 1

0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001

A 1010 B 1011 C 1100 D 1101 E 1110 F 1111 D I G I TA L I N T E G RAT E D C I RC U I T D E S I G N 30 O C TA L & H E X A D E C I M A L N U M B E R S Octal to hexadecimal

Example: ( 2 2 )8 6 . conversion Assume Zeros Convert to binary as an intermediate step ( 0 0 0 1 0 1 1 0 . 001 0 ( 4 Sunday, January 26, 2020 1 )16 6 . D I G I TA L I N T E G RAT E D C I RC U I T D E S I G N

)2 31 O C TA L & H E X A D E C I M A L N U M B E R S Sunday, January 26, 2020 Decimal Octal Hex Binary 00 00 0 0000 01 01 1 0001 02

02 2 0010 03 03 3 0011 04 04 4 0100 05 05 5 0101 06 06

6 0110 07 07 7 0111 08 10 8 1000 09 11 9 1001 10 12 A

1010 11 13 B 1011 12 14 C 1100 13 15 D 1101 14 16 E 1110

15 17 F 1111 INTRODUCTION TO LOGIC DESIGN 1.6 COMPLEMENTS 33 COMPLEMENTS Complements are used in digital computers to simplify the subtraction operation and for logical manipulation. Simplifying operations leads to simpler, less expensive circuits to implement the operations. There are two types of complements for each base-r system: diminished radix complement. the radix complement Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN

34 COMPLEMENTS Diminished Radix Complement (r-1)s Complement Given a Number = N, base = r, digits = n, The (r1)s complement of N is defined as: (rn 1) N Example for 6-digit decimal numbers: 9s complement is (rn 1)N = (1061)N = 999999N 9s complement of 546700 is 999999546700 = 453299 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 35 COMPLEMENTS For decimal numbers r = 10 and (r-1) = 9, this is called 9s complement of N. (10n-1)-N. 10n represents a number that consist of a single 1 followed by n 0s. 10n-1 is a number represented by n 9s.

For binary numbers r = 2 and r-1 = 1, this is called 1s complement of N. (2n-1)-N. 2n represents a binary number that consist of a 1 followed by n 0s. Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 36 COMPLEMENTS For Example: 0011 (2 2 4 4 -1) 0011 = 10000 - 1 1111 -

0011 01111 1 0 can 0 have either 1-0 =1 When subtracting binary digit from 1 1 we or 1-1 =0 which causes bit to change from 0 to 1 or from 1 to 0. 1s complement of a binary is formed by changing 1s to 0s and 0s to 1s. Example: 0 0 1 1 0 1 1 1 1 0 0 1 0 0 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 37 COMPLEMENTS Example for 7-digit binary numbers: 1s complement is (rn 1) N = (271)N = 1111111N 1s complement of 1011000 is 11111111011000 = 0100111 Observation:

Subtraction from (rn 1) will never require a borrow Diminished radix complement can be computed digit-by-digit Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 38 COMPLEMENTS 1s Complement (Diminished Radix Complement) All 0s become 1s All 1s become 0s If you add a number and its 1s complement 1 0 1 1 0 0 0 0 + 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 39

COMPLEMENTS Radix Complement, the r's Complement Given a Number = N, base = r, digits = n, The rs complement of N is defined as: rn - N, for N 0 and 0 for N = 0. The r's complement is obtained by adding 1 to the (r 1) 's complement, since = [(rn 1) N] + 1. = rn-N Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 40 COMPLEMENTS 10s complement of N can be formed: By leaving all least significant 0s unchanged. By subtracting first non-zero least significant digit by 10 By subtracting all higher significant digits from 9.

2s complement of N can be formed: By leaving all least significant 0s and the first 1 unchanged and replacing 1s with 0s and 0s with 1s in all other higher significant digits. Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 41 COMPLEMENTS Example: Base-10 The 10's complement of 012398: 9 9 9 9 9 10 - 0 1 2 3 9 9 8 7 6 0 8 2 The 10s complement of 246700: 9 9 9 10 0 0 Sunday, January 26, 2020 2 4 6 7 5 3

7 0 0 3 0 0 INTRODUCTION TO LOGIC DESIGN 42 COMPLEMENTS 2s Complement (Radix Complement) Take 1s complement then add 1 Toggle all bits to the left of the first 1 from the right Example: Number: 1 0 1 1 0 00 0 1 0 1 1s Comp.: 1 1 1 1 0 1 0 0 1 1 1 1 1 + 0 1 0 1 0 0 0 0 Sunday, January 26, 2020 or 1 0 0 0 0 01 01 0 0 0 0

INTRODUCTION TO LOGIC DESIGN 43 COMPLEMENTS Example: Base-2 The 2's complement of 1101100 is 0010100 1 1 0 1 10 0 1 1 0 1 1 0 0 1 1 + 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 Sunday, January 26, 2020 or 0 01 010 0 INTRODUCTION TO LOGIC DESIGN 44 COMPLEMENTS

Example: Base-2 The 2's complement of 0110111 is 1001001 0 1 1 0 11 1 + 1 0 0 1 0 0 0 1 1 0 0 1 0 0 1 Sunday, January 26, 2020 0 1 1 0 1 1 1 or 1 00100 1 INTRODUCTION TO LOGIC DESIGN 45 COMPLEMENTS Complement of the complement restores the number to its original value rs complement of N is rn-N The complement of the complement is r n

-(r n - N ) = N original number Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 46 COMPLEMENTS The subtraction of two n-digit unsigned numbers M N in base r can be done as follows: 1. Add the minuend M to the rs complement of the subtrahend N. o N rs complement = rn-N o = M + rn-N o = M N+rn 2. If M N, the sum will produce an end carry rn, which can be discarded; what is left is the result M N. 3. If M < N, the sum does not produce an end carry and is equal to rn-(N-M), which is the rs complement of (N-M). To obtain the answer in a familiar form, take the rs complement of the sum and place negative sign in front. Sunday, January 26, INTRODUCTION TO LOGIC DESIGN

2020 47 COMPLEMENT Example 1.5 Using 10's complement, subtract 72532 3250. M= N = 3250 72532 Step1: Take 10s complement of N 9 9 9 10 0 - 3 2 9 6 7 Sunday, January 26, 2020 5 0 5 0 INTRODUCTION TO LOGIC DESIGN 48 COMPLEMENT Step2: To find the SUM, Add 10s complement of N to M 72532

+ 96750 SUM= 169282 Step3: To find the ANSWER discard end carry 105, Subtract rn from SUM 169282 - 100000 ANSWER= 69282 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 49 COMPLEMENT Example 1.6 Using 10's complement, subtract 3250 - 72532. M = 3250 N= 72532 Step1: Take 10s complement of N 9 9 9 9 10 - 7 2 5 3 2 7 4 6

Sunday, January 26, 2020 2 8 INTRODUCTION TO LOGIC DESIGN 50 COMPLEMENT Step2: To find the SUM, Add 10s complement of N to M 03250 + 27468 There is no end carry! SUM= 30718 Step3: SUM) 9 - 3 6 To find the ANSWER take the (10s complement of 9 9 9 10 0 7 1 8 9 2 8 2 ANSWER= - 6 9 2 8 2 Sunday, January 26, 2020

INTRODUCTION TO LOGIC DESIGN 51 COMPLEMENT Example 1.7: Given the two binary numbers X = 1010100 and Y = 1000011, perform the subtraction (a) X Y and (b) Y X using 2s complements. (a) Step1:1 Take the02s0complement of Y 0 0 1 1 0 1 1 1 1 0 1 Step2: Add 2s complement of Y to X 1 0 1 0 1 0 0 + 0 1 1 1 1 0 1 There is an end carry! 1 0 0 1 0 0 0 1 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 52 COMPLEMENT Step3: Discard the end carry. 1 0 0 1 0 0 0 1 +1 0 0 0 0 0 0 0 ANSWER= 0 0 0 1 0 0 0 1

(b) Y X: Step1: Take the 2s complement of X 1 0 1 0 1 0 0 0 1 0 1 1 0 0 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 53 COMPLEMENT Step2: Add 2s complement of X to Y 1 0 0 0 0 1 1 + 0 1 0 1 1 0 0 SUM= 1 1 0 1 1 1 1 There is no end carry! Step3: To find the answer Y X = - (2s complement of SUM) 1 1 0 1 1 1 1 -0 0 1 0 0 0 1 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 54 COMPLEMENTS

Subtraction of unsigned numbers can also be done by means of the (r 1)'s complement. Remember that the (r 1) 's complement is one less then the r's complement. Example 1.8 :Repeat Example 1.7, but this time using 1's complement. (a) X Y = 1010100 1000011(84 67 = 17) Step1: Take the 1s complement of Y 1 0 0 0 0 1 1 0 1 1 1 1 0 0 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 55 COMPLEMENTS Step2: Add1s complement of Y to the X 1 0 1 0 1 0 0 + 0 1 1 1 1 0 0 1 0 0 1 0 0 0 0 = 16 SUM= There is an end carry! Sum is 1 less than the correct difference when an end carry occurs! Step3: Remove the end carry and add 1 (End-around carry) 0 0 1 0 0 0 0 +

ANSWER= 1 0 0 1 0 0 0 1 = 17 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 56 COMPLEMENTS Example 1.8 :Repeat Example 1.7, but this time using 1's complement. (a) Y X = 1000011 1010100 (67 84 = -17) Step1: Take the 1s complement of X 1 0 1 0 1 0 0 0 1 0 1 0 1 1 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 57 COMPLEMENTS Step2: Add1s complement of X to the Y 1 0 0 0 0 1 1 + 0 1 0 1 0 1 1 SUM=

1 1 0 1 1 1 0 There is NO end carry! Step3: To find the answer Y X = - (1s complement of SUM) 1 1 0 1 1 1 0 ANSWER= - 0 0 1 0 0 0 1 = 17 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 1.7 SIGNED BINARY NUMBERS 59 S I G N E D B I N A RY N U M B E R S To represent negative integers, we need a notation for negative values. It is customary to represent the sign with a bit placed in the left most position of the number since binary digits. The convention is to make the sign bit 0 for positive and 1 for negative. Example Signed-magnitude representation: 10001001 Signed-1s complement representation: 11110110 Signed-2s complement representation: 11110111 Table 1.3 lists all possible four-bit signed binary numbers in the three representations. Sunday, January 26,

2020 INTRODUCTION TO LOGIC DESIGN 60 S I G N E D B I N A RY N U M B E R S Sunday, January 26, 2020 Decimal Signed-2s Complement Signed-1s Complement Signed Magnitude +7 0111 0111 0111 +6 0110

0110 0110 +5 0101 0101 0101 +4 0100 0100 0100 +3 0011 0011 0011 +2 0010 0010

0010 +1 0001 0001 0001 +0 0000 0000 0000 -0 - 1111 1000 -1 1111 1110 1001

-2 1110 1101 1010 -3 1101 1100 1011 -4 1100 1011 1100 -5 1011 1010 1101 -6

1010 1001 1110 -7 1001 1000 1111 -8 1000 - - INTRODUCTION TO LOGIC DESIGN 61 S I G N E D B I N A RY N U M B E R S Arithmetic addition The addition of two numbers in the signed-magnitude system follows the rules of ordinary arithmetic. If the signs are the same; we add the two magnitudes and give the sum the common sign.

If the signs are different; we subtract the smaller magnitude from the larger and give the difference the sign of the larger magnitude. Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 62 S I G N E D B I N A RY N U M B E R S The addition of two signed binary numbers with negative numbers represented in signed-2's-complement form is obtained from the addition of the two numbers, including their sign bits. A carry out of the sign-bit position is discarded. Example: 0 0 0 0 0 1 1 0 - +1 3 + 0 0 0 0 1 1 0 1 +1 3 + 0 0 0 0 1 1 0 1 +1 9 + 7

0 0 0 1 0 0 1 1 Sunday, January 26, 2020 6 1 1 1 1 1 0 1 0 + 6 0 0 0 0 0 1 1 1 INTRODUCTION TO LOGIC DESIGN 63 S I G N E D B I N A RY N U M B E R S Example: + 6 0 0 0 0 0 1 1 0 - 6 1 1 1 1 1 0 1 0 - 1 3 +1 1 1 1 0 0 1 1 - 1 3 +1 1 1 1 0 0 1 1

- -19 7 1 1 1 1 1 0 0 1 Sunday, January 26, 2020 1 1 1 0 1 1 0 1 INTRODUCTION TO LOGIC DESIGN 64 S I G N E D B I N A RY N U M B E R S Arithmetic Subtraction In 2s-complement form: 1. Take the 2s complement of the subtrahend (including the sign bit) and add it to the minuend (including sign bit). 2. A carry out of sign-bit position is discarded. (+B) = ( (-B) = ( Sunday, January 26, 2020

INTRODUCTION TO LOGIC DESIGN 65 S I G N E D B I N A RY N U M B E R S Example: (-6) (-13) (11111010 11110011) - 6 1 1 1 1 1 0 1 0 +1 3 - 0 0 0 0 1 1 0 1 + 7 0 0 0 0 0 1 1 1 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 1.8 BINARY CODES 67 B I N A RY C O D E S BCD Code A number with k decimal digits will require 4k bits in BCD.

Decimal 396 is represented in BCD with 12bits as: 396 0 0 1 11 0 0 10 1 1 0 Each group of 4 bits representing one decimal digit. Sunday, January 26, 2020 D I G I TA L I N T E G RAT E D C I RC U I T D E S I G N 68 B I N A RY C O D E S Decimal Symbol BCD Digit 0 0000 the same as its equivalent 1 0001 binary number only when the 2 0010

number is between 0 and 9. 3 0011 4 0100 5 0101 1010 through 1111 are not 6 0110 used and have no meaning in 7 0111 BCD. 8 1000 9

1001 A decimal number in BCD is The binary combinations Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 69 B I N A RY C O D E S Example: Consider decimal 185 and its corresponding value in BCD and binary: (185) 1 0 ( 0 0 0 1 0 0 00 1 0 1 ) 1 = D B C (10111001 )2

Sunday, January 26, 2020 D I G I TA L I N T E G RAT E D C I RC U I T D E S I G N 70 B I N A RY C O D E S BCD Addition Consider the addition of two decimal digits in BCD Since each digit does not exceed 9 The sum cannot be greater than 9 + 9 + 1 = 19 the 1 in the sum being a previous carry Suppose we add the BCD digits as if they were binary numbers The binary sum will produce a result in the range from 0 to 19 In binary this will be from 0000 to 10011, but in BCD it is from 0000 to 1 1001 The first 1 being a carry and the next four bits being the BCD digit sum Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 71 B I N A RY C O D E S BCD Addition When binary sum is equal to or less than 1001 (without a carry)

When the binary sum is greater than or equal to 1010 The corresponding BCD digit is correct The result is an invalid BCD digit The addition of 6 = (0110)2 to the binary sum converts it to the correct digit and also produces a carry as required This is because the difference between a carry in the most significant bit position of the binary sum and a decimal carry. 16 10 = 6 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 72 B I N A RY C O D E S

BCD Addition Consider the following three addition of two decimal digits in 4 BCD 0 1 0 0 4 0 1 0 0 8 1 0 0 0 + 5 + 0 1 0 1 + 8 + 1 0 0 1 + 9 + 1 0 0 1 9 1 0 0 1 12 1 1 0 0

+ 0 1 1 0 17 1 0 0 0 1 + 0 1 1 0 1 0 0 1 0 1 0 1 1 1 Carry Sunday, January 26, 2020 Correct BCD digit sum (2) Carry Correct BCD digit sum (7) INTRODUCTION TO LOGIC DESIGN 73 B I N A RY C O D E S The addition of two n-digit unsigned BCD numbers follows the same procedure. Consider the addition of 184 + 576 = 760 in BCD 1

0 0 0 1 + 0 1 0 1 Binary Sum 0 1 1 1 Add 6 BCD Sum 0 1 1 1 Sunday, January 26, 2020 1 + 0 1 0 + 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0

0 + 0 1 + 0 1 1 0 1 0 1 1 1 0 0 0 0 1 8 4 +5 7 6 0 0 0 0 7 6 0 INTRODUCTION TO LOGIC DESIGN 74 B I N A RY C O D E S

The representation of signed decimal numbers in BCD is similar to the representation of signed numbers in binary. We can use either the familiar sign and magnitude system or the signed-complement system. The sign of a decimal number is usually represented with four bits to conform to the 4-bit code of the decimal digits. + with 0 0 0 0 and - with 1001 (BCD equivalent of 9) Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 75 B I N A RY C O D E S The signed-complement system can be either the 9s or the 10s complement. But the 10s complement is the one most often used. To obtain the 10s complement of a BCD number: First take the 9s complement 9s complement is calculated from the subtraction of each digit

from 9. Then add one to the least significant digit Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 76 B I N A RY C O D E S The procedures developed for the signed-2s complement system in the previous section apply also to the signed-10s complement system for decimal numbers. Addition is done by: adding all digits, including the sign digit and discarding the end carry. This assumes that all negative numbers are in 10s complement form. Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 77

B I N A RY C O D E S Consider the addition (+375) + (-240) = +135 Step1: Find the 10s complement of (-240) 9 10 0 - 2 7 4 0 6 0 Step 2: Add 10s complement of (-240) to 375 and discard the end carry. 0 375 +9 760 0 135 Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN

78 B I N A RY C O D E S Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 79 B I N A RY C O D E S Gray code: The output data of many physical systems produce quantities that are continuous. These data must be converted into digital form before they are applied to a digital system. Continuous or analog information is converted into digital form by means of an analog-to-digital converter. X(t) t Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 80 B I N A RY C O D E S

Gray code: It is convenient to use gray code to represent the digital data when it is converted from analog data. The advantage is that only bit in the code group changes in going from one number to the next. Error detection. Representation of data. Low power design. Sunday, January 26, 2020 analog Gray Code Decimal Equivalent 0000 0 0001

1 0011 2 0010 3 0110 4 0111 5 0101 6 0100 7 1100 8 1101 9

1111 10 1110 11 1010 12 1011 13 1001 14 1000 15 INTRODUCTION TO LOGIC DESIGN 81 B I N A RY C O D E S American Standard Code for Information Interchange (ASCII)

Character Code (Refer to Table 1.7) A popular code used to represent information sent as character-based data. It uses 7-bits to represent 128 characters: 94 Graphic printing characters. 34 Non-printing characters. Some non-printing characters are used for text format (e.g. BS = Backspace, CR = carriage return). Other non-printing characters are used for record marking and flow control (e.g. STX and ETX start and end text areas). Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 82 B I N A RY C O D E S Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 83 B I N A RY C O D E S Sunday, January 26,

2020 INTRODUCTION TO LOGIC DESIGN 84 B I N A RY C O D E S ASCII has some interesting properties: Digits 0 to 9 span Hexadecimal values 3016 to 3916 Upper case A-Z span 4116 to 5A16 Lower case a-z span 6116 to 7A16 Lower to upper case translation (and vice versa) occurs by flipping bit 6. Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 85 B I N A RY C O D E S Error-Detecting Code To detect errors in data communication and processing, an eighth bit is sometimes added to the ASCII character to indicate its parity. A parity bit is an extra bit included with a message to make the total number of 1's either even or odd.

Example: Consider the following two characters and their even and odd parity: With even parity With odd parity ASCII A = 1000001 ASCII T = 1010100 Sunday, January 26, 2020 01000001 11000001 11010100 01010100 INTRODUCTION TO LOGIC DESIGN 86 B I N A RY C O D E S Error-Detecting Code Redundancy (e.g. extra information), in the form of extra bits, can be incorporated into binary code words to detect and correct errors. A simple form of redundancy is parity, an extra bit appended onto the code word to make the number of 1s odd or even. Parity can detect all single-bit errors and some multiple-bit errors.

A code word has even parity if the number of 1s in the code word is even. A code word has odd parity if the number of 1s in the code word is odd. Example: Message A: 10001001 1 (even parity) Message B: 10001001 0 (odd parity) Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 1.9 BINARY STORAGE & REGISTERS 88 B I N A RY S T O RAG E & R E G I S T E R S Registers A binary cell is a device that possesses two stable states and is capable of storing one of the two states. 1/0 A register is a group of binary cells. A register with n cells can store any discrete quantity of information that contains n bits. 0 1 n cells Sunday, January 26, 2020

1 0 1 0 1 1 2n possible states INTRODUCTION TO LOGIC DESIGN 89 B I N A RY S T O RAG E & R E G I S T E R S A binary cell Two stable state Store one bit of information Examples: flip-flop circuits, ferrite cores, capacitor A register A group of binary cells AX in x86 CPU

Register Transfer A transfer of the information stored in one register to another. One of the major operations in digital system. An example in next slides. Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 90 B I N A RY S T O RAG E & R E G I S T E R S Memory CPU Control Unit Inputs: Keyboard, mouse, modem, microphone Sunday, January 26, 2020 Datapath Input / Output Outputs: CRT, LCD, modem, speakers Synchronous or Asynchronous?

INTRODUCTION TO LOGIC DESIGN 91 B I N A RY S T O RAG E & R E G I S T E R MEMORY UNIT J O H N 01001010 01001111 11001000 11001110 Memory Register PROCESSOR UNIT 8 cells 8 cells 8 cells 8 cells Processor Register 8 cells

Input Register INPUT UNIT J Keyboard O H Control N Figure 1.1 Transfer of information among register Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 92 B I N A RY S T O RAG E & R E G I S T E R S MEMORY UNIT SUM 0100100011 Operand 1 0011100001

Operand 2 0001000010 0001000010 R1 Digital logic circuits for binary addition 0011100001 0100100011 R3 R2 The other major component of a digital system Circuit elements to manipulate individual bits of information Load-store machine LD R1; LD R2; ADD R3, R2, R1; SD R3;

PROCESSOR UNIT Figure 1.2 Example of binary information processing Sunday, January 26, 2020 D I G I TA L I N T E G RAT E D C I RC U I T D E S I G N 1.10 BINARY LOGIC 94 B I N A RY LO G I C Definition of Binary Logic Binary logic consists of binary variables and a set of logical operations. The variables are designated by letters of the alphabet, such as A, B, C, x, y, z, etc., with each variable having two and only two distinct possible values: 1 and 0, Three basic logical operations: AND, OR, and NOT. Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 95 B I N A RY LO G I C 1. AND operation is represented by a dot () or by the absence of an operator.

Example: or X AND Y is equal to Z. Z =1 if only X = 1 and Y = 1; otherwise Z = 0. o X, Y and Z are binary variables and can be equal either to 1 or 0, nothing else. Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 96 B I N A RY LO G I C 2. OR operation is represented by a plus (+). Example: X OR Y is equal to Z.

Z =1 if X = 1 OR Y = 1 or if both X = 1 OR Y = 1. If both X = 0 OR Y = 0, then Z =0. Sunday, January 26, 2020 INTRODUCTION TO LOGIC DESIGN 97 B I N A RY LO G I C 3. NOT operation is represented by a prim () sometimes by an overbar () Example: or = Z NOT X is equal to Z. If X = 1, then Z =0, but if X = 0, then Z = 1. The NOT operation is also referred to as the complement operation, since it changes a 1 to 0 and a 0 to 1. Sunday, January 26,

2020 INTRODUCTION TO LOGIC DESIGN 98 B I N A RY LO G I C Truth tables, Boolean expressions and Logic Gates AND X 0 0 1 1 Y 0 1 0 1 OR Z 0 0 0 1 X 0 0 1

1 Y 0 1 0 1 = X Y NOT Z 0 1 1 1 X 1 0 =Z = Z Sunday, January 26, 2020 X

Y Z 0 1 Z X Z INTRODUCTION TO LOGIC DESIGN 99 B I N A RY LO G I C AND Sunday, January 26, 2020 OR INTRODUCTION TO LOGIC DESIGN 10 0 B I N A RY LO G I C Example of binary signals Volts 3

Signal range for logic 1 3 2 1 Logic 1 2 Transition occurs between these limits undefined Signal range for logic 0 0 Sunday, January 26, 2020 1 Logic 0 0 INTRODUCTION TO LOGIC DESIGN 10 1

B I N A RY LO G I C Graphic Symbols and Input-Output Signals for Logic gates: X Y X Y Z (a) two input AND gate (b) two input OR gate 0 1 1 0 0 0 0 1 1

0 0 0 1 0 0 X+Y0 1 1 1 0 X 1 0 0 0 X Y XY Sunday, January 26, 2020

X Z 1 Z (c) NOT gate or Inverter INTRODUCTION TO LOGIC DESIGN 10 2 B I N A RY LO G I C Graphic Symbols and Input-Output Signals for many input logic gates: A B C F=ABC (a) three input AND gate Sunday, January 26, 2020

A B C D F=A+B+C+D (b) four input OR gate INTRODUCTION TO LOGIC DESIGN

Recently Viewed Presentations

  • Tour du monde - Free

    Tour du monde - Free

    Title: Tour du monde Created Date: 1/11/2007 2:14:49 PM Document presentation format: Diavoorstelling Other titles: Arial Calibri Times New Roman Thème Office Dia 1 Dia 2 Dia 3 Dia 4 Dia 5 Dia 6 Dia 7 Dia 8 Dia 9...
  • Are Low Carbohydrate Diets Anything More Than A Fad?

    Are Low Carbohydrate Diets Anything More Than A Fad?

    Low Carbohydrate Diets CJ Segal-Isaacson, EdD, RD High Protein Diets Manny Noakes, PhD Low Fat Diets Keith Ayoob, EdD, RD Focus of Each Talk: Define Diet Present The Evidence for It's Weight Loss Effects Present The Evidence for Cardiovascular and...
  • Amoeba, Paramecium, Euglena, and Volvox

    Amoeba, Paramecium, Euglena, and Volvox

    Euglena (15 - 500µm) Flagella. Pellicle. Stigma/eyespot. Chloroplasts. Volvox (can be large enough to be seen w/ the naked eye) Flagella. Cytoplasm. Chloroplasts. Live in colonies. Moves by stretching its cytoplasm into finger like extensions or pseudopodia.
  • History of Metals

    History of Metals

    The hard steel forms the sword's outer shell and deadly blade, while the tough steel serves as the sword's core. University of Toronto chemistry and physics professor R.J. Dwayne Miller has demonstrated that gold can get harder, not softer, when...
  • Another look at the 1969 Ozernoi tsunami, and neotectonics of ...

    Another look at the 1969 Ozernoi tsunami, and neotectonics of ...

    UWa-ESS Other titles: Times Comic Sans MS Times New Roman MS Pゴシック Blank Using tsunami deposits to determine earthquake and tsunami recurrence intervals: opportunities and challenges Slide 2 Slide 3 intro intro Slide 6 Slide 7 Copalis deposit MaryAnn coring...
  • How to analyze a text

    How to analyze a text

    He/she adopts (or equivalent verb) a(n) (adjective describing the attitude/feeling conveyed by the writer) tone in order to (verb phrase describing what the writer wants readers to do/think)in his/her (intended audience). NOTE: This would be followed by your thesis.
  • Scott Air Force Base, Illinois USTRANSCOM Agenda July

    Scott Air Force Base, Illinois USTRANSCOM Agenda July

    Introductions Major General Carlos D. (Butch) Pair, Rear Admiral Marc Purcell, and Senior USTRANSCOM staff Ted Rybeck, Benchmarking Partners and Global Benchmarking Center for Security and Trade, Committee Chairman and Subset of the Committee
  • Communication and Optimal Resolution (CANDOR) Toolkit Module 6:

    Communication and Optimal Resolution (CANDOR) Toolkit Module 6:

    Second-victims can have specific concerns and symptoms following a CANDOR event. For example, second-victims might worry about the patient, themselves, their peers, and the future. The second-victim is often concerned about whether or not the patient and family are okay...