MinT - Construction X

Construction X

ConstructionÂ X [1, Ch.Â 18, TheoremÂ 9], a special case of constructionÂ X4, allows the construction of a new code based on two linear codes C₁ âŠ‚ C₂, such that the dimension of C₂ and the minimum distance of C₁ is obtained. This is bought by increasing the length of the resulting code by the length of an additional code C_e, which has to be chosen depending on the parameters of C₁ and C₂.

Given a linear [s, n₁, d₁]-code C₁, which is a subcode of a linear [s, n₂, d₂]-code C₂, as well as an additional linear [s_e, n_e, d_e]-code C_e, all over the same field, a new linear [s + s_e, n₁ + n_e, d₂ + d_e]-code can be constructed provided that n₁ + n_e â‰¤ n₂ and d₂ + d_e â‰¤ d₁. Usually C_e will be chosen such that n₂ = n₁ + n_e and d₁ = d₂ + d_e, however in some situations a smaller value of n_e or d_e may also yield good results.

Since constructionÂ X is derived from constructionÂ X4, it can also be applied to (not necessarily linear) orthogonal arrays. Given a linear OA A₂ which is a subspace of A₁ (or at least A₁ a union of disjoint translates of A₂) with parameters OA(M_i, s, S_b, k_i) and an auxiliary OA A_e with parameters OA(b^s_eM₂/M₁, s_e, S_b, k_e) such that M₁/M₂ translates of A_e form a partition of S_b^s_e, an OA(M₂b^s_e, s + s_e, S_b, min{k₁, k₂ + k_e +1}) can be constructed.

Construction

Let G₁, G₂, and G_e denote the generator matrices of C₁, C₂, and C_e, respectively, such that the rows of G₁ are a subset of the rows of G₂. Let G₂Ê¹ denote the n_eÃ—s matrix consisting of n_e rows of G₂ that are not in G₁. Then the new code is defined by the (n₂ + n_e)Ã—(s + s_e) generator matrix

$\displaystyle \left(\vphantom{\begin{array}{cc} \vec{G}_{1} & \vec{0}_{n_{1}\times s_{e}}\\ \vec{G}_{2}Ê¹ & \vec{G}_{e}\end{array}}\right.$ $\displaystyle \begin{array}{cc} \vec{G}_{1} & \vec{0}_{n_{1}\times s_{e}}\\ \vec{G}_{2}Ê¹ & \vec{G}_{e}\end{array}$ $\displaystyle \left.\vphantom{\begin{array}{cc} \vec{G}_{1} & \vec{0}_{n_{1}\times s_{e}}\\ \vec{G}_{2}Ê¹ & \vec{G}_{e}\end{array}}\right)$ .

All code words formed by a non-trivial linear combination of the first n₁ vectors have a weight of at least d₁ because these are essentially the code words of C₁ with s_e additional 0â€™s appended. All other non-zero code words have a weight of at least d₂ + d_e, because they are built using a non-zero code word from C₂ next to a non-zero code word from C_e.

For the construction for non-linear codes and OAs see the relevant sections in the discussion of construction X4.

Special Cases

If C₁ is the [s, 0, s + 1]-trivial code, which is a subcode of every linear code C₂, constructionÂ X reduces to juxtaposition of C₂ and C_e.
If C₁ = C₂, the auxiliary code C_e must be an [s_e, 0, s_e + 1]-trivial code and constructionÂ X reduces to embedding C₁ in the larger space F_b^s+s_e.

Applications

MinT applies constructionÂ X in the following situations:

Reed-Solomon codes RS(n₁, b) âŠ‚ RS(n₂, b) with n₁ < n₂
Algebraic-geometric codes AG(F, n₁) âŠ‚ AG(F, n₂) with n₁ < n₂
Cyclic codes C(A₁) âŠ‚ C(A₂) with A₂Ê¹ âŠ‚ A₁Ê¹
Extended cyclic codes C_e(k₁) âŠ‚ C_e(k₂) with k₁ > k₂
Sequences C_r and D_r by de Boer and Brouwer
Projective code from ovoid containing an [s, 1, sâˆ’1]-subcode.
Codes embedded in larger codes using the VarÅ¡amov bound
Codes embedded in larger codes using the VarÅ¡amov-Edel bound
To the sequence of orthogonal arrays RM(1, u) âŠ‚ K(u) âŠ‚ DG(u, u/2 âˆ’ 1) consisting of Reed-Muller codes, Kerdock codes, and Delsarte-Goethals codes.

References

[1]	F.Â Jessie MacWilliams and Neil J.Â A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977.
[2]	JÃ¼rgen Bierbrauer. Introduction to Coding Theory. Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, London, New York, Washington D.C., 2004. MR2079734 (2005f:94001)

Copyright