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...
Die Frage ist, wie formal möchtest du das haben ... Als C-Pseudo-Code würde das in etwa so aussehen:
1 | int state=0; |
2 | while (1) { |
3 | int input = getNextBit(); |
4 | switch (state) { |
5 | case 0: |
6 | if (!input) |
7 | state=1; |
8 | break; |
9 | case 1: |
10 | if (input) |
11 | state=2; |
12 | break; |
13 | case 2: |
14 | if (input) |
15 | state=3; |
16 | else |
17 | state=1; |
18 | break; |
19 | case 3: |
20 | if (!input) |
21 | state=4; |
22 | else |
23 | state=0 |
24 | break; |
25 | case 4: // "0110" erkannt! |
26 | if (!input) |
27 | state=2; |
28 | else |
29 | state=0; |
30 | break; |
31 | } |
32 | } |
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 ...
:
Bearbeitet durch User
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!
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^^
:
Bearbeitet durch User
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?
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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.