Reed-Muller-code

Een Reed-Muller-code is een lineaire foutcorrigerende code, die gebruikt wordt bij draadloze communicatie, in het bijzonder in communicatie in de ruimte.^[1] Bovendien steunt 5G op de nauw verwante polaire codes.^[2]

Reed-Mullercodes zijn een generalisatie van Reed-Solomoncodes en Walsh-Hadamardcodes. Traditioneel gebruikt met Reed-Mullercodes als binaire codes, wat betekent dat de boodschappen en codewoorden binaire tekenreeksen zijn. De codes zijn vernoemd naar David E. Muller, een Amerikaanse wiskundige en computerwetenschapper, die de codes in 1954 ontdekte^[3] en naar Irving S. Reed, een Amerikaanse wiskundige, die het eerste efficiënte decodeeralgoritme voor de codes voorstelde.^[4]

Constructie

Er bestaan verschillende equivalente manieren om Reed-Mullercodes te beschrijven. Hier wordt gebruik gemaakt van de methode met generatormatrix. Een andere manier is via veeltermen. De generator-matrix van een Reed-Muller-code met lengte ${\displaystyle n=2^{d}}$wordt opgebouwd als volgt. Beschouw eerst de vectorruimte met dimensie d over het eindig lichaam ${\displaystyle \mathbb {F} _{2}=GF(2)}$. Deze vectorruimte bevat ${\displaystyle 2^{d}}$ elementen.

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

We definiëren nu in de n-dimensionale ruimte over ${\displaystyle \mathbb {F} _{2}}$ de 'indicator-vectoren':

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

op deelverzamelingen ${\displaystyle A\subset \mathbb {F} _{2}^{d}}$ door:

${\displaystyle \left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ als }}x_{i}\in A\\0&{\mbox{ elders}}\\\end{cases}}}$

en we definiëren in ${\displaystyle (\mathbb {F} _{2})^{n}}$ de volgende binaire bewerking 'puntproduct':

${\displaystyle w\wedge z=(w_{1}\times z_{1},\ldots ,w_{n}\times z_{n})}$

${\displaystyle \mathbb {F} _{2}^{d}}$ is een ${\displaystyle d}$-dimensionale vectorruimte over ${\displaystyle \mathbb {F} _{2}}$, en is dus te schrijven als

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

We definiëren nu de volgende vectoren ter lengte ${\displaystyle n:v_{0}=(1,1,1,1,1,1,1,1)}$ en

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

waarbij ${\displaystyle H_{i}}$ hypervlakken in ${\displaystyle (\mathbb {F} _{2})^{d}}$ zijn (van dimensie ${\displaystyle 2^{d}-1}$):

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

De Reed-Muller RM(d,r)-code van de orde ${\displaystyle r}$ en lengte ${\displaystyle n=2^{d}}$ is de lineaire code die wordt gegenereerd door ${\displaystyle v_{0}}$en de puntproducten tot en met ${\displaystyle r}$ van de vectoren ${\displaystyle v_{i},1\leq i\leq m}$.

Voorbeeld 1

Zij ${\displaystyle d=3}$. Dan is derhalve ${\displaystyle n=8}$ en

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

en

${\displaystyle {\begin{matrix}v_{0}&=&(1,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{matrix}}}$

De RM(3,1)-code wordt gegenereerd door de verzameling

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

of, meer expliciet geformuleerd, door de rijen van de matrix:

${\displaystyle {\begin{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}}}$

De dimensie van de code is 4, dus de code bestaat uit 16 codewoorden.

Voorbeeld 2

De RM(3,2)-code wordt gegenereerd door de verzameling

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

ofwel door de volgende matrix:

${\displaystyle {\begin{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\\1&0&1&0&0&0&0&0\\1&1&0&0&0&0&0&0\\\end{pmatrix}}}$

Eigenschappen

Volgende eigenschappen gelden voor Reed-Mullercodes:

1. De verzameling van alle mogelijke puntproducten tot en met ${\displaystyle d}$ van de vectoren ${\displaystyle v_{i}}$ vormt een basis van ${\displaystyle \mathbb {F} _{2}^{n}}$.
2. De RM(d,r)-code heeft dimensie ${\displaystyle \sum _{s=0}^{r}{d \choose s}}$.
3. Er geldt RM(d,r) = RM(d-1,r) | RM(d-1,r-1) waarbij '|' voor twee lineaire codes ${\displaystyle C_{2}\subset C_{1}}$ is gedefinieerd 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) heeft minimale Hammingafstand ${\displaystyle 2^{d-r}}$.

Bronnen, noten en/of referenties

1. (en) James L. Massey (september 1992). Advanced Methods for Satellite and Deep Space Communications. Proceedings of an International Seminar Organized by Deutsche Forschungsanstalt für Luft- und Raumfahrt (DLR) (Springer). DOI: 10.1007/BFb0036046. Geraadpleegd op 13 september 2019.
2. (en) Erdal Arikan (19 juni 2009). Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels. IEEE Transactions on Information Theory 55 (7): 3051–3073 (IEEE). ISSN: 0018-9448. DOI: 10.1109/TIT.2009.2021379. Geraadpleegd op 13 september 2019.
3. (en) David E. Muller (september 1954). Application of Boolean algebra to switching circuit design and to error detection. Transactions of the I.R.E. Professional Group on Electronic Computers EC-3 (3): 6-12 (IEEE). ISSN: 2168–1740. DOI: 10.1109/IREPGELC.1954.6499441. Geraadpleegd op 13 september 2019.
4. (en) Irving S. Reed (september 1954). A class of multiple-error-correcting codes and the decoding scheme. Transactions of the IRE Professional Group on Information Theory 4 (4): 38–49 (IEEE). ISSN: 2168-2690. DOI: 10.1109/TIT.1954.1057465. Geraadpleegd op 13 september 2019.