信息论基础-信道编码理论课件

第4章数据可靠传输和信道编码1第4章数据可靠传输和信道编码1数据可靠传输和信道编码4.1离散无记忆信道和信道容量

4.2

信道容量的计算

4.3信道编码理论

4.4带反馈的信道模型4.5联合信源-信道编码定理4.6线性分组码习题四2数据可靠传输和信道编码4.1离散无记忆信道和信道容量2信道编码理论3信道编码理论3信道编码理论4信道编码理论41译码规则若信道输入符号x，输出符号y，则制定译码规则就是设计函数：g(y)=x.例1.单符号离散信道的信道矩阵信道编码理论g(y1)=x1g(y2)=x2g(y3)=x3g(y1)=x2g(y2)=x1g(y3)=x351译码规则信道编码理论g(y1)=x1g(y1)=x22误差概率定义①离散无记忆信道[Χ,Q(y|x),У]:信源消息集W={1,2,…,M}；编码函数f:W→Χn,如Χn(i)；译码函数g:Уn→W；码率R=(logM)/n；构成一个(M,n)码．信道编码理论消息集在等概条件下每个符号携带的平均信息量（bit）62误差概率信道编码理论消息集在等概条件下每个符号携带的平均定义②信道译码的误差概率：定义③(M,n)码的最大误差概率：定义④(M,n)码的平均误差概率：信道编码理论设计译码规则，使得误差概率最小，即输出符号均译成具有最大后验概率的相应输入符号．7定义②信道译码的误差概率：信道编码理论设计译码规则，使得误差1译码规则若信道输入符号x，输出符号y，则制定译码规则就是设计函数：g(y)=x.例1.单符号离散信道的信道矩阵信道编码理论g(y1)=x1g(y2)=x2g(y3)=x3g(y1)=x2g(y2)=x1g(y3)=x3借助于信道矩阵的传递概率选；称之为最大似然译码！81译码规则信道编码理论g(y1)=x1g(y1)=x23可达码率称码率R是可达的，如果存在一个(2nR,n)码使得4最大可达速率一个离散无记忆信道的最大可达速率为：信道编码理论93可达码率信道编码理论95影响信道传输的因素

最大似然译码：g(y=0)=(x=0),g(y=1)=(x=1)Pe=10-2信道编码理论Pe=10-2实际数据通信系统误差范围10-6~10-9105影响信道传输的因素信道编码理论Pe=10-2实际数据通信6降低错误概率策略①设计好的译码规则；②重复发送→降低信息传输率R；问题：能否找到好的编译方法，使Pe降低，而R保持在一定水平上？信道编码理论116降低错误概率策略信道编码理论117信道编码定理背景香农1948年指出可达、最大的信息传输率是信道容量，从理论上说明了“好码”存在；并且，基于联合ε典型序列进行证明．

╣香农第二基本定理；香农第一基本定理╠信道编码理论无失真变长信源编码定理：存在对离散无记忆信源S的N次扩展信源的唯一可译编码，使得S中每个信源符号所需的平均码长满足：码符号数127信道编码定理背景信道编码理论无失真变长信源编码定理：码符①面向数字信道的信道编码一部分科学家从事寻找最佳编码（纠错码）的研究工作，并已经形成一门独立的分支——纠错码理论．20世纪40年代，Golay和汉明提出分组编码技术，把代数方法引入到纠错码的研究，形成了代数编码理论，找到了大量可纠正多个错误的性能优异的码，而且提出了可实现的编译码方法．分组码中的不少码，如汉明码、Golay码、BCH码等都在通信、计算机技术中获得广泛应用．但是代数编码的渐近性能很差，不能实现香农信道编码定理所指出的结果．于1960年前后，提出了卷积码和概率译码，并逐步形成了一系列概率译码理论．以维特比（Viterbi）译码为代表的译码方法被美国卫星通信系统所采用，使香农理论成为真正具有实用意义的科学理论．1993年提出的Turbo码在性能上已非常接近理论极限．信道编码理论13①面向数字信道的信道编码信道编码理论13利用格子码与软判决理论，使数据传输速度提高了25倍、现有的网络通信成为实用性的技术②面向模拟信道的信道编码1974年，J.L.Massey提出将编码与调制统一考虑的概念．1982年，这一想法在G.Ungerboeck等人的研究下终于取得突破，这就是网格编码调制．网格编码调制在实际应用中发生的相位含糊问题在1984年被L.E.Wei所解决，这一方法随即被CCITT（现为ITU-T）所采纳成为一种标准．现在，网格编码调制正在向卫星通信、磁纪录等领域扩展其应用范围．信道编码理论国际电信联盟远程通信标准化组(ITU-TforITUTelecommunicationStandardizationSector),它是国际电信联盟管理下的专门制定远程通信相关国际标准的组织。14利用格子码与软判决理论，使数据传输速度提高了25倍、现有的信道编码理论在译码理论的研究中，根据对接收信号处理方式的不同，分为硬、软判决。接收时是一个模拟量，因此在送入译码器之前应进行量化处理。最简单的量化是二电平量化(即量化电平Q=2)，也就是硬判决，当接收信号R>0时，判为“0”，否则判为“1”。

这种量化太粗糙，将丢失许多有用的信息，以至于造成信噪比大约2Bd的损失。为了避免二电平量化的这种损失，应当使量化电平数Q>2也就是软判决。Q越大，量化越精细，损失也就越小，但同时译码器也就会越复杂。当量化电平超过8时，编码增益也趋于饱和，因而量化电平通常取Q=8。

软判决Vietbri译码器的结构并不比硬判决的复杂很多，但可以使性能提高

2-3Bd。目前，实用中的Viterbi译码器几乎都是软判决，并且一般都采用8电平均匀量化，其性能基本达到了最大似然译码的性能。15信道编码理论在译码理论的研究中，根据对接收信号处理方式的不同8联合典型序列①定义：关于联合分布p(x,y)的n长联合典型序列{(xn,yn)}的集Wε(n)为信道编码理论平均联合自信息无限接近联合熵的n长序列对的集合168联合典型序列信道编码理论平均联合自信息无限接近联合熵的n②性质：信道编码理论某输入典型序列发送，必是高概率地传送到与它构成联合典型序列的那些序列上17②性质：信道编码理论某输入典型序列发送，必是高概率地传送到与9信道编码定理（香农第二编码定理）

若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R<C

，就一定能找到一种信道编码方法，使得码长足够大时，最大误差概率任意接近于零；反之，最大误差概率可以任意接近零的码（2nR,n），必满足R<C．信道编码理论189信道编码定理（香农第二编码定理）信道编码理论18信道编码理论要想使信息传输率大于信道容量而又无错误地传输消息是不可能的19信道编码理论要想使信息传输率大于信道容量而又无错误地传输消息数据处理不等式：费诺不等式：信道编码理论20数据处理不等式：信道编码理论20数据可靠传输和信道编码4.1离散无记忆信道和信道容量

4.2

信道容量的计算

4.3信道编码理论

4.4带反馈的信道模型4.5联合信源-信道编码定理4.6线性分组码习题四21数据可靠传输和信道编码4.1离散无记忆信道和信道容量21最大似然译码准则→设计译码函数：

F(yj)=x*，s.tp(yj|x*)≥p(yj|xi)有噪信道编码定理信道容量是一个明确的分界点.当R<C

并接近C时，总能克服和消除信道中干扰和噪声引起的错误，实现可靠传输信息.

信道编码—回顾22最大似然译码准则信道编码—回顾22①面向数字信道的信道编码一部分科学家从事寻找最佳编码（纠错码）的研究工作，并已经形成一门独立的分支——纠错码理论．20世纪40年代，Golay和汉明提出分组编码技术，把代数方法引入到纠错码的研究，形成了代数编码理论，找到了大量可纠正多个错误的性能优异的码，而且提出了可实现的编译码方法．分组码中的不少码，如汉明码、Golay码、BCH码等都在通信、计算机技术中获得广泛应用．但是代数编码的渐近性能很差，不能实现香农信道编码定理所指出的结果．于1960年前后，提出了卷积码和概率译码，并逐步形成了一系列概率译码理论．以维特比（Viterbi）译码为代表的译码方法被美国卫星通信系统所采用，使香农理论成为真正具有实用意义的科学理论．1993年提出的Turbo码在性能上已非常接近理论极限．信道编码—回顾23①面向数字信道的信道编码信道编码—回顾23信道编码—回顾纠错码的分类按码的结构中对信息序列的处理方式分组码；卷积码24信道编码—回顾纠错码的分类24信道编码—回顾卷积编码•卷积码由码率R=k/n和约束长度N描述，记做(n,k,N)；•对k-bit输入数据块进行运算（k通常较小，例1,2or3)；•n-bit输出是当前输入块与以前(N-1)个输入块的加权求和，N一般小于9；•卷积码是把k个信息比特编成n个比特，但k和n通常很小.25信道编码—回顾卷积编码25信道编码—回顾卷积码中编码后的n个码元不但与当前段k个信息有关，而且与前面（N-1）段的信息有关；

在编码器复杂性相同的情况下，卷积码的性能优于分组码；分组码有严格的代数结构，但卷积码至今尚未找到严密的数学手段，目前大都采用计算机来搜索好码.26信道编码—回顾卷积码中编码后的n个码元不但与当前段k信道编码—回顾纠错码的分类按码的结构中对信息序列的处理方式分组码；卷积码按具有纠传输错误能力的工作方式反馈重传纠错；前向纠错（自动纠错）；混合纠错27信道编码—回顾纠错码的分类27信道编码—回顾纠错码的分类按码的结构中对信息序列的处理方式分组码；卷积码按具有纠传输错误能力的工作方式

反馈重传纠错；前向纠错（自动纠错）；混合纠错28信道编码—回顾纠错码的分类28带反馈的信道模型29带反馈的信道模型29带反馈的信道模型30带反馈的信道模型30带反馈的信道模型部分出错，只需反馈（重发）该部分.31带反馈的信道模型311带反馈的（2nR,n）信道码

离散无记忆信道[Χ,Q(y|x),У]:消息集W

={1,2,…,M}，M=2nR；编码函数f:W

ΧУ

i-1→У

n,

得码字Уn，其中У

i=У

i(w,У

i-1)；译码函数g:Уn→W；码率R=(logM)/n；带反馈的信道模型321带反馈的（2nR,n）信道码带反馈的信道模型32带反馈的信道模型2最大可达速率定义：带反馈的离散无记忆信道的最大可达速率为问题：增加了反馈信道，信息传输率得以提高，信道容量是否可以提高？33带反馈的信道模型2最大可达速率33带反馈的信道模型定理：设离散无记忆信道的容量为C，带反馈的信道容量为CFB，则证明：CFB≥

C；只须证CFB≤

C.34带反馈的信道模型定理：设离散无记忆信道的容量为C，带反馈34带反馈的信道模型设Pr{W=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)→Xi→Yi是马氏链.35带反馈的信道模型设Pr{W=w}=1/2nR，则(Y1...带反馈的信道模型可得：nR≤1+Pe(n)nR+nC即R≤1/n+Pe(n)R+C从而，当n充分大时，R≤C.所以，36带反馈的信道模型可得：36信道编码-实例通常在公共业务信道中，移动台用自己的电子序列号（ESNs）和系统公共长掩码（PublicLongCodeMask）共同生成可识别的长PN码偏置（Offset）；其中移动台的ESN代码是区别于其他移动用户的有效方式.*#06#手机串号,手机身份证-IMEI(InternationalMobileEquipmentIdentity,国际移动设备身份码),国际移动装备辨识码,由15位数字组成的"电子串号",它与每台手机一一对应,而且该码是全世界唯一的37信道编码-实例通常在公共业务信道中，移动台用自己的电子序列号信道编码-实例第七个和第八个数是下面对应的两个数，那么你的手机质量的好坏就确定了:

0，2or2，0代表是阿拉伯生产的，是很差的手机

0，8or8，0代表是德*生产的，是好一点儿的手机

0，1or1，0代表是芬兰生产的，是非常好的手机

0，0代表是原产公司生产，是质量最好的手机-原装手机）

1，3代表是阿赛拜疆生产的，是非常非常差的手机

38信道编码-实例第七个和第八个数是下面对应的两个数，那么你的手带反馈的信道模型39带反馈的信道模型39带反馈的信道模型不同的手机和基站信道单元都有一个长码生成器.其中长码状态寄存器（LCSR）保持与系统时间的同步，掩码寄存器（MR）存有只有用户可识别的码型.长码状态寄存器（LCSR）每个脉冲周期转变一次状态.状态寄存器（LCSR）和掩码寄存器（MR）合并至加和寄存器（SUMMER）在每个时钟周期内进行模2和计算，逐比特生成长码.生成的移位长码是由用户唯一的偏制（User’sOffset）码型所决定的，加扰后其他用户将无法解调此用户信息.40带反馈的信道模型不同的手机和基站信道单元都有一个长码生成器.带反馈的信道模型41带反馈的信道模型41带反馈的信道模型IMEI42带反馈的信道模型IMEI42第4章数据可靠传输和信道编码43第4章数据可靠传输和信道编码1数据可靠传输和信道编码4.1离散无记忆信道和信道容量

4.2

信道容量的计算

4.3信道编码理论

4.4带反馈的信道模型4.5联合信源-信道编码定理4.6线性分组码习题四44数据可靠传输和信道编码4.1离散无记忆信道和信道容量2信道编码理论45信道编码理论3信道编码理论46信道编码理论41译码规则若信道输入符号x，输出符号y，则制定译码规则就是设计函数：g(y)=x.例1.单符号离散信道的信道矩阵信道编码理论g(y1)=x1g(y2)=x2g(y3)=x3g(y1)=x2g(y2)=x1g(y3)=x3471译码规则信道编码理论g(y1)=x1g(y1)=x22误差概率定义①离散无记忆信道[Χ,Q(y|x),У]:信源消息集W={1,2,…,M}；编码函数f:W→Χn,如Χn(i)；译码函数g:Уn→W；码率R=(logM)/n；构成一个(M,n)码．信道编码理论消息集在等概条件下每个符号携带的平均信息量（bit）482误差概率信道编码理论消息集在等概条件下每个符号携带的平均定义②信道译码的误差概率：定义③(M,n)码的最大误差概率：定义④(M,n)码的平均误差概率：信道编码理论设计译码规则，使得误差概率最小，即输出符号均译成具有最大后验概率的相应输入符号．49定义②信道译码的误差概率：信道编码理论设计译码规则，使得误差1译码规则若信道输入符号x，输出符号y，则制定译码规则就是设计函数：g(y)=x.例1.单符号离散信道的信道矩阵信道编码理论g(y1)=x1g(y2)=x2g(y3)=x3g(y1)=x2g(y2)=x1g(y3)=x3借助于信道矩阵的传递概率选；称之为最大似然译码！501译码规则信道编码理论g(y1)=x1g(y1)=x23可达码率称码率R是可达的，如果存在一个(2nR,n)码使得4最大可达速率一个离散无记忆信道的最大可达速率为：信道编码理论513可达码率信道编码理论95影响信道传输的因素

最大似然译码：g(y=0)=(x=0),g(y=1)=(x=1)Pe=10-2信道编码理论Pe=10-2实际数据通信系统误差范围10-6~10-9525影响信道传输的因素信道编码理论Pe=10-2实际数据通信6降低错误概率策略①设计好的译码规则；②重复发送→降低信息传输率R；问题：能否找到好的编译方法，使Pe降低，而R保持在一定水平上？信道编码理论536降低错误概率策略信道编码理论117信道编码定理背景香农1948年指出可达、最大的信息传输率是信道容量，从理论上说明了“好码”存在；并且，基于联合ε典型序列进行证明．

╣香农第二基本定理；香农第一基本定理╠信道编码理论无失真变长信源编码定理：存在对离散无记忆信源S的N次扩展信源的唯一可译编码，使得S中每个信源符号所需的平均码长满足：码符号数547信道编码定理背景信道编码理论无失真变长信源编码定理：码符①面向数字信道的信道编码一部分科学家从事寻找最佳编码（纠错码）的研究工作，并已经形成一门独立的分支——纠错码理论．20世纪40年代，Golay和汉明提出分组编码技术，把代数方法引入到纠错码的研究，形成了代数编码理论，找到了大量可纠正多个错误的性能优异的码，而且提出了可实现的编译码方法．分组码中的不少码，如汉明码、Golay码、BCH码等都在通信、计算机技术中获得广泛应用．但是代数编码的渐近性能很差，不能实现香农信道编码定理所指出的结果．于1960年前后，提出了卷积码和概率译码，并逐步形成了一系列概率译码理论．以维特比（Viterbi）译码为代表的译码方法被美国卫星通信系统所采用，使香农理论成为真正具有实用意义的科学理论．1993年提出的Turbo码在性能上已非常接近理论极限．信道编码理论55①面向数字信道的信道编码信道编码理论13利用格子码与软判决理论，使数据传输速度提高了25倍、现有的网络通信成为实用性的技术②面向模拟信道的信道编码1974年，J.L.Massey提出将编码与调制统一考虑的概念．1982年，这一想法在G.Ungerboeck等人的研究下终于取得突破，这就是网格编码调制．网格编码调制在实际应用中发生的相位含糊问题在1984年被L.E.Wei所解决，这一方法随即被CCITT（现为ITU-T）所采纳成为一种标准．现在，网格编码调制正在向卫星通信、磁纪录等领域扩展其应用范围．信道编码理论国际电信联盟远程通信标准化组(ITU-TforITUTelecommunicationStandardizationSector),它是国际电信联盟管理下的专门制定远程通信相关国际标准的组织。56利用格子码与软判决理论，使数据传输速度提高了25倍、现有的信道编码理论在译码理论的研究中，根据对接收信号处理方式的不同，分为硬、软判决。接收时是一个模拟量，因此在送入译码器之前应进行量化处理。最简单的量化是二电平量化(即量化电平Q=2)，也就是硬判决，当接收信号R>0时，判为“0”，否则判为“1”。

这种量化太粗糙，将丢失许多有用的信息，以至于造成信噪比大约2Bd的损失。为了避免二电平量化的这种损失，应当使量化电平数Q>2也就是软判决。Q越大，量化越精细，损失也就越小，但同时译码器也就会越复杂。当量化电平超过8时，编码增益也趋于饱和，因而量化电平通常取Q=8。

软判决Vietbri译码器的结构并不比硬判决的复杂很多，但可以使性能提高

2-3Bd。目前，实用中的Viterbi译码器几乎都是软判决，并且一般都采用8电平均匀量化，其性能基本达到了最大似然译码的性能。57信道编码理论在译码理论的研究中，根据对接收信号处理方式的不同8联合典型序列①定义：关于联合分布p(x,y)的n长联合典型序列{(xn,yn)}的集Wε(n)为信道编码理论平均联合自信息无限接近联合熵的n长序列对的集合588联合典型序列信道编码理论平均联合自信息无限接近联合熵的n②性质：信道编码理论某输入典型序列发送，必是高概率地传送到与它构成联合典型序列的那些序列上59②性质：信道编码理论某输入典型序列发送，必是高概率地传送到与9信道编码定理（香农第二编码定理）

若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R<C

，就一定能找到一种信道编码方法，使得码长足够大时，最大误差概率任意接近于零；反之，最大误差概率可以任意接近零的码（2nR,n），必满足R<C．信道编码理论609信道编码定理（香农第二编码定理）信道编码理论18信道编码理论要想使信息传输率大于信道容量而又无错误地传输消息是不可能的61信道编码理论要想使信息传输率大于信道容量而又无错误地传输消息数据处理不等式：费诺不等式：信道编码理论62数据处理不等式：信道编码理论20数据可靠传输和信道编码4.1离散无记忆信道和信道容量

4.2

信道容量的计算

4.3信道编码理论

4.4带反馈的信道模型4.5联合信源-信道编码定理4.6线性分组码习题四63数据可靠传输和信道编码4.1离散无记忆信道和信道容量21最大似然译码准则→设计译码函数：

F(yj)=x*，s.tp(yj|x*)≥p(yj|xi)有噪信道编码定理信道容量是一个明确的分界点.当R<C

并接近C时，总能克服和消除信道中干扰和噪声引起的错误，实现可靠传输信息.

信道编码—回顾64最大似然译码准则信道编码—回顾22①面向数字信道的信道编码一部分科学家从事寻找最佳编码（纠错码）的研究工作，并已经形成一门独立的分支——纠错码理论．20世纪40年代，Golay和汉明提出分组编码技术，把代数方法引入到纠错码的研究，形成了代数编码理论，找到了大量可纠正多个错误的性能优异的码，而且提出了可实现的编译码方法．分组码中的不少码，如汉明码、Golay码、BCH码等都在通信、计算机技术中获得广泛应用．但是代数编码的渐近性能很差，不能实现香农信道编码定理所指出的结果．于1960年前后，提出了卷积码和概率译码，并逐步形成了一系列概率译码理论．以维特比（Viterbi）译码为代表的译码方法被美国卫星通信系统所采用，使香农理论成为真正具有实用意义的科学理论．1993年提出的Turbo码在性能上已非常接近理论极限．信道编码—回顾65①面向数字信道的信道编码信道编码—回顾23信道编码—回顾纠错码的分类按码的结构中对信息序列的处理方式分组码；卷积码66信道编码—回顾纠错码的分类24信道编码—回顾卷积编码•卷积码由码率R=k/n和约束长度N描述，记做(n,k,N)；•对k-bit输入数据块进行运算（k通常较小，例1,2or3)；•n-bit输出是当前输入块与以前(N-1)个输入块的加权求和，N一般小于9；•卷积码是把k个信息比特编成n个比特，但k和n通常很小.67信道编码—回顾卷积编码25信道编码—回顾卷积码中编码后的n个码元不但与当前段k个信息有关，而且与前面（N-1）段的信息有关；

在编码器复杂性相同的情况下，卷积码的性能优于分组码；分组码有严格的代数结构，但卷积码至今尚未找到严密的数学手段，目前大都采用计算机来搜索好码.68信道编码—回顾卷积码中编码后的n个码元不但与当前段k信道编码—回顾纠错码的分类按码的结构中对信息序列的处理方式分组码；卷积码按具有纠传输错误能力的工作方式反馈重传纠错；前向纠错（自动纠错）；混合纠错69信道编码—回顾纠错码的分类27信道编码—回顾纠错码的分类按码的结构中对信息序列的处理方式分组码；卷积码按具有纠传输错误能力的工作方式

反馈重传纠错；前向纠错（自动纠错）；混合纠错70信道编码—回顾纠错码的分类28带反馈的信道模型71带反馈的信道模型29带反馈的信道模型72带反馈的信道模型30带反馈的信道模型部分出错，只需反馈（重发）该部分.73带反馈的信道模型311带反馈的（2nR,n）信道码

离散无记忆信道[Χ,Q(y|x),У]:消息集W

={1,2,…,M}，M=2nR；编码函数f:W

ΧУ

i-1→У

n,

得码字Уn，其中У

i=У

i(w,У

i-1)；译码函数g:Уn→W；码率R=(logM)/n；带反馈的信道模型741带反馈的（2nR,n）信道码带反馈的信道模型32带反馈的信道模型2最大可达速率定义：带反馈的离散无记忆信道的最大可达速率为问题：增加了反馈信道，信息传输率得以提高，信道容量是否可以提高？75带反馈的信道模型2最大可达速率33带反馈的信道模型定理：设离散无记忆信道的容量为C，带反馈的信道容量为CFB，则证明：CFB≥

C；只须证CFB≤

C.76带反馈的信道模型定理：设离散无记忆信道的容量为C，带反馈34带反馈的信道模型设Pr{W=w}=1/2nR，则nR=H(W)=H(W|Yn)+I(W;Yn);由费诺不等式，得到H(W|