第六讲——循环码的译码.ppt

第六讲,循环码的译码,译码的基本准则,最小错误概率minPE=minP(CC|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为序列中rici的符号个数，M为符号集大小；此外根据最大似然准则且在信道容量不为0的情况下，有Pc(1-Pc)/(M-1)。因此有最小差错概率的序列与R的汉明距离最小。,最小汉明距离准则,在非时变对称DMC信道中，最小汉明距离准则与最大似然准则等价，此时如果再有发送码字等概的假设，则最小汉明距离就是最小序列（或码字）差错概率译码准则注意：最小汉明距离准则的适用条件，信道特性中的离散、无记忆、非时变和对称，发送码字等概这几个条件缺一不可。,循环码的一般译码方法,对收到的R(x)=C(x)+E(x)，找到最可能发生的错误图案E(x)根据接收多项式R(x)计算伴随式S(x)计算错误图案，即形成伴随式S(x)的最轻图案,伴随式的循环移位,令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)循环码译码所需错误图案表大小为，,循环码伴随式译码举例,纠一个错的循环码：汉明码共有n种可纠的错误图案，而它们都是000001（伴随式为S0(x)）的循环移位。因此它们可以归为一类，即对计算出的S(x)做0n-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个正交一致校验和式，则该码能纠正tJ/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为方