Transcription
LV Kanalkodierung1Inhaltsverzei Vorbemerkungen . . . . . . . . . . . . .Allgemeine Bes hreibung von RM-KodesErzeugung von RM-Kodes . . . . . . . .Dekodierung von RM-Kodes . . . . . . .Dekodierungsergebnisse . . . . . . . . . .3.23.33.43.53.6.Ausgewählte algebrais he Grundlagen . . . . . . .3.1.1 Eigens haften eines Modularpolynoms . .3.1.2 Erweiterungskörper und MinimalpolynomePrimitive BCH-Kodes . . . . . . . . . . . . . . . .Ni htprimitive BCH-Kodes . . . . . . . . . . . . .Kodierung und Fehlererkennung . . . . . . . . . .Verkürzte und erweiterte BCH-Kodes . . . . . . .Anwendung von BCH-Kodes . . . . . . . . . . . .181920222528.REED-SOLOMON-Kodes ER-Kodes (RM-Kodes)2.12.22.32.42.53Allgemeines zur Kanalkodierung . . . . . .SHANNON's hes KanalkodierungstheoremS hranken für Kodeparameter . . . . . . .Dekodierungsprinzipien . . . . . . . . . . .Dekodierungsmethoden . . . . . . . . . . .282829323539404142Kurze Bes hreibung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Kodierung (zyklis her Kodes) . . . . . . . . . . . . . . . . . . . . . . . . . 475Auswahl von Kodierungs- und Übertragungsverfahren496Fehlerkorrekturverfahren für zyklis he Kodes566.16.26.3Fehlerkorrektur mit BCH-Kodes . . . . . . . . . . . . . . . . . . . . . . . . 56Fehlerkorrektur mit RS-Kodes . . . . . . . . . . . . . . . . . . . . . . . . . 65Auslös hungskorrektur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
LV Kanalkodierung6.47Einordnung . . . . . . . . . . . . . . . . . . . . . . . . .Kodiers haltung und Bes hreibung . . . . . . . . . . . .Punktierung . . . . . . . . . . . . . . . . . . . . . . . . .Dekodierung . . . . . . . . . . . . . . . . . . . . . . . . .7.4.1 Vorbemerkungen hard/soft-de ision Dekodierung7.4.2 Sequentielle Dekodierung FANO-Algorithmus7.4.3 MD/ML Dekodierung VITERBI-Algorithmus7.4.4 MAP-Dekodierung . . . . . . . . . . . . . . . . .Kodeverkettungen8.18.29Lokatorpolynom na hBERLEKAMP-MASSEY und EUKLID . . . . . . . . . . . . . . . . . . . . Serielle Verkettung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121(Parallele) Verkettung und iterative Dekodierung . . . . . . . . . . . . . . 128Turboähnli he Kodes9.19.281138LDPC[Low-Density Parity-Che k -(Blo k)Kodes . . . . . . . . . . . . . . . 138RA[Repeat-A umulate -Kodes . . . . . . . . . . . . . . . . . . . . . . . . 15510 S hlussbetra htungen158
LV Kanalkodierung1Fakultät InformatikInstitut für Systemar odul:IST-05-FG-AVS, MINF-04-FG-IAS, INF-04-FG-AVSBa helor Informatik (INF-B-510, INF-B-520)Ba helor Medieninformatik (INF-B-530, INF-B-540)Master/Diplom Informatik (INF-BAS4, INF-VERT4, INF-PMANW)Master Medieninformatik (INF-BI-3) Kodierung zur Komprimierung der Na hri htenmenge QuellenkodierungKodierung zur Geheimhaltung und zur Authenti zierung derNa hri htenmenge Kryptographie Kodierung zur quasi fehlerfreien Übertragung der Na h-ri htenmenge Kanalkodierung
LV Kanalkodierung2Kurzer Abriss zur Entwi klung von Kanalkodes 40er Jahre bahnbre hendeNON, HAMMING und GOLAYEnde derArbeiten vonSHAN- 1946 (n, l, fk ) (7, 4, 1)HAMMING-Kode, Verallgemeinerungvon einfa hfehlerkorrigierenden HAMMING-Kodes 1950spielen au h heute no h eine bedeutende RolleGOLAY gri 1949Problem der nur Einfa hfehlerkorrekturauf (q, n, l, fk ) (2, 23, 12, 3)GOLAY-KodeAnwendung: erw. (2,24,12,3)GOLAY-Kode in Voyager I Mission zum Jupiter (1977) (3, 11, 6, 2)GOLAY-Kode gemeinsam: Blo kkodes([q, ]n l k, l, fk ),LinearkodesTraditionelle ( klassis he ) algebrais he Kodes derJahre 1954 REED-MULLER-Kode exibler in der Zahl korrigierbarer50er, 60erFehler, allerdings zu-lasten der KoderateHeise, Quattrohi [8 : mäÿige Korrektur, aber gute Imple-mentierungseigens haften;Anwendung 1969-1977: Mariner-Mission für Marserkundungen
LV Kanalkodierung 19573erste Diskussionen über zyklis he Kodes( y liredundan yhe kodes CRC-Kodes )Vorteil: reduzierte Komplexität von Kodierer und DekodiererAnwendung: vorrangig zur (Bündel)Fehlererkennung 1959/60 BOSE CHAUDHURI HOCQENGHEM(BCH)KodesVorteil: Korrektur von Einzelfehlern 1960ni htbinäreREED SOLOMON(RS)-KodesVorteil: Korrektur von Bündelfehlern, Auslös hungenAnwendung: u. a. Spei herung (CD, DVD, MP3, ., QR-Kodes) 1969e zienter Dekodierungsalgorithmus vonBERLEKAMP-MASSEY, damit Beginn praktis her Anwendungen von RS-Kodes Na hteile von Blo kkodes:Dekodierung erst na h Erhalt der Empfangsfolgen lgth(b) b (für groÿeni ht tolerierbare Verzögerungszeiten)präzise Blo ksyn hronisationnur hard-de ision Dekodierung;Verbesserung nur mit quasi-soft Auslös hungsstellen(mit soft-de ision Dekodierung 2-3 dB näher an SHANNONGrenze) Vorteil:Leistungsfähigkeit exakt de niertZyklis he Kodes si hern in Verkettung mit klassis hen und modernen Kodes eine hohe Datenintegrität!
LV Kanalkodierung 1955blo kfreie4Faltungskodeserstmalig von ELIAS vorge-stellt, nutzt hard/soft-de ision Information vom Demodulator 1961/63/69 sequentieller Dekodierungsalgorithmus von WOZENCRAFT und REIFFEN, modi ziert von FANO und JELINEK, Na hteile bei hohem Störverhalten 1967VITERBI-Dekodierungsalgorithmus(hard/soft-de ision Dekodierung auf Basis von on: 1. Anw. in deuts h-amerikanis her Sonnensonde Helios (50er J.)1968 erste exp. Nutzung in Pioneer 9 Mission(K 32, R 12 ), Anfang 70er Jahre Pioneer 10-12 zu Jupiter, Saturn, Venus (sequentielle Dekodierung) 1977 Voyager 1 Mission zum Jupiter(K 7, R 12 ),Voyager 2 Mission zum Saturn (K 9, R 12 ),(K 7, R 34 )Globalstar Satelliten in 1400km HöheIridium Satelliten in 700km Höhe (K 15, R 41 )Big-Viterbi-Deoder für Galileo Mission zumJupiter (damit Anfang der 90er Jahre versu ht an SHANNONGrenze zu gelangen)Mobilkommunikation: GSM (1992), UMTS (2001), LTE [advan ed (2011[2013 ), 5G? (2020?). (in vielen Standards enthalten)Na hteil: sehr emp ndli h gegen Bündelfehler( Interleaving, Kodeverkettung mit RS-Kodes)
LV Kanalkodierung 19665Kodevorteile dur hKodeverkettung,erstmalig vonFORNEY vorges hlagenAnwendung: bereits 1971 Mariner Mission (RS- und RM-Kode),1977 Voyager I Mission (GOLAY- und Faltungskode), seit 80erJ. ges hi kte Verkettung von RS- und Faltungskodes in Raumsonden vom Typ Voyager mit spektakulären Bildern von Planeten wie Jupiter, Saturn, Uranus, Neptun (NASA-Standardfür Satellitenkommunikation), Path nder 1997, DVB-Standard,. Seit Mitte der90er Jahre Lüke zwis hen praktikablen Kodesund SHANNON-Grenze mit Anwendungdierung (GALLAGER 1962) 1993Turbo Code Iterativer Deko-s hlieÿbar Turbodekodierung Grundlage: zwei parallel verkettete Faltungskodes Dekodierung von parallel/seriell verketteten klassis hen,algebrais h konstruierten Kodes 1996Low-Density Parity-Che k (LDPC-)KodesGrundlage: sparsame zufallsbasierte KontrollmatrizenAufgabe der KanalkodierungLü ke zur SHANNON-Grenze s hlieÿen iterative Dekodierung (?, ja)praktikable Anwendungen(Kodebes hreibung, Komplexität der iterativen Umsetzung)Herausforderung 5G:100 nsfür Kod/Übertragung/Dekod
Fakultät InformatikInstitut für Systemar hitekturKanalkodierungWintersemester, 2/2/Leistungsna hweisLehrbeauftragte: Dr.-Ing. D. S hönfeldSWV/Ü12VVÜVÜVÜEinführung, Anknüpfung an LV IKTVom erweiterten HAMMING-Kode zum REED-MULLER-KodeBeispiele und AufgabenPrimitive und ni htprimitive BCH-KodesBeispiele und AufgabenREED-SOLOMON-Kodes (RS-Kodes)Beispiele und AufgabenV345Thema9ÜVÜVÜVÜVÜV10ÜVAuswahl von Kodierungs- und Übertragungsverfahren,Fehlerkorrektur mit BCH-Kodes (PZG-Verfahren)Fehlerkorrektur mit BCH-KodesFehlerkorrektur mit RS-Kodes, Auslös hungskorrekturFehlerkorrektur mit RS-KodesFehlerkorrekturverfahren von BERLEKAMP-MASSEY und EUKLIDAnwendung der Verfahren, Berü ksi htigung von Auslös hungsstellenFaltungskodes (Faltungskodierung, Punktierung)Beispiele und Aufgaben zur KodierungDekodierung von FaltungskodesBeispiele und Aufgaben zur DekodierungDekodierung von Faltungskodes mit soft-de ision(soft-input: Punktierung, Quantisierung; [soft-output: BiSOVA )Beispiele und Aufgaben zur Dekodierung von soft-inputSerielle Kodeverkettung und Anwendungen (CD, Sat, GSM, DVB, .)?VTurbokode: (Parallele) Kodeverkettung und iterative Dekodierung11.15V/Ü6?78LDPC-(Blo k)Kodes(iterative Syndromdekodierung: hard, reliability-based, soft)Beispiele zur Anwendung der iterativen DekodierungsverfahrenAufgabe für Erhalt des Leistungsna hweises(Auswertung der Ergebnisse im Rahmen der LV)
LV Kanalkodierung7Fakultät InformatikInstitut für Systemar hitekturKanalkodierungLiteratur[1 C.E. Shannon. A mathemati alpp. 379-423 and 623-656, 1948[2 R.W. Hamming. Error147-160, 1950[3 M.J.E. Golay.dete ting and orre ting odes. Bell Sys. Te h. J., vol. 29, pp.Notes on digital oding. Pro . IEEE, vol. 37, p. 657, 1949[4 W.W. Peterson.[5 R.E. Blahut.Prüfbare und korrigierbare Kodes. Mün hen 1967Theory and Pra ti e of Error Control Codes. Massa husetts 1983[6 W.W. Peterson, E.J. Weldon.Eleventh printing 1991[7 O. Pretzel.theory of ommuni ation. Bell Sys. Te h. J., vol. 27,Error-Corre ting Codes. Cambridge, London 1972,Error-Corre ting Codes and Finite Fields. Oxford 1992[8 W. Heise, P. Quattro hi.1995Informations- und Codierungstheorie. Berlin, Heidelberg[9 D. S hönfeld, H. Klimant, R. Piotras hke.Au age, Wiesbaden 2012[10 U. Reimers. DigitaleHeidelberg 2008Informations- und Kodierungstheorie. 4.Fersehte hnik. Datenkompression und Übertragung für DVB.[11 M. Bossert.Kanal odierung. 3. Au age, Mün hen 2013[12 P. Sweeney.Error Control Coding: From Theory to Pra ti e. England: Wiley, 2002[13 Zeits hriften IEEE Trans. Inform. Theoryu. a. D.J. Costello,Jr., J. Hagenauer. H. Imai, S.B. Wi ker.Control Coding. vol. 44, pp. 2531-2560, 1998Appli ations of Error- IEEE Trans. on. Com.[14 A.J. Viterbi. Error Bounds for Convolutional Codes and an Asymptoti ally OptimumDe oding Algorithm. IEEE Transa tions on Information Theory, 1967, 260-269
LV Kanalkodierung8[15 G.D. Forney. Convolutional Codes I. IEEE Transa tions on Information Theory, 1970,720-738[16 G.D. Forney.Convolutional Codes II. IEEE Information and Control, 1974, 222-297[17 L. Bahl, J. Co ke, F. Jelinek, J. Raviv. Optimal de oding of linear odes for minimizing symbol error rate. IEEE Transa tions on Information Theory, 1974, 284-287[18 C. Berrou, A. Glavieux, P. Thitimajshima. Near Shannon Limit Error-Corre tingCoding: Turbo Codes. Pro . 1993 IEEE Intern. Conf. on Com., Geneva, May 1993[19 J. Hagenauer, P. Hoeher. A Viterbi AlgorithmAppli ations. IEEE, Globe om 1989, 1680-1686with Soft-De ision Outputs and its[20 J. Hagenauer. Soft is better than hard. In: R.E. Blahut, D.J. Costello, U. Maurer,T. Mittelholzer (Hrsg.): Communi ations and Cryptography Two Sides of OneTapestry, 1994, 155-171[21 J. Hagenauer, E. O er, L. Papke. Iterative De oding of Binary Blo k andtional Codes. IEEE Transa tions on Information Theory, 1996, 429-445Convolu-[22 S. Riedel. Iterative De odierung parallel verketteter binärer Faltungskodes. Forts hr.Ber. VDI Reihe 10: Informatik/Kommunikationste hnik, Nr. 498, Düsseldorf 1997[23 M.P. Fossorier, F. Burkert, Lin Shu, J. Hagenauer. On the Equivalenand MAX-Log-MAP De oding. 1998[24 B. Vu eti , J. Yuan.e Between SOVATurbo Codes. Prin iples and Appli ations. 2000[25 J. Vogt, K. Koora, A. Finger, G. Fettweis. Comparison of di erent Turborealizations for IMT-2000. Pro . GLOBECOM'99, 2704-2708 (De . 1999)[26 R.G. Gallager.Low density parity he k odes. Cambridge, MA: MIT Press 1963[27 D.J.C. Ma Kay, R.M. Neal. Near Shannon Limit PerformanChe k Codes. Ele troni s Letters, 12.07.1996[28 R. Urbanke.de odere of Low Density ParityModern Coding Theory. SS 2001[29 I. Land, P.A. Hoeher. Using thefor Turbo Codes. ITW 2001Mean Reliability as a Design and Stopping Criterion
LV Kanalkodierung9Fakultät InformatikInstitut für Systemar hitekturKanalkodierung1Einführung1.1Allgemeines zur KanalkodierungLV IKTNa hri htenübertragungsmodell:*Quellen AkodiererQuelleXAKanalkodiererÜbertragungskanal ekodiererBum Signalwerte am KE und KA:(am KA au h als Zuverlässigkeit der Empfangswerte bezei hnet)a (u1u2.ul ) a (u1u2.un) aM (x1x2.xn)uj {0, 1} xj { 1, 1}bM 1 (y1y2.yn ) bh (yh,1yh,2 .yh,n ) b (bu1 ub2.bul )yj R1yjp(y x 1) ln p(yjj xjj 1) , yh,j yh,j uj {0, 1}bq : yq,j Qb : yj R1 sign yj2, yj -Zuverlässigkeitubj {0, 1}
LV Kanalkodierung10KodeMenge von Kanalkodewörtern;harakterisiert die Ausgabe desKodierers ohne irgendeine Referenz auf die QuellenkodewörterKodiererbes hreibt geordnete Menge von Quellen- und KanalkodewortPaaren Ein Kode kann dur h unters hiedli he Kodierer (Bildungs-gesetze) Quellenkodewörter vers hieden (aber eineindeutig) aufKanalkodewörter abbilden.HAMMING-MetrikHAMMING-Distanz:nPd(H) d(ai, aj ) (ui,g uj,g )g 1minimale HAMMING-Distanz (Minimalabstand):dmin min d(ai, aj )fürHAMMING-Gewi ht:i, j 1, 2, ., Lundai 6 ajw(ai) d(0, ai)EUKLID-Metrikd(E) d(ai, aj ) dminp(ui1 uj1)2 (ui2 uj2)2 . . . (uin ujn )2des Kanalkodes:MD-Dekodierung:d(H) d2(E)min d(H)(ai, bh) ,iwennmin d2(E)(aM,i , b) ,i d2(E) (aM,i , b) nPyh,j uj {0, 1}wenny[q,]j Qbzw.R(xij yj )2 (xi1 y1 )2 (xi2 y2 )2 . . . (xin yn )2 ; xij { 1, 1}j 1
LV Kanalkodierung11Erforderli heMinimalabstände bei Fehlererkennung (und Wiederholung): bei Fehlerkorrektur:Auswahlkriteriendmin fe 1dmin 2 fk 1für Kode/Korrekturverfahren:1. Geforderte Genauigkeit2. Zeitfaktor3. ImplementierungsaufwandDekodierung:b A?ja:Dekodierungb b nein: Fehlerkorrektur und Dekodierung [oder Fehlerverde kung Drei mögli heDekodierungsergebnisse:1. ri htige Dekodierung(a i b i )2. fehlerhafte Dekodierung(a j b i )3. Dekodierungsversagen (Fehler erkannt, aber keine Zuordnungmögli h)
LV Kanalkodierung1.212SHANNON's hes KanalkodierungstheoremFür einen stationären Übertragungskanal mit der TransinformationHT 0und der KoderateBlo kkode der Längen,R ln HTexistiert immer einder eine beliebig kleine Restfehlerwahrs heinli hkeit eine Koderatenahe an der Transinformationunddes Kanalsgewährleistet. M. Bossert.Kanal odierung. 2013, S. 23 .Problem der Kanal odierung, Codes zu nden, die lei ht zuodieren und zu de odieren sind und glei h-zeitig eine mögli hst groÿe Coderate bei mögli hst groÿerMindestdistanz haben. Beispiel:SBK:dminps 10 2 ; l 4 ; pR 10 5 (n, l, dmin )Kanalkode?fkk ldfkPi 0n in31375261073913R lnHT H(Y )-H(Y X)0.570.400.31pR 1-fkPi 00.920.920.92n ii ps (1 ps )n i2.03 · 10 31.14 · 10 46.65 · 10 6Errei hung von groÿem Interesse:Einsparung von Sendeleistung, bei glei her Übertragungsqualität!?Verringerung von sog. Elektrosmog (Beein ussung unserer Umwelt dur h Zunahme von Funksignalen)
LV Kanalkodierung13SHANNON-GrenzeS. Lin, D.J. Costello Jr. Error Control Coding: Fundamentals andAppli ations. 2. Au age, 2004, S. 18, 20
LV Kanalkodierung1.315S hranken für KodeparameterKodeparameter:n, l, k, dmin R, fkFür einen linearenfürRbzw.(n, l, dmin)Kode existieren obere S hrankenL: HAMMING-S hranke (1950)fk Pnk2 ii 0k ldfkPi 0 ni; l n k.perfekter Kode: wenn Gleihheitszei hen gilt(HK-, GOLAY-, Wiederholungskodes) SINGLETON-S hranke (1964)2l 2n dmin 1und demzufolgek dmin 1 .Maximaldistanz-(MDS[maximum distane separable -)Kode:wenn Glei hheitszei hen gilt(triviale binäre Kodes; ni htbinäre RS-Kodes)Weitere S hranken von PLOTKIN (1951),GILBERT (1952)-VARSHAMOV (1957), REIGER (1960), u. a.
LV ennung:b A? ja:kein (erkennbarer) Fehler nein:Fehler: Rekonstruktion dur h wiederholte ÜbertragungODERFehlerverde kung (Vermeidung fehlerhafter Rekonstruktion) Begrenzte Minimum-Distane DekodierungDekodierung erfolgt nur innerhalb der Korrekturkugel Maximum-Likelihood Dekodierung (Ähnlihkeitsdekodierung)MLDp(b ba) max p(b x)für allex A Bestimmung des am wahrsheinli hsten gesendeten Kode-wortesMinimum-Distane Dekodierung (entspri ht im Prinzip derMLD)d(ba, b) min d(H,E)(x, b) für allex ASymbolweise Maximum a posteriori Dekodierung MAP Bestimmung der am wahrsheinli hsten gesendeten Kode-symbole (Ents heidung für jedes Symbol (Bit) separat)
LV Kanalkodierung1.5 DekodierungsmethodenBMD Dekodierung (klassis he Blo kkodes) Dekodierungstabelle Mehrheitsdekodierung Syndromdekodierung FehlerstellenpolynomML/MD Dekodierung Sequentielle, VITERBI-Dekodierung (Faltungskodes) Iterative Dekodierung (Turbokodes, LDPC, .)(näherungsweise Umsetzung)17
VS, G-A IST-05-F G-IAS, MINF-04-F VS G-A INF-04-F helor Bac Informatik (INF-B-510, INF-B-520) helor Bac Medieninformatik (INF-B-530, INF-B-540) Master/Diplom Informatik (INF-BAS4, T4, INF-VER INF-PM-ANW) Master Medieninformatik (INF-BI-3) o Kdierung zur omprimierung K der tenmenge h hric Nac o Quellenkdierung o Kdierung zur .
