A construction for strength-3 covering arrays from linear feedback shift register sequences
We present a new construction for covering arrays inspired by ideas from Munemasa (Finite Fields Appl 4:252260, 1998) using linear feedback shift registers (LFSRs). For a primitive polynomial \(f\) of degree \(m\) over \(\mathbb F _q\), by taking all unique subintervals of length \(\frac{q^m-1}{q-1}\) from the LFSR generated by \(f\), we derive a general construction for optimal variable strength orthogonal arrays over an infinite family of abstract simplicial complexes. For \(m=3\), by adding the subintervals of the reversal of the LFSR to the variable strength orthogonal array, we derive a strength-3 covering array over \(q^2+q+1\) factors, each with \(q\) levels that has size only \(2q^3-1\), i.e. a \(\text {CA}(2q^3-1; 3, q^2+q+1, q)\) whenever \(q\) is a prime power. When \(q\) is not a prime power, we obtain results by using fusion operations on the constructed array for higher prime powers and obtain improved bounds. Colbourn maintains a repository of the best known bounds for covering array sizes for all \(2 \le q \le 25\). Our construction, with fusing when applicable, currently holds records of the best known upper bounds in this repository for all \(q\) except \(q = 2,3,6\). By using these covering arrays as ingredients in recursive constructions, we build covering arrays over larger numbers of factors, again providing significant improvements on the previous best upper bounds.
covering arrays linear feedback shift registers variable strength orthogonal arrays combinatorial designs 05b15 05b05 05b40