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

環上の離散フーリエ変換

環上の離散[フーリエ変換]は、複素数体上のDFTを一般化した概念です。任意の環Rと自然数n≧1に対し、Rの単位元の主n乗根αを用いて、Rのn個の要素からなるベクトル(v₀, ..., vₙ₋₁)を、別のn個の要素からなるベクトル(f₀, ..., fₙ₋₁)へ変換します。この変換は、以下の式で定義されます。

math
f_k = \sum_{j=0}^{n-1} v_j \alpha^{jk}


ここで、αはRの単位元の主n乗根であり、以下の条件を満たします。

math
\alpha^n = 1 \\
\sum_{j=0}^{n-1} \alpha^{jk} = 0 \quad (1 \le k < n)


この変換において、(v₀, ..., vₙ₋₁)は時間領域、jは時刻、(f₀, ..., fₙ₋₁)は周波数領域、kは周波数と呼ばれ、(f₀, ..., fₙ₋₁)は(v₀, ..., vₙ₋₁)の周波数スペクトルとも呼ばれます。

逆変換

逆離散フーリエ変換は、以下の式で表されます。

math
v_j = \frac{1}{n} \sum_{k=0}^{n-1} f_k \alpha^{-jk}


ただし、1/nは環Rにおけるnの乗法逆元です。逆元が存在しない場合、逆変換はできません。逆変換の導出は、定義式を逆変換の式に代入し、主n乗根の性質を用いることで示せます。

行列表現

DFTは線形写像であるため、行列積で表現できます。DFT行列は、(i, j)成分がαⁱʲであるn×n行列で表されます。逆変換も同様に、DFT行列の逆行列を用いて表現できます。

多項式表現

時間領域のベクトル(v₀, ..., vₙ₋₁)を係数とする多項式pᵥ(x)を考えます。このとき、周波数領域の値fₖは、pᵥ(x)にx = αᵏを代入した値と一致します。すなわち、fₖ = pᵥ(αᵏ)です。逆変換も同様にして多項式を用いて表現できます。

特殊な場合

複素数

環Rを複素数体Cとした場合、αは複素平面上の単位円上に存在し、通常用いられる離散フーリエ変換になります。正規化のため、逆変換に係数1/nをかけるだけでなく、DFTと逆DFTの両方に1/√nをかけることもあります。この正規化により、DFT行列はユニタリ行列となります。

有限体

環Rを有限体GF(q)とした場合、単位元の原始n乗根が存在するための必要十分条件は、nがq-1を割り切ることです。GF(q)上のDFTは、符号理論におけるリード・ソロモン符号やBCH符号の復号などに用いられます。

数論変換

数論変換(NTT)は、環RをZ/pZ(pは素数)に限定した場合のDFTです。pが素数のとき、単位元の原始n乗根が存在するための条件は、nがp-1を割り切ることです。NTTは、整数列の畳み込みを効率的に計算するために用いられ、丸め誤差が発生しません。

性質

環上のDFTは、[複素数]]上のDFTと同様に、逆変換、畳み込み定理などが成立します。また、高速[[フーリエ変換]アルゴリズムを適用することで、計算量をO(n log n)に削減できます。

高速なアルゴリズム

FFTアルゴリズムと同様に、高速なアルゴリズム実装のために、nは小さな素数の積であることが望ましいです。しかし、有限体の場合には、nの因数分解に依存しない効率の良いアルゴリズムも存在します。

もう一度検索