kaira.models.fec.decoders.BruteForceMLDecoder
Inheritance diagram for BruteForceMLDecoder
- class kaira.models.fec.decoders.BruteForceMLDecoder(encoder: BaseBlockCodeEncoder, precompute_codebook: bool = True, *args: Any, **kwargs: Any)[source]
Bases:
BaseBlockDecoder[BaseBlockCodeEncoder]Brute Force Maximum Likelihood decoder for block codes.
This decoder implements a brute-force maximum likelihood approach by searching through all possible codewords to find the one that is closest to the received word in terms of Hamming distance. It is optimal in the sense that it performs maximum-likelihood decoding for symmetric channels [Proakis and Salehi, 2008], but becomes computationally infeasible for larger codes.
The brute force ML decoding principle is based on finding: argmin_{c ∈ C} d(r, c) where d(r, c) is the Hamming distance between the received word r and codeword c, and C is the set of all codewords in the code.
The decoder works by: 1. Generating all possible codewords (or using a precomputed codebook) 2. Computing the Hamming distance between the received word and each codeword 3. Selecting the codeword with the minimum distance (maximum likelihood) 4. Extracting the message bits from the selected codeword
- encoder
The encoder instance providing encoding functionality
- Type:
- _codebook
Precomputed tensor of all codewords with shape (2^k, n)
- Type:
- _message_map
Mapping from codeword indices to message bits with shape (2^k, k)
- Type:
- Parameters:
encoder (BaseBlockCodeEncoder) – The encoder for the code being decoded
precompute_codebook (bool) – Whether to precompute the entire codebook during initialization. Default is True, which is more efficient for multiple decoding operations but requires more memory.
*args – Variable positional arguments passed to the base class
**kwargs – Variable keyword arguments passed to the base class
Examples
>>> from kaira.models.fec.encoders import LinearBlockCodeEncoder >>> from kaira.models.fec.decoders import BruteForceMLDecoder >>> import torch >>> >>> # Create a simple (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 = BruteForceMLDecoder(encoder) >>> >>> # Encode a message >>> message = torch.tensor([1., 0., 1., 1.]) >>> codeword = encoder(message) >>> >>> # Introduce two bit errors >>> received = codeword.clone() >>> received[2] = 1 - received[2] >>> received[5] = 1 - received[5] >>> >>> # Decode using ML decoding >>> decoded = decoder(received) >>> print(torch.all(decoded == message)) True
Methods
Initialize the brute force ML decoder.
Decode received codewords using maximum likelihood decoding.
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: BaseBlockCodeEncoder, precompute_codebook: bool = True, *args: Any, **kwargs: Any)[source]
Initialize the brute force ML decoder.
Sets up the decoder with an encoder instance and optionally precomputes the complete codebook for more efficient decoding operations.
- Parameters:
encoder – The encoder instance for the code being decoded
precompute_codebook – Whether to generate all possible codewords during initialization (True) or on-demand (False)
*args – Variable positional arguments passed to the base class
**kwargs – Variable keyword arguments passed to the base class
Note
Precomputing the codebook requires O(2^k * n) memory, where k is the code dimension and n is the code length. This can be prohibitive for larger codes, so set precompute_codebook=False for such cases.
- 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 maximum likelihood decoding.
This method implements the complete maximum likelihood decoding process: 1. Compare the received word with every possible codeword 2. Find the codeword that minimizes the Hamming distance to the received word 3. Return the message bits corresponding to that codeword
This provides optimal decoding performance for the binary symmetric channel (BSC) in terms of minimizing the word error probability.
- 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 optimal (maximum likelihood) decoding for the binary symmetric channel at the cost of exponential complexity in the code dimension k. For larger codes, consider using more efficient decoders that may sacrifice some performance for computational tractability.