WikiDer > Linearer Code

In dem Codierungstheorie ist ein linearer Code eine Fehlerkorrektur Blockcode wofür jedes Geldt lineare Kombination der Codewörter ist auch ein Codewort. Mathematisch kann der Code wie folgt beschrieben werden: linearer Unterraum${Anzeigestil C}$ von a Vektorraum${Anzeigestil V}$ endlicher Dimension ${displaystyle n}$ über einen endlicher Körper${displaystyle K=mathrm {GF} (p^{r})}$. Die Elemente von ${Anzeigestil K}$ sind die Symbole, die verwendet werden, um ein Codewort zu bilden.

Lineare Codes werden bei der Vorwärtsfehlerkorrektur verwendet und auf Symbole angewendet (wie z Bits) über a . senden Kommunikationskanal, so dass bei einem Fehler im Kommunikationskanal einige Fehler vom Empfänger erkannt oder behoben werden können. Ein linearer Code ist ein Blockcode mit Wortlänge ${displaystyle n,}$ mit der zusätzlichen Eigenschaft, dass es sich um einen linearen Unterraum handelt.

Beispiel

Der Vektorraum ${Anzeigestil V}$ ist von Dimension ${Anzeigestil n=7}$ über einen Körper ${displaystyle K=mathrm {GF} (2)}$, die nur aus den Symbolen 0 und 1 besteht. Es gibt also ${Displaystil 2^{7}=128}$ mögliche Codewörter, Reihen von 7 Symbolen 0 und 1.

Der lineare Unterraum ${Anzeigestil C}$ erzeugt durch die linear unabhängigen Zeilen der folgenden Matrix:

${displaystyle { egin{bmatrix}1&0&0&0&0&1&1/0&1&0&1&1&0&0/0&1&1&0&0&0&1end{bmatrix}}}$

ist ein linearer Code mit Dimension 3 über ${Anzeigestil K}$. Der Code besteht aus 8 Codewörtern: die Linearkombinationen der drei Basisvektoren, einschließlich des Nullworts 0000000. Die acht Codewörter sind also die folgenden Zeilen:

${displaystyle { egin{bmatrix}0&0&0&0&0&0&0/1&0&0&0&0&1&1/0&1&0&1&1&0&0/0&1&1&0&0&0&1/1&1&0&1&1&1&1/1&1&1&1&0&0&&1&&0/1}&0b/1}$

Generatormatrix und Paritätsprüfmatrix

Die Matrix mit einem linearen Code produziert, wird zur Generatormatrix ${Anzeigestil G}$ erwähnt. EIN ${displaystyle k}$-dimensionaler linearer Code mit Wortlänge ${displaystyle n}$ Über ${displaystyle mathrm{GF}(2)}$, hat eine Generatormatrix mit Höhe ${displaystyle k}$ (jede Reihe ist eine der verbleibenden Reihen linear unabhängig Codewort) und Breite ${Anzeigestil n;}$ solcher Code besteht aus ${Displaystil 2^{k}}$ Codewörter. Die sogenannte Paritätsprüfmatrix ${Anzeigestil H}$ hat Breite ${displaystyle n}$ und Höhe ${displaystyle n}$ Die Reihen von ${Anzeigestil H}$ sind Wörter, die senkrecht zu allen Reihen von stehen ${Anzeigestil G,}$ und so weiter alle Codewörter. Für jedes Codewort ${Anzeigestil c}$ also die Multiplikation ${displaystyle Hc}$ das Nullvektor ergibt.

Umgekehrt, wenn ein Wort aus dem Vektorraum mit multipliziert wird ${Anzeigestil H}$ nicht den Nullvektor liefert, kann dieses beliebige Wort nicht unbedingt ein Codewort sein. Wenn der Code also zum Transport oder zur Speicherung von Informationen verwendet wird, ist eine Fehlererkennung auf diese Weise möglich: Ein empfangenes Wort wird mit ${Anzeigestil H;}$ ist das Ergebnis nicht der Nullvektor, müssen 1 oder mehrere Bitfehler aufgetreten sein.

Praxisbeispiele

Einige Beispiele für tatsächlich verwendete lineare Codes sind:

• Hamming-Code
• Reed-Müller-Code