有噪信道編碼定理.ppt

2020 2 14 1 17 理信學院孫桂萍 有噪信道編碼定理 2020 2 14 2 17 理信學院孫桂萍 主要內(nèi)容 錯誤概率和譯碼規(guī)則最大后驗概率準則最大似然譯碼準則錯誤概率與編碼方法最小距離譯碼準則 2020 2 14 3 17 理信學院孫桂萍 信道編碼的目的 從信道編碼的構造方法看 信道編碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼中加入一些人為多余的碼元 以保證傳輸過程可靠性 信道編碼的任務就是構造出以最小的冗余度代價換取最大抗干擾性能的 好碼 2020 2 14 4 17 理信學院孫桂萍 信道的統(tǒng)計特性 錯誤概率與信道的統(tǒng)計特性有關 而信道的統(tǒng)計特性可由信道的傳遞矩陣描述 二元對稱信道 錯誤的傳遞概率為p 正確的為1 p 信道矩陣 2020 2 14 5 17 理信學院孫桂萍 錯誤概率不僅與信道的統(tǒng)計特性有關 還與接收端的譯碼規(guī)則有關 譯碼規(guī)則a 收到 0 譯成 0 收到 1 譯成 1 在規(guī)則a確定的情況下 錯誤概率為 發(fā)送 0 收到 0 譯成 0 正確的譯碼 譯碼正確的概率為1 3 發(fā)送 0 收到 1 譯成 1 錯誤的譯碼 譯碼錯誤的概率為2 3 錯誤概率與譯碼規(guī)則的關系 2020 2 14 6 17 理信學院孫桂萍 因為是對稱信道 那么發(fā)送 1 錯譯成 0 的概率也為2 3 在此譯碼規(guī)則下 平均錯誤概率 PE這里 假設輸入端等概率分布 2020 2 14 7 17 理信學院孫桂萍 譯碼規(guī)則b 收到 0 譯成 1 收到 1 譯成 0 在規(guī)則b確定的情況下 錯誤概率為 發(fā)送 0 收到 1 譯成 0 正確的譯碼 譯碼正確的概率為2 3 發(fā)送 0 收到 0 譯成 1 錯誤的譯碼 譯碼錯誤的概率為1 3 在此譯碼規(guī)則下 平均錯誤概率 PE 可見 譯錯的可能性減少 譯對的可能性增加了 2020 2 14 8 17 理信學院孫桂萍 譯碼規(guī)則 數(shù)學定義 設離散單符號信道的輸入符號集為A ai i 1 2 r 輸出符號集為B bj j 1 2 s 制定譯碼規(guī)則就是設計一個函數(shù)F bj 它對于每一個輸出符號bj確定一個唯一的輸入符號ai與其對應 每一個輸入符號可以對應于多個輸出符號 也就是s個輸出符號中的每一個都可以譯成r個輸入符號中的任何一個 所以共有rs種譯碼規(guī)則 2020 2 14 9 17 理信學院孫桂萍 譯碼規(guī)則舉例 例6 1 有一離散單符號信道 信道矩陣為 針對于這種信道 設計兩種譯碼規(guī)則 2020 2 14 10 17 理信學院孫桂萍 平均錯誤概率 譯碼規(guī)則的選取原則是使得平均錯誤概率盡可能小 在確定了譯碼規(guī)則F bj 后 若收到的為bj 譯成ai 發(fā)送的是ai 正確收到的為bj 譯成ai 發(fā)送的不是ai 錯誤條件正確概率為 條件錯誤概率為 2020 2 14 11 17 理信學院孫桂萍 平均錯誤概率 平均錯誤概率PE應是條件錯誤概率對所有的Y求統(tǒng)計平均 為了是PE盡可能的小 對于 右側的每個求和項都是非負的 所以應使得每個項盡量的小 而且譯碼規(guī)則只影響條件錯誤概率 對P bj 沒有影響 所以應選取譯碼規(guī)則使得條件錯誤概率盡量的小 那么也就是尋找條件正確概率盡量的大 2020 2 14 12 17 理信學院孫桂萍 最大后驗概率準則 數(shù)學描述選擇譯碼函數(shù) 并使之滿足條件 文字描述采用一個譯碼函數(shù) 它對于每一個輸出符號均譯成具有最大后驗概率的那個輸入符號 則信道錯誤概率能達到最小 這種譯碼規(guī)則稱為最大后驗概率準則或最小錯誤概率準則 2020 2 14 13 17 理信學院孫桂萍 最大后驗概率準則另一種描述 因為一般已知傳遞概率和輸入符號的先驗概率 所以將根據(jù)貝葉斯定律改寫為 一般P bj 不等于0 最大后驗概率可表示為 選擇譯碼函數(shù) 使?jié)M足 1式 2020 2 14 14 17 理信學院孫桂萍 最大似然譯碼準則 若輸入符號的先驗概率均相等 則1式可寫為 數(shù)學描述 選擇譯碼函數(shù) 并滿足 文字描述選擇譯碼函數(shù) 收到bj后 譯成信道矩陣P的第j列中最大那個元素所對應的信源符號 注意 最大似然譯碼準則對于先驗概率等概率分布時才可使得錯誤概率PE最小 2020 2 14 15 17 理信學院孫桂萍 平均錯誤概率的計算 求和 可先列后行或先行后列 也就是說對于聯(lián)合概率矩陣中可先求每列中除去所對應的以外所有元素 再對各列求和 也可以先對行i求和 除去譯碼規(guī)則中所對應的 然后再對各行求和 2020 2 14 16 17 理信學院孫桂萍 平均錯誤概率的計算 如果先驗概率是等概率的 則PE為 2020 2 14 17 17 理信學院孫桂萍 例題6 2 已知信道矩陣如下 根據(jù)最大似然譯碼選取譯碼規(guī)則 并計算平均錯誤概率 若輸入不等概 概率分別為1 4 1 4 1 2 比較按照最大似然譯碼準則和最大后驗概率準則選取的譯碼規(guī)則的PE 2020 2 14 18 17 理信學院孫桂萍 費諾不等式 平均錯誤概率與譯碼規(guī)則有關 而譯碼規(guī)則又由信道特性決定 由于錯誤的存在 所以當收到某符號后對發(fā)送端仍存在不確定性 可見 PE與信道疑義度有關 費諾不等式 2020 2 14 19 17 理信學院孫桂萍 對于此二元對稱信道 假設等概 可以利用最大似然譯碼準則選取譯碼規(guī)則 使得PE盡量的小 F b1 a1F b2 a2注 b1 a1 0 b2 a2 1PE 0 5 0 01 0 5 0 01 0 01一般要求在 6到 9數(shù)量級上 錯誤概率與編碼方法的關系 0輸入1 0輸出1 p 0 99 p 0 01 二元對稱信道 0 01 0 99 例1 2020 2 14 20 17 理信學院孫桂萍 碼一 重復編碼將待發(fā)送的消息碼重復發(fā)送幾遍 可以減小錯誤的發(fā)生 提高可靠性 例如 重發(fā)三次 n 3輸入序列 i 輸出序列 j 000 許用碼字 000001001010010011011100100101101110110111 許用碼字 111 輸出序列8種可能 每一位都可能出錯 2020 2 14 21 17 理信學院孫桂萍 碼一 重復編碼 n 3 的PE利用最大似然譯碼準則選取譯碼規(guī)則時需要知道信道矩陣 可計算得 依據(jù)最大似然譯碼準則 應選取信道矩陣的每列中最大的那個傳遞概率對應的輸入符號即為該列對應的輸出要譯成的輸入符號 在此規(guī)則下求出PE 與發(fā)送單個符號相比 平均錯誤概率減小了兩個數(shù)量級 2020 2 14 22 17 理信學院孫桂萍 重復編碼可以使平均錯誤概率減小的原因重復編碼三次時 1 000 對應的輸出序列為 1 000 2 001 3 010 5 100 與 1比較之后可發(fā)現(xiàn) 或是相同 或是發(fā)生了一位錯誤 但是譯碼的結果都是正確的 降低了譯錯的可能性 平均錯誤概率減小了 若繼續(xù)增大n PE可逐漸減小 n可以無限增大嗎 2020 2 14 23 17 理信學院孫桂萍 答案是否定的 n不可以無限量增大因為n增大的同時 會降低信息傳輸率編碼后的信道的信息傳輸率R logM n 比特 碼符號 M不變的情況下 n增大 R變小所以不能為了使平均錯誤概率降低而一味的增大n 尋找好的編碼方法的思路 找到一種編碼方法 使PE相當?shù)?但R能保持在一定水平 2020 2 14 24 17 理信學院孫桂萍 碼二 將8個符號均作為許用碼字傳送M 8 logM 3 R logM n 3 3 1同樣利用最大似然譯碼準則選取譯碼規(guī)則 并可求得PE 3 10 2 比10 2還大 可發(fā)現(xiàn) 在二元信道的n次擴展信道中有2n個輸入 從中取出M個做許用碼字 M大 PE大 R大 M小 PE小 R小 2020 2 14 25 17 理信學院孫桂萍 碼三 在這個二元三次擴展信道中 取M 4再比較一下PE和R取 000 011 101 110 PE 2 10 2 R 2 3 與M 8比較都變小了 從8個中取4個有70種方法 選兩組比較一下 比較一下兩組碼的特點 分析為什么第 組的平均錯誤概率大 2020 2 14 26 17 理信學院孫桂萍 碼四 M 4 n 5 從二元五次擴展信道中32個輸入符號中取4個 再比較一下PE和RR log4 5 2 5 PE 7 8 10 4 結論 增大了n 并適當?shù)脑龃驧及合適的編碼方法 即可達到希望的結果 重點比較一下M 4 n 3的情況 R略降 但PE卻減少很多 2020 2 14 27 17 理信學院孫桂萍 漢明距離 碼字對應位置上不同碼元的個數(shù)D i j 兩個二元碼字Ci和Cj的距離等于對應位置上碼元的模二和 碼C的最小距離 這個碼C中 任意兩個碼字的漢明距離的最小值dmin 碼字距離 2020 2 14 28 17 理信學院孫桂萍 2020 2 14 29 17 理信學院孫桂萍 最小距離譯碼準則 選擇譯碼函數(shù) 使?jié)M足 即滿足 注意 二元對稱信道中最小距離譯碼準則等于最大似然譯碼準則 文字描述 二元信道中最大似然譯碼準則可表述為 當收到 j后 譯成與之距離最近的輸入碼字 2020 2 14 30 17 理信學院孫桂萍 總結編碼 應采用選擇M個消息所對應的碼字之間最小距離dmin盡