信息论与编码讲义第七讲

信息论与编码讲义第七讲2023/6/161第一页，共十六页，编辑于2023年，星期六§3.1信源及其分类信源的概念

（直观地理解，信源就是信息的来源。但是这里必须要注意两点）：在一个固定的时刻，信源发出的是一个随机变量。随着时间的延续，信源发出的是一个随机过程。（因此，一般的信源种类太多，其统计性质太复杂。怎样做工程实用的简化？）2023/6/162第二页，共十六页，编辑于2023年，星期六§3.1信源及其分类离散信源信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序列…U-2U-1U0U1U2…，其中Uk为第k个时间段发出的随机变量；每个Uk都是一个离散型的随机变量。离散无记忆信源离散无记忆信源是这样的离散信源：随机变量…、U-2、U-1、U0、U1、U2、…相互独立。离散无记忆简单信源离散无记忆简单信源是这样的离散无记忆信源：随机变量…、U-2、U-1、U0、U1、U2、…具有相同的概率分布。2023/6/163第三页，共十六页，编辑于2023年，星期六§3.1信源及其分类（总结：离散无记忆简单信源就是时间离散、事件离散、各随机变量独立同分布的信源。课程学习所面对的信源将主要是离散无记忆简单信源）一般的信源

连续信源：有时间连续的信源，也有事件连续的信源；有记忆信源：信源在不同时刻发出的随机变量相互依赖；有限记忆信源：在有限时间差内的信源随机变量相互依赖；非简单信源：信源在不同时刻发出的随机变量具有不同的概率分布。马尔可夫信源：信源随机过程是马尔可夫过程。2023/6/164第四页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码（顺序地叙述以下的概念）（1）设有一个离散无记忆简单信源，信源发出的随机变量序列为：…U-2U-1U0U1U2…。设信源随机变量U1的事件有K个：{a1,a2,…,aK}，则L维信源随机向量(U1U2…UL)的事件有KL个：{(u1u2…uL)|其中每个分量ul跑遍{a1,a2,…,aK}}。（2）设有一个含D个字母的字母表{b1,b2,…,bD}。需要用字母串来表示(U1U2…UL)的事件，每一个事件都要用一个字母串来表示。这种表示方法称为D元编码；每一个事件所对应的字母串称为一个码字。

2023/6/165第五页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码例：离散无记忆简单信源发出的随机变量序列为：…U-2U-1U0U1U2…。其中U1的事件有3个：{晴,云,阴}。(U1U2)有9个事件{（晴晴），（晴云），（晴阴），（云晴），（云云），（云阴），（阴晴），（阴云），（阴阴）}。用字母表{0,1}对(U1U2)的事件进行2元编码如下：（晴晴）→0000，（晴云）→0001，（晴阴）→0011，（云晴）→0100，（云云）→0101，（云阴）→0111，（阴晴）→1100，（阴云）→1101，（阴阴）→1111。2023/6/166第六页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码（3）如果限定码字的长度为N（即每个码字都是一个N维向量），则称此编码为等长编码，能够选择的不同码字的个数为DN。（4）如果限定码字的长度为≤N（即每个码字都是一个≤N维的向量），则称此编码为不等长编码，能够选择的不同码字的个数为D1+D2+…+DN=D(DN-1)/(D-1)。（注意：在不等长编码中，并不能同时使用D(DN-1)/(D-1)个不同的码字。一个长度为2的字母串究竟是两个长度为1的码字相连，还是一个长度为2的码字？无法识别。在等长编码中不存在这样的识别问题）2023/6/167第七页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码（本节以下将专门讨论等长编码）（5）编码速率

R=NlogD/L。（6）无错编码

(U1U2…UL)的不同事件用不同的码字来表示。能够实现无错编码的充要条件是DN≥KL。（即编码速率R=NlogD/L≥logK）（7）有错编码

(U1U2…UL)的有些不同事件用相同的码字来表示。（8）有错编码的译码方法与“译码错误”概率当使用有错编码时，必须给出译码方法（一个码字究竟翻译成哪个事件）。“译码错误”的概率定义为pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的码字在译码时并不译为(u1u2…uL)}。2023/6/168第八页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码（关于编码速率的说明：编码速率本来是编码设备的性能指标。这就是说，首先有了编码设备的编码速率R0，然后选择N和L，使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0

：R=NlogD/L≤R0。当编码速率R比较高时，可以选择比较大的N，因此可供选择的码字比较多，因此更容易设计出能够快速识别的码，降低译码的难度。当编码速率R比较低时，意味着使用低成本的编码设备。此时只能选择不大的N，因此更需要编码的技巧。）2023/6/169第九页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码（9）在无错编码的前提下，编码的最低代价当R≥logK时，能够实现无错编码。当R<H(U1)时，无论怎样编码都是有错编码。这是因为R<H(U1)≤logK。（如果H(U1)=logK，则以上两种情形已经概括了全部情形。但如果H(U1)<logK，则还有一种情形）当logK>R>H(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小。这就是所谓“渐进无错编码”。2023/6/1610第十页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码（10）渐进无错编码（简单地说就是：当R>H(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小。严格地说就是：）设给定了编码设备的编码速率R0，R0>H(U1)。则对任意的ε>0，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的等长编码和对应的译码方法，满足①实际的编码速率R=NlogD/L≤R0，②译码错误的概率pe<ε。（11）渐进无错编码的原理大数定律。随着L的增加，(U1U2…UL)的所有事件中，某些事件所占的比例越来越小（→0），其发生的概率却越来越大（→1）。2023/6/1611第十一页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码（12）不能渐进无错的编码（简单地说就是：当R<H(U1)时，无论怎样编码和译码都不能使译码错误的概率pe任意小。严格地说就是：）设给定了编码设备的编码速率R0，R0<H(U1)。则无论怎样编码和译码都不能同时满足①实际的编码速率R≤R0，②译码错误的概率pe任意小。2023/6/1612第十二页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码设…U-2U-1U0U1U2…是离散无记忆（简单）信源的输出随机变量序列。设U1的概率分布为取Vl是Ul的如下函数：当Ul=ak时，Vl=loga(1/qk)。则①随机变量序列…V-2V-1V0V1V2…相互独立，具有相同的概率分布；②2023/6/1613第十三页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码取IL是(V1V2…VL)的如下函数：则①IL最终是(U1U2…UL)的函数；②③因此有切比雪夫不等式：对任意ε>0有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥2023/6/1614第十四页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码取L0使得则当L≥L0时总有因此当L≥L0时总有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥1-ε。2023/6/1615第十五页，共十六页，编辑于2023年，星期六§3.2离散无记忆（简单）信源的等长编码定义3.2.1(p46)定义TU(L,ε)={(u1u2…uL)|H(U1)-ε≤IL≤H