




kok电子竞技权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
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卷
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
kok电子竞技:最新文档
- 合伙销售茶叶合同范本
- 农业维护协议合同范本
- 办公耗材批发合同范本
- 医院保洁耗材合同范本
- 合同范本由谁出
- 售卖蛋糕合同范本
- 受托付款合同范例
- 员工社:贤侗
- 合同范本个可以获取
- 厨师劳务派遣服务合同范本
- 2024中核集团中核资本招聘笔试冲刺题(带答案解析)
- CAS铝镁质保温施工施工方法及工艺技术
- 北师大kok电子竞技四kok电子竞技下册认识三角形和四边形
- 2023风电机组预应力混凝土塔筒与基础结构设计标准
- 2024年上海公安机关勤务辅警招聘笔试参考题库附带答案详解
- 《传染病》PPT课件完美kok电子竞技-2024鲜kok电子竞技
- 健康知识科普讲座主题
- 2024年事业单位考试昆明市A类《职业能力倾向测验》深度预测试题含解析
- 产品试用免责声明
- 篮球突分技术与配合-教学设计
- 【音乐】歌唱祖国-《彩色的中国》课件 2023-2024学年人音kok电子竞技初中音乐七kok电子竞技上册
评论
0/150
提交评论