基于FPGA的数论变换算法及应用的研究

1、技术创新中文核心期刊微计算机信息嵌入式与年第卷第期元年邮局订阅号现场总线技术应用例应用基于的数论变换算法及应用的研究南京航空航天大学余汉成王成华邵杰夏永君摘要本文介绍了数论变换及其一些基本特性讨论了数论变换中的快速算法和较长序列变换等重要问题并给出了解决方案。进一步论证了基于实现数论变换的可行性及其在数字信号处理应用中优势所在最后设计出了基于的基本数论变换的实现并基于此实现了快速卷积运算器。关键词数论变换卷积中图分类号文献标识码文章编号引言数论变换是以正整数为模的环上定义的线性正交变换所用的运算法则是数论中的同余运算特别是其中的费马数变换其基函数由的方幂构成即数论变换不用乘法只用移位操作因此它

2、比傅立叶变换的速度更快。和傅立叶变换一样数论变换具有正交性、周期性、对称性、位移性、循环卷积等特性。这决定了基于的系统将在数字信号处理的诸多方面得到应用。随着超大规模集成电路特别是技术的日益成熟使得的算法的几个基本单元得到有效、灵活而又快速的实现这样基于的实现显示出其独特的优势和广泛的应用前景。数论变换定义在有限群上定义了数论变换。设在以正整数为模的环上有存在变换对其中并且在有限群?中所有有和即是中的一个次单位根。类似可以定义二维数论变换对在环中没有有价值的变换但使用邻近的形如形式的质数称为质数形如形式的质数称为质数。循环卷积特性和是模定义的长度为的序列是和的循环卷积。令为和的长度为在上计算的

3、数论变换有?。字长限制用计算卷积时须注意输出序列的所有元素都必须在范围之内假设是无符号编码即满足结果才为真。数论变换的快速算法及新的定义方法数论正变换的快速算法我们也可以把数论正变换写成数论正变换也有类似傅立叶变换的快速算法下图此快速算法的基本蝶形运算单元及点数论正变换快速算法的流程图。图快速数论变换的蝶形算子及算法流程图数论逆变换的快速算法对于逆变换其中表示一个整数使得?因为?所以对于逆变换我们也可以写成余汉成讲师?邮局订阅号元年技术创新应用技术应用例您的论文得到两院院士关注数论变换的一种新的定义通过推导我们可以对比一下式与式发现无论从硬件还是用软件来实现数论逆变换的快速算法可以与数论正变换

4、的快速算法通用只要把换成最后变换结束再乘既可。从这个角度上讲我们可以重新定义一下数论变换数论变换的实现及其应用从前面我们可以看出快速数论变换优于快速傅立叶主要是由于算子和的差别如果取或的幂实际就是移位操作而乘则对应非整数的乘法两者实现的速度和代价都会差很多。所以数论变换及用数论变换实现卷积的过程的相关运算都可以化为取模、加、乘三种基本运算对于取模运算如果我们采用数制进行运算就可以自动的对任意位宽实现模运算。对于乘运算实际上它是移位操作基于可以方便的实现任意位宽的移位操作。对于加法实现起来也是非常的简单快速。数制对于前面所说的数对应数制可以不作调整直接有效的实现模的运算。数制表示法的编码定义如下

5、这种数制表示法能够有效的实现模的运算。下面我们所论述的问题都是针对形似的数。基本数论变换的实现基本数论变换的实现由数论变换新的定义我们以长度为、模阶数为的简单数论变换为例介绍快速数论变换的实现。其中碟形算子就是一个简单基于数制的加法电路和移位电路限于篇幅这里不再赘述。图快速数论变换正、逆设计框图从上图可以看出实现这样的一个变换长度为的数论变换的核心是两个并行的蝶形处理单元组成的碟形算子组虚线框内所示通过控制单元对碟形算子组和一个中数据存储和流向的控制实现每级之间对蝶形算子组的分时复用这样既提高了效率又节约了资源。如果变换长度较长也不一定用个并蝶形处理单元组成的碟形算子组可以用、个并蝶形处理单元

6、等。这样通过控制单元首先在每级之内实现间对蝶形算子组的分时复用再在各级之间实现分时复用。另外如果是正运算如果是逆运算、后面还要加上处理单元一个简单的移位电路。这样通过控制单元的适当控制还可以实现正、逆数论快速变换的分时复用。这样最大程度提高了硬件的利用率。下面是对仿真注意仿真图中的数据都是用数制表示。的上升沿启动变换输出允许信号表示的上升沿表示一次快速变换结束标志为表示此次完成的是正运算还是逆运算表示正运算表示逆运算。从仿真图上我们可以看出完成一次这样的变换大约需要。图数论变换的仿真波形图基于数论变换实现快速卷积运算器有前面的讨论可知我们可以基于实现快速卷积。根据场合不同应用的方法也有所不同。

7、如果需要实现卷积的长度较长而卷积序列的数值又较小的话我们可以利用二维数论变换实现快速卷积运算如果需要实现卷积不是很长而卷积序列的数值又不定的话我们可以利用一维数论变换实现快速卷积运算。无论是那种方法基本的思想都是一致的输入的序列及输出序列都是串行数据以为时钟。信号的标志将输入的序列、载入内部寄存器信号表示输出使能表示输出有效信号标志转换开始。从原理可知这样的运算主要是和乘法两种单元。对于单元无论是一维还是二维都是通过若干个蝶形处理单元来完成。为了节约资源我们使用同一单元分时复用完成两个输入序列的正变化和输出序列的逆变换。对于乘法单元为了提高速度我们用个并行的乘法器进行运算。当然本设计还需要一些

8、其他的附属单元例如时序和数据方向的控制需要控制单元输入和输出?技术创新中文核心期刊微计算机信息嵌入式与年第卷第期元年邮局订阅号现场总线技术应用例应用都是我们习惯的二进制补码数制而中间的运算都是数制所以我们需要二进制补码和数制相互转换的单元还需要一定规模的存储单元。图基于数论变换实现快速卷积运算器设计框图我们基于上面的框图设计了一个快速卷积运算器。此运算器可在内实现两个长度为的离散序列的圆周卷积。输出字长为位。下图是我们运算的仿真从的上升沿到变高表示一次转换周期。本次仿真实现了和的圆周卷积结果是分和轮流输出这样的快速卷积运算器在数字信号处理得很多领域中是非常有价值的。图快速卷积运算器仿真波形图结

9、束语基于的数论变换算法及应用的研究是一个比较新的领域目前国内外开展此项工作的都还很少。本文讨论了数论变换的诸多特性的基础上创新点在于在推导出快速数论变换的同时给出了数论变换的一种新的定义形式。论证了基于实现的可行性及高效性。设计出基于的的有效实现应用数制、模为数。以此为基础实现了快速卷积运算器。实际上基于的快速数论变换不只是在速度有优势而且可以应用的领域非常广阔。但是对于数论变换本身尚有许多问题需要进一步研究。比如物理解释问题、误差估计问题等等都有待进一步解决。参考文献著刘凌等译数字信号处理的实现北京清华大学出版社曹秀英数论变换在异步保密机中的应用通信学报梁曦捷肖璋一种基于的顺序迭代设计微计算

10、机信息蒋增荣数论变换上海科学技术出版社作者简介余汉成年生讲师目前研究方向数字图像处理王成华年生教授目前研究方向数字系统设计、数字信号处理。南京市南京航空航天大学电子工程系余汉成王成华邵杰夏永君通讯地址南京市南京航空航天大学信息学院余汉成收稿日期修稿日期上接第页小结环路滤波算法简单但其边界滤波函数的判断分支为并行优化增加了困难本文对该算法进行了改进并分别讨论了基于平台核的并行优化和基于平台的并行优化并通过优化解码器验证了优化效果很好使解码速度有了显著提高。本文作者创新点从标准中总结提取出其环路滤波的强度控制原理。提出了对中环路滤波的核心判断分支语句的改进方法。给出了基于两种不同平台的核和的的并行实现方法并针对各自的特点对重点问题做了详细的说明。参考文献工作组“信息技术先进音视频编码第七部分移动视频送审稿”“”“”钱晓捷汇编语言程序设计第二版电子工业出版社苏绍璟开放式多媒体应用平台双核通讯技术微计算机信息作者简介裴雷男年生中国海洋大学信息学院电子系硕士研究生研究方向视频编解码田树民男海信集团研发中心高级工程师博士研究方向视频编解码刘卫东男海信集团研发中心高级工程师博士后研究方向