（通信与信息系统专业论文）dtmb系统基带处理算法与实现.pdf

摘要 本文针对中国数字电视地面广播标准( d t m b ) 研究与设计数字电视传输 系统中的发射端与接收端的基带处理模块，并且探讨多载波系统和单载波系统 的融合设计方案。论文首先采用m a t l a b 仿真、分析基带数据处理算法并完 成系统设计。然后，采用q u a r t u si i 软件综合、仿真基于f p g a 的硬件电路设 计。 基带处理是数字电视传输系统中的重要组成部分，本文详细介绍了发射端 基带和接收端基带数据处理的算法与实现。其中，发射端的设计着重介绍前向 纠错码内码( q c l d p c ) 的编码实现，基于s d r a m 的卷积交织实现，多载波 系统的子载波映射i f f t 实现，以及s r r c 的设计与实现。接收端主要技术难点 是：同步算法与实现，单载波与多载波各自信道估计与均衡的算法与实现， b c h 码与q c l d p c 码的译码实现。同时介绍了d t m b 系统中采用的非线性编 码( n r 码) 的编译码实现方法。系统设计阶段的仿真平台采用c t 8 、t u 等 r a y l e i g h 信道模型。 本文基于d t m b 单载波与多载波系统的融合方案，提出融合技术实现的优 化方案。在完成基本功能模块设计的基础上，为各模块提出了有利于节省硬件 资源、减小功耗、加快数据处理速率的优化实现方案。 关键词：t d s o f d m ，同步，信道估计，均衡，q c l d p c ，n r 码 a b s t r a c t t h i sp a p e rd e s c r i b e dt h ea l g o r i t h ma n dd e s i g no ft h eb a s e b a n dd a t ap r o c e s s i n go f d i g i t a lt e l e v i s i o nt r a n s m i s s i o ns y s t e mb a s e do nc h i n e s ed i g i t a lt e l e v i s i o nt e r r e s t r i a l b r o a d c a s t i n gs t a n d a r d ，a n ds u p p l i e d a l l i n t e g r a t i o ns c h e m eo fs i n g l e c a r r i e r m o d u l a t i o ns y s t e ma n dm u l t i c a r r i e rm o d u l a t i o ns y s t e m t h es i m u l a t i o nr a no nt h e m a t l a b ，t oa n a l y z et h ed a t ap r o c e s s i n ga l g o r i t h ma n do p t i m i z et h es y s t e md e s i g n s c h e m e f i n a l l y ，t h es y s t e mw a sr e a l i z e do nf p g aa f t e rs y n t h e s i z e d ，c o m p i l e da n d s i m u l a t e di nt h eq u a r t u si i t h eb a s e b a n dd a t ap r o c e s s i n gi st h em o s ti m p o r t a n tp a r to ft h ed i g i t a lt e l e v i s i o n t r a n s m i s s i o ns y s t e m t h i sp a p e rd e s c r i b e dt h ed e s i g no ft r a n s m i t t e ra n dt h ea l g o r i t h m a p p l i e di n r e c e i v e r s y s t e md e t m l e d l ya n dr e s p e c t i v e l y t h ee m p h a s e s o ft h e t r a n s m i t t e ri st h ei m p l e m e n t a t i o no ft h ef o r w a r de r r o rc o r r e c t i n gc o d 川c l d p c e n c o d i n g ，t h ei m p l e m e n t a t i o no fi n t e r l e a v e rb a s e do ns d r a m ，t h ed e s i g n a n d i m p l e m e n t a t i o no fs q u a r er o o tr a i s ec o s i n ef i l t e r ，a n dt h ei m p l e m e n t a t i o no ff f t u s e di nt h ec a r r i e rm a p p i n go fm u l t i c a r r i e rm o d u l a t i o n t h ek e yp o i n to ft h er e c e i v e r i st h ea l g o r i t h mu s e di nt h es y n c h r o n i z a t i o n , t h er e s e a r c ho fa l g o r i t h mu s e di nt h e e s t i m a t i o na n de q u a l i z a t i o no fb o t ht h es i n g l ec a r r i e rs y s t e ma n dt h em u l t i c a r r i e r s y s t e m ，a n dt h ei m p l e m e n t a t i o no fb c hd e c o d i n ga n dq c - l d p cd e c o d i n g i n a d d i t i o n ，t h i sp a p e rd e s c r i b e dt h ei m p l e m e n t a t i o no ft h ee n c o d i n ga n dd e c o d i n go f n o n l i n e a rc o d e 寸、r ( n o r d s t o r mr o b i n s o n ) c o d ew h i c hu s e di nt h ed t m bs y s t e m a tt h es t a g eo fs y s t e md e s i g n ，t h es i m u l a t i o nw a sb a s e do nr a y l e i g hc h a n n e lm o d e l ， s u c ha sc t 8 ，t um o d e l t h i sp a p e rd i s c r i b e dt h ei n t e g r a t i o ns c h e m eo fs i n g l ec a r r i e rm o d u l a t i o ns y s t e m a n dm u l t i c a r r i e rm o d u l a t i o ns y s t e m ，t h e np r o p o s e dt h ec o m b i n i n gm e t h o da n d o p t i m i z e ds c h e m e u p o nc o m p l e t i o no ft h eb a s i cf u n c t i o n a lm o d u l a rd e s i g n ，t h i s p a p e rp r o p o s e dt h eo p t i m i z a t i o no f h a r d w a r ed e s i g n ，w h i c hw o u l dh e l ps a v eh a r d w a r e r e s o u r c e ，r e d u c ep o w e rc o n s u m p t i o na n ds p e e du pt h ed a t a p r o c e s s i n g k e y w o r d s ：t d s o f d m ，s y n c h r o n i z e ，e s t i m a t e ，e q u a l i z e ，q c l d p c ，n r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外。论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得丞洼太堂或其他教育机构的学位或 证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意。 靴敝储獬：王婶锢飙1 引舰 学位论文版权使用授权书 本学位论文作者完全了解丞婆拦有关保留、使用学位论文的规定。 特授权云洼太堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者躲丕弋聿新繇痧l 群 辩醐：呷拥塑磐醐：竹钥n 刖舌 电视产业和事业的发展一直以提高收视质量与服务能力为中心，其中作为 新一代的电视技术的数字电视，因其收视质量可大幅度提高并可为更多的新兴 业务创造发展空间而备受关注。 数字电视( d t v ，d i g i t a lt e l e v i s i o n ) 是指从电视节目采集、录制、播出到 发射、接收全部采用数字编码技术的新一代电视，是在数字技术基础上把电视 节目转换成为数字信息，以码流形式进行传播的电视形态，综合了数字压缩、 多路复用、纠错掩码、调制解调等多种先进技术。 2 0 0 6 年，全国数字电视产业从初期导入阶段过渡到全面启动和快速发展阶 段，全国各地区相继开展数字电视整体转换工作，数字电视用户增长迅速。 2 0 0 8 年是中国数字电视产业全面发展的一年，有线数字电视继续向高峰推进， 地面数字电视正式实施，奥运会采用地面高清信号免费向全世界转播，卫星直 播开始进入产业培育期：数字电视的投融资政策进一步放开、机卡分离体制逐 步开始实行，数字电视产业化进程加快 1 】。 数字电视地面广播系统是国家广播电视技术体系的重要组成部分。2 0 0 6 年 8 月，由国家组织的数字电视特别工作组负责起草具有自主知识产权的中国数 字电视地而广播传输标准【2 】，数字电视地面广播传输系统帧结构、信道编码 和调制( 地面数字电视多媒体广播，d i g i m lt e r r e s t r i a lm u l t i m e d i a b r o a d c a s t i n g ，d t m b ) ，经全国广播电视标准化技术委员会审查，由国家标准 化管理委员会正式批准成为强制性国家标准，于2 0 0 7 年8 月1 日正式强制实 施。 本文主要参考d t m b 标准，研究数字电视地面广播传输系统基带处理的算 法与实现，包括信道编解码、调制解调、接收机的同步和信道均衡、以及传输 系统其他关键技术的研究与实现。 第一章d t m b 系统介绍 第一章d t m b 系统介绍 1 1 中国数字电视地面广播传输系统标准 对地面数字电视广播标准来讲，首先要求数字电视有足够好的接收性能， 在室内采用简单、小型和低增益天线即可实现稳定接收。甚至在较强静态和动 态多径的环境中，系统仍能够稳定工作。其次，要有足够高的传输码率，以便 在单个6 - - 8 m h z 信道中提供高质量高清晰节目( 大约2 0 m b p s ) ，还要有利于 频率规划【l j 。 其它的要求包括：需要先进的信道编码和信道估计方案，以便降低系统 c nf - j 限，以此降低发射功率，并减少对现有模拟电视节目的干扰，具有良好 的抵抗各种干扰失真能力；高度灵活的操作模式；易于和其它媒介或服务器的 接口；高度灵活的频率规划和覆盖区域，能够使用单频网和同频道覆盖扩展缝 隙填充；系统应允许多种成本价格的接收机实现，包括低成本实现等等。 根据不同的应用环境和业务需求，d t m b 标准提供了多种工作模式参数。 d t m b 标准系统的主要技术模式和系统参数见表1 一i t 。 表1 1d t m b 标注主要技术参数 参数 定义 前向纠错编码 0 4 ( 7 4 8 8 ，3 0 8 8 ) ，0 6 ( 7 4 8 8 ，4 5 1 2 ) ，0 8 ( 7 4 8 8 ，6 0 1 6 ) 星座映射 4 q a m n r ，4 q a m ，1 6 q a m 3 2 q a m ，6 4 q a m 时域卷积交织短交织b = 5 2 ，m = 2 4 0 ：长交织b = 5 2 ，m = 7 2 0 帧头长度 p n 4 2 0 ，p n 9 4 5 ，p n 5 9 5 系统信息长度3 6 个符号，4 q a m 调制 帧体长度3 7 8 0 个符号，5 0 0 u s 信号帧长度4 2 0 0 ，4 7 2 5 ，4 3 7 5 个符号 信号带宽 7 5 6 m h z 基本净衙数据率4 8 1 3 3 2 4 8 6 m b p s 载波数目多载波c = 3 7 8 0 ：单载波c = i 2 第一章d t m b 系统介绍 d t m b 标准支持高清晰电视，标准清晰电视和多媒体数据广播等多种业 务，适用室内外、支持固定、移动等多种接收方式，支持大范围广播覆盖的多 频和单频组网方式。标准兼容了基于时域同步的单、多载波调制技术，采用先 进的前向编码技术，具有系统同步快、接收灵敏度高、抗多径衰落能力强、频 谱利用率高、可扩展功能多等先进性能【l 】。 1 1 1d t m b 多载波传输系统 为了表述方便，有时候本文也将d t m b 多载波调制系统称为m c m ( m u l t i c a r r i e rm o d u l a t i o n ) ，将d t m b 单载波调制系统称为s c m ( s i n g l ec a r r i e r m o d u l a t i o n ) 。 1 1 1 1t d s o f d m 调制器基本构架 t d s o f d m 传输系统的信号帧使用时域同步的正交频分复用调整，或者称 为以p n 序列为保护间隔的正交频分复用调制。一个信号帧由帧同步头和帧体 两部分组成，它们具有相同的基带符号率7 5 6 m s p s 。一个信号帧就是一个符号 块，由一个保护间隔和一个离散傅立叶变换数据块组成。对于t d s o f d m 来 说，p n 序列既作为保护间隔又作为帧同步序列，而帧体则为数据块，如图1 1 所示。 图l 一1t d s o f d m 调制器系统框图 信号帧中的帧同步部分由前同步、p n 序列和后同步三个部分组成。序列根 据模式的不同可以是2 5 5 或者5 1 1 个符号，而前同步和后同步信号则分别是p n 序列的循环扩展，与p n 序列一起共同组成保护间隔 2 。 信号帧的帧体采用多载波调制方式，帧体的频率域子载波数目为3 7 8 0 。相 邻子载波的问隔为2 k h z ，每个子载波采用n r 4 q a m 、4 q a m 、1 6 q a m 、 3 2 q a m 或者6 4 q a m 调制。信号帧的帧体除了正常的数据流外还有传输参数信 令t p s ，用来传输系统的配置信息，占用了3 6 个子载波 2 】。 3 第一章d t m b 系统介绍 1 1 1 2t d s o f d m 解调器基本构架 t d s o f d m 系统接收机在经过变采样滤波器和匹配滤波器对从调谐器 ( t u n e r ) 传输的信号进行基带变换之后，t d s o f d m 解调器使用p n 序列来进 行符号同步、载波同步、采样同步跟踪。 同步既可以通过p n 序列的升采样后相关提取来实现，也可以通过频域t p s 信息相位提取的方式来完成。随后，依靠p n 序列的己知信息通过时域的循环 相关完成信道估计。将得到的信道估计信息与已知的p n 序列信息结合3 7 8 0 点 f f t 解调后的频域数据进行补偿运算，通过循环卷积完成均衡。经过解调得到 的3 7 8 0 点f f t 频域信号再经过基于信道信息的软解星座映射、解卷积交织、 f e c 译码以及解扰，最终得到二进制码流( m p e g t s ) 输出。t d s o f d m 解调 器的基本构架如图1 2 所示。 混 p n 辅助载波同步hh 信道估计 霪蓑h 篙荔h 番霉h 霉恻裴鑫藿 二阶环路滤波 到篇h 豁恼一蓑翥薹薏簇嚣刚译码h 译码卜- 1 堡奎釜l 叫袤舞量蠢误爵 噪声估计 图1 - 2t d s o f d m 解调器系统框图 1 1 2d t m b 单载波传输系统 数据重构与均衡 中国数字电视地面广播单载波系统的主要技术核心采用了上海交通大学提 出的a d t b t 技术。a d t b t 系统简洁高效，安全可靠，兼容性好，扩展性 强；突破了单载波数字电视移动接收技术瓶颈，首次实现单载波高清晰度电视 移动接收；采用单载波调制技术，具有频谱效率高、峰均比低、调制度低、受 非线性失真影响小，对发射机要求低等优点【3 】【4 1 。d t m b 单载波系统的调制器 系统结构如图1 3 所示。 4 第一章d t m b 系统介绍 图1 - 3d t m b 单载波系统调制器框架 由于s c m 系统和m c m 系统一样，都采用了p n 序列作为帧头，因此s c m 接收系统的同步处理、基带后处理均与多载波的相似。但是由于s c m 系统没有 o f d m 符号，均衡的处理也完全不同。s c m 系统的均衡采用时域均衡器，且没 有复杂的f f t i f f t 运算，这也就决定了s c m 系统接收机的均衡结构较为简 单，类似于d v b c 系统。图l - 4 是d t m b 单载波接收系统的框图。 图1 - 4d t m b 单载波系统解调器框架 虽然s c m 系统与m c m 系统在调制方式上有所差别，但是其差别是有限 的，可以通过分析得到一个折中来共用大部分硬件模块，以方便实现融合方 案。在本文下面的章节中，将介绍各部分的融合处理方式。 1 1 3d t m b 系统的净荷数据率 在应用d t m b 标准时，可根据应用业务的特性和组网环境，选择不同的传 输模式和参数，并支持多业务的混合模式。根据d t m b 标准可供选择的参数， 5 第一章d t m b 系统介绍 在不同模式下，系统的净荷数据率可以按以下方法计算： 民= r 6 r 眦害半( 1 - 1 ) l e nf r a m e 式( 1 一1 ) 中，r 。是系统净荷数据率，r s 是数据符号率( d t m b 为 7 5 6 m s p s ) ，b 为每个符号的比特数( 与调制方式有关) ，月脚为前向纠错码 率，l e n d a t a 为信号帧中有效数据符号数，l e n f r a m e 为数据帧长。 表1 2d t m b 系统净荷数据率 f e c 码率 帧头模式 净荷数据率m s p s 0 4o 60 8 调制模式 4 q a m 5 4 1 48 1 2 2 p n 4 2 0 1 6 q a m 1 0 8 2 91 6 2 4 32 1 6 5 8 6 4 q a m? ? 2 4 3 6 5 澉。6 ，磊( m 强a 遽 1 _ t e f 舢，盖n 一自帆口i 4 q a m 5 1 9 87 9 7 ? p n 9 4 5 1 6 q a m 1 0 3 9 61 5 5 9 32 0 9 7 l 6 4 q a m 2 3 3 9 03 1 1 8 7 4 q a m - n r群湖 4 q a m 7 2 1 9 p n 5 9 5 1 6 q a m 9 6 2 61 4 4 3 81 9 2 5 l 3 2 q a m 2 4 0 6 4 6 4 q a m 2 1 6 5 82 8 8 7 7 按标准规定，支持从4 8 1 3 - 3 2 4 8 6m b i t s 的传输模式，支持包含4 q a m n r 、4 q a m 、1 6 q a m 、3 2 q a m 、6 4 q a m 五种调制方式，p n 4 2 0 、p n 5 9 5 、 p n 9 4 5 三种帧头模式，0 4 、0 6 、o 8 三种前向纠错码率，两种卷积交织模式， 两种传输模式，单载波可选插入双导频，共3 3 0 种组合。但标准只推荐其中的 3 3 种组合 5 】，而且根据应用分析及反馈，3 3 种模式中有几种组合是不被采用 的。根据地面数字电视接收机通用规范，只规定了其中7 种模式的应用要 求。目前为止，商用的模式只有2 种。多载波：1 6 q a m ，0 6 码率，p n 4 2 0 帧 头模式，m = 2 4 0 卷积交织模式：单载波：1 6 q h m ，0 6 码率，p n 5 9 5 帧头模 式，m = 2 4 0 卷积交织模式。根据上面分析，d t m b 系统有效组合及相应的净荷 数据率如表1 2 所示。 6 第一章d t m b 系统介绍 1 2 数字地面电视广播传输信道模型 研究传输系统，信道是重要环节，任何算法的选择都是基于特定的信道。 在无线通信系统中，通过电磁波在自由空间的传播来传输信息。发射机和接收 机之间的路径非常复杂。信号在空中的传播受到的损耗大致可分为两类：快衰 落和慢衰落，慢衰落表现为信号功率反比于距离的平方；快衰落由多径、反 射、折射、散射等引起，表现为信号在很小距离或很短时间内差别会很大【屹】。 文中所采用的信道有b r a z i l a 、b r a z i l d 、b r a z i l e 、t u 、c t 8 、s f n 等信 道模型【1 2 】【1 3 】，模型具体参数可见附录a 。其中b r a z i l a 信道性能最好，多径数 目少且多径延时小，且只有一个强径：b r a z i l b 及t u 信道性能较好，时延稍 大，有明显强径；b r a z i l c 、b r a z i l d 信道存在多条密集等强多径；b r a z i l e 、 c t 8 、s f n 信道存在强长延时多径，s f n 存在一条长达4 0 u s 的0 d b 多径，性能 极差。另外，典型乡村t r 信道有时候也被采用，它具有最良好的无线广播信 道特性，多径少且密集、强径突出、多径延时小。 1 3 任务安排及研究意义 本章介绍了我国数字地面电视广播标准规范的t d s o f d m 系统的发送、接 收机基带处理的基本结构以及单载波发送、接收系统基带处理结构。并且较为 简要地介绍数字地面电视广播传输信道模型。下面将针对d t m b 系统的各模 块，分别展开介绍实现方案。 第二章介绍d t m b 系统的基带处理基本功能模块，包括星座映射与解映射 的硬件实现、3 7 8 0 点f f t i f f t 技术及实现、卷积交织及解交织的实现、s r r c 设计与实现等内容。 第三章介绍d t m b 的分别适用于多载波调制模式与单载波调制模式的同步 算法及实现，包括载波频偏估计与纠正、符号同步及定时同步。 第四章介绍d t m b 系统的信道估计与均衡算法与实现，由于d t m b 是清华 的多载波d m b t h 与上海交大单载波a d t b t 的融合，同样也要分别介绍多载 波调制系统与单载波调制系统的信道估计与均衡【4 】。 第五章介绍d t m b 系统的前向纠错编码及其解码方案，主要是q c l d p c 的编解码，同时介绍单载波模式特有的n r 编码与解码。 在第六章简单总结本文前面几章的工作，包括系统设计各阶段任务完成情 况及最终结果，并展望后期工作。 为了确保系统设计的合理性，在考虑硬件实现及选择硬件器件之前，要对 7 第一章d t m b 系统介绍 各种算法进行仿真分卡斤【7 1 ，选择适用于该系统的算法，并选定算法中涉及到的 可设计性参数，包括参数大小和参数设置、变化规律等，为后续工作做好准 备，达到事半功倍的效果。在完成系统设计之后，采用d h l 描述【8 】各个模块， 并在q u a r t u si i 环境中综合、编译及仿真。 本文研究的意义在于，通过研究d t m b 系统基带处理算法及实现方法，能 够熟悉与掌握数字通信系统基带处理的基本方法，对数字通信系统的实现有深 刻认识，并在此基础上从整体的角度把握系统设计的思想，从而提出合理的系 统设计方案，更大程度上优化d t m b 系统基带数据处理模块的实现方案。 本文是在具有一定数字电视接收机基带处理模块设计经验的基础上展开 的，一定程度上保证了能在有限的时间与精力内完成任务，达到预期目标。因 此本文的工作重点在于d t m b 系统关键技术【9 】的理解与实现，如o f d m 调制实 现，基于p n 序列的同步、均衡算法，q c l d p c 的编译码，n r 码的编译码实 现等。 8 第二章d t m b 基带处理基本模块的实现 第二章d t m b 基带处理基本模块的实现 d t m b 发射机的基带处理包括：加扰器、b c h 编码器、q c l d p c 编码器、 星座映射、卷积交织器、系统信息产生与复接器、频域交织器、3 7 8 0 点i f f t 变换模块、p n 序列产生器、帧体复接器以及s r r c 成型滤波器【2 】。与此相应 的，d t m b 接收机基带处理包括：同步系统、信道估计与均衡、系统信息提取 与分析、频域解交织、解卷积交织、解星座映射( s c m 系统的n r 解码) 、 q c l d p c 解码、b c h 解码、解扰等模判1 】【l o 】。 同步系统、信道估计与均衡、及f e c 译码将分别在后面章节介绍。本章介 绍f f t f l f f t 技术及实现、卷积交织及解交织的实现、s r r c 设计等功能模块。 2 13 7 8 0 点f f t 实现t d s o f d m 子载波映射的f p g a 实现 f f t i f f t 是t d s o f d m 系统的关键技术之一，硬件实现比较复杂【6 】【9 1 。实 现算法的选择及优化的程度在很大程度上影响d t m b 系统的整体性能。 2 1 1 概述 3 7 8 0 点f f t 算法可以采用不同的算法来实现。例如，采用基2 或基4 的 f f t 算法，对x ( n ) 序列增补零值点，使n 增长到最邻近的一个基2 值： 2 ”= 4 0 9 6 ( n = 1 2 ) 。由d f t 性质可知，有限长序列补零之后，不会影响其频 谱特性，只不过增加了冗余数据。然而通信系统，特别是无线通信传输系统， 频带资源是有限的，减小不必要的冗余数据是提高带宽利用率的有效方法。 d t m b 系统是一个频谱利用为1 0 0 的系统，需要寻求别的f f t 算法实现 o f d m 系统的3 7 8 0 点i f f t f f t 模块【l 4 1 。 2 1 2n 点的傅立叶变化算法 快速傅立叶变换的基本思想是将大点数n 的d f t 的运算尽量分为小点数的 运算。当n 是一个复合数，即它能分解成一些因子的乘积时，可以根据分解得 到的因子的特征，采用不同的快速傅立叶算法。例如，若分解得到n = 2 。次， 则可以直接采用基一2f f t 算法，这种方法是c o o l e y - t u k e y 算法的一种典型情 况，由于它效率高，应用方便，目前应用相当广泛；若分解得到的因子两两互 9 第二章d t m b 基带处理基本模块的实现 素，如6 3 = 7 9 ，则可以采用素因数算法或w i n o g r a d 1 7 1 嵌套算法；若分解得到 因子不全是两两互素，则可以采用几种算法的综合。接下来先介绍几种快速算 法。 2 1 2 1c o o l e y t u k e y 快速傅立叶算法 任何一个大于1 的整数n 可以分解为素数的乘积。如果分解得到的因子不 能全部互为素数( 如7 5 = 3 5 5 ，后两个素因子是同一个素数) ，则此时可采用 c o o l e y t u k e y 快速傅立叶算法1 8 1 19 1 。假设= 1 2 ，且l 和2 有公共因子， 令n 和k 表示傅立叶变换对中的序号，若令n 和k 表示为： f 刀= n l + i ，z 2 1 后：2 毛+ 砭 所以时域抽取的f f t 算法可以表示式为： ( 2 - 1 ) n i l ln ，一l x ( 毛，也) = l x 【，z ：) 噍如l 吩如弧岛( 2 - 2 ) 啊= o l 玑= 0 若，2 和k 表示为： f 刀= u 2 1 + 刀2 1 j j ：k l + n l k 2 则频域抽取的f f t 算法的变化式为： ( 2 3 ) ，一l in 一li x 砭) = l 芝x h 咒：) 瞻墨i 蝶：与储( 2 - 4 ) 月，= 0 i 羁= o 时域抽取算法和频域抽取算法在结构上和计算顺序上不相同，但计算量相 同。本论文中使用的c o o l e y t u k e y 算法采用时域抽取变化的形式。 当n = n t n 2 时，按c o o l e y t u k e y 快速傅立叶变换所需要的复数乘法和复数 加法次数为： m ( n ) = l m ( 2 ) + 2 肘( 1 ) + a ( n ) = 。彳( 2 ) + 2 爿( 1 ) ( 2 - 5 ) 其中m 表示复数乘法次数( 4 次实数乘法) ，a 表示复数加法次数( 2 次实 数加法) 。由式( 2 5 ) 可知，c o o l e y t u k e y 算法所需的运算量明显小于直接d f t 1 0 第二章d t m b 基带处理基本模块的实现 计算所需的运算量，特别当n 是高度复合数时，即l 和也是复合数时，上 述计算步骤可以反复使用，一直分解n d , 点数的n 。可见这种方法应用于3 7 8 0 点d f t ，可以大大减小运算量，易于硬件实现。 为了进一步减小计算量，内层的傅立叶变换可以采用运算量比平方次小的 算法。如w i n o g r a d 的小点数d f t 算法。 2 1 2 2w i n o g r a d 小点数d f t 算法 w i n o g r a d 小点数的d f t 算法是一种计算小数组长度离散傅立叶变换的有效 方法【l7 1 。它建立在r a d e r 素数算法和w i n o g r a d 卷积算法的基础上，对于点数为 n 的小点数d f t 运算，乘法次数近似为n ，大大减少了乘法次数。序列长度n 可以为素数、奇素数幂或是2 的乘幂。目前研究利用最多，即最普遍的序列长 度为n = 2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 6 。 若用矩阵表示w i n o g r a d 小点数d f t 算法，有： x = o h z ) n 1 v x ( 2 - 6 ) 其中，、d 、d 分别是前编模矩阵、复乘矩阵以及后编模矩阵。l 表示 m n 的输入矩阵，d 是mx m 的对角矩阵，d 是n xm 的输出矩阵。d 的 元素足实数或纯虚数，和d 的元素为0 、l 或数值较小的整数。 若小点数n = 3 ，则输入数据表示为( ，x 。，x ：) ，输出变化结果表示为 ( 甄，石1 ，x 2 ) 。 则三点的w i n o g r a d 算法流图【1 7 】如下所示： 工o 五 工2 图2 1 三点的w i n o g r a d 算法流图 x o x l x 2 3 点d f t 的w i n o g r a d 算法需要3 次乘法，6 次加法，其中有1 次乘法是乘 以常数1 ，即有1 次平凡乘法。若直接d f t 计算，需要3 2 次乘法。由此可 见，w i n o g r a d 小点数d f t 算法大大降低了乘法次数，降低了运算复杂度，这也 是硬件实现所追求的。 w i n o g r a d 直接给出了n = 2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，16 八种长度d f t 的w i n o g r a d 算法， 第二章d t m b 基带处理基本模块的实现 采用的是顺序输入、顺序输出的结构【1 7 】。表2 1 列出了本文涉及到的 n = 3 ，4 ，5 ，7 ，9 时对应的复数乘法和复数加法次数。当输入为实序列时，则表中 所列的乘法数就是所需的实乘数。 表2 - 1 小点数f f t 运算复杂度【1 7 】 d f t 长度n 复数乘法次数m 复数加法次数a 336 448 551 7 7 93 6 91 l 4 4 2 1 2 3p f a 素因子算法 g o o d t h o m a s 素因子算法在概念上较c o o l e y t u k e y 算法稍复杂些，但计算 却更为简单【1 8 】【1 9 1 。这种算法利用中同余数定理做指数映射，通过数据重排将一 维序列映射为二维或多维序列，从而将n 点一维d f t 变换为二维或多维d f t t l 8 】 d 9 。与w f t a 一样，素因子算法同样要求分解的因子两两互素，每个小因子的 d f t 采用w i n o g r a d 小点数d f t 运算，也就是说，分解的因子必须是属于 n = 2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，16 。 假设n = 1 ，1 和互质。时域及频域地址映射关系式为： n：=n2nl,+1nln2(modn哪),nlki=-o，0,1,，nl-一1kn 2 kk s ( m o d n ) nk s 1 n 2 1 ( 2 7 ) 【=l + 1，2 ，= o ，i ，一一 、7 所以d f t 可以变化为： x 似2 ) - 雏- - 0 x h 以聪p 亿8 ， x 。，艮：) = i x g 。，刀：) 嘴如瞻岛 ( 2 8 肌= o ln ， 利用映射关系式( 2 - 7 ) ，可以将一维d f t 映射为二维d f t ，反复利用之，就 可以将一维d f t 变换到多维d f t 。也就是说，如果复合数n 可以分解为多个 质数的乘积，则复合数n 点的d f t 就可以用多维较小点数的d f t 变化，再用 w i n o g r a d 小点数d f t 实现。 1 2 第二章d t m b 基带处理基本模块的实现 要完成1 2 二维d f t 总共需要完成2 组l 点的d f t 和组l 点的 d f t 。下面计算一下l 点的d f t 所需要的计算量，以衡量硬件实现d f t 所需 的资源。 假定计算1 点d f t 所需要的复数加法和复数乘法运算次数为4 和m 。；计 算点d f t 所需要的复数加法和复数乘法运算次数为以和m ，。则总的复数乘 法次数m 和复数加法次数彳为： i m = n j m 2 + n 2 m 1 【a = n l a 2 + n 2 a l ( 2 - 9 ) 对于l 维的d f t 而言，即复合数可以分解为l 个两两互质的质数相乘的结果， 即n = n m 。 t = l 显然，素因子算法需要的乘法次数与加法次数仅跟素因数的分解有关，与 素因子的排列顺序无关。即一定的复合数如果可以分解为两两互质的因数相 乘，硬件实现复杂度就是一定的。 2 1 2 4 三种算法的比较及应用 d f t 算法的优劣主要是通过比较计算d f t 需要的总运算量来评断的，尤其 足总的乘法运算次数和加法运算次数。当n = lx n 2 = 3 5 时，c o o l e y t u k e y 快速傅立叶变换算法、w i n o g r a d 小点数d f t 嵌套算法以及p f a 素因子d f t 三 种算法的乘法次数和加法次数如表2 2 所示。 表2 2 三种f f t 算法的运算复杂度对比 运算次数c o l l e y t u k e yf f t w f t ap f a 复数乘法次数 4 81 83 3 复数加法次数 1 3 68 78 1 由此可知，以上三种算法中，w i n o g r a d 小点数d f t 算法所需的硬件资源最 少，但是可应用的范围却也是最少的，本文者d f t 运算的最小单元采用该算 法；p f a 素因子算法的运算比w i n o g r a d 小点数d f t 算法所需的硬件资源稍 大，但是实际应用范围也略大，结合小点数d f t 算法可以发挥较大的优势；而 c o o l e y t u k e y 算法是三者中硬件资源需求量最大的，这主要是由于分解的各因 数中不是两两互质，需要进行重排序，但几乎可以应用于所有的情况下。 1 3 第二章d t m b 基带处理基本模块的实现 2 1 33 7 8 0 点f f t 算法的硬件实现架构 2 1 3 13 7 8 0 点f f t 算法的运算结构 本文的d f t 点数为3 7 8 0 ，不能分解为两两互质的因数，采用三种算法结合 的方法实现，充分发挥各种算法的优势。通过对复合数n 的分解， n = 3 7 8 0 = 6 0 x6 3 = ( 3 x4 x5 ) x ( 7 x 9 ) ，可知，3 7 8 0 点d f t 的最上层采用 c o o l e y t u k e y 算法，中间层采用p f a 素因子算法，最下层采用w i n o g r a d 小点数 算法，具体的分解方式如图2 2 。 夕医三互至亟三亚亟竭 霉兰鲨堕塑塑坐划 图2 - 23 7 8 0 点f f t 实现结构 由以上的分层结构可以很明了的得出运算步骤，输入的3 7 8 0 点复数形式数 据暂存于r a m 中，根据各级地址映射关系分组，再进行该层的f f t 运算；内 层的计算在运用相应的算法实现。下面具体介绍每一层运算过程。 1 ) 第一层采用c o o l e y t u k e y 算法：按自然顺序存于r a m l 中的3 7 8 0 个数据 按照时域二维地址映射公式刀= 6 0 n 。，+ n 。分组为6 0 组，每组6 3 个数，准备 进行6 0 次6 3 点的f f t ；运算过程中采用原址存储，以节省r a m 资源；进 行完f f t 运算后，将得到的3 7 8 0 个数据分别乘以相应的旋转因子孵k ， 结果存回原来的地址；同样的，将r a m l 中的3 7 8 0 个中间数据按照时域二 维地址映射公式胛= 6 0 n 。，+ 6 0 分组为6 3 组，每组6 0 个数，进行6 3 个6 0 点 的f f t ，运算结果存回原地址；将运算结果按照频域二维地址映射公式 k = 心，+ 6 3 k 将二维数转化为一维数输出。 2 ) 第二层p f a 运算：以6 3 点f f t 为例介绍运算过程。6 3 点的数据暂时存入 r a m 2 中，按照时域地址映射公式疗= 9 n ，+ 7 n 9 ( m o d 6 3 ) 分为7 组，每组9 个数据，做7 个9 点的原址f f t 运算：再次按照地址映射关系式将数据分 1 4 寸八 鼍 第二章d t m b 基带处理基本模块的实现 为9 组，每组7 个数据，做9 个7 点原址f f t 运算；按照频域地址映射公 式k = 3 6 k 7 + 2 8 k 9 ( m o d 6 3 ) 将r a m 2 中的数输出，即得6 3 点f f t 运算结 果。 3 ) 第三层w m o g r a d 小点数f f t 运算：参考文献将n = 3 , 4 ，5 ，7 ，9 的小点数运算 生成相应模块，当运算时，直接调用；其中，平凡乘法可以简化而不作任 何处理，与复乘对角矩阵中特殊的因子进行的乘法运算可以采用相应的移 位运算以及加法运算实现。该底层模块的简化将在最大程度上影响整个 f f t 模块的实现复杂度。 p f a 算法和c o o l e y - t u k e y 算法是针对可分解的复合数而言的，相应的在运 算中必须要做地址映射，下面给出了3 7 8 0 点3 7 8 0 点c o o l e y t u k e y 算法采用的 映射关系式。 n = 6 ，0 n 6 3 + n 6 0 ；( 2 - l o ) 【k = 丸3 + 6 3 k 6 0 以上吩( 或岛) 表示o 吩i - 1 ( 或o 岛i - 1 ) 。 2 1 3 23 7 8 0 点f f t 的运算流程图 3 7 8 0 点f f t 分4 层，图2 3 是具体的运算流程。f f t3 、f f t4 、f f t5 、 f f t7 、f f t9 分别表示3 、4 、5 、7 、9 点的小点数f f t 模块。r a m l 、 r a m 2 、r a m 3 、r a m 4 、r a m 5 分别是运算中用来暂存数据的存储器。 本文中共用到6 个存储器r a m ，其中r a m 5 用来实现频域地址映射数据整 序。r a m 2 、r a m 3 实现时域地址映射，被多次重复使用，是读取频率最大的 r a m 。r a m 4 是实现小点数f f t 运算模块的输