信息论与编码理论基础(第五章)68550.ppt
《信息论与编码理论基础(第五章)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元对称信
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 编码 理论基础 第五 68550
链接地址:https://www.31doc.com/p-9136637.html