Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

put on hold as unclear what you're asking by D.W., e-sushi, archie, poncho, fgrieu Jul 24 at 13:48

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.

    
I find this question unclear. What do you have in mind as the statespace of the Markov chain? If the state is the entire state of the LFSR, then of course there is a trivial Markov chain, since it is a deterministic process, but this does not seem likely to be useful. So what did you have in mind? Let me put it another way. Why do you ask this question? What's the motivation or context where you plan to use this? How will you evaluate or use answers? As it stands the question seems a bit on the open-ended/ill-defined end. –  D.W. Jun 18 at 13:05
    
Yes, it does seem elementary, the context is to view the LFSR in other forms. The Berlekamp Massey algorithm gives an algorithm for this problem. In terms of numerical computations what would the equivalent Markov chain formulation take? So, if we did view the LFSR as a Markov chain what are the resources we would need, time, and space? –  user14938 Jun 18 at 13:10
1  
I don't understand in what sense the Berlekamp-Massey algorithm is an algorithm for "this problem" - what problem? Please try to be more precise. Berlekamp-Massey has nothing to do with Markov chains; it has to do with recovering the LFSR initial fill and feedback polynomial, given observations of its output. As far as your last question in your comment: for what task? what Markov chain formulation? It's impossible to say what resources are needed, if we don't know what the task is. Again, LFSRs are a deterministic process, so modelling it as a Markov chain is not very helpful. –  D.W. Jun 18 at 13:14

1 Answer 1

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.

share|improve this answer
    
So, continuing the above discussion, if we look at the Berlekamp Massey algorithm, it has as its input- bits of a stream, and its output is an LFSR. To think of the Markov chain, in context of the LFSR, the transition matrix is, as you correctly pointed out - a permutation matrix. If we are given the same bit stream (that we input to Berlekamp-Massey), is there a set of transitions we can define over the matrix to get information about the LFSR, or the LFSR this is a very roundabout, and redundant method- given Berlekamp Massey is an efficient algorithm! –  user14938 Jun 19 at 4:32

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