離散フーリエ変換 (一般)

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

定義

${\displaystyle R}$ を任意の環、${\displaystyle n\geq 1}$ を自然数とする。${\displaystyle \alpha \in R}$ を、${\displaystyle R}$ の単位元の主 ${\displaystyle n}$ 乗根(principal root)であり次式を満たす要素とする^[1]

${\displaystyle {\begin{aligned}&\alpha ^{n}=1\\&\sum _{j=0}^{n-1}\alpha ^{jk}=0{\text{ for }}1\leq k<n\qquad (1)\end{aligned}}}$

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

${\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}\alpha ^{jk}.\qquad (2)}$

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

もし環 ${\displaystyle R}$ が整域（体の場合を含む)であるとき、${\displaystyle \alpha }$は単位元の原始n乗根であれば十分であり、条件式(1)は、以下で置き換えることができる。^[1]

${\displaystyle \alpha ^{k}\neq 1}$ for ${\displaystyle 1\leq k<n}$

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

${\displaystyle \beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0}$

が成り立つ。${\displaystyle \alpha }$ は原始n乗根であるから、${\displaystyle \beta -1\neq 0}$ が成り立つ。 ${\displaystyle R}$ が整域であれば、零因子を持たないため、和 ${\displaystyle \sum _{j=0}^{n-1}\beta ^{j}}$ は零である。∎

もう一つのシンプルな条件は、nが２のべき乗のときである。この場合、条件式(1)は ${\displaystyle \alpha ^{n/2}=-1}$ でおきかえることができる。^[1]

逆変換

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

${\displaystyle v_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}.\qquad (3)}$

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

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

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

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

行列表現

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

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

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

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

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

と表せる。

多項式表現[2]

n個組 ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ を ${\displaystyle n-1}$ 次の多項式

${\displaystyle p_{v}(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1}}$

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

${\displaystyle f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}}$

となる。つまり、${\displaystyle f_{k}}$ は多項式 ${\displaystyle p_{v}(x)}$ の ${\displaystyle x=\alpha ^{k}}$ における値であり、

${\displaystyle f_{k}=p_{v}(\alpha ^{k})}$

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

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

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

である。多項式を

${\displaystyle p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1}}$

とすれば、

${\displaystyle v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j})}$

が成り立つ。

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

特殊な場合

複素数

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

${\displaystyle \alpha =e^{\frac {-2\pi i}{n}}}$

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

${\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}e^{{\frac {-2\pi i}{n}}jk}}$

が得られる。

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

有限体

環として有限体 ${\displaystyle F=GF(q)}$ （${\displaystyle q}$ は素数のべき乗）を考えた場合には、 単位元の原始n乗根の存在は自動的に ${\displaystyle n}$ が ${\displaystyle q-1}$ を割り切ることを意味する。 これは、各元の位数は体 ${\displaystyle F}$ の乗法群のサイズを必ず割り切り、乗法群のサイズは ${\displaystyle q-1}$ であることから言える。 これは、特に ${\displaystyle n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}}$ が乗法逆元を持つことを保証し、式(3)における ${\displaystyle {\frac {1}{n}}}$ はその逆元である。${\displaystyle GF(q)}$ 上での離散フーリエ変換の応用として、符号理論におけるリード・ソロモン符号やBCH符号の復号がある。これは、円分高速フーリエ変換といった効率の良いアルゴリズムによって実行可能である。

数論変換

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

具体例）${\displaystyle p=5}$、${\displaystyle n=4}$、${\displaystyle \alpha =2}$ の場合、

${\displaystyle {\begin{aligned}2^{1}&=2{\pmod {5}}\\2^{2}&=4{\pmod {5}}\\2^{3}&=3{\pmod {5}}\\2^{4}&=1{\pmod {5}}\end{aligned}}}$

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

数論変換は、法mが素数でない場合の環 ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ においても、位数がnである主要根が存在するならば、意味がある。ショーンハーゲ・ストラッセン法で用いられるフェルマー数変換（m = 2^k+1）や、メルセンヌ数変換（m = 2^k − 1）のような特殊な数論変換は、法として合成数を用いている。

性質

複素数上のDFTが持つ重要な特徴、例えば逆変換、畳み込み定理、多くの高速フーリエ変換(FFT) アルゴリズムなどは、変換の核が単位元の主要根であるという性質のみに依存している。したがって、一般化した離散フーリエ変換も同じ特徴を持つ（任意の環において、同様に証明できる）。特に、計算量が ${\displaystyle O(n\log n)}$ の高速フーリエ変換アルゴリズムをNTTに適用できることと、畳み込み定理が成り立つことから、数論変換を利用することで、整数列の畳み込みを効率よく正確に計算できる。複素数上のDFTでも畳み込みを効率よく計算できるが、有限精度の浮動小数演算において丸め誤差が生じる恐れがある。一方NTTでは、固定サイズの整数しか扱わず、厳密に値を表現できるため、丸めの誤差は生じない。

高速なアルゴリズム

高速なアルゴリズム実装のためには、（複素数上の離散フーリエ変換を計算する高速フーリエ変換アルゴリズムの場合と同様に）変換したい入力の長さnは小さな素数から成る合成数（典型的なのは2の冪）が望ましいことが良くある。しかし、WangとZhuのアルゴリズム^[3]のように、有限体の場合に特化したフーリエ変換アルゴリズムも存在しており、それらはnの因数分解に寄らず効率が良い。

関連項目

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

参考文献

1. Martin Fürer, "Faster Integer Multiplication", STOC 2007 Proceedings, pp. 57–66. Section 2: The Discrete Fourier Transform.
2. R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999, pp. 217–219.
3. 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

外部リンク

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