西安电子科技大学：《信息论与编码理论基础》课程PPT教学课件（信息论）第三章 信源编码（一）离散信源无失真编码

第三章信源编码（一) 离散信源无失真编码

第三章 信源编码（一） 离散信源无失真编码

·3.1信源及其分类 ·3.2离散无记忆信源的等长编码 ·3.3离散无记忆信源的不等长编码 。3.4最佳不等长编码

⚫ 3.1信源及其分类 ⚫ 3.2离散无记忆信源的等长编码 ⚫ 3.3离散无记忆信源的不等长编码 ⚫ 3.4最佳不等长编码

3.1信源及其分类

3.1 信源及其分类

信源及其分类 ● 离散信源 ·连续信源 ●无记忆信源 ●有记忆信源 ·简单信源一独立同分布 ·平稳信源，各态历经源 ●M阶记忆源 ●时间离散连续源 ●随机波形源

信源及其分类 ⚫ 离散信源 ⚫ 连续信源 ⚫ 无记忆信源 ⚫ 有记忆信源 ⚫ 简单信源－独立同分布 ⚫ 平稳信源，各态历经源 ⚫ M阶记忆源 ⚫ 时间离散连续源 ⚫ 随机波形源

3.2离散无记忆源的等长 编码

3.2 离散无记忆源的等长 编码

离散无记忆源 字母表A={a1…,aK,概率分别为p1,…pk,长为L 的源输出序列4L={41,…,4z}，共有K种序列 ●1 码符号字母表B={b1,…,bD},以码符号表示源输 出序列，D元码 等长D元码，能够选择的不同码字的个数为D 不等长D元码的个数，能够选择的不同码字的 个数为D1+D2+..+D=D(Dw1)/(D-1)

离散无记忆源 ⚫ 字母表A={a1 ,…,aK},概率分别为p1 ,…,pK,长为L 的源输出序列uL={u1 ,…,uL}，共有KL种序列 ⚫ 码符号字母表B={b1 ,…,bD},以码符号表示源输 出序列，D元码 ⚫ 等长D元码，能够选择的不同码字的个数为DN ， 不等长D元码的个数,能够选择的不同码字的 个数为D1+D2+…+DN=D(DN-1)/(D-1)

离散无记忆源的等长编码 。 编码速率 R=MogD/L。 ● 无错编码(UU,U)的不同事件用不同的码字来表 示。，能够实现无错编码的充要条件是DKL。(即编 码速率R=MogD/L≥logK) ·有错编码(U,U,..U)的有些不同事件用相同的码字 来表示。 ·有错编码的译码方法与“译码错误”概率当使用有 错编码时，必须给出译码方法，（一个码字究竟翻译成 哪个事件)。 译码错误”的概率定义为 peP{(UU2.U)(424z)(u1w2…uz)的码字在译码时 并不译为(u12.z)}

离散无记忆源的等长编码 ⚫ 编码速率 R=NlogD/L。 ⚫ 无错编码 (U1U2…UL )的不同事件用不同的码字来表 示。能够实现无错编码的充要条件是DN≥KL。（即编 码速率R=NlogD/L≥logK） ⚫ 有错编码 (U1U2…UL )的有些不同事件用相同的码字 来表示。 ⚫ 有错编码的译码方法与 “译码错误”概率 当使用有 错编码时，必须给出译码方法（一个码字究竟翻译成 哪个事件）。“译码错误”的概率定义为 pe = P{(U1U2…UL )=(u1u2…uL )| (u1u2…uL )的码字在译码时 并不译为(u1u2…uL )}

离散无记忆源的等长编码 关于编码速率的说明： 口纟 编码速率本来是编码设备的性能指标。这就是说，首 先有了编码设备的编码速率R,然后选择N和L,使得 实际的编码速率NogD/L不能超过编码设备的编码速率 Ro:R=MogD/L≤R。 口当编码速率R比较高时，可以选择比较大的N,因此可 供选择的码字比较多，因此更容易设计出能够快速识 别的码，降低译码的难度。 口当编码速率R比较低时，意味着使用低成本的编码设备 。此时只能选择不大的W,因此更需要编码的技巧

离散无记忆源的等长编码 关于编码速率的说明：  编码速率本来是编码设备的性能指标。这就是说，首 先有了编码设备的编码速率R0，然后选择N和L，使得 实际的编码速率NlogD/L不能超过编码设备的编码速率 R0 ：R=NlogD/L≤R0。  当编码速率R比较高时，可以选择比较大的N，因此可 供选择的码字比较多，因此更容易设计出能够快速识 别的码，降低译码的难度。  当编码速率R比较低时，意味着使用低成本的编码设备 。此时只能选择不大的N，因此更需要编码的技巧

离散无记忆源的等长编码 在无错编码的前提下，编码的最低代价 ● 当心logK时，能够实现无错编码。 ● 当RH(U)时，虽然无论怎样编码都是有错编 码，但可以适当地编码和译码使译码错误的概率。 任意小。这就是所谓“渐进无错编码

离散无记忆源的等长编码 在无错编码的前提下，编码的最低代价 ⚫ 当R≥logK时，能够实现无错编码。 ⚫ 当RR>H(U1 )时，虽然无论怎样编码都是有错编 码，但可以适当地编码和译码使译码错误的概率pe 任意小。这就是所谓“渐进无错编码

离散无记忆源的等长编码 渐进无错编码（简单地说就是：当R>H(U)时，可以适当地编码 和译码使得译码错误的概率p任意小。严格地说就是：) 设给定了编码设备的编码速率R,Ro>H(U1)。则对任意的>0，总 存在一个Lo,使得对任意的L>Lo,都有对(U1U2.U)的等长编 码和对应的译码方法，满足 ①实际的编码速率R=NogD/L≤Ro, ②译码错误的概率pe<g。 (11)渐进无错编码的原理大数定律。随着L的增加， (U1U2.U)的所有事件中，某些事件所占的比例越来越小（→0 ),其发生的概率却越来越大（→1）

离散无记忆源的等长编码 渐进无错编码 （简单地说就是：当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）