{"id":75,"date":"2017-12-28T05:48:07","date_gmt":"2017-12-27T20:48:07","guid":{"rendered":"http:\/\/mell0w-5phere.net\/jaded5phere\/2017\/12\/28\/2017-12-28-054807\/"},"modified":"2023-03-15T20:48:41","modified_gmt":"2023-03-15T11:48:41","slug":"speana-fft","status":"publish","type":"post","link":"https:\/\/mell0w-5phere.net\/jaded5phere\/2017\/12\/28\/speana-fft\/","title":{"rendered":"\u3010Processing\u3011\u30b9\u30da\u30af\u30c8\u30e9\u30e0\u30a2\u30ca\u30e9\u30a4\u30b6\u306e\u5b9f\u88c5\u3010FFT\u3011"},"content":{"rendered":"

\u3055\u3066\u3001\u524d\u56de<\/a>\u306fProcessing\u3092\u4f7f\u3063\u3066wave\u30d5\u30a1\u30a4\u30eb\u306e\u30c7\u30fc\u30bf\u8aad\u307f\u3053\u307f\u30fb\u6ce2\u5f62\u8868\u793a\u307e\u3067\u5b9f\u88c5\u3057\u305f\u3002\u4eca\u56de\u304c\u5c71\u5834\u3001\u30b9\u30da\u30a2\u30ca\u306e\u5b9f\u88c5\u3067\u3042\u308b\u3002\u307f\u3093\u306a\u5927\u597d\u304dFFT(\u9ad8\u901f\u30d5\u30fc\u30ea\u30a8\u5909\u63db)\u3067\u30b9\u30da\u30af\u30c8\u30e9\u30e0\u3092\u8a08\u7b97\u3059\u308b\u3002<\/p>\n

\u30b9\u30da\u30a2\u30ca\u306e\u30d7\u30ed\u30b0\u30e9\u30e0\u3088\u308a\u3080\u3057\u308dFFT\u306b\u3064\u3044\u3066\u304b\u306a\u308a\u306e\u91cf\u3092\u5272\u3044\u3066\u8aac\u660e\u3057\u3066\u3044\u308b\u306e\u3067\u3001\u305c\u3072\u8aad\u3093\u3067\u6b32\u3057\u3044(\u3067\u304d\u308b\u3060\u3051\u308f\u304b\u308a\u3084\u3059\u304f\u66f8\u3044\u305f\u3064\u3082\u308a\u306a\u306e\u3060\u304c...)\u3002<\/p>\n

\n

\u30fb\u30d5\u30fc\u30ea\u30a8\u5909\u63db\u3068\u306f<\/h3>\n

\u307e\u305a\u306f\u8efd\u304f\u30d5\u30fc\u30ea\u30a8\u5909\u63db\u306b\u3064\u3044\u3066\u89e6\u308c\u3066\u304a\u304f\u3002\u30d5\u30fc\u30ea\u30a8\u5909\u63db\u3068\u306f\u3001\u300c\u6642\u9593\u306b\u3064\u3044\u3066\u306e\u975e\u5468\u671f\u95a2\u6570\u3092\u3001\u5468\u6ce2\u6570\u306e\u7570\u306a\u308b\u6b63\u5f26\u6ce2\u306e\u91cd\u306d\u5408\u308f\u305b\u3067\u8868\u3059\u300d\u3053\u3068\u3067\u3042\u308b\u3002\u305d\u3057\u3066\u3069\u306e\u5468\u6ce2\u6570\u304c\u3069\u308c\u3060\u3051\u542b\u307e\u308c\u3066\u3044\u308b\u304b\u3092\u8868\u3059\u306e\u304c\u632f\u5e45\u30b9\u30da\u30af\u30c8\u30eb\u3067\u3042\u308b\u3002
\n\u30d5\u30fc\u30ea\u30a8\u5909\u63db\u306f(1)\u5f0f\u306e\u3088\u3046\u306b\u5b9a\u7fa9\u3055\u308c\u308b\u3002\u3053\u3053\u3067\u6642\u9593\u9818\u57df\u306e\u95a2\u6570\\(f(t)\\),\u5468\u6ce2\u6570\u9818\u57df\u306e\u95a2\u6570\\( F(\\omega)\\)\u306f\u3044\u305a\u308c\u3082\u9023\u7d9a<\/b>\u306a\u8907\u7d20<\/b>\u95a2\u6570\u3067\u3042\u308b\u3002<\/p>\n

$$F(\\omega)=\\int_{-\\infty}^{\\infty} f(t)e^{-i\\omega t}\\mathrm{d}t\\quad\\cdots(1)$$<\/p>\n

\u30fb\u96e2\u6563\u6642\u9593\u30d5\u30fc\u30ea\u30a8\u5909\u63db<\/h3>\n

\u3068\u3053\u308d\u304c\u3001\u5b9f\u969b\u306e\u97f3\u58f0\u30c7\u30fc\u30bf\u3092\u30d5\u30fc\u30ea\u30a8\u5909\u63db\u306b\u304b\u3051\u3088\u3046\u3068\u601d\u3063\u305f\u6642\u3001\u305d\u306e\u30c7\u30fc\u30bf\u306f\u4e00\u5b9a\u6642\u9593\u304a\u304d\u306b\u30b5\u30f3\u30d7\u30ea\u30f3\u30b0\u3055\u308c\u305f\u3082\u306e\u3001\u3064\u307e\u308a\u96e2\u6563\u7684\u306a\u3082\u306e\u3067\u3001\u9023\u7d9a\u7684\u3067\u306f\u306a\u3044\u3002
\n\u305d\u3053\u3067\u3001\u307e\u305a\u96e2\u6563\u6642\u9593\u3067\u306e\u30d5\u30fc\u30ea\u30a8\u5909\u63db\u3092\u8a66\u307f\u308b\u3002\u3053\u306e\u97f3\u58f0\u30c7\u30fc\u30bf\u304c\u6574\u6570\\(n\\)\u3092\u7528\u3044\u3066\\( f[n]\\)\u3068\u8868\u3055\u308c\u308b\u3068\u304d\u3001\u305d\u306e\u96e2\u6563\u6642\u9593\u30d5\u30fc\u30ea\u30a8\u5909\u63db\u306f(2)\u5f0f\u306e\u3088\u3046\u306b\u306a\u308b\u3002
\n$$F(\\omega)=\\sum_{n=-\\infty}^{\\infty} f[n]e^{-i\\omega n}\\quad\\cdots(2)$$<\/p>\n

\u307e\u3042\u7a4d\u5206\u304c\u7dcf\u548c\u306b\u306a\u3063\u305f\u3060\u3051\u3067\u3042\u308b\u3002\u305d\u3057\u3066\u3001\u3053\u306e\\( F(\\omega)\\)\u306f\u5468\u671f\\(2\u03c0\\)\u306e\u5468\u671f\u95a2\u6570\u306b\u306a\u308b*1<\/a>*2<\/a>\u3002<\/p>\n

\u30fb\u96e2\u6563\u30d5\u30fc\u30ea\u30a8\u5909\u63db(DFT: Discrete Fourier Transform)<\/h3>\n

\u3068\u3053\u308d\u304c\u307e\u3060\u554f\u984c\u304c\u3042\u3063\u3066\u3001\u3053\u306e\u307e\u307e\u3060\u3068\u5468\u6ce2\u6570\u9818\u57df\u304c\u9023\u7d9a\u7684\u306a\u306e\u3067\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30fc\u3067\u306f\u6271\u3048\u306a\u3044\u3002\u305d\u3053\u3067\u3001\u7dcf\u548c\u306e\u7bc4\u56f2\u3092\u6709\u9650\u306b\u3057\u3066\u3057\u307e\u3063\u3066\u3001\u305d\u306e\u533a\u9593\u304c\u5ef6\u3005\u3068\u7e70\u308a\u8fd4\u3055\u308c\u308b\u5468\u671f\u95a2\u6570\u306b\u3057\u3066\u3057\u307e\u304a\u3046*3<\/a>\u3068\u3044\u3046\u3053\u3068\u306b\u306a\u3063\u305f\u306e\u304c(3)\u5f0f\u3067\u3042\u308b\u3002
\n$$F(\\omega)=\\sum_{n=0}^{N-1} f[n]e^{-i\\omega n} \\quad \\cdots(3)$$<\/p>\n

\u305f\u3060\u7bc4\u56f2\u304c\\(0\\)\u304b\u3089\\(N-1\\)\u306b\u306a\u3063\u305f\u3060\u3051\u3067\u3042\u308b\u3002\u7dcf\u548c\u306e\u7bc4\u56f2\u304c\\(0\\)\u304b\u3089\\(N-1\\)\u306a\u306e\u3067\u3001\u3053\u306e\\( f[n]\\)\u306f\u5468\u671f\\(N\\)\u3067\u3042\u308a\u3001\u57fa\u672c\u89d2\u5468\u6ce2\u6570\u306f\\(\\displaystyle \\frac{2\\pi}{N}\\)\u306b\u306a\u308b\u3002\u3059\u306a\u308f\u3061\u3001\\(\\omega\\)\u306f\\( \\displaystyle \\frac{2\\pi}{N}\\)\u306e\u6574\u6570\u500d\u306e\u5024\u3092\u53d6\u308b\u3053\u3068\u306b\u306a\u308b\u304b\u3089\u3001\u6574\u6570\\(k\\)\u3092\u7528\u3044\u3066 \\( \\displaystyle \\omega=\\frac{2\\pi k}{N}\\)\u3068\u7f6e\u304d\u63db\u3048\u308b\u3068\u3001(3)\u5f0f\u306f
\n$$F\\left(\\frac{2\\pi k}{N}\\right)= F[k] = \\sum_{n=0}^{N-1} f[n]e^{-i\\frac{2\\pi k}{N} n} \\quad \\cdots(4)$$<\/p>\n

\u3068\u66f8\u304d\u63db\u3048\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u3053\u308c\u304c\u96e2\u6563\u30d5\u30fc\u30ea\u30a8\u5909\u63db\u3067\u3042\u308b\u3002
\n\u307e\u305f\u3001\\( F(\\omega)\\)\u304c\u5468\u671f\\(2\\pi\\)\u3067\u3042\u3063\u305f\u3053\u3068\u3092\u8003\u3048\u308c\u3070\u3001\\( F[k]\\)\u304c\u5468\u671f\\(N\\)\u3067\u3042\u308b\u3053\u3068\u3082\u308f\u304b\u308b\u3002\u3064\u307e\u308a\\( f[n], F[k]\\)\u306f\u3068\u3082\u306b\u96e2\u6563\u7684\u3067\u3001\u304b\u3064\u5468\u671f\\(N\\)\u3067\u5468\u671f\u7684\u306a\u306e\u3067\u3042\u308b\u3002<\/p>\n

\u30fb\u9ad8\u901f\u30d5\u30fc\u30ea\u30a8\u5909\u63db(FFT: Fast Fourier Transform)<\/h3>\n

\u3068\u308a\u3042\u3048\u305a(4)\u5f0f\u3055\u3048\u3042\u308c\u3070\u8a08\u7b97\u306f\u3067\u304d\u308b\u306e\u3060\u304c\u3001\\(0\\leq n < N, 0\\leq k < N\\) \u306a\u306e\u3067\u771f\u9762\u76ee\u306b\u3084\u308b\u3068\u8a08\u7b97\u91cf\u304c\\( O(N^2)\\)\u5fc5\u8981\u306b\u306a\u308b\u3002
\n\\(N\\)\u304c\u5c0f\u3055\u3044\u3046\u3061\u306f\u305d\u3053\u305d\u3053\u65e9\u304f\u7d42\u308f\u308b\u304c\u3001\\(N\\)\u304c\u5927\u304d\u304f\u306a\u3063\u3066\u304f\u308b\u3068\u6642\u9593\u304c\u304b\u304b\u308a\u3059\u304e\u308b\u3068\u3044\u3046\u3053\u3068\u3067\u9ad8\u901f\u5316\u3057\u305f\u306e\u304cFFT\u3067\u3042\u308b\u3002<\/p>\n

\u5b9f\u306fFFT\u3092\u4f7f\u3046\u306b\u306f\u5236\u9650\u304c\u3042\u3063\u3066\u3001\\(N\\)\u304c2\u306e\u7d2f\u4e57\u3067\u306a\u3051\u308c\u3070\u306a\u3089\u306a\u3044\u3002\u305d\u306e\u7406\u7531\u306f\u3059\u3050\u308f\u304b\u308b\u306e\u3067\u3001\u307e\u305a\u306fFFT\u306e\u539f\u7406\u3092\u8aac\u660e\u3057\u3066\u3044\u304f\u3002<\/p>\n

FFT\u3067\u306f\u3001(5)\u5f0f\u306e\u3088\u3046\u306b\u307e\u305a\\(n\\)\u306e\u5076\u5947\u3067\u9805\u3092\u5206\u3051\u308b\u3002
\n$$F[k] = \\sum_{n=0}^{\\frac{N}{2}-1} f[2n]e^{-i\\frac{2\\pi k}{N}\\cdot 2n}+\\sum_{n=0}^{\\frac{N}{2}-1} f[2n+1]e^{-i\\frac{2\\pi k}{N}\\cdot (2n+1)}\\quad\\cdots(5)$$<\/p>\n

\\(e\\)\u306e\u53f3\u80a9\u304c\u30b4\u30c1\u30e3\u30b4\u30c1\u30e3\u3059\u308b\u306e\u3067\u3001\\( \\displaystyle W=e^{-i\\frac{2\\pi}{N}}\\)\u3068\u7f6e\u304d\u63db\u3048\u308b\u3002\u3059\u308b\u3068(5)\u5f0f\u306f(6)\u5f0f\u306e\u3088\u3046\u306b\u306a\u308b\u3002<\/p>\n

$$F[k] = \\sum_{n=0}^{\\frac{N}{2}-1} f[2n]W^{k\\cdot 2n}+W^k\\sum_{n=0}^{\\frac{N}{2}-1} f[2n+1]W^{k\\cdot 2n}\\quad\\cdots(6)$$<\/p>\n

\u3064\u307e\u308a\u5947\u6570\u306e\u9805\u306b\u306f\\( W^k\\)\u304c\u304b\u304b\u308b\u3002<\/p>\n

\u305d\u3057\u3066\u3001\u305d\u308c\u305e\u308c\u306e\u9805\u306b\u3064\u3044\u3066\u307e\u305f\\(n\\)\u306e\u5076\u5947\u304c\u5206\u3051\u3089\u308c\u3066(7)\u5f0f\u306e\u3088\u3046\u306b\u306a\u308b\u3002
\n\u4eca\u5ea6\u306f\u5947\u6570\u306e\u9805\u306b\\( W^{2k}\\)\u304c\u304b\u304b\u3063\u3066\u3044\u308b\u3002
\n$$\\begin{alignat*}{3}
\nF[k] &=& && &\\sum_{n=0}^{\\frac{N}{4}-1} f[4n]W^{k\\cdot 4n} &\\;+\\; W^{2k}&\\sum_{n=0}^{\\frac{N}{4}-1} f[4n+2]W^{k\\cdot 4n}\\\\
\n&& &+ W^k& &\\sum_{n=0}^{\\frac{N}{4}-1} f[4n+1]W^{k\\cdot 4n} &\\;+\\; W^{k}W^{2k}&\\sum_{n=0}^{\\frac{N}{4}-1} f[4n+3]W^{k\\cdot 4n}\\quad\\cdots(7)
\n\\end{alignat*}$$<\/p>\n

\u305d\u3057\u3066\u3053\u308c\u3092\\(\\log N\\)\u56de\u7e70\u308a\u8fd4\u3059\u3068\u3001(8)\u56f3\u306e\u3088\u3046\u306b\u306a\u3063\u3066\u3057\u307e\u3046\u306e\u3067\u3042\u308b\u3002\\(N\\)\u304c2\u306e\u7d2f\u4e57\u3067\u306a\u3051\u308c\u3070\u306a\u3089\u306a\u3044\u7406\u7531\u304c\u304a\u308f\u304b\u308a\u3044\u305f\u3060\u3051\u305f\u3060\u308d\u3046\u304b\u3002
\n(\u56f3\u306f\\(N=8\\)\u306e\u3068\u304d\u3002\u3084\u3063\u3064\u3051\u306a\u306e\u306f\u52d8\u5f01\u3057\u3066\u307b\u3057\u3044\u3002)<\/p>\n

\"\"<\/p>\n

...(8)<\/div>\n

\u3053\u308c\u3067\u3001\u5404\u3005\u306e\\(k\\)\u306b\u3064\u3044\u3066\\(F[k]\\)\u304c\\(O(N\\log N)\\)\u3067\u6c42\u3081\u3089\u308c\u308b..........<\/p>\n

........???????????<\/p>\n

\u305d\u308c\u305e\u308c\u306e\\(k\\)\u306b\u3064\u3044\u3066\\(O(N\\log N)\\)\u3067\u8a08\u7b97\u3059\u308b\u306e\u3060\u304b\u3089\u3001\u6700\u7d42\u7684\u306a\u8a08\u7b97\u91cf\u304c
\n\\( O(N^2 \\log N)\\)\u306b\u306a\u3063\u3066\u3080\u3057\u308d\u60aa\u5316\u3057\u3066\u3044\u308b\u3002\u3042\u308c\u308c\uff5e\u304a\u304b\u3057\u3044\u305e\uff5e\u3002(\u68d2\u8aad\u307f)<\/p>\n

\u30fb\\( e^{i\\theta} = \\cos\\,\\theta + i\\sin\\,\\theta\\) \u306e\u4f7f\u3044\u3069\u3053\u308d<\/h3>\n

\u3053\u306e\u8b0e\u3092\u89e3\u304f\u9375\u306f\u3001\u300c\\(W\\)\u304c\\(k\\)\u306b\u3064\u3044\u3066\u306e\u8907\u7d20\u6307\u6570\u95a2\u6570\u3001\u3059\u306a\u308f\u3061\u5468\u671f\u7684<\/b>\u3067\u3042\u308b\u300d\u3068\u3044\u3046\u3068\u3053\u308d\u306b\u3042\u308b\u3002\\( \\displaystyle W=e^{-i\\frac{2\\pi}{N}}\\)\u306a\u306e\u3060\u304b\u3089\u3001
\n$$\\begin{alignat*}{2}
\nW^{k+N}&=&&e^{-i\\frac{2\\pi}{N}(k+N)}&&\\\\
\n&=&&e^{-i\\left(\\frac{2\\pi k}{N}+2\\pi\\right)}&&\\\\
\n&=&&e^{-i\\frac{2\\pi k}{N}}&&\\\\
\n&=&&W^k &\\cdots(9)&
\n\\end{alignat*}$$<\/p>\n

\u304c\u6210\u308a\u7acb\u3064\u306e\u3067\u3042\u308b\u3002<\/p>\n

\u8a66\u3057\u306b(8)\u56f3\u306b\\( F[4]\\)\u3092\u66f8\u304d\u52a0\u3048\u3066\u307f\u308b\u3068(10)\u56f3\u306e\u3088\u3046\u306b\u306a\u308b\u3002<\/p>\n

\"\"<\/div>\n
...(10)<\/div>\n

\u8d64\u67a0\u306e\u4e2d\u306f\\( F[0]\\)\u306e\u8a08\u7b97\u7d50\u679c\u3092\u6d41\u7528\u3067\u304d\u308b\u306e\u304c\u308f\u304b\u308b\u3060\u308d\u3046\u304b\u3002
\n\u305d\u3057\u3066\u305d\u308c\u3092\\( F[0]\\)\u304b\u3089\\( F[N]\\)\u307e\u3067\u7e26\u306b\u4e26\u3079\u3066\u91cd\u306d\u305f\u306e\u304c\u3044\u308f\u3086\u308b\u30d0\u30bf\u30d5\u30e9\u30a4\u30c0\u30a4\u30a2\u30b0\u30e9\u30e0\u3060...\u56f3(11)\u3002<\/p>\n

\"\"<\/div>\n
...(11)<\/div>\n

\u8d64\u7834\u7dda\u3068\u305d\u306e\u53f3\u7aef\u306e\u6570\u5b57\u306f\u3001\\(W\\)\u3092\u305d\u306e\u6570\u5b57\u306e\u5206\u3060\u3051\u51aa\u4e57\u3057\u3066\u8db3\u3059\u3068\u3044\u3046\u610f\u5473\u3067\u3042\u308b\u3002
\n\u3053\u308c\u3092\u3001\u9ed2\u7834\u7dda\u3067\u533a\u5207\u3089\u308c\u305f\u90e8\u5206\u3092\u4e00\u3064\u306e\u30e6\u30cb\u30c3\u30c8\u3068\u3057\u3066\u5de6\u304b\u3089\u8a08\u7b97\u3057\u3066\u3044\u3051\u3070\u3001\u30e6\u30cb\u30c3\u30c8\u5f53\u305f\u308a\\(O(N)\\)\u3001\u305d\u308c\u304c\\(\\log N\\)\u30e6\u30cb\u30c3\u30c8\u3042\u308b\u306e\u3067\u3001\u6674\u308c\u3066\\(O(N\\log N)\\)\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u5b8c\u6210\u3067\u3042\u308b\u3002<\/p>\n

\u30fb\u30d3\u30c3\u30c8\u9006\u8ee2<\/h3>\n

\u3053\u3053\u3067\u3001\u5de6\u5074\u306e\\( f[n]\\)\u306e\u6570\u5b57\u306e\u4e26\u3073\u306b\u6238\u60d1\u3063\u305f\u4eba\u3082\u3044\u308b\u306e\u3067\u306f\u306a\u3044\u3060\u308d\u3046\u304b\u3002\u7d50\u8ad6\u304b\u3089\u8a00\u3063\u3066\u3057\u307e\u3046\u3068\u3001\u30d3\u30c3\u30c8\u304c\u9006\u8ee2\u3057\u3066\u3044\u308b\u306e\u3067\u3042\u308b\u3002\u53cd\u8ee2\u3067\u306f\u306a\u3044\u3001\u9006\u8ee2\u3067\u3042\u308b\u3002
\n\u4f8b\u3048\u3070\\(N=8\\)\u306e\u3068\u304d\u3001\u4e0a\u304b\u30892\u9032\u6570\u3067000->100->010->110->001->101->011->111<\/code>\u3068\u306a\u3063\u3066\u3044\u308b\u3002\u3053\u306e\u305d\u308c\u305e\u308c\u3092\u9006\u304b\u3089\u8aad\u3093\u3067\u307f\u308b\u3068\u3001000->001->010->011->100->101->110->111<\/code>\u3068\u306a\u3063\u3066\u3061\u3083\u3093\u3068\u9806\u756a\u306b\u306a\u3063\u3066\u3044\u308b\u3002
\n\u8003\u3048\u3066\u307f\u308c\u3070\u7279\u306b\u4e0d\u601d\u8b70\u3067\u3082\u306a\u3093\u3067\u3082\u306a\u304f\u3001\u5076\u5947\u3059\u306a\u308f\u3061\u4e0b\u4f4d\u30d3\u30c3\u30c8\u304c0\u304b1\u304b\u3067\u9805\u3092\u5206\u3051\u3066\u3044\u308b\u306e\u3060\u304b\u3089\u305d\u308a\u3083\u9006\u8ee2\u3059\u308b\u308f\u306a\u3001\u3068\u3044\u3046\u611f\u3058\u3067\u3042\u308b\u3002<\/p>\n

\u3053\u3053\u307e\u3067\u3067\u7406\u8ad6\u306f\u7d42\u308f\u308a\u3067\u3001\u3042\u3068\u306f\u5b9f\u969b\u306b\u5b9f\u88c5\u3057\u3066\u3044\u304f\u3002<\/p>\n

\u30fb\u3084\u3063\u3068Processing\u306e\u51fa\u756a<\/h3>\n

\u524d\u8ff0\u306e\u3068\u304a\u308a\u30d5\u30fc\u30ea\u30a8\u5909\u63db\u306f\u8907\u7d20\u95a2\u6570\u306b\u3064\u3044\u3066\u5b9a\u7fa9\u3055\u308c\u3066\u3044\u308b\u306e\u3067\u3001\u7c21\u5358\u306b\u81ea\u524d\u306e\u8907\u7d20\u6570\u30af\u30e9\u30b9\u3092\u7528\u610f\u3057\u3066\u307f\u305f\u3002<\/p>\n

class Complex{\r\n\tprivate double re;\r\n\tprivate double im;\r\n\t\r\n\tpublic Complex(double real,double imaginary){\r\n\t\tre=real;\r\n\t\tim=imaginary;\r\n\t}\r\n\t\r\n\tpublic Complex(double radius,float arg){\r\n\t\tre=radius*cos(arg);\r\n\t\tim=radius*sin(arg);\r\n\t}\r\n\t\r\n\tpublic double Re(){\r\n\t\treturn re;\r\n\t}\r\n\t\r\n\tpublic double Im(){\r\n\t\treturn im;\r\n\t}\r\n\t\r\n\tpublic void Add(Complex c){\r\n\t\tre+=c.Re();\r\n\t\tim+=c.Im();\r\n\t}\r\n\t\r\n\tpublic Complex Product(Complex c){\r\n\t\treturn new Complex(re*c.Re()-im*c.Im(),re*c.Im()+im*c.Re());\r\n\t}\r\n\t\r\n\tpublic double Abs(){\r\n\t\tdouble re_sq=re*re;\r\n\t\tdouble im_sq=im*im;\r\n\t\treturn Math.pow(re_sq+im_sq,0.5);\r\n\t}\r\n\t\r\n\tpublic String toString(){\r\n\t\treturn String.format(\"%f+%fi\",re,im);\r\n\t}\r\n}<\/code><\/pre>\n<\/p>\n
\u4f7f\u3046\u306e\u306f\u548c\u3001\u7a4d\u3001\u5927\u304d\u3055\u304f\u3089\u3044\u306a\u306e\u3067\u6700\u5c0f\u9650\u3057\u304b\u7528\u610f\u3057\u3066\u3044\u306a\u3044\u3002
\n\u30b3\u30f3\u30b9\u30c8\u30e9\u30af\u30bf\u306b\u306f\\(a+bi\\)\u306e\u5f62\u3068\u3001\\(W\\)\u306e\u8a08\u7b97\u3067\u4fbf\u5229\u306a\u306e\u3067\u6975\u5f62\u5f0f\\( r({\\rm cos}\\,\\theta +i{\\rm sin}\\,\\theta)\\)\u306e\u4e21\u65b9\u3092\u7528\u610f\u3057\u3066\u307f\u305f(\u30c9\u30fb\u30e2\u30a2\u30d6\u30eb\u4e07\u6b73)\u3002toString()<\/code>\u306f\u30c7\u30d0\u30c3\u30b0\u7528\u306b\u3064\u3051\u3066\u307f\u305f\u3089\u6848\u5916\u4fbf\u5229\u3060\u3063\u305f\u3002<\/p>\n
\\(W\\)\u306e\u7d2f\u4e57\u306f\u4e8b\u524d\u306b\u8a08\u7b97\u3057\u3066\u304a\u3044\u3066\u914d\u5217\u306b\u683c\u7d0d\u3057\u3066\u304a\u304f\u3002\u305d\u3053\u307e\u3067\u8efd\u91cf\u5316\u306b\u3053\u3060\u308f\u3063\u3066\u306f\u3044\u306a\u3044\u306e\u3067\\(N\\)\u901a\u308a\u5168\u90e8\u8a08\u7b97\u3057\u3066\u3044\u308b\u3002<\/p>\n
W=new Complex[N];\r\nfor(int i=0;i<N;i++){\r\n\tW[i]=new Complex(1,-2*i*P\/N); \/\/\u6975\u5ea7\u6a19\u8868\u8a18\u304c\u6d3b\u8e8d\r\n}\r\n<\/code><\/pre>\n<\/p>\n
\u305d\u308c\u3068\u3001\u30d3\u30c3\u30c8\u9006\u8ee2\u306e\u914d\u5217\u3082\u4f5c\u3063\u3066\u304a\u304f\u3002\u3053\u308c\u306f\u67d0\u6240\u3067\u898b\u3064\u3051\u305f\u30d3\u30c3\u30c8\u9006\u8ee2\u30a4\u30f3\u30af\u30ea\u30e1\u30f3\u30c8\u306e\u30b3\u30fc\u30c9\u3092\u305d\u306e\u307e\u307e\u5199\u3057\u305f\u3002
\n\u8ab0\u304c\u8003\u3048\u305f\u306e\u304b\u77e5\u3089\u306a\u3044\u304c\u3001\u3088\u304f\u3082\u307e\u3042\u3053\u3093\u306a\u306e\u304c\u601d\u3044\u3064\u304f\u3082\u306e\u3060\u3002<\/p>\n
void ReverseIncrement(){\r\n\trevBit=new int[N];\r\n\tint p=0;\r\n\tint m=1<<power;\r\n\t\r\n\tfor(int i=1;i<N;i++){\r\n\t\trevBit[i-1]=p;\r\n\t\tp^=m-m\/2\/(i&(-i&m-1));\r\n\t}\r\n\trevBit[N-1]=p;\r\n}\r\n<\/code><\/pre>\n<\/p>\n
\u7a93\u95a2\u6570\u3082\u5fd8\u308c\u3066\u306f\u3044\u3051\u306a\u3044*4<\/a>\u3002\u4eca\u56de\u306f\u77e9\u5f62\u7a93\u3001\u30b5\u30a4\u30f3\u7a93\u3001\u30cf\u30f3(\u30cf\u30cb\u30f3\u30b0)\u7a93\u3001\u30cf\u30df\u30f3\u30b0\u7a93\u3001\u30d6\u30e9\u30c3\u30af\u30de\u30f3\u7a93\u3001Vorbis\u7a93\u306a\u3069\u3092\u81ea\u7531\u306b\u5207\u308a\u66ff\u3048\u3089\u308c\u308b\u3088\u3046\u306b\u3057\u3066\u307f\u305f\u3002<\/p>\n
float Window(int i){\r\n\tswitch(window){\r\n\t\tcase 0:return 1; \/\/Rect\r\n\t\tcase 1:return sin(P*i\/N); \/\/Sine\r\n\t\tcase 2:return 0.5-0.5*cos(2*P*i\/N); \/\/Hann\r\n\t\tcase 3:return 0.54-0.46*cos(2*P*i\/N); \/\/Hamming\r\n\t\tcase 4:return 0.42-0.5*cos(2*P*i\/N)+0.08*cos(4*P*i\/N);\/\/Blackman\r\n\t\tcase 5:return sin(P\/2*pow(sin(P*i\/N),2)); \/\/Vorbis\r\n\t\tdefault:return 0;\r\n\t}\r\n}\r\n<\/code><\/pre>\n<\/p>\n
\u3053\u3053\u307e\u3067\u304d\u305f\u3089\u6e96\u5099\u5b8c\u4e86\u3002\u3042\u3068\u306fFFT\u3092\u7d44\u3093\u3067\u3044\u304f\u3002<\/p>\n
void FFT(){\r\n\tif(timePos+N>sampleNum)return;\r\n\tComplex[] prev=new Complex[N];\r\n\tComplex[] next=new Complex[N];\r\n\t\r\n\tfor(int i=0;i<N;i++){\r\n\t\tprev[i]=new Complex(Window(revBit[i])*waveData[0][timePos+revBit[i]],0);\r\n\t\tnext[i]=new Complex(0,0);\r\n\t}\r\n\t\r\n\tfor(int i=0;i<power;i++){\r\n\t\tint k=1<<i;\r\n\t\t\r\n\t\tfor(int j=0;j<N;j++){\r\n\t\t\tif(j%(k*2)<k){\r\n\t\t\t\tnext[j].Add(prev[j]);\r\n\t\t\t\tnext[j+k].Add(prev[j]); \/\/...(12)\r\n\t\t\t}else{\r\n\t\t\t\tint w=N\/k\/2;\r\n\t\t\t\tnext[j].Add(prev[j].Product(W[w*(j%(k*2))]));\r\n\t\t\t\tnext[j-k].Add(prev[j].Product(W[w*((j-k)%(k*2))]));\r\n\t\t\t\t\/\/...(13) \r\n\t\t\t}\r\n\t\t}\r\n\t\t\r\n\t\tSystem.arraycopy(next,0,prev,0,N); \/\/...(14)\r\n\t\tnext=new Complex[N];\r\n\t\tfor(int a=0;a<N;a++)next[a]=new Complex(0,0);\r\n\t}\r\n\t\r\n\tfor(int i=0;i<N;i++){\r\n\t\tfreqData[i]=prev[i].Abs(); \/\/...(15)\r\n\t}\r\n}\r\n<\/code><\/pre>\n<\/p>\n
\u7d30\u304b\u3044\u8aac\u660e\u306f\u7701\u304f\u304c\u3001\u5076\u6570\u5074\u306e\u3068\u304d\u306f\u305d\u306e\u307e\u307e\u8db3\u3057...(12)\u3001\u5947\u6570\u5074\u306e\u3068\u304d\u306f\\(W\\)\u306e\u51aa\u4e57\u3092\u304b\u3051\u3066\u304b\u3089\u8db3\u3057\u3066\u3044\u308b...(13)\u3002\u30e6\u30cb\u30c3\u30c8\u3072\u3068\u3064\u306e\u8a08\u7b97\u304c\u7d42\u308f\u3063\u305f\u3089\u914d\u5217\u306e\u4e2d\u8eab\u3092\u79fb\u3057\u66ff\u3048\u3066\u6b21\u306e\u30e6\u30cb\u30c3\u30c8\u306e\u8a08\u7b97\u3092\u3059\u308b...(14)\u3002
\n\u5168\u90e8\u7d42\u308f\u3063\u305f\u3089\u5927\u304d\u3055\u3092\u53d6\u308c\u3070\u632f\u5e45\u30b9\u30da\u30af\u30c8\u30eb\u304c\u5f97\u3089\u308c\u308b...(15)\u3002<\/p>\n
\u3053\u308c\u3067FFT\u304c\u7d42\u308f\u3063\u305f\u306e\u3067\u3001\u3042\u3068\u306f\u30d7\u30ed\u30c3\u30c8\u3059\u308c\u3070\u30b9\u30da\u30a2\u30ca\u304c\u5b8c\u6210\u3059\u308b\u3002<\/p>\n
void PlotFreq(){\r\n\ttranslate(0,height-25);\r\n\ttextAlign(CENTER,BOTTOM);\r\n\ttext(String.format(\"Amp:%s, Freq:%s, Sample:%.0f, Window:%s\",\r\n\t\t\tlogAmp?\"Log\":\"Linear\",logFreq?\"Log\":\"Linear\",  \/\/...(18)\r\n\t\t\tpow(2,power),windowName),width\/2,-5);\r\n\tnyqFreq=logFreq?log(sampleRate\/2):sampleRate\/2;\r\n\tfundFreq=logFreq?log(sampleRate\/N):sampleRate\/N;\r\n\tfreqWidth=nyqFreq-fundFreq;\r\n\t\r\n\tfor(int i=1;i<=N\/2;i++){\r\n\t\tfloat freq=(float)sampleRate\/N*i;\r\n\t\tfloat freqPos=logFreq?log(freq):freq; \/\/...(16)\r\n\t\tfloat pos=20+(freqPos-fundFreq)\/freqWidth*localWidth;\r\n\t\t\t\/\/...(20)\r\n\t\tfloat val=(float)freqData[i];\r\n\t\tfloat fLevel=Float.NaN;\r\n\t\t\r\n\t\tif(logAmp){ \/\/...(17)\r\n\t\t\tfloat v=log(val)+thres;\r\n\t\t\tfLevel=50*fAmpZoom*(v>0?v:0);\r\n\t\t}else{\r\n\t\t\tfLevel=ampRate[power-10]*fAmpZoom*val;\r\n\t\t}\r\n\t\t\r\n\t\tif(fLevel>height){\r\n\t\t\tfLevel=height;\r\n\t\t\tstroke(255,0,0); \/\/...(20)\r\n\t\t}else{\r\n\t\t\tstroke(255);\r\n\t\t}\r\n\t\t\r\n\t\tline(pos,-30,pos,-fLevel-30);\r\n\t\ttextAlign(i==1?LEFT:RIGHT,BOTTOM);\r\n\t\tif(i==1||i==N\/2)text(String.format(\"%.0f\",freq),pos,-5);\r\n\t\t\/\/...(19)\r\n\t}\r\n\tstroke(255);\r\n\tline(20,-30,width-20,-30);\r\n}<\/code><\/pre>\n<\/p>\n
\u5927\u304d\u306a\u30dd\u30a4\u30f3\u30c8\u3068\u3057\u3066\u306f\u4e21\u8ef8\u305d\u308c\u305e\u308c\u30ea\u30cb\u30a2\/\u5bfe\u6570\u3092\u5207\u308a\u66ff\u3048\u3089\u308c\u308b\u3088\u3046\u306b\u3057\u305f\u308a...(16,17)\u3001\u8ef8\u306e\u30b9\u30b1\u30fc\u30eb\u3084FFT\u306e\\(N\\)\u306e\u5024\u3084\u7a93\u95a2\u6570\u306e\u7a2e\u985e\u3001\u57fa\u672c\u5468\u6ce2\u6570\u3068\u30ca\u30a4\u30ad\u30b9\u30c8\u5468\u6ce2\u6570\u3092\u4e0b\u90e8\u306b\u8868\u793a\u3057\u305f\u308a\u3057\u3066\u3044\u308b...(18,19)\u3002\u307e\u305f\u3001\u30b9\u30b1\u30fc\u30eb\u3092\u5207\u308a\u66ff\u3048\u3066\u3082\u5168\u4f53\u306e\u5e45\u304c\u4e00\u5b9a\u306b\u306a\u308b\u3088\u3046\u306b\u8a08\u7b97\u3057\u3066\u3044\u308b...(20)\u3002
\n\u7d30\u304b\u3044\u3068\u3053\u308d\u3068\u3057\u3066\u306f\u3001\u632f\u5e45\u306e\u5024\u304c\u753b\u9762\u5916\u306b\u51fa\u308b\u30ec\u30d9\u30eb\u306e\u3068\u304d\u306f\u30d0\u30fc\u304c\u8d64\u304f\u306a\u308b\u3088\u3046\u306b\u3057\u3066\u307f\u305f\u308a\u3057\u3066\u3044\u308b...(21)\u3002<\/p>\n
\u5b9f\u969b\u306b\u52d5\u3044\u3066\u3044\u308b\u306e\u304c\u3053\u3061\u3089\u3002<\/p>\n
\"\"<\/p>\n
Fast\u3068\u8b33\u3046\u3060\u3051\u3042\u3063\u3066\\(N=16384\\)\u3067\u308230fps\u306f\u5805\u3044\u3002\u3080\u3057\u308d\u30d7\u30ed\u30c3\u30c8\u3059\u308b\u307b\u3046\u304c\u91cd\u3044\u307e\u3067\u3042\u308b\u3002<\/p>\n
\n
\u4ee5\u4e0a\u3067\u30b9\u30da\u30a2\u30ca\u304c\u5b8c\u6210\u3057\u305f\u3002\u3057\u304b\u3057\u3001\u3053\u3053\u307e\u3067\u3067\u306f\u6ce2\u5f62\u3068\u30b9\u30da\u30a2\u30ca\u306e\u6620\u50cf\u3057\u304b\u306a\u304f\u3066\u7269\u8db3\u308a\u306a\u3044\u306e\u3067\u6b21\u56de\u306f\u97f3\u58f0\u3092\u3064\u3051\u3066\u3044\u304f\u3002<\/p>\n
\u3053\u3093\u306a\u306b\u9577\u3044\u8a18\u4e8b\u3092\u66f8\u3044\u305f\u306e\u306f\u521d\u3081\u3066\u3067\u30e1\u30c1\u30e3\u30af\u30c1\u30e3\u6642\u9593\u304c\u304b\u304b\u3063\u305f\u304c\u3001\u3044\u3044\u5fa9\u7fd2\u306b\u306a\u3063\u305f\u3002<\/p>\n
\u4f59\u8ac7:\u300c2\u03c0\/N\u300d\u306e\u300c\u03c0\/\u300d\u306e\u90e8\u5206\u3092\u03c0\u30b9\u30e9\u30c3\u30b7\u30e5\u3068\u8aa4\u8a8d\u3055\u308c\u3066\u3044\u308b\u3088\u3046\u3067\u5927\u5909\u907a\u61be\u3067\u3059\u3002<\/del><\/p>\n","protected":false},"excerpt":{"rendered":"
\u3055\u3066\u3001\u524d\u56de\u306fProcessing\u3092\u4f7f\u3063\u3066wave\u30d5\u30a1\u30a4\u30eb\u306e\u30c7\u30fc\u30bf\u8aad\u307f\u3053\u307f\u30fb\u6ce2\u5f62\u8868\u793a\u307e\u3067\u5b9f\u88c5\u3057\u305f\u3002\u4eca\u56de\u304c\u5c71\u5834\u3001\u30b9\u30da\u30a2\u30ca\u306e\u5b9f\u88c5\u3067\u3042\u308b\u3002\u307f\u3093\u306a\u5927\u597d\u304dFFT(\u9ad8\u901f\u30d5\u30fc\u30ea\u30a8\u5909\u63db)\u3067\u30b9\u30da\u30af\u30c8\u30e9\u30e0\u3092\u8a08\u7b97\u3059\u308b\u3002 \u30b9\u30da\u30a2\u30ca\u306e\u30d7\u30ed\u30b0\u30e9\u30e0\u3088\u308a<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[28,27,29],"_links":{"self":[{"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/posts\/75"}],"collection":[{"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/comments?post=75"}],"version-history":[{"count":10,"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/posts\/75\/revisions"}],"predecessor-version":[{"id":1237,"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/posts\/75\/revisions\/1237"}],"wp:attachment":[{"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/media?parent=75"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/categories?post=75"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mell0w-5phere.net\/jaded5phere\/wp-json\/wp\/v2\/tags?post=75"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}