摘 要：介绍了Winograd快速傅立叶变换的方法。这种方法的乘法次数只有Cooley-Tukey傅立叶算法的1/3，而加法次数并无明显增多，因此有很好的推广价值。采用这种算法设计了三相频谱分析仪，大大提高了计算速度。
关键词： Winograd算法；快速傅立叶变换；频谱分析仪
1引言
离散傅立叶变换(DFT)是对信号作数字频谱分析及实现数字滤波的基本方法。它在频谱分析、数字通信、语音信号分析、图象处理、雷达、声纳、地震、生物医学工程等各个领域都有着日益广泛的应用。直接计算DFT，工作量相当大，当数据点数为N时，大约需要N2次乘法和N2次加法。1965年，美国的Cooley和Tukey提出了快速傅立叶变换(FFT)的算法［1］。这种算法将DFT的计算速度提高了N/log2N倍，使许多信号的处理工作能与整个系统的运行速度协调。傅立叶变换的应用也就从某些数据的事后处理及系统的模拟研究，而进入数据的实时处理。现在已经有了一些更好的算法，例如Winograd快速傅立叶变换，这些算法是利用抽象代数和初等数论等数学工具建立起来的，因而接受程度和应用范围就受到了很大的限制，工程上使用的也较少。表1列出了几种傅立叶变换算法计算量的比较［2］，新算法的优越性是显而易见的。
2小数组Winograd快速傅立叶变换算法
所谓小数组Winograd快速傅立叶变换算法是指针对信号长度N＝2，3，4，5，6，7，8，9，16这8种短DFT，Winograd所提出的独特算法。他应用域的理论证明了这些算法的乘法次数接近于N，而加法次数与Cooley-Tukey FFT相近。这些小数组Winograd算法之所以重要还在于所有信号长度N很大的Winograd算法，都可以由几个互素的小数组Winograd算法经过矩阵嵌套来得到，使其乘法次数仅为Cooley-Tukey FFT的1/3，而加法次数并无明显增多。
设长度为N的信号为x＝｛x(n),n＝0,1,…，N－1｝,x的傅立叶变换是另一个长度为N的向量X＝｛X(k),k＝0,1,…,N－1｝,它由下式给出
其中
，我们也可以将其写成矩阵乘积形式，X＝Wx
其中，T和S的元素仅包含0和±1，C只有对角线上的元素非零，这样只有在数据与C作计算时才包含乘法计算，可以使计算中的乘法运算大大减少。W的分解是一个比较复杂的过程，我们应用时可直接查阅手册或参考书［1，2］。这里我们以N＝3为例，说明计算过程。
N＝3时，可分解W得，
可见只须3次乘法和6次加法，就可完成3点傅立叶变换，图1是其信号流图，具体计算如下：
3大数组Winograd快速傅立叶变换算法
信号长度N从几十个点到数千个点的Winograd傅立叶算法称为大数组Winograd快速傅立叶变换算法。例如N＝504时，可以将其分解为504＝7×8×9三个因子，利用小数组Winograd算法进行计算，把一维大数组傅立叶变换转化为多维小数组来计算。
大数组Winograd算法，首先要把一维输入映射到多维。计算完成后，还要将多维转化到一维。以N＝12＝3×4来说明这种转换。其他二维或高维过程可类似进行。
将X(k1,k2)映射为X(k)，即得到最后结果。要完成的映射即为
根据中国余数定理［1，2］，按如下方法确定映射关系：
计算结果如表2和表3所示。然后按图2进行数据重排。
接下来进行Winograd傅立叶计算，设输入信号经过标号重排后为x(n)′，计算后为X(k)′，则
⊕为矩阵直积(Kronecker积)
其中S12和T12全部元素均为0，±1，C12中只有对角线上的元素非零，这样只有在数据与C12作计算时才包含乘法计算。故计算12点Winograd傅立叶变换，仅须12次乘法，大大提高了计算效率。
4频谱分析仪的设计
所设计频谱分析仪用于对电力系统中的三相电源进行谐波监测。将电压和电流分别经过传感器送至PCL_1800数据采集卡，再由工控机上的软件进行处理。这样可以利用工控机所配的显示器、打印机、存储器等资源，提高了产品开发的速度，也提高了可靠性。其原理图如图3所示。
所采用的电流和电压传感器都是西南自动化研究所生产的WB系列传感器，精度是0.5级。采集卡是台湾研华公司生产的PCL_1800数据采集卡，这是一块高速、高性能、多功能的插入式数据采集卡，它有16个单端输入通道或者8个差分输入通道。采集三相的电压和电流信号，只需使用其中的6个通道。PCL_1800的采样频率可以由软件精确控制。
软件的设计可以分为两大部分：1)数据采集，2)对采集处理，采用Visual Basic语言完成设计。数据采集程序主要是对PCL_1800进行设置，设置好以后，启动PCL_1800，PCL_1800就可以自动按照设置的要求采集数据了，无须主机的干预。图3是设置PCL_1800的流程图。
数据处理采用本文所介绍的Winograd算法，对6路信号的每路每秒采集1008个点，1008＝19×9×7，按此进行分解，对6路信号分别进行计算，即可得到各相的电压和电流的频谱。
5总结
通过具体应用发现Winograd算法的计算速度快是其显著的优点， 其不足之处在于， 程序设计要比CooleyTukey算法繁琐，而且对于信号长度[WTBX]N较大时，N要能够分解为几个互素小N的乘积，因此对N有一定的选择。
Winograd算法不仅显示了更高的计算效率，在理论上也有所创新。Winograd还证明了当数据的点数N为素数时，Winograd算法所需的乘法次数达到了理论上的最小值。但在工程上还很少使用这种算法，对其在工程上应用的具体细节缺乏研究。本文希望抛砖引玉，使其在工程上得到越来越广泛的应用。
参考文献
［1］张彦仲，沈乃汉.快速傅里叶变换及沃尔什变换［Ｍ］.北京：航空工业出版社，1989.
［2］［美］R.E.布莱赫特，著，肖先赐，等译.数字信号处理的快速算法［Ｍ］.北京：科学出版社，1992.
