【正文】 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 信息傳輸?shù)目垢蓴_性 信道及信道容量 信道編碼 二元線性碼 線性碼的編碼與譯碼 循環(huán)碼 循環(huán)碼的編碼與譯碼 抗干擾信道編碼定理 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 信道的一般數(shù)學(xué)模型 信道及信道容量 YXP ( Y | X ) 其中 X表示輸入， Y表示輸出，條件概率 P(Y|X)表示它們之間的統(tǒng)計(jì)依賴關(guān)系（稱為轉(zhuǎn)移概率分布）。這個(gè)數(shù)學(xué)模型也可以寫作 { X P(Y|X) Y}。 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 信道矩陣 設(shè)輸入 X的符號(hào)表是 {a1, a2, …, a n}，輸出 Y的符號(hào)表是 {b1, b2, …, b m}。將 P(Y|X)用如下矩陣的方式表示： 稱為該信道的信道矩陣。其中行表示輸入 X，列表示輸出 Y，p(bj|ai)（ i = 1,…, n j = 1,…, m ） 表示輸入是 ai，輸出是 bj的條件概率。 1 1 2 1 11 2 2 2 212( | ) ( | ) ( | )( | ) ( | ) ( | )( | ) ( | ) ( | )mmn n m np b a p b a p b ap b a p b a p b ap b a p b a p b a???????? 信道及信道容量 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 互信息公式： 互信息表示當(dāng)收到 bj后 ， 可以提取到的關(guān)于 ai的信息量。 上式稱 I(X。 Y) 是 Y 對(duì) X 的平均互信息量，簡稱平均互信息。平均互信息 I(X。 Y) 克服了互信息的隨機(jī)性，成為一個(gè)確定的量，因此可以作為信道中信息流通的測度。 信道及信道容量 ( | )( 。 ) l o g()jiijjp b aI a bpb?11( | )( 。 ) ( ) l o g()nm jiijij jp b aI X Y p a bpb??? ??管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 假設(shè)信源 X 的熵為 H(X)，我們希望在信道輸出端接收到的信息量就是 H(X)，但由于干擾的存在，一般情況下只能接收到 I(X。 Y)。它是平均意義上每傳送一個(gè)符號(hào)流經(jīng)信道的信息量。 可以把 I(X。 Y)理解為信道的信息傳輸率（或信息率） : R = I ( X。 Y ) 信道及信道容量 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 由于 I( X。Y ) 是信源概率分布 P(X) 和信道轉(zhuǎn)移概率分布 P(Y|X) 的函數(shù)。給定一個(gè)信道，其 P(Y|X) 是固定的，因此， I(X。Y) 隨信源概率分布 P(X) 的變化而變化，調(diào)整 P(X)，在接收端就能獲得不同的信息量。 而總能找到某一種 P(X)（即某一種信源），使信道所能傳送的信息率達(dá)到最大。定義這個(gè)最大的信息傳輸率為信道容量，記為 C。 C = max R = max I(X。Y) 信道及信道容量 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 有時(shí)我們關(guān)心的是信道在單位時(shí)間內(nèi)能夠傳輸?shù)淖畲笮畔⒘?。若信道平均傳輸一個(gè)符號(hào)需要事件 t，則單位時(shí)間的信道容量為 Ct的單位是比特 /秒，用 bit/s表示。 Ct 實(shí)際上是信道的最大信息傳輸速率。 信道及信道容量 ? ?1 m a x 。tC I X Yt?管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ?二元對(duì)稱傳送 ?檢錯(cuò)與糾錯(cuò)原理 ?極大似然譯碼法 信道編碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 二元數(shù)字信息：是用二元數(shù)域 F2={0,1}中的數(shù)字 0與 1組成的數(shù)組或向量 ?F2中的 加法運(yùn)算： 0+0=1+1=0， 0+1=1+0=1 ?F2中的 乘法運(yùn)算： 11=1， 10=01=00=0 通常用同樣長度的二元數(shù)組代表一個(gè)信息集合中的信息。 如前文的英文字母示例。 信道編碼 ：二元對(duì)稱傳送 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ?如果在傳送過程中，傳送任何一個(gè)信息是否發(fā)生錯(cuò)誤與前面已傳送的信息是否發(fā)生了錯(cuò)誤無關(guān)，則稱這種傳送為 無記憶傳送 。 ?在無記憶傳送過程中，如果發(fā)送 1收到 0的概率與發(fā)送 0收到 1的概率都是 p，且發(fā)送 1收到 1的概率與發(fā)送 0收到 0的概率都是 1p，即 錯(cuò)誤傳送的概率為 p，正確傳送概率為 1p，則稱這種傳送為二元對(duì)稱傳送。 一般 p遠(yuǎn)小于 1/2。 二元對(duì)稱傳送 信道編碼 ：二元對(duì)稱傳送 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ? 抗干擾編碼 ： 數(shù)字信息在傳送過程中會(huì)受到各種可能的干擾而出現(xiàn)錯(cuò)誤，這樣收到的信息可能就不是傳送的原信息。抗干擾的有效做法是在采用種種技術(shù)措施的同時(shí)，在信息傳送前進(jìn)行一次抗干擾編碼，再傳送抗干擾編碼后的數(shù)字信息。 ? 抗干擾編碼有 檢錯(cuò)編碼 與 糾錯(cuò)編碼 ，檢錯(cuò)編碼是檢查有無錯(cuò)誤發(fā)生的編碼，糾錯(cuò)編碼是能糾正已發(fā)生錯(cuò)誤的編碼。 信道編碼 ：檢錯(cuò)與糾錯(cuò)原理 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ? 例 (奇偶校驗(yàn)碼 )： 設(shè)原信息是長為 5的二元向量，在傳送前編碼如下： ?顯然有 σ(c)的 6個(gè)分量之和為 0。傳送 σ(c)，設(shè)收到的向量是r=(r0,r1,r2,r3,r4,r5)，則 : 若 ，則在傳送過程中一定發(fā)生了錯(cuò)誤，且有奇數(shù)個(gè)分量發(fā)生了錯(cuò)誤；否則傳送過程可能沒有發(fā)生錯(cuò)誤，也可能發(fā)生了偶數(shù)個(gè)錯(cuò)誤。 40 1 2 3 40( ) , , , , , iic c c c c c c????? ???? ?500iir??? 信道編碼 ：檢錯(cuò)與糾錯(cuò)原理 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 定義 設(shè)原信息集合是 F2上 k 維向量組成的向量空間 Vk， σ是 Vk到 Vn 的一個(gè)單射 (nk)，則稱 Vk 的全體象 C = σ(Vk) 為碼， C中的每一個(gè) n 維向量為 碼字 ，碼字的分量稱為 碼元。 如果任一碼字在傳送過程中有 ≤ t 個(gè)錯(cuò)誤發(fā)生，而收信方可以檢查出有無錯(cuò)誤發(fā)生，則稱這個(gè)碼 C 可以檢查 t 個(gè)差錯(cuò)的 檢錯(cuò)碼 ，并稱 σ為 檢錯(cuò)編碼 ；如果收信方可以從收到的字正確譯出發(fā)送方發(fā)送的碼字，則稱碼 C 是可以糾正 t 個(gè)差錯(cuò)的 糾錯(cuò)碼 ，并稱 σ為 糾錯(cuò)編碼 。稱 k 為信息長度， n 為碼長， k/n 為碼 C的信息率。 信道編碼 ：檢錯(cuò)與糾錯(cuò)原理 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 示例 5維原信息 (數(shù)組信息 ) 編碼 (1位奇偶校驗(yàn)碼 ) 6維編碼信息 00000 0 000000 00001 1 000011 … … … 11010 1 110101 11011 0 110110 11100 1 111001 11101 0 111010 11110 0 111100 11111 1 111111 k=5 n=6 碼空間 Vn 碼字 碼元 原信息空間 Vk 映射 ? 信道編碼 ：檢錯(cuò)與糾錯(cuò)原理 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ? 如果 p = ，從統(tǒng)計(jì)意義上講，每發(fā)送 100個(gè)符號(hào)就可能有一個(gè)錯(cuò)誤產(chǎn)生，這顯然不能滿足傳輸?shù)囊蟆? ? 如果我們把信道輸入符號(hào)重復(fù)傳輸 N次，即對(duì)于信源符號(hào)“ 0”，信道輸入端不只發(fā)一個(gè)“ 0”，而是連續(xù)發(fā) N個(gè)“ 0”；對(duì)于信源符號(hào)“ 1”，信道輸入端不只發(fā)一個(gè)“ 1”，而是連續(xù)發(fā) N個(gè)“ 1”。 ? 則輸入 {0, 1}變?yōu)?( 00…0, 11…1 ) ，輸出則從 {0, 1}變?yōu)?N維空間中的某個(gè)向量。 重復(fù)編碼 信道編碼 ：檢錯(cuò)與糾錯(cuò)原理 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ? 若 N=3，則 單符號(hào)離散無記憶信道的信道矩陣為 轉(zhuǎn)變?yōu)殡x散無記憶信道的三次擴(kuò)展信道的信道矩陣 ???????ppppP10