垒！Ｉ兰竺皇翌！竺基于ＤＳＰ的ＦＦＴ算法实现ＲｅａｌｉｚａｔｉｏｎｏｆＦＦＴａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＤＳＰ艾红，常青青，邓大伟ＡＩＨｏｎｇ，ＣＨＡＮＧＱｉｎｇ—ｑｉｎｇ。ＤＥＮＧＤａ．ｗｅｊ（北京信息科技大学自动化学院，北京１００１９２）摘要：快速傅立叶变换（ＦＦＴ）是将信号从时域变换到频域的一种方法，广泛运用于各种信号分析领域。文中介绍了ＦＦＴ算法的原理，构建了基于ＴＭＳ３２０Ｆ２８１２的硬件平台，阐述了ＦＦＴ算法的硬件与软件实现。利用ＴＭＳ３２０Ｆ２８１２内部的ＡＤＣ模块与事件管理器的定时器实现信号的实时采集，不需要使用专门的Ａ／Ｄ转换芯片。软件上以１２８点ＦＦＴ运算为例，在ＣＯＳ环境下利用Ｃ语言编程实现了ＦＦＴ算法，程序充分利用蝶式权的周期性及ＦＦＴ运算中第一级蝶式权值固定为１的特点。使得运算量与复杂度大大减小。运行结果表明ＴＭＳ３２０Ｆ２８１２能够快速高效地完成ＦＦＴ运算。关键词：数字信号处理ｌ快速傅立叶变换；信号采集中圈分类号：ＴＰ２７３文献标识码：Ｂ文章编号：１００９－０１３４（ｔｏｉ２）Ｏｌ（Ｉ－－）－００１７－０３Ｄｏｉ：１０．３９６９／Ｊ．Ｉｓｓｎ．１００９－０１３４．２０１２．０１（上）．０７０引言结果进行相应的数据显示和数据存储。快速傅立叶变换（Ｒ叮）在雷达、通信、电子对抗和电力系统等领域有广泛应用，特别是在电力系统的谐波检测中，Ｈ可几乎是唯一可行的检测方法。通常提高ＦＦＩ＂运算速度有两种途径：改进ＦＦＴ算法本身和改进运算工具。现阶段提高ＦＦＴ算法本身非常困难，一般方法致力于改进运算工具。数字信号处理器ＤＳＰ是一种可编程的高性能处理器。文中充分利用１ＭＳ３２０Ｆ２８１２ＤＳＰ强大的数据处理能力，实现了ＦＦＴ运算，并提高了运算速度。１系统硬件结构图１系统的硬件整体结构图系统设计以ＴＭＳ３２０Ｆ２８１２处理器为核心，辅２ＦＦＴ算法原理以外围电路构成。ＤＳＰ负责模拟输入信号数据采集ＦＦＴ是离散傅立叶变换（Ｄ兀’）的快速运算，以及ＦＦＴ算法实现。外围电路包括电源转换电路，是数字信号处理的基础。因为有些信号在时域很时钟电路，复位电路以及外部ＲＡＭ等。系统的硬难看出特性，使用ＦＦｒ将其变换到频域，就会很容件整体结构如图ｌ所示¨】。对信号进行ＦＦＴ变换，易看出其特性。ＤＦＴ算法的基本公式为ｐＪ：首先要对模拟信号采样将其转换为数字信号。输．ｒ（七）＝＞’Ｊ（ｎ）≯ｆ锣，七＝０，．，．１．．，ＪⅣ一１．Ｎ．．一－Ｉ入的连续模拟信号经信号调理电路后输出到ＤＳＰ的ｎ＝ＯＡＤＣ模拟输入通道，经过ＡＤＣ数据采集，模数转式中ｘ（ｎ）表示时域信号，ｘ（ｋ）表示频域信号，换的结果存放于ＡＤＣ结果寄存器中。信号调理电咐为运算蝶式权。路主要是为了信号的抗混叠滤波以及电路阻抗的Ｈ叩算法是不断地把长序列的ＤＦＴ分解成几个匹配。信号调理电路对输入信号进行调理处理，短序列的ＤＦＴ，并利用时的周期性和对称性减少包括信号的滤波、跟随输出以及信号的稳定。ＤＳＰＤＦＴ的运算次数。设序列ｘ（ｎ）的长度为Ｎ（Ｎ＝２Ｍ，Ｍ对采集的数字信号进行ＦＦＴ运算处理，同时对运算为任意正整数），按ｎ的奇偶把ｘ（ｎ）分解成两个Ｎ／２啦１日ＩＩＩ：２０１１－０８－１２薹金焉目：北京市教育委员会科技计划面上项目（ＫＭ２００９１０７７２００８）作者简介：艾红（１９６２一），女，四川重庆人，副教授，硕士，研究方向为检测技术与自动化装置。第３４卷第１期２０１２—０１（１－）１１７１万方数据点的子序列：Ｘｌ（，）＝可２厂），，＝０，１，．，Ｎ１２－１＊ｘ２（ｒ）＝ｘ（２ｒ＋Ｉ），，．＝Ｏ，ｌ，…，Ｎ／２—１ｘＲｒ）＝ＤＦＴ［工ｌ（ｒ）】ｏｓ，．ｓ生一ｌ２则：ｘ２（ｒ）＝ＤＦＴ［ｘ２（ｒ）］ｘ（ｒ）＝ｘｌ（，．）＋Ｘｌ（，．）瞄Ⅳｘ（，．＋第：ｚｌ（，）一ｘｌ（，．）略㈣ｓ号一１由此可见，若将任何一偶数点序列按下标的奇偶性分成两个子序列，则原序列的ＤＦＴ可由两子序列的ＤＦＴ线性组合得到。运算流图如图２所示。ＡＢ图２运算流图《０Ｘ（０）《４Ｘ（１）“２Ｘ（２）】西６Ｘ（３）《ｌＸ（４）虹５Ｘ（５）《３Ｘ（６）《７Ｘ（７）图３螺式运算流图其中，Ａ和Ｂ的距离称为翅尖距。这种方法和直接进行ＤＦＴ计算相比较，运算量减少一半。按照这种分解运算的思想，将Ｘ。（ｋ）和Ｘ：（ｋ）继续向下分解，直到最后变为一点序列，此时的运算量大大减小。以８点序列Ｘ（ｎ）的ＦＦＴ运算为例：第一次分解：曼｛；：：ｊ篙器搿端ｘ２‘ｎＪ＝｛强ｌＪ，ⅪｊＪ，强）Ｊ，砥，Ｊｊｘ３（ｎ）＝｛玛（０），殉（２）｝＝｛鳆Ｏ），鳆４）｝第二次分解：’‘ｍ＝｛玛‘１’＇再‘３’｝＝｛铽２’＇缸６’｝璃（ｎ）＝｛Ｘ２（ｏ），ｘ２（２）｝＝｛《１）。西５）｝砭（ｎ）＝｛Ｘ２（１），ｘ２（３）｝＝｛《３），《７）｝蝶式运算流图如图３所示。比较ＦＦＴ和ＤＦＴ的运算量。假设序列点数为Ｎ，且有Ｎ－＿２Ｌ，当使用ＦＦＴ进行运算时，计算过程中只有蝶式运算，它的复数乘法运算量为４＝Ｎｘｋ２Ｎ，复数加法运算量为Ｍｃ＝（Ｎ１２）ｘ崦２Ｎ；直接进行ＤＦＴ运算时，复数乘１１８１第３４卷第１期２０１２－０１（Ｉ－）万方数据法和复数加法的运算量均为Ｎ２。由此可见，ＦＦＴ运算确实大大减小了ＤＦＴ的运算量。由图３可以看出，若想得到顺序正确的频域序列Ｘ（ｋ），必须对时域序列进行重新排序。这里先说明比特逆序的概念：设存储地址ｍ，其二进制数（设ｍ＝２Ｌ）为ｍ＝（ｍｌｍ２ｍ３），若有ｆｎ＝（ｍ３ｉｎ２ｍ１），则称Ｉｉｌ为ｍ的Ｌ位比特逆序列。若将图４中的输入时域序列下标转换成二进制，依次是：０００，１００，０１０，１１０，００１，１０１，０１ｌ，１１ｌ：而原时域序列下标转换成二进制依次是：０００，００１，０１０，０１ｌ，１００，１０１，１１０，ｌｌｌ，将两者对比可发现，输入时域序列下标就是原时域序列下标的比特逆序。所以ＦＦＴ蝶式运算的第一步就是对时域序列进行比特排序。３系统软件实现以及结果分析３．１ＦＦＴ程序实现ＦＦＴ算法主要包括比特逆序、蝶式权值的计算、各级的蝶式运算以及ＦＦＴ序列的输出。程序中涉及到复数的运算，由于计算机无法处理复数，故而将复数拆为实部和虚部，只需计算出实部和虚部的数值即可。程序设计将蝶式权ｗ【ｉ】拆分为实部ｐｒ［ｉ］和虚部ｐｉ［ｉ］，将参与各级蝶式运算的序列拆分为实部ｆｒ和虚部ｆｉ。复数进行加法运算时需将两复数的实部与实部、虚部与虚部对应相加即可，例如ｗ【ｉ】＋ｗ【ｉ＋ｌ】，所得的和的实部为ｐｒ［ｉ］＋ｐｒ［ｉ＋１］，虚部为ｐｉ［ｉ］＋ｐｉ［ｉ＋ｌ】：而复数的乘法，相对来说有些复杂，不再是简单的虚部和实部各自相乘，例如ｗ［ｉ】×Ｗ，所得的乘积的实部为ｐｒ［ｉ】Ｘｐｒ＋ｐｉ［ｉ】Ｘｐｉ，虚部为：（ｐｒ［ｉｌ＋ｐｉ【ｉ】）×（ｐｒ＋ｐｉ）一（ｐｒ［ｉ］×ｐｒ＋ｐｉ［ｉ】×ｐｉ）。该程序执行的是１２８个点的ＦＩ丌运算，共有７级蝶式运算，每个蝶式权Ｗ号Ｒ都可看作是Ｗ％Ｒ的ｎ次方，所以在一个循环内即可计算出所有的蝶式权。每级蝶式运算计算出新的序列值代替该级的输入序列值，这样避免了开辟新的存储空间，有效地节省了存储空间。ＦＦＴ算法程序设计如下所示：Ｕｉｎｔｌ６ＣｏｎｖｅｒｓｉｏｎＣｏｕｎｔ；Ｕｉｎｔｌ６ｐｘ［１２８］；Ｕｉｎｔｌ６ｐｚ［１２８］；ｖｏｉｄｋｆｆｔ（ｐｒ，ｐｉ，ｎ，ｋ，ｆｒ，ｆｉ，ｌ，ｎ）｛Ｕｉｎｔｌ６ｎ，ｋ，ｌ，ｉｌ；ｄｏｕｂｌｅｐｒ［】＇ｐｉ口，仃口，五【】；ｉｎｔｉｔ，ｍ，ｉｓ，ｉｊ，ｎｖ，１０；务ｌ遭止勺砂似ｄｏｕｂｌｅＰ…ｑｓｖｒ，ｖｉ，ｐｏｄｄｒ，ｐｏｄｄｉ；算的翅问距ｑｆｐｉ［ｍ＊ｊ］＋ｆｉ［ｉｔ＋ｊ＋ｎｖ／２］；ｓ－－ｐｒｉｍ＊ｊ］＋ｐｉ【ｍ巧】；ｆｏｒ（ｉｔ＝Ｏ；ｉｔ＜＝ｎ·ｌ；ｉｔ＋＋）｛ｍ－－ｉｔ；ｉｓ－－Ｏ；ｓ－－－ｓ＋（ｆｒ［ｉｔ＋ｊ＋ｎｖ／２］＋ｆｉ［ｉ州＋ｎ吡】）；ｆｏｒ（ｉ＝Ｏ：ｉ＜＝ｋ－１；ｉ＋＋）ｐｏｄｄｒ＝ｐ－ｑ；ｐｏｄｄｉ＝ｓ－ｐ－ｑ；｛ｊ－－ｒｌｌ，２；ｉｓ＝２＋ｉｓ＋（ｍ－２＊ｊ）；ｍ－ｊ；｝ｆｉ＇［ｉｔ］－－－ｐｒ［ｉｓ］；坷ｉｔ］＝ｐｉ【ｉｓ】；／／ｇ循环为比特逆序的实现，ｐｒ、ｐｉ是原序列的实部与虚部｝ｌｉｆｔ、６是捧完序后的序列ｐｆ【０】－１．ｏ；ｐｉ【ｏ】：０．０；ｐ＝６．２８３１８５３０６／（１．０＋ｎ）；ｐｒ［１］ｆｃｏｓ（ｐ）；ｐｉ【ｌ】一ｓｉｎ（ｐ）；降‰的虚部ｉｆ（Ｉｔ＝Ｏ）ｐｉ［１］＝－ｐｉ【ｌ】；ｆｏｒ０＝－２；ｉ＜－－ｎ－ｌ；ｉ＋＋）ｆｐ＝ｐｒ［ｉ—ｌ】＋ｐｒ【ｌ】；ｑ－－ｐｉｌｉ—ｌ】４ｐｉ【１】；ｓ＝（ｐｒｐ·ｌ】＋ｐｉ［ｉ·１１）’（州１】＋ｐｉ【ｌ】）；ｐｒ［ｉ］－－ｐ－ｑ；ｐｉ［ｉ］＝ｓ－ｐ－ｑ；｝／／此循环为权值运算实现ｆｏｒ（ｉｔ＝０；ｉｔ＜－－ｎ－２；ｉｔ＝ｉｔ＋２）／／ｉｔ是序列下标，在第一级蝶式运算中，，相邻的两个运算螺下标相差２｛ｖｒ＝ｆｒ［ｉｔ］；ｖｉ＝ｆｉ［ｉｔ］；ｆｒ［ｉｑ＝ｖｒ＋ｆｒ［ｉｔ＋１］；／／第一级蝶式运算中相邻两个数值进行加减运算丘【ｉｔ］＝ｖｉ＋ｎ【ｉｔ＋ｌ】；ｆｒ［ｉｔ＋１］＝ｖｒ－ｆｒ［ｉｔ＋１］；ｆｉ［ｉｔ＋１］＝ｖｉ－ｆｌ［ｉｔ＋１］；｝，，此循环为第一级蝶式运算，该级中的蝶式权均为１ｍ＝ｎ／２；ｎｖｆｆｉ２；ｆｏｒ（１０＝ｋ－２；１０＞＝耵；１０－－）嘛去第一级，还有六级蝶式运算｛ｍ－－ｍ／２；ｎｖ＝２＊ｎｖ；，，同一级相邻的两个蝶式运算中数值的下标相差为ｎｖｆｏｒ（ｉｔ－－０；ｉｔ＜＝（ｍ－１）＊ｒｌｖ；ｉｔ＝ｉｔ＋ｎｖ）／／ｉｔ仍为数值的下标￡娟＝０３＜《ｎｖ／２）·１ｊ＋＋）｛ｐｑｎ－［ｍ＊ｊ］＋ｆｒ［ｉｔ＋ｊ＋ｎｖ／２］；／／ｎｖ／２为燥式运万方数据ｆｒ［ｉｔ＋ｊ＋ｎｖ／２］ｆｆｒ［ｉｔ＋ｊ］－ｐｏｄｄｒ；ｆｉｌｉｔ＋ｊ＋ｎｖ／２］－－ｔｉ［ｉｔ＋ｊ］－ｐｏｄｄｉ；ｒ【ｉｔ＋ｊ］＝ｆｒ［ｉｔ＋ｊ］＋ｐｏｄｄｒ；６【ｉｔ＋ｊ］＝ｆｉ［ｉｔ＋ｊ］＋ｐｏｄｄｉ；，，计算出的新序列值代替输入序列值，节省了存储空间】）ｌ，，行、６分刖为计算出的ＦＦｒ序列的实部和虚部３．２运行结果用ＦＦＴ的计算公式对单一频率的正余弦信号进行变换，可以得出单一频率的信号在频域表现为在其正负频率点上的两个脉冲。根据单频信号的这一特性可验证上述程序是否正确。将单一频率的正弦波信号接人硬件系统，打开图形观察窗口，将观察点数设置为１２８点，即可观察到如图４所示的波形。甄幻弋７弋＝．丌丁Ｖ弋丌７颞丌７Ｖ图４时域正弦波的ＦＦＴ运行结果［卜图５改善后的ＦＦｌ鼋行结果第３４卷第１期２０１２－－０１（上）１１锄图４中上半部分波形为输入的时域正弦波，下半部分波形为经过变换后的频域波形。在图４中，由于产生的模拟信号伴有噪音，导致信号频率不单一，故而在信号的频域中，除了信号对应的频重要的分析工具，文中阐述了硬件结构图和信号调理电路。详细介绍了ＦＦＴ算法原理，采用Ｃ语言编写程序实现了ＦＦＴ算法。程序运行结果表明ＴＭＳ３２０Ｆ２８１２ＤＳＰ实现ＦＦＴ运算速度快，精度高Ⅲ。率点有脉冲外，其它频率点处也有较弱的脉冲。对输入信号的频率进行调整，使信号的组成频率尽可能单一，可以得到更好的波形，如图５所参考文献：【ｌ】贾玮，杨录，张艳花．基于ＴＭＳ３２０ＶＣ５４１６的ＦＦＴ算法的实现【Ｊ】．山西电子技术。２００９，２：１１－１３．【２】ＲｒｉｇｈｔＨｅｒｔ．Ｒａｐｉｄａｌｇｏｒｉｔｈｍｓｏｆｄｉｇｉｔａｌｓｉｇｎａｌｐｒｏｃｅｓｓｉｎｇ示。可以看到在信号对应的频率点有脉冲，其它频率点的振幅为０，与理论推导结果一致，由此可验证程序设计的正确性。【Ｍ】．Ｂｅｉｊｉｎｇ，ＥｌｅｃｔｒｏｎｉｃＩｎｄｕｓｔｒｉａｌＰｒｅｓｓ，２００２．【３】胡广书．数字信号处ｔ里［ＭＩ．北京：清华大学出版社，２００３．【４】苏奎峰，吕强，耿庆锋，陈圣俭．ＴＭＳ３２０Ｆ２８１２原理与开发ＩＭ］．北京：电子工业出版社，２００５．４结论ＦＦＴ是声学、图像和信号处理等领域中一种●蠡●●矗‘●蠡‘｜童‘●蠡●●■●●■●血●■●●‘－●■●●矗●●蠡‘●■‘．ｏｋ．●■●●蠡●●■●＇■－●●●●●●●■‘●■‘ｏｋ．【上接第２页】２．３反射光谱的测试出垂直排列和不规则排列的ＺｎＯ纳米线阵列，并在此基础上制备ｎ—ＺｎＯ纳米线／ｐ－Ｓｉ光伏器件。试验测得性能最好的器件的开路电压ＶＯＣ为０．７８Ｖ，短路ＪＳＣ电流为６．２２ｍＡ／ｃｍ２。效率为２．６％。同时，一维结构的ＺｎＯ纳米阵列具有非常优异的减反射性能，利用这些ＺｎＯ纳米线阵列设计和制作了新型异质结纳米阵列太阳电池，其在２００—９００ｎｍ波长范围内，反射率约为５％。远低于原始Ｓｉ片２５％的反射率。参考文献：【１】Ｌａｗ．Ｍ．；Ｇｒｅｅｎｅ，Ｌ．Ｅ．；Ｊｏｈｎｓｏｎｄ．Ｃ．；Ｓａｙｋａｌｌｙ，Ｒ．；Ｙａｎｇ。Ｐ．Ｄ．Ｎａｔ．Ｍａｔｅｒ．４，４５５（２００５）．【２】Ｂａｉ３（．Ｄ．；Ｗａｎｇ，Ｅ．Ｇ．；Ｇａｏ，Ｐ．Ｘ．；Ｗａｎｇ，Ｚ．Ｌ．Ｎａｎｏ（２００３）．Ｌｅｔｔ３．１１４７［３１Ｗａｎｇ，Ｘ．Ｄ．；Ｚｈｏｕ，Ｊ．；Ｌａｏ，Ｃ．Ｓ．；Ｓｏｎｇｄ．Ｈ．；Ｘｕ，Ｎ．Ｓ．；Ｗａｎｇ，Ｚ．图４ＺｎＯ纳米线阵列与原始硅片的反射光谱对比Ｌ．Ａｄ．Ｍａｔｅｒ．１９，１６２７（２００７）．【４】Ｙａｎｇ。Ｐ．Ｄ．；Ｙａｎ，Ｈ．Ｑ．；Ｍａｏ，Ｓ．；Ｒｕｓｓｏ，Ｒ．；ＪｏｈｎｓｏｎＪ．；Ｓａｙ蛐ｌｙ，Ｒ．；Ｍｏｒｒｉｓ。Ｎ．；Ｐｈａｍ，Ｊ．；Ｈｅ，Ｒ．Ｒ．；Ｃｈｏｉ，ＨＪ．Ａｄ．Ｆｕｎｃｔ．Ｍａｔｅｒ．１２，３２３（２００２）．图４是Ｓｉ两种不同形貌ＺｎＯ纳米结构与原始硅片反射光谱的对比，在２００—９００ｎｍ波长范围内，样品Ｃ平均反射率约为５％，样品Ｂ平均反射率约为８％，均大大优于普通抛光硅片大于２５％的平均反射率。样品Ｂ减反射性能略低于样品Ｃ的原因可能在于测试时入射光是垂直硅片表面人射的，相对于垂直阵列。不规则纳米结构顶部区域会使得更多的光被反射出去。【５】Ｈｕａｎｇ．Ｍ．Ｈ．；Ｍａｏ，Ｓ．；Ｆｅｉｃｋ，Ｈ．；Ｙａｈ，Ｈ．Ｑ．；Ｗｕ，Ｙ．Ｙ．；Ｋｉｎｄ，Ｈ．；Ｗｅｂｅｒ，Ｅ．；Ｒｕｓｓｏ，Ｒ．；Ｙａｎｇ，Ｐ．Ｄ．Ｓｃｉｅｎｃｅ．２９２，１８９７（２００１）．【６】“ｍＪ．Ｈ．；Ｋａｎｇ．Ｃ．Ｋ．；Ｋｉｍ，Ｋ．Ｋ．；Ｐａｒｋ，Ｉ．Ｋ．；Ｈｗａｎｇ，Ｄ．ｋ：Ｐ溅Ｓ．Ｊ．Ａｄ．Ｍａｔｅｒ．１８，２７２０（２００６）．［７１ＷａｎｇＺ．Ｌ．；Ｓｏｎ９３．Ｈ．Ｓｃｉｅｎｃｅ３１２．２４２（２００６）．［８１Ｗａｎｇ，Ｘ．；Ｓｏｎｇｄ．；ＬｉｕＪ．；Ｗａｎｇ，Ｚ．Ｌ，Ｓｃｉｅｎｃｅ．３１６，１０２（２００７）．［９１Ｂ．Ｔｉａｎ，Ｔ．Ｊ．Ｋｅｍｐａ，ａｎｄＣ．Ｍ．Ｌｉｅｂｅｒ，Ｃｈｅｍ．Ｓｏｃ．Ｒｅｖ．３８，１６（２００９）．３结论采用化学气相沉积的方法在Ｐ型硅片表面制备１２０１第３４卷第１期２０１２—０１（上）［１０］Ｈｕ，Ｌ．；Ｃｈｅｎ，Ｇ．ＮａｎｏＬｅｔｔ．７，３２４９—３２５２（２００７）．万方数据基于DSP的FFT算法实现
作者：作者单位：刊名：英文刊名：年，卷(期)：
艾红， 常青青， 邓大伟， AI Hong， CHANG Qing-qing， DENG Da-wei北京信息科技大学自动化学院,北京,100192制造业自动化
Manufacturing Automation2012,34(1)
1.胡广书 数字信号处理 2003
2.苏奎峰;吕强;耿庆锋;陈圣俭 TMS320F2812原理与开发 2005
3.Rright Hert Rapid algorithms of digital signal processing 20024.贾玮;杨录;张艳花 基于TMS320VC16的FFT算法的实现 2009
本文链接：http://d.g.wanfangdata.com.cn/Periodical_zzyzdh201201007.aspx
