Hallöchen! Ich will in einem Spartan 3A prüfen, ob eine 32 bit unsigned Zahl durch 10 teilbar ist. Der User schickt also eine 32 bit unsigned Zahl zum FPGA, dort sollen aber nur 10er Schritte angenommen werden: 0, 10, 20, 30 ist ok, aber 1, 2, 3, 11, 15, 22 ist nicht ok. Genau diese Prüfung soll nun in VHDL implementiert werden. Hat jemand einen Tipp, wie man sowas am besten macht? Danke im Voraus! Grüße, Anguel
Gast
#1867406
Ein wirklich recht seltsames Anliegen. Normalerweise versucht man alles um mit Zweierpotenzen rechnen zu können. Dann sind diese Vergleiche trivial. Kann das Problem nicht eher in diese Richtung abgewandelt werden? Na ich bin auch auf synthetisierbare Vorschläge gespannt. Der Besucher
Gast
#1867409
Aus welchem Grund kann man die untersten Bit's nicht auf 1010 b prüfen?
Gast
#1867412
@Helmut: weil dann auch 11010b (=26d) durch 10 teilbar sein müßte... Ansonsten fällt mir spontan nur eine Division durch 10 mit check ob der Rest gleich 0 ist ein. Der Besucher
Helmut schrieb: > Aus welchem Grund kann man die untersten Bit's nicht auf 1010 b > prüfen? Prüfen kannst du das sehr wohl, das sagt aber nicht, ob die Zahl durch 10 teilbar ist. z.B. dez. 20 ist 0b00010100
Helmut schrieb: > Aus welchem Grund kann man die untersten Bit's nicht auf 1010 b > prüfen? Kann man. Aber probier das mal mit dezimal 20 aus.
Helmut schrieb: > Aus welchem Grund kann man die untersten Bit's nicht auf 1010 b > prüfen? Schon bei 20 gehts schief: 20 = 0x14 = 00010100
Der Besucher schrieb: > Ansonsten fällt mir spontan nur eine Division durch 10 mit check ob der > Rest gleich 0 ist ein. Mit anderen Worten: x modulo 10 muß 0 sein.
Gast
#1867422
Du musst "nur" in BCD wandeln, ich glaube das ist nicht sonderlich schwierig. Und dann das untere Nibble auf "0000" prüfen.
Gast
#1867424
Wenn du ISE verwendest könnte es für die BCD Wandlung einen fertigen IP Core geben.
Der Besucher schrieb: > Ein wirklich recht seltsames Anliegen. Normalerweise versucht man alles > um mit Zweierpotenzen rechnen zu können. Dann sind diese Vergleiche > trivial. > Kann das Problem nicht eher in diese Richtung abgewandelt werden? Nun ja, über USB kommt eine 32 bit unsigned Zahl in den FPGA rein, was kann man da abwandeln?
Klaus Wachtler schrieb: > Mit anderen Worten: x modulo 10 muß 0 sein. Danke, diese Idee hatte ich auch, weiß aber nicht, ob es da evtl. einen IP-Core im ISE für gibt, oder geht das gar in VHDL?
ich schrieb: > Wenn du ISE verwendest könnte es für die BCD Wandlung einen fertigen IP > Core geben. Danke, die Idee ist ganz gut. Ich werde mal schauen, ob es sowas gibt.
Gast
#1867441
http://www3.informatik.uni-erlangen.de/Lehre/TechInfII/klausur/klausur-ti2-2008-03-18.pdf Wenn du Aufgabe 3.2 löst, kannst du das entstandene Assemblerprogramm direkt in VHDL umsetzen, da in der Aufgabe auch nur shift und Logikoperationen erlaubt sind. Aber ja die aufgabe ist ein bisschen tricky und mir fällt die Lösung von damals auch nicht mehr auf die schnelle ein, ging jedenfalls über Division. Mit effizient ist übrigens in mind. logarithmischer Zeit gemeint. Aber die BCD Wandlung gefällt mir am besten.
Die Datenkrake weiß es wieder: http://books.google.com/books?id=mwUV7ZK9l9gC&lpg=PA147&ots=OxTreaiv0x&dq=vhdl%20%22binary%20to%20bcd%22&pg=PA147#v=onepage&q=vhdl%20%22binary%20to%20bcd%22&f=false Das ist zwar nicht für 32 bit, aber lässt sich vermutlich portieren. Scheint nicht besonders effizient zu sein, aber wenn es nix besseres gibt...
Gast
#1867465
Ganz einfach: Schritt 1: Letztes Bit auf 0 kontrollieren. -> Falls ja durch 2 teilbar. Schritt 2: Zahl um eins nach rechts schieben und durch 5 dividieren (am besten seriell) und Divisionsrest auf 0 überprüfen. Somit hast du den Divisionsrest durch 10 errechnet.
Gast
#1867467
Kleiner tip: ca 20 threads weiter unten gibt es in diesem Forum einen kurzen Thread "Division in VHDL".
Klaus Wachtler schrieb: > Der Besucher schrieb: >> Ansonsten fällt mir spontan nur eine Division durch 10 mit check ob der >> Rest gleich 0 ist ein. > > Mit anderen Worten: x modulo 10 muß 0 sein. Gibts denn in deiner Programmiersprache keinen Modulo Operator? In c ist das der % Operator.
Anguel S. schrieb: > Die Datenkrake weiß es wieder:... Das ist der traditionelle shift-add-6 Weg. Den gibts auch kompakter: http://www.lothar-miller.de/s9y/archives/34-Vektor-nach-BCD.html BTW: das Buch habe ich auch. Der Programmierstil da drin ist m.E. unglaublich aufwendig. So kommt VHDL zu seinem Ruf, eine geschwätzige Sprache zu sein... > Gibts denn in deiner Programmiersprache keinen Modulo Operator? > In c ist das der % Operator. In VHDL auch. Nur lässt der sich unglaublich schlecht in Hardware umsetzen, weil diese Operation auf einer Division basiert...
Danke für die Tipps! Werde mal schauen, welche Methode für mich am besten geeignet ist. Dachte nur, es gäbe eine super-effiziente Lösung, scheint aber leider nicht der Fall zu sein ;)
Hier ist noch ein anderer Vorschlag: Es wird geprüft, ob die Zahl durch 2 und durch 5 teilbar ist. Ersteres geschieht einfach durch Überprüfung des letzten Bits. Für die Teilbarkeit durch 5 wird nicht eine komplette Division oder gar eine BCD-Umwandlung bemüht (die ja gleich mehrere Divisionen benötigt), sondern folgendes Verfahren angewandt, das darauf beruht, dass 5 um 1 größer als eine Zweierpotenz (2²) ist: Die eingegebene 32-Bit-Zahl wird in 16 Zweiergruppen unterteilt. Jede dieser Zweiergruppen wird als 2-Bit-Zahl mit dem Wertebereich [0..3] interpretiert. Diese 16 Zahlen werden mit alternierenden Vorzeichen (also immer abwchselnd positiv und negativ) addiert. Die Summe liegt immer im Bereich von -24 bis +24 und hat den gleichen Fünferrest wie die ursprüngliche Zahl. Die ursprüngliche Zahl ist also genau dann durch 5 teilbar, wenn die Summe einen der Werte -20, -15, -10, -5, 0, +5, +10, +15, +20 hat. Dies kann man durch 9 Vergleiche herausfinden. Alternativ kann man zur Summe 25 addieren (damit sie auf jeden Fall po- sitiv wird) und auf die enstehende 6-Bit-Zahl das Zweiergruppenverfahren erneut anwenden. Dabei entsteht eine neue Summe im Bereich von -3 bis +4. Da darin nur die 0 durch 5 teilbar ist, genügt also eine Überprüfung der zweiten Summe auf 0, um die Teilbarkeit der ursprünglichen Zahl durch 5 nachzuweisen. Beispiel:
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
Die Summe ist 11, also ist die ursprüngliche Zahl nicht durch 5 teilbar. Der Algorithmus kann wahlweise sequentiell oder parallel umgesetzt werden.
Yalu X. schrieb: > eine BCD-Umwandlung bemüht (die ja gleich mehrere Divisionen benötigt) Der Ansatz gefällt mir, aber die Informationslage bezüglich der BCD-Wandlung ist nicht aktuell. Stichwort nach wie vor: Shift-Add-6 oder Shift-Add-3 (je nach dem, ob vor oder nach dem Schieben addiert wird). http://edda.csie.dyu.edu.tw/course/fpga/Binary2BCD.pdf http://en.wikipedia.org/wiki/Double_dabble
Lothar Miller schrieb: > Der Ansatz gefällt mir, aber die Informationslage bezüglich der > BCD-Wandlung ist nicht aktuell. Stichwort nach wie vor: Shift-Add-6 oder > Shift-Add-3 Oh ja, stimmt! Dass es deutlich bessere Algorithmen gibt als die fortgesetzte Division, habe ich irgendwie verdrängt, obwohl erst vor kurzem hier ein Thread zu dem Thema lief. Danke für den Hinweis!
Gast
#1867772
Von Xilinx gibt es einen kostenlosen Divider-Core: http://www.xilinx.com/support/documentation/ip_documentation/div_gen_ds530.pdf
Gast
#1867946
Warum nicht der Ansatz mit Pruefung auf 0b1010. 1: Fals weniger als 4 bits vorhanden: nicht teilbar 2. Falls letztes Bit == 1: nicht teilbar 3: Falls die letzten 4 bits =1010 : teilbar, falls nicht, eins nach rechts schieben und wieder bei 1 beginnen
also ist 0b11010, auch bekannt als 26, prima durch 10 teilbar.
Gast
#1867987
> Die ursprüngliche Zahl ist also genau dann durch 5 teilbar, wenn die > Summe einen der Werte -20, -15, -10, -5, 0, +5, +10, +15, +20 hat. Dies > kann man durch 9 Vergleiche herausfinden. Das klingt für mich nach LUT, nicht nach Vergleichern. Da muss man vermutlich gar nicht mehr viel optimieren, das macht dann schon das Synthesetool.
Gast
#1868019
Autsch, mit Fieber sollte man keine tollen Ideen posten... Fuer die BCD Wandlungs gibt es auch von Opencore einen Core, den ich schon mal erfolgreich eingesetzt habe
Gast
#1868028
Gibt es da auch was Universelles?
Gast
#1868047
Hallo Ich würde es so ähnlich wie Yalu X machen. Ich würde im 16er System die Quersumme bilden. Weil 16 modulo 15 = 1, kann man damit mod 15 rechnen (wie im 10er System die 9er-Probe). Wenn diese Zahl 0, 5 oder 10 ist dann ist die Zahl durch 5 teilbar. Für das Beispiel von Yalu X ergibt sich: 1734457011 = 6761B6B3H 6 + 7 + 6 + 1 + B + 6 + B + 3 = 33H 3 + 3 = 6 also ist 1734457011 % 15 = 6 also nicht durch 5 teilbar. jubu
Gast
#1868062
> Gibt es da auch was Universelles?
Du fängst mit der höchstwertigen Stelle an, und rechnest in jedem
Schritt1 | |
Also hier
1 | |
Das ist ein endlicher Automat, der sich leicht mit einer Tabelle
implementieren läßt.
Gast
#1868676
@Yalu X & jubu: habt ihr für eure vorgestellten Algorythmen irgendwelche weiterführende Literatur. Wenn es sogar Beweise gibt, wäre das extrem toll. Der Besucher
Gast
#1868691
Lothar Miller schrieb: > Yalu X. schrieb: >> eine BCD-Umwandlung bemüht (die ja gleich mehrere Divisionen benötigt) > Der Ansatz gefällt mir Ich habe überhaupt keine Ahnung von VHDL, aber eine Frage kommt dir da gleich in den Sinn: Modulo ist eine Division, BCD-Umwandlung sind mehrere, warum sollte ich dann nicht Modulo nehmen? Und diesen Ansatz verstehe ich auch nicht: Sym schrieb: > Schritt 1: Letztes Bit auf 0 kontrollieren. -> Falls ja durch 2 teilbar. > Schritt 2: Zahl um eins nach rechts schieben und durch 5 dividieren (am > besten seriell) und Divisionsrest auf 0 überprüfen. Somit hast du den > Divisionsrest durch 10 errechnet. Einen Modulo, also eine Division, durch einmal Bitschieben und eine Division ersetzen ist sinnvoll? Vermutlich übersehe ich was, wäre nett wenn mir einer verrät, was es ist. :-)
Gast
#1868878
bcd umwandlung kann man mit division implementieren muss man aber nicht, geht auch anderst wie man hier schon gesehen hat
ekke schrieb: > warum sollte ich dann nicht Modulo nehmen? Du hast den Grund selbst genannt: > Modulo ist eine Division Es geht dabei nicht um VHDL (VHDL an sich kennt den Divisions- und den Modulo-Operator), sondern darum, dass sich Divisionen nur sehr aufwändig in Hardware abbilden lassen...
Gast
#1869032
Lothar Miller schrieb: > Es geht dabei nicht um VHDL (VHDL an sich kennt den Divisions- und den > Modulo-Operator), sondern darum, dass sich Divisionen nur sehr aufwändig > in Hardware abbilden lassen... Doch, den Teil habe ich verstanden, ich hatte nur ein Verständnisproblem, dass die BCD-Umwandlung nicht zwangsweise mit Divisionen erfolgen muss. Das scheint die Geschichte mit den Cores zu sein.
Der Besucher schrieb: > habt ihr für eure vorgestellten Algorythmen irgendwelche weiterführende > Literatur. Such mal nach "Teilbarkeitsregeln" und "Quersumme", ein erster Anlauf ist Wikipedia. Die Teilbarkeitsregeln im Dezimalsystem lassen sich auf andere Stellenwertsysteme übertragen. In meinem Beitrag benutzte ich die Teilbarkeitsregel durch 5 im Vierer- system, die der Teilbarkeitsregel durch 11 im Dezimalsystem entspricht. In beiden Fällen wird der Rest bei der Division durch 5 bzw. 11 mit Hilfe der alternierenden Quersumme berechnet. Die von jubu angesprochene Teilbarkeitsregel durch 15 im Hexadezimalsys- tem entspricht der Teilbarkeitsregel durch 9 im Dezimalsystem. Beidesmal wird die nichtalternierende Quersumme angewendet. > Wenn es sogar Beweise gibt, wäre das extrem toll. Die Beweise sind nicht schwierig. Es wird dabei in beiden Fällen eine vollständige Induktion über die Anzahl der Ziffern der zu untersuchenden Zahl gemacht. Für die Umformungen braucht man noch etwas Modulorechnung.
Gast
#1873190
Interessante Anwendung für die Restklassenbetrachtung. Jetzt weiss ich endlich mal, wofür ich das früher gelernt habe :-)
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.