Kanalcodierung PDF

Kanalcodierung Information und Codierung InCO Team: G. Groppo, P. Egli, M. Rosenthal, T. Welti, D. Cachin, R. Büchi Ziele n Sie können: den Unterschied zw. Forward und Backward Error Correction an je einem Beispiel erklären die Mehr-Bit-Fehlerwahrscheinlichkeit...

Kanalcodierung Information und Codierung InCO Team: G. Groppo, P. Egli, M. Rosenthal, T. Welti, D. Cachin, R. Büchi Ziele n Sie können: den Unterschied zw. Forward und Backward Error Correction an je einem Beispiel erklären die Mehr-Bit-Fehlerwahrscheinlichkeit einer Sequenz berechnen die Kanalkapazität eines symmetrischen binären Kanals bestimmen den Begriff der Hamming-Distanz definieren die Grenzen der Fehlererkennung als Funktion der Hamming-Distanz herleiten die Coderate R eines binären Block-Codes bestimmen 2 ZHAW, Information und Codierung 25.11.23 Inhalt n Prinzip der Fehlerkorrektur (Forward/Backward Error Correction) n Binäre symmetrische Kanäle (BSC) n Einfluss der Frame-Länge auf den Durchsatz n Mehr-Bit-Fehlerwahrscheinlichkeiten n Grundlagen zur Fehlererkennung Entropie und Kanalkapazität eines BSC Hamming-Distanz Binäre Blockcodes Coderate R Systematik, Linearität, Zyklizität 3 ZHAW, Information und Codierung 25.11.23 Übersicht + Redundanz + Feh ler + Fe hler n Ist es möglich, über einen Kanal, der bei der Übertragung Fehler macht, Daten fehlerfrei zu übertragen? 4 ZHAW, Information und Codierung 25.11.23 Einteilung der Fehlerkorrekturverfahren n Backward Error Correction (Rückwärtsfehlerkorrektur) Die Redundanz erlaubt lediglich, Fehler zu erkennen und eine Neuübertragung der Daten anzufordern: Im Folgenden behandelte Verfahren sind: - Blockcodes - CRC n Forward Error Correction (Vorwärtsfehlerkorrektur) Die von der Kanalcodierung hinzugefügte Redundanz reicht, um beim Empfänger Fehler zu korrigieren: Im Folgenden behandelte Verfahren sind: - Blockcodes - Minimum-Distance-Decoding - Faltungscodes 6 ZHAW, Information und Codierung 25.11.23 Fehlerkorrektur: Backward Error Correction Wie erkennt man eine fehlerhafte Nachricht? 7 ZHAW, Information und Codierung 25.11.23 Fehlerkorrektur: Backward Error Correction n Nachteile des obigen Verfahrens? Es ist ein Rückkanal erforderlich Sender wartet auf Quittung (im Normalbetrieb) Sender wartet im Fehlerfall auf Timeout; à mögliche Abhilfe: Verwendung einer negativen Bestätigung n Nicht anwendbar im Falle von Datenauslöschungen (Defekte): einmaligen Ereignissen (z.B. Raumsonde) zu hoher Fehlerwahrscheinlichkeit n Typisches Software-Verfahren für Transport-Dienste z.B. TCP à wird im Modul IT.KT genau betrachtet 8 ZHAW, Information und Codierung 25.11.23 Forward Error Correction n Das Kanalcodierungstheorem beschreibt, unter welcher Bedingung sich die Wahrscheinlichkeit von Fehlern beliebig reduzieren lässt. n Folgende Begriffe werden behandelt: Kanalmodell / Binärer Symmetrischer Kanal Bitfehlerwahrscheinlichkeit BER (Bit Error Ratio). Binärer Symmetrischer Kanal Kanalkapazität Hamming-Gewicht Hamming-Distanz Coderate 9 ZHAW, Information und Codierung 25.11.23 Binäre Kanäle n Binäre Kanäle können nur die Werte 0 und 1 übertragen Störquelle ε Binäre Kanal- Binärer Kanal- Daten- Quelle Encoder Kanal Decoder empfänger Übertragungsfehler wirken sich demnach dadurch aus, dass im Verlauf der Übertragung einzelne Werte von 0 in 1 umgewandelt werden oder umgekehrt. Wir verwenden ein einfaches Fehlermodell: Die Störquelle verfälscht mit einer Wahrscheinlichkeit von ε ein Bit des Kanal-Codes. n ε ist die Bitfehlerwahrscheinlichkeit (BER – Bit Error Ratio) (Nicht: Bitfehlerrate = Bitfehler pro Zeit) 10 ZHAW, Information und Codierung 25.11.23 Bitfehlerwahrscheinlichkeit n Die Bitfehlerwahrscheinlichkeit ε ist eine Eigenschaft des Kanals. Anzahl fehlerhafte Bits im Verhältnis zu Gesamtzahl der Bits. Beispiele: Wir betrachten die Bits Yk beim Empfänger: - Alle Bits falsch: BER = 1 - Kein Bit falsch: BER = 0 - 1 von 2 Bits falsch: BER = 0.5 - 1 von 1000 Bits falsch: BER = 0.001 n Ein asymmetrischer Kanal hat unterschiedliche Wahrscheinlichkeiten ε!→# also dass eine 0 zu einer 1 wird und ε#→! also dass eine 1 zu einer 0 wird. n Im Folgenden beschränken wir uns auf die Betrachtung des symmetrischen Kanals, wo die beiden Wahrscheinlichkeiten gleich sind: ε!→# = ε#→! = ε 11 ZHAW, Information und Codierung 25.11.23 Binary Symmetric Channel (BSC) n Für den symmetrischen binären Kanal gilt: (englisch: Binary Symmetric Channel, BSC) Die Fehlerwahrscheinlichkeit ε ist unabhängig vom Eingangssymbol. Die Wahrscheinlichkeiten 𝑃 𝑦! 𝑥" der Übergänge (bei gegebenem 𝑥" ) sind: Sender Empfänger 12 ZHAW, Information und Codierung 25.11.23 Fehlerwahrscheinlichkeit eines Datenblocks n Mit der BER ε lässt sich die Wahrscheinlichkeit 𝑃!,% ausrechnen, mit der eine Sequenz von 𝑁 Datenbits korrekt (also mit null Bitfehlern) übertragen wird. A sei eine grosse Anzahl Frames mit der Länge 𝑁 Bit Wie viele Frames 𝐴# von A werden im 1. Bit keinen Fehler haben? 𝐴# = 𝐴 1 − ε Wieviel der verbleibenden, korrekten Frames 𝐴# werden auch im 2. Bit noch fehlerfrei sein? 𝐴$ = 𝐴# 1 − ε = 𝐴 1 − ε 1 − ε = 𝐴 1 − ε $ … Wieviel Frames sind nach der Übertragung des 𝑁. Bits noch fehlerfrei? 𝐴% = 𝐴 1 − ε % &! % n Erfolgswahrscheinlichkeit 𝑃!,% = = 1−ε & n Fehlerwahrscheinlichkeit auf 𝑁 Datenbits = 1 - 𝑃!,% = 1 − 1 − ε % wobei für 𝑁 ' ε ≪ 1 folgende Näherung gilt: 1 − ε % ≅ 1−𝑁'ε 13 ZHAW, Information und Codierung 25.11.23 Beispiel: n Wahrscheinlichkeit fehlerfreier Frames 𝑃!,% in Funktion der Länge 𝑁 bei verschiedenen Bitfehlerwahrscheinlichkeiten ε 𝑃!,% = 1 − ε % 100% 90% 𝑃!,% ≅ 1 − 𝑁 ' 𝜀 80% ε= 1.00E-02 70% 1.00E-03 60% 1.00E-04 50% 1.00E-05 40% 30% 20% 10% 0% 10 100 1’000 10’000 100’000 1’000’000 Frame-Länge [bit] 14 ZHAW, Information und Codierung 25.11.23 Mehr-Bit-Fehlerwahrscheinlichkeit einer Sequenz n Die Wahrscheinlichkeit PF,N , dass in einer Sequenz von N Datenbits genau F Bitfehler auftreten, ist: Anzahl der Möglichkeiten Wahrscheinlichkeit für Wahrscheinlichkeit, F Fehler in N Bits einen F-fachen Bit-Fehler dass die restlichen anzuordnen. Bits (N-F) alle keinen Fehler haben. 𝑁 ist der sogenannte 𝐹 Binomialkoeffizient aus der Kombinatorik (s. nächste Folie) 15 ZHAW, Information und Codierung 25.11.23 Bestimmung des Binomialkoeffizienten 𝑛 n ist der 𝑘-te Koeffizient der Potenz des Binoms 𝑥 + 𝑦 ( 𝑘 𝑛 (! n Bestimmung (für kleine 𝑛): = wobei 𝑘 ≤ 𝑛 𝑘 *!+ (,* ! Pascalsches Dreieck 𝑛 Der Koeffizient 𝑘 befindet sich in Beispiele: der 𝑛 -ten Zeile an der 𝑘-ten Stelle: 6 )*+ = = 15 2 #*$ Zeile (n) Beispiel: 6 8 0 = 15 1 ,*-*) 2 = #*$*. = 56 Click f. S. 1 1 1 3 2 1 2 1 3 1 3 3 1 Wissenschaftliche Rechner haben für 𝑛 4 1 4 6 4 1 i.A. eine spezielle Funktion z.B. 𝑟 5 1 5 10 10 5 1 nCr für “n choose r” 6 1 6 15 20 15 6 1 Spalte (k) 0 1 2 3 4 5 6 16 ZHAW, Information und Codierung 25.11.23 Mehr-Bit-Fehlerwahrscheinlichkeit einer Sequenz n Für die Wahrscheinlichkeit, dass maximal F Fehler bei einer Über- tragung von N Bits auftreten, bilden wir die Summe aller Fälle:. 𝑁 𝑃-.,% = 6 ' 𝜀/' 1 − 𝜀 %,/ 𝑡 /0! n Oft will man die Restfehlerwahrscheinlichkeit wissen, also die Wahrscheinlichkeit, dass mehr als F Fehler bei einer Übertragung von N Bits auftreten: 𝑃1.,% = 1 − 𝑃-.,% n Sie lässt sich wegen der Ziffernauslöschung (sehr kleine Summanden) aber nur schwer berechnen. Darum ist die folgende Form besser, welche alle Fälle mit F+1 bis N Fehlern berechnet: % 𝑁 𝑃1.,% = 6 ' 𝜀/' 1 − 𝜀 %,/ 𝑡 /0.2# 17 ZHAW, Information und Codierung 25.11.23 Kanalkapazität des BSC n Wir suchen die Kanalkapazität eines BSC bei einer bestimmten Bitfehlerwahrscheinlichkeit BER. Die maximale Kanalkapazität entspricht dem Maximum der Entropie einer binären Quelle: 1 bit/Symbol = 1 bit/bit Die Störquelle kann ebenfalls als Binary Memoryless Source mit den Wahrscheinlichkeiten ε (Fehler) und 1-ε (kein Fehler) betrachtet werden. Störquelle Störentropie H(ε) binäre maximale Daten- Kanalkapazität nutzbare Quelle 1 bit/bit Kanalkapazität 19 ZHAW, Information und Codierung 25.11.23 Rückblick: Binary Memoryless Source (BMS) Die Entropie Hb einer Binary Memoryless Source (BMS) mit den Symbolwahrscheinlichkeiten p und 1 – p war: Maximale Entropie bei p = (1-p) = 0.5 20 ZHAW, Information und Codierung 25.11.23 Kanalkapazität des BSC Binary Symmetric Channel Entropie der Störquelle Kapazität des fehlerfreien BSC bei 𝑃 𝑥" = 𝑃 𝑥# = 0.5 CBSC (ε) ε (BER) ZHAW, Information und Codierung 25.11.23 21 Eingangs- und Ausgangswahrscheinlichkeiten eines BSC 𝑃 𝑥4 % (1 − 𝜀) 𝑃 𝑥4 𝑥4 = 1 𝑦4 = 1 𝑃 𝑦4 𝑃 𝑥4 % 𝜀 𝑃 𝑥3 % 𝜀 𝑃 𝑥3 𝑥3 = 0 𝑦3 = 0 𝑃 𝑦3 𝑃 𝑥3 % (1 − 𝜀) Summe = 1 Summe = 1 Summe = 1 𝑃 𝑦4 = 𝑃 𝑥4 % 1 − 𝜀 + 𝑃 𝑥3 % 𝜀 𝑃 𝑦3 = 𝑃 𝑥3 % 1 − 𝜀 + 𝑃 𝑥4 % 𝜀 22 ZHAW, Information und Codierung 25.11.23 Eingangs- und Ausgangswahrscheinlichkeiten eines BSC n Beispiel: Quelle mit 𝑃 𝑥! = 0.05 und BSC mit 𝜀 = 0.01 𝑃 𝑥# = 1 − 𝑃 𝑥0 = 0.95 𝑃 𝑥# 5 1 − 𝜀 = 0.95 5 0.99 = 0.9405 𝑃 𝑥# 𝑥# = 1 𝑦# = 1 𝑃 𝑦# 𝑃 𝑥# 5 𝜀 = 0.95 5 0.01 = 0.095 𝑃 𝑥0 = 0.05 𝑃 𝑥0 5 𝜀 = 0.05 5 0.01 = 0.0005 𝑃 𝑥0 𝑥0 = 0 𝑦0 = 0 𝑃 𝑦0 𝑃 𝑥0 5 (1 − 𝜀) = 0.05 5 0.99 = 0.0495 Summe = 1 Summe = 1 𝑃 𝑦# = 𝑃 𝑥# 5 1 − 𝜀 + 𝑃 𝑥0 5 𝜀 = 0.9405 + 0.0005 = 0.9410 Summe = 1 𝑃 𝑦0 = 𝑃 𝑥0 5 1 − 𝜀 + 𝑃 𝑥# 5 𝜀 = 0.0495 + 0.0095 = 0.0590 23 ZHAW, Information und Codierung 25.11.23 Entropien eines BSC n Die Eingangs- und Ausgangswahrscheinlichkeiten ergeben folgende Entropien: 𝑃 𝑥# ' (1 − 𝜀) 𝑃 𝑥4 𝑥4 = 1 𝑦4 = 1 𝑃 𝑦4 𝑃 𝑥# ' 𝜀 𝑃 𝑥! ' 𝜀 𝑃 𝑥3 𝑥3 = 0 𝑦3 = 0 𝑃 𝑦3 𝑃 𝑥! ' (1 − 𝜀) Entropie am Eingang: Entropie am Ausgang: 24 ZHAW, Information und Codierung 25.11.23 Entropien eines BSC n Beispiel: Fehlerfreier Kanal P(x0)= 0.050 BER ε= 0 X 0.070 Y H(x1) 0.070 1 0.070 1 0.070 H(y1) 0.000 0.000 0.000 0.000 H(x0) 0.216 0 0.216 0.216 0 0.216 H(y0) H(X) 0.286 0.286 H(Y) n Durchgängig gleiche Entropie: H(x) = H(y) 25 ZHAW, Information und Codierung 25.11.23 Entropien eines BSC n Beispiel: Kanal ohne Information (nur Einsen) P(x0)= 0 BER ε= 0.01 X 0.014 Y H(x1) 0.000 1 0.014 1 0.014 H(y1) 0.066 0.066 0.000 0.000 H(x0) 0.000 0 0.000 0.000 0 0.066 H(y0) H(X) 0.000 0.081 H(Y) n Die Fehlerquelle erzeugt scheinbare Entropie, abhängig von der BER: 𝐻 𝜀 = −𝜀 5 log $ 𝜀 − 1 − 𝜀 5 log $ 1 − 𝜀 = −0.01 5 log $ 0.01 − 0.99 5 log $ 0.99 = 0.081 26 ZHAW, Information und Codierung 25.11.23 Entropien eines BSC n Beispiel: Voll genutzter Kanal P(x0)= 0.5 BER ε= 0.01 X 0.502 Y H(x1) 0.500 1 0.502 1 0.500 H(y1) 0.038 0.038 0.038 0.038 H(x0) 0.500 0 0.502 0.502 0 0.500 H(y0) H(X) 1.000 1.000 H(Y) n Am Ausgang H(y1) = 0.540 + H(y0) = 0.540 à 1.08 à unmöglich! n Die Störquelle zerstört offensichtlich Information von H(X). 27 ZHAW, Information und Codierung 25.11.23 Gemeinsame Information n Welche Information kann trotz Fehlern übertragen werden? à Die übertragene Information, die dem Eingang und Ausgang gemeinsam ist. H(ε) H(Y) I(X,Y) H(X) H(X) – I(X,Y) Sind H(Y) und H(ε) bekannt, folgt für die gemeinsame Information I(X,Y): I(X,Y) = H(Y) – H(ε) [bit/bit] 29 ZHAW, Information und Codierung 25.11.23 Gemeinsame Information n Werte aus obigem Beispiel mit 𝜀 = 0.01 und 𝑃 𝑥! = 0.05: H(X) = 0.286, H(Y) = 0.323, H(𝜀) = 0.081 H(ε) = 0.081 H(Y) = H(X) = I(X,Y) = 0.242 0.323 0.286 H(X) – I(X,Y) = 0.044 I(X,Y) = H(Y) - H(ε) = 0.323 – 0.081 = 0.242 [bit/bit] 30 ZHAW, Information und Codierung 25.11.23 Binäre Kanalcodes n Ein binärer Kanalcode ist eine Sammlung von Codewörtern. n Diese können mit Vorkehrungen versehen sein, damit Übertragungsfehler erkannt oder möglicherweise sogar korrigiert werden können. n Beispiel für Fehler- erkennung: 31 ZHAW, Information und Codierung 25.11.23 Hamming-Distanz (1) n Hamming-Distanz ist die Anzahl der wechselnden Bits von einem gültigen Codewort zum nächsten gültigen Codewort n Beispiel: 3-Bit-Code mit folgender 110 111 systematischer Anordnung: 010 011 x1x 1xx 100 101 0xx x0x xx0 xx1 000 001 n Hamming Distanz 1: jedes Codewort ist gültig; jeder Fehler führt zu einem gültigen Codewort à keine Fehlererkennung möglich 32 ZHAW, Information und Codierung 25.11.23 Hamming-Distanz (2) n Codes mit Hamming-Distanz ≥ 2 erlauben die Erkennung von Ein- oder Mehr-Bitfehlern. ( = gültiges Codewort, = ungültiges Cw) Hamming-Distanz = 2 Hamming-Distanz = 3 110 111 110 111 010 010 011 011 100 100 101 101 000 001 000 001 Erlaubt die Erkennung eines Erlaubt die Erkennung von einzelnen Bitfehlers zwei Bitfehlern 33 ZHAW, Information und Codierung 25.11.23 Hamming-Distanz (3) n Minimale Hamming-Distanz Die Hamming Distanz 𝑑 zwischen den Codewörtern ist nicht per se konstant: Beispiel: Code mit den Codewörtern 00000, 01011, 10101, 11110 d(00000, 01011) = 3 d(00000, 10101) = 3 d(00000, 11110) = 4 d(01011, 10101) = 4 d(01011, 11110) = 3 d(10101, 11110) = 3 n Für eine sichere Fehlererkennung oder (später auch Fehlerkorrektur) ist die minimale Hamming-Distanz 𝑑𝑚𝑖𝑛(𝐶) eines Codes 𝐶 relevant: n 𝑑𝑚𝑖𝑛 ist die kleinste Hamming-Distanz 𝑑 zwischen zwei beliebigen Codewörtern eines Codes. n Ein Code heisst ein «perfekter Code», wenn jedes empfangene Wort w genau ein Codewort c hat, zu dem es eine geringste Hamming-Distanz hat und zu dem es eindeutig zugeordnet werden kann. 34 ZHAW, Information und Codierung 25.11.23 Hamming-Gewicht n Das Hamming-Gewicht 𝒘𝑯(𝒄𝒋) gibt an, wieviele Einsen das Codewort 𝑐𝑗 enthält. darf nicht mit Hamming-Distanz verwechselt werden! n Beispiel: 𝑤𝐻(000) = 0 𝑤𝐻(110) = 𝑤𝐻(011) = 𝑤𝐻(101) = 2 n Anwendung: Bestimmung der Hamming-Distanz zweier Codewörter. Dazu bildet man mit einer bitweisen XOR-Operation die Differenz zweier Codewörter und bestimmt dann davon das Hamming-Gewicht, also die Anzahl der unterschiedlichen Bits. 𝑑E 𝑐F, 𝑐H = 𝑤E 𝑐F ⨁ 𝑐H 𝑑6 000, 110 = 𝑤6 000 ⨁ 110 = 𝑤6 110 = 2 𝑑6 110, 011 = 𝑤6 110 ⨁ 011 = 𝑤6 101 = 2 𝑑6 110, 101 = 𝑤6 110 ⨁ 101 = 𝑤6 011 = 2 35 ZHAW, Information und Codierung 25.11.23 Hamming-Distanz (4) n Wie gross ist die Anzahl der erkennbaren Fehler e bei einer gegebenen Hamming-Distanz 𝒅𝒎𝒊𝒏? 36 ZHAW, Information und Codierung 25.11.23 Hamming-Distanz (4) n Wie gross ist die Anzahl der erkennbaren Fehler e bei einer gegebenen Hamming-Distanz 𝒅𝒎𝒊𝒏? e = (dmin – 1) ausgehend von Codewort A e = (dmin – 1) ausgehend von Codewort B 37 ZHAW, Information und Codierung 25.11.23 Binäre Blockcodes: Systematik n Encoder für (N,K)-Blockcode Coderate 𝑹: [ u0 u1... uK-1 ] Encoder [ c0 c1... cN-1 ] 𝑲 𝑹= Informationswort u Codewort c 𝑵 n Systematischer (N,K)-Blockcode: Die K Informationsbits erscheinen im Codewort am einem Stück N Codebits N - K Paritätsbits K Informationsbits oder N Codebits K Informationsbits N - K Paritätsbits Systematische Blockcodes lassen sich besonders einfach decodieren: à Es müssen lediglich die Paritätsbits entfernt werden. 38 ZHAW, Information und Codierung 25.11.23 Binäre Blockcodes: Linearität n Bei einem linearen(N,K)-Blockcode ist die bitweise Exor-Verknüpfung von 2 beliebigen Codewörtern (inklusive des selben) wieder ein gültiges Codewort: Beispiel: 𝐶= (000), (110), (011), (101) - Beliebiges Codewort xor mit sich selber: - Beliebiges Codewort xor mit (000): - Restliche Fälle: àJeder lineare Code muss zwingend das Null-Codewort (000) enthalten Anmerkung: Mathematisch nennt man die bitweise Exor-Verknüpfung eine bitweise Modulo-2-Summe (1-bit-Summe ohne Übertrag). n Bei linearen (N,K)-Blockcodes ist 𝒅𝒎𝒊𝒏 die minimale Hamming- Distanz der gültigen Codes zum Null-Codewort, oder einfacher das minimale Hamming-Gewicht: 𝑑34( (𝐶) = min 𝑤7 𝑐5 56! 39 ZHAW, Information und Codierung 25.11.23 Binäre Blockcodes: Zyklizität n Linearer, zyklischer (N,K)-Blockcode Die zyklische Verschiebung eines Codeworts gibt wieder ein Codewort: n Beispiel: n Ein linearer, zyklischer Blockcode wird später eingehend besprochen (siehe Abschnitt CRC). 40 ZHAW, Information und Codierung 25.11.23 Binäre Blockcodes Beispiel (3,2) Block-Code 𝑪 = { [𝟎 𝟎 𝟎], [𝟏 𝟏 𝟎], [𝟏 𝟎 𝟏], [𝟎 𝟏 𝟏] } 110 111 010 011 systematisch linear 100 101 zyklisch 000 001 perfekt Länge der Infowörter K= Länge der Codewörter N= Coderate 𝑅 = minimale Hamming-Distanz 𝑑𝑚𝑖𝑛 = 41 ZHAW, Information und Codierung 25.11.23 Kanalcodierungstheorem n Das Kanalcodierungstheorem beschreibt, unter welcher Bedingung sich die Wahrscheinlichkeit von Fehlern beliebig reduzieren lässt. Möchte man die Restfehlerwahrscheinlichkeit eines Fehlerschutzcodes beliebig klein machen, so muss 𝑅 < 𝐶 sein. n 𝐶: Kanalkapazität in bit/bit (Nutzbare Bits pro Kanalbenutzung) n 𝑅: Coderate in bit/bit (Infobits pro Codebit) 𝐾 𝑅= 𝑁 n 𝑅 muss kleiner als 𝐶 sein, damit alle Information in den nutzbaren Bits Platz hat 42 ZHAW, Information und Codierung 25.11.23