kaira.models.fec.encoders.CyclicCodeEncoder

Inheritance diagram for CyclicCodeEncoder

class kaira.models.fec.encoders.CyclicCodeEncoder(code_length: int, generator_polynomial: int | None = None, check_polynomial: int | None = None, information_set: List[int] | Tensor | str = 'left', **kwargs: Any)

Bases: SystematicLinearBlockCodeEncoder

Encoder for cyclic codes.

A cyclic code is a linear block code with the additional property that any cyclic shift of a codeword is also a codeword. A cyclic code is characterized by its generator polynomial g(X) of degree m (the redundancy of the code), and by its check polynomial h(X) of degree k (the dimension of the code). These polynomials are related by g(X)h(X) = X^n + 1, where n = k + m is the length of the code.

Currently, the implementation only supports systematic encoding, where the first k bits of the codeword are the information bits, and the last m bits are the parity bits.

Examples of generator polynomials for common codes:

Code (n, k, d) | Generator polynomial g(X) | Integer representation |

—————– | ————————————– | ——————————- |

Hamming (7,4,3) | X^3 + X + 1 | 0b1011 = 11 |

Simplex (7,3,4) | X^4 + X^2 + X + 1 | 0b10111 = 23 |

BCH (15,5,7) | X^10 + X^8 + X^5 + X^4 + X^2 + X + 1 | 0b10100110111 = 1335 |

Golay (23,12,7) | X^11 + X^9 + X^7 + X^6 + X^5 + X + 1 | 0b101011100011 = 2787 |

For more details, see [Lin and Costello, 2004, Moon, 2005].

Parameters:

• code_length (int) – The length n of the code

• generator_polynomial (int, optional) – The generator polynomial g(X) of the code

• check_polynomial (int, optional) – The check polynomial h(X) of the code

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

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

Examples

>>> encoder = CyclicCodeEncoder(code_length=23, generator_polynomial=0b101011100011)  # Golay (23, 12)
>>> encoder.code_length, encoder.code_dimension, encoder.redundancy
(23, 12, 11)
>>> encoder.generator_poly
BinaryPolynomial(0b101011100011)

Methods

__init__	Initialize the cyclic code encoder.
calculate_syndrome	Calculate the syndrome of a received word.
create_standard_code	Create a standard cyclic 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.
inverse_encode	Decode the input tensor using the generator matrix right inverse.
minimum_distance	Calculate 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).
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.
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__(code_length: int, generator_polynomial: int | None = None, check_polynomial: int | None = None, information_set: List[int] | Tensor | str = 'left', **kwargs: Any)

Initialize the cyclic code encoder.

Parameters:

• code_length – The length n of the code

• generator_polynomial – The generator polynomial g(X) of the code, specified as an integer

• check_polynomial – The check polynomial h(X) of the code, specified as an integer

• 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’.

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

Raises:

ValueError – If neither generator_polynomial nor check_polynomial is provided, or if the provided polynomial is not a factor of X^n + 1.

property generator_poly: BinaryPolynomial

Generator polynomial g(X) of the code.

property check_poly: BinaryPolynomial

Check polynomial h(X) of the code.

property modulus_poly: BinaryPolynomial

Modulus polynomial X^n + 1 of the code.

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_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)

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 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)

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

Create a standard cyclic code by name.

Parameters:

• name – Name of the standard code from the list of standard codes.

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

Returns:

A cyclic code encoder for the requested standard code.

Raises:

ValueError – If the requested code is not recognized.

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.

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

minimum_distance() → int

Calculate the minimum distance of the code.

For cyclic codes, the minimum distance is the minimum weight of any non-zero codeword. This implements an optimized approach for small to medium-sized codes.

Returns:

The minimum distance of the code