Wie viele States sollte ein FSM haben?

Andreas S. schrieb:

> Wie schon von Oliver angedeutet, sollte jede FSM exakt 42 Zustände
> aufweisen.

Du musst den Grund für die Zahl 42 nennen:

https://www.youtube.com/watch?v=ASoz_NuIvP0

Pepe schrieb:
zusammenkommen.
>
> Jetzt frage ich mich, wie viele States denn eine FSM haben sollte?

bei FPGA#s mit 4-LUT höchsten 16; bei denen mit 6 höchtens 64. Das gilt 
nur wenn binarye state encoding wählbar ist.

@Markus
Wenn schon, dann bin ich für 42. ;-)

@Fred
Und was passiert, wenn ich bei einer 4-LUT mehr States einbaue?
Was wird dann (intern) draus gemacht? Weil lauffähig ist die FSM ja dann 
trotzdem.

Pepe schrieb:
> Jetzt frage ich mich, wie viele States denn eine FSM haben sollte?

Da gibt es so keine Regel. Im Grunde ist ein Counter ja auch eine FSM.

Wenn ich n Werte von einem FIFO auslesen müsste, würde ich nicht n 
States dafür schreiben, sondern in einem State sowas wie:

1

case state is

2

    when ... => 

3

       fifo_entries <= 5;

4

       state <= READ_FIFO;

5

6

    when READ_FIFO =>

7

       if fifo_ptr < fifo_entries then

8

           frame(some_range_calculation) <= fifo(fifo_ptr);

9

           fifo_ptr <= fifo_ptr + 1;

10

       else

11

           fifo_ptr <= 0;

12

           state <= next_state;

13

       end if;

14

15

    when ... => ...

@Matyas
Das Auslesen in den Fifo ist nicht mein Thema. Das ist ohne FSM 
realisiert.

Sondern ich habe verschiedene Werte, die zwischen 2-3 Words lang sind 
und aus unterschiedlichen "Quellen" stammen. Und diese Werte möchte ich 
in einen gesamten Frame zusammensetzen und in einen FiFo eintragen.
Und für das Mergen des Frames hätte ich gerne eine FSM eingesetzt.

Pepe schrieb:
> Und diese Werte möchte ich
> in einen gesamten Frame zusammensetzen und in einen FiFo eintragen.
> Und für das Mergen des Frames hätte ich gerne eine FSM eingesetzt.

Was meinst Du damit?

Wenn die werte von Asynchron irgendwo unabhängig reinkommen, dann 
braucht es keine FSM.

Wenn die Werte nacheinander in einen Frame geschrieben werden, dann 
braucht es keine FSM.

Wenn die Werte nacheinander in einer festen Folge reinkommen, und nach 
jedem reinkommen was anderes gemacht werden muss, dann vielleicht, aber 
dazu fehlt mir jede Info zu Deinem Problem.

Grundsätzlich werte ich in Echtzeit das Bild einer Zeilenkamera aus.
D.h. es läuft eine Kantenerkennung gleich im FPGA und ich gebe die 
Koordinaten der Kanten für einige Messbereiche aus. Zusätzlich werden 
noch Positionen von Encodern in den Frame eingetragen.
Der Frame mit den Ergebnissen soll synchron zur Kamera ausgegeben 
werden.

Leider kann es vorkommen, dass "Kante#1" auch mal NACH "Kante#2" kommt, 
weil sich die Polarität der Helligkeiten im Bild ändern kann (SW <> WS).

Pepe schrieb:
> @Fred
> Und was passiert, wenn ich bei einer 4-LUT mehr States einbaue?

Der kritische Pfad wird um einen Chiplevel länger was dazu führt, das 
man die FSM und damit den FPGA nicht so schnell takten kann.

Pepe schrieb:
> Und für das Mergen des Frames hätte ich gerne eine FSM eingesetzt.

Wie wäre es mit einem Bitfield?
Wenn es 15-20 Objekte sind langt eine 32 bit Wert, jedes Objekt bekommt 
1 bit und es lassen sich wunderbar und einfach Prüfungen durchführen.

Pepe schrieb:
> Sondern ich habe verschiedene Werte, die zwischen 2-3 Words lang sind
> und aus unterschiedlichen "Quellen" stammen.

Und wie sehen diese Quellen aus?

Ich versuche häufig mir einen Datentyp/LUT zu bauen, der mir die 
Beschreibung vereinfacht.

Wenn jede Quelle die Werte in einen Datentyp* schreibt, könnte man da 
auch einfach drüber iterieren.

* zB:

1

type t_quelle_entry is record

2

    byte_buffer(range) : t_byte;

3

    used_entries       : natural in range xy;

4

end record;

5

6

type t_quellen is array(range_nr_quellen) of t_quelle_entry;

7

8

signal quellen : t_quellen;

9

...

10

11

case state is

12

    when READ_FRAME_FROM_SOURCES => 

13

       if quell_ptr < NR_QUELLEN then

14

           if byte_ptr < quellen(quell_ptr).used_entries then

15

               frame(some_range_calculation) <= quellen(quell_ptr).byte_buffer(byte_ptr);

16

               byte_ptr <= byte_ptr + 1;

17

               total_nr_of_bytes <= total_nr_of_bytes + 1;

18

           else

19

               byte_ptr <= 0;

20

               quell_ptr <= quell_ptr + 1;

21

           end if;

22

       else

23

           quell_ptr <= 0;

24

           state <= WRITE_FIFO;

25

       end if;

26

27

    when WRITE_FIFO =>

28

       if quell_ptr < total_nr_of_bytes then

29

           fifo(quell_ptr) <= frame(quell_ptr);

30

           quell_ptr <= quell_ptr + 1;

31

       else

32

           quell_ptr <= 0;

33

           total_nr_of_bytes <= 0;

34

           state <= next_state;

35

       end if;

36

37

    when ... => ...

Edit: Vll zu spät, war Mittagspause...

@Matyas
Klingt gut. Macht es auf jeden Fall einfacher.

51 wie die USA.

Aber mal eine ernste Frage: Sollten es immer 2^n States sein? Das wird 
ja intern als binäre Zahl gebaut, wenn man jetzt 7 Zustände hat bleibt 
ein Wert unbelegt aus 2^3. Kann es passieren, dass die Statemachine in 
diesen Zustand spring obwohl er nirgends verwendet wird?

-gb- schrieb:
> Kann es passieren, dass die Statemachine in
> diesen Zustand spring obwohl er nirgends verwendet wird?

Ja, beispielsweise bei einem SEU.

-gb- schrieb:
> Sollten es immer 2^n States sein? Das wird
> ja intern als binäre Zahl gebaut, wenn man jetzt 7 Zustände hat bleibt
> ein Wert unbelegt aus 2^3.

Quartus verwendet normalerweise one-hot Kodierung, d.h. pro State ein 
Flipflop (bzw -1, alle FF=0 ist ein weiterer State). Hat vermutlich 
Vorteile für die Überführungs- und Ausgabenetze.

K.A. wie Xilinx das handhabt.

Matyas schrieb:
> -gb- schrieb:
>> Kann es passieren, dass die Statemachine in
>> diesen Zustand spring obwohl er nirgends verwendet wird?
>
> Ja, beispielsweise bei einem SEU.

Per Synthesizer Pragma kann man erzwingen, dass für nicht verwendete 
aber mögliche Zustände eine Resetlogik generiert wird. Wird z. B. von 
den mir bekannten Safety Normen jeweils so verlangt.

Das erhöht den Ressourcenverbrauch etwas und verlangsamt die FSM, darum 
wird das per default nicht gemacht.

Burkhard K. schrieb:
>> Aber mal eine ernste Frage: Sollten es immer 2^n States sein?
>
> Nö - wieso denn?

Komplettes ausdecodieren aller möglichen Zustände damit die FSM nicht 
festhängt.

Kann man auch anders erreichen ('when others').
Aber man sollte sich schon mal drüber nachdenken wie die Zustände der 
FSM realisiert werden und wie sich die FSM verhält wenn mal eine 
FSM-Zustand eintritt (beispielsweise durch unbeabsichtigtes 
"Übertakten") der so nicht vorgesehen war.

FSM = Fliegendes Spaghetti Monster (gemäss Wikipedia)

C. A. Rotwang schrieb:
> Burkhard K. schrieb:
>>> Aber mal eine ernste Frage: Sollten es immer 2^n States sein?
>>
>> Nö - wieso denn?
>
> Komplettes ausdecodieren aller möglichen Zustände damit die FSM nicht
> festhängt.

Geht theoretisch ist aber schwierig zu erreichen, wenn der Synthesizer 
freie Hand hat bei der Wahl der FSM codierung.

Tönt auch eher nach Verilog Stil, wo es keinen Enumerationstyp gibt und 
FSM dann mit Bitvektoren beschrieben werden, die dann der Synthesizer 
wieder komplett anders implementiert.

> Kann man auch anders erreichen ('when others').

Synthesizer ignorieren den 'when others' Pfad (kann ich definitiv 
bestätigen für Synplify). Ist auch so dokumentiert bzw. wird als Warnung 
ausgegeben.

Um das gewünschte Ziel zu erreichen, stehen die schon weiter oben 
erwähnten Pragmas zur Verfügung.

Christophz schrieb:
> Synthesizer ignorieren den 'when others' Pfad (kann ich definitiv
> bestätigen für Synplify). Ist auch so dokumentiert bzw. wird als Warnung
> ausgegeben.
>
> Um das gewünschte Ziel zu erreichen, stehen die schon weiter oben
> erwähnten Pragmas zur Verfügung.

Ja stimmt, wenn der 'when others state' als nicht erreichbar erkannt 
wird und keine Attribute für die Synthese gesetzt sind.

Ich habe auch schon gesehen, dass der 'when others state' im Reset 
gesetzt wird, um die Erreichbarkeit der Synthese zu zeigen.