How to get permutation with LFSR in Verilog

Question

I am relatively inexperienced in Verilog and very new to the LFSR construct. What I would like to accomplish is as follows..

If I have a 5 byte array, that would imply max permutations of 5! or 120. What I'd like to be able to do is, have a way to quickly return any permutation of this array. If I init the array to (0,1,2,3,4), then for this 5 deep array, permutation 0 yields the array (1,2,3,4,0). Permutation 40 yields the array (4,0,3,2,1), etc.

So I think a LFSR is the quickest way to accomplish this, and I understand how they work, but I cannot get to a complete understanding of what the taps should be or how to get a particular permutation only.

reg [4:0] vals;
wire feedback
assign feedback = vals[0] ^ vals[1] ^ vals[2] ^ vals[3] ^ vals[4];

always@(posedge clk or negedge reset) begin
 if (reset==1'b0) begin
  vals[4:0]<=5'hF;  //reset condition first
 end 
 else begin
  vals[0]<=feedback;
  vals[1]<=vals[0];
  vals[2]<=vals[1];
  vals[3]<=vals[2];
  vals[4]<=vals[3];
 end

Clearly that feedback is not going to work! I am just stuck trying to get the entire comtext straight in my brain. How do I make it go to a certain permutation? How many taps are needed based on the size of the array? Any help is greatly appreciated!

'5 byte array' do you mean 5 bit array? – Morgan Dec 29 '13 at 20:58 — Morgan, Dec 29 '13 at 20:58

score 2 · Accepted Answer · answered Dec 29 '13 at 05:30

2

What you're asking for here doesn't make sense. Unless there's some major insight you've made and haven't articulated, I don't think there's any way to use an LFSR to generate permutations. A properly configured LFSR will generate a maximum-length sequence of output bits (by cycling through all but one of the possible internal states), but that sequence has no apparent relation to permutations. (The number of states certainly doesn't match up at all; an LFSR has 2^n - 1 states, but permutations have n! states.)

Reviewing the mathematical literature regarding the generation of permutations (e.g, Knuth's "Generating All Permutations" from The Art of Computer Programming) may be of some use here.

answered Dec 29 '13 at 05:30

I thought you can use an LFSR to generate permutations with a length that's a power of 2. For an arbitrary length, create one with the smallest power of 2 length greater than length. Since the LFSR can generate the same pseudo-random sequence each time, I thought a feedback function of the correct type could be concocted to produce any given permutation. If not, what construct would be best for this purpose? – user3143237 Dec 29 '13 at 05:52
It's power-of-2-minus-1, actually, because either the all-ones or all-zeroes state of the LFSR will be a fixed point. In any case, while using an LFSR to generate permutations is a creative idea, I don't see any obvious way to realize it. It's certainly not attested in the literature. – Dec 29 '13 at 06:03

score 1 · Answer 2 · edited May 23 '17 at 11:45

1

I have written a Q&A style on implementing an LFSR which may be of use. Especially the section about choosing tap points.

In my experience LFSR are used for hardware random sequences or dither when high levels of cryptography are not required, they are just white noise sources.

As they are used for randomness they will constantly repeat the same sequence but not designed to give bit y out on demand. Although you could just supply 64 positive clock edges to get the 64th bit (sequence).

edited May 23 '17 at 11:45

Community

1
1

answered Dec 29 '13 at 20:57

Morgan

19,934
8
58
84

Thank you for that insight Morgan. Your writings on implementing an LFSR were certainly helpful! – user3143237 Dec 30 '13 at 03:53

How to get permutation with LFSR in Verilog

2 Answers2