Constructing new covering arrays from LFSR sequences over finite fields

详细信息    查看全文

• 作者：Georgios Tzanakis^a ; ^{gtzanaki@math.carleton.ca" class="auth_mail" title="E-mail the corresponding author} ; Lucia Moura^b ; ^{lucia@eecs.uottawa.ca" class="auth_mail" title="E-mail the corresponding author} ; Daniel Panario^a ; ^{daniel@math.carleton.ca" class="auth_mail" title="E-mail the corresponding author} ; Brett Stevens^a ; ^{brett@math.carleton.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Covering arrays ; Linear feedback shift register sequences ; Primitive polynomials over finite fields ; Exhaustive search algorithms
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 March 2016
• 年：2016
• 卷：339
• 期：3
• 页码：1158-1171
• 全文大小：432 K

文摘

Let q$q$ be a prime power and F_q${\mathbb{F}}_q$ be the finite field with q$q$ elements. A q$q$-ary m-sequence   is a linear recurrence sequence of elements from F_q${\mathbb{F}}_q$ with the maximum possible period. A covering array  CA(N;t,k,v)$CA(N;t,k,v)$of strength  t$t$ is a N×k$N\times k$ array with entries from an alphabet of size v$v$, with the property that any N×m$N\times m$ subarray has at least one row equal to every possible m$m$-tuple of the alphabet. The covering array number  CAN(t,k,v)$CAN(t,k,v)$ is the minimum number N$N$ such that a CA(N;t,k,v)$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.