松岡 航太郎
At=∑x=0N−1ax⋅e−i2πtxN,t∈{0,1,...,N−1}A_t = ∑^{N-1}_{x=0} a_x⋅e^{-i\frac{2πtx}{N}},t∈\{0,1,...,N-1\} At=x=0∑N−1ax⋅e−iN2πtx,t∈{0,1,...,N−1}
ax=1N∑t=0N−1At⋅ei2πxtN,x∈{0,1,...,N−1}a_x = \frac{1}{N}∑^{N-1}_{t=0} A_t⋅e^{i\frac{2πxt}{N}},x∈\{0,1,...,N-1\} ax=N1t=0∑N−1At⋅eiN2πxt,x∈{0,1,...,N−1}
ck=1N[∑l=0N−1(∑n=0N−1ane−i2πnkN⋅∑m=0N−1bme−i2πmkN)ei2πklN]c_k = \frac{1}{N}[\sum^{N-1}_{l=0}(\sum^{N-1}_{n=0}a_ne^{-i\frac{2\pi n k}{N}} \cdot \sum^{N-1}_{m=0}b_me^{-i\frac{2\pi m k}{N}})e^{i\frac{2\pi k l}{N}}] ck=N1[l=0∑N−1(n=0∑N−1ane−iN2πnk⋅m=0∑N−1bme−iN2πmk)eiN2πkl]
∑n=0N−1e2πlnN={N if l≡0 mod N0 otherwise\sum^{N-1}_{n=0} e^{\frac{2\pi l n}{N}} = \begin{cases}N\ if\ l\equiv 0\bmod{N}\\ 0\ otherwise\end{cases} n=0∑N−1eN2πln={N if l≡0modN0 otherwise
ck=1N[∑l=0N−1(∑n=0N−1ane−i2πnlN⋅∑m=0N−1bme−i2πmlN)ei2πklN]=1N[∑l=0N−1∑n=0N−1∑m=0N−1anbme−i2π(k−n+m)lN]=∑n+m=kanbm+∑n+m=k+Nanbm\begin{aligned} c_k &= \frac{1}{N}[\sum^{N-1}_{l=0}(\sum^{N-1}_{n=0}a_ne^{-i\frac{2\pi n l}{N}} \cdot \sum^{N-1}_{m=0}b_me^{-i\frac{2\pi m l}{N}})e^{i\frac{2\pi k l}{N}}]\\ &= \frac{1}{N}[\sum^{N-1}_{l=0}\sum^{N-1}_{n=0}\sum^{N-1}_{m=0}a_nb_me^{-i\frac{2\pi (k-n+m)l}{N}}]\\ &= \sum_{n+m = k}a_nb_m + \sum_{n+m = k+N}a_nb_m \end{aligned} ck=N1[l=0∑N−1(n=0∑N−1ane−iN2πnl⋅m=0∑N−1bme−iN2πml)eiN2πkl]=N1[l=0∑N−1n=0∑N−1m=0∑N−1anbme−iN2π(k−n+m)l]=n+m=k∑anbm+n+m=k+N∑anbm
At=∑x=0N−1wxax⋅e−i2πtxN,t∈{0,1,...,N−1}ax=1wxN∑t=0N−1At⋅ei2πxtN,x∈{0,1,...,N−1}\begin{aligned} A_t &= ∑^{N-1}_{x=0} w_xa_x⋅e^{-i\frac{2πtx}{N}},t∈\{0,1,...,N-1\}\\ a_x &= \frac{1}{w_xN}∑^{N-1}_{t=0} A_t⋅e^{i\frac{2πxt}{N}},x∈\{0,1,...,N-1\} \end{aligned} Atax=x=0∑N−1wxax⋅e−iN2πtx,t∈{0,1,...,N−1}=wxN1t=0∑N−1At⋅eiN2πxt,x∈{0,1,...,N−1}
∑l=0N2−11N2e−i2πl2N{∑m=0N2−1[∑n=0N2−1ei2πn2N(an+iaN2+n)e−i2πlnN2⋅∑n=0N2−1ei2πn2N(bn+ibN2+n)e−i2πlnN2]ei2πlmN2}xl=∑l=0N2−1[e−i2πl2N∑n+m=lei2πl2N(an+iaN2+n)(bm+ibN2+m)+∑n+m=l+N2ei2π(l+N2)2N(an+iaN2+n)(bm+ibN2+m)]xl=∑l=0N2−1[∑n+m=l(an+iaN2+n)(bm+ibN2+m)+∑n+m=l+N2i(an+iaN2+n)(bm+ibN2+m)]xl=∑l=0N2−1{[∑n+m=l(anbm−aN2+nbN2+m)−∑n+m=l+N2(anbN2+m+aN2+nbm)]+i[∑n+m=l(anbN2+m+aN2+nbn)+∑n+m=l+N2(anbm−aN2+nbN2+m)]}xl\begin{aligned} \sum^{\frac{N}{2}-1}_{l = 0}&\frac{1}{\frac{N}{2}}e^{-i\frac{2\pi l}{2N}}\{\sum^{\frac{N}{2}-1}_{m=0}[\sum^{\frac{N}{2}-1}_{n=0}e^{i\frac{2\pi n}{2N}}(a_n+ia_{\frac{N}{2}+n})e^{-i\frac{2\pi l n}{\frac{N}{2}}} \cdot \sum^{\frac{N}{2}-1}_{n=0}e^{i\frac{2\pi n}{2N}}(b_n+ib_{\frac{N}{2}+n})e^{-i\frac{2\pi l n}{\frac{N}{2}}}]e^{i\frac{2\pi l m}{\frac{N}{2}}}\}x^l\\ &= \sum^{\frac{N}{2}-1}_{l = 0}[e^{-i\frac{2\pi l}{2N}}\sum_{n+m=l}e^{i\frac{2\pi l}{2N}}(a_n+ia_{\frac{N}{2}+n})(b_m+ib_{\frac{N}{2}+m}) + \sum_{n+m=l+\frac{N}{2}}e^{i\frac{2\pi (l+\frac{N}{2})}{2N}}(a_n+ia_{\frac{N}{2}+n})(b_m+ib_{\frac{N}{2}+m})]x^l\\ &= \sum^{\frac{N}{2}-1}_{l = 0}[\sum_{n+m=l}(a_n+ia_{\frac{N}{2}+n})(b_m+ib_{\frac{N}{2}+m}) + \sum_{n+m=l+\frac{N}{2}}i(a_n+ia_{\frac{N}{2}+n})(b_m+ib_{\frac{N}{2}+m})]x^l \\ &= \sum^{\frac{N}{2}-1}_{l = 0}\{[\sum_{n+m=l}(a_nb_m-a_{\frac{N}{2}+n}b_{\frac{N}{2}+m}) - \sum_{n+m=l+\frac{N}{2}}(a_nb_{\frac{N}{2}+m}+a_{\frac{N}{2}+n}b_m)]+i[\sum_{n+m=l}(a_nb_{\frac{N}{2}+m}+a_{\frac{N}{2}+n}b_n) + \sum_{n+m=l+\frac{N}{2}}(a_nb_m-a_{\frac{N}{2}+n}b_{\frac{N}{2}+m})]\}x^l \end{aligned} l=0∑2N−12N1e−i2N2πl{m=0∑2N−1[n=0∑2N−1ei2N2πn(an+ia2N+n)e−i2N2πln⋅n=0∑2N−1ei2N2πn(bn+ib2N+n)e−i2N2πln]ei2N2πlm}xl=l=0∑2N−1[e−i2N2πln+m=l∑ei2N2πl(an+ia2N+n)(bm+ib2N+m)+n+m=l+2N∑ei2N2π(l+2N)(an+ia2N+n)(bm+ib2N+m)]xl=l=0∑2N−1[n+m=l∑(an+ia2N+n)(bm+ib2N+m)+n+m=l+2N∑i(an+ia2N+n)(bm+ib2N+m)]xl=l=0∑2N−1{[n+m=l∑(anbm−a2N+nb2N+m)−n+m=l+2N∑(anb2N+m+a2N+nbm)]+i[n+m=l∑(anb2N+m+a2N+nbn)+n+m=l+2N∑(anbm−a2N+nb2N+m)]}xl
At=∑x=0N−1ax⋅e−i2πtxN=∑x=0N2−1ax⋅e−i2πtxN+ax+N2⋅e−i2πt(x+N2)N={∑x=0N2−1(ax+ax+N2)⋅e−i2πt2xN2ift≡0 mod 2∑x=0N2−1[(ax−ax+N2)⋅e−i2πxN]⋅e−i2πt−12xN2otherwise\begin{aligned} A_t &= ∑^{N-1}_{x=0} a_x⋅e^{-i\frac{2πtx}{N}}\\ &= ∑^{\frac{N}{2}-1}_{x=0} a_x⋅e^{-i\frac{2πtx}{N}}+a_{x+\frac{N}{2}}⋅e^{-i\frac{2πt(x+\frac{N}{2})}{N}}\\ &=\begin{cases}∑^{\frac{N}{2}-1}_{x=0} (a_{x}+a_{x+\frac{N}{2}})⋅e^{-i\frac{2π\frac{t}{2}x}{\frac{N}{2}}} \qquad if\quad t≡0 \bmod 2\\∑^{\frac{N}{2}-1}_{x=0} [(a_{x}-a_{x+\frac{N}{2}})⋅e^{-i\frac{2πx}{N}}]⋅e^{-i\frac{2π\frac{t-1}{2}x}{\frac{N}{2}}}\qquad otherwise\end{cases} \end{aligned} At=x=0∑N−1ax⋅e−iN2πtx=x=0∑2N−1ax⋅e−iN2πtx+ax+2N⋅e−iN2πt(x+2N)=⎩⎨⎧∑x=02N−1(ax+ax+2N)⋅e−i2N2π2txift≡0mod2∑x=02N−1[(ax−ax+2N)⋅e−iN2πx]⋅e−i2N2π2t−1xotherwise
Radix2FFT(𝐚,start,end) //startとendは最初0とN/ N = start-end n = (start-end)/2 for x from 0 to n-1 temp = aₓ+aₓ₊ₙ aₓ₊ₙ = (aₓ-aₓ₊ₙ)*exp(-i2πx/N) aₓ = temp if(N>2) Radix2FFT(𝐚,start,start+n) Radix2FFT(𝐚,start+n,end)
Radix4FFT(𝐚,start,end) N = start-end if(N==2) s = start //下付きにするため temp = aₛ+aₛ₊₁ aₛ₊₁ = aₛ - aₛ₊₁ aₛ = temp else n = (start-end)/4 for x from 0 to n-1 for j from 0 to 1 l = j*n m = l+2*n temp = aₓ₊ₗ+aₓ₊ₘ aₓ₊ₘ = (aₓ₊ₗ-aₓ₊ₘ)*i //実数部と虚数部の交換と符号反転 aₓ₊ₗ = temp for j from 0 to 1 l = j*2*n m = l+n if(j==0) temp = aₓ₊ₗ+aₓ₊ₘ aₓ₊ₘ = (aₓ₊ₗ-aₓ₊ₘ)*exp(-i2π2x/N) else temp = (aₓ₊ₗ+aₓ₊ₘ)*exp(-i2πx/N) aₓ₊ₘ = (aₓ₊ₗ-aₓ₊ₘ)*exp(-i2π3x/N) aₓ₊ₗ = temp Radix4FFT(𝐚,start,start+n) Radix4FFT(𝐚,start+n,start+2n) Radix4FFT(𝐚,start+2n,start+3n) Radix4FFT(𝐚,start+3n,end)
page_number: true