gfconv

Multiply polynomials over Galois field

Syntax

c = gfconv(a,b)

c = gfconv(a,b,p)

c = gfconv(a,b,field)

c = gfconv(polys)

c = gfconv(polys,p)

c = gfconv(polys,field)

Description

c = gfconv(a,b) returns a row vector that specifies the GF(2) polynomial coefficients in order of ascending powers. The returned vector results from the multiplication of GF(2) polynomials a and b. The polynomial degree of the resulting GF(2) polynomial c equals the degree of a plus the degree of b.

For additional information, see Tips.

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

c = gfconv(a,b,field) multiplies 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. a, b, and c 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).

c = gfconv(polys) returns a row vector that specifies the GF(2) polynomial coefficients in order of ascending powers. The returned vector results from the multiplication of the GF(2) polynomials specified in polys. The polynomial degree of the resulting GF(2) polynomial c equals the sum of the degrees of the polynomials contained in polys. Use this syntax when polys specifies polynomials as a cell array of character vectors or as a string array.

c = gfconv(polys,p) multiplies the GF(p) polynomials specified in polys, where p is a prime number. polys and c are polynomials with coefficients in order of ascending powers. Each coefficient is in the range [0, p–1]. a, b, and c are in the same Galois field.

c = gfconv(polys,field) multiplies the GF(p^m) polynomials in polys, 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. a, b, and c 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

Multiply GF(2) Polynomials

Multiply $1+2\mathit{x}+{3\mathit{x}}^2+{4\mathit{x}}^3$ and $1+\mathit{x}$ three times. Represent the polynomials as row vectors, character vectors, and strings.

c_rv = gfconv([1 1 0 1],[1 1])

c_rv = 1×5

     1     0     1     1     1

c_cv = gfconv('1 + x + x^3','1 + x')

c_cv = 1×5

     1     0     1     1     1

c_s = gfconv("1 + x + x^3","1 + x")

c_s = 1×5

     1     0     1     1     1

The results corresponds to $1+{\mathit{x}}^2+{\mathit{x}}^3+{\mathit{x}}^4$.

Multiply Polynomials Over GF(3)

Multiply $$1+x+x^4$$ and $$x+x^2$$ over the Galois field GF(3).

gfc = gfconv([1 1 0 0 1],[0 1 1],3)

gfc = 1×7

     0     1     2     1     0     1     1

The result corresponds to $$x+2x^2+x^3+x^5+x^6$$.

Multiply Polynomials Over GF(2^4) Using Field Input

Multiply $1+2\mathit{x}+{3\mathit{x}}^2+{4\mathit{x}}^3+{5\mathit{x}}^4$ and $1+\mathit{x}$ in the Galois field GF($2^4$).

field = gftuple([-1:2^4-2]',4,2);
c = gfconv('1 + 2x + 3x^2 + 4x^3 + 5x^4','1 + x',field)

c = 1×6

     2     6     7     8     9     6

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

gfpretty(c)

 
                                   2      3      4      5
                      2 + 6 X + 7 X  + 8 X  + 9 X  + 6 X 

Multiply GF(2) Polynomials Specified As Cell Array

Create a cell array containing three polynomials that result in the DVB-S2 generator polynomial for $\mathit{t}=3$ when multiplied together.

polyCell = {'1 + x + x3 + x5 + x14', ...
    '1 + x6 + x8 + x11 + x14','1 + x + x2 + x6 + x9 + x10 + x14'};
gp = gfconv(polyCell); % DVB-S2 for t=3

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

gfpretty(gp)

 
     4    6    8    10    11    13    16    17    20    24    25    26    27
1 + X  + X  + X  + X   + X   + X   + X   + X   + X   + X   + X   + X   + X  
 
              30    31    32    33    34    35    36    37    38    39    42
           + X   + X   + X   + X   + X   + X   + X   + X   + X   + X   + X  

Multiply Polynomials Expressed As Strings in GF(2^4) Using Field Input

Multiply $1+2\mathit{x}+3{\mathit{x}}^2+4{\mathit{x}}^3+5{\mathit{x}}^4$, $1+\mathit{x}$, and $1+{\mathit{x}}^3$ in the Galois field GF($2^4$).

field = gftuple((-1:2^4-2)', 4, 2);
c = gfconv(["1 + 2x + 3x^2 + 4x^3 + 5x^4","1 + x","1 + x3"],field)

c = 1×9

     4    13    14     9     2     1     7     8     8

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

gfpretty(c)

 
                          2      3      4    5      6      7      8
           4 + 13 X + 14 X  + 9 X  + 2 X  + X  + 7 X  + 8 X  + 8 X 

Input Arguments

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

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

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

polys — Galois field polynomial list

cell array of character vectors | string array

Galois field polynomial list, specified as a cell array of character vectors or a string array.

Example: ["1+x+x3+x5+x14","1+x6+x8+x11+x14"] is a string array of polynomials.

Data Types: cell | string

Output Arguments

c — Galois field polynomial

row vector

Galois field polynomial, returned as a row vector of the polynomial coefficients in order of ascending powers. The polynomial degree of the resulting GF(p^m) polynomial c equals the sum of the degrees of the input polynomials. c is in the same Galois field as the input polynomials.

Tips

• The gfconv function performs computations in GF(p^m), where p is prime, and m is a positive integer. It multiplies polynomials over a Galois field. To work in GF(2^m), you can also use the conv function of the gf object with Galois arrays. For details, see Multiplication and Division of Polynomials.

• To multiply elements of a Galois field, use gfmul instead of gfconv. Algebraically, multiplying polynomials over a Galois field is equivalent to convolving vectors containing the coefficients of the polynomials. This convolution operation uses arithmetic over the same Galois field.

Version History

Introduced before R2006a