离散傅里叶变换

一、功能

计算复序列的离散傅里叶变换（DFT）和离散傅里叶反变换（IDFT）。

二、方法简介

序列\(x(n)(n=0,1,...,N-1)\)的离散傅里叶变换定义为
\[ X(k)=\sum_{n=0}^{N-1}x(n)e^{-j\frac{2\pi nk}{N}} \]
设\(x(n)=a(n)+jb(n),X(k)=A(k)+jB(k),Q=2\pi/N\)，则上式变为
\[ A(k)+jB(k)=\sum_{n=0}^{N-1}[a(n)+jb(n)][cos(Qnk)-jsin(Qnk)] \]
即
\[ \begin{matrix}A(k)=\sum_{n=0}^{N-1}[a(n)cos(Qnk)+b(n)sin(Qnk)]\\ B(k)=\sum_{n=0}^{N-1}[b(n)cos(Qnk)-a(n)sin(Qnk)]\end{matrix} \]
序列\(X(k)\)的离散傅里叶反变换定义为
\[ x(n)=\frac{1}{N}\sum_{k=0}^{N-1}X(k)W_{N}^{-nk}, \qquad n=0,1,...,N-1 \]
它与离散傅里叶正变换的区别在于将\(W_N\)改变为\(W_N^{-1}\)，并多了一个除以\(N\)的运算。计算公式如下
\[ \begin{matrix}a(n)=\frac{1}{N}\sum_{k=0}^{N-1}[A(k)cos(Qnk)-B(k)sin(Qnk)]\\ b(n)=\frac{1}{N}\sum_{k=0}^{N-1}[B(k)cos(Qnk)+A(k)sin(Qnk)]\end{matrix} \]

三、使用说明

是用C语言实现离散傅里叶变换（DFT）的方法如下：

/************************************
    x       ---一维数组，长度为n，存放要变换数据的实部。
    y       ---一维数组，长度为n，存放要变换数据的虚部。
    a       ---一维数组，长度为n，存放变换结果的虚部。
    b       ---一维数组，长度为n，存放变换结果的虚部。
    n       ---数据长度。
    sign    ---当sign=1时，子函数计算离散傅里叶正变换；当sign=-1时，子函数计算离散傅里叶反变换
************************************/
#include "math.h"

void dft(double *x, double *y, double *a, double *b, int n, int sign)
{
    int i;
    int k;
    double c;
    double d;
    double q;
    double w;
    double s;

    q = 6.28318530718 / n;
    for(k = 0; k < n; k++) {
        w = k * q;
        a[k] = 0.0;
        b[k] = 0.0;
        for(i = 0; i < n; i++) {
            d = i * w;
            c = cos(d);
            s = sin(d) * sign;
            a[k] += c * x[i] + s * y[i];
            b[k] += c * y[i] - s * x[i];
        }
    }
    if(sign == -1) {
        c = 1.0 / n;
        for(k = 0; k < n; k++) {
            a[k] = c * a[k];
            b[k] = c * b[k];
        }
    }
}

离散傅里叶变换

原文：https://www.cnblogs.com/liam-ji/p/11685568.html