Der Zweck der Kanalcodierungstheorie besteht darin, Codes zu finden, die schnell übertragen, viele gültige Codewörter enthalten und viele Fehler korrigieren oder zumindest erkennen können. Obwohl sie sich nicht gegenseitig ausschließen, ist die Leistung in diesen Bereichen ein Kompromiss. Daher sind verschiedene Codes für verschiedene Anwendungen optimal. Die erforderlichen Eigenschaften dieses Codes hängen hauptsächlich von der Wahrscheinlichkeit ab, dass Fehler während der Übertragung auftreten. Bei einer typischen CD besteht die Beeinträchtigung hauptsächlich aus Staub oder Kratzern.

CDs verwenden eine verschachtelte Reed-Solomon-Codierung, um die Daten auf der Festplatte zu verteilen.

Obwohl kein sehr guter Code, kann ein einfacher Wiederholungscode als verständliches Beispiel dienen. Angenommen, wir nehmen einen Block von Datenbits (der Ton darstellt) und senden ihn dreimal. Am Ende werden wir die drei Wiederholungen Stück für Stück prüfen und mehrheitlich abstimmen. Die Wendung dabei ist, dass wir nicht nur die Bits in der richtigen Reihenfolge senden. Wir verschachteln sie. Der Block der Datenbits wird zunächst in 4 kleinere Blöcke unterteilt. Dann durchlaufen wir den Block und senden ein Bit vom ersten, dann vom zweiten usw. Dies geschieht dreimal, um die Daten über die Oberfläche der Festplatte zu verteilen. Im Kontext des einfachen Wiederholungscodes scheint dies möglicherweise nicht effektiv zu sein. Es sind jedoch leistungsfähigere Codes bekannt, die sehr effektiv bei der Korrektur des „Burst“ -Fehlers eines Kratzers oder eines Staubflecks sind, wenn diese Verschachtelungstechnik verwendet wird.

Andere Codes sind für verschiedene Anwendungen besser geeignet. Die Kommunikation im Weltraum wird durch das thermische Rauschen des Empfängers begrenzt, das eher kontinuierlicher Natur als burstiger Natur ist. Ebenso werden Schmalbandmodems durch das im Telefonnetz vorhandene Rauschen begrenzt und auch besser als kontinuierliche Störung modelliert. Mobiltelefone unterliegen einem schnellen Verblassen. Die verwendeten hohen Frequenzen können ein schnelles Verblassen des Signals verursachen, selbst wenn der Empfänger einige Zentimeter bewegt wird. Auch hier gibt es eine Klasse von Kanalcodes, die das Verblassen bekämpfen sollen.

Lineare Kodesbearbeiten

Der Begriff algebraische Kodierungstheorie bezeichnet das Teilgebiet der Kodierungstheorie, in dem die Eigenschaften von Codes in algebraischen Begriffen ausgedrückt und dann weiter erforscht werden.

Die algebraische Codierungstheorie ist grundsätzlich in zwei Haupttypen von Codes unterteilt:

• Lineare Blockcodes
• Faltungscodes

Sie analysiert die folgenden drei Eigenschaften eines Codes – hauptsächlich:

• Codewortlänge
• Gesamtzahl der gültigen Codewörter
• Der Mindestabstand zwischen zwei gültigen Codewörtern, wobei hauptsächlich der Hamming-Abstand verwendet wird, manchmal auch andere Entfernungen wie der Lee-Abstand

Lineare Blockcodeedit

Lineare Blockcodes haben die Eigenschaft der Linearität, dh die Summe von zwei beliebigen Codewörtern ist auch ein Codewort, und sie werden auf die Quellbits in Blöcken angewendet, daher der Name lineare Blockcodes. Es gibt Blockcodes, die nicht linear sind, aber es ist schwierig zu beweisen, dass ein Code ohne diese Eigenschaft gut ist.

Lineare Blockcodes werden durch ihre Symbolalphabete (z. B. binär oder ternär) und Parameter (n, m, dmin) zusammengefasst, wobei

1. n die Länge des Codeworts in Symbolen ist,
2. m ist die Anzahl der Quellensymbole, die gleichzeitig zum Codieren verwendet werden,
3. dmin ist der minimale Hamming-Abstand für den Code.

Es gibt viele Arten von linearen Blockcodes, wie

1. Zyklische Codes (z. Hamming-Codes)
2. Wiederholungscodes
3. Paritätscodes
4. Polynomcodes (z. B. BCH–Codes)
5. Reed–Solomon-Codes
6. Algebraische geometrische Codes
7. Reed-Muller-Codes
8. Perfekte Codes

Blockcodes sind an das Problem der Kugelpackung gebunden, das im Laufe der Jahre einige Aufmerksamkeit erhalten hat. In zwei Dimensionen ist es leicht zu visualisieren. Nehmen Sie ein paar Pfennige flach auf den Tisch und schieben Sie sie zusammen. Das Ergebnis ist ein Sechseckmuster wie ein Bienennest. Blockcodes basieren jedoch auf mehr Dimensionen, die nicht einfach visualisiert werden können. Der leistungsstarke (24,12) Golay-Code, der in der Weltraumkommunikation verwendet wird, verwendet 24 Dimensionen. Wenn sie als Binärcode verwendet werden (was normalerweise der Fall ist), beziehen sich die Abmessungen auf die Länge des Codeworts, wie oben definiert.

Die Theorie der Codierung verwendet das N-dimensionale Kugelmodell. Zum Beispiel, wie viele Pfennige können in einen Kreis auf einer Tischplatte verpackt werden, oder in 3 Dimensionen, wie viele Murmeln können in einen Globus verpackt werden. Andere Überlegungen geben Sie die Wahl eines Codes ein. Wenn Sie beispielsweise ein Sechseck in die Einschränkung einer rechteckigen Box packen, bleibt an den Ecken leerer Platz. Wenn die Dimensionen größer werden, wird der Prozentsatz des leeren Raums kleiner. Bei bestimmten Abmessungen nutzt die Verpackung jedoch den gesamten Platz und diese Codes sind die sogenannten „perfekten“ Codes. Die einzigen nichttrivialen und nützlichen perfekten Codes sind die Distanz-3-Hamming-Codes mit Parametern, die (2r – 1, 2r – 1 – r, 3) erfüllen, und die binären und ternären Golay-Codes.

Eine weitere Codeeigenschaft ist die Anzahl der Nachbarn, die ein einzelnes Codewort haben kann.Betrachten Sie erneut Pennies als Beispiel. Zuerst packen wir die Pfennige in ein rechteckiges Gitter. Jeder Penny hat 4 Nachbarn in der Nähe (und 4 an den Ecken, die weiter entfernt sind). In einem Sechseck hat jeder Cent 6 Nachbarn in der Nähe. Wenn wir die Dimensionen vergrößern, nimmt die Anzahl der nahen Nachbarn sehr schnell zu. Das Ergebnis ist, dass die Anzahl der Möglichkeiten für Rauschen, den Empfänger dazu zu bringen, einen Nachbarn auszuwählen (daher ein Fehler), ebenfalls zunimmt. Dies ist eine grundlegende Einschränkung von Blockcodes und in der Tat aller Codes. Es kann schwieriger sein, einem einzelnen Nachbarn einen Fehler zuzufügen, aber die Anzahl der Nachbarn kann groß genug sein, so dass die Gesamtfehlerwahrscheinlichkeit tatsächlich darunter leidet.

Eigenschaften von linearen Blockcodes werden in vielen Anwendungen verwendet. Zum Beispiel wird die Syndrom-Coset-Eindeutigkeitseigenschaft von linearen Blockcodes bei der Trellis-Formung verwendet, einem der bekanntesten Formungscodes.

Convolutional codesEdit

Die Idee hinter einem Convolutional Code ist es, jedes Codewortsymbol zur gewichteten Summe der verschiedenen Eingabenachrichtensymbole zu machen. Dies ist wie die Faltung, die in LTI-Systemen verwendet wird, um den Ausgang eines Systems zu finden, wenn Sie den Eingang und die Impulsantwort kennen.

Wir finden also im Allgemeinen die Ausgabe des Systemfaltungscodierers, die die Faltung des Eingabebits ist, gegen die Zustände des Faltungscodierers, Register.

Grundsätzlich bieten Faltungscodes nicht mehr Schutz vor Rauschen als ein äquivalenter Blockcode. In vielen Fällen bieten sie im Allgemeinen eine einfachere Implementierung als ein Blockcode gleicher Leistung. Der Encoder ist normalerweise eine einfache Schaltung, die über einen Zustandsspeicher und eine Rückkopplungslogik verfügt, normalerweise XOR-Gatter. Der Decoder kann in Software oder Firmware implementiert werden.

Der Viterbi-Algorithmus ist der optimale Algorithmus zum Dekodieren von Faltungscodes. Es gibt Vereinfachungen, um die Rechenlast zu reduzieren. Sie verlassen sich darauf, nur die wahrscheinlichsten Pfade zu suchen. Obwohl sie nicht optimal sind, haben sie sich im Allgemeinen als gute Ergebnisse in geräuscharmen Umgebungen erwiesen.

Faltungscodes werden in Voiceband-Modems (V.32, V.17, V.34) und in GSM-Mobiltelefonen sowie in Satelliten- und militärischen Kommunikationsgeräten verwendet.