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( p ^m ) polynomials, where field is a matrix containing the m -tuple of all elements in GF( p ^m ). 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, α , α ² , ...] relative to some primitive element α of GF( p ^m ).

Examples

collapse all

Divide Polynomials in GF(3)

Open Live Script

Divide $x + x^{3} + x^{4}$ 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

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)

 
                                    1 + X

Check for Irreducibility and Primitiveness over GF(3^k)

Open Live Script

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

The irreducibility of $1 + x^{2}$ over GF(3), along with the polynomials that are output, indicates that $1 + 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)
                                    2 + X 
                                    2 + X

Input Arguments

collapse all

`b` — Galois field polynomial
row vector | character vector | string

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( p ^m ) 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(2 ⁴ ) expressed as a character vector.

Data Types: double | char | string

`a` — Galois field polynomial
row vector | character vector | 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( p ^m ) 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+3x ² +4x ³ in GF(5) expressed as a row vector.

Data Types: double | char | string

`p` — Prime number
`2` (default) | prime number

Prime number, specified as a prime number.

Data Types: double

`field` — m -tuple of all elements in GF( p ^m )
matrix

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

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

The coefficients, specified in exponential format, represent the field elements in GF( p ^m ). For an explanation of these formats, see Representing Elements of Galois Fields .

Data Types: double

Output Arguments

collapse all

`q` — Galois field polynomial
row vector

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.

`r` — Division remainder
scalar | row vector

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

Tips

The gfdeconv function performs computations in GF( p ^m ), where p is prime, and m is a positive integer. It divides polynomials over a Galois field. To work in GF(2 ^m ), 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.

Version History

Introduced before R2006a

gfdeconv

Syntax

Description

Examples

Divide Polynomials in GF(3)

Check for Irreducibility and Primitiveness over GF(3^k)

Input Arguments

`b` — Galois field polynomial
row vector | character vector | string

`a` — Galois field polynomial
row vector | character vector | string

`p` — Prime number
`2` (default) | prime number

`field` — m -tuple of all elements in GF( p ^m )
matrix

Output Arguments

`q` — Galois field polynomial
row vector

`r` — Division remainder
scalar | row vector

Tips

Version History

See Also

Functions

Topics

gfdeconv

Syntax

Description

Examples

Divide Polynomials in GF(3)

Check for Irreducibility and Primitiveness over GF(3^k)

Input Arguments

b — Galois field polynomial row vector | character vector | string

a — Galois field polynomial row vector | character vector | string

p — Prime number 2 (default) | prime number

field — m -tuple of all elements in GF( p m ) matrix

Output Arguments

q — Galois field polynomial row vector

r — Division remainder scalar | row vector

Tips

Version History

See Also

Functions

Topics

`b` — Galois field polynomial
row vector | character vector | string

`a` — Galois field polynomial
row vector | character vector | string

`p` — Prime number
`2` (default) | prime number

`field` — m -tuple of all elements in GF( p ^m )
matrix

`q` — Galois field polynomial
row vector

`r` — Division remainder
scalar | row vector