+ Post New Thread

Results 1 to 6 of 6

- 11th January 2017, 13:29 #1

- Join Date
- Aug 2013
- Posts
- 38
- Helped
- 0 / 0
- Points
- 831
- Level
- 6

## 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
- 562
- Helped
- 174 / 174
- Points
- 3,453
- Level
- 13

## 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 tap-mirroring, 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
- 38
- Helped
- 0 / 0
- Points
- 831
- Level
- 6

## 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 n-bit 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 march-algorithm with several write / read cycles).

- 11th January 2017, 22:38

- 12th January 2017, 05:44 #4

- Join Date
- Feb 2015
- Posts
- 562
- Helped
- 174 / 174
- Points
- 3,453
- Level
- 13

## 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
- 38
- Helped
- 0 / 0
- Points
- 831
- Level
- 6

## 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
- 562
- Helped
- 174 / 174
- Points
- 3,453
- Level
- 13

## 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