DFT的循环卷积算法推导及其FPGA实现.docx
《DFT的循环卷积算法推导及其FPGA实现.docx》由会员分享，可在线阅读，更多相关《DFT的循环卷积算法推导及其FPGA实现.docx（14页珍藏版）》请在冰点文库上搜索。
DFT的循环卷积算法推导及其FPGA实现
DFT的循环卷积算法推导及其FPGA实现
王正彦,范延滨,徐茂荣
（青岛大学,山东青岛266071
摘 要:
首先提出了数论中的原根成对存在定理,并进行了详细的数学证明。
然后根据原根可使数环重新排序的性质,利用一对原根对DFT运算的输入和输出序列重新排序,推导出DFT的循环卷积算法,进一步给出了此算法的结构图。
最后给出了用VHDL语言实现该算法的完整程序、仿真结果及分析,并总结了用FPGA实现DFT运算的意义。
关键词:
原根;DFT;FPGA;循环卷积
中图分类号:
TN911172 文献标识码:
A文章编号:
1008-0686（200405-0045-04
AlgorithmDesignandFPGARealizationofConvolutionDFT
WANGZheng-yan1,FANYan-bin2,XUMao-rong1
（1.CollegeofAutomationEngineering,QingdaoUniversity,Qingdao266071,China;
2.CollegeofInformationEngineering,QingdaoUniversity,Qingdao266071,China
Abstract:
Inthispaper,atheoremofprimaryrootexistsasacoupleintheNumberTheorywassuggested,anddetailedmathematicproofwasgiven.BasedonthecharacterofprimitiverootcanreorderthenumberringandusingthetwoprimaryroottoreordertheinputandoutputsequencesoftheDFTcomputation,aalgorithmofDFTcyclicconvolutionwasdeductedandfurtherstructurediagramwasgiven.Attheend,acompleteprogramwritteninVHDLlanguageforthisalgorithm,thesimulatingresultandanalysisaregiv2en.TheimportanceofachievingtheDFTcomputationbyusingFPGAwassummarized.
Keywords:
primitiveroot;DFT;FPGA;circleconvolutionintegral
笔者在从事数论变换研究和FPGA的设计过程中,发现对于DFT的循环卷积算法推导,如果能够采用原根及其逆元（也是原根对输入输出序列进行重新排序,其推导过程将进一步简化。
由此提出原根成对存在定理,并给出了严格证明,最后给出了FPGA的设计和实现。
原根成对存在定理不仅有益于数论变换,而且可以应用于原根的研究。
1 原根成对存在定理
定理 设m、g均为整数,且m>g>0,若g是
m的原根,则g的逆元q存在,且q也是m的原根。
证明 由原根的定义可知（g,m=1,再根据逆元存在定理可得:
g的逆元q存在,即gq≡1mod
m。
设l为整数、Υ（m为m的欧拉函数,根据同余性质由gΥ（m≡1modm可得:
gΥ（mql=qlmodm,即
gΥ（m-l（gql≡qlmodm,进一步化简得gΥ（m-l≡qlmodm。
取0ΦlΦΥ（m,则可得
q≡gΥ（m-lmodm
q2≡gΥ（m-2modm
……
qΥ（m-1≡gmodm
qΥ（m≡1modm（1因为g是m的原根,所以g,g2,g3,…,gΥ（m是m的一组缩系,即g,g2,g3,…,gΥ（m两两不同余,所以q,
第26卷 第5期2004年10月
电气电子教学学报
JOURNALOFEEE
Vol.26 No.5
Oct.2004
收稿日期:
2004-02-15;修回日期:
2004-09-02
第一作者:
王正彦（1965-,女,山东省青岛人,研究生,副教授,从事数字信号处理和电子技术应用方面的教学科研工作。
q2,q3
…,q
Υ（m两两不同余,即q,q2,q3,…,qΥ（m
也是m的一组缩系,根据原根存在定理得,q是m的原根,定理得证。
2 DFT的循环卷积算法
1求解原根
若已知g是m的原根,则可以通过求解g的逆元q的方法,求得m的另一个原根。
表1例举了m=5、7、41的情况。
表1 原根对举例
m5741g23611121317222634q
3
5
7
15
24
19
29
28
30
35
2DFT的循环卷积算法
设x（n是长度为N的有限长序列,则其N点
DFT的表达式为X（k=
∑N-1
n=0
x（nW
nkN。
对于k=0,
X（0=
∑N-1
n=0
x（n,对于k=
1,2,…,N-1,可写成
X（k=x（0+
∑
N-1
n=1
x（nWnk
N
。
设N为素数,ZN为N的数环,g为ZN上的一个原根,则其逆元q=g-1亦为其原根。
将k,n=1,2,
…,N-1通过gk’模N和gn’
模N重新排序,即用gk′modN和qn′
modN（k′
n′=
0,1,…,N-1代替k和n得
X（gk′
modN=
x（0+
∑
N-2
n′=0
x（qn′
modNW
（qn′modN（gk′
modNN
即
X（gk′
modN=x（0+
∑
N-2
n′=0
x（qn′
modNW
g
k′-n′
modN
N
（2
若定义
X′
（K′=X（gk′
modNx′（n′=x（qn′
modNW′
（n=Wg
n
N则上式变为
X′
（k′=x（0+∑N-2
n′=0
x′
（n′W′（k′-n′
（3即 X′
（k′=x（0+x′（n′W′（n′（4故此将DFT运算转换成循环卷积运算。
3 用FPGA实现DFT循环卷积算法
以N=5为例,则g=2及其逆元q=3均为Z5
的原根,故k的新排序
（20,21,22,23mod5=（1,2,4,3
n的新排序为
（30,31,32,33mod5=（1,3,4,2
X（2k′
mod5=x（0+
∑
3
n′=0
x（3n′
mod5W
（2n′mod5（3k′
mod55
写成矩阵形式
X（1
X（2X（3X（4=W15W3
5W45W25W25W15W35W45W4
5
W25W15W35W3
5
W
45
W
25
W
15
x（1x（3x（4x（2
+
x（0
x（0x（0x（0
（5
交换W矩阵的第2列和第4列,得
X（1
X（2X（3X（4=W15W25W45W3
5W25W45W35W1
5W45W35W15W2
5W35W15W25W4
5x（1x（2x
（4x
（3
+
x（0x（0x（0x（0
（6
W是一个循环矩阵,即每一行都是前一行循环
左移的结果。
上式的结构图如图1。
输入按照x（3,
x（4,x（2,x（1的顺序输入,输出按照X（1,X（2,X（4,X（3的顺序输出。
此为一转置结构的FIR滤波器。
图1 循环卷积算法结构图
实现上述算法时,应首先对系数Wk5进行量化
。
假定输入值和系数都被表示成8位有符号数,量化后的系数如表2所列:
表2 量化系数表
k01234Re（256Wks25679-207-20779Im（256Wks
-243
-150
150
243
6
4 电气电子教学学报 26卷
将图1所示算法用VHDL语言实现的程序:
PACKAGEBbitintIS——自定义程序包SUBTYPEWORD8ISINTEGERRANGE-2337TO2337-1;——定义数据类型SUBTYPEWORD11ISINTEGERRANGE-23310TO23310-1;
SUBTYPEWORD19ISINTEGERRANGE-23318TO23318-1;
TYPEARRAYWORDISARRAY（0to3OFWORD19;ENDBbitint;
LIBRARYwork;——库的使用和说明USEwork.Bbitint.ALL;
LIBRARYieee;
USEieee.stdlogic1164.ALL;
USEieee.stdlogicarith.ALL;
USEieee.stdlogicunsigned.ALL;
ENTITYrader5IS——实体PORT （clk :
INSTDLOGIC;——端口说明xin :
INWORD8;
yreal,yimag :
OUTWORD11;
ENDrader5;
ARCHITECTUREflexOFrader5IS——结构体
SIGNALcount :
integerRANGE0TO11;
——定义信号,时钟计数器TYPE STATETYPEIS（Start,Load,Run;
SIGNALstate:
STATETYPE;
——状态变量SIGNALaccu:
WORD11;——X（0SIGNALreal,imag:
ARRAYWORD;
——滤波器抽头延迟线实部,虚部SIGNALx79,x207,x243,x150:
WORD19;——滤波器系数SIGNALx5,x25,x7,x125,x256:
WORD19;
——滤波器辅助系数SIGNALx,x0:
WORD8;——x（n,x（0BEGIN
States:
PROCESS——状态机BEGIN
WAITUNTILclk=’1’;
CASEstateIS
WHENStart=>——初始状态 state<=Load;
count<=1;
x0<=xin;——下载并保存x（0 accu<=0;
yreal<=0;
yimag<=0;
WHENLoad=>——下载状态 IFcount=6THEN
state<=Run;
ELSE
state<=Load;
accu<=accu+x;——求解X（0 ENDIF;
count<=count+1;
WHENRun=>——运行状态 IFcount=11THEN
yreal<=accu;——输出X（0 yimag<=0;
state<=Start;
ELSE
yreal<=real（0256+x0;——输出X实部 yimag<=imag（0256;——输出X虚部 state<=Run;
ENDIF;
count<=count+1;
ENDCASE;
ENDPROCESSStates;
Structure:
PROCESS——转置结构FIR滤波器（实部和虚部BEGIN
WAITUNTILclk=’1’;
x<=xin;——下载输入real（0<=real（1+x79;
——计算X（k的实部real（0（不包括x（0real（1<=real（2-x207;
real（2<=real（3+x79;
real（3<=-x207;
imag（0<=imag（1-x243;——计算X（k的虚部imag（0
imag（1<=imag（2-x150;
imag（2<=imag（3+x243;
imag（3<=x150;
ENDPROCESSStructure;
Coeffs:
PROCESS——求滤波器系数,实现乘法器模块BEGIN
WAITUNTILclk=’1’;
x79<=x2532+x25+x34;
x207<=x2538+x7;
x243<=x12532-x7;
x150<=x2534+x2532;
ENDPROCESSCoeffs;
Factors:
PROCESS（x,x5,x25——求滤波器辅助系数BEGIN
x5<=x34+x;
x7<=x5+x32;
x25<=x534+x5;
x125<=x2534+x25;
x256<=x3256;
ENDPROCESSFactors;
ENDflex;
用EDA软件Maxplus进行仿真,选用EPF10K10LC84-4型FPGA器件,并设x（n=
74
第26卷第5期 王正彦等:
DFT的循环卷积算法推导及其FPGA实现
（10,20,30,40,50,结果如图2所示。
其中xin即
x（n,按照x（0,x（3,x（4,x（2,x（1的顺序输
入。
yreal和yimag分别为X（k的实部和虚部,按照X（1,X（2,X（4,X（3,X（0的顺序输出。
需要说明的是在Maxplus中负数是以补码的形式
显示的,即2023实为-25,2013为-35,2039为-9,故由仿真结果可得X（k=（150,-25+j34,-25+j8,-25-j9,-25-j35,这与按X（k=
∑N-1
n=0
x（nW
nkN
进行手工计算所得结果是完全一致的
。
图2 仿真结果
4 结论
综上所述可以得到如下结论:
（1原根是成对存在的,即若g为m的原根,则其逆元q亦为m的原根。
（2利用原根可将数环重新排序,将此理论用于DFT,可推导出DFT的循环卷积算法,将该算法用VHDL语言实现并将程序下载至FPGA中,其意义
在于可用FPGA实现DSP的重要内容之一——
DFT运算,而FPGA实现DSP的优势在于速度快。
参考文献:
[1] UweMeyer2Baese著1数字信号处理的FPGA实现（刘凌等
译[M]1北京:
清华大学出版社,2003
[2] 裴定一,祝跃飞1算法数论[M]1北京:
科学出版社,2002[3] 胡广书1DFT和卷积的快速算法[M]1清华大学电机工程与
应用电子技术系讲义,1993
（上接第29页颜彪等文
中频信号首先被直接采样,然后分成上下两路,
一路信号经过希尔伯特变换网络,另一路信号经过延迟单元（以保证信号的同步,从而得到一对正交数字信号。
该方法的数字化程度较高,易于用FPGA器件实现[4]。
实际应用中,希尔伯特变换通常采用半带滤波器（Half2BandFilter,HBF和级联积分梳状滤波器（CascadedIntegrator2CombFilter,CICF来实现。
4 结束语
希尔伯特变换可以提供90°的相位变化而不影响频谱分量的幅度大小,如果采用数字方式,即离散希尔伯特变换则可产生具有高平衡度I-Q信道,因此,它被广泛应用于通信、雷达、语音处理、数字化
医学超声成像等这类需要用到信号正交分解技术的
系统中。
本文分别从希尔伯特变换的定义、实现及其应用等方面进行了详细阐述,希望能给电子通信专业的学生或有关技术人员提供帮助。
参考文献:
[1] JamesTsui著1宽带数字接收机[M]1杨小牛,陆安南,金飚
译,北京:
电子工业出版社,200:
174-180
[2] 何正权,何旭1多次采样与希尔伯特变换[J]1成都:
电子科技
大学学报,1997,26（5:
504-510
[3] 李晶晶,江桦,王明坤1希尔伯特变换在信号解调中的应用
[J]1郑州:
信息工程大学学报,2002,3（4:
29-31
[4] 黄英,李景文,刘敏1软件无线电技术在中频接收机中的应用
[J]1北京:
无线电通信技术,2004,30（1:
18-20
8
4 电气电子教学学报 26卷
升级会员 