編碼 用於資料傳輸及壓縮 漢明碼 霍夫曼編碼.

Slides:



Advertisements
Similar presentations
1 1.2 信息的表示与存储  数据:数据是对客观事物的符号表示。 如,数值、文字、语言、图形、图像等都是不同形 式的数据。  信息:信息是既是对客观事物变化和特征的反映,又 是事物之间相互作用、相互联系的表征。 信息必须数字化编码,才能用计算机进行传送、存 储和处理。 信息具有针对性和时效性。
Advertisements

不插电的计算机科学 从 小 比特到 大 数字 不插电的计算机科学 从 小 比特到 大 数字 教师:裴华艳 :
2010 新聞局影視幕後人才培訓課程 電視節目的類型解析 講師:高光德教授. 電視節目主要類型  新聞氣象節目  體育節目  綜合娛樂節目.
第八章 土地行政管理.
「互联网金融2.0时代」与房地产的融合 广州互联网金融协会会长、广州e贷总裁 方颂.
企业会计学(三) 人大版本 吕 昌.
第二章 数字图像媒体.
第一章 引论.
第6章 通信系统仿真 6.1 通信工具箱函数 6.2 信息的度量和编码 6.3 差错控制编/译码方法 6.4 模拟调制和解调
大洋洲.
據點考核與評鑑 報告人:臺南市政府 照顧服務管理中心.
当代 国 际 关 系(案例6) 冷战时期美苏关系的演变.
硫化氢中毒及预防 硫化氢的特性与危害 硫化氢(H2S)是无色气体,有特殊的臭味(臭蛋味),易溶于水;比重比空气大,易积聚在通风不良的城市污水管道、窨井、化粪池、污水池、纸浆池以及其他各类发酵池和蔬菜腌制池等低洼处。 硫化氢属窒息性气体,是一种强烈的神经毒物。硫化氢浓度在0.4毫克/立方米时,人能明显嗅到硫化氢的臭味;70~150毫克/立方米时,吸入数分钟即发生嗅觉疲痨而闻不到臭味,浓度越高嗅觉疲劳越快,越容易使人丧失警惕;超过760毫克/立方米时,短时间内即可发生肺气肿、支气管炎、肺炎,可能引起生命危险;
34 府学胡同的文天祥祠,相传是南宋民族英雄文天祥当年遭囚禁和就义的地方,1376年明洪武九年建祠 。
會計資訊系統 專章A.
第三章 調整與編表.
第6章 信號編碼技術.
特殊族群運動健康訓練(I).
依据教材 全国高等教育自学考试指定教材 《西方行政学说史》, 竺乾威主编,高等教育出版社。
老子的素朴 厦门大学计算机科学系 庄朝晖.
正 信 讀 書 會 主 持 群 : 姚 永 錩 、 鄭 健 、 陳 淑 珍 佛法的生活應用 2008/07/23.
非法集资典型案例评析 南京师范大学法学院 蔡道通 2016年1月.
专题(二) 交往沟通 掌握技能 命 题 解 读 背 景 材 料 新 题 演 练 考 点 链 接 1.
天府欧城“星光儿童乐园” ---项目计划书 此为机密文件。 天府欧城.
松竹梅岁寒三友 步入建交 桃李杏村暖一家 迈进职教 活出精彩.
99年成語200題庫(21-40).
亚洲国家一流大学建设的国际化道路: 体制改革的视角
高考文言文的整体阅读.
課程:諮商概論 指導老師:李秀玉老師 閱讀書籍:傷癒—低估自我的醫治(一) (P.60~69)
第八单元第二课第一课时 严守法律 温州四中 蒋莉青.
高级财务会计.
默写基础知识: 1、家庭是由 关系、 关系或 关系而结合成的亲属生活组织。家里有 ,家中有 。
什么是颈椎病? 颈椎病是指颈椎间盘退行性变,及其继发性椎间关节退行性变所致脊髓、神经、血管损害而表现的相应症状和体征。
第五章 关税法 王小宁教授 三峡大学经济与管理学院.
战 后 国 际 关 系 专题五:冷战时期美苏关系的演变 政治学与行政管理系.
第一单元 中国传统文化主流思想的演变.
再生能源簡介.
公務人員退休法、撫卹法 法制與實務講習 銓敘部退撫司 中華民國99年8月.
《傅雷家书》 学 科:语文 年 级:九年级 授课教师:王宁宁.
第一節 行政裁量與不確定法律概念 第二節 行政裁量
本课设置5个环节 一、限时秒杀--5分钟 二、摩拳擦掌--9分钟 三、刀锋相见--20分钟 四、现炒现卖--5分钟 五、相约课后--1分钟.
从中国与联合国的关系演进 看联合国的产生与发展
《计算机操作员》精品 课件 淮南市潘集职教中心
Audio.
2014年度 预归类专业技能培训和资格考试 纺织品部分(50-63章).
第九章 影像壓縮.
單元一:基頻訊號傳送技術實習 (PCM取樣 量化 編碼部分) 數位通訊實習模擬 單元一.
语音编码 陈虎.
第四章 系統內部控制設計.
四川大学 计算机学院 陈 虎 多媒体技术基础 四川大学 计算机学院 陈 虎
第一章 引论.
第三章:Huffman编码 信源概率模型已知的Huffman编码 信源概率模型未知的Huffman编码 Huffman编码中的码字设计
教科版初中九年级物理 第五章 欧姆定律 3 等效电路.
MTI 多媒体技术 第三讲 XIDIAN 话音编码(Speech Coding).
多媒体技术基础 Fundamentals of Multimedia
Review of Information Theory
國立豐原高級中學 104學年度家長代表大會 主持人:張健家會長 時間:104年10月3日(星期六)上午10時0分 地點:行政樓二樓會議室.
试乘试驾团购执行方案(模板) 单 位:经销商名称 时 间:
图像压缩标准JPEG.
Predictive Coding Chapter /4/28 資料壓縮 ※ 第七章 預測編碼 ※
教網單一入口請假系統操作步驟 人事室.
聚合型第一種:隱沒帶、島弧 例子:臺灣東方的琉球海溝、南美洲智利海溝. 聚合型第一種:隱沒帶、島弧 例子:臺灣東方的琉球海溝、南美洲智利海溝.
宝 贝.
加減法文字題 國小低年級學生對加減法文字題的瞭解 小組成員 陳育娟 羅珠綾 侯宜孜
飛行器製作與飛行 講師:劉修建.
因果性:一个形而上学的预设 赵敦华 2008年5月.
有理数的乘方(二).
阶段性词汇训练3 上海海事大学信息工程学院.
第四章 買賣業會計.
第5章 信源编码.
Presentation transcript:

編碼 用於資料傳輸及壓縮 漢明碼 霍夫曼編碼

漢明碼(Hamming Code) 奇偶檢驗碼 漢明碼(Hamming Code),奇偶檢驗碼,是在電信領域的一種線性偵錯碼,以發明者Richard Hamming的名字命名。 漢明碼在傳輸的訊息流中插入驗證碼,以偵測並更正單一位元錯誤。由於簡單的漢明編碼,它們被廣泛應用於內部記憶體(RAM)。其 SECDED (single error correction, double error detection) 版本另外加入一檢測位元,可以偵測兩個以下同時發生的位元錯誤,並能夠更正單一位元的錯誤。 當傳送端與接收端的位元樣式的漢明距離 (Hamming distance) 小於或等於1時(僅有 1 bit 發生錯誤),可實現可靠的通訊。相對的,簡單的奇偶檢驗碼除了不能糾正錯誤之外,也只能偵測出奇數個的錯誤。 2018/11/9

奇偶校驗是一種添加一個奇偶位用來指示之前的資料中包含有奇數還是偶數個1的檢驗方式。 在數學方面,漢明碼是一種二元線性碼。對於每一個整數m > 2,存在一個編碼,帶有m個奇偶校驗位2m − m − 1個資料位。該奇偶檢驗矩陣的漢明碼是通過列出所有欄的長度是兩兩獨立 。 奇偶校驗是一種添加一個奇偶位用來指示之前的資料中包含有奇數還是偶數個1的檢驗方式。 如果在傳輸的過程中,有奇數個位發生了改變,那麼這個錯誤將被檢測出來(注意奇偶位本身也可能改變)。一般來說,如果資料中包含有奇數個1的話,則將奇偶位設定為1;反之,如果資料中有偶數個1的話,則將奇偶位設定為0。換句話說,原始資料和奇偶位組成的新資料中,將總共包含偶數個1. 2018/11/9

奇偶校驗並不十分可靠,如果資料中有偶數個位(置)發生變化,則奇偶位校驗仍將認為正確,因此不能檢測出錯誤。 即使奇偶校驗檢測出了錯誤,他也無法指出哪一位(置)出現了錯誤,從而進行更正。資料必須整體丟棄並且重新傳輸。在一個噪音較大的媒介中,成功傳輸資料可能需要很長時間或者不可能完成。雖然奇偶校驗的效果不佳,但是由於他只需要佔用一位額外的空間,因此這是開銷最小的檢測方式。並且,如果知道了發生錯誤的位(置) ,奇偶校驗還可以恢複數據。 如果一條資訊中包含更多用於糾錯的位,且透過妥善安排這些糾錯位使得不同的出錯位產生不同的錯誤結果,那麼我們就可以找出出錯位了。在一個7(or 8)位的資訊中,單個位出錯有7(or 8)種可能,因此3個錯誤控制位就足以確定是否出錯及哪一位出錯了。 2018/11/9

漢明研究了包括五取二碼在內的編碼方案,並歸納了它們的思想。 舉例而言﹐先決定漢明碼的長度 公式﹕m+r+1<=2^r 其中﹕m為資料所具有的位元數﹐例如m=8表示有8位元。 r為檢查位元數(漢民碼的長度) 假設資料有4位元﹐m=4﹐則(4+1)+r<=2^r﹐r為3﹐因為(4+1)+3<=2^3 假設資料有8位元﹐m=8﹐則(8+1)+r<=2^r﹐r為4﹐因為(8+1)+4<=2^4 2018/11/9

因為資料為8位元﹐所以r=4﹐漢民碼分別佈置於2^0=1﹐2^1=2﹐2^2=4﹐2^3=8四個位置:(用方形表示) 如何產生漢明碼: 假設資料為75(十進制)﹐75=01001011(二進制) 。 因為資料為8位元﹐所以r=4﹐漢民碼分別佈置於2^0=1﹐2^1=2﹐2^2=4﹐2^3=8四個位置:(用方形表示) 12 11 10 09 08 07 06 05 04 03 02 01 (位置) 0 1 0 0  1 0 1  1   2018/11/9

r=4真值表: 根據位置檢查資料編碼﹐並產生檢查碼(漢明碼)﹐使得1的個數為偶數。 有1的位置為﹕ 0. 0 0 0 0 8. 1 0 0 0 0 0 0 1 9. 1 0 0 1 0 0 1 0 10. 1 0 1 0 0 0 1 1 11. 1 0 1 1 0 1 0 0 12. 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 有1的位置為﹕ 2^0: 01,03,05,07,09,11 2^1: 02,03,06,07,10,11 2^2: 04,05,06,07,12 2^3: 08,09,10,11,12 根據位置檢查資料編碼﹐並產生檢查碼(漢明碼)﹐使得1的個數為偶數。 2018/11/9

根據位置檢查資料編碼﹐並產生檢查碼(漢明碼)﹐使得1的個數為偶數。 有1的位置為﹕ 2^0: 01,03,05,07,09,11 2^1: 02,03,06,07,10,11 2^2: 04,05,06,07,12 2^3: 08,09,10,11,12 12 11 10 09 08 07 06 05 04 03 02 01 (位置) 0 1 0 0  1 0 1  1   例如第一個漢明碼的產生是: ,1,1,1,0,1  =0,才能讓1的個數為偶數 第二個漢明碼的產生是: ,1,0,1,0,1  =1,才能讓1的個數為偶數 依此類推﹐產生同位元檢查碼﹕1010 傳輸資料變為: 0 1 0 0 1 1 0 1 0 1 1 0 2018/11/9

檢查﹕假設傳輸過程有一個位元發生錯誤﹐如: 12 11 10 9 8 7 6 5 4 3 2 1 原始資料: 0 1 0 0 1 1 0 1 0 1 1 0 接收資料: 0 1 0 1 1 1 0 1 0 1 1 0 檢查同位元(如果為偶數個1﹐則表示正確﹐用0表示﹐有錯誤用1表示) 2^0: 01,03,05,07,09,11 => 0,1,1,1,1,1 => 1 2^1: 02,03,06,07,10,11 => 1,1,0,1,0,1 => 0 2^2: 04,05,06,07,12 => 0,1,0,1,0 => 0 2^3: 08,09,10,11,12 => 1,1,0,1,0 => 1 所以1001=9表示第9個碼發生錯誤。 2018/11/9

檢查﹕假設傳輸過程有一個位元發生錯誤﹐如: 12 11 10 9 8 7 6 5 4 3 2 1 原始資料: 0 1 0 0 1 1 0 1 0 1 1 0 接收資料: 0 1 0 0 0 1 0 1 0 1 1 0 檢查同位元(如果為偶數個1﹐則表示正確﹐用0表示﹐有錯誤用1表示) 2^0: 01,03,05,07,09,11 => 0,1,1,1,0,1 => 0 2^1: 02,03,06,07,10,11 => 1,1,0,1,0,1 => 0 2^2: 04,05,06,07,12 => 0,1,0,1,0 => 0 2^3: 08,09,10,11,12 => 0,0,0,1,0 => 1 所以1000=8表示第8個碼發生錯誤。 2018/11/9

檢查﹕假設傳輸過程沒有位元發生錯誤﹐如: 12 11 10 9 8 7 6 5 4 3 2 1 原始資料: 0 1 0 0 1 1 0 1 0 1 1 0 接收資料: 0 1 0 0 1 1 0 1 0 1 1 0 檢查同位元(如果為偶數個1﹐則表示正確﹐用0表示﹐有錯誤用1表示) 2^0: 01,03,05,07,09,11 => 0,1,1,1,0,1 => 0 2^1: 02,03,06,07,10,11 => 1,1,0,1,0,1 => 0 2^2: 04,05,06,07,12 => 0,1,0,1,0 => 0 2^3: 08,09,10,11,12 => 1,0,0,1,0 => 0 所以0000=0表示沒有發生錯誤。 2018/11/9

檢查﹕假設傳輸過程有2位元發生錯誤﹐如: 12 11 10 9 8 7 6 5 4 3 2 1 原始資料: 0 1 0 0 1 1 0 1 0 1 1 0 接收資料: 0 1 0 1 1 0 0 1 0 1 1 0 檢查同位元(如果為偶數個1﹐則表示正確﹐用0表示﹐有錯誤用1表示) 2^0: 01,03,05,07,09,11 => 0,1,1,0,1,1 => 0 2^1: 02,03,06,07,10,11 => 1,1,0,0,0,1 => 1 2^2: 04,05,06,07,12 => 0,1,0,0,0 => 1 2^3: 08,09,10,11,12 => 1,1,0,1,0 => 1 所以1110=14表示有1個以上發生錯誤,但是無法更正﹐幸虧現今的技術同時發生2個錯誤碼機率很低。 2018/11/9

Test it now! 請編125的漢明碼,將漢明碼插入資料碼中,並假設其中一個碼出錯,演算偵錯過程。 2018/11/9

壓縮的編碼 壓縮的編碼方式種類繁多,因不同的應用而有不同的選擇,它們可分成兩大類:失真編碼和不失真編碼。 失真編碼方式,壓縮後的影像還原回來和原始影像不同,在一些應用裏影像變黑一點或亮一點,線條變粗一點或細一點不會影響我們對影像的認知,此時我們可以應用失真編碼來壓縮影像,因為壓縮碼的過程中,我們允許資料損失,因此可以做到較高的壓縮比 (原影像的資料量和壓縮影像資料量的比值),一般 10:1 是很容易達到的。但是某些影像,如 X 光片的影像,影像稍微有點失真往往會讓醫生做出不同的診斷,此時就不允許編碼後的影像和原影像不同,此時需利用不失真編碼壓縮影像。 2018/11/9

我們將源編碼過程細分為 (1) 映射 (mapping),(2) 量化和 (3) 編碼等三個程序。源編碼的主要目的是去掉多餘的資訊。此三程序如能完全反向回去,此種編碼即是不失真編碼,一般失真的發生都是重新量化所造成的。 編碼的程序 2018/11/9

基本理論 消息的意義 (Information) 2018/11/9

熵 (entropy) 假設符號源 S={s1, s2, s3, s4} Example: 且 p1=0.5, p2=0.25, p3 = p4 = 0.125。 以 a = 2 為基底我們可以得到熵為 H2(S) = 0.5 log22+0.25  log24 +0.125  log28+ 0.125  log28 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 資訊位元 2018/11/9

Example: 丟擲一個兩面出現機率相等的銅板。 S = {s1, s2} 且 p1=p2=0.5。 以 a = 2 為基底 個別事件的資訊量 I(s1) = I(s2) = -log2(1/2)= log22=1 我們可以得到熵為 H2(S) = 0.5 log22+0.5  log22 = 1  H2(S) 的值等於I(si) 。 2018/11/9

編碼方式 2018/11/9

編碼方式 假設符號源 S={s1, s2, s3, s4} Example: 且 p1=0.5, p2=0.25, p3 = p4 = 0.125。 以 a = 2 為基底我們可以得到熵為 H2(S) = 0.5 log22+0.25  log24 +0.125  log28+ 0.125  log28 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 資訊位元 假設編碼後的結果分別為 (00)2, (01)2, (10)2, (11)2 L=0.5*2+0.25*2+0.125*2+0.125*2 = 2 Redundancy=1-(1.75/2)=1/8 2018/11/9

2018/11/9

霍夫曼編碼(Huffman Coding) 用於資料壓縮 霍夫曼編碼(Huffman Coding)是一種編碼方式,是一種用於無損數據壓縮的熵編碼(權編碼)演算法。1952年,David A. Huffman在麻省理工攻讀博士時所發明的,並發表於《一種構建極小多餘編碼的方法》(A Method for the Construction of Minimum-Redundancy Codes)一文。 在電腦資料處理中,霍夫曼編碼使用變長編碼表對源符號(如文件中的一個字母)進行編碼,其中變長編碼表是通過一種評估來源符號出現機率的方法得到的,出現機率高的字母使用較短的編碼,反之出現機率低的則使用較長的編碼,這便使編碼之後的字元串的平均長度、期望值降低,從而達到無損壓縮數據的目的。 2018/11/9

例如,在英文中,e的出現機率最高,而z的出現機率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時,e極有可能用一個位元來表示,而z則可能花去25個位元(不是26)。用普通的表示方法時,每個英文字母均佔用一個位元組(byte),即8個位元。二者相比,e使用了一般編碼的1/8的長度,z則使用了3倍多。倘若我們能實現對於英文中各個字母出現機率的較準確的估算,就可以大幅度提高無損壓縮的比例。 2018/11/9

霍夫曼樹又稱最優二叉樹,是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度,就是樹中所有的葉結點的權值乘上其到根結點的路徑長度(若根結點為0層,葉結點到根結點的路徑長度為葉結點的層數)。樹的路徑長度是從樹根到每一結點的路徑長度之和,記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹,相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明霍夫曼樹的WPL是最小的。 2018/11/9

歷史 1951年,霍夫曼和他在MIT信息論的同學需要選擇是完成學期報告還是期末考試。導師Robert M. Fano給他們的學期報告的題目是,尋找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的,霍夫曼放棄對已有編碼的研究,轉向新的探索,最終發現了基於有序頻率二叉樹編碼的想法,並很快證明了這個方法是最有效的。 由於這個演算法,學生終於青出於藍,超過了他那曾經和信息論創立者香農共同研究過類似編碼的導師。霍夫曼使用自底向上的方法構建二叉樹,避免了次優演算法Shannon-Fano編碼的最大弊端──自頂向下構建樹。 2018/11/9

this is an example of a huffman tree 字母 頻率 編碼 space 7 111 a 4 010 e 000 f 3 1101 h 2 1010 i 1000 m 0111 n 0010 s 1011 t 0110 l 1 11001 o 00110 p 10011 r 11000 u 00111 x 10010 this is an example of a huffman tree 統計每個字母(包括空白字元)出現的次數, 從小到大從下而上建立二元樹 1 1 1 2018/11/9

Huffman Code 產生的方式在建立一二元樹,此二元樹的產生是一連串的排序和合併直至剩下二筆資訊機率和等於 1,然後再根據此二元樹找出每一原始資料的 Huffman-Code,找法是由上而下有分枝即每分枝給1和0。 排序時,機率大的排在上面,如果資料的機率分配很不平均,則此二元樹也不平均,且機率大的事件因為經過的合併次數少,所以在此二元樹的上層,故碼長也較短,合併及排序的經過如圖2,所得到的二元樹及編碼如圖3。 2018/11/9

圖2 Huffman Code 二元樹之建立 2018/11/9

圖3 Huffman Code 2018/11/9

圖4 8×8 範例影像 2018/11/9

2018/11/9

DPCM (Differential Pulse Code Modulation) 影像編碼 DPCM 的結構如圖 7-14,因為相鄰點差的信號振幅通常小於個別點的振幅,因此可以較少能階量化,較少位元編碼,如我們可以二個能階量化相鄰兩點的差 (+△和-△),量化的結果可以一個位元編碼,此種編碼方式又稱為 DM (Delta Modulation)。 圖7-14 DPCM 編碼結構 2018/11/9

DPCM (Differential Pulse Code Modulation) 影像編碼 當信號變化太快,且 DPCM 量化能階太少此時編碼後的信號無法趕上原信號此種現象稱為斜率過載 (Slope Overload),又量化能階減少時編碼後信號每一步進的變化不會和原信號的差剛好相同此時會造成振盪現象,稱為粒化誤差 (granular noise) 我們以差調為例說明,如圖 7-15。 (1:代表+,0:代表-) 圖7-15 差調的斜率超載和粒化誤差 2018/11/9

圖7-16 加入預測器的 DPCM 編碼結構圖 2018/11/9

圖7-17 DPCM 解碼結構 2018/11/9