en>Mark viking: /* top */ Added wl

2014-09-28T22:30:49Z

top: Added wl

en>Krishnachandranvn: /* See also */

2013-12-30T17:56:00Z

See also

New page

The '''cyclotomic fast Fourier transform''' is a type of [[fast Fourier transform]] algorithm over [[finite field]]s.<ref>S.V. Fedorenko and P.V. Trifonov, {{cite journal |last=Fedorenko |first=S. V. |first2=P. V.. |last2=Trifonov |url=http://dcn.ftk.spbstu.ru/~petert/papers/pushkin2.pdf |title=On Computing the Fast Fourier Transform over Finite Fields |journal=Proceedings of International Workshop on Algebraic and Combinatorial Coding Theory |pages=108–111|year=2003}}</ref> This algorithm first decomposes a DFT into several circular convolutions, and then derives the DFT results from the circular convolution results. When applied to a DFT over GF(2<sup''>''m''), this algorithm has a very low multiplicative complexity. In practice, since there usually exist efficient algorithms for circular convolutions with specific lengths, this algorithm is very efficient.<ref name="complexityAnalysis">{{cite journal | last=Wu | first=Xuebin | last2=Wang | first2=Ying |last3=Yan | first3=Zhiyuan | title=On Algorithms and Complexities of Cyclotomic Fast Fourier Transforms Over Arbitrary Finite Fields| journal=IEEE Transactions on Signal Processing|volume=60|issue=3|year=2012|pages=1149–1158}}</ref>

== Background ==
The [[discrete Fourier transform]] over [[finite field]]s finds widespread application in the decoding of [[error-correcting code]]s such as [[BCH codes]] and [[Reed–Solomon error correction|Reed–Solomon codes]]. Generalized from the [[complex number|complex field]], a discrete Fourier transform of a sequence <math>\{f_i\}_{0}^{N-1}</math> over a finite field GF(''p''''m'') is defined as

:<math>F_j=\sum_{i=0}^{N-1}f_i\alpha^{ij}, 0\le j\le N-1, </math>

where <math>\alpha</math> is the ''N''-th [[primitive root]] of 1 in GF(''p''''m''). If we define the polynomial representation of <math>\{f_i\}_{0}^{N-1}</math> as

:<math>f(x) = f_0+f_1x+f_2x^2+\cdots+f_{N-1}x^{N-1}=\sum_{0}^{N-1}f_ix^i,</math>

it is easy to see that <math>F_j</math> is simply <math>f(\alpha^j)</math>. That is, the discrete Fourier transform of a sequence converts it to a polynomial evaluation problem.

Written in matrix format,
:<math>\mathbf{F}=\left[\begin{matrix}F_0\\F_1\\ \vdots \\ F_{N-1}\end{matrix}\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}.
</math>

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

== Algorithm ==

First, we define a [[linearized polynomial]] over GF(pm) as

:<math>L(x) = \sum_{i} l_i x^{p^i}, l_i \in \mathrm{GF}(p^m).</math>

<math>L(x)</math> is called linearized because <math>L(x_1+x_2) = L(x_1) + L(x_2)</math>, which comes from the fact that for elements <math>x_1,x_2 \in \mathrm{GF}(p^m),</math><math>(x_1+x_2)^p=x_1^p+x_2^p.</math>

The elements <math>\{0, 1, 2, \ldots, N-1\}</math> can be partitioned into <math>l+1</math> cyclotomic cosets modulo <math>N</math>:
:<math>\{0\},</math>
:<math>\{k_1, pk_1, p^2k_1, \ldots, p^{m_1-1}k_1\},</math>
:<math>\ldots,</math>
:<math>\{k_l, pk_l, p^2k_l, \ldots, p^{m_l-1}k_l\},</math>
and <math>k_i=p^{m_i}k_i \pmod{N}</math>. Therefore, the Fourier transform can be rewritten as

:<math>f(x)=\sum_{i=0}^l L_i(x^{k_i}), L_i(y) = \sum_{j=0}^{m_j-1}f_{p^jk_i\bmod{N}}y^{p^j},</math>

In this way, the polynomial representation is decomposed into a sum of linear polynomials, and hence <math>F_j</math> is given by
:<math>F_j=f(\alpha^j)=\sum_{i=0}^lL_i(\alpha^{jk_i})</math>.
Expanding <math>\alpha^{jk_i} \in \mathrm{GF}(p^{m_i})</math> with the proper basis <math>\{\beta_{i,0}, \beta_{i,1}, \ldots, \beta_{i,m_i-1}\}</math>, we have <math>\alpha^{jk_i} = \sum_{s=0}^{m_i-1}a_{ijs}\beta_{i,s}</math> where <math>a_{ijs} \in \mathrm{GF}(p)</math>, and by the property of the linearized polynomial <math>L_i(x)</math>, we have

:<math>F_j=\sum_{i=0}^l\sum_{s=0}^{m_i-1}a_{ijs}\left(\sum_{t=0}^{m_i-1}\beta_{i,t}^{p^t}f_{p^{t}k_i\bmod{N}}\right)</math>

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

Note that if the [[normal basis]] <math>\{\gamma_i^{p^0}, \gamma_i^{p^1}, \cdots, \gamma_i^{p^{m_i-1}}\} </math> is used to expand the field elements of <math>\mathrm{GF}(p^{m_i})</math>, the i-th block of <math>\mathbf{L}</math> is given by:
:<math>\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}
</math>
which is a [[circulant matrix]]. It is well known that a circulant matrix-vector product can be efficiently computed by [[convolution]]s. Hence we successfully reduce the discrete Fourier transform into short convolutions.

== Complexity ==

When applied to a [[Characteristic (algebra)|characteristc]]-2 field GF(2''m''), the matrix <math>\mathbf{A}</math> is just a binary matrix. Only addition is used when calculating the matrix-vector product of <math>\mathrm{A}</math> and <math>\mathrm{L\Pi f}</math>. It has been shown that the multiplicative complexity of the cyclotomic algorithm is given by <math>O(n(\log_2n)^{\log_2\frac{3}{2}})</math>, and the additive complexity is given by <math>O(n^2/(\log_2 n)^{\log_2\frac{8}{3}})</math>.<ref name="complexityAnalysis"/>

== References ==
{{reflist}}

[[Category:Discrete transforms]]
[[Category:FFT algorithms]]

Cyclic subspace - Revision history

en>Mark viking: /* top */ Added wl

en>Krishnachandranvn: /* See also */