Fehlerkorrigierende Codes

Fehlerkorrigierende Codes fügen Daten eine strukturierte Redundanz hinzu, sodass Fehler, die während der Übertragung oder Speicherung auftreten, erkannt und korrigiert werden können.

Definition

Ein Code ist eine Menge von Codewörtern, typischerweise Zeichenketten über einem endlichen Alphabet, die so gewählt sind, dass sich beliebige zwei an genügend Positionen unterscheiden, sodass Fehler, die einige Symbole ändern, durch Dekodierung zum nächsten Codewort erkannt oder korrigiert werden können.

Scope

Dieses Thema behandelt die grundlegenden Parameter von Blockcodes – Länge, Dimension und Minimalabstand –, die Hamming-Metrik, lineare Codes sowie deren Generator- und Paritätsprüfmatrizen und Schlüsselcodefamilien wie Hamming-, Reed-Solomon-, BCH- und Reed-Muller-Codes. Es werden grundlegende Grenzen für Codeparameter eingeführt, einschließlich der Singleton-, Hamming- und Gilbert-Varshamov-Grenzen.

Core questions

• Wie viele Fehler kann ein Code bei gegebenem Minimalabstand erkennen und korrigieren?
• Wie werden gute Codes über endlichen Körpern konstruiert?
• Welche grundlegenden Kompromisse bestehen zwischen Länge, Rate und Abstand?
• Wie können Codes effizient dekodiert werden?

Key concepts

• Hamming-Abstand und -Gewicht
• Minimalabstand
• Lineare Codes
• Generator- und Paritätsprüfmatrizen
• Hamming- und Reed-Solomon-Codes
• Singleton- und Hamming-Grenzen

Key theories

Minimalabstand und Fehlerkorrektur

Ein Code mit dem minimalen Hamming-Abstand d kann bis zu d-1 Fehler erkennen und bis zu floor((d-1)/2) Fehler korrigieren, was das zentrale Prinzip ist, das die geometrische Trennung von Codewörtern mit der Fehlerbehandlungsfähigkeit in Beziehung setzt.

Singleton-Grenze und MDS-Codes

Der Minimalabstand eines Codes der Länge n und Dimension k kann n-k+1 nicht überschreiten; Codes, die diese Grenze mit Gleichheit erreichen, wie Reed-Solomon-Codes, sind maximal abstandstrennbar (MDS) und optimal effizient.

Clinical relevance

Fehlerkorrigierende Codes sind in der digitalen Kommunikation und Speicherung unverzichtbar: Sie schützen Daten auf Compact Discs und Festplatten, in QR-Codes, zellularen und Satellitenverbindungen sowie bei der Übertragung in den Weltraum und stellen Verbindungen zu kombinatorischen Designs und endlicher Geometrie her.

History

Shannons Kanalcodierungstheorem von 1948 bewies, dass zuverlässige Kommunikation unterhalb der Kapazität möglich ist, und Hammings Codes von 1950 lieferten die erste praktische Konstruktion, wodurch die Codierungstheorie als Disziplin etabliert wurde.

Key figures

• Claude Shannon
• Richard Hamming
• Irving Reed

Seminal works

• macwilliams1977
• vanlintcoding1999

Frequently asked questions

Wie korrigiert ein Code einen Fehler, ohne zu wissen, wo er sich befindet?

Da gültige Codewörter weit voneinander entfernt sind, ist ein empfangenes Wort mit wenigen Fehlern genau einem Codewort am nächsten, und die Dekodierung zum nächsten Codewort stellt das Original wieder her.

Was ist der Unterschied zwischen Erkennung und Korrektur?

Die Erkennung signalisiert lediglich, dass ein Fehler aufgetreten ist und kann eine erneute Übertragung anfordern, während die Korrektur die beabsichtigten Daten direkt wiederherstellt; die Korrektur erfordert einen größeren Minimalabstand.