gfdeconv

Divide polynomials over Galois field

Syntax

[q,r] = gfdeconv(b,a)
[q,r] = gfdeconv(b,a,p)
[q,r] = gfdeconv(b,a,field)

Description

[q,r] = gfdeconv(b,a) returns the quotient q and remainder r as row vectors that specify GF(2) polynomial coefficients in order of ascending powers. The returned vectors result from the division b by a. a, b, and q are in GF(2).

For additional information, see Tips.

example

[q,r] = gfdeconv(b,a,p) divides two GF(p) polynomials, where p is a prime number. b, a, and q are in the same Galois field. b, a, q, and r are polynomials with coefficients in order of ascending powers. Each coefficient is in the range [0, p–1].

[q,r] = gfdeconv(b,a,field) divides two GF(pm) polynomials, where field is a matrix containing the m-tuple of all elements in GF(pm). p is a prime number, and m is a positive integer. b, a, and q are in the same Galois field.

In this syntax, each coefficient is specified in exponential format, specifically [-Inf, 0, 1, 2, ...]. The elements in exponential format represent the field elements [0, 1, α, α2, ...] relative to some primitive element α of GF(pm).

Examples

collapse all

Divide x+x3+x4 by 1+x in the Galois field GF(3) three times. Represent the polynomials as row vectors, character vectors, and strings.

p = 3;

Represent the polynomials using row vectors and divide them in GF(3).

b = [0 1 0 1 1];
a = [1 1];
[q_rv,r_rv] = gfdeconv(b,a,p)
q_rv = 1×4

     1     0     0     1

r_rv = 2

To confirm the output, compare the original Galois field polynomials to the result of adding the remainder to the product of the quotient and the divisor.

bnew = gfadd(gfconv(q_rv,a,p),r_rv,p);
isequal(b,bnew)
ans = logical
   1

Represent the polynomials using character vectors and divide them in GF(3).

b = 'x + x^3 + x^4';
a = '1 + x';
[q_cv,r_cv] = gfdeconv(b,a,p)
q_cv = 1×4

     1     0     0     1

r_cv = 2

Represent the polynomials using strings and divide them in GF(3) .

b = "x + x^3 + x^4";
a = "1 + x";
[q_s,r_s] = gfdeconv(b,a,p)
q_s = 1×4

     1     0     0     1

r_s = 2

Use the gfpretty function to display the result without the remainder in polynomial form.

gfpretty(q_s)
 
                                         3
                                    1 + X 

In the Galois field GF(3), output polynomials of the form xk-1 for k in the range [2, 8] that are evenly divisible by 1+x2. An irreducible polynomial over GF(p) of degree at least 2 is primitive if and only if it does not divide -1+xk evenly for any positive integer k less than pm-1. For more information, see the gfprimck function.

The irreducibility of 1+x2 over GF(3), along with the polynomials that are output, indicates that 1+x2 is not primitive for GF(32).

p = 3; m = 2;
a = [1 0 1]; % 1+x^2
for ii = 2:p^m-1
   b = gfrepcov(ii); % x^ii
   b(1) = p-1; % -1+x^ii
   [quot,remd] = gfdeconv(b,a,p);
   % Display -1+x^ii if a divides it evenly.
   if remd==0
      multiple{ii}=b;
      gfpretty(b)
   end
end
 
                                         4
                                    2 + X 
 
                                         8
                                    2 + X 

Input Arguments

collapse all

Galois field polynomial, specified as a row vector, character vector, or string. b can be either a Character Representation of Polynomials or numeric vector.

a and b must both be GF(p) polynomials or GF(pm) polynomials, where p is prime. The value of p is as specified when included, 2 when omitted, or implied when field is specified.

Example: '1 + x' is a polynomial in GF(24) expressed as a character vector.

Data Types: double | char | string

Galois field polynomial, specified as a row vector, character vector, or string. a can be either a Character Representation of Polynomials or numeric vector.

a and b must both be GF(p) polynomials or GF(pm) polynomials, where p is prime. The value of p is as specified when included, 2 when omitted, or implied when field is specified.

Example: [1 2 3 4] is the polynomial 1+2x+3x2+4x3 in GF(5) expressed as a row vector.

Data Types: double | char | string

Prime number, specified as a prime number.

Data Types: double

m-tuple of all elements in GF(pm), specified as a matrix. field is the matrix listing all elements of GF(pm), arranged relative to the same primitive element. To generate the m-tuple of all elements in GF(pm), use

field =gftuple([-1:p^m-2]',m,p)
The coefficients, specified in exponential format, represent the field elements in GF(pm). For an explanation of these formats, see Representing Elements of Galois Fields.

Data Types: double

Output Arguments

collapse all

Galois field polynomial, returned as a row vector of the polynomial coefficients in order of ascending powers. q is the quotient from the division of b by a and is in the same Galois field as the input polynomials.

Division remainder, returned as a scalar or a row vector of the polynomial coefficients in order of ascending powers. r is the remainder resulting from the division of b by a.

Tips

  • The gfdeconv function performs computations in GF(pm), where p is prime, and m is a positive integer. It divides polynomials over a Galois field. To work in GF(2m), use the deconv function of the gf object with Galois arrays. For details, see Multiplication and Division of Polynomials.

  • To divide elements of a Galois field, you can also use gfdiv instead of gfdeconv. Algebraically, dividing polynomials over a Galois field is equivalent to deconvolving vectors containing the coefficients of the polynomials. This deconvolution operation uses arithmetic over the same Galois field.

Introduced before R2006a