source: sage/coding/linear_code.py @ 0:039f6310c6fe

Revision 0:039f6310c6fe, 23.7 KB checked in by tornaria@…, 7 years ago (diff)

[project @ original sage-0.10.12]
Line 
1r"""
2Linear Codes
3
4 TODO: CURRENT NOT DONE / INTEGRATED INTO SAGE YET
5
6VERSION: 0.1
7
8AUTHOR:
9    -- David Joyner (2005-11-22, 2006-12-03): written
10    -- William Stein (2006-01-23) -- Inclusion in SAGE
11    -- David Joyner (2006-01-25, 2006-12-03): small fixed to use sage_eval
12   
13This file contains
14\begin{enumerate}
15\item LinearCode, Codeword class definitions
16\item The spectrum (weight distribution) and minimum distance
17    programs (calling Steve Linton's C programs)
18\item interface with A. Brouwer's online tables
19\item wrapped GUAVA's HammingCode, RandomLinearCode,
20    Golay codes, binary Reed-Muller code
21\item implemented some GAP-to-SAGE conversion of finite field elements.
22\item gen_mat, check_mat, decode, dual_code method for LinearCode.
23\end{enumerate}
24
25To be added:
26\begin{enumerate}
27\item PermutedCode method (with PermutationGroupElement as argument).
28\item More wrappers
29\item automorphism group.
30\item cyclic codes
31\item GRS codes and special decoders.
32\item $P^1$ Goppa codes and group actions.
33\end{enumerate}
34
35Many commands require GUAVA to be installed but not Leon's code.
36"""
37
38#*****************************************************************************
39#       Copyright (C) 2005 David Joyner <wdj@usna.edu>
40#                     2006 William Stein <wstein@ucsd.edu>
41#
42#  Distributed under the terms of the GNU General Public License (GPL)
43#
44#                  http://www.gnu.org/licenses/
45#*****************************************************************************
46
47import copy
48import sage.modules.free_module as fm
49import sage.modules.module as module
50import sage.modules.free_module_element as fme
51from sage.databases.lincodes import *
52from sage.interfaces.all import gap
53from sage.misc.preparser import *
54from sage.matrix.matrix_space import *
55from sage.rings.finite_field import *
56from sage.misc.sage_eval import sage_eval
57
58VectorSpace = fm.VectorSpace
59
60###################### coding theory functions ##############################
61
62def wtdist(Gmat, F): 
63    """
64    INPUT:
65        Gmat -- a string representing a GAP generator matrix G of a linear code.
66        F -- a (SAGE) finite field - the base field of the code.
67       
68    OUTPUT:
69        Returns the spectrum of the associated code.
70
71    EXAMPLES:
72    sage: Gstr = 'Z(2)*[[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]]'
73    sage: F = GF(2)
74    sage: wtdist(Gstr, F)
75    [1, 0, 0, 7, 7, 0, 0, 1]
76
77    Here Gstr is a generator matrix of the Hamming [7,4,3] binary code.
78
79    ALGORITHM: Uses C programs written by Steve Linton in the kernel
80    of GAP, so is fairly fast.
81
82    AUTHOR: David Joyner (2005-11)
83    """ 
84    q = F.order()
85    G = gap(Gmat)
86    k = gap(F)
87    C = G.GeneratorMatCode(k)
88    n = int(C.WordLength())
89    z = 'Z(%s)*%s'%(q, [0]*n)     # GAP zero vector as a string
90    d = G.DistancesDistributionMatFFEVecFFE(k, z)
91    return d.sage()
92
93def min_wt_vec(Gmat,F): 
94    """
95    INPUT:
96    Same as wtdist.
97    OUTPUT:
98    Returns a minimum weight vector v, the "message" vector m such that m*G = v,
99    and the (minimum) weight, as a triple.
100
101    EXAMPLES:
102    sage: Gstr = "Z(2)*[[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]]"
103    sage: min_wt_vec(Gstr,GF(2))
104    [[0, 1, 0, 1, 0, 1, 0], [0, 0, 1, 0], 3]
105
106    Here Gstr is a generator matrix of the Hamming [7,4,3] binary code.
107    Uses C programs written by Steve Linton in the kernel of GAP, so it fairly fast.
108
109    AUTHOR: David Joyner (11-2005)
110    """ 
111    gap.eval("G:="+Gmat)
112    k = eval(gap.eval("Length("+Gmat+")"))
113    q = F.order()
114    qstr = str(q)
115    gap.eval("C:=GeneratorMatCode("+Gmat+",GF("+qstr+"))")
116    n = eval(gap.eval("WordLength(C)"))
117    zerovec = [0 for i in range(n)]
118    zerovecstr = "Z("+qstr+")*"+str(zerovec)
119    all = []
120    for i in range(1,k+1):
121        P = gap.eval("P:=AClosestVectorCombinationsMatFFEVecFFECoords("+Gmat+", GF("+qstr+"),"+zerovecstr+","+str(i)+","+str(0)+"); d:=WeightVecFFE(P[1])")
122        v = gap.eval("v:=List(P[1], i->i)")
123        m = gap.eval("m:=List(P[2], i->i)")
124        dist = gap.eval("d")
125        #print v,m,dist
126        #print [gap.eval("v["+str(i+1)+"]") for i in range(n)]
127        all.append([[sage_eval(gap.eval("v["+str(i+1)+"]"))
128                              for i in range(n)],
129                    [sage_eval(gap.eval("m["+str(i+1)+"]"))
130                              for i in range(k)],eval(dist)])
131    ans = all[0]
132    for x in all:
133        if x[2]<ans[2] and x[2]>0:
134            ans = x
135    return ans
136
137def minimum_distance_lower_bound(n,k,F):
138        """
139        Connects to http://www.win.tue.nl/~aeb/voorlincod.html
140        Tables of A. E. Brouwer,   Techn. Univ. Eindhoven,
141        via Steven Sivek's linear_code_bound.
142
143        EXAMPLES:
144        sage: coding.minimum_distance_upper_bound(7,4,GF(2))
145        3
146
147        Obviously requires an internet connection.
148        """
149        q = F.order()
150        bounds = linear_code_bound(q,n,k)
151        return bounds[0]
152
153def minimum_distance_upper_bound(n,k,F):
154        """
155        Connects to http://www.win.tue.nl/~aeb/voorlincod.html
156        Tables of A. E. Brouwer,   Techn. Univ. Eindhoven
157        via Steven Sivek's linear_code_bound.
158       
159        EXAMPLES:
160        sage: coding.minimum_distance_upper_bound(7,4,GF(2))
161        3
162       
163        Obviously requires an internet connection.
164        """
165        q = F.order()
166        bounds = linear_code_bound(q,n,k)
167        return bounds[1]
168
169def minimum_distance_why(n,k,F):
170        """
171        Connects to http://www.win.tue.nl/~aeb/voorlincod.html
172        Tables of A. E. Brouwer,   Techn. Univ. Eindhoven
173        via Steven Sivek's linear_code_bound.
174       
175        EXAMPLES:
176        sage: coding.minimum_distance_why(7,4,GF(2))
177        Lb(7,4) = 3 is found by truncation of:
178        Lb(8,4) = 4 is found by the (u|u+v) construction
179        applied to [4,3,2] and [4,1,4]-codes
180        Ub(7,4) = 3 follows by the Griesmer bound.
181
182        Obviously requires an internet connection.
183        """
184        q = F.order()
185        bounds = linear_code_bound(q,n,k)
186        print bounds[2]
187
188
189########################### linear codes python class #######################
190
191class LinearCode(module.Module):
192    """
193    class for linear codes over a finite field or finite ring
194    INPUT:
195    A $k\times n$ matrix $G$ of rank $k$, $k\leq n$, over
196    a finite field $F$.
197    OUTPUT:
198    The linear code of length $n$ over $F$ having $G$ as a
199    generator matrix.
200 
201    EXAMPLES:
202        sage: MS = MatrixSpace(GF(2),4,7)
203        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]])
204        sage: C  = LinearCode(G)
205        sage: C
206        Linear code of length 7, dimension 4 over Finite field of size 2
207        sage: C.minimum_distance_upper_bound()
208        3
209        sage: C.base_ring()
210        Finite field of size 2
211        sage: C.dimension()
212        4
213        sage: C.length()
214        7
215        sage: C.minimum_distance()
216        3
217        sage: C.spectrum()
218        [1, 0, 0, 7, 7, 0, 0, 1]
219        sage: C.weight_distribution()
220        [1, 0, 0, 7, 7, 0, 0, 1]
221        sage: C.minimum_distance_why()
222        Ub(7,4) = 3 follows by the Griesmer bound.
223
224    AUTHOR: David Joyner (11-2005)
225    """
226    def __init__(self, gen_mat):
227        self.__gens = gen_mat.rows()
228        self.__gen_mat = gen_mat
229        self.__base_ring = gen_mat[0][0].parent()
230        self.__length = len(gen_mat[1])
231        self.__dim = gen_mat.rank()
232
233    def length(self):
234        return self.__length
235
236    def dimension(self):
237        return self.__dim
238
239    def base_ring(self):
240        return self.__base_ring
241
242    def _repr_(self):
243        return "Linear code of length %s, dimension %s over %s"%(self.length(), self.dimension(), self.base_ring())
244
245    def gen_mat(self):
246        return self.__gen_mat
247
248    def gens(self):
249        return self.__gens
250
251    def basis(self):
252        return self.__gens
253
254    def ambient_space(self):
255        return VectorSpace(self.__base_ring,self.__length)
256
257    def __contains__(self,v):
258        A = self.ambient_space()
259        C = A.subspace(self.gens())
260        return C.__contains__(v)
261
262    def characteristic(self):
263        return (self.base_ring()).characteristic()
264
265    def minimum_distance_upper_bound(self):
266        """
267        Connects to http://www.win.tue.nl/~aeb/voorlincod.html
268        Tables of A. E. Brouwer,   Techn. Univ. Eindhoven
269       
270        Obviously requires an internet connection
271        """
272        q = (self.base_ring()).order()
273        n = self.length()
274        k = self.dimension()
275        bounds = linear_code_bound(q,n,k)
276        return bounds[1]
277
278    def minimum_distance_why(self):
279        """
280        Connects to http://www.win.tue.nl/~aeb/voorlincod.html
281        Tables of A. E. Brouwer,   Techn. Univ. Eindhoven
282       
283        Obviously requires an internet connection.
284        """
285        q = (self.base_ring()).order()
286        n = self.length()
287        k = self.dimension()
288        bounds = linear_code_bound(q,n,k)
289        lines = bounds[2].split("\n")
290        for line in lines:
291            if len(line)>0:
292                if line[0] == "U":
293                    print line
294
295    def minimum_distance(self):
296        """
297        Uses a GAP kernel function (in C) written by Steve Linton.
298
299        EXAMPLES:
300        sage: MS = MatrixSpace(GF(3),4,7)
301        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]])
302        sage: C = LinearCode(G)
303        sage: C.minimum_distance()
304              3
305        sage: C=RandomLinearCode(10,5,GF(4))
306        sage: C.gen_mat()
307
308[    1     0     0     0     0 x + 1     1     0     0     0]
309[x + 1     1     0     1     0 x + 1     1     1     0     0]
310[    0 x + 1     0 x + 1     0     x x + 1 x + 1 x + 1     0]
311[    1     0     x     0     1     0     0     0     0     1]
312[    0     0     1     1     0     0     0     0     x x + 1]
313        sage: C.minimum_distance()
314      2
315        sage: C.minimum_distance_upper_bound()
316      5
317        sage: C.minimum_distance_why()
318Ub(10,5) = 5 follows by the Griesmer bound.
319
320
321        """
322        F = self.base_ring()
323        q = F.order()
324        G = self.gen_mat()
325        #k=len(G.rows())
326        #n=len(G.columns())
327        Gstr=str(gap(G))+"*Z("+str(q)+")"
328        return min_wt_vec(Gstr,F)[2]
329
330
331    def spectrum(self):
332        """
333        Uses a GAP kernel function (in C) written by Steve Linton.
334        EXAMPLES:
335
336        """
337        F = self.base_ring()
338        q = F.order()
339        G = self.gen_mat()
340        Glist = [list(x) for x in G] 
341        Gstr = "Z("+str(q)+")*"+str(Glist)
342        spec = wtdist(Gstr,F) 
343        return spec
344       
345    def weight_distribution(self):
346        #same as spectrum
347        return self.spectrum()
348
349    def __cmp__(self, right):
350        raise NotImplementedError
351
352    def decode(self, right):
353        """
354        Wraps GUAVA's Decodeword.
355        INPUT:
356        right must be a vector of length = length(self)
357        OUTPUT:
358        The codeword c in C closest to r.
359
360        Hamming codes have a special decoding algorithm. Otherwise, syndrome decoding is used.
361
362        EXAMPLES:
363        sage: C = HammingCode(3,GF(2))
364        sage: MS = MatrixSpace(GF(2),1,7)
365        sage: F=GF(2); a=F.gen()
366        sage: v=MS([a,a,F(0),a,a,F(0),a]); v
367        [1 1 0 1 1 0 1]
368        sage: C.decode(v)
369        [1 1 0 1 0 0 1]
370
371        Does not work for very long codes since the syndrome table grows too large.
372        """
373        F = self.base_ring()
374        q = F.order()
375        G = self.gen_mat()
376        n = len(G.columns())
377        k = len(G.rows())
378        Gstr = sage2gap_matrix_finite_field_string(G,k,n,F)         
379        vstr = sage2gap_matrix_finite_field_string(right,1,n,F)
380        v = vstr[1:-1]
381        gap.eval("C:=GeneratorMatCode("+Gstr+",GF("+str(q)+"))")
382        ans = gap.eval("c:=VectorCodeword(Decodeword( C, Codeword( "+v+" )))")
383        return gap2sage_matrix_finite_field(ans,1,n,F)
384
385
386    def dual_code(self):
387        """
388        Wraps GUAVA's DualCode.
389        OUTPUT:
390        The dual code.
391
392        EXAMPLES:
393        sage: C = HammingCode(3,GF(2))
394        sage: C.dual_code()
395        Linear code of length 7, dimension 3 over Finite field of size 2
396        sage: C = HammingCode(3,GF(4))
397        sage: C.dual_code()
398        Linear code of length 21, dimension 3 over Finite field in x of size 2^2
399
400        """
401        F = self.base_ring()
402        q = F.order()
403        G = self.gen_mat()
404        n = len(G.columns())
405        k = len(G.rows())
406        Gstr = str(gap(G))         
407        gap.eval("C:=GeneratorMatCode("+Gstr+",GF("+str(q)+"))")
408        Hmat = gap.eval("H:=CheckMat( C )")
409        H = [[sage_eval(gap.eval("H["+str(i)+"]["+str(j)+"]"))
410              for j in range(1,n+1)] for i in range(1,n-k+1)]
411        MS = MatrixSpace(F,n-k,n)
412        return LinearCode(MS(H))
413
414    def check_mat(self):
415        """
416        Returns the check matrix of self.
417
418        EXAMPLES:
419
420        sage: C = HammingCode(3,GF(2))
421        sage: Cperp = C.dual_code()
422        sage: C; Cperp
423Linear code of length 7, dimension 4 over Finite field of size 2
424Linear code of length 7, dimension 3 over Finite field of size 2
425        sage: C.gen_mat()
426
427[1 1 1 0 0 0 0]
428[1 0 0 1 1 0 0]
429[0 1 0 1 0 1 0]
430[1 1 0 1 0 0 1]
431        sage: C.check_mat()
432
433[0 1 1 1 1 0 0]
434[1 0 1 1 0 1 0]
435[1 1 0 1 0 0 1]
436        sage: Cperp.check_mat()
437
438[1 1 1 0 0 0 0]
439[1 0 0 1 1 0 0]
440[0 1 0 1 0 1 0]
441[1 1 0 1 0 0 1]
442        sage: Cperp.gen_mat()
443
444[0 1 1 1 1 0 0]
445[1 0 1 1 0 1 0]
446[1 1 0 1 0 0 1]
447
448
449        """
450        Cperp = self.dual_code()
451        return Cperp.gen_mat()
452
453######### defining the Codeword class by copying the FreeModuleElement class:
454Codeword = fme.FreeModuleElement
455Codeword.support = fme.FreeModuleElement.nonzero_positions
456is_Codeword = fme.is_FreeModuleElement
457"""
458    EXAMPLE:
459    sage: MS = MatrixSpace(GF(2),4,7)
460    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]])
461    sage: C = LinearCode(G)
462    sage: C.basis()
463
464          [(1, 1, 1, 0, 0, 0, 0),
465           (1, 0, 0, 1, 1, 0, 0),
466           (0, 1, 0, 1, 0, 1, 0),
467           (1, 1, 0, 1, 0, 0, 1)]
468    sage: c = C.basis()[1]
469    sage: c in C
470          True
471    sage: c.nonzero_positions()
472          [0, 3, 4]
473    sage: c.support()
474          [0, 3, 4]
475    sage: is_Codeword(c)
476          True
477    sage: c.parent()
478          Vector space of dimension 7 over Finite field of size 2
479"""
480
481##################### wrapped GUAVA functions ############################
482
483def HammingCode(r,F):
484    """
485    INPUT:
486    Integer r>1 and finite field F.
487    OUTPUT:
488    Returns the $r^{th}$ Hamming code over $F=GF(q)$ of length $n=(q^r-1)/(q-1)$.
489    Requires GUAVA.
490
491    EXAMPLES:
492    sage: C = HammingCode(3,GF(3))
493    sage: C
494          Linear code of length 13, dimension 10 over Finite field of size 3
495    sage: C.minimum_distance()
496          3
497    sage: C.gen_mat()
498
499[2 2 1 0 0 0 0 0 0 0 0 0 0]
500[1 2 0 1 0 0 0 0 0 0 0 0 0]
501[2 0 0 0 2 1 0 0 0 0 0 0 0]
502[1 0 0 0 2 0 1 0 0 0 0 0 0]
503[0 2 0 0 2 0 0 1 0 0 0 0 0]
504[2 2 0 0 2 0 0 0 1 0 0 0 0]
505[1 2 0 0 2 0 0 0 0 1 0 0 0]
506[0 1 0 0 2 0 0 0 0 0 1 0 0]
507[2 1 0 0 2 0 0 0 0 0 0 1 0]
508[1 1 0 0 2 0 0 0 0 0 0 0 1]
509    sage: C = HammingCode(3,GF(4))
510    sage: C
511      Linear code of length 21, dimension 16 over Finite field in x of size 2^2
512
513    AUTHOR: David Joyner (11-2005)
514    """
515    q = F.order()
516    gap.eval("C:=HammingCode("+str(r)+", GF("+str(q)+"))")
517    gap.eval("G:=GeneratorMat(C)")
518    k = eval(gap.eval("Length(G)"))
519    n = eval(gap.eval("Length(G[1])"))
520    G = [[sage_eval(gap.eval("G["+str(i)+"]["+str(j)+"]")) for j in range(1,n+1)] for i in range(1,k+1)]
521    MS = MatrixSpace(F,k,n)
522    return LinearCode(MS(G))
523   
524def QuadraticResidueCode(n,F):
525    """
526    INPUT:
527    Prime n>2 and finite prime field F of order q. Moreover,
528    q must be a quadratic residue modulo n.
529    OUTPUT:
530    Returns a quadratic residue code. Its generator polynomial is the product
531    of the polynomials $x-\alpha^i$ ($\alpha$ is a primitive $n^{th}$ root of unity,
532    and $i$ is an integer in the set of quadratic residues modulo $n$).
533    Requires GUAVA.
534
535    EXAMPLES:
536    sage: C = QuadraticResidueCode(7,GF(2))
537    sage: C
538          Linear code of length 7, dimension 4 over Finite field of size 2
539    sage: C = QuadraticResidueCode(17,GF(2))
540    sage: C
541          Linear code of length 17, dimension 9 over Finite field of size 2
542
543    AUTHOR: David Joyner (11-2005)
544    """
545    q = F.order()
546    gap.eval("C:=QRCode("+str(n)+", GF("+str(q)+"))")
547    gap.eval("G:=GeneratorMat(C)")
548    k = eval(gap.eval("Length(G)"))
549    n = eval(gap.eval("Length(G[1])"))
550    G = [[sage_eval(gap.eval("G["+str(i)+"]["+str(j)+"]")) for j in range(1,n+1)] for i in range(1,k+1)]
551    MS = MatrixSpace(F,k,n)
552    return LinearCode(MS(G))
553
554def QuasiQuadraticResidueCode(p):
555    """
556    INPUT:
557    p must be a prime >2.
558    OUTPUT:
559    Returns a (binary) quasi-quadratic residue code, as defined by
560    Proposition 2.2 in Bazzi-Mittel ({\it Some constructions of codes from group actions},
561    (preprint March 2003). Its generator matrix has the block form $G=(Q,N)$.
562    Here $Q$ is a $p\times p$ circulant matrix whose top row
563    is $(0,x_1,...,x_{p-1})$, where $x_i=1$ if and only if $i$
564    is a quadratic residue $\mod p$, and $N$ is a $p\times p$
565    circulant matrix whose top row is $(0,y_1,...,y_{p-1})$, where
566    $x_i+y_i=1$ for all i. (In fact, this matrix can be recovered
567    as the component DoublyCirculant of the code.)
568    Requires GUAVA.
569
570    EXAMPLES:
571    sage: time C = QuasiQuadraticResidueCode(31)
572Time: CPU 2.11 s, Wall: 102.49 s
573    sage: C
574      Linear code of length 62, dimension 31 over Finite field of size 2
575
576    AUTHOR: David Joyner (11-2005)
577    """
578    F = GF(2)
579    gap.eval("C:=QQRCode("+str(p)+")")
580    gap.eval("G:=GeneratorMat(C)")
581    k = eval(gap.eval("Length(G)"))
582    n = eval(gap.eval("Length(G[1])"))
583    G = [[sage_eval(gap.eval("G["+str(i)+"]["+str(j)+"]")) for j in range(1,n+1)] for i in range(1,k+1)]
584    MS = MatrixSpace(F,k,n)
585    return LinearCode(MS(G))
586
587def BinaryReedMullerCode(r,k):
588    """
589    INPUT:
590    Positive integers r,k with $2^k>r$.
591    OUTPUT:
592    Returns a binary 'Reed-Muller code' with dimension k and order r. 
593    This is a code with length $2^k$ and minimum distance $2^k-r$ (see
594    for example, section 1.10 in Huffman-Pless {\it Fundamentals of Coding Theory}).
595    By definition, the $r^{th}$ order binary Reed-Muller code of
596    length $n=2^m$, for $0 \leq r \leq m$, is the set of
597    all vectors $(f(p)\ |\ p in GF(2)^m)$, where $f$ is a
598    multivariate polynomial of degree at most $r$ in $m$ variables.
599    Requires GUAVA.
600
601    EXAMPLE:
602    sage: C = BinaryReedMullerCode(2,4)
603    sage: C
604          Linear code of length 16, dimension 11 over Finite field of size 2
605    sage: C.minimum_distance()
606          4
607    sage: C.gen_mat()
608
609        [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
610        [0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1]
611        [0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1]
612        [0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1]
613        [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
614        [0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1]
615        [0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1]
616        [0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1]
617        [0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1]
618        [0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1]
619        [0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1]
620
621    AUTHOR: David Joyner (11-2005)
622    """
623    F = GF(2)
624    gap.eval("C:=ReedMullerCode("+str(r)+", "+str(k)+")")
625    gap.eval("G:=GeneratorMat(C)")
626    k = eval(gap.eval("Length(G)"))
627    n = eval(gap.eval("Length(G[1])"))
628    G = [[sage_eval(gap.eval("G["+str(i)+"]["+str(j)+"]")) for j in range(1,n+1)] for i in range(1,k+1)]
629    MS = MatrixSpace(F,k,n)
630    return LinearCode(MS(G))
631
632def BinaryGolayCode():
633    """
634    BinaryGolayCode returns a binary Golay code. This is a
635    perfect [23,12,7] code. It is also cyclic, and has
636    generator polynomial $g(x)=1+x^2+x^4+x^5+x^6+x^{10}+x^{11}$.
637    Extending it results in an extended Golay code (see
638    ExtendedBinaryGolayCode).
639    Requires GUAVA.
640
641    EXAMPLE:
642    sage: C = BinaryGolayCode()
643    sage: C
644          Linear code of length 23, dimension 12 over Finite field of size 2
645    sage: C.minimum_distance()
646          7
647
648    AUTHOR: David Joyner (11-2005)
649    """
650    F = GF(2)
651    gap.eval("C:=BinaryGolayCode()")
652    gap.eval("G:=GeneratorMat(C)")
653    k = eval(gap.eval("Length(G)"))
654    n = eval(gap.eval("Length(G[1])"))
655    G = [[sage_eval(gap.eval("G["+str(i)+"]["+str(j)+"]")) for j in range(1,n+1)] for i in range(1,k+1)]
656    MS = MatrixSpace(F,k,n)
657    return LinearCode(MS(G))
658
659def ExtendedBinaryGolayCode():
660    """
661    BinaryGolayCode returns the extended binary Golay code. This
662    is a perfect [24,12,8] code. This code is self-dual.
663    Requires GUAVA.
664
665    EXAMPLE:
666    sage: C = ExtendedBinaryGolayCode()
667    sage: C
668          Linear code of length 24, dimension 12 over Finite field of size 2
669    sage: C.minimum_distance()
670          8
671
672    AUTHOR: David Joyner (11-2005)
673    """
674    F = GF(2)
675    gap.eval("C:=ExtendedBinaryGolayCode()")
676    gap.eval("G:=GeneratorMat(C)")
677    k = eval(gap.eval("Length(G)"))
678    n = eval(gap.eval("Length(G[1])"))
679    G = [[sage_eval(gap.eval("G["+str(i)+"]["+str(j)+"]")) for j in range(1,n+1)] for i in range(1,k+1)]
680    MS = MatrixSpace(F,k,n)
681    return LinearCode(MS(G))
682
683def TernaryGolayCode():
684    """
685    TernaryGolayCode returns a ternary Golay code. This is a
686    perfect [11,6,5] code. It is also cyclic, and has generator
687    polynomial $g(x)=2+x^2+2x^3+x^4+x^5$.
688    Requires GUAVA.
689
690    EXAMPLE:
691    sage: C = TernaryGolayCode()
692    sage: C
693          Linear code of length 11, dimension 6 over Finite field of size 3
694    sage: C.minimum_distance()
695          5
696
697    AUTHOR: David Joyner (11-2005)
698    """
699    F = GF(3)
700    gap.eval("C:=TernaryGolayCode()")
701    gap.eval("G:=GeneratorMat(C)")
702    k = eval(gap.eval("Length(G)"))
703    n = eval(gap.eval("Length(G[1])"))
704    G = [[sage_eval(gap.eval("G["+str(i)+"]["+str(j)+"]")) for j in range(1,n+1)] for i in range(1,k+1)]
705    MS = MatrixSpace(F,k,n)
706    return LinearCode(MS(G))
707
708def ExtendedTernaryGolayCode():
709    """
710    ExtendedTernaryGolayCode returns a ternary Golay code.
711    This is a self-dual perfect [12,6,6] code.
712    Requires GUAVA.
713
714    EXAMPLE:
715    sage: C = ExtendedTernaryGolayCode()
716    sage: C
717          Linear code of length 11, dimension 6 over Finite field of size 3
718    sage: C.minimum_distance()
719          6
720    sage: C.gen_mat()
721
722        [1 0 2 1 2 2 0 0 0 0 0 1]
723        [0 1 0 2 1 2 2 0 0 0 0 1]
724        [0 0 1 0 2 1 2 2 0 0 0 1]
725        [0 0 0 1 0 2 1 2 2 0 0 1]
726        [0 0 0 0 1 0 2 1 2 2 0 1]
727        [0 0 0 0 0 1 0 2 1 2 2 1]
728
729    AUTHOR: David Joyner (11-2005)
730    """
731    F = FiniteField(3)
732    gap.eval("C:=ExtendedTernaryGolayCode()")
733    gap.eval("G:=GeneratorMat(C)")
734    k = eval(gap.eval("Length(G)"))
735    n = eval(gap.eval("Length(G[1])"))
736    G = [[sage_eval(gap.eval("G["+str(i)+"]["+str(j)+"]")) for j in range(1,n+1)] for i in range(1,k+1)]
737    MS = MatrixSpace(F,k,n)
738    return LinearCode(MS(G))
739
740def RandomLinearCode(n,k,F):
741    """
742    INPUT:
743    Integers n,k, with n>k>1.
744    OUTPUT:
745    Returns a random linear code with length n, dimension k over field F.
746    The method used is to first construct a $k\times n$ matrix of the block form $(I,A)$,
747    where $I$ is a $k\times k$ identity matrix and $A$ is a $k\times (n-k)$
748    matrix constructed using random elements of $F$. Then the columns are permuted
749    using a randomly selected element of SymmetricGroup(n).
750    Requires GUAVA.
751
752    EXAMPLES:
753    sage: time C = RandomLinearCode(30,15,GF(2))
754Time: CPU 0.31 s, Wall: 0.44 s
755    sage: C
756      Linear code of length 30, dimension 15 over Finite field of size 2
757    sage: time C = RandomLinearCode(10,5,GF(4))
758Time: CPU 0.02 s, Wall: 0.10 s
759    sage: C
760      Linear code of length 10, dimension 5 over Finite field in x of size 2^2
761
762    AUTHOR: David Joyner (11-2005)
763    """
764    q = F.order()
765    gap.eval("C:=RandomLinearCode("+str(n)+","+str(k)+", GF("+str(q)+"))")
766    gap.eval("G:=GeneratorMat(C)")
767    k = eval(gap.eval("Length(G)"))
768    n = eval(gap.eval("Length(G[1])"))
769    G = [[sage_eval(gap.eval("G["+str(i)+"]["+str(j)+"]")) for j in range(1,n+1)] for i in range(1,k+1)]
770    MS = MatrixSpace(F,k,n)
771    return LinearCode(MS(G))
772
773
774
775
Note: See TracBrowser for help on using the repository browser.