離散フーリエ変換 (一般)のソースを表示


数学において、[[環 (数学)|環]]上の'''離散フーリエ変換'''は、[[複素数]]上の[[離散フーリエ変換]]を一般化したものである。

== 定義 ==
<math>R</math> を任意の[[環 (数学)|環]]、<math>n\geq 1</math> を自然数とする。<math>\alpha \in R</math> を、<math>R</math> の単位元の主 <math>n</math> 乗根(principal root)であり次式を満たす要素とする<ref name="furer">Martin Fürer, "[https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Faster Integer Multiplication]", STOC 2007 Proceedings, pp. 57&#x2013;66. Section 2: The Discrete Fourier Transform.</ref>

: <math>
\begin{align}
& \alpha^n = 1 \\
& \sum_{j=0}^{n-1} \alpha^{jk} = 0 \text{ for } 1 \leq k < n \qquad (1)
\end{align}
</math>

離散フーリエ変換は、<math>R</math> の要素の''n''個組 <math>(v_0,\ldots,v_{n-1})</math> を、次の計算式により <math>R</math> の要素の''n''個組 <math>(f_0,\ldots,f_{n-1})</math> へ写像する。

: <math>f_k = \sum_{j=0}^{n-1} v_j\alpha^{jk}.\qquad (2)</math>

慣例により、<math>(v_0,\ldots,v_{n-1})</math> は''時間領域''にあると言い、添え字 <math>j</math> を''時刻''と呼ぶ。また、<math>(f_0,\ldots,f_{n-1})</math> は''周波数領域''にあると言い、<math>k</math> を''周波数''と呼ぶ。また、<math>(f_0,\ldots,f_{n-1})</math> は<math>(v_0,\ldots,v_{n-1})</math>の''[[周波数スペクトル]]''とも呼ばれる。この用語は、フーリエ変換の[[信号処理]]への応用からきている。

もし環 <math>R</math> が[[整域]]（[[体 (数学)|体]]の場合を含む)であるとき、<math>\alpha</math>は単位元の[[冪根|原始''n''乗根]]であれば十分であり、条件式(1)は、以下で置き換えることができる。<ref name="furer" />

: <math>\alpha^{k} \ne 1</math> for <math>1 \leq k < n</math>

証明：<math>1 \leq k < n</math>に対して、<math>\beta = \alpha^k</math> と置く。<math>\alpha^n=1</math> であるから、<math>\beta^n=(\alpha^n)^k=1</math> であり、

: <math>\beta^n-1 = (\beta-1)\left(\sum_{j=0}^{n-1} \beta^j\right) = 0</math>

が成り立つ。<math>\alpha</math> は原始''n''乗根であるから、<math>\beta - 1 \ne 0</math> が成り立つ。 <math>R</math> が整域であれば、零因子を持たないため、和 <math>\sum_{j=0}^{n-1} \beta^j</math> は零である。∎

もう一つのシンプルな条件は、''n''が２のべき乗のときである。この場合、条件式(1)は <math>\alpha^{n/2} = -1</math> でおきかえることができる。<ref name="furer" />

== 逆変換 ==
逆離散フーリエ変換は、以下の式で与えられる：

: <math>v_j = \frac{1}{n}\sum_{k=0}^{n-1} f_k\alpha^{-jk}.\qquad (3)</math>

ここで、<math>1/n</math> は <math>R</math> における <math>n</math> の乗法逆元である。（もしこれが存在しないならば、DFTは逆変換できない。）

証明：式(2)を式(3)の右辺に代入すると

: <math>
\begin{align}
& \frac{1}{n}\sum_{k=0}^{n-1} f_k\alpha^{-jk} \\
= {} & \frac{1}{n}\sum_{k=0}^{n-1}\sum_{j'=0}^{n-1} v_{j'}\alpha^{j'k}\alpha^{-jk} \\
= {} & \frac{1}{n}\sum_{j'=0}^{n-1} v_{j'} \sum_{k=0}^{n-1}\alpha^{(j'-j)k}.
\end{align}
</math>

が得られる。<math>j'\neq j</math> ならば <math>\sum_{k=0}^{n-1}\alpha^{(j'-j)k}=0</math> であり（式(1)で <math>k=j'-j</math> と置けばよい）、 <math>j'=j</math> ならば <math>\sum_{k=0}^{n-1}\alpha^{(j'-j)k}=n</math> が成り立つので、上の式は <math>v_j</math> とちょうど一致する。∎

== 行列表現 ==
離散フーリエ変換は[[線形写像]]であるから、[[行列の乗法|行列積]]で表現できる。行列表現では、離散フーリエ変換は以下のように書ける。

: <math>
\begin{bmatrix}f_0\\f_1\\\vdots\\f_{n-1}\end{bmatrix}
= \begin{bmatrix}
1&1&1&\cdots &1 \\
1&\alpha&\alpha^2&\cdots&\alpha^{n-1} \\
1&\alpha^2&\alpha^4&\cdots&\alpha^{2(n-1)}\\
\vdots&\vdots&\vdots&&\vdots\\
1&\alpha^{n-1}&\alpha^{2(n-1)}&\cdots&\alpha^{(n-1)(n-1)}\\
\end{bmatrix}
\begin{bmatrix}v_0\\v_1\\\vdots\\v_{n-1}\end{bmatrix}
</math>

この行列は、DFT行列と呼ばれる。

同様に、逆離散フーリエ変換は

: <math>
\begin{bmatrix}v_0\\v_1\\\vdots\\v_{n-1}\end{bmatrix}
= \frac{1}{n}\begin{bmatrix}
1&1&1&\cdots &1 \\
1&\alpha^{-1}&\alpha^{-2}&\cdots&\alpha^{-(n-1)} \\
1&\alpha^{-2}&\alpha^{-4}&\cdots&\alpha^{-2(n-1)}\\
\vdots&\vdots&\vdots&&\vdots\\
1&\alpha^{-(n-1)}&\alpha^{-2(n-1)}&\cdots&\alpha^{-(n-1)(n-1)}
\end{bmatrix}
\begin{bmatrix}f_0\\f_1\\\vdots\\f_{n-1}\end{bmatrix}
</math>

と表せる。

== 多項式表現<ref>R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999, pp. 217–219.</ref> ==
''n''個組 <math>(v_0,\ldots,v_{n-1})</math> を <math>n-1</math> 次の多項式

: <math>p_v(x) = v_0 + v_1x + v_2x^2 + \cdots + v_{n-1}x^{n-1} </math>

と見做すと便利なことがある。離散フーリエ変換の定義式(2)の和を書き下すと、

: <math>f_k = v_0 + v_1\alpha^{k} + v_2\alpha^{2k}  + \cdots + v_{n-1}\alpha^{(n-1)k} </math>

となる。つまり、<math>f_k</math> は多項式 <math>p_v(x)</math> の <math>x=\alpha^k</math> における値であり、

: <math>f_k = p_v(\alpha^k) </math>

と書ける。したがって、離散フーリエ変換は、多項式の''係数''を''値''に変換するもの考えることができる。係数は時間領域で、値は周波数領域にある。もちろん、多項式の値は、単位元の<math>n</math> 乗根（<math>\alpha</math> とその2乗、3乗、4乗、...）において評価することが重要である。

同様に、逆離散フーリエ変換の式(3)を書き下すと

: <math>v_j = \frac{1}{n}(f_0 + f_1\alpha^{-j} + f_2\alpha^{-2j}  + \cdots + f_{n-1}\alpha^{-(n-1)j}) \qquad (5)</math>

である。多項式を

: <math>p_f(x) = f_0 + f_1x + f_2x^2 + \cdots + f_{n-1}x^{n-1}</math>

とすれば、

: <math>v_j = \frac{1}{n}p_f(\alpha^{-j})</math>

が成り立つ。

以上をまとめると、以下のようになる。 もし、多項式 <math>p(x)</math> の値が多項式 <math>q(x)</math> の係数であるならば、（定数倍と順番の入れ替えを除けば）<math>q(x)</math> の値は <math>p(x)</math> の係数と等しい。

== 特殊な場合 ==

=== 複素数 ===
環として複素数体 <math>F={\mathbb C}</math> を考えると、1の<math>n</math>乗根は[[複素平面]]上の[[単位円]]上にある。

: <math>\alpha=e^{\frac{-2\pi i}{n}}</math>

と定義すれば、通常の[[離散フーリエ変換]]の式

: <math>f_k = \sum_{j=0}^{n-1} v_j e^{\frac{-2\pi i}{n}jk}</math>

が得られる。

正規化のため、逆方向の変換IDFT（式(3)）では係数 <math>\frac{1}{n}</math> がかかるが、複素数の離散フーリエ変換においては、係数 <math>\frac{1}{\sqrt{n}}</math> を順方向の変換DFTと逆方向の変換IDFTの両方にかけることもある。この正規化方法だと、DFT行列は[[ユニタリ行列]]となる。 （<math>\sqrt{n}</math> は、任意の体においては意味を持たないことに注意。）

=== 有限体 ===
環として有限体 <math>F=GF(q)</math> （<math>q</math> は素数のべき乗）を考えた場合には、 単位元の原始''n''乗根の存在は自動的に <math>n</math> が <math>q-1</math> を割り切ることを意味する。 これは、各元の[[位数]]は体 <math>F</math> の[[乗法群]]のサイズを必ず割り切り、乗法群のサイズは <math>q-1</math> であることから言える。 これは、特に <math>n=\underbrace{1+1+\cdots+1}_{n\ \rm times}</math> が乗法逆元を持つことを保証し、式(3)における <math>\frac{1}{n}</math> はその逆元である。<!-- 
An application of the discrete Fourier transform over <math>GF(q)</math> is the reduction of [[Reed–Solomon code]]s to [[BCH code]]s in [[coding theory]]. Such transform can be carried out efficiently with proper fast algorithms, for example, [[cyclotomic fast Fourier transform]].  --><math>GF(q)</math> 上での離散フーリエ変換の応用として、[[符号理論]]における[[リード・ソロモン符号]]や[[BCH符号]]の復号がある。これは、[[円分高速フーリエ変換]]といった効率の良いアルゴリズムによって実行可能である。

=== 数論変換 ===
'''数論変換'''（number-theoretic transform, NTT、あるいは数論的変換）は、環を <math>F={\mathbb Z}/p{\mathbb Z}</math> に限定した場合の離散フーリエ変換である。{{mvar|p}}が素数ならば <math>F</math> は有限体であり、単位元の原始{{mvar|n}}乗根は {{mvar|n}} が <math>p-1</math> を割り切るとき、つまり、ある正の整数 {{mvar|&xi;}} を用いて <math>p=\xi n+1</math> と書けるときには、必ず存在する。特に、単位元の原始{{mvar|(p-1)}}乗根が <math>\omega</math> であれば、原始{{mvar|n}}乗根は <math>\alpha=\omega^{\xi}</math> で得られる.

具体例）<math>p=5</math>、<math>n=4</math>、<math>\alpha = 2</math> の場合、

: <math>\begin{align}2^{1}&=2 \pmod 5\\2^{2}&=4 \pmod 5\\2^{3}&=3 \pmod 5\\2^{4}&=1 \pmod 5\end{align}</math>

: <math>
\begin{bmatrix}
F(0) \\
F(1) \\
F(2) \\
F(3) \end{bmatrix}
=
 \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 3 \\
1 & 4 & 1 & 4 \\
1 & 3 & 4 & 2 \end{bmatrix}
\begin{bmatrix}
f(0) \\
f(1) \\
f(2) \\
f(3) \end{bmatrix}
</math>

数論変換は、法{{mvar|m}}が素数でない場合の[[環 (数学)|環]] <math>\mathbb{Z}/m\mathbb{Z}</math> においても、位数が{{mvar|n}}である主要根が存在するならば、意味がある。[[ショーンハーゲ・ストラッセン法]]で用いられるフェルマー数変換（{{math|1=''m'' = 2<sup>''k''</sup>+1}}）や、メルセンヌ数変換（{{math|1=''m'' = 2<sup>''k''</sup>&nbsp;&minus;&nbsp;1}}）のような特殊な数論変換は、法として合成数を用いている。<!-- 
===離散重み付き変換===
The '''離散重み付き変換 (discrete weighted transform, DWT)'''は、離散フーリエ変換のバリエーションである。変換前の列に重みベクトルを要素ごとに掛けて重み付けし、変換後の列には別のベクトルにより重み付けする。<ref>{{Citation | last = Crandall | first = Richard | last2 = Fagin | first2 = Barry | title = Discrete weighted transforms and large-integer arithmetic | journal = Mathematics of Computation | volume = 62 | issue = 205 | year = 1994 | pages = 305&ndash;324 | url = http://www.faginfamily.net/barry/Papers/Discrete%20Weighted%20Transforms.pdf | doi=10.2307/2153411}}</ref> [[Irrational base discrete weighted transform]] はこれの特殊な場合である。
--> 

== 性質 ==
[[離散フーリエ変換|複素数上のDFT]]が持つ重要な特徴、例えば逆変換、[[畳み込み定理]]、多くの[[高速フーリエ変換]](FFT) アルゴリズムなどは、変換の核が単位元の主要根であるという性質のみに依存している。したがって、一般化した離散フーリエ変換も同じ特徴を持つ（任意の環において、同様に証明できる）。<!-- In the case of fields, this analogy can be formalized by the field with one element, considering any field with a primitive nth root of unity as an algebra over the extension field <math>\mathbf{F}_{1^n}</math> ：翻訳が上手くできない -->特に、計算量が <math>O(n \log n)</math> の[[高速フーリエ変換]]アルゴリズムをNTTに適用できることと、畳み込み定理が成り立つことから、数論変換を利用することで、整数列の畳み込みを効率よく正確に計算できる。複素数上のDFTでも畳み込みを効率よく計算できるが、有限精度の浮動小数演算において[[丸め誤差]]が生じる恐れがある。一方NTTでは、固定サイズの整数しか扱わず、厳密に値を表現できるため、丸めの誤差は生じない。

== 高速なアルゴリズム ==
高速なアルゴリズム実装のためには、（複素数上の[[離散フーリエ変換]]を計算する[[高速フーリエ変換]]アルゴリズムの場合と同様に）変換したい入力の長さ''n''は小さな素数から成る合成数（典型的なのは[[2の冪]]）が望ましいことが良くある。しかし、WangとZhuのアルゴリズム<ref>Yao Wang and Xuelong Zhu, "A fast algorithm for the Fourier transform over finite fields and its VLSI implementation", IEEE Journal on Selected Areas in Communications 6(3)572–577, 1988</ref>のように、有限体の場合に特化したフーリエ変換アルゴリズムも存在しており、それらは''n''の因数分解に寄らず効率が良い。

== 関連項目 ==

* （複素関数における）[[離散フーリエ変換]]
* [[ガウス和]]
* [[畳み込み]]
* [[Multiplication algorithm]]
* [[高速フーリエ変換]](FFT)
* [[フーリエ級数]]
* [[フーリエ変換]]
* [[Z変換]]
* [[直交関数系]]
* [[離散時間フーリエ変換]]

== 参考文献 ==
{{reflist}}<!-- <references/> -->

== 外部リンク ==

* http://www.apfloat.org/ntt.html

{{DEFAULTSORT:りさんふうりえへんかん}}

[[Category:フーリエ解析]]
[[Category:数値解析]]
[[Category:信号処理]]
[[Category:ユニタリ作用素]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]