Impulsforgeerkennung und Automat

[SchalterAnAus (Gast)]

Hi ich habe eine Frage zur Impulserkennung und zum Moore Automaten,

also gegeben ist die Aussage:
Eine Schaltung soll eine Musterfolge von 0 und 1 erkennen. Eine Folge 
kann die Struktur X = 0110 haben. 0 wäre dann links das führende Bit und 
wird eingetaktet.

Ich habe schon ein paar Übungen zu Automaten gemacht, leider komme ich 
hier aber einfach nicht weiter. Auch verstehe ich diese "Impuls" 
Erkennung nicht wirklich und was das mit der Folge zu tun haben soll.

Vielleicht kann einer von euch Licht ins Dunkle bringen...

[Mampf F. (mampf)]

Die Frage ist, wie formal möchtest du das haben ...

Als C-Pseudo-Code würde das in etwa so aussehen:

int state=0;
while (1) {
  int input = getNextBit();
  switch (state) {
  case 0:
    if (!input)
      state=1;
    break;
  case 1:
    if (input)
      state=2;
    break;
  case 2:
    if (input)
       state=3;
    else
       state=1;
    break;
  case 3:
    if (!input)
      state=4;
    else
      state=0
    break;
  case 4: // "0110" erkannt!
    if (!input)
      state=2;
    else
      state=0;
    break;
  }
}

Es scheint mir so zu sein, dass man erst im State 4 ankommt, wenn "0110" 
erkannt wurde.

Wurde z.B. ein "010" erkannt, dann wäre der Automat in State 1. Dann 
würde noch ein "110" fehlen, um in den State 4 zu gelangen.

Der Sinn ist, dass du quasi beliebig Bits als Eingang hast und der 
Automat im State4 lande, sobald er irgendwann mal ein "0110" sieht. Das 
kann dann auch ein "0000010110" sein ...

0 => state 1
0 => state 1
0 => state 1
0 => state 1
1 => state 2
0 => state 1
1 => state 2
1 => state 3
0 => state 4

So wird dann das Bitmuster erkannt :)

Was die "Impuls-Erkennung" angeht, kann man das mit einem praktischen 
Beispiel evtl erklären.

Stell dir vor, du hast einen µController und an seinem Eingang sitzt 
irgendetwas, das Impulse von sich gibt.

Es können aber Störimpulse auch vorkommen oder meisten gibt er womöglich 
garkeine Impulse raus und der µC liest nur 0.

Jetzt weißt du, dass du z.B. ein IR-Empfänger hast, der beim Empfangen 
von Infrarot einen Impuls von sich gibt, der beim einlesen mindestens 
als "11" gelesen werden würde. Kurze Störungen wären kürzer und würden 
z.B. als "010" gelesen, aber du möchtest den Impuls. Der ist länger 
sagst du und weil du ja einen Impuls möchtest, könntest du das Bitmuster 
"0110" erkennen wollen. Der Automat würde das quasi direkt machen.

Man könnte ihn erweitern, in dem man sagt, man möchte zwischen den 
Impulsen noch eine gewisse Ruhezeit und möchte nur "0000110000" erkennen 
oder soetwas ...

[SchalterAnAus (Gast)]

Danke für deine ausführliche und gute Antwort.

Also er geht in einen Anderen Zustand über wenn er 0110 findet, das habe 
ich mir erklären können da ja von 000 zu 001 gesprungen wird wenn der 
Automat eine 0 (an erster Stelle) hat.

Aber warum springt er bei 010 auf 001, wenn es eine 0 ist?
Und warum springt er von 011 auf 000, wenn es eine 1 ist?
das erschließt sich mir noch nicht ganz...

Das kann ich mir nur mit:
"Der Sinn ist, dass du quasi beliebig Bits als Eingang hast und der
Automat im State4 lande, sobald er irgendwann mal ein "0110" sieht. Das
kann dann auch ein "0000010110" sein ..."
erklären.

Nur woher weiß ich, dass man das auch genauso zeichnen muss. Als 
Beispiel der Sprung von 011 auf 000. Dieses Springen auf den Anfang 
erschließt sich mir da nicht.

Aber das ist schon interessant, dass du aus dem kurzen Aufgabentext das 
richtig interpretiert hast!

[Mampf F. (mampf)]

SchalterAnAus schrieb:
> Aber warum springt er bei 010 auf 001, wenn es eine 0 ist?
> Und warum springt er von 011 auf 000, wenn es eine 1 ist?
> das erschließt sich mir noch nicht ganz...

Naja, wenn er 010 erkannt hat, dann könnte die letzte 0 ja bereits Teil 
der Bitmusters "0110" sein ... Das wäre dann so, als hätte er bisher nur 
"0" erkannt, weil der Rest ist ja schon falsch. Dann wartet er noch auf 
"110" im Anschluss.

quasi: 010 => 01|0 ... Das | soll ein Schnitt interpretieren, wo er 
alles davor quasi weg wirft. Die 0 danach ist aber Teil des Bitmusters, 
das der Automat sucht, dann muss er ja danach schon im State 1 sein :)

Genauso bei 0111 => Alles murks ... Also zurück zu State 0.

SchalterAnAus schrieb:
> Nur woher weiß ich, dass man das auch genauso zeichnen muss. Als
> Beispiel der Sprung von 011 auf 000. Dieses Springen auf den Anfang
> erschließt sich mir da nicht.

Reine Logik ... Das Bitmuster "0111" ist kein Präfix des gesuchten 
Bitmusters, d.h. der Automat muss von vorne neu suchen :) und "111" 
kommt auch nicht im Bitmuster vor, d.h. das verwirft der Automat 
vollständig :) Bei "011101" würde er im State 2 landen^^

[Possetitjel (Gast)]

SchalterAnAus schrieb:

> Also er geht in einen Anderen Zustand über wenn er 0110
> findet, das habe ich mir erklären können da ja von 000
> zu 001 gesprungen wird wenn der Automat eine 0 (an erster
> Stelle) hat.

??

Dein Mustererkennungsautomat hat immer drei Moeglichkeiten:
1. Er bleibt im gegenwaertigen Zustand.
   Das macht er im Startzustand, wenn er noch keinen gueltigen
   Anfang erkannt hat.
2. Er geht zum Folgezustand, wenn das naechste fuer das Muster
   notwendige Zeichen auch tatsaechlich eingetroffen ist.
3. Er geht zum Startzustand zurueck, wenn das gerade neu
   eingetroffene Zeichen NICHT das fuer das Muster notwendige
   Zeichen ist.

Ein Problem entsteht nur daraus, dass ein "falsches" Zeichen
zwar nicht zum bisherigen Muster passt, aber schon gleich das
erste Zeichen eines spaeteren Auftretens des Muster sein
kann.
(Deswegen gibt es in der Beispielloesung nicht DEN einen Start-
zustand, sondern eigentlich zwei Startzustaende.)

> Aber warum springt er bei 010 auf 001, wenn es eine 0 ist?

Weil die Zustaende bloed bezeichnet sind :)

Man sollte die Zustande einfach A, B, C... nennen. Die
Zustandscodierung ist ohnehin wahlfrei.

Hier im Beispiel ist Zustand 0 ("000") der Startzustand,
Zustand 1 ("001") der Zustand "fuehrende Null erkannt",
Zustand 2 ("010") der Zustand "erste Eins erkannt". Und
wenn nach der ersten Eins eine Null eintrifft, kann das
gesuchte Muster nicht mehr zustandekommen. Diese neue Null
kann aber wohl die erste Null eines spaeter eintreffenden
Musters sein, daher der Uebergang zu Zusand 1.

> Und warum springt er von 011 auf 000, wenn es eine 1 ist?
> das erschließt sich mir noch nicht ganz...

Naja, wenn auf die bisherige Eingangsfolge "011" eine weitere
Eins folgt, dann kann halt das Suchmuster nicht entstehen. Also
zurueck auf den Startzustand.

> Das kann ich mir nur mit:
> "Der Sinn ist, dass du quasi beliebig Bits als Eingang hast
> und der Automat im State4 lande, sobald er irgendwann mal
> ein "0110" sieht. Das kann dann auch ein "0000010110" sein ..."
> erklären.

Ja, richtig.

> Nur woher weiß ich, dass man das auch genauso zeichnen muss.

In Leipzig: "Entschuldigen Sie, wie komme ich denn in's Gewandt-
haus?" -- "Tja, junger Mann, da hilft nur: Ueben, ueben, ueben!"

> Als Beispiel der Sprung von 011 auf 000. Dieses Springen auf
> den Anfang erschließt sich mir da nicht.

Gegenfrage: Wenn nach den Zeichen "011" eine weitere Eins eintrifft,
was sollte der Automat Deiner Meinung nach machen?

[SchalterAnAus (Gast)]

Hi und danke euch für die klasse Antworten.

Ihr habt mir wieder gut geholfen!!!

Aber das muss man wirklich ein paar mal üben. ich hatte aus einem 
Elektronik Buch für die Uni noch eine Beispielaufgabe gefunden, die war 
bei weitem besser beschrieben und mit ein wenig Grübeln lösbar.