Kennt jemand eine FSM Implementierung die Block RAM benutzt?
Im Xilinx User Manual (für den Spartan 3E) steht eine grobe Beschreibung
dazu, aber ich kann mir nicht richtig vorstellen, wie man da die
Zustandsübergänge machen soll.
Das RAM kann als LUT benutzt werden. Hat man ein synchrones RAM, sind
die Register auch gleich inbegriffen. Du hast dann:
RAM-Adresse : Aktueller Zustand & Eingangssignale
RAM-Data : Aktueller Zustand
Die Übergangslogik ist dann direkt der RAM-Inhalt (das RAM wird quasi
als ROM benutzt, das im Betrieb nicht beschrieben/verändert wird
(mögliche Ausnahme: Dynamische Re-Konfiguration der laufenden FSM).
(d.h. der Aktuelle Zustand wird direkt wieder auf die Adresse gelegt,
das Register ist im synchronen RAM)
Das einzige, was nicht im RAM selbst ist, wäre dann die Ausgangslogik,
welche es möglicherweise auch noch braucht.
Beispiel: Mit 16 Zuständen und 4 Eingangssignalen ergäbe dies:
8-bit-Adresse und 4-Bit Daten.
Daniel R. schrieb:> aber ich kann mir nicht richtig vorstellen, wie man da die> Zustandsübergänge machen soll.
Man koppelt die Datenausgänge über die Weiterschaltlogik an die
Adressleitungen an. Oder man koppelt die Eingänge der FSM und die
Datenausgänge an Adressleitungen an. Auf jeden Fall müssen immer
irgendwie die Datenleitungen auf die Adressleitungen zurückgekoppelt
werden.
P. K. schrieb:> RAM-Adresse : Aktueller Zustand & Eingangssignale> RAM-Data : Aktueller Zustand>> (d.h. der Aktuelle Zustand wird direkt wieder auf die Adresse gelegt,> das Register ist im synchronen RAM)
Danke, ich würde es verstehen, wenn "RAM-Data : Folgezustand" wäre:
Bei beispielsweise einer 6-bit Zustandsadresse und zwei Eingangssignalen
(bilden die niedrigsten zwei Bits) würde man einen BRAM-Block mit 8bit
Adressleitung nehmen. Und so könnte man in je nach Eingangsbits
innerhalb von vier Zuständen umschalten (die alle die selbe 6-bit
Adresse haben).
Aber einer von diesen vier Zuständen muss doch eine andere 6-bit Adresse
enthalten. Sonst käme man nie aus dem vier-Zustände-Automaten raus,
oder?
Daniel R. schrieb:> Danke, ich würde es verstehen, wenn "RAM-Data : Folgezustand" wäre:
Da ist noch ein Takt dazwischen: es liegt schon die Bitkombination
(aktueller Zustand + Eingangssignale) für den Folgezustand an den
Adressen an, es wird aber noch nicht der Folgezustand ausgegeben. Dieser
Folgezustand wird erst mit dem nächsten Takt ausgegeben.
RAM Adr(3 downto 0) <= enthaltene Daten(1 downto 0) & input(1 downto 0)
bitfolge_erkannt <= '1' when RAM Adr = "11" else '0'
So hätte man eine SM die Zustand vier erreicht, wenn die Bitfolge 10 01
00 in dieser Reihenfolge eingegeben wird.
Ist das so richtig?
Daniel R. schrieb:> So hätte man eine SM die Zustand vier erreicht
Wenn man mit 1 zu zählen beginnt...
> So hätte man eine SM die Zustand vier erreicht, wenn die Bitfolge 10 01> 00 in dieser Reihenfolge eingegeben wird.
Du hättest auch den Zustand vier erreicht, wenn stattdessen die
Bitfolge 10 00 11 00 01 11 00 eingeben würde...
Sprich: woher kommen die Eingabesignale bzw. wie findet der Wechsel von
10 nach 01 statt? Geht der über 11 oder über 00. Denn das /exakt
gleichzeitig/ beide Bits umschalten ist technisch nicht möglich.
> Ist das so richtig?
Grundlegend: ja. Aber du musst die fraglichen Übergänge noch einmal
genauer anschauen.
> Ist das so richtig?
Ich würde das aber anders codieren, dann liest sich die Tabelle
einfacher, weil jeder Schritt mit den bereits erkannten Bits korreliert:
1
RAM Adr | enthaltene Daten
2
11 00 | 11
3
11 01 | 11
4
11 10 | 10 -- 10 erkannt
5
11 11 | 11
6
10 00 | 10
7
10 01 | 01 -- 10 und 01 erkannt
8
10 10 | 10
9
10 11 | 11 -- fehlerhafter Übergang --> zurück zum Start
10
01 00 | 00
11
01 01 | 01
12
01 10 | 11 -- fehlerhafter Übergang --> zurück zum Start
13
01 11 | 11 -- fehlerhafter Übergang --> zurück zum Start
14
00 00 | 00 -- Sequenz erkannt
15
00 01 | 00
16
00 10 | 00
17
00 11 | 00
Ich habe jetzt angenommen, dass es den Zustand 11 nicht geben darf, und
der wieder zurück zum Start führt.
Lothar Miller schrieb:> Du hättest auch den Zustand vier erreicht, wenn stattdessen die> Bitfolge 10 00 11 00 01 11 00 eingeben würde...
Stimmt ja, bei nicht zur Sequenz gehörenden Eingangswerten muss
natürlich zum Startzustand gesprungen werden.
> Denn das exakt gleichzeitig beide Bits umschalten ist technisch nicht> möglich.
Die an input anliegenden Werte würden dann abgetaktet werden. Die
Zuweisung
> RAM Adr(3 downto 0) <= enthaltene Daten(1 downto 0) & input(1 downto 0)
war nicht als nebenläufige Zuweisung gedacht, sondern sollte nur
verdeutlichen wie die Daten fließen.
>
1
> RAM Adr | enthaltene Daten
2
> 11 00 | 11
3
> 11 01 | 11
4
> 11 10 | 10 -- 10 erkannt
5
> 11 11 | 11
6
> 10 00 | 11 -- hier müsste wohl 11 statt 10 stehen
7
> 10 01 | 01 -- 10 und 01 erkannt
8
> 10 10 | 10
9
> 10 11 | 11 -- fehlerhafter Übergang --> zurück zum
10
> Start
11
> 01 00 | 00
12
> 01 01 | 01
13
> 01 10 | 11 -- fehlerhafter Übergang --> zurück zum
14
> Start
15
> 01 11 | 11 -- fehlerhafter Übergang --> zurück zum
16
> Start
17
> 00 00 | 11 -- Sequenz erkannt
18
> 00 01 | 11 -- nachdem das bitfolge_erkannt-Signal ausgegeben
19
> 00 10 | 11 -- wurde, gehts wieder zum Startzustand um die
20
> 00 11 | 11 -- nächste zu analysieren.
21
>
Diese Darstellung gefällt mir gut.
Mit der Tabelle wollte ich zeigen, warum ich
> RAM-Data : Folgezustand
geschrieben hab. Denn hinter jeder Unter-Adresse dieser vier-Zustände-SM
wird der Folgezustand gespeichert.
Was war denn nun mit
> RAM-Data : Aktueller Zustand
gemeint?
Die Frage ist, wie man eine solche FSM codieren / beschreiben möchte. Im
Grunde ist das Ganze ja nichts anderes, als ein ROM-Computer, wie man
ihn in den Anfangszeiten entwickelt hat und wie er auch den Lerninhalten
der Hochschule entspricht. Damals hat man sich die state machine
funktionell überlegt, mit binären Codes versetzt und es dann per Hand
optimiert - kann mich noch gut errinern.
Inzwischen sind wir aber etwas weiter und können die FSM abstrakt
funktionell beschreiben und es dem Tool überlassen, sie zu codieren
(Sobald man mit dynamischen states und/oder Redundanz arbeitet, wird das
unerlässlich).
Die so optimierte Codierung sieht dann auch bei kleinen Änderungen
mitunter immer wieder deutlich anders aus und wird beim automatischen
Verschieben von slices ins RAM auch nochmal ganz anders gemappt. Man
darf ja nicht vergessen, dass bei high speed Anwendungen ein timing
getriebenes placing erfolgt und die selbstgewählte Reihenfolge der
states im RAM nicht automatisch optimal ist.
Block RAMs verwende ich bei FSMs ausdrücklich nicht mehr, bzw nur bei
virtuelllen state machines, die aus Codes im Blockram gesteuert werden,
also eine Art mini-Alu darstellen.
Jürgen Schuhmacher schrieb:> Die so optimierte Codierung sieht dann auch bei kleinen Änderungen> mitunter immer wieder deutlich anders aus
Danke;) Ich denke auch, dass die Place&Route Tools sehr mächtig bzgl.
effizienter Platzierung etc. sind. Deshalb halte ich es auch für besser
die Zustände auf höchster Ebene zu definieren (Typerstellung in VHDL)
und sich nicht um die Low-Level-Implementierung, die daraus entsteht zu
kümmern. Abgesehen von der Auswahl des FSM-Typs (One-Hot etc.).
Die Absicht hinter der Überlegung BRAM zu benutzen kam daher, dass ich
Hardwarekosten sparen wollte. Es würde ja auch sparen, nur erkauft man
das durch eine höhere Komplexität auf Programmiererseite, schlechtere
Portierbarkeit und eben die ineffiziente Räumliche Positionierung.
