1
$\begingroup$

I'm trying to generate a de Bruijn sequence in GF(4) of order $k$ using the recursive formula from this paper:

$s_i = \theta_{k-1}s_{i-1} + \theta_{k-2}s_{i-2} + \dots + \theta_{0}s_{i-1k}$

where $\sum_{i = 0}^{k-1}{\theta_i x^i}$ is a primitive polynomial.

I came up with a short implementation in Python and as far as I can tell it reflects the model (it works if I generate sequences over GF(2)) but it doesn't generate the desired sequence correctly. What I found a bit suspicious is that the polynomial has degree $k-1$, not $k$ and that $\theta_0$ is multiplied by a sequence element. Should this method work also on GF(4)?

  • 0
    you're absolutely right, there is an error in the formula, the first term is missing.2012-11-18

0 Answers 0