Kanalcodierung g2 Fehlerprüfung Hamming‐Distanz und Fehlerkorrekturvermögen Perfekte Codes und Hamming‐Grenze Restfehlerwahrscheinlichkeit Eigenschaften und Konstruktion von Hamming‐Codes CRC‐Codes Martin Werner WS 2009/10 Martin Werner, January 10 1 Prinzip der Fehlerprüfung Sender Encoder FCS = f (u) Nachrichtenwort u u Rahmen‐ prüfsumme FCS Empfänger Codewort v Kanal Decoder ur FCSc = f (ur) FCSr ? FCSc = FCSr Rahmen‐ prüfsumme Martin Werner, January 10 NEIN Empfangswort r JA Keinen Fehler K i F hl entdeckt Fehler entdeckt F hl td kt 2 Hamming-Gewicht Code‐Tabelle des (7,4)‐Hamming‐Codes Codewort Hamming‐ Gewicht Codewort Hamming‐ Gewicht 000 0000 000 0000 0 101 0001 101 0001 3 110 1000 3 011 1001 4 011 0100 011 0100 3 110 0101 110 0101 4 101 1100 4 000 1101 3 111 0010 111 0010 4 010 0011 010 0011 3 001 1010 3 100 1011 4 100 0110 3 001 0111 4 010 1110 4 111 1111 7 Martin Werner, January 10 3 Hamming-Distanz Fall 1: Korrigierbarer Fehler 1 Bitfehler Fall 2: Erkennbarer Fehler 2 Bitfehler Fall 3: Restfehler 3 oder mehr Bitfehler Hamming‐Distanz und Hamming‐Gewicht n 1 d v i , v j vi ,l v j ,l wH v i v j Martin Werner, January 10 l 0 4 Fehlerkorrekturvermögen, Hamming-Grenze d min min wH v Minimale Hamming‐Distanz vC \0 Ei li Ein linearer binärer (n,k)‐Blockcode mit minimaler bi ä ( k) Bl k d it i i l Hamming‐Distanz dmin 2t + 1 kann dmin1 Fehler erkennen und bis zu t k d bi t Fehler korrigieren F hl k i i Perfecter Code (dicht gepackt): Hamming‐Grenze Hamming Grenze Martin Werner, January 10 Alle Empfangswörter liegen innerhalb der Korrigierkugeln der Korrigierkugeln 2 nk n l 0 l t 5 Restfehlerwahrscheinlichkeit Wie groß ist die Wahrscheinlichkeit, dass Übertragungsfehler nicht erkannt werden? p ( , ) g Beispiel (7,4)‐Hamming‐Code Restfehler Fehlerwort ist Codewort Restfehler Fehlerwort ist Codewort 1 A0 A1 A2 A3 A4 A5 A6 A7 0 0 7 7 0 0 1 Beispiel: e = (0011010) Beispiel: e P(e) = Pb3 (1Pb)4 Restfehlerwahrscheinlichkeit R f hl h h i li hk i Hamming‐Gewichte der Codewörter sind entscheidend Pr n i d min Ai Pbi 1 Pb n i Gewichtsverteilung des Codes Martin Werner, January 10 6 Hamming-Codes Perfekter Code Systematischer Code Codewortlänge n = 2m 1 Anzahl der Nachrichtenstellen k=nm Anzahl der Prüfstellen m=nk Fehlerkorrekturvermögen dmin = 3, t = 1 Hamming‐Codes g ((15,11), (31,26), (63,57), usw. , ), ( , ), ( , ), Matrix H einfach bestimmbar Martin Werner, January 10 7 Konstruktion von Hamming-Codes Prüfmatrix HTn k k T T I n k n k Pk n k Syndromdekodierung S d d k di Einzelfehlererkennung alle Spalten der Matrix H paarweise verschieden Minimale Distanz dmin = 3 alle Spalten von PT mindestens mit zwei 1en Matrix P besitzt k Spalten mit je n k Zeilen Es gibt 2nk Möglichkeiten 0en und 1en in einer Spalte anzuordnen 1 Möglichkeit für nur 0en in einer Spalte (n k) Möglichkeiten genau eine 1 in der Spalte wg. Es gibt genau 2 ib 2n k – 1 – (n ( – k) = n – (n ( – k) = k Möglichkeiten für li hk i f k Spalten von P S l P Martin Werner, January 10 9 (15,11)-Hamming-Code H 415 1 0 0 0 Martin Werner, January 10 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 10 CRC-Codes Cyclic redundancy check Binärer zyklischer (n k)‐Blockcode Binärer zyklischer (n, k) Blockcode Codewörter sind ohne Rest durch Generatorpolynom g(X) teilbar Gute Fehlererkennung Gute Fehlererkennung Zahl der Prüfstellen einstellbar, z. B. CRC‐8, ‐12, ‐16, ‐24 und ‐32 Codewortlänge variabel, auch lange Nachrichtenwörter möglich Codewortlänge variabel, auch lange Nachrichtenwörter möglich Schnelle Codier‐ und Decodier‐Algorithmen ITU‐Standard, z. B. ATM, Bluetooth, UMTS, HDLC, LAPD, PPP, … , , , , , , , Martin Werner, January 10 11 Encoderschaltung CRC‐4 mit Generatorpolynom g(X) = 1 + X 2 + X 3 + X 4 Schalter S2 g0 0 g2 g3 Schalter S1 Codewort v Nachrichtenwort u Martin Werner, January 10 12 Decoderschaltung CRC‐4 mit Generatorpolynom g(X) = 1 + X 2 + X 3 + X 4 Empfangswort r g0 0 g2 g3 Syndrom s Martin Werner, January 10 13
© Copyright 2024 ExpyDoc
