Hello
I am beginning the implementation of the polynomial binary division algorithm now as I understood i will be checking the MSB bit if 1 to XOR and shift the sum if 0 i will only shift.
What I am not getting well with is the numerator and denominator degree calculation and when to stop the the division
in a case of a polynomial division with M=8 and an irreducible polynomial :
X^8+X^4+X^3+X+1 will be divided by X^6+X^5+X^2+X
at first I will have to pad with zeros to obtain the same size
I have found that shifting the numerator by L and denominator by K until hitting the first '1' will give me the degree being M-L and M-K-1 of each polynomial
and the division will be of Deg(N)-Deg(D) cycles
in this example:
it will be:
Numerator: 100011011
Denominator: 01100110
Numerator MSB is 1 then degree(N) is M-0=8
Denominator MSB is 0 : then it will be shifted to the left by 1 and the Degree(D)=8-1-1=6
the needed counter is 8-6=2 steps and 8-6+1=3 XOR operations
what I would like to ask is this a correct way to start and won't the following degree calculation step includes a large hardware delay since it is done sequentially and M might get to 233
What is the best way of calculating the :
Degree of numerator and denominator
and when can i know where to stop the division
No padding to the left. Start with the numbers left aligned (the first '1' in both numbers aligned),
then Xor whenever the highest '1''s are aligned. Stop when the LSB's are aligned.
Code:
100011011
1100110 (do xor)
010000011
1100110 (do xor)
01001111
1100110 (do xor then stop because LSB's are aligned)
0101001 (remainder)
Xor in all steps => quotient is 111 = x^2 + x + 1
Remainder is 101001 = x^5 + x^3 + 1