FoCM 2014 conference

Workshop A4 - Graph Theory and Combinatorics

December 13, 15:30 ~ 16:00 - Room B11

Constructing covering arrays from $m$-sequences

Daniel Panario

Let $q$ be a prime power and $\mathbb{F}_q$ the finite field of $q$ elements. A $q$-ary $m$-sequence is a periodic sequence of elements from $\mathbb{F}_q$, which is generated by a linear recurrence relation of order $n$, and has maximal period $q^n-1$. These sequences play a crucial role in a wide variety of communications and cryptographic applications.
A covering array $CA(N; t; k; v)$ is a $N \times k$ array with entries from an alphabet of size $v$, with the property that any $N \times t$ sub-array has at least one row equal to every possible $t$-tuple. Covering arrays are used in applications such as software and hardware testing. It is crucial for such applications to find covering arrays $CA(N; t; k; v)$ with the smallest $N$ possible, for given $t, k, v$.
There are various algebraic and combinatorial constructions, as well as computer generation methods for covering arrays. Although constructions using $m$-sequences exist in the literature, these are a few and, until recently, only focused on similar combinatorial objects (orthogonal arrays'' that are covering arrays with more restrictions). Moura, Raaphorst and Stevens (2013) give a construction for covering arrays of strength 3 using $m$-sequences, which are the best known for many cases. For any prime power $q$, they give a covering array of strength $t = 3$ with $k = q^2 + q + 1$ columns over $v = q$ symbols that has size $N = 2q^3-1$ (number of rows).