信道编码

第六章 信道编码 信道编码以提高信息传输的可靠性为目的，是要使从信源发出的信息经过信道传输后，尽可能准确地、不失真地再现在接收端。信道编码通常通过增加信源冗余度的方式来实现。 本章首先介绍信道的基本模型，探讨信道传输信息的能力，讨论抗干扰信道编码的基本原理，然后详细介绍二元线性码和循环码的编码、译码，最后简要介绍限失真编码定理。 [学习目标] （1）理解和掌握信道编码的基本原理； （2）理解抗干扰信道编码定理； （3）理解和掌握二元线性码的编码和译码； （4）理解和掌握循环码的编码和译码； （5）理解限失真编码定理。 6.1 信道编码概述 6.1.1信道模型 信息必须首先转换成能在信道中传输或存储的信息后才能通过信道传送给收信者。在信息传输过程中，噪声或干扰主要是从信道引入的，它使信息通过信道传输后产生错误和失真。因此信道的输入和输出之间一般不是确定的函数关系，而是统计依赖的关系。只要知道信道的输入信号、输出信号以及它们之间的统计依赖关系，就可以确定信道的全部特性。 信道的种类很多，这里只研究无反馈、固定参数的单用户离散信道。 1．离散信道的数学模型 离散信道的数学模型一般如图6.1所示。图中输入和输出信号用随机矢量 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示，输入信号为 X= (X1, X2,…, XN)，输出信号为Y= (Y1, Y2,…, YN)；每个随机变量Xi和Yi又分别取值于符号集A={a1, a2, …, ar}和B={b1, b2, …, bs}，其中r不一定等于s；条件概率P(y|x) 描述了输入信号和输出信号之间的统计依赖关系，反映了信道的统计特性。 图6.1 离散信道模型 根据信道的统计特性即条件概率P(y|x) 的不同，离散信道可以分为三种情况： （1）无干扰信道。信道中没有随机干扰或干扰很小，输出信号 与输入信号 之间有确定的一一对应的关系。 （2）有干扰无记忆信道。实际信道中常有干扰，即输出符号与输入符号之间没有确定的对应关系。若信道任一时刻的输出符号只统计依赖于对应时刻的输入符号，而与非对应时刻的输入符号及其他任何时刻的输出符号无关，则这种信道称为无记忆信道。 （3）有干扰有记忆信道。这是更一般的情况，既有干扰又有记忆，实际信道往往是这种类型。在这一类信道中某一瞬间的输出符号不但与对应时刻的输入符号有关，而且与此前其他时刻信道的输入符号及输出符号有关，这样的信道称为有记忆信道。 2．单符号离散信道的数学模型 单符号离散信道的输入变量为 ，取值于{a1, a2, …, ar}，输出变量为 ，取值于{b1, b2, …, bs}，并有条件概率 P(y|x)= P(y=bj|x=ai)= P(bj |ai) (i=1,2,…,r；j=1,2,…,s) 这一组条件概率称为信道的传递概率或转移概率。 因为信道中有干扰（噪声）存在，信道输入为x=ai时，输出是哪一个符号y，事先无法确定。但信道输出一定是b1, b2, …, bs中的一个，即有 (i=1,2,…,r) (6-1) 由于信道的干扰使输入符号x在传输中发生错误，所以可以用传递概率P(bj|ai) 来描述干扰影响的大小。因此，一般简单的单符号离散信道的数学模型可以用概率空间[ ]加以描述。另外，也可以用图来描述，如图6.2所示。 图6.2 单符号离散信道 例6.1 二元对称信道 这是很重要的一种特殊信道（简记为BSC），如图6.3所示。它的输入符号X取值于{0,1}，输出符号Y取值于{0,1}，r=s=2， a1=b1=0，a2=b2=1，传递概率为 , , 其中， 表示信道输入符号为0而接收到的符号为1的概率， 表示信道输入符号为1而接受到的符号为0的概率，它们都是单个符号传输发生错误的概率，通常用p表示。而 和 是无错误传输的概率，通常用 表示。 显然，这些传递概率满足式(6-1)，即 X 1-p Y 图6.3 二元对称信道一 用矩阵来表示，即得二元对称信道的传递矩阵为 依此类推，一般离散单符号信道的传递概率可用以下形式的矩阵来表示，即 b1 b2 … bs 并满足式 （ ）。 为了表述简便，记 ，信道的传递矩阵表示为 而且满足 且 （ ) (6-2) 式(6-2)表示传递矩阵中的每一行之和等于1。 这个矩阵完全描述了信道的统计特征，又称为信道矩阵，其中有些概率是信道干扰引起的错误概率，有些概率是信道正确传输的概率。可以看到，信道矩阵 既表达了输入符号集A={a1,…, ar}，又表达了输出符号集B={b1,…, bs}，同时还表达了输入与输出之间的传递概率关系，故信道矩阵 能完整地描述给定的信道。因此，信道矩阵 也可以作为离散单符号信道的另一种数学模型的形式。 定义6.1 已知发送符号为ai，通过信道传输接收到的符号为bj的概率P(bj|ai)称为前向概率。已知信道输出端接收到的符号为bj，而发送符号为ai的概率P(ai|bj)，称为后向概率。 有时，也把P(ai)称为输入符号的先验概率（即在接收到一个输出符号以前输入符号的概率），而对应地把P(ai|bj)称为输入符号的后验概率（在接收到一个输出符号以后输入符号的概率）。 为了讨论方便，下面列出本章讨论中常用的一些关于联合概率和条件概率的关系： (1) 设输入和输出符号的联合概率为P(x= ai, y= bj)=P(ai bj)，则有 (2) （ ）。 (3) 根据贝叶斯定律，可得后验概率与先验概率之间的关系 （ ） ＝ （ ） 6.1.2信道疑义度和平均互信息 1. 信道疑义度 根据熵的概念，可计算信道输入信源X的熵 （6-3） H(X)是在接收到输出 以前，关于输入变量 的先验不确定性的度量，称为先验熵。如果信道中无干扰（噪声），信道输出符号与输入符号一一对应，则接收到传送过来的符号后就消除了对发送符号的先验不确定性。但一般信道中有干扰（噪声）存在，接收到输出 后对发送的是什么符号仍有不确定性。那么，怎样来度量接收到Y后关于X的不确定性呢？当没有接收到输入Y时，已知输入变量的X概率分布为P(x)；而当接收到输出符号y=bj后，输入符号的概率分布发生了变化，变成后验概率分布P(x|bj)。 定义6.2 接收到输出符号y=bj后，关于 的平均不确定性为 （6-4） 称H(X|bj)为接收到输出符号为bj后关于X的后验熵。后验熵是当信道接收端接收到输出符号bj后，关于输入符号的信息测度。 将后验熵对随机变量 求期望，得条件熵为 （6-5） 这个条件熵称为信息疑义度。 信息疑义度表示在输出端收到输出变量 的符号后，对于输入端的变量 尚存在的平均不确定性（即存在疑义）。这个对X尚存在的不确定性是由干扰（噪声）引起的。如果是一一对应信道，那么接收到输出Y后，对X的不确定性将完全消除，则信道疑义度H(X|Y)=0。 2. 平均互信息 由于H(X) 代表接收到输出符号以前输入变量 的平均不确定性，而H(X|Y) 代表接收到输出符号后输入变量X的平均不确定性，而且一般情况下条件熵小于无条件熵，即有H(X|Y)< H(X)。因此，接收到变量Y的所有符号后，输入变量X的平均不确定性将减少，即通过信道消除了一些关于输入端X的不确定性，获得了一些信息。 定义6.3 称 I(X;Y)= H(X)-H(X|Y) 为X和Y之间的平均互信息。 平均互信息表示接收到输出符号后平均每个符号获得的关于输入变量X的信息量，也表示输入与输出两个随机变量之间的统计约束程度。 根据式（6-3）和式（6-5），得 其中X是输入随机变量，Y是输出随机变量。 平均互信息是互信息（即接收到输出符号y后输入符号x获得的信息量）的统计平均值，所以永远不会取负值。最差情况是平均互信息为零，也就是在信道输出端接收到输出符号Y后不获得任何关于输入符号X的信息量。 6.1.3错误概率和译码规则 由于信道中存在噪声，因而信道传输信息的质量必然会下降。噪声越严重，传输信息的质量就会越差，当噪声严重到一定程度，传输信息就成为不可能。理想的信道，也就是无噪声的信道是不存在的。在有噪信道中传输消息是会发生错误的。为了减少错误，提高可靠性，首先要分析错误概率与哪些因素有关，有没有办法加以控制，能控制到什么程度等问题。 1．错误概率与信道统计特性有关 信道的统计特性可由信道的传递矩阵来描述。当确定了输入和输出对应关系后，也就确定了信道矩阵中哪些是正确传递概率，哪些是错误传递概率。例如在二元对称信道中，单个符号的错误传递概率是 ，正确传递的概率是 ＝1－ 。 2．错误概率与译码规则有关 通信过程一般并不是在信道输出端就结束了，还要经过译码过程(或判决过程)才到达消息的终端。因此，译码过程和译码规则对系统的错误概率影响很大。 现举一个特殊例子来说明。设一个二元对称信道，其传输特性如图6.4所示。一般二元对称信 道输出端的译码器是将接收到的符号“0”译成发送的符号为“0”，接收到的符号“1”译成发送的符号为“1”。如果仍按照此译码器的译码规则，那么当发送符号为“0”，接收到符号仍为“0”，则译码器译为符号“0”为正确译码，因此对发送符号“0”来说，译对的可能性只有l/3；而当发送符号为“0”，接收到符号却是“1”，则译成符号“1”为错误译码，则译错的概率 是2/3。因为信道对称，对发送符号“1”来说，译错的概率 也是2/3。在此译码规则下，平均错误概率（假设输入端符号是等概率分布） 反之，若译码器根据这个特殊信道定出另一种译码规则，将输出端接收符号“0”译成符号“1”，把接收符号“1”译成符号“0”，则译错的可能性就减少了，为1/3；而译对的可能性增大了，为2/3。 可见，错误概率既与信道的统计特性有关，也与译码的规则有关。 图6.4 二元对称信道二 3．译码规则 定义6.4 (译码规则) 设离散单符号信道的输入符号集为A={ai}， ＝1,2,…,r；输出符号集为B={bj}， ＝1,2,…,s。定义译码规则就是 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一个函数 ，它对于每一个输出符号bj确定一个惟一的输入符号ai与其对应(单值函数)，即 F(bj)= ai ( ＝1,2,…,r； ＝1,2,…,s) 例 6.2 有一离散单符号信道，信道矩阵为 b1 b2 b3 根据这个信道矩阵，设计一个译码规则 也可以设计另外一个译码规则 由于 个输出符号中的每一个都可以译成 个输入符号中的任何一个，所以共有rs种译码规则可供选择。 这里主要介绍最大后验概率准则和极大似然译码准则。 （1）最大后验概率准则 译码规则的选择应该根据什么准则？一个很自然的准则当然就是要使平均错误概率为最小。 为了选择译码规则，首先必须计算平均错误概率。 在确定译码规则F(bj)=ai后，若信道输出端接收到的符号为bj，则一定译成ai，如果发送端发送的就是ai，就为正确译码；如果发送的不是ai，就为错误译码。那么，收到符号bj条件下译码的条件正确概率为 令 为条件错误概率，其中 表示除了F(bj)=ai以外的所有输入符号的集合。条件错误概率与条件正确概率之间有关系 （6-6） 定义6.5 称条件错误概率 对 空间的平均值 （6-7） 为平均错误概率。 平均错误概率表示经过译码后平均接收到一个符号所产生的错误大小。 如何设计译码规则F(bj)=ai，使PE最小呢？由于式(6-7)右边是非负项之和，所以可以选择译码规则使每一项为最小，即得PE为最小。因为P(bj)与译码规则无关，所以只要设计译码规则F(bj)=ai使条件错误概率P(e|bj)为最小。 根据式(6-6)，为了使P(e|bj)为最小，就应选择 为最大。 定义6.6 选择译码函数： 并使之满足条件 （6-8） 这种译码规则称为“最大后验概率准则”或“最小错误概率规则”。 如果采用最大后验概率译码准则，它对于每一个输出符号均译成具有最大后验概率的那个输入符号，此时信道错误概率就能最小。 因为一般已知信道的传递概率P(bj|ai)与输入符号的先验概率P(ai)，所以根据贝叶斯定律，式(6-8)可写成 一般 EMBED Equation.3 0, bj (B ，这样，最大后验概率准则也可表示为： （2）极大似然译码准则 定义6.7 选择译码函数 使满足 这样定义的译码规则称为极大似然译码准则（Maximum likelihood decoding）。 根据极大似然译码准则，收到符号bj后，应译成信道矩阵 的第 列中最大的元素所对应的信源符号。 如果所对应的取值最大的信源符号不惟一，则不译此符号。显然，极大似然译码准则本身不再依赖先验概率P(ai)。但是当先验概率为等概率分布时，它使错误概率PE最小（如果先验概率不相等或未知时，仍可以采用这个准则，但不一定能使PE最小）。 在输入符号等概率时，极大似然译码准则与最大后验概率译码准则是等价的。 4．计算平均错误概率 根据译码准则，平均错误概率为 （6-9） 而平均正确概率为 式(6-9)中求和号 表示对输入符号集 中除 以外的所有元素求和，式(6-9)也可以写成 （6-10） 上式的平均错误概率是在联合概率矩阵[ ]中先求每列除去 所对应的 以外所有元素之和，然后再对各列求和。当然，也可以在矩阵 [ ]中先对每行求和，除去译码规则中 所对应的 （ 1，…， ），然后再对各行求和。因此，式(6-10)还可以写成 其中 ，是输入符号ai传输所引起的错误概率。 如果先验概率 是等概率的， ，则由式(6-10)得 (6-11) (6-12) 式(6-11)表明，在等先验概率分布情况下，译码错误概率可用信道矩阵中的元素 求和来表示。求和是除去每列对应于 的那一项后，求矩阵中其余元素之和。 例6.3 已知信道矩阵 根据极大似然译码准则，选择译码函数 因为在矩阵的第一列中 ＝0.5为最大；第3列中 ＝0.5为最大；而在第2列中 ＝0.3（ ＝1，2，3），所以 任选a1、a2、a3都行。在输入等概率分布时采用译码函数 可使信道平均错误概率最小，平均错误概率为： 若选用前述译码函数 则得平均错误概率 可见， 。 若输入不是等概分布，其概率分布为 ＝ ， ＝ ， ＝ ，根据极大似然译码准则仍可选择译码函数为 ，计算其平均错误概率为： 但采用最小错误概率译码准则，它的联合概率矩阵[ ]为 所以得译码函数为 计算平均错误概率 可见， ，所以输入不是等概分布时极大似然译码准则的平均错误概率不是最小。 平均错误概率PE与译码规则(译码函数)有关，而译码规则又由信道的特性决定。信道中的噪声导致输出端发生错误，并使接收到输出符号后，对发送符号具有不确定性。而这种不确定性可由 来度量，因此PE与信道疑义度 是有一定关系的，它们的关系满足下式 其中H(PE)是错误概率PE的熵，表示产生错误概率PE的不确定性。这个重要的不等式是由费诺首先 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 的，所以又称费诺不等式。它告诉人们：接收到 后关于 的平均不确定性可分为两部分，第一部分是指接收到 后是否产生PE错误的不确定性H(PE)；而第二部分表示当错误PE发生后，到底是哪个输入符号发送而造成错误的最大不确定性，为PElog(r-1) (其中 是输入符号集的个数)。若以H(X|Y)为纵坐标，PE为横坐标，函数H(PE)+PElog(r-1)随PE变化的曲线如图6.5所示。从图中可知当信源、信道给定时，信道疑义度H(X|Y)就给定了译码错误概率的下限。 图6.5 费诺不等式曲线图 6.1.4错误概率与编码方法 上一节已说明：当消息通过有噪信道传输时发生错误的概率与译码规则有关。一般来说，当信道给定即信道矩阵给定，不论采用什么译码规则，PE都不会等于或趋于零(除特殊信道外)。 例如，在如图6.6所示的二元对称信道中，若选择极大似然译码准则进行译码，使 ， 则总的平均错误概率（假设输入是等概率分布）为 =0.99 图6.6 某二元对称信道 对于一般数据传输系统来说(例如数字通信，数据传输)，这个错误概率已经相当大了。一般要求系统的错误概率在10-6~10-9的范围内，有的甚至要求更低的错误概率。 那么，在上述统计特性的二元信道中，能否有办法使错误概率降低呢? 实际经验告诉人们，只要在发送端把消息重复发几遍，就可使接收端接收消息时错误减小，从而提高通信的可靠性。 如在二元对称信道中，当发送符号0时，不是只发一个0而是连续发三个0；同样发送符号1时也连续发送三个l。这是一种最简单的重复编码，于是信道输入端有两个码字000和111。但在输出端，由于信道干扰的作用，各个码元都可能发生错误，则有8个可能的输出序列（如图6.7所示)。显然，这样一种信道可以看成是三次无记忆扩展信道。其输入是在8个可能出现的二元序列中选两个作为符号，而输出端这8个可能的输出符号都是接收序列。这时信道矩阵为 (1 (2 (3 (4 (5 (6 (7 (8 没有使用 的码字 用作消息 的码字 输出端 接收序列 000 111 图6.7 简单的重复编码 根据极大似然译码规则(假设输入是等概率的)，可得简单重复编码的译码函数为 根据式(6-11)计算得译码后的错误概率为 其中C={000,111}={a1,a8}。 也可以采用“择多译码”的译码规则，即根据输出端接收序列中0多还是1多。如果有两个以上是0则译码器就判决为0，如果有两个以上是1则判决为1。根据择多译码原则，同样可得到 可见，择多译码准则与极大似然译码准则是一致的。 与原来 比较，显然这种简单重复的编码方法(现在n＝3，重复三次)，已把错误概率降低了接近两个数量级。这是因为现在消息数M＝2，根据编码和译码规则使输入符号a1和四个接收序列（(1，(2 ，(3，(5）对应。而a8与另四个接收序列（(4， (6，(7，(8）对应。这样，当传送符号（a1或a8）时，若符号中有一位发生错误，译码器还能正确译出所传送的消息。但若传输中发生两位或三位错误，译码器就会译错。所以这种简单重复编码方法可以纠正发生一位的错误，译错的可能性变小了，因此错误概率降低。 显然，若重复更多次n＝5，7，…一定可以进一步降低错误概率，可算得 可见，当n很大时，使PE很小是可能的。但这里带来了一个新问题，当n很大时，信息传输率就会降低很多。把编码后的信息传输率(也称码率)表示为 （6-13） 若传输每个码符号平均需要t秒钟，则编码后每秒钟传输的信息 （6-14） 此处 是输入消息(符号)的个数，log 表示消息集在等概率条件下每个消息(符号)携带的平均信息量(比特)， 是编码后码字的长度(码元的个数)。 根据式(6-13)，可对上述重复编码方法计算信息传输率，设 ＝1秒，M＝2, 则 当n＝1(无重复)时, 当n＝3(重复三次)时, 当n＝5时 …… 当n＝11时 可以看到，尽管重复编码可使PE降低很多，但同时也使信息传输率降得很低。这个矛盾能否解决，能不否找到一种更好的编码方法，使PE相当低，而 却保持在一定水平呢?从理论上讲这是可能的。这就是下节要讲到的香农第二基本定理。 先看一下简单重复编码的方法为什么使信息传输率降低? 在未重复编码以前，输入端是有两个消息(符号)的集合，假设为等概率分布则每个消息(符号)携带的信息量是log ＝1(比特／符号)。 简单重复( ＝3)后，可以把信道看成是三次无记忆扩展信道。这时输入端有8个二元序列可以作为消息( a1，… ，a8)，但是这里只选择两个二元序列作为消息 ＝2。这样每个消息携带的平均信息量仍是1比特，而传送一个消息需要付出的代价却是三个二元码符号，所以 就降低到1/3 (比特／码符号)。 发送消息 接收消息 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 图6.8 二元对称信道的三次扩展信道 由此得到一个启发，如果在扩展信道的输入端把8个可能作为消息的二元序列都作为消息， ＝8，则每个消息携带的平均信息量就是log ＝log8＝3比特，而传递一个消息所需的符号数仍为三个二元码符号，则 就提高到1比特／码符号。这时，信道如图6.8所示。 现在，采用的译码规则将与前不同，只能规定接收端8个输出符号序列(j与ai一一对应。这样，只要符号序列中有一个码元符号发生错误就会变成其他所用的码字，使输出译码出现错误。只有符号序列中每个符号都不发生错误才能正确传输。所以得到正确传输的概率为 ，于是错误概率为 这时PE反比单符号信道传输的PE大三倍。 此处看到这样一个现象：在一个二元信道的 次无记忆扩展信道中，输入端有2n个符号序列可以作为消息。如果选出其中的 个作为消息传递，则 越大，PE和R也越大; 越小，PE和R也越小。 若在三次无记忆扩展信道中，取 ＝4，取如下4个符号序列作为消息 按照极大似然译码规则，可计算出错误概率为 与 ＝8的情况比较，错误概率降低了，而信息传输也降低了，即 再进一步看，从 ＝ ＝8个符号序列中取 ＝4个作为消息可以有70种选取方法。选取的方法(编码的方法)不同，错误概率是不同的，现在来比较下面两种取法： M=4 第I种选法 M=4 第II种选法 已求得第Ⅰ种选法的错误概率为 用极大似然译码规则，计算出第II种选法的错误概率为 比较这两种选法可知第II种码要差些(两者 相同)。对于第I种码来说，当接收到发送的消息中只要任一位发生错误时，就可判断消息在传输中发生了错误，但无法判断是哪个消息发生了什么错误。而对第II种码来说，当发送消息“000”传输时其中任一位发生错误，就变成了其他三个可能发送的消息，根本无法判断传输时有无发生错误。可见，错误概率与编码方法有很大关系。 现在再考察这样一个例子。若信道输入端所选取的消息数不变，仍取 ＝4，而增加码字长度，即增大 ，取 ＝5。这时信道为二元对称信道的五次无记忆扩展信道。这个信道输入端可有 ＝32个不同的二元序列，选取其中4个作为发送消息。这时信息传输率为 这4个码字的选取采用下述编码方法： 设输入序列 , ，其中 为ai序列中第k个分量，若ai中各分量满足方程 就选取此序列ai作为码字(其中 为模2和运算)，译码仍采用极大似然译码规则。选用此码，接收端译码规则能纠正码字中所有发生一位码元的错误，也能纠正其中两个二位码元的错误，所以可计算得正确译码概率为 错误译码概率为 将这种编码方法与前述 ＝3， ＝4的两种编码方法相比，虽然信息传输率略降低了一些，但错误概率减少很多。再拿此码与 ＝3， ＝2的重复码比较，它们的错误概率接近于同一个数量级，但此码的信息传输率却比 ＝3， ＝2的重复码的信息传输率大。因此采用增大 ，并适当增大 ，选取合适的编码方法，既能使PE降低，又能使信息传输率不减少。 总之，尽管从直观上看，在有噪信道上信息传输的可靠性与信息传输率之间是矛盾的，要提高可靠性就必须牺牲传输率，也就是增加重复传输的次数。但实际上，只要码长 足够长时，合适地选择 个消息所对应的码字，就可以使错误概率很小，而信息传输率保持在一定水平上。那么，人们不禁要问，信道信息传输率最高能达到什么样的水平？最小平均错误译码概率又能小到什么程度？申农第二定理给出了准确的 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 。 6.1.5 抗干扰信道编码定理及逆定理 定理6.1 有噪信道编码定理 设离散无记忆信道[X,P(y|x),Y], P(y|x)为信道传递概率，其信道容量为C。当信息传输率RC时，则无论码长n多长，均找不到一种编码2nR，使译码错误概率任意小。 定理6.1和定理6.2统称为申农第二定理，它是一个关于有效编码的存在性定理，它具有根本性的重要意义，它说明错误概率趋于零的好码是存在的。它有助于指导各种通信系统的设计，有助于评价各种通信系统及编码的效率。申农1948年发表申农第二定理后，科学家就致力于研究信道中的各种易于实现的实际编码方法，赋予码以各种形式的代数结构，出现了各种形式的代数编码、卷积码、循环码等。 6.1.6 检错与纠错的基本原理 在申农第二定理发表后，很长一段时间内人们都在探寻能够简单、有效地编码和译码的好码。由此形成了一整套纠错码理论。在此只简单地介绍检错和纠错的一些基本概念及基本原理。 在信息处理过程中，为了保持数据的正确性应对信息进行编码使其具有检错纠错能力，这种编码称为语法信息编码。它的基本思想是引入剩余度，在传输的信息码元后增加一些多余的码元，以使信息损失或错误后仍能在接收端恢复。 通常将要处理的信息称为原信息，将原信息转化为数字信息后再进行存储、传输等处理过程称为传送。工程上最容易实现的是二元数字信息（或二元码信息）的传送。所谓二元数字信息就是由二元数域F2={0,1}中的数字0与1组成的数组或向量。 F2中的加法运算为： F2中的乘法运算为： 通常用同样长度的二元数组代表一个信息集合中的信息。例如，可以用32个长为5的二元数组代表26个英文字母与6个标点符号，表示方法如表6.1所示。这样任何一篇英文文章都可以用长为5的二元数字信息表示。 表6.1 长为5的二元数组代表32个字符 二元数组 代表的字母或符号 00000 空格 00001 a 00010 b … … 11010 z 11011 ， 11100 . 11101 ？ 11110 ！ 11111 － 数字信息在传送过程中会受到各种可能的干扰而出现错误，这样收到的信息可能就不是传送的原信息。为了使原信息能正确地传送到接收方，可以采用各种技术上的措施，但更有效的做法是在采用各种技术措施的同时，在信息传送前进行一次抗干扰编码，再传送抗干扰编码后的数字信息。抗干扰编码有检错编码与纠错编码，检错编码是检查有无错误发生的编码，纠错编码是能纠正已发生错误的编码。下面介绍两个简单的检错编码的例子。 例6.4 设原信息是长为5的二元向量 ，在传送前编码如下： 其中求和在F2中进行，因此( (c)的6个分量之和为0。传送( (c)，设收到向量是 ，如果 ，则在传送过程中一定发生了错误，可能是0错成1，也可能是1错成0，且有奇数个分量发生了错误；但如果 ，则传送过程可能没有发生错误，也可能发生了偶数个错误。如果技术上能保证在传送过程中至多发生一个错误，则接收方就可以检查出有无错误发生。这种检错编码叫做奇偶校验码。 在双向信息的情况下，即接收方也可以传送信息给发送方，当接收方检查出在传送过程中有错误发生时，就可以通知发送方重发一次信息。但在单向信道的情形下，即使收信者知道发生了错误，也无法得到正确信息。例如，将一组已经过检错编码的数字信息存入计算机后，原始数字信息不再保存，过一段时间，打开计算机取出这组信息后，检查有错误发生，但也无法知道正确的信息。因此，有必要对信息进行纠错编码，从而纠正已发生错误的编码，译出原信息。 例6.5（汉明校验码）在被编码信息中加入m个奇偶校验位，让它们分布在码字的20、21、…、2(m-1)位，从而将k位被编码信息均匀拉长到k+m =2m-1位，就得到了汉明校验码。 在汉明校验码中，每个码元（包括校验位）的位置按从右向左的顺序从1开始编号，其编号可以表示为2的最小幂之和，如1=20，2=21，3=20+21，4=22，…，见表6.2，从而确定该码元由哪些校验位来校验；反之，也就确定了每个校验位校验哪些码元（数据位）。如果取偶校验，该校验位的值应该是这些码元（数据位）值之和。这样，当传送正确时，每个校验位与其所校验的码元（数据位）值之和应该为0；不为0就是该校验位或其所校验的码元（数据位）中有出错的。如果是其中一个数据位出错，由于该数据位被多个校验位校验，那就会有多组校验出错，这些校验位共同校验的那个数据位一定出错了，从而可以纠正那个错误。反过来，如果只有一组出错，即某校验位与其所校验的码元出错，就一定是该校验位出错，也可以纠正。所以，汉明校验码可以检查出多位错误，能纠正一位错误。m个奇偶校验位能校验的最大位为20+21+…+2(m-1)＝2m-1。 表6.2 编号的最小幂之和（m=4） 编 号 码位 最小幂 分解 编 号 码位 最小幂 分解 编 号 码位 最小幂 分解 1 P1 20 6 D2 21+22 11 D 6 20+21+23 2 P2 21 7 D3 20+21+22 12 D7 22+23 3 D0 20+21 8 P4 23 13 D8 20+22+23 4 P3 22 9 D4 20+23 14 D9 21+22+23 5 D 1 20+22 10 D5 21+23 15 D10 20+21+22+23 以m=4为例，码字最长为15位，被编码信息最长为11位。设4个校验位为P4P3P2P1， 原信息位为D10D9D8D7D6D5D4D3D2D1D0，汉明校验码为 H15H14H13H12H11H10H9H8H7H6H5H4H3H2H1 汉明校验码分别按如下位置放置11个信息位和4个校验位： D10D9D8D7D 6D 5D 4P4D3D2D 1P3D0P2 P1 以偶校验为例，求信息11110100110的汉明校验码。 (1) 编码 只须确定校验码。由表6.2按以下规则定义汉明校验位： P1= H1= D0+ D1+ D3+ D4+ D6+ D8+ D10=0+1+0+0+0+1+1=1 P2= H2= D0+ D2+ D3+ D5+ D6+ D9+ D10=0+1+0+1+0+1+1=0 P3= H4= D1+ D2+ D3+ D7+ D8+ D9+ D10=1+1+0+1+1+1+1=0 P4= H8= D4+ D5+ D6+ D7+ D8+ D9+ D10=0+1+0+1+1+1+1=1 即校验位P1的值由带有20的编号所对应的码元（自己除外）之和来确定，P2的值由带有21的编号所对应的码元（自己除外）之和来确定，P3的值由带有22的编号所对应的码元（自己除外）之和来确定，P4的值由带有23的编号所对应的码元（自己除外）之和来确定。该汉明校验码的取值如下表： H15 H14 H13 H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 D10 D9 D8 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 （2）校验 在本例中，若收到码字为111101010111011，容易验证，P1和P4与被其校验位之和为0，P2和P3与被其校验位之和为1，即 P1+D0+D1+D3+D4+D6+D8+D10=0 P4+D4+D5+D6+D7+D8+D9+D10=0 P2+D0+D2+D3+D5+D6+ D9+D10=1 P3 +D1+D2+D3+D7+D8+D9+D10=1 可判断该校验码有错。把收到的码字111101000110001和已知编码信息的汉明校验码比较，不难发现，这里第2位错，第4位也错，有多于一个以上的错误，所以汉明校验码不能纠错。 若收到码字为101101010110001，同理可验证P1与被其校验位之和为0， P2、P3和P4与被其检验位之和为1，可判断该校验码有错，而且它们共同检验的是D9和D10。在只有一位出错的情况下，由于P1与其所校验的码位之和为0，且D10被P1所校验，因此D10不会出错。这样，可判断D9出错，可以判断是该位出错，把它由1改为0。 （3）译码 从汉明码中去掉校验位，就恢复为原信息。本例中，去掉1、2、4、8位就得到11110100110。 这里只介绍了汉明码编码、校验和译码（得到原信息）的实际操作。汉明码是一种能纠一位错、检多位错、高效的重要分组线性码，更多的内容可参考相关的文献。 定义6.8 设原信息集合是F2上k维向量组成的向量空间Vk，σ是Vk到Vn的一个单射，n>k则称Vk的全体象C= σ（Vk）为码，C中的每一个n维向量为码字，码字的分量称为码元。当任一码字在传送过程中有不多于t个错误发生时，如果收信方可以检查出有无错误发生，则称这个码C是可以检查t个差错的检错码，并称σ为检错编码；如果收信方可以从收到的字正确译出发信方发送的码字，则称码C是可以纠正t个差错的纠错码，并称σ为纠错编码。称k为信息长度，n为码长， 为码C的信息率。 在例6.4中， σ ： |( 就是一个从V5到V6的能检一个差错的检错编码，而且C=σ(V5) ( V6。 这里信息率的概念与前面提到的信息传输率的概念是一致的。一般地，信息率越高，检错或纠错的能力就越大，而且编码和译码都比较简单的码就是“好”码。 定义6.9 设X=(x1, x2,…, xn)，Y=(y1, y2,…, yn)，xi(F2，yi(F2，i=1,…, n，称X和Y对应分量不相等的分量个数为X和Y的汉明（Hamming）距离，记为d(X, Y)。 记 则 d(X, Y)= d(x1, y1)+ d(x2, y2)+…+ d(xn, yn) 容易证明以下定理。 定理6.3 设X和Y是长为n的二元码字，则 （1） （非负且有界性） （2）d(X, Y)=0当且仅当X=Y（自反性） （3）d(X, Y)= d(Y, X)（对称性） （4） （三角不等式） [证明] 由定义6.9可知，（1）（2）（3）显然成立。只需证（4）。 ①若X=Z，则d(X, Z)=0，而d(X, Y)≧0, d(Y, Z)≧0，故d(X, Z)≦d(X, Y)+ d(Y, Z)。 ②当X≠Z时，对其分量，若xi≠zi ，一定有xi≠yi或yi≠zi，这时，d(xi, zi)=1, d(xi, yi)与d(yi, zi)中至少有一个为1，故d(xi, zi)≦d(xi, yi)+ d(yi, zi)；若xi＝zi，则d(xi, zi)=0，而d(xi,yi)与d(yi, zi)都≧0，故 d(xi, zi)≦d(xi, yi)+ d(yi, zi)；由定义6.9有d(X, Z)≦d(X, Y)+ d(Y, Z)。证毕。 定理6.3表明汉明距离具有一般距离的性质。 设收到字A，在所有码字中，如果c是与A的汉明距离最小的码字，即c是发生传送错误分量个数最少的码字而成为A的，从而在所有码字中，c是前向传送概率最大而成为A的码字，因此按极大似然译码准则，应将A译为c，即将A译成与A的汉明距离最小的码字。这样译码避免了计算概率，而只要数一数所有与码字A的对应分量不相等的分量个数，因此在二元对称信道中，最小汉明距离译码准则等于极大似然译码准则。在任意信道中也可采用最小汉明距离译码准则，但它不一定等于极大似然译码准则。 例6. 6 设码C=(0000,0011,1000,1100,0001,1001)，在二元对称传送中，如果收到A=0111，试问根据极大似然译码法，应将A译为哪一个码字？ [解] 计算码C中每一个码字与A的汉明距离如下： d(0111,0000)=3，d(0111,0011)=1，d(0111,1000)=4， d(0111,1100)=3，d(0111,0001)=2，d(0111,1001)=3， 由于码字0011与A的汉明距离最小，从而根据极大似然译码法应将A=0111译为0011。 通过例6.6可以发现在码字的个数较少，码长较小的情况下，译码是容易实现的；而当码字的个数很大（如军事通信中码字一般多达2100个），上述译码方法几乎是不可能实现的。 定义6.10 设码C是至少包含2个码字的码，称 为码C的极小距离。 若码长为n，极小距离为d的码 C含有m个码字，则称C是(n, m, d)码。 在码长为5的码C=（00000，00011，00111，11111）中，由于d(00011,00111)=1，而其他任何两个不同码字的汉明距离都大于或等于2，故d(C)=1，从而C是(5,4, 1)码。 定理6.4 设C是码长为n的二元码。 （1）若d(C)( t+1，则C是可以检查t个差错的检错码；若d(C) = t+1，则C是不能检查t+1个差错的检错码； （2）若d(C)(2t+1，则C是可以纠正t个差错的纠错码；若d(C)=2t+1，则C是不能纠正t+1个错误的纠错码。 定理6.4说明（证略），对于二进制码组而言，码组之间的最小距离是衡量该码组检错和纠错能力的重要依据。也就是说，在一般情况下，码组的最小汉明距离d0与检错和纠错能力之间满足下列关系： （1）当码组用于检测错误时，如果要检测e个错误，那么 d0(e+1 这个关系可以利用图6.9（a）予以说明。在图中用A和B分别表示两个码距为d0的码组，若A发生e个错误，则A就变成以A为球心、e为半径的球面上的码组，为了能将这些码组分辨出来，它们必须与距离其最近的码组B有一位的差别，即A和B之间的最小距离为d0(e+1。 （2）当码组用于纠正错误时，如果要纠正 个错误，那么 d0( 2t+1 这个关系可以利用图6.9（b）予以说明。在图中用A和B分别表示两个码距为d0的码组，若A发生t个错误，则A就变成以A为球心、t为半径的球面上的码组；若B发生t个错误，则B就变成以B为球心、t为半径的球面上的码组。为了在出现t个错误以后，仍能够分辨出A和B，A和B之间的距离应大于2t，最小距离也应当使两球体表面相距为1，即满足不等式d0(2t+1。 （3）如果码组用于纠正t个错，同时检测e个错，且t(e，那么 d0( t+e+1 这个关系可以利用图6.9（c）予以说明。在图中用A和B分别表示两个码距为d0的码组，当码组出现t个或小于t个错误时，系统按照纠错方式工作；当码组出现大于t个而小于e个错误时，系统按照检错方式工作；若A发生t个错误，B发生e个错误时，既要纠正A的错误，又要检测B的错误，则A和B之间的距离应大于t＋e，即满足不等式d0( t+e+1。 图6.9 检（纠）错能力的几何解释 6.2 二元线性码 根据极大似然译码法或汉明距离译码法，都要将接收到的字A与码C中的每一个码字结合计算前向传送概率或汉明距离，当n较大或码字较多时，译码工作量十分巨大。因此，研究并构造具有很好数学结构的码具有非常重要的意义。本节讨论的线性码是最基础、最重要的码。 6.2.1 有限域上的线性空间 在线性代数中，学习了实数域R上的向量空间V及其性质，将实数域R具体到有限域F2，向量空间及其性质当然也成立。有时又将向量空间称为线性空间。显然 是二元域F2上的n维线性空间。 例如， C={(0,0)}是0维线性空间, 是F2上的2维线性空间， 是F2上的3维线性空间。 定义6.11 设C是F2上n维线性空间V的非空子集，如果C也是F2上的线性空间，则称C是V的子空间。 例如，C1={(0,0),(0,1)}是 的子空间， 是 的子空间。 线性代数中已经证明，F2上的线性空间V的子集C是线性子空间的充要条件：任给X，Y∈C，任给k1，k2∈F2，都有k1X＋k2Y∈C。 定义6.12 设 ， ，称 为X与Y的内积；如果X(Y=0，则称X与Y正交。 定理6. 5 设C是 上线性空间的子空间，令 则 是 的子空间（称为C的正交补子空间），且 。 [证明] 由于 ，则 从而 ，即 是 的子空间。 设 ，(1, (2,…, (k是C的一组基，则 的充要条件是： 即 ，其中 ，由于A的秩为 ，故线性方程组 的基础解系含有 个解向量，即 ，从而有： 证毕。 例如，C={(0,0),(0,1)}是 的1维子空间，它的正交补子空间 ={(0,0),(1,0)}，且 。再如, C={(0,0,0)}是 的0维子空间， = ，且 。 6.2.2 线性码的生成矩阵与校验矩阵 定义6. 13 称 的任一子空间C是长为n的线性码，并称子空间C的维数为线性码C的维数，仍记为dimC。并记长为n，维数为k的线性码为 线性码。 设 是线性空间 的子空间C的正交补子空间，则 也是长为n的线性码，称 是线性码C的对偶码；当 时，称C是自对偶码。 定理6. 6 设C是长为n的二元线性码，则 (1) C恰好含有个码字； (2) 当C是自对偶码时， 。 [证明] (1) 设 ，即C是F2上 维子空间，设 是C在F2上的一组基，则C中每个码字c可由 惟一地线性表示为： 其中 。由于每个(i恰好有2种不同取值，从而 共有2k 种不同的取值，而每一种不同取值对应的码字c也不同，故C恰好含有2k 个码字。 (2) 由于C是自对偶码，则，故，又由定理6.5知， 故 证毕。 例如， 是[3，3]线性码，dim =3， 共有23=8个码字；而C1={(0,0),(0,1)}是[2，1] 线性码，dimC1=1，共有21=2个码字；而 ，是[2，1] 线性码， ，也有2个码字。再如，C2={(0,0)，(1,1)}是[2，1]线性码，共有21=2个码字，且是自对偶码， 。 定义6. 14 设C是F2上的 线性码，α1, α2，…，αk是C在F2上的一组基，称 为 线性码 的生成矩阵。 因为α1, α2，…，αk是C在F2上的一组基，所以任给c∈C，存在惟一一组常数λ1, λ2,…, λk∈F2,使 c=λ1α1+λ2α2+…+λkαk=(λ1, λ2,…, λk)G 反之，任给一组常数λ1, λ2,…, λk∈F2，由于C是F2上的 线性空间，故 λ1α1+λ2α2+…+λkαk=(λ1, λ2,…, λk)G∈C 所以，可以定义G是 线性码 的生成矩阵。 若C是 线性码，由于 也是长为n的线性码，且 ，从而 是 线性码。设h1=(h11,h12,…,h1n), h2=(h21,h22,…,h2n), …, hn-k=(hn-k,1, hn-k, 2, …, hn-k , n)是 的基，则 是 的生成矩阵。 定理6.7 设C是 线性码， 是C的对偶码 的生成矩阵，对，则 的充要条件是 。 [证明] (1) 若 ，由于 ，则 从而有 (2) 若 ，对 ，则存在 ，使a=(λ1, λ2,…, λn-k)H，从而 与 中每个向量正