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