差错控制编码

会计学1差错控制编码2023年1月18日28.1差错控制编码的基本概念数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字通信的有效性，以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。数字信号在传输的过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。第1页/共48页2023年1月18日3差错控制编码的基本思想：在发送端根据要传输的数字序列（信息码元）按一定的规律加入多余码元，使原来不相关的数字序列变为相关，然后把这些多余码元和有关的信息码元一起传送，接收端根据信息码元与多余码元之间的相关规则进行检验，从而发现错误。这时，或者通过反馈信道要求对方重发有错的信息，以进行纠错；或者由接收端的译码器自动把错误纠正。这些多余码元称为校验元或监督元。它的加入不改变信息本身，也就是说，它不传送新的信息，它的作用只是使信道译码器能够检测和纠正差错，从而控制系统差错概率，提高可靠性但这是以系统的有效性为代价的。第2页/共48页2023年1月18日48.1.1差错控制方式第3页/共48页2023年1月18日5前向纠错方式前向纠错方式记作FEC（ForwordErrorCorrection）发端编码器将数字信息按一定规则附加多余码元，组成有纠错能力的码，发端发送能够纠正错误的码；收端译码器按预先规定的规则译码；若发现错误，确定其出错位置并进行纠正。优点：单向传输，只有正向信道；适合于只能提供单向信道的场合；一点发送多点接收的同播方式；译码延迟固定，适用于实时传输系统。缺点：编译码设备复杂，为了纠正较多的错误，需要附加的多余码元较多，因而传输效率较低。第4页/共48页2023年1月18日6检错重发方式又称自动请求重传方式，记作ARQ（AutomaticRepeatRequest）。发端编码器将数字信息按一定规则附加多余码元，使之具有一定的检错能力，收端译码器按一定规则对数据码元组进行错误判决，并把判决结果形成应答信号，通过反馈信道回送到发端，发端根据收到的应答信号，把收端认为有错的那组数据码元再次重传，直到码元组无错为止。优点：只需要少量的多余码元就能获得极低的输出误码率，并且其成本和复杂性均比前向纠错低缺点。缺点：必须提供反向信道；不能进行同播（一点发多点收），收发端应有缓冲存储器和控制器；此外当信道干扰较大时，整个系统可能处在重传循环中，因而通信效率降低，信息传输连贯性差，不适于实时传输系统，主要在计算机通信中应用。常用的检错重发系统有三种，即停发等候重发、返回重发和选择重发。第5页/共48页第6页/共48页2023年1月18日8混合纠错方式混合纠错方式记作HEC（HybridErrorCorrection）发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此，近年来得到广泛应用。在实际通信系统中，选择那种差错控制方式，要视具体情况而定，可以根据信源的性质，信息传输的特点信道干扰的种类和对误码率的要求而适当选择差错控制方式。第7页/共48页2023年1月18日98.1.2差错控制编码的分类根据信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。

根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。第8页/共48页2023年1月18日108.1.3几种简单的检错码(1)奇偶监督码设码字A=［an-1,an-2,…,a1,a0］，对偶监督码有：an-1⊕

an-2⊕…⊕

a1⊕

a0=0奇监督码情况相似，只是码组中“1”的数目为奇数，即满足条件：an-1⊕

an-2⊕…⊕

a1⊕

a0=1而检错能力与偶监督码相同。第9页/共48页2023年1月18日11奇偶监督码编码方法：把信息码元分组，在每组信息码元的后面附加一位监督码元，使得码组中1的数目为奇数或偶数即可编码规则：码组长度n；信息位n-1特点：是一种能发现奇数个差错的分组码；n较大，即编码码组较长时，编码效率接近于1;（n-1）/n

——

信息码元比码组码元适用于检测随机的零星错码——加性白噪声造成的第10页/共48页2023年1月18日128.1.3几种简单的检错码(2)二维奇偶监督码(6,11)行列监督码第11页/共48页2023年1月18日13二维奇偶监督码编码方法：把码元排成方阵，按行列进行奇偶校验

——分别附加一位监督码元特点：不仅可检测每行（每列）中奇数个错误，而且可通过水平监督和垂直监督来确定错码的位置纠正仅一行（一列）出现的奇数个错误通过水平监督和垂直监督的关系可以发现单行中出现的偶数个错误；但不能发现构成矩形的4个错误码元适用于突发差错——由突发干扰（突发脉冲，如：闪电，电火花等）在短时间内错码成串出现，在某一行中出现多个错码第12页/共48页2023年1月18日148.1.3几种简单的检错码(3)重复码在每位信息码元之后，用简单重复多次的方法编码。例：重复两次时，用111传输1码，用000传输0码

编码方法：每位信息码元简单重复多次；收端译码采用多数表决法；例：重复2次特点：纠正1个错，检出2个错第13页/共48页2023年1月18日158.1.3几种简单的检错码(4)恒比码码字中1的数目与0的数目保持恒定比例的码称为恒比码。这种码在检测时，只要计算接收码元中1的数目是否正确，就知道有无错误。

第14页/共48页2023年1月18日16恒比码例：5中取3恒比码——用于电报电码每个码组长度为5，共有25=32种不同的码组，其中有3个1的码组为可用码组，共有10种——表示10个阿拉伯数字，用它拼成汉字（每4阿拉伯数字组成1个汉字电码）；其余的22个为禁用码组。特点：简单；除了1错为0与0错为1成对出现（对换性）差错不能检测外，其它任何奇数个或偶数个错码都可以被检测出来。只适用于传输种类较少且有固定代码的字符，而不适用于表示由信源来的二进制随机，数字序列。第15页/共48页2023年1月18日178.1.3几种简单的检错码(4)ISBN国际统一图书编号例ISBN0－471－02977－7第16页/共48页2023年1月18日188.1.4检错和纠错的基本原理如用三位二进制编码来代表八个字母

000A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位发生错误，都会使传输字母错误如用三位字母传四个字母000A 011 B 101 C 110 D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。如果进一步将许用码组限制为两种000A111B－检错和纠错能力是用信息量的冗余度来换取的。第17页/共48页2023年1月18日19检错和纠错的基本原理检错和纠错能力是用信息量的冗余度换取的——与码组之间的差别有关；不同的编码方法和形式，检错和纠错能力不同。例：n=3，共有8种组合，都用于传输消息，在传输过程中若发生一个误码，则一种码组就会错误地变成另一种码组，但接收端却不能发现错误，因为任何一个码组都是许用码组。第18页/共48页

在差错控制编码中，定义码组中非零码元的数目为码字的汉明(Hamming)重量，简称码重。例如，码字10110，码重w=3。定义两个等长码组之间相应位取值不同的数目为这两个码组的汉明(Hamming)距离，简称码距。例如11000与10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用dmin表示。最小码距是码的一个重要参数，它是衡量码检错、纠错能力的依据。第19页/共48页2023年1月18日21最小码距与检错纠错能力的关系

码组内的距离反映了码组之间的差别，最小距离越大，说明两个码组间的最小差别越大，或者说其中一个码组错为另一个码组的可能性就越小，那么其检错和纠错能力也就越强，因此可以说最小码距是衡量一种纠错编码的检错，纠错能力大小的标准。第20页/共48页

码的最小距离直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内:(1)检测e个随机错误，则要求码的最小距离dmin≥e+1;(2)纠正t个随机错误，则要求码的最小距离dmin≥2t+1;(3)纠正t个同时检测e(≥t)个随机错误，则要求码的最小距离dmin≥t+e+1。t1eAB第21页/共48页2023年1月18日23用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:Rc=k/n其中,k是信息元的个数，n为码长。对纠错码的基本要求是:检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。编码效率第22页/共48页2023年1月18日248.2线性分组码线性分组码的构成将信息序列划分为等长(k位)的序列段共有2k个不同的序列段，在每一信息段之后，附加m位监督元，构成长度n=k+m的分组码(n，k)监督元与信息码元为线性关系第23页/共48页2023年1月18日25例信息元长度k=3共有2k=8个不同的信息组每组信息组加4个监督元，构成一个长度为7的(7，3)线性分组码。设：每组信息元为C1C2C3监督元为C4C5C6C7根据下列线性方程组求监督元C4=C1+C3C5=C1+C2+C3C6=C1+C2C7=C2+C3第24页/共48页2023年1月18日26例

(7，3)码有8个信息组，信息组按上方程组求得每个信息组的4个监督元，得到(7，3)码的所有8个码字信息组码元00000000000010011101010010011101101110101001001110101101001111011010011111110100重要特性，线性码有封闭性

第25页/共48页2023年1月18日278.2线性分组码设分组码由n位码组构成，记为c1，c2，…，cn，信息码组由k位码组成，记为d1，d2，…，dk。则该分组码记为（n，k）码。码组和信息码组可用行矩阵C和D表示若为线性分组码，C中的n个元素都是由D中的k个元素经线性组合形成的。可用一联立方程表示为第26页/共48页将码组C写成矩阵形式矩阵G称为生成矩阵，它是一个k×n的矩阵第27页/共48页2023年1月18日29生成矩阵G第28页/共48页2023年1月18日30生成矩阵GIk

单位矩阵，k行k列(kxk阶)P矩阵，k行m列(kxm阶)编码前k位，编码后有n位，2n>2k；选择P矩阵，可得到有较强检错纠错能力，实现方法尽可能简单，编码效率又高的线性分组码由于线性码具有封闭性，故任何二个码组之间的距离必须与某一个码组中“1”的个数相等，而码组中非零码元的数目“1”的个数为码组的重量（码重）所以线性码任意二个码字之间的距离必须等于码中某一个码字的重量——线性码最小码距正好等于非零码的最小码重估算线性码的差错控制能力：求最小码距——最小码重第29页/共48页2023年1月18日31例已知（6，3）码的生成距阵，求：编码码组第30页/共48页2023年1月18日32监督矩阵H校验矩阵或监督矩阵H：mxn阶PT:m行k列

k+m=n列第31页/共48页2023年1月18日33伴随式（校正子）S

设发送码组C=［cn-1,cn-2,…,c1,c0］，在传输过程中可能发生误码。接收码组R=［rn-1,rn-2,…,r1,r0］，则收发码组之差定义为错误图样E，也称为误差矢量，即E=R–C=［en-1,en-2,…,e1,e0］，且

当ri=ci

当ri≠ci

令S=RHT，称为伴随式或校正子

S=RHT=CHT⊕

EHT=EHT

S只与错误图形有关，与发送的码组C无关

HT

：nxm阶；E：1xn阶；S：1xm阶；S=[s1s2

……sm]

解得误差矢量E，求得纠错后的码组C=R⊕E第32页/共48页2023年1月18日34检错与纠错检错：当码组出现错误S为非零矢量纠错：

S=RHT=CHT⊕EHT=EHT

S与E之间有着确定的线性关系——由H矩阵确定（也就是与G（P）矩阵有关）S=[s1s2

……sm]共有2m种不同的形式，除全0外，可代表2m-1种有错误的图形信息码组有2k个错误图形，有多种不同的形式可能有2k种解答；为了选择正确的结果，要使用最大似然比准则，选择与R最相似的C（与R距离最小的码组——E是1码最小的矢量）。第33页/共48页2023年1月18日35例：（6，3）码第34页/共48页2023年1月18日36S与E对照表ES

000000000100000101010000011001000110000100100000010010000001001100010111

（6，3）码具有纠1位错的能力发生1个错误的情况：

S是HT的第i行，说明R中第i位产生了错误，可以把它纠正发生2个错误的情况：除S=111对应第1，5位有错其它的双错不能得到纠正

例：

接收码组R[111011]

第35页/共48页2023年1月18日37查表法译码器的原理S=RHT=CHT⊕EHT=EHT算出伴随式S与最小码重的差错矢量E的对照表，提供译码使用第36页/共48页2023年1月18日38汉明码按上述方法构造的能纠正单个错误的线性分组码称为汉明码。对于线性分组码，为了指示所有单错位置和无错的情况，必须满足不等式汉明码具有以下特点：汉明码的编码效率第37页/共48页2023年1月18日39汉明界如果码组有纠t个差错的能力，则应能指出无错、单错到t个差错所有可能的情况，校验位数m应满足不等式：－汉明界，是纠正t个差错的一个必要条件第38页/共48页2023年1月18日408.3循环码特点线性分组码循环性——任一许用码字经过循环移位后，得到的码组仍为一个许用码组如是循环码的一许用码组则也是一许用码组移位i次得到也是许用码组第39页/共48页2023年1月18日418.3.1循环码的特点及表达码多项式表示以此类推，码组C移位i次，相应的码多项式c(i)(x)是xi·c(x)除以（xn+1)后的余式。在模（xn+1)意义下，若c(x)是码多项式，则xic(x)都是码多项式。第40页/共48页2023年1月18日42循环码的编码过程一个k位的信息码组可用信息多项式表示假设码组多项式可表示为如果(χn+1)是g(χ)的倍式C（1）(χ)=χd(χ)g(χ)+aC1g(χ)=[χd(χ)+aC1]g(χ)=d1(χ)g(χ)d1(χ)对应某个信息码组第41页/共48页2023年1月18日43生成多项式g(χ)

(χn+1)是g(χ)的倍式，且g(χ)为n-k次多项式，所以对(χn+1)进行因式分解，便可得到相应的g(χ)。对(χn+1)进行因式分解可由计算机完成，有表格给出。由信息多项式求解码多项式

C(χ)=d(χ)g(χ)

n-1次k-1次n-k次第42页/共48页2023年1月18日44例(7，4)——n=7

k=4

m=n-k=3g(χ)应为(χ7+1

)的3次因式χ７

+1=(χ+1)(χ３+

χ+1)(χ３+

χ２+1)g1(χ)=(χ３+

χ+1)g2(χ)=(χ３+

χ２+1)D=[1010]——d(χ)=(χ３+

χ)C1(χ)=d(χ)g1(χ)=(χ３+

χ)(χ３+

χ+1)

=χ６+

χ３+

χ２+

χ

——

C1=[1001110]C2(χ)=d(χ)g2(χ)=(χ３+

χ)(χ３+

χ２+1)

=χ６+

χ５+

χ４+

χ

——

C２

=[1110010]注：

1.不同的生成多项式得到不同的码组

2.由此编码法得到的不是系统码（前4位不是D=[1010]）