gfdeconv

Divide polynomials over Galois 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).

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 $\mathit{x}+{\mathit{x}}^{3}+{\mathit{x}}^{4}$ by $1+\mathit{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.

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 ${\mathit{x}}^{\mathit{k}}-1$ for $\mathit{k}$ in the range [2, 8] that are evenly divisible by $1+{\mathit{x}}^{2}$. An irreducible polynomial over GF(p) of degree at least 2 is primitive if and only if it does not divide ${-1\text{\hspace{0.17em}}+\mathit{x}}^{\mathit{k}}$ evenly for any positive integer $\mathit{k}$ less than ${\mathit{p}}^{\mathit{m}}-1$. For more information, see the gfprimck function.

The irreducibility of $1+{\mathit{x}}^{2}$ over GF(3), along with the polynomials that are output, indicates that $1+{\mathit{x}}^{2}$ is not primitive for GF(${3}^{2}$).

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 Representation of Polynomials in Communications Toolbox 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 Representation of Polynomials in Communications Toolbox 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.