Grundkurs Codierung

Wilfried Dankmeier

Grundkurs CodierungVerschlüsselung, Kompressionund Fehlerbeseitigung

4., überarbeitete Auflage

Wilfried DankmeierEppstein, Deutschland

ISBN 978-3-8348-1674-0 ISBN 978-3-8348-2154-6 (eBook)https://doi.org/10.1007/978-3-8348-2154-6

Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie;detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.

Springer Vieweg# Springer Fachmedien Wiesbaden GmbH 1994, 2001, 2006, 2017Die 1. und 2. Auflage sind unter dem Titel „Codierung“ erschienen.Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklichvom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung des Verlags. Das gilt insbesondere fürVervielfältigungen, Bearbeitungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitungin elektronischen Systemen.Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigtauch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- undMarkenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften.Der Verlag, die Autoren und die Herausgeber gehen davon aus, dass die Angaben und Informationen in diesemWerk zum Zeitpunkt der Ver€offentlichung vollständig und korrekt sind. Weder der Verlag, noch die Autoren oderdie Herausgeber übernehmen, ausdrücklich oder implizit, Gewähr für den Inhalt des Werkes, etwaige Fehler oderÄußerungen. Der Verlag bleibt im Hinblick auf geografische Zuordnungen und Gebietsbezeichnungen inver€offentlichten Karten und Institutionsadressen neutral.

Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier

Springer Vieweg ist Teil von Springer NatureDie eingetragene Gesellschaft ist Springer Fachmedien Wiesbaden GmbHDie Anschrift der Gesellschaft ist: Abraham-Lincoln-Str. 46, 65189 Wiesbaden, Germany

Vorwort

Jawohl, sie haben es nicht leicht! Unsere HighTech-Partner Smartphone, PC, Internet undalle die anderen. Klar, dass sie die ihnen anvertrauten Daten und Informationen mit gr€oßterSorgfalt behandeln müssen und nicht die kleinste Verfälschung daran zulassen dürfen. Unddas, obwohl ihnen fortwährend üble St€orungen das Leben vergällen und schlimme Fehlererzeugen! Wenn dem tatsächlich so ist – wie – werden Sie sich vielleicht fragen, gelingt esdann doch, unsere hohen Ansprüche zu erfüllen?

Zum Beispiel: Ist Ihnen manchmal nicht unwohl, dass Sie die vielen verschiedenenPassw€orter und PINs für Ihre Eurocards, Kreditkarten, Ihren Internet-Provider, fürs Home-banking, für den Zugang zum PC-Netz Ihrer Firma, zu Ihrem Notebook, für Ihr Autoradiousw. immer im Gedächtnis behalten müssen, weil Sie diese Passw€orter natürlich nirgendwoaufschreiben – sicherheitsbewusst wie Sie sind?

Oder: Hätten Sie nicht gern gewusst, ob Sie Ihrer Bestellung im Internet – vielleichtnicht von vorn herein – aber doch wenigstens prinzipiell trauen k€onnen? Überhaupt: Wergibt uns allen eigentlich die Sicherheit, dass ein digitales Bild oder eine elektronischver€offentlichte Einnahmevorschrift für ein Medikament nicht unerkannt und absichtlichverfälscht wurden?

Und schließlich: Eine Freundin übergibt Ihnen auf einer der guten alten Disketten (dieYoungster unter Ihnen kennen solche gar nicht mehr . . .) die neueste Version ihresBuchmanuskriptes zur kritischen Durchsicht vor Übergabe an den Verlag. Es hat mittler-weile einen Umfang von mehr als 4 Mio. Zeichen. Auf Ihren Einwand, dass so eineDiskette doch nur etwa 1,4 Mio. Zeichen fasst, lächelt sie überlegen, murmelt etwas von„Zippen auf weniger als die Hälfte“ und „Sie sollten sich lieber auf das Lesen konzentrie-ren“. Sind Sie jetzt nicht voller Zweifel, ob das mit rechten Dingen zugeht?

Auf den folgenden Seiten werden Sie Antworten auf solche und ähnliche Fragen finden.Das Fachgebiet, mit dem wir uns dabei auseinandersetzen, ist das der Codierungsverfahrenund umfasst die Aufgaben der Datenfehlerbeseitigung, der Verschlüsselung und der Ver-dichtung (oder Kompression). Manches, was wir dabei entdecken, wird Sie vielleichtverblüffen, vor allem schon deshalb, weil wir oft nur mit ganzen Zahlen arbeiten. Vermut-lich haben Sie bisher kaum geahnt, was für erstaunliche Leistungen man aus diesensimplen „Dingern“ herausholen kann.

V

Sie müssen dabei nicht unbedingt von vorn anfangen. Steigen Sie ruhig dort ein, wo esIhnen vernünftig erscheint, und gehen Sie zurück – oder nach weiter hinten, wenn Sie nochgrundlegende Informationen ben€otigen. Einige Hilfen finden Sie besonders in Abschn. 1.3und Kap. 2. Für einen schnellen Überblick ist der Schnupperkurs in Abschn. 1.2 gedacht.

Jedes Codierungsverfahren wird im Text anhand eines ausführlichen Beispiels erläutert.Dort, wo sich lästige Rechnerei (oder auch Nach-Rechnerei) nicht vermeiden lässt, ist essehr zu empfehlen, sich das Leben durch Benutzung kleiner, selbst entwickelter Hilfspro-gramme zu erleichtern. Der angenehme Nebeneffekt liegt darin, dass man bei Programm-erstellung und Austesten sein Verfahrensverständnis oft gewaltig verbessert. Der einge-setzte Rechnertyp (Taschenrechner, PC usw.) und die Programmiersprache ist dabeiziemlich egal, denn es geht hier nicht um ausgefeilte, optimierte Abläufe für den prakti-schen Einsatz. Sehr gut eignen sich übrigens Programme in der Sprache C oder C++. GuteCompiler mit Entwicklungsumgebungen für Windows gibt es dafür kostenfrei z. B. unterwww.bloodshed.com. Noch einfacher: Das kostenfrei aus dem Internet herunter ladbare,bereits bemerkenswert umfangreiche und vielseitige Mathematik-Paket SciLab oder einesder wiederum mächtigeren, allerdings kostenpflichtigen Systeme Matlab oder Mathema-tica, jeweils in den jetzt (2017) aktuellen Versionen (für den Privatgebrauch werdenkostengünstige Vollversionen angeboten).

Und noch etwas: Wenn Sie wollen, beantworten Sie doch die jeweils nach der Behand-lung eines in sich geschlossenen Teilgebietes gestellten Fragen („Was blieb?“). Vielleichthelfen sie Ihnen, eventuelle „Verständnishänger“ aufzuspüren – falls diese überhaupt nochvorhanden sind.

Die drei behandelten Teilgebiete der Codierung werden in aller Welt ständig undintensiv weiterentwickelt. Einer der Gründe liegt in der starken Nachfrage nach besserenund neuen Leistungen der Informations- und Kommunikationstechnik (was hierbei „bes-ser“ bedeuten soll, geht weit über den technischen Aspekt hinaus und ist zu RechtGegenstand kontroverser Diskussionen). Hier spielt unter anderem das Internet einewesentliche Rolle. Die Folge: Dauernd gibt es veränderte, verbesserte oder sogar prinzipi-ell neue L€osungswege für vorhandene Aufgabenstellungen, an denen sich die unterschied-lichsten Fachdisziplinen beteiligen: Mathematiker, Physiker, Ingenieure, Informatiker,Biologen, Mediziner, Wirtschaftswissenschaftler, Medienspezialisten usw. Dementspre-chend groß und vielfältig ist die Zahl der Ver€offentlichungen.

Das vorliegende Buch kann – hoffentlich – einen Eindruck der heute (im Januar 2017)aktuellen Verfahren und Begriffe vermitteln und liefert damit eine Grundlage, auf der beiBedarf mit zusätzlichen Studien aufgebaut werden kann oder auch muss. Als Ergänzungund zur Aktualisierung lohnt es sich auf jeden Fall, im Internet nach weiterem „Material“zu suchen. Sehr zu empfehlen ist eine Anfrage an eine der zahlreichen Suchmaschinen,z. B. mit den Begriffen „Error Correction Code“, „Turbo Produktcode“, „Public Key“,„Fiat Shamir“, „zero knowledge protocol“, „Data Kompression“, „LZW“, „Fourier-Trans-formation“, „jpeg“, „wavelet“, um nur einige ganz wenige Beispiele zu nennen.

Versuchen Sie’s mal! Es macht Spaß und man findet manches Nützliche dabei. DieLektüre der in diesem Buch behandelten Themen – auch einzelner – wird Ihnen helfen, die

VI Vorwort

oft überwältigend umfangreichen, bunt gemischten Ergebnislisten auf Ihre Suchanfragenbesser bewerten und gebrauchen zu k€onnen.

Und wenn Sie doch einmal verzweifeln, steuern Sie die unten genannte Adresse an. DerStein der Weisen ist dort zwar nicht versteckt, aber vielleicht greifen Sie einen derberühmten Strohhalme, um dem Sumpf zu entrinnen.

Und nun viel Vergnügen!

Eppstein im Taunusim Juli 2017

Wilfried Dankmeierwww.vkfco.de1

1. . . auch eine Codierung, . . . aber welche?

Vorwort VII

Inhaltsverzeichnis

1 Aufgabenstellung und Ziel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Beispiele für Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Ein Schnupperkurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 Verschlüsselung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.2 Fehlerbeseitigung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2.3 Kompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Begriffe aus der Informations- und Nachrichtentechnik . . . . . . . . . . . . . 111.4 Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.5 Ziel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.6 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 Mathematische Hilfsmittel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.1 Grundlagen aus der allgemeinen Ingenieurmathematik . . . . . . . . . . . . . 272.2 Weitere mathematische Hilfsmittel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.3 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3 Fehlerbeseitigung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.1 Der Prozess der Fehlerentstehung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.2 Die Prüfstellen: Notwendige und hinreichende Bedingungen für die

Korrektur mit dem Hard-Decison-Verfahren . . . . . . . . . . . . . . . . . . . . . 473.3 Direkte Nutzung des Hammingabstandes . . . . . . . . . . . . . . . . . . . . . . . 513.4 Hamming-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.4.1 Aufbau, Codierung und Hard-Decision-Decodierung . . . . . . . . 533.4.2 Generatormatrix G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.4.3 Paritätsprüfmatrix H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.4.4 Syndrom und Fehlerposition bei HD-Decodierung . . . . . . . . . . 583.4.5 Soft-Decision-Decodierung . . . . . . . . . . . . . . . . . . . . . . . . . . 603.4.6 Technischer Gebrauch des Hamming-Codes . . . . . . . . . . . . . . 613.4.7 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3.5 Leistungsbeurteilung von Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633.5.1 Beschreibung fehlerbehafteter Übertragungssysteme . . . . . . . . 63

IX

3.5.2 Verteilung der Fehler auf die Codew€orter . . . . . . . . . . . . . . . . 673.5.3 Einfluss der Informationsrate auf die Übertragungsrate . . . . . . . 683.5.4 Kriterien: Asymptotisches Verhalten bei langen Codes . . . . . . . 723.5.5 Ein Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743.5.6 Grenzen: Das Theorem von Shannon . . . . . . . . . . . . . . . . . . . 773.5.7 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

3.6 Erweiterungen des Hamming-Verfahrens . . . . . . . . . . . . . . . . . . . . . . . 893.6.1 Verallgemeinerung auf andere Ganzzahlbasen . . . . . . . . . . . . . 893.6.2 Erweiterung um zusätzliche Fehlererkennung . . . . . . . . . . . . . 923.6.3 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

3.7 Zyklische Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 963.7.1 Der Weg und die Mittel: Generatorpolynome und Reste . . . . . . 963.7.2 Bildung der Codew€orter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 983.7.3 Generatorpolynom, irreduzible Polynome und Decodierung . . . 1063.7.4 Generatorpolynome für Mehrbitfehler-Korrektur . . . . . . . . . . . 1093.7.5 Eignungstest für g(x) zur t-Bitfehler-Korrektur . . . . . . . . . . . . 1113.7.6 Irreduzible Polynome über Z2 und Galoisfelder GF(2m) . . . . . . 1133.7.7 BCH-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1183.7.8 Reed-Solomon-Code für Mehrfach-Bündelfehler-Korrektur . . . 1333.7.9 Vergleich zwischen BCH- und Reed-Solomon-Codes . . . . . . . . 1443.7.10 Erkennung von Einzelfehlern und Fehlerbündeln . . . . . . . . . . . 1453.7.11 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

3.8 Goppa-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1503.8.1 Erzeugung der Codew€orter . . . . . . . . . . . . . . . . . . . . . . . . . . . 1503.8.2 Zwei L€osungswege für die Decodierung . . . . . . . . . . . . . . . . . 1593.8.3 Der BCH-Code als Sonderfall des Goppa-Codes . . . . . . . . . . . 174

3.9 Reed-Muller-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1843.10 Interleaving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1943.11 Produkt-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1963.12 Maximum A-Posteriori-Prinzip und Turboprodukt-Codes . . . . . . . . . . . 2023.13 Faltungs-Codes (Convolutional Codes) . . . . . . . . . . . . . . . . . . . . . . . . 2153.14 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

4 R€uckgekoppelte Schieberegister . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2254.1 Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2254.2 Fehlerbeseitigung durch Kreuzkorrelation . . . . . . . . . . . . . . . . . . . . . . 2404.3 Zufallserzeugung von Schlüsselw€ortern . . . . . . . . . . . . . . . . . . . . . . . . 2424.4 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

5 Datenverschl€usselung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2535.1 Datenverschlüsselung zur Informationssicherung . . . . . . . . . . . . . . . . . 2545.2 Verschlüsselung nach dem Data-Encryption-Standard (DES) . . . . . . . . . 256

X Inhaltsverzeichnis

5.3 Verschlüsselung mit dem RSA-Algorithmus . . . . . . . . . . . . . . . . . . . . . 2685.4 Das Rechnen mit großen Ganzzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . 2775.5 Erzeugung großer Pseudoprimzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . 2805.6 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2855.7 Verschlüsselung mit Hilfe des Goppa-Codes . . . . . . . . . . . . . . . . . . . . 2855.8 Ansätze zur Suche nach Schwachstellen . . . . . . . . . . . . . . . . . . . . . . . 2895.9 Verfahren zum Austausch von Schlüsseln (Diffie-Hellmann) . . . . . . . . . 2915.10 Nachweis der Berechtigung (Benutzer-Authentikation) . . . . . . . . . . . . . 2935.11 Nachweis der Unversehrtheit einer Nachricht . . . . . . . . . . . . . . . . . . . . 2995.12 Nachweis der Absenderidentität (digitale Unterschrift, DSA) . . . . . . . . . 3045.13 Hinweise zu PGP und GnuPG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3075.14 Weitere Entwicklungen, Quantenkryptographie . . . . . . . . . . . . . . . . . . 3085.15 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

6 Datenkompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3136.1 Verlustfreie Kompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

6.1.1 Lauflängen-Codierung (Run Length Encoding¼RLE) . . . . . . . 3146.1.2 Huffman- und Fano-Codierung . . . . . . . . . . . . . . . . . . . . . . . . 3156.1.3 Lempel-Ziv-Welch-Codierung (¼ LZW-Codierung) . . . . . . . . . 3186.1.4 Arithmetische Codierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3236.1.5 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

6.2 Verlustbehaftete Kompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3276.2.1 Wesentliche Einspar-Potenziale . . . . . . . . . . . . . . . . . . . . . . . 3276.2.2 Fourier-Transformationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3286.2.3 JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3456.2.4 MPEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3506.2.5 Konkurrenz: Fraktale und Wavelets . . . . . . . . . . . . . . . . . . . . 3606.2.6 Was blieb? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

Literaturauswahl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367

Sachwortverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369

Inhaltsverzeichnis XI

Abbildungsverzeichnis

Abb. 1.1 Normalverteilungen und Rauschsignale rs für zwei verschiedeneEffektivwerte σ bzw. Signal/St€orverhältnisse SNR . . . . . . . . . . . . . . . . . . . . . . . 14

Abb. 1.2 Darstellung der 8 Codew€orter des Binärcodes der Länge n¼3als Würfeleckpunkte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Abb. 3.1 Prozess der Informationsübertragung und Fehlerbeseitigung . . . . . . . . . . . . 46Abb. 3.2 Darstellung der Signale u, us (hier us¼ vs), rs, ws, whd (¼ w)

und e für die zu übertragende Zeichenkette „Geiz“ . . . . . . . . . . . . . . . . . . . . . . . 48Abb. 3.3 Bitfehlerwahrscheinlichkeit BER¼ als Funktion von SNR . . . . . . . . . . . . . . 65Abb. 3.4 Anteile der fehlerfreien und fehlerbehafteten W€orter der der

Länge n¼7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69Abb. 3.5 Mittlere Fehlerverläufe BER¼ für ein uncodiertes Signal

(durchgezogene Linie, wie in Abb. 3.3) und ein Hamming-codiertesSignal bei gleicher Übertragungsgeschwindigkeit der Info-Bits . . . . . . . . . 70

Abb. 3.6 Sendesignal vs0(t) für das ASCII-Zeichen „e“ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81Abb. 3.7 Shannon-Theorem für normal verteilte (durchgezogene Linie) und

bipolare Sendesignale (gestrichelte Linie) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83Abb. 3.8 Verteilungsdichte p(ws) bei bipolarem Sendesignal und normal

verteiltem Rauschen rs mit σrs¼ 0,4 oder SNR¼ 6,25¼ 8 db . . . . . . . . . . . 84Abb. 3.9 Shannon-Grenze bei einem (7,4,3)-Code mit R¼ 0,57: Die

senkrechte, strichpunktierte Linie zeigt die Shannon-Grenze fürR¼ 0,57. Nimmt man ein BER von 10�9 als sehr fehlerarm an, sobeträgt der Abstand zur Shannon-Grenze 15�3,6¼ 11,4 db.Eingetragen ist auch die Shannon-Grenze, wenn R gegen denWert 0 läuft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Abb. 3.10 Modulo-Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99Abb. 3.11 Schema zur Modulo-Division u0(x) MOD g(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . 100Abb. 3.12 Division u(x) � x3 MOD g(x) mittels Schieberegister für g(x)¼1011,

oben u(x)¼1000, unten v(x)¼1000101 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104Abb. 3.13 Schema einer Polynom-Multiplikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

XIII

Abb. 3.14 Ablaufschema für Codierung und Decodierung beim BCH-Code . . . . . . . 119Abb. 3.15 Verschiedene BCH-Codes (¼ BER). Die Linienarten bedeuten:

� durchgezogen: uncodiert – gestrichelt: (7,4,3)-BCH-Code –1-Punkt-Strich: (15,5,7)-BCH-Code – 2-Punkt-Strich: (31,11,9)-BCH-Code – 3-Punkt-Strich: (63,15,13)-BCH-Code – 4-Punkt-Strich:(127,78,15)-BCH-Code – 5-Punkt-Strich: (255,171,23)-BCH-Code . . . . 132

Abb. 3.16 Korrekturleistung eines (255, 239)-Reed-Solomon-Codes (dickeschwarze gestrichelte Linie). Der Verlauf wurde einem Datenblattder Firma AHA entnommen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

Abb. 3.17 Paritätsgleichung eines 16-stelligen Goppa-Codes im GF(24) inMatrizen-Schreibweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Abb. 3.18 Veränderte Paritätsgleichung gemäß Abb. 3.17 auf oberedreiecksähnliche Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

Abb. 3.19 Paritätsgleichung in oberer Dreiecksmatrixform . . . . . . . . . . . . . . . . . . . . . . . . . . 153Abb. 3.20 Matrizengleichung zur Erzeugung eines Goppa-Codes im GF(24) . . . . . . 154Abb. 3.21 Die 16 Codew€orter des Goppa-Codes im GF(24) . . . . . . . . . . . . . . . . . . . . . . . . . 155Abb. 3.22 Paritätskontrolle der 16 Codew€orter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156Abb. 3.23 Paritätsgleichungen des Goppa-Codes mit c(z)¼z6 . . . . . . . . . . . . . . . . . . . . . . . 176Abb. 3.24 Paritätsgleichungen aus Abb. 3.23, auf rechte obere Dreiecksform

reduziert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176Abb. 3.25 Die auf zehn Gleichungen reduzierten Paritätsbeziehungen . . . . . . . . . . . . . 177Abb. 3.26 Generatormatrix für den (15,5)-Goppa-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177Abb. 3.27 Aufbau eines (16,5)-Reed-Muller-Codewortes aus den

Informationsvektor-Elementen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185Abb. 3.28 Bestimmung der Informationswort-Elemente u1, u2, u3 und u4 aus

dem Empfangswort w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188Abb. 3.29 Aufbau eines (16,11)-Reed-Muller-Codewortes aus den

Informationsvektor-Elementen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191Abb. 3.30 Produktcode-Empfangssignalblock ws für die 16 Bits der

ASCII-Zeichen „aß“ → (0110 00001 1101 1111) . . . . . . . . . . . . . . . . . . . . . . . . . 201Abb. 3.31 Verteilung P(vs) und Verbundverteilungsdichte p(rs1, rs2) . . . . . . . . . . . . . . . 205Abb. 3.32 Verteilungsdichte p(ws) des Empfangssignals ws und Verteilung

P(wsHD) bei HD-Demodulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206Abb. 3.33 Bedingte Verteilung p(ws|vs¼ (+1+1)) und Anwendung der

Bayes’schen Beziehung für die bedingte VerteilungP(vs¼ (+1+1) |ws)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

Abb. 3.34 Restfehler eines quadratischen (128, 120)-Turboprodukt-Codes(dicker strichpunktierter Verlauf) im Vergleich zu den Codes ausAbb. 3.15 (BCH-Code, Hamming-Code) und Abb. 3.16 (255,239)RS-Code mit R¼ 0,89 (dicke gestrichelte Linie) . . . . . . . . . . . . . . . . . . . . . . . . . 215

Abb. 3.35 Schieberegister als Faltungscodierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216Abb. 3.36 Trellisdiagramm für die Infofolge u¼ 1011101 . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

XIV Abbildungsverzeichnis

Abb. 3.37 Viterbi-Decodierung der Empfangsfolge w zur optimalen Schätzfolgeu¼ u1, u2, . . ., u7. Die Bits u8, u9, u10 entstehen wegen desAusschwingens der Impulsantwort und k€onnen der Kontrolle dienen . . . . 221

Abb. 4.1 Linear rückgekoppeltes Schieberegister mit m Speichern . . . . . . . . . . . . . . . . 226Abb. 4.2 Zustandsgleichungen in Matrixform für ein rückgekoppeltes

Schieberegister mit m Speichern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229Abb. 4.3 a Schieberegisterfolge A1 und AKF bei nicht minimalem

Rückkopplungspolynom b(z), n¼62. b Wie a, aber n¼60.c Maximallängenfolge n¼25�1¼31 und AKF. d VerschobeneMaximallängenfolge n¼25�1¼31 und AKF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

Abb. 4.4 Maximallängenfolge A3 und ihre AKF für m¼6, n¼63 . . . . . . . . . . . . . . . . . 233Abb. 4.5 Maximallängenfolge A4 und AKF für m¼6, wie A3, aber (fast)

mittelwertfrei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233Abb. 4.6 Kreuzkorrelationsfunktion von A1 und A2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234Abb. 4.7 Kreuzkorrelationsfunktion von A2 und A2a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234Abb. 4.8 Anzahl der irreduziblen Polynome im Z2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236Abb. 4.9 Folge „r“ normal verteilter Rauschsignale und ihre AKF . . . . . . . . . . . . . . . . 241Abb. 4.10 Verrauschte Empfangsfolge w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241Abb. 4.11 AKF von w. Der Anteil A2 im Empfangssignal hat hier durch die

Laufzeit eine Verschiebung erfahren, der beim Empfänger denEindruck erzeugt, das A2a gesendet wurde, was in der AKF abernicht sichtbar ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Abb. 4.12 KKF von A2 und w, der Maximalwert bei k¼6 lässt auf die Laufzeitder Impulsfolge schließen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Abb. 4.13 KKF von A3 und w, der Maximalwert bei k¼6 ist hier deutlicher zuerkennen als in Abb. 4.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Abb. 4.14 Häufigkeitsverteilung der Buchstaben der deutschen Sprache (oben)und des Beispieltextes (unten). Das Zeichen ζ steht dabei für denZwischenraum oder Leerschritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

Abb. 4.15 Häufigkeitsverteilung des mit der MOD(256�128�32)¼MOD(96)-Addition durch das ASCII-Zeichen „C“ (¼67)verschlüsselten Textes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

Abb. 4.16 Häufigkeitsverteilung eines Geheimtextes bei One-time-pad-Verschlüsselung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

Abb. 5.1 a Schema der DES-Teilschlüsselerzeugung. b Permutationslistenfür die DES-Schlüsselerzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

Abb. 5.2 Startphase und Teilschritt 1 der DES-Verschlüsselung mit demTeilschlüssel S1, den Permutationen MIP, ME und MP, denSubstitutionen MS1 bis MS8 und den beiden XOR-Verknüpfungen . . . 259

Abb. 5.3 Die Permutationslisten MIP, MIPI, ME und MP .. . . . . . . . . . . . . . . . . . . . . . . . . 260Abb. 5.4 Die acht Substitutionstabellen MS1 bis MS8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

Abbildungsverzeichnis XV

Abb. 5.5 DES-Ver- und Entschlüsselung mit dem Nullstring als Klartext K;das obere Diagramm zeigt die Teilschlüsselerzeugung . . . . . . . . . . . . . . . . . . . 262

Abb. 5.6 DES-Verschlüsselung und Entschlüsselung wie in Abb. 5.5, aberhier Schlüssel S „Holleri“ und Klartext K „Didudlj€o“ . . . . . . . . . . . . . . . . . . . 264

Abb. 5.7 Zweimalige Verschlüsselung mit einem „schwachen Schlüssel“ inverkürzter Darstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

Abb. 5.8 Beispiele für binäre invertierbare Verschlüsselungsmatrizen Sund Permutationsmatrizen P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

Abb. 5.9 Ungest€orter Übertragungsvorgang der potenziellen Schlüsselbitsohne Abfangen und Weiterleiten durch einen „Man-in-the-middle“-Angreifer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

Abb. 5.10 Der Empfänger stellt nach Ver€offentlichung der Polarisationsfolge fest,dass mehr als 50% der gesendeten Bits von ihm falsch zugeordnetwurden. Sender und Empfänger verwerfen deshalb diese Folge . . . . . . . . 311

Abb. 6.1 Signal s(t) unbekannter Zusammensetzung (identisch mit vs0(t) inAbb. 3.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

Abb. 6.2 a Signalgemisch s0(t) mit Anteil 1,3 fmin, zum Vergleich gestricheltdas Signal s(t) aus Abb. 6.1. b Das aus den Fourierkoeffizienten desSignals s0(t) gemäß Abb. 6.2a ermittelte synthetische Summensignalss0(t), zum Vergleich gestrichelt s0(t) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

Abb. 6.3 a Signal s0(t) aus Abb. 6.1 und gedachte periodische Wiederholung(unsymmetrisch) nach links und rechts. b s00(t) als spiegelsymmetrischeFortsetzung des Signals s0(t). c Synthetisches Signal nachRücktransformation der DFT-Koeffizienten für das auf eine geradeFunktion erweiterte Signal: Im Bereich 0�t<1 zeigt sich die engeÜbereinstimmung mit dem ursprünglichen – gestrichelt dargestellten –Verlauf. Nur an den Bereichsgrenzen bei t¼0 und t¼1 sind kleineAbweichungen zu sehen, die Abtastwerte bleiben identisch . . . . . . . . . . . . . 340

Abb. 6.4 Aus den DCT-Koeffizienten rücktransformiertes Signal. Es stimmtin den Abtastzeitpunkten mit dem ursprünglichen – gestricheltdargestellten – Signal s0(t) überein, ist wegen der fehlendenPhasenwinkel-Information darüber hinaus aber nicht identisch . . . . . . . . . 343

Abb. 6.5 Erzeugung des MP3-Codes aus den Abtastwerten s(ν) desEingangssignals. MDCT ist eine rechentechnische Variante der DCT . . . . 353

Abb. 6.6 Durchlasskurven zweier Bandfilter mit verschiedenenResonanzfrequenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355

Abb. 6.7 a Betragsverlauf des Filterfrequenzganges bei gleicherResonanzfrequenz, aber unterschiedlichen Dämpfungen(gestrichelt D2¼ 0,02). b Phasenwinkelverschiebung desFilterfrequenzganges bei gleicher Resonanzfrequenz, aberunterschiedlichen Dämpfungen (gestrichelt D2¼ 0,02) . . . . . . . . . . . . . . . . . . . . 356

Abb. 6.8 Signalgemisch aus vier Sinuskomponenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

XVI Abbildungsverzeichnis

Abb. 6.9 a Filterwirkung eines Bandfilters mit der Resonanzfrequenz 1000 Hzauf ein Eingangssignal aus vier Frequenzkomponenten(eingeschwungener Zustand). b Wie a, aber Resonanzfrequenz2000 Hz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

Abb. 6.10 a Maskenfunktion für benachbarte Frequenzkomponenten. Die starkeKomponente bei 3 KHz maskiert die links daneben und die beidenrechts liegenden Komponenten, während die dritte von rechts noch„durchschlägt“. b Maskenfunktion für die temporale Wirkung: Einstarkes Signal zum Zeitpunkt t¼0 überdeckt für einige 50 ms leisereEreignisse und überraschenderweise für einige Millisekunden auchkurz davor liegende . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359

Abb. 6.11 Steilflankiges Originalsignal s(t) und die Wiedergabe aus derinversen Fourier-Transformation bei verschiedenen Abtastraten nab.Auch bei Inanspruchnahme sehr vieler Fourierkoeffizienten gelingtdie Nachbildung an den Flanken nicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362

Abb. 6.12 a Zur Wavelet-Transformation: oben: Signal s(t) oder s(x); linksMitte: Mother-Wavelet ψ(t), hier als Funktion nach Haar; links unten:Produkt s(t) �ψ(t), über das durch Integration wie bei derFourier-Transformation der Mittelwert gebildet wird und einen derWavelet-Koeffizienten ergibt; mittlere und rechte Spalte: Baby-Waveletsder zweiten Skalierungsstufe und beide hiermit m€oglichen Trans-lationen sowie die Produkte mit s(t). b Zur Wavelet-Transformation:wie zuvor, aber Baby-Wavelets der dritten Skalierungsstufe und dievier Translationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Abb. 6.13 a Mandelbrotmenge in der komplexen Ebene. b Beim Zoomen aufden Rand trifft man immer neue selbst-ähnliche Punktmengen . . . . . . . . . 365

Abbildungsverzeichnis XVII

Tabellenverzeichnis

Tab. 1.1 Einige ASCII-Zeichen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Tab. 1.2 Hammingabstände der 8 W€orter des Binärcodes der Länge n ¼ 3 . . . . . . . 22

Tab. 2.1 Paarweise Multiplikation aller Elemente im Z5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34Tab. 2.2 Paarweise Multiplikation aller Elemente im Z6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Tab. 3.1 Bildung der Prufstellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55Tab. 3.2 W€orter eines 1-Bit-Fehler korrigierbaren (7,4,3)-Hamming-Codes . . . . . . 56Tab. 3.3 Zuordnung der Syndromwerte zur Fehlerposition . . . . . . . . . . . . . . . . . . . . . . . . . 58Tab. 3.4 Leistungsverhalten des Hamming-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73Tab. 3.5 Simulationsergebnisse fur die Ubertragung des zuvor gezeigten Textes

bei verschieden starken Rauschsignalen ohne Codierung, mit HD- undmit SD-Decodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

Tab. 3.6 und Diagramm: Asymptotisches Verhalten der Shannon-GrenzenSNR/R(R) bis zum absoluten Minimalwert 1,41 db für sinkendeInforaten R. Wegen SNR/R¼ 2 Eb/N0 läge der Minimalwert in derEb/N0-Darstellung bei �1,6 db . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

Tab. 3.7 Syndromzustande bei einem vierstelligen Code im Z3 . . . . . . . . . . . . . . . . . . . . 90Tab. 3.8 Codew€orter des vierstelligen Codes in Z3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91Tab. 3.9 Die 16 W€orter eines (8,4,4)-Hamming-Codes für zusätzliche

2-Bit-Fehler-Erkennung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93Tab. 3.10 Mithilfe des Schieberegisters von Abb. 3.12 erzeugter zyklischer,

systematischer (7,4,3)-Code und durch Multiplikation erzeugter nichtsystematischer (7,4,3)-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

Tab. 3.11 Die sieben unterscheidbaren Syndrompolynome s(x) des 1-bitfehler-korrigierbaren zyklischen Codes der Länge n¼7 . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Tab. 3.12 Einige irreduzible Polynome über Z2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108Tab. 3.13 Die fünf unterscheidbaren Syndrome zu g(x)¼ 11111 . . . . . . . . . . . . . . . . . . . . 109Tab. 3.14 Permutationen verschiedener Fehlermuster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110Tab. 3.15 Notwendige und tatsächliche Anzahlen unterscheidbarer Syndrome . . . . 111Tab. 3.16 Kleinste Gewichte der Basis-Codew€orter als Eignungstest der Codes

auf t-Fehler-Korrekturfähigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

XIX

Tab. 3.17 Testbeispiel „a“ für die Gewichte von Basiscodew€ortern . . . . . . . . . . . . . . . . . 113Tab. 3.18 Testbeispiel „b“ für die Gewichte von Basiscodew€ortern . . . . . . . . . . . . . . . . . 113Tab. 3.19 Das Galoisfeld GF(23) für das definierende Polynom g(x)¼1011 . . . . . . . 115Tab. 3.20 Das Galoisfeld GF(24) für das definierende Polynom g(x)¼ 10011 . . . . . 117Tab. 3.21 Generatorpolynome im GF(23) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123Tab. 3.22 Generatorpolynome im GF(24) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123Tab. 3.23 Generatorpolynome im GF(25) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124Tab. 3.24 Kennzahlen von BCH-Codes verschiedener Länge bei konstanter

Korrektur-Rate RKr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144Tab. 3.25 Kennzahlen von RS-Codes verschiedener Länge bei konstanter

Korrektur-Rate RKr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145Tab. 3.26 Modulare inverse Polynome im GF(24) zu (z – βi) bezüglich des

Polynoms c(z) ¼ z3 + z + 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159Tab. 3.27 Die 15 modularen inversen Polynome im GF(24) zu c(z)¼ z6 . . . . . . . . . . . 175Tab. 3.28 Sendew€orter vs eines (7,4,3)-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209Tab. 3.29 M€ogliche Zustände des Faltungscodierers und Ausgangsfolgen . . . . . . . . . 216Tab. 3.30 Ausgangsfolge v als Überlagerung der mit ui gewichteten

Impulsantworten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

Tab. 5.1 Permutationen T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

XX Tabellenverzeichnis