« »

GRABS Übungsaufgaben Automaten und Schaltwerke Schneckenglück

Schneckenglück

Gegeben sei eine Roboterschnecke mit einem endlichen Automaten als Gehirn. Die Schnecke kriecht von links nach rechts über ein Papierband mit Nullen und Einsen und liest ein Bit pro Takt.

Die Schnecke lächelt, bis der nächste Taktzyklus beginnt, sobald die letzten drei überfahrenen Bits 110 oder 101 waren. Wenn die Schnecke gelächelt hat, will sie wieder eine komplett neue 3-Bit-Folge sehen, bevor sie erneut lächelt. Entwerfen Sie einen endlichen Automaten, welcher die Schnecke in den richtigen Momenten zum Lächeln bringt.

Diese Aufgabe stammt aus Kapitel 3, Beispiel 3.7 von "Digital Design and Computer Architecture. RISC-V Edition." (Harris & Harris, 2022).

a)

Level 3: Anwenden

Entwerfen Sie zuerst ein passendes Zustandsübergangsdiagramm für einen Moore-Automaten. Versuchen Sie dabei, so wenig Zustände wie möglich zu verwenden.

Lösung
  • zuerst das Zustandsübergangsdiagramm bestimmen
  • insbesondere die Kante Q4 nach Q1 ist evtl. nicht sofort offensichtlich

b)

Level 1: Wissen

Kodieren sie die Zustände in Binärform und geben Sie die Zustandsübergangstabelle an.

Lösung

Zustandsübergangstabelle aus dem Zustandsübergangsdiagramm ableiten:

ZustandAFolgezustand
Q00Q0
Q01Q1
Q10Q3
Q11Q2
Q20Q4
Q21Q2
Q30Q0
Q31Q4
Q40Q0
Q41Q1

Zustände binär kodieren (fünf Zustände → drei Bits):

S2S1S0AS2'S1'S0'
0000000
0001001
0010011
0011010
0100100
0101010
0110000
0111100
1000000
1001001
  • S2, S1 und S0 bilden die Bits des Ausgangszustands (000 für Q0, 001 für Q1 …)
  • analog kodieren S2', S1' und S0' den Folgezustand

c)

Level 3: Anwenden

Leiten Sie zuletzt aus der Zustandsübergangstabelle die Zustandsübergangsgleichungen ab. Nutzen Sie die Regeln der Booleschen Algebra aus der Vorlesungen, um die Gleichungen später ressourcensparend verwirklichen zu können.

Lösung

Vorgehensweise:

  • für jedes Bit des Folgezustands wird eine Schaltung entwickelt
  • wir betrachten die einschlägigen Zeilen (also, wo beim Folgezustandsbit eine 1 steht)
  • daraus leiten wir Gleichungen ab (vgl. Übung zur Schaltungsminimierung)

Bei S2' ist der Trick, zu erkennen, dass der hintere Term durch das EQUIV-Gatter dargestellt werden kann:

S2' = /S2*S1*/S0*/A + /S2*S1*S0*A 
    = /S2*S1*(/S0*/A + S0*A)

Bei S1' ist der Trick, zu erkennen, dass Bit S2 nicht relevant ist:

S1' = /S2*/S1*S0*/A + /S2*/S1*S0*A + /S2*S1*/S0*A
    = /S2 * (/S1*S0*/A + /S1*S0*A + S1*/S0*A)       → /S2 kann gestrichen werden
    = /S1*S0*/A + /S1*S0*A + S1*/S0*A
    = S0 * (/S1*A + /S1*/A) + S1*/S0*A              → Resolution
    = /S1*S0 + S1*/S0*A

Bei S0' wird zuerst /S1 ausgeklammert und danach /S0 A:

S0' = /S2*/S1*/S0*A + /S2*/S1*S0*/A + S2*/S1*/S0*A
    = /S1*(/S2*/S0*A + /S2*S0*/A + S2*/S0*A)
    = /S1*(/S0*A*(/S2+S2) + /S2*S0*/A)
    = /S1*(/S0*A + /S2*S0*/A)

d)

Level 1: Wissen

Entwerfen Sie mit Hilfe der Zustandsübergangsgleichungen die Logikschaltungen für die jeweiligen Bits des Folgezustandes.

Lösung

Wichtig bei S2' ist, dass EQUIV äquivalent zu XOR und NOT ist.

Die Logikschaltung von S1' besteht aus zwei AND-Gattern und einem OR-Gatter.

Für S0' ergibt sich folgende Schaltung:

Lernziele

In dieser Aufgabe …

  • üben die Studierenden die Umsetzung einer Schaltung.
  • festigen die Studierenden ihr Verständnis von Automaten.
  • wenden die Studierenden ein einfaches Verfahren zur Schaltungssynthese aus Wertetabellen an.