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
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
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=2n 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 = ma·nb 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 log2N 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 n13, 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:
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 s3, s2, ¬s1 und s0, die in vier Schritten das Datenwort um 1·23 + 1·22 + 0·21 + 1·20 = 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 m3 und n1, die in zwei Schritten das Datenwort um 3·41 + 1·40 = 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
- Implementing Barrel Shifters Using Multipliers (PDF; 50 kB), Xilinx Application Note, Paul Gigliotti, 2004 (engl.)