信息论与编码全套课件电子教案板

信息论与编码第一部分信息论基础（第一章‐第五章）从学科方向说起信息科学信息与通信工程电子科学与技术计算机科学与技术控制科学与技术。。。信息产业的两大支柱：通信+计算机信息与通信工程：研究信息有效获取、表达、存储、传输与处理的系统科学与工程技术；信息论——信息科学发展的源泉和动力信息论信息科学发展的思想源泉和动力通信与信息系统的基础理论信息论与通信原理、通信技术前者：揭示信息获取、表达、传输与处理等过程所包含的本质规律与所应遵循的基本设计原则后者：具体环境和条件下通信过程的基本原理、具体实现方法、手段和技术信息论与现代信号处理理论虚实相生、相辅相成现代通信与信息系统研究与实现的两大理论支柱经典信息论所研究的若干基本问题信源编码问题信息是什么？理论上至少应该以什么样的速率才能无差错地表达一个信源所包含的信息？信道编码问题给定一个信道，理论上通过该信道最多能以多大的速率无差错地传递信息？……Shannon的回答信源编码当编码速率大于信源的熵速率即可实现渐进无差错地表达信道编码当传信率比信道容量高时，必然发送差错，反之，则可以实现渐进无差错地传输信息论革命性的指导意义（I）奠定了通信的基础理论，它所确定的理论极限是人类追求的目标，也是近代几乎所有通信技术取得重大突破的理论动力和思想源泉也带动了整个信息科学的发展，产生了很多信息科学的边缘学科和交叉学科，例如量子信息论，生物信息学，等等现代信息论蓬勃发展，导致网络通信、多用户通信、分布式通信、极限通信等许多学科方向的发展，新理论与新技术日新月异，层出不穷信息论革命性的指导意义（II）1993年，受Shannon随机编码思想的启示，C.Berrou等人提出了著名的基于交织级联和迭代译码的Turbo码，首次获得了逼近Shannon容量极限的性能，这一里程碑式的重大突破奠定了第三代无线移动通信的基础。1999年，D.J.Mackay等人重新发掘出R.G.Gallager早期研究的LDPC码，并且发现在迭代译码的方式下这也是一类能够逼近Shannon极限的好码。随机编码与迭代译码一时被认为是逼近Shannon极限的最为实用和有效的方法。信息论革命性的指导意义（III）1995年，I.E.Telatar第一次将单天线高斯信道的容量理论推广到多天线的情形，由此获得了一个令人震惊的结论：一定条件下，信道容量可随天线数目的增加而同比例增大，由此奠定了多天线（MIMO）通信理论的基础。随着BellLabs的实验证实和不断完善，多天线技术正式成为第三代/第四代无线通信实现容量增强不可或缺的核心技术。它同时也在理论上极大地丰富了经典Shannon信息论，并成为现代信息论中一个活跃的分支——多端网络的重要研究方向。信息论革命性的指导意义（IV）本世纪初信息与编码理论领域最激动人心的突破来自于华人学者RaymondYeung，NingCai和RobertLi及其合作者，这就是著名的网络编码理论。他们通过改变网络节点的简单存储转发方式，而进行适当的编码转发，即可获得网络流的最小割容量，从而大大提升网络多播的效率。如今，网络编码已经形成了一个庞大的编码理论体系，涉及到网络源编码、网络内容分送(组播、P2P等)、网络纠错、网络保密的各个方面，受到全球众多研究机构的关注和研究。这是华人学者为世界所作出的开创性贡献。1948年香农创立信息论信息论之父（比特之父）ClaudeElwoodShannon

1916.4.30-2001.2.24C.E.Shannon——信息论之父，比特之父

20岁从密歇根大学毕业；22岁在MIT获硕士，24岁获博士随后在BellLab.从事通信、密码、计算机等领域研究

1945年“保密的数学理论”；

32岁（1948年）“通信的数学理论”；

1956年回到MIT，重新研究信息论，在他下面集聚了一批年青学者和研究生，Fano,Elias,Gallager,Berlekamp,Forney,Ziv,Massey,Wyner,…，建立和发展了Shannon意义下信息论。

提出了信息量的精确定义和度量－熵和“比特”信源编码定理，信道编码定理，率失真定理；信道和信源分离编码定理；多用户信息理论（双向通信理论，反馈通信，发射端具有边信息的通信）；开关电路与布尔代数；保密的数学理论；人工智能（计算机下棋）；方法学上：典型列理论；随机编码理论；C.E.Shannon的伟大成就Ihaveoftenremarkedthatthetransistorandinformationtheory,twoBellLaboratoriesbreakthroughswithinmonthsofeachother,havelaunchedandpoweredthevehicleofmoderndigitalcommunications.Solidstateelectronicsprovidedtheenginewhileinformationtheorygaveusthesteeringwheelwithwhichtoguideit.

A.Viterbi对信息论的评价本课程的定位本课程是信息科学领域电子信息类专业的重要专业基础课程，主要用以了解和认识一般通信与信息系统的基本概念、本质规律与性能极限，并掌握其基本的设计方法和原则，为进一步深入学习和研究通信与信息系统的新理论与新技术、学习和研究多用户信息论与网络信息论奠定基础。本课程的研究内容主要介绍信息的基本概念与度量方法、信源无损压缩及其编码定理、信道容量及信道编码定理、率失真理论等内容绪论（1学时）信息的概念和度量：熵和互信息（7学时）离散无记忆信源的无损压缩编码（8学时）信道、信道容量与信道编码定理（11学时）率失真理论与限失真信源编码（7学时）本课程的基本要求重点掌握信息的基本概念和基本定理的内涵，了解信息论的重要思想与方法，关注信息论的典型应用课程评价方法：作业与平时成绩（含点名）：20%考试成绩：80%本课程的教材和参考书仇佩亮，《信息论与编码》，高等教育出版社，“十五”国家级规划教材，2003年第一版T.M.Cover，《ElementsofInformationTheory》，thesecondedition,Wiley，2006.第二章熵与互信息符号系统X,Y：随机变量（待观测变量）xk

,

yj

:变量取值（观测值）ak,bj:变量取值（观测值）

X={xk;k=1,2,…,K};Y={yj;j=1,2,…,J}:变量值域事件：X=xk或X=ak

;Y=yj或Y=bjqk=Pr{X=xk},wj=Pr{Y=yj}概率论基础知识对联合变量对（二维随机矢量）

有：

事件的自信息事件的发生通常会对外界提供信息。人们对信息的感受与事件发生的概率密切相关我们将特定事件X=xk发生后给外界带来的信息量定义为该事件的自信息当对数的底a取为2时，自信息的单位为比特（bit）；当对数底取为e时，单位称为奈特（nat）。公理化的定义事件自信息的本质事件发生后对外界（观察者）所提供的信息量事件发生前外界（观察者）为确证该事件的发生所需要的信息量，也是外界为确证该事件所需要付出的代价事件的自信息并不表示事件的不确定性，事件本身没有不确定性可言，它要么是观察的假设和前提，要么是观察的结果事件的条件自信息联合变量：事件

发生的条件下事件的条件自信息定义为：事件Y=yj

发生后事件X=xk的发生还能再给外界提供的“新”的信息量事件的联合自信息联合变量：所对应的事件

和联合发生所带来的联合自信息定义为：事件X=xk与事件Y=yj同时发生对外界提供的信息量事件的互信息联合变量：所对应的事件

和相互之间所提供的互信息定义为：事件互信息的本质事件X=xk发生后提供给外界的信息量事件Y=yj发生后事件X=xk还能提供给外界的新信息量事件Y=yj中包含的有关事件X=xk信息量事件互信息的性质事件的条件互信息

事件Z=z已知的条件下事件X=x与事件Y=y相互提供的信息量事件的联合互信息事件Y=y和Z=z联合提供的有关事件X=x的信息量事件联合互信息的链式法则事件Y=y和Z=z联合提供的有关事件X=x的信息量，等于Y=y提供的有关事件X=x的信息量再加上事件Y=y已知的条件下事件Z=z所提供的有关X=x的新信息量。变量的平均自信息——熵

我们更关心变量在其取值集合总体上平均每次观测所能获得的信息量熵的本质（I）p10.510H(p)p越接近于0或者1（X确定性越高），熵越小；p越接近于0.5（X越不确定），熵越大熵的本质（II）熵是随机变量不确定性的度量熵是随机变量每次观察结果平均对外界所提供的信息量熵是为了确证随机变量的取值外界平均所需要的与之相关的信息量条件熵以事件Y=y为条件的变量X的熵以变量Y为条件的变量X的熵

疑义度：Y已知的条件下X的剩余不确定性联合熵

随机变量X和Y的联合熵（联合不确定性）联合熵的链式法则熵的性质（I）熵的性质（II）熵的性质（III）X2={A1,A2,A3,B1,B2}X1={A,B}（5）可加性熵的性质（IV）对变量X可以进行多步分层的观察，每一步都可从上一步观察结果中得到更为细致的结果，变量X在最后的观察结果集合中的不确定性等于第一次观察结果的不确定性，加上其后每次观察结果在前一次观察结果已知的前提下的条件不确定性熵的性质（V）（6）极值性证明：对任何概率矢量q均成立。因为：（因）

令即得。熵的性质（VI）（7）凸性授课小结事件的自信息，条件自信息，联合自信息事件联合自信息的链式法则熵的概念及其本质条件熵，联合熵，联合熵的链式法则熵的性质作业复习授课内容预习2.1.5至2.2.2节独立完成习题（每章交一次）2.12.22.42.52.6凸函数（下凸函数,ConvexFunction）凹函数（上凸函数,ConcaveFunction）非负凸集上的上凸函数取极大值的充要条件概率空间上的上凸函数取极大值的充要条件随机变量间的平均互信息二个事件X=x与Y=y之间的相互提供的信息量定义为联合随机变量{(X,Y),X

Y,p(x,y)}相互提供的平均信息量称之为二者之间的平均互信息，简称互信息：互信息的性质（I）

（1）非负性证明：互信息的性质（II）（2）对称性（3）互信息与熵的关联性互信息的性质（III）（4）互信息与熵的大小关系

等号成立的条件是Y是X的确定性函数。等号成立的条件是X是Y的确定性函数；随机变量间的条件互信息在随机变量Z已知的条件下变量X与Y相互提供的信息量为随机变量间的联合互信息及链式法则随机变量Y和Z共同提供给变量X的信息量为例：互信息的应用有两个硬币，一个是真币（一面国徽，一面面值），另一个是假币（两面都是面值）。随机抽取一个硬币，抛掷2次。问出现面值的次数对于硬币的识别提供多少信息？XY1/41/21/4101120X=0，真币；X=1，假币。Y=面值出现的次数1/21/21/81/45/8例：互信息的应用（续）XY1/41/21/4101120相对熵（散度）定义在相同字符表X上的两个概率分布{p(x)}和{q(x)}之间的相对熵（散度），或称Kullback-Leibler距离，表示为：表示实际分布{p(x)}与假定分布{q(x)}之间的平均差距，因而也称鉴别熵。相对熵的性质（1）（2）（3）关于疑义度的Fano不等式（I）关于疑义度的Fano不等式（II）证明：授课小结随机变量间的平均互信息的定义互信息的性质相对熵的定义和性质关于疑义度的Fano不等式（重点）作业复习授课内容预习2.1.6至2.2.2节独立完成习题（每章交一次）2.92.102.122.132.17马尔可夫链（I）p(x2|x1)p(xn|xn-1)X1X2p(x3|x2)X3Xn-1Xn

马尔可夫链（II）性质：XYZ数据处理定理XYZ证明：由于故四变量马尔可夫链UXYV证明：互信息的凸性（I）互信息I(X;Y)是关于输入分布{q(x)}和转移概率矩阵{p(y|x)}的函数互信息的凸性（II）{q1(x)}ZX{p(y|x)}{q2(x)}Y{q

(x)}互信息的凸性（III）{q(x)}ZX{p2(y|x)}Y{p1(y|x)}{p(y|x)}=0>=0授课小结随机变量间的平均互信息互信息的基本性质相对熵关于疑义度的Fano不等式马尔科夫链数据处理定理互信息的凸性作业复习授课内容预习2.2至2.4节独立完成习题（每章交一次）2.20连续随机变量的概率密度连续随机变量的离散化连续随机变量的互信息（I）连续随机变量的互信息（II）连续随机变量的微分熵微分熵的本质和性质条件微分熵与联合微分熵及其性质熵功率例：微分熵的极大化（I）：峰值受限微分熵的极大化（II）：功率受限熵功率不等式授课小结互信息的凸性连续随机变量的互信息及其性质连续随机变量的微分熵及其性质微分熵的最大化熵功率不等式作业复习授课内容预习2.3节独立完成习题（每章交一次）2.21平稳源平稳源的熵平稳源的熵的性质（I）平稳源的熵的性质（II）平稳源的熵的性质（III）平稳源的熵的性质（IV）熵速率（熵率）马尔科夫源马尔科夫源的状态图表示s1sKmsisjxk;pij(n)xl;pji(n)时齐既约马尔科夫源的稳态状态分布马尔科夫源的熵率例：二状态马尔科夫源的熵率sisj

1-

1-授课小结平稳源的平均符号熵、条件熵平稳源的熵的性质平稳源的熵率马尔科夫源及其熵率作业复习授课内容预习3.1节独立完成习题（每章交一次，下次课交作业）2.232.252.26（选做）第三章离散无记忆信源（DMS）的无损编码DMS的编码信源编码无损编码有损编码（限失真编码）绝对无差错编码渐进无差错编码目标：在代价最小的意义上来最有效地表达一个信源。包括量化、压缩、映射、变换、自然语言翻译等许多具体和抽象的过程。DMS编解码系统概念框图DMSuLC(uL)xN无扰信道xND(xN)uL信宿^绝对无差错等长编码DMS编码符号集即编码速率渐进无差错等长编码AEP性质（I）AEP性质（II）AEP性质（III）由契比雪夫不等式可得给定，当L充分大时故典型列集合典型列性质（1）：当L足够大时，典型列性质典型列性质（2）：典型列性质（3）：证明：DMS编码定理DMS编码定理的证明DMS的不等长编码

消息集概率分布码长码字不等长码的例子1110011111100.125a41100110010.125a31001100.25a200000.5a1码D码C码B码A出现概率信源消息不等长码的基本要求唯一可译性即时可译性唯一可译性非奇异性码扩展定义：码的任意扩展都是非奇异的，则称码是唯一可译的。唯一可译性的Sardinas&Petterson判据后缀分解后缀分解示例S0=CS1S2S3S4S5

0

10

12

21

112

1122

2102121221220121221Sardinas&Petterson判据一个码是唯一可译码的充分必要条件是除S0外没有任何一个后缀分解集中包含码字。若S1=

，则该码是即时可译并且唯一可译的。异字头码如果一个码中没有任何一个码字是其它码字的前缀，则称该码是异字头码，即S1=

。异字头码的树形表示：所有码字只出现在叶结点上0级节点（1）（2）（3）(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,3,1)(3,3,2)(3,3,3)一级节点二级节点AKraft不等式存在长度为的D元异字头码的充要条件为

12D

第层Kraft不等式的证明必要性：充分性：唯一可译码与Kraft不等式任何唯一可译码必然满足Kraft不等式。证明：

r个码字所构成的序列的长度唯一可译码与异字头码的关系如果一个码是唯一可译Kraft不等式成立存在一个具有同样长度的异字头码。

不等长编码定理不等长编码定理的证明（I）（1）不等长编码定理的证明（II）（2）不等长编码定理的扩展授课小结信源编码的基本概念（编码速率等）AEP性质DMS等长编码定理不等长编码的概念唯一可译性与Kraft不等式DMS不等长编码定理作业复习授课内容预习3.3节独立完成习题（每章交一次，下次课交第二章作业）3.13.2（选做）3.33.4最佳不等长编码（Huffman编码）最佳不等长码：给定信源分布，在平均码长最 短的意义上最佳二元最佳码：给定信源分布，其最佳二元编码必然满足：1）其出现概率越小的消息所对应的码长越长；2）出现概率最小的两个消息所对应的码长相等，且其码字最后一位不同最佳不等长编码（Huffman编码）

1）最佳不等长编码（Huffman编码）

2）最佳不等长编码（Huffman编码）

3）辅助源可递归编码原理对辅助源U’的最佳编码也是对原始源的最佳编码。Huffman编码(1)(0)0.60.200.190.180.170.150.100.0070.003a1a2a3a4a5a6a7a8(11)(10)(011)(010)(001)(0001)(00001)(00000)0.26(1)(0)(1)(0)0.01(1)(0)0.110.35(1)(0)1.00.39(1)(0)(1)(0)

D元Huffman编码的虚拟消息合并0.200.190.180.170.150.100.0070.0030.00.0a1a2a3a4a5a6a7a8a9a10(1)(2)(3)(00)(01)(02)(030)(031)(3)0.01(0)(1)(2)(0)(1)(2)(3)(0)(1)(2)(3)0.431.0思考题：如何进一步增加编码效率？授课小结唯一可译性与Kraft不等式DMS不等长编码定理最优不等长编码（Huffman编码）作业复习授课内容预习3.3节独立完成习题（每章交一次）3.63.73.93.103.12Shannon编码Shannon编码的异字头性Shannon编码的效率与Huffman码相比，Shannon码渐进收敛性能较差，但具有竞争最优性Fano编码概率和对分法Fano编码的效率(1,6)(1,2)(3,6)(4,6)(5,6)a1:00a2:01a3:10a4:110a5:1110a6:1111Shannon-Fano-Elias编码12x

mF(x)F(x)1.0F(x-1)F(x-1)F(x-2)S-F-E编码的效率000111140.11110.93751.00.1254001110140.11010.81250.8750.125311020.100.50.750.520100130.0010.1250.250.251Huffman码码字的二进表示x算术编码熵编码的效率熵编码的概率排序序贯编码基本思想：S-F-E编码的直接推广（从单个符号到n长序列）关键之处：累积概率和的快速有效的迭代算法算术编码的基本算法（I）算术编码的基本算法（II）T3xnT2T101通用信源编码适用于具有任何统计特性的信源的有效编码方法Shannon编码在不能准确获得信源分布时的性能恶化Z-L编码序列的相异分解1011010100010…{(000,1),(000,0),(011,1),(010,1),(100,0),(010,0),(001,0)…}平稳信源的编码马尔科夫源的编码马尔科夫源的编码示例（I）ACDB1/0.11/0.50/0.51/0.51/0.90/0.90/0.50/0.1马尔科夫源的编码示例（II）对上述马尔科夫源输出的单符号序列进行二元编码，则：任何状态下均至少需要1比特来标记该输出符号，因此平均编码码长。马尔科夫源的编码示例（III）对上述马尔科夫源输出的二符号序列进行二元编码，则：ACDB01/0.0901/0.0510/0.0900/0.8100/0.4511/0.2510/0.2501/0.2511/0.8100/0.2510/0.0500/0.0511/0.0510/0.0511/0.4501/0.05马尔科夫源的编码示例（IV）消息ABCD000(0.81)0(0.45)10(0.25)111(0.05)0110(0.09)111(0.05)110(0.25)110(0.05)10110(0.05)110(0.25)111(0.05)10(0.09)11111(0.05)10(0.25)0(0.45)0(0.81)平均码长1.291.851.851.29授课小结Shannon编码Fano编码S-F-E编码算术编码通用信源编码平稳源编码马尔科夫信源编码作业复习授课内容预习第四章独立完成习题（下礼拜一交作业）3.143.153.16第四章信道、信道容量及

信道编码定理引言通信的数学理论：功率与带宽等通信资源的效用极限随机编码、联合（典型列）译码、注水法则、特征波束赋型等重要思想方法具体通信体制（OFDM/MIMO）的理论基础信道及其分类物理信道：噪声信道、干扰信道、衰落信道、存储信道…按输入/输出信号在幅度和时间上取值的连续性：幅度离散，时间离散信道；幅度连续，时间离散信道；幅度连续，时间连续信道；幅度离散，时间连续信道。按输入/输出之间的记忆性有记忆信道无记忆信道按其输入/输出信号的关系的确定性：确定信道随机信道信道的抽象模型信道输入量X（随机过程）输出量Y（随机过程）输入/输出统计关系离散无记忆信道平稳信道信道编码W信道{P(yn/xn)}xn信道编码ynW^记为：信道（互信息）容量平均每次利用信道，在输入和输出符号之间所能相互提供的互信息的最大值的极限离散无记忆信道（DMC）容量（I）对于离散无记忆信道（DMC）其中等号在输入为独立随机序列时达到。[证明]

等号在输出独立也即输入独立时达到。离散无记忆信道（DMC）容量（II）因此，对DMC从而DMC容量的例子——无噪信道XYx1x2xMx3y1y2y3yM比特DMC容量的例子——无损信道比特XYx1x2xMB1B2BMDMC容量的例子——确定信道比特Yx1,1x1,2x1,n1x2,1x2,2x2,n2y1y2Xxm,1xm,2ymxm,nmDMC容量的例子——无用信道0101p1-pp1-pXYDMC容量的例子——二进制对称信道（BSC）XY01011-p1-ppp当输入取等概分布时，输出Y也为等概分布，所以等号可以成立，即C=1-H(p).DMC容量的例子——二进制除删信道（BEC）XY当输入为等概分布时，等号成立.01011-p1-p

ppq1-q

BSC与BEC的容量比较和启示pCBSC(p)CBEC(p)1C10.50授课小结信道模型离散无记忆信道容量典型信道容量的计算作业复习授课内容预习4.2.4，4.3独立完成习题（每章交一次）4.1（a）,（d）4.3离散无记忆信道的容量定理（I）s.t.:OP:离散无记忆信道的容量定理（II）离散无记忆信道的容量定理（III）证明：离散无记忆信道的容量定理（IV）CiCjji0K-1对称离散无记忆信道（I）若P中每一行都是第一行的一个置换，则该信道关于输入对称若P中每一列都是第一列的一个置换，则该信道关于输出对称对称离散无记忆信道（II）若一个信道既关于输入对称，又关于输出对称，即P中每一行都是第一行的一个置换，每一列都是第一列的一个置换，则该信道是对称的对一个信道的转移概率矩阵P按列划分，得到若干子信道，若划分出的所有子信道均是对称的，则称该信道是准对称的0120.80.10.10.8010.10.1准对称离散无记忆信道的容量定理达到准对称离散无记忆信道容量的输入分布为均匀分布。证：故满足KKT条件。具有不同对称性的信道的容量

若信道关于输入对称，则：若信道同时也关于输出对称（即信道对称），则：若信道只关于输入对称，则：K元对称信道的容量012K–1012K–1二进制除删信道（BEC）0E11–p–q01qq1–p–qqqQ0=Q1=0.5模K加法信道+modKYXZY=X+ZmodKp(z)为任意分布

所以由概率转移矩阵可知是对称信道转移概率矩阵可逆的信道的容量计算（I）令则即亦即再由得若P可逆则可解出唯一的

.进一步可得转移概率矩阵可逆的信道的容量计算（II）进一步，再由求出{Qk}。讨论：若存在某个Qk<0，则原假设前提不满足，必须尝试令其中某个符号不发送（不一定是符号k），再用上述过程重新计算。例子p1-p10101XY信道的组合{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2平行信道（积信道）开关信道（和信道）级联信道平行信道（积信道）{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2等号在各子信道分别独立用最佳分布发送时成立。开关信道（和信道）{p1(j/k)}X1Y1{p2(j’/k’)}X2Y2PAPBXY级联信道{p1(j/k)}X{p2(j’/k’)}YZ授课小结离散无记忆信道容量定理对称和准对称信道准对称信道容量定理转移概率矩阵可逆的信道的容量计算信道的组合作业复习授课内容预习4.4节独立完成习题（每章交一次）4.24.4（选作）4.9离散无记忆信道的编码信道编码Xn(.)信道{p(y|x)}信道译码g(.)WxnynW^？离散无记忆信道的编码可能接收到2nH(Y|X)个典型序列

Y

nxMnx2nx1n

X

n12…M

M离散无记忆信道编码的基本定义（I）离散无记忆信道编码的基本定义（II）发送第i个消息所发生的错误概率（M，n）码的最大错误概率定义为（M，n）码的平均错误概率定义为联合典型列联合典型列的性质（I）联合典型列的性质（II）联合典型列的性质（III）

Y

nxn

X

n可能接收到2nH(Y|X)个典型序列随机选择yn,约有2-nI(X;Y)的概率与xn构成联合典型离散无记忆信道编码定理离散无记忆信道编码定理的证明思路渐近无差错准则所谓可靠通信是指随着码长增大，错误概率可以任意小，但并非为零。信道上不是仅传输一个符号，而是传输一串很长符号序列。由于多次使用信道，从而可以利用大数定律获得随机编码的统计性能。随机编码:计算在一类随机选择的码书上的平均错误概率。因此至少存在一个码书（即一个编码），它的错误概率和在码书集合上计算的平均错误概率一样好。联合（典型列）译码采用联合典型的准则进行译码，并且这样的译码准则是统计最优的离散无记忆信道编码定理的证明（I）离散无记忆信道编码定理的证明（II）使用所有码书发送消息w所引起的平均差错概率离散无记忆信道编码定理的证明（III）离散无记忆信道编码定理的证明（IV）离散无记忆信道编码定理的证明（V）离散无记忆信道编码逆定理信源信道分离编码与联合编码信源、信道分离编码信源、信道联合编码信源信道联合编码定理的证明（I）证明：信源信道联合编码定理的证明（II）证明：信源信道分离编码与联合编码只要H<C,总可以找到可行的信源信道联合编码；也可以分别构造最优的信源编码和信道编码，使信息传输可达；信源信道联合编码不能使得可行速率极限增加，但可以简化编码授课小结离散无记忆信道编码的基本概念编码定理及其证明思路离散无记忆信道编码逆定理信源信道分离编码与联合编码作业复习授课内容预习4.5节独立完成习题（每章交一次）4.12时间离散的加性高斯信道+YiXi时间离散的加性高斯信道的幅度离散化+YiXi>0<

Vi加性高斯信道的容量当输入X为高斯分布时等号成立。高斯信道编码定理高斯信道编码定理之逆高斯平行信道+Y2X2+Y1X1Z1+YkXkZ2Zk

，

高斯平行信道注水法则N1N2N3N4N5N6P1P2P4P5带限（模拟）高斯信道的容量连续信号的离散化模拟高斯信道的离散化等效平行信道+YnXnZn+Y2X2Z2+Y1X1Z1......模拟高斯信道的容量Shannon带限信道容量定理的重要启示授课小结加性高斯信道容量加性高斯信道的编码定理及其证明示意平行高斯信道的容量（注水法则）带限（模拟）高斯信道的容量及其重要意义作业复习授课内容预习第五章独立完成习题（每章交一次，下礼拜一交）4.13（选做）4.14第五章率失真信源编码引言信源的无损表达：R>=H(U)信源的有损表达：R<

H(U)实数的整数化表示有限精度量化/有限电平量化/矢量量化语音图像压缩抽样统计示例：最小化量化误差的矢量量化12MLloyd算法Voronoi区域率失真编码的定义12M

失真度量（函数）失真度量（函数）的重要例子失真的规范化（I）失真的规范化（II）失真的规范化（III）：例子xxabc

275

438^xxabc

053

105^零速率编码可达到的最小平均失真率失真编码的定义可达率失真对率失真区域率失真函数R(D)与失真率函数D(R)率失真编码定理简单信源的率失真函数——

Hamming失真度量下的贝努利信源（I）简单信源的率失真函数——

Hamming失真度量下的贝努利信源（II）随机差错关于恢复点对称简单信源的率失真函数——

Hamming失真度量下的贝努利信源（III）0101简单信源的率失真函数——

Hamming失真度量下的贝努利信源（IV）00.51p=0.5简单信源的率失真函数——

平方误差失真度量下的高斯信源（I）简单信源的率失真函数——

平方误差失真度量下的高斯信源（II）简单信源的率失真函数——

平方误差失真度量下的高斯信源（III）+简单信源的率失真函数——

平方误差失真度量下的高斯信源（IV）012简单信源的率失真函数——

平方误差失真度量下的高斯矢量信源（I）简单信源的率失真函数——

平方误差失真度量下的高斯矢量信源（II）简单信源的率失真函数——

平方误差失真度量下的高斯矢量信源（III）简单信源的率失真函数——

平方误差失真度量下的高斯矢量信源（IV）逆注水法则授课小结率失真编码的应用背景率失真编码的定义失真度量及其基本属性率失真区域率失真函数与率失真编码定理简单信源的率失真函数作业复习授课内容预习率失真函数的性质5.3节作业（每章交一次）率失真函数的性质R(D)的支撑集(Dmin,Dmax)12435R(D)的支撑集(Dmin,Dmax)贝努利信源R(D)函数的支撑集(Dmin,Dmax)高斯信源R(D)函数的支撑集(Dmin,Dmax)R(D)函数的下凸性证明：R(D)函数的单调递减性R(D)函数的单调递减性0DmaxH(X)离散信源0Dmax连续信源利用信源的对称性计算率失真函数利用信源的对称性计算率失真函数源的置换对称性失真度量矩阵的置换对称性利用信源的对称性计算率失真函数利用信源的对称性计算率失真函数例子信道编码与限失真信源编码的对偶授课小结率失真函数的性质利用信源的对称性计算率失真函数信道编码与限失真信源编码的对偶作业复习授课内容作业（本章作业不交）5.25.35.8信息论与编码第二部分基本纠错编码（第七章‐第九章）介绍信道编码的基本概念与基本方式，包括分组线性码基础、循环码与卷积码。线性分组纠错码（4学时）循环码（7学时）卷积码（6学时）内容提要与课时分配：第7章线性分组纠错编码

1、现代数字通信的两个基本理论基础：信息论和纠错编码；2、通信中信源编码，信道编码和数据转换编码常常同时使用；

本章介绍信道编码的基本的概念、也介绍最为常用的纠错编码，即分组循环码和卷积编码。

信源编码信道编码数据转换编码数据转换译码信道译码信源译码信道§7.1分组纠错编码的基本概念

7.1.1用于纠错和检错的信道编码

分组信道编码器的输入是一列长度为k的字符序列，其中字符是从信源字符表M中取值，信道编码器把输入消息序列映射成由n个信道字符组成的码字，n－码字长度，k－信息位长度，r=n–k－冗余位长度或称校验位长度，

码率分组编码器7.1.2二元对称信道的差错概率和差错分布

T表示码字中符号错误数目:

1-p1-ppp0011信道容量

7.1.3检错和纠错

检错是指当码字在信道上传输发生错误时，译码器能发现传输有误；纠错则是指译码器能自动纠正这个错误的能力。

[例7.1.3]3次重复编码，（n=3,k=1,r=2

）

“0”→“000”，“1”→“111”检测两位错误纠正一位错误[例7.1.2]r=3的重复码，即把 “0”→“0000” “1”→“1111”

纠正一位检测两位7.1.4自动重发请求（ARQ）编码

在半双工或双工情况下，收端发现有误时，可以通过反向信道去请求对方重发一次，直到正确接收到为止。这种通过检测错误，发现错误而且自动请求重发的通信方式称为ARQ方式。

1、等待式ARQ

码字出错概率为p，要成功传送码字，发方平均要发码字次数为：

2、退N

步ARQ

3、选择性重发ARQ

7.1.5最大似然译码和最小Hamming距离译码

发送码字：接收序列：错误矢量：

二元布尔运算中，减法等同于加法二元对称信道：

信道编码器信道译码器e

r

最大后验概率译码：最大似然译码准则：最大后验概率译码＝最大似然译码先验等概对于差错概率为p的二元对称信道来说

两个序列和的Hamming距离为d

指这两个序列有d位不同。7.1.6最小Hamming距离与检错、纠错能力的关系

把二个长度为n

的序列和之间的Hamming距离定义为和之间对应分量取不同值的位数。

定义9.1.1

长度为n的分组码C的最小Hamming距离d为分组码的三个最重要参数:

码字长度n，信息位数目k，最小Hamming距离d；对于一个（n,k）分组码来说，最小Hamming距离d与纠错、检错能力有如下关系：

定理7.1.1

任何一个（n,k）分组码，若要在任何码字内a.能检测e个随机错误，则要求最小Hamming距离d≥e+1。b.能纠正t个随机错误，则要求d≥2t+1。c.能纠正t个随机错误，同时检测出e(≥t)个错误，则要求d≥t+e+1。[证明]

§7.2线性分组纠错编码7.2.1线性分组编码的生成矩阵和校验矩阵线性分组码的基本特征是它具有“线性”的结构，即两个码字的线性组合仍是码字，对于二元码，即两个码字之和仍为码字。可以利用数学工具“线性空间”来研究线性分组码，使得编码器和译码器的实现更为简单。

定义7.2.1

一个速率为的线性分组码（n,k），把k

比特的消息矢量线性地映射成n比特的码字其中线性映射：全体码字集合称为码字空间，它是n维空间中的一个k维子空间。……

k个线性独立的二元n维矢量所以消息矢量生成矩阵[例9.2.1]

G生成的（6,3）线性码

行变换列交换系统生成矩阵系统生成矩阵生成系统线性码：r=n-k

校验位k

信息位系统线性码的校验矩阵：[例7.2.2]

例7.2.1中的（6.3）线性码的校验矩阵为

7.2.2对偶码和内积：u和v正交：n维空间中与一个k维子空间C正交的所有矢量的全体构成一个n-k维子空间，它称为C

的对偶空间，或称C

的正交补，用C⊥来表示。

定义7.2.2

生成矩阵为G，校验矩阵为H的（n,k）线性分组码C的对偶码C⊥是一个生成矩阵为H，校验矩阵为G的（n,n–k）线性分组码。

7.2.3线性分组码的最小Hamming距离和最小Hamming重量

定义7.2.3

一个n维矢量的Hamming重量定义为该矢量中非零分量的个数，对于二元矢量也就是矢量中“1”分量的个数。因为所以线性分组码的最小Hamming距离等于该码中非零码字的最小重量。

[例7.2.5]

由例9.2.3中生成矩阵所生成的线性分组码总共有8个码字（110100），（101010），（011001），（000000），（011110），（110011），（101101），（000111）

设若码字重量为w，则相应w列的和为零。如果一个线性分组码的最小Hamming距离为d，也就是说该码的最小Hamming重量为d，则它的校验矩阵H中任意d–1个列矢量是线性独立的。

§7.3线性分组码的纠错能力

线性码的纠错能力是由给定n,

k条件下，最小距离d的上，下界限来表征的。下面3个定理给出关于最小距离

d的上限。定理7.3.1

（Singleton限）任何线性（n,k）码的最小Hamming距离d满足

定理7.3.2

（Hamming限）长度为n，能纠正t个错误的二元分组码所含有码字数M必须满足定理7.3.3

（Plotkin限）长度为n，码字数为M的分组码，它的最小Hamming距离d必须满足定理7.3.4

（Varsharmov-Gilbert下限）可以构成一个最小距离为d的（n,k）线性分组码，其中参数n,k,d满足

d/2n§7.4

线性分组码的译码

发送的二元码字矢量为，从信道接收到的二元矢量为，错误矢量为

最大似然译码法则要求把译成与之距离最近的码字。

完全译码器把接收到的二元矢量译成与它最近码字；限定距离t译码器，选与最近的码字，当时，则译码器就译成；当时，译码器声称纠错失败。7.4.1标准阵列译码法

陪集首项：n维矢量中除了前面行矢量外最轻重量者二元（n,k）线性码C，若是任意一个非码字n维矢量，则称集合为C的一个陪集，其中称为陪集首项。任意二个倍集或者不相交或者重合，所以标准阵列是线性码的完全陪集分解。

对于任何接收到的矢量，若它落在标准阵列中的第j行，则可能的错误形式是该行中的所有矢量，最大似然译码准则要求把与接收矢量最近的码字译为发送码字，所以相当于在第j行中寻找最轻重量的矢量作为错误形式，即把该行的首项作为错误形式。

对于限定矩离

t

译码来说，不需要构造出完整的标准阵列，只需要构造重量不大于t

的陪集首项所对应的陪集。若接收到的矢量没有出现在这个不完整阵列表中，则说明这时发生了不可纠正的错误。

[例7.4.1]

一个具有4个码字，能纠错一位的（6，2）线性码，

C

={(000000),(010101),(101010),(111111)}000000010101101010111111000001010100101011111110000010010111101000111101000100010001101110111011001000011101100010110111010000000101111010101111100000110101001010011111…………………………………………陪集首项重量不大于1的不完全阵列表如果一个线性码的标准阵列中的陪集首项正好是所有重量不大于t的二元矢量，该线性码称为完备码。

7.4.2伴随式译码

接收矢量所对应的伴随式是一个维矢量

1、与相应的伴随式为零矢量的充要条件是为一个码字；

2、若则3、二个矢量出现在C的同一陪集中的充要条件是他们具有相同的伴随式；所以伴随式与陪集一一对应。如果接收到矢量为，首先计算出它的伴随式，如果，则表示接收到的是码字，没有错。如果不为0，则根据查出对应的错误形式。

§7.5

译码错误概率计算

误码字率为重量为i的陪集首项数目；误比特率

§7.6

二元Hamming码

定义7.6.1

长度为n=2r–1（r≥2）的二元Hamming码是一个（n=2r–1,k=2r–1–r）线性分组码，它的最小Hamming距离为3，能纠正全部一位错误。它的校验矩阵H由全部2r–1个长度为r的非零、相异的二元列矢量组成。[例7.6.1]

对于系统（7.4）Hamming码，它的校验矩阵

§7.7

从一个已知线性分组码来构造一个新的线性分组码

扩展的Hamming码(2r,2r–1–r,4)例（16,11,4）Hamming码Hr(2r–1,2r–1–r,3)例（15,11,3）Hr中偶重量码字构成的子码(2r–1,2r–2–r,4)例（15,10,4）除删，丢弃奇数重码字通过加入全“1”分量码字来增广延长缩短（cn–1=0）

在全校验位上凿孔

通过增加全校验位来扩展复习授课内容独立完成习题7.27.47.67.97.107.11作业：第7章线性分组纠错编码

第8章循环码

为了寻找好的纠错码，并寻找到有效的编/译码算法，通常要求码字集合除了线性以外还具有其他有用的构造，特别是代数和几何的结构。循环码是一类非常重要的线性码，它的码字具有循环特性，即循环码的码字经循环移位后仍然是一个码字。由于循环码具有更多的结构对称性，所以它的编/译码实现的复杂性比一般线性码更低，并有可能把编码的纠错性能与结构参数联系起来。要深入研究循环码的结构和编/译码方法，需要有一些代数方面的知识，特别是有限域的理论。§8.1

有限域代数的基本知识

8.1.1有限域的定义定义8.1.1

域F是一个由元素组成的集合，在这个集合上定义两种运算，加法“+”和乘法“·”。这两种运算满足交换律、结合律和分配律，即对于,存在唯一的加法零元素“0”，,存在唯一加法逆元，存在唯一单位元“1”，

存在唯一的乘法逆元，[例8.1.1]

最简单的有限域是二元域：其上的加法、乘法分别就是布尔加法和布尔乘法，即

对任何质数p，可以构成具有p个元素的伽罗华城在GF(p)上的加法和乘法分别为模p加法和模p乘法。[例8.1.2]

GF(5)是一个有5个元素的有限域，域上加法和乘法定义为：8.1.2GF(2m)的表示与构成多项式表示：考虑系数取自GF(2)上的（m

1）次多项式：m维二元矢量表示：GF(2m)元素间的加法和乘法运算：

（1101）

（1010）

（0111）采用普通多项式的加法和乘法，系数之间的运算是采用模2运算。为了使多项式乘法是封闭的，选是GF(2)上某个m次简约多项式的根。

在定义乘法时，遇到了困难：定理8.1.1

如果是GF(2)上次数等于m的不可约多项式，则对GF(2)上每个次数小于m的多项式，均存在唯一的逆元：8.1.3有限域的特征和元素的阶数令λ为使，成立的最小整数t，这个t称为该有限域的特征。GF(2)的特征为2。

有限域GF(q)上每个非零元，存在最小正整数k，使得，称k为的阶数。定理8.1.3

GF(q)上任何非零元素，必有定理8.1.4

令是GF(q)中非零元，的阶数为k，则q

1能被k除尽。GF(16)中非零元可能的阶数:1,3,5,15GF(256)中非零元可能的阶数:1,3,5,15,17,51,85,255定义8.1.2

如果GF(q)的一个元素

的阶数为q

1，则

被称为是本原元素。可证明每个有限域GF(q)至少有一个本原元素。因此至少存在一个本原元素

，它的逐次幂构成GF(q)的全部非零元，即[例8.1.3]

令是GF(2)上既约多项式的根，的逐次幂为：令是GF(2)上既约多项式的根，的逐次幂列为：定义8.1.3

GF(2)上一个m次多项，如果它的所有根均是GF(2m)中的本原元，则称为是m次本原多项式。容易验证例8.1.3中均是GF(24)的本原元，而是本原多项式。

1.可以证明本原多项式一定是简约的，但简约多项式不一定是本原的。2.GF(2m)中每个非零元的阶次是2m-1的因子，所以满足GF(2m)中所有元素是方程的根。8.1.4最小多项式设为GF(2m)中任一元素，m(x)是GF(2)上使的最低次多项式，则称为的最小多项式。最小多项式必定是既约的。在特征为p的有限域GF(pm)中，若是系数在GF(p)上的多项式的根，则也是的根。若GF(2m)中本原元是本原多项式的根，则均是的根，它们都是本原元素。如果的最小多项式是m次的，则的共轭系是，所以的m次最小多项式可写成：在特征为2的GF(2m)中，具有相同的最小多项式，这些元素构成共轭系。有限域的元素可以分解成若干个共轭系。§8.2

循环码定义与码字的多项式表示

循环移位定义8.2.1

一个（n,k）线性码C

，若它的每个码字矢量的循环移位也是该码的码字，则我们称C

为循环码。[例8.2.1]

一个由4个码字构成的，最小重量为3的（6，2）循环码

用多项式表示码字矢量因为定理8.2.1

循环码C中次数最低的非零码字多项式是唯一的。

[证明]令是码C

中一个次数最低的非零码字多项式。若不是唯一的，则必然存在另一个次数为r的码字多项式,由于C是线性的，所以这与假设是次数最低非零码字多项式相矛盾。

定理8.2.2

令是（n,k）循环码C中最低次数非零码多项式，则常数项。

[证明]若所以与假设矛盾。定理8.2.3

令是（n,k）循环码C中次数最低的非零码字多项式，则任何一个次数不大于n–1的二元多项式，当且仅当它是g(x)倍式时，才可成为一个码字多项式。[证明]

充分性：令是次数不大于n–1的二元多项式，且是g(x)的倍式，

上式中的被加项均是码字多项式，所以是也一个码字多项式；必要性：令是码C

中一个码字多项式，用g(x)除得到

b(x)次数小于g(x)次数；由充分性，a(x)g(x)

是一个码字多项式，故b(x)是次数小于r的码字多相式，于是导致矛盾。总结上面3条定理得：定理8.2.4

在一个二元（n,k）循环码中，存在唯一的次数为n–k的码字多项式，使得每个码字多项式都是的倍式，反之每个次数不大于n–1而且为倍式的多项式均对应于一个码字多项式。

所有次数不大于n–1，而且是g(x)倍式的多项式是由一切形如多项式与g(x)相乘的结果，总共有2n–r个。故2n–r应该等于2k

，即。称g(x)为这个（n,k）循环码的生成多项式，u(x)为消息多项式。

[例8.2.2]由生成的（6.2）循环码的码字

生成多项式必须满足一些条件：

定理8.2.5

（n,k）循环码的生成多项式g(x)是xn

+1的因子。[证明]

b(x)是g(x)连续向右移位k次后所得多项式，故b(x)是一个码字多项式。即故于是g(x)是xn+1的因式。

定理8.2.6

若g(x)是n–k次多项式，而且是xn+1的因式，则g(x)生成一个（n,k）循环码。

[证明]

令g(x)是xn+1的一个次数为n–k的因式，则是一个次数小于或等于（n–1）的多项式，且是g(x)的倍式。总共有2k个这样多项式。这些多项式组成一个（n,k）线性分组码。

下面证明这个线性分组码是循环的：

若v(x)是该线性码的一个码字多项式，即是g(x)的一个倍式，则所以v(1)(x)也是g(x)的倍式。从而v(1)(x)也是的线性组合，所以v(1)(x)也是一个码字多项式。

[例8.2.3]

多项式可分解成：由生成的（7,4）循环码

§8.3系统循环码的编码及实现

8.3.1系统循环码的编码

在（n,k）系统循环码中，k位消息位集中在码字矢量的右侧（最高位）。

构成系统循环码的步骤如下：1、用乘以消息多项式；2、用生成多项式除，得到余式（校验位多项式）；3、构成码字多项式；[例8.3.1]

考虑由生成的（7.4）循环码，消息多项式是，求相应的系统码字多项式。

[解]

1、2、3、8.3.2多项式运算的电路实现

一、多项式相加

c(x)+b(x)a(x)多项式，的系数依次从高到低位输入到模2加法器，和式的系数从高到低位依次输出。

二、多项式相乘

DDDDbr–1+brbr–2+b2+b1+b0+a(x)a0,a1,…,akc(x)c0,c1,…,ck+rb1+b0b2+br–2+br–1+br+a(x)a0,a1,…,akc(x)c0,c1,…,ck+rDDDD多项式乘法的另一种实现电路

[例8.3.2]

DD+a(x)1011c(x)100111DD+a(x)1011c(x)100111三、多项式除法电路

被除式除式商式余式–g1+–g0–g2+–gr3+–gr–2++d(x)d0,…,dnDDDD+DD–gr–1gr–1在n次移位后，商多项式出现在输出端，寄存器中保存的是余式。[例8.3.3]

++DDD+D+DDd(x)四、乘一个多项式后，再除一个多项式的电路–g1+–g0–g2+–gr–3+–gr–2++a(x)DDDD+D–gr–1gr–1+Dh1h0h2hr–3hr–2hr–1hr乘以多项式，再除以多项式的电路

输入++DDD+D+D+D输出乘以多项式，再除以的电路

DDDD++DDD+D+D+D+输入输出8.3.3循环码编码的电路实现