BlokcodeIn 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. WerkingBij 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 . Elk blok wordt vervolgens onafhankelijk van andere blokken omgezet (gecodeerd) naar een codewoord, een blok van vaste lengte . 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 parametersEen blokcode is wiskundig gezien een injectie . Hierbij is een eindige, niet-lege verzameling en zijn en 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 . De grootte van het alfabet wordt wel genoteerd als . Als , spreekt men van een binaire blokcode. In veel toepassingen is het wenselijk dat een macht van een priemgetal is, waardoor beschouwd kan worden als het eindige veld / lichaam . De boodschaplengte kElke boodschap is een element van , dat wil zeggen een tekenreeks bestaande uit symbolen uit van lengte . Het getal wordt de informatielengte, boodschaplengte of dimensie van de blokcode genoemd. De bloklengte nDe bloklengte is het aantal symbolen in een codewoord. De elementen van zijn dus tekenreeksen van lengte 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 is het codewoord van die boodschap. In formule: . Het datadebiet RHet datadebiet (Eng. rate) van een blokcode wordt gedefinieerd als de verhouding tussen de boodschaplengte en de bloklengte: . 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 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 , aangezien gegevens in het algemeen niet gecomprimeerd kunnen worden zonder dat daarbij informatie verloren gaat. De afstand d en het gewicht wDe (minimum)afstand van een blokcode is het minimaal aantal posities die verschillend zijn tussen elke twee codewoorden; de relatieve afstand is de verhouding . Als de Hammingafstand tussen de twee codewoorden is, zal de minimumafstand van de code gegeven worden door: Elk codewoord zal in minstens één positie verschillen van alle andere codewoorden, dus . Het gewicht van een codewoord is het aantal posities die niet gelijk zijn aan nul. Het minimumgewicht 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: 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 maakt het mogelijk om fouten te detecteren, aangezien het wijzigen van posities nooit leidt tot een ander codewoord. Als er bovendien niet meer dan fouten optreden tijdens de transmissie, kan de ontvanger het codewoord uniek decoderen. Dit omdat voor elk ontvangen woord er op afstand 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. NotatieDe notatie beschrijft een blokcode over een alfabet van grootte , met een bloklengte , boodschaplengte en afstand . Als de blokcode lineair is, kunnen blokhaken gebruikt worden om dit aan te geven: . Zowel als worden nogal eens weggelaten: als het gaat om een binaire code is vanzelfsprekend , en de laat men wel wewg als de afstand niet belangrijk is, niet bekend is of moeilijk te bepalen. VoorbeeldenDe meeste foutcorrigerende codes zijn blokcodes.
Foutdetectie en foutcorrectieEen codewoord kan beschouwd worden als een punt in een -dimensionale ruimte ; de code is een deelverzameling van . Een code met afstand betekent dat voor iedere geldt dat de Hammingbal gecentreerd op het punt met straal leeg is. De Hammingbal betekent hier de verzameling van -dimensionale woorden waarvan de Hammingafstand tot maximaal is. Equivalent heeft een code met afstand de eigenschappen:
Literatuur
Bronvermelding
|