大点数FFT的工程案例_许可.pdf

第 45 卷第 3 期2023 年 6 月电气电子教学学报Journal of Electrical and Electronic EducationVol 45No 3Jun 2023收稿日期:2022-05-11;修回日期:2022-09-23基金项目:国防科技大学本科教改重点课题(U2020102);湖南省普通高等学校教改项目(HNJG 2021 0270，HNJG 2021 0283)第一作者:许可(1982)，男，博士，副教授，主要从事信号处理的教学和科研工作，E-mail:xuke nudt edu cn大点数 FFT 的工程案例许可辛勤李双勋万建伟(国防科技大学 电子科学学院，长沙 410073)摘要:快速傅里叶变换(FFT)是“数字信号处理”课程中的重要知识点，该算法工程应用非常广泛。但 FFT 算法的推导过程比较复杂，学生不太容易深刻领会并灵活运用。以某型多频连续波雷达的数据处理为例，介绍如何利用 16K 缓存的芯片来实现 128K 点的 FFT 运算，通过实际工程案例来加深学生对 FFT 算法的理解，提高学生解决工程问题的能力。关键词:快速傅里叶变换(FFT);大点数;工程实现中图分类号:TN911 7文献标识码:A文章编号:1008-0686(2023)03-0150-03Engineering Case for Large Points FFTXU KeXIN QinLI ShuangxunWAN Jianwei(College of Electronic Science，National University of Defense Technology，Changsha 410073，China)Abstract:Fast Fourier transform algorithm，which is widely used in the engineering implementations，is important in the DigitalSignal Processing course However，due to the complicated derivation of this algorithm，students cannot deeply understand orflexibly use the FFT algorithm An engineering case based on the data processing for the multi-frequency continuous wave radar ispresented in this paper It describes how to calculate 128K points FFT with a 16K processor With this practical engineering case，the FFT algorithm is well understood by the students，and the ability of their engineering is greatly improvedKeywords:fast Fourier transform(FFT);large points;engineering implementation快速傅里叶变换(FFT，Fast Fourier Trans-form)算法自从 1965 年被提出以来1 2，在雷达探测、卫星导航、地质勘探、通信等领域取得了广泛且深入的应用，FFT 算法及其应用已成为“数字信号处理”课程中的重要知识点。FFT 算法的推导过程比较复杂，再加上在DSP、Matlab 等平台上有成熟且强大的软件支撑，学生在学习过程中容易出现“知其然不知其所以然”的局面，即只会把 FFT 算法当作工具来使用，而不会灵活运用 FFT 算法来解决工程实践问题。为此，我们基于连续波雷达数据处理设计了一个教学案例，给学生讲解如何利用小点数的 DSP 芯片实现大点数的 FFT 运算3。1教学案例设计1 1工程背景研发某型多频连续波测距雷达，根据设计要求测量距离需达到 100 km 以上，此时接收数据的信噪比很低，为提高对目标的检测能力，就需要进行大点数的 FFT 运算来积累能量。根据理论测算和工程经验，这个“大点数”就是128K(大写 K=1024)3。在 20 多年前，TI 系列 DSP 芯片最大缓存仅支持16K 点数据，如何利用 16K 的 DSP 来实现 128K点的 FFT 运算，就成为了该项目的一个工程难题。如何实现 128K 点的 FFT 运算，其实对应于“N 为复合数的 FFT 运算”这个知识点1 2。在讲授过程中，我们并不直接从理论推导入手，而是以这个工程背景为铺垫，对 N=128K 这个具体情况进行分析，学生就很容易理解这个知识点的来龙去脉和用法。1 2基本原理设参与 FFT 运算的序列 x(n)长度为 N=N1N2，输出的频域样本值为 X(k)，其中 n，k=0，1，N 1。可以把变量 n 和 k 改写为如下形式(1)(2)此时，FFT 运算输出序列可表示为1 2(3)公式(3)意味着为计算 N=N1 N2点的 FFT，可将数据分块，先做 N2个 N1点长的 FFT，将中间结果乘以旋转因子后，再做 N1个 N2点长的 FFT。1 3实现方案在本文的工程背景下，N1=16K，N2=8，意味着为完成128K 点的FFT 运算，可以先进行16K 点的FFT，乘以旋转因子后再做8 点的 FFT，如图1 所示。第1 步，把128K 点长的数据 x(n)以8 为间隔进行抽取，分为 8 组数据，每组数据长度为 16K，对应表 1 中的每一行。第 2 步，把每组(行)数据做 N1=16K 点的FFT 变换，得到如下结果X(n2，k1)=N11n1=0 x(N2n1+n2)Wk1n1N1(4)对于每组(行)数据而言，n2是一个常数，因此X(n2，k1)为16K 点的数据。当 n2从0 到7 循环一遍，就会生成 8 组(行)16K 点长的中间结果。第 3 步，把 N1点的 FFT 结果乘以旋转因子Wk1n2N，得到如下结果X(n2，k1)=X(n2，k1)Wk1n2N=N11n1=0 x(N2n1+n2)Wk1n1N Wk1n2N(5)第 4 步，做 N2点的 FFT 变换，得到 8 点长的输出结果，对应表 2 中的一列，即X(k)=X(k1+N1k2)=N21n2=0X(n2，k1)Wk2n2N2(6)2注意事项图 1 给出的仅仅是实现 128K 点 FFT 的示意图，但在具体工程实现过程中，还有以下几个需要注意的地方。(1)从表 1 和表 2 的特点可以看出，整个运算过程始终只需要一个 N2 N1的矩阵，因此这个过程仍然具备同址运算的特点1 2。(2)图1 中有8 个16K 的 DSP 并行运算，但实际只需要一个 16K 的 DSP 即可，也就是让 1 个16K 的 DSP 完成 8 轮 FFT 运算。流水处理的另外一个优势在于硬件实现上，既减少了 DSP 的数量，同时还避免了多个 DSP 数据同步的困难。(3)DSP 读取片内缓存的速度远快于读取片外缓存，如果在第4 步中一次只做8 点的 FFT，就会频图 1实现 128K 点 FFT 示意图151第 3 期许可，等:大点数 FFT 的工程案例1表 1以 8 为间隔对 128K 的数据进行抽取n1n201n1N110 x(0)x(8)x(8n1)x(8N18)1x(1)x(9)x(8n1+1)x(8N17)2x(2)x(10)x(8n1+2)x(8N16)3x(3)x(11)x(8n1+3)x(8N15)4x(4)x(12)x(8n1+4)x(8N14)5x(5)x(13)x(8n1+5)x(8N13)6x(6)x(14)x(8n1+6)x(8N12)7x(7)x(15)x(8n1+7)x(8N11)表 2输出结果k1k201k1N110X(0)X(1)X(k1)X(N11)1X(N1)X(N1+1)X(N1+k1)X(2N11)2X(2N1)X(2N1+1)X(2N1+k1)X(3N11)3X(3N1)X(3N1+1)X(3N1+k1)X(4N11)4X(4N1)X(4N1+1)X(4N1+k1)X(5N11)5X(5N1)X(5N1+1)X(5N1+k1)X(6N11)6X(6N1)X(6N1+1)X(6N1+k1)X(7N11)7X(7N1)X(7N1+1)X(7N1+k1)X(8N11)繁地读取片外缓存，因此最合理的做法就是在片内缓存区尽可能地多存储数据。DSP 片内缓存支持16K 点数据，所以在第 4 步中实际上是同时进行2K 次 8 点长的 FFT 运算。对于大点数 FFT 算法的实现及改进，我们还鼓励学有余力的学生查阅相关文献 4 7。3结语“从工程实践中来，回到工程实践中去”，是我们在“数字信号处理”课程教学中一直坚持的教学理念1。本文介绍了小点数(16K)DSP 实现大点数(128K)FFT 运算的教学案例。我们以 N=128K这个具体值为例，并结合雷达数据处理需求来进行讲解，学生就很容易理解“为什么要学”，即实现大点数 FFT 运算的前因后果，也很容易在今后的工程实践中举一反三，灵活处理更大点数的 FFT 运算需求。参考文献 1 许可，万建伟 数字信号处理 M 北京:清华大学出版社，2020 2 李素芝，万建伟 时域离散信号处理 M 长沙:国防科技大学出版社，1994 3 许可，王玲，万建伟 信号处理仿真实验M 2 版北京:清华大学出版社，2020 4 张博 基于大点数 FFT 运算器的雷达信号高速处理 D 成都:电子科技大学，2012 5 苏涛，庄德靖 大点数 FFT 算法的改进及其实现 J 现代雷达，2005，27(7):23 26 6 郭骁，张月，陈曾平，等 超长点数 FFT 的设计与实现技术 J 信号处理，2013，29(11):1488 1494 7 夏际金，梁之勇，崔留争 多核并行的大点数 FFT、IF-FT 设计 J 火控雷达技术，2016，45(1):64 68251电气电子教学学报第 45 卷