New Codes from Existing

The operations described here produce a new code by modifying in some way the codewords of a given code.

Standard Constructions

AugmentCode(C): Code -> 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\)).

CodeComplement(C, C1): Code, Code -> Code

Given a subcode \(C_1\) of \(C\), return a code \(C_2\) such that \(C=C_1 + C_2\).

DirectSum(C, D): Code, Code -> Code

Given an \([n_1, k_1]\) code \(C\) and an \([n_2, k_2]\) 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 \in C\) and \(v \in D\).

DirectSum(Q): [Code] -> Code

Given a sequence of codes \(Q = [C_1, \dots, C_r]\), all defined over the same field \(F\), construct the direct sum of the \(C_i\).

DirectProduct(C, D): Code, Code -> Code

ProductCode(C, D): Code, Code -> Code

Given an \([n_1, k_1]\) code \(C\) and an \([n_2, k_2]\) code \(D\), both over the same ring \(R\), construct the direct product of \(C\) and \(D\). The direct product has length \(n_1\cdot n_2\), dimension \(k_1\cdot k_2\), and its generator matrix is the Kronecker product of the basis matrices of \(C\) and \(D\).

ExtendCode(C): Code -> Code

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.)

ExtendCode(C, n): Code, RngIntElt -> Code

Return the code \(C\) extended \(n\) times.

PadCode(C, n): Code, RngIntElt -> Code

Add \(n\) zeros to the end of each codeword of \(C\).

ExpurgateCode(C): Code -> Code

Construct a new code by deleting all the code words of \(C\) having odd weight.

ExpurgateCode(C, L): Code, [ModTupFldElt] -> Code

The sequence \(L\) consists of codewords from \(C\). The result is obtained by deleting the words in \(L\) from \(C\).

ExpurgateWeightCode(C, w): Code, RngIntElt -> Code

Delete a subspace generated by a word of weight \(w\).

LengthenCode(C): Code -> Code

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.

PlotkinSum(C1, C2): Code, Code -> Code

Given two codes over the same alphabet, return the code consisting of all vectors of the form \(u|u+v\), where \(u \in C_1\) and \(v \in C_2\). Zeros are appended where needed to make up any length differences in the two codes. The result is a \([n_1 + \max\{n_1,n_2\},k_1 + k_2, \min\{2*d_1,d_2\}]\) code.

PlotkinSum(C1, C2, C3: parameters): Code, Code, Code -> 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 \in C_1\), \(v \in C_2\) and \(w \in C_3\). 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 \([n_1 + \max\{n_1,n_2\} + \max\{n_1,n_2,n_3\},k_1 + k_2+k_3, \min\{3*d_1,2*d_2,d_3\}]\) code.

PunctureCode(C, i): Code, RngIntElt -> Code

Given an \([n, k]\) code \(C\), and an integer \(i\), \(1 \leq i \leq n\), construct a new code \(C'\) by deleting the \(i\)-th coordinate from each code word of \(C\).

PunctureCode(C, S): Code, { RngIntElt } -> Code

Given an \([n, k]\) code \(C\) and a set \(S\) of distinct integers \(\{ i_1, \cdots, {\mathrm{i}}_r \}\) each of which lies in the range \([1, n]\), construct a new code \(C'\) by deleting the components \(i_1, \cdots, i_r\) from each code word of \(C\).

ShortenCode(C, i): Code, RngIntElt -> Code

Given an \([n, k]\) code \(C\) and an integer \(i\), \(1 \leq i \leq 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\).

ShortenCode(C, S): Code, { RngIntElt } -> Code

Given an \([n, k]\) code \(C\) and a set \(S\) of distinct integers \(\{ i_1, \cdots, {\mathrm{i}}_r\}\), 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 \(i_1, \cdots, i_r\), and deleting these components. Thus, the resulting code will have length \(n-r\).

Example: Make12 8 4Code (ex-7b4c39)

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]

Run in calculatorCopy input

Changing the Alphabet of a Code

ExtendField(C, L): Code, FldFin -> Code, Map

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'\).

LinearCode(C, S): Code, FldFin -> Code, Map

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 \geq 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'\).

SubfieldRepresentationCode(C, K): Code, FldFin -> Code

Given a linear code over \(GF(q^m)\), return a code whose codewords are obtained from those of \(C\) by expanding each coordinate in \(GF(q^m)\) as a vector of dimension \(m\) over \(K = GF(q)\).

SubfieldRepresentationParityCode(C, K): Code, FldFin -> Code

Given a linear code over \(GF(q^m)\), return a code whose codewords are obtained from those of \(C\) by expanding each coordinate in \(GF(q^m)\) as a vector of dimension \(m+1\) over \(K = GF(q)\), including a parity check bit.

SubfieldSubcode(C, S): Code, FldFin -> Code, Map

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 \leq k, D \geq 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'\).

SubfieldCode(C, S): Code, FldFin -> Code

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'\le km\).

Trace(C, F): Code, FldFin -> Code

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\).

Combining Codes

C1 cat C2: Code, Code -> Code

Given codes \(C_1\) and \(C_2\), both defined over the same field \(K\), return the concatenation \(C\) of \(C_1\) and \(C_2\). If \(A\) and \(B\) are the generator matrices of \(C_1\) and \(C_2\), respectively, the concatenation of \(C_1\) and \(C_2\) is the code with generator matrix whose rows consist of each row of \(A\) concatenated with each row of \(B\).

Juxtaposition(C1, C2): Code, Code -> Code

Given an \([n_1,k,d_1]\) code \(C_1\) and an \([n_2,k,d_2]\) code \(C_2\) of the same dimension, where both codes are defined over the same field \(K\), the function returns a \([n_1+n_2,k,\geq d_1+d_2]\) code whose generator matrix is HorizontalJoin(A, B), where \(A\) and \(B\) are the generator matrices for codes \(C_1\) and \(C_2\), respectively.

ConcatenatedCode(O, I): Code, Code -> Code

Given a \([N,K,D]\)-code \(O\) defined over \(GF(q^k)\) and a \([n,k,d]\)-code \(I\) defined over \(GF(q)\), construct the \([Nn,Kk,\delta \ge dD]\) concatenated code by taking \(O\) as outer code and \(I\) as inner code.

Example: Concatenated Code (ex-b27a80)

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)

Run in calculatorCopy input

ConstructionX(C1, C2, C3): Code, Code, Code -> Code

Let \(C_1,C_2\) and \(C_3\) be codes with parameters \([n_1, k_1, d_1]\), \([n_2, k_2, d_2]\) and \([n_3, k_3, d_3]\), respectively, where \(C_1\) is a union of \(b=2^{k_3}\) cosets of \(C_2\), (so \(n_1=n_2\) and \(k_2 \leq k_1\)) and \(k_1 = k_2+k_3\). The construction divides \(C_1\) into a union of cosets of \(C_2\) and attaches a different codeword of \(C_3\) to each coset. The new code has parameters \([n_1+n_3,k_1,\ge\min\{\ d_2,d_1+d_3 \} ]\). For further details see [MacWilliams and Sloane, 1978, p.581].

ConstructionXChain(S, C): [Code], Code -> [Code]

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\).

Example: construction X (ex-78f34f)

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

Run in calculatorCopy input

ConstructionX3(C1, C2, C3, D1, D2): Code, Code, Code, Code, Code -> Code, Map

Given a chain of codes \(C_1=[n,k_1,d_1]\), \(C_2=[n,k_2,d_2]\), and \(C_3=[n,k_3,d_3]\) with \(k_3 < k_2 < k_1\), and suffix codes \(D_1=[n_1,k_1-k_2,e_1]\) and \(D_2=[n_2,k_3-k_2,e_2]\), construct a code \(C=[n+n_1+n_2,k_1,\ge min\{d_3,d_1+e_1,d_2+e_2\}\). For further details see [MacWilliams and Sloane, 1978, p.583].

ConstructionX3u(C1, C2, C3, D1, D2): Code, Code, Code, Code, Code -> Code, Code

Given two chains of codes \(C_1=[n,k_1] \subset C_2=[n,k_2] \subset C_3=[n,k_3]\) and \(D_1=[n',k_1-k_3] \subset D_2=[n',k_2-k_3]\), return the codes \(C=[n+n',k_1] \subset C'=[n+n',k_2]\) using Construction X with \(C_1, C_3\) and \(D_1\) resp. \(C_2, C_3\) and \(D_2\).

Example: X3 (ex-3a19a8)

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

Run in calculatorCopy input

ConstructionXX(C1, C2, C3, D2, D3): Code, Code, Code, Code, Code -> Code

Let the parameters of codes \(C_1,C_2,C_3\) be \([n_1,k,d_1],[n_1,k-l_2,d_2]\) and \([n_1,k-l_3,d_3]\) respectively, where \(C_2\) and \(C_3\) are subcodes of \(C_1\). Codes \(D_2,D_3\) must have dimensions \(l_2,l_3\), with parameters \([n_2,l_2,\delta_2],[n_3,l_3,\delta_3]\) say. The construction breaks \(C_1\) up into cosets of \(C_2\) and \(C_3\) with the relevant tails added from \(D_2\) and \(D_3\). If the intersection of \(C_1\) and \(C_2\) has minimum distance \(d_0\) then the newly constructed code will have parameters \([n_1+n_2+n_3,k,\min\{d_0,d_2+\delta_2,d_3+\delta_3,d_1+\delta_2+\delta_3\}]\). For further details see [Alltop, 1984].

Example: XX (ex-db315b)

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

Run in calculatorCopy input

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

Run in calculatorCopy input

Thus the actual minimum distance is one greater than the lower bound guaranteed by Construction XX.

ZinovievCode(I, O): [Code], [Code] -> Code

The arguments are as follows: The first argument must be a sequence \(I\) containing an increasing chain of \(r\) codes with parameters,

\[[n,k_1,d_1]_q \subset [n,k_2,d_2]_q \subset \ldots \subset [n,k_r,d_r]_q\]

where \(0=k_0<k_1<k_2< \ldots < k_r\), (the inner codes). The second argument must be a sequence \(O\) of \(r\) codes with parameters \([N,K_i,D_i]_{Q_i}\), where \(Q_i = q^{e_i}\) and \(e_i = k_i - k_{i-1}\) for \(i = 1 \ldots r\) (the outer codes). The function constructs a generalised concatenated \([n*N,K,D]_q\) code is constructed, where \(K=e_1K_1+ \ldots +e_rK_r\) and \(D = min(d_1D_1,\ldots ,d_rD_r)\). For further details see [MacWilliams and Sloane, 1978, p.590].

Example: Zinoviev (ex-cc2def)

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)

Run in calculatorCopy input

ConstructionY1(C): Code -> Code

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,\geq d]\). For further details see [MacWilliams and Sloane, 1978, p.592].

ConstructionY1(C, w): Code, RngIntElt -> Code

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,\geq d]\).