信息论与编码讲义第七讲

1、2022-4-101第三章：第三章：信源编码（一）离散信源无失真编码3.1 信源及其分类信源及其分类3.2 离散无记忆（简单）信源的等长编离散无记忆（简单）信源的等长编码码3.3 离散无记忆（简单）信源的不等长离散无记忆（简单）信源的不等长编码编码3.4 最佳不等长编码最佳不等长编码3.5 算术编码和算术编码和LZ编码编码2022-4-1023.1 信源及其分类信源及其分类信源的概念信源的概念 （直观地理解，信源就是信息的来源。但是这里必须要注意两点）：n在一个固定的时刻，信源发出的是一个随机变量。在一个固定的时刻，信源发出的是一个随机变量。n随着时间的延续，信源发出的是一个随机过程。随着时间

2、的延续，信源发出的是一个随机过程。（因此，一般的信源种类太多，其统计性质太复杂。怎样做工程实用的简化？） 2022-4-1033.1 信源及其分类信源及其分类离散信源离散信源 信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序列U-2U-1U0U1U2，其中nUk为第k个时间段发出的随机变量；n每个Uk都是一个离散型的随机变量。离散无记忆信源离散无记忆信源 离散无记忆信源是这样的离散信源：随机变量、U-2、U-1、U0、U1、U2、相互独立。离散无记忆简单信源离散无记忆简单信源 离散无记忆简单信源是这样的离散无记忆信源：随机变量、U-2、U-1、U0、U1、U2、

3、具有相同的概率分布。 2022-4-1043.1 信源及其分类信源及其分类（总结：离散无记忆简单信源就是时间离散、事件离散、各随机变量独立同分布的信源。课程学习所面对的信源将主要是离散无记忆简单信源）一般的信源一般的信源 连续信源：有时间连续的信源，也有事件连续的信源；有记忆信源：信源在不同时刻发出的随机变量相互依赖；有限记忆信源：在有限时间差内的信源随机变量相互依赖；非简单信源：信源在不同时刻发出的随机变量具有不同的概率分布。马尔可夫信源：信源随机过程是马尔可夫过程。 2022-4-1053.2 离散无记忆（简单）信离散无记忆（简单）信源的等长编码源的等长编码（顺序地叙述以下的概念）（1）设

4、有一个离散无记忆简单信源，信源发出的随机变量序列为：U-2U-1U0U1U2。设信源随机变量U1的事件有K个：a1, a2, , aK，则L维信源随机向量(U1U2UL)的事件有KL个：(u1u2uL)|其中每个分量ul跑遍a1, a2, , aK。（2）设有一个含D个字母的字母表b1, b2, , bD。需要用字母串来表示(U1U2UL)的事件，每一个事件都要用一个字母串来表示。这种表示方法称为这种表示方法称为D元编码元编码；每一个事件所对应的字母串称为一个每一个事件所对应的字母串称为一个码字码字。 2022-4-1063.2 离散无记忆（简单）信离散无记忆（简单）信源的等长编码源的等长编码

5、例例：离散无记忆简单信源发出的随机变量序列为：U-2U-1U0U1U2。其中U1的事件有3个：晴, 云, 阴。(U1U2)有9个事件（晴晴），（晴云），（晴阴），（云晴），（云云），（云阴），（阴晴），（阴云）， （阴阴）。用字母表0, 1对(U1U2)的事件进行2元编码如下：（晴晴）0000，（晴云）0001，（晴阴）0011，（云晴）0100，（云云）0101，（云阴）0111，（阴晴）1100，（阴云）1101，（阴阴）1111。2022-4-1073.2 离散无记忆（简单）信离散无记忆（简单）信源的等长编码源的等长编码（3）如果限定码字的长度为N（即每个码字都是一个N维向量），则称此编

6、码为等长编码等长编码，能够选择的不同码字的个数为DN。（4）如果限定码字的长度为N（即每个码字都是一个N维的向量），则称此编码为不等长编码不等长编码，能够选择的不同码字的个数为D1+D2+DN=D(DN-1)/(D-1)。 （注意：在不等长编码中，并不能同时使用D(DN-1)/(D-1)个不同的码字。一个长度为2的字母串究竟是两个长度为1的码字相连，还是一个长度为2的码字？无法识别。在等长编码中不存在这样的识别问题 ）2022-4-1083.2 离散无记忆（简单）信离散无记忆（简单）信源的等长编码源的等长编码（本节以下将专门讨论等长编码）（5）编码速率编码速率 R=NlogD/L。（6）无错编

7、码无错编码 (U1U2UL)的不同事件用不同的码字来表示。能够实现无错编码的充要条件是DNKL。（即编码速率R=NlogD/LlogK）（7）有错编码有错编码 (U1U2UL)的有些不同事件用相同的码字来表示。（8）有错编码的译码方法与有错编码的译码方法与 “译码错误译码错误”概率概率 当使用有错编码时，必须给出译码方法（一个码字究竟翻译成哪个事件）。“译码错误”的概率定义为pe= P(U1U2UL)=(u1u2uL)| (u1u2uL)的码字在译码时并不译为(u1u2uL)。2022-4-1093.2 离散无记忆（简单）信离散无记忆（简单）信源的等长编码源的等长编码（关于编码速率的说明：p编

8、码速率本来是编码设备的性能指标。这就是说，首先有了编码设备的编码速率R0，然后选择N和L，使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0 ：R=NlogD/LR0。p当编码速率R比较高时，可以选择比较大的N，因此可供选择的码字比较多，因此更容易设计出能够快速识别的码，降低译码的难度。p当编码速率R比较低时，意味着使用低成本的编码设备。此时只能选择不大的N，因此更需要编码的技巧。 ） 2022-4-10103.2 离散无记忆（简单）信离散无记忆（简单）信源的等长编码源的等长编码（9）在无错编码的前提下，编码的最低代价在无错编码的前提下，编码的最低代价n当RlogK时，能够实现无错

9、编码。n当RH(U1)时，无论怎样编码都是有错编码。这是因为RH(U1)logK。（如果H(U1)=logK，则以上两种情形已经概括了全部情形。但如果H(U1)RH(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小。这就是所谓“渐进无错编码”。2022-4-10113.2 离散无记忆（简单）信离散无记忆（简单）信源的等长编码源的等长编码（10）渐进无错编码渐进无错编码 （简单地说就是：当RH(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小。严格地说就是：）设给定了编码设备的编码速率R0，R0H(U1)。则对任意的0，总存在一个L0，使得对任意

10、的LL0，都有对(U1U2UL)的等长编码和对应的译码方法，满足实际的编码速率R=NlogD/LR0，译码错误的概率pe。（11）渐进无错编码的原理渐进无错编码的原理 大数定律。随着L的增加，(U1U2UL)的所有事件中，某些事件所占的比例越来越小（0），其发生的概率却越来越大（1）。 2022-4-10123.2 离散无记忆（简单）信离散无记忆（简单）信源的等长编码源的等长编码（12）不能渐进无错的编码不能渐进无错的编码 （简单地说就是：当RH(U1)时，无论怎样编码和译码都不能使译码错误的概率pe任意小。严格地说就是： ）设给定了编码设备的编码速率R0，R00有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+LllLVLI11)(111UHEVLEILllL1121111DVLDVLVLDDILllLllL211LDV2022-4-10153.2 离散无记忆（简单）信离散无记忆（简单）信源的等长编码源的等长编码取L0使得则当LL0时总有因此当LL0时总有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+1-。 201LDV21LDV2022-4-10163.2 离散无记忆（简单）信离散无记忆（简单）信源