快速整序算法

在FFT运算中,每一个数据都必须经过一次整序(输入或输出),因此加速整序的运算是很有实用意义的。本文提出两种快速算法,可以大大加速整序运算。(1)应用位序倒置原理的快速整序算法,每个数的反序只需2次采法,比雷德法快一倍多。(2)应用FFT分解中序号重排原理的快速算法,它只需极少量乘法,在N=R~M个数据中只需2(M—1)次乘法,因此整序运算速度非常快。     

一种长序列卷积的默森变换算法

本文深入研究了应用默森变换方法计算长序列卷积的运算问题,给出了一种将长序列卷积缩减为短序列卷积,然后通过采用默森变换进行计算的高效算法。结果表明:当卷积结果长度N=N_1N_2…N_4,N_i为素数,i=1,…,d,则应用该算法计算序列卷积所需要的实数乘法次数M以及实数加法次数A分别为:M=N;A=2N(sum from i=1 to dN_i—d)     

一种新的基于矩的改进离散余弦变换及其反变换快速算法

为了提高离散余弦变换(MDCT)及其反变换(IMDCT)的计算效率,提出一种新的基于一维离散矩的快速算法.首先把MDCT和IMDCT的核函数映射到另外一个集合进行合并化简,再用三角函数泰勒级数展开的方法,将MDCT和IMDCT的计算用有限项的一维离散矩的线性加权和近似.一维离散矩的快速计算可以采用p+1维的矢量加法结构进行,用加法运算代替乘法运算,有效地减少了乘法的运算量.该算法的乘法计算量仅为O(Nlog2N/log2log2N),少于通常快速算法所需的O(Nlog2N),可以有效地降低运算时间.理论分析和实验结果都表明:用一维矩近似的方法计算MDCT和IMDCT的结果精度很高,运行速度比较快,能够很好地满足实际计算的要求.     

基于DSP的IMDCT快速算法

修正离散余弦变换 ( MDCT)在音视频信号编码中得到广泛地应用 ,其快速算法在实时编解码系统中尤为重要。论文给出了一种适用于数字信号处理器 ( DSP)实现的修正离散余弦反变换 ( IMDCT)快速算法—用 M/ 2点时间抽取 ( decimation in time,DIT)分裂基 FFT实现 2 M点的IMDCT。算法是基于蝶形运算组成 ,在 DSP中可以获得很高的运算效率。该算法的蝶形运算结构同样适用于正向MDCT。在由定点 DSP实现的活动图像专家组 ( MPEG)音频层 III解码器中 ,与 MPEG音频压缩标准 ISO/ IEC 11172 -3中给出的 IMDCT运算量相比较 ,该文提出的 IMDCT快速算法节省了 2 / 3的运算时间和 1/ 2的存储空间。     

一种有效的MDCT/IMDCT快速算法

提出了一种输入序列长度为N=5×2m的改进型的离散余弦变换（MDCT）的有效算法,可以有效减少数据量,提高计算机储存和运算效率.首先将序列长度为N的MDCT转化为N/2的离散余弦变换IV型（DCT-IV）,然后将后者转化为长度为N/2的离散余弦变换II型（DCT-II）,最后再通过加法和乘法运算实现快速计算过程.同时,分析该算法的算术复杂度.结果表明,较之传统方法,提出的算法能使常用窗型下的MDCT算术复杂度降低20%以上,实现了音频和语音编码领域的运算效率的提高.     

二进制域滑动窗口快速模乘算法

加速GF（2^m）上的模乘运算是提高GF（2^m）上ECC算法性能的关键。分析了窗口宽度ω的comb多项式乘法和NIST约简多项式算法,结合两种算法提出一种滑动窗口的快速模乘算法。该算法弥补了先乘后模方法在时间上和存储空间上的缺点,缩短了运算时间,仿真结果表明快速模算法的运算效率比先乘后模的窗口comb多项式乘法和NIST快速约简速度提高21%左右,预计算只需要ω-1个值。     

基于NAFw的二进制域乘法算法

椭圆曲线上的乘法运算速度是提高椭圆曲线加密(ECC)性能的一个关键;分析了宽度w的非相邻表示型(NAF)算法和多项式乘法算法,提出了一个基于NAFw的二进制域乘法算法;算法减少了运算中的异或运算次数和预计算个数,缩短了运算时间且节省了存储空间;经建模仿真,结果表明本算法运算效率较comb多项式乘法平均快14.7%左右,预计算只需要计算2w-1-1个,从存储预计算个数和时间消耗综合考虑w=4也是较优的窗口宽度选择。     

线性调频Z变换在数据处理中的应用

讨论一种基于DSP对数据序列进行频谱分析的运算法则。这种线性调频Z变换（简称CZT）是基于DSP处理器采用FFT变换方法对任意长度数据序列进行DFT变换计算。对于同一数据序列,CZT总的运算时间是FFT变换的2～3倍,运算结果和FFT、DFT转换结果一致。CZT适用任意长度采样序列,而非一定要求基2的长度,由此可使处理系统获得最大采样速率、采样大小和频谱分辨率。     

反重叠变换的快速算法及其FPGA实现

常用的反重叠变换算法运算复杂度较大，难以在FPGA中应用。根据DCT_IV的正交性和对称性，提出了基于M/2点FFT蝶形运算的反重叠变换快速算法。进一步分析了算法的复杂度，采用并行处理和流水线技术完成了反重叠变换快速算法的硬件设计和FGPA实时实现。     

快速计算等维长多维Fermat数变换的新算法

本文从并行处理的观点出发,导出了快速计算等维长多维Fermat数变换(FNT)的新算法,与传统的一维FNT快速算法计算多维FNT相比,两种算法具有相同的加减法运算量,但当维数为2、3、4和d时,新算法分别要少做25％、41.67％、53.1％和(1-2/d+2/d2~d)×100％的模M的一般乘法。     

非均匀快速傅立叶变换在音频编码中的应用

在音频变换编码中,一般采取均匀变换的方法进行频谱分析和心理声学模型计算,比如快速傅立叶变换（FFT）,移位离散傅立叶变换（SDFT）和改进离散余弦变换（MDCT）.但均匀频谱分析方法并不符合人耳听觉特性,需要进行额外的非线性映射,并且在低频段分辨率不足.本文在音频编码中引入非均匀快速傅立叶变换（NUFFT）,可以直接使频谱在不同频段具有不同的频率分辨率,非常有利于提高编码效率 同时根据音频编码的需求提出一种专门的近似求逆方法,尽管这种方法存在一定误差,但是可以证明这些误差主要与人耳不敏感的高频信息有关,并且采用此种近似求逆方法,NUFFT相对于FFT有更好的算法稳定性.最后给出了利用NUFFT和FFT进行变换操作的测试结果,从数据精度和客观音质评价两方面都说明在低码率下NUFFT的表现优于FFT.     

线性调频Z变换在信号频谱分析中的应用

由于快速傅里叶变换（Fast Fourier Transform,FFT）算法不能精确反应信号的局部频谱特性,对此,本文以按时间抽取（DIT）的基-2FFT算法为基础,并参考基于FFT的布鲁斯坦（Bluestein）算法,设计了新的信号频谱分析软件,用于对实序列采样信号做线性调频Z变换,即频率抽样处在Z平面上,可沿任意螺线做频率抽样的频谱分析方法.结合工程实践对相同采样点数的信号在0—50Hz频率段做频谱分析,由频谱图可以看到,采用线性调频Z变换算法远比采用FFT变换算法求得信号的频谱更精确.     

一种高速2-D滑动FFT的设计实现

文章介绍了采用2-D快速傅里叶变换(fast Fourier transform, FFT)算法的滑动窗FFT的基本特性原理和硬件实现过程，完成了窗长256点、步长16点的2-D滑动窗FFT的专用集成电路(application specific integrated circuit, ASIC)设计。传统FFT算法受序列完整性的制约，时滞较大，无法满足某些高实时性信号分析领域的处理速度要求。该文采用滑动FFT算法，克服了传统FFT对序列完整性的依赖，设计的滑动FFT处理器使用2-D FFT压缩新序列计算时间，以基16蝶形运算器为核心，采用系数复用和高基Booth方法优化系数编码技术压缩乘法器的数量，减少电路面积。所设计的2-D滑动FFT完成单次滑动窗长的计算时间比传统算法节约了16.1%,变换结果与MATLAB的运算结果相比，信噪比(signal-to-noise ratio, SNR)大于130 dB。在TSMC 28 nm的工艺下，工作主频为600 MHz,面积为1 980μm×2 060μm。     

OFDM/DMT中一种基于DIT-DHT的高效率FFT/IFFT结构

提出了一种基于按时间抽取(DIT)离散哈特莱变换(DHT)的快速傅里叶变换(FFT)结构,运算过程均为实数操作.与复数FFT相比,该结构可以节省1/2的RAM并且需要更少的乘法器和加法器.这种FFT/IFFT结构适用于ADSL/VDSL、DAB/DVB、WLAN及其他OFDM/DMT应用和实数FFT应用中.     

一组实用的基本曲线快速生成算法

本文采用增量法,选取适当的参数方程,得到了椭园(包括园)、抛物线、双曲线、阿基米德螺线、对数螺线以及概率曲线弧的快速生成算法。这些算法避免了需要较长时间的函数值计算,一般只需进行4次乘法和4次加法运算,就可以由曲线弧上前一点的坐标值精确地计算出下一点的坐标值。     

JPEG编码算法的DSP优化实现

文章介绍 JPEG编码的 DSP实现 ,且着重讨论 DCT快速算法和 DCT系数量化的快速实现 ,将 8点 DCT分解为蝶形运算和乘法累加运算两级结构 ,利用 DSP的乘法累加指令和双字加 /减法指令快速实现 DCT。用小数乘法运算代替 DCT系数量化的除法运算 ,快速实现了量化操作 ,JPEG算法用汇编语言编程实现 ,编译后的可执行代码仅 2 k字     

ηT配对的配对域F36m上的最优乘法算法

在基于配对的公钥密码学应用中, 配对的有效快速实现依赖于基域的扩域中乘法算法的有效快速的实现,特别是在η_T配对的实现中需要 F_3^6m中的快速乘法运算。作者提出了对偶插值算法, 其渐近复杂度为 11 次基域中 的乘法运算, 这达到了F_3^6m中乘法运算的理论下界。     

基于NEDA的最佳分组算法

新分布式算法(NEDA)是只使用加法运算完成乘加计算(MAC),它在面积和功耗方面的优越性是通过消去系数冗余使硬件面积大幅下降体现出来的.本文提出的最佳分组算法就是一种快速有效的去除系数冗余的方法,它是针对NEDA结构中的加法器矩阵(AM),通过对所有AM分组查找出现次数得出可复用的最佳位置来快速有效的去除AM冗余.研究表明,该算法能利用程序快速有效地去除NEDA结构的DCT和FFT的AM冗余,大幅降低硬件面积,并且它对于NEDA结构的数字信号处理硬件设计都广泛适用,使相应的硬件设计效率大幅提高.     

一种新的三维MDCT的快速算法

提出了计算三维改进的离散余弦变换(MDCT)的一种快速方法,可以有效减小数据量,提高计算机存储和运算的效率.首先将序列长度为N1×N2×N3的三维MDCT转化为(N1/2)×(N2/2)×(N3/2)的三维离散余弦变换Ⅳ型(DCT-Ⅳ)(N1=2m1,N2=2m2,N3=2m3),然后将后者转化为8个长度为(N1/4)×(N2/4)×(N3/4)的三维离散余弦变换Ⅱ型(DCT-Ⅱ),最后再通过变量代换和加法运算实现整个快速计算过程.同时,通过编写程序验证算法的正确性,并分析该算法的计算复杂度.结果表明:较之传统的行列方法,所提出的算法能够有效使计算复杂度降低75%左右,实现了计算机在三维信号处理领域的运行速率的提高.     

环Z_n上圆锥曲线加法的改进

环Zn圆锥曲线上的加法都要以(x,y)的形式表示出来作为判定条件,分别考虑运算结果属于C1,C2,C3,O的情况,因此计算比较繁琐.根据环Zn上的加法的定义对环上加法进行改进.运算过程中,圆锥曲线上的点都以参数t表示,不用每一步都计算出(x,y),利用中国剩余定理对点P坐标进行分解,然后将(tmp,tnq)合并,计算nP的坐标,运算时只需要对参数t进行操作,简化了环Zn上圆锥曲线的加法运算,明显减低计算的时间复杂度,算法优于改进前的加法运算.