1

I need a reference for the fact that each LFSR with XOR operation has a period of $2^m-1$ excluding zero state and every LFSR with XNOR operations has the same period excluding all ones state.

I want to cite it when I'm writing about the usage of LFSR in a paper, I've found some references but they avoid a proof and all of them include only the case of XOR operations.

Since LFSRs are mostly used in signal processing I ask it here.

Edit: I know that the feedback polynomial should be primitive.

SMA.D
  • 111
  • 5
  • L in LFSR means Linear and so an LFSR with XNOR operation is, by definition, not an L FSR but merely an FSR/ Also, as Nir Regev's answer points out, your "fact" for which you need a reference is not true. – Dilip Sarwate Oct 18 '15 at 18:07
  • @DilipSarwate I assume that the feedback polynomial is primitive, For XNOR operation I've found Xilinx, however I need a reference for it – SMA.D Oct 18 '15 at 18:14

1 Answers1

3

Not all LFSRs have the property of maximum cycle length. In fact, those who do have this property are based on a primitive polynomial of order n. It is a basic property of the extension field $GF(2^n)$ which is "spanned" by this primitive polynomial. The LFSR merely iterates through all of the powers of the polynomial primitive root.

Open a book on algebraic structures and cite the relevant part.

Dr. Nir Regev
  • 618
  • 5
  • 9
  • In all of the books I've found yet, Everything is proved for primitive LFSRs with XOR operations, I couldn't find a proof for XNOR. Xilinx suggests XNOR operations in its documentation. – SMA.D Oct 18 '15 at 18:43
  • XOR + negation = XNOR. negation over GF(2) is + 1. i.e. over GF(2) XOR(a,b) = a+b and XNOR(a,b) = a+b+1 (remember that everything is modulo 2), so basically the all ones state negated will turn into the all zeros state which is not a valid state for LFSR. In any case, it'll not change the cycle period which will stay $2^n-1$ – Dr. Nir Regev Oct 18 '15 at 19:58
  • You are true. Do you think that this fact is somehow obvious and doesn't need any citations? – SMA.D Oct 18 '15 at 20:14
  • Thank you. Also it would be very nice if you mention a good reference book on the subject, I searched google books but most of the books didn't have a robust proof. – SMA.D Oct 18 '15 at 20:19