《信息论与编码理论基础(第3章).》由会员分享，可在线阅读，更多相关《信息论与编码理论基础(第3章).（137页珍藏版）》请在金锄头文库上搜索。
1、第三章：信源编码-离散信源无失真编码 3.1 信源及其分类 3.2 离散无记忆（简单）信源的等长编码 3.3 离散无记忆（简单）信源的不等长编码 3.4 最佳不等长编码 3.1 信源及其分类 信源的概念 直观地理解，信源就是信息的来源。但是这里必须要注意两点： n在一个固定的时刻，信源发出的是一个随机变量。 n随着时间的延续，信源发出一个又一个随机变量，称之为一 个随机过程。 因此，一般的信源种类太多，其统计性质太复杂。 怎样做工程实用的简化？ 离散信源 信源每隔一个定长时间段就发出一个随机变量；随着 时间的延续，信源发出的是随机变量序列 U-2U-1U0U1U2， 其中 (1) Uk为第k个
2、时间段发出的随机变量； (2) 每个Uk都是一个离散型的随机变量。 离散无记忆信源 离散无记忆信源是这样的离散信源： 随机变量、U-2、U-1、U0、U1、U2、相互独立。 离散无记忆简单信源 离散无记忆简单信源是这样的离散无记忆 信源：随机变量、U-2、U-1、U0、U1、U2、具有相同的概率 分布。 3.1 信源及其分类 总结： 离散无记忆简单信源 就是时间离散、事件离散、各随机变量独立同分布的信源。 本课程学习所面对的信源将主要是离散无记忆简单信源。 一般的信源 连续信源：有时间连续的信源，也有事件连续的信源； 有记忆信源：信源在不同时刻发出的随机变量相互依赖； 有限记忆信源：在有限时间
3、差内的信源随机变量相互依赖； 非简单信源：信源在不同时刻发出的随机变量具有不同的概率分布 。 马尔可夫信源：信源随机过程是马尔可夫过程。 以下将顺序地叙述下面的相关概念： 3.1 信源及其分类 3.2 离散无记忆（简单）信源的等长编码 （1）设有一个离散无记忆简单信源，信源发出的随机变量序 列为：U-2U-1U0U1U2。 设信源随机变量U1的事件有K个：a1, a2, , aK，则L 维信源随机向量(U1U2UL)的事件有KL个：(u1u2uL)|其 中每个分量ul跑遍a1, a2, , aK。 P(U1U2UL)=(u1u2uL) =P(U1=u1)P(U2=u2) P(UL=uL) =P
4、(U1=u1)P(U1=u2) P(U1=uL) =q(u1)q(u2) q(uL) 3.2 离散无记忆（简单）信源的等长编码 （2）设有一个含D个字母的字母表。对于(U1U2UL)的每一 个事件(u1u2uL)，都用一个字母串(c1c2)来表示。 这种表示方法称为D元编码； 每一个事件(u1u2uL)所对应的字母串(c1c2)称为一个码字。 例：离散无记忆简单信源发出的随机变量序列为：U-2U- 1U0U1U2。其中U1的事件有3个：晴, 云, 阴。 (U1U2)有9个事件 (晴晴), (晴云), (晴阴), (云晴), (云云), (云阴), (阴晴), (阴云), (阴阴) 。 用字母表
5、0, 1对(U1U2)的事件进行2元编码如下： （晴晴）0000，（晴云）0001，（晴阴）0011， （云晴）0100，（云云）0101，（云阴）0111， （阴晴）1100，（阴云）1101，（阴阴）1111。 3.2 离散无记忆（简单）信源的等长编码 （3）如果限定所有码字的长度都为N（即每个码字都是一个长度 为N的字母串，或称为N维向量），则称此编码为等长编码，能 够选择的不同码字的个数为DN。 （4）如果限定每个码字的长度都N（即每个码字都是一个长度N 的字母串），则称此编码为不等长编码，能够选择的不同码字 的个数为 D1+D2+DN=D(DN-1)/(D-1)。 （注意：在不等长编
6、码中，并不能同时使用D(DN-1)/(D-1)个不同 的码字。一个长度为2的字母串究竟是两个长度为1的码字相连 ，还是一个长度为2的码字？无法识别。而在等长编码中不存在 这样的识别问题 ） 3.2 离散无记忆（简单）信源的等长编码 （本节以下将专门讨论等长编码） （5）编码速率 R=NlogD/L。 （单位时间内码可以携带的信息量，反映了码的能力） 关于编码速率的说明： 实际的编码速率的计算公式为R=NlogD/L，似乎可以人为地任 意设置N和L，因而可以人为地任意设置编码速率。事实并非如 此，存在着编码设备的编码速率R0，它是编码设备的性能指标 。这就是说，选择N和L，必须使得实际的编码速率
7、NlogD/L不 能超过编码设备的编码速率R0 ：R=NlogD/LR0。 3.2 离散无记忆（简单）信源的等长编码 （6）无错编码 (U1U2UL)的不同事件用不同的码字来表示。能 够实现无错编码的充要条件是DNKL。 （即编码速率R=NlogD/LlogK） （7）有错编码 (U1U2UL)的有些不同事件用相同的码字来表示 。 （8）有错编码的译码方法与 “译码错误”概率 当使用有错编码时 ，必须给出译码方法（即：一个码字可能表示几个不同的事件 ，究竟翻译成哪个事件）。“译码错误”的概率定义为 pe= P(U1U2UL)=(u1u2uL) | (u1u2uL)的码字在译码时并不译为(u1u
8、2uL)。 3.2 离散无记忆（简单）信源的等长编码 （9）在无错编码的前提下，编码的最低代价 n当RlogK时，能够实现无错编码。 （DNKL） n当RH(U1)时，虽然无论怎样编码都是有错编码，但 可以适当地编码和译码使译码错误的概率pe任意小。这就 是所谓“渐进无错编码”。 3.2 离散无记忆（简单）信源的等长编码 （10）渐进无错编码 （简单地说就是：当RH(U1)时，可以适当 地编码和译码使得译码错误的概率pe任意小。严格地说就是： ） 设给定了编码设备的编码速率R0，R0H(U1)，则对任意的0 ，总存在一个L0，使得对任意的LL0，都有对(U1U2UL)的等 长编码和对应的译码方
9、法，满足 实际的编码速率R=NlogD/LR0， 译码错误的概率pe0，取L0使得 则当LL0时总有P(U1U2UL)TU(L, )1-。 3.2 离散无记忆（简单）信源的等长编码 （简记H(U)=H(U1)。设以下的对数都是以2为底的。） 系3.2.1(特定典型序列出现的概率，p58) 若一个特定的事件 (u1u2uL)TU(L, )，则 2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。 证明 设(u1u2uL)TU(L, )。 注意到此时 H(U)-ILH(U)+， 3.2 离散无记忆（简单）信源的等长编码 所以 3.2 离散无记忆（简单）信源的等长编码 系3
10、.2.2(典型序列的数量，p58) (1-)2L(H(U)-)|TU(L, )|2L(H(U)+)。 证明 一方面， 3.2 离散无记忆（简单）信源的等长编码 另一方面 ， 3.2 离散无记忆（简单）信源的等长编码 （如果采用2元编码，且对数都是以2为底的，则编码速率为 R=NlogD/L=N/L。） 补充引理 设给定一个R0H(U)。对每个正整数L，对应地取整数 N=R0L（R0L的下取整）。则 N/LR0， limL+N/L=R0。 进而，任取正数(R0 -H(U)/2，存在正整数L0，当LL0时 （1）N/LR0-(R0 -H(U)/2=H(U)+(R0-H(U)/2H(U)+。 （2）
11、P(U1U2UL)TU(L, )1-。 （由定理3.2.1） 3.2 离散无记忆（简单）信源的等长编码 定理3.2.2(无错编码正定理，p60) 给定编码设备的编码速率R0， R0H(U)。则对任意的0，总存在一个L0，使得对任意的LL0， 都有对(U1U2UL)的2元等长编码方法和对应的译码方法， 实际的编码速率R满足 R0RH(U)， “译码错误”的概率pe L0，取N=LR0，令R=N/L，即N=LR， 则由补充引理的(1)可得 RH(U)+ ， 从而，2N =2LR 2L(H(U)+) 再由系3.2.2， |TU(L, )|2L(H(U)+) 2LR=2N ， 3.2 离散无记忆（简单
12、）信源的等长编码 这就是说， 典型序列集TU(L, )中的事件的个数不超过长度为 N的2元码字的数量2N。 因此，做如下的编码：将TU(L, )中的事件用不同的N长2元码 字来表示，而将TU(L, )以外的事件用一个固定的N长2元码字来表 示，这个固定的N长2元码字已经用来表示了TU(L, )中的某个事件 。 3.2 离散无记忆（简单）信源的等长编码 对应的译码：所有的码字均译为它所表示的TU(L, )中的事件 。 结论：实际的编码速率R满足R0RH(U)； “译码错误”的概率pe=P(U1U2UL)不属于TU(L, ) =1-P(U1U2UL)TU(L, )H(U)； 给定一个任意小的正数0
13、； 要求：选择合适的L，N，对(U1U2UL)进行合适的2元N长编码， 使得 实际的编码速率R=N/L满足RR0； “译码错误”的概率penb。现在将事件a和b交换码字，其它事件的码字保持 不变。此时2元异字头码S 变成新的2元异字头码T。 3.4 最佳不等长编码 （1）码S 中事件a和b的码字对平均码长的贡献为qana+qbnb； （2）码T中事件a和b的码字对平均码长的贡献为qanb+qbna。 (qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)0。 这就是说，码S 的平均码长码T 的平均码长。因而码S 不是最 佳2元异字头码。 用反证法已经证明了补充引理2。 3
14、.4 最佳不等长编码 补充引理2 设信源随机变量U的最佳2元异字头码S ，则最长的码字 至少有两个。 证明 如果2元异字头码S 的最长的码字竟然只有一个。设这个码字 为c，是事件a的码字。现在将c的最后一位去掉，成为c，将c 仍然作为事件a的码字。其它事件的码字保持不变。此时2元异 字头码S 变成新的2元码T。注意到以下两点： （1）码T仍然是2元异字头码； （2）码S 的平均码长码T 的平均码长。 因而码S 不是最佳2元异字头码。用反证法已经证明了补充引理3。 3.4 最佳不等长编码 补充引理3 最佳2元异字头码S可以满足以下两条： （1）概率最小的两个事件码字最长，且长度相等； （2）它们
15、的码字仅仅最后一位不同。 证明 取概率最小的事件a。在剩下的事件中取概率最小的事件b 。根据补充引理1和补充引理2，事件a和事件b的码字最长， 且长度相等。这就是说，最佳2元异字头码S显然满足第（1） 条。 3.4 最佳不等长编码 关于第（2）条，分以下三种情形来讨论： 情形一 事件a和事件b的码字仅仅最后一位不同。 情形二 事件a和事件b的码字不是仅仅最后一位不同，但有第三 个事件c，其码字与事件a的码字仅仅最后一位不同。 情形三 事件a和事件b的码字不是仅仅最后一位不同，也没有第 三个事件c，其码字与事件a的码字仅仅最后一位不同。 3.4 最佳不等长编码 3.4 最佳不等长编码 补充引理4 信源随机变量的最佳2元异字头码，一定是该信源随 机变量的最佳2元不等长码。（换句话说，寻找最佳2元不等长 码，只要寻找最佳2元异字头码即可） 证明 设最佳2元异字头码的码字长度依次为 设最佳2元不等长码的码字长度依次为 首先有 ： 3.4 最佳不等长编码 取码字长度依次为 其次，对于任意满足Craft不等式 的码字长度依次为m1、m2、mK的2元不等长码 ， 总存在码字长度依次为m1、m2、mK的2元异字头码。 2元不等长码 ， 3.4 最佳不等长编码 则也存在具有相同码字长度 的2元异字头码 ， 而是最佳的2元异字头码的码长 故有 引理得证 。 3.4 最佳不等长编码 补充定
