The Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for
maximum a posteriori
An estimation procedure that is often claimed to be part of Bayesian statistics is the maximum a posteriori (MAP) estimate of an unknown quantity, that equals the mode of the posterior density with respect to some reference measure, typically ...
decoding of
error correcting code
In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.
The centra ...
s defined on
trellises (principally
convolutional code
In telecommunication, a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of th ...
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 codes and
low-density parity-check codes.
Steps involved
Based on the
trellis:
* 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 channel
A binary symmetric channel (or BSCp) is a common communications channel model used in coding theory and information theory. In this model, a transmitter wishes to send a bit (a zero or a one), and the receiver will receive a bit. The bit will be ...
)
Variations
SBGT BCJR
Berrou, Glavieux and Thitimajshima simplification.
Log-Map BCJR
[
]
Implementations
Susaframework implements BCJR algorithm for
forward error correction
In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.
The centra ...
codes and channel equalization in C++.
See also
*
Forward-backward algorithm
*
Maximum a posteriori (MAP) estimation
*
Hidden Markov model
A hidden Markov model (HMM) is a Markov model in which the observations are dependent on a latent (or ''hidden'') Markov process (referred to as X). An HMM requires that there be an observable process Y whose outcomes depend on the outcomes of X ...
References
External links
The online textbook: Information Theory, Inference, and Learning Algorithms by
David J.C. MacKay, discusses the BCJR algorithm in chapter 25.
The implementation of BCJR algorithm in Susa signal processing framework
Error detection and correction
{{algorithm-stub