Euclidian algorithm on polynomials in Galois field

Question

I feel so defeated. I need to apply the Euclidian algorithm on two polynomials in GF(16). I already have the answers, I just have no idea on how to divide polynomials with coefficients in the finite GF(16) generated by a specific generator polynomial (given as p later). By hand or Matlab. I would prefer Matlab at first.

Tables Source: Essentials of Error-Control Coding

So e.g. in table 4.1,

r1 = 112%54 = 4 and q1 = 112/54 = 2
r2 = 54%4 = 2 and q2 = 54/4 = 13

So the first polynomial division is (I think):

$$\frac { { x }^{ 4 } }{ { a }^{ 4 }{ x }^{ 3 }+{ a }^{ 7 }{ x }^{ 2 }+{ a }^{ 4 }{ x }+{ a }^{ 2 } } $$

Where I need to find the quotient and remainder. I have tried by hand and by Matlab and failed miserably. This is my Matlab code:

%x^4 divided by a^8*x^3+a^7*x^2+a^4*x+a^2
%in GF(2^4) generated by p(x) = 1+x+x^4 binary  descending = [1 0 0 1 1]

pbin = [1 0 0 1 1]              %binary representation of p
pdig = bi2de(pbin, 'left-msb')  %digit representation of p

m = 4                           %working in GF(2^m) = GF(2^4) = GF(16)

%descending powers
polya = gf([1 0 0 0], m, pdig); %x^4
polyb = gf([8 7 4 2], m, pdig); %a^8*x^3+a^7*x^2+a^4*x+a^2

%answer in ascending powers
[q, r] = deconv(polya, polyb)

This is the answer, which does not seem correct:

q = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
Array elements = 
          15
r = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
Array elements = 
           0          11           9          13

Can anyone help with the Matlab code or any other smart way to divide polynomials in the finite field?

Answer 1

Okay so I finally found out the culprit. When expressing the polynomials as vector the coefficients are as a^i where the coefficient is i.

It's a lot easier to explain with an example. The main thing is that a coefficient of 0 is a^0 that is 1. If you need to have zero elements you will need to have negative number like -1 or -Inf.

%Construct the specified Galois field 
p = 2; m = 4; % GF(p^m)
%Use the primitive polynomial 1+X+X^4 for GF(2^4).
prim_poly = [1 1 0 0 1];
field = gftuple([-1:p^m-2]', prim_poly, p);

%X^4 divided by a^8*x^3+a^7*x^2+a^4*x+a^2
b=[-1 -1 -1 -1  0];
a=[ 2  4  7  8 -1];
[quot, remd] = gfdeconv(b, a, field)

%Keep algorithm going that is
%a^8*x^3+a^7*x^2+a^4*x+a^2 divided by a^4*x^2+a^13*x+a^8

[quot, remd] = gfdeconv(a, remd, field)

%relevant links: 
%http://se.mathworks.com/help/comm/ug/error-detection-and-correction.html#bql4k7s-2
%http://se.mathworks.com/help/comm/ref/gfdeconv.html

In the example the Euclidean algorithm stops at two iterations but you could just keep going.