|
#############################################################################
##
#A codegen.gi GUAVA library Reinald Baart
#A &Jasper Cramwinckel
#A &Erik Roijackers
## &David Joyner
##
## This file contains info/functions for generating codes
##
## BCHCode modified 9-2004
## added 11-2004:
## comment in GoppaCode
## GeneralizedReedSolomonCode and record fields
## points, degree, ring,
## (added SpecialDecoder field later: SetSpecialDecoder(C, GRSDecoder);)
## EvaluationCode and record fields
## points, basis, ring,
## OnePointAGCode and record fields
## points, curve, multiplicity, ring
## weighted option for GeneralizedReedSolomonCode and record fields
## points, degree, ring, weights
## minor bug in EvaluationCode fixed 11-26-2004
## GeneratorMatCodeNC added 12-18-2004 (after release of guava 2.0)
## added 5-10-2005: SetSpecialDecoder(C, CyclicDecoder); to
## the cyclic codes which are not BCH codes
## in codegen.gi, line 2066, replace C.GeneratorMat
## by C.EvaluationMat
## added 5-13-2005: QQRCode
## added 11-27-2005: CheckMatCodeMutable with *mutable*
## generator and check matrices
## added 1-10-2006: QQRCodeNC Greg Coy and David Joyner
## added 1-2006: FerreroDesignCode, written with Peter Mayr
## added 12-2007 (CJ): ExtendedReedSolomonCode, QuasiCyclicCode,
## CyclicMDSCode, FourNegacirculantSelfDualCode functions.
##
DeclareRepresentation( "IsCodeDefaultRep",
IsAttributeStoringRep and IsComponentObjectRep and IsCode,
["name", "history", "lowerBoundMinimumDistance",
"upperBoundMinimumDistance", "boundsCoveringRadius"]);
DeclareHandlingByNiceBasis( "IsLinearCodeRep", "for linear codes" );
InstallTrueMethod( IsLinearCode, IsLinearCodeRep );
#T The following is of course a hack, as is much of the
#T ``pretend as if you were a vector space'' stuff.
#T (`IsLinearCode' changes harmless codes into vector spaces;
#T `AsLinearCode' would be clean, but now it is too late ...)
InstallTrueMethod( IsFreeLeftModule, IsLinearCodeRep );
### functions to work with NiceBasis functionality for Linear Codes.
InstallHandlingByNiceBasis( "IsLinearCodeRep", rec(
detect:= function( R, gens, V, zero )
return IsCodewordCollection( V );
end,
NiceFreeLeftModuleInfo:= ReturnFalse,
NiceVector:= function( C, w )
return VectorCodeword( w );
end,
UglyVector:= function( C, v )
return Codeword( v, Length( v ), LeftActingDomain( C ) );
end ) );
#############################################################################
##
#F ElementsCode( <L> [, <name> ], <F> ) . . . . . . code from list of words
##
InstallMethod(ElementsCode, "list,name,Field", true,
[IsList,IsString,IsField], 0,
function(L, name, F)
local test, C;
L := Codeword(L, F);
test := WordLength(L[1]);
if ForAny(L, i->WordLength(i) <> test) then
Error("All elements must have the same length");
fi;
test := FamilyObj(L[1]);
if ForAny(L, i->FamilyObj(i) <> test) then
Error ("All elements must have the same family");
fi;
L := Set(L);
C := Objectify(NewType(CollectionsFamily(test), IsCodeDefaultRep), rec());
SetLeftActingDomain(C, F);
SetAsSSortedList(C, L);
C!.name := name;
return C;
end);
InstallOtherMethod(ElementsCode, "list,Field", true, [IsList, IsField], 0,
function(L,F)
return ElementsCode(L, "user defined unrestricted code", F);
end);
InstallOtherMethod(ElementsCode, "list,name,fieldsize", true,
[IsList, IsString, IsInt], 0,
function(L, name, q)
return ElementsCode(L, name, GF(q));
end);
InstallOtherMethod(ElementsCode, "list,size of field", true, [IsList,IsInt], 0,
function(L, q)
return ElementsCode(L, "user defined unrestricted code", GF(q));
end);
##Create a linear code from a list of Codeword generators
LinearCodeByGenerators := function(F, gens)
local V, M, row, i, j;
V:= Objectify( NewType( FamilyObj( gens ),
IsLeftModule and
IsLinearCodeRep and IsCodeDefaultRep ),
rec() );
SetLeftActingDomain( V, F );
SetGeneratorsOfLeftModule( V, AsList( One(F)*gens ) );
SetIsLinearCode(V, true);
SetWordLength(V, Length(gens[1]));
#M:=[];
#for i in [1..Length(gens)] do
# row:=[];
# for j in [1..Length(gens[i])] do
# Append(row,[gens[i][j]]);
# od;
# Append(M, [row]);
#od;
#SetGeneratorMat(V, M); #The calling functions always handle setting the GenMat
return V;
end;
#############################################################################
##
#F RandomCode( <n>, <M> [, <F>] ) . . . . . . . . random unrestricted code
##
InstallMethod(RandomCode, "wordlength,codesize,field", true,
[IsInt, IsInt, IsField], 0,
function(n, M, F)
local L;
if Size(F)^n < M then
Error(Size(F),"^",n," < ",M);
fi;
L := [];
while Length(L) < M do
AddSet(L, List([1..n], i -> Random(F)));
od;
return ElementsCode(L, "random unrestricted code", F);
end);
InstallOtherMethod(RandomCode, "wordlength,codesize", true, [IsInt, IsInt], 0,
function(n, M)
return RandomCode(n, M, GF(2));
end);
InstallOtherMethod(RandomCode, "wordlength,codesize,fieldsize", true,
[IsInt, IsInt, IsInt], 0,
function(n, M, q)
return RandomCode(n, M, GF(q));
end);
#############################################################################
##
#F HadamardCode( <H | n> [, <t>] ) . Hadamard code of <t>'th kind, order <n>
##
InstallMethod(HadamardCode, "matrix, kind (int)", true, [IsMatrix, IsInt], 0,
function(H, t)
local n, vec, C;
n := Length(H);
if H * TransposedMat(H) <> n * IdentityMat(n,n) then
Error("The matrix is not a Hadamard matrix");
fi;
H := (H-1)/(-2);
if t = 1 then
H := TransposedMat(TransposedMat(H){[2..n]});
C := ElementsCode(H, Concatenation("Hadamard code of order ",
String(n)), GF(2) );
C!.lowerBoundMinimumDistance := n/2;
C!.upperBoundMinimumDistance := n/2;
vec := NullVector(n);
# this was ... := NullVector(n+1);
# but this seems to be wrong -- Eric Minkes
vec[1] := 1;
vec[n/2+1] := Size(C) - 1;
SetInnerDistribution(C, vec);
elif t = 2 then
H := ShallowCopy( TransposedMat(TransposedMat(H){[2..n]}) );
Append(H, 1 - H);
C := ElementsCode(H, Concatenation("Hadamard code of order ",
String(n)), GF(2) );
C!.lowerBoundMinimumDistance := n/2 - 1;
C!.upperBoundMinimumDistance := n/2 - 1;
vec := NullVector(n);
vec[1] := 1;
vec[n] := 1;
# this was ... [n+1]...
# but this seems to be wrong -- Eric Minkes
vec[n/2] := Size(C)/2 - 1;
vec[n/2+1] := Size(C)/2 - 1;
SetInnerDistribution(C, vec);
else
Append(H, 1 - H);
C := ElementsCode( H, Concatenation("Hadamard code of order ",
String(n)), GF(2) );
C!.lowerBoundMinimumDistance := n/2;
C!.upperBoundMinimumDistance := n/2;
vec := NullVector(n);
vec[1] := 1;
vec[n+1] := 1;
vec[n/2+1] := Size(C) - 2;
SetInnerDistribution(C, vec);
fi;
return(C);
end);
InstallOtherMethod(HadamardCode, "order, kind (int)", true, [IsInt, IsInt], 0,
function(n, t)
return HadamardCode(HadamardMat(n), t);
end);
InstallOtherMethod(HadamardCode, "matrix", true, [IsMatrix], 0,
function(H)
return HadamardCode(H, 3);
end);
InstallOtherMethod(HadamardCode, "order", true, [IsInt], 0,
function(n)
return HadamardCode(HadamardMat(n), 3);
end);
InstallOtherMethod(HadamardCode, "matrix, kind (string)", true,
[IsMatrix, IsString], 0,
function(H, t)
if t in ["a", "A", "1"] then
return HadamardCode(H, 1);
elif t in ["b", "B", "2"] then
return HadamardCode(H, 2);
else
return HadamardCode(H, 3);
fi;
end);
InstallOtherMethod(HadamardCode, "order, kind (string)", true,
[IsInt, IsString], 0,
function(n, t)
if t in ["a", "A", "1"] then
return HadamardCode(HadamardMat(n), 1);
elif t in ["b", "B", "2"] then
return HadamardCode(HadamardMat(n), 2);
else
return HadamardCode(HadamardMat(n), 3);
fi;
end);
#############################################################################
##
#F ConferenceCode( <n | M> ) . . . . . . . . . . code from conference matrix
##
InstallMethod(ConferenceCode, "matrix", true, [IsMatrix], 0,
function(S)
local n, I, J, F, els, w, wd, C;
n := Length(S);
if S*TransposedMat(S) <> (n-1)*IdentityMat(n) or
TransposedMat(S) <> S then
Error("argument must be a symmetric conference matrix");
fi;
# Normalize S by multiplying rows and columns:
for I in [2..n] do
if S[I][1] <> 1 then
for J in [1..n] do
S[I][J] := S[I][J] * -1;
od;
fi;
od;
for J in [2..n] do
if S[1][J] <> 1 then
for I in [1..n] do
S[I][J] := S[I][J] * -1;
od;
fi;
od;
# Strip first row and first column:
S := List([2..n], i-> S[i]{[2..n]});
n := n - 1;
F := GF(2);
els := [NullWord(n, F)];
I := IdentityMat(n);
J := NullMat(n,n) + 1;
Append(els, Codeword(1/2 * (S+I+J), F));
Append(els, Codeword(1/2 * (-S+I+J), F));
Add( els, Codeword( List([1..n], x -> One(F) ), n, One(F) ) );
C := ElementsCode( els, "conference code", F);
w := Weight(AsSSortedList(C)[2]);
wd := List([1..n+1], x -> 0);
wd[1] := 1; wd[n+1] := 1;
wd[w+1] := Size(C) - 2;
SetWeightDistribution(C, wd);
C!.lowerBoundMinimumDistance := (n-1)/2;
C!.upperBoundMinimumDistance := (n-1)/2;
return C;
end);
InstallOtherMethod(ConferenceCode, "integer", true, [IsInt], 0,
function(n)
local LegendreSym, zero, QRes, E, I, S, F, els, J, w, wd, C;
LegendreSym := function(i)
if i = zero then
return 0;
elif i in QRes then
return 1;
else
return -1;
fi;
end;
if (not IsPrimePowerInt(n)) or (n mod 4 <> 1) then
Error ("n must be a primepower and n mod 4 = 1");
fi;
E := AsSSortedList(GF(n));
zero := E[1];
QRes := [];
for I in E do
AddSet(QRes, I^2);
od;
S := List(E, i->List(E, j->LegendreSym(j-i)));
F := GF(2);
els := [NullWord(n, F)];
I := IdentityMat(n);
J := NullMat(n,n) + 1;
Append(els, Codeword(1/2 * (S+I+J), F));
Append(els, Codeword(1/2 * (-S+I+J), F));
Add( els, Codeword( List([1..n], x -> One(F) ), n, One(F) ) );
C := ElementsCode( els, "conference code", F);
w := Weight(AsSSortedList(C)[2]);
wd := List([1..n+1], x -> 0);
wd[1] := 1; wd[n+1] := 1;
wd[w+1] := Size(C) - 2;
SetWeightDistribution(C, wd);
C!.lowerBoundMinimumDistance := (n-1)/2;
C!.upperBoundMinimumDistance := (n-1)/2;
return C;
end);
#############################################################################
##
#F MOLSCode( [ <n>, ] <q> ) . . . . . . . . . . . . . . . . code from MOLS
##
## MOLSCode([n, ] q) returns a (n, q^2, n-1) code over GF(q)
## by creating n-2 mutually orthogonal latin squares of size q.
## If n is omitted, a wordlength of 4 will be set.
## If there are no n-2 MOLS known, the code will return an error
##
InstallMethod(MOLSCode, "wordlength,size of field", true, [IsInt, IsInt], 0,
function(n,q)
local M, els, i, j, k, wd, C;
M := MOLS(q, n-2);
if M = false then
Error("No ", n-2, " MOLS of order ", q, " are known");
else
els := [];
for i in [1..q] do
for j in [1..q] do
els[(i-1)*q+j] := [];
els[(i-1)*q+j][1] := i-1;
els[(i-1)*q+j][2]:= j-1;
for k in [3..n] do
els[(i-1)*q+j][k]:= M[k-2][i][j];
od;
od;
od;
C := ElementsCode( els, Concatenation("code generated by ",
String(n-2), " MOLS of order ", String(q)), GF(q) );
C!.lowerBoundMinimumDistance := n - 1;
C!.upperBoundMinimumDistance := n - 1;
wd := List( [1..n+1], x -> 0 );
wd[1] := 1;
wd[n] := (q-1) * n;
wd[n+1] := (q-1) * (q + 1 - n);
SetWeightDistribution(C, wd);
return C;
fi;
end);
InstallOtherMethod(MOLSCode, "wordlength,field", true, [IsInt, IsField], 0,
function(n, F)
return MOLSCode(n, Size(F));
end);
InstallOtherMethod(MOLSCode, "fieldsize", true, [IsInt], 0,
function(q)
return MOLSCode(4, q);
end);
InstallOtherMethod(MOLSCode, "field", true, [IsField], 0,
function(F)
return MOLSCode(4, Size(F));
end);
## Was commented out in gap 3.4.4 Guava version.
#############################################################################
##
#F QuadraticCosetCode( <Q> ) . . . . . . . . . . coset of RM(1,m) in R(2,m)
##
## QuadraticCosetCode(Q) returns a coset of the ReedMullerCode of
## order 1 (R(1,m)) in R(2,m) where m is the size of square matrix Q.
## Q is the upper triangular matrix that defines the quadratic part of
## the boolean functions that are in the coset.
##
#QuadraticCosetCode := function(arg)
# local Q, m, V, R, RM1, k, f, C, h, wd;
# if Length(arg) = 1 and IsMat(arg[1]) then
# Q := arg[1];
# else
# Error("usage: QuadraticCosetCode( <mat> )");
# fi;
# m := Length(Q);
# V := Tuples(Elements(GF(2)), m);
# R := V*Q*TransposedMat(V);
# f := List([1..2^m], i->R[i][i]);
# RM1 := Concatenation(NullMat(1,2^m,GF(2))+GF(2).one,
# TransposedMat(Tuples(Elements(GF(2)), m)));
# k := Length(RM1);
# C := rec(
# isDomain := true,
# isCode := true,
# operations := CodeOps,
# baseField := GF(2),
# wordLength := 2^m,
# elements := Codeword(List(Tuples(Elements(GF(2)), k) * RM1, t-> t+f)),
# lowerBoundMinimumDistance := 2^(m-1),
# upperBoundMinimumDistance := 2^(m-1)
# );
# h := RankMat(Q + TransposedMat(Q))/2;
# wd := NullMat(1, 2^m+1)[1];
# wd[2^(m-1) - 2^(m-h-1) + 1] := 2^(2*h);
# wd[2^(m-1) + 1] := 2^(m+1) - 2^(2*h + 1);
# wd[2^(m-1) + 2^(m-h-1) + 1] := 2^(2*h);
# C.weightDistribution := wd;
# C.name := "quadratic coset code";
# return C;
#end;
#############################################################################
##
#F GeneratorMatCode( <G> [, <name> ], <F> ) . . code from generator matrix
##
InstallMethod(GeneratorMatCode, "generator matrix, name, field", true,
[IsMatrix, IsString, IsField], 0,
function(G, name, F)
local C;
if (Length(G) = 0) or (Length(G[1]) = 0) then
Error("Use NullCode to generate a code with dimension 0");
fi;
G := G*One(F);
G := BaseMat(G);
C := LinearCodeByGenerators(F, Codeword(G,F));
SetGeneratorMat(C, G);
SetWordLength(C, Length(G[1]));
C!.name := name;
return C;
end);
InstallOtherMethod(GeneratorMatCode, "generator matrix, field", true,
[IsMatrix, IsField], 0,
function(G, F)
return GeneratorMatCode(G, "code defined by generator matrix", F);
end);
InstallOtherMethod(GeneratorMatCode, "generator matrix, name, size of field",
true, [IsMatrix, IsString, IsInt], 0,
function(G, name, q)
return GeneratorMatCode(G, name, GF(q));
end);
InstallOtherMethod(GeneratorMatCode, "generator matrix, size of field", true,
[IsMatrix, IsInt], 0,
function(G, q)
return GeneratorMatCode(G, "code defined by generator matrix", GF(q));
end);
#############################################################################
##
#F GeneratorMatCodeNC( <G> , <F> ) . . code from generator matrix
##
## same as GeneratorMatCode but does not compute upper + lower bounds
## for the minimum distance or covering radius
##
InstallMethod(GeneratorMatCodeNC, "generator matrix, field", true,
[IsMatrix, IsField], 0,
function(G, F)
return GeneratorMatCode(G, "code defined by generator matrix, NC", F);
end);
#############################################################################
##
#F CheckMatCodeMutable( <H> [, <name> ], <F> ) . . code from check matrix
## The generator matrix is mutable
##
InstallMethod(CheckMatCodeMutable, "check matrix, name, field", true,
[IsMatrix, IsString, IsField], 0,
function(H, name, F)
local G, H2, C, dimC;
if (Length(H) = 0) or (Length(H[1]) = 0) then
Error("use WholeSpaceCode to generate a code with redundancy 0");
fi;
H := VectorCodeword(Codeword(H, F));
H2 := BaseMat(H);
if Length(H2) < Length(H) then
H := H2;
fi;
# Get generator matrix from H
if IsInStandardForm(H, false) then
dimC := Length(H[1]) - Length(H);
if dimC = 0 then
G := [];
else
G := TransposedMat(Concatenation(IdentityMat( dimC, F ),
List(-H, x->x{[1..dimC]})));
fi;
else
G := NullspaceMat(TransposedMat(H));
fi;
if Length(G) = 0 then # Call NullCode. Length(H=I) = n-k, in this case.
# Length(G) = k = 0 => n = Length(H).
C := NullCode(Length(H), F);
C!.name := name;
return C;
fi;
C := LinearCodeByGenerators(F,Codeword(G, F));
SetGeneratorMat(C, ShallowCopy(G));
SetCheckMat(C, ShallowCopy(H));
SetWordLength(C, Length(G[1]));
C!.name := name;
return C;
end);
InstallOtherMethod(CheckMatCodeMutable, "check matrix, field",
true, [IsMatrix, IsField], 0,
function(H, F)
return CheckMatCode(H, "code defined by check matrix", F);
end);
InstallOtherMethod(CheckMatCodeMutable, "check matrix, name, size of field", true, [IsMatrix, IsString, IsInt], 0,
function(H, name, q)
return CheckMatCode(H, name, GF(q));
end);
InstallOtherMethod(CheckMatCodeMutable, "check matrix, size of field",
true, [IsMatrix, IsInt], 0,
function(H, q)
return CheckMatCodeMutable(H, "code defined by check matrix", GF(q));
end);
#############################################################################
##
#F CheckMatCode( <H> [, <name> ], <F> ) . . . . . . code from check matrix
##
InstallMethod(CheckMatCode, "check matrix, name, field", true,
[IsMatrix, IsString, IsField], 0,
function(H, name, F)
local G, H2, C, dimC;
if (Length(H) = 0) or (Length(H[1]) = 0) then
Error("use WholeSpaceCode to generate a code with redundancy 0");
fi;
H := VectorCodeword(Codeword(H, F));
H2 := BaseMat(H);
if Length(H2) < Length(H) then
H := H2;
fi;
# Get generator matrix from H
if IsInStandardForm(H, false) then
dimC := Length(H[1]) - Length(H);
if dimC = 0 then
G := [];
else
G := TransposedMat(Concatenation(IdentityMat( dimC, F ),
List(-H, x->x{[1..dimC]})));
fi;
else
G := NullspaceMat(TransposedMat(H));
fi;
if Length(G) = 0 then # Call NullCode. Length(H=I) = n-k, in this case.
# Length(G) = k = 0 => n = Length(H).
C := NullCode(Length(H), F);
C!.name := name;
return C;
fi;
C := LinearCodeByGenerators(F,Codeword(G, F));
SetGeneratorMat(C, G);
SetCheckMat(C, H);
SetWordLength(C, Length(G[1]));
C!.name := name;
return C;
end);
InstallOtherMethod(CheckMatCode, "check matrix, field", true,
[IsMatrix, IsField], 0,
function(H, F)
return CheckMatCode(H, "code defined by check matrix", F);
end);
InstallOtherMethod(CheckMatCode, "check matrix, name, size of field", true,
[IsMatrix, IsString, IsInt], 0,
function(H, name, q)
return CheckMatCode(H, name, GF(q));
end);
InstallOtherMethod(CheckMatCode, "check matrix, size of field", true,
[IsMatrix, IsInt], 0,
function(H, q)
return CheckMatCode(H, "code defined by check matrix", GF(q));
end);
#############################################################################
##
#F RandomLinearCode( <n>, <k> [, <F>] ) . . . . . . . . random linear code
##
InstallMethod(RandomLinearCode, "n,k,field", true, [IsInt, IsInt, IsField], 0,
function(n, k, F)
if k = 0 then
return NullCode( n, F );
else
return GeneratorMatCode(PermutedCols(List(IdentityMat(k,F), i ->
Concatenation(i,List([k+1..n],j->Random(F)))),
Random(SymmetricGroup(n))), "random linear code", F);
fi;
end);
InstallOtherMethod(RandomLinearCode, "n,k,size of field", true,
[IsInt, IsInt, IsInt], 0,
function(n, k, q)
return RandomLinearCode(n, k, GF(q));
end);
InstallOtherMethod(RandomLinearCode, "n,k", true, [IsInt, IsInt], 0,
function(n, k)
return RandomLinearCode(n, k, GF(2));
end);
#############################################################################
##
#F HammingCode( <r> [, <F>] ) . . . . . . . . . . . . . . . . Hamming code
##
InstallMethod(HammingCode, "r,F", true, [IsInt, IsField], 0,
function(r, F)
local q, H, H2, C, i, j, n, TupAllow, wd;
TupAllow := function(W)
local l;
l := 1;
while (W[l] = Zero(F)) and l < Length(W) do
l := l + 1;
od;
return (W[l] = One(F));
end;
q := Size(F);
if not IsPrimePowerInt(q) then
Error("q must be prime power");
fi;
H := Tuples(AsSSortedList(F), r);
H2 := [];
j := 1;
for i in [1..Length(H)] do
if TupAllow(H[i]) then
H2[j] := H[i];
j := j + 1;
fi;
od;
n := (q^r-1)/(q-1);
C := CheckMatCode(TransposedMat(H2), Concatenation("Hamming (", String(r),
",", String(q), ") code"), F);
C!.lowerBoundMinimumDistance := 3;
C!.upperBoundMinimumDistance := 3;
C!.boundsCoveringRadius := [ 1 ];
SetIsPerfectCode(C, true);
SetIsSelfDualCode(C, false);
SetSpecialDecoder(C, HammingDecoder);
if q = 2 then
SetIsNormalCode(C, true);
wd := [1, 0];
for i in [2..n] do
Add(wd, 1/i * (Binomial(n, i-1) - wd[i] - (n-i+2)*wd[i-1]));
od;
SetWeightDistribution(C, wd);
fi;
return C;
end);
InstallOtherMethod(HammingCode, "r,size of field", true, [IsInt, IsInt], 0,
function(r, q)
return HammingCode(r, GF(q));
end);
InstallOtherMethod(HammingCode, "r", true, [IsInt], 0,
function(r)
return HammingCode(r, GF(2));
end);
#############################################################################
##
#F SimplexCode( <r>, <F> ) . The SimplexCode is the Dual of the HammingCode
##
InstallMethod(SimplexCode, "redundancy, field", true, [IsInt, IsField], 0,
function(r, F)
local C;
C := DualCode( HammingCode(r,F) );
C!.name := "simplex code";
if F = GF(2) then
SetIsNormalCode(C, true);
C!.boundsCoveringRadius := [ 2^(r-1) - 1 ];
fi;
return C;
end);
InstallOtherMethod(SimplexCode, "redundancy, fieldsize", true,[IsInt,IsInt],0,
function(r, q)
return SimplexCode(r, GF(q));
end);
InstallOtherMethod(SimplexCode, "redundancy", true, [IsInt], 0,
function(r)
return SimplexCode(r, GF(2));
end);
#############################################################################
##
#F ReedMullerCode( <r>, <k> ) . . . . . . . . . . . . . . Reed-Muller code
##
## ReedMullerCode(r, k) creates a binary Reed-Muller code of dimension k,
## order r; 0 <= r <= k
##
InstallMethod(ReedMullerCode, "dimension, order", true, [IsInt,IsInt], 0,
function(r,k)
local mat,c,src,dest,index,num,dim,C,wd, h,t,A, bcr;
if r > k then
return ReedMullerCode(k, r); #for compatibility with older versions
#of guava, It used to be
#ReedMullerCode(k, r);
fi;
mat := [ [] ];
num := 2^k;
dim := Sum(List([0..r], x->Binomial(k,x)));
for t in [1..num] do
mat[1][t] := Z(2)^0;
od;
if r > 0 then
Append(mat, TransposedMat(Tuples ([0*Z(2), Z(2)^0], k)));
for t in [2..r] do
for index in Combinations([1..k], t) do
dest := List([1..2^k], i->Product(index, j->mat[j+1][i]));
Append(mat, [dest]);
od;
od;
fi;
C := GeneratorMatCode( mat, Concatenation("Reed-Muller (", String(r), ",",
String(k), ") code"), GF(2) );
C!.lowerBoundMinimumDistance := 2^(k-r);
C!.upperBoundMinimumDistance := 2^(k-r);
SetIsPerfectCode(C, false);
SetIsSelfDualCode(C, (2*r = k-1));
if r = 0 then
wd := List([1..num + 1], x -> 0);
wd[1] := 1;
wd[num+1] := 1;
SetWeightDistribution(C, wd);
elif r = 1 then
wd := List([1..num + 1], x -> 0);
wd[1] := 1;
wd[num + 1] := 1;
wd[num / 2 + 1] := Size(C) - 2;
SetWeightDistribution(C, wd);
elif r = 2 then
wd := List([1..num + 1], x -> 0);
wd[1] := 1;
wd[num + 1] := 1;
for h in [1..QuoInt(k,2)] do
A := 2^(h*(h+1));
for t in [0..2*h-1] do
A := A*(2^(k-t)-1);
od;
for t in [1..h] do
A := A/(2^(2*t)-1);
od;
wd[2^(k-1)+2^(k-1-h)+1] := A;
wd[2^(k-1)-2^(k-1-h)+1] := A;
od;
wd[2^(k-1)+1] := Size(C)-Sum(wd);
SetWeightDistribution(C, wd);
fi;
bcr := BoundsCoveringRadius( C );
if 0 <= r and r <= k-3 then
if IsEvenInt( r ) then
C!.boundsCoveringRadius :=
[ Maximum( 2^(k-r-3)*(r+4), bcr[1] )
.. Maximum( bcr ) ];
else
C!.boundsCoveringRadius :=
[ Maximum( 2^(k-r-3)*(r+5), bcr[ 1 ] )
.. Maximum( bcr ) ];
fi;
fi;
if r = k then
SetCoveringRadius(C, 0);
C!.boundsCoveringRadius := [ 0 ];
elif r = k - 1 then
SetCoveringRadius(C, 1);
C!.boundsCoveringRadius := [ 1 ];
elif r = k - 2 then
SetCoveringRadius(C, 2);
C!.boundsCoveringRadius := [ 2 ];
elif r = k - 3 then
if IsEvenInt( k ) then
SetCoveringRadius(C, k + 2 );
C!.boundsCoveringRadius := [ k + 2 ];
else
SetCoveringRadius(C, k + 1 );
C!.boundsCoveringRadius := [ k + 1 ];
fi;
elif r = 0 then
SetCoveringRadius(C, 2^(k-1) );
C!.boundsCoveringRadius := [ 2^(k-1) ];
elif r = 1 then
if IsEvenInt( k ) then
SetCoveringRadius(C, 2^(k-1) - 2^(k/2-1) );
C!.boundsCoveringRadius := [ 2^(k-1) - 2^(k/2-1) ];
elif k = 5 then
SetCoveringRadius(C, 12 );
C!.boundsCoveringRadius := [ 12 ];
elif k = 7 then
SetCoveringRadius(C, 56 );
C!.boundsCoveringRadius := [ 56 ];
elif k >= 15 then
C!.boundsCoveringRadius := [ 2^(k-1) - 2^((k+1)/2)*27/64
.. 2^(k-1) - 2^( QuoInt(k,2)-1 ) ];
else
C!.boundsCoveringRadius := [ 2^(k-1) - 2^((k+1)/2)/2
.. 2^(k-1) - 2^( QuoInt(k,2)-1 ) ];
fi;
elif r = 2 then
if k = 6 then
SetCoveringRadius(C, 18 );
C!.boundsCoveringRadius := [ 18 ];
elif k = 7 then
C!.boundsCoveringRadius := [ 40 .. 44 ];
elif k = 8 then
C!.boundsCoveringRadius := [ 84
.. Maximum( bcr ) ];
fi;
elif r = 3 then
if k = 7 then
C!.boundsCoveringRadius := [ 20 .. 23 ];
fi;
elif r = 4 then
if k = 8 then
C!.boundsCoveringRadius := [ 22
.. Maximum( bcr ) ];
fi;
fi;
if r = 1 and
( IsEvenInt( k ) or k = 3 or k = 5 or k = 7 ) then
SetIsNormalCode(C, true);
fi;
return C;
end);
#############################################################################
##
#F LexiCode( <M | n>, <d>, <F> ) . . . . . Greedy code with standard basis
##
InstallMethod(LexiCode, "basis,distance,field", true,
[IsMatrix, IsInt, IsField], 0,
function(M, d, F)
local base, n, k, one, zero, elms, Sz, vec, word, i, dist, carry, pos, C;
base := VectorCodeword(Codeword(M, F));
n := Length(base[1]);
k := Length(base);
one := One(F);
zero := Zero(F);
elms := [];
Sz := 0;
vec := NullVector(k,F);
repeat
word := vec * base;
i := 1;
dist := d;
while (dist>=d) and (i <= Sz) do
dist := DistanceVecFFE(word, elms[i]);
i := i + 1;
od;
if dist >= d then
Add(elms,ShallowCopy(word));
Sz := Sz + 1;
fi;
# generate the (lexicographical) next word in F^k
carry := true;
pos := k;
while carry and (pos > 0) do
if vec[pos] = zero then
carry := false;
vec[pos] := one;
else
vec[pos] := PrimitiveRoot(F)^(LogFFE(vec[pos],PrimitiveRoot(F))+1);
if vec[pos] = one then
vec[pos] := zero;
else
carry := false;
fi;
fi;
pos := pos - 1;
od;
until carry;
if Size(F) = 2 then # or even (2^(2^LogInt(LogInt(q,2),2)) = q) ?
C := GeneratorMatCode(elms, "lexicode", F);
else
C := ElementsCode(elms, "lexicode", F);
fi;
C!.lowerBoundMinimumDistance := d;
return C;
end);
InstallOtherMethod(LexiCode, "basis,distance,size of field", true,
[IsMatrix, IsInt, IsInt], 0,
function(M, d, q)
return LexiCode(M, d, GF(q));
end);
InstallOtherMethod(LexiCode, "wordlength,distance,field", true,
[IsInt, IsInt, IsField], 0,
function(n, d, F)
return LexiCode(IdentityMat(n,F), d, F);
end);
InstallOtherMethod(LexiCode, "wordlength,distance,size of field", true,
[IsInt, IsInt, IsInt], 0,
function(n, d, q)
return LexiCode(IdentityMat(n, GF(q)), d, GF(q));
end);
#############################################################################
##
#F GreedyCode( <M>, <d> [, <F>] ) . . . . Greedy code from list of elements
##
InstallMethod(GreedyCode, "matrix,design distance,Field", true,
[IsMatrix, IsInt, IsField], 0,
function(M,d,F)
local space, n, word, elms, Sz, i, dist, C;
space := VectorCodeword(Codeword(M,F));
n := Length(space[1]);
elms := [space[1]];
Sz := 1;
for word in space do
i := 1;
repeat
dist := DistanceVecFFE(word, elms[i]);
i := i + 1;
until dist < d or i > Sz;
if dist >= d then
Add(elms, word);
Sz := Sz + 1;
fi;
od;
C := ElementsCode(elms, "Greedy code, user defined basis", F);
C!.lowerBoundMinimumDistance := d;
return C;
end);
InstallOtherMethod(GreedyCode, "matrix,design distance,size of field", true,
[IsMatrix, IsInt, IsInt], 0,
function(M,d,q)
return GreedyCode(M,d,GF(q));
end);
InstallOtherMethod(GreedyCode, "matrix,design distance", true,
[IsMatrix,IsInt], 0,
function(M,d)
return GreedyCode(M,d,DefaultField(Flat(M)));
end);
#############################################################################
##
#F AlternantCode( <r>, <Y> [, <alpha>], <F> ) . . . . . . . Alternant code
##
InstallMethod(AlternantCode, "redundancy, Y, alpha, field", true,
[IsInt, IsList, IsList, IsField], 0,
function(r, Y, els, F)
local C, n, q, i, temp;
n := Length(Y);
els := Set(VectorCodeword(Codeword(els, F)));
Y := VectorCodeword(Codeword(Y, F) );
if ForAny(Y, i-> i = Zero(F)) then
Error("Y contains zero");
elif Length(els) <> Length(Y) then
Error("<Y> and <alpha> have inequal length or <alpha> is not distinct");
fi;
q := Characteristic(F);
temp := NullMat(n, n, F);
for i in [1..n] do
temp[i][i] := Y[i];
od;
Y := temp;
C := CheckMatCode( BaseMat(VerticalConversionFieldMat( List([0..r-1],
i -> List([1..n], j-> els[j]^i)) * Y)), "alternant code", F );
C!.lowerBoundMinimumDistance := r + 1;
return C;
end);
InstallOtherMethod(AlternantCode, "redundancy, Y, alpha, fieldsize", true,
[IsInt, IsList, IsList, IsInt], 0,
function(r, Y, a, q)
return AlternantCode(r, Y, a, GF(q));
end);
InstallOtherMethod(AlternantCode, "redundancy, Y, field", true,
[IsInt, IsList, IsField], 0,
function(r, Y, F)
return AlternantCode(r, Y, AsSSortedList(F){[2..Length(Y)+1]}, F);
end);
InstallOtherMethod(AlternantCode, "redundancy, Y, fieldsize", true,
[IsInt, IsList, IsInt], 0,
function(r, Y, q)
return AlternantCode(r, Y, AsSSortedList(GF(q)){[2..Length(Y)+1]}, GF(q));
end);
#############################################################################
##
#F GoppaCode( <G>, <L | n> ) . . . . . . . . . . . . . . classical Goppa code
##
InstallGlobalFunction(GoppaCode,
function(arg)
local C, GP, F, L, n, q, m, r, zero, temp;
GP := PolyCodeword(Codeword(arg[1]));
F := CoefficientsRing(DefaultRing(GP));
q := Characteristic(F);
m := Dimension(F);
F := GF(q);
zero := Zero(F);
r := DegreeOfLaurentPolynomial(GP);
# find m
if IsInt(arg[2]) then
n := arg[2];
m := Maximum(m, LogInt(n,q));
repeat
L := Filtered(AsSSortedList(GF(q^m)),i -> Value(GP,i) <> zero);
m := m + 1;
until Length(L) >= n;
m := m - 1;
L := L{[1..n]};
else
L := arg[2];
n := Length(L);
m := Maximum(m, Dimension(DefaultField(L)));
fi;
C := CheckMatCode( BaseMat(VerticalConversionFieldMat( List([0..r-1],
i-> List(L, j-> (j)^i / Value(GP, j) )) )), "classical Goppa code", F);
# Make the code
temp := Factors(GP);
if (q = 2) and (Length(temp) = Length(Set(temp))) then
# second condition checks if the roots of G are distinct
C!.lowerBoundMinimumDistance := Minimum(n, 2*r + 1);
else
C!.lowerBoundMinimumDistance := Minimum(n, r + 1);
fi;
return C;
end);
#############################################################################
##
#F CordaroWagnerCode( <n> ) . . . . . . . . . . . . . . Cordaro-Wagner code
##
InstallMethod(CordaroWagnerCode, "length", true, [IsInt], 0,
function(n)
local r, C, zero, one, F, d, wd;
if n < 2 then
Error("n must be 2 or more");
fi;
r := Int((n+1)/3);
d := (2 * r - Int( (n mod 3) / 2) );
F := GF(2);
zero := Zero(F);
one := One(F);
C := GeneratorMatCode( [Concatenation(List([1..r],i -> zero),
List([r+1..n],i -> one)),
Concatenation(List([r+1..n],i -> one), List([1..r],
i -> zero))], "Cordaro-Wagner code", F );
C!.lowerBoundMinimumDistance := d;
C!.upperBoundMinimumDistance := d;
wd := List([1..n+1], i-> 0);
wd[1] := 1;
wd[2*r+1] := 1;
wd[n-r+1] := wd[n-r+1] + 2;
SetWeightDistribution(C, wd);
return C;
end);
#############################################################################
##
#F GeneralizedSrivastavaCode( <a>, <w>, <z> [, <t>] [, <F>] ) . . . . . .
##
InstallMethod(GeneralizedSrivastavaCode, "a,w,z,t,F", true,
[IsList, IsList, IsList, IsInt, IsField], 0,
function(a,w,z,t,F)
local C, n, s, i, H;
a := VectorCodeword(Codeword(a, F));
w := VectorCodeword(Codeword(w, F));
z := VectorCodeword(Codeword(z, F));
n := Length(a);
s := Length(w);
if Length(Set(Concatenation(a,w))) <> n + s then
Error("<alpha> and w are not distinct");
fi;
if ForAny(z,i -> i = Zero(F)) then
Error("<z> must be nonzero");
fi;
H := [];
for i in List([1..s], index -> List([1..t], vert -> List([1..n],
hor -> z[hor]/(a[hor] - w[index])^vert))) do
Append(H, i);
od;
C := CheckMatCode( BaseMat(VerticalConversionFieldMat(H)),
"generalized Srivastava code", GF(Characteristic(F)) );
C!.lowerBoundMinimumDistance := s + 1;
return C;
end);
InstallOtherMethod(GeneralizedSrivastavaCode, "a,w,z,t,q", true,
[IsList, IsList, IsList, IsInt, IsInt], 0,
function(a, w, z, t, q)
return GeneralizedSrivastavaCode(a, w, z, t, GF(q));
end);
InstallOtherMethod(GeneralizedSrivastavaCode, "a,w,z,t", true,
[IsList, IsList, IsList, IsInt], 0,
function(a, w, z, t)
return GeneralizedSrivastavaCode(a, w, z, t,
DefaultField(Concatenation(a,w,z)));
end);
InstallOtherMethod(GeneralizedSrivastavaCode, "a,w,z,F", true,
[IsList, IsList, IsList, IsField], 0,
function(a, w, z, F)
return GeneralizedSrivastavaCode(a, w, z, 1, F);
end);
InstallOtherMethod(GeneralizedSrivastavaCode, "a, w, z", true,
[IsList, IsList, IsList], 0,
function(a, w, z)
return GeneralizedSrivastavaCode(a, w, z, 1,
DefaultField(Concatenation(a, w, z)));
end);
#############################################################################
##
#F SrivastavaCode( <a>, <w> [, <mu>] [, <F>] ) . . . . . . . Srivastava code
##
InstallMethod(SrivastavaCode, "a,w,mu,F", true,
[IsList,IsList,IsInt, IsField], 0,
function(a, w, mu, F)
local C, n, s, i, zero, TheMat;
a := VectorCodeword(Codeword(a, F));
w := VectorCodeword(Codeword(w, F));
n := Length(a);
s := Length(w);
if Length(Set(Concatenation(a,w))) <> n + s then
Error("the elements of <alpha> and w are not distinct");
fi;
zero := Zero(F);
for i in [1.. n] do
if a[i]^mu = zero then
Error("z[",i,"] = ",a[i],"^",mu," = ",zero);
fi;
od;
TheMat := List([1..s], j -> List([1..n], i -> a[i]^mu/(a[i] - w[j]) ));
C := CheckMatCode( BaseMat(VerticalConversionFieldMat(TheMat)),
"Srivastava code", GF(Characteristic(F)) );
C!.lowerBoundMinimumDistance := s + 1;
return C;
end);
InstallOtherMethod(SrivastavaCode, "a,w,mu,q", true,
[IsList,IsList,IsInt,IsInt], 0,
function(a, w, mu, q)
return SrivastavaCode(a, w, mu, GF(q));
end);
InstallOtherMethod(SrivastavaCode, "a,w,mu", true,
[IsList,IsList,IsInt], 0,
function(a, w, mu)
return SrivastavaCode(a, w, mu, DefaultField(Concatenation(a,w)));
end);
InstallOtherMethod(SrivastavaCode, "a,w,F", true,
[IsList,IsList,IsField], 0,
function(a, w, F)
return SrivastavaCode(a, w, 1, F);
end);
InstallOtherMethod(SrivastavaCode, "a,w", true, [IsList,IsList], 0,
function(a, w)
return SrivastavaCode(a, w, 1, DefaultField(Concatenation(a,w)));
end);
#############################################################################
##
#F ExtendedBinaryGolayCode( ) . . . . . . . . . extended binary Golay code
##
InstallMethod(ExtendedBinaryGolayCode, "only method", true, [], 0,
function()
local C;
C := ExtendedCode(BinaryGolayCode());
C!.name := "extended binary Golay code";
Unbind( C!.history );
SetIsCyclicCode(C, false);
SetIsPerfectCode(C, false);
SetIsSelfDualCode(C, true);
C!.boundsCoveringRadius := [ 4 ];
SetIsNormalCode(C, true);
SetWeightDistribution(C,
[1,0,0,0,0,0,0,0,759,0,0,0,2576,0,0,0,759,0,0,0,0,0,0,0,1]);
#SetAutomorphismGroup(C, M24);
C!.lowerBoundMinimumDistance := 8;
C!.upperBoundMinimumDistance := 8;
return C;
end);
#############################################################################
##
#F ExtendedTernaryGolayCode( ) . . . . . . . . . extended ternary Golay code
##
InstallMethod(ExtendedTernaryGolayCode, "only method", true, [], 0,
function()
local C;
C := ExtendedCode(TernaryGolayCode());
SetIsCyclicCode(C, false);
SetIsPerfectCode(C, false);
SetIsSelfDualCode(C, true);
C!.boundsCoveringRadius := [ 3 ];
SetIsNormalCode(C, true);
C!.name := "extended ternary Golay code";
Unbind( C!.history );
SetWeightDistribution(C, [1,0,0,0,0,0,264,0,0,440,0,0,24]);
#SetAutomorphismGroup(C, M12);
C!.lowerBoundMinimumDistance := 6;
C!.upperBoundMinimumDistance := 6;
return C;
end);
#############################################################################
##
#F BestKnownLinearCode( <n>, <k> [, <F>] ) . returns best known linear code
#F BestKnownLinearCode( <rec> )
##
## L describs how to create a code. L is a list with two elements:
## L[1] is a function and L[2] is a list of arguments for L[1].
## One or more of the arguments of L[2] may again be such descriptions and
## L[2] can be an empty list.
## The field .construction contains such a list or false if the code is not
## yet in the apropiatelibrary file (/tbl/codeq.g)
##
InstallMethod(BestKnownLinearCode, "method for bounds/construction record",
true, [IsRecord], 0,
function(bds)
local MakeCode, C;
# L describs how to create a code. L is a list with two elements:
# L[1] is a function and L[2] is a list of arguments for L[1].
# One or more of the arguments of L[2] may again be such descriptions and
# L[2] can be an empty list.
MakeCode := function(L)
#beware: this is the most beautiful function in GUAVA (according to J)
if IsList(L) and IsBound(L[1]) and IsFunction(L[1]) then
return CallFuncList( L[1], List( L[2], i -> MakeCode(i) ) );
else
return L;
fi;
end;
if not IsBound(bds.construction) then
bds := BoundsMinimumDistance(bds.n, bds.k, bds.q);
fi;
if bds.construction = false then
Print("Code not yet in library\n");
return fail;
else
C := MakeCode(bds.construction);
if LowerBoundMinimumDistance(C) > bds.lowerBound then
Print("New table entry found!\n");
fi;
C!.lowerBoundMinimumDistance := Maximum(bds.lowerBound,
LowerBoundMinimumDistance(C));
C!.upperBoundMinimumDistance := Minimum(bds.upperBound,
UpperBoundMinimumDistance(C));
return C;
fi;
end);
InstallOtherMethod(BestKnownLinearCode, "n, k, q", true,
[IsInt, IsInt, IsInt], 0,
function(n, k, q)
local r;
r := BoundsMinimumDistance(n, k, q);
return BestKnownLinearCode(r);
end);
InstallOtherMethod(BestKnownLinearCode, "n, k, F", true,
[IsInt, IsInt, IsField], 0,
function(n, k, F)
local r;
r := BoundsMinimumDistance(n, k, Size(F));
return BestKnownLinearCode(r);
end);
InstallOtherMethod(BestKnownLinearCode, "n, k", true,
[IsInt, IsInt], 0,
function(n, k)
local r;
r := BoundsMinimumDistance(n, k);
return BestKnownLinearCode(r);
end);
## Helper functions for cyclic code creation
GeneratorMatrixFromPoly := function(p,n)
local coeffs, j, res, r, zero;
coeffs := CoefficientsOfLaurentPolynomial(p);
coeffs := ShiftedCoeffs(coeffs[1], coeffs[2]);
r := DegreeOfLaurentPolynomial(p);
zero := Zero(Field(coeffs));
res := [];
res[1] := [];
# first row
Append(res[1], coeffs);
Append(res[1], List([r+2..n], i->zero));
# 2..last-1
if n-r > 2 then
for j in [2..(n-r-1)] do
res[j] := [];
Append(res[j], List([1..j-1], i->zero));
Append(res[j], coeffs);
Append(res[j], List([r+1+j..n], i->zero));
od;
fi;
# last row
if n-r > 1 then
res[n-r] := [];
Append(res[n-r], List([1..n-r-1], i->zero));
Append(res[n-r], coeffs);
fi;
return res;
end;
CyclicCodeByGenerator := function(F, n, G)
local C, GM;
## for now, using linear code representation.
## Get generator matrix and call linear code creation function
## Note input is a codeword, for consistency.
## Further note GenMatFromPoly doesn't handle NullPoly case well,
## so calling NullMat instead. Once using poly rep, this should be
## unnecessary.
## And GMFP doesn't handle p = x^n-1 case.
if (G = NullWord(n,F)) or
(VectorCodeword(G) = []) or
(G = Codeword(Indeterminate(F)^n-One(F), F)) then
GM := NullMat(1,n,F);
else
GM := GeneratorMatrixFromPoly(PolyCodeword(G), n);
fi;
C := LinearCodeByGenerators(F, Codeword(One(F)*GM, F));
#C := LinearCodeByGenerators(F, One(F)*GM);
SetGeneratorMat(C, GM);
SetIsCyclicCode(C, true);
SetSpecialDecoder(C, CyclicDecoder);
return C;
end;
#############################################################################
##
#F GeneratorPolCode( <G>, <n> [, <name> ], <F> ) . code from generator poly
##
InstallMethod(GeneratorPolCode, "Poly, wordlength,name,field", true,
[IsUnivariatePolynomial, IsInt, IsString, IsField], 0,
function(G, n, name, F)
local R;
#G := PolyCodeword( Codeword(G, F) );
if not IsZero(G) then
G := Gcd(G,(Indeterminate(F)^n-One(F)));
fi;
R := CyclicCodeByGenerator(F, n, Codeword(G, F));
SetGeneratorPol(R, G);
R!.name := name;
return R;
end);
InstallOtherMethod(GeneratorPolCode, "Poly,wordlength,field", true,
[IsUnivariatePolynomial, IsInt, IsField], 0,
function(G, n, F)
return GeneratorPolCode(G,n,"code defined by generator polynomial", F);
end);
InstallOtherMethod(GeneratorPolCode, "Poly,wordlength,name,fieldsize", true,
[IsUnivariatePolynomial, IsInt, IsString, IsInt], 0,
function(G, n, name, q)
return GeneratorPolCode(G, n, name, GF(q));
end);
InstallOtherMethod(GeneratorPolCode, "Poly, wordlength, fieldsize", true,
[IsUnivariatePolynomial, IsInt, IsInt], 0,
function(G, n, q)
return GeneratorPolCode(G, n, "code defined by generator polynomial",
GF(q));
end);
#############################################################################
##
#F CheckPolCode( <H>, <n> [, <name> ], <F> ) . . code from check polynomial
##
InstallMethod(CheckPolCode, "check poly, wordlength, name, field", true,
[IsUnivariatePolynomial, IsInt, IsString, IsField], 0,
function(H, n, name, F)
local R,G;
H := PolyCodeword( Codeword(H, F) );
H := Gcd(H, (Indeterminate(F)^n-One(F)));
# Get generator pol
G := EuclideanQuotient((Indeterminate(F)^n-One(F)), H);
R := CyclicCodeByGenerator(F, n, Codeword(G,F));
SetCheckPol(R, H);
SetGeneratorPol(R, G);
R!.name := name;
return R;
end);
InstallOtherMethod(CheckPolCode, "check poly, wordlength, field", true,
[IsUnivariatePolynomial, IsInt, IsField], 0,
function(H, n, F)
return CheckPolCode(H, n, "code defined by check polynomial", F);
end);
InstallOtherMethod(CheckPolCode, "check poly, wordlength, name, fieldsize",
true, [IsUnivariatePolynomial, IsInt, IsString, IsInt], 0,
function(H, n, name, q)
return CheckPolCode(H, n, name, GF(q));
end);
InstallOtherMethod(CheckPolCode, "check poly, wordlength, fieldsize", true,
[IsUnivariatePolynomial, IsInt, IsInt], 0,
function(H, n, q)
return CheckPolCode(H, n, "code defined by check polynomial", GF(q));
end);
#############################################################################
##
#F RepetitionCode( <n> [, <F>] ) . . . . . . . repetition code of length <n>
##
InstallMethod( RepetitionCode, "wordlength, Field", true, [IsInt, IsField], 0,
function(n, F)
local C, q, wd, p;
q :=Size(F);
p := LaurentPolynomialByCoefficients( ElementsFamily(FamilyObj(F)),
List([1..n], t->One(F)), 0);
C := GeneratorPolCode(p, n, "repetition code", F);
C!.lowerBoundMinimumDistance := n;
C!.upperBoundMinimumDistance := n;
if n = 2 and q = 2 then
SetIsSelfDualCode(C, true);
else
SetIsSelfDualCode(C, false);
fi;
wd := NullVector(n+1);
wd[1] := 1;
wd[n+1] := q-1;
SetWeightDistribution(C, wd);
if n < 260 then
SetAutomorphismGroup(C, SymmetricGroup(n));
fi;
if F = GF(2) then
SetIsNormalCode(C, true);
fi;
if (n mod 2 = 0) or (F <> GF(2)) then
SetIsPerfectCode(C, false);
C!.boundsCoveringRadius := [ Minimum(n-1,QuoInt((q-1)*n,q)) ];
else
C!.boundsCoveringRadius := [ QuoInt(n,2) ];
SetIsPerfectCode(C, true);
fi;
return C;
end);
InstallOtherMethod(RepetitionCode, "wordlength, fieldsize", true,
[IsInt, IsInt], 0,
function(n, q)
return RepetitionCode(n, GF(q));
end);
InstallOtherMethod(RepetitionCode, "wordlength", true, [IsInt], 0,
function(n)
return RepetitionCode(n, GF(2));
end);
#############################################################################
##
#F WholeSpaceCode( <n> [, <F>] ) . . . . . . . . . . returns <F>^<n> as code
##
InstallMethod(WholeSpaceCode, "wordlength, Field", true, [IsInt, IsField], 0,
function(n, F)
local C, index, q;
C := GeneratorPolCode( Indeterminate(F)^0, n, "whole space code", F);
C!.lowerBoundMinimumDistance := 1;
C!.upperBoundMinimumDistance := 1;
SetAutomorphismGroup(C, SymmetricGroup(n));
C!.boundsCoveringRadius := [ 0 ];
if F = GF(2) then
SetIsNormalCode(C, true);
fi;
SetIsPerfectCode(C, true);
SetIsSelfDualCode(C, false);
q := Size(F) - 1;
SetWeightDistribution(C, List([0..n], i-> q^i*Binomial(n, i)) );
return C;
end);
InstallOtherMethod(WholeSpaceCode, "wordlength, fieldsize", true,
[IsInt, IsInt], 0,
function(n, q)
return WholeSpaceCode(n, GF(q));
end);
InstallOtherMethod(WholeSpaceCode, "wordlength", true, [IsInt], 0,
function(n)
return WholeSpaceCode(n, GF(2));
end);
#############################################################################
##
#F CyclicCodes( <n> ) . . returns a list of all cyclic codes of length <n>
##
InstallMethod(CyclicCodes, "wordlength, Field", true,
[IsInt, IsField], 0,
function(n, F)
local f, Pl;
f := Factors(Indeterminate(F) ^ n - One(F));
Pl := List(Combinations(f), c->Product(c)*Indeterminate(F)^0);
return List(Pl, p->GeneratorPolCode(p, n, "enumerated code", F));
end);
InstallOtherMethod(CyclicCodes, "wordlength, k, Field", true,
[IsInt, IsInt, IsField], 0,
function(n, k, F)
local r, f, Pl, codes;
r := n - k;
f := Factors(Indeterminate(F)^n-One(F));
Pl := [];
codes := function(f, g)
local i, tempf;
if Degree(g) < r then
i := 1;
while i <= Length(f) and Degree(g)+Degree(f[i][1]) <= r do
if f[i][2] = 1 then
tempf := f{[ i+1 .. Length(f) ]};
else
tempf := ShallowCopy( f );
tempf[i][2] := f[i][2] - 1;
fi;
codes( tempf, g * f[i][1] );
i := i + 1;
od;
elif Degree(g) = r then
Add( Pl, g );
fi;
end;
codes( Collected( f ), Indeterminate(F)^0 );
return List(Pl, p->GeneratorPolCode(p,n,"enumerated code",F));
end);
InstallOtherMethod(CyclicCodes, "wordlength, fieldsize", true,
[IsInt, IsInt], 0,
function(n, q)
return CyclicCodes(n, GF(q));
end);
InstallOtherMethod(CyclicCodes, "wordlength, k, fieldsize", true,
[IsInt, IsInt, IsInt], 0,
function(n, k, q)
return CyclicCodes(n, k, GF(q));
end);
#############################################################################
##
#F NrCyclicCodes( <n>, <F>) . . . number of cyclic codes of length <n>
##
InstallMethod(NrCyclicCodes, "wordlength, Field", true, [IsInt, IsField], 0,
function(n, F)
return NrCombinations(Factors(Indeterminate(F)^n-One(F)));
end);
InstallOtherMethod(NrCyclicCodes, "wordlength, fieldsize", true,
[IsInt, IsInt], 0,
function(n, q)
return NrCyclicCodes(n, GF(q));
end);
#############################################################################
##
#F BCHCode( <n> [, <b>], <delta> [, <F>] ) . . . . . . . . . . . . BCH code
##
## BCHCode (n [, b ], delta [, F]) returns the BCH code over F with
## wordlength n, designedDistance delta, constructed from powers
## x^b, x^(b+1), ..., x^(b+delta-2), where x is a primitive n'th power root
## of unity; b = 1 by default; the function returns a narrow sense BCH code
## Gcd(n,q) = 1 and 2<=delta<=n-b+1
InstallMethod(BCHCode, "wordlength, start, designed distance, fieldsize", true,
[IsInt, IsInt, IsInt, IsInt], 0,
function(n, start, del, q)
local stop, m, b, C, test, Cyclo, PowerSet, t,
zero, desdist, G, superfl, i, BCHTable;
BCHTable := [ [31,11,11], [63,36,11], [63,30,13], [127,92,11],
[127,85,13], [255,223,9], [255,215,11], [255,207,13],
[255,187,19], [255,171,23], [255,155,27], [255,99,47],
[255,79,55], [255,29,95], [255,21,111] ];
########### increase size of table? - wdj
stop := start + del - 2;
if Gcd(n,q) <> 1 then
Error ("n and q must be relative primes");
fi;
zero := Zero(GF(q));
m := OrderMod(q,n);
b := PrimitiveUnityRoot(q,n);
PowerSet := [start..stop];
G := Indeterminate(GF(q))^0;
while Length(PowerSet) > 0 do
test := PowerSet[1] mod n; ############### changed 8-1-2004
G := G * MinimalPolynomial(GF(q), b^test);
t := (q*test) mod n;
while t <> (test mod n) do ############### changed 7-31-2004
RemoveSet(PowerSet, t);
t := (q*t) mod n;
od;
RemoveSet(PowerSet, test);
od;
######################################
###### This loop computes the product of the
###### min polys of the elements when it should only
###### compute the lcm of them
###### Why not use cyclotomic codests and roots of code?
######################################
C := GeneratorPolCode(G, n, GF(q));
########### this removes extra powers by taking the gcd with x^n-1
SetSpecialDecoder(C, BCHDecoder);
########### this overwrites SetSpecialDecoder(C, CyclicDecoder);
# Calculate Bose distance:
Cyclo := CyclotomicCosets(q,n);
######## why not do this in the above loop?
PowerSet := [];
for t in [start..stop] do
for test in [1..Length(Cyclo)] do
if (t mod n) in Cyclo[test] then ##### added 8-1-2004
AddSet(PowerSet, Cyclo[test]);
fi;
od;
od;
PowerSet := Flat(PowerSet);
while stop + 1 in PowerSet do
stop := stop + 1;
od;
while start - 1 in PowerSet do
start := start - 1;
od;
desdist := stop - start + 2;
if desdist > n then
Error("invalid designed distance");
fi;
# In some cases the true minimumdistance is known:
SetDesignedDistance(C, desdist);
C!.lowerBoundMinimumDistance := desdist;
if (q=2) and (n mod desdist = 0) and (start = 1) then
C!.upperBoundMinimumDistance := desdist;
elif q=2 and desdist mod 2 = 0 and (n=2^m - 1) and (start=1) and
(Sum(List([0..QuoInt(desdist-1, 2) + 1], i -> Binomial(n, i))) >
(n + 1) ^ QuoInt(desdist-1, 2)) then
C!.upperBoundMinimumDistance := desdist;
elif (n = q^m - 1) and (desdist = q^OrderMod(q,desdist) - 1)
and (start=1) then
C!.upperBoundMinimumDistance := desdist;
fi;
# Look up this code in the table
########## table only for q=2^r, add this to if statement
########## to speed this up ?? - wdj
if start=1 then
for i in BCHTable do
if i[1] = n and i[2] = Dimension(C) then
C!.lowerBoundMinimumDistance := i[3];
C!.upperBoundMinimumDistance := i[3];
fi;
od;
fi;
# Calculate minimum of q*desdist - 1 for primitive n.s. BCH code
if q^m - 1 = n and start = 1 then
PowerSet := [start..stop];
superfl := true;
i := PowerSet[Length(PowerSet)] * q mod n;
while superfl do
while i <> PowerSet[Length(PowerSet)] and not i in PowerSet do
i := i * q mod n;
od;
if i = PowerSet[Length(PowerSet)] then
superfl := false;
else
PowerSet := PowerSet{[1..Length(PowerSet)-1]};
i := PowerSet[Length(PowerSet)] * q mod n;
fi;
od;
C!.upperBoundMinimumDistance := Minimum(UpperBoundMinimumDistance(C),
q * (Length(PowerSet) + 1) - 1);
fi;
C!.name := Concatenation("BCH code, delta=",
String(desdist), ", b=", String(start));
return C;
end);
InstallOtherMethod(BCHCode, "wordlength, start, designed distance, Field",
true, [IsInt, IsInt, IsInt, IsField], 0,
function(n, b, del, F)
return BCHCode(n, b, del, Size(F));
end);
InstallOtherMethod(BCHCode, "wordlength, designed distance", true,
[IsInt, IsInt], 0,
function(n, del)
return BCHCode(n, 1, del, 2);
end);
InstallOtherMethod(BCHCode, "wordlength, start, designed distance", true,
[IsInt, IsInt, IsInt], 0,
function(n, b, del)
return BCHCode(n, b, del, 2);
end);
InstallOtherMethod(BCHCode, "wordlength, designed distance, field", true,
[IsInt, IsInt, IsField], 0,
function(n, del, F)
return BCHCode(n, 1, del, Size(F));
end);
#############################################################################
##
#F ReedSolomonCode( <n>, <d> ) . . . . . . . . . . . . . . Reed-Solomon code
##
## ReedSolomonCode (n, d) returns a primitive narrow sense BCH code with
## wordlength n, over alphabet q = n+1, designed distance d
InstallMethod(ReedSolomonCode, "wordlength, designed distance", true,
[IsInt, IsInt], 0,
function(n, d)
local C,b,q,wd,w;
q := n+1;
if not IsPrimePowerInt(q) then
Error("q = n+1 must be a prime power");
fi;
b := Z(q);
C := GeneratorPolCode(Product([1..d-1], i-> (Indeterminate(GF(q))-b^i)), n,
"Reed-Solomon code", GF(q) );
SetRootsOfCode(C, List([1..d-1], i->b^i));
C!.lowerBoundMinimumDistance := d;
C!.upperBoundMinimumDistance := d;
SetDesignedDistance(C, d);
SetSpecialDecoder(C, BCHDecoder);
IsMDSCode(C); # Calculate weightDistribution field
return C;
end);
InstallMethod(ExtendedReedSolomonCode, "wordlength, designed distance", true,
[IsInt, IsInt], 0,
function(n, d)
local i, j, s, C, G, Ce;
C := ReedSolomonCode(n-1, d-1);
G := MutableCopyMatrix( GeneratorMat(C) );
TriangulizeMat(G);
for i in [1..Size(G)] do;
s := 0;
for j in [1..Size(G[i])] do;
s := s + G[i][j];
od;
Append(G[i], [-s]);
od;
Ce := GeneratorMatCodeNC(G, LeftActingDomain(C));
Ce!.name := "extended Reed Solomon code";
Ce!.lowerBoundMinimumDistance := d;
Ce!.upperBoundMinimumDistance := d;
IsMDSCode(Ce);
return Ce;
end);
## RootsCode implementation expunged and rewritten for Guava 3.11
## J. E. Fields 1/15/2012 (with help from WDJ)
#############################################################################
##
#F RootsCode( <n>, <list>, <field> ) code constructed from roots of polynomial
##
## RootsCode (n, rootlist, F) or RootsCode (n, <powerlist>, fieldsize) or
## RootsCode(n, rootlist) returns the
## code with generator polynomial equal to the least common multiple of
## the minimal polynomials of the n'th roots of unity in the list.
## The code has wordlength n.
##
InstallMethod(RootsCode, "method for n, rootlist, field", true, [IsInt, IsList, IsField], 0,
function(n, L, F)
local g, C, num, power, p, q, z, i, j, rootslist, powerlist, max, cc, CC, CCz;
L := Set(L);
q := Size(Field(L));
z := Z(q);
g:=One(F);
if List(L, i->i^n) <> NullVector(Length(L), F) + z^0 then
Error("powers must all be n'th roots of unity");
fi;
p := Characteristic(Field(L));
CC:=CyclotomicCosets(p,q-1);
CCz:=List([1..Length(CC)],i->List(CC[i],j->z^j));
## this is the set of cyclotomic cosets, represented
## as powers of a primitive element z
powerlist := [];
for i in [1..Length(L)] do
for cc in CCz do
if L[i] in cc then
Append(powerlist,[cc]);
fi;
od;
od;
########### add a cyclotomic coset into powerlist
########### if there is an element of L in that coset
g:=Product([1..Length(powerlist)],i->MinimalPolynomial(F,powerlist[i][1]));
C:=GeneratorPolCode(g,n,"code defined by roots",F);
rootslist := [];
for cc in powerlist do
Append(rootslist, cc);
od;
rootslist := Set(rootslist);
SetRootsOfCode(C, rootslist);
# Find the largest number of successive powers for BCH bound
max := 1;
i := 1;
num := Length(powerlist);
for z in [2..num] do
if powerlist[z] <> powerlist[i] + z-i then
max := Maximum(max, z - i);
i := z;
fi;
od;
C!.lowerBoundMinimumDistance := Maximum(max, num+1 - i) + 1;
return C;
end);
InstallOtherMethod(RootsCode, "method for n, rootlist", true, [IsInt, IsList], 0,
function(n, L)
local p,q,z,L1,L2,F;
L1 := Set(L);
p := Characteristic(Field(L1));
z := Z(Size(Field(L1)));
F := GF(p);
#L2 := List([1..Length(L1)],i-> LogFFE(L[i],z));
#Print(L1, p, z, F, L2);
return RootsCode(n, L1, F);
end);
InstallOtherMethod(RootsCode, "method for n, powerlist, fieldsize", true, [IsInt, IsList, IsInt], 0,
function(n, P, q)
# , "method for n, powerlist, fieldsize", true, [IsInt, IsList, IsInt], 0,
local z, L;
z := PrimitiveUnityRoot(q,n);
L := Set(List(P, i->z^i));
return RootsCode(n, L, GF(q));
end);
#############################################################################
##
#F QRCode( <n> [, <F>] ) . . . . . . . . . . . . . . quadratic residue code
##
InstallMethod(QRCode, "modulus, fieldsize", true, [IsInt, IsInt], 0,
function(n, q)
local m, b, Q, N, t, g, lower, upper, C, F, coeffs;
if Jacobi(q,n) <> 1 then
Error("q must be a quadratic residue modulo n");
elif not IsPrimeInt(n) then
Error("n must be a prime");
elif not IsPrimeInt(q) then
Error("q must be a prime");
fi;
m := OrderMod(q,n);
F := GF(q^m);
b := PrimitiveUnityRoot(q,n);
Q := [];
N := [1..n];
for t in [1..n-1] do
AddSet(Q, t^2 mod n);
od;
for t in Q do
RemoveSet(N, t);
od;
g := Product(Q,
i -> LaurentPolynomialByCoefficients(ElementsFamily(FamilyObj(F)),
[-b^i, b^0], 0) );
coeffs := CoefficientsOfLaurentPolynomial(g);
coeffs := ShiftedCoeffs(coeffs[1], coeffs[2]);
C := GeneratorPolCode( LaurentPolynomialByCoefficients(
ElementsFamily(FamilyObj(GF(q))), coeffs, 0),
n, "quadratic residue code", GF(q) );
if RootInt(n)^2 = n then
lower := RootInt(n);
else
lower := RootInt(n)+1;
fi;
if n mod 4 = 3 then
while lower^2-lower+1 < n do
lower := lower + 1;
od;
fi;
if (n mod 8 = 7) and (q = 2) then
while lower mod 4 <> 3 do
lower := lower + 1;
od;
fi;
upper := Weight(Codeword(coeffs));
C!.lowerBoundMinimumDistance := lower;
C!.upperBoundMinimumDistance := upper;
return C;
end);
InstallOtherMethod(QRCode, "modulus, field", true, [IsInt, IsField], 0,
function(n, F)
return QRCode(n, Size(F));
end);
InstallOtherMethod(QRCode, "modulus", true, [IsInt], 0,
function(n)
return QRCode(n, 2);
end);
#############################################################################
##
#F QQRCode( <n> [, <F>] ) . . . . . . . . binary quasi-quadratic residue code
##
## Code of Bazzi-Mittel (see Bazzi, L. and Mitter, S.K. "Some constructions of
## codes from group actions" preprint March 2003 (submitted to IEEE IT)
##
InstallMethod(QQRCode, "Modulus", true, [IsInt], 0,
function(p)
local G0,G,Q,N,QN,i,C,F,QuadraticResidueSupports,NonQuadraticResidueSupports;
# start local functions:
QuadraticResidueSupports:=function(p)
local L,i;
L:=List([1..(p-1)],i->1+Legendre(i,p))/2;
return L;
end;
NonQuadraticResidueSupports:=function(p)
local L,i;
L:=List([1..(p-1)],i->1-Legendre(i,p))/2;
return L;
end;
# end local functions
F:=GF(2);
Q:=[Zero(F)];
Q:=One(F)*Concatenation(Q,QuadraticResidueSupports(p));
N:=[Zero(F)];
N:=One(F)*Concatenation(N,NonQuadraticResidueSupports(p));
QN:=Concatenation(Q,N);
G:=BlockMatrix([[1,1,CirculantMatrix(p,Q)],[1,2,CirculantMatrix(p,N)]],1,2);
if p mod 4 = 1 then
G0:=List([1..(p-1)],i->G[i]);
else
G0:=MatrixByBlockMatrix(G);
fi;
C:=GeneratorMatCode(G0,F);
C!.DoublyCirculant:=G0;
C!.GeneratorMat:=G0;
return C;
end);
#############################################################################
##
#F QQRCodeNC( <n> [, <F>] ) . . . . . . . . binary quasi-quadratic residue code
##
## Code of Bazzi-Mittel (see Bazzi, L. and Mitter, S.K. "Some constructions of
## codes from group actions" preprint March 2003 (submitted to IEEE IT)
##
InstallMethod(QQRCodeNC, "Modulus", true, [IsInt], 0,
function(p)
local G,G0,Q,N,QN,i,C,F,QuadraticResidueSupports,NonQuadraticResidueSupports;
# start local functions:
QuadraticResidueSupports:=function(p)
local L,i;
L:=List([1..(p-1)],i->1+Legendre(i,p))/2;
return L;
end;
NonQuadraticResidueSupports:=function(p)
local L,i;
L:=List([1..(p-1)],i->1-Legendre(i,p))/2;
--> --------------------
--> maximum size reached
--> --------------------
[ zur Elbe Produktseite wechseln0.56Quellennavigators
Analyse erneut starten
]
|
