A polynomial-time probabilistic algorithm for the minimum distance of a non-binary linear error-correcting code
Wayne Irons
April 22, 2005


Contents

The goal of the project is to examine a polynomial-time probabilistic algorithm to compute the minimum distance of an arbitrary, non-binary, linear error-correcting code. Only the binary case was done in A. Foster's honors project [F]. For the non-binary case a new function was needed in the GAP kernel. This function was added by Steve Linton of St. Andrews, Scotland, one of GAP's kernel maintainers, in August 2004. The programming shall be done in the GAP coding-theory package GUAVA. GAP is a computer algebra package whose open source kernel is written in the C programming language [GAP]. However, most packages (such as GUAVA) and the algorithms described here are written in GAP's own interpreted language. Jointly, with my advisor, I extended Foster's work (Algorithm 4) to the non-binary case but with a new feature making it faster (Algorithm 5). The paper ends with applications to the non-binary McEliece public key cryptosystem (see §4) and trace codes (see §3)

Acknowledgement: The GAP examples were performed on an AMD-64 linux PC with 2G of RAM. I am grateful to the Director of Research Professor Reza Malek-Madani for making this available.

Introduction

When sending a message across a noisy channel, the message must first be converted into a binary sequence. Different types of error correcting codes exist, however, we will only consider block codes. A block code has the property that every element can be described as a word in an alphabet of a fixed length. We will only consider the case when the alphabet consists of elements of a finite field, and regard a word in the alphabet as a vector with coordinates in the finitle field. Error-correcting block codes are used primarily to transmit data across a noisy channel. Block codes allow for error correction by means of source encoding which adds redundant information onto each message vector being sent. A source encoder converts the data into codewords which are then transmitted across a medium. Depending on the nature of the information being sent and the amount of noise in the channel, we choose a block code with the suitable amount of redundancy to accurately recover the message being sent. In every application known to us, the block code is a set of binary vectors of a fixed number of coordinates $ n$. Therefore, the message being sent must be split into pieces of length $ n$. The parameter $ n$ depends on the nature of the application.

Let $ \mathbb{F}=GF(q)$ be a finite field with $ q$ elements. We call a subset of $ \mathbb{F}^n$ a (block) code. A linear code is a subspace of the vector space $ {\mathbb{F}}^n$. The length of the code is the integer $ n$. A generator matrix of a linear code can be any matrix whose rows form a basis for the subspace. Let $ C$ be a linear code of length $ n$ over $ {\mathbb{F}}$ with generator matrix $ G$, where $ q$ is a power of a prime $ p$. In this case if $ \mathbf{m}$ is a row vector in $ \mathbf{F}^{k}$, then $ \mathbf{c}=\mathbf{m}G$ is a codeword in C. Moreover, all codewords in C arise from some message vector $ \mathbf{m}$ this way. This defines the encoder from the message space $ \mathbb{F}^{k}$ to the code C. If $ p=2$, then the code is called binary. We assume that $ {\mathbb{F}}^{n}$ has been given the standard basis $ \mathbf{e}_{1}=(1,0,...,0)\in {\mathbb{F}}^{n}$, $ \mathbf{e}_{2}=(0,1,0,...,0)\in {\mathbb{F}}^{n}$, ..., $ \mathbf{e}_{n}=(0,0,...,0,1)\in {\mathbb{F}}^{n}$. The dimension of $ C$ is denoted $ k$, so the number of elements of $ C$ is equal to $ q^{k}$. The quantity $ R=k/n$ is called the rate of the code and measures the amount of information that the code can transmit.

Example 1   Consider the code $ C_1$ over $ GF(3)$ with generator matrix $ G_1$ given by

\begin{displaymath} \left( \begin{array}{ccccccc} 1&0&0&0&1&1&2 \\ 0&1&0&0&0&1&1 \\ 0&0&1&0&2&0&1 \\ 0&0&0&1&2&1&0 \end{array}\right) \end{displaymath}

and consider the code $ C_2$ over $ GF(3)$ with generator matrix $ G_2$ given by

\begin{displaymath} \left( \begin{array}{ccccccc} 1&0&0&1&0&1&2 \\ 0&1&0&0&0&1&1 \\ 0&0&1&2&0&0&1 \\ 0&0&0&2&1&1&0 \end{array}\right). \end{displaymath}

Notice that these two codes are identical except that the 4th and 5th columns have been swapped. Therefore they are equivalent to each other in the sense defined below.

Two codes are equivalent to each other if one can be obtained from the other by a combination of permutations of coordinate positions of the code and multiplication of the symbols appearing in a fixed position by a non-zero scalar. More precisely, two codes are equivalent if the generator matrix of one can be derived from the other using operations of the following types:

  1. Permutation of the rows.
  2. Multiplication of a row by a non-zero scalar.
  3. Addition of a scalar multiple of one row to another.
  4. Permutation of the columns.

  5. Multiplication of any column by a non-zero scalar.
Two codes are permutation equivalent if one generator matrix can be obtained from the other by using operations of only type 4.

Lemma 1   Every linear code $ C$ of length $ n$ and dimension $ k$ is permutation equivalent to a code $ C'$ with a generator matrix of the form $ (I_{k} \vert A)$, where $ A$ is a $ k \times (n-k)$ matrix.

Please see [HILL] or MacWilliams and Sloane [MS] for a proof of this fact. A code with generator matrix in the form above is said to be in standard form.

Another important parameter associated to the code is the number of errors which it can, in principle, correct. For this notion, let us introduce the concept of distance between codewords. For any two $ \mathbf{x},\mathbf{y}\in {\mathbb{F}}^n$, let $ d(\mathbf{x},\mathbf{y})$ denote the number of coordinates where these two vectors differ:

$\displaystyle d(\mathbf{x},\mathbf{y})=\vert\{0\leq i\leq n \vert x_{i}\not=y_{i}\}\vert.$ (1)

This defines the Hamming metric on the space $ {\mathbb{F}}^n$. Define the weight $ w$ of $ \mathbf{x}$ to be the number of non-zero entries of $ \mathbf{x}$. Note, $ d(\mathbf{x},\mathbf{y})=w(\mathbf{x}-\mathbf{y})$ because the vector $ \mathbf{x}-\mathbf{y}$ has non-zero entries only at locations where $ \mathbf{x}$ and $ \mathbf{y}$ differ.

If $ d(C)$ denotes the smallest distance between distinct codewords in a linear code $ C$,then there exist $ \mathbf{x}$ and $ \mathbf{y}$ such that $ d(C)=d(\mathbf{x},\mathbf{y})$. If $ M$ is any matrix with coefficents in $ {\mathbb{F}}$, then let $ d(M)$ denote the minimum distance of the linear code spanned by the rows of $ M$.

Lemma 2  

$\displaystyle d(C)=\min_{\mathbf{c}\in C, \mathbf{c}\not= \mathbf{0}}d(\mathbf{0},\mathbf{c}).$ (2)

Proof: Note that $ d(C)=w(\mathbf{x}-\mathbf{y}) \geq w(C)$, where $ w(C)$ is the minimum weight of a non-zero codeword in $ C$. Also, for some codeword $ \mathbf{z}$, $ w(C)=w(\mathbf{z})=d(\mathbf{0},\mathbf{z})\geq d(C)$. Therefore, $ w(C)=d(C)$.$ \Box$

Note, if $ C$ is equivalent to $ C'$, then $ d(C)=d(C')$. In general, this parameter is known to be very difficult to efficiently determine [CHA]. In fact, computing it in general is known to be NP-complete [BMT], [VAR].

Let $ C$ be a linear code. We say $ C$ is $ e$ error-correcting provided for any vector $ \mathbf{v}$ in $ \mathbb{F}^n$ there is exactly one codeword $ \mathbf{c}\in C$ for which $ d(\mathbf{c},\mathbf{v}) \leq e$.

Lemma 3   A linear code $ C$ is $ e$-error-correcting if and only if $ d(C)\geq 2e+1$. In other words, if $ d=d(C)$ then $ C$ is $ [(d-1)/2]$-error-correcting.

Proof: Let $ \mathbf{c}$ be a codeword. Let $ B(\mathbf{c},e)$ denote a ball of radius $ e$ centered at $ \mathbf{c}$. Since $ C$ is $ e$ error correcting, any two such balls must be disjoint. Therefore, the distance between their centers cannot be less than or equal to $ 2e$. This proves ``the only if'' part. For the ``if'' part of the proof, note that $ d(C)\geq 2e+1$ implies that any two such balls are disjoint. Suppose that $ C$ is not $ e$ error-correcting, in other words, the ball of radius $ e$ centered at $ \mathbf{v}$ contains distinct codewords $ \mathbf{c}$ and $ \mathbf{c'}$. By the triangle inequality for the Hamming metric, $ B(\mathbf{c},e)\cap B(\mathbf{c'},e)$ contains $ \mathbf{v}$. This contradicts the fact that they must be disjoint. $ \Box$

Notation: Let $ \mathbb{E}$ denote a field extension of the finite field $ \mathbb{F}$.

First we must explain how each element of $ \mathbb{E}$ may be represented as an invertible matrix with entries in $ \mathbb{F}$.

Let $ \alpha\in\mathbb{E}$ denote a generator of the cyclic group $ \mathbb{E}^\times$. Let $ f(x)$ denote the minimal polynomial of $ \alpha$ (the lowest degree monic polynomial which has $ \alpha$ as a root). Take the matrix associated to $ \alpha$, denoted $ A$, to be the companion matrix of $ f(x)$ (namely the characteristic polynomial of $ A$ is $ f$). If the degree of $ f(x)$ is $ m$, then $ A$ is an $ m\times m$ matrix with coefficients in $ \mathbb{F}$ (and the degree of $ \mathbb{E}/\mathbb{F}$ is $ m$). If $ \beta\in\mathbb{E}$ denotes any other non-zero element, then we can write $ \beta=\alpha^i$, for some $ i$ (because $ \mathbb{E}^\times$ is a cyclic group). Take the matrix associated to $ \beta$ to be $ B=A^i$. The matrix associated to $ 0\in\mathbb{E}$ will be the $ m\times m$ zero matrix.

We define the trace of $ x\in\mathbb{E}$ to be the trace of the corresponding matrix. Denote this trace by $ Trace_{\mathbb{E}/\mathbb{F}}(x)$. Let $ C$ denote a linear code over $ \mathbb{E}$. The trace code of $ C$ is defined to be

$\displaystyle Trace_{\mathbb{E}/\mathbb{F}}(C)=\{(Trace_{\mathbb{E}/\mathbb{F}}(c_1),..., Trace_{\mathbb{E}/\mathbb{F}}(c_n)) \vert (c_1,...,c_n)\in C\}. $

Note that this is a vector space over $ \mathbb{F}$ therefore is a linear code over $ \mathbb{F}$. The length of this code is $ n$, but the dimension and minimum distance are more difficult to determine.

Algorithms

The naive method for calculating the minimum distance is to examine the weight of every possible linear combination of rows in $ G$.

Algorithm 1   Brute Force Minimum Distance.

Input: A code $ C$ of length n containing $ M$ elements over $ \mathbb{F}$.

Output: The minimum distance of $ C$.

  1. Initialize $ {\tt mindist}=n$ and select $ minword$ to be an arbitrary element in $ C$.
  2. For $ \mathbf{c}$ in $ C$ compute the weight $ {\tt wt}=w(\mathbf{c})$, if $ {\tt wt}<{\tt mindist}$ then $ {\tt mindist}={\tt wt}$ and $ {\tt minword}=\mathbf{c}$.
  3. Return: $ {\tt mindist}$ and $ {\tt minword}$.

In the above algorithm $ C$ is not required to be linear. For linear codes the following algorithm is much faster.

Algorithm 2  
  1. After replacing $ C$ by a permutation equivalent code $ C'$, if necessary, one may assume the generator matrix has the following form: $ G=(I_{k} \vert A)$, for some $ k \times (n-k)$ matrix $ A$.

  2. If $ A=0$ then $ d(C)=1$.

  3. Find the minimum distance of the code spanned by the rows of $ A$. Call this distance $ d(A)$. Note that $ d(A)$ is equal to the Hamming distance $ d({\bf v},{\bf0})$ where $ {\bf v}$ is some proper linear combination of $ i$ distinct rows of $ A$.

  4. $ d(C)=d(A)+i$, where $ i$ is as in step (2).

By ``proper linear combination'', we mean to exclude the case where all coefficients are equal to 0.

Though this is still an exponential time algorithm problem, the vectors being compared are of length $ n-k$ rather than length $ n$. Additionally, this algorithm works for all Galois fields of order $ q\geq 2$. (We remark that step 2 in the above algorithm was missing from the implementation of MinimumDistance in the last release of GUAVA. This bug is fixed in version 2.0.)

The probabilistic algorithm used to reduce this to polynomial time was initially proposed by J. S. Leon [LEO] and later modified by F. Chabaud [CHA]. One version of the algorithm given in Chabaud's paper is as follows:

Algorithm 3   Let $ q$ be a power of a prime $ p$ and let $ C$ be a linear code of dimension $ k$ over $ GF(q)$ as above. This algorithm has input parameters $ s$ and $ \rho$, where $ s$ is an integer between $ 2$ and $ n-k$, and $ \rho$ is an integer between $ 2$ and $ k$.

(1)
Find a generator matrix $ G$ of $ C$.

(2)
Randomly permute the columns of $ G$.

(3)
Perform Gaussian elimination on the permuted matrix to obtain a new matrix of the following form:

$\displaystyle G=(I_{k} \vert Z \vert B)$ (3)

with $ Z$ a $ k\times s$ matrix. If $ Z$ and $ B$ are both 0 then return $ d(C)=1$. If $ Z$ is 0 but $ B$ is non-zero, then go back to step (2).

(4)
Search $ Z$ for at most $ \rho$ rows that lead to codewords of weight less than $ \rho$.

(5)
For these codewords, compute the weight of the whole word.

However, sometimes step (3) is impossible because Gaussian elimination does not always produce a matrix in standard form. For example, take any code with generator matrix in row reduced echelon form which is not of the form $ (I \vert A)$.

Here is a faster version of Leon's algorithm.

Algorithm 4  

Notation as in Algorithm 3.

(1)
Replace, if necessary, $ C$ by a permutation equivalent code $ C'$ with a generator matrix in standard form, $ G=(I_{k} \vert A)$.

(2)
Select $ s$ columns at random from the matrix $ A$ and call the resulting $ k\times s$ matrix $ Z$.

(3)
For each $ i\leq \rho$, find the linear combination of exactly $ i$ rows of $ Z$ for vectors of smallest weight. If $ Z=0$, then return $ d(C)=1$.

(4)
For these vectors, compute the weight of the associated codeword.

(5)
Find the minimum weight of the codewords from (4). Call this $ d_Z$.

(6)
Repeat this algorithm some multiple $ m$ times and return the most commonly occurring value of $ d_Z$.

Chabaud [CHA] and Barg [BARG] have discussed finding optimal values for $ \rho$, $ s$, and $ m$.

The previous two algorithms were discussed in A. Foster's thesis [F], although only implemented in GUAVA for binary codes. The next algorithm is original to this thesis and forms the basis of our application to non-binary McEliece public key cryptosystems. This application is discussed in section 4.

Algorithm 5   Notation as in Algorithm 3.
(1)
Select $ s$ columns at random from the matrix $ G$.

(2)
For each $ i\leq \rho$, find the linear combination of exactly $ i$ rows of $ G$ for vectors of smallest weight.

(3)
For these vectors, compute the weight of the associated codeword.

(4)
Find the minimum weight of the codewords from (3). Call this $ d_0$.

(5)
Repeat this algorithm some multiple $ m$ times and return the most commonly occurring value of $ d_0$.

Examples of the above algorithm are given in a later section.

The next algorithm is used in this project as well as Lennon's project [L] for testing purposes.

Algorithm 6   Nearest Neighbor List Decoding.

Input: A code $ C$ of length n containing $ M$ elements over $ \mathbb{F}$, an integer $ s\geq [(d-1)/2]$, a word $ \mathbf{v} \in \mathbb{F}^n$

Output: The list of all codewords within Hamming Distance $ s$ from $ \mathbf{v}$

  1. Initialize $ L=\{ \}$
  2. For $ \mathbf{c}$ in $ C$ compute the weight $ {\tt wt}=w(\mathbf{c-v})$, if $ {\tt wt}\leq s$ then append $ \mathbf{c}$ to list $ L$.
  3. Return: $ L$.

We remark that if $ s<[(d-1)/2]$ then the algorithm still works but may return an empty list.

Algorithm 7   Trace Code Construction.

Input: A linear code $ C$ of length $ n$ over $ \mathbb{E}$ where $ \mathbb{E}$ is an extension field of $ \mathbb{F}$

Output: The Trace Code of $ C$

  1. Initialize $ Tr(C)=\{ \}$
  2. For $ \mathbf{c}$ in $ C$ compute the trace $ Tr(\mathbf{c})$, and append it to the list $ Tr(C)$.
  3. Compute a basis of $ Tr(C)$ over $ \mathbb{F}$ and compute a generator matrix for $ Tr(C)$
  4. Return: $ Tr(C)$ and the generator matrix.


Application to Trace Codes

In the example below we compute the minimum distance of several randomly chosen Trace codes where $ \mathbb{F}$ is the field with $ 4$ elements and $ \mathbb{E}$ is the field with $ 16$ elements. 

gap> F:=GF(4);
GF(2^2)
gap> FF:=GF(16);
GF(2^4)
gap> Read("/home/irons/gapfiles/TraceCode.gap");
gap> C:=RandomLinearCode(15,4,F);
a  [15,4,?] randomly generated code over GF(4)
gap>  TC:=TraceCode(C,F);time;
a linear [15,4,1..8]6..11 user defined unrestricted code over GF(4)
126
gap> MinimumDistance(C);
7
gap> MinimumDistance(TC);
7
gap> C:=RandomLinearCode(15,4,FF);
a  [15,4,?] randomly generated code over GF(16)
gap>  TC:=TraceCode(C,F);time;
a linear [15,8,1..4]4..7 user defined unrestricted code over GF(4)
31061
gap> MinimumDistance(C);
10
gap> MinimumDistance(TC);
4
gap> C:=RandomLinearCode(15,4,FF);
a  [15,4,?] randomly generated code over GF(16)
gap> TC:=TraceCode(C,F);time;
a linear [15,8,1..6]4..7 user defined unrestricted code over GF(4)
31542
gap> MinimumDistance(C);
10
gap> MinimumDistance(TC);
5
gap> C:=RandomLinearCode(15,4,FF);
a  [15,4,?] randomly generated code over GF(16)
gap> TC:=TraceCode(C,F);time;
a linear [15,8,1..4]4..7 user defined unrestricted code over GF(4)
33973
gap> MinimumDistance(C);
10
gap> MinimumDistance(TC);
4


Application to McEliece Public Key Cryptosystem

We follow section 1.2 of [CHA].

Here is a brief description of this cryptosystem. Alice is sending a message to Bob. Eve is trying to read Alice's message. Given is a $ [n,k,d]$ non-binary code with generator matrix $ G$ and also given is a decoding algorithm that corrects up to $ t$ errors. Input parameters are an invertible $ k\times k$ matrix $ S$ and an $ n\times n$ permutation matrix $ P$. The triplet $ (S,G,P)$ will be the secret key and the pair $ (t,\hat{G}=SGP)$ will be the public key. Everyone knows the public key, but Alice and Bob are the only two who know the secret key. For Alice to transmit a $ k$ bit message $ m$, she sends the cipher text $ c=m\hat{G}+e$, where $ e$ is a random vector of weight at most $ t$. To decipher the cipher text Bob decodes $ cP^{-1}=mSG+eP^{-1}$ using the given algorithm.

To decrypt an encoded message, consider the matrix

\begin{displaymath} G'=\left( \begin{array}{c} \hat{G}\\ m\hat{G}+e \end{array}\right) . \end{displaymath}

This is the generator matrix of a linear code $ C'$ with minimum weight codeword $ e$. Note that $ e$ is the only vector in $ C'$ of minimum weight, by construction. Algorithm 4 can be modified to yield not only the minimum distance, but also a vector of minimum weight. Using this fact Eve can solve for $ e$, and therefore she can solve for the message $ m$ sent by Alice. This example illustrates the usefulness of fast minimum distance algorithms for cracking certain types of McEliece cryptosystems.

The GAP code below illustrates how to use the MinimumDistanceRandom command described in Algorithm 5 to break the McEliece cryptosystem cipher. 

gap>  F:=GF(16);
GF(2^4)
gap>  C := ReedSolomonCode( 15, 10 );
a cyclic [15,6,10]7..9 Reed-Solomon code over GF(16)
gap>  G:=GeneratorMat(C);;
gap>  g:=Random(SymmetricGroup(15));;
gap>  v:=ShallowCopy(NullWord( 15, F));
[ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2),
  0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2) ]

gap>  v[1]:=One(F);;
gap>  v[2]:=One(F);;
gap>  v[3]:=One(F);;
gap>  v[4]:=One(F);;
gap>  v[5]:=One(F);;
gap>  e:=Permuted(v,g);;
gap>  c0:=Random(C);;
gap>  w:=VectorCodeword(c0+e);;
gap>  Gnew:=Concatenation(G,[w]);;
gap>  Cnew:=GeneratorMatCode(Gnew,F); time;

a linear [15,7,1..9]6..8 code defined by generator matrix over GF(16)
49109

gap> MinimumDistanceRandom(Cnew,10,13);time;

 This is a probabilistic algorithm which may return the wrong answer.
[ 5, [ 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 ] ]
158361
gap> e;
[ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0,
  0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0 ]
Notice the error vector $ \mathbf{e}$ matches the minimum weight vector returned by MinimumDistanceRandom, as desired.

Appendix: GAP Code 

BruteForceMindist:=function(C)
local n,c,w, mindist, minword, Cwords;
Cwords:=Elements(C);
n:=WordLength(C);
mindist:=n; #initialize
minword:=Cwords[1]; #initialize
for c in Cwords do
w:=WeightCodeword(c);
 if w >0 and w < mindist then
mindist:=w;
minword:=c;   
 fi;
od;
return [mindist,minword];
end;


NearestNeighborDecodeword:=function(r,C,dist)
local Cwords,NearbyWords,c;
Cwords:=Elements(C);
NearbyWords:=[];
for c in Cwords do
 if WeightCodeword(r-c) < dist then
   NearbyWords:=Concatenation(NearbyWords,[c]); 
 fi;
od;
return NearbyWords;
end;

C:=NordstromRobinsonCode(  );
          a (16,256,6)4 Nordstrom-Robinson code over GF(2)
r:=Codeword("1100000000000000");
          [ 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
r in C;
          false
NearestNeighborDecodeword(r,C,3);
NearestNeighborDecodeword(r,C,4);
NearestNeighborDecodeword(r,C,5);

CodeLength:= function (C)
return WordLength(C);
end;

TraceCode:= function (C,F)
#C is defined over an extension of F
#F is a base field
local FF, TC, TrC, i, n, c;
n:= CodeLength(C);
FF:= LeftActingDomain(C);
TC:= List(C,c->Codeword(List([1..n],i->Trace(FF,F,c[i]))));
TrC:=ElementsCode(TC, F);
IsLinearCode(TrC);
return TrC;
end;

###################################################
## MinimumDistanceRandom( <C>, <num>, <s> )
##
## This is a simpler version than Leon's method, which does not put G in st form.
## (this works welland is in some cases faster than the st form one)
## Input: C is a linear code 
##        num is an integer >0 which represents the number of iterations
##        s is an integer between 1 and n which represents the columns considered
##           in the algorithm.
## Output: an integer >= min dist(C), and hopefully equal to it!
##         a codework of that weight
##
## Algorithm: randomly permute the columns of the gen mat G of C
##              by a permutation rho - call new mat Gp
##            break Gp into (A,B), where A is kxs and B is kx(n-s)
##            compute code C_A generated by rows of A
##            find min weight codeword c_A of C_A and w_A=wt(c_A)
##              using AClosestVectorCombinationsMatFFEVecFFECoords
##            extend c_A to a corresponding codeword c_p in C_Gp
##            return c=rho^(-1)(c_p) and wt=wt(c_p)=wt(c)
##
MinimumDistanceRandom:= function(C,num,s) 
	local A,HasZeroRow,majority,G0, Gp, Gpt, Gt, L, k, n, i, j, m, dimMat, J, d1,M,
	arrayd1, Combo, rows, row, rowSum, G, F, zero, AClosestVec, B, ZZ,  p, numrow0,
        bigwtrow,bigwtvec, x, d, v, ds, vecs,rho,perms,g,newv,pos,rowcombos,v1,v2;
# returns the estimated distance, and corresponding vector of that weight
Print("\n This is a probabilistic algorithm which may return the wrong answer.\n");
	G0 := GeneratorMat(C);
	p:=5; #this seems to be an optimal value
              # it's the max number of rows used in Z to find a small
              # codewd in C_Z
        G := List(G0,ShallowCopy);

	F:=LeftActingDomain(C);
	dimMat := DimensionsMat(G);
	n:=dimMat[2];
	k:=dimMat[1];
        if n=k then 
           C!.lowerBoundMinimumDistance := 1; 
           C!.upperBoundMinimumDistance := 1; 
           return 1; 
        fi; #  added 11-2004
	if s > n-1 then 
            Print("Resetting s to ",n-2," ... \n"); 
            s:=n-k; 
        fi;
	arrayd1:=[n];

        numrow0:=0; # initialize
        perms:=[]; # initialize

   for m in [1..num] do
   ##Permute the columns of C randomly
	Gt := TransposedMat(G);
	Gp := NullMat(n,k);
	L := SymmetricGroup(n);
	rho := Random(L);
	L:=List([1..n],i->OnPoints(i,rho));
	for i in [1..n] do 
		Gp[i] := Gt[L[i]];
	od;
	Gp := TransposedMat(Gp);
        Gp := List(Gp,ShallowCopy);

##generate the matrix A from Gp=(A|B)
	Gpt := TransposedMat(Gp);
	A := NullMat(s,k);
	for i in [1..s] do
		A[i] := Gpt[i];
	od;
	A := TransposedMat(A);

##generate the matrix B from Gp=(A|B)
	Gpt := TransposedMat(Gp);
	B := NullMat(n-s,k);
	for i in [s+1..n] do
		B[i-s] := Gpt[i];
	od;
	B := TransposedMat(B);

	zero := Zero(F)*A[1];
	if (s<n-k and A=Zero(F)*A) then 
           Error("This method fails for these parameters. Try increasing s.\n");
        fi; 
        if (s=n and A=Zero(F)*A) then 
           return 1; 
        fi;                 

## search for all rows of weight p
## J is the list of all triples representing the codeword in C which
## corresponds to AClosestVec[1].

	J := []; #col number of codewords to compute the length of
	for i in [1..p] do
        	AClosestVec:=AClosestVectorCombinationsMatFFEVecFFECoords(A, F, zero, i, 1);
### AClosestVec[1]=ZZ*AClosestVec[2]...
                v1:=AClosestVec[2]*Gp;
                v2:=Permuted(v1,(rho)^(-1));
        	Add(J,[WeightVecFFE(v2),Codeword(v2,n,F),AClosestVec[2]]);
	od;
        ds:=List(J,x->x[1]);
        vecs:=List(J,x->x[2]);
        rowcombos:=List(J,x->x[3]);
        d:=Minimum(ds);
        i:=Position(ds,d);
        arrayd1[m]:=[d,vecs[i],rowcombos[i]];
        perms[m]:=rho;
   od; ## m

   ds:=List(arrayd1,x->x[1]);
   vecs:=List(arrayd1,x->x[2]);
   rowcombos:=List(arrayd1,x->x[3]);
   d:=MostCommonInList(ds);
   pos:=Position(ds,d);
   v:=vecs[pos];
   L:=List([1..n],i->OnPoints(i,perms[pos]^(-1)));
   newv:=Codeword(List(L,i->v[L[i]]));
   return([d,newv]);
end;

Bibliography

[BARG] A. Barg. ``Complexity issues in coding theory'' in Handbook of coding theory, Vol 1 (edited by V. Pless, W. Huffman, R. Brualdi). North-Holland. (1998).

[BMT] E. R. Berlekamp, R. J. McEliece, and H. C. A. Van Tilborg. `` On the inherent intractability of certain coding problems.'' IEEE Trans. Inform. Theory. 24 (1978) 384-386.

[CHA] F. Chabaud. ``On the security of some cryptosystems based on error-correcting codes.'' Laboratoire d'Information de l'ENS, Preprint 1994.

[F] A. Foster, ``A polynomial-time probabilistic algorithm for the minimum distance of an arbitrary linear error-correcting code,'' Mathematics Honors Report, Spring 2003-2004.

[GAP] GAP 4.4, Groups Algorithms Programming, version 4.4 http://www.gap-system.org

[GUA] GUAVA, http://cadigweb.ew.usna.edu/~wdj/gap/GUAVA/

[HILL] R. Hill A first course in coding theory, Oxford University Press. (1986).

[LEO] J. S. Leon. `` A probabilistic algorithm for computing minimum weights of large error-correcting codes.'' IEEE Trans. Inform. Theory. 34 (1988) 1354-1359.

[L] C. Lennon, ``List-Decoding of Generalized Reed-Solomon Codes Using Sudan's Algorithm,'' Math Honors Project, 2004-2005 (Prof. W. D. Joyner advisor).

[MS] F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. North-Holland. (1983).

[VAR] A. Vardy, `` Algorithmic complexity in coding theory and the minimum distance problem'', Annual ACM Symposium on Theory of Computing, Proceedings of the twenty-ninth annual ACM symposium on Theory, El Paso, Texas, pages: 92 - 109, 1997. Avaliable at http://portal.acm.org/portal.cfm

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -t 'W. Irons Math Honors Thesis 2004-2005' -split 0 irons_mathhonors2004-2005.tex

The translation was initiated by David Joyner on 2005-04-22

David Joyner 2005-04-22