Gold code
A Gold code, also known as a Gold sequence, is a binary pseudorandom sequence of length $2^r - 1 (where r is a positive integer), constructed as the modulo-2 sum (XOR) of two maximal-length sequences (m-sequences) generated by linear feedback shift registers (LFSRs) using a "preferred pair" of primitive polynomials of degree r.[1][2] These sequences, first introduced by Robert Gold in 1967, possess ideal two-level autocorrelation—equal to $2^r - 1 at zero shift and -1 at all nonzero shifts—and bounded cross-correlation between distinct sequences in the set, with a maximum magnitude of approximately $2^{(r+1)/2} + 1.[1] This combination of properties makes Gold codes particularly valuable for applications requiring reliable signal detection amid interference, such as code-division multiple access (CDMA) systems and global positioning system (GPS) signals.[1] Gold codes are generated efficiently using pairs of LFSRs with carefully selected tap configurations to ensure the preferred pair condition, which guarantees the desired correlation bounds; for example, when r is odd, the decimation factor e satisfies \gcd(e, r) = 1, and the pair polynomials produce $2^r + 1 distinct sequences forming a large family with uniformly low cross-correlations.[2] From a coding theory perspective, each Gold sequence corresponds to a codeword in a cyclic linear code of length n = 2^r - 1 and dimension k = 2r, with the code generated by the product of the two primitive polynomials and exhibiting a minimum distance that varies with r (e.g., no codewords of weight less than 5 when r is odd).[2] The construction allows for the creation of extensive sets of nearly orthogonal sequences—up to $2^r + 1 in size—far larger than what single m-sequences can provide, enabling multiple users or signals to share the same bandwidth without significant mutual interference. These sequences have become foundational in modern telecommunications and navigation technologies due to their balance of length, randomness-like statistical properties, and computational simplicity in hardware implementation via shift registers.[1] In GPS, for instance, Gold codes of length 1,023 bits (with r = 10) are modulated onto carrier signals at 1.575 GHz to enable precise pseudoranging and anti-jamming resilience, while in CDMA systems such as cdmaOne (IS-95), Gold codes facilitate user separation in multi-access environments.[1] Ongoing research continues to explore their use in advanced areas such as iterative decoding for error correction and radar signal processing, leveraging their structured yet pseudorandom nature.[2]Background Concepts
Linear Feedback Shift Registers
A linear feedback shift register (LFSR) is a type of shift register that incorporates feedback by computing the input bit as a linear combination, modulo 2, of its previous state bits. This linear combination is typically performed using exclusive-OR (XOR) operations on selected bits from the register's stages.[3] The mechanism produces pseudorandom binary sequences and forms the basis for generating sequences used in applications like coding and synchronization.[4] The basic structure of an LFSR consists of an n-stage binary shift register, where each stage holds a bit (0 or 1), and feedback taps are defined by the coefficients of a characteristic polynomial of degree n over the finite field GF(2). The polynomial p(x) = x^n + c_{n-1} x^{n-1} + \cdots + c_1 x + c_0, with c_i \in \{0, 1\}, determines which stages are XORed to produce the feedback bit. In the common Fibonacci configuration, the register shifts right on each clock cycle, the output is taken from the least significant bit (LSB), and the feedback bit—computed as \bigoplus_{i=0}^{n-1} c_i s_i—is inserted into the most significant bit (MSB) position.[4][5] In operation, the LFSR is initialized with a non-all-zero state vector to avoid the trivial constant-zero sequence. Upon each clock pulse, the bits shift (right in Fibonacci LFSRs), the feedback bit is calculated from the current state using the polynomial taps, and it replaces the bit shifted out from the opposite end. The sequence output is usually the bit shifted out or a specific stage, such as the LSB. This process repeats deterministically, cycling through states based on the polynomial's properties.[4][5] For a simple illustrative example, consider a 3-stage LFSR with characteristic polynomial x^3 + x^2 + 1, corresponding to feedback taps on the LSB (s_0) and MSB (s_2) (XOR of those bits). Assuming a right-shifting Fibonacci setup with states denoted s_2 s_1 s_0 (MSB to LSB), starting from initial state "111": the transitions are as follows (feedback = s_2 XOR s_0; output = old s_0):- Clock 1: Feedback = 1 XOR 1 = 0; shift to "011" (output: 1)
- Clock 2: Feedback = 0 XOR 1 = 1; shift to "101" (output: 1)
- Clock 3: Feedback = 1 XOR 1 = 0; shift to "010" (output: 1)
- Clock 4: Feedback = 0 XOR 0 = 0; shift to "001" (output: 0)
- Clock 5: Feedback = 0 XOR 1 = 1; shift to "100" (output: 1)
- Clock 6: Feedback = 1 XOR 0 = 1; shift to "110" (output: 0)
- Clock 7: Feedback = 1 XOR 0 = 1; shift to "111" (output: 0)