Booth Algorithm
Booth Algorithm एक multiplication [गुणन] Algorithm है. जिसके द्वारा हम दो Signed Binary integers को 2’s complement में Multiply [गुणा] कर सकते हैं|
इस algorithm का प्रयोग करके हम multiplication [गुणन] की प्रक्रिया [process] की speed को बढ़ाने के लिए भी किया जाता है. यह एक बहुत efficient [कुशल] Algorithm भी है |
Booth algorithm की खोज [Discovery] 1950 में Andrew Donald Booth ने की थी |
यह Algorithm multiplier में string bits 0’s पर कार्य करता है जिसे किसी भी अतिरिक्त string bits की जरूरत नहीं होती है, इसमें
सिर्फ right-most string bits को shift करने की जरूरत होती है. Multiplier में 1s की एक string, weight 2k से weight 2m तक ही
होता है. Weight 2k से weight 2m को 2k+ 1 से 2m भी समझा जाता है |
Steps of Booth algorithm
1 . सबसे पहले multiplier और multiplicand को M और Q register के रूप में set किया जाता है |
2 . Starting में हम AC और Qn + 1 registers की value को 0 में set करते है |
3. SC जो है वो multiplier bits (Q) की संख्या को represents करता है. और यह एक sequence counter है जो कि लगातार घटते रहता है जब तक कि वह 0 तक ना आ जाए|
4 . Qn जो है वह Q की last bit को प्रदर्शित करता है और Qn + 1 जो है वह Qn के बढ़े हुए (incremented) बिट को 1 से दिखाता है।
5. Booth algorithm के प्रत्येक cycle (चक्र) में Qn और Qn + 1 bits को following parameters पर check किया जाता है:-
I). जब दो bits Qn and Qn + 1 00 या 11 हैं, तब हम AC के लिए arithmetic shift right operation (ashr) को परफॉर्म करते हैं और Qn और Qn + 1 के बिट्स 1 से increment हो जाते हैं|
ii). यदि Qn और Qn + 1 bits 01 है तब multiplicand bits को AC में जोड़ दिया जाता है. उसके बाद, हम AC और QR बिट्स में 1 से right shift operation करते हैं |
iii). यदि Qn और Qn + 1 के बिट्स 10 है तब M को AC से घटाया जाता है. इसके बाद, हम AC और QR बिट्स में 1 से right shift operation करते हैं|
6. यह operation तब तक चलता रहता है जब तक कि हम booth algorithm में n-1 bits तक ना पहुँच जाए |
7. Multiplication Binary Bits के परिणाम (results) AC और QR रजिस्टरों में store किए जाएंगे।