Skip to content

komm.CyclicCode

General binary cyclic code. A cyclic code is a linear block code such that, if $c$ is a codeword, then every cyclic shift of $c$ is also a codeword. It 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). Those polynomials are related by $g(X) h(X) = X^n + 1$, where $n = k + m$ is the length of the code.

Examples of generator polynomials can be found in the table below.

Code $(n, k, d)$ Generator polynomial $g(X)$ Integer representation
Hamming $(7,4,3)$ $X^3 + X + 1$ 0b1011 = 0o13 = 11
Simplex $(7,3,4)$ $X^4 + X^2 + X + 1$ 0b10111 = 0o27 = 23
BCH $(15,5,7)$ $X^{10} + X^8 + X^5 + X^4 + X^2 + X + 1$ 0b10100110111 = 0o2467 = 1335
Golay $(23,12,7)$ $X^{11} + X^9 + X^7 + X^6 + X^5 + X + 1$ 0b101011100011 = 0o5343 = 2787

For more details, see LC04, Ch. 5.

The constructor expects either the generator polynomial or the check polynomial.

Parameters:

  • length –

    The length $n$ of the code.

  • generator_polynomial –

    The generator polynomial $g(X)$ of the code, of degree $m$ (the redundancy of the code), specified either as a binary polynomial or as an integer to be converted to the former.

  • check_polynomial –

    The check polynomial $h(X)$ of the code, of degree $k$ (the dimension of the code), specified either as a binary polynomial or as an integer to be converted to the former.

  • systematic –

    Whether the encoder is systematic. Default is True.

Examples:

>>> code = komm.CyclicCode(length=23, generator_polynomial=0b101011100011)  # Golay (23, 12)
>>> (code.length, code.dimension, code.redundancy)
(23, 12, 11)
>>> code.minimum_distance
7

>>> code = komm.CyclicCode(length=23, check_polynomial=0b1010010011111)  # Golay (23, 12)
>>> (code.length, code.dimension, code.redundancy)
(23, 12, 11)
>>> code.minimum_distance
7

meggitt_table: dict[BinaryPolynomial, BinaryPolynomial] cached property

The Meggitt table for the cyclic code. It is a dictionary where the keys are syndromes and the values are error patterns. See XiD03, Sec. 3.4.