# fft

Discrete Fourier transform

## Syntax

```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`.