Redundante Zahlensysteme Redundante Zahlensysteme (Forts.)

Redundante Zahlensysteme
• redundante Darstellung einer Zahl x zur Basis b:
n 1
x
b ˜ xi
¦
i 0
i
k 1
bzw. x
m
b ˜ xi ¦ b i ˜ xi
¦
i 0
i 1
i
mit Ziffer
xi  { (b 1), (b 2), ... , –2, –1, 0, 1, 2, ... , b –2, b –1}
• Eigenschaften:
Für jede Zahl x z 0 mit n t 2 (bzw. k+m t 2) existieren viele gleichwertige Darstellungen, Kodierung mit den meisten Nullen heißt minimal
separates Vorzeichen für negative Zahlen entfällt! Vorzeichen wird
implizit festgelegt durch Vorzeichen der höchstwertigen Ziffer xi z0
Für die Basis b = 2 ergibt sich xi  {–1, 0, 1}; zur Speicherung einer
jeden Ziffer xi werden somit 2 Bit benötigt
auch als „Signed-Digit Representation“ (SD) bezeichnet
wurden bereits in Algorithmen zur Multiplikation (Recoding) und zur
Division (Kodierung des Quotienten bei SRT-Verfahren) eingesetzt
Computer-Arithmetik, SS 2005
A. Strey, Universität Ulm
Kapitel 5 : Unkonventionelle Zahlensysteme
1
Redundante Zahlensysteme (Forts.)
• Addition/Subtraktion:
Bestimmung von (sn–1 sn–2 ... s1 s0) = (xn–1 xn–2 ... x1 x0) + (yn–1 yn–2 ... y1 y0)
durch folgenden Algorithmus:
für alle i = 0,...,n-1 {
­1 falls xi yi t a
°
setze ci ®0 falls a xi yi a
mit a b 1
°̄ 1 falls xi yi d a
berechne zunächst ui xi yi ci ˜ b
und dann si ui ci 1 mit c1 0
}
Da stets |ui| d b – 2 und |si| d b – 1 gilt, kann in keiner Stelle i mehr ein
Überlauf auftreten! Dies ist jedoch nur erfüllt für eine Basis b t 3.
Für Basis b = 2 kann jedoch gezeigt werden, daß ui und ci in Abhängigkeit
von xi, yi, xi–1 und yi–1 derart bestimmt werden können, daß kein Überlauf bei
der Operation si = ui + ci–1 auftritt!
Computer-Arithmetik, SS 2005
A. Strey, Universität Ulm
Kapitel 5 : Unkonventionelle Zahlensysteme
2
Redundante Zahlensysteme (Forts.)
• Multiplikation: Booth-Algorithmus kann hier unverändert
übernommen werden; jedoch einfachere Realisierung:
– Umkodierung des Multiplikators entfällt
– CSA- und CLA-Addierer überflüssig, da Addition redundant kodierter
Teilprodukte bereits ausreichend schnell ist
• Konvertierung von x = (xn–1 xn–2 ... x1 x0) in Binärzahl y:
Annahmen: x sei redundante Zahl zur Basis b, b sei Zweierpotenz
Algorithmus: y(0) = xn–1, y(i+1) = b ˜ y(i) + xn–i–1 , y = y(n)
erfordert n Shifts und n Additionen mit Carry-Propagation !
• Zusammenfassung:
+ schnellere (übertragsfreie) Addition, einfachere Multiplikation
– höherer Speicherbedarf für jede Zahl
– Umwandlung von/in Zweierkomplement aufwendig
Computer-Arithmetik, SS 2005
A. Strey, Universität Ulm
Kapitel 5 : Unkonventionelle Zahlensysteme
3
Logarithmische Zahlensysteme
• Ziel: Beschleunigung von Multiplikation, Addition und
Quadratwurzel
• Idee: Nutzung der Eigenschaften von Logarithmen
• Darstellung von x in logarithmischer Darstellung: x = (–1)s u 2e
mit e = log2(x): e = ek–1 ... e1 e0 . e–1 e–2 ... e–n mit k binären
Vorkommastellen und n binären Nachkommastellen
• Anmerkungen:
– entspricht einer entarteten Gleitkommazahl mit fester Mantisse 1 und
Exponent e als Festkommazahl
– auch Logarithmus zur anderen Basis (z.B. e oder 10) möglich
– Werte x < 1 erfordern negativen Exponenten e; daher wird x oft auch mit
Bias dargestellt: x = (–1)s u 2e–bias mit bias = 2k–1 oder bias = 2k–1 – 1
– x = 0 kann nicht direkt dargestellt werden !
Ÿ mögliche Lösung: Reservierung von emin = 0 zur Darstellung der 0
Computer-Arithmetik, SS 2005
A. Strey, Universität Ulm
Kapitel 5 : Unkonventionelle Zahlensysteme
4
Logarithmische Zahlensysteme (Forts.)
• Multiplikation / Division:
p = a ˜ b = (1)s u 2D ˜ (1)t u 2E = (1)s † t u 2D+E
q = a / b = (1)s u 2D / (1)t u 2E = (1)s † t u 2DE
Eigenschaften:
erfordern lediglich eine einfache Addition / Subtraktion der Exponenten!
Überlauf und Unterlauf sind möglich, jedoch einfache Detektion
kein Runden erforderlich Ÿ Ergebnis exakt !
• Addition / Subtraktion:
s = a r b = a ˜ (1 r b / a) : (1)u u 2J o.B.d.A. mit |a| > |b|
J log2 |a ˜ (1 r b / a)| = log2 |a| + log2 |1 r b / a| = D + )(ED)
wobei die Funktionswerte )(ED) = log2 |1 r b / a| = log2 |1 r 2ED| entweder
direkt einer Tabelle (z.B. im ROM) entnommen werden oder tabellenbasiert
interpoliert werden
Computer-Arithmetik, SS 2005
A. Strey, Universität Ulm
Kapitel 5 : Unkonventionelle Zahlensysteme
5
Restklassen-Zahlensysteme
• Theorie: Zwei Zahlen a und b heißen kongruent modulo m,
falls m die Zahlen mit dem gleichen Rest teilt: a { b mod m
m z 1 heißt Modulus, der Rest r {0,1,...,m–1} heißt Residuum
von a bzw. b bezogen auf m, d.h. a { r mod m, b { r mod m
• Idee: Seien nun m1, m2, ...,mn Moduli mit M = –i mi ohne einen
gemeinsamen Teiler z 1, so kann eine Zahl x < M eindeutig
durch die resultierenden Residuen (r1, r2,...,rn) dargestellt werden
• Beispiel: Seien m1=2, m2=3, m3 =5, dann kann 13 eindeutig
kodiert werden durch (1, 1, 3) und 14 durch (0, 2, 4)
• Anmerkungen:
– auch negative Zahlen sind möglich, z.B. kann –7 mit m1=2, m2=3, m3 =5
kodiert werden als (1,2,3); jedoch muß dann –M/2 < x < M/2 –1 gelten
– keine direkte Repräsentation von Festkomma-Zahlen
– i.a. werden Moduli mi = 2e[i] – 1 mit geeigneten Werten e[i] verwendet
Computer-Arithmetik, SS 2005
A. Strey, Universität Ulm
Kapitel 5 : Unkonventionelle Zahlensysteme
6
Restklassen-Zahlensysteme (Forts.)
Seien (x1, x2, ... xn–1, xn) und (y1, y2, ... yn–1, yn) die Darstellungen
von x und y als Residuen in Bezug auf m1, m2, ..., mn–1, mn
• Addition: Die Summe s = (s1 s2 ... sn–1 sn) = x + y kann ermittelt
werden durch Berechnung von si { (xi + yi) mod mi. Bei einer
Wahl von mi = 2e[i] – 1 folgt:
si { ( xi yi ) mod(2e[i] 1)
­xi yi
falls xi yi 2e[i] 1
°
falls xi yi 2e[i] 1
®0
°(( xi yi ) mod 2e[i] ) 1 sonst
¯
• Multiplikation: Das Produkt p = (p1, p2, ... , pn–1, pn) = x ˜ y kann
ermittelt werden durch Berechnung von pi { (xi ˜ yi) mod mi. Bei
einer Wahl von mi = 2e[i] – 1 folgt:
pi { (xi ˜ yi) mod (2e[i] – 1) = ((xi ˜ yi) mod 2e[i] + (xi ˜ yi) / 2e[i])) mod (2e[i] – 1)
Ÿ Restklassen-Addition der höherwertigen und der niedrigwertigen Bits von xi ˜ yi
Computer-Arithmetik, SS 2005
A. Strey, Universität Ulm
Kapitel 5 : Unkonventionelle Zahlensysteme
7
Restklassen-Zahlensysteme (Forts.)
• Subtraktion: Differenz d = x – y wird bestimmt durch Bildung
der additiven inversen Elemente: (–yi) mod mi : (mi – xi) mod mi
und Berechnung von di { (xi + (yi) mod mi) mod mi.
• Erkennung von Überlauf und Vorzeichen des Resultates bei
arithmetischen Operationen sehr umständlich !
• Konvertierung von (x1 x2 ... xn–1 xn) in Binärzahl x durch Einsatz
des „Chinese Remainder Theorem“:
M
M
M·
M
§
... cn xn ¸ mod M , Wahl der ci : ci
x { ¨ c1x1 c2 x2
{ 1 mod mi
m1
m2
mn ¹
mi
©
• Zusammenfassung:
–
–
–
–
schnelle Addition, Subtraktion und Multiplikation
Vergleich und folglich auch Division sind sehr umständlich
Konvertierung aus/ins Zweierkomplement aufwendig
einfache Fehlererkennung und Fehlerkorrektur
Computer-Arithmetik, SS 2005
A. Strey, Universität Ulm
Kapitel 5 : Unkonventionelle Zahlensysteme
8