Construction X with Reed–Solomon Codes

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

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.

See Also

• [2, Theorem 14.1]

• Construction X is a special case of construction X4

• Generalization for arbitrary OOAs

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

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Construction X with Reed–Solomon Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2024-09-05. http://mint.sbg.ac.at/desc_CConsX-ReedSolomon.html