kaira.models.fec.decoders.MinSumLDPCDecoder

Inheritance diagram for MinSumLDPCDecoder

class kaira.models.fec.decoders.MinSumLDPCDecoder(encoder: LinearBlockCodeEncoder | LDPCCodeEncoder, bp_iters: int = 10, scaling_factor: float = 1.0, offset: float = 0.0, normalized: bool = False, return_soft: bool = False, device: str = 'cpu', *args: Any, **kwargs: Any)

Bases: BeliefPropagationDecoder

Min-Sum decoder for LDPC codes [Chen et al., 2005].

This decoder implements the Min-Sum algorithm, which is a simplified version of the Belief Propagation algorithm. It replaces the computationally expensive check node operations with simpler min and sign operations, reducing complexity while maintaining good performance.

The Min-Sum algorithm performs the following operations: 1. Variable node update: Same as standard BP 2. Check node update: Use min-sum approximation instead of sum-product 3. Message passing: Iterate between variable and check node updates

Supports multiple variants: - Standard Min-Sum: scaling_factor=1.0, offset=0.0 - Scaled Min-Sum: scaling_factor<1.0 (typically 0.7-0.9), offset=0.0 - Normalized Min-Sum: scaling_factor<1.0, offset>0.0 (e.g., 0.75, 0.2)

Parameters:

• encoder – The LDPC encoder instance providing code parameters

• bp_iters – Number of iterations to perform (default: 10)

• scaling_factor – Scaling factor to improve Min-Sum performance (default: 1.0)

• offset – Offset value for normalized Min-Sum variant (default: 0.0)

• normalized – If True, use optimized normalized parameters (default: False)

• return_soft – Whether to return soft outputs (default: False)

• device – Device for computation (default: “cpu”)

scaling_factor

Multiplicative scaling factor applied to check node outputs

offset

Additive offset for normalized Min-Sum variant

normalized

Whether using normalized variant parameters

Methods

__init__	Initialize the Min-Sum LDPC decoder.
calc_code_metrics	Calculate code metrics and prepare the Tanner graph representation.
compute_cv	Override parent's compute_cv to use Min-Sum algorithm.
compute_cv_minsum	Compute check-to-variable messages using Min-Sum algorithm.
compute_vc	Compute variable-to-check (VC) messages in the belief propagation algorithm.
forward	Decode received codewords using the Belief Propagation algorithm.
get_algorithm_info	Get information about the Min-Sum algorithm configuration.
marginalize	Compute marginal probabilities for each variable node.
prep_edge_ind	Prepare edge indices and map structures for the Tanner graph.

Attributes

code_dimension	Get the code dimension (k).
code_length	Get the code length (n).
code_rate	Get the code rate (k/n).
redundancy	Get the code redundancy (r = n - k).

__init__(encoder: LinearBlockCodeEncoder | LDPCCodeEncoder, bp_iters: int = 10, scaling_factor: float = 1.0, offset: float = 0.0, normalized: bool = False, return_soft: bool = False, device: str = 'cpu', *args: Any, **kwargs: Any)

Initialize the Min-Sum LDPC decoder.

Parameters:

• encoder – The LDPC encoder instance

• bp_iters – Number of iterations to perform

• scaling_factor – Scaling factor to improve performance (typically 0.7-0.9)

• offset – Offset value for normalized Min-Sum (typically 0.1-0.5)

• normalized – If True, use optimized normalized parameters (overrides scaling_factor and offset)

• return_soft – Whether to return soft outputs

• device – Device for computation

• *args – Additional positional arguments

• **kwargs – Additional keyword arguments

calc_code_metrics()

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.

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)

compute_vc(cv: Tensor, soft_input: Tensor) → Tensor

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]

forward(received: Tensor, *args: Any, **kwargs: Any) → Tensor | Tuple[Tensor, Tensor]

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

marginalize(cv: Tensor, soft_input: Tensor) → Tensor

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]

prep_edge_ind()

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

property redundancy: int

Get the code redundancy (r = n - k).

The redundancy represents the number of parity or check bits added to the information bits to enable error detection and correction.

Returns:

The redundancy of the code (number of parity bits)

compute_cv_minsum(vc: Tensor) → Tensor

Compute check-to-variable messages using Min-Sum algorithm.

The Min-Sum algorithm approximates the optimal sum-product check node operation with: 1. Sign computation: XOR of input signs 2. Magnitude computation: Minimum of input magnitudes 3. Optional scaling and offset for improved performance

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]

compute_cv(vc: Tensor) → Tensor

Override parent’s compute_cv to use Min-Sum algorithm.

get_algorithm_info() → dict

Get information about the Min-Sum algorithm configuration.

Returns:

Dictionary containing algorithm parameters and characteristics