2017/08/25 by Georgios Tzanakis, Tzanakis, Georgios
Computer Science · Engineering · #05B15 #05B20 #05B40 #94A55 #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1708.07828
openalex publication_date 2017/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The focus of this thesis is the study and construction of covering arrays, relying on maximal period sequences and other tools from finite fields. A covering array of strength t, denoted CA(N; t, k,v), is an N× k array with entries from an alphabet A of size v, with the property that in the N× t subarray defined by any t columns, each of the vt vectors in At appears at least once as a row. Covering arrays generalize orthogonal arrays, which are classic combinatorial objects that have been studied extensively. Constructing covering arrays with a small row-to-column ratio is important in the design of statistical experiments, however it is also a challenging mathematical problem. Linear feedback shift register (LFSR) sequences are sequences of elements from a finite field that satisfy a linear recurrence relation. It is well-known that these are periodic; LFSR sequences that attain the maximum possible period are maximal (period) sequences, often abbreviated to m-sequences in the literature. Arrays constructed from cyclic shifts of maximal sequences possess strong combinatorial properties and have been previously used to construct orthogonal and covering arrays (Moura et al., 2016), although only one of the known constructions is for covering arrays that are not orthogonal arrays (Raaphorst et al., 2014). In this thesis we present several new such constructions. The cornerstone of our results is a study of the combinatorial properties of arrays constructed from maximal sequences, where we make fundamental connections with concepts from diverse areas of discrete mathematics, such as orthogonal arrays, error-correcting codes, divisibility of polynomials and structures of finite geometry. One aspect of our work involves [..]