Construction X with Kerdock and Delsarte–Goethals OAs

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 C1C2, such that the dimension of C2 and the minimum distance of C1 is obtained. This is bought by increasing the length of the resulting code by the length of an additional code Ce, which has to be chosen depending on the parameters of C1 and C2.

Given a linear [s, n1, d1]-code C1, which is a subcode of a linear [s, n2, d2]-code C2, as well as an additional linear [se, ne, de]-code Ce, all over the same field, a new linear [s + se, n1 + ne, d2 + de]-code can be constructed provided that n1 + nen2 and d2 + ded1. Usually Ce will be chosen such that n2 = n1 + ne and d1 = d2 + de, however in some situations a smaller value of ne or de 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 A2 which is a subspace of A1 (or at least A1 a union of disjoint translates of A2) with parameters OA(Mi, s, Sb, ki) and an auxiliary OA Ae with parameters OA(bseM2/M1, se, Sb, ke) such that M1/M2 translates of Ae form a partition of Sbse, an OA(M2bse, s + se, Sb, min{k1, k2 + ke +1}) can be constructed.

Construction

Let G1, G2, and Ge denote the generator matrices of C1, C2, and Ce, respectively, such that the rows of G1 are a subset of the rows of G2. Let G2ʹ denote the ne×s matrix consisting of ne rows of G2 that are not in G1. Then the new code is defined by the (n2 + ne)×(s + se) 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 n1 vectors have a weight of at least d1 because these are essentially the code words of C1 with se additional 0’s appended. All other non-zero code words have a weight of at least d2 + de, because they are built using a non-zero code word from C2 next to a non-zero code word from Ce.

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

Special Cases

Applications

MinT applies construction X in the following situations:

See Also

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 Kerdock and Delsarte–Goethals OAs.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2008-04-04. http://mint.sbg.ac.at/desc_CConsX-Kerdock.html

Show usage of this method