对于离散傅里叶变换的一些记录

DFT即Discrete Fourier Transformation离散傅里叶变换，适用于对采样性质的信号样本进行傅里叶变换。因为本人目前还没有系统地学习《信号与系统》这门课，对于傅里叶变换的原理不了解，因而会从感性的角度写下自己对于DFT的一些理解。

不论学不学《信号与系统》这门课，三角函数总是学过的。

接下来我们需要知道这么一个事实：有相当大一部分的信号，是可以通过一系列数学运算，使用一组周期不同的三角函数表示的。

信号需要满足狄氏条件。抛开这个复杂的条件，我们粗略地认为常见的声波（甚至电磁波，Asteroids@home曾今发布过DFT计算任务）都是符合条件的，因为至少目前我还没见过不符合条件的。这说明DFT具有一定的使用空间，进而具有研究意义，后续发明的、被誉为20世纪重要发明之一的FFT算法甚至被某些OI大佬拿去AK。

由于DFT通常是给计算设备使用的，所以给定了输入长度有限的条件，下文假设有一个长度为N+1的信号序列x[n]，均匀采样，总时长为T。

设长度为N+1是为了能够方便地将每个采样点书写为x[0]，x[1]，...，x[N]。那么对于这个信号序列进行离散傅里叶变换，可以得到一个长度也为N+1的输出F[n]。

这里使用傅里叶最原始的想法来表示信号在时域/频域的转换：

s_N[t] = \sum_{n=0}^{N} k\text{sin} (n\omega t + \theta)

而上述提到的，对信号x[n]进行离散傅里叶变换后得到的F[n]，对应的是上式中的k、\theta，\omega则是通过采样频率\frac{N+1}{T}得到。

在进行实际计算后，可能会有一些发现：

1. F[N]给出的是一个复数序列，即使输入是实数序列；
2. 在x[n]是实数序列的时候，F[1]...F[N]是中心对称的，且对称的元素共轭（即a+bi和a-bi）.

(1)是因为多出来的虚部和实部一起，共同记录了\theta中的信息，在实际还原成时域信号的过程中，虚部会在运算中消除的（(2)从侧面印证了这一点）。

然后转到FFTW库的实现： http://www.fftw.org/doc/Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data

这里就提到，如果输入是实数的话，就会涉及到输出结果类型会变化的问题（从float到fftw_complex，实际上就是float[2]）。

这里就正好与上述的两个发现对应，因为输出数据类型改变，因而需要重新规划空间；又因为数据存在冗余性，可以通过删除冗余数据的方式节省内存空间。

那么文档里的算术就可以理解了：F[n]一共需要保存的复数元素个数至少为\lceil \frac{(N+1)-1}{2} \rceil + 1个。当元素个数为奇数（(n+1)%2==1）的时候，这个数是\frac{N}{2}+1，对应N+2个存储单元；偶数（(n+1)%2==0）的情况下，这个数是\lceil \frac{N}{2} \rceil + 1，对应N+3个存储单元。由于原始的输入规模是N+1，因而在该规模为奇数或偶数的时候分别需要补充1或2个单位的数据规模，与文档中的叙述相符合。