文档介绍：实验题目：使用 Haar 小波和傅里叶变换方法滤波及数据压缩
实验目的
1）掌握离散数据的 Haar 小波变换和傅里叶变换的定义，基本原理和方法
2）使用 C++实现数据的 Haar 小波变换和离散傅里叶变换
空域上看起来很复杂的信号（比如
声音或图像）通常在频域上只集中在很小一块区域内，而很大一部分数值都接近于零。即一个在空
域中看起来占满全空间的信号，从频域中很可能只占用了极小一块区域，而大部分频率是被为零的。
这就得到一个极为实用的结论：一个看起来信息量很大的信号，其实可以只用极少的数据就可加以
描述。只要对它先做傅里叶变换，然后只记录那些不接近零的频域信息就可以达到数据压缩的目的。
（3）快速傅里叶变换 FFT 原理
FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合，从而减少运算量。
WNn, k
e j 2 nk / N
F (k )
1
令
N
，则 F(u)可改写为

N 1
f (n)WNn ,k
n 0 。令 N=2M ，其中 M 为一正整
数。带入式中，得到
Fe (k )
1 M
1
n ,k
1
M 1
f (2n
n ,k
M n
f (2 n)WM
Fo ( k)
1)WM
令
0
，
M
n 0
则有
F (k )
1 Fe (k) Fo (k )W2kM
F (k M )
1 Fe (k) Fo (k)W2kM
2
，
2
上述推导说明：对一个长度为
N 的序列进行傅里叶变换可以通过将其划分为
2 个 N/2 的序列
进行傅里叶变换，对于
N/2 的傅里叶变换，可划分为两个
N/4 的变换，这一过程不断迭代，知道两
点的序列为止，可计算出该序列的傅里叶变换。
（4）时间抽取的基 2FFT 蝶形算法
对于（ 3）中的计算方法，可以采用蝶形运算符号来表示。本实验中采用的算法是时间抽取的基 2FFT 算法实现快速傅里叶变换。
数据压缩的评价准则
（1）数据压缩比
设原始信号 f(n) 的数据量大小为 S，经过数据压缩后，信号的数据量变为 M ，一般情况下 M<S 。
则数据压缩比率

的定义为：
由上式可知，数据压缩得越小，其数据压缩比越大。
（2）数据失真度
对于压缩后的数据，可以采用反变换等方式还原信号。设原信号为 f(n) ，还原信号为 f1(n) ，则
我们定义还原信号与原始信号的差异为数据失真度。显然，数据恢复越接近原始信号，数据失真度
越小。
算法步骤
1）Haar 小波方法步骤
读入原始数据 f(n)
对原始数据 f(n) 进行小波变换。对原始数据进行不同层级（分辨率）下的