« poprzedni punkt  następny punkt »


3. Mnożenie

Realizacja układowa mnożenia jest trudniejszą od układów wykonujących dodawanie lub odejmowanie. Algorytm mnożenia jest też bardziej złożony.

Rozpatrzmy najpierw operację mnożenia dwóch czterobitowych liczb w kodzie NKB na przykładzie liczb dodatnich +5 i +6. Wykonajmy to działanie tak jak to się robi dla liczb dziesiętnych:

Otrzymany rezultat jest liczbą siedmiobitową. W ogólnym przypadku wynik może mieć podwójną długość (suma bitów argumentów), a więc w naszym przykładzie mógłby być ośmiobitowy. Należy zauważyć, że działanie wykonano poprzez jednoczesne sumowanie czterech liczb. Komputery są tak skonstruowane, że wszystkie działania arytmetyczne wykonuje się jedynie na dwóch argumentach. Trzeba zatem przedstawiony algorytm zmodyfikować tak, aby wykonać go krokowo.

Dla tego samego przykładu weźmy czterobitową mnożną MN=0101 i ośmiobitowy mnożnik RH,MK = 00000110. Takie oznaczenia mnożnej i mnożnika będą wygodne przy opisie realizacji układu. Oznaczenie mnożnika można interpretować jako słowo podwójnej długości (złożenie czterobitowego słowa RH i czterobitowego słowa MK).

Algorytm mnożenia składa się z tylu kroków ile bitów mają argumenty. W naszym przykładzie wykonamy 4 kroki algorytmu. W każdym kroku algorytmu wykonywane są dwie operacje: warunkowe dodawanie i przesuwanie. Warunkowe dodawanie oznacza, że w zależności od wartości bitu warunku jest wykonywane dodawanie różnych argumentów. Bitem warunku jest bit na najmniej znaczącej pozycji liczby RH,MK. Jeśli jest on równy 1, to do liczby RH (bardziej znacząca część liczby RH,MK) jest dodawany mnożna MN. Jeśli jest on równy 0, to do liczby RH jest dodawane zero. Po wykonaniu dodawania liczba RH,MK jest przesuwana o jedną pozycję w prawo, a na najbardziej znaczącą pozycję wpisywane jest 0 (tylko w kodzie NKB, bo w innych kodach wpisywany jest bit znaku, co zostanie dalej pokazane).

Wykonajmy przedstawiony algorytm na podanych wcześniej liczbach 4-bitowych.

W pierwszym kroku najmniej znaczący bit mnożnika MK jest równy 0, więc do RH dodaje się zero, a następnie przesuwa się całe słowo RH,MK w prawo. W drugim i trzecim kroku najmniej znaczący bit liczby MK jest równy 1 i dlatego do RH jest dodawana liczba MN. W czwartym kroku najmniej znaczący bit MK jest równy 0 i dlatego do RH dodaje się 0. Po czwartym kroku wartość liczby RH,MK wynosi 3010, co jest wynikiem prawidłowym.

Spróbujmy zaprojektować układ realizujący powyższy algorytm dla liczb czterobitowych. Weźmy czterobitowy rejestr MN, ośmiobitowy rejestr przesuwający RH,MK i blok ALU (jak np. omówiony wcześniej układ 381). Na rysunku X.1 pokazano układ wraz z blokiem sterowania, którego zadaniem jest generowanie odpowiednich sygnałów sterujących rejestrami i sumatorem w każdym kroku algorytmu. Sygnały sterujące wskazują argumenty dodawania i odpowiadają za kolejność działań.

Rysunek X.1. Układ mnożenia

Na początku algorytmu zapisuje się argumenty do rejestrów. Po załadowaniu rejestrów wykonywane są omówione kroki algorytmu. Układ sterowania wybiera argumenty podawane na wejścia sumatora w zależności od wartości najmniej znaczącego bitu. Następnie układ sterowania generuje sygnał dla rejestru RH,MK, który powoduje przesuwanie zawartości tego rejestru w prawo. Zadaniem układu sterowania jest także zliczanie liczby kroków, aby wskazać moment, w którym w rejestrze RH,MK znajdzie się końcowy wynik.

Odpowiedzmy teraz na pytanie jak modyfikować przedstawiony algorytm aby wykonać mnożenie w różnych kodach. Mnożenie w kodzie polaryzowanym można pominąć ponieważ, jak okaże się w następnym punkcie, liczby w tym kodzie wykorzystuje się w zastosowaniach gdzie się je tylko dodaje lub odejmuje.

Mnożenie w kodzie ZM

Algorytm mnożenia w kodzie ZM polega na wykonaniu przedstawionego wyżej algorytmu dla liczb w kodzie NKB biorąc jako argumenty moduły liczb. Następnie algorytm jest uzupełniany obliczeniem bitu znaku. Bit znaku wyniku jest funkcją XOR bitów znaków argumentów.

Mnożenie w kodzie U1

Algorytm mnożenia w kodzie U1 jest identyczny z przedstawionym algorytmem dla kodu NKB jeśli wartość mnożnika jest dodatnia. Jeśli wartość mnożnika jest ujemna, to algorytm należy uzupełnić wstępnym krokiem korekcyjnym i końcowym krokiem korekcyjnym. Wstępny krok korekcyjny polega na tym, że do rejestru RH wpisuje się mnożną. Końcowy krok korekcyjny polega na tym, że od zawartości rejestru RH należy odjąć mnożną (dodać ją z przeciwnym znakiem) i dodać wartość -0 ( jest to liczba minus zero czyli same jedynki) do rejestru MK.

Mnożenie w kodzie U2

Algorytm mnożenia w kodzie U2 jest identyczny z przedstawionym wyżej algorytmem w kodzie NKB jeśli wartość mnożnika jest dodatnia. Jeśli wartość mnożnika jest ujemna, to algorytm uzupełnia się końcowym krokiem korekcyjnym. Krok korekcyjny polega na tym, że po wykonaniu wszystkich kroków algorytmu należy odjąć mnożną (dodać ją z przeciwnym znakiem) od zawartości rejestru RH.

Przykłady mnożenia

Ponieważ mnożenie liczb w kodzie ZM różni się od mnożenia w kodzie NKB jedynie operacją obliczenia znaku, to zostanie tu pominięte. Celem ilustracji stosowania powyższych algorytmów dla kodów U1 i U2 pokazane one będą na przykładzie mnożenia liczb +2310 i -2610 oraz na drugim przykładzie mnożenia liczb -2310 i +2610.

Działania zostaną przeprowadzone na liczbach ośmiobitowych. Należy zwrócić uwagę na uzupełnianie najbardziej znaczącej pozycji liczby w czasie przesuwania w prawo. Pozycję tą uzupełnia się taką wartością bitu aby nie zmienić znaku liczby. Jeśli na najbardziej znaczącej pozycji było 0, to przesuwając liczbę w prawo uzupełnia się zerem. Jeśli na najbardziej znaczącej pozycji było 1, to przesuwając liczbę w prawo uzupełnia się jedynką. Jest to tzw. przesuwanie arytmetyczne.

Przykład

W rejestrze wynikowym jest liczba -59810 (zera są na pozycjach 29 + 26 + 24 + 22 + 21), a więc wynik prawidłowy.

Przykład

Czytelnikowi zalecamy sprawdzenie wyniku.

Przykład

W rejestrze wynikowym jest liczba -59810, a więc wynik prawidłowy.

Przykład

Czytelnikowi zalecamy sprawdzenie wyniku.


« poprzedni punkt  następny punkt »