Arithmetik

Normaler­weise arbeiten Arithmetik­schaltungen bitparallel, wie etwa der Carry-Lookahead-Addierer oder der Carry-Save-Addierer. In manchen Situationen jedoch, etwa im Bereich hoch­integrierter Parallel­prozessoren, wird bitseriell gearbeitet. Dies liegt daran, dass die Prozessoren nur über eine einzige, bitserielle Leitung miteinander verbunden sind. Wenn die Kommunikation bitseriell ist, kann auch die Verarbeitung bitseriell durchgeführt werden. Bitserielle Arithmetik­schaltungen sind sehr viel kleiner als bitparallele Schaltungen.

Bitserielle Addition

Als bitserieller Addierer eignet sich der Ripple-Carry-Addierer sehr gut. Bild 1 zeigt eine solche Schaltung mit einem Volladdierer (engl.: full adder - FA) im Mittelpunkt. Die Operanden a = a₀, ..., a_n-1 und b = b₀, ..., b_n-1 werden bitseriell eingegeben, die Summenbits werden bitseriell ausgegeben. Das jeweils entstehende Übertragsbit c_i wird in einem Verzögerungs­element zwischen­gespeichert und im nächsten Takt wieder mit eingegeben.

Bitserielle Multiplikation

Im Folgenden werden zwei bitserielle Multi­plizierer vorgestellt und formal verifiziert. Der erste Multi­plizierer wurde im Prozessor des Parallel­rechners Systola-1024 verwendet. Der zweite Multi­plizierer geht auf Chen und Willoner zurück.

Grundlage für beide Multi­plizierer ist das Standard-Multi­plikationsschema für zwei n-Bit-Operanden a und b. Je nach dem, in welcher Reihenfolge die einzelnen Bit-Produkte a_ib_j zusammen­gefasst werden, ergeben sich unter­schiedliche Multi­plikationsalgorithmen. Die Berechnungen des Multi­plikationsalgorithmus werden vom Indexraum {(i,j)} in den Raum {(t,p)} aus Zeit und Prozessor­elementen trans­formiert. Durch unter­schiedliche Trans­formationen sind wiederum unter­schiedliche Multi­pliziererschaltungen möglich.