【正文】 游程序列： 3113213 二元序列： 000101110010001 若已知二元序列以 0 起始，從游程序列很容易恢復(fù)成 原來的二元序列。 哈夫曼編碼是先給每一符號(hào)一片樹葉，逐步合并成 節(jié)點(diǎn)直到樹根。 例： 設(shè)信源共 7 個(gè)符號(hào)消息，其概率如表所示： 費(fèi)諾（ Fano ）編碼方法 概率匹配 2 按信源符號(hào)的概率從大到小的順序排隊(duì)，不妨設(shè)： p ( a 1 ) ≥ p ( a 2 ) ≥ … ≥ p ( a n ) 按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接 近或相等。（統(tǒng)計(jì)匹配） 編碼后碼字 Y1 , Y 2 , ‥ , Y n 碼長分別為 K 1 , K 2 , ‥ , K n 碼的 平均長度 為： 編碼后的 信息傳輸率 為： 對(duì)于某一信源和某一碼符號(hào)集，若有一個(gè)唯一可譯 碼，其平均長度小于所有其他唯一可譯碼的平均長 度，則稱該碼為最佳碼（緊致碼）。 對(duì)信源的 L 長符號(hào)序列進(jìn)行 m 進(jìn)制編碼，碼長 KL 只要可用的碼字?jǐn)?shù)不少于擴(kuò)展信源的符號(hào)數(shù)： 就可做到唯一譯碼 編碼輸出碼 字的個(gè)數(shù) KL/L 是平均每個(gè)信源符號(hào)所需要的碼元符號(hào)個(gè)數(shù) 編碼后平均每個(gè)信源符號(hào)能載荷的最大信息量為： 定長編碼定理 在定長編碼中， K=KL 是定值，且為唯一可譯碼。向下不長 出樹枝的節(jié)點(diǎn)稱為終端節(jié)點(diǎn)或端點(diǎn)。只有分組碼才有對(duì)應(yīng) 的碼表，而非分組碼中則不存在碼表。 ? 密碼： –是以提高通信系統(tǒng)的安全性為目的的編碼。 采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特 數(shù)或信源的碼率。 針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的方 法把信源輸出符號(hào)序列變換為最短的碼字序列。 例： {0,10,11} 是一種唯一可譯碼。 應(yīng)用 Kraft 不等式，得： 不存在滿足這種 K i 的唯一可譯碼 要形成滿足上述長度 的碼字，必須在中間 節(jié)點(diǎn)放置碼字。 ? 差錯(cuò)概率 設(shè)差錯(cuò)概率用 ??Pe?表示，則有： ? ε 為一正數(shù) 為信源序列的自信息方差 當(dāng) 均為定值時(shí)，只要 L 足夠大， Pe可以小 于任一正數(shù) ?。 僅哈夫曼編碼是真正意義下的最佳編碼 哈夫曼編碼效率最高，費(fèi)諾編碼效率次之，香農(nóng) 編碼效率最低，甚至低于定長編碼的效率。 例： 對(duì)該信源進(jìn)行二 進(jìn)制費(fèi)諾編碼。以后每次取 m 個(gè)符號(hào)，分別配以 0,1,…, m 1；如此下去，直至所有 概率相加得 1 為止，即得到各符號(hào)的 m 進(jìn)制碼字。 ? 算術(shù)碼主要的編碼方法是計(jì)算輸入信源符號(hào)序列所 對(duì)應(yīng)的區(qū)間。 m 進(jìn)制哈夫曼編碼 在編 m 進(jìn)制哈夫曼碼時(shí)，為了使短碼得到充分利用， 使平均碼長最短，必須使最后一步的縮減信源有 m 個(gè) 信源符號(hào)。因此 平均碼長一般不會(huì)最小。 最佳變長編碼 凡是能載荷一定的信息量，且碼字的平均長度最 短，可分離的變長碼的碼字集合稱為最佳變長碼。 當(dāng) 時(shí)，不可能構(gòu)成無失真的編碼，也 就是不可能做一種編碼器，能使收端譯碼時(shí)差 錯(cuò)概率趨于零。 該碼樹從根到終端節(jié)點(diǎn)所經(jīng)路徑上， 每一個(gè)中間節(jié)點(diǎn)皆為碼字，因此碼 3 不是即時(shí)碼，但它是唯一可譯碼。反之為奇異碼 。 離散信源 無失真信源編碼定理稱為第一極限定理 離散和連續(xù)信道 信道編碼定理稱為第二極限定理 限失真信源編碼定理稱為第三極限定理 連續(xù)信源 信源編碼的主要任務(wù) 符號(hào)變換：使信源輸出符號(hào)與信道輸入符號(hào)匹配。 按不同的編碼目的，編碼分為三類： 信源編碼 信道編碼 安全編碼 /密碼 信源編碼 信源編碼是以提高通信的有效性為目的編碼。 無失真編碼 無失真信源編碼定理 信源編碼 限失真編碼 限失真信源編碼定理 無失真 ( 冗余度壓縮編碼 ) ：僅對(duì)信源的冗余度進(jìn)行 壓縮，不改變信源的熵。 定長碼 固定長度的碼，碼中所 有碼字的長度都相同。 碼樹上任一節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)碼字，組成該碼字的 碼元就是從樹根開始到該節(jié)點(diǎn)所經(jīng)過的樹枝 ( 碼元 ) 。 例 : 英文電報(bào)符號(hào)， n =27 ， L =1 ， m =2( 二元編碼 ) log 2 n ????? = log 2 27 ≈ 5 每個(gè)英文電報(bào)符號(hào)至少 log 2 m 要用 5位二元符號(hào)編碼 ? 實(shí)際英文電報(bào)符號(hào)信源，平均每個(gè)英文電報(bào)符號(hào)所 提供的信息量約等于 比特，大大小于 5 比特。 無失真變長信源編碼定理（ 香農(nóng)