cyclotomic fast Fourier transform

The discrete Fourier transform over finite fields finds widespread application in the decoding of error-correcting codes such as BCH codes and Reed–Solomon codes. Generalized from the complex field, a discrete Fourier transform of a sequence $\backslash \{f\_i\backslash \}\_\{0\}^\{N-1\}$ over a finite field GF(p^m) is defined as

:$F\_j=\backslash sum\_\{i=0\}^\{N-1\}f\_i\backslash alpha^\{ij\},\; 0\backslash le\; j\backslash le\; N-1,$

where $\backslash alpha$ is the N-th primitive root of 1 in GF(p^m). If we define the polynomial representation of $\backslash \{f\_i\backslash \}\_\{0\}^\{N-1\}$ as

:$f(x)\; =\; f\_0+f\_1x+f\_2x^2+\backslash cdots+f\_\{N-1\}x^\{N-1\}=\backslash sum\_\{0\}^\{N-1\}f\_ix^i,$

it is easy to see that $F\_j$ is simply $f(\backslash alpha^j)$. That is, the discrete Fourier transform of a sequence converts it to a polynomial evaluation problem.

Written in matrix format,

:$\backslash mathbf\{F\}=\backslash left[\backslash begin\{matrix\}F\_0\backslash \backslash F\_1\backslash \backslash \; \backslash vdots\; \backslash \backslash \; F\_\{N-1\}\backslash end\{matrix\}\backslash right]=$

\left[\begin{matrix}

\alpha^0&\alpha^0 &\cdots & \alpha^0\\

\alpha^0 & \alpha^1 &\cdots &\alpha^{N-1}\\

\vdots &\vdots & \ddots & \vdots \\

\alpha^{0} & \alpha^{N-1} &\cdots & \alpha^{(N-1)(N-1)}

\end{matrix}\right]

\left[\begin{matrix}f_0\\f_1\\\vdots\\f_{N-1}\end{matrix}\right]=\mathcal{F}\mathbf{f}.

Direct evaluation of DFT has an $O(N^2)$ complexity. Fast Fourier transforms are just efficient algorithms evaluating the above matrix-vector product.

First, we define a linearized polynomial over GF(p^m) as

:$L(x)\; =\; \backslash sum\_\{i\}\; l\_i\; x^\{p^i\},\; l\_i\; \backslash in\; \backslash mathrm\{GF\}(p^m).$

$L(x)$ is called linearized because $L(x\_1+x\_2)\; =\; L(x\_1)\; +\; L(x\_2)$, which comes from the fact that for elements $x\_1,x\_2\; \backslash in\; \backslash mathrm\{GF\}(p^m),$$(x\_1+x\_2)^p=x\_1^p+x\_2^p.$

Notice that $p$ is invertible modulo $N$ because $N$ must divide the order $p^m-1$ of the multiplicative group of the field $\backslash mathrm\{GF\}(p^m)$. So, the elements $\backslash \{0,\; 1,\; 2,\; \backslash ldots,\; N-1\backslash \}$ can be partitioned into $l+1$ cyclotomic cosets modulo $N$:

:$\backslash \{0\backslash \},$

:$\backslash \{k\_1,\; pk\_1,\; p^2k\_1,\; \backslash ldots,\; p^\{m\_1-1\}k\_1\backslash \},$

:$\backslash ldots,$

:$\backslash \{k\_l,\; pk\_l,\; p^2k\_l,\; \backslash ldots,\; p^\{m\_l-1\}k\_l\backslash \},$

where $k\_i=p^\{m\_i\}k\_i\; \backslash pmod\{N\}$. Therefore, the input to the Fourier transform can be rewritten as

:$f(x)=\backslash sum\_\{i=0\}^l\; L\_i(x^\{k\_i\}),\backslash quad\; L\_i(y)\; =\; \backslash sum\_\{t=0\}^\{m\_i-1\}y^\{p^t\}f\_\{p^tk\_i\backslash bmod\{N\}\}.$

In this way, the polynomial representation is decomposed into a sum of linear polynomials, and hence $F\_j$ is given by

:$F\_j=f(\backslash alpha^j)=\backslash sum\_\{i=0\}^lL\_i(\backslash alpha^\{jk\_i\})$.

Expanding $\backslash alpha^\{jk\_i\}\; \backslash in\; \backslash mathrm\{GF\}(p^\{m\_i\})$ with the proper basis $\backslash \{\backslash beta\_\{i,0\},\; \backslash beta\_\{i,1\},\; \backslash ldots,\; \backslash beta\_\{i,m\_i-1\}\backslash \}$, we have $\backslash alpha^\{jk\_i\}\; =\; \backslash sum\_\{s=0\}^\{m\_i-1\}a\_\{ijs\}\backslash beta\_\{i,s\}$ where $a\_\{ijs\}\; \backslash in\; \backslash mathrm\{GF\}(p)$, and by the property of the linearized polynomial $L\_i(x)$, we have

:$F\_j=\backslash sum\_\{i=0\}^l\backslash sum\_\{s=0\}^\{m\_i-1\}a\_\{ijs\}\backslash left(\backslash sum\_\{t=0\}^\{m\_i-1\}\backslash beta\_\{i,s\}^\{p^t\}f\_\{p^\{t\}k\_i\backslash bmod\{N\}\}\backslash right)$

This equation can be rewritten in matrix form as $\backslash mathbf\{F\}=\backslash mathbf\{AL\backslash Pi\; f\}$, where $\backslash mathbf\{A\}$ is an $N\backslash times\; N$ matrix over GF(p) that contains the elements $a\_\{ijs\}$, $\backslash mathbf\{L\}$ is a block diagonal matrix, and $\backslash mathbf\{\backslash Pi\}$ is a permutation matrix regrouping the elements in $\backslash mathbf\{f\}$ according to the cyclotomic coset index.

Note that if the normal basis $\backslash \{\backslash gamma\_i^\{p^0\},\; \backslash gamma\_i^\{p^1\},\; \backslash cdots,\; \backslash gamma\_i^\{p^\{m\_i-1\}\}\backslash \}$ is used to expand the field elements of $\backslash mathrm\{GF\}(p^\{m\_i\})$, the i-th block of $\backslash mathbf\{L\}$ is given by:

:$\backslash mathbf\{L\}\_i=$

\begin{bmatrix}

\gamma_i^{p^0} &\gamma_i^{p^1} &\cdots &\gamma_i^{p^{m_i-1}}\\

\gamma_i^{p^1} &\gamma_i^{p^2} &\cdots &\gamma_i^{p^{0}}\\

\vdots & \vdots & \ddots & \vdots\\

\gamma_i^{p^{m_i-1}} &\gamma_i^{p^0} &\cdots &\gamma_i^{p^{m_i-2}}\\

\end{bmatrix}

which is a circulant matrix. It is well known that a circulant matrix-vector product can be efficiently computed by convolutions. Hence we successfully reduce the discrete Fourier transform into short convolutions.

When applied to a characteristic-2 field GF(2^m), the matrix $\backslash mathbf\{A\}$ is just a binary matrix. Only addition is used when calculating the matrix-vector product of $\backslash mathrm\{A\}$ and $\backslash mathrm\{L\backslash Pi\; f\}$. It has been shown that the multiplicative complexity of the cyclotomic algorithm is given by $O(n(\backslash log\_2n)^\{\backslash log\_2\backslash frac\{3\}\{2\}\})$, and the additive complexity is given by $O(n^2/(\backslash log\_2\; n)^\{\backslash log\_2\backslash frac\{8\}\{3\}\})$.

{{reflist}}

Category:Discrete transforms

Category:FFT algorithms