信息論課程講義-第五章 糾錯編碼原理

1、2022-1-101 第五章第五章 糾錯編碼原理糾錯編碼原理有噪聲信道編碼的主要目的是有噪聲信道編碼的主要目的是提高傳輸可靠性提高傳輸可靠性，增，增加抗干擾能力，因此也稱為加抗干擾能力，因此也稱為糾錯編碼糾錯編碼或或抗干擾編碼抗干擾編碼。信源編碼之后的碼字序列抗干擾能力很脆弱，在信信源編碼之后的碼字序列抗干擾能力很脆弱，在信道噪聲的影響下容易產生差錯，為了提高通信系統(tǒng)道噪聲的影響下容易產生差錯，為了提高通信系統(tǒng)的有效性和可靠性，要在信源編碼器和信道之間加的有效性和可靠性，要在信源編碼器和信道之間加上一個信道編碼器。上一個信道編碼器。SOURCESOURCECODINGCHANNELCODING

2、TxCHANNELRxCHANNELDE-CODSOURCEDE-CODSINK2022-1-102 信源編碼信源編碼-Source Coding Compresses the data to remove redundancy 信道編碼信道編碼-Channel Coding Adds redundancy to protect against channel errors2022-1-103一個通信系統(tǒng)總是要以一定的速率、可靠地、保證質量的將一個通信系統(tǒng)總是要以一定的速率、可靠地、保證質量的將信息從一端傳送到另一端。信息從一端傳送到另一端。Example: Rate = 1MbpsError

3、 rate = 10-5；Error-control codingTwo key systems parameters aretransmitted signal power and channel bandwidth.In general, Signal power error rate Bandwidth error rate Both signal power and bandwidth cannot be increased infinitely.2022-1-1045.1 譯碼準則譯碼準則5.1.1 譯碼準則的含義譯碼準則的含義一個例子一個例子影響通信系統(tǒng)可靠性的一個重要問題是譯碼影

4、響通信系統(tǒng)可靠性的一個重要問題是譯碼方式，可以通過一個例子看一下；方式，可以通過一個例子看一下；有一個有一個BSC信道，如圖所示。信道，如圖所示。2022-1-105對于這樣一個信道，如果采用對于這樣一個信道，如果采用自然的譯碼準則自然的譯碼準則，即收，即收0判判0，收，收1判判1；這時可以明顯看到，當信源先驗概率；這時可以明顯看到，當信源先驗概率的等概時的等概時p(0)=p(1)=1/2；這時收到；這時收到Y判判X的后驗概率等的后驗概率等于信道轉移概率，系統(tǒng)正確的譯碼概率為于信道轉移概率，系統(tǒng)正確的譯碼概率為1/4，錯誤譯，錯誤譯碼概率為碼概率為3/4。但如果采用。但如果采用另一種譯碼準則另

5、一種譯碼準則，收，收0判判1，收收1判判0；則系統(tǒng)正確的譯碼概率為；則系統(tǒng)正確的譯碼概率為3/4，錯誤譯碼概率，錯誤譯碼概率為為1/4，通信的可靠性提高了。，通信的可靠性提高了。2022-1-106譯碼準則譯碼準則設一個有噪聲離散信道，輸入符號集設一個有噪聲離散信道，輸入符號集X X，輸出符號集，輸出符號集Y Y，信道轉移概率為信道轉移概率為P(Y/X);P(Y/X);X:x1,x2,.,xn。 Y:y1,y2,ymP(Y/X):p(yj/xi); i=1,2,n; j=1,2,m這時定義一個收到這時定義一個收到y(tǒng)j后判定為后判定為xi的單值函數(shù)，的單值函數(shù)，即： F(yj)=xi (i=1,

6、2,n; j=1,2,m)；這個函數(shù)稱為譯碼函數(shù)譯碼函數(shù)。它構成一個譯碼函數(shù)組，這些函數(shù)的值組成了譯碼準則譯碼準則。2022-1-107對于有對于有n個輸入，個輸入，m個輸出的信道來說，可以有個輸出的信道來說，可以有nm個個不同的譯碼準則。不同的譯碼準則。例如上面例子中有例如上面例子中有4種譯碼準則分別為：種譯碼準則分別為：A:F(0)=0;F(1)=0 B:F(0)=0;F(1)=1C:F(0)=1;F(1)=0 D:F(0)=1;F(1)=12022-1-1085.1.2 譯碼錯誤概率譯碼錯誤概率當譯碼準則確定之后，接收端收到一個yj后，則按譯碼準則譯成F(yj)=xi，這時如果發(fā)送的為x

7、i則為正確譯碼，如果發(fā)送的不是xi則為錯誤譯碼。所以接收到y(tǒng)j后正確譯碼的概率就是接收端收到y(tǒng)j后，推測發(fā)送端發(fā)出xi的后驗概率：Prj=PF(yj)=xi/yj而錯誤譯碼的概率為收到y(tǒng)j后，推測發(fā)出除了xi之外其它符號的概率：Pej=Pe/yj=1-PF(yj)=xi/yj其中e表示除了xi之外的所有其它信源符號的集合。2022-1-109然后對所有的yj取平均，則平均正確譯碼概率為：PP yPp yp F yxyrjrjjmjjijjm()() ()/11同樣可以得到平均錯誤譯碼概率為：Pp yP eyp yP F yxyejjjjijjmjm() /()()/111這就是平均錯誤譯碼概率

8、的基本表達式，在通信系統(tǒng)設計和分析時，總是希望得到最可能小的平均錯誤譯碼概率。因此所有通信系統(tǒng)都將平均譯碼錯誤概率作為系統(tǒng)可靠性的一個重要指標。2022-1-10105.1.3 最大后驗概率準則最大后驗概率準則由平均錯誤譯碼概率的表達式可以看出，錯誤譯碼概率與信道輸出端隨機變量Y的概率分布p(yj)有關，也與譯碼準則有關。當信道轉移概率p(yj/xi)確定，而且信源統(tǒng)計特性p(xi)確定之后，信道輸出端的p(yj)也就確定了。因為：p(xi,yj)=p(xi)p(yj/xi); 而p(yj)可以由p(xi,yj)的(i=1,2, ,n)求和得到。因此，在這種情況下，平均錯誤譯碼概率只與因此，在

9、這種情況下，平均錯誤譯碼概率只與譯碼準則譯碼準則有關了。通過選擇譯碼準則可以使平有關了。通過選擇譯碼準則可以使平均譯碼概率達到最小值。均譯碼概率達到最小值。2022-1-1011當式中的每一項的當式中的每一項的PF(yj)=xi/yj達到最大值時，平均達到最大值時，平均錯誤譯碼概率就可以為最小值。錯誤譯碼概率就可以為最小值。設信源設信源X的信源空間為：的信源空間為：Pp yP eyp yP F yxyejjjjijjmjm() /()()/111)(.)()(: )(: ,2211nnxpxxpxxpxXPXPX)/(.)/()/(.)/(.)/()/()/(.)/()/(2122212121

10、11nmmmnnxypxypxypxypxypxypxypxypxypP 信道的轉移矩陣為：信道的轉移矩陣為：2022-1-1012收到每一個yj(j=1,2,m)后，推測發(fā)送為xi(i=1,2,n)的后驗概率共有n個，為：p(x1/yj),p(x2/yj),p(xn/yj)。這其中必有一個為最大的，設其為：p(x*/yj)，即有：p(x*/yj)p(xi/yj) (對一切的對一切的i)這表明：收到符號yj后就譯為輸入符號x*，即譯碼函數(shù)選為：F(yj)=x* (j=1,2,m)這種譯碼準則稱為這種譯碼準則稱為最大后驗概率準則最大后驗概率準則。2022-1-1013利用這種準則就可以使平均譯碼

11、錯誤概率公式中的求利用這種準則就可以使平均譯碼錯誤概率公式中的求和的每一項和的每一項 達到最小值達到最小值1-F(yj)=x*/yj。這時的平均錯誤譯碼概率的最小值為：這時的平均錯誤譯碼概率的最小值為：mjjjeyxpypP1min)/*(1)( nimjmjjjiyxpyxp111)*,(),(mjmjjjjyxpypyp11)/*()()( mjimjixiyjpxipyjxip11)/()(),(從表達式中可以看到，這個最小值與信源先驗概率和信道轉移概率有關，特別從表達式中可以看到，這個最小值與信源先驗概率和信道轉移概率有關，特別是信道轉移概率，如果除了是信道轉移概率，如果除了p(yj/

12、x*)外，其它的項都外，其它的項都很小很小，錯誤譯碼概率就小。，錯誤譯碼概率就小。2022-1-10145.1.4 最大似然準則最大似然準則最大后驗概率譯碼準則需要已知后驗概率，但信道的統(tǒng)計特性描述一般是信道轉移概率，因此希望 利用信道轉移概率的譯碼準則。 由概率中的貝葉斯定理可有：p xyp xp yxp yjjj(/)() (/)()*這樣，如果能夠保證對所有的i p(x*)p(yj/x*)p(xi)p(yj/xi) (i=1,2,n)就等于：p(x*/yj)p(xi/yj) （最大后驗）（最大后驗）則選擇譯碼準則：F(yj)=x* (j=1,2,n)2022-1-1015這樣，可以看到當

13、信道輸入符號集這樣，可以看到當信道輸入符號集X的先驗概率為等的先驗概率為等概時概時p(xi)=1/n，最大后驗概率可以用最大信道轉移，最大后驗概率可以用最大信道轉移概率來取代。概率來取代。這時，如果這時，如果p(yj/x*)是是yj相應的相應的n個信道轉移概率個信道轉移概率 p(yj/x1),p(yj/x2),p(yj/xn)中的最大者，則我們就將中的最大者，則我們就將yj譯成譯成x*，這種譯碼方法稱，這種譯碼方法稱為為“最大似然譯碼準則最大似然譯碼準則”。最大似然譯碼準則利用了最大似然譯碼準則利用了信道轉移概率信道轉移概率，而不用后，而不用后驗概率，將更方便。驗概率，將更方便。p xyp x

14、p yxp yjjj(/)() (/)()*2022-1-1016這時的最小平均錯誤譯碼概率為：這時的最小平均錯誤譯碼概率為：mjiijmjiijiexypnxypxpP11)/(1)/()( 將信道轉移矩陣將信道轉移矩陣P P中每一列中的最大元素去掉，中每一列中的最大元素去掉，然后將其它元素相加后除以然后將其它元素相加后除以nn。為了減小錯誤譯碼概率，主要方法是改變信道為了減小錯誤譯碼概率，主要方法是改變信道轉移概率。轉移概率。2022-1-1017說明說明:q最大后驗概率準則也叫做最小錯誤譯碼最大后驗概率準則也叫做最小錯誤譯碼概率準則，是一種最佳準則。概率準則，是一種最佳準則。q當信道的輸

15、入符號先驗概率為等概時，當信道的輸入符號先驗概率為等概時，最大似然準則就等于最大后驗概率準則。最大似然準則就等于最大后驗概率準則。q當信道的輸入符號先驗概率不等概時，當信道的輸入符號先驗概率不等概時，最大似然準則就不是最佳準則了。但是最大似然準則就不是最佳準則了。但是由于使用方便通常還是應用的。由于使用方便通常還是應用的。2022-1-1018舉例：舉例：X:x1,x2,x3 Y:y1,y2,y3信道轉移矩陣為信道轉移矩陣為:4 . 05 . 02 . 03 . 03 . 03 . 03 . 02 . 05 . 0P2022-1-1019如果使用最大似然準則如果使用最大似然準則;譯碼函數(shù)為譯碼

16、函數(shù)為:F(y1)=x1F(y2)=x3F(y3)=x2為信道矩陣各列中的最大項為信道矩陣各列中的最大項.計算可知計算可知;當先驗等概時平均錯誤譯碼概率為當先驗等概時平均錯誤譯碼概率為:4 . 05 . 02 . 03 . 03 . 03 . 03 . 02 . 05 . 0P567. 0)4 . 02 . 0()3 . 03 . 0()3 . 02 . 0(31eP2022-1-1020如果先驗不等概時平均錯誤譯碼概率為如果先驗不等概時平均錯誤譯碼概率為:1/4,1/4,1/26 . 0)4 . 02 . 0(21)3 . 03 . 0(41)3 . 02 . 0(41eP2022-1-10

17、21Fano不等式不等式可以看到：錯誤譯碼概率與譯碼準則有關，可以看到：錯誤譯碼概率與譯碼準則有關，但是主要是由于信道噪聲引起的。也就是由但是主要是由于信道噪聲引起的。也就是由信道的疑義度信道的疑義度H(X/Y)的存在引起的。的存在引起的。因此因此Pe與與H(X/Y)一定存在某種關系。一定存在某種關系。稱為稱為Fano不等式。不等式。) 1log()()/(nPPHYXHee2022-1-1022H(Pe)是是Pe的熵。的熵。1. 這個不等式指出疑義度分為兩個部分。這個不等式指出疑義度分為兩個部分。第一部份是產生錯誤還是不產生錯誤的不第一部份是產生錯誤還是不產生錯誤的不確定性；第二部分是產生錯

18、誤后是哪個輸確定性；第二部分是產生錯誤后是哪個輸入造成的不確定性。入造成的不確定性。2. 雖然雖然Pe與譯碼準則有關，但無論什么準則與譯碼準則有關，但無論什么準則該不等式都成立。該不等式都成立。3. 當信源和信道確定后，信道疑義度給定了當信源和信道確定后，信道疑義度給定了譯碼錯誤概率的下限。譯碼錯誤概率的下限。) 1log()()/(nPPHYXHee2022-1-1023H(X/Y)Pe1(n-1)/nlognlog(n-1)H(Pe)+Pelog(n-1)2022-1-10245.2 信道編碼基本概念信道編碼基本概念5.2.1 信道編碼定理信道編碼定理定理定理：有噪聲信道編碼定理：有噪聲信

19、道編碼定理（Shannon第二編碼定理）第二編碼定理）如一個離散有噪聲信道有如一個離散有噪聲信道有n個輸入符號，個輸入符號，m個輸個輸出符號，信道容量為出符號，信道容量為C。當信道的熵速率。當信道的熵速率RC時，只要碼長足夠長，總可以找到一種時，只要碼長足夠長，總可以找到一種編碼方編碼方法法及及譯碼準則譯碼準則，使信道輸出端的平均錯誤譯碼，使信道輸出端的平均錯誤譯碼概率達到任意小，概率達到任意小，pe=。當。當RC時，則不可時，則不可能找到一種編碼方法及譯碼準則，使信道輸出能找到一種編碼方法及譯碼準則，使信道輸出端的平均錯誤譯碼概率達到任意小。端的平均錯誤譯碼概率達到任意小。2022-1-10

20、255.2.2 信道編碼的基本概念（分組碼）信道編碼的基本概念（分組碼）碼字空間碼字空間如果原始信源空間有M個碼字，對其進行q元等長碼的信道編碼，碼長為N，信道碼字空間的所有碼字為qN個，編碼器將在這qN個可用碼字中選擇M個碼字分別代表原始信源中的M個碼字，信道編碼碼字空間的這M個碼字稱為“許用碼字”，而另外的qN-M個碼字稱為“禁用碼字”。為了實現(xiàn)糾錯編碼，一定有qNM。這M個許用碼字也稱為一個碼組，或稱為碼字集合。2022-1-1026漢明距離：漢明距離：(Hamming distance)在一個碼組（碼字集合）中，任意兩個等長碼字之間，如果有d個相對應的碼元不同，則稱d為這兩個碼字的漢明

21、距離。例如：和為碼組X中的兩個不同碼字，X為一個長度為N的二元碼組，其中：=a1,a2,aN ai0,1=b1,b2,bN bi0,1則與的漢明距離為：dabdNiiiN( ,) 10d=0表明為全同碼，d=N表明為全異碼，如果用模2加法的概念，有dabiiiN( ,) 12022-1-1027最小碼距：最小碼距：在一個碼字集合中，任何兩個碼字之間的漢明距在一個碼字集合中，任何兩個碼字之間的漢明距離組成一個元素集合，離組成一個元素集合，D(,)，這個集合中的最，這個集合中的最小值稱為這個碼字集合的最小漢明距離，簡稱最小值稱為這個碼字集合的最小漢明距離，簡稱最小碼距，記為：小碼距，記為：dmin

22、。 dmin=mind(,) ,X 碼字重量（漢明重量）碼字重量（漢明重量）(Hamming weight)在二元編碼的碼字集合中，碼字中在二元編碼的碼字集合中，碼字中“1”碼元的個碼元的個數(shù)稱為這個碼字的重量。記為：數(shù)稱為這個碼字的重量。記為：W()。利用碼字重量的概念，漢明距離可以表示。利用碼字重量的概念，漢明距離可以表示為：為： d(,)=W( )2022-1-1028舉例舉例碼A碼B碼C碼D許用碼字000111000011101110000001100010000001111碼字個數(shù)2448最小距離3211傳輸效率1/32/32/31Pe310-4210-22.310-2310-220

23、22-1-1029分組碼最小碼距與糾檢錯能力的關系：分組碼最小碼距與糾檢錯能力的關系：一個分組碼的最小碼距為一個分組碼的最小碼距為dmin，則其糾檢錯能力為：，則其糾檢錯能力為：若發(fā)現(xiàn)若發(fā)現(xiàn)e個錯誤，則要求個錯誤，則要求dmine+1;若糾正若糾正t個錯誤，則要求個錯誤，則要求dmin2t+1;若糾正若糾正t個錯誤，同時發(fā)現(xiàn)個錯誤，同時發(fā)現(xiàn)e個錯誤，則要求個錯誤，則要求dmint+e+1; tC2R2022-1-1040降低譯碼錯誤概率的途徑：降低譯碼錯誤概率的途徑：(1)增加信道容量，從而使增加信道容量，從而使E(R)增加增加。根據(jù)上農公。根據(jù)上農公式可知，增加信道容量可以增加帶寬或者提高信噪式可知，增加信道容量可以增加帶寬或