Adding a Parity Check Bit

Given a (linear) orthogonal array OA(M, s, ℤ2, k) with k even, a (linear) OA(2M, s + 1, ℤ2, k + 1) can be constructed. Correspondingly, a (linear) (s + 1, N, d + 1)-code can be constructed based on a (linear) (s, N, d)-code over ℤ2 provided that d is odd.

Since code truncation reverses this process, a (linear) OA(2M, s + 1, ℤ2, k + 1) with even k exists if and only if a (linear) OA(M, k, ℤ2, 2) exists. Similarly a (linear) (s + 1, N, d + 1)-code over ℤ2 with odd d exists if and only if a (linear) (s, N, d)-code over ℤ2 exists.

There is no corresponding propagation rule for ordered orthogonal arrays with depth T > 1 or for (t, m, s)-nets (it would correspond to increasing s and m while leaving t constant).

Construction for Orthogonal Arrays

It is shown in [1] (the special case for k = 2 can already be found in [2]) that the new OA Aʹ can be constructed as

Aʹ = $\displaystyle \left(\vphantom{\begin{array}{cc} \mathcal{A} & \vec{0}_{M\times1}\\ 1-\mathcal{A} & \vec{1}_{M\times1}\end{array}}\right.$$\displaystyle \begin{array}{cc} \mathcal{A} & \vec{0}_{M\times1}\\ 1-\mathcal{A} & \vec{1}_{M\times1}\end{array}$$\displaystyle \left.\vphantom{\begin{array}{cc} \mathcal{A} & \vec{0}_{M\times1}\\ 1-\mathcal{A} & \vec{1}_{M\times1}\end{array}}\right)$,

where A is the original OA. If A is linear with generator matrix H and M = 2m, a generator matrix of Aʹ is given by

$\displaystyle \left(\vphantom{\begin{array}{cc} \vec{1}_{1\times s} & 1\\ \vec{H} & \vec{0}_{m\times1}\end{array}}\right.$$\displaystyle \begin{array}{cc} \vec{1}_{1\times s} & 1\\ \vec{H} & \vec{0}_{m\times1}\end{array}$$\displaystyle \left.\vphantom{\begin{array}{cc} \vec{1}_{1\times s} & 1\\ \vec{H} & \vec{0}_{m\times1}\end{array}}\right)$.

Construction for Codes

The result for codes is obtained by adding a parity check. An additional coordinate is appended to each code word such that the sum of the coordinates of each new code word is zero. This process is sometimes called lengthening the code.

For linear codes over ℤ2 with odd minimum distance it can be shown that this procedure always increases the minimum distance, i.e., a linear [s + 1, n, d + 1]-code is obtained by lengthening a linear [s, n, d]-code.

See also

References

[1]Esther Seiden and Rita Zemach.
On orthogonal arrays.
Annals of Mathematical Statistics, 37:1355–1370, 1966.
[2]Esther Seiden.
On the problem of construction of orthogonal arrays.
Annals of Mathematical Statistics, 25:151–156, 1954.
[3]F. Jessie MacWilliams and Neil J. A. Sloane.
The Theory of Error-Correcting Codes.
North-Holland, Amsterdam, 1977.
[4]A. S. Hedayat, Neil J. A. Sloane, and John Stufken.
Orthogonal Arrays.
Springer Series in Statistics. Springer-Verlag, 1999.
[5]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. “Adding a Parity Check Bit.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CParityCheck.html

Show usage of this method