{"id":65,"date":"2013-08-24T03:53:27","date_gmt":"2013-08-23T19:53:27","guid":{"rendered":"http:\/\/blog.stlover.org\/?p=65"},"modified":"2013-08-28T09:40:46","modified_gmt":"2013-08-28T01:40:46","slug":"%e7%a6%bb%e6%95%a3%e5%82%85%e7%ab%8b%e5%8f%b6%e5%ad%a6%e4%b9%a0","status":"publish","type":"post","link":"http:\/\/blog.xuhao1.me\/?p=65","title":{"rendered":"\u79bb\u6563\u5085\u7acb\u53f6\u5b66\u4e60\u4e4bFFT"},"content":{"rendered":"

FFT\uff0c\u5feb\u901f\u5085\u7acb\u53f6\u53d8\u6362\u662f\u4e2a\u86ee\u6709\u610f\u601d\u7684\u73a9\u610f\uff0c\u5e94\u7528\u5f88\u5e7f\uff0c\u5c24\u5176\u5728\u4fe1\u606f\u5904\u7406\u65b9\u9762\uff0c\u6700\u8fd1\u9700\u8981\u7528\u5230\uff0c\u5c31\u5b66\u5b66\u5566\u3002<\/p>\n

\u4e07\u4e8b\u5f00\u5934\u96be\uff0c\u5148\u505a\u4e2a\u7b80\u5355\u7684\u79bb\u6563\u5085\u7acb\u53f6\u53d8\u6362\u3002<\/p>\n

\u4ec0\u4e48\u662f\u5085\u7acb\u53f6\u53d8\u6362\uff0c\u5c31\u4e0d\u591a\u89e3\u91ca\u4e86\uff0c\u5c31\u662f\u628a\u51fd\u6570\u6253\u6210\u4e00\u5806\u6ce2\uff0c\u4e0d\u61c2\u7684\u8bf7\u51fa\u95e8\u5de6\u8f6c\u53bb\u4ea4\u91cd\u4fee\u8d39\u3002<\/p>\n

<\/p>\n

\u4e00\uff0c\u4ec0\u4e48\u662f\u79bb\u6563\u5085\u7acb\u53f6\u53d8\u6362\uff08DFT\uff09<\/p>\n

\u8be6\u7ec6\u5185\u5bb9\u89c1\uff1ahttp:\/\/zh.wikipedia.org\/wiki\/%E7%A6%BB%E6%95%A3%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2<\/p>\n

\u867d\u7136\u6211\u89c9\u5f97\u6211\u7528\u56fe\u62cd\u5b83\u62cd\u7684\u66f4\u6e05\u695a\u3002<\/p>\n

\u81f3\u4e8e\u79bb\u6563\u5085\u7acb\u53f6\u53d8\u6362\uff0c\u5219\u662f\u5e94\u7528\u4e8e\u5b9e\u8df5\u7684\u5bf9\u4fe1\u53f7\u91c7\u6837\u7684\u5085\u7acb\u53f6\u53d8\u6362\u7b97\u6cd5\uff0c\u65e0\u59a8\u6211\u4eec\u5148\u7528mathematica\u751f\u6210\u4e00\u4e2a4096\u4f4d\u7684\u4fe1\u53f7\uff0c\u501f\u7528mathematica\u6765\u4e86\u89e3\u4e0b\u79bb\u6563\u5085\u7acb\u53f6\u53d8\u6362\uff0c\u6298\u817e\u534a\u5929\u7ec8\u4e8e\u641e\u61c2\u4e86\u79bb\u6563\u5085\u7acb\u53f6\u7684\u5de5\u4f5c\u539f\u7406\u3002\u9996\u5148\u6211\u4eec\u901a\u8fc7\u4e00\u4e2a\u6f14\u793a\u6765\u8bf4\u4e0b.<\/p>\n

\u9996\u5148\u7528mathematica\u505a\u4e86\u4e00\u4e2a\u7b80\u5355\u7684\u51fd\u6570\u53d1\u751f\u5668\u3002<\/p>\n

    \n
  1. (*<\/span>Mathematica<\/span>\u00a0<\/span>Code<\/span>*)<\/span><\/li>\n
  2. SignalMk<\/span>[<\/span>t_<\/span>,<\/span>\u00a0<\/span>Omega<\/span>_<\/span>]<\/span>\u00a0<\/span>:=<\/span>\u00a0<\/span>(<\/span><\/li>\n
  3. \u00a0\u00a0<\/span>Omega<\/span>\u00a0<\/span>=<\/span>\u00a0<\/span>200<\/span>;<\/span><\/li>\n
  4. \u00a0\u00a0f<\/span>[<\/span>x_<\/span>]<\/span>\u00a0<\/span>:=<\/span>\u00a0<\/span>Sin<\/span>[<\/span>x<\/span>*<\/span>Omega<\/span>\/<\/span>4096<\/span>]<\/span>\u00a0<\/span>+<\/span>\u00a0<\/span>Sin<\/span>[<\/span>2<\/span>\u00a0x<\/span>*<\/span>Omega<\/span>\/<\/span>4096<\/span>];<\/span><\/li>\n
  5. \u00a0\u00a0<\/span>Signal<\/span>\u00a0<\/span>=<\/span>\u00a0<\/span>Table<\/span>[<\/span><\/li>\n
  6. \u00a0\u00a0\u00a0\u00a0f<\/span>[<\/span>i<\/span>]<\/span><\/li>\n
  7. \u00a0\u00a0\u00a0\u00a0<\/span>,<\/span>\u00a0<\/span>{<\/span>i<\/span>,<\/span>\u00a0<\/span>1<\/span>,<\/span>\u00a0<\/span>4096<\/span>*<\/span>t<\/span>}];(*\u5047\u8bbe<\/span>1<\/span>\u79d2\u91c7\u6837<\/span>4096<\/span>\u4e2a<\/span>\u00a0<\/span>*)<\/span><\/li>\n
  8. \u00a0\u00a0<\/span>Return<\/span>[<\/span>Signal<\/span>]<\/span>\u00a0<\/span><\/li>\n
  9. \u00a0\u00a0<\/span>)<\/span><\/li>\n<\/ol>\n

    \u6211\u4eec\u5982\u679c\u53d6<\/p>\n

      \n
    1. ListLinePlot<\/span>[<\/span>SignalMk<\/span>[<\/span>0.1<\/span>,<\/span>\u00a0<\/span>200<\/span>]]<\/span><\/li>\n<\/ol>\n

      \u751f\u6210\u4e00\u4e2a\u65f6\u957f0.1\u79d2\uff0comega\u4e3a200\u7684\u56fe\u50cf\u5982\u4e0b<\/p>\n

      \"anal\"<\/a><\/p>\n

       <\/p>\n

      \u4e00\u4e2a\u4e8c\u4e8c\u7684\u56fe\u50cf\uff0c\u4e8e\u662f\u6211\u4eec\u628a\u5b83\u6254\u5230mathematica\u81ea\u5e26\u7684\u79bb\u6563\u5085\u7acb\u53f6\u53d8\u5316\u91cc\u9762\u89c2\u5bdf\u4e0b\u3002<\/p>\n

      \u4e0b\u9762\u662f\u8001\u957f\u7684\u4ee3\u7801<\/p>\n

        \n
      1. Table<\/span>[<\/span><\/li>\n
      2. \u00a0<\/span>{<\/span><\/li>\n
      3. \u00a0\u00a0ts\u00a0<\/span>=<\/span>\u00a0<\/span>10<\/span>;<\/span><\/li>\n
      4. \u00a0\u00a0sig\u00a0<\/span>=<\/span>\u00a0<\/span>SignalMk<\/span>[<\/span>ts<\/span>,<\/span>\u00a0<\/span>Omega<\/span>];<\/span><\/li>\n
      5. \u00a0\u00a0<\/span>Print<\/span>[<\/span>“omega\u00a0is”<\/span>,<\/span>\u00a0<\/span>Omega<\/span>];<\/span><\/li>\n
      6. \u00a0\u00a0dr\u00a0<\/span>=<\/span>\u00a0<\/span>100<\/span>;<\/span><\/li>\n
      7. \u00a0\u00a0P1\u00a0<\/span>=<\/span>\u00a0<\/span>ListLinePlot<\/span>[<\/span><\/li>\n
      8. \u00a0\u00a0\u00a0\u00a0<\/span>(<\/span>Abs<\/span>[<\/span>Fourier<\/span>[<\/span>sig<\/span>,<\/span>\u00a0<\/span>FourierParameters<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>{<\/span>1<\/span>,<\/span>\u00a0<\/span>–<\/span>1<\/span>}]]<\/span><\/li>\n
      9. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>)[[<\/span>1<\/span>\u00a0<\/span>;;<\/span>\u00a0dr<\/span>*<\/span>ts<\/span>]],<\/span><\/li>\n
      10. \u00a0\u00a0\u00a0\u00a0<\/span>PlotRange<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>All<\/span>,<\/span>\u00a0<\/span>DataRange<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>{<\/span>1<\/span>,<\/span>\u00a0dr<\/span>*<\/span>ts<\/span>}*(<\/span>2<\/span>\u00a0<\/span>Pi<\/span>)\/<\/span>ts<\/span>,<\/span>\u00a0<\/span><\/li>\n
      11. \u00a0\u00a0\u00a0\u00a0<\/span>PlotStyle<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>Red<\/span><\/li>\n
      12. \u00a0\u00a0\u00a0\u00a0<\/span>];<\/span><\/li>\n
      13. \u00a0\u00a0<\/span><\/li>\n
      14. \u00a0\u00a0P2\u00a0<\/span>=<\/span>\u00a0<\/span>ListLinePlot<\/span>[<\/span><\/li>\n
      15. \u00a0\u00a0\u00a0\u00a0<\/span>(<\/span>Re<\/span>[<\/span>Fourier<\/span>[<\/span>sig<\/span>,<\/span>\u00a0<\/span>FourierParameters<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>{<\/span>1<\/span>,<\/span>\u00a0<\/span>–<\/span>1<\/span>}]])<\/span><\/li>\n
      16. \u00a0\u00a0\u00a0\u00a0\u00a0<\/span>[[<\/span>1<\/span>\u00a0<\/span>;;<\/span>\u00a0dr<\/span>*<\/span>ts<\/span>]],<\/span><\/li>\n
      17. \u00a0\u00a0\u00a0\u00a0<\/span>PlotRange<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>All<\/span>,<\/span>\u00a0<\/span>DataRange<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>{<\/span>1<\/span>,<\/span>\u00a0dr<\/span>*<\/span>ts<\/span>}*(<\/span>2<\/span>\u00a0<\/span>Pi<\/span>])\/<\/span>ts<\/span>,<\/span>\u00a0<\/span><\/li>\n
      18. \u00a0\u00a0\u00a0\u00a0<\/span>PlotStyle<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>Blue<\/span><\/li>\n
      19. \u00a0\u00a0\u00a0\u00a0<\/span>];<\/span><\/li>\n
      20. \u00a0\u00a0P3\u00a0<\/span>=<\/span>\u00a0<\/span>ListLinePlot<\/span>[<\/span><\/li>\n
      21. \u00a0\u00a0\u00a0\u00a0<\/span>(<\/span>Im<\/span>[<\/span>Fourier<\/span>[<\/span>sig<\/span>,<\/span>\u00a0<\/span>FourierParameters<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>{<\/span>1<\/span>,<\/span>\u00a0<\/span>–<\/span>1<\/span>}]]<\/span><\/li>\n
      22. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>)[[<\/span>1<\/span>\u00a0<\/span>;;<\/span>\u00a0dr<\/span>*<\/span>ts<\/span>]],<\/span><\/li>\n
      23. \u00a0\u00a0\u00a0\u00a0<\/span>PlotRange<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>All<\/span>,<\/span>\u00a0<\/span>DataRange<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>{<\/span>1<\/span>,<\/span>\u00a0dr<\/span>*<\/span>ts<\/span>}*(<\/span>2<\/span>\u00a0<\/span>Pi<\/span>)\/<\/span>ts<\/span>,<\/span>\u00a0<\/span><\/li>\n
      24. \u00a0\u00a0\u00a0\u00a0<\/span>PlotStyle<\/span>\u00a0<\/span>-><\/span>\u00a0<\/span>Yellow<\/span><\/li>\n
      25. \u00a0\u00a0\u00a0\u00a0<\/span>];<\/span><\/li>\n
      26. \u00a0\u00a0<\/span><\/li>\n
      27. \u00a0\u00a0<\/span>Show<\/span>[<\/span>P1<\/span>,<\/span>\u00a0P2<\/span>,<\/span>\u00a0P3<\/span>]<\/span><\/li>\n
      28. \u00a0\u00a0<\/span><\/li>\n
      29. \u00a0\u00a0<\/span>}<\/span><\/li>\n<\/ol>\n

        \u751f\u6210\u4e00\u7cfb\u5217\u4eceomega\u4e3a100-150-200\u7684\u5085\u7acb\u53f6\u540e\u7684\u56fe\u50cf\uff0c\u5982\u4e0b<\/p>\n

        \"50fly\"<\/a> \"100fly\"<\/a> \"200fly\"<\/a><\/p>\n

         <\/p>\n

        \u53ef\u89c1\u5728\u6b63\u786e\u7684\u5730\u65b9\u51fa\u73b0\u4e86\u5c16\u5cf0\uff0c\u4e5f\u5c31\u662f\u6211\u4eec\u5f97\u5230\u4e86\u4e00\u4e2a\u6f02\u4eae\u9891\u8c31\u7684\u5206\u5e03\u3002<\/p>\n

        \u90a3\u4e48\u6765\u89e3\u91ca\u4e00\u4e0bdft\uff08\u79bb\u6563\u5085\u7acb\u53f6\uff09\u5427\uff0c<\/p>\n

        \u6240\u8c13\u79bb\u6563\u5085\u7acb\u53f6\uff0c\u5c31\u662f\u628a\u79bb\u6563\u5316\u7684\u6570\u636e\u70b9\u8f6c\u5316\u4e3a\u4e00\u4e2a\u79bb\u6563\u7684\u5085\u7acb\u53f6\u7ea7\u6570\uff0c\u7528\u6765\u83b7\u5f97\u9891\u8c31\u5206\u6790\u7b49\uff0c\u5728\u4e2a\u9886\u57df\u90fd\u6709\u5f88\u5927\u7528\u9014\uff0c\u5176\u672c\u8d28\u5c31\u662f\u4e00\u5806\u6570\u636e\u70b9\uff0c\u6309\u7167\u65f6\u5e8f\u8fdb\u884c\u3002\u8f6c\u6362\u4e3a\u4e00\u4e2a\u9891\u7387\uff0d\u632f\u5e45\u7684\u5206\u5e03\uff0c<\/p>\n

        \u5176\u4e2d<\/p>\n

        $$!\\omega_k=k\\cdot\\frac{2\\pi}{NT}$$<\/p>\n

        T\u4e3a\u91c7\u6837\u9891\u7387\uff0cN\u4e3a\u91c7\u6837\u6570\u91cf\uff0cNT\u4e3a\u91c7\u6837\u603b\u65f6\u957f\uff0ck\u4e3a\u7f16\u53f7,k\u4e3a\u53d8\u6362\u540e\u7684\u6837\u70b9\uff08\u5728\u8ba1\u7b97\u673a\u4e2d\u4e00\u822c\u662f\u632f\u5e45\u7684\u6807\u53f7\uff09<\/p>\n

        \u4e5f\u5c31\u662f\u6211\u4e0a\u9762\u751f\u6210\u9891\u8c31\u56fe\u7684\u7cfb\u6570\u3002\u5bf9\u5e94\u7684\u5c06\u662f\u4e00\u4e2a\u632f\u5e45\uff0c\u53cd\u4e4b\u6211\u4eec\u53ef\u4ee5\u7528\u9006\u53d8\u6362\u628a\u5b83\u53d8\u56de\u53bb\u3002<\/p>\n

        \u4e8e\u662f\u539f\u4fe1\u53f7\u5c31\u53ef\u4ee5\u8868\u793a\u6210<\/p>\n

        $$\\sum_{k=0}^{n-1}Re[f(k)]\\cdot Cos(\\omega_{k}t)+Im[f(k)]\\cdot Sin(\\omega_{k}t)$$<\/p>\n

        \u65e0\u59a8\u4e00\u8bd5\uff0c\u53c8\u662fmathematica<\/p>\n

          \n
        1. (*<\/span>\u00a0<\/span>Mathematica<\/span>\u00a0code<\/span>*)<\/span><\/li>\n
        2. sig\u00a0<\/span>=<\/span>\u00a0<\/span>SignalMk<\/span>[<\/span>0.5<\/span>,<\/span>\u00a0<\/span>200<\/span>];(*\u751f\u6210\u4e00\u4e2a0.5\u79d2\u957f\uff0c200omega\u7684\u4fe1\u53f7*)<\/span><\/li>\n
        3. fx\u00a0<\/span>=<\/span>\u00a0<\/span>Fourier<\/span>[<\/span>sig<\/span>];(*\u628a\u8fd9\u73a9\u610f\u5085\u7acb\u53f6\u4e86*)<\/span><\/li>\n
        4. omgk<\/span>[<\/span>k_<\/span>]<\/span>\u00a0<\/span>:=<\/span>\u00a0k\u00a0<\/span>(<\/span>2<\/span>\u00a0<\/span>Pi<\/span>)\/<\/span>0.5\/\/k\u5bf9\u5e94\u7684omega<\/span><\/li>\n
        5. \u00a0<\/span><\/li>\n
        6. y\u00a0<\/span>=<\/span>\u00a0<\/span>Table<\/span>[<\/span><\/li>\n
        7. \u00a0\u00a0\u00a0<\/span><\/li>\n
        8. \u00a0\u00a0\u00a0<\/span>Sum<\/span>[<\/span>Re<\/span>[<\/span>fx<\/span>[[<\/span>k\u00a0<\/span>+<\/span>\u00a0<\/span>1<\/span>]]]*<\/span>Cos<\/span>[<\/span>omgk<\/span>[<\/span>k<\/span>]*<\/span>t<\/span>\/<\/span>4096<\/span>](*\u6ce8\u610f\u4e0a\u9762\u63d0\u5230\u7684k\u662f0\u5f00\u59cb\u7f16\u53f7\uff0cmathematica\u9ed8\u8ba41\u5f00\u59cb\uff0c\u6545\u6709\uff0b1\uff0c\u6b64\u9879\u65e0\u59a8\u8ba4\u4e3a\u662f\u793a\u6ce2\u5668\u7684\u90a3\u4e2a\u201c\u76f4\u6d41\u6210\u5206\u201d*)<\/span><\/li>\n
        9. \u00a0\u00a0\u00a0\u00a0\u00a0<\/span>+<\/span>\u00a0<\/span>Im<\/span>[<\/span>fx<\/span>[[<\/span>k\u00a0<\/span>+<\/span>\u00a0<\/span>1<\/span>]]]*<\/span>Sin<\/span>[<\/span>omgk<\/span>[<\/span>k<\/span>]*<\/span>t<\/span>\/<\/span>4096<\/span>]<\/span><\/li>\n
        10. \u00a0\u00a0\u00a0\u00a0<\/span>,<\/span>\u00a0<\/span>{<\/span>k<\/span>,<\/span>\u00a0<\/span>1<\/span>,<\/span>\u00a0<\/span>500<\/span>}]<\/span><\/li>\n
        11. \u00a0 \u00a0(*\u8fd9\u4e2a\u5f0f\u5b50\u542f\u793a\u5c31\u662f\u5b9a\u4e49\u4e86*)<\/span><\/li>\n
        12. \u00a0\u00a0\u00a0<\/span>,<\/span>\u00a0<\/span>{<\/span>t<\/span>,<\/span>\u00a0<\/span>1<\/span>,<\/span>\u00a0<\/span>2048<\/span>}];<\/span><\/li>\n
        13. ListLinePlot<\/span>[<\/span>sig<\/span>]<\/span><\/li>\n
        14. ListLinePlot<\/span>[<\/span>y<\/span>]<\/span><\/li>\n<\/ol>\n

          \u5f97\u5230\u4e24\u5e45\u56fe<\/p>\n

          \"redft0\"<\/a> \"redft1\"<\/a><\/p>\n

           <\/p>\n

          \u5206\u8fa8\u4e0d\u51fa\u6765\u90a3\u4e2a\u662f\u4fe1\u53f7\u6e90\u7684\u90a3\u4e2a\u662f\u91cd\u65b0\u9006\u5085\u7acb\u53f6\u56de\u53bb\u7684\uff1f\u90a3\u5c31\u662f\u9a8c\u8bc1\u6210\u529f\u4e86\u3002<\/p>\n

          \u4e8c\uff0c\u7b80\u5355\u7684\u4e00\u7ef4\u79bb\u6563\u5085\u7acb\u53f6\u53d8\u6362<\/span><\/p>\n

          Now\uff0c\u6211\u4eec\u5148\u6487\u5f00Mathematica\u548cwiki\uff0c\u81ea\u5df1\u63a8\u5012\u4e00\u4e0b\u79bb\u6563\u5085\u7acb\u53f6\u53d8\u6362\u3002<\/p>\n

          \u6253\u5f00\u6211\u4eec\u7684\u5fae\u79ef\u5206\u6559\u6750\uff0c\u8fde\u7eed\u5085\u7acb\u53f6\u53d8\u6362\u5982\u662f\u5b9a\u4e49<\/p>\n

          $$!F(\\omega)=\\frac{1}{l}\\intop_{0}^{+l}f(t)e^{-i\\omega t}dt$$<\/p>\n

          \u8fd9\u662f\u5bf9\u4e8e\u8fde\u7eed\u51fd\u6570\u7684\u79ef\u5206\uff0c\u5f53\u7136\u6211\u4eec\u4e0d\u80fd\u76f4\u63a5\u5b9e\u73b0\uff0c\u4e8e\u662f\u4e4e\uff0c\u6211\u4eec\u5f97\u628a\u5b83\u79bb\u6563\u5316\uff0c\u5f88\u5f00\u5fc3\u7684\u76f4\u63a5\u77e9\u9635\u79ef\u4e2a\u5206\u597d\u5566<\/p>\n

          \u6211\u4eec\u8ba9\u91c7\u6837\u5468\u671f\u4e3a\u6700\u5c0f\u5206\u5ea6dt\u4e5f\u5c31\u662f$$\\frac{L}{N}(s)=T$$<\/p>\n

          \u90a3\u4e48\u5f97\u5230\u5f0f\u5b50<\/p>\n

          $$!F(\\omega)=\\frac{1}{l}\\sum_{k=0}^{n-1}f(k\\cdot T)e^{-i\\omega k\\cdot T}T$$<\/p>\n

          \u5176\u4e2d\uff0ck\uff1d0, \u6b64\u5904\u4e0ewikipedia\u7565\u6709\u4e0d\u540c\uff0c\u5f52\u4e00\u5316\u5f97\u5230<\/p>\n

          $$!F[l]=\\sum_{k=0}^{k-1}f(k)e^{-i\\frac{2\\pi}{N}k\\cdot l}$$<\/p>\n

          \u6b64\u65f6\u9700\u8981\u6ce8\u610f\u7684\u662f\u5f97\u5230\u7684\u7cfb\u6570\u5e76\u975e\u6211\u4eec\u6700\u540e\u4f7f\u7528\u7684\uff0c\u4e2d\u95f4\u8fd8\u6709\u4e00\u4e2a\u5f52\u4e00\u5316\u7cfb\u6570\uff0c\u4e0d\u8fc7\u8fd9\u4e2a\u6682\u4e14\u65e0\u5173\u7d27\u8981\uff0c\u636e\u6b64\uff0c\u6211\u4eec\u53ef\u4ee5\u5199\u51fa\u7b2c\u4e00\u4e2a\u7b80\u5355\u7684o(n^2)\u7684dft\u7a0b\u5e8f<\/p>\n

          \u9996\u5148\uff0cc\u7b49\u8bed\u8a00\u662f\u4e0d\u652f\u6301\u865a\u6570\u7684\uff0c\u6d69\u6d69\u53c8\u4e0d\u60f3\u5b66fortran\uff0c\u4e8e\u662f\u5148\u8f6c\u4e3a\u4e24\u4e2a\u90e8\u5206<\/p>\n

          $$!F[i].Re=\\sum_{k=0}^{k-1}f(k)\\cdot Cos(2\\cdot\\pi\\cdot k\\cdot i\/N)$$<\/p>\n

          $$!F[i].Im=-\\sum_{k=0}^{k-1}f(k)\\cdot Sin(2\\cdot\\pi\\cdot k\\cdot i\/N)$$<\/p>\n

          $$!F[i].Abs=Sqrt(F[i].Re^2+F[i].Im^2)$$<\/p>\n

          \u4e8e\u662f\u4e4e\uff0crush\u4e00\u4e2a\u5c0fc\u7684\u7a0b\u5e8f\uff0c\u5c31\u662f\u6211\u4eec\u7684\u6162\u901f\u5085\u7acb\u53f6\u4e86\uff0c\u4e3a\u4e86\u8003\u8651\u5411\u5355\u7247\u673a\u8fc1\u79fb\uff0c\u4ee3\u7801\u98ce\u683c\u662f\u7eafc\u7684\u98ce\u683c\uff0c\u5927\u91cf\u6307\u9488\u6beb\u65e0\u7ed3\u6784\u6beb\u65e0\u7f8e\u611f\uff0c\u5404\u4f4d\u5c06\u5c31\u770b\u54c8\u3002<\/p>\n

            \n
          1. #include<\/span>“stdio.h”<\/span><\/li>\n
          2. #include<\/span>“stdlib.h”<\/span><\/li>\n
          3. #include<\/span>“math.h”<\/span><\/li>\n
          4. #define<\/span>\u00a0pi\u00a0<\/span>3.1415926<\/span><\/li>\n
          5. float<\/span>*<\/span>\u00a0dft<\/span>(<\/span>float<\/span>\u00a0<\/span>*<\/span>input<\/span>,<\/span>int<\/span>\u00a0<\/span>Size<\/span>,<\/span>float<\/span>\u00a0<\/span>*><\/span>re<\/span>,<\/span>float<\/span>\u00a0<\/span>*><\/span>im<\/span>)<\/span>\/\/return\u00a0abs \u6162\u901fdft\u6838\u5fc3<\/span><\/li>\n
          6. {<\/span><\/li>\n
          7. \u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>\u00a0<\/span>*<\/span>abs<\/span>=(<\/span>float<\/span>*)<\/span>malloc<\/span>(<\/span>Size<\/span>*<\/span>sizeof<\/span>(<\/span>float<\/span>));<\/span><\/li>\n
          8. \u00a0\u00a0\u00a0\u00a0re<\/span>=(<\/span>float<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>Size<\/span>*<\/span>sizeof<\/span>(<\/span>float<\/span>));<\/span><\/li>\n
          9. \u00a0\u00a0\u00a0\u00a0im<\/span>=(<\/span>float<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>Size<\/span>*<\/span>sizeof<\/span>(<\/span>float<\/span>));<\/span><\/li>\n
          10. \u00a0\u00a0\u00a0\u00a0<\/span>for<\/span>(<\/span>int<\/span>\u00a0i<\/span>=<\/span>0<\/span>;<\/span>i<\/span><<\/span>Size<\/span>;<\/span>i<\/span>++)<\/span><\/li>\n
          11. \u00a0\u00a0\u00a0\u00a0<\/span>{<\/span><\/li>\n
          12. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>\u00a0sumre<\/span>=<\/span>0<\/span>;<\/span><\/li>\n
          13. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>\u00a0sumim<\/span>=<\/span>0<\/span>;<\/span><\/li>\n
          14. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>for<\/span>(<\/span>int<\/span>\u00a0k<\/span>=<\/span>0<\/span>;<\/span>k<\/span><<\/span>Size<\/span>;<\/span>k<\/span>++)<\/span><\/li>\n
          15. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>{<\/span><\/li>\n
          16. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0sumre<\/span>+=<\/span>input<\/span>[<\/span>k<\/span>]*<\/span>cosf<\/span>(<\/span>2<\/span>*<\/span>pi<\/span>*<\/span>k<\/span>*<\/span>i<\/span>\/<\/span>Size<\/span>);<\/span>\/\/calculate\u00a0re<\/span><\/li>\n
          17. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0sumim<\/span>-=<\/span>input<\/span>[<\/span>k<\/span>]*<\/span>sinf<\/span>(<\/span>2<\/span>*<\/span>pi<\/span>*<\/span>k<\/span>*<\/span>i<\/span>\/<\/span>Size<\/span>);<\/span><\/li>\n
          18. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>}<\/span><\/li>\n
          19. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>if<\/span>(<\/span>sumre<\/span>><\/span>4000<\/span>)<\/span><\/li>\n
          20. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0printf<\/span>(<\/span>“%d\\n”<\/span>,<\/span>sumre<\/span>);<\/span><\/li>\n
          21. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0re<\/span>[<\/span>i<\/span>]=<\/span>sumre<\/span>\/<\/span>sqrtf<\/span>(<\/span>Size<\/span>);<\/span><\/li>\n
          22. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0im<\/span>[<\/span>i<\/span>]=<\/span>sumim<\/span>\/<\/span>sqrtf<\/span>(<\/span>Size<\/span>);<\/span>\/\/\u53d6\u5f52\u4e00\u5316\u7cfb\u6570\u90fd\u662fsqrt(n)<\/span><\/li>\n
          23. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0abs<\/span>[<\/span>i<\/span>]=<\/span>sqrtf<\/span>(<\/span>sumre<\/span>*<\/span>sumre<\/span>+<\/span>sumim<\/span>*<\/span>sumim<\/span>);<\/span><\/li>\n
          24. \u00a0\u00a0\u00a0\u00a0<\/span>}<\/span><\/li>\n
          25. \u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0abs<\/span>;<\/span><\/li>\n
          26. }<\/span><\/li>\n
          27. float<\/span>*<\/span>\u00a0<\/span>SignalMk<\/span>(<\/span>float<\/span>\u00a0time<\/span>,<\/span>int<\/span>\u00a0omega<\/span>)\/\/\u4fe1\u53f7\u53d1\u751f\u5668<\/span><\/li>\n
          28. {<\/span><\/li>\n
          29. \u00a0\u00a0\u00a0\u00a0<\/span>int<\/span>\u00a0<\/span>Size<\/span>=(<\/span>int<\/span>)<\/span>time<\/span>*<\/span>4096<\/span>;<\/span><\/li>\n
          30. \u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>\u00a0<\/span>*<\/span>sig<\/span>=(<\/span>float<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>Size<\/span>*<\/span>sizeof<\/span>(<\/span>float<\/span>));<\/span><\/li>\n
          31. \u00a0\u00a0\u00a0\u00a0<\/span>for<\/span>(<\/span>int<\/span>\u00a0i<\/span>=<\/span>0<\/span>;<\/span>i<\/span><<\/span>Size<\/span>;<\/span>i<\/span>++)<\/span><\/li>\n
          32. \u00a0\u00a0\u00a0\u00a0<\/span>{<\/span><\/li>\n
          33. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0sig<\/span>[<\/span>i<\/span>]=<\/span>sinf<\/span>(<\/span>\u00a0<\/span>((<\/span>float<\/span>)<\/span>i<\/span>)*<\/span>omega<\/span>\/<\/span>4096<\/span>)+<\/span>sinf<\/span>(<\/span>\u00a0<\/span>2<\/span>*((<\/span>float<\/span>)<\/span>i<\/span>)*<\/span>omega<\/span>\/<\/span>4096<\/span>);<\/span><\/li>\n
          34. \u00a0\u00a0\u00a0\u00a0<\/span>}<\/span><\/li>\n
          35. \u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0sig<\/span>;<\/span><\/li>\n
          36. }<\/span><\/li>\n
          37. int<\/span>\u00a0main<\/span>()<\/span><\/li>\n
          38. {<\/span><\/li>\n
          39. \u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>\u00a0<\/span>*<\/span>re<\/span>,*<\/span>im<\/span>;<\/span><\/li>\n
          40. \u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>\u00a0<\/span>*<\/span>sig<\/span>=<\/span>SignalMk<\/span>(<\/span>1<\/span>,<\/span>200<\/span>);<\/span><\/li>\n
          41. \u00a0\u00a0\u00a0\u00a0printf<\/span>(<\/span>“Build\u00a0Sucessful\\n”<\/span>);<\/span><\/li>\n
          42. \u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>\u00a0<\/span>*<\/span>abs<\/span>=<\/span>dft<\/span>(<\/span>sig<\/span>,<\/span>4096<\/span>,<\/span>re<\/span>,<\/span>im<\/span>);<\/span><\/li>\n
          43. \u00a0\u00a0\u00a0\u00a0printf<\/span>(<\/span>“dft\u00a0Sucessful\\n”<\/span>);<\/span><\/li>\n
          44. \u00a0\u00a0\u00a0\u00a0<\/span>FILE<\/span>\u00a0<\/span>*<\/span>fp<\/span>=<\/span>fopen<\/span>(<\/span>“d.txt”<\/span>,<\/span>“w”<\/span>);<\/span><\/li>\n
          45. \u00a0\u00a0\u00a0\u00a0<\/span>for<\/span>(<\/span>int<\/span>\u00a0i<\/span>=<\/span>0<\/span>;<\/span>i<\/span><<\/span>4096<\/span>;<\/span>i<\/span>++)<\/span><\/li>\n
          46. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0fprintf<\/span>(<\/span>fp<\/span>,<\/span>“%f\u00a0“<\/span>,<\/span>abs<\/span>[<\/span>i<\/span>]);<\/span><\/li>\n
          47. }<\/span><\/li>\n<\/ol>\n

            \u4e8e\u662f\uff0c\u7ed3\u679c\u5bfc\u5165\u4e86mathematica\u5f97\u5230\u4e86\u4e0b\u9762\u7684\u56fe<\/p>\n

            \"slowdft\"<\/a><\/p>\n

             <\/p>\n

            So cool!<\/p>\n

            \u8fd9\u5c31\u662f\u90a3\u4e2a\u7b80\u5355\u7684c\u7a0b\u7684\u7ed3\u679c\u3002\u67d0\u79cd\u610f\u4e49\u4e0a\uff0c\u6211\u4eec\u5df2\u7ecf\u5b9e\u73b0\u4e86\u591a\u6570\u7684\u4fe1\u53f7\u5904\u7406\u3002<\/p>\n

            \u4e09\uff0c\u4e3b\u9898\uff0cFFT\uff01\u6548\u7387\uff0c\u8fd8\u662f\u6548\u7387<\/p>\n

            \u5bf9\u4e8e\u6570\u5b57\u4fe1\u53f7\u5904\u7406\uff0c\u8dd1\u572812MHz\u5355\u7247\u673a\u5403\u7740\u65e0\u53ef\u5fcd\u8010\u7684\u7834\u70c2\u73af\u5883\u8fd8\u8981\u5e72\u6700\u91cd\u7684\u6d3b\uff0c\u6211\u771f\u63d0\u5355\u7247\u673a\u7a0b\u5e8f\u5458\u611f\u5230\u6349\u6025\uff08\u4ee5\u524d\u73a9\u5355\u7247\u673a\u7684\u70ed\u60c5\u5c31\u662f\u88ab\u786c\u4ef6\u8d44\u6e90\u7184\u706d\u7684\uff0c\u76f8\u6bd4\u800c\u8a00\u6211\u66f4\u613f\u610f\u57288 cores\u4e3b\u673a\u5199\u975e\u7ed3\u6784\u7f51\u683cCFD\uff09\u3002\u4e8e\u662f\uff0c\u8fd9\u4e2a\u6548\u7387\u662f$$O(n^2)$$\u7b80\u76f4\u4e0d\u80fd\u5fcd\u6709\u6ca1\u6709\u3002\u3002\u3002\u8bbe\u60f3\u6211\u4eec\u8981\u5206\u6790\u4e00\u4e2a\u4eba\u7684\u58f0\u97f3\u6765\u786e\u5b9a\u4ed6\u7684\u8eab\u4efd\uff0c\u5085\u7acb\u53f6\u53d8\u6362\u662f\u57fa\u7840\u4e86\uff0c\u53ef\u662f\uff01mp3\u91c7\u6837\u7387\u662f44,100 Hz \uff0c\u4e5f\u5c31\u662f\u8bf4\uff0c<\/p>\n

            \u67d0\u9634\u68ee\u7684\u5730\u4e0b\u4f1a\u573a\uff0c\u7537A\u9053\uff0c\u201c\u4f60\u597d\u3002\u201d\uff0c\u8017\u65f6\u4e00\u79d2<\/p>\n

            \u7537B\u6697\u9053\uff0c\u5f85\u6211\u5206\u6790\u4e0b\u5b83\u7684\u58f0\u97f3\u662f\u5426\u6b63\u786e\u3002<\/p>\n

            \u7ecf\u8fc7\u4e86\u6f2b\u957f\u7684162\u79d2\uff08\u7528\u6211\u4eec\u7684slowdft\u9700\u898144100*44100\u6b21\u8fd0\u7b97\uff0c51\u5355\u7247\u673a\u9700\u8981162\u79d2\uff09\u3002\u672c\u62c9\u767b\u5df2\u7ecf\u6210\u529f\u8131\u8eab\u3002<\/p>\n

            \u6216\u8005<\/p>\n

            \u82e6\u82e6\u601d\u8003\uff0c\u67ef\u5357\u60f3\u5230\u4e86\u8bc1\u4eba\u662f\u8c01\uff0c\u6253\u5f00\u53d8\u58f0\u5668\uff0c\u8bf4\u4e86\u4e00\u6bb560\u79d2\u949f\u7684\u63a8\u7406\uff0c\u7ecf\u8fc7\u5355\u7247\u673a\u81ea\u71c3\u7684\u6e29\u5ea6\u7684162\u5c0f\u65f6\u8fd0\u7b97\uff0c<\/p>\n

            \u72af\u4eba\u9003\u8dd1\u4e86\u3002<\/p>\n

             <\/p>\n

            \u8fd9\u6837\u4e0d\u5982\u627e\u5757\u8c46\u8150\u649e\u6b7b\u597d\u4e86\u3002\u4e8e\u662f\u4e4e\uff0cfft\u6a2a\u7a7a\u51fa\u4e16\u3002<\/p>\n

            FFT\u662f\u4e00\u79cd\u590d\u6742\u5ea6\u4e3aNLog(N)\u7684\u7b97\u6cd5\uff0c\u4e00\u822c\u770b\u5230\u8fd9\u4e2a\u6548\u7387\uff0c\u5c31\u4f1a\u5f88\u660e\u4e86\u8fd9\u662f\u4e00\u4e2a\u4e8c\u5206\u6784\u9020\u7684\u8fc7\u7a0b\uff0c\u6574\u4e2a\u7b97\u6cd5\u5fc5\u7136\u5b58\u5728\u4e00\u5b9a\u7684\u5bf9\u79f0\u6027\uff0c\u800c\u4e14\u51e0\u4e4e\u53ef\u4ee5\u8ba4\u5b9a\u662f\u5b58\u5728\u9012\u5f52\u8fc7\u7a0b\u3002\u5269\u4e0b\u8981\u505a\u7684\u5c31\u662f\u627e\u5230\u90a3\u4e2a\u7b80\u5355\u7684\u9012\u5f52\u51fd\u6570\uff0c\u7136\u540e\u5f97\u5230\u6211\u4eec\u7684\u8fd0\u7b97\u7ed3\u679c\u3002\u4e0d\u8fc7\u5728\u8fd9\u91cc\uff0c\u7b97\u6cd5\u5bf9\u79f0\u6027\u5012\u662f\u7531\u6570\u5b66\u7ed9\u51fa\u7684\u3002<\/p>\n

            \u53c2\u8003\uff1ahttp:\/\/zh.wikipedia.org\/wiki\/%E5%BF%AB%E9%80%9F%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2<\/p>\n

            \u6211\u4eec\u7528$$W_N$$\u8868\u793a$$e^{-j\\frac{2\\pi}{N}}$$\uff0c\u4e8e\u662f\u4e4e<\/p>\n

            $$!W_{N}^{k+N}=W_{N}^{k}$$<\/p>\n

            $$!W_{N}^{k+\\frac{N}{2}}=-W_{N}^{k}$$<\/p>\n

            $$!W_{N}^{m\\cdot k_{n}}=W_{\\frac{N}{m}}^{k_{n}}$$<\/p>\n

            \u6839\u636e\u8fd9\u4e2a\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\u8fd9\u6837\u4e00\u4e2a\u9012\u5f52\u6784\u9020\u8fc7\u7a0b\uff08\u5728\u6b64\u6211\u5012\u66f4\u5b81\u613f\u7528\u8ba1\u7b97\u673a\u4e0a\u7684\u65b9\u5f0f\u800c\u975e\u7eaf\u7cb9\u6570\u5b66\u8bed\u8a00\u8868\u8ff0\uff09\u3002<\/p>\n

            \u4e00\u822c\uff0c\u5bf9\u4e8e\u6b64\u7c7b\u95ee\u9898\u90fd\u662f\u5148\u5206\u89e3\u4e3a\u6734\u7d20\u9012\u5f52\uff0c\u7136\u540e\u627e\u5230\u91cd\u590d\u4f7f\u7528\u7684\u8c03\u7528\uff08\u6bd4\u5982\u5b8c\u5168\u76f8\u540c\u7684\u53c2\u6570\u8f93\u5165\uff09\uff0c\u5f97\u5230\u7ed3\u679c\uff0c\u662f\u4e3a\u8ba1\u5212\u641c\u7d22\u3002<\/p>\n

            F(N,k)=<\/p>\n

            If(k<=$$\\frac{N}{2}$$)<\/p>\n

            $$F_{even}(k)+W_N^kF_{odd}(k)$$<\/p>\n

            If(k>$$\\frac{N}{2}$$)<\/p>\n

            $$F_{even}(k-\\frac{N}{2})-W_N^{k-\\frac{N}{2}}F_{odd}(k-\\frac{N}{2})$$<\/p>\n

            \u7531\u6b64\u53ef\u4ee5\u9012\u5f52\u6784\u9020\u51faF(k)<\/p>\n

            \u4e8e\u662f\uff0c\u6211\u5199\u4e86\u8fd9\u6837\u4e00\u4e2a\u9012\u5f52<\/p>\n

              \n
            1. Complex<\/span>\u00a0dfftk<\/span>(<\/span>float<\/span>\u00a0<\/span>*<\/span>input\u00a0<\/span>,<\/span>int<\/span>\u00a0<\/span>Size<\/span>,<\/span>int<\/span>\u00a0k<\/span>)<\/span><\/li>\n
            2. {<\/span><\/li>\n
            3. \u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>*<\/span>even<\/span>=(<\/span>float<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>sizeof<\/span>(<\/span>float<\/span>)*<\/span>Size<\/span>\/<\/span>2<\/span>);<\/span><\/li>\n
            4. \u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>*<\/span>odd<\/span>=(<\/span>float<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>sizeof<\/span>(<\/span>float<\/span>)*<\/span>Size<\/span>\/<\/span>2<\/span>);<\/span><\/li>\n
            5. \u00a0\u00a0\u00a0\u00a0<\/span>for<\/span>(<\/span>int<\/span>\u00a0i<\/span>=<\/span>0<\/span>;<\/span>i<\/span><<\/span>Size<\/span>;<\/span>i<\/span>++)<\/span>\/\/\u7b5b\u9009\u5668<\/span><\/li>\n
            6. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>if<\/span>(<\/span>i<\/span>%<\/span>2<\/span>==<\/span>0<\/span>)<\/span><\/li>\n
            7. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0even<\/span>[<\/span>i<\/span>\/<\/span>2<\/span>]=<\/span>input<\/span>[<\/span>i<\/span>];<\/span><\/li>\n
            8. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>else<\/span><\/li>\n
            9. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0odd<\/span>[<\/span>i<\/span>\/<\/span>2<\/span>]=<\/span>input<\/span>[<\/span>i<\/span>];<\/span><\/li>\n
            10. \u00a0\u00a0\u00a0\u00a0<\/span>if<\/span>(<\/span>Size<\/span>==<\/span>1<\/span>)<\/span><\/li>\n
            11. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0input<\/span>[<\/span>0<\/span>]*<\/span>Complex<\/span>(<\/span>1<\/span>,<\/span>0<\/span>);<\/span><\/li>\n
            12. \u00a0\u00a0\u00a0\u00a0<\/span>if<\/span>(<\/span>k<\/span><=<\/span>Size<\/span>\/<\/span>2<\/span>)<\/span><\/li>\n
            13. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0<\/span>(<\/span>dfftk<\/span>(<\/span>even<\/span>,<\/span>Size<\/span>\/<\/span>2<\/span>,<\/span>k<\/span>)+<\/span>W<\/span>(<\/span>Size<\/span>,<\/span>k<\/span>)*<\/span>dfftk<\/span>(<\/span>odd<\/span>,<\/span>Size<\/span>\/<\/span>2<\/span>,<\/span>k<\/span>));<\/span><\/li>\n
            14. \u00a0\u00a0\u00a0\u00a0<\/span>else<\/span><\/li>\n
            15. \u00a0\u00a0\u00a0\u00a0<\/span>{<\/span><\/li>\n
            16. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0<\/span>(<\/span>dfftk<\/span>(<\/span>even<\/span>,<\/span>Size<\/span>\/<\/span>2<\/span>,<\/span>k<\/span>–<\/span>Size<\/span>\/<\/span>2<\/span>)-<\/span>W<\/span>(<\/span>Size<\/span>,<\/span>k<\/span>–<\/span>Size<\/span>\/<\/span>2<\/span>)*<\/span>dfftk<\/span>(<\/span>odd<\/span>,<\/span>Size<\/span>\/<\/span>2<\/span>,<\/span>k<\/span>–<\/span>Size<\/span>\/<\/span>2<\/span>));<\/span><\/li>\n
            17. \u00a0\u00a0\u00a0\u00a0<\/span>}<\/span><\/li>\n
            18. \u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0<\/span>Complex<\/span>(<\/span>0<\/span>,<\/span>0<\/span>);<\/span><\/li>\n
            19. }<\/span><\/li>\n<\/ol>\n

              \u7136\u540e\u4e3b\u51fd\u6570\u8fd9\u4e48\u641e<\/p>\n

                \n
              1. Complex<\/span>\u00a0<\/span>*<\/span>fft<\/span>(<\/span>float<\/span>*<\/span>input<\/span>,<\/span>int<\/span>\u00a0<\/span>Size<\/span>)<\/span><\/li>\n
              2. {<\/span><\/li>\n
              3. \u00a0\u00a0\u00a0\u00a0<\/span>Complex<\/span>*<\/span>res<\/span>=(<\/span>Complex<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>sizeof<\/span>(<\/span>Complex<\/span>)*<\/span>Size<\/span>);<\/span><\/li>\n
              4. \u00a0\u00a0\u00a0\u00a0<\/span>int<\/span>\u00a0i<\/span>;<\/span><\/li>\n
              5. \u00a0\u00a0\u00a0\u00a0<\/span>for<\/span>(<\/span>i<\/span>=<\/span>0<\/span>;<\/span>i<\/span><<\/span>Size<\/span>;<\/span>i<\/span>++)<\/span><\/li>\n
              6. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0res<\/span>[<\/span>i<\/span>]=<\/span>dfftk<\/span>(<\/span>input<\/span>,<\/span>Size<\/span>,<\/span>i<\/span>);<\/span><\/li>\n
              7. \u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0res<\/span>;<\/span><\/li>\n
              8. }<\/span><\/li>\n<\/ol>\n

                \u4e8e\u662f\u5f97\u5230\u4e86\u6f02\u4eae\u7684\u7ed3\u679c<\/p>\n

                \"fft0\"<\/a><\/p>\n

                \u55ef\uff01\u8fd9\u5c31\u662f\u6211\u4eec\u60f3\u8981\u7684\uff0c\u73b0\u5728\u4e07\u4e8b\u4ff1\u5907\uff0c\u53ea\u6b20\u4e1c\u98ce\uff1a\u5982\u4f55\u8ba9\u5b83\u5feb\u8d77\u6765\u3002<\/p>\n

                \u56db\uff1a\u96d5\u866b\u5c0f\u6280<\/p>\n

                \u8ba9\u6211\u4eec\u5728\u56de\u987e\u4e0b\u6211\u4eec\u7684\u51fd\u6570\u8f93\u5165\uff0c\u5047\u5b9a\u8ba1\u7b97\u7684\u90fd\u662f2\u7684\u6307\u6570\uff0c\u51fd\u6570\u7684\u7ed3\u679c\u4f9d\u8d56\u4e8e<\/p>\n

                1.\u70b9\u96c6\u5408\uff1ainput\uff0c\u5305\u542bSize\u4fe1\u606f\u3002<\/p>\n

                2.k\u7684\u503c\u3002<\/p>\n

                so\uff0c\u70b9\u96c6\u5408\u662f\u4e00\u4e2a\u9887\u4e3a\u865a\u65e0\u98d8\u6e3a\u7684\u6982\u5ff5\uff0c\u90a3\u6211\u4eec\u600e\u4e48\u786e\u5b9a\u5b83\u5462\uff0c\u6ce8\u610f\u5230\u6211\u4eec\u5047\u5b9a\u6570\u91cf\u4e00\u76f4\u662f\u4e8c\u7684\u6307\u6570\uff0c\u800c\u4e14\u4e00\u76f4\u4e8c\u5206\uff0c\u90a3\u4e48\uff0c\u53ea\u8981\u8bf4\u4e00\u4e2a\u70b9\u96c6\u5408\u7684Size\uff0c\u6211\u4eec\u5c31\u80fd\u786e\u5b9a\u4e8c\u5206\u4e86\u591a\u5c11\u6b21\uff0c\u7ed9\u51fa\u7b2c\u4e00\u4e2a\u70b9\u7684\u5168\u5c40\u7f16\u53f7\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u5728\u8fd9\u68f5\u67e5\u627e\u6811\u4e0a\u786e\u5b9a\u4ed6\u7684\u4f4d\u7f6e\u3002\u4e8e\u662f\uff0c\u5bf9\u4e8e\u6bcf\u6b21\u641c\u7d22\uff0c\u6211\u4eec\u53ef\u4ee5\u7528\u4ee5\u4e0b\u51e0\u4e2a\u70b9\u6807\u540d\u5176\u610f\u4e49<\/p>\n

                \u6df1\u5ea6\uff0c\u9996\u4f4d\u7f16\u53f7\uff0c\u4ee5\u53cak\u3002<\/p>\n

                \u5728\u8ba1\u7b97\u4e2d\uff0c\u6211\u4eec\u8981\u505a\u5bf9\u534a\u4f18\u5316\uff0c\u5176\u5b9e\u53ea\u9700\u5728k<Size\/2\u65f6\u5019\u628a+Size\/2\u52a0\u4e0a\u3002<\/p>\n

                \u4e8e\u662f\u4e4e\uff1a<\/p>\n

                  \n
                1. bool<\/span>\u00a0<\/span>Travel<\/span>[<\/span>4096<\/span>][<\/span>13<\/span>][<\/span>4096<\/span>]={<\/span>0<\/span>};\/\/\u7eaa\u5f55\u662f\u5426\u8bbf\u95ee\u8fc7<\/span><\/li>\n
                2. Complex<\/span>\u00a0val<\/span>[<\/span>4096<\/span>][<\/span>13<\/span>][<\/span>4096<\/span>];\/\/\u7eaa\u5f55\u8bbf\u95ee\u8fc7\u7684\u503c<\/span><\/li>\n
                3. int<\/span>\u00a0numheight<\/span>[<\/span>15<\/span>]={<\/span>0<\/span>};<\/span><\/li>\n
                4. \u00a0<\/span><\/li>\n
                5. Complex<\/span>\u00a0dfftk<\/span>(<\/span>float<\/span>\u00a0<\/span>*<\/span>input<\/span>,<\/span>int<\/span>*<\/span>nums\u00a0<\/span>,<\/span>int<\/span>\u00a0<\/span>Size<\/span>,<\/span>int<\/span>\u00a0k<\/span>)<\/span><\/li>\n
                6. {<\/span><\/li>\n
                7. \u00a0\u00a0\u00a0\u00a0<\/span>int<\/span>\u00a0h<\/span>=<\/span>log<\/span>(<\/span>Size<\/span>)\/<\/span>log<\/span>(<\/span>2<\/span>);<\/span><\/li>\n
                8. \u00a0\u00a0\u00a0\u00a0<\/span>int<\/span>\u00a0top<\/span>;<\/span><\/li>\n
                9. \u00a0\u00a0\u00a0\u00a0top<\/span>=<\/span>nums<\/span>[<\/span>0<\/span>];<\/span><\/li>\n
                10. \u00a0\u00a0\u00a0\u00a0<\/span>if<\/span>(<\/span>Travel<\/span>[<\/span>top<\/span>][<\/span>h<\/span>][<\/span>k<\/span>])\/\/\u8bbf\u95ee\u8fc7\u5c31\u76f4\u63a5\u7528<\/span><\/li>\n
                11. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0<\/span>Complex<\/span>(<\/span>val<\/span>[<\/span>top<\/span>][<\/span>h<\/span>][<\/span>k<\/span>]);<\/span><\/li>\n
                12. \u00a0\u00a0\u00a0\u00a0<\/span>Travel<\/span>[<\/span>top<\/span>][<\/span>h<\/span>][<\/span>k<\/span>]=<\/span>1<\/span>;\/\/\u6807\u5b9a\u4e3a\u8bbf\u95ee\u8fc7<\/span><\/li>\n
                13. \u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>*<\/span>even<\/span>=(<\/span>float<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>sizeof<\/span>(<\/span>float<\/span>)*<\/span>Size<\/span>\/<\/span>2<\/span>);<\/span><\/li>\n
                14. \u00a0\u00a0\u00a0\u00a0<\/span>int<\/span>*<\/span>evenums<\/span>=(<\/span>int<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>sizeof<\/span>(<\/span>int<\/span>)*<\/span>Size<\/span>\/<\/span>2<\/span>);<\/span><\/li>\n
                15. \u00a0\u00a0\u00a0\u00a0<\/span>float<\/span>*<\/span>odd<\/span>=(<\/span>float<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>sizeof<\/span>(<\/span>float<\/span>)*<\/span>Size<\/span>\/<\/span>2<\/span>);<\/span><\/li>\n
                16. \u00a0\u00a0\u00a0\u00a0<\/span>int<\/span>*<\/span>oddnums<\/span>=(<\/span>int<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>sizeof<\/span>(<\/span>int<\/span>)*<\/span>Size<\/span>\/<\/span>2<\/span>);<\/span><\/li>\n
                17. \u00a0\u00a0\u00a0\u00a0<\/span>for<\/span>(<\/span>int<\/span>\u00a0i<\/span>=<\/span>0<\/span>;<\/span>i<\/span><<\/span>Size<\/span>;<\/span>i<\/span>++)\/\/\u5947\u5076\u5206\u6d41<\/span><\/li>\n
                18. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>if<\/span>(<\/span>i<\/span>%<\/span>2<\/span>==<\/span>0<\/span>)<\/span><\/li>\n
                19. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>{<\/span><\/li>\n
                20. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0even<\/span>[<\/span>i<\/span>\/<\/span>2<\/span>]=<\/span>input<\/span>[<\/span>i<\/span>];<\/span><\/li>\n
                21. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0evenums<\/span>[<\/span>i<\/span>\/<\/span>2<\/span>]=<\/span>nums<\/span>[<\/span>i<\/span>];<\/span><\/li>\n
                22. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>}<\/span><\/li>\n
                23. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>else<\/span><\/li>\n
                24. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>{<\/span><\/li>\n
                25. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0odd<\/span>[<\/span>i<\/span>\/<\/span>2<\/span>]=<\/span>input<\/span>[<\/span>i<\/span>];<\/span><\/li>\n
                26. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0oddnums<\/span>[<\/span>i<\/span>\/<\/span>2<\/span>]=<\/span>nums<\/span>[<\/span>i<\/span>];<\/span><\/li>\n
                27. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>}<\/span><\/li>\n
                28. \u00a0\u00a0\u00a0\u00a0<\/span>if<\/span>(<\/span>Size<\/span>==<\/span>1<\/span>)<\/span><\/li>\n
                29. \u00a0\u00a0\u00a0\u00a0<\/span>{<\/span><\/li>\n
                30. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0val<\/span>[<\/span>nums<\/span>[<\/span>0<\/span>]][<\/span>h<\/span>][<\/span>k<\/span>]=(<\/span>input<\/span>[<\/span>0<\/span>]*<\/span>Complex<\/span>(<\/span>1<\/span>,<\/span>0<\/span>));<\/span><\/li>\n
                31. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0<\/span>Complex<\/span>(<\/span>val<\/span>[<\/span>top<\/span>][<\/span>h<\/span>][<\/span>k<\/span>]);<\/span><\/li>\n
                32. \u00a0\u00a0\u00a0\u00a0<\/span>}<\/span><\/li>\n
                33. \u00a0\u00a0\u00a0\u00a0<\/span>if<\/span>(<\/span>k<\/span><=<\/span>Size<\/span>\/<\/span>2<\/span>)<\/span><\/li>\n
                34. \u00a0\u00a0\u00a0\u00a0<\/span>{<\/span><\/li>\n
                35. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>Complex<\/span>\u00a0everes<\/span>,<\/span>oddres<\/span>;<\/span><\/li>\n
                36. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0everes<\/span>=<\/span>dfftk<\/span>(<\/span>even<\/span>,<\/span>evenums<\/span>,<\/span>Size<\/span>\/<\/span>2<\/span>,<\/span>k<\/span>);<\/span><\/li>\n
                37. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0oddres<\/span>=<\/span>dfftk<\/span>(<\/span>odd<\/span>,<\/span>oddnums<\/span>,<\/span>Size<\/span>\/<\/span>2<\/span>,<\/span>k<\/span>);<\/span><\/li>\n
                38. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0val<\/span>[<\/span>top<\/span>][<\/span>h<\/span>][<\/span>k<\/span>]=(<\/span>everes<\/span>+<\/span>W<\/span>(<\/span>Size<\/span>,<\/span>k<\/span>)*<\/span>oddres<\/span>);<\/span><\/li>\n
                39. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>Travel<\/span>[<\/span>top<\/span>][<\/span>h<\/span>][<\/span>k<\/span>+<\/span>Size<\/span>\/<\/span>2<\/span>]=<\/span>1<\/span>;<\/span><\/li>\n
                40. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0val<\/span>[<\/span>top<\/span>][<\/span>h<\/span>][<\/span>k<\/span>+<\/span>Size<\/span>\/<\/span>2<\/span>]=(<\/span>everes<\/span>–<\/span>W<\/span>(<\/span>Size<\/span>,<\/span>k<\/span>)*<\/span>oddres<\/span>);<\/span><\/li>\n
                41. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0<\/span>Complex<\/span>(<\/span>val<\/span>[<\/span>top<\/span>][<\/span>h<\/span>][<\/span>k<\/span>]);<\/span><\/li>\n
                42. \u00a0\u00a0\u00a0\u00a0<\/span>}<\/span><\/li>\n
                43. \u00a0\u00a0\u00a0\u00a0printf<\/span>(<\/span>“You\u00a0are\u00a0Wrong\\n”<\/span>);<\/span><\/li>\n
                44. \u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0<\/span>Complex<\/span>(<\/span>0<\/span>,<\/span>0<\/span>);<\/span><\/li>\n
                45. }<\/span><\/li>\n
                46. Complex<\/span>\u00a0<\/span>*<\/span>fft<\/span>(<\/span>float<\/span>*<\/span>input<\/span>,<\/span>int<\/span>\u00a0<\/span>Size<\/span>)<\/span><\/li>\n
                47. {<\/span><\/li>\n
                48. \u00a0\u00a0\u00a0\u00a0<\/span>Complex<\/span>*<\/span>res<\/span>=(<\/span>Complex<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>sizeof<\/span>(<\/span>Complex<\/span>)*<\/span>Size<\/span>);<\/span><\/li>\n
                49. \u00a0\u00a0\u00a0\u00a0<\/span>int<\/span>\u00a0i<\/span>;<\/span><\/li>\n
                50. \u00a0\u00a0\u00a0\u00a0<\/span>int<\/span>\u00a0<\/span>*<\/span>nums<\/span>=(<\/span>int<\/span>\u00a0<\/span>*)<\/span>malloc<\/span>(<\/span>sizeof<\/span>(<\/span>int<\/span>)*<\/span>Size<\/span>);<\/span><\/li>\n
                51. \u00a0\u00a0\u00a0\u00a0<\/span>for<\/span>(<\/span>i<\/span>=<\/span>0<\/span>;<\/span>i<\/span><<\/span>Size<\/span>;<\/span>i<\/span>++)<\/span><\/li>\n
                52. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0nums<\/span>[<\/span>i<\/span>]=<\/span>i<\/span>;<\/span><\/li>\n
                53. \u00a0\u00a0\u00a0\u00a0<\/span>for<\/span>(<\/span>i<\/span>=<\/span>0<\/span>;<\/span>i<\/span><<\/span>Size<\/span>;<\/span>i<\/span>++)<\/span><\/li>\n
                54. \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0res<\/span>[<\/span>i<\/span>]=<\/span>dfftk<\/span>(<\/span>input<\/span>,<\/span>nums<\/span>,<\/span>Size<\/span>,<\/span>i<\/span>);<\/span><\/li>\n
                55. \u00a0\u00a0\u00a0\u00a0<\/span>return<\/span>\u00a0res<\/span>;<\/span><\/li>\n
                56. }<\/span><\/li>\n<\/ol>\n

                  \u8dd1\u4e00\u4e0b\uff0c\u7ed3\u679c\u672a\u53d8\uff0c\u65f6\u95f4\u4ece24646\u53d8\u6210\u4e86189\u6beb\u79d2\u3002\u3002\u3002\u3002\u3002\u8fd9\u5dee\u8ddd<\/b><\/p>\n

                  \u4e8e\u662f\uff0c\u65f6\u95f4\u5f97\u5230\u4e86\u4f18\u5316\uff0c\u518d\u56de\u5934\u770b\u6211\u4eec\u7684\u6570\u7ec4\uff0c\u6709\u4ec0\u4e48\u4e0d\u5bf9\u4e48\uff1f<\/p>\n

                  $$N^2*Log_2N$$\u7684\u7a7a\u95f4\uff1f\u4f60\u5728\u9017\u6211\u561b\uff1f<\/p>\n

                  \u4e94\uff0c\u4e27\u5fc3\u75c5\u72c2<\/p>\n

                  \u72b6\u6001\u538b\u7f29\uff1a<\/p>\n

                  \u9996\u5148\u770b\u8fd9\u4e2a\u8bb0\u5f55\uff0c\u6211\u4eec\u6b64\u65f6\u9700\u8981\u8ba1\u7b97\u4e00\u4e0b\u6211\u4eec\u771f\u6b63\u9700\u8981\u8bb0\u5f55\u7684\u6570\u91cf\uff0c\u4ece\u4e00\u5230k\u6b21\u6b21\u4e8c\u5206\uff0c\u5171\u6709$$NLog_2N$$\u4e2a\u72b6\u6001\uff0c\u5176\u4e2d\u6709\u4e00\u534a\u662f\u4f5c\u4e3ak<Size\/2return\u7ed9\u51fa\u7684\uff0c\u4e00\u534a\u662f\u4f5c\u4e3a\u8bb0\u5f55\u7684\u3002\u4e8e\u662f\u6211\u4eec\u9700\u8981\u7cbe\u786e\u6784\u9020\u4e00\u4e2a\u65b0\u7684\u8bb0\u5f55\uff0c\u4f7f\u5f97\u8fd9\u4e2a\u5b58\u50a8\u91cf\u5927\u5e45\u5ea6\u51cf\u5c11\u3002<\/p>\n

                  \u9996\u5148\uff0c\u5f53\u7136\u662f\u6beb\u65e0\u8282\u64cd\u7684\u76f4\u63a5stl::Map\u4e86\uff08\u672c\u6765\u51c6\u5907\u81ea\u5df1\u5199\u4e2ahash\u6765\u7740\u3002\u3002\u56f0\u4e86\u3002\u3002\u3002\u53bb\u4ed6\u7684\u7eafc\u5e73\u53f0\uff09\u3002\u3002\u3002\u4e8e\u662f\u3002<\/p>\n

                   <\/p>\n","protected":false},"excerpt":{"rendered":"

                  FFT\uff0c\u5feb\u901f\u5085\u7acb\u53f6\u53d8\u6362\u662f\u4e2a\u86ee\u6709\u610f\u601d\u7684\u73a9\u610f\uff0c\u5e94\u7528\u5f88\u5e7f\uff0c\u5c24\u5176\u5728\u4fe1\u606f\u5904\u7406\u65b9\u9762\uff0c\u6700\u8fd1\u9700\u8981\u7528\u5230\uff0c\u5c31\u5b66\u5b66\u5566\u3002 \u4e07\u4e8b\u5f00\u5934\u96be\uff0c … <\/p>\n

                  \u7ee7\u7eed\u9605\u8bfb\u201c\u79bb\u6563\u5085\u7acb\u53f6\u5b66\u4e60\u4e4bFFT\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[5],"tags":[],"_links":{"self":[{"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=\/wp\/v2\/posts\/65"}],"collection":[{"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=65"}],"version-history":[{"count":39,"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=\/wp\/v2\/posts\/65\/revisions"}],"predecessor-version":[{"id":126,"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=\/wp\/v2\/posts\/65\/revisions\/126"}],"wp:attachment":[{"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=65"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=65"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.xuhao1.me\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=65"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}