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