移动通信的发展日新月异，从1978年第一代模拟蜂窝通信系统诞生至今，不过20多年的时间，就已经过三代的演变，成为拥有10亿多用户的全球电信业最活跃、最具发展潜力的业务。尤其是进几年来，随着第三代移动通信系统（3G）的渐行渐近，以及各国政府、运营商和制造商等各方面为之而投入的大量人力物力，移动通信又一次地在电信业乃至全社会掀起了滚滚热潮。虽然目前由于全球电信业的低迷以及3G系统自身存在的一些问题尚未完全解决等因素，3G业务的全面推行并不象计划中的顺利，但新一代移动通信网的到来必是大势所趋。因此，人们对新的移动通信技术的研究的热情始终未减。
移动通信的强大魅力之所在就是它能为人们提供了固话所不及的灵活、机动、高效的通信方式，非常适合信息社会发展的需要。但同时，这也使移动通信系统的研究、开发和实现比有线通信系统更复杂、更困难。实际上，移动无线信道是通信中最恶劣、最难预测的通信信道之一。由于无线电波传输不仅会随着传播距离的增加而造成能量损耗，并且会因为多径效应、多普勒频移和阴影效应等的影响而使信号快速衰落，码间干扰和信号失真严重，从而极大地影响了通信质量。
为了解决这些问题，人们不断地研究和寻找多种先进的通信技术以提高移动通信的性能。特别是数字移动通信系统出现后，促进了各种数字信号处理技术如多址技术、调制技术、纠错编码、分集技术、智能天线、软件无线电等的发展。本文将主要关注在几代移动通信系统中所使用的不同的纠错编码技术，以展示纠错编码在现代数字通信中的重要作用。
二、纠错编码基础知识
1948年，香农(Shannon)在他那篇著名的论文《通信的数学理论》中提出并证明了：对于一个信道容量为C的有扰信道，消息源产生信息的速率为R，只要R≤C，则总可以找到一种信道编码和译码方式使编码错误概率P随着码长n的增加，按指数下降到任意小的值，表示为，这里E( R )称为误差指数；若R>C，则不存在编译码方式来实现无误传输。这一结论为信道编码指出了方向，但它仅是一个存在性定理，并未给出怎样
去寻找这种性能优良的码。
近50年来，在信息技术发展和实际需要的不断推动下，人们一直在寻求实现复杂度合理的更优秀的编译码方法，去逼近Shannon理论的理想界限。令人鼓舞的是，在这个过程中，已经取得了许多伟大的进展，从早期的分组码、代数码，到RS码,到后来的卷积码，以及今天的Turbo ,LDPC码，所能达到的性能和Shannon限间的距离被不断缩小。这些方法也已经投入到多个领域的商用中，如卫星通信和深空通信，数据存储，数据传输，移动通信，数字音频和视频传输等。下面，我们将着重关注移动通信系统，特别是数字移动通信系统中，纠错编码技术的应用情况。
三、移动通信中纠错编码的应用和发展
如前所述，移动信道的恶劣性使接收信号展现出非常差的错误率（5-10%），迫使译码器在非常低的信噪比下工作。另一方面，“频带”是移动通信系统宝贵而紧张的资源，尤其是在用户密集的闹市区和室内通信系统里。为此，对编译码器的设计就提出了较高要求，驱使译码要充分用到所有已知的信号特点，如信道状态信息、级联、交织和软判决等；而且，会占用带宽的信息“冗余”必须谨慎使用。但同时，数字电路技术的快速发展也提高了复杂度较高的纠错编码的可行性。
1．模拟移动通信系统中数字信令的BCH编码
模拟蜂窝系统中，业务信道主要是传输模拟FM电话以及少量模拟信令，因此未应用数字处理技术。而控制信道均传输数字信令，并进行了数字调制和纠错编码。以英国系统为例，采用FSK调制，传输速率为8kb/s。基站采用的是BCH（40，28）编码，汉明距离d =5, 具有纠正2位随机错码的能力。之后重发5次，以提高抗衰落、抗干扰能力；移动台采用了BCH（48，36）进行纠错编码，汉明距离d =5，可纠正2个随机差错或纠正1个及检测2个差错,然后也是重复5次发送。上述纠错编码是提高数字信令传输可靠性必需的，也是行之有效的。
2．GSM的FEC编码
GSM系统仍是目前使用最广泛的移动通信系统，也是纠错编码最重要的应用之一。GSM标准的语音和数据业务使用多种FEC编码，包括BCH编码，FIRE码，CRC码（错误检测，码同步和接入，数据信道）。这些码都作为级联码的外码，我们这里主要侧重于级联码的内码方案，最初用于全速率语音业务信道。语音编码后的13kb/s信息，一个时隙20ms包括260bit，分成三个敏感类：78bit对错误不敏感类不加编码保护；50bit 特别敏感类加3bit奇偶校验，4bit格图终结尾比特,与其余的132bit，一共189bit用（2，1，5）的非系统卷积码进行编码。所以一共有378bit，加上未编码78bit，一共456bit，每20ms，总的速率为22.8。再加上相邻另外1个语音编码块的456bit一起，每组各占57bit*2进行（8*114）交织，分布到TDMA的8个突发中，在移动信道中使用GMSK调制。这些突发里还包括2bit业务/控制标识比特, 6bit尾比特,8.25bit 保护比特，还有26bit训练序列，提供给接收端的使用Viterbi算法的MMSE均衡器输出每块456软或硬判决值。
如果按GSM标准规定使用了跳频，那么我们可合理将信道视为统计独立的Rayleigh信道。这种情况下，如果使用CSI和软值，r=1/2的编码可得到3.1dB的增益。
3．窄带CDMA系统(IS-95)中的FEC编码
CDMA系统是个自干扰的系统，因此FEC编码在对抗多用户干扰（MUI）和多径衰落非常重要。CDMA（IS-95）系统的纠错编码是分别按反向链路和前向链路来进行设计的，主要包括卷积编码、交织、CRC校验等。现分述如下：
前向链路中除导频信道外，同步信道、寻呼信道和前向业务信道中的信息在传输前都要先进行（2，1，9）的卷积编码，卷积码的生成函数为go=（111101011）和g1=（101110001）；接着，同步信道的符号流要经过1次重发，然后进行16*8的块交织；
业务和寻呼信道的速率为4.8kbps/2.4kbps/1.2kbps符号流，分别进行1/3/7次重发（9.6kbps数据流不必重发），然后再进行24*16的块交织。
反向链路包括业务信道和接入信道，考虑到移动台的信号传播环境，增加编码长度，对信息进行（3，1，9）的卷积码。其生成函数为：g0=（101101111），g1=（110110011）和g2=（111001001）。然后，接入信道经过一次重发后，进行32*18交织；反向业务信道以同前向一样的方式进行重发，再进行32*18的交织。
如果整体考虑纠错编码和扩频调制，则可把扩频看作内码，而信道编码视作外码。以后向链路为例，编码交织后是64阶正交Walsh函数扩频，然后是被周期为2 -1的长码直接序列扩频。
接收端经相干或不相干Rake接受机进行分集接收后，系统码字（信息比特）就可以用相关的最大值或相关矢量的最大值表示。接着送到解交织器和外部SOVA Viterbi 译码器。
4．3G中的Turbo码
3G与2G最重要的不同是要提供更高速率、更多形式的数据业务，所以对其中的纠错编码体制提出了更高的要求（数据业务的差错率要小于10 ）。语音和短消息等业务仍然采用与GSM 和CDMA相似的卷积码，而对数据业务3GPP协议中已经确定Turbo 码为其纠错编码方案。
Turbo码又叫并行级联卷积码，由Berrou,Glavieux 和Thtimajshima 1993年首次提出。Turbo码编码器通过交织器把两个递归系统卷积码并行级联，译码器在两个分量码译码器之间进行迭代译码，译码之间传递去掉正反馈的外信息，整个译码过程类似涡轮（turbo）工作，所以又形象的称为Turbo码。
编码器的输出端包括信息位和两个校验位，这样代表编码速率1/3。轮流删除两个校验位就可以得到码率是1/2的码。用不同的校验位生成器或者不同的删除方式就可以得到各种不同速率的Turbo码。伪随机交织器对信息系列进入第二个校验位生成器之前
进行了重排列。迭代译码是Turbo码性能优异的一个关键因素，如上图所示，DEC1和DEC2分量译码器分别采用MAP或者SOVA算法。MAP（最大后验概率）算法比Viterbi 算法在复杂度上多3倍，对于传统卷积码只有0.5dB的增益，但是在Turbo码译码器中，它对每一比特给出了最大的MAP估计，这一点在低SNR情况下的迭代译码是至关重要的因素。一般在应用中，都采用对数化的MAP算法，即LOG-MAP算法，将大部分的乘法运算转化为加法运算，既减小了运算复杂度，又便于硬件实现。
实验四 纠错编码基本实验 一、实验目的 1、通过实验理解线性分组码的基本原理； 2、练习根据理论分析自行设计实验方法的能力。 二、实验内容 1、已知一(10,4)线性分组码的生成矩阵为 1001110111111000111001101101011101111001G ??????=?????? 试用Matlab 求出该码的全部码字和最小汉明距离。 2、用Matlab 求x 15+1的所有因子，构造(15,4)循环码的所有可能的生成多项式；选择 其中一个作为(15,4)循环码的生成多项式，求出所有的许用码字，并计算最小汉明距离。 三、实验原理 1、线性生成码的原理 线性分组码的构成方式是把信息序列分成每k 个码元一段，并由这k 个码元按一定规则产生r 个校验位，组成长度为n = k + r 的码字，用(n, k) 表示信息码元与校验位之间为线性关系。 一个[n ,k ]线性分组码，是把从信源输出的以k 个码元为一组的信息组m ，通过信道编码器后，变成长度为n ≥k 的码组（码字）c 作为[n ,k ]线性分组码的一个码字。 设GF(q )是一个含有q 个元素的有限数域，若每位码元的取值有q 种（取自GF(q )），则信息组m 共有k q 种不同的状态，因此，需要k q 个码字c 。而长为n 的数组共有n q 个，二进制时(q =2)共有n 2个。显然，n q 个n 维向量组成有限域GF(q )上的一个n 维线性空间V ，编码就是要在这个n 维线性空间中选出k q 个向量作为合法码字，其余的n q -k q 个向量为禁用码字。 如果选出的k q 个作为合法码字的向量的集合构成了V 的一个k 维线性子空间，则称它是一个q 进制[n ,k ]线性分组码。 如果值取自GF(q )上的[n ,k ]分组码的k q 个码字的集合C ，便构成了有限域GF(q )上的n 维线性空间V 的一个k 维线性子空间，则称C 是一个q 进制[n ,k ]线性分组码。 2、循环码的编码原理 在编码时，首先需要根据给定循环码的参数确定生成多项式g (x )，也就是从 的因子中选一个 （n-k ）次多项式作为g (x )；然后，利用循环码的编码特点，即所有循环码多项式A (x )都可以被g (x )整除， 来定义生成多项式g (x )。 根据上述原理可以得到一个较简单的系统循环码编码方法：设要产生（n,k ）循环码，m (x )表示信息多 项式，则其次数必小于k ，而·m (x )的次数必小于n ，用·m (x )除以g (x )，可得余数r (x )，r (x )的次 数必小于（n-k ），将r (x )加到信息位后作监督位，就得到了系统循环码。 下面就将以上各步处理加以解释： （1）用乘m (x )。这一运算实际上是把信息码后附加上（n-k ）个“0”。例如， 信息码为110，它相 当于m (x )＝ +x 。当n-k ＝7-3＝4时，·m （x ）＝+，它
汉明码的编码检错原理 针对4位数据的汉明码编码示意图 汉明码是一个在原有数据中插入若干校验码来进行错误检查和纠正的编码技术。以典型的4位数据编码为例，汉明码将加入3个校验码，从而使实际传输的数据位达到7个（位），它们的位置如果把上图中的位置横过来就是： 数据位1234567 代码P1P2D8P3D4D2D1 说明第1个 汉明码 第2个 汉明码 第1个 数据码 第3个 汉明码 第2个 数据码 第3个 数据码 第4个 数据码 注：Dx中的x是2的整数幂（下面的幂都是指整数幂）结果，多少幂取决于码位，D1是0次幂，D8是3次幂，想想二进制编码就知道了 现以数据码1101为例讲讲汉明码的编码原理，此时D8=1、D4=1、D2=0、D1=1，在P1编码时，先将D8、D4、D1的二进制码相加，结果为奇数3，汉明码对奇数结果编码为1，偶数结果为0，因此P1值为1，D8+D2+D1=2，为偶数，那么P2值为0，D4+D2+D1=2，为偶数，P3值为0。这样，参照上文的位置表，汉明码处理的结果就是1010101。在这个4位数据码的例子中，我们可以发现每个汉明码都是以三个数据码为基准进行编码的。下面就是它们的对应表： 汉明码编码用的数据码 P1D8、D4、D1 P2D8、D2、D1 P3D4、D2、D1 从编码形式上，我们可以发现汉明码是一个校验很严谨的编码方式。在这个例子中，通过对4个数据位的3个位的3次组合检测来达到具体码位的校验与修正目的（不过只允许一个位出错，两个出错就无法检查出来了，这从下面的纠错例子中就能体现出来）。在校验时则把每个汉明码与各自对应的数据位值相加，如果结果为偶数（纠错代码为0）就是正确，如果为奇数（纠错代码为1）则说明当前汉明码所对应的三个数据位中有错误，此时再通过其他两个汉明码各自的运算来确定具体是哪个位出了问题。 还是刚才的1101的例子，正确的编码应该是1010101，如果第三个数据位在传输途中因干扰而变成了1，就成了1010111。检测时，P1+D8+D4+D1的结果是偶数4，第一位纠错代码为0，正确。P1+D8+D2+D1的结果是奇数3，第二位纠错代码为1，有错误。P3+D4+D2+D1的结果是奇数3，第三但纠错代码代码为1，有错误。那么具体是哪个位有错误呢？三个纠错代码从高到低排列为二进制编码110，换算成十进制就是6，也就是
第五章纠错编码习题解答 1、已知一纠错码的三个码组为(001010)、(101101)、(010001)。若用于检错，能检出几位错码？若用于纠错，能纠正几位错码？若纠检错结合，则能纠正几位错码同时检出几位错码？ ［解］该码的最小码距为d o=4，所以有： 若用于检错，由d o> e+1，可得e=3,即能检出3位错码；若用于纠错，由d o> 2t+1，可得t=1，即能检出1位错码；若纠检错结合，由d o> e+t+1 (e>t),可得t=1, e=2，即能 纠正1 位错码同时能检出2 位错码。 2、设某(n,k)线性分组码的生成矩阵为： 001011 G 1 0 0 1 0 1 010110 ①试确定该(n,k)码中的n和k； ②试求该码的典型监督矩阵H； ③试写出该码的监督方程； ④试列出该码的所有码字； ⑤试列出该码的错误图样表； ⑥试确定该码的最小码距。 ［解］①由于生成矩阵G 是k 行n 列，所以k=3，n=6。 ②通过初等行变换，将生成矩阵G变换成典型生成矩阵 10 0 10 1
G 0 10 1 10 I k Q 0 0 10 11 1 0 1 1 1 0 由于Q 1 1 0 , P= Q T= 0 1 1，可知典型监督矩阵为 0 1 1 1 0 1 110 10 0 H = PI r 0 110 10 10 10 0 1 85 玄4 a? 0 ③监督方程为a。a3 q 0 a5 a3 a0 0 ④所有码字见下表 ⑤错误图样表即错误图样与校正子关系表，见下表
⑥线性码的最小码距为码字的最小重量(全零码除外) ，所 以该码的最小码距为 3。 3、已知一种(7,3)循环码的全部码组为： 0000000 0101110 1001011 1100101 0010111 0111001 1011100 1110010 试求该码的生成多项式 g(x)、典型生成矩阵G 和典型监督矩阵H ； ［解］由循环码的原理知，生成多项式g(x)对应的码字为前k-1 位码元 均为“ 0”的码字，即“ 0010111”，所以有 g(x)=x 4+x 2+x+1 x 2 g(x) 6 4 x x 3 x 2 x 1 0 1 1 1 0 0 则生成矩阵为G xg(x) 5 3 x x 2 x x 0 1 0 1 1 1 0 g(x) 4 2 x x x 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1
ADSL编码调制基本原理 1概述 数字用户线路，简称DSL。迄今为止，世界各国已相继开发出了HDSL（高比特率数字用户线）、SDSL（对称数字用户线）、VDSL（甚高速数字用户线）、ADSL（非对称数字用户线）与RADSL（速率自适应数字用户线）等多种不同类型的DSL接入技术。我们将它们统称为“xDSL”，xDSL接入技术的基础系统架构与原理基本上是相似的，所不同的只是这几种技术在信号传输速率与距离、具体实现方式及上、下行速率的对称性等方面有所区别而已。 xDSL是一种先进的传输技术，基本原理就是将模拟环路改造成数字用户线环路，在现有的铜质电话线路上采用较高的宽带和相应的调制技术，来获得高传输速率（理论上可达到100Mbps），正是为克服到用户“最后一公里”的传输瓶颈而产生的。其中ADSL是前景最好及竞争力最强的，也是电信公司占领宽带接入网市场的主要接入技术。它允许在一对双绞铜线上，不影响现有POTS电话业务的情况下，进行非对称高速数据传输。利用现有双绞线传输宽带业务，可保护投资、降低成本，特别适于大量分散的住宅用户，因此被广泛用于Internet接入、远端LAN接入、视频点播(VOD)、远程教学、多媒体检索等宽带业务的接入与传输。 编码调制技术是ADSL技术的核心，也是本文关注的重点。 2ADSL编码调制技术 我们知道，普通modem是工作在音频范围内，即300~3,400Hz的频段。根 据香农公式： 2(1) S C BLog N =+。 对于带宽3000Hz、信噪比((SNR)为30dB的信道，普通modem最大传输速率也只能达到30Kbit/s。与普通modem不同，ADSL modem是利用双绞线的远大于音频带宽的资源（接近2M带宽），采用现代数字信号处理技术和数字编码调制技术，通过动态的建立线路的信噪比模型来使线路利用率最佳。虽然话音只需要4KHz的带宽，但上行信道开始处频率越低，分离器的设计就越困难，所以一般都是选在25.875kHz。分离器实际上是由低通滤波器和高通滤波器合成的
移动通信的发展日新月异，从1978年第一代模拟蜂窝通信系统诞生至今，不过20多年的时间，就已经过三代的演变，成为拥有10亿多用户的全球电信业最活跃、最具发展潜力的业务。尤其是进几年来，随着第三代移动通信系统（3G）的渐行渐近，以及各国政府、运营商和制造商等各方面为之而投入的大量人力物力，移动通信又一次地在电信业乃至全社会掀起了滚滚热潮。虽然目前由于全球电信业的低迷以及3G系统自身存在的一些问题尚未完全解决等因素，3G业务的全面推行并不象计划中的顺利，但新一代移动通信网的到来必是大势所趋。因此，人们对新的移动通信技术的研究的热情始终未减。 移动通信的强大魅力之所在就是它能为人们提供了固话所不及的灵活、机动、高效的通信方式，非常适合信息社会发展的需要。但同时，这也使移动通信系统的研究、开发和实现比有线通信系统更复杂、更困难。实际上，移动无线信道是通信中最恶劣、最难预测的通信信道之一。由于无线电波传输不仅会随着传播距离的增加而造成能量损耗，并且会因为多径效应、多普勒频移和阴影效应等的影响而使信号快速衰落，码间干扰和信号失真严重，从而极大地影响了通信质量。 为了解决这些问题，人们不断地研究和寻找多种先进的通信技术以提高移动通信的性能。特别是数字移动通信系统出现后，促进了各种数字信号处理技术如多址技术、调制技术、纠错编码、分集技术、智能天线、软件无线电等的发展。本文将主要关注在几代移动通信系统中所使用的不同的纠错编码技术，以展示纠错编码在现代数字通信中的重要作用。 二、纠错编码基础知识 1948年，香农(Shannon)在他那篇著名的论文《通信的数学理论》中提出并证明了：对于一个信道容量为C的有扰信道，消息源产生信息的速率为R，只要R≤C，则总可以找到一种信道编码和译码方式使编码错误概率P随着码长n的增加，按指数下降到任意小的值，表示为，这里E( R )称为误差指数；若R>C，则不存在编译码方式来实现无误传输。这一结论为信道编码指出了方向，但它仅是一个存在性定理，并未给出怎样
目录 设计总说明 ............................................................... I Introduction ........................................................... III 1 绪论 (1) 2 纠错码的基本概念 (3) 2.1数字通信系统 (3) 2.1.1 数字通信系统的组成 (3) 2.1.2 信道模型 (4) 2.2差错控制系统和纠错码分类 (7) 2.2.1 差错控制系统的分类 (7) 2.2.2 纠错码的分类 (9) 3 线性分组码 (11) 3.1线性分组码的基本概念 (11) 3.2线性分组码的编码 (11) 3.2.1 生成矩阵 (11) 3.2.2 校验矩阵 (15) 3.2.3 编码的实现 (15) 3.3线性分组码的译码 (16) 3.3.1 线性分组码的纠检错能力 (17) 3.3.2 伴随式解码 (1) 4 循环码 (20) 4.1循环码的一般概念 (20) 4.1.1 循环码的定义 (20) 4.1.2 循环码的生成多项式 (20) 4.2循环码的编码 (20) 4.3循环码的译码 (22) 4.4 BCH码 (24) 4.4.1BCH的编码算法 (24)
4.4.2 BCH的译码算法 (25) 4.5 RS码 (26) 4.5.1 RS编码算法 (26) 4.5.2RS的译码 (26) 5 卷积码 (28) 5.1卷积码的表示 (28) 5.2卷积码的编码原理 (29) 5.3卷积码的译码 (29) 6 纠错码在移动通信中的应用 (32) 6.1移动通信的概述 (32) 6.2移动通信中的差错控制 (32) 6.2.1 移动通信中的差错控制 (32) 6.2.2 移动通信中常用的纠错方式 (33) 6.2.3 编码方法 (34) 6.3移动通信中纠错码的应用和发展 (34) 6.3.1 模拟移动通信系统中数字信令的BCH编码 (34) 6.3.2 GSM的FEC编码 (35) 6.3.3 DMA系统(IS-95)中的FEC编码 (35) 6.3.4．3G中的Turbo码 (36) 7 MATLAB简介及卷积码的仿真 (37) 7.1MATLAB (37) 7.2MATLAB在通信仿真中的应用 (37) 7.3卷积码的仿真 (38) 8 总结 (37) 参考文献................................................ 错误！未定义书签。 附录 (44) 致谢 (46)
74汉明码编码 1. 线性分组码是一类重要的纠错码，应用很广泛。在（n ，k ）分组码中，若 冗余 位是按线性关系模2相加而得到的，则称其为线性分组码。 现在以(7,4)分组码为例来说明线性分组码的特点。 其主要参数如下： 码长：21m n =- 信息位：21m k m =-- 校验位：m n k =-，且3m ≥ 最小距离：min 03d d == 其生成矩阵G （前四位为信息位，后三位为冗余位）如下： 系统码可分为消息部分和冗余部分两部分，根据生成矩阵，输出码字可按下 式计 算： 所以有 信息位 冗余位 由以上关系可以得到(7,4)汉明码的全部码字如下所示。 表2 (7,4)汉明码的全部码字 序号 信息码元 冗余元 序号 信息码元 冗余元 0 0000 000 8 1000 111 1 0001 011 9 1001 100 2 0010 101 10 1010 010 3 0011 110 11 1011 001 4 0100 110 12 1100 001 5 0101 101 13 1101 010 6 0110 011 14 1110 100 7 0111 000 15 1111 111 1000110010001100101110001101G ? ? ?? ?? =?? ???? 3210321010001100100011(,,,)(,,,)00101110001101b a a a a G a a a a ?? ?? ??=?=??? ???? 635241 30 b a b a b a b a ====2310 1321 0210b a a a b a a a b a a a =⊕ ⊕=⊕⊕=⊕⊕
第五章 纠错编码习题解答 1、已知一纠错码的三个码组为(001010)、(101101)、(010001)。若用于检错，能检出几位错码？若用于纠错，能纠正几位错码？若纠检错结合，则能纠正几位错码同时检出几位错码？ [解]该码的最小码距为d 0=4，所以有： 若用于检错，由d 0≥e +1，可得e =3，即能检出3位错码； 若用于纠错，由d 0≥2t +1，可得t =1，即能检出1位错码； 若纠检错结合，由d 0≥e +t +1 （e >t ），可得t =1，e =2，即能纠正1位错码同时能检出2位错码。 2、设某(n ,k )线性分组码的生成矩阵为： 001011100101010110G ?? ??=?????? ①试确定该(n ,k )码中的n 和k ； ②试求该码的典型监督矩阵H ； ③试写出该码的监督方程； ④试列出该码的所有码字； ⑤试列出该码的错误图样表； ⑥试确定该码的最小码距。 [解] ①由于生成矩阵G 是k 行n 列，所以k =3，n =6。 ②通过初等行变换，将生成矩阵G 变换成典型生成矩阵
[] 100101010110001011k G I Q ?? ??==?????? 由于101110110011011101T Q P Q ???? ????=???? ????????， ＝＝，可知典型监督矩阵为 []110100011010101001r H PI ?? ??=?? ????＝ ③监督方程为5424315 300 00 a a a a a a a a a ⊕⊕=??⊕⊕=??⊕⊕=? ④所有码字见下表 ⑤错误图样表即错误图样与校正子关系表，见下表
纠错输出编码（ECOC ）综述和基本原理 目录 <机器学习导论> (1) 《Solving Multiclass Learning Problems via Error-Correcting Output Codes 》 (2) A Subspace to ECOC (3) 中文参考文献 (5) <机器学习导论> 在纠错输出编码中，主要的分类任务通过由基学习器实现的一组子任务来定义。其思想是：将一个类从其他类区分开来的原始任务可能是一个困难的问题。作为替代，我们定义一组简单的分类问题，每个专注于原始任务的一个方面，并通过组合这些简单的分类器来得到最终的分类器。 这时，基分类器是输出为-1/+1的二元分类器，并且有一个K*L 的编码矩阵W ，其K 行是关于L 个基学习器dj 类的二元编码。例如，(2, )[ 1 1 1 1]M =-++-表示若一个样本属于第2类(C 2)，则该样本应在h 1和h 4上取负值，在h 2和h 3上取正值；(, 3)[ 1 1 1]T M =-++可理解为第三个基分类器h 3的任务是将属于C 1类的样本与属于C 2和C 3类的样本区分开。同时(, 3)M 也决定了如何构造基分类器h 3的训练样本集T 3：所有标记为C 2类及C 3类的样本形成正样本3χ+，而标记为C 1类的实例构成负样本3χ-，对h 3的训练应使得3T ?∈i x ，当3χ+∈i x 时，3()1h =+i x ；当3χ-∈i x 时，3()1h =-i x 。 这样，编码矩阵使得我们可以用二分类问题定义多分类问题，并且这是一种适用于任意可以实现二分基学习器的学习算法的方法，例如，线性或多层感知器，决策树或初始定义的两类问题的SVM 。 典型的每类一个判别式的情况对应于对角矩阵，其中L=K ，例如，对于K=4，我们有 W=【】 这里的问题是：如果某一个基学习器存在错误，就会有误分类，因为类的码
RS 基本概念 GF(2m )域 域在RS 编码理论中起着至关重要的作用。 简单点说域m GF(2)有m 2(设m 2= q )个符号 且具有以下性质： 域中的每个元素都可以用a 0，a 1，a 2，a m-1 的和来表示。除0、1外其余所有元素由本原多项式 P (x )生成。本原多项式的特性是得到的余式等于0。 在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行 在GF 域上的加、减、乘、除运算定义如下（GF(4 2)为例）： 1、 加、减运算均定义为元素的二进制表示方式进行异或运算。如：a 8 +a 10 ，先查表， 将其化为二进制表示方式得0101+0111，经过异或运算得0010，再查表得a 1，即：a 8+a 10= a 1 。 减运算与加运算相同，即：a 8-a 10= a 1 。 2、 乘运算定义为元素的指数相加后进行模15运算后所得的新元素，但若有一个元素 为0，则相乘结果为0。如：a 7*a 13，(7+13)mod 15=5，即a 7*a 13= a 5 。 3、 除运算定义为元素的指数相减后进行模15运算后所得的新元素(指数为正数)。若 被除数为0，则结果为0。如：a 5/a 9，(5-9)mod 15=11，即a 5/a 9= a 11 。 下面以一个较简单例子说明域的构造。 GF (42) 的所有元素 例：m=4,本原多项式 4p(x)=x +x+1求GF (4 2) 的所有元素： 因为α为p (x )的根得到4 ++1αα=0 或4 =+1αα (根据运算规则)
符号(n，k)RS GF(2)域中，符号(n，k)RS的含义如下： 在介绍之前需要说明一些符号。在4 m表示符号的大小，如m = 8表示符号由8位二进制数组成 n表示码块长度， k表示码块中的信息长度 K=n－k = 2t表示校验码的符号数 t表示能够纠正的错误数目 RS的编码算法 GF(2)域上的RS(15,11)码，码长n=15字符，码元长k=11本项目RS纠错算法选择在4 字符，码距d=5，纠错能力t=2字符，每字符为4bits，即一个码组合7.5字节。每11个有效字节加4个纠错字节。每一帧报文分成若干组，以11个字节为一组，对这11个字节作纠错，生成4字节里德-所罗门码纠错码，和前11个字节一起共15个字节构成纠错后的一组报文。一帧报文以每11个字节分组后，若最后一组字节数不满11个字节，剩余字节填77H，凑满11个字节再进行纠错。 对一个信息码符多项式，RS校验码生成多项式的一般形式为 (13－2) 式中，m0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)≥2t (t为要校正的错误符号数)。 x+a x+a x+a x+a 对于R（15，11）对应生成多项式为g(x)=413362310 信息码符多项式为
汉明码计算及其纠错原理详解 当计算机存储或移动数据时，可能会产生数据位错误，这时可以利用汉明码来检测并纠错，简单的说，汉明码是一个错误校验码码集，由Bell 实验室的R.W.Hamming 发明，因此定名为汉明码。 汉明码（Hamming Code），是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码，以侦测并更正单一比特错误。由于汉明编码简单，它们被广泛应用于内存（RAM ）。其SECDED （single error correction，double error detection）版本另外加入一检测比特，可以侦测两个或以下同时发生的比特错误，并能够更正单一比特的错误。因此，当发送端与接收端的比特样式的汉明距离（Hamming distance）小于或等于1时（仅有1 bit发生错误），可实现可靠的通信。相对的，简单的奇偶检验码除了不能纠正错误之外，也只能侦测出奇数个的错误。 在数学方面，汉明码是一种二元线性码。对于每一个整数，存在一个编码，带有个奇偶校验位个数据位。该奇偶检验矩阵的汉明码是通过列出所有米栏的长度是两两独立。 汉明码的定义和汉明码不等式：设：m=数据位数，k=校验位数为，n=总编码位数＝m+k，有Hamming不等式： a）总数据长度为N，如果每一位数据是否错误都要记录，就需要N位来存储。 b）每个校验位都可以表示：对或错；校验位共K位，共可表示2k种状态 c）总编码长度为N，所以包含某一位错和全对共N+1种状态。 d）所以2k≧N+1 e）数据表见下 无法实现2位或2位以上的纠错，Hamming码只能实现一位纠错。 以典型的4位数据编码为例，演示汉明码的工作 D8=1、D4=1、D2=0、D1=1， P1 =1，P2=0、P3=0。 汉明码处理的结果就是1010101 假设：D8出错，P3’P2’P1’=011=十进制的3，即表示编码后第三位出错，对照存储
基于纠错码的容错技术的研究 ——EVENODD码的设计与实现 论文作者姓名： 申请学位专业：网络工程申请学位类别：工学学士指导教师姓名（职称）： 论文提交日期：
基于纠错码的容错技术的研究 ——EVENODD码的设计与实现 摘要 由于网络技术的迅猛发展，存储系统的规模变得越来越庞大。因此它对系统的可靠性提出了严峻的挑战。而采用EVENODD编码算法的布局策略可以同时容许两个数据块同时出错，可以很好的保证系统的稳定性。它已经被广泛应用在RAID （Redundant Arrays of Independent Disks）等技术中。本论文从EVENODD 编码原理出发，详细介绍了EVENODD的编码和译码过程，以及从理论上对该译码的算法进行了分析证明，同时使用java编译技术实现了该编码过程的仿真。在本论文中还对该仿真软件的设计思路、开发过程、以及主要功能模块的实现都进行了详细的介绍。EVENODD码仿真软件的实现是理论运用于实际的又一典范。通过对其编码和译码核心算法的调用，可以实现图片、二进制文件等格式的备份和恢复。 关键词： EVENODD编码；容错技术；系统稳定性； java编译技术
Research of Fault Tolerance Technology based on Error Correcting Code ——The Design and Implementation of EVENODD Codes Abstract With the fast development of network technique, the scale of storage system becomes bigger and bigger. So, it is an austere challenge to the system. But the data placement strategy of EVENODD which has the ability to simultaneously correct two error data blocks can ensure the stability of the system. It has been extensively used in the RAID( Redundant Arrays of Independent Disks) technology. In the thesis encoding and decoding algorithms of EVENODD codes are introduced. Moreover decoding algorithms are analyzed and proven. At the same time, the software of EVENODD emulator is developed by java technology .The idea of design, the process of development and the design of main function blocks are proposed. It is an apotheosis which uses theory in the real world. Pictures and binary files can be backed up and recovered by EVENODD codes. Key words:EVENODD; Fault-tolerant; Stability of system; Java technology
实验九 (2,1,5）卷积码编码译码技术 一、实验目的 1、掌握(2,1,5）卷积码编码译码技术 2、了解纠错编码原理。 二、实验内容 1、(2,1,5）卷积码编码。 2、(2,1,5）卷积码译码。 三、预备知识 1、纠错编码原理。 2、(2,1,5）卷积码的工作原理。 四、实验原理 卷积码是将发送的信息序列通过一个线性的，有限状态的移位寄存器而产生的编码。通常卷积码的编码器由K级（每级K比特）的移位寄存器和n个线性代数函数发生器（这里是模2加法器）组成。 若以（n,k,m）来描述卷积码，其中k为每次输入到卷积编码器的bit数，n 为每个k元组码字对应的卷积码输出n元组码字，m为编码存储度，也就是卷积编码器的k元组的级数，称m+1= K为编码约束度m称为约束长度。卷积码将k 元组输入码元编成n元组输出码元，但k和n通常很小，特别适合以串行形式进行传输，时延小。与分组码不同，卷积码编码生成的n元组元不仅与当前输入的k元组有关，还与前面m-1个输入的k元组有关，编码过程中互相关联的码元个数为n*m。卷积码的纠错性能随m的增加而增大，而差错率随N的增加而指数下降。在编码器复杂性相同的情况下，卷积码的性能优于分组码。 编码器 随着信息序列不断输入，编码器就不断从一个状态转移到另一个状态并同时输出相应的码序列，所以图3所示状态图可以简单直观的描述编码器的编码过程。因此通过状态图很容易给出输入信息序列的编码结果，假定输入序列为110100，首先从零状态开始即图示a状态，由于输入信息为“1”，所以下一状态为b并输出“11”，继续输入信息“1”，由图知下一状态为d、输出“01”……其它输入信息依次类推，按照状态转移路径a->b->d->c->b->c->a输出其对应的编码结果“110101001011”。 译码方法 ⒈代数 代数译码是将卷积码的一个编码约束长度的码段看作是[n0(m+1），k0(m+1)]线性分组码，每次根据（m+1）分支长接收数字，对相应的最早的那个分支上的信息数字进行估计，然后向前推进一个分支。上例中信息序列 =(10111），相应的码序列 c=(11100001100111）。若接收序列R=(10100001110111），先根据R 的前三个分支（101000）和码树中前三个分支长的所有可能的 8条路径(000000…）、（000011…）、（001110…）、（001101…）、（111011…）、（111000…）、（110101…）和（110110…）进行比较，可知（111001）与接收
纠错编码技术的研究 xxxxx 指导教师：xxxxx 1 引言 在移动无线信道中由于无线电波传输不仅会随着传播距离的增加而造成能量损耗，并且会因为多种不利因素的影响而使信号快速衰落，码间干扰和信号失真严重，从而极大地影响了通信质量。 鉴于这些问题的存在，我们不断地研究和寻找多种先进的通信技术以提高移动通信的性能。信道编码的最终目的是提高信号传输的可靠性，而纠错编码正是作为提高传输可靠性的最主要措施之一。本文将主要关注几种重要的纠错编码技术以及它们在实际当中的应用，以展示纠错编码在现代数字通信中的是如何提高通信质量的。 2 纠错编码简介 2．1 纠错码原理 用于检测的信道编码被称作检错编码，而既可检错又可纠错的信道编码被称作纠错编码。但现在，无论是具有检错功能还是纠错功能的编码，我们都统称为纠错编码。可见纠错编码的范围已经扩大了。 纠错编码，就像它的字面解释的那样，是当消息经过有噪信道传输或要恢复储存的数据时用来纠错的。因为纠错编码试图克服和恢复信道中噪声或其他因素造成的损害，其编码过程又称为信道编码。 纠错码的基本思想是在消息通过一个有噪信道伟输前以多余符号的形式在消息中增添冗余度，这种冗余度是在控制下添加的。编码后的消息在传输时可能还会遭到信道中噪声的损害。在接收端，如果错误数在该码所设计的限度内，原始消息可以从受损的消息中恢复。图1显示了数字通信系统的框图。注意图中最重要的部分就是噪声部分，如果没有了它就用不着信道编码器了。
图1 数字通信系统框图 一种编码的纠检错能力决定于最小码距d 0的值。下面用几何关系来说明纠/检错 能力和最小码距的关系，有三种情况[10]。 （1） 检错e 个错码，则要求： 10+≥e d （1） 上式表明，若一种编码的最小码距为d0，则它能检测出（d0-1）个错码；反之，若要求检测e 个错码，则d0应小于（e+1）。 （2） 纠正t 个错码，则要求： 120+≥t d （2） （3） 为了能纠正t 个错码，同时检测e 个错码，则要求： 10++≥e t d （3） 这种情况是纠错和检错结合的工作方式，在这种情况下，当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统就按反馈重发的纠错方式工作，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。 2．2 纠错编码的优缺点 由纠错编码原理，我们知道为了减少错码，需要在信息码元序列中加入监督码元。但这样做的结果是：序列增长，冗余度增大。在这种情况下，我们只能增大系统的带宽来解决问题，但另一方面，系统带宽的增大又会引起系统中噪声功率增大，
实验四纠错码Hamming码编译码 一、实验原理 差错控制编码的基本作法是：在发送端被传输的信息序列上附加一些监督码元，这些多余的码元与信息之间以某种确定的规则建立校验关系。接收端按照既定的规则检验信息码元与监督码元之间的关系，一旦传输过程中发生差错，则信息码元与监督码元之间的校验关系将受到破坏，从而可以发现错误，乃至纠正错误。 通信原理综合实验系统中的纠错码系统采用汉明码（7，4）。所谓汉明码是能纠正单个错误的线性分组码。它有以下特点： 码长n=2m-1 最小码距d=3 信息码位k=2n-m-1 纠错能力t=1 监督码位r=n-k 这里m位≥2的正整数，给定m后，既可构造出具体的汉明码（n，k）。 汉明码的监督矩阵有n列m行，它的n列分别由除了全0之外的m位码组构成，每个码组只在某列中出现一次。系统中的监督矩阵如下图所示： 1110100 H=0111010 1101001 其相应的生成矩阵为： 1000101 0100111 G= 0010110 0001011 汉明译码的方法，可以采用计算校正子，然后确定错误图样并加以纠正的方法。 表3.4.1 （7，4）汉明编码输入数据与监督码元生成表
二、实验仪器 1、1 JH5001通信原理综合实验系统一台 2、20MHz双踪示波器一台 三、实验目的 1、通过纠错编解码实验，加深对纠错编解码理论的理解； 四、实验内容 准备工作 （1）将汉明编码模块内工作方式选择开关SWC01中，编码使能开关插入（H_EN）；； 设置m序列方式为（M_SEL1拔除、M_SEL0接入），此时m序列输出为全1码。 （2）将汉明译码模块内输入信号和时钟选择开关KW01、KW02设置在（右端），输入信号直接来自汉明编码模块；将译码器使能开关KW03设置在工作位置0N（左端）。 1.编码规则验证 （1）用示波器同时观测编码输入信号TPC03波形和编码输出波形TPC05，观测是否符合汉明编码规则（参见表3.4.1所示）。 （2）设置m序列方式为（10：M_SEL1插入、M_SEL0拔下），此时m序列输出为16进制码0000~1111（参见表3.4.2所示）。通过接入M-PAUSE跳线，选择某一静态 码。用示波器同时观测编码输入信号TPC01波形和编码输出波形TPC05，观测时 以TPC01同步，观测是否符合汉明编码规则。 （3）设置其它m序列方式，重复上述测量步骤。 注：m序列周期因非4bit的倍数，所以输入的4bit数据为其周期内的某一段截取码字。 2.译码数据输出测量 （1）用示波器同时观测汉明编码模块的编码输入信号TPC03波形和汉明译码模块译码输出m序列波形TPW06，测量译码输出数据与发端信号是否保持一致，以及 延时。 （2）设置不同的m序列方式，重复上述实验，验证汉明编译码的正确性。
第二节 纠错编码原理 一、纠错编码的原理 一般来讲，信源发出的消息均可用二进制信号来表示。例如，要传送的消息为A 和B ，则我们可以用1表示A ，0表示B 。在信道传输后产生了误码，0错为1，或1错为0，但接收端却无法判断这种错误，因此这种码没有任何抗干扰能力。如果在0或1的后面加上一位监督位（也称校验位），如以00表示A ，11表示B 。长度为2的二进制序列共有种组合，即00、01、10、11。00和11是从这四种组合中选出来的，称其为许用码组，01、10为禁用码。当干扰只使其中一位发生错误，例如00变成了01或10，接收端的译码器就认为是错码，但这时接收端不能判断是哪一位发生了错误，因为信息码11也可能变为01或10，因而不能自动纠错。如果在传输中两位码发生了错误，例如由00变成了11，译码器会将它判为B ，造成差错，所以这种1位信息位，一位监督位的编码方式，只能发现一位错误码。 224=按照这种思路，使码的长度再增加，用000表示A ，111表示B ，这样势必会增强码的抗干扰能力。长度为3的二进制序列，共有8中组合：000、001、010、011、100、101、110、111。这8种组合中有三种编码方案：第一种是把8种组合都作为码字，可以表示8种不同的信息，显然，这种编码在传输中若发生一位或多位错误时，都使一个许用码组变成另一个许用码组，因而接收端无法发现错误，这种编码方案没有抗干扰能力；第二种方案是只选四种组合作为信息码字来传送信息，例如：000、011、101、110，其他4种组合作为禁用码，虽然只能传送4种不同的信息，但接收端有可能发现码组中的一位错误。例如，若000中错了一位，变为100，或001或010，而这3种码为禁用码组。接收端收到禁用码组时，就认为发现了错码，但不能确定错码的位置，若想能纠正错误就还要增加码的长度。第三种方案中规定许用码组为000和111两个，这时能检测两位以下的错误，或能纠正一位错码。例如，在收到禁用码组100时，若当作仅有一位错码，则可判断出该错码发生在“1”的位置，从而纠正为000，即这种编码可以纠正一位差错。但若假定错码数不超出两位，则存在两种可能性，000错一位及111错两位都可能变为100，因而只能检错而不能纠错。 从上面的例子可以得到关于“分组码”的一般概念。如果不要求检错或纠错，为了传输两种不同的信息，只用1位码就够了，我们把代表所传信息的这位码称为信息位。若使用了2位码或3位码，多增加的码位数称为监督位。我们把每组信息码附加若干监督码的编码称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。 图8-2分组码的结构 分组码一般用符号(表示， 其中k 是每组码中信息码元的数目，n 是码组的总位数，又称为码组的长度（码长），为每码组中的监督码元数目，或称为监督位数目。通常将分组码规定为如图8-2所示的结构，图中前面位为信息位，后面附 )n n a a ??,n k n k r ?=k 12(,,...,)r a
在通信系统中,为提高信息传输可靠性,广泛使用了具有一定纠错能力的信道编码技术, 如奇偶校验码、行列监督码、恒比码、汉明码、循环码(CRC)等编码技术。这些编码技术因 其编码方式比较简单,其检错、纠错能力都不是很强,无法满足数字通信系统中高可靠传输的性能要求,必须采用高性能的强纠错编码技术。 下面介绍几种高性能强纠错编码技术： 1里德- 索罗门码(Read - Solomon) 里德-索罗门码,简称RS码,是一种重要的线性分组编码方式,对突发性错误有较强的纠错能力。该编码技术是利用伽罗华创造的伽罗华域(Galois Field)中的数学关系来把传送数据包的每个 字节映射成伽罗华域中的一个元素(又称符号) ,每个数据包都按码生成多项式为若干个字节 的监督校验字节,组成RS的误码保护包,接收端则按校验矩阵来校验接收到的误码保护包是 否有错,有错时则在错误允许的范围内纠错。RS纠错编码具有很强的纠正突发误码的能力。为了纠正一个错误,要2个符号的检测码,一个用来确定位置,一个用来纠错。一般来说纠t个错误需要2t个检验符,这时要计算2t个等式,确定t个位置和纠t个错。能纠t个符号的RS 码生成多项式为: g ( x) = ( x + a0 ) ( x + a1 ) ( x + a2) …( x + a2t - 1 ) 。 2卷积码(Convolution codes) 卷积码是一种非分组编码,适用于前向纠错法。在许多实际情况下,卷积码的性能常优于分组式编码。卷积编码是将信息序列以k个码元分段,通过编码器输出长为n的一个码段。卷积 码的监督码元并不实行分组监督,每一个监督码元都要对前后的信息单元起监督作用,整个编解码过程也是一环扣一环,连锁地进行下去。卷积编码后的n个码元不仅与本段的信息元有关,而且也与其前N - 1段信息有关,故也称连环码,编码过程中互相关联的码元个数为nN。卷积编码的结构是:“信息码元、监督码元、信息码元、监督码元…”。在解码过程中,首先将接收到的信息码与监督码分离,由接收到的信息码再生监督码,这个过程与编码器相同;再将此再 生监督码与接收到的监督码比较,判断有无差错,并纠正这些差错。 3交织编码 交织编码,其基本思路是将i个能纠t个错的分组码( n, k)中的码元比特排列成i行n列的方阵,每个码元比特记作B ( i, n) 。交织前如果遇到连续j个比特的突发错误,且j >> t,对其中的连续2个码组而言,错误数已远远大于纠错能力t,因而无法正确对出错码组进行纠错。交织后, 总的比特数不变,传输次序由原来的B (1, 1) , B (1, 2) , B (1, 3). . . B (1, n) , B (2, 1) , B (2, 2) , B (2, 3). . . B (2,n) , . . . . . . B ( i, 1) , B ( i, 2) , B ( i, 3). . . B ( i, n)转变为B (1, 1) , B (2, 1) , B (3, 1). . . B ( i, 1) , B (1, 2) , B (2, 2) , B(3, 2). . . B ( i, 2). . . . . . . . . B (1, n) , B (2, n) , B (3, n) , . . . B ( i, n)的次序。此时因干扰或衰落引起的突发错误图样正好落在分组码的纠错能力范围内,可以正确纠正这些 被分解开的差错。通常把码组数i称为交织度,用这种方法构造的码称为交织码。 使用交织编码的好处是提高了纠正突发错误的能力但又不增加新的监督码元,从而不会降低 编码效率。理论上交织度i越大,抗突发错误的能力就越强。 4格状编码调制