I would like to find a preferred pair of $m$-sequence of degree 34 (not a multiple of 4) for Gold code. However, I am lost when I am checking William Wesley Peterson's table in his Error-correcting Codes, Appendix C

enter image description here

I tried first fix the first entry for my first $m$-sequence. To find the other sequence, since $n = 34$, it is even, then $$2^{\left(\frac{34+2}{2}\right)}+1 = 2^{18} + 1$$ or $$2^{\left(\frac{34-2}{2}\right)}+1 = 2^{16} + 1$$

But either number is not mapped to any entry in the table that I cannot proceed to find the other $m$-sequence. I assume I should find the other $m$-sequence which has the equivalent root of $$r^{\left(2^{\left(\frac{34+2}{2}\right)}+1\right)}$$ or $$r^{\left(2^{\left(\frac{34-2}{2}\right)}+1\right)}$$

To elaborate, the following is what I consider as an easy case of prefered pair of Gold Sequence using Peterson's table and Gold's theorem, presented in this paper. I have no access to Dixon's book therefore I don't know what the correct procedure is.

enter image description here

The author applying the equation in the conjugate form of Gold's theorem in Gold's paper

  • $\begingroup$ What do you mean with "this number is way too large"? Could you elaborate? $\endgroup$ Commented Nov 11, 2020 at 10:34
  • 1
    $\begingroup$ @MarcusMüller I think what the OP means is that he needs an entry of the form 65537 20135723$\cdots$ but the table only goes up to 21 and then $3$ selected entries none if which begins 65537. $\endgroup$ Commented Nov 13, 2020 at 1:45

1 Answer 1


Printed tables of irreducible polynomials of large degrees are usually incomplete because there are so many of them! What one can do is use various tricks of the trade to figure out a set of $68 = 2\times 34$ consecutive bits of one m-sequence from the other m-sequence (with known generator polynomial as taken from the Peterson and Weldon table) and then run the Berlekamp-Massey algorithm on these consecutive bits to get the shortest shift register that generates the desired m-sequence.

If ${\bf s} = s_0, s_1, s_2, \ldots $ is one of the m-sequences, then the other m-sequence ${\bf t} = t_0, t_1, t_2, \ldots $ is related to ${\bf s}$ via $t_i = s_{qi}$ where $q = 2^{16}+1 = 65,537$. See the paper "Cross-correlation properties of pseudorandom and related sequences," Proc. IEEE, vol.68, pp.593-619, May 1980 (unfortunately behind IEEE's paywall, but copies can be found in the Internet) if you are unfamiliar with this idea. So, we crank up the LFSR that generates ${\bf s}$ and run it to produce the sequence ${\bf s}$, recording $$t_0 = s_0, ~~t_1 = s_{65537},~~ t_2 = s_{131074},~~ \cdots, t_{67} = s_{4390979}.$$ Once upon a time, cranking out 4 million+ bits would have taken some effort, but these days, it's no big deal.

What next? Well, the Berlekamp-Massey algorithm can be viewed as a shift-register synthesis algorithm: it finds the shortest LFSR that can generate any given sequence. Thus, applying the Berlekamp-Massey algorithm to the first $68$ bits of $\bf t$ which we have just found gives us the LFSR that generates the m-sequence $\bf t$, and away we go!!

  • $\begingroup$ That solves all my confusion...Thank you very much! $\endgroup$
    – Eagle Shou
    Commented Nov 13, 2020 at 5:53
  • $\begingroup$ @EagleShou if it solves the confusion, then you might want to accept this (the checkmark next to the up/downvote triangles), so the question gets marked as answered :) $\endgroup$ Commented Nov 16, 2020 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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