1、D FT的循環(huán)卷積算法推導(dǎo)及其FPGA實(shí)現(xiàn)王正彥,范延濱,徐茂榮(青島大學(xué),山東青島266071摘要:首先提出了數(shù)論中的原根成對(duì)存在定理,并進(jìn)行了詳細(xì)的數(shù)學(xué)證明。然后根據(jù)原根可使數(shù)環(huán)重新排序的性質(zhì),利用一對(duì)原根對(duì)D FT運(yùn)算的輸入和輸出序列重新排序,推導(dǎo)出D FT的循環(huán)卷積算法,進(jìn)一步給出了此算法的結(jié)構(gòu)圖。最后給出了用V HDL語(yǔ)言實(shí)現(xiàn)該算法的完整程序、仿真結(jié)果及分析,并總結(jié)了用FPGA實(shí)現(xiàn)D FT運(yùn)算的意義。關(guān)鍵詞:原根;D FT;FPGA;循環(huán)卷積中圖分類號(hào):TN911172文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):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筆者在從事數(shù)論變換研究和FPGA的設(shè)計(jì)過(guò)程中,發(fā)現(xiàn)對(duì)于D FT的循環(huán)卷積算法推導(dǎo),如果能夠采用原根及其逆元(也是原根對(duì)輸入輸出序列進(jìn)行重新排序,其推導(dǎo)過(guò)程將進(jìn)一步簡(jiǎn)化。由此提出原根成對(duì)存在定理,并給出了嚴(yán)格證明,最后給出了FPGA的設(shè)計(jì)和實(shí)現(xiàn)。原根成對(duì)存在定理不僅有益于數(shù)論變換,而且可以應(yīng)用于原根的研究。1原根成對(duì)存在定理定理設(shè)m、g均為整數(shù),且m>g>0,若

6、g是m的原根,則g的逆元q存在,且q也是m的原根。證明由原根的定義可知(g,m=1,再根據(jù)逆元存在定理可得:g的逆元q存在,即g q1m odm。設(shè)l為整數(shù)、(m為m的歐拉函數(shù),根據(jù)同余性質(zhì)由g(m1m od m可得:g(mq l=q l m od m,即g(m-l(g qlq l m od m,進(jìn)一步化簡(jiǎn)得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因?yàn)間是m的原根,所以g,g2,g3,g(m是m的一組縮系,即g,g2,g3,g(m兩兩不同余,所以q,第26卷第5期2004年10月電氣

7、電子教學(xué)學(xué)報(bào)JOU RNAL O F EEEV o l.26N o.5O ct.2004收稿日期:2004-02-15;修回日期:2004-09-02第一作者:王正彥(1965-,女,山東省青島人,研究生,副教授,從事數(shù)字信號(hào)處理和電子技術(shù)應(yīng)用方面的教學(xué)科研工作。q 2,q 3,q(m 兩兩不同余,即q ,q 2,q 3,q (m 也是m 的一組縮系,根據(jù)原根存在定理得,q 是m 的原根,定理得證。2D FT 的循環(huán)卷積算法1求解原根若已知g 是m 的原根,則可以通過(guò)求解g 的逆元q 的方法,求得m 的另一個(gè)原根。表1例舉了m =5、7、41的情況。表1原根對(duì)舉例357152419292830

8、352D FT 的循環(huán)卷積算法設(shè)x (n 是長(zhǎng)度為N 的有限長(zhǎng)序列,則其N 點(diǎn)D F T 的表達(dá)式為X (k =N -1n =0x (n Wnk N 。對(duì)于k =0,X (0=N -1n =0x (n ,對(duì)于k =1,2,N -1,可寫(xiě)成X (k =x (0+N -1n =1x (n W nkN。設(shè)N 為素?cái)?shù),Z N 為N 的數(shù)環(huán),g 為Z N 上的一個(gè)原根,則其逆元q =g -1亦為其原根。將k ,n =1,2,N -1通過(guò)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 則上式變?yōu)閄 (k =x (0+N -2n =0x (n W (k -n (3即X (k =x (0+x (n W (n (4故此將D FT 運(yùn)算轉(zhuǎn)換成循環(huán)卷積運(yùn)算。3用FPGA 實(shí)現(xiàn)D FT 循環(huán)卷積算法以N =5為例,則g =2及其逆元q =3均為Z 5的原根,故k 的新排

10、序(20,21,22,23m od 5=(1,2,4,3n 的新排序?yàn)?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寫(xiě)成矩陣形式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 是一個(gè)循環(huán)矩陣,即每一行都是前一行循環(huán)左移的結(jié)果。上式的結(jié)構(gòu)圖如圖1。輸入按照x (3,x (4,x (2,x (1的順序輸入,輸出按照X (1,X (2,X (4,X (3的順序輸出。此為一轉(zhuǎn)置結(jié)構(gòu)的F I R 濾波器。圖1循環(huán)卷積算法結(jié)構(gòu)圖實(shí)現(xiàn)上述算法時(shí),應(yīng)首先對(duì)系數(shù)W k 5進(jìn)行量化。假定輸入值和系數(shù)都被表示成8位有符號(hào)數(shù),量化后的系數(shù)如表2所列:表2量化系數(shù)表k 01234R e (256W k s 25679-207-20779I m (256W k

12、 s 氣電子教學(xué)學(xué)報(bào)26卷將圖1所示算法用V HDL語(yǔ)言實(shí)現(xiàn)的程序:PA CKA GE B bit int IS自定義程序包SUBT YPE W ORD8IS I N T EGER RAN GE-2337TO23 37-1;定義數(shù)據(jù)類型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;庫(kù)的使用和說(shuō)明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實(shí)體POR T(clk:I N STD LO G I C;端口說(shuō)明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結(jié)構(gòu)體S IGNAL count:integer RAN GE0TO11;定義信號(hào),時(shí)鐘計(jì)數(shù)器T YPESTA T E T YPE IS(Start,L oad,R un;S IGNAL state:STA T E T YPE;狀態(tài)變量S IGNAL accu:W ORD11;X(0 S IGNAL real,i m ag:A RRA Y W ORD;濾波器抽頭延遲線實(shí)部,虛部S IGNAL x79,x207,x243,x150:W ORD19;濾波器系數(shù)S IGNAL x5,x25,x7,x125,x256:W ORD19;濾波器輔助系數(shù)S IGNAL x,x0:W ORD8;x(n,

15、x(0 BEG I NStates:PROCESS狀態(tài)機(jī)BEG I NW A IT UN T I L clk=1;CA SE state ISW H EN Start=>初始狀態(tài)state<=L oad;count<=1;x0<=x in;下載并保存x(0accu<=0;y real<=0;y i m ag<=0;W H EN L oad=>下載狀態(tài)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=>運(yùn)行狀態(tài)IF count=11TH ENy real<=accu;輸出X(0y i m ag<=0;state<=Start;EL SEy real<=real(0 256+x0;輸出X實(shí)部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轉(zhuǎn)置結(jié)構(gòu)F I R濾波器(實(shí)部和虛部 BEG I NW A IT UN T I L clk=1;x<=x in;下載輸入

17、real(0<=real(1+x79;計(jì)算X(k的實(shí)部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;計(jì)算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求濾波器系數(shù),實(shí)現(xiàn)乘法器模塊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求濾波器輔助系數(shù)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 進(jìn)行仿真,選用EPF10K10L C84-4型FPGA器件,并設(shè)x(n=7

19、4第26卷第5期王正彥等:D FT的循環(huán)卷積算法推導(dǎo)及其FPGA實(shí)現(xiàn) (10,20,30,40,50,結(jié)果如圖2所示。其中x in 即x (n ,按照x (0,x (3,x (4,x (2,x (1的順序輸入。y rea l 和y i m ag 分別為X (k 的實(shí)部和虛部,按照X (1,X (2,X (4,X (3,X (0的順序輸出。需要說(shuō)明的是在M axp lu s 中負(fù)數(shù)是以補(bǔ)碼的形式顯示的,即2023實(shí)為-25,2013為-35,2039為-9,故由仿真結(jié)果可得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進(jìn)行手工計(jì)算所得結(jié)果是完全一致的 。圖2仿真結(jié)果4結(jié)論綜上所述可以得到如下結(jié)論:(1原根是成對(duì)存在的,即若g 為m 的原根,則其逆元q 亦為m 的原根。(2利用原根可將數(shù)環(huán)重新排序,將此理論用于D FT ,可推導(dǎo)出D FT 的循環(huán)卷積算法,將該算法用V HDL 語(yǔ)言實(shí)現(xiàn)并將程序下載至FPGA 中,其意義在于可用FPGA 實(shí)現(xiàn)D SP 的重要內(nèi)容之一D FT 運(yùn)算,而FPGA 實(shí)現(xiàn)D SP 的優(yōu)勢(shì)在于速度快。參考文獻(xiàn):1Uw e M eyer 2Baese 著1數(shù)字信號(hào)處理的FPGA 實(shí)現(xiàn)(劉凌等譯M 1北京:清華大學(xué)出版社,20032裴定一,祝躍飛1算法數(shù)論M 1北京:科學(xué)出版社,20023胡廣書(shū)1D FT 和卷積的快速算