kaira.models.fec.decoders.SyndromeLookupDecoder

Inheritance diagram for SyndromeLookupDecoder

class kaira.models.fec.decoders.SyndromeLookupDecoder(encoder: LinearBlockCodeEncoder, *args: Any, **kwargs: Any)

Bases: BaseBlockDecoder[LinearBlockCodeEncoder]

Syndrome lookup decoder for linear block codes.

This decoder implements syndrome-based hard-decision decoding using a precomputed table of coset leaders. It is efficient for small to medium sized codes but becomes impractical for larger codes due to the exponential growth of the syndrome table [Lin and Costello, 2004].

The standard array decoding approach provides maximum-likelihood decoding for binary symmetric channels when errors are equally likely in all positions. The decoder works by:

1. Calculating the syndrome of the received codeword: s = H·r^T

2. Looking up the most likely error pattern (coset leader) for that syndrome

3. Correcting the received word by XORing it with the error pattern: v = r + e

4. Extracting the message bits from the corrected codeword

encoder

The encoder instance providing code parameters and syndrome calculation functions

Type:

LinearBlockCodeEncoder

_syndrome_table

Lookup table mapping syndromes to their corresponding error patterns

Type:

Dict[int, torch.Tensor]

Parameters:

• encoder (LinearBlockCodeEncoder) – The encoder for the code being decoded

• *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

Examples

>>> from kaira.models.fec.encoders import LinearBlockCodeEncoder
>>> from kaira.models.fec.decoders import SyndromeLookupDecoder
>>> import torch
>>>
>>> # Create a (7,4) Hamming code encoder and decoder
>>> G = torch.tensor([
...     [1, 0, 0, 0, 1, 1, 0],
...     [0, 1, 0, 0, 1, 0, 1],
...     [0, 0, 1, 0, 0, 1, 1],
...     [0, 0, 0, 1, 1, 1, 1]
... ], dtype=torch.float)
>>> encoder = LinearBlockCodeEncoder(generator_matrix=G)
>>> decoder = SyndromeLookupDecoder(encoder)
>>>
>>> # Encode a message
>>> message = torch.tensor([1., 0., 1., 1.])
>>> codeword = encoder(message)
>>>
>>> # Introduce an error
>>> received = codeword.clone()
>>> received[2] = 1 - received[2]  # Flip a bit
>>>
>>> # Decode
>>> decoded = decoder(received)
>>> print(torch.all(decoded == message))
True

Methods

__init__	Initialize the syndrome lookup decoder.
forward	Decode received codewords using the syndrome lookup table.

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, *args: Any, **kwargs: Any)

Initialize the syndrome lookup decoder.

This constructor sets up the decoder and builds the syndrome lookup table, which maps each possible syndrome to its corresponding error pattern with minimum Hamming weight (coset leader).

Parameters:

• encoder – The encoder instance for the code being decoded

• *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

Note

For large codes, building the syndrome table can be computationally expensive, as it requires exploring a large space of error patterns. The table size is 2^r where r is the code’s redundancy.

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

Decode received codewords using the syndrome lookup table.

This method implements the complete syndrome-based decoding process: 1. Calculate the syndrome of the received word 2. Look up the corresponding error pattern in the syndrome table 3. Correct the received word by adding (XORing) the error pattern 4. Extract the message from the corrected codeword

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_errors: If True, also return the estimated error patterns

Returns:

• Decoded tensor containing estimated messages with shape (…, k) or (…, m*k)

• A tuple of (decoded tensor, error pattern tensor) if return_errors=True

Return type:

Either

Raises:

ValueError – If the last dimension of received is not a multiple of the code length

Note

This decoder provides maximum likelihood (ML) decoding for the binary symmetric channel (BSC) when all error patterns of the same weight are equally likely.

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)

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)