Communications Toolbox

Signal Processing Operations in Galois Fields

You can perform some signal-processing operations on Galois arrays, such as filtering, convolution, and the discrete Fourier transform. This section describes how to perform these operations. Other information about the corresponding operations for ordinary real vectors is in the Signal Processing Toolbox documentation.

Filtering

To filter a Galois vector, use the filter function. It behaves like the ordinary MATLAB filter function when given exactly three input arguments. The code and diagram below give the impulse response of a particular filter over GF(2).

• m = 1; % Work in GF(2).
  b = gf([1 0 0 1 0 1 0 1],m); % Numerator
  a = gf([1 0 1 1],m); % Denominator
  x = gf([1,zeros(1,19)],m);
  y = filter(b,a,x); % Filter x.
  figure; stem(y.x); % Create stem plot.
  axis([0 20 -.1 1.1])
  
  
  

Convolution

This toolbox offers two equivalent ways to convolve a pair of Galois vectors:

• Use the conv function, as described in Multiplication and Division of Polynomials. This works because convolving two vectors is equivalent to multiplying the two polynomials whose coefficients are the entries of the vectors.
• Use the convmtx function to compute the convolution matrix of one of the vectors, and then multiply that matrix by the other vector. This works because convolving two vectors is equivalent to filtering one of the vectors by the other. The equivalence permits the representation of a digital filter as a convolution matrix, which you can then multiply by any Galois vector of appropriate length.

Tip    If you need to convolve large Galois vectors, then multiplying by the convolution matrix might be faster than using conv.

Example.   The example below computes the convolution matrix for a vector b in GF(4), representing the numerator coefficients for a digital filter. It then illustrates the two equivalent ways to convolve b with x over the Galois field.

• m = 2; b = gf([1 2 3]',m);
  n = 3; x = gf(randint(n,1,2^m),m);
  C = convmtx(b,n); % Compute convolution matrix.
  v1 = conv(b,x); % Use conv to convolve b with x
  v2 = C*x; % Use C to convolve b with x.
  

Discrete Fourier Transform

The discrete Fourier transform is an important tool in digital signal processing. This toolbox offers these tools to help you process discrete Fourier transforms:

• fft, which transforms a Galois vector
• ifft, which inverts the discrete Fourier transform on a Galois vector
• dftmtx, which returns a Galois array that you can use to perform or invert the discrete Fourier transform on a Galois vector

In all cases, the vector being transformed must be a Galois vector of length 2^m-1 in the field GF(2^m). The examples below illustrate the use of these functions. You can check, using the isequal function, that y equals y1, z equals z1, and z equals x.

• m = 4;
  x = gf(randint(2^m-1,1,2^m),m); % A vector to transform
  alph = gf(2,m);
  dm = dftmtx(alph);
  idm = dftmtx(1/alph);
  y = dm*x; % Transform x using the result of dftmtx.
  y1 = fft(x); % Transform x using fft.
  z = idm*y; % Recover x using the result of dftmtx(1/alph).
  z1 = ifft(y1); % Recover x using ifft.
  

Tip    If you have many vectors that you want to transform (in the same field), then it might be faster to use dftmtx once and matrix multiplication many times, instead of using fft many times.

Linear Algebra in Galois Fields

Polynomials over Galois Fields