Lineaire code

Binnen de coderingstheorie is een lineaire code C een deelruimte van de vectorruimte V bestaande uit alle mogelijke woorden ter lengte n. Hierbij is V een vectorruimte over een eindig lichaam K, waarbij K de verzameling symbolen is die kunnen optreden als symbool binnen een codewoord. Algemeen: K = 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 voorgebracht 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 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 ontvangen woord vermenigvuldigd met H niet de nulvector oplevert, het ontvangen woord noodzakelijkerwijs geen codewoord kan zijn, en er dus 1 of meer bitfouten moeten zijn opgetreden.

Praktijkvoorbeelden

Enkele voorbeelden van daadwerkelijk gebruikte lineaire codes zijn: