《信息论与编码理论基础(第五章)68550.ppt》由会员分享，可在线阅读，更多相关《信息论与编码理论基础(第五章)68550.ppt（60页珍藏版）》请在三一文库上搜索。
1、2021/2/4,1,2021/2/4,2,2021/2/4,3,信道编码,在传输过程中噪声和干扰在所难免，为了降低差错率，提高传送的可靠性，在信道编码器中可以引入冗余度，在信道解码端就可以利用此冗余度来尽可能地重建输入序列。 可靠性：增加冗余,2021/2/4,4,实际信道由于信道噪声的干扰，传输错误不可避免。为了降低平均差错率，可先对消息进行编码信道编码，再送入信道传送。 信道编码的基本思路是根据一定的规律在待发送的信息码中加入一些多余的码元，以保证受损或出错的信息仍能在接收端恢复 。信道编码的任务就是构造出以最小冗余度代价换取最大抗干扰性能的“好码”。,2021/2/4,5,一般来说，引
2、入监督码元越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。 人们研究的目标是寻找一种编码方法使所加的监督码元最少，而检错、纠错能力又高且又便于实现。,通信过程,信源,信道编码器,Um,信道,Ym,信道译码器,信宿,干扰,Xm,Xm,纠错编码器 调制器,纠错译码器 解调器,信源消息序列经过信源编码后变成了信息随机变量序列Xm ；其中每个随机变量Xm的事件全体都是D元字母表中的元素。,2021/2/4,7,将信息随机变量序列Xm分成长度为k0的段（每段称为一个信息段）; 然后依次输入到有L位移位寄存器的编码器中， 编码器根据当前的输入和编码器的状态计算出n0个编码数字（称为码段）送入信道
3、，其中L称为编码约束长度。,编码速率：信息段与码段段长之比。 纠错编码： k0长信息段空间到n0长二元码段空间的映射。 映射的任何一种指定方案就是一种编码方案。,2021/2/4,8,(n0, k0)卷积码 (Convolutional codes)：各分组相关，约束长度L为(m+1) k0 n0长码段 (N, L)分组码 (Block codes)：分组之间独立，约束长度L为k0,N=n0长码段,2021/2/4,9,(N, L)分组码的纠错译码,译码器根据收到的N 长码段y=(Y1Y2YN)和编码规则，对发送的M=2L个可能的信息段xm=(X1X2XL)中的哪一个作出判决，这样的一个通信过
4、程yxm=(X1X2XL)称为纠错译码。 译码是编码的反变换，也是一种映射，若与码段y=(Y1Y2YN)对应的信息段是xm，经过通信过程判为xm，则： 若xm=xm，则正确译码; 若xmxm，发生译码错误。 译码错误概率（误组率）： 接收y的译码错误概率：,2021/2/4,10,接下来来分析这个错误概率与哪些因素有关。 在第四章里，我们已经知道错误概率与信道统计特性有关。但通信过程一般并不是在信道输出端就结束了，还要经过译码过程（或判决过程）才到达消息的终端（收信者）。因此译码过程和译码规则对系统的错误概率影响很大。,译码规则对错误概率的影响,2021/2/4,11,译码规则对错误概率的影响
5、,因此译码规则对系统的错误概率影响很大。,译码规则1：,译码规则2：,现在我们来定义译码规则，制定译码规则就是设计一个函数它对于每一个输出符号确定一个唯一的输入符号与其对应。,2021/2/4,12,译码规则,例：有一个离散信道，其转移概率矩阵P为 根据该转移概率矩阵可以设计一个译码规则A如上;,也可以设计一个译码规则B如下：,2021/2/4,13,由于s个输出符号中的每一个都可以翻译成r个输入符号中的任何一个，所以共有rs种译码规则可供选择。 译码规则的选择应该根据什么准则？ 一个很自然的准则当然就是要使错误概率为最小。,译码规则,制定译码规则就是设计一个函数它对于每一个输出符号确定一个唯
6、一的输入符号与其对应。,若信道有r个输入符号，s个输出符号，则共有多少种译码规则？,2021/2/4,14,最佳译码规则使Pe(y)达到最小 最佳译码规则的确定： 对接收矢量y和所有可能的发送消息m，计算P(m|y)； 若对所有的m，有 ，将y判为m。 P(m|y)被称为后验概率，这种译码准则被称为最大后验概率准则。,两种典型的译码规则,2021/2/4,15,例： （5.1） 设有一DMC，其转移概率矩阵如下。 若Q(x1)l/2，Q(x2)Q(x3)1/4，试求最佳译码判决。,两种典型的译码规则,2021/2/4,16,解答 最佳译码判决指的是最大后验概率译码。记(Q(x1), Q(x2)
7、, Q(x3)信道的输入随机变量X的概率向量，又称为先验概率向量， (W(y1), W(y2), W(y3)为信道的输出随机变量Y的分布概率向量。则 (Q(x1), Q(x2), Q(x3)=(1/2,1/4, 1/4)，,两种典型的译码规则,2021/2/4,17,两种典型的译码规则,2021/2/4,18,收到“Y=y1”时，译作 “X=x1”， 误码率（译码错误的概率）为 1/3； 收到“Y=y2”时，译作 “X=x1”，误码率（译码错误的概率）为 1/2； 收到“Y=y3”时，译作 “X=x3”，误码率（译码错误的概率）为 4/7。,两种典型的译码规则,2021/2/4,19,两种典型
8、的译码规则 计算后验概率是困难的，针对具体信道（转移概率已知），采用最大似然准则 离散序列,若所有可能消息序列的先验概率相等,最大似然准则,对特定的接收序列y，选择m使得m转移成y的概率不小于其它任意消息转移为y的概率,2021/2/4,20,例 已知信道转移矩阵如下，试确定译码规则。 解 只知转移概率，无法找出最佳译码规则，只能采用最大似然准则。 将转移概率矩阵各列最大的值标出，重写转移矩阵如下：,2021/2/4,21,按转移概率最大原则确定最大似然准则如下： 尽管一般情况下并不知道这样译码 的差错率。但可以证明，当信道输入等概时，最大似然准则也是最佳的。,两种典型的译码规则,2021/2
9、/4,22,命题 如果每个码字是等概出现的，则最大后验概率准则等价于最大似然概率准则。 证明,两种典型的译码规则,2021/2/4,23,译码错误概率,译码规则也可以看做是由信道输出空间YN到消息空间UL的映射，将YN按译码规则划分为M=2L个不相交的判决区间Y1,Y2,YM,其中 Yk=y:lnQ(k)+lnP(y|xk) lnQ(m)+lnP(y|xm), 对所有的mk,最有可能是由xk转移过来概率的所有输出序列y的集合,P(xk|y) P(xm|y),2021/2/4,24,若消息m的先验概率为Q(m)，则平均译码错误概率为,译码错误概率,当发送消息为m，而接收y落入YmC，即Ym的补集
10、中时，就会产生译码错误，给定m时的译码错误概率为,2021/2/4,25,定义 两个等长符号序列 和 之间的汉明距离，是 与 之间对应位置上不同符号的个数，记为 ， 例如 小意味着 与 的相似程度高，否则 与 的相似程度低。,汉明距离,2021/2/4,26,最小汉明距离译码准则（最小错误准则） 记y与u的Hamming距离为d(y, u)，则,最小汉明距离译码,2021/2/4,27,最小汉明距离译码,设信道 D元对称DMC信道，字母表为0, 1, , D-1。其信道转移概率矩阵为DD矩阵如下。 信道传输错误的概率定义为 P(输出不等于k|输入为k)= p，k0, 1, , D-1。 此处p
11、(1-p)。,2021/2/4,28,后验概率的计算：记q(u)=P(U1U2UN)=(u1u2uN)，称q(u)为先验概率；我们知道 pN(y|u)=P( (Y1Y2YN)=y|(U1U2UN)=u) =P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)P(YN=yN|UN=uN) 若记d是(y1y2yN)与(u1u2uN)对应位置值不相同的位数，即d为(y1y2yN)与(u1u2uN) 之间的Hamming距离，则 pN(y|u)=(p/(D-1)d(1-p)N-d，,最小汉明距离译码,2021/2/4,29,命题 对于对称DMC信道，最大似然概率准则等价于最小汉明距离译码准则。 证
12、明：若pN(y|u)达到最大，即对于任意的wu，有 pN(y|u)pN(y|w)， 令记d是y与u的Hamming距离， d是y与w的Hamming距离，则 pN(y|u)=P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)P(YN=yN|UN=uN) =(p/(D-1)d(1-p)N-d， pN(y|w)=(p/(D-1)d(1-p)N-d,最小汉明距离译码,对pN(y|u)pN(y|w)两边取对数，则有,2021/2/4,30,dln(p/(D-1)+(N-d)ln(1-p) d ln(p/(D-1)+(N-d)ln(1-p),最大后验概率译码,最大似然译码,所有消息等概,q元对称信
13、道,最小汉明距离译码,最小汉明距离译码,d(ln (p/(D-1) -ln(1-p)d (ln(p/(D-1)-ln(1-p) d(ln (p/(D-1)/(1-p)d (ln(p/(D-1)/(1-p),注意到p/(D-1)(1-p)，所以dd。 得证。,2021/2/4,31,例5.1.1(p143) BSC信道的转移概率矩阵为 取L=1。如果直接将X1输入信道，信道的输出为X1，则 当信道传输错误时无法检测到。 正确接收的概率为P(X1=X1)=1-p。 今取L=1，N=4，二元(4, 1)码如下： 00000， 11111。,最小汉明距离译码,2021/2/4,32,译码规则如下： 当
14、(Y1Y2Y3Y4)与(1111)的汉明距离不大于1时，将其译为1，放入集合A 即1111;1110;1101;1011;0111属于集合A ，译为1； 当(Y1Y2Y3Y4)与(0000)的汉明距离不大于1时，将其译为0，放入集合B 即0000;0001;0010;0100;1000属于集合B ，译为0； 若采用完备译码，即任何情况都必须做出判决，则当(Y1Y2Y3Y4)与(1111)及(0000)的汉明距离都等于2时，做如下处理， (0011)、(1100)、(1001)放入集合B ，译为0， (0101)、(1010)、(0110)放入集合A ，译为1。 译码规则显然是最小距离准则。,最
15、小汉明距离译码,2021/2/4,33,A=1111;1110;1101;1011;0111; 0101;1010;0110 B= 0000;0001;0010;0100;1000; 0011;1100;1001 信道传输错误概率为 ？ 当集合A(或B)中的元素译为0（或1）时，信道传输错误。 因此，信道传输出现错误的概率为,最小汉明距离译码,2021/2/4,34,若收到(0011)、(1100)、(1001)、(0101)、(1010)、(0110)这六个元素之一时，将其判为0和1按照最小汉明距离译码是等价的，可以单独作一个集合C,它表明接收的向量有错误但无法判决，此时 集合A=(1111
16、;1110;1101;1011;0111)1； 集合B=(0000;0001;0010;0100;1000)0； 信道传输出现错误的概率为： 发现错误无法判决的概率为：,最小汉明距离译码,2021/2/4,35,Fano不等式和信道编码逆定理,信道编码逆定理：表明当每个符号所含的信息量超过信道容量时，错误将是不可避免的。,2021/2/4,36,研究Pb，HL(U) ， I (UL;VL)之间的关系,先考虑L=1 ，这时，当收到V后关于U的平均不确定性或含糊度H(U|V)若不为0，就一定有错误存在。,信道编码,信 道,信道译码,2021/2/4,37,设空间U和V各有M个元素a1，a2，aM。
17、,平均误码率,接收矢量y判为vj时的错误概率,vj判为uj时正确译码,2021/2/4,38,定理5.2.1 (Fano不等式) U 和V 空间中的事件满足下不等式,其中,用V估计U产生的信息损失,误差的不确定性,估计错误时消除的不确定性,2021/2/4,39,证明：引入译码错误随机变量 E，E1 表示译码错误，E=0 表示译码正确。,H(UE|V) = H(E|V) + H(U|EV),H(E) + Pb H(U|E=1, V) + (1-Pb) H(U|E=0, V), H(E) + Pb log (|U|-1) + 0,另一方面：H(UE|V) = H(U|V) + H(E|UV)=
18、H(U|V),所以 H(U|V) H(E) + Pb log (|U|-1)， 也就是 H(U|V) H(Pb) + Pb log (|U|-1),2021/2/4,40,L1时,定理5.2.2 令ULVL是信息序列u=(u1,u2,uL)和译码判决序列v=(v1,v2,vL)的联合集，Pb为误比特率，表示为,其中Pek是第k位出错的概率，则有,2021/2/4,41,证明：,首先,2021/2/4,42,信道编码逆定理,设离散平稳信源的字母表有M个字母，每s秒产生一个字母，且熵为 令离散无记忆信道的容量为C，每c秒送一个信道符号，若长为L的信息序列被变成NLs/ c的码字，则误码率满足 当
19、误码率为非零值。,2021/2/4,43,L1时,由信息处理定理,2021/2/4,44,信道编码,信 道,信道译码,这个定理说明，对于信源在Ls秒产生的信息序列，当以长为NLs/c的分组码表示，经过信道传送和译码器处理时，若信源每个符号所含的熵H (U)大于信道容量s/c C，则不管采用何种编译码方法都不能使得平均错误概率为0。,2021/2/4,45,联合典型序列和信道编码定理,2021/2/4,46,3.2 离散无记忆（简单）信源的等长编码,当L足够大时，在信源序列中必有一些消息序列其自信息量的均值与信源熵之差小于，而对另外一些信源序列其差 ，因此，可以把信源序列分成两个互补的子集。,2
20、021/2/4,47,3.2 离散无记忆（简单）信源的等长编码,定义3.2.1(p57) 定义 TU(L, )=(u1u2uL)|H(U1)-ILH(U1)+， 称TU(L, )为-典型序列集。 称TU(L, )的补集为非-典型序列集。,P(U1U2UL) )=(u1u2uL)| (u1u2uL) TU(L, )1-。 系3.2.1(特定典型序列出现的概率) 2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。 系3.2.2(典型序列的数量) (1-)2L(H(U)-)|TU(L, )|2L(H(U)+)。,2021/2/4,48,定义5.3.1 x和y是联合典型序列
21、,(1) x是典型序列，即对任意小的正数e，存在N使,(2) xy是典型序列，即对任意小的正数e，存在N使,(2) y是典型序列，即对任意小的正数e ，存在N使,2021/2/4,49,联合典型序列,TX(N,e)表示XN中典型序列的集合，排在前边 TY(N,e)表示YN中的典型序列集合，排在前边 TXY(N,e) 表示XN YN 中的典型序列集 ，分布在阵列的左上角,|XN|个可能的x序列作为行号，以|YN|个可能的y序列作为列号,2021/2/4,50,联合典型序列,引理1,上图中每列最多的点数,上图中每行最多的点数,给定y和y构成联合典型序列的所有x序列的集合，称为在条件y下，x的典型序
22、列集。,2021/2/4,51,联合典型序列,2021/2/4,52,联合典型序列,引理2,证明：,2021/2/4,53,联合典型序列,左上角中联合典型序列点的密度,引理3,阵列中的左上角的总的格子数,2021/2/4,54,信道编码定理,DMC P(y|x),令编码速率为R，则各码字的标号集为1,2NR。 编码函数,译码函数,2021/2/4,55,信道编码定理,发送消息,平均误组率,发送m的误组率,定义5.3.2 对给定离散无记忆信道和任意e 0，若有一种编码速率为R 的码，在N足够大时，能使pee，就称R 是可达的。,接收序列为,译码结果为,2021/2/4,56,信道编码定理,定理5
23、.3.1 (Shannon信道编码定理)，给定容量为C的离散无记忆信道X，p(x|y)，Y，若编码速率RC，则R是可达的。,证明：从XN中独立随机地选择2NR个序列作为码字，每个码字出现的概率为,X中任一元素独立、等概地出现。这种编码方法称作随机编码。,译码规则：对给定的接收序列y，若存在唯一,使,就将y译为m,2021/2/4,57,信道编码定理,两个以上m和y联合典型,译码错误,定义,的概率，当N 足够大，趋于0,2021/2/4,58,联合典型序列,TX(N,e)表示XN中典型序列的集合，排在前边 TY(N,e)表示YN中的典型序列集合，排在前边 TXY(N,e) 表示XN YN 中的典
24、型序列集 ，分布在阵列的左上角,|XN|个可能的x序列作为行号，以|YN|个可能的y序列作为列号,2021/2/4,59,信道编码定理,使之极大化，用C 取代,当RC-3时，随机码集合的平均译码错误概率趋于零，所以必存在有一种码，当N足够大时，其译码错误概率为0,若,2021/2/4,60,有噪信道编码定理（香农第二定理） 定理（香农第二定理） 离散、无记忆、平稳信道，信道容量为C，只要待传送的信息率RC，就一定能找到一种信道编码方法，使得码长N足够大时，平均差错率Pe任意接近于零。 香农第二定理是存在性定理，它指出在RC时，肯定存在一种好的信道编码方法，使Pe逼近零。但香农并没有给出编码的具体方法。,