Coderingstheorie

Van Wikipedia

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

[bewerk] Broncodering versus kanaalcodering

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

Bij kanaalcodering worden er weer symbolen toegevoegd aan de gecodeerde informatie, ter bescherming tegen transport over het kanaal. Wat binnen de telecommunicatie 'kanaalcodering' genoemd wordt, noemen wiskundigen coderingstheorie. Er bestaan twee vormen van bescherming tegen fouten op een kanaal: foutdetectie en foutcorrectie. Foutdetectie geeft aan de ontvangstzijde een indicatie dat er fouten zijn opgetreden. De ontvanger kan in dat geval aan de zender vragen om hertransmissie van de foutief ontvangen informatie. Bij foutcorrectie is de ontvanger in staat om uit de foutief ontvangen informatie te herleiden wat de meest waarschijnlijk verzonden informatie was; hierbij wordt gebruikgemaakt van een zogenaamde 'foutcorrigerende code'. De foutkans kan hierdoor worden verkleind, maar wordt nooit helemaal nul.

De prestaties van foutcorrigerende codes worden gelimiteerd door de Shannonlimiet.

[bewerk] Theorie

In de coderingstheorie wordt vanwege de eenvoud van analyse gewerkt met codewoorden die eenzelfde lengte n hebben (dit in tegenstelling tot technieken uit de broncodering, zoals Huffman-codering, of de morse-code, die werken met codewoorden van verschillende lengte).

Foutdetecterende en foutcorrigerende codes werken op informatie die in digitale vorm is. De informatie kan zijn vastgelegd met behulp van binaire symbolen, bits (Binary digIT: 0 of 1), of symbolen uit een ander eindig lichaam $G F (p k)$ .

De Hammingafstand tussen twee (code)woorden is het aantal symboolposities waar de twee woorden van elkaar verschillen. Bijvoorbeeld de binaire woorden '110011' en '110000' verschillen op de twee laatste posities, en de Hammingafstand is twee. De minimum Hammingafstand van een verzameling van codewoorden, een code, is de kleinste onderlinge afstand die voorkomt tussen twee woorden uit die code. Een code met minimum Hammingafstand 2e+1 heeft een foutcorrigerend vermogen van e fouten, dat wil zeggen dat als een woord tijdens transport door het kanaal maximaal e fouten krijgt, 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 (en dus een grote Hammingafstand) en tegelijkertijd zoveel mogelijk informatie te kunnen transporteren (en dus te kunnen kiezen uit zoveel 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 dan ook deel uit van de discrete wiskunde.