New Codes from Old#

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

Sum, Intersection and Dual#

For the following operators, \(C\) and \(D\) are codes defined as subsets (or subspaces) of the same \(R\)-space \(V\).

C + D: Code, Code -> Code#: The (vector space) sum of the linear codes \(C\) and \(D\), where \(C\) and \(D\) are contained in the same \(R\)-space \(V\).

C meet D: Code, Code -> Code#: The intersection of the linear codes \(C\) and \(D\), where \(C\) and \(D\) are contained in the same \(R\)-space \(V\).

Dual(C): Code -> Code#: The dual \(D\) of the linear code \(C\). The dual consists of all codewords in the \(R\)-space \(V\) which are orthogonal to all codewords of \(C\).

Example: Sum Intersection (ex-e4970a)#

Verify some simple results from the sum and intersection of subcodes.

> R<w> := GR(9,2);
> P<x> := PolynomialRing(R);
> g := x^2 + 7*w*x + 1;
> C := CyclicCode(5, g);
> C;
(5, 43046721) Cyclic Code over GaloisRing(3, 2, 2)
Generator matrix:
[  1   0   0   1   w]
[  0   1   0 2*w 2*w]
[  0   0   1   w   1]
[  0   0   0   3   0]
[  0   0   0   0   3]
>
> C1 := sub< C | C.1 >;
> C1;
(5, 81, 3) Linear Code over GaloisRing(3, 2, 2)
Generator matrix:
[1 0 0 1 w]
> C2 := sub< C | C.4 >;
> C2;
(5, 9, 1) Linear Code over GaloisRing(3, 2, 2)
Generator matrix:
[0 0 0 3 0]
> C3 := sub< C | { C.1 , C.4} >;
> C3;
(5, 729, 1) Linear Code over GaloisRing(3, 2, 2)
Generator matrix:
[1 0 0 1 w]
[0 0 0 3 0]
> (C1 + C2) eq C3;
true
> (C1 meet C3) eq C1;
true

Run in calculator

Standard Constructions#

DirectSum(C, D): Code, Code -> Code#: Given a length \(n_1\) code \(C\) and a length \(n_2\) code \(D\), both over the same ring \(R\), construct the direct sum of \(C\) and \(D\). The direct sum consists of all length \(n_1+n_2\) vectors \(u|v\), where \(u \in C\) and \(v \in D\).

DirectProduct(C, D): Code, Code -> Code#: Given a length \(n_1\) code \(C\) and a length \(n_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\) and its generator matrix is the Kronecker product of the basis matrices of \(C\) and \(D\).

C1 cat C2: Code, Code -> Code#: Given codes \(C1\) and \(C2\), both defined over the same ring \(R\), 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\).

ExtendCode(C): Code -> Code#: Given a length \(n\) 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.

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

PlotkinSum(C, D): Code, Code -> Code#: Given codes \(C\) and \(D\) both over the same ring \(R\) and of the same length \(n\), construct the Plotkin sum of \(C\) and \(D\). The Plotkin sum consists of all vectors \(u|u+v\), \(u \in C\) and \(v \in D\).

PunctureCode(C, i): Code, RngIntElt -> Code#: Given a length \(n\) 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 a length \(n\) 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 a length \(n\) 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 a length \(n\) 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: lengths (ex-fe796f)#

We combine codes in various ways and look at the length of the new code.

> R<w> := GR(8,2);
> C1 := RandomLinearCode(R, 4, 2);
> C2 := RandomLinearCode(R, 5, 3);
> Length(C1);
4
> Length(C2);
5
> C3 := DirectSum(C1, C2);
> Length(C3);
9
> C4 := DirectProduct(C1, C2);
> Length(C4);
20
> C5 := C1 cat C2;
> Length(C5);
9

Run in calculator

Example: Punct Z4 (ex-0c4967)#

We note that, in general, puncturing a code over \({\mathbb{Z}}_4\) reduces the minimum Lee distance by \(2\).

> C := PreparataCode(3);
> C;
(8, 256, 4) Linear Code over IntegerRing(4)
Generator matrix:
[1 0 0 0 3 1 2 1]
[0 1 0 0 2 1 1 3]
[0 0 1 0 1 1 3 2]
[0 0 0 1 3 2 3 3]
> MinimumLeeWeight(C);
6
> C1 := PunctureCode(C,8);
> C1;
(7, 256, 3) Linear Code over IntegerRing(4)
Generator matrix:
[1 0 0 0 3 1 2]
[0 1 0 0 2 1 1]
[0 0 1 0 1 1 3]
[0 0 0 1 3 2 3]
> MinimumLeeWeight(C1);
4

Run in calculator