202 203

202

X    Y

5.11.3. Mnożenie binarne

Jak pamiętamy (patrz p. 1.2.10), algorytm mnożenia binarnego sprowadza się do ciągu przesunięć 1 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-bitowe pokazana jest na rys. 5*39.

Układ ten składa się z 2N-bitowego rejestru przesuwającego RX,N-bitowe-go rejestru przesuwającego RY, układu bramkowania BR obliczającego (przepuszczającego lub nie) Iloczyny częściowe oraz N-bltowego równoległego sumatora skumulującego, utworzonego z sumatora £ 1 rejestru buforowego RI, przechowującego sumę iloczynów częściowych.

Po wyzerowaniu rejestrów RX 1 RI, mnożną X wpisuje się 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 N 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 X |

2)    zapamiętanie sumy RI podcz&k przedniego zbocza impulsu zegarowego;

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

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

o

Rys. 5.89. Multiplisator szeregowy

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

W 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 ą-bitowe 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.

Hajsiybszy układ mnożący liczby H-bitowe można zrealizowaó przy użyciu pamięci stałej o 2N wejściach adresowych i 2H 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 multiplikatora wynosi 256 x 8 = 2k, co zostało rozdzielone pomiędzy dwa