+ Post New Thread
Results 1 to 6 of 6

11th January 2017, 13:29 #1
 Join Date
 Aug 2013
 Posts
 45
 Helped
 0 / 0
 Points
 995
 Level
 7
LFSR reverse function
is it possible to get the reverse sequence generated by a LFSR?
I need a pseudo random sequence, and the same sequence in reverse order
I read that the output stream of a LFSR can be reversed by mirroring the taps. This did not work, however :/
   Updated   
It's not possible

11th January 2017, 13:29

11th January 2017, 17:36 #2
 Join Date
 Feb 2015
 Posts
 825
 Helped
 237 / 237
 Points
 4,949
 Level
 16
Re: LFSR reverse function
What exactly are you doing? Are you doing the "shift by one" style of lfsr where you output multiple bits per cycle but only shift in one? or one where you shift multiple bits per cycle?
You can iterate through the bits backwards using the tapmirroring, but the new bits would need to be appended to the other side for the output.
1 members found this post helpful.

11th January 2017, 17:36

11th January 2017, 22:38 #3
 Join Date
 Aug 2013
 Posts
 45
 Helped
 0 / 0
 Points
 995
 Level
 7
Re: LFSR reverse function
Yes, i am doing the "shift by one" style of lfsr with XOR gates.
To mirror the tap sequence in an nbit LFSR I need to subtract the taps from n like so: [n, A, B, C] to [n, n − C, n − B, n − A].
And when the original LFSR is shifted to the right, the mirrored woul be shifted left, right?
The sequence and reverse of that sequence that i get from this would consist of sets of bits resulting from the respective output taps?
I already gave up on the idea but initially planned to write a deterministic random sequence to memory then reading the sequence again for testing the memory. The problem is that reading would also be done in reverse order (like a marchalgorithm with several write / read cycles).

11th January 2017, 22:38

12th January 2017, 05:44 #4
 Join Date
 Feb 2015
 Posts
 825
 Helped
 237 / 237
 Points
 4,949
 Level
 16
Re: LFSR reverse function
You can find the taps fairly easily with a test.
Take the 8 bit lfsr in fibbonacci config:
10111000
take a sequence:
A B C D E F G H
shifted right to left becomes:
B C D E F G H (A^C^D^E)
If we want to shift a value in on the right to get A, what would it be?
(A^C^D^E)^C^D^E = bit0 ^ bit6 ^ bit5 ^ bit4
(assumes value is 7:0)
so taps at 01110001, with values shifted from left to right. (notice that the input had C at the 2nd location, not the 3rd.)
Of course, if you wanted to shift from right to left the taps would be at 10001110.
1 members found this post helpful.

12th January 2017, 12:32 #5
 Join Date
 Aug 2013
 Posts
 45
 Helped
 0 / 0
 Points
 995
 Level
 7
Re: LFSR reverse function
that makes sense.
I tried your example and it worked for the 1st half of the sequence. This is because of the AND gates that make the sequence stuck at x"00".
I'm not sure what you ment to say with this.
I replaced the AND gates with XOR gates and it works perfectly
I still don't understand why, because:
(A^C^D^E)^C^D^E ≡ A
<=> A^C^D^E ≡ A
but when I use XOR gates:
(A XOR C XOR D XOR E) XOR C XOR D XOR E ≡ A
<=> A ≡ A
so no taps in this case!
   Updated   
(A XOR C XOR D XOR E) XOR C XOR D XOR E ≡ ØLast edited by LatticeSemiconductor; 12th January 2017 at 12:28.

12th January 2017, 12:32

12th January 2017, 19:06 #6
 Join Date
 Feb 2015
 Posts
 825
 Helped
 237 / 237
 Points
 4,949
 Level
 16
Re: LFSR reverse function
ah, sorry there were no and gates. I was trying to represent a sequence. I guess commas might have made that more clear.
state[0] = A,B,C,D,E,F,G,H
state[1] = B,C,D,E,F,G,H,(A^C^D^E)
forwardLfsr(a,b,c,d,e,f,g,h) = b,c,d,e,f,g,h,(a^c^d^e)
reverseLfsr(a,b,c,d,e,f,g,h) = (h^b^c^d),a,b,c,d,e,f,g
edit: I was using the C/Verilog operator "^" to denote xor here. Because the original LFSR used xor's and is also shown, I figured it would be clear. But the symbol "^" does look a bit like AND, as well as exponent. Likewise "+" looks like addition, could mean XOR, or could mean "OR" based on the field.
+ Post New Thread
Please login