primzahlengenerator in vhdl

[Armin (Gast)]

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?

[doofi (Gast)]

offtopic:
> touringmaschine

Der gute Mann hiess Turing.

[Armin (Gast)]

oh äh schulligung ^^
und danke

[Läubi .. (laeubi)]

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.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

      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

[Armin (Gast)]

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?

[D. I. (Gast)]

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.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

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.

[Armin (Gast)]

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

[Stefan Salewski (Gast)]

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

[Jochen F. (jamesy)]

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?

[Purzel H. (hacky)]

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.

[D. I. (Gast)]

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.

[Jochen F. (jamesy)]

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.