Convolutional code: Difference between revisions

Revision as of 19:21, 5 December 2019

Revision as of 04:46, 30 January 2020

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_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 25:

==Convolutional encoding==

To convolutionally encode data, start with ''k'' [[memory register]]s, each holding one input bit. Unless otherwise specified, all memory registers start with a value of 0. The encoder has ''n'' modulo-2 [[Adder (electronics)|adder]]s (a modulo 2 adder can be implemented with a single [[Boolean logic|Boolean]] [[XOR gate]], where the logic is: {{math|1=0+0&nbsp;=&nbsp;0}}, {{math|1=0+1&nbsp;=&nbsp;1}}, {{math|1=1+0&nbsp;=&nbsp;1}}, {{math|1=1+1&nbsp;=&nbsp;0}}), and ''n'' [[generator polynomial]]s &mdash; one for each adder (see figure below). An input bit ''m''₁ is fed into the leftmost register. Using the generator polynomials and the existing values in the remaining registers, the encoder outputs ''n'' symbols. These symbols may be transmitted or punctured depending on the desired code rate. Now [[bit shift]] all register values to the right (''m''₁ moves to ''m''₀, ''m''₀ moves to ''m''₋₁) and wait for the next input bit. If there are no remaining input bits, the encoder continues shifting until all registers have returned to the zero state (flush bit termination).

[[File:Convolutional encoder non-recursive.png|frame|Img.1. Rate 1/3 non-recursive, non-systematic convolutional encoder with constraint length 3]]

The figure below is a rate {{1/3}} ({{frac|''m''|''n''}}) encoder with constraint length (''k'') of 3. Generator polynomials are {{math|1=''G''₁ = (1,1,1),}} {{math|1=''G''₂ = (0,1,1)}}, and {{math|1=''G''₃ = (1,0,1)}}. Therefore, output bits are calculated (modulo 2) as follows:

Line 41:

<gallery mode="packed" heights="150px">

File:SystematicNon-systematic convolutional code.png|thumb|A short illustration of non-systematic convolutional code.

File:Non-systematicSystematic convolutional code.png|thumb|A short illustration of non-systematic convolutional code.

File:Systematic convolutional code.png|thumb|A short illustration of systematic convolutional code.

</gallery>

Line 54 ⟶ 52:

[[Image:Convolutional encoder recursive.svg|thumb|340px|none|Img.2. Rate 1/2 8-state recursive systematic convolutional encoder. Used as constituent code in 3GPP 25.212 Turbo Code.]]

The example encoder is ''[[Systematic code|systematic]]'' because the input data is also used in the output symbols (Output 2). Codes with output symbols that do not include the input data are called ''non-systematic.''

Recursive codes are typically systematic and, conversely, non-recursive codes are typically non-systematic. It isn't a strict requirement, but a common practice.

Line 139 ⟶ 137:

Longer constraint length codes are more practically decoded with any of several [[sequential decoding]] algorithms, of which the [[Robert Fano|Fano]] algorithm is the best known. Unlike Viterbi decoding, sequential decoding is not maximum likelihood but its complexity increases only slightly with constraint length, allowing the use of strong, long-constraint-length codes. Such codes were used in the [[Pioneer program]] of the early 1970s to Jupiter and Saturn, but gave way to shorter, Viterbi-decoded codes, usually concatenated with large [[Reed–Solomon error correction]] codes that steepen the overall bit-error-rate curve and produce extremely low residual undetected error rates.

Both Viterbi and sequential decoding algorithms return hard decisions: the bits that form the most likely codeword. An approximate confidence measure can be added to each bit by use of the [[Soft output Viterbi algorithm]]. [[Maximum a posteriori]] (MAP) soft decisions for each bit can be obtained by use of the [[BCJR algorithm]].

==Popular convolutional codes==

[[File:Conv code 177 133.png||400px|left|thumb|Shift-register for the (7, [171, 133]) convolutional code polynomial. Branches: <math>h^1 = 171_o = [1111001]_b</math>, <math>h^2 = 133_o = [1011011]_b</math>. All of the math operations should be done by modulo 2.]]

[[File:Lenss.png|thumb|right|300px|Theoretical bit-error rate curves of encoded QPSK (soft decision), additive white Gaussian noise channel. Longer constraint lengths produce more powerful codes, but the [[complexity]] of the Viterbi algorithm [[exponential growth|increases exponentially]] with constraint lengths, limiting these more powerful codes to deep space missions where the extra performance is easily worth the increased decoder complexity.]]

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 ''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>

Line 254 ⟶ 252:

* Modestino, J., and Shou Mui. "Convolutional code performance in the Rician fading channel." IEEE Transactions on Communications 24.6 (1976): 592-606.

* Chen, Yuh-Long, and Che-Ho Wei. "Performance evaluation of convolutional codes with MPSK on Rician fading channels." IEE Proceedings F-Communications, Radar and Signal Processing. Vol. 134. No. 2. IET, 1987.

[[Category:Error detection and correction]]