If b had been a signed integer instead of an unsigned integer, then the partial products would need to have been sign-extended up to the width of the product before summing. If a had been a signed integer, then partial product p7 would need to be subtracted from the final sum, rather than added to it.
Das interpretiere ich so, dass einer der beiden Operanden bei gleicher
Bitbreite auch vorzeichenlos sein kann, in dem Fall verzichtet man auf
die o.g. Vorzeichenerweiterung bzw. addiert p7 weiterhin anstatt zu
subtrahieren. Ist das korrekt?
Bei der generellen Berechnung strauchle ich bei zwei Sachen:
1) der vorzeichenlose Multiplizierer setzt den Multiplikant auf Null,
wenn das entsprechende Bit im Multiplikator ebenfalls Null ist. Wenn ich
den Wiki-Artikel richtig verstehe, muss beim Rechnen mit Vorzeichen
trotzdem die o.g. Vorzeichenerweiterung für jedes Bit des Multiplikators
vorgenommen werden, richtig? D.h. mindest das Vorzeichenbit kippt. Nur
wenn der Multiplikant vorzeichenlos ist, dann ist auch der Multiplikant
gleich Null und auf die Addition kann komplett verzichtet werden,
andernfalls sind acht Additionen nötig.
2) Wie wird der Wert für die letzte Addition berechnet? Ich verstehe die
im zweiten Artikel genannten Schritte zur Berechnung der letzten Reihe
nicht: egal ob ich den unmodifizierten Wert verwende, das 2er-Komplement
drauf anwende, nochmal inkrementiere (so interpretiere ich den letzten
Punkt unter "Recap so far: ..."), etc. Dabei habe ich auch beide
Varianten aus vorhergehenden Frage angewandt, ich komme nicht auf den
Wert, den ich für die letzte Addition benötige, um das korrekte Ergebnis
zu erhalten.
Ich kann gerne auch mal ein Rechenbeispiel bis zur letzten Addition zur
Verfügung stellen, wenn ich weiß ob ich mit der Vermutung zu 1) richtig
liege.
Grüße
Ralf schrieb:> Das interpretiere ich so, dass einer der beiden Operanden bei gleicher> Bitbreite auch vorzeichenlos sein kann, in dem Fall verzichtet man auf> die o.g. Vorzeichenerweiterung bzw. addiert p7 weiterhin anstatt zu> subtrahieren. Ist das korrekt?
Ja.
> 1) der vorzeichenlose Multiplizierer setzt den Multiplikant auf Null,> wenn das entsprechende Bit im Multiplikator ebenfalls Null ist. Wenn ich> den Wiki-Artikel richtig verstehe, muss beim Rechnen mit Vorzeichen> trotzdem die o.g. Vorzeichenerweiterung für jedes Bit des Multiplikators> vorgenommen werden, richtig?
Richtig. Aber da die Vorzeichenerweitung von 0 wieder 0 ergibt, ist sie
für diejenigen Teilprodukte, für die das Bit im Multiplikator 0 ist,
trivial.
> D.h. mindest das Vorzeichenbit kippt.
Nein, wieso?
> Nur wenn der Multiplikant vorzeichenlos ist, dann ist auch der> Multiplikant gleich Null und auf die Addition kann komplett verzichtet> werden, andernfalls sind acht Additionen nötig.
Nein, wenn das Bit im Multiplikator 0 ist, dann ist auch bei der
vorzeichenbehafteten Multiplikation das entsprechende Teilprodukt 0 und
muss nicht addiert werden.
> 2) Wie wird der Wert für die letzte Addition berechnet? Ich verstehe die> im zweiten Artikel genannten Schritte zur Berechnung der letzten Reihe> nicht: egal ob ich den unmodifizierten Wert verwende, das 2er-Komplement> drauf anwende, nochmal inkrementiere (so interpretiere ich den letzten> Punkt unter "Recap so far: ..."), etc.
Das letzte Teilprodukt wird nicht addiert, sondern subtrahiert, weil der
Wert des höchstwertigen Bits des Multiplikators bei vorzeichenbehafteten
8-Bit-Zahlen nicht 128, sondern -128 ist. Statt zu subtrahieren wird das
Zweierkomplement addiert. Das Zweierkomplement wird gebildet, indem alle
Bits invertiert werden und zum Ergebnis 1 addiert wird. Diese 1 ist
gemeint im letzten Punkt des Recaps:
"• Another 1 must be added at the lowest active bit of the final row as
part of two's complement negation."
PS: Bevor wir weiterdiskutieren, sollten wir uns darüber einigen,
welcher der beiden Operanden in die einzelnen Bits aufgedröselt wird. Im
Wikipedia-Artikel ist dies a (der Multiplikator, dort fälschlicherweise
als Multiplikand bezeichnet), im Artikel auf dsprelated.com hingegen b
(der Multiplikand).
Hallo Yalu,
danke für deine Antworten.
> PS: Bevor wir weiterdiskutieren, sollten wir uns darüber einigen,> welcher der beiden Operanden in die einzelnen Bits aufgedröselt wird. Im> Wikipedia-Artikel ist dies a (der Multiplikator, dort fälschlicherweise> als Multiplikand bezeichnet), im Artikel auf dsprelated.com hingegen b> (der Multiplikand).
Ja, da bin ich anfangs auch drüber gestolpert :) Dann würde ich die
Operanden aus dem Wiki-Artikel vorschlagen.
>>>> 1) der vorzeichenlose Multiplizierer setzt den Multiplikant auf Null,>>>> wenn das entsprechende Bit im Multiplikator ebenfalls Null ist. Wenn>>>> ich den Wiki-Artikel richtig verstehe, muss beim Rechnen mit>>>> Vorzeichen trotzdem die o.g. Vorzeichenerweiterung für jedes Bit des>>>> Multiplikators vorgenommen werden, richtig?>>> Richtig. Aber da die Vorzeichenerweitung von 0 wieder 0 ergibt, ist sie>>> für diejenigen Teilprodukte, für die das Bit im Multiplikator 0 ist,>>> trivial.>> D.h. mindest das Vorzeichenbit kippt.> Nein, wieso?
Im Wiki-Artikel-Artikel werden die Teilsummen p0 bis P7 gebildet. Bei
der vorzeichenbehafteten Berechnung werden die Teilsummen addiert, wobei
das Vorzeichenbit invertiert ist. Der Multiplikator wurde ja schon bei
der Berechnung der Teilsummen verarbeitet, deswegen hab ich so
interpretiert, dass auch die Teilsummen, bei denen das Bit im
Multiplikator Null ist mit invertiertem Vorzeichenbit in die Berechnung
einfließen.
> Das letzte Teilprodukt wird nicht addiert, sondern subtrahiert, weil der> Wert des höchstwertigen Bits des Multiplikators bei vorzeichenbehafteten> 8-Bit-Zahlen nicht 128, sondern -128 ist.
Wird in jedem Fall subtrahiert oder nur wenn das MSB eins ist? Bzw. wird
die letzte Teilsumme subtrahiert, wenn das MSB gesetzt ist und wenn es
gelöscht ist, dann fließt die Teilsumme gar nicht in die Berechnung ein?
> Statt zu subtrahieren wird das Zweierkomplement addiert. Das> Zweierkomplement wird gebildet, indem alle Bits invertiert werden und zum> Ergebnis 1 addiert wird. Diese 1 ist gemeint im letzten Punkt des Recaps:
Ja, das ist klar. Im Vorletzten Punkt steht:
1
The final row is subtracted by inverting all active bits and adding 1 at the lowest active bit. Note, the sign bit was already inverted and is now changed back.
Dort ist ja das 2er-Komplement schon gebildet. Den letzten Punkt habe
ich anfangs so gelesen, dass nochmal eine eins addiert werden muss. Wenn
das nicht der Fall ist, dann ist das etwas unglücklich, dass es in einem
separaten Punkt steht.
Grüße
Ralf schrieb:>> Nein, wieso?> Im Wiki-Artikel-Artikel werden die Teilsummen p0 bis P7 gebildet. Bei> der vorzeichenbehafteten Berechnung werden die Teilsummen addiert, wobei> das Vorzeichenbit invertiert ist.
Ok, das war wohl ein Missverständnis. Da du von "Vorzeichenerweiterung"
schriebst, dachte ich, du bezögest dich auf das einfache, unoptimierte
Multiplikationsverfahren. Beim optimierten Verfahren wird ja keine
Vorzeichenerweiterung durchgeführt, sondern stattdessen 128 addiert, um
die Teilprodukte in den nichtnegativen Bereich zu verschieben. Somit
können auch keine Additionen eingespart werden, was aber IMHO keinen
Nachteil darstellt. Da sich die Taktfrequenz nach der am längsten
dauernden Operation richten muss, bringt die Einsparung von Additionen
keinen Geschwindigkeitsvorteil.
Den Rest muss ich mir noch einmal genauer anschauen, aber heute nicht
mehr, weil ich jetzt gleich unterwegs bin.
Yalu X. schrieb:> Ok, das war wohl ein Missverständnis. Da du von "Vorzeichenerweiterung"> schriebst, dachte ich, du bezögest dich auf das einfache, unoptimierte> Multiplikationsverfahren.
Oh, sorry. Mit der Erweiterung meinte ich das Vorgehen aus dem zweiten
Artikel: Vorzeichenbit invertieren und im Fall der ersten bzw. letzten
Teilsumme auch noch das neunte Bit setzen.
> Den Rest muss ich mir noch einmal genauer anschauen, aber heute nicht> mehr, weil ich jetzt gleich unterwegs bin.
Alles klar.
Grüße
Macht das denn bei heutigen Programmen überhaupt noch Sinn, eine
spezielle Form der Multiplizierers zu nehmen oder aufzubauen?
Z.B. wenn man nur bestimmte Definitionsbereiche hat?
Ich meine, die Vereinfachungsalgorithmen in der Software solle es doch
schaffen, einen passenden Multiplizierer in Form der Kombinatorik
aufzubauen (wenn sie nicht gleich einen integrierten benutzt).
Oder gibt es da eine Art Vorbehandlung der eingehenden Werte, dass Minus
in Plus gewandelt wird und der eigentliche Multiplizierer nur in einem
Quadranten arbeitet?
Weil dann könnte man auch hergehen, die Zahlen sortieren und immer die
größere mit der kleineren multiplizieren, um einem einem Dreieck zu
bleiben, womit sich der Kombinatorikbedarf halbiert.
?
Nicki schrieb:> Macht das denn bei heutigen Programmen überhaupt noch Sinn, eine> spezielle Form der Multiplizierers zu nehmen oder aufzubauen?
Wenn Du selbst einen Cumputerkern hardwaremäßig bauen musst, macht
das schon Sinn. :-)
Harald W. schrieb:> Vielleicht fällt Dir das Verständnis leichter, wenn Du diese> Seite in Deutsch liest:> https://de.wikipedia.org/wiki/Multiplizierer_(Digitaltechnik)
Eher nicht, weil in der deutschen Wikipedia (wieder mal) nur ein
Abklatsch dessen zu finden ist, was in den EN_WP steht.
Hab mir auch den Booth-Algo angesehen und frage mich, ob das der
Synthesizer wirklich so baut.
Hallo zusammen,
schön dass noch weitere Leute dazu gekommen sind :)
@Nicki:
> Macht das denn bei heutigen Programmen überhaupt noch Sinn, eine> spezielle Form der Multiplizierers zu nehmen oder aufzubauen?
Wie Harald schrieb, wenn's drum was eigenes zu basteln oder wenn du sehr
eingeschränkt in den Ressourcen bist, dann schaut man sich schon an, was
es so alles gibt. In meinem Fall trifft letzteres zu, ich möchte den
Multiplizierer in einem PSoC implementieren, da hast du nicht viel
Ressourcen.
@Harald:
> Vielleicht fällt Dir das Verständnis leichter, wenn Du diese> Seite in Deutsch liest:
Nee, ich sehe das wie Horst - der deutsche Wiki-Artikel taugt für's
Verständnis noch weniger...
Hier mal ein kurzes Update: wie weiter oben vermutet, muss bei den
Teilsummen, welche durch den Multiplikator auf Null gesetzt werden
trotzdem das Vorzeichenbit invertiert werden, d.h. die alle Teilsummen
müssen herangezogen werden (das gilt für den Fall, dass beide Operanden
vorzeichenbehaftet sind).
Ich glaube, den Rechenweg für einen vorzeichenbehafteten Multiplikator
und einen vorzeichenlosen Multiplikanden habe ich verstanden. Für die
Bits im Multiplikator, die Null sind wird die Teilsumme nicht verwendet.
Ebenfalls werden die Teilsummen nicht modifiziert, sie entsprechen
jeweils dem geschobenen Multiplikanden mit Ausnahme der letzten
Teilsumme. Diese wird subtrahiert. Da der Multiplikand vorzeichenlos ist
muss diese Teilsumme bei der Bildung des 2er-Komplements um ein Bit
erweitert werden. Soweit entspricht das auch der Aussage aus dem
englischen Wiki-Artikel.
Wo ich um's Verrecken nicht weiterkomme ist beim umgekehrten Fall, also
vorzeichenbehafteter Multiplikand und vorzeichenloser Multiplikator.
Soweit ich es verstanden habe, kommt hier wieder die Modifikation der
Teilsummen ins Spiel, also die Erweiterung um ein Bit für die erste und
letzte Teilsumme, wobei das Bit gesetzt ist und die Invertierung des
Vorzeichenbits aller Teilsummen vorgenommen werden muss. Da der
Multiplikator vorzeichenlos ist, wird die letzte Teilsumme addiert. Und
mit der letzten Teilsumme hapert es: unter der Annahme, dass ich alle
vorhergehenden Teilsummen richtig gebildet und addiert habe, kann ich
die letzte Teilsumme nicht herleiten. Ich kann lediglich berechnen,
welche ich bräuchte, damit das Ergebnis stimmt, aber den berechneten
Wert kann ich aus keinem der Operanden ableiten :(
Das beweist nur, dass meine Annahme nicht stimmt XD
Für Hinweise, wo es schieflaufen könnte bin ich dankbar. Ich versuch
grad mal ein Berechnungsbeispiel zusammen zu stellen, um es hier zu
posten.
Grüße
0 100011011 1 <= Vorzeichen invertiert, um ein Bit erweitert und dieses Bit gesetzt
6
1 10000000 0 <= Teilsumme ist Null, Vorzeichen invertiert
7
= 1000011011
8
2 10000000 0
9
= 10000011011
10
3 00011011 1
11
= 10011110011
12
4 10000000 0
13
= 110011110011
14
5 10000000 0
15
= 1110011110011
16
6 00011011 1
17
= 10001110110011 9139
18
7 110011011 1 <= keine Subtraktion, da B unsigned ist, um ein Bit erweitert und dieses Bit gesetzt
19
1111000100110011 -3789 (IST)
20
1011000010110011 -20301 (SOLL)
Ich hoffe das kommt richtig formatiert rüber...
Wenn ich die Teilsumme #7 berechne, die ich benötigen würde, dann komme
ich auf b100011010. Egal, welche und wie viele Bits ich flippe, etc.,
ich kann den Wert nicht herleiten.
Grüße
Nachtrag:
Ich habe vergessen zu erwähnen, dass ich an einer Berechnungsvariante
für Teilsumme #7 vorbei gekommen bin, die ich noch prüfen muss:
- Erweitere um ein Bit und dieses Bit ist gesetzt
- invertiere das Vorzeichen
- dekrementiere die Teilsumme um eins
Somit würde aus -101 => b10011011 (8 Bit) dann b100011010 (9 Bit). Halte
ich für gewagt, aber muss ich wie gesagt noch prüfen.
Grüße
Ralf schrieb:> ich möchte den Multiplizierer in einem PSoC implementieren, da hast> du nicht vielRessourcen.
Da kann aber die Quadrantenreduktion große Vorteile bringen, wenn man
alles auf positive Vorzeichen bringt, vorsortiert und sich die halbe
Tabelle / Methode spart.
Jürgen S. schrieb:> Ralf schrieb:>> ich möchte den Multiplizierer in einem PSoC implementieren, da hast>> du nicht vielRessourcen.> Da kann aber die Quadrantenreduktion große Vorteile bringen, wenn man> alles auf positive Vorzeichen bringt, vorsortiert und sich die halbe> Tabelle / Methode spart.
Theoretisch ja, aber das seh ich praktisch ja erst, wenn ich alle
Berechnungen verstanden und jeweils implementiert habe.
Grüße
Gibt es eine Implementierung für dieses Verfahren in FPGAs? Es müsste
sich doch leicht zeigen lassen, wie umfangreich und schnell sie ist.
Und wie baut der FPGA-Compiler das eigentlich so generell? Alles in
Logik oder gibt es dedizierte Addierer? Ich kenne die Carry-chains und
frage mich, ob und wie die bei der Methode mitbenutzt werden (können)?
Gustl B. schrieb:> Der nutzt die Hardwaremultiplizierer.
Ja, stimmt, allerdings war ich jetzt irgendwie gedanklich bei den
Addieren gelandet. Damit erübrigt sich die Frage, ob es zweckmäßig ist,
das in Logik zu bauen, sage ich mal.
Horst schrieb:> Gibt es eine Implementierung für dieses Verfahren in FPGAs? Es müsste> sich doch leicht zeigen lassen, wie umfangreich und schnell sie ist.
Der zweite Artikel aus meinem Eingangsbeitrag hat auch einen
Verilog-Code mit dabei, wenn ich es recht erinnere. Der implementiert
halt signed-signed.
> Damit erübrigt sich die Frage, ob es zweckmäßig ist, das in Logik zu bauen,> sage ich mal.
Außer du hast "nur" einen PSoC :D
Grüße
Ralf schrieb:> Theoretisch ja,
Du kannst den Synthesizer laufen lassen und schauen, was raus kommt. Ich
hatte das in früheren Zeiten mal untersucht und hier vor etwa 2-3Jahren
mal Tabellen dazu gepostet. Die Synthesen werden immer schlauer und
bauen nach BEdarf um existente MUL etwas varbic drum herum, bevor sie
den nächst größeren nehmen.
Allerdings verwertet die Synthese auch immer mehr vorhandene Ergebnisse
aus zurückliegenden Läufen und ist zudem von der Reihenfolge beim
Platzieren und der Größe des Restdesigns abhängig, weil timing driven
platziert wird. Damit kommt schon mal ein abweichendes Ergebnis heraus.
Bei meinen damaligen Untersuchungen fand ich, dass es eine Art Hysterese
gibt: Wenn man die designs Stück für Stück mit immer breiter werdenden
Multiplizierern austestet, in dem man die generics ändert und neu bauen
lässt, dann kommt bei ein und dem selben Design, z.B. ein 32x32 etwas
anderes heraus, wenn man breit angefangen hat, z.B. 48x48 und dann immer
kleiner geworden ist.
Bezog sich auf das Vivado von ca. 2018. Kann sein, dass es heute wieder
anders ist. Die Synthesen werden ja immer schneller und damit
oberflächlicher, d.h. mutmasslich verschwenderischer.
Thread beobachten
Seitenaufteilung abschalten