松岡 航太郎
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}
WN=e−i2πN(A0A1A2A3)=(W0W0W0W0W0W1W2W3W0W2W4W6W0W3W6W9)⋅(a0a1a2a3)\begin{aligned} W_N &= e^{-i\frac{2π}{N}}\\ \begin{pmatrix} A_0 \\ A_1 \\ A_2 \\ A_3 \\ \end{pmatrix} &= \begin{pmatrix} W^0 & W^0 & W^0 & W^0 \\ W^0 & W^1 & W^2 & W^3 \\ W^0 & W^2 & W^4 & W^6 \\ W^0 & W^3 & W^6 & W^9 \end{pmatrix} \cdot \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ \end{pmatrix} \end{aligned} WN⎝⎛A0A1A2A3⎠⎞=e−iN2π=⎝⎛W0W0W0W0W0W1W2W3W0W2W4W6W0W3W6W9⎠⎞⋅⎝⎛a0a1a2a3⎠⎞
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]=1N[∑l=0N−1(Ak⋅Bk)ei2πklN]\begin{aligned} 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}}]\\ & = \frac{1}{N}[\sum^{N-1}_{l=0}(A_k \cdot B_k)e^{i\frac{2\pi k l}{N}}] \end{aligned} ck=N1[l=0∑N−1(n=0∑N−1ane−iN2πnk⋅m=0∑N−1bme−iN2πmk)eiN2πkl]=N1[l=0∑N−1(Ak⋅Bk)eiN2πkl]
∑n=0N−1e−i2πlnN={N if l≡0 mod N0 otherwise ∴(e−2πlnN−1)∑n=0N−1e−i2πlnN=∑n=1Ne−i2πlnN−∑n=0N−1e−i2πlnN=e−N2πlnN−1=0\begin{aligned} \sum^{N-1}_{n=0} e^{-i\frac{2\pi l n}{N}} &= \begin{cases}N\ if\ l\equiv 0\bmod{N}\\ 0\ otherwise\end{cases}\\\ ∴ (e^{-\frac{2\pi l n}{N}}-1)\sum^{N-1}_{n=0} e^{-i\frac{2\pi l n}{N}}&=\sum^{N}_{n=1} e^{-i\frac{2\pi l n}{N}}-\sum^{N-1}_{n=0} e^{-i\frac{2\pi l n}{N}}=e^{-N\frac{2\pi l n}{N}}-1=0 \end{aligned} n=0∑N−1e−iN2πln ∴(e−N2πln−1)n=0∑N−1e−iN2πln={N if l≡0modN0 otherwise=n=1∑Ne−iN2πln−n=0∑N−1e−iN2πln=e−NN2πln−1=0
ck=1N[∑l=0N−1(∑n=0N−1ane−i2πnlN⋅∑m=0N−1bme−i2πmlN)ei2πklN]=∑n=0N−1∑m=0N−1anbm(1N∑l=0N−1ei2π[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}}]\\ &= \sum^{N-1}_{n=0}\sum^{N-1}_{m=0}a_nb_m (\frac{1}{N}\sum^{N-1}_{l=0}e^{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]=n=0∑N−1m=0∑N−1anbm(N1l=0∑N−1eiN2π[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}
ck=(e−i2πk2N1N2)∑l=0N2−1[∑n=0N2−1ei2πn2N(an+iaN2+n)e−i2πlnN2⋅∑m=0N2−1ei2πm2N(bm+ibN2+m)e−i2πlmN2]ei2πlkN2=e−i2πk2N[∑n+m=kei2πk2N(an+iaN2+n)(bm+ibN2+m)+∑n+m=k+N2ei2π(k+N2)2N(an+iaN2+n)(bm+ibN2+m)]=∑n+m=k(an+iaN2+n)(bm+ibN2+m)+∑n+m=k+N2i(an+iaN2+n)(bm+ibN2+m)=[∑n+m=k(anbm−aN2+nbN2+m)−∑n+m=k+N2(anbN2+m+aN2+nbm)]+i[∑n+m=k(anbN2+m+aN2+nbn)+∑n+m=k+N2(anbm−aN2+nbN2+m)]\begin{aligned} c_k &= (e^{-i\frac{2\pi k}{2N}}\frac{1}{\frac{N}{2}})\sum^{\frac{N}{2}-1}_{l=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}_{m=0}e^{i\frac{2\pi m}{2N}}(b_{m}+ib_{\frac{N}{2}+m})e^{-i\frac{2\pi l m}{\frac{N}{2}}}]e^{i\frac{2\pi l k}{\frac{N}{2}}}\\ &= e^{-i\frac{2\pi k}{2N}}[\sum_{n+m=k}e^{i\frac{2\pi k}{2N}}(a_n+ia_{\frac{N}{2}+n})(b_m+ib_{\frac{N}{2}+m}) + \sum_{n+m=k+\frac{N}{2}}e^{i\frac{2\pi (k+\frac{N}{2})}{2N}}(a_n+ia_{\frac{N}{2}+n})(b_m+ib_{\frac{N}{2}+m})]\\ &= \sum_{n+m=k}(a_n+ia_{\frac{N}{2}+n})(b_m+ib_{\frac{N}{2}+m}) + \sum_{n+m=k+\frac{N}{2}}i(a_n+ia_{\frac{N}{2}+n})(b_m+ib_{\frac{N}{2}+m})\\ &= [\sum_{n+m=k}(a_nb_m-a_{\frac{N}{2}+n}b_{\frac{N}{2}+m}) - \sum_{n+m=k+\frac{N}{2}}(a_nb_{\frac{N}{2}+m}+a_{\frac{N}{2}+n}b_m)]+i[\sum_{n+m=k}(a_nb_{\frac{N}{2}+m}+a_{\frac{N}{2}+n}b_n) + \sum_{n+m=k+\frac{N}{2}}(a_nb_m-a_{\frac{N}{2}+n}b_{\frac{N}{2}+m})] \end{aligned} ck=(e−i2N2πk2N1)l=0∑2N−1[n=0∑2N−1ei2N2πn(an+ia2N+n)e−i2N2πln⋅m=0∑2N−1ei2N2πm(bm+ib2N+m)e−i2N2πlm]ei2N2πlk=e−i2N2πk[n+m=k∑ei2N2πk(an+ia2N+n)(bm+ib2N+m)+n+m=k+2N∑ei2N2π(k+2N)(an+ia2N+n)(bm+ib2N+m)]=n+m=k∑(an+ia2N+n)(bm+ib2N+m)+n+m=k+2N∑i(an+ia2N+n)(bm+ib2N+m)=[n+m=k∑(anbm−a2N+nb2N+m)−n+m=k+2N∑(anb2N+m+a2N+nbm)]+i[n+m=k∑(anb2N+m+a2N+nbn)+n+m=k+2N∑(anbm−a2N+nb2N+m)]
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