# Minimum Output Samples needed to crack a “Gold Code” Generator (Dual LFSR)

Below is an implementation of a "Gold Code" Generator formed by adding (in $GF(2)$) the outputs from two linear feedback shift registers (LFSRs). This generates a pseudo-random sequence and is similar to the C/A Code Generator used in GPS.

An LFSR operates by shifting the contents of its shift register right on each cycle and computing the new input on the left side through the $GF(2)$ addition of certain outputs based on its "generator polynomial".

Each LFSR generator, given that is uses a generator polynomial that supports a maximum length sequence (meaning the polynomial is "primitive") produces a pseudo-random sequence which does not repeat for $2^{10}-1 = 1023$ samples, or "chips". The combined output therefore also does not repeat for 1023 chips. The feedback taps in each LFSR are set by the specific generator polynomial used (as shown).

Assume a black box with a a similar Gold Code generator, using two 10th order LFSRs but with unknown and primitive generators, and we only have access to the output code in high SNR conditions. What is the minimum number of chips that we would need to observe in order to determine what the generator polynomials are (in other words, to determine what the feedback taps are)?

• @Dilip Sawarte- you deleted your comment which was a good answer but didn't add it to the answer section, why not? – Dan Boschen Jul 3 '16 at 17:26