+ Post New Thread
Results 1 to 6 of 6
  1. #1
    Member level 2
    Points: 973, Level: 7

    Join Date
    Aug 2013
    Posts
    45
    Helped
    0 / 0
    Points
    973
    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

    •   Alt11th January 2017, 13:29

      advertising

        
       

  2. #2
    Advanced Member level 3
    Points: 4,416, Level: 15

    Join Date
    Feb 2015
    Posts
    731
    Helped
    217 / 217
    Points
    4,416
    Level
    15

    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.

    •   Alt11th January 2017, 17:36

      advertising

        
       

  3. #3
    Member level 2
    Points: 973, Level: 7

    Join Date
    Aug 2013
    Posts
    45
    Helped
    0 / 0
    Points
    973
    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 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).



    •   Alt11th January 2017, 22:38

      advertising

        
       

  4. #4
    Advanced Member level 3
    Points: 4,416, Level: 15

    Join Date
    Feb 2015
    Posts
    731
    Helped
    217 / 217
    Points
    4,416
    Level
    15

    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.

  5. #5
    Member level 2
    Points: 973, Level: 7

    Join Date
    Aug 2013
    Posts
    45
    Helped
    0 / 0
    Points
    973
    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".



    Quote Originally Posted by vGoodtimes View Post
    (notice that the input had C at the 2nd location, not the 3rd.)
    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.



    •   Alt12th January 2017, 12:32

      advertising

        
       

  6. #6
    Advanced Member level 3
    Points: 4,416, Level: 15

    Join Date
    Feb 2015
    Posts
    731
    Helped
    217 / 217
    Points
    4,416
    Level
    15

    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.



--[[ ]]--