202 203

202

X    V

5.11.5. Mnożenie binarna

Jak pamiętam? (patrz p. 1.2.10), algorytm mnożenia binarnego sprowadza się do ciągu przesunięć i dodawań iloczynów częściowych. Technicznie można to zrealizować w sposób szeregowy lub równoległy. Jedna z wersji szeregowego układu mnożącego liczby N-bltowe pokazana Jest na rys. 5*89.

Układ ten składa się z 2B-bitowego rejestru przesuwającego RX,tł-bltowe-go rejestru przesuwającego RY, układu bramkowania BR obliczającego (przepuszczającego lub nie) iloczyny częściowe oraz H-bitowego równoległego sumatora akumulującego, utworzonego z sumatora £ i rejestru buforowego RI, przechowującego sumę iloczynów częściowych.

Po wyzerowaniu rejestrów RX 1 RI, mnożną X wpisuje alę do pierwszych (mniej znaczących) N bitów rejestru RX, zaś mnożnik T równolegle do rejestru RY w takiej kolejności, aby bit najmniej znaczący (ISB) był pierwszym bitem bramkującym. Obliczanie iloczynu trwa H cykli zegarowych. W ciągu każdego cyklu zachodzi:

1)    obliczanie iloczynu częściowego w układzie bramkującym oraz sumy iloczynów częściowych w sumatorze £ |

2)    zapamiętanie sumy RI podczak przedniego zbocza impulsu zegarowego;

3)    przesunięcie operandów i RI i RI podczas tylnego zbocza impulsu zegarowego .

Nie pokazany na rysunku licznik cykli sygnalizuje zakończenie operacji mnożenia.

o

Rys. 5>89> Multlplicator szeregowy

Oczywiście, zamiast przesuwania mnożnej względem sumy Iloczynów częściowych, nośna przesuwać sumę względem mnożnej, co daje inną wersję mul-ttplikatora szeregowego.

1 równoległej realizacji algorytmu mnożenia przesuwanie odbywa się nie przy pomocy rejestrów, lecz odpowiedniego łączenia zespołu bramkowanych sumatorów. Schemat równoległego układu mnożącego liczby 4-bltowe pokazany jest na rys. 5*90. Z uwagi na brak rejestrów układ ten nie wymaga zerowania, wpisywania ani cyklicznego przesuwania, a dzięki temu działa znacznie szybciej.

Najszybszy układ mnożący liczby N-bitowe można zrealizować przy użyciu pamięci stałej o 2N wejściach adresowych i 2N wyjściach. Obecnie produkuje się tylko pamięci stałe dla mnożenia liczb 4-bitowych i z nich składa zestawy mnożące dla liczb dłuższych. Wymagana pojemność pamięci takiego multipllkatora wynosi 256 x 8 = 2k, co zostało rozdzielone pomiędzy dwa