汉明距离5.411上节讨论译码时曾经提过，可将接收序列译为与之最“相似”的输入序列（码字）。如何定量描述符号序列之间的“相似”程度呢？汉明（R.W.Hamming）受距离概念的启发,在符智号序列之间引入汉明距离，用来定量描述符号序一一“相似”程度。列之间的福
1 5.4 汉明距离 上节讨论译码时曾经提过，可将接收序列译为与 之最“相似”的输入序列（码字）。 如何定量描述符号序列之间的“相似”程度呢？ 汉明（R.W.Hamming）受距离概念的启发,在符 号序列之间引入汉明距离，用来定量描述符号序 列之间的“相似”程度
吉祥1、汉明距离的定义与性质定义：两个等长符号序列x和之间的汉明距离，记为 D(x,)，是与之间对应位置上不同符号的个数α=1320120x =101111例:D(x,)=3D(α,β) = 2β=1220320= 111100程度：用汉明距离来度量两个符号序列的“相似”D(,J)小： 与 的相似程度高。D(x,J) 大:Ix 与 的相似程度低相似程度的高低是相对而言的。汉明距离的性质（距离公理）：1（1）非负性：D(x,J)≥0，当且仅当时等号成立；x=(2)对称性： D(x,)=D(J,x)(3) 三角不等式： D(x,z)+D(z,)≥D(x,J)2
2 1、汉明距离的定义与性质 定义：两个等长符号序列 和 之间的汉明距离，记 为 ，是 与 之间对应位置上不同符号的个数。 x y D x y ( , ) x y 101111 1320120 ( , ) 3 , ( , ) 2 111100 1220320 x D x y D y 例： 用汉明距离来度量两个符号序列的“相似”程度： 小： 与 的相似程度高。 大： 与 的相似程度低。 相似程度的高低是相对而言的 。 D x y ( , ) x y D x y ( , ) x y 汉明距离的性质（距离公理）： （1）非负性： ，当且仅当 时等号成立； （2）对称性： （3）三角不等式：D x y ( , ) 0 x y D x y D y x ( , ) ( , ) D x z D z y D x y ( , ) ( , ) ( , )
u2、二元序列的汉明距离11NX=xX2"".xN, Xe(0,1)Zx4D(x,y)④yk)=J= yiy2"yn, yke(0,1]k=111二元序列汉明重量W(x)：二元序列x中含“1"的个数。111W(x) = D(x,O~)111-一11N长的0序列111111111EE清.稻11111111-111131111
3 2、二元序列的汉明距离 1 2 1 2 , {0,1} , {0,1} N k N k x x x x x y y y y y 1 ( , ) N k k k D x y x y 二元序列汉明重量 W x( ) ：二元序列 x 中含“1”的个数。 ( ) ( , ) W x D x O N N长的0序列
花3、码的相似性等长码: C={ci,C2,,c,码间距离：D(c,,c,），c,±EC,C,码C的最小码间距离：dmn=min[D(c,c)Ci,C,ECC,±C;最小码间距离dmi是衡量码的性能的重要参数码距小：说明有些码字受干扰后容易变为另一码字，译码时就会出错。！进行信道编码时，只要条件允许，尽量选择最小码间距离大一些的码。福智景
4 3、码的相似性 最小码间距离dmin是衡量码的性能的重要参数， 码距小：说明有些码字受干扰后容易变为另一码字， 译码时就会出错。 进行信道编码时，只要条件允许，尽量选择最小码 间距离大一些的码。 1 2 { , , , } C c c c q ( , ) , , , D c c c c c c C i j i j i j 等长码： 码间距离： 码C 的最小码间距离 ： min min ( , ) , i j i j i j d D c c c c c c C
4、最小（汉明）距离译码规则IPb =0a=0XYP福1DMCp(by,b,](aj,a2)=1a =1p1EYNXNXNs信道译码P信道编码ynix"(B,β2,..",βan)Ffa,a,...,a,n{C,C2,**",CMl[Si,S2,"..S(c,,C,..l,cm)花特1111111111N次扩展信道(s,s2,.., Su)β.BBCi,C,.,CM,C....1极大似然译码规则：与汉明距离111F(B)=c,eC, β,eBN有何联系？F(P(B,Ic)≥ P(β,Ic,), c; ECcAN111115
5 4、最小（汉明）距离译码规则 1 2 1 2 { , , , } { , , , } f M M s s s c c c 1 2 1 2 2 { , , , } { , , , } N F M c c c N 次扩展信道 信道译码 F ˆ N X N X N Y 信道编码 f 1 2 2 1 2 { , , , } N 2 1 2 { , , , } { , , , } N c c cM S 1 2 { , , , } s s s M 1 2 { , , , } c c c M | n n Y X P p p p p 1 a 0 2 a 1 1 b 0 2 b 1 X Y DMC 1 2 { , } a a 1 2 { , } b b * * ( ) , : ( | ) ( | ) , N j j j N j j j i i F c C B F P c P c c C A 极大似然译码规则： 与汉明距离 有何联系？
VNYNPNS信道译码P信道编码y"jxnF(B, β2..., β,n)fa.a...(c,C..,cM)(S,S2..,SM8(C,C2,""",CM)1?1记:c, =a,a,a二11111111B, =b,b, ...b.JiJ21P(β, Ic,)= P(b,bi, i)=P(b, la,)P(b, la,)... P(binlai)Taa....a设码距D(C;,β,)111D(ci,β,)(1-p)NpD(ci,β,)D(c;,β,)[N-D(ci,β,)(1- p)Np(β, /c,)-pp=p(1- p)D(csP)1--p1假设 p>pD(c,β)→ =P(β, Ic)个111-福p/(1-p)<1F(β,)=c,EC, β,EBN最小（汉明）距FC,ECCAND(c,β,)=min[D(c,β,)]离译码规则：6
6 信道译码 F ˆ N X N X N 信道编码 Y f 1 2 2 1 2 { , , , } N 2 1 2 { , , , } { , , , } N M c c c S 1 2 { , , , } M s s s 1 2 { , , , } M c c c | n n Y X P 1 2 1 2 N N i i i i j j j j c a a a b b b 记： 1 2 1 2 1 1 2 2 ( | ) ( | ) ( | ) ( | ) ( | ) N N N N P c P b b b a a a P b a P b a P b a j i j j j i i i j i j i j i p p p p (1 ) 1 假设 ( , ) ( | ) D c P c i j j i * * ( , ) mi ( ) n ( , ) , : , j N j j j j i j N i F c C D c D c c A B F C 最小（汉明）距 离译码规则： ( )= ( , ) ( , ) [ ( , )] ( , ) ( , ) (1 ) | (1 ) (1 ) 1 i j i j i j i j i j D c N D c N D c D c N j i D c p p c p p p p p p p 设码距D(ci ,βj )
几点说明最小距离译码规则可在一般信道中采用，但不一定与极大似然译码规则等价；-对于二元对称信道，若正确概率大于错误概率则最小距离译码规则与极大似然译码规则等价，并且当输入等概时是最佳的。一一福稻福
7 几点说明 最小距离译码规则可在一般信道中采用，但不一 定与极大似然译码规则等价； 对于二元对称信道，若正确概率大于错误概率， 则最小距离译码规则与极大似然译码规则等价， 并且当输入等概时是最佳的
汉明距离与平均差错率1前提：二元对称信道输入等概。F(β,)=c,eC, β,eB"译码函数：1平均差错率：1D(cCi,β,)-[N-D(B:)ZpEP[β,1c,DPMMii111信源符11T号数量1111智8/11
8 汉明距离与平均差错率 前提：二元对称信道输入等概。 * ( ) , n F c C B j j j * * 1 1 * ( , ) [ ( , )] 1 | 1 D c N D c j j j j e j j j j P P c p p M M 译码函数： 平均差错率： 信源符 号数量
5. 57有噪信道编码定理与逆定理在有噪信道上传递信息，难免会出现差错为了降低平均差错率，可将每个消息重复传送若于次，但这样又降低了信息传递的速度。目标：找到一种信道编码方法能同时保证差错率和信息传输速度的要求。1948年，香农从理论上得出结论：对于有噪信道，只要通过足够复杂的编码方法，就能使信息率达到信道的极限通过能力一一信道容量，同时使平均差错率逼近零。这一结论称为香农第二编码定理或有噪信道编码定理，是有关信息传输的最基本结论
9 5.5 有噪信道编码定理与逆定理 在有噪信道上传递信息，难免会出现差错； 为了降低平均差错率，可将每个消息重复传送若干 次，但这样又降低了信息传递的速度。 目标：找到一种信道编码方法能同时保证差错率和 信息传输速度的要求。 1948年，香农从理论上得出结论：对于有噪信道， 只要通过足够复杂的编码方法，就能使信息率达到 信道的极限通过能力——信道容量，同时使平均差 错率逼近零。这一结论称为香农第二编码定理或有 噪信道编码定理，是有关信息传输的最基本结论
吉编码定理定理（香农第二编码定理）：若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R<C，就一定能找到一种信道编码方法，只要码长足够大时，平均差错率任意接近于零。注：（1）香农第二编码定理实际上是一个存在性定理，它指出：在R<C时，肯定存在一种好的信道编码方法，能够编出一种好码，用这种好码来传送消息可使平均差错率逼近零。I（2）香农并没有给出能够找到好码的具体方法。(3）香农第二编码定理的证明很复杂，略。10
10 编码定理 定理（香农第二编码定理）： 若信道是离散、无 记忆、平稳的，且信道容量为C，只要待传送的信息率 R<C ，就一定能找到一种信道编码方法,只要码长足够 大时，平均差错率任意接近于零。 注： （1）香农第二编码定理实际上是一个存在性定理，它 指出：在R<C时，肯定存在一种好的信道编码方法， 能够编出一种好码，用这种好码来传送消息可使平均 差错率逼近零。 （2）香农并没有给出能够找到好码的具体方法。 （3）香农第二编码定理的证明很复杂，略