1
$\begingroup$

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.

|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dilip Sarwate Oct 18 '15 at 18:07
  • $\begingroup$ @DilipSarwate I assume that the feedback polynomial is primitive, For XNOR operation I've found Xilinx, however I need a reference for it $\endgroup$ – SMA.D Oct 18 '15 at 18:14
3
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SMA.D Oct 18 '15 at 18:43
  • $\begingroup$ 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$ $\endgroup$ – Nir Regev Oct 18 '15 at 19:58
  • $\begingroup$ You are true. Do you think that this fact is somehow obvious and doesn't need any citations? $\endgroup$ – SMA.D Oct 18 '15 at 20:14
  • $\begingroup$ 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. $\endgroup$ – SMA.D Oct 18 '15 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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