信息论与编码第二讲

信息论与编码第二讲第一页，共八十四页，编辑于2023年，星期六主要内容1234信道编码定理线性分组码的编译码码的检、纠错能力信道编码概念第二页，共八十四页，编辑于2023年，星期六一、信道编码概念第三页，共八十四页，编辑于2023年，星期六1.1通信系统模型第四页，共八十四页，编辑于2023年，星期六信源编码器

把消息转换成为二进制形式的信息序列，并且为了使传输有效，去掉了与传输信息无关的多余度。纠错编码器

为了抗击传输过程中各种干扰，要人为地增加一些多余度，使其具有自动检错或纠错能力。纠错码译码器由于信道干扰，该信息序列中可能有错误，经过纠错码译码器，对错误进行纠正。第五页，共八十四页，编辑于2023年，星期六信源指原来的信源和信源编码器，其输出是二(多)进制信息序列。

信道包括发射机、实际信道（或称传输媒质）和接收机在内的广义信道，它的输入是二（多）进制数字序列，输出是二（多）进制数字序列。

1.2编码信道第六页，共八十四页，编辑于2023年，星期六第七页，共八十四页，编辑于2023年，星期六二、信道编码定理第八页，共八十四页，编辑于2023年，星期六2.1信道编码理论

每个信道具有确定的信道容量C，对任何小于C的码率Rs，存在有速率为Rs、码长为n的编码方法，若用最大似然译码，则随着码长的n增加其译码错误概率Pe可任意小，即：第九页，共八十四页，编辑于2023年，星期六式中，E(RS)为正实函数，称为误差指数，它与RS、C的关系如下图所示。图中，C1、C2为信道容量，且C1＞C2。第十页，共八十四页，编辑于2023年，星期六2.2信道编码基本思想

第十一页，共八十四页，编辑于2023年，星期六第十二页，共八十四页，编辑于2023年，星期六第十三页，共八十四页，编辑于2023年，星期六第十四页，共八十四页，编辑于2023年，星期六第十五页，共八十四页，编辑于2023年，星期六2.3译码平均错误概率

第十六页，共八十四页，编辑于2023年，星期六第十七页，共八十四页，编辑于2023年，星期六第十八页，共八十四页，编辑于2023年，星期六2.4译码规则

第十九页，共八十四页，编辑于2023年，星期六2.4.1最大后验概率译码准则第二十页，共八十四页，编辑于2023年，星期六例题第二十一页，共八十四页，编辑于2023年，星期六第二十二页，共八十四页，编辑于2023年，星期六2.4.2极大似然译码准则第二十三页，共八十四页，编辑于2023年，星期六例题第二十四页，共八十四页，编辑于2023年，星期六第二十五页，共八十四页，编辑于2023年，星期六两种译码准则比较第二十六页，共八十四页，编辑于2023年，星期六2.4.3最小码距译码准则第二十七页，共八十四页，编辑于2023年，星期六第二十八页，共八十四页，编辑于2023年，星期六最小码距第二十九页，共八十四页，编辑于2023年，星期六最小码距对错误概率的影响第三十页，共八十四页，编辑于2023年，星期六最小距离译码准则第三十一页，共八十四页，编辑于2023年，星期六最小距离准则与最大似然准则关系第三十二页，共八十四页，编辑于2023年，星期六例：重复码早期的检错码为重复码。该码用000代表信息“0”，用111代表信息“1”。显然所增加的2个码元并不增多信息，是多余的,使传信率降低。此外，除去传送信息的000和111这2种组合外,还有001,010,011,100,101,110等6种组合没采用。当信道上信噪比足够大时,可认为000和111中产生的错误一般不会多于一个码元。如接收到001,010,100,在接收端怎么译码呢？根据最小码距译码准则，可判定实际上是000,即信息为0；同理,如接收到011,110,101,在接收端也可判定111,即信息为1。可见,多余码元可检出并纠正一个错误，这样就提高了传信的可靠性。

第三十三页，共八十四页，编辑于2023年，星期六三、线性分组码第三十四页，共八十四页，编辑于2023年，星期六第三十五页，共八十四页，编辑于2023年，星期六m2m1m0C5C4C3C0C1C23.1生成矩阵第三十六页，共八十四页，编辑于2023年，星期六[m2m1m0]100111010110001011=[c5c4c3c2c1c0]mG=C100111010110001011张成码空间的三个基，本身也是码字。第三十七页，共八十四页，编辑于2023年，星期六第三十八页，共八十四页，编辑于2023年，星期六信息空间到码空间的线性映射信息组(m2m1m0) 码字(c5c4c3c2c1c0) 000 000000 001 001011 010 010110 011 011101 100 100111 101 101100 110 110001 111111010

k维k重

k维n重

信息空间

码字空间第三十九页，共八十四页，编辑于2023年，星期六

gk-1G== ⋮ g1 g0c

=m

G=[mk-1,……m1

m0][gk-1

…g1g0]T

=mk-1

gk-1+…+m1

g1+m0

g0

第四十页，共八十四页，编辑于2023年，星期六生成矩阵G是由k个行矢量组成的，其中的每个行矢量gi既是一个基底，也是一个码字。任何码字都是生成矩阵G的k个行矢量的线性组合。只要这k个行矢量线性无关，就可以作为k个基底张成一个k维n重空间，它是n维n重空间的一个子空间，子空间的所有2k个矢量构成码集C。第四十一页，共八十四页，编辑于2023年，星期六不同的生成矩阵产生不同的码，生成矩阵的特点决定了码的特点。由于构成同一空间的基底不是唯一的，所以不同的基底或生成矩阵可能生成同一码集。码集相同，编码不一定相同，因为编码涉及码集和映射两个因素，码集一样而映射方法不同不能说是同样的编码。第四十二页，共八十四页，编辑于2023年，星期六由于基底不是唯一的，因此允许将基底线性组合后挑出其中k个线性无关的矢量作为新的基底，依然可以张成同一个码空间。对应到生成矩阵，等效于允许通过行运算（行交换、行的线性组合）改变生成矩阵的行而不改变码集，只要保证矩阵的秩仍是k（k行线性无关)。所以，任何生成矩阵可通过行运算转化成“系统码”形式。第四十三页，共八十四页，编辑于2023年，星期六3.2系统码把信息组原封不动搬到码字前k位的(n,k)码，其码字具有如下形式：c=(cn-1,…cn-k

,cn-k-1,…,c0)=(mk-1,…m1,m0,cn-k-1,…c0)其生成矩阵具有如下形式：G=[IkP]=

第四十四页，共八十四页，编辑于2023年，星期六3.3校验矩阵对于k×n矩阵G，存在一个(n-k)×n矩阵H，使得G的行空间和H正交。基底数k的码空间C是n维n重空间的子空间，若能找出全部n个基底的另外n-k个基底，也就找到了对偶空间D。将D空间的n-k个基底排列起来可构成一个(n-k)×n矩阵，称为是码空间C的校验矩阵H，它与所有码字正交。既然用k个基底能产生一个(n,k)线性码，那么也能用其余n-k个基底产生一个(n,n-k)线性码，称（n,n-k）线性码是(n,k)线性码的对偶码。C和D的对偶是相互的，G是C的生成矩阵又是D的校验矩阵，而H是D的生成矩阵又是C的校验矩阵。第四十五页，共八十四页，编辑于2023年，星期六

n维n重空间R k维k重k维n重 n-k维n重信息组码空间C

对偶空间D

空间m

G

H

图3-1码空间与映射第四十六页，共八十四页，编辑于2023年，星期六c是G空间的一个码字，那么由正交性得到：

c

HT=0 0代表零阵，它是[1×n]×[n×(n-k)]=1×(n-k)矢量。上式可以用来检验一个n重矢量是否为码字：若等式成立，该n重是码字，否则不是码字。由于生成矩阵的每行都是一个码字，因此有：

GHT=0 这里0代表一个[k×n]×[n×(n-k)]=k×(n-k)的零矩阵。第四十七页，共八十四页，编辑于2023年，星期六对于系统码，其校验矩阵也是规则的，必为：

H＝[PT┆In-k]

因为：

GHT=[Ik┆P][PT┆In-k]T

=[IkP]+[P

In-k]

=[P]+[P]

=0

第四十八页，共八十四页，编辑于2023年，星期六例3.1考虑一个(7，4)码，其生成矩阵是：

G= =[I4

P]

①对于信息组m=(1011),编出的码字是什么？②画一个（7，4）分组码编码器原理图。 ③若接收到一个7位码r=(1001101),检验它是否码字？

第四十九页，共八十四页，编辑于2023年，星期六3.3伴随式与译码线性分组码C=(cn-1,……c1,c0)，接收码R=(rn-1,……r1,r0)，

差错图案:E=(en－1,…，e1,e0)=R–C 对于二进制码，有E=R＋C及 R=C＋E RHT=(C＋E)HT=CHT＋EHT=0＋EHT=EHT如收码无误，必有R=C即RHT=0,如信道差错E0，必有RHT=EHT0。定义伴随式S：S=(sn-k-1,…，s1,s0)=RHT=EHT S仅与E有关，而与C无关。

第五十页，共八十四页，编辑于2023年，星期六从物理意义看，伴随式S并不反映发送的码字是什么，而只反映信道对码字造成了怎样的干扰。伴随式S是一个(n-k)重矢量，只有2n-k种可能的组合；而差错图案E是n重矢量，共有2n个可能的组合。因此，同一伴随式可能对应若干个不同的差错图案。在接收端我们并不知道发码C究竟是什么，但可以知道HT和接收码是R什么，从而算出S是什么。译码最重要的任务：从伴随式S找出C的估值。第五十一页，共八十四页，编辑于2023年，星期六

一般的译码思路RHT

=S

E

C=R＋E

E

m

编码C

R S= no计算输出Ĉ

mGRHT=0？

ER+Eyes

输出R

图3-3译码过程框图第五十二页，共八十四页，编辑于2023年，星期六S=(sn-k-1,…，s1,s0)=EHT=(en－1,…e1,e0) (3-18)展开成线性方程组形式，为：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

s1=en-1h1(n-1)+…+e1h11+e0h10

s0=en-1h0(n-1)+…+e1h01+e0h00方程组中有n个未知数en－1,…e1,e0，却只有n-k个方程。第五十三页，共八十四页，编辑于2023年，星期六在二元域中，少一个方程导致两个解，少两个方程导致四个解…少n-(n-k)=k个方程导致有2k个解。在E的2k个解中选一，最合理的方法是概率译码，它把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该算法的理论根据就是最小汉明距离译码。

第五十四页，共八十四页，编辑于2023年，星期六3.4标准阵列第五十五页，共八十四页，编辑于2023年，星期六某一个(5,2)系统线性码的生成矩阵：G=码集：{00000,10111,01101,11010}S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100第五十六页，共八十四页，编辑于2023年，星期六E2n-k+C2kE2n-k+CiE2n-k-1+C1E2n-k+C0=E2n-kEj+C2k－1Ej+CiEj+C1Ej+C0=EjE1+C2k－1E1+CiE1+C1E1+C0=E1E0+C2k－1=C2k－1E0+Ci=CiE0+C1=C1E0+C0=0+0=0表3-2标准阵列译码表第五十七页，共八十四页，编辑于2023年，星期六对于(6,3)码的8个码矢：v1=(000000),v2=(001110),v3=(010101),v4=(100011),v5=(011011),v6=(101101),v7=(110110),v8=(111000)。其标准阵列：第五十八页，共八十四页，编辑于2023年，星期六例：某一个(5,2)系统线性码的生成矩阵是G=，设收码是R=(10101),请先构造该码的标准阵列译码表，然后译出发码的估值Ĉ。分析：H=[PTI3]=，由S=(E+C)HT=EHT得：

s2=e4+e3+e2

s1=e4+e15个未知数，3个方程

s0=e4+e3+e0

必有4组解令S0=000,并分别令e4e3=00、01、10、11,解得E0的4组解是(00000)(01101)(10111)(11010)，取E0=(00000)再依次令S=001,010,011…每次有4组解，取最轻者为“解”。其中有的组最轻解是唯一的，有的却不是，比如伴随式S=(011)的4个解是(00011)、(10100)、(01110)、(11001)，其中(00011)和(10100)并列最小重量，任取其中一个？第五十九页，共八十四页，编辑于2023年，星期六S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100第六十页，共八十四页，编辑于2023年，星期六第六十一页，共八十四页，编辑于2023年，星期六查表译码方法[1]计算R的伴随式S=RHT；[2]找出伴随式S等于RHT的陪集首el；[3]码矢v=R+el就是发送码矢。第六十二页，共八十四页，编辑于2023年，星期六例3.3对于(6,3)码，校验矩阵为：S=EHT第六十三页，共八十四页，编辑于2023年，星期六如果发送的码矢为v=(111000)，接收的矢量r=(111001)，怎样来译码？第六十四页，共八十四页，编辑于2023年，星期六四、码的纠、检错能力第六十五页，共八十四页，编辑于2023年，星期六4.1计算最小距离的方法[1]直接计算。含2k个码字的码集需计算2k(2k-1)/2个距离后才能找出dmin。[2]利用群码封闭性——两码字之和仍是码字：

d(C1,C2)=w(C1C2)=w(C3) 可得定理3.1:线性分组码的最小距离等于码集中非零码字的最小重量：

dmin=min{w(Ci)}CiC及Ci0于是最小距离问题转化为寻找最轻码字问题，含2k个码字的码集仅需计算2k次。第六十六页，共八十四页，编辑于2023年，星期六[3]利用校验矩阵H的秩定理3.4：(n,k)线性分组码最小距离等于dmin的充要条件是校验矩阵H中有（dmin-1)列线性无关。换言之，dmin=校验矩阵H的秩+1。第六十七页，共八十四页，编辑于2023年，星期六定理3.2:任何最小距离dmin的线性分组码，其检测随机差错的能力为（dmin－1）。

定理3.3:

任何最小距离等于dmin的线性分组码，其纠正随机差错的能力t为：

t=INT若最小距离为dmin的码同时能检ed个、纠ec个差错,则 ed＋ec

dmin–1

ec

ed。

抑制纠错能力才能提高检错能力。第六十八页，共八十四页，编辑于2023年，星期六第六十九页，共八十四页，编辑于2023年，星期六例：每个分组码dmin=7，那么怎么来纠错和检错？（1）纠错t=3；（2）2重纠错，并且4重错误检测

t=2,D=4；（3）6重错误检测D=6。第七十页，共八十四页，编辑于2023年，星期六定理3.5：(n,k)线性分组码的最小距离必定小于等于(n-k+1)即

dmin

(n-k+1)

因为H是(n-k)n矩阵，该矩阵的秩最大不会超过(n-k)，即线性无关的列不会超过(n-k)。第七十一页，共八十四页，编辑于2023年，星期六

4.2完备码如果某码的伴随式组合数目恰好和不大于t个差错的图案数目相等，相当于在标准阵列中能将所有重量不大于t的差错图案选作陪集首而没有一个陪集首的重量大于t，这时的伴随式就能和可纠差错图案实现一一对应，校验位得到最合理的利用。满足方程：

的二元(n,k)线性分组码称为完备码。t=1的完备码叫汉明码。第七十二页，共八十四页，编辑于2023年，星期六4.3汉明码纠错能力t=1的完备码称为汉明码。汉明码指一类码，既可以是二进制的，也可以是非二进制的。二进制汉明码应满足条件：2n-k=1+n。令r=n-k，汉明码n和k服从以下关系码长：n=2r-1

信息位：k=2r-1-r

最小距离dmin=3 当r＝3、4、5、6、7、8…时，有以下汉明码：(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)…。第七十三页，共八十四页，编辑于2023年，星期六

从n维矢量空间的角度看(n,k)完备码，假定每个码字为中心放置一个半径t的球，与该码汉明距离小于等于t的所有接收矢量均包含在此球内，每球包含的矢量点数是。以码集2k个码字为中心、半径t(不相重叠)的球共可包含2k

点。由于n重矢量的总数是2n个，包含在2k个球中的点数不可能多于总点数，所以下列不等式必定成立：

第七十四页，共八十四页，编辑于2023年，星期六如果上式等号成立，表示全部2n个接收矢量等分地落在2k个半径t的球内，而没有一个矢量落在球外，这就是完备码。围绕完备码2k个码字、汉明距离为t的所有球都是不相交的、不相切的，每一个接收矢量不是落在这个球、就是落在那个球内，没有一点是在球外。这样，接收矢量离码字的距离至多为t，所有重量Wt的差错图案都能通过最小距离译码得到纠正，而所有重量Wt+1的差错图案都不能纠正。第七十五页，共八十四页，编辑于2023年，星期六例3.4:构造一个m=3的二元(7，4)汉明码。

0001111列置换

1110100

H= 0110011 0111010 1010101 1101001那么系统汉明码的生成矩阵G为：

1000101 G=[I4

P]= 0100111 0010110 0001011 第七十六页，共八十四页，编辑于2023年，星期六

4.4高莱码高莱码是二进制（23，12）线性码，其最小距离dmin＝7，纠错能力t=3。由于满足：

223-12=2048=它也是完备码。在(23,12)码上添加一位奇偶位即得二进制线性(24,12)扩展高莱码，其最小距离dmin＝8。第七十七页，共八十四页，编辑于2023年，星期六

4.5扩展码(n,k)分组码+1位奇偶校验=(n＋1,k)扩展码校验位c校的选择应满足校验方程

c

n－1

…c1c0

c

校＝0

矩阵H与H扩的关系如下：

0 H 0 k个0H扩＝ ׃

0 111…1 1 (n+1)个1从最小距离角度看，若扩展前原码的最小距离dmin是奇数,则扩展后的最小距离变成dmin+1；若原码的最小距离是偶数，则偶校验不改变其最小距离。第七十八页，共八十四页，编辑于2023年，星期六

4.6缩短码(n,k)分组码缩短i位=(n-i,k-i)缩短码如果缩短1位,可在码集中去掉所有第1位是0的码字,剩下的码组成一个新的码集，其最小码重不变；如果缩短2位,可在码集中去掉所有前2位是0的码字,剩下的码组成一个新的码集，其最小码重仍不变；……以此类推，缩短i位，在码集中去掉所有前i位是0的码字，剩下码集的dmin与缩短前一样。因此,（n-i,k-i,dmin）缩短码与原（n,k,dmin）码具有相同的纠检错能力。第七十九页，共八十四页，编辑于2023年，星期六缩短后的生成矩阵Gs(删除前i行、前i列）

g(k-1)(n-1)g(k-1)(n-2)……g(k-1)(n-i)g(k-1)(n-i-1)…………g(k-1)0 g(k-2)(n-1)g(k-2)(n-2)……g(k-2)(n-i)g(k-2)(n-i-1)…………g(k-2)0Gs=⋮