kok电子竞技

1、D FT的循环卷积算法推导及其FPGA实现王正彦,范延滨,徐茂荣(青岛大学,山东青岛266071摘要:首先提出了数论中的原根成对存在定理,并进行了详细的数学证明。然后根据原根可使数环重新排序的性质,利用一对原根对D FT运算的输入和输出序列重新排序,推导出D FT的循环卷积算法,进一步给出了此算法的结构图。最后给出了用V HDL语言实现该算法的完整程序、仿真结果及分析,并总结了用FPGA实现D FT运算的意义。关键词:原根;D FT;FPGA;循环卷积中图分类号:TN911172文献标识码:A文章编号:1008-0686(200405-0045-04A lgor ithm D esign an

2、d FPGA Rea l iza tion of Convolution D FTW ANG Zheng-yan1,FAN Yan-b i n2,XU M ao-rong1(1.Colleg e of A u to m a tion E ng ineering,Q ing d ao U n iversity,Q ing d ao266071,Ch ina;2.Colleg e of Inf or m a tion E ng ineering,Q ing d ao U n iversity,Q ing d ao266071,Ch inaAbstract:In th is p aper,a the

3、o rem of p ri m ary roo t ex ists as a coup le in the N um ber T heo ry w as suggested, and detailed m athem atic p roof w as given.B ased on the character of p ri m itive roo t can reo rder the num ber ring and u sing the tw o p ri m ary roo t to reo rder the inp u t and ou tp u t sequences of the

4、D FT com pu tati on,a algo rithm of D FT cyclic convo lu ti on w as deducted and fu rther structu re diagram w as given.A t the end,a com p lete p rogram w ritten in V HDL language fo r th is algo rithm,the si m u lating resu lt and analysis are giv2 en.T he i m po rtance of ach ieving the D FT com

5、p u tati on by u sing FPGA w as summ arized.Keywords:p ri m itive roo t;D FT;FPGA;circle convo lu ti on in tegral笔者在从事数论变换研究和FPGA的设计过程中,发现对于D FT的循环卷积算法推导,如果能够采用原根及其逆元(也是原根对输入输出序列进行重新排序,其推导过程将进一步简化。由此提出原根成对存在定理,并给出了严格证明,最后给出了FPGA的设计和实现。原根成对存在定理不仅有益于数论变换,而且可以应用于原根的研究。1原根成对存在定理定理设m、g均为整数,且m>g>0,若

6、g是m的原根,则g的逆元q存在,且q也是m的原根。证明由原根的定义可知(g,m=1,再根据逆元存在定理可得:g的逆元q存在,即g q1m odm。设l为整数、(m为m的欧拉函数,根据同余性质由g(m1m od m可得:g(mq l=q l m od m,即g(m-l(g qlq l m od m,进一步化简得g(m-lq l m od m。取0l(m,则可得qg(m-l m od mq2g(m-2m od mq(m-1g m od mq(m1m od m(1因为g是m的原根,所以g,g2,g3,g(m是m的一组缩系,即g,g2,g3,g(m两两不同余,所以q,第26卷第5期2004年10月电气

7、电子教学学报JOU RNAL O F EEEV o l.26N o.5O ct.2004收稿日期:2004-02-15;修回日期:2004-09-02第一作者:王正彦(1965-,女,山东省青岛人,研究生,副教授,从事数字信号处理和电子技术应用方面的教学科研工作。q 2,q 3,q(m 两两不同余,即q ,q 2,q 3,q (m 也是m 的一组缩系,根据原根存在定理得,q 是m 的原根,定理得证。2D FT 的循环卷积算法1求解原根若已知g 是m 的原根,则可以通过求解g 的逆元q 的方法,求得m 的另一个原根。表1例举了m =5、7、41的情况。表1原根对举例357152419292830

8、352D FT 的循环卷积算法设x (n 是长度为N 的有限长序列,则其N 点D F T 的表达式为X (k =N -1n =0x (n Wnk N 。对于k =0,X (0=N -1n =0x (n ,对于k =1,2,N -1,可写成X (k =x (0+N -1n =1x (n W nkN。设N 为素数,Z N 为N 的数环,g 为Z N 上的一个原根,则其逆元q =g -1亦为其原根。将k ,n =1,2,N -1通过g k模N 和g n模N 重新排序,即用g k m od N 和q n m od N (k ,n = 0,1,N -1代替k 和n 得X (g k m od N =x (

9、0+N -2n =0x (q n m od N W(q n mod N (g k mod N N即X (g k m od N =x (0+N -2n =0x (q n m od N Wgk -n mod NN(2若定义X (K =X (g k m od N x (n =x (q n m od N W (n =W gnN 则上式变为X (k =x (0+N -2n =0x (n W (k -n (3即X (k =x (0+x (n W (n (4故此将D FT 运算转换成循环卷积运算。3用FPGA 实现D FT 循环卷积算法以N =5为例,则g =2及其逆元q =3均为Z 5的原根,故k 的新排

10、序(20,21,22,23m od 5=(1,2,4,3n 的新排序为(30,31,32,33m od 5=(1,3,4,2X (2k m od 5=x (0+3n =0x (3n m od 5W(2n mod 5(3k mod 55写成矩阵形式X (1X (2X (3X (4=W 15W 35W 45W 25W 25W 15W 35W 45W 45W 25W 15W 35W 35W45W25W15x (1x (3x (4x (2+x (0x (0x (0x (0(5交换W 矩阵的第2列和第4列,得X (1X (2X (3X (4=W 15W 25W 45W 35W 25W 45W 35W 1

11、5W 45W 35W 15W 25W 35W 15W 25W 45x (1x (2x(4x(3+x (0x (0x (0x (0(6W 是一个循环矩阵,即每一行都是前一行循环左移的结果。上式的结构图如图1。输入按照x (3,x (4,x (2,x (1的顺序输入,输出按照X (1,X (2,X (4,X (3的顺序输出。此为一转置结构的F I R 滤波器。图1循环卷积算法结构图实现上述算法时,应首先对系数W k 5进行量化。假定输入值和系数都被表示成8位有符号数,量化后的系数如表2所列:表2量化系数表k 01234R e (256W k s 25679-207-20779I m (256W k

12、 s 气电子教学学报26卷将图1所示算法用V HDL语言实现的程序:PA CKA GE B bit int IS自定义程序包SUBT YPE W ORD8IS I N T EGER RAN GE-2337TO23 37-1;定义数据类型SUBT YPE W ORD11IS I N T EGER RAN GE-23310TO2 3310-1;SUBT YPE W ORD19IS I N T EGER RAN GE-23318TO2 3318-1;T YPE A RRA Y W ORD IS A RRA Y(0to3O F W ORD19; END B bit i

13、nt;L I BRA R Y wo rk;库的使用和说明U SE wo rk.B bit int.ALL;L I BRA R Y ieee;U SE ieee.std logic1164.ALL;U SE ieee.std logic arith.ALL;U SE ieee.std logic unsigned.ALL;EN T IT Y rader5IS实体POR T(clk:I N STD LO G I C;端口说明x in:I N W ORD8;y real,y i m ag:OU T W ORD11;END rader5;A RCH IT ECTU R E flex O F rader

14、5IS结构体S IGNAL count:integer RAN GE0TO11;定义信号,时钟计数器T YPESTA T E T YPE IS(Start,L oad,R un;S IGNAL state:STA T E T YPE;状态变量S IGNAL accu:W ORD11;X(0 S IGNAL real,i m ag:A RRA Y W ORD;滤波器抽头延迟线实部,虚部S IGNAL x79,x207,x243,x150:W ORD19;滤波器系数S IGNAL x5,x25,x7,x125,x256:W ORD19;滤波器辅助系数S IGNAL x,x0:W ORD8;x(n,

15、x(0 BEG I NStates:PROCESS状态机BEG I NW A IT UN T I L clk=1;CA SE state ISW H EN Start=>初始状态state<=L oad;count<=1;x0<=x in;下载并保存x(0accu<=0;y real<=0;y i m ag<=0;W H EN L oad=>下载状态IF count=6TH ENstate<=R un;EL SEstate<=L oad;accu<=accu+x;求解X(0END IF;count<=count+1;W H

16、 EN R un=>运行状态IF count=11TH ENy real<=accu;输出X(0y i m ag<=0;state<=Start;EL SEy real<=real(0 256+x0;输出X实部y i m ag<=i m ag(0 256;输出X虚部state<=R un;END IF;count<=count+1;END CA SE;END PROCESS States;Structure:PROCESS转置结构F I R滤波器(实部和虚部 BEG I NW A IT UN T I L clk=1;x<=x in;下载输入

17、real(0<=real(1+x79;计算X(k的实部real(0(不包括x(0 real(1<=real(2-x207;real(2<=real(3+x79;real(3<=-x207;i m ag(0<=i m ag(1-x243;计算X(k的虚部i m ag(0i m ag(1<=i m ag(2-x150;i m ag(2<=i m ag(3+x243;i m ag(3<=x150;END PROCESS Structure;Coeffs:PROCESS求滤波器系数,实现乘法器模块BEG I NW A IT UN T I L clk=1;

18、x79<=x2532+x25+x34;x207<=x2538+x7;x243<=x12532-x7;x150<=x2534+x2532;END PROCESS Coeffs;Facto rs:PROCESS(x,x5,x25求滤波器辅助系数BEG I Nx5<=x34+x;x7<=x5+x32;x25<=x534+x5;x125<=x2534+x25;x256<=x3256;END PROCESS Facto rs;END flex;用EDA软件M axp lu s 进行仿真,选用EPF10K10L C84-4型FPGA器件,并设x(n=7

19、4第26卷第5期王正彦等:D FT的循环卷积算法推导及其FPGA实现 (10,20,30,40,50,结果如图2所示。其中x in 即x (n ,按照x (0,x (3,x (4,x (2,x (1的顺序输入。y rea l 和y i m ag 分别为X (k 的实部和虚部,按照X (1,X (2,X (4,X (3,X (0的顺序输出。需要说明的是在M axp lu s 中负数是以补码的形式显示的,即2023实为-25,2013为-35,2039为-9,故由仿真结果可得X (k =(150,-25+j 34,-25+j 8,-25-j 9,-25-j 35,这与按X (k =N -1n =0

20、x (n Wnk N进行手工计算所得结果是完全一致的 。图2仿真结果4结论综上所述可以得到如下结论:(1原根是成对存在的,即若g 为m 的原根,则其逆元q 亦为m 的原根。(2利用原根可将数环重新排序,将此理论用于D FT ,可推导出D FT 的循环卷积算法,将该算法用V HDL 语言实现并将程序下载至FPGA 中,其意义在于可用FPGA 实现D SP 的重要内容之一D FT 运算,而FPGA 实现D SP 的优势在于速度快。参考文献:1Uw e M eyer 2Baese 著1数字信号处理的FPGA 实现(刘凌等译M 1北京:清华大学出kok电子竞技社,20032裴定一,祝跃飞1算法数论M 1北京:科学

21、出kok电子竞技社,20023胡广书1D FT 和卷积的快速算法M 1清华大学电机工程与应用电子技术系讲义,1993(上接第29页颜彪等文中频信号首先被直接采样,然后分成上下两路,一路信号经过希尔伯特变换网络,另一路信号经过延迟单元(以保证信号的同步,从而得到一对正交数字信号。该方法的数字化程度较高,易于用FPGA 器件实现4。实际应用中,希尔伯特变换通常采用半带滤波器(H alf 2B and F ilter ,HB F 和级联积分梳状滤波器(Cascaded In tegrato r 2Com b F ilter ,C I CF 来实现。4结束语希尔伯特变换可以提供90°的相位变化而不影响频

22、谱分量的幅度大小,如果采用数字方式,即离散希尔伯特变换则可产生具有高平衡度I -Q 信道,因此,它被广泛应用于通信、雷达、语音处理、数字化医学超声成像等这类需要用到信号正交分解技术的系统中。本文分别从希尔伯特变换的定义、实现及其应用等方面进行了详细阐述,希望能给电子通信专业的学生或有关技术人员提供帮助。参考文献:1Jam es T sui 著1宽带数字接收机M 1杨小牛,陆安南,金飚译,北京:电子工业出kok电子竞技社,200:174-1802何正权,何旭1多次采样与希尔伯特变换J 1成都:电子科技大学学报,1997,26(5:504-5103李晶晶,江桦,王明坤1希尔伯特变换在信号解调中的应用J 1郑州:信息工程大学学报,2002,3(4:29-314黄英,李景文,刘敏1软件无线电技术在中频接收机中的应用J 1北京:无线电通信技术,2004,30(1:18-2084电气电子教学学报26卷