離散Fourier変換

梅谷 武
作成:2000-08-14 更新:2005-04-20
離散Fourier変換の概念を可換環R上へ一般化し、複素数上や整数の剰余環上の離散Fourier変換の性質や高速算法の議論を統一的に行なえるようにすることを目的とする。最初に離散Fourier変換を可換環R上で定義し、その諸性質を整理する。その上で高速算法について論ずる。
IMS:20000814001; NDC:413.66; keywords:Fourier展開,Fourier変換,畳み込み,群環;
目  次
1. 離散Fourier変換
2. 高速Fourier変換
参考文献
1. 離散Fourier変換
1.1 離散Fourier変換の定義
 可換環R上で離散Fourier変換を定義するには次の条件が必要である。
条件1.1 (離散Fourier変換を定義するための必要条件)
 Rを可換環とする。
  1. ∃n:自然数,∃ζ∈R:ζは1の原始n乗根 (i.e. ζn=1, n>k>0 → ζk≠1)
  2. ∃n-1∈R (i.e. nをRの元とみなしたときにその逆元が存在する)
  3. n>k>0 → i=0n-1ζik=0
 上の条件の下で、ζによって生成される巡回群をG={1,ζ,…,ζn-1}とする。GからRへの関数全体の集合をC(G)={f:G→R}とすると、C(G)にはRから自然に加法と乗法が定義され、それによって可換環となる。さらにスカラー倍を自然に定義することによってR上の多元環となる。
定義1.2 (C(G)上の双線形形式( , ))
 C(G)上の双線形形式( , ):C(G)×C(G)→Rを次のように定義する。
(f,g)=n-1n-1
Σ
i=0
f(ζi)g(ζ-i), f,g∈C(G)
 上の定義でζ-in-iであることに注意せよ。これがR上の双線形形式になることは明らかなので証明は略す。次の定理は、C(G)がこの双線形形式について直交な基底をもつことを示す。
定理1.3 (C(G)上の標準直交基底とそのFourier展開)
 k=0,…,n-1についてeki)=ζikによってek:C(G)→Rを定義すると{ek:k=0,…,n-1}C(G)の直交基底となる。すなわち、任意のf∈C(G)は、
f=n-1
Σ
i=0
(f,ei)ei
と一意的に表現することができる。これをfのFourier展開と呼ぶ。
証明 
(ek,el)
=
n-1n-1
Σ
i=0
ζikζ-il
=
n-1n-1
Σ
i=0
ζi(k-l)
ここで、条件3.を使うと
(ek,el)
=
0, k≠l
(ek,el)
=
1, k=l
となり、{ek:k=0,…,n-1}が互いに直交していることがわかる。i=0n-1λiei=0と仮定すると、k=0,…,n-1に対して
λk
=
n-1
Σ
i=0
λi(ei,ek)
=
(n-1
Σ
i=0
λiei,ek)
=
0
となるから、{ek:k=0,…,n-1}は線形独立である。f∈C(G),k=0,…,n-1について、
n-1
Σ
i=0
(f,ei)eik)
=
n-1
Σ
i=0
(n-1n-1
Σ
l=0
f(ζl-ilik
=
n-1n-1
Σ
l=0
f(ζl)(n-1
Σ
i=0
ζi(k-l))
=
n-1f(ζk)(n-1
Σ
i=0
ζ0)
=
f(ζk)
となることから証明が終了する。ここでも条件3.が使われている。 ■
 Fourier変換及び逆Fourier変換を定義する。
定義1.4 (Fourier変換・逆Fourier変換)
 Fourier変換F:C(G)→C(G)を次のように定義する。
F(f)(ζk)=n-1
Σ
s=0
f(ζssk, f∈C(G), k=0,…,n-1
逆Fourier変換F-1:C(G)→C(G)を次のように定義する。
F-1(f)(ζr)=n-1n-1
Σ
t=0
f(ζt-tr, f∈C(G), r=0,…,n-1
1.2 離散Fourier変換の性質
定理1.5 (R-加群としての同型性)
 Fourier変換F:C(G)→C(G)はR-加群としての同型写像を与え、逆Fourier変換F-1はその逆写像である。
証明 線形性は明らかである。条件3.を使うことによって以下のように同型性を示すことができる。
F-1・F(f)(ζr)
=
n-1n-1
Σ
t=0
F(f)(ζt-tr
=
n-1n-1
Σ
t=0
(n-1
Σ
s=0
f(ζsst-tr
=
n-1n-1
Σ
s=0
f(ζs)(n-1
Σ
t=0
ζt(s-r))
=
n-1f(ζr)(n-1
Σ
t=0
ζ0)
=
f(ζr)
F・F-1(f)(ζk)
=
n-1
Σ
s=0
F-1(f)(ζssk
=
n-1
Σ
s=0
(n-1n-1
Σ
t=0
f(ζt-tssk
=
n-1n-1
Σ
t=0
f(ζt)(n-1
Σ
s=0
ζs(k-t))
=
n-1f(ζk)(n-1
Σ
s=0
ζ0)
=
f(ζk)
 C(G)にはRから誘導される自然な積の他に、畳み込みと呼ばれる積を定義することができる。
定義1.6 (C(G)上の畳み込み)
 f,g∈C(G)に対して、畳み込みf*g∈C(G)を次のように定義する。
f*g(ζr)=n-1
Σ
i=0
f(ζr-i)g(ζi), r=0,…,n-1
 C(G)はこの畳み込みを積としても可換環となり、さらにR上の多元環となる。これをGR上の群環と呼び、R[G]と書く。C(G)R[G]R-加群としては同じものであるが、積の違いを区別するために記号を使い分ける。
命題1.7
 R[G]R上の可換な多元環である。
  1. δ∈R[G]:δ(1)=1, δ(ζi)=0, i=1,…,n-1 とすると f*δ=f, f∈R[G]
  2. f*g=g*f, f,g∈R[G]
  3. f*(g*h)=(f*g)*h, f,g,h∈R[G]
  4. f*(g+h)=f*g+f*h, f,g,h∈R[G]
  5. (λf)*g=λ(f*g), λ∈R, f,g∈R[G]
証明 1.は直接計算する。
f*δ(ζr)
=
n-1
Σ
i=0
f(ζr-i)δ(ζi)
=
f(ζr)
2.はr-i=tと変数変換すればよい。
f*g(ζr)
=
n-1
Σ
i=0
f(ζr-i)g(ζi)
=
n-1
Σ
i≡0(mod n)
f(ζr-i)g(ζi)
=
r
Σ
t=r-(n-1)
f(ζt)g(ζr-t)
=
g*f(ζr)
3.は可換性を利用する。
f*(g*h)(ζr)
=
n-1
Σ
i=0
(g*h)(ζr-i)f(ζi)
=
n-1
Σ
i=0
(n-1
Σ
j=0
g(ζ(r-i)-j)h(ζj))f(ζi)
=
n-1
Σ
j=0
(n-1
Σ
i=0
g(ζ(r-j)-i)f(ζi))h(ζj)
=
n-1
Σ
j=0
(f*g)(ζr-j)h(ζj)
=
(f*g)*h(ζr)
4.と5.は明らかである。 ■
定理1.8 (R-多元環としての同型性)
 Fourier変換F:R[G]→C(G)R-多元環としての同型写像を与え、逆Fourier変換F-1はその逆写像である。すなわち、同値な性質
  1. F(f*g)=F(f)F(g), f,g∈R[G]
  2. F-1(fg)=F-1(f)*F-1(g), f,g∈C(G)
  3. F(fg)=F(f)*F(g), f,g∈C(G)
  4. F-1(f*g)=F-1(f)F-1(g), f,g∈R[G]
が成り立つ。
証明 1.のみを証明すればよい。
F(f*g)(ζi)
=
n-1
Σ
s=0
f*g(ζssi
=
n-1
Σ
s=0
(n-1
Σ
t=0
f(ζs-t)g(ζt)si
=
n-1
Σ
s=0
n-1
Σ
t=0
f(ζs-t(s-t)ig(ζtti
=
n-1
Σ
t=0
(n-1
Σ
s=0
f(ζs-t(s-t)i)g(ζtti
=
n-1
Σ
t=0
F(f)(ζi)g(ζtti
=
F(f)(ζi)F(g)(ζi)
定理1.9 (構造定理)
 R上の多項式環R[X]からR[G]へのR-線形写像を
Xrer, r=0,…,n-1
を線形拡張するように定義する。この核は(Xn-1)であり、R[X]/(Xn-1)R[G]R-加群として同型である。さらに、この同型写像はR-多元環としての同型を与える。
証明 R-加群として同型であることは明らかである。a(X),b(X)∈R[X]/(Xn-1)
a(X)
=
an-1Xn-1++a1X+a0, ai∈R, i=0,…,n-1
b(X)
=
bn-1Xn-1++b1X+b0, bi∈R, i=0,…,n-1
とすると、同型写像は
asa(ζs), btb(ζt)
というような対応により、a,b∈R[G]を定める。c(X)=a(X)b(X)∈R[X]/(Xn-1)とすると
c(X)
=
cn-1Xn-1++c1X+c0, ci∈R
cr
=

Σ
s+t≡r(mod n)
asbt
となるが、この係数は同型写像により、
c(ζr)=n-1
Σ
i=0
a(ζr-i)b(ζi)
に対応するが、これはc=a*bを示している。 ■
 今後、上の対応によってR[X]/(Xn-1)R[G]を同一視する場合がある。その場合、上の記号で多項式の係数ai∈Rの添え字はnを法として考える。もし、i0,…,n-1以外の値をとるときは、暗黙のうちにi ← i%nという変換を施すことにする。
1.3 高速乗算法への応用
 次節で高速Fourier変換について論ずるが、Fourier変換が高速に計算できることを利用してR[X]/(Xn-1)の乗算を高速に行なうことができる。
算法1.10 (多項式の高速乗算法)
 a(X),b(X)∈R[X]/(Xn-1)
a(X)
=
an-1Xn-1++a1X+a0, ai∈R, i=0,…,n-1
b(X)
=
bn-1Xn-1++b1X+b0, bi∈R, i=0,…,n-1
その積c(X)=a(X)b(X)∈R[X]/(Xn-1)
c(X)
=
cn-1Xn-1++c1X+c0, ci∈R
cr
=
n-1
Σ
i=0
ar-ibi
と表現する。この計算を次の手順で行なう。

Step 1.(a0,…,an-1),(b0,…,bn-1)に対して、そのFourier変換(a'0,…,a'n-1),(b'0,…,b'n-1)を計算する。

Step 2. 項毎に乗算して(c'0,…,c'n-1)=(a'0b'0,…,a'n-1b'n-1)とする。

Step 3.(c'0,…,c'n-1)に対して、その逆Fourier変換(c0,…,cn-1)を計算する。

証明 定理1.8と定理1.9はこの算法の正当性を示している。 ■
2. 高速Fourier変換
2.1 Cooley-Tukey型高速算法
補題2.1
 可換環Rが自然数N2Nについて、離散Fourier変換の必要条件を満たし、GN1の原始N乗根ζNから生成される巡回群、G2N1の原始2N乗根ζ2Nから生成される巡回群であり、さらに
ζ2N2=ζN
が成り立ち、GN⊂G2Nとなっていると仮定する。このとき、R[GN]の元に対するFourier変換が高々M回の加算と乗算で計算できるとすれば、R[ζ2N]の元に対するFourier変換は高々2M+6N回の加算と乗算で計算できる。
証明 f∈R[ζ2N]に対して、feven,fodd∈R[ζN]
fevenNu)
=
f(ζ2N2u), u=0,…,N-1
foddNv)
=
f(ζ2N2v+1), v=0,…,N-1
によって定める。fのFourier変換について、次の式が成り立つ。
F(f)(ζ2Nk)
=
2N-1
Σ
i=0
f(ζ2Ni2Nik
=
N-1
Σ
u=0
f(ζ2N2u2N2uk+N-1
Σ
v=0
f(ζ2N2v+12N(2v+1)k
=
N-1
Σ
u=0
fevenNuNuk+N-1
Σ
v=0
foddNvNvkζ2Nk
=
F(feven)(ζNk)+F(fodd)(ζNk2Nk
ζ2Nk, k=0,…,2N-1は高々2N回の乗算で計算できる。また仮定より、F(feven)F(fodd)は高々2M回で計算できる。これらと上の式を利用するとF(f)は高々2M+6N回の加算と乗算で計算できることがわかる。 ■
定理2.2 (Cooley-Tukey型高速算法)
 可換環Rが自然数N=2nとそのすべての約数について、離散Fourier変換の必要条件を満たし、K|NならばGK⊂GNとなっていると仮定する。このとき、ζNが与えられたとすると、R[GN]の元に対するFourier変換は高々n2n+2=4Nlog2N回の加算と乗算で計算できる。
証明 M(n)N=2nの場合にFourier変換の計算に要する加算と乗算の回数を表わす。nに関する帰納法で証明する。n=1のとき、
F(f)(ζ0)
=
f(ζ00+f(ζ10=f(ζ0)+f(ζ1)
F(f)(ζ1)
=
f(ζ00+f(ζ11=f(ζ0)+f(ζ11
より、M(1)=3≦1×21+2となる。M(n)≦n2n+2であると仮定すると補題より、
M(n+1)2M(n)+6×2n2M(n)+8×2n=(n+1)2n+3
となり、帰納法により証明された。 ■
参考文献
Fourier解析
[F1] T. W. Koerner(高橋 陽一郎訳), フーリエ解析大全〈上〉, 朝倉書店, 1996
[F2] T. W. Koerner(高橋 陽一郎訳), フーリエ解析大全〈下〉, 朝倉書店, 1996
[F3] 大浦 拓哉, FFTの概略と設計法
算法
[S1] 野下浩平, 高岡忠雄, 町田元, 基本的算法, 岩波書店, 1983
[S2] D.E.Knuth(中川圭介訳), 準数値算法―算術演算, サイエンス社, 1986
ディジタル信号処理
[D1] 電子情報通信学会, ディジタル信号処理の基礎, コロナ社, 1988