Dekodierungsmethoden - Decoding methods

In der Codierungstheorie ist Decodierung der Prozess des Übersetzens empfangener Nachrichten in Codewörter eines bestimmten Codes . Es gibt viele gängige Methoden zum Zuordnen von Nachrichten zu Codewörtern. Diese werden häufig verwendet, um Nachrichten wiederherzustellen, die über einen verrauschten Kanal gesendet wurden , z. B. einen binären symmetrischen Kanal .

Notation

${\ displaystyle C \ subset \ mathbb {F} _ {2} ^ {n}}$ wird als Binärcode mit der Länge betrachtet ; soll Elemente sein von ; und ist der Abstand zwischen diesen Elementen. ${\ displaystyle n}$ ${\ displaystyle x, y}$ ${\ displaystyle \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle d (x, y)}$

Ideale Beobachterdecodierung

Man kann die Nachricht erhalten , dann erzeugt die ideale Beobachterdecodierung das Codewort . Der Prozess führt zu dieser Lösung: ${\ displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle y \ in C}$

{\ displaystyle \ mathbb {P} (y {\ mbox {gesendet}} \ mid x {\ mbox {empfangen}})}

Beispielsweise kann eine Person das Codewort auswählen, das am wahrscheinlichsten nach der Übertragung als Nachricht empfangen wird. ${\ displaystyle y}$ ${\ displaystyle x}$

Dekodierungskonventionen

Jedes Codewort hat keine erwartete Möglichkeit: Es kann mehr als ein Codewort mit der gleichen Wahrscheinlichkeit geben, in die empfangene Nachricht zu mutieren. In einem solchen Fall müssen sich Sender und Empfänger vorab auf eine Dekodierungskonvention einigen. Beliebte Konventionen umfassen:

Fordern Sie an, dass das Codewort erneut gesendet wird - automatische Wiederholungsanforderung .
Wählen Sie ein beliebiges zufälliges Codewort aus der Menge der wahrscheinlichsten Codewörter, die näher daran liegen.
Wenn ein anderer Code folgt , markieren Sie die mehrdeutigen Bits des Codeworts als Löschungen und hoffen Sie, dass der äußere Code sie eindeutig macht

Dekodierung mit maximaler Wahrscheinlichkeit

Einen Empfangsvektor gegebene Maximum - Likelihood - Decodieren wählt eine Codewort , dass maximieren ${\ displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle y \ in C}$

{\ displaystyle \ mathbb {P} (x {\ mbox {empfangen}} \ mid y {\ mbox {gesendet}})}

,

Das heißt, das Codewort , das die Wahrscheinlichkeit maximiert, dass es empfangen wurde, vorausgesetzt, es wurde gesendet. Wenn alle Codewörter gleich wahrscheinlich gesendet werden, entspricht dieses Schema der idealen Beobachterdecodierung. In der Tat, nach dem Bayes-Theorem , ${\ displaystyle y}$ ${\ displaystyle x}$ ${\ displaystyle y}$

{\ displaystyle {\ begin {align} \ mathbb {P} (x {\ mbox {empfangen}} \ mid y {\ mbox {gesendet}}) & {} = {\ frac {\ mathbb {P} (x { \ mbox {empfangen}}, y {\ mbox {gesendet}})} {\ mathbb {P} (y {\ mbox {gesendet}})}} \\ & {} = \ mathbb {P} (y {\ mbox {gesendet}} \ mid x {\ mbox {empfangen}}) \ cdot {\ frac {\ mathbb {P} (x {\ mbox {empfangen}})} {\ mathbb {P} (y {\ mbox { gesendet}})}}. \ end {align}}}

Bei der Fixierung , restrukturiert und ist konstant , da alle Codewörter gleich wahrscheinlich gesendet werden. Daher wird als Funktion der Variablen genau dann maximiert, wenn maximiert wird, und der Anspruch folgt. ${\ displaystyle \ mathbb {P} (x {\ mbox {empfangen}})}$ ${\ displaystyle x}$ ${\ displaystyle \ mathbb {P} (y {\ mbox {sent}})}$ ${\ displaystyle \ mathbb {P} (x {\ mbox {empfangen}} \ mid y {\ mbox {gesendet}})}$ ${\ displaystyle y}$ ${\ displaystyle \ mathbb {P} (y {\ mbox {gesendet}} \ mid x {\ mbox {empfangen}})}$

Wie bei der idealen Beobachterdecodierung muss eine Konvention für die nicht eindeutige Decodierung vereinbart werden.

Das Maximum-Likelihood-Decodierungsproblem kann auch als ganzzahliges Programmierproblem modelliert werden .

Der Maximum-Likelihood-Decodierungsalgorithmus ist eine Instanz des Problems "Marginalisieren einer Produktfunktion", das durch Anwendung des verallgemeinerten Verteilungsgesetzes gelöst wird .

Minimale Entfernungsdecodierung

Bei einem empfangenen Codewort , Mindestabstand Dekodieren nimmt ein Codewort die minimieren Hammingdistanz : ${\ displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle y \ in C}$

{\ displaystyle d (x, y) = \ # \ {i: x_ {i} \ not = y_ {i} \}}

dh wählen Sie das Codewort , das so nah wie möglich ist . ${\ displaystyle y}$ ${\ displaystyle x}$

Es ist zu beachten, dass, wenn die Fehlerwahrscheinlichkeit auf einem diskreten speicherlosen Kanal streng weniger als die Hälfte beträgt , die minimale Entfernungsdecodierung der maximalen Wahrscheinlichkeitsdecodierung entspricht , da wenn ${\ displaystyle p}$

{\ displaystyle d (x, y) = d, \,}

dann:

{\ displaystyle {\ begin {align} \ mathbb {P} (y {\ mbox {empfangen}} \ mid x {\ mbox {gesendet}}) & {} = (1-p) ^ {nd} \ cdot p ^ {d} \\ & {} = (1-p) ^ {n} \ cdot \ left ({\ frac {p} {1-p}} \ right) ^ {d} \\\ end {align} }}

was (da p kleiner als die Hälfte ist) durch Minimieren von d maximiert wird .

Die Dekodierung der Mindestentfernung wird auch als Dekodierung des nächsten Nachbarn bezeichnet . Es kann mithilfe eines Standardarrays unterstützt oder automatisiert werden . Die Mindestabstandsdecodierung ist eine sinnvolle Decodierungsmethode, wenn die folgenden Bedingungen erfüllt sind:

Die Wahrscheinlichkeit, dass ein Fehler auftritt, ist unabhängig von der Position des Symbols. ${\ displaystyle p}$
Fehler sind unabhängige Ereignisse - ein Fehler an einer Position in der Nachricht wirkt sich nicht auf andere Positionen aus.

Diese Annahmen können für Übertragungen über einen binären symmetrischen Kanal sinnvoll sein . Sie können für andere Medien, z. B. eine DVD, unangemessen sein, bei denen ein einzelner Kratzer auf der Festplatte einen Fehler in vielen benachbarten Symbolen oder Codewörtern verursachen kann.

Wie bei anderen Decodierungsmethoden muss eine Konvention für die nicht eindeutige Decodierung vereinbart werden.

Syndrom-Dekodierung

Die Syndromdecodierung ist eine hocheffiziente Methode zum Decodieren eines linearen Codes über einen verrauschten Kanal , dh einen, auf dem Fehler gemacht werden. Im Wesentlichen ist die Syndromdecodierung eine Mindestabstandsdecodierung unter Verwendung einer reduzierten Nachschlagetabelle. Dies wird durch die Linearität des Codes ermöglicht.

Angenommen, dies ist ein linearer Code für Länge und Mindestabstand mit Paritätsprüfungsmatrix . Dann ist klar in der Lage, bis zu zu korrigieren ${\ displaystyle C \ subset \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle n}$ ${\ displaystyle d}$ ${\ displaystyle H}$ ${\ displaystyle C}$

{\ displaystyle t = \ left \ lfloor {\ frac {d-1} {2}} \ right \ rfloor}

Fehler, die vom Kanal gemacht wurden (da, wenn nicht mehr als Fehler gemacht werden, die minimale Entfernungsdecodierung das falsch übertragene Codewort immer noch korrekt decodiert). ${\ displaystyle t}$

Angenommen, ein Codewort wird über den Kanal gesendet und das Fehlermuster tritt auf. Dann wird empfangen. Eine gewöhnliche Mindestabstandsdecodierung würde den Vektor in einer Größentabelle nach der nächsten Übereinstimmung suchen - dh nach einem Element (nicht unbedingt eindeutig) mit ${\ displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle e \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle z = x + e}$ ${\ displaystyle z}$ ${\ displaystyle | C |}$ ${\ displaystyle c \ in C}$

{\ displaystyle d (c, z) \ leq d (y, z)}

für alle . Die Syndromdecodierung nutzt die Eigenschaft der Paritätsmatrix, dass: ${\ displaystyle y \ in C}$

{\ displaystyle Hx = 0}

für alle . Das Syndrom des Empfangenen ist definiert als: ${\ displaystyle x \ in C}$ ${\ displaystyle z = x + e}$

{\ displaystyle Hz = H (x + e) ​​= Hx + He = 0 + He = He}

Zur Durchführung ML - Decodierung in einem binären symmetrischen Kanal , muss man Nachschau eine vorberechnete Tabelle der Größe , mapping zu . ${\ displaystyle 2 ^ {nk}}$ ${\ displaystyle He}$ ${\ displaystyle e}$

Beachten Sie, dass dies bereits wesentlich weniger komplex ist als das einer Standard-Array-Decodierung .

Unter der Annahme, dass während der Übertragung nicht mehr als Fehler gemacht wurden, kann der Empfänger den Wert jedoch in einer weiter reduzierten Größentabelle nachschlagen ${\ displaystyle t}$ ${\ displaystyle He}$

{\ displaystyle {\ begin {matrix} \ sum _ {i = 0} ^ {t} {\ binom {n} {i}} \\\ end {matrix}}}

Listendecodierung

Dekodierung von Informationssätzen

Dies ist eine Familie von Las Vegas- wahrscheinlichen Methoden, die alle auf der Beobachtung beruhen, dass es einfacher ist, genügend fehlerfreie Positionen zu erraten, als alle Fehlerpositionen zu erraten.

Die einfachste Form ist Prange: Sei die Generatormatrix, die für die Codierung verwendet wird. Wählen Sie Spalten von zufällig aus und bezeichnen Sie sie mit der entsprechenden Submatrix von . Mit hinreichender Wahrscheinlichkeit wird vollen Rang hat, was bedeutet , dass , wenn wir lassen der Untervektor für die entsprechenden Positionen von jedem Codewort sein von einer Nachricht können wir erholen wie . Wenn wir also das Glück hatten, dass diese Positionen des empfangenen Wortes keine Fehler enthielten und daher den Positionen des gesendeten Codeworts entsprachen, können wir dekodieren. ${\ displaystyle G}$ ${\ displaystyle k \ times n}$ ${\ displaystyle C}$ ${\ displaystyle k}$ ${\ displaystyle G}$ ${\ displaystyle G '}$ ${\ displaystyle G}$ ${\ displaystyle G '}$ ${\ displaystyle c '}$ ${\ displaystyle c = mG}$ ${\ displaystyle C}$ ${\ displaystyle m}$ ${\ displaystyle m}$ ${\ displaystyle m = c'G '^ {- 1}}$ ${\ displaystyle k}$ ${\ displaystyle y}$

Wenn Fehler aufgetreten sind, ist die Wahrscheinlichkeit einer solchen glücklichen Auswahl von Spalten gegeben durch . ${\ displaystyle t}$ ${\ displaystyle \ textstyle {\ binom {nt} {k}} / {\ binom {n} {k}}}$

Diese Methode wurde auf verschiedene Weise verbessert, z. B. von Stern und Canteaut und Sendrier.

Teilantwort maximale Wahrscheinlichkeit

Partial Response Maximum Likelihood ( PRML ) ist ein Verfahren zum Umwandeln des schwachen analogen Signals vom Kopf einer Magnetplatte oder eines Bandlaufwerks in ein digitales Signal.

Viterbi-Decoder

Ein Viterbi-Decoder verwendet den Viterbi-Algorithmus zum Decodieren eines Bitstroms, der unter Verwendung einer Vorwärtsfehlerkorrektur basierend auf einem Faltungscode codiert wurde . Die Hamming-Distanz wird als Metrik für Viterbi-Decoder mit schwerer Entscheidung verwendet. Der quadratische euklidische Abstand wird als Metrik für Decoder mit weichen Entscheidungen verwendet.

Siehe auch

Verweise

Weiterführende Literatur

Hill, Raymond (1986). Ein erster Kurs in Codierungstheorie . Oxford Angewandte Mathematik und Informatik. Oxford University Press . ISBN 978-0-19-853803-5 .
Pless, Vera (1982). Einführung in die Theorie der Fehlerkorrekturcodes . Wiley-Interscience-Reihe in diskreter Mathematik. John Wiley & Sons . ISBN 978-0-471-08684-0 .
van Lint, Jacobus H. (1992). Einführung in die Codierungstheorie . Diplomtexte in Mathematik (GTM). 86 (2. Aufl.). Springer-Verlag . ISBN 978-3-540-54894-2 .

Languages

In other projects