Booth
Multiplication Algorithm
เป็นอัลกอริทึมที่ใช้ในการคูณตัวเลขในระบบ
signed integer มีหลักการทำงานดังนี้
1. เริ่มการทำงาน
2. ให้ตัวแปรA=0, M:เป็นตัวตั้ง,Qเป็นตัวคูณและให้Q-1=0,
count เป็นจำนวนbitของเลขที่จะนำมาคูณกัน
3.เปรียบเทียบค่าQ0,Q-1ว่ามีค่าเท่าใดโดย
1. Q0,Q-1=10:A=A-M
2. Q0,Q-1=01:A=A+M
4.shftขวาค่าภายในA,Q,Q-1และ count-=1
5.ดู count ว่าเท่ากับ 0 หรือยังหากยังให้กลับไปทำ3.ต่อหากเท่ากับ0แล้วจบการทำงานที่5.
6.แล้วจบการทำงาน
ตัวอย่าง:ขนาด4บิต
ให้M:2คูณกับQ:-4ได้เลขฐาน
2 ดังนี้ 0010 *1100
1.กำหนดค่าต่างๆ
AH
|
AL
|
Q
|
Q-1
|
|
0000
|
0000
|
1100
|
0
|
load
|
2.Q0,Q-1=00shiftอย่างเดียว
AH
|
AL
|
Q
|
Q-1
|
|
0000
|
0000
|
1100
|
0
|
load
|
0000
|
0000
|
0110
|
0
|
sh
|
3. Q0,Q-1=00shiftอย่างเดียว
AH
|
AL
|
Q
|
Q-1
|
|
0000
|
0000
|
1100
|
0
|
load
|
0000
|
0000
|
0110
|
0
|
sh
|
0000
|
0000
|
0011
|
0
|
sh
|
4. Q0,Q-1=10,A-Mแล้วshift
AH
|
AL
|
Q
|
Q-1
|
|
0000
|
0000
|
1100
|
0
|
load
|
0000
|
0000
|
0110
|
0
|
sh
|
0000
|
0000
|
0011
|
0
|
sh
|
1110
1111
|
0000
0000
|
0011
1001
|
0
1
|
A-M
sh
|
5. Q0,Q-1=11shiftอย่างเดียว
AH
|
AL
|
Q
|
Q-1
|
|
0000
|
0000
|
1100
|
0
|
load
|
0000
|
0000
|
0110
|
0
|
sh
|
0000
|
0000
|
0011
|
0
|
sh
|
1110
1111
|
0000
0000
|
0011
1001
|
0
1
|
A-M
sh
|
1111
|
1000
|
1100
|
1
|
sh
|
