Wiederholungscode - Repetition code

In der Codierungstheorie ist der Wiederholungscode einer der grundlegendsten Fehlerkorrekturcodes . Um eine Nachricht über einen verrauschten Kanal zu übertragen, der die Übertragung an einigen Stellen beschädigen kann, besteht die Idee des Wiederholungscodes darin, die Nachricht nur mehrmals zu wiederholen. Die Hoffnung ist, dass der Kanal nur eine Minderheit dieser Wiederholungen korrumpiert. Auf diese Weise wird der Empfänger feststellen, dass ein Übertragungsfehler aufgetreten ist, da der empfangene Datenstrom nicht die Wiederholung einer einzelnen Nachricht ist, und außerdem kann der Empfänger die ursprüngliche Nachricht wiederherstellen, indem er die empfangene Nachricht in dem am häufigsten auftretenden Datenstrom betrachtet.

Aufgrund der schlechten Fehlerkorrekturleistung und des geringen Verhältnisses zwischen Informationssymbolen und tatsächlich übertragenen Symbolen werden in den meisten Fällen andere Fehlerkorrekturcodes bevorzugt. Die Hauptattraktion des Wiederholungscodes ist die einfache Implementierung.

Code-Parameter

Im Fall eines binären Wiederholungscodes existieren zwei Codewörter - alle Einsen und alle Nullen - mit einer Länge von . Daher entspricht der minimale Hamming-Abstand des Codes seiner Länge . Dies gibt dem Wiederholungscode eine Fehlerkorrekturkapazität von (dh er korrigiert bis zu Fehlern in jedem Codewort). ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle {\ tfrac {n-1} {2}}}$${\ displaystyle {\ tfrac {n-1} {2}}}$

Wenn die Länge eines binären Wiederholungscodes ungerade ist, ist es ein perfekter Code . Der binäre Wiederholungscode der Länge n entspricht dem ( n , 1) - Hamming-Code .

Beispiel

Betrachten Sie einen binären Wiederholungscode der Länge 3. Der Benutzer möchte die Informationsbits übertragen 101 . Dann ordnet die Codierung jedes Bit entweder dem Codewort für alle Einsen oder alle Nullen zu, so dass wir das erhalten 111 000 111 , das übertragen wird.

Angenommen, drei Fehler verfälschen die gesendeten Bits und die empfangene Sequenz ist 111 010 100 . Die Dekodierung erfolgt normalerweise durch eine einfache Mehrheitsentscheidung für jedes Codewort. Das führte uns zu 100 den decodierten Informationsbits, da im ersten und zweiten Codewort weniger als zwei Fehler auftraten, so dass die Mehrzahl der Bits korrekt ist. Im dritten Codewort sind jedoch zwei Bits verfälscht, was zu einem fehlerhaften Informationsbit führt, da zwei Fehler über der Fehlerkorrekturkapazität liegen.

Anwendungen

Trotz ihrer schlechten Leistung als eigenständige Codes ermöglicht die Verwendung in Turbo-Code- ähnlichen iterativ decodierten verketteten Codierungsschemata wie Wiederholungsakkumulations- (RA) und Akkumulations-Wiederholungsakkumulations- (ARA) -Codes eine überraschend gute Fehlerkorrekturleistung.

Wiederholungscodes sind einer der wenigen bekannten Codes, deren Coderate automatisch an unterschiedliche Kanalkapazitäten angepasst werden kann , indem mehr oder weniger Paritätsinformationen gesendet werden , um das Kanalrauschen zu überwinden, und es ist der einzige Code, der für nicht löschbare Kanäle bekannt ist . Praktische adaptive Codes für Löschkanäle wurden erst kürzlich erfunden und sind als Springbrunnencodes bekannt .

Einige UARTs , wie die im FlexRay- Protokoll verwendeten, verwenden einen Mehrheitsfilter, um kurze Rauschspitzen zu ignorieren. Dieses Spike-Rejection-Filter kann als eine Art Wiederholungsdecoder angesehen werden.

Verweise