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 and McE04, Ch. 8.
The constructor expects either the generator polynomial or the check polynomial.
Parameters:
-
length(int) –The length $n$ of the code.
-
generator_polynomial(SupportsInt | None) –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(SupportsInt | None) –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(bool) –Whether the encoder is systematic. Default is
True.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> (code.length, code.dimension, code.redundancy)
(7, 4, 3)
>>> code = komm.CyclicCode(length=7, check_polynomial=0b10111)
>>> (code.length, code.dimension, code.redundancy)
(7, 4, 3)
length int
cached
property
The length $n$ of the code.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.length
7
dimension int
cached
property
The dimension $k$ of the code.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.dimension
4
redundancy int
cached
property
The redundancy $m$ of the code.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.redundancy
3
rate float
cached
property
The rate $R = k/n$ of the code.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.rate
0.5714285714285714
generator_matrix Array2D[integer]
cached
property
The generator matrix $G \in \mathbb{B}^{k \times n}$ of the code.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.generator_matrix
array([[1, 1, 0, 1, 0, 0, 0],
[0, 1, 1, 0, 1, 0, 0],
[1, 1, 1, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 0, 1]])
check_matrix Array2D[integer]
cached
property
The check matrix $H \in \mathbb{B}^{m \times n}$ of the code.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.check_matrix
array([[1, 0, 0, 1, 0, 1, 1],
[0, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 1, 1]])
encode()
Applies the encoding mapping $\Enc : \mathbb{B}^k \to \mathbb{B}^n$ of the code. This method takes one or more sequences of messages and returns their corresponding codeword sequences.
Parameters:
-
input(ArrayLike) –The input sequence(s). Can be either a single sequence whose length is a multiple of $k$, or a multidimensional array where the last dimension is a multiple of $k$.
Returns:
-
output(NDArray[integer]) –The output sequence(s). Has the same shape as the input, with the last dimension expanded from $bk$ to $bn$, where $b$ is a positive integer.
Examples:
See BlockCode.encode for examples.
inverse_encode()
Applies the inverse encoding partial mapping $\Enc^{-1} : \mathbb{B}^n \rightharpoonup \mathbb{B}^k$ of the code. This method takes one or more sequences of codewords and returns their corresponding message sequences.
Parameters:
-
input(ArrayLike) –The input sequence(s). Can be either a single sequence whose length is a multiple of $n$, or a multidimensional array where the last dimension is a multiple of $n$.
Returns:
-
output(NDArray[integer]) –The output sequence(s). Has the same shape as the input, with the last dimension contracted from $bn$ to $bk$, where $b$ is a positive integer.
Raises:
-
ValueError–If the input contains any invalid codewords.
Examples:
See BlockCode.inverse_encode for examples.
check()
Applies the check mapping $\mathrm{Chk} : \mathbb{B}^n \to \mathbb{B}^m$ of the code. This method takes one or more sequences of received words and returns their corresponding syndrome sequences.
Parameters:
-
input(ArrayLike) –The input sequence(s). Can be either a single sequence whose length is a multiple of $n$, or a multidimensional array where the last dimension is a multiple of $n$.
Returns:
-
output(NDArray[integer]) –The output sequence(s). Has the same shape as the input, with the last dimension contracted from $bn$ to $bm$, where $b$ is a positive integer.
Examples:
See BlockCode.check for examples.
codewords()
cached
Returns the codewords of the code. This is a $2^k \times n$ matrix whose rows are all the codewords. The codeword in row $i$ corresponds to the message obtained by expressing $i$ in binary with $k$ bits (MSB in the right).
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.codewords()
array([[0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 1, 0, 0, 0],
[0, 1, 1, 0, 1, 0, 0],
[1, 0, 1, 1, 1, 0, 0],
[1, 1, 1, 0, 0, 1, 0],
[0, 0, 1, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 1, 0],
[0, 1, 0, 1, 1, 1, 0],
[1, 0, 1, 0, 0, 0, 1],
[0, 1, 1, 1, 0, 0, 1],
[1, 1, 0, 0, 1, 0, 1],
[0, 0, 0, 1, 1, 0, 1],
[0, 1, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 1, 1],
[0, 0, 1, 0, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1]])
codeword_weight_distribution()
cached
Returns the codeword weight distribution of the code. This is an array of shape $(n + 1)$ in which element in position $w$ is equal to the number of codewords of Hamming weight $w$, for $w \in [0 : n]$.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.codeword_weight_distribution()
array([1, 0, 0, 7, 7, 0, 0, 1])
minimum_distance()
cached
Returns the minimum distance $d$ of the code. This is equal to the minimum Hamming weight of the non-zero codewords.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.minimum_distance()
3
coset_leaders()
cached
Returns the coset leaders of the code. This is a $2^m \times n$ matrix whose rows are all the coset leaders. The coset leader in row $i$ corresponds to the syndrome obtained by expressing $i$ in binary with $m$ bits (MSB in the right), and whose Hamming weight is minimal. This may be used as a LUT for syndrome-based decoding.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.coset_leaders()
array([[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 0]])
coset_leader_weight_distribution()
cached
Returns the coset leader weight distribution of the code. This is an array of shape $(n + 1)$ in which element in position $w$ is equal to the number of coset leaders of weight $w$, for $w \in [0 : n]$.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.coset_leader_weight_distribution()
array([1, 7, 0, 0, 0, 0, 0, 0])
packing_radius()
cached
Returns the packing radius of the code. This is also called the error-correcting capability of the code, and is equal to $\lfloor (d - 1) / 2 \rfloor$.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.packing_radius()
1
covering_radius()
cached
Returns the covering radius of the code. This is equal to the maximum Hamming weight of the coset leaders.
Examples:
>>> code = komm.CyclicCode(length=7, generator_polynomial=0b1011)
>>> code.covering_radius()
1