Main Content

fft

Fast Fourier transform of Galois field vector

collapse all in page

Syntax

y = fft(x)

Description

y = fft(x) computes the discrete Fourier transform (DFT) of the Galois field vector x.

example

Examples

collapse all

Open Live Script

Define parameters for Galois field order and input length.

m = 4; % Galois field order
n = 2^m-1; % Length of input vector

Specify a primitive element in the Galois field (GF). Generate the matrices for the corresponding DFT and inverse DFT.

alph = gf(2,m);
dm = dftmtx(alph);
idm = dftmtx(1/alph);

Generate a random GF vector.

x = gf(randi([0 2^m-1],n,1),m);

Perform the Fourier transform twice, once using the function and once using multiplication with the DFT matrix.

y1 = fft(x);
y2 = dm*x;

Invert the transform, using the function and multiplication with the inverse DFT matrix.

z1 = ifft(y1);
z2 = idm*y2;

Confirm that both results match the original input.

isequal(z1,z2,x)
ans = logical
   1

Input Arguments

collapse all

Input vector, specified as a vector with Galois field entries. The entries of x must be in the Galois field GF(2m).

Data Types: gf

Output Arguments

collapse all

DFT of the input vector x, returned as a vector with Galois field entries.

Data Types: gf

Limitations

The Galois field, GF(2m), over which this function works must have 256 or fewer elements. In other words, m must be an integer in the range [1, 8].

Algorithms

If x is a column vector, fft applies dftmtx to the primitive element of the Galois field and multiplies the resulting matrix by x. If x is a row vector, the order of the matrix multiplication is reversed.

Version History

Introduced before R2006a

See Also

| |

Topics