Codierungstheorie

Allgemeines

Die Codierungstheorie dient dazu eine möglichst angemessene Art der Datenübertragung zu finden. Die eigentlichen Daten sollen möglichst mit kleinen Worten, jedoch auch ohne Störungen übertragen werden. Der wesentlichste Teil der Codierung ist die Erkennung und Korrektur von Fehlern.

Begriffe

Nachricht: eine Wirkung unabhängig vom Träger, eine Nachricht besteht aus Zei

chen und die sind Teile eines Alphabets, eine Nachricht ist eine Zei

chenfolge (d.h. ein Wort)

Information: Gehalt/Inhalt der Nachricht

Signal: physikalischer Träger der Nachricht

Zeichen: ist die Elementarmenge einer Nachricht

Alphabet: ist ein endlicher Satz von Zeichen, alle Zeichen eines Zeichensystems

Nachrichtenraum: alle mögl. Nachrichten in einem Alphabet

Störung: Verfälschung der Information

Alphabetumfang: Anzahl der Zeichen hoch Wortlänge

Nutzwörter: Die Wörter die ich verwenden kann

Pseudowörter: nicht verwendete Wörter

Abstand: Anzahl der Stellen an denen sich zwei Codewörter voneinander unter

scheiden

Bsp: Zeichen: 0,1

Wortlänge: 2

Nachrichtenraum: 00, 01, 10, 11

Bsp: Zeichen: 0,1

Wortlänge: 3

Nachrichtenraum: 000, 001, 010, 011, 100, 101, 110, 111

Alphabetumfang:

000 A

001 - Nutzwort (WN)

010 - Alphabetumfang (AU)

011 B Pseudowort (WP)

100 -

101 C

110 D

111 -

AU = WN + WP

AU = ZeichenanzahlWortlänge

Distanz:

Dies ist die Anzahl der Stellen an denen sich zwei Wörter voneinander unterscheiden.

Bsp:

x

y

Zeichen

0

0

A

0

1

B

1

0

C

1

1

D

Distanz: A-B=1, A-C=1, A-D=2, B-C=2, B-D=1, C-D=1

Hamming-Distanz:

Diese Distanz zeigt, wie groß die kleinste Distanz in einem Code ist. Hierfür muss jedes Wort mit allen anderen verglichen werden. Die Hamming-Distanz dient dazu Fehler zu erkennen bzw. sie zu beseitigen. Denn je größer die Hamming-Distanz eines Codes ist, desto eher kann ein Fehler erkannt werden. Die Erkennung und Behebung von Fehlern macht die Qualität eines Codes aus.

000

001

010

011

100

101

110

111

000

0

1

1

2

1

2

2

3

001

1

0

2

1

2

1

3

2

010

1

2

0

1

2

3

1

2

011

2

1

1

0

3

2

2

1

100

1

2

2

3

0

1

1

2

101

2

1

3

2

1

0

2

1

110

2

3

1

2

1

2

0

1

111

3

2

2

1

2

1

1

0

Hamming-Distanz der 8 Wörter des Binärcodes der Wortlänge 3

Anzahl der erkennbaren Fehler: e = HA - 1 HA = Hamming-Distanz(Hammingabstand)

Anzahl der korrigierbaren Fehler: siehe Fehlerkorrigierender Code

Bsp:

000 001 011 010 110 100 101 111

A - B - D - C -

1 aus 10 - Code

1 aus 10 Code

0

0000000001

1

0000000010

2

0000000100

3

0000001000

4

0000010000

5

0000100000

6

0001000000

7

0010000000

8

0100000000

9

1000000000

Paritätskontrolle

Bei der Paritätskontrolle wird ein zusätzliches Parity-Bit angehängt. Dieses Parity-Bit ermöglicht es Fehler bei der Übertragung zu erkennen. Bei dieser Methode werden die Bits die auf 1 gesetzt sind zusammengezählt. Welchen Wert das Parity-Bit dann hat, kann aus der Tabelle entnommen werden.

Ã¥ der "1"-Bits

Parity-Bit

even

Parity-Bit

odd

gerade

0

1

ungerade

1

0

Bsp:

gerade (even) ungerade (odd)

0

0

0

0

0

1

0

1

1

0

1

0

1

0

1

1

0

1

1

1

0

1

1

1

Nun kann man zwar erkennen wenn in der Bitfolge ein Fehler auftritt, sind es allerdings zwei Fehler so heben sie sich gegenseitig auf und man erkennt den Fehler nicht.

Blockparität

Die Blockparität ist eine Verbesserung der einfachen Paritätskontrolle. Bei der Blockparität wird zusätzlich nach einer bestimmten Anzahl von Bitfolgen (Zeilen) eine weitere Bitfolge eingeschoben.

Vorteil: 2-Bit-Fehler werden erkannt

1-Bit-Fehler können nun sogar korrigiert werden

0

1

0

1

0

1

1

1

0

1

0

1

1

0

0

1

1

0

1

1

Fehlerkorrigierender Code

4 gültige Codewörter:

00000 00000, 00000 11111, 11111 00000, 11111 11111

Hammingabstand (HA) = 5

d = = = 2 è Doppelfehler sind korrigierbar

d = behebbare Fehleranzahl

Hamming-Code

Die Hamming-Methode eignet sich zur Korrektur von Einzelfehlern bei einer beliebig großen Zeichenzahl. Die Prüfbits befinden sich an der 1., 2., 4., 8., 16., ... Stelle, je nachdem wieviele Informationsstellen vorhanden sind.

Bsp:

Zeichen ASCII Hamming-Code

H 1001000 00110010000

Prüfbits

Berechnung d. Prüfbits für Parity = even

Stelle

2er Potenz

1. Prüfbit (1)

2. Prüfbit (2)

3. Prüfbit (4)

4. Prüfbit (8)

1

1

0

2

2

0

3

2+1

1

1

4

4

1

5

4+1

0

0

6

4+2

0

0

7

4+2+1

1

1

1

8

8

0

9

8+1

0

0

10

8+2

0

0

11

8+2+1

0

0

0

Erstellung d. Prüfbits (senderseitig)

Datenbits an Stellen ¹ 2neinsetzen

Stellennummer der Datenbits binär zerlegen

Für 1. Prüfbit alle Stellenbits addieren und Parity bilden in deren Zerlegung "1"(20) vorkommt, für 2. Prüfbit alle Stellenbits in deren Zerlegung "2"(21) vorkommt, usw.

Beispiel für Korrektur

00110000000

Bit falsch übertragen

alle Prüfbits ergeben mit ihren Datenbits å =even

außer Prüfbit 1, 2 und 3 (an Stellen #1, #2, und #4)

è bilde å der Stellenzahlen und drehe an der Stelle "å " das Bit um.

Für Fehlerkorrekturcode zur Behebung von Einzelfehlern gilt:

(m + r + 1) 2r

m........ Anzahl der Nachrichtenbits

r......... Anzahl der Prüfbits

Bsp:

Fehlerquote 10-6/Bit

1000 Bits/Block

è 1 fehlerhaftes Bit auf 103Block

è 1 fehlerhaftes Bit auf 106Bit

Sicherung jedes Blockes:

Annahme r=9

103+ 9 + 1 29è Nein

103+ 10 + 1 210è Ja

10 Prüfbits nötig! (zur Fehlerbehebung)

Obgleich nur 1 fehlerhaftes Bit auf 103Blocks!

Zyklische Codes

Die Bezeichnung "zyklisch" beschreibt eine Besonderheit: für jedes zulässige Codewort v ist auch jedes weitere ein Codewort, welches daraus durch zyklische Verschiebung (links oder rechts) hervorgeht. Wenn man also das Codewort va=0001011 hat, so gehören auch die Wörter vb=0010110 oder Vc=1000101 zu diesem Code.

Der denkbare Schluß, dass nämlich der gesamte Code nur aus dem einen Codewort und seinen zyklischen Verschiebungen bestehen könnte, ist falsch; es gibt immer mehrere Basis-Codewörter, die nicht durch zyklische Verschiebung auseinander hervorgehen. Sonst wäre die Menge an verschiedenen Codewörtern auch recht klein.

Allerdings gilt folgende Aussage: ist ein Wort kein Codewort, so trifft dies auch für alle daraus durch zyklische Verschiebung hervorgegangenen Wörter zu.

Wir wollen Informationen gesichert übertragen, die als Dezimalzahlen aus dem Wertebereich 0, 1, 2,....., 15 vorliegen. Da wir zur Sicherung einen Divisionsrest benutzen, der natürlich mit zu übertragen ist, erweitern wir die Stellenzahl des Informationsteils (hier 2 Stellen) um soviele weitere, wie der Rest haben kann. Ist die Zahl 13 unsere Generatorzahl (sie "generiert" oder "erzeugt" nämlich den Rest), so müssen 2 zusätzliche Stellen vorgesehen werden.

Bsp:

15 : 13 = 1 Rest 02, Codewort à 1502

oder

10 : 13 = 0 Rest 10, Codewort à 1010

usw.

Einfacher und sparsamer ist die stellenweise Division. Eigentlich betrachtet man hierbei die Informations- und die Generatorzahl als Koeffizienten eines Polynoms, wobei diese Koeffizienten nur Werte zwischen 0 und 9 annehmen können. Hier ist das Generatorpolynom (Wert 13, siehe vorheriges Bsp)

g(x) = 1x1+ 3x0= x + 3 und statt einer Restzahl erhält man bei einer derartigen Polynomdivision ein Restpolynom. So, wie bei einer Zahlendivision die Restzahl immer kleiner als die Generatorzahl sein wird, hat das Restpolynom stets einen kleineren Grad als das Generatorpolynom. Da in unserem Beispiel das Generatorpolynom vom Grad 1 ist, hat also das Restpolynom den Grad 0. Das heißt zugleich, dass man für den Rest hier nur eine Stelle reservieren muss.

Zweckmäßig ist es, das Informationspolynom vorher noch um soviele Stellen nach links zu schieben, wie man zur Aufnahme des Restpolynoms benötigt. Dieses Linksschieben bewerkstelligt man mathematisch durch Multiplikation mit einem Polynom entsprechenden Grades, was nur aus einer Potenz von x besteht, hier also aus x1.

Aus dem Infopolynom

15 à 1x1+ 5x0= x + 5

entsteht durch Multiplikation mir x1

1x2+ 5x1+ 0x0= x2+ 5x + 0

Bsp:

x2+ 5x + 0 : x + 3 = x + 2 + 4 / (x + 3)

x2+ 3x

0 + 2x + 0

2x + 6

0 + 4 à Rest = 4

Nachdem man den Rest MOD 10 gerechnet hat, erhält man als Codewort-Polynom 1x2+ 5x + 6, oder in Kurzform 156.

Wenn man das Generatorpolynom nun durch das Codewortpolynom dividiert erhält man Null Rest. Falls der Rest ungleich Null ist, wurde das Codewort nicht richtig übertragen.

Division mittels Schieberegister

Bsp: g(x) = 1011

Eingangsfolge w(x) = 1111000

Berechneter Rest: 111

g3 g1 g0

w(x)

t = 0 0 0 0

t = 1 0 0 1 1

t = 2 0 1 1 1

t = 3 1 1 1 1

t = 4 1 0 0 1

t = 5 0 1 1 0

t = 6 1 1 0 0

t = 7 1 1 1 0

Zum Zeitpunkt t=0 haben alle drei Speicherelemente den Zustand 0. Von rechts läuft mit jedem Zeittakt die Eingangsfolge hinein. Nach 7 Schritten steht der Rest in den Speicherzellen. Das Schieberegister hat also wie ein MOD g(x) - Dividierer gewirkt.

1466 Worte in "deutsch"  als "hilfreich"  bewertet