Snížení počtu účastníků - Reduction of summands
Redukce součtů je algoritmus pro rychlé binární násobení binárních celých čísel bez znaménka. Provádí se ve třech krocích: výroba součtů, redukce součtů a součet.
Kroky
Výroba sběratelů
V binárním násobení bude každá řada součtů buď nula, nebo jedno z čísel, která mají být vynásobena. Zvažte následující:
1001 x1010 ----- 0000 1001 0000 1001
Druhá a čtvrtá řada sčítání jsou ekvivalentní prvnímu členu. Výroba součtů vyžaduje pro každé součet jednoduchou bránu AND . Vzhledem k dostatečnému počtu AND bran bude čas na vytvoření součtů jeden cyklus aritmetické logické jednotky .
Snížení počtu účastníků
Summands jsou redukovány pomocí běžného 1-bitového plného sčítače, který přijímá dva 1-bitové výrazy a carry-in bit. Produkuje částku a realizaci. Plné sčítače jsou uspořádány tak, aby součet zůstal ve stejném sloupci sčítání, ale provedení je posunuto doleva. V každém kole redukce jsou použity tři bity v jednom sloupci jako dva termíny a přenos pro celou sčítačku, čímž se pro sloupec vytvoří jeden bit součtu. Tím se sníží bity ve sloupci o faktor 3. Sloupec vpravo se však přesune nad prováděcí bity, čímž se bity ve sloupci zvýší o třetinu počtu řádků sčítání. V nejhorším případě bude redukce 2/3 počtu řádků na kolo redukce.
Následující text ukazuje, jak probíhá první kolo redukce. Všimněte si, že všechny „prázdné“ pozice součtů jsou považovány za nulové (a. Se zde používá jako indikátor „předpokládaných nulových hodnot“). V každém řádku jsou horní tři bity tři vstupy do plného sčítače (dva termíny a přenos). Součet se umístí do horního bitu sloupce. Provedení je umístěno ve druhé řadě sloupce vlevo. Spodní bit je jeden posuv do sčítačky. Součet tohoto sčítače je umístěn ve třetím řádku sloupce. Provedení je ignorováno, protože bude vždy nulové, ale záměrně by bylo umístěno ve čtvrtém řádku sloupce vlevo. Pro návrh je důležité si uvědomit, že řádky 1, 3, 5, ... (počítané shora) jsou vyplněny součty ze samotného sloupce. Řádky 2, 4, 6, ... jsou vyplněny hodnotami provedení ze sloupce vpravo.
1011 x0110 ----- ...0000 ..1011. .1011.. 0000... ------- 0111010 000100. 00000..
Redukce se provádí znovu úplně stejným způsobem. Tentokrát jsou zajímavé pouze horní tři řady součtů, protože všechny ostatní součty musí být nulové.
0111010 000100. 00000.. ------- 0110010 001000.
Pokud existují pouze dvě významné řady součtů, redukční cykly končí. Základní plná sčítačka obvykle vyžaduje tři cykly aritmetické logické jednotky . Proto je každý cyklus redukce obvykle 3 cykly dlouhý.
Shrnutí
Pokud zbývají pouze dva řádky sčítání, jsou přidány pomocí rychlého sčítače. Existuje mnoho návrhů rychlých sčítání, z nichž každý lze použít k dokončení tohoto algoritmu.
Čas výpočtu
Doba výpočtu pro algoritmus redukce summandů je: T = 1Δt + r3Δt + FA (kde r je počet redukčních cyklů a FA je čas rychlého sčítače na konci algoritmu).