kaira.models.fec.decoders.BerlekampMasseyDecoder
Inheritance diagram for BerlekampMasseyDecoder
- class kaira.models.fec.decoders.BerlekampMasseyDecoder(encoder: BCHCodeEncoder | ReedSolomonCodeEncoder, *args: Any, **kwargs: Any)[source]
Bases:
BaseBlockDecoder[BCHCodeEncoder|ReedSolomonCodeEncoder]Berlekamp-Massey decoder for BCH and Reed-Solomon codes.
This decoder implements the Berlekamp-Massey algorithm for decoding BCH and Reed-Solomon codes. It is particularly efficient for these algebraic codes and can correct up to t = ⌊(d-1)/2⌋ errors, where d is the minimum distance of the code [Berlekamp, 1968, Lin and Costello, 2004].
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. Computing the syndrome polynomial from the received word 2. Using the Berlekamp-Massey algorithm to find the error locator polynomial 3. Finding the roots of the error locator polynomial to determine error locations 4. Correcting the errors in the received word 5. Extracting the message bits from the corrected codeword
- encoder
The encoder instance providing code parameters and syndrome calculation methods
- Type:
Union[BCHCodeEncoder, ReedSolomonCodeEncoder]
- field
The finite field used by the code for algebraic operations
- Type:
GaloisField
- Parameters:
encoder (Union[BCHCodeEncoder, ReedSolomonCodeEncoder]) – 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 BCHCodeEncoder or ReedSolomonCodeEncoder
Examples
>>> from kaira.models.fec.encoders import BCHCodeEncoder >>> from kaira.models.fec.decoders import BerlekampMasseyDecoder >>> import torch >>> >>> # Create an encoder for a BCH(15,7) code >>> encoder = BCHCodeEncoder(mu=4, delta=5) >>> decoder = BerlekampMasseyDecoder(encoder) >>> >>> # Encode a message >>> message = torch.tensor([1., 0., 1., 1., 0., 1., 0.]) >>> codeword = encoder(message) >>> >>> # Introduce some errors >>> received = codeword.clone() >>> received[2] = 1 - received[2] # Flip a bit >>> received[8] = 1 - received[8] # Flip another bit >>> >>> # Decode and check if recovered correctly >>> decoded = decoder(received) >>> print(torch.all(decoded == message)) True
Methods
Initialize the Berlekamp-Massey decoder.
Implement the Berlekamp-Massey algorithm to find the error locator polynomial.
Decode received codewords using the Berlekamp-Massey algorithm.
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: BCHCodeEncoder | ReedSolomonCodeEncoder, *args: Any, **kwargs: Any)[source]
Initialize the Berlekamp-Massey decoder.
Sets up the decoder with an encoder instance and extracts relevant parameters needed for the decoding process, such as the finite field and error correction capability.
- 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 BCHCodeEncoder or ReedSolomonCodeEncoder
- berlekamp_massey_algorithm(syndrome: List[Any]) List[Any][source]
Implement the Berlekamp-Massey algorithm to find the error locator polynomial.
This algorithm iteratively determines the minimal LFSR (Linear Feedback Shift Register) that can generate the syndrome sequence. The connection polynomial of this LFSR corresponds to the error locator polynomial, whose roots identify error positions.
The algorithm maintains two key polynomials: - sigma: The current error locator polynomial - discrepancy: Measure of how well the current polynomial fits the syndrome
At each iteration, it updates these polynomials based on the discrepancy value.
- Parameters:
syndrome – List of syndrome values in the Galois field, representing the syndrome polynomial coefficients S(x)
- Returns:
Coefficients of the error locator polynomial sigma(x)
- forward(received: Tensor, *args: Any, **kwargs: Any) Tensor | Tuple[Tensor, Tensor][source]
Decode received codewords using the Berlekamp-Massey algorithm.
This method implements the complete decoding process for BCH and Reed-Solomon codes: 1. Calculate the syndrome of the received word 2. If syndrome is zero, no errors occurred, so return the message directly 3. Otherwise, use the Berlekamp-Massey algorithm to find the error locator polynomial 4. Find the roots of this polynomial to determine error locations 5. Correct the errors and extract the message
- 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
The decoder can correct up to t errors per codeword, where t is the error correction capability of the code. If more errors occur, the decoding may fail.
- 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)