Coderingstheorie

Coderingstheorie, niet te verwarren met cryptografie, is een onderdeel van de informatietheorie dat zich richt op het toevoegen van redundantie aan gecodeerde informatie, waardoor deze beter beschermd is tegen mogelijke fouten die kunnen optreden tijdens het verzenden over een onbetrouwbaar kanaal.

Broncodering versus kanaalcodering

Binnen de telecommunicatie bestaan er grofweg twee vormen van codering: broncodering en kanaalcodering. Bij broncodering vindt datacompressie plaats en wordt informatie met zo weinig mogelijk 'informatieverlies' in zo weinig mogelijk symbolen gerepresenteerd, met als doel efficiëntieverbetering bij opslag en verzenden over een kostbaar kanaal. Een voorbeeld van broncodering is de GSM-code, waarbij een digitaal spraaksignaal, dat bij vaste telefonie wordt gecodeerd met 64 kb/s gecomprimeerd is tot 13 kb/s, met zo weinig mogelijk hoorbaar verlies van kwaliteit.

Bij kanaalcodering worden symbolen aan het gecodeerde signaal of bericht toegevoegd om te voorkomen dat er bij het verzenden fouten optreden, die niet meer kunnen worden gerepareerd. Dit heet het toevoegen van redundantie. Wat binnen de telecommunicatie 'kanaalcodering' genoemd wordt, noemen wiskundigen coderingstheorie. Er bestaan twee vormen van bescherming tegen fouten in een kanaal: foutdetectie en foutcorrectie. Foutdetectie geeft aan de kant van de ontvanger een indicatie dat er fouten zijn opgetreden. De ontvanger kan in dat geval aan de afzender vragen om hetzelfde bericht nog eens te sturen. Bij foutcorrectie is de ontvanger in staat om uit het foutief ontvangen bericht te herleiden wat het meest waarschijnlijk verzonden bericht was, door gebruik te maken van een zogenaamde 'foutcorrigerende code'. De foutkans kan hierdoor worden verkleind, maar wordt nooit helemaal nul.

De laatste stap bij het verzenden is de lijncodering, waarbij het te verzenden digitale signaal in een amplitude- en tijd-discreet signaal wordt omgezet, dat is toegesneden op de eigenschappen van het gebruikte kanaal.

Theorie

Claude Shannon heeft in 1948 twee stellingen voor gegevensoverdracht gegeven, waarvan de eerste mede naar hem is genoemd. De eerste is de wet van Shannon-Hartley, volgens welke de capaciteit van een kanaal lineair met de bandbreedte van het kanaal toeneemt en afhankelijk is van de signaal-ruisverhouding van het gebruikte kanaal. De tweede is het noisy-channel coderings theorema, dat een maximum geeft voor het aantal symbolen, die per seconde kunnen worden verzonden over een verbinding met ruis.

In de coderingstheorie wordt vanwege de eenvoud gewerkt met codewoorden die dezelfde lengte $n$ hebben. Dat is in tegenstelling tot technieken uit de broncodering, zoals huffmancodering, of de morse-code, die werken met codewoorden van verschillende lengte.

Foutdetecterende en foutcorrigerende codes werken op berichten die in digitale vorm zijn verstuurd. De berichten kunnen zijn vastgelegd met behulp van binaire symbolen, bits, of symbolen uit een of ander eindig lichaam $\mathrm {GF} (p^{k})$.

De hammingafstand tussen twee (code)woorden is het aantal posities waar de twee woorden van elkaar verschillen. De binaire woorden '110011' en '110000' bijvoorbeeld verschillen op de twee laatste posities, dus de hammingafstand is twee. De minimum hammingafstand van een verzameling van codewoorden, van een code, is de kleinste onderlinge afstand die voorkomt tussen twee woorden uit die code. Een code met minimum hammingafstand $2r+1$ heeft een foutcorrigerend vermogen van $r$ fouten, dat wil zeggen dat als er in een woord tijdens het verzenden door het kanaal maximaal $r$ fouten optreden, gegarandeerd correct het verzonden codewoord kan worden gereconstrueerd.

Het is de uitdaging binnen de coderingstheorie om bij een gegeven woordlengte $n$, een zo groot mogelijk foutcorrigerend vermogen te hebben, dus een grote hammingafstand, en tegelijkertijd zo veel mogelijk gegevens te kunnen verzenden, dus te kunnen kiezen uit zo veel mogelijk codewoorden. Met $A[n,d]$ wordt het maximaal mogelijke aantal codewoorden ter lengte $n$ aangeduid, die als code een minimum hammingafstand $d$ hebben. In Russische coderingsliteratuur wordt dit met $B[d,n]$ aangeduid.

Coderingstheorie maakt veel gebruik van technieken uit de discrete wiskunde, en maakt volgens sommigen daar dan ook deel van uit.

Belangrijke wetenschappers

• Robert Gallager
• Marcel J.E. Golay
• Richard Hamming
• Claude Shannon
• Neil Sloane
• Andrew Viterbi

Voorbeelden

• Blokcodes
• BCH-codes
• Constant gewicht codes
• Convolutiecodes
• Cyclic redundancy check
• Cyclische codes
• Golay-codes
• Goppa Codes
• Lee-codes
• Lineaire codes, waaronder de Hamming-code
• Low-density parity-check codes
• Reed-Muller-codes
• Reed-Solomoncodes
• Turbocodes

Websites

• MathWorld. Coding Theory.
• Neil J. A. Sloane: Home Page.
• TU/e. Table of general binary codes. Lijst met maximaal aantal codewoorden A[n,d] in een binaire code