Boothův multiplikační algoritmus - Booths multiplication algorithm - Wikipedia

Boothův multiplikační algoritmus je multiplikační algoritmus což znásobuje dva podepsané binární čísla v dvoukompletní notace. The algoritmus byl vynalezen Andrew Donald Booth v roce 1950 při výzkumu krystalografie na Birkbeck College v Bloomsbury, Londýn.^[1] Boothův algoritmus je zajímavý pro studium počítačová architektura.

Algoritmus

Boothův algoritmus zkoumá sousední páry bity multiplikátoru „N“ bitů Y v podepsané doplněk dvou reprezentace, včetně implicitního bitu pod nejméně významný bit, y₋₁ = 0. Pro každý bit y_i, pro i běží od 0 do N - 1, kousky y_i a y_i−1 jsou považovány. Kde jsou tyto dva bity stejné, produktový akumulátor P je beze změny. Kde y_i = 0 a y_i−1 = 1, multiplikátor a krát 2ⁱ je přidán do P; a kde y_i = 1 a y_{i − 1} = 0, násobek a krát 2ⁱ je odečteno od P. Konečná hodnota P je podepsaný produkt.

Reprezentace multiplikátoru a produktu nejsou specifikovány; obvykle jsou oba také v reprezentaci dvou doplňků, jako je multiplikátor, ale bude fungovat také jakýkoli číselný systém, který podporuje sčítání a odčítání. Jak je zde uvedeno, pořadí kroků není určeno. Typicky vychází z LSB na MSB, počínaje od i = 0; násobení o 2ⁱ je pak obvykle nahrazen přírůstkovým posunem P akumulátor vpravo mezi kroky; nízké bity lze posunout ven a následné sčítání a odčítání pak lze provádět jen na nejvyšší N kousky P.^[2] Existuje mnoho variant a optimalizací těchto detailů.

Algoritmus je často popisován jako převod řetězců 1 s v multiplikátoru na vyšší řád +1 a nízký řád -1 na koncích řetězce. Když řetězec prochází MSB, neexistuje žádný vyšší řád +1 a čistým efektem je interpretace jako zápor příslušné hodnoty.

Typická implementace

Walther WSR160 arithmometer z roku 1960. Každé otočení kliky přidává (nahoru) nebo odečte (dolů) operand nastavený na horní registr z hodnoty v registru akumulátoru dole. Řazení sčítačka vlevo nebo vpravo znásobí účinek o deset.

Boothův algoritmus lze implementovat opakovaným přidáváním (s běžným nepodepsaným binárním přidáním) jedné ze dvou předem určených hodnot A a S k produktu P, poté provedením doprava aritmetický posun na P. Nechat m a r být multiplikátor a násobitel, v uvedeném pořadí; a nechte X a y představují počet bitů v m a r.

Určete hodnoty A a Sa počáteční hodnota P. Všechna tato čísla by měla mít délku rovnou (X + y + 1).
1. Odpověď: Vyplňte nejvýznamnější (nejvíce vlevo) bity hodnotou m. Naplňte zbývající (y + 1) bity s nulami.
2. S: Naplňte nejvýznamnější bity hodnotou (-m) ve dvojkové notaci. Naplňte zbývající (y + 1) bity s nulami.
3. P: Vyplňte nejvýznamnější X bity s nulami. Napravo od toho přidejte hodnotu r. Naplňte nejméně významný bit (nejvíce vpravo) nulou.
Určete dva nejméně významné (nejvíce vpravo) bity P.
1. Pokud jsou 01, najděte hodnotu P + A. Ignorujte jakékoli přetečení.
2. Pokud je jim 10, najděte hodnotu P + S. Ignorujte jakékoli přetečení.
3. Pokud jsou 00, nedělejte nic. Použití P přímo v dalším kroku.
4. Pokud je jim 11, nedělejte nic. Použití P přímo v dalším kroku.
Aritmeticky posunout hodnota získaná ve 2. kroku o jedno místo vpravo. Nechat P nyní rovná se tato nová hodnota.
Opakujte kroky 2 a 3, dokud nebudou hotové y krát.
Vyhoďte nejméně významný bit (nejvíce vpravo) z P. Toto je produkt m a r.

Příklad

Najděte 3 × (−4), s m = 3 a r = −4 a X = 4 a y = 4:

m = 0011, -m = 1101, r = 1100
A = 0011 0000 0
S = 1101 0000 0
P = 0000 1100 0
Proveďte smyčku čtyřikrát:
1. P = 0000 1100 0. Poslední dva bity jsou 00.
  - P = 0000 0110 0. Aritmetický posun doprava.
2. P = 0000 0110 0. Poslední dva bity jsou 00.
  - P = 0000 0011 0. Aritmetický posun doprava.
3. P = 00000011 0. Poslední dva bity jsou 10.
  - P = 1101 0011 0. P = P + S.
  - P = 1110 1001 1. Aritmetický posun doprava.
4. P = 1110 1001 1. Poslední dva bity jsou 11.
  - P = 1111 0100 1. Aritmetický posun doprava.
Produkt je 1111 0100, což je −12.

Výše uvedená technika je neadekvátní, když multiplikátor je nejvíce záporné číslo které lze reprezentovat (např. má-li multiplikátor 4 bity, pak je tato hodnota −8). Jednou z možných korekcí tohoto problému je přidání ještě jednoho bitu nalevo od A, S a P. Poté následuje výše popsaná implementace s úpravami při určování bitů A a S; např. hodnota m, původně přiřazen k prvnímu X bity A, budou přiřazeny první X+1 bity A. Níže je vylepšená technika demonstrována vynásobením −8 o 2 pomocí 4 bitů pro multiplikátor a multiplikátor:

A = 1 1000 0000 0
S = 0 1000 0000 0
P = 0 0000 0010 0
Proveďte smyčku čtyřikrát:
1. P = 0 00000010 0. Poslední dva bity jsou 00.
  - P = 0 0000 0001 0. Posun doprava.
2. P = 0 0000 0001 0. Poslední dva bity jsou 10.
  - P = 0 1000 0001 0. P = P + S.
  - P = 0 0100 0000 1. Posun doprava.
3. P = 0 0100 0000 1. Poslední dva bity jsou 01.
  - P = 1 1100 0000 1. P = P + A.
  - P = 1 1110 0000 0. Posun doprava.
4. P = 1 1110 0000 0. Poslední dva bity jsou 00.
  - P = 1 1111 0000 0. Posun doprava.
Produkt je 11110000 (po vyřazení prvního a posledního bitu), což je −16.

Jak to funguje

Zvažte pozitivní multiplikátor skládající se z bloku 1 s obklopeného 0 s. Například 00111110. Produkt je dán:

{ displaystyle M times , ^ { prime prime} 0 ; 0 ; 1 ; 1 ; 1 ; 1 ; 1 ; 0 , ^ { prime prime} = M krát (2 ^ {5} + 2 ^ {4} + 2 ^ {3} + 2 ^ {2} + 2 ^ {1}) = M krát 62}

kde M je multiplikátor. Počet operací lze snížit na dvě přepsáním stejného jako

{ displaystyle M times , ^ { prime prime} 0 ; 1 ; 0 ; 0 ; 0 ; 0 { mbox {-1}} ; 0 , ^ { prime prime } = M krát (2 ^ {6} -2 ^ {1}) = M krát 62.}

Ve skutečnosti lze ukázat, že jakoukoli sekvenci 1 s v binárním čísle lze rozdělit na rozdíl dvou binárních čísel:

{ 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}.}

Násobení tedy může být ve skutečnosti nahrazeno řetězcem jedniček v původním počtu jednoduššími operacemi, přidáním multiplikátoru, posunutím takto vytvořeného dílčího produktu o příslušná místa a nakonec multiplikátor odečtením. Využívá skutečnosti, že při práci s 0s v binárním multiplikátoru není nutné dělat nic jiného, než posunout, a je podobné použití matematické vlastnosti 99 = 100 - 1 při vynásobení 99.

Toto schéma lze rozšířit na libovolný počet bloků 1 s v multiplikátoru (včetně případu jedné 1 v bloku). Tím pádem,

{ displaystyle M times , ^ { prime prime} 0 ; 0 ; 1 ; 1 ; 1 ; 0 ; 1 ; 0 , ^ { prime prime} = M krát (2 ^ {5} + 2 ^ {4} + 2 ^ {3} + 2 ^ {1}) = M krát 58}

{ displaystyle M times , ^ { prime prime} 0 ; 1 ; 0 ; 0 { mbox {-1}} ; 1 { mbox {-1}} ; 0 , ^ { prime prime} = M krát (2 ^ {6} -2 ^ {3} + 2 ^ {2} -2 ^ {1}) = M krát 58.}

Boothův algoritmus sleduje toto staré schéma tím, že provádí sčítání, když narazí na první číslici bloku jednotek (0 1), a odčítání, když narazí na konec bloku (1 0). To funguje i pro negativní multiplikátor. Když jsou ty v multiplikátoru seskupeny do dlouhých bloků, Boothův algoritmus provede méně sčítání a odčítání než normální multiplikační algoritmus.

Viz také

Reference

^ Booth, Andrew Donald (1951) [1950-08-01]. „Podepsaná technika binárního násobení“ (PDF). Quarterly Journal of Mechanics and Applied Mathematics. IV (2): 236–240. Archivováno (PDF) od originálu 16. 7. 2018. Citováno 2018-07-16. Přetištěno Booth, Andrew Donald. Podepsaná technika binárního násobení. Oxford University Press. str. 100–104.
^ Chen, Chi-hau (1992). Příručka pro zpracování signálů. CRC Press. str. 234. ISBN 978-0-8247-7956-6.

Další čtení

Collin, Andrew (jaro 1993). „Počítače Andrewa Bootha na Birkbeck College“. Vzkříšení. Londýn: Computer Conservation Society (5).
Patterson, David Andrew; Hennessy, John Leroy (1998). Organizace a design počítače: Rozhraní hardware / software (Druhé vydání.). San Francisco, Kalifornie, USA: Nakladatelé Morgan Kaufmann. ISBN 1-55860-428-6.
Stallings, William (2000). Počítačová organizace a architektura: Návrh výkonu (Páté vydání.). New Jersey: Prentice-Hall, Inc. ISBN 0-13-081294-3.
Savard, John J. G. (2018) [2006]. „Pokročilé aritmetické techniky“. quadibloc. Archivováno z původního dne 2018-07-03. Citováno 2018-07-16.

externí odkazy

[Booth_1951-1] Booth, Andrew Donald (1951) [1950-08-01]. „Podepsaná technika binárního násobení“ (PDF). Quarterly Journal of Mechanics and Applied Mathematics. IV (2): 236–240. Archivováno (PDF) od originálu 16. 7. 2018. Citováno 2018-07-16. Přetištěno Booth, Andrew Donald. Podepsaná technika binárního násobení. Oxford University Press. str. 100–104.

[Chen_1992-2] Chen, Chi-hau (1992). Příručka pro zpracování signálů. CRC Press. str. 234. ISBN 978-0-8247-7956-6.

[1]

[2]