Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–1
Skalowanie w systemach naturalnych
Skalowanie – mno enie przez całkowit pot g podstawy
β
k
.
•
skalowania mo na składa poniewa
β
k
X =
β
…
ββ
X
•
mno enie przez ka d dodatni pot g podstawy
daje w wyniku cykliczne przemieszczenie cyfr w lewo, poniewa
∑
∑
∑
=
+
−
=
−
−
=
−
=
+
−
=
−
=
=
=
k
i
m
i
i
i
k
i
m
i
i
i
k
i
m
i
i
i
x
x
x
1
1
1
1
1
β
β
β
β
•
mno enie przez ka d ujemn pot g podstawy
daje w wyniku cykliczne przemieszczenie cyfr w prawo, poniewa
∑
∑
∑
−
=
−
−
=
+
−
=
−
=
−
−
=
−
=
−
=
=
2
1
1
1
1
1
1
k
i
m
i
i
i
k
i
m
i
i
i
k
i
m
i
i
i
x
x
x
β
β
β
β
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–2
Skalowanie w systemach uzupełnieniowych i dopełnieniowych
Je li najwy sz pozycj liczby nie jest cyfra rozszerzenia
)
1
)(
(
1
−
=
−
β
ϕ
k
k
x
x
,
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:
)
1
)(
(
1
−
=
−
β
ϕ
k
k
x
x
– otrzymamy
}
0
,
,...,
,
{
}
,...,
,
),
1
)(
(
{
2
1
e
2
1
1
e
m
k
k
m
k
k
k
x
x
x
x
x
x
x
−
−
−
−
−
−
−
=
⇒
−
=
X
X
β
β
ϕ
,
W systemie dopełnieniowym nast pi cykliczne przemieszczenie cyfr
)}
1
)(
(
,
,...,
,
{
}
,...,
,
),
1
)(
(
{
1
2
1
e
2
1
1
e
−
=
⇒
−
=
−
−
−
−
−
−
−
−
β
ϕ
β
β
ϕ
k
m
k
k
m
k
k
k
x
x
x
x
x
x
x
x
X
X
Wynik skalowania odwrotnego (mno enia przez
β
−1
) jest zawsze poprawny
}
,...,
,
),
1
)(
(
{
}
,
,...,
,
{
1
2
1
1
e
1
1
2
1
e
+
−
−
−
−
−
−
+
−
−
−
−
=
⇒
=
m
k
k
k
m
m
k
k
x
x
x
x
x
x
x
x
β
ϕ
β
X
X
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–3
Skalowanie w dwójkowym systemie uzupełnieniowym i dopełnieniowym
Wynikiem dodawania liczby do niej samej jest na ka dej pozycji:
i
i
i
i
i
s
c
c
x
x
+
=
+
+
+
1
2
⇒
i
i
x
c
=
+
1
,
i
i
c
s
=
⇒
i
i
x
s
=
+
1
W systemie uzupełnieniowym, u ywaj c rozszerzenia, otrzymamy
}
0
,
,
,...,
,
{
}
,
,...,
,
,
{
1
2
1
e
e
1
2
1
1
e
m
m
k
k
m
m
k
k
k
x
x
x
x
x
x
x
x
x
−
+
−
−
−
−
+
−
−
−
−
=
+
⇒
=
X
X
X
,
•
(
×2
)
U
= przesuni cie logiczne (logical shift)
W systemie dopełnieniowym pojawi si przeniesienie okr
ne o warto ci x
k–1
}
,
,
,...,
,
{
}
,
,...,
,
,
{
1
1
2
1
e
e
1
2
1
1
e
−
−
+
−
−
−
−
+
−
−
−
−
=
+
⇒
=
k
m
m
k
k
m
m
k
k
k
x
x
x
x
x
x
x
x
x
x
X
X
X
•
(
×2
)
D
= przemieszczenie cykliczne, rotacja (rotation)
Wynikiem skalowania odwrotnego (mno enia przez
2
−1
) jest zawsze
}
,...,
,
,
{
}
,
,...,
,
{
1
2
1
1
e
2
1
1
2
1
e
+
−
−
−
−
−
+
−
−
−
=
⇒
=
m
k
k
k
m
m
k
k
x
x
x
x
x
x
x
x
X
X
•
(
×2
−1
) = przesuni cie arytmetyczne (arithmetic shift).
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–4
Skalowanie jako zło enie przesuni
Poniewa
β
k
= (
β
a
β
2
b
β
4c
…)
−1
(a, b, c, … = 0, 1) , wi c mno enie przez
β
k
mo na wykona jako zło enie przesuni
o 2
i
pozycji
•
w lewo gdy k > 0
•
w prawo gdy k < 0
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
L P
L P
L P
L P
L P
L P
L P
Schemat skalowania przez przesuni cie w lewo
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–5
Sekwencyjny algorytm mno enia w systemie naturalnym
Mno na (multiplicand)
|
}
,
,...,
{
|
1
1
β
p
p
s
a
a
a
A
−
+
−
−
=
,
Mno nik (multiplier)
|
}
,
,...,
{
|
1
1
β
m
m
k
x
x
x
X
−
+
−
−
=
,
∑
∑
−
−
=
−
−
=
=
⋅
=
⋅
1
1
)
(
k
m
i
i
i
k
m
i
i
i
A
x
x
A
X
A
β
β
Algorytm pisemny – akumulacja skalowanych iloczynów cz ciowych
i =
−
m,
−
m+1,...,k
−
1,
0
=
−
m
S
)
(
1
A
x
S
S
i
i
i
i
β
+
=
+
,
X
A
S
k
⋅
=
Algorytm dodaj-przesu (add-and-shift) – skalowanie sum cz ciowych
i
i
i
S
P
−
=
β
)
(
1
1
A
x
P
P
i
i
i
+
=
−
+
β
X
A
x
A
P
P
k
m
i
i
i
m
k
k
⋅
=
+
=
∑
−
−
=
−
1
}
{
β
β
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–6
Mno enie sekwencyjne w systemach uzupełnieniowych i dopełnieniowych
Warto ci znakowanego mno nika jest
∑
−
−
=
−
+
−
=
1
1
)
(
k
m
i
i
i
k
x
R
x
X
β
ϕ
,
gdzie
))
1
2
(
sgn
1
(
)
(
1
2
1
1
β
ϕ
−
+
+
=
−
−
k
k
x
x
– funkcja znaku liczby,
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
β
)):
m
k
k
m
i
i
i
k
k
k
x
x
x
x
X
−
−
−
−
=
−
−
−
+
+
−
=
∑
β
δϕ
β
β
ϕ
β
)
(
))
(
(
1
2
1
1
1
Je eli najwy sz cyfr jest cyfra rozszerzenia
)
(
)
1
(
1
1
−
−
−
=
k
k
x
x
ϕ
β
, to wtedy
A
x
A
x
A
x
x
x
x
A
X
A
m
k
k
m
i
i
i
k
k
m
k
k
m
i
i
i
k
k
−
−
−
−
=
−
−
−
−
−
−
=
−
−
+
+
−
=
=
+
+
−
⋅
=
⋅
∑
∑
β
δϕ
β
β
ϕ
β
δϕ
β
β
ϕ
)
(
)
(
)
(
)
(
)
(
1
2
1
1
1
2
1
1
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–7
Interpretacja
Funkcja
)
(
1
1
1
−
−
−
−
=
k
k
k
x
x
z
ϕ
β
opisuje przekształcenie zbioru
D = {0, 1, …,
β
−
1}
na nieredundantny zbiór cyfr znakowanych
}
1
,...,
1
,
0
,
1
,...,
{
2
1
2
1
−
−
−
=
β
β
S
D
W
NIOSKI
:
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 (–2
k–1
), jest jej
traktowanie jako liczby z ujemn cyfr (–x
k–1
) i dodatni wag (2
k–1
)
∑
∑
∑
−
=
−
=
−
−
−
=
−
=
−
−
−
=
−
=
−
−
+
−
=
+
−
=
+
−
2
1
1
2
1
1
2
1
1
2
2
)
(
2
)
2
(
2
2
k
i
m
i
i
i
k
k
k
i
m
i
i
i
k
k
k
i
m
i
i
i
k
k
x
x
x
x
x
x
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–8
Mno enie pisemne w systemie uzupełnieniowym – przykład
bez rozszerzenia mno nika
A
=−124
9 9 9 9 9 8 7 6
A
=124
0 1 2 4
X
=−21
7 7 9
X
=−21
7 7 9
x
0
=9
9 9 9 9 8 8 8 4
x
0
=9
0 0 0 0 1 1 1 6
x
1
=7
9 9 9 9 1 3 2
x
1
=7
0 0 0 0 8 6 8
x
2
=−3
−3
A 0 0 0 3 7 2
x
2
=−3
−3
A 9 9 9 6 2 8
X
⋅
A
0 0 0 2 7 4 0 4
X
⋅
A
9 9 9 7 2 5 9 6
z rozszerzeniem mno nika
A
=−124
9 9 9 9 9 8 7 6
A
=124
0 0 0 0 0 1 2 4
X
=−21
9 7 7 9
X
=−21
9 7 7 9
x
0
=9
9 9 9 9 8 8 8 4
x
0
=9
0 0 0 0 1 1 1 6
x
1
=7
9 9 9 9 1 3 2
x
1
=7
0 0 0 0 8 6 8
x
2
=7
9 9 9 1 3 2
x
2
=7
0 0 0 8 6 8
x
3
=−1
−
A
0 0 1 2 4
x
3
=−1
−
A
9 9 8 7 6
X
⋅
A
0 0 0 2 7 4 0 4
X
⋅
A
9 9 9 7 2 5 9 6
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–9
Algorytm mno enia sekwencyjnego w systemach uzupełnieniowych
Algorytm mno enia dodaj-przesu (add-and-shift) – [
)
(
)
1
(
1
1
−
−
−
=
k
k
x
x
ϕ
β
]
0.
if
)
(
)
1
(
1
1
−
−
−
≠
k
k
x
x
ϕ
β
then
a)
)
(
)
1
(
1
−
−
=
k
k
x
x
ϕ
β
; dopisz pozycj rozszerzenia
b) k ++
; zwi ksz k
1.
A
x
P
k
m
)
(
1
−
−
=
δϕ
; (
δ
=1 w s. niepełnym, 0 w pełnym)
2. i = –m
3.
A
x
M
i
i
=
; oblicz iloczyn cz ciowy
4.
)
(
1
1
i
i
i
M
P
P
+
=
−
+
β
; przeskaluj (przesu ) sum cz ciow
5. i ++
; zwi ksz i
6.
if i < k–1 goto 3
; powtarzaj do przedostatniego
7.
))
)(
(
(
1
1
1
A
x
P
P
k
k
k
−
+
=
−
−
−
ϕ
β
; dodaj dopełnienie mno nej lub 0
8.
k
k
P
X
A
β
=
⋅
; iloczyn
!! UWAGA: Wszystkie sumy cz ciowe s przesuwane w prawo
wi c musz by obliczane z lewostronnym rozszerzeniem
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–10
Mno enie dodaj-przesu w systemie uzupełnieniowym – przykład
A
=−124
9 9 8 7 6
A
=124
0 1 2 4
X
=−21
7 7 9
X
=−21
7 7 9
x
0
=9
+9A
9 8 8 8 4
x
0
=9
+9A 0 1 1 1 6
→
9 9 8 8 8 4
→
0 0 1 1 1 6
x
1
=7
+7A
9 9 1 3 2
x
1
=7
+7A 0 0 8 6 8
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
x
2
=−3
−3
A
0 0 3 7 2
x
2
=−3
−3
A 9 9 6 2 8
0 0 2 7 4 0 4
9 9 7 2 5 9 6
X
⋅
A
→
0 0 0 2 7 4 0 4
X
⋅
A
9 9 9 7 2 5 9 6
… …
… …
→
9 9 9 0 2 0 4
→
0 0 0 9 7 9 6
x
2
=7
+7A
9 9 1 3 2
x
2
=7
+7A 0 0 8 6 8
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
x
3
=−1
−
A
0 0 1 2 4
x
3
=−1
−
A
9 9 8 7 6
X
⋅
A
0 0 0 2 7 4 0 4
X
⋅
A
9 9 9 7 2 5 9 6
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–11
Mno enie pisemne w dwójkowych systemach uzupełnieniowych U2 i U1
U2
A
=−7
1 1 1 1 1 0 0 1
A
=+5
0 1 0 1
X
=−5
1 0 1 1
X
=−3
1 1 0 1
x
0
=1
1 1 1 1 1 0 0 1
x
0
=1
0 0 0 0 0 1 0 1
x
1
=1
1 1 1 1 0 0 1
x
1
=0
0 0 0 0 0 0 0 0
x
2
=0
0 0 0 0 0 0
x
2
=1
0 0 0 1 0 1
x
3
=1
(−
A)
0 0 1 1 1
x
3
=1
(−
A) 1 1 0 1 1 0 0 0
X
⋅
A
=
35
0 0 1 0 0 0 1 1
X
⋅
A
=−
15
1 1 1 1 0 0 0 1
U1
A
=−7
1 1 1 1 1 0 0 0
A
=+5
0 1 0 1
X
=−4
1 0 1 1
X
=−2
1 1 0 1
P
0
=
x
3
A
1 1 1 1 1 0 0 0
P
0
=
x
3
A
0 0 0 0 0 1 0 1
x
0
=1
1 1 1 1 1 0 0 0
x
0
=
1
0 0 0 0 0 1 0 1
x
1
=1
1 1 1 1 0 0 0 1
x
1
=0
0 0 0 0 0 0 0 0
x
2
=0
0 0 0 0 0 0 0 0
x
2
=1
0 0 0 1 0 1 0 0
x
3
=
1
(−
A) 0 0 1 1 1 0 0 0
x
3
=1
(−
A) 1 1 0 1 0 1 1 1
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
X
⋅
A
=28
0 0 0 1 1 1 0 0
X
⋅
A
=−10
1 1 1 1 0 1 0 1
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–12
Mno enie maszynowe w dwójkowych systemach uzupełnieniowych
W dwójkowych systemach uzupełnieniowych
1
1
1
)
(
2
−
−
−
−
=
−
k
k
k
x
x
x
ϕ
m
k
k
m
i
i
i
k
k
x
x
x
X
−
−
−
−
=
−
−
+
+
−
=
∑
2
2
2
1
2
1
1
δ
1.
A
x
P
k
m
1
−
−
=
δ
; (x
k–1
A) 0 w systemie (nie)pełnym
i = –m
2.
A
x
M
i
i
=
; oblicz iloczyn cz ciowy
3.
i
i
i
M
P
S
+
=
+
1
; oblicz sum cz ciow
4. if
δ
= 1 then
+
+
+
+
=
c
S
S
i
i
1
1
;
δ
= 1
→
skoryguj sum przeniesieniem
5.
1
1
1
2
+
−
+
=
i
i
S
P
; przeskaluj sum (przesu w prawo)
6. i ++
; zwi ksz i
7. if i < k–1 goto 3
; powtarzaj do przedostatniego
8.
))
(
(
2
1
1
1
A
x
P
P
k
k
k
−
+
=
−
−
−
; dodaj dopełnienie mno nej lub 0
9.
k
k
P
X
A
2
=
⋅
; iloczyn
•
działania na wszystkich pozycjach sum cz ciowych
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–13
Mno enie maszynowe w systemie U2 – przykład
A
=−7
1 0 0 1
A
=+5
0 1 0 1
X
=−5
1 0 1 1
X
=−3
1 1 0 1
P
0
=0
0 0 0 0 0
P
0
=0
0 0 0 0 0
x
0
=1
+A
+ 1 1 0 0 1
x
0
=1
+A
0 0 1 0 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
x
1
=1
+A
+ 1 1 0 0 1 0
x
1
=0
ShR 0 0 0 0 1 0 1
1 0 1 0 1 1
x
2
=1
+A
+ 0 0 1 0 1 0 0
ShR 1 1 0 1 0 1 1
0 0 1 1 0 0 1
x
2
=0
ShR 1 1 1 0 1 0 1 1
ShR 0 0 0 1 1 0 0 1
x
3
=1
−
A
+ 0 0 1 1 1 0 0 0
x
3
=1
−
A
+ 1 1 0 1 1 0 0 0
X
⋅
A
=
35
0 0 1 0 0 0 1 1
X
⋅
A
=−
15
1 1 1 1 0 0 0 1
Uwaga: W polach zacienionych wpisano cyfry rozszerzenia znakowego.
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–14
Mno enie maszynowe w systemie U1 – przykład
A
=−7
1 0 0 0
A
=+5
0 1 0 1
X
=−4
1 0 1 1
X
=−2
1 1 0 1
P
0
=
x
3
A
1 1 0 0 0
P
0
=
x
3
A
0 0 1 0 1
x
0
=1
+A
+ 1 1 0 0 0
x
0
=
1
+A
0 0 1 0 1
+1
1 0 0 0 0
0 1 0 1 0
1 0 0 0 1
ShR 0 0 1 0 1 0
ShR 1 1 0 0 0 1
x
1
=0
ShR 0 0 0 1 0 1 0
x
1
=1
+A
+ 1 1 0 0 0 1
x
2
=1
+A
+ 0 0 1 0 1 0 0
+1
1 0 0 0 1 0
0 0 1 1 1 1 0
1 0 0 0 1 1
ShR 0 0 0 1 1 1 1 0
ShR 1 1 0 0 0 1 1
x
3
=1
−
A
+ 1 1 0 1 0 1 1 1
x
2
=0
ShR 1 1 1 0 0 0 1 1
X
⋅
A
=−10
1 1 1 0 1 0 1
x
3
=
1
−
A
+ 0 0 1 1 1 0 0 0
+1
0 0 0 1 1 0 1 1
+ 1
X
⋅
A
=28
0 0 0 1 1 1 0 0
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–15
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 2
k–1
to otrzymamy liczb dodatni
∑
∑
−
−
=
−
−
−
−
−
=
−
−
+
−
=
+
+
−
2
1
1
1
2
1
1
2
2
)
1
(
2
2
2
k
m
i
i
i
k
k
k
k
m
i
i
i
k
k
x
x
x
x
Je li zatem do ka dego iloczynu cz ciowego x
i
A dodamy i odejmiemy 2
k–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
dodamy
1
2
1
−
k
β
, to otrzymamy liczb dodatni , ale … algorytm si komplikuje
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–16
Akumulacja iloczynów cz ciowych w kodzie U2
W systemie U2 mamy
+
−
−
=
−
−
−
−
=
−
−
+
−
=
+
−
+
−
=
+
−
=
∑
∑
Z
z
z
z
z
Z
k
k
i
i
i
k
k
k
k
i
i
i
k
k
1
2
0
1
1
1
2
0
1
1
2
2
2
)
1
(
2
2
2
Iloczyny cz ciowe (x
i
A, –x
m–1
A) maj te przypisane wagi, wi c:
∑
∑
−
=
−
+
−
+
−
−
−
=
−
−
−
+
−
−
=
+
−
=
1
0
1
1
1
1
1
0
1
1
)
2
(
2
)
2
)
(
(
2
2
2
m
i
k
i
i
k
m
m
m
i
i
i
m
m
A
x
A
x
A
x
A
x
AX
.
a zatem:
1
1
1
0
1
1
2
2
]
)
(
2
)
)
(
(
2
[
−
−
+
−
=
+
+
−
−
+
−
+
−
=
∑
k
k
m
m
i
i
i
m
m
A
x
A
x
AX
→
algorytm
•
zast pi bit znaku iloczynu cz ciowego (mno nej, jej uzupełnienia lub 0)
jego dopełnieniem (0
→
10...00)
•
doda stał korekcyjn
1
1
2
2
−
+
−
−
k
m
k
(„1” na pozycji najwy szego bitu
mno nej i pozycjach wy szych od najwy szego bitu ostatniego iloczynu)
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–17
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 0 1 1 0 1
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0
1 1 1 0 1 1 0 1
0 0 1 1 0 1
1 0 1 0 0 1 1
1 1 0 0 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
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–18
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.
2
2
1
1
1
1
2
2
2
2
,
2
2
−
+
−
+
−
−
−
−
≤
<
−
⇒
<
≤
−
<
≤
−
p
k
p
k
p
p
k
k
AX
X
A
(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
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–19
Algorytm mno enia równoległego
mno na
|
}
,
,...,
{
|
1
1
β
p
p
s
a
a
a
A
−
+
−
−
=
, mno nik
|
}
,
,...,
{
|
1
1
β
m
m
k
x
x
x
X
−
+
−
−
=
system naturalny
∑
∑
∑
∑
=
+
−
+
−
−
=
−
−
=
−
−
=
=
=
⋅
r
j
i
i
j
k
s
p
m
r
r
k
m
i
i
i
s
p
j
j
j
x
a
x
a
X
A
2
1
1
β
β
β
algorytm
→
obliczenie wszystkich iloczynów elementarnych
i
j
x
a
→
akumulacja czynników o tej samej wadze
∑
=
+
r
j
i
i
j
x
a
problem
– szybkie dodawanie wieloargumentowe
system uzupełnieniowy do 2 – niektóre iloczyny elementarne maj ujemne wagi
∑
∑
∑
∑
=
+
−
+
−
−
=
−
−
=
−
−
−
−
=
−
−
−
=
+
−
+
−
=
⋅
r
j
i
p
i
j
k
s
p
m
r
r
k
m
i
i
i
k
k
s
p
j
j
j
s
s
x
a
x
x
a
a
X
A
)
1
(
2
2
2
2
2
2
2
1
1
2
1
1
p = 0 gdy j
≠
s–1 oraz i
≠
k–1 lub i+j = s+k–2, w przeciwnym razie p = 1
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–20
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) + x
i
(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
C
S/P
X/P
A
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
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–21
Redukcja liczby iloczynów cz ciowych – przekodowanie kanoniczne
Minimaln dla danego mno nika liczb dodawa lub odejmowa okre la waga
|)
|
...
|
|
|
|
(
0
2
1
y
y
y
n
n
+
+
+
−
−
jego minimalnej reprezentacji w kodzie SD.
}
,
,...,
{
0
1
1
x
x
x
n
−
=
X
U2
→
}
,
,...,
{
0
1
1
min
y
y
y
n
−
=
Y
SD
– przekodowanie kanoniczne
Przekodowanie kanoniczne –algorytm sekwencyjny (p
0
=0)
x
i–1
x
i
p
i
p
i+1
y
i
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
1
pocz tek ci gu jedynek
0
0
1
0
1
koniec ci gu jedynek
0
1
1
1
0
ci g jedynek
1
0
1
1
1
izolowane zero
1
1
1
1
0
ci g jedynek
Skomplikowana i czasochłonna procedura przekodowania
→
rzadko stosowane
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–
22
Przekodowanie Bootha
•
zast pienie serii dodawa jednym odejmowaniem i jednym dodawaniem
l
s
l
l
s
s
2
2
2
2
...
2
2
1
2
1
−
=
+
+
+
+
+
−
−
|{...0[11...11]0... }
U2
| = |{...1[00...00]0... }
U2
| – |{...0[00...01]0...}
U2
,
|{...0[11...11]0... }
SD
| = |{
...
0
]
1
0
...
00
[
1
...
}
SD
|
→
reguła Bootha
≡
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
x
≥
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
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–
23
Algorytm Bootha
Uzasadnienie teoretyczne – równowa no X = 2X
−
X
1
1
0
1
2
0
1
1
1
2
0
1
2
)
(
2
2
2
2
−
−
=
−
−
=
−
−
+
−
=
−
−
−
=
+
−
−
+
−
=
∑
∑
∑
x
x
x
x
x
x
x
X
i
n
i
i
i
i
n
i
i
n
n
i
n
i
i
n
n
}
1
,
0
{
∈
i
x
⇒
}
1
,
0
,
1
{
1
−
∈
−
=
−
i
i
i
x
x
y
(x
–1
= 0)
|{x
n–1
, x
n–2
, x
n–1
, …, x
1
, x
0
}
U2
| = |{(x
n–2
– x
n–1
), (x
n–3
– x
n–2
), …, (x
0
– x
1
), (x
– 1
– x
0
)}
SD
|
Przekodowanie Bootha (
i
i
i
x
x
y
−
=
−
1
)
x
i
x
i–1
y
i
operacja komentarz
0
0
0
—
ci g zer
0
1
1
+
A
koniec ci gu jedynek
1
0
1
−
A
pocz tek ci gu jedynek
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
1
1
1
...
.
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–
24
Alternatywne przekodowanie Bootha
0
2
0
1
1
1
0
1
2
)
(
2
2
)
(
x
x
x
x
x
x
X
i
n
i
i
i
i
n
i
i
i
−
−
=
−
−
=
∑
∑
−
=
+
−
−
=
−
.
⇒ alternatywne przekodowanie mno nika
}
,
,...,
{
0
1
1
y
y
y
n
−
=
Y
1
0
,
1
−
≤
≤
−
=
+
n
i
x
x
y
i
i
i
,
Poniewa
0
2
x
Y
X
−
=
, wi c
•
warto ci pocz tkow akumulowanej sumy iloczynów jest
A
x
0
−
,
•
zamiast mno nej A nale y w algorytmie u y jej podwojenia 2A,
•
y
i
(przekodowanie alternatywne) = y
i+1
(przekodowanie proste)
Przekodowanie alternatywne NB/U2
→
SD zawsze wykonalne:
•
U2
→
SD – rozszerzenie
1
−
=
n
n
x
x
, ⇒
0
1
=
−
n
y
•
NB
→
SD – rozszerzenie
0
=
n
x
⇒
1
1
−
−
=
n
n
x
y
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–25
Przekodowanie rozszerzone (w bazie 2
2
) – algorytm Bootha-McSorleya
1
2
1
0
1
2
2
1
2
1
2
1
0
1
2
2
2
1
2
1
1
2
1
0
1
2
2
2
1
0
2
1
2
1
1
2
0
1
2
)
2
(
2
)
2
2
(
2
)
(
2
)
(
2
)
(
−
−
=
−
+
−
−
=
+
−
−
+
−
=
+
−
=
−
−
−
=
−
−
+
+
−
=
−
−
+
−
=
=
−
−
+
−
=
−
−
=
∑
∑
∑
∑
∑
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
X
i
k
i
i
i
i
i
k
i
i
i
i
i
i
k
i
i
i
i
k
i
i
i
j
k
j
j
j
Poniewa je li
}
1
,
0
{
∈
i
x
to
}
2
,
1
,
0
,
1
,
2
{
2
1
2
2
1
2
+
+
−
−
∈
+
+
−
−
+
i
i
i
x
x
x
(x
−
1
=0), wi c
istnieje jednoznaczne przekształcenie
X
U2
→
Y
SD
:
}
0
1
,
1
0
,
0
0
,
1
0
,
0
1
{
}
,
{
}
,
,
{
}
1
,
0
{
2
1
2
1
2
2
1
2
3
∈
→
∋
+
−
+
i
i
i
i
i
y
y
x
x
x
Wynik przekształce :
SD
0
1
1
}
,
,...,
{
y
y
y
n
−
=
Y
})
1
,
0
,
1
{
(
#
∈
y
takie, e
i
i
i
i
i
y
y
x
x
x
2
1
2
1
2
2
1
2
2
2
+
=
+
+
−
+
−
+
,
0
2
1
2
=
+
i
i
y
y
•
połowa cyfr
Y to zera
•
mo liwe zmniejszenie liczby zer mno nika (00101010
→
0
1
1
0
1
010
).
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–
26
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
⇒ liczba iloczynów cz ciowych
≤
n
2
1
•
dla pary
i
i
x
x
2
1
2
,
+
iloczynem jest
A
x
x
x
i
i
i
)
2
(
1
2
1
2
2
+
−
−
+
o wadze 2
2i
Przekodowanie rozszerzone (Bootha-McSorleya)
x
2i+1
x
2i
x
2i–1
y
2i+1
y
2i
działanie komentarz
0
0
0
0
0
—
ci g zer
0
1
0
0
1
+A
izolowana jedynka
1
0
0
1
0
−
2A
pocz tek ci gu jedynek
1
1
0
0
1
−
A
pocz tek ci gu jedynek
0
0
1
0
1
+A
koniec ci gu jedynek
0
1
1
1
0
+2A
koniec ci gu jedynek
1
0
1
0
1
−
A
izolowane zero
1
1
1
0
0
—
ci g jedynek
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–
27
Alternatywne przekodowanie Bootha-McSorleya
0
2
2
1
2
2
2
1
0
0
2
2
0
1
2
)
2
(
2
2
)
(
2
x
x
x
x
x
x
x
X
i
i
i
i
k
i
j
k
j
j
j
−
+
+
−
=
−
−
=
+
+
−
=
−
=
+
∑
∑
.
}
2
,
1
,
0
,
1
,
2
{
)
2
(
2
1
2
2
2
−
−
∈
+
+
−
+
+
i
i
i
x
x
x
→
wynik przekodowania: Y
SD
taka, e
i
i
i
i
i
y
y
x
x
x
2
1
2
2
1
2
2
2
2
2
+
=
+
+
−
+
+
+
oraz
0
2
1
2
=
+
i
i
y
y
Alternatywne przekodowanie Bootha-McSorleya
x
2i+2
x
2i+1
x
2i
y
2i+1
y
2i
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
1
0
−
4A
koniec ci gu jedynek
1
0
1
0
1
−
2A
izolowane zero
1
1
0
0
1
−
2A
koniec ci gu jedynek
1
1
1
0
0
—
ci g jedynek
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–
28
Algorytm Bootha/Bootha-McSorleya – przykłady
X
= {(1),1,0,1,1,0,0,1}
U2
– w bazie 2 –
}
1
,
1
,
0
,
1
,
0
,
1
,
1
{
=
Y
,
– alternatywne w bazie 4 –
}
01
,
0
1
,
10
,
1
0
{
=
Y
A
=−19
1 0 1 1 0 1
1 0 1 1 0 1
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.
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–
29
Alternatywny algorytm Bootha/Bootha-McSorleya – przykłady
X
= {1,1,0,1,0,1}
U2
– w bazie 2 –
}
1
,
1
,
1
,
1
,
0
{
=
Y
,
– alternatywne w bazie 4 –
}
1
0
,
1
0
,
00
{
=
Y
, P
0
=–x
0
A
Y
(2R)
Y
(4R)
A
=−3
1 1 1 1 0 1
1 1 1 1 0 1
X
=−11
0
1
1
1
1
0 0 0
1
0
1
P
0
=
–x
0
A
0 0 0 0 0 0 0 0 0 1 1
–x
0
A
0 0 0 0 0 0 0 1 1
+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
XA
=
33
0 0 0 0 0 1 0 0 0 0 1
Uwaga
: W polach zacienionych wpisano cyfry rozszerzenia znakowego.
Mno enie
© Janusz Biernat, 03-06-Mnozenie.doc, 4 pa
ź
dziernika 2006
MUL–
30
Przekodowanie mno nika w systemie uzupełnie do 1
W systemie U1, na podstawie równowa no ci X = 2X
−
X
mamy
+
−
−
−
+
−
−
=
∑
∑
−
=
−
−
+
−
=
−
i
n
i
i
n
n
i
n
i
i
n
n
x
ulp
x
x
ulp
x
X
2
)
2
(
2
)
2
2
(
2
0
1
1
1
2
0
1
,
sk d wynika
ulp
x
x
x
x
X
n
i
n
i
i
i
1
1
1
0
1
2
)
(
−
−
−
=
−
+
−
−
=
∑
.
Poniewa ulp = 1, a rozszerzeniem liczby w kodzie U1 jest
1
1
−
−
=
n
x
x
, zatem
i
n
i
i
i
x
x
X
2
)
(
1
0
1
∑
−
=
−
−
=
.
Podobnie
)
(
2
)
(
2
0
1
2
0
1
x
x
x
x
X
n
i
n
i
i
i
−
+
−
=
−
−
=
+
∑
.
•
algorytm analogiczny jak w U2, lecz inna warto pocz tkowa akumulacji
•
sumowanie z uwzgl dnieniem rozszerze prawo- i lewostronnych