A theory of two-dimensional linear recurring arrays

Abstract

In this paper, two-dimensional arrays of elements of an arbitrary finite field are examined, especially arrays having maximum-area matrices. We first define two-dimensional linear recurring arrays. In order to study the characteristics of two-dimensional linear recurring arrays, we also define two-dimensional linear cyclic codes. A systematic method of constructing two-dimensional linear recurring arrays having maximum-area matrices is given using the theory of two-dimensional cyclic codes. These arrays, here called <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\gamma \beta</tex> -arrays, may be said to be two-dimensional analogs of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</tex> -sequences. A <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\gamma \beta</tex> -array of area <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N_x \times N_y</tex> exists over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">GF(q)</tex> if and only if <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N_x N_y</tex> is equal to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q^N _ 1</tex> for some positive integer <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</tex> . Many interesting characteristics of the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\gamma \beta</tex> -array, such as the properties of its autocorrelation function and the properties of the characteristic arrays, are deduced and explained.