Gold Sequences and m-Sequences
Gold Sequence
Gold sequence (or Gold code) is a type of pseudo-random binary sequence used in digital communications and signal processing, especially in spread-spectrum systems.
It belongs to a family of sequences known for:
- Good cross-correlation properties
- Predictable structure
- Easy hardware implementation
Basic Idea
- Generate two different maximal-length sequences (m-sequences) of the same length.
- Combine them using bitwise XOR (modulo-2 addition).
- Shift one sequence relative to the other to create multiple distinct sequences.
If each m-sequence has length:
$$ N = 2^n - 1 $$
then the Gold code family contains:
$$ N + 2 $$
different sequences.
Why They’re Important
1. Bounded Cross-Correlation
The cross-correlation between different sequences is small and limited to three values. This is critical in multi-user systems.
2. Good Auto-Correlation
Each sequence looks noise-like but still allows reliable synchronization.
3. Large Family Size
You get many distinct sequences of the same length.
Where They Are Used
1. CDMA (Code Division Multiple Access)
Used to assign unique spreading codes to users.
2. GPS Systems
The Global Positioning System uses Gold codes to uniquely identify satellites.
3. Spread Spectrum Communication
Especially Direct Sequence Spread Spectrum (DSSS) systems.
Mathematical Construction
Use two m-sequences:
$$ G_i(t) = A(t) \oplus B(t+i) $$
- A(t) and B(t) are m-sequences
- i is the shift
- ⊕ is XOR
m-Sequence (Maximal-Length Sequence)
An m-sequence is a pseudo-random binary sequence generated using a linear feedback shift register (LFSR).
Why "Maximal-Length"?
If an LFSR has n flip-flops, the maximum period is:
$$ N = 2^n - 1 $$
An m-sequence achieves this maximum period.
Generation Steps
- Use an n-stage LFSR
- Choose a primitive feedback polynomial
- Feed back selected taps using XOR
- Clock the register repeatedly
Example (3-stage LFSR)
$$ 2^3 - 1 = 7 $$
1 0 0 1 1 1 0 (repeats)
Key Properties
1. Periodicity
Repeats every $$ 2^n - 1 $$ bits.
2. Balance Property
- Number of 1’s = $$ 2^{n-1} $$
- Number of 0’s = $$ 2^{n-1} - 1 $$
3. Autocorrelation
Define:
$$ R(\tau) = \sum_{k=0}^{N-1} a(k)a(k+\tau) $$
Then:
$$ R(\tau) = \begin{cases} N & \tau = 0 \\ -1 & \tau \ne 0 \end{cases} $$
Finite Field Formulation
Let:
$$ \text{GF}(2^n) $$
be the finite field with \(2^n\) elements.
If \( \alpha \) is a primitive element:
$$ \alpha^{2^n - 1} = 1 $$
Define:
$$ s(k) = \text{Tr}(\alpha^k) $$
Where trace is:
$$ \text{Tr}(x) = x + x^2 + x^{2^2} + \dots + x^{2^{n-1}} $$
Gold Sequence Cross-Correlation
For preferred pairs:
$$ R_{ij}(\tau) \in \left\{ -1,\; -1 + 2^{\frac{n+1}{2}},\; -1 - 2^{\frac{n+1}{2}} \right\} $$
Bound:
$$ |R| \le 1 + 2^{\frac{n+1}{2}} $$
Summary
| Property | m-sequence | Gold sequence |
|---|---|---|
| Length | 2n − 1 | 2n − 1 |
| Family Size | 1 | ≈ 2n + 1 |
| Autocorrelation | Perfect (-1 off-peak) | Good |
| Cross-correlation | Poor | Bounded |
Summary
- m-sequence → optimal autocorrelation
- Gold sequence → good autocorrelation + bounded cross-correlation
- Both rely on primitive polynomials over GF(2)
- Both are generated using LFSRs