第6章信道编码教学内容：信道编码的概念、信道编码定理、线性分组码、循环码6.1信道编码的概念教学内容：1、信道编码的意义2、信道编码的分类3、信道编码的基本原理4、检错和纠错能力1、信道编码的意义由于实际信道存在噪声和干扰，使发送的码字与信道传输后所接收的码字之间存在差异，称这种差异为差错。
信道编码的目的是为了改善通信系统的传输质量。
基本思路是根据一定的规律在待发送的信息码中加入一些多余的码元，以保证传输过程的可靠性。
信道编码的任务就是构造出以最小冗余度代价换取最大抗干扰性能的“好码”。
2、信道编码的分类纠错编码的目的是引入冗余度，即在传输的信息码元后增加一些多余的码元（称为校验元，也叫监督元），以使受损或出错的信息仍能在接收端恢复。
一般来说，针对随机错误的编码方法与设备比较简单，成本较低，而效果较显著；而纠正突发错误的编码方法和设备较复杂，成本较高，效果不如前者显著。
因此，要根据错误的性质设计编码方案和选择差错控制的方式。
3、信道编码的基本原理可见，用纠（检）错控制差错的方法来提高通信系统的可靠性是以牺牲有效性的代价来换取的。
在通信系统中，差错控制方式一般可以分为检错重发、前向纠错、混合纠错检错和信息反馈等四种类型。
香农理论为通信差错控制奠定了理论基础。
香农的信道编码定理指出：对于一个给定的有干扰信道，如信道容量为C，只要发送端以低于C的速率R发送信息(R为编码器输入的二元码元速率)，则一定存在一种编码方法，使编码错误概率p随着码长n的增加，按指数下降到任意小的值。
这就是说，可以通过编码使通信过程实际上不发生错误，或者使错误控制在允许的数值之下。
4、检错和纠错能力举例：A、B两个消息a、没有检错和纠错能力：0、1b、检出一位错码的能力：00、11c、判决传输有错：000、111（大数法则）一般来说，引入监督码元越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。
人们研究的目标是寻找一种编码方法使所加的监督码元最少，而检错、纠错能力又高且又便于实现。
6.2信道编码定理教学内容：1、译码规则及错误概率2、信道编码定理3、检错与纠错原理1、译码规则及错误概率信宿如何译码使发生错误概率最小。
信源共有M个消息，假设已用M个码元X1，…，XK，…，XM对它进行了最佳编码。
信源通过信源编码器编码后发送码元Xk，其发送概率为q（Xk），通过信道转移慨率为的信道传输，接收到码元Y，信道译码器输出，而是对Y的一个估值，通信过程可用图6.2.1所示框图表示。
约定时，认为误码，则发送Xk收到Y估错的概率为：(6.2.1)通信总希望错误概率最小，由式(6.2.1)可看出最小等同于后验概率最大，这就是最大后验概率准则。
，若Y已收到，则=1，所以，最大等同于最大。
在输入码元先验概率q（X）相等的条件下就等同于最大，这就是最大似然译码准则，也称似然函数。
2、依据【例6.2.1】来在两大准则下译码。
3、信道编码定理对于任何离散无记忆信道(DMC)，存在信息传输率为R，长为N的码C，当时，差错概率，式中E(R)为可靠性函数，E(R)在0 上述定理也称有噪信道编码定理，即香农第二定理。 定理说明：信道容量C是保证无差错传输时信息传输率R的极限值。 对于固定信道，C值是一定的，它是衡量信道质量的一个重要物理量。 E(R)在信道编码中具有重要意义，它表示了在N一定的条件下，最佳编码误码率的一个上界，同时也告知了随而趋于0的速率，在规定了值后，E(R)可帮助你选择合适的N和R。 4、检错与纠错原理编码效率：R=k／n1、偶（或奇）校验方法：确定校验位P的编码方程为校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错。 当编码可以产生多个奇偶校验位时，一个校验位可以由消息位的部分或全部按校验方程产生。 例如，下式的C是一个对阵列消息进行垂直与水平校验以及总校验的码字，其码率为编码效率，，2、重复消息位：一个n重复码是一个码率为l／n的码，仅有两个码字C0和C1，传送1bit(k=1)消息。 C0＝（00…0），C1＝（11…1）（6.2.4）对于一个无记忆二进制对称信道总有转移概率，nbit传输中发生差错数目越少，概率越大，即从而总认为发生差错的图案是差错数目较少的图案，因此当接收到重复码的接收序列r中“l”的个数少于一半时，认为发送的是C0，否则认为是C1。 这样重复码可以纠正传输中可能出现的不多于[n/2]个差错。 3、设计码字中的非0符号个数：实现检纠错的第三个方法是设计码字中的非0符号个数（二进制码则为“1”的个数），又称为码字重量w(c)，恒为常数，即C由全体重量恒等于m的n长向量组成，称这种码为等重码或定比码。 例如，一种用于表示0至9数字的5中取3等重码如表6.1.1所示，其码率（每个码字平均传送的消息bit数）R为，其中表示n中取m的组合数。 表6.2.15中取3等重码显然5中取3等重码可以检测出全部奇数位差错（只变奇数个0或1，改变码重），对某些码字的传输则可以检测出部分偶数位差错（只变偶数个0或1，改变码重）。 而对（1变为0的同时0变为1，无能为力）。 4、检错与纠错方式和能力a、前向纠错方式用于纠错的纠错码在译码器输出端总要输出一个码字或是否出错的标志，这种纠错码的应用方式称为前向纠错方式（FEC）。 b、自动请求重发用于检错的纠错码在译码器输出端只给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字全部或部分，这种纠错码的应用方式称为自动请求重发（ARQ）方式。 比较纠错码检纠错能力的最直接指标是检纠差错数目，常用汉明（Hamming）距离来描述这一特性。 码距：把两个码字中对应码位上具有不同的二元码元的位数定义为两码字的汉明距离。 码距的最小值定义为最小汉明距离。 汉明距离具有以下性质：（1）对称性：d(c1,c2)=d(c2,c1)（2）非负性：d(c1,c2)>=0（3）满足距离三角不等式：d(c1,c2)<=d(c1,c3)+d(c3,c2)纠错码的基本任务就是构造出R一定且dmin尽可能大的码。 若纠错码的最小距离为dmin，那么有如下三个结论的任何一个结论独立成立。 (1)可以检测出任意小于等于l＝dmin-1个差错。 (2)可以纠正任意小于等于个差错。 (3)可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足。 6.3线性分组码教学内容：1、线性分组码概述2、生成矩阵和一致校验矩阵3、纠错能力4、译码1、线性分组码概述检错码在发现差错后必须通过要求对方重发一遍来获得正确的信息，在实时信息采集系统中可能是有困难的（信息源已经发生变化）。 就是在发方保留有原信息样本的情况下，也只有在差错率很低的条件下是比较可行的。 如果通信条件比较恶劣，差错出现频繁，以至多次重发仍然得不到一份正确的信息。 在这种情况下，只采用“检错”手段就显得无能为力了。 本节和下一节介绍两种纠错码：线性分组码和循环码。 线性分组码是分组码的一个子类，由于线性码的编码和译码容易实现，至今仍是应用最广泛的一类码。 一个[n,k]线性分组码，是把从信源输出的以k个码元为一组的信息组m，通过信道编码器后，变成长度为n≥k的码组（码字）c作为[n,k]线性分组码的一个码字。 设GF(q)是一个含有q个元素的有限数域，若每位码元的取值有q种（取自GF(q)），则信息组m共有种不同的状态，因此，需要个码字c。 而长为n的数组共有个，二进制时(q=2)共有个。 显然，个n维向量组成有限域GF(q)上的一个n维线性空间V，编码就是要在这个n维线性空间中选出个向量作为合法码字，其余的-个向量为禁用码字。 如果选出的个作为合法码字的向量的集合构成了V的一个k维线性子空间，则称它是一个q进制[n,k]线性分组码。 如果值取自GF(q)上的[n,k]分组码的个码字的集合C，便构成了有限域GF(q)上的n维线性空间V的一个k维线性子空间，则称C是一个q进制[n,k]线性分组码。 结合【例6.3.1】给出形象化描述。 【例6.3.1】若n=7，k＝3的[7，3]线性分组码的8个码字和对应的信息组如表6.3.1所列，这8个码字构成GF(2)上的一个7维线性空间中的一个3维线性子空间，且在按位模2加运算下构成阿贝尔加群。 表6.3.1[7，3]线性分组码和对应信息2、线性分组码的生成矩阵和一致校验矩阵[n,k]线性分组码的编码问题就是在n维线性空间V中，如何选出满足一定要求的k维线性子空间的问题。 或者说，在满足给定条件（如码的最小距离dmin，或码率）下，如何从已知的k个信息元中求出r＝n-k个校验元。 首先从已知的k个系数，求出r＝n-k个未知数，使得到的码恰好有所要求的最小距离。 我们从例6.3.1开始分析，对该例中的[7,3]线性分组码，若用C0，C1，C2代表信息元，则C3，C4，C5，C6四个校验元可由如下的线性方程组求得：(6.3.1)或(6.3.2)用矩阵写成：(6.3.3)上述运算为模2运算。 系数矩阵的秩为4，所以，它的解空间是一个3维线性子空间。 因此，这个解空间就是由该线性分组码的全部码字所组成。 （R(A)=r<=>A中至少有一个r阶子式不等于0）则式(6.3.3)可写为：HeT=oT,称H为该[7，3]线性分组码的一致校验矩阵。 再将式(6.3.33)改写为：(6.3.4)用矩阵写成：(6.3.5)记作：G=称G为该[7,3]线性分组码的生成矩阵。 值得注意的是G的每一行是一个合法码字（C的重量取1）。 由于G的每一行都是［n,k］线性分组码字，所以，HGT＝0或GHT＝0。 说明G与H的行向量生成的空间互为零空间。 （如果选出的个作为合法码字的向量的集合构成了V的一个k维线性子空间，则称它是一个q进制[n,k]线性分组码。 ）由于生成矩阵的秩是k，所以每个行向量既是基底，也是一个码字。 任何生成矩阵都可以通过行运算转换成如下形式：Gsys=[Ik|P]P是k*（n-k）矩阵，I是k阶单位矩阵。 Hsys=[PT|In-k]3、线性码的纠错能力讨论线性分组码的最小距离与H的关系，给出3个定理并证明之。 【定理6.3.1】若[n,k]线性分组码的最小距离必等于码中非零码字的最小重量，即dmin=。 利用定理6.3.3可通过H求出码的最小重量Wmin，即码的最小距离dmin，再利用分组码的最小距离与纠错能力的关系得到线性分组码的最小距离与纠错能力的关系。 4、线性分组码的译码（1）回顾译码准则（2）伴随式检错由于信道存在干扰，发送端发出的合法码字，接收端收到的可能是任何一个n维向量。 没发送的码字为C=(c1,c2,…,cn)，收到的向量是R＝(r1,r2,…,rn)，用监督矩阵编码，当然也用监督矩阵译码。 判断HRT=0T是否成立。 记E=R-C，称它为错误图样，E=(e1,e2,…,en)=（r1-e1,r2-e2,…,rn-en）。 若ei=0,表示第i位无错，否则，表示第i位有错。 由于R＝c＋E，可得：HRT=H（c＋E）T=HcT＋HET=HET。 式中，H为一致校验矩阵。 HRT称为接收向量的伴随式，用s表示，即：s＝HRT=HET=h1en-1+h2en-2+…+hnen0得到如下结论：（1）伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样有关。 （2）伴随式是错误的判别式，若S=0，则判无错，否则，有错。 （3）不同的错误图样具有不同的伴随式，二元码伴随式是H矩阵中与错误码元对应列之和。 给出如下例子：设[6，3]线性分组码的一致校验矩阵H为：H=如果发送的码字c=（101011），接收的向量为R=（101011），则：s=因此，判定传输中没有发生错误。 如果发送的码字c=（101011），接收的向量为R=（100011），则：s=由于S等于H的第2列，因此判定接收码子R的第2位是有错的。 当码元错误多余1个时，设接收码字R=（101000），则其伴随式为s=S是第5列和第6列之和，则只能发现差错。 （3）陪集纠错前面说明了可用伴随式来检验接收字是否包含错误，下面讨论如何纠正接收字中的错误。 把2n个n维向量划分成为2k个互不相交的子集D1,D2,…,，使f’在每一个子集中仅含有一个码字。 例如，在Di中仅有Ci一个码字。 译码时，凡是落在Di中的接收向量都译成Ci。 表6.3.2建立供译码用的标准阵列标准阵列中的每一行都是一个陪集，每一个陪集的第一个元素叫做陪集首。 该标准阵列译码表的建立方法是：标准阵列中的第一行是合法码字的集合即子群C，共2k个合法码字，该行最左边的第一个元素C1=E1为全零码字，第二行的左边的第一个元素E2要选上一行中未出现的元素，作为陪集首，与第一行的对应元素Ci构成E2＋Ci放在Ci下面，得第二行。 第二行的元素集合是陪集E2＋C。 类似地，取第一、二行未出现的元素E3作为陪集首，放在E2的下面，同上法作出第三行，依此类推，直至作出第2n-k行。 为使所有陪集不相交，一定要选择上面陪集中未曾出现的元素作陪集首。 为了尽可能使译码正确，应该把实际信道中出现概率大的错误图样都作为陪集首。 由于错误图样E=中，ei为零表示该位正确，非零则表示该位出错。 E的重量表示出错的位数，因E的重量越小，出现的概率越大。 因此，要选择禁用码字中重量最小的向量作为陪集首，以全零码字作为子群的陪集首。 这样得到的标准阵列使Ei＋Ci与Ci的距离最小，因而也称为最小距离译码。 表6.3.3（6，3）码标准阵列表为了用伴随式来简化译码表，先给出下面的定理。 【定理6.3.4】一个陪集中的全部2k个n维向量都有相同的伴随式，但不同陪集的伴随式是不相同的。 根据该定理，一个陪集与一个伴随式(n-k维向量)之间是一一对应的，于是只要计算接收向量的伴随式，就可以根据这种对应关系找到对应的陪集首。 利用伴随式与陪集首的这种对应关系，我们可作简化译码表。 利用译码表译码的步骤如下：（1）计算接收向量的伴随式s＝；（2）根据译码表找出对应的陪集首E；（3）输出译码c=R+E。 结合例6.3.2熟悉译码表译码步骤。 6.4循环码教学内容：1、定义2、码多项式3、码多项式基本性质4、生成矩阵和一致校验矩阵5、编码6、译码1、定义：循环码是十分重要的线性分组纠错码，是最重要、最有用的一类。 特点：1：循环码有很多固有的代数结构，从而可以找到各种简单实用的译码方法。 2：利用反馈线性移位寄存器很容易实现其编码和伴随式计算。 设[7，4]汉明码C的生成矩阵和一致校验矩阵分别为：G=，H=，得到16个码字是：（1000101），（0001011），（0010110），（0101100），（1011000），（0110001），（1100010），（0100111），（1001110），（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]线性分组码为循环码。 2、码多项式循环码可以用多种方式进行描述，在不同情况下使用不同的描述方式将有助于问题的深入研究。 我们将一个码字的诸分量看成是一个多项式的系数，因此有如下的一一对应：c=(cn-1，cn-2，…，c1，c0)c(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0。 例子（7，3）：0011101x4+x3+x2+10111010x5+x4+x3+x=x(x4+x3+x2+1)mod(1+x7)1110100x6+x5+x4+x2=x2(x4+x3+x2+1)mod(1+x7)1101001x6+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-ixn-2+…+c1xi+1+c0xi+cn-1xi-1+…+cn-i+1x+cn-i，实际上c(i)(x)=xic(x)mod(xn-1)，所以xic(x)=c(i)(x)mod(xn-1)。 为了方便，今后我们直接称xic(x)是一个码多项式。 3、码多项式基本性质：【定理6.4.1】在一个[n,k]线性分组码中，有惟一的非零最低次数的码多项式g(x)。 【定理6.4.2】设g(x)=xr+ar-1xr-1+…+a1x+a0为[n,k]循环码C的非零最低次数的码多项式，则任意一个次数小于或等于n–1的多项式h(x)是码多项式的充分必要条件，其充要条件为：h(x)是g(x)的倍式。 【定理6.4.3】[n,k]循环码的生成多项式g(x)的次数等于n–k，并且常数项不等于零。 【定理6.4.4】[n,k]循环码的生成多项式g(x)一定是xn－1的因式。 【定理6.4.5】若g(x)是xn–1的n–k次因式，则g(x)生成一个[n,k]循环码，且g(x)就是该[n,k]循环码的生成多项式。 根据上述订立，我们可以找到构成（n、k）循环码的方法：（1）对xn－1实施因式分解，找出其中的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，得到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=(0100111)，依次将（000）到（111）全部代入，则可以得到全部循环码集：00000000000010011100010*******01101001111001110100101110100111010011101111010011下面总结构成系统码的方法：所谓构成系统码，就是前k位为信息位，而后n-k位为校验元。 我们认为码多项式应该具有如下的结构：C(x)=xn-km(x)+r(x)，其中r(x)是与n-k位校验元对应的n-k-1次多项式。 根据［定理6.4.4］可知，C(x)是g(x)的倍式，即C(x)=xn-km(x)+p(x)≡0modg(x)。 所以，p(x)≡xn-km(x)modg(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-km(x)=x4(x+1)=x5+x4x5+x4除以x4+x3+x2+1得到余式x3+x得到C(x)=x5+x4+x3+x，得到（0111010）4、循环码的生成矩阵和一致校验矩阵一个[n,k]线性分组码是n维线性空间中的一个k维子空间，同样，一个[n,k]循环码也是n维线性空间中的一个k维子空间。 因此，只要找出k个线性无关的码多项式，就可通过线性组合得到所有码多项式。 由于码的生成多项式g(x)是n-k次的，所以g(x)，xg(x)，x2g(x)，…，xk-1g(x)都是线性无关的，可得码的生成矩阵：G=。 【例6.4.1】设g(x)=x3+x+1为[7,4]循环码的生成多项式，则对应的g=(0，0，0，1，0，1，1)，所以，得到生成矩阵为：G=。 由于g(x)是xn–1的因式，所以，可写成：xn–1=g(x)h(x)。 由g(x)可导出生成矩阵G，那么由h(x)是否可导出一致校验矩阵H呢？下面讨论这个问题。 因为g(x)h(x)=xn–1，设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)=xn－1，已知arbk＝1，a0b0＝1，而xn-1，xn-2，…，x等的系数均为0。 a0b1+a1b0=0，a0b2+a1b1+a2b0=0，ar-ibk-1+ar-i+1bk-2+…+ar-i+jbk-j-1=0，arbk-1+ar-1bk=0，由此可知循环码的校验矩阵为：H=。 若记h﹡(x)=b0xk+b1xk-1+…+bk-1x+bk，则H(x)=。 因此，H由h(x)的系数决定，故称h(x)是循环码的校验多项式。 【例6.4.2】在例6.4.1的[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)，因此，得到生成矩阵和校验矩阵为：G=H=容易验证GHT=0。 信道产生的错误图样是E，它的多项式表示为：E(x)=en-1xn-1+en-2xn-2+…+e1x+e0。 译码器收到的是R=C+E=(rn-1，rn-2，…，r1，r0)，它的多项式表示为：R(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0。 由于循环码是线性分组码，所以，循环码的译码与线性分组码的译码一样可分为三步：第一步，计算接收向量R(x)的伴随式s(x)；第二步，根据s(x)从译码表找出对应的陪集首E(x)；第三步，输出译码c(x)＝R(x)+E(x)。 s(x)＝R(x)modg(x)。 这说明循环码的伴随式计算电路就是用生成多项式g(x)除以接收多项式R(x)的求余式电路，伴随式s(x)就是所得之余式。 根据s(x)从译码表找出对应的陪集首E(x)，输出译码c(x)＝R(x)十E(x)，达到纠错的目的。