Der erweiterte Euklidische Algorithmus in VHDL (effizient)

[Kiigass (Gast)]

Hallo Leute

ich bin grad auf der Suche nach einer möglichst effizienten 
Implementierung des erweiterten euklidischen Algorithmus oder eines 
äquivalenten Algorithmus in VHDL. Mir gehts dabei nur um die Berechnung 
der modularen Inversen. Seltsamer Weise finde ich kaum was zu dem Thema. 
Könnte mir bitte jemand nen Wink mit dem Zaunpfahl geben?
Also mir ist schon klar, dass man den so wie er herkömmlich notiert wird 
als Zustandsautomaten implementieren kann, aber habe die Hoffnung, dass 
es auch besser geht.

danke für eure Hilfe

[Weihnachtsmann (Gast)]

Kannst du das nicht synthetisch generieren? Die Vorschrift lässt sich 
doch auskompilieren und produziert ein rein kombinatorisches Schaltwerk, 
das das Ergebnis in einem Takt liefert.

Die algebraische Optimierung macht der VHDL-Compiler.

[Kiigass (Gast)]

Weihnachtsmann schrieb:
> Kannst du das nicht synthetisch generieren? Die Vorschrift lässt sich
> doch auskompilieren und produziert ein rein kombinatorisches Schaltwerk,
> das das Ergebnis in einem Takt liefert.
>
> Die algebraische Optimierung macht der VHDL-Compiler.

Wow, das klingt sehr interessant (vor allem der Teil mit dem Ergebnis in 
einem Takt), aber ich versteh nicht 100% wie du das meinst. Könntest du 
das bitte ausführlicher darlegen? Vor allem ein Punkt versteh ich nicht: 
In dem Algorithmus wie er häufig im Netz und der Literatur vorgestellt 
wird, wird ja mind. einmal dividiert. Diese Division in rein 
kombinatorischer Logik kann ich mir nicht vorstellen (was aber vllt auch 
an meiner mangelnden Erfahrung liegt)

danke dir schonmal!

[Hocko (Gast)]

Kiigass schrieb:
> Diese Division in rein
>
> kombinatorischer Logik kann ich mir nicht vorstellen

Funktionieren tut das schon: Man formliert eine binäre Division mit 
"schriflichem Dividieren" und lässt die FFs weg. Mit einem schnelle FPGA 
kommt man bei einem 32 Bit Dividierer auf 50MHz. Allerdings sind 
gepipelinte Strukturen effektiver.