A linear code of length
is a finite dimensional subspace of
. SAGE can compute with linear error-correcting codes
to a limited extent. It basically has some wrappers to
GAP and GUAVA 2.6 commands (GUAVA 2.6 does not include any
of Leon's C code which was included in previous versions of GUAVA).
GUAVA 2.6 is incuded with SAGE's install of GAP 4.4.7.
SAGE can compute Hamming codes
sage: C = HammingCode(3,GF(3)) sage: C Linear code of length 13, dimension 10 over Finite Field of size 3 sage: C.minimum_distance() 3 sage: C.gen_mat() [2 2 1 0 0 0 0 0 0 0 0 0 0] [1 2 0 1 0 0 0 0 0 0 0 0 0] [2 0 0 0 2 1 0 0 0 0 0 0 0] [1 0 0 0 2 0 1 0 0 0 0 0 0] [0 2 0 0 2 0 0 1 0 0 0 0 0] [2 2 0 0 2 0 0 0 1 0 0 0 0] [1 2 0 0 2 0 0 0 0 1 0 0 0] [0 1 0 0 2 0 0 0 0 0 1 0 0] [2 1 0 0 2 0 0 0 0 0 0 1 0] [1 1 0 0 2 0 0 0 0 0 0 0 1]
sage: C = ExtendedTernaryGolayCode() sage: C Linear code of length 12, dimension 6 over Finite Field of size 3 sage: C.minimum_distance() 6 sage: C.gen_mat() [1 0 2 1 2 2 0 0 0 0 0 1] [0 1 0 2 1 2 2 0 0 0 0 1] [0 0 1 0 2 1 2 2 0 0 0 1] [0 0 0 1 0 2 1 2 2 0 0 1] [0 0 0 0 1 0 2 1 2 2 0 1] [0 0 0 0 0 1 0 2 1 2 2 1]
as well as binary Reed-Muller codes, quadratic residue codes, quasi-quadratic residue codes, ``random'' linear codes, and a code generated by a matrix of full rank (using, as usual, the rows as the basis).
For a given code,
, SAGE can return a generator matrix,
a check matrix, and the dual code:
sage: C = HammingCode(3,GF(2)) sage: Cperp = C.dual_code() sage: C; Cperp Linear code of length 7, dimension 4 over Finite Field of size 2 Linear code of length 7, dimension 3 over Finite Field of size 2 sage: C.gen_mat() [1 1 1 0 0 0 0] [1 0 0 1 1 0 0] [0 1 0 1 0 1 0] [1 1 0 1 0 0 1] sage: C.check_mat() [0 1 1 1 1 0 0] [1 0 1 1 0 1 0] [1 1 0 1 0 0 1] sage: Cperp.check_mat() [1 1 1 0 0 0 0] [1 0 0 1 1 0 0] [0 1 0 1 0 1 0] [1 1 0 1 0 0 1] sage: Cperp.gen_mat() [0 1 1 1 1 0 0] [1 0 1 1 0 1 0] [1 1 0 1 0 0 1]
For
and a vector
,
SAGE can try to decode
(i.e., find the codeword
closest
to
in the Hamming metric) using syndrome decoding. As of yet,
no special decoding methods have been implemented.
sage: C = HammingCode(3,GF(2)) sage: MS = MatrixSpace(GF(2),1,7) sage: F=GF(2); a=F.gen() sage: v=MS([a,a,F(0),a,a,F(0),a]); v [1 1 0 1 1 0 1] sage: C.decode(v) [1, 1, 0, 1, 0, 0, 1]
To plot the (histogram of) the weight distribution of a code, one can use the gnuplot.py package included with SAGE:
sage: C = HammingCode(4,GF(2)) sage: C Linear code of length 15, dimension 11 over Finite Field of size 2 sage: C.weight_distribution() [1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1] sage: w = C.weight_distribution() sage: from Gnuplot import Gnuplot sage: g = Gnuplot(debug=1) gnuplot> set terminal x11 sage: g.plot([[i,w[i]] for i in range(len(w))]) gnuplot> plot '/tmp/tmpSDiZuo' notitle
SAGE can also compute algebraic-geometric codes, called AG codes,
via the Singular interface §17.4.1.
One may also use the AG codes implemented in GUAVA
via the SAGE interface to GAP gap_console()
.
See the GUAVA manual for more details.
SAGE has a special type of stream cipher implemented - a linear feedback shift register (LFSR) sequence defined over a finite field. Stream ciphers have been used for a long time as a source of pseudo-random number generators.
S. Golomb [G] gives a list of three
statistical properties a
sequence of numbers
,
, should display to be considered
``random''. Define the autocorrelation of
to be
In the case where
Assume
(For sequences satisfying these first two properties, it is known that
A general feedback shift register is a map
of the form
where
for some given constants
is sometimes called the connection polynomial.
Example:
Over
, if
then
,
The LFSR sequence is then
The sequence of
lfsr_connection_polynomial
(which produces the
reverse of berlekamp_massey
).
sage: F = GF(2) sage: o = F(0) sage: l = F(1) sage: key = [l,o,o,l]; fill = [l,l,o,l]; n = 20 sage: s = lfsr_sequence(key,fill,n); s [1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0] sage: lfsr_autocorrelation(s,15,7) 4/15 sage: lfsr_autocorrelation(s,15,0) 8/15 sage: lfsr_connection_polynomial(s) x^4 + x + 1 sage: berlekamp_massey(s) x^4 + x^3 + 1
See About this document... for information on suggesting changes.