北京交通大学通信原理探讨

通原研讨组员：肖逸然15231081庞凯怡15292012刘源1529203323组题目要求可以认为重复码和偶校验码是线性分组码，也是循环码，请说明原因；并分别列出(4,1)重复码和(4,3)偶校验码的生成矩阵(系统码形式)和生成多项式。证明重复码和偶校验码是线性分组码01PART1通原研讨PART1通原研讨【线性分组码】1：一个长度为n，包含个码字的分组码，若这个码字构成GF（2）上所有的n维向量空间V的一个k维子空间，则称这个分组码为线性分组码。2k2：在线性码中信息位和监督位是由一些线性代数方程联系着的，或者说线性码是按照一组线性方程构成的。3：分组码可以写成(n,k)形式，码字一共n比特，消息序列分组为k比特，每组增加校验（监督）位r=n-k比特。2kPART1通原研讨【重复码（n,1）】1证明重复码是分组码：因为重复码n个码元中，只有最高位为信息位，所以可以写为（n，1）码的形式，即分组码。2证明重复码是线性码：假设重复码一共有n位，最高位是信息位，则它的线性方程可以写为：0.......00013121aaaaaannnnn满足线性分组码定义，题目得证。PART1通原研讨【偶校验码（n，n-1）】1证明偶校验码是分组码，因为偶校验码的n个码元中，只有最低位为监督位，所以偶校验码可以写为（n,n-1）的形式，即为分组码。2证明偶校验码是线性码：偶校验码含1位校验位a0，与信息位an-1至a1构成一个代数式：0.....021aaann满足线性分组码的定义，题目得证。PART1通原研讨【线性分组码的性质】1封闭性：任意两个码字之和仍为一个码字对于重复码来说可能的取值为（1,1,1,1....1）或（0,0,0,0....0），显然任两个码字之和仍为一个码字对于偶校验码来说，一个（4,3）码的所有可能码为做加法检验可以知道满足封闭性2许用码字集合中必包含全零码。可以从重复码和（4,3）偶校验码中看出上面的性质。11111100101010010110010100110000【例】（2，1）重复码（2，1）重复码可以检出一个错误，但错误不能纠正。8【重复码的纠检错能力】PART1通原研讨（3，1）重复码（3，1）重复码可以检出最多不超过两个错误，能纠正一个错误，但不能检出3个错误。9PART1通原研讨10【偶码的纠检错能力】PART1通原研讨偶校验码只能发现单个或奇数个错误，而不能检测出偶数个错误，也不能检验突发错误，因此它的检测水平不高。奇偶校验码水平奇偶校验码水平垂直奇偶校验码检错能力增强证明重复码和偶校验码是循环码02PART2通原研讨PART2通原研讨【循环码】如果其任何一个码字循环移位(左移或右移)后仍然是一个码字，称一个(n,k)线性分组码是循环码。PART2通原研讨【重复码（n,1）】因为重复码的内容为（1,1,1,1....1）或（0,0,0,0....0），无论向左循环还是向右循环都满足条件，所以重复码是循环码。【偶校验码（n,n-1）】1偶校验码也是循环码，举一个（4,3）码的例子，可以看到一共有4个循环圈，0000,0101,0011，1111所有的码都能看成是由这四个循环构成的，无论左移右移，循环圈里1的个数不会改变，所以仍然满足偶校验关系。2与此类似，所有的偶校验码都是循环码。11111100101010010110010100110000PART2通原研讨【偶校验码（n,n-1）】符合循环码的必要条件——（n，k）分组码中要有一个正确的生成多项式g（x）能够生成循环码的g（x）的条件：g（x）是xn＋1的因式，其最高次幂为n-k,最低项为1，其非0系数的个数不小于相应（n，k）分组码的d0值。11111100101010010110010100110000偶校验码g（x）＝x＋1d0＝2等于非零系数个数满足条件03PART3通原研讨列出(4,1)重复码和(4,3)偶校验码的生成矩阵(系统码形式)PART3通原研讨【（4,1）重复码的生成矩阵】根据（4,1）重复码的线性关系式：000004142434aaaaaaaa则H矩阵为100101010011对应的P矩阵为111PART3通原研讨则Q矩阵为111对应的生成矩阵G为1111PART3通原研讨【（4,3）偶校验码的生成矩阵】（4,3）偶校验码的线性多项式为00123aaaa则H矩阵为1111则P矩阵为111PART3通原研讨则Q矩阵为对应的生成矩阵G为111110010101001分别列出(4,1)重复码和(4,3)偶校验码的生成多项式。04PART4通原研讨PART4通原研讨【生成多项式】生成多项式g(x)：最大幂次n-k=r(监督位数)。码多项式v(x)是g(x)的倍式。循环码由n及g(x)唯一确定，次数低于n的多项式若能被g(x)整除，则是一个码多项式。所有这样的多项式构成(n,k)循环码。PART4通原研讨【前提结论】x^n+1因式分解所得的一次因式，必是(x+1)，分解所得的二次因式，必是(x^2+1)或(x^2+mx+1)，其中m是常数。一般说来，n是奇数时，有一个一次因式，其余是二次因式；n是偶数时，只有二次因式，没有一次因式。PART4通原研讨【（4,1）重复码的生成多项式】确定生成多项式，因式分解𝑥4+1，找到3次因式（4,1）重复码的生成多项式)(xg𝑥4+1=𝑥+1（𝑥3+𝑥2+𝑥+1)（𝑥3+𝑥2+𝑥+1)PART4通原研讨【（4,3）偶校验码的生成多项式】确定生成多项式，因式分解，找到1次因式（4,3）偶校验码的生成多项式1)(xxg𝑥4+1=𝑥+1（𝑥3+𝑥2+𝑥+1)𝑥4+1PART4通原研讨【对偶性】（4,3）偶校验码的校验位为1位，（4,1）重复码的校验位为3位，他们的生成多项式相乘正好为，所以偶校验码和重复码存在对偶性。𝑥4+1100101010011（4，1）H阵1111（4，1）G阵110010101001（4，3）G阵1111（4，3）H阵100101010011线性行变换PART4通原研讨【对循环码加入噪声后进行仿真】clear;clc;closeall;%清屏N=11;%信息码的行数n=7;%码长k=4;%信息位长sig=randint(N,k)%信号码元code=encode(sig,n,k,'cyclic')%循环编码sig1=decode(code,n,k,'cyclic')%循环解码errs1=biterr(sig,sig1)%计算误差比特数noise=randerr(N,n,2)%产生随机噪声rsig=double(xor(code,noise))%加噪sig2=decode(rsig,n,k,'cyclic')%加噪解码errs2=biterr(sig,sig2)%计算加噪后的误差比特数PART4通原研讨【仿真实验】sig=10111010110111100111011001100010011010001011sig1=11110100110000011001111001010001110000111000errs1=0code=00010110111010001110110011100100111001011000101101100010001011010110000001011PART4通原研讨【仿真实验】sig2=00111111101111110001011111011110001110101010errs2=18noise=10010001000001000011001000010010100001000100010100100100100010001000100100001rsig=10000111111011001101111011110110011000011100111001000110101001011110100101010欢迎老师、同学指正通原研讨