Binäre Subtraktion (PASCAL): Grundidee • wähle Basis b > 1

√0 INFO 1 (A-136)
Binäre Subtraktion (PASCAL): Grundidee
• wähle Basis b > 1; Zahlrepräsentation sei k-stellig
• berechne Differenz x – y
• betrachte (o.B.d.A.) 0 ≤ y ≤ x < bk
dann gilt jedoch:
x – y ≡ ( x – y ) mod bk =
= (( x – y ) + bk) mod bk =
= ( x + (bk – y )) mod bk =
= ( x + y”) mod bk
mit y” = bk – y
y” ist allerdings nicht in k Stellen rechenbar, da bk selbst ja
bereits (k+1) Stellen umfasst (bei Repräsentation zur Basis b);
allerdings ist bk – 1 in k Stellen darstellbar
setze daher:
y’ = (bk – 1) – y
dann gilt: y” = y’ + 1
bzw. x – y ≡ (x + ( y’ + 1 )) mod bk
m.a.W., innerhalb der k „signifikanten“ Stellen ist die
Differenz x – y durch
x + ( y’ + 1 ) = x + y”
kalkulierbar
 K.A.Fröschl 2000
OH ♦ 11.1
√0 INFO 1 (A-136)
Binäre Subtraktion (PASCAL): Grundidee
geg.: (x)b, (y)b; Ziffernmenge $b = {δj | 0 ≤ j < b} mit
„größter“ Ziffer δb–1
• bilde zuerst das (b–1)-Komplement von y, (y’)b:
(y’)b = ck–1…c1c0
mit ci ← δb–1 – di (0 ≤ i < k),
wobei (y)b = dk–1…d1d0
ci … „Ziffern-Komplemente“, da ja immer gilt:
ci + di = δb–1
• folglich gilt auch:
kb(y + y’) = bk – 1
und somit kb(y + y’) + 1 = bk
bzw. kb(y + y’ + 1) = bk
nun ist (y”)b = (y’ + 1)b , also lässt sich der Operand (y”)b
durch Addition (in b-Arithmetik) von (y’)b und (1)b berechnen,
sodass (x – y)b auf (x + y”)b ohne jede Subtraktion
rückführbar ist
 K.A.Fröschl 2000
OH ♦ 11.2
√0 INFO 1 (A-136)
60$57&2'(-Funktion zur PASCAL-Subtraktion
6KRUW:RUG →6KRUW:RUGSDVFDO6XE λVG~V
G
3
6KRUW:RUG→6KRUW:RUGSDVFDO.RPSOHPHQW λ[
6KRUW:RUGN
◊
/223
/223
L
M
N ←
LM
JORNDOH=XVWDQGVYDULDEOH



,)[ L M
ö
27+(5:,6(
5(7851N
t
◊
6KRUW:RUG(LQV >>@
5(7851V⊕
>@ >@ @ó
SDVFDO.RPSOHPHQWG⊕ (LQVì
3
3
t
ORNDOH)XQNWLRQ]XU%LOGXQJGHV.RPSOHPHQWVYRQ$UJXPHQW[
ó .RQVWDQWH LQ 6KRUW:RUG5HSUlVHQWDWLRQ LQ YROOHU ([SDQVLRQ ODXWHW GHU ]XJH
ZLHVHQH:HUW
>>@>@@
ì %HUHFKQXQJGHU'LIIHUHQ]GXUFK5FNIKUXQJDXI3$6&$/$GGLWLRQÄ⊕ ¶
ö 6RQGHUIRUPGHU=XZHLVXQJPLW%HGLQJXQJVDXVGUXFNDXIGHUUHFKWHQ6HLWH
x
3
 K.A.Fröschl 2000
OH ♦ 11.3
√0 INFO 1 (A-136)
60$57&2'(-Funktion zur PASCAL-Addition
Version 1: positionsweise Addition
6KRUW:RUG →6KRUW:RUGSDVFDO$GG
◊
/223
λ([\a[ ⊕ \
3
6KRUW:RUGUHV←[
/223
ELW
óUHV←DGG3RVUHVELW∗E\WHìö
:+(5(0 ^N_\ `
E\WH0
NELW
N
5(7851UHV
t
]XHUVW ZLUG HLQ :HUW IU 6FKOHLIHQYDULDEOH ELW lXHUH 6FKOHLIH JHZlKOW PLW GLHVHP
GDQQGLH,QGH[PHQJHIU6FKOHLIHQYDULDEOHE\WHHUPLWWHOW
ó ,QGLFHVELWXQGE\WHGXUFKODXIHQGLH0HQJHGHU,QGLFHVMHQHU3RWHQ]HQYRQGLHLQ
2SHUDQG \ DXIWUHWHQ ZREHL IU MHGHQ :HUW YRQ ELW ]XQlFKVW GLH ,QGL]HV GHU %\WHV
EHVWLPPWZHUGHQZRHLQHHU3RWHQ]LPELWWHQ%LWYRUNRPPWGLHKLHUDQJZDQGWH
0HWKRGHGHU,QGH[*HQHULHUXQJLVWVLFKHUOLFKQLFKWGLHHLQ]LJP|JOLFKH²EVSZZlUH
lTXLYDOHQW
/223
/223
ELW
,)\
E\WH
7+(1UHV←DGG3RVUHVELW∗E\WH
E\WHELW
ì YRUOlXILJZLUGXQWHUVWHOOWGDVVGHUDUWLJH$XVGUFNHLP6LQQHGHUEOLFKHQ$ULWKPHWLN
DXVZHUWEDUVLQG
ö)XQNWLRQÄDGG3RV¶ZLHYRUKLQEHUHLWVIUGLH1$3,(5$GGLWLRQGHILQLHUW
x
 K.A.Fröschl 2000
OH ♦ 11.4
√0 INFO 1 (A-136)
60$57&2'(-Funktion zur PASCAL-Addition
Version 2: bit-serielle Addition
6KRUW:RUG →6KRUW:RUGSDVFDO$GG λ[\a[⊕ \
3
7<3(%LW$GG
〈%LWVWHOOHEHUWUDJ〉
6KRUW:RUGUHV%LW$GGQH[W%LW
%LWFDUU\%LW←
%LW3→%LW$GGELW6HULHOO λDEFó
◊
,)D E F  〈〉
5(7851
,)D E F  〈〉
,)&RQG
 〈〉
27+(5:,6(
 〈〉
:+(5(&RQG
◊
/223
D≠E∧F ∨D E ∧F ì
t
/223
E\WHV
ö
ELW
UHV
←QH[W%LWVWHOOH
FDUU\%LW←QH[W%LWEHUWUDJ
:+(5(QH[W%LW ELW6HULHOO[
E\WHELW
\
E\WHELW
FDUU\%LW
E\WHELW
5(7851UHV
t
5HJLVWHUIUGLH$XIQDKPHGHVhEHUWUDJVGHUELWZHLVHQ$GGLWLRQ,QLWLDOLVLHUXQJPLW
ó ORNDOH)XQNWLRQ]XU$GGLWLRQMHZHLOVHLQHU%LW6WHOOHDOV(UJHEQLVHUJLEWVLFKGLH
6XPPHQ]LIIHUGHUMHZHLOLJHQ6WHOOH%LWVRZLHGLHhEHUWUDJ,QIRUPDWLRQ%LW
DXVGHPYRUKHULJHQ6FKULWWLVWGDEHLHLQDOOHQIDOOVEHVWHKHQGHUhEHUWUDJ]XEHUFN
VLFKWLJHQ$UJXPHQWF
ì GLHVH²ORJLVFKH²%HGLQJXQJGHFNWDOOH)lOOHDELQGHQHQNHLQhEHUWUDJEHLGHU
ELWZHLVHQ$GGLWLRQGHU6WHOOHDXIWULWW
ö EHLGLHVHUVWHOOHQZHLVHQ9HUNQSIXQJZLUGGDV5HJLVWHUÄFDUU\%LW¶GXUFKGLH=X
ZHLVXQJVRSHUDWLRQVWHWVQHXJHVHW]W=XVWDQGVEHUJDQJLQMHGHP6FKOHLIHQGXUFK
JDQJZLUG]XGHPHLQZHLWHUHV%LWGHU6XPPHHUPLWWHOW
x
 K.A.Fröschl 2000
OH ♦ 11.5
√0 INFO 1 (A-136)
PASCAL-Subtraktion: Beispiel
P
P
Q mit
P = 0x005D = (93)10
Q = 0x002E = (46)10
d.h. (P–Q)10 = (47)10
dekadisch (16 Binärstellen):
≡²PRG
PRG
PRG
3
hexadezimal (4 Stellen):
4· [))'
ZHLO44· [([))' [))))
4µ 4·[ [))'
3
4≡34µPRG
['[))'PRG
[)PRG[
[)
3
[
in der 60$57&2'(-Version:
3
>>@>@ @
4
>>@>@ @
4·
>>@>@ @
4µ
>>@>@ @
3⊕34µ
>>@>@ @
8QWHUVWUHLFKXQJKLHUWULWW%LWhEHUWUDJDXI
 K.A.Fröschl 2000
OH ♦ 11.6

Download Report