程序代写代做代考 algorithm PowerPoint 演示文稿

PowerPoint 演示文稿

CO101
Principle of Computer

Organization
Lecture 04: Arithmetic 2

Liang Yanyan

澳門科技大學
Macau of University of Science and

Technology

How does a computer work?

computer
Input Output

2

The basic unit: repeater

3

Basic logic unit: NOT

4

Basic logic unit: buffer

5

Basic logic unit: AND

6

7

Basic logic unit: OR

8

Basic logic unit: NAND and NOR

9

1-bit Half Adder and Full Adder

• A: input
• B: input
• S: output
• C: output

• Using two half adders
to build a full adder.

10

XOR gate

AND gate

Inputs Outputs
A B C S
0 0 0 0
1 0 0 1
0 1 0 1
1 1 1 0

Feedback and Flip-Flops

11

12

• Truth Table

13

14

An edge-triggered D-type flip-flop
• The idea here is that the Clock input controls both the first stage and the second

stage. But notice that the clock is inverted in the first stage. This means that the first
stage works exactly like a D-type flip-flop except that the Data input is stored when
the Clock is 0. The outputs of the second stage are inputs to the first stage, and these
are saved when the Clock is 1. The overall result is that the Data input is saved when
the Clock changes from 0 to 1.

15

An edge-triggered D-type flip-flop

16

Registers

• A register is a group of flip-flops.
• An n-bit register is made of n flip-flops and can store n

bits.
• A register may have additional combinational gates to

perform certain operations.

17

4-Bit Register
• A simple 4-bit register can be made

with 4 D-type flip-flops.
• They have a Common Clock.

• At each positive-edge, 4 bits are loaded in
parallel.

• Previous data is overwritten.
• Common Clear

• Asynchronous clear
• When clear = 0, all flip-flops are cleared.

i.e. 0 is stored.

18

4-bit Shift Register
• Serial-in and Serial-out (SISO)

• A simple 4-bit shift register can be made with 4 D-type
flip-flops.

• They have a Common Clock.
• At each positive-edge, 1 bit is shifted in
• Rightmost bit is discarded

• Which direction is this register shifting?
19

Multiply (unsigned)
• Paper and pencil example (unsigned):

• Multiplicand 1000
Multiplier 1001

1000
0000
0000
1000

Product 01001000

• m bits x n bits = m+n bit product
• Binary makes it easy:

•0 => place 0 ( 0 x multiplicand)
•1 => place a copy ( 1 x multiplicand)

20

Multiply Hardware
• 32-bit Multiplicand register, 32-bit ALU, 64-bit Product

register, (Multiplier register is encapsulated in product
register).

21

Product (Multiplier)

Multiplicand

32-bit ALU

Write
Control

32 bits

64 bits

Shift Right

Multiply Algorithm

22Done
Yes: 32 repetitions

2. Shift the Product register right 1 bit.

No: < 32 repetitions 1. Test Product LSB Product LSB == 0Product LSB == 1 1a. Add multiplicand to the left half of product & place the result in the left half of Product register 32nd repetition? Start Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = 0011, multiplicand = 0010. 23 Product Multiplier Multiplicand Write Control 4 bits Initial state: 0010 0000 0011 Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = 0011, multiplicand = 0010. 24Product Multiplier Multiplicand Write Control 4 bits 1st repetition: 0010 0010 0011 Step 1a: Add multiplicand to the left half of product Step 1: Product LSB == 1 Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = 0011, multiplicand = 0010. 25 Product Multiplier Multiplicand Write Control 4 bits 1st repetition: 0010 0001 0001 Step 2: Shift product register right 1 bit Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = 0011, multiplicand = 0010. 26 Product Multiplier Multiplicand Write Control 4 bits 2nd repetition: 0010 0011 0001 Step 1a: Add multiplicand to the left half of product Step 1: Product LSB == 1 Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = 0011, multiplicand = 0010. 27 Product Multiplier Multiplicand Write Control 4 bits 2nd repetition: 0010 0001 1000 Step 2: Shift product register right 1 bit Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = 0011, multiplicand = 0010. 28 Product Multiplier Multiplicand Write Control 4 bits 3rd repetition: 0010 0001 1000 Step 1: Product LSB == 0 No addition is required. Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = 0011, multiplicand = 0010. 29 Product Multiplier Multiplicand Write Control 4 bits 3rd repetition: 0010 0000 1100 Step 2: Shift product register right 1 bit Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = 0011, multiplicand = 0010. 30 Product Multiplier Multiplicand Write Control 4 bits 4th repetition: 0010 0000 1100 Step 1: Product LSB == 0 No addition is required. Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = 0011, multiplicand = 0010. 31 Product Multiplier Multiplicand Write Control 4 bits 4th repetition: 0010 0000 0110 Step 2: Shift product register right 1 bit 4th repetition, STOP Observations on Multiply Version 3 • Both Multiplier & Product are shifted at the same time. • As they are combined in the same register ? • What about signed multiplication? • easiest solution is to make both positive & remember whether to inverse product when done (leave out the sign bit, run for 31 steps). • apply definition of 2’s complement • need to sign-extend partial products and subtract at the end. • Booth’s Algorithm is elegant way to multiply signed numbers using same hardware as before. 32 Multiply Hardware for Booth Algorithm • Same as version 3 before • 32-bit Multiplicand register, 32-bit ALU, 64-bit Product register, (Multiplier register is encapsulated in product register) 33 Product (Multiplier) Multiplicand 32-bit ALU Write Control 32 bits 64 bits Shift Right Multiply Booth Algorithm 34Done Yes: 32 repetitions 2. Shift the Product register right 1 bit. No: < 32 repetitions 1. Test Product Product lower 2 bits == 00 or 11 Product lower 2 bits == 01 1a. Left half product = Left half product + multiplicand 32nd repetition? Start 1b. Left half product = Left half product - multiplicand Product lower 2 bits == 10 NOTE: Product 00101101 0 Product lower 2 bits Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 35 Product Multiplier Multiplicand Write Control 4 bits Initial state: 0010 0000 1101 0 Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 36 Product Multiplier Multiplicand Write Control 4 bits 1st repetition: 0010 1110 1101 0 Step 1: Product lower 2 bits == 10 Step 1b: Product left half = Product left half – multiplicand 0000 – 0010 = 0000 + 1110 = 1110 0000 Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 37 Product Multiplier Multiplicand Write Control 4 bits 1st repetition: 0010 1111 0110 1 Step 2: Shift product register right 1 bit (Remember sign extend) Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 38Product Multiplier Multiplicand Write Control 4 bits 2nd repetition: 0010 Step 1: Product lower 2 bits == 01 Step 1a: Product left half = Product left half + multiplicand 0010 + 1111 = 0001 0001 0110 1 1111 Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 39 Product Multiplier Multiplicand Write Control 4 bits 2nd repetition: 0010 Step 2: Shift product register right 1 bit 0000 1011 0 Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 40Product Multiplier Multiplicand Write Control 4 bits 3rd repetition: 0010 1110 1011 0 Step 1: Product lower 2 bits == 10 Step 1b: Product left half = Product left half - multiplicand 0000 - 0010 = 0000 + 1110 = 1110 0000 Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 41 Product Multiplier Multiplicand Write Control 4 bits 3rd repetition: 0010 1111 0101 1 Step 2: Shift product register right 1 bit Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 42 Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 43 Product Multiplier Multiplicand Write Control 4 bits 4th repetition: 0010 1111 0101 1 Step 1: Product lower 2 bits == 11 No need to add or sub. Example • 4-bit Multiplicand register, 4-bit ALU, 8-bit Product register, (Multiplier register is encapsulated in product register). • Multiplier = -3 = 1101, multiplicand = 0010. 44 Product Multiplier Multiplicand Write Control 4 bits 4th repetition: 0010 Step 2: Shift product register right 1 bit 1111 1010 1 4th repetition, STOP Product = 1111 1010 Divide: Paper & Pencil • See how big a number can be subtracted, creating quotient bit on each step • Dividend = Quotient x Divisor + Remainder • 3 versions of divide, successive refinement 45 Divide Hardware • 32-bit Divisor register, 32-bit ALU, 64-bit Remainder register, (0-bit Quotient register, combined in remainder register) 46 Remainder (Quotient) Divisor 32-bit ALU Write Control 32 bits 64 bits Shift Left“HI” “LO” Divide Algorithm 47 3b. Restore the original value by adding the Divisor register to the left half of the Remainder register, &place the sum in the left half of the Remainder register. Also shift the Remainder register to the left, setting the new LSB to 0. Test Remainder Remainder < 0Remainder ≧ 0 2. Subtract the Divisor register from the left half of the Remainder register, & place the result in the left half of the Remainder register. 3a. Shift the Remainder register to the left, setting the LSB to 1. 1. Shift the Remainder register left 1 bit. Done. Shift left half of Remainder right 1 bit. Yes: n repetitions nth repetition? No: < n repetitions Start: Place Dividend in lower part of Remainder Takes n steps for n-bit Quotient Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 48 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 0000 0111 Initial state: 0010 Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 49 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 0000 1110 Initial state: 0010 Step 1: shift remainder left 1 bit Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 50 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 1110 1110 1st repetition: 0010 Step 2: remainder upper half = remainder upper half – divisor = 0000 – 0010 = 1110 Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 51 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 0000 1110 1st repetition: 0010 As remainder < 0 Step 3b: restore remainder upper half Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 52 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 0001 1100 1st repetition: 0010 Step 3b: shift remainder left 1 bit set remainder LSB = 0 Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 53 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 1111 1100 2nd repetition: 0010 Step 2: remainder upper half = remainder upper half – divisor = 0001 – 0010 = 1111 Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 54 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 0001 1100 2nd repetition: 0010 Since remainder < 0 Step 3b: restore remainder upper half Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 55 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 0011 1000 2nd repetition: 0010 Step 3b: shift remainder left 1 bit set remainder LSB = 0 Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 56 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 0001 1000 3rd repetition: 0010 Step 2: remainder upper half = remainder upper half – divisor = 0011 – 0010 = 0001 Example • 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register. • Dividend = 0111, divisor = 0010. 57 Remainder (Quotient) Divisor 4-bit ALU Control 4 bits 0011 0001 3rd repetition: 0010 Since remainder >= 0
Step 3a: shift remainder left 1 bit
set remainder LSB = 1

Example
• 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register.
• Dividend = 0111, divisor = 0010.

58

Remainder (Quotient)

Divisor

4-bit ALU

Control

4 bits

0001 0001

4th repetition:

0010

Step 2: remainder upper half = remainder upper half – divisor
= 0011 – 0010
= 0001

Example
• 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register.
• Dividend = 0111, divisor = 0010.

59

Remainder (Quotient)

Divisor

4-bit ALU

Control

4 bits

0010 0011

4th repetition:

0010

Since remainder >= 0
Step 3a: shift remainder left 1 bit
set remainder LSB = 1

Example
• 4-bit Divisor register, 4-bit ALU, 8-bit Remainder register.
• Dividend = 0111, divisor = 0010.

60

Remainder (Quotient)

Divisor

4-bit ALU

Control

4 bits

0001 0011

4th repetition:

0010

4th repetition, quit the loop
Shift upper half of remainder right 1 bit
STOP

Summary
• Divide and Multiply use the same hardware architecture

• Just need ALU to add or subtract
• 64-bit register for multiply and divide

• Signed Divides: Simplest is to remember signs, make
positive, and complement quotient and remainder if
necessary
• Note: the sign of Dividend and Remainder must be the same
• Note: Quotient negated if Divisor sign & Dividend sign disagree

e.g., –7 ÷ 2 = –3, remainder = –1

61

Remainder (Quotient)

“HI” “LO”

Product (Multiplier)

“HI” “LO”

32 bits 32 bits 32 bits 32 bits

CO101�Principle of Computer Organization
How does a computer work?
The basic unit: repeater
Basic logic unit: NOT
Basic logic unit: buffer
Basic logic unit: AND
幻灯片编号 7
Basic logic unit: OR
Basic logic unit: NAND and NOR
1-bit Half Adder and Full Adder
Feedback and Flip-Flops
幻灯片编号 12
幻灯片编号 13
幻灯片编号 14
An edge-triggered D-type flip-flop
An edge-triggered D-type flip-flop
Registers
4-Bit Register
4-bit Shift Register
Multiply (unsigned)
Multiply Hardware
Multiply Algorithm
Example
Example
Example
Example
Example
Example
Example
Example
Example
Observations on Multiply Version 3
Multiply Hardware for Booth Algorithm
Multiply Booth Algorithm
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Divide: Paper & Pencil
Divide Hardware
Divide Algorithm
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Summary