DVIP06 熵编码.ppt

门爱东教授******@(消息集)编码输出集(接收端)U0={a1,a2,…,aK}Y={y1,y2,…,yK}符号集Sm={s1,s2,…,sM}编码器模型图其中U0是无记忆信源的消息集,由多个消息ak构成(k=1,2,……,K),出现的概率分别为Pj(j=1,2,……,K)。Y是输出集,由多个码字yk构成(k=1,2,……,K),yk与ak一一对应。Sm是符号集,由m个码元si构成(i=1,2,……,M),符号集中的码元组成输出码字。熵编码原理-信息量和信息熵列挞械艺没土寇灯吧忽栽诉旨蛔队阿蔡痘尉阅汇邻委矿瘟芜越絮啸币蘸岿DVIP06熵编码DVIP06熵编码3熵编码原理-信息量和信息熵信息:是用不确定性的量度定义的信息量:从N个可能事件中选出一个事件所需要的信息度量或含量。上述消息“ak”的信息量定义为:熵:如果将信源所有可能事件信息量进行平均就得到信息的熵(熵就是平均信息量),单位是bits/Symbol。熵的特性:绘圾吗摄捏鹊厂禹郧杨侠抽屎裸号拢夹剑铀流胎顶素戌抖纫琳耳尚翰盔连DVIP06熵编码DVIP06熵编码4信源含有的平均信息量(熵)H(U0),就是对符号U0进行可解码的变字长编码的平均码长Iav的下限,即无失真编码的理论极限。相反,如果有足够大的符号块进行联合编码,平均码长Iav可以逼近H(U0)。码的冗余定义为:信源中或多或少的含有自然冗余。熵编码原理-信息量和信息熵如果每个码字长度等于则码字的平均码长等于它的熵,没有冗余,即对于二进制码字,概率将都是二进制分数:磷迂万账昨村伐厂裸皮哮畦侥磕贩抨趣全舜盎集庞辽钨脸锑厩较碍郝谜烘DVIP06熵编码DVIP06熵编码5熵编码原理-信息量和信息熵例对于等字长码,要表示4个事件,需要2bit,其平均码长为2bit/符号,。对于变字长码坷串聋抗撕哇郡荐汝正鸟来爽凑洲戌屿东架短刑砖虽袋欣外然敢憎两翌激DVIP06熵编码DVIP06熵编码6熵编码原理-变字长编码定理在变字长编码中,对于出现概率大的信息符号,赋予短字长的码,对于出现概率小的信息符号,赋予长字长的码。如果码字长度严格按照符号概率的大小的相反顺序排列,则平均码字长度一定小于按任何其它符号顺序排列方式得到的码字长度。最佳的平均码字长度:其中:P(ak)是信源符号ak出现的概率;Ik是符号ak的编码长度。根据编码方法定义规定:如果P(ai)≥P(as),则Ii<Is如果将ai的码字与as的码字互换,则:慢拓拥赛韧鼎铱劈艾哇垣蒂擒菲夫驱耳赦紫池烷钞疮守刻绘赤绰噎锥按湘DVIP06熵编码DVIP06熵编码7Huffman编码Huffman于1952发明了整数码的最佳变字长编码,利用了上述熵、熵编码和变字长编码概念。所谓的整数码是指每个符号所对应的码字的位数都是整数。Huffman码码树形成步骤①合并:把信源符号按概率大小顺序排列,出现概率最小的两个符号的概率相加,得到一个新的合并概率。②置换:把这个合并概率看成是一个新组合符号的概率。③类推:重复上述做法直到最后只剩下两个符号概率为止。④赋值和反推:把上述码树转换为前缀码。完成以上概率顺序排列后,再反过来逐步向前进行编码,每一步有两个分支各赋予一个二进制码,可以对概率大的赋为“1”,概率小的赋为“0”。硬憎孙淄悲赢剥蒙渍板邱晕押佯酿埔卓瑚烘诱秒跳淆津芍荷甫盯蝗成篆植DVIP06熵编码DVIP06熵编码8Huffman编码比特数22334444010**********敲多椭斗耸闺饵损正跟黔槛犯娠释评醒缴修胆浚丸心揖投谩眨人狈猛绽嵌DVIP06熵编码DVIP06熵编码9例:信源有四个符号:Xa1a2a3a41/21/41/81/8信息熵:Huffman编码Huffman(二进制编码)a1a2a3a4010110111平均码长:Iav=(1/2)1+(1/4)2+(1/8)6=:==100%编码冗余:R=0a11/2a21/4a31/8a41/800011/211/41010110111姻周筛昂熏普涝错坷橙滓离贼控哆鼎列吁赖饰傅俄陇毕掂池拱咕谋嚏疑床DVIP06熵编码DVIP06熵编码10