信息論與編碼 曹雪芹 Chap6

1、126.1 糾錯(cuò)編譯碼的基本原理與分析方法6.2 線性分組碼6.3 卷積碼3 信源編碼 提高數(shù)字信號(hào) 將信源的模擬信號(hào)轉(zhuǎn)變?yōu)閿?shù)字信號(hào) 降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮) 信道編碼 提高數(shù)字通信 數(shù)字信號(hào)在信道的傳輸過(guò)程中,由于實(shí)際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會(huì)產(chǎn)生誤碼。45是衡量傳輸質(zhì)量的重要指標(biāo)之一,它有幾種不同的定義。 碼元差錯(cuò)率/符號(hào)差錯(cuò)率 指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯(cuò)的碼元數(shù)所占的比例(平均值),簡(jiǎn)稱誤碼率。 是指差錯(cuò)概率 比特差錯(cuò)率 /比特誤碼率： 在傳輸?shù)谋忍乜倲?shù)中發(fā)生差錯(cuò)的比特?cái)?shù)所占比例 是指差錯(cuò)概率 對(duì)二進(jìn)制傳輸系統(tǒng),符號(hào)差錯(cuò)等效于比特差錯(cuò);對(duì)多進(jìn)制系統(tǒng)

2、,一個(gè)符號(hào)差錯(cuò)對(duì)應(yīng)多少比特差錯(cuò)卻難以確定6 根據(jù)不同的應(yīng)用場(chǎng)合對(duì)差錯(cuò)率有不同的要求: 在電報(bào)傳送時(shí),允許的比特差錯(cuò)率約為: 104105； 計(jì)算機(jī)數(shù)據(jù)傳輸,一般要求比特差錯(cuò)率小于: 108109； 在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯(cuò)率7 為定量地描述信號(hào)的差錯(cuò),定義差錯(cuò)圖樣E E=CR (模M ) 最常用的二進(jìn)制碼可當(dāng)作特例來(lái)研究,其差錯(cuò)圖樣等于收碼與發(fā)碼的模2加,即 E = C R 或 C = R E 設(shè)發(fā)送的碼字C 1 1 1 1 1 1 1 1 1 1 接收的碼字R 1 0 0 1 0 0 1 1 1 1 差錯(cuò)的圖樣E 0 1 1 0 1 1 0 0 0 0

3、 差錯(cuò)圖樣中的“1”既是符號(hào)差錯(cuò)也是比特差錯(cuò),差錯(cuò)的個(gè)數(shù)叫漢明距離。0:傳輸中無(wú)錯(cuò)1:傳輸中有錯(cuò)8 隨機(jī)差錯(cuò)： 差錯(cuò)是相互獨(dú)立的,不相關(guān) 存在這種差錯(cuò)的信道是無(wú)記憶信道或隨機(jī)信道 突發(fā)差錯(cuò)： 指成串出現(xiàn)的錯(cuò)誤,錯(cuò)誤與錯(cuò)誤間有相關(guān)性,一個(gè)差錯(cuò)往往要影響到后面一串字 E: 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 突發(fā)長(zhǎng)度= 4突發(fā)長(zhǎng)度= 69 從功能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼 檢錯(cuò)碼：用于發(fā)現(xiàn)差錯(cuò) 糾錯(cuò)碼：能自動(dòng)糾正差錯(cuò) 糾錯(cuò)碼與檢錯(cuò)碼在理論上沒(méi)有本質(zhì)區(qū)別,只是應(yīng)用場(chǎng)合不同,而側(cè)重的性能參數(shù)也不同。10 按照對(duì)信息序列的處理方法,有

4、分組碼和卷積碼 分組碼： 將k個(gè)信息碼元分成一組,由這k個(gè)碼元按照一定規(guī)則產(chǎn)生r個(gè)監(jiān)督碼元,組成長(zhǎng)度n = k + r的碼字 卷積碼： 先將信息序列分組,不同的是編解碼運(yùn)算不僅與本組信息有關(guān),而且還與前面若干組有關(guān)。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr11 按照碼元與原始信息位的關(guān)系,分為 線性碼：所有碼元均是原始信息元的線性組合,編碼器不帶反饋回路。 非線性碼：碼元并不都是信息元的線性組合,可能還與前面已編的碼元有關(guān),編碼器可能含反饋回路。 由于非線性碼的分析比較困難,早期實(shí)用的糾錯(cuò)碼多為線性碼,但當(dāng)今發(fā)現(xiàn)的很多好碼恰恰是非線性

5、碼。12 按照適用的差錯(cuò)類型,分成: 糾隨機(jī)差錯(cuò)碼:用于隨機(jī)差錯(cuò)信道,其糾錯(cuò)能力用碼組內(nèi)允許的獨(dú)立差錯(cuò)的個(gè)數(shù)來(lái)衡量。 糾突發(fā)差錯(cuò)碼:針對(duì)突發(fā)差錯(cuò)而設(shè)計(jì),其糾錯(cuò)能力主要用可糾突發(fā)差錯(cuò)的最大長(zhǎng)度來(lái)衡量13 前向糾錯(cuò)(FEC)： 發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯(cuò)能力的碼。 接收端信道譯碼器對(duì)接收碼字進(jìn)行譯碼,若傳輸中產(chǎn)生的差錯(cuò)數(shù)目在碼的糾錯(cuò)能力之內(nèi)時(shí),譯碼器對(duì)差錯(cuò)進(jìn)行定位并加以糾正。14 自動(dòng)請(qǐng)求重發(fā)(ARQ)： 發(fā)端發(fā)送檢錯(cuò)碼， 收端譯碼器判斷當(dāng)前碼字傳輸是否出錯(cuò)； 當(dāng)有錯(cuò)時(shí)按某種協(xié)議通過(guò)一個(gè)反向信道請(qǐng)求發(fā)送端重傳已發(fā)送的碼字(全部或部分)。15 混合糾錯(cuò)(HEC)： 是FEC與ARQ

6、方式的結(jié)合。 發(fā)端發(fā)送同時(shí)具有自動(dòng)糾錯(cuò)和檢測(cè)能力的碼組,收端收到碼組后,檢查差錯(cuò)情況,如果差錯(cuò)在碼的糾錯(cuò)能力以內(nèi),則自動(dòng)進(jìn)行糾正。 如果信道干擾很嚴(yán)重,錯(cuò)誤很多,超過(guò)了碼的糾錯(cuò)能力,但能檢測(cè)出來(lái),則經(jīng)反饋信道請(qǐng)求發(fā)端重發(fā)這組數(shù)據(jù)。 信息反饋(IRQ)： 收端把收到的數(shù)據(jù),原封不動(dòng)地通過(guò)反饋信道送回到發(fā)端,發(fā)端比較發(fā)的數(shù)據(jù)與反饋來(lái)的數(shù)據(jù),從而發(fā)現(xiàn)錯(cuò)誤,并且把錯(cuò)誤的消息再次傳送,直到發(fā)端沒(méi)有發(fā)現(xiàn)錯(cuò)誤為止。16 0:晴,1:雨 若10,01。收端無(wú)法發(fā)現(xiàn)錯(cuò)誤00晴1001110011雨能發(fā)現(xiàn)一個(gè)錯(cuò)誤禁用碼組 插入1位監(jiān)督碼后具有檢出1位錯(cuò)碼的能力,但不能予以糾正。17000晴010001111000

7、111雨晴 在只有1位錯(cuò)碼的情況下,可以判決哪位是錯(cuò)碼并予以糾正,可以檢檢出2位或2位以下的錯(cuò)碼。100011101110雨18 最大似然譯碼： 將接收到的碼字譯碼為與它的許用碼字,并且認(rèn)為這個(gè)許用碼字就是它所對(duì)應(yīng)的發(fā)送碼字,從而在碼字的糾錯(cuò)能力內(nèi)實(shí)現(xiàn)自動(dòng)糾錯(cuò)。 糾錯(cuò)編碼之所以具有檢錯(cuò)、糾錯(cuò)能力,是因?yàn)樵谛畔⒋a元之外加入了監(jiān)督碼。監(jiān)督碼不載信息,只是用來(lái)監(jiān)督信息碼在傳輸中有無(wú)差錯(cuò)。 糾錯(cuò)編碼所提高的可靠性,是以犧牲信道利用率為代價(jià)換取的。 監(jiān)督碼引入越多,檢錯(cuò)、糾錯(cuò)能力越強(qiáng),但信道的傳輸效率下降也越多。1920(4) 等重碼/定比碼設(shè)計(jì)碼字中的非0符號(hào)個(gè)數(shù)恒為常數(shù)，即 C 由全體重量恒等于 m

8、 的 n 重向量組成。5中取3等重碼可以檢測(cè)出全部奇數(shù)位差錯(cuò)，對(duì)某些碼字的傳輸則可以檢測(cè)出部分偶數(shù)位差錯(cuò)。21(2) 最大似然譯碼譯碼過(guò)程 由圖6.1.2可見(jiàn)：譯碼器接收到一個(gè)接收碼字 R 后，按編碼規(guī)則對(duì) R 進(jìn)行譯碼后輸出信息碼組的估值 m； 信息碼組與碼字 C 之間是有固定規(guī)則的，這相當(dāng)于信道譯碼器能給出碼字 C 的估值 C。當(dāng)CC時(shí)就出現(xiàn)了譯碼錯(cuò)誤。因?yàn)橹挥挟?dāng) C=C 時(shí)，m=m。22最大后驗(yàn)概率譯碼準(zhǔn)則 當(dāng)譯碼器收到某一個(gè)接收碼字R后，根據(jù)最大后驗(yàn)概率p(C/R)進(jìn)行譯碼判決，一定是譯碼錯(cuò)誤概率最小。 根據(jù)貝葉斯原理 似然函數(shù)：p(R/C)kiipp/pppppppi2 , 2 ,

9、1)(max)()()/(,)()()()()()(CRCRCRRCCCRCRCRCRCCC即具有最大值，要求條件概率最大就等效于則相同的先驗(yàn)概率如果所有碼字23 設(shè)每個(gè)碼字長(zhǎng)為 n，若接收碼字 R 與碼字 C 的距離為 d(R,C)，則條件概率 p(RC) 可表示為 最大化 p(RC) 等價(jià)于最小化 d(R,C)，所以使差錯(cuò)概率最小的譯碼是使接收向量 R 與輸出碼字 C 距離最小的譯碼。),(),(),(1)1 ()1 ()(CRCRCRCRdbbnbdbdnbpppppp) ,(),(min: CRCRCCddii24 信道編碼 在被傳輸信息中附加一些冗余碼冗余碼,即監(jiān)督碼元,利用附加碼元

10、與信息碼元間的約束關(guān)系加以校驗(yàn),以。 信源編碼減少了 冗余度是隨機(jī)的、無(wú)規(guī)律的 信道編碼增加了 冗余度是特定的、有規(guī)律的,故可利用其在接收端進(jìn)行檢錯(cuò)和糾錯(cuò)。25 傳輸冗余比特必然要?jiǎng)佑萌哂嗟馁Y源。 時(shí)間： 比如一個(gè)比特重復(fù)發(fā)幾次,或一段消息重復(fù)發(fā)幾遍,或根據(jù)收端的反饋重發(fā)受損信息組。 頻帶： 插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一是增大符號(hào)傳遞速率(波特率),結(jié)果就占用了更大的帶寬。 功率： 采用多進(jìn)制符號(hào),用8進(jìn)制ASK符號(hào)代替4進(jìn)制ASK符號(hào)來(lái)傳送2比特信息,可騰出位置另傳1冗余比特。 8進(jìn)制ASK符號(hào)的平均功率肯定比4進(jìn)制時(shí)要大,這就是動(dòng)用冗余的功率資源來(lái)傳輸冗

11、余比特。 設(shè)備復(fù)雜度： 加大碼長(zhǎng),采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實(shí)施糾錯(cuò)編碼的有效方法,代價(jià)是算法復(fù)雜度的提高,需動(dòng)用設(shè)備資源。26 信道編碼 按一定規(guī)則給數(shù)字序列m增加一些多余的碼元,使不具有規(guī)律性的信息序列 m 變換為具有某種規(guī)律性的數(shù)碼序列 C； 碼序列中的信息序列碼元與多余碼元之間是的； 信道譯碼器利用這種預(yù)知的編碼規(guī)則譯碼。檢驗(yàn)接收到的數(shù)字序列 R 是否符合既定的 規(guī)則,從而發(fā)現(xiàn) R 中是否有錯(cuò),或者糾正其中的差錯(cuò)； 根據(jù)來(lái)檢測(cè)/發(fā)現(xiàn)和糾正傳輸過(guò)程中產(chǎn)生的差錯(cuò)就是信道編碼的基本思想。27 糾錯(cuò)編碼的檢錯(cuò)糾錯(cuò)能力,要取決于碼組的碼距 碼距越大,檢錯(cuò)、糾錯(cuò)能力越強(qiáng)。 漢明距離

12、： 二個(gè)碼組對(duì)應(yīng)碼位碼元不同的個(gè)數(shù)。 最小碼距dmin： 一個(gè)碼組的集合中任意二個(gè)碼組間的最小漢明距離。 碼重W： 碼組中非0的數(shù)目。28 定理：若糾錯(cuò)碼的最小距離為dmin，可以檢測(cè)出任意小于等于l = dmin1個(gè)差錯(cuò)可以糾正任意小于等于 個(gè)差錯(cuò)21mindt可以檢測(cè)出任意小于等于l同時(shí)糾正小于等于t個(gè)差錯(cuò)， 其中l(wèi)、t滿足： l + t dmin1 t l29 編碼效率： 一個(gè)組中信息所占的比重nkR k：信息碼元的數(shù)目 n：編碼組碼元的總數(shù)目 n = k+ r r：監(jiān)督碼元的數(shù)目30 奇偶校驗(yàn)碼(n，n-1)(k+1，k) 偶校驗(yàn)碼字0110pmmmk31(2) 偶（或奇）校驗(yàn)方法 一

13、個(gè)奇偶校驗(yàn)位 p 為偶校驗(yàn)位 m0+m1+m2+mk1+p=0 (mod 2) 則 C =(m0,m1,m2,mk1,p) 為一個(gè)偶校驗(yàn)碼字。C 中一定有偶數(shù)個(gè)“1” 所有可能的 C 的全體稱為一個(gè)碼率為 k/(k+1) 的(k+1,k) 偶校驗(yàn)碼； 確定校驗(yàn)位 p 的編碼方程為 p= m0+m1+m2+mk1 當(dāng)差錯(cuò)圖案 E 中有奇數(shù)個(gè)“1”，即 R 中有奇數(shù)個(gè)位有錯(cuò)時(shí)，可以通過(guò)校驗(yàn)方程是否為0判斷有無(wú)可能傳輸差錯(cuò)。 校驗(yàn)方程為1表明一定有奇數(shù)個(gè)差錯(cuò)，校驗(yàn)方程為0表明可能有偶數(shù)個(gè)差錯(cuò)。32多個(gè)奇偶校驗(yàn)位一個(gè)校驗(yàn)位可以由信息位的部分或全部按校驗(yàn)方程產(chǎn)生；例如 C 是一個(gè)對(duì)陣列消息進(jìn)行垂直與水平

14、校驗(yàn)以及總校驗(yàn)的碼字；其碼率為2mod1, 1 , 0, 2mod1, 1 , 0, 2mod111) 1(1010,10,10,1,0, 11, 10, 1,01,00,0sitjjstitssijijstjjititstsststssttmmptjmpsimpppppmmpmmsttstsststRCl當(dāng)校驗(yàn)位數(shù)增加時(shí)，可以檢測(cè)到差錯(cuò)圖案種類數(shù)也增加，同時(shí)碼率減小。33(3) 重復(fù)消息位方法n重復(fù)碼：碼率為 1/n，僅有兩個(gè)碼字 C0和 C1，傳送1比特(k=1)消息；C0=(000)，C1=(111)n重復(fù)碼可以檢測(cè)出任意小于 n/2 個(gè)差錯(cuò)的錯(cuò)誤圖案 BSC信道：pb1/2，n比特傳輸

15、中發(fā)生差錯(cuò)數(shù)目越少，概率越大 (1pb)n pb(1pb)n 1 pbt(1pb)n t pbn 總認(rèn)為發(fā)生差錯(cuò)的圖案是差錯(cuò)數(shù)目較少的圖案，當(dāng)接收到重復(fù)碼的接收序列 R 中“1”的個(gè)數(shù)少于一半時(shí)，認(rèn)為發(fā)送的是C0，否則認(rèn)為是 C1。圖6.1.7所示糾1個(gè)任意差錯(cuò)的3重復(fù)碼。34 6.2.1 有噪信道編碼定理 定理6.2 設(shè)有一個(gè)離散無(wú)記憶平穩(wěn)信道，其信道容量為C。當(dāng)信息傳輸率RC，只要碼長(zhǎng)n足夠長(zhǎng)，則總存在一種編碼，可以使平均譯碼錯(cuò)誤概率任意小。 這個(gè)定理稱為有噪信道編碼定理，又稱為香農(nóng)第二定理。 35 通過(guò)一個(gè)有噪信道可以實(shí)現(xiàn)幾乎無(wú)失真?zhèn)鬏?，這與人們通過(guò)一個(gè)有噪信道可以實(shí)現(xiàn)幾乎無(wú)失真?zhèn)鬏敚@

16、與人們的直觀想象似乎是大相徑庭的，而定理的證明也是非常巧的直觀想象似乎是大相徑庭的，而定理的證明也是非常巧妙的。香農(nóng)巧妙地先，他不去構(gòu)造理想的好碼，而是用隨妙的。香農(nóng)巧妙地先，他不去構(gòu)造理想的好碼，而是用隨機(jī)編碼的方法得到所有可能生成的碼的集合，然后在碼集機(jī)編碼的方法得到所有可能生成的碼的集合，然后在碼集合中隨機(jī)選擇一個(gè)碼作為輸入碼序列，最后計(jì)算這樣隨機(jī)合中隨機(jī)選擇一個(gè)碼作為輸入碼序列，最后計(jì)算這樣隨機(jī)選擇的一個(gè)碼在碼集合上的平均性能。在譯碼時(shí)，利用了選擇的一個(gè)碼在碼集合上的平均性能。在譯碼時(shí)，利用了聯(lián)合典型序列的概念，即將接收序列譯成與其聯(lián)合典型的聯(lián)合典型序列的概念，即將接收序列譯成與其聯(lián)合

17、典型的碼字這種譯碼方法不是最優(yōu)譯碼，但便于理論分析。碼字這種譯碼方法不是最優(yōu)譯碼，但便于理論分析。36 定義定義6.6 設(shè) 是長(zhǎng)為n的隨機(jī)序列對(duì)，且 則在這些隨機(jī)序列對(duì)中同時(shí)滿足以下條件的序列對(duì)稱為聯(lián) 合典型序列。(,)ijx y1()()nijijkkkpp x yx y1log(),ipH Xnxix即即 是是X的的典型序列；典型序列；(1)(2)1log(),jpH Xny即即 是是X的的典型序列；典型序列；1log(),ijpH XYnx , yiy(3)是任意小的正數(shù)。是任意小的正數(shù)。聯(lián)合聯(lián)合典型序列的全體構(gòu)成的集合稱為典型序列的全體構(gòu)成的集合稱為聯(lián)合聯(lián)合典型序典型序列集列集，記作，

18、記作()GXY37按照以上定義可以得到聯(lián)合漸進(jìn)等分割性。對(duì)于任意小的正數(shù)0,0,當(dāng)n足夠大時(shí)，有(1) 典型列集和聯(lián)合典型列集的概率滿足：()1( )1()1rrrP GXP G YP GXY ()()( )( )()()2()22()22()2n H Xn H Xin H Yn H Yjn H XYn H XYijpppxyx y(2) 典型列和聯(lián)合典型列出現(xiàn)的概率滿足：38典型序列典型序列 是輸入端高概率出現(xiàn)的序列，典型序列是輸入端高概率出現(xiàn)的序列，典型序列 是輸是輸出端高概率出現(xiàn)的序列，而聯(lián)合典型序列對(duì)出端高概率出現(xiàn)的序列，而聯(lián)合典型序列對(duì) 則是信則是信道輸入和輸出之間關(guān)聯(lián)密切且經(jīng)常出現(xiàn)的序列對(duì)。也就是道輸入和輸出之間關(guān)聯(lián)密切且經(jīng)常出現(xiàn)的序列對(duì)。也就是說(shuō)，當(dāng)某一輸入典型序列說(shuō)，當(dāng)某一輸入典型序列 發(fā)送時(shí)，必定高概率地以和它發(fā)送時(shí)，必定高