Miscellaneous Known Linear Codes

Well-known codes are programmed into the library for convenience. Their parameters are known analytically, so the minimum distance is set at construction rather than searched for.

CodingTheory.HammingCode — Method
HammingCode(q::Int64, r::Int64) -> HammingCode

Return the [(q^r - 1)/(q - 1), (q^r - 1)/(q - 1) - r, 3] Hamming code over GF(q).

source
CodingTheory.MacDonaldCode — Method
MacDonaldCode(q::Int64, k::Int64, u::Int64) -> MacDonaldCode

Return the [(q^k - q^u)/(q - 1), k, q^{k - 1} - q^{u - 1}] MacDonald code over GF(q).

Notes

  • MacDonald codes are the classic examples of two-weight codes.
  • They are constructed by taking a Simplex code of dimension k and removing the columns that correspond to a Simplex subcode of dimension u.
source
CodingTheory.SimplexCode — Method
SimplexCode(
    q::Int64,
    r::Int64
) -> Union{LinearCode, SimplexCode}

Return the [(q^r - 1)/(q - 1), r] simplex code over GF(q).

Notes

  • Generator matrices for the binary codes are constructed using the standard recursive definition.
  • The higher fields return dual(HammingCode(q, r)).
  • This is currently only implemented for binary codes.
source
CodingTheory.ExtendedGolayCode — Method
ExtendedGolayCode(p::Int64) -> LinearCode

Return the [24, 12, 8] extended binary Golay code if p == 2 or the [12, 6, 6] extended ternary Golay code if p == 3.

source
CodingTheory.ExtendedHammingCode — Method
ExtendedHammingCode(r::Int64) -> LinearCode

Return the [2^r, 2^r - 1 - r, 4] extended binary Hamming code.

Notes

  • Extended Hamming codes are formed by adding an overall parity-check bit to a binary Hamming code, creating a SEC-DED (Single Error Correction, Double Error Detection) code.
source
CodingTheory.GolayCode — Method
GolayCode(p::Int64) -> LinearCode

Return the [23, 12, 7] binary Golay code if p == 2 or the [11, 6, 5] ternary Golay code if p == 3.

source
CodingTheory.HadamardCode — Method
HadamardCode(m::Int64) -> LinearCode

Return the [2^m, m, 2^{m - 1}] binary Hadamard code.

Notes

  • Hadamard codes are generally constructed using Hadamard matrices H_n. When n is a power of two, the codes are linear. Constructing H_{2^m} then mapping +/- 1 to {0, 1} gives a generator matrix which, up to permutation, is equivalent to using all 2^m binary strings as column vectors. The construction here uses this latter definition.
  • Note that some engineering fields define the Hadamard code to be the [2^m, m + 1, 2^{m - 1}] augmented Hadamard code (equivalent to the first-order Reed-Muller code RM(1, m)).
source
CodingTheory.Lexicode — Method
Lexicode(n::Int64, d::Int64) -> LinearCode

Return the binary Lexicode of length n and minimum distance d.

Notes

  • Lexicodes are generated via a greedy algorithm. The algorithm iterates through all 2^n binary vectors in lexicographic order, adding a vector to the code if its Hamming distance to all currently selected vectors is at least d.
  • By the Conway-Sloane theorem, this greedy construction over GF(2) naturally produces a linear code.
source
CodingTheory.SPCCode — Method
SPCCode(q::Int64, n::Int64) -> LinearCode

Return the $[n, n - 1, 2]$ single parity-check code over $\operatorname{GF}(q)$. This is an alias for SingleParityCheckCode.

source
CodingTheory.TetraCode — Method
TetraCode() -> LinearCode

Return the [4, 2, 3] tetra code over GF(3).

Notes

  • This is equivalent to the Hamming(3, 2, 3) code, but the construction here is based on the commonly presented generator and parity-check matrices.
source
CodingTheory.WalshCode — Method
WalshCode(m::Int64) -> LinearCode

Return the $[2^m, m, 2^{m - 1}]$ binary Hadamard code. This is an alias for HadamardCode and WalshHadamardCode.

source
CodingTheory.ZeroCode — Method
ZeroCode(
    F::AbstractAlgebra.FinField,
    n::Integer
) -> LinearCode

Return the [n, 0, 0] zero code over F.

source
CodingTheory.best_known_linear_code — Method
best_known_linear_code(n::Int64, k::Int64) -> Any

Return the best known linear code of length n and dimension k over GF(2) using the internal GAP database.

source