1 of 80

Adapted from Dr. Bassam Kahhaleh’ Slides by Prof. Iyad Jafar

Digital Logic

0907231

0

2 of 80

Chapter 1

Binary Arithmetic

​

Chapter 5

Arithmetic Logic Circuits

1

3 of 80

Outline

  • Binary Addition
  • Unsigned Binary Subtraction
  • Binary Complements
  • Unsigned Numbers
  • Signed Numbers
  • Binary Adders
  • Binary Subtractors
  • Overflow Detection
  • Binary Multiplication and Division
  • Number Width Expansion

2

4 of 80

Binary Addition

3

5 of 80

Binary Addition

  • Remember!
  • Decimal Addition

5

5

5

5

+

0

1

1

= Ten ≥ Base

🡺 Subtract a Base and add carry to next digit

1

1

Carry

4

6 of 80

Binary Addition

  • One bit addition
  • Four possible combinations

X

+ Y

C S

0

+ 0

0 0

0

+ 1

0 1

1

+ 0

0 1

1

+ 1

1 0

X: Augend

Y: Addend

S: Sum

C: Carry

5

7 of 80

Binary Addition

  • Multiple bits!
  • Column Addition

1

0

1

1

1

1

1

1

1

1

0

+

0

0

0

0

1

1

1

≥ (2)10

1

1

1

1

1

1

= 61

​

= 23

= 84

🡺 Subtract a Base and add carry to next digit

6

8 of 80

Unsigned Binary Subtraction

7

9 of 80

Unsigned Binary Subtraction

  • One-bit Subtraction
  • Four possible combinations

X

- Y

B D

0

- 0

0 0

0

- 1

? ?

1

- 0

0 1

1

- 1

0 0

0

- 1

1 1

1

2

1 0 0

- 1 1

- 0 0 1

X: Subtrahend Y : Minuend D: Difference B: Borrow

Wrong!

8

10 of 80

Unsigned Binary Subtraction

0 1 1 0

0 1 0 1

-

2

0

0

0 0 0 1

0 0 0 1

0 1 0 1

-

0 0

1

2

1 0 0 0 0

1 1 0 0

-

- 0 1 0 0

1 1

9

11 of 80

Unsigned Binary Subtraction

  • Borrow a “Base” when needed

0

0

1

1

1

0

1

1

1

1

0

−

0

1

0

1

1

1

0

= (10)2

2

2

2

2

1

0

0

0

1

= 77

​

= 23

= 54

10

12 of 80

Binary Complements

11

13 of 80

Complements

  • 1’s Complement (Diminished Radix Complement)
    • All ‘0’s become ‘1’s
    • All ‘1’s become ‘0’s

Example (10110000)2

⇨ (01001111)2

If you add a number and its 1’s 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

12

14 of 80

Complements

  • What is the 1s complement of
    • (10010111)2

​

​

    • (100011)2

​

​

​

​

​

​

13

15 of 80

Complements

  • 2’s Complement (Radix Complement)
    • Take 1’s complement then add 1
    • Toggle all bits to the left of the first ‘1’ from the right

Example:

Number:

1’s Comp.:

0 1 0 1 0 0 0 0

1 0 1 1 0 0 0 0

0 1 0 0 1 1 1 1

+ 1

OR

1 0 1 1 0 0 0 0

0

0

0

0

1

0

1

0

14

16 of 80

Complements

  • What is the 2s complement of
    • ( 1010000100 )2

​

​

    • ( 101111111 )2

​

​

​

​

​

​

15

17 of 80

Unsigned Numbers

16

18 of 80

Unsigned Numbers

  • All numbers considered so far are unsigned numbers, i.e. positive only
  • Given n bits to represent an unsigned number:
    • The minimum value is 0
    • The maximum value is 2n-1
  • Example
    • n = 9
      • Minimum =
      • Maximum =
  • How about signed numbers?

17

19 of 80

Signed Numbers

18

20 of 80

Signed Numbers

  • Computers Represent Information in ‘0’s and ‘1’s
    • ‘+’ and ‘−’ signs have to be represented in ‘0’s and ‘1’s
      • ‘0’ ⇨ positive
      • ‘1’ ⇨ negative
    • We need one bit; the sign bit
  • Three Systems
    • Signed Magnitude
    • Signed 1’s Complement
    • Signed 2’s Complement
  • All three use the left-most bit to represent the sign

19

21 of 80

Signed Magnitude Representation

  • Magnitude of positive and negative numbers is the same and in binary.
  • Only the sign is different.

​

S

Magnitude (Binary)

Positive (+13)

Negative (-13)

0

1101

1

1101

20

22 of 80

Signed Magnitude Representation

  • Using 6 bits, show the representation of (-25)10 in signed magnitude.

​

​

  • What is the value of (101001)2 if it is a signed magnitude number?

​

​

  • What is the value of (001101)2 if it is signed magnitude number?

​

​

​

​

​

​

​

21

23 of 80

Signed Magnitude Representation

  • List all signed magnitude numbers that can be represented using 3 bits and determine their value in decimal.

Signed Magnitude

Value in Decimal

0

0

0

​

​

0

0

1

​

​

0

1

0

​

​

0

1

1

​

​

1

0

0

​

​

1

0

1

​

​

1

1

0

​

​

1

1

1

​

​

22

24 of 80

Signed Magnitude Range

  • 4-Bit Representation

24 = 16 Combinations

− 7 ≤ Number ≤ + 7

−23+1 ≤ Number ≤ +23 − 1

​

  • n-Bit Representation

−2n−1+1 ≤ Number ≤ +2n−1 − 1

Sign Mag.

Decimal

0 0 0 0

+ 0

0 0 0 1

+ 1

0 0 1 0

+ 2

0 0 1 1

+ 3

0 1 0 0

+ 4

0 1 0 1

+ 5

0 1 1 0

+ 6

0 1 1 1

+ 7

1 0 0 0

− 0

1 0 0 1

− 1

1 0 1 0

− 2

1 0 1 1

− 3

1 1 0 0

− 4

1 1 0 1

− 5

1 1 1 0

− 6

1 1 1 1

− 7

23

25 of 80

Signed Magnitude Representation

  • Challenges
    • Two representations for 0

(+0)10 ⇨ (0 000)2

(−0)10 ⇨ (1 000)2

​

    • Can’t include the sign bit in ‘Addition’

​

0 0 1 1 ⇨ (+3)10

+ 1 0 1 1 ⇨ (−3)10

1 1 1 0 ⇨ (−6)10

24

26 of 80

1’s Complement Representation

  • Positive numbers: magnitude in binary with a sign bit of 0
  • Negative numbers: calculate the “1’s Comp.” of the positive number including the sign bit

​

​

​

​

​

0

Magnitude (Binary)

1

Code (1’s Comp.)

Sign

Positive

Negative

25

27 of 80

1’s Complement Representation

  • Using 6 bits, show the representation of (-25)10 in signed 1s complement.

​

​

  • What is the value of (101001)2 if it is a signed 1s complement?

​

​

  • What is the value of (001101)2 if it is signed 1s complement number?

​

​

​

​

​

​

​

​

26

28 of 80

1’s Comp. Representation

  • List all signed 1’s comp numbers that can be represented using 3 bits and determine their value in decimal.

Signed 1s Comp.

Value in Decimal

0

0

0

​

​

0

0

1

​

​

0

1

0

​

​

0

1

1

​

​

1

0

0

​

​

1

0

1

​

​

1

1

0

​

​

1

1

1

​

​

27

29 of 80

1’s Complement Range

  • 4-Bit Representation

24 = 16 Combinations

− 7 ≤ Number ≤ + 7

−23+1 ≤ Number ≤ +23 − 1

​

  • n-Bit Representation

−2n−1+1 ≤ Number ≤ +2n−1 − 1

1s Comp.

Decimal

0 0 0 0

+ 0

0 0 0 1

+ 1

0 0 1 0

+ 2

0 0 1 1

+ 3

0 1 0 0

+ 4

0 1 0 1

+ 5

0 1 1 0

+ 6

0 1 1 1

+ 7

1 0 0 0

− 7

1 0 0 1

− 6

1 0 1 0

− 5

1 0 1 1

− 4

1 1 0 0

− 3

1 1 0 1

− 2

1 1 1 0

− 1

1 1 1 1

− 0

28

30 of 80

1’s Comp. Representation

  • Challenges
    • Two representations for 0

(+0)10 ⇨ (0 000)2

(−0)10 ⇨ (1 111)2

​

    • We can add the sign bit, but we may need to correct the result of ‘Addition’ unless we add the carry

​

0 0 1 1 ⇨ (+3)10

+ 1 1 0 1 ⇨ (−2)10

0 0 0 0 ⇨ (+0)10

1

1

0 0 0 1 ⇨ (+1)10

X

29

31 of 80

2’s Complement Representation

  • Positive numbers: magnitude in binary with a sign bit of 0
  • Negative numbers: calculate the “2’s Comp.” of the positive number including the sign bit

​

​

​

​

​

0

Magnitude (Binary)

1

Code (2’s Comp.)

Sign

Positive

Negative

30

32 of 80

2’s Complement Representation

  • Using 6 bits, show the representation of (-25)10 in 2s complement.

​

​

  • What is the value of (101001)2 if it is a signed 2s complement number?

​

​

  • What is the value of (001101)2 if it is signed 2s complement number?

​

​

​

​

​

​

​

31

33 of 80

2’s Complement Representation

  • List all signed 2’s comp numbers that can be represented using 3 bits and determine their value in decimal.

Signed 2s Comp.

Value in Decimal

0

0

0

​

​

0

0

1

​

​

0

1

0

​

​

0

1

1

​

​

1

0

0

​

​

1

0

1

​

​

1

1

0

​

​

1

1

1

​

​

32

34 of 80

2’s Complement Range

  • 4-Bit Representation

24 = 16 Combinations

− 8 ≤ Number ≤ + 7

−23 ≤ Number ≤ + 23 − 1

​

  • n-Bit Representation

−2n−1 ≤ Number ≤ + 2n−1 − 1

2s Comp.

Decimal

0 0 0 0

+ 0

0 0 0 1

+ 1

0 0 1 0

+ 2

0 0 1 1

+ 3

0 1 0 0

+ 4

0 1 0 1

+ 5

0 1 1 0

+ 6

0 1 1 1

+ 7

1 0 0 0

− 8

1 0 0 1

− 7

1 0 1 0

− 6

1 0 1 1

− 5

1 1 0 0

− 4

1 1 0 1

− 3

1 1 1 0

− 2

1 1 1 1

− 1

33

35 of 80

2’s Complement Representation

  • Challenges???
    • One representation for 0

​

(+0)10 ⇨ (0 000)2

(−0)10 ⇨ (0 000)2 ⇨ (1 111) 2 +1 ⇨ 1 (0 000) 2

    • We can add the sign bit with no problems; result is always correct!

​

0 0 1 1 ⇨ (+3)10

+ 1 1 1 0 ⇨ (−2)10

0 0 0 1 ⇨ (+1)10

1

34

36 of 80

Number Representations Summary

  • 4-Bit Example

​

Unsigned Binary

Signed Magnitude

1’s Comp.

2’s Comp.

Range

0 ≤ N ≤ 15

-7 ≤ N ≤ +7

-7 ≤ N ≤ +7

-8 ≤ N ≤ +7

Positive

Binary

Binary

Binary

Binary

Negative

X

Binary

1’s Comp.

2’s Comp.

0

0

0

1

1

1

35

37 of 80

Example

  • What is the decimal value of (101110)2?

​

​

​

​

​

​

​

​

36

38 of 80

Example

  • Complete the following table. Assume you have 5 bits only.

Decimal

Signed. Mag.

Signed 1’s Comp.

Signed 2’s Comp.

+12

​

​

​

-12

​

​

​

+7

​

​

​

-7

​

​

​

+19

​

​

​

-19

​

​

​

+16

​

​

​

-16

​

​

​

37

39 of 80

Example

  • Complete the following table. Assume you have 5 bits only.

Decimal

Signed. Mag.

Signed 1’s Comp.

Signed 2’s Comp.

+12

0 1100

0 1100

0 1100

-12

1 1100

1 0011

1 0100

+7

0 0111

0 0111

0 0111

-7

1 0111

1 1000

1 1001

+19

Out of range

Out of range

Out of range

-19

Out of range

Out of range

Out of range

+16

Out of range

Out of range

Out of range

-16

Out of range

Out of range

1 0000

38

40 of 80

Binary Subtraction Using 1’s Comp. Addition

  • Change “Subtraction” to “Addition”
  • If “Carry” = 1�then add it to the�LSB.
  • If “Carry” = 0�then the result�is ready.�

0 1 0 1

+ 1 1 1 0

(5)10 – (1)10

(+5)10 + (-1)10

0 0 1 1

+

0 1 0 0

0 1 0 1

+ 1 0 0 1

(5)10 – (6)10

(+5)10 + (-6)10

0 1 1 1 0

1 1 1 0

+ 4

− 1

1

39

41 of 80

Binary Subtraction Using 2’s Comp. Addition

  • Change “Subtraction” to “Addition”
  • We ignore the carry

in the 2’s Complement.

0 1 0 1

+ 1 1 1 1

(5)10 – (1)10

(+5)10 + (-1)10

1 0 1 0 0

0 1 0 1

+ 1 0 1 0

(5)10 – (6)10

(+5)10 + (-6)10

0 1 1 1 1

+ 4

− 1

40

42 of 80

Binary Adders

41

43 of 80

Binary Adders

  • Imagine designing a circuit that adds two n-bit numbers
    • Number of inputs 2 × n
    • Number of combinations 22n
    • Number of outputs n
  • Complex as n increases!
  • Alternatives?

X0

X1

X2

X3

Y0

Y1

Y2

Y3

+

S0

S1

S2

S3

C1

C2

C3

C4

42

44 of 80

Binary Adders

  • Design a functional block for the sub-function and repeat to obtain functional block for overall function
  • This functional block is called Cell
  • The approach is called Iterative Circuit / Array
  • Iterative array takes advantage of the regularity to make design feasible

​

43

45 of 80

Binary Adder

  • Half Adder
    • Adds 1-bit plus 1-bit
    • Produces Sum and Carry

HA

x

y

S

C

x y

C S

0 0

0 0

0 1

0 1

1 0

0 1

1 1

1 0

x

+ y

───

C S

x

​

​

y

S

​

C

44

46 of 80

Example 5

  • Using 1-bit half adders, show how to build a 2-bit adder

HA

X0

X1

Y0

Y1

+

S0

S1

C1

C2

X0

Y0

S0

C1

HA

X1

HA

Y1

S1

C2

2-bit

Adder

S0

S1

C2

X0

Y0

X1

Y1

X1+C1

Y1+X1+C1

45

47 of 80

Exercise

  • Using 1-bit half adders, show how to build a 4-bit adder

​

46

48 of 80

Exercise

  • Using the 2-bit adder block in Example 5, show how to build a 4-bit adder to add two 4-bit numbers

A: A3A2A1A0 and B: B3B2B1B0

​

2-bit

Adder

S0

S1

Cout

X0

Y0

X1

Y1

2-bit

Adder

S0

S1

Cout

X0

Y0

X1

Y1

47

49 of 80

Binary Adder

  • Full Adder
    • Adds 1-bit plus 1-bit plus 1-bit
    • Produces Sum and Carry

x y Cin

Cout S

0 0 0

0 0

0 0 1

0 1

0 1 0

0 1

0 1 1

1 0

1 0 0

0 1

1 0 1

1 0

1 1 0

1 0

1 1 1

1 1

x

+ y

+ Cin

───

Cout S

FA

x

y

Cin

S

Cout

​

​

​

y

​

​

​

0

1

0

1

x

1

0

1

0

​

​

Cin

​

​

​

​

​

​

y

​

​

​

0

0

1

0

x

0

1

1

1

​

​

Cin

​

​

​

S = x'y'Cin+x'yCin'+xy'Cin'+xyCin = x ⊕ y ⊕ Cin

Cout = xy + xCin + yCin

48

50 of 80

Binary Adder

  • Full Adder

x

​

​

y

​

​

Cin

S

​

​

​

​

​

Cout

x

​

y

​

Cin

S

​

​

​

Cout

S = x'y'Cin+x'yCin'+xy'Cin'+xyCin = x ⊕ y ⊕ Cin

Cout = xy + xCin + yCin

49

51 of 80

Example 6

  • Using 1-bit full adders, show how to build a 4-bit adder

C3 C2 C1

c3 c2 c1 .

+ x3 x2 x1 x0

+ y3 y2 y1 y0

────────

C4 S3 S2 S1 S0

FA

x3 x2 x1 x0

FA

FA

FA

y3 y2 y1 y0

S3 S2 S1 S0

0

4-bit

Binary Adder

x3x2x1x0 y3y2y1y0

S3S2S1S0

C4

C4

Carry Propagate Adder

Or Ripple Carry Adder

0

0

50

52 of 80

Example 7

  • 8-bit adder realized using two 4-bit CPAs

​

4-bit Ripple Carry Adder

A3 A2 A1 A0

B3 B2 B1 B0

S3 S2 S1 S0

C0

C4

x3 x2 x1 x0

y3 y2 y1 y0

x7 x6 x5 x4

y7 y6 y5 y4

S3 S2 S1 S0

S7 S6 S5 S4

4-bit Ripple Carry Adder

A3 A2 A1 A0

B3 B2 B1 B0

S3 S2 S1 S0

C0

C4

0

x3 x2 x1 x0

x7 x6 x5 x4

y3 y2 y1 y0

y7 y6 y5 y4

+

S3 S2 S1 S0

S7 S6 S5 S4

C8

51

53 of 80

Real Stuff

  • 74LS83A
  • 4-BIT BINARY FULL ADDER (Fast Carry)

52

54 of 80

Binary Subtractors

53

55 of 80

Binary Subtractor

  • Use 2’s complement with binary adder
    • x – y = x + (-y) = x + y’ + 1

54

56 of 80

Binary Adder/Subtractor

  • Use single adder for addition and subtraction
  • M: Control Signal (Mode)
    • M = 0 🡺 F = x + y
    • M = 1 🡺 F = x – y

55

57 of 80

Binary Adder/Subtractor

  • Can you think of a different approach to build the adder/subtractor?
    • Multiplexors!

56

58 of 80

Exercise

  • Design the circuit that can perform the operations X+Y, X-Y, Y-X and –X-Y. Assume X and Y to be 4-bit numbers.
    • Can we preform the four operations using one 4-bit adder?

​

​

​

​

​

​

​

​

​

    • Only three operations can be implemented using a single adder
    • Need two adders 🡪 Two possible solutions

57

59 of 80

Exercise - continued

  • Two possible solutions

58

60 of 80

Overflow Detection

59

61 of 80

Overflow

  • Arithmetic operations are performed on fixed-size values.
  • Result might not fit in the given size!

​

​

​

​

​

  • Need to detect overflow in hardware!

1

0

1

1

1

1

1

1

​

​

​

0

1

0

1

+

1

1

1

1

No space to

store!

60

62 of 80

Overflow

  • Unsigned Binary Numbers

​

​

​

FA

x3 x2 x1 x0

FA

FA

FA

y3 y2 y1 y0

S3 S2 S1 S0

C4 C3 C2 C1

0

Overflow

0 0 1 1

1 0 0 1

+

1 1 0 0

0

0 1 1 1

1 1 0 1

+

0 1 0 0

1

61

63 of 80

Overflow

  • Signed 2’s Complement Numbers

​

​

​

​

  • How?

FA

x3 x2 x1 x0

FA

FA

FA

y3 y2 y1 y0

S3 S2 S1 S0

C4 C3 C2 C1

0

Overflow

62

64 of 80

Overflow

  • 8-bit signed number range between: -128 to +127

​

 

 

 

 

63

65 of 80

Multiplication and Division

64

66 of 80

Binary Multiplication

  • Single-bit multiplication

​

  • Multiple bits

​

0 × 0 = 0

0 × 1 = 0

1 × 0 = 0

1 × 1 = 1

1 0 1

0 1 0

×

0 0 0

1 0 1

0 0 0

0

0

0

0 1 0 1 0

+

Multiplicand

Multiplier

Product

Partial Product

65

67 of 80

Multiplication by a Constant

  • Can use an adder of suitable size to implement
  • Example: X3X2X1X0 × 101

X3 X2 X1 X0

1 0 1 ×

X3 X2 X1 X0

X3 X2 X1 X0 0 0

0 0 0 0 0

X0

X1

(X2+X0)

(X3+X1)

(X2+0)

(X3+0)

X2

X0

X3

X1

X2

0

X3

0

0

X0

X1

(X2+X0)

(X3+X1)

(X2+0)

(X3+0)

66

68 of 80

Multiplication by 2n

​

​

​

​

​

​

​

​

​

​

​

​

1

0

1

0

1

0

1

0

1

1

0

0

0

0

x

x

3

6

12

×21

×21

  • Multiplication by 2n is equivalent to shifting the multiplicand by n bits to the left and inserting n zeros from right

×22

67

69 of 80

Division By 2n (Logical Right Shift)

​

​

​

​

​

​

​

​

​

​

​

​

1

0

1

0

1

0

1

0

0

1

1

0

0

0

x

x

12

6

3

/21

/21

/22

  • Division by 2n is equivalent to shifting the dividend by n bits to the right and inserting n zeros from left
  • Use with unsigned numbers

68

70 of 80

Division By 2n (Arithmetic Right Shift)

​

​

​

​

​

​

​

​

​

​

​

​

1

0

1

0

1

0

1

1

1

1

1

1

1

1

x

x

- 4

- 2

- 1

/21

/21

/22

  • Division by 2n is equivalent to shifting the dividend by n bits to the right and replicating the sign bit n times on the left
  • Use with signed numbers

69

71 of 80

Exercise

  • Assume A is 6-bit number with value (101110)2
    • What is the decimal value of A if it is
      • An unsigned number 🡪
      • Signed magnitude number 🡪
      • Signed 1s complement number 🡪
      • Signed 2s complement number 🡪
    • If A undergoes a logical right shift by two bits, then what is its new decimal value?

​

​

    • If A undergoes an arithmetic right shift by two bits, then what is its new decimal value?

​

​

70

72 of 80

Number Width Expansion

71

73 of 80

Zero Fill

  • Given an M-bit number, we might need to make it an N-bit number such that N > M

​

​

​

​

  • Zero filling: add N-M zeros to the left
  • Used with unsigned numbers

1

1

0

1

1

1

0

1

​

​

​

​

0

0

0

0

13

13

72

74 of 80

Sign Extension

  • Given an M-bit number, we might need to make it an N-bit number such that N>M

​

​

​

​

​

  • Replicate the sign bit N-M times
  • Used with signed numbers

1

0

1

1

1

0

1

1

​

​

​

​

1

1

1

1

0

0

1

1

0

0

1

1

​

​

​

​

0

0

0

0

-5

-5

+3

+3

73

75 of 80

Exercises

74

76 of 80

Suggested Problems

  • 1-8
  • 1-12
  • 5-8
  • 5-13

​

​

75

77 of 80

Exercises

*

Obtain the 1’s and 2’s complements of the following binary numbers:

  1. 11101010
  2. 01111110
  3. 00000001
  4. 10000000
  5. 00000000

​

76

78 of 80

Exercises

*

Implement a full adder with two 4 × 1 multiplexers�

77

79 of 80

Exercises

*

Convert decimal +61 and +27 to binary using the signed-2’s complement representation and enough digits to accommodate the numbers.

​

​

Then perform the binary equivalent of (+27) + (– 61), (–27) + (+61) and (–27) + (–61). Convert the answers back to decimal and verify that they are correct.

78

80 of 80

Exercises

*

The adder-subtractor circuit has the following values for mode input M and data inputs A and B. In each case, determine the values of the four SUM outputs and the carry C.

M A B

(a) 0 0111 0110�(b) 0 1000 1001�(c) 1 1100 1000�(d) 1 0101 1010�(e) 1 0000 0001

79