Kabīnes algoritms ir reizināšanas algoritms, kas ļauj reizināt divus bināros veselus skaitļus attiecīgi 2 papildinājumā. To izmanto arī, lai paātrinātu reizināšanas procesa veiktspēju. Tas ir arī ļoti efektīvs. Tas darbojas uz virknes bitiem 0 reizinātājā, kam nav nepieciešami papildu biti, tikai tiek pārvietoti vistālāk labējie virknes biti un 1. virkne reizinātāja bitu svarā 2^klīdz svaram 2^mko var uzskatīt par 2^k+1- 2^m .

Šis ir Booth algoritma attēlojums:

Iepriekš minētajā blokshēmā sākotnēji AC un J_n+1 biti ir iestatīti uz 0, un SC ir secības skaitītājs, kas attēlo kopējo bitu kopumu n, kas ir vienāds ar bitu skaitu reizinātājā. Tur ir BR kas pārstāv reizināšanas biti, un QR apzīmē reizinātāja biti . Pēc tam mēs sastapāmies ar diviem reizinātāja bitiem kā Q_nun Q_n+1, kur Qn apzīmē QR pēdējo bitu un Q_n+1apzīmē Qn palielināto bitu ar 1. Pieņemsim, ka divi reizinātāja biti ir vienādi ar 10; tas nozīmē, ka mums ir jāatņem reizinātājs no daļējā reizinājuma akumulatorā AC un pēc tam jāveic aritmētiskā nobīdes darbība (ashr). Ja abi reizinātāji ir vienādi ar 01, tas nozīmē, ka mums ir jāpievieno reizinātājs daļējai reizinājumam akumulatorā AC un pēc tam jāveic aritmētiskā nobīdes darbība ( Ašrs ), ieskaitot J_n+1 . Aritmētiskā maiņas darbība tiek izmantota Booth algoritmā, lai pārvietotu maiņstrāvas un QR bitus pa labi par vienu, un maiņstrāvas zīmes bits paliek nemainīgs. Un secības skaitītājs tiek nepārtraukti samazināts, līdz tiek atkārtota skaitļošanas cilpa, kas ir vienāda ar bitu skaitu (n).

Darbs pie Booth algoritma

1. Iestatiet bināros bitus Reizinātājs un Reizinātājs attiecīgi kā M un Q.
2. Sākotnēji mēs iestatījām maiņstrāvu un Q_n+1reģistrē vērtību uz 0.
3. SC apzīmē reizinātāja bitu skaitu (Q), un tas ir secības skaitītājs, kas tiek nepārtraukti samazināts, līdz vienāds ar bitu skaitu (n) vai sasniegts līdz 0.
4. Qn apzīmē Q pēdējo bitu un Q_n+1parāda Qn palielināto bitu par 1.
5. Katrā kabīnes algoritma ciklā Q_nun Q_n+1biti tiks pārbaudīti pēc šādiem parametriem:
   1. Kad divi biti Q_nun Q_n+1ir 00 vai 11, mēs vienkārši veicam aritmētisko nobīdes darbību pa labi (ashr) uz daļēju reizinājumu AC. Un Qn un Q biti_n+1tiek palielināts par 1 bitu.
   2. Ja Q biti_nun Q_n+1ir rāda uz 01, reizināšanas biti (M) tiks pievienoti maiņstrāvas (akumulatora reģistram). Pēc tam mēs veicam labās maiņas darbību uz maiņstrāvas un QR bitiem par 1.
   3. Ja Q biti_nun Q_n+1rāda līdz 10, reizināšanas biti (M) tiks atņemti no maiņstrāvas (akumulatoru reģistra). Pēc tam mēs veicam labās maiņas darbību uz maiņstrāvas un QR bitiem par 1.
6. Darbība nepārtraukti darbojas, līdz kabīnes algoritmā esam sasnieguši n - 1 bitu.
7. Reizināšanas bināro bitu rezultāti tiks saglabāti AC un QR reģistros.

Booth algoritmā tiek izmantotas divas metodes:

kas ir īpašs raksturs

1. RSC (labās maiņas apļveida raksts)

Tas nobīda binārā skaitļa vistālāk labo bitu un pēc tam tiek pievienots bināro bitu sākumam.

2. RSA (labās maiņas aritmētika)

Tas pievieno divus bināros bitus un pēc tam novirza rezultātu pa labi par 1 bita pozīciju.

atzīmes pārsvītrojums

Piemērs : 0100 + 0110 => 1010, pēc binārā skaitļa pievienošanas pārvietojiet katru bitu par 1 pa labi un ievietojiet pirmo rezultāta bitu jaunā bita sākumā.

Piemērs: reiziniet divus skaitļus 7 un 3, izmantojot Booth reizināšanas algoritmu.

Gadiem . Šeit mums ir divi skaitļi, 7 un 3. Pirmkārt, mums ir jāpārvērš 7 un 3 bināros skaitļos, piemēram, 7 = (0111) un 3 = (0011). Tagad iestatiet 7 (binārajā 0111) kā reizinātāju (M) un 3 (binārajā 0011) kā reizinātāju (Q). Un SC (Sequence Count) apzīmē bitu skaitu, un šeit mums ir 4 biti, tāpēc iestatiet SC = 4. Tas arī parāda kabīnes algoritmu iterācijas ciklu skaitu, un pēc tam cikli tiek palaisti SC = SC — 1 reizi.

Booth reizināšanas algoritma skaitliskais piemērs ir 7 x 3 = 21, un 21 binārais attēlojums ir 10101. Šeit mēs iegūstam bināro rezultātu 00010101. Tagad mēs to pārvēršam decimāldaļā kā (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

tostring metode

Piemērs: reiziniet divus skaitļus 23 un -9, izmantojot Booth reizināšanas algoritmu.

Šeit M = 23 = (010111) un Q = -9 = (110111)

J_n+1 = 1, tas nozīmē, ka izvade ir negatīva.

Tādējādi 23 * -9 = 2 papildinājums 111100110001 => (00001100111)