Convolutional code: Difference between revisions

Revision as of 17:32, 31 January 2022

Revision as of 00:20, 24 July 2022

Line 1:

{{Short description|Type of error-correcting code using convolution}}

{{refimprovemore citations needed|date=May 2015}}

In [[telecommunication]], a '''convolutional code''' is a type of [[Forward error correction|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.

Line 7:

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.

The code rate of a convolutional code is commonly modified via [[PuncturingPunctured code|symbol puncturing]]. For example, a convolutional code with a 'mother' code rate <math>n/k=1/2</math> may be punctured to a higher rate of, for example, <math>7/8</math> simply by not transmitting a portion of code symbols. The performance of a punctured convolutional code generally scales well with the amount of parity transmitted. The ability to perform economical soft decision decoding on convolutional codes, as well as the block length and code rate flexibility of convolutional codes, makes them very popular for digital communications.

==History==

Line 19:

==Where convolutional codes are used==

[[File:GSM convol code.png|thumb|right|400px|Stages of channel coding in GSM.<ref>Eberspächer J. et al. GSM-architecture, protocols and services. – John Wiley & Sons, 2008. - p.97</ref> Block encoder and Parity check - error detection part. Convolutional encoder and Viterbi decoder - error correction part. [[Error_correction_codeError correction code#Interleaving|Interleaving]] and Deinterleaving - code words separation increasing in time ___domain and to avoid bursty distortions.]]

Convolutional codes are used extensively to achieve reliable data transfer in numerous applications, such as [[digital video]], radio, [[mobile communications]] (e.g., in GSM, GPRS, EDGE and 3G networks (until 3GPP Release 7)<ref>3rd Generation Partnership Project (September 2012). "3GGP TS45.001: Technical Specification Group GSM/EDGE Radio Access Network; Physical layer on the radio path; General description". Retrieved 2013-07-20.</ref><ref>Halonen, Timo, Javier Romero, and Juan Melero, eds. GSM, GPRS and EDGE performance: evolution towards 3G/UMTS. John Wiley & Sons, 2004. - p. 430</ref>) and [[satellite communications]].<ref>Butman, S. A., L. J. Deutsch, and R. L. Miller. [http://tda.jpl.nasa.gov/progress_report/42-63/63H.PDF "Performance of concatenated codes for deep space missions."] The Telecommunications and Data Acquisition Progress Report 42-63, March–April 1981 (1981): 33-39.</ref> These codes are often implemented in [[concatenated code|concatenation]] with a hard-decision code, particularly [[Reed–Solomon error correction|Reed–Solomon]]. Prior to [[turbo codes]] such constructions were the most efficient, coming closest to the [[Shannon-Hartley theorem|Shannon limit]].

Line 35:

* systematic repeats the structure of the message before encoding

* non-systematic changes the initial structure

Line 131 ⟶ 130:

{{see also|Viterbi algorithm}}

[[File:Convolutional codes PSK QAM LLR.svg|thumb|right|300px| Bit error ratio curves for convolutional codes with different options of digital modulations ([[Phase-shift keying|QPSK, 8-PSK]], [[Quadrature amplitude modulation|16-QAM, 64-QAM]]) and [[Likelihood_functionLikelihood function#Log-likelihood|LLR]] Algorithms.<ref>[https://www.mathworks.com/help/comm/examples/llr-vs-hard-decision-demodulation.html LLR vs. Hard Decision Demodulation (MathWorks)]</ref><ref>[https://www.mathworks.com/help/comm/ug/estimate-ber-for-hard-and-soft-decision-viterbi-decoding.html Estimate BER for Hard and Soft Decision Viterbi Decoding (MathWorks)]</ref> (Exact<ref>[https://www.mathworks.com/help/comm/ug/digital-modulation.html#brc6yjx Digital modulation: Exact LLR Algorithm (MathWorks)]</ref> and Approximate<ref>[https://www.mathworks.com/help/comm/ug/digital-modulation.html#brc6ymu Digital modulation: Approximate LLR Algorithm (MathWorks)]</ref>) over additive white Gaussian noise channel.]]

Several [[algorithm]]s exist for decoding convolutional codes. For relatively small values of ''k'', the [[Viterbi algorithm]] is universally used as it provides [[maximum likelihood]] performance and is highly parallelizable. Viterbi decoders are thus easy to implement in [[VLSI]] hardware and in software on CPUs with [[SIMD]] instruction sets.

Line 145 ⟶ 144:

In fact, predefined convolutional codes structures obtained during scientific researches are used in the industry. This relates to the possibility to select catastrophic convolutional codes (causes larger number of errors).

An especially popular Viterbi-decoded convolutional code, used at least since the [[Voyager program]] has a constraint length {{mvar|K}} of 7 and a rate ''r'' of 1/2.<ref> Butman, S. A., L. J. Deutsch, and R. L. Miller. [https://ipnpr.jpl.nasa.gov/progress_report/42-63/63H.PDF "Performance of concatenated codes for deep space missions." ] The Telecommunications and Data Acquisition Progress Report 42-63, March–April 1981 (1981): 33-39.</ref>

[[Mars Pathfinder]], [[Mars Exploration Rover]] and the [[Cassini probe]] to Saturn use a {{mvar|K}} of 15 and a rate of 1/6; this code performs about 2&nbsp;dB better than the simpler <math>K=7</math> code at a cost of 256× in decoding complexity (compared to Voyager mission codes).

Line 245 ⟶ 244:

==Further reading==

{{refbegin}}

===Publications===

* Francis, Michael. "Viterbi Decoder Block Decoding-Trellis Termination and Tail Biting." Xilinx XAPP551 v2. 0, DD (2005): 1-21.