Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for a way to mathematically combine two concepts: LFSRs, and Barrel Shifters

I'm looking for a way, in O(1) time, to shift an LFSR loop a given number of shifts.

What I'm hoping to find is a simple process where I have the current state of the LFSR and the number of times I want to shift from that state as parameters to a quick/easy process.

At first I just thought about looking at all the taps, then moving the taps over by 1 and looking at them again, finding the shift in bit each time and appending it onto the end but of course this isn't O(1) and it gets complicated if I want to shift so many times that a tap would "slide off" the original LFSR state.

I may be in the wrong place to ask this because I'm looking for a way to do this programmatically. Although any incite into how it's possible (or why it's impossible) would be very helpful.

share|improve this question
    
I'm not sure such a way exists... –  Yuval Filmus Feb 17 '11 at 16:45
    
me either, but I can hope –  Corey Ogburn Feb 17 '11 at 18:08
    
@Dilip: Please see the discussion on this meta answer and comments. –  Asaf Karagila Apr 18 '12 at 15:47
1  
@AsafKaragila I deleted the lfsr tag, and so it can stay on the list of deleted tags on meta –  Dilip Sarwate Apr 18 '12 at 16:00

1 Answer 1

The successive contents of a (binary) maximal-length linear feedback shift register with $n$ stages can be interpreted as the elements $\ldots, \alpha^{i-1}, \alpha^i, \alpha^{i+1}, \ldots,$ of $\mathbb F_{2^n}$ (where $\alpha$ is a primitive element in the field) expressed in the dual-polynomial basis (see the answers and comments on this question). So what you are asking is,

Given the current state $\alpha^i$ and an integer $j$, compute the state $\alpha^{i+j}$ as quickly as possible (preferably in $O(1)$ time).

This would require either

  • exponentiation (compute $\alpha^j$) followed by multiplication (to find $\alpha^i \times \alpha^j$)

or

  • a discrete logarithm computation (find $i = \log_{\alpha}(\alpha^i)$ followed by addition ($i+j$) and exponentiation.

This fleshes out @YuvalFilmus's hint that a simple method may not exist. Of course, if $n$ is not too large, and the set of values of $j$ that you are interested in is not too large, table look-up would be the way to solve the problem instead of barrel shifters. If $j$ can be only two or three values, you can implement the transformation $\alpha^i \to \alpha^{i+j}$ using Exclusive-OR trees with feedback going not just to the last stage of the LFSR but to several stages.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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