《线性分组码编码的分析与实现》由会员分享，可在线阅读，更多相关《线性分组码编码的分析与实现（20页珍藏版）》请在金锄头文库上搜索。
1、吉林建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目：线性分组码编码的分析与实现专业班级：电子信息工程111学生姓名：学 号：指导教师：设计时间：201411242014125第 1 章 概述1.1 设计的作用、目的随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理 和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出 了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性， 成为现代数字通信系统设计的重要课题。目前，绝大多数的数字计算机和 数字通信系统中广泛采用二进制形式的码。而线性分组码具有编译码简 单，封闭性好等特点，采用差错控制编码技术是
2、提高数字通信可靠性的有 效方法，是目前较为流行的差错控制编码技术。 对线性分组码的讨论都 在有限域GF（2）上进行，域中元素为0,1,域中元素计算为模二加法和模 二乘法。分组码是一组固定长度的码组，可表示为（n , k）,通常它用于 前向纠错。在分组码中，监督位被加到信息位之后，形成新的码。在编码 时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检 错与纠错。对于长度为n的二进制线性分组码，它有种2n可能的码组， 从2n种码组中，可以选择M=2k个码组（kn）组成一种码。这样，一个 k 比特信息的线性分组码可以映射到一个长度为 n 码组上，该码组是从 M=2k 个码组构成的码集
3、中选出来的，这样剩下的码组就可以对这个分组 码进行检错或纠错。1.2 设计任务及要求设计一个（7, 3）线性分组码的编译码程序，完成对任意序列的编码，根据 生成矩阵形成监督矩阵，得到伴随式，并根据其进行译码，同时验证工作的正确 性，最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力。1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编 码过程4. 能够使用 MATLAB 或其他语言进行编程，编写的函数要有通用性。1.3 设计内容已知一个（7,3）线性
4、分组码的校验元与信息元有如下限定关系。设码字为（c7,c6,c5,c4,c3,c2,c1)c = c c413c=ccc5123c=cc612c=cc723求出标准校验矩阵、Q矩阵、标准生成矩阵，完成对任意信息序列Q3个许 用码字）的编码。，纠错并正确译码，当有两位错码时，假定为c5位和c2位发生错误。第 2 章 线性分组码编码的分析与实现2.1 设计原理1. 线性分组码的生成矩阵和校验矩阵（1）（n, k）线性分组码的性质1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于长度为n的二进制线性分组码，它有种2n可能的码组，从2n种码组中, 可以选择M=2k个
5、码组（kn则有可能构造出纠正一位或一位以上错误 的线性码。（2）生成矩阵和校验矩阵线性分组码码空间C是由k个线性无关的基底g ，g 1 g，张成的k维nk-11 0重子空间，码空间的所有元素(即码字)都可以写成k个基底的线性组合，即C = m g + mg + mgk 一1 k 一11 1 0 0这种线性组合特性正是线性分组码名称的来历。显然，研究线性分组的关键是研究基底、子空间和映射规则。用g表示第i个基底并写成1x n矩阵形式g = i个基底排列成k行n列的G矩阵，得：i (n 一1)，gi(n一2)，g ,g 再将ki1 i0g (k - 1 )ne1)gk 一 (igi k 一( 1)
6、 0, g1 , g0g 1 1 g 01gpLk10 0p (k - 1)(n - k - 1)p(k -1)1p (k - 1)001 0 p1(n-k-1)p11P10_000 1p0(n - k -1)p01P 00 一g1 n( 一 1 )g0 n( 一 1 )由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k，当信息元确 定后，码字仅由G矩阵决定，因此称这kxn矩阵G为该(nxk)线性分组码的生成 矩阵。基底不是唯一的，生成矩阵也就不是唯一的。事实上，将k个基底线性组合 后产生另一组k个矢量，只要满足线性无关的条件，依然可以作为基底张成一个 码空间。不同的基地有可能生成同一
7、个码集，但因编码涉及码集和映射两个因素， 码集一样而映射方法不同也不能说是同样的码。基底的线性组合等效于生成矩阵G的行运算，可以产生一组新的基底。利用 这点可使生成矩阵具有如下的“系统形式”：这里P是kx(n-k)矩阵；Z是k x k单位矩阵，从而保证了矩阵的秩是K。k与任何一个(n,k)分组线性码的码空间C相对应，一定存在一个对偶空间D。事实上，码空间基底数k只是n维n重空间全部n个基底的一部分，若能找出另 外n-k个基底，也就找到了对偶空间D。既然用k个基底能产生一个(n,k)分组 线性码，那么也就能用n-k个基底产生包含2 n-k个码字的(n,n-k)分组线性码, 称(n,n-k)码是(
8、n,k)码的对偶码。将D空间的n-k个基底排列起来可构成一个(n-k)xn矩阵，将这个矩阵称为码空间C的校验矩阵H ,而它正是(n,n-k)对偶 码的生成矩阵，它的每一行是对偶码的一个码字。C和D的对偶是互相的，G是 C的生成矩阵又是D的校验矩阵，而H是D的生成矩阵，又是C的校验矩阵。 由于C的基底和D的基底正交，空间C和空间D也正交，它们互为零空间。因 此，(n,k)线性码的任意码字c 一定正交于其对偶码的任意一个码字，也必定正交 于校验矩阵的H任意一个行矢量，即cHt= 0。由于生成矩阵的每个行矢量都是 一个码字，因此必有GHt = 0。对于生成矩阵符合“系统形式” G的系统码，其 校验矩
9、阵也是规则的，必为：H = L Pt I Jn-k上式中的负号在二进制码情况下可以省略，因为模 2 减法和模 2 加法是等同的。(3) 信息码元及对应码字的关系(n，k)码字中的任一码字c，均可以由这组基底的线性组合生成，即ic = m. G=m , m - m Gi in-1n-2n-k式中m =mmm 的是k个信息元组的信息组，因此其信息码元及in -1n - 2n - k对应码字的关系如表一所示：表一 信息码元及对应码字关系信息组码字000000000000100111010100100111011011101010010011101011010011110110100111111101
10、002. 线性分组码的伴随式与译码(1)码的距离及检错能力两个码字之间，对应位取之不同的个数，称为汉明距离，用d表示。一个码 的最小距离d 定义为d .= minid ,j丰j,c,cw (n,k,两个码字之间的距离minmin(ci , cj)i j表示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个 码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。任何最小距离d的线性分组码，其检错能力为(dmi-1)纠错能力t为min mindminm i n最小距离d表明码集中各码字差异的程度，差异越大越容易区分，抗干扰能力min自然越强，因此成了衡量分组码性能最重要
11、的指标之一。估算最小距离是纠错码 设计的必要步骤，最原始的方法是逐一计算两两码字间距离，找到其中最小者。含2个码字的码集需计算2 k(2 k -1)2个距离后才能找出d .，费时太多，实用中 / 2min还有一些更好更快的方法。线性分组码的最小距离等于码集中时非零码字的最小重量，即d = m i i（C ）mi niC e C及C丰0ii式中，符号w(c )表示c重量(1的个数)。这里利用了群的封闭性，由于分组ii码是群码，任意两码字之和仍是码字，即CjC=CeC。因此任意两码字间的 汉明距离其实必是另一码字的重量，表示为成下面公式形式。d(C ,C )= w(CC)= w(C )min(C
12、,CminwG )。于是可将最小距离问题i kj kij ki转化为寻找最轻码字问题，含2k个码字的码集仅需计算2k次。码的检错能力取决于码的最小距离，但还需说明的另一点是码的总体检错能力不仅仅与d有关。检错能力t只是说明距离t的差错一定能纠，并非说距离大 min于t的差错一定不能纠。事实上，如果有2k个码子，就存在2k (2k -1)/2个距离,这并非相等的。比如最小距离d .= 3，检错力t = 1，是由码CC的距离决定, min2 1只要C朝C方向偏差大于1就会出现译码差错；然而若C朝C方向偏差3,2123译码时仍可正确地判断为C而非C。可见，总体的、平均的纠错能力不但与最23 小距离有
13、关，而且与其余码距离或者说与码子的重量分布特性有关，把码距（码 重）的分布特性称为距离（重量）谱，其中最小的重量就是d 。正如信息论各 min 符号等概时熵最大一样，从概念上可以想象到 :当所有码距相等时是（重量谱为 线谱）码的性能应该最好；或者退一步说，当各码距相当不大时（重量谱为窄谱） 性能应该叫好。事实证明确实如此，在同样的d 条件下，窄谱的码一般比宽谱 min的码更优。纠错重量谱的研究具有理论与现实意义，不仅仅是计算各种译码差错 概率的主要依据，也是研究码的结构、改善码集内部关系从而发现新的好码的重 要工具。但目前除了少数几类码如汉明码、极长码等的重量分布已知外，还有很 多码的重量分布
14、并不知道，距离分布与性能之间确切的定量关系对于大部分码而 言尚在进一步研究当中，特别当n和k较大时，要得出码重分布是非常困难的。重量谱可以如下多项式来表示，称为重量算子，即A （x ）= A + Ax + Ax 2 + Ax 3+ Ax 什 A xn = Axn01234nii=1式中的含义：在码长n的码集里，包括重量为0的码子A个（线性码一定包含一 0个重量为0的全0码），码重为1的码字A个，重量为n的码字A个。1n（ 2）伴随式与译码码字C = （ c , c , c , C在传输过程中受到各种干扰，接收端收码n-12 1 0R = （r , r , r,）已不一定等于发码C，两者间的差异就是差错，差错是多样n-12 1 0化的，我们定义差错的式样为差错图样E，即E = (e ,n-1,e,e )=R-C =(r1 0n -1-cn-1,r - c ,r -c1 1 0 0对于二进制码，模2减等同模2加，因此有E
