第六讲――循环码的译码

第六讲循环码的译码译码的基本准则•最小错误概率–minPE=minP(C’C|R)•最大后验概率：maxP(C’=C|R)–C’取maxiP(Ci|R)的最大值时的Ci•最大似然：maxP(R|C’=C)–C’取maxiP(R|Ci)的最大值时的Ci，•当发送码字等概时，最大后验概率准则与最大似然准则等价–P(Ci|R)=P(Ci)P(R|Ci)/P(R)。其中的P(Ci)为发送码字Ci的先验概率。译码方法分类•按处理方法分类–时域译码，直接根据序列的前后关系进行译码–变换域译码，将序列进行某些变换如FFT等再行译码•时域处理中，又可分为–代数译码：利用码的代数结构的译码–概率译码：不仅利用码的代数结构，还利用信道统计特性的译码循环码的代数译码•适用情况：非时变对称DMC，接收符号集与发送符号集相同，且各发送符号在接收符号集中有一个最大似然的对应符号，不妨令此符号即为发送符号。•依据：最大似然译码准则时非变对称DMC中的最大似然准则•对接收矢量R，和一个可能的许用码矢量C，它们的相应的似然值为iP(ri|ci)，这里用到了信道的无记性，再利用非时变性和对称性得Pcm[(1-Pc)/(M-1)]n，其中m为序列中ri=ci的符号个数，n为序列中rici的符号个数，M为符号集大小；此外根据最大似然准则且在信道容量不为0的情况下，有Pc(1-Pc)/(M-1)。因此有最小差错概率的序列与R的汉明距离最小。最小汉明距离准则•在非时变对称DMC信道中，最小汉明距离准则与最大似然准则等价，此时如果再有发送码字等概的假设，则最小汉明距离就是最小序列（或码字）差错概率译码准则•注意：最小汉明距离准则的适用条件，信道特性中的离散、无记忆、非时变和对称，发送码字等概这几个条件缺一不可。循环码的一般译码方法•对收到的R(x)=C(x)+E(x)，找到最可能发生的错误图案E(x)–根据接收多项式R(x)计算伴随式S(x)–计算错误图案，即形成伴随式S(x)的最轻图案–)(xE)()()(xExRxC伴随式的循环移位•令S(x)为R(x)的伴随式，则R(x)的循环移位xR(x)modxn-1的伴随式S1(x)是S(x)的模g(x)移位运算的结果：S1(x)=xS(x)modg(x)•因此有：xjR(x)modxn-1=Sj(x)=xjS(x)modg(x)；•a(x)R(x)modxn-1=Sa(x)=a(x)S(x)modg(x)循环码的伴随式译码•将常数项（或最高项）非零的可纠错误图案E(x)组成一个集合，计算它们的伴随式，构成一张表。译码时，先计算出S(x)，然后对其做0,1,…,n-1次模g(x)移位，得到Sj(x)。比较Sj(x)是否在可译表中，若在，则得到循环移位j次后的错误图案。运算量分析•纠t个错的(n,k)线性分组码译码所需错误图案表大小为，而纠t个错的(n,k)循环码译码所需错误图案表大小为，tn11tn循环码伴随式译码举例•纠一个错的循环码：汉明码–共有n种可纠的错误图案，而它们都是000…001（伴随式为S0(x)）的循环移位。因此它们可以归为一类，即对计算出的S(x)做0~n-1次模g(x)移位，直到出现S0(x)为止，将R(x)做相应次移位后最后一位反转，再做剩余的移位，即得到正确的译码结果。可见伴随式表可以大大缩小。循环码的捕错译码•依据：能纠t个错的GF(q)上的(n,k)循环码，不多于t个错误全在最低的n-k位中的充要条件是w(S(x))t。•证明：若这些错不全落在低n-k位中，则E(x)-S(x)0，其重量d=2t+1，则w(E(x))+w(-S(x))d，而w(E(x))t，=w(S(x))t+1。捕错译码算法与条件•算法：根据上面的分析，可实现捕错译码。即S(x)做j次模g(x)移位后，如果重量不大于t则此时的Sj(x)就是R(x)循环移位j次的错误图案。•条件：t个错误均匀分布时仍要保证其空隙长度不小于k。因此有kn/t，即编码效率R=k/n1/t。•捕错译码的修正：略，见参考书。大数逻辑译码•正交一致校验矩阵：若某一特定码元位（如xn-1）出现在H0矩阵中J行的每一行中，而其它码元位至多在其中一行出现，则称H0为正交于该码元位(xn-1)的正交一致校验矩阵。•正交一致校验和式：正交一臻校验矩阵中的各校验方程。纠错能力与正交一致校验矩阵的关系•一个线性分组码若在任一位上都能建立J个正交一致校验和式，则该码能纠正tJ/2个错误。•大数逻辑译码：当要判断第I位码元处是否发生错误时，可以根据J个该位的正交一致校验和式为0的个数来判断，如果为不为0的个数大于J/2时则该位有错，否则该位正确。大数逻辑译码•对循环码而言，只需要对任一特定位建立正交一致校验和式即可，在判断其它位是否正确时，可以通过移位的方式来实现。•大数逻辑可译码：可以采用大数逻辑译码的码。显然，是否能构成J个一致校验和式是关键。•一步大数逻辑可译码和L步大数逻辑可译码。BCH码的译码•出发点：BCH码是一种构造性较好的码，可以较容易地得到较大的n,k,和t。•在伴随式译码的三步曲中，最关键的是第二步：即根据S(x)找错误图案E(x)。当k和n-k都很大时，以上算法复杂度都很高，需要找到更有效的方法。伴随式译码的进一步分解•将第二步“计算错误图案”分成两步：–确定错误位置–确定在各错误位置上的错误值•对于二进制码而言，第2步可以省略。错误位置多项式•在找错误位置时，位置可由该BCH码的本原元（或生成元）的幂次表示，即，li是第i个错误的位置。则找到各xi即可。而各xi为方程的根的倒数。•称为错误位置多项式。ilixtiixx1)1(tiixxx1)1()(BCH译码的运算量•因此找错误位置就又可分为两步–根据S(x)确定(x)的各项系数，运算量正比于t3。–求解(x)。可用Chien搜索算法，运算量正比于t。•其中求(x)还可用迭代算法，其运算量正比于t2。线性分组码小结•为了分析和译码的方便而引入线性分组•为了同样的原因引入循环码•为了分析循环码而引入近世代数•循环码是模xn-1剩余类结合代数是的理想•用根定义的循环码•循环码的译码