[計算機(jī)軟件及應(yīng)用]第5章信源編碼ppt-在線瀏覽
2025-04-09 22:16本頁面
【正文】 個碼字，組成該碼字的 碼元就是從樹根開始到該節(jié)點所經(jīng)過的樹枝 ( 碼元 ) 。 滿樹 — 等長碼 節(jié)數(shù) — 碼長 非滿樹 — 變長碼 樹碼：若有 n 個信源符號，那么在碼樹上就要選擇 n 個終端節(jié)點，用相應(yīng)的 m 元基本符號表示這些碼字。 ? 當(dāng)碼字長度給定，即時碼不是唯一的。 唯一可譯碼存在的充分和必要條件 各碼字的長度 K i 應(yīng)符合克勞夫特 (Kraft) 不等式： m ：碼元進(jìn)制數(shù) n ：信源符號數(shù) Ki ：各個碼字的長度 例： 設(shè)二進(jìn)制碼樹中 X∈ ( a1, a2, a3, a4)， K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。 中間節(jié)點 如果將各碼字長度改成： 存在唯一可譯碼 K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。 注意 Kraft 不等式只是用來說明唯一可譯碼是 否 存在 ，并不能作為唯一可譯碼的判據(jù)。 K1 =1 , K2 =2 , K3 =3 , K4 =3 。 對信源的 L 長符號序列進(jìn)行 m 進(jìn)制編碼，碼長 KL 只要可用的碼字?jǐn)?shù)不少于擴(kuò)展信源的符號數(shù)： 就可做到唯一譯碼 編碼輸出碼 字的個數(shù) KL/L 是平均每個信源符號所需要的碼元符號個數(shù) 編碼后平均每個信源符號能載荷的最大信息量為： 定長編碼定理 在定長編碼中， K=KL 是定值，且為唯一可譯碼。 例 : 英文電報符號， n =27 ， L =1 ， m =2( 二元編碼 ) log 2 n ????? = log 2 27 ≈ 5 每個英文電報符號至少 log 2 m 要用 5位二元符號編碼 ? 實際英文電報符號信源，平均每個英文電報符號所 提供的信息量約等于 比特，大大小于 5 比特。定長編碼的信息傳輸效率極低 當(dāng)考慮信源符號出現(xiàn)的概率及符號間的依賴關(guān)系后 （考慮信源的冗余度），在定長編碼中每個信源符 號平均所需的 碼長可以減少。 定長編碼定理 ? 編碼器的平均輸出信息率 ? 對于二進(jìn)制編碼，每個信源符號必須 輸出的碼長 定長編碼定理說明： 只要碼字所能攜帶的信息量大于信源序列輸出的 信息量，則可以使傳輸幾乎無失真，當(dāng)然條件是 L足夠大。 當(dāng) 時，則為臨界狀態(tài)，可能無失真， 也可能有失真。即： ?當(dāng)信源序列長度 L 滿足 能達(dá)到差錯率要求： ?? 編碼效率 編碼效率總 定義編碼效率為： ?是小于 1 信源的平均符號熵為 HL (X) ，采用平均符號碼長 為 K 來編碼后所得的效率。 例： 設(shè)離散無記憶信源概率空間為 ? 信源熵： H ( X ) = ∑ p ( xi ) log p ( xi ) = bit / 符號 i = 1 對信源符號采用定長二元編碼 , 要求編碼效率 η為 90 ％ 若取 L ＝ 1 ，則 即每個符號用 進(jìn)行定長編碼，共有 = 種 可能，按 7 種可能性計算，信源符號中就有一種符號 沒有對應(yīng)的碼字，取概率最小的 a8 ，則 Pe= , 太大 ? 信源序列的自信息方差： 若要求譯碼錯誤概率 δ ≤ 106 L?應(yīng)滿足： ?對于定長編碼，即使在編碼效率和譯碼錯誤概率的要 求并不十分苛刻的情況下，就需要 10 8 個信源符號一 起進(jìn)行編碼。 變長編碼定理 在變長編碼中，碼長 KL是變化的。（統(tǒng)計匹配） 編碼后碼字 Y1 , Y 2 , ‥ , Y n 碼長分別為 K 1 , K 2 , ‥ , K n 碼的 平均長度 為： 編碼后的 信息傳輸率 為： 對于某一信源和某一碼符號集，若有一個唯一可譯 碼，其平均長度小于所有其他唯一可譯碼的平均長 度，則稱該碼為最佳碼（緊致碼）。 無失真變長信源編碼定理（ 香農(nóng)第一定理 ） 對于平均符號熵為 HL(X) 的離散平穩(wěn)無記憶信源（離散 無記憶信源 X 的 L 次擴(kuò)展信源 對其進(jìn)行 m 元編碼，必存在一種無失真編碼方法，構(gòu) 成唯一可譯碼，使信源 X 中每個信源符號所需的平均碼 長 滿足： 用變長編碼可達(dá)到相當(dāng)高的編碼效率，一般所要求 的符號長度 L 可以比定長編碼小得多。而用變長碼編碼時， L 不需要很大就可 達(dá)到相當(dāng)高的編碼效率，而且可實現(xiàn)無失真編碼。編碼后的傳輸率 R 也越來越接近于無噪無損 二元對稱信道的信道容量 (1bit/ 二元碼符號 ) ，達(dá)到信 源與信道的匹配。 編碼主要方法有：香農(nóng)編碼、費諾編碼、哈夫曼 編碼等。因此，香 農(nóng)編碼的實用價值不大，但卻有深遠(yuǎn)的理論意義，因 為按香農(nóng)的方法對信源序列編碼，當(dāng)序列長度趨于無 窮時，平均碼長會趨于信源的熵。 香農(nóng)第一定理指出，選擇每個碼字的長度 K
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1