Sequences and arrays with desirable correlation properties.
K. T. Arasu · 2011
Binary perfect sequences and their variations have applications in various areas such as signal processing, synchronizing and distance measuring radars. This survey discusses their p-ary analogs, other variations and related matters. Many new results are also presented. Introduction: In recent years there have been many publications on time-discrete one and twodimensional sequences and arrays with perfect autocorrelation functions. Such sequences find applications in signal processing and as aperture functions for electromagnetic and acoustic imaging. Applications of two-dimensional perfect binary arrays are found in 2-D synchronization (Hershey & Yarlagadda (1983)) and timefrequency coding (Golomb & Taylor (1982)). In his invited address at the 1991 British Combinatorial Conference, Golomb gave an excellent exposition on why “small correlations” of sequences and arrays are desirable in dealing with radar problems (Golomb (1991)). Some fundamental results on sequences with small correlations can be found in the excellent survey of Turyn (1968). As observed by Luke, Bomer and Antweiler (1989), higher dimensional arrays are used in channel coding and in cryptographic coding. Because of their applications to wide-band digital communications and to optical signal processing, perfect binary arrays and their related mathematical objects deserve further study. Sequences with ideal autocorrelation property have many applications in spread spectrum communication systems such as a code division multiple access (CDMA) system, which has been adopted as a standard for multiple access method in the mobile radio communication systems. Signal designs for CDMA systems have become interesting research topics in their application area. Other applications where sequence design is a more pressing issue include: radar and audio coding. (see Golomb and Gong (2005)) This paper surveys several related areas that pertain to sequences and arrays with good correlation properties. We confine our discussion only to the “periodic” case and the “autocorrelation” discussions. The “aperiodic” discussion will take us too far and we refer the reader to Jedwab (2008) and references therein for further study on that very useful topic. For the cross correlation issues, any search engine would yield dozens of resources – we give only two references (Hertel (2006) and Gologlu and Pott (2008)). Another intriguing related topic pertains to the study of the so-called “Balanced generalized weighing matrices”, for which we refer the reader to the excellent survey by Jungnickel and Kharaghani (2004). 1 Research supported in part by grants from AFOSR and NSF. In this survey, we shall discuss perfect sequences and perfect arrays (binary, ternary, quaternary, p-ary for any prime p) and certain variations of them. Excellent surveys and fundamental discussions on related topics can be found in Jungnickel and Pott (1999a, 1999b), Cai and Ding (2009), Xiang (1992), Xiang (2005), Jedwab (1992,2008), and Davis and Jedwab (1997); all of which also provide a wealth of references. In section 1, we discuss binary sequences with 2-level optimal autocorrelation values (all of whose out-of-phase values being the same). Section 2 will be devoted to the 3-level case for optimal binary sequences. Generalization to the multi-dimensional case will be the focus of study in section 3, where we also investigate the inclusion of zero to the binary alphabet set , terming the resulting arrays as “ternary”. These latter entities turn out to be equivalent to group weighing matrices. Section 4 will be devoted the “quaternary” case, primarily the 1and 2dimensional cases will be discussed. These will be equivalent to “complex Hadamard matrices” with a group action, which in turn give rise to a class of relative difference sets. Section 5 is a synopsis of the systematic study undertaken by Ma and Ng (2009) for the p-ary sequences (p any odd prime). Their terminology may slightly differ from what we shall use in section 6, wherein we study the 2-level p-ary case, primarily on the construction arena. Results of section 6 will serve as a preview of a rather long paper of Arasu, Dillon and Player (2010) which is nearing its completion. In the remainder of this section, we provide some basic definitions of some combinatorial objects that arise naturally from the sequences that we shall discuss in later sections. Let be a multiplicatively written abelian group of order . Let denote the group ring of over the field of complex numbers . A subset of is identified with the group ring element which is a formal sum of the elements of (i.e. with coefficients 0 and 1) and for an element of and integer denotes the image of under the group homomorphism to , extended linearly to all of ; A* would denote in which we also replace each coefficient of by its complex conjugate. Difference sets, perfect sequences and related objects are often studied using character theory. Let be the group of characters of (A homomorphism from a group to the field of complex numbers is called a character of ). The principal character of is defined as the homomorphism that maps each element of to 1. We shall denote the principal character by . The character homomorphism can be extended linearly to the group ring. We let the induced homomorphism from to also be denoted by . Definition : (Difference Set, abbr. DS) Let be an element of whose coefficients are from . is a difference set in if