2
$\begingroup$

Please preface your answer with spoiler notation by typing the following two characters first ">!"

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".

enter image description here

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)?

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

For a single polynomial generator, the minimum number of samples is 2N+1 where N is the order of the polynomial. If noise free this would result in 10 equations with 10 unknowns, sufficient to solve the linear equations involved. For the case of the Gold Code given above, the generator shown could also be done with a single polynomial which is determined by convolving the two polynomials shown, resuting in a 20th order polynomial (it just would no longer be irreducible and primitive, but would still generate each Gold Code by changing the initial state to 20 consecutive values that are in the sequence desired). Therefore the answer is 21 chips, and the Berleykamp-Massey algorithm can quickly decipher the generator polynomial that could recreate every Gold code.

$\endgroup$
  • $\begingroup$ Berlekamp-Massey will handle Gold Codes as inputs? Huh. I thought it was limited to m-sequences. $\endgroup$ – Jason S Aug 15 '17 at 19:09
  • $\begingroup$ @JasonS I thought that the Berlekamp-Massey algorithm would solve any linear feedback shift register polynomial, it needn't be a maximum length sequence? The answer is still correct in that it is 21 chips to the extent we can solve the 10x10 matrix in GF(2) $\endgroup$ – Dan Boschen Aug 15 '17 at 23:11
  • $\begingroup$ oh, I see, it will spit out the polynomial that is the product of the two LFSR polynomials. $\endgroup$ – Jason S Aug 16 '17 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.