6.3循环码.ppt

第6章 信道编码 信道编码 6.1 信道编码简介 6.2 线性分组码 6.3 循环码 循环码 循环码的定义 设C为(n，k)线性分组码，若任意一个码字都是另一个码字的循环移位，则称C为循环码。 例：C=(C0 C1 …… Cn-1) C(1)=( Cn-1C0 C1 …… Cn-2)： C(1)表示C的1次循环右移位, ……都是循环码的码字，则其全体结构可构成循环码集合C。 循环码 如：已知编码1101001，循环右移一位 —1110100 —0111010—0011101 —1001110—0100111 —1010011 —1101001 循环码的多项式 循环码的多项式表示 码字C=(C0C1……Cn-1)的码多项式C(x) C(x)= C0+C1x+……+ Cn-1xn-1 其中：多项式的次数： 定理：循环码C，(n，k)，若已知任意的码多项式C(x)，则该循环码的其它码多项式 例：已知（7,3）循环码的任意一个码字 1010011，求其所有的码字。 解：简单方法1：直接循环移位得所有码字。 方法2：用多项式求： 循环右移i位操作等价于码多项式乘以xi，再对 取余。即： 循环码的生成多项式 定理1：(n，k)循环码c(x)中存在一个非零的、首一的、次数最低且次数为r(rn)的码多项式g(x)，满足： （1）g(x)的常数项g0=1 （2）c(x)是码多项式当且仅当c(x)是g(x)的倍式。 （3） r=n-k 定理2：g(x)是(n，k)循环码的生成多项式，当且仅当g(x)是 的r次因式。 生成多项式的用途： P191例6.3.3：求(7，4)循环码的生成多项式。 解：生成多项式g(x)：r=n-k=7-4= 3次首一多项式 即将 因式分解： 选择 或 任一均可作为（7，4）循环码的生成多项式。 例：求输入消息m=1001时，(7，4)循环码的输出码字。 解： 6.3.2 循环码的生成矩阵 定理：(n，k)循环码的生成矩阵G由g(x)唯一确定，其第一行对应于g(x)的系数，第二行对应于xg(x)的系数，第k行对应于 的系数。 Gk*n：k行n列，则 生成的循环码码字：C=mG P193例6.3.4：求二进制(7，4)循环码的G。 （1）生成矩阵。 解：（1）设选 ，g(x)按升幂排列：则Gk*n=G4*7为 （2）求输入消息m=1001时的输出码字: 解：C=mG 代入得c=1010011 循环码的校验多项式 循环码的校验多项式h(x) (n,k)循环码的校验多项式h(x)定义为： 由于循环码是线性分组码，因此也满足CHT=0 循环码的校验多项式 循环码的校验矩阵 校验矩阵Hr*n：将h(x)的系数按幂次的降序排列：作为矩阵的第一行；将第一行向右移一位作为G的第二行；…。则 由于是循环码是线性的，因此也满足：GHT=0 循环码的校验矩阵举例 P193例6.3.4：求二进制（7，4）循环码的H。 系统循环码 系统循环码的定义：（n,k）循环码是系统码。 已知待发送的消息为：m=(m0m1……mk-1)，则 分析：系统循环码C=(校验位，信息位) 思路：将k位信息位整体向右移位r位，再加上 校验位。 按照以上思路可得系统循环码的码多项式为 系统循环码的码多项式 例：求输入消息m=1001时的（7，4）系统循环码码字。 解： 系统循环码的生成矩阵 系统循环码码字的第二种求法：c=mGs 生成矩阵Gs 又有两种求法： 求法1：由g(x)—G—初等行变换—Gs 求法2(不要求)： 系统循环码的生成矩阵 生成矩阵Gs 的求法2 (不要求) ： 系统循环码的一致校验矩阵 系统循环码的一致校验矩阵Hs，求法与6.2线性系统码相同。 例：已知二进制（7，4）循环码，求 （1）求系统生成矩阵。 （2）输入消息m=1001时的输出的系统循环码码字。 （3）求一致校验矩阵。 解：（1）选g(x)=1+x+x3可得生成矩阵G: 由于是求系统循环码的生成矩阵，则矩阵中需含有I4的单位阵，而直接求得的G中不含单位阵，所以它不是系统循环码的G。 需求系统循环码的Gs： 通过初等行变换得系统循环码的生成矩阵Gs （3）一致校验矩阵 （4）生成的系统循环码字集合： C=mGS 循环码编码器 循环码编码器的分类 （1）r级编码器：基于生成多项式g(x) （2）k级编码器：