第6章有噪信道編碼定理20059

1、第六章 有噪信道編碼第五章結(jié)論：在無噪無損信道上，只要對信源的輸出進行恰當(dāng)?shù)木幋a，總能以信道容量C無差錯地傳輸信息。實際信道都有噪聲干擾。本章研究香農(nóng)第二定理，即通信的可靠性問題。包括：(1)怎么使有噪信道中消息傳輸錯誤最少?(2)在有噪信道中無錯誤傳輸?shù)目蛇_的最大信息傳輸率是什么?了解第六章 有噪信道編碼 第一節(jié) 錯誤概率與譯碼規(guī)則第二節(jié) 錯誤概率與編碼方法第三節(jié) 有噪信道編碼定理第五節(jié)糾錯編碼的基本思想第四節(jié)聯(lián)合信源信道編碼定理第一節(jié) 錯誤概率與譯碼規(guī)則（1）錯誤概率的相關(guān)因素錯誤定義：譯碼輸出不等于信源輸入產(chǎn)生原因：噪聲干擾研究目的：減少錯誤，提高可靠性研究途徑：信道的傳遞矩陣信道統(tǒng)計特

2、性錯誤概率當(dāng)確定了輸入和輸出對應(yīng)關(guān)系后，也就確定了信道矩陣中哪些是正確傳遞概率，哪些是錯誤傳遞概率。通信過程一般并不是在信道輸出端就結(jié)束了，還要經(jīng)過譯碼(或判決)過程才到達消息的終端(收信者)。因此譯碼過程和譯碼規(guī)則對系統(tǒng)的錯誤概率影響很大。了解例：有一個BSC信道，如圖所示 01011/31/32/32/3若收到“0”譯作“0”，收到“1”譯作“1”，則平均錯誤概率為：(0)(1)2(0)(1)3EeePPPPP反之，若收到“0”譯作“1”，收到“1”譯作“0”，則平均錯誤概率為1/3，可見錯誤概率與譯碼準(zhǔn)則有關(guān)。掌握（2）譯碼規(guī)則定義其中F(bj)是單值函數(shù)，即對于每一個輸出符號bj確定一

3、個惟一的輸入符號ai與其對應(yīng)。定義對輸入符號集為i=1,2,r,輸出符號集為i=1,2,s的離散單符號信道，制定譯碼規(guī)則就是設(shè)計一個函數(shù)F(bj)，使得： iAa iBb()jiF ba理解例：0.50.30.20.20.30.50.30.30.4P譯碼規(guī)則的數(shù)目11( )F ba22()F ba33( )F ba和B：11( )F ba23()F ba32( )F ba由于s個輸出符號中的每一個都可以譯成r個輸入符號中的任何一個，所以共有rs種譯碼規(guī)則可供選擇?？梢栽O(shè)計譯碼準(zhǔn)則A：掌握( ()/)(/)jjijP F bbP ab(3)平均錯誤概率在確定譯碼規(guī)則F(bj)=ai 后：若信道輸

4、出端接收到的符號為bj，則譯為ai 若發(fā)送端發(fā)送的是ai則為正確譯碼；否則為錯誤譯碼。收到bj條件下譯碼的正確概率即為發(fā)送端發(fā)送ai的概率： 而錯誤譯碼的概率為收到 后，推測發(fā)出除了 之外其它符號的概率： jbia( /)1(/)jijP e bP ab 條件錯誤概率掌握可以得到平均錯誤譯碼概率為： 它表示經(jīng)過譯碼后平均每收到一個符號所產(chǎn)生錯誤的大小，也稱平均錯誤概率。掌握（4）最小錯誤概率準(zhǔn)則為使 最小，就應(yīng)選擇 為最大，即選擇譯碼函數(shù) 并使之滿足條件： ( ()/)jjP F bb( /)jP e b*()jF ba*(/)(/)jijiP abP abaa這種譯碼準(zhǔn)則稱為“最大后驗概率準(zhǔn)

5、則”或“最小錯誤概率準(zhǔn)則”。收到一個符號以后譯成具有最大后驗概率的那個輸入符號。掌握*(/) ()(/) ( )jjiiP ba P aP ba P a 根據(jù)貝葉斯定律，上式也可以寫成*(/) ()(/) ( )()()jjiijjP ba P aP ba P aP bP b一般P(bj)不等于0，這樣，最大后驗概率準(zhǔn)則就可表示為：掌握當(dāng)信源等概分布時，上式為：*(/)(/)jjiP baP ba 這稱為最大似然譯碼準(zhǔn)則，方法是收到一個 后，在信道矩陣的第j列，選擇最大的值所對應(yīng)的輸入符號作為譯碼輸出。jb（）最大似然譯碼準(zhǔn)則本身不再依賴于先驗概率P(ai) 。但當(dāng)先驗概率為等概率分布時，它使

6、錯誤概率PE最小特點：掌握() ( /)1 ()/ ()EjjjjjYYPP b P e bP F bbP b1 ()jjYP F b b *,()ijjX YYp abP a b,() ()ijjjX YYp abP F b b*,()ijX Y aP ab（）平均錯誤概率的計算掌握按列計算平均錯誤概率求聯(lián)合概率矩陣 P(ai)P(bj|ai) 中每列除去 F(bj)=a* 所對應(yīng)的 P(a*bj) 以外所有元素之和。再對上述結(jié)果求和。 掌握按行計算平均錯誤概率求矩陣 P(ai)P(bj|ai) 各行中 F(bj)=a* 所對應(yīng)的 P(a*bj)以外所有元素之和；然后再對上述結(jié)果求和： 掌握

7、若先驗概率P (ai) = 1/r，有： 即在等先驗概率分布情況下，譯碼錯誤概率可用信道矩陣中的元素P (bj |ai)和（除去每列對應(yīng)于F(bj)=a*的那一項）來表示。 掌握0.50.30.20.20.30.50.30.30.4P根據(jù)最大似然準(zhǔn)則可選擇譯碼函數(shù)為B：112332( )()()F baF baF ba*,11( / )(0.20.3)(0.30.3)(0.20.4)0.56733EY XaPP b a（）例題掌握若采用前邊講到的譯碼函數(shù)A，則平均錯誤率為：*,11( / )(0.30.2)(0.30.3)(0.20.5)0.633EY X aPP b a若輸入不等概分布，其概

8、率分布為：123111(), (), ()442P aP aP a6 . 0)4 . 03 . 0(21)3 . 02 . 0(41)2 . 03 . 0(41)()(XieiEPaPP掌握若采用最小錯誤概率譯碼準(zhǔn)則，則聯(lián)合矩陣為：0.1250.0750.05()0.050.0750.1250.150.150.2ijP ab 所得譯碼函數(shù)為：C：132333( )()()F baF baF ba平均錯誤率為：5 . 0)125. 005. 0()075. 0075. 0()05. 0125. 0()()(* YijiaXEabPaPP掌握第二節(jié) 錯誤概率與編碼方法6.1節(jié)結(jié)論：1）消息通過有噪

9、信道傳輸時會發(fā)生錯誤2）錯誤概率與譯碼規(guī)則有關(guān)噪聲干擾：破壞了信號的內(nèi)部結(jié)構(gòu)產(chǎn)生畸變而造成信息的損失。提高信號抗噪聲干擾能力：改造信號使其內(nèi)部結(jié)構(gòu)具有更強的規(guī)律性或相關(guān)性，當(dāng)信號的部分結(jié)構(gòu)被破壞時，仍能根據(jù)信號原有的內(nèi)在規(guī)律和相關(guān)性來發(fā)現(xiàn)甚至糾正錯誤，恢復(fù)原來的信息。了解01010.990.990.010.01例：對于如下二元對稱信道20.0110EP掌握（）重復(fù)編碼沒有使用的碼字001010011100101110用作消息的碼字000111輸出端接收序列000001010011100101110111二元對稱信道的三次擴展信道掌握則：3222222332222223pp pp pppp pp

10、ppppPpppppp pppp pp pp根據(jù)最大似然譯碼準(zhǔn)則，可得譯碼函數(shù)為：F(000)=000 F(001)=000 F(010)=000 F(011)=111F(100)=000 F(101)=111 F(110)=111 F(111)=1113*4() (/)3*10EijiY C aPPP最大似然譯碼掌握根據(jù)接收序列中0多還是1多，0多就判作0，1多就判作1。擇多譯碼錯誤概率降低了兩個數(shù)量級，這種編碼可以糾正碼字中的一位碼元出錯。若重復(fù)多次可進一步降低錯誤率理解（2）重復(fù)編碼產(chǎn)生的問題n很大時，信息傳輸率會降低很多l(xiāng)ogMRn 在上例中：M=2當(dāng)n=1時 R=1當(dāng)n=3時 R=1

11、/3 當(dāng)n=5時 R=1/5 .當(dāng)n=11時 R=1/11編碼后的消息傳輸率（碼率）M輸入消息的個數(shù)，logM表示消息集在等概率條件下每個消息攜帶的平均信息量編碼后碼字的長度結(jié)論：重復(fù)編碼盡管可使錯誤概率降低很多，但同時也使信息傳輸率降的很低。掌握這個矛盾能不能解決，能不能找到一種更好的編碼方法，使PE 相當(dāng)?shù)?，而R卻保持在一定水平呢?掌握（3）重復(fù)編碼降低信息傳輸率的原因在未重復(fù)編碼以前，輸入端是二個消息的集合。假設(shè)為等概率分布則每個消息攜帶的信息最是logM=1(比特符號)。簡單重復(fù)(n=3)后，可以把信道看成是三次無記憶擴展信道。這時輸入端有8個二元序列可以作為消息(a1,a8)，但只選

12、擇了二個二元序列作為消息，M2。這樣每個消息攜帶的平均信息量仍是1比特。而傳送一個消息需要付出的代價卻是三個二元碼符號，所以R就降低到1/3(比特碼符號)。了解如果在擴展信道的輸入端把8個可能作為消息的二元序列都作為消息，M8，則每個消息攜帶的平均信息量就是3比特，而傳遞一個消息所得的符號數(shù)仍為三個二元碼符號，則R就提高到 1（比特碼符號）。這時的信道如下圖所示。 發(fā)送消息接受消息理解這時只能規(guī)定接收端8個輸出符號序列j與i 一一對應(yīng)。這樣，只要符號序列中有一個碼元符號發(fā)生錯誤就會變成其他所用的碼字，造成譯碼錯誤。只有符號序列中每個符號都不發(fā)生錯誤才能正確傳輸。所以得到正確傳輸概率為 錯誤概率

13、: 理解 如果在三次無記憶擴展信道中，取M4，如：取000 011 101 110為消息，其他的不用，則222*103EPR(4)M的選擇則與M=8比較，錯誤率降低了，而信息率也降低了。進一步觀察M=4時，有70種選取方法，而選取方法不同，錯誤率也不同。我們比較下面兩種選取方法： 第一種： 000 011 101 110 第二種： 000 001 010 100 可以計算得第一種方法的錯誤率為 第二種方法的錯誤率為22*1022.28*10掌握 取M4，n5，這4個碼字按如下規(guī)則選?。?設(shè)輸入序列為:12345()iiiiiiaaaaaa滿足方程：31241512iiiiiiiiaaaaaaa

14、a若譯碼采取最大似然準(zhǔn)則：25R 漢明編碼漢明編碼掌握000000000100010001000000001000100001000100011011010110001111010010110100101111011110001110101111011010101100111011111111001110011010100110101101111000111101101010010010100101111001 此碼能糾正所有碼字中一位碼元錯誤，也能糾正其中兩個兩位碼元的錯誤。543252EPpp pp p5432411 (52)7.8 10EEPPpp pp p 掌握（5）碼字之間區(qū)別的度量

15、碼字距離漢明距離：1(,)nijikjkkD 如：101111i111100j則(,)3ijD 掌握 在某一碼書中，任意兩個碼字的漢明距離的最小值稱為該碼C的最小距離。minmin (,)ijijdD C CCC最小距離在任一碼書中，碼的最小距離與該碼的譯碼錯誤概率有關(guān)。掌握43*1022*1022.28*1023*10前邊的5種碼的距離：理解 很明顯， 越大， 越小，在M相同的情況下也是一樣mindEP碼書中最小距離越大，受干擾后，越不容易把一個碼字錯成為另一碼字，因而錯誤概率小。若碼書的最小距離小，受干擾后很容易把一碼字變成另一碼字，因而錯誤概率大。結(jié)論：在編碼選碼字時，要使碼字之間的距離

16、越大越好。理解（6）最大似然譯碼準(zhǔn)則與漢明距離的關(guān)系若 和 之間的距離為 記為Dij ，它表示傳輸過程中 傳輸?shù)?，有 Dij 個位置發(fā)生了錯誤，(n - Dij)個位置沒有錯誤。njjYCF,)(*CPPiiijj,)()(*i按照最大似然譯碼準(zhǔn)則，應(yīng)選擇譯碼函數(shù)：使得：j),(jiDij理解設(shè)二元對稱信道的單個符號傳輸錯誤概率為p，當(dāng)信道是無記憶時，則編碼后信道的傳遞概率為： 通常p1/2，Dij越大P(j / i)越小，Dij越小P(j / i)越大理解（7）最小距離譯碼準(zhǔn)則：稱為最小距離譯碼準(zhǔn)則，它等價于最大似然譯碼準(zhǔn)則，也就是收到一個碼字后，把它譯成與它最近的輸入碼字，這樣可以使平均

17、錯誤率最小。 另外，我們應(yīng)該選擇這樣的編碼方法：應(yīng)盡量設(shè)法使選取的M個碼字中任意兩兩不同碼字的距離盡量大。理解在有噪信道中，傳輸?shù)钠骄e誤概率PE與各種編、譯碼方法有關(guān)。編碼選用M個消息所對應(yīng)的碼字間最小距離dmin盡可能大的編碼方法；譯碼采用將接收序列bj譯成與之距離最近的那個碼字a*的譯碼規(guī)則；只要碼長n足夠長時，合適地選擇M個消息所對應(yīng)的碼字，就可以使錯誤概率很小，而信息傳輸率保持一定。（8）結(jié)論理解1、有噪信道編碼定理有噪信道編碼定理 如一個離散無記憶信道，信道容量為C。當(dāng)信息傳輸率RC時，只要碼長足夠長，總可以在輸入符號集中 找到M 個碼字組成的一組碼 和相應(yīng)的譯碼準(zhǔn)則，使信道輸出端

18、的平均錯誤譯碼概率達到任意小。nX(2 )nR(2 , )nRn第四節(jié) 有噪信道編碼定理（香農(nóng)第二定理）了解允許平均錯誤概率任意小而非零；用n次無記憶信道大數(shù)定律有效；隨機選取碼書，在隨機選取編碼的基礎(chǔ)上計算碼的平均錯誤概率；因為隨機選取，所以使概率對稱；并由此證明至少有一種好碼存在。說明：了解2、有噪信道編碼逆定理有噪信道編碼逆定理 如一個離散無記憶信道，信道容量為C。當(dāng)信息傳輸率RC時，則無論碼長n多長，總找不到一種編碼 使信道輸出端的平均錯誤譯碼概率達到任意小。(2 , )nRn了解 定理定理6.6 對于限帶高斯白噪聲加性信道，噪聲功率對于限帶高斯白噪聲加性信道，噪聲功率為為 ，帶寬為，

19、帶寬為W，信號平均功率受限為，信號平均功率受限為 ，則，則（1）當(dāng)）當(dāng) ，總可以找到一種信道編碼，總可以找到一種信道編碼在信道中以信息傳輸率（碼率）在信道中以信息傳輸率（碼率）R傳輸信息，而使平均錯傳輸信息，而使平均錯誤概率任意小。（誤概率任意小。（2）當(dāng)）當(dāng)R C ，找不到任何信道編碼，在，找不到任何信道編碼，在信道中以信道中以R傳輸信息而使平均錯誤概率任意小。傳輸信息而使平均錯誤概率任意小。 sPlog(1)snRCWP PnP了解 這個定理是信道編碼的理論依據(jù)，可以看出：信道容量是一個明確的分界點，當(dāng)取分界點以下的信息傳輸率時， 以指數(shù)趨進于0；當(dāng)取分界點以上的信息傳輸率時， 以指數(shù)趨進

20、于1；因此在任何信道中，信道容量都是可達的、最大的可靠信息傳輸率。 這個定理是一個存在定理，它沒有給出一個具體可構(gòu)造的編碼方法，在它的證明過程中，碼書是隨機的選取的，它有助于指導(dǎo)各種通信系統(tǒng)的設(shè)計，有助于評價各種系統(tǒng)及編碼的效率。EPEP3、結(jié)論了解第五節(jié) 聯(lián)合信源信道編碼定理香農(nóng)第二定理指出：要在任意信道中進行數(shù)據(jù)傳輸，必須信息傳輸率小于信道容量RC，才能可靠地傳輸數(shù)據(jù)。香農(nóng)第一定理指出：要進行無失真信源數(shù)據(jù)壓縮必須RH。問題：若信源通過信道傳輸，要做到有效和可靠(無錯誤)地傳輸，是否HC是充分和必要的條件？了解1、兩步編碼 從香農(nóng)第一、第二定理可以看出，要做到有效和可靠從香農(nóng)第一、第二定理可以看出，要做到有效和可靠的傳輸信息，我們可以將通信系統(tǒng)設(shè)計成兩部分的組合，的傳輸信息，我們可以將通信系統(tǒng)設(shè)計成兩部分的組合，即信源編碼和信道編碼兩部分，即信源編碼和信道編碼兩部分，首先通過信源編碼，用盡首先通過信源編碼，用盡可能少的信道符號來表達信源，可能少的信道符號來表達信源，然后針對信道，然后針對信道，對信源編對信源編碼后的數(shù)據(jù)獨立的進行信道編碼，適當(dāng)增加一些剩余度，碼后的數(shù)據(jù)獨立的進行信道編碼，適當(dāng)增加一些剩余度，使能糾正和克服信道中引起的錯誤和干擾。使能糾正和克服信道中引起的錯誤和干擾。了解2、兩步編碼與一步編碼具有相同的效果無失真信源編碼是一一對