（微电子学与固体电子学专业论文）交织与解交织的算法研究及fpga实现.pdf

摘要 摘要 本文主要研究了数字声音广播系统( d a b ：d i g i t a la u d i ob r o a d c a s t ) 内交织器 与解交织器的算法及硬件实现方法。时间交织器与解交织器的硬件实现可以有几 种实现方案，本文对其性能进行了分析比较，选择了一种工程中实用的设计方案 进行设计，并将设计结果以f p g a 设计验证。时间解交织器的交织速度、电路面 积、占用内存、是设计中主要因素，文中采用了单口s r a m 实现，减少了对存储 器的使用，利用l c 设计的优化设计方法来改善电路的面积。硬件实现是采用工业 e d a 标准t o p t o - d o w n 设计思想来设计时间解交织，使用v e r i l o g h d l 硬件描述语 言来描述解交织器，用c a d e n c en c - v e r i l o g 进行仿真，d e b u s s y 进行d e b u g ，在a l t e r a 公司的f p g a 开发板上进行测试，然后用a s i c 实现。测试结果证明：时间解交织 器的输出正确，实现速度较快，占用面积较小。 关键字：交织器f p g ad a bv e r i l o g h d l a b s t r a c t a b s t r a c t n ep a p e rs t u d i e sa l g o r i t h ma n dh a r d w a r ei m p l e m e n t a t i o nm e t h o do ft h e i n t e r l e a v e ra n dd e i n t e r l e a v e ri nt h ed a b ( d i g i t a la u d i ob r o a d c a s t ) s y s t e m t h e r ea r e s e v e r a lh a r d w a r ei m p l e m e n t a t i o nm e t h o d so nt i m ei n t e r l e a v e ra n dd e i n t e r l e a v e r , i n n i st h e s i sc h o o s eo n ep r a c t i c a la n do p t i m i z a t i o nm e t h o df o rd e s i g nt e s t e do nf p g a d e v e l o pb o a r db yc o m p a r i n ga n da n a l y z i n gt h ep r o p e r t y o ft h ei m p l e m e n t a t i o n m e t h o d s 1 1 l ek e yf a c t o r so nt h et i m ei n t e r l e a v i n gd e s i g na r ei n t e r l e a v i n gs p e e d c i r c u i t a r e aa n dm e m o r yu n i t t h ep a p e ra d o p t so n ep o r ts r a m t oi m p l e m e n tf h ed e s i g ni n o r d e rt ou s el e s sm e m o r ya n dt h eo p t i m i z a t i o nd e s i g nm e t h o d st oi m p r o v et h ec i r c u i t a r e a t h eh a r d w a r ei m p l e m e n t a t i o no ft h et i m ed e i n t e r l e a v e ra d o p t si n d u s t r ye d a s t a n d a r d t o p - t o - d o w ni d e a ，a n du s i n gv e r i l o gh a r d w a r ed e s c r i p t i o nl a n g u a g e d e s c r i b e st h ed e i n t e r l e a v e r , a n du t i l i z i n gc a d e n c en c v e r i l o gs i m u l a t o r , d e b u g g i n g w i t hd e b u s s y , s y n t h e s i s i n gw i t hs y n o p s y st o o la n dt e s t so nt h ef p g ad e v e l o pb o a r d m a d eb ya l e t r a 1 1 l er e s u l ts a y s ：1 1 l ef u n c t i o nw o r k sw e l l ，a n db e t t e rs p e e da n ds m a l l e r a r e aa r eu s e d k e y w o r d ：i n t e r l e a v e r f p g ad a bv e r i l o g h d l 声明 创新性声明 秉承学校严谨的学风和优良的科学道德本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包括其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说 明雩翟! 勉 本人签名：i 幺属蹬蜴 日期：丝乒卫生 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： i t 梵l l ：翘：丝 e i t # i ：兰生：! ：丝 第一章绪论 第一章绪论 1 1 差错控制技术 差错控制编码也称为纠错编码。在实际信道上传输数字信号时，由于信道传 输特性不理想及噪声的影响，接收端所收到的数字信号不可避免地会发生错误。 为了在已知信噪比情况下达到一定的比特误码率指标，首先应该合理设计基带信 号，选择调制解调方式，采用时域、频域均衡，使比特误码率尽可能降低。但实 际上，在许多通信系统中的比特误码率并不能满足实际的需求。此时则必须采用 信道编码( 即差错控制编码) 才能将比特误码率进一步降低，以满足系统指标要求。 差错控制技术随着差错控制编码理论的完善和数字电路技术的飞速发展，信 道编解码技术已经成功地应用于各种通信系统中，并且在计算机、磁记录与各种 存储器中也得到日益广泛的应用。差错控制编码的基本实现方法是在发送端将被 传输的信息附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规 则相互关联( 约束) 。接收端按照既定的规则校验信息码元与监督码元之问的关系， 一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以 发现错误乃至纠正错误。因此，研究各种编码和译码方法是差错控制编码所要解 决的问题。编码涉及到的内容也比较广泛，前向纠错编码( f e o 、线性分组码( 汉 明码、循环码1 、理德一所罗门码( r s 码) 、b c h 码、交织码、卷积码、t c m 编码 及t u r b o 码等都是差错控制编码的研究范畴。 1 9 6 0 年，i s r e e d 和g s o l o m o n 发现了r e e d s o l o m o n 码( r s 码) ，r s 码具有 很强的纠正随机错误的能力及纠正一定突发错误的能力，是近五十年来被广泛使 用的一种码字。卷积码的概念是由p e l i a s 于1 9 5 5 年发现的。尽管其代数结构以 及相应的理论结果没有分组码丰富，但由于其译码算法的实用性，因而在编码理 论中也占有重要地位。 由于r s 码以及其它纠错码纠错能力有限，当信道中长的突发错误出现概率 很高时，可以采用级联码来充分发挥纠错能力。级联码( 或称级连码，c o n c a t e n a t e d c o d e s ) 是由g d f o m e y 于1 9 6 6 年提出的，级联码一般以r s 码作为外码，而以卷 积码作为内码，并经过加扰、交织技术，进一步离散突发错误。f o m e y 的性能分 析表明，级联码的性能改善了很多，而译码复杂度增加的并不多。 2 交织与解交织的算法研究及f p g a 实现 1 2 交织技术的应用 大多数分组码和卷积码都可以抵抗独立随机错误，对于有记忆信道，错误不 再是比特问相互独立的随机分布的比特错误。由于信道有记忆性，这使得这些编 码的差错性能下降。己经有人提出有记忆信道的编码技术，但是，要想得到这种 信道的时变统计特性的精确模型十分困难，这是这种编码在实现上的最大困难。 时间分集或者交织技术就是其中的一种技术，它只需要知道信道记忆的持续时间 或者跨度，而不需要知道其确切的统计特性。 交织和解交织是一种很实用也很常用的构造码的方法，交织技术是对纠错码 纠错能力的重要补充。交织与解交织在理论上己经成熟，重点在于选择何种交织 器构造方法，得到简单实用的交织方案，基于不同情况下交织方案的选择，交织 器的性能也有所不同。比如面向r s 码的交织器，由于r s 码的纠错能力极其有限， 因而当信道出现较大的突发错误时，超出r s 码的纠错能力，这时候要充分发挥 r s 码的纠错能力，就需采用交织的方法，作为对r s 码的重要补充，极大提高了 系统的纠错能力。再比如面向t u r b o 码的交织器，它的作用显得更加重要。t u r b o 码的巧妙之处在于多个子编码器通过交织器进行并行或串行级联伊c c s c c ) ，然 后以类似内燃机引擎废气反复利用的机理进行迭代译码，从而获得具有接近 s h a n n o n 极限的纠错性能。在t u r b o 码的编译码过程中，正是由于交织器的存在 才真正体现了s h a n n o n 随机编码的思想精华。在t u r b o 译码中反复地利用了附加 信息( 即外信息) 在子译码器闻进行多次迭代译码的结果，而这些由各级子译码器 产生并反映相应信息位译码判决可信度的附加信息之所以能被相互利用，归功于 插在它们之间的交织与解交织器，即它们的“置乱”作用使在同一时刻送入各子 编译码器的信息序列码元几乎不相关。 交织器的研究还有待于进一步深入，以期找到更多性能优良的解决方案。下 一章将着重介绍交织原理。 交织技术结合纠错码技术广泛应用于深空通信、卫星通信、移动通信，数字 存储设备、数字电视等领域，交织技术的使用，极大提高了纠错码的纠错能力。 在m p e g 一2 视频标准中，使用了复杂的差错控制，特别是在d a b d m b ( d i g i t m a u d i o m u l t i m e x t i ab r o a d c a s t ) ，d v b ( d i g i t a iv i d e ob r o a d c a s t ) 中，使用了级联码。 深空信道，由于它可以近乎精确地模型化为无记忆a w g n ( a d d i t i v ew h i t e g a u s s i a nn o i s e ) 信道，而且信道的频带资源丰富，其次是功率受限，由于传输距 离远，信号衰减严重，需要采用纠错能力强的码。数字电视传输系统，要求高可 靠性和高效率，而数字信道和广播信道都是带限信道，为了提高在传播过程中的 信号衰落，也采用了交织技术。 第一章绪论 1 3d a b d m b 系统简介 d a b d m b 系统由发射系统和接收机两部分组成。发射系统由信源编码器、 信道编码器、多路复用器、o f d m 调制器、以及模拟射频等部分组成；而接收机 则由调谐器、d a b 解码模块、数据业务解码器、接口及系统总控等部分组成。发 射和接收系统的原理框图见图1 1 。 音频信源编码采用m u s i c a m 算法，得到的音频压缩数据经信道可删除型 卷积编码，送入多路复用器与数据业务一起复用，复用信号以包的形式进行 o f d m 基带调制，在其中还加入f i c 、同步信号等，o f d m 基带调制后得到i q 两路信号送入射频部分进行载波调制并发射。 而系统接收部分则是发射部分的逆过程。 接收机将首先调谐从天线进入的高频信号并进行a d 变换后，得到数字信号。 数字信号经过i ，o 变换，得到两路正交的信号，该信号通过信道同步和信道均衡 后，送入o f d m 基带解调器进行基带解调，然后通过解复用器将音频信号送入信 道解码器解码，接着进行信源解码，音频综合，最后经d a 还原成模拟音频。而 从解复用器出来的数据业务，则送入数据业务电路处理，完成数据业务的解码与 显示部分。 图1 1d a b d m b 系统发送和接收原理图 时间交织和频率交织主要用于削弱突发干扰和频率选择性干扰的影响，这些 干扰主要是来自多径信道的衰落干扰和移动接收过程中的多普勒频率时变导致的 4 交织与解交织的算法研究及f p g a 实现 干扰。通过时间交织和频率交织，突发干扰和频率选择性干扰被分散到各个不同 的区域，借助卷积码的强大的纠错能力得到很好的抗干扰性能。 许多移动中的干扰是由多径接收造成的。所谓“多径接收”，就是指接收机 所接收的信号不仅是发射台直接传送过来的主信号，还有很多其他发射机发出的 及经建筑物和山坡等障碍物反射后才接收到的信号，这些相遇的信号会有较大的 时延差，可能导致接收的各信号成分相互干扰，形成所谓的“时间选择性衰落”及 “频率选择性衰落”。另外，在接收机快速移动时，由于多普勒效应，会使接收到 的各部分信号产生频率偏移。为了防止这种由于多径传播引起的信号衰落，在 d a b d m b 发射机中采用了c o f d m 的方法来传输。这种编码和调制方式，采用了 在数据流里人为加进冗余进行差错保护，以及其他信道编码技术，以便修正传输 中可能出现的差错。 为得到一个均匀的差错分布，使本来相邻的信元在时域和频域上尽可能远地 分开来传送，这样接收端经过去交织恢复信源原来的顺序后，同时也就把可能出 现的“块差错”拆开为相距较远的单个比特差错，从而容易予以修正。 d m b 的传输中，将每个c o f d m 符号人为地延长一段时间，即在每个信元后认 为地插入保护间隔。通过保护间隔，可以确保各种反射波不会干扰当前接收到的 直达信号的码元，经过这样处理后，只要反射波与直达波之间的时延差不超过保 护间隔，所有的反射信号都会增加接收信号的强度，从而改善收听效果。 d m b 使用大量的载波( 又称副载波) 以代替通常单个载波传送一套节目的方 式，即在1 5 哪z 的宽带中发送多达1 5 3 6 个副载波，而不像f m ，仅一个载波。这样， 干扰只会影响个别或少量的载频，而大部分仍不会有噪音干扰。 d m b 的发射一般会采用单频网技术，即在该网络中的所有发射机均工作在相 同的频率。在单频网中，各发射台所有到达接收机的信号，只要这些信号间的时 延差不超过保护间隔，都可建设性地相加形成一个加强的信号，从而增大了覆盖 范围。例如，在一台发射机的发射覆盖区的边缘，可由另一台发射机的信号来同 频交叉覆盖，因而与f m 相比，可具有更高的接收场强。另外，在山村或高大建筑 遮掩处，为防止接收效果变差，还可以另外安装信号填充装置。 d m b 改善移动接收效果的方法可归纳如下表1 2 所示： 表1 2 移动接收过程中出现问题及d m b 的对策 移动接受的问题d m b 的对策 与时间有关的衰落时间交织 与频率有关的衰落 宽带( 多载波) 。频率交织 多普勒频移选择好c o f d m 载波的频率间隔 不同时延的信号在接收机相遇应用保护间隔 传输差错 运用可删除型卷积编码纠错技术 超出单个发射台的覆盖范围采用同步网技术 第一章绪论 5 1 ，4 本文的主要工作 本文围绕交织器、解交织器的f p g a 验证实现中的问题，对于交织原理、应用、 实现等进行了重点分析研究。具体内容安排如下： 第一章简单介绍了差错控制技术，交织技术的应用，及d a b d m b 系统简介。 第二章介绍了交织原理，对不同的交织器进行了分析比较，尤其是对卷积交 织和分组交织进行了重点介绍、比较，同时对交织器在d a b 系统中的应用作了 简 要说明。 第三章针对时间交织器和频率交织器的算法和设计方法作了介绍，给出了几 种设计方案，从速度、存储器、逻辑单元等方面进行了比较，提出了用单口s r a m 作为存储器实现时间交织和解交织的方案。 第四章讨论了优化设计方法，f p g a 的基本知识，以及f p g a 验证设计的主 要流程。重点对硬件实现交织器、解交织器进行了介绍，并给出了硬件电路的具 体实现方法，模块说明及硬件实现仿真结果。 第五章总结与展望。 1 5 本章小结 本章通过对差错控制技术的介绍引出了交织和解交织技术，它是对通信系统 中纠错码纠错能力的重要补充；以及交织与解交织在理论上己经成熟，重点在于 选择何种交织器构造方法。同时对介绍了d a b d m b 系统以及交织器在d a b 系 统中的应用。这将有助于理解第三章要介绍的时间交织和频率交织的算法及其物 理意义。 第二章交织原理简介 7 第二章交织原理简介 2 。1 交织技术的出现 在s h a n n o n 的所谓信道编码定理的证明中，他引用了三个基本条件：( 1 ) 采用随 机编译方式。( 2 ) 编译长度趋于无穷，即分组的码组长度无限。( 3 ) 译码采用最佳的 最大似然译码算法。在此之下，s h a n n o n 证明了在信道中可以实现无差错传输。后 来，在1 9 6 5 年至1 9 6 8 年r g g a l l a g e r 给出了误码率p 。的指数界表示形式： p ，e x p ( - l 1 e 1 俾”( 2 - 1 ) 其中厶为分组码的编译码长度，僻) 0 为可靠性函数，取决于不同的编译码方 式。但是长期以来，由于译码的复杂度，人们将构造信道编码的重点放在了短码 上，即寻找一种可译码的结构使短码具有尽可能大的最小码距，可是通过式( 2 1 ) 可以看出：只要编码分组长度l 足够大，对于白噪声信道在最大似然译码的准则下 就能使差错概率p 任意小，从码空间上来看，可理解为每个码字在整个码空间中 平均占有足够大的区域。码长越长码空间的维数就越高，出现远离平均码距的码 字概率也就越小并趋于零。而在码的构造空间中，由于高维理论的不足，编码研 究的思想多半局限于低维数的短码，这时好码要求有尽可能大的最小码距，它相 对于未编码能提供一定的编码增益，但是其与信道编码定理要求的相差甚远，为 了实现长码码距尽可能接近平均码距获得可译的高维数编码，1 9 6 6 年f o r n e y 首先提 出了利用两个确定的短码来构造长码的串接式级联码“4 ，并且采用了准最佳的广 义最小距离译码，证明了与上式完全类似的结论： p 。c x p ( - l 2 e 2 僻) ) ( 2 - 2 ) 式中e ：僻) t e l 似) ，这是由于e ：( 固采用的是非随机码且译码为准最佳的广义最 小距离译码。显然，要达到同样小的误码率时，工：要大于厶，即其编译码的分组 长度要比理想的随机码与最大似然译码情况下还要长才行。 f o r n e y 的串行级联编译码器实现的典型示意图如图2 1 ，图2 2 所示，由图可见串 行级联码是分别采用己确知的短码作为内码和外码，然后在它们之间接个固定 的交织器它的基本工作机理是：在正常情况下，内外编译码器都在有条不紊的进 8 交织与解交织的算法研究及f p g a 实现 行编译码工作，当外界干扰使得在信道传输中出现了突发错误，而这些错误对于 内码译码器来说是没有能力完全将之纠正的，然而通过交织器可以将这些突发的 集中的错误置乱，使之分散化而进入外码译码器并最终将所有的错误纠正过来， 从而输出正确的码序列。 宣刮外码l f 编辑器i 图2 1 串行级联码编码器示意图 接收码：厂丙码 一 广歹| = 明译码 留腰飘磷寸 - _ 1 窆堡墨i 图2 2 串行级联码译码器示意图 简而言之，它就是通过交织器的置乱作用使错误分散化，从而使外码可以继 续纠正由于内码未能纠正的错误以保证整个码序列的正确性。由于这一革新思想 的引入，给信道编码特别是长码的性能带来了很大程度上的改善。这类串行级联 码很快的便应用于无需追求传输效率的深空通信中并取得了巨大成功。它在采用 最大似然的软判决译码后其误码率几乎达到逼近理想s h 咖o n 限的优异性能。但是 这种结构总的纠错能力取决于内外码的纠错能力，是两者性能函数的级联，这并 没有摆脱传统的短码性能的束缚，当其接近信道容量的渐进状态时，一般传统的 短码的译码过程不但不能纠正错误反而有可能使错误增大，这是一切己知的短码 在性能上存在的不可逾越的鸿沟。但这毕竟是一种革新，是人们在信道编码上的 一次质的飞跃，尤其是交织器的出现使得码的纠错能力有着明显地提高成为了可 能而且随着信道编码的进一步研究尤其是在b e r r o u 等人提出t u r b o 码1 后交织器的 采用更是成为其优异性能不可缺少的重要成因之一o ”。因此也成了许多编码界学 者研究的热点之一。 2 2 交织技术的基本理论 交织其实是通信系统中进行数据处理而采用的一种技术“”，交织器从其本质 上来说就是一种实现最大限度的改变信息结构而不改变信息内容的器件。从传统 上来讲就是使信道传输过程中所突发产生集中的错误最大限度的分散化、不规则 化。因此，具体来讲也许数据置乱器这个称呼更加符合交织器其本质，会让人们 对交织器的基本工作机理有更多的感性认识。从一个最为简单的交织器示意图( 如 匾 一蕾 第二章交织原理简介 9 图2 3 所示) 可以看出， 土匹p 鱼 对于一个信息序列x ，i 时刻从交织器输出的第i 个信息位对应于输入的第筇o ) 个信 息位。这个模型表明l ，- i x 僻) ，而对应的可以得到石一，( 1 ，) ，其中j ，为解交织 器，即j 。= f 。对于一个实际应用的交织器来说它是有周期性的，可以用 石o ) - t 一万( f - t ) ，式来表示，这里的t 其实就是通常所说的交织长度。有了周 f o 1 r 一1 1 来表示，其中第一行代表的是原信息列中的各信息位，而第二 石。万l 石r lj 表达式。i l i i 对于整数n ，m 如果满足万( f ) 一石o - n ) + m ，那么就称这两个交织器是等 1 其中1 在矩阵中所处的位置( i j ) 表示交织前序列中的第i 个信息位经过交织后则 成为序列中的躺个信息位，有了1 位置的确定，矩阵也就算基本生成了。举两个简 单的例子对此进行一下说明，对于基本置换矩阵( ：。1 ；) 和( ：；) ，根据生 成矩阵的准则，此两式对应的生成矩阵g p ，分别为q 。仨 刁和 呸- 臣i 习，而对于带有延时的交织器来说，可以在矩阵中用变量。取代而表 入一个新的概念：交织器的延时，它是指在时刻i ，输出的y 。仅与此时此刻或以前的 1 0 交织与解交织的算法研究及f p g a 实现 输入_ ，j s i 有关，且石a ) s i ，用式子来表示就是6t i 一石( f ) z 0 ，相应的 6 一a 。m 。i r n ( i 一石o ) ) 为交织器的最小延时，由此可知所有带延时的交织器都可以通 过延时输入石a ) 一石( f + 6 曲) 而表示出来。所以要全面的表示一个交织器不能单单 的由生成矩阵来表示，为了更好的说明交织器的生成，还要引用延迟矩阵d ，其定 义为d t 01 0o ： o o do o 1 0 o o 00 o0 ： 01 oo 这样对于一个有着最小延时的交织器来讲，就 q i 。g c 。，4 兰i 习。曙i 习2 【j 三i g ：- 。2 ，g c 。，一( 弓兰习 ；i 习2 ( i 弓三) m 习 一g c 。，。2 一【；i 自。( 虽三习一【喜虽习 一般来说一个器件要想正常工作就必须保证其参数配置的合理，对于交织器同样 在这里重点介绍一下交织器的一个主要参数：分散因子。当交织器满足i 一州t s 和 k ( f ) 一石( 叫苫f 或者是k o ) 一万( 州t f 和i - j l 之s 时，就说此交织器是有正常的分散 第二章交织原理简介 1 1 a y 一万( ，) 一石( f ) ，此时如果xcs ，a y 急t ，那么就说此交织器有正常的分散因 子，表示为( s ，t ) ，它的物理意义就是将输入端长度小于t 的一段序列在输出端使之 各信息位都相邻或大于s 个单位。对应的解交织器的分散因子便是( t ，s ) ，对于一个 固定的交织长度，交织器根据需要可以有不同的分散因子。而一般来说在这些分 散因子中总有一个最大的，当取( s + 1 ，t ) 或( s ，t + 1 ) 时就不会满足此交织器工作在正常 状态下的要求。在一般情况下，如果想要交织器工作在最佳状态，除了其它因素 外，最为重要的便是要使交织器拥有最好的分散因子。 2 3 交织器的分类 数字通信中常用的交织器按照交织对象可以分为符号交织和比特交织，按照 交织的方式可以分为伪交织和周期性交织，按照交织的域可分为频率交织和时间 交织等三种。 一按交织对象分： 1 比特交织比特交织是将v 路并行的比特流中每一路的顺序按照不同得规则 置换，这样交织后v 比特数据) ，0 0 ，口j ，口，却) 与交织前 y 。一( 4 岍，口，a ，却) 比特间的对应关系是错位的 2 符号交织符号交织则是对数据符号的位置按一定规则进行倒乱，即将m 个 v 比特并行数据y 一( y o ，“，丸) 变换成y 。一( y o ，西，y ：) 。 二按交织方式可分为： 1 伪随机交织器伪随机交织器实际上也可以看成是分组交织器，只是数据是 经过伪随机排序处理的，要注意的是每个码元只能一次。假设有一个交织器其大 小为1 5 ，这是应选择一个本原多项式，使其周期等于1 5 ，如：1 + d + d 4 。这是一个 m 序列，其最大周期为1 5 ，信息序列为：工一万。“) = o , o , l o ，l l o ，o , l o , l l l l 0 伪随机序列为 8 ，1 ，3 ，7 ，1 5 ，1 4 ，1 3 ，1 0 ，5 ，1 1 ，6 ，1 2 ，9 ，2 ，4 。则 经过交织器的交织后，工一 o l l o , o , i , l o , l 1 , l 1 , l o , o ) 。伪随机交织器由于没有固 定的周期，对于各种信道特性均有很强的适应能力，尤其是当信道上存在对敌方 的有意干扰时，更能显示其优越性，故多数应用于扩频通信和保密通信。 2 周期性交织器周期性交织器的交织排列关系是时间的周期函数。有两种常 交织与解交织的算法研究及f p g a 实现 用结构：块交织和卷积交织。它们都是同步交织器，每时刻存入一个数据，同时 读出一个数据。数字通信中一般采用的同步交织有两种： 1 1 块交织亦即是分组结构的交织器。 1m + l r n 一1 ) m + l 2m + 2 f n 一1 ) m + 2 m2 mn m m 行n 列矩阵 图2 4 分组交织器原理框图 分组结构的交织器是把待编码的m * n 个数据位放入一个m 行n 列的矩阵中， 即每次是对m * n 个数据位进行交织。通常每行由n 个数据位组成一个码子，而交 织器的深度，即行数为m ，其结构示于图2 4 。由图可见，数据为被按列填入数据 存储矩阵中，而在发送时却是按行读出的，这样就产生了对原始数据位以m 个比 特为周期进行分隔的效果。这实际上是一个存储器阵列。将数据按列写入，然后 按行读出，完成交织。在接收端解交织操作则是相反进行的，即是按行写入，按 列读出。这种形式的交织器结构简单，但是数据延迟时间长，所以需要的存储容 量大。 分组结构的交织器的一些重要特性如下： ( 1 ) 任何小于n 的连续信道码元错误在解交织器输出端转化为独立的随机错 误，相互之间有至少m 个码元隔开。 ( 2 ) 任何b n 个突发错误，这里b l ，将使解交织器的输出发生不超过【b 】个 突发码元错误。每个输出突发错误与其余突发错误之间至少有m b 1 个码元隔开。 符号【x 】表示不小于x 的最小整数。符号 x ) 表示不大于x 的最大整数。 ( 3 ) 具有n 个码元问隔的单个错误周期序列将使解交织器输出产生单个长度 为m 的突发错误。 ( 4 ) 交织器与解交织器的端到端延迟大约为2 r a n 个码元时间。精确的说， 在传输开始之前，只需m ( n - 1 1 + 1 个记忆单元被填充( 只要m n 矩阵的最后一列的 第一个码元被填充) 在接收端相应数量的码元被填满，译码才能开始进行。这样 第二章交织原理简介 一来最少的端到端的延迟为( 2 m n 2 m 2 ) 个码元时间，不包括任何信道传输延迟。 ( 5 ) 每个单元( 交织器与解交织器) 都需要m n 码元的存储空间。但是由于 m n 矩阵必须( 几乎) 填满才能被读出，因而每个单元使用一个2 m n 码元的存储空 间，以便在清空其中一个矩阵式可以填充另一个。 通常对于使用纠正单个错误编码的情况，交织器参数的选择应当使得列数n 大于预期的突发噪声长度。行数i n 的选择取决于所使用的编码机制。对于分组码， m 必须大于分组长度，而对于卷积码，i n 必须大于卷积长度。由此长度为n 的突 发噪声在每个码字中最多产生一个错误。对于纠正t 格错误的编码，n 只需大约与 其突发长度的t 分之一。 2 ) 卷积交织在大多数情况下卷积交织可以替代块交织。 ( 1 ) 卷积交织原理及性质 ( n n ) 的卷积交织器满足如下要求【1 9 1 ：在该交织器输出的任何一个长度为 n ，的数据串中不包含交织前原来数据序列中相距小于n ，的任何两个数据。显然， 在发送端采用交织器，在接受端就要用解交织器把数据恢复过来。可以证明( n ：，n 。) 的交织器相对应的交织器自身是一个( 1 1 ，n ：) 的交织器。 对于( n i ) n ，) 的卷积交织器来说，有两个性能是设计着所关心的：一个是编 码延迟d ，它定义为从数据经过交织和解交织后所引起的最大延迟。另一个是交 织器和解交织器的存储容量s 和s u 个符号单元。对于( n 。n 。) 的交织器有如下 关系： d 苫n 2 x ( n 1 1 ) s + s u 土d 设计交织器时，希望其d 和s 、s u 尽量小。 卷积交织器最早由f o m e y l l 8 】和r a m s e y 1 9 1 提出，下面讨论的这种结构由f o m e y 给出。r a m s e y 的方案实质上类似。如图表示了卷积交织器和解交织器的原理。该 卷积交织器其实就是前面提到的n ，= b m ，n ，= b 的卷积交织器。 卷积交织器由一系列先入先出( h f o ) 移位寄存器组成，每个移位寄存器遇 有固定的延迟，当新的信号输入时，寄存器内存储的信号被新输入的信号所替代， 原信号变为输出信号的一部分，如图2 5 所示的卷积交织器，交织器的输入端的输 入符号数据按照顺序分别进入b 条支流延迟器，每一路延迟不同的符号周期，第 一路无延迟，第二路延迟m 个符号周期，第三路延迟2 m 个符号周期，第b 路则延迟( b 一1 ) m 个符号周期，它属于同步交织，每时刻存入一个数据，同时 1 4 交织与解交织的算法研究及f p g a 实现 读出一个数据。交织器的输出端按照输入端的工作节拍分别同步输出对应支路经 过延迟的数据。也就是卷积交织每条支路符号数据的延迟节拍为： d 1 = ( i - - 1 ) m i - - - - - 1 ，2 ，b 一1 ，b ： 解交织器将交织器打乱的字节序列重新排列恢复原始码子。因而它的实现与 交织器在延时电路设计上正好相反。第一路延迟( b 1 ) m 个符号周期，第二路延 迟( b 2 ) m 个符号周期，第三路延迟( b 一3 ) m 个符号周期，第b 路无延 迟。也就是卷积解交织每条支路延迟为： d i = ( b - i ) m i = 1 ，2 ，b ： 设交织器输入序列 a i ) ，输出序列为 a j ) ，作一个排列例子，若b = 3 ，m - - - - 4 ，按 照每行b m 个元素分成m 组，每组b 个元素排列，由移位寄存器的性质，根据交 织器的原理图可以得到i ，i 间对应关系如下： 输入序列： 第一组 1 ，2 3 ， 1 1 , 1 2 , 1 3 , 2 4 2 5 ，2 6 ， 3 6 , 3 7 ，3 s , 4 8 ，4 9 ，5 0 , 第二组 3 ，4 ，5 ， 1 5 ，1 6 , 1 7 ， 2 7 ，2 8 , 2 9 ， 3 9 , 4 04 1 , 5 1 , 5 2 , 5 3 ， 第三组 6 ，7 ，8 ， 1 8 , 1 9 ，2 0 ， 3 0 , 3 1 , 3 2 , 4 2 ，4 3 ，4 4 ， 5 4 , 5 5 ，5 6 , 第四组 9 ，1 0 ，1 1 ， 2 1 ，2 2 ，2 3 ， 3 3 ，3 4 ，3 5 ， 4 5 ，4 6 ，4 7 ， 5 7 ，5 8 , 5 9 ， 输出序列： 第一组 第二组第三组第四组 谚0谚写0妨60 ，妨霉毋绣 1 2 , 1 ，o ，1 5 ，4 ，0 ，1 8 ，7 ，o ，2 1 , 1 0 , o 2 4 ，1 3 , 2 ，2 7 ，1 6 , 5 ，3 0 , 1 9 ，8 ，3 3 ，2 2 ，1 1 , 3 6 , 2 5 ，1 4 ,3 9 ，2 s , 1 7 ，4 2 , 3 1 , 2 0 , 4 5 ，3 4 , 2 3 , 4 8 ，3 7 ，2 6 ， 5 1 , 4 0 ，2 9 ,5 4 , 4 3 , 3 2 ，5 7 ，4 6 ，3 5 ， 根据上述例子可以得出，输出排列序列实际上是输入排列序列的一个置换。 并可以得出： a 交织器输入两个相邻数据经过( b m ) 个符号周期，出现在输出端。其中 b m 由移位寄存器本身造成，如输入1 6 ，1 7 的相邻输入数据，交织器输出相邻b m = 1 2 个码符。 b 交织器输入端任何间隔低于b m 个符号的两个符号，在交织器输出端最小 间隔为b 个码符，如本例2 4 ，2 7 间具有最小输出间隔b - - - - 3 个码符。 c 间隔为b m - - 1 的k 个周期性单位差错，在解交织器输出端变为长度为k 个突发错误。 第二章交织原理简介 在实际使用中，b 、m 的值选择与交织器级联的纠错码的毋字长有关。若纠错码采 数据被分散到b 个包中；同时经过交织后的数据如果加入了长为b t 的突发错误， 产1h 面面 弋 肛卜一= 。 蒜黑= 留蒿= 忑 蒜。；高音。+ 回+ 畦 一艘 q 卧- o 虻j 画亘二卜m 岫址一 1 6 交织与解交织的算法研究及f p g a 实现 lj 1 b f ， 7 ，7 f j b ，77 ， ，f ，? j ，f ， b f7 ，“ r 2 6 交织后数据分布示意图 3 ) 其它的一些交织器介绍： 首先假设输入信息矩阵为： 工1x2工3 x4x5x6 工1x8工9 善1 0石1 1x 1 2 并1 3x 1 4 工1 5 x 1 6x 1 1x 1 8 x 1 9x2 0 x2 1 a 螺旋形交织器： 假设写入形式如表所示，读出时以对角线方式螺旋读出，如下所示： x 1 9 x 1 7 x 1 5 x l lx 7 x 5 x 3x 2 8 x 1 8 x 1 4x 1 0 b 奇偶交织器： 假设输入序列如表所示，在写入交织器时先写入奇数位( 行方向) ，如表a 所 示。然后以列的方向输入表的偶数位，如表2 2 所示，将表2 1 ，表2 2 合并成表 2 3 ，这样久把原序列均匀化了，如此安排可以保证每一位均有唯一的位置，即不 会漏排也不会重复。 第二章交织原理简介 表2 1 奇数位序列 x lx 2x 3x 4x 5x 6x 7x 8x 9x 1 0x 1 1x 1 2 x 1 3x 1 4x 1 5 y 1 一y 3 一y 5 一y 7 一y 9 一y 1 1 一 y 1 3一y 1 5 表2 2 偶数位序列 表2 3 奇偶交织器的输入序列 c 随机交织器： 随机交织器是最近刚刚兴起的一种交织器，其实也可以说它是随着t u r b o 码的 产生而被日益广泛的应用起来的。顾名思义，随机交织器应该实现的思想便是随 机交织过程，但是现在所说的随机交织器大部分恰当的来讲应该称之为伪随机交 织器。这是因为译码器中的交织器是要与编码器中的交织器相对应的。而分组交 织器是以规则的顺序进行交织，所以在收发两端可以通过一定的协议来确定交织 器的工作方式。但是在采用了随机交织器的t u r b o 码系统中，由于对于每一组信息 序列所产生的交织后的结果是随机性的，而译码器则要求对每帧数据都要有相应 的交织顺序，所以在传输编码序列的同时，在信道上还要传输交织器的信息，这 不仅会加大译码器的复杂度，而且也加大了信道负载，而且如果在中途若交织信 息出现错误，则会使译码的误码增多，所以现在所采用的随机交织器都是伪随机 的，是事先经过随机选择而生成的一种性能较好的交织方式，然后将其做成表的 形式存储起来而进行读取的。 随机交织器的随机性能主要取决于随机数的产生方式、交织器主要参数s 取值 的选取等方面。现在主要有利用基于线性取余法的贝斯一德拉姆洗牌技术以及对 系统时钟进行随机抽样产生随机数的方法。贝斯一德拉姆技术主要是利用式 以“一( 窿x 。+ c ) m o d m ( 2 - 3 ) 产生随机数，并使数之间存在下述的串行相关性 一i 1 x 。“一( 口x 。+ ! 等c ) m o d m ( 2 - 4 ) 一1 在这里ct 小。很显然m 的取值越大，交织前后序列的相关性就越小，所以效果就 会更好。 交织与解交织的算法研究及f p g a 实现 除了随机数的产生方法不同之外，现在人们将目光都投向了如何利用交织器 的主要参数而设计出较好的随机交织器这方向上来，由此介绍几种基本的随机 交织器。 1 ) s 随机交织器这种交织器其随机数的产生是与其它交织器一样的，只不过 它有一个附加条件，即要求在交织前的信息序列长为s 的各信息位在交织后必须相 邻大于s + 1 个单位，其实也就是让交织器拥有最大分散因子参数的特性。目前在 t u r b o 码中采用的大部分都是这种交织器或是由此而演变出的s 系列随机交织器。 2 ) t 随机交织器这种交织器是一种特殊的随机交织器，它要求码字中的任何 一对相邻的信息位在交织后的距离要大于整个码的约束长度，它只适合于那些由 重量为2 且两个“1 ”信息元相邻k 个单位的码而产生的最小汉明重量的信息序列。 一般来讲，只有采用k = 3 的卷积码才能产生出符合此种要求的随机交织器。 3 ) s - t 随机交织器此交织器是对s 随机交织器和t 随机交织器两种产生条件的 综合，实现起来就更加困难了，属于较为特殊的随机交织器。 综上所述，从总体上来讲s 随机交织器比较容易生成，而且生成速度较快，是 较为理想的随机交织器，而其它两种只是在特殊场合下才得以应用。所以现在应 用的大部分随机交织器应该都是属于s 随机交织器d a b 系统中采用的频率交织器 就是按照贝斯一德拉姆技术产生的随机数进行交织彳导。 2 4 本章小结 本章从交织器的出现以及交织器在现代通信系统中所起的作用开始，详细介 绍交织器的基本理论，交织器的分类，并对不同的交织器进行了分析比较。 第三章时间交织与频率交织算法及实现方法 1 9 第三章时间交织与频率交织算法及实现方法 3 1 时间交织在d a b 系统中的物理意义及算法 3 1 1 时间交织器的物理意义 由第一章介绍的差错控制技术可以知道通信系统中纠错能力的强弱除了编码 本身的能力外，还和交织器的作用有关。信道编码的纠错能力在很大程度上取决 于接收序列错误分布情况。尽量使差错均匀分布对纠错是有利的。但是，移动无 线信道特征是，在相对较宽的范围内，出错几率小，而在相对较窄的范围，具有 较大的传输衰减和群延时失真，相邻信息单元同时出现差错的概率一般很大，即 突发错误可能性大。这种错误不可能仅仅通过信道解码予以解决，而应当结合“交 织器”来使错误均匀分布。接收方对接收信号去交织后，成块的突发错误将被分 散开。借v i t e r b i 解码算法的纠错能力，就可以得到纠正，从而得到很好的抗干扰 性能。 根据第一章中对d a b d m b 系统的简介可知，在f i c ( 快速信息通道) 中没 有采用时间交织，这是基于实时性的考虑。因为采用时问交织会带来3 8 4 m s 的传 输延时，这对接收机解调控制信息是不允许的。增强f i c 的抗干扰性能主要通过 循环重复，增大冗余来实现的。以降低码率为代价来获取传输可靠性保障。在 d a b d m b 系统中，只有对m s c ( 主业务信道) 中的信息采用了时间交织。另外 d a b 系统中传输帧的构成包含同步通道( s y n