|
The operations described here produce a new code by modifying
in some way the codewords of a given code.
Given an [n, k] binary code C, construct a new code
C' by including the all-ones vector with the words of C
(provided that it is not already in C).
Given a subcode C1 of C, return a code C2 such that C=C1 + C2.
Given an [n1, k1] code C and an [n2, k2] code
D, both over the same field F, construct the direct sum of
C and D. The direct sum consists of all vectors u|v, where
u ∈C and v ∈D.
Given a sequence of codes Q = [C1, ..., Cr], all defined
over the same field F, construct the direct sum of the Ci.
ProductCode(C, D) : Code, Code -> Code
Given an [n1, k1] code C and an [n2, k2] code
D, both over the same ring R, construct the direct product of
C and D. The direct product has length n1.n2, dimension
k1.k2, and its
generator matrix is the Kronecker product of the basis matrices
of C and D.
Given an [n, k, d] code C
form a new code C' from C by adding the appropriate extra coordinate
to each vector of C such that the sum of the coordinates of the extended
vector is zero. (Thus if C is a binary code, the construction will add
a 0 at the
end of every codeword having even weight, and a 1 at the end
of every codeword having odd weight.)
Return the code C extended n times.
Add n zeros to the end of each codeword of C.
Construct a new code by deleting
all the code words of C having odd weight.
The sequence L consists of codewords from C. The result is obtained by
deleting the words in L from C.
Delete a subspace generated by a word of weight w.
Given an [n, k] binary code C, construct a new code
by first adding the all-ones codeword, and then extending
it by adding an overall parity check.
Given two codes over the same alphabet, return the code consisting
of all vectors of the form u|u + v, where u ∈C1 and v ∈C2.
Zeros are appended where needed to make up any length differences
in the two codes.
The result is a [n1 + max{n1, n2}, k1 + k2, min{2 * d1, d2}] code.
a: FldFinElt Default: -1
Given three codes over the same alphabet, return the code consisting
of all vectors of the form u|u + a * v|u + v + w, where u ∈C1, v ∈C2
and w ∈C3.
Zeros are appended where needed to make up any length differences
in the three codes.
The result for the default case of a := -1 is a
[n1 + max{n1, n2} + max{n1, n2, n3}, k1 + k2 + k3,
min{3 * d1, 2 * d2, d3}] code.
Given an [n, k] code C, and an integer i,
1 ≤i ≤n, construct a new code C' by deleting
the i-th coordinate from each code word of C.
Given an [n, k] code C and a set S of distinct integers
{ i1, ..., ir } each of which lies in the range [1, n],
construct a new code C' by deleting the components
i1, ..., ir from each code word of C.
Given an [n, k] code C and an integer i,
1 ≤i ≤n, construct a new code from C by selecting
only those codewords of C having a zero as their i-th
component and deleting the i-th component from these
codewords. Thus, the resulting code will have length n - 1.
Given an [n, k] code C and a set S of distinct integers
{ i1, ..., ir}, each of which lies in the range [1, n],
construct a new code from C by selecting only those codewords
of C having zeros in each of the coordinate positions
i1, ..., ir, and deleting these components. Thus, the
resulting code will have length n - r.
Using only two simple RepetitionCode's and several standard
constructions, we create a [12, 4, 6] code. This is the best
possible minimum weight for a code of this length and dimension,
as is the minimum weight for all
codes produced in this example.
Instead of printing each individual code out,
the codes are named by convention as c_n_k_d, where
n, k, d represent the Length,Dimension and MinimumWeight
respectively.
> c_4_1_4 := RepetitionCode(GF(2),4);
> c_6_1_6 := RepetitionCode(GF(2),6);
> c_4_3_2 := Dual( c_4_1_4 );
> c_8_4_4 := PlotkinSum( c_4_3_2 , c_4_1_4 );
> c_7_4_3 := PunctureCode( c_8_4_4 , 8 );
> c_6_3_3 := ShortenCode( c_7_4_3 , 7 );
> c_12_4_6 := PlotkinSum( c_6_3_3 , c_6_1_6 );
> c_12_4_6;
[12, 4, 6] Linear Code over GF(2)
Generator matrix:
[1 0 0 1 1 0 0 1 1 0 0 1]
[0 1 0 1 0 1 0 1 0 1 0 1]
[0 0 1 1 1 1 0 0 1 1 1 1]
[0 0 0 0 0 0 1 1 1 1 1 1]
Given an [n, k, d] code C defined over the finite field K,
and an extension
field L of K, construct the code C' over L corresponding to C.
The function also returns the embedding map from C into C'.
Given an [n, k, d] code C defined over the finite field K, and a subfield
S of K such that the degree of K over S is m, construct a new
[N = mn, k, D ≥d] code C' over S by replacing each component of
each codeword of C by its representation as a vector over S.
The function also returns the isomorphism from C onto C'.
Given a linear code over GF(qm), return a code whose codewords are obtained
from those of C by expanding each coordinate in GF(qm) as a vector of
dimension m over K = GF(q).
Given a linear code over GF(qm), return a code whose codewords are
obtained from those of C by expanding each coordinate in GF(qm) as a
vector of dimension m + 1 over K = GF(q), including a parity check bit.
RestrictField(C, S) : Code, FldFin -> Code, Map
SubfieldSubcode(C) : Code -> Code, Map
RestrictField(C) : Code -> Code, Map
Given an [n, k, d] code C defined over the field K, and a subfield
S of K, construct a new [n, K ≤k, D ≥d] code C' over
S consisting of the codewords of C which have all their components
in S. If S is omitted, it is taken to be the prime subfield of K.
The function also returns the restriction map from C to the
subfield subcode C'.
Given an [n, k] code C defined over the field K, and a subfield
S of K, such that K is a degree m extension of S,
construct a new [n, k'] code over S by expanding each element of K
as a column vector over S. The new code will have k'≤km.
Trace(C) : Code -> Code
Given a code C defined over the field K, and a subfield
F of K, construct a new code C' over F consisting of
the traces with respect to F of each of the codewords of
L. If F is omitted, it is taken to be the prime subfield of K.
Given codes C1 and C2, both defined over the same field K,
return the concatenation C of C1 and C2. If A and B are the
generator matrices of C1 and C2, respectively, the concatenation
of C1 and C2 is the code with generator matrix whose rows consist
of each row of A concatenated with each row of B.
Given an [n1, k, d1] code C1 and an [n2, k, d2] code C2
of the same dimension, where both codes are defined over the same
field K, the function returns a [n1 + n2, k, ≥d1 + d2] code
whose generator matrix is HorizontalJoin(A, B), where A and B
are the generator matrices for codes C1 and C2, respectively.
Given a [N, K, D]-code O defined over GF(qk) and a [n, k, d]-code I
defined over GF(q), construct the [Nn, Kk, δ ≥dD] concatenated
code by taking O as outer code and I as inner code.
We use the function ConcatenatedCode to construct a [69, 19, 22]
code over GF(2), this being the best known code for this length and
dimension. While it is theoretically possible for a code of minimum
weight up to 24 to exist, the best binary [69, 19] code at the time
of writing (July 2001) has minimum weight 22.
> C1 := ShortenCode( QRCode(GF(4),29) , {24..29} );
> C1:Minimal;
[23, 9] Linear Code over GF(2^2)
> C2 := ConcatenatedCode( C1 , CordaroWagnerCode(3) );
> C2:Minimal;
[69, 18] Linear Code over GF(2)
> res := C2 + RepetitionCode(GF(2),69);
> res:Minimal;
[69, 19] Linear Code over GF(2)
> MinimumWeight(res);
22
> res:Minimal;
[69, 19, 22] Linear Code over GF(2)
Let C1, C2 and C3 be codes with parameters [n1, k1, d1],
[n2, k2, d2] and [n3, k3, d3], respectively, where C1 is
a union of b=2k3 cosets of C2, (so n1=n2 and k2 ≤k1) and
k1 = k2 + k3. The construction divides C1 into a union of cosets
of C2 and attaches a different codeword of C3 to each coset.
The new code has parameters [n1 + n3, k1, ≥min{ d2, d1 + d3 } ].
For further details see [MS78, p.581].
Given a sequence of codes S where all codes are subcodes of the first one,
apply ConstructionX to S[1], S[2] and C.
Then compute the resulting subcodes from the other codes in S.
We create a [161, 29, 53] code by applying construction X to two BCH
codes of length 127. To maximise the resulting minimum weight we take
the best known [34, 14] code as C 3. The construction sets a lower
bound on the minimum weight, making the calculation of the true
minimum weight much faster.
> SetPrintLevel("Minimal");
>
> C1 := BCHCode(GF(2), 127, 43);
> C2 := BCHCode(GF(2), 127, 55);
> C3 := BKLC(GF(2), 34, 14);
> C1; C2; C3;
[127, 29, 43] BCH code (d = 43, b = 1) over GF(2)
[127, 15, 55] BCH code (d = 55, b = 1) over GF(2)
[34, 14, 10] Linear Code over GF(2)
> CX := ConstructionX(C1, C2, C3);
> CX;
[161, 29] Linear Code over GF(2)
> time MinimumWeight(CX);
53
Time: 0.010
Given a chain of codes C1=[n, k1, d1], C2=[n, k2, d2],
and C3=[n, k3, d3] with
k3 < k2 < k1, and suffix codes D1=[n1, k1 - k2, e1] and
D2=[n2, k3 - k2, e2],
construct a code C=[n + n1 + n2, k1, ≥min{d3, d1 + e1, d2 + e2}.
For further details see [MS78, p.583].
Given two chains of codes C1=[n, k1] ⊂C2=[n, k2] ⊂C3=[n, k3]
and D1=[n', k1 - k3] ⊂D2=[n', k2 - k3],
return the codes C=[n + n', k1] ⊂C'=[n + n', k2] using Construction X
with C1, C3 and D1 resp. C2, C3 and D2.
We construct a best known [74, 43, 11] code using
construction X3. From a chain of BCH subcodes, we take an
subcode to get the appropriate length, then use
construction X3 with the best possible codes D 1, D 2.
Because the construction algorithm sets a lower bound on
the minimum weight, then it is quick to calculate afterwards.
> SetPrintLevel("Minimal");
> C1 := ExtendCode( BCHCode(GF(2), 63, 7) );
> C2 := ExtendCode( BCHCode(GF(2), 63, 9) );
> C3 := ExtendCode( BCHCode(GF(2), 63, 11) );
> C1; C2; C3;
[64, 45, 8] Linear Code over GF(2)
[64, 39, 10] Linear Code over GF(2)
[64, 36, 12] Linear Code over GF(2)
> CC := SubcodeBetweenCode(C1, C2, 43);
> CC;
[64, 43] Linear Code over GF(2)
> MinimumWeight(CC);
8
> CX3 := ConstructionX3(CC, C2, C3,
> BKLC(GF(2), 7, 4), BKLC(GF(2), 3, 3));
> CX3;
[74, 43] Linear Code over GF(2)
> time MinimumWeight(CX3);
11
Time: 0.000
Let the parameters of codes C1, C2, C3 be
[n1, k, d1], [n1, k - l2, d2] and [n1, k - l3, d3] respectively,
where C2 and C3 are subcodes of C1. Codes D2, D3 must have
dimensions l2, l3, with parameters [n2, l2, δ2], [n3, l3, δ3]
say.
The construction breaks C1 up into cosets of C2 and C3 with
the relevant tails added from D2 and D3. If the intersection of
C1 and C2 has minimum distance d0 then the newly constructed
code will have parameters
[n1 + n2 + n3, k, min{d0, d2 + δ2, d3 + δ3, d1 + δ2 + δ3}].
For further details see [All84].
We construct a best known [73, 38, 13] code C using construction XX.
For C 1, C 2, C 3 we take three cyclic (or BCH) codes of
length 63, while for D 1, D 2 we use two Best Known Codes.
> SetPrintLevel("Minimal");
> C1 := BCHCode(GF(2),63,10,57);
> P<x> := PolynomialRing(GF(2));
> p := x^28 + x^25 + x^22 + x^21 + x^20 + x^17 + x^16
> + x^15 + x^9 + x^8 + x^6 + x^5 + x + 1;
> C2 := CyclicCode(63, p);
> C3 := BCHCode(GF(2), 63, 10, 58);
> C1; C2; C3;
[63, 38] BCH code (d = 10, b = 57) over GF(2)
[63, 35] Cyclic Code over GF(2)
[63, 32] BCH code (d = 10, b = 58) over GF(2)
> MinimumDistance(C1 meet C2);
12
So the minimum distance of the code produced by Construction XX must be at
least 12.
> C := ConstructionXX(C1, C2, C3, BKLC(GF(2),3,3), BKLC(GF(2),7,6) );
> C;
[73, 38] Linear Code over GF(2)
> MinimumDistance(C);
13
Thus the actual minimum distance is one greater than the lower bound
guaranteed by Construction XX.
The arguments are as follows: The first argument must be a sequence I
containing an increasing chain of r codes with parameters,
[n, k1, d1]q ⊂[n, k2, d2]q ⊂ ... ⊂[n, kr, dr]q
where 0=k0<k1<k2< ... < kr, (the inner codes). The second argument
must be a sequence O of r codes with parameters [N, Ki, Di]Qi,
where Qi = qei and ei = ki - ki - 1 for i = 1 ... r
(the outer codes). The function constructs a generalised concatenated
[n * N, K, D]q code is constructed, where K=e1K1 + ... + erKr and
D = min(d1D1, ... , drDr). For further details see [MS78, p.590].
We create a [72, 41, 12] code over GF(2) using the ZinovievCode
function, which is the best known code for this length and dimension.
While it is theoretically possible for a [72, 41] code to have minimum
weight up to 14, at the time of writing (July 2001) the best known
code has minimum weight 12.
The minimum weight is not calculated since it is a lengthy calculation.
> I1 := RepetitionCode(GF(2),8);
> I2 := I1 + LinearCode( KMatrixSpace(GF(2),3,8) !
> [0,1,0,0,0,1,1,1,0,0,1,0,1,0,1,1,0,0,0,1,1,1,0,1]
> );
> I3 := Dual(I1);
> Inner := [I1, I2, I3];
> Inner:Minimal;
[
[8, 1, 8] Cyclic Code over GF(2),
[8, 4, 4] Linear Code over GF(2),
[8, 7, 2] Cyclic Code over GF(2)
]
>
> O1 := Dual(RepetitionCode(GF(2),9));
> O2 := BCHCode(GF(8),9,3,4);
> O3 := BCHCode(GF(8),9,6,7);
> Outer := [O1, O2, O3];
> Outer:Minimal;
[
[9, 8, 2] Cyclic Code over GF(2),
[9, 7, 3] BCH code (d = 3, b = 4) over GF(2^3),
[9, 4, 6] BCH code (d = 6, b = 7) over GF(2^3)
]
>
> C := ZinovievCode(Inner, Outer);
> C:Minimal;
[72, 41] Linear Code over GF(2)
Apply construction Y1 to the code C. This construction applies the
shortening operation at the positions in the support of a word of minimal
weight in the dual of C. If C is a [n, k, d] code, whose dual code
has minimum weight d', then the returned code has parameters
[n - d', k - d' + 1, ≥d]. For further details see [MS78, p.592].
Apply construction Y1 to the code C. This construction applies the
shortening operation at the positions in the support of a word of
weight w in the dual of C. If C is a [n, k, d] code,
then the returned code has parameters [n - w, k - w + 1, ≥d].
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|