Convolutional code

Convolutional code[1]

Description

Infinite-block code that is formed using generator polynomials over the finite field with two elements. The encoder slides across contiguous subsets of the input bit-string (like a convolutional neural network) evaluating the polynomials on that window to obtain a number of parity bits. These parity bits are the encoded information.

Rate

Depends on the polynomials used. Using puncturing removal [2] the rate for the code can be increased from \(\frac{1}{t}\) to \(\frac{s}{t}\), where \(t\) is the number of output bits, and \(s\) depends on the puncturing done. This is done by deleting some pieces of the encoder output such that the most-likely decoders remain effective

Encoding

Evaluation on the generator polynomials. Can be implemented with a small number of XOR gates

Decoding

Decoders based on the Viterbi algorithm (trellis decoding) were developed first, which result in the most-likely codeword for the encoded bits [3].BCJR decoder, also a trellis-based decoder [4].

Realizations

A type of convolutional code used in Real-time Application networks [5].Mobile and radio communications (3G networks) use convolutional codes concatenated with RS codes to obtain suitable performance [6].A convolutional code with rate 1/2 was used for deep-space and satellite communication [7]

Notes

There are connections between convolutional codes and statistical mechanical models [8–10].

Parent

Block code — Convolutional codes for infinite block size are block codes consisting of infinite blocks.

Children

Cousins

\(q\)-ary code — Convolutional codes for finite block size are \(q\)-ary codes.
Quantum convolutional code
Reed-Solomon (RS) code — Convolutional codes are often used in concatenation with RS codes for communication [6].
Code in permutations — Convolutional codes in permutations have been constructed [11].
Quasi-cyclic code — Quasi-cyclic codes can be unwrapped to obtain convolutional codes [12–18].
EA quantum convolutional code

References

[1]: Peter Elias. Coding for noisy channels. IRE Convention Records, 3(4):37–46, 1955.
[2]: L. Sari, “Effects of Puncturing Patterns on Punctured Convolutional Codes”, TELKOMNIKA (Telecommunication, Computing, Electronics and Control) 10, (2012) DOI
[3]: A. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm”, IEEE Transactions on Information Theory 13, 260 (1967) DOI
[4]: L. Bahl et al., “Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)”, IEEE Transactions on Information Theory 20, 284 (1974) DOI
[5]: S. I. Mrutu, A. Sam, and N. H. Mvungi, “Forward Error Correction Convolutional Codes for RTAs’ Networks: An Overview”, International Journal of Computer Network and Information Security 6, 19 (2014) DOI
[6]: T. Halonen, J. Romero, and J. Melero, editors , “GSM, GPRS and EDGE Performance”, (2003) DOI
[7]: Butman, Deutsch, and Miller. Performance of concatenated codes for deep space missions. 1981.
[8]: P. Ruján, “Finite temperature error-correcting codes”, Physical Review Letters 70, 2968 (1993) DOI
[9]: M. Mézard and A. Montanari, “Information, Physics, and Computation”, (2009) DOI
[10]: H. Nishimori, “Statistical Physics of Spin Glasses and Information Processing”, (2001) DOI
[11]: H. C. Ferreira et al., “Permutation Trellis Codes”, IEEE Transactions on Communications 53, 1782 (2005) DOI
[12]: G. D. Forney, Jr., “Why quasi cyclic codes are interesting,” unpublished note, 1970.
[13]: G. Solomon and H. C. A. Tilborg, “A Connection Between Block and Convolutional Codes”, SIAM Journal on Applied Mathematics 37, 358 (1979) DOI
[14]: R. Michael Tanner, “Error-correcting coding system,” U.S. Patent 4295218, 1981.
[15]: R. Michael Tanner. Convolutional codes from quasi-cyclic codes: A link between the theories of block and convolutional codes. University of California, Santa Cruz, Computer Research Laboratory, 1987.
[16]: “Generalized tail-biting convolutional codes,” Ph.D. dissertation, Univ. of Massachusetts, Amherst, 1985.
[17]: Y. Levy and J. Costello, Jr., “An algebraic approach to constructing convolutional codes from quasi-cyclic codes,” DIMACS Ser. Discr. Math. and Theor. Comp. Sci., vol. 14, pp. 189–198, 1993.
[18]: M. Esmaeili et al., “A link between quasi-cyclic codes and convolutional codes”, IEEE Transactions on Information Theory 44, 431 (1998) DOI

Page edit log

Victor V. Albert (2021-12-16) — most recent
Benjamin Quiring (2021-12-16)

Cite as:

“Convolutional code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2021. https://errorcorrectionzoo.org/c/convolutional

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/convolutional/convolutional.yml.