信息論中的有噪信道編碼

信息論中的有噪信道編碼2023/6/27信息論中的有噪信道編碼25.1錯誤概率和譯碼規(guī)則編碼信道2023/6/27信息論中的有噪信道編碼3正確概率通信過程不是在信道輸出端結(jié)束，要經(jīng)過譯碼到達收信者，所以譯碼過程和譯碼規(guī)則對錯誤概率有影響2023/6/27信息論中的有噪信道編碼4圖5.1二元對稱信道設(shè)輸入等概，收到0，譯為0，譯對概率為，譯錯概率為收到0，譯為1，收到1，譯為0，譯對概率為，譯錯概率為結(jié)論錯誤概率與信道統(tǒng)計特性有關(guān)，與譯碼規(guī)則有關(guān)2023/6/27信息論中的有噪信道編碼5XYa1a2arb1b2bsp(bj/ai)譯碼函數(shù)定義譯碼規(guī)則2023/6/27信息論中的有噪信道編碼6rs種譯碼規(guī)則2023/6/27信息論中的有噪信道編碼7兩種典型的譯碼規(guī)則

譯碼規(guī)則選擇的一個很自然的規(guī)則就是錯誤概率最小若定義收到bj后就一定譯為ai

，若發(fā)送的是ai

，就認為正確2023/6/27信息論中的有噪信道編碼8平均錯誤概率如何使平均錯誤概率最?。孔畲蠛篁灨怕蕼蕜t最小錯誤概率準則2023/6/27信息論中的有噪信道編碼9一般是已知：根據(jù)貝葉斯公式：一般：選擇2023/6/27信息論中的有噪信道編碼10如果都相等上式：這樣定義的譯碼規(guī)則稱為最大似然譯碼規(guī)則最大似然譯碼規(guī)則不依賴于先驗概率，但當(dāng)先驗概率為等概時，它使平均錯誤概率最小2023/6/27信息論中的有噪信道編碼11上式中求和號表示對輸入符號集X中除以外的所有元素求和

2023/6/27信息論中的有噪信道編碼12正確概率上式在聯(lián)合矩陣先求每列除去所對應(yīng)的以外所有元素之和，然后再對各列求和。也可在聯(lián)合矩陣中先對行i求和，除去譯碼規(guī)則中所對應(yīng)的然后再對行求和2023/6/27信息論中的有噪信道編碼13輸入ai引起的錯誤概率如果先驗概率是等概2023/6/27信息論中的有噪信道編碼14例題已知信道則設(shè)計的最大似然譯碼規(guī)則：設(shè)輸入等概，則錯誤概率：信道矩陣中每列取大值2023/6/27信息論中的有噪信道編碼15設(shè)輸入不等概，p(a1)=1/4,p(a2)=1/4,p(a3)=1/2

則設(shè)計的最小錯誤概率譯碼規(guī)則為：聯(lián)合矩陣中每列取大值2023/6/27信息論中的有噪信道編碼16=(1/8+1/24)+(1/12+1/12)+(1/12+1/24)=11/24

輸入不等概時，最大似然譯碼規(guī)則的平均錯誤概率不是最小2023/6/27信息論中的有噪信道編碼175.2錯誤概率與編碼方法

圖二元對稱信道

（輸入等概）2023/6/27信息論中的有噪信道編碼182023/6/27信息論中的有噪信道編碼19則最大似然譯碼規(guī)則：擇多譯碼2023/6/27信息論中的有噪信道編碼20顯然，重復(fù)更多次，錯誤概率會更小消息傳輸率（碼率）：比特/碼符號

比特/秒

M是輸入消息符號的個數(shù)

2023/6/27信息論中的有噪信道編碼21（重復(fù)三次），M=2比特/碼符號

（重復(fù)五次），M=2比特/碼符號

如何使得錯誤概率相當(dāng)?shù)?，而R卻保持在一定水平？從理論上講，這時可能的，即香農(nóng)第二定理，有噪信道編碼定理2023/6/27信息論中的有噪信道編碼22N＝3，輸入端有8個消息，選擇2個消息，即M=2，這樣每個消息攜帶平均信息量仍為1比特，而傳送一個消息需要付出三個二元符號，所以R下降到1/3而輸入端8個消息都作為消息發(fā)送，R＝1，錯誤概率卻又降低了輸入端有2n符號序列可作為消息，如果選擇其中的M個作為消息，則M大些，PE也跟著大，R也大，則M小些，PE也跟著小，R也小，2023/6/27信息論中的有噪信道編碼23圖N次擴展信道的消息符號2023/6/27信息論中的有噪信道編碼24在三次擴展信道中，取M=4作為消息符號第I種選法第II種選法000000011001101010110100按照最大似然譯碼規(guī)則第I種選法PE=2×10－2

第II種選法PE×10－2

2023/6/27信息論中的有噪信道編碼25選擇M=4，n＝5，2023/6/27信息論中的有噪信道編碼262023/6/27信息論中的有噪信道編碼27這與M=4，n=3兩中編碼方法比較，R略為下降一些，錯誤概率卻小得多漢明距離碼的最小距離：2023/6/27信息論中的有噪信道編碼28

碼A碼B碼C碼D碼E碼

字00011100001110111000000110001000000011011011111010000001010011100101110111消息數(shù)M24448碼的最小距離32131信息傳輸率R(比特/碼符號)1/32/32/32/51錯誤概率(最大似然譯碼規(guī)則)310-4210-22.2810-27.810-4310-22023/6/27信息論中的有噪信道編碼29最大似然譯碼規(guī)則：滿足越大，越小越小，越大2023/6/27信息論中的有噪信道編碼30最大似然譯碼規(guī)則用漢明距離表示為：最小距離譯碼準則在二元對稱信道中，最小距離譯碼準則等于最大似然譯碼規(guī)則2023/6/27信息論中的有噪信道編碼31在有噪信道中，錯誤概率與編碼、譯碼規(guī)則有關(guān)，編碼可采用選擇M個消息，使之對應(yīng)的碼字最小距離盡可能最大的編碼方法；譯碼采用將接受符號序列譯為距離最近的碼字，則碼長足夠長時，合適的選擇M，可使錯誤概率很小，而信息傳輸率保持不變2023/6/27信息論中的有噪信道編碼325.3有噪信道編碼定理

香農(nóng)第二定理證明方法包含的思路：允許平均錯誤概率任意小；連續(xù)使用信道許多次；在n次無記憶擴展信道中討論，使大數(shù)定律有效；隨機選取碼書，證明有一種好碼存在2023/6/27信息論中的有噪信道編碼33有噪信道編碼定理：設(shè)離散無記憶信道[X,p(y|x),Y],p(y|x)為信道傳遞概率，其信道容量為C，當(dāng)信息傳輸率R<C時，只要碼長足夠長，總可以在輸入Xn符號中找到M＝2nR個碼字，構(gòu)成一組碼（2nR

，n）和相應(yīng)的譯碼規(guī)則，使譯碼的錯誤概率任意?。≒E

－>0）2023/6/27信息論中的有噪信道編碼34有噪信道編碼逆定理：設(shè)離散無記憶信道[X,p(y|x),Y],p(y|x)為信道傳遞概率，其信道容量為C，當(dāng)信息傳輸率R>C時，無論碼長多長，總也找不到一組碼（2nR

，n）和相應(yīng)的譯碼規(guī)則，使譯碼的錯誤概率任意小（PE

－>0）2023/6/27信息論中的有噪信道編碼355.4糾錯碼基本思想和漢明碼處理差錯的兩種基本策略：糾錯碼和檢錯碼糾錯碼：在每一個要發(fā)送的數(shù)據(jù)塊上附加足夠的冗余信息，使接受方能夠推導(dǎo)出已發(fā)出的字符應(yīng)該是什么。檢錯碼：只加入足夠的冗余位，使接受方知道有差錯發(fā)生，但不知錯誤所在，然后，要求發(fā)送方重傳。碼字：通常一幀包括m個數(shù)據(jù)位和r個校驗位或冗余位，整個長度為n位,(n=m+r)則此長度為n的單元被稱為n位碼字。2023/6/27信息論中的有噪信道編碼36漢明距離：兩個碼字中不同的位的個數(shù)該概念的重要性：兩個碼字具有漢明距離d，則需要d個位差錯才能將其中一個碼字轉(zhuǎn)換成另一個。一種編碼的校驗和糾錯能力取決于它的漢明距離。2023/6/27信息論中的有噪信道編碼37從功能角度：檢錯碼、糾錯碼對信息序列的處理方法：分組碼、卷積碼碼元與原始信息位的關(guān)系：線性碼、非線性碼差錯類型：糾隨機差錯碼、糾突發(fā)差錯碼、介于中間的糾隨機/突發(fā)差錯碼。構(gòu)碼理論：代數(shù)碼、幾何碼、算術(shù)碼、組合碼等糾錯碼分類2023/6/27信息論中的有噪信道編碼38碼字的漢明重量非零碼元個數(shù)，二元碼中指含“1”的個數(shù)漢明距離滿足：對稱性；非負性；距離三角不等式2023/6/27信息論中的有噪信道編碼39定義E＝(en－1,…,e1,e0)＝R－C

＝(rn-1－cn-1,…,r1－c1,r0－c0)二進制碼中模2加與模2減是等同的，因此有E=R＋C及R=C＋E 錯誤圖樣E（差錯圖案E）ei取0，表示該碼元無錯C=RE

，差錯圖樣中的“１”既是符號差錯也是比特差錯。2023/6/27信息論中的有噪信道編碼40若BSC信道的差錯概率是p，則長度n的碼中錯誤概率：

0個錯1個錯2個錯…n個錯

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

由于p<<1,>>>>>>…>>

出錯越少的情況，發(fā)生概率越大，E的重量越輕，2023/6/27信息論中的有噪信道編碼41分組碼糾正隨機錯誤能力與碼書中最小距離關(guān)系碼集各碼字間的距離是不同的，碼距最小者決定碼的特性，稱之為最小距離dmindmin=3，糾錯能力是1，檢錯能力是22023/6/27信息論中的有噪信道編碼422023/6/27信息論中的有噪信道編碼43要發(fā)現(xiàn)（檢測）e個隨機錯誤，要求：2023/6/27信息論中的有噪信道編碼44要糾正e個隨機錯誤，要求：2023/6/27信息論中的有噪信道編碼45要糾正e個錯誤，同時檢測到f個隨機錯誤，要求：2023/6/27信息論中的有噪信道編碼46常用的檢、糾錯碼奇偶檢驗碼行列奇偶檢驗碼1101001010110001011011000010011110011001

10110001

行監(jiān)督元列監(jiān)督元發(fā)送順序1101001010110001…2023/6/27信息論中的有噪信道編碼47等比碼檢驗碼字中含“1”和“0”個數(shù)之比如：3：2等比碼，“1”－>3個，

“0”

－>2個，5中取3碼2023/6/27信息論中的有噪信道編碼48在（n,k）線性分組碼中，n－碼長，k－信息位，也就是自空間的維數(shù)。設(shè)M=(m1,m2,…mk)是輸入糾錯碼編碼器的信息組，輸出碼字cc＝mG1×n1×k

k×n

碼字消息生成矩陣G建立了消息與碼字矢量間的一一對應(yīng)關(guān)系，C的每一位都是消息數(shù)字的線性組合2023/6/27信息論中的有噪信道編碼492023/6/27信息論中的有噪信道編碼50G1=

101011110101111000G2=

100110010011001100消息用G1得到的碼字用G2得到的碼字0000000000000000011110000011010101101010100110110011010111101001010111001101010100111010111100111101101011111001101110002023/6/27信息論中的有噪信道編碼51上表所示碼字，雖然用不同的生成矩陣得到，但屬于同一個（n,k）碼的碼字空間，檢、糾錯能力一樣。G2生成是碼字，其前k位與消息位完全相同，這種碼稱為系統(tǒng)碼，否則稱為非系統(tǒng)碼2023/6/27信息論中的有噪信道編碼52想要保證(n,k)線性分組碼能夠構(gòu)成k維n重子空間，G的k個行矢量gk,…,g2,g1必須是線性無關(guān)的，只有這樣才符合作為基底的條件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一碼集，但因編碼涉及碼集和映射兩個因素，碼集一樣而映射方法不同也不能說是同樣的碼。2023/6/27信息論中的有噪信道編碼53若通過行運算和列置換能將兩個生成矩陣G互等，則稱這兩個G等效。非系統(tǒng)碼的G可通過運算轉(zhuǎn)變?yōu)橄到y(tǒng)碼的G。等效的兩個G生成的兩個(n,k)線性碼也是等效的。因此，每個(n,k)線性碼都可以和一個系統(tǒng)的(n,k)線性碼等效。2023/6/27信息論中的有噪信道編碼54系統(tǒng)形式的生成矩陣(n,k)碼的任何生成矩陣都可以通過行運算（以及列置換）簡化成“系統(tǒng)形式”。G=[Ik

P]Ik是k×k單位矩陣，P是k×(n-k)矩陣。2023/6/27信息論中的有噪信道編碼55在線性分組碼（n,k）中因為監(jiān)督元和信息位之間是線性關(guān)系，所以每個碼字中r(=n-k)和信息位之間關(guān)系為：

HCT=0T

或CHT=0H稱為（n,k）線性碼的一致監(jiān)督矩陣2023/6/27信息論中的有噪信道編碼56把H實行初等行變換和列置換，將H的后r列化為單位子矩陣，則H實行初等行變換和列置換，后r列為單位子矩陣的H稱為監(jiān)督矩陣的標(biāo)準形式H=[QIr]2023/6/27信息論中的有噪信道編碼57G和H之間關(guān)系：由于G中的每一行都是一個碼字，所以G每行滿足監(jiān)督關(guān)系式HCT=0T

，則有

HGT=0T

或GHT=0將H=[QIr]和G=[Ik

P]代入上式，得到

P=QT或PT=QG和H行矢量彼此正交得到G=[Ik

P]=[Ik

QT]2023/6/27信息論中的有噪信道編碼58漢明碼漢明碼不是指一個碼，而是代表一類碼。漢明碼的糾錯能力t=1，既有二進制的，也有非二進制的。二進制時，漢明碼碼長n和信息位k服從以下規(guī)律：(n,k)=(2m-1,2m-1-m)

其中m=n-k，是正整數(shù),n－碼長，k－信息位，r－監(jiān)督位，d－最小距離。當(dāng)m＝3、4、5、6、7、8…時，有漢明碼(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)…。2023/6/27信息論中的有噪信道編碼59

漢明碼的校驗矩陣H具有特殊的性質(zhì)，能使構(gòu)造方法簡化。一個(n,k)碼的校驗矩陣有n－k行和n列，二進制時n-k個碼元所能組成的列矢量總數(shù)是2n-k-1,恰好和校驗矩陣的列數(shù)n=2m-1相等。只要排列所有列，通過列置換將矩陣H轉(zhuǎn)換成系統(tǒng)形式，就可以進一步得到相應(yīng)的生成矩陣G。漢明碼H中任意兩列線性無關(guān)，且沒有全零列2023/6/27信息論中的有噪信道編碼60例6.4構(gòu)造一個m=3的二元(7，4)漢明碼。解：先利用漢明碼的特性構(gòu)造一個(7，4)漢明碼的校驗矩陣H，再通過列置換將它變?yōu)橄到y(tǒng)形式：

0001111列置換0111100 H= 0110011 1011010=[PT

I3] 1010101 1101001再得生成矩陣G為

1000011 G=[I4

P]=0100101 0010110 0001111 2023/6/27信息論中的有噪信道編碼61H矩陣各列位置調(diào)動后，相當(dāng)于碼字各個分量次序作了相應(yīng)的變動，不過只是形式不同，碼字重量分布不同，檢糾錯能力一樣H矩陣各列位置調(diào)動，不改變各列之間的相關(guān)性H各列排列原則上是任意的，應(yīng)用上常兩種：標(biāo)準形式，得到系統(tǒng)碼，＝>GR重二進制按所代表的十進數(shù)次序排列2023/6/27信息論中的有噪信道編碼62