一维复数序列的快速傅里叶变换（FFT） 傅里叶（FFT、DFT、傅立叶、Fourier）傅里叶变换的...
\u4e00\u7ef4\u5b9e\u5e8f\u5217\u7684\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362\uff08FFT\uff09\u901a\u8fc7\u524d\u9762\u7684\u5206\u6790\uff0c\u6211\u4eec\u8ba4\u8bc6\u5230\u5085\u91cc\u53f6\u53d8\u6362\u672c\u8eab\u662f\u590d\u6570\u8fd0\u7b97\uff0c\u5730\u7403\u7269\u7406\u83b7\u53d6\u7684\u6570\u636e\u5927\u591a\u6570\u662f\u5b9e\u6570\uff0c\u5bf9\u4e8e\u5b9e\u6570\u7684\u53d8\u6362\u539f\u5219\u4e0a\u53ef\u76f4\u63a5\u5957\u7528\u590d\u5e8f\u5217\u7684FFT\u7b97\u6cd5\uff0c\u4f46\u90a3\u6837\u662f\u628a\u5b9e\u6570\u5e8f\u5217\u5f53\u4f5c\u865a\u90e8\u4e3a\u96f6\u7684\u590d\u6570\u5bf9\u5f85\uff0c\u663e\u7136\u9700\u8981\u5b58\u50a8\u865a\u90e8\u7684\u96f6\u5e76\u8fdb\u884c\u65e0\u529f\u7684\u8fd0\u7b97\uff0c\u65e2\u6d6a\u8d39\u4e86\u4e00\u500d\u7684\u8ba1\u7b97\u5185\u5b58\uff0c\u53c8\u964d\u4f4e\u4e86\u7ea6\u4e00\u534a\u7684\u8fd0\u7b97\u901f\u5ea6\u3002
\u4e3a\u4e86\u4e0d\u6d6a\u8d39\u4e0d\u53ef\u4e0d\u8bbe\u7684\u865a\u90e8\u5185\u5b58\u548c\u5fc5\u7136\u51fa\u73b0\u7684\u590d\u6570\u8fd0\u7b97\uff0c\u53ef\u5426\u5c06\u4e00\u4e2a\u5b9e\u5e8f\u5217\u5206\u4e3a\u4e24\u4e2a\u5b50\u5b9e\u5e8f\u5217\uff0c\u5206\u522b\u4f5c\u4e3a\u5b9e\u90e8\u4e0e\u865a\u90e8\u6784\u6210\u4e00\u4e2a\u590d\u6570\u5e8f\u5217\uff0c\u7136\u540e\u7528\u590d\u5e8f\u5217\u7684FFT\u7b97\u6cd5\u6c42\u5176\u9891\u8c31\uff0c\u5bf9\u5408\u6210\u7684\u590d\u5e8f\u5217\u9891\u8c31\u8fdb\u884c\u5206\u79bb\u548c\u52a0\u5de5\u5f97\u5230\u539f\u5b9e\u5e8f\u5217\u7684\u9891\u8c31\u5462\uff1f\u7b54\u6848\u662f\u80af\u5b9a\u7684\uff0c\u5b9e\u73b0\u8fd9\u4e00\u8fc7\u7a0b\u601d\u8def\u5c31\u662f\u5b9e\u5e8f\u5217FFT\u7b97\u6cd5\u7684\u57fa\u672c\u601d\u60f3\u3002
1.\u5b9e\u5e8f\u5217\u7684\u5085\u91cc\u53f6\u53d8\u6362\u6027\u8d28
\u5bf9\u4e8e\u4e00\u4e2aN\u4e2a\u6837\u672c\u7684\u5b9e\u5e8f\u5217x\uff08k\uff09\uff0c\u5176\u9891\u8c31\u4e3aX\uff08j\uff09\uff0c\u7528Xr\uff08j\uff09\u548cXi\uff08j\uff09\u8868\u793aX\uff08j\uff09\u7684\u5b9e\u90e8\u548c\u865a\u90e8\uff0c \u8868\u793aX\uff08j\uff09\u7684\u5171\u8f6d\uff0c\u5219
\u8bc1\u660e\uff1a\u5df2\u77e5 \u5219
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u4e0a\u5f0f\u4e24\u7aef\u53d6\u5171\u8f6d\uff0c\u5e76\u6ce8\u610f\u5230x\uff08k\uff09\u662f\u5b9e\u5e8f\u5217\uff0c\u5219
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u8fd9\u5c31\u662f\u5b9e\u5e8f\u5217\u7684\u5085\u91cc\u53f6\u53d8\u6362\u5177\u6709\u590d\u5171\u8f6d\u6027\u3002
\u5176\u540c\u6837\u5177\u6709\u5468\u671f\u6027\uff0c\u5373
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
2.\u4e00\u7ef4\u5b9e\u5e8f\u5217\u7684FFT\u7b97\u6cd5
\uff081\uff09\u540c\u65f6\u8ba1\u7b97\u4e24\u4e2a\u5b9e\u5e8f\u5217\u7684FFT\u7b97\u6cd5
\u5df2\u77e5\u4e24\u4e2a\u5b9e\u5e8f\u5217h\uff08k\uff09\uff0cg\uff08k\uff09\uff08k\uff1d0\uff0c1\uff0c\u2026\uff0cN\uff0d1\uff09\uff0c\u4f8b\u5982\u91cd\u78c1\u5f02\u5e38\u5e73\u9762\u6570\u636e\u4e2d\u7684\u4e24\u6761\u5256\u9762\uff0c\u6216\u5730\u9707\u52d8\u63a2\u4e2d\u7684\u4e24\u9053\u5730\u9707\u8bb0\u5f55\uff0c\u53ef\u4ee5\u4eba\u4e3a\u5730\u6784\u6210\u4e00\u4e2a\u590d\u5e8f\u5217\uff1a
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u8bbeh\uff08k\uff09\u7684\u9891\u8c31\u4e3aH\uff08j\uff09\uff1dHr\uff08j\uff09\uff0biHi\uff08j\uff09
g\uff08k\uff09\u7684\u9891\u8c31\u4e3aG\uff08j\uff09\uff1dGr\uff08j\uff09\uff0biGi\uff08j\uff09
y\uff08k\uff09\u7684\u9891\u8c31\u4e3aY\uff08j\uff09\uff1dYr\uff08j\uff09\uff0bi Yi\uff08j\uff09
\u5229\u7528\u4e0a\u8282\u7684\u590d\u5e8f\u5217FFT\u7b97\u6cd5\uff0c\u6c42\u5f97Y\uff08j\uff09\uff0c\u5373Yr\uff08j\uff09\u548cYi\uff08j\uff09\u5df2\u77e5\uff0c\u6765\u5bfb\u627eHr\uff08j\uff09\uff0cHi\uff08j\uff09\uff0cGr\uff08j\uff09\uff0cGi\uff08j\uff09\u4e0eYr\uff08j\uff09\uff0cYi\uff08j\uff09\u4e4b\u95f4\u7684\u5173\u7cfb\u3002
\u5bf9\u5f0f\uff088\uff0d22\uff09\u4f5c\u5085\u91cc\u53f6\u53d8\u6362\uff1a
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u7531\u4e8eH\uff08j\uff09\uff0cG\uff08j\uff09\u672c\u8eab\u662f\u590d\u5e8f\u5217\uff0c\u6240\u4ee5\u4e0d\u80fd\u4ec5\u4ece\u4e0a\u5f0f\u5206\u79bb\u51faH\uff08j\uff09\u548cG\uff08j\uff09\u3002\u5e94\u7528Y\uff08j\uff09\u7684\u5468\u671f\u6027\uff0c\u5bb9\u6613\u5f97\u5230
Y\uff08N\uff0dj\uff09\uff1dH\uff08\uff0dj\uff09\uff0biG\uff08\uff0dj\uff09
\u4e0a\u5f0f\u53d6\u5171\u8f6d\uff1a
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u7531\u4e8eh\uff08k\uff09\uff0cg\uff08k\uff09\u4e3a\u5b9e\u5e8f\u5217\uff0c\u5bf9\u4e0a\u5f0f\u53f3\u7aef\u5e94\u7528\u590d\u5171\u8f6d\u5b9a\u7406\uff0c\u5f97
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u5bf9\u5f0f\uff088\uff0d23\uff09\u5c55\u5f00\uff0c\u5f97
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u5bf9\u5f0f\uff088\uff0d24\uff09\u5c55\u5f00\uff0c\u5e76\u5e94\u7528\u5171\u8f6d\u5173\u7cfb\uff0c\u5f97
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u628a\u5f0f\uff088\uff0d25\uff09\u548c\u5f0f\uff088\uff0d26\uff09\u4e0eY\uff08j\uff09\uff1dYr\uff08j\uff09\uff0biYi\uff08j\uff09\u8fdb\u884c\u5bf9\u6bd4\uff0c\u6709
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u6574\u7406\u5f97
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u56e0\u6b64\uff0c\u5bf9\u4e8e\u4e24\u4e2a\u5b9e\u5e8f\u5217\uff0c\u901a\u8fc7\u6784\u9020\u4e00\u4e2a\u590d\u5e8f\u5217\uff0c\u5e94\u7528\u590d\u5e8f\u5217\u7684FFT\u7b97\u6cd5\u548c\u5f0f\uff088\uff0d28\uff09\u7684\u5206\u79bb\u52a0\u5de5\uff0c\u5373\u53ef\u5f97\u5230\u4e24\u4e2a\u5b9e\u5e8f\u5217\u7684\u9891\u8c31\u3002
\uff082\uff09\u8ba1\u7b972 N\u4e2a\u6570\u636e\u70b9\u7684\u5b9e\u5e8f\u5217FFT\u7b97\u6cd5
\u8bbe\u67092N\u70b9\u7684\u5b9e\u5e8f\u5217u\uff08k\uff09\uff08k\uff1d0\uff0c1\uff0c\u2026\uff0c2N\uff0d1\uff09\uff0c\u9996\u5148\u6309k\u7684\u5076\u3001\u5947\u5206\u6210\u4e24\u4e2a\u5b50\u5b9e\u5e8f\u5217\uff0c\u5e76\u6784\u6210\u590d\u5e8f\u5217\uff0c\u5373
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u901a\u8fc7\u8c03\u7528\u590d\u5e8f\u5217FFT\u7b97\u6cd5\uff0c\u6c42\u5f97y\uff08k\uff09\u7684\u9891\u8c31\u4e3aY\uff08j\uff09\u3002\u53e6\u8bb0h\uff08k\uff09\uff0cg\uff08k\uff09\u7684\u9891\u8c31\u4e3aH\uff08j\uff09\u548cG\uff08j\uff09\u3002
\u5229\u7528\u524d\u9762\u5f0f\uff088\uff0d23\uff09\u548c\u5f0f\uff088\uff0d24\uff09\uff0c\u5bb9\u6613\u6c42\u5f97
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u4e0b\u9762\u5206\u6790\u7528H\uff08j\uff09\uff0cG\uff08j\uff09\u5f62\u6210u\uff08k\uff09\u9891\u8c31\u7684\u95ee\u9898\u3002\u8bb0u\uff08k\uff09\uff08k\uff1d0\uff0c1\uff0c\u2026\uff0c2 N\uff0d1\uff09\u7684\u9891\u8c31\u4e3aV\uff08j\uff09\uff0c\u5206\u6790V\uff08j\uff09\uff0cH\uff08j\uff09\uff0cG\uff08j\uff09\u4e4b\u95f4\u7684\u5173\u7cfb\uff0c\u6839\u636e\u5b9a\u4e49
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u5229\u7528\u5f0f\uff088\uff0d31\uff09\u548c\u5f0f\uff088\uff0d34\uff09\u53ef\u6362\u7b97\u51fau\uff08k\uff09\u7684\u524dN\u4e2a\u9891\u8c31V\uff08j\uff09\uff08j\uff1d0\uff0c1\uff0c\u2026\uff0cN\uff0d1\uff09\uff0c\u8fd8\u8981\u8bbe\u6cd5\u6c42u\uff08k\uff09\u7684\u540eN\u4e2a\u9891\u8c31V\uff08N\uff0bj\uff09\uff08j\uff1d0\uff0c1\uff0c\u2026\uff0cN\uff0d1\uff09\u3002\u5229\u7528\u5b9e\u5e8f\u5217\u5176\u9891\u8c31\u7684\u590d\u5171\u8f6d\u548c\u5468\u671f\u6027\uff1a
\uff081\uff09H\uff08N\uff09\uff1dH\uff080\uff09\uff0cG\uff08N\uff09\uff1dG\uff080\uff09\uff0cWN1\uff1d\uff0d1\uff0c\u5f97
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\uff082\uff09\u7531\u4e8eu\uff08k\uff09\uff08k\uff1d0\uff0c1\uff0c\u2026\uff0c2N\uff0d1\uff09\u662f\u5b9e\u5e8f\u5217\uff0c\u540c\u6837\u5229\u7528\u5b9e\u5e8f\u5217\u5176\u9891\u8c31\u7684\u590d\u5171\u8f6d\u548c\u5468\u671f\u6027\uff0c\u7528\u5df2\u6c42\u51fa\u7684\u524dN\u4e2a\u9891\u8c31V\uff08j\uff09\u8868\u793a\u51fa\u540e\u9762\u7684N\uff0d1\u4e2a\u9891\u8c31V\uff08N\uff0bj\uff09\uff1a
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u7531\u4e8e0<2N\uff0dj<N\uff0c\u6240\u4ee5\u53ef\u4eceV\uff08j\uff09\uff08j\uff1d0\uff0c1\uff0c\u2026\uff0cN\uff0d1\uff09\u4e2d\u9009\u51faV\uff082N\uff0dj\uff09\uff08j\uff1dN\uff0b1\uff0cN\uff0b2\uff0c\u2026\uff0c2 N\uff0d1\uff09\uff0c\u5e76\u76f4\u63a5\u53d6\u5176\u5171\u8f6d \u5373\u53ef\u5f97\u5230V\uff08N\uff0b1\uff09\uff5eV\uff082 N\uff0d1\uff09\uff0c\u4ece\u800c\u5b8c\u6210\u6574\u4e2a\u5b9e\u5e8f\u5217\u9891\u8c31\u7684\u8ba1\u7b97\u3002
\u603b\u7ed3\u4ee5\u4e0a\u53d9\u8ff0\uff0c\u4e00\u7ef4\u5b9e\u5e8f\u5217u\uff08k\uff09\uff08k\uff1d0\uff0c1\uff0c\u2026\uff0c2N\uff0d1\uff09\u7684FFT\u8ba1\u7b97\u7f16\u7a0b\u6b65\u9aa4\u5982\u4e0b\uff1a
\uff081\uff09\u6309\u5076\u3001\u5947\u62c6\u5206\u5b9e\u5e8f\u5217u\uff08k\uff09\uff0c\u5e76\u6784\u9020\u590d\u5e8f\u5217\uff1a
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\uff082\uff09\u8c03\u7528\u590d\u5e8f\u5217\u7684FFT\u8ba1\u7b97y\uff08k\uff09\u7684\u9891\u8c31Y\uff08j\uff09\uff08j\uff1d0\uff0c1\uff0c\u2026\uff0cN\uff0d1\uff09\uff1b
\uff083\uff09\u7528\u4e0b\u5f0f\u8ba1\u7b97\u5f62\u6210h\uff08k\uff09\uff0cg\uff08k\uff09\u7684\u9891\u8c31H\uff08j\uff09\u548cG\uff08j\uff09\uff1b
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\uff084\uff09\u7528\u4e0b\u5f0f\u6362\u7b97\u5b9e\u5e8f\u5217u\uff08k\uff09\u7684\u9891\u8c31V\uff08j\uff09\uff08j\uff1d0\uff0c1\uff0c\u2026\uff0c2 N\uff0d1\uff09\uff1a
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\uff3b\u4f8b3\uff3d\u6c42\u5b9e\u5e8f\u5217\u6837\u672cu\uff08k\uff09\uff1d\uff5b1\uff0c2\uff0c1\uff0c1\uff0c3\uff0c2\uff0c1\uff0c2\uff5d\uff08k\uff1d0\uff0c1\uff0c\u2026\uff0c7\uff09\u7684\u9891\u8c31\u3002
\u89e3\uff1a\u6309\u5076\u3001\u5947\u62c6\u5206\u5b9e\u5e8f\u5217u\uff08k\uff09\uff0c\u6309\u5f0f\uff088\uff0d37\uff09\u6784\u9020\u590d\u5e8f\u5217c\uff08j\uff09\uff08j\uff1d0\uff0c1\uff0c2\uff0c3\uff09\uff0c\u5373
c\uff080\uff09\uff1d1\uff0b2i\uff1b c\uff081\uff09\uff1d1\uff0bi\uff1b c\uff082\uff09\uff1d3\uff0b2i\uff1b c\uff083\uff09\uff1d1\uff0b2i\u3002
\uff081\uff09\u8c03\u7528\u590d\u5e8f\u5217FFT\u6c42c\uff08j\uff09\uff08j\uff1d0\uff0c1\uff0c2\uff0c3\uff09\u7684\u9891\u8c31Z\uff08k\uff09\uff08k\uff1d0\uff0c1\uff0c2\uff0c3\uff09\uff0c\u5f97
Z\uff080\uff09\uff1d6\uff0b7i\uff1b Z\uff081\uff09\uff1d\uff0d3\uff1b Z\uff082\uff09\uff1d2\uff0bi\uff1b Z\uff083\uff09\uff1d\uff0d1\u3002
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\uff083\uff09\u8fd0\u7528\u516c\u5f0f\uff088\uff0d38\uff09\u8ba1\u7b97H\uff08j\uff09\uff0cG\uff08j\uff09\uff1a
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\uff084\uff09\u6839\u636e\u5f0f\uff088\uff0d39\uff09\u6c42\u51fau\uff08k\uff09\uff08k\uff1d0\uff0c1\uff0c\u2026\uff0c7\uff09\u76848\u4e2a\u9891\u8c31V\uff08j\uff09\uff08j\uff1d0\uff0c1\uff0c\u2026\uff0c7\uff09\uff1a
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u5730\u7403\u7269\u7406\u6570\u636e\u5904\u7406\u57fa\u7840
\u7531\u4e0a\u4f8b\u53ef\u89c1\uff0c\u5b8c\u6210\u5168\u90e82 N\u4e2a\u5b9e\u5e8f\u5217\u9891\u8c31\u7684\u8ba1\u7b97\u53ea\u9700\u505aN\u6b21FFT\u8ba1\u7b97\uff0c\u76f8\u6bd4\u76f4\u63a5\u7528\u590d\u5e8f\u5217\u7684FFT\u7b97\u6cd5\u8282\u7701\u4e86\u7ea6\u4e00\u534a\u7684\u8ba1\u7b97\u91cf\u3002
\u7b2c\u4e00\uff0c\u4ece\u5b9a\u4e49\u5f0f\u4e0a\u770b\uff0c\u79ef\u5206\u53f7\u91cc\u542b\u6709\u590d\u6570\uff0c\u79ef\u5206\u7ed3\u679c\u662f\u590d\u6570\uff1b
\u7b2c\u4e8c\uff0c\u4ece\u5085\u7acb\u53f6\u53d8\u6362\u7684\u7269\u7406\u610f\u4e49\u4e0a\u770b\uff1aFT\u53d8\u6362\u662f\u5c06\u4e00\u4e2a\u4fe1\u53f7\u5206\u89e3\u4e3a\u591a\u4e2a\u4fe1\u53f7\u4e4b\u548c\u7684\u5f62\u5f0f\uff0c\u5e76\u4e14\u662f\u6b63\u5f26\u6216\u4f59\u5f26\u4fe1\u53f7\u53e0\u52a0\u7684\u5f62\u5f0f\uff1b\u6211\u4eec\u77e5\u9053\uff0c\u51b3\u5b9a\u4e00\u4e2a\u6b63\u5f26\u6ce2\u7684\u662f\u5176\u632f\u5e45\u548c\u76f8\u4f4d\uff0c\u4e8c\u8005\u7f3a\u4e00\u4e0d\u53ef\u3002
\u800c\u5b9e\u6570\u53ea\u80fd\u8868\u793a\u632f\u5e45\u6216\u8005\u76f8\u4f4d\uff0c\u800c\u590d\u6570\u662f\u4e8c\u7ef4\u5e73\u9762\u4e0a\u7684\uff0c\u53ef\u4ee5\u540c\u65f6\u8868\u793a\u632f\u5e45\u548c\u76f8\u4f4d\uff0c\u6240\u4ee5\u7528\u590d\u6570\u8868\u793a\u3002\u9891\u8c31\u662f\u590d\u6570\u5f62\u5f0f\uff0c\u53ef\u4ee5\u5206\u89e3\u4e3a\u632f\u5e45\u8c31\u548c\u76f8\u4f4d\u8c31\uff0c\u5b83\u4eec\u662f\u5b9e\u6570\u5f62\u5f0f\u3002
\u6269\u5c55\u8d44\u6599\uff1a
\u5728\u4e00\u4e2a\u4ee52T\u4e3a\u5468\u671f\u5185f(X)\u8fde\u7eed\u6216\u53ea\u6709\u6709\u9650\u4e2a\u7b2c\u4e00\u7c7b\u95f4\u65ad\u70b9\uff0c\u9644f\uff08x\uff09\u5355\u8c03\u6216\u53ef\u5212\u5206\u6210\u6709\u9650\u4e2a\u5355\u8c03\u533a\u95f4\uff0c\u5219F\uff08x\uff09\u4ee52T\u4e3a\u5468\u671f\u7684\u5085\u91cc\u53f6\u7ea7\u6570\u6536\u655b\uff0c\u548c\u51fd\u6570S\uff08x\uff09\u4e5f\u662f\u4ee52T\u4e3a\u5468\u671f\u7684\u5468\u671f\u51fd\u6570\uff0c\u4e14\u5728\u8fd9\u4e9b\u95f4\u65ad\u70b9\u4e0a\uff0c\u51fd\u6570\u662f\u6709\u9650\u503c\uff1b\u5728\u4e00\u4e2a\u5468\u671f\u5185\u5177\u6709\u6709\u9650\u4e2a\u6781\u503c\u70b9\uff1b\u7edd\u5bf9\u53ef\u79ef\u3002
\u5c06\u6ee1\u8db3\u4e00\u5b9a\u6761\u4ef6\u7684\u67d0\u4e2a\u51fd\u6570\u8868\u793a\u6210\u4e09\u89d2\u51fd\u6570\uff08\u6b63\u5f26\u548c/\u6216\u4f59\u5f26\u51fd\u6570\uff09\u6216\u8005\u5b83\u4eec\u7684\u79ef\u5206\u7684\u7ebf\u6027\u7ec4\u5408\u3002\u5728\u4e0d\u540c\u7684\u7814\u7a76\u9886\u57df\uff0c\u5085\u7acb\u53f6\u53d8\u6362\u5177\u6709\u591a\u79cd\u4e0d\u540c\u7684\u53d8\u4f53\u5f62\u5f0f\uff0c\u5982\u8fde\u7eed\u5085\u7acb\u53f6\u53d8\u6362\u548c\u79bb\u6563\u5085\u7acb\u53f6\u53d8\u6362\u3002\u6700\u521d\u5085\u7acb\u53f6\u5206\u6790\u662f\u4f5c\u4e3a\u70ed\u8fc7\u7a0b\u7684\u89e3\u6790\u5206\u6790\u7684\u5de5\u5177\u88ab\u63d0\u51fa\u7684\u3002
\u53c2\u8003\u8d44\u6599\u6765\u6e90\uff1a\u767e\u5ea6\u767e\u79d1--\u5085\u91cc\u53f6\u53d8\u6362
设x（N）为N点有限长离散序列，代入式（8－3）、式（8－4），并令 其傅里叶变换（DFT）为
地球物理数据处理基础
反变换（IDFT）为
地球物理数据处理基础
两者的差异只在于W的指数符号不同，以及差一个常数1/N，因此下面我们只讨论DFT正变换式（8－5）的运算量，其反变换式（8－6）的运算是完全相同的。
一般来说，W是复数，因此，X（j）也是复数，对于式（8－5）的傅里叶变换（DFT），计算一个X（j）值需要N次复数乘法和N－1次复数加法。而X（j）一共有N个值（j＝0，1，…，N－1），所以完成整个DFT运算总共需要N2次复数乘法和N（N－1）次复数加法。
直接计算DFT，乘法次数和加法次数都是与N2成正比的，当N很大时，运算量会很大，例如，当N＝8时，DFT需64次复数乘法；而当N＝1024时，DFT所需乘法为1048576次，即一百多万次的复数乘法运算，对运算速度要求高。所以需要改进DFT的计算方法，以减少运算次数。
分析Wjk，表面上有N2个数值，由于其周期性，实际上仅有N个不同的值W0，W1，…，WN－1。对于N＝2m时，由于其对称性，只有N/2个不同的值W0，W1，…，
地球物理数据处理基础
因此可以把长序列的DFT分解为短序列DFT，而前面已经分析DFT与N2成正比，所以N越小越有利。同时，利用ab＋ac＝a（b＋c）结合律法则，可以将同一个Wr对应的系数x（k）相加后再乘以Wr，就能大大减少运算次数。这就是快速傅里叶变换（FFT）的算法思路。下面，我们来分析N＝2m情况下的FFT算法。
1.N＝4的FFT算法
对于m＝2，N＝4，式（8－5）傅里叶变换为
地球物理数据处理基础
将式（8－7）写成矩阵形式
地球物理数据处理基础
为了便于分析，将上式中的j，k写成二进制形式，即
地球物理数据处理基础
代入式（8－7），得
地球物理数据处理基础
分析Wjk的周期性来减少乘法次数
地球物理数据处理基础
则 代回式（8－9），整理得
地球物理数据处理基础
上式可分层计算，先计算内层，再计算外层时就利用内层计算的结果，可避免重复计算。写成分层形式
地球物理数据处理基础
则X（j1 j0）＝X2（j1 j0）。
上式表明对于N＝4的FFT，利用Wr的周期关系可分为m＝2步计算。实际上，利用Wr的对称性，仍可以对式（8－11）进行简化计算。考虑到
地球物理数据处理基础
式（8－11）可以简化为
地球物理数据处理基础
令j＝j0；k＝k0，并把上式表示为十进制，得
地球物理数据处理基础
可以看到，完成上式N＝4的FFT计算（表8－1）需要N·（m－1）/2＝2次复数乘法和N·m＝8次复数加法，比N＝4的DFT算法的N2＝16次复数乘法和N·（N－1）＝12次复数加法要少得多。
表8－1 N＝4的FFT算法计算过程
注：W0＝1；W1＝－i。
［例1］求N＝4样本序列1，3，3，1的频谱（表8－2）。
表8－2 N＝4样本序列
2.N＝8的FFT算法
类似N＝4的情况，用二进制形式表示，有
地球物理数据处理基础
写成分层计算的形式：
地球物理数据处理基础
则X（j2 j1 j0）＝X3（j2 j1 j0）。
对式（8－14）的X1（k1 k0 j0）进行展开，有
地球物理数据处理基础
还原成十进制，并令k＝2k1＋k0，即k＝0，1，2，3，有
地球物理数据处理基础
用类似的方法对式（8－14）的X2（k0 j1 j0），X3（j2 j1 j0）进行展开，整理得
地球物理数据处理基础
用式（8－16）、式（8－17）逐次计算到X3（j）＝X（j）（j＝0，1，…，7），即完成N＝23＝8的FFT计算，其详细过程见表8－3。
表8－3 N＝8的FFT算法计算过程
注：对于正变换 对于反变换 所
［例2］求N＝8样本序列（表8－4）x（k）＝1，2，1，1，3，2，1，2的频谱。
表8－4 N＝8样本序列
3.任意N＝2m的FFT算法
列出N＝4，N＝8的FFT计算公式，进行对比
地球物理数据处理基础
观察式（8－18）、式（8－19），不难看出，遵循如下规律：
（1）等式左边的下标由1递增到m，可用q＝1，2，…，m代替，则等式右边为q－1；
（2）k的上限为奇数且随q的增大而减小，至q＝m时为0，所以其取值范围为k＝0，1，2，…，（2m－q－1）；
（3）j的上限为奇数且随q的增大而增大，且q＝1时为0，其取值范围为j＝0，1，2，…，（2q－1－1）；
（4）k的系数，在等式左边为2q，等式右边为2q－1（包括W的幂指数）；
（5）等式左边序号中的常数是2的乘方形式，且幂指数比下标q小1，即2q－1；等式右边m对式子序号中的常数都是定值2m－1。
归纳上述规则，写出对于任意正整数m，N＝2m的FFT算法如下：
由X0（p）＝x（p）（p＝0，1，…，N－1）开始：
（1）对q＝1，2，…，m，执行（2）～（3）步；
（2）对k＝0，1，2，…，（2m－q－1）及j＝0，1，2，…，（2q－1－1），执行
地球物理数据处理基础
（3）j，k循环结束；
（4）q循环结束；由Xm（p）（p＝0，1，…，N－1）输出原始序列x（p）的频谱X（p）。
在计算机上很容易实现上述FFT算法程序，仅需要三个复数数组，编程步骤如下：
（1）设置复数数组X1（N－1），X2（N－1）和 （数组下界都从0开始）；
（2）把样本序列x赋给X1，即X1（k）＝x（k）（k＝0，1，…，N－1）；
（3）计算W，即正变换 反变换
（4）q＝1，2，…，m，若q为偶数，执行（6），否则执行第（5）步；
（5）k＝0，1，2，…，（2m－q－1）和j＝0，1，2，…，（2q－1－1）循环，作
X2（2qk＋j）＝X1（2q－1k＋j）＋X1（2q－1k＋j＋2m－1）
X2（2qk＋j＋2q－1）＝［X1（2q－1k＋j）－X1（2q－1k＋j＋2m－1）］W（2q－1k）
至k，j循环结束；
（6）k＝0，1，2，…，（2m－q－1）和j＝0，1，2，…，（2q－1－1）循环，作
X1（2qk＋j）＝X2（2q－1k＋j）＋X2（2q－1k＋j＋2m－1）
X1（2qk＋j＋2q－1）＝［X2（2q－1k＋j）－X2（2q－1k＋j＋2m－1）］W（2q－1k）
至k，j循环结束；
（7）q循环结束，若m为偶数，输出X1（j），否则输出X2（j）（j＝0，1，…，N－1），即为所求。
绛旓細鍏朵腑锛孎(蠅) 琛ㄧず棰戝煙鐨澶嶆暟鍑芥暟锛宖(t) 琛ㄧず鏃跺煙鐨勫嚱鏁帮紝蠅 鏄鐜囷紝j 鏄櫄鏁板崟浣嶃2. 绂绘暎鏃堕棿鍌呴噷鍙跺彉鎹紙Discrete Fourier Transform锛夛細F(k) = 危[f(n) * e^(-j(2蟺/N)kn)]锛屽 n = 0 to N-1 鍏朵腑锛孎(k) 琛ㄧず棰戝煙鐨勫鏁板嚱鏁帮紝f(n) 琛ㄧず鏃跺煙鐨勭鏁ｅ簭鍒楋紝N 鏄搴忓垪鐨闀垮害锛...
绛旓細褰撳悜閲忓拰鐭╅樀鏄澶嶆暟鏃讹紝姹備袱涓鍚戦噺鐨勫唴绉 鍌呴噷鍙跺鏁扮煩闃碉紝鐗规畩鐨勫揩閫熷倕閲屽彾鍙樻崲(绠绉癋FT)鍦ㄨ绠楁満缁忓父鐢ㄥ埌锛岀壒鍒槸娑夊強澶ф暟鎹殑鏃跺欙紝瀹冨彲浠ュ緢蹇熺殑杩涜鍌呴噷鍙跺彉鎹傚仛涔樻硶鏃舵庢牱鎵嶈兘蹇熺敤杩欎釜 闃舵柟闃靛仛涔樻硶锛岄氬父 闃舵柟闃电殑涔樻硶瑕佺畻 娆★紝鍥犱负鏈 涓潪闆跺厓绱狅紝杩欐槸涓煩闃碉紝涓斿垪鍚戦噺姝ｄ氦锛岃...
绛旓細DFT鐨勫熀鏈濇兂鏄皢涓涓湁闄愰暱鐨勭鏁ｄ俊鍙峰簭鍒楄浆鎹负涓缁澶嶆暟鐨勫簭鍒锛岃繖浜涘鏁拌〃绀轰簡淇″彿涓笉鍚岄鐜囧垎閲忕殑骞呭害鍜岀浉浣嶄俊鎭傚湪瀹為檯搴旂敤涓紝鎴戜滑閫氬父浣跨敤蹇熷倕閲屽彾鍙樻崲锛FFT锛夌畻娉曟潵璁＄畻DFT锛屽洜涓篎FT绠楁硶鍦ㄨ绠楁晥鐜囦笂杩滈珮浜庣洿鎺ョ殑DFT绠楁硶銆侳FT閫氳繃鍒╃敤DFT鐨勫绉版у拰鍛ㄦ湡鎬э紝灏嗚绠楀鏉傚害浠嶰(N^2)闄嶄綆鍒癘(...
绛旓細杩欎釜鏄暟瀛椾俊鍙峰鐞嗛鍩熼噷鐨勪竴涓叿鏈夊垝鏃朵唬鎰忎箟鐨勫彂鐜帮紝浣垮緱绂绘暎鍌呯珛鍙跺彉鎹㈢殑璁＄畻閲忓噺灏戜簡鍑犱釜鏁伴噺绾э紝浣胯绠楁満瀹炵幇瀹炴椂澶勭悊鎴愪负鍙兘銆傝嚜浠庡簱鍒╋紝鍥惧熀涓や汉鐨勫叧浜蹇熷倕绔嬪彾鍙樻崲璁＄畻鏂规硶鐨勮鏂囧彂琛ㄤ互鏉ワ紝鏁板瓧淇″彿澶勭悊浠庤繛缁俊鍙峰鐞嗕腑鐙珛鍑烘潵锛屽舰鎴愪竴涓畬鏁翠綋绯汇傚畠鏄繎浠ｈ绠楁満鎶鏈閫熷彂灞曠殑鍩虹銆傚叧浜澶嶆暟搴忓垪...
绛旓細蹇熷倕姘忓彉鎹紝鏄鏁ｅ倕姘忓彉鎹鐨勫揩閫绠楁硶锛屽畠鏄牴鎹鏁ｅ倕姘忓彉鎹㈢殑濂囥佸伓銆佽櫄銆佸疄绛夌壒鎬э紝瀵圭鏁鍌呯珛鍙跺彉鎹鐨勭畻娉曡繘琛屾敼杩涜幏寰楃殑銆傚畠瀵瑰倕姘忓彉鎹㈢殑鐞嗚骞舵病鏈夋柊鐨勫彂鐜帮紝浣嗘槸瀵逛簬鍦ㄨ绠楁満绯荤粺鎴栬呰鏁板瓧绯荤粺涓簲鐢ㄧ鏁ｅ倕绔嬪彾鍙樻崲锛屽彲浠ヨ鏄繘浜嗕竴澶ф銆傝x(n)涓篘椤圭殑澶嶆暟搴忓垪锛岀敱DFT鍙樻崲锛屼换涓X锛坢...
绛旓細鐢熸垚涓涓簩缁翠俊鍙凤紙浜岀淮鐭╅樀锛夎繖閲屼互涓涓 4x4 鐨勯殢鏈虹煩闃典綔涓虹ず渚 signal = rand(4, 4);鎸夊垪灞曞紑浜岀淮淇″彿涓轰竴缁村悜閲 signal_1d = signal(:);杩涜涓缁村倕閲屽彾鍙樻崲 f_signal_1d = fft(signal_1d);灏嗕竴缁村倕閲屽彾绯绘暟閲嶆柊鎺掑垪涓轰簩缁村舰寮 f_signal_2d = reshape(f_signal_1d, size(signal));鏄剧ず...
绛旓細瑕佸緱鍒颁竴涓疄鏁板簭鍒楋紝杈撳叆鍒癷fft锛堥蹇熷倕閲屽彾鍙樻崲锛夌殑鏁版嵁闇瑕佹弧瓒冲叡杞绉扮殑鏉′欢銆傚叿浣撴潵璇达紝瀵逛簬涓涓暱搴︿负N鐨澶嶆暟搴忓垪X[k]锛屽鏋淴[k] = X*[N-k]锛堝叾涓*琛ㄧず鍏辫江锛宬鐨勮寖鍥存槸0鍒癗-1锛夛紝閭ｄ箞瀵筙[k]杩涜ifft鍙樻崲鍚庡緱鍒扮殑搴忓垪x[n]灏辨槸瀹炴暟搴忓垪銆傞鍏堬紝鎴戜滑鏉ヨВ閲婁竴涓嬪叡杞绉扮殑姒傚康銆傚叡杞...
绛旓細4. 蹇熷倕閲屽彾鍙樻崲锛FFT锛夛細FFT鏄疍FT鐨勪竴绉嶅揩閫熺畻娉曘傜敱浜庡鏁扮殑鍔犳硶鍜屼箻娉曡绠楅噺杈冨ぇ锛孎FT鍒╃敤浜咲FT涓澶嶆暟搴忓垪鐨鍛ㄦ湡鎬у拰瀵圭О鎬э紝閫氳繃灏嗗簭鍒楁寜濂囧伓鍒嗙粍锛岄掑綊鍦板皢闂鍒嗚В涓烘洿灏忕殑瀛愰棶棰橈紝浠庤屾樉钁楀噺灏戜簡璁＄畻閲忋侳FT骞舵病鏈夊鍌呴噷鍙跺彉鎹㈢殑鐞嗚鍋氬嚭鏂扮殑鍙戠幇锛屼絾瀹冩瀬澶у湴鎺ㄨ繘浜嗗湪璁＄畻鏈虹郴缁熷拰鏁板瓧绯荤粺涓...
绛旓細浣犱滑鑰佸笀鎵璇寸殑澶嶆暟搴忓垪鍙互绉颁箣涓鸿В鏋愪俊鍙凤紝涔熷氨鏄叾瀹為儴鍜岃櫄閮ㄦ弧瓒冲笇灏斾集鐗鍙樻崲銆傝В鏋愪俊鍙峰繀鐒舵槸澶嶄俊鍙凤紝鍏跺棰戝煙涓洪浂銆傝繖鏍峰湪淇″彿澶勭悊涓湁璇稿鏂逛究涔嬪锛屾瘮濡傝鐢变簬澶嶉鍩熶负闆讹紝鍦ㄤ俊鍙锋娊鏍锋椂锛屼笉鍙戠敓娣峰彔鐨勬渶浣庢娊鏍烽鐜囦篃浼氫笅闄嶅埌鍘熸潵鐨1/2銆
绛旓細鍦ㄤ笉鍚岀殑鐮旂┒棰嗗煙锛屽倕绔嬪彾鍙樻崲鍏锋湁澶氱涓嶅悓鐨勫彉浣撳舰寮忥紝濡傝繛缁倕绔嬪彾鍙樻崲鍜岀鏁ｅ倕绔嬪彾鍙樻崲銆傛渶鍒濆倕绔嬪彾鍒嗘瀽鏄綔涓虹儹杩囩▼鐨勮В鏋愬垎鏋愮殑宸ュ叿琚彁鍑虹殑銆傛暣浣撶粨鏋勶細鍏朵腑锛學N=exp锛堬紞2pi/N)銆俋(k锛夊拰x(n锛夐兘涓澶嶆暟銆備笌涔嬬浉瀵鐨勫揩閫熷倕閲屽彾鍙樻崲鏈夊緢澶氱锛屽DIT锛堟椂鍩熸娊鍙栨硶锛夈丏IF锛堥鍩熸娊鍙栨硶锛夈...
