|
#############################################################################
##
#A codeops.gi GUAVA Reinald Baart
#A &Jasper Cramwinckel
#A &Erik Roijackers
## &David Joyner
##
## All the code operations
##
## changes 2003-2004 to MinimumDistance by David Joyner, Aron Foster
## bug in MinimumDistance corrected 9-29-2004 by wdj
## moved Decode and PermutationDecode to decoders.gi on 10-2004
## added HasGeneratorMat to GeneratorMat function 11-2-2004
## another bug in MinimumDistance (discovered by Jason McGowan)
## corrected 11-9-2004 by wdj
## slight changes to MinimumWeightWords (11-26-2005)
## wdj (9-14-2007): bug fix to MinimumDistance
## added MinimumDistanceCodeword
## 20 Dec 07 14:24 (CJ) added IsDoublyEvenCode, IsSinglyEvenCode
## and IsEvenCode functions
## 18 Dec 2008 (wdj) bugfix for MinimumDistanceLeon reported by
## Jorge Ernesto PÉREZ CHAMORRO
##
## 05 Nov 2024 (jef) The infix '+' operation between codes was documented in the manual but apparently never implemented.
## WRONG - it's on line 1382 - it's just not being selected...
#############################################################################
##
#F WordLength( <C> ) . . . . . . . . . . . . length of the codewords of <C>
##
InstallOtherMethod(WordLength, "generic code", true, [IsCode], 0,
function(C)
return WordLength(AsSSortedList(C)[1]) ;
end);
# This comment from GAP3 version.
#In a linear code, the wordlength must always be included
#because the wordlength cannot always be calculated (NullCode)
#
#InstallOtherMethod(WordLength, "method for linear codes", true,
# [IsLinearCode], 0,
#function(C)
# if HasGeneratorMat(C) then
# return Length( GeneratorMat(C)[1] );
# else
# return Length( CheckMat(C)[1] );
# fi;
#end);
#############################################################################
##
#F IsLinearCode( <C> ) . . . . . . . . . . . . . . . checks if <C> is linear
##
## If so, the record fields will be adjusted to the linear type
##
InstallMethod(IsLinearCode, "method for unrestricted codes", true, [IsCode], 0,
function(C)
local gen, k, F, q;
F := LeftActingDomain(C);
q := Size(F);
k := LogInt(Size(C),q);
# first the trivial cases:
if ( HasWeightDistribution(C) and
HasInnerDistribution(C)
and (WeightDistribution(C) <> InnerDistribution(C)) )
or ( q^k <> Size(C) )
or (not NullWord(WordLength(C), F) in C) then
return false; #is cool
else
gen:=BaseMat(VectorCodeword(AsSSortedList(C)));
if Length(gen) <> k then
return false; # is cool as ice
else
SetFilterObj(C, IsLinearCodeRep);
SetGeneratorMat(C, gen);
if Length(gen) = 0 then # special case for Nullcode
SetGeneratorsOfLeftModule(C, [AsSSortedList(C)[1]]);
else
SetGeneratorsOfLeftModule(C, AsList(Codeword(gen,F)));
fi;
if HasInnerDistribution(C) then
SetWeightDistribution(C, InnerDistribution(C));
fi;
return true;
fi;
fi;
end);
InstallOtherMethod(IsLinearCode, "method for generic object", true,
[IsObject], 0,
function(obj)
return IsCode(obj) and IsLinearCode(obj);
end);
#############################################################################
##
#F IsFinite( <C> ) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
##
##
InstallTrueMethod(IsFinite, IsCode);
#############################################################################
##
#F Dimension( <C> ) . . . . . . . . . . . . . . . . . . . . . . . . . . .
##
##
InstallOtherMethod(Dimension, "method for unrestricted codes", true,
[IsCode], 0,
function(C)
if IsLinearCode(C) then
return Dimension(C);
else
Error("dimension is only defined for linear codes");
fi;
end);
InstallOtherMethod(Dimension, "method for linear codes", true,
[IsLinearCode], 0,
function(C)
return Length(GeneratorMat(C));
end);
InstallOtherMethod(Dimension, "method for cyclic codes", true,
[IsCyclicCode], 0,
function(C)
if HasGeneratorPol(C) then
return WordLength(C) - DegreeOfLaurentPolynomial( GeneratorPol(C) );
elif HasCheckPol(C) then
return DegreeOfLaurentPolynomial( CheckPol(C) );
else
Error("Attempting to find the dim of a cyclic code with neither a gen. poly. nor a check poly...\n");
fi;
end);
#############################################################################
##
#F Size( <C> ) . . . . . . . . . . . returns the number of codewords of <C>
##
##
InstallMethod(Size, "method for unrestricted codes", true, [IsCode], 0,
function(C)
return Length(AsSSortedList(C));
end);
#############################################################################
##
#F AsSSortedList( <C> ) . . . . . . . . returns the list of codewords of <C>
## AsList( <C> )
##
## Codes created with ElementsCode must have AsSSortedList set.
## Linear codes use the vector space / FLM method to calculate.
## AsList defaults to AsSSortedList.
InstallMethod(AsList, "method for unrestricted codes", true, [IsCode], 0,
function(C)
return AsSSortedList(C);
end);
#############################################################################
##
#F Redundancy( <C> ) . . . . . . . . . . . . . . . . . . . . . . . . . . .
##
##
InstallMethod(Redundancy, "method for unrestricted codes", true, [IsCode], 0,
function(C)
if IsLinearCode(C) then
return Redundancy(C);
else
Error("redundancy is only defined for linear codes");
fi;
end);
InstallMethod(Redundancy, "method for linear codes", true, [IsLinearCode], 0,
function(C)
return WordLength(C) - Dimension(C);
end);
#############################################################################
##
#F GeneratorMat(C) . . . . . finds the generator matrix belonging to code C
##
## Pre: C should contain a generator or check matrix
##
InstallMethod(GeneratorMat, "method for unrestricted code", true, [IsCode], 0,
function(C)
if IsLinearCode(C) then
return GeneratorMat(C);
else
Error("non-linear codes don't have a generator matrix");
fi;
end);
InstallMethod(GeneratorMat, "method for linear code", true, [IsLinearCode], 0,
function(C)
local G;
if HasGeneratorMat(C) then return C!.GeneratorMat; fi;
if not HasCheckMat( C ) then
return List( BasisVectors( Basis( C ) ), x -> VectorCodeword( x ) );
fi;
if CheckMat(C) = [] then
G := IdentityMat(Dimension(C), LeftActingDomain(C));
elif IsInStandardForm(CheckMat(C), false) then
G := TransposedMat(Concatenation(IdentityMat(
Dimension(C), LeftActingDomain(C) ),
List(-CheckMat(C), x->x{[1..Dimension(C) ]})));
else
G := NullspaceMat(TransposedMat(CheckMat(C)));
fi;
return ShallowCopy(G);
end);
InstallMethod(GeneratorMat, "method for cyclic code", true, [IsCyclicCode], 0,
function(C)
local F, G, p, n, i, R, zero, coeffs;
if HasGeneratorMat(C) then return C!.GeneratorMat; fi;
#To be inspected:
#if HasCheckMat(C) and IsInStandardForm(CheckMat(C), false) then
# G := TransposedMat(Concatenation(IdentityMat(Dimension(C),
# LeftActingDomain(C)),
# List(-CheckMat(C), x->x{[1..Dimension(C)]})));
#else
F := LeftActingDomain(C);
p := GeneratorPol(C);
n := WordLength(C);
G := [];
zero := Zero(F);
coeffs := CoefficientsOfLaurentPolynomial(p);
coeffs := ShiftedCoeffs(coeffs[1], coeffs[2]);
for i in [1..Dimension(C)] do
R := NullVector(i-1, F);
Append(R, coeffs);
Append(R, NullVector(n-Length(R), F));
G[i] := R;
od;
#fi;
return ShallowCopy(G);
end);
#############################################################################
##
#F CheckMat( <C> ) . . . . . . . finds the check matrix belonging to code C
##
## Pre: <C> should be a linear code
##
InstallMethod(CheckMat, "method for unrestricted codes", true, [IsCode], 0,
function(C)
if IsLinearCode(C) then
return CheckMat(C);
else
Error("non-linear codes don't have a check matrix");
fi;
end);
InstallMethod(CheckMat, "method for linear code", true, [IsLinearCode], 0,
function(C)
local H;
if GeneratorMat(C) = [] then
H := IdentityMat(WordLength(C), LeftActingDomain(C));
elif IsInStandardForm(GeneratorMat(C), true) then
H := TransposedMat(Concatenation(List(-GeneratorMat(C),
x-> x{[Dimension(C)+1 .. WordLength(C) ]}),
IdentityMat(Redundancy(C), LeftActingDomain(C) )));
else
H := NullspaceMat(TransposedMat(GeneratorMat(C)));
fi;
return ShallowCopy(H);
end);
InstallMethod(CheckMat, "method for cyclic code", true, [IsCyclicCode], 0,
function(C)
local F, H, p, n, i, R, zero, coeffs;
#if HasGeneratorMat(C) and IsInStandardForm(GeneratorMat(C), true) then
# H := TransposedMat(Concatenation(List(-GeneratorMat(C), x->
# x{[Dimension(C)+1..WordLength(C)]}),
# IdentityMat(Redundancy(C), LeftActingDomain(C))));
#else
F := LeftActingDomain(C);
H := [];
p := CheckPol(C);
p := Indeterminate(F)^Dimension(C)*Value(p,Indeterminate(F)^-1);
n := WordLength(C);
zero := Zero(F);
coeffs := CoefficientsOfLaurentPolynomial(p);
coeffs := ShiftedCoeffs(coeffs[1], coeffs[2]);
for i in [1..Redundancy(C)] do
R := NullVector(i-1, F);
Append(R, coeffs);
Append(R, NullVector(n-Length(R), F));
H[i] := R;
od;
#fi;
return ShallowCopy(H);
end);
#############################################################################
##
#F IsCyclicCode( <C> ) . . . . . . . . . . . . . . . . . . . . . . . . . .
##
InstallOtherMethod(IsCyclicCode, "method for unrestricted codes",
true, [IsCode], 0,
function(C)
if IsLinearCode(C) then
return IsCyclicCode(C);
else
return false;
fi;
end);
InstallMethod(IsCyclicCode, "method for linear codes", true, [IsLinearCode], 0,
function(C)
local C1, F, L, Gp;
F := LeftActingDomain(C);
L := List(GeneratorMat(C),
g->LaurentPolynomialByCoefficients(
ElementsFamily(FamilyObj(F)),One(F)*g, 0 ));
Add(L, Indeterminate(F)^WordLength(C) - One(F));
Gp := Gcd(L);
if Redundancy(C) = DegreeOfLaurentPolynomial(Gp) then
SetGeneratorPol(C, Gp);
return true;
else
return false; #so the code is not cyclic
fi;
end);
InstallOtherMethod(IsCyclicCode, "method for generic objects", true,
[IsObject], 0,
function(obj)
return IsCode(obj) and IsLinearCode(obj) and IsCyclicCode(obj);
end);
#############################################################################
##
#F GeneratorPol( <C> ) . . . . . . . . returns the generator polynomial of C
##
## Pre: C must have a generator or check polynomial
##
InstallMethod(GeneratorPol, "method for unrestricted codes", true, [IsCode], 0,
function(C)
if IsCyclicCode(C) then
return GeneratorPol(C);
else
Error("generator polynomial is only defined for cyclic codes");
fi;
end);
InstallMethod(GeneratorPol, "method for cyclic codes", true, [IsCyclicCode], 0,
function(C)
local F, n;
F := LeftActingDomain(C);
n := WordLength(C);
return EuclideanQuotient(One(F)*(Indeterminate(F)^n-1),CheckPol(C));
end);
#############################################################################
##
#F CheckPol( <C> ) . . . . . . . . returns the parity check polynomial of C
##
## Pre: C must have a generator or check polynomial
##
InstallMethod(CheckPol, "method for unrestricted codes", true, [IsCode], 0,
function(C)
if IsCyclicCode(C) then
return CheckPol(C);
else
Error("generator polynomial is only defined for cyclic codes");
fi;
end);
InstallMethod(CheckPol, "method for cyclic codes", true, [IsCyclicCode], 0,
function(C)
local F, n;
F := LeftActingDomain(C);
n := WordLength(C);
return EuclideanQuotient((Indeterminate(F)^n-One(F)),GeneratorPol(C));
end);
#############################################################################
##
#F MinimumDistanceCodeword( <C> [, <w>] ) . . . . determines a codeword
## having minimum distance to w
## (w= zero vector is the default)
##
##wdj,9-14-2007
InstallMethod(MinimumDistanceCodeword, "attribute method for linear codes", true,
[IsLinearCode], 0,
function(C)
local k, i, j, G, F, zero, AClosestVec, minwt, num, n, closestvec;
F := LeftActingDomain(C);
n := WordLength(C);
zero := Zero(F)*NullVector(n);
G := GeneratorMat(C);
minwt:=n;
closestvec := zero;
for i in [1..Length(G)] do
AClosestVec:=AClosestVectorCombinationsMatFFEVecFFE(G, F, zero, i, 1);
if WeightVecFFE(AClosestVec)<minwt then
minwt := WeightVecFFE(AClosestVec);
closestvec := AClosestVec;
fi;
od;
return(closestvec);
end);
#
# This _was_ an InstallOtherMethod for MinimumDistance but the methods
# for that (including one with the same filter list as this) are encoded
# further down in this file. On close inspection notice that it is
# returning a codeword -- it _should_ have been an InstallOtherMethod
# for MinimumDistanceCodeword -- JEF 6/22/11
#
InstallOtherMethod(MinimumDistanceCodeword, "linear code, word", true,
[IsLinearCode, IsCodeword], 0,
function(C, word)
local k, i, j, G, F, zero, AClosestVec, minwt, num, n, closestvec;
Print("linear code, vector (first in file) \n");
F := LeftActingDomain(C);
n := WordLength(C);
zero := Zero(F)*NullVector(n);
G := GeneratorMat(C);
minwt:=n;
closestvec := word;
for i in [1..Length(G)] do
AClosestVec:=AClosestVectorCombinationsMatFFEVecFFE(G, F, word, i, 1);
if WeightVecFFE(AClosestVec)<minwt then
minwt := WeightVecFFE(AClosestVec);
closestvec := AClosestVec;
fi;
od;
return(closestvec);
end);
#############################################################################
##
#F MinimumDistance( <C> [, <w>] ) . . . . determines the minimum distance
##
## MinimumDistance( <C> ) determines the minimum distance of <C>
## MinimumDistance( <C>, <w> ) determines the minimum distance to a word <w>
##
InstallMethod(MinimumDistance, "attribute method for unrestricted codes", true,
[IsCode], 0,
function(C)
local W, El, F, n, zero, d, DD, w;
#Print("unrestricted code\n");
if IsBound(C!.upperBoundMinimumDistance) and
IsBound(C!.lowerBoundMinimumDistance) and
C!.upperBoundMinimumDistance = C!.lowerBoundMinimumDistance then
return C!.lowerBoundMinimumDistance;
elif IsCyclicCode(C) or IsLinearCode(C) then
return MinimumDistance(C);
fi;
W := VectorCodeword(AsSSortedList(C));
El := W; # so not a copy!
F := LeftActingDomain(C);
n := WordLength(C);
zero := Zero(F);
d := n;
DD := NullVector(n+1);
for w in W do
DD := DD + DistancesDistributionVecFFEsVecFFE(El, w);
od;
d := PositionProperty([2..n+1], i->DD[i] <> 0);
C!.lowerBoundMinimumDistance := d;
C!.upperBoundMinimumDistance := d;
return d;
end);
InstallMethod(MinimumDistance, "attribute method for linear codes", true,
[IsLinearCode], 0,
function(C)
local k, i, j, G, F, zero, AClosestVec, minwt, num, n;
if IsBound(C!.upperBoundMinimumDistance) and
IsBound(C!.lowerBoundMinimumDistance) and
C!.upperBoundMinimumDistance = C!.lowerBoundMinimumDistance then
return C!.lowerBoundMinimumDistance;
fi;
F := LeftActingDomain(C);
n := WordLength(C);
zero := Zero(F)*NullVector(n);
G := GeneratorMat(C);
minwt:=n;
for i in [1..Length(G)] do
AClosestVec:=AClosestVectorCombinationsMatFFEVecFFE(G, F, zero, i, 1);
if WeightVecFFE(AClosestVec)<minwt then
minwt := WeightVecFFE(AClosestVec);
fi;
od;
C!.lowerBoundMinimumDistance := minwt;
C!.upperBoundMinimumDistance := minwt;
return(minwt);
end);
InstallMethod(MinimumDistance, "attribute method for cyclic code", true,
[IsCyclicCode], 0,
function(C)
local md;
#Print("cyclic code\n");
if IsBound(C!.lowerBoundMinimumDistance) and
IsBound(C!.upperBoundMinimumDistance) and
C!.lowerBoundMinimumDistance = C!.upperBoundMinimumDistance then
return C!.lowerBoundMinimumDistance;
else
md := MinimumDistance( PuncturedCode( C ) ) + 1;
C!.lowerBoundMinimumDistance := md;
C!.upperBoundMinimumDistance := md;
return md;
fi;
end);
## Should be a better way to set up the Other methods, given
## how much overlap there is with attribute methods. For now, though,
## this works.
InstallOtherMethod(MinimumDistance, "unrestricted code, word", true,
[IsCode, IsCodeword], 0,
function(C, word)
local W, El, F, n, zero, d, w, DD;
#Print("unrestricted code, vector\n");
if IsLinearCode(C) then
return MinimumDistance(C, word);
fi;
if word in C then
return 0;
fi;
W := [VectorCodeword(Codeword(word, C))];
El := VectorCodeword(AsSSortedList(C));
F := LeftActingDomain(C);
n := WordLength(C);
zero := Zero(F);
d := n;
DD := NullVector(n+1);
for w in W do
DD := DD + DistancesDistributionVecFFEsVecFFE(El, w);
od;
d := PositionProperty([2..n+1], i->DD[i] <> 0);
return d;
end);
InstallOtherMethod(MinimumDistance, "linear code, word", true,
[IsLinearCode, IsCodeword], 0,
function(C, word)
local Mat, n, k, zero, UP, G, W, multiple, weight,
ThisGIsDone, #is true as the latest matrix is converted
Icount, #number of corrected generatormatrices
i, #first rownumber which could be added to I
l, #columnnumber which could be used
IdentityColumns,
j, CurW, UMD, w, q, tmp, F;
# Print("linear code, vector (second in file) \n");
k := Dimension(C);
n := WordLength(C);
zero := Zero(LeftActingDomain(C));
q := Size(LeftActingDomain(C));
F := LeftActingDomain(C);
w := VectorCodeword(word);
if w in C then
return 0;
elif k = 0 then
return Weight(Codeword(w));
elif HasSyndromeTable(C) then
j := 1;
w := VectorCodeword( Syndrome(C, w) );
for i in [ 0 .. k - 1 ] do
if w[ k - i ] <> zero then
j := j + q^i * ( LogFFE( w[ k - i ] ) + 1 );
fi;
od;
return Weight(SyndromeTable(C)[j][1]);
fi;
UMD := Weight(Codeword(w));
#this must be so, because the kernel function
#can not find this distance
CurW := 0;
Mat := ShallowCopy(GeneratorMat(C));
i := 1;
## The next lines could go etwas faster for cyclic codes by weighting the
## generator polynomial, but a copy of this function must be made in the
## CycCodeOps, which makes it harder to make changes.
if q = 2 then
multiple := 2;
repeat
weight := 0;
for j in Mat[i] do
if not j = zero then
weight := weight + 1;
fi;
od;
multiple := Gcd( multiple, weight );
i := i + 1;
until multiple = 1 or i > k;
else
multiple := 1;
fi;
# we now know that the weight of all the elements are a multiple of multiple
UP := List([1..n], i->false); #which columns are already used
G := [];
W := [];
Icount := 0;
repeat
ThisGIsDone := false;
i := 1; # i is the row of the identitymatrix it
l := 1; # is trying to make
IdentityColumns := [];
while not ThisGIsDone and (l <= n) do
if not UP[l] then # try this column if it is not already used
j := i;
while (j <= k) and (Mat[j][l] = zero) do
j := j + 1; # go down in the matrix until a nonzero
od; # entry is found
if j <= k then
if j > i then
tmp := Mat[i];
Mat[i] := Mat[j];
Mat[j] := tmp;
fi;
Mat[i] := Mat[i]/Mat[i][l];
for j in Concatenation([1..i-1], [i+1..k]) do
if Mat[j][l] <> zero then
Mat[j] := Mat[j] - Mat[j][l]*Mat[i];
fi;
od;
UP[l] := true;
Add(IdentityColumns, l);
i := i + 1;
ThisGIsDone := ( i > k );
fi;
fi;
l := l + 1;
od;
if ThisGIsDone then
Icount := Icount + 1;
Add( G, Mat{[1..k]}{Difference([1..n],IdentityColumns)} );
w := w-w{IdentityColumns}*Mat;
Add(W,w{Difference([1..n], IdentityColumns)} );
UMD := Minimum( UMD, WeightCodeword( Codeword( w ) ) );
## G_i is generator matrix i
## W_i has zeros in IdentityColumns,
## but has same distance to code because
## only a codeword is added
fi;
until not ThisGIsDone or ( Icount = Int( n / k ) );
while CurW <= ( UMD - multiple ) / Icount do
i := 0;
repeat
i := i + 1;
UMD := Minimum( UMD, DistanceVecFFE( W[i],
AClosestVectorCombinationsMatFFEVecFFE(
G[i], F, W[i], CurW, CurW*(Icount-1) )
) + CurW );
until (i = Length(G)) or (UMD = CurW*Icount);
CurW := CurW + 1;
od;
return UMD;
end);
InstallMethod(MinimumDistanceLeon, "attribute method for linear codes", true,
[IsLinearCode], 0,
function(C)
local majority,G0, Gp, Gpt, Gt, L, k, i, j, dimMat, Grstr, J, d1, arrayd1, Combo, rows, row, rowSum, G, F, zero, AClosestVec, s, p, num;
F:=LeftActingDomain(C);
if F<>GF(2) then Print("Code must be binary. Quitting. \n"); return(0); fi;
G := MutableCopyMatrix(GeneratorMat(C));
if (IsInStandardForm(G)=false) then
PutStandardForm(G);
fi;
p:=5; #these seem to be optimal values
num:=8; #these seem to be optimal values
dimMat := DimensionsMat(G);
s := dimMat[2]-dimMat[1];
arrayd1:=[];
for k in [1..num] do
##Permute the columns randomly
Gt := TransposedMat(G);
Gp := NullMat(dimMat[2],dimMat[1]);
L := SymmetricGroup(dimMat[2]);
L := Random(L);
L:=List([1..dimMat[2]],i->OnPoints(i,L));
for i in [1..dimMat[2]] do
Gp[i] := Gt[L[i]];
od;
Gp := TransposedMat(Gp);
Gp := ShallowCopy(Gp);
##Use gaussian elimination on the new matrix
TriangulizeMat(Gp);
##generate the restricted code (I|Z) from Gp=(I|Z|B)
Gpt := TransposedMat(Gp);
Grstr := NullMat(s,dimMat[1]);
for i in [dimMat[1]+1..dimMat[1]+s] do
Grstr[i-dimMat[1]] := Gpt[i];
od;
Grstr := TransposedMat(Grstr);
zero := Zero(F)*Grstr[1];
##search for all rows of weight p
J := []; #col number of codewords to compute the length of
for i in [1..p] do
AClosestVec:=AClosestVectorCombinationsMatFFEVecFFE(Grstr, F, zero, i, 1);
if WeightVecFFE(AClosestVec) > 0 then
Add(J, [AClosestVec,i]);
fi;
od;
d1:=dimMat[2];
for rows in J do
d1:=Minimum(WeightVecFFE(rows[1])+rows[2],d1);
od;
arrayd1[k]:=d1;
od;
if AbsoluteValue(Sum(arrayd1)/Length(arrayd1)-Int(Sum(arrayd1)/Length(arrayd1)))<1/2 then
majority:=Int(Sum(arrayd1)/Length(arrayd1));
else
majority:=Int(Sum(arrayd1)/Length(arrayd1))+1;
fi;
return(majority);
end);
InstallOtherMethod(MinimumDistanceLeon, "attribute method for linear codes, integer, integer", true,
[IsLinearCode, IsInt, IsInt], 0,
function(C,p,num)
# p = 5 seems to be optimal
# num = 8 seems to be optimal
local majority,G0, Gp, Gpt, Gt, L, k, i, j, dimMat, Grstr, J, d1, arrayd1, Combo, rows, row, rowSum, G, F, zero, AClosestVec, s;
G := MutableCopyMatrix(GeneratorMat(C));
if (IsInStandardForm(G)=false) then
PutStandardForm(G);
fi;
F:=LeftActingDomain(C);
if F<>GF(2) then Print("Code must be binary. Quitting. \n"); return(0); fi;
dimMat := DimensionsMat(G);
s := dimMat[2]-dimMat[1];
arrayd1:=[];
for k in [1..num] do
##Permute the columns randomly
Gt := TransposedMat(G);
Gp := NullMat(dimMat[2],dimMat[1]);
L := SymmetricGroup(dimMat[2]);
L := Random(L);
L:=List([1..dimMat[2]],i->OnPoints(i,L));
for i in [1..dimMat[2]] do
Gp[i] := Gt[L[i]];
od;
Gp := TransposedMat(Gp);
Gp := ShallowCopy(Gp);
##Use gaussian elimination on the new matrix
TriangulizeMat(Gp);
##generate the restricted code (I|Z) from Gp=(I|Z|B)
Gpt := TransposedMat(Gp);
Grstr := NullMat(s,dimMat[1]);
for i in [dimMat[1]+1..dimMat[1]+s] do
Grstr[i-dimMat[1]] := Gpt[i];
od;
Grstr := TransposedMat(Grstr);
zero := Zero(F)*Grstr[1];
##search for all rows of weight p
J := []; #col number of codewords to compute the length of
for i in [1..p] do
AClosestVec:=AClosestVectorCombinationsMatFFEVecFFE(Grstr, F, zero, i, 1);
if WeightVecFFE(AClosestVec) > 0 then
Add(J, [AClosestVec,i]);
fi;
od;
d1:=dimMat[2];
for rows in J do
d1:=Minimum(WeightVecFFE(rows[1])+rows[2],d1);
od;
arrayd1[k]:=d1;
od;
if AbsoluteValue(Sum(arrayd1)/Length(arrayd1)-Int(Sum(arrayd1)/Length(arrayd1)))<1/2 then
majority:=Int(Sum(arrayd1)/Length(arrayd1));
else
majority:=Int(Sum(arrayd1)/Length(arrayd1))+1;
fi;
return(majority);
end);
#############################################################################
##
#F LowerBoundMinimumDistance( arg ) . . . . . . . . . . . . . . . . . . .
##
##LR - Is there a better way to handle HasMD case, without reset?
InstallMethod(LowerBoundMinimumDistance, "method for unrestricted codes",
true, [IsCode], 0,
function(C)
if HasMinimumDistance(C) then
C!.lowerBoundMinimumDistance := MinimumDistance(C);
elif not IsBound(C!.lowerBoundMinimumDistance) then
if Size(C) = 1 then
C!.lowerBoundMinimumDistance := WordLength(C);
else
C!.lowerBoundMinimumDistance := 1;
fi;
fi;
return C!.lowerBoundMinimumDistance;
end);
InstallMethod(LowerBoundMinimumDistance, "method for linear code", true,
[IsLinearCode], 0,
function(C)
if HasMinimumDistance(C) then
C!.lowerBoundMinimumDistance := MinimumDistance(C);
elif not IsBound(C!.lowerBoundMinimumDistance) then
if Dimension(C) = 0 then
C!.lowerBoundMinimumDistance := WordLength(C);
elif Dimension(C) = 1 then
C!.lowerBoundMinimumDistance:= Weight(Codeword(GeneratorMat(C)[1]));
else
C!.lowerBoundMinimumDistance := 1;
fi;
fi;
return C!.lowerBoundMinimumDistance;
end);
InstallMethod(LowerBoundMinimumDistance, "method for cyclic codes", true,
[IsCyclicCode], 0,
function(C)
if HasMinimumDistance(C) then
C!.lowerBoundMinimumDistance := MinimumDistance(C);
elif not IsBound(C!.lowerBoundMinimumDistance) then
if Dimension(C) = 0 then
C!.lowerBoundMinimumDistance := WordLength(C);
elif Dimension(C) = 1 then
C!.lowerBoundMinimumDistance := Weight(Codeword(GeneratorPol(C)));
else
C!.lowerBoundMinimumDistance := 1;
fi;
fi;
return C!.lowerBoundMinimumDistance;
end);
InstallOtherMethod(LowerBoundMinimumDistance, "n, k, q", true,
[IsInt, IsInt, IsInt], 0,
function(n, k, q)
local r;
r := BoundsMinimumDistance(n, k, q, true);
return r.lowerBound;
end);
InstallOtherMethod(LowerBoundMinimumDistance, "n, k", true,
[IsInt, IsInt], 0,
function(n, k)
local r;
r := BoundsMinimumDistance(n, k, 2, true);
return r.lowerBound;
end);
InstallOtherMethod(LowerBoundMinimumDistance, "n, k, F", true,
[IsInt, IsInt, IsField], 0,
function(n, k, F)
local r;
r := BoundsMinimumDistance(n, k, Size(F), true);
return r.lowerBound;
end);
#############################################################################
##
#F UpperBoundMinimumDistance( arg ) . . . . . . . . . . . . . . . . . . .
##
##LR - is there a better way to handle HasMD case, without reset?
InstallMethod(UpperBoundMinimumDistance, "method for unrestricted codes",
true, [IsCode], 0,
function(C)
if HasMinimumDistance(C) then
C!.upperBoundMinimumDistance := MinimumDistance(C);
elif not IsBound(C!.upperBoundMinimumDistance) then
C!.upperBoundMinimumDistance := WordLength(C);
fi;
return C!.upperBoundMinimumDistance;
end);
InstallMethod(UpperBoundMinimumDistance, "method for linear codes", true,
[IsLinearCode], 0,
function(C)
local ubmd;
if HasMinimumDistance(C) then
C!.upperBoundMinimumDistance := MinimumDistance(C);
else
if not IsBound(C!.upperBoundMinimumDistance) then
ubmd := WordLength(C);
else
ubmd := C!.upperBoundMinimumDistance;
fi;
if MinimumWeightOfGenerators(C) < ubmd then
ubmd := MinimumWeightOfGenerators(C);
fi;
if UpperBoundOptimalMinimumDistance(C) < ubmd then
ubmd := UpperBoundOptimalMinimumDistance(C);
fi;
C!.upperBoundMinimumDistance := ubmd;
fi;
return C!.upperBoundMinimumDistance;
end);
InstallOtherMethod(UpperBoundMinimumDistance, "n, k, q", true,
[IsInt, IsInt, IsInt], 0,
function(n, k, q)
local r;
r := BoundsMinimumDistance(n, k, q, false);
return r.upperBound;
end);
InstallOtherMethod(UpperBoundMinimumDistance, "n,k", true,
[IsInt, IsInt], 0,
function(n, k)
local r;
r := BoundsMinimumDistance(n, k, 2, false);
return r.upperBound;
end);
InstallOtherMethod(UpperBoundMinimumDistance, "n,k,F", true,
[IsInt, IsInt, IsField], 0,
function(n, k, F)
local r;
r := BoundsMinimumDistance(n, k, Size(F), false);
return r.upperBound;
end);
#############################################################################
##
#F UpperBoundOptimalMinimumDistance( arg ) . . . . . . . . . . . . . . . .
##
## UpperBoundMinimumDistance of optimal code with given parameters
##
InstallMethod(UpperBoundOptimalMinimumDistance, "method for unrestricted code",
true, [IsCode], 0,
function(C)
local r;
r := BoundsMinimumDistance(WordLength(C), Dimension(C),
Size(LeftActingDomain(C)), false);
return r.upperBound;
end);
#############################################################################
##
#F MinimumWeightOfGenerators( arg ) . . . . . . . . . . . . . . . . . . . .
##
##
InstallMethod(MinimumWeightOfGenerators, "linear codes", true,
[IsLinearCode], 0,
function(C)
local zero, mwg, sum, element, row;
zero := Zero(LeftActingDomain(C));
mwg := WordLength(C);
if Dimension(C) > 0 then
# minimumWeightOfGenerators for null codes is n
for row in GeneratorMat(C) do
sum := 0;
for element in row do
if element <> zero then
sum := sum + 1;
fi;
od;
if sum < mwg then
mwg := sum;
fi;
od;
fi;
return mwg;
end);
InstallMethod(MinimumWeightOfGenerators, "method for cyclic codes", true,
[IsCyclicCode], 0,
function(C)
if Dimension(C) > 0 then
# minimumWeightOfGenerators of null codes is n
return Weight(Codeword(GeneratorPol(C)));
else
return WordLength(C);
fi;
end);
#############################################################################
##
#F MinimumWeightWords( <C> ) . . . returns the code words of minimum weight
##
InstallMethod(MinimumWeightWords, "method for unrestricted code", true,
[IsCode], 0,
function(C)
local curmin, res, e, w, zerovec, d;
if IsLinearCode(C) then
return MinimumWeightWords(C);
fi;
curmin := WordLength(C);
if not HasWeightDistribution(C) then
res := [];
for e in AsSSortedList(C) do
w := Weight(e);
if w < curmin and w <> 0 then
# New minimum weight found
curmin := w;
res := [ e ];
elif w = curmin then
Add(res, e);
fi;
od;
return res;
else
# Find the minimum weight
d := MinimumDistance(C);
return Filtered(AsSSortedList(C), e -> Weight(e) = d);
fi;
end);
InstallMethod(MinimumWeightWords, "method for linear code", true,
[IsLinearCode], 0,
function(C)
local d, G, res, vector, count, i, t, k, q, M, zerovec;
d := MinimumDistance(C); # Equal to minimum weight
G := GeneratorMat(C);
k := Dimension(C);
q := Size(LeftActingDomain(C));
M := Size(C);
res := [];
vector := NullVector(WordLength(C), LeftActingDomain(C));
zerovec := ShallowCopy(vector);
count := 1;
while count < M do
# Calculate next word in the code
i := k;
t := count;
while t mod q = 0 do
t := t / q;
i := i - 1;
od;
vector := vector + G[i];
if DistanceVecFFE(vector, zerovec) = d then
# This word has minimum weight
Add(res, Codeword(vector));
fi;
count := count + 1;
od;
return res;
end);
#############################################################################
##
#F WeightDistribution( <C> ) . . . returns the weight distribution of a code
##
InstallMethod(WeightDistribution, "method for unrestricted code", true,
[IsCode], 0,
function (C)
local El, nl, newwd;
if IsLinearCode(C) then
return WeightDistribution(C);
fi;
El := VectorCodeword(AsSSortedList(C));
nl := VectorCodeword(NullWord(C));
newwd := DistancesDistributionVecFFEsVecFFE(El, nl);
return newwd;
end);
InstallMethod(WeightDistribution, "method for linear code", true,
[IsLinearCode], 0,
function(C)
local G, nl, k, n, q, F, wd, newwd, oldrow, newrow, i, j;
n := WordLength(C);
k := Dimension(C);
q := Size(LeftActingDomain(C));
F := LeftActingDomain(C);
nl := VectorCodeword(NullWord(C));
if k = 0 then
G := NullVector(n+1);
G[1] := 1;
newwd := G;
elif k = n then
newwd := List([0..n], i->Binomial(n, i));
elif k <= Int(n/2) then
G := One(F)*ShallowCopy(GeneratorMat(C));
newwd := DistancesDistributionMatFFEVecFFE(G, F, nl);
else
G := One(F)*ShallowCopy(CheckMat(C));
wd := DistancesDistributionMatFFEVecFFE(G, F, nl);
newwd := [Sum(wd)];
oldrow := List([1..n+1], i->1);
newrow := [];
for i in [2..n+1] do
newrow[1] := Binomial(n, i-1) * (q-1)^(i-1);
for j in [2..n+1] do
newrow[j] := newrow[j-1] - (q-1) * oldrow[j] - oldrow[j-1];
od;
newwd[i] := newrow * wd;
oldrow := ShallowCopy(newrow);
od;
newwd:= newwd / (q ^ Redundancy(C));
fi;
return newwd;
end);
#############################################################################
##
#F InnerDistribution( <C> ) . . . . . . the inner distribution of the code
##
## The average distance distribution of distances between all codewords
##
InstallMethod(InnerDistribution, "method for unrestricted code", true,
[IsCode], 0,
function (C)
local ID, c, El;
El := VectorCodeword(AsSSortedList(C));
ID := List([1..WordLength(C)+1], i->0);
for c in El do
ID := ID + DistancesDistributionVecFFEsVecFFE(El, c);
od;
return ID/Size(C);
end);
InstallMethod(InnerDistribution, "method for linear codes", true,
[IsLinearCode], 0,
function (C)
return WeightDistribution(C);
end);
#############################################################################
##
#F OuterDistribution( <C> ) . . . . . . . . . . . . . . . . . . . . . . .
##
## the number of codewords on a distance i from all elements of GF(q)^n
##
InstallOtherMethod(OuterDistribution, "method for unrestricted code", true,
[IsCode], 0,
function (C)
local gen, q, n, F, zero, Els, res, vector, t, large, count, dd;
if IsLinearCode(C) then
return OuterDistribution(C);
fi;
q := Size(LeftActingDomain(C));
n := WordLength(C);
F := LeftActingDomain(C);
zero := Zero(F);
Els := VectorCodeword(AsSSortedList(C));
res := [[NullWord(C),WeightDistribution(C)]];
vector := NullVector(n, F);
t := n;
gen := Z(q);
large := One(F);
for count in [2..q^n] do
t := n;
while vector[t] = large do
vector[t] := zero;
t := t-1;
od;
if vector[t] = zero then
vector[t] := gen;
else
vector[t] := vector[t] * gen;
fi;
dd := DistancesDistributionVecFFEsVecFFE(Els, vector);
Add(res, [Codeword(vector), dd]);
od;
return res;
end);
InstallMethod(OuterDistribution, "method for linear codes", true,
[IsLinearCode], 0,
function(C)
local STentry, dtw, E, res, i;
E := AsSSortedList(C);
res := [];
for STentry in List(SyndromeTable(C), i -> i[1]) do
dtw := DistancesDistribution(C, STentry);
for i in E do
Add(res, [VectorCodeword(STentry) + i, dtw]);
od;
od;
return res;
end);
#############################################################################
##
#F InformationWord( Code, c ) . . . "decodes" a codeword c in C to the
## information "message" word m, so m*C=c
InstallMethod(InformationWord, "code, codeword", true, [IsCode, IsCodeword], 1,
function(C, c)
local m;
if not(c in C) then Error( "ERROR: codeword must belong to code" ); fi;
if not(IsLinearCode(C)) then return "ERROR: code must be linear"; fi;
m := SolutionMat(List(GeneratorMat(C),List), VectorCodeword(c));
return Codeword(m);
end);
#############################################################################
##
#F IsSelfDualCode( <C> ) . . . . . . . . . determines whether C is self dual
##
## i.o.w. each codeword is orthogonal to all codewords (including itself)
##
InstallMethod(IsSelfDualCode, "method for unrestricted code", true,
[IsCode], 0,
function(C)
if IsCyclicCode(C) or IsLinearCode(C) then
return IsSelfDualCode(C);
else
return false;
fi;
end);
InstallMethod(IsSelfDualCode, "method for linear code", true,
[IsLinearCode], 0,
function(C)
if IsCyclicCode(C) then
return IsSelfDualCode(C);
elif Redundancy(C) <> Dimension(C) then
return false; #so the code is not self dual
else
return (GeneratorMat(C)*TransposedMat(GeneratorMat(C)) =
NullMat(Dimension(C),Dimension(C),LeftActingDomain(C)));
fi;
end);
InstallMethod(IsSelfDualCode, "method for cyclic codes", true,
[IsCyclicCode], 0,
function(C)
local r;
if Redundancy(C) <> Dimension(C) then
return false; #so the code is not self dual
else
r := ReciprocalPolynomial(GeneratorPol(C),Redundancy(C));
r := r/LeadingCoefficient(r);
return CheckPol(C) = r;
fi;
end);
#############################################################################
##
#F CodewordVector( <l>, <C> )
##
## only valid if C is linear!
##
InstallOtherMethod(CodewordVector,"vector and unrestricted code", true,
[IsList, IsCode], 0,
function(l, C)
if IsLinearCode(C) then
return CodewordVector(l,C);
else
Error("<r> is a non-linear code");# encoding not possible
fi;
end);
InstallOtherMethod(CodewordVector,"vector and linear code", true,
[IsList, IsLinearCode], 0,
function(l, C)
local s, i, k;
if IsCyclicCode(C) then
return CodewordVector(l,C);
else
l := VectorCodeword(Codeword(l, Dimension(C), LeftActingDomain(C)));
if GeneratorMat(C) = [] then
return NullMat(Length(l), WordLength(C), LeftActingDomain(C));
else
return Codeword(l*GeneratorMat(C), C);
fi;
fi;
end);
InstallOtherMethod(CodewordVector, "<list of codewords|vector>,cyclic code",
true, [IsList, IsCyclicCode], 0,
function(l, C)
local F, p;
F := LeftActingDomain(C);
l := Codeword(l, Dimension(C), F);
if IsList(l) and not IsCodeword(l) then
return List(l, i->CodewordVector(i,C));
else
return Codeword(PolyCodeword(l) * GeneratorPol(C), C);
fi;
end);
InstallOtherMethod(CodewordVector, "method for poly and cyclic code", true,
[IsUnivariatePolynomial, IsCyclicCode], 0,
function(p, C)
local F, w;
F := LeftActingDomain(C);
w := Codeword(p, Dimension(C), F);
return Codeword(PolyCodeword(w) * GeneratorPol(C), C);
end);
InstallOtherMethod(\*, "list with code", true, [IsList, IsCode], 0,
CodewordVector);
InstallOtherMethod(\*, "poly with code", true,
[IsUnivariatePolynomial, IsCode], 0, CodewordVector);
InstallOtherMethod(\*, "method for two codes", true, [IsCode, IsCode], 0,
function(C1, C2)
return DirectProductCode(C1, C2);
end);
#############################################################################
##
#F \+( <l>, <C> ) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
##
##
InstallOtherMethod(\+, "method for codeword+code", true,
[IsCodeword, IsCode], 0,
function(w, C)
return CosetCode(C, w);
end);
InstallOtherMethod(\+, "method for code+codeword", true,
[IsCode, IsCodeword], 0,
function(C, w)
return CosetCode(C, w);
end);
InstallOtherMethod(\+, "method for two codes", ReturnTrue,
[IsCodeDefaultRep, IsCodeDefaultRep], 25,
function(C1, C2)
return DirectSumCode(C1, C2);
end);
InstallOtherMethod(\+, "method for two linear codes", ReturnTrue,
[IsLinearCode, IsLinearCode], 26,
function(C1, C2)
return DirectSumCode(C1, C2);
end);
#############################################################################
##
#F \in( <l>, <C> ) . . . . . . true if the vector is an element of the code
##
##
InstallMethod(\in, "method for codeword in unrestricted code", true,
[IsCodeword, IsCode], 0,
function(w, C)
if WordLength(w) <> WordLength(C) then
return false;
else
return w in AsSSortedList(C);
fi;
end);
InstallMethod(\in, "method for list of codewords in unrestricted code", true,
[IsList, IsCode], 0,
function(l, C)
return ForAll(l, w->w in C);
end);
InstallMethod(\in, "method for unrestricted code in unrestricted code", true,
[IsCode, IsCode], 0,
function(C1, C2)
local l;
l := ShallowCopy(AsSSortedList(C1));
return ForAll(l, w->w in C2);
end);
InstallMethod(\in, "method for codeword in linear code", true,
[IsCodeword, IsLinearCode], 0,
function(w, C)
if WordLength(w) <> WordLength(C) then
return false;
elif GeneratorMat(C) = [] then
return w = 0*w;
elif CheckMat(C) = [] then #Code is WholeSpace, just check field.
return ForAll(VectorCodeword(w), x->x in LeftActingDomain(C));
else
return CheckMat(C)*w = 0*w;
fi;
end);
InstallMethod(\in, "method for linear code in linear code", true,
[IsLinearCode, IsLinearCode], 0,
function(C1, C2)
local l;
l := ShallowCopy(GeneratorMat(C1));
return ForAll(l, w-> Codeword(w) in C2);
end);
InstallMethod(\in, "method for codeword in cyclic code", true,
[IsCodeword, IsCyclicCode], 0,
function(w, C)
return PolyCodeword(w) mod GeneratorPol(C) =
0 * Indeterminate(LeftActingDomain(C));
end);
InstallMethod(\in, "method for cyclic code in cyclic code", true,
[IsCyclicCode, IsCyclicCode], 0,
function(C1, C2)
return GeneratorPol(C1) mod GeneratorPol(C2) =
0 * Indeterminate(LeftActingDomain(C2));
end);
#############################################################################
##
#F \=( <C1>, <C2> ) . . . . . tests if Set(AsList(C1))=Set(AsList(C2))
##
## Post: returns a boolean
##
InstallMethod(\=, "method for unrestricted code = unrestricted code", true,
[IsCode, IsCode], 0,
function(C1, C2)
local field, fields;
if (IsLinearCode(C1) and IsLinearCode(C2)) or
(IsCyclicCode(C1) and IsCyclicCode(C2)) then
return C1 = C2;
elif IsLinearCode(C1) or IsLinearCode(C2) then
return false; ##one is linear, the other is not, so not equal
fi;
if Set(AsSSortedList(C1)) = Set(AsSSortedList(C2)) then
fields := [WeightDistribution, InnerDistribution,
IsLinearCode, IsPerfectCode,
IsSelfDualCode, OuterDistribution, IsCyclicCode,
AutomorphismGroup, MinimumDistance, CoveringRadius];
for field in fields do
if not Tester(field)(C1) then
if Tester(field)(C2) then
Setter(field)(C1, field(C2));
fi;
else
if not Tester(field)(C2) then
Setter(field)(C2, field(C1));
fi;
fi;
od;
if not IsBound(C1!.boundsCoveringRadius) then
if IsBound(C2!.boundsCoveringRadius) then
C1!.boundsCoveringRadius := C2!.boundsCoveringRadius;
fi;
else
if not IsBound(C2!.boundsCoveringRadius) then
C2!.boundsCoveringRadius := C1!.boundsCoveringRadius;
fi;
fi;
C1!.lowerBoundMinimumDistance := Maximum(LowerBoundMinimumDistance(C1),
LowerBoundMinimumDistance(C2));
C2!.lowerBoundMinimumDistance := C1!.lowerBoundMinimumDistance;
C1!.upperBoundMinimumDistance := Minimum(UpperBoundMinimumDistance(C1),
UpperBoundMinimumDistance(C2));
C2!.upperBoundMinimumDistance := C1!.upperBoundMinimumDistance;
return true;
else
return false; #so C1 is not equal to C2
fi;
end);
InstallMethod(\=, "method for linear code = linear code", true,
[IsLinearCode, IsLinearCode], 0,
function(C1, C2)
local field, fields;
if IsCyclicCode(C1) and IsCyclicCode(C2) then
return C1 = C2;
elif IsCyclicCode(C1) or IsCyclicCode(C2) then
return false; ##one is cyclic, the other is not, so not equal.
fi;
if BaseMat(GeneratorMat(C1))=BaseMat(GeneratorMat(C2)) then
fields := [WeightDistribution, InnerDistribution,
IsLinearCode, IsPerfectCode,
IsSelfDualCode, OuterDistribution, IsCyclicCode,
AutomorphismGroup, MinimumDistance, CoveringRadius];
for field in fields do
if not Tester(field)(C1) then
if Tester(field)(C2) then
Setter(field)(C1, field(C2));
fi;
else
if not Tester(field)(C2) then
Setter(field)(C2, field(C1));
fi;
fi;
od;
if not IsBound(C1!.boundsCoveringRadius) then
if IsBound(C2!.boundsCoveringRadius) then
C1!.boundsCoveringRadius := C2!.boundsCoveringRadius;
fi;
else
if not IsBound(C2!.boundsCoveringRadius) then
C2!.boundsCoveringRadius := C1!.boundsCoveringRadius;
fi;
fi;
C1!.lowerBoundMinimumDistance := Maximum(LowerBoundMinimumDistance(C1),
LowerBoundMinimumDistance(C2));
C2!.lowerBoundMinimumDistance := C1!.lowerBoundMinimumDistance;
C1!.upperBoundMinimumDistance := Minimum(UpperBoundMinimumDistance(C1),
UpperBoundMinimumDistance(C2));
C2!.upperBoundMinimumDistance := C1!.upperBoundMinimumDistance;
return true;
else
return false; #so l is not equal to r
fi;
end);
InstallMethod(\=, "method for cyclic code = cyclic code", true,
[IsCyclicCode, IsCyclicCode], 0,
function(C1, C2)
local field, fields, bmdl, bmdr;
if GeneratorPol(C1) = GeneratorPol(C2) then
fields := [WeightDistribution, InnerDistribution,
IsLinearCode, IsPerfectCode,
IsSelfDualCode, OuterDistribution, IsCyclicCode,
AutomorphismGroup, MinimumDistance, CoveringRadius,
RootsOfCode];
for field in fields do
if not Tester(field)(C1) then
if Tester(field)(C2) then
Setter(field)(C1, field(C2));
fi;
else
if not Tester(field)(C2) then
Setter(field)(C2, field(C1));
fi;
fi;
od;
if not IsBound(C1!.boundsCoveringRadius) then
if IsBound(C2!.boundsCoveringRadius) then
C1!.boundsCoveringRadius := C2!.boundsCoveringRadius;
fi;
else
if not IsBound(C2!.boundsCoveringRadius) then
C2!.boundsCoveringRadius := C1!.boundsCoveringRadius;
fi;
fi;
C1!.lowerBoundMinimumDistance := Maximum(LowerBoundMinimumDistance(C1),
LowerBoundMinimumDistance(C2));
C2!.lowerBoundMinimumDistance := C1!.lowerBoundMinimumDistance;
C1!.upperBoundMinimumDistance := Minimum(UpperBoundMinimumDistance(C1),
UpperBoundMinimumDistance(C2));
C2!.upperBoundMinimumDistance := C1!.upperBoundMinimumDistance;
return true;
else
return false; #so l is not equal to r
fi;
end);
#############################################################################
##
#F SyndromeTable ( <C> ) . . . . . . . . . . . . . . . a Syndrome table of C
##
InstallMethod(SyndromeTable, "method for unrestricted code", true,
[IsCode], 0,
function(C)
if IsLinearCode(C) then
return SyndromeTable(C);
else
Error("the syndrome table is not defined for non-linear codes");
fi;
end);
InstallMethod(SyndromeTable, "method for linear code", true,
[IsLinearCode], 0,
function(C)
local H, L, F;
H := CheckMat(C);
if H = [] then
return [];
fi;
F := LeftActingDomain(C);
L := GuavaCosetLeadersMatFFE(List(H,List), F);
H := TransposedMat(H);
return Codeword(List(L, l-> [l, l*H]), F);
end);
#############################################################################
##
#F StandardArray( <C> ) . . . . . . . . . . . . a standard array for code C
##
## Post: returns a 3D-matrix. The first row contains all the codewords of C.
## The other rows contain the cosets, preceded by their coset leaders.
##
InstallMethod(StandardArray, "method for unrestricted code", true,
[IsCode], 0,
function(C)
if IsLinearCode(C) then
return StandardArray(C);
else
Error("a standard array is not defined for non-linear codes");
fi;
end);
InstallMethod(StandardArray, "method for linear code", true, [IsLinearCode], 0,
function(C)
local Els;
Els := AsSSortedList(C);
if CheckMat(C) = [] then
return [Els];
fi;
return List(Set(GuavaCosetLeadersMatFFE(CheckMat(C), LeftActingDomain(C))),
row -> List(Els, column -> row + column));
end);
#############################################################################
##
#F AutomorphismGroup( <C> ) . . . . . . . . the automorphism group of code
##
## The automorphism group is the largest permutation group of degree n such
## that for each permutation in the group C' = C
##
InstallOtherMethod(AutomorphismGroup, "method for unrestricted codes", true,
[IsCode], 0,
function(C)
local path;
path := DirectoriesPackagePrograms( "guava" );
if ForAny( ["desauto", "leonconv", "wtdist"],
f -> Filename( path, f ) = fail ) then
Print("desauto not loaded ... switching to PermutationGroup ...\n");
return PermutationGroup(C);
fi;
if Size(LeftActingDomain(C)) > 2 then
Print("This command calculates automorphism groups for binary codes only\n");
Print("... automatically switching to PermutationGroup ...\n");
return PermutationGroup(C);
elif IsLinearCode(C) then
return AutomorphismGroup(C);
else
return MatrixAutomorphisms(VectorCodeword(AsSSortedList(C)),
[], Group( () ));
fi;
end);
InstallOtherMethod(AutomorphismGroup, "method for linear codes", true,
[IsLinearCode], 0,
function(C)
local incode, inV, outgroup, infile,Ccalc,path;
path := DirectoriesPackagePrograms( "guava" );
if ForAny( ["desauto", "leonconv", "wtdist"],
f -> Filename( path, f ) = fail ) then
Print("desauto not loaded ... switching to PermutationGroup ...\n");
return PermutationGroup(C);
fi;
if Size(LeftActingDomain(C)) > 2 then
Print("This command calculates automorphism groups for binary codes only\n");
Print("... automatically switching to PermutationGroup ...\n");
return PermutationGroup(C);
fi;
incode := TmpName(); PrintTo( incode, "\n" );
inV := TmpName(); PrintTo( inV, "\n" );
outgroup := TmpName(); PrintTo( outgroup, "\n" );
infile := TmpName(); PrintTo( infile, "\n" );
# Calculate with dual code if it is smaller:
if Dimension(C) > QuoInt(WordLength(C), 2) then
Ccalc := DualCode(C);
else
Ccalc := ShallowCopy(C);
fi;
GuavaToLeon(Ccalc, incode);
Process(DirectoryCurrent(),
Filename(path, "wtdist"),
InputTextNone(),
OutputTextNone(),
["-q", Concatenation(incode,"::code"), MinimumDistance(Ccalc), Concatenation(inV, "::code")]
);
#Exec(Filename(DirectoriesPackagePrograms("guava"), "wtdist"),
# Concatenation("-q ",incode,"::code ",
# String(MinimumDistance(Ccalc))," ",inV,"::code"));
Process(DirectoryCurrent(),
Filename(path, "desauto"),
InputTextNone(),
OutputTextNone(),
["-code", "-q", Concatenation(incode,"::code"), Concatenation(inV, "::code"), outgroup]
);
#Exec(Filename(DirectoriesPackagePrograms("guava"), "desauto"),
# Concatenation("-code -q ",
# incode,"::code ",inV,"::code ",outgroup));
Process(DirectoryCurrent(),
Filename(path, "leonconv"),
InputTextNone(),
OutputTextNone(),
["-a", outgroup, infile]
);
#Exec(Filename(DirectoriesPackagePrograms("guava"), "leonconv"),
# Concatenation("-a ",outgroup," ", infile));
Read(infile);
#RemoveFiles(incode,inV,outgroup,infile);
return GUAVA_TEMP_VAR;
end);
## If the new partition backtrack algorithms are implemented, the previous
## function can be replaced by the next:
#InstallOtherMethod(AutomorphismGroup, "method for linear code", true,
# [IsLinearCode], 0,
#function(C)
# local Ccalc, InvSet;
# if Dimension(C) > QuoInt(WordLength(C), 2) then
# Ccalc := DualCode(C);
# else
# Ccalc := ShallowCopy(C);
# fi;
# InvSet := VectorCodeword(MinimumWeightWords(Ccalc));
# return AutomorphismGroupBinaryLinearCode(Ccalc, InvSet);
#end);
#############################################################################
##
## PermutationGroup( <C> ) . . . . . . PermutationGroup of non-binary code
##
## confusing name?
InstallMethod(PermutationGroup, "attribute method for linear codes", true,
[IsLinearCode], 0,
function(C)
local G0, Gell, G1, G2, Gt, L, k, i, j, G, F, A, aut, n, Sn, ell;
Print("\n To be deprecated. Please use PermutationAutomorphismGroup.\n");
F:=LeftActingDomain(C);
G1 := GeneratorMat(C);
G := List(G1,ShallowCopy);
k:=DimensionsMat(G)[1];
n:=DimensionsMat(G)[2];
TriangulizeMat(G);
Gt := TransposedMat(G);
Sn := SymmetricGroup(n);
A:=[];
for ell in Sn do
G2:= NullMat(n,k);
for j in [1..n] do
G2[j]:=Gt[OnPoints(j,ell)];
od; # j
Gell := TransposedMat(G2);
G0 := List(Gell,ShallowCopy);
TriangulizeMat(G0);
if G = G0 then Add(A, ell); fi;
od; # ell
if Length(A)>0 then
aut := Group(A);
else aut:=Group(());
fi;
return(aut);
end);
#############################################################################
##
## PermutationAutomorphismGroup( <C> ) . . Permutation automorphism
## group of linear (possibly non-binary) code
##
##
InstallMethod(PermutationAutomorphismGroup, "attribute method for linear codes", true,
[IsLinearCode], 0,
function(C)
local G0, Gell, G1, G2, Gt, L, k, i, j, G, F, A, aut, n, Sn, ell;
F:=LeftActingDomain(C);
G1 := GeneratorMat(C);
G := List(G1,ShallowCopy);
k:=DimensionsMat(G)[1];
n:=DimensionsMat(G)[2];
TriangulizeMat(G);
Gt := TransposedMat(G);
Sn := SymmetricGroup(n);
A:=[];
for ell in Sn do
G2:= NullMat(n,k);
for j in [1..n] do
G2[j]:=Gt[OnPoints(j,ell)];
od; # j
Gell := TransposedMat(G2);
G0 := List(Gell,ShallowCopy);
TriangulizeMat(G0);
if G = G0 then Add(A, ell); fi;
od; # ell
if Length(A)>0 then
aut := Group(A);
else aut:=Group(());
fi;
return(aut);
end);
#############################################################################
##
#F IsSelfOrthogonalCode( <C> ) . . . . . . . . . . . . . . . . . . . . . .
##
InstallTrueMethod(IsSelfOrthogonalCode, IsSelfDualCode);
InstallMethod(IsSelfOrthogonalCode, "method for unrestricted code", true,
[IsCode], 0,
function(C)
local El, M, zero, i, j, IsSO;
if IsLinearCode(C) then
return IsSelfOrthogonalCode(C);
fi;
El := AsSSortedList(C);
M := Size(C);
zero := Zero(LeftActingDomain(C));
i := 1; IsSO := true;
while (i <= M-1) and IsSO do
j := i+1;
while (j <= M) and (El[i]*El[j] = zero) do
j := j + 1;
od;
if j <= M then
IsSO := false;
fi;
i := i + 1;
od;
return IsSO;
end);
InstallMethod(IsSelfOrthogonalCode, "method for linear code", true,
[IsLinearCode], 0,
function(C)
local G, k;
G := GeneratorMat(C);
k := Dimension(C);
return G*TransposedMat(G) = NullMat(k,k,LeftActingDomain(C));
end);
#############################################################################
##
#F IsDoublyEvenCode( <C> ) . . . . . . . . . . . . . . . . . . . . . . . .
##
## Return true if and only if the code C is a binary linear code which has
## all codewords of weight divisible by 4 only.
##
## If a binary linear code is self-orthogonal and the weight of each row
## in its generator matrix is divisibly by 4, the code is doubly-even
## (see Theorem 1.4.8 in W. C. Huffman and V. Pless, "Fundamentals of
## error-correcting codes", Cambridge Univ. Press, 2003.)
##
InstallMethod(IsDoublyEvenCode, "method for binary linear code", true,
[IsLinearCode], 0,
function(C)
local G, i;
if LeftActingDomain(C)<>GF(2) then
Error("Code must be binary\n");
fi;
G:=GeneratorMat(C);
for i in [1..Size(G)] do;
if Weight(Codeword(G[i])) mod 4 <> 0 then
return false;
fi;
od;
return IsSelfOrthogonalCode(C);
end);
#############################################################################
##
#F IsSinglyEvenCode( <C> ) . . . . . . . . . . . . . . . . . . . . . . . .
##
## Return true if and only if the code C is a self-orthogonal binary linear
## code which is not doubly-even.
##
InstallMethod(IsSinglyEvenCode, "method for binary linear code", true,
[IsLinearCode], 0,
function(C)
if LeftActingDomain(C)<>GF(2) then
Error("Code must be binary\n");
fi;
return (IsSelfOrthogonalCode(C)) and (not IsDoublyEvenCode(C));
end);
#############################################################################
##
#F IsEvenCode( <C> ) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
##
## Return true if and only if the code C is a binary linear code which has
## even weight codewords--regardless whether or not it is self-orgthogonal.
##
InstallMethod(IsEvenCode, "method for binary linear code", true,
[IsLinearCode], 0,
function(C)
if LeftActingDomain(C)<>GF(2) then
Error("Code must be binary\n");
fi;
return (C = EvenWeightSubcode(C));
end);
#############################################################################
##
#F CodeIsomorphism( <C1>, <C2> ) . . the permutation that translates C1 into
#F C2 if C1 and C2 are equivalent, or false otherwise
##
InstallMethod(CodeIsomorphism, "method for two unrestricted codes", true,
[IsCode, IsCode], 0,
function(C1, C2)
local tp, field;
if WordLength(C1) <> WordLength(C2) or Size(C1) <> Size(C2)
or MinimumDistance(C1) <> MinimumDistance(C2)
or LeftActingDomain(C1) <> LeftActingDomain(C2) then
return false; #I think this is what we want (see IsEquivalentCode)
elif C1=C2 then
return ();
elif IsLinearCode(C1) and IsLinearCode(C2) then
return CodeIsomorphism(C1, C2 );
fi;
tp := TransformingPermutations(VectorCodeword(AsSSortedList(C1)),
VectorCodeword(AsSSortedList(C2)));
if tp <> false then
for field in [WeightDistribution, InnerDistribution,
IsPerfectCode, IsSelfDualCode] do
if not Tester(field)(C1) then
if Tester(field)(C2) then
Setter(field)(C1, field(C2));
fi;
else
if not Tester(field)(C2) then
Setter(field)(C2, field(C1));
fi;
fi;
od;
if not IsBound(C1!.boundsCoveringRadius) then
if IsBound(C2!.boundsCoveringRadius) then
C1!.boundsCoveringRadius := C2!.boundsCoveringRadius;
fi;
else
if not IsBound(C2!.boundsCoveringRadius) then
C2!.boundsCoveringRadius := C1!.boundsCoveringRadius;
fi;
fi;
C1!.lowerBoundMinimumDistance := Maximum(LowerBoundMinimumDistance(C1),
LowerBoundMinimumDistance(C2));
C2!.lowerBoundMinimumDistance := LowerBoundMinimumDistance(C1);
C1!.upperBoundMinimumDistance := Minimum(UpperBoundMinimumDistance(C1),
UpperBoundMinimumDistance(C2));
C2!.upperBoundMinimumDistance := UpperBoundMinimumDistance(C1);
return tp.columns;
else
return false; #yes, this is right
fi;
end);
InstallMethod(CodeIsomorphism, "method for two linear codes", true,
[IsLinearCode, IsLinearCode], 0,
function(C1, C2)
local code1,code2,cwcode1,cwcode2,output,infile, field;
if WordLength(C1) <> WordLength(C2) or Size(C1) <> Size(C2)
or MinimumDistance(C1) <> MinimumDistance(C2)
or LeftActingDomain(C1) <> LeftActingDomain(C2) then
return false; #I think this is what we want (see IsEquivalentCode)
elif C1=C2 then
return ();
elif LeftActingDomain(C1) <> GF(2) then
Error("GUAVA can only calculate equivalence over GF(2)");
fi;
code1 := TmpName(); PrintTo( code1, "\n" );
code2 := TmpName(); PrintTo( code2, "\n" );
cwcode1 := TmpName(); PrintTo( cwcode1, "\n" );
cwcode2 := TmpName(); PrintTo( cwcode2, "\n" );
output := TmpName(); PrintTo( output, "\n" );
infile := TmpName(); PrintTo( infile, "\n" );
GuavaToLeon(C1, code1);
GuavaToLeon(C2, code2);
#Exec(Filename(DirectoriesPackagePrograms("guava"), "wtdist"),
# Concatenation("-q ",code1,"::code ",
# String(MinimumDistance(C1))," ",cwcode1,"::code"));
Process(DirectoryCurrent(),
Filename(DirectoriesPackagePrograms("guava"), "wtdist"),
InputTextNone(),
OutputTextNone(),
["-q", Concatenation(code1,"::code"),
MinimumDistance(C1), Concatenation(cwcode1, "::code")]
);
#Exec(Filename(DirectoriesPackagePrograms("guava"), "wtdist"),
# Concatenation("-q ",code2,"::code ",
# String(MinimumDistance(C2))," ",cwcode2,"::code"));
Process(DirectoryCurrent(),
--> --------------------
--> maximum size reached
--> --------------------
[ zur Elbe Produktseite wechseln0.97Quellennavigators
Analyse erneut starten
]
|
