Grundlagen der Informatik 2 Grundlagen der Digitaltechnik ... · PDF filejeweilige Folgezustand und die Ausgabe, beim Moore-Automaten nur der Folgezustand eingetragen Mealy Moore S

Grundlagen der Digitaltechnik

Grundlagen der Informatik 2Grundlagen der Informatik 2Grundlagen der DigitaltechnikGrundlagen der Digitaltechnik

6. Automaten und Schaltwerke6. Automaten und Schaltwerke

Prof. Dr.Prof. Dr.--Ing. Jürgen TeichIng. Jürgen TeichDr.Dr.--Ing. Christian Ing. Christian HaubeltHaubelt

Lehrstuhl für HardwareLehrstuhl für Hardware--SoftwareSoftware--CoCo--DesignDesign

Grundlagen der Digitaltechnik 2

Automaten Automaten -- MotivationMotivation

• Schaltnetze: Bilden Ausgangsgrößen unmittelbar aus (als Funktion von) Eingangsgrößen

• Nachteil: Keine Zustände darstellbar

• Notwendig: ein neues Konzept, welches die Möglichkeit hat, Zustände zu speichern und die Ausgabe abhängig vom Zustand des Systems zu beschreiben

• Dieses Konzept basiert auf dem Modell von Automaten, deren Realisierungen wir als Schaltwerk bezeichnen.


Beispiel: GetränkeautomatBeispiel: Getränkeautomat

• Ein dümmlicher Getränkeautomat erwartet, dass man im ersten Schritt einen Euro einwirft und dann im zweiten Schritt eines von zwei möglichen Getränken auswählt.

• Verhält man sich anders, zeigt der Automat keine Reaktion.

• Man kann aber auf den Rückgabeknopf drücken.

• Dann gibt der Automat das Geld zurück, für das er keine Ware geliefert hat.


Automaten Automaten -- AllgemeinAllgemein

• Gegeben:– endliches Eingabealphabet: E = { E1, E2, ... , Eg, ... , Eu }– endliches Ausgabealphabet: A = { A1, A2, ... , Ah, ... , Av }

• Ein Automat ist eine Einheit AT, bei der eine zeitliche Folge von Elementen des Eingabealphabets FE in eine zeitliche Folge von Elementen des Ausgabealphabets FA abgebildet wird:

• Zur Unterscheidung zeitlicher Reihung: Einführung eines Ordnungsindizes ν: FE = Eg

ν Egν-1 Eg

ν-2 ... FA = Ahν Ah

ν-1 Ahν-2 ...

FE ⇒ AT ⇒ FA



• Eingabealphabet: E = { m (Euro einwerfen),

w1 (Sorte 1 wählen), w2 (Sorte 2 wählen), r (Geldrückgabe

anfordern)}• Ausgabealphabet:

A = { g (Geld zurück), k (keine Reaktion), a1 (Sorte 1 ausgeben), a2 (Sorte 2 ausgeben)}



• Für die neue Einheit AT muss gelten:

Ahν = f ( Eg

ν, Egν-1, Eg

ν-2, ... , Egν-α )

– insgesamt werden α+1 Elemente des Eingabealphabets beobachtet– α ist die zeitliche Tiefe der Verarbeitung



• Nachteil dieses Konzeptes: Speicherung von αEingabeelementen erforderlich, um Ah

ν zu berechnen:

• Erhalt eines neuen Elements -> ältestes Element Egν-α

entfällt aus Folge mit Länge (α+1)

vgE v

hA

AT

...

gEv-1

gE

v-agE

fv-2



• Bei Normierung der Indizes dem Alter nach erhält man:

ανανννν −+−−− g

1 g

2g

1gg E .....E E E E

αναννννν −+−−−+ g

1 g

2 g

1 gg

1 g E E ..... E E E E

αναννννν −+−−−+ g

1 g

2 g

1 gg

1 g E E ..... E E E E

ανανννν −+−−− g

1 g

2 g

1 gg E E ..... E E Eν+1 ⇒ ν:

ν:

ν+1:

ν+1: reduziert

normiert



• Weiterhin: Abbildung der Folge Egν-1 ... Eg

ν-α auf ein neues Alphabet S = { S1, ... , Sk, ... , Sw } mit geringerer Mächtigkeit:

( Egν-1 ... Eg

ν-α ) → S, mit ⏐E⏐α ≥ ⏐S⏐• Das Element Sk wird Zustand des Automaten AT genannt• Unter Beachtung der zeitlichen Reihung erhält man nun:

Ahν = λ ( Eg

ν, Skν )

mit λ als Ausgabefunktion des Automaten AT



• Bei Eingabe eines neuen Eingabeelements Egν ergibt sich

unter Berücksichtigung des aktuellen Zustands(sogenante “Historie der Eingaben“):

Skν+1 = δ ( Eg

ν, Skν )

mit δ als Überführungsfunktion der Zustände- Kennzeichnung der Einheit AT als Quintupel

AT = ( E, A, S, δ, λ )mit drei endlichen Mengen und zwei Abbildungenzwischen diesen Mengen



• Zustandsmenge:S = {s1, s2}

• Darstellung der Überführungs- und Ausgabefunktion durch eine Tabelle:

δ / λ

s2 / k s1 / k s1 / ks1

w1rm

s2 / k s1 / g s1 / a1s2

s1 / k

w2

s1 / a2



• Darstellung eines Automaten durch folgende Struktur:

- rekursive Anordnung für die Bestimmung des neuen Zustandes- der Speicher nimmt den momentanen Zustand Sk

ν auf- der neue Zustand Sk

ν+1 muss zum richtigen Zeitpunkt übernommen werden

Skν+1Sk

ν

Egν

Ahν

λ

δ

Speicher


AutomatentypenAutomatentypen

• Wichtige Typklassen von Automaten im Zusammenhang mit Digitalschaltungen: endliche, diskrete und deterministische Automaten

• Bezüglich der Ausgabefunktion von Egν und Sk

ν

unterscheidet man drei Fälle: - Mealy-Automat mit Ah

ν = λ ( Egν, Sk

ν ) als allgemeinster Fall:

Skν+1Sk

ν

Egν

Ahν

λ

δ

Speicher


AutomatentypenAutomatentypen

- Moore-Automat mit Ahν = λ ( Sk

ν ) als ein Spezialfall, bei dem die Ausgabe allein vom Zustand abhängt

- Medwedew-Automat mit Ahν = Sk

ν als dem Spezialfall, bei dem als Ausgabe der Zustand selbst dient

Skν+1Sk

ν

Egν

Ahν

λ

δ

Speicher

Skν+1Sk

ν

Egν

Ahνδ

Speicher


AutomatengraphenAutomatengraphen

• Knoten repräsentieren Zustände, Kanten als Zustandsübergänge

• Beide Elemente des Graphen werden mit Attributenversehen, die sich auf Eingangs- und Ausgangselementebeziehen:

Mealy

Sν E /A

ν ν

Sν+1

k k

g h

Moore

Eν

+1νS /A

+1νννS /Ak k

ghh


Beispiel Beispiel MealyMealy--AutomatAutomat

E /A2 1

E /A1 2 E /A2 2

E /A11E /A2

E /A2 3

E /A1 2

3S

4SS2

1S

E /A1 1

3


Beispiel MooreBeispiel Moore--AutomatAutomat

E ,E1 2

E1

E1

E2

E ,E212 1S A/

/1S 1A /3S 2A

4 3S A/

E2


AutomatentafelnAutomatentafeln

• Bilden des kartesischen Produktes aus Eingabe- und Zustandsmenge

• An Kreuzungsstellen werden beim Mealy-Automaten der jeweilige Folgezustand und die Ausgabe, beim Moore-Automaten nur der Folgezustand eingetragen

Mealy

Moore

Sν+1/Aν Sν+1

Sν E1ν .. . En

ν Sν E1ν .. . En

ν Aν

.. . .. . .. . .. .

Sν .. . Skν+1/Ah

ν .. . Sν .. . Skν+1 .. . Ah

ν

.. . .. . .. . .. .

Moore


AutomatentafelnAutomatentafeln

• Beispiele:

Sν+1/Aν Sν+1

Sν E1 E2 Sν E1 E2 Aν

S1 S2/A2 S4/A2 S1 S2 S4 A1

S2 S3/A1 S2/A1 S2 S3 S2 A1

S3 S4/A1 S4/A3 S3 S4 S4 A2

S4 S2/A2 S2/A3 S4 S2 S2 A3


SchaltwerkeSchaltwerke

• Die technische Realisierung eines endlichen, diskreten und deterministischen Automaten wird Schaltwerkgenannt (im Gegensatz zum “gedächtnislosen“ Schaltnetz)

• Unterscheidung zwischen Mealy-, Moore- und Medwedew-Schaltwerken beim Übergang vom Automaten zum Schaltwerk ist eine eineindeutige Abbildung der Automatenelemente in binäre Größen (Bit-Leitungen) erforderlich:

E ↔ { Xj } mit ⏐E⏐ ≤ 2n bei X = ( xn, ... , x1 )A ↔ { Yi } mit ⏐A⏐ ≤ 2m bei Y = ( ym, ... , y1 )



• Neu: Eineindeutige Abbildung der Zustände Sk der Menge S in die Menge der Belegungen eines weiteren Binärvektors, des Zustandvektors Q:

S ↔ { Qk } mit ⏐S⏐ ≤ 2r bei Q = ( qr, ... , q1 )• Zustandskodierung, λ und δ werden als Schaltnetze

abgebildet• Spezifikation von Schaltwerken:

Automatengraphen und Automatentafeln-> entsprechende Automatenelemente werden durch ihre

binäre Äquivalente ersetzt



• Weiterhin: Formal eingeführte Indizierung ν der zeitlichen Ordnung muss nun in technische Realisierung überführt werden: Rückführung der Zustände über einen Speicher

• Schaltwerke, bei denen Rückführungen direkt wirksamwerden, heißen asynchron.

Speicher

g

Sν

S +1ν

x = konstant



• Als zusätzliches informationsfreies Binärsignal wird der sogenannte Takt c benötigt

• Auftrennung und partielle Weiterleitung des Zustandesbzw. Folgezustandes → Zustandsspeicher in zwei Teilspeicher zerlegen

– Funktion: c = 0: (Teilspeicher 1) = Sν+1

c = 1: (Teilspeicher 2) = (Teilspeicher 1)immer: Sν = (Teilspeicher 2)Tor 1 und Tor 2 sind nie gleichzeitig aktiv

Teil- speicher

1

Teil- speicher

2

T O R 1

T O R 2

MasterSlave

Sν+1Sν

Takt c



• Schaltwerke mit taktgesteuerten Speichern werden getaktet betrieben genannt

• Ist der Takt an allen Schaltungsteilen gleichzeitig aktiv,spricht man von einem synchronen Schaltwerk

• Mealy-Automat: Änderung der Eingabe bewirkt asynchrone Ausgabenberechnung.

• Die Zählung des Indexes ν muss aus dem Taktsignal abgeleitet werden


TaktsteuerungsartenTaktsteuerungsarten

ν

t

νt

t

νt

t

. . .νν-1

ν+1 . . .

ν+1 . . .

. . .

ν-1. . . ν +1 . . .

1

0

Schaltwerk c

c

Schaltwerk c

Schaltwerk c

Schaltwerk c

1

0

1

0

1

0

t ν t +1ν

tν

t +1 νν

t ν +1

tν t +1ν

c

c

c

pegelgesteuert:

pegelgesteuert:

flankengesteuert:

flankengesteuert:


Binärspeicher (Flipflops) Binärspeicher (Flipflops) -- WiederholungWiederholung

• Binärspeicher werden zur Speicherung von Zuständender Schaltwerke benötigt

• Ist ⏐S⏐ die Zahl der Zustände, berechnet sich die Größedes Binärvektors Q zu r = ⎡ld⏐S⏐⎤ mit Q = ( qr, ... , qk, ... , q1 ) mit qk einer beliebigen Zustandsvariable des Zustandsvektors- einzelne Zustandsvariablen qk werden rekursiv mit δ berechnet- eine zwei Werte speichernde Einheit wird als Binärspeicher

bezeichnet: FlipFlop- ein Speicher mit r FlipFlops kann 2r unterschiedliche Zustände

speichern


Binärspeicher (Flipflops) Binärspeicher (Flipflops) -- WiederholungWiederholung

• Grundsätzliche Funktionen eines Binärspeichers:– muss wahlweise eine 0 oder 1 eingespeichern können

(schreiben)– der Wert im Speicher muss extern zur Verfügung stehen (lesen)– Vorhandensein eines Taktes: Rekursion (ν+1 => ν) muss vom

Binärspeicher unter Einwirkung des Taktes verwirklicht werden

• Wir kennen: verschiedene Varianten der Binärspeichermit verschiedenen Ansteuerfunktionen


FlipflopFlipflop--Varianten (Wiederholung)Varianten (Wiederholung)Fall 1: RS-FlipFlop

Lesesignal =̂ Zustandswert:

qk

∈ {0,1}

Schreiben einer 0, Rücksetzen:

R {0,1} 0 =̂ inaktiv 1 =̂ Schreiben 0

Schreiben einer 1, Setzen:

S {0,1} 0 =̂ inaktiv1 =̂ Schreiben 1

∈

∈

Fall 2: D-FlipFlop

Lesesignal =̂ Zustandswert:

qk

{0,1}

Datensignal =̂ Zustandswert neu:

D {0,1}

Schreiben des Wertes von D:

W {0,1} 0 =̂ inaktiv

1 =̂ Schreiben

∈

∈

∈

Das gleichzeitige Schreiben von 0 und 1 (R=1, S=1) beim RS-FlipFlopist unzulässig


FlipFlopsFlipFlops (Wiederholung)(Wiederholung)

Dq 1 =ν+

Symbole

q

qR

S

q

q1R

1SC1

q

q

1D

C1

Charakteristische Gleichungen Ansteuerfunktionen

qν qν+1 R S

0 0 - 0 0 1 0 1 1 0 1 0 1 1 0 -

qν qν+1 D

0 0 0 0 1 1 1 0 0 1 1 1

RS-FlipFlop

D-FlipFlop

)R&q(Sq 1 ν+ν ∨=


FlipFlopsFlipFlops (Wiederholung)(Wiederholung)

)q&T()q&T(q 1 νν+ν ∨=

Symbole Charakteristische Gleichungen Ansteuerfunktionen

q

q

1J1K

C1

q

q

1TC1

q ν q ν+1 J K

0 0 0 -0 1 1 -1 0 -

01 1 -

q ν q ν+1 T

0 0 0 0 1 1 1 0 1 1 1 0

T-FlipFlop

JK-FlipFlop

)q&J()q&K(q 1 νν+ν ∨=

1


Entwurf von SchaltwerkenEntwurf von Schaltwerken

• Vorgehensweise:– 1. Schritt: Definition und Kodierung der Ein- und

Ausgabevariablen– 2. Schritt: Wahl des Schaltwerktyps und Erstellen der

Automatentafel oder Zustandsgraphgemäß Aufgabenstellung

– 3. Schritt: Zustandskodierung– 4. Schritt: Wahl des FlipFlop-Typs und Aufstellen der

Ansteuerfunktionen– 5. Schritt: Entwurf des Schaltnetzes für die Überführungs-

funktion auf der Basis der Ansteuerfunktionen– 6. Schritt: Entwurf des Schaltnetzes für die Ausgabefunktion– 7. Schritt: Eventuell Umformung der logischen Ausdrücke in

geeignete Strukturausdrücke– 8. Schritt: Umsetzen in das Schaltbild des Schaltwerkes



• 1. Schritt:• Eingabeereignisse:

– Münze eingeworfen: m– Geldrückgabe: r– Getränkewahl 1 w1– Getränkewahl 2 w2

• Ausgabeereignisse:– keine Aktion k– Geldauswurf g– Getränkeausgabe 1 a1– Getränkeausgabe 2 a2



• Definition und Kodierung der Eingaben: |E| = 4 = 22. Deshalb sind n=2 Variablen notwendig:X = (x2,x1).

• Definition und Kodierung der Ausgaben:|A| = 4 = 22. Deshalb sind m=2 Variablen notwendig:Y = (y2,y1).

y2 y1

0 0011

101

kga1a2

x2 x1

0 0011

101

mr

w1w2



• 2. Schritt:• Wahl des Schaltwerktyps:

– Mealy(Der Ausgang hängt vom aktuellen Zustand und von den Eingängen ab)

s1 s2

m/ k

m/ kw1/ a1

w2 / a2

r / g

w1 / k

w2/ k

r / k



• 3. Schritt:• Zustandskodierung:

– |S| = 2 = 21 Zustände. Deshalb ist r = 1 Zustandsvariable notwendig: Q = (q).

– Kodierung der beiden Zustände s1 und s2:

q

01

s1s2



• 4. Schritt:• FlipFlop-Typ:

– D-FlipFlop• Automatentafel mit kodierten Ein-, Ausgaben

und Zuständen:X=(x2 ,x1)

1/(0,0) 0/(0,0) 0/(0,0) 0/(0,0)1/(0,0) 0/(0,1) 0/(1,0) 0/(1,1)1

0(0, 0) (0, 1) (1, 0) (1, 1)

m r w1 w2δ/λ

(s1)(s2)Q

=(q)

Y=(y2,y1)



• Ansteuerfunktion des D-Flipflops:

+ x2 • x1 • q

1 0 0 01 0 0 01

0(0, 0) (0, 1) (1, 0) (1, 1)

m r w1 w2δ

(s1)(s2)Q

=(q)

(0,1) (1, (1,1)(0,0) (0,0) (0,0) (0,0)(0,0) 0)1

0(0, 0) (0, 1) (1, 0) (1, 1)

m r w1 w2λ

(s1)(s2)Q=(

q)

• Ausgabefunktion D = x2 • x1 • q

+ x2 • x1 • q y2 = x2 • x1 • q y1 = x2 • x1 • q + x2 • x1 • q



• 5. Schritt:• KV-Diagramm für

Überführungsfunktion δ:

x21 0 0 1

0000x1

D:

⇒ D = x1 • x2



• 6. Schritt:• Entwurf der Schaltnetze für die

Ausgabefunktion(en) λ:

x20 0 0 0

1100q

x1

y1:

y1 = q • x1⇒

x20 0 1 0

0100q

x1

y2:

y2 = q • x2⇒


λ

δ


• 7. Schritt: entfällt.• 8. Schritt:• Schaltbild des Schaltwerkes:

Achtung: Der Takt muss so gestaltet sein, dass eine Vorderflanke nur im Falle einer Eingabeänderung erzeugt wird!

11

1D& qx2x1

C1

&

&

Takt

y2

y1


Spezielle SchaltwerkeSpezielle Schaltwerke

• Zähler– Zähler-Schaltwerke dienen dazu, auf einer speziellen

Signalleitung beobachtete Ereignisse zu zählen– Das Zählen entspricht einer Abbildung in den

Zustandsraum, so dass ein Zählcode entsteht– Wie bei mechanischen Zählern können noch weitere

Eingriffmöglichkeiten eingebaut werden:• Überlaufmeldung• Nullstellungsmeldung• Rückstellmöglichkeit auf 0


DualzählerDualzähler

• Beispiel:– Es soll ein Zähler als Schaltwerk realisiert werden, der...

• dual zyklisch von 0 bis 7 zählt• eine Rückstellmöglichkeit auf 0 besitzt• bei dem Wert 7 das Überlaufsignal auf 1 setzt• auf den Wechsel der Zählervariablen Z von 0 auf 1 reagiert

– Zur Realisierung sollen JK-Flipflops mit 0/1-Flankensteuerung verwendet werden



• Beispiel:– Eingangsvariable:

N = 1: Rückstellen auf 0N = 0: sonst

– Ausgangsvariable:Ü = 1: Zählerstand ist 7Ü = 0: sonst

– Bei Zählern wird die Zählervariable Z häufig nicht als Eingangsvariable, sondern direkt als Taktsignal angeschlossen

– Das Zählereignis „Wechsel von 0 auf 1“ kann so direkt mit einem synchronen Schaltwerk mit positiver Flankensteuerungrealisiert werden



• Schaltwerkstabelle:– Die Kodierung der

Zustände ist die duale Zahlendarstellung

– Bei N = 1 ist der Folgezustand auf jeden Fall0 (Rücksetzen)

– Die Übertragungsfunktionkann direkt abgelesen werden:

Qυ Xυ Qυ+1 Yυ

q3 q2 q1 N q3 q2 q1 Ü0 0 0 0 0 0 1 00 0 0 1 0 0 0 00 0 1 0 0 1 0 00 0 1 1 0 0 0 00 1 0 0 0 1 1 00 1 0 1 0 0 0 00 1 1 0 1 0 0 00 1 1 1 0 0 0 01 0 0 0 1 0 1 01 0 0 1 0 0 0 01 0 1 0 1 1 0 01 0 1 1 0 0 0 01 1 0 0 1 1 1 01 1 0 1 0 0 0 01 1 1 0 0 0 0 11 1 1 1 0 0 0 1

ννν123 qqqÜ &&=


DualzählerDualzählerQυ Xυ Qυ+1 Yυ

q3 q2 q1 N q3 q2 q1 Ü J3 K3 J2 K2 J1 K1

0 0 0 0 0 0 1 0 0 - 0 - 1 -0 0 0 1 0 0 0 0 0 - 0 - 0 -0 0 1 0 0 1 0 0 0 - 1 - - 10 0 1 1 0 0 0 0 0 - 0 - - 10 1 0 0 0 1 1 0 0 - - 0 1 -0 1 0 1 0 0 0 0 0 - - 1 0 -0 1 1 0 1 0 0 0 1 - - 1 - 10 1 1 1 0 0 0 0 0 - - 1 - 11 0 0 0 1 0 1 0 - 0 0 - 1 -1 0 0 1 0 0 0 0 - 1 0 - 0 -1 0 1 0 1 1 0 0 - 0 1 - - 11 0 1 1 0 0 0 0 - 1 0 - - 11 1 0 0 1 1 1 0 - 0 - 0 1 -1 1 0 1 0 0 0 0 - 1 - 1 0 -1 1 1 0 0 0 0 1 - 1 - 1 - 11 1 1 1 0 0 0 1 - 1 - 1 - 1

• Ansteuerfunktionen:– durch Ablesen oder

mit Hilfe von Symmetrie-diagrammenerhält man:

νν

ν

123

12

1

qqNKqNK

1K

∨=

∨=

=

νν

ν

123

12

1

qqNJ

qNJ

NJ

=

=

=


• Blockschema des Zählers:

≥1

1

&

&

≥1

C11K

1J

C11K

1J

C11K

1J

&Ü

N

q3

q2

q1

"1"

Zähler-stand

J 1

K 1

J 2

K 2

K 3

J 3

c

νν

ν

123

12

1

qqNKqNK

1K

∨=

∨=

=

νν

ν

123

12

1

qqNJ

qNJ

NJ

=

=

=

• Ansteuerfunktionen:




• Symboldarstellung:– Um bei Zählern von Realisierungsdetails zu abstrahieren,

führt man Blocksymbole ein– Das Symbol besteht aus einem Daten- und einem Steuerteil– Für das besprochene Beispiel sieht der Zähler so aus:

RCT=7 Ü

Nc

q3

q2

q1



• Eigenschaften:– Hier noch die wichtigsten Merkmale von Zählern:

• Art des Zählcodes-> Dualzahlen, 1-aus-n-Code, BCD-Code,...

• Art des Zählerreignisses-> 0->1, 1->0, Auftreten von Werten, ...

• Steuersignal für Zählen/Anhalten

• Steuersignal für Zählrichtung (aufwärts/abwärts)

• Synchrone oder asynchrone Rückstellmöglichkeit

• Steuersignal für Zählen/Laden eines Anfangswertes

Documents

Grundlagen der Informatik 2 Grundlagen der Digitaltechnik ... · PDF filejeweilige Folgezustand und die Ausgabe, beim Moore-Automaten nur der Folgezustand eingetragen Mealy Moore S