二维实序列的快速傅里叶变换（FFT） 谁能帮我调试一下这个二维快速傅里叶变换FFT2D的逆变换C+...

\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

\u6211\u9760 \u4ee3\u7801\u8fde\u4e00\u53e5\u6ce8\u91ca\u4e5f\u6ca1\u6709 \u4ee3\u7801\u5206\u5272\u4e5f\u597d\u4e11 \uff0c\u52a0\u70b9\u4e0b\u73ed\u4e86\u56de\u53bb\u5e2e\u4f60\u770b\u770b

在地球物理数据处理中，经常遇到处理二维实数据的情况。例如在地震勘探中，对面波勘探数据作频散分析解释时，要将时间－空间域的信息转换为频率－波数域频谱；在重磁异常的滤波或转换中，要将空间域的异常f（x，y）转换为波数域F（ω，υ）等。这些分析都需要进行二维的傅里叶变换（FFT）。

根据傅里叶变换的定义，对于连续二维函数f（x，y），其傅里叶变换对为

地球物理数据处理基础

对于离散的二维序列f_jk（j＝0，1，…，M－1；k＝0，1，…，N－1），其傅里叶变换为

地球物理数据处理基础

1.二维复序列的FFT算法

对于M条测线，每条测线N个测点，构成复序列y_jk（j＝0，1，…，M－1；k＝0，1，…，N－1），根据离散傅里叶公式（8－41），其傅里叶变换为

地球物理数据处理基础

于是，可以分两步套用一维复FFT完成二维复FFT的计算。

（1）沿测线方向计算

对于j＝0，1，…，M－1逐测线套用一维复FFT，执行式（8－43）。定义复数组 则算法为

1）对于j＝0，1，…，M－1，作2）～7）；

2）将y_jk输入A₁（k），即A₁（k）＝y_jk（k＝0，1，…，N－1）；

3）计算W^r，存入W（r），即

4）q＝1，2，…，p（p＝log₂N），若q为偶数执行6），否则执行5）；

5）k＝0，1，2，…，（2^p－q－1）和n＝0，1，2，…，（2^q－1－1）循环，作

A₂（k2^q＋n）＝A₁（k2^q－1＋n）＋A₁（k2^q－1＋n＋2^p－1）

A₂（k2^q＋n＋2^q－1）＝［A₁（k2^q－1＋n）－A₁（k2^q－1＋n＋2^p－1）］·W（k2^q－1）

至k，n循环结束；

6）k＝0，1，2，…，（2^p－q－1）和n＝0，1，2，…，（2^q－1－1）循环，作

A₁（k2^q＋n）＝A₂（k2^q－1＋n）＋A₂（k2^q－1＋n＋2^p－1）

A₁（k2^q＋n＋2^q－1）＝［A₂（k2^q－1＋n）－A₂（k2^q－1＋n＋2^p－1）］·W（k2^q－1）

至k，n循环结束；

7）q循环结束，若p为偶数，将A₁（n）输入到Y_jn，否则将A₂（n）输入到Y_jn（n＝0，1，…，N－1）；

8）j循环结束，得到Y_jn（j＝0，1，…，M－1；n＝0，1，…，N－1）。

（2）垂直测线方向计算

对于n＝0，1，…，N－1逐一套用一维复FFT，执行式（8－44）。即

1）对于n＝0，1，…，N－1，作2）～7）；

2）将Y_jn输入A₁（j），即A₁（j）＝Y_jn（j＝0，1，…，M－1）；

3）计算W^r存入W（r），即

4）q＝1，2，…，p（p＝log₂M），若q为偶数执行6），否则执行5）；

5）j＝0，1，2，…，（2^p－q－1）和m＝0，1，2，…，（2^q－1－1）循环，作

A₂（j2^q＋m）＝A₁（j2^q－1＋m）＋A₁（j2^q－1＋m＋2^p－1）

A₂（j2^q＋m＋2^q－1）＝［A₁（j2^q－1＋m）－A₁（j2^q－1＋m＋2^p－1）］·W（j2^q－1）

至j，m循环结束；

6）j＝0，1，2，…，（2^p－q－1）和m＝0，1，2，…，（2^q－1－1）循环，作

A₁（j2^q＋m）＝A₂（j2^q－1＋m）＋A₂（j2^q－1＋m＋2^p－1）

A₁（j2^q＋m＋2^q－1）＝［A₂（j2^q－1＋m）－A₂（j2^q－1＋m＋2^p－1）］·W（j2^q－1）

至j，m循环结束；

7）q循环结束，若p为偶数，将A₁（m）输入到Y_mn，否则将A₂（m）输入到Y_mn（m＝0，1，…，M－1）；

8）n循环结束，得到二维复序列的傅氏变换Y_mn（m＝0，1，…，M－1；n＝0，1，…，N－1），

所求得的Y_mn是复数值，可以写为

Y_mn＝R_mn＋iI_mn （m＝0，1，…，M－1；n＝0，1，…，N－1）

其中，R_mn，I_mn的值也是已知的。

2.二维实序列的FFT算法

对于二维的实序列，我们把其看作是虚部为零的复序列，套用上述的二维复序列FFT方法来求其频谱算法上也是可行的，但势必会增加大量的无功运算。因此，有必要研究二维实序列FFT的实用算法，同一维实序列FFT的实现思路一样，同样把二维实序列按一定的规律构造成二维复序列，调用二维复序列FFT，然后通过分离和加工得到原实序列的频谱。

例如采样区域有2 M条测线，每条测线有N个点，并且M，N都是2的整数幂，需要计算实样本序列x_jk（j＝0，1，2，…，2 M－1；k＝0，1，2，…，N－1）的傅氏变换：

地球物理数据处理基础

类似于一维实序列FFT的思想，直接建立下面的二维实序列FFT算法：

（1）将一个二维实序列按偶、奇线号分为两个二维子实序列，分别作为实部和虚部组合为一个二维复序列。即令

地球物理数据处理基础

（2）调用二维复FFT过程，求出y_jk的二维傅氏变换Y_mn的复数值：

地球物理数据处理基础

式中：R_mn，I_mn是Y_mn的实部和虚部。

（3）利用R_mn，I_mn换算X_mn的值。

前两步容易实现，下面分析第（3）步的实现。

记h_jk，g_jk的傅氏变换为H_mn，G_mn。根据傅里叶变换的定义，我们导出X_mn与H_mn，G_mn的关系式：

地球物理数据处理基础

式中，H_mn，G_mn为复数，我们用上标r和i表示其实部和虚部，将上式右端实部、虚部分离

地球物理数据处理基础

其中：

地球物理数据处理基础

下面的任务是将H_mn，G_mn各分量与通过二维复FFT求出的R_mn，I_mn值联系起来。为此先给出奇、偶分解性质和类似于一维情况的三个二维傅氏变换性质：

（1）奇偶分解性

任何一个正负对称区间定义的函数，均可唯一地分解为如下偶（even）、奇（odd）函数之和：

地球物理数据处理基础

（2）周期性

地球物理数据处理基础

（3）复共轭性

地球物理数据处理基础

现在我们来建立R_mn，I_mn与H_mn，G_mn的关系。对Y_mn作奇偶分解：

地球物理数据处理基础

根据线性性质

地球物理数据处理基础

对照式（8－54）和式（8－55），得

地球物理数据处理基础

由于h_jk，g_jk是实函数，根据复共轭性质，上面两式对应的奇偶函数相等。即

地球物理数据处理基础

再由奇偶分解性和周期性，得

地球物理数据处理基础

将式（8－57）代入式（8－50），得

地球物理数据处理基础

再利用H_mn，G_mn周期性及复共轭性，可以得到m＝M/2＋1，…，M－1；n＝0，1，…，N－1的傅氏变换，即

地球物理数据处理基础

将式（8－50）中M，N改为M－m，N－n，并将上式代入，得

地球物理数据处理基础

由式（8－58）、式（8－59）和式（8－61）即可得到原始序列x_jk（j＝0，1，…，2M－1；n＝0，1，…，N－1）在m＝0，1，…，M－1；n＝0，1，…，N－1区间的傅氏变换X_mn。

具体二维实序列的FFT算法如下：

（1）令h_jk＝x_2j，k，g_jk＝x_2j＋1，k，形成

y_jk＝h_jk＋ig_jk （j＝0，1，…，2 M－1；n＝0，1，…，N－1）

（2）调用二维复序列FFT过程，即从两个方向先后调用一维复FFT算法式（8－43）和式（8－44），求得y_jk的二维傅氏变换Y_mn的复数值：

Y_mn＝R_mn＋iI_mn （m＝0，1，…，M－1；n＝0，1，…，N－1）

（3）用下列公式由R_mn，I_mn的值换算X_mn的值：

地球物理数据处理基础

地球物理数据处理基础

浜岀淮瀹炲簭鍒楃殑蹇熷倕閲屽彾鍙樻崲(FFT)
绛旓細鏍规嵁鍌呴噷鍙跺彉鎹鐨勫畾涔夛紝瀵逛簬杩炵画浜岀淮鍑芥暟f锛x锛寉锛夛紝鍏跺倕閲屽彾鍙樻崲瀵逛负 鍦扮悆鐗╃悊鏁版嵁澶勭悊鍩虹 瀵逛簬绂绘暎鐨浜岀淮搴忓垪fjk锛坖锛0锛1锛屸︼紝M锛1锛沰锛0锛1锛屸︼紝N锛1锛夛紝鍏跺倕閲屽彾鍙樻崲涓 鍦扮悆鐗╃悊鏁版嵁澶勭悊鍩虹 1.浜岀淮澶搴忓垪鐨FFT绠楁硶 瀵逛簬M鏉℃祴绾匡紝姣忔潯娴嬬嚎N涓祴鐐癸紝鏋勬垚澶嶅簭鍒梱jk锛坖锛0锛1锛屸︼紝...

蹇熷倕閲屽彾鍙樻崲(FFT)鍩烘湰鍘熺悊涓庡簲鐢ㄥ疄渚
绛旓細鍦ㄤ俊鍙峰鐞嗙殑棰嗗煙锛屽懆鏈熶俊鍙风殑绂绘暎鍒嗘瀽鏄叧閿殑涓鐜傜鏁ｅ倕閲屽彾绾ф暟锛圖FT锛夋槸鍏跺熀纭锛岃蹇熷倕閲屽彾鍙樻崲锛團FT锛夊垯鍑熷叾楂樻晥鎬ф垚涓哄垎鏋愮殑鍒╁櫒銆傝鎴戜滑浠庡畾涔夊嚭鍙戯紝閫愭鎻ず杩欎竴鐞嗚鐨勭簿楂撳拰瀹為檯搴旂敤銆傚畾涔夋柊瑙 绂绘暎鏃堕棿鍛ㄦ湡淇″彿锛屽叾澶嶆潅鎬ч氳繃铏氭寚鏁伴」宸у鍦板憟鐜般傚綋鎴戜滑灏嗚繛缁椂闂翠俊鍙烽噰鏍峰悗锛屼究寰楀埌涓...

鍌呴噷鍙跺彉鎹姹傚嚭Fn浜嗕互鍚,鎬庝箞姹傛尟骞厊Fn|鍜岀浉浣嵪?
绛旓細Fn鍙嶆槧浜嗘瀯鎴愪俊鍙风殑鍚勪釜鍒嗛噺鐨勫箙搴﹀拰鐩镐綅锛屾墍浠ヤ篃绉颁负棰戣氨锛岃窡杩欎釜绫讳技锛歽(t)=F1cos(t+蠄1)+F2cos(2t+蠄2)銆傚蹇熷倕閲屽彾鍙樻崲锛團FT锛夌畻娉曠殑鐮旂┒渚夸笉鏂繁鍏ワ紝鏁板瓧淇″彿澶勭悊杩欓棬鏂板叴瀛︾涔熼殢FFT鐨勫嚭鐜板拰鍙戝睍鑰岃繀閫熷彂灞曘傛牴鎹搴忓垪鍒嗚В涓庨夊彇鏂规硶鐨勪笉鍚岃屼骇鐢熶簡FFT鐨勫绉嶇畻娉曪紝鍩烘湰绠楁硶鏄熀2DIT鍜...

鍌呴噷鍙跺彉鎹涓璂FT鍜孖DFT鍒嗗埆浠涔堟剰鎬 鍌呴噷鍙跺彉鎹腑DFT鍜孖DFT鐨勬剰鎬
绛旓細1銆佺鏁鍌呴噷鍙跺彉鎹紙Discrete Fourier Transform锛岀缉鍐欎负DFT锛夛紝鏄倕閲屽彾鍙樻崲鍦ㄦ椂鍩熷拰棰戝煙涓婇兘鍛堢鏁ｇ殑褰㈠紡锛屽皢淇″彿鐨勬椂鍩熼噰鏍峰彉鎹负鍏禗TFT鐨勯鍩熼噰鏍枫傚湪褰㈠紡涓婏紝鍙樻崲涓ょ锛堟椂鍩熷拰棰戝煙涓婏級鐨搴忓垪鏄湁闄愰暱鐨勶紝鑰屽疄闄呬笂杩欎袱缁勫簭鍒楅兘搴斿綋琚涓烘槸绂绘暎鍛ㄦ湡淇″彿鐨勪富鍊煎簭鍒椼傚嵆浣垮鏈夐檺闀跨殑绂绘暎淇″彿浣淒FT锛屼篃搴...

FFT , DTFT, DFT 鐨勫尯鍒拰鑱旂郴?
绛旓細1銆佸惈涔変笉鍚岋細DTFT鏄鏁ｆ椂闂村倕閲屽彾鍙樻崲锛孌FT鏄鏁ｅ倕閲屽彾鍙樻崲锛孎FT鏄疍FT鐨勪竴绉嶉珮鏁堝揩閫熺畻娉曪紝涔熺О浣蹇熷倕閲屽彾鍙樻崲銆2銆佹ц川涓嶅悓锛欴TFT鍙樻崲鍚庣殑鍥惧舰涓殑棰戠巼鏄竴鑸繛缁殑锛坈os(wn)绛夎繖鏍风殑鐗规畩鍑芥暟闄ゅ锛屽叾鍙樻崲鍚庢槸鍐插嚮涓)锛岃孌FT鏄疍TFT鐨勭瓑闂撮殧鎶芥牱锛屾槸绂绘暎鐨勭偣銆傚揩閫熷倕閲屽彾鍙樻崲FFT鍏跺疄鏄竴绉嶅...

matlab涓璮ft()鍑芥暟鏄粈涔堟剰鎬?
绛旓細蹇熷倕閲屽彾鍙樻崲, 鍗冲埄鐢ㄨ绠楁満璁＄畻绂绘暎鍌呴噷鍙跺彉鎹紙DFT)鐨勯珮鏁堛佸揩閫熻绠楁柟娉曠殑缁熺О锛岀畝绉癋FT銆傚揩閫熷倕閲屽彾鍙樻崲鏄1965骞寸敱J.W.搴撳埄鍜孴.W.鍥惧熀鎻愬嚭鐨勩傞噰鐢ㄨ繖绉嶇畻娉曡兘浣胯绠楁満璁＄畻绂绘暎鍌呴噷鍙跺彉鎹㈡墍闇瑕佺殑涔樻硶娆℃暟澶т负鍑忓皯锛岀壒鍒槸琚彉鎹㈢殑鎶芥牱鐐规暟N瓒婂锛孎FT绠楁硶璁＄畻閲忕殑鑺傜渷灏辫秺鏄捐憲銆

涓缁瀹炲簭鍒楃殑蹇熷倕閲屽彾鍙樻崲(FFT)
绛旓細杩欏氨鏄瀹炲簭鍒楃殑鍌呴噷鍙跺彉鎹鍏锋湁澶嶅叡杞с傚叾鍚屾牱鍏锋湁鍛ㄦ湡鎬э紝鍗 鍦扮悆鐗╃悊鏁版嵁澶勭悊鍩虹 2.涓缁村疄搴忓垪鐨凢FT绠楁硶 锛1锛夊悓鏃惰绠椾袱涓疄搴忓垪鐨凢FT绠楁硶 宸茬煡涓や釜瀹炲簭鍒梙锛坘锛夛紝g锛坘锛夛紙k锛0锛1锛屸︼紝N锛1锛夛紝渚嬪閲嶇寮傚父骞抽潰鏁版嵁涓殑涓ゆ潯鍓栭潰锛屾垨鍦伴渿鍕樻帰涓殑涓ら亾鍦伴渿璁板綍锛屽彲浠ヤ汉涓哄湴鏋勬垚涓涓搴忓垪...

宸茬煡x(n)鏄2N鐐圭殑瀹炲簭鍒,姘旂鏁鍌呯珛鍙跺彉鎹涓篨(k)=DFT[(x(n)],2N鐐...
绛旓細fft(y(n),N)

蹇熷倕閲屽彾鍙樻崲:绠楁硶涓庡簲鐢ㄧ洰褰
绛旓細蹇熷倕閲屽彾鍙樻崲锛氱畻娉曚笌搴旂敤鐩綍 璇戣呭簭鍘熶功鍓嶈█鏈功缁撴瀯缂╃暐璇1绔犵畝浠1.1 绂绘暎鍌呴噷鍙跺彉鎹㈢殑搴旂敤绗2绔犵鏁ｅ倕閲屽彾鍙樻崲2.1 瀹氫箟2.1.1 DFT2.1.2 IDFT2.1.3 褰掍竴鍖朌FT2.2 Z鍙樻崲2.3 DFT鎬ц川2.4 鍗风Н瀹氱悊2.5 鐩稿叧鎬у畾鐞2.6 閲嶅彔鐩稿姞鍜屼繚鐣欐硶2.7 鏁版嵁鍩熺殑琛ラ浂2.8 瀹炲簭鍒DFT璁＄畻2.9...

杩欎釜matlab绋嬪簭鎬庝箞缂?(璁捐浣庨氭护娉㈠櫒)
绛旓細1.閫氳繃瀹為獙鍔犳繁瀵蹇熷倕绔嬪彾鍙樻崲(FFT)鍩烘湰鍘熺悊鐨勭悊瑙ｃ 2.浜嗚ВFFT鐐规暟涓庨璋卞垎杈ㄧ巼鐨勫叧绯,浠ュ強涓ょ鍔犻暱搴忓垪FFT涓庡師搴忓垪FFT鐨勫叧绯汇 2.2 瀹為獙浠櫒 1.YBLD鏅鸿兘缁煎悎淇″彿婧愭祴璇曚华 1鍙 2.鍙岃釜绀烘尝鍣 1鍙 3.MCOM-TG305鏁板瓧淇″彿澶勭悊涓庣幇浠ｉ氫俊鎶鏈疄楠岀 1鍙 4.PC鏈(瑁呮湁MATLAB銆丮COM-TG305閰嶅瀹為獙杞欢) 1鍙 ...

扩展阅读：傅立叶为什么是空想 ... 傅里叶变换结果唯一吗 ... 傅里叶公式大全 ... 二维傅立叶变换例子 ... 傅里叶变换全部公式 ... python创建二维空列表 ... 傅里叶变换视频 ... 传热傅里叶去世 ... 傅里叶级数收敛理解 ...