西电纠错码课件---第四章_多项式环及循环码

null第四章 多项式环与循环码第四章 多项式环与循环码课件下载地址 jiucuoma@126.com 密码:111111一种特殊的线性分组码一种特殊的线性分组码循环算子L：对n重码字A=(an-1, an-2, an-3, … , a2, a1, a0)，有B = L(A) = (bn-1, bn-2, bn-3, … , b2, b1, b0) = (an-2, an-3, … , a2, a1, a0, an-1) 循环特性：对任意许用码字C，则L(C)也是许用码字 循环码： 一个 (n,k )线性码C，如果每个码字的循环移位仍是一个码字,称该码为循环码。循环码的描述循环码的描述 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ：如何构造和描述一个循环码？满足什么样条件的循环码可以有较好的距离特性？多项式的引入多项式的引入如果将码字描述成n阶多项式的形式，A(x)= an-1xn-1+an-2xn-2 +an-3xn-3+ … +a2x2+a1,x+a0，则循环算法就可以描述为L(A(x))=xA(x) mod (xn-1) 便于描述：对任何一个多项式D(x)，有D(x)A(x) mod (xn-1)为许用码字，这里并没有限定D(x)的幂次，但可以肯定的一点是不同的D(x)A(x) mod (xn-1)是有限的，其个数由A(x)决定，这也决定了码集的冗余度和纠错能力，什么样的A(x)可以得到什么样的冗余度？哪些A(x)是等价的？ 第一节 多项式与多项式环第一节 多项式与多项式环要求掌握的内容要求掌握的内容多项式剩余类环 循环群 一、复习几个概念一、复习几个概念同余、剩余类 群 环 域同余和剩余类(p23)同余和剩余类(p23)同余：若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为剩余类(Residue)：给定正整数m，可将全体整数按余数相同进行分类，可获得m个剩余类，分别用群(Group)的定义(p26)群(Group)的定义(p26) 设G是一个非空集合，并在G内定义了一种代数运算 “ 。”，若满足：1) 封闭性。对任意，恒有则称G构成一个群。若加法，恒等元用0 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示， 若为乘法，恒等元称为单位元环(Ring)的定义(p30)环(Ring)的定义(p30)非空集合R中，若定义了两种代数运算加和乘，且满足： 1) 集合R在加法运算下构成阿贝尔群 2) 乘法有封闭性 3) 乘法结合律成立，且加和乘之间有分配律null子环、理想和主理想(P101子环：若环R中的子集S，在环R中的定义的代数运算也构成环，则称S为R的子环。 理想：S是R的一个子环，若S中的元素由某几个元素及其所有可能的倍数构成，则S是一个理想 主理想：若理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为主理想。二、多项式剩余类环(P103)二、多项式剩余类环(P103)有关多项式的几个概念 多项式的加法和乘法 多项式剩余类环的定义null多项式 f(x)=fnxn+ fn-1xn-1+…+ f1x+f0其中i=0,1,…n，该多项式称为域Fp上的多项式多项式次数 degf(x) 系数不为零的x的最高次数称为多项式f(x)的次数首一多项式 最高次数的系数为1的多项式有关多项式的几个概念null 既约多项式 设f(x)是次数大于零的多项式，若除常数和常数与本身的乘积以外，再不能被域Fp上的其他多项式整除，则称f(x)为域Fp上的既约多项式 多项式的因式分解问题、根的问题有关多项式的几个概念多项式的加法和乘法f(x)=fnxn+ fn-1xn-1+…+ f1x+f0g(x)=gnxn+ gn-1xn-1+…+ g1x+g0若对所有i, fi=gi, 则f(x)=g(x)多项式加法f(x)+g(x)=(fn + gn)xn+ (fn-1 + gn-1)xn-1+…+ (f1 + g1)x+(f0 + g0)多项式乘法结论：按上述定义的加法和乘法运算，Fp[x]构成一个具有单位 元、无零因子的可换环多项式的加法和乘法多项式剩余类环定义：以一个Fp上的多项式f(x)=fnxn+ fn-1xn-1+…+ f1x+f0为模的剩余类全体构成一个多项式剩余类环 Fp上的所有次数小于n-1的多项式构成n次多项式的剩余类全体 剩余类之间的加法和乘法运算规则多项式剩余类环null 1、GF(2)上的多项式 f(x)=x2+1的剩余类全体为： 2、GF(2)上的多项式 f(x)=x2+x+1的剩余类全体为： 对所定义的加法和乘法运算，前者构成剩余类环，后者构成域结论：若n次首一多项式f(x)在域Fp上既约，则f(x)的剩余类环构成 一个有pn个元素的有限域Examples两个结论两个结论多项式环Fp[x]的一切理想均是主理想 多项式剩余类环Fp[x]/f(x)中的每一个理想都是主理想。第2节 循环码的描述第2节 循环码的描述要求掌握的内容要求掌握的内容定义 循环码的代数性质 循环码的生成多项式和校验多项式 循环码的生成矩阵和校验矩阵 循环码的系统码形式 null 定义1：设CH是一个[n.k]线性分组码，C1是其中的一个码字，若C1的左(右)循环移位得到的n维向量也是CH中的一个码字，则称CH是循环码。一、循环码定义将码字 看成如下多项式的系数:将码字 看成如下多项式的系数:循环码码字与多项式之间的关系因此，循环码的每个码字对应一个次数小于等于n-1的多项式。并且，码字与多项式之间是一一对应的。二、循环码的代数性质二、循环码的代数性质 假设有两个码多项式 则有二、循环码的代数性质二、循环码的代数性质 定理4.1 循环码C中次数最低的非零码多项式是唯一的。 由于循环码是线性码，因此 证明：令 为循环码中次数最低的一个非零多项式。假设该多项式不唯一，即存在另一个次数为r的多项式 是一个次数比r更低的码多项式。二、循环码的代数性质二、循环码的代数性质 定理4.1 循环码C中次数最低的非零码多项式是唯一的。 即 证明：若 则 是一个次数比r更低的非零码多项式。 因此，g(x)是唯一的。 这与假设相矛盾，因此必有二、循环码的代数性质二、循环码的代数性质 定理4.2 令 为循环码C中最低次数的非零码多项式，则常数项g0一定等于1。 这与之前假设g(x)是次数最低的非零码多项式相矛盾。由定理4.2可知，次数最低的非零码多项式具有如下形式由定理4.2可知，次数最低的非零码多项式具有如下形式因此，由循环码的定义，它们一定是循环码的码多项式，且它们的线性组合也一定是一个码多项式，即nullnull 因此，码多项式必为g(x)的倍式。null定理4-4(p147) (n,k)循环码中，有且仅有一个次数为n-k的码多项式 每一个码多项式是g(x)的倍式，且每个次数不大于n-1且为g(x)的倍式 的多项式必为一码多项式。null注： 由上述定理， (n,k)循环码的每一个码多项式可表示为生成多项式的次数等于码中校验位的个数，即等于n-k.问题：如何寻找生成多项式g(x)？问题：如何寻找生成多项式g(x)？三、生成多项式三、生成多项式 定理4-5(p148):GF(q)(q为素数或素数的幂)上[n,k]循环码的生成多项式g(x)一定是xn-1的n-k次因式： xn-1= g(x) h(x)。 反之，若g(x)为n-k次多项式，且xn-1能被g(x)整除，则g(x)一定能生成一个[n,k]循环码三、生成多项式三、生成多项式 结论1:找一个[n,k]循环码，即是找一个n-k次首一多项式g(x)，且g(x)必是xn-1的因式。nullg(x)决定生成矩阵，h(x)决定校验矩阵四、循环码的生成矩阵和校验矩阵nullnullnullExamples GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 试求一个[7,4]循环码。g(x)、 xg(x)、x2 g(x)、 x3g(x)、null五、循环码的系统码(P151)null由于生成矩阵G中的k行要求线性无关，因此在求余式时，可选择k个线性无关的信息组 (1,0,0,…,0) xk-1， (0,1,0,0,…0) xk-2, …(0,0,0,…,0,1) 1nullnull循环码的编码原理(1)循环码的编码原理(1)基本步骤([n,k])1、分解多项式xn-1=g(x)h(x)2、选择其中的n-k次多项式g(x)为生成多项式3、由g(x)可得到k个多项式g(x), xg(x),…xk-1g(x)4、取上述k个多项式的系数即可构成相应的生成矩阵5、取h(x)的互反多项式h*(x),取h*( x), xh*( x),… xn-k-1h*( x) 的系数即可构成相应的校验矩阵循环码的编码原理(2)循环码的编码原理(2)可选择k个线性无关的信息组 (1,0,0,…,0) xk-1， (0,1,0,0,…0) xk-2, …(0,0,0,…,0,1) 1null第3节 循环码的编码电路(P165,174)第3节 循环码的编码电路(P165,174)多项式乘法和除法电路 循环码的编码电路(乘法和除法)一、多项式乘法和除法电路一、多项式乘法和除法电路nullnull 乘B(x)运算电路 (利用校验多项式h(x)编码时会用到)nullbr-2br-1输出C(x)输入A(x)a0,a1,…ak乘B(x)运算电路akb0akb1akbr-2akbr-1null除B(x)运算电路a0,a1,…ak除式B(x)构成电路，被除式A(x)的系数依次送入电路nullhr-2hr-1输入A(x)a0,a1,…akgr-1输出商q(x)乘H(x),除g(x)运算电路二、循环码编码电路(P174)二、循环码编码电路(P174)nulln-k 级编码器n-k 级编码器基本原理：利用生成多项式g(x)若要求编成非系统码形式，则利用乘法电路若要求编成系统码形式，则利用除法电路n-k级乘法电路(非系统码形式)n-k级乘法电路(非系统码形式)取g(x), xg(x),…xk-1g(x)的系数可构成生成矩阵Gn-k级乘法电路(非系统码形式)n-k级乘法电路(非系统码形式)若信息序列 m=(mk-1, mk-2,…m0),则mG对应的n维向量为：该n为向量正是多项式m(x)g(x)的系数nullnullExamples GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 试画一个[7,4]循环码的n-k级乘法编码电路。n-k级除法电路(系统码形式)n-k级除法电路(系统码形式) (1,0,0,…,0) xk-1， (0,1,0,0,…0) xk-2, …(0,0,0,…,0,1) 1nulln-k级除法电路(系统码形式)n-k级除法电路(系统码形式)对任意信息多项式m(x), xn-km(x)除g(x)可得余式r(x)， m(x)的系数为信息序列m r(x) 的系数为m对应的校验比特n-k级除法电路(系统码形式)n-k级除法电路(系统码形式)若信息序列 m=(mk-1, mk-2,…m0)对应的多项式m(x)=mk-1xk-1+ mk-2xk-2+…+m0n-k级除法电路(系统码形式)n-k级除法电路(系统码形式)综上，循环码的系统码电路是信息多项式m(x) 乘xn-k,除g(x)的实现电路null输入m(x)m0,m1,…mk-1gn-k-1-g0-gn-k-1-gn-k-2乘xn-k除g(x)运算电路k 级编码器k 级编码器基本原理：利用校验多项式h(x)为系统码编码电路k 级编码器k 级编码器若信息序列 m=(mk-1, mk-2,…m0)对应的多项式m(x)=mk-1xk-1+ mk-2xk-2+…+m0码多项式C(x)= m(x)g(x),且C(x)为系统码h(x)C(x)= h(x)m(x)g(x) = m(x)(xn-1) = m(x)xn-m(x) = mk-1xn+k-1+ mk-2xn+k-2+…+m0xn -(mk-1xk-1+mk-2xk-2+…m0)k 级编码器k 级编码器h(x)C(x)的乘积中，xn-1, xn-2,… xk次的系数为零k 级编码器k 级编码器由于hk=1cn-1-k = - (h0 cn-1 +h1 cn-1-1 + …+hk-1 cn-1-(k-1))cn-2-k = - (h0 cn-2 +h1 cn-2-1 + …+hk-1 cn-k-1)cn-3-k = - (h0 cn-3 +h1 cn-3-1 + …+hk-1 cn-k-2)cn-k-(n-k) = - (h0 ck +h1 ck-1 + …+hk-1 c1)null循环码k级编码电路nullExamples:设[7,4]循环码的生成多项式为 g(x)=x3+x2+1，试 1)写出它的校验多项式h(x) 2)求出生成矩阵和校验矩阵 3) 求出系统码的生成矩阵和校验矩阵 4) 画出(n-k)级系统码编码电路和k级编码电路null1) h(x)=(xn-1)/g(x)=x4+x3+x2+12) h*(x)=x4+x2+x+1nullnull作 业作 业设[7,4]循环码的生成多项式为g(x)=x3+x+1，试 1)写出它的校验多项式h(x) 2)求出生成矩阵和校验矩阵 3) 求出系统码的生成矩阵和校验矩阵 4) 画出(n-k)级系统码编码电路和k级编码电路null1) h(x)=(xn-1)/g(x)=x4+x2+x+12) h*(x)=x4+x3+x2+1nullnull第四节 几类特殊的循环码第四节 几类特殊的循环码最小循环码：一个理想中不再含有任何的非零理想，此理想对应的循环码是最小循环码(p158) 缩短循环码：对循环码缩短得到的码(p159) 准循环码 双环循环码第五节 用生成多项式的根定义循环码(p152)第五节 用生成多项式的根定义循环码(p152)研究表明，生成多项式有重根的码一般都要比无重根的码差，因此只考虑无重根的码，或构造无重根的多项式。 循环码的编码问题转化为：如何由给定的根来得到生成多项式g(x)? GF(q)上多项式xn-1无重根的充要条件是n与q互素。因此对GF(2)而言，充要条件即为n为奇数。用指定的根确定码长和生成多项式(1)用指定的根确定码长和生成多项式(1)给定r个根 , 每个根都有级数ei，即 ，则码长为所有级的最小公倍数； 每个根都可有一个最小多项式m(x)，而生成多项式则是所有根的最小多项式的最小公倍式； 同一共轭根系的根在设计生成多项式时的效果相同，只需考虑其中一个；用指定的根求生成多项式(2)用指定的根求生成多项式(2)给定必含根 ，求生成多项式g(x)时，要先找出各个根的最小多项式（可计算或查表），然后求它们的公倍式。 由于共轭根系的最小多项式相同，需先要找出必含根中包括哪几个共轭根系用根形成生成多项式举例用根形成生成多项式举例GF(211)中，为本原元，令=89，求以、2、3、4为根的二进制循环码。的级数为211-1=2047=8923，23=(89)23=1，因此的级为23，如果以为根，则它的共轭根系也为根：、2、4、8、16、32=9、18、36=13、26=3、6、12。例（续）例（续）由于所要求的其它必含根2、3、4都包括在这个共轭根系中，它们有相同的最小多项式 g(x)=m(x) =(x-)(x-2) (x-4) (x-8) (x-16) (x-9) (x-18) (x-13) (x-3) (x-6) (x-12) = x11 + x9 + x6 + x5 + x4 + x2 + 1 这是著名的Golay码，能纠3个错，是一种完备码。（上面的化简中要用到m()=0和=89 ）由生成多项式根定义的校验矩阵(1)由生成多项式根定义的校验矩阵(1)若g(x)有r个不相等的根，则每个根必为每个码多项式的根， 可将所有根代入是否为零来验证是否为码多项式； 也可由此得到循环码的校验矩阵。 （此处的运算是在扩域GF(qm)上的）由生成多项式根定义校验矩阵(2)由生成多项式根定义校验矩阵(2)由生成多项式根定义的校验矩阵(3)由生成多项式根定义的校验矩阵(3)BCH码BCH码用GF(qm)中的n级元素的-1个连续幂次为根的多项式生成的循环码称为BCH码。它的自由距不小于。如果根集中有本原元,则码长n=qm-1，称为本原BCH码RS码RS码GF(q)上的码长N=q-1的本原BCH码称RS码 RS码的符号域与根域相同 RS码生成多项式g(x)=(x-m0) (x-m0+1)…(x-m0+-2)，常取m0=1。其码距为。即生成的码为(n,k,d)=(q-1, q-, )。因此RS码被称为极大最小距离可分码。第六节 循环码的译码(P190)第六节 循环码的译码(P190)一般译码原理 捕错译码 大数逻辑译码一、一般译码原理(P190)一、一般译码原理(P190)null基本思想与线性分组码类似1、根据接收序列R计算伴随式S=RHT(n-k维向量)2、根据伴随式S寻找错误图样E3、根据错误图样E估计码向量C‘， 进而计算信息序列伴随式计算的多项式表示伴随式计算的多项式表示系统循环码的一致校验矩阵H系统循环码的一致校验矩阵Hnull循环码伴随式 可用除法电路实现循环码伴随式 可用除法电路实现由此可知：循环码的检错电路易于实现。null输入m(x)m0,m1,…mL-1gn-k-1-g0-gn-k-1-gn-k-2乘xn-k除g(x)运算电路循环码的检错功能在ARQ中的应用(1)C(x)发送端实现电路：在数据序列后端添加CRC校验循环码的检错功能在ARQ中的应用(2)循环码的检错功能在ARQ中的应用(2)输入R(x)r0,r1,…rn-1gn-k-1-g0-gn-k-1-gn-k-2若移位寄存器的存储值全部为零，则表示收到的码字为合法码字， 否则，有错，将向发送端反馈一个信号，用于重传。接收端实现电路：将接收序列通过一除法电路，判断是否有错。计算伴随式电路的特点计算伴随式电路的特点定理：若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))。译码时，可将错误图样进行归类，即任一错误图样及其循环移位作为一类nullExample: 循环码生成多项式g(x)=x3+x+1， 计算E(x)=x6和E(x)=x5的伴随式循环汉明码译码电路循环汉明码译码电路[7,4,3]循环汉明码的生成多项式为x3+x+1null输入R(x)循环汉明码译码电路 (需要14移位)nullExample：设计一个由g(x)=x4+x3+1 生成的[15,11]循环汉明码译码电路。基本要求：需要一个除法电路和一个逻辑电路要设计逻辑电路，须知道该码可纠正的错误图样及伴随式汉明码可纠一个错误，只需知道一个错误图样的伴随式 伴随式又可由校验矩阵H得到扩展汉明码的译码(p195)扩展汉明码的译码(p195)缩短循环码的译码(p197)二、捕错译码(P197)二、捕错译码(P197)基本原理基本原理基本原理基本原理若错误集中在校验元的n-k位上，即EI(x)=0, E(x)=EP(x)此时，伴随式就是错误图样，C’(x)=R(x)-S(x)可用捕错译码循环码必须满足可用捕错译码循环码必须满足1、错误必须集中在任意连续的n-k位上可利用循环码的特点将错误移到后n-k位上 2、k < n/t 或 t < n/k 或 R < 1/t错误集中在n-k个校验元上的条件错误集中在n-k个校验元上的条件纠正t个错误的GF(q)上的[n,k]循环码，捕错译码 过程中，已把t个错误集中在Ri(x)的最低次n-k 位 以内的充要条件是：其中w(Si(x))是伴随式Si(x)的重量null若前面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)一致，即可找到最终的错误图样三、大数逻辑译码原理(P206)三、大数逻辑译码原理(P206)关于仿真程序的几个问题关于仿真程序的几个问题null产生信息序列编码通过信道译码与信息序列比较，判断是否有错计算误比特率中止YesGaussian Noise Program(1)Gaussian Noise Program(1)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(2)Gaussian Noise Program(2)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) * sqrt((double)num / 12.0) + mean; return gaussRand; }null作业2设GF(2)上的多项式x2+x+1 试写出模该多项式的剩余类全体 在模多项式的加法和乘法运算下构造加法和乘法运算表 3) 上述剩余类全体在所定义的运算下是否构成域？ 4) 若构成域，所有非零元素在上述定义的乘法运算下是否构成循环群？若是，该循环群的生成元是什么？单位元是什么？每个元素的级是多少？null系数取自GF(p)的，以w为根的所有首一多项式中，次数最低的称为w的最小多项式m(x)， m(x)的次数m称为w的次数，称w为m次域元素 m(x)在GF(p)上不可约，但在GF(pm)上可以完全分解成一次因式之积，其根为共轭根系