HS Mittweida Fachbereich Inform
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Digitale Systeme / AutomatenDigitale Systeme / Automaten
1. Definition und Klassifikation digitaler Systeme
-Einordnung digitaler Systeme-Einordnung digitaler Signale-Automatenmodell-Vereinbarungen ( Variable, Buchstabe, Wort)
1. Definition und Klassifikation digitaler Systeme
-Einordnung digitaler Systeme-Einordnung digitaler Signale-Automatenmodell-Vereinbarungen ( Variable, Buchstabe, Wort)
6. Basissysteme- NAND- NOR- ANF
6. Basissysteme- NAND- NOR- ANF
11. Automatentheorie- Definitionen- Beschreibungsformen- Typen- und ihre Eigenschaften
11. Automatentheorie- Definitionen- Beschreibungsformen- Typen- und ihre Eigenschaften
2. Einführung in die KombinatorikEigenschaften von Schaltfunktionen- Buchstabenabbildungen- Elementare Operationen - Boolesche Algebra- Codes und Zahlensysteme- Positionssysteme
2. Einführung in die KombinatorikEigenschaften von Schaltfunktionen- Buchstabenabbildungen- Elementare Operationen - Boolesche Algebra- Codes und Zahlensysteme- Positionssysteme
3. Analytische Beschreibung . ........kombinatorischer Netzwerke- Axiome der Booleschen Algebra - Funktionseigenschaften- Normalformen
3. Analytische Beschreibung . ........kombinatorischer Netzwerke- Axiome der Booleschen Algebra - Funktionseigenschaften- Normalformen
4. Minimierung von Schaltfunktionen - Identische Abbildungen- Kürzungsregeln- Karnaughplan- Quine & Mc Kluskey
4. Minimierung von Schaltfunktionen - Identische Abbildungen- Kürzungsregeln- Karnaughplan- Quine & Mc Kluskey
5. Einführung in das Praktikum- Grundlagen der VHDL- Syntax- XPLA – Designer- Logiksimulation
5. Einführung in das Praktikum- Grundlagen der VHDL- Syntax- XPLA – Designer- Logiksimulation
ationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 1
7. Synthese von Funktionsbündeln-Logikplan- Relaisplan- Funktionsbündel durch ROM- Strukturen programmierbarer Schaltkreise
7. Synthese von Funktionsbündeln-Logikplan- Relaisplan- Funktionsbündel durch ROM- Strukturen programmierbarer Schaltkreise
12. Automatentypenumwandlumg- Moore Mealy- Mealy Moore
12. Automatentypenumwandlumg- Moore Mealy- Mealy Moore
13. Zustandsreduktion- Zeilenverschmelzung- Minimierung der Übergänge- Hohn & Aufenkamp- Paull Unger
13. Zustandsreduktion- Zeilenverschmelzung- Minimierung der Übergänge- Hohn & Aufenkamp- Paull Unger
8. Logikanalyse- Auswertung von Stromlauf- und Logikplänen- Dynamische Analyse- statische und dynamische Hasards
8. Logikanalyse- Auswertung von Stromlauf- und Logikplänen- Dynamische Analyse- statische und dynamische Hasards
14. Ablaufsteuerungen- Automatenbeschreibung- Speicherfestlegung- Schaltbelegungstabelle- Kürzung der Schaltfunktionen- Simulation- Test
14. Ablaufsteuerungen- Automatenbeschreibung- Speicherfestlegung- Schaltbelegungstabelle- Kürzung der Schaltfunktionen- Simulation- Test
9. Freie Rückführkreise- Stabilität- Grund-Flip-Flop- Beschreibung von FF’s- charakteristische Gleichungen- Zustandsgrafen- Tabelle
9. Freie Rückführkreise- Stabilität- Grund-Flip-Flop- Beschreibung von FF’s- charakteristische Gleichungen- Zustandsgrafen- Tabelle
15. Digitale Schaltungstechnik- Motivation und Einführung- Grundlagen - Schaltkreisfamilien- DA / AD - Wandler
15. Digitale Schaltungstechnik- Motivation und Einführung- Grundlagen - Schaltkreisfamilien- DA / AD - Wandler
10. Standardschaltungen- getriggerte Zähler- Umlaufregister- AD- DA- Wandler
10. Standardschaltungen- getriggerte Zähler- Umlaufregister- AD- DA- Wandler
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 2
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Zur ErinnerungZur Erinnerung
Menge der möglichen AusgangszuständeMenge der möglichen
Eingangszustände
Menge der möglichen inneren Zustände
X YZ
(X x Z)
(X x Z) δ Überführungsfunktion
Ausgangsfunktion
aktueller Zustand
Folgezustand
λ
YδÜberführungs-
zuordnerSpeicher
λAusgangs-zuordner
X Z
LöschenTakt
Z*
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 3
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
ProblemstellungProblemstellung
Za
Zb X1/Y0X0/Y1
X1/Y0 X0/Y0X1/Y0
X0/Y1
Z0
Z2
Z3
Z1
X0/Y0X1/Y0
X1/Y0
X1/Y0
X0/Y1X0/Y1
?
},,,{ 3210 ZZZZZ =},{ 10 YYY =
},{ 10 XXX =),,,,( ZYXAA= λδ
},{ ba ZZZ =
),,,,( ZYXAA= λδ},{ 10 XXX =
},{ 10 YYY =?ψ
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 4
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Äquivalenz von AutomatenÄquivalenz von Automaten
δ/λ X0 X1
Z0 Z3/Y0 Z1/Y0Z1 Z2/Y1 Z2/Y0Z2 Z3/Y1 Z2/Y0Z3 Z1/Y1 Z2/Y0
δ∗/ λ∗ X0 X1
Za Zb/Y0 Zb/Y0Zb Zb/Y1 Zb/Y0
Z3
Z2Z1
Z0Z
Zb
Za
*Zψ
Zwei Automaten sind einander äquivalent, wenn sie, gestartet in äquivalenten Zuständen, gleiches „Klemmenverhalten“ zeigen.
Zwei Automaten sind einander äquivalent, wenn sie, gestartet in äquivalenten Zuständen, gleiches „Klemmenverhalten“ zeigen.
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 5
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Vergleich der AutomatenVergleich der Automaten
X1/Y0
X0/Y1
Z0
Z2
Z3
Z1
X0/Y0X1/Y0
X1/Y0
X1/Y0
X0/Y1X0/Y1
X1X1 X0X1X0X0X0X0X0X0 X0X0X0
Z0 Z1 Z2Z3 Z3 Z2 Z3 Z1 Z2 Z2 Z3 Z1 Z2 Z3
Y0 Y1 Y0 Y1 Y0 Y1 Y1 Y1 Y0 Y1 Y1 Y1 Y1
Beide Automaten zeigen am Beispiel
gleiches Ausgangsverhalten.X1X1 X0X1X0X0X0X0X0X0 X0X0X0=X~
Za
Zb X1/Y0X0/Y1
X1/Y0 X0/Y0
X1X1 X0X1X0X0X0X0X0X0 X0X0X0
Za Zb ZbZb Zb Zb Zb Zb Zb Zb Zb Zb Zb Zb
Y0 Y1 Y0 Y1 Y0 Y1 Y1 Y1 Y0 Y1 Y1 Y1 Y1
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 6
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
AufgabenstellungAufgabenstellung
AutomatAutomatx
Takt Löschen
y0y1
x
X0 0
X1 10 0 0 1 8
1 0 0 1 9
0 1 0 1 10
(LsB) (MsB)
y1 y0
Y0 0 0
Y1 0 1
Y2 1 0
Y3 - -
Der Automat überprüfe einen 4- Bitstrom auf x.Das Bit höchster Wertigkeit (MsB) trifft zuletzt ein.Der Automat antworte während der ersten 3 Takte jeweils mit Y0Y0Y0 .Mit dem letzten Takt gebe der Automat Y1 aus, wenn das Eingangswort >9; Y2 wenn das Eingangswort <10 war.
Der Anfangszustand sei Z0. (Wird durch Löschen eingestellt.)
Der Automat überprüfe einen 4- Bitstrom auf x.Das Bit höchster Wertigkeit (MsB) trifft zuletzt ein.Der Automat antworte während der ersten 3 Takte jeweils mit Y0Y0Y0 .Mit dem letzten Takt gebe der Automat Y1 aus, wenn das Eingangswort >9; Y2 wenn das Eingangswort <10 war.
Der Anfangszustand sei Z0. (Wird durch Löschen eingestellt.)
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 7
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Z0
Z1 Z2
Z3 Z4 Z5 Z6
Z7 Z8 Z9 Z10 Z11 Z12 Z13 Z14
/
/ / / /
/ / / / / / / /
/ / / / / / / / / / / / / / / /
X0 X1
/
AufgabenstellungAufgabenstellung
0 8 4 12 2 10 6 7 1 9 5 13 3 11 7 15LsB zuerst
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 8
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Z0
Z1 Z2
Z3 Z4 Z5 Z6
Z7 Z8 Z9 Z10 Z11 Z12 Z13 Z14
/Y0
/Y0 /Y0 /Y0 /Y0
/Y0/Y0/Y0/Y0/Y0/Y0/Y0/Y0
/Y2/Y1/Y2/Y1/Y2/Y1 /Y1/Y1 /Y2/Y1/Y2/Y1/Y1/Y1 /Y2/Y1
X0 X1
/Y0
AufgabenstellungAufgabenstellung
0 8 4 12 2 10 6 7 1 9 5 13 3 11 7 15LsB zuerst
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 9
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Erzeugen der AutomatentabelleErzeugen der Automatentabelle
δ/λ X0 X1
Z0 Z1/Y0 Z2/Y0Z1 Z3/Y0 Z4/Y0Z2 Z5/Y0 Z6/Y0Z3 Z7/Y0 Z8/Y0Z4 Z9/Y0 Z10/Y0Z5 Z11/Y0 Z12/Y0Z6 Z13/Y0 Z14/Y0Z7 Z0/Y1 Z0/Y1Z8 Z0/Y1 Z0/Y2Z9 Z0/Y1 Z0/Y2Z10 Z0/Y1 Z0/Y2Z11 Z0/Y1 Z0/Y1Z12 Z0/Y1 Z0/Y2Z13 Z0/Y1 Z0/Y2Z14 Z0/Y1 Z0/Y2
Z0
Z1 Z2
Z3 Z4 Z5 Z6
Z7 Z8 Z9 Z10 Z11 Z12 Z13 Z14
/Y0
/Y0 /Y0 /Y0 /Y0
/Y0/Y0/Y0/Y0/Y0/Y0/Y0/Y0
/Y2/Y1/Y2/Y1/Y2/Y1 /Y1/Y1 /Y2/Y1/Y2/Y1/Y1/Y1 /Y2/Y1
X0 X1
/Y0
1
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 10
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
ÄquivalenzklassenÄquivalenzklassen
δ/λ X0 X1
Z0 Z1/Y0 Z2/Y0Z1 Z3/Y0 Z4/Y0Z2 Z5/Y0 Z6/Y0Z3 Z7/Y0 Z8/Y0Z4 Z9/Y0 Z10/Y0Z5 Z11/Y0 Z12/Y0Z6 Z13/Y0 Z14/Y0Z7 Z0/Y1 Z0/Y1Z8 Z0/Y1 Z0/Y2Z9 Z0/Y1 Z0/Y2Z10 Z0/Y1 Z0/Y2Z11 Z0/Y1 Z0/Y1Z12 Z0/Y1 Z0/Y2Z13 Z0/Y1 Z0/Y2Z14 Z0/Y1 Z0/Y2
2 Bilden von Äquivalenzklassen
)10(),(),( −≤≤= niZXZX biai λλIn einer Äquivalenzklasse gilt:
hrittKürzungsscterkiklasseÄquivalenzZ k
i
−⇒ ,
21 YYwegen11 YYwegen00 YYwegen
14131210981
2
1171
1
65432101
0
},,,,,{},{
},,,,,,{
ZZZZZZZZZZ
ZZZZZZZZ
===
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 11
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Einsortieren der Äquivalenzklassen in die ÜberführungstabelleEinsortieren der Äquivalenzklassen in die Überführungstabelle
δ X0 X1
Z0 Z1 - Z2 -Z1 Z3 - Z4 -Z2 Z5 - Z6 -Z3 Z7 - Z8 -Z4 Z9 - Z10 -Z5 Z11 - Z12 -
Z01
Z6 Z13 - Z14 -Z7 Z0 - Z0 -Z1
1
Z11 Z0 - Z0 -Z8 Z0 - Z0 -Z9 Z0 - Z0 -Z10 Z0 - Z0 -Z12 Z0 - Z0 -Z13 Z0 - Z0 -
Z21
Z14 Z0 - Z0 -
δ/λ X0 X1
Z0 Z1/Y0 Z2/Y0Z1 Z3/Y0 Z4/Y0Z2 Z5/Y0 Z6/Y0Z3 Z7/Y0 Z8/Y0Z4 Z9/Y0 Z10/Y0Z5 Z11/Y0 Z12/Y0Z6 Z13/Y0 Z14/Y0Z7 Z0/Y1 Z0/Y1Z8 Z0/Y1 Z0/Y2Z9 Z0/Y1 Z0/ Y2Z10 Z0/Y1 Z0/Y2Z11 Z0/Y1 Z0/Y1Z12 Z0/Y1 Z0/Y2Z13 Z0/Y1 Z0/Y2Z14 Z0/Y1 Z0/Y2
2
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 12
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
LageprüfungLageprüfung
δ X0 X1
Z0 Z1 - Z2 -Z1 Z3 - Z4 -
Z02
Z2 Z5 - Z6 -Z3 Z7 - Z8 -Z1
2
Z5 Z11 - Z12 -Z4 Z9 - Z10 -Z2
2
Z6 Z13 - Z14 -Z7 Z0 - Z0 -Z3
2
Z11 Z0 - Z0 -Z8 Z0 - Z0 -Z9 Z0 - Z0 -Z10 Z0 - Z0 -Z12 Z0 - Z0 -Z13 Z0 - Z0 -
Z42
Z14 Z0 - Z0 -
δ X0 X1
Z0 Z1 - 0 Z2 - 0Z1 Z3 - 0 Z4 - 0Z2 Z5 - 0 Z6 - 0Z3 Z7 - 1 Z8 - 2Z4 Z9 - 2 Z10 - 2Z5 Z11 - 1 Z12 - 2
Z01
Z6 Z13 - 2 Z14 - 2Z7 Z0 - 0 Z0 - 0Z1
1
Z11 Z0 - 0 Z0 - 0Z8 Z0 - 0 Z0 - 0Z9 Z0 - 0 Z0 - 0Z10 Z0 - 0 Z0 - 0Z12 Z0 - 0 Z0 - 0Z13 Z0 - 0 Z0 - 0
Z21
Z14 Z0 - 0 Z0 - 0
3
Prüfung der Lage der Zielzustände.Bilden sich neue Äquivalenzklassen?
Ja Nein
Prüfung der Lage der Zielzustände.Bilden sich neue Äquivalenzklassen?
Ja Nein3 4
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 13
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Lageprüfung ..Lageprüfung ..
δ X0 X1
Z0 Z1 - 0 Z2 - 0Z1 Z3 - 1 Z4 - 2
Z02
Z2 Z5 - 1 Z6 - 2Z3 Z7 - 3 Z8 - 4Z1
2
Z5 Z11 - 3 Z12 - 4Z4 Z9 - 4 Z10 - 4Z2
2
Z6 Z13 - 4 Z14 - 4Z7 Z0 - 0 Z0 - 0Z3
2
Z11 Z0 - 0 Z0 - 0Z8 Z0 - 0 Z0 - 0Z9 Z0 - 0 Z0 - 0Z10 Z0 - 0 Z0 - 0Z12 Z0 - 0 Z0 - 0Z13 Z0 - 0 Z0 - 0
Z42
Z14 Z0 - 0 Z0 - 0
3δ X0 X1
Z03 Z0 Z1 - Z2 -
Z1 Z3 - Z4 -Z13
Z2 Z5 - Z6 -Z3 Z7 - Z8 -Z2
3
Z5 Z11 - Z12 -Z4 Z9 - Z10 -Z3
3
Z6 Z13 - Z14 -Z7 Z0 - Z0 -Z4
3
Z11 Z0 - Z0 -Z8 Z0 - Z0 -Z9 Z0 - Z0 -Z10 Z0 - Z0 -Z12 Z0 - Z0 -Z13 Z0 - Z0 -
Z53
Z14 Z0 - Z0 -
Prüfung der Lage der Zielzustände.Bilden sich neue Äquivalenzklassen?
Ja Nein
Prüfung der Lage der Zielzustände.Bilden sich neue Äquivalenzklassen?
Ja Nein3 4
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 14
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Auswahl der StellvertreterAuswahl der Stellvertreter
δ*Z0
3 ZaZbZ1
3
ZcZ23
ZdZ33
ZeZ43
ZfZ53
Zuordnung von
δ X0 X1
Z03 Z0 Z1 - 1 Z2 - 1
Z1 Z3 - 2 Z4 - 3Z13
Z2 Z5 - 2 Z6 - 3Z3 Z7 - 4 Z8 - 5Z2
3
Z5 Z11 - 4 Z12 - 5Z4 Z9 - 5 Z10 - 5Z3
3
Z6 Z13 - 5 Z14 - 5Z7 Z0 - 0 Z0 - 0Z4
3
Z11 Z0 - 0 Z0 - 0Z8 Z0 - 0 Z0 - 0Z9 Z0 - 0 Z0 - 0Z10 Z0 - 0 Z0 - 0Z12 Z0 - 0 Z0 - 0Z13 Z0 - 0 Z0 - 0
Z53
Z14 Z0 - 0 Z0 - 0
3 4
Stellvertreterzuständen.Zuordnung von Prüfung der Lage der Zielzustände.
Bilden sich neue Äquivalenzklassen?
Ja Nein
Prüfung der Lage der Zielzustände.Bilden sich neue Äquivalenzklassen?
Ja Nein3 4Stellvertreterzuständen.
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 15
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
5δ X0 X1
Z03 Za Z1 - 1 Z2 - 1
Zb Z3 - 2 Z4 - 3Z13
Z2 Z5 - 2 Z6 - 3Zc Z7 - 4 Z8 - 5Z2
3
Z5 Z11 - 4 Z12 - 5Zd Z9 - 5 Z10 - 5Z3
3
Z6 Z13 - 5 Z14 - 5Ze Z0 - 0 Z0 - 0Z4
3
Z11 Z0 - 0 Z0 - 0Zf Z0 - 0 Z0 - 0Z9 Z0 - 0 Z0 - 0Z10 Z0 - 0 Z0 - 0Z12 Z0 - 0 Z0 - 0Z13 Z0 - 0 Z0 - 0
Z53
Z14 Z0 - 0 Z0 - 0
δ* X0 X1
Za Zb ZbZb Zc ZdZc Ze ZfZd Zf ZfZe Za ZaZf Za Za
Konstruktion der δ TabelleKonstruktion der δ Tabelle
Konstruktion derδ* Tabelle
Konstruktion derδ* Tabelle
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 16
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Konstruktion der λ TabelleKonstruktion der λ Tabelle
Konstruktion derλ* Tabelle
Konstruktion derλ* Tabelle
λ* X0 X1
Za Y0 Y0Zb Y0 Y0Zc Y0 Y0Zd Y0 Y0Ze Y1 Y1Zf Y1 Y2
δ* δZa Z0Zb Z1
Z2Zc Z3
Z5Zd Z4
Z6Ze Z7
Z11Zf Z8
Z9Z10Z12Z13Z14
δ/λ X0 X1
Z0 Z1/Y0 Z2/Y0Z1 Z3/Y0 Z4/Y0Z2 Z5/Y0 Z6/Y0Z3 Z7/Y0 Z8/Y0Z4 Z9/Y0 Z10/Y0Z5 Z11/Y0 Z12/Y0Z6 Z13/Y0 Z14/Y0Z7 Z0/Y1 Z0/Y1Z8 Z0/Y1 Z0/Y2Z9 Z0/Y1 Z0/ Y2Z10 Z0/Y1 Z0/Y2Z11 Z0/Y1 Z0/Y1Z12 Z0/Y1 Z0/Y2Z13 Z0/Y1 Z0/Y2Z14 Z0/Y1 Z0/Y2
6
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 17
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
LösungLösungX0 X1
Za
Zb Z2
Zc Zd Z5 Z6
Ze Zf Z9 Z10 Z11 Z12 Z13 Z14
/Y0
/Y0 /Y0 /Y0 /Y0
/Y0/Y0/Y0/Y0/Y0/Y0/Y0/Y0
/Y2/Y1/Y2/Y1/Y2/Y1 /Y1/Y1 /Y2/Y1/Y2/Y1/Y1/Y1 /Y2/Y1
/Y0
- /Y0
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 18
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
δ* X0 X1
Z0 Z1 Z1 Z1 Z2 Z3 Z2 Z4 Z5 Z3 Z5 Z5 Z4 Z0 Z0 Z5 Z0 Z0
δ* X0 X1
Za Zb ZbZb Zc ZdZc Ze ZfZd Zf ZfZe Za ZaZf Za Za
λ* X0 X1
Z0 Y0 Y0 Z1 Y0 Y0 Z2 Y0 Y0 Z3 Y0 Y0 Z4 Y1 Y1 Z5 Y1 Y2
λ* X0 X1
Za Y0 Y0Zb Y0 Y0Zc Y0 Y0Zd Y0 Y0Ze Y1 Y1Zf Y1 Y2
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 19
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
δ* X0 X1 Z0 Z1 Z1 Z1 Z2 Z3 Z2 Z4 Z5 Z3 Z5 Z5 Z4 Z0 Z0 Z5 Z0 Z0
λ* X0 X1
Z0 Y0 Y0 Z1 Y0 Y0 Z2 Y0 Y0 Z3 Y0 Y0 Z4 Y1 Y1 Z5 Y1 Y2
u x q2 q1 q0 D2 D1 D0 y1 y0
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
0 1 0 1 0
11 1 0 1 1
12 1 1 0 0
13 1 1 0 1
14 1 1 1 0
15 1 1 1 1
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 20
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
δ* X0 X1
Z0 Z1 Z1 Z1 Z2 Z3 Z2 Z4 Z5 Z3 Z5 Z5 Z4 Z0 Z0 Z5 Z0 Z0
u x q2 q1 q0 D2 D1 D0 y1 y0
0 0 0 0 0 0 0 1 0 0
1 0 0 0 1 0 1 0 0 0
2 0 0 1 0 1 0 0 0 0
3 0 0 1 1 1 0 1 0 0
4 0 1 0 0 0 0 0 0 1
5 0 1 0 1 0 0 0 0 1
6 0 1 1 0 - - - - -
7 0 1 1 1 - - - - -
8 1 0 0 0 0 0 1 0 0
9 1 0 0 1 0 1 1 0 0
0 1 0 1 0 1 0 1 0 0
11 1 0 1 1 1 0 1 0 0
12 1 1 0 0 0 0 0 0 1
13 1 1 0 1 0 0 0 1 0
14 1 1 1 0 - - - - -
15 1 1 1 1 - - - - -
λ* X0 X1
Z0 Y0 Y0 Z1 Y0 Y0 Z2 Y0 Y0 Z3 Y0 Y0 Z4 Y1 Y1 Z5 Y1 Y2
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 21
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
u x q2 q1 q0 D2 D1 D0 y1 y0
0 0 0 0 0 0 0 1 0 0
1 0 0 0 1 0 1 0 0 0
2 0 0 1 0 1 0 0 0 0
3 0 0 1 1 1 0 1 0 0
4 0 1 0 0 0 0 0 0 1
5 0 1 0 1 0 0 0 0 1
6 0 1 1 0 - - - - -
7 0 1 1 1 - - - - -
8 1 0 0 0 0 0 1 0 0
9 1 0 0 1 0 1 1 0 0
0 1 0 1 0 1 0 1 0 0
11 1 0 1 1 1 0 1 0 0
12 1 1 0 0 0 0 0 0 1
13 1 1 0 1 0 0 0 1 0
14 1 1 1 0 - - - - -
15 1 1 1 1 - - - - -
2 1
1 2 1 0
0 1 0 2 1 0 2
1 2 0
0 2 2 0
D qD q q qD q q q q q xq
y xq qy xq q q
=== ∨ ∨
== ∨
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 22
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
=>1
=>1
&
&
&
&
&
&
&
Q
D
r
Qt
Q
D
r
Qt
Q
D
r
Qt
x
q0
y0q1
q2 y1Takt
res
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 23
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
AufgabenstellungAufgabenstellung
? ?
Z0
Z3
Z1Z5
Z4Z2
X1/Y1 X0/Y1
X0/ -
X0/ -X0/Y0X1/Y1
X0/ -X1/ -
X1/Y1
δ/λ X0 X1
Z0 - / Y1 - / Y1
Z1 Z3 / - Z4 / -Z2 Z5 / Y0 - / -Z3 Z0 / - - / Y1
Z4 - / - Z2 / Y0
Z5 Z3 / Y0 - / Y1
?
X1/ -X0/Y0
X1/Y0
??
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 24
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
VerträglichkeitsbedingungenVerträglichkeitsbedingungen
Z0 - / Y1 - / Y1
Z1 Z3 / - Z4 / -Verträgliches Zustandspaar :
(Za,Zb) v wenn für alle Xi gilt: δ/λ(Za,Xi) = δ/λ ( Zb,Xi)
(Z0,Z1)
Z4 - / - Z2 / Y0
Z5 Z3 / Y0 - / Y1
Unverträgliches Zustandspaar :
(Za,Zb) X wenn für ein Xi gilt: λ(Za,Xi) == λ ( Zb,Xi) (Z4,Z5) X
(Z2,Z3) {(Z0,Z5)}Z2 Z5 / Y0 - / -Z3 Z0 / - - / Y1 Bedingt verträgliches Zustandspaar :
(Za,Zb) wenn für alle Xi gilt: λ(Za,Xi) = λ ( Zb,Xi)und alle Paare { δ((Za,Xi),(Zb,Xi) } untereinander verträglich sind
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 25
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Durchmusterung aller ZustandspaareDurchmusterung aller Zustandspaare
Z0 Z1 Zi Zn-2
Zn-1
Zn-2
Zi
Z1
Z1Z2 X (Z3,Z5)
Z3 (Z0,Z3) (Z0,Z5)
Z4 X (Z2,Z4) x
Z5 X (Z3,Z5) (Z0,Z3) x
Z0 Z1 Z2 Z3 Z4
Über die Schenkel (Z1 .. Zn-1), (Z0 .. Zn-2)im rechtwinkligen Drei-
eck findet man alle ge-ordneten Paare.
δ/λ X0 X1
Z0 - / Y1 - / Y1
Z1 Z3 / - Z4 / -Z2 Z5 / Y0 - / -Z3 Z0 / - - / Y1
Z4 - / - Z2 / Y0
Z5 Z3 / Y0 - / Y1
Ist eine Bedingung unverträglich,so ist auch das Paar unverträglich.
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 26
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Liste der verträglichen ZustandspaareListe der verträglichen Zustandspaare
Z1
Z2 X (Z3,Z5)
Z3 (Z0,Z3) (Z0,Z5)
Z4 X (Z2,Z4) x
Z5 X (Z3,Z5) (Z0,Z3) x
Z0 Z1 Z2 Z3 Z4
(Z0,Z1)(Z0,Z3)
(Z1,Z2)(Z1,Z3)(Z1,Z4)(Z1,Z5)
(Z2,Z4)(Z2,Z5)
(Z3,Z5)
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 27
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Bilden von VerträglichkeitsmengenBilden von Verträglichkeitsmengen
In einer Vertäglichkeitsmenge sind alle Zustände untereinander verträglich !
(Z0,Z1)(Z0,Z3)
(Z1,Z2)(Z1,Z3)(Z1,Z4)(Z1,Z5)
(Z2,Z4)(Z2,Z5)
(Z3,Z5)
M1Z0
Z3Z1
VV
V
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 28
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Probleme bei der VerträglichkeitsmengenbildungProbleme bei der Verträglichkeitsmengenbildung
(Z0,Z1)(Z0,Z3)
(Z1,Z2)(Z1,Z3)(Z1,Z4)(Z1,Z5)
(Z2,Z4)(Z2,Z5)
(Z3,Z5)
M2
Z2 Z3
Z1
Z4Z5
V
X
Z2 Z4
Z1
Z3Z5
Z2 Z4
Z1
Z1
Z3Z5
Z2
Z1
Z5
M3
M4
Verträgliches Zustandspaar
Unverträgliches Zustandspaar
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 29
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Probleme bei der VerträglichkeitsmengenbildungProbleme bei der Verträglichkeitsmengenbildung
(Z0,Z1)(Z0,Z3)
(Z1,Z2)(Z1,Z3)(Z1,Z4)(Z1,Z5)
(Z2,Z4)(Z2,Z5)
(Z3,Z5)
Z2
Z5Z4
VV
V
V
X
Verträgliches Zustandspaar
Unverträgliches Zustandspaar
M6Z2
Z5
V
Z2
Z4
V
M5
Z3 Z5
M7V
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 30
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Systematische VerträglichkeitsmengenbildungSystematische Verträglichkeitsmengenbildung
Z1 Z2 Z3 Z4 Z5
1 0 0 0 0
1 0 0 0 11 0 0 1 01 0 1 0 01 1 0 0 0
1 0 0 1 11 0 1 0 11 0 1 1 01 1 0 0 11 1 0 1 01 1 1 0 0
1 0 1 1 11 1 0 1 11 1 1 0 11 1 1 1 0
1 1 1 1 1
(Z0,Z1)(Z0,Z3)
(Z1,Z2)(Z1,Z3)(Z1,Z4)(Z1,Z5)
(Z2,Z4)(Z2,Z5)
(Z3,Z5)
Z1 Z2 Z3 Z4 Z5
1 0 0 0 0
1 0 0 0 11 0 0 1 01 0 1 0 01 1 0 0 0
1 0 0 1 11 0 1 0 11 0 1 1 01 1 0 0 11 1 0 1 01 1 1 0 0
1 0 1 1 11 1 0 1 11 1 1 0 11 1 1 1 0
1 1 1 1 1
Z1
Z3Z5
Z2
Z1
Z5
Z2 Z4
Z1
M2
M3
M4
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 31
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Auswahl der VerträglichkeitsmengenAuswahl der Verträglichkeitsmengen
Z0 Z1 Z2 Z3 Z4 Z5M1 x x xM2 x x xM3 x x xM4 x x xM5 x xM6 x xM7 x x
M1={Z0,Z1,Z3}M2={Z1,Z2,Z4}M3={Z1,Z2,Z5}M4={Z1,Z3,Z5}M5={Z2,Z4}M6={Z2,Z5}M7={Z3,Z5}
)7643()52()741()6532()4321(1 MMMMMMMMMMMMMMMMMMAj ∨∨∨∧∨∧∨∨∧∨∨∨∧∨∨∨∧=
)()()()()()()()(
)7643))(()((
)7643)(52(1
751651451
351721621421321
5121
MMMMMMMMMMMMMMMMMMMMMMMMAj
MMMMMMMMAj
MMMMMMMAj
∨∨∨∨∨∨∨=
∨∨∨∨=
∨∨∨∨=
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 32
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
Auswahl der VerträglichkeitsmengenAuswahl der Verträglichkeitsmengen
Z0 Z1 Z2 Z3 Z4 Z5M1 x x xM2 x x xM3 x x xM4 x x xM5 x xM6 x xM7 x x
M1={Z0,Z1,Z3}M2={Z1,Z2,Z4}M3={Z1,Z2,Z5}M4={Z1,Z3,Z5}M5={Z2,Z4}M6={Z2,Z5}M7={Z3,Z5} 47
36
25
MM
MM
MM
⊂
⊂
⊂
)43)(2()41)(32)(4321(1 MMMMMMMMMMMMAj ∨∧∨∨∨∨∨=
)()(
)(
)7643)(52(1
421321
4321
MMMMMMAj
MMMMAj
MMMMMMMAj
∨=
∨=
∨∨∨∨=
Lösung 1 Lösung 2
HS Mittweida Fachbereich Informationstechnik & Elektrotechnik Lehrgruppe Digitaltechnik Prof.Dr.-Ing.habil. Pfahlbusch 33
Digitale Systeme
© Prof.Dr.-Ing.habil.H.Pfahlbusch, Febr. 2007
ZustandsreduktionZustandsreduktion
δ X0 X1
Z0 - - - -M1 Z1 Z3 - M1 Z4 - M2
Z3 Z0 - M1 - -
Z1 Z3 - M1 Z4 - M2
M2 Z2 Z5 - M3 - -Z4 - - Z2 - M2
Z1 Z3 - M1 Z4 - M2
M3 Z2 Z5 - M3 - -Z5 Z3 - M1 - -
δ X0 X1
Z0 - - - -M1 Z1 Z3 - M1 Z4 - M2
Z3 Z0 - M1 - -
Z1 Z3 - M3 Z4 - M2
M2 Z2 Z5 - M3 - -Z4 - - Z2 - M2
Z1 Z3 - M1 Z4 - M2
M3 Z3 Z0 - M1 - -Z5 Z3 - M1 - -
Aufspaltung!Aufspaltung!
Z0
Z1Z2
X0/Y1
X1/Y1
X0/Y0 X1/Y0
δ X0 X1
Z0 Z0 Z1
Z1 Z2 Z1
Z2 Z0 Z1
λ X0 X1
Z0 Y1 Y1
Z1 Y0 Y0
Z2 Y0 Y1
Lösung !
δ/λ X0 X1
Z0 - / Y1 - / Y1
Z1 Z3 / - Z4 / -Z2 Z5 / Y0 - / -Z3 Z0 / - - / Y1
Z4 - / - Z2 / Y0
Z5 Z3 / Y0 - / Y1
X0/Y0
X1/Y1