mikrocontroller.net

Forum: FPGA, VHDL & Co. Fliesskomma Multiplikation möglichst in einem Takt ;)


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Holger K. (holgerkraehe)


Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen

Ich weiss, ich spame aktuell diese Kategorie etwas zu...

Multiplikationen im FPGA ohne entsprechende HW sind ja immer etwas 
heikel.
Daher, sieht jemand eine optimale (kurze Laufzeit) Möglichkeit, diese 
Berechnung durchzuführen?

(0.2126*R + 0.7152*G + 0.0722*B)

R, G und B sind jeweils Werte von 0..255

Danke!

: Verschoben durch Moderator
von foobar (Gast)


Bewertung
2 lesenswert
nicht lesenswert
Skalier sie mit einer Zweierpotenz so, dass genügend genaue Ganzzahlen 
herauskommen, z.B.: (109*R + 366*G + 37*B) / 512.

von dummschwaetzer (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
LUT, wird aber ziemlich groß 256*256*256 Einträge

von Wolfgang (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Holger K. schrieb:
> Daher, sieht jemand eine optimale (kurze Laufzeit) Möglichkeit, diese
> Berechnung durchzuführen?

Festkommarechnung

(435*R + 1465*G + 148*B)/2048

Muss es auf vier Dezimalstellen genau sein?

Bei 2.4 Dezimalstellen für die Ausgabe scheinen das etwas übertriebene 
Anforderungen an die Rechnengenauigkeit zu sein.

von Veit D. (devil-elec)


Bewertung
-1 lesenswert
nicht lesenswert
Hallo,

wäre es nicht sinnvoller mit 10000 zu skalieren damit die Faktoren nicht 
verfälscht werden?


(2126*R + 7152*G + 722*B)/10000

von Wolfgang (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Veit D. schrieb:
> wäre es nicht sinnvoller mit 10000 zu skalieren damit die Faktoren nicht
> verfälscht werden?

Nein, eine Division durch 10000 macht die Sache im Vergleich zu 
Zweierpotenzen nicht wirklich schneller.
Und die ganzen Nachkommastellen fallen bei der Ausgabe sowieso unter den 
Tisch.
Lernt man soetwas heutzutage in der Schule nicht mehr?

von c r (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Veit D. schrieb:
> Hallo,
>
> wäre es nicht sinnvoller mit 10000 zu skalieren damit die Faktoren nicht
> verfälscht werden?

Ich kenne mich mit FPGAs nicht aus, aber ich schätze mal durch 2^n zu 
teilen kostet weniger (keine?) zusätzliche Zeit, weil man es durch ein 
nach rechts verschieben um n Bits ersetzen kann.

von foobar (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Die Division mit einer Zweierpotenz ist wesentlich schneller und 
einfacher als mit einer Zehnerpotenz.

von rbx (Gast)


Bewertung
0 lesenswert
nicht lesenswert
http://www.iti.fh-flensburg.de/lang/algorithmen/arithmetik/karatsuba-multiplikation.htm

Karatsuba-Multiplikation Könnte man auch noch im Hinterkopf haben.

von TMS320C31 (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
Daruber lacht der nur.

von Dergute W. (derguteweka)


Bewertung
-1 lesenswert
nicht lesenswert
Moin,

Vielleicht mal einen Blick in die Entwicklungsumgebung werfen; Bei den 
IP-Cores fliegt evtl. sowas schon 'rum.
Und dann muss es doch auch nicht in einem Takt ablaufen, das kann doch 
prima "gepipelined" werden. Wen kratzt das denn, wenn die Pixel beim 
Farbe auf Schwarzweisswandeln ein paar Takte unterwegs sind?
Einfach die H,V und DE Signale auch durch ein paar Flipflops schicken 
und alles ist wieder beieinander.

Gruss
WK

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
c r schrieb:
> Veit D. schrieb:
>> wäre es nicht sinnvoller mit 10000 zu skalieren damit die Faktoren nicht
>> verfälscht werden?
Naja, ich denke, dass diese Zahlen nicht mit dem Hammer in Granit 
gemeißelt sind, und z.B ein Fehler in der 4. Nachkommastelle sich kaum 
schädlich auswirkt.
> Ich kenne mich mit FPGAs nicht aus, aber ich schätze mal durch 2^n zu
> teilen kostet weniger (keine?) zusätzliche Zeit, weil man es durch ein
> nach rechts verschieben um n Bits ersetzen kann.
Das wird im FPGA einfach nur anders verdrahtet, die unnötigen unteren 
Bits sind einfach nicht angeschlossen.

foobar schrieb:
> Die Division mit einer Zweierpotenz ist wesentlich schneller und
> einfacher als mit einer Zehnerpotenz.
Digitaltechnik ist für Prozessoren und Logik "normal". Damit was im 
Zehnersystem berechnen zu lassen ist wie wenn wir was im Siebenersystem 
ausrechnen müssten: halt echt umständlich und langsam.
Was ergibt beispielsweise 11x11 im 7er-System (also dezimal 8x8)? Wie 
lang hat die Berechnung gedauert? Und wie schnell berechnet sich das im 
Dezimalsystem?

von Jürgen S. (engineer) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Lothar M. schrieb:
> Naja, ich denke, dass diese Zahlen nicht mit dem Hammer in Granit
> gemeißelt sind, und z.B ein Fehler in der 4. Nachkommastelle sich kaum
> schädlich auswirkt.
Ja, das kann man wohl so festhalten :-)

Im Ernst: Fließkommaoperationen bei Video? Solche Rechnungen auf dem 
Level haben wir vor 30 Jahren auf dem C64 schon hinbekommen, als die 
Apfelmännchen gemalt wurden, mit weit höheren Genauigkeitsanforderungen.

Bei RGB-Werten, die aus Kameras kommen, sind selten mehr, als 10 Bit zu 
erwarten. Eine strenge Fehlerrechnung weist in Richtung 12 Bit als 
maximale Auflösung für die Koeffizienten, will man keinen zusätzlichen 
Fehler machen. Daher ist der Ansatz von Wolfgang sicher der 
zielführendste:

Wolfgang schrieb:
> (435*R + 1465*G + 148*B)/2048
... vielleicht noch 1 Bit mehr, wegen der Zahl 435, die nur geringfügig 
genauer ist, als der R-Wert, laut Aufgabenstellung des TE. Die scheinbar 
kleinste Zahl, 148, ist zwar auch nur auf 1/2 digit genau, passt aber zu 
der 2048 und liefert nicht mehr Fehler, als eine Skalierung mit 512.
Man könnte also sogar noch 1 Bit weniger nehmen, mit geringem 
tolerierbarem Fehler.

rbx schrieb:
> Karatsuba-Multiplikation Könnte man auch noch im Hinterkopf haben.
Für sehr viele Multiplikationen als pipeline in FPGAs mit Mangel an 
Multipliern, ja - ansonsten ist das ja hier eine schnudellige fixed 
coefficient MUL und noch dazu mit Werten wie 148, die gerade 3 
Additionen aufwerfen.:-)

Der Blauwert wäre also B*128 + B*16 + B*4, also durchaus in einem Takt 
zu machen.

Lothar M. schrieb:
> Das wird im FPGA einfach nur anders verdrahtet, die unnötigen unteren
> Bits sind einfach nicht angeschlossen.
Womit die Binärdivision mit einem Konstantfaktor in FPGAs die 
Schnellste, aller Grund-Rechenoperationen ist. Schneller, als "+" oder 
"-". Das vergessen Viele, wenn sie ihre Formeln für FPGAs optimieren. 
Selbst MATLAB hat da seine Probleme, naheliegende gute Lösungen zu 
finden. Immer wieder lustig, das mitanzusehen.

Das Einzige, was man manchmal braucht, ist Runden vor dem Abschneiden. 
Auch da haben einige komischerweise Probleme, das einzusehen und 
anzuwenden.

von foobar (Gast)


Bewertung
0 lesenswert
nicht lesenswert
> Naja, ich denke, dass diese Zahlen nicht mit dem Hammer in Granit
> gemeißelt sind,

Jain, das sind Parameter zur RGB-nach-Luminanz-Umrechnung und in 
irgendwelchen Standards (mehr oder weniger willkürlich) spezifiziert.

Iirc, findet man das Triple [0.2126 0.7152 0.0722] unter anderem bei 
HDTV/BT.709, während SDTV/BT.601 das Triple [0.299 0.587 0.114] 
verwendet.  Ach, sind Standards nicht was Feines ;-)

von VHDL hotline (Gast)


Bewertung
0 lesenswert
nicht lesenswert
dummschwaetzer schrieb:
> LUT, wird aber ziemlich groß 256*256*256 Einträge

3 256-Einträge LUTs mit anschließender Addition tun es auch. Im Prinzip 
ähnlich wie bei deiner anderen Frage: wenn irgendwo Konstanten 
vorkommen, ist vorinitialisierter Speicher eine effiziente Möglichkeit 
(zumindest für Xilinx FPGAs).

von Vancouver (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Integer-Konstantenmultiplikationen lassen sich gut in gepipelinete 
shift&add-Operationen zerlegen. Dafür eine DSP IP zu verwenden, grenzt 
schon an Verschwendung.

von Fitzebutze (Gast)


Bewertung
0 lesenswert
nicht lesenswert
LUTs sind eine denkbar käsige Idee, siehe Rundungsfehler.
Fixpoint-Operationen sind dein Freund, 1.15 reicht typischerweise.
Fliesskomma-Units dafür zu instanzieren ist wiederum Käse.

Was den Einstieg in Fixpoint angeht, sind die Reference-Manuals zu den 
guten alten Blackfin-DSPs zu empfehlen, die erklären teils besser als so 
manches Lehrbuch.

von Markus W. (elektrowagi78) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Fitzebutze schrieb:
> LUTs sind eine denkbar käsige Idee, siehe Rundungsfehler.
> Fixpoint-Operationen sind dein Freund,

?

Wie wird denn eine FP-Operation praktisch realisiert, wenn nicht in 
LUTs?

Und wieso haben LUTs Rundungsfehler, die eine FP-Operation (angeblich) 
nicht hat?

?

von Vancouver (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Man unterscheide zwischen FPGA-Luts zur Berechnung von Logikfunktionen 
und Blockram-basierten Tabellen mit numerischen Werten.

von Mampf F. (mampf) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Holger K. schrieb:
> (0.2126*R + 0.7152*G + 0.0722*B)

Ich hatte für einen PAL-Encoder mal sowas gemacht.

Allerdings waren bei mir R, G und B keine 8Bit sondern nur jeweils 5Bit.

Und die Koeffizienten für die Multiplikation waren andere - die 
"offizielle" Formel ist ja die hier:

Y = 0,299*R + 0,587*G + 0,114*B

Aber deine Anwendung kenn ich natürlich nicht - wird sicherlich einen 
Grund haben, dass du andere Koeffizienten benutzt.

Naja, vielleicht kannst du trotzdem was mit der Source anfangen.

https://opencores.org/websvn/filedetails?repname=graphiti&path=%2Fgraphiti%2Ftrunk%2Fxilinx%2Frgb2yuv.vhd


*edit*: 45MHz auf einem Spartan 2 waren damals kein Problem (allerdings 
hatten mit 45MHz für PAL gereicht und ich hab nicht mehr ausprobiert). 
Wie schnell muss es denn bei dir sein?

: Bearbeitet durch User

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]
  • [vhdl]VHDL-Code[/vhdl]
  • [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.