gfdeconv

Divide polynomials over Galois field

collapse all in page

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

Open Live Script

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
Open Live Script

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.

See Also

Functions

Topics

Introduced before R2006a

Communications Toolbox Documentation

Support