Bit-Pair-Verfahren

Das Bit-Pair-Verfahren (eng. Bit-Pair-Recoding) ist ein Algorithmus zur Beschleunigung computergestützter Multiplikation zweier Zahlen in Zweierkomplement-Darstellung. Er stellt eine Erweiterung des Booth-Algorithmus dar.

Inhaltsverzeichnis

Idee

Wird eine Zahl x mit 2 multipliziert und anschließend von der entstandenen Zahl subtrahiert, ergibt sich wieder x:

  • 2xx = x

Analog:

  • − 2x + x = − x

Der Booth-Algorithmus allerdings generiert unter Umständen Code, der solche (unnötigen) Berechnungen durchführen würde. Das lässt sich durch das Bit-Pair-Verfahren vereinfachen.

Verfahren

Benachbarte „*(+1)“ und „*(-1)“ im Booth-Code werden wie folgt zusammengefasst:

Booth-Code: +1 -1
nach Vereinfachung: 0 +1
Booth-Code: -1 +1
nach Vereinfachung: 0 -1

Es entfällt eine Addition. Die Berechnung wird effizienter.

Beispiel

Es soll 3 * 89 berechnet werden.

  • 310 = 000000112
  • 8910 = 010110012

Auf den Faktor 8910 werden nacheinander die entsprechenden Verfahren angewandt:

8910= 0 1 0 1 1 0 0 1
nach Anwendung des Booth-Algorithmus: +1 -1 +1 0 -1 0 +1 -1
nach Anwendung des Bit-Pair-Verfahrens: +1 0 -1 0 -1 0 0 +1

Die Berechnung erfolgt analog zum Booth-Algorithmus:

0 0 0 0 0 0 1 1 310
x +1 0 -1 0 -1 0 0 +1 Kodierung des 2. Faktors
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 310
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 keine Addition
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 keine Addition
+ 1 1 1 1 1 1 1 1 1 1 0 1 2er Komplement von 310
+ 0 0 0 0 0 0 0 0 0 0 0 keine Addition
+ 1 1 1 1 1 1 1 1 0 1 2er Komplement von 310
+ 0 0 0 0 0 0 0 0 0 keine Addition
+ 0 0 0 0 0 0 1 1 310
0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 Ergebnis ohne Überlauf
2 2 2 2 2 2 2 1 1 0 0 0 0 0 0 Übertrag
  • 01000010112 = 26710 = 310 * 8910

Das Ergebnis ist korrekt, ausgeführt allerdings mit 4 Additionsoperationen, statt mit 6. Es sei angemerkt, dass hier nur zu beispielzwecken 89 statt 3 mit den Algorithmen vereinfacht wurde. Praktisch wäre es natürlich in diesem Fall am effizientesten 89 * 3 „direkt“ zu berechnen. Das würde nur 2 Additionen erfordern.

Quellen


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Booth-Verfahren — Der Booth Algorithmus ist ein Algorithmus für die Multiplikation zweier Zahlen in Zweierkomplement Darstellung. Er wurde um 1951 von Andrew D. Booth entwickelt. Inhaltsverzeichnis 1 Verfahren 2 Idee 2.1 Beispiel 3 Beispiele …   Deutsch Wikipedia

  • Zweierkomplement — Das Zweierkomplement (auch 2 Komplement – verallgemeinert b Komplement (b Basis) –, Zweikomplement, B(inär) Komplement, Basiskomplement, two s complement) ist eine Möglichkeit, negative Zahlen im Dualsystem darzustellen. Dabei werden keine… …   Deutsch Wikipedia

  • Booth-Algorithmus — Der Booth Algorithmus ist ein Algorithmus für die Multiplikation zweier Zahlen in Zweierkomplement Darstellung. Er wurde 1951 von Andrew Donald Booth bei Arbeiten zur Kristallographie am Birkbeck College entwickelt. Inhaltsverzeichnis 1 Verfahren …   Deutsch Wikipedia

  • Ethernet — im TCP/IP‑Protokollstapel: Anwendung HTTP IMAP SMTP DNS … Transport TCP UDP Internet …   Deutsch Wikipedia

  • 1000BASE-T — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Metro Ethernet. Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst …   Deutsch Wikipedia

  • 1000Base-CX — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Metro Ethernet. Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst …   Deutsch Wikipedia

  • 1000Base-LX — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Metro Ethernet. Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst …   Deutsch Wikipedia

  • 1000Base-SX — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Metro Ethernet. Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst …   Deutsch Wikipedia

  • 1000Base-T — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Metro Ethernet. Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst …   Deutsch Wikipedia

  • 1000BaseLX — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Metro Ethernet. Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”