The BCJR algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for
maximum a posteriori
In Bayesian statistics, a maximum a posteriori probability (MAP) estimate is an estimate of an unknown quantity, that equals the mode of the posterior distribution. The MAP can be used to obtain a point estimate of an unobserved quantity on the ...
decoding of
error correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
s defined on trellises (principally
convolutional codes). The algorithm is named after its inventors: Bahl, Cocke,
Jelinek and Raviv.
[L.Bahl, J.Cocke, F.Jelinek, and J.Raviv, "Optimal Decoding of Linear Codes for minimizing symbol error rate", IEEE Transactions on Information Theory, vol. IT-20(2), pp. 284-287, March 1974.] This algorithm is critical to modern iteratively-decoded error-correcting codes, including
turbo code
In information theory, turbo codes (originally in French ''Turbocodes'') are a class of high-performance forward error correction (FEC) codes developed around 1990–91, but first published in 1993. They were the first practical codes to closely ...
s and
low-density parity-check code
In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC code is constructed using a sparse Tanner graph (subclass of the b ...
s.
Steps involved
Based on the
trellis
Trellis may refer to:
Structures
* Trellis (architecture), an architectural structure often used to support plants (especially vineyards)
* Trellis drainage pattern, a drainage system
Technology
* Trellis (graph), a special kind of graph used ...
:
* Compute forward probabilities
* Compute backward probabilities
* Compute smoothed probabilities based on other information (i.e.
noise variance for
AWGN
Additive white Gaussian noise (AWGN) is a basic noise model used in information theory to mimic the effect of many random processes that occur in nature. The modifiers denote specific characteristics:
* ''Additive'' because it is added to any nois ...
,
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 "f ...
)
Variations
SBGT BCJR
Berrou, Glavieux and Thitimajshima simplification.
Log-Map BCJR
[P. Robertson, P. Hoeher and E. Villebrun, "Optimal and Sub-Optimal Maximum A Posteriori Algorithms Suitable for Turbo Decoding", European Transactions on Telecommunications, Vol. 8, 1997.
]
Implementations
Susaframework implements BCJR algorithm for
forward error correction
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
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 statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an ob ...
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