11.3 BCJR Algorithm

The BCJR algorithm is a powerful decoding method for convolutional codes. It uses forward and backward recursions to calculate probabilities of states and transitions in a trellis diagram, enabling accurate soft-decision decoding of received sequences.

This algorithm plays a crucial role in turbo codes and iterative decoding. By computing log-likelihood ratios for each bit, it provides soft information that can be used in iterative decoding schemes, improving overall error correction performance.

Recursion and Metrics

Forward and Backward Recursion

• Forward recursion calculates the probability of reaching each state in the trellis at time $k$ based on the probabilities of the states at time $k-1$ and the branch metrics connecting them
• Denoted as $\alpha_k(s)$, where $s$ is the state at time $k$
• Backward recursion calculates the probability of reaching each state in the trellis at time $k$ based on the probabilities of the states at time $k+1$ and the branch metrics connecting them
• Denoted as $\beta_k(s)$, where $s$ is the state at time $k$
• Recursions are initialized with known probabilities at the start and end states of the trellis ($\alpha_0(s_0) = 1$, $\beta_N(s_N) = 1$)

Branch and State Metrics

• Branch metrics represent the probability of transitioning from one state to another along a specific branch in the trellis
• Calculated using the channel output and the expected output for each possible input sequence (Hamming distance or Euclidean distance)
• State metrics combine the branch metrics and the probabilities from the forward and backward recursions to determine the likelihood of being in a particular state at time $k$
• Denoted as $\gamma_k(s',s) = p(y_k, s_k=s | s_{k-1}=s')$, where $s'$ is the previous state and $s$ is the current state

Probabilities and Ratios

A Posteriori Probabilities (APP)

• APP represents the probability of a particular bit being 0 or 1 given the entire received sequence
• Calculated by summing the state metrics for all states at time $k$ where the bit is 0 or 1
• $APP(u_k=0) = \sum_{(s',s):u_k=0} \alpha_{k-1}(s') \gamma_k(s',s) \beta_k(s)$
• $APP(u_k=1) = \sum_{(s',s):u_k=1} \alpha_{k-1}(s') \gamma_k(s',s) \beta_k(s)$

Log-Likelihood Ratios (LLRs) and Max-Log-MAP Approximation

• LLRs represent the logarithm of the ratio of the APP for a bit being 1 to the APP for a bit being 0
• $LLR(u_k) = \log \frac{APP(u_k=1)}{APP(u_k=0)}$
• Max-log-MAP approximation simplifies the LLR calculation by using the maximum state metrics instead of summing over all states
• $LLR(u_k) \approx \max_{(s',s):u_k=1} (\alpha_{k-1}(s') + \gamma_k(s',s) + \beta_k(s)) - \max_{(s',s):u_k=0} (\alpha_{k-1}(s') + \gamma_k(s',s) + \beta_k(s))$
• Reduces computational complexity at the cost of some performance loss

Trellis Representation

Trellis Diagram

• Trellis diagram is a graphical representation of the encoding process and the possible state transitions
• Each node represents a state at a specific time step, and each branch represents a possible transition between states
• Input bits determine the path through the trellis (upper branch for 0, lower branch for 1)
• Output bits are associated with each branch, determined by the generator polynomials of the convolutional code
• Trellis structure depends on the encoder's memory and generator polynomials (rate 1/2 encoder with memory 2 has 4 states and 8 branches per time step)
• BCJR algorithm operates on the trellis to calculate forward and backward recursions, branch metrics, and state metrics for decoding