Linear Feedback Shift Register (LFSR)

Two equivalent hardware architectures exist for implementing the same generator polynomial:

• Fibonacci (External Feedback): XOR gates are placed in the feedback path, combining selected tap outputs before feeding the first flip-flop. This introduces a single XOR gate delay in the critical path.
• Galois (Internal Feedback): XOR gates are placed between adjacent flip-flop stages, with the feedback signal routed in parallel. This architecture offers higher maximum clock speeds because the combinational logic delay is distributed across stages rather than concentrated in a single feedback loop.

Both configurations produce identical output sequences when initialized with the same seed and polynomial.

When the feedback polynomial is primitive, the LFSR generates an m-sequence with period 2^n - 1, where n is the number of flip-flop stages. Key properties include:

• Balance Property: The number of 1s exceeds the number of 0s by exactly one over a full period.
• Run Property: Half of all runs are length 1, one-quarter are length 2, one-eighth are length 3, and so on.
• Two-Level Autocorrelation: The periodic autocorrelation function is 2^n - 1 at zero shift and -1 at all other shifts, making m-sequences ideal for synchronization and ranging.

Example: A 10-stage LFSR with primitive polynomial x^10 + x^3 + 1 produces a sequence of length 1,023 chips.

The choice of feedback polynomial determines the sequence properties and must be selected carefully:

• Primitive Polynomials: Produce maximal-length sequences. For a given degree n, multiple primitive polynomials exist. Example: x^7 + x^3 + 1 is primitive for n=7.
• Non-Primitive Polynomials: Produce shorter, non-maximal periods that depend on the initial seed value.
• Irreducible but Non-Primitive: The period divides 2^n - 1 but does not equal it.

Tables of primitive polynomials are well-documented for degrees up to several hundred. The polynomial is typically expressed in octal or hexadecimal notation for compact representation in hardware specifications.

The initial state loaded into the flip-flops is called the seed or key. Critical considerations:

• All-Zero Lockup: If the LFSR ever enters the all-zero state, the feedback XOR produces zero, and the register remains permanently stuck. An m-sequence of length 2^n - 1 excludes the all-zero state by definition.
• Seed Sensitivity: Changing a single bit in the seed produces a time-shifted version of the same sequence, not a different sequence. This property is exploited in code phase acquisition.
• Cryptographic Weakness: Given only 2n consecutive output bits, the entire sequence and feedback polynomial can be reconstructed using the Berlekamp-Massey algorithm, making standalone LFSRs unsuitable for cryptographic applications without non-linear combining.

LFSRs serve multiple critical roles in DSSS and FHSS systems:

• Spreading Code Generation: The PN sequence directly modulates the data, spreading its bandwidth by the processing gain factor.
• Scrambling: Randomizing data streams to avoid long runs of identical bits that would impair clock recovery.
• Hop Pattern Generation: In FHSS, the LFSR output selects the next carrier frequency from a hop set.
• Gold Code Generation: Combining two synchronized m-sequence LFSRs produces a family of codes with bounded cross-correlation, essential for CDMA multi-user access.
• Built-In Self-Test (BIST): LFSRs generate exhaustive test patterns for digital circuit verification.

Non-cooperative receivers can exploit LFSR structure to recover spreading codes:

• Eigenanalysis Techniques: The repetition of the spreading code induces cyclostationarity. By computing the spectral correlation density or performing subspace decomposition on the covariance matrix, the chip rate and code period can be estimated.
• Delay-and-Multiply: A non-coherent method that multiplies the received signal by a delayed copy, producing a spectral line at the chip rate.
• Maximum Likelihood Sequence Estimation: Once the polynomial degree is estimated, MLSE can jointly recover the spreading sequence and data symbols.

These vulnerabilities drive the use of non-linear combining and dynamic code updates in LPI waveforms to defeat blind estimation.