科技信息
高校理科研究
傅里叶级数在数字信号处理中的应用
中北大学信息与通信工程学院
姜世杰
余红英
［摘要］快速傅里叶变换是针对于将一个大点数Ｎ的ＤＦＴ分解成若干个小点的ＤＦＴ的组合的算法［１］，主要是巧妙的利用了Ｗｎ因
使运算量大大降低，节省了大量时间。快速傅里叶变换的算法已经作为一种强子的周期性和对称性，构造出的一种ＤＦＴ快速算法。
［２］
有力的工具运用到信号处理领域中，大大推动了数字信号处理技术的进步。本论文比较详细的阐述了快速傅里叶算法的数学原理、运算特点并完善的运用到Ｍａｔｌａｂ，实现先好的仿真处理。［关键词］离散傅里叶变换快速傅里叶变换Ｍａｔｌａｂ
１．引言
ＤＦＴ在数字信号处理中得到了广泛的应用，其把信号从时域转化到频域上加以分析其频率与相位的变化关系，因为信号不仅随时间变化，还与频率、相位等信息有关，这就需要进一步分析信号的频率结构，并在频率域中对信号进行描述。然而ＤＦＴ算法是以庞大的数学计算量作为代价。ＦＦＴ的发现，使计算量大大缩减。它的发现是数字信号处理发展史上的一个转折点，也可以说是一个里程碑的作用。
２．ＦＦＴ的算法推导
我们知道离散傅里叶变换对是如下形式：
Ｎ－１
Ｎ＋ｋＮｋ
ｋ
ＷＮ＝ＷＮ·ＷＮ＝－ＷＮ（１０）（１１）（１２）代入（６）中
ｋ
（１２）
ＤＦＴ：Ｘ（ｋ）＝Σｘ（ｎ）Ｗ
ｎ＝０
Ｎ－１
ｎｋＮ
ｋ＝０，１，…，Ｎ－１（１）
－ｎｋ
ＩＤＦＴ：ｘ（ｎ）＝１ΣＸ（ｋ）ＷＮｎ＝０，１，…，Ｎ－１（２）
ｎ＝０
ｍ为正整数，若不满足此关系我们可以相设序列ｘ（ｎ）的长度Ｎ＝２ｍ，
应的补零。
首先，我们将ｘ（ｎ）按照ｎ的奇、偶将其分成两个子列，即：ｘ１（ｒ）＝ｘ（２ｒ）
ｒ＝０，１，（３）…Ｎ－１
ｒ）＝ｘ（２ｒ＋１）ｘ２（所以（１）式可变为：
Σ
Ｎ－１
Ｘ（ｋ）＝ＤＦＴ［ｘ（ｎ）］＝Σｘ（ｎ）Ｗ
ｎ＝０
Ｎ－１
ｎｋＮ
Ｎ－１＝Σｘ（２ｒ）Ｗ
ｒ＝０
２ｒｋＮ
Ｎ－１
＋Σｘ（２ｒ＋１）Ｗ
ｒ＝０
（２ｒ＋１）ｋＮ
偶子列
＝Σｘ１（ｒ）（ＷＮ）＋Ｗ利用Ｗ
ｒ＝０
ｎｋＮ
２ｒｋ
ｋＮＮ－１奇子列
（４）
Σｘ（ｒ）（Ｗ
ｒ＝０
２
２ｒｋＮ
）
（１３）前半部分：Ｘ（ｋ）＝Ｘ１（ｋ）＋ＷＮＸ２（ｋ）ｋ＝０，１…Ｎ－１
ｋ
后半部分：ＸＮ＋ｋ）＝Ｘ１（（１４）ｋ）－ＷＮＸ２（ｋ）ｋ＝０，１…Ｎ－１
Ｎ
综上，我们只要求出－１上各个整数ｋ对应的Ｘ１（ｋ）、Ｘ２（ｋ）值，
即可求出整个区间的Ｘ（ｋ）值，显然这样可以大大节省计算时间。
３．Ｍａｔｌａｂ实现已知ｘ（ｎ）是两个正弦信号与白噪声的叠加，利用Ｍａｔｌａｂ对其进行频谱分析。
ｃｌｅａｒａｌｌ；
％产生两个正弦加白噪声；Ｎ＝２５６；ｆ１＝．１；ｆ２＝．２；ｆｓ＝１；ａ１＝５；ａ２＝３；ｗ＝２＊ｐｉ／ｆｓ；ｘ＝ａ１＊ｓｉｎ（ｗ＊ｆ１＊（０：Ｎ－１））＋ａ２＊ｓｉｎ（ｗ＊ｆ２＊（０：Ｎ－１））＋ｒａｎｄｎ（１，Ｎ）；％应用ＦＦＴ求频谱；ｓｕｂｐｌｏｔ（３，１，１）；ｐｌｏｔ（ｘ（１：Ｎ／４））；ｆ＝－０．５：１／Ｎ：０．５－１／Ｎ；Ｘ＝ｆｆｔ（ｘ）；ｙ＝ｉｆｆｔ（Ｘ）；ｓｕｂｐｌｏｔ（３，１，２）；ｐｌｏｔ（ｆ，ｆｆｔｓｈｉｆｔ（ａｂｓ（Ｘ）））；ｓｕｂｐｌｏｔ（３，１，３）；ｐｌｏｔ（ｒｅａｌ（ｘ（１：Ｎ／４）））；
≤≤
的周期性：
－ｊ∏
－ｊ∏由于ＷＮ＝ｅ
２
所以ＷＮ＝ｅ
Ｎ－１－ｊ∏２＝ｅ＝Ｗ
Ｎ－１Ｎ（５）
（５）式代入（４）式化简得：ｒ）ＷＸ（ｋ）＝Σｘ１（
ｒ＝０
Σ
ΣΣΣΣ１ΣΣΣΣΣΣΣ２Σ
ｋＮ＋Ｗ
ｋＮΣｘ（ｒ）Ｗ
ｒ＝０
２
ｒｋＮ＝Ｘ１（ｋ）＋ＷＮＸ２（ｋ）
ｋ
（６）
在此也不难看出：
Ｎ－１
Ｘ（ｋ）＝Σｘ１（ｒ）Ｗ
ｒ＝０
ＮｒｋＮｒｋＮＮ－１＝Σｘ（２ｒ）Ｗ
ｒ＝０
ＮｒｋＮｒｋＮ（７）（８）
Ｘ（ｋ）＝Σｘ２（ｒ）Ｗ
ｒ＝０
＝Σｘ（２ｒ＋１）Ｗ
ｒ＝０
即Ｘ１（ｋ）与Ｘ２（ｋ）分别为ｘ１（ｒ）与ｘ２（ｒ）的Ｎ／２点的ＤＦＴ，这些点按照（６）
式可合成一个Ｎ点的ＤＦＴ。但是ｘ１（ｒ）与ｘ２（ｒ）以及Ｘ１（ｋ）与Ｘ２（ｋ）的长度都
Ｎｋ＝０，１，…－１，而Ｘ（ｋ）的长度为Ｎ；因此要想得到完整是Ｎ／２，也就是ｒ、
的图像，我们就要再次用到Ｗ的周期性。
Ｗ则
Ｘ１（ｋ＋Ｎ）＝Σｘ１（ｒ）Ｗ
ｒ＝０
同理可得Ｘ２（ｋ＋Ｎ）＝Ｘ２（ｋ）
Ｎｒ（ｋ＋Ｎ）
ＮＮｒｋＮ＝Ｗ
ｒ（ｋ＋Ｎ）
Ｎ（９）
＝Σｘ１（ｒ）Ｗ
ｒ＝０
ｒｋＮ
＝Ｘ１（ｋ）（１０）
４．小结
本论文着重详细的介绍了ＦＦＴ的两种算法原理，并在Ｍａｔｌａｂ中得到了很好的实现，可以让我们对ＦＦＴ有个更加直观的理解。通过ＦＦＴ与ＤＦＴ的对比，我们看出，ＦＦＴ并不是一种不同于ＤＦＴ的变换形式，而
ｌａｂ给出的ＦＦＴ介绍实际是是为减少ＤＦＴ计算量的一种快速算法。ｍａｔ
ＤＦＴ的表达式，未作ＤＦＴ向ＦＦＴ的简化过程说明，但计算过程内核是
加之超大规模集成电路（ＶＬＳＩ）和计算机的飞ＦＦＴ。以ＦＦＴ算法为契机，
速发展，使得数字信号处理的理论获得了飞速发展，并广泛的应用到各个领域。
参考文献［１］胡广书．数字信号处理－理论算法与实现（第二版）．清华大学出版社，２００３
［２］余成波，杨菁，杨如民，周登义．数字信号处理及ＭＡＴＬＡＢ实现．清华大学出版社，２００５
［３］谭子尤，张雅彬．离散傅里叶变换快速算法的研究与ＭＡＴＬＡＢ算法实现．中国科技信息，２００６／２２
（１１）
由（１０）（１１）两式看出，当Ｎ≤ｋ≤Ｎ－１时，所对应的Ｘ１（ｋ）、Ｘ２（ｋ）与
２
前半部分ｋ值（０≤k ≤Ｎ-1）所对应的完全相同。而
２
科技信息
高校理科研究
傅里叶级数在数字信号处理中的应用
中北大学信息与通信工程学院
姜世杰
余红英
［摘要］快速傅里叶变换是针对于将一个大点数Ｎ的ＤＦＴ分解成若干个小点的ＤＦＴ的组合的算法［１］，主要是巧妙的利用了Ｗｎ因
使运算量大大降低，节省了大量时间。快速傅里叶变换的算法已经作为一种强子的周期性和对称性，构造出的一种ＤＦＴ快速算法。
［２］
有力的工具运用到信号处理领域中，大大推动了数字信号处理技术的进步。本论文比较详细的阐述了快速傅里叶算法的数学原理、运算特点并完善的运用到Ｍａｔｌａｂ，实现先好的仿真处理。［关键词］离散傅里叶变换快速傅里叶变换Ｍａｔｌａｂ
１．引言
ＤＦＴ在数字信号处理中得到了广泛的应用，其把信号从时域转化到频域上加以分析其频率与相位的变化关系，因为信号不仅随时间变化，还与频率、相位等信息有关，这就需要进一步分析信号的频率结构，并在频率域中对信号进行描述。然而ＤＦＴ算法是以庞大的数学计算量作为代价。ＦＦＴ的发现，使计算量大大缩减。它的发现是数字信号处理发展史上的一个转折点，也可以说是一个里程碑的作用。
２．ＦＦＴ的算法推导
我们知道离散傅里叶变换对是如下形式：
Ｎ－１
Ｎ＋ｋＮｋ
ｋ
ＷＮ＝ＷＮ·ＷＮ＝－ＷＮ（１０）（１１）（１２）代入（６）中
ｋ
（１２）
ＤＦＴ：Ｘ（ｋ）＝Σｘ（ｎ）Ｗ
ｎ＝０
Ｎ－１
ｎｋＮ
ｋ＝０，１，…，Ｎ－１（１）
－ｎｋ
ＩＤＦＴ：ｘ（ｎ）＝１ΣＸ（ｋ）ＷＮｎ＝０，１，…，Ｎ－１（２）
ｎ＝０
ｍ为正整数，若不满足此关系我们可以相设序列ｘ（ｎ）的长度Ｎ＝２ｍ，
应的补零。
首先，我们将ｘ（ｎ）按照ｎ的奇、偶将其分成两个子列，即：ｘ１（ｒ）＝ｘ（２ｒ）
ｒ＝０，１，（３）…Ｎ－１
ｒ）＝ｘ（２ｒ＋１）ｘ２（所以（１）式可变为：
Σ
Ｎ－１
Ｘ（ｋ）＝ＤＦＴ［ｘ（ｎ）］＝Σｘ（ｎ）Ｗ
ｎ＝０
Ｎ－１
ｎｋＮ
Ｎ－１＝Σｘ（２ｒ）Ｗ
ｒ＝０
２ｒｋＮ
Ｎ－１
＋Σｘ（２ｒ＋１）Ｗ
ｒ＝０
（２ｒ＋１）ｋＮ
偶子列
＝Σｘ１（ｒ）（ＷＮ）＋Ｗ利用Ｗ
ｒ＝０
ｎｋＮ
２ｒｋ
ｋＮＮ－１奇子列
（４）
Σｘ（ｒ）（Ｗ
ｒ＝０
２
２ｒｋＮ
）
（１３）前半部分：Ｘ（ｋ）＝Ｘ１（ｋ）＋ＷＮＸ２（ｋ）ｋ＝０，１…Ｎ－１
ｋ
后半部分：ＸＮ＋ｋ）＝Ｘ１（（１４）ｋ）－ＷＮＸ２（ｋ）ｋ＝０，１…Ｎ－１
Ｎ
综上，我们只要求出－１上各个整数ｋ对应的Ｘ１（ｋ）、Ｘ２（ｋ）值，
即可求出整个区间的Ｘ（ｋ）值，显然这样可以大大节省计算时间。
３．Ｍａｔｌａｂ实现已知ｘ（ｎ）是两个正弦信号与白噪声的叠加，利用Ｍａｔｌａｂ对其进行频谱分析。
ｃｌｅａｒａｌｌ；
％产生两个正弦加白噪声；Ｎ＝２５６；ｆ１＝．１；ｆ２＝．２；ｆｓ＝１；ａ１＝５；ａ２＝３；ｗ＝２＊ｐｉ／ｆｓ；ｘ＝ａ１＊ｓｉｎ（ｗ＊ｆ１＊（０：Ｎ－１））＋ａ２＊ｓｉｎ（ｗ＊ｆ２＊（０：Ｎ－１））＋ｒａｎｄｎ（１，Ｎ）；％应用ＦＦＴ求频谱；ｓｕｂｐｌｏｔ（３，１，１）；ｐｌｏｔ（ｘ（１：Ｎ／４））；ｆ＝－０．５：１／Ｎ：０．５－１／Ｎ；Ｘ＝ｆｆｔ（ｘ）；ｙ＝ｉｆｆｔ（Ｘ）；ｓｕｂｐｌｏｔ（３，１，２）；ｐｌｏｔ（ｆ，ｆｆｔｓｈｉｆｔ（ａｂｓ（Ｘ）））；ｓｕｂｐｌｏｔ（３，１，３）；ｐｌｏｔ（ｒｅａｌ（ｘ（１：Ｎ／４）））；
≤≤
的周期性：
－ｊ∏
－ｊ∏由于ＷＮ＝ｅ
２
所以ＷＮ＝ｅ
Ｎ－１－ｊ∏２＝ｅ＝Ｗ
Ｎ－１Ｎ（５）
（５）式代入（４）式化简得：ｒ）ＷＸ（ｋ）＝Σｘ１（
ｒ＝０
Σ
ΣΣΣΣ１ΣΣΣΣΣΣΣ２Σ
ｋＮ＋Ｗ
ｋＮΣｘ（ｒ）Ｗ
ｒ＝０
２
ｒｋＮ＝Ｘ１（ｋ）＋ＷＮＸ２（ｋ）
ｋ
（６）
在此也不难看出：
Ｎ－１
Ｘ（ｋ）＝Σｘ１（ｒ）Ｗ
ｒ＝０
ＮｒｋＮｒｋＮＮ－１＝Σｘ（２ｒ）Ｗ
ｒ＝０
ＮｒｋＮｒｋＮ（７）（８）
Ｘ（ｋ）＝Σｘ２（ｒ）Ｗ
ｒ＝０
＝Σｘ（２ｒ＋１）Ｗ
ｒ＝０
即Ｘ１（ｋ）与Ｘ２（ｋ）分别为ｘ１（ｒ）与ｘ２（ｒ）的Ｎ／２点的ＤＦＴ，这些点按照（６）
式可合成一个Ｎ点的ＤＦＴ。但是ｘ１（ｒ）与ｘ２（ｒ）以及Ｘ１（ｋ）与Ｘ２（ｋ）的长度都
Ｎｋ＝０，１，…－１，而Ｘ（ｋ）的长度为Ｎ；因此要想得到完整是Ｎ／２，也就是ｒ、
的图像，我们就要再次用到Ｗ的周期性。
Ｗ则
Ｘ１（ｋ＋Ｎ）＝Σｘ１（ｒ）Ｗ
ｒ＝０
同理可得Ｘ２（ｋ＋Ｎ）＝Ｘ２（ｋ）
Ｎｒ（ｋ＋Ｎ）
ＮＮｒｋＮ＝Ｗ
ｒ（ｋ＋Ｎ）
Ｎ（９）
＝Σｘ１（ｒ）Ｗ
ｒ＝０
ｒｋＮ
＝Ｘ１（ｋ）（１０）
４．小结
本论文着重详细的介绍了ＦＦＴ的两种算法原理，并在Ｍａｔｌａｂ中得到了很好的实现，可以让我们对ＦＦＴ有个更加直观的理解。通过ＦＦＴ与ＤＦＴ的对比，我们看出，ＦＦＴ并不是一种不同于ＤＦＴ的变换形式，而
ｌａｂ给出的ＦＦＴ介绍实际是是为减少ＤＦＴ计算量的一种快速算法。ｍａｔ
ＤＦＴ的表达式，未作ＤＦＴ向ＦＦＴ的简化过程说明，但计算过程内核是
加之超大规模集成电路（ＶＬＳＩ）和计算机的飞ＦＦＴ。以ＦＦＴ算法为契机，
速发展，使得数字信号处理的理论获得了飞速发展，并广泛的应用到各个领域。
参考文献［１］胡广书．数字信号处理－理论算法与实现（第二版）．清华大学出版社，２００３
［２］余成波，杨菁，杨如民，周登义．数字信号处理及ＭＡＴＬＡＢ实现．清华大学出版社，２００５
［３］谭子尤，张雅彬．离散傅里叶变换快速算法的研究与ＭＡＴＬＡＢ算法实现．中国科技信息，２００６／２２
（１１）
由（１０）（１１）两式看出，当Ｎ≤ｋ≤Ｎ－１时，所对应的Ｘ１（ｋ）、Ｘ２（ｋ）与
２
前半部分ｋ值（０≤k ≤Ｎ-1）所对应的完全相同。而
２