convolutiecodes

Convolutiecodes zijn een klasse foutenkorrigerende codes die data codereren met behulp van geheugen in de encoder. In de gebruikelijke opzet wordt één invoerbit per tijdstap verwerkt en ontstaan er n uitvoerbits; de coderate k/n geeft de verhouding tussen invoer- en uitvoerbits aan. De constraint length K beschrijft hoe ver terug in de tijd de huidige uitvoer nog afhankelijk is van eerdere invoerbits; bij veel systemen geldt K = m+1, waarbij m het geheugen van de encoder is. De n outputs worden bepaald door generatorpolynomen gj(D) (j = 1,...,n), waarbij D de vertragingoperator is; deze polynomen geven aan welke combinatie van de huidige en voorgaande invoerbits modulo 2 wordt uitgezonden.

Een convolutionele encoder kan worden voorgesteld als een eindige-toestandmachine met m geheugenplaatsen; elke stap verschuift het geheugen en wordt een lineaire combinatie van de huidige input en de geheugenbits uitgedrukt in de outputs. Trellisdiagrammen worden vaak gebruikt om de toestanden en overgangen te illustreren. Convolutionele codes kunnen systematisch zijn, wat betekent dat een van de uitvoerbits direct gelijk is aan de huidige invoer.

Decoding: Voor maximale-likelihood sequence estimation wordt meestal het Viterbi-algoritme toegepast; het BCJR-algoritme kan soft-decision decoding leveren. De complexiteit van decoding groeit met de constraint length en het aantal outputs; hogere coderaten worden bereikt door puncturing of door koppeling met andere codes. Ook concatenatie, zoals in turbo codes, wordt veel gebruikt.

Historisch: De theorie en praktijk van convolutionele codes kregen een belangrijke impuls door de introductie van het Viterbi-algoritme in 1967 door Andrew Viterbi; sindsdien zijn convolutionele codes een standaardonderdeel in digitale communicatie en opslag. Toepassingen omvatten satelliet- en mobiele communicatie, netwerktechnologie en als bouwsteen in geavanceerde coderingsstructuren zoals turbo codes.