Constructing new covering arrays from LFSR sequences over finite fields
Let q be a prime power and q be the finite field with q elements. A q-ary m-sequence is a linear recurrence sequence of elements from q with the maximum possible period. A covering array CA(N;t,k,v) of strength t is a N×k array with entries from an alphabet of size v, with the property that any N×m subarray has at least one row equal to every possible m-tuple of the alphabet. The covering array number CAN(t,k,v) is the minimum number N such that a CA(N;t,k,v) exists. Finding upper bounds for covering array numbers is one of the most important questions in this research area. Raaphorst, Moura and Stevens give a construction for covering arrays of strength 3 using m-sequences that improves upon some previous best bounds for covering array numbers. In this paper we introduce a method that generalizes this construction to strength greater than or equal to 4. Our implementation of this method returned new covering arrays and improved upon 38 previously best known covering array numbers. The new covering arrays are given here by listing the essential elements of their construction.
|Keywords||Covering arrays, Exhaustive search algorithms, Linear feedback shift register sequences, Primitive polynomials over finite fields|
Tzanakis, G. (Georgios), Moura, L. (Lucia), Panario, D, & Stevens, B. (2016). Constructing new covering arrays from LFSR sequences over finite fields. Discrete Mathematics, 339(3), 1158–1171. doi:10.1016/j.disc.2015.10.040