Linear code constructions¶
This file contains constructions of error-correcting codes which are pure Python/Sage and not obtained from wrapping GUAVA functions. The GUAVA wrappers are in guava.py.
All codes available here can be accessed through the codes
object:
sage: codes.HammingCode(3,GF(2))
Linear code of length 7, dimension 4 over Finite Field of size 2
Let be a finite field with
elements.
Here’s a constructive definition of a cyclic code of length
.
- Pick a monic polynomial
dividing
. This is called the generating polynomial of the code.
- For each polynomial
, compute
. Denote the answer by
.
is a codeword in
. Every codeword in
arises in this way (from some
).
The polynomial notation for the code is to call
the codeword (instead of
). The polynomial
is called the check polynomial of
.
Let be a positive integer relatively prime to
and let
be a primitive
-th root of unity. Each generator polynomial
of a cyclic code
of length
has a
factorization of the form
where . The
numbers
,
, are
called the zeros of the code
. Many families of cyclic
codes (such as BCH codes and the quadratic residue codes) are
defined using properties of the zeros of
.
- BCHCode - 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)
, where
is a primitive
root of unity in the splitting field
,
is an integer
and
is the multiplicative order of
modulo
. The default here is
(unlike Guava, which has default
). Here
are the cyclotomic codes.
- BinaryGolayCode, ExtendedBinaryGolayCode, TernaryGolayCode, ExtendedTernaryGolayCode the well-known”extremal” Golay codes, http://en.wikipedia.org/wiki/Golay_code
- cyclic codes - CyclicCodeFromGeneratingPolynomial (= CyclicCode), CyclicCodeFromCheckPolynomial, http://en.wikipedia.org/wiki/Cyclic_code
- DuadicCodeEvenPair, DuadicCodeOddPair: Constructs the “even (resp. odd) pair” of duadic codes associated to the “splitting” S1, S2 of n. This is a special type of cyclic code whose generator is determined by S1, S2. See chapter 6 in [HP].
- HammingCode - the well-known Hamming code, http://en.wikipedia.org/wiki/Hamming_code
- LinearCodeFromCheckMatrix - for specifying the code using the check matrix instead of the generator matrix.
- QuadraticResidueCodeEvenPair, QuadraticResidueCodeOddPair: 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. Here 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. QuadraticResidueCode (a special case) and ExtendedQuadraticResidueCode are included as well.
- RandomLinearCode - Repeatedly applies Sage’s random_element applied to the ambient MatrixSpace of the generator matrix until a full rank matrix is found.
- ReedSolomonCode - Given a finite field
of order
, let
and
be chosen such that
. Pick
distinct elements of
, denoted
. Then, the codewords are obtained by evaluating every polynomial in
of degree less than
at each
.
- ToricCode - Let
denote a list of lattice points in
and let
denote a listing of all points in
. Put
and let
denote the dimension of the vector space of functions
. The associated toric code
is the evaluation code which is the image of the evaluation map
, where
is the multi-index notation.
- WalshCode - a binary linear
code related to Hadamard matrices. http://en.wikipedia.org/wiki/Walsh_code
REFERENCES:
[HP] | (1, 2, 3, 4, 5, 6, 7, 8, 9) W. C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, 2003. |
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
Functions¶
-
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)
, where a is a primitive
root of unity in the splitting field
, b is an integer
and m is the multiplicative order of q modulo n. (The integers
typically lie in the range
.) The integer
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
above.
Special cases are b=1 (resulting codes are called ‘narrow-sense’ BCH codes), and
(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
.
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
. 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
then this constructs the code “generated by g” (ie, the code associated with the principle ideal
in the ring
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)
must divide
. If ignore=True, instead of returning an error, a code generated by
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: “
must divide
”. 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 “
must divide
”.
-
sage.coding.code_constructions.
CyclicCodeFromCheckPolynomial
(n, h, ignore=True)¶ If h is a polynomial over GF(q) which divides
then this constructs the code “generated by
” (ie, the code associated with the principle ideal
in the ring
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
then this constructs the code “generated by g” (ie, the code associated with the principle ideal
in the ring
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)
must divide
. If ignore=True, instead of returning an error, a code generated by
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: “
must divide
”. 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 “
must divide
”.
-
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 primeF
- 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 Linear code of length 8, dimension 4 over Finite Field of size 2 sage: C2 == C3 True sage: C = codes.ExtendedQuadraticResidueCode(17,GF(2)) sage: C Linear code of length 18, 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.
HammingCode
(r, F)¶ Implements the Hamming codes.
The
Hamming code over
is an
code with length
, dimension
and minimum distance
. The parity check matrix of a Hamming code has rows consisting of all nonzero vectors of length r in its columns, modulo a scalar factor so no parallel columns arise. A Hamming code is a single error-correcting code.
INPUT:
r
- an integer 2F
- a finite field.
OUTPUT: Returns the r-th q-ary Hamming code.
EXAMPLES:
sage: codes.HammingCode(3,GF(2)) Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C = codes.HammingCode(3,GF(3)); C Linear code of length 13, dimension 10 over Finite Field of size 3 sage: C.minimum_distance() 3 sage: C.minimum_distance(algorithm='gap') # long time, check d=3 3 sage: C = codes.HammingCode(3,GF(4,'a')); C Linear code of length 21, dimension 18 over Finite Field in a of size 2^2
While the
codes
object now gathers all code constructors,HammingCode
is still available in the global namespace:sage: HammingCode(3,GF(2)) doctest:...: DeprecationWarning: This method soon will not be available in that way anymore. To use it, you can now call it by typing codes.HammingCode See http://trac.sagemath.org/15445 for details. Linear code of length 7, dimension 4 over Finite Field of size 2
-
sage.coding.code_constructions.
LinearCodeFromCheckMatrix
(H)¶ A linear [n,k]-code C is uniquely determined by its generator matrix G and check matrix H. We have the following short exact sequence
(“Short exact” means (a) the arrow
is injective, i.e.,
is a full-rank
matrix, (b) the arrow
is surjective, and (c)
.)
EXAMPLES:
sage: C = codes.HammingCode(3,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: codes.LinearCodeFromCheckMatrix(H) == C True sage: C = codes.HammingCode(2,GF(3)) sage: H = C.parity_check_matrix(); H [1 0 1 1] [0 1 1 2] sage: codes.LinearCodeFromCheckMatrix(H) == C True sage: C = codes.RandomLinearCode(10,5,GF(4,"a")) sage: H = C.parity_check_matrix() sage: codes.LinearCodeFromCheckMatrix(H) == C True
-
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
(
is a primitive
root of unity;
ranges over the set of quadratic residues modulo
).
See QuadraticResidueCodeEvenPair and QuadraticResidueCodeOddPair for a more general construction.
INPUT:
n
- an odd primeF
- 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
is prime then (Theorem 6.6.2 in [HP]) a QR code exists over
iff q is a quadratic residue mod
.
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: C2x == C1x.dual_code() True 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] sage: C3x.is_self_dual() True
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)¶ The method used is to first construct a
matrix using Sage’s random_element method for the MatrixSpace class. The construction is probabilistic but should only fail extremely rarely.
INPUT: Integers n,k, with
, and a finite field F
OUTPUT: Returns a “random” linear code with length n, dimension k over field F.
EXAMPLES:
sage: C = codes.RandomLinearCode(30,15,GF(2)) sage: C Linear code of length 30, dimension 15 over Finite Field of size 2 sage: C = codes.RandomLinearCode(10,5,GF(4,'a')) sage: C Linear code of length 10, dimension 5 over Finite Field in a of size 2^2
AUTHORS:
- David Joyner (2007-05)
-
sage.coding.code_constructions.
ReedSolomonCode
(n, k, F, pts=None)¶ Given a finite field
of order
, let
and
be chosen such that
. Pick
distinct elements of
, denoted
. Then, the codewords are obtained by evaluating every polynomial in
of degree less than
at each
:
is a
code. (In particular,
is MDS.)
INPUT: n : the length k : the dimension F : the base ring pts : (optional) list of n points in F (if None then Sage picks n of them in the order given to the elements of F)
EXAMPLES:
sage: C = codes.ReedSolomonCode(6,4,GF(7)); C Linear code of length 6, dimension 4 over Finite Field of size 7 sage: C.minimum_distance() 3 sage: C = codes.ReedSolomonCode(6,4,GF(8,"a")); C Linear code of length 6, dimension 4 over Finite Field in a of size 2^3 sage: C.minimum_distance() 3 sage: C.minimum_distance(algorithm='gap') # long time, check d=n-k+1 3 sage: F.<a> = GF(3^2,"a") sage: pts = [0,1,a,a^2,2*a,2*a+1] sage: len(Set(pts)) == 6 # to make sure there are no duplicates True sage: C = codes.ReedSolomonCode(6,4,F,pts); C Linear code of length 6, dimension 4 over Finite Field in a of size 3^2 sage: C.minimum_distance() 3
While the
codes
object now gathers all code constructors,ReedSolomonCode
is still available in the global namespace:sage: ReedSolomonCode(6,4,GF(7)) doctest:...: DeprecationWarning: This method soon will not be available in that way anymore. To use it, you can now call it by typing codes.ReedSolomonCode See http://trac.sagemath.org/15445 for details. Linear code of length 6, dimension 4 over Finite Field of size 7
REFERENCES:
-
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
.
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
denote a list of lattice points in
and let
denote the set of all points in
(ordered in some fixed way). Put
and let
denote the dimension of the vector space of functions
. The associated toric code
is the evaluation code which is the image of the evaluation map
where
is the multi-index notation (
,
, and
), where
, and where
. 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.
TrivialCode
(F, n)¶
-
sage.coding.code_constructions.
WalshCode
(m)¶ Returns the binary Walsh code of length
. The matrix of codewords correspond to a Hadamard matrix. This is a (constant rate) binary linear
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.
cyclotomic_cosets
(q, n, t=None)¶ This method is deprecated.
See the documentation in
cyclotomic_cosets()
.INPUT: q,n,t positive integers (or t=None) Some type-checking of inputs is performed.
OUTPUT: q-cyclotomic cosets mod n (or, if t is not None, the q-cyclotomic coset mod n containing t)
EXAMPLES:
sage: cyclotomic_cosets(2,11) doctest:...: DeprecationWarning: cyclotomic_cosets(q,n,t) is deprecated. Use Zmod(n).cyclotomic_cosets(q) or Zmod(n).cyclotomic_cosets(q,[t]) instead. Be careful that this method returns elements of Zmod(n). See http://trac.sagemath.org/16464 for details. [[0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]] sage: Zmod(11).cyclotomic_cosets(2) [[0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]] sage: cyclotomic_cosets(5,11) [[0], [1, 3, 4, 5, 9], [2, 6, 7, 8, 10]] sage: cyclotomic_cosets(5,11,3) [1, 3, 4, 5, 9]
-
sage.coding.code_constructions.
is_a_splitting
(S1, S2, n, return_automorphism=False)¶ Check wether
(S1,S2)
is a splitting of.
A splitting of
is a pair of subsets of
which is a partition of
and such that there exists an element
of
such that
and
(where
is the point-wise multiplication of the elements of
by
).
Splittings are useful for computing idempotents in the quotient ring
.
INPUT:
S1, S2
– disjoint sublists partitioning[1, 2, ..., n-1]
n
(integer)return_automorphism
(boolean) – whether to return the automorphism exchangingand
.
OUTPUT:
If
return_automorphism is False
(default) the function returns boolean values.Otherwise, it returns a pair
(b, r)
whereb
is a boolean indicating whether,
is a splitting of
, and
is such that
and
(if
is
False
,is equal to
None
).EXAMPLES:
sage: from sage.coding.code_constructions import is_a_splitting sage: is_a_splitting([1,2],[3,4],5) True sage: is_a_splitting([1,2],[3,4],5,return_automorphism=True) (True, 4) sage: is_a_splitting([1,3],[2,4,5,6],7) False sage: is_a_splitting([1,3,4],[2,5,6],7) False sage: for P in SetPartitions(6,[3,3]): ....: res,aut= is_a_splitting(P[0],P[1],7,return_automorphism=True) ....: if res: ....: print aut, P[0], P[1] 6 {1, 2, 3} {4, 5, 6} 3 {1, 2, 4} {3, 5, 6} 6 {1, 3, 5} {2, 4, 6} 6 {1, 4, 5} {2, 3, 6}
We illustrate now how to find idempotents in quotient rings:
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: F = GF(q) sage: P.<x> = PolynomialRing(F,"x") sage: I = Ideal(P,[x^n-1]) sage: Q.<x> = QuotientRing(P,I) sage: i1 = -sum([x^i for i in S1]); i1 2*x^9 + 2*x^5 + 2*x^4 + 2*x^3 + 2*x sage: i2 = -sum([x^i for i in S2]); i2 2*x^10 + 2*x^8 + 2*x^7 + 2*x^6 + 2*x^2 sage: i1^2 == i1 True sage: i2^2 == i2 True sage: (1-i1)^2 == 1-i1 True sage: (1-i2)^2 == 1-i2 True
We return to dealing with polynomials (rather than elements of quotient rings), so we can construct cyclic codes:
sage: P.<x> = PolynomialRing(F,"x") sage: i1 = -sum([x^i for i in S1]) sage: i2 = -sum([x^i for i in S2]) sage: i1_sqrd = (i1^2).quo_rem(x^n-1)[1] sage: i1_sqrd == i1 True sage: i2_sqrd = (i2^2).quo_rem(x^n-1)[1] sage: i2_sqrd == i2 True sage: C1 = codes.CyclicCodeFromGeneratingPolynomial(n,i1) sage: C2 = codes.CyclicCodeFromGeneratingPolynomial(n,1-i2) sage: C1.dual_code() == C2 True
This is a special case of Theorem 6.4.3 in [HP].
-
sage.coding.code_constructions.
lift2smallest_field
(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_field sage: FF.<z> = GF(3^4,"z") sage: a = z^10 sage: lift2smallest_field(a) (2*z + 1, Finite Field in z of size 3^2) sage: a = z^40 sage: lift2smallest_field(a) (2, Finite Field of size 3)
AUTHORS:
- John Cremona
-
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) (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.
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: