I test this law with a 7-bits primitive polynomial LFSR. and the run property could be found according to output. Is there any theoretical to prove m-sequence property, I could just find some conclusion on some literature.


General property for a primitive LFSR:

Each nonzero bitstring of length $k$ where $k\leq m,$ occurs $2^{m-k+1}$ times while the all zero bitstring occurs $2^{m-k+1}-1$ times, in a single period of the LFSR. The run of $k$ 1’s is just one of those nonzero bitstrings.

For $k>m,$ some patterns never occur. The ones that do occur are exactly those patterns that satisfy parity checks which correspond to polynomial multiples of the generating polynomial.

Example: For the generating polynomial $x^4+x+1,$ the generating parity check is $$s_{t-4}\oplus s_{t-1}\oplus s_t=0.$$ Since $$(x+1)(x^4+x+1)=x^5+x^4+x^2+1,$$ the only $5-$tuples that occur at the output of this generator are those satisfying $$ s_{t-5}\oplus s_{t-4} \oplus s_{t-2}\oplus s_t=0.$$

| improve this answer | |

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.