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].

Cousins

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

Member of code lists

Primary Hierarchy

Classical Domain

Error-correcting code (ECC)

Block code

Parents

Block code

Convolutional codes for infinite block size are block codes consisting of infinite blocks.

Convolutional code

Children

Irregular convolutional code (IRCC)

LDPC convolutional code (LDPC-CC)

Turbo 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, J. Cocke, F. Jelinek, and J. Raviv, “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]: Piret, Philippe. Convolutional codes: an algebraic approach. MIT press, 1988.
[12]: H. C. Ferreira, A. J. H. Vinck, T. G. Swart, and I. deBeer, “Permutation Trellis Codes”, IEEE Transactions on Communications 53, 1782 (2005) DOI
[13]: G. D. Forney, Jr., “Why quasi cyclic codes are interesting,” unpublished note, 1970.
[14]: G. Solomon and H. C. A. Tilborg, “A Connection Between Block and Convolutional Codes”, SIAM Journal on Applied Mathematics 37, 358 (1979) DOI
[15]: R. Michael Tanner, “Error-correcting coding system,” U.S. Patent 4295218, 1981.
[16]: 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.
[17]: “Generalized tail-biting convolutional codes,” Ph.D. dissertation, Univ. of Massachusetts, Amherst, 1985.
[18]: 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.
[19]: M. Esmaeili, T. A. Gulliver, N. P. Secord, and S. A. Mahmoud, “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.