第6章信道編碼理論6.1

概述6.2分組編碼6.3卷積碼6.4級聯(lián)碼6.5

Turbo碼6.6網(wǎng)格編碼調(diào)制(TCM)習(xí)題6.1概述6.1.1信道編碼的基本概念數(shù)字信號在傳輸過程中,不可避免地要受到熱噪聲和脈沖噪聲等的污染。在這兩種噪聲的影響下,被傳送的信息數(shù)據(jù)將引起兩種不同類型的差錯,即隨機分散出現(xiàn)的隨機差錯和成串出現(xiàn)的突發(fā)差錯,從而出現(xiàn)在通信接收端收到的數(shù)據(jù)與發(fā)送端實際發(fā)出的數(shù)據(jù)不一致的現(xiàn)象。為了保證通信系統(tǒng)的差錯在許可的范圍內(nèi),必須對通信可靠性要求高的系統(tǒng)加入差錯控制編碼措施。信道編碼就是用來減小甚至消除信道噪聲產(chǎn)生差錯的一種主要措施。差錯控制編碼的原理是:發(fā)送方對被傳輸?shù)男畔?shù)據(jù)進行分組,然后按某種編碼規(guī)則算法附加上一定的冗余位,構(gòu)成一個碼字后再向信道發(fā)送。接收方收到編碼數(shù)據(jù)(可能有差錯)后進行校驗,即檢查信息位和附加的冗余位之間的關(guān)系,以檢查傳輸過程中是否有差錯發(fā)生。實現(xiàn)這種編碼的設(shè)備叫信道編碼器。當(dāng)每個k位信息組按照編碼規(guī)則加上足夠的r個校驗位而組成k+r位的碼組后,這樣的碼組(也叫碼字)就不僅能發(fā)現(xiàn)傳輸中出現(xiàn)的差錯,甚至具有糾正這類差錯的能力。受到污染的信息數(shù)據(jù)在到達接收端后,由相應(yīng)的信道譯碼器對受到污染的信息數(shù)據(jù)進行反變換,即譯碼。通常,經(jīng)過譯碼的數(shù)據(jù)是原始發(fā)送信息數(shù)據(jù)的精確復(fù)制品,或者是帶有可以被接受的差錯的復(fù)制品。衡量編碼性能好壞的一個重要參數(shù)是編碼效率R,其中,n表示碼字的位數(shù),k表示數(shù)據(jù)信息的位數(shù),r表示冗余位(監(jiān)督位)的位數(shù)。上述編碼就是常見的分組編碼。長度為n的“碼字”共有2n個,但其中只有2k個許用碼字(組),其余2n－2k個是禁用碼字。6.1.2差錯控制工作方式常用的差錯控制工作方式主要有三種:前向糾錯(簡稱FEC)、檢錯重發(fā)(簡稱ARQ)和混合糾錯(簡稱HEC)。它們的系統(tǒng)構(gòu)成如圖6.1所示。圖6.1差錯控制工作方式前向糾錯方式的信道編碼器的發(fā)送端發(fā)出可以糾正錯誤的碼,接收端可以發(fā)現(xiàn)并糾正傳輸中的某些錯誤。其特點是單向傳輸,實時性好,但譯碼設(shè)備較復(fù)雜。在檢錯重發(fā)方式中,發(fā)射機中的信道編碼器發(fā)出能夠發(fā)現(xiàn)錯誤的編碼信號。接收端譯碼后如果未發(fā)現(xiàn)差錯,則通過反向信道向發(fā)送端反饋一個“確認(rèn)”(ACK)回執(zhí)信號,接收端譯碼后如果發(fā)現(xiàn)有傳輸錯誤,則通過反向信道向發(fā)送端反饋一個“否認(rèn)”(NAK)回執(zhí)信號,發(fā)送端再把前面發(fā)送的信息重新發(fā)送一次,直至接收端能正確接收為止。有三種檢錯重發(fā)方式,即停發(fā)等候重發(fā)(SW-ARQ)、退N步重發(fā)(go-back-N-ARQ)和選擇重發(fā)(S-ARQ)。SW-ARQ(stop-and-waitARQ)也稱停等法。在此系統(tǒng)中,發(fā)送端每發(fā)送一幀后就要停下等待接收方的確認(rèn)返回,僅當(dāng)接收方確認(rèn)正確接收后再繼續(xù)發(fā)送下一幀。如果接收端檢測出錯誤,則反饋一個否認(rèn)信號(NAK),發(fā)送端接到NAK信號后重發(fā)前一個碼組,并再次等候ACK或NAK信號,如圖6.2所示。這種方式由于在兩個碼組之間有停頓時間,所以傳輸效率低,常在數(shù)據(jù)通信中應(yīng)用。圖6.2

SW-ARQ工作原理示意圖

SW-ARQ法的實現(xiàn)過程如下:發(fā)送方每次僅將當(dāng)前信息幀作為待確認(rèn)的幀保留在緩沖存儲器中。當(dāng)發(fā)送方開始發(fā)送信息幀時,隨即啟動計時器。當(dāng)接收方檢測到一個出錯(E)的信息幀時,便舍棄(D)該幀。當(dāng)接收方收到無差錯的信息幀后,即向發(fā)送方返回一個確認(rèn)幀。若發(fā)送方在規(guī)定的時間內(nèi)未能收到確認(rèn)幀(即計時器超時),則應(yīng)重發(fā)存于緩沖器中待確認(rèn)的信息幀;若發(fā)送方在規(guī)定的時間內(nèi)收到確認(rèn)幀,即將計時器清零，繼而開始下一幀的發(fā)送。此方案最主要的優(yōu)點就是所需的緩沖存儲空間最小,因此在鏈路端使用簡單終端的場合中被廣泛采用。

go-back-N-ARQ是當(dāng)接收方檢測出失序的信息幀后,要求發(fā)送方重發(fā)最后一個正確接收的信息幀之后的所有未被確認(rèn)的幀,或者當(dāng)發(fā)送方發(fā)送了N幀后,若發(fā)送該N幀的前一幀在計時器超時后仍未返回其確認(rèn)信息,則該幀被判定為出錯或丟失。對接收方來說,因為這一幀出錯,就不能以正確的序號向它的終端遞交數(shù)據(jù),對其后發(fā)送來的N幀也可能都不能接收而丟棄。因此,發(fā)送方發(fā)現(xiàn)這種情況后,就不得不重新發(fā)送該出錯幀及其后的N幀,這就是go-back-N(退回N)法名稱的由來。go-back-N-ARQ法的工作過程如圖6.3所示。圖中假定發(fā)送完8號幀后,發(fā)現(xiàn)2號幀的確認(rèn)返回在計時器超時后還未收到,則發(fā)送方只能退回從2號幀開始重發(fā)。圖6.3

go-back-N-ARQ工作原理示意圖

S-ARQ系統(tǒng)的發(fā)送端也是不停頓地發(fā)送信號。當(dāng)接收方發(fā)現(xiàn)某幀出錯后,其后繼續(xù)送來的正確的幀雖然不能立即遞交給接收端的終端,但接收端仍可收下來,并存放在一個緩沖區(qū)中,同時要求發(fā)送端重新傳送出錯的那一幀。一旦收到重新傳來的正確幀后,就可與原已存于緩沖區(qū)中的其余幀一并按正確的順序遞交給終端。與退N步重發(fā)不同的是,它的發(fā)送端收到接收端返回的NAK信號后只重發(fā)有錯誤的那個碼組。其工作原理示意圖如圖6.4所示。顯然,選擇重發(fā)系統(tǒng)的傳輸效率高,當(dāng)然其設(shè)備也復(fù)雜一些。圖6.4

S-ARQ工作原理示意圖檢錯重發(fā)方式的特點是譯碼設(shè)備簡單,但需要雙工鏈路,實時性差。信道編碼器輸出碼的檢錯能力,一般大于其糾錯能力。在混合糾錯方式中,接收端若檢測到能夠糾正的錯誤,則進行糾錯處理;若檢測到無法糾正的錯誤,則向發(fā)送端返回否認(rèn)信號,接收端收到此信號后重新發(fā)送傳輸中出錯的碼組。此方式的實時性和復(fù)雜性介于前向糾錯與檢錯重發(fā)方式之間。6.1.3差錯控制編碼的分類按照實現(xiàn)的功能,可將差錯控制碼分為檢錯碼和糾錯碼。當(dāng)然,糾錯碼必須具有檢錯功能,而具有檢錯能力的碼不一定具有糾錯功能。按照信息碼元與監(jiān)督碼元之間的函數(shù)關(guān)系,可將差錯控制碼分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的,即滿足一組線性方程式,則稱為線性碼,反之稱為非線性碼。實際應(yīng)用的一般都是線性碼。按照監(jiān)督碼元是否僅與本碼組內(nèi)的信息碼元有關(guān)系,可將差錯控制碼分為分組碼和卷積碼。在分組碼中,每個碼組內(nèi)的監(jiān)督碼元或許僅與該碼組內(nèi)的信息碼元有關(guān);在卷積碼中,每個碼組內(nèi)的監(jiān)督碼不僅與本碼組內(nèi)的信息碼元有關(guān),而且還與前面若干碼組內(nèi)的信息碼元有關(guān)。按照編碼后的信息碼元組是否與編碼前的相同,可將差錯控制碼分為系統(tǒng)碼和非系統(tǒng)碼。在系統(tǒng)碼中,編碼后的信息碼元組保持不變;在非系統(tǒng)碼中,編碼后的信息碼元被校驗位分隔。常用的線性分組碼一般為系統(tǒng)碼。另外,按照碼字的結(jié)構(gòu)是否具有循環(huán)性,可以分為循環(huán)碼和非循環(huán)碼;按照糾錯的類別,可以分為糾隨機錯誤的碼和糾突發(fā)錯誤的碼。6.1.4差錯控制編碼的基本原理差錯編碼的基本思想是在被傳輸信息中增加一些冗余碼,利用附加碼元和信息碼元之間的約束關(guān)系加以校驗,以檢測和糾正錯誤。增加冗余碼的個數(shù)可增加糾錯和檢錯能力。

1.碼長、碼重和碼距編碼碼組的碼元總位數(shù)稱為碼組的長度,簡稱碼長。如“1011”碼長為4,“110011”碼長為6。碼組中,“1”碼元的數(shù)目稱為碼組的重量,簡稱碼重。如“10110”碼重為3。兩個等長碼組之間對應(yīng)位上不同碼元的個數(shù)稱為這兩個碼組的距離,簡稱碼距。如“11000”與“11011”有兩個對應(yīng)位不同,故碼距為2,常稱此為漢明距離。碼組集中任意兩個碼字之間距離的最小值稱為最小碼距,用dmin表示。最小碼距是碼的一個重要參數(shù),它是衡量編碼檢錯和糾錯能力的重要依據(jù)。

2.檢錯和糾錯能力最小碼距與檢錯、糾錯能力的關(guān)系:為了能夠檢測e個錯誤,要求dmin≥e+1;為了能夠糾正t個錯誤,要求dmin≥2t+1;為了能夠糾正t個錯誤,同時檢測e個錯誤(e＞t),要求dmin≥t+e+1。上述檢錯及糾錯能力與最小碼距的關(guān)系,可以用圖6.5所示的幾何圖形加以說明。圖6.5(a)中,C表示某一碼組,當(dāng)誤碼不超過e個時,該碼組的位置移動范圍將不超出以它為圓心、以e為半徑的圓。只要其他任何許用碼組不落入此圓內(nèi),則碼組C就不會與其他碼組混淆,這就意味著只要碼組C與其他任何許用碼組之間的最小碼距不小于e+1,就可以檢測出碼組C發(fā)生了e個錯誤。圖6.5(b)中,C1、C2分別表示兩個許用碼組,當(dāng)各自的誤碼不超過t時,若最小碼距不小于2t+1,則可根據(jù)碼組落在哪個圓內(nèi)正確判斷為C1或C2,即可以糾正錯誤。圖6.5(c)中表示許用碼組C1發(fā)生e個錯誤,而許用碼組C2發(fā)生t個誤碼(e≥t)。當(dāng)最小碼距不小于t+e+1時,若C1及C2的誤碼不超過t個,則可根據(jù)碼組落在哪個圓內(nèi)正確判斷為C1或C2;若C1發(fā)生了e個錯誤,則該碼組的位置移動范圍仍沒與碼組C2的位置移動范圍相混淆,仍可檢測出碼組C1發(fā)生了e個錯誤。圖6.5碼距與糾錯、檢錯能力的關(guān)系例如,若將晴天編為“1”,雨天編為“0”,則dmin=1,無法檢測錯誤和糾正錯誤。若將天氣情況編為(2,1)碼,兩個許用碼組是11與00,dmin=2,收端譯碼,當(dāng)出現(xiàn)01、10禁用碼組時,這種錯誤可以檢測出來,但無法糾正。如果將天氣情況編為(3,1)碼,兩個許用碼組是111與000,dmin=3,可以檢測出一個或兩個錯誤碼元,糾正一個錯誤碼元。當(dāng)收端出現(xiàn)兩個或三個1時,判為1,否則判為0。此時,可以糾正單個錯誤,或者該碼可以檢出兩個錯誤。顯然采用這種譯碼方法所得到的誤判(即誤碼)概率是最小的,這稱為最大似然譯碼準(zhǔn)則。6.1.5最大似然譯碼準(zhǔn)則設(shè)發(fā)送碼字為C=(cn－1,cn－2,…,c0),它有2k個許用碼組,當(dāng)接收碼字為R=(c′n－1,c′n－2,…,c0′)時,計算2k個條件概率P(R|Ci)(i=1,2,…,2k)。若條件概率P(R|CL)為最大,則認(rèn)為發(fā)送的碼字為CL。這就是最大似然準(zhǔn)則。

P(R|CL)可用下式計算:(6.1)式中,ci′為接收碼字的第i個碼元,cLi為許用碼字CL的第i個碼元。設(shè)信道為二進制對稱信道,錯誤轉(zhuǎn)移概率為Pe,接收碼字R與許用碼字CL的碼距為d,則上式可寫成P(R|CL)=(1－Pe)n－dPde

(6.2)由于Pe＜0.5,故P(R|CL)隨d增大而單調(diào)減小。所以,當(dāng)所有碼字的發(fā)送概率相同時,按最大似然概率譯碼等效于按最小碼距譯碼,即接收碼字與哪一個許用碼字的碼距最小,就認(rèn)為傳送的是哪個碼字。6.2分組編碼信息論指出,在固定信噪比下,可通過增加波形的復(fù)雜度使消息錯誤概率趨近于零。只要總信息傳送速率低于信道容量,上述結(jié)論就有效。因此,迫切尋找一種特殊的技術(shù),在不增加傳送功率的條件下降低消息誤碼率,或?qū)崿F(xiàn)同樣消息誤碼率的條件下降低傳送功率。同時構(gòu)造傳送波形,能夠緩解信道的失真,并在合理的復(fù)雜度下接收機能正常接收。假設(shè)信源已經(jīng)通過理想信源編碼,它的輸出就是一個獨立等概的二進制數(shù)字序列。信源輸出序列在編碼器中加上一些為在接收端能夠糾正傳輸錯誤所必需的結(jié)構(gòu)。在很多情形下,編碼器輸入和輸出字符為二進制,為了使信源序列加上一些必要的結(jié)構(gòu)組成傳送信號,二進制輸入/輸出編碼器的輸出符號速率應(yīng)比它的輸入比特速率高。假設(shè)信道為轉(zhuǎn)移概率為Pr(y|x)的二進制對稱信道,其中的y、x∈｛0,1｝。當(dāng)信道的輸入和輸出字符集相同時,信道被稱為硬判決信道,與其相關(guān)的解碼器被稱為硬判決解碼器。在討論卷積碼時,信道將允許輸出符號的符號集大于輸入符號集。大的輸出符號集使信道可以給譯碼器提供判決可靠性信息。當(dāng)可靠性信息從信道輸出時,信道被稱為軟判決信道,其相關(guān)的譯碼器被稱為軟判決譯碼器。6.2.1基本概念分組編碼技術(shù)就是那些以信息分組為單位進行處理的編碼技術(shù)。二進制輸入/輸出分組編碼器把k位二進制信息符號作為一個分組,然后把它映射為n位二進制為一分組的輸出符號。分組碼的編碼速率定義為R=k/n,它等于每次使用信道的信息傳送速率,即編碼器的每一個輸出符號被傳送的時候,就有R比特的信息被傳送。一個由n個信道使用組成的分組傳送nR=n(k/n)=k比特的信息。如要通過編碼來提高信號的可靠性,信息傳送速率必須低于信道容量。對于二進制輸入信道,它的信道容量最大為每次使用信道傳送1比特信息,所以R≤CN≤1.0,同樣得出k≤n。

1.分組編碼的定義

k位信息比特的分組用一k維矢量Wm=wm(k－1)…wm2wm1wm0來表示,其中每個wmi取值為0或1,腳標(biāo)m表示正考慮的特定的消息。對應(yīng)2k種可能的編碼器輸入消息有2k個二進制k維矢量Wm,信源輸出消息m的概率表示為QM(m),對于假設(shè)的二進制對稱信道,所有輸出的消息是等概的,所以對所有的m有QM(m)=2－k。編碼器映射為二進制n維矢量Xm=xm0xm1xm2…xm(n－1)。這種映射是一對一的映射,意味著不會出現(xiàn)兩個消息對應(yīng)同一X的情形,即對于m≠m′,有Xm≠Xm′。分組碼(n,k)是消息m所對應(yīng)的Xm的集合,每個Xm是編碼的一個碼字,共有2n種可能的碼字和2k種可能的消息。因為k<n,消息數(shù)2k小于可能的碼字?jǐn)?shù)2n,所以并不是所有的n維矢量都用作碼字。一般來說,所用碼字占總可用碼字的比值為2k－n=2k(1－1/R),因為R<1.0,很顯然這個比值隨k的增加而降低。碼字的糾錯能力表明并不是所有可能的n維矢量都能用作碼字。正因為這樣,才有可能通過挑選碼字來生成編碼,使得在接收端的一個碼字與另一個碼字混淆前必然發(fā)生傳輸錯誤。

2.漢明距離和漢明碼表6.1給出了一組典型的分組編碼。這組分組編碼的信息比特是4位(k=4),把它們映射成了長度為7的碼字(n=7),碼率為R=4/7。因為n=7,有27=128種可能的碼字,現(xiàn)只選擇其中的16種來編碼。檢查一下表6.1中的碼字,就會發(fā)現(xiàn)任意兩個碼字間至少有3處不同,這意味若一個或兩個傳輸錯誤不可能使其中一個碼字轉(zhuǎn)變?yōu)榱硪粋€碼字。在這種情況下,譯碼器雖然不能夠糾正這些錯誤,但可以告知用戶傳輸錯誤已經(jīng)發(fā)生;有3個錯誤發(fā)生時,就能夠把傳輸?shù)拇a字變成另一可用碼字,這樣解碼器就不會檢測出或不會糾正這些錯誤。例如,如果對應(yīng)消息數(shù)2的碼字被傳輸,且在第1,2和4(從右數(shù))的位置上發(fā)生錯誤,接收到的碼字正好是對應(yīng)消息數(shù)3的碼字。如發(fā)生的錯誤超過3個時,只有在接收到的碼字矢量不是可用碼字時才能夠檢測出錯誤。成對碼字Xm和Xm′間相應(yīng)位置不同的數(shù)目是一種很重要的特性,被稱為碼字間的漢明距離,記為dH或dH(Xm′,Xm′)。碼字集合中任意兩個碼字間的最小漢明距離被稱為碼的最小距離,記為dmin。表6.1中的碼是一個漢明碼,漢明碼的最小碼距是3,后面將會證明它能夠糾正任意傳輸碼字分組中的單一錯誤。成對碼字間的漢明距離等于兩碼字模2矢量中1的個數(shù)。兩碼字的模2矢量就是矢量的各分量(無進位)逐項模2求和,任意碼字矢量中1的個數(shù)稱為這個碼字的漢明重量(即碼重),記為wH或wH(Xm)。

3.錯誤矢量碼字Xm在二進制對稱信道上傳輸,為了方便起見,用一個n維錯誤矢量建立錯誤模型來表征在傳輸中哪些位置發(fā)生了錯誤。錯誤矢量在每一位沒有發(fā)生錯誤的位置為0,每一位發(fā)生錯誤的位置為1。這樣,二進制對稱信道的輸出矢量就是傳送的碼字矢量Xm和錯誤矢量e的模2和。例如,一個7比特的碼字在1,2和4位置發(fā)生錯誤時,7維的錯誤矢量為e=0001011,如對應(yīng)于表6.1的碼中消息2(m=2)的碼字被傳送,并按上述錯誤矢量發(fā)生失真,則接收到的7維矢量將是:(6.3)接收到的n維矢量標(biāo)記為y=yn－1…y2y1y0。假設(shè)信道是無記憶的,意味著任意特定符號發(fā)生錯誤的概率獨立于發(fā)生在所有其他符號的事件。進一步假設(shè)二進制對稱信道的轉(zhuǎn)移概率Pr(yi|xi)對所有的傳送都是常數(shù),因而(6.4)對于二進制對稱信道有Pr(1|0)=Pr(0|1)=p,所以Pr(0|0)=

Pr(1|1)=1－p,則二進制對稱信道引發(fā)錯誤使e=0001011的概率為

Pr［e=0001011］=p×p×(1－p)×(1－p)×(1－p)(6.5)一般來說,二進制對稱信道在長度為n的分組碼字的特定位置引發(fā)e′個錯誤序列的概率為(6.6)Pr［在碼字的特定位置發(fā)生e′個錯誤］這一結(jié)論被用來計算Pr(y|xm),即在給定xm被傳輸?shù)那疤嵯陆邮盏統(tǒng)的概率,這個概率可由下式給出:Pr(y|xm)=pdH(1－p)n－dH

(6.7)其中dH是xm和y之間的漢明距離。長度為n且包含e′個錯誤的特定序列的數(shù)目可由下面的二項式系數(shù)給出:(6.8)因而,二進制對稱信道引發(fā)的在長度為n的分組中包含e′個錯誤序列的概率為

Pr［在長度為n的分組中發(fā)生e′個錯誤］(6.9)=

4.最佳譯碼準(zhǔn)則譯碼器的輸入是接收到的矢量y,預(yù)先已知全部碼字xm(m=0,1,…,2k－1)的集合。信源輸出消息的概率QM(m)和信道轉(zhuǎn)移概率Pr(y|xm)。利用上述信息,設(shè)計譯碼器對傳送的碼字做出“最佳可能”的估計?！白罴芽赡堋惫烙嬍侵腹烙嫷慕Y(jié)果提供給信息用戶的平均比特錯誤的數(shù)值最小。比特錯誤概率記作Pb。首先考慮比較簡單的情況。我們按以下方法選擇譯碼規(guī)則:在不考慮某個特定碼字發(fā)生錯誤所引起的信息比特錯誤數(shù)量的情況下,選擇譯碼準(zhǔn)則使得對傳送碼字做出不正確估計的概率最小。分組譯碼的錯誤概率記為PB，譯碼器對傳送的碼字的估值記為，已知接收到的矢量為y和＝xm，如xm確實是被傳送的碼字時則譯碼器的估值就是正確的。,

P(A)≠0(6.10)因為y有2n種可能，而碼字只需要2k個，在這種準(zhǔn)則下就會有多個y映射到同一xm的情形。所有對應(yīng)于最佳譯碼器的估值=xm的y的集合稱為xm的判決區(qū)域，有2n種取值可能的y的整個空間被劃分為2k個互不重疊的判決區(qū)域，對每一可能的消息都存在一判決區(qū)域。為計算后驗概率Pr(xm|y),利用貝葉斯準(zhǔn)則由概率理論有(6.11)因而(6.12)等式右端的分母為(6.13)它是正數(shù)且獨立于消息m。因此,解碼準(zhǔn)則又可以變?yōu)?選擇使得式(6.14)最大的xm作為譯碼器的估值,這個等式在已知式(6.4)的信道轉(zhuǎn)移概率和消息的先驗概率時可求解。(6.14)當(dāng)所有消息的概率相等時,譯碼準(zhǔn)則可進一步簡化為選擇使得Pr［y|xm］最大的xm作為譯碼器的估值。對于二進制對稱信道,Pr［y|xm］由式(6.7)給出。因為對數(shù)對于遞增變量是單調(diào)遞增函數(shù),所以,Pr［y|xm］的對數(shù)也可以在不改變?nèi)魏巫g碼器判決的情況下應(yīng)用到最大似然譯碼準(zhǔn)則中。取式(6.7)的對數(shù),對于二進制對稱信道(BSC)的譯碼準(zhǔn)則可表示為:選擇使得式(6.15)最大的xm作為譯碼器的估值。(6.15)在等式中,dH是接收到的n維矢量與所考慮的n維碼字間的漢明距離。因為對于p<0.5,有l(wèi)g［p/(1－p)］,所以使式(6.15)最大即等效為使dH最小,因而譯碼準(zhǔn)則就是最小距離譯碼準(zhǔn)則。對于p<0.5的二進制對稱信道(BSC),譯碼器將選擇在漢明距離上與接收到的矢量y最近的碼字作為它的估值。例如,現(xiàn)有如表6.1給出的n=7、k=4的漢明碼,假設(shè)二進制對稱信道(BSC)的輸出為n維矢量y=0101101,譯碼器要計算矢量y與所有可能的碼字xm間的漢明距離dH(y,xm),譯碼器將輸出與矢量y和漢明距離最小的碼字xm作為它的估值。本例最小距離是1,消息。上述譯碼準(zhǔn)則可實現(xiàn)最小可能的分組譯碼錯誤概率。我們假設(shè)分組譯碼錯誤概率的最小化也意味著所譯出的比特錯誤概率最小化。通過合理設(shè)計消息與碼字的映射關(guān)系,可使上面的假設(shè)成立。選擇消息的映射應(yīng)使得最可能的分組譯碼錯誤所引起的比特錯誤數(shù)最小。

5.譯碼區(qū)域與錯誤概率最小距離譯碼器是通過找尋與接收的n維矢量y最接近的碼字xm來進行工作的。正如前面提到的,從概念上這也可通過把所有可能接收的矢量y的空間劃分出區(qū)域來實現(xiàn)。在任一區(qū)域內(nèi)的所有矢量y都選擇在漢明距離上最近的特定碼字xm而不是其他xm′,因而譯碼器可通過找尋包含接收矢量y的判決區(qū)域并把估值取為與這一區(qū)域關(guān)聯(lián)的碼字xm。表6.2給出了表6.1中漢明碼所有可能的7維矢量的集合的劃分。表6.2中的第一列含有編碼中的16個碼字,表中其他列包含了其他所有的7維矢量,每個碼字所對應(yīng)的譯碼區(qū)域就是包含碼字本身且與碼字同處一行的7維矢量的集合。表6.2中所有的128個二進制7維矢量分成8列16行?？梢允止を炞C的是相應(yīng)碼字的判決區(qū)域內(nèi)的任一7維矢量與碼字間的漢明距離為0或1,同樣可以驗證的是與一碼字間的漢明距離為0或1的所有7維矢量都在與這個碼字相應(yīng)的判決區(qū)城內(nèi),碼字本身也在其譯碼區(qū)域內(nèi)。表6.2這樣的譯碼表一旦給定,就可計算分組譯碼的錯誤概率。當(dāng)碼字xm被發(fā)送,傳送中發(fā)生錯誤使得接收到的n維矢量y落在了不同碼字xm′的譯碼區(qū)域時,就會發(fā)生分組譯碼錯誤。把消息m或碼字xm的譯碼區(qū)域標(biāo)記為Λm,Λm外的所有n維矢量標(biāo)記為。當(dāng)接收到的n維矢量y處在Λm時,譯碼器輸出為=xm。只要是碼字xm被發(fā)送,而接收的矢量y處在Λm時,就會發(fā)生譯碼錯誤。假定消息m被傳送,則條件分組錯誤概率PBm為(6.16)其中的和式是對所有不在消息m對應(yīng)的判決區(qū)域的n維矢量y求和。上式中對消息概率可通過對所有消息取平均而去掉條件,于是得到:［長度為7的分組中有e′個錯誤］(6.17)例如,對于表6.1中的漢明碼和表6.2中給定的譯碼表,任一傳送的消息當(dāng)有超過單個傳輸錯誤發(fā)生時,譯碼錯誤就會發(fā)生,因而,PBm獨立于消息m,且對于任一消息m,它的先驗概率為QM(m)=2－k,所以分組錯誤概率PB為上式計算相對容易,可得到PB作為二進制對稱信道(BSC)的轉(zhuǎn)移概率的函數(shù)曲線。上式給出了分組錯誤概率與二進制對稱信道(BSC)的錯誤概率p之間的關(guān)系,要完成分析,必須得到分組錯誤概率PB與譯碼器輸出比特錯誤概率Pb間的關(guān)系。當(dāng)一個分組錯誤發(fā)生時,相應(yīng)發(fā)生錯誤的信息比特數(shù)是分組錯誤引發(fā)的特定譯碼器信息輸出的函數(shù)。當(dāng)傳送的消息m被譯碼為m′時,引起的比特錯誤數(shù)記為B(m,m′)。例如,當(dāng)表6.1編碼中的碼字2被傳送時,卻在譯碼器端估算出發(fā)送端發(fā)送的是碼字3,這時就會在第4比特位t發(fā)生1位比特的錯誤,即B(2,3)=1。把特定的消息m譯碼為另一特定消息m′的概率記為PB(m,m′),這一概率也是當(dāng)xm被傳送時而接收到的矢量y處在Λm′的概率,為(6.18)精確的誤比特率為(6.19)式(6.19)中，系數(shù)1/k是由于每一傳送的碼字被譯碼后即會得到k位比特信息所致,如沒有這一項,該式的結(jié)果將是每分組錯誤比特的平均數(shù)。這個表達式只做最簡單的編碼,而對于很大的k來說,計算時間極長而無法計算。對于線性碼,上述關(guān)系可被簡化。

6.編碼增益采用前向糾錯的目的就是能改善通信的效率,這可根據(jù)實現(xiàn)要求的比特錯誤概率所需的發(fā)送功率來衡量。系統(tǒng)的編碼增益就是在無編碼和有編碼的情況下實現(xiàn)同一特定誤碼概率Pb所需的信噪比Eb/N0間的差值。一般情況下,編碼增益是Pb的函數(shù)。編碼增益的計算非常直觀,但是,在有編碼的情形下計算二進制對稱信道(BSC)的錯誤概率時必須保證所用的信噪比是正確的。前面已述及,編碼器輸出的符號速率大于編碼器輸入的比特速率,因而,編碼器每一輸出符號的發(fā)送能量Es小于每比特的能量Eb,二者之間的關(guān)系為Es=REb,其中R為編碼速率?？紤]二進制移相鍵控系統(tǒng)(BPSK),在無前向糾錯的情況下可求出其誤比特率。如系統(tǒng)采用前向糾錯,編碼速率為R,且仍采用二進制移相鍵控系統(tǒng)(BPSK),用來計算譯碼比特錯誤概率p的錯誤率可由Rm′=R代入得到。計算的編碼增益與計算編碼系統(tǒng)的Pb所采用的技術(shù)有關(guān)。在大多情形下采用Pb的下界,故計算的編碼增益是實際編碼增益的下界。例如,一通信系統(tǒng)在無編碼和采用碼率為R=4/7的漢明編碼的情形下都利用相干二進制移相鍵控作為調(diào)制方式。無編碼時,計算出比特錯誤概率,有編碼時,計算得到二進制對稱信道的錯誤概率,進而把結(jié)果代入式(6.19)得到比特錯誤概率。計算式(6.19)所需的參數(shù)可以利用計算機對所有成對碼字進行詳細(xì)檢查的結(jié)果來決定。圖6.6給出了精確的計算結(jié)果。編碼增益等于圖6.6中兩條曲線間隔的分貝數(shù)。在比特錯誤概率為10－6時,編碼增益大約為0.5dB。從圖中可以看出,兩條曲線的間隔不是常數(shù),所以編碼增益隨信噪比的不同而變化,同時兩條曲線在信噪比大約為5.75dB處相交,說明在低信噪比時通信系統(tǒng)不采用糾錯編碼,性能反而更好。圖6.6

(7,4)漢明碼的比特錯誤概率與Eb/N0的關(guān)系曲線6.2.2線性分組碼前面討論的問題具有普遍意義,其中碼字是經(jīng)過合理選擇的n維矢量集合,并把它與k維消息矢量建立合理的映射關(guān)系,從而得到很好的通信性能。在本小節(jié)中討論的問題是,編碼矢量的集合限制為所有可能的n維矢量集合的某些特定子集,這些特定子集的性質(zhì)有利于編、譯碼的操作;另外,這些特性也同時使得這些編碼系統(tǒng)的性能預(yù)測變得容易。為了討論這些編碼,首先需要掌握模2矢量運算和線性矢量空間的概念。

1.模2矢量運算現(xiàn)考慮兩個二進制矢量a=an－1…a2a1a0和b=bn－1…b2b1b0值均取自集合{0,1}兩個矢量的模2和,即c=a+b如前面提到的是兩個矢量的元素逐項模2加,因而有c0=a0+b0,c1=a1+b1,依此類推。標(biāo)量b與矢量a的積c=ba定義為矢量的各元素逐項與標(biāo)量b的乘積,有c0=b·a0,c1=b·a1。兩矢量的點積c=a·b由下式定義:a·b=(a0·b0)+(a1·b1)+(a2·b2)+…+(an－1bn－1)(6.20)其中所有的加法和乘法都為模2運算。如兩個矢量的點積為零,則定義這兩矢量是正交的。利用矢量的運算規(guī)則來定義矢量的線性組合,即:給定任一由k個n維二進制矢量組成的集合gk－1,…,g1,g0和由k個二進制標(biāo)量wk－1,…,w2,w1,w0組成的集合,下列和式:(w0·g0)+(w1·g1)+(w2·g2)+…+(wk－1·gk－1)

(6.21)稱為矢量集g的線性組合。如果沒有一個不全為零的二進制標(biāo)量集使得上式的線性組合為零矢量0=000…0,則稱由k個n維二進制矢量組成的集合gk－1,…,g1,g0是線性獨立的;否則,就是線性非獨立的。例如,考慮4個7維矢量組成的集合：

g3=1000101

g2=0100111

g1=0010110

g0=0001011對于這4個矢量,可以有16種可能的線性組合,也對應(yīng)著16種不同的二進制4維矢量w=w3,w2,w1,w0。例如,對應(yīng)于w=1101的線性組合為

x=(1·g3)+(1·g2)+(0·g1)+(1·g0)

=1000101

+0100111

+0000000

+0001011

=1101001盡管計算過程比較繁瑣,但對4個矢量g的所有16種線性組合的計算還是很直觀的,這些組合由表6.3給出。從表中可看出,只有對應(yīng)w=0000的線性組合的結(jié)果等于零矢量0=0000000。因而,矢量集g3,g2,g1,g0是線性獨立的。表6.1給出了R=4/7的漢明碼,比較表6.1和表6.3可發(fā)現(xiàn)這兩個表是一致的，即矢量g3到g0的16種線性組合生成了所有16種可能的漢明碼字,對應(yīng)一個碼字的特定線性組合由消息矢量的二進制表達式給出,也就是說,消息矢量的元素w3,w2,w1,w0定義了哪些g組合而形成碼字。因而R=4/7的漢明碼完全由g3到g0的4個矢量所決定,故這些矢量也稱作碼字的生成矢量。

2.二進制線性矢量空間二進制矢量空間是滿足一定條件的k個n維二進制矢量(xk－1,…,x2,x1,x0)的集合,即滿足下列條件:

(1)集合中的任意兩個矢量的模2和仍是集合中的另一矢量。

(2)集合中的任一矢量與{0,1}中的一元素的模2標(biāo)量積仍是集合中的一矢量。

(3)滿足分配律。如果b1和b2都是取值為{0,1}的標(biāo)量,x1和x2是集合中的兩個矢量,則有:

b1·(x1+x2)=(b1·x1)+(b1·x2)

(b1+b2)·x1=(b1·x1)+(b2·x1)

(4)滿足結(jié)合律。如果b1和b2都是取值為{0,1}的標(biāo)量,x1是集合中的一個矢量,則有:(b1·b2)·x1=b1(b2·x1)

(6.23)(6.22)所有的n維二進制矢量構(gòu)成的集合S就是一個矢量空間,因為它滿足上述四個條件。首先,由矢量加法的規(guī)則可得任意兩個n維二進制矢量的模2和仍是一個n維二進制矢量,而所有的n維二進制矢量都屬于集合S,故條件(1)滿足。其次,因為標(biāo)量積的每一元素都是二進制,其結(jié)果即為一個n維二進制矢量,而所有的n維二進制矢量都屬于集合S,所以標(biāo)量積也屬于集合S,(2)滿足。(3)和(4)同樣可以證明。

3.線性分組碼

線性分組碼就是一種分組編碼,并且它的碼字構(gòu)成了由所有可能的n維矢量組成的線性矢量空間的一個k維子空間。利用線性空間的特性可得出這樣的結(jié)論:線性分組碼中的任意兩個碼字矢量的和是另一碼字矢量;同樣,因為任一碼字矢量與它本身的和是一個有效的碼字且等于零矢量,故全零矢量一定是每一線性分組碼的一個碼字矢量。例如,考慮前例中的矢量集g3,g2,g1,g0。已經(jīng)證明,除了(0·g3)+(0·g2)+(0·g1)+(0·g0)外沒有其他的線性組合等于零矢量,即矢量集g是線性獨立的。同樣已經(jīng)證明,矢量集g的16種線性組合是漢明碼的16個碼字。因為矢量集g的所有線性組合包含在漢明碼字中,故碼字集g是所有7維矢量空間的一個線性子空間。因為矢量集g是獨立的,所以它是可以用來生成子空間的最小矢量集,子空間的維數(shù)為4,即矢量集g中的矢量個數(shù)。因為子空間的所有矢量都是由矢量g的線性組合生成的,故矢量集g擴張成該子空間。因而,上例中的漢明碼是維數(shù)k=4的線性分組碼。因為一個分組編碼構(gòu)成了由全部n維矢量組成的空間的一個k維子空間,所有的碼字矢量可由子空間的k個線性獨立的基本矢量的線性組合生成。這k個基本矢量稱作碼的生成矢量。用矩陣來計算編碼的碼字非常方便,把編碼的生成矢量按列排序組成編碼的生成矩陣G,其定義為(6.24)把消息矢量同前面一樣用k維矢量wm=wm,k－1…wm2wm1wm0來表征,則碼字行矢量xm就等于行矢量wm與矩陣G的乘積,即(6.25)從上面的等式很明顯可看出,每一碼字符號為消息符號的模2線性組合。某一特定消息符號由生成矩陣G組合成特定的編碼矢量符號。每一編碼矢量符號也可用下式計算:(6.26)其中的和為模2和。使用線性編碼的一個好處就是用上式實現(xiàn)碼字的生成非常容易。例如,漢明碼的生成矩陣G為則對應(yīng)于消息矢量w=1101的碼字為一個線性編碼是所有n維矢量組成的空間的一個線性子空間。這一子空間的零空間也是一個子空間,并且可以用生成基矢量或生成矩陣來表征。零空間的生成矩陣用H來表示,它的生成基本矢量用hn－k－1,…,h1,h0來表示,則零空間的生成矩陣為(6.27)這一矩陣稱作由生成矩陣G定義的編碼的奇偶校驗矩陣。當(dāng)編碼空間的維數(shù)為k時,零空間的維數(shù)為n－k。由定義可知,零空間中的所有矢量與全部碼字矢量正交,因為矢量hj是零空間的成員,它們與任一碼字矢量正交,所以對于任意的m=0,1,…,2k－1和j=0,1,…,n－k－1有xm·hj=0,用矩陣表示為(6.28)其中的上標(biāo)T表示矩陣的轉(zhuǎn)置。同樣可以證明,不是碼字的任一矢量y不滿足上式。因此,矢量y當(dāng)且僅當(dāng)滿足下式時才為碼字:0=y×HT(6.29)一個線性分組編碼既可以用它的生成矩陣G也可以用它的奇偶監(jiān)督矩陣H來描述,二者都有實際應(yīng)用。例如,(7,4)線性分組編碼的奇偶監(jiān)督矩陣為n維矢量y=1001111與矩陣H的轉(zhuǎn)置矩陣的乘積為結(jié)果不為零,說明矢量y不是一個有效的碼字。

4.系統(tǒng)線性分組編碼如上所述,任一編碼矢量符號是消息符號的一個線性組合,因而并沒有要求消息符號本身必須出現(xiàn)在碼字中。系統(tǒng)分組編碼就是它的生成矩陣可使得它的消息符號直接出現(xiàn)在碼字矢量中的一種編碼。系統(tǒng)編碼是所有線性編碼的一子集。如生成矩陣G有如下所示的形式,消息符號就會直接出現(xiàn)在碼字中:(6.30)很顯然,生成矩陣G的左邊為一單位矩陣。對于系統(tǒng)碼,它的前n－k個碼字矢量符號是消息符號的奇偶校驗?？梢宰C明的是這種系統(tǒng)碼存在且它的誤碼糾錯性能與任一給定的線性碼相同。表6.1給出的漢明碼就是系統(tǒng)碼,消息符號出現(xiàn)在每一碼字矢量的左邊。對于系統(tǒng)碼,它的奇偶監(jiān)督矩陣H可直接從生成矩陣得到。特別地,對應(yīng)給定的生成矩陣,它的奇偶監(jiān)督矩陣H為(6.31)

5.線性分組碼的距離特性編碼的距離特性是表征它糾錯能力的重要特性。對于碼字長度為n、編碼速率為R的好碼就是指任意兩個碼字間的漢明距離盡可能的大。譯碼器采用最小距離譯碼時,當(dāng)信道發(fā)生錯誤導(dǎo)致接收到的n維矢量在漢明距離上更接近不同于發(fā)送的碼字時,分組譯碼就會發(fā)生錯誤。為計算分組錯誤或比特錯誤概率，就必須知道所有碼字對之間的漢明距離?，F(xiàn)討論線性分組編碼中任意兩個碼字xm和xm′的漢明距離dH(xm,xm′)。假設(shè)另一碼字矢量xa同時疊加到xm和xm′,則矢量xn為1的位置使得矢量xm和xm′和式中對應(yīng)位置同時發(fā)生變化。因為xm和xm′發(fā)生變化的位置相同,故疊加矢量xa后的和式間的漢明距離與原始碼字間的漢明距離相同,即dH(xm+xa,xm′+xa)=dH(xm,xm′)。既然矢量xn是任一碼字矢量,不妨讓xa=xm′,則有dH(xm+xm′,xm′+xm′)=dH(xm+xm′,0)。因而,線性分組編碼中的任意兩個碼字矢量間的漢明距離等于碼字中的另一碼字與零碼字矢量間的距離。事實上,任一特定碼字矢量與其他所有碼字矢量間的漢明距離的集合等于零碼字矢量與所有非零碼字矢量間的漢明距離的集合。分組編碼的最小距離dmin

等于任意兩個不同的碼字矢量之間漢明距離的最小值。利用編碼的線性特性,編碼的最小距離等于碼字矢量中零碼字矢量與任一非零碼字矢量間的最小漢明距離,所以編碼的最小距離就是具有最小漢明重量的非零碼字矢量的漢明重量。大家已熟知的表6.1給出的漢明碼的最小距離是3,從表6.1中可以看出非零碼字矢量中1的個數(shù)最小的是3,與編碼的最小距離一致。

6.用標(biāo)準(zhǔn)陣列譯碼

對于線性分組編碼構(gòu)造譯碼區(qū)間Λm有一種非常方便有效的方法?；仡櫼幌?譯碼區(qū)間把所有n維矢量構(gòu)成的空間劃分為若干子集,使得落在區(qū)間Λm的所有接收矢量y是由發(fā)送端的消息矢量xm傳輸?shù)玫降目赡苄宰畲?。對于錯誤概率小于0.5的二進制對稱信道,這也就意味著落在區(qū)間Λm的所有接收矢量y在漢明距離上與其他碼字矢量xm′相比更接近xm。構(gòu)造譯碼區(qū)間是通過計算2n種可能的接收矢量y的每一種與所有碼字矢量xm間的漢明距離,從而把y放置到適當(dāng)?shù)膮^(qū)間來實現(xiàn)的。用下列步驟來構(gòu)造二進制對稱信道的譯碼區(qū)間非常容易。首先,把所有的編碼矢量xm排成一行,全零矢量放在行的最左邊,接著選擇一個與第一行任一碼字都不相同的錯誤矢量e1并把它放在全零矢量的下面。完成了這一步后,剛剛選擇的錯誤矢量應(yīng)該是可以糾正的錯誤矢量,也就是說,當(dāng)錯誤發(fā)生時,接收到的矢量仍可被正確譯碼。盡管這一錯誤矢量的選擇是任意的,但可以證明,若具有糾正最大可能錯誤矢量的能力,就可以收到好的通信系統(tǒng)性能。既然錯誤矢量的概率隨著重量的降低而增加,選擇的最佳錯誤矢量應(yīng)是具有最小重量的矢量,在所有情形中,第一個選擇的錯誤矢量是重量為1的矢量。現(xiàn)在把錯誤矢量e1與第一行所有的非零碼字矢量相加,把結(jié)果排成一行且放在錯誤矢量e1的右邊、相應(yīng)碼字矢量的下面。接著再選擇另一錯誤矢量e2,也把它放在全零矢量的下面,選擇的錯誤矢量應(yīng)是沒有在前面兩行出現(xiàn)過的具有盡可能小的漢明重量的矢量,同樣計算錯誤矢量e2與第一行全部非零碼字矢量e2的和,結(jié)果排成一行且放在相應(yīng)碼字矢量的下面。重復(fù)這一步驟,直到所有的n維矢量都被窮盡。最后可得如下標(biāo)準(zhǔn)陣列：(6.32)這里所采用的構(gòu)造過程和編碼的線性特性,使在陣列中的每個n維矢量都是不同的,且所有2n種可能的n維矢量僅在陣列中出現(xiàn)一次,陣列總共有2n－k行。用標(biāo)準(zhǔn)陣列來譯碼是通過把與碼字矢量xm同一列(包含碼字矢量xm本身)的所有n維矢量定義為譯碼區(qū)間Λm來實現(xiàn)的。只要接收矢量與碼字矢量在同一列,譯碼器就會輸出消息m。因為所有的n維矢量在陣列中僅出現(xiàn)一次,故所有的接收矢量y僅會出現(xiàn)在一個單獨的譯碼區(qū)間Λm(列)且被惟一地譯碼。仔細(xì)檢查標(biāo)準(zhǔn)陣列就會發(fā)現(xiàn),對于任意碼字矢量,如果實際的錯誤圖樣是任一錯誤矢量ej,則接收矢量y與碼字矢量xm會處于同一列并將被正確譯碼。這樣,選擇的錯誤圖樣是可被糾正的。選擇錯誤矢量ej的惟一條件就是它沒有出現(xiàn)在它上面的行中?？梢宰C明,任何沒有在標(biāo)準(zhǔn)陣列的第一列中出現(xiàn)的錯誤矢量是不可被糾正的,事實上這些錯誤矢量將導(dǎo)致分組譯碼錯誤。對于任一(n,k)線性分組編碼,標(biāo)準(zhǔn)陣列譯碼法能正確地糾正2n－k個錯誤矢量,包括全零錯誤矢量。要得到好的通信性能,應(yīng)該選擇沒有出現(xiàn)在已經(jīng)構(gòu)造好的行中的、可糾正的且具有盡可能小的重量的錯誤矢量。同樣可以證明,由上述規(guī)則得出的標(biāo)準(zhǔn)陣列構(gòu)造出的譯碼區(qū)間實際上就是最小距離譯碼區(qū)間。因此,生成標(biāo)準(zhǔn)陣列對于線性分組編碼得到其譯碼區(qū)間Λm是一個正確的過程。標(biāo)準(zhǔn)陣列譯碼可利用奇偶監(jiān)督矩陣得到簡化?；仡櫼幌?任一線性編碼的碼字滿足:0=xm×HT

(6.33)且任一接收矢量為y=xm+ej,接收矢量y與奇偶監(jiān)督矩陣的轉(zhuǎn)置矩陣的積被稱做y的校正子,(ej+xm)×HT=ej×HT+xm×HT=ej×HT+0

(6.34)校正子僅僅是錯誤矢量ej的函數(shù)。顯然,在標(biāo)準(zhǔn)陣列中同一行的所有接收矢量的校正子都相同,標(biāo)準(zhǔn)陣列中不同行的接收矢量的校正子各不相同。正因為這些因素,譯碼可由下列步驟完成:

(1)計算接收矢量y的校正子。

(2)在標(biāo)準(zhǔn)陣列中尋找與第(1)步計算所得校正子相同的行,并把這一行的錯誤矢量作為估計的錯誤矢量。

(3)把估計的錯誤矢量與接收矢量相加得到估計的傳送碼字。如果實際的錯誤圖樣就是生成標(biāo)準(zhǔn)陣列時用到的錯誤圖樣之一,就會得到正確譯碼。標(biāo)準(zhǔn)陣列譯碼法可以糾正在生成陣列時用到的所有錯誤矢量,而對其他錯誤矢量無法糾正,則分組的錯誤率PB為(6.35)其中的wH(ej)是ej的漢明重量。上式等于1減去任一可糾正錯誤矢量出現(xiàn)的概率。

7.線性碼的錯誤概率上(下)界技術(shù)的應(yīng)用可以簡化線性分組編碼的分組錯誤概率的計算。首先,重新考慮前面討論得出的分組錯誤概率的結(jié)果,對于任意編碼(線性或非線性)的平均分組錯誤概率就是接收矢量y落在譯碼區(qū)間Λm之外的概率的平均(對所有的消息m),這個錯誤概率是:(6.36)其中(6.37)對于很大的n和k來說,利用式(6.37)精確計算是很困難的。為了使預(yù)測編碼系統(tǒng)的性能更容易,編碼理論采用上(下)界技術(shù)來解決這一問題。仔細(xì)研究區(qū)間,其定義為

=｛y|ln［Pr(y|xm′)］≥ln［Pr(y|xm)］,某些m′≠m｝

=｛y|ln［Pr(y|xm′)］≥ln［Pr(y|xm)］｝

=

Λmm′

(6.38)其中(6.39)對于每個m和m′來說,區(qū)間Λmm′是由所有在不考慮任何其他碼字的情況下,相對于xm來說更可能是由xm′傳輸所得到的所有接收矢量y組成的。也就是說,所有接收矢量y組成的空間被分成兩個譯碼區(qū)間,一個是xm的,另一個是xm′的。

因為對于特定的m和m′來說,所有接收矢量y一定包含在區(qū)間Λmm′或中,區(qū)間對不同的m和m′來說是相交的。由概率理論可知,一聯(lián)合事件的概率小于或等于各組成事件的概率之和。因而,分組錯誤概率可由下式給出上界:(6.39)(6.40)其中的PB′(m,m′)是在編碼中僅有m和m′兩個碼字的假設(shè)下的分組錯誤概率。

PB′(m,m′)可利用已給出的方法進行估值。特別地,現(xiàn)考慮只有兩個碼字xm和xm′的編碼情況,它們的漢明距離為dH(xm,xm′),這時決定采用最小距離譯碼器的錯誤譯碼概率。假設(shè)傳送的是xm,只要傳送中的錯誤使得接收到的矢量y相對于xm來說在漢明距離上更接近xm′時譯碼錯誤就會發(fā)生。傳送中發(fā)生的錯誤發(fā)生在兩個碼字內(nèi)容相同的位置上時,會同時加大y與xm間和y與xm′間的漢明距離,因而對譯碼結(jié)果沒有影響。當(dāng)dH為偶數(shù),只有(dH/2)+1個或更多的傳送錯誤發(fā)生在xm和xm′的內(nèi)容不同的位置上時譯碼錯誤才會發(fā)生。當(dāng)僅發(fā)生dH/2個錯誤時,y到xm和xm′的漢明距離相同,假設(shè)這時有一半發(fā)生譯碼錯誤。故dH為偶數(shù)的兩個碼字編碼的錯誤概率為(6.41)當(dāng)dH為奇數(shù),只有dH/2個或更多的傳送錯誤發(fā)生在xm和xm′的內(nèi)容不同的位置上時譯碼錯誤才會發(fā)生。故dH為奇數(shù)的兩個碼字編碼的錯誤概率為(6.42)利用上述關(guān)系式,整個分組譯碼錯誤概率的上界由下式給出:(6.43)平均分組錯誤概率的計算可通過利用上界替代式(6.41)和式(6.42)稍作簡化,則(6.44)其中dH(xm,xm′)為xm和xm′間的漢明距離。利用線性編碼的特性可以進一步簡化結(jié)果。線性碼很重要的一個特性是,對于所有的碼字xm來說,任一碼字xm與所有其他的碼字xm′,m′=m,m′=0,…,2k－1間的漢明距離集是相同的。正因為這一特性,式(6.43)中界的第二項和式對于任意選擇的m都是相同的。因此,在第二項和式的所有計算中選擇m=0將不會改變錯誤概率的值,故(6.45)其中PB′(0,m′)由式(6.41)和(6.42)計算。對于線性編碼,全部平均分組錯誤概率可通過只計算假設(shè)消息m=0傳送時的錯誤概率而得到。從原理上說,任意特定的編碼的碼字是可排列的,從而可以確定與全零碼字間漢明距離為d的碼字的數(shù)量。如果碼字xm′與全零碼字間的漢明距離已知,函數(shù)PＢ′(0,m′)就會完全確定下來,因此,分組錯誤概率也可表達為漢明距離上的和式:(6.46)其中,ad為與全零碼字間漢明距離為d的碼字的數(shù)量,PB′(d)為僅考慮由漢明距離為d的兩碼字情形時的誤碼概率。要注意的是,PB′(d)表示的是對于任意的m和m′當(dāng)dH(xm,xm′)=d

時PB′(m,m′)的值。對于d=dmin,…,n的ad的集合稱做編碼的重量結(jié)構(gòu)。對于k大小適中的編碼,利用計算機來尋找ad是完全可能的,小的編碼集的ad已分析找出。但是,通信工程師經(jīng)常需要計算具有很大k的編碼的PB,這個k大到甚至用很快的計算機也無法在合理的時間內(nèi)列舉出編碼的所有碼字。在這些情形下,仍然可以通過對譯碼規(guī)則稍作改變及只考慮系統(tǒng)碼而得到結(jié)果。特別地,假設(shè)譯碼器最大可糾正M個信道錯誤,具有這種特性的譯碼器被稱做限定距離譯碼器(boundeddistancedecoders)。值得注意的是,最大似然譯碼器保證能夠糾正t個信道錯誤,但是在許多情況下它能夠糾正超過t個的錯誤。限定距離譯碼器只要超過M個信道錯誤發(fā)生,分組譯碼一定也發(fā)生錯誤,因而,分組錯誤概率簡單地就是M+1個或更多個信道錯誤發(fā)生的概率,它是:(6.47)這一結(jié)果就是保證糾正至少M=t個錯誤的最大似然譯碼器的PB的上界。上述討論的結(jié)果使得通信系統(tǒng)設(shè)計者來預(yù)測任何線性編碼的分組錯誤概率性能成為可能。要確定比特錯誤概率則需要知道每一可能的分組譯碼錯誤所關(guān)聯(lián)的比特錯誤數(shù)量。精確的比特錯誤概率表達式已在前面給出,對其近似的估值可利用作為分組錯誤概率函數(shù)的界完成。當(dāng)每一分組譯碼錯誤發(fā)生時,至少總有1比特發(fā)生錯誤,又因每一分組有k個比特相關(guān)聯(lián),單個比特錯誤相應(yīng)的平均比特錯誤概率為PB/k,故比特錯誤概率的一個下界為≤同樣,每一分組譯碼錯誤發(fā)生時不會有超過k個比特發(fā)生錯誤,又因每一分組有k個比特被譯碼,故比特錯誤概率的一個上界為Pb≤PB

(6.49)對于系統(tǒng)設(shè)計來說,這些界通常已足夠。對于線性系統(tǒng)分組編碼,還可以提高比特錯誤概率估值的精度?；仡櫼幌?對于線性編碼,所有的碼字中與任一特定碼字漢明距離為d的碼字?jǐn)?shù)量都是相同的。利用這一事實,分組錯誤概率的計算可簡化為計算假設(shè)在碼字0被傳送時的分組錯誤概率。利用相似與為簡化分組錯誤概率計算用到的表達式,可以證明對于線性系統(tǒng)分組編碼,平均比特錯誤概率的計算可簡化為計算假設(shè)在碼字0被傳送時的比特錯誤概率。這種簡化是可行的,原因有二：其一,所有的碼字中與任一特定碼字漢明距離為d的碼字?jǐn)?shù)量都是相同的;其二,所有的碼字中由任意漢明距離為d的分組譯碼錯誤引起的比特錯誤數(shù)量都是相同的。例如,對于(7,4)漢明碼,如果傳送的是消息7,而譯碼的結(jié)果是消息13,就會發(fā)生2比特的錯誤,傳送的碼字和譯碼后的碼字間的漢明距離為4,同時會存在一個相應(yīng)的與傳送碼字0相關(guān)聯(lián)的錯誤事件。特別地,如傳送的是消息0,而譯碼的結(jié)果是消息9,就會發(fā)生2比特的錯誤,傳送的碼字和譯碼后的碼字間的漢明距離為4。計算信息比特錯誤概率Pb時,假設(shè)傳送的為消息0,并對每一分組錯誤事件由其對應(yīng)的信息比特錯誤數(shù)量進行加權(quán)。用B(m′)表征傳送的是m=0而譯碼為m′時發(fā)生的比特錯誤數(shù)量,則平均比特錯誤概率可擴展為式(6.45),從而得到:(6.50)其中,PB′(0,m′)是不正確譯碼為m′的概率。通過觀察可知,PB′(0,m′)是碼字0和xm′間漢明距離的函數(shù),且對具有相同漢明距離的所有碼字都相同。如前面一樣,PB′(d)表示的是對于任意的m和m′當(dāng)dH(xm,xm′)=d時PB′(m,m′)的值。Bd表示在所有引發(fā)碼字與全零碼字間距離為d的分組錯誤事件中比特錯誤的總數(shù)。式(6.49)可重新寫為(6.51)其中dmin是編碼的最小距離。上式對任意特定的編碼給出了比特錯誤概率的一個很好的界限。對特定的編碼,Bd的值可能是給定的也可能是用計算機計算得到的。對低誤碼率,

比特錯誤概率通常只用上式的第一項。對具有適中的k的編碼,用計算機來尋找Bd是完全可能的,但是對于很大的k就得利用其他技術(shù)。只考慮系統(tǒng)編碼和限定距離譯碼器,利用限定距離譯碼器,譯碼器對接收矢量最多在M個位置進行更改(“糾錯”),最好的情況是這些更改正好糾正了系統(tǒng)碼字中信息比特部分中錯誤的信息比特;最糟的情形是這些更改仍在系統(tǒng)碼字的信息比特部分,但卻改變了那些本已正確的信息位而使它們發(fā)生錯誤。因而,當(dāng)i≤M個信道錯誤發(fā)生時就會正確譯碼,不會有比特發(fā)生錯誤;當(dāng)i>M個信道錯誤發(fā)生時就會有分組譯碼錯誤且信息比特錯誤的最大數(shù)是min［k,i+M］。很明顯,不會發(fā)生超過全部信息比特數(shù)量的錯誤,并且如果全部錯誤發(fā)生在碼字的信息比特部分且i+M位正確的比特被譯碼器更改,就會有M位信息比特發(fā)生錯誤。故比特錯誤概率的上界為(6.52)其中,1/k是指每一分組被譯碼時有k位信息比特輸出,二項式系數(shù)是n個符號的分組中發(fā)生i個錯誤的組合數(shù)。6.2.3循環(huán)碼

(n,k)分組編碼就是簡單地把k位信息比特巧妙地映射為n位符號的碼字。對于編碼來說,碼字和映射關(guān)系必須認(rèn)真選取,因為它對提高通信系統(tǒng)的性能是非常有用的。對編碼的結(jié)構(gòu)則沒有進一步的限制,一個(n,k)分組編碼的編碼是通過查表的方法實現(xiàn)的。一般地,它的譯碼也可用查表的方法利用最小距離譯碼準(zhǔn)則來完成。對于很大的n和k,因為需要很大的表,查表的方法就無法采用。在前面,僅考慮線性分組編碼,所需的線性特性可大大簡化編碼和譯碼過程。線性分組碼的編碼可由k維信息矢量與生成矩陣G的矩陣乘積完成,它的譯碼可以很簡單地利用校正子的概念和標(biāo)準(zhǔn)陣列實現(xiàn)。在本小節(jié),對線性分組碼提出了附加的結(jié)構(gòu)條件,可使它的編碼和譯碼功能進一步簡化。這一附加結(jié)構(gòu)使得編碼器可以采用簡單的前饋移位寄存器的形式。同樣地,譯碼器可以采用反饋移位寄存器,再附加一些用來計算錯誤矢量的邏輯組成。本小節(jié)的主題是循環(huán)碼,它是所有線性編碼的子集。

1.循環(huán)碼的定義循環(huán)碼是一線性編碼,具有線性編碼的所有特性,并且碼字的任意位循環(huán)移位仍是另一有效碼字。因此,如x=xn－1xn－2…x2x1x0是循環(huán)碼的一碼字,則x′=xn－2

…x2x1x0xn－1是循環(huán)碼的一碼字;重復(fù)利用這一特性,碼字經(jīng)過q次移位后,記作x(q),仍是循環(huán)碼的一碼字。這時x(q)=xn－q－1…x1x0…xn－q+1xn－q。循環(huán)碼可用生成矩陣G或奇偶校驗矩陣H表示,但通常它們是用生成多項式的概念來表述的。在定義生成多項式前,我們先復(fù)習(xí)一下多項式的乘法和除法運算。

2.多項式運算

w(D)=wk－1Dk－1+…+w2D2+w1D+w0是D的多項式,每一wj的取值取自集合{0,1}。這一多項式的次數(shù)等于系數(shù)為非零值的D的最高冪次,如多項式w(D)=D4+D+1的次數(shù)為4。為了方便,系數(shù)為零的項不再寫出,同時與1的乘積中的1也略去,即w(D)=(1·D4)+(0·D3)+(0·D2)+(1·D1)+(1·D0)寫作w(D)=D4+D+1這一多項式也代表k位信息矢量w=wk－1…w2w1w0。設(shè)多項式g(D)=gk－1Dk－1+…+g2D2+g1D+g0是另一多項式,同樣定義多項式y(tǒng)(D)、x(D)和e(D),則兩個多項式x(D)和e(D)的模2和為y(D)=ytDt+…+y2D2+y1D+y0該多項式的系數(shù)是x(D)和e(D)中相應(yīng)具有相同冪次的D的系數(shù)的模2和,即yj=xj+ej兩個多項式的乘積為x(D)=xn－1Dn－1+…+x2D2+x1D+x0它的系數(shù)由下式給出:g(D)w(D)=(gn－k·wk－1)Dn－1

+(gn－k·wk－2+gn－k－1·wk－1)Dn－2

+(gn－k·wk－3+gn－k－1·wk－2+gn－k－2·wk－1)Dn－3+…+(g0,w0)D0=xn－1Dn－1+xn－2Dn－2+…+x0D0(6.53)其中所有的運算是模2運算