Binäre Polynomdivision

H.K. Gast #7113126
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
H.K. Gast #7113144
Lesenswert?
• ▲
▼ 
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?
Antwort Zitieren Bearbeiten Löschen Beitrag melden
J. S. Persönliche Seite #7113173
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
H.K. Gast #7113207
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Beitrag #7113364 wurde von einem Moderator gelöscht.
Mike Teavee Gast #7113578
Lesenswert?
• ▲
▼ 
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).
Antwort Zitieren Bearbeiten Löschen Beitrag melden
ossi Gast #7113936
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
J. S. Persönliche Seite #7114336
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren