Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Beispiele für die Bedeutung eines n-bit-Wortes: • Befehl (instruction) • Zahl (number) • Zeichen (character) • Bildelement (pixel)
Codes (1)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
DEZ HEX Zeichen DEZ HEX Zeichen DEZ HEX Zeichen DEZ HEX Zeichen 00 00 NUL 32 20 SP 64 40 @ 96 60 ` 01 01 SOH 33 21 ! 65 41 A 97 61 a 02 02 STX 34 22 " 66 42 B 98 62 b 03 03 ETX 35 23 # 67 43 C 99 63 c 04 04 EOT 36 24 $ 68 44 D 100 64 d 05 05 ENQ 37 25 % 69 45 E 101 65 e 06 06 ACK 38 26 & 70 46 F 102 66 f 07 07 BEL 39 27 ' 71 47 G 103 67 g 08 08 BS 40 28 ( 72 48 H 104 68 h 09 09 HT 41 29 ) 73 49 I 105 69 i 10 0A LF 42 2A * 74 4A J 106 6A j 11 0B VT 43 2B + 75 4B K 107 6B k 12 0C FF 44 2C , 76 4C L 108 6C l 13 0D CR 45 2D - 77 4D M 109 6D m 14 0E SO 46 2E . 78 4E N 110 6E n 15 0F SI 47 2F / 79 4F O 111 6F o 16 10 DLE 48 30 0 80 50 P 112 70 p 17 11 DC1 49 31 1 81 51 Q 113 71 q 18 12 DC2 50 32 2 82 52 R 114 72 r 19 13 DC3 51 33 3 83 53 S 115 73 s 20 14 DC4 52 34 4 84 54 T 116 74 t 21 15 NAK 53 35 5 85 55 U 117 75 u 22 16 SYN 54 36 6 86 56 V 118 76 v 23 17 ETB 55 37 7 87 57 W 119 77 w 24 18 CAN 56 38 8 88 58 X 120 78 x 25 19 EM 57 39 9 89 59 Y 121 79 y 26 1A SUB 58 3A : 90 5A Z 122 7A z 27 1B ESC 59 3B ; 91 5B [ 123 7B { 28 1C FS 60 3C < 92 5C \ 124 7C | 29 1D GS 61 3D = 93 5D ] 125 7D } 30 1E RS 62 3E > 94 5E ^ 126 7E ~ 31 1F US 63 3F ? 95 5F _ 127 7F DEL
ASCII (bzw, ISO 7-bit) – Zeichencode
Codes (2)
DEZ
HEX
Zeichen
DEZ
HEX
Zeichen
DEZ
HEX
Zeichen
DEZ
HEX
Zeichen
00
00
NUL
32
20
SP
64
40
@
96
60
`
01
01
SOH
33
21
!
65
41
A
97
61
a
02
02
STX
34
22
"
66
42
B
98
62
b
03
03
ETX
35
23
#
67
43
C
99
63
c
04
04
EOT
36
24
$
68
44
D
100
64
d
05
05
ENQ
37
25
%
69
45
E
101
65
e
06
06
ACK
38
26
&
70
46
F
102
66
f
07
07
BEL
39
27
'
71
47
G
103
67
g
08
08
BS
40
28
(
72
48
H
104
68
h
09
09
HT
41
29
)
73
49
I
105
69
i
10
0A
LF
42
2A
*
74
4A
J
106
6A
j
11
0B
VT
43
2B
+
75
4B
K
107
6B
k
12
0C
FF
44
2C
,
76
4C
L
108
6C
l
13
0D
CR
45
2D
-
77
4D
M
109
6D
m
14
0E
SO
46
2E
.
78
4E
N
110
6E
n
15
0F
SI
47
2F
/
79
4F
O
111
6F
o
16
10
DLE
48
30
0
80
50
P
112
70
p
17
11
DC1
49
31
1
81
51
Q
113
71
q
18
12
DC2
50
32
2
82
52
R
114
72
r
19
13
DC3
51
33
3
83
53
S
115
73
s
20
14
DC4
52
34
4
84
54
T
116
74
t
21
15
NAK
53
35
5
85
55
U
117
75
u
22
16
SYN
54
36
6
86
56
V
118
76
v
23
17
ETB
55
37
7
87
57
W
119
77
w
24
18
CAN
56
38
8
88
58
X
120
78
x
25
19
EM
57
39
9
89
59
Y
121
79
y
26
1A
SUB
58
3A
:
90
5A
Z
122
7A
z
27
1B
ESC
59
3B
;
91
5B
[
123
7B
{
28
1C
FS
60
3C
p class="standard"92/p
p class="standard"5C/p
p class="standard"\/p
p class="standard"124/p
p class="standard"7C/p
p class="standard"|/p
p class="standard"29/p
p class="standard"1D/p
p class="standard"GS/p
p class="standard"61/p
p class="standard"3D/p
p class="standard"=/p
p class="standard"93/p
p class="standard"5D/p
p class="standard"]/p
p class="standard"125/p
p class="standard"7D/p
p class="standard"}/p
p class="standard"30/p
p class="standard"1E/p
p class="standard"RS/p
p class="standard"62/p
p class="standard"3E/p
p class="standard">
94
5E
^
126
7E
~
31
1F
US
63
3F
?
95
5F
_
127
7F
DEL
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Erweiterungen des ASCII-Codes: • ISO 646 (Latin-1) • ISO 8859 (code pages)
– ISO 8859-1 (Latin-1, Westeuropa) – ISO 8859-2 (Latin-2, Zentral- und Osteuropa, slawische
Sprachen) – ISO 8859-3 (Latin-3, Südeuropa, z.B. türkisch, maltesisch,
Esperanto) – ISO 8859-4 (Latin-4, Nordeuropa, z.B. baltische Sprachen) – ISO 8859-5 (Kyrillisch, z.B. Bulgarisch, Russisch, Serbisch) – ...
• ISO 10646 (Unicode)
Codes (3)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Unicode • 65,536 code points • enthält Latin-1 als Untermenge (336 code points) • weitere Sprachenbeispiele:
– griechisch (144), kyrillisch (256), armenisch (96), hebräisch (112) • code points für Sonderzeichen:
– z.B. Indizes (48), Währungssymbole (48), math. Symbole (256) • Symbole für chinesisch, japanisch, koreanisch • 6,400 code points frei definierbar für den lokalen Gebrauch • steigende Akzeptanz, wird schon unterstützt von einigen
Programmiersprachen (Java) und Betriebssystemen (Windows NT … Windows 8, Linux, Mac OSX)
Codes (4)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Beispiel für die Verwendung von graphischen Symbolen (Teletext):
Zeichensatztabelle (westeuropäische Sprachen) für den Videotext Decoder SAA5281 (Philips)
Codes (5)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Bit-map: • Transformation eines Bildes in ein rechteckiges Feld mit Bildpunkten
(Pixel) • Pixel: kleinste Bildinformationseinheit (Analogie zu bit) • Pixel kann Attribute besitzen (z.B. Farbe) • sehr kapazitätsintensiv (Speicher, Bandbreite) • komplexe Komprimierungstechniken (z.B. MPEG zur Bildübertragung)
Codes (6)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Distanz zwischen 2 Binärworten
Der 4-bit GRAY CODE
0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1
1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0
1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0
Dezimal- wert
Binär- wert
Gray- code
Dezimal- wert
Binär- wert
Gray- code
0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 x 1
0 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0 x x x 3
0 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 x x 2
0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 x 1
Wort 1 Wort 2 Unterschied Hamming-Abstand
Der Hamming-Abstand ist einfach die Anzahl von Positionen, in denen sich zwei binäre Folgen unterscheiden.
Codes (7)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Optischer Codierer mit BINÄR CODES
Optischer Codierer mit GRAY CODES
transparent - logisch 1
undurchsichtig - logisch 0
Licht-detektoren
Licht-quellen
binäre Ausgänge
Sektor Winkel Binärcode
0 1 2 3 4 5 6 7
0-45 45-90
90-135 135-180 180-225 225-270 270-315 315-360
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Sektor Winkel Graycode
0 1 2 3 4 5 6 7
0-45 45-90
90-135 135-180 180-225 225-270 270-315 315-360
0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0
Codes (8)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Umwandlung Binär Codes in Gray Codes Umwandlung Gray Codes in Binär Codes
Codes (9)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (10)
Beispiel einer Codierscheibe
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Fehlererkennende (EDC) bzw. fehlerkorrigierende Codes (ECC) Einsatz von ECCs insbesondere bei: • stark gestörten Übertragungswegen • militärische Datenübertragungen auf Funkwegen • bei Computerspeichern, um Lesefehler ohne Wiederholvorgang zu beheben
z.B. ECC-RAM, CD, Plattenspeicher Definitionen: Codewort ∶= mit zusätzlichen (redundanten) Kontrollbits versehenes Quellwort 𝑚𝑚 ≔ Länge des Quellwortes (Anzahl der Nutzdatenbits) 𝑟𝑟 ≔ Anzahl der Kontrollbits 𝑛𝑛 = 𝑚𝑚 + 𝑟𝑟 ∶= Länge des Codewortes Ein binärer Code ist eine Teilmenge von 𝑅𝑅𝑛𝑛2. Seine Elemente können auch als Codevektoren (Spaltenvektoren) aufgefasst werden
Codes (11)
m r
Codewort
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Hammingdistanz: Seien 𝑥𝑥 und 𝑦𝑦 Codewörter im 𝑅𝑅𝑛𝑛2. Dann heißt die Funktion
d 𝑥𝑥,𝑦𝑦 = ∑ 𝑥𝑥𝑖𝑖 + 𝑦𝑦𝑖𝑖 mit 𝑖𝑖 = 1, … . . ,𝑛𝑛
Hammingdistanz von 𝑥𝑥 und 𝑦𝑦.
Hammingdistanz eines Codes:
Sei 𝐶𝐶 ⊆ 𝑅𝑅𝑛𝑛2 ein Code. Dann ist
d(𝐶𝐶) ∶= min (d(𝑥𝑥,𝑦𝑦) | 𝑥𝑥,𝑦𝑦 ∈ 𝐶𝐶 ⋀ 𝑥𝑥 ≠ 𝑦𝑦)
Die Hammingdistanz des gesamten Codes (Menge aller Codewörter), d.h. gleich der minimalen Hammingdistanz zwischen beliebigen 2 beliebigen Codewörtern dieses Codes.
Hammingdistanz als Metrik: Seien 𝑥𝑥,𝑦𝑦 Elemente der Menge 𝑂𝑂, mit d:𝑂𝑂 × 𝑂𝑂 → 𝑂𝑂 eine Funktion auf 𝑂𝑂. d heißt Metrik, wenn die Axiome der Metrik für alle 𝑥𝑥,𝑦𝑦, 𝑧𝑧 ∈ 𝑂𝑂 gelten:
d 𝑥𝑥,𝑦𝑦 ≥ 0 und aus d 𝑥𝑥,𝑦𝑦 = 0 folgt 𝑥𝑥 = 𝑦𝑦 Nichtnegativität d 𝑥𝑥,𝑦𝑦 = d 𝑦𝑦, 𝑥𝑥 Symmetrie d 𝑥𝑥,𝑦𝑦 ≤ d 𝑥𝑥, 𝑧𝑧 + d 𝑧𝑧,𝑦𝑦 Dreiecksungleichung
die Hammingdistanz d ist eine Metrik auf 𝑅𝑅𝑛𝑛2 .
Codes (12)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Prüfbarkeit auf p-Bit-Fehler: Sei 𝐶𝐶 ⊆ 𝑅𝑅𝑛𝑛2 ein Code. 𝐶𝐶 heißt auf 𝑝𝑝-Bit-Fehler prüfbar wenn für jedes 𝑥𝑥 aus 𝐶𝐶 gilt:
K 𝑥𝑥,𝑦𝑦 ⋂ 𝐶𝐶 = 𝑥𝑥 wobei K 𝑥𝑥,𝑦𝑦 = 𝑦𝑦 | d 𝑦𝑦, 𝑥𝑥 ≤ 𝑝𝑝
𝐶𝐶 ist auf 𝑝𝑝-Bit-Fehler prüfbar genau dann wenn für alle 𝑥𝑥,𝑦𝑦 aus 𝐶𝐶 gilt: d 𝑥𝑥,𝑦𝑦 ≥ 𝑝𝑝 + 1 Korrigierbarkeit von p-Bit-Fehlern: 𝐶𝐶 heißt auf 𝑝𝑝-Bit-Fehler korrigierbar, wenn für alle 𝑥𝑥,𝑦𝑦 aus 𝐶𝐶 gilt:
K 𝑥𝑥,𝑝𝑝 ⋂ K 𝑦𝑦,𝑝𝑝 =
𝐶𝐶 ist auf 𝑝𝑝-Bit- Fehler korrigierbar genau dann wenn für alle 𝑥𝑥,𝑦𝑦 aus 𝐶𝐶 gilt: d(𝑥𝑥,𝑦𝑦) ≥ 2𝑝𝑝 + 1
Codes (13)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Veranschaulichung des Codeprinzips:
räumliche Darstellung von Codes:
Codes (14)
000 001
010
100 101
110 111
011
000 001
010
100 101
110 111
011
Ungültiges CodewortGültiges Codewort
2 mögliche Codewörtern
2 gültige Codewörterm
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Paritätscode mit geraden und ungeraden Paritäten:
Nachricht Codewort (gerade Parität)
Codewort (ungerade Parität)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
0 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1
1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1
gerades Paritätsbit (even)
ungerades Paritätsbit (odd)
Codes (15)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Paritätscode für einen Block von Quellworten (geblockter Paritätscode):
D0 D1 D2
0 1 1
1 0 1
1 0 0
0 1 1
1 0 1
0 1 0
D0 D1 D2 D3
0 1 1 0
1 0 1 0
1 0 0 1
0 1 1 0
1 0 1 0
0 1 0 1
1 1 0 0
Bit Wort 1 Wort 2 Wort 3 Wort 4 Wort 5 Wort 6 Wort 7
Bit Wort 1 Wort 2 Wort 3 Wort 4 Wort 5 Wort 6
Vertikale Paritätsbits
Horizontale Paritätswort
Codes (16)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
D0 D1 D2 D3
0 1 1 0
1 0 1 0
1 1 0 1
0 1 1 0
1 0 1 0
0 1 0 1
1 1 0 0
Bit Wort 1 Wort 2 Wort 3 Wort 4 Wort 5 Wort 6 Wort 7
ok ok ok ok ok ok X
ok X ok ok
Durch Erkennung des Paritätsfehlers in einer Zeile kann die fehlerhafte Bitposition gefunden werden (z.B. D1.). Durch Erkennung eines Paritätsfehlers in einer Spalte kann das fehlerhafte Wort gefunden erkannt werden (z.B. Wort 3). Nun kann der Fehler lokalisiert werden: Bit D1 im Wort 3.
Paritätscode für einen Block von Quellworten (geblockter Paritätscode):
Codes (17)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Anzahl der benötigten Kontrollbits für einen Einfach-ECC:
Wortbreite Prüfbits Gesamtgröße Overhead in %
8 16 32 64
128 256 512
4 5 6 7 8 9
10
12 21 38 71
136 265 522
50 31 19 11 6 4 2
Codes (18)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Kurzdarstellung des Hamming-Algorithmus: 1. Kodierung auf der Sender (Schreib-)seite: • Die Bits des Codewortes werden von 1 bis 𝑛𝑛 (𝑛𝑛 = 𝑚𝑚 + 𝑟𝑟) durchnummeriert,
wobei die Positionsnummer als binäres Polynom dargestellt wird. • Als 𝑟𝑟 Kontrollbits 𝑝𝑝𝑖𝑖 werden jene Bits verwendet, deren Positionsnummer eine
Zweierpotenz darstellt, also die Bits 𝑖𝑖 = 1,2,4, … , 2𝑛𝑛−1 . • Die restlichen Bits mit den Positionsnummern 3,5,6,7,9 … werden mit den 𝑚𝑚
Datenbits 𝑑𝑑𝑖𝑖 an der Position 𝑥𝑥𝑖𝑖 belegt. • Die Kontrollbits dienen als Paritätsbits. Das Kontrollbit 𝑝𝑝𝑖𝑖 stellt die Parität aller
Nutzdatenbits 𝑑𝑑𝑖𝑖 mit 𝑥𝑥𝑖𝑖 = 1 her, deren 𝑖𝑖-ter Polynomial-Koeffizient (Positionsnummer an der Stelle 𝑖𝑖) eine 1 enthält.
1 𝑝𝑝0 0 0 1
2 𝑝𝑝1 0 1 0
3 𝑑𝑑0 0 1 1
4 𝑝𝑝2 1 0 0
5 𝑑𝑑1 1 0 1
6 𝑑𝑑2 1 1 0
7 𝑑𝑑3 1 1 1
𝑝𝑝2 = 𝑑𝑑3 xor 𝑑𝑑2 xor 𝑑𝑑1 𝑝𝑝1 = 𝑑𝑑3 xor 𝑑𝑑2 xor 𝑑𝑑0 𝑝𝑝0 = 𝑑𝑑3 xor 𝑑𝑑1 xor 𝑑𝑑0
22 21 20
𝑥𝑥𝑖𝑖
Polynomial- Koeffizienten
Bit-Nr.
Zuordnung
Codes (19)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Kurzdarstellung des Hamming-Algorithmus: 2. Fehlerkontrolle auf der Empfängerseite / Leseseite: • Auf der Basis des vorliegenden Codewortes werden erneut nach der
gleichen Regel wie oben Kontrollbits 𝑝𝑝𝑖𝑖∗ erzeugt • Es wird das Syndrom 𝑆𝑆 gebildet, wobei 𝑆𝑆𝑖𝑖 = 𝑝𝑝𝑖𝑖 xor 𝑝𝑝𝑖𝑖∗ für 𝑖𝑖 = 1,2,4, … , 2𝑛𝑛−1. • Ist das zu kontrollierende Codewort fehlerfrei 𝑆𝑆 = 0 • Existiert genau ein Fehler 𝑆𝑆 als Binärzahl gelesen identifiziert die
Positionsnummer des zu korrigierenden Bits.
Codes (20)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Prinzipielle Idee hinter dem Hamming-Algorithmus:
A B
C
Codes (21)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
p0 p1
p2
d3
d2 d1
d0
Prinzipielle Idee hinter dem Hamming-Algorithmus:
Codes (22)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Beispiel:
Paritätsbit 1 falsch (1,3,5,7,9,11,13,15,17,19,21 enthalten zusammen 5 Einsen) Paritätsbit 2 richtig (2,3,6,7,10,11,14,15,18,19, enthalten zusammen 6 Einsen) Paritätsbit 4 falsch (4,5,6,7,12,13,14,15,20,21 enthalten zusammen 5 Einsen) Paritätsbit 8 richtig (8,9,10,11,12,13,14,15 enthalten zusammen 2 Einsen) Paritätsbit 16 richtig (16,17,18,19,20,21 enthalten zusammen 4 Einsen)
20 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0
Paritäts-Bits
Codiertes Wort: 1111000010101110
Codes (23)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (23a)
Bitposition 1 2 3 4 5 6 7 Kontrollbits p0 p1 p2 Datenbits c0 c1 c2 c3
• Durchnumerieren der Bit-Positionen beginnend mit 1 • Markieren der Kontrollbit-Positionen an den Stellen 20 bis 2r, also 1,
2, 4, 8 ... • Auffüllen der restlichen (freien) Positionen durch Datenbits
Beispiel zum Erzeugen einer Hamming-Codierung
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (23b)
Bitposition 1 2 3 4 5 6 7 Kontrollbits p0 p1 p2 Datenbits c0 c1 c2 c3 Datencode: 0 1 1 0
• Eintragen der zu übertragenden Datenbits
Beispiel zum Prüfen einer Hamming-Codierung
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (23c)
Bitposition 1 2 3 4 5 6 7 Kontrollbits p0 p1 p2 Datenbits c0 c1 c2 c3 Datencode: 0 1 1 0 für p0: 1 0 1 0 1 0 1 für p1: 0 1 1 0 0 1 1 für p2: 0 0 0 1 1 1 1
• Eintragen der Polynolialcodes für jede Bit-Nr. zur Gruppierung von Kontroll- und Datenbits
• Alle mit 1 markierten Positionen gehören zu einer Gruppe
Beispiel zum Prüfen einer Hamming-Codierung
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (23d)
Bitposition 1 2 3 4 5 6 7 Kontrollbits p0 p1 p2 Datenbits c0 c1 c2 c3 Datencode: 0 1 1 0 für p0: 0 1 0 für p1: 0 1 0 für p2: 1 1 0
• Übertragen der bekannten Datenbits an die vorher markierten Positionen
Beispiel zum Prüfen einer Hamming-Codierung
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (23e)
Bitposition 1 2 3 4 5 6 7 Kontrollbits p0 p1 p2 Codebits c0 c1 c2 c3 Datencode: 0 1 1 0 für p0: 1 0 1 0 für p1: 1 0 1 0 für p2: 0 1 1 0 Ergebnis: 1 1 0 0 1 1 0
• Ein Kontrollbit wird so gesetzt, dass die Anzahl der gesetzten Bits des kontrollierten Bereiches gerade ist.
Beispiel zum Prüfen einer Hamming-Codierung
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (23f)
Bitposition 1 2 3 4 5 6 7 Kontrollbits p0 p1 p2 Datenbits c0 c1 c2 c3 Code: 1 1 0 1 1 1 0
• Durchnumerieren der Bit-Positionen beginnend mit 1 • Markieren der Kontrollbit-Positionen an den Stellen 20 bis 2r, also 1,
2, 4, 8 ... • Auffüllen der restlichen (freien) Positionen durch Datenbits
Beispiel zum Prüfen einer Hamming-Codierung
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (23g)
Bitposition 1 2 3 4 5 6 7 Kontrollbits p0 p1 p2 Datenbits c0 c1 c2 c3 Code: 1 1 0 1 1 1 0 für p0: 1 0 1 0 für p1: 1 0 1 0 für p2: 1 1 1 0
• Zuordnung der Codebits zu Gruppen entsprechend der durch die Polynomialcodes der Bit-Nummern mit einer 1 markierten Positionen
Beispiel zum Prüfen einer Hamming-Codierung
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (23h)
Bitposition 1 2 3 4 5 6 7 Kontrollbits p0 p1 p2 p* Datenbits c0 c1 c2 c3 Code: 1 1 0 1 1 1 0 für p0: 1 0 1 0 0 für p1: 1 0 1 0 0 für p2: 1 1 1 0 1
• Bilden des Syndroms S • Nochmaliges Erzeugen der Kontrollbits und Verknüpfung dieser
mittels XOR mit den mitgelieferten Kontrallbits • Aufgrund gleicher logischer Operationen für Kontrollbit- und
Syndromerzeugung kann das Syndrom auch durch Ermitteln der Parität über die gesamte Gruppe gebildet werden
Beispiel zum Prüfen einer Hamming-Codierung
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Codes (23i)
Bitposition 1 2 3 4 5 6 7 Kontrollbits p0 p1 p2 p* S Datenbits c0 c1 c2 c3 Code: 1 1 0 1 1 1 0 für p*0: 1 0 1 0 0 0 ∙20 für p*1: 1 0 1 0 0 0 ∙21 für p*2: 1 1 1 0 1 1 ∙22 ∑ 4 Korrektur: 1 1 0 0 1 1 0
• Interpretation des Syndroms S als Polynomialcode • wenn S=0, so trat kein Fehler auf • wenn S≠0, so gibt S sie Nummer des fehlerhaften Bits an • ggf. Korrektur des fehlerhaften Bits
Beispiel zum Prüfen einer Hamming-Codierung
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Weitere Eigenschaften von Hamming-Codes: • Die (Komponentenweise gebildete) Summe mod2 zweier Codewörter ist
wieder ein Codewort. Damit ist der Code auffassbar als ein Vektorraum über einem Körper mit 2 Elementen. Dafür gibt es eine mathematische. Theorie (Lineare Codes)
• Die Kugeln mit Radius 1 um Codewörter sind nicht nur disjunkt, sondern enthalten alle möglichen Wörter der Länge 𝑛𝑛. Jedes Wort der Länge 𝑛𝑛 kann decodiert werden. Ein Code dieser Eigenschaft heißt perfekt.
• Geht man von 𝑥𝑥1𝑥𝑥2 … 𝑥𝑥𝑛𝑛 über zu 𝑥𝑥2 … 𝑥𝑥𝑛𝑛𝑥𝑥1 (zyklischer Shift), so entsteht aus einem Codewort wiederum ein Codewort. Ein Code dieser Eigenschaft heißt zyklisch.
Codes (24)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
𝑟𝑟 = 𝑥𝑥 sei der Grad des Generator-Polynoms 𝑥𝑥. Füge 𝑟𝑟 Null-Bits zum niederwertigen Ende des Frames (Quellwortes) hinzu, so dass er nun 𝑚𝑚 + 𝑟𝑟 Bits enthält und mit dem Polynom 𝑥𝑥𝑟𝑟𝑀𝑀 𝑥𝑥 korrespondiert.
Dividiere den Polynom 𝑥𝑥𝑟𝑟𝑀𝑀 𝑥𝑥 durch den Generator-Polynom 𝑥𝑥 unter Nutzung der Modulo-2-Division.
Subtrahiere den Rest, der immer 𝑟𝑟 oder weniger Bits enthält, vom Polynom 𝑥𝑥𝑟𝑟𝑀𝑀 𝑥𝑥 unter Nutzung der Modulo-2-Subtraktion. Das Ergebnis ist der Frame mit Prüfsumme, der übertragen wird. Dieser Polynom heißt 𝑇𝑇 𝑥𝑥 .
1.
2.
3.
Algorithmus zur Berechnung der Prüfsumme:
Codes (25)
Polynomialcodes
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
11010110110000 : 10011 = 110000101010011 10011 10011 00001 00000 00010 00000 00101 00000 01011 00000 10110 10011 01010 00000 10100 10011 01110 00000 1110 Rest
Beispiel:
Frame (Quellwort):
Generator:
Nachricht nach dem Anfügen von vier Nullen:
1 1 0 1 0 1 1 0 1 1
1 0 0 1 1 𝑥𝑥 = 4
1 1 0 1 0 1 1 0 1 1 0 0 0 0
Übertragener Frame 𝑇𝑇 𝑥𝑥 : 1 1 0 1 0 1 1 0 1 1 1 1 1 0
Rest: 1 1 1 0
Codes (26)
Polynomialcodes
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Drei (Generator-)Polynome sind zum internationalen Standard geworden: CRC-12 ≔ 𝑥𝑥12 + 𝑥𝑥11 + 𝑥𝑥3 + 𝑥𝑥2 + 𝑥𝑥1 + 1 CRC-16 ≔ 𝑥𝑥16 + 𝑥𝑥15 + 𝑥𝑥2 + 1 CRC-CCITT ≔ 𝑥𝑥16 + 𝑥𝑥12 + 𝑥𝑥5 + 1 Eigenschaften der 16-Bit Prüfsumme (z.B. CRC-16 und CRC-CCITT): entdeckt werden: • alle Einfach- und Doppelfehler • alle Fehler mit einer ungeraden Anzahl von Bits • alle Burst-Fehler mit der Länge 16 oder weniger • 99.997% der 17-Bit-Burst-Fehler • 99.998% der 18-Bit-Fehler und längere Burst-Fehler
Codes (27)
Vorlesung Technische Informatik 1 WS 2019 T. Ihme
Kodierung von 4 Lebensmittelartikeln mit einem 2 Bit - Binärcode:
Huffman - Code:
Der entsprechende Huffman - Code:
Beispiel für die Darstellung des Huffman - Codes als Binärbaum:
Element
Kartoffeln Zwiebeln Bohnen Avocado
Code
00 01 10 11
Element
Kartoffeln Zwiebeln Bohnen Avocado
Prozentsatz der Übertragung
Code
70 14 9 7
0 11 100 101
Codes (28)
Start
Kartoffeln Bohnen
Avocado
Zwiebeln
000
0
111
11
100
101
Codes (1)Codes (2)Codes (3)Codes (4)Codes (5)Codes (6)Codes (7)Codes (8)Codes (9)Codes (10)Codes (11)Codes (12)Codes (13)Codes (14)Codes (15)Codes (16)Codes (17)Codes (18)Codes (19)Codes (20)Codes (21)Codes (22)Codes (23)Codes (23a)Codes (23b)Codes (23c)Codes (23d)Codes (23e)Codes (23f)Codes (23g)Codes (23h)Codes (23i)Codes (24)Codes (25)Codes (26)Codes (27)Codes (28)