程序代写代做代考 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
