Module guava

The binary 'Reed-Muller code' with dimension k and 
order r is a code with length $2^k$ and minimum distance $2^k-r$
(see for example, section 1.10 in [HP]). By definition, the
$r^{th}$ order binary Reed-Muller code of length $n=2^m$, for
$0 \leq r \leq m$, is the set of all vectors $(f(p)\ |\ p \\in GF(2)^m)$,
where $f$ is a multivariate polynomial of degree at most $r$ in $m$ variables.
    
INPUT:
    r, k -- positive integers with $2^k>r$.

OUTPUT:
    Returns the binary 'Reed-Muller code' with dimension k and order r. 

EXAMPLE:
    sage: C = BinaryReedMullerCode(2,4)
    sage: C
    Linear code of length 16, dimension 11 over Finite Field of size 2
    sage: C.minimum_distance()
    4
    sage: C.gen_mat()
    [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
    [0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1]
    [0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1]
    [0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1]
    [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
    [0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1]
    [0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1]
    [0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1]
    [0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1]
    [0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1]
    [0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1]

AUTHOR: David Joyner (11-2005)

A (binary) quasi-quadratic residue code (or QQR code), as defined by 
Proposition 2.2 in [BM], has a generator matrix in the block form $G=(Q,N)$. 
Here $Q$ is a $p \\times p$ circulant matrix whose top row 
is $(0,x_1,...,x_{p-1})$, where $x_i=1$ if and only if $i$ 
is a quadratic residue $\mod p$, and $N$ is a $p \\times p$ circulant matrix whose top row
is $(0,y_1,...,y_{p-1})$, where $x_i+y_i=1$ for all i. 
    
INPUT:
    p -- a prime >2.

OUTPUT: 
    Returns a QQR code of length 2p.

EXAMPLES:
    sage: C = QuasiQuadraticResidueCode(11)
    sage: C
    Linear code of length 22, dimension 11 over Finite Field of size 2

REFERENCES:
    [BM] Bazzi and Mitter, {\it Some constructions of codes from group actions}, (preprint
         March 2003, available on Mitter's MIT website). 
    [J]  D. Joyner, {\it On quadratic residue codes and hyperelliptic curves}, (preprint 2006)
    
These are self-orthogonal in general and self-dual when $p \\equiv 3 \\pmod 4$.

AUTHOR: David Joyner (11-2005)

The method used is to first construct a $k \\times n$ matrix of the block form $(I,A)$, 
where $I$ is a $k \\times k$ identity matrix and $A$ is a $k \\times (n-k)$ matrix
constructed using random elements of $F$. Then the columns are permuted 
using a randomly selected element of the symmetric group $S_n$.

INPUT:
    Integers n,k, with n>k>1.

OUTPUT:
    Returns a "random" linear code with length n, dimension k over field F. 

EXAMPLES:
    sage: C = RandomLinearCode(30,15,GF(2))
    sage: C
    Linear code of length 30, dimension 15 over Finite Field of size 2
    sage: C = RandomLinearCode(10,5,GF(4,'a'))
    sage: C
    Linear code of length 10, dimension 5 over Finite Field in a of size 2^2

AUTHOR: David Joyner (11-2005)