【教学课件】第六章循环码的译码.ppt
第六章 循环码的译码,循环码的译码,一般译码原理捕错译码大数逻辑译码,一、一般译码原理,基本思想与线性分组码类似,1、根据接收序列R计算伴随式S=RHT(n-k维向量),2、根据伴随式S寻找错误图样E,3、根据错误图样E估计码向量C，进而计算信息序列,伴随式计算的多项式表示,系统循环码的一致校验矩阵H,循环码伴随式 可用除法电路实现,由此可知：循环码的检错电路易于实现。,循环码计算伴随式电路的特点,定理：若S(x)是R(x)的伴随式，R(x)的循环移位xR(x)的伴随式为S1(x)，则S1(x)是伴随式计算电路中无输入时右移一位的结果。,循环码计算伴随式电路的特点,推论：xjR(x)的伴随式Sj(x)xjS(x)(mod g(x)，j=0，1，n-1。而任意多项式a(x)乘R(x)所对应的伴随式 Sa(x)a(x)S(x)(mod g(x),在q进制时，若码要纠正t个错误，则错误图样代表共有使得循环码译码器的错误图样识别电路大为简化，由原来识别N2个图样减少到N1个,Example:循环码生成多项式g(x)=x3+x+1，计算E(x)=x6和E(x)=x5的伴随式,循环汉明码译码电路,7,4,3循环汉明码的生成多项式为x3+x+1,输入R(x),循环汉明码译码电路(需要14移位),Example：设计一个由g(x)=x4+x3+1生成的15,11循环汉明码译码电路。,基本要求：需要一个除法电路和一个逻辑电路,要设计逻辑电路，须知道该码可纠正的错误图样及伴随式,汉明码可纠一个错误，只需知道一个错误图样的伴随式,伴随式又可由校验矩阵H得到,扩展汉明码的译码,缩短循环码的译码,扩展汉明码的译码,扩展汉明码的码长是8的整数倍。扩展汉明码d=4，能纠正一个错误同时发现两个错误。译码电路主要部分与循环汉明码译码器相同，需要加上检错电路。,二、捕错译码,基本原理,基本原理,若错误集中在校验元的n-k位上，即EI(x)=0,E(x)=EP(x),此时，伴随式就是错误图样，C(x)=R(x)-S(x),可用捕错译码循环码必须满足,1、错误必须集中在任意连续的n-k位上可利用循环码的特点将错误移到后n-k位上,2、k n/t 或 t n/k 或 R 1/t,错误集中在n-k个校验元上的条件,纠正t个错误的GF(q)上的n,k循环码，捕错译码过程中，已把t个错误集中在Ri(x)的最低次n-k 位以内的充要条件是：,其中w(Si(x)是伴随式Si(x)的重量,若前面k位没有错误，则可用捕错译码实现,若前面k位也有错误，此时伴随式S(x)为：,若EI(x)和SI(x)已知，可由此得到EP(x)，进而确定E(x)=EI(x)+EP(x)，即是修正捕错译码,修正的捕错译码,当循环码的信息比特数k等于n/t或比n/t稍大时，可采用某种方法，将大部分错误集中在n-k位上，而把个别错误集中在固定的某几位上，即可实现修正的捕错译码,修正捕错译码原理,修正捕错译码原理,因此，如果能找到一个k-1次多项式Q(x)，使错误图样E(x)或E(x)的循环移位在前k位码段内与Q(x)一致，即可找到最终的错误图样,覆盖多项式的数目,对于纠正t个错误的GF(q)上的n,k循环码，当且仅当R2/t时，覆盖多项式集合必存在。对于t=2，覆盖多项式Qj(x)中，最少的多项式数目为,三、大数逻辑译码原理,大数逻辑译码,大数逻辑译码,A1=c6+c4+c3=0A2=c6+c5+c1=0A3=c6+c2+c0=0该校验方程的特点：c6含在每一方程中，c5,c4,c3,c2,c1,c0只含在某一方程中。称为正交于c6码元位的正交校验方程。H0称为正交一致校验矩阵。定义：若某一特定码元位出现在H0矩阵中J行的每一行中，其他码元位至多在其中一行出现，则称H0为正交于该码元位的正交一致校验矩阵。,大数逻辑译码,假设正交位为en-1,若奇偶校验和的绝对多数为1，则差错位en-1被译码为1；否则被译码为0。一个循环码若在任一位上能建立J个正交一致校验和式，则该码能纠正tJ/2个错误。最小距离d=J+1的码为一步完备可正交码一步大数逻辑可译码的纠错个数，与码参数之间的关系:汉明码的对偶码，极长码,大数逻辑译码,如果某一码元位置集合ci1,ci2,cil的线性组合 ai1ci1+ai2ci2+ailcil 在A1，A2,AJ的一致校验和式中均出现，而其余码元位置集合至多在其中一个校验和式中出现，则说A1，A2,AJ在集合ci1,ci2,cil上正交，称A1，A2,AJ是正交于该码元位置集合的正交一致校验和式。例：7,4,3循环汉明码，两步大数逻辑可译码,大数逻辑可译码,RM码极长码（汉明码的对偶码）差集循环码复数旋转码,RM码,G0是长为N的全1矢量，G1是m2m阶矩阵，其各列由2m个m重矢量组成；Gi是从G1中选取i行进行矢量与运算所得到的矢量构造的。r阶RM码r阶RM码是r+1步大数逻辑可译码,极长码,对任何整数m=2，均存在有如下参数的极长码：n=2m-1，k=m,d=2m-1。码的生成多项式g(x)=(xn-1)/p(x)。p(x)是一个m次本原多项式。极长码是汉明码的对偶码。一步大数逻辑译码,四 软判决译码,软判决译码,能够充分利用接收信号波形信息比硬判决译码能得到额外的23dB的增益适合中等码长和中等纠错能力的码信噪比可以在很宽的范围内变化硬判决译码软判决译码最大后验概率译码,软判决译码准则,码字错误概率最低：广义最小距离译码、Chase译码码元错误概率最低：APP译码、逐位译码、重量删除译码,几类最佳译码,最小欧几里德距离译码最大内积译码（最大相关译码）,软判决译码,软判决译码是最佳译码的折衷,软判决译码,软判决距离：二进制输入Q元输出的DMC中，最大似然译码近似等价于最小软判决距离译码软判决重量wls软重量和汉明重量关系：wls=(Q-1)wlh一个最小距离为dh的二进制n,k线性分组码，有最小软距离ds=(Q-1)dh,它一定能纠正软重量为ts(Q-1)dh/2的任何错误图样有最小距离为dh的二进制线性分组码，在Q进制输出的DMC中，当信噪比很高时，应用最小软判决距离译码，能纠正dh-1个硬判决错误,编码增益和软判决增益,在某一误码率下，应用一定的纠错码系统后，相对于没有应用时所获得的信噪比减少的分贝数称为此纠错码的编码增益高信噪比时所获得的编码增益称为渐进编码增益码率R,纠t个错误，AWGN信道，硬判决译码未应用纠错码，AWGN信道硬判决渐进编码增益：未量化信道的渐进编码增益：,码字错误概率最小的软判决译码,GMD译码算法：逐字判决的软判决译码算法设由解调器输出的实数序列，送入一个似然比估值器，计算码元的对数似然函数比对Li量化，ai=q(Li)令a=(a1,a2,an)是输入至译码器的实数序列，其中|ai|=1,则至多只有一个码字Cl(n,k,dh)满足,GMD译码过程,Step1：从量化器输出的a序列删去i个最不可信的码元，并按ai的正负号，把a序列变成由-1、1、0元素组成的试探序列aStep2：通过纠错纠删译码器得到已译码字C1Step3：检测GMD条件是否满足，满足，输出C1，不满足，在a序列删除i+1个最不可信码元，重新回到step1.试探次数,Chase译码算法,用硬判决纠错译码器代替GMD中的纠删或纠错纠删译码器，且试探序列的选择稍有不同基本原理：利用硬判决译码器，根据不同的试探序列产生几个候选码字，把它们与接受序列比较，挑选一个与接收序列有最近软距离的候选码字作为译码器的输出,
