第6讲_信道编码：汉明码纠检、循环码

信道编码例：设（7,4）线性码的生成矩阵G为：当信息位为0001时，试求其后的监督位。1101000101010001100101110001例：试求上例的监督矩阵H解：根据生成矩阵和监督矩阵的关系：G=[Ik·Q]，H=[P·Ir]可得监督矩阵H为：100110101010110010111对偶码定义：对于线性分组码：1）将(n,k)码的监督矩阵H作为(n,n–k)码的生成矩阵G’；2）将(n,k)码的生成矩阵G作为(n,n–k)码的监督矩阵H’这样的(n,k)码与(n,n–k)码互为对偶码编码过程观察(7,4)码的监督关系式：可设计出相应的编码电路：654265316430uuucuuucuuuc6u5u4u2c6u5u3u1c6u4u3u0c6u4u3u5u2c0c1c6u4u3u5u译码纠、检过程错误矩阵/错误图样E：设发送码组为c，接收码组为y，则对于二元有限域，上式中的减法等价于加法，即：对于二元有限域的加法的具有确定两个码组中不同比特位的特性，例如：假设长度为n的码组A和B分别为：假设这两个码组的第k位不同，其他位相同，根据加法规则：因此接收端可以利用这种特性进行纠错，即若能确定错误图样就可以进行纠错：120nnecyeee120nnecyeee10()nnkaaaa10()nnkbbbb1010()(0010)()nnknnkaaaabbbb除了第k位为1，其他均为0。若有1位以上的不同，同样可以根据相加之后的1的位置确定不同的比特位，此特性还说明A与B之和的码组的码重等于A与B的码距ˆcey接收端纠错后的码组接收端利用监督矩阵计算校正子S，即可见校正子S只与E有关，即错误图样与校正子之间有确定的关系而校正子S可以用接收码组y与监督矩阵HT相乘获得，则错误图样也就得到确认，即：上式即为一个线性方程组，但它的解不唯一，即求得的错误图样不唯一。假设其中一个解为e0，即e0HT=S，则对于码组集合中的任一许用码组c，下式一定成立：因此这个线性方程组一共有2k个解，即2k个错误图样TTTTTSyHecHeHcHeHTSeH000()TTTTecHeHcHeHS因此利用等式及2k个错误图样可以纠正出2k个码组，即：稍作变换，每个等式进行移项：再由两个码组之和的码重等于两个码组的码距，可得：最佳译码应选择那些离y最近的，再由上式可知：1）所有错误图样中选择码重最小图样；2）该图样所对应的作为纠正后的码组ˆcey00ˆcey11ˆcey2121ˆkkcey00ˆecy11ˆecy2121ˆkkecy00ˆ(,)()dycWe11ˆ(,)()dycWe2121ˆ(,)()kkdycWeˆcˆc例如，某(7,3)线性分组码的监督矩阵为：1）若收到的码组y=(1001001)，则利用式S=yHT计算出校正子，其结果为S=(0111)；2）再利用式eHT=S计算出所有可能的错误图样，因为k=3，则共有8个图样分别为：(1001001)(1010100)(1101110)(1110011)(0000111)(0011010)(0100000)(0111101)3）其中图样(0100000)的码重最小，则纠正后的码组为：e+y=(0100000)+(1001001)=(1101001)1011000111010011000100110001H在实际中译码：1）一般事先确定好每种校正子S所对应的所有错误图样；2）选择码重最小的错误图样作为可纠正的错误图样；3）然后将校正子与最小码重的错误图样制成表格；4）译码时，利用校正子查表，然后用等式c=e+y进行纠正译码电路包括三个部分：1）计算校正子；2）查找确定纠正图样；3）纠正接收码组中的错误某（7，4）码的监督矩阵以及校正子错误图样表：查表方法如下：观察错误图样表发现校正子与错误图样一一对应利用二元有限域的乘法规则，对于等式：S2·S1·S0=1当且仅当S2、S1、S0全为1时成立，因此：1）对每一校正子设计一个这样的乘式，保证其乘积为1；2）对于右表共设计7个乘式，对应于7种可能出现的错误图样；3）当三位校正子确定后，代入到7个乘式中计算，那个乘式为1，就表明是哪一个图样2101SSS2101SSS21021021021021011111SSSSSSSSSSSSSSS2S1S0S2S1S0S由其监督矩阵可知，其监督位与信息位之间的偶监督关系：653226541154300uuucSuuucSuuucS进行纠错，即实现等式：ˆcey7个逻辑与门所进行的运算分别为：2102102102102102102101,1,11,1,11SSSSSSSSSSSSSSSSSSSSS线性分组码的封闭性特征的证明：码组集合中任意两许用码组之和仍为一许用码组证明：设A1和A2为码中任意两许用码组，则有A1·HT=0A2·HT=0A1·HT+A2·HT=(A1+A2)·HT=0即（A1+A2）必是该码中一许用码组由封闭性以及二元有限域的加法特性可知，两个码组之间的距离必是另一码组的重量，码的最小距离等于非零码的最小重量。此即证明了为线性分组码的另一特征是线性分组码中最主要、最有用的一种码与一般线性分组码相比，循环码具有循环特性，每个码组经任意循环移位之后仍然在码组的集合中数学定义：设C为某(n,k)线性分组码的码组集合，如果对C中任意一个码组c=(an-1an-2……a1a0)，它的循环移位c(1)=(an-2an-3…a1a0an-1)也属于C，则称该(n,k)码为循环码其中c(i)表示c码组循环移位i次例如：某(7,4)循环码组集合中的一个码组为(1000101)，向左循环移位一次后的码组(0001011)仍为码组集合中第一个许用码组循环码码多项式码多项式是描述循环码的主要方法对于任一长为n的码组c=(an-1an-2……a1a0)可用一多项式来表示：c(x)=(an-1xn-1+an-2xn-2+……+a1x1+a0)此多项式称码多项式，式中每项的各分量an-1,an-2,……,a1,a0是多项式的系数系数不为零的x的最高次数为多项式c(x)的次数，或称多项式的阶数，degc(x)例如：某码组(1100101)对应的码多项式可表示为c7(x)=1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1=x6+x5+x2+1码多项式与码组的关系：本质上是一回事，仅是表示方法的不同而已222102102210()()()()()()()()()()xgxuguuuxgxuxgxuxgxugxgxuxuxugxuxgx码多项式的加法与乘法有两个码多项式u(x)=u2x2+u1x+u0；g(x)=g1x+g0相加：u(x)+g(x)=(u2+0)x2+(u1+g1)x+u0+g0相乘：u(x)·g(x)=u2g1x3+(u2g0+u1g1)x2+(u1g0+u0g1)x+u0g0若使用g(x)的系数组成矩阵：同时u(x)的系数组成矩阵:将矩阵u和g相乘：101010000000ggggggg210uuuu212011100100ugugugugugugug相当于将g(x)乘以x2，使得g(x)的次数变为3，即使g(x)的最高次与u(x)·g(x)一样：x2g(x)=g1x3+g0x2然后将上式的系数作为矩阵的第一行相当于将g(x)乘以x，使得g(x)的次数变为2：xg(x)=g1x2+g0x=0x3+g1x2+g0x然后将上式的系数作为矩阵的第二行g(x)不变：g(x)=g1x2+g0x=0x3+0x2+g1x+g0然后将上式的系数作为矩阵的第三行所得到的矩阵的各项恰好与u(x)·g(x)所得多项式的系数相等，因此可用这种矩阵相乘代替两个多项式相乘，这一特性可用于构造循环码的生成矩阵210101000()00()00()ggxgxgggxgxgggx码多项式的模运算正整数的模运算若一正整数M除以正整数N，所得到的商为Q，余数为R，可表示为其中Q为整数，则在模N运算下，上式的结果为：多项式的模运算与正整数的模运算相同，一般利用长除法计算商式和余式有两个多项式a(x)和p(x)，一定存在有唯一的多项式Q(x)和r(x)，使得：称Q(x)是a(x)除以p(x)的商式，r(x)是a(x)除以p(x)的余式，在模p(x)运算下且有即：除到余式的次数小于除式为止，当能整除时次数为00MRQRNNN)mod，记模(NNRM为()()()()axQxpxrx)](mod[)()(xpxrxa0deg()deg()rxpx定理：对于(n,k)循环码，若c(x)对应码组c=(an-1an-2……a1a0)，c(1)的一次循环移位c(1)=(an-2an-3……a1a0an-1)及c(i)(x)对应的c码循环移位i次c(i)，则有：证明：码组c的多项式为：则有：(1)()mod(1)mod(1)()[()],()[()]nniixxcxxcxcxxcx-1-21210()()nnnncxaxaxaxa-121-2-121-1-210-1-1101)1-1(-()(1)()nnnnnnnnnnnnxcxaxaxaxaxaxaaxcaaxxxxaa(1)1mod(1)mod(1)(1)[()][(1)()]()nnnnxxxcxaxcxcx相当于将多项式c(x)循环移位一次能被xn+1整除，所以余数为0最高此为n–1，小于(xn+1)的幂次，所以余数为c(1)(x)此定理说明若c(x)是(n,k)循环码中的一个码组，则它的循环移位xic(x)均为该循环码的码组，且这些码多项式都是模xn+1的一个余式例如：(7,4)循环码的第12个码组c12为：1011000，则其码多项式为：c(x)=x6+x4+x3请写出c12左循环移位3次的码组解：i=3，则x3c(x)=x9+x7+x6其对应码组为：1000101，它是(7,4)循环码中的第4个码组c47362mod1[()]1xxcxxx27976927627621111xxxxxxxxxxxxx循环码生成多项式定义：记C(x)为(n,k)循环码的所有码组对应的多项式的集合，若g(x)是C(x)中除0多项式以外次数最低的多项式，则称g(x)为这个循环码的生成多项式其一般形式为：g(x)=xr+gr-1xr-1+……+g1x1+1g(x)具有以下性质：1）g(x)的0次项是1；2）循环码的每一码多项式c(x)都是g(x)的倍式，且每一个小于等于n-1次的g(x)的倍式一定是码多项式；3）g(x)的最高次为n-k，且是唯一的；4）g(x)是xn+1的一个因子因为g(x)是n-k次的多项式，故xkg(x)为一个n次多项式则xkg(x)除以xn+1的商必为1，余式记为b(x)即：xkg(x)=1•(xn+1)+b(x)表示g(x)向左移动k次，并且仍为许用码组，即：是g(x)的倍式，则有：b(x)=u(x)g(x)则xn+1=g(x)[xk+u(x)]=h(x)g(x)即证明g(x)为xn+1的一个因子因此，这一性质也就指出了g(x)的求解方法，即对多项式xn+1进行分解：xn+1=(x+1)(xn-1+xn-2+…+x+1)例如：(7,k)循环码的生成多项式，x7+1可以作如下分解（分到不能分为止）：(x+1)(x3+x2+1)(x3+x+1)循环码的生成由生成多项式的定义及其性质可知：1）循环码完全由其码组长度n及生成多项式g(