mikrocontroller.net

Forum: FPGA, VHDL & Co. primzahlengenerator in vhdl


Autor: Armin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hi zusammen,

auf euer Anraten hin habe ich mir den Reichardt/Schwarz aus der Bib 
geliehen. Irgendwann am Anfang (S. 67) steht folgende Aufgabenstellung


"Entwerfen Sie einen taktsynchronen Primzahlengenerator: Die Primzahlen 
{1,2,3,5,7,11,13} sollen bei jeder ansteigenden Flanke des Taktsignals 
CLK am dual codierten Ausgang in der angegebenen Reihenfolge zyklisch 
generiert werden. Ein asynchroner Low-aktiver Reset setzt den Ausgang Q 
auf die Zahl 1 zurück."


Die Vorgeschlagene Lösung hat nichts mit Primzahlen zu tun. Da geht es 
um eine Zustandsmaschine, die die Ausgänge der Reihe nach mit 
hinterlegten Konstanten beschickt.
Mag ich nicht.



Aus Übungszwecken wollte ich mal versuchen, ob man eine synthetisierbare 
Beschreibung für einen ernsthaften Generator hinbekommt. Mit der 
Siebmethode ist das sicher nicht schwer, aber ich hätte es mal klassisch 
versucht:
"Durchsuche alle Zahlen bis zur aktuellen Zahl mit modulo, ob sie Teiler 
sind. Falls einer dabei ist, versuche die nächste Zahl."

Mir ist klar, dass dieser Begriff "Durchsuche" schon verdächtig nach 
touringmaschine klingt. Aber auf jeden Fall lässt der Sprachschatz von 
VHDL eine Beschreibung zu:
entity buchuebungen is
--generic();
port (  CLK, reset:  in std_logic := '0';
    Q:      out std_logic_vector(3 downto 0));
end buchuebungen;


architecture verhalten of buchuebungen is
begin
prime:
  process (reset, CLK)
    variable primeCounter: integer range 0 to 15;
    variable primeOK: std_logic;
  begin
    if '0' = reset then
      primeCounter := 0;
    elsif rising_edge(CLK) then
      primeOK := '0';                -- noch keine Primzahl gefunden.
      while('0' = PrimeOK) loop          -- so lange hochzählen, bis nächste Primzahl gefunden ist.
        primeCounter := primeCounter + 1;    -- nächste Zahl generieren
        PrimeOK := '1';              -- Annehmen, es wäre eine Primzahl
        for i in 2 to 15 loop
          if i < primeCounter/2 then  -- (For-Schleife darf keine dynamische obere Grenze haben)
            if primeCounter mod i = 0 then    -- ist doch keine Primzahl
              PrimeOK := '0';
            end if;
          end if;
        end loop;
      end loop;
      Q <= std_logic_vector(to_unsigned(primeCounter, 4));
    end if;
  end process prime;
end;

Lässt sich nicht synthetisiseren. Hatte ich irgendwie erwartet, ohne 
eine Begründung dazu haben.
Quartus meldet jetzt dasda:
"Error (10536): VHDL Loop Statement error at Buchuebungen.vhdl(25): loop 
must terminate within 10,000 iterations"
und bezieht sich damit auf die while-Schleife.

Also wenn ich nicht irgendwo einen billigen Fehler gemacht habe, 
terminiert der while-loop IMMER innerhalb von 10000 Durchläufen. In dem 
Wertebereich der primecounter-variable (0 to 15) ist die größte 
Iterationszahl die vorkommen kann 4 [nämlich 
13(prime)->14->15->0->1(prime)]

Auch wenn man der counter-Variable einen Startwert mitgibt:
variable primeCounter: integer range 0 to 15 := 0;
ändert sich der Fehler nicht. Wobei ich nicht sicher bin, ob sich das 
dann überhaupt noch richtig verhalten kann: Wird dann der primeCounter 
bei jeder positiven Flanke auf 0 gesetzt? Oder wird dieser init-Wert nur 
einmal (z.B. beim ersten "Prozessstart") zugewiesen?

Ideen?

Autor: doofi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
offtopic:
> touringmaschine

Der gute Mann hiess Turing.

Autor: Armin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
oh äh schulligung ^^
und danke

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
du hättest vielleicht erstmal das "langweilige" Beispiel machen sollen.
loop/for etc.. Produzieren parrallele Pfade und keine Sequentuielle 
Logik.
Da es unendlich viele Primzahlen gibt bricht die Schleife nie ab also 
wird die Schleife über das Limit oft (10.000 wohl bei Quartus) oft 
synthetisiert.

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

Bewertung
0 lesenswert
nicht lesenswert
      while('0' = PrimeOK) loop          -- so lange hochzählen, bis nächste Primzahl gefunden ist.
        primeCounter := primeCounter + 1;    -- nächste Zahl generieren
        PrimeOK := '1';              -- Annehmen, es wäre eine Primzahl
        for i in 2 to 15 loop
Oh, wieder mal ein C-Programmierer, der VHDL macht...

> Da es unendlich viele Primzahlen gibt bricht die Schleife nie ab
Und das hier wird das nächste sein:
  for i in 2 to 15 loop
     if primeCounter mod i = 0 then
Geht das bei Altera?
Einen Teiler, der keine Zweierpotenz ist (3,5,6,7,9...)?

@  Armin
Vergiss die C-Denkweise.
Lass while und for und loop erst mal ganz weit weg.
Lies zum Einstieg "VHDL-Synthese" von Reichhardt+Schwarz

Autor: Armin (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Lothar Miller schrieb:
> Oh, wieder mal ein C-Programmierer, der VHDL macht...

Wenn du so willst. Kannst du kein C? :P

> Geht das bei Altera?
> Einen Teiler, der keine Zweierpotenz ist (3,5,6,7,9...)?

geht, ja. Ich habe gerade einen Zähler gebaut und auf dessen Ausgang ein 
mod 7 gesetzt. Das Ergebnis steht in Q (Im Anhang RTL und Simulation, 
eine Hardware zum testen habe ich gerade nicht da). Leider sieht man im 
RTL nicht, wie dieser Modulo wirklich umgesetzt wird, ich habe einen Max 
II als Hardware eingestellt.

Das Altera Quartus ist mir irgendwie lieber als Xilinx (für das ich 
einen CPLD hier hätte). Das macht intuitiv eher das, was ich von ihm 
möchte - so weit ich das mit meinem eher knappen Erfahrungsschatz sagen 
kann ;)
Womit arbeitest du? Für die Screenshots auf deiner Website z.B.?

> Vergiss die C-Denkweise.
> Lass while und for und loop erst mal ganz weit weg.
Wie kann ich denn ohne 'for' und 'while' überprüfen, ob - um die Aufgabe 
zu vereinfachen - eine anliegende Zahl eine Primzahl ist? Ich wäre ja 
für Vorschläge offen =)

Läubi .. schrieb:
> du hättest vielleicht erstmal das "langweilige" Beispiel machen sollen.
> loop/for etc.. Produzieren parrallele Pfade und keine Sequentuielle
> Logik.
auch die Siebmethode wird eine for-schleife brauchen, wenn du das 
meinst.

> Da es unendlich viele Primzahlen gibt bricht die Schleife nie ab also
> wird die Schleife über das Limit oft (10.000 wohl bei Quartus) oft
> synthetisiert.
Aber da es doch beschränkte Zahlenbereiche (range 0 to 15) gibt, müsste 
auch diese Schleifengeschichte beschränkt sein. Warum läuft der dann 
über 10000 Mal durch?

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
WENN er das wirklich synthetisieren kann wird ein dicker Dividierer 
draus, aber ich kann mir nicht vorstellen dass er das macht, weil man 
einen Dividierer normalerweise taktet.
Und die Aufgabe aus dem hatte nicht das Lernziel Primzahlen zu erzeugen 
in Hardware, da das eine Aufgabe ist die für Hardware denkbar unggeignet 
ist wie man sieht.

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

Bewertung
0 lesenswert
nicht lesenswert
Armin schrieb:
> Lothar Miller schrieb:
>> Oh, wieder mal ein C-Programmierer, der VHDL macht...
> Wenn du so willst. Kannst du kein C? :P
Doch, aber in C denke ich anders als in VHDL ;-)

>> Geht das bei Altera?
>> Einen Teiler, der keine Zweierpotenz ist (3,5,6,7,9...)?
> geht, ja.
Krass. Lass mal den Ressourcenverbrauch sehen...
Und mach mal den Zähler etwas breiter.

> Das Altera Quartus ist mir irgendwie lieber als Xilinx (für das ich
> einen CPLD hier hätte). Das macht intuitiv eher das, was ich von ihm
> möchte - so weit ich das mit meinem eher knappen Erfahrungsschatz sagen
> kann ;)
> Womit arbeitest du? Für die Screenshots auf deiner Website z.B.?
Xilinx ISE 9 und 11
Lattice ispLever

> Wie kann ich denn ohne 'for' und 'while' überprüfen
In FPGAs mußt du in Zustandsmaschinen denken, die mit dem (es kann nur 
einen geben) FPGA-Takt weitergeschaltet werden. Weil du das bisher 
offenbar noch nicht kannst, solltest du dir mal das oben angesprochene 
Buch leisten und durcharbeiten.

Autor: Armin (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
D. I. schrieb:
> WENN er das wirklich synthetisieren kann wird ein dicker Dividierer
> draus
woraus wird ein Dividierer? Aus den 14 modulos?

D. I. schrieb:
> Und die Aufgabe aus dem hatte nicht das Lernziel Primzahlen zu erzeugen
> in Hardware, da das eine Aufgabe ist die für Hardware denkbar unggeignet
> ist wie man sieht.
Das hatte ich dann auch irgendwann verstanden. Trotzdem schadet es 
nicht, etwas zu versuchen, wenn man schon selbst irgendwelche Ideen aus 
der Aufgabenstellung zieht. Wenn man das denn so nennen darf.
Wer eine Zustandsmaschine von mir haben möchte, der soll mich nach ner 
Ampel oder so fragen ;)

Lothar Miller schrieb:
> Doch, aber in C denke ich anders als in VHDL ;-)
und ich teste die Grenzen aus. VHDL erlaubt sequenziellen Code. Nur das 
wenigste davon ist synthetisierbar. So lange ich keine brauchbaren 
Kriterien bekomme, was geht und was nicht, muss ich einfach 
herumprobieren. Da ist es dann nur schade, wenn Fehlermeldungen kommen, 
die gar keine Aussage haben. Also frage ich hier.

Lothar Miller schrieb:
> Krass. Lass mal den Ressourcenverbrauch sehen...
> Und mach mal den Zähler etwas breiter.
counter:
  process (CLK, reset)
    variable Counter: integer range 0 to 255;
  begin
    if '1' = reset then
      Counter := 0;
    elsif rising_edge(CLK) then
      Counter := Counter + 1;
    end if;
    Q <= std_logic_vector(to_unsigned(Counter mod 11, 8));
  end process counter;
Haut mich nicht wegen der Variable, sollte schnell aus dem oberen Code 
entstehen.
Auf jeden Fall eher teuer das Ganze...
Ressourcenverbrauch im Anhang, brauchst noch mehr?

Lothar Miller schrieb:
> ..., solltest du dir mal das oben angesprochene
> Buch leisten und durcharbeiten.
bitte nochmal gaaaaanz nach oben scrollen und meine erste Zeile lesen.
So schließt sich der Kreis...

Autor: Stefan Salewski (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>und ich teste die Grenzen aus. VHDL erlaubt sequenziellen Code. Nur das
>wenigste davon ist synthetisierbar. So lange ich keine brauchbaren
>Kriterien bekomme, was geht und was nicht, muss ich einfach
>herumprobieren.

Ich persönlich würde das eher als Schwachsinn bezeichnen -- mit VHDL 
etwas beschreiben zu wollen, wenn man auch nicht die entfernteste Idee 
hat, wie die Hardware dazu auf Register-Transfer-Ebene aussehen soll. 
Natürlich, du kannst einen Mikrocontroller implementieren, dann kann man 
vieles berechnen. Wenn das denn das Ziel sein soll...

Autor: Jochen Fe. (jamesy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mal so 'ne dumme Frage: Ich würde den Primzahlensucher in Hardware eher 
so implementieren, daß er sich die Zahl vornimmt, un dann hardwaremäßig 
durch die möglichen Divisoren teilt - also immer soundsoviele Impulse 
dekrementieren, und nachschauen, ob mehr, gleich, oder weniger Null 
herauskommt. Ich muß doch keinen arithmetischen Teiler im FPGA 
unterbringen!
Wenn ich die Zahl 1023 auf Primizität untersuche, dann beginne ich mit 2 
als Teiler, also immer 2 subntrahieren und Ergebnis vergleichen > = < 
Null, nächste Iteration, und ab dann mit 3, 5, 7, 9, usw dieselbe 
Operation, das kann man mit einem Addierer einfach realisieren, eine 
kurze Stae machine drumherum, um die Divisoren zu liefern, und ein 
Check, ab wann abgebrochen werden kann, das ist die nächsthöhere 
ungerade Zahl über der Quadratwurzel.
Sollte in einem FPGA recht einfach umzusetzen sein.
Oder liege ich da falsch?

Autor: Zwölf Mal Acht (hacky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das Projekt is unguenstig. Es geht ja nicht darum, die Primzahlen zu 
rechnen, sondern zu generieren. Dh repetitiv. Dazu liest man besser 
einen Speicher aus. zB ein 64MByte Flash, darf auch noch etwas groesser 
sein. Dann kriegt man wenigstens einen wert pro Zeiteinheit.
Das Problem ist, dass die Primzahlen unstet verteilt sind, man effektiv 
jeden Wert neu testen muss. zB mit dem Sieb des Erathes oder so. Eine 
Aufgabe fuer ein CPU wenn schon.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jochen Fe. schrieb:
> Sollte in einem FPGA recht einfach umzusetzen sein.
> Oder liege ich da falsch?

Ist zwar nicht die schnellste Lösung der Welt, aber eine die sich recht 
gut in Hardware gießen lässt das ist wahr.

Autor: Jochen Fe. (jamesy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn es einfach um ein Auslesen von Primzahlen geht, so kann man am 
besten ein stochastisches Rauschen erzeugen und auslesen, digital kann 
dies mit rückgekoppelten Schieberegistern einfach bewerkstelligt werden. 
GPS nutzt das.

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.