Chapter 1: Digital Systems and Binary Numbers + 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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. + Binary values are represented by values or ranges of values of physical quantitiesNumber Representation + Decimal number sf (yyy... a J t-__. becimat point L_. Power [— Base or radix > [L +10, +10%a, +10°a, +10, +10'a, +10°a, +10 a, +1074 +104, +L Example: 7,329 =710° +310? +210! +9 x10" + General form of base-r system arta +L tar tacrtatay +a, +h +a oF Coefficient: a,=0 to r— 1Binary Numbers Example: Base-2 number (1010.11), = (26.75), = 1x24 +1290 27 +12! £02" 1x24 1x2? Example: Base-5 number (4021.2), =4x5° +05? +2x5' 415° 42x51 =(S115)io Example: Base-8 number (127.4), = 1x8? +28? +18! +78" 4x87 = (87.5)j5 Example: Base-16 number (B65F),, =11x16* +616? +5x16' +15x16° = (46,687),Binary Numbers Example: Base-2 number (110101), =32+16+4+1=(53),, Special Powers of 2 = 210 (1024) is Kilo, denoted "K" = 220 (1,048,576) is Mega, denoted "M" = 230 (1,073, 741,824)is Giga, denoted "G" Powers of two <=> Table 1.1Table 1.1 Powers of Two n 2 n 2 n 2 0 1 8 256 16 65,536 1 2 9 512 17 131,072 2 4 10 1,024 18 262,144, 5 8 i 2,048, 19 524,288 4 16 12 4,096 20 1,048,576 5 32 13 8.192 21 2,097,152 6 64 14 16,384 22 4,194,304 f 128 15 32,768 23 8,388,608 Arithmetic operation Arithmetic operations with numbers in base r follow the same rules as decimal numbers,Binary Arithmetic Single Bit Addition with Carry Multiple Bit Addition Single Bit Subtraction with Borrow Multiple Bit Subtraction Multiplication BCD AdditionBinary Arithmetic + Addition + Subtraction Augend: 101101 Minuend: 101101 Addend: +100111 Subtrahend: —100111 Sum: 1010100 Difference: 000110 + Multiplication Multiplicand 1011 ip! x 101 Partial Products 1011 0000 - 1011 -- Product 110111Number-Base Conversions Name Radix Digits Binary 2 0,1 Octal 8 0,1,2,3,4,5,6,7 Decimal 10 0,1,2,3,4,5,6,7,8,9 Hexadecimal 16 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F = The six letters (in addition to the 10 integers) in hexadecimal represent: 10, 11, 12, 13, 14, and 15, respectively.Number-Base Conversions Example1.1 Convert decimal 41 to binary. The process is continued until the integer quotient becomes 0. Integer Quotient Remainder Coefficient 41/2 = 20 a 4 ani 20/2 = 10 + 0 a,=0 10/2 = 5 + 0 a,=0 5/2 2 + 4 a1 2/2 1 + 0 a. 0 5 1 0 + ===> (4D)io = (asasasarayay)» = (101001).Number-Base Conversions 4 The arithmetic process can be manipulated more conveniently as follows: Integer Remainder 41 20 1 10 i} 5 0 2 1 1 0 0 1 101001 = answerNumber-Base Conversions Example 1.2 Convert decimal 153 to octal. The required base ris 8. Integer Remainder 153 19 2 3 0 2 =(231)s Example1.3 Convert (0.6875)1o to binary. The process is continued until the fraction becomes 0 or until the number of digits has sufficient accuracy.Number-Base Conversions Example1.3 Integer Fraction Coefficient 0.6875 x 2= 1 + 0.3750 a, = 1 0.3750 x 2= 0 0.7500 ay = 0 0.7500 x 2= 1 fe 0.5000 1 0.5000 x 2= 1 + 0.0000 1 S==> — [0.6875)0 = (O.ayazasay)2 = O.1011D)2 # To convert a decimal fraction to a number expressed in base r, a similar procedure is used. However, multiplication is by rinstead of 2, and the coefficients found from the integers may range in value from 0 to r—1 instead of 0 and 1.Example1.4 Convert (0.513),9 to octal. 0.513 x 8 = 4,104 0.104 x 8 = 0.832 0.832 * 8 = 6.656 0.656 x 8 = 5.248 0.248 x 8 = 1.984 0.984 * 8 = 7.872 4 From Examples 1.1 and 1.3: 4 From Examples 1.2 and 1.4: Number-Base Conversions ===> [05130 = 0.406517 )s| (41.6875)1o = (101001.1011), (153.513)4o = (231.406517),Octal and Hexadecimal Numbers # Numbers with different bases: Table 1.2. Table 1.2 Numbers with Different Bases Decimal Binary Oct Hexadecimal (base 10) (base 2) (base 8) (base 16) 00 0000 00 0 oa 0001 ol 1 02 0010 02 2 03 0011 03 3 4 0100 4 4 05 o101 05 5 06 ono 06 6 o7 ou 07 7 08. 1000 10 8 09. 1001 ul 9 10 1010 12 A "1 toll 1B B 12 1100 14 c B 1101 Is D 4 110 16 E 15 nn 7 FEOctal and Hexadecimal Numbers + Conversion from binary to octal can be done by positioning the binary number into groups of three digits each, starting from the binary point and proceeding to the left and to the right. 10 110 001 101 O11 : 111 100 000-110)» = (26153.7406)s 2 6 1 5 3 7 4 0 6 + Conversion from binary to hexadecimal is similar, except that the binary number is divided into groups of four digits: (10-1100 0110 1011 ‘ 1111 0010) 2 = (2C6B.F2)i6| a c 6 B - 2 4 Conversion from octal or hexadecimal to binary is done by reversing the preceding procedure. (673.124)s=(110 11 O1L. = 001-010-100) 6 7 3 1 2 4 (306.D);s= (011 0000 010 ~~~ ‘11012 s 0 6 DComplements 4% There are two types of complements for each base-r system: the radix complement and diminished radix complement. ===> the r's complementand the second as the (r— 1)'s complement. [Diminished Radix Complement (Given a number Vin case r having n digits, the (r— 1 )’s complement of Vis defined] as (r” — 1) - N. For decimal numbers, r= 10 and r— 1 = 9, so the 9's complement of M iis (10" — 1) —N. Example: The 9's complement of 546700 is 999999 — 546700 = 453299. The 9's complement of 012398 is 999999 — 012398 = 987601. + For binary numbers, r= 2 and r— 1 = 1, so the 1's complementof Nis (2"— 1) - N. Example: The 1's complement of 1011000 is 0100111 The 1's complement of 0101101 is 1010010}Complements i Radix Complement The r’s complement of an n-digit number N in base r is defined as r” - N for N#0 and as 0 for N = 0. Comparing with the (r- 1)'s complement, we note that the r's. complementis obtained by adding 1 to the (r~ 1)'s complement, since 1” — N= [(r? — 1)-N)+1. Example: Base-10 The 10's complement of 012398 is 987602 The 10's complement of 246700 is 753300 Example: Base-10 The 2's complement of 1101100 is 0010100 The 2's complementof 0110111 is 1001001Subtraction with Complements The subtraction of two n-digit unsigned numbers M — N in base rcan be done as follows: Complements 1. ‘Add the minuend © to the 7’s complement of the subtrahend N. Mathematically, 11] +("-N)=M-N+?". If.M = N, the sum will produce and end carry 7”, which can be discarded; what is left is the result M—N. IfM <_N, the sum does not produce an end carry and is equal to 7” — (NM) which is the 7's complement of (N — M). To obtain the answer in a familiar form, take the r’s complement of the sum and place a negative sign in front.Complements Example 1.5 Using 10's complement, subtract 72532 — 3250. M= 72532 10's complement of N= +96750 Sum= 169282 Discard end carry 10°= 100000 Answer= 69282 Example 1.6 Using 10's complement, subtract 3250 - 72532 M= 03250 10's complement of N= 427468 Sum = 30718 ===> There is no end carry. ===> Therefore, the answeris— (10's complementof 30718) = - 69282Complements Example 1.7 Given the two binary numbers X = 1010100 and Y = 1000011, perform the subtraction (a) X-Y and (b) Y— X by using 2's complement. (a) X= 1010100 2's complement of Y= +0111101 | Sum= 10010001 Discard end carry 2’= —10000000 Answer.X-Y= 0010001 Y= 1000011 2's complement of X= + 0101100) Sum = 01111 There is no end carry. Therefore, the answeris Y¥-X =~ (2's complement of 1101111) = - 0010001Complements 4 Subtraction of unsigned numbers can also be done by means of the (r- 1)'s complement. Remember that the (r- 1)'s complementis one less then the ’s complement Example 1.8 Repeat Example 1.7, but this time using 1's complement (a) X—¥= 1010100 — 1000011 X= 1010100 I's complement of ¥= + 0111100 Sum= 10010000 End-around cary= 4. Answer. ¥—Y= 0010001 (b)¥— X= 1000011 — 1010100 Y= 1000011 I's complement of Y= +0101011 Sum = 1101110) There is no end carry, Therefore, the answeris Y-X=- (1's complement of 1101110) = - 0010001Signed Binary Numbers # To represent negative integers, we need a notation for negative values. * It is customary to represent the sign with a bit placed in the leftmost position of the number. 4 The convention is to make the sign bit 0 for positive and 1 for negative. Example: ned-magnitude representation: 10001001 igned-1's complement representation: ‘11110110 igned-2's-complement representation: 11110111 + Table 3 lists all possible four-bit signed binary numbers in the three representations.Signed Binary Numbers Table 1.3 Signed Binary Numbers Signed-2's Signed-1's Signed Decimal Complement Complement _ Magnitude +7 om om om +6 O10 O110 O10 +5 o101 o101 101 +4 0100 0100 0100 +3 ool ool oon +2 0010 0010 0010 +1 0001 0001 0001 +0 ‘0000 0000 0000 _( — uit 1000 = mn 10 1001 = 1110 M101 1010 hor 1100 1011 1100 1011 1100 loi 1010 Ho 1010 1001 110 1001 1000 un 1000 — -Signed Binary Numbers 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 if the larger magnitude. & The addition of two signed binary numbers with negative numbers represented in signed-2's-complementform is obtained from the addition of the two numbers, including their sign bits. * Acarry out of the sign-bit position is discarded Exampl + 6 00000110 =6 11111010 +13 00001101 +13 00001101 +19 00010011 +7 00000111 + 6 00000110 11111010 =13 LIL10011 11110011 —7 11111001 11101101Binary Codes IIBCD Code Anumber with k decimal digits will Table 1.4 require 4k bits in BCD. Decimal 396 Binary-Coded Decimal (BCD) is represented in BCD with 12bits as —§£_[_—— _ 0011 1001 0110, with each group of Decimal BCD 4 bits representing one decimal digit Symbol Digit A decimal number in BCD is the 0 0000 sameas its equivalent binary number only when the numberis ; ee between 0 and 9. ABCD number 3 ool greater than 10 looks different from 4 0100 its equivalent binary number, even 5 0101 though both contain 1's and 0's. 6 atid Moreover, the binary combinations 7 oli 1010 through 1111 are not used and 8 1000 have no meaning in BCD. 9 1001Signed Binary Numbers WiArithmetic Subtraction # In 2’s-complement form: 1, Take the 2’s complementof the subtrahend (including the sign bit) and add it to the minuend (including sign bit). 2. Acarry out of sign-bit position is discarded. (+4) —-(+B) = (+4) +(-B) (£4) -(-B) = (44) + (+B) Example: (-6)-( 13) ===> (11111010 - 11110011) ===> (11111010 + 00001101) ===> 00000111 (+ 7)Binary Codes Example: Consider decimal 185 and its corresponding value in BCD and binary: ===> [18510 = 001 1000 0101) peo = (10111001) 2 HIBCD Addition 4 0100 4 0100 8 1000 +5 +0101 +8 +1000 +9 +1001 9 1001 12 1100 17 10001 +0110 +0110 10010 10111Binary Codes Example: Consider the addition of 184 + 576 = 760 in BCD: BCD Binary sum Add 6 BCD sum 1 0001 +0101 oll Ol 1 1000 oul 10000 110 o110 0100 o10 1010 o110 0000 i Decimal Arithmetic 0 375 +9 760 0 135Binary Codes I Other Decimal Codes Table 1.5 Four Different Binary Codes for the Decimal Digits Decimal Digit Unused bit combi- nations BcD 8421 0000 0001 0010 0011 0100 0101 oo oul 1000 1001 1010 loll 1100 1101 1110 ML 2421 0000 0001 0010 ool 0100 1011 1100 Hol 110 mun 0101 ono out 1000 1001 1010 Excess-3 ool 0100 0101 ou out 1000 1001 1010 1011 1100 0000 ‘0001 0010 nol 110 Mu 0000 oul o110 o101 0100 1011 1010 001 1000 it 0001 0010 0011 1100 Hol 1110Binary Codes Table 1.6 MGray Code capetie Gray Decimal Code Equivalent 0000 0 0001 1 011 2 0010 3 O10 4 oll 5 0101 6 0100 7 1100 8 1101 9 Wi 10 1110 a 1010 12 1011 13 1001 14 1000 15Binary Codes HBASCII Character Code Table 1.7 ‘American Standard Code for Information interchange (ASCII) babsb2b; 0000 0001 0010 0011 0100 o101 ono oun 1000 1001 1010 101 1100 1101 110 uu 000 NUL SOH STX ETX EOT ENQ ACK BEL BS HT LE FF cR so sl 001 DLE Der pez pe3 pes NAK SYN ETB CAN EM SUB ESC Fs cs RS us sp on 100 @ A B c D E F G 101 P Q R 110 bybebs 010 mWBinary Codes HBASCII Character Code Control characters cr so sl sp Null Start of heading Start of text End of text End of transmission Enquiry Acknowledge Bell Backspace Horizontal tab Line feed Vertical tab Form feed Carriage return Shift out Shift in Space DLE pel bc2 DC3 pea NAK SYN ETB CAN RS US DEL Data-link escape Device control | Device control 2 Device control 3 Device control 4 Negative acknowle Synchronous idle End-of-transmission block Cancel End of medium Substitute Escape File separator Group separator Record separator Unit separator DeleteASCII Character Codes + American Standard Code for Information Interchange (Refer to Table 1.7) + A popular code used to represent information sent as character-based data. + Ituses 7-bits to represent: — 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).ASCII Properties ASCII has some interesting properties: = Digits 0 to 9 span Hexadecimal values 301, = Upper case A-Z span 41,, to 5Aj, . = Lower case a -zspan 61,, to 7Aj.. ° Lower to upper case translation (and vice versa) occurs by flipping bit 6. = Delete (DEL) is all bits set, punched paper tape was used to store messages. = Punching all holes in a row erased a mistake! to 39,,. a carryover from whenBinary Codes MlError-Detecting Code 4 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 01000001 11000001 ASCII T = 1010100 11010100 01010100Binary Codes HError-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. Asimple form of redundancy is parity, an extra bit appended onto the code word to make the number of 1’s 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 1’s in the code word is even. A code word has odd parity if the number of 1’s in the code word is odd.Binary Storage and Registers HiRegisters + Abinary cellis a device that possesses two stable states and is capable of storing one of the two states. + Aregisteris a group of binary cells. A register with n cells can store any discrete quantity of information that contains n bits. ncells >> 2"possible states + Abinary cell — two stable state = store one bit of information — examples: flip-flop circuits, ferrite cores, capacitor + Aregister — 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Transfer of information ‘MEMORY UNIT zi oO HN Memory ‘oroTOIdOTOOTTTiTIOOTOOGLIOOTIIO] Remycy PROCESSOR UNIT Processor Seats fof Sexi Jef Beets Jef Seats ] ROSSter INPUT UNIT Input Bells | Register CONTROL oO Keyboard eI @F Fig, 1-1 Transfer of information with registers+ The other major component of a digital system — circuit elements to manipulate individual bits of information MEMORY UNIT Sum ‘dovv0v0000 Operand 1 ort Io000L operand? door 000010 ‘O00 100001 0]RI Digital tog ecuistor |—=fo1 001 0001 1]R5| binary addition O01 1100007] Ro PROCESSOR UNIT Fe 1a Esamole of binary information procoadlaeary Logic Il 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, There are three basic logical operations: AND, OR, and NOT. 1. AND: This operation is represented by a dot or by the absence of an operator. For example, x + y=2 or ay =z is tead “x AND y is equal to 2,” The logical operation 1; otherwise 2 = 0. AND is interpreted to mean that z= 1 if only x= 1 and (Remember that x, and nothing else.) |2. OR: This operation is represented by a plus sign, For example, x + y= is read “xv OR y is equal to 2,” meaning that2= 1 if If both x= 0 and y= 0, thenz=0. and z are binary variables and can be equal either to 1 or 0, 1 ory=1 or if both x andy 3. NOT: This operation is represented by a prime (sometimes by an overbar). For example, x'=z (or ¥ =z) is read “not x is equal to z,” meaning that z is what zis , The NOT operation| is also referred to as the complement operation, since it changes a 1 to 0 and a0 to 1 not. In other words, ifx= 1, then z |, but ifr =0, then z=Binary Logic @ The truth tables for AND, OR, and NOT are given in Table 1.8. Table 1.8 Truth Tables of Logical Operations AND OR xX yi) xey x y xty 0 0 0 0 0 0 01 0 0 1 1 1 0 0 10 1 11 dL 11 1Binary Logic I Logic gates # Example of binary signals Volts A f Transition occurs between these limit Ss Signal range for logic 1 Signal range for logic 0Binary Logic I Logic gates Graphic Symbols and Input-Output Signals for Logic gates: — gexey jo ’ eae — > y+—4 ¥ (a) Two-input AND gate (b) Two-input OR gate (c) NOT gate or inverter Fig. 1.4 Symbols for digital logic circuits x 0 1 1 0 0 y Fig. 1.5 Input-Output signals 1—> anp-x- y 0 0 1 0 0 for gates . OR:x+y of 1 THILO NOT: x’ 1 0 0 1 1Binary Logic I Logic gates Graphic Symbols and Input-Output Signals for Logic gates: 7, . A J yeaa B G=A+Bt+C+D — Cc D Am (a) Three-input AND gate (b) Four-input OR gate Fig. 1.6 Gates with multiple inputsNumber-Base ConversionsComplementsComplementsSignal Example — Physical Quantity: Voltage OUTPUT INPUT SE 5.0 HIGH MW GG 40 HIGH 3.0 ‘Threshold 2.0 Region 1.0 LOW YY 00 LOW VoltsSignal Examples Over Time Time Analog value & time Digital Asynchronous [| Synchronous s_| yogic aa) SIE. Cola aT Col time Discrete in value &A Digital Computer Example Control ere Datapath Inputs: Keyboard, t y Outputs: CRT, mouse, modem, LCD, modem, , microphone Input/Output speakers , Synchronous or Asynchronous?ary Codes for Decimal Digits = There are over 8,000 ways that you can chose 10 elements from the 16 binary numbers of 4 bits. A few are useful: Decimal 8,4,2,1 Excess3 | 8,4,-2,-1 | Gray 0 0000 0011 0000 0000 1 0001 0100 O11 0100 2 0010 0101 0110 0101 3 0011 110 0101 om 4 0100 O11 0100 0110 5 0101 1000 1011 0010 6 ono 1001 1010 0011 7 om 1010 1001 0001 8 1000 1011 1000 1001 9 1001 1100 Wit 1000UNICODE UNICODE extends ASCII to 65,536 universal characters codes — For encoding characters in world languages — Available in many modern applications — 2 byte (16-bit) code words — See Reading Supplement -— Unicode on the Companion Website http:/Awww.prenhall.com/manoNegative Numbers + Complements — 1's complements (2"-)-N — 2's complements 2"- — Subtraction = addition with the 2's complement — Signed binary numbers » signed-magnitude, signed 1's complement, and signed 2's complement.M-N + M+ the 2’s complement of N — M+(2"-N)=M-N#2" + IfM2N — Produce an end carry, 2", which is discarded * IfM 9) +0110 soadd6 1 0011 leaving 3 + cy 0001 | 0011 Final answer (two digits) = If the digit sum is > 9, add one to the next significant digit carr’BCD Addition Example + Add 2905gcp to 1897Bcp showing carries and digit corrections. 0 0001 1000 1001 0111 +0010 1001 0000 0101Error-Detection Codes Redundancy (e.g. extra information), in the form of extra bits, can be incorporated into binary code words to detect and correct errors. Asimple form of redundancy is parity, an extra bit appended onto the code word to make the number of 1’s 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 1’s in the code word is even. A code word has odd parity if the number of 1’s in the code word is odd.4-Bit Parity Code Example + Fill in the even and odd parity bits: Even Parity Odd Parity | Message - Parity Message - Parity 000 - 000 _ 001. 001 _ 010 - 010 _ O11. O11 _ 100 - 100 _ 101. 101 _ 110. 110 _ 111 - 11 _ + The codeword "1111" has even parity and the codeword "1110" has odd parity. Both can be used to represent 3- bit data.