Affine Feedback Shift Register

Posted on June 29, 2011 by webmaster

Several previous articles have focused on linear feedback shift registers.  These are very simple circuits which are very often used for generating “maximal” length sequences, which are sequences of all non-zero values of N bits.  “Maximal” does not include the value of 0.  This article discusses some alternative implementations of these simple circuits.

The linear feedback shift register can be seen as a solution to the recursive, linear equation y_{n} = A y_{n-1} Where the transformation matrix has the property A^{2^{N}-1} = I.  Likewise, all math is throughout this article is done in GF2 for scalars and GF2[x] for vectors.

This article focuses on the affine case, where y_{n} = A y_{n-1} + b. In this case, b is a vector of length N (in GF2[x]) that is added to the result of the LFSR shift operator, A.  For a galois field, it is equivalent to inverting some elements, or converting some XOR’s into XNOR’s.  This article focuses first on formulations of the A matrix for the galois implementation of an LFSR.

The following will happen if y_0 = u for some non-zero, but otherwise unspecified initial condition:

  • y_1 = A u + b
  • y_2 = A^2 u + A b + b

Which will continue until:

  • y_{2^N-2} = A^{2^N-2} u + \sum_{k=0}^{2^N-3}A^k b
  • y_{2^N-1} = A^{2^N-1} u + \sum_{k=0}^{2^N-2}A^k b

At this point, two thing will happen, at least for GF2:

  • y_{2^N-1} = u

The first thing that occurs is that A^{2^N-1} = I and thus the initial vector is seen again.  This is the first term of the equation.

The second is that the summation equates to zero.  To see why this is the case, consider the sum of all vectors of length N, as done in GF2[x], which is equal to zero.  Likewise the sum of all non-zero vectors of length N, again in GF2[x], is 0.  Recall the addition in GF2[x] is simply the element-wise XOR operator.  The summation term for y_{n-1} actually includes every non-zero element of length N in GF2[x].

As an example, consider the galois field generated by \alpha^3 = \alpha^2 + 1, with y_0 = u = 1 and b = \alpha.  The LFSR operation is defined by the A matrix, [1,1,0; 0,0,1; 1,00].  (My LaTeX-math plugin seems to be have some issues with matrices at the moment.)

This proceeds as follows:

  1. y_0 = 1
  2. y_1 = \alpha+\alpha = 0
  3. y_2 = \alpha
  4. y_3 = \alpha^2 + \alpha
  5. y_4 = \alpha + 1
  6. y_5 = \alpha^2
  7. y_6 = \alpha^2 + \alpha + 1
  8. y_7 = 1 = y_0

As before, there must still be a degenerate case.  Notice that if u = 0, the above still iterates through 2^{N}-1 elements.  In fact u_{deg} = A u_{deg} + b is this case.  In the above, this is u_{deg} = \alpha^2 + 1.  This can be solved in general, if desired:
A u_{deg} + u_{deg} = b
u_{deg} = (A+I)^{-1} b

The above analysis again is based on the galois implementation of the LFSR which was then augmented with inverters/xnors to perform the above, affine operation.  Because LFSR’s only use even numbers of taps, selecting b=1 and the appropriate matrix for A will also generate a fibbonacci-style LFSR.  In this case, the additional XOR of a constant 1 would be the same as changing all of the XOR’s to XNOR’s.

However, the modified for of the galois-style LFSR presents an attractive alternative to either style.  Such an LFSR can be reset to 0’s or 1’s without locking up.  For this to work, the affine constant b must be neither 0 nor the connection polynomial.  This allows for the creation of a more robust LFSR.

// verilog
// N       = length of lfsr
// CPOLY   = connection polynomial
// AFCONST = constant.
always @ (posedge clk) begin
  s <= {s[N-2:0],s[N-1]}^(s[N-1]?CPOLY:0)^AFCONST;
end

-- VHDL
p_lfsr : process (Clk) is
begin
  if Clk'event and Clk = '1' then
    if s(s'high) = '1' then
      s <= (s(s'high-1 downto 0) & s(s'high))
           xor CPOLY xor AFCONST;
    else
      s <= (s(s'high-1 downto 0) & s(s'high)) xor AFCONST;
    end if;
  end if;
end process;
This entry was posted in Math. Bookmark the permalink.

Comments are closed.