菲諾由Fano音譯而來，又常被譯為費諾。費諾(菲諾)算法是由Fano 提出的一種編碼算法。費諾編碼算法就是通過使編碼中各個句號出現的機率大致相等，實現機率均勻化，從而減少冗餘度，提高編碼效率。費諾編碼是一種信源編碼，它編碼後的費諾碼要比香農碼的平均碼長小，訊息傳輸速率大，編碼效率高。但它屬於機率匹配編碼。
基本介紹
- 中文名：菲諾算法
- 外文名：Fano algorithm
- 提出者：Fano
- 性質：編碼算法
- 屬於：機率匹配編碼
- 領域範圍：編碼
編碼概述,費諾編碼基本原理,費諾編碼特點,費諾編碼算法,費諾編碼過程示例,
菲諾由Fano音譯而來，又常被譯為費諾。費諾(菲諾)算法是由Fano 提出的一種編碼算法。
編碼概述
早期的數據壓縮來自於人們對機率的了解。當對文字信息進行編碼時，如果 出現機率較高的字幕賦予較短的編碼，為出現機率較低的字母賦予較的編碼，平均編碼長度就能縮短不少。著名的Morse電碼就是一個範例。資訊理論之父C.E.Shannon曾指出，任何信息都存在冗餘，冗餘大小與信息中個符號出現機率（不確定性）有關。他所提出的無失真信源編碼定理奠定了數據壓縮的理論基礎。數據壓縮的目的就是要消除冗餘，資訊理論是運用率論與數理統計的方法研究信息、信源熵、通信系統、數據傳輸、密碼學、數據壓縮等問題的套用數學學科。
從DVD到個人電腦，從衛星通信到文，在我們今天的生活中，信息幾乎在每個領域都扮演者重要角色。工程師克勞德·香農於1948年奠定了資訊理論的基礎，他指出了通信的極限。基於這理論產生了數據壓縮技術、糾錯技術等各個套用技術，這些技術提高了數據傳輸和存儲的效率。資訊理論將信息的傳遞作為一種統計現象來考慮，給了估算通信信道容量的方法。信息傳輸和信息壓縮是資訊理論研究中的兩大領域。這兩個方面又由信息傳輸定理、信源—信道隔離定理相互聯繫。當然資訊理論的重大套用遠不止於此。DNA是一種信息存儲物質，正事資訊理論幫助人們解開了生物因組密碼之謎。簡單地說資訊理論包含了生命、宇宙乃至一切。
資訊理論對現代社會的影響是多方面的。首先，在理論研究方面，資訊理論所處的地位已遠遠超出了香農當年所界定的“通信的數學理論”的範疇，得到了不斷的擴充和發展，出現了語義信息、語法信息與語用信息等研究與信息的意義有關的學科，以及面向智慧型研究的全信息理論。如今，信息已成為與物質、能量並列的宇宙中的三個基本要素，世間萬物的發展變化可歸結為物質、能量和信息的傳遞和轉化過程。另一方面，在科學和技術高度發展的今天，信息的概念也被滲透到許多不同的學科和領域，深入到了社會生活的各個方面，成為可與相對論和量子力學並駕齊驅的新一代邊緣交叉學科的重要組成部分。特別是以資訊理論、控制論、和系統論為代表的“老三論”以及以普利高津的耗散結構理論，哈肯的協同學和托姆的突變論或艾根的超循環理論為代表的“新三論”的出現，標誌著一代新的邊緣交叉學科的興起。它們的形成和發展對現代科學的研究具有重要的方法論上的指導意義。
編碼是信息從一種形式或格式轉換為另一種形式的過程也稱為計算機程式語言的代碼簡稱編碼。用預先規定的方法將文字、數字或其它對象編成碼，或將信息、數據轉換成規定的電脈衝信號。編碼在電子計算機、電視、遙控和通訊等方面廣泛使用。在計算機硬體中，編碼（coding）是指用碼來表示各組數據資料，使其成為可利用計算機進行處理和分析的信息。代碼是用來表示事物的記號，它可以用數字、字母、特殊的符號或它們之的組合來表示，將數據轉換為代碼或編碼字元，並能譯為原數據形式。是計算機書寫指令的過程，程式設計中的一部分。在地圖自動製圖按一定規則用數字與字母表示地圖內容的過程，通過編碼，使計算機能識別地圖的各地理要素。
編碼分為信源編碼和信道編碼，其中信源編碼又為無失真和限失真。由於這些定力都要求符號數很大，以便其值接近所規定的值，因而這些定力被稱為極限定理。一般稱無失真信源編碼定力為第極限定理；信道編碼（包括離散和連續信道）稱為第二極限定理；限失真信源編碼定力稱為第三極限定理。
費諾編碼基本原理
費諾編碼就是通過使編碼中各個句號出現的機率大致相等，實現機率均勻化，從而減少冗餘度，提高編碼效率。凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為最佳變長碼。在編N進制碼時首先將信源訊息符號按其出現的額機率一次又小到大排列開來，並將排列好的心愿符號按機率值分N大組，使N組的機率之和近似相同，並對各組賦予一個N進制碼元0、1...N-1。之後再針對每一個大組內的心愿符號做如上處理，即再分為機率相同的N組，賦予N進制碼元。如此重複，直到每組只剩下一個心愿符號為止。此時每個信源符號所對應的碼字即為費諾碼。針對同一個心愿，費諾碼比香農碼平均碼長小，訊息出書速率大，編碼效率高。費諾編碼是一種信源編碼，它編碼後的費諾碼要比香農碼的平均碼長小，訊息傳輸速率大，編碼效率高。但它屬於機率匹配編碼它不是最佳的編碼方法。
費諾編碼特點
費諾編碼是一種信源編碼，它編碼後的費諾碼要比香農碼的平均碼長小，訊息傳輸速率大，編碼效率高。但它屬於機率匹配編碼，它不是最佳的編碼方法。
費諾編碼屬於機率匹配編碼，具有如下特點：
（1）機率大，則分解次數少；機率小則分解次數多，這符合最佳編碼原則。
（2）碼字集合是唯一的。
（3）分解之後先得碼字後得碼長。
費諾編碼算法
1.將信源訊息符號按其出現的機率大小依次排列。
2.將依次排列的信源符號按機率值分為兩大組，使兩個組的機率之和近似相同，並對各組賦予一個二進制碼元“0”和“1”。
3.將每一大組的信源符號再分為兩組，使劃分後的兩個組的機率之和近似相同，並對各組賦予一個二進制符號“0”和“1”。
4.如此重複，直至每個組只剩下一個信源符號為止。
5.信源符號所對應的碼字即為費諾碼。
費諾編碼過程示例
訊息 符號 | 各個訊息 機率 | 第一次 分組 | 第二次 分組 | 第三次 分組 | 第四次 分組 | 第五次 分組 | 二元 碼字 | 碼長 Ki |
x1 | 0.25 | 0 | 0 | 0 | 0 | 0 | 00 | 2 |
x2 | 0.2 | 1 | 01 | 2 | ||||
x3 | 0.2 | 1 | 0 | 100 | 3 | |||
x4 | 0.1 | 1 | 101 | 3 | ||||
x5 | 0.1 | 1 | 0 | 110 | 3 | |||
x6 | 0.08 | 1 | 1110 | 4 | ||||
x7 | 0.05 | 1 | 11110 | 5 | ||||
x8 | 0.02 | 1 | 11111 |
