Multiplier architectures and algorithms
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (380.66 KB, 26 trang )
Digital Circuits Design with HDL Course
CE Undergraduate – 1st, 2010-2011
Multiplier Architectures and
Algorithms
Pham Quoc Cuong
/>
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
Combinational Binary Multiplier
Multiplicand 1 1 0 1 0 1 1 1
21510
Multiplier
0 0 0 1 0 1 1 1
2310
Shift copies of
the multiplicand
1 1 0 1 0 1 1 1
1 1 0 1 0 1 1 1
1 1 0 1 0 1 1 1
1 1 0 1 0 1 1 1
Double shift
1 0 0 1 1 0 1 0 1 0 0 0 1
494510
• A combinational Circuit can be developed to implement the product
• Require hardware with multiple adders for each column
• Ordinary adder operates on only two words at a time
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
2
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
Combinational Binary Multiplier
Multiplicand 1 1 0 1 0 1 1 1
21510
Multiplier
2310
0 0 0 1 0 1 1 1
Accumulated
Partial Products
1 1 0 1 0 1 1 1
Shift copies of
the multiplicand
1 1 0 1 0 1 1 1
1 0 1 0 0 0 0 1 0 1
1 1 0 1 0 1 1 1
1 0 1 1 1 1 0 0 0 0 1
Double shift
1 1 0 1 0 1 1 1
1 0 0 1 1 0 1 0 1 0 0 0 1
494510
• Combinational Binary Multiplier operate fast, but require a significant
amount of silicon area
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
3
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
Sequential Binary Multiplier
• Choose a data-path architecture
• Design state machine for controller
Word1
[-:0]
Word2
[-:0]
7
15
Start
Clock
Reset
0
Sequential
Binary
Multiplier
Ready
Products
[-:0]
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
16
+
0
15
0
0
0
0
0
0
0
1
product
0
0
0
1
0
1
1
7
0
0
1
multiplier
0
1
0
1
0
1
1
1
multiplicand
Datapath architecture of sequential 8-bit multiplier
Interface signals and block diagram
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
4
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
Register transfers
product
7
0
multiplier
7
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
1
0
0
1
15
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
multiplicand
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
1
1
0
0
0
0
0
0
0
0
1
1
0
1
0
1
1
1
Shift Multiplicant
0
0
0
0
0
0
0
1
1
0
1
0
1
1
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
1
0
1
1
1
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
1
1
1
0
0
0
0
1
0
1
1
Shift Multiplicant
0
0
0
1
0
Shift Multiplicant
+
+
+
Not add
...
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
5
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
Structural Units
• Top-level module: Multiplier_STG_0
• m0: LSB of Multiplier, used to control state transaction
word1 word2
Load_words
Start
Shift
m0
Add
Controller
Datapath
Clock
Reset
m0
Ready
Multiplier Algorithms and Architectures
24/12/2010
Product
Pham Quoc Cuong
6
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
STGs for 4-bit Seq. Multiplier
!Reset/
Ready
!Reset/
Ready
Reset
S_Idle
Start/Load_word,
Ready
S_1
[0]/Add
S_8
Ready
![0]
Start/Load_word,
Ready
S_2
![0]/shift
[0]/Add
S_7
Start/Load_word,
Ready
S_1
[0]/Add
S_8
Ready
![0]
-/Shift
Reset
S_Idle
S_2
![0]/shift
[0]/Add
-/Shift
S_7
S_3
-/Shift
![0]/Shift
![0]/Shift
S_3
-/Shift
![0]/Shift
![0]/Shift
[0]/Add
S_6
S_4
[0]/Add
[0]/Add
S_6
S_5
[0]/Add
-/Shift
Multiplier Algorithms and Architectures
S_4
24/12/2010
S_5
-/Shift
Pham Quoc Cuong
7
Digital Circuits Design with HDL Course
CE Undergraduate – 1st, 2010-2011
Module Decleration
module Multiplier_STG_0 (product, Ready, word1, word2, Start, clock, reset);
parameter
L_word = 4;
// Datapath size
output [2*L_word -1: 0] product;
output
Ready;
input [L_word -1: 0]
word1, word2;
input
Start, clock, reset;
wire
m0, Load_words, Shift;
Datapath M1 (product, m0, word1, word2, Load_words, Shift, Add, clock, reset);
Controller M2 (Load_words, Shift, Add, Ready, m0, Start, clock, reset);
endmodule
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
8
Digital Circuits Design with HDL Course
CE Undergraduate – 1st, 2010-2011
Controller (1)
module Controller (Load_words, Shift, Add, Ready, m0, Start, clock, reset);
parameter
L_word = 4;
// Datapath size
parameter
L_state = 4;
// State size
output
Load_words, Shift, Add, Ready;
input
m0, Start, clock, reset;
reg
[L_state -1: 0]
state, next_state;
parameter
S_idle = 0, S_1 = 1, S_2 = 2;
parameter
S_3 = 3, S_4 = 4, S_5 = 5, S_6 = 6;
parameter
S_7 = 7, S_8 = 8;
reg
Load_words, Shift, Add;
wire
Ready = ((state == S_idle) && !reset) || (state == S_8);
always @ (posedge clock or posedge reset)
// State transitions
if (reset) state <= S_idle; else state <= next_state;
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
9
Digital Circuits Design with HDL Course
CE Undergraduate – 1st, 2010-2011
Controller (2)
always @ (state or Start or m0) begin
// Next state and control logic
Load_words = 0; Shift = 0; Add = 0;
case (state)
S_idle: if (Start)
begin Load_words = 1; next_state = S_1; end
else next_state = S_idle;
S_1:
if (m0)
begin Add = 1; next_state = S_2; end
else
begin Shift = 1; next_state = S_3; end
S_2:
begin Shift = 1; next_state = S_3; end
S_3:
if (m0)
begin Add = 1; next_state = S_4; end
else
begin Shift = 1; next_state = S_5; end
S_4:
begin Shift = 1; next_state = S_5; end
S_5:
if (m0)
begin Add = 1; next_state = S_6; end
else
begin Shift = 1; next_state = S_7; end
S_6:
begin Shift = 1; next_state = S_7; end
S_7:
if (m0)
begin Add = 1; next_state = S_8; end
else
begin next_state = S_8; end
S_8:
if (Start)
begin Load_words = 1; next_state = S_1; end
else
next_state = S_8;
default:
next_state = S_idle;
endcase
end
endmodule
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
10
Digital Circuits Design with HDL Course
CE Undergraduate – 1st, 2010-2011
Datapath (1)
module Datapath (product, m0, word1, word2, Load_words, Shift, Add, clock, reset);
parameter
L_word = 4;
output
[2*L_word -1: 0]
product;
output
m0;
input
[L_word -1: 0]
word1, word2;
input
Load_words, Shift, Add, clock, reset;
reg
[2*L_word -1: 0]
product, multiplicand;
reg
[L_word -1: 0]
multiplier;
wire
Multiplier Algorithms and Architectures
m0 = multiplier[0];
24/12/2010
Pham Quoc Cuong
11
Digital Circuits Design with HDL Course
CE Undergraduate – 1st, 2010-2011
Datapath (2)
always @ (posedge clock or posedge reset) begin
if (reset) begin multiplier <= 0; multiplicand <= 0; product <= 0; end
else if (Load_words) begin
multiplicand <= word1;
multiplier <= word2; product <= 0;
end
else if (Shift) begin
multiplier <= multiplier >> 1;
multiplicand <= multiplicand << 1;
end
else if (Add) product <= product + multiplicand;
end
endmodule
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
12
Digital Circuits Design with HDL Course
CE Undergraduate – 1st, 2010-2011
Synthesized circuit (1)
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
13
Digital Circuits Design with HDL Course
CE Undergraduate – 1st, 2010-2011
Synthesized circuit - controller
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
14
Digital Circuits Design with HDL Course
CE Undergraduate – 1st, 2010-2011
Synthesized circuit - datapath
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
15
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
Booth’s-Algorithm Sequential Multiplier
• Skips over strings of 1s in the multiplier
• Replaces a series of additions by one addition and one
subtraction
• Ex: 1111_0000 = 28 – 1 – (24 – 1) = 28 – 24 = 240
• Booth recoding scheme recodes the multiplier by detecting
strings of 1s and replacing them by signed digits that result
the same decimal value when indicated addition and
subtraction operations are performed
mi
mi-1
BRCi
Value
Status
0
0
0
0
String of 0s
0
1
1
+1
End of String of 1s
1
0
1
-1
Begin strings of 1s
1
1
0
0
Midstring of 1s
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
16
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
Booth recoding
mi
mi-1
BRCi
Value
Status
0
0
0
0
String of 0s
0
1
1
+1
End of String of 1s
1
0
1
-1
Begin strings of 1s
1
1
0
0
Midstring of 1s
-6510 =
Multiplier Algorithms and Architectures
1 0 1 1 1 1 1 1
2s complement Notation
1 0 1 1 1 1 1 1 0
Additional bit
1 1 0 0 0 0 0 1
Booth Recoded
Signed Digit Notation
24/12/2010
Pham Quoc Cuong
17
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
Example
0 0 0 0 1 1 1 1
-6510 =
1 1 0 0 0 0 0 1
-
0 0 0 0 1 1 1 1
Booth Recoded
Signed Digit Notation
0 0 0 0 1 1 1 1
-
0 0 0 0 1 1 1 1
1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 1
2s Complement Notation
0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1
Magnitude of product = 975
• Ordinary multiplication by -6510 would require seven additions,
but the Booth-recoded multiplier only requires one addition
and two subtractions
Multiplier Algorithms and Architectures
24/12/2010
Pham Quoc Cuong
18
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
STG for a 4-bit Booth Seq.
Multiplier
!Reset/
Ready
Reset
S_Idle
Start/Load_word,
Ready
S_1
1/Add
S_8
Ready
0,3/Shift
1/Add
S_7
2/Sub
BRC
S_2
0,3/shift
-/Shift
2/Sub
S_3
-/Shift
S_6
0,3/Shift
1/Add
2/Sub
2/Sub
1/Add
Multiplier Algorithms and Architectures
0,3/Shift
S_4
S_5
-/Shift
24/12/2010
Pham Quoc Cuong
19
CE Undergraduate – 1st, 2010-2011
Digital Circuits Design with HDL Course
Structural Units
• Top-level module: Multiplier_Booth_STG_0
• m0: LSB of Multiplier, used to control state transaction
word1 word2
Load_words
Start
Shift
m0
Add
Controller
Datapath
Sub
Clock
Reset
m0
Ready
Multiplier Algorithms and Architectures
24/12/2010
Product
Pham Quoc Cuong
20
