title: Blokcode
text: 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 . 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 parameters 
  Een 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 k 
  Elke 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 n 
  De 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 R 
  Het 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 w
  De (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.
  
  Notatie 
  De 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.
  
  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 -code.
  
   Reed-Solomoncodes zijn -codes, waarbij  en  een priemmacht is.
   Rankcodes zijn <mat-codes, met  en .
  
  Foutdetectie en foutcorrectie 
  Een 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:
    kan  fouten detecteren. Omdat een codewoord  het enige codewoord is in de Hammingbal gecentreerd op zichzelf met straal  is, kan een foutpatroon met  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 , 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).
    kan  fouten corrigeren. Omdat een codewoord  het enige codewoord is in de Hammingbal gecentreerd op zichzelf met straal  is, kunnen de Hammingballen gecentreerd op twee andere codewoorden met straal  nooit overlappen met elkaar. Een fout kan dan gecorrigeerd worden door het dichtstbijzijnde codewoord voor het ontvangen woord  te zoeken, zolang het aantal fouten minder dan  is: er is dan maar één codewoord in de Hammingbal gecentreerd op  met straal .
   Om te decoderen bij meer dan  fouten, kan met gebruik maken van list decoding of maximum likelihood decoding.
    kan  ontbrekende symbolen corrigeren. Hierbij moet opgemerkt worden dat de positie van het verdwenen symbool gekend dient te zijn.
  
  Literatuur
  
  Bronvermelding 
   
  
  Code
  Informatietheorie