BCJR algorithm
Encyclopedia
The BCJR algorithm is an algorithm for maximum a posteriori
decoding of error correcting codes defined on trellises (principally convolutional code
s). The algorithm is named after its inventors: Bahl, Cocke, Jelinek
and Raviv . This algorithm is critical to modern iteratively-decoded error-correcting codes including turbo code
s and low-density parity-check code
s.
:
Maximum a posteriori
In Bayesian statistics, a maximum a posteriori probability estimate is a mode of the posterior distribution. The MAP can be used to obtain a point estimate of an unobserved quantity on the basis of empirical data...
decoding of error correcting codes defined on trellises (principally convolutional code
Convolutional code
In telecommunication, a convolutional code is a type of error-correcting code in which* each m-bit information symbol to be encoded is transformed into an n-bit symbol, where m/n is the code rate and...
s). The algorithm is named after its inventors: Bahl, Cocke, Jelinek
Frederick Jelinek
Frederick Jelinek was a Czech American researcher in information theory, automatic speech recognition, and natural language processing...
and Raviv . This algorithm is critical to modern iteratively-decoded error-correcting codes including turbo code
Turbo code
In information theory, turbo codes are a class of high-performance forward error correction codes developed in 1993, which were the first practical codes to closely approach the channel capacity, a theoretical maximum for the code rate at which reliable communication is still possible given a...
s and low-density parity-check code
Low-density parity-check code
In information theory, a low-density parity-check code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel, and is constructed using a sparse bipartite graph...
s.
Steps involved
based on the trellisConvolutional code
In telecommunication, a convolutional code is a type of error-correcting code in which* each m-bit information symbol to be encoded is transformed into an n-bit symbol, where m/n is the code rate and...
:
- Compute Forward probabilities
- Compute Backward probabilities
- Compute smoothed probabilities based on other information (i.e. noise variance for AWGN, bit crossover probability for Binary symmetric channelBinary symmetric channelA binary symmetric channel is a common communications channel model used in coding theory and information theory. In this model, a transmitter wishes to send a bit , and the receiver receives a bit. It is assumed that the bit is usually transmitted correctly, but that it will be "flipped" with a...
)
See also
- Forward-backward algorithm
- Maximum a posteriori (MAP) estimationMaximum a posterioriIn Bayesian statistics, a maximum a posteriori probability estimate is a mode of the posterior distribution. The MAP can be used to obtain a point estimate of an unobserved quantity on the basis of empirical data...
- Hidden Markov modelHidden Markov modelA hidden Markov model is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved states. An HMM can be considered as the simplest dynamic Bayesian network. The mathematics behind the HMM was developed by L. E...
External links
- The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses the BCJR algorithm in chapter 25.