# Linear code constructors that do not preserve the structural information#

This file contains a variety of constructions which builds the generator matrix of special (or random) linear codes and wraps them in a sage.coding.linear_code.LinearCode object. These constructions are therefore not rich objects such as sage.coding.grs_code.GeneralizedReedSolomonCode.

All codes available here can be accessed through the codes object:

sage: codes.random_linear_code(GF(2), 5, 2)
[5, 2]  linear code over GF(2)


REFERENCES:

AUTHORS:

• David Joyner (2007-05): initial version

• David Joyner (2008-02): added cyclic codes, Hamming codes

• David Joyner (2008-03): added BCH code, LinearCodeFromCheckmatrix, ReedSolomonCode, WalshCode, DuadicCodeEvenPair, DuadicCodeOddPair, QR codes (even and odd)

• David Joyner (2008-09) fix for bug in BCHCode reported by F. Voloch

• David Joyner (2008-10) small docstring changes to WalshCode and walsh_matrix

Constructs the “even pair” of duadic codes associated to the “splitting” (see the docstring for _is_a_splitting for the definition) S1, S2 of n.

Warning

Maybe the splitting should be associated to a sum of q-cyclotomic cosets mod n, where q is a prime.

EXAMPLES:

sage: from sage.coding.code_constructions import _is_a_splitting
sage: n = 11; q = 3
sage: C = Zmod(n).cyclotomic_cosets(q); C
[, [1, 3, 4, 5, 9], [2, 6, 7, 8, 10]]
sage: S1 = C
sage: S2 = C
sage: _is_a_splitting(S1,S2,11)
True
([11, 5] Cyclic Code over GF(3),
[11, 5] Cyclic Code over GF(3))


Constructs the “odd pair” of duadic codes associated to the “splitting” S1, S2 of n.

Warning

Maybe the splitting should be associated to a sum of q-cyclotomic cosets mod n, where q is a prime.

EXAMPLES:

sage: from sage.coding.code_constructions import _is_a_splitting
sage: n = 11; q = 3
sage: C = Zmod(n).cyclotomic_cosets(q); C
[, [1, 3, 4, 5, 9], [2, 6, 7, 8, 10]]
sage: S1 = C
sage: S2 = C
sage: _is_a_splitting(S1,S2,11)
True
([11, 6] Cyclic Code over GF(3),
[11, 6] Cyclic Code over GF(3))


This is consistent with Theorem 6.1.3 in [HP2003].

The extended quadratic residue code (or XQR code) is obtained from a QR code by adding a check bit to the last coordinate. (These codes have very remarkable properties such as large automorphism groups and duality properties - see [HP2003], Section 6.6.3-6.6.4.)

INPUT:

• n – an odd prime

• F – a finite prime field whose order must be a quadratic residue modulo $$n$$.

OUTPUT: Returns an extended quadratic residue code.

EXAMPLES:

sage: C1 = codes.QuadraticResidueCode(7, GF(2))
sage: C2 = C1.extended_code()
sage: C3 = codes.ExtendedQuadraticResidueCode(7, GF(2)); C3
Extension of [7, 4] Cyclic Code over GF(2)
sage: C2 == C3
True
sage: C
Extension of [17, 9] Cyclic Code over GF(2)
sage: C3x = C3.extended_code()
sage: C3x == C4
True


AUTHORS:

• David Joyner (07-2006)

A quadratic residue code (or QR code) is a cyclic code whose generator polynomial is the product of the polynomials $$x-\alpha^i$$ ($$\alpha$$ is a primitive $$n$$’th root of unity; $$i$$ ranges over the set of quadratic residues modulo $$n$$).

See QuadraticResidueCodeEvenPair and QuadraticResidueCodeOddPair for a more general construction.

INPUT:

• n – an odd prime

• F – a finite prime field whose order must be a quadratic residue modulo $$n$$.

OUTPUT: Returns a quadratic residue code.

EXAMPLES:

sage: C = codes.QuadraticResidueCode(7, GF(2))
sage: C
[7, 4] Cyclic Code over GF(2)
sage: C
[17, 9] Cyclic Code over GF(2)
sage: C1 == C2
True
sage: C1 == C2
True


AUTHORS:

• David Joyner (11-2005)

Quadratic residue codes of a given odd prime length and base ring either don’t exist at all or occur as 4-tuples - a pair of “odd-like” codes and a pair of “even-like” codes. If $$n > 2$$ is prime then (Theorem 6.6.2 in [HP2003]) a QR code exists over $$\GF{q}$$ iff q is a quadratic residue mod $$n$$.

They are constructed as “even-like” duadic codes associated the splitting $$(Q,N)$$ mod $$n$$, where $$Q$$ is the set of non-zero quadratic residues and $$N$$ is the non-residues.

EXAMPLES:

sage: codes.QuadraticResidueCodeEvenPair(17, GF(13))  # known bug (#25896)
([17, 8] Cyclic Code over GF(13),
[17, 8] Cyclic Code over GF(13))
([17, 8] Cyclic Code over GF(2),
[17, 8] Cyclic Code over GF(2))
sage: codes.QuadraticResidueCodeEvenPair(13, GF(9,"z"))  # known bug (#25896)
([13, 6] Cyclic Code over GF(9),
[13, 6] Cyclic Code over GF(9))
sage: C1.is_self_orthogonal()
True
sage: C2.is_self_orthogonal()
True
sage: C3.systematic_generator_matrix() == C4.dual_code().systematic_generator_matrix()
True


This is consistent with Theorem 6.6.9 and Exercise 365 in [HP2003].

Quadratic residue codes of a given odd prime length and base ring either don’t exist at all or occur as 4-tuples - a pair of “odd-like” codes and a pair of “even-like” codes. If n 2 is prime then (Theorem 6.6.2 in [HP2003]) a QR code exists over $$\GF{q} iff q$$ is a quadratic residue mod $$n$$.

They are constructed as “odd-like” duadic codes associated the splitting $$(Q,N)$$ mod $$n$$, where $$Q$$ is the set of non-zero quadratic residues and $$N$$ is the non-residues.

EXAMPLES:

sage: codes.QuadraticResidueCodeOddPair(17, GF(13))  # known bug (#25896)
([17, 9] Cyclic Code over GF(13),
[17, 9] Cyclic Code over GF(13))
([17, 9] Cyclic Code over GF(2),
[17, 9] Cyclic Code over GF(2))
sage: codes.QuadraticResidueCodeOddPair(13, GF(9,"z"))  # known bug (#25896)
([13, 7] Cyclic Code over GF(9),
[13, 7] Cyclic Code over GF(9))
sage: C1x = C1.extended_code()
sage: C2x = C2.extended_code()
sage: C2x.spectrum(); C1x.spectrum()
[1, 0, 0, 0, 0, 0, 102, 0, 153, 0, 153, 0, 102, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 102, 0, 153, 0, 153, 0, 102, 0, 0, 0, 0, 0, 1]
sage: C3x = C3.extended_code()
sage: C3x.spectrum()
[1, 0, 0, 0, 14, 0, 0, 0, 1]


This is consistent with Theorem 6.6.14 in [HP2003].

sage.coding.code_constructions.ToricCode(P, F)#

Let $$P$$ denote a list of lattice points in $$\ZZ^d$$ and let $$T$$ denote the set of all points in $$(F^x)^d$$ (ordered in some fixed way). Put $$n=|T|$$ and let $$k$$ denote the dimension of the vector space of functions $$V = \mathrm{Span}\{x^e \ |\ e \in P\}$$. The associated toric code $$C$$ is the evaluation code which is the image of the evaluation map

$\operatorname{eval}_T : V \rightarrow F^n,$

where $$x^e$$ is the multi-index notation ($$x=(x_1,...,x_d)$$, $$e=(e_1,...,e_d)$$, and $$x^e = x_1^{e_1}...x_d^{e_d}$$), where $$\operatorname{eval}_T (f(x)) = (f(t_1),...,f(t_n))$$, and where $$T=\{t_1,...,t_n\}$$. This function returns the toric codes discussed in [Joy2004].

INPUT:

• P – all the integer lattice points in a polytope defining the toric variety.

• F – a finite field.

OUTPUT: Returns toric code with length n = , dimension k over field F.

EXAMPLES:

sage: C = codes.ToricCode([[0,0],[1,0],[2,0],[0,1],[1,1]], GF(7))
sage: C
[36, 5] linear code over GF(7)
sage: C.minimum_distance()
24
sage: C.minimum_distance(algorithm="guava")  # optional - gap_package_guava
...24
sage: C = codes.ToricCode([[-2,-2],[-1,-2],[-1,-1],[-1,0],
....:                      [0,-1],[0,0],[0,1],[1,-1],[1,0]], GF(5))
sage: C
[16, 9] linear code over GF(5)
sage: C.minimum_distance()
6
sage: C.minimum_distance(algorithm="guava")  # optional - gap_package_guava
6
sage: C = codes.ToricCode([[0,0],[1,1],[1,2],[1,3],[1,4],[2,1],
....:                      [2,2],[2,3],[3,1],[3,2],[4,1]], GF(8,"a"))
sage: C
[49, 11] linear code over GF(8)


This is in fact a [49,11,28] code over $$\GF{8}$$. If you type next C.minimum_distance() and wait overnight (!), you should get 28.

AUTHOR:

• David Joyner (07-2006)

sage.coding.code_constructions.WalshCode(m)#

Return the binary Walsh code of length $$2^m$$.

The matrix of codewords correspond to a Hadamard matrix. This is a (constant rate) binary linear $$[2^m,m,2^{m-1}]$$ code.

EXAMPLES:

sage: C = codes.WalshCode(4); C
[16, 4] linear code over GF(2)
sage: C = codes.WalshCode(3); C
[8, 3] linear code over GF(2)
sage: C.spectrum()
[1, 0, 0, 0, 7, 0, 0, 0, 0]
sage: C.minimum_distance()
4
sage: C.minimum_distance(algorithm='gap')  # check d=2^(m-1)
4


REFERENCES:

sage.coding.code_constructions.from_parity_check_matrix(H)#

Return the linear code that has H as a parity check matrix.

If H has dimensions $$h \times n$$ then the linear code will have dimension $$n-h$$ and length $$n$$.

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3); C
[7, 4] Hamming Code over GF(2)
sage: H = C.parity_check_matrix(); H
[1 0 1 0 1 0 1]
[0 1 1 0 0 1 1]
[0 0 0 1 1 1 1]
sage: C2 = codes.from_parity_check_matrix(H); C2
[7, 4] linear code over GF(2)
sage: C2.systematic_generator_matrix() == C.systematic_generator_matrix()
True

sage.coding.code_constructions.permutation_action(g, v)#

Returns permutation of rows $$g * v$$.

Works on lists, matrices, sequences and vectors (by permuting coordinates). The code requires switching from $$i$$ to $$i+1$$ (and back again) since the SymmetricGroup is, by convention, the symmetric group on the “letters” $$1$$, $$2$$, …, $$n$$ (not $$0$$, $$1$$, …, $$n-1$$).

EXAMPLES:

sage: V = VectorSpace(GF(3),5)
sage: v = V([0,1,2,0,1])
sage: G = SymmetricGroup(5)                                                     # optional - sage.groups
sage: g = G([(1,2,3)])                                                          # optional - sage.groups
sage: permutation_action(g,v)                                                   # optional - sage.groups
(1, 2, 0, 0, 1)
sage: g = G([()])                                                               # optional - sage.groups
sage: permutation_action(g,v)                                                   # optional - sage.groups
(0, 1, 2, 0, 1)
sage: g = G([(1,2,3,4,5)])                                                      # optional - sage.groups
sage: permutation_action(g,v)                                                   # optional - sage.groups
(1, 2, 0, 1, 0)
sage: L = Sequence([1,2,3,4,5])
sage: permutation_action(g,L)                                                   # optional - sage.groups
[2, 3, 4, 5, 1]
sage: MS = MatrixSpace(GF(3),3,7)
sage: A = MS([[1,0,0,0,1,1,0],[0,1,0,1,0,1,0],[0,0,0,0,0,0,1]])
sage: S5 = SymmetricGroup(5)                                                    # optional - sage.groups
sage: g = S5([(1,2,3)])                                                         # optional - sage.groups
sage: A
[1 0 0 0 1 1 0]
[0 1 0 1 0 1 0]
[0 0 0 0 0 0 1]
sage: permutation_action(g,A)                                                   # optional - sage.groups
[0 1 0 1 0 1 0]
[0 0 0 0 0 0 1]
[1 0 0 0 1 1 0]


It also works on lists and is a “left action”:

sage: v = [0,1,2,0,1]
sage: G = SymmetricGroup(5)                                                     # optional - sage.groups
sage: g = G([(1,2,3)])                                                          # optional - sage.groups
sage: gv = permutation_action(g,v); gv                                          # optional - sage.groups
[1, 2, 0, 0, 1]
sage: permutation_action(g,v) == g(v)                                           # optional - sage.groups
True
sage: h = G([(3,4)])                                                            # optional - sage.groups
sage: gv = permutation_action(g,v)                                              # optional - sage.groups
sage: hgv = permutation_action(h,gv)                                            # optional - sage.groups
sage: hgv == permutation_action(h*g,v)                                          # optional - sage.groups
True


AUTHORS:

• David Joyner, licensed under the GPL v2 or greater.

sage.coding.code_constructions.random_linear_code(F, length, dimension)#

Generate a random linear code of length length, dimension dimension and over the field F.

This function is Las Vegas probabilistic: always correct, usually fast. Random matrices over the F are drawn until one with full rank is hit.

If F is infinite, the distribution of the elements in the random generator matrix will be random according to the distribution of F.random_element().

EXAMPLES:

sage: C = codes.random_linear_code(GF(2), 10, 3)
sage: C
[10, 3] linear code over GF(2)
sage: C.generator_matrix().rank()
3

sage.coding.code_constructions.walsh_matrix(m0)#

This is the generator matrix of a Walsh code. The matrix of codewords correspond to a Hadamard matrix.

EXAMPLES:

sage: walsh_matrix(2)
[0 0 1 1]
[0 1 0 1]
sage: walsh_matrix(3)
[0 0 0 0 1 1 1 1]
[0 0 1 1 0 0 1 1]
[0 1 0 1 0 1 0 1]
sage: C = LinearCode(walsh_matrix(4)); C
[16, 4] linear code over GF(2)
sage: C.spectrum()
[1, 0, 0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0]
`

This last code has minimum distance 8.

REFERENCES: