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...
:
Bearbeitet durch Moderator
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.
:
Bearbeitet durch User
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.
Beitrag #7113364 wurde von einem Moderator gelöscht.
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.