Lineaire code

In de coderingstheorie is een lineaire code $C$ een lineaire deelruimte van een vectorruimte $V$ van dimensie $n$ over een eindig lichaam $K.$ De codes zijn alle mogelijke woorden van de lengte $n.$ Het lichaam $K$ is de verzameling symbolen die kunnen optreden binnen een codewoord. Algemeen: $K=\mathrm {GF} (p^{r}).$

Voorbeeld

n=7, p=2, r=1
V is een vectorruimte bestaande uit alle mogelijke symboolrijen ter lengte 7, met de symbolen 0 en 1. Dus V bestaat uit 2⁷ = 128 symboolrijen.

Een code C is een lineaire deelruimte van V; alle woorden die voorkomen in C noemen we codewoorden.

Omdat C een lineaire deelruimte is, kunnen we C beschrijven als een ruimte die wordt voortgebracht door een aantal basisvectoren b₁, b₂, .... Voor ieder codewoord c uit C geldt dat c een lineaire combinatie (met factoren 0 en 1) is van de basisvectoren. Een lineaire code bevat dus het codewoord dat uit allemaal nullen bestaat.

Een voorbeeld van een lineaire code C is de code voortgebracht door de basisvectoren die de rijen vormen van de volgende 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}}

De lineaire code C in dit voorbeeld heeft dimensie 3, en bestaat dus uit 8 codewoorden: de lineaire combinaties van de drie basisvectoren (inclusief het nulwoord). De acht codewoorden zijn dus de volgende:

{\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 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-k. 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, dan is op deze wijze foutdetectie mogelijk: een ontvangen woord wordt vermenigvuldigd met H; als het resultaat niet de nulvector is, dan moeten er 1 of meer bitfouten zijn opgetreden.

Praktijkvoorbeelden

Enkele voorbeelden van daadwerkelijk gebruikte lineaire codes zijn: