Mikrocontroller.net - Benutzerbeiträge [de]

Statemachine

2020-02-16T15:23:49Z

Nobodyy: /* Geschwindigkeitsvergleich */

==Einleitung==

Bei einem sogenannten [http://de.wikipedia.org/wiki/Finite_State_Machine Endlichen Zustandsautomaten] (engl. '''f'''inite '''s'''tate '''m'''achine, kurz FSM) handelt es sich um die Realisation eines Steuerungskonzeptes, welches eine abstrahierte Maschine zum Vorbild hat, die eine Reihe von Zuständen besitzt, durch die sich ihr Betriebsablauf definiert. Diese Maschine arbeitet, indem sie von einem Zustand in einen anderen Zustand übergeht und bei derartigen Zustandsübergängen und im Verharren von Zuständen bestimmte Aktionen ausführt. Dabei ergibt sich der Folgezustand aus dem momentanen Zustand und einem externen Ereignis, z. B. einem Tastendruck. Dabei ist die Maschine in verschiedenen Zuständen für ganz bestimmte Ereignisse sensibel.

Die FSM selbst wird fast immer in irgendeiner Weise über einen Takt angetrieben, kann also nicht in beliebig kurzen Zeitspannen auf Ereignisse reagieren und Zustände wechseln. In jedem Takt wird anhand des vorliegenden Zustands und dem Status der Eingabekanäle entschieden, welcher Zustand als nächstes vorliegen soll und welche Aktionen auszuführen sind.

Abstrahierte Formen dieser Maschine werden in vielen elektronischen Geräten eingesetzt, um Bedieneraktivitäten und andere Ereignisse im System zu verarbeiten und autark ablaufende Prozesse geeignet zu beeinflussen. Entsprechend formulierte FSMs können sowohl in Software als auch Hardware aufgebaut werden.

Die Beschreibung einer FSM ist auf mehrere Arten möglich. Zum einen kann sie in Form einer Tabelle beschrieben werden, aber auch eine graphische Darstellung der Zustände und deren Abhängigkeiten in Form eines Zustandsdiagramms ist möglich.

==Darstellung von Zustandsautomaten==

Zustandsautomaten haben den großen Charme, dass es meistens leicht möglich ist, ihre Funktion durch eine Grafik zu veranschaulichen.

Beispiel: Es ist eine FSM zu entwerfen, die eine Rollosteuerung übernimmt. Es gibt einen Motor, der sich in 3 Zuständen befinden kann: stop, rauf drehend, runter drehend. Außerdem gibt es Endschalter, welche betätigt werden, wenn das Rollo die jeweilige Endposition erreicht hat. Und es gibt 2 Taster "Up" und "Down" durch welche der Benutzer den Bewegungswunsch an die FSM weitergibt. Irgendwie weiß jeder, wie so eine Rollosteuerung funktioniert, und so recht und schlecht kann das auch jeder in der einen oder anderen Form beschreiben. Aber kann man das ganze auch so 'beschreiben', dass man im Vorfeld, vor der Programmierung tatsächlich alle Eventualitäten erfasst und so darstellt, dass auch ein Nicht-Informatiker die Funktionsweise versteht? Genau an dieser Stelle kommt die graphische Darstellung ins Spiel.

Wie sieht nun eine derartige FSM aus? Jede Wolke im Bild sei ein Zustand, dem man einen Namen gibt. Die Pfeile zwischen den Wolken zeigen die Zustandsübergänge an, wobei am Pfeil vermerkt ist, unter welcher Bedingung dieser Übergang genommen werden kann (in Rot) und welche Aktionen dabei auszuführen sind (in Blau).

[[Datei:StateRollo.jpg|center|framed|Zustandsautomat für eine Rollosteuerung]]

Aus der Zeichnung ist ablesbar:
Befindet sich die Maschine im Zustand "unten" und wird die Taste "Up" gedrückt, dann folgt als Aktion, daß der Motor auf "rauf drehend" gestellt wird und gleichzeitig wechselt die Maschine in den Zustand "nach oben". In diesem Zustand verbleibt die Maschine, während der Motor immer weiter dreht, bis der Endschalter meldet, dass das Rollo oben angekommen ist. Dies ist eine Möglichkeit wie die Maschine den Zustand "nach oben" verlassen kann. In diesem Fall wird dann der Motor abgeschaltet und die Maschine wechselt in den Zustand "oben".

Man sieht hier schon, dass es mit so einer Grafik relativ einfach ist, sich von der korrekten Logik zu überzeugen. In einfachsten Fall legt man zur Simulation einfach einen Gegenstand in die betreffende Wolke, die den gerade aktiven Zustand symbolisiert. Danach geht man alle Möglichkeiten durch, wie diese Maschine von aussen (Taster, Schalter, etc) beeinflusst werden kann und sieht sich an, ob es dafür in der Grafik einen Pfeil gibt, der von der aktiven Wolke wegführt. Gibt es keinen, dann passiert auch nichts. Gibt es einen, dann verschiebt man den Gegenstand in die betreffende Wolke und führt (in Gedanken) die Aktion aus. Auf die Art kann man ganz leicht einige typische Benutzerszenarien durchspielen aber auch ausprobieren, ob man alle Eventualitäten berücksichtigt hat. Denn gerade diese Evantualitäten, an die man am Anfang gar nicht denkt, die sind es, die einem in weiterer Folge oft Probleme bereiten.

Um bei der Rollosteuerung zu bleiben: Was soll denn passieren, wenn das Rollo gerade hochfährt und der Benutzer ein weiteres mal auf "Up" drückt? Oder wenn er auf "Down" drückt? In der Grafik ist ersichtlich, wie in diesem Fall zu verfahren ist. (Und Hand aufs Herz: Hätten Sie daran gedacht, dass diese Fälle zu berücksichtigen sind, als sie 'Rollosteuerung' gelesen haben?)

==Implementierungsvariationen==

Der konkrete softwaremässige Aufbau einer FSM kann in weiten Grenzen variieren. Das grundlegende Konzept, Aktionen an Zustände zu knüpfen und logische Abläufe an die Abfolge von Zuständen zu binden, bleibt dabei in allen Fällen erhalten. Aber je nach Lust und Laune und dem Können des Programmierers gibt es viele unterschiedliche Möglichkeiten eine FSM zu implementieren. Ziel ist es dabei immer, die eigentliche Maschine, also das was in der Zustandstabelle ausgedrückt wird, so einfach und überschaubar wie möglich zu präsentieren. Sie implementiert die Logik und definiert was die Maschine eigentlich macht und warum sie es macht. Ein einfacher Ansatz ist die Verwendung des C-Konstukts switch, in der in jedem case-zweig die einzelnen Zustände kodiert werden. Es ist aber auch durchaus möglich eine universelle FSM zu bauen, bei denen eine generische Funktion die Tabelle in Arrayform bekommt und zusammen mit einigen globalen Variablen die Maschine implementiert. Oft wird auch eine Statemaschine dadurch gebaut, indem das zentrale switch-case Konstukt der Sprache [C] durch einen einzelnen [[Funktionszeiger in C | Funktionszeiger]] ersetzt wird und jeder Zustand nichts anderes als eine Funktion ist. Der Übergang von einem Zustand in einen anderen Zustand ist dann nichts anderes als das Zuweisen einer Funktion an diesen Funktionszeiger. Oder aber man kombiniert Tabelle und Funktionszeiger in ein gemeinsames Konzept.

==Grundlegender Aufbau==

Im Folgenden wird eine FSM in Software verwirklicht, welche die Ampelsteuerung einer Kreuzung übernimmt.
[[Bild:Statemachine_Kreuzung.png|center|framed|Ampeln an einer Kreuzung]]

Die Abfolge der Lichtzeichen einer einzelnen Ampel ist dabei
 [[Bild:Statemachine_Ampel.png|center|framed|Zustände einer einzelnen Ampel]]

Die komplette Lichtfolge aller Ampeln in der Kreuzung stellt sich dann wie folgt dar: Es ist dabei ausreichend, nur Ampel 1 und Ampel 2 zu betrachten, da Ampel 3 bzw. Ampel 4 die jeweils gleichen Lichtsignale anzeigen. Dies muss nicht immer so sein! Auf einer Kreuzung kann es durchaus für eine Fahrtrichtung Zusatzampeln geben, die die Lichtfolge der Hauptampel modifizieren.

<center>
{| {{Tabelle|min-width:20em;text-align:center;}}
|+ '''Zustandstabelle der Ampelanlage'''
|- style="background-color:#ffddcc"
!width="20%"| Zustand ||width="20%"| Ampel 1 ||width="20%"| Ampel 2 ||width="20%"| nächster Zustand
|-
| 1 || rot || grün || 2
|-
| 2 || rot || gelb || 3
|-
| 3 || rot || rot || 4
|-
| 4 || rot/gelb || rot || 5
|-
| 5 || grün || rot || 6
|-
| 6 || gelb || rot || 7
|-
| 7 || rot || rot || 8
|-
| 8 || rot || rot/gelb || 1
|-
|}
</center>

Die Zustandsnummer ist in diesem Fall einfach die Taktung der FSM. Verfolgt man die Zustände von einem Zustand zum nächsten, dann kann man sich sehr leicht davon überzeugen, daß die Lichtfolge der beiden Ampeln tatsächlich der gewünschten Abfolge entspricht.

Hat man die Funktionalität einer FSM erst mal soweit in Tabellenform festgelegt, dann ist es sehr einfach daraus ein Programm in einer Programmiersprache wie z.B. C abzuleiten, welches diese Statemachine implementiert.

Kochrezeptartig kann man dabei folgenden Aufbau vornehmen:
* Es gibt eine globale Variable, die den aktuellen Zustand der Maschine repräsentiert. Die Zustände wurden in obiger Tabelle bereits durchnummeriert, so dass es sich anbietet, Zustände innerhalb der Maschine durch ebendiese Zahlen darzustellen.
* Die FSM wird als Funktion implementiert, die für jeden einzelnen Takt aufgerufen wird.
* Jeder Zustand wird innerhalb der Funktion durch einen case innerhalb einer switch Anweisung dargestellt.
* Jeder Zustand kann vor verlassen der Funktion den aktuellen Zustand der FSM beim nächsten Aufruf der Funktion festlegen, indem er an die globale Variable die Nummer des nächsten Zustands zuweist.
* Jegliche Form von Warteschleifen innerhalb der FSM sind verboten. Wenn die FSM auf ein Ereignis warten müsste, dann ist dafür ein eigener Zustand vorzusehen, der auf das Eintreten des Ereignisses prüft und nur dann den nächsten Zustand auswählt, wenn das Ereignis tatsächlich eingetreten ist. Damit erreicht man [[Multitasking]].
* Es ist sinnvoll, den Ampelfarben Namen in Form eines #define oder enums zu geben, damit wird das Konstrukt deutlich leichter lesbar.

<syntaxhighlight lang="c">
#define ROT 1
#define ROT_GELB 2
#define GRUEN 3
#define GELB 4

void Ampel1( unsigned char Farbe ); // schaltet Ampel1 auf eine Farbe
void Ampel2( unsigned char Farbe ); // schaltet Ampel2 auf eine Farbe

unsigned char state = 1; // globale Variable, die den Status repräsentiert

void stateMachine()
{
switch( state ) {
case 1:
Ampel1( ROT );
Ampel2( GRUEN );
state = 2;
break;

case 2:
Ampel1( ROT );
Ampel2( GELB );
state = 3;
break;

case 3:
Ampel1( ROT );
Ampel2( ROT );
state = 4;
break;

case 4:
Ampel1( ROT_GELB );
Ampel2( ROT );
state = 5;
break;

case 5:
Ampel1( GRUEN );
Ampel2( ROT );
state = 6;
break;

case 6:
Ampel1( GELB );
Ampel2( ROT );
state = 7;
break;

case 7:
Ampel1( ROT );
Ampel2( ROT );
state = 8;
break;

case 8:
Ampel1( ROT );
Ampel2( ROT_GELB );
state = 1;
break;
}
}

int main()
{
....

while( 1 ) {
stateMachine();
delay_ms( 1000 );
}
}
</syntaxhighlight>

Wird diese Funktion im Sekundentakt aufgerufen, so werden die Funktionen Ampel1() bzw. Ampel2() mit der jeweils richtigen Lichtstellung in der richtigen Reihenfolge aufgerufen um die Lichtwechsel der Ampeln einer Kreuzung zu realisieren. Der Einfachheit halber wird in diesem Beispiel die Funktion delay_ms() verwendet. Praktisch wird man in den meisten Fällen besser einen [[Timer]] benutzen, um die Statemachine periodisch aufzurufen. Wie das geht und was das für Vorteile hat ist im Artikel [[Multitasking#Verbesserter Ansatz mit Timer | Multitasking]] beschrieben.

==Reaktionen auf äußere Ereignisse==

Obige Statemaschine ist noch sehr primitiv. Angenommen an dieser Ampelkreuzung gibt es eine Induktionsschleife. Diese sei derartig geschaltet, dass die Hauptrichtung über Ampel2/Ampel4 ständig Grün zeigt und nur bei Annäherung eines Fahrzeugs auf der Strecke Ampel1/Ampel3 wird ein Lichtwechselzyklus durchgeführt, um diesem Fahrzeug die geordnete Durchfahrt zu ermöglichen. Die Statemaschine muss daher auf ein äußeres Ereignis reagieren können. Der Übergang von Zustand 1 in Zustand 2 ist von diesem Ereignis abhängig. Nur wenn es auftritt wird dieser Übergang durchgeführt, ansonsten verbleibt die Maschine im Zustand 1. Die Beschreibung der FSM wird also um einen weiteren Tabelleneintrag ergänzt, in dem festgehalten wird, wie mit dem zusätzlichen Eingang verfahren werden soll. In dieserm erweiterten Beispiel sollen die Zustände mit einem aussagekräftigen Namen versehen werden, denn Menschen sind sehr schlecht im Umgang mit abstrakten Zahlen, sie sind viel besser mit Wörtern vertraut. Die x in der Tabellenspalte "Induktionsschleife" besagen, daß dieses Eingangsignal für die Entscheidungen der Statemaschine keine Rolle spielt (engl. don't care).

<center>
{| {{Tabelle|min-width:20em;text-align:center;}}
|+ '''Zustandstabelle der Ampelanlage mit zusätzlichem Eingang'''
|- style="background-color:#ffddcc"
!| Zustand ||| Name ||| Ampel 1 || | Ampel 2 || Induktionsschleife || | nächster Zustand
|-
| 1 || OSTWEST_GRUEN || rot || grün || ==1 ? || 2
|-
| 2 || OSTWEST_GELB || rot || gelb || x ||3
|-
| 3 || ALLE_ROT_1 || rot || rot || x || 4
|-
| 4 || NORDSUED_ROTGELB ||rot/gelb || rot || x || 5
|-
| 5 || NORDSUED_GRUEN || grün || rot || x || 6
|-
| 6 || NORDSUED_GELB || gelb || rot || x || 7
|-
| 7 || ALLE_ROT_2 || rot || rot || x || 8
|-
| 8 || OSTWEST_ROTGELB || rot || rot/gelb || x || 1
|-
|}
</center>

<syntaxhighlight lang="c">
#define ROT 1
#define ROT_GELB 2
#define GRUEN 3
#define GELB 4

void Ampel1( unsigned char Farbe ); // schaltet Ampel1 auf eine Farbe
void Ampel2( unsigned char Farbe ); // schaltet Ampel2 auf eine Farbe
unsigned char Induktionsschleife(); // fragt die Induktionsschleife ab
typedef enum { NORDSUED_ROTGELB, NORDSUED_GRUEN, NORDSUED_GELB, ALLE_ROT_1,
OSTWEST_ROTGELB, OSTWEST_GRUEN, OSTWEST_GELB, ALLE_ROT_2} state_t ;

state_t state = ALLE_ROT_1;

void stateMachine()
{
switch( state ) {
case OSTWEST_GRUEN:
Ampel1( ROT );
Ampel2( GRUEN );
if( Induktionsschleife() ) {
state = OSTWEST_GELB;
}
break;

case OSTWEST_GELB:
Ampel1( ROT );
Ampel2( GELB );
state = ALLE_ROT_1;
break;

case ALLE_ROT_1:
Ampel1( ROT );
Ampel2( ROT );
state = NORDSUED_ROTGELB;
break;

case NORDSUED_ROTGELB:
Ampel1( ROT_GELB );
Ampel2( ROT );
state = NORDSUED_GRUEN;
break;

case NORDSUED_GRUEN:
Ampel1( GRUEN );
Ampel2( ROT );
state = NORDSUED_GELB;
break;

case NORDSUED_GELB:
Ampel1( GELB );
Ampel2( ROT );
state = ALLES_ROT_2;
break;

case ALLES_ROT_2:
Ampel1( ROT );
Ampel2( ROT );
state = OSTWEST_ROTGELB;
break;

case OSTWEST_ROTGELB:
Ampel1( ROT );
Ampel2( ROT_GELB );
state = OSTWEST_GRUEN;
break;
}
}
</syntaxhighlight>

==Warteschleifen==

Das Warten auf ein äußeres Ereignis kann mit dem Verzweigen oder auch nicht Verzweigen in einen anderen Zustand realisiert werden. In obiger Statemaschine soll z.B. die Grünphase der Ampel1 von einem Takt auf 5 Takte angehoben werden. Grundfalsch wäre es, dies jetzt mit einer while-Schleife im Zustand 5 zu realisieren. Warten wird immer über zusätzliche Zustände realisiert. Eine Statemaschine darf innerhalb eines Zustands niemals auf etwas warten, sondern muss so schnell als möglich die Kontrolle wieder abgeben. Geht man naiv an die Sache ran, dann könnte man die 5 Takte über die Einführung von zusätzlichen Zuständen leicht erreichen.

<center>
{| {{Tabelle|min-width:20em;text-align:center;}}
|+ '''Zustandstabelle der Ampelanlage mit zusätzlichem Eingang'''
|- style="background-color:#ffddcc"
!width="20%"| Zustand ||width="20%"| Ampel 1 ||width="20%"| Ampel 2 ||width="20%"| Induktionsschleife ||width="20%"| nächster Zustand
|-
| 1 || rot || grün || ==1? || 2
|-
| 2 || rot || gelb || x ||3
|-
| 3 || rot || rot || x || 4
|-
| 4 || rot/gelb || rot || x || 5
|-
| 5 || grün || rot || x || 9
|-
| 6 || gelb || rot || x || 7
|-
| 7 || rot || rot || x || 8
|-
| 8 || rot || rot/gelb || x || 1
|-
| 9 || grün || rot || x || 10
|-
| 10 || grün || rot || x || 11
|-
| 11 || grün || rot || x || 12
|-
| 12 || grün || rot || x || 6
|-
|}
</center>

Daß ein derartiges Vorgehen bei längeren Wartezeiten oder gar bei berechneter Wartezeitdauer nicht praktikabel ist, dürfte auf der Hand liegen. Besser ist daher die Einführung eines internen Zählers sowie nur eines einzigen, neuen Wartezustands. Beginnt die Wartezeit wird der Zähler auf einen Wert entsprechend der Wartezeit gestellt. Im neuen Zustand wird der Zähler um 1 verringert und nur dann, wenn der Zähler 0 erreicht hat, wird in den ursprünglichen Folgezustand gewechselt. Der Zähler kann also in ähnlicher Form wie die Induktionsschleife als Ereignislieferant aufgefasst werden.

<center>
{| {{Tabelle|min-width:15em;text-align:center;}}
|+ '''Zustandstabelle der Ampelanlage mit zusätzlichem Eingang'''
|- style="background-color:#ffddcc"
!width="10%"| Zustand ||width="10%"| Ampel 1 ||width="10%"| Ampel 2 ||width="10%"| Induktionsschleife ||width="10%"| Wartezeit ||width="10%"| nächster Zustand
|-
| 1 || rot || grün || ==1 ? || x || 2
|-
| 2 || rot || gelb || x || x || 3
|-
| 3 || rot || rot || x || x || 4
|-
| 4 || rot/gelb || rot || x || x || 5
|-
| 5 || grün || rot || x || =4 || 9
|-
| 6 || gelb || rot || x || x || 7
|-
| 7 || rot || rot || x || x || 8
|-
| 8 || rot || rot/gelb || x || x || 1
|-
| 9 || x || x || x || dec / ==0 ? || 6
|-
|}
</center>

<syntaxhighlight lang="c">
#define ROT 1
#define ROT_GELB 2
#define GRUEN 3
#define GELB 4

void Ampel1( unsigned char Farbe ); // schaltet Ampel1 auf eine Farbe
void Ampel2( unsigned char Farbe ); // schaltet Ampel2 auf eine Farbe
unsigned char Induktionsschleife(); // fragt die Induktionsschleife ab
typedef enum { NORDSUED_ROTGELB, NORDSUED_GRUEN, NORDSUED_GELB,
ALLE_ROT_1,
OSTWEST_ROTGELB, OSTWEST_GRUEN, OSTWEST_GELB,
ALLE_ROT_2, WARTE_NORDSUED} state_t;

state_t state = ALLE_ROT_1;
unsigned char zaehler;

void stateMachine()
{
switch( state ) {
case OSTWEST_GRUEN:
Ampel1( ROT );
Ampel2( GRUEN );
if( Induktionsschleife() ) {
state = OSTWEST_GELB;
}
break;

case OSTWEST_GELB:
Ampel1( ROT );
Ampel2( GELB );
state = ALLES_ROT_1;
break;

case ALLES_ROT_1:
Ampel1( ROT );
Ampel2( ROT );
state = NORDSUED_ROTGELB;
break;

case NORDSUED_ROTGELB:
Ampel1( ROT_GELB );
Ampel2( ROT );
state = NORDSUED_GRUEN;
break;

case NORDSUED_GRUEN:
Ampel1( GRUEN );
Ampel2( ROT );
zaehler = 4;
state = WARTE_NORDSUED;
break;

case NORDSUED_GELB:
Ampel1( GELB );
Ampel2( ROT );
state = ALLES_ROT_2;
break;

case ALLES_ROT_2:
Ampel1( ROT );
Ampel2( ROT );
state = OSTWEST_ROTGELB;
break;

case OSTWEST_ROTGELB:
Ampel1( ROT );
Ampel2( ROT_GELB );
state = OSTWEST_GRUEN;
break;

case WARTE_NORDSUED:
zaehler = zaehler - 1;
if( zaehler == 0 )
state = NORDSUED_GELB;
break;
}
}
</syntaxhighlight>

== Umsetzung in Tabellenform ==

Im letzten Beispiel wollen wir die Ampelsteuerung noch etwas realistischer gestalten. Denn die einzelnen Phasen sind unterschiedlich lang, der Zustand Gelb ist deutlich kürzer als der Zustand Grün. Wenn wir also in fast jedem Zustand eine bestimmte Anzahl Takte warten wollen, erscheint es nicht sinnvoll, dafür jedesmal einen neuen Zustand anzuspringen. Sinnvoller ist die Integration des Wartens direkt in den Zustand, so wie im vorherigen Beispiel der Zustand "WARTE_NORDSUED". Dabei fallen jedoch zwei Sachen auf.

* In jedem Zustand muss die Wartezeit des ''nächsten'' Zustands zugewiesen werden. Das ist etwas verwirrend.
* Fast alle Anweisungen sind gleich in den Zuständen, nur die Zahlen und der Wert für den nächsten Zustand ändern sich.

Darum soll hier die FSM von einer großen switch Anweisung auf eine Tabelle geändert werden. Das hat den Vorteil, dass die Zustandstabelle nahezu 1:1 in den Quelltext geschrieben werden kann und sie so sehr kompakt und übersichtlich ist. Die eigentliche FSM wird sehr klein und arbeitet sich durch die Tabelle durch. Zur weiteren Verbesserung der Lesbarkeit (siehe [[Strukturierte Programmierung auf Mikrocontrollern]]) nutzen wir einen Struct, welche den Zustand der State machine mit sinnvollen Variablennamen beschreibt. Bei dieser Methode muss man beachten, dass die Reihenfolge der Zustände in der enum Definition gleich sein muss mit der Reihenfolge der Zustände in der Tabelle, sonst funktioniert es nicht.

<syntaxhighlight lang="c">
#define ROT 1
#define GRUEN 2
#define GELB 4
#define ROTGELB 5

void Ampel1( unsigned char Farbe ); // schaltet Ampel1 auf eine Farbe
void Ampel2( unsigned char Farbe ); // schaltet Ampel2 auf eine Farbe
int Induktionsschleife(); // fragt die Induktionsschleife ab

typedef enum { OSTWEST_GRUEN=0, OSTWEST_GELB, ALLE_ROT_1,
NORDSUED_ROTGELB, NORDSUED_GRUEN, NORDSUED_GELB, ALLE_ROT_2,
OSTWEST_ROTGELB } state_t;

typedef struct {
int Ampel1;
int Ampel2;
int I_Schleife;
int Wartezeit;
int Naechster;
} ampel_state_t;

state_t state = ALLE_ROT_1;
int zaehler=1;

// Tabelle fuer state machine

ampel_state_t state_table[8] = {

// AMPEL1 AMPEL2 Induktionsschleife ?
// | | | Wartezeit in s
// | | | |
// | | | | naechster Zustand Name
//----------------------------------------------------------------------
{ROT , GRUEN , 1, 10, OSTWEST_GELB}, // OSTWEST_GRUEN
{ROT , GELB , 0, 1, ALLE_ROT_1}, // OSTWEST_GELB
{ROT , ROT , 0, 3, NORDSUED_ROTGELB}, // ALLE_ROT_1
{ROTGELB , ROT , 0, 1, NORDSUED_GRUEN}, // NORDSUED_ROTGELB
{GRUEN , ROT , 0, 10, NORDSUED_GELB}, // NORDSUED_GRUEN
{GELB , ROT , 0, 1, ALLE_ROT_2}, // NORDSUED_GELB
{ROT , ROT , 0, 3, OSTWEST_ROTGELB}, // ALLE_ROT_2
{ROT , ROTGELB , 0, 1, OSTWEST_GRUEN}}; // OSTWEST_ROTGELB

void stateMachine()
{
Ampel1(state_table[state].Ampel1);
Ampel2(state_table[state].Ampel2);

if (zaehler>0) {
zaehler--;
} else {
if ( ((state_table[state].I_Schleife == 1) && Induktionsschleife() ) ||
(state_table[state].I_Schleife == 0) )
{
state = state_table[state].Naechster;
zaehler = state_table[state].Wartezeit;
}
}
}
</syntaxhighlight>

== Implementierung einer objektorientierten Finite State Machine in C++==

* Notation von Endlichen Automaten in UML
* Praktisches Beispiel, anhand dessen die Funktionsweise eines Toasters erklärt wird. Dazu wird die Notation in UML verwendet.
* Implementation des Beispiels in C++ auf einem AVR-Controller

Die gezeigte Möglichkeit bzw. das Beispiel sollte als Denkanstoss verstanden werden und nicht als Referenzimplementation. Es wurden bewusst bestimmte Feinheiten von endlichen Automaten verzichtet, um das Beispiel auf gut verständlichem Niveau zu halten.

* Dokumentation im PDF Format [http://www.mikrocontroller.net/attachment/137066/ImplementierungEinerFiniteStateMachine_V1.1.pdf ImplementierungEinerFiniteStateMachine_V1.1.pdf]
* LaTeX Source der Dokumentation [http://www.mikrocontroller.net/attachment/137067/Dokumentation_Source_V1.1.zip Dokumentation_Source_V1.1.zip]
* Beispielcode für AVR-Studio 4 [http://www.mikrocontroller.net/attachment/135434/AVR_Beispiel_Source.zip AVR_Beispiel_Source.zip]

* [http://www.mikrocontroller.net/topic/248837#2556592 Forumsbeitrag]: Eine objektorientierte State Machine in C++

== Grafische Modellierung einer Finite State Machine ==
Das Open Source Werkzeug Yakindu Statechart Tools (http://www.statecharts.org) ermöglicht es Zustandsautomaten grafisch zu modellieren, deren Verhalten zu simulieren und Code für verschiedene Sprachen (C/C++, Java) zu generieren.
Die grafischen Modellelemente entsprechen denen der UML2 und werden durch eine einfache und zweckmäßige Expression-Language ergänzt.

'''Einfaches Ampel Modell'''

Das Modell einer einfachen Ampel wie oben beschrieben sieht in Yakindu SCT wie folgt aus:

[[Datei:Sct_beispiel1.jpg|center|framed|Einfaches Ampel Modell]]

Wie erwartet hat die Ampel vier Zustände, die wiederum mit Übergangs-Pfeilen (Transitionen) verbunden sind. Jede Transition verfügt über einen Auslöser, in diesem Fall mit dem Namen ''tick''
Mit Hilfe der Yakindu DSL wird im linken Teil des Editors ein internes Event mit dem Name "tick" definiert, das entsprechend der Taktung des Zustandsautomaten "gefeuert" werden soll. Der Ausdruck ''every 1s / raise tick'' sorgt dafür, dass das Event ''tick'' jede Sekunde einmal gefeuert wird.
Da Yakindu SCT es erlaubt Zustandsautomaten zu simulieren, ist es jederzeit überprüfbar ob das modellierte Verhalten den Erwartungen entspricht. Über ''Run as... --> YAKINDU Statechart'' lässt sich in die ''Simulation View'' wechseln. Der jeweils aktive Zustand wird nun rot hinterlegt.

[[Datei:Sct_beispiel1b.jpg|center|framed|Simulation View]]

'''Einfache Kreuzung mit Zwei Ampel-Gruppen'''

Im zweiten Beispiel soll eine einfache Ampelkreuzung modelliert werden. Es wird davon ausgegangen, dass die Ampeln in zwei Gruppen geschaltet werden. Ampel 1 und 3 bilden die nord_süd – Gruppe, während die übrigen Ampeln die ost-west – Gruppe bilden. Der Einfachheit halber werden Ampeln einer Gruppe immer gleich geschaltet. Wie oben darf eine Ampel-Gruppe nur dann den Zustand ''rot'' verlassen, wenn die jeweils andere Gruppe sich im Zustand ''rot'' befindet.

[[Datei:Sct_beispiel2.jpg|800px|center|Ampelkreuzung]]

Im Yakindu SCT Modell gibt es nun für jede Ampel-Gruppe eine eigene Region. Wird der Zustandsautomat betreten so wird nun parallel der Zustand ''rot'' in der ''nord_sued'' Region und der Zustand ''gruen'' in der ''ost_west'' Region aktiv. Wie bereits im ersten Beispiel wird der Zustandsautomat über das ''tick'' Ereignis angetrieben, das jede Sekunde einmal auftritt.
Um das gewünschte Ampel-Verhalten zu modellieren wird nun die Transition von ''rot'' zu ''rot-gelb'' mit einem ''Guard'', also einer Bedingung geschützt. Zwar wird der Übergang weiterhin mit dem Ereignis ''tick'' angestoßen, allerdings wird der Übergang nur ausgeführt wenn die in eckigen Klammern formulierte Boolesche-Bedingung erfüllt ist. Die Funktion ''active()'' gehört zu den Bordmitteln von Yakindu SCT und prüft ob ein bestimmter Zustand aktiv ist. In diesem Beispiel kann in der Region ''nord_sued'' der Zustand ''rot'' nur verlassen werden, wenn in der Region ''ost-west'' der Zustand ''rot'' aktiv ist. Wie auch im vorhergegangenen Beispiel lässt sich das Verhalten simulieren, so das überprüft werden kann ob das Verhalten den Erwartungen entspricht.

'''Ampel mit Induktionsschleife'''

Das Verhalten der Ampelanlage aus Beispiel 2 soll um eine Induktionsschleife erweitert werden. Der Verkehr an der Ampelanlage fließt normalerweise in ''ost_west'' – Richtung, daher die Ampel in dieser Richtung immer den Zustand ''grün'' haben, es sei denn die Induktionsschleife in ''nord-süd'' - Richtung wird ausgelöst.

[[Datei:Sct_beispiel3.jpg|800px|center|Ampelkreuzung mit Induktionsschleife]]

Um dieses Verhalten in das SCT-Modell zu integrieren muss zunächst ein neues Ereignis definiert werden. Dieses Ereignis wird als Teil des ''Interface-Scopes'' definiert, da es außerhalb des Zustandsautomaten erzeugt werden soll. Ereignisse die Teil einer externen Schnittstelle sind werden mit einer Richtung (in / out) deklariert, die angibt ob das Ereignis den Zustandsautomat betritt, oder verlässt.

Nach dem das neue Ereignis definiert ist, muss nur noch der Auslöser für den Übergang von ''gruen'' zu ''gelb'' geändert werden. Statt wie bisher durch das ''tick'' Event, wird nun das ''induktionsSignal'' als Auslöser verwendet. In der Simulations-Ansicht kann das neue Ereignis manuell mit einem Klick ausgelöst werden, so dass das korrekte Verhalten wieder getestet werden kann.

[[Datei:Sct_simView.jpg|center|framed|Induktionsschleife auslösen]]

'''Warteschleife'''

Es soll die Grün-Phase verlängert werden, so dass erst nach dem 5. ''tick'' der Übergang in den ''gelb'' Zustand erfolgt.

[[Datei:Sct beispiel4.jpg|800px|center|Ampelkreuzung mit Warteschleife]]

Um eine Warteschleife zu realisieren wird dem ''Internal-Scope'' zuerst eine neue Variable hinzugefügt. Da während des Wartens der ''grün'' Zustand nicht verlassen wird, lässt sich das Herunterzählen der Wartezeit mittels eines zusammengesetzten Zustands darstellen. Wird der Zustand ''grün'' betreten, wird zunächst einen Eintritts-Aktion ausgeführt, die den Wert von ''wartezeit'' auf 5 setzt. Außerdem wird ebenfalls der Zustand ''Warten'' aktiv. Erfolgt nun ein ''tick'' wird ohne ''grün'' zu verlassen in ''WartezeitVerringern'' gewechselt und der Wert von ''wartezeit'' um 1 verringert.
Der Übergang zu ''gelb'' ist wieder durch einen Guard geschützt und kann nur erfolgen wenn die Bedingung ''wartezeit == 0'' erfüllt ist.

'''C-Code aus dem Modell generieren'''

Um nun Code aus dem Modell zu generieren muss zuerst eine GeneratorModel-Datei erzeugt werden, in der unter anderem die Ziel-Sprache angegeben wird.
Um den Zustandsautomaten abzubilden verwendet die konkrete Implementierung ein ''switch case'' Konstrukt, das dem oben Gezeigten ähnelt. Außerdem wurde ein ''code-only'' Ansatz verfolgt, so dass keine externen Bibliotheken oder Frameworks benötigt werden. Das komplette Eclipse Projekt kann [http://statecharts.org/Examples/ampel.zip hier] runtergeladen werden.

== Realisation von FSMs in Hardware ==
=== Aufbau einer FSM in digitalen Chips ===

Sollen sehr schnelle Steuerungen und Entscheider aufgebaut werden, wurden und werden digitale Bausteine mit Logikgattern verdrahtet, die steuerbare Zähler enthalten. Damit lassen sich effektive Taktgeschwindigkeiten im Bereich von mehreren MHz erreichen, die in Sicherheitsbereichen eingesetzt werden. Oft werden solche Schaltungen auch zur Überwachung von anderen Schaltungsteilen eingesetzt.

Früher wurden fast alle logischen Schaltungen auf diese Weise entworfen, z.B. auch die ersten Computer von IBM.

=== Umsetzung von FSMs in programmierbarer Hardware ===

Da heute digitale Hardware vielfach in Form programmierter PLD- und [[FPGA]]-Bausteine eingesetzt wird, verlagert sich der Entwurf der FSM mehr zu Softwareentwicklung hin. Dabei besteht je nach Vorliegen der funktionellen Beschreibung und eventueller Primärinformation die Möglichkeit, ein Abbild der digitalen Schaltung in VHDL zu formulieren und zu importieren, bzw. ein klassisches state diagram neu zu entwerfen oder die Zustandswechsel in Tabellenform zu importieren und das Erzeugerwerkzeug die FSM generieren zu lassen.

Letztendlich kann in Hardware jede sequentielle Logikschaltung, welche [[FlipFlop]]s und Dekoder enthält als FSM betrachtet werden, egal ob es ein einfaches Schieberegister oder eine komplexe ALU einer CPU ist. Die einfachste, denkbare FSM ist ein Toggle-FlipFlop, welches mit jedem Takt seinen Ausgangszustand wechselt.

== Geschwindigkeitsvergleich ==
In Software realisierte state machines erreichen unter C++ in Windows auch bei hoher Prozessauslastung selten niedrigere Reaktionszeiten als im Millisekundenbereich. Die damit in Echtzeit erfassbaren und prozessierbaren externen Ereignisse bewegen sich üblicherweise im Bereich von einigen 100Hz. Mit Microcontrollern und DSPs erreicht man mit Nicht-Multi-tasking-FSMs Abtastraten bis einige 100kHz. In VHDL realisierte state machines besitzen je nach FPGA-Familie, Art der Codierung und Zyklustiefe typische Taktfrequenzen von 10...100MHz.
Mit einem Echtzeitbetreibssystem auf einem PC, z. B. Linux mir Preempt-RT Patch, werden ungefähr 35 µs Zykluszeit erreicht, also circa 30 kHz.

== Weblinks ==

* [http://www.aqdi.com/state.htm Using State Machines In Your Designs] (C) 2003 Hank Wallace
* [http://qfsm.sourceforge.net/ Qfsm] - A graphical tool for designing finite state machines (GPL)
* [https://www.itemis.com/en/yakindu/statechart-tools/ YAKINDU Statechart Tools] Ein Werkzeug zum Modellieren und Simulieren von Statecharts sowie Code-Generatoren für Java, C und C++.
* [http://www.sinelabore.com www.sinelabore.com] Ein Werkzeug das aus UML State Machines C-Code speziell für eingebettete Systeme erzeugt.
* [http://smc.sourceforge.net SMC The State Machine Compiler]
* [http://block-net.de/Programmierung/cpp/fsm/fsm.html C/C++ event driven FSM] Open source Werkzeug zur Generierung von C++ FSM Code und UML Diagramm mittels Transitionstabelle.
* http://astade.tigris.org/ -> http://wiki.astade.de/dokuwiki/doku.php (https://www.mikrocontroller.net/search?query=astade)
* [http://stefanfrings.de/multithreading_arduino/index.html Multithreading mit/ohne Arduino] von Stefan Frings
[[Kategorie:Algorithmen und Arithmetik]]

Digitaler Rauschgenerator im FPGA

2017-06-26T20:59:43Z

Nobodyy: /* Weblinks */

Ein digitaler Rauschgenerator basierend auf Zufallsbits

''von [[Benutzer:engineer|J.S.]]''

Dieser Artikel beschreibt eine Möglichkeit, tatsächlich zufällige, nicht vorhersagbare Bitfolgen zu erzeugen, die prinzipiell gleichverteilt sind und keinerlei Präferenzen besitzen. Damit lassen sich tatsächliche Zufallszahlen erzeugen, die wiederum als Rauschen verwendbar sind.

Für die Realisation in VHDL müssen noch Buffer eingesetzt- sowie Schaltungsteile mittels "keep" erhalten werden. Die Lösung ist so gewählt, dass keine PLLs oder eine externe Verschaltungen benötigt werden.

==Historie==
Die Schaltung funktionierte seinerzeit mit CMOS-Invertern und einem Binärzähler der 4000er Serie. Das letzten Bits diente als Umschalter zwischen den unterschiedlich langen Inverterketten.

==Prinzip==
Die Idee beruht auf der Abtastung eines sich asynchron zur Zieldomain bewegenden Taktes, der sich praktisch während jedes denkbaren Abtastvorgangs ändern und damit vollkommen zufällige Werte annehmen kann. Die so abgetasteten Bits werden dann unabhängig von einander zu Bytes zusammengebaut, wodurch prinzipiell auch lange Einsen- und Nullfolgen entstehen können. Dazu muss der asynchrone Takt allerdings vergleichsweise langsam abgetastet werden.

===Der freilaufende Zähler===
Eine einfache Schaltung für den Bitgenerator in VHDL ergibt sich durch einen Zähler, von dem ein Takt (hier 1/8-tel - es klappt oft auch 1/4-tel) abgeleitet wird und der sich infolge der aynchronen Rückkopplung auch noch verzählen kann:

signal toggle : std_logic_vector(2 downto 0) := "000";

signal clock : std_logic;

p_osc : process (toggle)

begin
toggle <= toggle + "1";
clock <= toggle (2);
end process;

Die Teilung des Taktes ist bei manchen FPGAs nicht nötig, allerdings wird eine simple Rückkopplung vom Typ toggle <= not toggle; mitunter nicht erzeugt, bzw. sie ist zu schnell, um einen sauberen Takt zu erzeugen. Je breiter der Vektor "toggle" angesetzt wird, desto grösser ist die Wahrscheinlichkeit, dass der Zähler falsch zählt und Periodensprünge vollzieht. Die Ausgangsfrequenz wird allerdings geringer. Diese einfache Formulierung führt aber zu sehr technologieabhängigen Implementierungen, die von Synthesedurchlauf zu Synthesedurchlauf schwankt. Ein Beispiel findet sich im Farbmultiplex-Modul meines VGA-Cores.

Besser ist ein gezielter Aufbau eines selbstschwingenden Systems auf Technologieniveau:

===Einfacher Ringoszillator===
Der naheliegende Ansatz ist ein selbstschwingender Ringoszillator, der unabhängig von der Zieldomain arbeitet und im Prinzip jeden Flankenzustand darstellen kann. Derartige Oszillatoren lassen sich leicht durch rückgekoppelte Inverterketten bilden, die vom Prinzip nie in einen stabilen Zustand schwingen können und daher immer oszillieren. Gegenüber dem Zähler werden höhere Taktraten erzielt. Die Erfahrung zeigt aber, dass solch ein einfacher Oszillator meistens nicht genügend jittert, um über venüftige Zeiträume wirklich alle erdenklichen Kombinationen erzeugen zu können, da sich in der kurzfristigen Betrachtung immer eine Interferenz zu dem Abtasttakt einstellen wird. Ausserdem zeigt sich, dass solche Ringoszillatoren dazu neigen, sich auf benachbarte Schaltungsteile zu synchronisieren. Wenn diese mit dem Lesetakt getriggert werden, entstehen beobachtbare Spektren in den erzeugten Bitfolgen.

===Mehrfach-Ringoszillator===
Eine deutliche Verbesserung stellt die Verwendung zweier Oszillatoren dar, die miteinander interferieren und je nach zeitlicher Überlagerung durch Verknüpfung mit einem EXOR ein z.T. sehr schnell toggelndes Bit ergeben, das schon gute Zufallswerte generiert, wenn es selten genug abgetastet wird. Je mehr solche Oszillatoren zugeschaltet werden, desto größer ist die Wahrscheinlichkeit eines Bitwechsels im Bereich der abtastenden Flanke. Leider neigt aber auch diese Anordnung von Ringoszillatoren dazu, sich auf Einflüsse der Restschaltung zu synchronisieren, was sich in der FFT-Analyse und Häufungsmessung des erzeugten Ausgangsignal äussert.

===Desynchronisierte Ringoszillatoren===
Eine effektive Möglichkeit, etwaige Synchronisationsneigungen zu unterdrücken, ist es, die Frequenzen der Oszillatoren permanent umzuschalten, sodass keiner von ihnen eine stabile Phasenlage einnehmen kann. Genau, wie zu Beginn der Einschwingphase, benötigt der Oszillator nach dem Umschalten nämlich einige Schwingungen, um halbwegs stabil zu werden. Dies gilt insbesondere, wenn er sich auf irgendein externes Ereignis einstellen möchte. Wenn rechtzeitig umgeschaltet wird, hat der Oszillator keine Chance, sich auf Nachbarschaltungen einzuschwingen.

Die Umschaltung funktioniert so, dass die Länge der Inverterkette verändert wird, indem ein Steuersignal einen Multiplexer treibt, der zwischen zwei Pfaden auswählt. Im einfachsten Fall schaltet man einfach 2 Inverter mehr dazu, wodurch sich etwas die Frequenz senkt. Je nach Technologie sind 4 Inverter besser, da dies einen deutlicheren Frquenzhub zur Folge hat. Entscheidend ist bei der Methode auch, dass durch das Umschalten ein Phasensprung erzeugt wird. Sollte der Oszillator begonnen haben, sich auf ein Ereignis zu synchronisieren, wird die massgebliche Taktflanke dadurch sofort wieder auf einen anderen Punkt gesetzt.

===selbstdesynchronisierende Ringoszillatoren===
Eine Erweiterung der Lösung von oben ist es nun, die Zeitpunkte der Umschaltung ebenfalls zufällig bestimmen zu lassen. Dies geschieht am einfachsten durch einen ähnlich aufgebauten Gegenpart, der seinerseits wieder zufällig gesteuert wird. Im ersten Schritt entsteht der nachfolgend beschriebene 2fach- gekoppelte OSC. Mit drei deratig ringförmig verketteten, selbstschwingenden Oszillatoren bekommt man ein nahezu zufälliges Verhalten der Phase, da sich immer einer der Oszillatoren im Einschwingvorgang befindet und sich sein Beitrag zum Exor stark verschiebt, sodass auch in der lokalen Betrachtung keine sichtbaren Interferenzmuster mehr auftreten.

==Realisationsvorschlag==
Hier eine konkrete Lösung mit 2 gekoppelten Oszillatoren:

[[Datei:Js-Vhdl-noise-bit-generator-schematic.gif]]

Jeder der beiden OSC wird über eine Inverterkette mit einer insgesamt ungeraden Anzahl von Invertern gebildet, wobei die geradzahligen Inverterstufen ein delay bilden. Die Rückführung erfolgt über einen Multiplexer, welcher umschaltbar ist. So liegen beispielsweise einmal 7 und einmal 9 inverter in der Kette, bei dem anderen z.B. 11 oder 13.

Jeder der beiden Oszillatoren treibt einen eigenen Zähler an, der bis 13 bzw. 27 zählt. Das jeweilige höchste Bit des Zählers wird zum Umschalten der Kettenlänge des anderen Oszillators benutzt. Durch die asymmetrische Verteilung 8/13 zu 5/13 bzw. 16/27 zu 11/27 wird erreicht, dass es eine längere und eine kürzere Phase gibt. Während der längeren Phase schaltet man die niedrigere Frequenz, während der längeren die höhere Frequenz. Damit ergibt sich für die Kettenlänge die Folge:

OSC1 : ...7.7.7.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.7.7.7.7.7.7.7.7.7.7.7.9.9.9.9.....

OSC2 : ....13.13.11.11.11.11.11.11.11.11.13.13.13.13.13.11.11.11.11.11.11.11.11.13.13...

Oszillator 1 darf also abwechselnd eine längere Periode mit der etwas niedrigeren Frequenz schwingen und danach eine kürzere Periode mit der höheren. Irgendwann dazwischen schaltet er die Frequenz des zweiten um. Da sich der andere ebenso verhält, ergeben sich grob 4 Frequenzkombinationen, die unterschiedlich und veränderlich überlappen. Durch die langen Phasen von mindestens >5 Takten ist sichergestellt, dass auch bei schnellen Technologien der jeweilige OSC wieder anschwingt, falls beim Umschalten mitten in einen Zustandswechsel gesprungen wurde. Genau dies verschiebt die Phasen immer wieder sehr zufällig, sodass die Frequenz nicht lange stabil ist und sich die Oszillatoren auf nicht auf Umgebungseinflüsse synchronisieren können. Die Ausgänge werden mit Exor gemischt, wodurch bei einer Abtastung durch eine andere Domain noch bis zu 5-10 MHz vollkommen zufällige Bits entstehen.

===Realisation für Consumerqualität===
16Bit-Rauschwerte bekommt man gemäß der Methode oben dann mit etwa 500kHz, in dem man kontinuierlich samplet und die Werte in SR schiebt. Für meine Audioworkstation benutze ich eine Abtastrate von ~4,5MHz und generiere daraus 24 Bit-Werte mit 192kHz Samplefrequenz. Muster im Bereich der Audiofrequenzen sind im Spektrum nicht erkennbar.

Anfänglich hatte ich auch noch mehrere Generatoren parallel aufgebaut und die 24 Bit-Werte gemischt, fand aber keine Verbesserung mehr. Allerdings hatte ich teilweise den Fall, dass statistisch mehr Nullen rauskamen (53%:47%). Ich habe dann einfach zwei ähnliche Generatoren aufgebaut (andere Kettenlängen) und einen Kanal invers zugemischt. Für meine Zwecke reicht das jetzt vollkommen aus. Für messtechnische Zwecke müsste man es näher untersuchen. Wenn man irgendwelche Rauschquellen mischen möchte, sollte man eine Extraquelle aufbauen, statt die erste mit anzuzapfen, es sei denn, dies ist signalverarbeitungstechnisch notwenig. Bei den Tongeneration von Schlagzeugklängen bekam ich vereinzelt seltsame metallisch klingende Auslöschungen, wenn zwei Instrumente (per Filter erzeugt) gleichzeitig erklangen. Einfache Abhilfe schafft ein Bitvertauscher.

===Realisation für Messtechnik===
Für messtechnische Applikationen sollte man genügend niedrig abtasten, z.B. 1/MHz/bit. Für jedes weitere bit bzw MHz kommt ein weiterer Generator hinzu, der anders parametriert ist. Das stellt platzmäßig nur ein geringes Problem dar, da je nach Realisation nur 50-100 Logikelemente benötigt werden. Die Rauschgeneratoren sollten an verschiedenen Stellen im FPGA sitzen und sich keine Logikzellen teilen -> FPGA-Editor für das mapping / constraints benutzen.

Ein eventuelles 1:0-Verteilungsproblem sollte mit zwei komplementären Rauschquellen zu lösen sein, während man die Zuordnung der Rauschbits ebenfalls noch ändern kann, indem man einen weiteren Oszillator nutzt, der zyklisch Adressen generiert, die einen von mehreren Multiplexern mit wechselndem Bitmapping auswählt. Auch lassen sich mehrere Rauschgeneratoren überlagern, um die Auflösung zu erhöhen. wobei das Problem auftritt, dass Ergebnisse im mittleren Wertebereich dann wahrscheinlicher sind, als Werte am Rand. Will man das verhindern, sind die Werte immer über EXOR bitweise zu verknüpfen.

====Bauvorschlag / Beispiel====
Ein array von 2x32 Rauschquellen (ca. 500 LEs) wird mit einem PLL-basierten Takt von 1MHz in 64 Registern asynchron eingelesen. Über einen 64:64-Bitvertauscher mit zufällig wechselndem Mapping werden diese zu zwei 32 2-Bit-Werten zusammengesetzt, die mit einem Exor und einem Inverter von einander subtrahiert / komplementär addiert werden. Die Ergebnisse gehen auf einen synchronen asymmetrischen 32:8-FiFo, der 8-bit Rauschwerte mit 4MHz produziert, die statistisch vollkommen gleichverteilt sind.

==Einschätzung der Qualität==
===Simulation===
Bereits mit festen Werten für die Inverterverzögerungen, die ja real starken Zufällen unterworfen sind, produziert eine ModelSIM-Simulation für die 2fach-Lösung ein sehr komplexes Muster mit geringer Wiederholrate. In der Realität lässt sich ein entsprechender Jitter messen, der mehrere Perioden des abtastenden Taktes überstreicht.

Mit einer analogen Simulation können minimale Änderungen des Schaltverhaltens untersucht werden. Variiert man z.B. die Steilheit nur eines Inverterausgangs eines Oszillators um 0,5% ergibt sich bereits nach wenigen Schwingungen ein qualitativ verändertes Bild, weil die Umschaltpunkte des anderen Oszillators ein wenig wandern, wodurch sich eine andere Phasenkonstellation ergibt.

<gallery caption="2 Fälle verkoppelter Oszillatoren" widths="600" heights="300" perrow="1">
Datei:Lut-based-oscillator-js.gif|;Die beiden blauen Oszillatoren variieren minimal, was anhand des sich ergebenden 2Bit Codes (Visualisierung der Zustandsfolge) = violette Kurve schon sichtbar wird. Der mit einem EXOR gebildete Signal-Wert (türkis), wird mit einem willkürlichen Takt im FPGA (rot) gesampelt, sodass der grüne Ausgangswert entsteht. Eine kleine Änderung im Verhalten eines Inverters bedingt bereits ein anderes Ausgangsmuster;
</gallery>

=== Probleme der realen Schaltung ===
Leider ergibt sich das Problem, dass bei zusammenfallenden Flankenwechseln kein eindeutiges Signal am Ausgang des XOR-Gatters erzeug wird und das abtastende FF der Zieldomain einen Zwischenwert sieht. Aufgrund der nicht 100%-symmetrischen Schaltungstopologie in CMOS-Schaltungen liegt die Schaltschwelle für den FF-Eingang nicht auf dem 50%-Niveau, sodass mitunter ein Zustand (0 oder 1) bevorzugt wird und häufiger auftritt. Dieses Prblem lässt sich durch einen Twister lösen:

==== Twister als Symmetierhilfe ====

Durch Zuschaltung eines weiteren ca Faktor 8-16 langsamer laufenden Zufallsbitgenerators wird die Bedeutung eines Bits bei Zustand 1 invertiert, was durch ein weiteres XOR realisiert wird. Damit unterdrückt eine hohe Zahl von Einsen sich selbst. Die statistische Verteilung der Zahlen wird damit quasi umgeklappt. Angenommen, ein asymmetrischer Generator liefert zu 60% Einsen und nur 40% Nullen, so würde ein weiterer Generator derselben Art jeweils 60% der Bits invertieren. Es ergäben sich also:

* 60% * 60% = 36% zu 0 (1 verändert)
* 40% * 60% = 24% zu 1 (0 verändert)
* 60% * 40% = 24% zu 1 (1 unverändert)
* 40% * 40% = 16% zu 0 (0 unverändert)

im Ergebnis also 36%+16% = 52% Nullen und 48% Einsen und damit erheblich symmetrischer, als die Eingangsannahme. Der Twister hat sich in einem anderen Zusammenhang praktisch bereits vervorragend bewährt und eigenet sich auch für andere Formen von Zufallsgeneratoren.

=== Messungen ===

<gallery caption="FFT-Analyse von 2 gekoppelten Oszillatoren" widths="600" heights="300" perrow="1">
Datei:Vga-spectrum-analyzer-altera-fft-noise.jpg|;Das Bild (Screenshot) zeigt eine FFT-Analyse von künstlich erzeugtem 16Bit-Rauschen aus zwei gekoppelten Oszillatoren. Der blaue Bereich zeigt die spiegelsymmetische 1024 FFT bei 16Mhz. Links sind Min, Max, Mittelwert und Standardabweichung automatisch markiert. Der verkleinerte türkise Bereich zeigt die um Faktor 2 verkleinerten über 16 Messungen gemittelten Werte.;
</gallery>

===Tauglichkeit als Zufallszahlengenerator===
Die so erzeugten Zufallsbits reichen in aller der Regel bereits für gute Zufallszahlen aus, wie sie in Simulationen für technische Anwendungen benötigt werden. Sie entstehen durch einfaches Aneinanderreihen von mehreren Bits mit einem Schieberegister.

==== Gleichverteilung ====
Das Aneinanderreihen von Bits bevorzugt keine Zahl. Theoretisch kommt jede Zahl mit derselben Häufigkeit vor. Ausnahmen sind wie oben beschrieben technologisch bedingt und durch den Symmetrierer zu verbessern.

<gallery caption="Verteilung der erzeugten Zahlen" widths="600" heights="300" perrow="1">
Datei:Js-histogramm-rauschgenerator-verteilung.gif|;Die Grafik zeigt die Verteilung von Zahlen, die mit einem Rauschgenerator generiert wurden. Mit 8 zusammengehängten Bits werden Zahlen erzeugt und deren Häufung mitgezählt, wobei dieselbe Zahl innerhalb von 4096 "Würfen" schwerpunktmäßig etwa 10-40x vorkommt. Wird das Experiment fortgesetzt und weitersummiert, gleichen sich Unsymmetrien wieder etwas aus und die Kurve wird glatter. Bei 15000 Würfen beträgt die Dynamik zwischen seltenen und häufigen Zahlen ca. 60-120. Die Varianz beträgt letzlich nach >250.000 Würfen noch etwa +/- 12%. Aus Platzgründen sind nur die ersten 128 Zahlen dargestellt.;
</gallery>

==== Normalverteilung ====
Durch das Addieren von Rauschwerten kommen Werte in der Mitte des Zahlenraums naturgemäß häufiger häufiger vor, weil es mehrere Kombinationsmöglichkeiten gibt, wie sie entstehen können. Werte am Randbereich sind sehr selten.
[[Datei:Js-histogramm-rauschgenerator-summe.gif]]

Um den 8-Bit Zahlenraum abzudecken, wurde für den Rundungsfehler eine weitere Zahl addiert. Damit ist der Zahlenraum 0...255 darstellbar. Ansonsten wären nur 16x15 = 240 erreichbar.

==== Weitere Verteilungen====
Will man gezielte Verteilungen generieren und sicherstellen, dass Zahlen nach bestimmten Zeiten mindestens einmal auftreten, muss noch ein wenig mehr getan werden. Siehe [[Digitaler Zufallszahlengenerator in VHDL]].

===Verbesserungsmöglichkeiten===
Um die Zufälligkeit weiter zu erhöhen, lässt sich die Schleife eines oder mehrerer Oszillatoren über externe Pins bilden, was zu starken Temperatur und Exemplarschwankungen führt. Dies ist vor allem bei der Nutzung nur eines Oszillators vorteilhaft. Allerdings reduziert sich dadurch die maximale Frequenz des Generators.

[[Kategorie:FPGA-Projekte]]

===Tauglichkeit als Rauschgenerator===
Aufgrund der echten Zufälligkeit der Werte können keine Aussagen über das Spektralverhalten gemacht werden, womit sich das System als nichtdeterministischer Rauschgenerator eignet. Im Test wurden keine bevorzugt erzeugten Frequenzen beobachtet.

== Anwendungen ==
=== Signalverarbeitung ===
Zufallszahlen werden oft als Startwerte für deterministische Zufallszahlengeneratoren verwendet

=== Bildverarbeitung ===
Rauschgeneratoren werden in der Bildverarbeitung zur Verbesserung der Bildqualität eingesetzt, indem z.b. mittels der "salt and pepper"-Methode Kanten infolge von Abtastungsartefakten geglättet werden.

=== Beiträge zum Thema ===
*[http://www.mikrocontroller.net/topic/245078 Noisegenerator im FPGA]
*[http://www.mikrocontroller.net/topic/243241 Pseudozufallsgenerator mittels VHDL]
*[http://www.mikrocontroller.net/topic/191427 Rauschgenerator in VHDL]

=== Weblinks ===

* http://de.wikipedia.org/wiki/Rauschgenerator
* http://de.wikipedia.org/wiki/Zufallszahlengenerator
* Das Verfahren ist patentiert seit 1999: https://www.google.ch/patents/DE19926640A1

FIFO

2015-01-01T14:45:23Z

Nobodyy: /* Beschreibung */

Ein FIFO (First-In-First-Out) ist ein Pufferspeicher nach dem "Warteschlangen-Prinzip". Pufferspeicher dienen dazu, für einen Prozessor Daten aufzufangen, die er noch nicht verarbeiten kann. Ein FIFO funktioniert definitionsgemäß so, dass das erste Element (First In), welches "hinten" in die Warteschlange eingefügt wird, später auch als erstes "vorne" herausgeholt wird (First Out). Das Gegenstück zum FIFO ist [[LIFO]].

Ein bekanntes Beispiel für einen FIFO-Speicher ist der des [[UART]]s im PC. Dieser sammelt ankommende Daten solange, bis er fast voll ist (meist 14 Bytes). Dann wird ein [[Interrupt]] ausgelöst und der Prozessor kann "auf einen Rutsch" alle Daten auf einmal auslesen. Ganz am Anfang hatten UARTs keinen FIFO und erzeugten für jedes empfangene Byte einen Interrupt, so wie es heute noch die meisten Mikrocontroller machen. Damit ist aber die CPU-Belastung wesentlich höher, was bei höheren Datenraten zu Problemen führen kann.

Die Umsetzung eines FIFOs in Software heißt Ringpuffer und weist auch eine feste Puffergröße auf. Wesentlicher Vorteil gegenüber der verketteten Liste ist die schnellere Ausführungszeit und der geringere Aufwand.

== Standard-Ringpuffer ==

Vorteile:
* Simpel
* Leicht verständlich
* Daten können auch vom Typ struct sein

Nachteile:
* Schnell aber nicht optimal

=== Beschreibung ===
{|
|-
|
[[Bild:Ringpuffer.png|300px]]
|
[[Bild:Circular buffer.png|200px]]
|}

Die Inhalte des Puffers werden in einem schlichten Array gespeichert und der Zugriff erfolgt über einen Integer-Index. Erreicht ein Index die Obergrenze springt dieser auf Null zurück. Ein größer-gleich statt nur eines ist-gleich Vergleichs ist sicherer gegenüber Programmfehlern, bei denen der Index verstellt wurde.
<syntaxhighlight lang="c">
write = write + 1;
if (write >= BUFFER_SIZE)
write = 0;
</syntaxhighlight>
Haben Lese- und Schreib-Index den gleichen Wert wird der Puffer als leer angesehen. Wenn write+1 und read identisch sind wird der Puffer als voll angesehen. Nun fehlt noch der Sonderfall bei dem read gleich Null ist, hier funktioniert der write+1-Vergleich nicht mehr und die Abfrage einer zusätzlichen Bedingung ist zur voll-Abfrage erforderlich.

<syntaxhighlight lang="c">
read == write => leer

write + 1 == read || read == 0 && write+1 == BUFFER_SIZE => voll
</syntaxhighlight>

Bei gleichzeitigem Zugriff zwischen UART-ISR und Hauptprogramm muss ausgeschlossen werden, dass das Hauptprogramm beim Lesen aus dem Puffer nicht durch den Interrupt unterbrochen werden kann. Ansonsten können Programmabstürze passieren, deren Ursache oft nicht nachvollziehbar ist. Als Abhilfe dienen [[Interrupt#Atomarer_Datenzugriff|Atomare Abschnitte]], solche können durch keinen Interrupt unterbrochen werden. Die Radialkur deaktiviert alle Interrupts, besser ist die Deaktivierung eines einzelnen Interrupts. Im Allgemeinen werden versäumte Interrupts nach erneuter Aktivierung nachgeholt, da ein Flag gesetzt wurde. Wichtig ist vor allem, dass die Ausführungszeit des Atomaren Abschnitts und der ISR geringer ist als der Intervall in dem Interrupts erfolgen, da ansonsten ein Interrupt verloren gehen könnte.

<syntaxhighlight lang="c">
cli()
ret = BufferOut(&var);
sei()
</syntaxhighlight>

Hilfreich ist die Initialisierung der Indizes (read, write) mit -1, denn damit kann man einen leere Ringpuffer von einem vollen unterscheiden. Initialisiert man nur mit 0, kann man einen leeren nicht von einem vollen mit read=write=0 unterscheiden.

=== Code-Beispiel ===
<syntaxhighlight lang="c">
#define BUFFER_SIZE 23

struct Buffer {
uint8_t data[BUFFER_SIZE];
uint8_t read; // zeigt auf das Feld mit dem ältesten Inhalt
uint8_t write; // zeigt immer auf leeres Feld
} buffer = {{}, 0, 0};

uint8_t BufferIn(uint8_t byte)
{
//if (buffer.write >= BUFFER_SIZE)
// buffer.write = 0; // erhöht sicherheit

if (buffer.write + 1 == buffer.read || buffer.read == 0 && buffer.write + 1 == BUFFER_SIZE)
return FAIL; // voll

buffer.data[buffer.write] = byte;

buffer.write = buffer.write + 1;
if (buffer.write >= BUFFER_SIZE)
buffer.write = 0;
return SUCCESS;

}

uint8_t BufferOut(uint8_t *pByte)
{
if (buffer.read == buffer.write)
return FAIL;
*pByte = buffer.data[buffer.read];

buffer.read = buffer.read + 1;
if (buffer.read >= BUFFER_SIZE)
buffer.read = 0;
return SUCCESS;
}
</syntaxhighlight>

== 2n-Ringpuffer - die schnellste Lösung ==

Vorteile:
* Durch Bitmaske auf den Feld-Index ''write'' kann der nicht "Amoklaufen" und beliebige Inhalte im Speicher überschreiben
* Sehr einfach, sehr schnell
* Daten können auch vom Typ ''struct'' sein
Nachteile:
* Nur Größenfaktoren von 2n möglich
* Nur in speziellen Fällen Pointerreferenz möglich

=== Beschreibung ===

Wenn der Index am oberen Ende angekommen ist springt er an den Anfang zurück. Die Definition der Obergrenze wird nicht durch einen Vergleich realisiert, sondern durch Modulo-Arithmetik. Dies kann sehr einfach und schnell durch Maskieren des Index-Werts umgesetzt werden.

Beispiel:
<syntaxhighlight lang="c">
( write + 1 ) & MASK

15 = 0b00001111
15 + 1 = 16 = 0b000010000
16 & MASK = 0b000010000 & 0b000001111 = 0b000000000
</syntaxhighlight>

Daraus folgt das ''write'' nur einen Wert zwischen 0 und 15 einnehmen kann. Das ganze funktioniert nur mit Zahlen der Reihe 2n.

Da der Puffer nur eine endliche Größe aufweist, muss eine voll/leer Indikation verfügbar sein. read == write bedeutet Puffer leer, entsprechend bedeutet write + 1 == read, dass keine weiteren Elemente mehr hinzugefügt werden können, denn sonst würde das Hinzufügen weiterer Daten einen Pufferüberlauf hervorrufen. Für die Behandlung des Pufferüberlaufs gibt es zwei Methoden, nichts tun und Fehler zurück geben oder ältesten Puffer-Inhalt verwerfen (read+1).

<syntaxhighlight lang="c">
read == ((write + 1) & MASK)
</syntaxhighlight>

Auch hier verhindert die Bitmaske einen möglichen Überlauf. Weiter zu beachten ist, dass ein Byte durch die voll/leer Indikation verloren geht, der Puffer hat hier nur eine größe von 15 statt 16 Byte

Und noch ein kleiner Trick. Bei einer Zahl der Reihe 2^n lässt sich auf einfache Weise immer eine passende Bitmaske erzeugen und man sieht gleichzeitig klar die Anzahl der genutzten Bytes.

<syntaxhighlight lang="c">
# define SIZE 16
# define MASK (SIZE-1)

16 = 0b010000
16 - 1 = 0b001111
</syntaxhighlight>

Im Normalbetrieb sollte der Puffer nie voll ausgereizt sein und wenn der Puffer bereits überläuft ist es für die Systemstabilität und Fehleranlyse oft schon zu spät, denn von einem nicht mehr funktionierenden Gerät lässt sich nur wenig Information herauskitzeln. Da kann ein Frühwarnsystem mehr bieten, wobei zwei Ausprägungen typisch sind, Höchstwert merken und eine Meldeschwelle einführen.

<syntaxhighlight lang="c">
freeMemory = (read - write - 1 ) & MASK);
if (freeMemory < floodmark)
floodmark = freeMemory;
</syntaxhighlight>

<syntaxhighlight lang="c">
if ( (read - write - 1 ) & MASK) <= FLOODMARK;
FloodmarkExcess();
</syntaxhighlight>

=== Code-Beispiel ===

<syntaxhighlight lang="c">
#define BUFFER_SIZE 16 // muss 2^n betragen (8, 16, 32, 64 ...)
#define BUFFER_MASK (BUFFER_SIZE-1) // Klammern auf keinen Fall vergessen

struct Buffer {
uint8_t data[BUFFER_SIZE];
uint8_t read; // zeigt auf das Feld mit dem ältesten Inhalt
uint8_t write; // zeigt immer auf leeres Feld
} buffer = {{}, 0, 0};

uint8_t BufferIn(uint8_t byte)
{
uint8_t next = ((buffer.write + 1) & BUFFER_MASK);
if (buffer.read == next)
return FAIL;
buffer.data[buffer.write] = byte;
// buffer.data[buffer.write & BUFFER_MASK] = byte; // absolut Sicher
buffer.write = next;
return SUCCESS;
}

uint8_t BufferOut(uint8_t *pByte)
{
if (buffer.read == buffer.write)
return FAIL;
*pByte = buffer.data[buffer.read];
buffer.read = (buffer.read+1) & BUFFER_MASK;
return SUCCESS;
}
</syntaxhighlight>

=== FIFO mit C-Präprozessor ===

<syntaxhighlight lang="c">
#ifndef FIFO_H_
#define FIFO_H_

#include <stdint.h>

typedef struct {
uint8_t _read;
uint8_t _write;
uint8_t _buffer[64];
} FIFO64_t;

typedef struct {
uint8_t _read;
uint8_t _write;
uint8_t _buffer[128];
} FIFO128_t;

#define FIFO_init(fifo) { fifo._read = 0; fifo._write = 0; }

#define FIFO_available(fifo) ( fifo._read != fifo._write )

#define FIFO_read(fifo, size) ( \
(FIFO_available(fifo)) ? \
fifo._buffer[fifo._read = (fifo._read + 1) & (size-1)] : 0 \
)

#define FIFO_write(fifo, data, size) { \
uint8_t tmphead = ( fifo._write + 1 ) & (size-1); /* calculate buffer index */ \
if(tmphead != fifo._read) { /* if buffer is not full */ \
fifo._write = tmphead; /* store new index */ \
fifo._buffer[tmphead] = data; /* store data in buffer */ \
} \
}

#define FIFO64_read(fifo) FIFO_read(fifo, 64)
#define FIFO64_write(fifo, data) FIFO_write(fifo, data, 64)

#define FIFO128_read(fifo) FIFO_read(fifo, 128)
#define FIFO128_write(fifo, data) FIFO_write(fifo, data, 128)

#endif /*FIFO_H_*/
</syntaxhighlight>

== Weblinks ==
* [http://en.wikipedia.org/wiki/Circular_buffer Circular buffer], englische Wikipedia

[[Kategorie:Grundlagen]]
[[Kategorie:Datenübertragung]]
[[Kategorie:Algorithmen und Arithmetik]]
[[Kategorie:Speicher und Dateisysteme]]