imported>Phzh: Form, typo

2021-03-27T17:54:26Z

Form, typo

Neue Seite

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.

== Idee ==

Wird eine Zahl <math>x</math> mit 2 multipliziert und anschließend von der entstandenen Zahl subtrahiert, ergibt sich wieder <math>x</math>:
*<math>2x - x = x</math>
Analog:
*<math>-2x + x = -x</math>

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:

{| class="wikitable"
| Booth-Code:
| …
| bgcolor="#FFcccc" | +1
| bgcolor="#FFcccc" | −1
| …
|-
| nach Vereinfachung:
| …
| bgcolor="#FFcccc" | 0
| bgcolor="#FFcccc" | +1
| …
|}

{| class="wikitable"
| Booth-Code:
| …
| bgcolor="#ccccff" | −1
| bgcolor="#ccccff" | +1
| …
|-
| nach Vereinfachung:
| …
| bgcolor="#ccccff" | 0
| bgcolor="#ccccff" | −1
| …
|}

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

=== Beispiel ===

Es soll <math>3 * 89</math> berechnet werden.
*<math>3_{10} = 00000011_2</math>
*<math>89_{10} = 01011001_2</math>

Auf den Faktor 8910 werden nacheinander die entsprechenden Verfahren angewandt:

{| class="wikitable"
| 8910=
| 0
| 1
| 0
| 1
| 1
| 0
| 0
| 1
|-
| nach Anwendung des Booth-Algorithmus:
| +1
| bgcolor="#ccccff" | −1
| bgcolor="#ccccff" | +1
| 0
| −1
| 0
| bgcolor="#FFcccc" | +1
| bgcolor="#FFcccc" | −1
|-

| nach Anwendung des Bit-Pair-Verfahrens:
| +1
| bgcolor="#ccccff" | 0
| bgcolor="#ccccff" | −1
| 0
| −1
| 0
| bgcolor="#FFcccc" | 0
| bgcolor="#FFcccc" | +1
|}

Die Berechnung erfolgt analog zum Booth-Algorithmus:

{| class="wikitable"
!
!
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#666666"|0
! style="background:#666666"|0
! style="background:#666666"|0
! style="background:#666666"|0
! style="background:#666666"|0
! style="background:#666666"|0
! style="background:#666666"|1
! style="background:#666666"|1
| 310
|-
!x
!
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#EEEEEE"|
! style="background:#666666"| +1
! style="background:#666666"|0
! style="background:#666666"| −1
! style="background:#666666"| 0
! style="background:#666666"| −1
! style="background:#666666"|0
! style="background:#666666"|0
! style="background:#666666"| +1
|Kodierung des 2. Faktors
|-
| +
|
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|0
|0
|0
|0
|0
|0
|1
|1
| 310
|-
| +
|
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|0
|0
|0
|0
|0
|0
|0
|0
|bgcolor="#EEEEEE"|
|keine Addition
|-
| +
|
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|0
|0
|0
|0
|0
|0
|0
|0
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|keine Addition
|-
| +
|
|bgcolor="#EEEEEE" |1
|bgcolor="#EEEEEE" |1
|bgcolor="#EEEEEE" |1
|bgcolor="#EEEEEE" |1
|1
|1
|1
|1
|1
|1
|0
|1
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|2er Komplement von 310
|-
| +
|
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|bgcolor="#EEEEEE" |0
|0
|0
|0
|0
|0
|0
|0
|0
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|keine Addition
|-
| +
|
|bgcolor="#EEEEEE" |1
|bgcolor="#EEEEEE" |1
|1
|1
|1
|1
|1
|1
|0
|1
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|2er Komplement von 310
|-
| +
|
|bgcolor="#EEEEEE" |0
|0
|0
|0
|0
|0
|0
|0
|0
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|keine Addition
|-
| +
|
|0
|0
|0
|0
|0
|0
|1
|1
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
| 310
|-
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|bgcolor="#666666"|0
|bgcolor="#666666"|0
|bgcolor="#666666"|0
|bgcolor="#666666"|0
|bgcolor="#666666"|0
|bgcolor="#666666"|0
|bgcolor="#666666"|1
|bgcolor="#666666"|0
|bgcolor="#666666"|0
|bgcolor="#666666"|0
|bgcolor="#666666"|0
|bgcolor="#666666"|1
|bgcolor="#666666"|0
|bgcolor="#666666"|1
|bgcolor="#666666"|1
|Ergebnis ohne Überlauf
|-
|bgcolor="#EEEEEE"|
|bgcolor="#EEEEEE"|
|2
|2
|2
|2
|2
|2
|2
|1
|1
|0
|0
|0
|0
|0
|0
|Übertrag
|}

*<math>0100001011_2 = 267_{10} = 3_{10} * 89_{10}</math>
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.

== Literatur ==
* [http://www.dauniv.ac.in/downloads/CArch_PPTs/CompArchCh03L05BoothAlgor.pdf Arithmetic Multiplication Circuits] (engl.; PDF-Datei; 134 kB)
* {{Literatur |Autor=T. N. Rajashekhara, O. Kal |Titel=Fast multiplier design using redundant signed-digit numbers |Sammelwerk=International Journal of Electronics |Band=69 |Nummer=3 |Datum=1990-09 |ISSN=0368-1947 |Seiten=359–368 |DOI=10.1080/00207219008920321}}

[[Kategorie:Algorithmus]]
[[Kategorie:Rechnerarchitektur]]

Bit-Pair-Verfahren - Versionsgeschichte

imported>Phzh: Form, typo