通信與信息理論基礎(chǔ)_第10章--信道編碼

1、1信道編碼信道編碼信道差錯(cuò)概率信道差錯(cuò)概率信道編碼概述信道編碼概述信道譯碼準(zhǔn)則信道譯碼準(zhǔn)則碼的檢錯(cuò)與糾錯(cuò)能力碼的檢錯(cuò)與糾錯(cuò)能力2信道差錯(cuò)概率信道差錯(cuò)概率l 在通信過(guò)程中，傳送的最小信號(hào)波形是符號(hào)，編碼后在通信過(guò)程中，傳送的最小信號(hào)波形是符號(hào)，編碼后也稱為碼元。由于噪聲干擾，碼元在信道傳輸過(guò)程中也稱為碼元。由于噪聲干擾，碼元在信道傳輸過(guò)程中會(huì)發(fā)生變化，信宿方接收到的碼元符號(hào)不一定是信源會(huì)發(fā)生變化，信宿方接收到的碼元符號(hào)不一定是信源發(fā)出的碼元符號(hào)發(fā)出的碼元符號(hào) XY信道信道干擾干擾3隨機(jī)差錯(cuò)信道隨機(jī)差錯(cuò)信道l DMC的平均誤碼率的平均誤碼率u信道輸入信道輸入X ：A=a1, a2, aqu信道輸出

2、信道輸出Y ：B=b1, b2, bs u信道差錯(cuò)規(guī)律：條件概率描述信道差錯(cuò)規(guī)律：條件概率描述 (|)(|) (1,2,., ,1,2,., ).ijjijipP YbXaP baiq js4隨機(jī)差錯(cuò)信道隨機(jī)差錯(cuò)信道l DMC的平均誤碼率的平均誤碼率u碼元碼元ai正確傳輸概率為：正確傳輸概率為：(|) (1,2,., ).iiiiP YbXapiqu碼元碼元ai出錯(cuò)概率為：出錯(cuò)概率為：(|)=1 (1,2,., ).iiijiij iP YbXappiqu信道先驗(yàn)概率分布為信道先驗(yàn)概率分布為：() (1,2,., ).iiP Xapiqu信道因噪聲干擾產(chǎn)生的平均錯(cuò)誤概率為：信道因噪聲干擾產(chǎn)生的

3、平均錯(cuò)誤概率為：(1)1.ciiiiiiiiPppp p 5信道編碼信道編碼信道差錯(cuò)概率信道差錯(cuò)概率信道編碼概述信道編碼概述信道信道譯碼準(zhǔn)則信道信道譯碼準(zhǔn)則碼的檢錯(cuò)與糾錯(cuò)能力碼的檢錯(cuò)與糾錯(cuò)能力6信道編碼概述信道編碼概述l 信道編碼器是一個(gè)映射信道編碼器是一個(gè)映射f，它把信源符號(hào)序列，它把信源符號(hào)序列m變換成變換成信道符號(hào)序列信道符號(hào)序列c = f (m)，f稱為稱為信道編碼函數(shù)信道編碼函數(shù)，或稱為，或稱為糾錯(cuò)編碼函數(shù)糾錯(cuò)編碼函數(shù)。信道編碼也稱為。信道編碼也稱為糾錯(cuò)編碼糾錯(cuò)編碼。7信道編碼概述信道編碼概述l 信源符號(hào)序列：信源符號(hào)序列： m=m1m2,mk (mi A) l 信道編碼函數(shù)信道編碼

4、函數(shù)f ： c = f (m)= m1m2,mk d1d2,dr (dj A)l 信息元：信息元：m1m2,mkl 校驗(yàn)（監(jiān)督）元：校驗(yàn)（監(jiān)督）元：d1d2,drl 碼字碼字 (codeword)： cl k：信息位長(zhǎng)度l r: 校驗(yàn)位長(zhǎng)度，或稱為冗余位長(zhǎng)度，l n=k+r : 碼字長(zhǎng)度l 設(shè)S是全體信源符號(hào)序列構(gòu)成的集合， C = f (m) | m S 稱為信道碼信道碼，或稱為糾錯(cuò)碼糾錯(cuò)碼，簡(jiǎn)稱為碼碼 (code)。8信道譯碼信道譯碼l 譯碼函數(shù)譯碼函數(shù) 信道譯碼器的主要功能就是確定一套譯碼規(guī)則信道譯碼器的主要功能就是確定一套譯碼規(guī)則g，由接，由接收到的符號(hào)序列收到的符號(hào)序列r給出信源符號(hào)

5、序列給出信源符號(hào)序列c的一個(gè)最接近的的一個(gè)最接近的估計(jì)估計(jì)g(r)。g稱為稱為譯碼函數(shù)譯碼函數(shù)，由，由r求求g(r)的過(guò)程稱為的過(guò)程稱為信道信道譯碼譯碼。如果。如果g(r)=c，說(shuō)明信道譯碼器譯碼正確。如果，說(shuō)明信道譯碼器譯碼正確。如果g(r) c，說(shuō)明信道譯碼器譯碼錯(cuò)誤。，說(shuō)明信道譯碼器譯碼錯(cuò)誤。9信道譯碼信道譯碼l 在接收到符號(hào)序列在接收到符號(hào)序列r的條件概率，譯碼器譯碼錯(cuò)誤的條的條件概率，譯碼器譯碼錯(cuò)誤的條件概率定義為：件概率定義為：|( ( )| ).EPP grrc rl 譯碼器平均譯碼錯(cuò)誤概率定義為譯碼器平均譯碼錯(cuò)誤概率定義為|( )( ) ( ( )| ).EEPPPPP grr

6、rrrrc r10信道譯碼信道譯碼l P(r)是譯碼器接收符號(hào)序列是譯碼器接收符號(hào)序列r的概率分布：的概率分布：( )()( ) ( | ).PPPPccrc,rcr cl 信道因噪聲干擾產(chǎn)生的平均錯(cuò)誤概率為信道因噪聲干擾產(chǎn)生的平均錯(cuò)誤概率為l 使用信道編碼技術(shù)的主要目的就是使使用信道編碼技術(shù)的主要目的就是使 PE PC.( ) (| ).CPPPrrrc r11信道譯碼信道譯碼l 重復(fù)碼重復(fù)碼 重復(fù)碼是一個(gè)重復(fù)碼是一個(gè)(n, 1)分組碼，其編碼規(guī)則是分組碼，其編碼規(guī)則是將每位信息元重復(fù)將每位信息元重復(fù)n 1次，也稱為次，也稱為n次重復(fù)碼。即次重復(fù)碼。即C =000, 111。對(duì)重復(fù)碼，可以采

7、用。對(duì)重復(fù)碼，可以采用大數(shù)準(zhǔn)則譯大數(shù)準(zhǔn)則譯碼碼。即如果接收序列中。即如果接收序列中0的個(gè)數(shù)多于的個(gè)數(shù)多于1的個(gè)數(shù)，則譯的個(gè)數(shù)，則譯為為0；否則，譯為；否則，譯為1。 l 例如，例如，2元元3次重復(fù)碼的編碼規(guī)則如下：次重復(fù)碼的編碼規(guī)則如下： “0” “000”， “1” “111”。 它是一個(gè)它是一個(gè)2元元(3, 1)分組碼分組碼C=000, 111 。12信道譯碼信道譯碼l 當(dāng)三個(gè)符號(hào)在傳輸過(guò)程中有一位或二位出錯(cuò)時(shí)，譯碼器當(dāng)三個(gè)符號(hào)在傳輸過(guò)程中有一位或二位出錯(cuò)時(shí)，譯碼器能夠發(fā)現(xiàn)接收到的序列有錯(cuò)，但不知道那些位出了錯(cuò)。能夠發(fā)現(xiàn)接收到的序列有錯(cuò)，但不知道那些位出了錯(cuò)。但當(dāng)三個(gè)符號(hào)在傳輸過(guò)程中都出錯(cuò)

8、時(shí)，譯碼器不能發(fā)現(xiàn)但當(dāng)三個(gè)符號(hào)在傳輸過(guò)程中都出錯(cuò)時(shí)，譯碼器不能發(fā)現(xiàn)錯(cuò)誤。即分組碼錯(cuò)誤。即分組碼C最多能檢出最多能檢出2位錯(cuò)誤位錯(cuò)誤。l 如果大數(shù)準(zhǔn)則譯碼方法，當(dāng)傳輸?shù)姆?hào)序列有一位出錯(cuò)如果大數(shù)準(zhǔn)則譯碼方法，當(dāng)傳輸?shù)姆?hào)序列有一位出錯(cuò)時(shí)，能正確糾正。即時(shí)，能正確糾正。即分組碼分組碼C能糾正能糾正1位錯(cuò)誤位錯(cuò)誤。13信道譯碼信道譯碼u譯碼器接收符號(hào)序列譯碼器接收符號(hào)序列r及譯碼結(jié)果及譯碼結(jié)果接收序列r譯出的碼元u0 0 000 0 100 1 000 1 111 0 001 0 111 1 011 1 1114信道譯碼信道譯碼l 假設(shè)使用一個(gè)具有錯(cuò)誤概率為假設(shè)使用一個(gè)具有錯(cuò)誤概率為p 1/2的無(wú)記

9、憶二元對(duì)稱的無(wú)記憶二元對(duì)稱信道傳輸一個(gè)信源符號(hào)，且信源發(fā)出符號(hào)信道傳輸一個(gè)信源符號(hào)，且信源發(fā)出符號(hào)0和和1的概率均的概率均為為1/2。l 譯碼器平均譯碼錯(cuò)誤概率為譯碼器平均譯碼錯(cuò)誤概率為()(000,111)(000,011)(000,110)(000,101)(111,000)(111,001)(111,010)(11,100)c,r,g(r) cc,rEPPp crp crp crp crp crp crp crp cr15信道譯碼信道譯碼l 如果不使用信道編碼，直接傳輸信源符號(hào)，則信宿方接如果不使用信道編碼，直接傳輸信源符號(hào)，則信宿方接收到符號(hào)收到符號(hào)0時(shí)譯為時(shí)譯為0，接收到符號(hào)，接收到

10、符號(hào)1時(shí)譯為時(shí)譯為1，其信道錯(cuò)誤，其信道錯(cuò)誤概率為概率為(0) (1|0)(1) (0|1)11 .22CPPPPPpppcrccrcl 因?yàn)镻E PC，所以3次重復(fù)碼的使用提高了信道的可靠性。 323(1).EPpppl 譯碼器平均譯碼錯(cuò)誤概率為譯碼器平均譯碼錯(cuò)誤概率為16信道譯碼信道譯碼l 例如，當(dāng)例如，當(dāng)PC = p=10 2時(shí)，有時(shí)，有l(wèi) 使用簡(jiǎn)單的重復(fù)編碼方法，已將錯(cuò)誤概率降低了接近使用簡(jiǎn)單的重復(fù)編碼方法，已將錯(cuò)誤概率降低了接近二個(gè)數(shù)量級(jí)二個(gè)數(shù)量級(jí)!3240.013 0.01 (1 0.01)3 10 .EP 17信道譯碼信道譯碼l 當(dāng)重復(fù)次數(shù)當(dāng)重復(fù)次數(shù)n增加時(shí)，平均錯(cuò)誤概率將進(jìn)一步

11、降低，但碼增加時(shí)，平均錯(cuò)誤概率將進(jìn)一步降低，但碼率也隨之降低。率也隨之降低。碼長(zhǎng)n平均錯(cuò)誤概率PE ()碼率(比特/碼符號(hào))31041/351051/571071/791081/91110101/1118信道編碼信道編碼信道差錯(cuò)概率信道差錯(cuò)概率信道編碼概述信道編碼概述信道譯碼準(zhǔn)則信道譯碼準(zhǔn)則碼的檢錯(cuò)與糾錯(cuò)能力碼的檢錯(cuò)與糾錯(cuò)能力19最小錯(cuò)誤概率譯碼最小錯(cuò)誤概率譯碼 l 最小錯(cuò)誤概率譯碼最小錯(cuò)誤概率譯碼( ) ( ( )| )1( ) ( ( )| ).EPPP g rPP g rrrc rrrc ru譯碼函數(shù)譯碼函數(shù)g應(yīng)該具有最小平均譯碼錯(cuò)誤概率應(yīng)該具有最小平均譯碼錯(cuò)誤概率PE。u定義定義g(r

12、)的值滿足：的值滿足： ( ( )| )max( | ).P gPcrrc ru譯碼函數(shù)譯碼函數(shù)g稱為稱為最小錯(cuò)誤譯碼函數(shù)最小錯(cuò)誤譯碼函數(shù)，或稱為，或稱為最大后最大后驗(yàn)概率譯碼驗(yàn)概率譯碼。u選擇最大后驗(yàn)概率譯碼函數(shù)選擇最大后驗(yàn)概率譯碼函數(shù)g ( )*, , *,(| )( | ) ().ngCAPPCrcrcc* rc rc20最小錯(cuò)誤概率譯碼最小錯(cuò)誤概率譯碼; ( ( ); ( ( )( ) ( ( )| )( )1( ( )| )1( ( ), )( , )( ( ), )( , )( ) ( | ).EggPPP gPP gP gPP gPPP rrrc,rrc rrcc rrcrrc

13、rrrc rr rc rr rc rcr c( ( )( )( | ).EgPPPcrrccr c( ( )1( | ).EgPPM c rrcr cl 根據(jù)譯碼函數(shù)，可以寫(xiě)出平均譯碼錯(cuò)誤概率的計(jì)算根據(jù)譯碼函數(shù)，可以寫(xiě)出平均譯碼錯(cuò)誤概率的計(jì)算公式如下。公式如下。信源服從均勻分布時(shí)，信源服從均勻分布時(shí)，P(c)也是均勻分布，設(shè)碼字總也是均勻分布，設(shè)碼字總數(shù)為數(shù)為M =|C|，則有，則有P(c)= M 121最小錯(cuò)誤概率譯碼最小錯(cuò)誤概率譯碼l 后驗(yàn)概率后驗(yàn)概率P(c| r)與輸入概率分布與輸入概率分布P(c)有關(guān)，所以最大有關(guān)，所以最大后驗(yàn)概率譯碼函數(shù)依賴于輸入概率分布后驗(yàn)概率譯碼函數(shù)依賴于輸入概

14、率分布P(c)。即當(dāng)。即當(dāng)輸入概率分布輸入概率分布P(c)改變時(shí)，最大后驗(yàn)概率譯碼函數(shù)改變時(shí)，最大后驗(yàn)概率譯碼函數(shù)也要變化。也要變化。 22最大似然譯碼最大似然譯碼 ( |( )max( | ).PgPcrrr c( )*, , *ngCArcrc( |)( | ) ().PPCr c*r cc定義定義g(r)的值滿足：的值滿足：這樣確定的譯碼函數(shù)稱為這樣確定的譯碼函數(shù)稱為最大似然譯碼最大似然譯碼 (MLD)，P(r | c) 稱為稱為似然函數(shù)。最大似然譯碼函數(shù)只與信道轉(zhuǎn)移概似然函數(shù)。最大似然譯碼函數(shù)只與信道轉(zhuǎn)移概率有關(guān)，與信源概率分布無(wú)關(guān)率有關(guān)，與信源概率分布無(wú)關(guān)。可得最大似然譯碼函數(shù)?？傻?/p>

15、最大似然譯碼函數(shù)g滿足：滿足：即對(duì)于每一個(gè)符號(hào)序列即對(duì)于每一個(gè)符號(hào)序列r，均譯成具有最大似然函數(shù)的，均譯成具有最大似然函數(shù)的那個(gè)碼字那個(gè)碼字g(r) 23最大似然譯碼最大似然譯碼 ( ) ( | )( | )( | ).( )( )PPPPPMPcr cr cc rrr1max( | )max( | ).( )PPMPccc rr cr當(dāng)信源服從均勻分布時(shí)，有當(dāng)信源服從均勻分布時(shí)，有所以，所以，因此，在信源服從均勻分布情況下，最大后驗(yàn)概率譯與因此，在信源服從均勻分布情況下，最大后驗(yàn)概率譯與最大似然譯碼是相同的，其平均譯碼錯(cuò)誤概率為最小。最大似然譯碼是相同的，其平均譯碼錯(cuò)誤概率為最小。24例例l

16、 有一個(gè)離散信道，輸入符號(hào)集為有一個(gè)離散信道，輸入符號(hào)集為A=a1, a2, a3，接收符號(hào)集，接收符號(hào)集為為B=b1, b2, b3，信道矩陣為，信道矩陣為 假設(shè)信道每次傳輸一個(gè)符號(hào)。假設(shè)信道每次傳輸一個(gè)符號(hào)。0.5 0.3 0.20.2 0.3 0.5 .0.3 0.3 0.4P因?yàn)樾诺谰仃囈驗(yàn)樾诺谰仃嘝的第一列中的第一列中P(b1| a1)=0.5為最大，第三列為最大，第三列中中P(b3| a2)=0.5為最大，第二列中為最大，第二列中P(b2| a1)= P(b2| a2)= P(b2| a3)=0.3，所以最大似然譯碼函數(shù)為，所以最大似然譯碼函數(shù)為g(b1)= a1, g(b2)=

17、a3, g(b3)= a2.25例例123111(),(),().333p ap ap a( ( )11( | )1(0.3 0.2) (0.2 0.3) (0.3 0.4)0.567.3EgPPM c rrcr c123111( ), ( ), ( ).442p ap ap a如果輸入是等概率分布，其概率分布為如果輸入是等概率分布，其概率分布為最大似然譯碼函數(shù)最大似然譯碼函數(shù)g平均錯(cuò)誤概率為平均錯(cuò)誤概率為如果輸入不是等概率分布，設(shè)其概率分布為如果輸入不是等概率分布，設(shè)其概率分布為最大似然譯碼函數(shù)最大似然譯碼函數(shù)g的平均錯(cuò)誤概率為的平均錯(cuò)誤概率為( ( )( )( | )111(0.3 0.2

18、)(0.20.3)(0.3 0.4)0.600.442EgPPPcrrccr c26例例1112131111212313()(,)(,)(,)() (|)() (|) () (|)PbPabPabPabPa PbaPa PbaPa Pbarcrcrcrcrccrccrc111=0.50.20.3 0.325.442 l最大后驗(yàn)概率譯碼函數(shù)最大后驗(yàn)概率譯碼函數(shù)h。計(jì)算接收符號(hào)計(jì)算接收符號(hào)r概率分布概率分布P( r)。計(jì)算后驗(yàn)概率計(jì)算后驗(yàn)概率P(c| r)111111() (|)(|)()0.25 0.55.0.12513pa PbaPabPbcrccrr375. 0)(3 . 0)(32brPb

19、rP27例例512 13415211(|) .1343618 13215Pcr后驗(yàn)概率矩陣為后驗(yàn)概率矩陣為根據(jù)最大后驗(yàn)概率譯碼規(guī)則得最大后驗(yàn)概率譯碼根據(jù)最大后驗(yàn)概率譯碼規(guī)則得最大后驗(yàn)概率譯碼函數(shù)函數(shù)h為為h(b1)= a3, h(b2)= a3, h(b3)= a3. 接收序列接收序列r概率分布概率分布P(r)譯碼函數(shù)譯碼函數(shù)hb10.3250a3b20.3000a3b30.3750a328例例最大后驗(yàn)概率譯碼函數(shù)最大后驗(yàn)概率譯碼函數(shù)h的平均錯(cuò)誤概率為的平均錯(cuò)誤概率為此時(shí)此時(shí)所以，輸入不是等概率分布時(shí)，最大似然譯碼函數(shù)所以，輸入不是等概率分布時(shí)，最大似然譯碼函數(shù)的平均錯(cuò)誤概率不是最小的。的平均

20、錯(cuò)誤概率不是最小的。EEPP5 .0)31152(375.0)4141(3 .0)132135(325.0)|()()(crgcrErcPrPP29信道譯碼準(zhǔn)則信道譯碼準(zhǔn)則l 漢明（漢明（Hamming）距離）距離 兩個(gè)長(zhǎng)為兩個(gè)長(zhǎng)為n的碼字的碼字x與與y之間漢明（之間漢明（Hamming）距離是）距離是指指x與與y之間對(duì)應(yīng)位置上不相同碼元的個(gè)數(shù)，用符號(hào)之間對(duì)應(yīng)位置上不相同碼元的個(gè)數(shù)，用符號(hào)d(x, y)表示。表示。l 漢明重量：漢明重量： 碼字碼字x中非零碼元的個(gè)數(shù)稱為中非零碼元的個(gè)數(shù)稱為x的漢明重量，用符號(hào)的漢明重量，用符號(hào)w(x)表示。表示。u例如例如: 對(duì)于兩個(gè)二元碼字對(duì)于兩個(gè)二元碼字

21、x=101111， y=111100 有有d(x, y)=3。u又如又如: 對(duì)于兩個(gè)碼字對(duì)于兩個(gè)碼字 x=1320120, y=1223310 有有d(x, y)=4。30信道譯碼準(zhǔn)則信道譯碼準(zhǔn)則l 設(shè)設(shè) x= x1x2xn, y= y1y2yn 是兩個(gè)二元碼字，容易驗(yàn)證以下等式成立是兩個(gè)二元碼字，容易驗(yàn)證以下等式成立: 其中其中 是模二加法是模二加法l 漢明距離有以下性質(zhì)漢明距離有以下性質(zhì) 定理定理 設(shè)設(shè)x、y與與z是長(zhǎng)為是長(zhǎng)為n的碼字，那么漢明距離滿足的碼字，那么漢明距離滿足以下性質(zhì)：以下性質(zhì)： (1) 非負(fù)性：非負(fù)性：d(x, y) 0。且。且d(x, y) = 0的充分必要條件的充分必

22、要條件是是x = y； (2) 對(duì)稱性：對(duì)稱性：d(x, y) = d(y, x)； (3) 三角不等式三角不等式：d(x, y) d(x, z)+ d( z, y)。 1( , ),niiid x yxy31信道譯碼準(zhǔn)則信道譯碼準(zhǔn)則l 對(duì)于二元信道，如果譯碼函數(shù)對(duì)于二元信道，如果譯碼函數(shù)g將二元序列將二元序列r譯成譯成二元碼字二元碼字c，那么，那么r與與c之間的漢明距離之間的漢明距離d(r, c)就是就是譯碼出錯(cuò)的位數(shù)。譯碼出錯(cuò)的位數(shù)。l 最小漢明距離譯碼最小漢明距離譯碼 好的譯碼函數(shù)應(yīng)該使其譯碼出錯(cuò)的位數(shù)盡可能小，好的譯碼函數(shù)應(yīng)該使其譯碼出錯(cuò)的位數(shù)盡可能小，據(jù)此定義譯碼函數(shù)如下：據(jù)此定義譯

23、碼函數(shù)如下： 這樣確定的譯碼函數(shù)稱為最小漢明距離譯碼函數(shù)，這樣確定的譯碼函數(shù)稱為最小漢明距離譯碼函數(shù)，簡(jiǎn)稱為最小距離譯碼函數(shù)。簡(jiǎn)稱為最小距離譯碼函數(shù)。u最小漢明距離譯碼與信道轉(zhuǎn)移概率無(wú)關(guān)最小漢明距離譯碼與信道轉(zhuǎn)移概率無(wú)關(guān)( )*, , *,( ,)( , ) ().ngCAddCrcrcr c*r cc32信道譯碼準(zhǔn)則信道譯碼準(zhǔn)則l 對(duì)于對(duì)于BSC，設(shè)每個(gè)符號(hào)出錯(cuò)概率為，設(shè)每個(gè)符號(hào)出錯(cuò)概率為p1/2，r=(r1, r2, rn)，c=(c1, c2, cn)，那么，那么u這說(shuō)明，當(dāng)這說(shuō)明，當(dāng)r不變時(shí)，選擇不變時(shí)，選擇c使使P(r|c)達(dá)到最大的達(dá)到最大的充分必要條件是使充分必要條件是使d(r,

24、 c) 達(dá)到最小。達(dá)到最小。u因此，對(duì)于二元對(duì)稱無(wú)記憶信道，最小漢明距因此，對(duì)于二元對(duì)稱無(wú)記憶信道，最小漢明距離譯碼與最大似然譯碼是相同的。離譯碼與最大似然譯碼是相同的。1122( , )( , )( , )( | )( |) (|). (|)(1)(1).1nnddn dnPP r c P rcP rcpppppr cr cr cr c33信道譯碼準(zhǔn)則信道譯碼準(zhǔn)則l 在二元對(duì)稱無(wú)記憶信道中，平均譯碼錯(cuò)誤概率可在二元對(duì)稱無(wú)記憶信道中，平均譯碼錯(cuò)誤概率可用漢明距離表示。設(shè)信源服從均勻分布，碼字總用漢明距離表示。設(shè)信源服從均勻分布，碼字總數(shù)為數(shù)為M =|C|，有，有( , )( ( )( ( )(

25、 , )( ( )11( | )(1)1(1).1HHdnEggdngpPPpMMpppMp r ccrrccrrcr ccrrcr c34信道譯碼準(zhǔn)則信道譯碼準(zhǔn)則l 對(duì)對(duì)n次重復(fù)碼次重復(fù)碼C =000, 111進(jìn)行最小距離譯碼。進(jìn)行最小距離譯碼。u設(shè)接收的序列為設(shè)接收的序列為r，如果，如果d (r, 000) d (r, 111)，則將，則將r譯為譯為111。u如果如果d (r, 000) = d (r, 111)，則不能正常譯，則不能正常譯碼，只能發(fā)現(xiàn)差錯(cuò)。碼，只能發(fā)現(xiàn)差錯(cuò)。u注意到，當(dāng)注意到，當(dāng)d (r, 000) d (r, 111)時(shí)，序列時(shí)，序列r中中1的個(gè)數(shù)多于的個(gè)數(shù)多于0的個(gè)數(shù)

26、，所以的個(gè)數(shù)，所以n次重復(fù)碼的最小距離譯碼與大數(shù)準(zhǔn)則譯碼相次重復(fù)碼的最小距離譯碼與大數(shù)準(zhǔn)則譯碼相同。同。35信道譯碼準(zhǔn)則信道譯碼準(zhǔn)則l 平均譯碼錯(cuò)誤概率平均譯碼錯(cuò)誤概率PE與與譯碼函數(shù)有關(guān)，而譯碼函與與譯碼函數(shù)有關(guān)，而譯碼函數(shù)又與信道特性有關(guān)。由于信道存在噪聲，導(dǎo)致符數(shù)又與信道特性有關(guān)。由于信道存在噪聲，導(dǎo)致符號(hào)傳輸發(fā)生錯(cuò)誤，接收端收到符號(hào)后，對(duì)發(fā)送的是號(hào)傳輸發(fā)生錯(cuò)誤，接收端收到符號(hào)后，對(duì)發(fā)送的是什么符號(hào)還存在不確定性。什么符號(hào)還存在不確定性。l Fano不等式不等式 (|)()log(1).EEH X YH PPq36信道編碼信道編碼信道差錯(cuò)概率信道差錯(cuò)概率信道編碼概述信道編碼概述信道譯碼準(zhǔn)

27、則信道譯碼準(zhǔn)則碼的檢錯(cuò)與糾錯(cuò)能力碼的檢錯(cuò)與糾錯(cuò)能力37碼的檢錯(cuò)與糾錯(cuò)能力碼的檢錯(cuò)與糾錯(cuò)能力l 最小漢明距離最小漢明距離 設(shè)設(shè)C是一個(gè)是一個(gè) (n, k) 分組碼，分組碼，C的任意兩個(gè)碼字漢明距離的任意兩個(gè)碼字漢明距離的最小值稱為的最小值稱為C的最小漢明距離，簡(jiǎn)稱為最小距離，記的最小漢明距離，簡(jiǎn)稱為最小距離，記為為l 最小距離與糾錯(cuò)能力的關(guān)系最小距離與糾錯(cuò)能力的關(guān)系 定理設(shè)定理設(shè)C是一個(gè)是一個(gè) (n, k) 分組碼，其最小漢明距離為分組碼，其最小漢明距離為d(C)，則有則有 (1) 如果碼字出現(xiàn)了如果碼字出現(xiàn)了e個(gè)隨機(jī)錯(cuò)誤，且個(gè)隨機(jī)錯(cuò)誤，且d(C) e +1，則，則能夠檢測(cè)到出現(xiàn)的錯(cuò)誤。能夠檢測(cè)

28、到出現(xiàn)的錯(cuò)誤。 (2) 如果碼字出現(xiàn)了如果碼字出現(xiàn)了t個(gè)隨機(jī)錯(cuò)誤，且個(gè)隨機(jī)錯(cuò)誤，且d(C) 2t +1，則，則能夠糾正出現(xiàn)的錯(cuò)誤。能夠糾正出現(xiàn)的錯(cuò)誤。 (3) 如果如果C既能糾正既能糾正t個(gè)隨機(jī)錯(cuò)誤，又能檢測(cè)個(gè)隨機(jī)錯(cuò)誤，又能檢測(cè)e ( t)個(gè)隨個(gè)隨機(jī)錯(cuò)誤，則要求機(jī)錯(cuò)誤，則要求d(C) t + e +1。 min,( )min ( , ).x y C x ydd Cd x y38碼的檢錯(cuò)與糾錯(cuò)能力碼的檢錯(cuò)與糾錯(cuò)能力l 證明證明 (1) 如果發(fā)送的碼字如果發(fā)送的碼字c中出現(xiàn)了中出現(xiàn)了e個(gè)隨機(jī)錯(cuò)誤，且個(gè)隨機(jī)錯(cuò)誤，且變成了另一個(gè)許用碼字變成了另一個(gè)許用碼字r，則這樣的錯(cuò)誤是不可能被檢，則這樣的錯(cuò)誤是不

29、可能被檢測(cè)出來(lái)的。反之，如果測(cè)出來(lái)的。反之，如果r是一個(gè)禁用碼字，則這樣的錯(cuò)是一個(gè)禁用碼字，則這樣的錯(cuò)誤能夠被發(fā)現(xiàn)。當(dāng)誤能夠被發(fā)現(xiàn)。當(dāng)d(C) = e +1時(shí)，由于時(shí)，由于d(r, c) e，所以，所以r必須是禁用碼字，因而能夠被檢測(cè)出來(lái)的。必須是禁用碼字，因而能夠被檢測(cè)出來(lái)的。 在圖中，以在圖中，以c為圓心，為圓心，e為半徑的圓內(nèi)，只有一個(gè)許用為半徑的圓內(nèi)，只有一個(gè)許用碼字碼字c。由于。由于d(r, c) e，即，即r位于該圓內(nèi)，所以位于該圓內(nèi)，所以r一定是一定是禁用碼字。禁用碼字。 39碼的檢錯(cuò)與糾錯(cuò)能力碼的檢錯(cuò)與糾錯(cuò)能力l 證明證明 (2) 如果發(fā)送的碼字如果發(fā)送的碼字c出現(xiàn)了出現(xiàn)了t個(gè)隨機(jī)錯(cuò)誤變成了個(gè)隨機(jī)錯(cuò)誤變成了一個(gè)碼元序列一個(gè)碼元序列r，由已知得，由已知得( ) 1( , ).2d Cdt c r 設(shè)設(shè)c c是任意一個(gè)碼字是任意一個(gè)碼字 d(c, c) d(c, r)+ d(r, c)，( ) 1( ) 1( ) 1( )( , )( , )( , ).222d Cd Cd Cd Cdddr cr cr c 在在C的所有碼字中，的所有碼字中， c與與 r 的漢明距離最小。使用最小的漢明距離最小。使用最小距離譯碼方法時(shí)，必將距離譯碼方法時(shí)，必將 r