Forum: FPGA, VHDL & Co. Wie prüfe ich, ob eine Zahl durch 10 teilbar?


von Anguel S. (anguel)


Lesenswert?

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

von Der Besucher (Gast)


Lesenswert?

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

von Helmut (Gast)


Lesenswert?

Aus welchem Grund kann man die untersten Bit's nicht auf 1010 b
prüfen?

von Der Besucher (Gast)


Lesenswert?

@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

von Klaus W. (mfgkw)


Lesenswert?

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

von Karl H. (kbuchegg)


Lesenswert?

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.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

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

von Klaus W. (mfgkw)


Lesenswert?

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.

von ich (Gast)


Lesenswert?

Du musst "nur" in BCD wandeln, ich glaube das ist nicht sonderlich 
schwierig. Und dann das untere Nibble auf "0000" prüfen.

von ich (Gast)


Lesenswert?

Wenn du ISE verwendest könnte es für die BCD Wandlung einen fertigen IP 
Core geben.

von Anguel S. (anguel)


Lesenswert?

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?

von Anguel S. (anguel)


Lesenswert?

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?

von Anguel S. (anguel)


Lesenswert?

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.

von D. I. (Gast)


Lesenswert?

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.

von Anguel S. (anguel)


Lesenswert?

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...

von Sym (Gast)


Lesenswert?

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.

von Lattice User (Gast)


Lesenswert?

Kleiner tip:

ca 20 threads weiter unten gibt es in diesem Forum einen kurzen
Thread "Division in VHDL".

von Sven H. (dsb_sven)


Lesenswert?

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.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

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...

von Anguel S. (anguel)


Lesenswert?

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 ;)

von Yalu X. (yalu) (Moderator)


Lesenswert?

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
1734457011 = 01100111011000011011011010110011₂
2
3
01 10 01 11 01 10 00 01 10 11 01 10 10 11 00 11
4
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
5
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  '--  +11
6
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  '-----  -00
7
 |  |  |  |  |  |  |  |  |  |  |  |  |  '--------  +11
8
 |  |  |  |  |  |  |  |  |  |  |  |  '-----------  -10
9
 |  |  |  |  |  |  |  |  |  |  |  '--------------  +10
10
 |  |  |  |  |  |  |  |  |  |  '-----------------  -01
11
 |  |  |  |  |  |  |  |  |  '--------------------  +11
12
 |  |  |  |  |  |  |  |  '-----------------------  -10
13
 |  |  |  |  |  |  |  '--------------------------  +01
14
 |  |  |  |  |  |  '-----------------------------  -00
15
 |  |  |  |  |  '--------------------------------  +10
16
 |  |  |  |  '-----------------------------------  -01
17
 |  |  |  '--------------------------------------  +11
18
 |  |  '-----------------------------------------  -01
19
 |  '--------------------------------------------  +10
20
 '-----------------------------------------------  -01
21
                                                  ----
22
                                                001011

Die Summe ist 11, also ist die ursprüngliche Zahl nicht durch 5 teilbar.

Der Algorithmus kann wahlweise sequentiell oder parallel umgesetzt
werden.

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

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

von Yalu X. (yalu) (Moderator)


Lesenswert?

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!

von Xenu (Gast)


Lesenswert?

Von Xilinx gibt es einen kostenlosen Divider-Core:

http://www.xilinx.com/support/documentation/ip_documentation/div_gen_ds530.pdf

von Uwe Bonnes (Gast)


Lesenswert?

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

von Klaus W. (mfgkw)


Lesenswert?

also ist 0b11010, auch bekannt als 26, prima durch 10 teilbar.

von Morin (Gast)


Lesenswert?

> 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.

von Uwe Bonnes (Gast)


Lesenswert?

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

von Michael (Gast)


Lesenswert?

Gibt es da auch was Universelles?

von jubu (Gast)


Lesenswert?

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

von Jürgen (Gast)


Lesenswert?

> Gibt es da auch was Universelles?

Du fängst mit der höchstwertigen Stelle an, und rechnest in jedem 
Schritt
1
rest = (basis * rest + ziffer) % teiler

Also hier
1
rest = (2 * rest + bit) % 5

Das ist ein endlicher Automat, der sich leicht mit einer Tabelle
implementieren läßt.

von Der Besucher (Gast)


Lesenswert?

@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

von ekke (Gast)


Lesenswert?

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. :-)

von D. I. (Gast)


Lesenswert?

bcd umwandlung kann man mit division implementieren muss man aber nicht, 
geht auch anderst wie man hier schon gesehen hat

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

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...

von ekke (Gast)


Lesenswert?

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.

von Yalu X. (yalu) (Moderator)


Lesenswert?

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.

von Segor (Gast)


Lesenswert?

Interessante Anwendung für die Restklassenbetrachtung. Jetzt weiss ich 
endlich mal, wofür ich das früher gelernt habe :-)

Bitte 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
Noch kein Account? Hier anmelden.