## 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_{1} ⊂ C_{2}, such that the dimension of C_{2} and the minimum distance of C_{1} 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_{1} and C_{2}.

Given a linear [*s*, *n*_{1}, *d*_{1}]-code C_{1}, which is a subcode of a linear [*s*, *n*_{2}, *d*_{2}]-code C_{2}, 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*_{1} + *n*_{e}, *d*_{2} + *d*_{e}]-code can be constructed provided that *n*_{1} + *n*_{e} ≤ *n*_{2} and *d*_{2} + *d*_{e} ≤ *d*_{1}. Usually C_{e} will be chosen such that *n*_{2} = *n*_{1} + *n*_{e} and *d*_{1} = *d*_{2} + *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_{2} which is a subspace of A_{1} (or at least A_{1} a union of disjoint translates of A_{2}) with parameters OA(*M*_{i}, *s*, *S*_{b}, *k*_{i}) and an auxiliary OA A_{e} with parameters OA(*b*^{se}*M*_{2}/*M*_{1}, *s*_{e}, *S*_{b}, *k*_{e}) such that *M*_{1}/*M*_{2} translates of A_{e} form a partition of *S*_{b}^{se}, an OA(*M*_{2}*b*^{se}, *s* + *s*_{e}, *S*_{b}, min{*k*_{1}, *k*_{2} + *k*_{e} +1}) can be constructed.

### Construction

Let **G**_{1}, **G**_{2}, and **G**_{e} denote the generator matrices of C_{1}, C_{2}, and C_{e}, respectively, such that the rows of **G**_{1} are a subset of the rows of **G**_{2}. Let **G**_{2}ʹ denote the *n*_{e}×*s* matrix consisting of *n*_{e} rows of **G**_{2} that are not in **G**_{1}. Then the new code is defined by the (*n*_{2} + *n*_{e})×(*s* + *s*_{e}) generator matrix

All code words formed by a non-trivial linear combination of the first *n*_{1} vectors have a weight of at least *d*_{1} because these are essentially the code words of C_{1} with *s*_{e} additional 0’s appended. All other non-zero code words have a weight of at least *d*_{2} + *d*_{e}, because they are built using a non-zero code word from C_{2} 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

_{1}is the [*s*, 0,*s*+ 1]-trivial code, which is a subcode of every linear code C_{2}, construction X reduces to juxtaposition of C_{2}and C_{e}.If C

_{1}= C_{2}, the auxiliary code C_{e}must be an [*s*_{e}, 0,*s*_{e}+ 1]-trivial code and construction X reduces to embedding C_{1}in the larger space**F**_{b}^{s+se}.

### Applications

MinT applies construction X in the following situations:

Reed-Solomon codes RS(

*n*_{1},*b*) ⊂ RS(*n*_{2},*b*) with*n*_{1}<*n*_{2}Algebraic-geometric codes AG(

*F*,*n*_{1}) ⊂ AG(*F*,*n*_{2}) with*n*_{1}<*n*_{2}Cyclic codes C(

*A*_{1}) ⊂ C(*A*_{2}) with*A*_{2}ʹ ⊂*A*_{1}ʹExtended cyclic codes C

_{e}(*k*_{1}) ⊂ C_{e}(*k*_{2}) with*k*_{1}>*k*_{2}Sequences C

_{r}and D_{r}by de Boer and BrouwerProjective code from ovoid containing an [

*s*, 1,*s*−1]-subcode.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: 2015-09-03.
http://mint.sbg.ac.at/desc_CConsX-ReedSolomon.html