kaira.models.fec.decoders.BeliefPropagationDecoder
Inheritance diagram for BeliefPropagationDecoder
- class kaira.models.fec.decoders.BeliefPropagationDecoder(encoder: LinearBlockCodeEncoder | LDPCCodeEncoder, bp_iters: int = 10, arctanh: bool = True, return_soft: bool = False, device: str = 'cpu', *args: Any, **kwargs: Any)[source]
Bases:
BaseBlockDecoder[LinearBlockCodeEncoder|LDPCCodeEncoder]Belief propagation decoder for linear block codes and LDPC codes.
This algorithm is an iterative message-passing technique used for decoding error-correcting codes by operating on the Tanner graph representation of the code. It exchanges messages between variable nodes and check nodes to iteratively refine the decoding process. It is particularly efficient for LDPC codes due to the sparsity of their parity-check matrices.
The algorithm finds the shortest linear feedback shift register (LFSR) that generates the syndrome sequence, which corresponds to the error locator polynomial. The roots of this polynomial identify the positions of errors in the received word.
The decoder works by: 1. Initializing the decoder with the edge indices and mappings for the Tanner graph. 2. Iteratively updating the messages passed between variable nodes and check nodes. 3. Combining messages to compute soft outputs. 4. Extracting the information bits from the decoded codeword.
- encoder
The encoder instance providing code parameters.
- Type:
- G
The generator matrix of the code of size (k, n).
- Type:
- H
The parity check matrix of the code of size (n - k, n).
- Type:
- Parameters:
encoder (Union[LinearBlockCodeEncoder, LDPCCodeEncoder]) – The encoder for the code being decoded
bp_iters (int) – Number of belief propagation iterations to perform.
arctanh (bool) – Boolean flag to determine whether to use the arctanh function for message updates or
approximation (its)
return_soft (bool) – Boolean flag to determine whether to return the soft output
*args – Variable positional arguments passed to the base class
**kwargs – Variable keyword arguments passed to the base class
- Raises:
TypeError – If the encoder is not a LinearBlockCodeEncoder or LDPCCodeEncoder
Examples
>>> from kaira.models.fec.encoders import LDPCCodeEncoder >>> from kaira.models.fec.decoders import BeliefPropagationDecoder >>> from kaira.channels.analog import AWGNChannel >>> import torch >>> >>> parity_check_matrix = torch.tensor([ ... [1, 0, 1, 1, 0, 0], ... [0, 1, 1, 0, 1, 0], ... [0, 0, 0, 1, 1, 1] ... ], dtype=torch.float32) >>> # Create an encoder for an LDPC code >>> encoder = LDPCCodeEncoder(parity_check_matrix) >>> decoder = BeliefPropagationDecoder(encoder, bp_iters=10) >>> channel = AWGNChannel(snr_db=5.0) >>> >>> # Encode a message >>> message = torch.tensor([1., 0., 1., 1., 0., 1., 0.]) >>> codeword = encoder(message) >>> >>> # Simulate transmission over AWGN channel >>> bipolar_codeword = 1 - 2.0 * codeword >>> received_soft = channel(bipolar_codeword) >>> >>> # Decode and check if recovered correctly >>> decoded = decoder(received_soft) >>> print(torch.all(decoded == message)) True
Methods
Initialize the Belief Propagation decoder.
Calculate code metrics and prepare the Tanner graph representation.
Compute check-to-variable (CV) messages in the belief propagation algorithm.
Compute variable-to-check (VC) messages in the belief propagation algorithm.
Decode received codewords using the Belief Propagation algorithm.
Compute marginal probabilities for each variable node.
Prepare edge indices and map structures for the Tanner graph.
Attributes
Get the code dimension (k).
Get the code length (n).
Get the code rate (k/n).
Get the code redundancy (r = n - k).
- __init__(encoder: LinearBlockCodeEncoder | LDPCCodeEncoder, bp_iters: int = 10, arctanh: bool = True, return_soft: bool = False, device: str = 'cpu', *args: Any, **kwargs: Any)[source]
Initialize the Belief Propagation decoder.
Sets up the decoder with an encoder instance and extracts relevant parameters needed for the decoding process.
- Parameters:
encoder – The encoder instance for the code being decoded
bp_iters – Number of belief propagation iterations to perform.
arctanh – Boolean flag to determine whether to use the arctanh function or its approximation
return_soft – Boolean flag to determine whether to return the soft output
*args – Variable positional arguments passed to the base class
**kwargs – Variable keyword arguments passed to the base class
- Raises:
TypeError – If the encoder is not a LinearBlockCodeEncoder or LDPCCodeEncoder
- calc_code_metrics()[source]
Calculate code metrics and prepare the Tanner graph representation.
This method computes metrics for the code based on the parity check matrix: - Number of edges in the Tanner graph - Variable node degrees - Check node degrees - Number of variable nodes - Number of check nodes
It also initializes the Tanner graph structure and finds message indices for non-standard codes.
- prep_edge_ind()[source]
Prepare edge indices and map structures for the Tanner graph.
This method constructs the Tanner graph representation of the code by: 1. Creating edge mappings between variable nodes and check nodes 2. Grouping variable nodes and check nodes by their degrees 3. Preparing data structures for message passing (extrinsic and marginalization) 4. Building indices for efficient tensor operations during decoding
The method builds several important structures: - lv_ind: List mapping edges to their variable nodes - edge_map: Maps each variable node to its incident edges - cv_map: Maps each check node to its incident edges - marg_ec, ext_ec, ext_ce: Structures for message passing and marginalization - vc_group, cv_group: Groups of variable/check nodes with same degree
- compute_vc(cv: Tensor, soft_input: Tensor) Tensor[source]
Compute variable-to-check (VC) messages in the belief propagation algorithm.
This method calculates messages sent from variable nodes to check nodes by: 1. Reordering the soft input values according to the Tanner graph structure 2. Subtracting check-to-variable messages to compute extrinsic information
- Parameters:
cv – Check-to-variable messages tensor of shape [batch_size, num_edges]
soft_input – Soft input LLR values of shape [batch_size, code_length]
- Returns:
Variable-to-check messages tensor of shape [batch_size, num_edges]
- compute_cv(vc: Tensor) Tensor[source]
Compute check-to-variable (CV) messages in the belief propagation algorithm.
This method implements the check node update rule of the sum-product algorithm by: 1. Converting variable-to-check messages to tanh domain 2. Computing the product of tanh values (implemented as sum in log domain) 3. Converting back to LLR domain using arctanh
The implementation handles numerical stability issues and supports both exact arctanh calculation and Taylor series approximation.
- Parameters:
vc – Variable-to-check messages tensor of shape [batch_size, num_edges]
- Returns:
Check-to-variable messages tensor of shape [batch_size, num_edges]
- marginalize(cv: Tensor, soft_input: Tensor) Tensor[source]
Compute marginal probabilities for each variable node.
This method performs the final marginalization step in belief propagation by: 1. Collecting all check-to-variable messages for each variable node 2. Summing these messages to compute the marginal log-likelihood ratio 3. Adding the channel soft input to get the posterior LLR
- Parameters:
cv – Check-to-variable messages tensor of shape [batch_size, num_edges]
soft_input – Soft input LLR values of shape [batch_size, code_length]
- Returns:
Soft output LLR values of shape [batch_size, code_length]
- property code_dimension: int
Get the code dimension (k).
The code dimension is the number of information bits in each codeword, representing the actual data being transmitted.
- Returns:
The dimension of the code (number of information bits)
- property code_length: int
Get the code length (n).
The code length is the total number of bits in each codeword, including both information bits and redundancy bits.
- Returns:
The length of the code (number of bits in a codeword)
- property code_rate: float
Get the code rate (k/n).
The code rate is the ratio of information bits to the total bits, indicating the coding efficiency. Higher rates mean more efficient use of the channel but typically lower error correction capability.
- Returns:
The rate of the code (ratio of information bits to total bits)
- forward(received: Tensor, *args: Any, **kwargs: Any) Tensor | Tuple[Tensor, Tensor][source]
Decode received codewords using the Belief Propagation algorithm.
This method implements the sum-product decoding algorithm for linear block codes: 1. Input Validation: Ensures the input tensor’s dimensions are valid. 2. Initialization: Sets up messages and internal structures. 3. Iterative Decoding: Updates variable-to-check and check-to-variable messages for a fixed number of iterations. 4. Marginalization: Combines messages to compute soft outputs. 5. Message Extraction: Extracts decoded messages and optionally returns soft outputs.
- Parameters:
received – Received codeword tensor with shape (…, n) or (…, m*n) where n is the code length and m is some multiple
*args – Additional positional arguments
**kwargs – Additional keyword arguments return_soft: If True, also return the estimated codeword
- Returns:
Decoded tensor containing estimated messages with shape (…, k)
A tuple of (decoded tensor, soft codeword estimate tensor) if return_soft=True
- Return type:
Either
- Raises:
ValueError – If the last dimension of received is not a multiple of the code length