This may seem an elementary question about LFSRs, and their link to Markov chains. LFSRs show Markov chain behaviour in that there can be a transition matrix defined over the LFSR, this follows from the very definition of the LFSR. Is there any formal formulation for the LFSR as a Markov chain?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.
In a standard linear feedback shift register (LFSR), the succession of states (generally taken to mean the shift register contents) is predetermined; there is nothing random about the state transitions. Given any state and the feedback polynomial, the next state can be readily computed. Indeed, the states recur in periodic cycles.
In contrast, in a Markov chain, the next state cannot be determined from knowledge of the current state; all we know are the (conditional) probabilities that the next state is $S_j$ given that the current state is $S_i$. Think of it this way: the transition matrix of a $N$-state Markov chain is a $N\times N$ matrix of transition probabilities. In contrast, an LFSR with $N$ bits/symbols has $2^N$ (more generally, $q^N$) different states, but its transition matrix is only an $N\times N$ matrix. If you were to write down the transition matrix in Markov-chain style, it would be a $2^N\times 2^N$ matrix and all the transition probabilities (entries in the matrix) would be either $0$ or $1$ and there would be exactly one $1$ in each row and in each column, that is, it would be a permutation matrix.