Booth Algorithm

นานมากแล้วที่ไม่ได้เขียนblogเลยมาเขียนเสียบ้างเรื่องbooth algorithm

 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