\documentclass[14pt]{article} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsgen} \usepackage{amsfonts} \usepackage{hyperref} \usepackage{makeidx} % allows for index generation \usepackage{url} \usepackage{xspace} \usepackage{graphicx} \usepackage{fancyvrb} \usepackage{moreverb} \usepackage{color} \definecolor{hue}{rgb}{.202, .602, .58} \definecolor{red}{rgb}{.902, .02, .08} \definecolor{green}{rgb}{.02, .902, .08} \definecolor{blue}{rgb}{.02, .02, .908} \definecolor{orange}{rgb}{.902, .502, .08} \definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064} \definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083} \definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179} \definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894} \definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894} \definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000} \definecolor{Black}{rgb}{0.0,0.0,0.0} \definecolor{FuncColor}{rgb}{1.0,0.0,0.0} \definecolor{lorange}{rgb}{.952, .902, .86} \definecolor{lpink}{rgb}{.952, .882, .94} \definecolor{purple}{rgb}{0.6179,0.0236,0.4894} \definecolor{LightGreen}{rgb}{0.7544,1.00,0.7511} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{axiom}{Axiom} \newtheorem{remark}{Remark} \numberwithin{equation}{section} \def\ppp{{\mathbb{P}}} \def\aaa{{\mathbb{A}}} \def\fff{{\mathbb{F}}} \def\qqq{\mathbb{Q}} \def\rrr{\mathbb{R}} \def\ccc{\mathbb{C}} \def\zzz{\mathbb{Z}} \def\nnn{\mathbb{N}} \def\pf{\noindent {\bf Proof}:\ } \def\qed{$\Box$} \def\wt{{\rm wt}} \def\supp{{\rm supp}} \newcommand{\SAGE}{{\sf SAGE}\,} \newcommand{\sage}{\SAGE} \begin{document} \author{David Joyner\footnote{Math. Dept., US Naval Academy, wdjoyner@gmail.com} and Robert Miller\footnote{Math. Dept., Univ. Washington, rlm@rlmiller.org}} \title{\sage and Coding Theory} \maketitle \begin{abstract} This brief paper surveys recent work in \sage on implementing algorithms to compute with linear block codes. \color{blue}http://www.sagemath.org\normalcolor \end{abstract} \sage is a mathematical software package similar to the ``big M's'' (Maple, Mathematica, Magma, and Matlab) but free and open source \cite{S}. Download information and manuals are available at \url{http://www.sagemath.org/}. Included in \sage is the group theory package GAP \cite{G} and GUAVA \cite{Gu}, GAP's coding theory package. All of GUAVA's functions can be accessed within \sage. \section{General coding theory functions} Many of the following coding theory functions are pure Python and do not call GUAVA: \begin{enumerate} \item {\tt LinearCode} class definition; {\tt LinearCodeFromVectorspace} conversion function. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: MS = MatrixSpace(GF(2),4,7) sage: G = MS([[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 = LinearCode(G) sage: C Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C.base_ring() Finite Field of size 2 sage: C.dimension() 4 sage: C.length() 7 sage: C.minimum_distance() 3 sage: C.spectrum() [1, 0, 0, 7, 7, 0, 0, 1] sage: C.weight_distribution() [1, 0, 0, 7, 7, 0, 0, 1] \end{Verbatim} This function also enables you to create your own code functions. The following function implements the hexacode. \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] def Hexacode(): """ This function returns the [6,3,4] hexacode over GF(4). It is an extremal (Hermitian) self-dual Type IV code. EXAMPLES: sage: C = Hexacode() sage: C.minimum_distance() 4 """ F = GF(4,"z") z = F.gen() MS = MatrixSpace(F, 3, 6) G = MS([[1, 0, 0, 1, z, z ],\ [0, 1, 0, z, 1, z ],\ [0, 0, 1, z, z, 1 ]]) return LinearCode(G) \end{Verbatim} \item The {\tt spectrum} (weight distribution), \verb+minimum_distance+ programs (calling Steve Linton's C programs in GAP), \verb+characteristic_function+ (as in \cite{vL}), and several implementations of the Duursma zeta function (\verb+zeta_polynomial+, \verb+zeta_function+, \verb+chinen_polynomial+, for example), \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = HammingCode(3,GF(2)) sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C = best_known_linear_code(6,3,GF(2)) sage: C.minimum_distance() 3 sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 \end{Verbatim} \item \verb+gen_mat+, \verb+check_mat+, \verb+decode+, \verb+dual_code+, \verb+extended_code+, \verb+binomial_moment+ for {\tt LinearCode}. The i-th binomial moment of the $[n,k,d]_q$-code $C$ is \[ B_i(C) = \sum_{S, |S|=i} \frac{q^{k_S}-1}{q-1} \] where $k_S$ is the dimension of the shortened code $C_{J-S}$, $J=[1,2,...,n]$. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = HammingCode(3,GF(2)) sage: C.binomial_moment(2) 0 sage: C.binomial_moment(3) # long time 0 sage: C.binomial_moment(4) # long time 35 sage: C = HammingCode(3,GF(2)) sage: MS = MatrixSpace(GF(2),1,7) sage: F = GF(2); a = F.gen() sage: v1 = [a,a,F(0),a,a,F(0),a] sage: C.decode(v1) (1, 0, 0, 1, 1, 0, 1) \end{Verbatim} Decoding, at the moment, merely uses syndrome decoding via GUAVA. \item Boolean-valued functions such as ``=='', \verb+is_self_dual+, \verb+is_self_orthogonal+, \newline \verb+is_permutation_automorphism+, \item permutation methods: \verb+automorphism_group_binary_code+, \newline \verb+is_permutation_automorphism+, \verb+standard_form+, \verb+module_composition_factors+. This later function simply calls up the MeatAxe record from GAP. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = HammingCode(3,GF(2)) sage: G = C.automorphism_group_binary_code(); G Permutation Group with generators [(2,3)(5,7), (2,5)(3,7), (2,3,7,5)(4,6), (2,4)(6,7), (1,2)(3,4)] sage: G.order() 168 sage: C = HammingCode(3,GF(2)) sage: C.gen_mat() [1 0 0 1 0 1 0] [0 1 0 1 0 1 1] [0 0 1 1 0 0 1] [0 0 0 0 1 1 1] sage: C.redundancy_matrix() [1 1 0] [1 1 1] [1 0 1] [0 1 1] sage: C.standard_form()[0].gen_mat() [1 0 0 0 1 1 0] [0 1 0 0 1 1 1] [0 0 1 0 1 0 1] [0 0 0 1 0 1 1] sage: MS = MatrixSpace(GF(2),4,8) sage: G = MS([[1,0,0,0,1,1,1,0],[0,1,1,1,0,0,0,0], [0,0,0,0,0,0,0,1],[0,0,0,0,0,1,0,0]]) sage: C = LinearCode(G) sage: gp = C.automorphism_group_binary_code() sage: C.module_composition_factors(gp) [ rec( field := GF(2), isMTXModule := true, dimension := 1, generators := [ [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 5, 3 ], [ 5, 3 ] ], [ Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0 ] ], algebraElementMatrix := [ [ 0*Z(2) ] ], characteristicPolynomial := x_1, charpolFactors := x_1, nullspaceVector := [ Z(2)^0 ], ndimFlag := 1 ), IsIrreducible := true ), rec( field := GF(2), isMTXModule := true, dimension := 1, generators := [ [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 5, 2 ], [ 1, 2 ] ], [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2) ] ], algebraElementMatrix := [ [ 0*Z(2) ] ], characteristicPolynomial := x_1, charpolFactors := x_1, nullspaceVector := [ Z(2)^0 ], ndimFlag := 1 ), IsIrreducible := true ), rec( field := GF(2), isMTXModule := true, dimension := 1, generators := [ [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 4, 2 ], [ 7, 4 ] ], [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ] ], algebraElementMatrix := [ [ 0*Z(2) ] ], characteristicPolynomial := x_1, charpolFactors := x_1, nullspaceVector := [ Z(2)^0 ], ndimFlag := 1 ), IsIrreducible := true ), rec( field := GF(2), isMTXModule := true, dimension := 1, generators := [ [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 4, 6 ], [ 1, 6 ] ], [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0 ] ], algebraElementMatrix := [ [ Z(2)^0 ] ], characteristicPolynomial := x_1+Z(2)^0, charpolFactors := x_1+Z(2)^0, nullspaceVector := [ Z(2)^0 ], ndimFlag := 1 ), IsIrreducible := true ) ] \end{Verbatim} \item design-theoretic methods: \verb+assmus_mattson_designs+ (implementing the Assmus-Mattson Theorem). \begin{theorem} (Assmus and Mattson Theorem; \S 8.4, page 303 of \cite{HP}) Let $A_0, A_1, ..., A_n$ be the weight distribution of the codewords in a binary linear $[n , k, d]$ code $C$, and let\footnote{For typographical reasons, the output of the program {\tt assmus\_mattson\_designs} uses {\tt C*} instead of $C^\perp$.} $A_0^\perp, A_1^\perp, ..., A_n^\perp$ be the weight distribution of the codewords in its dual $[n,n-k, d^\perp]$ code $C^\perp$. Fix a $t$, $00$ elements called {\bf points}, and $B$ is a non-empty finite multiset of size $b$ whose elements are called {\bf blocks}, such that each block is a non-empty finite multiset of $k$ points. $A$ design without repeated blocks is called a {\bf simple} block design. If every subset of points of size $t$ is contained in exactly $\lambda$ blocks the the block design is called a {\bf $t$--$(v,k,\lambda)$ design} (or simply a $t$-design when the parameters are not specfied). When $\lambda=1$ then the block design is called a {\bf $S(t,k,v)$ Steiner system}. In the Assmus and Mattson Theorem, $X$ is the set $\{1,2,...,n\}$ of coordinate locations and $B = \{supp(c)\ |\ c \in C_i\}$ is the set of supports of the codewords of $C$ of weight $i$. Therefore, the parameters of the $t$-design for $C_i$ are \begin{eqnarray*} t &= {\rm given},\\ v &= n,\\ k &= i,\ \ ({\rm this}\ k\ {\rm is\ not\ to\ be\ confused\ with\ dim}(C)!),\\ b &= A_i,\\ \lambda &= b*binomial(k,t)/binomial(v,t) \end{eqnarray*} (by Theorem 8.1.6, p. 294, in \cite{HP}). Setting the \verb+mode="verbose"+ option prints out the values of the parameters. The first example below means that the binary $[24,12,8]$-code $C$ has the property that the (support of the) codewords of weight 8 (resp, 12, 16) form a 5-design. Similarly for its dual code $C^\perp$ (of course $C=C^\perp$ in this case, so this info is extraneous). The test fails to produce 6-designs (ie, the hypotheses of the theorem fail to hold, not that the 6-designs definitely don't exist). The command \verb+assmus_mattson_designs(C,5,mode="verbose")+ returns the same value but prints out more detailed information. The second example below illustrates the blocks of the $5$--$(24, 8, 1)$ design (ie, the $S(5,8,24)$ Steiner system). EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = ExtendedBinaryGolayCode() # example 1 sage: C.assmus_mattson_designs(5) ['weights from C: ', [8, 12, 16, 24], 'designs from C: ', [[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)], [5, (24, 24, 1)]], 'weights from C*: ', [8, 12, 16], 'designs from C*: ', [[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)]]] sage: C.assmus_mattson_designs(6) 0 sage: X = range(24)# example 2 sage: blocks = [c.support() for c in C if hamming_weight(c)==8] sage: len(blocks) 759 \end{Verbatim} \end{enumerate} The method \verb+automorphism_group_binary_code+ is actually an interface to an extremely fast implementation written by the second author. It uses an open-source implementation of permutation backtracking, written by Robert Miller and developed into a \sage module called {\tt NICE}. This package is described more filly in \cite{M1}. A permutation $g \in S_n$ of the fixed basis gives rise to a permutation of the vectors, or words, in $GF(2)^n$, sending $(w_i)$ to $(w_{g(i)})$. The {\bf (permutation) automorphism group} of the code $C$ is the set of permutations of the indices that bijectively map $C$ to itself. \sage uses a partition refinement algorithm to compute the automorphism group of any binary code. In future work, this will be extended to other base rings. \section{Native constructions} \sage contains GUAVA but most of GUAVA's functions have not been implemented in Python, so they must be called via the GAP interface. (See the GUAVA manual \cite{Gu} for details on the syntax of GUAVA.) In addition, here are some of the special codes implemented natively in Python: \begin{itemize} \item {\tt 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 (contained in) $\{\alpha^{b},\alpha^{b+1}, ..., \alpha^{b+\delta-2}\}$, where $\alpha$ 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$. \newline \url{http://en.wikipedia.org/wiki/BCH_code} EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: FF. = 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 = CyclicCode(8,g); C Linear code of length 8, dimension 4 over Finite Field of size 3 sage: C.minimum_distance() 4 sage: C = 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 = BCHCode(8,3,GF(3)); C Linear code of length 8, dimension 3 over Finite Field of size 3 sage: C.minimum_distance() 5 \end{Verbatim} \item {\tt BinaryGolayCode}, {\tt ExtendedBinaryGolayCode}, {\tt TernaryGolayCode}, \newline {\tt ExtendedTernaryGolayCode} - the well-known ``extremal'' Golay codes, \newline \url{http://en.wikipedia.org/wiki/Golay_code} EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = ExtendedBinaryGolayCode() sage: C Linear code of length 24, dimension 12 over Finite Field of size 2 sage: C.minimum_distance() 8 sage: C.is_self_dual() True sage: C = TernaryGolayCode() sage: C Linear code of length 11, dimension 6 over Finite Field of size 3 sage: C.minimum_distance() 5 \end{Verbatim} \item Cyclic codes - {\tt CyclicCodeFromGeneratingPolynomial} (= {\tt CyclicCode}), {\tt CyclicCodeFromCheckPolynomial}, \newline \url{http://en.wikipedia.org/wiki/Cyclic_code} EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: P. = PolynomialRing(GF(3),"x") sage: g = x-1 sage: C = CyclicCodeFromGeneratingPolynomial(4,g); C Linear code of length 4, dimension 3 over Finite Field of size 3 sage: P. = PolynomialRing(GF(4,"a"),"x") sage: g = x^3+1 sage: C = CyclicCodeFromGeneratingPolynomial(9,g); C Linear code of length 9, dimension 6 over Finite Field in a of size 2^2 sage: P. = PolynomialRing(GF(2),"x") sage: g = x^3+x+1 sage: C = CyclicCodeFromGeneratingPolynomial(7,g); C Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C.gen_mat() [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 = CyclicCodeFromGeneratingPolynomial(4,g); C Linear code of length 4, dimension 3 over Finite Field of size 2 sage: C.gen_mat() [1 1 0 0] [0 1 1 0] [0 0 1 1] sage: P. = PolynomialRing(GF(3),"x") sage: C = CyclicCodeFromCheckPolynomial(4,x + 1); C Linear code of length 4, dimension 1 over Finite Field of size 3 sage: C = CyclicCodeFromCheckPolynomial(4,x^3 + x^2 + x + 1); C Linear code of length 4, dimension 3 over Finite Field of size 3 sage: C.gen_mat() [2 1 0 0] [0 2 1 0] [0 0 2 1] \end{Verbatim} \item {\tt DuadicCodeEvenPair}, {\tt DuadicCodeOddPair} - Constructs the ``even'' (resp. ``odd'') pair of duadic codes associated to a ``splitting'' $S_1$, $S_2$ of $n$. This is a special type of cyclic code whose generator is determined by $S_1$, $S_2$. See chapter 6 in \cite{HP}. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: from sage.coding.code_constructions import is_a_splitting sage: n = 11; q = 3 sage: C = cyclotomic_cosets(q,n); 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, 2) sage: 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) \end{Verbatim} \noindent This is consistent with Theorem 6.1.3 in \cite{HP}. \item {\tt HammingCode} - the well-known Hamming code. The $r^{th}$ Hamming code over $F=GF(q)$ is an $[n,k,d]$ code with length $n=(q^r-1)/(q-1)$, dimension $k=(q^r-1)/(q-1) - r$ and minimum distance $d=3$. 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. \newline \url{http://en.wikipedia.org/wiki/Hamming_code} EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: HammingCode(3,GF(2)) Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C = 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 = HammingCode(3,GF(4,'a')); C Linear code of length 21, dimension 18 over Finite Field in a of size 2^2 \end{Verbatim} \item {\tt LinearCodeFromCheckMatrix} - for specifing the code using the check matrix instead of the generator matrix. A linear $[n,k]$-code $C$ is uniquely determined by its generator matrix $G$ and check matrix $H$. These objects and morphisms fit into the following short exact sequence, \begin{equation} 0 \rightarrow {\mathbf{F}}^k \stackrel{G}{\rightarrow} {\mathbf{F}}^n \stackrel{H}{\rightarrow} {\mathbf{F}}^{n-k} \rightarrow 0. \end{equation} Here, ``short exact'' means (a) the arrow $G$ is injective, i.e., $G$ is a full-rank $k\times n$ matrix, (b) the arrow $H$ is surjective, and (c) ${\rm image}(G)={\rm kernel}(H)$. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = HammingCode(3,GF(2)) sage: H = C.check_mat(); H [1 0 0 1 1 0 1] [0 1 0 1 0 1 1] [0 0 1 1 1 1 0] sage: LinearCodeFromCheckMatrix(H) == C True sage: C = HammingCode(2,GF(3)) sage: H = C.check_mat(); H [1 0 2 2] [0 1 2 1] sage: LinearCodeFromCheckMatrix(H) == C True sage: C = RandomLinearCode(10,5,GF(4,"a")) sage: H = C.check_mat() sage: LinearCodeFromCheckMatrix(H) == C True \end{Verbatim} \item {\tt QuadraticResidueCodeEvenPair}, {\tt 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 \cite{HP}) a QR code exists over $GF(q)$ if and only if $q$ is a quadratic residue $\pmod n$. Here they are constructed as ``even-like'' (resp., ``odd-like'') duadic codes associated the splitting $(Q,N) \pmod n$, where $Q$ is the set of non-zero quadratic residues and $N$ is the non-residues. {\tt QuadraticResidueCode} (a special case) and {\tt ExtendedQuadraticResidueCode} are included as well. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: 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: 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: 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 = QuadraticResidueCodeEvenPair(7,GF(2))[0] sage: C1.is_self_orthogonal() True sage: C2 = QuadraticResidueCodeEvenPair(7,GF(2))[1] sage: C2.is_self_orthogonal() True sage: C3 = QuadraticResidueCodeOddPair(17,GF(2))[0] sage: C4 = QuadraticResidueCodeEvenPair(17,GF(2))[1] sage: C3 == C4.dual_code() True \end{Verbatim} \noindent This is consistent with Theorem 6.6.9 and Exercise 365 in \cite{HP}. \item {\tt RandomLinearCode} - Repeatedly applies \sage's \verb+random_element+ applied to the ambient MatrixSpace of the generator matrix until a full rank matrix is found. \item {\tt ReedSolomonCode} - Also called a ``generalized Reed-Solomon code'' (the ``narrow'' RS codes codes are also cyclic codes; they are part of GUAVA but have not been ported over to natice Python/\sage\, yet). Given a finite field $\fff$ of order $q$, let $n$ and $k$ be chosen such that $1 \leq k \leq n \leq q$. Pick $n$ distinct elements of $\fff$, denoted $\{ x_1, x_2, ... , x_n \}$. Then, the codewords are obtained by evaluating every polynomial in $\fff [x]$ of degree less than $k$ at each $x_i$: \[ C = \left\{ \left( f(x_1), f(x_2), ..., f(x_n) \right)\ |\ f \in \fff[x], {\rm deg}(f) = 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 = 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 \end{Verbatim} \item {\tt ToricCode} - Let $P$ denote a list of lattice points in $\zzz^d$ and let $T$ denote a listing of all points in $(\fff^x )^d$. Put $n=|T|$ and let $k$ denote the dimension of the vector space of functions $V = Span \{x^e \ |\ e \\in P\}$. The associated toric code $C$ is the evaluation code which is the image of the evaluation map $eval_T : V \rightarrow \fff^n$, where $x^e$ is the multi-index notation. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = 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: P = [ [0,0],[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[3,1],[3,2],[4,1]] sage: C = ToricCode(P, GF(8,"a")) sage: C Linear code of length 49, dimension 11 over Finite Field in a of size 2^3 \end{Verbatim} \noindent This is in fact a $[49,11,28]$ code over $GF(8)$. If you type next \verb+C.minimum_distance()+ and wait overnight (!), you will get 28. \item WalshCode - a binary linear $[2^m,m,2^{m-1}]$ code related to Hadamard matrices. \newline \url{http://en.wikipedia.org/wiki/Walsh_code} EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = WalshCode(4); C Linear code of length 16, dimension 4 over Finite Field of size 2 sage: C.minimum_distance() 8 \end{Verbatim} \end{itemize} \section{Bounds} Regarding bounds on coding theory parameters, this module implements: \begin{itemize} \item \verb+best_known_linear_code_www+ (interface with codetables.de since A. Brouwer's online tables have been disabled). Explains the construction of the best known linear code over GF(q) with length n and dimension k, courtesy of the www page \url{http://www.codetables.de/}. INPUT: \begin{itemize} \item \verb+n+ -- integer, the length of the code \item \verb+k+ -- integer, the dimension of the code \item \verb+F+ -- finite field, whose field order must be in [2, 3, 4, 5, 7, 8, 9] \item \verb+verbose+ -- bool (default=False), print verbose message \end{itemize} EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: L = best_known_linear_code_www(72, 36, GF(2)) # requires internet sage: print L Construction of a linear code [72,36,15] over GF(2): [1]: [73, 36, 16] Cyclic Linear Code over GF(2) CyclicCode of length 73 with generating polynomial x^37 + x^36 + x^34 + x^33 + x^32 + x^27 + x^25 + x^24 + x^22 + x^21 + x^19 + x^18 + x^15 + x^11 + x^10 + x^8 + x^7 + x^5 + x^3 + 1 [2]: [72, 36, 15] Linear Code over GF(2) Puncturing of [1] at 1 last modified: 2002-03-20 \end{Verbatim} \verb+bounds_minimum_distance+ which call tables in GUAVA (updated May 2006) created by Cen Tjhai instead of the online internet tables. It simply returns the GAP record for that code: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: print bounds_minimum_distance(10,5,GF(2)) rec( n := 10, k := 5, q := 2, references := rec( ), construction := [ , [ [ , [ [ , [ [ , [ 8, 2 ] ] ] ], [ , [ [ , [ [ , [ 4, 2 ] ] ] ], [ , [ 4, 2 ] ] ] ] ] ], [ 1, 2, 3, 4, 5, 6 ] ] ], lowerBound := 4, lowerBoundExplanation := [ "Lb(10,5)=4, by shortening of:", "Lb(16,11)=4, by the u|u+v construction applied to C1 [8,7,2] and C2 [8,4,4]: ", "Lb(8,7)=2, dual of the repetition code", "Lb(8,4)=4, by the u|u+v construction applied to C1 [4,3,2] and C2 [4,1,4]: ", "Lb(4,3)=2, dual of the repetition code", "Lb(4,1)=4, repetition code" ], upperBound := 4, upperBoundExplanation := [ "Ub(10,5)=4, by the Griesmer bound" ] ) \end{Verbatim} \item \verb+codesize_upper_bound(n,d,q)+, for the best known (as of May, 2006) upper bound $A(n,d)$ for the size of a code of length $n$, minimum distance $d$ over a field of size $q$. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: codesize_upper_bound(10, 3, 2) 85 \end{Verbatim} This means that there is a $(10,85,3)$ binary (non-linear) code. Since $85>2^6$, this is a better code that a $[10,6,3]$ binary (linear) code, assuming one exists. Let's use \verb+best_known_linear_code_www+ to find out: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: L = best_known_linear_code_www(10, 6, GF(2)) sage: print L Construction of a linear code [10,6,3] over GF(2): [1]: [4, 1, 4] Cyclic Linear Code over GF(2) RepetitionCode of length 4 [2]: [4, 3, 2] Cyclic Linear Code over GF(2) Dual of the RepetitionCode of length 4 [3]: [8, 4, 4] Quasicyclic of degree 2 Linear Code over GF(2) PlotkinSum of [2] and [1] [4]: [8, 7, 2] Cyclic Linear Code over GF(2) Dual of the RepetitionCode of length 8 [5]: [16, 11, 4] Linear Code over GF(2) PlotkinSum of [4] and [3] [6]: [15, 11, 3] Linear Code over GF(2) Puncturing of [5] at 1 [7]: [10, 6, 3] Linear Code over GF(2) Shortening of [6] at { 11 .. 15 } last modified: 2001-01-30 \end{Verbatim} Not only does a $[10,6,3]$ binary linear code exist, the value $d=3$ is the minimum distance is best known for $n=10$, $k=6$. \item \verb+dimension_upper_bound(n,d,q)+, an upper bound $B(n,d)=B_q(n,d)$ for the dimension of a linear code of length n, minimum distance d over a field of size q. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: dimension_upper_bound(10, 3, 2) 6 \end{Verbatim} This was established in the example above. \item \verb+gilbert_lower_bound(n,q,d)+, a lower bound for number of elements in the largest code of minimum distance $d$ in $\fff_q^n$. \item \verb+gv_info_rate(n,delta,q)+, namely $log_q(GLB)/n$, where GLB is the Gilbert lower bound above and \verb+delta+ $= d/n$. Let \[ R = R(C) = \frac{k}{n}, \] which measures the information rate of the code, and \[ \delta = \delta(C) = \frac{d}{n}, \] which measures the error correcting ability of the code. Let $\Sigma_q$ denote the set of all $(\delta,R)\in [0,1]^2$ such that there exists a sequence $C_i$, $i=1,2,...$, of $[n_i,k_i,d_i]$-codes for which $\lim_{i\rightarrow \infty} d_i/n_1=\delta$ and $\lim_{i\rightarrow \infty} k_i/n_i=R$. The following theorem describes information-theoretical limits on how ``good'' a linear code can be. \begin{theorem} (Manin \cite{SS}, chapter 1) There exists a continuous decreasing function \[ \alpha_q:[0,1]\rightarrow [0,1], \] such that \begin{itemize} \item $\alpha_q$ is strictly decreasing on $[0,{\frac{q-1}{q}}]$, \item $\alpha_q(0)=1$, \item if ${\frac{q-1}{q}}\leq x\leq 1$ then $\alpha_q(x)=0$, \item $\Sigma_q=\{(\delta,R)\in [0,1]^2\ |\ 0\leq R\leq \alpha_q(\delta)\}$. \end{itemize} \end{theorem} Not a single value of $\alpha_q(x)$ is known for $00$, there exists an $(n,k,d)$-code $C$ (which may depend on $\epsilon$) with \[ R(C)+\delta(C)\geq 1- \delta(C)\log_q({\frac{q-1}{q}})-\delta(C)\log_q(\delta(C))- (1-\delta(C))\log_q(1-\delta(C))-\epsilon. \] \end{theorem} The curve $(\delta, 1- \delta\log_q({\frac{q-1}{q}})-\delta\log_q(\delta)- (1-\delta)\log_q(1-\delta)))$ is called the {\bf Gilbert-Varshamov curve}. \item \verb+gv_bound_asymp(delta,q)+, asymptotic analog of the Gilbert lower bound. \vskip .1in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: f = lambda x: gv_bound_asymp(x,2) sage: plot(f,0,1/2) \end{Verbatim} \vskip .1in \noindent The plot is in Figure \ref{fig:gv-bound-asymp}. \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} %\vspace{1.0 cm} \includegraphics[height=4cm,width=8cm]{gv-bound-asymp.eps} \end{center} \end{minipage} \caption{Plot of the Gilbert-Varshamov curve using \sage (i.e., $y=$gv\_bound\_asymp$(x,2)$).} \label{fig:gv-bound-asymp} \end{figure} \item \verb+plotkin_upper_bound(n,q,d)+ \item \verb+plotkin_bound_asymp(delta,q)+, asymptotic analog of the Plotkin upper bound. \noindent The plot is in Figure \ref{fig:plotkin-bound-asymp}. \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} %\vspace{1.0 cm} \includegraphics[height=4cm,width=8cm]{plotkin-bound-asymp.eps} \end{center} \end{minipage} \caption{Plot using \sage of $y=$plotkin\_bound\_asymp$(x,2)$.} \label{fig:plotkin-bound-asymp} \end{figure} \item \verb+griesmer_upper_bound(n,q,d)+, the Griesmer upper bound. \item \verb+elias_upper_bound(n,q,d)+, the Elias upper bound. \item \verb+elias_bound_asymp(delta,q)+, asymptotic analog of the Elias upper bound. \noindent The plot is in Figure \ref{fig:elias-bound-asymp}. \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} %\vspace{1.0 cm} \includegraphics[height=4cm,width=8cm]{elias-bound-asymp.eps} \end{center} \end{minipage} \caption{Plot using \sage of $y=$elias\_bound\_asymp$(x,2)$.} \label{fig:elias-bound-asymp} \end{figure} \item \verb+hamming_upper_bound(n,q,d)+, the Hamming upper bound. \item \verb+hamming_bound_asymp(delta,q)+, asymptotic analog of the Hamming upper bound. \noindent The plot is in Figure \ref{fig:hamming-bound-asymp}. \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} %\vspace{1.0 cm} \includegraphics[height=4cm,width=8cm]{hamming-bound-asymp.eps} \end{center} \end{minipage} \caption{Plot using \sage of $y=$hamming\_bound\_asymp$(x,2)$.} \label{fig:hamming-bound-asymp} \end{figure} \item \verb+singleton_upper_bound(n,q,d)+, the Singleton upper bound. \item \verb+singleton_bound_asymp(delta,q)+, asymptotic analog of the Singleton upper bound. \noindent The plot is in Figure \ref{fig:singleton-bound-asymp}. \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} %\vspace{1.0 cm} \includegraphics[height=4cm,width=8cm]{singleton-bound-asymp.eps} \end{center} \end{minipage} \caption{Plot using \sage of $y=$singleton\_bound\_asymp$(x,2)$.} \label{fig:singleton-bound-asymp} \end{figure} \item \verb+mrrw1_bound_asymp(delta,q)+, ``first'' asymptotic McEliese-Rumsey-Rodemich-Welsh upper bound for the information rate \cite{HP}. \noindent The plot is in Figure \ref{fig:mrrw1-bound-asymp}. \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} %\vspace{1.0 cm} \includegraphics[height=4cm,width=8cm]{mrrw1-bound-asymp.eps} \end{center} \end{minipage} \caption{Plot using \sage of $y=$mrrw1\_bound\_asymp$(x,2)$.} \label{fig:mrrw1-bound-asymp} \end{figure} \end{itemize} Here are all the bounds together: \vskip .1in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: f1 = lambda x: gv_bound_asymp(x,2) sage: P1 = plot(f1,0,1/2,linestyle=":") sage: f2 = lambda x: plotkin_bound_asymp(x,2) sage: P2 = plot(f2,0,1/2,linestyle="--") sage: f3 = lambda x: elias_bound_asymp(x,2) sage: P3 = plot(f3,0,1/2,rgbcolor=(1,0,0)) sage: f4 = lambda x: singleton_bound_asymp(x,2) sage: P4 = plot(f4,0,1/2,linestyle="-.") sage: f5 = lambda x: mrrw1_bound_asymp(x,2) sage: P5 = plot(f5,0,1/2,linestyle="steps") sage: f6 = lambda x: hamming_bound_asymp(x,2) sage: P6 = plot(f6,0,1/2,rgbcolor=(0,1,0)) sage: show(P1+P2+P3+P4+P5+P6) \end{Verbatim} \vskip .1in \noindent The plot is in Figure \ref{fig:all-bounds-asymp}. \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} %\vspace{1.0 cm} \includegraphics[height=7cm,width=7cm]{all-bounds-asymp.eps} \end{center} \end{minipage} \caption{Plot of the Gilbert-Varshamov (dotted), Elias (red), Plotkin (dashed), Singleton (dash-dotted), Hamming (green), and MRRW (stepped) curves using \sage.} \label{fig:all-bounds-asymp} \end{figure} \section{Self-dual codes} \sage also includes a database of all self-dual binary codes of length $\leq 20$ (and some of length $22$). The main function is \verb+self_dual_codes_binary+, which is a case-by-case list of entries, each represented by a Python dictionary. Format of each entry: a Python dictionary with keys \verb"order autgp", \verb"spectrum", \verb"code", \verb"Comment", \verb"Type", where \begin{itemize} \item \verb"code" - a self-dual code $C$ of length $n$, dimension $n/2$, over $GF(2)$, \item \verb"order autgp" - order of the permutation automorphism group of $C$, \item \verb"Type" - the type of $C$ (which can be "I" or "II", in the binary case), \item \verb"spectrum" - the spectrum $[A_0,A_1,...,A_n]$, \item \verb"Comment" - possibly an empty string. \end{itemize} In fact, in Table 9.10 of \cite{HP}, the number $B_n$ of inequivalent self-dual binary codes of length $n$ is given: \vskip .1in \begin{tabular}{c|ccccccccccccccc} $n$ & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 \\ \hline $B_n$ & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 7 & 9 & 16 & 25 & 55 & 103 & 261 & 731\\ \end{tabular} \vskip .1in \noindent According to an entry in Sloane's Online Encyclopedia of Integer Sequences, \url{http://www.research.att.com/~njas/sequences/A003179}, the next 2 entries are: 3295, 24147. EXAMPLES: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = self_dual_codes_binary(10)["10"] sage: C["0"]["code"] == C["0"]["code"].dual_code() True sage: C["1"]["code"] == C["1"]["code"].dual_code() True sage: len(C.keys()) # number of inequiv sd codes of length 10 2 sage: C = self_dual_codes_binary(12)["12"] sage: C["0"]["code"] == C["0"]["code"].dual_code() True sage: C["1"]["code"] == C["1"]["code"].dual_code() True sage: C["2"]["code"] == C["2"]["code"].dual_code() True \end{Verbatim} These \sage \, commands simply show that the two inequivalent self-dual binary codes of length 10, and the two inequivalent self-dual binary codes of length 12, are indeed self dual. A lot of work on the classification of doubly even self-orthogonal codes using \sage can be found at \url{http://www.rlmiller.org/de_codes/}. The number of permutation equivalence classes of all doubly even $[n,k]$--codes is shown in the table at \url{http://www.rlmiller.org/de_codes/}, and the list of codes so far discovered is linked from the list entries. Each link on that webpage points to a Sage object file, which when loaded (e.g., \newline \verb+sage: L = load('24_12_de_codes.sobj')+) is a list of matrices in standard form. The algorithm is described in \cite{M2}. \begin{thebibliography}{99} \bibitem[G]{G} The GAP Group, {\tt GAP} -- Groups, Algorithms, and Programming, Version 4.4.10; 2007. \url{http://www.gap-system.org}. \bibitem[Gu]{Gu} GUAVA, a coding theory package for GAP, \url{http://sage.math.washington.edu/home/wdj/guava/}. \bibitem[HP]{HP} W. C. Huffman and V. Pless, {\bf Fundamentals of error-correcting codes}, Cambridge Univ. Press, 2003. \bibitem[M1]{M1} Robert Miller, {\it Graph automorphism computation}, \url{http://www.rlmiller.org/talks/nauty.pdf}, March 2007. \bibitem[M2]{M2} ------, {\it Doubly even codes}, \url{http://www.rlmiller.org/talks/June_Meeting.pdf}, June 2007. \bibitem[S]{S} The \sage\, Group, \sage: {\it Mathematical software}, version 3.0. \newline \url{http://www.sagemath.org/}. \bibitem[SS]{SS} S. Shokranian and M.A. Shokrollahi, {\bf Coding theory and bilinear complexity}, Scientific Series of the International Bureau, KFA J\"ulich Vol. 21, 1994. \bibitem[vL]{vL} J. van Lint, {\bf Introduction to coding theory, 3rd ed.}, Springer-Verlag GTM, 86, 1999. %\bibitem[]{} \end{thebibliography} \end{document}