循 环 码 （IV）

内容 一般译码原理 捕错译码 大数逻辑译码 仿真流程及Gaussian噪声的产生

一般译码原理 基本思想与线性分组码类似 1、根据接收序列R计算伴随式S=RHT (n-k维向量) 2、根据伴随式S寻找错误图样E 3、根据错误图样E估计码向量C’=R-E，进而估计信息序列（系统码、非系统码）

伴随式计算的多项式表示 系统码

伴随式计算的多项式表示 S 如何用多项式表示？

循环码伴随式的除法电路实现 由此可知：循环码的检错电路易于实现。 就是一个g(x)除法电路 若deg(E(x)) < deg(g(x))，则S(x) = E(x) != 0 (mod g(x))  能检测长度小于等于n-k的突发错误

发送端实现电路：在数据序列后端添加CRC校验 循环码的检错功能在ARQ中的应用 发送端实现电路：在数据序列后端添加CRC校验 门1 -g1 -g2 gn-k-1 -g0 -gn-k-2 -gn-k-1 门2 C(x) 输入m(x) m0,m1,…mk-1 乘xn-k除g(x)运算电路

接收端实现电路：将接收序列通过一除法电路，判断是否有错。 循环码的检错功能在ARQ中的应用 接收端实现电路：将接收序列通过一除法电路，判断是否有错。 -g1 -g2 gn-k-1 -g0 -gn-k-2 -gn-k-1 r0,r1,…rn-1 输入R(x) 若移位寄存器的存储值全部为零，则表示收到的码字为合法 码字，否则，有错，将向发送端反馈一个信号，用于重传。

计算伴随式电路的特点 定理：若S(x)是R(x)的伴随式，R(x)的循环移位xR(x)的伴随式为S1(x)，则S1(x)是伴随式计算电路中无输入时右移一位的结果。 推论：xiR(x)的伴随式为Si(x) = xiS(x) mod(g(x))，a(x)R(x)的伴随式为Sa(x) = a(x)S(x) mod(g(x))。 译码时，可将错误图样进行归类，即任一错误图样及其循环移位作为一类

Example 循环码生成多项式g(x)=x3+x+1，计算E(x)=x6，E(x)=x5和E(x)=x4的伴随式

Example (Continued) 非门 与门 输入R(x) 七级缓存 门 循环汉明码译码电路 (需要14次移位)

Example (Continued) R(x)=x6+x+1, E(x) = x4

捕错译码 基本工作原理 伴随式 式中 分别是码字信息组(或前k位)和校验位(或后n-k位）上的错误图样

基本原理 若错误集中在校验元的n-k位上，即EI(x)=0, E(x)=EP(x) 此时，伴随式就是错误图样，C’(x)=R(x)-S(x) 可用捕错译码循环码必须满足 1、错误必须集中在任意连续的n-k位上，可利用循环码的特点将错误移到后n-k位上 2、要求有连续k维码元无错，即 k < n/t 或 t < n/k 或 R < 1/t

捕错译码 纠正t个错误的GF(q)上的[n,k]循环码，捕错译码过程中，已把t个错误集中在Ri(x)的最低次n-k 位以内的充要条件是： 其中w(Si (x))是伴随式Si (x)的重量 (R(x), S0(x), R(x)’)  (Ri(x)=xiR(x), Si(x)=xiS0(x)) 满足w(Si (x)) ≤t  Ri (x)’= Ri(x)- Si(x)=xi R(x)’  xn-i Ri (x)’= xn R(x)’= R(x)’(mod xn-1)

捕错译码 错误多项式 若前面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)一致，即可找到最终的错误图样

大数逻辑译码 [7, 3, 4]增余删信Hamming码的校验矩阵 设接收R=C+E，相应的伴随式 对伴随式分量s0、s1、s2和s3进行线性组合，得到以下一组校验方程

大数逻辑译码 显然，上述方程的系数所组成的3个七重数组: (1011000), (1100010), (1000101)是H行的线性组合，在H的行空间中，则码字C满足

大数逻辑译码 可知 得到一组新的校验方程。它有以下特点:c6含在每一方程中，而其他所有码元只含在某一方程中。有这种特点的校验方程称为正交于c6码元位的正交校验方程。系数组成的矩阵为正交一致校验矩阵

大数逻辑译码 译c6时，计算A1, A2, A3中取1数目的多少进行纠错。 其他位置码元通过循环移位后按相同方法译码 若发生一个错误在该正交位上时，Ai中1的数目为3；否则为1 其他位置码元通过循环移位后按相同方法译码 这种按照正交方程中取1数目的多少，进行译码的方法称为大数逻辑译码。 一个循环码若在任一上能建立J个正交已知校验和式，则该码能纠正 个错误 若码的最小距离d=J+1的码称为一步完备可正交码

产生信息序列 仿真流程 编码 通过信道 实际系统中， 采用检错码判断 译码 与信息序列比较，判断是否有错 中止 Yes 计算误比特率

Gaussian Noise Program long Seed = 17; double UniformRand() { double uRand; // generate a uniformly distributed random number Seed = (Seed * 1029 + 221591L) % 1048576L; // make 0.0 <= uRand <= 1.0 uRand = (double)Seed / 1048576.0; return uRand; }

Gaussian Noise Program double GaussNoise(double sigma) // sigma -- standard deviation of Gaussian noise { int num; // total number of random to generate gaussRand double sum; // sum of uniformly distributed random number double gaussRand; double mean = 0.0; // mean of Gaussian noise sum = 0.0; num = 12; // compute sum of 12 uniform random number for (int i = 0; i < num; i++) sum += UniformRand(); gaussRand = sigma * (sum - 6.0) + mean; return gaussRand; }