kaira.models.fec.encoders.BCHCodeEncoder

Inheritance diagram for BCHCodeEncoder

class kaira.models.fec.encoders.BCHCodeEncoder(mu: int, delta: int, information_set: List[int] | Tensor | str = 'left', dtype: dtype = torch.float32, **kwargs: Any)

Bases: CyclicCodeEncoder

Encoder for BCH (Bose–Chaudhuri–Hocquenghem) codes.

BCH codes are a class of powerful cyclic error-correcting codes that can be designed to correct multiple errors. They are constructed using polynomials over finite fields and provide great flexibility in the trade-off between redundancy and error-correcting capability [Lin and Costello, 2004, Richardson and Urbanke, 2008].

For given parameters μ ≥ 2 and δ satisfying 2 ≤ δ ≤ 2^μ - 1, a binary BCH code has the following parameters, where δ = 2τ + 1:

• Length: n = 2^μ - 1

• Dimension: k ≥ n - μτ

• Redundancy: m ≤ μτ

• Minimum distance: d ≥ δ

This implementation handles narrow-sense, primitive BCH codes [Lin and Costello, 2004, Moon, 2005, Sklar, 2001].

Parameters:

• mu (int) – The parameter μ of the code. Must satisfy μ ≥ 2.

• delta (int) – The design distance δ of the code. Must satisfy 2 ≤ δ ≤ 2^μ - 1 and be a valid Bose distance.

• information_set (Union[List[int], torch.Tensor, str], optional) – Information set specification. Default is “left”.

• dtype (torch.dtype, optional) – Data type for internal tensors. Default is torch.float32.

• **kwargs – Additional keyword arguments passed to the parent class.

Examples

>>> encoder = BCHCodeEncoder(mu=4, delta=5)
>>> print(f"Length: {encoder.length, Dimension: {encoder.dimension}, Redundancy: {encoder.redundancy}")
Length: 15, Dimension: 7, Redundancy: 8
>>> message = torch.tensor([1., 0., 1., 1., 0., 1., 0.])
>>> codeword = encoder(message)
>>> print(codeword)
tensor([1., 0., 1., 1., 0., 1., 0., 1., 0., 0., 1., 1., 0., 0., 1.])

Methods

__init__	Initialize the BCH code encoder.
calculate_syndrome	Calculate the syndrome of a received word.
calculate_syndrome_polynomial	Calculate the syndrome polynomial for a received word.
create_standard_code	Create a standard BCH code by name.
encode_message_polynomial	Encode a message polynomial into a codeword polynomial using systematic encoding.
extract_message	Extract the message bits from a codeword.
extract_message_polynomial	Extract a message polynomial from a codeword polynomial.
forward	Encode the input tensor using polynomial encoding.
from_design_rate	Create a BCH code with a design rate close to the target rate.
get_standard_codes	Get a dictionary of standard BCH codes with their parameters.
inverse_encode	Decode the input tensor using the generator matrix right inverse.
minimum_distance	Get the minimum distance of the code.
project_word	Project a codeword onto the information set.

Attributes

check_poly	Check polynomial h(X) of the code.
code_dimension	Get the code dimension (k).
code_length	Get the codeword length (n).
code_rate	Get the rate of the code (k/n).
delta	Design distance δ of the code.
error_correction_capability	Error correction capability of the code (t = ⌊(δ-1)/2⌋).
generator_poly	Generator polynomial g(X) of the code.
information_set	Either indices of information positions, which must be a k-sublist of [0...n), or one of the strings 'left' or 'right'.
modulus_poly	Modulus polynomial X^n + 1 of the code.
mu	Parameter μ of the code.
parity_bits	Get the number of parity bits (synonym for redundancy).
parity_check_matrix	Get the check matrix H of the code.
parity_set	Parity set M of the code.
parity_submatrix	Parity submatrix P of the code.
redundancy	Get the code redundancy (r = n - k).

__init__(mu: int, delta: int, information_set: List[int] | Tensor | str = 'left', dtype: dtype = torch.float32, **kwargs: Any)

Initialize the BCH code encoder.

Parameters:

• mu – The parameter μ of the code. Must satisfy μ ≥ 2.

• delta – The design distance δ of the code. Must satisfy 2 ≤ δ ≤ 2^μ - 1 and be a valid Bose distance.

• information_set – Either indices of information positions, which must be a k-sublist of [0…n), or one of the strings ‘left’ or ‘right’. Default is ‘left’.

• dtype – Data type for internal tensors. Default is torch.float32.

• **kwargs – Additional keyword arguments passed to the parent class.

Raises:

ValueError – If μ < 2 or if δ is not a valid Bose distance.

property mu: int

Parameter μ of the code.

property delta: int

Design distance δ of the code.

property error_correction_capability: int

Error correction capability of the code (t = ⌊(δ-1)/2⌋).

minimum_distance() → int

Get the minimum distance of the code.

For BCH codes, the minimum distance is at least the design distance.

Returns:

The minimum distance of the code, which is at least δ.

classmethod from_design_rate(mu: int, target_rate: float, **kwargs: Any) → BCHCodeEncoder

Create a BCH code with a design rate close to the target rate.

Parameters:

• mu – The parameter μ of the BCH code.

• target_rate – The target rate (k/n) of the code.

• **kwargs – Additional arguments passed to the constructor.

Returns:

A BCH code encoder with rate close to the target rate.

Raises:

ValueError – If no suitable code can be found.

classmethod get_standard_codes() → Dict[str, Dict[str, Any]]

Get a dictionary of standard BCH codes with their parameters.

Returns:

Dictionary mapping code names to their parameters.

classmethod create_standard_code(name: str, **kwargs: Any) → BCHCodeEncoder

Create a standard BCH code by name.

Parameters:

• name – Name of the standard code from get_standard_codes().

• **kwargs – Additional arguments passed to the constructor.

Returns:

A BCH code encoder for the requested standard code.

Raises:

ValueError – If the requested code is not recognized.

calculate_syndrome_polynomial(received: List[Any]) → List[Any]

Calculate the syndrome polynomial for a received word.

This method computes the syndrome polynomial S(x) for a received codeword by evaluating the received polynomial at powers of alpha, which are the roots of the generator polynomial.

Parameters:

received – List of field elements representing the received word

Returns:

List of syndrome values in the field, S = [S_0, S_1, …, S_{2t-1}]

calculate_syndrome(x: Tensor) → Tensor

Calculate the syndrome of a received word.

The syndrome is computed as s = xH^T and is used to detect errors. A non-zero syndrome indicates the presence of errors [Lin and Costello, 2004, Moon, 2005]. This approach is a fundamental technique in error detection and correction for linear block codes [Sklar, 2001].

Parameters:

x – Received word tensor of shape (…, codeword_length) or (…, b*codeword_length) where b is a positive integer.

Returns:

Syndrome tensor of shape (…, redundancy) or (…, b*redundancy)

property check_poly: BinaryPolynomial

Check polynomial h(X) of the code.

property code_dimension: int

Get the code dimension (k).

Returns:

The number of information bits encoded in each codeword

property code_length: int

Get the codeword length (n).

Returns:

The number of bits in each codeword after encoding

property code_rate: float

Get the rate of the code (k/n).

The code rate is a measure of efficiency, representing the proportion of the total bits that carry information (as opposed to redundancy).

Returns:

The ratio of information bits to total bits (between 0 and 1)

encode_message_polynomial(message_poly: BinaryPolynomial) → BinaryPolynomial

Encode a message polynomial into a codeword polynomial using systematic encoding.

Parameters:

message_poly – The message polynomial to encode

Returns:

The systematically encoded codeword polynomial

extract_message(codeword: Tensor) → Tensor

Extract the message bits from a codeword.

By default, this calls inverse_encode and returns just the decoded message. Subclasses can override this method to provide more efficient implementations.

Parameters:

codeword – Codeword tensor with shape (…, n) where n is the code length

Returns:

Extracted message tensor with shape (…, k) where k is the code dimension

Note

This implementation assumes the inverse_encode method can handle a single codeword correctly. Specific code types may override this with more efficient implementations.

extract_message_polynomial(codeword_poly: BinaryPolynomial) → BinaryPolynomial

Extract a message polynomial from a codeword polynomial.

Parameters:

codeword_poly – The codeword polynomial to extract from

Returns:

The message polynomial

forward(x: Tensor, *args: Any, **kwargs: Any) → Tensor

Encode the input tensor using polynomial encoding.

For cyclic codes, encoding can be done using polynomial operations. This implementation delegates to the parent class for efficiency.

Parameters:

• x – The input tensor of shape (…, message_length) or (…, b*message_length) where b is a positive integer.

• *args – Additional positional arguments (unused).

• **kwargs – Additional keyword arguments (unused).

Returns:

Encoded tensor of shape (…, codeword_length) or (…, b*codeword_length)

property generator_poly: BinaryPolynomial

Generator polynomial g(X) of the code.

property information_set: Tensor

Either indices of information positions, which must be a k-sublist of [0…n), or one of the strings ‘left’ or ‘right’.

Default is ‘left’.

inverse_encode(x: Tensor, *args: Any, **kwargs: Any) → Tuple[Tensor, Tensor]

Decode the input tensor using the generator matrix right inverse.

This method takes one or more sequences of codewords and returns their corresponding decoded messages along with syndromes. The decoding approach follows standard techniques in error control coding literature [Lin and Costello, 2004, Sklar, 2001].

Parameters:

• x – The input tensor. Can be either a single sequence whose length is a multiple of n, or a multidimensional tensor where the last dimension is a multiple of n.

• *args – Additional positional arguments (unused).

• **kwargs – Additional keyword arguments (unused).

Returns:

• Decoded tensor of shape (…, b*k). Has the same shape as the input, with the last dimension reduced from b*n to b*k, where b is a positive integer.

• Syndrome tensor for error detection of shape (…, b*r), where r is the redundancy.

Return type:

Tuple containing

Raises:

ValueError – If the last dimension of the input is not a multiple of n.

property modulus_poly: BinaryPolynomial

Modulus polynomial X^n + 1 of the code.

property parity_bits: int

Get the number of parity bits (synonym for redundancy).

Returns:

The number of parity/check bits in each codeword

property parity_check_matrix: Tensor

Get the check matrix H of the code.

The check matrix H satisfies the property: GH^T = 0

Returns:

The check matrix H of the code

property parity_set: Tensor

Parity set M of the code.

property parity_submatrix: Tensor

Parity submatrix P of the code.

project_word(x: Tensor) → Tensor

Project a codeword onto the information set.

This extracts the information bits directly from a codeword without decoding, which is a key advantage of systematic codes.

Parameters:

x – Input tensor of shape (…, codeword_length) or (…, b*codeword_length) where b is a positive integer.

Returns:

Projected tensor of shape (…, message_length) or (…, b*message_length)

Raises:

ValueError – If the last dimension of the input is not a multiple of n.

property redundancy: int

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

Returns:

The number of redundant bits added during encoding