《信息论与编码》课程教学课件（PPT讲稿）第三章 信源编码（一）离散信源无失真编码

第三章信源编码(一) 离散信源无失真编码 ●●●●● ●●●● ●●。●●

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

●●●●● ●●●● ●●0 ●●● ●●●● ●3.1信源及其分类 ●32离散无记忆信源的等长编码 ●3.3离散无记忆信源的不等长编码 ●34最佳不等长编码

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

31信源及其分类 ●●●●● ●●●● ●●。●●

3.1 信源及其分类

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

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

32离散无记忆源的等长 编码 ●●●●● ●●●● ●●。●●

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

●●●●● ●●●● 离散无记忆源 ●●0 ●●● ●●●● 字母表A={a1…,ak},概率p1,…,pk,长为L的源输 出序列a={u1,…,u4},共有K种序列 码符号字母表B={b1…,b)},以码符号表示源输 出序列,D元码 ●等长D元码,不等长D元码 ●单义可译码,每个消息都至少有一个码字与之 对应 ●单义可译码存在充要条件DNKL N≌ LlogK/ogD

离散无记忆源 ⚫ 字母表A={a1 ,…,aK },概率p1 ,…,pK ,长为L的源输 出序列uL={u1 ,…,uL}，共有KL种序列 ⚫ 码符号字母表B={b1 ,…,bD},以码符号表示源输 出序列，D元码 ⚫ 等长D元码，不等长D元码 ⚫ 单义可译码，每个消息都至少有一个码字与之 对应。 ⚫ 单义可译码存在充要条件DN≥KL N≥LlogK/logD

●●●●● ●●●● DMs的等长编码 ●●0 ●●● ●●●● NogD≥LH(U) ●H(U)是统计平均值,L达到无限时,一个具体 的源输出序列的平均每符号的信息量才等于 ●选L足够长,使NogD≥L[H(U)+e1]

DMS的等长编码 ⚫ NlogD≥LH(U) ⚫ H(U)是统计平均值，L达到无限时，一个具体 的源输出序列的平均每符号的信息量才等于 H(U) ⚫ 选L足够长，使 NlogD≥L[H(U)+eL ]

●●●●● ●●●● 弱、强ε典型序列集 ●●0 ●●● ●●●● T(L,E)={1:H(U)-E≤1≤H(U)+e T(L,E)={l1:(p(ak)-E)≤Lk≤L(p(ak)+E)}

弱、强e典型序列集 T (L,e ) ={u : H(U) −e  I  H(U) +e} U L L ( ,e ) ={ : ( ( ) −e )   ( ( ) +e )} TU L uL L p ak Lk L p ak

●●●●● ●●●● 信源划分定理 ●●0 ●●● ●●●● P{u2∈T(,E)}≥ 2b0)≤P(2)≤2 LIH(U)8I (1-E)2 LIH(O-8 (L,2)2 LIH(U+E] U

信源划分定理 [ ( ) ] [ ( ) ] [ ( ) ] [ ( ) ] (1 )2 | ( , )| 2 2 ( ) 2 { ( , )} 1 e e e e e e e e − + − + − − −       − L H U U L H U L H U L L H U r L U T L P u P u T L

●●●●● ●●●● 编码速率和等长编码定理 ●●0 ●●● ●●●● R=(1/)ogM=(N/L)logD,M为码字总数 ●对于给定信源和编码速率R以及任意ε>0,若有 I,以及编译码方法,使得I>Lo,错误概率小于ε, R是可达的 ●等长编码定理 R>H(U,R是可达的,R<H(U是不可达的 编码效率η=H(U/R

编码速率和等长编码定理 ⚫ R=(1/L)logM=(N/L)logD, M为码字总数 ⚫ 对于给定信源和编码速率R以及任意e>0，若有 L0 ,以及编译码方法，使得L>L0 ,错误概率小于e， R是可达的 ⚫ 等长编码定理 ⚫ R>H(U),R是可达的，R<H(U)是不可达的 ⚫ 编码效率h=H(U)/R