A construction for strength-3 covering arrays from linear feedback shift register sequences

作者：Raaphorst Sebastian^*; Moura Lucia; Stevens Brett

来源：Designs, Codes and Cryptography, 2014, 73(3): 949-968.

DOI：10.1007/s10623-013-9835-2

• Covering arrays
• Variable strength orthogonal arrays
• Combinatorial designs
• Linear feedback shift registers

We present a new construction for covering arrays inspired by ideas from Munemasa (Finite Fields Appl 4:252-260, 1998) using linear feedback shift registers (LFSRs). For a primitive polynomial of degree over , by taking all unique subintervals of length from the LFSR generated by , we derive a general construction for optimal variable strength orthogonal arrays over an infinite family of abstract simplicial complexes. For , by adding the subintervals of the reversal of the LFSR to the variable strength orthogonal array, we derive a strength-3 covering array over factors, each with levels that has size only , i.e. a whenever is a prime power. When 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 . Our construction, with fusing when applicable, currently holds records of the best known upper bounds in this repository for all except . 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.

• 出版日期2014-12