// Example code from paper 13:
// _Searching for linear codes with large minimum distance_, by Markus Grassl
//
print "Examples from: Searching for linear codes with large minimum distance";
Attach("Paper13.m");
ei := GetEchoInput();
SetEchoInput(true);
// Section 2: Computing the minimum weight
// Subsection 2.1: General linear codes
SetVerbose("Code", 1);
c := BKLC(GF(2), 77, 15);
ResetMinimumWeightBounds(c);
MinimumWeight(c);
perm := Sym(77)!(1,64,4,66,36,59,65,73,12,18,31,45,57,17)
 (2,55,68,42,56,24,39,47,54,33,30,8,60,40,71,21,58,16,46,61,50,
  26,9,27,28,43,67,69,75,38,19,76,35,25,6,74,13,53,3,29,14,20,
  10,37,77,32,63,15,5)(7,23,22,52,11,44,49,62,70,48,72,34,51);
c2 := c^perm;
ResetMinimumWeightBounds(c2);
MinimumWeight(c2);
WorkFactor(GF(2), 77, 15, 29, [ 15, 15, 15, 15, 11, 6 ]);
WorkFactor(GF(2), 77, 15, 29, [ 15, 15, 15, 15, 15, 2 ]);

// Subsection 2.2: Cyclic codes
WorkFactor(GF(4), 85, 16, 44, [ 16, 16, 16, 16, 16, 5 ]);
CyclicWorkFactor(GF(4), 85, 16, 44);
c := BKLC(GF(4), 85, 16);
ResetMinimumWeightBounds(c);
MinimumWeight(c);

// Subsection 2.3: The MacWilliams transform
c := BKLC(GF(4), 100, 90);
ResetMinimumWeightBounds(c);
new_MinimumWeight(c);
SetVerbose("Code", 0);
c := BKLC(GF(4), 100, 90);
ResetMinimumWeightBounds(c);
time MinimumWeight(c);
ResetMinimumWeightBounds(c);
time new_MinimumWeight(c);

// Section 4: Searching for good codes
// Subsection 4.1: Cyclic codes
cand := AllCyclicCodes(GF(3), 73);
time exists(c){ c : c in cand | Dimension(c) eq 25
                      and VerifyMinimumWeightLowerBound(c, 24) };
F<a> := GF(4);
g := PolynomialRing(F) ! [1,1,1,a,a,0,a^2,a,a,1,0,0,1,1,0,1,1,a,a^2,
      a^2,a^2,a^2,a,a,1,a^2,1,a,0,0,0,a^2,a,1,0,a,1,a,0,a^2,1,1,1];
c := CyclicCode(85, g);
// This next line takes 8+ days on a 64-bit 2.6GHz AMD processor
MinimumWeight(c);

// Subsection 4.2: Other techniques
P<x> := PolynomialRing(GF(9));
w := Roots(x^2 - x - 1)[1,1];
g := x^7 + w*x^6 + w^6*x^5 + w^3*x^4 + w^7*x^3 + w^2*x^2 + w^5*x + 2;
C_146_132_6 := ConcatenatedCode(
      CyclicCode(73, g), UniverseCode(GF(3), 2));
time MinimumWeight(C_146_132_6);
ResetMinimumWeightBounds(C_146_132_6);
time new_MinimumWeight(C_146_132_6);
C_146_134_4 := ConcatenatedCode(
      CyclicCode(73, g div (x-1)), UniverseCode(GF(3), 2));
subcodes := { sub< C_146_134_4 | C_146_132_6, x > :
   x in CodeComplement(C_146_134_4, C_146_132_6) | x ne 0 };
L_d := { MinimumWeight(c) : c in subcodes };
subcodes : Minimal;
subcodes := [ c : c in subcodes | MinimumWeight(c) eq 5 ];
C2 := subcodes[1];
C3 := subcodes[2];
C4 := UniverseCode(GF(3), 1);
C_148_134_6 := ConstructionXX(C_146_134_4, C2, C3, C4, C4);
new_MinimumWeight(C_148_134_6);
time CosetDistanceDistribution(C_148_134_6);
cc := CodeComplement(Generic(C_148_134_6), C_148_134_6);
repeat
  c1 := LinearCode< GF(3), 148 | C_148_134_6, Random(cc) >;
until c1 ne C_148_134_6 and VerifyMinimumWeightLowerBound(c1, 4);
C_150_135_6 := ConstructionX(c1, C_148_134_6, RepetitionCode(GF(3), 2));
c := C_150_135_6;
while CoveringRadius(c) ge 5 do
  cc := CodeComplement(Generic(c), c);
  time repeat
    c1 := LinearCode< GF(3), Length(c) | c, Random(cc) >;
  until c1 ne c and VerifyMinimumWeightLowerBound(c1, 5);
  c := ConstructionX(c1, c, UniverseCode(GF(3), 1));
end while;
SetEchoInput(ei);