本科生毕业论文(设计)-信道编码的研究与实现

1、本科生毕业论文本科生毕业论文信道编码的研究与实现Disquisition and realization of channel coding学生姓名所在专业所在班级申请学位指导教师职称副指导教师职称答辩时间年 月 日目 录目目 录录摘 要 .IABSTRACT .II1引言.12信道编码理论.22.1信道编码概述.22.1.1错误概率与译码规则.42.1.2错误概率与编码方法.42.2分组码.52.2.1奇偶校验码.52.2.2行列检验码.52.2.3群计数法.52.2.4恒比码.52.3线性分组码.62.3.1汉明距离.62.3.2生成矩阵和校验矩阵.72.3.3纠错能力.92.4循环码.9

2、2.4.1码多项式.92.4.2多项式的基本性质.102.4.3循环码的生成矩阵和一致校验矩阵.112.5.NET.Framework 介绍.132.6C#语言.142.7Visual Studio 2005 概述.153编译码.163.1行列校验码.163.1.1C#语言实现行列校验码.163.2群计数法.213.2.1C#语言实现群计数法.223.3线性分组码.253.3.1C#语言实现线性分组码.253.3.2线性分组码的纠正译码.304软件的应用.305性能比较.315.1编码效率.32目 录5.2检/纠错能力.336结束语.33鸣 谢.35参考文献.36附 录.37摘 要I摘 要信息

3、传输系统的基本功能是：在系统输出端准确地再现系统输入端发送的信息。我们希望信息传输多快好省，但现实与我们的良好愿望之间总是存在差距1。客观规律是不可违背的，首先，信息传输的速度受信道容量的限制，不可能无限大；其次，由于信道噪声的干扰，传输错误不可避免，我们只能采用信道编码将传输错误控制在允许范围之内。为了降低平均差错率，可以先对消息进行编码再送入信道传送，这种为降低平均差错率而进行的编码称为信道编码。信道编码主要分为两大类：检验码、纠错码。检验码只检查信息在传输过程中是否有差错，而纠错码不但检查是否有差错，而且还可以将错误的信息纠正。本研究首先介绍什么是信道编码、信道编码的意义及国内外的发展水

4、平，并对信道编码分类，接着介绍信道编码的基本理论，对行列分组码、群计数法、线性分组码的性质及其编译原理进行详细的说明。介绍了 C#编程语言及其平台 visual studio 2005。之后用 C#语言在 visual studio 2005 平台下对行列分组码、群计数法、线性分组码进行可视化编程，针对线性分组码部分进行随机出错，并实现纠正译码。最后利用生成的软件对行列分组码、群计数法、线性分组码进行性能的比较。关键词：信道编码；线性分线码；C#语言ABSTRACTIIABSTRACTThe basic function of information transmission system i

5、s the output point accurately recur the information in input point. We hope the information transmit as fast as we wish, but actually we cant make it. First, the channel of transmission limit the transmit speed. Second, because of noise disturb, the information will change not as we hope. So we must

6、 use channel coding to control the error. To reduce the error, we can code the information before transmit. This method we call channel coding. Channel coding is classified checking-code and error-correcting-code. The first just checks the code, the last one not only checks the code, but also correc

7、ts the code.This thesis discusses channel coding, the meaning of channel and the development of channel coding. Then classifies channel coding and introduces theory of channel coding. Particularly, explains rang block coding, counting coding and liner block coding. Second introduces C# language and

8、the platform (visual studio 2005), then makes uses of them to programs channel coding. With the liner block coding portion, checks errors and corrects the errors. At last, makes uses of the software to compares their performent.KEYWORDS: channel coding; liner block coding; C# language 1 信道编码的研究与实现1

9、引言目前，中国固定和移动两大网络的规模都已位居世界第 2 位，上网用户 2004 年总数达 9400 万，中国的信息通信制造业也得到很大的发展。今后 5 年中国信息产业预计将仍会民高于 20%的速度增长。1中国将加快建设新一代信息通信网络技术、生产体系。在信息通信网络的高速发展下，要有效地提高传输速度，然而由于信道噪声的干扰，传输错误不可避免，我们只能采用信道编码将传输错误控制在允许范围之内。信道是指通信系统把载荷消息的信号从甲地传输到地的媒介2。在狭义的通信系统中实际信道有明线、电缆、波导、光纤、无线电波传输空间等，这些都是属于传输电磁波能量的信道。当然，对广大的通信系统来说，信道还可以是其

10、他传输媒介。信道编码的目的主要有两点：(1) 要求码列的频谱特性适应通道频谱特性，从而使传输过程中能量损失最小，提高信号 能量与噪声能量的比例，减小发生差错的可能性，提高传输效率。一般传输通道的频率特性总是有限的，即有上、下限频率，超过此界限就不能进行有效的传输。如果数字信号流的频率特性与传输通道的频率特性很不相同，那么信号中的很多能量就 会失去，信噪比就会降低，使误码增加，而且还会给邻近信道带来很强的干扰。因此，在传输前要对数字信号进行某种处理，减少数字信号中的低频分量和高频分量，使能量向中频集中，或者通过某种调制过程进行频谱的搬移。这两种处理都可以被看作是使信号的频谱特性与信道的频谱特性相

11、匹配。 (2) 增加检验能力。 信道编码的意义在于降低各类数字通信系统以及计算机存贮和运算系统中的误码率，提高通信质量，延长计算机无故障运行时间等3。国外 50 年代至 60 年代初，主要研究各种有效的编、译码方法，奠定了纯属分组码的理论基础，包括奇偶校验码、行校验码、恒比码、群计数法。这些码只能检错而不能纠错。60 年代至 70 年代初，提出了许多有效的编译码方法，并注重实用化，由霍昆格姆（Hocquenghem） ，博斯（Bose）和雷查德胡里（Ray-Chaudhuri）分别提出了纠正多个随机错误的循环码BCH 码的构造方法。BCH 码是迄今为止所发现的一类很好的线性纠错码类，它纠错能力

12、强，特别在短和中等码长下，其性能很接近于理论值，并且构造方便，编码简单。后来彼德逊（peterson）从理论上解决了二进制的译码得法，奠定了 BCH 码译码的理论基础，稍后格林期坦（Gorensten）和刘勒尔（Zierler）把它推广到多进制。1966 年伯利坎普（Berlekamp）利用迭代算法译BCH。70 年代至 80 年代，理论上心戈帕为首的学者构造了一类 Goppa 码，其中一类子 2 码通达到香农在信道编码定理中所提出的码香农码。从而使信道编码在各类通信系统中的广泛使用，起到了极好的推动作用，并提出构造了一系列广义码，如交替码、GBCH 码等。自 80 年代初以来，利用代数曲线构

13、造了一类代数几何码。由于代数几何码是一类范围非常产的码，在理论上已证明它具有优越的性能，所以代数几何码的研究方兴未艾。卷积码由爱里斯(Elias)它与以前的分组码不相同，卷积码在编码过程中，充分利用了各组之间的相关性，在译码过程中，不仅从此时刻收到的码组中提取译码信息，而且还要利用以前或以后各时刻收到的码组中提取有关信息4。现在通信系统所用的信道编码都基本上达到香农理论、纠错能力强，但一般都编码复杂，要用高性能的设备进行高速编码。本研究目标：码长尽量短，信息率尽量高，纠检能力尽量大，编码规律尽量简单，实现设备简单易实现且费用合理，与信道的差错统计特性尽量匹配。本主要研究内容：掌握常用信道编码内

14、容、选择其中两种进行编程实现、并进行性能比较。本文首先介绍信道编码的理论，包括不同的编码，接着介绍 C#评议以及 visual studio 2005.在介绍完后，利用 visual studio 2005 平台用 C#语言编写行列校验码、群计数法和线性分组码，生成可执行文件。最后利用软件比较不同编码的性能。2 信道编码理论2.1信道编码概述信息传输系统的基本功能是：在系统输出端准确地再现系统输入端发送的信息。而实际的通信信道往往都是有噪信道，其差错率与信道的统计特性有关，不可能为零，有时甚至很大。为了降低平均差错率，可先对消息进行编码再送入信道传送，这种为降低平均差错率而进行的编码称为信道编

15、码。信道编码的意义：由于实际信道存在噪声和干扰，使发送的码字与信道传输后所接收的码字之间存在差异，称这种差异为差错5。信道编码的目的是为了改善通信系统的传输质量。图 2-1:信道编码的基本原理可见，用纠（检）错控制差错的方法来提高通信系统的可靠性是以牺牲有效性的代价来换取的。信息码元 k 监督码元 r纠正发现规则 3 香农理论为通信差错控制奠定了理论基础。香农的信道编码定理指出：对于一个给定的有干扰信道，如信道容量为C，只要发送端以低于C的速率R发送信息(R为编码器输入的二元码元速率)，则一定存在一种编码方法，使编码错误概率p随着码长n的增加，按指数下降到任意小的值。这就是说，可以通过编码使通

16、信过程实际上不发生错误，或者使错误控制在允许的数值之下。信道编码的分类：纠错编码的目的是引入冗余度，即在传输的信息码元后增加一些多余的码元（称为校验元，也叫监督元） ，以使受损或出错的信息仍能在接收端恢复。图 2-2:信道编码的分类差错控制编码属于信道编码，差错控制的目的是用信道编码的方法检测和纠正误码，降低误比特率。差错控制有：(1) 前向纠错法（FEC）发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。优点:单向传输，实时性好缺点:译码设备较复杂。 (2) 自动请求重发（ARQ）由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果

17、反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。优点:是译码设备简单，对突发错误和信道干扰较严重时有效，可达到良好的性能。缺点:需要双向信道，实时性差(3) 混合纠错（HEC）发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力， 但码组的功能检错码和纠错码监督码与信息码元之间的关系线性码和非线性码（监督码元与信息码元之间的关系是线性关系）信息码元处理方法分组码： n=k+r信息码元k监督码元r监督码元仅监督本码组中的信息码元卷积码：循环码和非循环码码元取值二元码与多元码 4 能检

18、测出来，则经过反馈信道请求发端重发。具有自动纠错和检错重发的优点，可达到较低的误码率2.1.1 错误概率与译码规则在有噪信道中传输消息是会发生错误的。为了减少错误，提高可靠性，首先就要分析错误概率与哪些因素有关。错误概率与信道统计特性有关。信道的统计特性可由信道貌岸然的转移矩阵来描述。当确定了输入和输出对应关系后，也就确定了信道矩阵中哪些是正确转移概率，哪些是错误转移概率。也就是译码对错误概率有影响7。信源共有 M 个消息，假设已用 M 个码元 X1，XK，XM对它进行了最佳编码。信源通过信源编码器编码后发送码元 Xk，其发送概率为 q（Xk） ，通过信道转移慨率为P(Y|Xk)的信道传输，接

19、收到码元 Y，信道译码器输出，而是对 Y 的一个估值，kXkX通信过程可用图 2-3 所示框图表示。图 2-3:信息传输系统 约定时，认为误码，则发送 Xk收到 Y 估错的概率为：kkXX)Y|p(Xk1Y)|p(XiY)|XXp()(XpkIkkkc通信总希望错误概率最小，由式可看出 Pc(Xk)最小等同于后验概率 P(Xk |Y)最大，这就是最大后验概率准则。，若 Y 已收到，则 P(Y) =1，所以，p(Y)q(XX|p(YY)|p(XiiiP(Xk |Y)最大等同于 P(Y|Xk)q(Xk)最大。在输入码元先验概率 q（X）相等的条件下就等同于 P(Y|Xk)最大，这就是最大似然译码准

20、则，P(Y|Xk)也称似然函数。最大后验概率这种译码方法在一般情况下棋先求解后验概率或联合概率，这样做比较麻烦。而最大似然概率译码方法不依赖于先给概率8。2.1.2 错误概率与编码方法 选择最佳译码规则只能使错误概率 Pe 任意地小。要想进一减少错误概率 Pe，必须选信道编码方法。增加“重复”次数 N（增大码长） ，会使 Pe 下降，但R也跟着下降。增多消息个数 M 会提高 R，但会使 Pe 增大。增大码长 N，同时适当增多消息个数 M，有可能使平均差错率降低到要求的范围以内，而又能使信息率不降低或降低不多。信源信道编码器Xk信道Y信道译码器信宿kX干扰 5 2.2分组码分组码是前向纠错码，它

21、可以在无需重新发送的情况下检测出有限个错码，并加以纠正。在分组码编码器中，K 个信息比特被编成 N 个比特，从而对 K 个信息比特增加了 N-K 个冗余比特，而冗余比特的作用是检测和纠正错码。分组码也称为（N，K）码，其码速率定义为 Rc=K/N。2.2.1 奇偶校验码这是最基本的检错码。它的编码规则是在信息码后附加一个监督码元，使得码组中“1”或“0”的个数为奇数（奇校验）或偶数（偶校验） 。奇偶校验码组共有个 n 码元，其中信息元有 n-1 个。当传输过程中奇数个码元发生错误时，奇偶校验可以检测出；偶数个码元发生错误时，无法检测。2.2.2 行列检验码行列检验码是二维奇偶校验码，又称为矩阵

22、码。这种码克服了奇偶校验码不能了现偶数个差错的缺点。其编码方法是将若干要传送的信息码元编成一个矩阵，矩阵的每一行为一个码组进行奇偶校验。矩阵中的每一列由不同码组系统位置的码无组成，每列都进行奇偶校验。这样每一行，每一列均构成一个奇偶校验码。当某一行（列）出现偶数个差错时，该行（列）虽然不能发现，但只要差错所在的列（行）没有同时出现偶数个差错，该差错仍然可以被发现。只有当差错数正好为 4 的倍数，而且差错位置刚好构成矩阵的 4 个角时，行列校验码才无法进行了差错检验。行列校验码是发现错码能力较强的检测突发的简单编码。2.2.3 群计数法群计数器法首先将信息码分组，而后计算每一组中“1”码的个数，

23、并用二进制数表示。此二进制作为校验元附在信息元后传输。如 101101 共有 4 个 1，用 100 表示，则传输的码组为 1011011100。这种编码方法可以发现大量的错误图样，有很高的检错能力，但群计数法的编码效率较低。2.2.4 恒比码 恒比码又称为定比码、定 1 码、等比码等。在恒比码中，每个码组 1 和 0 的数目都保持固定的比例。在接收端检测时，只要计算接收的码组中 1 的个数是否正确就知道有无错误。除去“1”错成“0”正好等于“0”错成“1”的误码外，恒比码还可以 6 检测出所有其他的错误模式。恒比码的主要优点是简单，且适用于传输电传机或其他键盘设备产生的状态有限的字母和符号，

24、但不适用于传输信源来的随机二进制数字序列。2.3线性分组码检错码在发现差错后必须通过要求对方重发一遍来获得正确的信息，在实时信息采集系统中可能是有困难的（信息源已经发生变化） 。就是在发方保留有原信息样本的情况下，也只有在差错率很低的条件下是比较可行的。如果通信条件比较恶劣，差错出现频繁，以至多次重发仍然得不到一份正确的信息。在这种情况下，只采用“检错”手段就显得无能为力了。这时就要采用“纠错码” ，它不但能发现差错，而且能将差错自动纠正过来，避免频繁重发所消耗的时间，从而大大提高了通讯的可靠性6。线性分组码是分组码的一个子类，由于线性码的编码和译码容易实现，至今仍是应用最广泛的一类码。一个n

25、,k线性分组码，是把从信源输出的以 k 个码元为一组的信息组m，通过信道编码器后，变成长度为 nk 的码组（码字）c 作为n,k线性分组码的一个码字。设 GF(q)是一个含有 q 个元素的有限数域，若每位码元的取值有 q 种（取自 GF(q)），则信息组m共有 qk种不同的状态，因此，需要 qk个码字 c。而长为n的数组共有 qn个，二进制时(q=2)共有n2个。显然，qn个 n 维向量组成有限域 GF(q)上的一个n维线性空间 V，编码就是要在这个 n 维线性空间中选出 qk个向量作为合法码字，其余的 qn-qk个向量为禁用码字。如果选出的 qk个作为合法码字的向量的集合构成了 V 的一个

26、k 维线性子空间，则称它是一个 q 进制n,k线性分组码4。2.3.1 汉明距离对于二元序列，还可以引入汉明距离。二元序列 X 中含有“1”的个数为 X 的汉明重量。对于二元对称信道，可以根据汉明距离来决定译码规则。最小码距 dmin 码组集中任意两个码字之间距离的最小值(1) 检测 e 个随机错误，则要求码的最小距离 d0e+1 (2) 纠正 t 个随机错误， 则要求码的最小距离 d02t+1(3) 纠正 t 个同时检测 e(t)个随机错误，则要求码的最小距离 d0t+e+12.3.2 生成矩阵和校验矩阵 n,k线性分组码的编码问题就是在n维线性空间 V 中，如何选出满足一定要求的k 维线性

27、子空间的问题。或者说，在满足给定条件（如码的最小距离 dmin，或码率）下， 7 如何从已知的 k 个信息元中求出 rn-k 个校验元。首先从已知的 k 个系数，求出 rn-k 个未知数，根据需求(如检测、纠正)使得到的码恰好有所要求的最小距离。对该例中的7,3线性分组码，若用C0，C1，C2代表信息元，则C3，C4，C5，C6四个校验元可由如下的线性方程组求得： 2106210521042103110011111101cccccccccccccccc式 2-1或 010001100010001100010111000011016543210654321065432106543210ccccc

28、ccccccccccccccccccccccc 式 2-2用矩阵写成：000010001100100011001011100011016543210ccccccc式 2-3上述运算为模 2 运算。系数矩阵的秩为 4，所以，它的解空间是一个 3 维线性子空间。因此，这个解空间就是由该线性分组码的全部码字所组成。HeT=oT,称 H 为该7，3线性分组码的一致校验矩阵。再将式 1 改写为： 8 2106210521042103221100110011111101111cccccccccccccccccccccc式 2-4用矩阵写成：1000110010001100101110001101),(,2

29、106543210cccccccccc 式 2-5记作： 0110001110001011101001011000G式 2-6称 G 为该7,3线性分组码的生成矩阵。G 的每一行是一个合法码字（C 的重量取 1） 。由于 G 的每一行都是n,k线性分组码字，所以 HGT 0 或 GHT 0。说明 G 与 H 的行向量生成的空间互为零空间。（如果选出的 qk个作为合法码字的向量的集合构成了 V 的一个 k 维线性子空间，则称它是一个 q 进制n,k线性分组码。 ）由于生成矩阵的秩是 k，所以每个行向量既是基底，也是一个码字。任何生成矩阵都可以通过行运算转换成如下形式：Gsys=Ik|P P 是

30、k*（n-k）矩阵，I 是 k 阶单位矩阵。Hsys=PT|In-k 42.3.3 纠错能力(1) 若n,k线性分组码的最小距离必等于码中非零码字的最小重量；(2) 如果线性码 C 是 H 矩阵的零化空间，则对于每一个重量为 W 的码字，H 中有相应的 W 列线性相关。反之，H 中若有W列线性相关，那么就有相应的重量为 W 的一个 9 码字；(3) 线性码的最小重量为 Wmin的充分必要条件是：一致校验矩阵 H 的任意 Wmin-1 列线性无关，而有 Wmin列线性相关；通过H求出码的最小重量 Wmin，即码的最小距离dmin，再利用分组码的最小距离与纠错能力的关系得到线性分组码的最小距离与纠

31、错能力的关系。2.4循环码 循环码是十分重要的线性分组纠错码，是最有用的一类。(1) 循环码有很多固有的代数结构，从而可以找到各种简单实用的译码方法。(2) 利用反馈线性移位寄存器很容易实现其编码和伴随式计算。设7，4汉明码C的生成矩阵和一致校验矩阵分别为： H=0001011001011001001111000101G110100101110101110101 得到 16 个码字是：（1000101） ， （0001011） ， （0010110） ， （0101100） ，（1011000） ， （0110001） ， （1100010） ， （0100111） ， （1001110） ，

32、 （0011101） ，（0111010） ， （1110100） ， （1101001） ， （1010011） ， （1111111）和（0000000） 。如果n,k线性分组码 C 的任何一个码字 c=(cn-1，cn-2，c1，c0)向左（或右）循环位移一位，得到的n维向量 c(1)=(cn-2，cn-3，c0，cn-1)也是 C 的码字，则称此n,k线性分组码为循环码5。2.4.1 码多项式 循环码可以用多种方式进行描述，在不同情况下使用不同的描述方式会有助于问题的解决。将一个码字的诸分量看成是一个多项式的系数，因此有如下的一一对应：c=(cn-1，cn-2，c1，c0)c(x)=

33、cn-1xn-1+cn-2 xn-2+c1x+c0。例（7，3）码：0011101 x4+x3+x2+10111010 x5+x4+x3+x=x(x4+x3+x2+1)mod(1+x7)1110100 x6+x5+x4+x2= x2(x4+x3+x2+1)mod(1+x7)1101001 x6+x5+x3+1= x3(x4+x3+x2+1)mod(1+x7)设 c(i)=(cn-1-i，cn-2-i，c1，c0，cn-1，cn-i) 表示 C 循环 I 次c(i)(x)= cn-1-ixn-1+cn-2-i xn-2+c1 xi+1+c0 xi+cn-1xi-1+ cn-i+1x+cn-i，实

34、际上 c(i)(x)=xic(x) mod (xn-1)，所以 xic(x) =c(i)(x) mod (xn-1) 10 2.4.2 多项式的基本性质(1) 在一个n,k线性分组码中，有惟一的非零最低次数的码多项式 g(x)。(2) 设 g(x)=xr+ar-1xr-1+a1x+a0为n,k循环码 C 的非零最低次数的码多项式，则任意一个次数小于或等于 n1 的多项式 h(x)是码多项式的充分必要条件，其充要条件为：h(x)是 g(x)的倍式。(3) n,k循环码的生成多项式 g(x)的次数等于 nk，并且常数项不等于零。(4) n,k循环码的生成多项式 g(x)一定是 xn1 的因式。(5

35、) 若 g(x)是 xn1 的 nk 次因式，则 g(x)生成一个n,k循环码，且 g(x)就是该n,k循环码的生成多项式。根据上述订立，我们可以找到构成（n、k）循环码的方法：(1) 对 xn1 实施因式分解，找出其中的 N-K 次多项式。(2) 以找出的 N-K 次因式构成循环码生成多项式 G(X)，与信息多项式 m(x)相乘，即得到码多项式：C(x)=m(x)g(x)其中 m(x)是 k-1 次信息多项式，与 k 重信息矢量相对应：m=(mk-1,mk-2,m1,m0)=mk-1xk-1+.+m1x+m0给出如下例子：分析码长 n=7 的二进制循环码的所有可能结构。解：分解因式 x7+1

36、，得到 x7+1=（x+1）(x3+x+1)(x3+x2+1)分解如下：1 次 x+13 次 x3+x+1 、x3+x2+14 次 （x+1）(x3+x+1)、 （x+1）(x3+x2+1)6 次 (x3+x+1)(x3+x2+1)断言，存在（7，6） 、 （7，4） 、 （7，3） 、 （7，1）循环码。以（7，3）循环码为例，若选 g(x)= （x+1）(x3+x+1)=x4+x3+x2+1 为生成多项式，则码多项式 C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1),当输入 m=(011)，则 m(x)=x+1,C(x)=x5+x2+x+1,则 C=(0 1

37、0 0 1 1 1 )，依次将（000）到（111）全部代入，则可以得到全部循环码集：000 0000000001 0011100010 0111010011 0100111100 1110100101 1101001 11 110 1001110111 1010011构成系统码的方法：所谓构成系统码，就是前 k 位为信息位，而后 n-k 位为校验元。我们认为码多项式应该具有如下的结构：C(x)=xn-km(x)+r(x)，其中 r(x)是与 n-k 位校验元对应的 n-k-1 次多项式。根据(4)可知，C(x)是 g(x)的倍式，即 C(x)=xn-km(x)+p(x)0modg(x)。所以

38、，p(x) xn-km(x)mod g(x)。也即将 m(x)移位 n-k 次，然后用 g(x)相除，所得余式就是 p(x)，实现循环码的编码。所以构成系统码的具体步骤为：(1) 将信息多项式 m(x)乘以 xn-k，即右移 n-k 位(2) xn-km(x)除以 g(x)，得到余式 r（x）(3) 写出码多项式 C(x)=xn-km(x)+r(x)例：同上例，g(x)= x4+x3+x2+1,产生循环码集合当输入 m=(011)时，xn-k m(x)= x4(x+1)=x5+ x4x5+ x4除以 x4+x3+x2+1 得到余式 x3+x得到 C(x)= x5+ x4+x3+x，得到（011

39、1010）2.4.3 循环码的生成矩阵和一致校验矩阵 一个n,k线性分组码是 n 维线性空间中的一个 k 维子空间，同样，一个n,k循环码也是 n 维线性空间中的一个 k 维子空间。因此，只要找出 k 个线性无关的码多项式，就可通过线性组合得到所有码多项式。由于码的生成多项式 g(x)是 n-k 次的，所以 g(x)，xg(x)，x2g(x)，xk-1g(x)都是线性无关的，可得码的生成矩阵：)()()()(21xgxxgxgxxgxGkk设 g(x)=x3+x+1 为7,4循环码的生成多项式，则对应的 g=(0，0，0，1，0，1，1)，所以，得到生成矩阵为：0001011001011001

40、011001011000G 12 由于g(x)是xn1 的因式，所以，可写成：xn1=g(x)h(x)。因为 g(x)h(x)= xn1，设 g(x)=arxr+ar-1xr-1+a1x+a0， h(x)=bkxk+bk-1xk-1+b1x+b0，则(arxr+ar-1xr-1+a1x+a0)( bkxk+bk-1xk-1+b1x+b0)= xn1，已知 arbk1，a0b01，而 xn-1，xn-2，x 等的系数均为 0。由此可知循环码的校验矩阵为： H=kkkbbbbbbbbb1010100000000。若记h(x)=b0 xk+b1xk-1+bk-1x+bk，则 )()(*)(*)(*)

41、(H21xhxhxxhxxhxxknkn因此，H 由 h(x)的系数决定，故称h(x)是循环码的校验多项式。7,4循环码中，生成的多项式为 g(x)=x3+x+1。因在式 GF(2)上，x7-1=(x+1)( x3+x+1)( x3+x2+1)，所以，h(x)= x4+x2+x+1，则对应的 h*=(1,1,1,0,1)，因此，得到生成矩阵和校验矩阵为： 0001011001011001011001011000G001110101110101110100H容易验证GHT=0。以 x3+x+1 为生成多项式生成一个（7，4）循环码，而且是系统码，步骤如下：g(x)= x3+x+1，h(x)=(x

42、+1)(x3+x2+1)= x4+x2+x+1，对上述矩阵作初等行变换，我们知道这样并不改变行向量的线性相关性，00010110010110010011110001010001011001011001011001011000p|IG2421431ksys110100101110101110100I |pHkNTsys 13 2.5.NET.Framework 介绍 NET Framework 是微软的几个开发团队一起努力发展的成果，最主要用来产生一个可以用来快速开发、部署网站服务及应用程序的开发平台。这个架构是两个项目的结果：第一个项目的目的是用来改善 Windows 作业平台上的程序开发，特

43、别是改善COM（Component Object Model，组件对象模块。一种微软所制定的软件技术；让对象的功能可以被其它软件所叫用，可以让组件重复使用、容易更新及维护） ；第二个项目则是制作一个以发展服务（Service）软件为目标的开发平台。这两个项目团队三年多前就已经在一起工作，他们希望可以发展出一种可以快速开发出以因特网为基础，而且易学易用的开发平台。为了要达到这些目标，所以.Net Framework 在设计时加入了下列特色：(1) 透过因特网的标准做整合以 XML（eXtensible Markup Language，延伸标注语言）及SOAP（Simple Object Acce

44、ssProtocol，简单对象存取协议）等标准通讯协议，将各种由不同环境所组成的应用程序及组件整合在一起工作。(2) 松散的整合组件大多数具延展能力（可扩充功能）的系统，现阶段是以异步讯息为架构而建立的。要建立这种多层的架构非常复杂，而且工具很少。.NET Framework 不需要很严谨的定义每个组件的结构即可很轻松的整合，这样可提高程序的延展性。(3) 支持多种程序语言许多程序设计师会使用多种语言来开发他们的解决方案，这是因为每种语言都有它的长处。例如某些语言对于数值计算效率较好，某些语言对于数据库的操作较为方便，而某些语言又有大量的链接库可供使用；所以没有办法强迫别人只学一种程序语言。.

45、NET Framework 把这些语言整合起来，可以让开发人员使用不同的程序语言来开发解决方案，让程序设计师可以选择他们专长的程序语言，企业则可省去重新训练员工的成本。(4) 提高程序设计师的生产力现今程序设计师人才非常缺乏，程序设计师在人力不足的情形之下就必需提高生产力，因为每个项目的时程很可能很急促；况且公司也希望赶快结案好再进行下一个项目。正因如此，.NETFramework 的开发团队希望尽可能减少写程序会发生的问题，让程序设计师专心于撰写企业法则（企业处理数据的规则） 。所以.NET Framework 有些节省时间的特色，例如容易使用的自动交易机制、自动内存管理，以及丰富的控件。(

46、5) 完善的数据保全目前因特网最受大家注目的，就是它的安全性。要设计一个安全性完善的因特网应用程序，在设计时就必须考虑所有组件的保全设计，而不能仅做一部分而已。 14 .NET Framework 在设计安全模型时时即考虑到这点，将所有的数据与程序代码做完善的安全防护。(6) 可用操作系统的服务Windows 提供了比其它作业平台更丰富的服务及资源，例如众多的数据存取服务、使用系统所提供的整合安全模式来做身分验证及保全的工作、交互式的使用者接口、成熟的对象模块、交易程序监视以及讯息队列服务。.NET Framework 当然也将这些操作系统所提供出来的功能包装起来，以更简单的方式提供程序设计师

47、使用。2.6 C#语言C#(读做 C sharp，中文译音“夏普”)是微软公司发布的一种面向对象的、运行于.NET Framework 之上的高级程序设计语言,并定于在微软职业开发者论坛(PDC)上登台亮相.C#是微软公司研究员 Anders Hejlsberg 的最新成果.C#看起来与 Java 有着惊人的相似;它包括了诸如单一继承,界面,与 Java 几乎同样的语法,和编译成中间代码再运行的过程.但是 C#与 Java 有着明显的不同,它借鉴了 Delphi 的一个特点,与COM(组件对象模型)是直接集成的,而且它是微软公司.NET windows 网络框架的主角. C#从 Java 继承

48、而来的特点 C#从 C 和 C+继承的特点C#独有的特点 (1) 中间代码:微软在用户选择何时 MSIL 应该编译成机器码的时候是留了很大的余地.微软公司很小心的声称 MSIL 不是解释性的,而是被编译成了机器码.它也明白许多-如果不是大多数的话-程序员认为 Java 程序要不可避免的比 C 编写的任何东西都要慢.而这种实现方式决定了基于 MSIL 的程序(指的是用 C#,Visual Basic,Managed C+-C+的一个符合 CLS 的版本-等语言编写的程序)将在性能上超过解释性的Java 代码.当然,这一点还需要得到事实证明,因为 C#和其他生成MSIL 的编译器还没有发布.但是

49、Java JIT 编译器的普遍存在使得 Java 和 C#在性能上相对相同.象C#是编译语言而 Java 是解释性的,之类的声明只是商业技巧.Java的中间代码和 MSIL 都是中间的汇编形式的语言,它们在运行时或其它的时候被编译成机器代码. 命名空间中的申明:当你创建一个程序的时候,你在一个命名空间里创建了一个或多个类.同在这个命名空间里(在类的外面)你还有可能声明界面,枚举类型和结构体.必须使用 using 关键字来引用其他命名空间的内容. (2) 基本的数据类型:C#拥有比 C,C+或者 Java 更广泛的数据类型.这些类型是 bool, byte, ubyte, short, usho

50、rt, int, uint, long, ulong, float, double,和decimal.象 Java 一样,所有这些类型都有一个固定的大小.又象 C 和 C+一样,每个数据类型都有有符号和无符号两种类型.与 Java 相同的是,一个字符变量包含的是一个 16 位的 Unicode 字符.C#新的数据类型是 decimal 数据类型,对于货币数据,它能存放 28 位 10 进制数字. 15 (3) 两个基本类:一个名叫 object 的类是所有其他类的基类.而一个名叫 string 的类也象 object 一样是这个语言的一部分.作为语言的一部分存在意味着编译器有可能使用它-无论何

51、时你在程序中写入一句带引号的字符串,编译器会创建一个 string 对象来保存它. (4) 参数传递:方法可以被声明接受可变数目的参数.缺省的参数传递方法是对基本数据类型进行值传递.ref 关键字可以用来强迫一个变量通过引用传递,这使得一个变量可以接受一个返回值.out 关键字也能声明引用传递过程,与 ref 不同的地方是,它指明这个参数并不需要初始值. (5) 与 COM 的集成:C#对 Windows 程序最大的卖点可能就是它与 COM 的无缝集成了,COM就是微软的 Win32 组件技术.实际上,最终有可能在任何.NET 语言里编写 COM 客户和服务器端.C#编写的类可以子类化一个以存

52、在的 COM 组件;生成的类也能被作为一个 COM 组件使用,然后又能使用,比方说,JScript 语言子类化它从而得到第三个 COM组件.这种现象的结果是导致了一个运行环境的产生,在这个环境里的组件是网络服务,可用用任何.NET 语言子类化. 2.7Visual Studio 2005 概述 Visual Studio .NET 是一套完整的开发工具，用于生成 ASP Web 应用程序、XML Web services、桌面应用程序和移动应用程序。Visual Basic .NET、Visual C+ .NET、Visual C# .NET 和 Visual J# .NET 全都使用相同的集

53、成开发环境(IDE)，该环境允许它们共享工具并有助于创建混合语言解决方案。另外，这些语言利用了.NET Framework 的功能，此框架提供对简化 ASP Web 应用程序和 XML Web services 开发的关键技术的访问。3 编译码3.1行列校验码其编码方法是将若干要传送的信息码元编成一个矩阵，矩阵的每一行为一个码组进行奇偶校验。矩阵中的每一列由不同码组系统位置的码无组成，每列都进行奇偶校验。这样每一行，每一列均构成一个奇偶校验码。 下面以十六位数据为例解释行列校验码的编译码过程。利用 D15D0表示数据位，H3H0表示行校验位，V3V0表示列校验位。则编码长度为二十四位。D0D1

54、D2D3V0D4D5D6D7V1D8D8D10D11V2 16 D12D13D14D15V3H0H1H2H3表 3-1:行列校验码公式 1V0= D0D1D2D3V1= D4D5D6D7V2= D8D9D10D11V3= D12D13D14D15公式 2H0= D0D4D8D12H1= D1D5D8D13H2= D2D6D10D14H3= D3D7D11D15编码时十六位数据 D15D0是随机的，H3H0是根据公式 2 计算得出，V3V0根据公式 1 计算得出。3.1.1 C#语言实现行列校验码(1) 计算有多少位信息元、自动分成多少行多少列public int range()/构造分组函数,

55、计算分成多少行多少列 string a = textBox1.Text;/将窗口1输入的字符付给字符变量a int d = a.Length;/计算字符个数 int i; for (i = 1; i =d) break; return i; (2) 将字符 0、1 转化为数值 0、1 private void textBox1_Validating(object sender, CancelEventArgs e 17 string a = textBox1.Text; /将窗口1输入的字符付给字符变量a int d = a.Length; /计算字符个数 int j; for(j=0;jd;

56、j+)/将计算机输入的字符0、1转化为数值0、1 if (aj = 0)/如果字符是0则ab数值为0 abj = 0; else if (aj = 1) /如果字符是1则ab数值为1 abj = 1; else /提示只能输入0或1 MessageBox.Show(你只能输入0 或1 ！); textBox1.Focus();/焦点停留在窗口1 break; (3) 计算输入的字符分组后有多少行public int hang()/计算行函数 string a = textBox1.Text; /将窗口1输入的字符付给字符变量a int d = a.Length; /计算字符个数 int t =

57、 range();/调用分组函数 int k = 0;/变量k表示多少行 for (int i = 1; i = t; i+)/如果列数乘以行数大于字符个数加列数就跳出，返回k值 if (t * i d + t) k+; 18 return k; (4) 补零、计算每行、列数值 1 的个数、模 2 运算private void button2_Click(object sender, EventArgs e)/ string a = textBox1.Text; /将窗口1输入的字符付给字符变量a int d = a.Length; /计算字符个数 int m=0; int k=0; int

58、i; int j; int t=range();/调用分组函数 string v = new stringt;/行的校验码 int c = new intt;/行的校验码的暂时变量 int o = new int2000; /列的校验码的暂时变量 string h= new stringt;/列的校验码 int n = t * t - d;/计算补零个数 int kkk;/将行函数的变量付给kkk double nnn;/编码效率变量 string dak; textBox2.Clear();/清屏 for (i = 0; i n; i+)/补0，将字符“0”加到输入字符串的后面 a += 0

59、; /行校验码 for (i = 0; i t; i+)/将窗口1输入的字符分组后转化为数值后付给ab,计算每行有多少个数值1 for (j = 0; j t; j+) ci+=abk; k+;/转到下一行 k=0;/将K变量清零 19 for (i = 0; i t; i+)/利用奇校验码，如果那一行数值1的个数模2为零，则其行校验码为数值1，否则行校验码为数值0 if (k = ci % 2) vi = 1; else vi = 0; /列校验码 for (i = 0; i t; i+)/将窗口1输入的字符分组后转化为数值后付给ab,计算每行有多少个数值1 for (j = 0; j t;

60、 j+) oi += abk; k=k+t;/转到下一列 k =i; k = 0; /将K变量清零 for (i = 0; i t; i+)/利用奇校验码，如果那一列数值1的个数模2为零，则 其列校验码为数值1，否则列校验码为数值0 if (k = oi % 2) hi = 1; else hi = 0; 20 (5) 将整型转化为字符 public string tostring(int a)/ 构造一个将整型转化为字符的函数 string ddc = ; switch (a) case 0: ddc = 0; break;/将字符0转化为数值0 case 1: ddc = 1; break