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

第5章 有噪信道编码

5.1 基本要求

通过本章学习，了解信道编码的目的，了解译码规则对错误概率的影响，掌握两种典型的译码规则：最佳译码规则和极大似然译码规则。掌握信息率与平均差错率的关系，掌握最小汉明距离译码规则，掌握有噪信道编码定理（香农第二定理）的基本思想，了解典型序列的概念，了解定理的证明方法，掌握线性分组码的生成和校验。

5.2 学习要点

5.2.1 信道译码函数与平均差错率

5.2.1.1 信道译码模型

从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为F。信道译码模型如图5.1所示。

ˆXYX信道译码 DMC F

A{a1,a2,,ar}A{a1,a2,,ar}B{b,b,,b}12s

N图5.1 信道译码模型

5.2.1.2 信道译码函数

信道译码函数F是从输出符号集合B到输入符号集合A的映射：

F(bj)a*jA，j1,2,...s

其含义是：将接收符号bjB译为某个输入符号ajA。译码函数又称译码规则。 5.2.1.3 平均差错率

在信道输出端接收到符号bj时，按译码规则F(bj)ajA将bj译为a*j，若此时信道输入刚好是

**a*j，则称为译码正确，否则称为译码错误。

bj的译码正确概率是后验概率：

P(Xa*j|Ybj)PF(bj)|bj （5.1）

bj的译码错误概率：

P(e|bj)PXF(bj)|Ybj1PF(bj)|bj （5.2）

平均差错率是译码错误概率的统计平均，记为Pe：

PeP(bj)P(e|bj)P(bj)1PF(bj)|bjj1j1ssss （5.3）

1PF(bj),bj1PF(bj)Pbj|F(bj)j1j15.2.2 两种典型的译码规则

两种典型的译码规则是最佳译码规则和极大似然译码规则。 5.2.2.1 最佳译码规则

使Pe达到最小的译码规则称为最佳译码规则。这种规则是按后验概率最大原则定出的，所以又称最大后验概率译码规则。

*F(bj)ajA,bjB （5.4） F:*P(aj|bj)P(ai|bj),aiA上式中最大后验概率条件可等价成最大联合概率条件。

*将P(a*j|bj)P(ai|bj)两边乘以P(bj)，变换为P(aj,bjP(ai,bj)。

因此，最佳译码规则又可表示成：

*F(bj)ajA,bjB （5.5） F:*P(aj,bj)P(ai,bj),aiA因为使用最大联合概率条件，所以又称为最大联合概率译码规则。 5.2.2.2 极大似然译码规则

按最大转移概率条件来确定的译码规则，称为极大似然译码规则：

*F(b)abjBjjA, （5.6） F:*P(bj|aj)P(bj|ai),aiA虽然极大似然译码规则的平均差错率不是最小，不是最佳的，但最易找出。

可以证明，当信道输入等概时，极大似然译码规则与最大联合概率译码规则等价，此时极大似然译码规则也是最佳的。

5.2.3 信道编码对平均差错率和信息率的影响

信道编码（或称纠错编码）是靠增加冗余码元来克服或减轻噪声影响的。冗余是相对于信息的表示而言，但是对提高传送可靠性来说，冗余码元却提供了极宝贵的可靠性信息。

以下以两种简单信道编码方法来说明信道编码对平均差错率和信息率的影响。 5.2.3.1 “简单重复”编码

日常中人们可以通过重复某句话使别人听得更清楚。数字通信中，将符号重复传几次，也会提高传送可靠性。例如，“重复2次”编码，如图5.2所示。

ˆ3Y3X3XU信道译码 信道译码 PY3|X3 f F {1,8} {1,2,,8}{u1,u2}{1,2,,8}

fu101000 0001 20010012

30100103

F100040110114

21115100 1005 61011016

71101107

fu2181111118

图5.2 “重复2次”编码

编码规则为

0000 f:1111扩展信道的转移矩阵为

1p3[P]3Y3|X3p按极大似然译码规则得译码函数：

2p2ppp23p2ppp24pp2p2p5p2ppp26pp2p2p7pp2p2p8p31

3p8

F(1)1F(5)1即

F(2)1F(6)8F(3)1F(7)8F(4)8F(8)810002001F100030105100信道编码之后的信息率为

40116101F8111 71108111H(U) bit/码元 （5.7） NlogM bit/码元 （5.8） NR若信源等概率分布，则

R其中M代表信源消息（符号）个数。

log221 bit/码元 Pe10 1log214R bit/码元 P“重复2次”编码 N3e310

3315N5R bit/码元 Pe10

517N7R bit/码元 Pe410

7R也跟着下降。即信息传输的有效性和可靠性是矛盾的。 随着“重复”次数的增加，Pe下降，但

无编码 N1R5.2.3.2 对符号串编码

对信源的符号串进行编码，即增多消息个数M，同时增大码长N，有可能使平均差错率Pe降低到要求的范围以内，而又能使信息率R降低得不多。

例如，取M4（2次扩展信源）、N5。4个消息记为s100,s201,s310,s411 编码函数为

f:simi1mi2iai1ai2ai3ai4ai5i1,2,3,4

ai1ai2ai3ai4ai1mi1mi2mi1mi2 mi1mi1mi2译码采用极大似然规则。编译码示意图见图5.3所示。

0000000001F0001000100 000000100010000 1000100011

0110101100F f01111010010000000011015次扩展信道 0010111101

f111000111001 011011011110110 f1011110F1010110011 f10111111110011111110100011010100

1101011011F1100011110 110101001001010 0101111001

图5.3 M4 、n5 的编译码示意图

编码后的信息率R和平均差错率Pe分别为

log42 bit/码元 551Pe1(4p520p4p8p3p2)7.86104

4N和适当增多消息与“重复2次”编码相比，R略有增加，Pe处在同一数量级。因此，增大码长

R（有效性）的要求是有效的。 个数M，对兼顾Pe（可靠性）和

R5.2.4 最小汉明距离译码规则

5.2.4.1汉明距离

两个等长符号序列x和y之间的汉明距离，记为D(x,y)，是x与y之间对应位置上不同符号的个

数，用来定量描述符号序列之间的“相似”程度。 5.2.4.2汉明距离与信道编码性能的关系

码是码字的集合，码字则是由码元组成的符号序列。假如C{c1,c2,意两个不同码字之间的汉明距离或码间距离为

,cq}是等长码，则C中任

D(ci,cj),cicj,ci,cjC

码C的最小码间距离定义为

dminminD(ci,cj)cicjci,cjC

最小码间距离dmin是衡量码的性能的重要参数，码的dmin小，说明其中有些码字受干扰后容易变为另一码字，译码时就会出错。因此，信道编码在选择码字时，应尽量使码的最小码间距离dmin大一些为好。

对于二元对称信道，设信源有M个消息{s1,s2,,sM}，输入和输出符号集分别为A{0,1}和,2N},2N}B{0,1}，其N次扩展信道的入口符号集AN和出口符号集BN中都含有2N个N长二元符号串，即

AN{1,2,B{1,2,从A中选择M个符号串当作码字组成码C：

NN

C{c1,c2,,cM}

按极大似然译码规则进行译码时，可以推导出等价于以下规则，称为最小（汉明）距离译码规则：

*NF()cC,Bjjj （5.9） F:*ND(ci,j),ciCAD(cj,j)min其含意是：将接收序列j译为与之最相似的输入序列（码字）c*j。

5.2.5有噪信道编码定理（香农第二定理）

5.2.5.1有噪信道编码定理

若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率RC，就一定能找到一种信道编码方法，使得码长N足够大时，平均差错率Pe任意接近于零。 有噪信道编码定理实际上是一个存在性定理，它指出：在RC时，肯定存在一种好的信道编码方法，用这种好码来传送消息可使Pe逼近零。但香农并没有给出具体编码方法。 对有噪信道编码定理的证明要用到联合典型序列。所谓典型序列，是指那些平均自信息量逼近熵的序列。联合典型序列，是指那些平均联合自信息量逼近联合熵的序列。

离散无记忆信源X发出N长序列xixi1xi2xiN，若

I(xi)H(X) （5.10） N则称xi为X的典型序列，否则称为X的非典型序列。

若xi和yj分别是X和Y的N长典型序列，且

I(xi,yj)NH(XY) （5.11）

则称序列对(xi,yj)为X与Y的联合典型序列，否则称为非联合典型序列。 5.2.5.2有噪信道编码逆定理

若信道是离散、无记忆、平稳的，且信道容量为C，如果信息率RC，则肯定找不到一种信道编码方法，使得码长N足够大时，平均差错率Pe任意接近于零。

对有噪信道编码逆定理的证明，要用到Fano不等式。

Fano不等式：

H(X|Y)H(Pe,1Pe)Pelog(r1) （5.12）

式中r是信道输入符号个数。

5.2.6 线性分组码

5.2.6.1 基本概念

信道编码的目的是为了降低平均差错率。纠错编码理论几乎与信息论同时创立，创始人是汉明

（R.W.Hamming），他与信息论创始人香农都在贝尔实验室工作。

纠错编码的基本思路是在信息序列中引入可控冗余，或称校验码元，组成一个相关的码元序列——码字，译码时利用码元之间的相关性质来检测错误和纠正错误。

分组码：先将信息序列分成K个符号一组，称为信息组，然后在信息组中加入一些校验码元组成N长码字，由此得到的码称为(N,K)分组码，校验位数目为rNK。

线性码：线性码满足线性特性，即码中任意两个码字的和仍为码字。否则为非线性码。

循环码：循环码是线性码的一个子集。循环码中任一码字循环移位后仍为该码的码字。否则为非循环码。

5.2.6.2 生成矩阵和校验矩阵

编码函数f可用矩阵表示成

cmG （5.13）

其中m是K维信息组行矩阵，c是N维码字行矩阵，G是码的生成矩阵。

mm1m2cc1c2mK,mi{0,1} （5.14） cN,ci{0,1} （5.15）

通过生成矩阵，可将信息组变换为相应的码字。

如果码字的前（或后）K位照搬信息组的K个信息元，这样形成的码称为系统码。 对于前K位为信息元的系统码，生成矩阵G可分块成

GIKK1001AKr0000a11a21a12a22aK21aK1a1ra2r （5.16） aKr校验方程的矩阵形式则为

cHT0或HcT0 （5.17）

式中H为rN一致性校验矩阵，rNK为校验位数目。

5.2.6.3 汉明距离和码的纠检错能力的关系

(1) 一个码能够检测出td个错误的充要条件是dmintd1； (2) 一个码能够纠正tc个错误的充要条件是dmin2tc1；

(3) 一个码能够纠正tc个错误，同时又能够检测出tdtc个错误的充要条件是

dmin2tc1和dmintctd1。

其中，dmin表示码的最小汉明距离，是衡量其纠、检错能力的重要参数。 5.2.6.4 伴随式与伴随式译码

用一致性校验矩阵H对接收序列y进行检验，检验结果记为s，则

s=yHT(c+e)HTeHT （5.18）

式中c为发送码字。如果s0，则表明有错误存在。s是传输是否出错的标志，称为伴随式。e称为差错图样。当码字第i位发生错误时，ei1，否则ei0。

ˆ： 通过接收序列y可以确定发送码字c的估计值cˆ=ye=ye （5.19） c

教材习题参考答案

5.1 译码规则与错误概率

5.1.1 （陈杰，红皮书，p139，例5.1）

0.5例5.1 已知信道矩阵P0.20.30.30.20.30.5，求pE。 0.30.4 解：根据极大似然译码准则选择译码函数B

Fb1a1 B：Fb2a3

Fba23又设输入符号为等概率分布pa则有

1 311pEpba[0.20.30.30.30.20.4]3Y,Xa3 =0.567

若按下述译码函数A计算平均错误概率pE

Fb1a1A： Fb2a2 Fba33得

pE1pba 3Y,Xa1 [0.20.30.30.30.20.5]0.600

3

可见pEpE (平均错误概率)，即得以下结论：

（1） 平均错误概率pE与译码规则有关； （2） 极大似然译码准则B优于A。

，用2元11100,01001,10010,001115.1.2（原5.3）设码为Cc1,c2,c3,c4对称信道传送（错误概率p0.01）。如果码字概率为

Pc0.50.1250.1250.25，试找出一种译码规则，使平均差错率pe最

小。 答案：王虹老师 5.2 两种典型的译码规则

5.2.1 （原5.1） 设有DMC其转移矩阵如下

121316161213P YX 131612若信道输入概率为PX0.50.250.25，试确定最佳译码规则和极大似然译码规则并计算出相应的平均差错率。 答案：王虹老师 解：

P(x1)11,P(x2)P(x3)， 24141信道的联合概率矩阵为241121161211812 11248根据最小错误概率准则（其实就是最大联合概率译码准则），在联合概率矩阵中，每列选一最大值（矩阵中带下划线的值），译为

y1x1y2x2 yx33平均错误概率

11111111PE

2412824121224若根据最大似然概率译码准则，

121P61313121616y1x113，在矩阵每列中选一最大值，译为y2x2

yx1332平均错误概率

PE1111111111 26343643625.2.2（陈杰，140页）

例5.3 设一离散无记忆信道的输入符号集为x1,,xK，输出符号集为

y1,,yJ，信道转移概率为pyjxk，k1，„，K；j1，„，J。

若译码器以概率kj（k1，„，K；j1，„，J）对收到的yj判决为

xk，试证明对于给定的输入分布，任何随即判决方法得到的错误概率不低于最大后验概率译码时的平均译码错误概率。

1,2,,K，且 证明：根据最大后验概率译码准则，有xqfyj，q1,2,,K，j1,2,,J qjkj k所以有 pxqyjpxkyjpxq,yjpyjpxk,yjpyj

pxqpyjxqpyjpxkpyjxkpyj

pyjxqpxqpyjxkpxk 最大后验概率译码的错误概率为： PE1Y,Xxqpyxpx1pyxpx

Jjiijqqj1随即判决法译码的错误概率为： PE2Y,Xxkpyxpx1pyxpx

jiijkkj1J所以PE1PE2，得证。 5.3平均差错率与信道编码

5.3.1（原5.2）设信源有M个消息符号，将每个符号编码成N长的二进制码字，码字从2N个N长二进制序列中独立、等概地选出，若采用极大似然译码规则，试分别求取在以下三种信道下的平均差错率。

p1pp1p 答案：王虹老师 5.3.2（傅详，p192）

0011pp1p 01pp p [6-8]设一离散无记忆信道，其信道矩阵为

120P0

012（1） 计算信道容量C。

121200001212000012120000 12121（2） 找出一个码长为2的重复码，其信息传输率为log5（即5个码字）。

2如果按最大似然译码准则设计译码器，求译码器输出端的平均错误概率PE（输入码字为等概率分布）。

i（3） 有无可能存在一个码长为2的码而使pe0(i1,2,3,4,5) 即使

PE0，如存在的话请找出来。

解： （1）

因为输入码字等概率分布，这重复码n2，M5，因此满足信息传输率 R 此信道是无记忆信道，满足

PjWiPbj1ai1Pbj2ai2

jbj1bj2，Wiai1ai2，bj1，bj2B，ai1，ai2A j=1，2，„，25， i=1，2，„，5 解：（1）根据信道矩阵P，可知其是一对称信道，所以信道容量为

logM1log5 n2

11Clog5H,,0,0,0

22 log5log2 1.322 比特／符号

（3） 设信道的输入符号集A0,1,2,3,4，输出符号集B0,1,2,3,4，其

传递信道矩阵为P，任选码长为2的重复码： C：W100,W211,W322,W433,W544

因为输入码字等概率分布，这重复码n2，M5，因此满足信息传输率 R此信道是无记忆信道，满足

PjWiPbj1ai1Pbj2ai2

jbj1bj2， Wiai1ai2， bj1，bj2B， ai1，ai2A j=1，2，„，25， i=1，2，„，5 下面给出传递概率PjWi的矩阵为：

W100W211W322W433W444000102141400000000001400030410111213142021222324303132333440414243440014140000000000000000000001414000141400000000000000000000014140001414000000000000000000000141400014140140000000000000001400014logM1log5 n2根据最大似然译码准则，确定的译码规则是

002211j01译成 00，j12译成 11，j23译成 22

103221

33403444译成 33，j译成 44 j0443在选择码C重复码的情况下，因为对于其他j，PjWi0，所以其他j在输出端不会出现。可计算得

1i1Pe PEMM151 

544Pr2jWi

FjWi

i（3）存在码长为2的码，它使Pe0i1,2,3,4,5，也就是它使PE0。

这种码共有10种。

这是因为这个离散无记忆信道具有特殊的传输概率，输入符号“0”只传输到输出符号“0”和“1”；输入符号“1”只传输到输出符号“1”和“2”；„；输入符号“4”只传输到输出符号“4”和“0”。因此，从（2）题的传递概率矩阵中可以看出，它可使有些

PjWiPbj1ai1Pbj2ai20。

也就是选择码长n2的序列作为码字时，它只传输到输出端若干个序列，而

,10,11；使其他传输概率为零。如（2）题中码字W100只传输到j00,01，12，21，22；等等。为此，我们只要适当地选择码长为W211只传输到j112的5个码字，它们将输出端可能出现的25个码长为2的接受序列j分割成五个互不相交的子集，每个码字只传输到所对应的子集，这样就可使

iP,,5等于零。 ei1 能使PE0，M5，码长为2的十种可选的码是：

C1W100W212W324C2C3C40310C50411233042C10 042041123301021314202122333441C9034011W43132C6W100W342W534C7W5434440C80102434430W221222324W41314103132从上面码字选择的规律可以看出，当选定某一二位长序列为码字，其他码字是将第一位码元的符号增加1，第二位的码元的符号增加2而获得；或者其他码字是将第一位码元的符号增加2，而第二位码元的读好增加1而获得。 我们也可以类似卡诺图来排列，将25个n2的序列排列成一方块图。由于00只传输到00，01，10，11；01只传输到01，02，11，12；等等。所以图中每一序列只可能向右一格，向下一格的含四个序列的方框内传输（如箭图所示）；隔行、隔列或反向的传输都为零。只要找出不相交的五个子集（即五个含四个序列的方框），选取方框左上角的序列作为码字，就可以找出这个码组。如果所选方框相交，这就不是所需的码。上述十种码中任一种码都满足如此划分的条件。

00 01 10 11 20 30 40 00

02 03 04 00 12 13 22 23 33 43

14 10 24 20 31 32 41 42 01 02

34 30 44

40 00

03 04

，W212，W324，W431，W543。我上面种所选的码是：W100们也可以用上图来检验所选的码是否正确。 5.4 汉明距离

5.4.1（原5.4）码为C{11100,01001,10010,00111}。

（1）求该码的最小汉明距离；

（2）假设码字等概率分布，该码的码率；

（3）若采用最小距离译码规则，那么，当接收到“10000”、“01100”以及“00100”时，别译为什么码字。

（4）该码能检出几位错误？能纠正几位错误？ 解：（1）此二元码的最小距离 dmin3

（2）此二元码的码字个数M4，码长n5 所以，码率 Rlog42 比特/码符号 55（4） 采用最小距离译码准则（即将接收序列译成与其码距为最小的码字）,

接收序列10000与码字10010距离为1，与其码字的距离都大于1，所以

10000 译成 10010 同理 01100 译成 11100

00100 译成 11100 或 00111任一个

（4）因此此码dmin3211，即e1，所以，此码能纠正所有发生一位码元的随机错误。 5.4.2（傅详，186）

【6-2】计算码长n5的二元重复码的译码错误概率。假设无记忆二元对称信道中正确传递概率p，错误传递概率p1p。此码能检测出多少错误？又能纠正多少错误。若p0.01，译码错误概率是多大？

解：码长n5二元重复码的码字是（00001，11111）。这码的最小距离

dmin5。

因为 dmin541

所以此码用于检测错误能检测出所有发生小于等于4位码元的随机错误。 又因为 dmin5221

所以此码用于纠正错误能纠正出所有发生小于等于2位码元的随机错误。 可以根据最大似然译码准则的译码规律或择多译码的译码规则来计算这n5的二元重复码的错误概率，这两种计算结果是一致的。所以，采用择多

译码的译码规则来计算，得

4455 PECpPC5PPC5P

3532 10PP5P4PP5 若p0.01，则

65 PE9.8101.010

325.5有噪信道编码定理 5.5.1（傅精，171页）

【5.1】某信源按P034，P114的概率产生统计独立的二元序列。 （1）试求N0，使当NN0时有

IaiPHS0.050.01 N其中HS是信源的熵。

（2）试求当NN0时典型序列集GN中含有的信源序列个数。

解：（1）本题信源是一个二元信源

1S0  得Hs0.811 比特／符号 Ps3414根据契比雪夫不等式，对于任意0，当NN0时有

IaiDIsiHS P 2NNDIsi0.01 现0.05 0.01，得2N根据信源，其

2S DIspslogpsH iii2i1233112loglog0.811

4444 0.471 所以 N022DIsi0.47118840 220.010.010.05 （2）序列集GN是所有N长的典型序列的集合，根据GN的特性有

12NHSGN2NHS

GN是序列GN中含有的典型序列的个数。

所以当NN0时GN中含有的信源序列个数为

12NHS0GN02N0HS

50.992143425GN0216226。

N0HS5G2215284。或者 N0

5.7线性分组码

5.7.1 （原5.5） 设6,3二元线性码的生成矩阵为

101011G011110

000111

（1）将生成矩阵化为GIKKAKr的形式； （2）求校验矩阵； 答案：王虹老师

5.7.2 （原5.6）试证N,K线性码的最小汉明距离不大于NK1。 答案：王虹老师

5.7.3 （傅详，P198）

【6-12】下面是某n,k线性二元码的全部码字：

C1000000C2000111C3011001C4011110

C5101011C6101100C7110010C8110101（1） 求n，k为何值； （2） 构造这码的生成矩阵G； （3） 构造这码的一致校验矩阵H。

k33码线性分组码 解：（1）因为码字数M822，所以k3，n6为6，（2）生成矩阵G为k3，n6列的矩阵，由k3个线性独立的码字组成。

000111011001G 故  101011(3)设信息位mm1m2m3，则码字

CmG

000111011001mmm123  101011

c1m3cm22c1c2c30c3m2m3c1c2c1c4c50所以c4m1cccc0

2461c5m1m3c4c1c6m1m2m3c4c2c1111000100110H所以  110101 本章测验题

一、填空题

1. 信息传递系统的基本功能是在系统输出端准确地再现系统输入端发送的信息。但是会受到客观限制，首先_____受_____的限制；其次，由于_____的干扰，_____不可避免。

2. 衡量信息传输速度大小的指标是信道的信息（传输）率R，其最大值就是_____，衡量信息传输可靠性的指标是_____。

3. 为了降低平均差错率，可先对消息_____再送入信道传送，这种为降低_____而进行的编码称为信道编码。

4. 信道输出Y它与信道输入X既有联系又有区别，联系的程度和区别的大小取决于_____或者说取决于_____。

5. 信道译码函数F是从_____到_____的映射：其含义是将_____译为_____。译码函数又称_____。 二、判断题

1. 译码规则取决于信道，一个信道的译码规则是唯一的。（）

2. 在信道输出端接收到符号bj时，按译码规则FbjajA将bj译为

aj，若此时信道输入刚好是aj，则称为译码正确。（）

3. 若按译码规则FbjajA将bj译为aj，则平均译码错误概率是

PXajYbjPFbjbj的加权平均值。（）

4. 最“好”的译码规则必然使Pe最小。（） 5. 最大后验概率译码规则是最佳译码规则。（） 三、选择题

1. 译码规则不能由_____确定

A．后验概率 B. 联合概率 C. 转移概率 D. 边缘概率

2. 假设Pa10.4，信道线图如下图所示，相应的最佳译码规则为_____

a10.30.20.7b1a20.8b3

F1b1a1F2b1a2A. F1: B. F1:

FbaFba112222F3b1a1F4b1a2C. F1: D. F1:

FbaFba2142323. 下列说法不正确的是_____

A. 信道输入等概时，极大似然译码规则也是最佳的 B. 最大后验概率条件可无条件等价成最大联合概率条件

C. 当信源统计特性未知的时候，可以使用极大似然译码规则作为译码规则

D．应用极大似然译码规则总可以确定译码的平均差错率

4. 关于“重复N次”编码，说法不正确的是_____。 A．N越大，信息传输率越高 B．“重复N次”是定长码 C．采用择多译码策略 D．能减低平均差错率

5. 对信源U的2元符号串进行编码，取码长为N3，则_____ A. 可供选择的码字有4个

2B．信息率R

3C．共有4×8＝32种不同的编码方法。 D．继续增加消息个数，可以降低平均差错率 四、计算题 1、（傅详，p191）

【6-7】考虑一个码长为4的二元码，其码字为W10000，W20011，

W31100，W41111。假设码字送入一个二元对称信道（其单符号的错误概率为p，并p0.01），而码字输入是不等概率分布的，其概率为 PW11111PWPWPW，，， 2344288试找出一种译码规则使平均错误概率PE为最小。 2、（傅详，p188）

【6-5】对于离散无记忆强对称信道，信道矩阵为

p1pr1p1pP1p

ppr1r1ppr1r1ppr1r1 p1pr1试证明对于此信道，最小距离译码准则等价于最大似然译码准则。 3、（傅详，p197）

【6-11】设无记忆二元对称信道的正确传递概率为p，错误传递概率为p对于（7，4）汉明码（如参考书[1]中表6.2）

（1） 若码字都是等概率分布，试问什么是其最佳的译码规则。 （2） 在接收端，128个接收的二元序列应该对应译成什么码字。并说

明其能纠正一个码元的随机错误。

（3） 在最佳译码规则下，计算此码的平均错误概率PE。

（4） 若p=0.01,从PE和码率R上将（7，4）汉明码与n=7的重复码进

行比较。

4、（傅详，P200）

【6-14】有一组码将二位信息位编成五位长的码字，其规则如下：

信息序列 码字 00 00000 01 01101 10 10111 11 11010 （1）证明此码是系统一致效验码； （2）找出其生成矩阵和一致效验矩阵； （3）对于无记忆二元对称信道（p（4）计算正确译码概率。

1，21），列出其最大似然译码的译码表； 2

5、（傅精，P203）

【6-16】设一分组码具有一致效验矩阵

100101 H010011 001111（1）求这分组码n?k?，共有多少个码字；

（2）此分组码的生成矩阵； （3）矢量101010是否是码字； （4）设发送码字C=（001111），但接收到的序列为R=（000010），其伴随式S是什么，这伴随式指出已发生的错误在什么地方，为什么与实际错误不同。

五、实验题

试编程实现线性分组码的编译码

本章测验题参考答案

一、填空题

1. 2. 3. 4.

传输速度 信道容量 信道噪声 传输错误 信道容量 平均差错率 编码 平均差错率

噪声N的影响情况 信道的统计特性

*5. 输出符号集合B 输入符号集合A 接收符号bjB 某个输入符号ajA 译码规则 二、判断题

1. ×；2. ×；3. ×；4. ×；5. √ 三、选择题

1、D 2、C 3、D 4、A 5、B 四、计算题 1、

解：在二元对称信道(p0.01)中最小距离译码准则等价于最大似然译码准则。但是，码字输入不是等概率分布，所以最大似然译码准则不能使平均错误概率为最小。要使译码后平均错误概率最小只有选择最小错误概率准则进行译码。也就是比较P(Wi,i)(i1,2,3,4, iYn)来决定译码规则。

我们将P(Wi,i)的矩阵如下列出：

j0000 0001 0010 0011 0100 0101 0110 0111W10000142p2W200111pp28212W31100pp814W411114p13pp213pp813pp813pp413pp213pp813pp813pp4122pp214p814p8122pp413pp213pp813pp813pp4122pp2122pp8122pp8122pp4122pp2122pp8122pp8122pp413pp213pp

813pp813pp4

1000 1001 1010 1011 1100 1101 1110 111112181814pppp3pppp333122pp2122pp8122pp8122pp4122pp2122pp8122pp8122pp413pp213pp813pp813pp4122pp214p814p8122pp413pp213pp813pp813pp413pp213pp813pp813pp414p2122pp 8122pp814p4根据最小错误概率译码准则将接收序列j译成在[P(Wi,i)]矩阵的每一列中P(Wi,i)为最大的那个码字。所以，得译码规则为（因为p0.01）

0000000100100111j=0011译成W2=001101001011j0101译成W1=0000j1101译成W4=1111

j=1100译成W3=1100011011101000111110011010若按最大似然译码准则来选择译码规则的话，如j0101,0110,…；也可译成W2或W3或W4；j1101,1110也可译成W3；等等。但其并没有将[P(Wi,i)]矩阵中每一列的最大元素除去，所以余下

元素之和就不是最小的了，PE不能为最小。 2、

证明：设码C为M个码长为n的r元码，其码字i(ai1ai2…ain) ain{0,1,…,r1}，接收的序列为

i(bi1bi2…bin) bin{0,1,…,r1}。

码字i与接收序列i的距离DijD(i,j)仍是二序列之间对应码位上不同码元的个数。因为是强对称信道，只要aik与bjk(k1,2,…,n)不相同就引起错误，而其传递概率都相等，即

P(bjk|aik)p aikbjk,k1,2,…,n r1而且强对称信道是无记忆的，所以 P(j|i)P(bj1|ai1)P(bj2|ai2)…P(bjn|ain)

iC, jYn, aik和bjk{0,1,2,…,r1}

k1,2,…,n

(1p) (一般p(nDij(pDij) r11DijDij(nDij))pp (p1p) r111p;r2,1。所以当接收序列i与码字i的距离越大，即Dij越大，nDij越小时，2r1(nDij)1DijD也越小，则P(j|i)越小。当i与i的距离越小，即Dij越小，nDij越大，)和pij越小，pr1则P(j|i)越大。

所以满足 D(*,j)≤（ Di,j） i*, i,*C, jYn 则满足 P(j|*)≥（ Pj|i） i*, i,*C, jYn 所以最小距离译码准则是选择译码函数

F(j)* *C, jYn 使满足 D(*,j)≤（Di,j） i*, iC 则等价于最大似然译码准则是选择译码函数

F(j)* *C, jYn 使满足 P(j|*)≥（Pj|i） i*, iC

[证毕] 3、

1

，所以最小距离译码准则等价于最大似然译码准则。而且2

码字是等概率分布，所以最大似然译码准则能使译码的平均错误概率PE最小。因此，此时最佳译码规则

解：（1）在无记忆二元对称信道中p

应采用最小距离译码准则。

（2）根据最小距离译码准则，因为（7，4）汉明码共有16个码字，而接收端共有128个7位长的二元序列，正好分成16个集合。每个集合都有8个二元接收序列，都是由码字 发生一位码元错位所变

成的接收序列（共7个二元序列）和完全正确传递的一个接收序列组成。而且任一码字发生一位码元错位所变成的接收序列都不会进入其它的集合。又在这16个集合中也没有相同的接收序列，即这16个集合是不相交的。因此，采用最小距离译码就能纠正一位码元的随即错误。具体的译码见译码表。

（3） PEpkpkk2777k

（4）若p=0.01，则 PE2.03103 码率 R40.5714 比特/码元 7而（7，1）重复码 P'E3.42107 码率 R'10.1429 比特/码元 7 可见，（7，1）重复码虽然能纠正≤3个码元发生的随机错误，其平均错误概率减少。但同时码率（信息传输率）也减小很多。

译码表

接收序列 码字 接收序列 码字 接收序列 码字 接收序列 码字

01001001000010110011100000100100111100000111001000000100010000110001111100010 译成0000000，译成0100101，译成1000011，译成1100110，000100001011011001011110111000100000110101101001111101100100000000010111000111000110100000011001010000011010011000000000000001010010110000111100110

00011010101000100111011010110001011010111010010001101101 译成0001111，译成0101010，译成1001100，译成1101001，000011101000101000100110000100111110111010101110011110010101111000101011011001001001100111111010100001100010100100011100001111010101001010111001100100110111010001101001

0010110001011100101000010010011001001100010110011101010010101111010101111000011100011110010011011110100011110100 译成0010110，译成0110011，译成1010101，译成1110000，0011110011101110111011111000000011001000111000101110000001101100010011111010110100001010110111001100101010110000

1111111001100001111011011011111111000110110111110101100011111010011101011100010111101111011译成0011001，译成0111100，译成1011010，译成1111111 00100010110100101001011101110001001010110010010101101111011100100111001111010101111110110011111100001101001111110011001011110010110104、

解：（1）设码字C=（c4c3c2c1c0），信息位为c4c3。根据码字可得

c2c4c3 c1c4

ccc430可见，码字的后三位都由其前二位线性组合得到。因此，此码是（5，2）一致效验码。

（2）由码字可得 G10111[I201101P]

H[PT11100I3]10010

11001故，此码是系统一致效验码。

（3）列出下列最大似然译码表

伴随式 错误图样 000 00000 111 10000 101 01000 100 00100 010 00010 001 00001

011 10100（或00011） 110 10001（或00110）

因为码的最小距离dmin3，所以能纠正一位码元的错误。从译码表中可以看出所有一位码元发生错误的错误图样能被纠错，而且还有二种发生二位码元错误的错误图样能被纠错。

（4）根据译码表及无记忆二元信道，所以正确译码概率

PE(1p)55p(1p)42p2(1p)3 5、

解：（1）设码字C=（c5c4c3c2c1c0），有 HCT0T

c5c2c00 故得 c4c1c00

cccc03210所以n=6，r=3，k=3，为（6，3）分组码。码字共有2k8个。

（2）由（1）式得

c5c0c2  c4c0 + c1

cccc0123所以c0，c1，c2为信息位。设c0m0，c1m1，c2m2，信息位m(m2m1m0)，故生成矩阵

101100 G011010

111001（3）这（6，3）分组码的所有许用码字是

000000 101100 011010 111001 001111 110110 100011 010101 可见矢量101010不是码字

（4）因为 STHRT

00100101001 010011 ST0001111110伴随式ST正好是H矩阵中第5列。根据伴随式ST就判断码字中c1发生了错误，则E’=（000010）。但实际错误图样E为

C + E = R E = R + C

E = （000010）+（001111）=（001101）

是码字传送中发生了三位码元错误。因为此（6，3）码dmin3，所以dmin2e1，得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,2^K); % 信息组初始化 for i=0:2^K-1

seq=dec2bin(i,K); for j=1:K

m(i+1,j)=str2num(seq(j)); end end

c=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,i)=bas(:,i); for index=1:r

e_common(k+index,i)=mod(H(index,1:k)*e_common(1:k,i),2); % 确定通解 end end

e_special=zeros(N,1); e_special(1:k)=0; for index=1:r

e_special(k+index)=mod(H(index,1:k)*e_special(1:k)+s(index),2); % 确定特解 end

% 以下构成系数的所有组合 e=zeros(N,2^k); coef=zeros(2^k,k); for i=0:2^k-1

seq=dec2bin(i,k); for j=1:k

coef(i+1,j)=str2num(seq(j)); % 确定系数 end end

for index=1:2^k for i=1:k

e(:,index)=e(:,index)+coef(index,i)*e_common(:,i); end end

e=mod(e,2); for i=1:2^k

e(:,i)=e(:,i)+e_special; % 确定全解 end

e=mod(e,2); % 模2和

weight=sum(e); % 求e的汉明重量

minimum=min(weight); % 找出汉明重量最小的差错图样

location=find(weight==minimum); %确定具有最小汉明重量的e的位置 location=location(1); % 可能有多个，择其一 err=e(:,location);

codeword=mod(y+err',2); 程序说明：

本程序并非使用陪集方法来译码，而是利用求解线性方程组的思路确定差错图样，进而译码。按照线性代数理论，方程HeT=s的未知数个数多于方程个数，e的理论值有无穷多个，但考虑到取值的有限性（仅0和1），e的个数也为有限个，可以确定所有e值，然后将汉明权重最小者作为差错图样。举例如下。

例 (5,3)线性码C，一致性校验矩阵H如下，如果接收到序列y＝[10101]，试确定发送的序列c

10010H

11101第一步，计算伴随式

10100101TsHy11

1110101第二步，计算对应于s的陪集，即解如下方程：

HeTs即e1e2100101 11101e31e4e5解应该由通解和特解两部分构成，具有如下表达式

01011110Tea1b0c00

01000010abc 陪集 000 10000 001 11001 010 01011 011 00011 100 11100 101 10101 110 00111 111 01111 选择e＝10000作为差错模式

第三步，得出码字的估计值

c=ye101011000000101

程序运行结果：

>> H=[1 0 0 1 0;1 1 1 0 1]; >> y=[1 0 1 0 1]; >> lincoder(H,y)

ans =

0 0 1 0 1