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

Top images from around the web for Forward and Backward Recursion

• 

  Forward substitution - Algowiki View original

  Is this image relevant?

• 

  Hidden Markov Model View original

  Is this image relevant?

• 

  Tree diagram (probability theory) - Wikipedia View original

  Is this image relevant?

• 

  Forward substitution - Algowiki View original

  Is this image relevant?

• 

  Hidden Markov Model View original

  Is this image relevant?

1 of 3

Top images from around the web for Forward and Backward Recursion

• 

  Forward substitution - Algowiki View original

  Is this image relevant?

• 

  Hidden Markov Model View original

  Is this image relevant?

• 

  Tree diagram (probability theory) - Wikipedia View original

  Is this image relevant?

• 

  Forward substitution - Algowiki View original

  Is this image relevant?

• 

  Hidden Markov Model View original

  Is this image relevant?

1 of 3

• 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