第5章 信源编码.

Slides:



Advertisements
Similar presentations
课前寄语 1 、保持纪律 2 、相互配合. 第三节 公民的投资 —— 公民的存款储蓄 课堂导入.
Advertisements

渡黑水溝 郁永河. 2 戎克船:是明末清初時期往返兩岸的主要交通工具 ∗ 1. 關於台灣的開發歷史,我們到底了解多少呢?不妨試著說出 就我們所知有關台灣開發史的故事、小說、電影、音樂與大 家分享。 ∗ 2. 什麼是黑水溝?黑水溝為什麼會成為大陸移民渡海來臺時最 大的威脅? ∗ 3. 有聽過「六死三留一回頭」、「有唐山公,無唐山嬤」這兩.
台南市立後甲國中 訓導工作簡報 報告人:訓導主任 傅寶源 歡迎蒞臨指導. 訓導處是一個關懷學生生活問題、處理 學生生活事務的溫馨園地,舉凡生活常 規、安全防護、交通安全之教育,民主 法治、社團活動、訓育活動之訓練,衛 生習慣、飲食健康、預防疾病之培養, 體育活動,運動競賽、身心健康之鍛練, 均有專人專責為同學服務。
等可能性事件的概率(二) 上虞春晖中学数学组欢迎你! 1 本课件制作于 §10.5 等可能事件 的概率 ( 二 )
旅遊實務Ⅰ 授課教師:李健民 上課班級: 320. 課程大綱 旅遊業之設立程序 旅行業組織結構 旅行業之分類 旅行業之管理.
親 ( 四 ) 親近神的路. 一、親的三字訣、七字訣: 親近神,親愛人; 與主交通親近神,同情關心親愛人。 甚麼是親? 1. 親有親近、親愛,更有關心、同情、親切的 意思。 2. 親的人與人沒有間隔,拉近人與人之間的距 離,並且樂意幫助人,與人相調建造在一起。
商管群科科主任 盧錦春 年 3 月份初階建置、 4 月份進階建置、 5 月份試賣與對外營業。
第二班群教師團隊 105 張心平 107 鐘于寧 106 黃意評 108 鄭婉茹. 第二班群之班親會說明 學校規定事項說明 教學活動說明 班群活動介紹.
差勤.
申論題要拿高分並不容易,因為他是 有一定的技巧的,如果你遵照下列技 巧來作答申論題,相信高分並不難拿, 其技巧如下:
重建精细管理意识 不能粗线条管理 不简单敷衍人民 不轻易指责媒体 不与媒体对立冲突 粗心 粗糙 粗略 粗鲁 粗暴 不消极等待自生自灭
102大學甄選入學 個人申請、繁星推薦說明 主講人:簡慧嫻.
32个团体游戏 增加团队凝聚力.
窦娥冤 关汉卿 感天动地 元·关汉卿.
妝點歌曲的神奇彩衣 part2 六年一班 設計與教學:陳映蓉.
新進教師研習 教務處報告 報告人:教務處 林永仁 2011 年 8 月31日.
「明清時期台灣古典散文」 教師:田啟文.
新編多元性向測驗 測驗說明 輔導室
科學論文 鰂魚涌街的衛生情況 作者:廖梓芯 學校:北角官立上午小學 班級:P.5A.
广东省高新技术企业认定工作培训 关于专项审计报告的说明与解释.
議題探索-化學報告 題目:衣服質料的化學性質 成員:
知其不可而为之.
旅鼠之谜 位梦华.
在《命运交响曲》 音乐声中 安静我们的心 迎接挑战.
中国画家协会理事、安徽省美术家协会会员、 工艺美术师、黄山市邮协常务理事余承平主讲
101年國中畢業生多元進路宣導 國中部註冊組 100年10月29日.
第二章 语音 第六节 音变 轻 声1.
《成佛之道》序~第三章 圓融 /
高中職優質化專題 教育研究博士班二年級 游宗輝.
海星國中部直升方案說明 報告人:教務處 陳博文主任
101年度十二年國民基本教育 國民中學校長專業研習 校長落實補救教學、適性輔導 中輟生的預防與復學輔導之實務作為
歡迎各位老師 蒞校參訪 召集人、各位委員、同仁大家好,我是林淑玟,負責教務行政進行簡報 報告人:林淑玟 中華民國九十九年三月二十三日.
大學甄選入學 選填志願輔導說明會 曾文農工輔導室.
一所具有悠久歷史與優良傳統的 優質學校 強調生活教育與精緻教學 是您有心向學的最佳選擇.
國立嘉義高級工業職業學校 101年度綜合高中宣導研習 國立嘉義高工 教務主任 林章明
汉字的构造.
诵读欣赏 古代诗词三首.
“深入推进依法行政加快建设法治政府” -《法治政府建设实施纲要》解读
親愛的吉姆舅舅:   今天吃完晚餐後,奶奶說,在家裡情況變好以前,您要我搬到城裡跟您住。奶奶有沒有跟您說,爸爸已經好久沒有工作,也好久沒有人請媽媽做衣服了?   我們聽完都哭了,連爸爸也哭了,但是媽媽說了一個故事讓我們又笑了。她說:您們小的時候,她曾經被您追得爬到樹上去,真的嗎?   雖然我個子小,但是我很強壯,只要我會做的我都可以幫忙,但是,奶奶說,做其他事情以前,要先把功課做完。
大气的受热过程 周南中学.
孟子名言 1. 幼吾幼,以及人之幼。 2.天时不如地利, 。 3. ,威武不能屈。 4.得道者多助, 。 5.穷则独善其身, 。 6.
寡人之于国也 《孟子》.
海軍軍官學校 士官二專班 招生簡報 、 第1頁,共30頁.
海軍軍官學校 士官二專班 103學年度 招生簡報.
第六节 可降阶的二阶微分方程 一、 型的微分方程 二、 型的微分方程 三、 型的微分方程.
时政发布 制作:宋虹雷.
中学生心理健康讲座 打开心灵之门 开启阳光之路 主讲人:范荃.
贴近教学 服务师生 方便老师.
通信原理.
六年级 语文 下册 第四单元 指尖的世界.
(浙教版)四年级品德与社会下册 共同生活的世界 第四单元 世界之窗 第二课时.
教育部宣導專員 國立臺中家商 許敏政主任 101年2月23日製作 #201~203
25.3 用 频 率 估 计 概 率 快走啊听老师讲“用频率估计概率”哦.
通信原理.
第1章 熵和互信息量.
导数的应用 ——函数的单调性与极值.
十二年國民基本教育 103學年度高中高職及五專 入學方式與就學區規劃 (草案諮詢稿)
第五讲 从常用连续分布到二维变量分布 本次课讲授:第二章的 ; 下次课讲第三章的 ;
無尾熊 作者:五年二班潘勁亨.
第八章 数字信号的最佳接收 1、引言 2、数字信号接收的统计表述 3、关于最佳接收的准则 4、确知信号的最佳接收 5、随相信号的最佳接收
高中職多元進路 家長說明會 主講人: 東莞台商子弟學校 麥馨月 日 期:
小学5.
Xián 伯 牙 绝 弦 安徽淮南市八公山区第二小学 陈燕朵.
國立嘉義高級工業職業學校 101年度雲嘉區綜合高中宣導研習 國立嘉義高工 綜高高中學務組長 呂明欣
補習動機與補習效益之分析 -以大台北地區大學生為例- 九十九學年度第二學期 社會研究方法 期末報告 指導教授:黃朗文 天組
3-3 随机误差的正态分布 一、 频率分布 在相同条件下对某样品中镍的质量分数(%)进行重复测定,得到90个测定值如下:
99年基測暨直升、原藝班、 申請、甄選入學報名作業說明
臺灣北區102學年度高級中等學校 舞蹈班暨聯合甄選入學術科測驗 暨甄選入學說明會
台中市黎明國中105學年度 學生報考 一般智能暨學術性向資賦優異學生鑑定 報名流程說明
Presentation transcript:

第5章 信源编码

5.2 无失真信源编码

5.2.3 最佳变长编码 最佳码: 能获得最佳码的编码方法主要有: 在信源满足无失真编码定理的编码方式中, 5.2.3 最佳变长编码 最佳码: 在信源满足无失真编码定理的编码方式中, 若存在一种唯一可译码,其平均码长小于所有其 他唯一可译码的平均长度。 能获得最佳码的编码方法主要有: 香农(Shannon) 费诺(Fano) 哈夫曼(Huffma )

1、香农编码 I(xi)≤ Ki <I(xi)+1 香农第一定理指出了平均码长与信源之间的关系,同时也指出了可以通过编码使平均码长达到极限值,这是一个很重要的极限定理。 香农第一定理指出,任意一个符号Xi的码字的 长度Ki满足下式: I(xi)≤ Ki <I(xi)+1 就可以得到这种码。 这种编码方法称为香农编码

⑷将Pi用二进制表示,并取小数点后Ki位作为 符号xi的码字。 二进制香农码的编码步骤如下: ⑴将信源符号按概率从大到小的顺序排列,     p(x1)≥ p(x2)≥…≥ p(xn) ⑵确定每个符号的码字长度Ki , -log2 p(xi)≤ Ki <1-log2 p(xi) ⑶令p1=0,用Pi表示第i个码字的累加概率, ⑷将Pi用二进制表示,并取小数点后Ki位作为 符号xi的码字。

对该信源编二进制香农码。其编码过程如表所示 例 有一单符号离散无记忆信源 对该信源编二进制香农码。其编码过程如表所示 以i = 3为例: 码字长度: K4 = [-log0.2] = 3 累加概率 Pi=0.70 → 0.10110… 信源 符号 xi 概率 p(xi) 累加 Pi -log p(xi) 码长 码字 x1 0.4 1.32 2 00 x2 0.3 1.73 01 x3 0.2 0.7 2.32 3 101 x4 0.05 0.9 4.3 5 11100 x5 0.95 11110 00 01 101 11100 11110 这些码字没有占满所有码树,所以是非最佳码

香农码的平均码长 熵 x1 编码效率 x2 x5 x3 x4 为提高编码效率,首先应达到满树;如把x4x5换成前面的节点,可减小平均码长。

2、费诺编码 费诺编码属于概率匹配编码。 编码步骤如下: 将概率按从大到小的顺序排列,令 p(x1)≥ p(x2)≥…≥ p(xn) 按编码进制数将概率分组,使每组概率尽可能接近或相等。如编二进制码就分成两组,编m进制码就分成m组。 给每一组分配一位码元。 将每一分组再按同样原则划分,重复步骤2和3,直至概率不再可分为止。

例 设有一单符号离散信源 对该信源编二进制费诺码。 平均码长: K= 2.0 编码效率: η=97.5% 平均码长: K= 2.1 例 设有一单符号离散信源 平均码长: K= 2.0 编码效率: η=97.5% 平均码长: K= 2.1 编码效率: η=93% 对该信源编二进制费诺码。 信源符号 xi 符号概率 p(xi) 第1次 分组 第2次分组 第3次 码 字 长 x1 0.4 00 2 x4 0.05 1 010 3 x5 011 x2 0.3 10 x3 0.2 11 信源符号 xi 符号概率 p(xi) 第1 分组 第2分组 第3 第4 码 字 长 x1 0.4 1 x2 0.3 10 2 x3 0.2 110 3 x4 0.05 1110 4 x5 1111

平均码长 编码效率 费诺码比较适合于每次分组概率都很接近的信源 特别是对每次分组概率都相等的信源进行编码时, 可达到理想的编码效率。

例 有一单符号离散无记忆信源 对该信源编二进制费诺码,编码过程如表:

信源熵为 H(X)=2.75(比特/符号) 平均码长为 编码效率为 η=1 之所以如此,因为每次所分两组的概率恰好相等。

3、哈夫曼编码 哈夫曼编码也是用码树来分配各符号的码字。 哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。

哈夫曼编码的步骤如下: ⑴ 将信源消息符号按其出现的概率大小依次排列 p(x1)≥p(x2)≥…≥ p(xn) ⑵ 取两个概率最小的符号分别配以0和1两码元,并 将这两个概率相加作为一个新符号的概率,与未 分配的二进符号的字母重新排队。 ⑶ 对重排后的两个概率最小符号重复步骤⑵的过 程。 ⑷ 不断继续上述过程,直到最后两个符号配以0和1 为止。 ⑸ 从最后一级开始,向前返回得到各个信源符号所 对应的码元序列,即相应的码字。

在图中读取码字的时候,要从后向前读,此时编出来的码字是哈夫曼码。 例5-7 设单符号离散无记忆信源如下,要求对信源编二进制哈夫曼码。编码过程如下表 在图中读取码字的时候,要从后向前读,此时编出来的码字是哈夫曼码。 信源符号xi 符号概率p(xi) 编码过程 x1 0.20 x2 0.19 x3 0.18 x4 0.17 x5 0.15 x6 0.10 x7 0.01 码字 10 11 000 001 010 0110 0111 0.20 0.19 0.18 0.17 0.15 0.11 0.26 0.20 0.19 0.18 0.17 0.35 0.26 0.20 0.19 0.39 0.35 0.26 0.61 0.39 1 1 1 1 1 1

熵 平均码长为 编码效率

3、哈夫曼编码 哈夫曼的编法并不惟一。 每次对缩减信源两个最小概率的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到哈夫曼码字。 不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所以没有本质区别;

3、哈夫曼编码 缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。 此时得到的码字长度Ki也不相同,但平均码长相同,即编码效率相同。

例5-8 单符号离散无记忆信源 编码过程 x1 x2 x3 x4 x5 码字 1 01 000 0010 0011 码字 00 10 11 信源符号xi 符号概率p(xi) 编码过程 x1 0.4 x2 0.2 x3 x4 0.1 x5 码字 1 01 000 0010 0011 码字 00 10 11 010 011 0.4 0.2 0.4 0.2 0.6 0.4 1 1 1 1

3、哈夫曼编码 编法一的平均码长为 编法二的平均码长为 两种编法的平均码长相同,所以编码效率相同。

讨论:同一种编码方法,概率相同、放置位置 不同,哪种方法更好? 定义码字长度的方差σ2: 第二种编码方法的码长方差要小许多。 第二种编码方法的码长变化较小,比较接近于 平均码长。

第一种方法编出的5个码字有4种不同的码长; 第二种方法编出的码长只有两种不同的码长; 第二种编码方法更简单、更容易实现,所以更好。 结论: 在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。

3、哈夫曼编码 哈夫曼编码总结: 对相同的信源编码,其熵是一样的,采用不同的编法,得到的平均码长可能不同。 平均码长越短,编码效率就越高。

r进制哈夫曼编码 在编r进制哈夫曼码时为了使平均码长最短,就要使长码的符号数尽量少、概率尽量小。 希望信源符号数满足: m=n(r-l)+r 其中r是进制数,n是缩减的次数: 若信源符号数m无法满足上式,那么必须在最后添加概率为0的虚拟符号,以满足条件,使得长码的符号数最少;

例: 对如下单符号离散无记忆信源编三进制哈 夫曼码 这里:r=3,m=8 令n=3,r+n(r-1)=9,则需要添加一个需要 符号来满足条件 设符号x9,概率为0.

编码过程 x1 x2 x3 x4 x5 x6 x7 x8 x9 码字 10 11 12 21 22 200 201 202 信源符号xi 符号概率p(xi) 编码过程 x1 0.40 x2 0.18 x3 0.10 x4 x5 0.07 x6 0.06 x7 0.05 x8 0.04 x9 0.00 码字 10 11 12 21 22 200 201 202 0.40 0.18 0.10 0.09 0.07 0.06 0.40 0.22 0.18 0.10 0.40 0.38 0.22 1 2 1 2 1 2 1 2

平均码长为 平均信息量为 编码效率为 哈夫曼的编码效率相当高,对编码器的要 求也简单得多。

结论 香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使概率大的信源符号对应较短的码字,缩短信源的平均码长,从而实现了对信源的压缩; 香农码有系统的、惟一的编码方法,但在很多情况下编码效率不是很高; 费诺码和哈夫曼码的编码方法都不唯一;

结论 费诺码比较适合于对分组概率相等或接近的信源编码,费诺码也可以编m进制码,但m越大,信源的符号数越多,可能的编码方案就越多,编码过程就越复杂,有时短码未必能得到充分利用; 哈夫曼码对信源的统计特性没有特殊要求,编码效率比较高,对编码设备的要求也比较简单,因此综合性能优于香农码和费诺码。

5.3 限失真信源编码定理

限失真信源编码定理 设离散无记忆信源X的信息率失真函数为R(D) , 当信息率R>R(D)时,只要信源序列长度 L 足够长,一定存在一种编码方法,其译码失真 小于或等于 D+ε,ε为任意小的正数; 反之,若R<R(D) ,则无论采用什么样的编 码方法,其译码失真必大于D。 如是二元信源,则对于任意小的ε>0,每一个 信源符号的平均码长满足如下公式:

5.4 常用信源编码方法

常用信源编码 香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。 香农编码、费诺编码、哈夫曼编码属于无失真信源编码; 当信源有记忆时上述编码效率不高; 香农编码、费诺编码、哈夫曼编码属于无失真信源编码; 游程编码对有记忆信源编码更有效; 游程编码属于限失真信源编码。

游程编码 游程: 数字序列中连续出现相同符号的一段。 二元序列的游程:只有“0”和“1”两种符号。 连“0”这一段称为“0”游程,它的长度称 为游程长度L(0); 连“1”这一段称为“1”游程,它的游程长 度用L(1)表示。

游程编码 二进制序列进行游程编码的规则: 若规定二元序列总是从“0”开始,第一个游程 是“0”游程,则第二个游程必为“1”游程,第 三个又是“0”游程……。 对于随机序列,游程长度是随机的其取值可为 1,2,3,…,直至无穷。 游程变换: 是一种一一对应的变换,也是可逆变换。 例如:二元序列000101110010001… 可变换成如下游程序列 31132131

游程编码 游程变换减弱了原序列符号间的相关性。 游程变换将二元序列变换成了多元序列; 在此基础上还可以利用哈夫曼编码,进一步压缩信源,提高通信效率。 编码方法: 首先测定“0”游程长度和“1”游程长度的概率分布,即以游程长度为元素,构造一个新的信源; 对新的信源(游程序列)进行哈夫曼编码。

算术编码的主要理念 算术编码利用了累积概率的概念。 算术码主要的编码方法是计算输入信 源符号序列所对应的区间。 把信源输出序列的概率和实数段[0,1]中 的一个数C联系起来。

设信源字母表为{a1, a2},其概率p(a1)=0.6, p(a2)=0.4 将[0,1]分成与概率比例相应的区间,[0,0.6] [0.6,l] p(a1) p(a2) 0 0.36 0.6 0.84 1 0 0.6 1 随着序列的长度不断增加,C所在区间的长度就越短,也就可以更加精确地确定C的位置 p(a1a1) p(a1a2) p(a2a1) p(a2a2) 设信源输出序列S=S1S2S3…Sn 当信源输出的第一个符号S1 = a1时,数C的值处在[0,0.6] 当信源输出的第一个符号S1 = a2时,数C的值处在[0.6,l] 根据信源S1的情况,把C所在的段再次按概率 比例划分

累积概率 设信源符号集A={a1,a2,…,an},其相应概率分 布为p(ai)或pi,p(ai)>0(i=1,2, …,n) 信源符号的累积概率为 显然 P0= 0; P1= p(a1)=p1 ; P2= p(a1)+p(a2)= p1 +p2; … 而且 p(ar) =pr= Pr - Pr-1

累积概率Pr和Pr-1都是小于1的正数,可用[0,1] 区间内的两个点来表示; p(ar)就是这两点间的小区间的长度,如图: P0 P1 P2 P3 1 … p(a1) p(a2) P(a3) … 当A={0,1}二元信源时: P0=0; P1=p(0) P0 P1 1 p(0) p(1)

算术编码 计算二元无记忆信源序列的累积概率 初始时:在[0,1)区间内由P1划分成二个子区 间[0,P1)和[P1,1),P1=p(0) 。 若输入符号序列的第一个符号为S=“0”, 落入[0,P1)区间,得累积概率 P (S =“0”)= P0 = 0;

若输入第二个符号为“1”,S=“01”, S=“01”所对应的区间是在区间[0, P1 ) 中进行分割; 符号序列“00”对应的区间为 [0,P(S=“01”)) 符号序列“01”对应的区间为 [P(S =“01”),P1) 累积概率: P(S =“01”)=p(00)= p(0)p(0)

设输入符号序列S=011 P0= 0 p(0)= p(00)+p(01) P(01)= p(00) p(01)= p(010)+p(011) P0 P1 1 p(0) p(1) P1 P0 P(01) p(01) p(00) P(01) P(011) P1 p(010) p(011) P0= 0 P(01)= p(00) P(011)= P(01)+p(010) = P(01)+ p(01) P1 p(0)= p(00)+p(01) p(01)= p(010)+p(011)

算术编码 一般多元信源序列的累积概率递推公式 序列的概率公式

算术编码 在编码过程中,每输入一个符号要进行乘法和加法运算,所以称为算术编码。 通过关于信源符号序列的累积概率的计算,把区间分割成许多小区间,不同的信源符号序列对应不同的区间为[P(S), P(S)+p(S))。可取小区间内的一点来代表这序列。

算术编码 编码方法: 将符号序列的累积概率写成二进位的小 数,取小数点后L位,若后面有尾数,就进位 到第L位,这样得到的一个数C,并使L满足 取整

P(S) == 0.110100100111 例:设二元无记忆信源S={0,1},其p(0)=1/4,p(1)=3/4。 对二元序列11111100做算术编码。 解:p(S=11111100)=p2(0)p6(1)=(1/4)2 (3/4)6 经过计算得到序列的累计概率经过二进制编码得到: P(S) == 0.110100100111 得 C = 0.1101010 S的码字为 1101010

信源编码总结 我们学习了几种信源编码:香农编码、费诺编码、哈夫曼编码、游程编码、算术编码。 游程编码和算术编码是非分组编码; 游程编码是限失真信源编码。 本章介绍的都是离散信源变长编码。 优点:提高编码效率; 缺点:需要大量缓冲设备来存储这些变长码,然后再以恒定的码率进行传送;在传输的过程中如果出现了误码,容易引起错误扩散,所以要求有优质的信道。