第六章 信道编码

第6章信道编码信息论与编码信道模型1．离散信道的数学模型根据信道的统计特性即条件概率P(y|x)的不同，离散信道可以分为三种情况：（1）无干扰信道（2）有干扰无记忆信道（3）有干扰有记忆信道信道有关概念回顾YX信道输入信号输出信号图6.1离散信道模型

条件概率反映信道的统计特性

2．单符号离散信道的数学模型单符号离散信道的输入变量为X，取值于{a1,a2,…,ar}，输出变量为Y，取值于{b1,b2,…,bs}，并有条件概率(信道的传递概率)：P(y|x)=

P(y=bj|x=ai)=

P(bj

|ai)(i=1,2,···,r；j=1,2,···,s)模型：P(bj

|ai)图6.2单符号离散信道一般离散单符号信道的传递概率可用以下形式的矩阵来表示(信道转移概率)：

并满足式。

…………b1b2

···bsP(b1|a1)P(b2|a1)···P(bs|a1)P(b1|a2)P(b1|a2)···P(bs|a2)P(b1|a2)P(b1|a2)···P(bs|a2)a1

a2a3定义6.1

已知发送符号ai

，通过信道传输接收到的符号为bj

的概率P(bj|ai)称为前向概率。已知信道输出端接收到的符号为bj，而发送符号为ai

的概率P(ai|bj)称为后向概率。有时，也把P(ai)称为输入符号的先验概率(即在接收到一个输出符号以前输入符号的概率)，而对应地把P(ai|bj)称为输入符号的后验概率(即在接收到一个输出符号以后输入符号的概率)

。信道疑义度和平均互信息1.先验熵信道输入信号X的熵H(X)是在接收到输出Y以前，关于输入X的先验不确定的度量，称为先验熵。如果信道中无干扰（噪声），接收到传送过来的符号后就消除了对发送符号的先验不确定性。但一般信道中有干扰存在，接收到输出Y对发送的是什么符号仍有不确定性。2.信道疑义度(条件熵)信息疑义度表示在输出端收到输出变量Y的符号后，对于输入端的变量X

尚存在的平均不确定性(即存在疑义)。这个对X尚存在的不确定性是由干扰(噪声)引起的。如果是一一对应信道，那么接收到输出Y后，对X的不确定性将完全消除，则信道疑义度H(X|Y)=0。3.

平均互信息定义6.3称I(X;Y)=H(X)-H(X|Y)为X

和Y

之间的平均互信息。平均互信息表示接收到输出符号Y后平均每个符号获得的关于输入变量X的信息量。经过推算得出：

其中X是输入随机变量，Y是输出随机变量平均互信息用于表示传输信息率。信道编码定理：若有一离散无记忆平稳信道，其容量为C，输入序列长度为L，只要待传送的信息率R<C，总可以找到一种编码，当L足够长时，译码差错概率Pe<ε，ε为任意大于零的正数。反之，当R>C时，任何编码的Pe必大于零，当L→∞，Pe→1。信道编码定理说明：同无失真信源编码定理类似，信道编码定理也是一个理想编码的存在性定理。它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可几乎无失真地把信息传送过去，否则就会产生失真。在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。§6.1信道编码的概念§6.1.1信道编码的作用和分类信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号－－线路编码如何避免少量差错信号对信息内容的影响－－纠错编码广义信道编码=特定信道上传输信息而进行的传输信号或信号格式的设计与实现广义信道编码有如下分类:描述编码

用于对特定数据信号的描述约束编码用于对特定信号特性的约束扩频编码用于扩展信号频谱为近似白噪声谱并满足某些相关特性

纠错编码用于检测与纠正信号传输过程中因噪声干扰导致的差错1234所有频率具有相同能量的随机噪声称为白噪声信号的频谱一般是针对确定性信号而言,它描述了信号在各个频率上的分布大小。

消息信道编码

编码信道

信道译码

码字接收向量消息编码信道模型§6.1.2编码信道

当码字c和接受向量R均由二元序列表时，称编码信道为二进制信道.

c=(c0,c1,…cn-1)如果对于任意的n都有：

p(r/c)=∏p(ri/ci)则称此二进制信道为无记忆二进制信道。

p(0/1)=p(1/0)=pb则称此信道为无记忆二进制对称信道，简称BSC.错误传输概率一样BSC转移概率BSC编码信道BSC输入输出关系等效为e=1表示差错,e=0表示正确差错图案：指n长的随机序列e=(e0,e1,…,en-1).

称e=(e0,e1,…,en-1)中ei=1为第i位上的一个随机错误.

第i至第j位之间有很多错误时,称为一个j-i+1长的突发错误.发送序列c:(1111011000)接收序列的r:(0110010110)比较c和r，可写出另一个序列e：1001001110r=c+e(mod2)或e=r+c(mod2)如:对于一个BSC信道总有转移概率1/2，比特传输中发生差错数目越少，概率越大，即

从而总认为发生差错的图案是差错数目较少的图案(概率大的事件发生,可以利用此进行纠错)

二元软判决信道

用多个比特（理想情况下为实数）表示每一个无记忆编码信道的二元符号输出,此时的二元无记忆编码信道,称为二元软判决信道.

信道干扰z为零均值正态分布的随机变量，噪声干扰功率为均方差，z的概率分布为。对于BPSK调制，二元输入符号为二元符号取值为+1或-1.6.1.3检错与纠错的基本原理为了使原信息能正确地传送到接收方，可以在信息传送前进行一次抗干扰编码(即检错编码与纠错编码)，再传送抗干扰编码后的数字信息。检纠错是根据信道输出序列r来判断是否可能是发送的c，或纠正导致r不等c的错误。冗余编码：为了实现检纠错,所以码字c的长度n一定大于消息m的长度k。纠错编码编码码率R

：每个码字的序列符号（或码元）平均传送的消息比特数,称为编码码率:对检纠错码的基本要求是:检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。

例6.1

偶（或奇）校验方法：实现检纠错目的的一个基本方法。一个偶校验位p是对消息m使得如下校验方程成立的二进制符号，即:

称c=[m0,m1,…,mk-1,p]一个偶校验码码字,所有可能的c的全体C称为一个码率为

k/(k+1)的(k+1,k)的偶校验码.下面介绍两个简单的检错编码的例子:或:也就是说:如果是偶校验码，在附加上一个校验位以后，码长为n的码字中“1”的个数为偶数个;如果是奇校验码，在附加上一个校验位以后，码长为n的码字中“1”的个数为奇数个.

编码可以产生多个奇偶校验位，即一个校验位可以由消息位的部分或全部按某种校验方程产生，例如对阵列消息进行垂直与水平校验以及总校验的码字c和其码率分别为:为了增强校验能力编码码率:如:110010100001000011010111100001100111000010101010100010111000111100例6.2重复消息位：

在发送端把消息重复发几遍，可使接收端接收消息时错误减少，从而提高通信的可靠性。如：在二元对称信道中，当发送符号0时，不是只发一个0而是连续发三个0；同样，发送符号1时也连续发送三个1。于是信道输入端有两个码字000和111。一个(n,k)重复码是一个码率为1/n的码，仅有两个码字c0和c1,传送1比特（k=1）消息。

n重复码可以检测出任意小于n个差错的错误图案，纠正任意小于[n/2]个差错的错误图案。纠[n/2]=1位差错的3重复码,关于这点,下面再说.例6.3

恒比码方法：

码字中1的数目与0的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码。这种码在检测时，只要计算接收码元中1的数目是否正确，就知道有无错误。

目前我国电传通信中普遍采用3∶2码，又称“5中取3”的恒比码，即每个码组的长度为5，其中3个“1”。这时可能编成的不同码组数目等于从5中取3的组合数10，这10个许用码组恰好可表示10个阿拉伯数字(0-9)，在汉字电报码中,每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。

表10-13∶2恒比码5:3恒比码5中取3等重码可以检测出全部奇数位差错，因为只要奇数位有错,1的个数就不为3;对某些码字的传输则可以检测出部分偶数位差错n:m的码率为:二进制位数,即需要的最大信息位数.6.1.4差错控制方式

和能力图10-1差错控制方式

差错控制方式

1.检错重发方式

检错重发又称自动请求重传方式，记作ARQ(AutomaticRepeatRequest)。由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效，但实时性差，主要在计算机数据通信中得到应用。2.前向纠错方式

前向纠错方式记作FEC(ForwordErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。

3.混合纠错方式

混合纠错方式记作HEC(HybridErrorCorrection)是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力，但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此，近年来得到广泛应用。

另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道，错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。先给出汉明距离的概念:定义:

设X=(x1,x2,…,xn)，Y=(y1,y2,…,yn)，xiF2，yiF2，i=1,…,n，称

X和

Y对应分量不相等的分量个数为X和Y的汉明(Hamming)距离，记为d(X,Y)。定理:

设X和Y是长为n的二元码字，则（1）0≤d(X,Y)≤n

（非负且有界性）（2）d(X,Y)=0当且仅当X=Y（自反性）（3）d(X,Y)=d(Y,X)（对称性）（4）d(X,Z)≤d(X,Y)+d(Y,Z)（三角不等式）差错控制能力二元数域F2={0,1}的异或运算：F2的加法运算：0+0=0，0+1=1，1+0=1，1+1=0F2的乘法运算：0·0=0·1=1·0=0，1·1=1例如11000与10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用dmin表示。最小码距是码的一个重要参数，它是衡量码检错、纠错能力的依据。下面定理给出了检纠错能力:

dmin=min{d(X,Y)|X,Y∈C,X≠Y}定理

对一个最小距离为dmin纠错码，如下结论成立:

（1）

可以检测出任意小于等于l个差错,其中:（2）

可以纠正任意小于等于t个差错,其中:（3）可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足:最小码距与检纠错能力编码增益实际的通信系统，信号的传送需要一定的信噪比Eb/N0，它直接影响信道转移概率的大小，误码率pbe与信噪比Eb/N0的关系如图所示，当采用纠错码之后，达到同样的误码率需要的信噪比减小量称为编码增益。降价了信噪比检纠错码的分类

(1)根据纠错码各码组冗余位和信息元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。

(2)根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。

(3)根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。

关于分组码的纠错能力说明:

分组码一般可用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的冗余位数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个冗余位，组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码字未被选用，称为禁用码组。

2.检错和纠错能力

若分组码码字中的冗余位在信息元之后，而且是信息元的简单重复，则称该分组码为重复码。它是一种简单实用的检错码，并有一定的纠错能力。例如(2,1)重复码，两个许用码组是00与11，dmin=2，收端译码，出现01、10禁用码组时，可以发现传输中的一位错误。如果是(3,1)重复码，两个许用码组是000与111,dmin=3;当收端出现两个或三个1时，判为1，否则判为0。此时，可以纠正单个错误，或者可以检出两个错误。

检错能力与纠错能力进一步解释1、码距为1时，能保证码字的唯一性，但不能检错和纠错。2、码距为2时，能检查出一位错误，但无法纠错。许用码组：00，11禁用码组：01，10能够发现一个错误，但不能纠正错误如上例中:3、码距为3时，能检查出一位或两位错误，并且还可纠正一位错误。例：设码长为3，取000、111作为码字，其余为禁用码字。如接收端收到001，它是禁用码字，知道出错，由于001与000相差一个码元，与111相差两个码元，根据最大似然译码原则将001译为000，因为根据前面的结论：P(001/000)大于P(111/000)。最大似然译码原则：当ci为若干个发送码字中的一个，r为接收码字，若条件概率P(r/ci)为最大，则认为码字ci就是发送码字。码距的几何意义：以n=3的编码为例一般而言，码距是n维空间中单位正多面体顶点之间的汉明距离。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1预备知识--有限域上的线性空间定义是二元域F2上的n维线性空间。定义6.11

设C是F2上n维线性空间V的非空子集，如果C也是F2上的线性空间，则称C是V的子空间。定义6.15

设,

称为X与Y的内积；如果XY=0，则称X与Y正交。6.2线性分组码定理6.5

设C是F2上线性空间的子空间，令

则C⊥是的子空间（称为C的正交补子空间），且。§6.2.1线性分组码的描述

相应的信息码组行向量和分组码码组行向量为c=［c1,c2,…,cn］

m=［d1,d2,…,dk］则一个分组码组的前k位是信息码元，后n-k位是监督码元（设监督码元位数为r，则有r=n-k），每一个分组码组可以由信息码元线性组合而成.一个（n,k）线性分组码C是称为码字c的n维向量的集合:

C={c|c=mG}其中m为任意的k维向量并称为消息向量。G是k行n行列秩为k（n≥k）的矩阵并称为生成矩阵:行向量线性无关对每一个信息组m，由矩阵G都可以求得(n,k)线性码对应的码字。对于二元编码，和是二元向量，是一个二元矩阵，，向量与矩阵，矩阵与矩阵之间的基本运算是模二加和模二乘运算。

表6.2.1模二加/乘法表

例6.2.13重复码是一个（3，1）线性分组码

例6.2.2（4，3）偶校验码是一个（4，3）线性分组码例6.2.3:(7,4)线性码的生成矩阵为线性分组码有如下性质：零向量(0,0,…,0)一定是一个码字，称为零码字(当m为零向量时)；任意两码字的和仍是一个码字(封闭性,当m向量只有两个1时)；任意码字C

是G

的行向量(g1,g2,…,gk)的线性组合:

设C是[n,k]线性码，则恰好含有2k个码字。设

是C的生成矩阵，对cC，则存在惟一一组常数(其实就是信息序列)(m0,···,mk-1)F2，使:G中每一行gi=(gi,1,gi,2,…,gi,n

)都是一个码字(当m向量只有一个1时)

；(n,k)线性码的每一个码字都是生成矩阵G的行矢量的线性组合，所以它的2k个码字构成了由G的行张成的n维空间的一个k维子空间Vk。线性分组码的最小距离等于非零码字最小重量:

该最小重量也称汉明重量.上述结论给出了最小距离与最小重量的关系：线性分组码的最小距离等于它的最小重量。最小距离决定了检纠错能力,因为它体现了码字之间的差别.

码字重量就是码字中含“1”的个数,如码字10110，码重w=3。例:编码表

从表中可见非零码组的最小码重为3，则分组码的最小码距dmin=3，根据前面的结论可知:该分组码能够检2位错，纠1位错，或同时纠1位错检1位错。由偶校验码的检错概念，可以通过计算接收向量的所有校验方程值是否为0来判断传输是否可能有错，那么必有一个矩阵H满足:显然的每一列或的每一行确定了一个可能的分组码的校验方程，的线性不相关行数最少要等于该码的所有可能的校验方程数，称这样的矩阵为线性分组码的一致校验矩阵。

通俗地理解：在(n,k)分组码中，若每一个监督元(校验位)都是码组中某些信息元按模二和而得到的，即监督元是按线性关系相加而得到的，所以称线性分组码。或者说，可用线性方程组表述码规律性的分组码称为线性分组码。

现以(7,3)分组码为例来说明线性分组码的特点。设其码字为A=［c6

c5

c4c3c2

c1c0

］，其中前3位是信息元，后4位是监督元，可用下列监督线性方程组(校验方程组)来描述该分组码，产生监督元：

关于一致校验矩阵(一致监督矩阵)举例例如：信息码组(101)，即c6=1,c5=0,c4=1代入监督方程得：

c3=0,c2=0,c1=1,c0=1由信息码组(101)编出的码字为(1010011)。其它7个码字如表6.2.1。为了运算方便，将监督方程写成矩阵形式，得:系数矩阵H的后四列组成一个(4×4)阶单位子阵，用I4表示，H的其余部分用P表示推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由下面的线性方程组确定令上式的系数矩阵为H，码字行阵列为C一般H矩阵和G矩阵一样,每行之间是彼此线性无关的10.3线性分组码下面分析一下生成矩阵和校验矩阵的关系:(课堂练习)

现以(7,4)分组码为例来说明线性分组码的特点。设其码字为C=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是监督元，可用下列线性方程组来描述该分组码，产生监督元。

(6-3)(7,4)码的码字表

10.3.2监督矩阵H和生成矩阵G

式(6-3)所述(7,4)码的3个监督方程式可以改写为

(6-4)

这组线性方程可用矩阵形式表示为

(6-5)

并简记为

(6-6)其中，AT是A的转置，0T是0=［000］的转置，HT是H的转置。

(6-7)

H称为监督矩阵，一旦H给定，信息位和监督位之间的关系也就确定了。H为r×n阶矩阵，H矩阵每行之间是彼此线性无关的。式(6-7)所示的H矩阵可分成两部分:

其中,P为r×k阶矩阵，Ir为r×r阶单位矩阵。可以写成H=［PIr］形式的矩阵称为典型监督矩阵。HCT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字C是否出错的依据。(6-8)若把监督方程补充为下列方程

(6-9)可改写为矩阵形式

(6-10)(6-11)即

变换为

其中是生成矩阵，由G和信息组就可以产生全部码字。G为k×n阶矩阵，各行也是线性无关的。生成矩阵也可以分为两部分，即

(6-12)(6-13)由此得出一个结论:

(6-14)Q为k×r阶矩阵,Ik为k阶单位阵。可以写成式(6-13)形式的G矩阵称为典型生成矩阵。非典型形式的矩阵经过运算也一定可以化为典型矩阵形式。也就是说,线性系统码的监督矩阵H和生成矩阵G之间可以直接互换。

如:已知(7,4)线性系统码的监督矩阵为H=[PI]G=[IQ]Q=PT若与分别是线性码C的生成矩阵与校

验矩阵，则从而GHT=(HGT)T=0T=0。另一方面,由于G的每一行都是一个码字，有：

说明生成矩阵和校验矩阵的行正交,事实上：由:HCT=0T对偶码对偶码：对一个(n,k)线性码CI，由于Hr×nGTn×k=0Tr×k，如果以G作监督矩阵，而以H作生成矩阵，可构造另一个码CId，码CId是一个(n,n－k)线性码，称码CId为原码的对偶码。如：(7,4)线性码的对偶码是(7,3)码：(7,3)码的监督矩阵H(7,3)是(7,4)码生成矩阵G(7,4)

(7,3)码的生成矩阵G(7,3)是(7,4)码监督矩阵H(7,4)

设C⊥是线性空间的子空间C的正交补子空间，则也是长为n的(n,n-k)线性码，即C⊥是线性码C的对偶码；当C⊥

=C时，称C是自对偶码。定理：设C是长为n的二元线性码，则

(1)C恰好含有M=2dimC

个码字；

(2)当C是自对偶码时，。设h1=(h11,h12,…,h1n),

···,hn-k=(hn-k,1,hn-k,2,···,hn-k,n)是C⊥的基，则是C⊥的生成矩阵。

定理

设C是[n,k]线性码，是C的对偶码

C⊥

的生成矩阵，对，则X∈C的充要条件是。就是监督方程

由线性空间的理论，当H的行秩为r时，有如下的维数关系成立一个定理定理：[n,k]线性分组码有最小汉明距离d的充要条件是，H矩阵中任意d-1列线性无关。证明见教材该定理实际给出了计算线性分组码最小码距的一种方法。

译码的概念检错译码：译码器输出为当前接收向量r和r是否有差错的标志s，即。6.2.2线性码的译码纠错译码的译码成功：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字，即。纠错译码的译码失败：译码器不能输出一个确切的码字，通常此时的输出y与检错译码输出相同。

译码的问题：设行向量r=［r1，r2，…，rn］是收信端通过信道收到的码组。由于信道干扰会产生误码，接收向量r和发送向量c就会有差别，我们用向量e=[e1，e2，…，en］表示这种差别。三者之间的关系为:r=c+e(mod2)若r中的某一位ri与c中的相同位ci一样时，e中的ei=0；若不同（即出现误码），则ei=1。可见向量e能够反映误码状况，因此，称之为错误向量或错误图案。比如，发送向量c=［11011001］，而接收向量r=［10001011］，显然，r中有3个错误，由上式可得错误图样e=［01010010］。可见，e的码重就是误码的个数，因此e的码重越小越好。因为没有差错时:

令:并称为伴随式或校正子。

，则传输中一定有错误发生，则传输中要么无差错发生，要么差错图案恰好为一个码字。

否则有差错时:

另一方面:

由此可见，伴随式s与错误图样e之间有确定的线性变换关系。接收端译码器的任务就是从伴随式确定错误图案e(将s与最可能的e建一张表，然后通过s查表法得到其所对应用的e)，然后从接收到的码字中减去错误图案e:根据差概率大小决定【例题】已知一线性(6，3)码的生成矩阵为se000000000101100000011010000110001000100000100010000010001000001111100010s与e的对照表如下：

求当接收端收到码组r=［111011］时，所对应的信息码组m。=[I,Q]

解:根据前面HT的定义式可得将接收码组r=［111011］代入下式:从s―e关系表中可知，s=［011］所对应的错误图样为e=［010000］。将r=［111011］和e=［010000］代入下式可得:

从c中分出信息码组(前三位)为:

m=[101]

信息码组为m=[101]。伴随式纠错译码的通用译码方法

（1）按最可能出现的2r个差错图案e，计算相应的伴随式s，并构造伴随式—差错图案表(s-e表)；（2）对接收向量r计算伴随式s；（3）查s-e表得e；（4）纠错计算:按概率大小定理

可纠t错的2元线性分组码满足

伴随式的所有可能情况,每一种能纠一种错误.r=［r1，r2，…，rn］所有可能出错的情况§6.2.3码例与码的重构常见的线性分组码有:重复码汉明码里德-穆勒码戈雷码二进制汉明码的参数n,k和d分别为:

码长：信息位数：监督位数：最小距离：码率：1.汉明码汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。在被编码信息中加入m个奇偶校验位，让它们分布在码字的20,21,···,2m-1

位(m>=3)，从而将k位被编码信息均匀拉长到n=k+m=2m-1位(即k=2m-m-1)，就得到了(n,k)分组码,称汉明校验码。在汉明校验码中，n个码元（包括校验位）的位置按从右向左的顺序从1开始编号，其编号可以表示为2的最小幂之和，如1=20，2=21，3=20+21，4=22，…。这样，就确定了该码元由哪些校验位来校验,同样也就确定了每个校验位校验哪些码元（数据位）。说明:设原信息位为：D10D9D8D7D6D5D4D3D2D1D0;汉明校验码为：H15H14H13H12H11H10H9H8H7H6H5H4H3H2H1，它们分别按如下位置放置11个信息位和4个校验位：D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1

。编号码位最小幂分解编号码位最小幂分解编号码位最小幂分解1P1206D221+2211D

620+21+232P2217D320+21+2212D722+233D020+218P42313D820+22+234P3229D420+2314D921+22+235D120+2210D521+2315D1020+21+22+23例子:以m=4为例，码字最长为n=24-1=15位，被编码信息最长为11位。设4个校验位为：P4P3P2P1:P1=H1=D0+D1+D3+D4+D6+D8+D10P2=H2=D0+D2+D3+D5+D6+D9+D10P3=H4=D1+D2+D3+D7+D8+D9+D10P4=H8=D4+D5+D6+D7+D8+D9+D10编号码位最小幂分解编号码位最小幂分解编号码位最小幂分解1P1206D221+2211D

620+21+232P2217D320+21+2212D722+233D020+218P42313D820+22+234P3229D420+2314D921+22+235D120+2210D521+2315D1020+21+22+23H15H14H13H12H11H10H9H8H7H6H5H4H3H2H1D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1Hamming码的对偶码是一个(2m-1,m)线性分组码，称为最大长度码，由于所有非零码字的重量均为2m-1，又称为等距码或单形（simplex）码。

由于汉明码的最小距离是3，故汉明码能纠正一个随机错误或检测两个错误，且码的校验矩阵H中任意两列线性无关.一旦r给定，就可构造出具体的（n,k）汉明码。例:一个二元（7，4）Hamming码的系统码形式的矩阵和校验矩阵分别为

等价的编码方程为

伴随式计算方程

能纠1位错误6.3循环码

循环码是线性分组码的一个重要分支。循环码有许多特殊的代数性质，基于这些性质，循环码有较强的纠错能力，而且其编码和译码电路很容易用移位寄存器实现，因而在FEC系统中得到了广泛的应用。循环码可定义为：对于一个（n，k）线性码C，若其中的任一码组向左或向右循环移动任意位后仍是C中的一个码组，则称C是一个循环码。循环码是一种分组码，前k位为信息码元，后r位为监督码元。它除了具有线性分组码的封闭性之外，还具有一个独特的性质即循环性。循环性指的是任一许用码组经过循环移位后所得到的码组仍为一许用码组。

若c=[a0，a1，…，an-1]是一个循环码组，对它左循环移位一次，得到c(1)=[a1，a2，…，an-1，a1]也是许用码组，移位i次得到c(i)=［ai+1，ai+2，…，an，a1，ai］还是许用码组。不论右移或左移，移位位数多少，其结果均为循环码组。在代数编码理论中，可以把循环码组中各码元当作一个多项式的系数，即把一个长为n的码组表示为:c(x)=a0xn-1+a1xn-2+…+an-1c(x)称为码多项式，变量x称为元素，其幂次对应元素的位置，它的系数即为元素的取值（我们不关心x本身的取值），系数之间的加法和乘法仍服从模2规则。比如一个（7，3）循环码（见下表）中第7个码组为（1100101），则该码组可表示为

c7(x)=1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1=x6+x5+x2+1一种（7，3）循环码的全部码组

观察可见，该码的前3位是信息位，后4位是监督位，排列顺序一致而分明，是一种系统码。下面再举一例说明系统码与非系统码的区别。对一组4位信息码组，附加3位监督码元可编成两种（不只两种）循环码,如下表:（7，4）循环码码组

从表中可见，对于16组信息，系统码和非系统码都具有16个相同的编码码组，但与信息码的对应（映射）关系不一样。系统码的前4位对应的都是信息码，而后3位都是监督码元，二者泾渭分明，且编码前后信息码形式保持不变。而非系统码从第5组开始信息码就乱了，虽然每组信息码仍有一个确定的编码码组与之对应，但已经没有了系统码那种前后一致的信息码结构。由于一般我们只研究系统码，所以，有些书上直接说循环码是一种系统码。

生成多项式及生成矩阵

我们先讨论循环码和码多项式的关系:

事实上有如下的结论:码多项式的按模运算与整数类似:

若f(x)=m(x)q(x)+r(x)

则f(x)≡r(x)(模m(x))例因为:注意:系数是按模2运算.

如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如下表的(7,3)循环码中，

其它码多项式都是g(x)的倍式，即

表--(7,3)循环码

因此，循环码中次数最低的多项式(全0码字除外)就是生成多项式g(x)。可以证明:g(x)是常数项为1的r=n-k次多项式，是xn+1的一个因式。

循环码的生成矩阵常用多项式的形式来表示:

其中

例如(7,3)循环码，n=7,k=3,r=4,其生成多项式及生成矩阵分别为:即

监督多项式及监督矩阵为了便于对循环码编译码，通常还定义监督多项式，令

其中g(x)是常数项为1的r次多项式，是生成多项式；h(x)是常数项为1的k次多项式，称为监督多项式。同理，可得监督矩阵H

称为h(x)的逆多项式。例如(7，3)循环码，其中

则

即

编码方法和电路

在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一个r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为m(x)的最高幂次为k-1。循环码中的所有码多项式都可被g(x)整除，根据这条原则，就可以对给定的信息进行编码。用xr乘m(x)，得到xr·m(x),用g(x)去除xr·m(x)，得到余式r(x),r(x)的次数必小于g(x)的次数，即小于(n-k)。将此余式加于信息位之后作为监督位，即将r(x)与xrm(x)相加，得到的多项式必为一码多项式，因为它必能被g(x)整除，且商的次数不大于(k-1)。循环码的码多项式可表示为:其中，xr·m(x)代表信息位，r(x)是xr·m(x)与g(x)相除得到的余式，代表监督位。

循环冗余检验CRC在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术,采用的就是循环码的思想。例：假设待传送的数据M=1010001101(共k=10bit)。用二进制的模2运算进行2r乘M的运算，这相当于在M后面添加r个0。得到的(k+r)bit的数除以事先选定好的长度为(r+1)bit的数P，得出商是Q而余数是R，余数R比除数P至少要少1个比特。设r=5,P=110101.

1101010110

←

Q

商

除数

P→

110101101000110100000

←

2rM被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余数运算的结果是：商Q=1101010110，余数R=01110。将余数R作为冗余码添加在数据M的后面发送出去，即发送的数据是101000110101110，即2rM+R。差错检测方法用P去除接收向量M*,只要得出的余数R不为0，就表示检测到了差错。由于2rM=P•Q+R，而发送端所发送的数据是：2rM+R，又：2rM+R=(P•Q+R)+R=P•Q+(R+R),按模2加有：R+R=0，所以2rM+R=P•Q。因此若接收端能无差错地接收到2