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

《《有噪信道編碼》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《有噪信道編碼》PPT課件.ppt（41頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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