文档库 最新最全的文档下载
当前位置:文档库 › 二维FFT在TMS320系列DSP中的实现

二维FFT在TMS320系列DSP中的实现

二维FFT在TMS320系列DSP中的实现
二维FFT在TMS320系列DSP中的实现

二维FF T在TMS320系列DSP中的实现

董 晖,姜秋喜,毕大平

(电子工程学院,安徽合肥230037)

摘 要:分析了二维FF T的快速算法,提出了在TMS320C6701评估板上的高速

实现方法,通过实验验证了该方法,并讨论了在多片DSP上的并行实现方法。

关键词:信号处理;二维FF T;DSP;直接存储器访问(DMA);并行实现

中图分类号:TN91117 文献标识码:A 文章编号:100920401(2002)0120034205

Implementation of Two2dimensional FF T in TMS320DSP

DON G Hui,J IAN G Qiu2xi,B I Da2ping

(Elect ronic Engi neeri ng Instit ute,Heif ei230037,Chi na)

Abstract:The algorithm of two2dimensional FF T is analyzed in this paper.The fast realization by TMS320DSP is given and the results are proved by experiments.The parallel realization by mul2 tiple DSP is given.

K ey w ords:signal processing;two2dimensional FF T;DSP;Direct Memory Access(DMA);paral2 lel realization

1 引 言

二维FF T在图像处理场合有着广泛的应用,可以利用它来快速实现图像相关和卷积。二维FF T在信号处理的其它领域也得到了越来越多的应用,例如在对周期平稳信号的处理中,可以通过对自相关函数作二维FF T来求得周期谱密度函数从而进行特征提取。但是二维FF T运算量大,使用通用的微处理器实现二维FF T难以满足信号实时处理的要求,而DSP适合大数据量运算,将二维FF T和DSP相结合使得二维FF T具有很强的可实现性。

2 二维FF T

二维序列x(m,n)的二维傅里叶变换(22D F T)定义为

X(e jω1,e jω2)=6∞m=-∞6∞n=-∞x(m,n)e-jmω1e-jnω2(1) 如x(m,n)是在(m,n)平面上(0≤m≤M-1,0≤n≤N-1)有限区域内的非零的二维收稿日期:2001207209;修订日期:2002201221

作者简介:董晖(1971-),男,甘肃兰州人,合肥电子工程学院硕士研究生在读,主要从事信号处理研究。

序列,则x (m ,n )的二维离散傅里叶变换(22D DF T )定义为

X (k ,l )=

6M -1m =06N -1n =0x (m ,n )W mk N W nl

N (k =0,1,2,…,M -1;l =0,1,2,…,N -1)(2)

由上式不难看出,二维FF T 可通过作两次一维FF T 实现,即先作N 点的FF T

A (m ,l )=

6N -1

n =0x (m ,n )W nl N (m =0,1,2,…,M -1;l =0,1,2,…,N -1)(3)

接着作M 点的FF T

X (k ,l )=

6M -1

m =0A (m ,l )W mk M (k =0,1,2,…,M -1;l =0,1,2,…,N -1)(4)

若M 和N 均为2的整数幂,采用基2FF T 算法,那末总共需要

M N

2log 2N +N M

2log 2M =N M

2log 2(N M )

次复数乘法。直接用二维DF T 计算,则需要N 2M 2次复数乘法。显然,这种算法可以显著减少运算量,提高运算速度。

存储量大也是计算二维FF T 的主要困难,对于N M 个复数输入信号需要2N M 个实数存储器。如N =M =256,则需要131072个存储器。在使用DSP 实现二维FF T 时同样存在这一问题,使用DSP 芯片片内集成的存储器无法满足运算的需要,因此必须使用片外存储器,但直接访问片外存储器的时间比访问片内存储器的时间要长的多,为此可以采用直接存储器访问(DMA )方式在片内存储器和片外存储器之间交换数据以解决数据交换的瓶颈问题,提高运算速度。

图1 在单片DSP 上实现二维FF T 的流程图

3 二维FF T 在单片DSP 上的应用

下面以TI 公司的TMS320C6701评估板(EVM )为

例介绍二维FF T 在单片DSP 上的应用。C6701EVM 上

有一个C6701DSP ,集成了两条1M ×32bit 、100MHz 的

SDRAM 。需要处理的数据存放在这两条SDRAM 内,

使用这两条存储空间一次可以完成1024×1024点的复

数二维FF T 。该算法的流程如图1所示。该算法主要

有以下特点。

311 使用DMA 完成片内与片外数据的交换

C6701EVM 的片外存储空间大,可以存放大量数据

及中间结果,但其访问速度慢,访问时间约为访问片内

存储器的16倍。片内存储空间小,但访问速度快可以

高速实现小数据量的FF T ,其完成1024点的定点复数

FF T 仅需要108μs 。为此我们把需要处理的二维数据放在片外存储器,在片内存储器完成一维FF T ,利用DMA 方式实现片内存储器和片外存储器之

间的数据交换。

DSP 的DMA 控制器,可以在没有CPU 参与的情况下完成映射存储空间的数据搬移。C6701的DMA 控制器有四个相互独立的可编程传输通道和一个用来满足主机口需要的辅助通道。这四个通道的优先级不同,通道0最高,通道3最低。由于一维FF T 采用原位运算,因此必须先将上一次的处理结果读出才能将下一次的待处理数据写入,我们使用通道0完成从片内存储器到片外存储器的数据读出,通道1完成从片外存储器到片内存储器的数据写入,由于通道0的优先级高于通道1,这样就可以确保数据是先读出后写入的。

每一个DMA 通道的控制都是由一组相关的寄存器完成传输控制的,在使用前需要向相关的寄存器写入控制字进行初始化,初始化完成后向DMA 主控制寄存器STAR T 域写入01b 就可以立即启动该通道的DMA 。启动是在程序中完成的,在进行每一次一维FF T 前启动DMA 这样就可以在运算的同时完成数据的搬移。

312 使用乒乓缓冲技术在完成一维FFT 的同时并行实现数据搬移

图2 乒乓缓冲示意图

使用DMA 通道可以在CPU 后台传输数据,但

如果一维FF T 和DMA 同时访问相同的片内存储器

的时候就会产生冲突,为避免这种情况发生我们使

用了如图2的乒乓缓冲技术。

一维FF T 采用数据长度为16bit 的定点算法,一

维FF T 在C6701的片内存储器上进行,在片内数据

存储器开辟两个数据缓冲区,分别是FftBuffA 和

FftBuffB ,每个的最大长度为1K ×32bit ;二维数据存

放在片外的SDRAM 内,也开辟两个数据缓冲区,分

别是InputBuff 和OutputBuff ,每个的最大长度为1M ×32bit 。当对FftBuffA 的数据作FF T 运算的同时,通过DMA 控制器首先将上一次FF T 运算的结果从FftBuffB 写到OutputBuff ,,然后再将下一次FF T 所需要的数据从InputBuff 写到FftBuffB 。这样当这一次FF T 运算结束时下一次FF T 的数据也已经准备好了,作下一次FF T 的时候就可以把这一次FF T 的结果读出并且为再下一次FF T 准备数据,完成一维FF T 的同时并行实现了数据搬移。

通过实验证明,将DMA 和乒乓缓冲技术相结合可以最大限度的发挥DSP 器件的效能,完成1024×1024点数据的二维FF T 仅需要777.940ms ,平均每次一维FF T 的时间为0.109ms ,而直接访问片外存储器则需要9264.245ms ,所需时间是前一种方式的12倍。

表 DMA 和乒乓缓冲二维FF T 与直接访问片外存储器二维FF T 执行时间二维数组大小

DMA 和乒乓缓冲方式(ms )直接访问片外存储器方式(ms )总时间一维FFT 平均时间总时间一维FFT 平均时间64×64

2.7480.01126.7120.078256×256

41.5880.033493.0000.4091024×1024777.9400.1099264.245 2.184

313 非原位转置

对二维输入数据的每一行作完一维FF T将结果存储在OutputBuff后就需要对中间结果的每一列作一维FF T,为了便于DMA访问,我们对中间结果作了一次非原位转置,转置后的结果存放在InputBuff内。采用非原位转置的速度大大快于原位转置,编程实现也较简单,在存储空间许可的情况下应尽量采用这种方法。同时,在转置的过程中使用字访问技巧,考虑到数据在存储器内是按实部虚部的顺序存放的,在转置时用对一个32bit数的访问代替对两个16bit数的访问,节省一半的数据访问时间。

4 二维FF T在多片DSP上的并行实现

单片DSP实现二维FF T虽然取得了较好的效果,但仍难满足一些对实时性要求较高的场合,随着多处理器芯片TMS320C4x及TMS320C8x的出现,在多片DSP上实现二维FF T 成为可能,从而满足更高的实时性要求。C40的时钟周期为40到50ns,每个时种周期最多可以同时执行11条指令,其内部集成的6个通讯口可以实现处理器和处理器之间的无缝连接,1个多通道DMA提供了并行I/O功能。C80是一个多处理器芯片,它包括一个主处理器(MP)、4个C40、一个传输控制器(TC)和一个视频控制器(VC)。各个处理器之间通过交叉网和共享内存系统紧紧连接在一起。这两种DSP都十分有利于处理的并行化,可以开发出基于它们的二维FF T并行实现方法。

411 共享式存储器的实现方法

图3给出一个共享存储器二维FF T在4片DSP上的实现方法。图中,二维数组A储存在全局存储器中,每个DSP都可访问所有的行和列,在同一时刻不同的DSP访问全局存储器不同的行和列,其程序流程与单片DSP时相同,片内数据和片外数据的交换也是由DMA方式实现的,不同的就是用多片DSP来完成各行或列的一维FF T。该方式实现起来较为简单,但由于所有DSP共享存储器,当几个DSP同时访问全局存储器会出现数据瓶颈。

图3 共享式存储器实现二维FF T示意图(图中二维数组为8

行8列共64个元素,所标数字为二维数组元素的下标)

412 分布式存储器的实现方法

图4给出了一个分布式存储器二维FF T在4片DSP上的实现方法。如图所示,DSP0~DSP3按照超立方体拓扑结构互相连接,二维数组A被分割为A0~A3四个部分分别存放在各

行8列共64个元素,所标数字为二维数组元素的下标)

个处理器的本地存储器内,其程序流程与单片DSP时相同,第一步和第三步都是在本地存储器内完成的。其最大的不同点是二维数组的转置较为复杂,因为整个二维数组分布在不同的存储器内,其转置要按分块矩阵的转置方法来实现,首先,各DSP之间按照分块矩阵的转置要求进行块交换,与单片时的情况类似这一步可以用DMA在运算的同时并行实现数据交换;其次,再将每个DSP内的的分块矩阵分别转置,这样就完成了整个二维数组的转置。分布式存储器没有数据瓶颈问题,但编程实现比较复杂,并受到单片DSP存储器大小的限制。

5 结束语

本文讨论了在单片和多片DSP上实现二维FF T的方法,通过实验证明在单片DSP上的实现方法是有效的,能较好的满足二维数据处理的要求。

参考文献:

[1] 任丽香,马淑芬,李方慧.TMS320C6000系列DSPs的原理与应用[M].北京:电子工业出版社,2000.

[2] 陈昌灵.数字信号处理[M]1上海:华东师范大学出版社,1992.

[3] TMS320C6x Peripheral Support Library Programmer’s Reference[M].Texas Instruments Incorporated,

19991

[4] TMS320C6201/6701Evaluation Module Technical Reference[M].Texas Instruments Incor porated,

1999.

[5] TMS320C4x User’s Guide[M].Texas Instruments Incorporated,1991.

[6] TMS320C62x DSP Library Programmer’s Reference[M].Texas Instruments Incorporated,2000.

[7] Parallel22D FFT Implementation with TMS320C4x DSPs[M].Texas Instruments Incorporated,1994.

相关文档