7 Schaltwerke und Automaten Folie 1
Grundlagen der Technischen Informatik 1 Version: WS07/08
7. Schaltwerke und Automaten 7.1 Allgemeine Begriffe Bekannt:
1) Schaltnetze: Verknüpfung mehrerer Eingangsvariablen ohne Rückkopplung des Ergebnisses
2) Flipflops: Speicherfähigkeit durch Ausnutzung von Signalverzögerungen
3) Aufbau von Zählern aus Flipflops und Schaltnetzen
Neu: Bei einem Schaltwerk sind die Ausgänge von früheren Zuständen abhängig, d.h. es handelt sich um eine logische Schaltung, die sequentiell verschiedene Zustände durchläuft.
Schematische Darstellung von Schaltwerken über:
• verzögerungsfreies Schaltnetz und
• zusammengefasste Verzögerungen / Rückkopplung.
Variante I:
SchaltnetzVerzöge-rungs-einheit
X
SY
Rückkopplung
X = Xn = {X1n,X2
n,....Xmn } = Eingangsvektor mit den entspre-
chenden Variablen S = Sn = {S1
n,S2n,....Sr
n } = Zustandsvektor mit den entsprech-enden Variablen
Y = Yn = {Y1n,Y2
n,....Yln } = Ausgangsvektor mit den entspre-
chenden Variablen
7 Schaltwerke und Automaten Folie 2
Grundlagen der Technischen Informatik 1 Version: WS07/08
Variante II:
Y muss nicht identisch mit den rückgekoppelten Signalen sein:
Schalt-netz
Verzöge-rungsein-heit
X
S
E
Y
Verzöge-rung
zusätzlich E = En = {E1n,E2
n,...Ekn } = Erregungsvektor mit den
entsprechenden Variablen
Variante III:
Verzögerung von E nach Y hat keinen prinzipiellen Einfluss auf die Funktion des Schaltwerks, daher:
Schalt-netz
X
S
E X S=g( , )
Y X S=f( , )
Verzöge-rung
gf
7 Schaltwerke und Automaten Folie 3
Grundlagen der Technischen Informatik 1 Version: WS07/08
Funktionsgleichungen:
Y = f(X,S)
E = g(X,S)
Funktionsweise:
1 Änderung von X0 → X1 ⇒ Änderung von Y0 → Y1 und Änderung von E0 → E1
2 Änderung von E0 → E1 ⇒ Änderung von Y1 → Y2 und Änderung von E1 → E2
3 Iteration von 2. bis: Änderung von Ei → Ei+1 ⇒ Änderung von Yi+1 → Yi+2
und Stabilitätsbedingung Ei+1 = Ei
Alle Zwischenschritte nach 2. sind instabil, d.h. sie werden nur kurzzeitig durchlaufen.
7 Schaltwerke und Automaten Folie 4
Grundlagen der Technischen Informatik 1 Version: WS07/08
Analyse eines Schaltwerks auf stabile Zustände:
• Auftrennen der Verzögerung und
• Vergleich von S und E in vollständiger Funktionstabelle.
Beispiel:
X Y
1
>1
>1 1
Y2
Umzeichnen:
X
S
Y
1 >1
>1 1
Y2
Y
E
E
E
1
2
7 Schaltwerke und Automaten Folie 5
Grundlagen der Technischen Informatik 1 Version: WS07/08
E = f(X,S)
Y = E
Eingänge Ausgänge X S1 S2 E1 E2
n =1 0 0 0 1 0 n =2 0 0 1 0 0 n =3 0 1 0 1 0 n =4 0 1 1 0 0 n =5 1 0 0 0 1 n =6 1 0 1 0 1 n =7 1 1 0 0 0 n =8 1 1 1 0 0
1221 SXE SXE +=+=
Ergebnis:
• Schaltwerk mit 2 stabilen Zuständen (D-FF, hier ohne Takteingang)
• Änderung von x bewirkt Umschalten von 3 → 6 bzw. 6 → 3 über zwei Zwischenzustände ((7,5) und (2,1))
In der Praxis werden Verzögerungen meist (selbst) durch Flipflops realisiert, daher im Folgenden immer
τ = FF (Flipflop in unterschiedlichen Varianten möglich!)
7 Schaltwerke und Automaten Folie 6
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.2 Asynchrone Schaltwerke
Schalt-netz
Xn
Sn En
Yny1
y2yn
s1
s2s2
s4
e1
e3e4
e5
x1x2xn
Xn, Yn, En, Sn: Vektoren zum Zeitpunkt n
Definition: Ein Schaltwerk heißt asynchron, wenn die Zeitpunkte der Änderungen von Yn und Sn ausschließlich von Änderungen von X sowie internen Laufzeiten abhängen und folglich beliebig auf der Zeitachse verteilt sein können.
Vorteile:
- unmittelbare Reaktion auf Eingangsänderungen
- sehr schnelle Arbeitsweise möglich
Nachteile:
- Entwurf aufwendig + Untersuchung / Wahl der Zwischenzustände + unterschiedlich lange Zyklen
- Unerwünschte Wirkung auf nachfolgende Schaltung durch Zwischenzustände möglich
⇒ Bedeutung gering
7 Schaltwerke und Automaten Folie 7
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.3 Synchrone Schaltwerke
E
Xn
Sn
Yn
Zn
Definition: Ein Schaltwerk heißt synchron, wenn Änderungen des Zustandvektors (und u.U. Ergebnisvektors) nur zu ausgezeichneten Zeitpunkten möglich sind, die von einem Taktsignal bestimmt sind. Der Takt ist kein Eingangssignal! (Verzögerungseinheit: Zustandsregister)
⇒ Einschwingvorgänge über mehrere instabile Zwischen-zustände sind unmöglich: Alle Si nehmen ihre neuen Werte zur selben Zeit an und behalten sie mindestens für eine Taktperiode.
⇒ - Übergänge erfolgen stets von stabilen in stabile Zustände,
- Zustands- und Ergebnisvektoren reagieren um eine Taktdauer verzögert auf Änderungen am Eingang,
- Werteänderungen erfolgen stets in gleichen Zeitabständen und sind immer eindeutig,
- Änderungen im Eingangsvektor dürfen zu beliebigen Zeitpunkten und auf beliebig vielen Leitungen erfolgen (außer während set-up und hold-Zeit).
7 Schaltwerke und Automaten Folie 8
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.4 Autonome Schaltwerke
ESn
Yn
g1
g2
f
Definition: Ein Schaltwerk wird autonom genannt, wenn
sein Verhalten nicht über Eingangsvariablen von außen beeinflussbar ist. Die Eigengesetzlichkeit des Schaltnetzes bestimmt das Verhalten:
Yn = f(Sn) Ausgangsfunktion
Sn+1 = g1(En) Übergangsfunktion
En = g2(Sn) Erregungsfunktion
Anwendung: Steuerung unverändert ablaufender Prozesse
7 Schaltwerke und Automaten Folie 9
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.5 Beschreibungsformen (Impulsplan, Boole'sche Funktionen)
7.5.1 Zustandstabelle
Abgeleitet aus den Funktionsgleichungen ergibt sich:
Zustand Xn Sn En Sn+1 Yn Zn 1 2 3 . . .
Xn
Sn
Yn
Z n
En
g1
g2
f1f2
Yn = f1 (X
n,Sn) Sn+1 = g1(E
n) En = g2(X
n,Sn) Zn+1 = f2(Y
n)
Sonderfälle:
1) Yn = Zn ohne Ergebnisregister 2) Yn = Sn Zähler 3) kein Xn: autonomes Schaltwerk
7 Schaltwerke und Automaten Folie 10
Grundlagen der Technischen Informatik 1 Version: WS07/08
Beispiel:
X1
S
1
1Y
EE1
2
>1
&
&
TSQ
RQ
g1
g2
f
X2
g1 folgt aus charakteristischer Gleichung des SR-FF:
Zustandstabelle:
X1n X2
n Sn E1n E2
n Sn+1 Yn 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 0 1 0
7 Schaltwerke und Automaten Folie 11
Grundlagen der Technischen Informatik 1 Version: WS07/08
Verwendung der Zustandstabelle bei der
a) Analyse von Schaltwerken:
gegeben: Schaltplan
gesucht: Zustandstabelle oder Funktionsgleichungen
b) Synthese von Schaltwerken:
gegeben: Aufgabenstellung (Eingabe, Ausgabe)
• als verbale Formulierung
• als Funktionsgleichung
• als Wertetabelle
gesucht: Schaltplan
7 Schaltwerke und Automaten Folie 12
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.5.2 Zustandsgraph
Begriffe:
Beispiel: SR-Flipflop
0 1
10/1
01/0
0x/0 x0/1S R Q
X Y
n n n
n n
7 Schaltwerke und Automaten Folie 13
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.6 Minimierung der Schaltwerkszustände (nach Hoffmann und Mealy)
Regel:
Erforderliche Anzahl Flipflops: [ld z], z: Anzahl der Zustände
Beispiel:
3 4 5
1 0 7
1/0
1/0
1/0
1/0
1/0
1/0
0/1
0/1
0/10/10/10/10/1
1/0
1/0
2 6
0/0
7 Schaltwerke und Automaten Folie 14
Grundlagen der Technischen Informatik 1 Version: WS07/08
Also kann der Zustandsgraph vereinfacht werden zu:
4 5
2
0 7
1/0
1/0
0/1
0/1
0/1
1/0
0/1
0/0
...
...
Zn Zn+1 Yn Yn
X=0 X=1 X=0 X=10 0 1 0 0 0 1 3 7 V 1 0 2 6 0 1 1 0 3 1 4 1 1 0 4 5 0 0 1 0 5 2 0 1 1 0 6 2 0 1 1 0 7 5 0 0 1 0
7 Schaltwerke und Automaten Folie 15
Grundlagen der Technischen Informatik 1 Version: WS07/08
Zn Zn+1 Yn Yn+1 X=0 X=1 X=0 X=10 0 1 0 0 0 1 3 4/2 V 1 0 2 5 0 1 1 0 3 1 4/2 1 1 0 4 5 0 1 1 0 5 2 0 1 1 0
Minimierter Zustandsgraph:
3 5
2
1 0
1/0
0/1
0/10/1
1/0
0/1
0/0
1/01/0
1/0
2. Regel: Weitere Minimierung kann durch Gruppenbildung von Zuständen mit gleichem Folgeausgangsvektor Yn+1 und Vergleich der Gruppen erfolgen.
7 Schaltwerke und Automaten Folie 16
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.7 Automaten Zur Synthese synchroner Schaltwerke eignen sich besonders die Methoden der Automatentheorie. Dies ist lediglich eine formalere Betrachtungsweise der Schaltwerke.
Ein Automat sei definiert durch
• X: Eingabemenge
• Y: Ausgabemenge
• Z: Zustandsmenge
• zwei Abbildungen (g,f) mit f =̂ Ausgabefunktion g =̂ Übergangsfunktion
7 Schaltwerke und Automaten Folie 17
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.7.1 Mealy-Automat
Ein Mealy-Automat ist definiert durch seine
Ausgabefunktion Yn = f(Xn,Zn) sowie
Übergangsfunktion Zn+1 = g(Xn,Zn)
g
Y
Spei-cher
f
Spei-cher
f,gX n
Zn Zn+1
Y nZn+1
ZZn
n
XX
n
n
TT
7.7.2 Moore-Automat
Ein Moore-Automat ist definiert durch seine
Ausgabefunktion Yn = h(Zn)
Übergangsfunktion Zn+1 = g(Xn,Zn)
gSpei-cher h Y
Zn+1Zn
Xn
T
andere Schreibweise:
Yn = h(Zn+1) ergibt durch Einsetzen von Zn+1: Yn = h(g(Xn,Zn))
7 Schaltwerke und Automaten Folie 18
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.7.3 Gegenüberstellung Mealy- und Moore-Automat
In einem stabilen Zustand können in einem
• Mealy-Automaten verschiedene Ausgangsvektoren
• Moore-Automaten nur ein Ausgangsvektor auftreten.
Mealy- und Moore-Automat können ineinander überführt werden.
Yn = Zn: keine Ausgabefunktion vorhanden ⇒ Medwedjew-Automat
Übliche Darstellungsform: Automatentafel (kompaktere Darstel-lung der Tabellen aus Kap. 9.6):
Eingangswerte
BelegungX n
Z n
Belegung Z n+1/ Yn
(=g/f)
Vorzustände
7 Schaltwerke und Automaten Folie 19
Grundlagen der Technischen Informatik 1 Version: WS07/08
7.8 Synthese von Schaltwerken Die Synthese allgemeiner Schaltwerke erfolgt schrittweise:
1. Problemanalyse
2. Zustandsdefinition und Zustandsgraph
3. Aufstellen der Zustandstabelle
4. Minimierung der Zustände (auf < [ld z])
5. Kodierung der Zustände (willkürlich, aber geschickt; binär)
6. Wahl des Flipflop-Typs und Aufstellen der Gleichungen (Aufwandsabschätzung durch mehrere Versuche und Vergleich)
7 Schaltwerke und Automaten Folie 20
Grundlagen der Technischen Informatik 1 Version: WS07/08
Beispiel „Aufstehen“ Szenario:
• Studierende(r) stellt den Wecker auf 6 Uhr morgens • An Werktagen wird aufgestanden und der Wecker
abgeschaltet • An Wochenenden bleibt man liegen und stellt den Wecker
auf 10 Uhr • Erst dann wird auf gestanden
Skizze des Automaten:
Automat Wecker klingelt (WE)
Wochenende (WO)
Wach (WA)
Schlummerfunktion bis 10 Uhr (SF)
7 Schaltwerke und Automaten Folie 21
Grundlagen der Technischen Informatik 1 Version: WS07/08
Ausgabe mit Zuständen assoziiert:
schlaf. bis 6 wach 6 auf
Wecker st. schlaf. bis 10 wach 10
Wecker
Wecker
Wecker
Wochenende
Wochenende
wach = 0Schlumerfkt. = 0
wach = 1Schlumerfkt. = 0
wach = 1Schlumerfkt. = 0
wach = 1Schlumerfkt. = 1
wach = 0Schlumerfkt. = 0
wach = 1Schlumerfkt. = 0
Wecker
• Zustände zeigen Aktionen • Nicht beachtete Eingabewerte werden nicht eingetragen • unbedingte Übergänge sind nicht beschriftet
7 Schaltwerke und Automaten Folie 22
Grundlagen der Technischen Informatik 1 Version: WS07/08
Ausgabe mit Kanten assoziiert:
wach = 0Schlumerfkt. = 0
Wecker
wach = 1Schlumerfkt. = 0
schlaf. bis 6
Wecker gest.
Wochenende
wach = 1
Schlumerfkt. =
1
wach = 0Schlumerfkt. = 0
wach = 1Schlumerfkt. = 0
wach 6 auf
schlaf. bis 10 wach 10
Wecker
Wecker
Wecker
Wochenende
wach = 1Schlumerfkt. = 0
wach = 1Schlumerfkt. = 0
wach = 1Schlumerfkt. = 0
• Zustände repräsentieren Ereignisse zwischen Aktionen • Zustände müssen möglicherweise umbenannt werden
7 Schaltwerke und Automaten Folie 23
Grundlagen der Technischen Informatik 1 Version: WS07/08
d daufd dwach10d 1schlaf10d 0schlaf10d dSchlumerfkt.0 dwach61 dwach6d 1schlaf6d 0schlaf6
WO WE
FolgezuständeEingängeZustände
Zustandstabelle
d d1 1 1
d d1 1 0
aufd dauf 1 0 1
aufd dwach10 1 0 0
wach10d 1schlaf10 0 1 1
schlaf10d 0schlaf10 0 1 1
schlaf10d dSchlumerfkt. 0 1 0
auf0 dwach6 0 0 1
Schlumerfkt.1 dwach6 0 0 1
wach6d 1schlaf6 0 0 0
schlaf6d 0schlaf6 0 0 0
FolgezuständeQ2´ Q1´ Q0´
EingängeWO WE
ZuständeQ2 Q1 Q0
Binäre Zustandscodierung, binäre Zustandstabelle
7 Schaltwerke und Automaten Folie 24
Grundlagen der Technischen Informatik 1 Version: WS07/08
d d d d d dd d dd d1 1 1
d d d d d dd d dd d1 1 0
d 0 0 d d 01 0 1d d1 0 1
d 0 0 d 1 d1 0 1d d1 0 0
1 d d 1 d 11 0 0d 10 1 1
0 d d 0 d 00 1 1d 00 1 1
0 d d 0 1 d0 1 1d d0 1 0
1 d 0 d d 01 0 10 d0 0 1
0 d 1 d d 10 1 01 d0 0 1
0 d 0 d 1 d0 0 1d 10 0 0
0 d 0 d 0 d0 0 0d 00 0 0
Flip-Flop-AnsteuerungJ2 K2 J1 K1 J0 K0
FolgezuständeQ2´ Q1´ Q0´
EingängeWO WE
ZuständeQ2 Q1 Q0
JK- Flip- Flops und deren Ansteuerung
d d1 1 1
d d1 1 0
1 0auf 1 0 1
1 0wach10 1 0 0
0 0schlaf10 0 1 1
1 1Schlumerfkt. 0 1 0
1 0wach6 0 0 1
0 1schlaf6 0 0 0
AusgabeWA = wach SF = Schlumerfkt.
ZuständeQ2 Q1 Q0
Ausgabefunktionen in Abhängigkeit vom Zustand
7 Schaltwerke und Automaten Folie 25
Grundlagen der Technischen Informatik 1 Version: WS07/08
01
01012
120
021
01012
QQSFQQQQQWA
WEQQJWOQQJ
WEQQWOQQJ
⋅=
⋅+⋅+=
++=
⋅⋅=
⋅⋅+⋅⋅=
WEQWOQQKWEQQK
0K
1220
011
2
⋅+⋅⋅=
⋅⋅=
=
Gleichungen
Schaltbild des Automaten:
(aus: Franz J. Hauck, Vorlesung Technische Informatik 1, SS02, Verteilte Systeme, Universität Ulm)
SF
7 Schaltwerke und Automaten Folie 26
Grundlagen der Technischen Informatik 1 Version: WS07/08
Sonderfälle:
a) Zählerentwurf
Bis hierher Schaltwerke mit fest verdrahteter Funktion, weitere Möglichkeit:
b) Rückgekoppeltes Schieberegister
Schaltnetz
F
D Parallelesladen :Programmieren
i
i
<
festgelegte Sequenz, abhängig vom geladenen Wort Fi=f(Di)
aber: nur für einfache Steuerungen, da begrenzte Programmierbarkeit, da Schaltnetz starr ist.
c) ROM oder PLA als programmierbare Schaltnetze mit
Rückkopplung über Register
Größtmögliche Freiheit im Entwurf! (siehe nächstes Kapitel!)