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$

! The answer by @cbos is correct in spirit but wrong in its details.

In an answer on crypto.SE, I wrote

"The Berlekamp-Massey algorithm is an iterative algorithm that solves the following problem.

Given a sequence $s_0, s_1, s_2, \ldots$ of elements of a field, find the shortest linear feedback shift register (LFSR) that generates this sequence.

! Here, LFSR is a linear array of $n$ elements with initial value $$(s_0, \quad s_1,\quad \ldots, \quad s_{n-2}, \quad s_{n-1})$$ and successive values $$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\\ \downarrow\\ (s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\\ \downarrow\\ (s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\\ \downarrow\\ \cdots \quad \cdots$$ where the array contents shift leftwards at each step (clock cycle) so that the field elements falling off the left end (the LFSR output) are the given sequence, while the field elements shown as entering the LFSR on the right* are being computed as a linear combination of the LFSR contents at the previous step. In particular, for $i \geq 0$, the state transition can be expressed as $$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\\ \downarrow\\ \biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad \sum_{j=0}^{n-1}c_{n-j} s_{i+j}\biggr),$$ that is, the linear combination $c_ns_i + c_{n-1}s_{i+1} + \cdots + c_1s_{i+n-1}$ of previous LFSR contents is being fed back into the right end of the LFSR as $s_{n+i}$ (and hence the name linear feedback shift register).

As mentioned previously, the Berlekamp-Massey algorithm finds the shortest LFSR that generates the given sequence meaning it figures out the values of the $c_i$ elements. The iterative process consists of finding the shortest LFSR that generates the first $t$ elements $s_0, s_1, \ldots s_{t-1}$ and checking if the LFSR finds $s_t$ correctly. If so, $s_{t+1}$ is checked, while if not, the $c_i$'s are updated so that the revised LFSR generates $s_t$. If the sequence was indeed created by a $n$-stage LFSR as described above, the Berlekamp-Massey algorithm finds all $n$ coefficients $c_i$ after examining $s_0, s_1, \ldots, s_{2n-1}$. From this point onwards, the Berlekamp-Massey algorithm can continue checking the rest of the sequence (if so desired) but does not need to update the $c_i$'s because each check of the next symbol simply reports back that everything is OK."

Ignoring the sheer backwardness of the answer above as a trivial detail that can be fixed by standing on one's head, the shortest (single) LFSR that will generate the Gold sequences shown in Dan Boschen's question is of length 20 and its feedback polynomial (which is the product of the two feedback polynomials shown) is of degree 20. As such, we need $\mathbf{40}$ bits of the Gold sequence to determine the coefficients of this degree-$20$ polynomial, not the $21$ noted in cbos's answer. We don't get the two LFSRs shown in Dan Boschen's question but rather a single LFSR that is twice as long, and its initial loading is the first $20$ bits of the Gold sequence.

| improve this answer | |
$\endgroup$
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.

| improve this answer | |
$\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
  • $\begingroup$ This answer is correct in spirit but wrong in its details. $\endgroup$ – Dilip Sarwate Apr 28 at 21:08

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.