Content deleted Content added
No edit summary |
No edit summary |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 3:
In [[Telecommunications|telecommunication]], a '''convolutional code''' is a type of [[Error correction code|error-correcting code]] that generates parity symbols via the sliding application of a [[Algebraic normal form|boolean polynomial]] function to a data stream. The sliding application represents the 'convolution' of the encoder over the data, which gives rise to the term 'convolutional coding'. The sliding nature of the convolutional codes facilitates [[Trellis (graph)|trellis]] decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity.
The ability to perform economical maximum likelihood soft decision decoding is one of the major benefits of convolutional codes. This is in contrast to classic block codes, which are generally represented by a time-variant trellis and therefore are typically hard-decision decoded. Convolutional codes are often characterized by the base [[code rate]] and the depth (or memory) of the encoder <math>[n,k,K]</math>. The base code rate is typically given as <math>n/k</math>, where {{mvar|n}} is the raw input data rate and {{mvar|k}} is the data rate of output channel encoded stream. {{mvar|n}} is less than {{mvar|k}} because channel coding inserts redundancy in the input bits. The memory is often called the "constraint length" {{mvar|K}}, where the output is a function of the current input as well as the previous <math>K-1</math> inputs. The depth may also be given as the number of memory elements {{mvar|v}} in the polynomial or the maximum possible number of states of the encoder (typically: <math>2^v</math>).
Convolutional codes are often described as continuous. However, it may also be said that convolutional codes have arbitrary block length, rather than being continuous, since most real-world convolutional encoding is performed on blocks of data. Convolutionally encoded block codes typically employ termination. The arbitrary block length of convolutional codes can also be contrasted to classic [[block code]]s, which generally have fixed block lengths that are determined by algebraic properties.
Line 12:
Convolutional codes were introduced in 1955 by [[Peter Elias]]. It was thought that convolutional codes could be decoded with arbitrary quality at the expense of computation and delay. In 1967, [[Andrew Viterbi]] determined that convolutional codes could be maximum-likelihood decoded with reasonable complexity using time invariant trellis based decoders — the [[Viterbi algorithm]]. Other trellis-based decoder algorithms were later developed, including the [[BCJR algorithm|BCJR]] decoding algorithm.
Recursive systematic convolutional codes were invented by [[Claude Berrou]] around 1991. These codes proved especially useful for iterative processing including the processing of concatenated codes such as [[Turbo code|turbo codes]].<ref>Benedetto, Sergio, and Guido Montorsi. "[https://web.archive.org/web/20190406181758/https://ieeexplore.ieee.org/abstract/document/390945/ Role of recursive convolutional codes in turbo codes]." Electronics Letters 31.11 (1995): 858-859.</ref>
Using the "convolutional" terminology, a classic convolutional code might be considered a [[Finite impulse response]] (FIR) filter, while a recursive convolutional code might be considered an [[Infinite impulse response]] (IIR) filter.
Line 243:
{{Main article|Turbo code}}
[[File:Turbo codes scheme.png|thumb|350 px| A turbo code with component codes 13, 15.<ref>[http://www.scholarpedia.org/article/Turbo_codes Turbo code]</ref> Turbo codes get their name because the decoder uses feedback, like a turbo engine. Permutation means the same as the interleaving. C1 and C2 are recursive convolutional codes. Recursive and non-recursive convolutional codes are not so much different in BER performance, however, recursive type of is implemented in Turbo convolutional codes due to better interleaving properties.<ref>Benedetto, Sergio, and Guido Montorsi. "[https://web.archive.org/web/20190406181758/https://ieeexplore.ieee.org/abstract/document/390945/ Role of recursive convolutional codes in turbo codes]." Electronics Letters 31.11 (1995): 858-859.</ref>]]
Simple Viterbi-decoded convolutional codes are now giving way to [[turbo code]]s, a new class of iterated short convolutional codes that closely approach the theoretical limits imposed by [[Noisy-channel coding theorem|Shannon's theorem]] with much less decoding complexity than the Viterbi algorithm on the long convolutional codes that would be required for the same performance. [[Concatenated error correction code|Concatenation]] with an outer algebraic code (e.g., [[Reed–Solomon error correction|Reed–Solomon]]) addresses the issue of [[error floor]]s inherent to turbo code designs.
| |||