imported>APPERbot: Bot: Dateieinbindungen: 440px und hochkant nicht gemeinsam (hochkant entfernt)

2024-06-01T21:28:55Z

Bot: Dateieinbindungen: 440px und hochkant nicht gemeinsam (hochkant entfernt)

Neue Seite

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. 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''. ''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:
:<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: 
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.<ref>[https://www.xilinx.com/support/documentation/application_notes/xapp195.pdf Implementing Barrel Shifters Using Multipliers] (PDF; 50 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]]

Barrel-Shifter - Versionsgeschichte

imported>APPERbot: Bot: Dateieinbindungen: 440px und hochkant nicht gemeinsam (hochkant entfernt)