MinT - Construction X4 with Kerdock OAs

Construction X4 with Kerdock OAs

Let C₁ʹ denote an [s₁, n₁, d₁ʹ]-code which is a subcode of an [s₁, n₁ + Δn, d₁]-code C₁. Similarly, let C₂ʹ denote an [s₂, n₂, d₂ʹ]-code which is a subcode of an [s₂, n₂ + Δn, d₂]-code C₂. Then construction X4 allows the construction of an [s₁ + s₂, n₁ + n₂ + Δn, d]-code C with

d = min{d₁ʹ, d₂ʹ, d₁ + d₂},

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

Correspondingly, if A₁ denotes a linear orthogonal array OA(b^m₁, s₁,F_b, k₁) which is a subspace of a linear OA(b^m₁+Δm, s₁,F_b, k₁ʹ) A₁ʹ, and if A₂ denotes a linear OA(b^m₂, s₂,F_b, k₂) which is a subspace of a linear OA(b^m₂+Δm, s₂,F_b, k₂ʹ) A₂ʹ, then a linear OA(b^{m₁+m₂+Δm}, s₁ + s₂,F_b, k) with

k = min{k₁ʹ, k₂ʹ, k₁ + k₂ +1}

can be constructed, where a value of k_iʹ = s_i (i.e., A_iʹ = F_b^s_i) can be treated as k_iʹ = ∞.

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).

Construction

For i ∈ {1, 2} let G_iʹ denote generator matrices of C_iʹ and let G_i denote generator matrices for C_i such that the first n_i rows of G_i are equal to G_iʹ. Furthermore let G_i” denote the remaining Δn rows of G_i. 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 C₁, C₁ʹ, C₂, C₂ʹ instead of the generator matrices of C₁ʹ, C₁, C₂ʹ, C₂, 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 C_iʹ and C_i are (s_i, N_i, d_iʹ)- and (s_i, N_i⋅ΔN, d_i)-codes, respectively, and C_i is the union of ΔN disjoint translates of C_iʹ, i.e,

C_i = $\displaystyle \bigcup_{{j=1}}^{{\Delta N}}$ (v_j⁽ⁱ⁾ + C_iʹ),

then

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}ʹ}}^{}$ (v_j⁽¹⁾ + x₁,v_j⁽²⁾ + x₂)

is an (s₁ + s₂, N₁N₁⋅ΔN, d)-code.

Construction for Non-Linear Orthogonal Arrays

Suppose that the A_i and A_iʹ are OA(M_i, s_i, S_b, k_i) and OA(M_i⋅ΔM, s_i, S_b, k_iʹ), respectively, and A_iʹ is the union of ΔM disjoint translates of A_i, i.e.,

A_iʹ = $\displaystyle \bigcup_{{j=1}}^{{\Delta M}}$ (v_j⁽ⁱ⁾ + A_i),

then

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}}}^{}$ (v_j⁽¹⁾ + x₁,v_j⁽²⁾ + x₂)

is an OA(M₁M₂⋅ΔM, s₁ + s₂, S_b, k) [2, Theorem 10.5].

Special Cases

If C_iʹ = { 0} (or A_iʹ = F_q^s_i) for one i, construction X applied to the remaining three codes / OAs follows.
If C_iʹ = { 0} (or A_iʹ = F_q^s_i) for i = 1 and i = 2, juxtaposition applied to C₁ and C₂ (or A₁ and A₂) follows.
If C₁ = C₁ʹ and C₂ = C₂ʹ, the direct product of C₁ and C₂ follows.

Applications

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 C₁ʹ ⊂ C₁ (or A₁ ⊂ A₁ʹ) considered by construction X, but only for the following pairs of codes C₂ʹ ⊂ C₂ (or their dual OAs A₂ ⊂ A₂ʹ):

If b ≠ 2 or s₂ is even, then the [s₂, s₂ − 1, 2]-parity-check code C₂ contains an [s₂, 1, s₂]-code C₂ʹ.
For b = 2 and s₂ odd, the [s₂, s₂ − 1, 2]-parity-check code C₂ contains only an [s₂, 1, s₂ − 1]-code C₂ʹ.
Truncating the ternary Hamming code H(3, 3) yields a [12, 9, 3]-code C₂ containing a [12, 1, 12]-code C₂ʹ .

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

References

[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.

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 X4 with Kerdock OAs.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CConsX4-Kerdock.html

Show usage of this method