EE 599 Signal Design for Good Correlation, Spring 2007

 

 


 Instructors:  Professors G. Gong and S.W. Golomb

 

Text:  Signal Design for Good Correlation, by S.W. Golomb and G. Gong, Cambridge University Press, 2005.

 

Prerequisite:  Any one of EE-564a, EE-565a, EE-568a, or EE-595.

 

Meeting times:  Tuesdays, 6:00 – 8:30 pm, 3 units.

 

Room: KAP 165.

 

Course grade based on:      Weekly HW          10%

                                             Midterm                35%

                                             Final Exam            55%

 

 

Course Description.  Starting with the basic principles of how correlation is used to distinguish among members of a set of signals used in communication, and among different shifts of the same signal for applications to radar and sonar, the course then proceeds in two parallel directions. One direction is the derivation of the families of signals, and in particular, sequences, that have the best correlation properties for different applications. The other direction is a description of the applications themselves, and how the signals are used in them to best effect.

 

Course Outline

 

  1. Introductions to signal design for correlations for wireless communications, cryptography and radar. (Slides)
  2. Finite Fields: group structure, finite group, order, finite fields GF(p) and GF(2n), minimal polynomial, subfield, and trace function. (Slides)
  3. Linear Feedback Shift Registers: nonlinear and linear feedback shift registers, minimal polynomials, periods, trace representation, decimations and decomposition of LFSRs. (Slides)
  4. Randomness Properties of Sequences and m-Sequences: randomness criteria, randomness and interleaved structure of m-sequences, trinomial property, constant-on-cosets property, Fourier transforms and linear spans of periodic sequences. (Slides)
  5. Two-Level Autocorrelation Binary Sequences and Cyclic Difference Sets: cyclic Hadamard difference sets, a 1-1 correspondence, Fourier spectra of 2-level autocorrelation sequences.
  6. Hadamard Designs and Cyclic Hadamard Sequences: m-sequences, quadratic residue sequences, GMW sequences, multiple trace term sequences, and WG sequences. Case study: examples of orthogonal codes. Applications in CDMA Systems I. (Slides)
  7. Low Crosscorrelation Signal Sets: Gold-pair sequences, Kasami sequences, interleaved sequences,  bent function sequences, and Z4 sequences. Case study:  signal sets for 3G. Applications in CDMA Systems II. (Slides: part1, part2)
  8. Pseudo-random Sequence (Number) Generators: filtering generators, combinatorial function generators, clock-control generators, and shrinking generators. (Slides)
  9. Applications to Radar, Sonar and Synchronization: signal design for pulse radar, and optimal rulers, generalized barker sequences and polyphase sequences, impulse-equivalent pulse trains, and perfect circular rulers, costas arrays and Tuscan squares. (Slides)

10.    Applications to Symmetric Cryptography: stream cipher design, one-time-pad, examples of stream ciphers (A5 and W7), and stream cipher candidates from ECRYPT (WG). (Slides)

 

 

Supplemental Materials and References

 

·       Tables for Computations in Small Finite Fields

·       Berlekamp-Massey Algorithm in c Program

·       Notes on Berlekamp-Massey Algorithm