Lineaire code

In de coderingstheorie is een lineaire code een foutcorrigerende blokcode waarvoor geldt dat elke lineaire combinatie van de codewoorden ook een codewoord is. Wiskundig kan de code omschreven worden als een lineaire deelruimte $C$ van een vectorruimte $V$ van eindige dimensie $n$ over een eindig lichaam/veld $K=\mathrm {GF} (p^{r})$, met $p$ een priemgetal. De elementen van $K$ zijn de symbolen waarmee een codewoord wordt gevormd.

Lineaire codes worden gebruikt in voorwaartse foutcorrectie en worden toegepast om symbolen zoals bits over een communicatiekanaal te versturen, zodat als er een fout optreedt in het communicatiekanaal, sommige fouten door de ontvanger kunnen worden gedetecteerd en eventueel hersteld. Een lineaire code is een blokcode met woordlengte $n$, met als extra eigenschap dat het een lineaire deelruimte is.

Voorbeeld

De verzameling die bestaat uit de rijtjes van 7 symbolen 0 of 1, kan opgevat worden als vectorruimte $V$ van dimensie 7 over het lichaam $K=\mathrm {GF} (2)$, dat bestaat uit alleen de symbolen 0 en 1. De vectorruimte bestaat uit $2^{7}=128$ woorden.

De lineaire deelruimte $C$ voortgebracht door de lineair onafhankelijke rijen van de onderstaande matrix:

${\begin{bmatrix}1&0&0&0&0&1&1\\0&1&0&1&1&0&0\\0&1&1&0&0&0&1\end{bmatrix}}$

is een lineaire code van dimensie 3 over $K$. De code bestaat uit 8 codewoorden: de lineaire combinaties van de drie basisvectoren, inclusief het nulwoord 0000000. De acht codewoorden zijn dus de volgende rijen:

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

Generatormatrix en parity check matrix

De matrix die een lineaire code voortbrengt, wordt de generatormatrix $G$ genoemd. Een $k$-dimensionale lineaire code met woordlengte $n$ over $\mathrm {GF} (2)$, heeft een generatormatrix met $k$ rijen en $n$ kolommen. Iedere rij is een codewoord, dat van de overige rijen lineair onafhankelijk is. Een dergelijke code bestaat uit $2^{k}$ codewoorden. De paritycheckmatrix $H$ heeft $n$ kolommen en $n$ rijen. De rijen van $H$ zijn woorden die loodrecht staan op alle rijen van $G$, dus op alle codewoorden. Voor ieder codewoord $c$ geldt dus dat de vermenigvuldiging $Hc$ de nulvector oplevert.

Omgekeerd geldt ook dat als een willekeurig woord uit de vectorruimte vermenigvuldigd met $H$ niet de nulvector oplevert, dit woord geen codewoord kan zijn. Als de code wordt gebruikt voor het verzenden of de opslag van gegevens, is op deze wijze foutdetectie mogelijk: een ontvangen woord wordt vermenigvuldigd met $H$ en als het resultaat niet de nulvector is, moeten er een of meer bitfouten zijn opgetreden.

Praktijkvoorbeelden

Voorbeelden van lineaire codes zijn:

• Hamming-code
• Reed-Muller-code

Websites

• MathWorld. Linear Code.