信息论与编码第八章纠错编码.pptx

信息论与编码第八章纠错编码;内容提要;内容提要;1.信道纠错编码;2.差错控制系统模型及分类;2.差错控制系统模型及分类;2.差错控制系统模型及分类;2.差错控制系统模型及分类;2.差错控制系统模型及分类;3.差错类型;3.差错类型;4.纠错码的分类;4.纠错码的分类;内容提要;近世代数简介;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;1.群;2.域;2.域;2.域;2.域;2.域;3.环;3.环;3.环;3.环;3.环;3.环;内容提要;1.分组码相关定义;1.分组码相关定义;1.分组码相关定义;定义：[n,k]线性分组码是GF(q)上的n维线性空间中的一个k维子空间。

;2.线性分组码定义;2.线性分组码定义;2.线性分组码定义;2.线性分组码定义;容易验证C是线性的。假设消息序列与码字序列的映射关系为如下两种：

第一种：映射关系为：

第二种：映射关系与第一种截然不同。;三、线性分组码;三、线性分组码;三、线性分组码;三、线性分组码;三、线性分组码;三、线性分组码;三、线性分组码;三、线性分组码;例题;由生成矩阵;把校验矩阵;;（n，k）线性分组码编码电路;;4.伴随式与译码;4.伴随式与译码;4.伴随式与译码;;;线性分组码的检、纠错能力与H矩阵的关系;;;;;;例：某一个(5,2)系统线性码的生成矩阵是

设接收到码字是r=(10101)，先构造该码的标准阵列译码表，然后译出发码的估值C。;;;(5)标准阵列;【例】（7，3）线性分组码;如：（一个错）;例已知（7，3）码的校验矩阵为

;若错误图样en=（0010000），则;若错误图样en=（0010100），则;由定义可以求得，rn的伴随式：;一．基本概念;（1）H中列为非全零元素；;几个结论：对于具有纠单个错误能力的线性分组码。;;结论：为了得到具有纠一个错误的二元（n，n-m）线性码，（其中n-m=k，m为校验位的个数），只需从定义在F2上的m维非零列矢量中选取彼此不同的n个列矢量并依任意次序把它们排成一个m×n的矩阵：;如：;四.汉明码的编译码电路框图

编码器设计

例(7,4)汉明码;2.译码器设计;汉明码的译码电路框图;内容提要;1.循环码的定义;;2.码字的多??式描述;;多项式的模运算示例;如果A＝（an-1an-2…a1a0）是（n，k）循环码的一个码字，则A(1)＝（an-2…a1a0an-1）也是该循环码的一个码字。这就是说

A(x)＝an-1xn-1＋an-2xn-2＋…＋a1x＋a0

和A(1)(x)＝an-2xn-1＋…＋a1x2＋a0x＋an-1

都是（n，k）循环码的码字多项式。;循环多项式的模运算;例题：设循环码(7,4)中一个码字为，则该循环码的所有码字及其码多项式如表所示。;3.生成多项式和生成矩阵;由生成多项式g(x)容易得到生成矩阵。生成矩阵的每一行必定为线性无关的，且每行都是一个码字。g(x)为n-k阶多项式，则g(x),xg(x),x2g(x),…,xk-1g(x)必是线性无关的，将此对应的码字作为矩阵的每一行，得到生成矩阵。与生成矩阵对应的生成矩阵多项式G(x)可记作：;例题：已知循环码(7,4)的生成多项式g(x)有两种可能

x3+x+1或x3+x2+1，分别求其生成矩阵;例题：已知循环码(7,4)的生成多项式g(x)有两种可能

x3+x+1或x3+x2+1，分别求其生成矩阵;例题：如果循环码(7,4)的生成多项式g(x)=x3+x+1求对应的所有码字;16个码字构成4个循环组，前两组分别7个码字，后两组为自循环的单独码字。

可见，循环码并不是只由一个码字循环就可以得到全部码字。;将生成矩阵通过矩阵初等变换转换成[IkPk*r]的形式，即可得到系统生成矩阵。;解：可以先得到两个生成矩阵，后经过矩阵初等变换得到系统生成矩阵;通过比较，可以发现，对于生成矩阵G1及系统生成矩阵G1’,最后所生成的码字相同，

唯一不同的是消息位与码字的对应关系不同。;由生成多项式g(x)直接产生系统循环码;解:(1)消息码为[1101]，所以消息多项式为m(x)=x3+x2+1，则

xn-km(x)=x3m(x)=x6+x5+x3