BCJR (Bahl, Cocke, Jelinek and Raviv algorithm)

The BCJR algorithm, named after its inventors Bahl, Cocke, Jelinek, and Raviv, is a forward-backward algorithm that can be used to compute the log-likelihood ratio of each bit in a sequence of data that has been transmitted through a noisy channel. This algorithm is widely used in communication systems, including wireless and wired communication, digital television, and satellite communication.

The BCJR algorithm is based on the assumption that the received sequence of data can be modeled as a sequence of random variables. The random variables are assumed to be Gaussian, with a mean that depends on the transmitted data and a variance that depends on the channel noise. The BCJR algorithm works by computing the likelihood of each transmitted bit given the received sequence of data and the channel model.

To understand the BCJR algorithm, we need to first understand the basic concepts of forward and backward recursion. In the forward recursion, we compute the probability of reaching a particular state at time t given the received data up to time t. In the backward recursion, we compute the probability of observing the remaining data after time t, given that we are in a particular state at time t.

In the BCJR algorithm, we use both forward and backward recursion to compute the log-likelihood ratio of each transmitted bit. The log-likelihood ratio is the logarithm of the ratio of the probability that the bit is a 1 to the probability that the bit is a 0, given the received data.

To compute the log-likelihood ratio using the BCJR algorithm, we first represent the transmitted data as a sequence of bits b_1, b_2, ..., b_N, where N is the length of the sequence. We then represent the received data as a sequence of random variables y_1, y_2, ..., y_N, where each y_i is a noisy version of the transmitted bit b_i.

We also represent the channel as a state diagram, where each state corresponds to a possible sequence of transmitted bits up to time t, and the transitions between states represent the possible transmissions of the next bit at time t+1. We denote the state at time t as s_t.

The BCJR algorithm works as follows:

1. Initialization: We start by computing the forward and backward probabilities for the first state s_1. The forward probability alpha_1(s_1) is the probability of reaching the first state s_1 given the received data up to time 1. The backward probability beta_1(s_1) is the probability of observing the remaining data after time 1, given that we are in state s_1 at time 1.
2. Recursion: We then compute the forward and backward probabilities for each state s_t, t=2,...,N. The forward probability alpha_t(s_t) is the probability of reaching state s_t given the received data up to time t. The backward probability beta_t(s_t) is the probability of observing the remaining data after time t, given that we are in state s_t at time t.
3. Compute Gamma: We then compute the gamma values for each state s_t and each bit b_t. The gamma value gamma_t(s_t,b_t) is the probability that bit b_t was transmitted given the received data up to time t and the state s_t.
4. Compute Xi: We then compute the xi values for each pair of states s_t and s_{t+1}, and each bit b_t. The xi value xi_t(s_t,s_{t+1},b_t) is the probability of transitioning from state s_t to state s_{t+1} and transmitting bit b_t, given the received data up to time t.
5. Compute the log-likelihood ratio: Finally, we compute the log- likelihood ratio for each transmitted bit using the gamma and xi values. The log-likelihood ratio of bit b_t is given by:

L(b_t) = log [ sum_{s_t} sum_{s_{t+1}} gamma_t(s_t,b_t) xi_t(s_t,s_{t+1},b_t) beta_{t+1}(s_{t+1}) / alpha_t(s_t) ]

where the sum is taken over all possible states s_t and s_{t+1}.

This formula computes the log-likelihood ratio of bit b_t by combining the contributions of all possible paths through the state diagram that could have led to the observation of the received data up to time t. The ratio of the gamma and xi values in the numerator reflects the likelihood of the specific bit b_t being transmitted given the received data up to time t and the state at time t. The backward probability beta_{t+1}(s_{t+1}) reflects the probability of observing the remaining data after time t given that we are in state s_{t+1} at time t+1. The forward probability alpha_t(s_t) reflects the probability of reaching state s_t at time t given the received data up to time t.

The BCJR algorithm is computationally efficient because it avoids the need to compute the probabilities of all possible sequences of transmitted bits. Instead, it computes the likelihood of each bit given the received data and the channel model, which can be done using the forward and backward recursion, and then combines these likelihoods using the gamma and xi values.

One important application of the BCJR algorithm is in the decoding of convolutional codes. A convolutional code is a type of error-correcting code that encodes a stream of input bits into a longer stream of output bits using a shift register and a set of modulo-2 adders. The BCJR algorithm can be used to decode the received data by finding the most likely sequence of transmitted bits that could have produced the observed data, given the convolutional code and the channel model.

In conclusion, the BCJR algorithm is a powerful tool for computing the log-likelihood ratio of each bit in a sequence of data that has been transmitted through a noisy channel. The algorithm is based on the forward-backward recursion and can be applied to various types of communication systems, including wireless and wired communication, digital television, and satellite communication. The BCJR algorithm is computationally efficient and can be used in the decoding of convolutional codes.