Technische Grundlagen der Informatik

Transcrição

Technische Grundlagen der
Informatik
WS 2008/2009
20. Vorlesung
Klaus Kasper
WS 2008/2009
1
Inhalt
• Wiederholung
– Hamming-Code
H
i C d
• Beispiel
– Cyclic Redundancy Code (CRC)
• Massenspeicher
– Magnetisch
– Optisch
O ti h
• Hazards
WS 2008/2009
2
Hamming-Distanz
Hamming
Distanz (h)
h=1, Erkennung: 0, Korrektur: 0
h 2 E
h=2,
Erkennung:
k
1
1, K
Korrektur:
kt 0
h 3 E
h=3,
Erkennung:
k
2
2, K
Korrektur:
kt 1
h=4 Erkennung: 3,
h=4,
3 Korrektur: 1
h=5 Erkennung: 4,
h=5,
4 Korrektur: 2
WS 2008/2009
3
Hamming-Distanz
g
Eine Codierung
g mit einer Hamming-Distanz
g
h erlaubt die Erkennung von h - 1 Bitfehlern
und (h
(h-1)/2
1)/2 Korrekturen,
Korrekturen wenn h ungerade ist,
ist
bzw. h/2 – 1 Korrekturen, wenn h gerade ist.
WS 2008/2009
4
Entropie, Redundanz
Entropie: H = ld(N), wobei N die Anzahl der
Nutzwörter bezeichnet
bezeichnet.
Redundanz: R = L – H,
H wobei L die mittlere
Länge der Codewörter bezeichnet.
Beispiel: Mit L = 5 und einer Codierung mit 4
Nutzwörtern kann eine Hamming-Distanz
Hamming Distanz von
3 realisiert werden. Ein einzelner Bitfehler kann
k i i t werden,
korrigiert
d
2 Bitf
Bitfehler
hl werden
d d
detektiert.
t kti t
R = 5 – ld(4) = 3
WS 2008/2009
5
Hamming Code
Hamming-Code
• Codes, die einen Fehler korrigieren
g
können,, werden auch als HammingCodes bezeichnet.
• Ein Hamming
Hamming-Code
Code hat eine Hamming
HammingDistanz h=3.
• Beispiel: Code mit n=7 Stellen,
Stellen m=4
Nutzbits, k=3 Prüfbits
WS 2008/2009
6
Prüfschema (gerade Parität)
Codewortstelle
x1
x2
x3
x4
x5
x6
x7
Bedeutung
g
P
P
N
P
N
N
N
Prüfgruppe a
X
Prüfgruppe b
X
X
X
Prüfgruppe c
Fehler
X
Prüfbedingung
Fehler
x1
x5
x2
x6
x3
x7
x4
kein
WS 2008/2009
X
X
X
X
X
X
X
Prüfbedingung
7
Prüfschema (gerade Parität)
Codewortstelle
x1
x2
x3
x4
x5
x6
x7
Bedeutung
g
P
P
N
P
N
N
N
Prüfgruppe a
X
Prüfgruppe b
X
X
X
X
X
Prüfgruppe c
X
X
X
X
X
X
Fehler
Prüfbedingung
Fehler
Prüfbedingung
x1
a
x5
a, c
x2
b
x6
b, c
x3
a, b
x7
a, b, c
x4
c
kein
WS 2008/2009
8
Codewörter (gerade Parität)
Nr.
1
2
3
4
5
6
7
Nr.
1
2
3
4
5
6
7
0
0
0
0
0
8
1
0
0
0
1
0
0
0
1
9
1
0
0
1
2
0
0
1
0
10
1
0
1
0
3
0
0
1
1
11
1
0
1
1
4
0
1
0
0
12
1
1
0
0
5
0
1
0
1
13
1
1
0
1
6
0
1
1
0
14
1
1
1
0
7
0
1
1
1
15
1
1
1
1
WS 2008/2009
Prüfbit 1 (1)
3 5
3,
5, 7
Prüfbit 2 (2)
3, 6, 7
Prüfbit 3 (4)
5, 6, 7
9
Nr.
1
2
3
4
5
6
7
Nr.
0
0
0
0
0
0
0
0
8
1
2
3
4
5
6
7
1
0
0
0
1
0
0
0
1
9
1
0
0
1
2
0
0
1
0
10
1
0
1
0
3
0
0
1
1
11
1
0
1
1
4
0
1
0
0
12
1
1
0
0
5
0
1
0
1
13
1
1
0
1
6
0
1
1
0
14
1
1
1
0
7
0
1
1
1
15
1
1
1
1
WS 2008/2009
P üfbit 1 (1)
Prüfbit
3 5
3,
5, 7
Prüfbit 2 (2)
3, 6, 7
Prüfbit 3 (4)
5 6
5,
6, 7
10
Nr.
1
2
3
4
5
6
7
Nr.
0
0
0
0
0
0
0
0
8
1
2
3
4
5
6
7
1
0
0
0
1
0
0
0
1
9
1
0
0
1
2
0
0
1
0
10
1
0
1
0
3
0
0
1
1
11
1
0
1
1
4
0
1
0
0
12
1
1
0
0
5
0
1
0
1
13
1
1
0
1
1
1
0
14
1
1
1
0
1
1
1
15
1
1
1
1
6
1
1
7
0
0
WS 2008/2009
0
Prüfbit 1 (1)
3, 5, 7
Prüfbit 2 (2)
3, 6, 7
Prüfbit 3 (4)
5, 6, 7
11
Nr.
1
2
3
4
5
6
7
Nr.
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
8
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
9
0
0
1
1
0
0
1
2
0
1
0
1
0
1
0
10
1
0
1
1
0
1
0
3
1
0
0
0
0
1
1
11
0
1
1
0
0
1
1
4
1
0
0
1
1
0
0
12
0
1
1
1
1
0
0
5
0
1
0
0
1
0
1
13
1
0
1
0
1
0
1
6
1
1
0
0
1
1
0
14
0
0
1
0
1
1
0
7
0
0
0
1
1
1
1
1
15
1
1
1
1
1
1
1
WS 2008/2009
Prüfbit 1 (1)
3, 5, 7
Prüfbit 2 (2)
3, 6, 7
Prüfbit 3 (4)
5, 6, 7
12
Beispiel (gerade Parität)
gesendetes Codewort: 0011001
empfangenes Wort: 0011101 (Bit 5 gestört)
Prüfbit 1 falsch
Prüfbit 2 korrekt
Prüfbit 3 falsch
101
WS 2008/2009
Prüfbit 1 (1)
3, 5, 7
Prüfbit 2 (2)
3, 6, 7
Prüfbit 3 (4)
5 6
5,
6, 7
13
Übung (gerade Parität)
Empfangene Bitfolge:
0001001
Analyse?
Prüfbit 1 (1)
3, 5, 7
Prüfbit 2 (2)
3, 6, 7
Prüfbit 3 (4)
5, 6, 7
Prüfbit 1: f
Prüfbit 2: f
-> 011 -> Korrektur:
WS 2008/2009
Prüfbit 3: ok
0011001
14
Übung (gerade Parität)
Nr
Nr.
1
2
3
4
5
6
7
Nr.
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
8
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
9
0
0
1
1
0
0
1
2
0
1
0
1
0
1
0
10
1
0
1
1
0
1
0
3
1
0
0
0
0
1
1
11
0
1
1
0
0
1
1
4
1
0
0
1
1
0
0
12
0
1
1
1
1
0
0
5
0
1
0
0
1
0
1
13
1
0
1
0
1
0
1
6
1
1
0
0
1
1
0
14
0
0
1
0
1
1
0
7
0
0
0
1
1
1
1
15
1
1
1
1
1
1
1
Prüfbit 1 (1)
3, 5, 7
Prüfbit 2 (2)
3, 6, 7
Prüfbit 3 (4)
5, 6, 7
Empfangene Bitfolge:
0001001
Analyse?
Prüfbit 1: f Prüfbit 2: f Prüfbit 3: ok
->
> 011 ->
> Korrektur: 0011001
WS 2008/2009
15
Fazit: Hamming-Code
Soll in einem n-stelligen Code ein
Fehler korrigiert werden, so müssen mit
den k Prüfbits n+1 Informationen
dargestellt werden.
2 ≥ n +1 = 1+ m + k
k
k ≥ ld(n + 1)
WS 2008/2009
16
Error Controlling and Correcting
(ECC) für RAMs
• 2-Bit-Fehler
e e können
ö e de
detektiert
e e werden
e de
• 1-Bit-Fehler können korrigiert werden
• es werden typischerweise 8 zusätzliche
p
benötigt
g ((72 statt 64))
Datenpins
• Die Wahrscheinlichkeit, dass ein 2-BitFehler auftritt wird als äußerst gering
angenommen, so dass mit dem Einsatz
von ECC B
Bausteinen
t i
eine
i sehr
h h
hohe
h
Sicherheit erreicht werden kann.
WS 2008/2009
17
Cyclic Redundancy Code (CRC)
• Zyklischer Redundanzcode, Polynomcode
• Für jede Nachricht N wir eine Prüfsumme
P berechnet und mit N zu N* zusammengefasst.
gefasst
• P wird mit einem Generatorpolynom
p y
G der
Ordnung g berechnet.
• N wird mit g 0
0-Bits
Bits zu N
N* ergänzt.
ergänzt
• N* wird durch G geteilt.
• Der Rest der Division wird von N*
subtrahiert
WS 2008/2009
18
CRC (Fortsetzung)
• N* ist nun durch G ohne Rest teilbar.
• Auf der Empfängerseite kann dies über
überprüft werden, da auch hier G bekannt ist.
• Mit der Entfernung von P erhält der
Empfänger die ursprüngliche Nachricht N.
• Mit dem CRC-Verfahren können Fehler
detektiert aber nicht korrigiert werden.
• Wird das Verfahren mit Paritätsbits ergänzt kann auch eine Korrektur durch
durchgeführt werden.
WS 2008/2009
19
CRC (Durchführung)
• Berechnung erfolgt ohne Berücksichtigung von
Überträgen
g ((algebraische
g
Feldtheorie Modulo-2).
)
• Berechnung kann einfach in Hardware realisiert werden.
• Generatorpolynome werden so konstruiert, dass
bestimmte Fehlerklassen detektiert werden können
können.
Bezeichnung
Polynom
Anwendung
CRC-12
x12+x11+x3+x2+x1+1
6 Bit Werte
CRC 16
CRC-16
x16+x15+x2+1
1
8 Bit W
Werte
t
CRC-CCITT
x16+x12+x5+1
8 Bit Werte
CRC-32
CRC
32
x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x
4+x2+x1+1
Internet
WS 2008/2009
20
Massenspeicher
• Um große Datenmengen zu speichern,
werden periphere (sekundäre) Speicher
verwendet.
• Magnetische Massenspeicher (Floppy,
Festplatte Magnetband)
Festplatte,
• Optische Massenspeicher (CD, DVD)
• Magnetooptische Laufwerke (MO)
WS 2008/2009
21
Prinzip der magnetischen
Aufzeichnung
• Phänomene: Diamagnetismus,
Paramagnetismus Ferromagnetismus
Paramagnetismus,
• auf dem Ferromagnetismus basiert das Prinzip
der magnetischen Speicherung
• die Weiß‘schen Bezirke eines ferromagnetischen Materials werden durch ein
äußeres magnetisches Feld ausgerichtet
• nach Entfernen des äußeren Feldes bleibt die
makroskopische Magnetisierung erhalten
WS 2008/2009
22
Hystereseschleife
WS 2008/2009
23
Ferromagnete
• nach Entfernen des äußeren magnetischen
Feldes bleibt eine Magnetisierung erhalten,
die als Remanenz bezeichnet wird
g Entmagnetisierung
g
g muss
• für die vollständige
ein entgegen gesetztes Magnetfeld angelegt
werden,, das mit einer Stärke angelegt
g g
werden, die als Koerzivität bezeichnet wird
Curie Temperatur verschwinden die
• bei der Curie-Temperatur
ferromagnetischen Eigenschaften schlagartig
WS 2008/2009
24
Prinzip der Speicherung
• Zur Speicherung der Daten werden die
magnetischen Speichermedien in
g
Gebiete eingeteilt.
• Die Gebiete speichern jeweils ein Bit.
• Durch
D h di
die A
Ausrichtung
i ht
d
des G
Gebietes
bi t
wird die Wertigkeit des zugeordneten
Bits codiert.
WS 2008/2009
25
Durchführung von Lesen und
Schreiben
• Bei konstantem Stromfluss durch eine
Spule wird ein Magnetfeld erzeugt
(Elektromagnet).
(Elektromagnet)
• Mit einem Elektromagneten können die
Daten eingeschrieben werden.
• Ein sich veränderndes Magnetfeld
g
induziert eine elektrische Spannung.
• Zum Auslesen wird der
Spannungsverlauf ausgewertet.
WS 2008/2009
26
Speichermedien
• Magnetbänder: sequentieller Zugriff,
Backup, Streamer, langsamer Zugriff
• Magnetplatten: zweidimensionale
J ti
Justierung
d
des S
Schreib-/Lesearms,
h ib /L
Speicherung großer Datenmengen,
Festplatten, (Floppy), schneller Zugriff
WS 2008/2009
27
Prinzip der magnetischen
Speicherung
p
g
WS 2008/2009
28
Optimierung
p
g
• möglichst kleiner Spalt und geringer Abstand
zwischen Schreib-/Lesekopf
Schreib /Lesekopf damit kleine
Gebiete magnetisiert werden können
• in Diskettenlaufwerken schleift der Kopf direkt
auf der Oberfläche
• bei Festplatten fliegt der Kopf über die Platte
• der Abstand wird über ein Luftpolster realisiert
WS 2008/2009
29
Organisation von Festplatten
• Festplatten
p
sind aus einem Plattenstapel
p
aufgebaut.
• Jeder Kopf arbeitet auf einer Oberfläche.
• Jede Oberfläche ist in konzentrische Kreise
aufgeteilt, die als Spuren oder Tracks
bezeichnet werden
werden.
• Die äquivalenten Spuren auf allen Oberflächen
werden als Zylinder bezeichnet
bezeichnet.
• Die Spuren sind in Sektoren eingeteilt.
• Sektoren sind die kleinste Einheit
Einheit, die gelesen
und geschrieben werden können (bspw. 512
Bytes).
WS 2008/2009
30
Beispiel
Seagate Cheetah 36
• 3,5 Inch Disk
• 36,4
36 4 GByte
GB t Kapazität
K
ität
• 10.000 Umdrehungen/Minute
• 18,3 bis 28 MByte/s interne
Datentransferrate
• 9.772 Zylinder (Spuren)
• 71.132.960 Sektoren insgesamt
g
• Mittlere Zugriffszeiten:
Lesen 5.2 ms,
Schreiben 6
6,0
0 ms
WS 2008/2009
31
Prinzip
p der optischen
p
Speicherung
p
g
WS 2008/2009
32
Optische Speicherung
• Halbleiterlaser tastet Oberfläche der CDROM ab.
• Im Grundzustand reflektiert die Oberfläche
den Strahl ohne signifikante Streuung.
• Zur Datenspeicherung werden in die
Oberfläche kleine Vertiefungen eingebracht,
di als
die
l Pit b
bezeichnet
i h t werden.
d
• Jeder Übergang von Pit zur nicht veränderten
Oberfläche die als Land be
Oberfläche,
bezeichnet
eichnet wird,
ird
kann detektiert werden.
WS 2008/2009
33
CD R(ecordable)
CD-R(ecordable)
• Einsatz einer organischen Schicht zur
Veränderung der
Reflektionseigenschaften des Mediums.
• Bei Erhitzung durch den Schreiblaser
g Blasen,, die die
bilden sich winzige
Reflektionseigenschaften verändern.
• Der Schreibvorgang ist irreversibel
irreversibel.
WS 2008/2009
34
CD-ReWritable (CD-RW)
(
)
• Die Reflektionseigenschaften werden mit Hilfe einer
Phasenwechselschicht manipuliert.
• Hier wird die Kristallstruktur des des Materials
verändert.
ä d t
• Mit dem Laser wird ein kleiner Bereich auf 600 Grad
Celsius erhitzt
erhitzt.
• Bei sehr schneller Abkühlung wird die Ausbildung
einer kristallinen Struktur verhindert.
• Die kristalline Struktur kann durch eine mittlere
Temperatur, die eine Ausrichtung der Atome erlaubt,
wieder
ieder hergestellt werden.
erden
• DVDs arbeiten nach ähnlichen Prinzipien wie CDs.
WS 2008/2009
35
Magnetooptische
g
p
Laufwerke
• Das Prinzip der Beeinflussung der Polarisation
elektromagnetischer
g
Wellen durch Magnetfelder
g
wird
ausgenutzt.
• Die Polarisierung von linear polarisiertem Licht kann
durch Polarisationsfilter ermittelt werden
werden.
• Das Speichermedium ist ein Ferromagnetikum.
• Zum Speichern
p
wird das Ferromagnetikum
g
auf die CurieTemperatur erwärmt und die Elementarmagnete
anschließend mit Hilfe eines äußeren Magnetfeldes
g
ausgerichtet.
• MO-Medien sind sehr sicher, da Ferromagnetika
verwendet werden, die unterhalb der Curie-Temperatur
nicht magnetisiert werden können
können.
• Zur Löschung der Daten wird gleichzeitig eine hohe
Temperatur und ein Magnetfeld benötigt.
WS 2008/2009
36
Hazards
• Kurzzeitige und unerwartete Änderungen
Ä
g
g
der Werte auf Signalleitungen.
• Eine Schaltung, die eine Gefahr (Hazard)
enthält hat das Potential einen Störimpuls
enthält,
von kurzer Dauer (Glitch) zu produzieren.
• Hazards können zu instabilem Verhalten in
g führen und müssen daher
Schaltungen
schon beim Entwurf vermieden werden.
WS 2008/2009
37
Typisierung von Hazards
erwartet
gestört
negativer statischer
Hazard
positiver statischer
Hazard
dynamischer Hazard
WS 2008/2009
38
Entstehung von Hazards
• Unterschiedliche Laufzeiten von
Signalen in der Schaltung, die später
kombiniert werden.
• Als gleichzeitig angenommene
Signaländerungen werden real
zeitversetzt ausgeführt.
WS 2008/2009
39
Logik-Hazards (kombinatorisch)
• Ein Eingangssignal verzweigt in der
S h lt
Schaltung.
• In einem später zu durchlaufenden Gatter
werden die zuvor verzweigten Signale wieder
kombiniert.
• Wenn auf den unterschiedlichen
Signalpfaden
g p
unterschiedliche Laufzeiten
benötigt werden, kann es zu Störimpulsen
kommen.
WS 2008/2009
40
Beispiel
X3
0
0
0
0
1
1
1
1
X2
0
0
1
1
0
0
1
1
X1
0
1
0
1
0
1
0
1
Y
0
1
0
1
1
1
0
0
Übergang von 101 zu 001
WS 2008/2009
PI1 = X 1 ∧ X 3
PI 2 = X 2 ∧ X 1
PI 3 = X 2 ∧ X 3
41
Beispiel (Fortsetzung)
WS 2008/2009
Annahme
A
h
(L
(Laufzeiten):
f it )
und/oder: 4ns
Negation: 2ns
42
Beispiel (Lösung)
WS 2008/2009
43
Vermeiden von Logik-Hazards
• Erzeugung Minimalform
• Wenn bei dem Übergang einer
Komponente der aktive Primimplikant
gewechselt wird, kann ein redundanter
Primimplikant hinzugefügt werden
werden, so
dass der Übergang eliminiert wird.
• Einsatz von getakteten Schaltungen
WS 2008/2009
44
funktionale Hazards
• Kann bei gleichzeitigem Signalwechsel
an mehreren Eingängen auftreten.
• Mehrkomponentenwechsel
Mehrkomponentenwechsel.
• Das Ergebnis hängt von dem Ausgang
d W
des
Wettlaufs
ttl f ab.
b
• Dies kann zu Fehlfunktionen im System
führen.
WS 2008/2009
45
Vermeiden von funktionalen
Hazards
• Überführung von MehrkomponentenMehrkomponenten
übergängen in mehrere
Einkomponentenübergänge
• Einsatz von synchronen Schaltungen
WS 2008/2009
46
Fazit Hazards
• Bei komplexen asynchronen Schaltungen
i di
ist
die W
Wahrscheinlichkeit
h h i li hk i fü
für Hazards
H
d
hoch.
• Analyse von asynchronen Schaltungen
bezüglich Hazards ist aufwendig
aufwendig.
WS 2008/2009
47

Technische Grundlagen der Informatik

Transcrição

Documentos relacionados

Thema: „Hamming-Codes“ Titelblatt anonymisiert

Inhaltsverzeichnis TEIL A GEFAHRSTOFFE IN DER APOTHEKE

3. Hard- und Orgware

Handout Prüfgruppe Handwaffen ( PDF , 61,1 kB)

Richtlinie des Landesschaf- und Ziegenzuchtverbandes

leben lernen mit der sucht

LCS-GS8116

Der Radarführungsdienst nach 1990

CRC Einführung

newsletter - CRC 649 - Hu