title: Non-binary linear feedback shift register
body: <p>I used the instructions on <a href="http://en.wikipedia.org/wiki/Linear_feedback_shift_register#Galois_LFSRs" rel="nofollow">Wikipedia</a> to write a Galois linear feedback shift register in Python:</p>
  
  <pre><code>def lfsr(coefficients, state):
      while 1:
          lsb = state.pop()
          state.insert(0, 0)
          if lsb:
              state = app(coefficients, state)
  
          yield lsb
  
  def app(coefficients, state):
      return [ (coefficients[i]^state[i]) for i in range(len(state)) ]
  
  L = lfsr([1,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1], [0]*15+[1])
  seq = [ str(L.next()) for i in range(2**16+16) ]
  </code></pre>
  
  <p>This works fine. What I would like to do now is write a generalised version that could handle Galois fields other than GF(2) but I don't understand the section about <a href="http://en.wikipedia.org/wiki/Linear_feedback_shift_register#Non-binary_Galois_LFSR" rel="nofollow">non-binary LFSRs</a>. This part doesn't make sense to me: "the feedback bit (output bit) is multiplied (modulo-q) by a q-ary value which is constant for each specific tap point." How can a single output bit be multiplied by values for each tap point?</p>
  
  <p>This is what I came up with but instead of giving a cyclic sequence, the output quickly deteriorates to all 0s:</p>
  
  <pre><code># Multiplication table for GF(4)
  mult_4 = [[0, 0, 0, 0],
            [0, 1, 2, 3],
            [0, 2, 3, 1],
            [0, 3, 1, 2]]
  
  def lfsr(coefficients, state):
      while 1:
          lsb = state.pop()
          state.insert(0, 0)
          state = app(coefficients, state)
  
          yield lsb
  
  def app(coefficients, state):
      return [ mult_4[coefficients[i]][state[i]] for i in range(len(state)) ]
  
  L = lfsr([ 1, 0, 0, 0, 1, 2, 3 ], [1]*6)
  seq = [ str(L.next()) for i in range(4**6+6) ]
  </code></pre>