线性分组码编码分析与实现讲解

1、吉林建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目：线性分组码编码的分析与实现专业班级：电子信息工程 111学生姓名： 学 号： 指导教师：设计时间：2014.11.24 2014.12.5教师评语：成绩评阅教师日期第 1 章 概述1.1 设计的作用、目的1、通过完成具体编码算法的程序设计和调试工作， 提高编程能力， 深刻理解 信源编码、信道编译码的基本思想。2、加深对理论知识的理解， 提高实践技能， 培养独立分析问题及解决问题的 能力。3、掌握编码的基本原理与编码过程，增强逻辑思维能力。4、使用 MATLABH 或其他语言进行编程及实现。1.2 设计任务及要求设计一个( 7

2、,3)线性分组码的编译码程序，完成对任意序列的编码，根据 生成矩阵形成监督矩阵， 得到伴随式下， 并根据其进行译码， 同时验证工作的正 确性，最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力。1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2. 掌握哈夫曼编码 /费诺编码方法的基本步骤及优缺点；3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编 码过程4. 能够使用 MATLAB 或其他语言进行编程，编写的函数要有通用性。1.3 设计内容已知一个(7,3)线性分组码的校验元与信息元有如下限定关系。 设码字为 (c1,c2, c3, c4, c5,

3、 c6,c7)c4 c1 c3c5 c1 c2 c3c6 c1 c2c7 c2 c3求出标准校验矩阵、 Q 矩阵、标准生成矩阵，完成对任意信息序列( 23 个 许用码字)的编码。当接收码字分别为 (0000000), (0000001), (0000010), (0000100), (0001000), (0010000), (0100000), (1000000), (0100100时) ，写出其伴随式 S，以表格形式写出 伴随式与错误图样 E 的对应关系，纠错并正确译码，当有两位错码时，假定为 c5 位和 c2 位发生错误。第 2 章 线性分组码编码分析与实现2.1 设计原理1. 线性分组

4、码的生成矩阵和校验矩阵（1）（n，k）线性分组码的性质1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于长度为 n 的二进制线性分组码， 它有种 2n可能的码组，从 2n种码组中， 可以选择 M=2k个码组（ k<n）组成一种码。这样，一个 k 比特信息的线性分组 码可以映射到一个长度为 n 码组上，该码组是从 M=2 k个码组构成的码集中选出 来的，这样剩下的码组就可以对这个分组码进行检错或纠错。对于码组长度为 n、信息码元为 k 位、监督码元为 r nk 位的分组码，常 记作（ n，k）码，如果满足 2r 1n，则有可能构造出纠正一位或一位以上错误

5、 的线性码。（2）生成矩阵和校验矩阵线性分组码码空间 C是由k个线性无关的基底 gk 1，g1g0，张成的k维n 重子空间，码空间的所有元素 （即码字）都可以写成 k 个基底的线性组合，即C mk 1 gk 1m1 1g m0 g这种线性组合特性正是线性分组码名称的来历。 显然，研究线性分组的关键是研 究基底、子空间和映射规则，可把子空间和映射关系画成如图一所示的图形。图 2.1 码空间与映射用gi 表示第 i 个基底并写成 1 n矩阵形式 gi gi(n 1),gi(n 2), ,gi1,gi0 再将 k个基底排列成 k行 n列的 G 矩阵，得：由于k个基底即 G的k个行矢量线性无关，矩阵G

6、 的秩一定等于 k ，当信息元确g(k 1)(n 1)g(k 1)1g(k 1)0gk 1, ,g1,g0g1(n 1)g11g10g0(n 1)g01g00G定后，码字仅由 G 矩阵决定，因此称这 k n矩阵 G 为该 n k 线性分组码的生成 矩阵。基底不是唯一的，生成矩阵也就不是唯一的。事实上，将 k 个基底线性组合 后产生另一组 k 个矢量，只要满足线性无关的条件，依然可以作为基底张成一个 码空间。不同的基地有可能生成同一个码集， 但因编码涉及码集和映射两个因素， 码集一样而映射方法不同也不能说是同样的码。基底的线性组合等效于生成矩阵 G 的行运算，可以产生一组新的基底。 利用 这点可

7、使生成矩阵具有如下的 “系统形式 ”：100p(k 1)(n k 1)p(k 1)1p(k 1)0GIk P 010p1(n k 1)p11p100001p0(n k 1)p01p00这里 P是k n k 矩阵； Ik是k k单位矩阵，从而保证了矩阵的秩是 K与任何一个 n,k 分组线性码的码空间 C 相对应，一定存在一个对偶空间 D 。 事实上，码空间基底数 k只是 n维 n重空间全部 n个基底的一部分，若能找出另 外n k 个基底，也就找到了对偶空间 D。既然用 k个基底能产生一个 n,k 分组 线性码，那么也就能用 n k 个基底产生包含 2 个码字的 n,n k 分组线性码， 称 n,

8、n k 码是 n,k 码的对偶码。将 D空间的 n k 个基底排列起来可构成一个 n k n矩阵，将这个矩阵称为码空间 C的校验矩阵 H ，而它正是 n,n k 对偶 码的生成矩阵， 它的每一行是对偶码的一个码字。 C和D 的对偶是互相的， G是 C 的生成矩阵又是 D 的校验矩阵，而 H 是 D 的生成矩阵，又是 C 的校验矩阵。由于 C 的基底和 D的基底正交，空间 C 和空间 D 也正交，它们互为零空间。因 此， n,k 线性码的任意码字 c 一定正交于其对偶码的任意一个码字， 也必定正交 于校验矩阵 H 的任意一个行矢量，即 cHT 0 。由于生成矩阵的每个行矢量都是 一个码字，因此必

9、有 GHT 0。对于生成矩阵符合 “系统形式 ”G 的系统码，其校 验矩阵也是规则的，必为：HPT In k上式中的负号在二进制码情况下可以省略，因为模 2 减法和模 2 加法是等同的。（3）信息码元及对应码字的关系 （n，k）码字中的任一码字 ci ，均可以由这组基底的线性组合生成，即ci mi G mn 1 mn 2mn k G式中 mi mn 1 mn 2mn k 的是 k 个信息元组的信息组，因此其信息码元及对应码字的关系如表一所示：表 2.1 信息码元及对应码字关系信息组码字0000000000001001110101001001110110111010100100111010110

10、10011110110100111111101002. 线性分组码的伴随式与译码（1）码的距离及检错能力 两个码字之间，对应位取之不同的个数，称为汉明距离，用 d 表示。一个码的最小距离 dmin 定义为 dmin min d（ci,cj）,j j,ci,cj （n,k） ,两个码字之间的距离 表示了它们之间差别的大小。 距离越大， 两个码字的差别越大， 则传送时从一个 码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。任何最小距离 dmin的线性分组码，其检错能力为 dmin 1 纠错能力 t为d mi n1t I NT min2最小距离 dmin 表明码集中各码字差异的程度

11、，差异越大越容易区分，抗干扰能力 自然越强， 因此成了衡量分组码性能最重要的指标之一。 估算最小距离是纠错码 设计的必要步骤，最原始的方法是逐一计算两两码字间距离，找到其中最小者。 含2k个码字的码集需计算 2 2 12 个距离后才能找出 dmin ，费时太多，实用中 还有一些更好更快的方法。线性分组码的最小距离等于码集中时非零码字的最小重量，即dm i n m i nw CiCi C及 Ci 0式中，符号 w ci 表示 ci 重量（1 的个数）。这里利用了群的封闭性，由于分组 码是群码， 任意两码字之和仍是码字， 即Cj Ck Ci C 。因此任意两码字间的 汉明距离其实必是另一码字的重量

12、，表示为成下面公式形式。d Ci,Ck wCj Ck wCi ,mind Cj,Ck min wCi 。于是可将最小距离问题 转化为寻找最轻码字问题，含 2k 个码字的码集仅需计算 2k次。码的检错能力取决于码的最小距离， 但还需说明的另一点是码的总体检错能 力不仅仅与 dmin有关。检错能力t只是说明距离 t的差错一定能纠，并非说距离大 于t的差错一定不能纠。 事实上，如果有 2k个码子，就存在 2k 2k 1 2 个距离， 这并非相等的。比如最小距离 dmin 3 ，检错力 t 1 ，是由码 C2C1 的距离决定， 只要 C2 朝C1 方向偏差大于 1 就会出现译码差错；然而若 C2朝 C

13、3方向偏差 3， 译码时仍可正确地判断为 C2而非 C3 。可见，总体的、平均的纠错能力不但与最 小距离有关， 而且与其余码距离或者说与码子的重量分布特性有关， 把码距（码 重）的分布特性称为距离（重量）谱，其中最小的重量就是 dmin 。正如信息论各 符号等概时熵最大一样，从概念上可以想象到 :当所有码距相等时是（重量谱为 线谱）码的性能应该最好；或者退一步说，当各码距相当不大时 （重量谱为窄谱） 性能应该叫好。事实证明确实如此，在同样的 dmin 条件下，窄谱的码一般比宽谱 的码更优。 纠错重量谱的研究具有理论与现实意义， 不仅仅是计算各种译码差错 概率的主要依据， 也是研究码的结构、 改

14、善码集内部关系从而发现新的好码的重 要工具。 但目前除了少数几类码如汉明码、 极长码等的重量分布已知外， 还有很 多码的重量分布并不知道， 距离分布与性能之间确切的定量关系对于大部分码而 言尚在进一步研究当中， 特别当 n 和 k 较大时，要得出码重分布是非常困难的。重量谱可以如下多项式来表示，称为重量算子，即nA x A0 A 1x A x22 Ax33 A x 44 AnxnAi xni1 式中的含义：在码长n的码集里，包括重量为 0的码子 A0个（线性码一定包含一 个重量为 0 的全 0 码），码重为 1 的码字 A1 个， ，重量为 n 的码字 An 个。（2）伴随式与译码码字 C c

15、n1, ,c2,c1,c0 在传输过程中受到各种干扰，接收端收码 R rn1, ,r2, r1 , r0已不一定等于发码 C ，两者间的差异就是差错，差错是多样 化的，我们定义差错的式样为差错图样 E,即E en 1, ,e1,e0 R C rn 1 cn 1, ,r1 c1,r0 c0 对于二进制码，模 2 减等同模 2 加，因此有E R C及 R C E mo d 2 利用码字与校验矩阵的正交性 CHT ，可检验收码 R是否错误 ,即T T TTTT 0RHTC E HTCTHETH0ET HTEH0定义 RHT 运算结果为伴随式 S,即S sn k 1, ,s1,s0 RHT EH T可

16、见，虽然 R本身与发码有关， 但乘以 H T后的伴随式 RHT S EH T 仅与差错 图 E 有关，只反映信道对码字造成怎样的干扰而与发什么码 C 无关了。于是可以 先利用收码 R和已知的 H算出的伴随式 S；再利用 S算出差错图样 E 。这种思路 下的编译码过程如图所示。在此过程中， RHT和R E 的计算都是确定性的，而 从 S计算 E却带有随机性。这是因为伴随式 S 是一个重失量，二进制时只有种肯 那个的组合，而差错图样 E是n重失量，有种可能的组合，因此 S与 E不存在一 一对应关系。假设接收端收到的码字为 B ，那么它和原来发送端发送的码字 A之间就有可 能存在着误差。即在码组 A

17、 a6 a5 a4 a3 a2 a1 a0 中的任意一位就有可 能出错。这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要 表达的意思。为了描述数据在传输信道中出现错误的情况，引入了错误图样 E ， 在错误图样中， 0 代表对应位没有传错， 1 代表传输错误。实际上错误图样 E 就 是收序列与发送序列的差。 所以在译码中用接收到的码字 B 模尔加错误图样 E就 可以得到发送端的正确码字 A 。因此译码的过程就是要找到错误图样 E。定义：校正子SS B* HAT E * H TA* HT E* HT E*HT因为 A是编得的正确码字。 根据前面所叙述，它和监督矩阵的转置相乘为 0。

18、显然， S仅与错误图样有关，它们之间是一一对应的关系。找到了校正子S ，也就可以找到 E 。而与发送的码字无关。若 E 0，则S 0 ；因此根据 S是否为 0 可进行码字的检错。如果接收码字 B中只有一位码元发生错误，又设错误在第i位。即 Ei 1 1,其他的 Ei均为 0。在后面的译码程序中，建立了一个校正子 S与错误图样 E对应 的表。也就是收到一个 B 序列，就可以通过计算得到一个校正子， 而每一个校正 子都对应着一个错误图样 E ，再通过 B 模尔加上 E ，就可以得到正确的码字 A。因为在不同的错误序列 B 中，同一位码元错误时对应的 E是一样的，所以可 以利用 0000000 这个

19、正确的码字让它每位依次错误， 来求得它的八个校正子。 而 这时的矩阵 B就是错误图样 E 。2.2 设计步骤1. 编码过程根据已知检验元与信息的关系，设码字为 (c1,c2, c3, c4, c5, c6,c7) c4 c1 c3 c5 c1 c2 c3 c6 c1 c2 c7 c2 c3在由监督矩阵和生成矩阵的关系如下：由H与G的分块的矩阵形式 H Q Ink ，G Ik P ,P QT 。可以求出生成矩阵 G和监督矩阵 H 。1001110G 0 1 0 0 1 1 100111011101111001H110000110000001001有了生成矩阵后可以根据输入的四位信息位和生成矩阵相

20、乘得到编码矩阵，即 MATLAB 函数为：C rem I G,2其中为编码后的结果，为信息矩阵，为生成矩阵。则编码所有情况为： 编码序列：信息位 |监督位0000000001110101001110100111C10011101010010110100111101002. 译码过程 对于译码过程来说，由上面可知道监督矩阵： 1011000 1110100H11000100110001H矩阵与 n,k 码的任何一个许用码字进行相乘的结果必等于 0，即若C m G是 任一 n,k 码字，则必有 C H T 0。若不属于许用码字，或有传输差错，且差错位数在 n,k 码纠错能力内，则运算结果将为非 0

21、 值，此时，可以纠错或检错重 发。设接收的码字 （c1,c2,c3,c4,c5,c6,c7），c1为第七位， c7 为第一位，则：（1）当接收码字为（ 0000000）时：101 伴随式 S0 R H T 0000000 100010100001100010000所以此时接收编码无错误。2）当接收码字为（ 0000001）时：伴随式 S1 R H T1010000001 100001100010001000000）。所以，此时接收编码第一位发生错误，纠错后的正确译码为3）当接收码字为（ 0000010）时：111001111101R H T 00000101000001001000010000

22、1伴随式 S2所以，此时接收编码第二位发生错误，纠错后的正确译码为（ 000000）4）当接收码字为（ 0000100）时：0110 0100001111011110 伴随式 S3 R H T 0000100 1 0 0010001000所以，此时接收编码第三位发生错误，纠错后的正确译码为（ 000000）5）当接收码字为（ 0001000）时：0110 1000001111011110 伴随式 S4 R H T 0001000 1 0 001000100010所以，此时接收编码第四位发生错误，纠错后的正确译码为（ 000000）111001111101伴随式 S5 R H T 0010000

23、10000100001000016）当接收码字为（ 0010000）时：所以，此时接收编码第五位发生错误，纠错后的正确译码为（1101000000）。7）当接收码字为（ 0100000）时：111001111101伴随式 S6 R H T 0100000 1 0 0 0 01000010 0001所以，此时接收编码第六位发生错误，纠错后的正确译码为（8）当接收码字为（ 0100100）时：111001111101伴随式 S7 R H T 0100100 1 0 0 0 0100001000010111000000）。110011所以，此时接收编码 c5 位和 c2位发生错误，纠错后的正确译码（

24、 0000000）当编码矩阵与生成矩阵的转置矩阵相乘时， 若当其中的一位编码或两位出现 差错时会有八种情况，则这些情况列出错码矩阵如下表二：表 2.2 伴随式 S 与错误图样 E 的对应关系校正子 S差错图样 E00000000000000100000010010000001001000000100100000010001101001000001110100000111010000000011010010012第 3 章 仿真程序及结果分析3.1 仿真程序% H 监督矩阵% G 生成矩阵% C 编码矩阵% I 输入信息序列% B 信道输出码% A 纠错输出码序列% E 错码矩阵% S 校验子矩

25、阵% M 校验子的行的十进制序列%信道编码程序clear allclose allH=1 0 1 1 0 0 0;1 1 1 0 1 0 0;1 1 0 0 0 1 0;0 1 1 0 0 0 1; G=gen2par(H);%监督矩阵 H%求 H 阵的生成矩阵 GI=0 0 0;0 0 1;0 1 0;0 1 1;1 0 0;1 0 1;1 1 0;1 1 1; C=rem(I*G,2); disp('所得的编码结果为 :C=');%求码字 C%显示输出码字 Cdisp(C);%信道译码程序clear all;close all;H=1 0 1 1 0 0 0;1 1 1 0

26、 1 0 0;1 1 0 0 0 1 0;0 1 1 0 0 0 1;B=input('请输入接收码组 a,b=size(B);%监督矩阵 H%返回数组 R 的维数E=0 0 0 0 0 0 0;0 0 0 0 0 0 1;0 0 0 0 0 1 0;0 0 0 0 1 0 0;0 0 0 1 0 0 0; 0 0 1 0 0 0 0;0 1 0 0 0 0 0;0 1 0 0 1 0 0;13S=rem(B*H',2);%求校验子 Si=1;for i=1:1:a%求校验子所表示的十进制整数M(i,1)=S(i,1).*8+S(i,2).*4+S(i,3).*2+S(i,4)

27、; endfor i=1:1:aswitch(M(i,1)case 0 A(i,:)=B(i,:)+E(1,:); case 1A(i,:)=B(i,:)+E(2,:); case 2A(i,:)=B(i,:)+E(3,:); case 4A(i,:)=B(i,:)+E(4,:); case 8A(i,:)=B(i,:)+E(5,:); case 13A(i,:)=B(i,:)+E(6,:); case 7A(i,:)=B(i,:)+E(7,:); case 14A(i,:)=B(i,:)+E(8,:);endend for i=1:1:a switch(M(i,1) case 0case 1

28、 disp（'注意：第 1 位出现一个错误！请纠正！ '）;case 2disp（'注意：第 2 位出现一个错误！请纠正！ '）; case 414 disp（'注意：第 3 位出现一个错误！请纠正！ '）; case 8disp（'注意：第 4 位出现一个错误！请纠正！ '）; case 13disp（'注意：第 5 位出现一个错误！请纠正！ '）; case 7disp（'注意：第 6 位出现一个错误！请纠正！ '）; case 14disp（'注意： c2 位和 c5 位出现两个错误！

29、请纠正！ '）; endendA=rem（A,2）;%求出正确的编码disp（'检纠错后的码组 A='）;disp（A）;%显示正确的编码j=1;while j<=3%提取信息位I（:,j）=A（:,j）;j=j+1;enddisp（'译出的信息序列 I='）;disp（I）;153.2 仿真结果1) 输出编码结果和无错误输入时显示图图 3.1 没有出现错误是的仿真图2) 有一位错误输入时显示图 :图 3.2 第 4 位出现错误时的仿真图16图 3.3 第 3 位出现错误时的仿真图3）有两位错误输入时显示图 :图 3.4 出现两位错误时的仿真图17

30、3.3结果分析1输出编码结果及输入正确接收码的译码结果分析 由图可以看出编码的结果的八种情况和在推导过程中运算的结果是一致的， 所以我们可以知道程序的编码过程是正确的。 对于译码过程而言，当界面显示“请 输入接收码组 B：”，然后从提示符后输入： 0 0 0 0 0 0 0，由于输入的接收码组 与编码后的码字一致，它提取了每个码组的前四位，即信息位，由结果看出译码 过程是正确的，并没有出现错译的情况，可见程序的译码片段是正确的。 2输入一位错误时的结果分析由图可以看出，当界面显示“请输入接收码组 B：” 。然后从提示符后输入： 1 0 1 0 0 0，由图有一位错误输入时的显示图所知， 接收码

31、组的第五位发生了错 误，经程序纠检错误后改正了接收序列的错误， 并且正确译出了信息位。可见程 序的纠错功能也是可以实现的，以上结果进一步证实了，系统译码程序的正确性。 3输入两位特定位错误时的结果分析由图有两位特定位错误输入时的显示图知，当输入 B=0 1 0 0 1 0 0 时，校 正子是 0011，错误图样是 0100100，所以说明理论得以验证。18第 4 章 总结 通过这次的课程设计，我学习到了很多东西，让我对线性编码有了一个全 新的认识，对 MATLAB 的掌握也进步了解很多，为以后的学习中出现的可能问 题做好了准备， 锻炼了自己的动手能力和设计能力， 掌握了一种科技工具， 丰富 了自己的学习生活。 整个实验过程中我懂得了许多东西， 在查找的过程中我们也 知道了许多原来不知道的东西， 对于源代码的修改以及成功利用也树立了对知识 应用的信心， 相信会对今后的学习工作和生活有非常大的帮助， 并且提高了自己 的动手实践操作能力，使自己充分体会到了在实验过程中的成功喜悦。让我对 MATLAB 软件有了更深的了解，对 MATLAB 语言也有了更加深入 的学习和理解。在本次的设计中，我了解了 MATLAB 中很多函数的用法，提高 了我编程的能力， 在软件仿真上， 提高了自己的动手能力和学习能力， 为以后的 学习打