อัลกอริทึมการคูณของ Boothเป็นอัลกอริทึมการ คูณที่คูณ เลขฐานสองที่มี เครื่องหมายสอง จำนวนในรูปแบบสอง^คอม พลี เมนต์ อัลกอริทึมนี้คิดค้นโดยAndrew Donald Boothในปี 1950 ขณะทำการวิจัยเกี่ยวกับผลึกศาสตร์ที่Birkbeck CollegeในBloomsburyกรุงลอนดอน^{[ 1} ] อัลกอริทึมของ Booth มีความสำคัญในการศึกษาสถาปัตยกรรม คอมพิวเตอร์

อัลกอริทึมของ Booth ตรวจสอบคู่บิต ที่อยู่ติดกัน ของ ตัวคูณ NบิตYในการแสดงแบบสองคอมพลีเมนต์แบบมีเครื่องหมาย รวมถึงบิตโดยปริยายที่อยู่ต่ำกว่าบิตที่มีค่าน้อยที่สุด y = 0 สำหรับแต่ละบิตy สำหรับiที่วิ่งจาก 0 ถึงN − 1 จะพิจารณาบิตy และy ในกรณีที่บิตทั้งสองนี้เท่ากัน ตัวสะสมผลคูณPจะไม่เปลี่ยนแปลง ในกรณีที่y = 0 และ y = 1 ค่าตัวคูณคูณ 2 ⁱจะถูกบวกเข้ากับPและในกรณีที่y = 1 และy = 0 ค่าตัวคูณคูณ 2 ⁱจะถูกลบออกจากPค่าสุดท้ายของPคือผลคูณแบบมีเครื่องหมาย

การแสดงแทนของตัวคูณและผลคูณไม่ได้ระบุไว้ โดยทั่วไปแล้ว ทั้งสองอย่างจะอยู่ในรูปแบบสองส่วนเติมเต็มเช่นเดียวกับตัวคูณ แต่ระบบตัวเลขใดๆ ที่รองรับการบวกและการลบก็สามารถใช้งานได้เช่นกัน ดังที่กล่าวไว้ในที่นี้ ลำดับของขั้นตอนไม่ได้ถูกกำหนด โดยทั่วไปแล้ว จะดำเนินการจาก บิตที่มีค่าน้อยที่สุด (LSB)ไปยัง บิตที่มีค่ามากที่สุด (MSB)โดยเริ่มจากi = 0 การคูณด้วย 2i ^มักจะถูกแทนที่ด้วยการเลื่อนตัว สะสม Pไปทางขวาทีละน้อยระหว่างขั้นตอน บิตที่มีค่าน้อยสามารถเลื่อนออกไปได้ และการบวกและการลบในภายหลังสามารถทำได้เฉพาะกับ บิต N ที่มีค่าสูงสุด ของPเท่านั้น^{[ 2 ]}มีรูปแบบและการปรับปรุงประสิทธิภาพมากมายในรายละเอียดเหล่านี้

โดยทั่วไปแล้ว อัลกอริทึมนี้จะถูกอธิบายว่าเป็นการแปลงสตริงของเลข 1 ในตัวคูณให้เป็น +1 ที่มีลำดับสูงกว่า และ −1 ที่มีลำดับต่ำกว่าที่ปลายสตริง เมื่อสตริงวิ่งผ่านบิตที่มีค่าสูงสุด (MSB) จะไม่มี +1 ที่มีลำดับสูงกว่า และผลลัพธ์สุทธิจะถูกตีความว่าเป็นค่าลบของค่าที่เหมาะสม

อัลกอริทึมของ Booth สามารถนำไปใช้ได้โดยการบวกค่าที่กำหนดไว้ล่วงหน้าสองค่าAและS ซ้ำๆ ( ด้วยการบวกเลขฐานสองแบบไม่มีเครื่องหมายทั่วไป) เข้ากับผลคูณP จากนั้นทำการ เลื่อนบิต ไป ทางขวาบนPให้mและrเป็นตัวตั้งคูณและตัวคูณตามลำดับ และให้xและyแทนจำนวนบิตในmและr

1. กำหนดค่าของAและSและค่าเริ่มต้นของPตัวเลขทั้งหมดเหล่านี้ควรมีความยาวเท่ากับ ( x  +  y  + 1)
   1. A: เติมค่าm ลงในบิตที่มีนัยสำคัญที่สุด (ซ้ายสุด) ส่วนบิต ที่เหลืออีก ( y  + 1) บิต ให้เติมด้วยเลขศูนย์
   2. S: เติมบิตที่มีนัยสำคัญที่สุดด้วยค่าของ (− m ) ในรูปแบบเลขฐานสองแบบคอมพลีเมนต์ เติมบิตที่เหลือ ( y  + 1) บิตด้วยศูนย์
   3. P: เติมเลขศูนย์ลงในบิตที่มีค่ามากที่สุดxบิต จากนั้นเติมค่าของr ทางด้านขวาของ บิตที่มีค่าน้อยที่สุด (ขวาสุด) ด้วยเลขศูนย์
2. ระบุบิต ที่ มีค่าน้อยที่สุดสองบิต (บิตขวาสุด) ของP
   1. ถ้าค่าเป็น 01 ให้หาค่าของP  +  Aไม่ต้องสนใจค่าที่เกินขีดจำกัด
   2. ถ้าค่าเป็น 10 ให้หาค่าของP  +  Sไม่ต้องสนใจค่าที่เกินขีดจำกัด
   3. ถ้าค่าเป็น 00 ไม่ต้องทำอะไร ให้ใช้Pโดยตรงในขั้นตอนถัดไป
   4. ถ้าอายุครบ 11 ปี ไม่ต้องทำอะไร ให้ใช้Pในขั้นตอนถัดไปโดยตรง
3. เลื่อนค่าที่ได้ในขั้นตอนที่ 2 ไปทางขวาหนึ่งตำแหน่งโดยใช้การเลื่อนทางคณิตศาสตร์ ให้Pเท่ากับค่าใหม่นี้
4. ทำซ้ำขั้นตอนที่ 2 และ 3 จนครบyครั้ง
5. ตัดบิตที่มีค่าน้อยที่สุด ( บิตขวาสุด) ออกจากPนี่คือผลคูณของmและr

จงหาค่า 3 × (−4) โดยที่m = 3 และr = −4 และx = 4 และy = 4:

• m = 0011, -m = 1101, r = 1100
• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0
• ทำซ้ำลูปสี่ครั้ง:
  1. P = 0000 110 0 0บิตสองบิตสุดท้ายคือ 00
     • P = 0000 0110 0. การเลื่อนเลขคณิตไปทางขวา
  2. P = 0000 011 0 0บิตสองบิตสุดท้ายคือ 00
     • P = 0000 0011 0. การเลื่อนเลขคณิตไปทางขวา
  3. P = 0000 001 1 0สองบิตสุดท้ายคือ 10
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. การเลื่อนเลขคณิตไปทางขวา
  4. P = 1110 100 1 1 . สองบิตสุดท้ายคือ 11.
     • P = 1111 0100 1. การเลื่อนเลขคณิตไปทางขวา
• ผลคูณคือ 1111 0100 ซึ่งก็คือ −12

เทคนิคที่กล่าวมาข้างต้นนั้นไม่เพียงพอเมื่อตัวคูณเป็นจำนวนลบที่สุดที่สามารถแสดงได้ (เช่น ถ้าตัวคูณมี 4 บิต ค่านี้จะเป็น −8) เนื่องจากจะเกิดการโอเวอร์โฟลว์เมื่อคำนวณ -m ซึ่งเป็นค่าลบของตัวคูณ ซึ่งจำเป็นสำหรับการกำหนดค่า S วิธีแก้ไขที่เป็นไปได้วิธีหนึ่งคือการขยาย A, S และ P ออกไปอีกหนึ่งบิต ในขณะที่ยังคงแสดงจำนวนเดียวกัน กล่าวคือ ในขณะที่ก่อนหน้านี้ −8 ถูกแทนด้วย 1000 ในสี่บิต ตอนนี้จะถูกแทนด้วย 11000 ใน 5 บิต จากนั้นจึงดำเนินการตามที่อธิบายไว้ข้างต้น โดยมีการปรับเปลี่ยนในการกำหนดจำนวนบิตของ A และ S เช่น ค่าของm ซึ่งเดิมกำหนดให้กับบิต xแรกของ A จะถูกขยายเป็นx + 1 บิต และกำหนดให้กับบิต x + 1 บิต แรกของ A ต่อไป ด้านล่างนี้ สาธิตเทคนิคที่ได้รับการปรับปรุงโดยการคูณ −8 ด้วย 2 โดยใช้ 4 บิตสำหรับตัวตั้งคูณและตัวคูณ:

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0
• ทำซ้ำลูปสี่ครั้ง:
  1. P = 0 0000 001 0 0บิตสองบิตสุดท้ายคือ 00
     • P = 0 0000 0001 0. เลื่อนไปทางขวา
  2. P = 0 0000 000 1 0สองบิตสุดท้ายคือ 10
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. เลื่อนไปทางขวา
  3. P = 0 0100 000 0 1บิตสองบิตสุดท้ายคือ 01
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. เลื่อนไปทางขวา
  4. P = 1 1110 000 0 0บิตสองบิตสุดท้ายคือ 00
     • P = 1 1111 0000 0. เลื่อนไปทางขวา
• ผลลัพธ์ที่ได้คือ 11110000 (หลังจากตัดบิตแรกและบิตสุดท้ายทิ้ง) ซึ่งก็คือ −16

พิจารณาตัวคูณบวกที่ประกอบด้วยบล็อกของเลข 1 ล้อมรอบด้วยเลข 0 ตัวอย่างเช่น 00111110 ผลคูณจะคำนวณได้จากสูตร: โดยที่ M คือตัวตั้งคูณ จำนวนการคำนวณสามารถลดลงเหลือสองขั้นตอนได้โดยการเขียนใหม่เป็น $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&1&1&0\\\hline \end{array}}=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62}$$$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&0&0&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{1})=M\times 62.}$$

ในความเป็นจริง สามารถแสดงให้เห็นได้ว่าลำดับของเลข 1 ในระบบเลขฐานสองใดๆ สามารถแยกออกเป็นผลต่างของเลขฐานสองสองจำนวนได้:

$${\displaystyle (\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}.}$$

ดังนั้น การคูณจึงสามารถแทนที่ได้ด้วยสตริงของเลขหนึ่งในจำนวนเดิมโดยใช้การดำเนินการที่ง่ายกว่า เช่น การบวกตัวคูณ การเลื่อนผลคูณย่อยที่เกิดขึ้นไปยังตำแหน่งที่เหมาะสม แล้วจึงลบตัวคูณออก วิธีนี้ใช้ประโยชน์จากข้อเท็จจริงที่ว่าไม่จำเป็นต้องทำอะไรเลยนอกจากเลื่อนเมื่อจัดการกับเลข 0 ในตัวคูณไบนารี และคล้ายกับการใช้คุณสมบัติทางคณิตศาสตร์ที่ว่า 99 = 100 − 1 เมื่อคูณด้วย 99

รูปแบบนี้สามารถขยายไปใช้กับบล็อกเลข 1 จำนวนเท่าใดก็ได้ในตัวคูณ (รวมถึงกรณีที่มีเลข 1 เพียงตัวเดียวในบล็อก) ดังนั้น

$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&0&1&0\\\hline \end{array}}\ =M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58}$$$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&-1&1&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58.}$$

อัลกอริทึมของบูธใช้รูปแบบเก่านี้ โดยทำการบวกเมื่อพบหลักแรกของกลุ่มเลขหนึ่ง (0 1) และทำการลบเมื่อพบหลักสุดท้ายของกลุ่ม (1 0) วิธีนี้ใช้ได้กับตัวคูณที่เป็นลบเช่นกัน เมื่อเลขหนึ่งในตัวคูณถูกจัดกลุ่มเป็นกลุ่มยาว อัลกอริทึมของบูธจะทำการบวกและลบน้อยกว่าอัลกอริทึมการคูณแบบปกติ

ไมโครโปรเซสเซอร์Pentium ของIntelใช้รูปแบบ radix-8 ของอัลกอริทึม Booth ในตัวคูณฮาร์ดแวร์ 64 บิต เนื่องจากวิธีการที่ใช้ในการคูณแบบ radix-8 จึงจำเป็นต้องมีวงจรเสริมที่ซับซ้อนเพื่อดำเนินการกรณีพิเศษของการคูณด้วย 3 ในลักษณะที่ลดความหน่วงให้น้อยที่สุด โดยการรวมการใช้carry-lookahead , carry-selectและ การ บวกKogge–Stone ^{[ 3 ]}

• ตัวคูณเลขฐานสอง
• รูปแบบที่ไม่ติดกัน
• การแสดงผลไบนารีที่ซ้ำซ้อน
• ต้นไม้วอลเลซ
• ตัวคูณแดดด้า

• Collin, Andrew (ฤดูใบไม้ผลิ 1993). "คอมพิวเตอร์ของ Andrew Booth ที่ Birkbeck College" . Resurrection (5). ลอนดอน: Computer Conservation Society .
• แพตเตอร์สัน, เดวิด แอนดรูว์ ; เฮนเนสซี, จอห์น เลอรอย (1998). การจัดระเบียบและการออกแบบคอมพิวเตอร์: ส่วนต่อประสานระหว่างฮาร์ดแวร์และซอฟต์แวร์ (ฉบับที่สอง). ซานฟรานซิสโก, แคลิฟอร์เนีย, สหรัฐอเมริกา: สำนักพิมพ์มอร์แกน คอฟแมนน์ . ISBN 1-55860-428-6.
• สตอลลิงส์, วิลเลียม (2000). การจัดระเบียบและสถาปัตยกรรมคอมพิวเตอร์: การออกแบบเพื่อประสิทธิภาพ (ฉบับที่ห้า). นิวเจอร์ซีย์: เพรนติส-ฮอลล์ อิงค์. ISBN 0-13-081294-3.
• Savard, John JG (2018) [2006]. "เทคนิคการคำนวณขั้นสูง" . quadibloc . เก็บถาวรจากต้นฉบับเมื่อวันที่ 3 กรกฎาคม 2018 . สืบค้นเมื่อเมื่อวันที่ 16 กรกฎาคม 2018 .

• การเข้ารหัสบูธ Radix-4
• การเข้ารหัสแบบ Booth ฐาน 8ในทฤษฎีเชิงรูปธรรมของ RTL และเลขคณิตคอมพิวเตอร์
• โปรแกรมจำลอง JavaScript ของ Booth's Algorithm
• การนำไปใช้งานในภาษา Python
• การนำไปใช้งานในภาษา C++
• การนำไปใช้งานในภาษาจาวา
• ข้อดีของการใช้อัลกอริทึมของบูธ