Communications Toolbox

dftmtx

Discrete Fourier transform matrix in a Galois field

Syntax

• dm = dftmtx(alph);
  

Description

dm = dftmtx(alph) returns a Galois array that represents the discrete Fourier transform operation on a Galois vector, with respect to the Galois scalar alph. The element alph is a primitive nth root of unity in the Galois field GF(2^m) = GF(n+1); that is, n must be the smallest positive value of k for which alph^k equals 1. The discrete Fourier transform has size n and dm is an n-by-n array. The array dm represents the transform in the sense that dm times any length-n Galois column vector yields the transform of that vector.

Note    The inverse discrete Fourier transform matrix is dftmtx(1/alph).

Examples

The example below illustrates the discrete Fourier transform and its inverse, with respect to the element gf(3,4). The example examines the first n powers of that element to make sure that only the nth power equals one. Afterward, the example transforms a random Galois vector, undoes the transform, and checks the result.

• m = 4;
  n = 2^m-1;
  a = 3;
  alph = gf(a,m);
  mp = minpol(alph);
  if (mp(1)==1 && isprimitive(mp)) % Check that alph has order n.
      disp('alph is a primitive nth root of unity.')
      dm = dftmtx(alph);
      idm = dftmtx(1/alph);
      x = gf(randint(n,1,2^m),m);
      y = dm*x; % Transform x.
      z = idm*y; % Recover x.
      ck = isequal(x,z)
  end
  

The output is

• alph is a primitive nth root of unity.
  
  ck =
  
       1
  

Limitations

The Galois field over which this function works must have 256 or fewer elements. In other words, alph must be a primitive nth root of unity in the Galois field GF(2^m), where m is an integer between 1 and 8.

Algorithm

The element dm(a,b) equals alph^((a-1)*(b-1)).

See Also

fft, ifft

demodmap

dmod