Spread Spectrum via Linear Shift-Register Sequences

Ken Abend, PhD

Course Outline

1. Modulo two arithmetic
2. Shift-register generation of binary sequences
3. Maximal and non-maximal sequences
4. Fundamental properties of SRG sequences
5. Matrix formulation of simple linear shift registers
6. The number of maximal sequences
7. What connections result in maximal sequences
8. Pseudo-random properties of maximal sequences
9. Correlation and autocorrelation

Only short proofs and intuitive justifications are included in the text.  The Appendix, with long mathematical proofs, is not part of the course.

This course includes a multiple-choice quiz at the end, which is designed to enhance the understanding of the course materials.

Learning Objective

The purpose of this course is to impart an understanding of the generation and properties of pseudorandom digital sequences to electrical engineers.  Specific learning objectives are the understanding of:

• Desirable properties of digital codes;
• Generation of such codes;
• Characteristic polynomials;
• Necessary conditions for a maximal shift register sequence;
• Sufficient conditions for a maximal shift register sequence;
• Number of maximal sequences; and
• Radar range accuracy improvement using a maximal sequence.

Intended Audience

Electrical Engineers needing skills in digital communications and related fields.

Benefit for Attendee

Know how to generate spread spectrum waveforms for CDMA cellular communications or for secure or long-range data communications.

Course Introduction

Figure 1 shows two simple six stage shift registers.  Each stage is in one of two states denoted as 0 and 1.
A shift pulse applied to all stages causes the binary data to move one stage in the direction of the arrow.  In the first case, the period (also called the length of the sequence) is 6.  In the second case, with stages 5 and 6 tapped and summed in a modulo-two adder, the period or sequence length is 2⁶ - 1 = 63.  Each sextuple except 000000 appears exactly once.  (A run of six zeroes would produce an all zero sequence with a period of one.)

The data sequence that the GPS in your car receives from a satellite comes from a 10 stage shift register with a period of 2¹⁰ – 1 = 1,023.  Each satellite has a different set of taps and produces a different sequence. Similar operations apply to 3^rd generation cell phones and to guided missiles.  Our missiles receive data from 47 stage shift registers in the GPS satellites.

Figure 2 shows a simple shift register along with some of the terminology we will use in this course.  The output due to the initial state shown in the figure will be called the impulse response of the shift register.  Each stage may or may not be tapped.  Note that if the last stage is not tapped, it serves no purpose; it only adds a delay.  Therefore we will always assume that in an n-stage shift register, the n^th stage (the last stage) is always tapped.

Course Content

For this coruse, you are required to study Pages 1-43 of “Introduction to Linear Shift-Register Generated Sequences” by Birdsall and Ristenbatt [omitting Sections 3.4 and 3.5 (pp. 30-33) but adding Section 4.5 (pp. 53-56)].

Available at http://deepblue.lib.umich.edu/handle/2027.42/3614.

Course Summary

Spread spectrum modulation uses a transmission bandwidth many times greater than the information bandwidth.  Spreading factors and processing gains on the order of a million (60 dB) are common.  In this course we examine the properties of maximal sequences (of length 2ⁿ -1) and show how they allow improvements proportional to the spreading factor.  These improvements can be in interference suppression, position and velocity estimation, low detectability, and multiple accesses.  As a result of this course, the student will be able to calculate how may maximal sequences can be produced with a given length shift register and determine what stages to tap in order to produce a maximal sequence.

Related Links and References

The following reference books were used by the author in the preparation of this course:

Theodore G. Birdsall and Marlin P. Ristenbatt, Introduction to Linear Shift-Register Generated Sequences, Technical Report 90, Electronics Defense Group, Department of Electrical Engineering, The University of Michigan, November, 1958.  Available (free of charge) in PDF at the following URL: www.deepblue.lib.umich.edu/handle/2027.42/3614   (This is the textbook for the course; you may omit section 5 and Appendix A)
Solomon Golomb, Shift Register Sequences, second edition, Aegean Park Press, Laguna Hills, CA, 1982.

Andrew J. Viterbi, CDMA Principles of Spread Spectrum Communication, Addison Wesley, 1995.

Solomon Golomb and Guang Gong, Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar, Cambridge University Press, 2005.

Quiz

Once you finish studying the above course content, you need to take a quiz to obtain the PDH credits.

---

DISCLAIMER: The materials contained in the online course are not intended as a representation or warranty on the part of PDH Center or any other person/organization named herein. The materials are for general information only. They are not a substitute for competent professional advice. Application of this information to a specific project should be reviewed by a registered architect and/or professional engineer/surveyor. Anyone making use of the information set forth herein does so at their own risk and assumes any and all resulting liability arising therefrom.

---