信息论基础信道编码理论课件.ppt

第4章 数据可靠传输和信道编码,2,数据可靠传输和信道编码,4.1 离散无记忆信道和信道容量 4.2 信道容量的计算 4.3 信道编码理论 4.4 带反馈的信道模型4.5 联合信源-信道编码定理4.6 线性分组码习题四,3,信道编码理论,4,信道编码理论,5,1 译码规则 若信道输入符号x，输出符号y，则制定译码规则就是设计函数：g(y)= x.例1.单符号离散信道的信道矩阵,信道编码理论,g(y1)= x1g(y2)= x2g(y3)= x3,g(y1)= x2g(y2)= x1g(y3)= x3,6,2 误差概率定义离散无记忆信道,Q(y|x),: 信源消息集W=1,2,M； 编码函数f:W n,如n(i)； 译码函数g:nW； 码率R=(logM)/n；构成一个(M, n)码,信道编码理论,消息集在等概条件下每个符号携带的平均信息量（bit）,7,定义信道译码的误差概率：定义(M, n)码的最大误差概率：定义(M, n)码的平均误差概率：,信道编码理论,设计译码规则，使得误差概率最小，即输出符号均译成具有最大后验概率的相应输入符号,8,1 译码规则 若信道输入符号x，输出符号y，则制定译码规则就是设计函数：g(y)= x.例1.单符号离散信道的信道矩阵,信道编码理论,g(y1)= x1g(y2)= x2g(y3)= x3,g(y1)= x2g(y2)= x1g(y3)= x3,借助于信道矩阵的传递概率选；称之为最大似然译码！,9,3 可达码率 称码率R是可达的，如果存在一个(2nR,n)码使得4 最大可达速率 一个离散无记忆信道的最大可达速率为：,信道编码理论,10,5 影响信道传输的因素 最大似然译码：g(y=0)=(x=0), g(y=1)=(x=1) Pe=10-2,信道编码理论,Pe=10-2,实际数据通信系统误差范围10-610-9,11,6 降低错误概率策略设计好的译码规则；重复发送降低信息传输率R ；问题：能否找到好的编译方法，使Pe降低， 而R保持在一定水平上？,信道编码理论,12,7 信道编码定理背景 香农1948年指出可达、最大的信息传输率是信道容量，从理论上说明了“好码”存在；并且，基于联合典型序列进行证明 香农第二基本定理； 香农第一基本定理,信道编码理论,无失真变长信源编码定理：存在对离散无记忆信源S的N次扩展信源的唯一可译编码，使得S中每个信源符号所需的平均码长满足：,码符号数,13, 面向数字信道的信道编码一部分科学家从事寻找最佳编码（纠错码）的研究工作，并已经形成一门独立的分支纠错码理论20世纪40年代，Golay和汉明提出分组编码技术，把代数方法引入到纠错码的研究，形成了代数编码理论，找到了大量可纠正多个错误的性能优异的码，而且提出了可实现的编译码方法分组码中的不少码，如汉明码、Golay码、BCH码等都在通信、计算机技术中获得广泛应用但是代数编码的渐近性能很差，不能实现香农信道编码定理所指出的结果于1960年前后，提出了卷积码和概率译码，并逐步形成了一系列概率译码理论以维特比（Viterbi）译码为代表的译码方法被美国卫星通信系统所采用，使香农理论成为真正具有实用意义的科学理论1993年提出的Turbo码在性能上已非常接近理论极限,信道编码理论,14,利用格子码与软判决理论，使数据传输速度提高了25 倍、现有的网络通信成为实用性的技术,面向模拟信道的信道编码1974年，J.L.Massey提出将编码与调制统一考虑的概念1982年，这一想法在G.Ungerboeck等人的研究下终于取得突破，这就是网格编码调制网格编码调制在实际应用中发生的相位含糊问题在1984年被L.E.Wei所解决，这一方法随即被CCITT（现为ITU-T）所采纳成为一种标准现在，网格编码调制正在向卫星通信、磁纪录等领域扩展其应用范围,信道编码理论,国际电信联盟远程通信标准化组(ITU-T for ITU Telecommunication Standardization Sector), 它是国际电信联盟管理下的专门制定远程通信相关国际标准的组织。,15,信道编码理论,在译码理论的研究中，根据对接收信号处理方式的不同，分为硬、软判决。接收时是一个模拟量，因此在送入译码器之前应进行量化处理。最简单的量化是二电平量化(即量化电平Q=2)，也就是硬判决，当接收信号R0时，判为“0”，否则判为“1”。这种量化太粗糙，将丢失许多有用的信息，以至于造成信噪比大约2Bd的损失。为了避免二电平量化的这种损失，应当使量化电平数Q2也就是软判决。Q越大，量化越精细，损失也就越小，但同时译码器也就会越复杂。当量化电平超过8时，编码增益也趋于饱和，因而量化电平通常取Q=8。软判决Vietbri译码器的结构并不比硬判决的复杂很多，但可以使性能提高2-3Bd。目前，实用中的Viterbi译码器几乎都是软判决，并且一般都采用8电平均匀量化，其性能基本达到了最大似然译码的性能。,16,8 联合典型序列定义：关于联合分布p(x,y)的n长联合典型序列(xn,yn)的集W(n)为,信道编码理论,平均联合自信息无限接近联合熵的n长序列对的集合,17,性质：,信道编码理论,某输入典型序列发送，必是高概率地传送到与它构成联合典型序列的那些序列上,18,9 信道编码定理（香农第二编码定理） 若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率RC ，就一定能找到一种信道编码方法，使得码长足够大时，最大误差概率任意接近于零； 反之，最大误差概率可以任意接近零的码 （2nR,n），必满足RC,信道编码理论,19,信道编码理论,要想使信息传输率大于信道容量而又无错误地传输消息是不可能的,20,数据处理不等式：费诺不等式：,信道编码理论,21,数据可靠传输和信道编码,4.1 离散无记忆信道和信道容量 4.2 信道容量的计算 4.3 信道编码理论 4.4 带反馈的信道模型4.5 联合信源-信道编码定理4.6 线性分组码习题四,22,最大似然译码准则 设计译码函数： F(yj)=x*，s.t p(yj| x*) p(yj| xi)有噪信道编码定理 信道容量是一个明确的分界点. 当RC 并接近C时，总能克服和消除信道中干扰和噪声引起的错误，实现可靠传输信息.,信道编码回顾,23, 面向数字信道的信道编码一部分科学家从事寻找最佳编码（纠错码）的研究工作，并已经形成一门独立的分支纠错码理论20世纪40年代，Golay和汉明提出分组编码技术，把代数方法引入到纠错码的研究，形成了代数编码理论，找到了大量可纠正多个错误的性能优异的码，而且提出了可实现的编译码方法分组码中的不少码，如汉明码、Golay码、BCH码等都在通信、计算机技术中获得广泛应用但是代数编码的渐近性能很差，不能实现香农信道编码定理所指出的结果于1960年前后，提出了卷积码和概率译码，并逐步形成了一系列概率译码理论以维特比（Viterbi）译码为代表的译码方法被美国卫星通信系统所采用，使香农理论成为真正具有实用意义的科学理论1993年提出的Turbo码在性能上已非常接近理论极限,信道编码回顾,24,信道编码回顾,纠错码的分类按码的结构中对信息序列的处理方式 分组码；卷积码,25,信道编码回顾,卷积编码卷积码由码率 R=k/n 和约束长度 N 描述，记做 (n, k, N)； 对 k-bit 输入数据块进行运算（k 通常较小，例1,2 or 3)； n-bit 输出是当前输入块与以前 (N-1) 个输入块的加权求和，N 一般小于 9； 卷积码是把 k 个信息比特编成n个比特，但 k 和 n 通常很小.,26,信道编码回顾,卷积码中编码后的 n 个码元不但与当前段 k 个信息有关，而且与前面（N-1）段的信息有关； 在编码器复杂性相同的情况下，卷积码的性能优于分组码；分组码有严格的代数结构，但卷积码至今尚未找到严密的数学手段，目前大都采用计算机来搜索好码.,27,信道编码回顾,纠错码的分类按码的结构中对信息序列的处理方式 分组码；卷积码按具有纠传输错误能力的工作方式 反馈重传纠错； 前向纠错（自动纠错）； 混合纠错,28,信道编码回顾,纠错码的分类按码的结构中对信息序列的处理方式 分组码；卷积码按具有纠传输错误能力的工作方式 反馈重传纠错； 前向纠错（自动纠错）； 混合纠错,29,带反馈的信道模型,30,带反馈的信道模型,31,带反馈的信道模型,部分出错，只需反馈（重发）该部分.,32,1 带反馈的（2nR,n）信道码 离散无记忆信道,Q(y|x),: 消息集W =1,2,M，M=2nR ； 编码函数f: W i-1 n, 得码字n ，其中 i= i (w, i-1)； 译码函数g:nW； 码率R=(logM)/n；,带反馈的信道模型,33,带反馈的信道模型,2 最大可达速率定义：带反馈的离散无记忆信道的最大可达速率为问题：增加了反馈信道，信息传输率得以提高，信道容量是否可以提高？,34,带反馈的信道模型,定理：设离散无记忆信道的容量为C，带反馈的信道容量为CFB，则证明：CFB C；只须证CFB C.,35,带反馈的信道模型,设PrW=w=1/2nR，则 nR=H(W)=H(W|Yn)+I(W;Yn);由费诺不等式，得到 H(W|Yn)1+Pe(n)nR; 而 I(W;Yn)= H(Yn)-H(Yn|W) = H(Yn)-H(Yi|Y1Y2.Yi-1W) = H(Yn)-H(Yi|Y1Y2.Yi-1W,Xi) = H(Yn)-H(Yi|Xi)H(Yi)-H(Yi|Xi) =I(Xi;Yi)nC ,(Y1.Yi-1) XiYi是马氏链.,36,带反馈的信道模型,可得： nR1+Pe(n)nR+ nC即 R1/n+Pe(n)R+ C从而，当n充分大时，RC.所以，,37,信道编码-实例,通常在公共业务信道中，移动台用自己的电子序列号（ESNs）和系统公共长掩码（PublicLongCodeMask）共同生成可识别的长PN码偏置（Offset）；其中移动台的ESN代码是区别于其他移动用户的有效方式.,*#06#手机串号,手机身份证 -IMEI (International Mobile Equipment Identity,国际移动设备身份码),国际移动装备辨识码,由15位数字组成的电子串号,它与每台手机一一对应,而且该码是全世界唯一的,38,信道编码-实例,第七个和第八个数是下面对应的两个数，那么你的手机质量的好坏就确定了: 0，2or2，0代表是阿拉伯生产的，是很差的手机 0，8or8，0代表是德*生产的，是好一点儿的手机 0，1or1，0代表是芬兰生产的，是非常好的手机 0，0代表是原产公司生产，是质量最好的手机-原装手机） 1，3代表是阿赛拜疆生产的，是非常非常差的手机,39,带反馈的信道模型,40,带反馈的信道模型,不同的手机和基站信道单元都有一个长码生成器.其中长码状态寄存器（LCSR）保持与系统时间的同步，掩码寄存器（MR）存有只有用户可识别的码型.长码状态寄存器（LCSR）每个脉冲周期转变一次状态.状态寄存器（LCSR）和掩码寄存器（MR）合并至加和寄存器（SUMMER）在每个时钟周期内进行模2和计算，逐比特生成长码.生成的移位长码是由用户唯一的 偏制（UsersOffset）码型 所决定的，加扰后其他用户将无法解调此用户信息.,41,带反馈的信道模型,42,带反馈的信道模型,IMEI,