Créer une présentation
Télécharger la présentation

Télécharger la présentation
## Positional Number System

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Positional Number System**• A number is represented by a string of digits where each digit position has an associated weight. • The weight is based on the radix of the number system. • Some common radices: • Decimal. • Binary. • Hexadecimal.**Notation**• Decimal. • W = 12310 = 123d = 123 • Binary. • X = 102 = 10b • Hexadecimal. • Z = 0A316 = 0A3h = 0xA3**Radix 10 Numbers**• Decimal. • Here the base or radix is 10. • Digits used. • 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.**Radix 2 Numbers**• Binary. • Here the base or radix is 2. • Digits used: • 0, and 1.**Radix 16 Numbers**• Hexadecimal. • Here the base or radix is 16. • Digits used: • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F.**Binary to Octal, Octal to Binary Conversions**• Substitute a three binary digit string with an octal digit.**Binary to Hexadecimal, Hexadecimal to Binary Conversions**• Substitute a four binary digit string, called a nibble, with a hexadecimal digit.**Simple Conversions**• The conversions just described are simple due to the fact that the radices are all powers of two. • 21 = binary. • 8 = 23 = octal. • 16 = 24 = hexadecimal.**Radix r to Decimal Conversions**• Ex: • 1012 = 1X22 + 0X21 + 1X20 = 5 • 4325 = 4X52 + 3X51 + 2X50 = 117 • 758 = 7X81 + 5X80 = 61 • 1A16 = 1X161 + 10X160 = 26**Decimal to Radix r Conversions**• AI / r = (anr+ an-1)r+…+ a1 as the quotient and a0 as the remainder. • Divide the result repeatedly until a zero quotients is reached. • The remainders of the consecutive divisions form the numbers in base r.**Decimal to Radix r Conversions**• Convert 26 decimal to binary. • Quotient Remainder • 26/2 13 0 LSB • 13/2 6 1 • 6/2 3 0 • 3/2 1 1 • 1/2 0 1 MSB • 26 = 110102**Decimal to Radix r Conversions**• AF * r = r -1(a-1+ r –1(a-2+…)) * r =a-1 + r –1(a-2+…) • Multiplying the fractional part by r results in a mixed number. • The integral part of this mixed number is the conversion’s required digit.**Decimal to Radix r Conversions**• This algorithm is not guaranteed to terminate, since a finite fraction in one number system may correspond to an infinite one in another number system.**Decimal to Radix r Conversions**• Convert 0.75 decimal to binary. Mixed no. Integral part • 0.75 X 2 1.5 1 MSB • 0.5 X 2 1.0 1 LSB • 0.75 = 0.112**Negative Number Representation**• Signed magnitude. • Complement number system: • Radix-complement. • Diminished radix-complement.**Signed Magnitude Representation**• A is a n digit number, where an-1 is the sign, and the remaining n–1 bits are the magnitude. • an-1 • Positive if equal to 0. • Negative if equal to 1 or r -1 for r greater than 2. • Range is – (2n-1 - 1) to (2n-1 - 1). • Two zero representations: • 00…02 = +0 • 10…02 = -0**Addition and Subtraction**• Check sign. • If equal. • Add magnitudes and give the result the same sign. • If different. • Compare magnitudes. • Subtract the smaller from the larger and give the result the sign of the larger.**Complement Representation**• Negation is accomplished by taking the complement of the numbers. • Two numbers in complement representation may be added or subtracted directly without sign and magnitude checks. • Numbers in complement representation may be sign extended.**Diminished Radix Complement**• Also known as: • One’s complement (r = 2). • Nine’s complement (r = 10). • 1’s Complement of A is B = (2n - 1) – A • n is the numbers of digits in A.**Diminished Radix Complement**• The easy way to get the one’s complement of a binary number is by complementing each individual digit of that number. • Ex: • A = 111000102 • B = One’s complement of A • B = 000111012**Diminished Radix Complement**• Range is – (2n-1 - 1) to (2n-1 - 1). • Two zero representations: • 00…02 = +0 • 11…12 = -0**Radix Complement**• Also known as: • Two’s complement (r = 2). • Ten’s complement (r = 10). • 2’s Complement of A = 2n – A • n is the numbers of digits in A. • B = 2’s Complement of A = 2n – A • B = 2n – A –1 + 1 • B = (2n – 1 – A) + 1**Radix Complement**• Ex: • A = 111000102 • B = Two’s complement of A • B = 000111012 + 12 • B = 000111102**Radix Complement**• The easy way to get the two’s complement of a binary number is to search that number starting with the LSB until you find the rightmost one digit. Leave that digit and all other digits to the right of it unchanged. Complement all digits to the left of that one digit. • Ex: • A = 111010002 • B = Two’s complement of A • B = 000110002**Radix Complement**• Range is – 2n-1 to 2n-1 - 1. • One zero representation: • 00…02 = 0**Two’s Complement Addition**• Simply add the numbers ignoring any carries beyond the MSB. • The result will always be correct as long as the range of the number system is not exceeded. • Example:**Overflow**• Overflow occurs when the result of an addition exceeds the range of the number system. • So, will overflow occur when numbers with different signs are added? • Detection of an overflow: • Compare the carries into and out of the sign bit, if they are different an overflow has occurred. • The sign of the addends are the same and they differ from the sums sign. • Ex: • - 4 + ( -5 ) = -9 • 4 + 5 = 9**Two’s Complement Subtraction**• Subtraction is performed by negating the subtrahend by taking its two’s complement, then adding it to the minuend using normal two’s complement addition rules. • Ex:**One’s Complement Addition**• Perform addition; If there is a carry out of the sign bit, add one to the result. • This is called the end-around carry. • Ex: • - 3 + ( -4 ) = -7**One’s Complement Subtraction**• Subtraction is performed by negating the subtrahend by taking its one’s complement, then adding it to the minuend using normal one’s complement addition rules. • Ex: • - 3 – ( -4 ) = 1**Boolean Algebra**• 1854, George Boole created a two valued algebraic system which is now called Boolean algebra. • 1938, Claude Shannon adapted Boolean algebra to analyze and describe the behavior of circuits built with relays. This adaptation is called switching algebra.**Switching Algebra**• In switching algebra the condition of a logic signal is represented by symbolic variables, such as x, y, and/or z, and these variables can only have two values, 0 or 1. • Two possible conventions: • Positive Logic. • Where LOW = 0 and HIGH = 1. • Negative Logic. • Where LOW = 1 and HIGH =0.**Axioms**• The axioms or postulates of a mathematical system are a minimum set of basic definitions that are assumed to be true, and from which all other information about the system can be derived. • The axioms stated below embody the “digital abstraction” by formally stating that X can take on only one of two values. • (A1) X = 0 if X 1 • (A1’) X = 1 if X 0**Axioms**• Complement. • (A2) If X = 0, then X’ = 1. • (A2’) If X = 1, then X’ = 0. • Notation.**Axioms**• Logical multiplication ( ). • (A3) 0 0 = 0 • (A4) 1 1 = 1 • (A5) 0 1 = 1 0 = 0 • Logical addition ( + ). • (A3’) 1 + 1 = 1 • (A4’) 0 + 0 = 0 • (A5’) 1 + 0 = 0 + 1 = 1**Precedence**• By convention, the precedence of operations in a logic expression is the following: • Parentheses. • Complement. • Multiplication. • Addition.**Theorems**• Theorems are statements, known to be always true, that are used to manipulate algebraic expressions to allow simpler analysis or more efficient synthesis of circuits. • Identities. • (T1) X + 0 = X • (T1’) X 1 = X**Theorems**• Null elements. • (T2) X + 1 = 1 • (T2’) X 0 = 0 • Idempotency. • (T3) X + X = X • (T3’) X X = X**Theorems**• Involution. • (T4) (X’)’ = X • Complements. • (T5) X + X’ = 1 • (T5’) X X’ = 0**Theorems**• Proofs. • Theorems T1 through T5’ can be proved by using a technique called perfect induction. • Since a switching variable can take on only two different values, 0 or 1 by Axiom A1, we can prove a theorem involving a single variable by showing that the theorem is true for both X=0 and X=1.**Theorems**• Proof of theorem (T2). X + 1 = 1 • Two cases: • X = 0 • 0 + 1 = 1 is true according to A5’. • X = 1 • 1 + 1 = 1 is true according to A3’.**Theorems**• Commutativity. • (T6) X + Y = Y + X • (T6’) X Y = Y X • Associativity. • (T7) (X + Y) + Z = X + (Y + Z) • (T7’) (X Y) Z = X (Y Z) • Distributivity. • (T8) X Y + X Z = X (Y + Z) • (T8’) (X + Y) (X + Z) = X + Y Z**Theorems**• Covering (absorption). • (T9) X + X Y = X • (T9’) X (X + Y) = X • Combining. • (T10) X Y + X Y’ = X • (T10’) (X + Y) (X + Y’) = X**Theorems**• Consensus. • (T11) X Y + X’ Z + Y Z = X Y + X’ Z • (T11’) (X + Y) (X’ + Z) (Y + Z) = (X + Y) (X’ + Z) • Comments. • T9 and T10 are used in minimization of logic functions. • T10 used to eliminate timing hazards and to find prime implicants (iterative consensus method).**Theorems**• Proof of theorem (T9). X + X Y = X (T1’) X 1 + X Y = X (T8) X (1 + Y) = X (T2) X 1 = X (T1’) X = X • Proof of theorem (T10). X Y + X Y’ = X (T8) X (Y + Y’) = X (T5) X 1 = X (T1’) X = X