Construction X4 with Extended Narrow-Sense BCH Codes

Let C1ʹ denote an [s1, n1, d1ʹ]-code which is a subcode of an [s1, n1 + Δn, d1]-code C1. Similarly, let C2ʹ denote an [s2, n2, d2ʹ]-code which is a subcode of an [s2, n2 + Δn, d2]-code C2. Then construction X4 allows the construction of an [s1 + s2, n1 + n2 + Δn, d]-code C with

d = min{d1ʹ, d2ʹ, d1 + d2},

where a value of diʹ = si + 1 (i.e., Ciʹ = { 0}) can be treated as diʹ = ∞ [1].

Correspondingly, if A1 denotes a linear orthogonal array OA(bm1, s1,Fb, k1) which is a subspace of a linear OA(bm1+Δm, s1,Fb, k1ʹ) A1ʹ, and if A2 denotes a linear OA(bm2, s2,Fb, k2) which is a subspace of a linear OA(bm2+Δm, s2,Fb, k2ʹ) A2ʹ, then a linear OA(bm1+m2+Δm, s1 + s2,Fb, k) with

k = min{k1ʹ, k2ʹ, k1 + k2 +1}

can be constructed, where a value of kiʹ = si (i.e., Aiʹ = Fbsi) can be treated as kiʹ = ∞.

Equivalent results hold also for non-linear codes as well as for non-linear OAs, provided that the larger codes/OAs can be partitioned in translates of the smaller ones (see below).


For i ∈ {1, 2} let Giʹ denote generator matrices of Ciʹ and let Gi denote generator matrices for Ci such that the first ni rows of Gi are equal to Giʹ. Furthermore let Gi denote the remaining Δn rows of Gi. Then a generator matrix of C is given by

G = $\displaystyle \left(\vphantom{\begin{array}{cc} \vec{G}_{1}ʹ & \vec{0}_{n_{1}\t… …\vec{G}_{2}”\\ \vec{0}_{n_{2}\times s_{1}} & \vec{G}_{2}ʹ\end{array}}\right.$$\displaystyle \begin{array}{cc} \vec{G}_{1}ʹ & \vec{0}_{n_{1}\times s_{2}}\\ … …{1}” & \vec{G}_{2}”\\ \vec{0}_{n_{2}\times s_{1}} & \vec{G}_{2}ʹ\end{array}$$\displaystyle \left.\vphantom{\begin{array}{cc} \vec{G}_{1}ʹ & \vec{0}_{n_{1}\t… …\vec{G}_{2}”\\ \vec{0}_{n_{2}\times s_{1}} & \vec{G}_{2}ʹ\end{array}}\right)$.

The construction is self-dual, i.e., if the same construction is performed using the check-matrices of C1, C1ʹ, C2, C2ʹ instead of the generator matrices of C1ʹ, C1, C2ʹ, C2, respectively, a check-matrix of C is obtained. In particular, this implies that this construction can be applied directly to the generator matrices of orthogonal arrays.

Construction for Non-Linear Codes

Suppose that the codes Ciʹ and Ci are (si, Ni, diʹ)- and (si, NiΔN, di)-codes, respectively, and Ci is the union of ΔN disjoint translates of Ciʹ, i.e,

Ci = $\displaystyle \bigcup_{{j=1}}^{{\Delta N}}$(vj(i) + Ciʹ),


C := $\displaystyle \bigcup_{{j=1}}^{{\Delta N}}$$\displaystyle \bigcup_{{\vec{x}_{1}\in\mathcal{C}_{1}ʹ}}^{}$$\displaystyle \bigcup_{{\vec{x}_{2}\in\mathcal{C}_{2}ʹ}}^{}$(vj(1) + x1,vj(2) + x2)

is an (s1 + s2, N1N1ΔN, d)-code.

Construction for Non-Linear Orthogonal Arrays

Suppose that the Ai and Aiʹ are OA(Mi, si, Sb, ki) and OA(MiΔM, si, Sb, kiʹ), respectively, and Aiʹ is the union of ΔM disjoint translates of Ai, i.e.,

Aiʹ = $\displaystyle \bigcup_{{j=1}}^{{\Delta M}}$(vj(i) + Ai),


A := $\displaystyle \bigcup_{{j=1}}^{{\Delta M}}$$\displaystyle \bigcup_{{\vec{x}_{1}\in\mathcal{A}_{1}}}^{}$$\displaystyle \bigcup_{{\vec{x}_{2}\in\mathcal{A}_{2}}}^{}$(vj(1) + x1,vj(2) + x2)

is an OA(M1M2ΔM, s1 + s2, Sb, k) [2, Theorem 10.5].

Special Cases


Construction X4 is not used in its general form by MinT. In addition to the cases covered by Construction X, it is applied to all pairs C1ʹ ⊂ C1 (or A1A1ʹ) considered by construction X, but only for the following pairs of codes C2ʹ ⊂ C2 (or their dual OAs A2A2ʹ):

These are exactly the cases considered in [3, Section 3.6].


[1]Neil J. A. Sloane, S. M. Reddy, and Chin-Long Chen.
New binary codes.
IEEE Transactions on Information Theory, 18(4):503–510, July 1972.
[2]A. S. Hedayat, Neil J. A. Sloane, and John Stufken.
Orthogonal Arrays.
Springer Series in Statistics. Springer-Verlag, 1999.
[3]Yves Edel.
Eine Verallgemeinerung von BCH-Codes.
PhD thesis, Ruprecht-Karls-Universität, Heidelberg, 1996. PDF


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 X4 with Extended Narrow-Sense BCH Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2008-04-04.

Show usage of this method