www.mikrocontroller.net

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


Autor: Anguel S. (anguel)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Der Besucher (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Helmut (Gast)
Datum:

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

Autor: Der Besucher (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: ich (Gast)
Datum:

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

Autor: ich (Gast)
Datum:

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

Autor: Anguel S. (anguel)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Anguel S. (anguel)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Anguel S. (anguel)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://www3.informatik.uni-erlangen.de/Lehre/TechI...

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.

Autor: Anguel S. (anguel)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Datenkrake weiß es wieder:

http://books.google.com/books?id=mwUV7ZK9l9gC&lpg=...

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

Autor: Sym (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Lattice User (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kleiner tip:

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

Autor: Sven H. (dsb_sven)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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...

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

Autor: Anguel S. (anguel)
Datum:

Bewertung
0 lesenswert
nicht 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 ;)

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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:
1734457011 = 01100111011000011011011010110011₂

01 10 01 11 01 10 00 01 10 11 01 10 10 11 00 11
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  '--  +11
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  '-----  -00
 |  |  |  |  |  |  |  |  |  |  |  |  |  '--------  +11
 |  |  |  |  |  |  |  |  |  |  |  |  '-----------  -10
 |  |  |  |  |  |  |  |  |  |  |  '--------------  +10
 |  |  |  |  |  |  |  |  |  |  '-----------------  -01
 |  |  |  |  |  |  |  |  |  '--------------------  +11
 |  |  |  |  |  |  |  |  '-----------------------  -10
 |  |  |  |  |  |  |  '--------------------------  +01
 |  |  |  |  |  |  '-----------------------------  -00
 |  |  |  |  |  '--------------------------------  +10
 |  |  |  |  '-----------------------------------  -01
 |  |  |  '--------------------------------------  +11
 |  |  '-----------------------------------------  -01
 |  '--------------------------------------------  +10
 '-----------------------------------------------  -01
                                                  ----
                                                001011

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

Der Algorithmus kann wahlweise sequentiell oder parallel umgesetzt
werden.

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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!

Autor: Xenu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Von Xilinx gibt es einen kostenlosen Divider-Core:

http://www.xilinx.com/support/documentation/ip_doc...

Autor: Uwe Bonnes (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Klaus Wachtler (mfgkw)
Datum:

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

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Uwe Bonnes (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gibt es da auch was Universelles?

Autor: jubu (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Jürgen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Gibt es da auch was Universelles?

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

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

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

Autor: Der Besucher (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: ekke (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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. :-)

Autor: D. I. (Gast)
Datum:

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

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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...

Autor: ekke (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Segor (Gast)
Datum:

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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.