Abstract
The probability of error in decoding an optimal convolutional code transmitted over a memoryless channel is bounded from above and below as a function of the constraint length of the code. For all but pathological channels the bounds are asymptotically (exponentially) tight for rates above <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_{0}</tex> , the computational cutoff rate of sequential decoding. As a function of constraint length the performance of optimal convolutional codes is shown to be superior to that of block codes of the same length, the relative improvement increasing with rate. The upper bound is obtained for a specific probabilistic nonsequential decoding algorithm which is shown to be asymptotically optimum for rates above <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_{0}</tex> and whose performance bears certain similarities to that of sequential decoding algorithms.
Keywords
Decoding methodsAlgorithmList decodingConvolutional codeSequential decodingMathematicsUpper and lower boundsBounded functionDiscrete mathematicsConstraint (computer-aided design)Code (set theory)Asymptotically optimal algorithmProbabilistic logicFunction (biology)Berlekamp–Welch algorithmBlock codeComputer scienceConcatenated error correction codeStatistics
Affiliated Institutions
Related Publications
Low-density parity-check codes
A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed number <tex xmlns:mml="http://www....
A simple derivation of the coding theorem and some applications
Upper bounds are derived on the probability of error that can be achieved by using block codes on general time-discrete memoryless channels. Both amplitude-discrete and amplitud...
Maximum distanceq-nary codes
A <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</tex> -nary error-correcting code with <tex xmlns:mml="http://www.w3.org/1998/...
Asymptotically good codes have infinite trellis complexity
The trellis complexity s(C) of a block code C is defined as the logarithm of the maximum number of states in the minimal trellis realization of the code. The parameter s(C) gove...
Asymptotically optimal block quantization
In 1948 W. R. Bennett used a companding model for nonuniform quantization and proposed the formula <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3...
Publication Info
- Year
- 1967
- Type
- article
- Volume
- 13
- Issue
- 2
- Pages
- 260-269
- Citations
- 6666
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
6666
OpenAlex
Cite This
Andrew J. Viterbi
(1967).
Error bounds for convolutional codes and an asymptotically optimum decoding algorithm.
IEEE Transactions on Information Theory
, 13
(2)
, 260-269.
https://doi.org/10.1109/tit.1967.1054010
Identifiers
- DOI
- 10.1109/tit.1967.1054010