●●● ●●●● ●●●●● ●●●● 离散无记忆源 ●●0●● ●●●● ●●●● 字母表A={a1,a:概率分别为p1…,p0k,长为L 的源输出序列1={u1,…,u},共有K种序列 ·码符号字母表B={b,,bD},以码符号表示源输 出序列,D元码 ●等长D元码,能够选择的不同码字的个数为DN 不等长D元码的个数能够选择的不同码字的 个数为D+D2+.+D=DD-1)(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)
●●● ●●●● ●●●●● ●●●● 离散无记忆源的等长编码 ●●0●● ●●●0 ●●●● 编码速率 R= Mlog D/L。 无错编码(UU2)的不同事件用不同的码字来表 示。能够实现无错编码的充要条件是D心>K。(即编 码速率R= Nlog D/logk) 有错编码(U1U2…U)的有些不同事件用相同的码字 来表示。 ●有错编码的译码方法与“译码错误”概率当使用有 蹴必须像膜方概率定究充译 P=P(U1U2Ul)=(l2)(l2-)的码字在译码时
离散无记忆源的等长编码 ⚫ 编码速率 R=NlogD/L。 ⚫ 无错编码 (U1U2…UL )的不同事件用不同的码字来表 示。能够实现无错编码的充要条件是DN≥KL。（即编 码速率R=NlogD/L≥logK） ⚫ 有错编码 (U1U2…UL )的有些不同事件用相同的码字 来表示。 ⚫ 有错编码的译码方法与 “译码错误”概率 当使用有 错编码时，必须给出译码方法（一个码字究竟翻译成 哪个事件）。“译码错误”的概率定义为 pe = P{(U1U2…UL )=(u1u2…uL )| (u1u2…uL )的码字在译码时 并不译为(u1u2…uL )}
●●● ●●●● ●●●●● ●●●● 离散无记忆源的等长编码 ●●0●● ●●●● ●●●● 关于编码速率的说明: 口编码速率本来是编码设备的性能指标。这就是说,首 先有了编码设备的编码速率R。,然后选择N和L,使得 实际的编码速率MogD不能超过编码设备的编码速率 Ro: R=MOgDILSRo 口当编码速率R比较高时,可以选择比较大的N,因此可 供选择的码字比较多,因此更容易设计出能够快速识 别的码,降低译码的难度。 口当编码速率R比较低时,意味着使用低成本的编码设备 。此时只能选择不大的N,因此更需要编码的技巧
离散无记忆源的等长编码 关于编码速率的说明： 编码速率本来是编码设备的性能指标。这就是说，首 先有了编码设备的编码速率R0，然后选择N和L，使得 实际的编码速率NlogD/L不能超过编码设备的编码速率 R0 ：R=NlogD/L≤R0。 当编码速率R比较高时，可以选择比较大的N，因此可 供选择的码字比较多，因此更容易设计出能够快速识 别的码，降低译码的难度。 当编码速率R比较低时，意味着使用低成本的编码设备 。此时只能选择不大的N，因此更需要编码的技巧
●●● ●●●● ●●●●● ●●●● 离散无记忆源的等长编码 ●●0●● ●●●0 ●●●● 在无错编码的前提下,编码的最低代价 当Rogk时,能够实现无错编码 当R<HU1)时,无论怎样编码都是有错编码。这是 因为R<H(U1)sogK。 (如果HU1)=logK,则以上两种情形已经概括了全部情 形。但如果H(U1)<logK,则还有一种情形) 当lgKR>HU)时,虽然无论怎样编码都是有错编 码,但可以适当地编码和译码使译码错误的概率p 任意小。这就是所谓“渐进无错编码
离散无记忆源的等长编码 在无错编码的前提下，编码的最低代价 ⚫ 当R≥logK时，能够实现无错编码。 ⚫ 当R<H(U1 )时，无论怎样编码都是有错编码。这是 因为R<H(U1 )≤logK。 （如果H(U1 )=logK，则以上两种情形已经概括了全部情 形。但如果H(U1 )<logK，则还有一种情形） ⚫ 当logK>R>H(U1 )时，虽然无论怎样编码都是有错编 码，但可以适当地编码和译码使译码错误的概率pe 任意小。这就是所谓“渐进无错编码
●●● ●●●● ●●●●● ●●●● 离散无记忆源的等长编码 ●●0●● ●●●0 ●●●● 渐进无错编码(简单地说就是:当R>HU)时,可以适当地编码 和译码使得译码错误的概率p任意小。严格地说就是:) 设给定了编码设备的编码速率R0,R0>H(U1)。则对任意的>0,总 存在一个L0,使得对任意的L>L0,都有对(U1U2…U)的等长编 码和对应的译码方法,满足 ①实际的编码速率R=MogD/L<Ro, ②译码错误的概率pa (11)渐进无错编码的原理大数定律。随着L的增加, (U1U2…J)的所有事件中,某些事件所占的比例越来越小(→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）