Codierungstheorie

• Titel: Codierungstheorie
• Organisation: UNI TUEBINGEN
• Seitenzahl: 124

Skript herunterladen (PDF)

Inhalt

• Skript zur Vorlesung im WS
• A LTE Fassung von Daniel Raible
• Codes einige einfache Beispiele Blockcodes grundlegende Denitionen
• Literatur zur Vorlesung Codierungstheorie
• ggf Decodierer Converter Empfänger
• Konstruktion von Codierern Decodierern Anforderung Ezienz
• Codes einige einfache Beispiele
• Nachrichten und Alphabet wie in
• Nachrichten und Alphabet wie in Codierung
• Kennzeichnung des Erscheinungslandes
• Verlagsinterne Nummer für das spez Buch
• andere Stellenzahlen möglich
• kzk i zi xi
• kzk izj jzi
• kzk j izi zj
• Tabelle Die vier Codes des EAN
• Abbildung Beispiel eines EAN Codewortes
• Blockcodes grundlegende Denitionen
• c ASCIICode R
• Grundbegrie der Informationstheorie und der Kanalcodierungssatz von Shannon
• Gibt Zeichen über Alphabet A aus
• pF a logpF a R
• alle WVert einer Quelle F
• ungestrter o Kanal
• Jedes Bit wird umgedreht
• total gestrter Kanal o
• pG p pF ppF
• fr alle x C u
• viele Wrter o
• Eine einfache Abschtzung zeigt a
• np log p p log p
• siehe zB Friedrichs Anhang A
• Die Kugelpackungsschranke und perfekte Codes
• Anzahl der Auswahl von j Positionen in y
• Dies liefert die Behauptung
• qn n q j j
• Add der drei Gl
• u g u k gk C
• Daran lsst sich die Kontrollmatrix a H
• Zunchst werden a g g g
• HammingCode uber Z vgl a
• t Hf t Hf t Hf t Hf
• P P P P P
• Allgemeine Konstruktionsprinzipien linearer Codes
• vgl euklidsches Skalarprodukt im Rn
• A t At Ink
• At Ik Ink At
• Und fr das Gewicht u
• z z z
• c ci ci cn
• ci K mit c ci cn C
•  Beispiele a Sei C n
• ReedMullerCodes und MajorityLogicDecodierung
• Ansonsten per Induktion nach r m dimRMr m
• dimRMr m dimRMr m
• m m i i m i
• vgl wwwjplnasagov bzw wwwnasagov
• Werte von f dh Z
• x x x
• aZm f a j aj
• xi i m
• f f x Zm
• f zx M f M
• pi x xm Boolesches Polynom vom
• Frage Ist zi fehlerhaft oder nicht
• Wir whlen a
• entweder zr xr oder yr oder beides
• j yr zr y jxr
• r i is
• Berechne alle M z
• Polynomcodierung und zyklische Codes
• Multiplikation mit Skalaren
• ein Untervektorraum von Kx Grad
• mit ci a bi a bi ai b
• S x S k x S k x
• Es ist dann Sj
• x mx mod gx x x
• xnk mx mod gx
• ist Erzeugermatrix von C
• und cx gx qx
• Dann gxtx c cnkxnk xnk mx C
• Beweis zB Willems und
• ai xi an xn
• ai xi an a an
• n j n i iterieren
• Distributiv n gesetz
• Gradmx k gx Kxk
•  Folgerung Ist C ein zyklischer n kCode
• Kontrollmatrix von C
• gxhx xn g x h x xn
• ReedSolomonCodes und Anwendungen
• ij xj fr alle i d u
• si f i f i f ni fn
• qj sij i t d
• invertierbar vgl Beweis a
• Nullstelle von qx Fehlerposition i
• je Kontrollsymbole von
• c c c c c
• fach verzögerter Interleaver
• zuerst Codierung der Spalten mit
• dann Codierung der Zeilen mit C
• übersetzt in zeitkontinuierliches Signal
• r Codebits Generatorpolynome
• C uD GD uD
• ur D r ur Z
• Ubergangswahrscheinlichkeiten des Kanals
• diskreter gedchnisloser Kanal a
• Kantenmetrik denn entspr Kante in Trellisdiagramm
• log pvij cij
• Metrik zur Codewortfolge c Pfad in Trellisdiagramm ViterbiMetrik
• vij cij N maximal
• Empfangene Folge v Surviviorpfad c Infofolge u
• Abbildung ViterbiDecodierung fr das Beispiel u
• H HH ci viHHH
• Mache Metrik ganzzahlig entsprechend d b a
• BitMetrik Kanten PfadMetriken Summe der BitMetriken
• Empfangene v Folge Einziger SurvivorPfad Infofolge

Vorschau