Dieses Buch entstand aus einer Reihe von Vorlesungen und Seminaren an der Universitat Saarbrlicken. Es enthalt eine vergleichende Be schreibung von schnellen und kostenglinstigen Algorithmen zur Reali sierung arithmetischer Operationen in Digitalrechnern. Obwohl fast aIle Informatiker und nicht wenige Wissenschaftler an derer Fachrichtungen mit diesen Problemen mehr oder weniger inten siv konfrontiert werden, behandeln deutschsprachige Fachblicher mit allgemeinerer Zielsetzung diese Fragen nur am Rande oder in ver gleichsweise kurzen Kapiteln; dies flihrt zwangslaufig zu einer Be schrankung auf die Beschreibung der bekanntesten und einfachsten Verfahren. In der englischsprachigen Literatur gibt es zwar mehre re ausgezeichnete Standardwerke (zu erwahnen ist hier in erster Li nie Flores "The Logic of computer Arithmetic"), doch sind diese oft nur schwer zuganglich und meist alteren Datums; viele wichtige Re sultate wird man dort also vergeblich suchen. Der Mangel an neueren Blichern liber Rechnerarithmetik kann nicht dar auf zurlickgeflihrt werden, daB aIle interessierenden Probleme be reits in Standardwerken abgehandelt sind: die Anzahl und die Rele vanz der in jlingster Zeit veroffentlichten Arbeiten beweist das Ge genteil. Die Hauptursache daflir liegt nach meiner Ansicht vielmehr in der oft uneinheitlichen Darstellung und der zu starken Beschran kung vieler Arbeiten auf ein bestimmtes Maschinenkonzept oder auf eine zur Zeit verfligbare bzw. in Entwicklung befindliche Baustein serie, wodurch eine zusammenfassende Ubersicht sehr erschwert wird.
Inhaltsverzeichnis
1. Zahlendarstellung. - 1. 1 d-näre Stellenwertcodierungen. - 1. 2 Einbettung in längere Zahlendarstellungen; Überlaufproblem. - 1. 3 Arithmetik bei d-nären Stellenwertcodierungen. - 1. 4 Andere Zahlendarstellungen. - 1. 5 Basiswahl, Register, Schaltwerke, Mikroprogramme. - 1. 6 Fest- und Gleitkommadarstellungen. - 2. Addierwerke. - 2. 1 (m, k)-Zähler, Halfadder, Fulladder. - 2. 2 Beschreibung der Logik einfacher Addierwerke (Zahlendarstellung, serielle Addition, von-Neumann-Addier-werk, Carry-Save-Addition, Adder tree, Carry-Ripple-Addition, asynchrone C-R-Addition, Exclusive-Or-Addition). - 2. 3 Carry-Look-Ahead-Addition4. - 2. 4 Carry-Skip-Addition (konstante Gruppengröße g, variable Gruppengröße, Carry-Skip-Addition höherer Ordnung). - 2. 5 Conditional-Sum-Addition. - 2. 6 Carry-Select-Addition. - 2. 7 Zusammenfassung, Vergleich. - 3. Multiplikation. - 3. 1 Registerkonfiguration, Zahlendarstellung, Überlaufproblem. - 3. 2 Serielle Multiplikation ohne Multiplikatorcodierung. - 3. 3 Multiplikatorcodierung. - 3. 4 Ungetaktete bzw. parallele Multiplizierverfahren (Multiplikationsmatrix, Reduktion, Mult. durch Carry-Save-Addition, parallele Multiplikation nach Wallace und Dadda, Aufwandsuntersuchungen, Faktoren unterschiedlicher Länge, Multiplikation zur Basis 2h). - 3. 5 Arithmetische Schaltkreise. - 3. 6 Pipelining-Prinzipien. - 4. Division. - 4. 1 Grundlagen. - 4. 2 Serielle Divisionsverfahren für nichtnegative Operanden (Restoring-, Non-Performing-, Non-Restoring-Division, Division mit Shift über Nullen und Einsen). - 4. 3 Negative Operanden. - 4. 4 Beschleunigung der Division durch Verwendung geeigneter Vielfacher des Divisors (Table-Look-Up-Division, Verwendung spezieller Divisorvielfacher). - 4. 5 Iterative Division. - 5. Redundante Zahlendarstellung. - 5. 1 SDNR-Darstellung zur Basis d ? 3. - 5. 2Parallele Addition von SDNR-Summanden. - 5. 3 Anwendung von SDNR-Zahlen bei Multiplikation bzw. Division. - 5. 4 Parallele Addition bzw. Subtraktion bei unterschiedlicher Darstellung der Summanden. - 5. 5 SRT-Division. - 6. Berechnung von speziellen Funktionen. - 6. 1 Berechnung von Logarithmen. - 6. 2 Berechnung von Arc tan (y/x). - 6. 3 Berechnung von $$\sqrt {{ \frac{y}{x}}}$$. - 6. 4 Umkehrfunktionen. - 6. 5 Das CORDIC-Verfahren zur Berechnung von arithmetischen Funktionen. - 7. Zeitkomplexität von arithmetischen Operationen. - 7. 1 Beschreibung des Modells. - 7. 2 Untere Laufzeitschranken für arithmetische Operationen. - 7. 3 Obere Schranken. - 7. 4 Berechnung der Funktionen ? 1 und ? 2 (Addition) bei binärer Stellenwertcodierung der Ein- und Ausgänge des Schaltkreises. - Verzeichnis der Symbole.
