实现卷积交织的几种实用方法

1、徐元欣王匡仇佩亮浙江大学 信息与通信工程研究所, 浙江 杭州 310027摘要 卷积交织在数字通信系统中得到了广泛的应用 本文将分析卷积交织原理 然后提出几种实用的实现方法 并对其性能进行了分析对比关键词 卷积交织 atsc dvb rs 码 hdtv中图分类号 tn911.22 文献标识码 a引言1在数字通信中 信道中除了随机干扰 常常由外来的脉冲干扰会引起突发错误如电机的突发噪声电火花等 同时同频道干扰 相位噪声 多径和衰落信道等都会引起突发错误 也就是说发生的错误 有很强的相关性 当发生一个错误时 往往波及后面的很多数据 导致一片数据都发生错误 使突发 错误的数目超过了纠错码的纠错能力

2、为了使纠错码能抵抗这些突发错误 在实际应用中纠错编码往 往要结合数据交织技术 在发送端加上数据交织器 在接收端加入去交织器 使得信道的突发错误分 散开来 把突发差错信道改造成独立的随机差错信道 从而可以充分发挥纠错编码的作用1 加上交 织后 系统的纠错性能可以提高好几个数量级 美国 astc 和欧洲 dvb 的数字电视传输标准中都采 用了数据交织技术23下面以 atsc vsb 传输系统(如图 1)为例加以说明 为了提高通信系统的可靠性 纠错编码则可 采用级联码的方式来进行误码控制 一般采用两级串联 第一级采用具有很强纠错能力的极大最小距 离可分码(mds 码)rs 码 称为外码 第二级可采用

3、短的分组码或卷积码 称为内码4 atsc vsb传输系统采用了这种形式rs(207,187)作为外码了存在前面讲述的突发错误外接收8 电平 tcm 格状编码作为内码在数据传输中除端内码采用 viterbi 算法进行格状译码时当接收信号的信噪比较低时会出 现差错扩散也会引起突发错误5这些突发错误就可能超过 rs 码的纠错能力因此为了充分发挥 rs 码的 纠错能力在 rs 外码和格状编码内码之间加入交织器dvb 的传输系统采用的是 rs(204,184)码在 rs 码后 也加入了交织器下面介绍卷积交织的原理然后提出实现卷积交织的实用优化方法上频(a)发射部分谐滤波器(b)接收部分图 1 astc

4、vsb 传输系统卷积交织原理实际上交织过程也可以算是一个编码过程2通过把经过纠错编码的数据进行一定的排列组合提高原有纠错码的纠突发错误能力在数字通信中一般采用的同步交织有两种同步与定时数据 去 扰rs 解 码去 交 织tcm 解 码相 位 跟 踪均 衡ntsc 抑制if滤波 和解调调器数 据 扰 码rs 编 码交 织tcm 编 码复 接导 频 插 入vsb 调 制射 频变段 同 步 场 同 步8电路与系统学报第 6 卷(1) 块交织它是一个二维存储器阵列 (n b)将数据先按行写入然后按列读出完成交织过程相应地去交织过程是将数据按列写入再按行读出块交织结构简单但数据延迟时间长而且所 需的存储器

5、比较大7(2) 卷积交织( n2 , n1 ) 的卷积交织器满足如下要求在该交织器输出上的任何一个长度为 n2 的数据串中不包含交织前原来数据序列中相距小于 n1 的任何两个数据显然在发送端采用交织器在接收端就要用去交织器把数据恢复过来可以证明 (n2 , n1 ) 交织器相对应的去交织器自身是一个7( n1 , n2 ) 交织器对于 ( n2 , n1 ) 的卷积交织器来说有两个性能是设计者所关心的一个是编码延迟 d它定义为从数据经过交织和去交织后所引起的最大延迟号单元对于 ( n2 , n1 ) 交织器有如下关系 d n2 (n1 1)另一个是交织器和去交织器的存储容量 s 和 su 个符

6、(1) s s u d设计交织器时希望其 d 和 ssu 尽量小卷积交织器最早由ramsey 7 和forney 6 提出下面要讨论的这种结构由forney给出ramsey的方案实质上与之类似图2表示了卷积交织器和去交织器的原理交织器的输入端的输入符号数据按顺序分别进入b 条支路延迟器每一路延迟不同的符号周期第一路无延迟第二路延迟m 个符号周 期第三路延迟2m 个符号周期.第b 路则延迟(b-1)m个符号周期交织器的输出端按输入端的工作节拍分别同步输出对应支路经延迟的数据也就是卷积交织每条支路符号数据的延迟节拍为di=( i -1)mbi=1,2, b(2)去交织器的各个支路的延迟数与交织器相

7、反第一路延迟(b-1)m个符号周期第二路延迟(b-2)m个符号周期第三路延迟(b-3)m 个符号周期.第b 路则无延迟也就是卷积去交织每条支路延迟为dui=( b- i )mbi=1,2, b(3)由此可知该卷积(去)交织器有以下性质6(1) 数据经过交织器与去交织器所产生总延迟(即编码延迟)d =b(b-1)m 个符号周期(2) 交织器或去交织器所需的存储容量s = su = b(b-1)m/2 个符号单元(3) 交织器的两个相邻的输入数据经过交织器后出现在输出端时其间隔增加为bm个符号周期交织器输入端任何间隔低于bm个符号的两个符号在交织器输出端最小间隔为b个符号 该卷积交织器其实就是前面

8、提到的n2 =bm, n1 =b的卷积交织器8112i3去解码来自b-2纠错编码ib-1bbi=1,2, b图 2 卷积交织器和去交织器在实际应用中m值的选择与交织器前面级连的纠错码的码字长有关若纠错码采用(n, k)b码为了实现方便一般取:n = bm(4)(b-1)mm(i-1)m2m信道2m(b- i)mm(b-1)m9第 1 期徐元欣等 实现卷积交织的几种实用方法如atsc 采用rs(207,187)以及b=52, m=4的卷积交织器这里rs码的码字长为207但加上段同步头每个传输包长为208dvb采用rs(204,188)卷积交织器的b=12,m=17称该(去) 交织器为 (n b)

9、卷积(去)交织器纠错码(n, k)级连上(n b)卷积(去)交织器可近似于一个纠错码(bn, bk)1 这也可由图3的示意图得知它表示了编码的符号数据经交织后的顺序被交织打乱的情况其中打斜线的每 个符号为编码来的某个包的连续数据可看出经过(n b)卷积交织器后由纠错码rs(n,k)编码来的n长的连续的包数据被分散到b个包中同时经交织后的数据如果加入了长为 bt 的突发错误经过 去交织后这些长为bt个的突发错误就被分散到相邻的b个包中每个包t个错误假设纠错码(n, k)的 每个码字包能纠t个错这样加入了该卷积交织器后能纠长为 l=bt 的突发错误在atsc 中 t=10能抵抗l=520 个符号周

10、期的突发错误 dvb中个符号周期的突发错误可以看出(n b) 卷积交织与(n突发错误性能数据延迟上是相同的t=8 能抵抗 l=96b)块交织在对付但前者所需的总存储器容量比后者少一半故实际中常采用卷积交织3卷积交织的实现方法3.1 移位寄成器法图 3 交织后数据分布示意图由图2 可知卷积交织实际就是将数据进行不同的延迟以使连续的数据分散开来简单的方法就是每条延迟支路可用fifo 移位寄成器来实现这里称为移位寄成器法 去交织器都所需的寄成器数目s = s u = b(b-1)mk/2实现时最直观对于交织器和(5)这里假定每个符号为 k比特当b和m比较小时采用该方法简单实用但b和m 都比较大时采用

11、该方法就需的大量的寄成器如实现dvb 的交织器和去交织器所需的寄成器数都是8976atsc 则需42432目前在fpga中实现或 asic 芯片设计中都很难承受这么多的寄成器采用该方法实现起来代 价非常大3.2 ram分区循环移位法 该方法就是将移位寄成器法中的(去)交织的各个支路的fifo延迟采用ram来实现 通过控制ram的读写就能实现卷积交织为了叙述方便下面以卷积交织为例讲述这种方法如图4所示除了第1条支路不需延迟外将ram分为b-1个区每区对应于一条支路每区的大小si= ( i - 1)mi = 1,2, b(6)为了充分利用ram的空间 对于每区按 读-修改- 写 方式进行循环操作

12、也就是在每个符号节拍当前的读写地址相同 只是要先读出该地址单元的原来的符号数据后 再写入新的数据 每区自己的相 对地址ai 每更新一个单元按模 si 进行循环加1 该区是每隔b个符号数据节拍才更新一个单元 也就 是ai 每b个数据才加1 由此可得出每路数据延迟di = s i b = ( i -1)mbi = 1,2, b上式(7)与 (2)式相同也就是每条支路达到了所需的延迟该方法能完成卷积交织 设第i区的首地址为hi 则(7)i 1i 1hi s j ( j 1)mi = 2, b(8)j 1 j 1所以对于整个ram的第n个节拍的读写地址指针应为(n = 0,1,2, . )an= hi

13、+aiai = (ai +1) mod si i = n mod b +1(9)nbb b数据方 b10电路与系统学报第 6 卷该处的i表示第n个节拍的交织数据对应的第i条延迟支路由式(6) (8)和(9)就产生ram的读写地址(见图5)其中模b复位器按交织输入的符号数据节拍在每包数据起始时从0开始进行模b计数并在计数 值为0时停止读写ram和1时产生清0复位信号相类似地可采用ram分区循环移位法来实现卷积去交织这里不祥述可看出采用该方法实 现卷积交织所使用的存储器为ram其容量(bit)为bs = s u = ) si = b(b-1)mk/2(10)i =2与移位寄成器法所需数目相同对于实

14、现dvb的交织器和去交织器都只需1122 8=8976比特的ram而atsc 都只需5304 8=42432比特的ram使所用存储器的代价最小实现成为可能但这种方法还需用于存放每条支路的相对地址的fifo3.3ram整块循环移位法 1 其容量为(b-1)个单元每个单元的大小为 log 2 max si j123in输出输入 i i ib图 5 ram 分区循环移位法地址产生框图图 4 ram 分区循环移位法原理同样为了叙述方便下面以卷积交织为例讲述这种方法该方法是将分区循环读写改为整块循环读写 要求每条支路的当前输入数据是靠相邻的下一条支路的读写地址指针来输出以达到延迟的目 的 其原理如图6所

15、示 同样为了充分利用ram的空间 对ram按 读-修改-写 方式进行操作 假 设当前交织的第n节拍的数据是参与第i条延迟支路 对应的ram读写地址(绝对)为an 支路地址为ai= an 那么第n+1 节拍的数据就对应于第i +1 条延迟支路 相应的读写地址为an+1 支路地址为ai+1 =an+1那么an+1 = an + ( i-1)mi = n mod b +1(11)经过b个节拍也就是卷积交织一个b路循环后的第n+b节拍的数据应连接第i条延迟支路第n+1+b节拍的数据就对应于第i +1条延迟支路这时第i +1条的支路地址ai+1 应朝第i条的支路地址ai 的方向前进一拍以达到对第i条支路

16、的延迟作用比如图6中画出的虚线支路1假定ram容量为s个单元(12)2则an+b = an+b mod s = (an 1) mod s又由图6可知如不限定ram容量则ban+b an= (i 1)m = b(b-1)m/2i 1结合式(12)(13)就可得该方法所需的ram的单元数目应为s = b(b-1)m/2 +1(13)(14)这样第i条延迟支路写入的数据要经过( i -1)m个b路循环后的第i +1条延迟支路时刻才读出由此可得出每条支路数据的延迟为di = ( i -1)mb +1i = 1,2, b(15)寄成器寄成器ramaahs存放相对地址ms模 b 复位i = n mod b

17、 +1 复位m2m(i-1)mram(b-1)m取模 s iif si , 赋 011第 1 期徐元欣等 实现卷积交织的几种实用方法将上式与(2)式相比较该方法的每条支路数据比 (2)多延迟一个节拍但输出数据的相互顺序分布满足卷积交织的要求在ram容量为s单元时第n节拍的数据时刻的读写ram的地址an+1 = an + ( i-1)m mod si = n mod b +1(16)该处的i表示第n个节拍的交织数据对应的第i条延迟支路由式(14)(16)可得到ram整块循环移位法的地址产生框图如图7所示其中模b复位器按交织输入的符号数据节拍在每包数据起始时从b-1开始 进行模b计数并在计数值为0

18、和1时产生清0复位信号同样可采用 ram整块循环移位 法来实现卷积去交 织这里不祥述 该方法所需存储器 ram的容量只比前 面ram分区循环移 位法多一个单元 对于实现dvb 的交 织器和去交织器都 只需 11238=8984输出输入比特的 ram而atsc 都只需53058=42440 比特的ram可看出该方法就省去了前面所需的fifo控制也简单使实现的代价更小所以是用ram实 现卷积交织的最优化方法但该方法对卷积交织的数据都要多延迟一个符号节拍图8是仿真采用ram整块循环移位法来实现atsc (b=52, m=4, s=5035)的卷积交织的ram地址的某几段的结果假设an 初始值为510

19、1实际中可为任意初值图 6ram 整块循环移位法原理图 7ram 整块循环移位法地址产生框图n=00, 0,4, 12, 24, 40, 60, 84, 112, 144, 180, 220, 264, 312, 364, 420, 480, 544, 612, 684,760, 840, 924,1012,1104,1200,1300,1404,1512,1624,1740,1860,1984,2112,2244,2380,2520,2664,2812,2964,3120,3280,3444,3612,3784,3960,4140, 432,4512,4704,4900,5100n=2085

20、301,5301, 0, 8, 20, 36, 56, 80, 108, 140, 176, 216, 260, 308, 360, 416, 476, 540, 608, 680,756, 836, 920,1008,1100,1196,1296,1400,1508,1620,1736,1856,1980,2108,2240,2376,2516,2660,2808,2960,3116,3276,3440,3608,3780,3956,4136,4320,4508,4700,4896,5096n=10660,5100,5104,5112,5124,5140,5160,5184,5212,524

21、4,5280, 15, 59, 107, 159, 215,275, 339, 407, 479,555, 635, 719, 807, 899, 995,1095,1199,1307,1419,1535,1655,1779,1907,2039,2175,2315,2459,2607,2759,2915,3075,3239,3407,3579,3755,3935,4119,4307,4499,4695,4895,图 8采用 ram 整块循环移位法实现卷积交织的仿真结果由图8可看出经过卷积交织第n=0节拍的数据延迟了1个节拍第n=1节拍的数据延迟了209个节拍 .第n=51节拍的数据延迟了106

22、09个节拍寄成器复位器5100模 b复位寄成器rams取模 sif s ,减去 sanm1,23 mi(i-1)mi+1ramb(b-1)m1,212电路与系统学报第 6 卷结束语本文在分析了卷积交织原理基础上提出了三种实现方法 法和ram整块循环移位法其性能对比见表1当卷积交织的b4移位寄成器法ram分区循环移位m比较大时则所需的存储量就大ram整块循环移位法 尤其后者ram整块循采用ram实现卷积交织的方法使实现成为可能其中的ram分区循环移位法分别在我国hdtv的第1代第2代样机中得到了成功应用从成本和规模上讲 环移位法在hdtv的asic 芯片设计中具有重要的意义表1三种实现方法对比方

23、法所需总的存储器控制数据总延迟(符号)周期复位总的规模b(b-1)m b(b-1)m移位寄成器法ram 分区循环移位法 ram 整块循环移位法b(b-1)m k 个寄成器b(b-1)m k 比特 ram简单复杂,需 fifo可以可以很大较小 最小b(b-1)m +2 可以b(b-1)m+1k 比特 ram 较简单参考文献1 proakis, j. g. . digital communicationsm. 3rd edition. new york: mcgraw-hill, 1995. 468-470. 2 atsc. atsc digital television standards .

24、doc. a/53 , 1995-09.3 etsi. european standard (telecommunications series) dvbs. 1997.4 姚庆栋 梁慧君 戴文琪. 数字无线传输m. 杭州: 浙江大学出版社 1992. 247-248. 5 王新梅 肖国镇. 纠错码原理与方法m. 西安: 西安电子科技大学出版社 1996.6 forney, g.d.burst-correcting codes for the classic bursty channelj. ieee trans. comm. tech., 1971, 19:772-781. 7 ramsey j l. realization of optimum interleavers j. ieee trans. inform. theor y, 1970, 16: