Skip to main content


Weitere Artikel dieser Ausgabe durch Wischen aufrufen

20.02.2018 | Ausgabe 11/2018

Designs, Codes and Cryptography 11/2018

Covering arrays of strength three from extended permutation vectors

Designs, Codes and Cryptography > Ausgabe 11/2018
Jose Torres-Jimenez, Idelfonso Izquierdo-Marquez
Wichtige Hinweise
Communicated by D. Panario.


A covering array \(\text{ CA }(N;t,k,v)\) is an \(N\times k\) array such that in every \(N\times t\) subarray each possible t-tuple over a v-set appears as a row of the subarray at least once. The integers t and v are respectively the strength and the order of the covering array. Let v be a prime power and let \({\mathbb {F}}_v\) denote the finite field with v elements. In this work the original concept of permutation vectors generated by a \((t-1)\)-tuple over \({\mathbb {F}}_v\) is extended to vectors generated by a t-tuple over \({\mathbb {F}}_v\). We call these last vectors extended permutation vectors (EPVs). For every prime power v, a covering perfect hash family \(\text{ CPHF }(2;v^2-v+3,v^3,3)\) is constructed from EPVs given by subintervals of a linear feedback shift register sequence over \({\mathbb {F}}_v\). When \(v\in \{7,9,11,13,16,17,19,23,25\}\) the covering array \(\text{ CA }(2v^3-v;3,v^2-v+3,v)\) generated by \(\text{ CPHF }(2;v^2-v+3,v^3,3)\) has less rows than the best-known covering array with strength three, \(v^2-v+3\) columns, and order v. CPHFs formed by EPVs are also constructed using simulated annealing; in this case the results improve the size of eighteen covering arrays of strength three.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Über diesen Artikel

Weitere Artikel der Ausgabe 11/2018

Designs, Codes and Cryptography 11/2018 Zur Ausgabe

Premium Partner