Binární multiplikátor - Binary multiplier

Binární multiplikátor je elektronický obvod použitý v digitální elektronice , jako je počítač , na násobit dvě binární čísla .

K implementaci digitálního multiplikátoru lze použít různé počítačové aritmetické techniky. Většina technik zahrnuje výpočet množiny dílčích produktů, které jsou poté sečteny pomocí binárních sčítačů . Tento proces je podobný dlouhému násobení , kromě toho, že používá číselný systém báze 2 ( binární ) .

Dějiny

V letech 1947 až 1949 Arthur Alec Robinson pracoval pro společnost English Electric Ltd, jako studentský učeň a poté jako vývojový inženýr. Zásadně v tomto období studoval doktorát na univerzitě v Manchesteru, kde pracoval na návrhu hardwarového multiplikátoru pro raný počítač Mark 1. [3] Do konce 70. let však většina minipočítačů neměla instrukci násobení, a proto programátoři používali „rutinu násobení“, která opakovaně posouvá a hromadí dílčí výsledky, často psané pomocí odvíjení smyčky . Sálové počítače měly pokyny pro násobení, ale dělaly stejné druhy posunů a přidávaly jako „rutina násobení“.

První mikroprocesory také neměly instrukci pro násobení. Ačkoli se instrukce násobení stala běžnou u 16bitové generace, nejméně dva 8bitové procesory mají instrukci znásobení: Motorola 6809 , představená v roce 1978, a řada Intel MCS-51 , vyvinutá v roce 1980, a později moderní Atmel AVR 8bitové mikroprocesory přítomné v mikrokontrolérech ATMega, ATTiny a ATXMega.

Vzhledem k tomu, že díky integraci ve větším měřítku bylo k dispozici více tranzistorů na čip , bylo možné dát na jeden čip dostatek sčítačů pro součet všech dílčích produktů najednou, než znovu použít jeden sčítač pro zpracování každého dílčího produktu jeden po druhém.

Protože některé běžné algoritmy pro zpracování digitálního signálu tráví většinu času rozmnožováním, konstruktéři digitálních signálových procesorů obětují značnou plochu čipu, aby se násobení stalo co nejrychlejším; jednotka s jedním cyklem násobení a akumulace často spotřebovala většinu čipové oblasti raných DSP.

Binární dlouhé násobení

Metoda vyučovaná ve škole pro násobení desetinných čísel je založena na výpočtu dílčích součinů, jejich posunutí doleva a následném sečtení. Nejsložitější je získat dílčí produkty, protože to zahrnuje vynásobení dlouhého čísla jednou číslicí (od 0 do 9):

     123
   x 456
   =====
     738  (this is 123 x 6)
    615   (this is 123 x 5, shifted one position to the left)
 + 492    (this is 123 x 4, shifted two positions to the left)
   =====
   56088

Binární počítač provádí přesně stejné násobení jako desítková čísla, ale s binárními čísly. V binárním kódování je každé dlouhé číslo vynásobeno jednou číslicí (buď 0 nebo 1), a to je mnohem jednodušší než v desítkové soustavě, protože součin 0 nebo 1 je pouze 0 nebo stejné číslo. Znásobení dvou binárních čísel tedy spočívá ve výpočtu dílčích součinů (které jsou 0 nebo první číslo), jejich posunutí doleva a jejich sčítání (samozřejmě binární sčítání):

       1011   (this is binary for decimal 11)
     x 1110   (this is binary for decimal 14)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is binary for decimal 154)

To je mnohem jednodušší než v desítkové soustavě, protože neexistuje žádná tabulka násobení, kterou byste si pamatovali: pouze posouvá a přidává.

Tato metoda je matematicky správná a má tu výhodu, že malý procesor může provádět násobení pomocí posunu a přidávání funkcí své aritmetické logické jednotky místo specializovaného obvodu. Tato metoda je pomalá, protože zahrnuje mnoho meziproduktů. Tyto doplňky jsou časově náročné. Rychlejší multiplikátory mohou být navrženy tak, aby prováděly méně přidávání; moderní procesor může znásobit dvě 64bitová čísla 6 přidáním (místo 64) a může provést několik kroků souběžně.

Druhým problémem je, že základní školní metoda zvládá znak se samostatným pravidlem („ + s + výnosy +“, „ + s - výnosy -“ atd.). Moderní počítače vkládají znak čísla do samotného čísla, obvykle do zastoupení obou komplementů . To nutí proces násobení přizpůsobit tak, aby zvládl čísla dvou komplementů, a to proces ještě více komplikuje. Podobně procesory, které používají doplněk , znak a velikost , IEEE-754 nebo jiné binární reprezentace, vyžadují specifické úpravy procesu násobení.

Celá čísla bez znaménka

Předpokládejme například, že chceme znásobit dvě nepodepsaná osmibitová celá čísla dohromady: a [7: 0] a b [7: 0]. Můžeme vyrobit osm dílčích produktů provedením osmi jednobitových násobení, jednoho pro každý bit v multiplikátoru a :

 p0[7:0] = a[0] × b[7:0] = {8{a[0]}} & b[7:0]
 p1[7:0] = a[1] × b[7:0] = {8{a[1]}} & b[7:0]
 p2[7:0] = a[2] × b[7:0] = {8{a[2]}} & b[7:0]
 p3[7:0] = a[3] × b[7:0] = {8{a[3]}} & b[7:0]
 p4[7:0] = a[4] × b[7:0] = {8{a[4]}} & b[7:0] 
 p5[7:0] = a[5] × b[7:0] = {8{a[5]}} & b[7:0]
 p6[7:0] = a[6] × b[7:0] = {8{a[6]}} & b[7:0]
 p7[7:0] = a[7] × b[7:0] = {8{a[7]}} & b[7:0]

kde {8 {a [0]}} znamená opakování [0] (0. bit a) 8krát ( notace Verilog ).

Abychom získali náš produkt, musíme sečíst všech osm našich dílčích produktů, jak je ukázáno zde:

                                                p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0]
                                        + p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0
                                  + p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0     0
                            + p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0     0     0
                      + p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0     0     0     0
                + p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0     0     0     0     0
          + p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0     0     0     0     0     0
    + p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0     0     0     0     0     0     0
-------------------------------------------------------------------------------------------
P[15] P[14] P[13] P[12] P[11] P[10]  P[9]  P[8]  P[7]  P[6]  P[5]  P[4]  P[3]  P[2]  P[1]  P[0]

Jinými slovy, P [15: 0] se vytvoří součtem p 0, p 1 << 1, p 2 << 2 atd., Čímž vznikne náš konečný nepodepsaný 16bitový produkt.

Podepsaná celá čísla

Pokud b byl podepsané celé číslo namísto bez znaménka celé číslo, pak dílčí produkty budou muset mít byla přihlášení prodloužit až na šířku výrobku před sečtením. Pokud by a bylo celé číslo se znaménkem, pak by částečný součin p7 bylo třeba od konečného součtu odečíst, nikoli k němu přičíst.

Výše uvedený multiplikátor pole lze upravit tak, aby podporoval podepsaná čísla dvou doplňkových zápisů převrácením několika produktových výrazů a vložením jedničky nalevo od prvního dílčího produktového výrazu:

                                                    1  ~p0[7]  p0[6]  p0[5]  p0[4]  p0[3]  p0[2]  p0[1]  p0[0]
                                                ~p1[7] +p1[6] +p1[5] +p1[4] +p1[3] +p1[2] +p1[1] +p1[0]   0
                                         ~p2[7] +p2[6] +p2[5] +p2[4] +p2[3] +p2[2] +p2[1] +p2[0]   0      0
                                  ~p3[7] +p3[6] +p3[5] +p3[4] +p3[3] +p3[2] +p3[1] +p3[0]   0      0      0
                           ~p4[7] +p4[6] +p4[5] +p4[4] +p4[3] +p4[2] +p4[1] +p4[0]   0      0      0      0
                    ~p5[7] +p5[6] +p5[5] +p5[4] +p5[3] +p5[2] +p5[1] +p5[0]   0      0      0      0      0
             ~p6[7] +p6[6] +p6[5] +p6[4] +p6[3] +p6[2] +p6[1] +p6[0]   0      0      0      0      0      0
   1  +p7[7] ~p7[6] ~p7[5] ~p7[4] ~p7[3] ~p7[2] ~p7[1] ~p7[0]   0      0      0      0      0      0      0
 ------------------------------------------------------------------------------------------------------------
P[15]  P[14]  P[13]  P[12]  P[11]  P[10]   P[9]   P[8]   P[7]   P[6]   P[5]   P[4]   P[3]   P[2]   P[1]  P[0]

Kde ~ p představuje doplněk (opačná hodnota) p.

Ve výše uvedeném bitovém poli existuje mnoho zjednodušení, která nejsou zobrazena a nejsou zřejmá. Sekvence jednoho komplementovaného bitu následované nekomplementovanými bity implementují trik komplementu dvou, aby se zabránilo prodloužení znaménka. Sekvence p7 (nekomplementovaný bit následovaný všemi komplementovanými bity) je, protože odečteme tento termín, takže pro začátek byly všechny negovány (a 1 byla přidána v nejméně významné pozici). U obou typů sekvencí je poslední bit převrácen a přímo pod MSB by měla být přidána implicitní -1. Když se sečtou +1 z negace komplementu těchto dvou pro p7 v bitové pozici 0 (LSB) a všechny -1 v bitových sloupcích 7 až 14 (kde jsou umístěny všechny MSB), lze je zjednodušit na jedinou 1 že „magicky“ plave doleva. Vysvětlení a důkaz, proč nám převrácení MSB šetří příponu znaménka, najdete v počítačové aritmetické knize.

Čísla s plovoucí desetinnou čárkou

Binární plovoucí číslo obsahuje znaménkový bit, významné bity (známé jako význam) a exponentní bity (pro jednoduchost nepovažujeme základní a kombinační pole). Znaménkové bity každého operandu jsou XOR'd, aby se získal znak odpovědi. Poté se přidají dva exponenty, aby se získal exponent výsledku. Nakonec vynásobením významu každého operandu vrátí význam výsledku. Pokud je však výsledek binárního násobení vyšší než celkový počet bitů pro konkrétní přesnost (např. 32, 64, 128), je vyžadováno zaokrouhlení a exponent se příslušně změní.

Hardwarová implementace

Proces násobení lze rozdělit do 3 kroků:

  • generování dílčího produktu
  • snížení dílčího produktu
  • výpočet konečného produktu

Starší multiplikátorové architektury využívaly k součtu každého dílčího produktu přesouvač a akumulátor, často jeden dílčí produkt za cyklus, obchodování mimo rychlost pro oblast zápustky. Moderní architektury multiplikátorů používají (Modified) Baugh – Wooleyův algoritmus , Wallaceovy stromy nebo Dadda multiplikátory k přidání dílčích produktů dohromady v jednom cyklu. Výkon implementace Wallaceova stromu je někdy vylepšen upraveným Boothovým kódováním jednoho ze dvou multiplicand, což snižuje počet dílčích produktů, které je třeba sčítat.

Pro rychlost vyžadují multiplikátory řazení a přidávání rychlý sčítač (něco rychlejšího než ripple-carry).

Multiplikátor „jednoho cyklu“ (nebo „rychlý multiplikátor“) je čistá kombinační logika .

V rychlém multiplikátoru obvykle proces redukce částečného produktu nejvíce přispívá ke zpoždění, výkonu a oblasti multiplikátoru. Pokud jde o rychlost, fáze „snížení dílčího produktu“ jsou obvykle implementovány jako sčítač pro uložení a uložení složený z kompresorů a krok „vypočítat konečný produkt“ je implementován jako rychlý sčítač (něco rychlejšího než zvlnění).

Mnoho rychlých multiplikátorů používá plné kompresory jako kompresory („kompresory 3: 2“) implementované ve statickém CMOS . K dosažení lepšího výkonu ve stejné oblasti nebo stejného výkonu v menší oblasti mohou multiplikátorové návrhy používat kompresory vyššího řádu, jako jsou například kompresory 7: 3; implementovat kompresory do rychlejší logiky (taková logika přenosové brány, logika průchodového tranzistoru, domino logika ); připojte kompresory v jiném vzoru; nebo nějaká kombinace.

Příklad obvodů

2bitový 2bitový binární multiplikátor

Viz také

Reference

externí odkazy