Gold code generator — preferred pairs, correlation, and CDMA use

In one sentence: a Gold code is the XOR of two m-sequences that form a preferred pair. With $n$-stage shift registers you get $2^n + 1$ codes of length $2^n – 1$, and any two of them cross-correlate to only three values.

That last property is the whole reason Gold codes exist. GPS satellites use them, 3G cells use them, and 5G still uses a Gold generator for scrambling. In this article I’ll show you how the generator works, which pairs of polynomials actually qualify as “preferred” (with a table I’ve re-checked by brute force), and how to generate and test Gold codes yourself in Python and Matlab. At the end we’ll build the real GPS C/A code and check it against the official spec.

Why not just use m-sequences?

If you’ve read my post on maximum-length sequences, you know m-sequences have a beautiful autocorrelation: a spike of $N$ at zero lag and $-1$ everywhere else. That makes them great for finding timing.

The problem shows up when you need many users. Pick two different m-sequences of the same length and their cross-correlation can be surprisingly large. Worse, there just aren’t many m-sequences to go around. For $n = 7$ there are only 18 of them.

What we want is a big family of codes where every pair stays quiet at every lag. In 1967, Robert Gold showed how to build exactly that from two m-sequences.

How a Gold code generator works

You need two linear feedback shift registers (LFSRs) of the same length $n$. Each one generates an m-sequence. Their outputs are XORed chip by chip, and the result is a Gold code.

For the registers in Figure 1, each new bit is the XOR of the tapped stages:

$$a_i = a_{i-2} \oplus a_{i-5}, \quad b_i = b_{i-2} \oplus b_{i-3} \oplus b_{i-4} \oplus b_{i-5}.$$

Now fix sequence $a$ and slide sequence $b$ by $k$ chips. Writing $T^k b$ for “$b$ shifted by $k$”, each shift gives a new code:

$$g_k = a \oplus T^k b, \quad k = 0, 1, \dots, N-1.$$

Add the two parent m-sequences themselves and you have the complete Gold family:

$$\mathcal{G}(a, b) = \lbrace a,\; b,\; g_0,\; g_1,\; \dots,; g_{N-1} \rbrace , \qquad |\mathcal{G}| = N + 2 = 2^n + 1.$$

So two 5-stage registers give you 33 codes of length 31, and two 10-stage registers give you 1025 codes of length 1023. In hardware you don’t store any of them. You just load a different seed into LFSR 2.

A note on notation. I describe each register by its tap list. Taps $[5, 2]$ means stages 5 and 2 feed back, which corresponds to the polynomial $1 + x^2 + x^5$. Some books and tools write the same register as the reciprocal polynomial $1 + x^3 + x^5$. Both conventions are fine, but you must use the same one for both registers. Mixing them is the most common reason a “preferred pair” from a table refuses to work.

What makes a pair “preferred”?

Not every pair of m-sequences gives a good Gold family. The pair has to be preferred, which means its cross-correlation takes only these three values:

$$R_{ab}(\tau) \in \lbrace -1,; -t(n),; t(n) – 2 \rbrace ,$$

where

$$t(n) = \begin{cases} 1 + 2^{(n+1)/2}, & n \text{ odd} \cr 1 + 2^{(n+2)/2}, & n \text{ even} \end{cases}$$

and the correlation is the usual periodic one on $\pm 1$ chips ($0 \; to +1$, $1 \; to -1$):

$$R_{ab}(\tau) = \sum_{i=0}^{N-1} (1 – 2a_i)(1 – 2b_{i+\tau}).$$

Gold’s result is that if the parents are a preferred pair, every pair of codes in the family inherits the same three values. That’s the guarantee.

A few rules worth remembering:

• Odd $n$ is the best case. The peak $t(n)$ is as low as it can be for a family this size.
• $n equiv 2 pmod 4$ (6, 10, 14, …) still gives preferred pairs, with a slightly weaker bound.
• $n equiv 0 pmod 4$ (8, 12, 16, …) has no preferred pairs at all. I checked $n = 8$ by testing all 120 pairs of its 16 m-sequences; none of them are three-valued.

Verified table of preferred pairs

Updated October 2026. Every row below was verified by exhaustive search: I generated every primitive polynomial for each $n$, computed the full cross-correlation of every pair, and kept the pairs that give exactly three values. Thanks to reader David Skeet, who spotted that $[7, 3, 1]$ in the old table is not a primitive polynomial. The search also showed that the old $n = 10$ entries did not work, so they have been replaced.

$n$	Length $N$	Family size	Three values	Preferred pair (taps)
5	31	33	$-9, -1, 7$	$[5,2]$ and $[5,4,3,2]$
6	63	65	$-17, -1, 15$	$[6,1]$ and $[6,5,2,1]$
7	127	129	$-17, -1, 15$	$[7,3]$ and $[7,1]$
7	127	129	$-17, -1, 15$	$[7,3,2,1]$ and $[7,3]$
9	511	513	$-33, -1, 31$	$[9,4]$ and $[9,6,4,3]$
10	1023	1025	$-65, -1, 63$	$[10,3]$ and $[10,7,3,1]$
10	1023	1025	$-65, -1, 63$	$[10,3]$ and $[10,9,8,6,3,2]$ (GPS)
11	2047	2049	$-65, -1, 63$	$[11,2]$ and $[11,8,5,2]$

There are many more preferred pairs than this. For $n = 7$ my search found 90 of them, and for $n = 11$ it found 1936. The ones above are just the simplest to wire up.

Autocorrelation: the price you pay

Gold codes are not m-sequences, so they lose the perfect $-1$ autocorrelation. Off the main peak, a Gold code’s autocorrelation takes the same three values as its cross-correlation.

That’s the trade. You give up a little autocorrelation quality and, in return, get a large family with controlled cross-correlation. For multi-user systems that’s a very good deal, because cross-correlation is what sets the interference between users.

To see how good the deal is, compare against random codes. Figure 4 takes all 129 codes from one $n = 7$ Gold family, correlates every pair at every lag, and plots how often each value appears. It does the same for 129 random $pm 1$ codes of the same length.

In normalized terms, the worst-case cross-correlation of a Gold family with odd $n$ is

$$\frac{t(n)}{N} = \frac{1 + 2^{(n+1)/2}}{2^n – 1} \approx 2^{-(n-1)/2}.$$

For $n = 7$ that is $17/127 \approx 0.13$, and for $n = 11$ it drops to $65/2047 \approx 0.03$.

Hardware: a length-127 generator

In hardware, each box in the LFSR is a D flip-flop, all clocked together. For a length-127 Gold code you can use the preferred pair $[7, 3, 2, 1]$ and $[7, 3]$:

$$a_i = a_{i-1} \oplus a_{i-2} \oplus a_{i-3} \oplus a_{i-7}, \qquad b_i = b_{i-3} \oplus b_{i-7}.$$

That’s 14 flip-flops, four XOR gates for the feedback and one XOR at the output. Load a different seed into the second register and you get a different member of the 129-code family. No memory, no lookup table.

Python code: generate and test Gold codes

Here’s a compact generator. It builds the full family and checks that every pair stays within the three values.

import numpy as np

def mseq(taps, n):
    """m-sequence (0/1) from an n-stage Fibonacci LFSR with the given taps."""
    state = [1] * n
    out = []
    for _ in range(2**n - 1):
        out.append(state[-1])
        fb = 0
        for t in taps:
            fb ^= state[t - 1]
        state = [fb] + state[:-1]
    return np.array(out)

def gold_family(taps1, taps2, n):
    """All 2^n + 1 Gold codes from a preferred pair."""
    a, b = mseq(taps1, n), mseq(taps2, n)
    return [a, b] + [a ^ np.roll(b, -k) for k in range(2**n - 1)]

def xcorr(x, y):
    """Periodic cross-correlation of two 0/1 codes, mapped to +1/-1."""
    x, y = 1 - 2 * x, 1 - 2 * y
    return np.fft.ifft(np.conj(np.fft.fft(x)) * np.fft.fft(y)).real.round().astype(int)

codes = gold_family([7, 3], [7, 1], 7)
values = set()
for i in range(len(codes)):
    for j in range(i + 1, len(codes)):
        values |= set(xcorr(codes[i], codes[j]).tolist())
print(len(codes), "codes, cross-correlation values:", sorted(values))
# 129 codes, cross-correlation values: [-17, -1, 15]

Try swapping [7, 1] for [7, 4]. That pair is not preferred, and you’ll see the set of values blow up.

Matlab code

The same idea in Matlab, generating two Gold codes and printing their cross-correlation values:

n = 7;
a = mseq([3 7], n);
b = mseq([1 7], n);

k = 5;
g1 = xor(a, circshift(b, -k));
g2 = xor(a, circshift(b, -(k + 1)));

x = 1 - 2*g1;  y = 1 - 2*g2;
R = round(real(ifft(conj(fft(x)) .* fft(y))));
disp(unique(R))                  % -17  -1  15

function out = mseq(taps, n)
   state = ones(1, n);
   out = zeros(1, 2^n - 1);
   for i = 1:2^n - 1
      out(i) = state(n);
      fb = mod(sum(state(taps)), 2);
      state = [fb state(1:n-1)];
   end
end

If you have the Communications Toolbox, comm.GoldSequence does the same job. Just be careful with its polynomial convention when you copy pairs from a table.

Real example: the GPS C/A code

The GPS coarse/acquisition (C/A) code is a Gold code of length 1023, built from two 10-stage registers:

$$G_1(x) = 1 + x^3 + x^{10}, \qquad G_2(x) = 1 + x^2 + x^3 + x^6 + x^8 + x^9 + x^{10}.$$

Both registers start at all ones. GPS has one twist: instead of shifting $G_2$ by loading a different seed, each satellite XORs two stages of $G_2$ together (the “phase select”). By the shift-and-add property of m-sequences, that’s the same as a delayed copy of $G_2$, so the result is still a Gold code.

def gps_ca(s1, s2):
    """GPS C/A code (0/1, 1023 chips) for G2 phase-select stages s1, s2."""
    g1, g2, out = [1] * 10, [1] * 10, []
    for _ in range(1023):
        out.append(g1[9] ^ g2[s1 - 1] ^ g2[s2 - 1])
        f1 = g1[2] ^ g1[9]
        f2 = g2[1] ^ g2[2] ^ g2[5] ^ g2[7] ^ g2[8] ^ g2[9]
        g1, g2 = [f1] + g1[:-1], [f2] + g2[:-1]
    return np.array(out)

for prn, taps in {1: (2, 6), 2: (3, 7), 3: (4, 8), 4: (5, 9)}.items():
    first10 = "".join(map(str, gps_ca(*taps)[:10]))
    print(prn, first10, oct(int(first10, 2))[2:])

The output matches the first-10-chip values published in the GPS interface specification (IS-GPS-200):

PRN	G2 stages	First 10 chips	Octal
1	2, 6	1100100000	1440
2	3, 7	1110010000	1620
3	4, 8	1111001000	1710
4	5, 9	1111100100	1744

That’s a nice sanity check: if your generator reproduces these octal values, it’s wired correctly.

Where else Gold codes are used

• GPS (above): one Gold code per satellite, so a receiver can tell 30+ satellites apart on the same frequency.
• 3G WCDMA: downlink scrambling uses Gold codes of length $2^{18} – 1$, truncated to one 10 ms frame (38,400 chips). Each cell gets one. The uplink uses a longer Gold code of length $2^{25} – 1$ for each phone.
• 5G NR: no CDMA, but the pseudo-random sequence $c(n)$ in TS 38.211 is a length-31 Gold sequence. It generates the scrambling bits for data channels and the DMRS and CSI-RS reference signals.

For how Gold codes fit alongside Walsh, OVSF and plain PN codes in a full CDMA system, see Spreading and Scrambling Codes in CDMA.

Gold vs m-sequence vs Kasami

	m-sequence	Gold	Kasami (small set)
Length	$2^n – 1$	$2^n – 1$	$2^n – 1$, $n$ even
Number of codes	a few	$2^n + 1$	$2^{n/2}$
Off-peak autocorrelation	always $-1$	three-valued	three-valued
Peak cross-correlation	can be large	$t(n)$	$1 + 2^{n/2}$

Kasami codes give you lower cross-correlation but far fewer codes. Gold codes sit in the middle: lots of codes, with a cross-correlation bound you can design around.

FAQ

Why must Gold codes be built from preferred pairs? Only preferred pairs guarantee the three-valued cross-correlation. An arbitrary pair of m-sequences can produce many more values with a higher peak (Figure 2), which defeats the point of using Gold codes.

How many Gold codes can I get from one pair? $2^n + 1$: the $2^n – 1$ shifted combinations plus the two parent m-sequences. Different preferred pairs give you different families.

What length are Gold codes? The same as the parent m-sequences, $N = 2^n – 1$. For GPS, $n = 10$ and $N = 1023$.

Why doesn’t a table pair work in my code? Almost always it’s the polynomial convention. Check whether your LFSR reads taps from the input end or the output end, and use the same convention for both registers.

Do Gold codes exist for $n = 8$? Not in the classic three-valued sense. Preferred pairs do not exist when $n$ is a multiple of 4.

Keep learning

• Maximum-length sequences (m-sequences): the building block of every Gold code
• Spreading and Scrambling Codes in CDMA: Walsh, PN, Gold, and OVSF
• Walsh–Hadamard codes — generate the matrix and simulate in Matlab
• Spread Spectrum Communications – Intro

Go further with the ebooks: the Digital Modulations ebooks include full Matlab/Python projects on spreading codes, correlation and BER. Compare all books.

References

1. R. Gold, “Optimal binary sequences for spread spectrum multiplexing,” IEEE Trans. Inf. Theory, vol. 13, no. 4, pp. 619–621, Oct. 1967.
2. D. V. Sarwate and M. B. Pursley, “Crosscorrelation properties of pseudorandom and related sequences,” Proceedings of the IEEE, vol. 68, no. 5, pp. 593–619, May 1980.
3. IS-GPS-200, Navstar GPS Space Segment / Navigation User Segment Interfaces.
4. 3GPP TS 25.213, Spreading and modulation (FDD).
5. 3GPP TS 38.211, NR; Physical channels and modulation, §5.2.1.