Covering Arrays from Maximal Sequences over Finite FieldsPublic Deposited
Downloadable ContentDownload PDF
- Resource Type
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 v t vectors in A t 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 rowto-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 , although only one of the known constructions is for covering arrays that are not orthogonal arrays . 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 concatenating arrays corresponding to different maximal sequences and finding subarrays that are covering arrays. We express this as an optimization problem, to which we give an algorithmic solution based on backtracking, an underlying finite field theory and connections to other combinatorial objects. The results of our experiments include 37 new covering arrays of strength 4 and one of strength 5.For integers v ≥ 2, we introduce cyclic trace arrays modulo v, a variation of arrays from maximal sequences that we study using finite field characters - homomorphisms from the finite field to the unit circle of complex numbers. In particular, we use well-known bounds on character sums to derive conditions subject to which cyclic trace arrays modulo v are covering arrays, and we present new infinite families of covering arrays of strengths 3 and 4, as well as one of arbitrary strength which appears to be the second such family in the known literature . We also express the number of times that different vectors appear in the rows of a cyclic trace array modulo v as the solution of a linear program.
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Rights Notes
- Copyright © 2017 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- In Collection: