Post on 04-Mar-2021
transcript
1
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 1FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Grundlagen der Nachrichtentechnik 4
Prof. Dr.-Ing. Andreas Czylwik
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 2FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 4Organisatorisches
Vorlesung 2 SWS
Übung 1 SWS, Betreuer: Dipl.-Ing. Lars Häring
Folienkopien sind verfügbar
Prüfung: schriftlich
Neue Forschungsthemen im Fachgebiet Nachrichtentechnische Systeme
Studien- und Diplomarbeiten
2
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 3FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 4Literatur
Literatur zur Vorlesung:
B. Friedrichs: Kanalcodierung, Springer-Verlag
H. Schneider-Obermann: Kanalcodierung, Vieweg-Verlag
H. Rohling: Einführung in die Informations- und Codierungstheorie, Teubner-Verlag
Blahut: Theory and practice of error control codes, Addison-Wesley
M. Bossert: Channel coding for telecommunications, John Wiley
M. Bossert: Kanalcodierung, Teubner-Verlag
J. H. van Lint: Introduction to coding theory
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 4FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 4Literatur
Literatur zur digitalen Übertragung:
S. Benedetto, E. Biglieri, V. Castellani: Digital transmission theory, Prentice-Hall
J.G. Proakis: Digital communications, McGraw-Hill
S. Haykin: Communication systems, John Wiley
3
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 5FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 4Inhalt1. Einführung
2. Grundlagen der Informationstheorie
3. Kanalcodierung in der Nachrichtenübertragung
4. Algebraische Grundbegriffe für Codes
5. Blockcodes
6. Faltungscodes
7. Codierungstechniken
8. Ausblick
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 6FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 41 Einführung
Blockschaltbild eines Systems zur digitalen Nachrichtenübertragung
Quellen-codierer
Kanal-codierer
Übertragungs-kanal
Modulator
DemodulatorKanal-decodierer
Quellen-decodierer
Signal-quelle
Signal-senke
StörungDigitale Quelle
Digitale SenkeDiskreter Kanal
4
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 7FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 41 Einführung
Quellencodierung (source coding):Kompression der Nachricht auf eine minimale Anzahl von Symbolen ohne Informationsverlust (Reduktion von Redundanz)
weitergehende Kompression, wobei toleriert wird, dass Information verloren geht (z. B. bei Bild- und Tonübertragung)
Codierung zur Verschlüsselung (Kryptologie)Schutz vor unberechtigtem Abhören
Entschlüsselung nur mit Kenntnis eines Code-Schlüssels
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 8FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 41 Einführung
Kanalcodierung (error control coding): kontrolliertes Hinzufügenvon Redundanz zum Schutz gegen Übertragungsfehler
Kanalcodierung zur Fehlerkorrektur (FEC – forward error correction)
vereinfachtes Modell:
Kanalqualität bestimmt Restfehlerwahrscheinlichkeit nach Decodierung
Datenrate unabhängig von Kanalqualität
Daten-quelle
Kanal-codierer Kanal Kanal-
decodiererDaten-senke
5
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 9FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 41 Einführung
Kanalcodierung zur Fehlerdetektion (CRC – cyclic redundancy check, Einsatz für ARQ-Verfahren (automatic repeat request))
Rückkanal notwendig
adaptives Einfügen von Redundanz (zusätzliche Redundanz nur im Fehlerfall
Restfehlerwahrscheinlichkeit unabhängig von der Kanalqualität
Datenrate abhängig von Kanalqualität
ARQ-Steuerung
Kanalcodierer Kanal Kanaldecodierer
(Fehlererkennung)ARQ-
Steuerung
FehlerinformationRückkanal
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 10FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 41 Einführung
Anwendungen: sichere Datenübertragung über Wellenleiter und Funkkanäle (insbesondere Mobilfunkkanäle), sichere Datenspeicherung
Begründer der Informationstheorie Claude E. Shannon:
Durch Kanalcodierung kann die Fehlerwahrscheinlichkeit beliebig reduziert werden, wenn die Datenrate kleiner als die Kanalkapazität ist.
(Shannon gibt keine Konstruktionsvorschrift an.)
6
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 11FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 41 Einführung
Grundgedanke der Kanalcodierung:Einfügen von Redundanz
Ziel: Fehlererkennung oder Fehlerkorrektur
Zuordnung im Codierer am Beispiel einer Block-Codierung:
Eingangsvektor: u = (u1, ... , uk)
Ausgangsvektor: x = (x1, ... , xn)
Coderate: nkR =C
Länge k Länge n
Informationsvektor u Codewort-Vektor x
(1.1)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 12FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 41 Einführung
Codewürfel mit n = 3, k = 3
uncodierte Übertragung: RC = 1
kleinstmögliche Distanz zu anderem Codewort: dmin = 1
keine Fehlererkennung und keine Fehlerkorrektur möglich
7
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 13FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 41 Einführung
Codewürfel mit n = 3, k = 2
codierte Übertragung: RC = 2/3
kleinstmögliche Distanz zu anderem Codewort: dmin = 2
Erkennung eines Fehlers möglich, keine Fehlerkorrektur möglich
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 14FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 41 Einführung
Codewürfel mit n = 3, k = 1
codierte Übertragung: RC = 1/3
kleinstmögliche Distanz zu anderem Codewort: dmin = 3
Erkennung von zwei Fehlern und Korrektur eines Fehlers möglich
8
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 15FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Informationtheorie: mathematische Beschreibung der Übertragung von Nachrichten
zentrale Fragestellungen: quantitative Berechnung des Informationsgehalts von Nachrichten
Bestimmung der Übertragungskapazität von Übertragungskanälen
Analyse und Optimierung von Quellen- und Kanalcodierung
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 16FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Nachricht aus der Sicht der Informationstheorie
irrelevant relevant
Fehl-information
redundant nicht redundant
9
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 17FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Informationsgehalt einer Nachricht, Entropie
qualitative Einordung von Nachrichten: Bedeutung umso größer, je weniger die Nachricht vorhersagbar ist
Beispiel:
Morgen geht die Sonne auf.
Morgen gibt es schlechtes Wetter.
Morgen gibt es ein starkes Unwetter, bei dem der Strom ausfallen wird.
Nachrichten einer digitalen Quelle: Folge von Zeichen
Bedeutung
Wahrscheinlichkeit
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 18FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Entscheidungsgehalt H0 einer Quelle: Anzahl der für die Auswahl der Nachricht benötigten Binärentscheidungen
Zeichenvorrat: N Zeichen
H0 = ld(N) bit/Zeichen
mit ld(x) = logarithmus dualis
Einheit: bit = binary digit
Entscheidungsgehalt H0 berücksichtigt nicht die Auftrittswahrscheinlichkeit
(2.1)
10
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 19FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel: deutschsprachiger Text als Quelle
26 ⋅ 2 Buchstaben, 3 ⋅ 2 Umlaute, ß, 12 Sonderzeichen einschließlich Leerzeichen „“ ()-.,;:!?
insgesamt 71 alphanumerischen Zeichen
H0 = ld(71) = ln(71) / ln(2) = 6,15 bit/Zeichen
Beispiel: eine Seite deutschsprachiger Text mit 40 Zeilen und 70Zeichen pro Zeile
Anzahl unterschiedlicher Seiten: N = 7140⋅70
Entscheidungsgehalt:
H0 = ld(7140⋅70) = 40 ⋅ 70 ⋅ ld (71) = 17,22 kbit/Seite
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 20FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Zeichenvorrat (Alphabet): X = {x1, ... , xN}
Auftrittswahrscheinlichkeiten der Zeichen: p(x1), ... , p(xN)
gewünschte Eigenschaften des Informationsgehalts I = f(p):I(xi) ≥ 0 für 0 ≤ p(xi) ≤ 1
I(xi) → 0 für p(xi) → 1
I(xi) > I(xj) für p(xi) < p(xj)
zwei aufeinanderfolgende statistisch unabhängige Zeichen
xi und xj mit p(xi,xj) = p(xi) ⋅ p(xj) :
I(xi,xj) = I(xi) + I(xj)
allgemeine Lösung: I(xi) = −k ⋅ logb(p(xi)) (2.2)
11
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 21FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Definition des Informationsgehalts:
Entropie H(X) = mittlerer Informationsgehalt einer Quelle:
nbit/Zeiche)(
1ld)(
=
ii xp
xI
nbit/Zeiche)(
1ld)(
)()()()(
1
1
∑
∑
=
=
⋅=
⋅==
N
i ii
N
iiii
xpxp
xIxpxIXH
(2.3)
(2.4)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 22FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel: binäre Quelle mit X = {x1, x2}Auftrittswahrscheinlichkeiten: p(x1) = p , p(x2) = 1 − p
Entropie: H(X) = −p ld(p) − (1 − p) ld(1 − p)
Shannon-Funktion: H(X) = S(p)(2.5)
0.0
0.2
0.4
0.6
0.8
1.0
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
S(p) / bit
p
12
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 23FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Die Entropie wird maximal für gleichwahrscheinliche Zeichen
⇒ H(X) ≤ H0 = ld N.Beweis:
Ausnutzen der Ungleichung:
∑
∑∑
=
==
⋅⋅=
⋅−⋅=−
N
i ii
N
ii
N
i ii
Nxpxp
Nxpxp
xpNXH
1
11
)(1ld)(
ld)()(
1ld)(ld)(
1ln −≤ xx
(2.6)
(2.7) -1.0
0.0
1.0
1.0 2.0 x
ln(x)
x − 1
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 24FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
mit
■
Redundanz einer Quelle: RQ = H0 − H(X)
0112ln
1)(12ln
1
1)(
12ln
1)(ld)(
1
1
=
−⋅=
−≤
−
⋅⋅≤−
∑
∑
=
=
NNxp
N
NxpxpNXH
N
ii
N
i ii
)1(2ln
1ld1ln −≤⇒−≤ xxxx
(2.8)
13
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 25FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Übertragung über Binärkanal:
Entwurf von Binärcodierungen für eine diskrete Quelle
Aufgaben der Quellencodierung:Zuweisung eines Binärcodes mit der Codewortlänge L(xi) zu einem Zeichen xi
Minimierung der mittleren
Codewortlänge
∑=
⋅==N
iiii xLxpxLL
1)()()(
L x1 1001
x2 011
xN 010111
L(xN)
....
....
(2.9)
L
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 26FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiele für binäre Codierungen von Zeichen:
ASCII-Code: feste Codewortlänge L(xi) = 8 (Blockcode)
Morse-Code (Punkt-Strich-Alphabet mit Pause zur Trennung der Codewörter): häufig auftretende Buchstaben werden kurzen Codeworten zugeordnet
Präfix-Eigenschaft eines Codes: kein Codewort bildet gleichzeitig den Beginn eines anderen Codewortes – „kommafreier Code“
14
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 27FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel für einen Code ohne Präfix-Eigenschaft:
eindeutige Decodierung einer Bitfolge nicht möglich
mögliche Decodier-Ergebnisse für die Sequenz 010010: x1x3x2x1, x2x1x1x3, x1x3x1x3, x2x1x2x1, x1x4x3
x1 → 0
x2 → 01
x3 → 10
x4 → 100
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 28FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel für einen Code mit Präfix-Eigenschaft:
eindeutige Decodierung einer Bitfolge
Decodierung der Sequenz 010010110111100: x1x2x1x2x3x4x2x1
Synchronisation: Anfang der Sequenz
x1 → 0
x2 → 10
x3 → 110
x4 → 111
15
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 29FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Decodierung mit Hilfe eines Entscheidungsbaums
Ebene 1: L(x1) = 1
0 1
0 1
0 1Ebene 2: L(x2) = 2
Ebene 3: L(x3) = L(x4) = 3
x1 → 0
x2 → 10
x3 → 110
x4 → 111
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 30FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Kraftsche Ungleichung: Ein Binärcode mit der Präfix-Eigenschaft und den Codewortlängen L(x1), L(x2), ... , L(xN) existiert nur dann, wenn
Das Gleichheitszeichen gilt, wenn alle Endpunkte des Codebaums mit Codewörten besetzt sind.
121
)( ≤∑=
−N
i
xL i (2.10)
16
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 31FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beweis:
Länge der Baumstruktur = maximale Codewortlänge
Lmax = max(L(x1), L(x2), ... , L(xN))
Codewort in Ebene L(xi) eliminiert der möglichen Codeworte in der Ebene Lmax
Summe aller eliminierten Codeworte ≤ maximale Anzahl in der Ebene Lmax
■
)(max2 ixLL −
maxmax 221
)( LN
i
xLL i ≤∑=
−
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 32FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Grenze für die mittlere Codewortlänge:
Beispiel für den Sonderfall, dass die Auftrittswahrschein-lichkeiten Zweierpotenzen sind:
Zuordnung der Codeworte entsprechend der Vorschrift
L(xi) = Ki
Sonderfall:
)(XHL ≥
( ) iKixp 2
1)( =
815)( == XHL
xi p(xi) Codewortex1 1/2 1x2 1/4 00x3 1/8 010x4 1/16 0110x5 1/16 0111
(2.11)
(2.12)
17
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 33FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Shannon’sches Codierungstheorem: Für jede Quelle lässt sich eine Binärcodierung finden mit:
Beweis:
linke Seite: mittlere Codewortlänge ≥ mittlerer Informationsgehalt
rechte Seite: Auswahl eines Codewortes mit
I(xi) ≤ L(xi) ≤ I(xi) + 1
Multiplikation mit p(xi) und Summation über alle i ⇒ s.o.
1)()( +≤≤ XHLXH (2.13)
(2.14)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 34FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Nachweis, dass es einen Code mit Präfix-Eigenschaft (11) gibt:
linke Seite von (2.14):
Summe über alle Symbole entspricht (2.10):
■1)(2
11
)( ∑∑==
− =≤N
ii
N
i
xL xpi
)()(
1 2)()(ld)( ii
xLiixpi xpxLxI −≥⇒≤
=
18
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 35FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Shannon’sche CodierungCodewortlänge entsprechend (2.14): I(xi) ≤ L(xi) ≤ I(xi) + 1
akkumulierte Auftrittswahrscheinlichkeiten
Sortieren der Symbole nach Auftrittswahrscheinlichkeit
Codeworte sind Nachkommastellen eine Binärdarstellung von Pi
∑−
==
1
1)(
i
jji xpP
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 36FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel
H0 = 3,17 bit
H(X) = 2,97 bit
Mittlere Codewortlänge:
Berechnung eines Codewortes:
0,90 = 1⋅2−1 + 1⋅2−2 + 1⋅2−3 + 0⋅2−4 + 0⋅2−5 + 1⋅2−6 + 1⋅2−7 +0⋅2−8 + 0⋅2−9 + 1⋅2−10 + ...
i p(xi) I(xi) L(xi) Pi Code1 0,22 2,18 3 0,00 0002 0,19 2,40 3 0,22 0013 0,15 2,74 3 0,41 0114 0,12 3,06 4 0,56 10005 0,08 3,64 4 0,68 10106 0,07 3,84 4 0,76 11007 0,07 3,84 4 0,83 11018 0,06 4,06 5 0,90 111009 0,04 4,64 5 0.96 11110
bit54.3=L
19
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 37FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Baumdarstellung eines Shannon-Codes:
Nachteil: nicht alle Endpunkte des Baums sind besetzt
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 38FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Codewortlänge kann reduziert werden ⇒ Code ist nicht optimal
Redundanz eines Codes:
Redundanz einer Quelle:
Huffman-Codierungrekursives Vorgehen
Startpunkt: Symbole mit den kleinsten Wahrscheinlichkeiten
gleiche Codewortlänge für die beiden Symbole mit der kleinsten Wahrscheinlichkeit
andernfalls: Reduzierung der Codewortlänge möglich
)(C XHLR −=
)(0Q XHHR −=(2.15)
(2.16)
20
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 39FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Algorithmus:
Schritt 1: Ordnen der Symbole entsprechend ihrer Wahrscheinlichkeit
Schritt 2: Zuordnung von 0 und 1 zu den beiden Symbolen mit der kleinsten Wahrscheinlichkeit
Schritt 3: Zusammenfassen der beiden Symbole mit der kleinsten Wahrscheinlichkeit xN−1 und xN zu einem neuen Symbol mit der Wahrscheinlichkeit p(xN−1 ) + p( xN)
Schritt 4: Wiederholung der Schritte 1 - 3, bis nur noch ein Symbol übrig bleibt
Beispiel
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 40FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
x1 x2 x3 x4 x5 x6 x7 x8 x9 0,22 0,19 0,15 0,12 0,08 0,07 0,07 0,06 0,04
0 1
x1 x2 x3 x4 x8 x9 x5 x6 x7 0,22 0,19 0,15 0,12 0,10 0,08 0,07 0,07
0 1 0 1
x1 x2 x3 x6 x7 x4 x8 x9 x5 0,22 0,19 0,15 0,14 0,12 0,10 0,08
0 1 00 01 1
x1 x2 x8 x9 x5 x3 x6 x7 x4 0,22 0,19 0,18 0,15 0,14 0,12
00 01 1 00 01 1
21
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 41FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
x6 x7 x4 x1 x2 x8 x9 x5 x3 0,26 0,22 0,19 0,18 0,15
00 01 1 000 001 01 1
x8 x9 x5 x3 x6 x7 x4 x1 x2 0,33 0,26 0,22 0,19
000 001 01 1 00 01 1 0 1
x1 x2 x8 x9 x5 x3 x6 x7 x4 0,41 0,33 0,26
0 1 0000 0001 001 01 100 101 11
x8 x9 x5 x3 x6 x7 x4 x1 x2 0,59 0,41
00000 00001 0001 001 0100 0101 011 10 11
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 42FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Baumstruktur des Huffman-Code-Beispiels
bit01.3=L
22
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 43FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Diskrete Quelle ohne GedächtnisVerbundentropie von Zeichenketten
zwei unabhängige Zeichen: p(xi,yk) = p(xi) ⋅ p(yk)
[ ]
)()(),(
))((ld)()())((ld)()(
))((ld))((ld)()(
)),((ld),(),(
1´111
1 1
1 1
YHXHYXH
ypypxpxpxpyp
ypxpypxp
yxpyxpYXH
N
kkk
N
ii
N
iii
N
kk
N
i
N
kkiki
N
i
N
kkiki
+=
⋅⋅−⋅⋅−=
+⋅⋅−=
−=
∑∑∑∑
∑∑
∑∑
====
= =
= =
(2.18)
(2.17)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 44FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
M unabhängige Zeichen der gleichen Quelle:
H(X1, X2, ... , XM) = M ⋅ H(X)
Effizienteres Codieren durch Codieren von ZeichenkettenShannon’sches Codierungstheorem:
Nachteil beim Codieren von Zeichenketten: stark ansteigender Codierungsaufwand (exponentielle Zunahme der Zahl der möglichen Zeichen)
H(X1,...,XM) ≤ ≤ H(X1,...,XM) + 1
M⋅H(X) ≤ ≤ M⋅H(X) + 1
H(X) ≤ ≤ H(X) + 1/M
),,( 1 MM XXL K
LM ⋅
L
(2.19)
(2.20)
23
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 45FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel: Codierung von Zeichenfolgenbinäre Quelle mit X = {x1, x2}
Auftrittswahrscheinlichkeiten: p(x1) = 0,2, p(x2) = 0,8
Entropie: H(X) = 0,7219 bit/Zeichen
Codierung von Einzelzeichen:
mittlere Codewortlänge:
Zeichen p(xi) Code L(xi) p(xi)⋅L(xi)x1 0,2 0 1 0,2x2 0,8 1 1 0,8
Σ = 1
nbit/Zeiche1=L
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 46FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Codierung von Zeichenpaaren:
mittlere Codewortlänge:
Zeichen-paar
p(xi) Code L(xi) p(xi)⋅L(xi)
x1x1 0,04 101 3 0,12x1x2 0,16 11 2 0,32x2x1 0,16 100 3 0,48x2x2 0,64 0 1 0,64
Σ = 1,56
nbit/Zeiche 78,0=L
24
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 47FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Codierung von Zeichentripeln:
mittlere Codewortlänge:
Zeichen-tripel
p(xi) Code L(xi) p(xi)⋅L(xi)
x1x1x1 0,008 11111 5 0,040x1x1x2 0,032 11100 5 0,160x1x2x1 0,032 11101 5 0,160x1x2x2 0,128 100 3 0,384x2x1x1 0,032 11110 5 0,160x2x1x2 0,128 101 3 0,384x2x2x1 0,128 110 3 0,384x2x2x2 0,512 0 1 0,512
Σ = 2,184nbit/Zeiche 728,0=L
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 48FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Diskrete Quelle mit Gedächtnisreale Quellen: Korrelation zwischen den Einzelzeichen
zwei abhängige Zeichen: p(xi,yk) = p(xi) ⋅ p(yk|xi) = p(yk) ⋅ p(xi|yk)
[ ]
)|()(),(
))|((ld),())((ld)()|(
))|((ld))((ld)|()(
)),((ld),(),(
1 11 1
1 1
1 1
XYHXHYXH
xypyxpxpxpxyp
xypxpxypxp
yxpyxpYXH
N
i
N
kikki
N
i
N
kiiik
N
i
N
kikiiki
N
i
N
kkiki
+=
⋅−⋅⋅−=
+⋅⋅−=
−=
∑∑∑∑
∑∑
∑∑
= == =
= =
= =
(2.21)
25
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 49FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
H(Y | X) = bedingte Entropie
Entropie einer Quelle ≥ bedingte Entropie
H(Y) ≥ H(Y | X )
Beweis:
(2.22)∑∑= =
⋅−=N
i
N
kikki xypyxpXYH
1 1))|((ld),()|(
(2.23)
∑∑
∑∑∑
= =
= ==
⋅=−
⋅−=⋅−=
N
i
N
k ik
kki
N
i
N
kkki
N
kkk
xypypyxpYHXYH
ypyxpypypYH
1 1
1 11
)|()(ld),()()|(
))((ld),())((ld)()(
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 50FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Abschätzung mit:
mit p(xi,yk) = p(xi) ⋅ p(yk|xi)
■
∑∑= =
−⋅⋅≤−
N
i
N
k ik
kki xyp
ypyxpYHXYH1 1
1)|(
)(2ln
1),()()|(
)1(2ln
1ld1ln −≤⇒−≤ xxxx
0),()()(2ln
1)()|(1 11 1
=
−≤− ∑∑∑∑
= == =
N
i
N
kki
N
i
N
kki yxpypxpYHXYH
= 1 = 1
26
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 51FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
gleichwahrscheinliche Einzelzeichen: Entropie einer Quelle mit Gedächtnis < Entropie einer Quelle ohne Gedächtnis
besonders effiziente Quellencodierung durch Codierung von Zeichenfolgen bei Quellen mit Gedächtnis
allgemeine Beschreibung einer diskreten Quelle mit Gedächtnis als Markoff-Quelle
Markoff-Prozesse:
Folge von Zufallsvariablen z0, z1, z2, ... ,zn, (n = Zeitachse)
zi und zj sind statistisch unabhängig:
)(),...,,|( 021,...,,| 021 nznnnzzzz zfzzzzfnnnn
=−−−− (2.24)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 52FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
zi und zj sind stat. abhängig (Markoff-Prozess m-ter Ordnung):
Häufig: Markoff-Prozess erster Ordnung (m = 1):
zi nehmen endlich viele diskrete Werte an: zi ∈ {x1, ... , xN}
⇒ Markoff-Kette
vollständige Beschreibung einer Markoff-Kette durch Übergangswahrscheinlichkeiten
)|(),...,,|( 1|021,...,,| 1021 −−− −−−= nnzznnnzzzz zzfzzzzf
nnnnn
),...,|(),...,|(101 101 mnnn imninjniinjn xzxzxzpxzxzxzp
−−−======= −−−
(2.26)
(2.27)
),...,|(),...,,|( 1,...,|021,...,,| 1021 mnnnzzznnnzzzz zzzfzzzzfmnnnnnn −−−− −−−−
=
(2.25)
27
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 53FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
homogene Markoff-Kette: Übergangswahrscheinlichkeiten hängen nicht von der absoluten Zeit ab:
stationäre Markoff-Kette: eingeschwungener Zustand hängt
nicht von den Anfangswahrscheinlichkeiten ab
homogene und stationäre Markoff-Kette erster Ordnung: m = 1
jjjnkn
ikjnkn
wxpxzpxzxzp ====== +∞→
+∞→
)()(lim)|(lim
ijinjn pxzxzp === − )|( 1
(2.29)
(2.30)
),...,|(),...,|(11 11 mm imkikjkimninjn xzxzxzpxzxzxzp ======= −−−−
(2.28)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 54FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Übergangsmatrix:
Eigenschaften der Übergangsmatrix:
Wahrscheinlichkeitsvektor:
Bestimmung von w mit Hilfe des eingeschwungenen Zustands:
11
=∑=
N
jijp
))()()(()( 2121 NN xpxpxpwww LL ==w
Pww =
(2.32)
(2.33)
(2.34)
=
NNNN
N
N
ppp
pppppp
L
LOLL
L
L
21
22221
11211
P (2.31)
28
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 55FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
stationäre Markoff-Quelle: Markoff-Kette erster Ordnung
Entropie einer stationären Markoff-Quelle = Entropie im eingeschwungenen Zustand:
iinnN
iinni
N
i
N
jinjninjni
N
i
N
jinjninjn
nnnnnn
xzzHxzzHwZH
xzxzpxzxzpw
xzxzpxzxzp
zzHzzzzHZH
)|()|()(
))|((ld)|(
))|((ld),(
)|(),,,|(lim)(
11
1
1 111
1 111
1021
===⋅=
==⋅==⋅−=
==⋅==−=
==
−=
−∞
= =−−
= =−−
−−−∞→
∞
∑
∑ ∑
∑∑
K
(2.38)
(2.35)
(2.36)
(2.37)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 56FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
⇒ Entropie H∞(Z) = bedingte Entropie, da Zeichen aus der Vergangenheit bereits bekannt sind
Codierung einer Markoff-Quelle:
Berücksichtigung des Gedächtnisses
z. B. Huffman-Codierung unter Berücksichtigung des momentanen Zustands der Quelle
grundsätzliches Problem bei Quellencodes mit variabler Länge: katastrophale Fehlerfortpflanzung
)()()|()( 01 nnnn zHzHzzHZH ≤≤= −∞ (2.39)
29
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 57FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel einer Markoff-Quelle:Zustände = gesendete Zeichenzn ∈ {x1, x2, x3}Übergangswahrscheinlichkeiten:
( ) ( )
===== −
3,01,06,02,05,03,04,04,02,0
)|( 1 Pijinjn pxzxzp
zn zn−1
x1 x2 x3
x1 0,2 0,4 0,4 x2 0,3 0,5 0,2 x3 0,6 0,1 0,3
x1 x2
x3
0.20.3
0.4
0.2
0.1
0.4
0.5
0.3
0.6
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 58FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Berechnung der stationären Wahrscheinlichkeiten mit:
w1 = 0,2 w1 + 0,3 w2 + 0,6 w3
w2 = 0,4 w1 + 0,5 w2 + 0,1 w3
w3 = 0,4 w1 + 0,2 w2 + 0,3 w3
1 = w1 + w2 + w3
lineare Abhängigkeit !
Lösung:
1 und 1
== ∑=
N
iiwPww
3011,03441,03548,0 9328
39332
29333
1 ≈=≈=≈= www
(2.40)
30
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 59FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Berechnung der Entropie mit (35):
Zahlenwerte einsetzen:
∑ ∑
∑
= =
=−∞
⋅⋅−=
=⋅=
N
i
N
jijiji
N
iinni
ppw
xzzHwZH
1 1
11
)(ld
)|()(
(2.41)
henbit / Zeic2955,1ld3,0ld1,0ld6,0)|(henbit / Zeic4855,1ld2,0ld5,0ld3,0)|(henbit / Zeic5219,1ld4,0ld4,0ld2,0)|(
3,01
0,11
0,61
31
2,01
0,51
0,31
21
4,01
0,41
0,21
11
≅⋅+⋅+⋅==≅⋅+⋅+⋅==≅⋅+⋅+⋅==
−
−
−
xzzHxzzHxzzH
nn
nn
nn
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 60FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Entropie:
zum Vergleich: statistisch unabhängige Zeichen
Zeichen/bit441,1
)|()|()|()( 313212111
≅
=+=+== −−−∞ xzzHwxzzHwxzzHwZH nnnnnn
Zeichen/bit5814,11ld)(lim)(1
≅⋅== ∑=∞→
N
i iin
n wwzHZH
Zeichen/bit5850,13ld0 ≅=H
(2.42)
31
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 61FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
zustandsabhängige Huffman-Codierung für das Beispiel: unterschiedliche Codierungen für jeden Zustand zn−1
pij Codewörter
mittlere Codewortlänge:
zn
zn−1
x1 x2 x3 ⟨L⟩|zn−1
x1 11 10 0 1,6x2 10 0 11 1,5x3 0 11 10 1,4
Zeichen/bit5054,1
)|()|(1 1
11
≅
==⋅⋅==== ∑∑= =
−−N
i
N
jinjnijiinjn xzxzLpwxzxzLL
(2.43)
zn
zn−1
x1 x2 x3
x1 0,2 0,4 0,4x2 0,3 0,5 0,2x3 0,6 0,1 0,3
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 62FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Quellencodierung ohne Kenntnis der statistischen Parameter der Quelle
Lauflängencodierung (run-length coding)
Substitution eines wiederholten Symbols durch ein einzelnes Symbole und die Anzahl der Wiederholungen
Beispiel:
Ausgangssequenz der Quelle:
aaaabbbccccccccdddddeeeeeaaaaaaabddddd.....
codierte Sequenz:
4a3b8c5d5e7a1b5d.....
32
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 63FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Codierung mit Wörterbüchern
Idee: Wiederholungen in der Datensequenz werden durch (kürzere) Referezierungen in das Wörterbuch ersetzt
Statisches Wörterbuch:
schlechte Anpassung des Wörterbuchs an bestimmte zu codierende Daten
geringe Kompression für die meisten Datenquellen
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 64FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
halbadaptives Wörterbuch
Das Wörterbuch ist für die zu codierenden Daten zugeschnitten.
Das Wörterbuch muss über den Kanal übertragen werden.
Zwei Durchläufe über die Daten notwendig:
» für den Aufbau des Wörterbuchs
» für die Codierung der Daten
Adaptives Wörterbuch
Einfacher Durchlauf für den gleichzeitigen Aufbau des Wörterbuchs und der Codierung
Lempel-Ziv-Algorithmus: *.zip *.gzip Dateien
33
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 65FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Lempel-Ziv-Algorithmus (LZ77)
Suche nach der längsten Übereinstimmung zwischen den ersten Symbolen des Analysefensters und dem Suchfenster
Ausgabe: Codewörter mit fester Länge Position der Übereinstimmung (Zählanfang = 0) Länge der Übereinstimmungnächstes Symbol im Analysefenster
Suchfenster Analysefenster
..... a b c b a a b c b d f e e a a b a a c c d d d c d .....
Bearbeitungsfenster
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 66FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Parameter:Symbolalphabet: {x0,x1,x2, .... , xα−1}Eingangssequenz: S = {S1,S2,S3,S4, ....}Länge des Analysefensters: LS
Länge des Bearbeitungsfensters: n
Codewörter: Ci = {pi,li,Si}Position der Übereinstimmung: pi
Länge der Übereinstimmung: li
nächstes Symbol: Si
Länge der Codewörter: 1)(log)(log SSC ++−= LLnL αα
34
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 67FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel:Symbolalphabet: {0,1,2}Eingangssequenz:S = {0010102102102120210212001120.....}Länge des Analysefensters: LS = 9Länge des Bearbeitungsfensters: n = 18Schritt 1:
Schritt 2:
1 0 2 10 0 0 0 0 0 0 0 0 0 2 1 0 2 . . . .1000
C1 = {22 02 1}
1 0 2 10 0 0 0 0 0 0 1 2 0 2 1 2 0 . . . .0100
C2 = {21 10 2}
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 68FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Schritt 3:
Schritt 4:
Anzahl codierter Quellensymbole nach 4 Schritten: 3 + 4 + 8 + 9 = 24
Anzahl von Codewortsymbolen nach 4 Schritten: 4 × 5 = 20
0 2 1 20 0 0 1 0 1 0 2 1 0 2 1 0 2 . . . .2010
C3 = {20 21 2}
2 1 2 01 0 2 1 0 2 1 2 0 0 1 1 2 0 . . . .1202
C4 = {02 22 0}
35
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 69FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Decodierung:Schritt 1: C1 = {22 02 1}
Schritt 2: C2 = {21 10 2}
Schritt 3: C3 = {20 21 2}
Schritt 4: C4 = {02 22 0}
0 0 0 0 0 0 0 0 1000
0 0 0 0 0 0 0 1 20100
0 2 1 20 0 0 1 0 1 0 2 12010
2 1 2 01 0 2 1 0 2 1 2 0 01202
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 70FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Nachrichtenübertragung über einen diskreten gedächtnislosen Kanal
störungsfreier Kanal:
Information am Ausgang = Information am Eingang
⇒ übertragene Information = Entropie der Quelle
gestörter Kanal:
Information am Ausgang < Information am Eingang
⇒ übertragene Information < Entropie der Quelle
Definition:
Transinformation = tatsächlich übertragene Information
36
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 71FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Diskreter gedächtnisloser Kanal
(discrete memoryless channel – DMC)
Eingangssignal:
Ausgangssignal:
},...,,{ 21 XNxxxX ∈
},...,,{ 21 YNyyyY ∈
Diskretergedächtnisloser
Kanal
X Y
p11
p21
p12
p22
x1
y2
xNX
x2
y1
yNYpNXNY
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 72FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Übergangsmatrix:
mit
Binärkanal:
Fehlerwahrscheinlichkeit eines Binärkanals:
( ) ( )
=====
YXXX
Y
Y
NNNN
N
N
ijij
ppp
pppppp
pxXyYp
L
LOLL
L
L
21
22221
11211
)|(P
212121
212121)()(
)|()()|()()Fehler(pxppxp
xypxpxypxpp⋅+⋅=
⋅+⋅=
=2221
1211pppp
P
11
=∑=
N
jijp
(2.44)
(2.45)
(2.46)
(2.47)
37
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 73FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Symmetrischer Binärkanal (binary symmetric channel - BSC)
Fehlerwahrscheinlichkeit:
1−perr
perr
perr
x1
x21−perr
errerr21
212121
)]()([
)()()Fehler(
ppxpxp
pxppxpp
=⋅+=
⋅+⋅=
−
−=
errerr
errerr1
1pp
ppP (2.48)
(2.49)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 74FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel zur Transinformation – qualitative Betrachtung:
Übertragung von 1000 binären, statistisch unabhängigen und gleichwahrscheinlichen Symbolen (p(0) = p(1) = 0,5)
symmetrischer Binärkanal mit perr = 0,01
mittlere Anzahl der richtig übertragenen Symbole: 990
aber: T(X,Y) < 0,99 bit/Zeichen
Ursache: genaue Lage der Fehler ist nicht bekannt
38
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 75FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Definitionen der Entropien an einem diskreten gedächtnislosen Kanal:
Eingangsentropie = mittlerer Informationsgehalt der Eingangssymbole:
Ausgangsentropie = mittlerer Informationsgehalt der Ausgangssymbole:
Verbundentropie = mittlere Unsicherheit des gesamten Übertragungssystems:
)(1ld)()(
1 i
N
ii xp
xpXHX∑=
⋅=
)(1ld)()(
1 j
N
jj yp
ypYHY∑=
⋅=
∑ ∑= =
⋅=X YN
i
N
j jiji yxp
yxpYXH1 1 ),(
1ld),(),(
(2.50)
(2.51)
(2.52)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 76FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
bedingte Entropie H(Y|X) = mittlerer Informationsgehalt am Ausgang bei bekanntem Eingangssymbol = Entropie der Irrelevanz
bedingte Entropie H(X|Y) = mittlerer Informationsgehalt am Eingang bei bekanntem Ausgangssymbol = Entropie der Information, die auf dem Kanal verloren geht = Entropie der Äquivokation
∑ ∑= =
⋅=X YN
i
N
j ijji xyp
yxpXYH1 1 )|(
1ld),()|(
∑ ∑= =
⋅=X YN
i
N
j jiji yxp
yxpYXH1 1 )|(
1ld),()|(
(2.53)
(2.54)
39
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 77FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beziehungen zwischen den Entropien:
mittlere Transinformation:
)|()()|()(),(),( YXHYHXYHXHXYHYXH +=+==
)()|( XHYXH ≤
)()|( YHXYH ≤
),()()(
)|()(
)|()(),(
YXHYHXH
XYHYH
YXHXHYXT
−+=
−=
−=
(2.55)
(2.56)
(2.57)
(2.58)
(2.59)
(2.60)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 78FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Informationsströme
Quelle Quellen-codierer
Quellen-decoder Senke
H(U)H(X)
H(Y)
H(X|Y)
H(Y|X)
Äquivokation
Irrelevanz
Transinformation
)ˆ(UH
Übertragungskanal
T(X,Y)
40
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 79FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
spezielle Beispiele zur Transinformation:
idealer ungestörter Kanal:
Entropien: H(X|Y) = 0, H(Y|X) = 0,
H(X,Y) = H(X) = H(Y)
T(X,Y) = H(X) = H(Y)
≠=
=jiji
pij für 0für 1
(2.61)
(2.62)
(2.63)
(60)
(2.64)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 80FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
nutzloser, vollständig gestörter Kanal:
p(xi,yj) = p(xi) ⋅ p(yj) = p(yj|xi) ⋅ p(xi)
⇒ p(yj|xi) = p(yj) ⇒ pij = pkj
Entropien: H(X|Y) = H(X), H(Y|X) = H(Y),
H(X,Y) = H(X) + H(Y)
T(X,Y) = 0
(60)
(2.65)
(2.66)
(2.67)
(2.68)(2.69)
41
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 81FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel zur Transinformation – quantitative Betrachtung:
Übertragung von 1000 binären, statistisch unabhängigen und gleichwahrscheinlichen Symbolen (p(0) = p(1) = 0,5)
symmetrischer Binärkanal mit perr = 0,01
nbit/Zeiche9192,0
)(11ld1
1ld)1())1()0((1
)|(1ld)|()(
)(1ld)(
)|()(),(
errerr
errerr
err
1 11
≅
−=
+
−−+−=
⋅⋅−⋅=
−=
∑ ∑∑= ==
pSp
pp
ppp
xypxypxp
ypyp
XYHYHYXT
X YY N
i
N
j ijiji
N
j jj
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 82FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
KanalkapazitätTransinformation hängt von der Wahrscheinlichkeitsdichte der Quellensymbole ab
Definition der Kanalkapazität:
Kanalkapazität = Maximum des Transinformationsflusses
∆T = Periode der Zeichen
Dimension der Kanalkapazität: bit/s
C hängt von den Kanaleigenschaften ab, nicht von der Quelle!
),(max1
)(YXT
TC
ixp∆= (2.70)
42
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 83FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Definition von Informationsfluss ...Informationsfluss = Entropie / Zeit:
H′(X) = H(X) / ∆T
Transinformationsfluss = Transinformation / Zeit:
T′(X,Y) = T(X,Y) / ∆T
Entscheidungsfluss = Entscheidungsgehalt / Zeit:
H0′(X) = H0(X) /∆T
(2.71)
(2.72)
(2.73)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 84FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel: symmetrischer Binärkanal (binary symmetric channel –BSC):
−
−+−
+−−+−−+
−+−+=
−=
errerr
errerr
err1err1err1err1
err1err1err1err1
11ld)1(1ld
211ld)21(
21ld)2(
)|()(),(
pp
pp
pppppppp
pppppppp
XYHYHYXT
(2.74)
43
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 85FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Transinformation
Maximum für p1 = p(x1) = 0,5
0.0
0.2
0.4
0.6
0.8
1.0
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 p(x1)
T(X,Y)bi
t/Zei
chen
perr = 0
perr = 0,1
perr = 0,2
perr = 0,3
perr = 0,5
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 86FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Kanalkapazität
0.0
0.2
0.4
0.6
0.8
1.0
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 perr
C⋅∆T / bit
)(11
1ld)1(1ld1),(max errerr
errerr
err)(
pSp
pp
pYXTTCixp
−=
−
−+−==∆⋅
(2.75)
44
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 87FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beispiel: binärer Auslöschungskanal (binary erasure channel – BEC)
−
−=
err
err
err
err1
00
1pp
pp
P err1 pTC −=∆⋅
0.0
0.2
0.4
0.6
0.8
1.0
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 perr
C⋅∆T / bit
(2.77)(2.76)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 88FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Satz von der Kanalkapazität (Shannon 1948):Für jedes ε > 0 und jeden Informationsfluss einer Quelle R kleiner als die Kanalkapazität C ( R < C ) existiert ein binärer Blockcode der Länge n (n hinreichend groß), so dass die Restfehlerwahrscheinlichkeit nach der Decodierung im Empfänger kleiner ε ist.
Umkehrung: Für R > C kann die Restfehlerwahrscheinlichkeit eine gewisse Grenze auch bei größtem Aufwand nicht unterschreiten.
45
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 89FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Beweisführung mit zufälligen Blockcodes (random coding argument):
Beweis für das Mittel über alle Codes
Alle bekannten Codes sind schlechte Codes
keine Konstruktionsvorschrift für Codes
Kanalkapazität: Optimum für unendliche Codewortlänge ⇒unendliche Verzögerungszeit, unendliche Komplexität
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 90FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Verfeinerung des Satzes von der Kanalkapazität mit dem Fehlerexponent nach Gallager für einen DMC mit NXEingangssymbolen:
Es existiert immer ein (n,k)-Blockcode mit RC = k / n ld NX < C∆T, so dass für die Wort-Fehlerwahrscheinlichkeit gilt:
⋅−⋅−= ∑ ∑
=
+
=
+≤≤
Y X
i
N
j
sN
i
sijixps
xypxpRsRE1
1
1
11
C)(10
CG )|()(ldmaxmax)(
)(w CG2 REnP ⋅−<
(2.78)
(2.79)
46
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 91FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Fehlerexponent nach GallagerEigenschaften:
EG(RC) > 0 für RC < C
EG(RC) = 0 für RC ≥ C
Definition R0-Wert:
R0 = EG(RC = 0) 0.0
0.2
0.4
0.6
0.8
0.0 0.2 0.4 0.6 0.8 1.0
EG(RC)
RC
R0
R0 C
(2.80)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 92FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
R0-Wert (auch: computational cut-off rate)
Maximum von EG(RC = 0) liegt bei s = 1
Vergleich für s = 1:
⋅−=== ∑ ∑
= =
Y X
i
N
j
N
iiji
xpxypxpRER
1
2
1)(CG0 )|()(ldmax)0(
C01
2
1C
)(CG )|()(ldmax)( RRxypxpRRE
Y X
i
N
j
N
iiji
xp−=
⋅−−≥ ∑ ∑
= =
(2.81)
(2.82)
47
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 93FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
R0-Theorem:Es existiert immer ein (n,k)-Blockcode mit RC = k / n ld NX < C∆T, so dass für die Wort-Fehlerwahrscheinlichkeit (bei Maximum-Likelihood-Decodierung) gilt:
keine Konstruktionsvorschrift für gute Codes
Wertebereiche für die Coderate
0 ≤ RC ≤ R0 Abschätzung von PW mit (2.83)
R0 ≤ RC ≤ C ∆T Abschätzung von PW schwierig zu berechnen
RC > C ∆T PW kann nicht beliebig klein werden
)(w C02 RRnP −−< (2.83)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 94FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 42 Grundlagen der Informationstheorie
Vergleich von Kanalkapazität und R0-Wert für einen BSC:
0.0
0.2
0.4
0.6
0.8
1.0
0.0 0.1 0.2 0.3 0.4 0.5 perr
R0
C ∆T
bit/Z
eich
en
48
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 95FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Ziele: Grundbegriffe und Codebeispiele für Blockcodes
Konstruktion von Codewörternbinäre Codewörterredundante Codes
Code C = Menge aller Codewörter
Codewort c = (c0, c1, ... , cn-1) mit c ∈ CCodierung ist gedächtnislose Zuweisung:
Informationswort Codewort u = (u0, u1, ... , uk-1) → c = (c0, c1, ... , cn-1)
k Informationsstellen n Codewortstellen n ≥ k
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 96FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
identische Codes: Codes mit den gleichen Codewörtern
äquivalente Codes: Codes, die nach Vertauschung von Stellen identisch werden
allgemeine Bezeichnung: (n,k,dmin)q-Blockcode
q = Anzahl bzw. Stufenzahl der Symbole
Coderate:
Anzahl von Codewörtern: N = 2k
1C ≤=nkR (3.1)
(3.2)
49
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 97FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
systematische Codes:
Codewort c = (u, p)
m = n-k
Prüf- / Kontrollstellen
nicht-systematische Codes: Informations- und Prüfstellen nicht trennbar
Blockcodes sind immer in äquivalente systematische Codes umformbar
u0 u1 u2 u3 ... ... uk-1
↓ ↓ ↓ ↓ ↓ ↓ ↓c0 c1 c2 c3 ... ... ck-1 ck ck+1 ... ... cn-1
(3.3)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 98FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Addition und Multiplikation im binären Zahlensystem (modulo 2):
zwei Binärvektoren gleicher Länge x und yHamming-Distanz:
dH(x,y) = Anzahl der Abweichungen zwischen den Stellen von x und y
Beispiel: dH( 0 1 1 1 0 1 0 1,1 0 1 0 0 1 0 1 ) = 3
⊕ 0 10 0 11 1 0
⊗ 0 10 0 01 0 1
50
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 99FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
(Hamming-)Gewicht eines Vektors x:
Beispiel: wH(0 1 1 1 0 1 0 1) = 5
Hamming-Distanz: dH(x,y) = wH(x + y)
Beispiel: x = ( 0 1 1 1 0 1 0 1 )y = ( 1 0 1 0 0 1 0 1 )
x + y = ( 1 1 0 1 0 0 0 0 )wH(x + y) = 3
(3.5)
Stellenenen verschied0der von Anzahl )(1
0H == ∑
−
=
n
iixw x (3.4)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 100FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Übertragung über Binärkanal:
y = x + f
f = Fehlervektor
Der Wiederholungscode (repetition code)
k = 1 Informationsbit → n − 1 Wiederholungen
2k = 2 Codewörter: c1 = (0 0 0 ... 0) und c2 = (1 1 1 ... 1)
Wiederholungscode ist systematisch
einfache Decodierung durch Mehrheitsentscheid, wenn n ungerade ist
(n − 1)/2 Fehler sind korrigierbar, n − 1 Fehler sind erkennbar
(3.6)x y
f
51
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 101FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Beispiel für einen Wiederholungscode:
n = 5 ⇒ RC = 1/5 u1 = (0) → c1 = (0 0 0 0 0) und u2 = (1) → c2 = (1 1 1 1 1)
gestörte Empfangsfolgen:f1 = (0 1 0 0 1) und x1 = (1 1 1 1 1) y1 = x1 + f1 = (1 0 1 1 0) →f2 = (1 1 0 1 0) und x2 = (0 0 0 0 0) y2 = x2 + f2 = (1 1 0 1 0) →
zwei Fehler korrigierbar, vier Fehler erkennbar
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 102FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Paritätskontrolle (parity check code)k Informationsbits, eine Prüfstelle (m = 1) → n = k + 1
2k Codewörter
c = (u p) mit p = u0 + u1 + u2 + ... + uk−1
(gerade Anzahl von Einsen in den Codewörten c)
Paritätskontrolle ist systematisch
kein Fehler korrigierbar, ungerade Anzahl von Fehlern erkennbar
Paritätskontrolle:
s0 = y0 + y1 + y2 + ... + yn−1 = 0 → kein Fehler
s0 = y0 + y1 + y2 + ... + yn−1 = 1 → Fehler
(3.7)
52
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 103FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Beispiel: k = 3
y1 = ( 0 1 1 0) → kein Fehler
y2 = ( 1 1 1 0) → Fehler
Codewort Information Prüfstellec0 000 0c1 001 1c2 010 1c3 011 0c4 100 1c5 101 0c6 110 0c7 111 1
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 104FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Hamming-CodeKorrektur eines einzelnen Fehlers in einem Codewort
Beispiel: (7,4)-Hamming-Code
Kontrollstellen:c4 = c0 + c1 + c2
c5 = c0 + c1 + c3
c6 = c0 + c2 + c3
u0 u1 u2 u3
↓ ↓ ↓ ↓c0 c1 c2 c3 c4 c5 c6
(3.8)(3.9)
(3.10)
53
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 105FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Matrix-Darstellung von Blockcodesx = u G
G = Generator-Matrix (k × n -Matrix)
Systematische Blockcodes:
G = [Ik P]
Ik = Einheitsmatrix k × k, P = Prüfstellenmatrix k × (n − k)
Beispiel: (7,4)-Hamming-Code
(3.11)
(3.12)
=
110|101|011|111|
1000010000100001
G (3.13)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 106FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Fortsetzung: (7,4)-Hamming-Code
Berechnung von Codewörtern durch Matrixmultiplikation
Anzahl von Codewörtern: 2k = 16
Anzahl möglicher Empfangswörter: 2n = 128
( ) ( )
110|101|011|111|
1000010000100001
001|10011001
u x
G
54
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 107FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Codewort-Tabelle
Codewort Information Prüfstellenc8 1000 111c9 1001 100c10 1010 010c11 1011 001c12 1100 001c13 1101 010c14 1110 100c15 1111 111
Codewort Information Prüfstellenc0 0000 000c1 0001 011c2 0010 101c3 0011 110c4 0100 110c5 0101 101c6 0110 011c7 0111 000
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 108FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Eigenschaften von linearen Blockcodes:
Jedes Codewort ist eine Linearkombination von Zeilen von G.
Der Code setzt sich aus allen Linearkombinationen von Gzusammen.
Die Summe von Codewörtern ist wieder ein Codewort.
Im Code ist der Nullvektor (0 0 0 ... 0) enthalten.
⇒ Ein Code ist linear, wenn er als Matrixmultiplikation x = u Gbeschrieben werden kann (u beliebig).
Generatormatrix: Zeilen müssen linear unabhängig sein
55
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 109FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
elementare Zeilenoperationen ändern einen Code nichtVertauschung zweier ZeilenMultiplikation einer Zeile mit einem Skalar ungleich 0Addition einer Zeile zu einer anderen
Die minimale Distanz zweier Codewörter entspricht dem minimalen Gewicht:
Beweis:
( )( ) minH
212121Hmin;|)(min
;,|),(minww
dd=≠∈=
≠∈=0ccc
ccccccC
C
(3.14)( )( )( )( )0ccc
0ccc0cccccc0
cccccc
≠∈=≠∈=
≠∈+=≠∈=
;|)(min;|),(min
;,|),(min;,|),(min
H
H
212121H
212121Hmin
C
C
C
C
wdddd
■
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 110FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Fehlerkorrektur mit dem (7,4)-Hamming-Code:Auswertung der Prüfgleichungen:s0 = y0 + y1 + y2 + y4
s1 = y0 + y1 + y3 + y5
s2 = y0 + y2 + y3 + y6
Syndrom : s = (s0 s1 s2)
Symdrom hängt nicht vom Codewort ab, nur vom Fehler
Zuordnung der Fehlerposition
(3.15)(3.16)(3.17)
SyndromFehlerposition s0 s1 s2
kein Fehler 0 0 0Fehler in 0. Stelle 1 1 1Fehler in 1. Stelle 1 1 0Fehler in 2. Stelle 1 0 1Fehler in 3. Stelle 0 1 1Fehler in 4. Stelle 1 0 0Fehler in 5. Stelle 0 1 0Fehler in 6. Stelle 0 0 1
56
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 111FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Decodierung von Hamming-Codes:Auswertung der Prüfgleichungen → SyndromFehlerposition aus SyndromtabelleFehlerkorrektur: „1“ an der Fehlerposition addieren
m = n − k Kontrollstellen adressieren 2m − 1 Positionen (Nullvektor)Blocklänge: n = 2m − 1mögliche Parameter für Hamming-Codes:
(2m − 1,2m − 1 − m)-Blockcode
(3.18)
m 2 3 4 5 6 7 8n 3 7 15 31 63 127 255k 1 4 11 26 57 120 247
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 112FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Prüfmatrix
Definition: c HT = 0 für alle c ∈ C
und x HT ≠ 0 für alle x ∉ CEigenschaften der Prüfmatrix:
0 = c HT = (u G) HT = u (G HT) → G HT = 0
→ Generatormatrix und Prüfmatrix sind orthogonal
elementare Zeilenoperationen für H sind erlaubt
Prüfmatrix: H = (PT In − k) mit G = [Ik P]H ist (n − k) × n -Matrix
(3.20)
(3.19)
(3.21)
57
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 113FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Nachweis der Orthogonalität:
Dualer Code
Code C : Generatormatrix G, Prüfmatrix H
dualer Code Cd : Generatormatrix Gd = H, Prüfmatrix Hd = G
Codewörter der beiden Codes sind orthogonal:
mit c = u G ∈ C und cd = v H ∈ Cd gilt:
(3.23)
(3.22)( ) 0PPIPPII
PPIHG =+=+=
= −−
knkkn
kT
( ) ( ) 0TTTTTd ==== v0uvHGuHvGucc
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 114FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Beispiel für duale Codes:
Wiederholungscode
Paritätskontrolle:
(3.24)
(3.25)
( )111|1 L=G
=
10000
010001
||||
1
11
L
OM
M
L
MH
( )111|1 L=H
=
10000
010001
||||
1
11
L
OM
M
L
MG
58
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 115FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Syndromberechnung in Matrix-Schreibweise:
s = y HT
Eigenschaften des Syndroms:
Syndrom ist Nullvektor nur dann, wenn y ein Codewort ist
Syndrom ist unabhängig vom Codewort:
s = y HT = (x + f) HT = f HT
alle Fehlervektoren f werden erkannt, die nicht Codewörter sind
(3.26)
(3.27)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 116FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Beispiel: (7,4)-Hamming-Code
=
110|101|011|111|
1000010000100001
G
=
1101
1011
0111
P
== −
100
010
001
|||
110
101
011
111
)I( TknPH
59
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 117FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Beispiel: (7,4)-Hamming-Code
s = y HT
( ) ⇔
−−−=
100010001
110101011111
610 yyy Kss0 = y0 + y1 + y2 + y4s1 = y0 + y1 + y3 + y5s2 = y0 + y2 + y3 + y6
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 118FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Konstruktionsvorschrift für Hamming-Codes
Syndrom hängt nur von Fehlervektor ab:
s = f HT
ein Einzelfehler an der Stelle i (fi = 1) führt zu einem Syndrom, das der entsprechenden Zeile von HT entspricht
alle Zeilen von HT müssen sich unterscheiden, damit die Fehlerposition eindeutig bestimmt werden kann
keine Zeile von HT darf ein Nullvektor sein
⇒ Die Zeilen von HT / Spalten von H werden durch alle möglichen Sequenzen bis auf den Nullvektor gebildet
(3.28)
60
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 119FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Prüfmatrix eines systematischen Hamming-Codes:
Beispiel: (15,11)-Hamming-Code
== −
10000
010001
||||
11
1101
)I( T
L
OM
M
L
LL
LLMM
LL
LL
knPH
alle möglichen Spaltenvektoren mit mehr als einer 1
=
1000010000100001
|110|101|011|000
1001010100111110
1101101101111111
H
(3.29)
(3.30)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 120FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Modifikationen linearer CodesExpandieren (extending): Anhängen zusätzlicher Prüfstellen
n' > n, k' = k, m' > m, RC' < RC, dmin' ≥ dmin
Punktieren (puncturing): Reduktion von Prüfstellen
n' < n, k' = k, m' < m, RC' > RC, dmin' ≤ dmin
Verlängern (lengthening): Anhängen zusätzlicher Informationsstellen
n' > n, k' > k, m' = m, RC' > RC, dmin' ≤ dmin
Verkürzen (shortening): Reduktion von Informationsstellen
n' < n, k' < k, m' = m, RC' < RC, dmin' ≥ dmin
61
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 121FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Beispiel: Hamming-Code: ein Fehler korrigierbar durch Syndrom-Auswertungzwei Fehler führen ebenfalls auf s ≠ 0
erweiterter (expandierter) Hamming-Code: Unterscheidung zwischen 1- und 2-Fehlersituation durch zusätzliche Prüfstelle(2m,2m − 1 − m)-BlockcodeGeneratormatrix des erweiterten Hamming-Codes:
=
1
11
HextH,M
GG (3.31)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 122FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Fehlerereignisse:
kein Fehler: s = 0
ein Fehler: s ≠ 0, sm+1 = 1
zwei Fehler: s ≠ 0, sm+1 = 0
Decodierung:
s = 0 : Empfangsvektor = Codewort
s ≠ 0, sm+1 = 1 : ungerade Anzahl von Fehlern ⇒ ein Fehler angenommen und durch Syndrom-Auswertung korrigiert
s ≠ 0, sm+1 = 0 : gerade Anzahl von Fehlern ⇒ Fehler können nicht korrigiert werden
62
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 123FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Fehlerkorrektur und Fehlererkennungminimale Distanz zwischen Codewörtern:
dmin = 1 : einzelner Fehler kann dazu führen, dass Fehler weder erkennbar noch korrigierbar ist
dmin = 2 : mindestens ein einzelner Fehler kann erkannt werden
dmin = 3 : mindestens ein einzelner Fehler kann korrigiert werden
mindestens zwei Fehler können erkannt werden
( )C∈= 2121Hmin ,|),(min ccccdd (3.32)
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 124FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Fehlerkorrektur und Fehlererkennung
Anzahl erkennbarer Fehler: te = dmin − 1Anzahl korrigierbarer Fehler
dmin ist gerade: t = (dmin − 2) / 2dmin ist ungerade: t = (dmin − 1) / 2
dmin = 3 dmin = 4
(3.33)
(3.34)(3.35)
63
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 125FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Singleton-Schranke: Mindestdistanz und Mindestgewicht eines linearen Codes sind beschränkt durch:
Beweis: systematisches Codewort mit einer Informationsstelle ungleich 0
Gewicht / Distanz in Informationsstellen: dH,Information = 1
Gewicht / Distanz in Prüfstellen: dH,Prüf ≤ m = n − k
Ein Code, für den das Gleichheitszeichen in (3.36) gilt, heißt maximum distance separable (MDS)
mknwd +=−+≤= 11minmin (3.36)
■
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 126FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Fehlererkennung:
(3.33): te + 1 = dmin ≤ 1 + m ⇒ m ≥ te
mindestens 1 Prüfstelle pro erkennbarem Fehler notwendig
Fehlerkorrektur:
(3.34, 3.35): (dmin − 1) / 2 ≥ t ≥ (dmin − 2) / 2
2 t + 1 ≤ dmin ≤ 1 + m ⇒ m ≥ 2 t
mindestens 2 Prüfstellen pro korrigierbarem Fehler notwendig
(3.37)
(3.38)
64
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 127FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Decodierkugel: n-dimensionale Kugel um Codewort mit Radius t – alle Vektoren im Innern der Decodierkugeln werden als zugehöriges Codewort decodiert
Gesamtzahl aller Vektoren innerhalb von Decodierkugeln ≤Gesamtzahl aller möglichen Vektoren ⇒
Hamming-Schranke:Für einen binären (n,k)-Blockcode mit der Korrekturfähigkeit tgilt:
(3.39)nt
i
kin
220
≤
∑=
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 128FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Beweis:Anzahl von Vektoren um ein Codewort mit dH = 1:
Anzahl von Vektoren um ein Codewort mit dH = 2:
Anzahl von Vektoren um ein Codewort mit dH = t:
mit
Gesamtzahl aller Vektoren innerhalb von Decodierkugeln:
(3.40)
1n
tn
2n
1)1())1(()1(
⋅⋅−⋅−−⋅⋅−⋅=
K
K
tttnnn
tn
nktnnnn
2210
2 ≤
++
+
+
K ■
65
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 129FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Perfekte Codes (dichtgepackte Codes)in (3.39) gilt Gleichheitszeichenkeine Codewörter liegen zwischen den Codierkugelnnur sehr wenige bekannte Codes sind perfekt
Beispiel: (7,4)-Hamming-Codedmin = wmin = 3 ⇒ t = 1
Hamming-Codes sind perfekt
7
74
2128)71(16
217
07
2
==+⋅
≤
+
⋅
Prof. Dr.-Ing. Andreas Czylwik Grundlagen der Nachrichtentechnik 4SS 2003
S. 130FachgebietNachrichtentechnische Systeme
GerhardMercatorUniversitätDuisburg
N T S
Nachrichtentechnik 43 Kanalcodierung in der Nachrichtenübertragung
Plotkin-Schranke:Für einen binären (n,k)-Blockcode mit der minimalen Distanz dmingilt:
Näherung:
Beweis: minimales Gewicht ≤ mittlerem Gewichtmittleres Gewicht einer Stelle eines Codeworts: 1/2mittleres Gewicht eines Codeworts der Länge n: n/2mittleres Gewicht ohne Nullvektor:
(3.41)122 1
min−
⋅≤−
k
knd
12für2min >>≤ knd
122
2 −⋅ k
kn■