--- title: "Kapitel 04 - Rechnerarithmetik" source: "ti-4-deck.html" generated-by: uni-vault/sync.py --- # Kapitel 04 - Rechnerarithmetik ## Title Einführung in die Technische Informatik Prof. Jian-Jia Chen | Dr.-Ing. Christian Hakert | Dr. rer. nat. Marcus Völker RWTH Aachen University ## Kapitel 4: Rechnerarithmetik ## Einleitung **Rechnen zu können ist für Computer zentral** - Grundlegende Rechenoperationen sollten durch die Hardware unterstützt werden. **Betrachtete Rechenoperationen** - Addition - Subtraktion - Multiplikation - **Keine Division** **Betrachtete Datentypen** - Natürliche Zahlen - Ganze Zahlen - Rationale Zahlen (IEEE 754-1985) ## Abschnitt 4.1 Addition natürlicher Zahlen - Halbaddierer und Volladdierer - Ripple-Carry-Addierer - Carry-Look-Ahead-Addierer - Fan-In ## Addition natürlicher Zahlen **Schulalgorithmus für die Addition von Dezimalzahlen** \[\begin{array}{l|cccccccc} \text{1. Summand} & & 9 & 3 & 8 & 9 & 9 & 8 & 9\\ \text{2. Summand} & & & 9 & 7 & 9 & 8 & 9 & 8\\ \text{Übertrag} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ \hline \text{Summe} & 1 & 0 & 3 & 6 & 9 & 8 & 8 & 7 \end{array}\] **Übertragung auf Binärzahlen** \[\begin{array}{l|cccccccc} \text{1. Summand} & & 1 & 1 & 0 & 0 & 1 & 1 & 1\\ \text{2. Summand} & & 1 & 0 & 0 & 1 & 0 & 1 & 1\\ \text{Übertrag} & 1 & & & 1 & 1 & 1 & 1 & \\ \hline \text{Summe} & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \end{array}\] ## Addition natürlicher Zahlen **Beobachtung zu den Überträgen** - \(1+1\) erzeugt einen Übertrag - \(0+0\) eliminiert einen vorhandenen Übertrag - \(0+1\) und \(1+0\) reichen einen vorhandenen Übertrag weiter - Übertrag ist höchstens 1 **Kann man Addition als Boolesche Funktion ausdrücken?** - **Summenbit** \(s\) und **Übertrag** \(c\) (*engl. carry*) - \(f_{HA}:B^2\to B^2\) - \(f_{HA}\) realisiert die Forderungen zum Teil \(x\) \(y\) \(c\) \(s\) 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 ## Halbaddierer \(f_{HA}\) realisiert einen sog. **Halbaddierer** \(f_{HA}:B^2\to B^2\) \(x\) \(y\) \(c\) \(s\) 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 **Schaltung für den Halbaddierer:** \(\quad c=x\land y \qquad s=x\oplus y\) **Wie viele Gatter benötigt ein Halbaddierer und wie tief ist ein Halbaddierer?** - Größe: 1, Tiefe: 1 - Größe: 2, Tiefe: 1 - Größe: 1, Tiefe: 2 - Größe: 2, Tiefe: 2 - Größe: 5, Tiefe: 2 **Beobachtung** - Gültig nur für isolierte Ziffern - **Berücksichtigung des vorherigen Übertrags fehlt** ## Volladdierer **Halbaddierer** - Berechnet Übertrag aus der Addition - Berücksichtigt keinen Übertrag, der schon vorher entstanden ist **Volladdierer** - \(f_{VA}:B^3\to B^2\) - Berechnet **Übertrag \(c\) ** aus der Addition - Berücksichtigt **Übertrag \(c_{alt}\) **, der schon vorher entstanden ist \(c_{alt}\) \(x\) \(y\) \(c\) \(s\) 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 ## Volladdierer **Beobachtung für \(s\) ** - \(s=1\Leftrightarrow\) Anzahl der Einsen ungerade - \(s=c_{alt}\oplus x\oplus y\) **Beobachtung für \(c\) ** - \(c=1\Leftrightarrow\) Anzahl Einsen \(\geq 2\) - DNF: \(c=\overline{c_{alt}}xy\lor c_{alt}\overline{x}y\lor c_{alt}x\overline{y}\lor c_{alt}xy\) - Resolution: \(\overline{c_{alt}}xy\lor c_{alt}xy=xy\) - \(c_{alt}xy\lor c_{alt}\overline{x}y=c_{alt}y\) - \(c_{alt}xy\lor c_{alt}x\overline{y}=c_{alt}x\) - \(\boldsymbol{c=xy\lor c_{alt}y\lor c_{alt}x}\) \(c_{alt}\) \(x\) \(y\) \(c\) \(s\) 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 ## Volladdierer - Verbesserte Realisierung für \(c\) - Durch Wiederverwenden von Teilergebnissen **Es gilt bisher:** \(c=xy\lor c_{alt}y\lor c_{alt}x\) Wir müssen die Belegungen für \((c_{alt},x,y)\in\{(011),(101),(110),(111)\}\) realisieren - \(x\oplus y=1\Leftrightarrow\) genau eine 1 in \(x,y\) - Also \(c_{alt}(x\oplus y)\) realisiert \(c\) für \(\{(101),(110)\}\) - Fehlen noch die Belegungen \(\{(011),(111)\}\) , realisiert durch \(xy\) \(\Rightarrow c=c_{alt}(x\oplus y)\lor xy\) \(c_{alt}\) \(x\) \(y\) \(c\) \(s\) 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 ## Schaltnetz Volladdierer - \(s=c_{alt}\oplus x\oplus y\) - \(c=c_{alt}(x\oplus y)\lor xy\) - Größe 5 - Tiefe 3 \(c_{alt}\) \(x\) \(y\) \(c\) \(s\) 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 ## Vollständiger Addierer ## Vollständiger Addierer ## Natürliche Zahlen addieren - **Größe:** \(2+(n-1)\cdot 5=5n-3\) - **Tiefe:** \(1+(n-1)\cdot 3=3n-2\) ## Ergebnis: Ripple-Carry-Addierer **Realisierung „Addition von natürlichen Zahlen“** - Sehr gut strukturiert - Größe \(5n-3\) \(\quad\rightarrow\) **sehr klein** - Tiefe \(3n-2\) \(\quad\rightarrow\) **viel zu tief** **Warum ist unser Schaltnetz so tief?** - Offensichtlich gilt: Überträge brauchen sehr lange - Verbesserungsidee: **Überträge früh berechnen** - Wie? Struktureinsicht ## Struktureinsicht - \((x_i,y_i)=(1,1)\) **generiert** Übertrag - \((x_i,y_i)=(0,0)\) **eliminiert** Übertrag - \((x_i,y_i)\in\{(0,1),(1,0)\}\) **reicht** Übertrag **weiter** Dieses Verhalten ist sehr gut durch einen **Halbaddierer** realisierbar - \(u_i=1\) **generiert** Übertrag - \(v_i=1\) **reicht** Übertrag **weiter** **Zentrale Beobachtung** - Jeder HA ist in **Tiefe 1** parallel realisierbar und berechnet \(u_i\) und \(v_i\) \(x_i\) \(y_i\) \(u_i\) \(v_i\) Übertrag 0 0 0 0 eliminieren 0 1 0 1 weiterreichen 1 0 0 1 weiterreichen 1 1 1 0 generieren ## Carry-Look-Ahead-Addierer **Notation** - \(f_{HA}:B^2\to B^2\) , \(f_{HA}(x_i,y_i)=(u_i,v_i)\) - \(u_i=1\) **generiert** Übertrag, \(v_i=1\) **reicht** Übertrag **weiter** **Vorausberechnung der Überträge** \[c_i=u_{i-1}\lor c_{i-1}v_{i-1}\] ## Carry-Look-Ahead-Addierer **Notation** - \(f_{HA}:B^2\to B^2\) , \(f_{HA}(x_i,y_i)=(u_i,v_i)\) - \(u_i=1\) **generiert** Übertrag, \(v_i=1\) **reicht** Übertrag **weiter** **Vorausberechnung der Überträge** \[\begin{aligned} c_1 &= u_0\\ c_2 &= u_1\lor u_0v_1\\ c_3 &= u_2\lor u_1v_2\lor u_0v_1v_2\\ c_4 &= u_3\lor u_2v_3\lor u_1v_2v_3\lor u_0v_1v_2v_3\\ c_i &= u_{i-1}\lor u_{i-2}v_{i-1}\lor u_{i-3}v_{i-2}v_{i-1}\lor\ldots\lor u_0v_1v_2\cdots v_{i-1} \end{aligned}\] \[c_i=\bigvee_{j=0}^{i-1}\Big(u_j\land\bigwedge_{k=j+1}^{i-1}v_k\Big)\] ## Carry-Look-Ahead-Addierer \[c_i=\bigvee_{j=0}^{i-1}\Big(u_j\land\bigwedge_{k=j+1}^{i-1}v_k\Big)\] **Gesamttiefe des CLA: 4** Baustein Tiefe Alle Halbaddierer ( \(u_i,v_i\) ) 1 Alle Und-Gatter \(\big(u_j\land\bigwedge_{k=j+1}^{i-1}v_k\big)\) 1 Großes Oder-Gatter 1 \(n\times\oplus\) -Gatter für korrekte Summenbits 1 ## Carry-Look-Ahead-Addierer Quelle: Denis Pitzschel ## Carry-Look-Ahead-Addierer Quelle: Denis Pitzschel ## Carry-Look-Ahead-Addierer **Waren wir wirklich fair bei der Bestimmung der Ebenen?** - Beliebig lange Zahlen in Tiefe 4 addieren … - Anzahl Eingänge eines Gatters heißt **Fan-In** Nehmen wir an, dass wir nur ODER-Gatter mit Fan-In 2 haben. Wie viele Gatter brauchen wir, um eine ODER-Logik mit Fan-In 16 zu implementieren? - 1 - 4 - 7 - 8 - 15 - 16 ## Vermeidung von großem Fan-In Großes Fan-In **systematisch** verkleinern **Beispiel:** ODER, Fan-In 16 ## Carry-Look-Ahead-Addierer **Waren wir wirklich fair bei der Bestimmung der Ebenen?** - Beliebig lange Zahlen in Tiefe 4 addieren … - Anzahl Eingänge eines Gatters heißt **Fan-In** - Wir vergleichen ein Schaltnetz mit max. Fan-In 2 **(Ripple-Carry-Addierer)** - mit einem Schaltnetz mit max. Fan-In \(n\) **(Carry-Look-Ahead-Addierer)** - Große Fan-Ins sind technologisch schwierig zu realisieren **Ziel:** Vergleichbarkeit herstellen ## Vermeidung von großem Fan-In **Am Beispiel** - Aus Fan-In 16 bei Tiefe 1 (Größe 1) - wird Fan-In 2 bei Tiefe 4 (Größe 15) **Wie lässt sich das verallgemeinern?** - **Größe** Bei jeder Stufe halb so viele Gatter wie in der Stufe davor - \(\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\ldots+1\approx n\) (*geometrische Reihe*) - **Tiefe** So oft halbieren, bis man bei einem Gatter ist - \(\approx\log_2(n)\) ## Carry-Look-Ahead-Addierer (CLA) - Fokus auf AND-Gatter: \[\sum_{i=1}^{n}\sum_{j=1}^{i}(j-1)\] - Größe \(\approx\frac{n^3}{6}\) - Tiefe \(\approx 2\log_2(n)\) Wolfram Alpha ## Carry-Look-Ahead-Addierer (CLA) **Realisierung der Addition von natürlichen Zahlen** - Gut strukturiert - Größe \(\approx\frac{n^3}{6}\) \(\quad\leftarrow\) ziemlich groß - Tiefe \(\approx 2\log_2(n)\) \(\quad\leftarrow\) ziemlich flach **Vergleich zum Ripple-Carry-Addierer** \(n\) Ripple-Carry Größe Ripple-Carry Tiefe Carry-Look-Ahead Größe Carry-Look-Ahead Tiefe 8 37 22 170 6 16 77 46 1365 8 32 157 94 10922 10 64 317 190 87381 12 ## Quiz: Addierer Welcher Addierer ist besser? - Ripple-Carry-Addierer - Carry-Look-Ahead-Addierer ## Addition natürlicher Zahlen Darstellung der Tiefe / Größe ## Carry-Skip-Addierer: Motivation - CLA ist flach, aber **groß** ( \(\approx\frac{n^3}{6}\) ) und komplex - **Frage:** Können wir den Ripple-Carry-Addierer nur **etwas** verbessern, sodass er zumindest **manchmal** schneller ist? **Schlechtester Fall im RCA:** alle Stellen reichen den Übertrag weiter, d.h. \(v_i=1\) für alle \(i\) \(\Rightarrow\) Der Übertrag \(c_0\) läuft durch alle \(n\) Volladdierer **Eigentlich ein einfacher Fall:** Wenn alle Stellen weiterreichen, gilt \(c_n=c_0\) - Dafür genügt die Propagate-Bedingung \(P=v_0\land v_1\land\ldots\land v_{n-1}\) - Ein einziges Und-Gatter, die \(v_i\) liegen nach Tiefe 1 vor (Halbaddierer) ## Carry-Skip-Addierer **Idee:** mehrere kleine RCAs, jeder mit eigenem Propagate-Check - \(P_j\) : alle Stellen des Blocks reichen weiter \(\Rightarrow\) Übertrag **überspringt** den Block - Sonst entsteht der Übertrag im Block selbst: normaler RCA-Übertrag \[c_{\text{aus}}=c_{\text{RCA}}\lor\big(P_j\land c_{\text{ein}}\big)\] ## Carry-Skip-Addierer: ein Block im Detail - \(v_i=x_i\oplus y_i\) berechnet jeder Volladdierer ohnehin (erstes XOR) \(\Rightarrow\) nur herausführen - \(P_j=v_0\land v_1\land v_2\land v_3\) : ein Und-Gatter, parallel zur Übertragskette ## Carry-Skip-Addierer: Bewertung - **Größe:** RCA plus je Block ein Und-Gatter für \(P_j\) , ein Und und ein Oder \(\Rightarrow\) nur wenig größer als RCA - **Ungünstigster Übertrag:** entsteht im ersten Block, läuft durch ihn hindurch, **überspringt** alle mittleren Blöcke und läuft nur noch durch den letzten Block - **Aber:** Der lange Pfad durch alle RCAs existiert im Schaltnetz weiterhin Die **Tiefe** des Schaltnetzes bleibt wie beim RCA - Er wird nur nie gebraucht: Muss ein Übertrag lange weitergereicht werden, nimmt er die Abkürzung - **Fazit:** Kompromiss zwischen RCA (klein, langsam) und CLA (groß, flach) ## Abschnitt 4.2 Multiplikation natürlicher Zahlen - Addition vieler Zahlen - Carry-Save-Addierer - Wallace-Tree ## Multiplikation Direkt mit Binärzahlen … \[\begin{array}{ccccccccccccccc} 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & \cdot & 1 & 1 & 1 & 0 & 1 & 0\\ \hline & & & & & & & & & & & & & & 0\\ & & & & & & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & \\ & & & & & & & & & & & & 0 & & \\ & & & & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & & & \\ & & & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & & & & \\ & & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & & & & & \\ \hline & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \end{array}\] **Multiplizieren heißt** - Nullen passend schreiben - Zahlen passend verschoben kopieren - Viele Zahlen addieren ## Multiplikation als Schaltnetz **Multiplikation** ist - Nullen passend schreiben - Zahlen passend verschoben kopieren - Viele Zahlen addieren **Beobachtung** - Nullen schreiben: **einfach** und **kostenlos** - Zahlen verschieben und kopieren: **einfach** und **kostenlos** - **Viele** Zahlen addieren: nicht ganz so einfach ## Multiplikation: Addition vieler Zahlen - Wir haben Addierer für die Addition zweier Zahlen - Wie addieren wir damit \(n\) Zahlen? **Erster Ansatz:** Einfach nacheinander - Schema hat die Tiefe \((n-1)\) - In jeder Ebene noch die Tiefe des Addierwerks - Tiefe \(=(n-1)\cdot\) Tiefe(Addierer) \(\Rightarrow\) ist zu tief! **Idee** - In Schaltnetzen **niemals** alles nacheinander tun! - Was geht gleichzeitig? ## Multiplikation: Addition vieler Zahlen **Besserer Ansatz:** Paarweise addieren **Bewertung** - Anzahl Addierer \(=\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\ldots+1\approx n\) - Gesamtgröße \(\approx n\cdot\) Größe(Addierer) - Tiefe \(\approx\log_2(n)\) Ebenen **Gesamttiefe** \(\approx\log_2(n)\cdot 2\log_2(n)=2(\log_2(n))^2\) (Anzahl der zu addierenden Bitvektoren ist gleich der Anzahl Bits) ## Multiplikation: Addition vieler Zahlen **Gibt es einen noch besseren Ansatz?** **Beobachtung** - Addition ersetzt **zwei** Zahlen - durch **eine** Zahl gleicher Summe **Zentral für uns** - Gleiche Summe \(\rightarrow\) Korrektheit - Weniger Zahlen \(\rightarrow\) Fortschritt **(Verrückte?) Idee:** Vielleicht ist es einfacher, **drei** Zahlen zu ersetzen durch **zwei** Zahlen gleicher Summe? Sei \(x=(001)\) , \(y=(010)\) , \(z=(011)\) . Welche Bitvektoren \(a\) und \(b\) erfüllen die Bedingung \(x+y+z=a+b\) ? (mehrere Auswahlmöglichkeiten) - \(a=x+y\) , \(b=z\) - \(a=x+z\) , \(b=y\) - \(a=(011)\) , \(b=(011)\) - \(a_i=x_i\oplus y_i\oplus z_i\) (für \(i=0,1,2\) ) und \(b_0=0\) , \(b_i=x_{i-1}\land y_{i-1}\land z_{i-1}\) (für \(i=1,2\) ) ## Multiplikation: Addition vieler Zahlen **Gibt es einen noch besseren Ansatz?** **(Verrückte?) Idee:** Vielleicht ist es einfacher, **drei** Zahlen zu ersetzen durch **zwei** Zahlen gleicher Summe? **Beobachtung** - **Es gilt immer noch:** Gleiche Summe \(\rightarrow\) Korrektheit - **Weniger Fortschritt:** \(3\rightarrow 2\) statt \(2\rightarrow 1\) ## Multiplikation: Addition vieler Zahlen **Wallace-Tree** - Carry-Save-Adder (CSA) - \(m_i\) sind \(n\) -Bit-Zahlen - Sinnvoll, wenn CSA flacher ist als CLA-Addierer ## Multiplikation: Carry-Save-Adder **Gesucht** - Addierer mit drei Eingängen und zwei Ausgängen, für den gilt: \[x+y+z=a+b\] **Gefunden** - **Volladdierer**, der für \(x,y,z\in\{0,1\}\) folgendes Resultat liefert: \[x+y+z=2\cdot c+s\] - \(s\) ist das Summenbit - \(2\cdot c\) ist das Übertragsbit, bezogen auf seine Stelle eine Position weiter links ## Multiplikation: Carry-Save-Adder - Parallelschaltung von \(n\) Volladdierern - Liefern jeweils die **Summenbits** - und die **Übertragsbits** **Diese Volladdierer sind nicht verkettet** - Jeder liefert ein \(s\) -Bit und ein \(c\) -Bit - Aus diesen Bits werden das Summen-Wort gebildet, das an der höchstwertigen Stelle (Anfang) mit 0 erweitert wird, - und das Carry-Wort, das an der niederwertigsten Stelle (Ende) mit 0 erweitert wird - **Summe** aus Summen-Wort und Carry-Wort **bildet das Resultat** ## Beispiel: Carry-Save-Adder **Wir addieren** - \(x=001001\) - \(y=001111\) - \(z=001100\) \[\begin{array}{lccccccccl} \text{Summen-Wort} & = & (0) & 0 & 0 & 1 & 0 & 1 & 0 & = 0001010\\ \text{Carry-Wort} & = & 0 & 0 & 1 & 1 & 0 & 1 & (0) & = 0011010 \end{array}\] ## Beispiel: Carry-Save-Adder \[\begin{array}{l|cccccccc} \text{Summand } x & & & x_5 & x_4 & x_3 & x_2 & x_1 & x_0\\ \text{Summand } y & + & & y_5 & y_4 & y_3 & y_2 & y_1 & y_0\\ \text{Summand } z & + & & z_5 & z_4 & z_3 & z_2 & z_1 & z_0\\ \color{gray}\text{Resultat} & & & \color{gray}2c_5+s_5 & \color{gray}2c_4+s_4 & \color{gray}2c_3+s_3 & \color{gray}2c_2+s_2 & \color{gray}2c_1+s_1 & \color{gray}2c_0+s_0\\ \hline \text{Carry-Wort} & & c_5 & c_4 & c_3 & c_2 & c_1 & c_0 & (0)\\ \text{Summen-Wort} & + & (0) & s_5 & s_4 & s_3 & s_2 & s_1 & s_0 \end{array}\] \[\begin{array}{l|cccccccc} \text{Summand } x & & & 0 & 0 & 1 & 0 & 0 & 1\\ \text{Summand } y & + & & 0 & 0 & 1 & 1 & 1 & 1\\ \text{Summand } z & + & & 0 & 0 & 1 & 1 & 0 & 0\\ \hline \text{Carry-Wort} & & 0 & 0 & 1 & 1 & 0 & 1 & (0)\\ \text{Summen-Wort} & + & (0) & 0 & 0 & 1 & 0 & 1 & 0\\ \hline \text{Summe} & & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{array}\] ## Quiz: Carry-Save-Adder Wie viele Schritte braucht es, \(c\) und \(s\) zu berechnen? - 1 - 2 - 3 - 4 - 5 ## Multiplikation: Carry-Save-Adder **Berechnung von drei \(n\) -Bit-Zahlen** - Zum Einsatz kommen \(n\) Volladdierer - Größe: \(5n\) - Tiefe: 3 **Beobachtung** - Der (große) Carry-Look-Ahead-Addierer wird in einem Wallace-Tree erst als letzte Operation benötigt - Der Wallace-Tree hat somit für die Addition von \(n\) Zahlen folgende Eigenschaften: Größe: \(\approx\frac{n^3}{3}\) (proportional, bedingt durch den CLA) - Tiefe: \(\approx 3\log_{3/2}(n)+2\log_2(n)\approx 7{,}13\log_2(n)\) **Fazit:** Multiplikation ist nicht **wesentlich teurer oder langsamer** als die Addition ## Multiplikation **Serielle Addierer** - Tiefe \(=(n-1)\cdot\) Tiefe(Addierer) - Tiefe \(=(n-1)\cdot 2\log_2(n)\) **Paarweise Addierer** - Tiefe \(=\log_2(n)\cdot\) Tiefe(Addierer) - Tiefe \(=2(\log_2(n))^2\) **Wallace-Tree mit Carry-Save-Addierern** - Tiefe \(\approx 3\log_{3/2}(n)+2\log_2(n)\approx 7{,}13\log_2(n)\) ## Multiplikation Darstellung der Tiefe ## Quiz: Wallace-Tree Welche Aussage ist korrekt, wenn \(n\) \(n\) -Bit-Vektoren mit einem Wallace-Tree addiert werden? - Der Wallace-Tree benötigt nur einen Carry-Look-Ahead-Addierer (CLA) mit der Tiefe \(2\log_2(n)\) - Jeder Carry-Save-Adder (CSA) in dem Wallace-Tree ist ein \(n\) -Bit-Addierer, der die Summe von 3 \(n\) -Bit-Vektoren berechnet - Wallace-Trees zeigen, dass die Multiplikation deutlich langsamer als die Addition ist - Paarweise Addition ist schneller als ein Wallace-Tree, wenn \(n\) groß genug gewählt wird