Algorithmensammlung Codierungstheorie

Algorithmensammlung Codierungstheorie
von Alfred Franz und Hauke Hund
Sommersemester 2007
Inhaltsverzeichnis
Hamming-Code.................................................................................................................................... 2
Codewort überprüfen und ggf. korrigieren...................................................................................... 2
BCH-Code............................................................................................................................................ 2
Einen BCH-Code mit gegebenem e und G1(u) erzeugen................................................................2
Zu gegebenen Nachrichtenstellen die Kontrollstellen berechenen..................................................2
Abramsen-Code.................................................................................................................................... 3
Überprüfen ob ein Codewort richtig ist........................................................................................... 3
Ein Codewort mit Fehler korrigieren...............................................................................................3
Fire-Code.............................................................................................................................................. 3
Fire-Code anhand von G1(u) bestimmen.........................................................................................3
Codewort überprüfen....................................................................................................................... 3
Codewort korrigieren.......................................................................................................................3
Reduziblität von G(u)........................................................................................................................... 4
Primitivität von G(u)............................................................................................................................ 4
Zyklische Eigenschaften von G(u) bestimmen.....................................................................................5
Beispiel: .......................................................................................................................................... 5
Schieberegisterverfahren...................................................................................................................... 6
Generatorworte erstellen...................................................................................................................... 7
Matrix-Verfahren..................................................................................................................................8
Huffman-Code...................................................................................................................................... 8
Fano-Shannon-Code............................................................................................................................. 9
1
Hamming-Code
(Ein Hamming-Code erkennt und korrigiert 1-Bit-Fehler)
- Zuerst die Eigenschaften des Hamming-Codes anhand von G(u) bestimmen:
• Grad k (Kontrollstellen)
• Codewortlänge n = 2^k – 1
• Nachrichtenstellen m = n – k
• G(u)
- Dann kann anhand der Stellen die komplette Bitfolge erstellt werden.
Codewort überprüfen und ggf. korrigieren
- Um zu testen ob es sich um ein Codewort handelt muß das Codewort durch G(u) geteilt
werden:
Wenn kein Rest (Fehlersyndorm) rauskommt ist die Bitfolge ein Codewort.
- Wenn kein Codewort => Korrektur z.B. mit rückgekoppeltem Schieberegister (Verfahren):
1. RS0 bestimmen: Das Fehlersyndrom + k Nullen durch G(u) teilen
2. Ein Schieberegister (Bauart G(u)) mit RS0 füttern und so lange takten bis 1 0 ... 0
(1-Bit-Fehler) herauskommt. Handelt es sich um einen 1-Bit-Fehler zeigt die Anzahl der
Takte die Position des Fehlers an (z.B. 5ter Takt = Fehler an Bit 5).
BCH-Code
Einen BCH-Code mit gegebenem e und G1(u) erzeugen
n von G(u):
k von G(u) für e = 2:
k von G(u) für e = i:
m:
Schritt (1):
Schritt (2):
Schritt (3): für e = 2:
für e = 3:
usw.
n=2 k1−1
k =k1k2
k =k1k2...ki
m=n−k
(Gesamtlänge des Codeworts)
(Anzahl der Kontrollstellen)
(Gesamtlänge des Codes)
Galois-Feld aufstellen.
G2(u) mit Hilfe von a2 aufstellen.
ggf. auch G3(u), usw.
G(u) = G1(u) * G2(u)
G(u) = G1(u) * G2(u) * G3(u)
Zu gegebenen Nachrichtenstellen die Kontrollstellen berechenen
(Divisionsverfahren)
● Die Nachrichtenstellen mit Nullen zu voller Nachrichtenlänge auffüllen und das Ergebnis
durch G(u) teilen. Der Rest sind die Nachrichtenstellen.
2
Abramsen-Code
(Ein Abramsen-Code erkennt und korrigiert 1-Bit-Fehler, und kann benachbarte 2-Bit-Fehler
erkennen)
Zuerst die Eigenschaften des Codes bestimmen:
•
•
•
•
G(u) = G1(u) · (u + 1)
Kontrollstellen k = grad(G(u))
Codewortlänge n = 2k−1 − 1
Nachrichtenstellen m = n − k
Überprüfen ob ein Codewort richtig ist
Das Codewört durch G(u) teilen:
Bleibt kein Rest übrig ist es ein Codewort.
Bleibt ein Rest übrig ist es kein Codwort, den Rest nennt man Fehlersyndrom.
Ein Codewort mit Fehler korrigieren
Eine Möglichkeit ist das Schieberegisterverfahren (siehe eigenes Kapitel)
Fire-Code
Fire-Code anhand von G1(u) bestimmen
k = grad(G(u))
n = kgV ( 2 k1−1 , k2) (Bsp.: kgV (15 , 5) = 15)
m= n-k
G u=G 1 u ⋅u k2 1
k2 bestimmen:
k1 = grad(G1(u))
Bedingung: b <= k1
k2 > 2b - 2
(Kontrollstellen)
(Codewortlänge)
(Nachrichtenstellen)
(b gegeben)
(k2 kann gewählt werden)
Codewort überprüfen
Codewort durch G(u) teilen. Kommt Rest 0 raus ist es ein Codewort, sonst nicht.
Codewort korrigieren
geht z.B. mit dem Schieberegisterverfahren => siehe Kapitel Schieberegisterverfahren
3
Reduzierbarkeit von G(u)
G(u) ist reduzibel wenn teilbar durch (u) oder (u+1).
● u=1
● u + 1 = 11
Primitivität von G(u)
entweder: aus Liste ablesen, Liste irreduzibler Polynome:
oder:
- Grad des Polynoms g bestimmen
- Periode des Polynoms p bestimmen
g = grad(G(u))
p bestimmt man wie folgt:
Die Periode p eines Polynoms G(u) ist der kleinste Wert p, für den gilt: das Polynom
u p 1 ist ohne Rest durch G(u) teilbar.
Für reduzible Polynome beginnt man mit p=g, für irreduzible Polynome beginnt man
mit p=1. Wenn die Teilung einen Rest ergibt erhöht man das p jeweils um 1.
- Das Polynom G(u) ist primitiv wenn gilt: 2 g −1= p
4
Zyklische Eigenschaften von G(u) bestimmen
- Das normale Golois-Feld aufstellen
- Alle Kombination, die da noch nicht vorkamen einzeln betrachen.
- aufmalen, auch die Kombinationen die nur auf einen Zyklus abbilden
Beispiel:
Zyklische Eigenschaften von M(u) = u4 + u2 + u = 10110
5
Schieberegisterverfahren
- zuerst RS0 bestimmen:
Den Rest aus der Division Codewort : G(u) nehmen, mit k Nullen auffüllen und nochmals
durch G(u) teilen. Der rauskommende Rest ist RS0 (Startwert des Schieberegisters).
- Aus G(u) ein Schieberegister bauen.
Beispiel:
- Schieberegister Schritt für Schritt ausführen, bis 100.... oder 11000.... ausführen. Aber nie
mehr Durchläufe als Stellen im Codewort!
100....
zeigt 1-Bitfehler an. In diesem Fall ist die Anzahl der Durchläufe gibt die Stelle des
Fehlers an. (z.B. RS=11 (bei RS0 begonnen), dann ist das 12te Bit falsch.)
1100....
zeigt 2-Bitfehler an. Je nach Code evtl. keine Korrektur möglich.
Beim Abramsen-Code: Das fehlerhafte Codewort durch 11 teilen, wenn kein Rest
rauskommt handelt es sich tatsächlich um einen 2-Bit-Fehler, sonst ist keine Aussage
möglich (kein korrigier oder erkennbarer Fehler)
6
Generatorworte erstellen
Abbildung 1: Beispiel Generatorworte erstellen
7
Matrix-Verfahren
Abbildung 2: Veranschaulichung Matrix-Verfahren
- Galois-Feld kippen, dann hat man die Matrix. Zum kontrollieren und korrigieren ein Codewort
darüber schreiben und nach dem Verfahren in Abbildung 1 durchrechnen.
- Zum Erstellen der Kontrollstellen die Nachrichtenstellen mit Nullern ergänzen und ebenfalls
Durchrechnen, das Ergebnis sind, begonnen mit der obersten Zahl die Nachrichtenstellen.
Huffman-Code
Abbildung 3: Beispiel zum Huffman Code
Schritt 1:
Schritt 2:
nach der Häufigkeit nach sortieren
die beiden kleinsten zusammenfassen und die Summe wieder einsortieren, den beiden 0
und 1 zuordnen (siehe Beispiel)
solange wiederholen, bis alles abgearbeitet ist
8
Fano-Shannon-Code
Schritt 1:
Schritt 2:
Schritt 3:
Der Häufigkeit nach sortieren
Das Feld so teilen, dass die Differenz der Summen der Häufigkeiten oberhalb und unterhalb
des Strichs möglichst gering ist.
(Oben und unten sollten möglichst ähnliche Häufigkeitssummen stehen.)
Oben 0, unten 1 zuweisen.
=> Für beide Teile wieder bei Schritt 1 beginnen, bis es nur noch einzelne Häufigkeiten gibt.
Abbildung 4: Beispiel zum Fano-Shannon-Code
9

Download Report