Skip to main content

2024 | Buch

Elemente der Codierungstheorie

Besser sehen, besser hören, besser informieren

verfasst von: Hermann Kautschitsch, Gert Kadunz

Verlag: Springer Berlin Heidelberg

Buchreihe : Mathematik Primarstufe und Sekundarstufe I + II

insite
SUCHEN

Über dieses Buch

Im täglichen Leben sind wir zunehmend von Codes umgeben, die mathematisch konstruiert werden. Sie sind teils leicht erkennbar (Strichcode, ISBN, IBAN, QR) und teils eher verborgen (GPS, WLAN, CD, DVD). In diesem Buch werden solche Codes vorgestellt. Es wird dargelegt, wie sie aufgebaut sind, wie sie funktionieren und welche Mathematik zu ihrer Entwicklung und Anwendung notwendig ist. Die Lesenden lernen, eigenhändig Codes zu erstellen, Fehler zu erkennen und zu korrigieren:

EAN, ISBN und deren Barcodedarstellung sowie die internationale Bankkontonummer IBAN werden erarbeitet.Kleine QR-Codes werden mit den vorgestellten Methoden (Paritätsprüfung, Linearcode, Polynomcode, zyklischer Code und Reed-Solomon Code) anschaulich realisiert.An der Herstellung einer Mini-CD mit einem CIRC-Code über einem kleinen Körper werden wesentliche Konstruktionsprinzipien von neuen Codes aus bestehenden Codes, wie z.B. Kürzen, Erweitern, Spreizen (Interleaving) und gekreuztes Spreizen (Cross-Interleaving) veranschaulicht.

Das Verstehen von Mathematik wird durch diese selbstständige Erstellung und Verwendung didaktisch maßgeschneiderter Codes wesentlich gefördert.

Ein besonderer Fokus des Buchs liegt auf elementaren Methoden des Rechnens mit ganzen Zahlen und Polynomen. Für diese benötigt man nur den Satz von der Division mit Rest als zentrale Aussage – daher können große Abschnitte bereits mit Lernenden der Sekundarstufe II erarbeitet und die Grundlagen wesentlicher Teile der Codierungstheorie von den Lernenden mathematisch korrekt erfasst werden. Für Ausführungen, zu deren Verständnis Kenntnisse notwendig sind, die über die Mathematik der Sekundarstufe II hinausgehen, liegt ein ausführlicher Anhang vor (Vektorräume, Matrizen, Rechnen in endlichen Körpern).

Inhaltsverzeichnis

Frontmatter
1. Einleitung
Zusammenfassung
Auf einem Notenblatt ist „codiert”, welche Töne wie lange, wie laut und von wem gespielt (gesungen) werden sollen (Abb. 1.1). Mit unterschiedlichsten „Zeichen“ hat der Komponist versucht, seine Melodie- und Klangvorstellungen und seine Empfindungen der Öffentlichkeit zu übermitteln. Nach einer gehörigen Übungszeit können Musiker auf der ganzen Welt in „Echtzeit“ uns ihre Interpretation der Klangvorstellungen des Komponisten vermitteln. Sie verarbeiten diesen Code. An der Kasse von Supermärkten, auf der Rückseite von Büchern, Waren aller Art oder anderen Gegenständen erkennt man „Bildmuster“, die Informationen auf kleinstem Raum vermitteln (Haftendorn, 2016, S. 45).
Hermann Kautschitsch, Gert Kadunz
2. Sichtbare Codes im Alltag
Zusammenfassung
Bevor es zu einem systematischen Aufbau von Elementen der Codierungstheorie kommt, sollen Erfahrungen im Umgang mit einfachen Codes gesammelt werden. In diesem Kapitel werden „sichtbare“ Codes besprochen, die uns täglich immer öfter begleiten. Dies sind zum einen die eindimensionalen Strichcodes (Barcodes), bei denen unterschiedlich breite schwarze bzw. weiße Balken linear aufeinanderfolgen (EAN, ISBN, …) oder Zeichenketten (Strings) aus Großbuchstaben und Ziffern aus {0, …, 9} (IBAN, EURO-Seriennummer). Zum anderen sind es die zweidimensional angeordneten schwarz-weiß gefärbten Quadrate (QR-Codes).
Hermann Kautschitsch, Gert Kadunz
3. Theoretische Grundlagen
Zusammenfassung
Nachdem in Kap. 2 praktische und theoretische Erfahrungen mit Elementen der Codierungstheorie an alltäglichen Codierungen gesammelt wurden, wollen wir in diesem Kapitel grundlegende Begriffe der Codierungstheorie allgemein beschreiben. Dabei werden Wörter als n-Tupel über einem Alphabet A und Codes als „bloße“ Teilmengen das An, also ohne irgendeine Rechenstruktur, aufgefasst. Insbesondere beschränken wir uns auf Wörter der konstanten Länge n, die jeweils eine konstante Anzahl k von zu übermittelnden Nachrichtenzeichen und damit n − k Prüfzeichen enthalten. Man spricht von (n, k)-Blockcodes. Auf die Faltungscodes wird in diesem Buch nicht eingegangen. Diese Prüfzeichen werden der Nachricht gerne vorangestellt oder angehängt. Damit kann nach der Decodierung des gesendeten (gespeicherten) Wortes die Nachricht sofort abgelesen werden (systematische Codierung). Als zentral für die Erkennung und Korrektur von Fehlern erweist sich der dem anschaulichen Abstand nachempfundene Hamming-Abstand zweier Codewörter. Mit ihm kann als eine Decodierungsstrategie die Hamming-Decodierung formuliert werden. Sie erweist sich der Maximum-Likelihood-Decodierung (MLD) als gleichwertig, sofern man annimmt, dass die Übertragungskanäle binär und symmetrisch sind sowie die Fehlerwahrscheinlichkeit je Bit kleiner als 0,5 ist. Dies ist in der Praxis oft der Fall. Um der bei der Hamming-Decodierung möglichen „sinnlosen“ Decodierung entgegenzuwirken, wird die Strategie der Bounded-Distance-Decodierung (BD) eingeführt und eine Schranke für den Abbruch einer Decodierung entwickelt. Dazu und zur Definition von t-fehlererkennenden bzw. t-fehlerkorrigierenden Codes erweist sich der ebenfalls der Anschauung entliehene Begriff der t-Umgebung bzw. der „Kugelumgebung“ eines Wortes als nützlich. Der Minimalabstand d eines Codes zeigt sich als entscheidende Größe für die Fehlerkorrekturkapazität. Damit werden die in Kap. 2 vorgestellten Codes untersucht. Die Informationsrate eines Codes stellt eine weitere Maßzahl für die „Güte“ eines Codes dar. Es wird auf die Frage eingegangen, welche Anforderungen ein „guter“ (n, k, d)-Blockcode erfüllen soll. Dazu werden zwei der wichtigsten Schranken der Codierungstheorie entwickelt, die Hamming- und die Singleton-Schranke. Wird in den entsprechenden Ungleichungen die Gleichheit erreicht, so spricht man von perfekten Codes bzw. von optimalen Codes (MDS-Codes). Am Ende des Kapitels wird auf die Namensgebung dieser „Maximal Distance Separable“ Codes experimentell eingegangen. Mit dem Wort „optimal“ wird ausgedrückt, dass ein Code die maximale Anzahl von Wörtern enthält. Mit dem Wort „perfekt“ wird ausgedrückt, dass der Idealfall der vollständigen Überdeckung der Wortmenge An durch elementfremde Kugeln erreicht wird. In solchen Codes ist die Decodierungsstrategie „Decodierung zum Kugelmittelpunkt“ möglich. Auf die zur Menge der perfekten Codes gehörigen Hamming-Codes und die Golay-Codes wird in Kap. 4 eingegangen.
Hermann Kautschitsch, Gert Kadunz
4. Lineare Codes
Zusammenfassung
In den bisherigen Überlegungen haben wir überwiegend Wörter als Konkatenationen von Zeichen aus einem Alphabet A gedeutet. Die Codes C waren damit nur Teilmengen von An. Als Alphabete wurden A = {0,1}, A = {0,1, …, 9} oder andere Teilmengen von verwendet. Daraus ergaben sich eine Reihe von Nachteilen.
Hermann Kautschitsch, Gert Kadunz
5. Polynomcodes
Zusammenfassung
Im Kap. 4 wurden Codewörter der Länge n über einem Körper \( \mathbb {K} \) als Vektoren des \( {\mathbb {K}}^n \) aufgefasst. Besonders leistungsfähige Codes über \( \mathbb {K} \) waren damit nicht nur Teilmengen des \( {\mathbb {K}}^n \), sondern sogar Teilräume des \( {\mathbb {K}}^n \). Ihre Effizienz beruhte auf der Möglichkeit, die Theorie der Vektorräume einfließen lassen zu können. Dazu war es notwendig, als Alphabete Körper vorauszusetzen. Nun gehen wir einen Schritt weiter und fassen Codewörter als Polynome über \( \mathbb {K} \) auf. Beim Rechnen mit Polynomen gibt es im Gegensatz zum Rechnen mit Vektoren zusätzlich eine Multiplikation und damit eine Division (gegebenenfalls mit Rest), analog zur „Division mit Rest“ beim Rechnen mit ganzen Zahlen (vgl. Abschn. 10.​8). Wir bemerken, dass die „Skalarmultiplikation“ zweier Vektoren als Ergebnis nur ein Element des Körpers \( \mathbb {K} \) ergibt und damit keine „echte“ algebraische Operation ist (vgl. zu diesem Problemkreis die Überlegungen zum Begriff der algebraischen Operation in Abschn. 10.​3).
Hermann Kautschitsch, Gert Kadunz
6. Zyklische Codes
Zusammenfassung
Die Leistungsfähigkeit von Codes, welche so bekannten alltäglichen Anwendungen wie USB, Bluetooth, WLAN, SD-Karten, CD, DVD … zugrunde liegen, beruht auf der Eigenschaft, dass sie mit jedem Codewort auch jenes mit „zyklisch“ vertauschten Komponenten enthalten. Nachdem im Kap. 5 die große Effizienz von Polynomcodes herausgearbeitet wurde, wird zunächst versucht, die Zyklizität mittels Polynommultiplikation zu erzeugen. Dies gelingt durch Ersetzung des Resultates des Produktes der „gewöhnlichen“ Polynommultiplikation durch den Rest bei Division durch (xn − 1). Dieses Produkt wird als „∗-Produkt“ bezeichnet. Zyklische Codes können dann als „Ideale“ in dem „neuen“ Polynomring \( \left(\mathbb {K}{\left[x\right]}_n,+,\ast \right) \) charakterisiert werden. Zyklische Codes C erhalten damit eine reichhaltigere algebraische Struktur als lineare Codes. Sie besitzen zusätzlich zur Teilraumstruktur noch eine Idealstruktur. Mit Codewörtern kann man damit nicht nur Linearkombinationen bilden, sondern sie auch mit beliebigen Polynomen multiplizieren, ohne C zu verlassen. So gelingt dann der Nachweis, dass zyklische Codes Polynomcodes bezüglich eines eindeutig bestimmten normierten Generatorpolynoms sind. Dieser Nachweis wird elementar ohne Verwendung von Begriffen aus der höheren Algebra (Faktorring, Hauptidealring) geleistet. Analog zur Kontrollmatrix bei Linearcodes gibt es auch bei zyklischen Codes ein Kontrollpolynom, das sogar eindeutig bestimmt ist. Damit kann wie im linearen Fall eine Syndromdecodierung mittels Polynomen aufgebaut werden. Wegen der reichhaltigeren algebraischen Struktur der zyklischen Codes ist diese effizienter als die Decodierung mittels Syndromen der Nebenklassenführer bei linearen Codes.
Hermann Kautschitsch, Gert Kadunz
7. Reed-Solomon-Codes
Zusammenfassung
Wir wenden uns nun den derzeit in Anwendungen weitverbreiteten Reed-Solomon-Codes (RS-Codes) zu. Sie zählen ebenfalls zu den Blockcodes. Weitere Codeentwicklungen stellen die sogenannten Faltungscodes und Turbocodes dar, auf die wir aus Platzgründen nicht eingehen können.
Hermann Kautschitsch, Gert Kadunz
8. Spreizen und Kreuzen von Linearcodes
Zusammenfassung
Bereits beim QR-Code (vgl. Abschn. 2.​4) hat es sich gezeigt, dass es aufgrund von mechanischen Belastungen zweckmäßig ist, die Komponenten eines Codewortes nicht hintereinander, sondern „zerrissen“ in das Quadrat einzutragen. Dadurch konnten sogar fünf Fehler korrigiert werden, obwohl der dort verwendete Hamming-Code selbst nur einen Fehler korrigiert. Hätte man im angegebenen Beispiel die Komponenten eines Codewortes hintereinander eingetragen, wäre es zu einem totalen Datenverlust gekommen. Auch auf einer CD kann es durch Kratzer nicht nur zu verstreuten Fehlern, sondern zu mehreren Fehlern hintereinander kommen. Es entsteht ein Fehlerbündel (vgl. Abschn. 6.​2). Ähnliche Verluste können beim Senden von Daten durch „Funklöcher“ auftreten. Wie wir bereits gesehen haben, eignen sich zyklische Codes gut, um solche Fehlerbündel zu erkennen und zu korrigieren (Satz 6.5).
Hermann Kautschitsch, Gert Kadunz
9. CIRC-Codes
Zusammenfassung
In diesem Kapitel wollen wir eine Reihe der bisher vorgestellten Codierungstechniken (Verkürzung, Spreizung, Kreuzung) bei ihrer Verwendung zur Aufzeichnung und Wiedergabe von Audio- und Videosignalen betrachten. Dazu werden wegen der großen Fehlerkorrekturkapazität und der schnellen Speicher- und Lesefähigkeit verkürzte RS-Codes verwendet (vgl. Kap. 7).
Hermann Kautschitsch, Gert Kadunz
10. Anhänge
Zusammenfassung
Mengen und Abbildungen sind zentrale Begriffe in der Mathematik. Für die Ziele dieses Buches genügen intuitive „Definitionen“.
Hermann Kautschitsch, Gert Kadunz
Backmatter
Metadaten
Titel
Elemente der Codierungstheorie
verfasst von
Hermann Kautschitsch
Gert Kadunz
Copyright-Jahr
2024
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-67520-5
Print ISBN
978-3-662-67519-9
DOI
https://doi.org/10.1007/978-3-662-67520-5