Documentation

# fft

Discrete Fourier transform

fft(x)

## Description

fft(x) is the discrete Fourier transform (DFT) of the Galois vector x. If x is in the Galois field GF(2m), the length of x must be 2m-1.

## Examples

collapse all

Set the order of the Galois field. Because x is in the Galois field (${2}^{4}$), the length of x must be ${2}^{m}-1$.

m = 4;
n = 2^m-1;

Generate a random GF vector.

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

Perform the Fourier transform.

y = fft(x);

Invert the transform.

z = ifft(y);

Confirm that the inverse transform z = x.

isequal(z,x)
ans = logical
1

## Limitations

The Galois field over which this function works must have 256 or fewer elements. In other words, x must be in the Galois field GF(2m), where m is an integer between 1 and 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.