Mno enie
Skalowanie w systemach naturalnych
Skalowanie  mno enie przez całkowit pot g podstawy �k.
" skalowania mo na składa poniewa
�kX= �& ��X
" mno enie przez ka d dodatni pot g podstawy
daje w wyniku cykliczne przemieszczenie cyfr w lewo, poniewa
i=k -1 i=k -1 i=k
i i+1 i
�
"x � = "x � = "x �
i i i-1
i=-m i=-m i=-m+1
" mno enie przez ka d ujemn pot g podstawy
daje w wyniku cykliczne przemieszczenie cyfr w prawo, poniewa
i=k -1 i=k -1 i=k -2
-1 i i-1 i
�
"x � = "x � = "x �
i i i+1
i=-m i=-m i=-m-1
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 1
 Mno enie
Skalowanie w systemach uzupełnieniowych i dopełnieniowych
Je li najwy sz pozycj liczby nie jest cyfra rozszerzenia xk = �(xk -1)(� -1),
to w wyniku mno enia przez � wyst pi nadmiar.
Je li k najwy szych pozycji liczby nie jest cyframi rozszerzenia,
to w wyniku mno enia przez �k wyst pi nadmiar.
W systemie uzupełnieniowym  rozszerzenie: xk = �(xk -1)(� -1)  otrzymamy
Xe = {�(xk -1)(� -1), xk -1, xk -2,..., x-m} �! � Xe = {xk -1, xk -2,..., x-m ,0},
W systemie dopełnieniowym nast pi cykliczne przemieszczenie cyfr
Xe = {�(xk -1)(� -1), xk -1, xk -2,..., x-m} �! � Xe = {xk -1, xk -2,..., x-m,�(xk -1)(� -1)}
Wynik skalowania odwrotnego (mno enia przez �-1) jest zawsze poprawny
-1
Xe = {xk -1, xk -2,..., x-m+1, x-m} �! � Xe = {�(xk -1)(� -1), xk -1, xk -2,..., x-m+1}
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 2
 Mno enie
Skalowanie w dwójkowym systemie uzupełnieniowym i dopełnieniowym
Wynikiem dodawania liczby do niej samej jest na ka dej pozycji:
xi + xi + ci = 2ci+1 + si �! ci+1 = xi , si = ci �! si+1 = xi
W systemie uzupełnieniowym, u ywaj c rozszerzenia, otrzymamy
Xe = {xk -1, xk -1, xk -2,..., x-m+1, x-m} �! Xe + Xe = {xk -1, xk -2,..., x-m+1, x-m,0},
" (�2)U = przesuni cie logiczne (logical shift)
W systemie dopełnieniowym pojawi si przeniesienie okr ne o warto ci xk 1
Xe = {xk -1, xk -1, xk -2,..., x-m+1, x-m} �! Xe + Xe = {xk -1, xk -2,..., x-m+1, x-m, xk -1}
" (�2)D = przemieszczenie cykliczne, rotacja (rotation)
Wynikiem skalowania odwrotnego (mno enia przez 2-1) jest zawsze
1
Xe = {xk -1, xk -2,..., x-m+1, x-m} �! Xe = {xk -1, xk -1, xk -2,..., x-m+1}
2
" (�2-1) = przesuni cie arytmetyczne (arithmetic shift).
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 3
 Mno enie
Skalowanie jako zło enie przesuni
Poniewa �k=(�a�2b�4c& )-1 (a,b,c,& =0,1), wi c mno enie przez �k
mo na wykona jako zło enie przesuni o 2i pozycji
" w lewo gdy k>0
" w prawo gdy k<0
L P L P L P L P L P L P L P L P
�! �! 1
L P L P L P L P L P L P L P L P
�! �! 2
L P L P L P L P L P L P L P L P
�! �! 4
Schemat skalowania przez przesuni cie w lewo
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 4
 Mno enie
Sekwencyjny algorytm mno enia w systemie naturalnym
Mno na (multiplicand) A =|{as-1,...,a- p+1,a- p}� |,
Mno nik (multiplier) X =|{xk-1,..., x-m+1, x-m}� |,
k-1 k-1
�ł
i i
A�" X = A�"�ł xi� =
�ł �ł
" "� (xi A)
�łi=-m łł i=-m
Algorytm pisemny  akumulacja skalowanych iloczynów cz ciowych
i=- m, - m+1,...,k-1, S-m = 0
i
Si+1 = Si + � (xi A) , Sk = A�" X
Algorytm dodaj-przesu (add-and-shift)  skalowanie sum cz ciowych
-i
Pi = � Si
-1
Pi+1 = � (Pi + xi A)
k -1
k i
� Pk = P-m + A{
"x � } = A�" X
i
i=-m
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 5
 Mno enie
Mno enie sekwencyjne w systemach uzupełnieniowych i dopełnieniowych
Warto ci znakowanego mno nika jest
k -1
i
X = - �(xk-1)R +
"x � ,
i
i=-m
1
gdzie �(xk-1) = (1+ sgn(2xk -1+1- �))  funkcja znaku liczby,
2
R=Q+ulp=�k w systemie pełnym, R=Q=�k-� m  w niepełnym
Mamy zatem (�=0 w systemie pełnym (U�), 0  w systemie niepełnym (D�)):
k -2
k -1 i -m
X = (xk -1 - ��(xk -1))� + )�
"x � + ��(xk -1
i
i=-m
Je eli najwy sz cyfr jest cyfra rozszerzenia xk -1 = (� -1)�(xk -1), to wtedy
k -2
�ł
k-1 i -m
A�" X = A�"�ł - �(xk-1)� + �ł
"x � + ��(xk-1)� �ł =
i
�ł i=-m łł
k-2
k-1 i -m
= - �(xk-1)� A +
"� (xi A) + ��(xk-1)� A
i=-m
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 6
 Mno enie
Interpretacja
Funkcja zk -1 = xk -1 - ��(xk -1) opisuje przekształcenie zbioru D={0,1,& ,�-1}
1 1
na nieredundantny zbiór cyfr znakowanych DS = {- � ,...,-1,0,1,..., � -1}
2 2
WNIOSKI:
W mno eniu w systemach uzupełnieniowych rozszerzenie mno nika zapewnia,
e warto ci najwy szej cyfry jest zawsze 0 albo  1 ( �-1 ).
W mno eniu przez k-cyfrowy mno nik nale y u y k cyfr lewostronnego
rozszerzenia mno nej
W dwójkowym systemie uzupełnieniowym równowa n interpretacji liczby
jako stałobazowej z ujemn wag pozycji najwy szej ( 2k 1), jest jej
traktowanie jako liczby z ujemn cyfr ( xk 1) i dodatni wag (2k 1)
i=k -2 i=k -2 i=k -2
- xk -12k -1 + (-2k -1) + ) 2k -1 +
"x 2i = xk -1 "x 2i = (-xk -1 "x 2i
i i i
i=-m i=-m i=-m
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 7
 Mno enie
Mno enie pisemne w systemie uzupełnieniowym  przykład
bez rozszerzenia mno nika
9 9 9 9 9 8 7 6 0 1 2 4
A=-124 A=124
7 7 9 7 7 9
X=-21 X=-21
9 9 9 9 8 8 8 4 0 0 0 0 1 1 1 6
x0=9 x0=9
9 9 9 9 1 3 2 0 0 0 0 8 6 8
x1=7 x1=7
0 0 0 3 7 2 9 9 9 6 2 8
x2=-3 -3A x2=-3 -3A
0 0 0 2 7 4 0 4 9 9 9 7 2 5 9 6
X�"A X�"A
z rozszerzeniem mno nika
9 9 9 9 9 8 7 6 0 0 0 0 0 1 2 4
A=-124 A=124
9 7 7 9 9 7 7 9
X=-21 X=-21
9 9 9 9 8 8 8 4 0 0 0 0 1 1 1 6
x0=9 x0=9
9 9 9 9 1 3 2 0 0 0 0 8 6 8
x1=7 x1=7
9 9 9 1 3 2 0 0 0 8 6 8
x2=7 x2=7
0 0 1 2 4 9 9 8 7 6
x3=-1 -A x3=-1 -A
0 0 0 2 7 4 0 4 9 9 9 7 2 5 9 6
X�"A X�"A
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 8
 Mno enie
Algorytm mno enia sekwencyjnego w systemach uzupełnieniowych
Algorytm mno enia dodaj-przesu (add-and-shift)  [ xk -1 = (� -1)�(xk -1)]
0. if xk -1 `" (� -1)�(xk -1) then
a) xk = (� -1)�(xk -1) ; dopisz pozycj rozszerzenia
b) k++ ; zwi ksz k
1. P-m = ��(xk -1)A ; (�=1 w s. niepełnym, 0 w pełnym)
2. i= m
3. Mi = xi A ; oblicz iloczyn cz ciowy
-1
4. Pi+1 = � (Pi + Mi ) ; przeskaluj (przesu ) sum cz ciow
5. i++ ; zwi ksz i
6. if i-1
7. Pk = � (Pk -1 +�(xk -1)(-A)) ; dodaj dopełnienie mno nej lub 0
k
8. A�" X = � Pk ; iloczyn
!! UWAGA: Wszystkie sumy cz ciowe s przesuwane w prawo
wi c musz by obliczane z lewostronnym rozszerzeniem
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 9
 Mno enie
Mno enie dodaj-przesu w systemie uzupełnieniowym  przykład
9 9 8 7 6 0 1 2 4
A = -124 A = 124
7 7 9 7 7 9
X = -21 X = -21
+9A 9 8 8 8 4 +9A 0 1 1 1 6
x0 = 9 x0 = 9

9 9 8 8 8 4 0 0 1 1 1 6
+7A 9 9 1 3 2 +7A 0 0 8 6 8
x1 = 7 x1 = 7
9 9 0 2 0 4 0 0 9 7 9 6

9 9 9 0 2 0 4 0 0 0 9 7 9 6
0 0 3 7 2 9 9 6 2 8
x2 = - 3 -3A x2 = - 3 -3A
0 0 2 7 4 0 4 9 9 7 2 5 9 6
0 0 0 2 7 4 0 4 X�"A
9 9 9 7 2 5 9 6
X�"A
& & & &

9 9 9 0 2 0 4 0 0 0 9 7 9 6
+7A 9 9 1 3 2 +7A 0 0 8 6 8
x2 = 7 x2 = 7
9 9 0 3 4 0 4 0 0 9 6 5 9 6
9 9 9 0 3 4 0 4 0 0 0 9 6 5 9 6
0 0 1 2 4 9 9 8 7 6
x3 = - 1 -A x3 = - 1 -A
0 0 0 2 7 4 0 4 9 9 9 7 2 5 9 6
X�"A X�"A
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 10
 Mno enie
Mno enie pisemne w dwójkowych systemach uzupełnieniowych U2 i U1
U2
1 1 1 1 1 0 0 1 0 1 0 1
A = -7 A = +5
1 0 1 1 1 1 0 1
X = -5 X = -3
1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1
x0 = 1 x0 = 1
1 1 1 1 0 0 1 0 0 0 0 0 0 0 0
x1 = 1 x1 = 0
0 0 0 0 0 0 0 0 0 1 0 1
x2 = 0 x2 = 1
0 0 1 1 1 1 1 0 1 1 0 0 0
x3 = 1 (-A) x3 = 1 (-A)
0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1
X�"A = 35 X�"A = -15
U1
1 1 1 1 1 0 0 0 0 1 0 1
A = -7 A = +5
1 0 1 1 1 1 0 1
X = -4 X = -2
1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1
P0 = x3 A P0 = x3 A
1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1
x0 = 1 x0 = 1
1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0
x1 = 1 x1 = 0
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
x2 = 0 x2 = 1
0 0 1 1 1 0 0 0 1 1 0 1 0 1 1 1
x3 = 1 (-A) x3 = 1 (-A)
0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1
e-a-c = 11 0 0 0 0 0 0 1 1 e-a-c = 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1
X�"A = 28 X�"A = -10
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 11
 Mno enie
Mno enie maszynowe w dwójkowych systemach uzupełnieniowych
W dwójkowych systemach uzupełnieniowych xk -1 - 2�(xk -1) = -xk -1
k -2
X = -xk -12k -1 + xi 2i + � xk -12-m
"
i=-m
1. P-m = � xk -1A ; (xk 1A) 0 w systemie (nie)pełnym
i= m
2. Mi = xi A ; oblicz iloczyn cz ciowy
3. Si+1 = Pi + Mi ; oblicz sum cz ciow
4. if �=1 then Si+1 = Si+1 + c+ ; �=1skoryguj sum przeniesieniem
5. Pi+1 = 2-1Si+1 ; przeskaluj sum (przesu w prawo)
6. i++ ; zwi ksz i
7. if i8. Pk = 2-1(Pk -1 + xk -1(-A)) ; dodaj dopełnienie mno nej lub 0
9. A�" X = 2k Pk ; iloczyn
" działania na wszystkich pozycjach sum cz ciowych
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 12
 Mno enie
Mno enie maszynowe w systemie U2  przykład
1 0 0 1 0 1 0 1
A=-7 A=+5
1 0 1 1 1 1 0 1
X=-5 X=-3
0 0 0 0 0 0 0 0 0 0
P0=0 P0=0
+A + 1 1 0 0 1 +A 0 0 1 0 1
x0=1 x0=1
1 1 0 0 1 0 0 1 0 1
ShR 1 1 1 0 0 1 ShR 0 0 0 1 0 1
+A + 1 1 0 0 1 0 ShR 0 0 0 0 1 0 1
x1=1 x1=0
1 0 1 0 1 1 +A + 0 0 1 0 1 0 0
x2=1
ShR 1 1 0 1 0 1 1 0 0 1 1 0 0 1
ShR 1 1 1 0 1 0 1 1 ShR 0 0 0 1 1 0 0 1
x2=0
+ 0 0 1 1 1 0 0 0 + 1 1 0 1 1 0 0 0
x3=1 -A x3=1 -A
0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1
X�"A=35 X�"A=-15
Uwaga: W polach zacienionych wpisano cyfry rozszerzenia znakowego.
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 13
 Mno enie
Mno enie maszynowe w systemie U1  przykład
1 0 0 0 0 1 0 1
A=-7 A=+5
1 0 1 1 1 1 0 1
X=-4 X=-2
1 1 0 0 0 0 0 1 0 1
P0=x3A P0=x3A
+A + 1 1 0 0 0 +A 0 0 1 0 1
x0=1 x0=1
[phone]
1 0 0 0 1 ShR 0 0 1 0 1 0
ShR 1 1 0 0 0 1 ShR 0 0 0 1 0 1 0
x1=0
+A + 1 1 0 0 0 1 +A + 0 0 1 0 1 0 0
x1=1 x2=1
[phone]
1 0 0 0 1 1 ShR 0 0 0 1 1 1 1 0
ShR 1 1 0 0 0 1 1 + 1 1 0 1 0 1 1 1
x3=1 -A
ShR 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1
x2=0 X�"A=-10
+ 0 0 1 1 1 0 0 0
x3=1 -A
[phone]
+ 1
0 0 0 1 1 1 0 0
X�"A=28
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 14
 Mno enie
Uproszczenie mno enia w dwójkowym systemie uzupełnieniowym
Je li do liczby danej w dwójkowym systemie uzupełnieniowym o k pozycjach
cz ci całkowitej dodamy 2k 1 to otrzymamy liczb dodatni
k -2 k -2
-1
- xk -12k -1 + )2k -1 +
"x 2i + 2k = (1- xk -1 "x 2i
i i
i=-m i=-m
Je li zatem do ka dego iloczynu cz ciowego xiA dodamy i odejmiemy 2k 1
(waga najwy szego bita mno nej), to iloczyn b dzie sum dodatnich
skalowanych iloczynów cz ciowych z dopełnieniem najwy szej cyfry
pomniejszon o sum kolejnych pot g dwójki
poczynaj c od pot gi odpowiadaj cej najwy szej cyfrze mno nej.
UWAGA:
Uproszczenie jest istotne w rozwi zaniach układowych, ale tak e
umo liwia uproszczenie realizacji programowej.
Intuicja (inne systemy)
Je li do liczby w systemie uzupełnieniowym o k pozycjach cz ci całkowitej
k -1
1
dodamy � , to otrzymamy liczb dodatni , ale & algorytm si komplikuje
2
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 15
 Mno enie
Akumulacja iloczynów cz ciowych w kodzie U2
W systemie U2 mamy
k -2 k -2
Z = -zk -12k-1 + zi 2i = -2k -1 + (1- zk -1)2k -1 + zi 2i = -2k -1 + Z+
" "
i=0 i=0
Iloczyny cz ciowe (xi A,  xm 1 A) maj te przypisane wagi, wi c:
m-1 m-1
2i xi A = 2m-1(xm-1(-A)+ - 2k-1) + 2i (xi A+ - 2k-1).
AX = -2m-1xm-1A +
" "
i=0 i=0
a zatem:
m-1
AX = [2m-1(xm-1(-A)+) + 2i (xi A+ )] - 2m+k-1 + 2k-1
"
i=0
algorytm
" zast pi bit znaku iloczynu cz ciowego (mno nej, jej uzupełnienia lub 0)
jego dopełnieniem (010...00)
" doda stał korekcyjn 2k -1 - 2m+k -1 ( 1 na pozycji najwy szego bitu
mno nej i pozycjach wy szych od najwy szego bitu ostatniego iloczynu)
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 16
 Mno enie
Schemat dodawania iloczynów cz ciowych w kodzie U2
a) A 9 8 7 6 5 4 3 2 1 0 b) A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o
" " " " " " " "
" " " " " " "
" " " " " " "
" " " " " " "
o o o o o o o o o o
" " " " " " "
" " " " " "
" " " " " "
" " " " " "
o o o o o o o o o o
" " " " " "
" " " " "
" " " " "
" " " " "
o o o o o o o o o o
" " " " "
" " " "
" " " "
" " " "
o o o o o o o o o o
" " " "
" " "
" " "
" " "
o o o o o o o o o o
" " "
" "
" "
" "
+ (1) 0 0 0 0 0 1
Matryca iloczynów cz ciowych: a) z rozszerzeniem ("
"  bit najwy szy i jego
"
"
kopia), b) bez rozszerze ("  dopełnienie najbardziej znacz cego bitu)
1 1 1 1 1 0 1 1 0 1 0 1 1 0 1
0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1
1 1 1 0 1 1 0 1 0 1 1 0 1
0
1 0 1 0 0 1 1 1 0 0 1 1
1
0 0 0 1 1 1 0 0 1 (1) 0 0 0 1
(0) 0 0 0 1 1 1 0 0 1
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 17
 Mno enie
Nadmiar w mno eniu w systemie naturalnym i uzupełnieniowym
Wynik mno enia k-pozycyjnej mno nej przez p-pozycyjny mno nik
mo na zawsze zapisa na k+p pozycjach iloczynu.
- 2k-1 d" A < 2k-1, - 2p-1 d" X < 2p-1 �! -2k+ p-2 < AX d" 2k+ p-2
(A oraz X s argumentami przeskalowanymi do warto ci całkowitych)
W układach cyfrowych wymaga si cz sto,
aby operandy (argumenty i wynik działania) były takiego samego rozmiaru.
Przekroczenie zakresu odpowiadaj cego rozmiarowi operandu jest zwykle
sygnalizowane jako nadmiar.
Wyró nia si ponadto:
mno enie dolne  wynikiem jest ni sza cz (połowa bitów) iloczynu
sygnalizacja nadmiaru je li wy sze bity nie s rozszerzeniem
mno enie górne  wynikiem jest wy sza cz (połowa bitów) iloczynu,
odpowiada mno eniu ułamków z obci ciem ni szych bitów,
nadmiar nie mo e wyst pi
mno enie z normalizacj  ustalona liczba bitów cz ci całkowitej
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 18
 Mno enie
Algorytm mno enia równoległego
mno na A =|{as-1,...,a- p+1,a- p}� |, mno nik X =|{xk-1,..., x-m+1, x-m}� |
system naturalny
s-1 k-1 s+k-2
�ł
�ł
j i r
A�" X = �ł �ł�ł xi� =
�ł
"a � �ł�ł " "� "a xi
j j
j=- p i=-m łł r=-m- p i+ j=r
�ł łł�ł
algorytm
obliczenie wszystkich iloczynów elementarnych a xi
j
akumulacja czynników o tej samej wadze
"a xi
j
i+ j=r
problem  szybkie dodawanie wieloargumentowe
system uzupełnieniowy do 2  niektóre iloczyny elementarne maj ujemne wagi
s-2 k -2 s+k -2
�ł �ł�ł
j -1 r p
�ł-
A�" X = as-12s-1 + xi 2i �ł =
�ł
"a 2 �ł�ł- xk 2k + " "2 "a xi (-1)
j j
�ł �ł�ł -1
j=- p i=-m łł r=-m- p i+ j=r
�ł łł
p=0 gdy j`" s 1 oraz i`" k 1 lub i+j=s+k 2, w przeciwnym razie p=1
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 19
 Mno enie
Algorytm mno enia liczb dwójkowych w kodzie NB
Krok 0. A �! A, X/P �! X, C||S/P �! 0. Podstaw i=1.
Krok 1. C||S/P �! (S/P) + xi(A)
Krok 2. C||S/P||X/P �! 2 1(C||S/P||X/P) = ShR(C||S/P||X/P)
Krok 3. i=i+1. Je li i < k+m, wró do kroku 1.
Wynik: A�"X=(S/P||X/P)
ShR
A
C S/P X/P
Ł
S
Schemat blokowy układu mno cego: S/P  rejestr sum cz ciowych,
X/P  rejestr mno nika, A  rejestr mno nej, C  rejestr przeniesienia
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 20
 Mno enie
Redukcja liczby iloczynów cz ciowych  przekodowanie kanoniczne
Minimaln dla danego mno nika liczb dodawa lub odejmowa okre la waga
(| yn-1 | + | yn-2 | +...+ | y0 |) jego minimalnej reprezentacji w kodzie SD.
X = {xn-1,..., x1, x0}U2 Ymin = {yn-1,..., y1, y0}SD  przekodowanie kanoniczne
Przekodowanie kanoniczne  algorytm sekwencyjny (p0=0)
xi 1 xi pi pi+1 yi Komentarz
0 0 0 0 0 ci g zer
0 1 0 0 1 izolowana jedynka
1 0 0 0 0 ci g zer
1 1 0 1 pocz tek ci gu jedynek
1
0 0 1 0 1 koniec ci gu jedynek
0 1 1 1 0 ci g jedynek
1 0 1 1 izolowane zero
1
1 1 1 1 0 ci g jedynek
Skomplikowana i czasochłonna procedura przekodowania rzadko stosowane
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 21
 Mno enie
Przekodowanie Bootha
" zast pienie serii dodawa jednym odejmowaniem i jednym dodawaniem
2s-1 + 2s-2 + ... + 2l +1 + 2l = 2s - 2l
|{...0[11...11]0...}U2|=|{...1[00...00]0...}U2| |{...0[00...01]0...}U2,
|{...0[11...11]0...}SD|= |{...1[00...0 1]0...}SD|
reguła Bootha a" przekodowanie mno nika na kod SD
" reprezentacja w systemie NB lub U2 jest reprezentacj w systemie SD, ale
przekodowanie według reguły Bootha:
" U2 SD  wykonalne, bo [x1...11]0...= [(1-x)0...00]0... - [00...01]0...
" NB SD  niewykonalne bez rozszerzenia gdy {1,1,& ,1,0,x,& }, bo
xe"0 '" z `" 1 �! |{1,x,...,x,x}SD| > |{z,y,y,...,y}SD|
�! konieczne rozszerzenie {1,& ,1,0,x,& }NB= {0,1, & ,1,0,x,& }U2
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 22
 Mno enie
Algorytm Bootha
Uzasadnienie teoretyczne  równowa no X=2X-X
n-2 n-2 n-1
�ł- �ł-
X = xn-12n + xi 2i+1łł - xn-12n-1 + xi 2i łł =
" " "(x - xi )2i - x-1
i-1
�ł śł �ł śł
�ł i=0 �ł �ł i=0 �ł i=0
xi "{0,1} �! yi = xi-1 - xi "{-1,0,1} (x 1=0)
|{xn 1,xn 2,xn 1,& ,x1,x0}U2|=|{(xn 2 xn 1),(xn 3 xn 2),& ,(x0 x1),(x 1 x0)}SD|
Przekodowanie Bootha ( yi = xi-1 - xi)
xi xi 1 yi operacja komentarz
0 0 0  ci g zer
0 1 1 koniec ci gu jedynek
+A
1 0 pocz tek ci gu jedynek
1 -A
1 1 0  ci g jedynek
Wady:
 zmienna liczba działa arytmetycznych, zale na od kodu liczby,
 nieefektywne kodowanie izolowanych jedynek  ...010101(0) ...1 1 1 11 1 .
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 23
 Mno enie
Alternatywne przekodowanie Bootha
n-1 n-2
X =
"(x - xi )2i - x-1 = 2"(x - xi+1)2i - x0.
i-1 i
i=0 i=0
�! alternatywne przekodowanie mno nika Y = {yn-1,..., y1, y0}
yi = xi - xi+1, 0 d" i d" n -1,
Poniewa X = 2Y - x0, wi c
" warto ci pocz tkow akumulowanej sumy iloczynów jest - x0A,
" zamiast mno nej A nale y w algorytmie u y jej podwojenia 2A,
" yi (przekodowanie alternatywne) = yi+1(przekodowanie proste)
Przekodowanie alternatywne NB/U2 SD zawsze wykonalne:
" U2 SD  rozszerzenie xn = xn-1, �! yn-1 = 0
" NB SD  rozszerzenie xn = 0 �! yn-1 = xn-1
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 24
 Mno enie
Przekodowanie rozszerzone (w bazie 22)  algorytm Bootha-McSorleya
2k -1 k-1 k-1
j
X =
"(x - xj )2 - x-1 = "(x - x2i )22i +"(x - x2i+1)22i+1 - x-1 =
j-1 2i-1 2i
j=0 i=0 i=0
k-1 k-1
=
"(x - x2i + 2x2i - 2x2i+1)22i - x-1 = "(-2x + x2i + x2i-1)22i - x-1
2i-1 2i+1
i=0 i=0
Poniewa je li xi "{0,1} to - 2x2i+1 + x2i + x2i-1 "{-2,-1, 0,+1,+2} (x =0), wi c
-1
istnieje jednoznaczne przekształcenie XU2YSD:
{0,1}3 {x2i+1, x2i, x2i-1} {y2i+1, y2i}"{1 0, 0 1, 00, 01,10}
Wynik przekształce : Y = {yn-1,..., y1, y0}SD (y# "{1,0,1}) takie, e
- 2x2i+1 + x2i + x2i-1 = 2y2i+1 + y2i , y2i+1y2i = 0
" połowa cyfr Y to zera
" mo liwe zmniejszenie liczby zer mno nika (00101010 010 1 0 1 1 0).
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 25
 Mno enie
Algorytm Bootha-McSorleya  praktyczna realizacja
Analizowane s pary bitów �! rozszerzenie mno nika do parzystej liczby bitów
" ka da z kolejnych par bitów mno nika zawiera co najmniej jedno 0
1
�! liczba iloczynów cz ciowych d" n
2
" dla pary x2i+1, x2i iloczynem jest (x2i + x2i-1 - 2x2i+1)A o wadze 22i
Przekodowanie rozszerzone (Bootha-McSorleya)
x2i+1 x2i x2i 1 y2i+1 y2i działanie komentarz
0 0 0 0 0  ci g zer
0 1 0 0 1 +A izolowana jedynka
1 0 0 0 pocz tek ci gu jedynek
-2A
1
1 1 0 0 pocz tek ci gu jedynek
-A
1
0 0 1 0 1 +A koniec ci gu jedynek
0 1 1 1 0 +2A koniec ci gu jedynek
1 0 1 0 izolowane zero
-A
1
1 1 1 0 0  ci g jedynek
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 26
 Mno enie
Alternatywne przekodowanie Bootha-McSorleya
2k -2 k-1
j
X = 2
"(x - xj+1)2 - x0 = 2"(-2x + x2i+1 + x2i )22i - x0.
j 2i+2
j=0 i=0
(-2x2i+2 + x2i+1 + x2i ) "{-2,-1,0,1,2} wynik przekodowania: YSD taka, e
- 2x2i+2 + x2i+1 + x2i = 2y2i+1 + y2i oraz y2i+1 y2i = 0
Alternatywne przekodowanie Bootha-McSorleya
x2i+2 x2i+1 x2i y2i+1 y2i działanie komentarz
0 0 0 0 0  ci g zer
0 0 1 0 1 +2A pocz tek ci gu jedynek
0 1 0 0 1 +2A izolowana jedynka
0 1 1 1 0 +4A pocz tek ci gu jedynek
1 0 0 0 koniec ci gu jedynek
-4A
1
1 0 1 0 izolowane zero
1 -2A
1 1 0 0 koniec ci gu jedynek
1 -2A
1 1 1 0 0  ci g jedynek
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 27
 Mno enie
Algorytm Bootha/Bootha-McSorleya  przykłady
X= {(1),1,0,1,1,0,0,1}U2  w bazie 2  Y ={1,1,0,1,0,1,1},
 alternatywne w bazie 4  Y ={01,10,1 0,01}
1 0 1 1 0 1 1 0 1 1 0 1
A = -19
X = -39 1 1 0 1 0 1 1 0 1 1 0 1 0 0 1
 A 0 0 0 0 0 0 0 0 1 0 0 1 1 A 1 1 1 1 1 1 1 1 0 1 1 0 1
+A 1 1 1 1 1 1 1 0 1 1 0 1  2A 0 0 0 0 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 2A 1 1 1 0 1 1 0 1
 A 0 0 0 0 0 1 0 0 1 1  A 0 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 1
+A 1 1 1 0 1 1 0 1
 A 0 0 1 0 0 1 1
XA=741 0 0 0 1 0 1 1 1 0 0 1 0 1
Uwaga: W polach zacienionych wpisano cyfry rozszerzenia znakowego.
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 28
 Mno enie
Alternatywny algorytm Bootha/Bootha-McSorleya  przykłady
X= {1,1,0,1,0,1}U2  w bazie 2  Y ={0,1,1,1,1},
 alternatywne w bazie 4  Y = {00,0 1,0 1}, P0= x0A
Y(2R) Y(4R)
1 1 1 1 0 1 1 1 1 1 0 1
A=-3
0 1 1 0 0 0 0
1 1 1 1
X=-11
 x0A 0 0 0 0 0 0 0 0 0 1 1  x0A 0 0 0 0 0 0 0 1 1
P0=
+2A 1 1 1 1 1 1 1 1 0 1  2A 0 0 0 0 0 0 1 1
 2A 0 0 0 0 0 0 0 1 1  2A 0 0 0 0 1 1
+2A 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 1
 2A 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 1
XA=33
Uwaga: W polach zacienionych wpisano cyfry rozszerzenia znakowego.
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 29
 Mno enie
Przekodowanie mno nika w systemie uzupełnie do 1
W systemie U1, na podstawie równowa no ci X=2X-X mamy
n-2 n-2
�ł- �ł-
X = xn-1 (2n - 2ulp) + xi 2i+1 łł - xn-1 (2n-1 - ulp) + xi 2i łł ,
" "
�ł śł �ł śł
�ł i=0 �ł �ł i=0 �ł
sk d wynika
n-1
X =
"(x - xi )2i - x-1 + xn-1ulp.
i-1
i=0
Poniewa ulp=1, a rozszerzeniem liczby w kodzie U1 jest x-1 = xn-1, zatem
n-1
X =
"(x - xi )2i.
i-1
i=0
Podobnie
n-2
X = 2
"(x - xi+1)2i + (xn-1 - x0 ).
i
i=0
" algorytm analogiczny jak w U2, lecz inna warto pocz tkowa akumulacji
" sumowanie z uwzgl dnieniem rozszerze prawo- i lewostronnych
z

� Janusz Biernat, 03-06-Mnozenie.doc, 4 pa dziernika 2006 MUL 30