法律状态公告日
法律状态信息
法律状态
2015-05-20
未缴年费专利权终止 IPC(主分类):H04L1/00 授权公告日:20110720 终止日期:20140403 申请日:20080403
专利权的终止
2011-07-20
授权
授权
2008-12-10
实质审查的生效
实质审查的生效
2008-10-15
公开
公开
技术领域
本发明涉及的是一种用于通信技术领域的译码方案,具体说是一种应用于传统二进制Turbo码和双二进制Turbo码通用译码方法。
背景技术
现代数字通信的奠基人香农早在1948年就在信道编码定理中指出,只要随机编码的码长足够大,就可以进行无限逼近信道容量C的通信并使错误概率任意小。但香农只是从理论上证明了编码极限的存在,却没有构造一种编译码结构逼近这种极限。自香农之后,许多性能优异的码相继出现,BCH码、RS码和卷积码等,它们都能获得不错的性能,但是与香农提出的性能限,还存在不少差距。
直到Turbo码的发现,才使得信道编码理论在逼近香农极限的道路上迈出了一大步。1993年,Berrou,Glavieux和Thitimajshima在ICC的会议上首次提出了Turbo码,通过对子码的伪随机交织实现大约束长度的编码,采用软输入软输出迭代译码来逼近最大似然译码。仿真结果表明,在信噪比为0.7dB的AWGN信道条件下,采用(21,37)递归系统卷积码作为分量码,交织深度65536,迭代18次之后误码率下降到10-5以下,离香农极限仅仅只有0.7dB。
1996年Berrou提出了双二进制Turbo码,与传统二进制Turbo码相比,双二进制Turbo码具有以下优点:交织深度是经典Turbo码的一半,译码时延减小;通过符号间交织增大最小自由距离,消除误码平层;相同复杂度译码器下,双二进制Turbo码的纠错性能优于传统Turbo码;码率删余对于双二进制Turbo码的性能影响小于传统Turbo码;采用循环递归系统卷积码做子码,它不需要“收尾比特”就可以使每一帧具有相同的初始状态和终止状态。由于其优秀的性能,目前双二进制Turbo码已经广泛应用于很多无线通信的标准中,如WiMAX(IEEE 802.16)和欧洲卫星网络标准(DVB-RCS)都采用了双二进制Turbo码。
从译码算法角度来说,Turbo码译码算法分为两类:一类是由Viterbi算法演化而来的SOVA算法,一类是基于后验概率的MAP算法,以及由MAP算法延伸出的Log-MAP算法和修正Max-Log-MAP算法。Log-MAP的算法译码性能比较好,但是需要大量的指数和对数计算,复杂度高;而Max-Log-MAP算法则完全用加法和求最大值来替代对数运算,复杂度低,有利于硬件上的实现。从输出方式来说,双二进制的译码又可以分成基于符号和基于比特的后验概率对数似然比的译码方式。
双二进制Turbo码与传统的二进制Turbo码相比有很多优秀的性能,但是目前很多通信标准采用的Turbo码还是传统二进制Turbo码,一些比较新的通信协议如3GPP-LTE,UMB等也采用的是传统二进制Turbo码。而目前的Turbo码译码器都只是专用的Turbo码译码器,并没有一个既能够对传统二进制Turbo码译码,也能够对双二进制Turbo码译码的Turbo码译码器。
图1所示为传统二进制Turbo码的Log-MAP算法前向状态度量αk(s)递推计算的基本模块ACSO(Add-Compare-Select-Offset)结构。双二进制Turbo码的前向递推αk(s)的基本结构如图2所示,由于是四个数取最大值的结构,因此可以由两个ACSO模块加上一个CSO模块组成。由图1和2可以看出传统二进制Turbo码和双二进制Turbo码最基本的递推结构模块无法共用。这是制约通用Turbo码译码器设计的主要因素。
发明内容
本发明的目的在于提供一种通用可配置的Turbo码译码方法,使得译码器既可以对传统二进制Turbo码进行译码,同时也可以对双二进制Turbo码进行译码,并且通用可配置Turbo码译码装置相比于专用Turbo码译码器对传统Turbo码译码时可以减少一倍时延。
本发明提出的Turbo码通用译码方法采用增强型的Max-log-MAP算法,其性能上接近于Log-MAP算法,但是在计算状态度量时省去了修正函数,简化了译码算法,降低了译码的时延。
本发明提出的Turbo码通用译码方法利用广义分配率中的Max-Sum半环性质,对传统二进制Turbo码的前向和后向状态度量计算进行合并简化,从本质上也就是对传统二进制Turbo码的网格图进行合并,使得传统二进制Turbo码的状态度量具有和双二进制Turbo码一样的计算表达式,从而通用译码方法对传统二进制Turbo码和双二进制Turbo码都可实现。
增强型Max-Log-MAP算法中前向和后向状态度量递推公式如下式(1)和式(2)所示:
定义“+”为,“max”为,那么max-sum运算是一个交换半环结构,用来表示
根据式(3)把Turbo码的前向递推转化为矩阵向量乘积形式:
其中,前向状态度量向量Ak为:
Ak=(αk(0),αk(1),…,αk(M-1))T (5)
M×M阶矩阵向量Гk包含了所有的分支度量值γk(s’,s),乘法幺元Q=0来表示分支度量为0的γk(s’,s),矩阵向量Гk的行向量对应时刻k同一状态s的分支度量,列向量对应时刻k-1同一状态s’的分支度量。一个四状态编码器的分支度量矩阵为
由于后向递推计算公式与前向递推计算公式类似,同样也用矩阵向量乘积的形式来表示:
其中,后向状态度量向量Bk为:
Bk=(βk(0),βk(1),…,βk(M-1))T (8)
矩阵向量乘积的表示方法使得我们能够将半环的所有运算用于前向递推和后向递推的推算中,最终合并网格图。
由于前向和后向递推计算都可以用递归的矩阵向量乘积的形式来表示,因此将式(9)代入到式(10)中可以得到式(11):
也就是说只需要合并分支度量矩阵,就能够将两步前向递推合并成为单步前向递推。定义
更一般地,可以将上式扩展到将L步前向递推合并为单步递推:
其中L步分支度量矩阵LГk(L≥2)定义为:
通过Max-Sum半环上的矩阵向量乘法,将L步前向递推合并为单步前向递推,可以通过求从k时刻状态s到k+L时刻状态s’网格连线上所有分支度量LГk(s’,s)与αk(s)之和的最大值,来计算αk+L(s’)。
本发明提出的通用Turbo码译码方法及装置具有以下步骤:
步骤(1)将接收到的序列顺序的存储到输入数据缓冲器,输入数据缓冲器的容量为两帧,在进行一帧译码操作的同时,接收下一帧数据;
步骤(2)控制模块控制地址发生器产生顺序地址,将输入数据缓冲区中接收到的第一个子码信息位和校验位序列按照顺序地址读出到分量译码器中,同时将外信息存储器中的外信息也按照顺序地址读出到分量译码器中,外信息存储器中的外信息初始值为0;
步骤(3-1)分量译码器通过式(1)计算第一个分量码的分支度量;
其中m=2表示信息位的数量,w=2表示校验位的数量,xkl表示信息位和校验位,取值范围为{+1,-1},La(AB)表示先验信息;双二进制Turbo码四个符号先验信息La(AB)由式(2)计算得到:
La(00)=0
La(01)=Le(01) (2)
La(10)=Le(10)
La(11)=Le(11)
而传统二进制Turbo码四个比特先验信息La(AB)由式(3)计算得到:
La(00)=0
La(01)=Le(B)=Le(10) (3)
La(10)=Le(A)=Le(01)
La(11)=Le(A)+Le(B)=Le(01)+Le(10)
其中Le(uk)是分量译码器接收到的外信息,通过控制模块实现传统二进制和双二进制Turbo码先验信息计算的切换;
步骤(3-2)分量译码器通过式(4)计算前向状态度量,并且后向状态采用模归一化处理;
步骤(3-3)分量译码器通过式(5)计算后向状态度量,并且采用模归一化处理;同时采用两个后向度量计算模块,当其中的一个输出有效数据的时候,另一个进行预热窗口的计算;
步骤(3-4)分量译码器通过式(6)、(7)计算符号外信息,通过式(6)、(8)计算比特外信息;对于双二进制Turbo码,传递的是符号外信息,而对于传统二进制Turbo码,传递的是比特外信息,每次传递的两个比特外信息或者三个符号外信息共用三根数据线通过两个数据选择器对比特外信息和符号外信息进行选择;
APPe(uk=i)表示uk=i,i∈{00,01,10,11}对应的外信息的概率似然比;
Le(uk=00)=0
Le(uk=01)=APPe(uk=01)-APPe(uk=00) (7)
Le(uk=10)=APPe(uk=10)-APPe(uk=00)
Le(uk=11)=APPe(uk=11)-APPe(uk=00)
Le(A)=max(APPe(uk=10),APPe(uk=11))
-max(APPe(uk=00),APPe(uk=01)) (8)
Le(B)=max(APPe(uk=01),APPe(uk=11))
-max(APPe(uk=00),APPe(uk=10))
步骤(4)控制模块控制地址发生器产生顺序地址,将步骤(3-4)计算出来的三个外信息值按照顺序地址存储到外信息存储器中;
步骤(5)控制模块控制地址发生器产生交织地址,将输入数据缓冲区中接收到的第二个子码信息位和校验位序列按照交织地址读出到分量译码器中,同时将外信息存储器中的外信息按照交织地址读出到分量译码器;
步骤(6)分量译码器计算第二个分量码的分支度量、前向状态度量、后向状态度量和外信息,具体方法与步骤与(3-1)~(3-4)相同;
步骤(7)控制模块控制地址发生器产生交织地址,将步骤(6)计算出来的三个外信息值按照交织地址存储到外信息存储器中,方法与步骤(5)相同,一次完整迭代译码结束;
步骤(8)分量译码器根据步骤(6)计算出来的比特外信息进行迭代译码停止判决,如果不满足迭代译码停止准则,转到步骤(9);反之,转到步骤(10);所述的迭代译码停止准则是基于比特外信息判决;
步骤(9)判断当前的迭代次数是否等于预置的最大迭代次数,如果是则转到步骤(10),反之,则转到步骤(1);
步骤(10)根据式(9)计算三个符号后验概率似然比,将{0,LLR(uk=1),LLR(uk=2),LLR(uk=3)}中最大的后验概率似然比对应的uk作为译码输出,其中0对应的是uk=0;控制模块控制地址发生器产生交织地址,将译码出来的uk序列按照交织地址写入到输出缓冲器中;
步骤(11)控制模块控制地址发生器产生顺序地址,将输出缓冲器中的信息序列按照顺序地址输出。
本发明提出了一种适用于传统二进制Turbo码和双二进制Turbo码译码的通用可配置Turbo码译码方案,很好的兼顾了通用性、译码性能、译码复杂度以及资源占用的四个指标。
附图说明
图1为传统二进制Turbo码译码器前向递推模块结构;
图2为双二进制Turbo码译码器前向递推模块结构;
图3为(13,15)分量码的网格图;
图4为(13,15)分量码两步合并后的网格图;
图5为通用Turbo码译码器总体框图;
图6为通用Turbo码译码器中的分量码译码器结构框图;
图7为通用Turbo码译码器的输入缓冲器写操作原理图;
图8为通用Turbo码译码器的输入缓冲器读操作原理图;
图9为通用Turbo码译码器中的分支度量计算模块结构框图;
图10为通用Turbo码译码器中的状态度量计算模块结构框图;
图11为通用Turbo码译码器中的外信息计算模块结构框图;
图12为通用Turbo码译码器外信息RAM读、写结构图;
图13为网格图合并前后Log-MAP和增强型MAX-Log-MAP算法的误码率(仿真环境:帧长为1504,3GPP(15,13)分量码编码器,码率1/2,AWGN信道,QPSK调制,最大迭代译码次数为8次,采用3GPP标准的交织器);
图14为通用Turbo码译码器的四路并行实时交织器结构图。
具体实施方式
本发明提出的通用Turbo码译码方法采用增强型的Max-log-MAP算法,对传统Turbo码译码采用两步前向、后向递推计算合并为单步前向、后向递推计算,即将传统Turbo码网格图中的两步状态转移合并成为一步状态转移,使得传统Turbo码与双二进制Turbo码具有相同的网格图结构,从而可以同时对双二进制和传统二进制Turbo码译码。一个8状态的传统Turbo码编码器网格图如图3所示,经过网格图合并后的传统Turbo码编码器网格图如图4所示。
本发明中通用可配置Turbo码译码装置结构如图5所示,它由输入数据缓冲器,分量码译码器,外信息存储器RAM,输出数据缓冲器,地址发生器,控制器组成。为了减少资源占用,降低能量损耗,仅仅使用一个分量码译码器模块。图5中虚线表示的是地址。通用Turbo码译码装置根据不同Turbo码采用相应的配置,因此在双二进制Turbo码译码装置上增加一些选通模块进行模块间的调配。对于双二进制Turbo码来说,资源上不会有太大的增加。相对于传统二进制Turbo码来说,资源上会有一定量的增加,但是由于采用同样的滑动窗算法,因此在占用Turbo码译码器主要资源的存储空间上并没有多大的增加。SISO运算量上的微量增加以及控制模块上的增加与Turbo码的大存储空间相比,几乎可以忽略。另外网格图合并技术增加的资源代价对传统二进制Turbo码来说,也带来了很大的好处。通过网格图合并,使得两个比特同时进行译码,大大降低了译码延时。增加一定的资源,获得译码延时的降低。
通用Turbo码译码装置中的分量译码器是最复杂、核心的部分,它采用的是滑动窗方式,基于符号的增强型Max-Log-MAP译码算法,基于比特的停止迭代判决准则。译码装置结构如图6所示,分量码译码器是由分支度量计算模块,状态度量计算模块,外信息计算模块,判决输出判决模块,RAM及选择器组成。
本发明提出的通用Turbo码译码方法及装置具有以下步骤:
步骤(1):将接收到的序列顺序的存储到数据缓冲器。
为了能够减小时延,输入数据缓冲器的容量应该设计成两帧的大小,在进行一帧译码操作的同时,接收下一帧数据。
步骤(2):控制模块控制地址发生器产生顺序地址,将输入数据缓冲区中接收到的第一个子码信息位和校验位序列按照顺序地址读出到分量译码器中,同时将外信息存储器中的外信息也按照顺序地址读出到分量译码器中(外信息存储器中的外信息初始值为0)。
对于传统二进制Turbo码译码,输入缓冲器的读和写操作是针对每个比特的,而对于双二进制Turbo码译码,输入和输出缓冲器的读和写操作是针对每个符号的。输入缓冲器的写操作存储原理如图7所示,读操作原理如图8所示。
步骤(3-1):分量译码器计算第一个分量码的分支度量。
由于译码器采用的增强型Max-Log-MAP译码算法,分支度量γk(s’,s)表示为:
其中m=2表示信息位的数量,w=2表示校验位的数量,xkl对应于信息位和校验位,取值范围为{+1,-1},La(AB)代表的是符号先验信息。
双二进制Turbo码四个符号先验信息La(AB)由下式计算得到:
La(00)=0
La(01)=Le(01)
La(10)=Le(10)
La(11)=Le(11)
而对传统二进制Turbo码,外信息传递的是两个比特外信息Le(A)和Le(B),因此传统二进制Turbo码四个符号先验信息La(AB)由下式计算:
La(00)=0
La(01)=Le(B)=Le(10)
La(10)=Le(A)=Le(01)
La(11)=Le(A)+Le(B)=Le(01)+Le(10)
其中Le(uk)是分量译码器接收到的外信息,通过控制模块实现传统二进制和双二进制Turbo码先验信息计算的切换;
对于每一个时刻k分支度量γk(s’,s)有32个,两个寄存器总共需要64个存储空间存储分支度量。仔细观察可以发现,γks(s’,s)对于两个分量码译码器只有4种可能的取值,同信息符号有关。而γke(s’,s)对于每个分量码译码器也只有4种可能的取值,同校验位有关,两个分量码译码器就只有8种可能的取值。因此如果在每个时刻k只存储γks(s’,s)和γke(s’,s)就仅仅需要12个存储空间即可,这比直接存储分支度量要节省更多的空间。
对γks(s’,s)和γke(s’,s)进行选择的时候需要根据网格图实时计算。实际上,我们只需要计算一个相对γks(s’,s)和γke(s’,s):
因此对于两个分量码译码器γks(s’,s)只需要存储3个数值,γke(s’,s)只需要存储6个数值即可。计算模块结构如图9所示。虚线框内代表了传统二进制Turbo码的合并计算。通过控制模块改变选择器的选择项即可实现传统二进制和双二进制Turbo码的切换。
步骤(3-2):分量译码器计算第一个分量码的前向状态度量。
根据前向状态度量计算公式,可以推出:
前向状态度量计算模块也就是递推结构,前向状态度量结构如图10所示。由于通用译码器都采用的是8状态的网格图,因此输出状态度量总线上是一个8选1的选择器。图中的粗线表示是一组数据,根据选择器选择相应地数据输入到ACS中去。图10中每一基本模块可以在一个时钟周期内即可完成,大大降低译码时延。图中每个ACS的输入都是三输入,相应的加法就是三输入加法器。前向状态度量计算采用模归一化处理。
步骤(3-3):分量译码器计算第一个分量码的后向状态度量。
βk(s)的结构与αk(s)基本类似,不过由于采用的是滑动窗算法,如图6所示,有两个βk(s)计算模块,其中一个βk(s)输出有效数据的时候,另一个βk(s)计算模块进行预热窗口的计算,这样通过增加模块的方式减少预热窗口的等待,降低延时。通过模归一化处理,可以省略归一化模块,简化状态度量的计算,加速状态度量的计算。
步骤(3-4):分量译码器通过下面三个式子分别计算第一个分量码的符号外信息和比特外信息:
APPe(uk=i)表示uki,i∈{00,01,10,11}对应的外信息的概率似然比;
Le(uk=00)=0
Le(uk=01)=APPe(uk=01)-APPe(uk=00)
Le(uk=10)=APPe(uk=10)-APPe(uk=00)
Le(uk=11)=APPe(uk=11)-APPe(uk=00)
Le(A)=max(APPe(uk=10),APPe(uk=11))
-max(APPe(uk=00),APPe(uk=01))
Le(B)=max(APPe(uk=01),APPe(uk=11))
-max(APPe(uk=00),APPe(uk=10))
对于双二进制Turbo码,传递的是符号外信息,而对于传统二进制Turbo码,传递的是比特外信息,每次传递的两个比特外信息或者三个符号外信息共用三根数据线通过两个数据选择器对比特外信息和符号外信息进行选择。
外信息Le(uk=i)计算模块的结构如图11所示。其中右边虚框代表了传统二进制Turbo码额外的比特外信息计算。而对于双二进制Turbo码我们只需要通过简单的减法之后传递三个外信息即可。左边的虚框表示外信息概率的计算模块,输入方式与状态度量中类似,采用选择器进行选择输入。由于采用增强型Max-Log-MAP算法,因此在图6可以看到外信息的输出端接了个乘以校验因子sf的过程。实际中sf取0.75,只需要通过移位自加再移位即可实现。最后一点是由于不论是对传统二进制Turbo码还是对双二进制Turbo码进行译码,外信息传递都是公用三条数据线的,因此还需要两个数据选择器对比特外信息和符号外信息进行选择。
步骤(4):控制模块控制地址发生器产生顺序地址,将步骤(3-4)计算出来的三个外信息值按照顺序地址存储到外信息存储器中。
外信息存储器存储结构如图12所示。对于传统Turbo码译码来说,由于交织和解交织不是针对网格合并后的每个符号进行,而是针对每个比特进行的,因此外信息RAM存储的是比特的外信息。外信息RAM中不再区分是A比特还是B比特,即在外信息RAM中同时译码出的两个比特外信息不进行捆绑式存储。下标表示的是比特外信息存储在外信息RAM中的位置。同样的当从外信息RAM中读比特外信息的时候,按照交织器产生的两个比特地址一次从RAM中读取两个比特外信息;对于双二进制Turbo码译码来说,由于交织和解交织是针对每个符号而言的,因此外信息RAM存储的是符号外信息。每个符号的三个符号外信息是捆绑式存储的。下标表示的是该符号在外信息RAM中的相对位置。同样的当从外信息RAM中读取符号外信息的时候,按照交织器产生的一个符号地址一次从RAM中连续的读取三个符号外信息。最后要说明的是,每次传递的两个比特外信息或者三个符号外信息是共用三根数据线的,存储前需要控制器对写入或者读出的数据进行选择。
步骤(5):控制模块控制地址发生器产生交织地址,将输入数据缓冲区中接收到的第二个子码信息位和校验位序列按照交织地址读出到分量译码器中,同时将外信息存储器中的外信息也按照交织地址读出到分量译码器中。
步骤(6-1):分量译码器计算第二个分量码的分支度量。
步骤(6-2):分量译码器计算第二个分量码的前向状态度量。
步骤(6.3):分量译码器计算第二个分量码的后向状态度量。
步骤(6-4):分量译码器计算第二个分量码的符号和比特外信息。
步骤(6-1)~(6-4)的方法同步骤同(3-1)~(3-4)是一样的。
步骤(7):控制模块控制地址发生器产生交织地址,将步骤(6-4)经过选择后的三个外信息值按照交织地址存储到外信息存储器中。其方法同步骤(5)中的是一样的。此时一次完整迭代译码结束。
步骤(8):分量译码器根据步骤(6-4)计算出来的比特外信息进行迭代停止判决。由于在步骤(6-4)中,不论是双二进制还是传统二进制Turbo码,都计算出了它们的比特外信息,因此迭代停止准则采用基于比特的的停止判决方法。如果停止准则不满足,转到步骤(9);否则停止迭代,转到步骤(10)。
步骤(9):判断当前的迭代次数是否等于预置的最大迭代次数,如果是则转到步骤(10);反之,则转到步骤(1)。
步骤(10)根据下式计算三个符号后验概率似然比,将{0,LLR(uk=1),LLR(uk=2),LLR(uk=3)}中最大的后验概率似然比对应的uk作为译码输出,其中0对应的是uk=0;控制模块控制地址发生器产生交织地址,将译码出来的uk序列按照交织地址写入到输出缓冲器中;
步骤(11):控制模块控制地址发生器产生顺序地址,将输出缓冲器中的信息序列按照顺序地址输出。
以现有的硬件技术,Turbo码译码的浮点实现是几乎不可能的,因此这里采用定点运算。通过仿真发现,采用双二进制Turbo码的译码结构,输入数据采用5bit量化,分支度量采用8bit,状态度量采用9bit,而外信息采用8bit量化下的定点量化已经能取得接近与浮点仿真的性能。
这里给出一个适合于本发明提出的通用译码方法的传统二进制Turbo码仿真图和实验结果比较。图13为帧长1504,3GPP(15,13)分量码编码器,码率1/2的传统Turbo码网格图合并前后Log-MAP和增强型MAX-Log-MAP算法的误码率,仿真环境采用AWGN信道,QPSK调制,最大迭代译码次数为8次,3GPP标准的交织器,交织器的结构图如图14所示。
如图13所示在低信噪比时,Log-MAP算法下,两步合并的性能比不合并的性能下降仅仅0.04dB,而增强型MAX-Log-MAP算法,性能下降更少。而在高信噪比区域,四种条件下的性能几乎没有差别。性能下降的原因是上述推导使用的是max-sum半环,并没有添加修正项。传统Turbo码复杂度比较如表1所示。
综上所述,基于符号和基于比特停止准则在增加资源不多的情况下,都能获得很好的停止效果。
实现结果比较
表1网格图合并前后运算量比较
传统二进制Turbo码 网格图合并后的Turbo码
加法运算 比较运算 加法运算 比较运算
γk(s’,s) 10 0 26 0
αk(s) 32 16 32 24
βk(s) 32 16 32 24
L(uk) 66 28 66 32
由于网格图合并一次译码两个比特,因此合理的比较方式是对传统二进制Turbo码两个比特的运算量进行统计,再与网格图合并后的运算量比较。表1是8状态下两种方法每个分量译码器每两个比特运算量统计。
传统二进制Turbo码状态度量的基本模块只需要一个ACSO模块,而网格图合并后的传统二进制Turbo码状态度量的基本模块同双二进制Turbo一样需要两个ACSO模块再加上一个CSO模块,所以SISO计算模块的资源增加了一倍。而由表1可以看出,事实上,从运算量角度来说,网格图合并前后运算量增加很少。
机译: 双二进制TURBO编码器,双二进制TURBO解码器和可见光通信系统,包括相同的能力,可提高BER性能
机译: 用非二进制LDPC码对编码块进行译码的基础上更新控制节点的方法及相应的译码器
机译: 软件定义的无线电系统中二进制和双二进制turbo解码的统一停止标准