2

My question stems from the observation made that we can use a Linear Feedback Shift Register to perform a CRC check. Algebraically this normally is of the form;

S(x) = M(x) * x^k % G(x) ( gives the remainder, for a G(x) of order k)

The implementation of this is shown in this question, (and registers are all initialised to zero) and the mathematical bitwise calculation of the XOR division is shown in this question here.

I understand both of these - however, I also know that another common way of using an LFSR is to have no input, but instead preload the registers with non-zero values, and run (with zero as an input) to form a sequence of pseudo random numbers. This is shown in the image below

enter image description here

My question is, just as the CRC can be represented as a modulo-2 division both bitwise and algebraically, can we do the same for an LFSR sequence generator, given the generator polynomial and initial values? And if so, an example would be great!

Thanks very much, feel free to correct me if I've misrepresented or misunderstood a concept!

davidhood2
  • 1,367
  • 17
  • 47
  • Lfsr with zero input gives zero output. But with nonzero input, the output is something like x_0^ i mod p(x) with p being the generator polynomial. – Aki Suihkonen May 24 '17 at 17:17
  • An LFSR with zero input doesnt give zero output if the registers are initialised to non-zero value - as 0 xor A = A? (The LFSR shown in the image has a zero input?) Also, a non-zero input would be equivalent to CRC check; as described in the first link? – davidhood2 May 24 '17 at 17:21
  • Meaning zero initial state. – Aki Suihkonen May 24 '17 at 18:52
  • @AkiSuihkonen Do you have any mathematical examples? I can see how an LFSR with zero initial state is doomed to only give zero, but not how the ouput you described is formed? – davidhood2 May 25 '17 at 11:15

0 Answers0