Discrete Fourier transform matrix in Galois field
dm = dftmtx(alph)
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 |
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(randi([0 2^m-1],n,1),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
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.