Extended Euclidean Algorithm for polynomials over GF(2^m)

by

 

Implementation of the extended Euclidean algorithm for polynomials over GF(2^m)

test_euclid.m
% Last updated => 29/05/2003
% Test division algorithm

% Find the GCD of two polynomials f(x) and g(x)

clear
clc


%**************************************
%*** RS Code Parameters ***
%**************************************

% m  is the number of bits of each symbol
% n = 2^m-1 => the number of symbols transmitted
% k = the number of code symbols that is going to be codes to a n symbol message
% h = the number of erasures

m = 3
n = 2^m-1
h = 3 % the packetlength
k = 4
%*************************************



%*****************************
%*** Generate Galois Field ***
%*****************************

field = gftuple([-1:2^m-2]', m, 2);

%*****************************


%****************************************
%*** Generator polynomial of RS codes ***
%****************************************

c = [1 0]; 
p(1) = c(1);

for i = 1:h-1
    p(1) = gfmul(p(1),1,field);
    p(2) = 0;
    c = gfconv(c,p,field);
end
g = c;

%****************************************


g

A = [1 2 3 4 5 6]
B = [4 5 1]

C = gfeuclid(A,B,field)
[gg,u,v] = gfcomp_gcd(A,B,field)

AA = gfconv(A,u,field);
BB = gfconv(B,v,field);

CC = gfadd(AA,BB,field);

%clear all leading zeros
CC = gfconv(CC,0,field)

Contact us