Gold Codes

Gold Codes are a class of binary sequences used extensively in spread spectrum and code-division multiple access communications systems. They are constructed by the modulo-2 addition of two specific maximum length sequences generated by linear-feedback shift registers. Named for their inventor, Robert Gold, who published their properties in 1967, these sequences are prized for their well-controlled cross-correlation and autocorrelation properties, which are critical for allowing multiple transmitters to share the same frequency band with minimal interference.

Definition and basic properties

A set is defined by selecting a pair of preferred pair maximum length sequences of equal length. These sequences, often denoted *m*-sequences, are generated using linear-feedback shift registers with primitive polynomials. The complete family includes the two original *m*-sequences and the modulo-2 sums of one sequence with cyclically shifted versions of the other. For sequences of length \(L = 2^n - 1\), where \(n\) is the register length and is not divisible by 4, a full set contains \(L + 2\) sequences. This construction ensures that every sequence in the set has a three-valued cross-correlation function, a property rigorously proven by Robert Gold in his seminal work. The mathematical foundation relies on concepts from Galois field theory, particularly operations within \(\mathrm{GF}(2^n)\).

Generation and structure

Generation is typically implemented in hardware using two linear-feedback shift registers configured with specific feedback tap positions corresponding to a preferred pair of primitive polynomials. The outputs of these two shift registers are combined using an XOR gate to produce a single output sequence. The initial state of the registers, excluding the all-zero state, determines which specific sequence from the set is produced. The structure can also be understood algebraically by representing sequences as traces of powers of a primitive element in a Galois field. This algebraic perspective, explored by researchers like James Massey and Solomon W. Golomb, facilitates the analysis of their periodic properties and equivalence to certain Kasami sequences under specific parameters.

Correlation properties

The defining characteristic is their bounded three-valued cross-correlation. For any two distinct sequences, \(x\) and \(y\), in a set, the periodic cross-correlation \(R_{xy}(\tau)\) takes on only the values \(\{-1, -t(n), t(n)-2\}\), where \(t(n) = 1 + 2^{\lfloor (n+2)/2 \rfloor}\). This bound is significantly lower than the maximum cross-correlation between arbitrary maximum length sequences, making them superior for multiple-access applications. Their autocorrelation function is also nearly ideal, with a sharp peak at zero shift and a low, uniform sidelobe level, which is crucial for reliable synchronization and signal acquisition in systems like the Global Positioning System. These properties were central to their adoption in major standards such as the IS-95 cellular network.

Applications

Primary application is in direct-sequence spread spectrum systems, where they serve as spreading codes. They are famously employed in the Global Positioning System for the coarse/acquisition (C/A) code broadcast on the L1 frequency, allowing all GPS satellites to transmit on the same frequency with minimal mutual interference. They were also used in the IS-95 standard for cdmaOne digital cellular technology and in the UMTS standard for pilot channels. Their good correlation properties enable efficient code division multiple access, supporting numerous users simultaneously in communications networks operated by companies like Qualcomm. Other uses include radar systems and ranging applications where precise timing is derived from correlation peaks.

Comparison with other sequences

Compared to individual maximum length sequences, sets offer a much larger family of sequences with strictly bounded cross-correlation, whereas cross-correlation between two arbitrary *m*-sequences can be very high. They are often compared to Kasami sequences, which offer an even larger set size for a given length but with a slightly different correlation bound; the small set of Kasami sequences has optimal cross-correlation properties. Walsh codes, used in systems like IS-95 for orthogonal channelization, have zero cross-correlation when perfectly synchronized but are highly susceptible to multipath interference and require precise timing alignment. In contrast, sequences maintain their low correlation properties even under timing offsets, making them more robust for asynchronous environments, a key advantage highlighted in the work of Andrew Viterbi.