Organisation
• in der Vorlesung wird der Stoff durchgesprochen und erläutert
• Folienkopien sind über shop.spod.ethz.ch zu beziehen
• als Ergänzung wird das Buch "Jürgen Reichardt:
Lehrbuch Digitaltechnik" empfohlen
• die prüfungsrelevanten Kapitel im Textbuch sind benannt
• Empfehlung: in Stichworten mitschreiben
• in den Übungen Vertiefung anhand konkreter Aufgaben
• die Aufgaben über shop.spod.ethz.ch beziehbar
• häusliche Vorbereitung ist notwendig !
• verlangt wird als Vorbereitung die Lösung vorab benannter
Aufgaben; diese werden in der Übung durchgesprochen
• in den 3 Tests werden Aufgaben in der Schwierigkeit der
Prüfung gestellt und entsprechend korrigiert
• im Praktikum sind 5 Versuche durchzuführen mit dem Ziel,
einen einfachen Melodie-Generator (‚Synthesizer‘) auf einem
programmierbaren Baustein (FPGA) zu entwerfen und
auszutesten
• auch hier ist häusliche Vorbereitung notwendig !
Herzlich Willkommen !
Digitaltechnik
Vorlesung, Übung, Praktikum
Herbstsemester 2015
Prof. Dr. Gerhard Tröster
Alwin Daus
Andreas Mehmann
Christian Vogt
Paul Holz
Prüfung: schriftlich im August/September 2016
Fragen, Hilfestellungen
• bei Unklarheiten, zu schneller oder zu langsamer Darstellung
- Fragen während der Vorlesung erwünscht
- MitarbeiterInnen in den Übungen und Praktikum
- ETH Edu App: Vorlesung Digitaltechnik, Praktikum Digitaltechnik
- eMail-Assistenz:
Alwin Daus
[email protected]
Christian Vogt
[email protected]
- professorale Beratung: ETZ H89 [email protected]
• Umfrage am Semesterende
Institut für Elektronik
www.ife.ethz.ch
http://www.ife.ee.ethz.ch/education/Digitaltechnik
http://www.ife.ee.ethz.ch/education/DigitaltechnikPraktikum
Digitaltechnik
HS2015
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
2
Tröster
'was ist eigentlich Elektronik ?'
Vorlesungsinhalt
'ist Elektronik dasselbe wie Elektrotechnik ?'
Einführung in die Digitaltechnik
'vom Gatter zum Mikroprozessor'
die Elektronik:
Baukasten
• stellt die Bauelemente und Methoden zur Verfügung, um
ein gewünschtes Verhalten mit Mittel der Elektrotechnik
umsetzen zu können
• logische Verknüpfungen
• Zahlensysteme, Codierung
• Aufbau und Funktionsweise von Gattern und sequenziellen
Schaltungen
• Basismodule: Speicher, programmierbare Bausteine
• wird als Basistechnologie für viele Bereiche der
Elektrotechnik, der Informatik, des Maschinenbaus und der
Verfahrenstechnik genutzt
Anwendungen
• Codeumsetzer, Zähler
• Automaten
• Rechenschaltungen
• Mikroprozessor
Nachrichtentechnik
Smartphone Internet, Satelliten Signalverarbeitung Energietechnik
wearable Comput.
Robotik Automobil e‐Mobile Solar, Wind Smart Grid Medizintechnik
Herzschrittmacher
Gentechnik MRI, CTI
Lernziele
- die Grundbegriffe der Digitaltechnik zu beherrschen
Elektronik (analog, digital,..) - die wesentlichen Baublöcke zu kennen
Integrationstechnologien, Bauelemente, Entwurfstechnik, Fabrikation - Digitalschaltungen analysieren zu können
- Digitalschaltungen selber entwickeln zu können
- Erfahrung in der Handhabung und der Einschätzung
digitaler Systeme zu gewinnen
Begeisterung für die Elektronik, die Informationstechnologie
und für die Elektrotechnik noch weiter zu steigern
Digitaltechnik
HS2015
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
Tröster
3
Digitaltechnik
HS2015
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
'was ist digital ?'
• binär:
nur zwei definierte Zustände: (0, 1), (L, H), (0V, 5V), ..
zweiwertige Logik
Reichardt Kap 1.2, 1.3
• engl. digit: Zahl
- in der Digitaltechnik wird sie verwendet; logische
Zustände könnten auch mehrere Pegel haben, z. B. ein
zusätzliches 'Zwischensignal', wenn die Photozelle halb
bedeckt ist
Beispiel: Füllstandanzeiger (für lichtundurchlässige Flüssigkeiten)
• Bit: (engl. Binary digit): binäre Stelle
• Codierung des Füllstandes: Binärbeschreibung
'Thermometercode'
'Codewort'
Gefässboden
• Code: Bit-Muster, Zuordnungsvorschrift
Fehlererkennung und -Korrektur:
• Photozelle:
- sendet ein elektrisches Signal (Strom), wenn genügend
Licht auf die Zelle trifft
Gefässboden
• Auflösung:
'wie genau kann der Füllstand angegeben werden ?'
je mehr (unterscheidbare) Binärstellen, desto höher die
Auflösung
• Definition:
keine Flüssigkeit
Flüssigkeit
Digitaltechnik
HS2015
Photozelle bestrahlt
elektrisches Signal
logischer Pegel 1
Photozelle nicht bestrahlt kein elektrisches Signal logischer Pegel 0
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
5
Tröster
Digitaltechnik
HS2015
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
6
Tröster
Codeumsetzer:
'wie ist der 10 Bit-Thermometercode einem effizienteren
4 Bit-Code zugeordnet'
• Redundanz
'wie viele Binärstellen sind notwendig, um die
Füllstandshöhe exakt beschreiben zu können?'
10-Bit auf
- für 11 unterscheidbare Füllstandshöhen {d.h. Zustände}
10 Binärstellen (Bit)
von den
Photozellen
- wenn ein Bit zwei Zustände beschreiben kann, dann
können n Bit
z=2n
4-Bit
Übertragung
Konverter
Zustände unterscheiden
'Schaltnetz'
n Bit
z Zustände
1
2
3
4
.
8
.
12
.
16
2
4
8
16
.
256
.
4096
.
65536
• Zuordnung zwischen einzelnen Codewörtern, zwischen
einem Zustand und seiner Codierung kann in einer
Wahrheitstabelle dargestellt werden:
Zustandsnummer
0
1
2
3
4
5
6
7
8
9
10
d. h. für die Codierung der Zustände der 10 Photozellen
sind 4 Binärstellen ausreichend.
- jede Wertemenge W lässt sich mit der Binärzahl kodieren
mit n  1  int(log 2 W ) Binärstellen (int: Integerfunktion)
Thermometercode 4-Bit-Code
‚Dualzahlencode‘
00 00 00 00 00
00 00
00 00 00 00 01
00 01
00 00 00 00 11
00 10
00 00 00 01 11
00 11
00 00 00 11 11
01 00
00 00 01 11 11
01 01
00 00 11 11 11
01 10
00 01 11 11 11
01 11
00 11 11 11 11
10 00
01 11 11 11 11
10 01
11 11 11 11 11
10 10
• digitale Grössen bestehen aus abzählbar vielen
Elementen (wie sieht es mit analogen Grössen aus ?)
Digitaltechnik
HS2015
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
Tröster
7
Digitaltechnik
HS2015
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
'analog - digital - kontinuierlich - diskret ?'
Signale können sowohl in ihrem Wert (Amplitude) wie in
ihrem zeitlichen Auftreten kontinuierlich und diskret sein.
Amplituden, Messwerte
analog - digital (z.B. Füllstandanzeiger)
- wie genau ?
- mit welchem Aufwand ?
Beispiel:
Zeit:
kontinuierlich - diskret
'wann soll der Füllstand abgelesen werden ?'
- wenn sich der Messwert um eine Stelle verändert:
wie schnell muss dann abgelesen werden, um diese
Änderung zu erfassen
- zu festen Zeitpunkten:
dann existiert eine feste Zuordnung zwischen
Messgrösse und Ablesezeitpunkt;
der Füllstand zwischen den Ablesezeitpunkten ist dann
nicht bekannt
• Kommunikation, Datenübertragung erfordern eine
gemeinsame Zeitbasis
Übertragung der 4-Bit-Daten über eine einzige Leitung:
Multiplexer
Demultiplexer
aus Ad van den Enden, Niek Verhoeckx, "Digitale Signalverarbeitung,"Vieweg 1990.
vier
parallele
Leitungen
Digitaltechnik
HS2015
vier
parallele
Leitungen
eine serielle
Leitung
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
9
Tröster
Digitaltechnik
HS2015
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
Gegenüberstellung: analog - digital
10
Tröster
logische Zustände, Pegel
• Vorteile der Digitaltechnik:
geringe Anforderungen an die Bauteiltoleranzen:
Photozelle an oder aus, dafür aber erhöhter Aufwand bei
der Informationsverarbeitung und -Übertragung
binäre Zustände
Zahlen
logische Zustände
physikalische Zuordnung
Low, High
Spannungen: {0V, 5V}
Schalter: {auf, zu}
Frequenzen: {F1, F2}
Morse: 'kurz, lang'
0,1
• Vorteile erkauft durch erhöhten technologischen Aufwand;
die Technologie integrierter Schaltungen stellt die
erforderliche Komplexität zur Verfügung
Wahr, Falsch
True, False
• Zuordnung von binären Zuständen/Zahlen zu einer physikalischen
Grösse ist beliebig; es gibt häufig benutzte Konventionen:
• heutiger Stand:
- 128GBit-Speicher auf Daumennagelgrösse
- Prozessoren mit mehr als 5 Milliarden Transistoren
'positive
Logik'
'wo und wozu noch analoge Schaltungen,
analoge Systeme ?'
^
0 = L = 0V (Masse )
1 =^ H = + 5V
5,5 V
‚1‘
H (High)
4,5 V
logischer Zustand
logischer Zustand
nicht
definiert;
nicht definiert
wird häufig als ‚X‘
bezeichnet
Toleranzschema für
analoge Schale
digitaler Kern
5V-CMOS-Gatterfamilie
0,8 V
‚0‘
L (Low)
0V
• mit dem Anwachsen der Digitaltechnik vergrössert sich
auch die 'Analogoberfläche'
Schalterlogik:
Konvention: Schalter geschlossen, wenn eine 1 anliegt (A=1)
Schalter offen, wenn eine 0 anliegt (A=0)
(„Schliesserprinzip“)
• analoge Technik bleibt unverzichtbar zur Kommunikation
mit der Aussenwelt: Sprache, Übertragungsmedium
(Träger)
A=0
A=1
Relais
Digitaltechnik
HS2015
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
Tröster
11
Digitaltechnik
HS2015
1. Einführung
ETH Zürich Institut für Elektronik (IfE)
Tröster
12
UND- (AND) Verknüpfung
2. Logische Verknüpfungen
'Wenn Aussage A wahr und Aussage B wahr sind, dann ist Aussage X
wahr'
Lernziele:
1. logische Grundfunktionen kennenlernen, ihre Funktion, ihre
Darstellung
Vereinbarung:
wahr (True) = logischen Zustand 1
2. Aufbau komplexer Funktionen aus zusammengesetzten
Gattern
Schalter offen:
3. Analyse komplexer Gatter: die Funktion eines aus den
Grundgattern zusammengesetzten Schaltwerkes ist zu
bestimmen
R
falsch (False) = logischen Zustand 0
I  0A
Wahrheitstabelle
Schalterlogik
(Serieschaltung)
OV
+ 5V
Textbuch Reichardt: Kapitel 3
Fall
A
beide Schalter
geschlossen:
3
I0
R
5V
X
2
B
I  0A
• Für das Arbeiten mit binären/digitalen Systemen sind
elementare Basisfunktionen erforderlich, die sich leicht in
'Elektronik' umsetzen lassen
A
1
5V
Motivation
B
^ 0V (Masse)
0 =
X
4
R>0
^ + 5V
1 =
Vorspann: Spannung, Strom, Ohm
logische Gleichung UND-Verknüpfung:
Ausgang X = Funktion(Eingänge A, B)
(verschiedene Schreibweisen)
• Elektrische Spannung U12 definiert zwischen zwei
elektrischen Potentialen e1 und e2
• e2 meist als Bezugspotential zu e2 = OV gewählt
e1
I
Spannungsquelle
Generator,
Batterie
U12 = e1 - e2
+
=-
R
e2 := 0V :
U12 Voltmeter
Ohm’sche Gesetz:
U=I.R
I = U/R
R=U/I
Bezugspotential; Masse / GND
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
X=A*B
(X = A & B)
Schaltzeichen eines UND-Gatters (Tor) mit 2 Eingängen:
&
A
•wichtig: ein definierter Spannungspegel verlangt einen
‚elektrischen Pfad‘ zur Spannungsquelle
X=A.B
X = A 
A
X
B
A
X
B
X
B
USA
genormt
2. logische Verknüpfungen
Tröster
1
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
ODER-Verknüpfung
NEGATION, INVERTIERUNG
'Wenn Aussage A wahr oder Aussage B wahr ist, dann ist Aussage X
wahr'
'Wenn Aussage A wahr ist, dann ist Aussage X falsch'
Wahrheitstabelle
Schalterlogik
Wahrheitstabelle
Schalterlogik
+ 5V
(Parallelschaltung)
+ 5V
Fall
A
B
A
R>0
X
1
I0
A
Fall
X
^ 0V (Masse)
0 =
R>0
2
^ + 5V
1 =
4
I0
X
^ 0V (Masse)
0 =
3
X
A
1
2
B
2
logische Gleichung der NEGATION:
1 ^
= + 5V
X= A
logische Gleichung der ODER (OR)-Funktion: (verschiedene
Schreibweisen)
X = A 
X=¬A
X = NOT A
X=A+B
Schaltzeichen eines Inverters, NICHT-Gliedes:
Schaltzeichen eines ODER-Gatters (Tor) mit 2 Eingängen:
A
1
A
X
B
B
genormt
X
1
A
X
A
A
X
B
genormt
USA
X
A
X
USA
1
Invertierungskreis auch
am Eingang möglich
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
3
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
4
Zusammenfassung
NAND-Verknüpfung, NAND-Gatter
Invertierung der UND-Funktion
Mit den drei Grundfunktionen UND, ODER, NICHT lassen
sich alle möglichen logischen Verknüpfungen realisieren
NAND-Gatter aus einem UND- Gatter und einem Inverter:
&
A
B
Schalterlogik
^ 0V (Masse)
0 =
R>0
1 ^
= + 5V
X
Z
I0
A
• Häufig benutzte Gatter, die aus den Grundgattern
aufgebaut sind, haben eigene Schaltzeichen erhalten
Z
Wahrheitstabelle
+ 5V
(Serieschaltung)
Zusammengesetzte Gatter
1
X
B
• 'dürfen Gatter so einfach zusammengeschaltet werden ?'
Fall
B
A
X
1
0
0
0
2
0
1
0
3
1
0
0
4
1
1
1
Z
nur wenn beide Eingänge auf 1 liegen, ist der Ausgang 0
logische Gleichung der NAND-Funktion:
?
Z  A  B Z  A  B Z  A  B Z  A & B ( Z  AB)
Schaltzeichen eines NAND-Gatters (Tor) mit 2 Eingängen:
A
A
A
&
Z
Z
Z
B
B
B
USA
genormt
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
5
NOR-Verknüpfung, NOR-Gatter
1
1
B
?
+ 5V
Z
A
Schaltnetz aus den Grundgattern UND, ODER, NICHT (mit
zusammengesetzten Gattern weitere Konfigurationen möglich)
Wahrheitstabelle
Schalterlogik
B
Fall
B
A
X
1
0
0
0
2
0
1
1
3
1
0
1
4
1
1
1
6
Entwurfsziel:
Es ist ein Schaltnetz aufzubauen, das dann eine logische 1 liefert,
wenn beide Eingangszustände gleich sind, sonst 0
(Äquivalenz = Gleichwertigkeit)
Z
X
2. logische Verknüpfungen
Tröster
ETH Zürich Institut für Elektronik (IfE)
ÄQUIVALENZ-, -Verknüpfung, XNOR-Gatter
der Ausgang eines ODER-Gatters wird invertiert
A
Digitaltechnik
HS2015
&
A
Z
Q
1
1
Z
&
S
1
B
nur wenn beide Eingänge auf 0 liegen, ist der Ausgang 1
Wahrheitstabelle:
logische Gleichung der NOR-Funktion
Z  AB
Z  AB
(Z  A B )
Schaltzeichen eines NOR-Gatters (Tor) mit 2 Eingängen:
A
1
Z
B
A
B
genormt
Z
A
Z
X
B
Fall
B
A
1
0
0
2
0
1
3
1
0
4
1
1
B
A Q=
S=
Z
USA
Z = ............................................................................................
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
7
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
8
ANTIVALENZ-, EXKLUSIV-ODER-, XOR-Gatter
Entwurfsziel:
Es ist ein Schaltnetz aufzubauen, das das dann eine logische 1 liefert,
wenn beide Eingangszustände ungleich sind, sonst 0 (Antivalenz =
Ungleichwertigkeit)
logische Gleichung der ÄQUIVALENZ-, XNOR-Funktion
Z  A  B ( Z  A  B)
Inversion des XNOR-Gatters:
A
=
A
Z
B
B

Z
Wahrheitstabelle der ANTIVALENZ-Verknüpfung:
Z
B
USA
genormt
1
X
B
A
Z
=
A
Schaltzeichen eines XNOR-Gatters (Tor) :
Fall
B
A
1
0
0
2
0
1
3
1
0
4
1
1
X
Z
logische Gleichung der ANTIVALENZ-, XOR-Funktion
Z  A  B (Z  A 
 B)
Schaltzeichen eines XOR-Gatters (Tor) :
A
=1
A
Z
B
B

Z
A
USA
genormt
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
9
Digitaltechnik
HS2015
Z
X
B
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
10
Gatter mit mehr als zwei Eingängen
Verknüpfungsmöglichkeiten bei Gattern mit
zwei Eingängen
• die Grundfunktionen sind nicht auf 2 Eingangsvariable
beschränkt, sondern verallgemeinerbar auf n Eingänge
• bei 2 Eingängen sind 4 Eingangskombinationen möglich
• zu den 4 Eingangskombination können 4 Ausgangszustände
definiert werden
Beispiel: UND-Funktion mit n Eingangsvariablen
X1
• damit sind 16 verschiedene Kombinationen von
Ausgangszuständen möglich
&
X2
Z = X1 X2 Xn
• nicht alle haben praktische Bedeutung:
Reichardt S. 36
Xn
'Wenn alle Eingänge X1 bis Xn den Wert 1 haben, nur dann ist der
Ausgang Z ebenfalls 1'
wie gross ist die Wahrheitstabelle ?
• durch jeden zusätzlichen Eingang verdoppeln sich die
Kombinationsmöglichkeiten, also bei n Eingängen sind z
Eingangskombinationen möglich mit z = 2n
Beispiel: Wahrheitstabelle eines UND-Gatters mit 3 Eingängen
Fall
C
B
A
Z
1
2
• bei einem Gatter mit n Eingängen sind 2(2n)
Kombinationen von Ausgangszuständen möglich
A
B
C
3
&
Z
4
5
6
7
8
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
11
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
12
Aufbau von Gattern mit mehreren Eingängen
weitere Gattersymbole, Konventionen
zum Beispiel durch Kaskadierung von (n-1) Grundgattern
Gatter mit Inversion am Eingang
&
&
X2
&
A
&
X1
B
Z
Z
A

1
&
Z
X
B
X
.
.
.
Xn
&
Z
zusammengesetzte Symbole
Darstellung des zeitlichen Verlaufs (waveform)
A
(z.B. Takt)
A
&
B
Digitaltechnik
HS2015
t
X
B
t
X
t
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
13
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
Schaltnetzanalyse, Schaltnetzsynthese
• Analyse:
'wie funktioniert eine vorgegebene Schaltung ?'
• Synthese:
'wie konstruiere ich ein Schaltnetz, um eine
vorgegebene Funktion zu erfüllen ?'
2. logische Verknüpfungen
Tröster
14
Beispiel
ein Schaltnetz ist vorgegeben:
1. wie sieht die Wahrheitstabelle aus
2. welche logische Funktion hat das Schaltnetz
3. welche Funktionsgleichung beschreibt das Netz
Schaltnetzanalyse
Hilfsmittel zur Analyse:
A
1. Wahrheitstabelle (Wertetabelle)
&
X
B
&
V
• zu jeder kombinatorischen Digitalschaltung existiert eine
Wahrheitstabelle
• übersichtliche Darstellung (für wenig Eingangsleitungen)
1
Z
1
Y
2. Funktionsgleichung
• die Verknüpfungseigenschaften werden verdeutlicht
• aus der Funktionsgleichung kann die Wahrheitstabelle
aufgestellt werden
• aus einer vorgegebenen Funktionsgleichung kann ein
Schaltnetz aufgebaut werden
Z = ............................................................................................
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
15
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
2. logische Verknüpfungen
Tröster
16
MOS-Transistor, MOS-FET
3. Logikschaltungen
MOS: Metal - Oxid - Semiconductor (Halbleiter)
Lernziele:
Transistor: Trans - Resistor (steuerbarer Widerstand)
• was ist ein MOS-Transistor und wie funktioniert er ?
FET: FeldEffektTransistor
• wie müssen MOS-Transistoren zusammengeschaltet sein,
um Gatterfunktionen zu realisieren?
Aufbau:
• ist ein Transistor oder Gatter beliebig schnell ?
• Basismaterial Silizium
• was ist ein Bus ? (Omnibus, Trolleybus ?)
• zwei in ihrer Funktion komplementäre Transistortypen
(CMOS: Complementary MOS)
Textbuch Reichardt:
• Kapitel 4
(schematischer) Querschnitt
Schaltkreisfamilien
• Umsetzung der logischen Verknüpfungen heute mit
Halbleiterschaltungen
- erste Rechner (K. Zuse) mit Relais
- erster 'elektronischer' Rechner (ENIAC) mit Elektronenröhren
• entsprechend der verfügbaren Halbleitertechnologie entstanden
verschiedenartige Schaltungstechniken
• Gatter, die nach einem gemeinsamen Schema aufgebaut sind, die mit
ihren Ein- und Ausgangspegel zusammenpassen, bilden eine
Schaltkreisfamilie
Name
NMOSTransistor
N: negative
Ladungen
(Elektronen)
Bauelemente
Eigenschaften
Stand/Einsatz
Dioden-Schalter
DTL
Dioden
Widerstände
einfach
zu langsam
ausgestorben
Transistor-Transistor
-Logik:TTL
Bipolartrans.
für einfache Gatter
Pegeldef.
Emitter-Coupled-Logik Bipolartrans.
ECL
schnellste Technik
hohe Leistung
Kommunikationstechnik
PMOSTransistor
NMOS
NMOS-Trans.
einfach
ersetzt durch CMOS
Complementär-MOS
CMOS
MOS
klein, billig
unempfindlich
dominierend
bis 2025 ?
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
1
Tröster
NMOS-Transistor
P: positive
Ladungen
('Löcher')
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
2
Tröster
Aufsicht CMOS -Planar-Technologie (Layoutmasse für NMOS und
PMOS annähernd gleich)
(14nm) 22nm … 0.2m
Gate-Länge
Source
GateWeite
SourceKontakt
Gate
Drain
Dimensionen Standard-CMOS-Technik
Oxiddicke unter der Gate-Elektrode:
1.2 ... 20nm (1nm = 10-9m)
Transistorgrösse (in 4-Transistor NAND 2015) :  0.04μm2
Querschnitt eines menschliches Haares:( 25μm)2.  2000μm2
keine leitende Verbindung zwischen Drain
und Source „Schalter offen“
MOS-Transistoren sind wegen ihres symmetrischen Aufbaus unipolar:
Drain und Sourceanschlüsse können vertauscht werden
der MOS-Transistor ist ein Dreipol: Drain - Gate - Source (Substrat)
Schaltsymbole: (Substrat/Bulk in Digitalschaltungen durch
Platzierung verschaltet)
D
G
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
S
D
D
G
S
B
G
D
G
S
S
S
S
leitende Verbindung zwischen Drain und
Source „Schalter geschlossen“
(Prinzip Inversionskanal)
B
G
G
D
D
G
G
D
B
S
S
B
D
N - MOS
D: Drain
G: Gate
S: Source
B: Bulk, Substrat
P - MOS
Reichardt
in Vorlesung/Übung
3
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
'wie funktioniert ein MOS-Transistor ?'
Kennlinien:
• beschreiben den Drain-Stromes ID in Abhängigkeit von den
Spannungen UGS an der Steuerelektrode Gate und der
Betriebspannung UDS zwischen Drain und Source
UTh: Schwellspannung, 'Threshold'
• NMOS, PMOS, nichtlineare Bauelemente, Dreipole
'Gartenschlauchmodell'
Drain
NMOS
ID
ID
(Steuer)Gate
U DS = const
U GS
Drain-SourceSpannung
U DS
U GS
U Th
Source
PMOS
-U GS
-U DS
-U Th
-U GS
• die Stellung (Spannung) am Steuergate bestimmt die
Durchflussmenge (Drainstrom)
U DS = const
-I D
• die Durchflussmenge (Drainstrom) hängt in Grenzen von
dem Gefälle (Potentialdifferenz, Spannung) ab
-I D
Stromstärke von ID durch die Dimensionierung der Gate-Elektrode
einstellbar:
(Gate  Weite)
ID 
(Gate  Länge)
3. Logikschaltungen
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
5
Tröster
der MOS-Transistor als Schalter
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
6
Tröster
Transmission- (Transfer) - Gate:
Parallelschaltung von NMOS- und PMOSTransistor
• für eine Gatespannung |UGS| kleiner als die
Schwellspannung |UTh| (≈ |0,7V| in 5V-Technik) ist der Kanal
Drain-Source abgeschnürt, also elektrisch nichtleitend
Schalter offen;
nicht im Textbuch
• für Gatespannungen grösser als die Schwellspannung ist der
Drain-Source-Kanal niederohmig (einige Kiloohm), also
elektrisch leitend
Schalter geschlossen
aber
• wegen der Nichtlinearität des Kanalwiderstandes kann der
NMOS- Transistor nur den Low-Pegel
und
der PMOS-Transistoren nur den High-Pegel
sicher schalten: die Drain-Source-Spannung UDS  O V
mit G 1= G 2 (gegenphasig)
G1
G1
G2
G2
Schaltsymbole
Komplementärtechnik
Schaltpegel
+ (5V)
S
PMOS
+
+
S
+
+ (5V)
S
S
G
0V
UGS
S
UDS
G
D
D
D
D
D
+ (5V)
+ (5V)
D
NMOS
D
G
S
S
S
S
1
für
D
UGS
A
UDS
G
S
• mit Transmissiongates können Logikgatter aufgebaut
werden, z.B.
D
D
S = 0 -> Z = A
Z
S
S = 1 -> Z = B
B
Schaltfunktion
Schaltfunktionen
Digitaltechnik
HS2015
nicht
geeignet
nicht
geeignet,
da |UDS|  |UTh GS|
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
Wertetabelle ?, logische Gleichung ?
7
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
Schalterlogik
CMOS-Inverter
+ 5V
Schaltbild:
Gegentakt- ,
'Push/Pull'- Stufe
(Totem-pole)
Reichardt S. 146
Z
A
S
D
1
A
Z
D
S
CMOS-Inverter
• immer (mindestens) ein Strompfad zwischen
Versorgungsspannung/Masse und Gatterausgang
Übertragungskennlinie: (statisch)
Abhängigkeit der Ausgangsspannung am Knoten Z von der
Eingangsspannung am Knoten A
• im durchgeschalteten Zustand keine Stromaufnahme
• keine statische Leistung zum Ansteuern notwendig;
Ausgangsspannung UZ [V]
• im Übergangsbereich fliesst ein Querstrom;
Übergangsbereich:
beide Transistoren
leitend
5
• die Treiberfähigkeit hängt von der Transistorgrösse ab
• das Inverterprinzip gilt für alle statischen CMOS-Gatter
PMOS T1
leitend
PMOS T1
gesperrt
NMOS T2
gesperrt
NMOS T2
leitend
Struktur von statischen CMOS-Gattern
+
„pull-up“
Eingänge
PMOS
A
B
.
.
X
0
0
Z
.
.
NMOS
5
Ausgang
„pull-down“
Eingangsspannung UA [V]
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
9
Tröster
Digitaltechnik
HS2015
NAND- und NOR- Gatter in CMOS-Technik
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
10
Tröster
NOR-Gatter
NAND-Gatter:
Reichardt S. 151ff
A
S
S
1
Z
B
D
D
D
&
S
D
S
Wahrheitstabelle
Wahrheitstabelle
Fall
A
B
1
L
L
H
Fall
A
B
2
L
1
L
L
3
H
L
2
L
H
4
H
H
3
H
L
4
H
H
Digitaltechnik
HS2015
T1
T2
T3
T4
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
Z
11
Digitaltechnik
HS2015
T1
?
T2
T3
T4
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
Z
12
'wie schnell schalten CMOS-Gatter ?'
Konstruktion von CMOS-Gattern
Reichardt S. 148
Kaskade von zwei
CMOS-Inverter mit
parasitären Kapazitäten
 statische CMOS-Gatter bestehen aus genauso vielen NMOSwie PMOS-Transistoren:
bei m Eingängen m NMOS- und m PMOS-Transistoren
 wenn NMOS-Transistoren in Serie geschaltet ( UNDVerknüpfung), dann sind die entsprechenden PMOSTransistoren parallel angeordnet
+ 5V
+ 5V
•
•
•
•
•
•
•
•
•
 wenn NMOS-Transistoren parallel geschaltet (ODERVerknüpfung), dann sind die entsprechenden PMOSTransistoren in Serie angeordnet
•
•
• Laufzeit, Verzögerungszeit:
Ansprechverzögerung im Gatter, bis die Umladung der
Gate-Elektrode am Ausgang wirksam wird
• Umladung von internen und externen Kapazitäten;
Umladezeit abhängig von der Grösse der Kapazitäten und
dem Kanalwiderstand der MOS-Transistoren
charakteristische Zeitkonstante:  = RMOS-Kanal . Cparasitär
 statische CMOS-Gatter invertieren das Ausgangssignal
(‚Inverterprinzip‘ von MOS-Transistoren)
UA [V]
Beispiel:
zusammengesetzte Gatter, Komplexgatter
Zeitablaufdiagramm an einem Inverter:
1
A
50%
A
•
Z
&
t
B
1
Z
UZ [V]
90%
C
t pHL
50%
t pLH
10%
tr
ttLH
tf
t tHL
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
13
Tröster
Kenndaten für das dynamische Verhalten
(CMOS):
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Verzögerungszeit
• Transistor-Drainstrom ID :
 Gate  Weite
beim Übergang H L
mit
(Propagation delay High Low) gemessen bei 50% des Pegelhubs
tpLH
Verzögerungszeit
beim Übergang L H
Anstiegs- (Rise-) Zeit
Transition Low High
gemessen zwischen 10% und 90%
des Pegelhubs
tf
ttHL
Abfall- (Fall-) Zeit
Transition High Low
gemessen zwischen 90% und 10%
des Pegelhubs

d ox Gate  Länge
cm 2
 : Beweglichkeit der Ladungsträger [
Vs ]
dox : Dicke des Oxids unter der Gate-Elektrode

• (mittlere) Driftgeschwindigkeit v der Ladungsträger:


v  E

E : elektrische Feldstärke
mit
(Propagation delay Low High) gemessen bei 50% des Pegelhubs
tr
ttLH
14
Tröster
MOS-Transistor: Ladungsträgerbeweglichkeit
ID 
tpHL
t
• Beweglichkeit der Ladungsträger  abhängig von dem
jeweiligen Material, Temperatur, dem Ladungsträgertyp
(Elektronen oder Löcher) und von der
Ladungsträgerkonzentration
• Verzögerungszeit ist bestimmt durch die interne Struktur
des Gatters
• Beweglichkeit für verschiedene Halbleitermaterialien bei
Raumtemperatur und geringer Ladungsträgerkonzentration
• Anstiegs- und Abfallzeiten hängen von der Treiberleistung
der Ausgangsstufe und der externen Last ab
Beweglichkeit[ cm 2 / Vs ]
Elektronen n
Löcher p
1350
480
Germanium Ge
3900
1900
GaAs
8600
250
InGaAs/InPn
12000
Silizium Si
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
15
Digitaltechnik
HS2015
Polymere (‚Plastik’)
10-3 – 10
10-3 – 10 (!)
Graphene
 350.000
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
16
'open collector', 'open drain' - Verbindung, WiredVerknüpfungen (AND, OR)
'was ist eine (Kommunikations-) Bus ?'
Reichardt Kap 9.5
+ 5V
Beispiel: Personalcomputer
Terminal
Drucker
CD-ROM
Empfänger
R
Busleitung
Y
YA
YB
A
Bus
BusTreiber
Sender 1
Fall
• Busse gewährleisten die Kommunikation zwischen
verschiedenen Modulen in elektronischen Systemen.
 die Busleitung behält den High-Pegel, solange kein Bustreiber
durchschaltet
 in ihrer logischen Funktion beeinflussen sich die Bustreiber
nicht
 wodurch ist der Spannungspegel auf der Busleitung bestimmt
(Übung !)
+ 5V
Y
B=H
1
Z
1
Beispiel: I2C-Bus
(Inter-IntegratedCircuit Bus)
SDA: serial data line
SCL: serial clock line
Y
3. Logikschaltungen
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
17
Tröster
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
+ 5V
Reichardt Kap 9.5.3
AnsteuerLogik
• 'galvanische' Trennung der Logikstufen von der
gemeinsamen Busleitung, z. B. durch ein
Transmissiongate
• neben den Pegeln Low und High sind weiterer
Pegeldefinitionen notwendig
'don't care'
Z
hochohmig, schwebend,
'floating', OFF-state
A
?
P
Fall
EN
A
1
0
x
2
0
x
3
1
0
4
1
1
X
N
Enable (EN)
Ausgang unabhängig vom
Eingangspegel, aber 0 oder 1
Ausgang beeinflusst nicht die
angeschlossen Schaltungen
A
18
Tröster
Beschaltung eines CMOS-Tristate-Buffers
Tristate- (Three-State) Logik (3-state)
'x'
BusY
YA
A
4
Bus
A=L
YB
3
direkte Anbindung von CMOS-Gattern nicht zulässig:
B=H
B
2
wie ist die elektrische Verbindung zu den Busleitungen
aufzubauen?
Z
BusTreiber
Sender 2
1
• Mehrere Teilnehmer kommunizieren als Empfänger oder
Sender über eine gemeinsame 'Leitung' (Ressource)
A=L
N
Wahrheitstabelle
• Busse können aus mehreren Leitungen aufgebaut sein (z.B.
4, 8, 16, ..64,..Bit)
+ 5V
B
N
X
?
P
N
X
Z
Z
0
1
E
CMOS-Inverter mit Tristate-Ausgang
Reichardt S. 156
Schalterlogik:
Wahrheitstabelle
+ 5V
Fall
X
B
A
EN
A
Bus B
X
1
2
3
Enable (EN)
'Freischaltung'
4
Tristate-Inverter
A
B
A
EN
EN
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Y
Tröster
19
Digitaltechnik
HS2015
3. Logikschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
20
'Bausteine'
4. Schaltalgebra, Boolesche Algebra
Elemente: Binärsystem: 0 und 1
Operationen:
Lernziele:
binäre: UND, ODER;
unär: NICHT
Verknüpfungen zweier Konstanten
1. die Grund- und Rechenregeln der Booleschen Algebra
kennenlernen;
Reichardt S. 25
UN D
2. die Anwendung auf die Analyse und den Entwurf von
Digitalschaltungen einüben;
OD ER
Parallelschaltung
Serienschaltung
(eine grundlegende Herleitung der Booleschen Algebra wird
in Mathematik-Vorlesungen gegeben)
Textbuch Reichardt:
















• Kapitel 3
Motivation:
• die Schaltalgebra ist nicht an eine bestimmte
Bauelementtechnologie gebunden
• da binäre Zustände direkt in Digitalschaltungen umgesetzt
werden können, erleichtern und vereinfachen abstrakte
Regeln den Schaltungsentwurf
NICHT
1 =0
Digitaltechnik
HS2015
4. Schaltalgebra
ETH Zürich Institut für Elektronik (IfE)
1
Tröster
0 =1
4. Schaltalgebra
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
Verknüpfungen einer Konstanten mit einer
Variablen
2
Tröster
Verknüpfungsgesetze
Reichardt Kap. 3.4.2/3.4.3
Reichardt Kap. 3.4.1
UN D

NullTheorem
Kommutativität (Vertauschungsgesetz)
OD ER




• 'die Reihenfolge der Variablen in UND-Verknüpfungen und
in ODER-Verknüpfungen beeinflusst das Ergebnis nicht'

UND
C
A

EinsTheorem




IdemPotenz
B

ODER

A







B
C

C
A
B
B
C
Z = A  B  C = C A  B

A
Z =  B  C = C  A  B
Assoziativität (Zuordnungsgesetz)
'Variablen können zu Gruppen zusammengefasst werden'







UND
Z = A  (B  C) = (A  B)  C
ODER
Z = A (B C) = (A B) C

NICHT

Digitaltechnik
HS2015
4. Schaltalgebra
ETH Zürich Institut für Elektronik (IfE)
Tröster
3
Digitaltechnik
HS2015
4. Schaltalgebra
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
Verknüpfungsgesetze
Verknüpfungsgesetze
Reichardt Kap. 3.4.4/3.4.6
Reichardt Kap. 3.9
Bindungsregeln (Vorrangregeln)
Distributivität (Verteilungsgesetz)
•'gemeinsame Variablen können verteilt ('ausmultipliziert,
ausgeklammert') werden
A
B
C
• eine Regelung ist notwendig, da sonst die Eindeutigkeit
nicht gewährleistet ist
disjunktiv
konjunktiv
A
• 'welche der Operationen (UND/ODER/NICHT) hat höhere
Priorität ?'
B
A
A


B
C
Beispiel:
B
die Gleichung Z = A B C mit A = B = 1, C = 0 ergibt
je nach Reihenfolge der Berechnung
A
C
A
C
Z = (A B) C = (1 1) 0 = 0
Z = A (B C) = 1 (1 0) = 1
(A B) (A C) = A  (B C)
(A B)  (A C) = A  (B C)
daher als Regeln/Prioritäten
1. Klammern
2. Negation ¬
Vereinfachungsregeln
3. {UND, AND,ODER,NOR} vor {EXOR,XNOR}
4. {UND, AND,ODER,NOR} und {EXOR,XNOR} untereinander
gleichwertig
Adsorptionsgesetze
A  ( A  B) = A  B
A  ( A  B) = A  B
und
• entgegen Regel 4 ist die Vereinbarung „UND-Verknüpfung
vor ODER-Verknüpfung“ in einigen Lehrbüchern und
Simulationstools implementiert; daher eindeutigen Ablauf
(z.B. bei obigem Beispiel) durch Klammern festlegen
Absorptionsgesetze
A  (A  B) = A
und
A  (A B) = A
Nachbarschaftsgesetze
(A B)  ( A  B) = B
Digitaltechnik
HS2015
und (A B)  ( A  B) = B
4. Schaltalgebra
ETH Zürich Institut für Elektronik (IfE)
5
Tröster
Digitaltechnik
HS2015
4. Schaltalgebra
ETH Zürich Institut für Elektronik (IfE)
6
Tröster
De Morgan‘sche Regeln
De Morgan‘sche Regeln
Reichardt Kap. 3.4.5
• 'welche Beziehungen bestehen zwischen der UND  ODER,
NAND  NOR, ist ein gegenseitiger Austausch möglich ?'
Beweis für 2 Variablen anhand einer Wahrheitstabelle:
Erstes De Morgansche Gesetz:
A
AB
=
A  B
AB
=
A  B
&
X 
B
1
A
X
B
Fall
B
A
AB
1
0
0
00 =
11 =
A  B
2
0
1
01 =
3
1
0
10 =
4
1
1
11 =
AB
A B
00 =
11 =
10 =
01 =
10 =
01 =
10 =
01 =
00 =
11 =
00 =
NAND-Funktion kann durch eine ODER-Funktion mit invertierten
Eingängen ersetzt werden
die DeMorgan‘sche Gesetze sind verallgemeinerbar auf
mehrere Variable:
Zweites De Morgan‘sche Gesetz:
A
B
A B
=
A  B
AB
=
A  B
1
X 
A
1. Gesetz
Z = A  B  C  ...
= A  B  C 
2. Gesetz
Z = A  B  C  ...
= A  B  C 
&
X
B
NOR-Funktion kann durch eine UND-Funktion mit invertierten
Eingängen ersetzt werden
Digitaltechnik
HS2015
4. Schaltalgebra
ETH Zürich Institut für Elektronik (IfE)
Tröster
7
Digitaltechnik
HS2015
4. Schaltalgebra
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
Erweiterungen
Grundgatter, Universalgatter
Negation der ersten De Morgan‘schen Regel
AB = A  B
A
&
B
• mit den Grundgattern UND, ODER, NICHT kann jede logische
Verknüpfung realisiert werden
 A  B = A  B
X

• die De Morgan‘sche Regeln ermöglichen den Ersatz von
Grundgattern
1
A
X
B
• jedes 'Universalgatter' NAND oder NOR allein ist
ausreichend !
1
die UND-Funktion kann
durch die NOR-Funktion
ersetzt werden
A
1
1
X
B
Negation der zweiten De Morgan‘schen Regel
AB =
A
B
A  B
 A B=
1
X

UND, NICHT
ODER, NICHT
Grundgatter
UND, ODER, NICHT
A  B
A
&
B
X
NOR
NAND
&
die ODER-Funktion kann
durch die NAND-Funktion
ersetzt werden
Digitaltechnik
HS2015
A
B
&
&
4. Schaltalgebra
ETH Zürich Institut für Elektronik (IfE)
Tröster
X
9
Digitaltechnik
HS2015
4. Schaltalgebra
ETH Zürich Institut für Elektronik (IfE)
Tröster
10
Synthesemöglichkeiten
5. Schaltungssynthese
'wie kommen wir von einer gegebenen Aufgabenstellung
zu einem Schaltplan'
Lernziele:
• Normalformen
• Karnaugh-Diagramm
• Aufspüren und Beseitigen von Hazards
verbale
Formulierung
Funktionsgleichung
Wertetabelle
Variablenzuordnung
Textbuch Reichardt:
• Kapitel 3.6, 6 (teilweise)
Motivation:
Wertetabelle
• Boolesche Algebra, Rechenregeln, Grundgatter: damit
können wir jede kombinatorische Schaltung aufbauen
Normalformen
Vereinfachung
Logikminimierung
• die Voraussetzungen und die Grundlagen sind vorhanden,
um Schaltungen synthetisieren zu können
> Boolesche Algebra:
mathematische Grundlage
Rechenregeln, Schaltalgebra
logische Verknüpfung von Variablen
Wahrheitstabelle
Funktionsgleichung
Schaltplan
> die notwendigen Grundgatter sind eingeführt, mit denen
jede kombinatorische Schaltung realisiert werden kann
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
1
Tröster
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
2
Tröster
Minterm  Produktterm Vollkonjunktion
Definitionen:
Schaltfunktion, Min- Maxterme; Normalformen
Reichardt, S. 44
Minterme sind UND-Verknüpfungen, die alle Schaltvariablen genau
einmal in negierter oder nichtnegierter Form enthalten
• bei n Schaltvariablen gibt es 2n verschiedene Minterme
z.B. bei zwei Variablen A und B
• eine Schaltfunktion ist eine eindeutige
Zuordnungsvorschrift, die jeder Wertekombination von
Variablen einen Wert zuordnet, also jeder der 2n
Wertekombinationen
AB
A  B
A B
A  B
jeder Minterm hat nur bei einer Kombination der Wertetabelle den
Wert 1, bei allen anderen Kombinationen den Wert 0
x1, x2, ..., xn mit xi  {0,1} (i = 1,2,...,n)
A, B, C...
Fall
A
B
1
0
0
ƒ(x1, x2, ..., xn )  {0,1}
2
0
1
ƒ(A, B, C, ..)
3
1
0
4
1
1
wird durch die Zuordnungsvorschrift ƒ eindeutig ein
Funktionswert
zugeordnet. Mit
AB
AB
A B A  B
• wie findet man den Minterm, der bei einer bestimmten
Werte-Kombination den Wert 1 hat ?
y = ƒ(x1, x2, ..., xn )
y = ƒ(A, B, C, ..)
> die UND-Verknüpfung aus allen Schaltvariablen benennen
und die Variablen negieren, die bei dieser Kombination
den Wert 0 haben
'ist y eine Funktion von x1, x2, ..., xn '
A, B, C, ..
> Beispiel: zu der Wertekombination 1 0 gehört der Minterm
A B
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
3
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
Maxterm Summenterm Volldisjunktion
Zweistufige Normalformen
Reichardt, S. 25
Maxterme sind ODER-Verknüpfungen, die alle Schaltvariablen genau
einmal in negierter oder nichtnegierter Form enthalten
• bei n Schaltvariablen gibt es 2n verschiedene Maxterme
z.B. bei zwei Variablen A und B
A  B
AB
A B
A  B
A
B
1
0
0
2
0
1
3
1
0
4
1
1
AB
A B
die zweistufige kanonisch konjunktive Normalform KNF (UNDNormalform) besteht aus der konjunktiven (UND-) Verknüpfung aller
Maxterme einer Schaltfunktion
A B A  B
Beispiel: (Funktion y = ƒ (A,B,C) ist vorgegeben)
• wie findet man den Maxterm, der bei einer bestimmten
Kombination den Wert 0 hat ?
> die ODER-Verknüpfung aus allen Schaltvariablen
benennen und die Variablen negieren, die bei dieser
Kombination den Wert 1 haben
Beispiel: zu der Wertekombination 1 0 gehört der Maxterm
A  B
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
die zweistufige disjunktive Normalform DNF (ODER-Normalform)
besteht aus der disjunktiven (ODER-) Verknüpfung von einem oder
mehreren Mintermen einer Schaltfunktion
die zweistufige kanonisch disjunktive Normalform (ODERNormalform) besteht aus der disjunktiven (ODER-) Verknüpfung aller
Minterme einer Schaltfunktion
jeder Maxterm hat nur bei einer Kombination der Wertetabelle den
Wert 0, bei allen anderen Kombinationen den Wert 1
Fall
Reichardt, S. 32
5
Tröster
A
B
C
y = ƒ (A,B,C)
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
1
1
0
0
Digitaltechnik
HS2015
Minterme
Maxterme
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
6
Tröster
'wie kann eine Funktionsgleichung
vereinfacht und minimiert werden ?'
zweistufige kanonisch disjunktive Normalform DNF:
ƒ (A,B,C) = ( A  B  C )  ( A BC)  (A B  C )  (A B C)
• die kanonische Normalformen geben nicht
notwendigerweise die einfachsten Gleichungen an
zweistufige kanonisch konjunktive Normalform KNF :
Vereinfachung von Schaltfunktionen
ƒ (A,B,C) = (AB C )  (A B C)  ( A  B C)  ( A  B  C )
• mit den Gesetzen der Schaltalgebra
• mit KV-Diagrammen
• Methode von Quine-McCluskey
Bedeutung der zweistufigen kanonischen
Normalformen:
Möglichkeiten der Schaltalgebra
Jede Schaltfunktion ist darstellbar in der kanonisch disjunktiven
Normalform und in der kanonisch konjunktiven Normalform.
• Ausklammern, Kürzen, Zusammenfassen, DeMorgan
Beide Darstellungen sind äquivalent und ineinander überführbar
(Dualität).
Beispiel:
ƒ (A,B,C) = ( A  B  C )  ( A B C )  (A B C)  (ABC)
Ausklammern von ( B B)
Schaltungssynthese
= ( A  C )( B B)  (AC)( B B)
Zu jeder Wahrheitstabelle können systematisch
Funktionsgleichungen in Form der kanonische Normalformen erstellt
werden
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
7
= ( A  C )  (AC)
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
Karnaugh (KV)-Diagramm
• die Existenz einer Vollkonjunktion (Minterm) in einer
gegebenen Funktionsgleichung oder Wertetabelle wird
durch eine 1 in dem entsprechenden Feld gekennzeichnet
Reichardt, Kap 6.2 f
• übersichtliche Darstellung der zweistufigen Normalformen
als eine zweidimensionale Wertetabelle
Beispiel:
Konstruktionsprinzip für die ODER (disjunktive)
Normalform DNF
ƒ (A,B) = ( A  B )  (A B )
A
A
• das KV-Diagramm einer Funktionsgleichung mit n Variablen
besteht aus 2n Felder
• jede Variable erscheint in ihrer negierten und nichtnegierten
Form, und zwar an der gleichen Diagrammseite
B
• jedes Feld ist reserviert für eine Vollkonjunktion (Minterm)
entsprechend der Zuordnung der Variablen an den Rändern
B
KV-Diagramm für 2 Variable A und B:
B
A
A
AB
AB
A B
B
¬B
alternative Form
(Reichardt, S. 92)
B
Digitaltechnik
HS2015
• orthogonal benachbarte Vollkonjunktionen können zu
einem 'Päckchen' (auch Implikant, Block oder Schleife)
zusammengefasst werden
• diese Päckchen (Primimplikanten[Reichardt]) enthalten
Variable in ihrer negierten und nichtnegierten Form, die bei
der Koordinatenbeschreibung dieses Päckchens entfallen
können; damit vereinfacht sich die Schaltfunktion
AB
¬A
A
AB
A B
AB
AB
• Beispiel:
ƒ (A,B) = ( A  B )  (A B )
Distributivität, Ausklammern von ( A A), Nachbarschaftsgesetz
= ( A  A)  B
= B 
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
9
Tröster
5. Schaltungssynthese
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
10
Tröster
KV-Diagramme mit 3 Variablen
• bei mehreren Päckchen besteht die vereinfachte
Schaltfunktion aus der ODER-Verknüpfung der einzelnen
Päckchenterme und eventuell übriggebliebener Einzelfelder
Reichardt, S. 92
Beispiel
A
ƒ (A,B) = ( A  B )  ( A B)  (A  B )
3 Möglichkeiten der Zusammenfassung
A
A
B
B
1
A
1
B
1
B
1
A
A
1
B
1
B
(A,B) = ..............
(A,B) = ..............
B
A
1
1
B
1
C
(A,B) = ..............
C
C
• statt einer dreidimensionalen zylinderförmigen Struktur des
KV-Diagramms wird ein zweidimensionales Diagramm mit
erweiterten Nachbarschaftsbedingungen benutzt
die Blöcke sind möglichst gross zu wählen
• ein Päckchen darf nur 2i, i = 0, 1, 2, ... Elemente besitzen
weitere Beispiele:
Digitaltechnik
HS2015
A
• jedes Päckchen muss rechteckig sein (4 Ecken)
A
A
B
1
1
B
B
1
1
B
A
A
1
1
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
11
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
12
KV-Diagramme mit 4 Variablen
Beispiele für erweiterte Nachbarschaftsbedingungen:
Reichardt, S. 94
ƒ(A,B,C) = ...................
ƒ(A,B,C) = ...................
1
1
erweiterte Nachbarschaft auch
über die Ecken (Kugelform)
1
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
13
Tröster
KV-Diagramme mit 5 Variablen
Digitaltechnik
HS2015
1
CD
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
14
Tröster
KV-Diagramm der UND-(konjunktive)
Normalform KNF für die Variablen A und B
Reichardt, Kap 6.2.2)
• jedes Feld im KV-Diagramm ist reserviert für eine
Volldisjunktion (Maxterm: ODER-Verknüpfung = 0)
entsprechend der Zuordnung der Variablen an der Rändern
A
A
B
A B
AB
B
AB
A B
Beispiel:
A
A B (A,B)
KV-Diagramme mit mehr als 5 Variablen
• bei mehr als 5 Variablen ist die Übersichtlichkeit und
Handhabbarkeit sehr erschwert
0
0
1
0
1
0
1
0
1
1
1
0
• Vereinfachung zu
A
B
B
ƒ (A,B) =
• komplexere Systeme versucht man daher zuerst zu
vereinfachen, oder setzt Computerprogramme ein
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
15
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
16
alternative Bezeichnung des KV-Diagramms
KV-Diagramme für die UND (konjunktive)
und die ODER (disjunktive) Normalform
nicht im Textbuch,
aber in den Übungen
• für KV-Diagramme der beiden Normalformen gelten
ähnliche Konstruktions- und Auswerteregeln
• statt die Variablen an alle 4 Seiten anzuordnen, werden sie
häufig paarweise an der oberen und der linken Kante
aufgetragen
• beide Diagramme sind zueinander komplementär: aus
einem vollständigen Diagramm kann die konjunktive und
disjunktive Normalform entnommen werden
• die Binärkombinationen dürfen sich in vertikaler oder
horizontaler Richtung nur um jeweils einen Wert ändern
(sog. einschrittiger Code)
Beispiel:
KV-Diagramm mit 4 Variablen
Gegenüberstellung:
ODER (disjunktive)
UND (konjunktive)
A
Normalform
A
CA
2n- Felder bei n Variablen
Variable (original und negiert) an den Rändern
Minterme
in den Feldern
Maxterme
1
mit dem Wert
0
10
11
01
DB
00
01
D
11

B
D
orthogonal benachbarte
Minterme
Maxterme
können zu Päckchen zusammengefasst werden
10
B
die vereinfachte Schaltfunktion besteht aus der
ODER-Verknüpfung
D
00
UND-Verknüpfung
C
der einzelnen rechteckigen Päckchenterme mit 2i Elementen
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
17
Tröster
Digitaltechnik
HS2015
don't care Zustände
 ( A BCD)7  (A B  C  D )8
 (A B C D )10  (AB C  D )12
• Beispiel:
In einer Digitaluhr, die auch die Monate anzeigt, soll eine
möglichst einfache Schaltung entworfen werden, die die
Monate mit 31 Tagen detektiert.
Januar
Februar
März
April
Mai
Juni
Juli
August
September
Oktober
November
Dezember
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
18
Tröster
ƒ(A,B,C,D) = ( A  B  C D)1  ( A  B CD)3  ( A B C D)5
Reichardt, Kap 6.2.3
1
2
3
4
5
6
7
8
9
10
11
12
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Kanonische disjunktive Normalform der Funktion ƒ(A,B,C,D),
die alle Monate mit 31 Tagen benennt:
Es gibt Wertetabellen, in denen nicht für jede der 2n -Kombinationen
der Eingangsvariablen ein Wert der Ausgangsvariablen definiert ist.
Diese don't care Terme werden meist mit X gekennzeichnet und
dürfen den Wert 0 oder 1 annehmen
Die 12 Monate sind mit 4 Bit codiert, also
Wertetabelle:
Nr
Monat
Codierung
A B C D
C
C
KV-Diagramm:
CA
DB
01
31 Tage
11
1
0
1
0
1
0
1
1
0
1
0
1
1
12
00
X
14
X
1
X
15
13
7
1
5
1
10
00
10
11
01
3
1
8
1
1
1
X
10
0
don't care Terme (nichtexistierende Monate)
0
0 0 0 0
13
14
15
Digitaltechnik
HS2015
1
1
1
1
1
1
0 1
1 0
1 1
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
19
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
20
A
A
A
A
1
I1
B
D
X
12
X
1
X
15
13
5
3
B
I
1
10
1
II
C
7
C
1
1
1
10
8

D
1
D
X
1
5
3
B
0
X
0
D
C
C
C
ƒ(A,B,C,D)
• die Funktion kann vereinfacht werden zu
= (A D )  ( A D)
= AD
ƒ(A,B,C,D) = (A C  D )  (A B  D )  ( A D)
II
1
X
15
13
1
C
I
D
X
D
III
1
1
14
X

1
7
1
8
B
14
12
(ANTIVALENZ)
• Ergebnis:
Aufwand zur Implementierung der Wertetabelle
III
• eine weitere Vereinfachung ist möglich, wenn dem 'don't
care' Term 14: ABCD = 1110 der Wert 1 zugewiesen wird, da
dann die Päckchen I und II zusammenzufassen sind
Anzahl Verknüpfungen
27
7
3
kanonische ODER-Normalform:
mit KV-Diagramm
mit 'don't care' Term
'don't care' Terme dürfen genutzt werden, um Funktionsgleichungen
zu vereinfachen
• welches Ergebnis liefert die konjunktive Normalform ?
5. Schaltungssynthese
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
21
Tröster
5. Schaltungssynthese
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
Mehrstufige Logik
Hazards (Spikes, Glitches)
Störungen in Digitalsystemen
• jede logische Funktion kann auf eine zweistufige Form
abgebildet werden
Reichardt, S. 104
• mehrstufige Logik benötigt i.allg. weniger Gatter, aber
bedingt längere Verzögerungszeiten
• bisher wurde angenommen, dass die realen zeitlichen
Verzögerungen in den Verknüpfungsgattern keine
Verfälschung der logischen Funktion hervorruft
• (Gegen) Beispiel:
im eingeschwungenen Zustand ist die Funktion
• die Umwandlung einer zweistufigen in eine mehrstufige
Logik kann durch Faktorisierung erfolgen; Beispiel
ƒ =ADF+AEF+BDF+BEF+CDF+CEF+G
= (A D + A E + B D + B E + C D + C E ) F + G
ƒ(A) = A  A 
= [(A + B + C) D + (A + B + C) E] F + G
immer 1
Inverter und ODER-Gatter mit realen Laufzeiten (tpd:
Propagation Delay)
=(A + B + C) (D + E) F + G
=XYF+G
22
Tröster
mit
X=A+B+C;Y=D+E
A
D
F
A
E
F
B
D
F
B
E
F
C
D
F
C
E
F
1
Z
2
3
4
7
ƒ
A
B
C
1
D
E
2
X
Y
3
4
ein Hazard tritt auf, da die Signale A und A nicht
'gleichzeitig' an dem ODER-Gatter anliegen
ƒ
F
G
5
zweistufig
1
aus
R.Katz, „Contemporary Logic Design“,
Benjamin/Cummings, 1994
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
Signal A
0
Ausgang Z
1
• (heuristische) Verfahren zur Faktorisierung werden in
Synthesetools eingesetzt
Digitaltechnik
HS2015
A
0
6
G
Eingang
1
dreistufig
0
Hazard
‘kurzzeitige und unerwünschte
Änderung von Signalwerten’
(Reichardt)
23
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
24
'wodurch entstehen Hazards ?'
'wie können wir Hazards aufspüren'
• Signale werden in Schaltnetzen unterschiedlich lange verzögert, abhängig
• (statische) Hazards entstehen, wenn ein Signal von einem
logischen Zustand in den anderen invertiert und der
Ausgangswert unverändert bleibt
von den Laufzeiten in den einzelnen Gattern
• Signalwechsel können daher zu unterschiedlichen Zeitpunkten an einem
Gatter anliegen und ein ungewolltes Schalten des Gatters bewirken
• Dieser Wechsel ist im KV-Diagramm markierbar
• Hazards können zu Fehlfunktionen in digitalen Systemen führen (z.B.
wenn Datenspeicher falsch adressiert werden)
• Klassifizierung von Hazards
> statische Hazards (Strukturhazards):
Beispiel:
ƒ(ABCD) = (AB)  ( B C)
disjunktiv
ƒ(ABCD) = (A B )  (BC)
konjunktiv
wenn nur ein Signalwechsel zwischen dem negierten und
nichtnegierten Zustand an einem Gatter auftritt
ƒ
ƒ
AA
AA
CA
t
statischer 0-Hazard
01
11
10
00
01
1
1
0
0
11
1
1
0
0
0
1
1
0
0
1
1
0
DB
t
statischer 1-Hazard
> funktionale Hazards:
wenn mehrere Signale schalten, z.B. von ABC = 111 nach ABC = 000, ist es
sehr unwahrscheinlich, dass alle 3 Zustände 'gleichzeitig' wechseln, eher
kritischer Übergang
zw ischen B u nd B
z.B. 111  101  001  000. Diese Hazards sind mehr begründet in der
logischen Funktion als in der Implementierung
10
> dynamische Hazards (mehrere Wechsel)
ƒ
00
t
Gegenmassnahmen:
• Angleichen der Verzögerungen, z.B. durch Verzögerungselemente
> riskant, da temperatur- und typenabhängig
Hinweis:
Wenn sich ‘Päckchen’ diagonal berühren, wechseln (mindestens) zwei
Signale.  kein Struktur-, sondern ein funktionaler Hazard
• besser: systematische Vorgehensweise
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
25
Tröster
5. Schaltungssynthese
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
A
Schaltnetz
B
&
B
A
1
&
1
0
0
D
1
1
0
0

ƒ
C
B
1
B
&
ƒ
C
zusätzliche
Blöcke
D
1
B
1-H azard
A
1
A
26
Tröster
0
1
1
0
0
1
1
0
B
0-H azard
die Stellen im KV-Diagramm, an denen sich Päckchen berühren,
markieren kritische Signalwechsel
C
D
C
C
erweiterte, 'hazardfreies' Schaltnetze
Abhilfe
B
sich berührende Päckchen durch eine zusätzliche Schleife verbinden
&
B
A
&
• neue Funktionsgleichung (disjunktiv):
ƒ(ABCD) = (AB)  ( B C)  (AC)
A
1
C
&
B
> der Term (AC) ist immer 0, wenn B invertiert
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
&
ƒ
C
1
B
• neue Funktionsgleichung (konjunktiv):
ƒ(ABCD) = (A B )  (BC)  (AC)
Digitaltechnik
HS2015
1
ƒ
> der Term (AC) ist immer 1, wenn B invertiert (von B nach
B und umgekehrt)
1
Hinweis:
Wenn sich ‘Päckchen’ diagonal berühren, wechseln
(mindestens) zwei Signale.  kein Struktur-, sondern ein
funktionaler Hazard
27
Digitaltechnik
HS2015
5. Schaltungssynthese
ETH Zürich Institut für Elektronik (IfE)
Tröster
28
was sind programmierbare Bausteine ?
6. Programmierbare Bausteine
• integrierte Schaltungen, die aus einem oder mehreren Arrays
von z.T. verdrahteten Funktionsblöcken bestehen
Lernziele
• der Benutzer implementiert seine Anwendung durch
Konfigurierung der Hardware, z.B. durch Lösen oder den
Aufbau von Verbindungen
• wo braucht man programmierbare Bausteine
• wie sind programmierbare Bausteine aufgebaut, z.B. das
Bauteil Cyclone II aus dem Praktikum
• für den Entwurf und die Programmierung stehen
Softwaretools zur Verfügung
• was bedeutet PLD, PAL, PLA, FPGA
• wie werden sie programmiert
• je nach Aufbau und Anwendungsbereich gibt es eine Vielzahl
von verschiedenen Bauformen
Textbuch Reichardt
wie kann man Hardware programmieren ?
• Kap. 16 (teilweise)
• mit elektrisch programmierbaren Schaltern können
Verbindungen zwischen Gattern oder komplexeren
Funktionseinheiten geschlossen oder gelöst werden
Motivation
• logische Funktionen können auch in programmierbaren ROModer Flash-Strukturen abgelegt werden
• wie können wir Schaltnetze und Schaltwerke implementieren,
z.B.
Programmiertechniken:
Software
> Software auf einem PC
> durch Programmierung eine Mikroprozessors
> durch Konfigurieren eines programmierbaren Bausteins
> durch den Zusammenbau aus Grundgattern
> durch einen integrierten Schaltkreis
Hardware
1. SRAM (Static Random Access Memory)-Zelle
• in einer SRAM-Zelle (vereinfachtes SR-Latch [wird in Kap 9
besprochen]) oder Flash-Zelle kann eine 1-Bit-Information
abgelegt werden, die nachgeschaltete Module steuert
• programmierbare Bausteine (?)
• die Informationen können immer wieder überschrieben
werden
• attraktive Hardwareplattform für die Entwicklung und
Prototypfertigung mit starken Zuwächsen
• die abgespeicherten Informationen gehen bei Unterbruch der
Betriebsspannung verloren
 nicht bei Flash-Speicher
PLD: Programmable Logic Devices
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
1
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
2
3. 'Floating Gate'-Technik (Flash)
Anwendung von SRAM-Zellen
• Ladungen auf einem Zusatzgate (floating gate) schalten
einen MOS-Transistor permanent ein oder aus
• EPROM: löschbar durch UV-Licht
EEPROM (Flash): elektrisch löschbar durch Spannungsimpuls
• eine SRAM-Zelle kann einen MOS-Schalter (Transfer-,
Transmission-Gate) schalten
• zur Steuerung eines 4-zu-1 -Multiplexers genügen 2 SRAM-Zellen
2. 'Antifuse'-Technik
• durch einen Spannungsimpuls ( ca 10V) wird eine hochohmige
Verbindung niederohmig; z.B. an Leiterbahnkreuzungen
Querschnitt Floating-Gate (Speicher-)Transistor
• diese Programmiertechnik lässt sich sehr platzsparend
implementieren, sie ist aber nicht reversibel
Beispiel: Actel PLICE Technologie
Leitbahn
(wikimed)
Durchbruchsbereich
Dünnoxid
Dickoxid
Dickoxid
d iffund ierte
Leitbahn
Querschnitt
Silizium-Substrat
Leitbahn
A ufsicht
d iffund ierte
Leitbahn
Digitaltechnik
HS2015
Durchbruchsbereich
'anti-fuse'
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
3
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
4
PAL: Programmable Array Logic
a
b
1
d
• Abbildung der disjunktiven Normalform (Summe von
Produkttermen) auf eine vorgefertigte Hardware-Architektur
> PALs bestehen aus programmierbaren UND-Arrays und
festverdrahteten ODER-Verknüpfungen
(bei den PLAs: Programmable Logik Arrays ist auch die
ODER-Matrix programmierbar; PLAs sind weitgehend von
den PALs verdrängt worden)
a b c d
&
a.b.d
&
UND-Verknüpfung der
Variablen a, b, d mit
4-Eingangs-UND-
a
b
0
d
Basisstruktur eines PALs:
ODER-Matrix
a.b.d
Darstellung in einem PLA
mit festen Verbindungen
a b c d
1
a+b+d
1
a+b+d
Darstellung in einem PLA
ODER-Verknüpfung
mit festen Verbindungen
• schaltungstechnisch werden die UND-Verknüpfungen durch
'wired-AND'-Techniken realisiert
Ausgänge
______________________________________________
• Beispiel (für eine einfache Implementierung):
> die beiden Funktionen
y0 = x2 + x0 .x1
y1 = x0 .x1 + x0 . x2 + x0. x1 .x2
UND-Matrix
sind in einem PAL zu programmieren:
Eingänge
• zur übersichtlichen Darstellung wird eine vereinfachte
Verknüpfungsnotation benutzt
Beispiel:
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
5
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
6
ein modernes Tool:
Feldprogrammierbare Gate-Arrays FPGAs
Ergebnis:
• PALs sind für die Umsetzung komplexerer Schaltungsstrukturen wie Datenpfade mit Recheneinheiten oder
kompletten Mikrorechnerstrukturen zu unflexibel
• die Fortschritte der Halbleitertechnik erlauben die Integration
grossflächiger Strukturen
• FPGAs bestehen aus einem Array von (komplexen)
Logikblöcken und einzelnen Funktionsblöcken wie
Rechenschaltungen, Speicher und Prozessorkerne
• die Verbindung zwischen den Logikblöcken wie die
Konfiguration der Logikblöcke selber sind programmierbar
'amerikanische' PAL-Notation
PAL von der Firma Advanced Micro Devices (Ausschnitt)
DE1-Altera Development Boards
(vereinfachte) Architektur des FPGA-Bausteins Cyclone II der
Firma ALTERA aus dem Praktikum
UND-Matrix
ODER-Matrix
PLL: Phase-Locked Loop zur Generierung verschiedener Taktfrequenzen
IOEs: Input/Output Elements
• die Ausgänge sind mit Tristate-Gatter beschaltet
und in das Schaltnetz zurückgekoppelt
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
M4K: 4k Bit Speicher, verschieden konfigurierbar
LAB: Logic Array Blocks, bestehen aus jeweils 16 Logic Elements LE
7
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
8
Look-up Table (LUT)
LE: Logic Element (aus der Cyclone II -Serie)
• in einer Tabelle kann jede kombinatorische Verknüpfung
durch Abspeichern der Wahrheitstabelle abgelegt werden
Beispiel:
die Funktion
f = a.b + c
mit der Wahheitstabelle
> Funktionsmerkmale:
LUT: 8 x 1 Sp eicher
• über verschiedene Ketten ‚chains‘ können Daten zwischen
den LEs ausgetauscht werden
f
1
0
1
0
1
0
1
1
• die LockUp (LUT) Table besteht aus einem 16 Bit-Speicher
(SRAM), mit dem entweder eine beliebige Eingangsfunktion
von 4 Variablen realisiert werden kann (24 Bit x 1), oder zwei
beliebige Funktionen mit je 3 Eingangsvariablen (23 Bit x 2)
b
• Look-Up- Tabellen werden häufig eingesetzt, z.B.
> in der Bildverarbeitung: Multiplikation von Bildpunkten
(Pixel) zur Filterung oder Farbveränderungen
9
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
Interzellverbindungen (Cyclone II)
6. Programmierbare Bausteine
Tröster
10
(Cyclone II)
System- und Schaltungsentwurf auf programmierbaren
Bausteinen
• programmierbare Schaltermatrizen (auf der SRAM-Technik
basierend) stellen die Verbindungen zwischen den
Verdrahtungskanälen her
• wie kann man eine Schaltung auf ein PLD/FPGA
implementieren
• die LEs sind über programmierbare Anschlüsse in das
Verbindungsnetz eingehängt
• CAD (Computer Aided Design) Tools:
> Schaltungsentwurf (und Simulation) mit graphischen
Editoren oder schaltungsspezifischer Programmiersprache
(z.B. VHDL: Very High speed integrated circuits Hardware
Description Language)
spezielle Ein-und Ausgangszellen
• jeder Anschluss kann als Ein- oder Ausgang genutzt werden
• Eingangspegel (TTL, CMOS), Synchronisierung (durch D-FF),
Ausgangspegel (z.B. Tristate), Anstiegszeit (Slew Rate),
Ruhepotential (durch Pull-up Widerstand)
können für jede Zelle programmiert werden
ETH Zürich Institut für Elektronik (IfE)
f
• Laufzeit durch die LUT logikunabhängig
• Logikfunktion im Betrieb umprogrammierbar
Digitaltechnik
HS2015
1
0
1
0
1
0
1
1
• eine LUT mit k Eingängen und einem Ausgang benötigt 2k
Speicherzellen
• verschiedene Taktsignale, asynchroner Reset
6. Programmierbare Bausteine
Tröster
c
0
1
0
1
0
1
0
1
c
• in das D-Flipflop können die Ausgaben des kombinatorischen
Blocks oder von data3 gespeichert werden
ETH Zürich Institut für Elektronik (IfE)
b
0
0
1
1
0
0
1
1
a
• ein LE enthält neben einem D-Flipflop (wird in Kap 9
besprochen) einen kombinatorischen Block und mehrere
Multiplexer zur Signalverteilung
Digitaltechnik
HS2015
a
0
0
0
0
1
1
1
1
6. Programmierbare Bausteine
Tröster
> Übersetzungsprogramme (Compiler) generieren
Instruktionen und Daten für den jeweiligen Baustein
> eine Rücksimulation notwendig, um aus der aktuellen
Implementierung in dem PLD das logische und dynamische
Verhalten (Timing) zu extrahieren und mit den
Spezifikationen zu vergleichen
11
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
12
Rücksimulation, Backannotation
Vorgefertigte (embedded) Module (Xilinx)
• DSP Slice (bis 500MHz)
Ersatzschaltbild Leitungsverbindung
Komplexe Zellen: Xilinx Virtex-7 SLICEM (2014)
• Embedded PowerPC 405 core
> 450 MHz, MIPS RISC core (32-bit Harvard architecture)
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
13
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
14
Gegenüberstellung:
(einfaches) Beispiel: Ansteuerung Schrittmotor
wann nehme ich ein ASIC, wann ein FPGA,
wann einen Mikroprozessor ?
•Beispiel: Steuerung Garagenautomat-Automat
•Fallbeispiel: Kriterium Stückkosten
•ASIC - FPGA - μP
Entwicklungs-
Impulsdiagramm
ASIC
FPGA
μProzessor
Stückpreis CHF bei Stückzahl
kosten CHF
106
103
10
1'000'000
80'000
80'000
11
20
100
1'020
100
180
102'000
10'000
8'100
• hohe Initialkosten verlangen eine grosse Stückzahl bei
kleinen Fertigungskosten
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
15
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
6. Programmierbare Bausteine
Tröster
16
'was ist ein Zahlensystem ?'
7. Zahlen, Kodes (Codes)
Reichardt, Kap 5.1 ff
' wie kann man mit 0 und 1 rechnen ?'
• Grundlagen moderner Zahlensysteme:
> Stellenwertprinzip: die Position einer Ziffer innerhalb einer
Zahl gibt den Wert an, mit der die Basis des Zahlensystems
an dieser Stelle potenziert werden muss (polyadische
Zahlensysteme)
Lernziele
• virtuoser Umgang mit verschiedenen Zahlensystemen:
Dual-, Hexadezimal- (Oktal-) Zahlen, 2er-Komplement
• Arithmetik mit Dualzahlen
> es existiert eine Zahl 'Null'
• verschiedene Kodes z.B. BCD;
fehlererkennende & fehlerkorrigierende Kodes
> die Anzahl der verschiedenen Ziffernsymbole entspricht
der Basis des Zahlensystems
Textbuch Reichardt:
• Kapitel 5: wesentliche Teile in veränderter Reihenfolge

Festkommazahlen (fixed point numbers)
• Kapitel 8: teilweise
Fliesskommadarstellung (floating point numbers)
• Festkomma:
Dezimalzahl ohne Exponenten; der Dezimalpunkt bestimmt
den Zahlenwert mit, z.B.
Motivation
• das Dualzahlensystem bietet viele Möglichkeiten, Zahlen zu
repräsentieren (Kodes)
1(,0)
• für die Arbeitsweise von Rechenmaschinen, für
Steuerungsaufgaben, für die digitale Signalverarbeitung
und in der Kommunikationstechnik spielen
Zahlendarstellung und Kodierung eine wichtige Rolle, z.B.
für die Verschlüsselung vom Informationen
2,5
-0,03
• Fliesskomma:
Darstellung mit einem Exponenten; die Stellung des
Dezimalpunktes variiert mit dem Exponenten
Beispiel:
103,734.100 = 10,3734.101 = 1,03734.102
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
1
Tröster
Digitaltechnik
HS2015
> Hexadezimalsystem: R = 16
da 10 Ziffern für die 16 Stellen nicht ausreichen, sind 6
weitere Buchstaben A, B, C, D, E, F definiert
• Berechnung einer positive, (auch gebrochenen) Zahl D mit
der Basis („Radix“) R und den Koeffizienten (Ziffern) bi:

 bi . Ri
(*)
Dezimalzahl
i=-
die Zahl wird dargestellt in der Form
{....bi=+2 bi=+1 bi=0 ,bi=-1 bi=-2....},
und für eine m-stellige Dezimalzahl rm-1 rm-2 ri=0
0
D=
2
Tröster
Reichardt, Kap 5.1ff
Festkommazahlen
D=
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
 bj . Rj
j = m-1
2621(10)
> Dezimalsystem: R = 10
1908(10) = 0 . 10(i>3) + 1 .103 + 9 .102 + 0 .101+ 8 . 100 + 0
Hexadezimalzahl
0...9
10
11
12
13
14
15
= A . 162 + 3 . 161 + D. 160
0...9
A
B
C
D
E
F
= A3D(16)
(Darstellung im Textbuch: Zeichenfolge 0x vorangestellt, also
0xA3D(16))
3,625(10) = 3. 100 + 6. 10-1 + 2. 10-2+ 5. 10-3
• wozu das Hexadezimalsystem ?
> Oktalsystem: R = 8
1908(10) = 3 . 83 + 5 . 82 + 6 . 81+ 4 . 80 = 3564(8)
> 4 Dualstellen (Tetrade) repräsentieren eine Ziffer im
Hexadezimalsystem
3,625(10) = 3. 80 + 5. 8-1 = 3,5(8)
> lange Dualzahlen können übersichtlich und kompakt
durch Hexadezimalzahlen dargestellt werden
> Dualsystem: R = 2
243(10) = 1 . 27 + 1 . 26 + 1 . 25+ 1 . 24+ 0 . 23 + 0 . 22 + 1 . 21 + 1 .20
=
1111 0011(2)
> Dual-, Oktal- und Hexadezimalzahlen können
päckchenweise ineinander umgerechnet werden
Beispiel:
3,625(10) = 1 . 21+ 1 . 20 + 1 . 2-1 + 0 . 2-2 + 1 . 2-3
=
11,101(2)
E
6
0
5(16)
|
|
|
|
= 58'885(10)
|1110| 0110| 0000| 0101|
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
3
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
Umwandlung dezimal  binär, hexadezimal
'wie konvertiert man Zahlen in die
verschiedenen Zahlensysteme ?'
in das Dezimalsystem

a. ganze Zahlen
gegeben sei eine n-stellige Binärzahl mit
> wiederholtes (ganzzahlige) Dividieren mit der Zahlenbasis;
der jeweilige Rest entspricht der Ziffer im neuen
Zahlensystem, beginnend mit der letzten Ziffer
D(2)= bn-1bn-2 …b1b0
die entsprechende Dezimalzahl kann mit
n-1
D(10) =
bi  2i
> das Verfahren endet, wenn als Divisionsergebnis Null
erreicht wird
Beispiel:
150(10) als Dualzahl, also
Rest
150 ÷ 2
=
75
0
(LSB*)
75 ÷ 2
=
37
1
37 ÷ 2
=
18
1
18 ÷ 2
=
9
0
9 ÷2
=
4
1
4 ÷2
=
2
0
2 ÷2
=
1
0
1 ÷2
=
0
1
(MSB**)
also 150(10) = 10010110(2)
(*)
i=0
berechnet werden.

der rekursive Ansatz (‚Horner’-Schema) vermeidet die Berechnung der
Zweierpotenzen:
aus (*)
= 2
D(10)
 n-1

 (bi  2i-1 ) + b0
i = 1



n-1


i=2

= 2  2  
(bi  2i-2 ) + b1 + b0
= 2 (2 ... (2 (2bn-1+bn-2) ...) + b1)+ bo
*LSB: Least Significant Bit; **MSB: Most Significant Bit
= 2 ( 2  ( 2  ( 2  1 +1) + 1) + 0) + 1
Beispiel : 11101(2)
Reichardt, Kap 5.3
• die Umwandlung kann separat für den Teil vor dem Komma,
also für bi mit i  0 und für den 'Fraktionalteil' ('fractional
number') hinter dem Komma, also für bi mit i < 0 erfolgen
Beispiel:
3509(10) als Hexadezimalzahl, also
= 2 ( 2  ( 2  3 + 1) + 0) + 1
= 2 ( 2  7 + 0) + 1
= 29
Rest
5
B
0 D
3509 ÷ 16
=
219
219 ÷ 16
=
13
13
÷ 16
=
also 3509(10) = DB5(16)
Aufwand: n Multiplikationen mit 2 und n Additionen
(LSD*)
*LSD: Least Significant Digit
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
5
Tröster
Digitaltechnik
HS2015
b. Dezimalzahlen 1  x  0 in Dualzahlen
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
6
Tröster
Beispiel: Umwandlung des Fraktionalteils einer Dezimal- in
eine Hexadezimalzahl
Verfahren nicht imTextbuch
• wiederholtes Multiplizieren mit der Zahlenbasis 2;
0,171875(10) als Hexadezimalzahl, also
> ist das jeweilige Ergebnis kleiner 1, dann lautet die
Binärstelle K-i = 0 (beginnend mit K-1); die Prozedur wird
0,171875 . 16
. 16
0,75
mit dem Multiplikationsergebnis weitergeführt
> ist das Ergebnis grösser 1 der Form a, d-1d-2d-3..., mit a > 0,
dann ist der Koeffizient K-i = a zu setzen; das Verfahren
=
2,75
2
=
12
C
K-1
also 0,171875(10) = 0,2C(16)
wird mit dem um den Wert a verminderten
Multiplikationsergebnis weitergeführt
• zwischen Dual- und Hexadezimalzahlen kleiner 1 ebenfalls
päckchenweise Umrechnung
0, 2
C(16)
= 0,171875(10)
> das Verfahren endet, wenn
* eine Multiplikation exakt eine ganze Zahl > 0 liefert,
oder
* eine untere Genauigkeitsschranke erreicht ist,
oder
* die maximal zulässige Stellenzahl erreicht ist.
|
|
0, | 0 0 1 0 | 1 1 0 0 |
Beispiel:
nicht jede gebrochen rationale Dezimalzahl ist exakt mit endlicher
Stellenanzahl in einem anderen Zahlensystem darstellbar (!?)
0,171875(10) als Dualzahl, also
0,171875
. 2
=
0,34375
0
K-1 MSB
0,34375
0,6875
0,375
0,75
0,5
.
.
.
.
.
=
=
=
=
=
0,6875
1,375
0,75
1,5
1,0
0
1
0
1
1
LSB
2
2
2
2
2
also 0,171875(10) = 0,001011(2)
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
7
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
Fliesskommazahlen
'Grundrechenarten'
Reichardt, Kap . 5.6.2
x = Mi . BE
• allgemeine Form:
• Rechenregeln (1 = 1(2), 0 = 0(2))
1. Addition
Reichardt, Kap. 5.4
mit
M:
B:
E:
Mantisse
Basis (z.B. 2)
Exponent
0+0=
0+1=
1+0=
1+1=
1+ 1+1=
• Darstellung als Dualzahlen in Rechnersystemen
standardisiert
|
Übertrag, Carry
IEEE/ANSI Floating Point standard 754 - 1985
'einfach genau' (single precision) mit 32 Bit:
31 30
2. Subtraktion
22
Exponent
VZ
0
0-0=
1-0=
1-1=
0-1=
Mantisse
Vorzeichenbit (0  '+'; 1  '-')
VZ:
0
1
0
1 mit Ausleihen (borrowing) einer 1
von der höherwertigen Spalte
Exponent: zur Basis 2, 8 Bit, beginnend mit -127
Mantisse:
0
1
1
10
11
3. Multiplikation
23 Bit, normalisierte Darstellung der Form
1.xxx, wobei nur der gebrochene Teil xxx
abgespeichert wird
0.0= 0
1.0= 0
0.1= 0
1
1.1=
Beispiel:
+53,2265625(10) = +110101,001101(2) = +(1,)10101001101(2) 25
Mantisse:
Vorzeichen:
Exponent:
Digitaltechnik
HS2015
1010100110100000000000
0
10000100
(AND-Funktion !)
(23 Bit)
'+'
(+127 + 5)
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
9
Tröster
Digitaltechnik
HS2015
n-stellige Zweierkomplementzahl: bn-1 bn-2 bn-3 …b1 b0
Konvertierung: 2er-Komplement in Dezimalzahl:
n-2
D(10) = - bn-1 . 2n-1 +  bi . 2i
i=0
• n-stellige Dualzahlen mit Vorzeichenbit
1 Bit
(n-1) Bit
Beispiel: 3-Bit Zahl
• verschiedene Darstellungsformen ('Kodierungen') für
positive und negative Dualzahlen sind möglich: VorzeichenBetrag, Einer-Komplement, Zweier-Komplement
Dezimalzahl
+3
+2
+1
0
-1
-2
-3
-4
• in Rechenanlagen/μProzessoren/Signalprozessoren
meistens die Zweier-Komplement-Darstellung
Zweier (2er, two's, 2's) Komplement – Darstellung für
positive und negative Zahlen:
VZ
-(2n-1)  D  (2n-1 – 1)
Wertebereich:
Reichardt, Kap. 5.5
Betrag
10
Tröster
Ganze Zahlen
'gibt es eine negative Dualzahl ?'
VZ
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Zweierkomplement
0
0
0
0
1
1
1
1
11
10
01
00
11
10
01
00
Beispiel: 4-Bit-Darstellung (im Zahlenkreis)
Betrag
positiv
0
MSB, MSB-1, ...., LSB = |X(2)|
negativ
1
 |X(2)| bitweise invertieren
 zu dem Ergebnis eine '1(2)' addieren
(an der LSB-Stelle )
0100
0011
0010
+
4
0110
+5
+3
+6
+2
0111
0001
+1
+7
0101
1000
1001
-8
0
-7
-6
-1
-2
0000
1111
-5 -4 -3
1110
1010
1011 1100 1101
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
11
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
12
Eigenschaften 2er-Komplementzahlen:
Rationale Zahlen
n-stellige Zweierkomplementzahl: b0 b1 … bn-1
der Zahlenwert ist auch durch die vorgegebene Stellenzahl bestimmt !
-1D <1
Wertebereich:
Beispiel:
Konvertierung: 2er-Komplement in rationale Dezimalzahl:
n-1
D(10) = - b0 . 20 +  bi . 2-i
i=1
0100
0110
0111
1000
+ o.625
0010
+ 0.25
+ 0.75
+ 0.875
0001
- 1.0
+ 0.125
0
- 0.875
- 0.125
1001
1010
- 0.75
- 0.25
- 0.625 - 0.375
- 0.5
1011
1100
0000
1111
1110
1101
• Darstellung vorzeichenbehafteter Zahlen mit rationalem
Anteil häufig im Q-Format: mQn
• bei m Vorkomma- und n Nachkommabits sind insgesamt
k=1+m+n Binärstellen erforderlich
• Umwandlung der Dualzahl bm bm-1 … b0 b1 … bn in eine
Dezimalzahl D(10) mit
D(10) = - bm . 2m +
Digitaltechnik
HS2015
101100:
010011
010100: 2er Komplement
und wieder zurück:
Zweierkomplement zu
> Inversion
> 1 addieren
010100
101011
101100
5.4375(10) = 0101.0111(2)
n
7. Zahlen, Codes
Beispiel:
Zweierkomplement zu
> bitweise Inversion
> 1 addieren
- 5.4375(10)
 bitweise invertieren:
 bi . 2i +  bi . 2-i
i = m-1
i=1
ETH Zürich Institut für Elektronik (IfE)
+4
+5
Beispiel: gebrochene Dezimalzahl im 3Q4-Format
5.4375(10) und -5.4375(10) ist in eine 8-stellige Dualzahl
umzuwandeln, wobei je 4 Bit vor und nach dem Komma zur
Verfügung stehen
0.4375(10) = 0.0111(2) , also
5(10)  101(2)
Q-Format
0
0100 =
0101 =
das Zweierkomplement eines Zweierkomplements ergibt wieder die
ursprüngliche Zahl
0011
+ 0.5
+ 0.375
4-Bit
-4
-3
Weglassen führender Nullen nicht erlaubt !
Beispiel: 4-Bit-Darstellung (im Zahlenkreis)
0101
3-Bit
100 =
101 =
1010.1000
1
1010.1001
 eine '1(2)' addieren:
(an der LSB-Stelle )
13
Tröster
Rechenoperationen mit Dualzahlen
Digitaltechnik
HS2015
also
- 5.4375(10) = 1010.1001
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
14
Tröster
2. Subtraktion von Festkommazahlen
1. Addition von Festkommazahlen
Reichardt, Kap. 5.5.2
• Rechenregeln (1 = 1(2), 0 = 0(2))
• Rechenregeln (1 = 1(2), 0 = 0(2))
0+0=
0+1=
1+0=
1+1=
1+ 1+1=
0-0=
1-0=
1-1=
0-1=
0
1
1
10
11
|
• die Addition einer n-Bit breiten Zahl erfolgt bitweise,
beginnend mit den niederwertigen Stellen
• die Stellenwertigkeit ist zu beachten, eventuell sind Nullen
aufzufüllen
• die Wortbreite (d.h. die Anzahl der Binärstellen) des
Additionsergebnisses zweier B-Bit breiten Dualzahlen kann
(B+1) Bit betragen
Beispiel:
Beispiel:
+
1
1
1
1
1
1
1
1
0
0
0
1
mit Ausleihen (borrowing) einer 1 von
der höherwertigen Spalte
• die Subtraktion erfolgt bitweise, beginnend mit den
niederwertigen Stellen
Übertrag, Carry
0
1
0
1
0
1
1
1
1
- 0
1
1
0
1
0
1
1
1
1(2)
0(2)
51(10)
30(10)
ausgeliehen
0
1
0
1
0
1(2)
21(10)
Überträge
1 ,0
1 , 1
1 1(2),
0 0(2)
25, 375(10)
59, 5(10)
wenig gebräuchlich
=
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
15
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
16
Subtraktion mit dem 2er-Komplement
Multiplikation von Dualzahlen (Festkomma)
Reichardt, Kap. 10.9
• Rechenregeln (1 = 1(2), 0 = 0(2))
1. Subtraktion zweier Dualzahlen A - B darstellbar als die
Addition von positiven 2er-Komplement von A mit dem
negativen 2er-Komplement von B
2. Minuend (A) und Subtrahend (B) müssen über die gleiche
Stellenzahl verfügen
3. Falls die Stellenzahl nicht übereinstimmt, muss linksbündig
erweitert werden mit dem jeweiligen Vorzeichenbit (‚sign
extension’)
A
B
59
15
Dezimal
Betrag(2)
1 1 1 0 1 1
1 1 1 1
erweitert auf 8 Bit
0 0 1 1 1 0 1 1
0 0 0 0 1 1 1 1
1 1 0 0 0 1 0 1
1 1 1 1 0 0 0 1
2er-Komplement:
Fall a:
A-B
A:
-B:
(Übertrag)
Fall b:
1
0
• die Wortbreite (d.h. die Anzahl der Binärstellen) des
Multiplikationsergebnisses zweier B-Bit breiten Dualzahlen
kann 2.B Bit betragen (Vorzeichen siehe 9.20)
Beispiel:
21 . 17 = 357
1 0 1 0 1
.
1 0 0 0 1
__________________
1 1 1 1 0 0 0 1
1 0 1 0 1
______________
44(10)
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1 1 1 1
1 0 1 0 1
1 1 0 0 0 1 0 1
______________
(kein Übertrag)
1 . 1 =
0
(AND-Funktion !)
0 0 1 1 1 0 1 1
(1) 0 0 1 0 1 1 0 0
B-A
B:
-A:
0
• Multiplikation zweier (vorzeichenloser) Dualzahlen:
> bitweise Multiplikation: Partialprodukte
> Aufsummieren der verschobenen Partialprodukte
4. ein Übertrag an der Stelle n+1 bei n-stelliger Darstellung wird
für die weiteren Berechnungen nicht benötigt.
Beispiel:
0 . 0 =
1 . 0 =
0 . 1 =
1 1 0 1 0 1 0 0
__________________
- 44(10)
1 0 1 1 0 0 1 0 1
(A - B) ist 2er-Komplement zu (B - A)
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
17
Tröster
Digitaltechnik
HS2015
• Schiebeoperationen (shift) nach links entspricht einer
Multiplikation mit der Zahlenbasis, nach rechts einer
Division mit der Zahlenbasis
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
18
Tröster
Arithmetische Operationen mit
Fliesskommazahlen
Beispiel:
Dezimalzahl:
21 um eine Stelle nach rechts: 2,1 = 21 ÷ 10
21 um eine Stelle nach links: 210 = 21 . 10
• Addition
1. die Exponenten müssen angeglichen werden durch
Schiebeoperationen
Dualzahlen:
1 0 1 0 1 (21) um eine Stelle nach rechts: 1 0 1 0,1 (10,5)
1 0 1 0 1 (21) um eine Stelle nach links: 1 0 1 0 1 0 (42)
2. die Mantissen werden addiert
3. eventuell Normalisierung der Mantissen
• Hardware-Multiplizierer häufig aus Shift-Add-Operationen
aufgebaut (z.B. Booth-Multiplizierer)
• Subtraktion
Multiplikation von 2er-Komplementzahlen
1. die Exponenten werden auf den grössten der beiden
Operanden angeglichen
• aufwendiger als die Multiplikation von Betragszahlen, da die
Betragsbildung einer negativen Zahl die
Komplementbildung verlangt
2. Subtraktion der Mantissen über das 2er-Komplement
• 2er-Komplement-Multiplizierer verwenden daher eine
modifizierte 2er-Komplement-Addition, oder negative
Zahlen in 2er-Komplementdarstellung werden in ihr
vorzeichenloses Komplement umgewandelt. Das Vorzeichen
des Ergebnisses wird separat ermittelt: gleiches Vorzeichen
von Multiplikand/Multiplikator: Ergebnis positiv, sonst
negativ
• Multiplikation
1. Multiplikation der Mantissen
2. Addition der Exponenten
• Division
• Booth-Multiplizierer (7.19) können 2er-Komplementzahlen
ohne Modifikation behandeln
1. Division der Mantissen
2. Subtraktion der Exponenten
Division von Festkommazahlen
• darstellbar als eine Abfolge von Schiebeoperationen (nach
rechts) und Subtraktionen
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
19
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
20
'was ist ein Kode ?'
Beispiel: Fliesskomma-Addition
Reichardt, Kap. 8 teilweise
• (binäre) Kodes:
Abbildung von Informationen (Zahlen, Ziffern,..) auf das
Binärystem nach einem vorgegebenen Konstruktionsprinzip
• Beispiel:
Dezimalzahl durch Dualzahlen

x(10) =
 bi . Ri
i=-
Lernziel
• kennenlernen der wichtigen Grundbegriffe und einiger
(einfacher) Kodes
Motivation
• Kodierung bestimmt die Leistungsfähigkeit eines Systems
> Computertechnik: Speichern von Informationen
> Audio- und Videotechnik: Störunempfindlicheit (CD-, DVDSpieler,...)
> Nachrichtenübertragung: Fehlerkorrektur (Handy,
Satellitenkommunikation), Verschlüsselung
aus
J. Hennessy, D. Patterson, “Computer Architecture and Design”, Morgan Kaufmann, 1997
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
21
Tröster
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
22
Tröster
Tetraden-Kodes
Beispiel:
• Tetrade: Einheit von vier Binärstellen
2 5 , 3 7 5 (10)
• Tetraden-Kodes: der Kode ist aus Tetraden aufgebaut
• direkte binäre Darstellung von Ziffern in Dezimalzahlen
2 5 , 3 7 5 (10)
• viele Abbildungen möglich
• Auswahl-, Konstruktionsprinzipien:
> einfache Darstellung
> einfache Rechenoperationen
0010 0101 , 0011 0111 0101
BCD-Kode (Binary Coded Decimals)
• von den 24 = 16 Kodewörtern werden nur 10 für die
Dezimalziffern benötigt: 6 Pseudotetraden
• Konstruktionsprinzip:
jede Dezimalziffer wird durch eine Tetrade kodiert
• die 'Kodeeffizienz' ist im BCD-Kode meist schlechter
• Vergleich:
25,375(10) = 11001 , 011(2) als Dualzahl benötigt 8 Dualstellen
im Gegensatz zu 20 Dualstellen mit BCD-Kodierung
arithmetische Operationen
• Addition
> Stelle für Stelle
> besondere Massnahmen notwendig, wenn die Addition
zweier Summanden grösser 8
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
23
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
24
'wie können wir die 16 Tetraden noch auf die
10 Dezimalziffer verteilen ?'
BCD
• häufig eingesetzt, Gewichtung der Binärstellen: 8-4-2-1
häufig benutzte Kodes:
Excess-3 und Aiken
Binär
Digitaltechnik
HS2015
0000
0
0
0
0
0001
1
1
1
1
0010
2
2
2
3
0011
3
0
3
3
0100
4
1
4
0101
5
2
0110
6
3
0111
7
4
1000
8
5
1001
9
6
• die Ziffern 0 - 9 liegen symmetrisch im Binärfeld; günstig für
dezimale Rechenwerke
4-2-2-1:
• Gewichtung 4-2-2-1, für A/D-Wandler interessant
0
2
Reichardt, Kap. 8.4
7
4
6
3
4
4
1
5
5
2
Gray und O'Brien:
• einschrittige Kodes:
Änderung zur nächstgelegenen Tetrade nur in einem Bit;
keine Fehlinformation bei Übergängen (Winkelkodierung)
• die BCD-, Aiken-, 4-2-2-1, Excess-3 -Kodes sind mehrschrittig
1010
7
9
1011
8
5
1100
9
6
6
8
5
1101
7
7
9
6
1110
8
8
8
1111
9
9
7
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
25
Tröster
ASCII-Kode
Digitaltechnik
HS2015
aus
M.Mano, „Digital Design“,
Prentice Hall2002
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
26
Tröster
'wie sind Fehler zu erkennen und zu
korrigieren ?'
Reichardt, Kap. 8.5
• Voraussetzung: redundante Kodierung
• Fehler werden erkannt, wenn eine nichtzulässige
Kodekombination erscheint
'Parity Bit'
• Annahme: nur maximal ein Bitfehler kann auftreten
(Fehlermodell)
• ein vorgegebener Kode wird durch ein Bit PE ergänzt, dass
die Anzahl der '1' immer geradzahlig - oder Null - ('even
parity'), oder mit dem ‚odd parity bit’ PO immer
ungeradzahlig ('odd parity') wird
• es gilt: PO = ¬ PE = Po
BCD-Kode mit 'even parity' PE
PE
• Alphanumerischer Kode: Ziffern, Buchstaben, Steuerzeichen
• 7-Bit Kode für 128 Zeichen; Erweiterung zu 8-Bit-Wort(= Byte)
• achte Bit entweder für vergrösserten Zeichensatz (256
Zeichen, z.B. ä, ö ) oder zur Fehlererkennung
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
• Fehlererkennung durch 'Abzählen'
27
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
28
Fehlerkorrektur
=1
A in
Xou t
• mehr Redundanz als zur Fehlererkennung notwendig
‚Parity Checker’
Q1
• Korrektur durch Bitinversion, wenn das fehlerhafte Bit
lokalisiert ist (Binärsystem !)
D
T
C1
Blockkorrektur
'Geradzahligkeitsprüfung'
in der Übung
• hier Voraussetzung: Einzelfehler (Fehlermodell)
• erweiterbar aus die Korrektur von mehreren Fehlern (z.B. bei
CD-Codierung)
• die Korrektur erfolgt über mehrere Datenwörter
• neben den Parity Bits wird ein zusätzliches Prüfwort
übertragen, das die Parity-Ergänzung über die Spalten
enthält
Beispiel:
Q
Q-aus-n Kodes,  n  - Kodes: Erweiterung auf Mehrbitfehler
• Definition:
von den N = 2n möglichen Zuständen werden nur die mit Q
Bits = 1 benutzt
• Beispiele:
Zwei-aus-Fünf-Kodes, Drei-aus-Fünf-Kodes, Zwei-ausSieben-Kodes
0
1
1
0
1
1
0
0
0
0
0
1
1
1
1
0
0
1
1
1
Parity Bits
0
0
0
1
1
Prüfwort
Fehler
• Fehlererkennung:
wenn in einem Kodewort die Anzahl der 'Eins-Bits' ungleich
Q ist
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
29
Tröster
Codierung im Handy (2G)
Digitaltechnik
HS2015

7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Frequenzen:
30
Tröster
MSBS: 890-915 MHz (=25MHz)
BSMS: 935-960 MHz (=25MHz)
Übertragungskanal:


125 Frequenzkanäle zu je 200 kHz: FDMA (Frequency Division
Multiple Access)
jeder Frequenzkanal in 8 Zeitschlitze (Kanäle) zu je 576,9μs
aufgeteilt; d.h. jedem Benutzer steht ein Achtel der Kapazität
eines Frequenzbandes zur Verfügung: TDMA (Time Division
Multiple Access)
Fehlerkorrektur


Datenstruktur (*)



in jedem Zeitschlitz werden 148 Bits übertragen, davon sind
26 Trainingsbits zum Adaptieren des Empfängers auf die
jeweiligen Empfangsbedingungen
Störungen im Funkkanal (Rauschen, Schwund,
Dopplereffekt,..) verhindern eine akzeptable
Übertragungsqualität
Kanalcodierung: zu den Nutzdaten von 260Bit je 20ms
Sprache werden 206 Bit an Korrekturdaten angehängt, um
die Verzerrungen auf dem Übertragungsweg zu korrigieren
Die 456 Bits werden auf 8 Portionen (‚Bursts‘) a‘ 57 Bits
aufgeteilt und verschachtelt (‚interleaved‘) übertragen; damit
wirken sich kurzzeitige Störungen geringfügiger aus
Interleaving(*)
(*)wikipedia: Global_System_for_Mobile_Communications
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
31
Digitaltechnik
HS2015
7. Zahlen, Codes
ETH Zürich Institut für Elektronik (IfE)
Tröster
32
was sind Rechenschaltungen ?
8. Rechenschaltungen,
Datenpfadkomponenten
• Digitalschaltungen
- kombinatorische
- sequenzielle,
Lernziele
oder
> die arithmetische Grundoperationen,
wie Additionen, Multiplikationen,
• was sind Rechenschaltungen ?
• wie sind sie aufgebaut (Festkomma) ?
oder
> komplexere Operationen,
wie Fliesskommaoperationen auf komplexen Zahlen,
Fouriertransformation, digitale Filter
• wo werden sie benötigt ?
• welche Hälfte addiert ein Halbaddierer ?
ausführen
• Ripple-Carry, Look-Ahead ??
Rechenschaltungen sind code-spezifisch
Textbuch Reichardt
Dateneingang
• Kap 10
Datenausgang
Datenpfad
(Operationswerk)
Halbaddierer
Reichardt Kap 10.8
Statussignale
Motivation
Steuerpfad
(Steuerwerk)
• Funktion: Addition zweier Dualziffern gemäss den
Rechenregeln für Dualzahlen
Steuersignale
• Rechenschaltungen
werden als Basismodule in vielen Systemen benötigt,
A B
0+0=
0+1=
1+0=
1+1=
1 + 1 +1=
> in einem Mikroprozessor, um die Speicheradressen zu
berechnen
> in Computersystemen, um komplexe Rechenoperationen
schnell ausführen zu können
Übertrag
Carry
• Datenpfadkomponenten
> für die Manipulation von Datenströmen werden (De-)
Multiplexer, (De-)Codierer und Komparatoren eingesetzt
8. Rechenschaltungen
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
Z
Summe
• kombinatorische Schaltung
1
Tröster
Digitaltechnik
HS2015
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
2
Tröster
Schaltzeichen eines Volladdierers:
Wertetabelle:
A
B
0
0
1
1
0
1
0
1
C
S
A
Z, Su m m e

B
Ci
C = .....................................
=1
Z, Su m m e
A
B
&
Z, Su m m e

CO
B
Ü, Carry
CO
CI
Ü, Carry, C o
• Wertetabelle:
S = .........................................................................
A
00
01
01
10
11
Ü, Carry
A
B
Ci
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
Z
Co
Volladdierer
A
• bei der Addition von zwei Dualzahlen müssen wegen des
Übertrags drei Dualziffern addiert werden
A
B
Z
Beispiel:
+
1
0
1
1
0
1
1
1
B

Digitaltechnik
HS2015
C
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
3
Digitaltechnik
HS2015
C
C
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
A
Mehrbit - Addierer
A
• für die Addition mehrstelliger (Dual-) Zahlen
B
• die Addition mehrstelliger Dualzahlen kann bitseriell oder
bitparallel erfolgen
Co
B
• Serienaddierer:
in einem Taktschritt nur die Addition einer Stelle
C
C
• Paralleladdierer:
während eines Taktschritts die Addition aller Stellen
C
Z = ..................................................................................... = ...................
Co = .....................................................................................
Paralleladdierer
• drei wesentliche Implementierungsstrategien möglich:
> Paralleladdierer in Normalform
> Ripple-Carry-Adder
> Carry-Look-Ahead- Adder
Schaltung aus Halbaddierer
Normalform
A
B
A+B
S
HalbAddierer A B
CO *
A + B + CI
S
HalbAddierer CI (A +
CO
• aus der Wahrheitstabelle kann die Normalform (z.B.
disjunktiv) gewonnen und in eine kombinatorische
Schaltung umgesetzt werden
S
Beispiel: Addition von zwei 2-stelligen Summanden A, B
CI
1
Digitaltechnik
HS2015
CO
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
5
Tröster
Digitaltechnik
HS2015
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
6
Tröster
Ripple-Carry Addierer
Reichardt, Kap 10.8.2
4-Bit-Parallel-Addierschaltung
• Aufwand:
bei der Addition zweier N-stelliger Summanden müssen für
die (N+1)-Summenausgänge (ohne Logikminimierung)
N.2(2n-1) Min- oder Maxterme verknüpft werden
• für jede Stelle (ausser für die niederwertigste) wird ein
Volladdierer benötigt
• Additionsdauer:
die Normalform ist immer in ein dreistufiges Schaltnetz
umsetzbar: NICHT, UND, ODER;
die Laufzeit beträgt daher unabhängig von der
Stellenanzahl der Summanden minimal 3 Gatterlaufzeiten
(tp)
• der Ripple-Carry Addierer ist durch Kaskadierung einfach
erweiterbar (skalierbar), z.B. aus zwei 4-Bit-Addierer kann ein
8-Bit Addierer aufgebaut werden
• der Schaltungsaufwand wächst linear mit der Stellenanzahl
• Laufzeit:
Summe und Übertrag für die i-te Stelle können erst gebildet
werden, wenn die Summe und der Übertrag der (i-1)-ten
Stelle vorliegen:
der Übertrag 'rippelt', rieselt durch alle Stufen des
Schaltnetzes
schneller, aber schaltungsaufwendiger Addierer
• die Addierzeit wächst linear mit der Stellenzahl
Digitaltechnik
HS2015
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
7
Digitaltechnik
HS2015
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
Carry-Look-Ahead (Fast Carry-) Addierer
Beispiel:
Reichardt, Kap 10.8.3
• Paralleladdierer mit Übertragsvorausberechnung
• Kompromiss aus Ripple-Carry und Normalformaddierer
• Funktionsweise:
die Berechnung der Überträge erfolgt parallel zu der
Summenbildung in einem kombinatorischen Netzwerk in
einem Schritt
Beispiel:
2-Bit-Addierer mit Carry-Look-Ahead
• das Schaltnetz ist zweistufig, die Berechnung der Überträge
erfordert minimal zwei Gatterlaufzeiten
Subtrahierer
• die Subtraktion kann
1. durch Abbildung der Subtraktionsregeln für Dualzahlen
oder
• der Aufwand für die Berechnung der Überträge wächst mit
der Stellenanzahl
Digitaltechnik
HS2015
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
2. durch 2er-Komplementbildung und Addition erfolgen
9
Tröster
Digitaltechnik
HS2015
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
10
Tröster
Multiplizierer
Rechenwerk für die Addition/Subtraktion
Reichardt, Kap 10.9
• Rechenregeln (1 = 1(2), 0 = 0(2))
umschaltbarer Addierer/Subtrahierer
0.0=
1.0=
0.1=
1.1=
0
0
0
1
AND-Funktion
• Multiplikation zweier (vorzeichenloser, ‚unsigned’)
Dualzahlen:
> bitweise Multiplikation: Partialprodukte
> Aufsummieren der verschobenen Partialprodukte
• negative Zahlen in 2er-Komplementdarstellung (siehe Kap.
7) sind in ihre vorzeichenloses Komplement umzuwandeln
• die Wortbreite (d.h. die Anzahl der Binärstellen) des
Multiplikationsergebnisses zweier B-Bit breiten Dualzahlen
kann 2.B Bit betragen
Beispiel:
9 . 11 = 99
a3a2a1a0
1001
__________________
1001
1001
0000
Shift & Add
1001
__________________
• für S = 0 sind die EXOR-Gatter transparent und das
Schaltnetz arbeitet als Addierer
• für S = 1 wird der Inhalt des B-Registers bitweise negiert; C0
= 1 bewirkt die Addition einer '1', die notwendig ist für die
2er-Komplementbildung
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
b0 a 20
b1 a 21
b2 a 22
b3 a 23
Partialprodukte
p7p6p5p4p3p2p1p0
• mehrere integrationsgerechte Architekturen bekannt, z.B.
• für den Addierer können Ripple-Carry oder Carry-LookAhead-Typen benutzt werden
Digitaltechnik
HS2015
b3b2b1b0
. 1011
11
Digitaltechnik
HS2015
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
12
ein 4x 4-Bit Array-Multiplizierer mit Ripple-Carry-Addierer
Multiplikation mit einem konstanten
Koeffizienten (Hybrid-Technik)
• um den Speicherbedarf für die LUT zu reduzieren, wird die
Multiplikation in mehrere Teile zerlegt und über einen
Addierer zusammengesetzt
Beispiel: 8 x 8 Bit (Xilinx)
> Aufspaltung in 2 x 4 Bit (entspricht einer Hex-Zahl)
> die LUT enthält die Multiplikationsergebnisse von 0.k bis
15.k
0 x k=0
1 x k=1K
.
15 x k=15k
Festwertmultiplikation mit Look-up Table (LUT)
Y = k X
• Funktion:Multiplikant adressiert einen Speicher, in dem
das Ergebnis der Multiplikationen für jeden möglichen
Eingangswert abgelegt ist
x
n
n
2 x B Bits
B
0
K
.
15k
8 x 8 Bit Hybrid-Multiplizierer
y
RAM/ROM
• Beispiel: geradzahlige Multiplikation mit 1012
Adresse x
Speicherwert y
001
010
..
101
Digitaltechnik
HS2015
101
1010
..
11001
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
13
Tröster
Digitaltechnik
HS2015
• Funktionsweise:
die Multiplikation wird seriell ('Bit für Bit') abgearbeitet; der
erforderliche Hardware-Aufwand ist gering
• Ablauf für A . B = P mit A ={ an-1 …a2 a1 a0 }
1. Anfangswert: P = 0, a-1=0
2. beginnend mit dem LSB (i = 0, 1, 2 ..)werden jeweils 2
benachbarte Bits überprüft und das Zwischenprodukt P
neu berechnet,
0
1
0
1
ai
ai-1
Operation
Ergebnis
0
1
2
3
1
1
0
1
0
1
1
0
P = (P-B)/2
P = P/2
P = (P+B)/2
P = P-B
1.1010
1.11010
0.010010
1.100010
Modifizierter Booth-Algorithmus
• Überprüfung von 3 benachbarten Bits
Addition/Subtraktion von B oder 2.B
Schiebeoperation um 2 Bits
4. Vorzeichenverdoppelung bei der Division
0
0
1
1
i
15
also: P = 1.100010(2) = - 32
3. ohne Division im letzten Schritt
ai-1
14
Tröster
5
3
• Beispiel: A = - 8 = 1.011(2), B = 4 = 0.110(2), (2er-Komplement)
Booth-Multiplizierer
ai
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
• i = 0, 2, 4 …
Operation
• im letzten Schritt Division durch 2
P = P/2
P = (P+B)/2
P = (P-B)/2
P = P/2
• nur n/2-Zyklen notwendig bei kaum erhöhtem
Hardwareaufwand
• geringer Hardwareaufwand erforderlich:
- Schieberegister
- Addierer (Subtraktion durch 2er-Komplementbildung)
- 'Division durch 2' mit Schiebeoperation um 1 Bit nach
rechts
•geeignet für die Multiplikation von negativen Zahlen
(Zweierkomplement)
ai+1
ai
ai-1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
Operation
P = P/4
P = (P+B)/4
P = (P+B)/4
P = (P+2.B)/4
P = (P-2.B)/4
P = (P-B)/4
P = (P-B)/4
P = P/4
• für die Multiplikation von n-Bit-breiten Zahlen sind n Zyklen
notwendig
Digitaltechnik
HS2015
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
15
Digitaltechnik
HS2015
8. Rechenschaltungen
ETH Zürich Institut für Elektronik (IfE)
Tröster
16
Kombinatorische  sequenzielle
Schaltungen ?
9. Sequenzielle Schaltungen:
Latches, Flipflops, zeitabhängige
Gatter
• bei kombinatorischen Schaltungen hängen die
Ausgangswerte nur von dem Verknüpfungsnetzwerk und
von den Eingangsgrössen ab; eine gegebene
Eingangsbelegung Xi erzeugt stets dieselbe Ausgangswerte
Yj , unabhängig von der Vorgeschichte
Lernziele
• was charakterisiert kombinatorische Schaltungen, was
sequenzielle Schaltungen
Yj = ƒ(Xi)
• wie lassen sich rückgekoppelte Schaltungen analysieren
Verknüpfungsnetzwerk
Xi
• was ist ein Latch, ein Flipflop
Yj
• wie funktionieren häufig gebrauchte Latches und Flipflops
Textbuch Reichardt
• Kapitel 11
• sequenzielle Schaltungen besitzen Rückkopplungen
(feedback loops), die Ausgangswerte hängen auch von
vorangegangenen Werten ab, z.B.
> Ergänzungen in der Übung
Motivation
Yj = ƒ(Xi, Yj)
• neben Schaltnetzen benötigen wir Schaltungen, die
Informationen speichern können
• bistabile Kippschaltungen sind Basiselemente der Elektronik
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
Verknüpfungsnetzwerk
Xi
1
Digitaltechnik
HS2015
Basis-Latch
ETH Zürich Institut für Elektronik (IfE)
Yj
9. Sequenzielle Schaltungen
Tröster
2
KV-Diagramm von 2 NOR-Gatter (?!)
Reichardt, Kap. 11.2
• aus zwei NOR-Gatter kann durch eine Rückkopplung ein
Speicherelement aufgebaut werden, das SR-Latch
S
1
• es gelten die Gleichungen:
Q1
1
S
S
Q1 Q
R
R
Q2 NQ
Q2
R
Q1 = Q2
Q2 = S  q1
=
S  q1
Q1 = R  q2
=
R  q2
• die Wertetabellen für Q1 und Q2 werden in ein 'doppeltes' KVDiagramm für Minterme eingetragen
Schaltzeichen
Schaltzeichen
im Textbuch Bezeichnung Q und NQ
SR
• wie analysiert man eine Schaltung mit Rückkopplungen ?
1. die Rückkopplungen werden aufgetrennt und das
Verhalten der 'offenen Schleife'/'Vorwärtspfad (open loop)
berechnet
q q
1
2
00
00
01
11
11
01
00
2. die Rückkopplungen werden miteinbezogen
01
1. SR-Latch ohne Rückkopplungen
1
S
q1
q2
1
R
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
01
01
Q1
9. Sequenzielle Schaltungen
Tröster
11
00
10
10
5
Digitaltechnik
HS2015
Q 1Q
00
00
00
00
00
00
10
2
3
2
3
10
00
4
Q2
10
ETH Zürich Institut für Elektronik (IfE)
1
9. Sequenzielle Schaltungen
Tröster
4
2. mit Rückkopplung
'wie beschreibt man die Zustandsfolge'
• die beiden Rückkopplungen verlangen
Q1 = q 1
• das Verhalten des Latches hängt nicht nur von den aktuellen
Eingangszuständen ab, sondern auch von dem internen
(Speicher-) Zustand
Q2 = q 2
und
• fünf Zustände im KV-Diagramm erfüllen diese Bedingung:
Fall
S
R
Q1
Q2
1
1
0
1
0
2
0
0
1
0
3
0
1
0
1
4
0
0
0
1
5
1
1
0
0
• Definitionen:
t
Zeitpunkt vor einem Zustands- oder Taktwechsel: tn
Zeitpunkt nach einem Wechsel:
tn+1 t+
Q1 Q2 = 1 0 unverändert
• also Q1n bezeichnet den Wert des Ausgangs Q1 vor einem
betrachteten Wechsel, und Q1(n+1) den Wert nach dem
Wechsel
Q1 Q2 = 0 1 unverändert
• im Textbuch Bezeichnungen Q und Q+
• Analyse der einzelnen Zustände und Zustandsübergänge:
• Zustandsfolge- (Folgezustands-) tabelle des SR-Latches
> wenn für R=0 die Eingangsvariable S den Wert 1 annimmt,
erzwingt sie den Wert 1 am Ausgang Q1: Setzzustand
dieser Ausgangszustand bleibt erhalten (gespeichert),
auch wenn wieder S = 0 zurückspringt
> durch R  1 für S=0 geht Q1  0: Rücksetzzustand;
die Rückkehr am R-Eingang nach 0 bewirkt ebenfalls keine
Zustandsänderung
> der Eingangszustand R = S = 1 ist nicht zulässig, da
Fall
S
R
Q1(n+1)
Q2(n+1)
1
0
0
Q1n
Q2n
speichern
2
0
1
0
1
rücksetzen
3
1
0
1
0
setzen
4
1
1
-
-
unzulässig
# immer Q2 = Q1 gelten muss,
# bei dem Übergang zu R = S = 0 die Ausgangszustände
nicht vorhersehbar sind
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
5
S
R
Q1n
Q1(n+1)
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
0
1
1
x
x
2
3
4
5
6
7
8
S
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
6
(Takt-) Zustandsgesteuertes (SRT-)Latch
• für ein KV-Diagramm muss eine komplette Werte- (Arbeits-)
tabelle für die Ausgangsvariable Q1(n+1) aufgestellt werden
Fall
Digitaltechnik
HS2015
Reichardt, Kap 11.2.2
• bei dem Basis-SR-Latch wird der Eingangszustand sofort
wirksam
speichern
• oftmals wünschenswert, Änderungen nur in einem
definierten Zeitfenster zuzulassen, beispielsweise in
Abhängigkeit von einem Taktsignal T, C, CLK(z.B. zur
Synchronisierung)
rücksetzen
setzen
unzulässig
Lösungsmöglichkeit:
S
UND-Verknüpfung der SR-Eingänge mit einem Taktsignal T
Q1n
Q1n
S
R
R
R
&
SI
T
&
R
Q1(n+1) = [S  R  Q1)]n
S
Q1
R
Q2
RI
(Q+ = S  R  Q)
• nur mit T = 1 gelangen Zustandsänderungen von S und R an
das Basis-SR-Latch (FF); mit T = 0 bleibt der gespeicherte
Zustand unverändert, da SI = RI = 0.
unter der Bedingung
R  S = 0, also R = S = 1 ist unzulässig
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
7
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
8
Schaltzeichen
S
T
R
&
D(elay)-Latch
Q1
S
T
&
Q2
R
Reichardt, Kap 11.3
Q1
• Erweiterung des taktzustandsgesteuerten SR-Latch: der
Rücksetzeingang R ist nicht nach aussen geführt, sondern
wird aus dem Setzeingang durch Invertierung gewonnen
Q2
SI
D
1
T
T
RI
T
Zeitablauf- oder Impulsdiagramm
T
t
S
D
Q2
R
D
D
T
T
Q1
Q2
Q1n Q1(n+1)
0
X
0
0
0
X
1
1
1
0
X
0
1
1
X
1
DNF (für beide Taktphasen):
Q1(n+1) = (Dn T Q1n  T )
Funktion
t
> durch den Inverter wird der unzulässige Eingangszustand
RI = SI = 1 vermieden
R
> im aktiven Taktzustand T = 1 ist das D-Latch transparent,
also Q1 = D
t
> beim Übergang von T = 1 nach T = 0 'schnappt' der Eingang
'zu' (latched), der 'letzte' Eingangswert wird übernommen
Q1
> für T = 0 gilt RI= SI = 0, der eingenommene
Ausgangszustand wird verriegelt; er bleibt erhalten, bis
T=1, also
t
Q2
t
Digitaltechnik
HS2015
Q1
S
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
9
Q1(n+1) = Dn
Digitaltechnik
HS2015
was ist der Unterschied zwischen
Latch und Flipflop ?
für T = 1
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
10
Taktflankengesteuerte Flipflop
• Latches sind transparent während der ganzen aktiven
Taktphase; Änderungen an den Eingängen können während
der aktiven Taktphase die Ausgänge beeinflussen
Zusammenfassung: Taktzustandssteuerung
• taktzustandsgesteuerte Schaltungen ‚Latches‘ sind
empfindlich gegenüber Störimpulsen, da für T = 1 jede
Änderung an den Eingängen in das Latch übernommen
werden kann; das Latch ist transparent für T = 1
• Flipflop: taktflankengesteuerte Kippschaltungen;
der Eingangszustand zum Zeitpunkt des Taktwechsels
(Flanke) wird wirksam, nicht während der Taktphase
Zeitdiagramm an einem Latch und einem vorderflankengesteuerten
Flipflop
Abhilfe: Taktflankensteuerung
• die Zustandsänderungen am Eingang werden nur in einem
schmalen Zeitfenster wirksam, nämlich wenn das
Taktsignal wechselt: Taktflankensteuerung, Flipflop
• während den Taktzuständen T = 1 oder T = 0 werden die
Daten am Eingang nicht übernommen, sondern nur bei
einem Taktflankenwechsel
Schaltzeichen für die Taktflankensteuerung
T, C
Eingangsvariable werden beim
0 - 1 Übergang von C wirksam
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
11
Digitaltechnik
HS2015
T, C
Eingangsvariable werden beim
1 - 0 Übergang von C wirksam
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
12
wie verhält sich ein rückgekoppeltes D-Latch ?
SR-Flipflop (taktflankengesteuert)
S
S
Q1
T, C
R
R
Q2
T
> mit der steigenden Flanke des Taktsignals T, C


1D
Q1
C1
Q2
C
werden der aktuell anliegenden Eingangswerte S und R
übernommen,
der Ausgang bestimmt sich zu
t
Q2
Q1(n+1) = [S  R  Q1)]n unter der Bedingung R  S = 0

t
danach ist der Eingang verriegelt und der Ausgang
bleibt unverändert bis zur nächsten steigenden
Taktflanke
wie verhält sich ein rückgekoppeltes D-Flip-Flop ?
D-Flipflop (taktflankengesteuert)
D
T
C1
Q2
Q1
1D
T
Q1
1D
C
Q2
C1
t
> mit der steigenden Flanke des Taktsignals T,C


Q2
wird der aktuell anliegende Eingangswert D
übernommen,
t
und an den Ausgang weitergereicht,
Q1(n+1) = Dn

Digitaltechnik
HS2015
danach ist der Eingang verriegelt und der Ausgang
bleibt unverändert bis zur nächsten steigenden
Taktflanke
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
T
13
Digitaltechnik
HS2015
C1
X
D
C1
Q1
Clk
1D
C1
Q2
9. Sequenzielle Schaltungen
Tröster
14
Q1
• Idee: die Setz- und Rücksetzeingänge an einem SR-FF werden
mit dem Takt in Abhängigkeit von den vorhergehenden
Ausgangswerten umgeschaltet
Q2
SR-Flipflop mit Rückkopplungen
D-Latch 2
1D Q
Q2
• wie könnte eine Schaltung aussehen, die bei jeder
Taktflanke in den anderen Zustand kippt ('toggelt'), z.B. für
einen Taster
• Reihenschaltung zweier D-Latches, mit gegenphasigem
Takt angesteuert
1D Q
C1
T(oggle)-Flipflop
Reichardt, Kap 11.4
D
Q1
1D
ETH Zürich Institut für Elektronik (IfE)
Aufbauvarianten D-Flipflop (Master-Slave)
D-Latch 1
?
D-FF mit Rückkopplung
Q1
1D
Clk
S
Q1
R
Q2
T, C
• Funktionsprinzip:
 die Information am D-Latch1 (Master)-Eingang wird
während Clk = 0 eingespeichert, das D-Latch2 (Slave)
ist dabei verriegelt
T
C1
Q2
Q1
T, C
 mit der Taktflanke Clk von 0 auf 1 wird das D-Latch1
verriegelt, und D-Latch2 ‚transparent‘:
der X-Wert erscheint am Ausgang Q1
Funktionsgleichung:
Q2
Q1(n+1) = Q1n
Clk
Taktgesteuertes T-Flipflop
t
Reichardt, Kap 11.6
D
• das T-Flipflop kippt nur, wenn T = 1, für T = 0 bleibt der
Ausgangszustand erhalten
t
X
T
C
t
&
&
Q1
S
R
Q1
Q2
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
Q1
Q2
Q+ = Q für T = 1
t
Digitaltechnik
HS2015
T
C
15
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
16
Rückflankengesteuertes JK-Flipflop
ein vielseitiges FF: das JK-FF
Reichardt, Kap 11.5
&
J
Q1
S
C
C
K
&
R
Q2
J
J
Q1
C
K
K
Q2
• Erweiterung des T-FF um die J- und K-Eingänge
• (vereinfachte) Wahrheitstabelle
Fall
J
K
Q1(n+1) Q2(n+1)
1
0
0
Q1n
Q2n
speichern
2
3
0
1
1
0
0
1
1
0
rücksetzen
setzen
4
1
1
Q1n
Q2n

SR - FF
kippt
T - FF
Funktionsgleichung:Q1(n+1) = [(J Q1 )  ( K  Q1)]n
• häufig eingesetzt in verschiedenen Varianten, insbesondere
mit mehreren J- und K-Eingängen
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
17
Master-Slave-FF, Zweispeicher-FF
Reichardt, Kap 11.7
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
SR-Latch aus NAND-Gatter
&
S
> das Master-FF übernimmt die Information mit der ersten
Taktflanke; das Slave-FF erhält die Information vom
Master mit der zweiten Taktflanke
Q1
&
 Master-Slave Flipflop: SR, oder JK
S
S
Q1 Q
R
R
Q2 NQ
Q2
R
Schaltzeichen
JK-Master-Slave Flipflop
J
J
C
K
Q m1
Q m2
K
18
Aufbauvarianten SR-Latch, D-Latch/DFlipflop
• Zweiflankensteuerung
Master
9. Sequenzielle Schaltungen
Tröster
C
D-Latch mit
Transmission-Gates
Slave
J (S)
K
Q1
C
C
1
D
Q2
1
Q
C
D-Flipflop
vorderflankengesteuert, aus 2 gekoppelten D-Latches
(Master-Slave-Prinzip)
Gegenüberstellung einflanken  zweiflankengeteuert
C
C
Q
C
t
J
1
D
K
1
1
1
Q
C
C
t
Q m1
D
einflanken
gesteu ert
C
C
C
C
t
Q
D-Latch 1
D-Latch 2
1D Q
1D Q
Q1
C1
C1
Q2
t
C
Q1
C
zw eiflankengesteuert
Transmission Gate
(aus Kap 3)
t
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
19
Digitaltechnik
HS2015
C
ETH Zürich Institut für Elektronik (IfE)
C = 0: gesperrt
C = 1: leitend
9. Sequenzielle Schaltungen
Tröster
20
Reset, Rücksetzeingang
welche Dynamik hat ein FF, ein Latch ?
Reichardt, Kap 11.4.11
teilweise im Textbuch,
Aufgabe in den Übungen
• Latches und Flipflops besitzen häufig einen Setz- oder
Rücksetzeingang, mit dem der aktuelle Speicherinhalt
überschrieben werden kann
• wie schnell reagiert ein FF, ein Latch ?
• wie muss das zeitliche Zusammenspiel von Clock und Daten
organisiert sein, um die Funktionssicherheit zu gewährleisten
?
• mit einem asynchrone Set/Reset kann der Speicherzustand
unabhängig vom Takt- und dem Dateneingang festgelegt
werden, z.B. D-FF mit asynchronem Setzeingang
T
C1
S1
S
R
tPLH/HL: Propagation Delay, Verzögerungszeit, Durchlaufzeit
Q1
1D
D
dynamische Kenndaten:
R1
'aktive Taktflanke bis Reaktion an den Ausgängen'
Q2
tp
C
t
monostabile Kippstufe, Monoflop
Q
t
• ein monostabile Kippstufe generiert einen Puls definierter
Länge tQ, getriggert (angestossen) durch einen
Eingangsimpuls
tSetup:
Setup-Zeit, Vorbereitungszeit, Einschwingzeit
'wie lange muss ein Datensignal vor der aktiven Taktflanke
unverändert anliegen, damit es sicher in das FF
übernommen wird ?
thold: Haltezeit
'wie lange muss ein Datensignal nach der aktiven Taktflanke
noch anliegen, damit es sicher in das FF übernommen wird ?
•Verweilzeit tQ durch RC-Glieder extern einstellbar
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
Daten können
ändern
D
9. Sequenzielle Schaltungen
Tröster
Daten müssen in
der Setup- und
Holdphase stabil
sein
21
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
Analyse
Daten können
ändern
1
D1
t
C
1D
QF1
D2
t
1D
Q F2
C1
C1
ts
22
C
Als Ausgang nutzbar QF1 oder QF2
th
Gleichungen:
1. QF1n+1 =
2. QF2n+1 =
Modell: Daten und Takt werden verzögert wirksam
3. D1n =
't s '
4. D2n =
D
Speicher
QF2n+1 =
4. in 2.
mit 1'+3.
C
Wertetabelle:
QF2n
QF2n-1
QF2n+1
't h'
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
23
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
24
wie schnell darf der Teiler getaktet werden ?
Ablauf:
QF2i-1
QF2i-2
QF2i
Zeitablauf
i
i+1
C
i+2
i+3
Q F1
i+4
t
t PFF
i+5
t
i+6
t PNOR
D2
.
i
t
QF2
Ablaufdiagramm Taktteiler
tS
t
C
t
D1
D1
t
• wie lange muss eine Taktperiode mindestens sein ?
t
Q F1
• zeitlich ‚längster‘ Pfad bestimmt die maximale Taktfrequenz:
definiert als Summe der Laufzeiten zwischen zwei Flipflops
einschliesslich Setup-Zeit
t
Beispiel:
D2
t
tPFF = 30ns; tPNOR = 10ns; tS = 20ns; thold = 4ns
Tmin  tPFF + tPNOR + tS = 60ns
Q F2
1
= 16.7 MHz
also fmax  T
min
t
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
25
Digitaltechnik
HS2015
9. Sequenzielle Schaltungen
Tröster
ETH Zürich Institut für Elektronik (IfE)
26
Latch, verbotener Zustand
Zusammenfassung
Nicht gleichzeitiger Wechsel
a.
• bistabile Kippschaltungen können nach zwei Kriterien
unterschieden werden:
b.
> Wirkung der Eingangssignale
Wie verhalten sich die Ausgänge Q1 und Q2, wenn
(S, R) = (1, 1)
 (1, 0) 
(0, 0)
(Q1, Q2) =
(...,…)

(…, …) 
(…,…)
. (S, R)
(1, 1)

(0, 1)

(0, 0)
(...,…)

(…, …) 
(…,…)
=
(Q1, Q2) =
> Wirkungsweise des Taktsignals
S
1. Eingangssignale
RS: Basismodul, Setzen, Rücksetzen, Speichern
D: Verzögerungsglied
T: Toggle-Glied
JK: Kombination von RS und T
1
1
R
2. Taktsignal
- ohne Taktsteuerung (Latch)
- mit Zustandssteuerung (Latch)
- mit Einflankensteuerung (Flipflop)
- mit Zweiflankensteuerung (Master-Slave-Prinzip)
Q1
Q2
Gleichzeitiger Wechsel (ideal)
S
t
R
t
Q1
t
Q2
t
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
27
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
9. Sequenzielle Schaltungen
Tröster
28
was sind Automaten, FSM
10. Automaten
Lernziele
• ein Automat beschreibt ein System, das
• was sind Automaten, sequenzielle Schaltwerke, 'Finite State
Machines' (FSM): Einstieg in die Automatentheorie
• was ist ein 'Mealy'-, was ein 'Moore'-Automat
> auf seinen Eingang reagiert,
> einen Ausgang generiert, der
> von dem Eingangssignal und von dem momentanen
Zustand des Systems eindeutig abhängt
• wie kann man Automaten beschreiben
• was ist ein Zustandsdiagramm, -graph
• wo wird eine Folgezustandstabelle benötigt
• wie lassen sich Automaten analysieren
• wie kann man Automaten bauen, synthetisieren
• endlicher Automat, 'Finite State Machine' FSM:
> die Menge der möglichen Eingabezeichen
(Eingabealphabet), die Mengen der möglichen
Ausgabezeichen (Ausgabealphabet) und die
Zustandsmenge sind endlich
Textbuch Reichardt
• Schaltwerke sind typische Beispiel für endliche Automaten
• im Textbuch Kap 12 sowie einige Ergänzungen
• synchrone Schaltwerke:
Motivation
> alle Speicherelemente besitzen den gleichen Takteingang
• Automaten spielen als Steuerungs- und Kontrollelemente
eine wichtige Rolle
> interne Zustandsänderungen laufen synchron mit dem
gemeinsamen Taktsignal
> in der Informationstechnik: Ablaufsteuerung in
Mikroprozessoren, Kontrolle der Kommunikation
zwischen verschiedenen Baugruppen, …
• asynchrone Schaltwerke:
> sie besitzen kein gemeinsames Taktsignal
> in der Verfahrenstechnik, Maschinenbau,
Regelungstechnik, wo Abläufe kontrolliert werden
müssen
10. Automaten
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
> Zustandsänderungen werden durch Änderungen des
Eingangssignals initiiert
1
Tröster
Y = (y1, y2, ... , yb)
Z = (z1, z2, ... , zm)
Z0  Z
Yn = f ( Xn, Zn )
Eingabealphabet mit e
Eingangszuständen xi, die durch
binäre Eingangsvariablen
xi,  repräsentiert werden
Schaltwerken oder bei Änderung des Eingangsvektors in
asynchronen Schaltwerken wird der Folgezustandsvektor
Zn+1 zum neuen Zustandsvektor Zn,
also
Zn := Zn+1
Ausgabealphabet mit b
Ausgangszuständen yi, und binären
Ausgangsvariablen yi, 
Zustandsmenge mit m (inneren)
Zuständen zi, und binäre
Zustandsvariablen
zi, 
Funktionsablauf in einem Mealy-Automaten
• Annahmen:
> synchrones Schaltwerk
> als Speicherelemente werden D-Flipflops eingesetzt
Anfangszustand
> bei der positiven Taktflanke (von 0 nach 1) schalten die DFFs
• Ablauf:
> für C = 0 sind die Eingänge der Speicherelemente
verriegelt. Mit den Vektoren Xn, Zn werden die
Schaltfunktionen f ( Xn, Zn ) und g ( Xn, Zn ) berechnet,
Yn ausgegeben und
der Folgezustandsvektor Zn+1 gebildet
Struktur (Huffman-Darstellung):
> während der positiven Taktflanke von C (von 0 nach 1)
wird der Zustandsvektor Zn+1 in die D-FF eingelesen und
kombinatorisches
Schaltnetz
f ( X n , Zn )
Clock
Digitaltechnik
HS2015
Yn
ist an deren Ausgängen verfügbar
• neben einflankengesteuerten FFs (D- und JK) können auch
Master-Slave-FFs benutzt werden
g ( X n, Z n )
Speicherelemente
• einfache Latches sind nicht geeignet, warum ?
Zn+1
• wieviele Zustände k kann ein Automat mit N Flipflops
maximal annehmen ?
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Ausgangsfunktion
Übergangsfunktion
> bei einem Taktwechsel von tn nach tn+1 in synchronen
'Mealy'-Automat
Zn
2
Tröster
Zn+1 = g ( Xn, Zn )
g {fc1 im Textbuch} : ( xi, zj,)  zk Übergangs-, Überführungsfunktion
f {fc2 im Textbuch} : ( xi, zj,)  yr Ausgangs-, Ausgabefunktion
Xn
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Schaltfunktion:
wie lassen sich Schaltwerke klassifizieren
• Definitionen:
X = (x1, x2, ... , xe)
Digitaltechnik
HS2015
Tröster
3
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
Synchroner Automaten:
sequenzielle Darstellung
Ausgang
Schaltfunktion:
Yn = f ( Zn)
Ausgangsfunktion
Ausgangsfunktion
Übergangsfunktion
Zn+1 = g ( Xn, Zn )
Yn
Moore-Automat
• Sonderfall des Mealy-Automaten:
der Ausgangsvektor Y hängt nur von den inneren Zuständen
ab, nicht vom Eingangsvektor, also
Zn
Struktur
f ( Z n)
Medwedjew-Automat
• der Ausgangsvektor ist mit den Speicherinhalten identisch
(z.B. bei Zähler)
Q2
C1
Clock
S
R
oder
Q1
Q2
Q1
C1
D
oder
K
Zn+1
C
Zn+1
Zustandsübergangsfunktion
Speicherelemente
C1
g ( X n, Z n )
J
Zn
nur bei Mealy-Automat
X
Zustandsspeicher
Q1
Q2
Y
Struktur
g ( X n, Z n )
C
Digitaltechnik
HS2015
Speicherelemente
Zn+1
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
5
Tröster
wie können wir die Funktion von
Schaltwerken beschreiben
Digitaltechnik
HS2015
Xn
Zn
Eingang
X
Eingangskodierung
Y
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Zustandsgraph, Zustandsdiagramm, Automatengraph,
'state graph', 'state transition diagram'
> Ausgangs- und Übergangsfunktionen
• graphische (äquivalente) Darstellung der
Folgezustandstabelle bestehend aus Knoten und
(gerichteten) Kanten
> KV-Diagramme
• die Knoten (Kreise) bezeichnen den internen Zustand
• für Schaltwerke gibt es verschiedene, äquivalente
Beschreibungsmöglichkeiten
> und bei Moore-Automaten zusätzlich den Ausgang, da der
Ausgang nur von den internen Zuständen abhängt
> Zustandsdiagramme oder -Graphen
> Zustandsfolge- oder Folgezustandstabellen
• der Übergang zwischen zwei Zuständen kennzeichnen
Kanten,
Zustandsfolgetabelle, Folgezustandstabelle,
Automatentabelle, 'state table', 'state transition table'
> die Eingangskombination e (und bei Mealy-Automaten
zusätzlich der Ausgang a), die die Zustandsänderung
bewirken, werden an der jeweiligen Kante vermerkt
• zu jeder Kombination der aktuellen internen Zustände und
des Eingangsvektors werden die Folgezustände und
Ausgangswerte aufgelistet (endliche Automaten !)
Struktur:
e/a
m: Anzahl Zustände
No
Eingang
Xn
momentaner
Zustand Zn
Ausgang
Yn
Folgezustand
Zn+1
1
x1,x2,...,xe
z1n, z2n,...,zmn
y1,y2,...,yb
z1n+1, z2n+1,..,zmn+1
Kanten
keine
Zustandsänderung
(Eigenschleife)
• verschiedene Anordnungen möglich und gebräuchlich
e: Anzahl Eingangsvariable
b: Anzahl Ausgangsvariable
6
Tröster
e/a
Zj /Yp
Zustand j
(und Ausgang p bei
Moore-Automaten)
Zi /Y h
Knoten
e/a
Zustand i
Belegung des Eingangsvektors
(und des Ausgangsvektors bei
Mealy-Automaten)
.

• maximale ‚Länge‘ der Tabelle, wenn alle Eingangs- und
Zustandskombinationen aufgeführt sind: max= 2e+m
• Zustandsdiagramme sind ein häufig verwendetes
Hilfsmittel zur Darstellung von Abläufen
• die internen Zustände Zn sowie die Ein- und
• wo ist der Takt ?
• wieviele Knoten, wieviele Kanten (maximal) ?
Ausgangszustände können in Form von Variablen oder in
kodierter (‚mit einem Namen‘) Form eingetragen werden
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
• wieviele Kanten ‚verlassen‘ maximal einen Knoten ?
7
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
Folgezustandstabelle
Analyse von Schaltwerken
• Aufgabe:
ein Schaltwerk ist vorgegeben, es soll analysiert werden
• Vorgehensweise:
> eine Zustandstabelle aufstellen,
> die Schaltfunktionen und/oder
> das Zustandsdiagramm bestimmen
Beispiel:
&
OUT
IN
z1
&
1D
z2
1D
C1
C1
No
Eingang
INn
moment. Zustand
z1n z2n
1
0
0
0
2
0
0
1
B
3
0
1
0
C
4
0
1
1
D
5
1
0
0
A
6
1
0
1
B
7
1
1
0
C
8
1
1
1
D
Ausgang
OUTn
Folgezustand
z1n+1 z2n+1
A
Zustandsdiagramm
Takt
• wieviel verschiedene Zustände:
• Automatentyp: Moore
• Eingabealphabet:
X = (IN)
Ausgabealphabet:
Y = (OUT)
Zustandsmenge Z = (z1, z2)
• Schaltfunktionen
> Ausgangsfunktion f ( z1, z2 ):
> Übergangsfunktionen g ( IN, z1, z2 )
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
9
Tröster
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
wie konstruiert man ein Schaltwerk:
Synthese
10
Tröster
Beispiel: Garageneinfahrt
weiteres Beispiel Im Textbuch Kap 12.3
• Aufgabe:
aus einer Funktionsbeschreibung ist ein Schaltwerk zu
entwerfen, das die vorgegebenen Spezifikationen erfüllt
» Aufgabenstellung:
> eine Garageneinfahrt ist mit 2 Lichtschranken x1 und x2
ausgerüstet; bei Unterbruch geht das jeweilige Signal x
von 0 auf 1
• Vorgehensweise:
> eine Schaltung soll anzeigen, ob ein Auto hinein- oder
herausfährt, oder ob sich kein Auto im
Lichtschrankenbereich aufhält
(1) Zustandsmenge bestimmen; daraus folgt die Anzahl der
Zustandsvariablen und die Anzahl der erforderlichen
Speicherglieder
> handelt es sich um eine kombinatorische Schaltung oder
um eine sequenzielle Schaltung ?
(2) Definition der Ein- und Ausgangsvariablen,
Wahl einer Zustandscodierung
(3) Darstellung der zeitlichen Zustandsfolge in einem
Zustandsdiagramm
Lichtschranke
c
(4) Aufstellen der Zustandsfolgetabelle
Einfahrt
(5) Bestimmen und gegebenenfalls Minimieren der
Übertragungs- und Ausgangsfunktionen
x
X1
(6) Prüfung auf unbenutzte Zustände
x < c
X2
» Entwurf
(7) Konstruktion des Schaltplanes anhand der
Schaltfunktionen
(1) Zustandsmenge:
k = 3 verschiedene Situationen sollen erkannt werden:
> einfahrendes Auto:
EIN
> herausfahrendes Auto:
AUS
> kein Auto
RUHE
• je nach Aufgabenstellung kann die Vorgehensweise
variieren
dafür werden 2 Flipflops benötigt
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
11
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
12
(2) Ein- und Ausgangsvariable, Zustandskodierung
(3) Zustandsdiagramm
Eingang:
die Kodierung für die vier möglichen Kombinationen ist
durch die Aufgabenstellung vorgegeben:
x1
x2
0
1
0
1
0
0
1
1
> Als nächster Schritt ist das Zustandsdiagramm zu
erstellen, das die Übergänge zwischen den 3
Automatenzuständen definiert
> Mealy-Automat:
y2
0
1
0
0
0
1
11/01
A
10/00
Eingangsalphabet:
Ausgangsalphabet:
Zustandsmenge:
> Rücksprung in den Zustand R, wenn keine Lichtschranke
mehr unterbrochen ist
EIN
AUS
RUHE
1
0
0
> bleibt solange erhalten, bis eine der Lichtschranken
anspricht
0
1
0
• Zustand A
> wird nur aus dem Ruhezustand R erreicht, wenn die rechte
Lichtschranke unterbrochen ist (x2 = 1)
> wenn beide Lichtschranken unterbrochen sind ('das Auto
fährt weiter'), wird das Ausgangssignal gesetzt (y2 = 1)
> Rücksprung in den Zustand R, wenn keine Lichtschranke
mehr unterbrochen ist
13
Tröster
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
> aus der Zustandsfolgetabelle können die KV-Diagramme für die
Folgezustände QBn+1, QAn+1 , y1 und y2 aufgestellt und z.B. über
> auf der Basis von Variablen (dc: 'don't care')
Eingänge
x1x2
Zustand
RUHE
EIN
AUS
00
01
11
10
R
R
R
A
E
A
dc
E
A
E
E
A
die disjunktive Normalform unter Berücksichtigung der
unbenutzten Zustände minimiert werden (übungshalber sind
beide Formen des KV-Diagramms benutzt; die KV-Diagramme
für y1 und y2 sind in die KV-Diagramme für QBn+1 und QAn+1
eingezeichnet)
x1
x1
Folgezustände
QB(n+1)
> in kodierter Form: (Di: don't care-Zustände)
No
Eingänge
x1n x2n
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
R
A
E
R
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
R
R
R
A
5
6
7
0
0
1
1
1
1
0
1
0
1
0
0
A
E
R
0
0
0
0
0
0
0
1
D0B
1
0
D0A
A
E
8
9
10
11
12
13
14
15
16
1
1
1
1
1
0
0
1
1
1
1
0
0
0
0
1
0
1
0
1
0
0
1
1
1
1
1
1
0
0
1
0
1
1
1
1
A
E
R
A
E
dc
dc
dc
dc
0
1
0
0
0
D1y1
D2y1
D3y1
D4y1
1
0
0
0
0
D1y2
D2y2
D3y2
D4y2
0
1
1
0
1
D1B
D2B
D3B
D4B
1
0
0
1
0
D1A
D2A
D3A
D4A
A
E
E
A
E
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
QB
D0
x2
1
y1
moment. Zustand Ausgänge
Folgezustand
QBn QAn
y1n y2n QBn+1 QAn+1
1
2
3
4
Digitaltechnik
HS2015
14
Tröster
(5) Übertragungs- und Ausgangsfunktionen
(4) Zustandsfolgetabelle
momentaner
• Zustand R
X = (x1, x2)
Y = (y1, y2)
Z = (E, A, R)
ETH Zürich Institut für Elektronik (IfE)
01/00
00/00
> wenn beide Lichtschranken unterbrochen sind ('das Auto
fährt weiter'), wird ein Ausgangssignal gesetzt (y1 = 1)
10. Automaten
Digitaltechnik
HS2015
11/10
E
• Zustand E
> wird erreicht nur aus dem Ruhezustand R, wenn die linke
Lichtschranke unterbrochen ist (x1 = 1)
Zustandskodierung:
die 3 Zustände des Automaten bedingen eine Kodierung mit
2 Binärstellen QB und QA, beispielsweise:
QB QA
Zusammenfassung:
10/00
R
01/00
kein Auto vorhanden
Auto einfahrend
Auto herausfahrend
> einfahrendes Auto:
> herausfahrendes Auto:
> kein Auto:
10/00
00/00
01/00
Ausgang:
3 Situationen sollen erkannt werden, also sind 2 Bit für die
Kodierung erforderlich, eine mögliche Kodierung:
y1
x 1x 2/y 1y 2
00/00
kein Auto vorhanden
Auto einfahrend
Auto herausfahrend
Auto zwischen den Schranken
1
1
D4
D2
D3
D1
x2
1

x1x2
QB QA
QB
Q
A
00
QA
A
01
11
QA(n+1)
00
1
D0
y2
01
1
1
D2
D4
11
QB

1
Q

D1
10
1
1
D3
10
15
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
16
es sollen D-Flipflops eingesetzt werden
(Qn+1 = Dn)
(7) Schaltplan
(realisiert mit D-FF)
> (minimierte) Übergangsfunktionen g(Xi, QA,B)
x1 x2
QB(n+1) = x1 . QA + x2 . QB
QA(n+1) = x2 . QB + x1 . QA
&
> (minimierte) Ausgangsfunktionen f(Xi, QA,B)
&
1
1D
QB
C1
y1 = x1 . x2 . QB
y = x .x .Q
2
1
2
A
(6) unbenutzte Zustände
> die 4 unbenutzten Zustände sind durch QA = QB = 1
&
&
gekennzeichnet
1
1D
QA
C1
> damit ergeben die Übergangsfunktionen aus dem Zustand
QA(n) = QB(n) = 1
&
QB(n+1) = 0 + x2
QA(n+1) = 0 + x1
y1
> Zustandsdiagramm für QA = QB = 1
x1 x2
&
R
11
y2
00
A
10
11
01
Clock
E
Fazit:
aus dem unbenutzten Zustand QA = QB = 1 findet der
Automat bei einer Änderung der Eingangswerte den Weg
in einen der 3 definierten Zustände
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
17
Tröster
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Moore-Automat für Garageneinfahrt ?
18
Tröster
Entwurfsaufgabe 1
• es ist ein Gerät zu entwerfen, das einen Impuls wählbarer
Dauer erzeugt (= Impulsgenerator)
1. wie ist der Zustandsgraph in Folie 14 für die Implementierung
mit einem Moore-Automaten zu ändern ?
Bedienelemente:
2. worin unterscheidet sich die Funktionalität ?
3. wird der Implementierungsaufwand grösser oder kleiner
sein ?
Wahl der
Impulsdauer
Impulsdauer in
Anzahl Taktperioden
'0'
'I'
'II'
'III'
kein Impuls
1
2
3
Vorschlag:
Startknopf: S
Impulsdiagramm
Takt
t
Start
t
'0'
t
'I'
t
'II'
t
'III'
t
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
19
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
20
Impulsgenerator
Entwurfsideen:
Entwurfsaufgabe 2
1. ein einstellbarer (Synchron-) Zähler
2. Automat:
abhängig von der Stellung des Wahlschalters wird ein
bestimmter Zustand in einem Zyklus angesprungen und
der Zyklus in seinen Ausgangszustand 'getaktet'
Zustandsmenge:
4,
• ein Automat soll aus einem seriellen Datenstrom die
Impulsfolge '0010110' erkennen und durch die Ausgabe y = 1
quittieren
> 7 innere Zustände z1, z2,..., z7 müssen behandelt werden
als A, B, C, D definiert
Eingangsvariable:
'0'
'I'
'II'
'III'
> 3 Flipflops sind erforderlich
> zur Codierung der 7 Zustände genügen 3 Zustandsvariable
zi, = (zi, , zi, , zi, )
e1 e2
00
01
10
11
Ausgangsvariable: Y
Start: S = 1
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
21
Tröster
Digitaltechnik
HS2015
Eingangskodierung
• ein Automat mit N Flipflops kann k = 2N Zustände
einnehmen
• eine allgemeingültige Entwurfsregel ist nicht anzugeben
• häufig werden nicht alle k = 2N Zustände, sondern nur kI< k
Zustände benötigt (abhängig von der Aufgabenstellung)
• die restlichen (k-kI) 'don't care'-Zustände können für die
Wahl der Zustandskodierung
Logikminimierung genutzt werden
• in einem Automat mit r Flipflop-Speicher wird jeder Zustand
mit einem eindeutigen r-Bit breiten Binärkode beschrieben
• um n Zustände mit r Bit zu kodieren, gibt es
• eine sichere ('robuste') Funktion setzt voraus, dass
r
2!
( 2  n )!
> beim Einschalten des Automaten und
> bei Störungen der Automat nach wenigen Taktzyklen in
das 'Nutzzustandsdiagramm' einläuft
r
nichtäquivalente Kodiermöglichkeiten
Beispiele:
n
3
4
5
10
15
r
2
2
3
4
4
22
Tröster
unbenutzte (parasitäre) Zustände
• wenn nicht alle möglichen Kombinationen der
Eingangsvariablen benutzt sind, kann die Anzahl durch
geeignete Kodierung reduziert werden
KM ( r , n )
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
• Entwurfsvorkehrungen
KM(r,n)
24
24
6720
2,9.1010
2,1.1013
> durch eine RESET-Schaltung sollen alle Flipflops aus jedem
beliebigen Zustand in einen definierten Startzustand z0
gebracht werden können
> wenn einer der 'don't care'-Zustände nicht in einen der
definierten Zustände gelangt, ist der 'don't care'Folgezustand durch einen der in kI definierten Zustände zu
• die Zustandskodierung bestimmt den Implementierungsaufwand für die kombinatorische Logik
ersetzen
• es sind heuristische rechnergestützte Verfahren bekannt,
um aufwandsgünstige Kodierungen zu suchen
• bei Moore-Automaten kann versucht werden, die
Zustandskodierung so zu wählen, dass die FF-Ausgänge
ganz oder teilweise den Ausgangsvariablen entsprechen; die
Ausgangskodierung vereinfacht sich dadurch
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
23
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
24
Synchronisierung der Eingänge
gekoppelte Automaten
• eine sichere Automatenfunktion setzt voraus, dass die
Eingangswerte X synchron zu der aktiven Taktflanke
wechseln
• (komplexe) Automaten können aus mehreren miteinander
kommunizierenden Teilautomaten aufgebaut werden
• die Zustandsanzahl des Gesamtautomaten ergibt sich aus
dem Produkt der Zustandsanzahlen der Teilautomaten
>wo liegt dann der Gewinn der Aufteilung ?
• ohne diese Synchronität zwischen Takt und Daten können
Fehlfunktionen auftreten:
> wenn sich bei dem Mealy-Automaten die Ausgänge ohne
Taktwechsel mit den Eingängen ändern,
• Vorteile:
> mehrere kleine Automaten sind zumeist übersichtlicher zu
entwerfen als ein komplexes Schaltwerk
> wenn unterschiedliche Laufzeiten in dem
kombinatorischen Schaltnetz an den FF-Eingängen zu
unerwünschten Datenwerten führen, die durch die aktive
Taktflanke in die FF übernommen werden.
> die Gesamtzustandsanzahl reduziert sich häufig, wenn
mehrere äquivalente Zustände zusammengefasst werden
können, oder wenn einige Zustände nicht erreichbar sind
(einfaches) Beispiel:
Abhilfe:
Synchronisations-Flipflop (-Register)
 ein Schaltwerk besteht aus den zwei synchronen Teilautomaten
Schaltwerk_1 und Schaltwerk_2
Clock
Out
+ C1
Start
R
Schaltwerk_1
X'
X
1D
1D
+
+
1D
+
DREI
Y
Automat
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
25
Tröster
 Schaltwerk_2 ist ein synchron rücksetzbarer
3-Bit-Dual-Zähler, der bei Erreichen des
Zählerstandes 3 bzw. 7 das Signal DREI bzw.
SIEBEN auf Eins setzt, und der durch
RESET=0 in den Folgezustand und bei
jedem Taktwechsel mit RESET=1 in den
Anfangszustand '000' übergeht
Digitaltechnik
HS2015
x1x/x1
1xx/10
warte1
warte2
5
8
7
6
Zustandsgraph
3-Bit-Dual-Zähler
26
Tröster
 Definition:
Zwei Zustände Z1 und Z2 eines Schaltwerk sind genau dann
äquivalent, Z1  Z2, wenn bei jeder für Z1 und Z2 zulässigen
xx1/10
Eingabefolge die gleichen Ausgangswerte generiert werden
und das Schaltnetz die gleichen oder äquivalente
Folgezustände einnimmt
 Satz (ohne Beweis):
Äquivalente Zustände Z1 und Z2 können zu einem neuen
Zustand Z1,2 zusammengefasst werden. In der
Folgezustandstabelle ersetzt Z1,2 jeweils Z1 und Z2; von zwei
identischen Zeilen kann eine entfernt werden
• Beispiel:
gegeben ist ein Automat mit den 4 Zuständen Z (A, B, C,
D), mit dem Eingang X, dem Ausgang Y und der
Folgezustandstabelle:
 12 Takte nach Start wird Out = 1
• wieviele Zustände hat der Gesamtautomat ?
• aufgrund der gegenseitigen Abhängigkeit beider
Teilautomaten sind nicht alle Zustände erreichbar, z.B.
> im Zustand 'warte2' läuft der Zähler (Schaltnetz_2) nur bis
zu dem Zählstand 3 und wird dann zurückgesetzt
> alle Zustände aus der Kombination des Zustands 'init' mit
einem beliebigen Zählerzustand sind äquivalent
10. Automaten
Tröster
1
Kein Prüfungsstoff .
• Beschreibung:
> ausgehend von dem Zustand 'init' wird mit dem StartSignal der Zähler (Schaltwerk_2) gestartet (RESET=1) und
der Zustand 'warte1' angelaufen
> dort verharrt das Schaltwerk_1 solange, bis nach 8 Takten
das Schaltwerk_2 das Signal SIEBEN auf Eins setzt und
Schaltwerk_1 in den Zustand 'warte2' wechselt
> Schaltwerk_2 startet wieder mit dem Zählerstand 0 und
setzt nach 4 Takten das Signal DREI=1 ab
> Schaltwerk_1 wechselt damit von 'warte2' nach 'init', das
Signal Out geht auf Eins
> Schaltwerk_1 verbleibt in dem Zustand 'init' bis zu einem
neuen Start-Impuls, während Schaltwerk_2 weiterläuft
ETH Zürich Institut für Elektronik (IfE)
4
• ähnlich wie bei dem Entwurf kombinatorischer Schaltungen
strebt man bei Schaltwerken eine Minimierung der
Zustände an
xx0/00
Digitaltechnik
HS2015
3
Zustandsreduktion
x0x/00
init
2
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
> Schaltwerk_1 ist durch ein Zustandsdiagramm beschrieben
Start DREI SIEBEN / RESET Out
0xx/x0
Takt
SIEBEN
• die aktive Taktflanke synchronisiert die Eingangswerte X' mit
den internen Zuständen Z des Automaten
• da der Datenwechsel an den Synchronisier-FFs mit der
Taktflanke zusammenfallen kann, sind sog. metastabile
Zustände prinzipiell nicht auszuschliessen
- MasterSlave FFs reduzieren die Wahrscheinlichkeit
Digitaltechnik
HS2015
RESET
Schaltwerk_2
27
Digitaltechnik
HS2015
moment.
Zustand Zn
Eingang
X
Folgezustand
Zn+1
Ausgang
Y
A
A
B
B
C
C
D
D
0
1
0
1
0
1
0
1
A
C
B
C
D
A
C
B
0
1
0
1
1
0
1
0
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
28
Zustandsdiagramm
Zustandsdiagramm nach der Zustandsreduktion
0/0
0/0
B
A
0/0
1/1
1/0
1/1
0/1
C
A/B
X/Y
X/Y
1/0
1/0
1/0
D
0/1
• welche Zustände sind zueinander äquivalent ?
> 1. Voraussetzung:
die Ausgangsfolge stimmt überein:
 A und C, A und D, B und C, B und D nicht äquivalent
• die Zustände C und D können zusammengefasst werden
Unvollständig spezifizierte Schaltwerke
• häufig enthält die Verhaltensbeschreibung von Automaten
unspezifizierte Ausgabewerte und Folgezustände, die zur
Minimierung der Zustandsanzahl genutzt werden können,
z.B.
> in dem Zustand Zi sei der Folgezustand nicht spezifiziert.
Ein Folgezustand Zin+1 könnte so definiert werden, dass er
dem Folgezustand Zjn+1 eines anderen Zustands Zjn+1
entspricht, Zi und Zj könnten dann zusammengefasst
> das verbleibende Paar {A, B} ist äquivalent:
 die Zustände A und B können zu A/B zusammengefasst
werden.
reduzierte Folgezustandstabelle:
Eingang
X
Folgezustand
Zn+1
Ausgang
Y
A/B
A/B
C
C
D
D
0
1
0
1
0
1
A/B
C
D
A/B
C
A/B
0
1
1
0
1
0
D
0/1
> 2. Voraussetzung (für die verbleibenden Zustandspaare {A, B}
sowie {C,D})
 C und D nicht äquivalent (in dem gegebenen Diagramm)
moment.
Zustand Z
0/1
C
werden, wenn die Äquivalenzbedingungen (s.o.) erfüllt
sind
• für die systematische Zustandsminimierung sind Verfahren
bekannt, z.B. mittels Implikantentabellen. Diese Verfahren
sind aufwendiger als die Logikminimierung mit KVDiagrammen.
• moderne Synthesewerkzeuge bieten automatisierte
Verfahren zur Zustandsminimierung an
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
29
Tröster
Automaten mit Festwertspeicher
‚Look-up-Table’
Variable:
Momentan_Zustand
nächster_Zustand
Ausgabe
Eingang
Beispiel Garageneinfahrt:
die Wertetabellen der Übergangsfunktionen
=x . Q
Q
.
A + x2 QB
wenn
QA(n+1) = x2 . QB + x1 . QA
dann
B(n+1)
1
y1 = x1 . x2 . QB
y2 = x1 . x2 . QA
1
Folgezustände Zn+1
+C1
R
1D
1D
+
+
programmierbarer Speicher
QA
QB
Y1
X1
X2
Y2
Speicherinhalte
Speicheradressen
• welche Speicherkapazität muss der Speicher (mindestens)
haben ?
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
A, R, E;
A, R, E
00, 01,10,11
00, 01,10,11
<Taktflanke (synchr. Automat)>
< Änderung Eingangsdaten (asynch. Automat)>
<Momentan_Zustand = nächster_Zustand>;
<Momentan_Zustand = R>
wenn <Eingang = 00>
dann <nächster_Zustand = R>
<Ausgabe = 00>;
wenn <Eingang = 10>
dann <nächster_Zustand = E>
<Ausgabe = 00>;
wenn <Eingang = 01>
dann <nächster_Zustand = A>
<Ausgabe = 00>;
end case;
case
<Momentan_Zustand = E>
wenn <Eingang = 00>
dann <nächster_Zustand = R>
<Ausgabe = 00>;
wenn <Eingang = 10> oder <Eingang = 01>
dann <nächster_Zustand = E>
<Ausgabe = 00>;
wenn <Eingang = 11>
dann <nächster_Zustand = E>
<Ausgabe = 10>;
end case;
2}
Reset
30
Tröster
case
sind in einem Speicher abgelegt. Die einzelnen Speicherzellen sind durch {x1 , x2 , QB ,QA} adressiert; die Zellen
enthalten die Werte für die Ausgänge {y , y und die
Takt
ETH Zürich Institut für Elektronik (IfE)
Garagenautomat, Pseudocode Mealy
• statt mit kombinatorischen Schaltungen können die
Übergangs- und Ausgangsfunktionen auch in
Festwertspeichern (Look-up-Table) abgelegt werden
und Ausgangsfunktionen
10. Automaten
Digitaltechnik
HS2015
31
Digitaltechnik
HS2015
10. Automaten
ETH Zürich Institut für Elektronik (IfE)
Tröster
32
Asynchronzähler
11. Zähler, Frequenzteiler
Synthesizer
• 'was heisst zählen ?'
Abfolge von Zuständen nach einem vorgegebenen Schema
durchlaufen
Lernziele:
• Beispiel:
• was gibt es für verschiedene Zählertypen
• wozu braucht man Zähler
2
• was ist der Unterschied zwischen einem synchronen und
einem asynchronen Zähler
3
4
1
• ripple
5
8
• zählt ein Modulo - Zähler Module
6
7
Zustandsgraph
Vorwärtszähler
• wie baut man Zähler für bestimmte Anwendungen
• wie einen programmierbaren Frequenzteiler
• Zähler (Automaten) mit JK-Flipflops
Zustands-Nr
1
2
3
4
5
6
7
8
(max 8 Zustände)
III
0
0
0
0
1
1
1
1
?
II
0
0
1
1
0
0
1
1
I
0
1
0
1
0
1
0
1
rückwärts
vorwärts
• I-Stelle: kippt bei jedem Zustandswechsel
Textbuch Reichardt:
• II-Stelle kippt bei jedem 2. Zustandswechsel
• Kapitel 13, auszugsweise
• III-Stelle kippt bei jedem 4. Zustandswechsel
• Grundbaustein: T-Flipflop (ohne Taktsteuerung, mit
Taktsteuerung siehe Kap 8, Folie 16)
Motivation:
• fast jedes elektronische Gerät beinhaltet Frequenzteiler, z.B.
von einem Quarzoszillator werden die Takte von
Subsystemen abgeleitet
T
• Zähler werden benötigt, um Zeiten auszumessen
(Stoppuhr), Abläufe zu steuern oder verschiedene
Systemzustände zu (de)kodieren
Digitaltechnik
HS2015
3-Bit Dualzähler
1
Tröster
Digitaltechnik
HS2015
3-Bit-Dualzähler
Q2
Q 1(n+2 ) = Q 1 (n+1 ) = Q 1n
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
asynchron
2
Tröster
 (synchron) ?
• 'wann ist das letzte Flipflop in der Kette gekippt ?'
Ketten(Reihen-)schaltung von 3 T-Flipflops
(Rückflankensteuerung)
LSB
Q 1(n+1) = Q 1n
• der Ausgangszustand wiederholt sich jeweils nach 2
Taktwechsel
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
Q1
T
• 'wie schnell darf der Zähltakt anliegen ?'
MSB
(nochmals) der 3-Bit-Dualzähler:
Zeitablauf-Diagramm mit Signallaufzeiten:
Zeitablaufdiagramm
Rückwärtszähler: wenn statt Qi die bitweise invertierten
Werte Qi benutzt werden
Digitaltechnik
HS2015
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
Tröster
3
Digitaltechnik
HS2015
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
Frequenzteiler
• Zustandsänderungen laufen in Form einer Welle durch die
Welle (ripple) durch die Flipflop-Kette, die
Einzelverzögerungen kumulieren
• jeder Dualzähler teilt die Taktfrequenz in Stufen von
Zweierpotenzen
• der Zeitpunkt, an dem der jeweils gültige Zählerstand
verfügbar ist, wenn also alle Flipflops ihren Zählerwert
eingenommen haben, hängt auch von dem Zählerstand ab
Beispiel:
3-Bit-Dualzähler mit Zeitablaufdiagramm
• wie gross ist die max. Taktfrequenz fmax, um in einer
n-stufigen FF-Kette jeden gewünschten Zählerzustand
gewährleisten zu können (mindestens für eine ‚kurze’
Zeitspanne):
mit tpi: max. Durchlaufzeit für das i-te FF
fmax =
1
 tpi
i
• Beispiel:
3-Bit-Dualzähler: tp1..3worst case = 30ns, dann
fmax = 11,1MHz
• bei einem 12-Bit-Dualzähler:
• mögliche Teilerverhältnisse:
fE
fT = n
2
Eingangs- (Takt)frequenz fT:
fE:
fmax = 2,8MHz
besser (aber aufwendiger): Synchronzähler
n:
mit
geteilte Frequenz
Anzahl der Flipflops
• Frage: welchen Einfluss hat die Durchlaufzeit auf die
Frequenzteilerfunktion ?
Digitaltechnik
HS2015
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
5
Tröster
11. Zähler
Digitaltechnik
HS2015
ETH Zürich Institut für Elektronik (IfE)
Modulo- n (mod-n) Zähler (?)
Synchronzähler
Reichardt, Kap 13.2
teilweise Reichardt, Kap 13.2
• Aufgabe:
'es ist ein Schaltwerk zu bauen, das bis zu einer bestimmten
Anzahl n von Zuständen zählt, und dann auf einen
vorgegebenen Zustand (z.B. den Anfangszustand) springt', z.B.
in einer Digitaluhr, Zählen auf 24h, 60min, 60sec
• im Gegensatz zu Asynchronzähler liegt der Takt an allen
Flipflops an: alle Flipflops schalten gleichzeitig mit dem
Takt: synchron
• Synchronzähler werden zumeist als MedwedjewAutomaten behandelt: die Ausgänge der Flipflops
entsprechen den Zählzuständen;
der Steuereingang X kann zur Ablaufkontrolle, z.B.
vorwärts/rückwärts eingesetzt werden
• Lösung für einen asynchronen Dualzähler:
der Zählzustand n wird durch eine kombinatorische Schaltung detektiert und der Zähler damit auf Null gesetzt (reset)
• Beispiel:
ein Modulo-5-Zähler durchläuft 5 Zählzustände und wird
mit dem nächsten Taktsignal auf den Anfangszustand 0
zurückgesetzt;
Codierung des Zustands: 1 0 1(2);
2
3
Y
X
7
C
4
4-Bit Ringzähler Zähler
mit asynchronem
Set/Reset für ‘1000’-Start
6
Z0
S
1000
0010
Clk
Start
Z0Z1Z2Z3
E
Schaltzeichen
QI
Q II
Q III
Tröster
0111
0000
Digitaltechnik
HS2015
R
S
Q
g
Z2
Z1
D
Q
Q
D
Z3
Q
D
0011
0001
7
Z0
D
Z0Z1Z2Z3
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
R
S
Q
C
‘1’
‘0’
4-Bit Johnson-Zähler mit
asynchronem Set/Reset
für ‘1000’-Start
Start
Digitaltechnik
HS2015
0100
D
C
R
S
R
Z3
Q
D
Q
C
y
Steuerblock
Funktionsblock
+
+
+
D
C
Start
Zustandsgraph
Z2
Z1
Q
D
0001
CTR 5
+
Zn+1
Speicherelemente
Beispiele:
5
8
g ( X n, Zn )
Zn
3-Bit-Zähler erforderlich:
1
6
Tröster
S
1111
1000
1110
1100
C
C
Clk
Start
R
S
C
R
S
C
R
S
R
‘1’
‘0’
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
zyklischer 3-Bit mod-6 Pseudo-Gray-CodeGenerator
KV-Diagramme für die Flipflops A, B, C:
QA
• Aufgabe:
es ist ein 6-stufiger Zähler mit JK-FFs für folgende,
vorgegebener Zustandsfolge zu entwerfen:
Nr QAn
1
2
3
4
5
6
7
8
QBn QCn
0
0
0
0
1
1
0
0
1
1
1
0
0
1
1
0
0
0
1
1
0
1
1
1
QAn+1
QBn+1
QA
QB
QA(n+1)
QB
QCn+1
QB
QB(n+1)
QB
QB
QC(n+1)
QB
• für die 6 Zustände sind 3 Flipflops (A, B, C) erforderlich
• die restlichen 2 Zustände sind als 'don't care'-Zustände zur
Logikminimierung zu benutzen
3
2
QC
• wenn JK-FFs benutzt werden sollen, dann sind die
Minimierungen im KV-Diagramm so vorzunehmen, dass für
Qk(n+1) sowohl Qk wie Qk berücksichtigt sind
4
1
5
8
• charakteristische Gleichung für das i-te JK-Flipflop:
Qi(n+1) = [( Ki . Qi) + (J . Qi ) ]
6
7
QC
QC
i
Digitaltechnik
HS2015
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
9
Tröster
Digitaltechnik
HS2015
n
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
10
Tröster
..und wenn der Zähler aus den 'don't care'Zuständen heraus startet ?'
JK-FF adäquate Formeln:
QA(n+1) = QA . QB + QA . QB . QC
QB(n+1) = QA . QB + QB . QC
• 1. Fall: Start aus dem 7. Zustand [QA QB QC]n=7 = 1 0 1
QC(n+1) = QC . QB + QA . QB . QC
Koeffizientenvergleich
JA = . QB . QC
KA = QB
JB = QC
KB = QA
JC = QA . QB
KC = QB
• Flipflop A:
 
KA = QB = 1
FF A wird zurückgesetzt, also QA(n+1) = 0
• Flipflop B:
 
JA = QB . QC = 0;
JB = QC = 1;
KB = QA = 1
FF B 'toggelt', also QB(n+1) = 1
• Flipflop C:
JC = QA . QB = 0; KC = QB = 0
FF C behält seinen Zustand, also QC(n+1) = 1
Schaltwerk
7
QC
[QA QB QC]7+1 = 0 1 1 : dies ist der Zustand 3,
QA
QB
3
2
4
1
damit die Zustandsfolge 1 0 1, 0 1 1, 0 1 0, ..
5
Takt
6
• 2. Fall: Start aus dem 8. Zustand [QA QB QC]n=7 = 1 1 1
1J C
C1
1JB
C1
1JA
C1
1K C
1K B
1KA
mit den Verknüpfungsgleichungen für die drei FFs
• Flipflop A:
 
KA = QB = 0
FF A behält seinen Zustand, also QA(n+1) = 1
• Flipflop B:
 
JA = QB . QC = 0;
JB = QC = 1; KB = QA = 1
FF B 'toggelt', also QB(n+1) = 0
• Flipflop C:
JC = QA . QB = 0; KC = QB = 1
FF C wird zurückgesetzt, also QC(n+1) = 0
[QA QB QC]8+1 = 1 0 0 : dies ist der Zustand 6
, damit die Zustandsfolge 111, 100, 000..
Digitaltechnik
HS2015
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
Tröster
11
Digitaltechnik
HS2015
2
3
Tröster
5
8
6
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
4
1
12
jetzt mit D-Flip-Flops
KV-Diagramme für die Flipflops A, B, C:
QA
QA(n+1)
QB
(n+1)
QC(n+1)
1
QB
Schaltwerk
QA
X1
QC
1
QA
QB
Takt
QB
X2
QB
X1
1
QB
X2
1
QB
X1
QB
X2
QC
C1
1
1
C1
C1
DC
DA
DB
1
QC
QC
• Können Hazards entstehen ?
D-FF adäquate Formeln:
QA(n+1) = QB . QC
QB(n+1) = QA . QB + QC
QC(n+1) = QA . QB
Koeffizientenvergleich:
Digitaltechnik
HS2015
Qi(n+1) = Di(n)
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
13
Digitaltechnik
HS2015
Tröster
Takt
• startet der Zähler im Zustand k,
R
Reset
-Bus
E0
E1
E2
E3
(ähnlich wie das Rechenwerk in Folie 8/11)
Takt
• gegeben ist ein Vorwärts-/Rückwärtszähler mit n Zuständen
+C1
4
1D
1D
1D
1D
- werden in Vorwärtsrichtung n-k Zustände,
Z
+ 0
Z
+ Z1
+ Z2
+ 3
- in Rückwärtsrichtung k Zustände bis zum Zustand n
durchlaufen;
- wenn für den Sprung vom Zustand
n zum Zustand k ein weiterer Takt
notwendig ist, erhöht sich die
Anzahl der durchlaufenen
Zustände jeweils um Eins
+C1
4
R
Reset
Z
+ 0
Z
+ Z1
+ Z2
+ 3
1D
1D
1D
1D
Zählerausgang: Z0..3
‘1’
B0
=1
‘0’
=1
‘0’
=1
‘0’
=1
A0
A1
A2
A3
Q0
Q1
Q2
4-Bit Q3
Lade
B2
Speicher
Cin
Zustand k
X = 0: Addition: ‘vorwärts’
X = 1: Subtraktion: ‚rückwärts‘
s0
s1
s2
s3
X
• für X = 0 wird +1(10) addiert, für X= 1 wird -1(10) addiert und das
Additionsergebnis in den D-Flipflops bis zur nächsten
Taktflanke gespeichert
Start
11. Zähler
Z0
Z1
Vorwärts/
Z2
RückwärtsZ3
Zähler
&
L
T
Q
T
vor/rück
• wenn der Zählstand Zn = ‘1111’ erreicht ist, wird mit L=1 der
dem Zustand k entsprechende Speicherwert in den Zähler
geladen und mit dem Zustand k gestartet
• das Toggle-Flipflop registriert die Zustandswechsel
• wie ist Taktverhältnis FT/FClk, wenn der Zähler jeweils m
Zustände durchläuft ?
• welcher Codierung erscheint an den Ausgängen Z0..3 ?
Tröster
rück
k
Clk
• durch Einspeicherung eines Startwertes in die D-Flipflops
kann die Zähldauer bis zu einem bestimmten Wert
programmiert werden
ETH Zürich Institut für Elektronik (IfE)
vor
Addierer
X
Digitaltechnik
HS2015
n
programmierbarer 4-Bit-Teiler aus Vorwärts-/RückwärtsZähler
B1
B3
14
Tröster
Programmierbarer Frequenzteiler
Synthesizer (Praktikum)
Zähler mit Addierer (Praktikum)
Schaltsymbol für 4 Input D-FF:
Eingänge Ei, Ausgänge Zi, gemeinsamer
Takt; über den Reset-Bus können die DFFs einzeln geladen werden
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
15
Digitaltechnik
HS2015
11. Zähler
ETH Zürich Institut für Elektronik (IfE)
Tröster
16
Aufgabe:
Schnittstelle zwischen einer
(seriellen) Leitung und einem 4-Bit
Schaltnetz
12. Register, Speicher
' DRAM, SRAM, ROM, PROM, EPROM, SDRAM ... ?'
Schaltbild:
Lernziele
Takt
• wozu müssen Daten geschoben werden: Schieberegister
?
Din
• was gibt es für Speicher
serielle
Leitung
• wie funktionieren sie und wofür kann man sie benutzen
• wie entsteht eine integrierte Schaltung
4 Bit
Schaltnetz
Textbuch Reichardt:
• Kapitel 14 (Auszug), 15
• gewünschte Funktion:
> über die serielle Leitung kommen digitale Daten
> das Schaltnetz verlangt, dass jeweils 4-Bit breite Worte
parallel (also 'gleichzeitig') zur Verfügung stehen
Motivation
• Register und Speicher sind Schlüsselbauelemente in
digitalen Systemen (SmartPhone, Digitaluhr,
Mikroprozessor, PCs, Grossrechner, ...)
• wie kann dieser 'Serien-Parallelwandler' aufgebaut werden ?
welche Detailfunktionen muss diese Baugruppe ausführen ?
> es müssen max. 4 Bit gespeichert werden
• in einem Mikroprozessor/PC/Laptop/SmartPhone entfällt
ein beträchtlicher Teil der Kosten auf die internen Speicher
> welche Speicher kennen wir: Latches, Flipflops
> Konstruktionsvorschlag:
- eine Kette von Flipflops,
- in der die Daten von einem FF zu dem nachfolgenden FF
bewegt ('geschoben') werden können, und
- wo jeder FF-Ausgang abgegriffen werden kann
 Schieberegister
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
1
Digitaltechnik
HS2015
Tröster
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
2
Tröster
Zeitablaufdiagramm:
4-Bit Schieberegister
Reichardt, Kap 14
die Dualzahl 0101 wird in das Schieberegister eingelesen
4-Bit-Schieberegister mit D-FF
QA
Din
1D
QB
QC
1D
C1
1D
C1
Q2
QD
1D
C1
Q2
Din
C1
Q2
Q2
Takt
'wie sieht die charakteristische Gleichung aus ?'
für ein D-FF:
Q1(n+1) = Dinn
allgemein: für die mte Stufe
oder
Qm(n) = Dinn-m
Qm(n+m) = Dinn
' welche Zeitbedingungen müssen erfüllt sein ?'
weitere Schieberegister, z.B.
> mit steuerbarer Schieberichtung
> mit einstellbarer Länge
> für umlaufende Daten ('Ringregister', ‚Ringspeicher‘)
(Reichardt, Kap 14.5.1)
> mit verschiedenen Wortbreiten (8 Bit, 16 Bit, 32 Bit,...)
• nach 4 Takten ist das Datenwort 0101 eingelesen und steht
parallel an den Ausgängen QA,..,D zur Verfügung
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
3
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
'was gibt es für Speichermedien ?'
allgemein: Register, Speicherregister
Einteilung:
• Aufbau:
Ketten von Flipflops, Latches, die parallel gesetzt und
parallel ausgelesen werden können
• nach der Bauart des Speichermedium:
> Lochkarten und Lochstreifen
• Funktion:
Zwischenspeichern von Daten, z.B. von ihrem Weg von
einem Massenspeicher in das Rechenwerk
> Magnetbänder
(nur ca 15% der Plattenspeicherkosten)
> Plattenlaufwerke (magnetische oder optische
Speicherung)
'wozu braucht man grosse Speicher ?'
1 Buchstabe (ASCII)
1 Byte = 8 Bit
100 - 6000 GByte
3,6 kByte
Zugriff im Bereich von ms
1 gedruckte Seite (80 Zeichen/Zeile, 45 Zeilen)
1 Buch (300 Seiten)
1,1 MByte
> Ferrite
1 SW-Bild (VGA: 480 x 640, 1 Byte je Bildpunkt)
307 kByte
> Halbleiter (Silizium-IC, DRAM)
1 Farbbild (1024 x 1024, 3 Byte je Bildpunkt)
3.1 MByte
1 sec gesprochener Text (Telephon, 8kHz x 8 Bit)
64 kBit
Spielfilm HD-Qualität (z.B. für BluRay)
> 50GB
1 Bit pro Kern
• nach der Funktion:
> nur Lesen: (CD-)ROM: 'Read Only Memory'
> gleichwertiges Lesen und Schreiben: RAM 'Random Access
Memory' (wahlfreier Zugriff)
• Entwurfsprogramme für integrierte Schaltungen:
CADENCE: > 10 GB
> statischer oder dynamischer Speicher
• Speichersystem am D-ITET
> permanente Speicherung oder nur temporär
(Abhängigkeit von der Betriebsspannung)
• Home-Daten von Studenten und Mitarbeiter auf Hitachi
SAN Speicher: 40TB
• Institutseigene NAS-Systeme für Projektdaten:
Kilo Bit
Mega Bit
Giga Bit
TeraBit
:
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Kennwerte Speicherkapazität
200TB
• Backup- und Archivdaten auf jabba (Tape-Roboter);
650TB
5
Tröster
Digitaltechnik
HS2015
Si-Präfixe
kbit 103 Bit
Mbit 106 Bit
Gbit 109 Bit
Tbit 1012 Bit
12. Register, Speicher
• Beispiel: 16kBit-Speicher, jede Speicherzelle ist einzeln
ansprechbar: bitorganisiert
• Zellenarray, Speichermatrix, angesteuert von einem Zeilenund Spaltendekoder
1
2
3
M
> quadratische Speichermatrix wird angenommen, N = M
> mit N = M = 7:
2N . 2M = (128 . 128) = 16 384 (Bit)
wären 2 . 128 = 256 Adressleitungen notwendig !
Spalten
• Dekoder = Kodeumsetzer:
ein k-Bit breiter Kode wird in einen 2k - Bit breiten Kode
umgesetzt
1
Speichermatrix
N
• Konstruktionsprinzip: (N)AND-Tree
2
Zeilen
1-Bit
x1
x1
Zelle
N
Schreiben
Lesen
x2
xk
xk
.
a1
2M
Spalten-Dekoder
Schreib-/Leseverstärker
1 2 3
........
.. . . . . . . . .
........
.
M
........
.. . . . . . . . .
........
.
Spaltenadressen
• der Spaltendekoder kann sowohl Lese- wie Schreibsignale
verarbeiten
Digitaltechnik
HS2015
x2
&
2N
1
DatenEingang
Ausgang
6
Tröster
'wozu ein Dekoder ?'
Aufbau:
2
Binär-Präfixe
210 Bit 1024 Bit
220 Bit 1.046576 Bit
230 Bit 1.073743 109 Bit
240 Bit 1.099511627776 1012 Bit
Kibit
Mibit
Gibit
Tibit
ETH Zürich Institut für Elektronik (IfE)
Schreib-Lesespeicher: RAM
Zeilenadressen
8 Gbit ( 16GBit)
Zugriff innerhalb 50 ns
> Halbleiter (Silizium-IC, Flash)
128/256 Gbit
Zugriff innerhalb 200μs/Schreiben, 25μs
Software:
Digitaltechnik
HS2015
400 GByte
Zugriff bis 3 min
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
&
a2
.
.
&
ak
2
• Speicherorganisation: bitweise, byteweise (8 Bit), wortweise
(16 Bit, 32 Bit,..)
7
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
Speicherelemente
statische Speicher: SRAM
EPROM, EEPROM, Flash
Reichardt, Kap. 15.3
• ein Floating-Gate-Transistor (FAMOS) kann durch Anlegen
einer Programmierspannung in einen Zustand gebracht
werden, wo die Permanentladung auf dem Floating-Gate
den MOS-Transistor durchsteuert;
• die einzelne Speicherzelle besteht aus einem vereinfachten
Latch (nur mit einem 'Setzeingang'), das über MOS-Schalter
angewählt werden
* die Ladungen können wieder abgebaut werden
* durch UV-Strahlung  EPROM
* durch einen elektrischen Löschimpuls  EEPROM, Flash
eine
Speicherzelle
1
N1
N2
1
Aufbau eines FlashTransistors
Wordleitung
(Zeilenauswahl)
BitLeitung
• Zwei Konfigurationen: NAND-, NOR-Flash
BitLeitung
* NAND: hohe Packungsdichte, für Blocktransfer (z.B. Bilder)
und SSD ‚Solid-State-Disk‘
* NOR: wahlfreier Zugriff, für Speicherung/Zugriff von
Programmcode
• mit der Wortleitung (= 1) wird eine Speicherzeile angewählt:
die NMOS-Transistoren N1, N2 sind durchgeschaltet
• Zwei Zell-Codierungen
• über die ausgewählten Bitleitungen kann der Speicherinhalt
gelesen
oder das Latch gesetzt werden
* SLC: Single Level Cell: ein Bit pro Zelle wird gespeichert,
* MLC MultiLevel Cell: mit 4 gestaffelten Schwellspannungen
werden 4 Zustände - codiert in 2 Bit - definiert;
MLC höhere Packungsdichte, aber geringere
Langzeitzuverlässigkeit, daher für (billige) USB-Sticks
• CMOS-SRAM-Speicherzelle besteht aus 6 MOS-Transistoren
• meist als Caches benutzt
• Zugriffszeit ('Access Time') 3ns ... 20ns
• Zellgrösse für 32nm Technologie (2015):
0.06μm2
‘1’
Uth_1
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
9
Tröster
Dynamische Speicherzelle: DRAM
'Ein-Transistor-Zelle'
Digitaltechnik
HS2015
MLC
SLC
Codierung ‘Single Layer‘ und ‘Multi Layer-‚ Zelle
‘1 1’
‘0’
Uth_2
Uth_1
‘1 0’
Uth_2
‘0 1’
Uth_3
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
‘0 0’
Uth_4
10
Tröster
DRAM-Technik:
höchstentwickelte Fertigungs-Technologie
• 'dreidimensionaler' Zellenaufbau:
der Speicherkondensator ist unter dem Schalttransistor
'vergraben'
• 'was ist die minimale Konfiguration, um ein Bit zu
speichern ?'
• statt Plattenkondensator ein 'vergrabener' Kondensator
• 'Trench'-Technologie (4MBit, Siemens, ca 1995)
eine
Speicherzelle
Wordleitung
(Zeilenauswahl
BitLeitung
• über den (nichtidealen) MOS-Schalter (Raus ≈ 1010..1012 )
entlädt sich der Speicherkondensator (Cspeicher ≈ 6.. 20 fF)
• der Speicherinhalt muss periodisch erneuert werden
('Refresh')
• Refresh-Zyklus ca alle 20ms: Steuerschaltung liest jede Zelle;
eine vorhandene '1' wird zurückgespeichert
• wie viele Elektronen ‚bilden’ 1 Bit ?
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
11
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
12
Grössenvergleich mit einem Haar: (4MBit von Siemens)
kompletter 4Mbit-Speicherbaustein (Siemens, ca 1995)
Silizium-Wafer (16cm Ø) mit 16MBit-DRAM-Speicher (140mm2)
• weitere Entwicklungsplanungen (entsprechend
‚International Technology Roadmap for Semiconductors ITRS
http://www.itrs.net/ ):
Speichergrösse Einführungsjahr
• Grösse von Halbleiter-Speicherzellen (je Bit):
16 MBit- 64 MBit- 256 MBit- 1Gbit4Gbit- Speicher
1,5 μm2 < 1 μm2 <0.2 μm2 <0.04 μm2
4μm2
• Vergleich mit Platten- und Magnetbandlaufwerken
0.003 μm2 je Bit
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
1 GBit
16 GBit
128GBit
512GBit
13
Tröster
Hard Disk, HDD
Digitaltechnik
HS2015
2001
2007
2013
2019
4 GBit
64 GBit
256GBit
1024GBit
2004
2010
2016
2022
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
14
Tröster
Vergleich Disk, NAND Flash, Magnetband
Tape
R. Fontana¹, G. Decad¹, S. Hetzler² – ¹IBM Systems Technology Group, ²IBM Research
Division, April 2012
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
15
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
16
Lesezyklus
Handhabung DRAMs
•Reduktion der externen Anschlüsse:
–Adressen 'gemultiplext'
Address
–3 Steuersignale
–RAS: Row address strobe
Einlesen
Zeilenadresse
–CAS: Column address strobe
–WE: Write Enable
Einlesen
Spaltenadresse
Row Address
Col Address
RAS
CAS
Valid
Dout
Zugriffszeit
Access Time
Row
Adress
Setup
Storage Matrix
Row
Decoders
Col.
Adress
Setup
64 x 64
Address
Row Address
Col Address
RAS
Row Address
Column Address &
Control Signals
A5
. . .
A0
RAS
CAS
Column Latches,
Multiplexers/Demultiplexers
Control
Logic
Valid
Dout
CAS
WE
DOUT
Digitaltechnik
HS2015
DIN
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
17
Tröster
Schreibzyklus
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
18
Tröster
Festwertspeicher: ROM, PROM, EPROM,..
Reichardt, Kap 15.3
1.Einlesen Zeilenadresse
Address
2. Write Enable
RAS
3. Einlesen Datenbit
CAS
4. Zeile zurücklesen
WE
5. Abschluss Einlesen
Din Write Time
Row Address
• ROM: Read Only Memory
Speicherinhalt kann nur gelesen, nicht (einfach) modifiziert
werden
Col Address
• PROM: Programmable ROM
der Speicher kann einmal durch den Benutzer programmiert
werden
• EPROM: Erasable PROM
Löschen und Neuprogrammieren des Festwertspeichers sind
möglich
> EEPROM: Electrical Erasable PROM = Flash Memory
Aufbau von Festwertspeicher
Valid
• Aufbau ähnlich dem von DRAMs: Speichermatrix, Dekoder,
Ausleseschaltung:
64 x 1 Bit
ROM
Address
Row Address
Col Address
RAS
CAS
WE
Din
Digitaltechnik
HS2015
Valid
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
19
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
20
FIFO (First In/First Out)
•Dual-Port
• zwei voneinander unabhängige Speicherbänke, die
nacheinander adressiert werden
•mit einem festen Takt zeiteffizientere Nutzung des DRAMKerns: kontinuierlicher Datenfluss möglich
Schreib-/Lesespeicher mit seriellem Zugriff
Eingang
Dual-Port RAM
•Steuersignale taktgebunden (vereinfachte Handhabung für
den Anwender)
Ausgang
Pipelined DDR (DoubleSDRAM
Schreib-Takt
Lese-Takt
Neue Speicherarchitekturen
SDRAM: Synchronous DRAM, DDR: Double Data Rate
DDR-SDRAM für geringen Energieverbrauch
(Mobilgeräte)
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
21
Tröster
Digitaltechnik
HS2015
neuartiger Speicher: Ferroelektrische RAM
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
22
Tröster
wie geht es weiter: Nanotechnologie
• ferroelektrischer Effekt:
Materialeigenschaft, eine elektrische Polarisation trotz
fehlendem elektrischen Feld beizubehalten: Hysterese
(ähnlich zu dem ferromagnetischen Effekt)
Trigate-Transistor (intel):
Bessere Kontrolle der
Bauelementeigenschaften für
Gatelängen kleiner
20nm
• ferroelektrischer Kondensator:
> behält seine gespeicherte Polarisierung
> kann durch eine äussere Spannung umgeladen werden
> hohe Zugriffsgeschwindigkeit: bis zu 100 Mal schneller
und mit weniger Energie als in Flash-Speichern, aber bei
deutlich höherem Flächenbedarf
> integrierbar in CMOS-Technologie
z.B: Microcontroller mit FRAM als statischer Speicher
U int
NanowireTransistor
U ext
eine
FRAM Speicherzelle
1-Bit-Speicher mit
ferroelektrischem
Kondensator
Wordleitung
(Zeilenauswahl)
Daten (2009):
128Mb Speicher
Zellgrösse 0.25μm2
BitLeitung
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
23
Digitaltechnik
HS2015
12. Register, Speicher
ETH Zürich Institut für Elektronik (IfE)
Tröster
24
Verifikation  Testen ?
13. Testen
Lernziele
wozu muss getestet werden
welche Fehler können auftreten
Fehlermodelle
Stuck-at ?
Testpatterngenerator, BIST
hier nur ein ‚Hineinriechen’ in ein sehr breites Gebiet möglich






Verifikation:
vor der Fertigung wird überprüft, ob der Entwurf mit der
geforderten Spezifikation übereinstimmt

es existieren formale Methoden, z.B. basierend auf Binary
Decision Diagrams BDD, um eine Spezifikation mit den
Entwurfsdaten zu vergleichen

auch bekannt unter ‚model checking’, ‚formale Verifikation’

Textbuch
Testen:
nicht enthalten

Ausmessen der realisierten Schaltungen, um Herstellungsund Ausfallfehler zu erkennen

Motivation
in der Fertigung elektronischer Komponenten sind statistisch
verteilte Fehler unvermeidbar
jede Komponente muss daher vor der Auslieferung getestet
werden
die Komplexität elektronischer Systeme verlangt
Vorkehrungen beim Entwurf, um die Testbarkeit sicher zu
stellen



Digitaltechnik
HS2015
13. Testen
ETH Zürich Institut für Elektronik (IfE)
Beispiel: Leiterbahnabriss in einer integrierten Schaltung
1
Tröster
Herstellungsfehler bei integrierten
Schaltungen/Systemen
Digitaltechnik
HS2015
Tester
TestmusterGenerator/
Analysator
Parametrische Defekte:
elektrische Parameter: Schichtwiderstände,
Stromverstärkung, Schwellspannung, Lithographie,
Justierfehler


Verhältnis zwischen den hergestellten Komponenten und
den fehlerfreien Komponenten

Ausbeutemodell:

Annahme: gleichverteilte Defekte konstanter Dichte
(Poisson-Verteilung);

Testmuster
Systemausgabe
DUT
Device under Test
‚Tester’ (von HP): ATE: Automatic Test Equipment
Ausbeute

2
Tröster
Wie testet man eine Digitalschaltung ?
Prozessdefekte:
Leitbahnabrisse und -Kurzschlüsse, Leckströme (pnÜbergang), Oxidlöcher, Kristalldefekte

13. Testen
ETH Zürich Institut für Elektronik (IfE)
über max. 256 bidirektionale Pins (Kontaktpunkte) wird das
IC/Board angeschlossen
jeder Pin ist mit einem eigenen Rechnerboard/
Patterngenerator/Patternanalysator verbunden
die Testmuster können zeitlich gegeneinander im 10psRaster verschoben werden
Defektdichte: D = AnzahlDefekte/ Flächeneinheit [cm-2]
abhängig von Prozesskomplexität, Integrationsdichte
Chipausbeute: Yc = exp(-D.A) (A: Chipfläche)


höhere Ausbeute
bei kleinen ICs

wie gross darf die
Defektdichte D in einer intel-Fab sein, damit aus einer
Siliziumscheibe mit 300mm Ø mindestens 50% der 4 cm2grossen Pentium-ICs verkauft werden können ?
Digitaltechnik
HS2015
13. Testen
ETH Zürich Institut für Elektronik (IfE)
Tröster
3
Digitaltechnik
HS2015
13. Testen
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
Funktionstest:



Prüfbus, Scan Path
entsprechend der Spezifikation werden Eingangswerte
angelegt, die Ausgänge ausgelesen und mit den Sollwerten
verglichen


wieviele Eingangswerte müssen angelegt werden, um die
Funktionalität vollständig abzutesten ?
Ziel: alle innere Knoten eines Systems können beobachtet
(‚Observability‘ )und gesetzt werden (‚Accessability‘)
Ansätze:
1. Aufteilung des Systems, zusätzliche Testpunkte
2. Prüfbus (Scan Path); IEEE JTAG (Joint Test Action Group)
Beispiel: Digitaluhr
o wieviele Zyklen sind notwendig, um den 23-BitTeiler vollständig zu testen ?
o wie testet man die Schaltjahrfunktion ?
Problemstellung

um ein Steuerwerk mit n Zuständen und m
Eingangsvariablen eindeutig zu verifizieren, sind bei einem
Funktionstest (d.h. Anlegen von Testdaten an dem Eingang
und Vergleich der gemessenen Ausgangsdaten mit den
(n-1)
Solldaten) mindestens Lmin = m Testzyklen notwendig
Lmin = 10
918
Mikroprozessor intel 8085: Lmin = 10
10
Beispiele: 8-Bit-Rechenwerk:

58

Speicher
8 Bit
1kBit
1Mbit


Digitaltechnik
HS2015
Zustände
256
10300
10 300.000


Funktionstest bei komplexen Systemen ökonomisch nicht
durchführbar

Testen ist ein zentrales Problem im Entwurf und in der
Fertigung: Design for Testability
13. Testen
ETH Zürich Institut für Elektronik (IfE)
5
Tröster
Digitaltechnik
HS2015
alle Speicherelemente können im Prüfmodus zu einem
Schieberegister zusammengeschaltet werden
im Testmodus wird ein Testvektor in das Schieberegister
geschoben
die Schaltung wird in dem Normalmod getaktet, damit
ändern sich die Registerinhalte
nach Zurückschalten in den Testmod wird das
Schieberegister ausgelesen und verglichen
für den Prüfbus ist zusätzliche Hardware notwendig (ca 15%)
> Erweiterung der Register (FF)
> zusätzliche Verbindungen
13. Testen
ETH Zürich Institut für Elektronik (IfE)
6
Tröster
Scan-Register
Sequenzielle Schaltung mit Prüfbus


um einen Scan-Pfad aufzubauen, müssen die Register durch
‘scan-fähige’ Register ersetzt werden
der Eingang ist über die Testleitung zwischen der Daten- und
der Prüfleitung umschaltbar
Data D i
&
Multiplexer
SCAN OUTi
&
SCAN IN i
Q1
1D
&
Q2
C1
TEST
CLK
Normalmodus
Board mit Prüfbus
T
d
SCAN OUTi
Data D i
SCAN IN i
TEST
CLK

Digitaltechnik
HS2015
13. Testen
ETH Zürich Institut für Elektronik (IfE)
Tröster
7
Digitaltechnik
HS2015
Q1
1D
C1
Q2
wie verändert sich die Schaltung unseres Garagenautomaten,
wenn Scan-Register benutzt werden ?
13. Testen
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
Automatische Testmustergenerierung ATPG
Fehlermodelle


es werden technologische Fehler in den Gatter angenommen

welche Testmuster sind anzulegen, um diese Fehler zu
erkennen ?
Stuck-at-Fault (Haftfehler) häufig in der CMOS-Technik

Pfadsensibilisierung
Annahme: infolge eines Kurzschlusses oder einer
Leiterbahnunterbruchs ‚klebt’ (genau) ein Eingang oder
Ausgang eines Gatters fälschlich auf dem binären Wert ‚1’
(stuck-at-1) oder auf dem binären Wert ‚0’ (stuck-at-0)

Beispiel: NAND-Gatter mit 3 Eingängen

Fragestellungen:
a
Beispiel: gegebene kombinatorische Schaltung
A
C
&
c



Fehlertabelle:
a/0
a/1
b/0
b/1
c/0
c/1
z/0
 Stuck-at-Fehler
000
x
001
x
010
x

x

x
011
x
100
x
101
111
x
x
x

x
110
Digitaltechnik
HS2015
z/1
x
x
Z
&
F
die 7 Knoten können 14 Single-Stuck-at Fehler annehmen:
A/0, A/1, B/0, B/1, C/0, C/1, D/0, D/1, E/0, E/1, F/0, F/1, Z/0, Z/1
um A/0 zu testen, muss A auf 1 gesetzt werden
beobachtbar ist nur der Knoten Z, es muss also ein Pfad von A
nach Z gefunden und die restlichen Eingänge B, C und D
geeignet gesetzt werden

B=1, da für B=0 der Knoten E unabhängig von A ist

aus gleichem Grund F=0, daher Cund/oder D =0
wenn A/0 vorliegt, folgt E=1, Z=1, sonst E=0, Z=0
A/0 kann ebenfalls ausser mit ABCD =1101 auch mit 1110 und
1100 am Ausgang Z erkannt werden
der einfache Algorithmus funktioniert nicht in allen Fällen,
daher werden weiterentwickelte Verfahren eingesetzt, z.B.
der D-Algorithmus (J.Roth, IBM 1960)
x
13. Testen
ETH Zürich Institut für Elektronik (IfE)
E

D
z
 können alle Fehler gefunden werden, welche
Eingangspattern werden nicht benötigt ?
abc
&
B
b
 mit welchen Eingangsdaten kann ich
welchen Stuck-at Fehler erkennen
verschiedene Verfahren bekannt, anhand der
Schaltungsstruktur Testmuster zu generieren, die Fehler
gemäss vorgegebener Fehlermodelle detektieren
9
Tröster
Digitaltechnik
HS2015
13. Testen
ETH Zürich Institut für Elektronik (IfE)
10
Tröster
Nichtdetektierbare Fehler

Linear Feedback Shift Register
wenn Redundanz in eine kombinatorische Schaltung
eingebaut wurde, z.B. für die Vermeidung von Hazards,
können nicht alle Stuck-at-Fehler erkannt werden
einfache Schaltung, um eine ‘Zufallsfolge’ zu generieren
Fehlersimulation


alle ‚möglichen’ Fehler an jedem Gatter werden auf ihre
Wirkung und Detektierbarkeit untersucht
damit Berechnung der Fehlerabdeckung: wieviele der
möglichen Fehler werden mit einem Testmustersatz erkannt
Selbsttest BIST: (built-in selftest)



ein eingebauter Generator erzeugt ein binäres Testmuster
und vergleicht die Reaktion mit einem abgespeicherten
Sollwert
Ausfallmechanismen, 'Burn-In'
Vorteile:
o Paralleler Test möglich: kürzere Testzeit

o Test kann im Normalbetrieb ohne einen externen
Tester wiederholt werden

Kosten:

o zusätzlicher Hardware- und Softwareaufwand

die meisten Defekte zeigen sich in den ersten
Betriebsstunden
'künstliches Altern', Burn-In
Bauteile werden über eine begrenzte Zeit (z.B. 100h) bei
hoher Temperatur betrieben
danach geringere Ausfallwahrscheinlichkeit
 Generatoren:
Signaturregister, Zähler, Programmsegmente etc
Digitaltechnik
HS2015
13. Testen
ETH Zürich Institut für Elektronik (IfE)
Tröster
11
Digitaltechnik
HS2015
13. Testen
ETH Zürich Institut für Elektronik (IfE)
Tröster
12
wie muss eine Maschine gebaut sein,
14. Mikroprozessor
?
Lernziele
• die logische Verknüpfungen von binären Zahlen
durchführt,
• was ist ein Mikrocomputer, Mikroprozessor ?
• wie ist er aufgebaut ?
• die die 'Grundrechenarten' (Addition,
Multiplikation, Division) beherrscht,
• was versteht man unter einer 'von Neumann' - Architektur ?
• was verbirgt sich hinter ALU, CPU ?
• CISC, RISC ?
• die Abläufe steuert,
• was ist ein digitaler Signalprozessor ?
• deren Verhalten nicht durch die Hardware,
sondern durch den Benutzer bestimmt und
d
verändert
( programmiert ) werden kann.
Textbuch
• im Textbuch nicht behandelt
(kein Prüfungsstoff)
welche Funktionseinheiten sind notwendig ?
> in den Vorlesungen Informatik 1/2 wird der Mikroprozessor
ausführlich behandelt !
• Speicher, um
> das auszuführende Programm und seine einzelnen
Anweisungen sowie
Motivation
> Daten, z.B. Zwischenergebnisse
ablegen zu können
• alle notwendigen Baublöcke (kombinatorische und
sequenzielle Schaltungen, Register, Speicher, Busse,..) sind
bekannt, um einen Digitalrechner aufbauen zu können
• Rechenwerk, das die arithmetischen und logischen
Operationen durchführt
• in der (Digital-)Elektronik und Systemtechnik ist der
Mikroprozessor ein dominierendes, nicht mehr
wegzudenkendes Bauteil
Digitaltechnik
HS2015
• eine Steuereinheit, die für den Programmablauf und für die
Kommunikation zwischen den verschiedenen
Funktionsblöcken verantwortlich ist
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
1
Tröster
eine geniale Universalarchitektur:
der 'von Neumann' Computer
Digitaltechnik
HS2015
• die Wahl des nächsten Befehls kann von dem aktuellen
Ergebnis aus der ALU abhängen
> damit sind Konditionalabfragen möglich: z.B.
if <Wert a> grösser 0, then springe <Adresse b> an
> Schleifen mit variabler Anzahl von Durchläufen können
programmiert werden
Aussenwelt
Steuerwerk
• gleichartige Speicherung von Daten und Befehlen
> Befehlsadressen können wie Daten abgespeichert und zu
einem späteren Zeitpunkt zurückgeholt werden, um den
Programmablauf an einer bestimmten Stelle weiterlaufen
zu lassen:
Unterprogramme, Subroutines
Daten
Rechenwerk
ALU
Programm
Central Processing Unit
CPU
2
Tröster
was unterscheidet diese Architektur von der einer
einfachen Rechenmaschine ?
• im Jahr 1945 hat John von Neumann eine Architektur
vorgeschlagen, deren Grundstruktur die Computertechnik
bis heute geprägt hat
Daten- und Befehlsbus
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
Speicher
> Programme können andere Programme erzeugen:
Compiler
Takt
Rückblick
• Programmablauf:
• 1950: erste Realisierung in Röhrentechnik
• 1958: die IBM704 mit (diskreten) Transistoren
• 1964: IBM System 360, erster Rechner mit ICs, 0.0018 bis 1.7
MIPS (iPhone 5S: 18200 MIPS)
• seit 1965: Minicomputer, z.B. DEC PDP-1, PDP-8
• 1971: intel 4004 erster 4-Bit 'Microprocessor Unit (MPU) mit
2300 Transistoren
• 1972: intel 8008 8 Bit-Prozessor
• 1975: intel 8080 (daraus 80x86 Familie)
• 1974: Motorola 6800 (daraus die 680x0 Familie)
• heute: Xeon (intel research), ca 2.3 Milliarden Transistoren
• Zukunft: 2022 werden Mikroprozessoren mit bis zu 25
Milliarden Transistoren erwartet
> das Steuerwerk holt aus dem Programmspeicher den
nächsten Befehl <fetch>
> ein Befehlswort besteht aus dem Instruktionsteil ('was soll
getan werden') und u.U. aus einer Datenadresse ('welche
Daten sollen manipuliert werden')
> der Befehl wird dekodiert und der ALU übergeben
> die ALU führt den Befehl aus <execute>, z.B. den Datenwert
um 1 Bit nach rechts schieben
> das Steuerwerk berechnet die nächste Adresse
> das Programm wird Befehl für Befehl abgearbeitet
Digitaltechnik
HS2015
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
Tröster
3
Digitaltechnik
HS2015
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
Tröster
4
Entwicklung Energieeffizienz
Entwicklung Rechenleistung
[aus http://download.intel.com/pressroom/pdf/computertrendsrelease.pdf]
Moore’sche Gesetz (ca 1970):
„die Prozessorleistung verdoppelt sich alle zwei
Jahre“
Gordon Moore 2007
Entwicklungszyklus (intel)
[aus
http://download.intel.com/pressroom/pdf/c
omputertrendsrelease.pdf]
Digitaltechnik
HS2015
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
5
Tröster
Digitaltechnik
HS2015
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
Befehlsausführung
Befehlsablauf
-
BR
BRC
BRA
ST
BZ
AR
SR
AK
6
Tröster
Decodieren des Befehlscodes (BRc  ST)
Auslesen des Operanden (SP  SR)
Ausführen der Operation (AK Op SR SR  AK)
Setzen des Bedingungsbits (ALU  ST)
Befehlsregister
Codeteil von BR
Adressteil von BR
Register für Steuerbits
Befehlszähler
Adressregister
Speicherregister
Akkumulator
aus Hans-Martin Lipp, Jürgen
Becker: Grundlagen der
Digitaltechnik, Oldenbourg
2008
Befehlsholphase
Digitaltechnik
HS2015
Adresse für den nächsten Befehl (FBR  AR)
Auslesen des adressierten Befehls (SP  SR)
Laden des Befehls (SR  BR)
Berechnen der nächsten Befehlsadresse (FBR+1  FBR)
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
Tröster
7
Digitaltechnik
HS2015
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
Tröster
8
eine wichtige Funktion: Interrupts
Pentium
Mikroarchitektur
• Erweiterung der 'von Neumann'-Architektur
• Frage:
> wie kann die Aussenwelt den Programmablauf
beeinflussen (z.B. durch Tastendruck)
> wie kann ein externes Signal in einen laufenden
Programmfluss eingeschleust werden
• in einer if-Schleife wird permanent abgefragt, ob ein Signal
von extern gesetzt ist
• Unterprogramm-Sprung:
nach jedem Befehl wird überprüft, ob ein Interrupt-Signal
anliegt, das die Verzweigung in Unterprogramm initiiert
RISC
 CISC
• CISC (complex instruction set computer):
komplexe und leistungsfähige Befehle, die prozessorintern
eine aufwendige (Mikro-)Kodierung verlangen und mehrere
Taktzyklen für die Ausführungen benötigen
AMD
K5
> Beispiele:
Intel 80x86, Motorola 680x0
• RISC (reduced instruction set computer);
der Befehlsatz enthält nur noch Befehle, die in einem
Taktzyklus ausgeführt werden; dadurch ist ein erheblich
höherer Durchsatz möglich
> Beispiele:
MIPS, Sun SPARC, DEC Alpha, ARM, XScale
http://en.wikipedia.org/wiki/ARM_architecture
Digitaltechnik
HS2015
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
9
Tröster
Digitaltechnik
HS2015
digitaler Signalprozessor DSP
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
10
Tröster
was kann ein leistungsfähiger DSP ?
• digitale Signalverarbeitung:
• z.B. der TMS320C6713 von TexasInstruments
'A Complete System-On-A-Chip'
> analoge Signale (Audio, Video) werden in binäre Zahlen
umgewandelt und weiterverarbeitet
• optimiert für hohe Rechengeschwindigkeit, Datendurchsatz
und Multiprozessing
> Algorithmen:
filtern, verstärken, kodieren, addieren, modulieren,
verschlüsseln, Fehler korrigieren, ...
• anspruchsvolle Anwendungen: Sprache, Klang, Graphik,
Bildverarbeitung, Kommunikation
• die Algorithmen der digitale Signalverarbeitung sind
gekennzeichnet durch die MAC-(Multiply/Acculumate)Funktion:
R  R + a.x
z.B. bei der die Vektor/Matrixmultiplikation
Blockdiagramm
• Signalprozessoren sind durch ihre Hardwarestruktur auf die
MAC-Operation hin optimiert:
in einem Takt wird die MAC-Operation ausgeführt
Beispiel Handy („Natel D“)
der Signalprozessor bewältigt die gesamte
Basisbandverarbeitung
Digitaltechnik
HS2015
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
Tröster
11
Digitaltechnik
HS2015
14. Mikroprozessor
ETH Zürich Institut für Elektronik (IfE)
Tröster
12

Orientierungstage SoSe 2016 Ev. Theol. Fakultät Münster

Achtung!!! Geänderte Sprechzeiten bei einigen Lehrkräften Stand

Kolloquiumsplan FS 2016

Physik und Unterricht

tefal vc 4003 user guide

2015-02-19 Offener Brief BF Erinnern Sie sich noch daran, dass wir

Auswahl Publikationen und Weiteres

Miniplan - Ministranten St. Josef Cham

Career Sandwich

Wir planen, entwickeln und fertigen die mechanischen