WikiDer > Reed-Müller Code

EIN Reed-Müller-Code ist ein linear Fehlerkorrektur Code, das in der drahtlosen Kommunikation, insbesondere in der Weltraumkommunikation, verwendet wird.^[1] Außerdem unterstützt 5G auf dem eng verwandten Polarcodes.^[2]

Reed-Müller-Codes sind eine Verallgemeinerung von Reed-Solomon-Codes und Walsh-Hadamard-Codes. Traditionell mit Reed-Muller-Codes als Binärcodes verwendet, d Saiten sein. Die Codes sind nach David E. Muller benannt, einem amerikanischen Mathematiker und Informatiker, der die Codes 1954 entdeckte^[3] und an Irving S. Reed, einen amerikanischen Mathematiker, der den ersten effizienten Decodieralgorithmus für die Codes vorschlug.^[4]

Konstruktion

Es gibt mehrere gleichwertige Möglichkeiten, Reed-Muller-Codes zu beschreiben. Hier wird das Generator-Matrix-Verfahren verwendet. Ein anderer Weg ist durch Polynome. Die Generatormatrix eines Reed-Muller-Codes mit Länge ${Anzeigestil n=2^{d}}$ist wie folgt aufgebaut. Betrachten Sie zuerst die Vektorraum mit Abmessungend über die endlicher Körper${displaystyle mathbb {F} _{2}=GF(2)}$. Dieser Vektorraum enthält ${Displaystil 2^{d}}$ Elemente.

${displaystyle mathbb {F} _{2}^{d}={x_{1},ldots ,x_{2^{d}}}}$

Wir definieren nun im n-dimensionalen Raum über ${displaystyle mathbb {F}_{2}}$ die 'Indikatorvektoren':

${displaystyle mathbb {I} _{A}in mathbb {F} _{2}^{n}}$

auf Teilmengen ${displaystyle Asubset mathbb {F} _{2}^{d}}$ durch:

${displaystyle left(mathbb {I} _{A}ight)_{i}={ egin{cases}1&{mbox{ as }}x_{i}in A/0&{mbox{other}}/end{cases} }}$

und wir definieren in ${displaystyle (mathbb {F} _{2})^{n}}$ die folgende binäre Operation 'Punktprodukt':

${displaystyle wwedge z=(w_{1}imes z_{1},ldots ,w_{n}imes z_{n})}$

${displaystyle mathbb {F} _{2}^{d}}$ ist ein ${displaystyle d}$-dimensionaler Vektorraum über ${displaystyle mathbb {F}_{2}}$, und kann daher geschrieben werden als

${displaystyle (mathbb {F} _{2})^{d}={(y_{1},ldots ,y_{d})|y_{i}in mathbb {F} _{2}}}$

Wir definieren nun die folgenden Vektoren der Länge ${displaystyle n:v_{0}=(1,1,1,1,1,1,1,1,1)}$ und

${displaystyle v_{i}=mathbb {I} _{H_{i}}}$

bei welchem ${displaystyle H_{i}}$ Hyperebenen in ${displaystyle (mathbb {F} _{2})^{d}}$ sein (von der Dimension) ${Displaystil 2^{d}-1}$):

${displaystyle H_{i}={yin (mathbb {F} _{2})^{d}mid y_{i}=0}}$

Das Reed-Müller RM(d,r)-Code der Ordnung ${displaystyle r}$ und Länge ${Anzeigestil n=2^{d}}$ ist der linearer Code die erzeugt wird von ${displaystyle v_{0}}$und die Punktprodukte bis ${displaystyle r}$ der Vektoren ${displaystyle v_{i},1leq ileq m}$.

Beispiel 1

Sie ${Anzeigestil d=3}$. Dann also ${Anzeigestil n=8}$ und

${displaystyle mathbb {F} _{2}^{3}={(0,0,0),(0,0,1),ldots ,(1,1,1)}}$,

und

${displaystyle { egin{matrix}v_{0}&=&(1,1,1,1,1,1,1)/v_{1}&=&(1,0,1,0,1, 0,1,0)/v_{2}&=&(1,1,0,0,1,1,0,0)/v_{3}&=&(1,1,1,1,0, 0,0,0)./end{array}}}$

Der RM(3,1)-Code wird von der Menge erzeugt

${displaystyle {v_{0},v_{1},v_{2},v_{3}}}$

oder, genauer gesagt, durch die Zeilen der Matrix:

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

Die Dimension des Codes ist 4, der Code besteht also aus 16 Codewörtern.

Beispiel 2

Der RM(3,2)-Code wird von der Menge erzeugt

${displaystyle {v_{0},v_{1},v_{2},v_{3},v_{1}Keil v_{2},v_{1}Keil v_{3},v_{2}Keil v_{ 3}}}$

entweder durch die folgende Matrix:

${displaystyle { egin{pmatrix}1&1&1&1&1&1&1&1/1&0&1&0&1&0&1&0/1&1&0&0&1&1&0&0/1&1&1&1&0&0&0&0/1&0&0&0&1&0&0&0&0/1&0}&0}&0$

Eigenschaften

Die folgenden Eigenschaften gelten für Reed-Müller-Codes:

1. Die Menge aller möglichen Punktprodukte bis ${displaystyle d}$ der Vektoren ${displaystyle v_{i}}$ bildet eine Grundlage für ${displaystyle mathbb {F} _{2}^{n}}$.
2. Der RM(d,r)-Code hat Abmessungen${Anzeigestilsumme _{s=0}^{r}{d wähle s}}$.
3. RM(d,r) = RM(d-1,r) | RM(d-1,r-1) wobei '|' für zwei lineare Codes${Displaystil C_{2}Teilmenge C_{1}}$ ist definiert als ${displaystyle C_{1}|C_{2}={(c_{1}|c_{1} c_{2})mid c_{1}in C_{1},c_{2}in C_{2}}}$.
4. RM(d,r) hat ein Minimum Hamming-Abstand${Displaystil 2^{d-r}}$.