3
$\begingroup$

If I've got an LFSR, let's say a 16-bit Fibonacci LFSR as shown in the corresponding wikipedia article, which generates maximum length sequences, could I use it to create word sequences instead of bit sequences?

Staying with the wiki example, let's say I got a 16-bit LFSR with the following primitive polynomial: $x^{16} + x^{14} + x^{13} + x^{11} + 1$ which results in the usage of taps: 16 14 13 11. Now, if I just use the standard LFSR, the process would look as follos:

TAP:  1                                       11      13  14      16  
  +-->[1] [0] [1] [0] [1] [1] [0] [0] [1] [1] [1] [0] [0] [0] [0] [1]---+ 
  |                                            |       |   |            |
  +-------------------------------------------XOR-----XOR-XOR------<----+

The LFSR generates a sequence of length $2^{16}-1=65535$ bits until it reaches its original internal state again. Now, what would happen if the single bits in the state were replaced by whole words as shown in the next figure (w are changing 32-bit words)?

TAP:  1                                       11      13  14      16  
  +-->[w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w]---+
  |                                            |       |   |            |
  +-------------------------------------------XOR-----XOR-XOR------<----+ 

Would this return a sequence of 65535 32-bit words before it reaches its initial state again?

(Please note: I don't want to collect 32bit from output of a "bit-wise" LFSR to form a word, I'm merely interested in the above problem )

$\endgroup$
0

1 Answer 1

7
$\begingroup$

Sure enough, if you use xor with the words, what you do have is the bitwise LFSR repeated 32 times in parallel, each in a different state, but each one having a $2^{16}-1$ period, so the period of your construction should be $2^{16}-1$ as well. If LFSR period wasn't exactly $2^{16}-1$ this will be another history.

$\endgroup$
2
  • $\begingroup$ Oh yes, veiewing it from that perspective answers my question quite illustrative, thanks! $\endgroup$
    – Hagge Knar
    Oct 21, 2013 at 10:26
  • 1
    $\begingroup$ @HaggeKnar I suppose you could use other operations than XOR in your feedback function to make the 32 parallel registers more interacting with each other. But then it won't be linear anymore (at least not linear respective to XOR). $\endgroup$ Oct 21, 2013 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.