mikrocontroller.net

Forum: FPGA, VHDL & Co. Zähler für Primzahlen


Autor: F. M. (frabi)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Forum,


ich bin momentan dabei, mittels ISE Design Suite im Schematic Typ und 
einem PLD folgendes zu realisieren:

Eine Kombination aus Zähler und Decoder, wobei der Zähler binär die 
Primzahlen zwischen 0 und 20 (also 2,3,5,7,11,13,17,19) ausgegeben 
werden, welche durch den Decoder entsprechend auf zwei 7-Segment 
Anzeigen ausgegeben werden.

Außerdem soll es noch eine Möglichkeit geben, die ganze Schaltung zu 
resetten.

Bislang habe ich einen Decoder mit fünf Eingängen fertiggestellt, der 
eben der die Primzahlen bei entsprechenden high oder low Werten anzeigt.
(Hierzu: Auf der ersten 7-Segment Anzeige wird immer dann die eins 
angezeigt, wenn ein high am Eingang anliegt. Die erste Anzeige ist also 
mehr oder weniger seperat, während die zweite Anzeige mit den 
Binärwerten von den Zahlen 1,2,3,5,7 und 9 arbeitet.)

Nun bin ich allerdings etwas überfragt, wie ich den zugehörigen Zähler, 
der eben mehrere Zahlen überspringt, und Resetter realisieren kann, hat 
da vielleicht jemand eine Idee für mich?

Ich bedanke mich im Vorraus für jede hilfreiche Antwort!

Autor: Tobias B. (Firma: www.elpra.de) (ttobsen)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Spontan würde ich sagen, leg die Primzahlen in ein ROM ab und lass den 
Read-Pointer einfach durchiterieren.

Autor: Analog OPA (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Man sollte aus dem Mathematikunterricht wissen, dass es keine 
analytische Vorschrift zur Bilung von Primzahlen gibt. Daher ist ein 
solches Vorgehen unproduktiv. Tabelle ist sicher die gegebene Lösung.

Autor: Theor (Gast)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Analog OPA schrieb:
> [...], dass es keine
> analytische Vorschrift zur Bilung von Primzahlen gibt.
> [...]

Das ist in diesem Zusammenhang, und so ausgedrückt, nicht korrekt.


Hier liegt der besondere Fall vor, dass eine obere Grenze (20) 
festgelegt. In diesem Fall gibt es durchaus einen geschlossenen bzw. 
analytischen Ausdruck für die Folge der Primzahlen.
Es gibt nur keinen geschlossenen bzw. analytischen Ausdruck für eine * 
nach oben offene* Folge von Primzahlen.

In diesem Fall, wäre, neben der Benutzung einer Tabelle, eben auch ein 
boolescher Ausdruck möglich, den man findet, wenn man zunächst die 
Wahrheitstabelle der Mimik aufstellt. Links, als Eingabe, die Primzahlen 
und rechts, als Ergebnis die jeweils auf die linke Zahl folgende 
Primzahl.
Das ist sicher aufwendiger, als eine Tabelle aufzustellen, aber sowohl 
lehrreich als auch ein Beweis für meine obige Behauptung.

Autor: foobar (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Nicht so kompliziert. Einfach nen 3-Bit-Zähler und der 7-Segment-Dekoder 
konvertieren 0 nach "2", 1 nach "3", ..., 7 nach "19".

Autor: Theor (Gast)
Datum:

Bewertung
-3 lesenswert
nicht lesenswert
foobar schrieb:
> Nicht so kompliziert. Einfach nen 3-Bit-Zähler und der 7-Segment-Dekoder
> konvertieren 0 nach "2", 1 nach "3", ..., 7 nach "19".

Da schon einfache, grammatikalisch korrekte Sätze für Dich zu 
kompliziert sind ... Was soll man da von Deiner Antwort halten? :-)

Autor: foobar (Gast)
Datum:

Bewertung
-2 lesenswert
nicht lesenswert
Deine sind ja auch nicht besser ...

Autor: Lothar M. (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
F. M. schrieb:
> Nun bin ich allerdings etwas überfragt, wie ich den zugehörigen Zähler,
> der eben mehrere Zahlen überspringt, und Resetter realisieren kann, hat
> da vielleicht jemand eine Idee für mich?
Dieser Ansatz ist zu umständlich. Du hast das Einfachere zuerst gemacht 
und willst das Komplizierte da dran flanschen.

Mach das mit dem ROM. Im 8x16 Bit ROM (*) kannst du auch gleich direkt 
das Muster für die Ausgabe auf die Anzeigen ablegen. Dann brauchst du 
lediglich den erwähnten 3 Bit Binärzähler und bist fertig. Alles Andere 
ist viel zu umständlich mit dieser unsäglichen Schaltplaneingabe. In 
VHDL wären das bestenfalls 20 Zeilen, wenn ich das Design mit 
Kommentaren schreibe...

> mittels ISE Design Suite im Schematic Typ
Darf man fragen, für wen oder was du das so mittelalterlich im Schematic 
machen musst und keine HDL verwenden darfst?
Mit VHDL brauche ich dafür weniger als 20 Zeilen...

(*) in deinem Fall reicht sogar ein 8x8 Bit ROM, denn darin finden 7 
Einer-Segmente Platz und das 1 nötige Zehner-Segment für die "1"

: Bearbeitet durch Moderator
Autor: Vancouver (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
PLD bedeutet Programmable Logic Device und ist ein Oberbegriff für FPGA, 
CPLD, PAL, GAL und was es sonst noch so gibt und gab. Was genau 
verwendest Du denn?

Ich hoffe, Du willst nicht nur aus historischen Gründen bei der 
Schematic-Eingabe bleiben. Wie Lothar schon geschrieben hat, in VHDL 
oder Verilog wären das ein paar Zeilen Code: Eine State-Machine mit 8 
Zuständen und dem bereits fertig dekodierten 7-Segement-Bitvektor als 
Ausgabe.

Autor: Lothar M. (lkmiller) (Moderator) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
1 lesenswert
nicht lesenswert
Vancouver schrieb:
> in VHDL oder Verilog wären das ein paar Zeilen Code: Eine State-Machine
> mit 8 Zuständen und dem bereits fertig dekodierten 7-Segement-Bitvektor
> als Ausgabe.
Ich habe das mal in der Frühstückspause als Fingerübung gemacht. 
Inklusive Simulation. Und noch eine Zeile Reserve bis zu den 
propagierten 20...  ;-)

EDIT: noch einen kleinen Schönheitsfeher bei den Zehnern korrigiert. Da 
wurde statt der Segmente b+c nur das Segment a angesteuert.

: Bearbeitet durch Moderator
Autor: Markus F. (mfro)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
... und wer keine Lust hat, die Primzahlen selber auszurechnen, der kann 
das auch gleich VHDL erledigen lassen:
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity prime_generator is
end entity prime_generator;

architecture rtl of prime_generator is
    function prime(last_prime : integer) return integer is
        variable x, l   : integer;
    begin
        x := last_prime + 1;
        while true loop
            for l in 2 to x loop
                if x rem l = 0 and x /= l then exit; end if;
                if l = x then return l; end if;
            end loop;
            x := x + 1;
        end loop;
        return 3;
    end function prime;

    constant NUM_PRIMES : integer := 100;
    type primes_array is array(0 to NUM_PRIMES - 1) of integer;
    signal primes       : primes_array;
begin
    p_init: process
        variable p  : integer := 3;
    begin
        for i in primes_array'range loop
            report "p(" & integer'image(i) & ")=" & integer'image(p);
            p := prime(p);
            primes(i) <= p;
        end loop;
        wait;
    end process p_init;
end architecture rtl;


Autor: Vancouver (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
OK, in Lines Of Code hat die ROM-Lösung gewonnen :-) Ich bin gerade 
dabei, ein Steuerwerk zu entwickeln und versuche daher alle Probleme der 
Welt mit FSMs lösen.
Aber auf einem FPGA könnte in beiden Fällen das gleiche oder etwas sehr 
Ähnliches herauskommen. Die Transitionsfunktion einer Statemachine ist 
logisch gesehen nichts anderes als ein ROM.

Autor: Lothar M. (lkmiller) (Moderator) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
1 lesenswert
nicht lesenswert
Vancouver schrieb:
> Die Transitionsfunktion einer Statemachine ist logisch gesehen nichts
> anderes als ein ROM.
Gib einem ROM einen Takt und kopple die Ausgänge an den Eingang zurück. 
Fertig, ohne zusätzlichen Zähler... ;-)

EDIT: falsche Datei hochgeladen, die hatte noch ein paar Syntaxfehler. 
Aber dafür habe jetzt noch den RTL-Schaltplan mit dem ROM und den 
Flipflops zugefügt. Der hat allerdings die bekannten Anzeigefehler, so 
dass man die Verbindung vom ROM zu den Zehnersegmenten nicht sieht... 
:-/

: Bearbeitet durch Moderator
Autor: Vancouver (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Here we go :-)

Autor: F. M. (frabi)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
foobar schrieb:
> Nicht so kompliziert. Einfach nen 3-Bit-Zähler und der 7-Segment-Dekoder
> konvertieren 0 nach "2", 1 nach "3", ..., 7 nach "19".

Das wäre tatsächlich auch eine interessante Idee, darüber denke ich 
nochmal nach, danke.

Lothar M. schrieb:
> Darf man fragen, für wen oder was du das so mittelalterlich im Schematic
> machen musst und keine HDL verwenden darfst?

Für die Uni natürlich. Die nur eine einzige richtige Antwort akzetiert, 
wie ich manchmal leider das Gefühl habe. Und dadurch weiß ich leider 
nicht, ob wir den ROM auch zusätzlich benutzen dürfen. Aber ich behalte 
es auf jedem Fall im Hinterkopf.

Lothar M. schrieb:
> Ich habe das mal in der Frühstückspause als Fingerübung gemacht.
> Inklusive Simulation. Und noch eine Zeile Reserve bis zu den
> propagierten 20...  ;-)

Oha, danke. Noch ein Grund mehr, dies im Hinterkopf zu behalten. Nur, 
wie eben schon erwähnt, wahrscheinlich leider nicht erlaubt. Auch wenn 
es so viel simpler wäre.

Auf jeden Fall bedanke ich mich bei euch allen für eure Mühen! :)

Autor: Lothar M. (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
F. M. schrieb:
> Und dadurch weiß ich leider nicht, ob wir den ROM auch zusätzlich
> benutzen dürfen.
Dann schlag halt die klassische Lösung über den Binarzähler mit 
nachgeschalteter such noch vor.
Aber du hast das ROM bezahlt als du das FPGA gekauft hast. Warum 
solltest du es micht nutzen?

Autor: foobar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nen FPGA ist dafür aber schon etwas overkill - das bekommt man in nen 
popeliges 20V10 rein ...

Autor: Harald (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
foobar schrieb:
> Nen FPGA ist dafür aber schon etwas overkill - das bekommt man in nen
> popeliges 20V10 rein ...

Das ist interessant. Kannst du die Gleichungen bitte posten?

Autor: foobar (Gast)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
> Kannst du die Gleichungen bitte posten?

... und deine Hausaufgaben machen? ;-)

Outline:
- Auf 3 Ausgänge nen synchroner 3-bit-Counter, das MSB ist gleichzeitig 
Segment B und C des linken 7-seg-Displays. Zählerstände 0..7 entsprechen 
den Primzahlen 2, 3, 5, 7, 11, 13, 17, 19.

- die restlichen 7 outputs je ein Segment des rechten Displays. Die 
Gleichungen sind das jeweils in der Form:
  ; Segment links oben, an bei cnt==2(entspr 5) und cnt==7(entspr 19)
  SEG_F = /cnt2*cnt1*/cnt0 + cnt2*cnt1*cnt0
  ...

Autor: foobar2 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
foobar schrieb:
> - die restlichen 7 outputs je ein Segment des rechten Displays. Die
> Gleichungen sind das jeweils in der Form:

Richtig. Und wenn man kurz drüber schaut, findet man schnell einige 
triviale Segmente. Das ist alles nicht sonderlich kompliziert und 
aufwendig.

Autor: foobar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, es ist eher ne Fleißaufgabe.

Man bekäme es auch in ein 16V8 rein - ohne Counter, die Segmentausgänge 
selbst sind die States. Left as an exercise for the reader ;-)

Autor: Lothar M. (lkmiller) (Moderator) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Lothar M. schrieb:
> EDIT: falsche Datei hochgeladen
Hoppla, da ging offenbar was mit dem Dateiinhalt schief. Jetzt die 
Richtige...

Autor: Andreas H (heute nur als Gast) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Theor schrieb:
> Hier liegt der besondere Fall vor, dass eine obere Grenze (20)
> festgelegt. In diesem Fall gibt es durchaus einen geschlossenen bzw.
> analytischen Ausdruck für die Folge der Primzahlen.

Mach mich mal schlau.

Sei k \in |N die obere Grenze.

Wie sieht dann der geschlossene Ausdruck für die Folge der Primzahlen < 
k aus?

/regards

Autor: Detlef _. (detlef_a)
Datum:
Angehängte Dateien:

Bewertung
1 lesenswert
nicht lesenswert
>>>>>>>>
Ja, es ist eher ne Fleißaufgabe.
Man bekäme es auch in ein 16V8 rein - ohne Counter, die Segmentausgänge
selbst sind die States. Left as an exercise for the reader ;-)
<<<<

Ja, ist eine Fleißaufgabe. Macht aber Spaß. 7 JK-FlipFlops für die 7 
Segmente, eines für die '1'. Dann läßt man diese 'state-machine' direkt 
die 'Primzahlen' durchzählen, das sind acht Zustände von den 256 
vorhandenen. Hab ich mal gemacht, siehe Anhang. Die Rückkoppellogik ist 
nicht so einfach wie ich dachte, maximal müssen drei Terme aus dem alten 
Zustand verknüpft werden. Man braucht 4 AND Gatter und 3 ORs oder so.

So hamwadat gemacht bevor wir VHDL konnten ;)

Cheers
Detlef

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.

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