Temat:
Układy arytmetyczne II: mnożenie liczb binarnych,
zapis stało i zmiennoprzecinkowy
Rozdziały wykładu:
1. Mnożenie liczb binarnych w zapisie uzupełnień do 2
1.1 Metoda  przesuń i dodaj
1.2 Mnożenie metodą Booth a/Wallace a
1.3 Mnożenie metodą macierzową
2. Formaty słów liczbowych w systemach komputerowych
2.1 Format stałoprzecinkowy
2.2 Format zmiennoprzecinkowy
3. Arytmetyka zmiennoprzecinkowa
3.1 Dodawanie zmiennoprzecinkowe
3.2 Mnożenie zmiennoprzecinkowe
Mnożenie liczb binarnych w zapisie uzupełnień do 2
Znane są 3 główne metody realizacji mnożenia liczb w zapisie uzupełnień do 2:
" metoda  przesuń i dodaj ,
" metoda Booth a/Wallace a
" metoda macierzowa
Mnożenie liczb binarnych metodą przesuń i dodaj
Mnożymy dwie liczby n-bitowe X (mnożna) i Y (mnożnik) w zapisie uzupełnień do 2.
Wykonanie w układzie rejestrów podłączonych do sumatora binarnego:
" rejestr Q zawiera X,
" rejestr M zawiera Y.
" rejestr A połączony w szereg z Q i rejestrem S  tworzy rejestr SAQ.
Rejestry M, A, Q są n-bitowe.
Rejestr S jest 1-bitowy.
Schemat blokowy układu mnożenia metodą  przesuń i dodaj
M(n-1) M(0)
Y
M
A(n-1) A(0) Q(n-1) Q(0)
10 X
S A Q
SAQ(2n) SAQ(2n-1) SAQ(n-1)
SAQ(n) SAQ(0)
Metoda jest wzorowana na ręcznym dziesiętnym mnożeniu.
Metoda dodaje mnożną Y do siebie tyle razy, ile wynosi X.
Zawartość M jest dodawana do A dla kolejnych jedynek w X w rejestrze Q, począwszy od
bitu najmniej znaczącego, z przesuwaniem całego rejestru SAQ o jedną pozycjęw prawo po
każdym dodaniu M oraz po każdym wykryciu zerowego bitu mnożnika na zerowej pozycji
rejestru Q.
Otrzymany wynik ma podwójną liczbę bitów w porównaniu z agumentami mnożenia.
Otrzymany wynik można sprowadzić do formatu argumentów poprzez obcięcie połowy
bitów i zaokrąglenie.
Zaokrąglenie binarne
" Jeśli pierwszy bit z obciętej części jest równy 1
" dodanie na najmniej znaczącej pozycji obciętego wyniku 1
" wykonanie propagacji przeniesień
" Jeśli pierwszy bit z obciętej części jest równy 0
" brak działań po obcięciu bitów
Algorytm mnożenia
A=0; S=0; Inicjalizacja A i S.
M=Y; Wprowadzenie mnożnej do M.
Q=X; Wprowadzenie mnożnika do Q.
If (Q(n -1)=  1 then Jeśli mnożnik jest ujemny, zastąp M i Q
M= - M; przez ich uzupełnienia do 2, wtedy Q będzie zawsze
Q = -Q; dodatni.
EndIf;
S = M(n-1); Wprowadzenie znaku M do S.
For i in 1 to n
If(Q(0) =  1 then
A = M + A; Dodanie M do A Q razy.
End If;
For j in 1 to 2n
SAQ(j-1) = SAQ (j); Przesunięcie SAQ o 1 pozycje w prawo,
EndFor; bez zmiany znaku S.
EndFor;
Przykład:
Pomnóż X = 01010 przez Y = 11001 (czyli 10 przez  7 w systemie dziesiętnym).
S A Q Operacja do wykonania
po zbadaniu Q
0 00000 01010 przesuń w prawo
0 00000 00101 dodaj M do A
1 11001 00101 przesuń w prawo
1 11100 10010 przesuń w prawo
1 11110 01001 dodaj M do A
1 10111 01001 przesuń w prawo
1 11011 10100 przesuń w prawo
1 11101 11010
Wynik 11101 11010 (czyli  70 w systemie dziesiętnym).
Mnożenie metodą Booth a/Wallace a
" Mnożenie metodą  przesuń i dodaj dla n-bitowych argumentów wymaga n badań
kolejnych bitów mnożnika i tylu dodawań mnożnej do wyniku ile jedynek wystąpiło w
mnożniku - zupełnie sekwencyjny charakter algorytmu .
Metoda Booth a/Wallace a jest szybsza, gdyż wprowadza zrównoleglenie operacji.
" wiele równolegle pracujących układów mnożących mnożną przez trójki bitów mnożnika
(metoda Booth a)
" wiele równolegle pracujących układów sumatorów ustawionych w strukturę drzewa
Wallace a, które dodają do siebie wyniki mnożeń z odpowiednimi przesunięciami.
Algorytm Booth a
Zastępuje mnożenie przez nieprzerwane ciągi zer i jedynek mnożnika, przez przesunięcia
wyniku z  korekcyjnym odjęciem mnożnej od wyniku, odpowiadającym pozycji najmniej
znaczącej jedynki w ciągu.
Np. jeśli mnożymy mnożną Y przez mnożnik X o postaci 10111100
to mnożnik X można przedstawić jako X = -1 " 27 + (26  22)
1 0 1 1 1 1 0 0
-27 26 25 24 23 22 21 21
Wtedy mnożenie X " Y można przedstawić formułą:
X " Y = [- 1 " 27 + (26  22)] * Y = - 27 Y + 26 Y 22 Y .
W układzie typu  przesuń i dodaj mnożącym Y przez 10111100 trzeba:
" przesunąć wynik o 2 miejsca w prawo dla prawych bitów 0 mnożnika 00,
" odjąć mnożną Y od wyniku (czyli dodać -Y) i przesunąć wynik w prawo dla bitu 1
najbardziej na prawo w ciągu jedynek w mnożniku 101111 00,
" tylko przesuwać wynik o 1 w prawo dla każdego kolejnego bitu 1 w mnożniku 10111100,
" dodać mnożną do wyniku i przesunąć wynik o 1 w prawo dla pierwszego bitu 0 w
mnożniku po ciągu jedynek 10111100
" dla najbardziej lewego bitu 1 w mnożniku, odjąć mnożną od wyniku i przesunąć wynik o 1
w prawo 10111100.
Struktura drzewa Wallace a
W strukturze drzewa Wallace a wykorzystane są specjalne sumatory trójargumentowe z
pamiętaniem przeniesień (CSA  Carry Save Adder)
" pozostawiają wynik dodawania w postaci dwu słów: słowa bitów sumy i słowa bitów
przeniesień.
Sumatory CSA działają bardzo szybko, gdyż:
" nie ma w nich propagowania przeniesień,
" generowane są szybko słowa przeniesień na podstawie trójek bitów argumentów na
kolejnych pozycjach.
Na końcu serii dodawań, wynik sprowadza się do postaci jednego słowa.
Stosowany jest do tego sumator z przeniesieniami jednoczesnymi (CLA - Carry Look-Ahead
Adder).
Struktura drzewa Wallace a dodaje iloczyny częściowe wytworzone w trakcie mnożenia
mnożnej przez trójki bitów mnożnika.
Schemat blokowy układu mnożącego metodą Booth a/Wallace a
iloczyn iloczyn iloczyn iloczyn iloczyn iloczyn iloczyn iloczyn
Iloczyny
Y przez Y przez Y przez Y przez Y przez Y przez Y przez Y przez
mnożnej
x15x14x13 x13x12x11 x11x10x9 x9x8x7 x7x6x5 x5x4x3 x3x2x1 x1x00
i trójek bitów
mnożnika
CSA CSA
Carry Save Adder
Wynik w postaci 2 słow:
CSA CSA
słowa bitów sum,
słowa bitów przesunięć
CSA
CSA
Carry Look-Ahead Adder
CLA
(z przeniesieniami jednoczesnymi)
Mnożenie metodą macierzową
Formułę mnożenia argumentów binarnych można sprowadzić, poprzez odpowiednie
grupowanie wyrazów i wprowadzenie negacji bitów, do postaci, która stanowi podstawę dla
zbudowania macierzowego (matrycowego) układu mnożącego.
Układ jest zbudowany z sumatorów 1-bitowych.
W matrycy elementarnych sumatorów występuje tyle wierszy sumatorów ile bitów maja
mnożone liczby.
Na wejścia początkowej warstwy sumatorów oraz na wejścia przeniesień w niższych
warstwach, wprowadzane są odpowiednie iloczyny logiczne bitów mnożnika i mnożnej
(proste lub zanegowane).
Wyniki elementarnych sumowań (bity sumy i przeniesień) są podawane na wejścia
sumatorów w niższych warstwach lub stanowią bity wyniku iloczynu, w zależności od
pozycji danego sumatora w matrycy.
Schemat blokowy układu mnożącego metodą macierzową
y 5 x 0 0 y 4x 0 y 1x 3 y 3 x 0 y 0 x 3 y 2 x 0 0 y 1 x 0 0 y 0 x 0
y 4x 1 y 3x 1 y 2x 1 y 1x 1 y 0x 1
SUM
SUM SUM SUM SUM
y 5 x 1
y 4x 2 y 3x 2 y 2x 2 y 1x 2 y 0x 2
SUM SUM SUM SUM SUM
y 5 x 2
y 4x 3 y 3x 3 y 2x 3
x 3
SUM SUM SUM SUM SUM
y 5x 3
y 5 y 5
SUM SUM SUM SUM
1
x 3
SUM SUM
P 9 P 8 P 7 P 6 P 5 P 4 P 3 P 2 P 1 P 0
Formaty słów liczbowych w systemach komputerowych
Format słowa podaje budowę słowa z pól bitowych i ich przeznaczenie.
" Jeżeli liczba jest zapisana w jednym słowie komputera to obliczenia będą prowadzone w
tzw. pojedyńczej precyzji.
" Jeżeli do zapisu liczby wykorzystuje się dwa lub więcej słów to mówi się o wielokrotnej
precyzji obliczeń, np. podwójnej.
Wyróżniamy dwa formaty zapisu liczb: format stałoprzecinkowy i format
zmiennoprzecinkowy.
Format stałoprzecinkowy
W formacie stałoprzecinkowym słowa reprezentującego liczbę mamy:
" pole znaku (bit znaku)
" pole liczbowe (bity wartości liczby).
Pole
znaku
Pole liczbowe
an an-1 a0 a-1 a-m
Pozycja przecinka
liczbowe
Format stałoprzecinkowy pozwala na zapis liczb całkowitych, ułamkowych i mieszanych.
Miejsce przecinka binarnego jest ustalone między pozycjami bitowymi wyznaczającymi
koniec zapisu części całkowitej (numery pozycji nieujemne) i początek zapisu części
ułamkowej (numery pozycji ujemne).
Pole
znaku
Pole liczbowe
a0 a-1 a-2 a-m
Pole
znaku
Pole liczbowe
an an-1 an-2 a0
Skrajne pozycje przecinka w zapisie staloprzecinkowym
W polu liczbowym, wagi pozycji zapisu liczby w części całkowitej są kolejnymi dodatnimi
całkowitymi potęgami podstawy p (rosnącymi od zera w lewo) a wagi części ułamkowej są
kolejnymi ujemnymi potęgami podstawy p (malejącymi od  1 w prawo).
Dla słowa o długości (m+1) bitów z przecinkiem umieszczonym zaraz na prawo od pola
(bitu) znaku, zakresy reprezentowalnych liczb wynoszą:
dla zapisu znak-moduł -1 + 2-m, , 1 - 2-m
dla zapisu uzupełnień do 2 -1, , 1 - 2-m
Dla słowa o długości (m+1) bitów z przecinkiem umieszczonym na prawym końcu pola
liczbowego, zakresy reprezentowalnych liczb wynoszą:
dla zapisu znak-moduł - (2m  1), , 2m  1
dla zapisu uzupełnień do 2 - 2m, , 2m  1
Skala obliczeń.
Skalowanie polega na pomnożeniu wszystkich liczb uczestniczących w obliczeniu przez stały
współczynnik równy p-k,
gdzie p jest podstawą systemu liczbowego
k nazywa się skalą obliczeń.
W praktyce skalowanie powoduje zmianę miejsca przecinka w zapisach liczbowych
argumentów przed wykonaniem stałoprzecinkowych operacji arytmetycznych.
Do ustalenia skali obliczeń stałoprzecinkowych służy specjalna instrukcja języka
wewnętrznego komputera.
Skalę obliczeń należy ustawić tak, by wyniki obliczeń były reprezentowalne (mieściły się) na
liczbie miejsc przed przecinkiem wyznaczonej przez przyjętą skalę dla argumentów.
Przyklady
Liczba 5.25 w skali 0 ma zapis 00101,010
Ta liczba w skali 3 ma zapis 0,1010100
W skali 5 0,0010101
W skali  4 01010100
Liczba -5.25 ma skali 0 zapis 110101,110
Ta liczba w skali 3 ma zapis 110,101110
W skali 5 1,10101110
W skali  4 110101110
Format zmiennoprzecinkowy ( zmiennopozycyjny)
Aby zapisać liczbę A w formacie zmiennoprzecinkowym, należy liczbę A przedstawić w
postaci iloczynu:
A = M pC gdzie M nazywamy mantysą liczby A
p - podstawa używanego systemu liczbowego
(2 dla zapisu binarnego)
C nazywamy cechą (wykładnikiem) - jest to wykładnik
użytej potęgi podstawy.
Dla p = 2 czyli binarnego zapisu zmiennoprzecinkowego,
Przedstawia się osobno mantysę i cechę w postaci dwu liczb binarnych w zadanym
pozycyjnym zapisie binarnym np. zapisie uzupełnień do 2 (U2).
Te dwie liczby binarne, mantysę i cechę należy następnie umieścić we wspólnym słowie
reprezentującym liczbę A.
W związku tym w słowie liczbowym w formacie zmiennoprzecinkowym wyróżnia
się pole mantysy i pole cechy. Wykładniczy zapis wartości liczby eliminuje w tym formacie
potrzebę użycia pojęcia skali liczbowej, której rolę pełni cecha.
Format zapisu zmiennoprzecinkowego
Pole cechy Pole mantysy
m0 m1 mn ck ck-1 c0
bity znaku
We wcześniejszych mikroprocesorach stosowano rożną kolejność pól cechy i mantysy w
słowie liczbowym, taką jak np. podana poniżej kolejność stosowana dla procesorów 16-
bitowych. Dla uzyskania przenoszalności programów wszystkie współczesne mikroprocesory
32-bitowe przyjęły standardowy format opracowany przez Instytut tandardów amerykańskiej
organizacji IEEE, pokazany na rysunku poniżej drugiej kolejności.
mantysa 7-bitowa
1 wykładnik 8-bitowy
1 mantysa 15- wykładnik 8-
bitowa bitowy
znak
mantysy
Formaty zapisu zmiennoprzecinkowego w pojedynczej i podwójnej precyzji
(przy długości słowa 16-bitów)
31 30 0
23 22
S wykładnik mantysa
znak mantysy
63
62 52 51 0
S wykładnik mantysa
znak mantysy
Formaty zapisu zmiennoprzecinkowego w pojedynczej i podwójnej precyzji
(standard IEEE 754 przy długości słowa 32 bity)
W formacie zmiennoprzecinkowym dana liczba może mieć wiele przedstawień, zależnych od
wyboru cechy.
Postać znormalizowana jest to wyróżniony rodzaj reprezentacji, przy którym moduł
mantysy przyjmuje największą możliwą wartość.
Przy normalizacji przesuwa się mantysę w lewo, aby najbardziej znacząca jedynka znalazła
się przy polu znaku mantysy, a potem koryguje się cechę.
Każdemu przesunięciu mantysy w lewo odpowiada pomnożenie jej wartości przez 2 czyli
korekta cechy polega na odjęciu od niej 1.
Arytmetyka zmiennoprzecinkowa
Dodawanie zmiennoprzecinkowe
Najpierw wykonywane jest porównanie wykładników obu składników.
Następnie wykonywane jest uzupełnienie mniejszego wykładnika do wartości większego, z
jednoczesnym takim zmniejszeniem mantysy, aby wartość modyfikowanego składnika
pozostała taka sama.
Dodanie jedynki do wykładnika odpowiada pomnożeniu składnika przez 2. Aby składnik nie
zmienił swej wartości, trzeba mantysę podzielić przez 2. Odpowiada temu przesunięcie
mantysy o jedno miejsce w prawo.
Po wyrównaniu wykładników, można dodawać mantysy.
W formule dodawania składników zapisanych jako iloczyn mantys i potęg wykładników
odpowiada temu wyciągnięcie czynnika 2 do potęgi wykładnika z obu składników przed
nawias i dodanie mantys w nawiasie.
Separujemy przedtem znaki składników w osobnych przerzutnikach. Dodawanie
wykonujemy w sumatorze.
Następnie wynik możemy znormalizować wstawiając znak wyniku. Jeśli potrzeba, wynik
można zaokrąglić.
Schemat blokowy dodawania zmiennoprzecinkowego
Wykładnik E Wykładnik E 1 Mantysa E 2 Mantysa E 1
2
Porównanie wykładników Przesuń mantysę
Dodaj / Odejmij mantysy
Normalizacja i zaokrąglenie wyników
Wynikowy wykładnik Wynikowa mantysa
Przykład.
Mamy dodać dwie liczby binarne w zapisie uzupełnień do 2 i formacie
zmiennoprzecinkowym podane poniżej.
Dodajemy A = mA 2wA do B = mB 2wB .
Mamy obliczyć A + B = mA 2wA + mB 2wB.
Mantysa
Wykładnik
0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1
0 1 1 0 1 1 0 1 0 0 0 0 0 1 0 0
Porównujemy wykładniki
Uzupełniamy wykładnik pierwszej liczby, dodając 1 tak, aby był równy wykładnikowi
drugiej liczby (mnożymy liczbę przez 2).
Aby wartość tej liczby nie uległa zmianie, dzielimy mantysę przez 2, co odpowiada
przesunięciu mantysy o 1 bit w prawo.
Zauważmy, ze przy takim przesunięciu wszystkie bity mantysy przesuwają się
na pozycje o wagach dwa razy mniejszych. Wartość liczby po przesunięciu ( suma
iloczynów wag i wartości bitów na wszystkich pozycjach) będzie więc dwa razy mniejsza.
0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0
0 1 1 0 1 1 0 1 0 0 0 0 0 1 0 0
Mając równe wykładniki możemy umownie  wyciągnąć przed nawias czynnik 2 do potęgi
wykładnika
A + B = 0.5 mA 2wB + mB 2wB = 2wB (0.5 mA + mB).
Dodajemy mantysy w sumatorze liczb w zapisie U2, rozszerzonym o jedną pozycję w lewo,
dla zapisania bitu znaku przy ewentualnym nadmiarze.
Po dodaniu mamy wynik w postaci trzech części: bitu rozszerzenia, mantysy i cechy.
Jak widzimy w przykładzie wystąpił nadmiar (wynik pozornie zmienił znak)
rozsz. cecha
wynikowa mantysa
0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0
Trzeba teraz sprowadzić wynik z nadmiarem do poprawnej postaci.
Przesunięcie mantysy z rozszerzeniem w prawo o jedną pozycję. Aby skompensować to
przesunięcie (zmniejszenie mantysy 2 razy), musimy zwiększyć cechę o 1 ( zwiększenie
czynnika potęgowego zapisu liczby 2 razy).
ostateczna mantysa cecha
0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1
" Przy dodawaniu jedynki do cechy przy kompensacji nadmiaru mantysy, może wystąpić
nadmiar arytmetyczny cechy, który musi być sygnalizowany jako błąd obliczeń do
użytkownika, gdyż uniemożliwia poprawne wykonanie operacji dodawania.
" Wynik dodawania może być normalizowany. W tym przypadku przesuwamy mantysę w
lewo z kompensacją zmian poprzez zmniejszanie wykładnika. W tym przypadku może
wystąpić niedomiar wykładnika, który też jest sygnalizowany do użytkownika.
Mnożenie zmiennoprzecinkowe
Mnożenie liczb binarnych w formacie zmiennoprzecinkowym odbywa się poprzez
pomnożenie mantys i dodanie wykładników obu liczb.
Mnożąc A=mA 2wB przez B=mB 2wB
mamy A B = ( mA mB) 2wA+wB.
Musimy dodać wykładniki obu liczb oraz pomnożyć ich mantysy.
Schemat blokowy dodawania zmiennoprzecinkowego
Wykładnik A Wykładnik B1 Mantysa A2 Mantysa B1
2
Dodaj Pomnóż
Normalizacja i zaokrąglenie wyników
Wynikowy wykładnik Wynikowa mantysa