Barrel-Shifter

Ein Barrel-Shifter ist eine Schaltung der Digitaltechnik, die Bitvektoren (Datenworte) schnell und in konstanter Zeit um eine beliebige Anzahl von Bits verschiebt oder rotiert. Diese Eigenschaft unterscheidet sie grundlegend von klassischen Schieberegistern, deren Ausführungszeit von der Verschiebedistanz abhängt und insbesondere für große Verschiebedistanzen beträchtliche Zeiten annehmen kann.

Im Gegensatz zu Schieberegistern, welche aus getakteten Flipflops (z. B. D-Flipflops) bestehen, besitzt ein Barrel-Shifter primär keine Speicherelemente. Bei Bedarf können diese einem Barrel-Shifter vor- und/oder nachgeschaltet werden. Sind die Bits innerhalb des Barrel-Shifters zyklisch miteinander verbunden, so spricht man manchmal von einem Barrel-Rotator.

Allgemeines

4-Bit breiter Barrel-Shifter realisiert als Matrix (x als Eingang, y als Ausgang)

Ein Barrel-Shifter führt eine Verschiebung um mehrere Bits asynchron durch, wobei die benötigte Zeit durch die Gatterlaufzeit des Schaltnetzes bestimmt wird. Je nach (synchroner) Umgebung, in die der Barrel-Shifter eingebettet ist, wird für die Schiebeoperation mitunter kein zusätzlicher Taktzyklus benötigt.

Das ist der grundlegende Unterschied gegenüber einem gewöhnlichen Schieberegister, welches eine Verschiebung um n Bit sequentiell (und meist getaktet) durch n Verschiebungen um 1 Bit durchführt.

Ein 4-Bit breiter Barrel-Rotator als einfachste Form besitzt vier Dateneingänge, zwei Steuereingänge und vier Datenausgänge. Wenn bei den Eingängen die Folge „ABCD“ anliegt, so kann als Funktion der möglichen vier Zustände an den beiden Steuereingängen folgende Ausgangsfolgen erzeugt werden: ABCD, DABC, CDAB oder BCDA. In nebenstehender Grafik sind diese vier möglichen Schaltzustände durch vier Farben in der Steuerlogik eingezeichnet: Durch den Decoder wird immer nur eine der vier eingefärbten Leitungen aktiviert und damit eines der vier Ausgangsmuster erzeugt.

Der Barrel-Shifter ist häufig Bestandteil von Mikroprozessoren. Ebenso kann diese Logikfunktion in einem programmierbaren Logikbaustein (PLD), einem FPGA oder einem ASIC als Teil einer Gesamtschaltung realisiert werden.

Realisierung

Barrel-Shifter zum Rotieren (ohne Carry-Flag) von 16-bit-Worten. Eingetragen ist Rotiere nach Links um 13 bzw. Rotiere nach rechts um 3.
Oben: mit einer 16×16-Matrix; Mitte: mit zwei 16×4-Matrizen; Unten: mit vier 16×2-Matrizen

Barrel-Shifter können unterschiedlich implementiert werden. Die Verschiebung eines N-bit-Wortes um eine beliebige Verschiebedistanz zwischen 0 und N−1 kann man mit einem 1-aus-N-Decoder und N× N-aus-1-Multiplexern mit einem Multiplexerdurchlauf implementieren. Man kann N aber auch in Faktoren (vorzugsweise Zweierpotenzen und identisch) zerlegen, z. B. N = √N·√N oder N=2^n und dann

• mit zwei 1-aus-√N-Decodern und N·2× √N-aus-1-Multiplexern in zwei Schritten,
• mit n 1-aus-2-Decodern und N·n 2-aus-1-Multiplexern in n Schritten

oder allgemeiner mit N = m^a·n^b und

• mit a 1-aus-m-Decodern, b 1-aus-n-Decodern, N·a m-aus-1-Multiplexern und N·b n-aus-1-Multiplexern

durchführen.

Der Aufwand für diese verschiedenen Implementierungen ist unterschiedlich, weiterhin gibt es Unterschiede in der Laufzeit, wenn zur Implementierung NANDs mit 4 oder 8 Eingängen zur Verfügung stehen. Aber alle Schaltungen weisen konstante und kurze Durchlaufzeiten im Bereich weniger Gatterlaufzeiten meist unterhalb von einem Taktzyklus auf.

                 oben   mitte   unten
NAND 1 Eingang      4       4       4
NAND 2 Eingänge     -       -     192
NAND 3 Eingänge   320     128       -
NAND 4 Eingänge    80      32       -
FETs             2568    1032     776
Laufzeit Input      4       4       8 Gatterlaufzeiten
Laufzeit Input     80ps    80ps   160ps  FO4=20ps
Laufzeit Shift      5       5       9 Gatterlaufzeiten
Laufzeit Shift    120ps   120ps   200ps  FO4=20ps

Realisierung mit N× N-aus-1-Multiplexern

Die N verschiedenen Verschiebeoperationen des N Bit langen Eingangs-Bitvektors werden als eine N×N-Matrix abgebildet. Die Verschiebedistanz, die als ein log₂N Bit-Wert vorliegt, wird mit einem 1-aus-N-Decoder dekodiert und selektiert einen bestimmten Eingang aller N N-aus-1-Multiplexer.

Siehe Graphik rechts, oberes Beispiel:
Eine Verschiebung um 13 aktiviert die Spalte n₁₃, die in einem Schritt das Datenwort um 13 nach links rotiert.

Teilung in N·n× 2-aus-1-Multiplexer

Hier nutzt man die Eigenschaft aus, die schon bei Schieberegistern ausgenutzt werden: Verschiebeoperationen sind separierbar. Es gilt:

${\displaystyle S(A,x+y)=S(S(A,x),y)}$

Daher kann man die große N×N-Matrix in n 2×N-Teilmatrizen zerlegen. Auf den ersten Blick sieht diese Implementierung langsamer als die erste aus, dies gilt allerdings nur, wenn man die N-aus-1-Multiplexer aus der ersten Implementierung nicht ohnehin als kaskadierte 2-aus-1-Multiplexer implementieren muss.

Siehe Graphik rechts, unteres Beispiel:
Eine Verschiebung um 13 aktiviert die Spalten s₃, s₂, ¬s₁ und s₀, die in vier Schritten das Datenwort um 1·2^3 + 1·2^2 + 0·2^1 + 1·2^0 = 13 nach links rotieren.

Teilung in N·n/2× 4-aus-1-Multiplexer

Wenn sich effizient 4-aus-1-Multiplexer aufbauen lassen, ist diese Implementierung effizienter als die zweite.

Siehe Graphik rechts, mittleres Beispiel:
Eine Verschiebung um 13 aktiviert die Spalten m₃ und n₁, die in zwei Schritten das Datenwort um 3·4^1 + 1·4^0 = 13 nach links rotieren.

Realisierung mit Hardware-Multiplizierern

Eine weitere Realisierungsmöglichkeit für das Verschieben nach links stellt das Multiplizieren mit einer Zweierpotenz dar. Insbesondere, wenn in einem FPGA vorhandene dedizierte Hardware-Multiplizierer sonst brachliegen würden, lassen sich damit effizient Barrel-Shifter realisieren, ohne universell verwendbare FPGA-Ressourcen zu benötigen.[1]

Daneben gibt es auch Barrel-Shifter als einzelne integrierte Schaltungen, wie beispielsweise der Baustein SN74AS897, welcher einen 8 Bit breiten Barrel-Shifter bietet.

Einzelnachweise

1. Implementing Barrel Shifters Using Multipliers (PDF; 50 kB), Xilinx Application Note, Paul Gigliotti, 2004 (engl.)