Gunroar:Cannon() wrote: ↑Wed Jan 04, 2023 8:24 pm
So this primitive polynomial
x^4 + x^1 + 1
Has 3 monomials and it's taps are {4,1,0}? And then does that render that table I posted above not applicable?
Sorry, I should have specified. The highest-degree monomial (the one that gives the degree of the polynomial) doesn't count. The taps would be 1, 0.
I haven't checked if x^4 + x^1 + 1 is primitive. Assuming it is, note that the table doesn't exhaustively list
all primitive polynomials for a given degree (bit length); it just provides
one for each.
Edit: Wait, those taps are numbered in the opposite way to how polynomial division works. For a 16th degree polynomial, for example, tap 15 corresponds to the monomial of degree 0, tap 14 to degree 1, ..., tap 0 to degree 15. So, actually (polynomial degree - 1 - monomial degree) gives the tap number. In the case of x^4 + x^1 + 1, the taps, following the convention of that table, would be 4 - 1 - 1 and 4 - 1 - 0, i.e. 2 and 3. The clue is that degree 0 (the 1 at the end) should always be present for the polynomial to be primitive, but the table shows many entries which lack a tap 0, even though all have tap (degree-1).
So, if the table is correct, then for example this entry: 16 65,535 [1, 2, 4, 15] means that the polynomial x^16 + x^14 + x^13 + x^11 + 1 is primitive. It isn't the only primitive polynomial of degree 16;
for example the CCITT CRC polynomial, x^16 + x^12 + x^5 + 1 is also primitive. Edit: Sorry, it is not, see below.
Edit 2: If you have Python and the SymPy package, you can try this:
Code: Select all
>>> from sympy import *
>>> x = symbols('x')
>>> init_printing(True)
>>> p = <primitive polynomial>
>>> (0, <seed polynomial>)
then repeatedly enter this line:
The function div() divides two polynomials, giving you a tuple with the quotient and the remainder. We specify GF(2) as the domain for the coefficients, which causes the arithmetic operations to be computed modulo 2. Assuming you entered a polynomial with a maximum degree 15 as seed, the quotient will always be either 0 or 1 (the output of the LFSR), and the remainder will be the new state of the LFSR.
For example, let's say our seed is the binary number 0110101000111110. Converted to a polynomial, that's x**14+x**13+x**11+x**9+x**5+x**4+x**3+x**2+x so let's enter that as the seed polynomial and see what happens.
Code: Select all
>>> p = x**16 + x**12 + x**5 + 1 # CCITT
>>> (0, x**14+x**13+x**11+x**9+x**5+x**4+x**3+x**2+x)
⎛ 14 13 11 9 5 4 3 2 ⎞
⎝0, x + x + x + x + x + x + x + x + x⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛ 15 14 12 10 6 5 4 3 2⎞
⎝0, x + x + x + x + x + x + x + x + x ⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛ 15 13 12 11 7 6 4 3 ⎞
⎝1, x + x + x + x + x + x + x + x + 1⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛ 14 13 8 7 4 ⎞
⎝1, x + x + x + x + x + x + 1⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛ 15 14 9 8 5 2 ⎞
⎝0, x + x + x + x + x + x + x⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛ 15 12 10 9 6 5 3 2 ⎞
⎝1, x + x + x + x + x + x + x + x + 1⎠
>>>
The output of the LFSR would be 0 1 1 0 1 (the successive quotients; the first 0 doesn't count because we entered it ourselves) and the successive states of the LFSR would be the binary numbers:
0110101000111110 (seed)
1101010001111100 (x**15 + x**14 + x**12 + x**10 + x**6 + x**5 + x**4 + x**3 + x**2)
1011100011011001 (x**15 + x**13 + x**12 + x**11 + x**7 + x**6 + x**4 + x**3 + 1)
0110000110010011 (x**14 + x**13 + x**8 + x**7 + x**4 + x + 1)
1100001100100110 (x**15 + x**14 + x**9 + x**8 + x**5 + x**2 + x)
1001011001101101 (x**15 + x**12 + x**10 + x**9 + x**6 + x**5 + x**3 + x**2 + 1)
Note how the direct implementation of the division of polynomials requires shifting to the left, even though many explanations of LFSRs use shifting to the right.