円分高速フーリエ変換

円分高速フーリエ変換は、有限体上の高速フーリエ変換アルゴリズムの一種です。^[1]このアルゴリズムは、まず DFT をいくつかの循環畳み込みに分解し、次に循環畳み込みの結果から DFT 結果を導出します。 上の DFT に適用した場合、このアルゴリズムの乗法の複雑さは非常に低くなります。実際には、特定の長さの循環畳み込みには通常効率的なアルゴリズムが存在するため、このアルゴリズムは非常に効率的です。^[2]${\displaystyle GF(2^{m})}$

有限体上の離散フーリエ変換は、BCHコードやリード・ソロモンコードなどの誤り訂正符号の復号に広く応用されている。複素体から一般化して、有限体GF( p ^m )上の数列の離散フーリエ変換は次のように定義される。 ${\displaystyle \{f_{i}\}_{0}^{N-1}}$

${\displaystyle F_{j}=\sum _{i=0}^{N-1}f_{i}\alpha ^{ij},0\leq j\leq N-1,}$

ここで はGF( p ^m ) における 1 のN乗原始根である。 の多項式表現を次のように 定義すると、${\displaystyle \alpha }$${\displaystyle \{f_{i}\}_{0}^{N-1}}$

${\displaystyle f(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{N-1}x^{N-1}=\sum _{0}^{N-1}f_{i}x^{i},}$

は単純に であることが簡単にわかります。つまり、シーケンスの離散フーリエ変換はそれを多項式評価問題に変換します。 ${\displaystyle F_{j}}$${\displaystyle f(\alpha ^{j})}$

マトリックス形式で記述すると、

${\displaystyle \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} .}$

DFT の直接的な評価は複雑です。高速フーリエ変換は、上記の行列ベクトル積を評価する効率的なアルゴリズムです。 ${\displaystyle O(N^{2})}$

まず、 GF(p ^m ) 上の線形多項式を次のように定義する。

${\displaystyle L(x)=\sum _{i}l_{i}x^{p^{i}},l_{i}\in \mathrm {GF} (p^{m}).}$

${\displaystyle L(x)}$は線形化されていると言われます。これは、要素${\displaystyle L(x_{1}+x_{2})=L(x_{1})+L(x_{2})}$${\displaystyle x_{1},x_{2}\in \mathrm {GF} (p^{m}),}$${\displaystyle (x_{1}+x_{2})^{p}=x_{1}^{p}+x_{2}^{p}.}$

は体の乗法群の位数を割り切る必要があるため、を法として可逆であることに注目してください。したがって、要素は を法として円分剰余類に分割できます。 ${\displaystyle p}$${\displaystyle N}$${\displaystyle N}$${\displaystyle p^{m}-1}$${\displaystyle \mathrm {GF} (p^{m})}$${\displaystyle \{0,1,2,\ldots ,N-1\}}$${\displaystyle l+1}$${\displaystyle N}$

${\displaystyle \{0\},}$

${\displaystyle \{k_{1},pk_{1},p^{2}k_{1},\ldots ,p^{m_{1}-1}k_{1}\},}$

${\displaystyle \ldots ,}$

${\displaystyle \{k_{l},pk_{l},p^{2}k_{l},\ldots ,p^{m_{l}-1}k_{l}\},}$

ここで である。したがって、フーリエ変換の入力は次のように書き直すことができる。 ${\displaystyle k_{i}=p^{m_{i}}k_{i}{\pmod {N}}}$

${\displaystyle f(x)=\sum _{i=0}^{l}L_{i}(x^{k_{i}}),\quad L_{i}(y)=\sum _{t=0}^{m_{i}-1}y^{p^{t}}f_{p^{t}k_{i}{\bmod {N}}}.}$

このように、多項式表現は線形多項式の和​​に分解され、次のように表される。 ${\displaystyle F_{j}}$

${\displaystyle F_{j}=f(\alpha ^{j})=\sum _{i=0}^{l}L_{i}(\alpha ^{jk_{i}})}$。

適切な基底で展開すると、 となり、線形化多項式の性質により、 ${\displaystyle \alpha ^{jk_{i}}\in \mathrm {GF} (p^{m_{i}})}$${\displaystyle \{\beta _{i,0},\beta _{i,1},\ldots ,\beta _{i,m_{i}-1}\}}$${\displaystyle \alpha ^{jk_{i}}=\sum _{s=0}^{m_{i}-1}a_{ijs}\beta _{i,s}}$${\displaystyle a_{ijs}\in \mathrm {GF} (p)}$${\displaystyle L_{i}(x)}$

${\displaystyle F_{j}=\sum _{i=0}^{l}\sum _{s=0}^{m_{i}-1}a_{ijs}\left(\sum _{t=0}^{m_{i}-1}\beta _{i,s}^{p^{t}}f_{p^{t}k_{i}{\bmod {N}}}\right)}$

この式は、行列形式では と書き直すことができます。ここで、 はGF( p ) 上の行列で、はブロック対角行列、 は円分剰余類指数に従っての要素を再グループ化する置換行列です。 ${\displaystyle \mathbf {F} =\mathbf {AL\Pi f} }$${\displaystyle \mathbf {A} }$${\displaystyle N\times N}$${\displaystyle a_{ijs}}$${\displaystyle \mathbf {L} }$${\displaystyle \mathbf {\Pi } }$${\displaystyle \mathbf {f} }$

正規基底 を使用して の体要素を展開する場合、 の i 番目のブロックは次のように与えられることに注意してください。 ${\displaystyle \{\gamma _{i}^{p^{0}},\gamma _{i}^{p^{1}},\cdots ,\gamma _{i}^{p^{m_{i}-1}}\}}$${\displaystyle \mathrm {GF} (p^{m_{i}})}$${\displaystyle \mathbf {L} }$

${\displaystyle \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}}}$

これは巡回行列です。巡回行列ベクトル積は畳み込みによって効率的に計算できることはよく知られています。したがって、離散フーリエ変換を短い畳み込みに減らすことに成功しました。

特性-2の体GF(2 ^m )に適用すると、行列は単なる2元行列になります。との行列ベクトル積を計算するときは、加算のみが使用されます。 円分アルゴリズムの乗法計算量は で与えられ、加法計算量は で与えられることが示されています。^[2]${\displaystyle \mathbf {A} }$${\displaystyle \mathrm {A} }$${\displaystyle \mathrm {L\Pi f} }$${\displaystyle O(n(\log _{2}n)^{\log _{2}{\frac {3}{2}}})}$${\displaystyle O(n^{2}/(\log _{2}n)^{\log _{2}{\frac {8}{3}}})}$