武汉理工大学第二章辅导信息理论编码

1、第5章 有噪信道编码5.1 基本要求通过本章学习，了解信道编码的目的，了解译码规则对错误概率的影响，掌握两种典型的译码规则：最佳译码规则和极大似然译码规则。掌握信息率与平均差错率的关系，掌握最小汉明距离译码规则，掌握有噪信道编码定理（香农第二定理）的基本思想，了解典型序列的概念，了解定理的证明方法，掌握线性分组码的生成和校验。5.2 学习要点5.2.1 信道译码函数与平均差错率5.2.1.1 信道译码模型从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为F。信道译码模型如图5.1所示。DMC信道译码图5.1 信道译码模型5.2.1.2 信道译码函数信道译码函数是从输出符号集合到输入符号

2、集合的映射：，其含义是：将接收符号译为某个输入符号。译码函数又称译码规则。5.2.1.3 平均差错率在信道输出端接收到符号时，按译码规则将译为，若此时信道输入刚好是，则称为译码正确，否则称为译码错误。的译码正确概率是后验概率： （5.1）的译码错误概率： （5.2）平均差错率是译码错误概率的统计平均，记为： （5.3）5.2.2 两种典型的译码规则两种典型的译码规则是最佳译码规则和极大似然译码规则。5.2.2.1 最佳译码规则使达到最小的译码规则称为最佳译码规则。这种规则是按后验概率最大原则定出的，所以又称最大后验概率译码规则。 （5.4）上式中最大后验概率条件可等价成最大联合概率条件。将两边

3、乘以，变换为。因此，最佳译码规则又可表示成： （5.5）因为使用最大联合概率条件，所以又称为最大联合概率译码规则。5.2.2.2 极大似然译码规则按最大转移概率条件来确定的译码规则，称为极大似然译码规则： （5.6）虽然极大似然译码规则的平均差错率不是最小，不是最佳的，但最易找出。可以证明，当信道输入等概时，极大似然译码规则与最大联合概率译码规则等价，此时极大似然译码规则也是最佳的。5.2.3 信道编码对平均差错率和信息率的影响信道编码（或称纠错编码）是靠增加冗余码元来克服或减轻噪声影响的。冗余是相对于信息的表示而言，但是对提高传送可靠性来说，冗余码元却提供了极宝贵的可靠性信息。以下以两种简单

4、信道编码方法来说明信道编码对平均差错率和信息率的影响。5.2.3.1 “简单重复”编码日常中人们可以通过重复某句话使别人听得更清楚。数字通信中，将符号重复传几次，也会提高传送可靠性。例如，“重复2次”编码，如图5.2所示。信道译码信道译码图5.2 “重复2次”编码编码规则为扩展信道的转移矩阵为按极大似然译码规则得译码函数：即信道编码之后的信息率为 /码元 （5.7）若信源等概率分布，则 /码元 （5.8）其中代表信源消息（符号）个数。无编码 /码元 “重复2次”编码 /码元 /码元 /码元 随着“重复”次数的增加，下降，但也跟着下降。即信息传输的有效性和可靠性是矛盾的。5.2.3.2 对符号串

5、编码对信源的符号串进行编码，即增多消息个数，同时增大码长，有可能使平均差错率降低到要求的范围以内，而又能使信息率降低得不多。例如，取（2次扩展信源）、。4个消息记为编码函数为译码采用极大似然规则。编译码示意图见图5.3所示。图5.3 、 的编译码示意图5次扩展信道编码后的信息率和平均差错率分别为 /码元与“重复2次”编码相比，略有增加，处在同一数量级。因此，增大码长和适当增多消息个数，对兼顾（可靠性）和（有效性）的要求是有效的。5.2.4 最小汉明距离译码规则5.2.4.1汉明距离两个等长符号序列和之间的汉明距离，记为，是与之间对应位置上不同符号的个数，用来定量描述符号序列之间的“相似”程度。

6、5.2.4.2汉明距离与信道编码性能的关系码是码字的集合，码字则是由码元组成的符号序列。假如是等长码，则中任意两个不同码字之间的汉明距离或码间距离为码的最小码间距离定义为最小码间距离是衡量码的性能的重要参数，码的小，说明其中有些码字受干扰后容易变为另一码字，译码时就会出错。因此，信道编码在选择码字时，应尽量使码的最小码间距离大一些为好。对于二元对称信道，设信源有个消息，输入和输出符号集分别为和，其次扩展信道的入口符号集和出口符号集中都含有个长二元符号串，即从中选择个符号串当作码字组成码：按极大似然译码规则进行译码时，可以推导出等价于以下规则，称为最小（汉明）距离译码规则： （5.9）其含意是：

7、将接收序列译为与之最相似的输入序列（码字）。5.2.5有噪信道编码定理（香农第二定理）5.2.5.1有噪信道编码定理若信道是离散、无记忆、平稳的，且信道容量为，只要待传送的信息率，就一定能找到一种信道编码方法，使得码长足够大时，平均差错率任意接近于零。有噪信道编码定理实际上是一个存在性定理，它指出：在时，肯定存在一种好的信道编码方法，用这种好码来传送消息可使逼近零。但香农并没有给出具体编码方法。对有噪信道编码定理的证明要用到联合典型序列。所谓典型序列，是指那些平均自信息量逼近熵的序列。联合典型序列，是指那些平均联合自信息量逼近联合熵的序列。离散无记忆信源发出长序列，若 （5.10）则称为的典型

8、序列，否则称为的非典型序列。若和分别是和的长典型序列，且 （5.11）则称序列对为与的联合典型序列，否则称为非联合典型序列。5.2.5.2有噪信道编码逆定理若信道是离散、无记忆、平稳的，且信道容量为，如果信息率，则肯定找不到一种信道编码方法，使得码长足够大时，平均差错率任意接近于零。对有噪信道编码逆定理的证明，要用到Fano不等式。Fano不等式： （5.12）式中是信道输入符号个数。5.2.6 线性分组码5.2.6.1 基本概念信道编码的目的是为了降低平均差错率。纠错编码理论几乎与信息论同时创立，创始人是汉明（R.W.Hamming），他与信息论创始人香农都在贝尔实验室工作。纠错编码的基本思

9、路是在信息序列中引入可控冗余，或称校验码元，组成一个相关的码元序列码字，译码时利用码元之间的相关性质来检测错误和纠正错误。分组码：先将信息序列分成个符号一组，称为信息组，然后在信息组中加入一些校验码元组成长码字，由此得到的码称为分组码，校验位数目为。线性码：线性码满足线性特性，即码中任意两个码字的和仍为码字。否则为非线性码。循环码：循环码是线性码的一个子集。循环码中任一码字循环移位后仍为该码的码字。否则为非循环码。5.2.6.2 生成矩阵和校验矩阵编码函数可用矩阵表示成 （5.13）其中是K维信息组行矩阵，是N维码字行矩阵，是码的生成矩阵。 （5.14） （5.15）通过生成矩阵，可将信息组变

10、换为相应的码字。如果码字的前（或后）位照搬信息组的个信息元，这样形成的码称为系统码。对于前位为信息元的系统码，生成矩阵可分块成 （5.16）校验方程的矩阵形式则为或 （5.17）式中为一致性校验矩阵，为校验位数目。5.2.6.3 汉明距离和码的纠检错能力的关系(1) 一个码能够检测出个错误的充要条件是；(2) 一个码能够纠正个错误的充要条件是；(3) 一个码能够纠正个错误，同时又能够检测出个错误的充要条件是和。其中，表示码的最小汉明距离，是衡量其纠、检错能力的重要参数。5.2.6.4 伴随式与伴随式译码用一致性校验矩阵对接收序列进行检验，检验结果记为，则 （5.18）式中为发送码字。如果，则表

11、明有错误存在。是传输是否出错的标志，称为伴随式。称为差错图样。当码字第位发生错误时，否则。通过接收序列可以确定发送码字的估计值： （5.19）教材习题参考答案5.1 译码规则与错误概率5.1.1 （陈杰，红皮书，p139，例5.1）例5.1 已知信道矩阵，求。 解：根据极大似然译码准则选择译码函数B B： 又设输入符号为等概率分布 则有 =0.567 若按下述译码函数A计算平均错误概率 得 可见 (平均错误概率)，即得以下结论：（1） 平均错误概率与译码规则有关；（2） 极大似然译码准则B优于A。5.1.2（原5.3）设码为，用2元对称信道传送（错误概率）。如果码字概率为，试找出一种译码规则，

12、使平均差错率最小。 答案：王虹老师 5.2 两种典型的译码规则5.2.1 （原5.1） 设有DMC其转移矩阵如下 若信道输入概率为，试确定最佳译码规则和极大似然译码规则并计算出相应的平均差错率。答案：王虹老师解：， 信道的联合概率矩阵为根据最小错误概率准则（其实就是最大联合概率译码准则），在联合概率矩阵中，每列选一最大值（矩阵中带下划线的值），译为平均错误概率若根据最大似然概率译码准则，在矩阵每列中选一最大值，译为平均错误概率5.2.2（陈杰，140页）例5.3 设一离散无记忆信道的输入符号集为，输出符号集为，信道转移概率为，；，。若译码器以概率（，；，）对收到的判决为，试证明对于给定的输入分

13、布，任何随即判决方法得到的错误概率不低于最大后验概率译码时的平均译码错误概率。证明：根据最大后验概率译码准则，有，且 ，所以有 最大后验概率译码的错误概率为： 随即判决法译码的错误概率为： 所以，得证。5.3平均差错率与信道编码5.3.1（原5.2）设信源有M个消息符号，将每个符号编码成N长的二进制码字，码字从个N长二进制序列中独立、等概地选出，若采用极大似然译码规则，试分别求取在以下三种信道下的平均差错率。 答案：王虹老师5.3.2（傅详，p192） 6-8设一离散无记忆信道，其信道矩阵为 （1） 计算信道容量C。（2） 找出一个码长为2的重复码，其信息传输率为（即5个码字）。如果按最大似然

14、译码准则设计译码器，求译码器输出端的平均错误概率（输入码字为等概率分布）。（3） 有无可能存在一个码长为2的码而使 即使，如存在的话请找出来。解：（1） 因为输入码字等概率分布，这重复码，因此满足信息传输率 此信道是无记忆信道，满足 ， =1，2，25， =1，2，5解：（1）根据信道矩阵P，可知其是一对称信道，所以信道容量为 比特符号（3） 设信道的输入符号集，输出符号集，其传递信道矩阵为P，任选码长为2的重复码： ：, 因为输入码字等概率分布，这重复码，因此满足信息传输率 此信道是无记忆信道，满足 ， ， ， ， =1，2，25， =1，2，5下面给出传递概率的矩阵为：根据最大似然译码准则

15、，确定的译码规则是译成 00，译成 11，译成 22 译成 33，译成 44在选择码C重复码的情况下，因为对于其他，所以其他在输出端不会出现。可计算得 （3）存在码长为2的码，它使，也就是它使。这种码共有10种。这是因为这个离散无记忆信道具有特殊的传输概率，输入符号“0”只传输到输出符号“0”和“1”；输入符号“1”只传输到输出符号“1”和“2”；输入符号“4”只传输到输出符号“4”和“0”。因此，从（2）题的传递概率矩阵中可以看出，它可使有些 。也就是选择码长的序列作为码字时，它只传输到输出端若干个序列，而使其他传输概率为零。如（2）题中码字只传输到；只传输到；等等。为此，我们只要适当地选择

16、码长为2的5个码字，它们将输出端可能出现的25个码长为2的接受序列分割成五个互不相交的子集，每个码字只传输到所对应的子集，这样就可使等于零。 能使，码长为2的十种可选的码是：从上面码字选择的规律可以看出，当选定某一二位长序列为码字，其他码字是将第一位码元的符号增加1，第二位的码元的符号增加2而获得；或者其他码字是将第一位码元的符号增加2，而第二位码元的读好增加1而获得。 我们也可以类似卡诺图来排列，将25个的序列排列成一方块图。由于00只传输到00，01，10，11；01只传输到01，02，11，12；等等。所以图中每一序列只可能向右一格，向下一格的含四个序列的方框内传输（如箭图所示）；隔行、

17、隔列或反向的传输都为零。只要找出不相交的五个子集（即五个含四个序列的方框），选取方框左上角的序列作为码字，就可以找出这个码组。如果所选方框相交，这就不是所需的码。上述十种码中任一种码都满足如此划分的条件。00 0110 1112 1322 2331 3241 4243 4403 0424 2034 3014 1002 03 04 0020304000 01 02 334000上面种所选的码是：。我们也可以用上图来检验所选的码是否正确。5.4 汉明距离5.4.1（原5.4）码为。（1）求该码的最小汉明距离；（2）假设码字等概率分布，该码的码率；（3）若采用最小距离译码规则，那么，当接收到“100

18、00”、“01100”以及“00100”时，别译为什么码字。（4）该码能检出几位错误？能纠正几位错误？解：（1）此二元码的最小距离 （2）此二元码的码字个数，码长所以，码率 比特/码符号（4） 采用最小距离译码准则（即将接收序列译成与其码距为最小的码字）,接收序列10000与码字10010距离为1，与其码字的距离都大于1，所以 10000 译成 10010同理 01100 译成 11100 00100 译成 11100 或 00111任一个（4）因此此码，即，所以，此码能纠正所有发生一位码元的随机错误。5.4.2（傅详，186）【6-2】计算码长的二元重复码的译码错误概率。假设无记忆二元对称信

19、道中正确传递概率，错误传递概率。此码能检测出多少错误？又能纠正多少错误。若，译码错误概率是多大？解：码长二元重复码的码字是（00001，11111）。这码的最小距离。因为 所以此码用于检测错误能检测出所有发生小于等于4位码元的随机错误。 又因为 所以此码用于纠正错误能纠正出所有发生小于等于2位码元的随机错误。 可以根据最大似然译码准则的译码规律或择多译码的译码规则来计算这的二元重复码的错误概率，这两种计算结果是一致的。所以，采用择多译码的译码规则来计算，得 若，则 5.5有噪信道编码定理5.5.1（傅精，171页）【5.1】某信源按的概率产生统计独立的二元序列。（1）试求，使当时有 其中是信源

20、的熵。（2）试求当时典型序列集中含有的信源序列个数。解：（1）本题信源是一个二元信源 得 比特符号根据契比雪夫不等式，对于任意，当时有 现 ，得根据信源，其 所以 （2）序列集是所有长的典型序列的集合，根据的特性有是序列中含有的典型序列的个数。 所以当时中含有的信源序列个数为或者 5.7线性分组码5.7.1 （原5.5） 设二元线性码的生成矩阵为（1）将生成矩阵化为的形式；（2）求校验矩阵；答案：王虹老师5.7.2 （原5.6）试证线性码的最小汉明距离不大于。答案：王虹老师5.7.3 （傅详，P198）【6-12】下面是某线性二元码的全部码字： （1） 求，为何值；（2） 构造这码的生成矩阵；

21、（3） 构造这码的一致校验矩阵。解：（1）因为码字数，所以为码线性分组码（2）生成矩阵为列的矩阵，由个线性独立的码字组成。 故 (3)设信息位，则码字 所以所以 本章测验题一、填空题1. 信息传递系统的基本功能是在系统输出端准确地再现系统输入端发送的信息。但是会受到客观限制，首先_受_的限制；其次，由于_的干扰，_不可避免。2. 衡量信息传输速度大小的指标是信道的信息（传输）率，其最大值就是_，衡量信息传输可靠性的指标是_。3. 为了降低平均差错率，可先对消息_再送入信道传送，这种为降低_而进行的编码称为信道编码。4. 信道输出它与信道输入既有联系又有区别，联系的程度和区别的大小取决于_或者说

22、取决于_。5. 信道译码函数是从_到_的映射：其含义是将_译为_。译码函数又称_。二、判断题1. 译码规则取决于信道，一个信道的译码规则是唯一的。（）2. 在信道输出端接收到符号时，按译码规则将译为，若此时信道输入刚好是，则称为译码正确。（）3. 若按译码规则将译为，则平均译码错误概率是的加权平均值。（）4. 最“好”的译码规则必然使最小。（）5. 最大后验概率译码规则是最佳译码规则。（）三、选择题1. 译码规则不能由_确定A后验概率 B. 联合概率 C. 转移概率 D. 边缘概率2. 假设，信道线图如下图所示，相应的最佳译码规则为_A. B. C. D. 3. 下列说法不正确的是_A. 信道

23、输入等概时，极大似然译码规则也是最佳的B. 最大后验概率条件可无条件等价成最大联合概率条件C. 当信源统计特性未知的时候，可以使用极大似然译码规则作为译码规则D应用极大似然译码规则总可以确定译码的平均差错率4. 关于“重复N次”编码，说法不正确的是_。AN越大，信息传输率越高B“重复N次”是定长码C采用择多译码策略D能减低平均差错率5. 对信源的2元符号串进行编码，取码长为，则_A. 可供选择的码字有4个B信息率C共有4×832种不同的编码方法。D继续增加消息个数，可以降低平均差错率四、计算题1、（傅详，p191）【6-7】考虑一个码长为4的二元码，其码字为，。假设码字送入一个二元对

24、称信道（其单符号的错误概率为，并），而码字输入是不等概率分布的，其概率为 ，试找出一种译码规则使平均错误概率为最小。2、（傅详，p188）【6-5】对于离散无记忆强对称信道，信道矩阵为 试证明对于此信道，最小距离译码准则等价于最大似然译码准则。3、（傅详，p197）【6-11】设无记忆二元对称信道的正确传递概率为，错误传递概率为，对于（7，4）汉明码（如参考书1中表6.2）（1） 若码字都是等概率分布，试问什么是其最佳的译码规则。（2） 在接收端，128个接收的二元序列应该对应译成什么码字。并说明其能纠正一个码元的随机错误。（3） 在最佳译码规则下，计算此码的平均错误概率。（4） 若p=0.0

25、1,从和码率R上将（7，4）汉明码与n=7的重复码进行比较。4、（傅详，P200） 【6-14】有一组码将二位信息位编成五位长的码字，其规则如下： 信息序列 码字 00 00000 01 01101 10 10111 11 11010（1）证明此码是系统一致效验码；（2）找出其生成矩阵和一致效验矩阵；（3）对于无记忆二元对称信道（），列出其最大似然译码的译码表；（4）计算正确译码概率。5、（傅精，P203）【6-16】设一分组码具有一致效验矩阵 （1）求这分组码，共有多少个码字；（2）此分组码的生成矩阵；（3）矢量101010是否是码字；（4）设发送码字C=（001111），但接收到的序列为R

26、=（000010），其伴随式S是什么，这伴随式指出已发生的错误在什么地方，为什么与实际错误不同。五、实验题试编程实现线性分组码的编译码本章测验题参考答案一、填空题1. 传输速度 信道容量 信道噪声 传输错误2. 信道容量 平均差错率3. 编码 平均差错率4. 噪声的影响情况 信道的统计特性5. 输出符号集合 输入符号集合 接收符号 某个输入符号 译码规则二、判断题1. ×；2. ×；3. ×；4. ×；5. 三、选择题1、D 2、C 3、D 4、A 5、B四、计算题1、 解：在二元对称信道中最小距离译码准则等价于最大似然译码准则。但是，码字输入不是等概率

27、分布，所以最大似然译码准则不能使平均错误概率为最小。要使译码后平均错误概率最小只有选择最小错误概率准则进行译码。也就是比较来决定译码规则。我们将的矩阵如下列出：根据最小错误概率译码准则将接收序列译成在矩阵的每一列中为最大的那个码字。所以，得译码规则为（因为）若按最大似然译码准则来选择译码规则的话，如；也可译成或或；也可译成；等等。但其并没有将矩阵中每一列的最大元素除去，所以余下元素之和就不是最小的了，不能为最小。2、证明：设码C为M个码长为n的r元码，其码字，接收的序列为。码字与接收序列的距离仍是二序列之间对应码位上不同码元的个数。因为是强对称信道，只要与()不相同就引起错误，而其传递概率都相

28、等，即 而且强对称信道是无记忆的，所以 一般。所以当接收序列与码字的距离越大，即越大，越小时，和越小，也越小，则越小。当与的距离越小，即越小，越大，则越大。所以满足 则满足 所以最小距离译码准则是选择译码函数 使满足 则等价于最大似然译码准则是选择译码函数 使满足 证毕3、 解：（1）在无记忆二元对称信道中，所以最小距离译码准则等价于最大似然译码准则。而且码字是等概率分布，所以最大似然译码准则能使译码的平均错误概率最小。因此，此时最佳译码规则应采用最小距离译码准则。（2）根据最小距离译码准则，因为（7，4）汉明码共有16个码字，而接收端共有128个7位长的二元序列，正好分成16个集合。每个集合

29、都有8个二元接收序列，都是由码字 发生一位码元错位所变成的接收序列（共7个二元序列）和完全正确传递的一个接收序列组成。而且任一码字发生一位码元错位所变成的接收序列都不会进入其它的集合。又在这16个集合中也没有相同的接收序列，即这16个集合是不相交的。因此，采用最小距离译码就能纠正一位码元的随即错误。具体的译码见译码表。（3） （4）若p=0.01，则 码率 比特/码元而（7，1）重复码 码率 比特/码元 可见，（7，1）重复码虽然能纠正3个码元发生的随机错误，其平均错误概率减少。但同时码率（信息传输率）也减小很多。译码表接收序列 码字 接收序列 码字 接收序列 码字 接收序列 码字4、解：（1

30、）设码字，信息位为。根据码字可得 可见，码字的后三位都由其前二位线性组合得到。因此，此码是（5，2）一致效验码。（2）由码字可得 故，此码是系统一致效验码。（3）列出下列最大似然译码表 伴随式 错误图样 000 00000 111 10000 101 01000 100 00100 010 00010 001 00001 011 10100（或00011） 110 10001（或00110）因为码的最小距离，所以能纠正一位码元的错误。从译码表中可以看出所有一位码元发生错误的错误图样能被纠错，而且还有二种发生二位码元错误的错误图样能被纠错。（4）根据译码表及无记忆二元信道，所以正确译码概率 5、

31、解：（1）设码字，有 故得 所以n=6，r=3，k=3，为（6，3）分组码。码字共有个。（2）由（1）式得 所以，为信息位。设，信息位，故生成矩阵 （3）这（6，3）分组码的所有许用码字是 000000 101100 011010 111001 001111 110110 100011 010101可见矢量101010不是码字（4）因为 伴随式正好是H矩阵中第5列。根据伴随式就判断码字中发生了错误，则E=（000010）。但实际错误图样E为 C + E = R E = R + C E = （000010）+（001111）=（001101）是码字传送中发生了三位码元错误。因为此（6，3）码，所

32、以，得e = 1。根据（6，3）码伴随式所判断的错误是能纠正一位码元发生错误的错误图样。若此（6，3）码用于检测错误，也只能检测出二位码元发生错误。因此，当传输过程中码字发生了三位以上码元的错误也就无法检测出来了。五、（1）编码过程G=1 0 0 1 0 1; 0 1 0 1 1 1; 0 0 1 1 1 0; % 生成矩阵K,N=size(G); % 确定生成矩阵的大小% 下面生成所有可能的信息组：% m=zeros(K,2K); % 信息组初始化for i=0:2K-1 seq=dec2bin(i,K); for j=1:K m(i+1,j)=str2num(seq(j); endendc

33、=mod(m*G,2); 生成所有信息组对应的码字程序说明：（5） 生成矩阵G和信息组m是已知的（6） 本程序对所有的信息组进行了编码，如果只需要对特定信息组进行编码，修改m即可（7） str2num：实现字符串向数字的转换（8） mod：求模函数运行结果：所有可能的信息组为:m = 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1生成所有信息组对应的码字为：c = 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 0（2）译码过程function codeword=lincoder(H,y)% H:校验矩阵% y：接收到的矢量% codeword：估计发送的矢量，返回值r,N=size(H); % 确定校验位个数和码长s=mod(H*y',2); % 确定伴随式k=N-r; % 确定信息位个数e_common=zeros(N,k);bas=eye(k);for i=1:k e_common(1:k,