TechCodeview

Алгоритъмът на кабината е алгоритъм за умножение, който ни позволява да умножим двете двоични цели числа със знак съответно в допълнение 2. Използва се и за ускоряване на изпълнението на процеса на умножение. Също така е много ефективен. Работи върху низовите битове 0 в умножителя, който не изисква допълнителен бит, само измества най-десните битове на низа и низ от 1 в битово тегло на умножителя 2^кдо тегло 2^мкоето може да се счита за 2^{k+ 1}- 2^м .

Следва графичното представяне на алгоритъма на Booth:

В горната блок-схема, първоначално, AC и Q_{n + 1} битовете са зададени на 0, а SC е брояч на последователности, който представлява общия набор от битове н, което е равно на броя на битовете в умножителя. Има БР които представляват умножени битове, и QR представлява умножителни битове . След това се натъкнахме на два бита от множителя като Q_ни Q_{n + 1}, където Qn представлява последния бит от QR, и Q_{n + 1}представлява увеличения бит на Qn с 1. Да предположим, че два бита от множителя са равни на 10; това означава, че трябва да извадим множителя от частичния продукт в акумулатора AC и след това да извършим аритметична операция за изместване (ashr). Ако двата множителя са равни на 01, това означава, че трябва да извършим добавяне на множителя към частичното произведение в акумулатора AC и след това да извършим операцията за аритметично изместване ( Ашр ), включително Q_{n + 1} . Операцията за аритметично изместване се използва в алгоритъма на Booth за изместване на AC и QR битовете надясно с един и остава знаковият бит в AC непроменен. И броячът на последователности непрекъснато намалява, докато изчислителният цикъл се повтори, равен на броя битове (n).

Работа по алгоритъма на щанда

1. Задайте двоичните битове за множител и множител като M и Q, съответно.
2. Първоначално задаваме AC и Q_{n + 1}регистрира стойност на 0.
3. SC представлява броя на битовете на множителя (Q) и е брояч на последователности, който непрекъснато се намалява, докато стане равен на броя на битовете (n) или достигне до 0.
4. Qn представлява последния бит от Q и Q_n+1показва увеличения бит на Qn с 1.
5. На всеки цикъл от алгоритъма на кабината Q_ни Q_{n + 1}битовете ще бъдат проверени по следните параметри, както следва:
   1. Когато два бита Q_ни Q_{n + 1}са 00 или 11, ние просто изпълняваме операцията за аритметично изместване надясно (ashr) към частичното произведение AC. И битовете на Qn и Q_{n + 1}се увеличава с 1 бит.
   2. Ако битовете на Q_ни Q_{n + 1}се показва на 01, битовете на множителя (M) ще бъдат добавени към AC (Акумулаторен регистър). След това извършваме дясната операция за преместване към битовете AC и QR с 1.
   3. Ако битовете на Q_ни Q_{n + 1}показва до 10, битовете на множителя (M) ще бъдат извадени от AC (Акумулаторен регистър). След това извършваме дясната операция за преместване към битовете AC и QR с 1.
6. Операцията работи непрекъснато, докато достигнем n - 1 бит в алгоритъма на кабината.
7. Резултатите от двоичните битове на умножението ще се съхраняват в регистрите AC и QR.

Има два метода, използвани в алгоритъма на Booth:

svm

1. RSC (Кръгла дясна смяна)

Той измества най-десния бит на двоичното число и след това се добавя към началото на двоичните битове.

2. RSA (Аритметика за дясно преместване)

Той добавя двата двоични бита и след това измества резултата надясно с 1-битова позиция.

блокиране на реклами в youtube android

Пример : 0100 + 0110 => 1010, след като добавите двоичното число, изместете всеки бит с 1 надясно и поставете първия бит от резултата в началото на новия бит.

Пример: Умножете двете числа 7 и 3, като използвате алгоритъма за умножение на Booth.

години . Тук имаме две числа, 7 и 3. Първо, трябва да преобразуваме 7 и 3 в двоични числа като 7 = (0111) и 3 = (0011). Сега задайте 7 (в двоичен 0111) като множител (M) и 3 (в двоичен 0011) като множител (Q). И SC (Брой последователности) представлява броя на битовете, а тук имаме 4 бита, така че задайте SC = 4. Освен това показва броя на итерационните цикли на алгоритмите на кабината и след това циклите се изпълняват SC = SC - 1 път.

Численият пример на алгоритъма за умножение на Бут е 7 x 3 = 21 и двоичното представяне на 21 е 10101. Тук получаваме резултата в двоичен 00010101. Сега го преобразуваме в десетичен, като (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

низ към цяло число в java

Пример: Умножете двете числа 23 и -9, като използвате алгоритъма за умножение на Booth.

Тук M = 23 = (010111) и Q = -9 = (110111)

Q_{n + 1} = 1, това означава, че изходът е отрицателен.

Следователно, 23 * -9 = допълнение на 2 от 111100110001 => (00001100111)