第六讲——循环码译码 (2)

1、第六讲循环码的译码1译码的基本准则最小错误概率min PE = min P(CC|R)最大后验概率：max P(C=C|R)C 取maxi P(Ci|R) 的最大值时的Ci最大似然：max P(R| C=C)C 取maxi P(R|Ci) 的最大值时的Ci，当发送码字等概时，最大后验概率准则与最大似然准则等价P(Ci|R)=P(Ci) P(R|Ci)/P(R)。其中的P(Ci)为发送码字Ci的先验概率。2译码方法分类按处理方法分类时域译码，直接根据序列的前后关系进行译码变换域译码，将序列进行某些变换如FFT等再行译码时域处理中，又可分为代数译码：利用码的代数结构的译码概率译码：不仅利用码的代数

2、结构，还利用信道统计特性的译码3循环码的代数译码适用情况：非时变对称DMC，接收符号集与发送符号集相同，且各发送符号在接收符号集中有一个最大似然的对应符号，不妨令此符号即为发送符号。依据：最大似然译码准则4时非变对称DMC中的最大似然准则对接收矢量R，和一个可能的许用码矢量C，它们的相应的似然值为iP(ri|ci)，这里用到了信道的无记性，再利用非时变性和对称性得Pcm(1-Pc)/(M-1)n，其中m为序列中ri=ci的符号个数，n为序列中rici的符号个数，M为符号集大小；此外根据最大似然准则且在信道容量不为0的情况下，有Pc (1-Pc)/(M-1)。因此有最小差错概率的序列与R的汉明距

3、离最小。5最小汉明距离准则在非时变对称DMC信道中，最小汉明距离准则与最大似然准则等价，此时如果再有发送码字等概的假设，则最小汉明距离就是最小序列（或码字）差错概率译码准则注意：最小汉明距离准则的适用条件，信道特性中的离散、无记忆、非时变和对称，发送码字等概这几个条件缺一不可。6循环码的一般译码方法对收到的R(x)=C(x)+E(x)，找到最可能发生的错误图案E(x)根据接收多项式R(x)计算伴随式S(x)计算错误图案 ，即形成伴随式S(x)的最轻图案 7伴随式的循环移位令S(x)为R(x)的伴随式，则R(x)的循环移位xR(x) mod xn-1的伴随式S1(x)是S(x)的模g(x)移位运

4、算的结果：S1(x)=xS(x) mod g(x)因此有：xjR(x) mod xn-1 = Sj(x)=xjS(x) mod g(x)；a(x)R(x) mod xn-1 = Sa(x)=a(x)S(x) mod g(x)8循环码的伴随式译码将常数项（或最高项）非零的可纠错误图案E(x)组成一个集合，计算它们的伴随式，构成一张表。译码时，先计算出S(x)，然后对其做0, 1, , n-1次模g(x)移位，得到Sj(x)。比较Sj(x)是否在可译表中，若在，则得到循环移位j次后的错误图案。9运算量分析纠t个错的(n,k)线性分组码译码所需错误图案表大小为 ，而纠t个错的(n,k)循环码译码所需

5、错误图案表大小为 ，10循环码伴随式译码举例纠一个错的循环码：汉明码共有n种可纠的错误图案，而它们都是000001（伴随式为S0(x)）的循环移位。因此它们可以归为一类，即对计算出的S(x)做0n-1次模g(x)移位，直到出现S0(x)为止，将R(x)做相应次移位后最后一位反转，再做剩余的移位，即得到正确的译码结果。可见伴随式表可以大大缩小。11循环码的捕错译码依据：能纠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，而

6、w(E(x) t，= w(S(x) t + 1。12捕错译码算法与条件算法：根据上面的分析，可实现捕错译码。即S(x)做j次模g(x)移位后，如果重量不大于t则此时的Sj(x)就是R(x)循环移位j次的错误图案。条件：t个错误均匀分布时仍要保证其空隙长度不小于k。因此有kn/t，即编码效率R=k/n1/t。捕错译码的修正：略，见参考书。13大数逻辑译码正交一致校验矩阵：若某一特定码元位（如xn-1）出现在H0矩阵中J行的每一行中，而其它码元位至多在其中一行出现，则称H0为正交于该码元位(xn-1)的正交一致校验矩阵。正交一致校验和式：正交一臻校验矩阵中的各校验方程。14纠错能力与正交一致校验矩

7、阵的关系一个线性分组码若在任一位上都能建立J个正交一致校验和式，则该码能纠正tJ/2个错误。大数逻辑译码：当要判断第I位码元处是否发生错误时，可以根据J个该位的正交一致校验和式为0的个数来判断，如果为不为0的个数大于J/2时则该位有错，否则该位正确。15大数逻辑译码对循环码而言，只需要对任一特定位建立正交一致校验和式即可，在判断其它位是否正确时，可以通过移位的方式来实现。大数逻辑可译码：可以采用大数逻辑译码的码。显然，是否能构成J个一致校验和式是关键。一步大数逻辑可译码和L步大数逻辑可译码。16BCH码的译码出发点：BCH码是一种构造性较好的码，可以较容易地得到较大的n, k, 和t。在伴随式译码的三步曲中，最关键的是第二步：即根据S(x)找错误图案E(x)。当k和n-k都很大时，以上算法复杂度都很高，需要找到更有效的方法。17伴随式译码的进一步分解将第二步“计算错误图案”分成两步：确定错误位置确定在各错误位置上的错误值对于二进