komm.ReedMullerCode

Reed–Muller code. Let $\mu$ and $\rho$ be two integers such that $0 \leq \rho < \mu$. The Reed–Muller code with parameters $(\rho, \mu)$ is the linear block code whose generator matrix rows are $$ \mathbf{1}, \, v_1, \ldots, v_m, \, v_1 v_2, v_1 v_3, \ldots, v_{\mu} v_{\mu - 1}, \, \ldots \, \text{(up to products of degree $\rho$)}, $$ where $\mathbf{1}$ is the all-one $2^\mu$-tuple, $v_i$ is the binary $2^\mu$-tuple composed of $2^{\mu-i}$ repetitions of alternating blocks of zeros and ones, each block of length $2^i$, for $1 \leq i \leq \mu$, and $v_i v_j$ denotes the component-wise product (logical AND) of $v_i$ and $v_j$. Here we take the rows in reverse order. The resulting code has the following parameters:

• Length: $n = 2^{\mu}$
• Dimension: $k = 1 + {\mu \choose 1} + \cdots + {\mu \choose \rho}$
• Redundancy: $m = 1 + {\mu \choose 1} + \cdots + {\mu \choose \mu - \rho - 1}$
• Minimum distance: $d = 2^{\mu - \rho}$

For more details, see LC04, Sec. 4.3.

Notes

• For $\rho = 0$ it reduces to a repetition code.
• For $\rho = 1$ it reduces to a lengthened simplex code.
• For $\rho = \mu - 2$ it reduces to an extended Hamming code.
• For $\rho = \mu - 1$ it reduces to a single parity-check code.

Parameters:

• rho (int) –

  The parameter $\rho$ of the code.

• mu (int) –

  The parameter $\mu$ of the code.

Examples:

>>> code = komm.ReedMullerCode(2, 4)
>>> (code.length, code.dimension, code.redundancy)
(16, 11, 5)
>>> code.generator_matrix
array([[0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
       [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
       [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
       [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])
>>> code.minimum_distance()
4

reed_partitions() cached

The Reed partitions of the code. See LC04, Sec. 4.3.

Examples:

>>> code = komm.ReedMullerCode(2, 4)
>>> reed_partitions = code.reed_partitions()
>>> reed_partitions[1]
array([[ 0,  1,  4,  5],
       [ 2,  3,  6,  7],
       [ 8,  9, 12, 13],
       [10, 11, 14, 15]])
>>> reed_partitions[8]
array([[ 0,  4],
       [ 1,  5],
       [ 2,  6],
       [ 3,  7],
       [ 8, 12],
       [ 9, 13],
       [10, 14],
       [11, 15]])