Finite Fields in Combinatorial Arrays: Constructions and Applications

We discuss constructions based on finite fields of three types of combinatorial arrays: orthogonal, covering and ordered orthogonal arrays. In this talk, for each of these arrays, we briefly explain constructions based on finite fields, and main applications. Other combinatorial arrays have been similarly considered in the literature, including permutation arrays, frequency permutation arrays, hypercubes and Costas arrays, but we do not cover here.

An Orthogonal Array (OA) of strength $t$ on $v$ symbols is an array with the property that, for every $t$-combination of column vectors, every one of the possible $v^t$ $t$-tuples of symbols appears as a row ``exactly'' once in the subarray defined by these column vectors. OAs have been applied in coding theory and in cryptography. They are equivalent to MDS (maximum distance separable) codes where the strength of the OA is closely related to the minimum distance of the code. OAs are also closely related to secret sharing in cryptography. An Ordered Orthogonal Arrays (OOA) is a generalization of OAs where the coverage property applies to some selected columns of the array. Similarly, a Covering Array of strength $t$ on $v$ symbols is an array with the property that, for every $t$-combination of column vectors, every one of the possible $v^t$ $t$-tuples of symbols appears as a row ``at least'' once in the subarray defined by these column vectors. Covering arrays are used to reduce the number of tests in application areas such as software testing and group testing.

A common theme on several recent constructions of these arrays is the use of linear feedback shift register (LFSR) sequences and finite fields. Arrays whose rows are cyclic shifts of a sequence over a finite field possess many combinatorial properties. They have been used to build arrays attaining a high number of $t$-subsets of columns with the desired ``coverage property''. We provide examples of applications of these combinatorial arrays.