nach oben

2017 | Buch

Kapitel lesen Erstes Kapitel lesen

Fehlerkorrigierende Codes

Konstruieren, Anwenden, Decodieren

verfasst von: Olaf Manz

Verlag: Springer Fachmedien Wiesbaden

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Dieses Buch stellt mit möglichst wenig mathematischen Hilfsmitteln die wesentlichen Grundbegriffe und Konzepte der Theorie fehlerkorrigierender Codes in der Datenübertragung dar. Alle historisch und für Praxisanwendungen wichtigen Klassen und Familien von Codes werden explizit konstruiert; dies beinhaltet auch deren Rate und Minimalabstand. Außerdem werden die wesentlichen Decodieralgorithmen beschrieben. Die Darstellung orientiert sich dabei an den zugehörigen "Meilensteinen" in der Geschichte der Codierungstheorie. Besonderer Wert gelegt wird außerdem auf die Vermittlung der Art und Weise, wie diese Codes in der Praxis angewandt werden. Das Buch eignet sich für Studierende im mathematisch-technischen Bereich an Fachhochschulen und Universitäten (z.B. in Proseminaren), auch für die MINT-Lehrerfortbildung und andere Weiterbildungsveranstaltungen für interessierte Anwender, Schüler und Senioren.

Inhaltsverzeichnis

Frontmatter

1. Eingangsbeispiele und Blockcodes

Zusammenfassung

Wir machen uns zunächst einmal klar, um was es beim Codieren geht, nämlich zu der eigentlichen Information redundante Daten hinzuzufügen, um Fehler bei der Datenübertragung oder beim Datenauslesung aus einem Speicher selbstständig erkennen oder sogar korrigieren zu können. Hierzu führen wir das Konzept der Blockcodes ein und stellen deren wichtigste Eigenschaften zusammen. Fundamental ist dabei der Begriff des Hamming-Abstands, d.h. der Anzahl der Positionen, an denen sich zwei Codewörter unterscheiden. Hieraus leiten sich nämlich die Fehlererkennungs- und Fehlerkorrekturkapazität eines Blockcodes ab. Die Konzepte veranschaulichen wir an Praxisbeispielen wie der Buchnummer (ISBN), der Artikelnummer (EAN), der Kontonummer (IBAN) und der Wertpapierkennnummer (ISIN). Den berühmten Kanalcodierungssatz von Claude Shannon aus dem Jahr 1948 betrachten wir als Ermutigung bei unserer Suche nach guten Codes.

Olaf Manz

2. Lineare Codes

Zusammenfassung

Eines haben wir aus unseren Eingangsbeispielen gelernt: Wenn wir eine Chance haben wollen, gute Code zu konstruieren, dann sollten wir mit den Codewörtern in geeigneter Weise rechnen können. Aus diesem Grund konzentrieren wir uns von nun an auf lineare Codes, d.h. Vektorräume über endlichen Körpern, wobei der Körper der Bits der mit Abstand wichtigste sein wird. Wir lernen beispielsweise dabei, wie man systematisch codiert. Als konkrete Beispiele betrachten wir zwei Protagonisten in der Geschichte der Codierungstheorie - den kleinen binären Hamming-Code und den ternären Golay-Code. Der duale Code eines linearen Codes, der über das Skalarprodukt definiert wird, stellt sich als wichtig bei den Fehlerkorrekturverfahren heraus. Wir gehen in diesem Zusammenhang auf die Syndrom-Decodierung sowie auf das Prinzip der Maximum-Likelihood-Decodierung ein.

Olaf Manz

3. Hamming- und Golay-Codes

Zusammenfassung

Nun wollen wir Hamming- und Golay-Codes etwas systematischer untersuchen. Richard Hamming hat seine berühmten Codes 1950 publiziert, die er ursprünglich erfand, um Fehler beim Einlesen von abgenutzten Lochkarten automatisch korrigieren zu können. Alle Hamming-Codes können nämlich einen Fehler je Wort sicher korrigieren. Außerdem sind sie perfekt, d.h. in einer wichtigen Schranke für Codes – der Kugelpackungschranke - steht bei ihnen das Gleichheitszeichen. Fast gleichzeitig hat Marcel Golay 1949 zwei weitere perfekte Codes angegeben, nämlich nebem dem ternären noch seinen berühmten binären Golay Code. Für binäre Hamming-Codes gibt es bis heute noch die ein oder andere Anwendung, z.B. in Arbeitsspeichern von Computern und beim Satellitennavigationssystem GPS. Golay-Codes hingegen haben seit jeher eine erstaunliche Faszination in- und außerhalb der Wissenschaft ausgelöst. Ihr wohl bekanntester Praxiseinsatz war der bei den NASA-Sonden Voyager 1 und 2 auf ihrem Weg zwischen 1979 und 1981 vorbei an Jupiter und Saturn.

Olaf Manz

4. Reed-Muller-Codes

Zusammenfassung

Im Jahr 1954 erhielt die Codierungstheorie einen weiteren Schub. David Muller publizierte die Reed-Muller-Codes und Irving Reed steuerte das passende Fehlerkorrekturverfahren bei: Die Majority-Logic-Decodierung. Diese entscheidet per Mehrheitsvotum, wo in einem empfangenen Wort ein Fehler aufgetreten ist. Wir nutzen das Majority-Logic-Verfahren, um einen kleinen Reed-Muller-Code per Hand zu decodieren. Ein etwas größerer Reed-Muller-Code – nämlich der mit Wortlänge 32 und 64 Codewörtern - hat große Berühmtheit erlangt. Mit seiner Hilfe haben Mariner-Sonden in den Jahren 1969 bis 1972 die damaligen Schwarz-Weiß-Bilder vom Mars übertragen, wobei zur Fehlerkorrektur die legendäre Green Machine zum Einsatz kam.

Olaf Manz

5. Reed-Solomon-Codes

Zusammenfassung

Um beim Codieren noch etwas mehr algebraische Struktur verwenden zu können, bietet sich zusätzlich das Rechnen mit Polynomen an. Genau das haben Irving Reed und Gustave Solomon im Jahr 1960 getan, und mittels Polynomauswertungen ihre Reed-Solomon-Codes konstruiert – die wahren Stars unter den Blockcodes. Sie sind so gut, dass bei Ihnen in der wohl wichtigsten Schranke für Codes - der Singleton-Schranke – das Gleichheitszeichen steht (sog. MDS-Codes). Die Verwendung von Reed-Solomon-Codes in der Praxis ist auch heute noch Stand der Technik. Nach einem ersten Überblick (u.a. NASA-Raumfahrt, Aztec-Code) gehen wir besonders ausführlich auf das Verfahren bei Audio-CDs und Daten-DVDs ein, bei denen Kratzer das Hauptproblem sind. Mittels zweier Reed-Solomon-Codes, die über ein Interleaving-Verfahrens verkettet werden, können auch größere Fehlerbündel und Auslöschungen (Bursts) automatisch korrigiert werden.

Olaf Manz

6. Zyklische Codes und CRC-Verfahren

Zusammenfassung

Nun verweden wir Polynome in einer anderen Weise, wir untersuchen nämlich zyklische Codes, bei denen die Codewörter Vielfache eines festen Generatorpolynoms sind. Der wesentlliche Vorteil zyklischer Codes ist der, dass man mit Ihnen noch deutlich effizienter rechnen kann also nur mit linearen Codes. Wir stellen die hierzu verwendeten Schieberegisterschaltungen zur Polynom-Multiplikation und zur Division mit Rest vor, und gehen dabei besonders auf die Meggitt-Decodierung von zyklischen Codes ein. Unter dem Schlagwort CRC Cyclic Redundancy Check spielen zyklische Codes eine wichtige Rolle bei reiner Fehlererkennung. Das Verfahren wurde 1961 von Wesley Peterson vorgeschlagen und wird heute insbesondere bei Netzwerken (u.a. Ethernet, WLAN, Modbus), Schnittstellen (u.a. USB, Bluetooth) und Speicher-Chips (SanDisk) eingesetzt. Wir lernen dabei auch die wichtigsten standardisierten CRC-Polynome kennen.

Olaf Manz

7. Zyklische Reed-Solomon- und BCH-Codes

Zusammenfassung

Fast gleichzeitig zu den Reed-Solomon-Codes wurden 1959/60 die nach Alexis Hocquenghem, Raj Chandra Bose und Kumar Ray-Chaudhuri benannten BCH-Codes publiziert, nämlich als Teilklasse der zyklischen Codes. Dabei wird uns klar, dass Reed-Solomon-Codes als Spezialfall der BCH-Codes aufgefasst werden können, und daher auch zyklisch sind. Wir machen uns anhand der Anwendungsbeispiele Pager, PDF417 und vor allem QR-Code weiter mit der Materie vertraut. Aufgrund der Wichtigkeit dieser Codes beschreiben wir auch ausführlich die auf sie zugeschnittenen Fehlerkorrekturverfahren. Dabei handelt es sich um die PGZ-Decodierung nach Westley Peterson, Daniel Gorenstein und Neal Zierler aus den Jahren 1960/61, den Berlekamp-Massey-Algorithmus aus den später 1960er Jahren und die Euklid-Decodierung, die Mitte der 1970er entwickelt wurde. Letztlich geben wir einen Ausblick auf die von Valery Goppa 1970 publizierten Goppa-Codes als Verallgemeinerung der BCH-Codes.

Olaf Manz

8. LDPC-Codes

Zusammenfassung

Wir greifen noch eine andere Konstruktionsmethode von Codes auf, die Robert Gallager bereits 1960 vorschlug, die aber in der Folgezeit dem Reed-Solomon- und BCH-Hype zum Opfer fiel: Codes mit dünn besetzten Kontrollmatrizen LDPC (Low Density Parity Check) führen nämlich in der Regel zu effizienteren Fehlerkorrekturverfahren. LDPC-Codes erlebten seit den späten 1990ern eine Art Revival, wobei man allerdings eher mit rechnergestützten Pseudozufallsverfahren die Güte solcher Codes optimiert. Wir erläutern, wie man LDPC-Codes strukturiert mittels Tanner-Graphen beschreiben kann, kümmern uns um die wichtige Teilklasse der RA-Codes (Repeat-Accumulate) und stellen die Bit-Flipping-Decodierung für LDPC-Codes vor. Neben Praxisanwendungen bei Festplatten und GPS gehen wir sehr ausführlich auf das Digitalfernsehen DVB-2 (Digital Video Broadcasting) der 2. Generation ein.

Olaf Manz

9. Faltungscodes

Zusammenfassung

Wir begeben uns nun in eine andere Welt – die der Faltungscodes, bei denen mittels Schieberegisterschaltungen quasi-unendliche Bit-Folgen erzeugt werden. Die Idee zu diesem Codierverfahren geht auf Peter Elias bis ins Jahr 1955 zurück. Wir kümmern uns insbesondere um deren Standardfehlerkorrekturverfahren, das bereits 1967 von Andrew Viterbi vorgeschlagen und 1973 von David Forney mittels Trellis-Diagrammen perfektioniert wurde. Block- und Faltungscodes werden in der Praxis gerne kombiniert als Hybrid verfahren eingesetzt. Dies zeigen wir am Beispiel der NASA, die für die Uranus- und Neptun-Passage von Voyager 2 in den Jahren 1986 und 1989 einen Reed-Solomon-Code verkettet mit einem Faltungscode mit sechs Schieberegisterzellen und zwei Ausgängen implementiert hat. Dabei geben wir auch gleich einen kleinen Überblick über mehrere Jahrzehnte „Codierung in der NASA-Raumfahrt“. Außerdem erläutern wir die Hybridverfahren beim Digitalfernsehen DVB (Digital Video Broadcasting), beim Mobilfunk mit GSM und beim euröpäischen Satellitennavigationssystem Galileo.

Olaf Manz

10. Turbocodes

Zusammenfassung

Das Konzept der Turbocodes wurde erstmalig 1993 von Claude Berrou, Alain Glavieux und Punya Thitimajshima vorgeschlagen. Wenngleich man ihre Güte nur mit Simulationen ermittelt und durch Pseudozufallsverfahren optimieren kann, zählen sie heute zu den besten bekannten Codes. Dies ist vor allem ihrer iterativen Decodiermethode geschuldet, die wir zu verstehen lernen. Dabei handelt es sich um den SOVA Soft-Output-Viterbi-Algorithmus und den BCJR/MAP-Algorithmus (Maximum A-Posteriori Probability). Wir erfahren, welcher Turbocode für den Mobilfunk mit UMTS verwendet wird. Schließlich runden wir das Thema „Raumfahrt“ ab mit dem bei der ESA-Sonde Rosetta implementierten Turbocode, die Ihren Lander Philae 2014 auf dem Kometen Tschuri abgesetzt hat, sowie dem bei der NASA-Sonde New Horizons eingesetzten Turbocode auf ihrem Weg 2015 vorbei an Pluto hinaus in den Kuiper-Gürtel.

Olaf Manz

Backmatter

Titel: Fehlerkorrigierende Codes
verfasst von: Olaf Manz
Verlag: Springer Fachmedien Wiesbaden
Electronic ISBN: 978-3-658-14652-8
Print ISBN: 978-3-658-14651-1
DOI: https://doi.org/10.1007/978-3-658-14652-8