信道编码简介.ppt

助教 刘磊：liul@mail.ustc.edu.cn * * 如果一个(n,k)线性码具有以下的属性，则称为循环码(cyclic code): 如果n元组c={c0,c1,…,cn-1}是子空间S的一个码字，则经过循环移位得到的c(1)={cn-1, c0 , … , cn-2}也同样是S中的一个码字；或者，一般来说，经过j次循环移位后得到的 c(j)={cn-j,cn-j+1,…,cn-1,c0,c1,…,cn-j-1}也是S中的一个码字。 * * 码字c={cn-1 … c1 ,c0}的各个分量可以看作是多项式c(D)的系数，即 c(D)= cn-1Dn-1 +…+ c1D + c0 每一项的存在或不存在对应了n元组中相应的位置为1或0，如果cn-1非0，那么多项式的阶数为n-1。 * * 如（7，3）循环码的全部码字为： * * 为了便于计算，常用码多项式表示码字，如（n，k）循环码，其多项式表示为： 第2号码字可用多项式表示为： * * 生成多项式g(D)及生成矩阵G 如果一种码的所有码多项式都是多项式g(D)的倍式，则称g(D)为该码的生成多项式。在循环码中，次数最低的多项式（0除外）就是生成多项式g(D)，其他码多项式都是其倍数。且该g(D)的阶数为r = n – k，常数项为1，是Dn+1的一个因式。为了寻求生成多项式，必须对Dn+1进行因式分解。 * * 以D7＋1为例： D7+1=(D+1)(D3+D+1)(D3+D2+1) 这样，我们可知， （n，k） g(D) （7，6） D+1 （7，4） D3+D+1或D3+D2+1 （7，3） (D+1)(D3+D+1)或 (D+1)(D3+D2+1) （7，1） (D3+D+1)(D3+D2+1) * * 循环码的生成矩阵多项式为： 然后将系数提出就得到生成矩阵G。 * * 例如，已知（7，4）码的生成多项式g(D)=D3+D2+1，求生成矩阵。 解：k=4 这样我们就可直接 得到生成矩阵G为： * * 由A＝MG，其中M=[mk-1 mk-2 …m1 m0]表示输入信息码元序列，我们可求出编码后的输出码组序列，但这样得到的循环码不是一个系统码。所谓系统码，指的是码组A的左边k位与M中的k个元素相同，而后面n – k位是M中元素的线性组合，表示监督码元。 为了得到系统码，就要求G矩阵的左边是一个k阶的单位阵，即是一个典型生成矩阵G = [Ik Q]形式。 * * 这样的系统码用多项式表示即为： A(D)=Dn-kM(D)+r(D) 式中M(D)是不大于k-1次多项式，Dn-kM(D)是不大于n-1次多项式，r(D)是不大于r-1次多项式，称为监督码多项式，它等于Dn-kM(D)除以g(D)得到的余式，表示为 r(D) = Dn-kM(D) mod g(D) 或 * * 由于典型生成矩阵G = [Ik Q]形式，与单位矩阵Ik每行对应的信息多项式为： Dn-kmi(D)=Dn-kDk-i =Dn-i ，i＝1,2,…,k ri(D) = Dn-i mod g(D) 由此得到生成矩阵中每行的码生成多项式为： Ci(D) = Dn-i + ri(D), i = 1,2,…,k 这样系统循环码生成矩阵多项式的一般表示式为： * * 例2：我们再对前面我们的例题进行求解，已知g(D)=D3+D2+1，希望给出系统循环码的生成矩阵。 解： r1(D)=D6 mod g(D) = D2+D r2(D)=D5 mod g(D) = D+1 r3(D)=D4 mod g(D) = D2+D+1 r4(D)=D3 mod g(D) = D2+1 所以，我们可写出生成矩阵多项式为： * * 生成矩阵G可写为： 其实这个矩阵我们也可以通过初等变换从第74页的矩阵得到。 * * * * 监督多项式h(D)和监督矩阵H 由于GHT=0,对循环码相应的有g(D)h(D)≡0,mod(Dn+1) 监督矩阵多项式可写为： 其中 系数不同！！ * * 例如：（7，3）循环码的生成多项式为g(D)=D4+D3+D2+1，求其监督矩阵。 解： * * 循环码的编码和译码 我们知道，系统码用多项式表示即为： A(D)=Dn-kM(D)+r(D) 编