Lineaire code

In de coderingstheorie is een lineaire code een lineaire deelruimte $C$ van een vectorruimte $V$ van eindige dimensie $n$ over een eindig lichaam $K$ . De elementen van $K$ zijn de symbolen waarmee een codewoord gevormd wordt. Een lineaire code is een blokcode met woordlengte $n,$ met als extra eigenschap dat het een lineaire deelruimte is. Algemeen: $K=\mathrm {GF} (p^{r})$ .

Voorbeeld

De vectorruimte $V$ is van dimensie $n=7$ over een het lichaam $K=\mathrm {GF} (2)$ , dat bestaat uit alleen de symbolen 0 en 1. Er zijn dus $2^{7}=128$ mogelijke codewoorden, rijtjes van 7 symbolen 0 en 1.

De lineaire deelruimte $C$ voortgebracht door de onderling 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 met 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 generator-matrix $G$ genoemd. Een $k$ -dimensionale lineaire code met woordlengte $n$ over $\mathrm {GF} (2)$ , heeft een generatormatrix met hoogte $k$ (iedere rij is een van de overige rijen lineair onafhankelijk codewoord) en breedte $n;$ een dergelijke code bestaat uit $2^{k}$ codewoorden. De zogenaamde parity check matrix $H$ heeft breedte $n$ en hoogte $n$ De rijen van $H$ zijn woorden die loodrecht staan op alle rijen van $G,$ en 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 willekeurige woord noodzakelijkerwijs geen codewoord kan zijn. Als de code dus wordt gebruikt voor transport of opslag van informatie, is op deze wijze foutdetectie mogelijk: een ontvangen woord wordt vermenigvuldigd met $H;$ als het resultaat niet de nulvector is, moeten er 1 of meer bitfouten zijn opgetreden.

Praktijkvoorbeelden

Enkele voorbeelden van daadwerkelijk gebruikte lineaire codes zijn: