Kodierungstheorie: Lineare Kodes
Seminararbeit
Sommersemester 2015
Bearbeitet von:
Sebastian Gombocz
(Matrikelnummer: 48947)
Christian Löhle
(Matrikelnummer: 48913)
Betreuer:
Prof. Dr. Thomas Thierauf
Hochschule für Technik und Wirtschaft Aalen
Fakultät Elektronik und Informatik
Studiengang Informatik
Inhaltsverzeichnis
1 Einleitung
1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Abgrenzung Informationstheorie . . . . . . . . . . . . . . . . . . . . .
1.3 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
2
3
2 Grundlagen
2.1 Algebra . . . . . .
2.2 Kodierung . . . . .
2.3 Hamming-Abstand
2.4 Fehlermuster . . . .
2.5 Fehlererkennung . .
2.6 Mindestdistanz . .
2.7 Fehlerkorrektur . .
2.8 Zusammenfassung .
.
.
.
.
.
.
.
.
4
4
4
4
5
5
5
6
7
3 Lineare Kodes
3.1 Generatormatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Kontrollmatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Syndrom-Dekodierung . . . . . . . . . . . . . . . . . . . . . . . . . .
8
8
9
9
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Zyklische Kodes
10
4.1 Reed-Solomon Kodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Literaturverzeichnis
12
1
1 Einleitung
1.1 Definition
Die Kodierungstheorie ist eine Teilgebiet der Mathematik, das sich mit Kodierung
von Informationen mit der Absicht Fehler bei der Übertragung zu erkennen und
eventuell zu korrigieren. Ausgangspunkt ist dazu ein Modell[5], das folgendermaßen
aufgebaut ist:
Die Problemstellung der Kodierungstheorie ist es über einen störungsbehafteten
Kanal eine zuverlässige Datenübertragung herzustellen. Hierbei wird abstrahiert,
dass jedes Bit die gleiche Wahrscheinlichkeit p hat, fehlerhaft übertragen zu werden.
Es muss p 6= 12 gelten, für p < 12 wird das übertragene Bit immer invertiert, somit
erhält man p > 12 . (Anmerkung: Diese Abstraktion ist nicht immer zutreffend in
der Praxis, bei einer kurzfristigen Störung der Leitung könnten in einem kurzen
Zeitraum sehr viele Bits beschädigt worden sein.)
1.2 Abgrenzung Informationstheorie
Shannon gilt als Pionier der Informationstheorie, das oben abgebildete Modell wurde
von ihm eingeführt. Anhand des Modells lässt sich die Abgrenzung zur Informationstheorie leicht erklären. Die Kodierungstheorie beschäftigt sich nur mit der Kommunikation zwischen Sender und Empfänger. Die Theorie der Kommunikation kann
so aufgeteilt werden, in die Informationstheorie, die sich damit beschäftigt möglich
effizient Informationen festhalten zu können. Wohingegen die Kodierungstheorie die
Informationen für die Übertragung redundant, aber dafür fehlerresistent, macht.
2
1.3 Anwendung
Kodierungstheorie wird in der Praxis sowohl bei der Datenübertragung als auch bei
der Datenspeicherung eingesetzt. Bei der Datenübertragung kann bei Fehlererkennung die Information erneut gesendet werden, dies erzeugt Verzögerung und könnte
in manchen Szenarien sehr teuer sein, deshalb kommen hier nicht nur fehlererkennende sondern auch fehlerkorrigierende Kodes zum Einsatz.
Bei Der Datenspeicherung hingegen, ist es oft nicht möglich, an die Information
zu kommen, wenn diese fehlerhaft vorliegt, z.B. durch einen Defekt des physischen
Datenträgers. Ohne Fehlerkorrigierende Kodes wären diese Daten unter Umständen
nicht wiederherstellbar.
3
2 Grundlagen
Dieses Kapitel bezieht sich großteils auf [2].
2.1 Algebra
Die Kodierungstheorie beschränkt sich, sofern es nicht von Nöten ist, nicht auf das
binäre System zum Übertragen von Nachrichten. Diese Arbeit wird das allerdings
großteils tun um das Thema nicht zu abstrakt vorzutragen. Besonders wichtig ist
das exklusive Oder(XOR) und die Multiplikation, da diese einen Körper bilden. In
der Literatur wird der Körper (Z2 , +, ∗) oft mit GF (2)(Galois Field of two elements,
zu deutsch: Endlicher Körper mit zwei Elementen) notiert. Im folgenden sind + und
∗ also immer in Z2 zu verstehen.
2.2 Kodierung
Es gilt eine Menge Nachrichten M , wobei jedes m ∈ M aus k bits besteht, auf eine
Menge Kodewörter C, wobei jedes c ∈ C aus n bits besteht, abzubilden. Daraus folgt
direkt das n ≥ k gelten muss. Es wird ausserdem angenommen das |M | = |C| = 2k ,
die Nachrichtenmenge M also ihre Bits komplett ausnutzt. Die Abbildung wäre für
die Kodierung nutzlos, wenn sie nicht injektiv wäre, da ansonsten Informationen der
Nachricht verloren gehen würde.
Definition: Ein Kode C ist eine Injektive Abbildung: C : {0, 1}k → {0, 1}n .
In der Literatur und auch in dieser Arbeit, wird C doppelt belegt: Als Kode im
Sinne einer Abbildung und als Menge aller Kodewörter des Kodes(Wertemenge von
C).
2.3 Hamming-Abstand
Das Hamming-Gewicht eines Wortes ist die Anzahl der Bits die nicht null sind,
notiert als weight(c). Der Hamming-Abstand zweier Wörter c1 und c2 ist definiert
als weight(c1 + c2 ) anders ausgedrückt: Die Anzahl an Stellen an denen sich c1 und
c2 unterscheiden.
Notiert wird der Hamming-Abstand zweier Kodewörter c1 und c2 mit d(c1 , c2 ).
4
2.4 Fehlermuster
Das Fehlermuster e ist das Wort, das das Störsignal auf das zu übertragene Kodewort
addiert. Wenn weight(e) = 0, wurde die Nachricht ungestört übertragen. Wenn
weight(e) = 1 ist bei der Fehlerübertragung ein Bit falsch übertragen worden, usw.
2.5 Fehlererkennung
Man sagt ein Kode erkennt das Fehlermuster e, wenn für alle Kodewörter c ∈ C
gilt, dass c + e ∈
/ C. Der Kode erkennt also, dass ein Fehler e bei der Übertragung
geschehen ist und das Kodewort verfälscht wurde. Es muss e nicht bestimmen können. Die Konsequenz ist das empfangene Wort zu verwerfen und neu anzufordern.
Allerdings existiert bei Kodes mit |M | > 1 immer auch ein e das nicht vom Kode
erkannt wird, also dass c1 + e = c2 gilt für c1 , c2 ∈ C. Ein Kode ist i-fehlererkennend
wenn er alle e mit weight(e) ≤ i erkennt. Als Beispiel sei M = 0, 1 und C = 00, 11.
Eine Nachricht m ∈ M wird kodiert in dem das Bit wiederholt wird.
Behauptung: C ist 1-fehlererkennend, d.h. der Kode erkennt alle Fehler solang nur
maximal 1 Fehler pro Übertragung passiert.
Zu zeigen: c + e ∈
/ C ∀e mit weight(e) ≤ 1.
c
00
00
11
11
e
01
10
01
10
c0
01
10
10
01
Da c0 die Werte 01, 10 ∈
/ C annimmt, kann ein Fehlermuster mit Hamming-Gewicht
1 immer erkannt werden. 2.6 Mindestdistanz
Die Mindestdistanz ist das Minimum der Hamming-Abstände die alle Paare c1 , c2 ∈
C haben.
Definition: Mindestdistanz = min(d(c1 + c2 ) ∀c1 , c2 ∈ C).
Notiert wird diese Eigenschaft eines Kodes C mit minweight(C). Wenn C trivial ist
und m = c für alle m ∈ M gilt, gilt offensichtlich minweight(C) = 1, da die Nachrichten sich nur in einem Bit unterscheiden. Das vorige Beispiel war C = {00, 11}
also gilt minweight(C) = 2. Wie viele Fehler ein Kode erkennt ist von seiner Mindestdistanz abhängig:
Satz: Ein Kode C mit Mindestdistanz d erkennt alle Fehlermuster e mit weight(e) =
d − 1.
5
Beweis: Sei e ein beliebiges Fehlermuster mit weight(e) ≤ d − 1 und c das zu übertragene Kodewort. Zu zeigen ist, dass der Fehler erkannt wird..
Das empfangene Wort ist c+e. Der Abstand vom Kodewort zum empfangenen Wort
ist weight(c + c + e) = weight(e) und weight(e) ≤ d − 1 also gilt weight(e) < d.
Angenommen c + e ∈ C, dann ist d(c, c + e) = weight(e) also gilt d(c, c + e) < d,
dies ist ein Widerspruch, da d die Mindestdistanz von C ist, d.h. zwei Kodewörter
mindestens Abstand d haben müssen. Satz: Für einen Kode C mit Mindestdistanz d gibt es ein Fehlermuster e mit
weight(e) = d das nicht erkannt wird.
Beweis: Da die Mindestdistanz d ist, gibt es zwei Kodewörter c1 , c2 ∈ C so dass gilt
weight(c1 + c2 ) = d.
Ist nun c1 das zu übertragene Wort und c1 +c2 das Fehlermuster, wird c2 empfangen,
da c1 + c1 + c2 = c2 . Das Fehlermuster wird nicht korrigiert, da c2 ∈ C. Der zweite Satz zeigt, dass der erste Satz maximal formuliert ist.
2.7 Fehlerkorrektur
Um nun auch einen Fehler zu korrigieren wird Maximum Likelihood Decoding(MLD)
angewandt. Wird ein Fehler erkannt, wird er zum nächstliegenden Kodewort korrigiert. Das bedeutet allerdings, dass MLD auch falsch korrigieren kann wenn weight(e)
groß genug ist. Da Fehlermuster mit niedrigem Gewicht wahrscheinlicher sind, korrigiert MLD meist richtig.
Definition: Ein Kode C heißt i-fehlerkorrigierend, wenn er alle Fehlermuster e mit
weight(e) ≤ i korrigiert.
Beispiel: M = 0, 1 und C = {000, 111}, es wird das Nachrichtenbit 3 mal wiederholt.
Behauptung: C ist 1-fehlerkorrigierend.
Beweis: Fehlermuster E mit e ∈ E und weight(e) = 1 für alle e sind E = {001, 010, 100}.
Die Fehlermuster verändern nur 1 Bit, Nachrichtem M = {000, 111} sind aber 3 Bit
entfernt. Folgerung: Es bräuchte ein e mit weight(e) = 2 um eine falsche Korrektur
6
zu ermöglichen. . Auch die Fehlerkorrigerbarkeit hängt direkt von der Mindestdistanz ab:
Satz: Ein Kode C mit Mindestdistanz d korrigiert alle Fehlermuster e mit weight(e) ≤
b(d − 1)/2c.
Satz: Für einen Kode C mit Mindestdistanz d gibt es ein Fehlermuster e mit
weight(e) = d das nicht erkannt wird.
2.8 Zusammenfassung
In diesem Kapitel wurde gezeigt, dass sowohl Fehlererkennbarkeit als auch Fehlerkorrigierbarkeit direkt von der Mindestdistanz abhängen. Die Parameter eines (binären)
Kodes C lassen sich also mit Länge der Nachrichten n, Länge der Kodewörter k und
Mindestdistanz d vollständig beschreiben.
Definition: Ein Kode C ist ein (n, k, d) Kode wenn die Länge der Nachrichten
n ist, die Länge der Kodewörter k ist und die Kodewörter eine Mindestdistanz von
d haben.
7
3 Lineare Kodes
Der Nachteil an der bisherigen Vorgehensweise einen Kode explizit als Abbildung
anzugeben, also für jedes m ∈ M ein c ∈ C anzugeben, ist die Größe der Darstellung
und damit der Kodierungs- und Dekodierungsaufwand.
Viele Kodes lassen sich auch angeben ohne die komplette Wertemenge auszuschreiben, eine weit verbreitete Art solcher Kodes sind die linearen Kodes.
Alle Kodewörter werden als Vektoren interpretiert, dies ermöglicht die Anwendung
bereits bekannter Verfahren der Linearen Algebra.
Definition: Ein Kode ist ein linearer Kode, wenn die Kodewörter einen Untervektorraum von Fn2 bilden.
Ein Untervektorraum U von einem Vektorraum (V, +, ∗) ist eine nichtleere Teilmenge U ⊆ V die unter der Vektoraddition und der Skalarmultiplikation abgeschlossen
ist.
Diese Eigenschaften sind einfacher zu erfüllen, als man auf den ersten Blick vielleicht
denkt.
Die Skalarmultiplikation resultiert nur in den Nullvektor, durch 0 als Skalar, und in
c selbst, durch 1 als Skalar. Eine hinreichende und notwendige Bedingung folgt also
direkt daraus: Der Nullvektor muss ein Kodewort sein.
Die Abgeschlossenheit der Vektoraddition fordert, das ∀c1 , c2 ∈ C auch c1 + c2 ∈ C.
3.1 Generatormatrix
Vektorräume und damit auch Untervektorräume haben eine Basis, eine Menge von
linear unabhängigen Vektoren, dessen Linearkombination den kompletten Vektorraum aufspannt.
In dem letzten Abschnitt wurden Kodes definiert die einen Vektorraum bilden und
sich damit die Basis zunutzen machen können um nicht alle Kodewörter angeben zu
müssen.
Definition: Eine k × n Matrix dessen Zeilen eine Basis für einen (n, k, d) Kode
C bilden, nennt man Generatormatrix.
Jede Linearkombination kann mit einem Vektor der Länge k dargestellt werden,
dieser Vektor ist die zu kodierende Nachricht des Kodes. Um nun eine Nachricht in
8
das zugehörige Kodewort umzuwandeln reicht es G ∗ mT zu berechnen, wobei G die
Generatormatrix ist.
Es gibt eine einheitliche Form eine Generatormatrix anzugeben:
Definition: Eine Generator-Matrix G die den Aufbau G = [Ik |P ] hat ist in systematischer Form.
Ik ist dabei die k × k Identitätsmatrix und P der Paritätsteil, der die Redundanz
hinzufügt. Jeder lineare Kode kann in einen äquivalenten Kode in systematischer
Form gebracht werden.
3.2 Kontrollmatrix
Die Generatormatrix aus dem letzten Abschnitt hilft, zumindest offensichtlich, nicht
bei der Dekodierung weiter. Es gilt eine zweite Matrix zu finden, die die Kodierung
rückgängig macht:
Definition: Eine Matrix H, für die ∀c ∈ C HcT = 0 gilt, nennt man Kontrollmatrix. Ist die Generatormatrix G in systematischer Form G = [Ik |P ] dann ist die
Kontrollmatrix H = [P T |In − k], da GH T = P − P = 0.
3.3 Syndrom-Dekodierung
Die Kontrollmatrix wie sie bisher erläutert wurde, hilft nur um zu überprüfen ob
ein empfangenes Wort ein Kodewort ist, allerdings lässt sie sich auch zur MaximumLikelihood Dekodierung nutzen.
Um noch einmal zu veranschaulichen:
Bei bisherigen Kodes musste der Fehlervektor des empfangenes Vektors ’erraten’
werden, indem die Liste alle Kodewörter durchlaufen wird, um zu sehen welches am
nächsten liegt.
Man kann sich die Kontrollmatrix folgendermaßen zu Nutze machen, dabei sei c0 das
empfangene Wort, c das gesendete Kodewort und e der Fehlervektor.
Für das Syndrom s = Hc0 gilt:
Hc0 = H(c + e) = H(c) + H(e) = 0 + H(e) = H(e).
Diese Fehlerkorrektur wird effizient wenn man im Vorfeld eine Tabelle aller Syndrome(auch Syndrom-Tabelle) und deren zugehöriges Kodewort berechnet und beim
Dekodieren nur einen Table-Lookup durchführen muss.
9
4 Zyklische Kodes
Eine in der Praxis besonders relevante Teilmenge der linearen Kodes stellen die zyklischen Kodes dar.
Definition: Ein linearer Kode heißt zyklischer Kode, wenn jede bitweise Verschiebung eines Kodewortes ebenfalls ein Kodewort ist.
Die bisherige Darstellung von linearen Kodes macht Verschiebungen sehr schwer, da
sie nur in Form der Generatormatrix angegeben werden. Für zyklische Kodes ist die
Angabe von Generatorpolynomen geläufiger.
Die Idee dabei ist es, das Bit als Koeffizient und die Stelle als Potenz zu nutzen,
dadurch lässt sich ein Kodewort in ein Polynom umwandeln.
Beispiel: Sei c = 11001011 ein Kodewort. Das zugehörige Polynom ist dann: c(x) =
1 + x + x4 + x6 + x7 .
Die Verschiebungen von c sind xi c(x) (mod xn − 1) für alle i. Eine Multiplikation des Polynoms mit xi bedeutet also eine Rechts-Verschiebung um i Positionen.
Zusammen mit der Linearität folgt daraus, dass das Produkt zweier KodewortPolynome c1 und c2 ebenfalls ein Kodewort ist:
c1 (x)c2 (x) (mod xn − 1) ∈ C
Dies ist offensichtlich wenn man die Multiplikation als eine Linearkombination von
xi c2 (x) sieht.
Definition: Ein Polynom g(x) heißt Generator-Polynom von Kode C wenn für jedes
Kodewort c(x) und das dazugehörige Nachrichtenwort w(x) gilt: c(x) = w(x) ∗ g(x).
Damit ist ein Kodewort ein Vielfaches des Generator-Polynoms.
Jeder zyklische Kode besitzt ein eindeutiges Generator-Polynom mit minimalem
Grad.
4.1 Reed-Solomon Kodes
Reed-Solomon Kodes(RS-Kodes) sind zyklische Kodes die vielerlei Anwendung finden, zum Beispiel bei der Kodierung von CD’s oder bei der Übertragung von Nachrichten in der Raumfahrt.
Man wählt einen Vektor a = (a1 , a2 , ..., an ) wobei die ai jeweils verschieden sein
müssen. Daraus folgt, dass eine Betrachung von F2 nur bedingt Sinn macht, da n
10
auf zwei beschränkt ist, deshalb betrachtet man bei RS-Kodes Fq . Es muss dann
offensichtlich n ≤ q gelten.
Fq ist nur dann ein Körper, wenn q eine Primzahlpotenz ist, deshalb wird dies im
folgenden vorausgesetzt.
Die Nachricht m wird als Polynom p(x) betrachtet, wie im vorigen Abschnitt beschrieben. Zu einer Nachricht p(x) ist das Kodewort dann p = (p(a1 ), p(a2 ), ..., p(an )).
Satz: Ein RS-Kode hat die Parameter (n, k, n − k + 1).
Beweis: Zu zeigen ist lediglich, dass die Minimaldistanz d den Wert n − k + 1 besitzt,
n und k ergeben sich direkt aus der Definition.
Seien m1 , m2 zwei Nachrichten für die gilt m1 6= m2 , die dazugehörigen Kodewörter p1 und p2 sind die n Stellen des Polynoms für x = a1 , x = a2 : ... x = an .
Nach Definition sind diese x Werte verschieden. Nun kann der Fundamentalsatz der
Algebra angewandt werden: Zwei unterschiedliche Polynome mit Grad ≤ k haben
≤ k − 1 Schnittpunkte. Es wurden n Punkte ausgewertet, schlimmsten Falls befinden sich alle Schnittpunkte darunter also sind noch n−(k−1) Punkte verschieden. Eine Dekodierung kann ebenfalls über das Syndrom durchgeführt werden, allerdings
bieten Verfahren an, die auf Schaltungen effizienter durchzuführen sind.
Reed-Solomon Kodes haben neben der effizienten Kodierung und Dekodierung noch
andere Vorteile gegenüber allgemeinen linearen oder zyklischen Kodes.
Ein großer Vorteil ist, dass die Mindestdistanz nicht nur bekannt ist, sondern sogar
über die anderen beiden Parameter fixiert werden kann.
Für (binäre) lineare Kodes hingegen, ist das Problem den Mindestabstand zu berechnen NP-Hart, das zugehörige Entscheidungsproblem NP-vollständig[6].
11
5 Literaturverzeichnis
[1] Rudi Piotraschke Dagmar Schönfeld, Herbert Kliment. Informations- und Kodierungstheorie. Springer, 2012.
[2] D. G. Hoffman. Coding Theory - The Essentials. Marcel Dekker Inc, 1991.
[3] Dirk W. Hoffmann. Einführung in die Informations- und Codierungstheorie.
Springer, 2014.
[4] Ralph-Hardo Schulz. Codierungstheorie - Eine Einführung. Vieweg, 1991.
[5] C. E. Shannon. A mathematical theory of communication. The bell System
Technical Journal, 1948.
[6] Alexander Vardy. The intractability of computer the minimum distance of a
code. Transactions on Information Theory, 1997.
12
© Copyright 2024 ExpyDoc
