Reed-Muller Codes

Reed-Muller codes are a subtype of LinearCode and inherit its methods.

The binary family is generated from the recursive $(u \mid u + v)$ form of the generator matrix. Sources differ on the base case: if alt is true the identity is used as the generator matrix of $\mathcal{RM}(1, 1)$, and otherwise $\begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}$ is used.

CodingTheory.ReedMullerCode — Type
ReedMullerCode(r::Int64, m::Int64) -> ReedMullerCode
ReedMullerCode(
    r::Int64,
    m::Int64,
    alt::Bool
) -> ReedMullerCode

Return the $\mathcal{RM}(r, m)$ Reed-Muller code.

Notes

  • If alt is true, the identity is used for the generator matrix for $\mathcal{RM}(1, 1)$, as in common in some sources.

Otherwise, [1 1; 0 1] is used, as is common in other sources.

source
AbstractAlgebra.order — Method
order(C::ReedMullerCode) -> Int64

Return the order $r$ of the $\mathcal{RM}(r, m)$ Reed-Muller code C.

source
CodingTheory.RM_m — Method
RM_m(C::ReedMullerCode) -> Int64

Return the number of variables $m$ of the $\mathcal{RM}(r, m)$ Reed-Muller code C.

source
CodingTheory.RM_r — Method
RM_r(C::ReedMullerCode) -> Int64

Return the order $r$ of the $\mathcal{RM}(r, m)$ Reed-Muller code C. This is an alias for order.

source
CodingTheory.RandomBooleanFunction — Method
RandomBooleanFunction(r::Int64, m::Int64) -> Any

Return the truth table (as a vector) of a random Boolean function in m variables of algebraic degree at most r.

Notes

  • This is mathematically equivalent to returning a random codeword from RM(r, m).
source
CodingTheory.RandomPermutedReedMullerCode — Method
RandomPermutedReedMullerCode(
    r::Int64,
    m::Int64
) -> LinearCode

Return a random permuted Reed-Muller code RM(r, m).

Notes

  • Applies a random column permutation to the standard RM(r, m) generator matrix.
  • Used in cryptographic settings to hide the affine geometric structure of the code.
source
CodingTheory.RandomRMCoset — Method
RandomRMCoset(r::Int64, m::Int64) -> Any

Return a random coset representative of the RM(r, m) code.

Notes

  • When r = 1, the weight of the lowest-weight element in this coset defines the nonlinearity of the representative Boolean function.
source
Oscar.generator_matrix — Function
generator_matrix(C::ReedMullerCode) -> Any
generator_matrix(C::ReedMullerCode, stand_form::Bool) -> Any

Return the generator matrix of the Reed-Muller code. If stand_form is true, returns the standard form matrix.

source