ECE251 Student Note PDF

Preview

Summary

Download ECE251 Student Note PDF

Description

DIGITAL DESIGN ECE 251 Notes

Dr. Jacob Savir New Jersey Institute of Technology

Editor: Andrzej Strycharz

 1 

Digital logic circuits Number representation: bit – binary digit, either 0 or 1. Review of base 10 representation:

…

0 1 2 digits in base 10

…

9 10 11 12 19 20 …

Count:

 2 

376 = 3×102 + 7×101 + 6×100 weights – progressive powers of 10

In binary: Count:

0 digits in base 2 1 10 11 100 101 110 111 1000

These numbers correspond to zero to eight in the decimal system.

 3 

A sequence of 0’s and 1’s represent an integer in the binary system. (bn bn-1 bn-2…b1 b0)2=(bn×2n + bn-1×2n-1 +…+ b1×2 + b0)10

Example of converting from binary to decimal (101100101)2=(x)10 Number 1 0 1 1 0 0 1 0 1 × × × × × × × × × += Weights 256 128 64 32 16 8 4 2 1

= 256 + 64 + 32 + 4 + 1 = (357)10 Rule: To find the decimal equivalent add the weights where the bit is one.

 4 

Example of converting from decimal to binary 357 178 89 44 22 11 5 2 1 0

1 0 1 0 remainders of progressive 0 divisions by 2 1 1 0 1

quotient of division by 2

(357)10 = (101100101)2 Rule: Progressively divide by 2, recording the quotient and remainder. When a quotient of 0 is reached – you are finished. The remainder read upward is the binary equivalent of the decimal number.

 5 

General number system base r numbers: digits used: {0, 1, 2,…,r-1}

(dndn-1...d0.d-1d-2...d-m)r = Integer part

Fractional part

dn×rn + dn-1×rn-1 +...+ d1×r1 + d0×r0 + d-1×r-1 + d-2×r-2 +...+ d-m×r-m Example 1. r=10 523.61 = 5×102+2×101+3×100+6×10-1+1×10-2

2. r=2 1011.11 = 23+21+20+2-1+2-2= (11.75)10

 6 

3. r=4 31.2 = 3×41+1×40+2×4-1 = (13.5)10

4. r=8, octal 65.3 = 6×81+5×80+3×8-1 = 53 3/8 = (53.375)10

Conversion from base 10 to base r: (531.375)10 = (x)8  Treat the integer part and the fraction part separately. 531 66 8 1 0

3 2 0 1

remainder of division by 8

x=1023.3

.375 3.000 3

integer part of multiplying by 8

 7 

Example:

r=3

(48.5)10=(x)3 .5 1 .5 1 1 .5 1 1 .5 1

0 1 2 1

…

48 16 5 1 0

\ x=1210.1111…=1210.1

Example:

r=5

(76.85)10=(x)5 .85 4.25 4 1.25 1 1.25 1

…

76 1 15 0 3 3 0

x=301.411…=301.41

 8 

Example:

r=16, hexadecimal system

digits used: {0, 1, 2,…, 9, A, B, C, D, E, F} (F3)16 = (x)10 x=F×161 + 3×160 = 15×16 + 3 = 243

(A92.1E)16 = (x)10 x=A×162 + 9×161 + 2×160 + 1×16-1 + E×16-2 30

=10×256+9×16+2+ 116 +14 256 =2706 256

=2706.1171875

(102.5)10 = (x)16 102 6 6 6 0

.5 8.0 8 0 x=66.8

 9 

Conversion to and from binary, octal and hexadecimal 8=23, 3-group size

(i) binary to octal

(1010111101100011)2 = (x)8 added to make a full group

001 010 111 101 100 011 1

2

7

5

4

3

x=127543 4

(ii) binary to hexadecimal 16=2 , 4-group size

(1010111101100011)2 = (x)16 1010 1111 0110 0011 A

F

x=AF63

6

3

 10 

(iii) Conversion from octal to binary

(7615)8=(x)2

group size-3

7 6 1 5 111

110

001

101

x=111110001101 (iv) hexadecimal to binary

(7615)16=(x)2

group size-4

7 6 1 5 0111 0110 0001 0101 x=0111011000010101 delete leading zeroes.

 11 

Decimal representation The Binary-Coded-Decimal numbers (BCD): Decimal Number

BCD number

0 1 2 3 4 5 6 7 8 9

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

 Note, that (99)10 converted to binary yields 1100011, but when represented in BCD code it becomes 1001 1001, namely each decimal digit is separately encoded.

 12 

ASCII code for characters character A B C

ASCII code 100 0001 100 0010 100 0011

⋮

⋮

O P Q

100 1111 101 0000 101 0001

⋮

⋮

Z 0 1

101 1010 011 0000 011 0001

⋮

⋮

9 blank (

011 1001 010 0000 010 1000

⋮

⋮

=

011 1101

 13 

Fixed point representation  Need a sign, magnitude and a radix point  To represent the sign: 0

positive

1

negative

1st bit =

 The decimal (or binary) point is usually either at the extreme left of the register, or at the extreme right of the register.  The radix point (decimal or binary) is usually implicit

 14 

 Before we show the fixed point representation we have to define the complement of a number:

(i) (r-1)’s complement

 The (r-1)’s complement of a number in radix r is obtained by subtracting each digit of the number from r-1.

Example: (a) r=10. The 9’s complement of 671 is 328. (b) r=2. 00101.

The one’s complement of 11010 is

 15 

(ii) The r’s complement

 Obtained by adding 1 to the low order digit of its (r-1)’s complement.

Example: (a) r=10. The 9’s complement of 671 is 328. The 10’s complement of 671 is 329. (b) r=2.

The 1’s complement of 11010 is

00101. The 2’s complement of 11010 is: one's complement

00101 + 1 00110

 16 

 The 2’s complement can be formed also by leaving all least significant 0’s and the first 1 unchanged, and then complementing the remaining digits:

Let N=11010

The 2’s complement of N is

00110 complemented unchanged

Example: The 2’s complement of 101101110001110100 is 010010001110001100

 17 

 To represent a positive number attach a 0 to its magnitude.  To represent a negative number there are 3 methods: 1. Signed magnitude representation. 2. Signed 1’s complement representation. 3. Signed 2’s complement representation.

Signed magnitude  The magnitude of the number is inserted after a negative sign (1). Let N=6 stored in a 7-bit register N

0 0 0 0 1 1 0 Sign bit

 18 

then –N is represented as −N

1 0 0 0 1 1 0 Sign bit

Signed One’s complement  The negative number is represented by the 1’s complement of its positive number.

Example: Same as before N=0000110, then –N=1111001

Signed Two’s complement  The negative number is represented by the 2’s complement of its positive number.

 19 

Example: Same as before N=0000110, then –N=1111010

Arithmetic addition  With signed magnitude: A+B=? - If sign (A) = sign (B), add magnitudes and attach signs. - If sign (A) ≠ sign (B), subtract small magnitude from large magnitude, and attach sign of large magnitude.  This procedure is slow for a computer.

 20 

With 2’s complement:  Add the two numbers, including their sign bit, and discard any carry out of the leftmost bit.

carries

+6 +9 +15

0 000110 + 0 001001 0 001111

−6 +9 +3

1 111010 + 0 001001 10 000011 discarded

carries

+6 −9 −3

0 000110 + 1 110111 1 111101

carries

−6 −9 −15

1 111010 + 1 110111 11 110001 discarded

 21 

With 1’s complement:  Add the two numbers, including their sign bit. If there is a carry out of the most significant (sign) bit, the result is incremented by 1 and the carry discarded.

+6 −9 −3

0 000110 + 1 110110 1 111100

−6 +9 +3

1 111001 + 0 001001 10 000010 + 1 0 000011 Called end-around carry.

 22 

 Advantage of 2’s complement: unique representation of 0:

Signed magnitude

+0 0 0…0

−0 1 0…0

1’s complement

0 0…0

1 1…1

2’s complement

0 0…0

None

 Range of numbers with a register of k+1 bits is ±(2k−1), where k bits are reserved for the number and one bit for the sign. 2’s complement system is asymmetric – it has one more negative then positives.

Arithmetic subtraction A−B=A+(−B)  In 2’s complement A−B=A+(2’s complement of B)

 23 

Example: Let

A=(3)10=000011 B=(5)10=000101

to perform A−B, we first complement B: 2’s complement of B:

111011

Then, we add A to it: 000011 + 111011 111110

2's complement representation of (−2)10

 24 

Floating point representation  Has two parts: mantissa, and exponent  Mantissa, m, represents a signed fixed point number. Usually the binary point is at the leftmost position of the number.  Exponent, e, designates the position of the actual binary point.  The value of the floating point number, with mantissa, m, and exponent, e, is m×re where r, is an implicit radix. r differs from computer to computer. Typically r=2, 8, 16.

 25 

Example: Consider a 24 bit register: 0 1

16 17 18

±

23

±

●

m

e

0

-

plus

1

-

minus

Sign: r=2

What is the value of the floating point number: 011001000000000000010100 sign

m

e

sign 3

1

25

m=+.11001=2-1+2-2+2-5= 4 + 32 = 32 =.78125 e=+010100=24+22=16+4=20 N=.78125×220=819200

 26 

 A mantissa is called normalized if it has no leading zeroes. In this case it contains the maximum number of significant digits. ± 1

±

1st digit ”1”.

Digital logic circuits  Manipulation of binary information is done by logic circuits, called gates.  Each gate has a distinct graphical symbol and its operation can be described by either an algebraic function or a truth table.

 27 

 AND gate: A B

x

Truth table A 0 0 1 1

x  AB or

x  AB

B 0 1 0 1

x 0 0 0 1

 OR gate: A B

x

Truth table A 0 0 1 1

x  AB

B 0 1 0 1

x 0 1 1 1

Note – this is not the arithmetic plus.

 Inverter: A

x

x  A or

xA

Truth table A x 0 1 1 0

 28 

 NAND gate: NAND=NOT AND

A B

x

Truth table A 0 0 1 1

x  ( AB ) or

x  AB

B 0 1 0 1

x 1 1 1 0

 NOR gate: NOR=NOT OR

A B

x

x  (A  B ) or

x  AB

Truth table A 0 0 1 1

B 0 1 0 1

x 1 0 0 0

 Exclusive-OR gate: A B

x x  A B

Truth table A 0 0 1 1

B 0 1 0 1

x 0 1 1 0

 29 

 Equivalence gate (exclusive nor): A B

x x  ( A  B)  or

x  AB

Truth table A 0 0 1 1

B 0 1 0 1

x 1 0 0 1

Note that equivalence and exclusive-or are complements of one another. Gates with more than two inputs:  AND gate xn

y

...

x1 x2

y  x1 x2

Truth table x1 x2 ... xn y 0 0 ... 0 0 0 0 ... 1 0

...

...

1 1 ... 0 0 1 1 ... 1 1

Output is “1” iff all inputs are “1”. y  Min x1 , x2 ,

 30 

 NOR gate: y

...

x1 x2 xn

Truth table x1 x2 ... xn y 0 0 ... 0 1 0 0 ... 1 0 ...

...

or

1 1 ... 0 0 1 1 ... 1 0

NOR=NOT OR  OR gate:

xn

...

x1 x2

y y  x1  x2 

Truth table x1 x2 ... xn y 0 0 ... 0 0 0 0 ... 1 1

...

...

1 1 ... 0 1 1 1 ... 1 1

Output is “0” iff all inputs are “0”. y  Max x1, x2,

 31 

 NAND gate:

xn

y

...

x1 x2

Truth table x1 x2 ... xn y 0 0 ... 0 1 0 0 ... 1 1

y  ( x1x 2 y  x1 x2

...

...

Or,

1 1 ... 0 1 1 1 ... 1 0

The output is “0” iff all inputs are “1”. NAND=NOT AND  Exclusive-OR gate (parity function): ...

x1 x2

y

xn

y  x1  x2 

Truth table x1 x2 ... xn y 0 0 ... 0 0 0 0 ... 1 1

...

...

y=1 iff odd # of inputs equal “1”.

 32 

Example: 3-way Exclusive-OR x1 x2 x3

y

Truth table x1 0 0 0 0 1 1 1 1

x2 0 0 1 1 0 0 1 1

x3 0 1 0 1 0 1 0 1

y 0 1 1 0 1 0 0 1

 Equivalence gate: Truth table

y  ( x1  x 2 

y  ( x1  x 2 

...

Or,

x1 x2 ... xn y 0 0 ... 0 1 0 0 ... 1 0

...

xn

y

...

x1 x2

y=1 iff even # of inputs are “1”. Note that exclusive or and equivalence are complements of one another.

 33 

Boolean algebra  Basic relations: 1. x  0  x 2. x  0  0 1 3. x  1 4. x  1  x

5. x  x  x 6. x  x  x 7. x  x  1 8. x  x  0 9. x  y  y  x

commutative law

10. xy  yx

commutative law

11. x  (y  z)  ( x  y )  z  x  y  z associative law associative law 12. x(yz)  (xy )z  xyz distributive law 13. x(y  z )  xy  xz 14. x  yz  ( x  y )( x  z) 15. x  y  x y 16. xy  x  y

17. x  x

distributive law De Morgan’s law De Morgan’s law

 34 

Examples: 1. Simplify

F  ( x1  x2 )x 2

F  x1 x2  x 2 x2  x1 x2  x1  x2  x1  x2 0

x1

original

x2

function F

x1 x2

F

simplified function

 35 

2. Simplify

F  ( x1  x2 )( x1  x2 )  x3

According to the distributive law x  yz  ( x  y )( x  z)

Therefore, F  x1  x2 x2  x3  x1  0  x3  x1  x 3 0

x1  x2

x1 x2

( x1  x2 )( x1  x2 )

x1  x2

x3

x1 x3

F

simplified function

original function F

 36 

 A measure to the complexity of a function is the number of literals in it.  A literal is an appearance of a variable, or its complement, in the function.

Example: In the previous example we have found that ( x1  x2 )( x1  x2 )  x3  x1  x3 5 literals

2 literals

 All the Boolean algebra relations may be proved by using truth tables.

 37 

Example: Proof of De Morgan’s law 15. x  y  x y x 0 0 1 1

y xy xy 0 1 1 1 0 0 0 0 0 1 0 0 two identical columns

Example: Proof of distributive law x  yz  ( x  y )( x  z) x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z x  yz ( x  y )( x  z ) 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 two identical columns

 38 

Map simplification:  Is a graphical way of simplifying functions.  The simplification will be done by a Karnaugh map.  A combination of variables for which the output is one is called a minterm.  A combination of variables for which the output is zero is called a maxterm.  Every function can be implemented with ANDs, ORs and INVERTs.

 39 

Example: Implement the following function

decimal equivalent

0 1 2 3 4 5 6 7

Minterms: Maxterms:

x1 0 0 0 0 1 1 1 1

x2 0 0 1 1 0 0 1 1

x3 0 1 0 1 0 1 0 1

F 0 1 0 1 0 1 1 1

x1 x2 x3

?

 001, 011,101,110,111 000,010,100 

 Instead of describing the function by a truth table, it is possible to specify it by listing its minterms F  1,3,5, 6,7 called standard sum

or, by its maxterms F  0, 2, 4 called standard product

F

 40 

 Implementation of standard sum components: 0  x1x 2 x3 , 1  x1x 2x 3 ,

2  x1x2 x3 , 3  x1 x2 x3 , 4  x1x 2x 3 , 5  x1 x2 x3 ,

6  x1 x2 x3 , 7  x1 x2 x3

can be implemented by AND gate and Inverters, like: x1 x2 x3

 4 

 Implementation of standard product components: 0  x1  x 2  x 3 , 1  x1  x2  x3 , 2  x1  x2  x3 , 3  x1  x2  x3 ,

4  x1  x2  x3 , 5  x1  x2  x3 , 6  x1  x2  x3 , 7  x1  x2  x3 ,

 41 

can be implemented by OR gate and Inverters, like: x1 x2 x3

  4

 Note that   i1 , i2 ,

and,   i1 , i2 ,

Going back to the example: F  1, 3, 5, 6, 7   1  3  5  6  7   x1 x2 x3  x1 x2 x3  x1 x2 x3  x1 x2 x3  x1 x2 x3

called standard sum of products

 42  x1 x2 x3

F

Sum of product implementation cost = 15

 43 

 The function could have been implemented by a product of sums: F   0, 2, 4    0  2  4    ( x1  x2  x3 )( x1  x 2  x 3 )( x1  x 2  x 3 )

x1 x2 x3 F

Product of sums implementation cost = 9

 44 

Karnaugh maps

x2

x1 0 0 0

1 2

1 1

3

x3

x1x 2

00 01 11 10 0 0 2 6 4 1 1

two variable map

3

7

5

three variable map

x3 x4

x1x 2

00 01 11 10 00 0 4 12 8 01 1

5 13 9

11 3

7 15 11

10 2

6 14 10

four variable map

 45 

Going back to the previous example: F  1,3,5,6,7

We draw the 3-variable map and indicate the minterms

x3

minterm 6

x1x2

00 01 11 10 0 0 0 1 0 1 1

minterm 1

1 minterm 3

1

1

minterm 5

minterm 7

 In order to come up with an economical implementation, we group the minterms into cubes.

 46 

 The size of the cubes must be a power of 2. Like 1, 2, 4, 8, 16.  Cells (minterms) in the cube must be “adjacent”.  The bigger the cube, the smaller is its cost.  A minterm may be covered by more than one cube.

Example of cubes

x1x2

x3

00 01 11 10 0 0 1 1 0 1 1

1

1

x2 x3

1

x1x2

x3

00 01 11 10 0 0 0 1 1

1

1

x1 x2 x3<...