Moin,
ich möchte eine Polynomdivision (im Binären Bereich (sprich GF(2))
erstellen, ich habe dafür ein festen Divisor.
Natürlich ist da ein Schieberegisterstruktur da super (z.B.
Galois-LFSR), aber die Berechnung müsste schneller gehen.
Spricht bei dieser Schieberegisterstruktur wäre es ja so, das bei 64
Bit, ich erst nach 64 Takten mein Endergebnis mit Rest bekomme.
Gibts da auch Verfahren, die auch gerne mehr Hardwareaufwand benötigen,
dafür aber schneller sind?
Natürlich möchte ich das in VHDL auf einem FPGA machen.
Gerne auch Links oder Schlagwörter wonach ich da suchen kann.
Vielen Dank im vorraus!
Gruß
H.K.
H.K. schrieb:> ich habe dafür ein festen Divisor.
Ich mache da gern eine Multiplikation mit dem Reziprokwert:
Beitrag "Re: Frage VHDL Division"
Allerdings sind 64 Bit da schon recht sportlich...
Ich weiß nicht ob wir aneinander vorbeireden.
Ich möchte ja nicht 2 Integerzahlen miteinander dividieren, sondern 2
Polynome dividieren.
Sprich, bei 0xC / 0x4 würde ja 0x3 rauskommen (bei Integer)
Bei Polynomdivision wäre es ja sowas wie:
x^3+x2 / x^1 + 1 = x^2 Rest 0
Für detailierte Rechnung mal hier:
http://www.ee.unb.ca/cgi-bin/tervo/calc.pl?num=1100&den=11&f=d&e=1&m=1
Habe ich vllt meine Frage falsch formuliert, oder deinen Punkt nicht
verstanden?
H.K. schrieb:> Gibts da auch Verfahren, die auch gerne mehr Hardwareaufwand benötigen,> dafür aber schneller sind?
Ja klar, du musst eben 4 Prüfungen machen, wegen des möglichen
Divisionsrestes und bekommst dann 00,01,10,11 und damit 4
"Frageschaltungen" und auch 4 mögliche Ergebnis-Pfade. Damit
vervierfacht sich dieser Teil des designs und du kriegst das Ergebnis
mit der halben Zahl der Takte.
In der Realität wächst das design bei kleinen Divisionen um rund Faktor
2.5 bis 3.5, weil noch Laden und Entladen hinzukommen. Gleichsam ist die
Zahl der Takt auch meistens etwas wie X+N und damit folgt als Verkürzung
X+N/2.
Bei 64 Bit bringt es dir in der Tat richtig Tempo aber massig mehr
Fläche. Aber: Es ist nicht mehr ganz so schnell taktbar!
Es kann aber sein, dass das mit deinem festen Divisorpolynom ziemlich
zusammenpurzelt. Schreibe es mal als Kombinatorik hin und schau, was
rauskommt. Die Synthese vereinfacht dir das dann schon passend. Danach
heißt es, das Design geschickt zu teilen und jeweils FF-Stufen
dazwischen zu setzen, um auf timing zu kommen. Das kann dann aber
mächtig aufblähen. Je nach Aufgabe ist es gfs zweckmäßiger mit der
Latenz zu leben und 2 oder mehr Schaltungen parallel rechnen zu lassen,
um die Bandbreite zu packen.
Moin Jürgen,
das klingt nach nem spannenden Ansatz.
Ich werde das mal ausprobieren. Damit hätte ich ja noch die hälfte der
Takte, das mir leider auch noch zuviel ist, aber dann ist es wohl
technisch bedingt.
Alternativ (wie du auch schon meintest) werde ich das wohl
parallelisieren müssen.
Werde mir dann auch mal anschauen wie hoch ich beides takten kann. Der
"Standardweg" über das Galois-LFSR sollte sich ja bis zum max. Takt
takten lassen. Ist ja nur 1x mal schieben mit XOR.
H.K. schrieb:> Spricht bei dieser Schieberegisterstruktur wäre es ja so, das bei 64> Bit, ich erst nach 64 Takten mein Endergebnis mit Rest bekomme.
Sicher?! Ich glaub du hast das mit dem Schieberegister bei LSFR nicht
richtig verstanden, nach jedem Takt liegt da ein Endgebnis vor.
> Ist ja nur 1x mal schieben mit XOR.
Schieben ist nicht gleich schieben, im FPGA kann man schiebstrukturen
aus verschiedenen Strukturen aufbauen:
-Slice-FF
-SLRmakros
-dsp-MULT mit fixem Faktor 2
-SERDES-Macros
um da das Optimum zu finden, muss man eine Implementierung komplett
durchlaufen lassen und das period constraint kontroliert ändern.
Aber so eine Optimierung auf die höchste Frequenz ist meist sinnfrei,
weil die Bit und damit die Taktrate für das Übertragungsverfahren fix
vorgegeben ist (bspw IEEE 802.16).
Die Polynomdivision P/Q ist eine in P lineare Funktion d.h.
(P1+P2)/Q=P1/Q+P2/Q Daher kann man das 64 Bit Polynom P z.B. in 8 Bytes
aufteilen und die Polynomdivision für jedes Byte durch eine Tabelle mit
256 Einträgen erledigen. Die 8 Teilresultate muss man dann noch
addieren. Das ganze lässt sich auch gut parallelisieren.
H.K. schrieb:> Ich werde das mal ausprobieren. Damit hätte ich ja noch die hälfte der> Takte, das mir leider auch noch zuviel ist, aber dann ist es wohl> technisch bedingt.
Der nächste Schritt wären 8 bei dann X+16 Takten. Da ein konstantes
Divisor-Polynom vorliegt, müsste man das leicht vorberechnen und
formulieren lassen können. Allerdings kann ich so nicht abschätzen, ob
man nicht irgendwann mehr pipeline-Takte braucht, um bei einem zu
komplexen Polynom die möglichen Ergebnisvaritionen auszurechnen, was das
design wieder verlangsamen würde.
ossi schrieb:> Die Polynomdivision P/Q ist eine in P lineare Funktion d.h.> (P1+P2)/Q=P1/Q+P2/Q Daher kann man das 64 Bit Polynom P z.B. in 8 Bytes> aufteilen
Das wäre mal interessant, zu vergleichen und ob der Synthesizer zu
ähnlichen Ergebnissen führt. Ganz sicher wäre es vorteilhaft,
Vorberechnungen so weit als möglich zur Designphase zu machen.
