mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Seriell Multiplizieren mit Vorzeichen (auf PSoC)


Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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#Mo...

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

Autor: Binary multiplier (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Binary multiplier (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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


Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: foobar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: foobar (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
>> 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 :-)

Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: foobar (Gast)
Datum:
Angehängte Dateien:

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

Autor: Peter D. (peda)
Datum:

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

Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo foobar & Peter,

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

Ralf

Autor: soso (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

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

Möchtest Du den DFB verwenden und selber programmieren?

Autor: soso (Gast)
Datum:

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

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

Autor: soso (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: soso (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Willst deine eigene Komponente entwickeln?

Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.