Quelltext der Seite 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 [[Schieberegister|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 [[Schieberegister]]n, welche aus getakteten [[Flipflop]]s (z.&nbsp;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 ==
[[Datei:Crossbar barrel shifter.svg|mini|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 [[Schaltnetz]]es bestimmt wird. Je nach [[Schaltwerk (Technische Informatik)|(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 [[Mikroprozessor]]en. Ebenso kann diese Logikfunktion in einem [[Programmierbare logische Schaltung|programmierbaren Logikbaustein]] (PLD), einem [[Field Programmable Gate Array|FPGA]] oder einem [[Anwendungsspezifische integrierte Schaltung|ASIC]] als Teil einer Gesamtschaltung realisiert werden.

== Realisierung ==
[[Datei:Barrel3.png|mini|440px|Barrel-Shifter zum Rotieren (ohne [[Carry-Flag]]) von 16-bit-Worten. Eingetragen ist ''Rotiere nach Links um 13'' bzw. ''Rotiere nach rechts um 3''.<br/ >''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.&nbsp;B. N = √N·√N oder N=2<sup>n</sup> 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<sup>a</sup>·n<sup>b</sup> 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<sub>2</sub>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:<br />
Eine Verschiebung um 13 aktiviert die Spalte n<sub>13</sub>, 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:
:<math>S(A,x+y) = S(S(A,x),y)</math>
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:<br />
Eine Verschiebung um 13 aktiviert die Spalten s<sub>3</sub>, s<sub>2</sub>, ¬s<sub>1</sub> und s<sub>0</sub>,  die in vier Schritten das Datenwort um 1·2<sup>3</sup>&nbsp;+&nbsp;1·2<sup>2</sup>&nbsp;+&nbsp;0·2<sup>1</sup>&nbsp;+&nbsp;1·2<sup>0</sup>&nbsp;=&nbsp;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:<br />
Eine Verschiebung um 13 aktiviert die Spalten m<sub>3</sub> und n<sub>1</sub>, die in zwei Schritten das Datenwort um 3·4<sup>1</sup>&nbsp;+&nbsp;1·4<sup>0</sup>&nbsp;=&nbsp;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.<ref>[https://www.xilinx.com/support/documentation/application_notes/xapp195.pdf Implementing Barrel Shifters Using Multipliers] (PDF; 50&nbsp;kB), Xilinx Application Note, Paul Gigliotti, 2004 (engl.)</ref>

Daneben gibt es auch Barrel-Shifter als einzelne [[integrierte Schaltung]]en, wie beispielsweise der Baustein ''SN74AS897'', welcher einen 8 Bit breiten Barrel-Shifter bietet.

== Einzelnachweise ==
<references/>

[[Kategorie:Digitaltechnik]]