《信息理论与编码》课程教学课件（讲稿）第5章 有噪信道编码 5.4 汉明距离 5.5 有噪信道编码定理与逆定理

汉明距离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                极大似然译码规则： 与汉明距离 有何联系？