《有噪信道編碼》PPT課件.ppt

第六章有噪信道編碼,6.1譯碼準(zhǔn)則與譯碼錯誤概率,有噪聲信道編碼的主要目的是提高傳輸可靠性，增加抗干擾能力，因此也稱為糾錯編碼或抗干擾編碼。信源編碼之后的碼字序列抗干擾能力很脆弱，在信道噪聲的影響下容易產(chǎn)生差錯，為了提高通信系統(tǒng)的有效性和可靠性，要在信源編碼器和信道之間加上一個信道編碼器，,6.1.1譯碼準(zhǔn)則的含義,一個例子影響通信系統(tǒng)可靠性的一個重要問題是譯碼方式，可以通過一個例子看一下；有一個BSC信道，如圖所示。,對于這樣一個信道，如果采用自然的譯碼準(zhǔn)則，即收0判0，收1判1；這時可以明顯看到，當(dāng)信源先驗概率的等概時p(0)=p(1)=1/2；這時收到Y(jié)判X的后驗概率等于信道轉(zhuǎn)移概率，系統(tǒng)正確的譯碼概率為1/4，錯誤譯碼概率為3/4。但如果采用另一種譯碼準(zhǔn)則，收0判1，收1判0；則系統(tǒng)正確的譯碼概率為3/4，錯誤譯碼概率為1/4，通信的可靠性提高了。譯碼準(zhǔn)則,這時定義一個收到y(tǒng)j后判定為xi的單值函數(shù)，即：F(yj)=xi(i=1,2,…n;j=1,2,…m)；這個函數(shù)稱為譯碼函數(shù)。它構(gòu)成一個譯碼函數(shù)組，這些函數(shù)的值組成了譯碼準(zhǔn)則。對于有n個輸入，m個輸出的信道來說，可以有nm個不同的譯碼準(zhǔn)則。例如上面例子中有4中譯碼準(zhǔn)則分別為：A:{F(0)=0;F(1)=0}B:{F(0)=0;F(1)=1}C:{F(0)=1;F(1)=0}D:{F(0)=1;F(1)=1},6.1.2譯碼錯誤概率,譯碼準(zhǔn)則確定之后，當(dāng)接收端收到一個yj后，則按譯碼準(zhǔn)則譯成F(yj)=xi，這時如果發(fā)送的為xi則為正確譯碼，如果發(fā)送的不是xi則為錯誤譯碼。所以接收到y(tǒng)j后正確譯碼的概率就是接收端收到y(tǒng)j后，推測發(fā)送端發(fā)出xi的后驗概率：Prj=P{F(yj)=P(xi/yj)}而錯誤譯碼的概率為收到y(tǒng)j后，推測發(fā)出除了xi之外其它符號的概率：Pej=P{e/yj}=1-P{F(yj)=xi/yj},其中e表示除了xi之外的所有其它信源符號的集合。然后對所有的yj取平均，則平均正確譯碼概率為：,,同樣可以得到平均錯誤譯碼概率為：,,6.1.3最大后驗概率準(zhǔn)則,由平均錯誤譯碼概率的表達式可以看出，錯誤譯碼概率與信道輸出端隨機變量Y的概率分布p(yj)有關(guān)，也與譯碼準(zhǔn)則有關(guān)。當(dāng)信道信道轉(zhuǎn)移概率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)求和得到。因此，在這種情況下，平均錯誤譯碼概率只與譯碼準(zhǔn)則有關(guān)了。通過選擇譯碼準(zhǔn)則可以使平均譯碼概率達到最小值。當(dāng)式中的每一項的P{F(yj)=xi/yj}達到最大值時，平均錯誤譯碼概率就可以為最小值。設(shè)信源X的信源空間為：,收到每一個yj(j=1,2,…m)后，推測發(fā)送為xi(i=1,2,…n)的后驗概率共有n個，為：p(x1/yj),p(x2/yj),……p(xn/yj)。這其中必有一個為最大的，設(shè)其為：p(x*/yj)，即有：p(x*/yj)≥p(xi/yj)(對一切的i)這表明：收到符號yj后就譯為輸入符號x*，即譯碼函數(shù)選為：F(yj)=a*(j==1,2,…m)這種譯碼準(zhǔn)則稱為“最大后驗概率準(zhǔn)則”。,這個表達式平均錯誤譯碼概率的最小值，是把每一個yj對應(yīng)的后驗概率排除后再連續(xù)求和。從表達式中可以看到，這個最小值與信源先驗概率和信道轉(zhuǎn)移概率有關(guān)，特別是信道轉(zhuǎn)移概率，如果除了p(yj/x*)外，其它的項多很小，錯誤譯碼概率會減小。,6.1.4最大似然準(zhǔn)則,使用最大后驗概率譯碼準(zhǔn)則必須已知后驗概率，但信道的統(tǒng)計特性描述總是給出信道轉(zhuǎn)移概率，因此利用信道轉(zhuǎn)移概率的譯碼準(zhǔn)則。由概率中的貝葉斯定理可有：,,,這樣，根據(jù)最大后驗概率譯碼準(zhǔn)則，如果p(x*)p(yj/x*)≥p(xi)p(yj/xi)(i=1,2,……n)就等于：p(x*/yj)≥p(xi/yj)則選擇譯碼準(zhǔn)則：F(yj)=x*(j=1,2,……n)這樣，可以看到當(dāng)信道輸入符號集X的先驗概率為等概時[p(xi)=1/n]，比較上面三個式子，最大后驗概率可以用最大信道轉(zhuǎn)移概率來取代。這時，在X的先驗概率為等概時，如果p(yj/x*)是yj相應(yīng)的n個信道轉(zhuǎn)移概率p(yj/x1),p(yj/x2),……,p(yj/xn)中的最大者，則我們就將yj譯成x*，這種譯碼方法稱為“最大似然譯碼準(zhǔn)則”。,最大似然譯碼準(zhǔn)則利用了信道轉(zhuǎn)移概率，而不用后驗概率，將會更方便。為了減小錯誤譯碼概率，主要方法是改變信道轉(zhuǎn)移概率，,,6.2信道編碼定理,[定理]：有噪聲信道編碼定理（Shannon第二編碼定理）如一個離散有噪聲信道有n個輸入符號，m個輸出符號，信道容量為C。當(dāng)信道的熵速率R≤C時，只要碼長足夠長，總可以找到一種編碼方法及譯碼準(zhǔn)則，使信道輸出端的平均錯誤譯碼概率達到任意小，[pe=ε]。當(dāng)R>C時，則不可能找到一種編碼方法及譯碼準(zhǔn)則，使信道輸出端的平均錯誤譯碼概率達到任意小。,編碼定理的證明比較復(fù)雜，主要參考課本140頁這個定理是一個存在定理，指出錯誤率趨于0的編碼方法是存在的。定理表明，在錯誤率趨于0的同時，還可以使R趨于C，這是具有理論指導(dǎo)意義的。,引入冗余,一個BSC信道，輸入為X={0，1}，且為等概分布，信道模型為：,按最大似然譯碼準(zhǔn)則為：F(0)=0;F(1)=1;pe=0.01這里沒有采用任何信道編碼。,編譯碼方法,將0編為000，1編為111。這時的可用碼字為8；分別為：X1=000X2=001X3=010X4=100X5=011X6=110X7=101X8=111而許用碼字為000和111，相當(dāng)于信道輸入為X1=000，X2=111，而信道輸出端為：Y1=000；Y2=001；Y3=010；Y4=100Y5=011；Y6=110；Y7=101；Y8=111這時的信道轉(zhuǎn)移矩陣為：,這時如果按最大似然法則譯碼，將為：F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111錯誤譯碼概率為：Pe≈310-4可見簡單重復(fù)碼可以將錯誤譯碼概率下降兩個數(shù)量級。這是三次方法；可以看出如果是五次重復(fù)碼，誤碼率還要降低,6.3信道編碼,信道編碼又稱為差錯控制編碼，簡稱為糾錯編碼，即在信息序列中按一定的規(guī)則附加若干監(jiān)督碼元，以便對信息傳輸（或存儲）起檢錯與糾錯作用，目的在于提高通信（或存儲）的可靠性，減低誤碼率。,6.3.1分類,幾個基本概念,碼字空間：如果原始信源空間有M個碼字，對其進行q元等長碼的信道編碼，碼長為N，信道碼字空間的所有碼字為qN個，編碼器將在這qN個可用碼字中選擇M個碼字分別代表原始信源中的M個碼字，信道編碼碼字空間的這M個碼字稱為“許用碼字”，而另外的qN-M個碼字稱為“禁用碼字”。為了實現(xiàn)糾錯編碼，一定有qN>M。這M個許用碼字也稱為一個碼組，或稱為碼字集合。,漢明距離：(Hammingdistance),在一個碼組（碼字集合）中，任意兩個等長碼字之間，如果有d個相對應(yīng)的碼元不同，則稱d為這兩個碼字的漢明距離。例如：α和β為碼組X中的兩個不同碼字，X為一個長度為N的二元碼組，其中：α=[a1,a2,……aN]ai∈{0,1}β=[b1,b2,……bN]bi∈{0,1}則α與β的漢明距離為：d=0表明為全同碼，d=N表明為全異碼，如果用模2加法的概念，有模2加法等同于“異或”運算,最小碼距：,,在一個碼字集合中，任何兩個碼字之間的漢明距離組成一個元素集合，D(α,β),這個集合中的最小值稱為這個碼字集合的最小漢明距離，簡稱最小碼距，記為：dmin。dmin=min{d(α,β)α,β∈Xα≠β},碼字重量（漢明重量）(Hammingweight),在二元編碼的碼字集合中，碼字中“1”碼元的個數(shù)稱為這個碼字的重量。記為：W(α),舉例:,氣象臺預(yù)報天氣信碼監(jiān)督元碼字（偶校驗）傳輸中錯一位晴000（000）?100，010，001云011（011）?111，001，010陰101（101）?001，111，100雨110（110）?010，100，111許用碼字禁用碼組可檢一位錯，之所以能檢錯，是因為引入了冗余（禁用碼組）,例2可檢查出2位錯。附加兩個監(jiān)督元，設(shè)只有“晴”、“雨”兩種信息:信碼監(jiān)督元碼字傳輸中錯一位晴000（000）?100，010，001?0雨111（111）?011，101，110?1可糾1位錯（000）（111）許用碼字,其他為禁用碼字.在例2中，若編碼規(guī)則為晴011，雨000，則無糾錯能力。當(dāng)發(fā)生1位錯時：（011）?111，001，010（000）?001，100，010則不能糾1位錯，但仍能檢1位錯。,糾、檢錯能力與最小距離d0之間的關(guān)系,一個碼能夠檢測出,個錯誤；,只用于糾錯，能糾正,個錯誤；,用于既糾tc個錯，又檢td個錯,6.3.2線性分組碼,分組碼是一種代數(shù)編碼，它的基本關(guān)系一個碼字包括獨立的信息元和監(jiān)督元，其監(jiān)督元與信息元之間是一種代數(shù)關(guān)系，如果這種代數(shù)關(guān)系為線性的則稱為線性分組碼。分組碼的編碼器的模型為：,[m]為編碼器的輸入，稱為信息碼元（信息位），它由k位碼元組成。[C]為編碼器的輸出，稱為碼字矢量，它由n位碼元組成，其中有k位信息元，r=n-k位監(jiān)督元。線性分組碼：監(jiān)督元與信息元之間的關(guān)系可用一組線性方程組來描述的(n,k)分組碼。,以(7,4)漢明碼為例簡單介紹,N=7,k=4,r=3.,[C]=[c6,c5,c4,c3,c2,c1,c0]；其中[c6,c5,c4,c3]為信息位，[c2,c1,c0]為監(jiān)督位。,由[H][C]T=[0]可知：監(jiān)督方程為：c2=c5+c4+c3c1=c6+c4+c3c0=c6+c5+c3其中加號為”模2和”規(guī)則.,根據(jù)這個方程組可以進行編碼。例如信息碼元m=[1011]，則有c2=c5+c4+c3=0+1+1=0c1=c6+c4+c3=1+1+1=1c0=c6+c5+c3=1+0+1=0則漢明碼字[C]=[1011010]。,假如接收碼字為[R]=[0100101]可以看到：[S]T=[H][R]T=[0]這時表明無差錯；如果接收碼字有一位差錯，[R]=[0110101]；即錯誤圖樣[E]=[0010000]；接收碼字的第三位錯。這時校驗子矢量為：,可見這時校驗子[S]T不為0，譯碼器認為有錯，且正好等于[H]的第三列，表明接收碼字的第三位碼元錯了。這時判斷發(fā)送碼字位[0100101]，譯碼正確。,如果接收碼字由兩位差錯，[R]=[0111101]；即錯誤圖樣[E]=[0011000]；接收碼字的第三、四位錯。這時校驗子矢量為：,可見這時，校驗子矢量不為0，但是如果這時接收機按原來的譯碼方法，將認為第7位出錯。但如果接收機設(shè)計為檢錯系統(tǒng)，當(dāng)校驗子不為0，就認為有錯。因為(7,4)漢明碼的最小碼距為3(3<1+2+1)，其不具備一種方法同時具有糾錯檢錯能力.,注意：糾錯碼的選用要小心，要根據(jù)信道條件來確定，如果信道較差，而使用的糾錯碼能力不夠，可能使譯碼錯誤反而增加，不僅錯誤的碼元沒有糾正，原來正確的碼元還被錯誤的改變。錯上加錯。,這種糾檢錯能力是由碼組的最小碼距決定的?？梢则炞C：下面的(7,3)線性分組碼的最小碼距為4，可以糾一位錯，同時檢兩位錯，其基本監(jiān)督矩陣為：,生成矩陣(Generatormatrix),[C]=[m3,m2,m1,m0].[G],[m]=[1100],[C]=[1100][G]=[1100110],即有：[H][G]T=[0]，同時有：[G][H]T=[0]稱[H]與[G]為正交矩陣,