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.GeneralizedReedSolomonCodes.

For deprecation reasons, this file also contains some constructions for which Sage now does have rich representations.

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

sage: codes.BinaryGolayCode()
Linear code of length 23, dimension 12 over Finite Field of size 2

AUTHOR:

  • David Joyner (2007-05): initial version
  • ” (2008-02): added cyclic codes, Hamming codes
  • ” (2008-03): added BCH code, LinearCodeFromCheckmatrix, ReedSolomonCode, WalshCode, DuadicCodeEvenPair, DuadicCodeOddPair, QR codes (even and odd)
  • ” (2008-09) fix for bug in BCHCode reported by F. Voloch
  • ” (2008-10) small docstring changes to WalshCode and walsh_matrix
sage.coding.code_constructions.BCHCode(n, delta, F, b=0)

A ‘Bose-Chaudhuri-Hockenghem code’ (or BCH code for short) is the largest possible cyclic code of length n over field F=GF(q), whose generator polynomial has zeros (which contain the set) \(Z = \{a^{b},a^{b+1}, ..., a^{b+delta-2}\}\), where a is a primitive \(n^{th}\) root of unity in the splitting field \(GF(q^m)\), b is an integer \(0\leq b\leq n-delta+1\) and m is the multiplicative order of q modulo n. (The integers \(b,...,b+delta-2\) typically lie in the range \(1,...,n-1\).) The integer \(delta \geq 1\) is called the “designed distance”. The length n of the code and the size q of the base field must be relatively prime. The generator polynomial is equal to the least common multiple of the minimal polynomials of the elements of the set \(Z\) above.

Special cases are b=1 (resulting codes are called ‘narrow-sense’ BCH codes), and \(n=q^m-1\) (known as ‘primitive’ BCH codes).

It may happen that several values of delta give rise to the same BCH code. The largest one is called the Bose distance of the code. The true minimum distance, d, of the code is greater than or equal to the Bose distance, so \(d\geq delta\).

EXAMPLES:

sage: FF.<a> = GF(3^2,"a")
sage: x = PolynomialRing(FF,"x").gen()
sage: L = [b.minpoly() for b in [a,a^2,a^3]]; g = LCM(L)
sage: f = x^(8)-1
sage: g.divides(f)
True
sage: C = codes.CyclicCode(8,g); C
Linear code of length 8, dimension 4 over Finite Field of size 3
sage: C.minimum_distance()
4
sage: C = codes.BCHCode(8,3,GF(3),1); C
Linear code of length 8, dimension 4 over Finite Field of size 3
sage: C.minimum_distance()
4
sage: C = codes.BCHCode(8,3,GF(3)); C
Linear code of length 8, dimension 5 over Finite Field of size 3
sage: C.minimum_distance()
3
sage: C = codes.BCHCode(26, 5, GF(5), b=1); C
Linear code of length 26, dimension 10 over Finite Field of size 5
sage.coding.code_constructions.BinaryGolayCode()

BinaryGolayCode() returns a binary Golay code. This is a perfect [23,12,7] code. It is also (equivalent to) a cyclic code, with generator polynomial \(g(x)=1+x^2+x^4+x^5+x^6+x^{10}+x^{11}\). Extending it yields the extended Golay code (see ExtendedBinaryGolayCode).

EXAMPLE:

sage: C = codes.BinaryGolayCode()
sage: C
Linear code of length 23, dimension 12 over Finite Field of size 2
sage: C.minimum_distance()
7
sage: C.minimum_distance(algorithm='gap') # long time, check d=7
7

AUTHORS:

  • David Joyner (2007-05)
sage.coding.code_constructions.CyclicCode(n, g, ignore=True)

If g is a polynomial over GF(q) which divides \(x^n-1\) then this constructs the code “generated by g” (ie, the code associated with the principle ideal \(gR\) in the ring \(R = GF(q)[x]/(x^n-1)\) in the usual way).

The option “ignore” says to ignore the condition that (a) the characteristic of the base field does not divide the length (the usual assumption in the theory of cyclic codes), and (b) \(g\) must divide \(x^n-1\). If ignore=True, instead of returning an error, a code generated by \(gcd(x^n-1,g)\) is created.

EXAMPLES:

sage: P.<x> = PolynomialRing(GF(3),"x")
sage: g = x-1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(4,g); C
Linear code of length 4, dimension 3 over Finite Field of size 3
sage: P.<x> = PolynomialRing(GF(4,"a"),"x")
sage: g = x^3+1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(9,g); C
Linear code of length 9, dimension 6 over Finite Field in a of size 2^2
sage: P.<x> = PolynomialRing(GF(2),"x")
sage: g = x^3+x+1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(7,g); C
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C.generator_matrix()
[1 1 0 1 0 0 0]
[0 1 1 0 1 0 0]
[0 0 1 1 0 1 0]
[0 0 0 1 1 0 1]
sage: g = x+1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(4,g); C
Linear code of length 4, dimension 3 over Finite Field of size 2
sage: C.generator_matrix()
[1 1 0 0]
[0 1 1 0]
[0 0 1 1]

On the other hand, CyclicCodeFromPolynomial(4,x) will produce a ValueError including a traceback error message: “\(x\) must divide \(x^4 - 1\)”. You will also get a ValueError if you type

sage: P.<x> = PolynomialRing(GF(4,"a"),"x")
sage: g = x^2+1

followed by CyclicCodeFromGeneratingPolynomial(6,g). You will also get a ValueError if you type

sage: P.<x> = PolynomialRing(GF(3),"x")
sage: g = x^2-1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(5,g); C
Linear code of length 5, dimension 4 over Finite Field of size 3

followed by C = CyclicCodeFromGeneratingPolynomial(5,g,False), with a traceback message including “\(x^2 + 2\) must divide \(x^5 - 1\)”.

sage.coding.code_constructions.CyclicCodeFromCheckPolynomial(n, h, ignore=True)

If h is a polynomial over GF(q) which divides \(x^n-1\) then this constructs the code “generated by \(g = (x^n-1)/h\)” (ie, the code associated with the principle ideal \(gR\) in the ring \(R = GF(q)[x]/(x^n-1)\) in the usual way). The option “ignore” says to ignore the condition that the characteristic of the base field does not divide the length (the usual assumption in the theory of cyclic codes).

EXAMPLES:

sage: P.<x> = PolynomialRing(GF(3),"x")
sage: C = codes.CyclicCodeFromCheckPolynomial(4,x + 1); C
Linear code of length 4, dimension 1 over Finite Field of size 3
sage: C = codes.CyclicCodeFromCheckPolynomial(4,x^3 + x^2 + x + 1); C
Linear code of length 4, dimension 3 over Finite Field of size 3
sage: C.generator_matrix()
[2 1 0 0]
[0 2 1 0]
[0 0 2 1]
sage.coding.code_constructions.CyclicCodeFromGeneratingPolynomial(n, g, ignore=True)

If g is a polynomial over GF(q) which divides \(x^n-1\) then this constructs the code “generated by g” (ie, the code associated with the principle ideal \(gR\) in the ring \(R = GF(q)[x]/(x^n-1)\) in the usual way).

The option “ignore” says to ignore the condition that (a) the characteristic of the base field does not divide the length (the usual assumption in the theory of cyclic codes), and (b) \(g\) must divide \(x^n-1\). If ignore=True, instead of returning an error, a code generated by \(gcd(x^n-1,g)\) is created.

EXAMPLES:

sage: P.<x> = PolynomialRing(GF(3),"x")
sage: g = x-1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(4,g); C
Linear code of length 4, dimension 3 over Finite Field of size 3
sage: P.<x> = PolynomialRing(GF(4,"a"),"x")
sage: g = x^3+1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(9,g); C
Linear code of length 9, dimension 6 over Finite Field in a of size 2^2
sage: P.<x> = PolynomialRing(GF(2),"x")
sage: g = x^3+x+1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(7,g); C
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C.generator_matrix()
[1 1 0 1 0 0 0]
[0 1 1 0 1 0 0]
[0 0 1 1 0 1 0]
[0 0 0 1 1 0 1]
sage: g = x+1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(4,g); C
Linear code of length 4, dimension 3 over Finite Field of size 2
sage: C.generator_matrix()
[1 1 0 0]
[0 1 1 0]
[0 0 1 1]

On the other hand, CyclicCodeFromPolynomial(4,x) will produce a ValueError including a traceback error message: “\(x\) must divide \(x^4 - 1\)”. You will also get a ValueError if you type

sage: P.<x> = PolynomialRing(GF(4,"a"),"x")
sage: g = x^2+1

followed by CyclicCodeFromGeneratingPolynomial(6,g). You will also get a ValueError if you type

sage: P.<x> = PolynomialRing(GF(3),"x")
sage: g = x^2-1
sage: C = codes.CyclicCodeFromGeneratingPolynomial(5,g); C
Linear code of length 5, dimension 4 over Finite Field of size 3

followed by C = CyclicCodeFromGeneratingPolynomial(5,g,False), with a traceback message including “\(x^2 + 2\) must divide \(x^5 - 1\)”.

sage.coding.code_constructions.DuadicCodeEvenPair(F, S1, S2)

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
[[0], [1, 3, 4, 5, 9], [2, 6, 7, 8, 10]]
sage: S1 = C[1]
sage: S2 = C[2]
sage: _is_a_splitting(S1,S2,11)
True
sage: codes.DuadicCodeEvenPair(GF(q),S1,S2)
(Linear code of length 11, dimension 5 over Finite Field of size 3,
 Linear code of length 11, dimension 5 over Finite Field of size 3)
sage.coding.code_constructions.DuadicCodeOddPair(F, S1, S2)

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
[[0], [1, 3, 4, 5, 9], [2, 6, 7, 8, 10]]
sage: S1 = C[1]
sage: S2 = C[2]
sage: _is_a_splitting(S1,S2,11)
True
sage: codes.DuadicCodeOddPair(GF(q),S1,S2)
(Linear code of length 11, dimension 6 over Finite Field of size 3,
 Linear code of length 11, dimension 6 over Finite Field of size 3)

This is consistent with Theorem 6.1.3 in [HP].

sage.coding.code_constructions.ExtendedBinaryGolayCode()

ExtendedBinaryGolayCode() returns the extended binary Golay code. This is a perfect [24,12,8] code. This code is self-dual.

EXAMPLES:

sage: C = codes.ExtendedBinaryGolayCode()
sage: C
Linear code of length 24, dimension 12 over Finite Field of size 2
sage: C.minimum_distance()
8
sage: C.minimum_distance(algorithm='gap') # long time, check d=8
8

AUTHORS:

  • David Joyner (2007-05)
sage.coding.code_constructions.ExtendedQuadraticResidueCode(n, F)

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 [HP], Section 6.6.3-6.6.4.)

INPUT:

  • n - an odd prime
  • F - a finite prime field F 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
Extended code coming from Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C2 == C3
True
sage: C = codes.ExtendedQuadraticResidueCode(17,GF(2))
sage: C
Extended code coming from Linear code of length 17, dimension 9 over Finite Field of size 2
sage: C3 = codes.QuadraticResidueCodeOddPair(7,GF(2))[0]
sage: C3x = C3.extended_code()
sage: C4 = codes.ExtendedQuadraticResidueCode(7,GF(2))
sage: C3x == C4
True

AUTHORS:

  • David Joyner (07-2006)
sage.coding.code_constructions.ExtendedTernaryGolayCode()

ExtendedTernaryGolayCode returns a ternary Golay code. This is a self-dual perfect [12,6,6] code.

EXAMPLES:

sage: C = codes.ExtendedTernaryGolayCode()
sage: C
Linear code of length 12, dimension 6 over Finite Field of size 3
sage: C.minimum_distance()
6
sage: C.minimum_distance(algorithm='gap') # long time, check d=6
6

AUTHORS:

  • David Joyner (11-2005)
sage.coding.code_constructions.QuadraticResidueCode(n, F)

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 F 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
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C = codes.QuadraticResidueCode(17,GF(2))
sage: C
Linear code of length 17, dimension 9 over Finite Field of size 2
sage: C1 = codes.QuadraticResidueCodeOddPair(7,GF(2))[0]
sage: C2 = codes.QuadraticResidueCode(7,GF(2))
sage: C1 == C2
True
sage: C1 = codes.QuadraticResidueCodeOddPair(17,GF(2))[0]
sage: C2 = codes.QuadraticResidueCode(17,GF(2))
sage: C1 == C2
True

AUTHORS:

  • David Joyner (11-2005)
sage.coding.code_constructions.QuadraticResidueCodeEvenPair(n, F)

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 [HP]) 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))
(Linear code of length 17, dimension 8 over Finite Field of size 13,
 Linear code of length 17, dimension 8 over Finite Field of size 13)
sage: codes.QuadraticResidueCodeEvenPair(17,GF(2))
(Linear code of length 17, dimension 8 over Finite Field of size 2,
 Linear code of length 17, dimension 8 over Finite Field of size 2)
sage: codes.QuadraticResidueCodeEvenPair(13,GF(9,"z"))
(Linear code of length 13, dimension 6 over Finite Field in z of size 3^2,
 Linear code of length 13, dimension 6 over Finite Field in z of size 3^2)
sage: C1,C2 = codes.QuadraticResidueCodeEvenPair(7,GF(2))
sage: C1.is_self_orthogonal()
True
sage: C2.is_self_orthogonal()
True
sage: C3 = codes.QuadraticResidueCodeOddPair(17,GF(2))[0]
sage: C4 = codes.QuadraticResidueCodeEvenPair(17,GF(2))[1]
sage: C3 == C4.dual_code()
True

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

TESTS:

sage: codes.QuadraticResidueCodeEvenPair(14,Zmod(4))
Traceback (most recent call last):
...
ValueError: the argument F must be a finite field
sage: codes.QuadraticResidueCodeEvenPair(14,GF(2))
Traceback (most recent call last):
...
ValueError: the argument n must be an odd prime
sage: codes.QuadraticResidueCodeEvenPair(5,GF(2))
Traceback (most recent call last):
...
ValueError: the order of the finite field must be a quadratic residue modulo n
sage.coding.code_constructions.QuadraticResidueCodeOddPair(n, F)

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 [HP]) 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))
(Linear code of length 17, dimension 9 over Finite Field of size 13,
 Linear code of length 17, dimension 9 over Finite Field of size 13)
sage: codes.QuadraticResidueCodeOddPair(17,GF(2))
(Linear code of length 17, dimension 9 over Finite Field of size 2,
 Linear code of length 17, dimension 9 over Finite Field of size 2)
sage: codes.QuadraticResidueCodeOddPair(13,GF(9,"z"))
(Linear code of length 13, dimension 7 over Finite Field in z of size 3^2,
 Linear code of length 13, dimension 7 over Finite Field in z of size 3^2)
sage: C1 = codes.QuadraticResidueCodeOddPair(17,GF(2))[1]
sage: C1x = C1.extended_code()
sage: C2 = codes.QuadraticResidueCodeOddPair(17,GF(2))[0]
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: C3 = codes.QuadraticResidueCodeOddPair(7,GF(2))[0]
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 [HP].

TESTS:

sage: codes.QuadraticResidueCodeOddPair(9,GF(2))
Traceback (most recent call last):
...
ValueError: the argument n must be an odd prime
sage.coding.code_constructions.RandomLinearCode(n, k, F)

Deprecated alias of random_linear_code().

EXAMPLES:

sage: C = codes.RandomLinearCode(10, 3, GF(2))
doctest:...: DeprecationWarning: codes.RandomLinearCode(n, k, F) is deprecated. Please use codes.random_linear_code(F, n, k) instead
See http://trac.sagemath.org/21165 for details.
sage: C
Linear code of length 10, dimension 3 over Finite Field of size 2
sage: C.generator_matrix().rank()
3
sage.coding.code_constructions.ReedSolomonCode(n, k, F, pts=None)
sage.coding.code_constructions.TernaryGolayCode()

TernaryGolayCode returns a ternary Golay code. This is a perfect [11,6,5] code. It is also equivalent to a cyclic code, with generator polynomial \(g(x)=2+x^2+2x^3+x^4+x^5\).

EXAMPLES:

sage: C = codes.TernaryGolayCode()
sage: C
Linear code of length 11, dimension 6 over Finite Field of size 3
sage: C.minimum_distance()
5
sage: C.minimum_distance(algorithm='gap') # long time, check d=5
5

AUTHORS:

  • David Joyner (2007-5)
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

\[\mathrm{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 \(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 [J].

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
Linear code of length 36, dimension 5 over Finite Field of size 7
sage: C.minimum_distance()
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
Linear code of length 16, dimension 9 over Finite Field of size 5
sage: C.minimum_distance()
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
Linear code of length 49, dimension 11 over Finite Field in a of size 2^3

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)

REFERENCES:

[J]D. Joyner, Toric codes over finite fields, Applicable Algebra in Engineering, Communication and Computing, 15, (2004), p. 63-79.
sage.coding.code_constructions.WalshCode(m)

Returns 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
Linear code of length 16, dimension 4 over Finite Field of size 2
sage: C = codes.WalshCode(3); C
Linear code of length 8, dimension 3 over Finite Field of size 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 Finite Field of size 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
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C2.systematic_generator_matrix() == C.systematic_generator_matrix()
True
sage.coding.code_constructions.lift2smallest_field2(a)

INPUT: a is an element of a finite field GF(q)

OUTPUT: the element b of the smallest subfield F of GF(q) for which F(b)=a.

EXAMPLES:

sage: from sage.coding.code_constructions import lift2smallest_field2
sage: FF.<z> = GF(3^4,"z")
sage: a = z^40
sage: lift2smallest_field2(a)
doctest:...: DeprecationWarning: lift2smallest_field2 will be removed in a future release of Sage. Consider using sage.coding.code_constructions._lift2smallest_field instead, though this is private and may be removed in the future without deprecation warning. If you care about this functionality being in Sage, consider opening a Trac ticket for promoting the function to public.
See http://trac.sagemath.org/21165 for details.
(2, Finite Field of size 3)
sage: FF.<z> = GF(2^4,"z")
sage: a = z^15
sage: lift2smallest_field2(a)
(1, Finite Field of size 2)

Warning

Since coercion (the FF(b) step) has a bug in it, this only works in the case when you know F is a prime field.

AUTHORS:

  • David Joyner
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)
sage: g = G([(1,2,3)])
sage: permutation_action(g,v)
(1, 2, 0, 0, 1)
sage: g = G([()])
sage: permutation_action(g,v)
(0, 1, 2, 0, 1)
sage: g = G([(1,2,3,4,5)])
sage: permutation_action(g,v)
(1, 2, 0, 1, 0)
sage: L = Sequence([1,2,3,4,5])
sage: permutation_action(g,L)
[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)
sage: g = S5([(1,2,3)])
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)
[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)
sage: g = G([(1,2,3)])
sage: gv = permutation_action(g,v); gv
[1, 2, 0, 0, 1]
sage: permutation_action(g,v) == g(v)
True
sage: h = G([(3,4)])
sage: gv = permutation_action(g,v)
sage: hgv = permutation_action(h,gv)
sage: hgv == permutation_action(h*g,v)
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
Linear code of length 10, dimension 3 over Finite Field of size 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
Linear code of length 16, dimension 4 over Finite Field of size 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: