Seriell Multiplizieren mit Vorzeichen (auf PSoC)

[Ralf (Gast)]

Hallo,

ich möchte auf einem PSoC 5LP einen Multiplizierer realisieren. Da dort 
die Ressourcen verglichen mit FPGAs sehr beschränkt sind, möchte ich 
einen seriellen Multiplizierer verwenden.

Mir geht es hier erstmal nicht um die konkrete Lösung in Verilog (PSoC 
"spricht" kein VHDL), sondern um's Verständnis, denn daran hapert es 
gerade. Ich versuche, den Multiplizierer aus Wikipedia zu verstehen:
https://en.wikipedia.org/wiki/Binary_multiplier#More_advanced_approach:_signed_integers

Momentan versuche ich das per Papier & Block durchzurechnen, aber 
offenbar setze ich die einzelnen Summanden schon falsch zusammen:

         0111 A (entspricht dezimal der Zahl +7)
       · 0011 B (entspricht dezimal der Zahl +3)
erwartet: 10101b = 21d

          B
    11110 1 (entspricht A*1, MSB+1 = 1, Vorzeichen invertiert, LSB invertiert)
+   1110  1 (entspricht A*2, Vorzeichen invertiert, LSB invertiert)
+  1001   0 (entspricht 0*4, Vorzeichen invertiert, LSB invertiert)
+11000    0 (entspricht 0*8, MSB+1 = 1, 2-er Komplement, LSB invertiert)

Im Endeffekt hapert es wohl an meiner Interpretation des englischen 
Textes, denn schon der erste Summand bringt das ganze zum Scheitern, 
weil das LSB = 0 ist, im Ergebnis jedoch eine 1 stehen muss.

So, wie ich den Text verstehe, muss das LSB jeweils invertiert werden. 
Das im Text erwähnte, implizite subtrahieren von 1 unterhalb des 
jeweiligen MSBs ist aus meiner Sicht bereits durch das invertieren des 
Vorzeichenbits drin, ist das korrekt?
Und der letzte Summand ist das 2er-Komplement, da eigentlich abgezogen 
werden muss. Auch hier das LSB wieder invertiert.
Rechne ich nun alle Summanden zusammen, komme ich auf 30d und nicht die 
erwarteten 21d. Wo liegt mein Fehler?

Vielen Dank.

Ralf

[Binary multiplier (Gast)]

Ein paar Beispiele vielleicht hilft das ja.

für 7 * 3: 

    0111 -------+
x   0011 -+     |
========= v     v
     111  1     0x shift left
+   1110  1     1x shift left
========
   10101  = 21

für 3 * 7:

    0111 -------+
x   0011 -+     |
========= v     v
      11  1     0x shift left
+    110  1     1x shift left
+   1100  1     2x shift left
========
   10101  = 21

für 5 * 4: 

    0101 -------+
x   0100 -+     |
========= v     v
       0  0     0x shift left
+      0  0     1x shift left
+  10100  1     2x shift left
========
   10100  = 20

für 4 * 5:

    0100 -------+
x   0101 -+     |
========= v     v
     100  1     0x shift left
+      0  0     1x shift left
+  10000  1     2x shift left
========
   10100  = 20

[Ralf (Gast)]

Hallo,

danke für die Beispiele. Das sind vorzeichenlose Rechnungen, wie 
schaut's denn mit vorzeichenbehaftet aus? (Sorry, es wird aus meinem 
Text wohl nicht ganz klar, dass es um vorzeichenbehaftete Berechnungen 
geht).

Ralf

[Binary multiplier (Gast)]

Funktioniert auch mit der Zweierkomplementdarstellung.

für -7 * 3: 

11111001 -------+
x     11 -+     |
========= v     v
11111001  1     0x shift left
11110010  1     1x shift left
========
11101011  = -21

für -3 * 7:

11111101 -------+
x    111 -+     |
========= v     v
11111101  1     0x shift left
11111010  1     1x shift left
11110100  1     2x shift left
========
11101011  = -21

für -5 * 4:
 
11111011 -------+
x    100 -+     |
========= v     v
       0  0     0x shift left
+      0  0     1x shift left
11101100  1     2x shift left
========
11101100  = -20

für -4 * 5:

11111100 -------+
x    101 -+     |
========= v     v
11111100  1     0x shift left
+      0  0     1x shift left
11110000  1     2x shift left

========
11101100  = -20

[Ralf (Gast)]

Okay, dann muss ich noch präzisieren: der von mir verlinkte Wiki-Artikel 
verwendet eine Implementierung, welche auf das Auffüllen des 
Vorzeichenbits (sign extension) bis zur Breite des Ergebnisses 
verzichtet. Das würde es mir ermöglichen, einen Teil der Berechnung 
direkt im Ergebnisregister auszuführen. Wie gesagt, die Ressourcen sind 
knapp.
Deswegen hatte ich auch meine Interpretation(tm) des Rechenweges 
basierend auf diesem Artikel widergegeben. Sorry für das 
Missverständnis.

Ralf

[foobar (Gast)]

Am LSB wird doch nichts geändert. Es wird nur das MSB invertiert und im 
letzten Schritt zusätzlich alle Bits (bzw alles außer das MSB).

Als Summanden treten folglich auf:

    1001 ....  (die Konstanten, z.B. Vorbelegung Summenreg)
+   .... 1111  A<<0, MSB invertiert
+   ...1 111.  A<<1, MSB invertiert
+   ..10 00..  0<<2, MSB invertiert
+   .011 1...  0<<3, MSB invertiert, alles invertiert
-------------
= 1 0001 0101  21 mod 256

Ich frag mich allerdings, was das bringen soll - Vorzeichenerweiterung 
ist billig und passiert eh nur einmal am Anfang.

[Ralf (Gast)]

Hi foobar,

danke für deine Antwort.

> Ich frag mich allerdings, was das bringen soll - Vorzeichenerweiterung
> ist billig und passiert eh nur einmal am Anfang.
Bei den Implementierungen, die ich bisher gesehen habe, geschieht die 
Vorzeichenerweiterung bei jedem Durchgang.
Hier hatte ich eine Implementierung gefunden, welche das verkürzt, aber 
mit Papier und Block kam ich da auch auf die falschen Ergebnisse. 
Deswegen versuche ich herauszufinden, wo mein Denkfehler liegt:
https://www.dsprelated.com/showarticle/555.php

> 1001 ....  (die Konstanten, z.B. Vorbelegung Summenreg)
Wie bist du auf die 1001 gekommen? Mit -7d vorbelegt?

Ralf

[foobar (Gast)]

>> 1001 ....  (die Konstanten, z.B. Vorbelegung Summenreg)
> Wie bist du auf die 1001 gekommen?

Das sind einfach die beiden Einser in der Tabelle des 
Wikipedia-Artikels. Ich habe nicht versucht, die Bittricksereien des 
Algorithmus' nachzuvollziehen, hab nur das Ergebnis interpretiert - 
scheint zu stimmen :-)

[Ralf (Gast)]

Okay, dann versteh ich's grad echt nicht XD Vielleicht schon zu spät... 
Die 1 gehört ja vorangestellt, also müsste es ein 5-Bit Wert sein.

Ralf

[foobar (Gast)]

Die beiden zusätzlichen Bits aus der ersten und letzten Zeile hab ich 
einfach rausgezogen, s. Anhang. Machte die Sache mMn etwas 
übersichtlicher.

[Peter D. (peda)]

Eine Multiplikation ist im Zweierkomplement richtig, wenn das Ergebnis 
die gleiche Breite wie die Operanden hat. Eine Vorzeichenberechnung ist 
daher nicht nötig.

[Ralf (Gast)]

Hallo foobar & Peter,

danke für die Antworten, ich werd heut abend gleich mal wieder Papier 
und Stift bemühen =)

Ralf

[soso (Gast)]

Hallo,

ich verstehe Deine Absichten nicht ganz. Ressourcen - knapp?Da gibt es 
wesentlich kleinere Prozessoren.

Möchtest Du den DFB verwenden und selber programmieren?

[soso (Gast)]

Hier noch eine Komponente von Cypress, könnte evtl. interessant sein.
Nuttz ebenfalls den DFB.

https://community.cypress.com/thread/16591?start=0&tstart=0

[soso (Gast)]

Wäre schön zu wissen, was Du beabsichtigst. Vll. kann Dir der ein oder 
andere nicht nur bei der ursprünglichen Frage helfen, sondern evtl. 
Impulse geben, wie Deine Problemstellung auch einfacher gelöst werden 
kann.

[soso (Gast)]

Willst deine eigene Komponente entwickeln?

[Ralf (Gast)]

Hallo soso,

vielen Dank für den Link zu der Komponente, das schau ich mir an.

zur Frage was ich machen möchte: ganz lapidar gesagt möchte ich ein per 
DAC ausgegebenes Signal in der Amplitude variieren. Mit der 
WaveDAC-Komponente kann man zwar Sinus & Co. sehr einfach ausgeben und 
auch in der Frequenz variieren, aber die Amplitude ist leider fix. Im 
Prinzip geht's um einen Signalgenerator.

Ralf