Efficient maximum likelihood decoding of linear block codes using a trellis
- 1 January 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 24 (1) , 76-80
- https://doi.org/10.1109/tit.1978.1055821
Abstract
It is shown that soft decision maximum likelihood decoding of any(n,k)linear block code overGF(q)can be accomplished using the Viterbi algorithm applied to a trellis with no more thanq^{(n-k)}states. For cyclic codes, the trellis is periodic. When this technique is applied to the decoding of product codes, the number of states in the trellis can be much fewer thanq^{n-k}. For a binary(n,n - 1)single parity check code, the Viterbi algorithm is equivalent to the Wagner decoding algorithm.Keywords
This publication has 8 references indexed in Scilit:
- An optimum symbol-by-symbol decoding rule for linear codesIEEE Transactions on Information Theory, 1976
- Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)IEEE Transactions on Information Theory, 1974
- Algebraic decoding of block codes over a q-ary input, Q-ary output channel, Q > qInformation and Control, 1973
- Class of algorithms for decoding block codes with channel measurement informationIEEE Transactions on Information Theory, 1972
- Decoding binary block codes onQ-ary output channelsIEEE Transactions on Information Theory, 1971
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithmIEEE Transactions on Information Theory, 1967
- Generalized minimum distance decodingIEEE Transactions on Information Theory, 1966
- Coding for constant-data-rate systemsTransactions of the IRE Professional Group on Information Theory, 1954