×

Signal design for good correlation. For wireless communication, cryptography, and radar. (English) Zbl 1097.94015

Cambridge: Cambridge University Press (ISBN 0-521-82104-5/hbk). xviii, 438 p. (2005).
This book provides a comprehensive theoretical and methodological background for designing digital signal sets with optimized correlation properties. The book is outstanding in its field. It is written by famous researcher Solomon Golomb with cooperation of Guang Gong, author of many important papers. The aim of the book is to present the necessary background to explain how signals with appropriate correlation constraints are generated. All the known methods, also recently discovered, to obtain balanced binary sequences with two-valued autocorrelation, are described.
The book consists of 12 chapters. First two chapters are of introductory nature. What is correlation, autocorrelation and crosscorrelation is explained and basic notions are introduced. Application of correlation to the communication is discussed. Signal codes like orthogonal, biorthogonal and simplex codes and the role of Hadamard matrices in code construction is presented. Chapter 3 deals with fundamentals of algebraic structures – groups, rings, fields and polynomials. Finite fields are used in most of the known constructions of pseudorandom sequences and analysis of periods, correlations, and linear spans of linear feedback shift register (LFSR) sequences. Finite fields and their properties that are frequently used in sequence design and cryptography are described. Methods for finding minimal polynomials are presented. Trace functions are discussed. Chapter 4 is devoted to linear feedback shift registers (LFSR) sequences. LFSR sequences have been defined from the point of view of polynomial rings. Minimal polynomials and periods of LFSR sequences are characterized. The decomposition of LFSR sequences is presented. Matrix and trace representations of LFSR sequences are characterized. Chapter 5 discusses the randomness of sequences whose elements are taken from a finite field. Three randomness postulates for binary sequences have been earlier formulated by Golomb – balance property, run property and the (ideal) two-level autocorrelation property. In this chapter m-sequences are exhaustively studied (interleaved structures of \(m\)-sequences and the subfield decomposition of \(m\)-sequences, shift-and-add property, constant-on-cosets property, 2-tuple balance property). Chapter 6 is devoted to transforms of sequences and functions – discrete Fourier transform, Hadamard transform and convolution transform. The Fourier transform serves as a bridge for a connection between sequences and functions. Newly discovered binary sequences with 2-level autocorrelation functions were proved in terms of their Hadamard transforms.
Chapter 7 is related to cyclic difference sets and binary sequences with 2-level autocorrelation. Chapters 8 and 9 emphasize the role of cyclic Hadamard sequences. Binary sequences of period \(N\) with 2-level autocorrelation have many important applications in communications and cryptology. There are many constructions for binary 2-level autocorrelation sequences. They are described in these chapters. Of special importance are new constructions which are developed after 1997 – hyper-oval constructions, Kasami power construction and iterative decimation-Hadamard transform. Chapter 10 deals with signal sets with low crosscorrelation. Constructions for signal sets with low crosscorrelation include three classic methods: Gold-pair construction, the Kasami (small) set construction, and bent function signal set construction. Chapter 11 discusses correlation of Boolean functions. Such properties as nonlinearity, correlation immunity and resiliency, and Walsh transform properties are related to cryptographic characteristics of boolean functions. Chapter 12 summarize remarks about application to radar, sonar, synchronization and CDMA. The generation of pulse patterns with good correlation properties is described.
This book seems to be carefully edited, however minor additions, corrections and updating of the material are planned to be put on the website (please note that the correct URL is http://calliope.uwaterloo.ca/ ggong/GolombGongBook/GolombGongBook.htm).
To summarize, this handbook is strongly recommended for advanced and graduate university courses in signal design for digital communication. Its value is enhanced by exercises for students after each chapter and extensive bibliography. The book may also serve well as reference background for professionals.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
62H20 Measures of association (correlation, canonical correlation, etc.)
94-02 Research exposition (monographs, survey articles) pertaining to information and communication theory
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
PDFBibTeX XMLCite