Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

LFSR reverse function

Status
Not open for further replies.
L

LatticeSemiconductor

Member level 2
Joined
Aug 31, 2013
Messages
45
Helped
0
Reputation
0
Reaction score
0
Trophy points
6
Activity points
589
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
 

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.
 
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).
 

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.
 
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".



vGoodtimes said:
(notice that the input had C at the 2nd location, not the 3rd.)
Click to expand...

I'm not sure what you ment to say with this.

I replaced the AND gates with XOR gates and it works perfectly :razz:

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:

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.
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top