Blokcode

In de coderingstheorie is een blokcode een foutcorrigerende code met als belangrijkste kenmerk dat de gegevens in blokken met een vaste lengte worden verdeeld, waarna elk blok gecodeerd wordt. Blokcodes nemen een belangrijke plaats in binnen de kanaalcodering en als onderdeel daarvan binnen de foutcorrigerende codes. Blokcodes worden als abstract concept bestudeerd. Daarmee is het bijvoorbeeld mogelijk gemeenschappelijke kenmerken vast te stellen, zoals grenzen aan het maximale aantal fouten dat gedetecteerd of hersteld kan worden.

Er zijn allerlei soorten blokcodes met veel praktische toepassingen. Enkele voorbeelden van blokcodes zijn Reed-Solomoncodes, Hammingcodes en Reed-Mullercodes. Deze codes zijn bovendien lineair.

Bij alle foutcorrigerende codes wordt een blok met een vast aantal ingevoerde bits in een ander blok, ook met een vast aantal bits, omgezet. Er worden daarbij een of meer pariteitsbits toegevoegd die de correctie naderhand mogelijk maken. Dat zorgt dus voor een vorm van redundantie.

Soms wordt iedere foutcorrigerende code een blokcode genoemd. Met deze definitie zijn bijvoorbeeld turbocodes ook te rekenen tot de blokcodes. Dit artikel behandelt de algebraïsche blokcodes, dat wil zeggen blokcodes waarbij blokken gegevens onafhankelijk van elkaar gecodeerd worden, wat niet het geval is bij turbocodes.

Werking

Bij gegevenstransmissie over een communicatiekanaal stuurt de afzender gegevens naar de ontvanger. Elk communicatiekanaal heeft echter last van ruis, waardoor de transmissie niet foutloos verloopt. Bij een blokcode worden de te verzenden gegevens opgesplitst in binaire blokken of boodschappen van vaste lengte $k$. Elk blok wordt vervolgens onafhankelijk van andere blokken omgezet (gecodeerd) naar een codewoord, een blok van vaste lengte $n$. Bij deze omzetting worden extra bits toegevoegd aan elk blok met het doel het daarmee mogelijk te maken fouten te detecteren en te corrigeren. Een eenvoudig voorbeeld is het toevoegen van een pariteitsbit aan ieder blok.

Bij de ontvanger gebeurt het omgekeerde: de ontvangen codewoorden, waarin mogelijk een of meer fouten zitten, worden zo goed mogelijk gedecodeerd, teneinde de inhoud van het originele blok terug te vinden.

Formele beschrijving en parameters

Een blokcode is wiskundig gezien een injectie $C\colon \Sigma ^{k}\to \Sigma ^{n}$. Hierbij is $\Sigma$ een eindige, niet-lege verzameling en zijn $k$ en $n$ gehele getallen. De verschillende parameters voor blokcodes worden hieronder uitgelegd.

Het alfabet Σ

De gegevens die codering moeten ondergaan, worden gemodelleerd als een tekenreeks van tekens uit een alfabet $\Sigma$. De grootte van het alfabet $|\Sigma |$ wordt wel genoteerd als $q$. Als $q=2$, spreekt men van een binaire blokcode. In veel toepassingen is het wenselijk dat $q$ een macht van een priemgetal is, waardoor $\Sigma$ beschouwd kan worden als het eindige veld / lichaam $\mathbb {F} _{q}$.

De boodschaplengte k

Elke boodschap $m$ is een element van $\Sigma ^{k}$, dat wil zeggen een tekenreeks bestaande uit symbolen uit $\Sigma$ van lengte $k$. Het getal $k$ wordt de informatielengte, boodschaplengte of dimensie van de blokcode genoemd.

De bloklengte n

De bloklengte $n$ is het aantal symbolen in een codewoord. De elementen $c$ van $\Sigma ^{n}$ zijn dus tekenreeksen van lengte $n$ en komen overeen met een blok dat ontvangen kan worden door de ontvanger. Daarom worden ze ook wel ontvangen woorden genoemd. Het resultaat van de codering van een boodschap $m$ is het codewoord $c$ van die boodschap. In formule: $c=C(m)$.

Het datadebiet R

Het datadebiet (Eng. rate) van een blokcode wordt gedefinieerd als de verhouding tussen de boodschaplengte en de bloklengte: $R=k/n$.

Een hoog debiet betekent dat een groot deel van het codewoord bestaat uit de boodschap. In deze zin meet het debiet de transmissiesnelheid, en geeft $1-R$ de overhead aan die optreedt doordat de resulterende codewoorden langer zijn dan de boodschap. Uit de informatietheorie volgt dat het debiet nooit groter kan zijn dan $1$, aangezien gegevens in het algemeen niet gecomprimeerd kunnen worden zonder dat daarbij informatie verloren gaat.

De afstand d en het gewicht w

De (minimum)afstand $d$ van een blokcode is het minimaal aantal posities die verschillend zijn tussen elke twee codewoorden; de relatieve afstand $\delta$ is de verhouding $d/n$. Als $\Delta (c_{1},c_{2})$ de Hammingafstand tussen de twee codewoorden $c_{1},c_{2}\in \Sigma ^{n}$ is, zal de minimumafstand $d$ van de code $C$ gegeven worden door:

$d=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]$

Elk codewoord zal in minstens één positie verschillen van alle andere codewoorden, dus $d\geq 1$.

Het gewicht $w$ van een codewoord is het aantal posities die niet gelijk zijn aan nul. Het minimumgewicht $w_{\min }$ is het kleinste gewicht van alle codewoorden, of ook het gewicht van het codewoord met het minste aantal nullen. Voor lineaire blokcodes geldt dat de minimumafstand gelijk is aan het minimumgewicht:

$\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [\mathbf {0} ,C(m_{1})+C(m_{2})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }$

Een grotere afstand laat meer foutdetectie en foutcorrectie toe. Beschouw bijvoorbeeld alleen fouten die symbolen van de codewoorden wijzigen, maar er nooit een wissen of toevoegen; de codewoorden blijven dus altijd even lang. Dan is het aantal fouten gelijk aan het aantal posities waarin het verzonden en het ontvangen codewoord verschillen. Een code met afstand $d$ maakt het mogelijk om $d-1$ fouten te detecteren, aangezien het wijzigen van $d-1$ posities nooit leidt tot een ander codewoord. Als er bovendien niet meer dan $(d-1)/2$ fouten optreden tijdens de transmissie, kan de ontvanger het codewoord uniek decoderen. Dit omdat voor elk ontvangen woord er op afstand $(d-1)/2$ hoogstens één codewoord is. Als er meer fouten optreden, kan de ontvanger het ontvangen woord niet uniek decoderen, aangezien er dan meer verschillende codewoorden kunnen overeenkomen.

Notatie

De notatie $(n,k,d)_{q}$ beschrijft een blokcode over een alfabet $\Sigma$ van grootte $q$, met een bloklengte $n$, boodschaplengte $m$ en afstand $d$. Als de blokcode lineair is, kunnen blokhaken gebruikt worden om dit aan te geven: $[n,k,d]_{q}$. Zowel $q$ als $d$ worden nogal eens weggelaten: als het gaat om een binaire code is vanzelfsprekend $q=2$, en de $d$ laat men wel wewg als de afstand niet belangrijk is, niet bekend is of moeilijk te bepalen.

Voorbeelden

De meeste foutcorrigerende codes zijn blokcodes.

• De eerste foutcorrigerende code was de (7,4)-Hammingcode, ontwikkeld door Richard Hamming in 1950. Deze code transformeert een informatieblok van 4 bits in een codewoord van 7 bits door 3 pariteitsbits toe te voegen. Dit is ook een lineaire code, met afstand 3. In de notatie van hierboven zouden we de (7,4)-Hammingcode dus noteren als een $[7,4,3]_{2}$-code.

• Reed-Solomoncodes zijn $[n,k,d]_{q}$-codes, waarbij $d=n-k+1$ en $q$ een priemmacht is.
• Rankcodes zijn <mat$[n,k,d]_{2}$-codes, met $n=2^{k-1}$ en $d=2^{k-2}$.

Foutdetectie en foutcorrectie

Een codewoord $c\in \Sigma ^{n}$ kan beschouwd worden als een punt in een $n$-dimensionale ruimte $\Sigma ^{n}$; de code $C$ is een deelverzameling van $\Sigma ^{n}$. Een code $C$ met afstand $d$ betekent dat voor iedere $c\in C$ geldt dat de Hammingbal gecentreerd op het punt $c$ met straal $d-1$ leeg is. De Hammingbal betekent hier de verzameling van $n$-dimensionale woorden waarvan de Hammingafstand tot $c$ maximaal $d-1$ is. Equivalent heeft een code $C$ met afstand $d$ de eigenschappen:

• $C$ kan $d-1$ fouten detecteren. Omdat een codewoord $c$ het enige codewoord is in de Hammingbal gecentreerd op zichzelf met straal $d-1$ is, kan een foutpatroon met $d-1$ fouten of minder nooit een codewoord omzetten in een ander codewoord. Als de ontvanger een ontvangen woord krijgt dat niet overeenkomt met een codewoord van $C$, worden de fouten gedetecteerd (maar er zijn geen garanties over correctie van fouten, m.a.w. de ontvanger weet dat het ontvangen woord fout is, maar weet niet wat het verstuurde codewoord is).
• $C$ kan $\left\lfloor (d-1)/2\right\rfloor$ fouten corrigeren. Omdat een codewoord $c$ het enige codewoord is in de Hammingbal gecentreerd op zichzelf met straal $d-1$ is, kunnen de Hammingballen gecentreerd op twee andere codewoorden met straal $\left\lfloor (d-1)/2\right\rfloor$ nooit overlappen met elkaar. Een fout kan dan gecorrigeerd worden door het dichtstbijzijnde codewoord voor het ontvangen woord $y$ te zoeken, zolang het aantal fouten minder dan $\left\lfloor (d-1)/2\right\rfloor$ is: er is dan maar één codewoord in de Hammingbal gecentreerd op $y$ met straal $\left\lfloor (d-1)/2\right\rfloor$.
• Om te decoderen bij meer dan $(d-1)/2$ fouten, kan met gebruik maken van list decoding of maximum likelihood decoding.
• $C$ kan $d-1$ ontbrekende symbolen corrigeren. Hierbij moet opgemerkt worden dat de positie van het verdwenen symbool gekend dient te zijn.

Literatuur

• (en) van Lint, Jack H. (1999). Introduction to Coding Theory, 3e editie. Springer-Verlag. DOI:10.1007/978-3-642-58575-3, p. 33. ISBN 978-3-540-64133-9.
• (en) MacWilliams, Florence J., Sloane, Neil J. A. (1893). The Theory of Error-Correcting Codes. North Holland, p. 35. ISBN 9780444851932. Gearchiveerd op 20 juni 2022.
• (en) Berrou, Claude (2010). Codes and Turbo Codes. Springer-Verlag. DOI:10.1007/978-2-8178-0039-4, "Block codes", pp. 109-166. ISBN 9782817800387. Gearchiveerd op 13 augustus 2020.

Bronvermelding

• Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Block code op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.