Essenzielle Codierungstheorie [pdf]

• Dieses Buch bietet eine umfassende Darstellung der Kernkonzepte der Codierungstheorie und ihrer modernen Entwicklungen
• Es behandelt die Grundprinzipien von fehlerkorrigierenden Codes, die Struktur und Grenzen verschiedener Codes sowie praktische Anwendungsfelder
• Mit besonderem Fokus werden unter anderem Shannons Theorie und Hamming-Codes sowie in der Praxis weit verbreitete Codes wie Reed-Solomon erläutert
• Auch Anwendungsbeispiele in modernen IT-Systemen wie Hashing, Gruppentests und der Schutz biometrischer Daten werden systematisch dargestellt
• Einschließlich Anhängen, Übungsaufgaben und Literaturverweisen ist das Buch als effektives Nachschlagewerk sowohl für Lernende als auch für Praktiker aufgebaut

---

Vorwort

• Dieses Buch basiert auf Vorlesungsunterlagen zur Codierungstheorie von Venkatesan Guruswami, Atri Rudra und Madhu Sudan
• Grundlage sind Lehrveranstaltungen an der University of Washington, CMU, University at Buffalo SUNY, Harvard, MIT und weiteren Institutionen
• Unterstützt durch den NSF CAREER grant CCF-0844796
• Die Ansichten und Ergebnisse der Autoren stellen nicht die offizielle Position der NSF dar
• Verfügbar unter der Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License

Inhaltsübersicht

Kapitel 1: Grundlegende Fragen

• Ziel der Codierungstheorie, grundlegende Definitionen und Codes
• Fehlerkorrektur und das Distanzkonzept von Codes, Hamming-Codes und Schranken
• Klassifikation von Codefamilien, einschließlich Übungsaufgaben und Literaturhinweisen

Teil I: Grundlagen

• Einführung mathematischer Strukturen wie lineare Codes, endliche Körper und Vektorräume
• Effiziente Decodierung von Hamming-Codes und Erklärung des Dualcodes
• Einschließlich Übungsaufgaben und Literaturverweisen

Kapitel 3: Wahrscheinlichkeit und q-äre Entropiefunktion

• Grundlagen der Wahrscheinlichkeitstheorie, probabilistische Methoden, Verständnis der q-ären Entropiefunktion
• Mit zugehörigen Übungsaufgaben und Literaturhinweisen

Teil II: Kombinatorik

• Erläuterung von Codeschranken und Grenzen wie Hamming, Gilbert-Varshamov, Singleton und Plotkin
• Reed-Solomon-Codes, Polynome und Anwendungen endlicher Körper
• Shannons Rauschmodell und Grenzen der Informationsübertragung, im Vergleich zu Hamming
• Erweiterungen wie List Decoding, Johnson Bound und die Kapazität des List Decoding
• Neue Grenztheorien wie Elias-Bassalygo und Schranken aus der linearen Programmierung

Teil III: Verschiedene Codestrukturen

• Polynom-basierte Codes und Anwendungen auf binäre Körper, allgemeine Codestrukturen
• Code-Verkettung (concatenation), Zyablov Bound, fortgeschrittene Verkettungstechniken und Zusammenfassung
• Expander-Graphen und Expander-Codes, Distanzverstärkung und Anwendungsfälle

Teil IV: Algorithmen

• Effiziente Decodierungsverfahren für Reed-Solomon-, Reed-Muller- und verkettete Codes
• Methoden zum Erreichen der BSCp-Kanal-Kapazität sowie innere/äußere Codestrukturen
• Polar-Codes, das Polarization-Prinzip sowie die Implementierung von Encoder/Decoder, Fähigkeiten des List Decoding
• Beschreibung von Codes mit linearer Zeitkomplexität bei der Kodierung und lokaler Reparierbarkeit

Teil V: Anwendungen

• Theorie des Hashings und Kollisionsvermeidung, nahezu universelle Hash-Funktionen, Proof of Data Possession
• Das Konzept des Fuzzy Vault zum Schutz biometrischer Authentifizierung (Fingerabdrücke)
• Formalisierung von Gruppentests (Group Testing), Schranken und Anwendungen auf Data-Stream-Algorithmen
• Komplexität von Codierungsproblemen: Nearest Codeword Problem, Decodierung mit Vorverarbeitung, Approximation, Minimum-Distance-Problem usw.
• Als Themen zur rechnerischen Komplexität werden außerdem Kommunikationskomplexität, Randomisierung, Pseudorandomness, Hardcore Predicates, Average-Case-Hardness-Probleme u. a. behandelt

Anhang

• Symbolverzeichnis, nützliche Ungleichungen und Gleichungen, asymptotische Notation, grundlegender Hintergrund zu Algorithmen und Komplexität
• Algebraische Algorithmen, Einführung in endliche Körper und Polynomoperationen
• Wichtige Konzepte der Informationstheorie: Entropie, bedingte Entropie, gegenseitige Information usw.

Merkmale und praktischer Nutzen

• Bietet umfassend den theoretischen Hintergrund und die praktische Anwendung fehlerkorrigierender Algorithmen, die in moderner Informations- und Kommunikationstechnik, Datenspeicherung und kryptografischen Systemen unverzichtbar sind
• Von Grundkonzepten über aktuelle Entwicklungen bis hin zu praktischen Anwendungen aufbereitet und damit eine breit angelegte Wissensquelle für Berufseinsteiger, Forschende und IT-Praktiker
• Jedes Kapitel enthält Übungsaufgaben und Literaturverweise und eignet sich daher gut für Lernen und selbstgesteuertes Studium
• Kann unter der Creative-Commons-Lizenz frei für akademische und nicht-kommerzielle Zwecke genutzt werden

[GN⁺]

Hacker-News-Kommentare

• Ich möchte hervorheben, dass Claude Shannons „The Mathematical Theory of Communication“ ein grundlegendes Dokument der Informationstheorie ist, das so zugänglich erklärt ist, dass es auch ohne tiefen mathematischen Hintergrund von praktisch jedem gelesen werden kann Link

  • Shannon ist wirklich eine großartige Figur, um mit mathemischem Denken anzufangen. Er leitete das Konzept der Informationsentropie zunächst ohne irgendeine tiefere Bedeutung her, allein aus den Eigenschaften, die er brauchte. Erstaunlicherweise stimmt diese eher zufällig entstandene Definition fast mit der thermodynamischen Entropie der Physik überein, worauf von Neumann hinwies und ihr den Namen gab. Mathematik entwickelt sich oft aus einer logischen Kette der Form „wenn diese Regeln erfüllt sein müssen“, und das ist einer der Gründe, warum viele Menschen sie als schwierig empfinden. Shannons Arbeit liefert nur das Gerüst der Codierungstheorie; eine konkrete Implementierung steht nicht in der Veröffentlichung. Ich habe in einem früheren Startup einmal einen Buchclub organisiert, in dem wir die Buchfassung dieser Arbeit gemeinsam gelesen haben, und ich kann das als wirklich gute Erfahrung zum Verständnis von Informationstheorie und Mathematik im Allgemeinen sehr empfehlen

• Es wäre interessant, mehr dazu aufzunehmen, weil verlustfreie Kompression eng mit generativer KI verbunden ist. Ich möchte eine Dissertation empfehlen, die die Verbindung zwischen verlustfreier Kompression und Machine Learning gut einführt Link

  • Man muss das nicht unbedingt nur auf verlustfreie Kompression beschränken. Tatsächlich kann man fast jedes Machine Learning als eine Form von Kompression verstehen, meist als verlustbehaftete Kompression. Wenn man zum Beispiel nur semantische Embeddings durch einen Kanal sendet, kann man trotzdem Aufgaben lösen, auch ohne den vollständigen Originaltext, weil in den Embedding-Werten genügend Information steckt. Auch Datenklassifikation ist letztlich ein Prozess, bei dem vom Datensatz nur latente Repräsentationen allgemeiner Kategorien übrig bleiben und der Rest verworfen wird. Bei generativer KI funktioniert es gerade deshalb gut, weil wir „verlustbehaftete Kompression“ betreiben. Wir werfen absichtlich Informationen weg, und erst wenn diese Lücken durch Inferenz gefüllt werden müssen, entsteht ein Weg zur Generalisierung. Verlustfreie LLMs wären in der Praxis eigentlich nicht besonders interessant. Die empfohlene Arbeit ist jedoch sehr besonders, weil sie selbst im Bereich Machine Learning seltene verlustfreie Kompression behandelt

• Als gutes neueres Material gibt es das Lehrbuch <i>Information Theory: From Coding to Learning</i>. Es gibt auch eine Online-PDF-Version, die man sich ansehen kann Link

  • Ich möchte auch David MacKays <i>Information Theory, Inference, and Learning Algorithms</i> empfehlen Link

• Um die Frage zu beantworten, was „Coding“ hier bedeutet: Gemeint ist das Kodieren und Dekodieren, also das Umwandeln von Information aus einer Darstellung in eine andere. Solche Systeme nennt man Codes, und sie werden so entworfen, dass sie bei der Informationsübertragung gegen Störungen, Verfälschung oder Abhören resistent sind. Coding wird also in vielen Bereichen eingesetzt, darunter Datenkompression, Verschlüsselung, Fehlererkennung und -korrektur sowie Datenübertragung und -speicherung Link

  • Das erwähnte Buch konzentriert sich insbesondere auf Fehlerkorrekturcodes. Beim Übertragen einer Nachricht werden zusätzliche Daten angehängt, damit verlorene Teile wiederhergestellt werden können. Die zu lösende Schwierigkeit besteht darin, diese zusätzlichen Daten so zu entwerfen, dass mit minimalem Overhead und in vertretbarer Rechenzeit genügend Fehler korrigiert werden können. Solche Techniken werden tatsächlich in sehr vielen Bereichen eingesetzt, etwa bei WiFi, Festplatten, QR-Codes und RAM. Zum Beispiel steht das ECC in ECC RAM genau für einen Fehlerkorrekturcode. In DDR5 ist diese Technik in Teilen inzwischen verpflichtend

• Da hier gerade kostenlose CS-E-Books geteilt werden, möchte ich auch Jeff E.s Algorithms-Buch nachdrücklich empfehlen. Für alle, die Algorithmen lernen oder ihre Kenntnisse auffrischen möchten, ist es Pflichtlektüre Link

• Ich habe ein paar Kapitel dieses Buches gelesen und bin wirklich sehr zufrieden damit. Ich habe vor, es in den nächsten Wochen oder vielleicht Monaten langsam weiterzulesen

• Wenn man Informationstheorie und Codierungstheorie tiefer studieren möchte, würde ich auch die folgenden Materialien empfehlen. Für Fehlerkorrekturcodes: „Error-Correcting Codes“ von W. Wesley Peterson und E. J. Weldon, Jr.; und für abstrakte Algebra, insbesondere Körpertheorie: „Commutative Algebra“ von Oscar Zariski und Pierre Samuel

  • LaTeX-Befehle funktionieren hier nicht

• Wenn ich ein paar Bücher für Einsteiger empfehlen sollte:

  1. John R. Pierces <i>An Introduction to Information Theory, Symbols, Signals and Noise</i> – ein Klassiker, der sich gut eignet, um Konzepte zu verstehen und Intuition aufzubauen. Andere Bücher desselben Autors sind ebenfalls hervorragend
  2. James V. Stones <i>Information Theory: A Tutorial Introduction</i> – ein leicht zugängliches und gutes Einsteigerbuch. Auch andere Tutorials des Autors sind nützlich
  3. Stefan Moser und Po-ning chens <i>A Student's Guide to Coding and Information Theory</i> – ein kompakter und klarer Leitfaden, und auch andere Bücher aus derselben Reihe sind empfehlenswert

• Immer wenn jemand sagt, „das ist essenziell“, ist das für mich als jemanden, der das Thema im Studium höchstens gestreift hat, immer ein leicht einschüchternder Moment

  • Mit „essenziell“ ist in diesem Kurs weniger gemeint, dass es etwas sei, das alle Informatikstudierenden unbedingt wissen müssten, sondern eher, dass es die Essenz der Codierungstheorie enthält. Einer der Mitautoren des Buches hält an unserer Universität selbst eine Vorlesung dazu, und diese Veranstaltung ist ein Wahlfach in höheren Semestern mit überwältigend viel Mathematik. In einem vierjährigen Informatikstudium belegen sie meist nur sehr wenige Studierende im letzten Studienjahr, und alle Freunde in meinem Umfeld, die den Kurs besucht haben, waren Leute, die mathematische Beweise mochten. Ihnen hat der Kurs gefallen

  • Wenn irgendwo „essenziell“ oder „Einführung“ draufsteht, ist das oft eine Vorankündigung, dass ein extrem dichtes Lehrbuch auf einen wartet