第1章 糾錯(cuò)碼的基本概念

1、第一章 糾錯(cuò)碼的基本概念 第一章 糾錯(cuò)碼的基本概念 1.1 數(shù)字通信系統(tǒng)的組成及信道模型數(shù)字通信系統(tǒng)的組成及信道模型 1.2 差錯(cuò)控制系統(tǒng)和糾錯(cuò)碼分類(lèi)差錯(cuò)控制系統(tǒng)和糾錯(cuò)碼分類(lèi) 1.3 最大似然譯碼和糾錯(cuò)碼的基本概念最大似然譯碼和糾錯(cuò)碼的基本概念 1.4 信道編碼定理信道編碼定理 第一章 糾錯(cuò)碼的基本概念 1.1 數(shù)字通信系統(tǒng)的組成及信道模型數(shù)字通信系統(tǒng)的組成及信道模型 一、一、 數(shù)字通信系統(tǒng)的組成數(shù)字通信系統(tǒng)的組成 通信的目的：把對(duì)方不知道的消息及時(shí)、可靠地（有時(shí)還需秘密地）傳送給對(duì)方 在數(shù)字通信系統(tǒng)中可靠與快速往往是一對(duì)矛盾 若要求快速，則必然使得每個(gè)數(shù)據(jù)碼元所占的時(shí)間縮短、波形變窄、能量減

2、少，從而在受到干擾后產(chǎn)生錯(cuò)誤的可能性增加，傳送消息的可靠性減低。 若要求可靠， 則使得傳送消息的速率變慢 因此，如何較合理地解決可靠性與速度這一對(duì)矛盾， 是正確設(shè)計(jì)一個(gè)通信系統(tǒng)關(guān)鍵問(wèn)題之一。 通信理論本身(包括糾錯(cuò)碼)也正是在解決這對(duì)矛盾中不斷發(fā)展起來(lái)的。 第一章 糾錯(cuò)碼的基本概念 圖 1 - 1 數(shù)字通信系統(tǒng)模型第一章 糾錯(cuò)碼的基本概念 信源編碼器：把信源發(fā)出的消息轉(zhuǎn)換成為二進(jìn)制(或多進(jìn)制)形式的信息序列，并且為了使傳輸有效，還去掉了一些與傳輸信息無(wú)關(guān)的多余度（信源編碼越短越好）。信道編碼器（糾錯(cuò)編碼器）：為了抗擊傳輸過(guò)程中的各種干擾，人為地增加多余度，使其具有自動(dòng)檢錯(cuò)或糾錯(cuò)能力。發(fā)射機(jī)(調(diào)

3、制器)：把糾錯(cuò)碼送出的信息序列通過(guò)調(diào)制器變換成適合于信道傳輸?shù)男盘?hào)。解調(diào)器：信號(hào)變?yōu)槎M(jìn)制(或多進(jìn)制)信息序列。信道譯碼器（糾錯(cuò)譯碼器）：糾正由于信道干擾而使信息序列中發(fā)生的錯(cuò)誤。信源譯碼器：恢復(fù)成原來(lái)的消息送給用戶(hù)。 第一章 糾錯(cuò)碼的基本概念 我們關(guān)心的是信道編、譯碼器即糾錯(cuò)編、譯碼器上述模型可進(jìn)一步簡(jiǎn)化為圖1-2模型： 信源指原來(lái)的信源和信源編碼器， 其輸出是二(多)進(jìn)制信息序列。 信道包括發(fā)射機(jī)、實(shí)際信道和接收機(jī)在內(nèi)的廣義信道(又稱(chēng)編碼信道)， 它的輸入是二(多)進(jìn)制數(shù)字序列，輸出一般也是二(多)進(jìn)制數(shù)字序列。 信宿可以是人或計(jì)算機(jī)。 第一章 糾錯(cuò)碼的基本概念 二、二、 信道模型信道模型

4、 現(xiàn)在以簡(jiǎn)化模型來(lái)討論二進(jìn)制數(shù)字序列通過(guò)該系統(tǒng)時(shí)所發(fā)生的情況。設(shè)從信源送出字母A，它的二進(jìn)制序列為11000， 以基帶信號(hào)傳送， 經(jīng)發(fā)射機(jī)調(diào)制后，送往信道的已調(diào)信號(hào)如圖1-3所示。由于信道的干擾， 從信道輸出端的信號(hào)產(chǎn)生了失真， 如圖1-4所示。第一章 糾錯(cuò)碼的基本概念 這些失真信號(hào)送入接收機(jī)進(jìn)行判決時(shí)， 由于第一、 二、 四、 五碼元的波形失真不大， 容易正確地判為1、1和0、 0； 但對(duì)第三個(gè)碼元來(lái)說(shuō)，由于失真嚴(yán)重而難于判決。這時(shí)有以下三種判決方法： 硬判決：一是勉強(qiáng)作出是0還是1的判決 刪除符號(hào)：對(duì)該碼元暫且不作判決，而輸出一個(gè)未知或待定的信號(hào)“x”，稱(chēng)其為刪除符號(hào) 軟判決：第三種方法是

5、輸出一種有關(guān)該碼元的信息，例如關(guān)于0和1的后驗(yàn)概率或似然函數(shù) 當(dāng)然軟判決的性能較好，但實(shí)現(xiàn)起來(lái)較復(fù)雜。第一章 糾錯(cuò)碼的基本概念 在二進(jìn)制硬判決情況下，信道可用圖1-5所示的簡(jiǎn)單模型表示。圖中，p01和p10分別是0錯(cuò)成1和1錯(cuò)成0的概率， 稱(chēng)信道轉(zhuǎn)移概率。該信道的信道轉(zhuǎn)移概率矩陣可用 101001011110010011ppppppppP描述。如果p01=p10=pe，則稱(chēng)這種信道為二進(jìn)制對(duì)稱(chēng)信道二進(jìn)制對(duì)稱(chēng)信道，簡(jiǎn)稱(chēng)BSC。否則，稱(chēng)為不對(duì)稱(chēng)信道不對(duì)稱(chēng)信道。若p01或p10等于零，則稱(chēng)為Z信信道道。通常BSC是一種無(wú)記憶信道無(wú)記憶信道，所以也稱(chēng)隨機(jī)信道隨機(jī)信道， 它說(shuō)明數(shù)據(jù)序列中出現(xiàn)的錯(cuò)誤彼此無(wú)

6、關(guān)。 第一章 糾錯(cuò)碼的基本概念 如果信道的輸入是二進(jìn)制符號(hào)，而輸出是離散的q(qpm2)進(jìn)制符號(hào)，如圖1-6所示，且p(i0)p(q-1-i1)，i0， 1， q-1，則這種信道稱(chēng)為離散無(wú)記憶信道(DMC)，顯然BSC是DMC的一種特殊情況。 DMC的信道轉(zhuǎn)移概率矩陣 ) 1 |1() 1 |1 () 1 |0()0|1()0|1 ()0|0(qpppqpppP第一章 糾錯(cuò)碼的基本概念 在作刪除判決情況下，信道可用圖1-7所示的模型表示， 稱(chēng)為二進(jìn)制刪除信道，簡(jiǎn)稱(chēng)BEC，一般它也是對(duì)稱(chēng)信道。圖中， pe為信道的轉(zhuǎn)移概率，q為刪除概率。第一章 糾錯(cuò)碼的基本概念 在有刪除處理情況下， 信道的轉(zhuǎn)移概

7、率pe一般很小，可忽略，因此把圖1-7所示的模型用圖1-8代替，稱(chēng)為二進(jìn)制純刪除信道。以后所說(shuō)的BEC都是指這種信道。應(yīng)當(dāng)指出，當(dāng)碼元作刪除處理時(shí)，它在序列中的位置是已知的，僅不知其值是0還是1，故對(duì)這種BEC信道的糾錯(cuò)要比BSC信道容易。 第一章 糾錯(cuò)碼的基本概念 上述三種信道模型只是為了討論問(wèn)題方便而簡(jiǎn)化成理想的情況，它們表達(dá)了某些實(shí)際信道傳送信號(hào)的主要特征。例如， 衛(wèi)星信道或深空信道，可近似看成是BSC。但有很多實(shí)際信道如高頻、散射、有線等信道， 由于各種干擾所造成的錯(cuò)誤， 往往不是單個(gè)地而是成群成串地出現(xiàn)的， 也就是一個(gè)錯(cuò)誤的出現(xiàn)，往往引起其前后碼元的錯(cuò)誤(突發(fā)錯(cuò)誤)， 表現(xiàn)為錯(cuò)誤之間

8、的相關(guān)性。產(chǎn)生這種錯(cuò)誤的信道稱(chēng)有記憶信道或突發(fā)信道。 在計(jì)算機(jī)存貯系統(tǒng)中，磁帶的缺陷或讀寫(xiě)頭接觸不良所引起的錯(cuò)誤，也屬于這種類(lèi)型。第一章 糾錯(cuò)碼的基本概念 但由于實(shí)際信道干擾的復(fù)雜性，所引起的錯(cuò)誤往往不是單純的一種，而是兩種錯(cuò)誤形式并存，只不過(guò)有的信道以某種錯(cuò)誤形式為主罷了。像這種隨機(jī)錯(cuò)誤與突發(fā)錯(cuò)誤并存的信道，稱(chēng)為組合信道或復(fù)合信道。 作為檢錯(cuò)與糾錯(cuò)用的抗干擾碼，必須針對(duì)這幾類(lèi)信道， 設(shè)計(jì)能糾正隨機(jī)錯(cuò)誤或糾正突發(fā)錯(cuò)誤的碼，或者設(shè)計(jì)既能糾正隨機(jī)錯(cuò)誤又能糾正突發(fā)錯(cuò)誤的碼。第一章 糾錯(cuò)碼的基本概念 由于目前在信道中傳輸或計(jì)算機(jī)內(nèi)部運(yùn)算的數(shù)據(jù)序列， 大部分是二進(jìn)制數(shù)字序列， 因此以后主要討論二進(jìn)制數(shù)字

9、通信中的糾錯(cuò)碼，當(dāng)然這些糾錯(cuò)碼往往可以推廣到q(素?cái)?shù)或素?cái)?shù)的冪)進(jìn)制情況，這將在以后具體討論時(shí)予以說(shuō)明。 二進(jìn)制情況下， 序列之間0、1兩個(gè)符號(hào)按下列規(guī)則進(jìn)行運(yùn)算： +0 1 0 0 11 1 0模2相加 模2相乘 0 1 0 0 01 0 1 為了簡(jiǎn)便，今后用+和表示模2相加和相乘。 在模2情況下， 加和減是一回事。 第一章 糾錯(cuò)碼的基本概念 三、三、 錯(cuò)誤圖樣錯(cuò)誤圖樣設(shè)發(fā)送的是n個(gè)碼元長(zhǎng)的序列C：(cn-1，cn-2，c1，c0)， 通過(guò)信道傳輸?shù)竭_(dá)接收端(糾錯(cuò)碼譯碼器輸入端)的序列為R：(rn-1， rn-2，r1，r0)。由于信道中存在干擾，R序列中的某些碼元可能與C序列中對(duì)應(yīng)碼元的值

10、不同，也就是說(shuō)產(chǎn)生了錯(cuò)誤。把信道中的干擾也用二進(jìn)制序列E：(en-1，en-2，e1，e0)表示，則相應(yīng)有錯(cuò)誤的各位ei取值為1，無(wú)錯(cuò)的各位取值為0，而R就是C與E序列模2相加的結(jié)果，我們稱(chēng)E為信道的錯(cuò)誤圖樣或干擾矢量。 例如，發(fā)送序列C：(1111100000)， 收到的序列R： (1001010000)，第二、三、五、六位產(chǎn)生了錯(cuò)誤， 因此信道的錯(cuò)誤圖樣E的二、 三、 五、 六位取值為1，其它各位取值為0， 即E： (0110110000)。 用式子可表示成： 第一章 糾錯(cuò)碼的基本概念 發(fā)送序列C: 1111100000 錯(cuò)誤圖樣E： 0110110000 接收序列R： 100101000

11、0 +即RC+E， 或E=R-C。 信道干擾所造成的錯(cuò)誤可在序列中的任一位出現(xiàn)，且也可以在n長(zhǎng)序列中同時(shí)出現(xiàn)一位、二位，甚至n位錯(cuò)誤。因此，若發(fā)送的C序列長(zhǎng)為n， 則信道中可能產(chǎn)生的錯(cuò)誤圖樣E共有2n種。 若為突發(fā)信道，則在錯(cuò)誤圖樣E中，第一個(gè)1與最后一個(gè)1之間的長(zhǎng)度稱(chēng)為突發(fā)長(zhǎng)度，其圖樣稱(chēng)為突發(fā)圖樣。在該例中，突發(fā)圖樣是(11011)， 突發(fā)長(zhǎng)度為5。 第一章 糾錯(cuò)碼的基本概念 1.2 差錯(cuò)控制系統(tǒng)和糾錯(cuò)碼分類(lèi)差錯(cuò)控制系統(tǒng)和糾錯(cuò)碼分類(lèi) (1) 重傳反饋方式(ARQ)。 應(yīng)用ARQ方式糾錯(cuò)的通信系統(tǒng)如圖 1 - 9所示。 發(fā)送端發(fā)出能夠發(fā)現(xiàn)(檢測(cè))錯(cuò)誤的碼， 接收端收到通過(guò)信道傳來(lái)的碼后，在譯碼

12、器根據(jù)該碼的編碼規(guī)則，判決收到的碼序列中有無(wú)錯(cuò)誤產(chǎn)生，并通過(guò)反饋信道把判決結(jié)果用判決信號(hào)告訴發(fā)端。發(fā)端根據(jù)這些判決信號(hào)， 把接收端認(rèn)為有錯(cuò)的消息再次傳送，直到接收端認(rèn)為正確接收為止。 第一章 糾錯(cuò)碼的基本概念 圖 1 - 9 ARQ通信系統(tǒng) 第一章 糾錯(cuò)碼的基本概念 從上可知，應(yīng)用ARQ方式必須有一反饋信道，一般較適用于一個(gè)用戶(hù)對(duì)一個(gè)用戶(hù)（點(diǎn)對(duì)點(diǎn))的通信，且要求信源能夠控制，系統(tǒng)收發(fā)兩端必須互相配合、 密切協(xié)作，因此這種方式的控制電路比較復(fù)雜。由于反饋重發(fā)的次數(shù)與信道干擾情況有關(guān)，若信道干擾很頻繁，則系統(tǒng)經(jīng)常處于重發(fā)消息的狀態(tài)， 因此這種方式傳送消息的連貫性和實(shí)時(shí)性較差。該方式的優(yōu)點(diǎn)是： 編譯

13、碼設(shè)備比較簡(jiǎn)單；在一定的多余度碼元下，檢錯(cuò)碼的檢錯(cuò)能力比糾錯(cuò)碼的糾錯(cuò)能力要高得多，因而整個(gè)系統(tǒng)的糾錯(cuò)能力極強(qiáng)， 能獲得極低的誤碼率；由于檢錯(cuò)碼的檢錯(cuò)能力與信道干擾的變化基本無(wú)關(guān)，因此這種系統(tǒng)的適應(yīng)性很強(qiáng)，特別適應(yīng)于短波、散射、有線等干擾情況特別復(fù)雜的信道中。 第一章 糾錯(cuò)碼的基本概念 (2) 前向糾錯(cuò)方式(FEC)。發(fā)送端發(fā)送能夠被糾錯(cuò)的碼，接收端收到這些碼后，通過(guò)糾錯(cuò)譯碼器不僅能自動(dòng)地發(fā)現(xiàn)錯(cuò)誤， 而且能自動(dòng)地糾正接收碼字傳輸中的錯(cuò)誤。優(yōu)點(diǎn)：是不需要反饋信道，能進(jìn)行一個(gè)用戶(hù)對(duì)多個(gè)用戶(hù)的同播通信，譯碼實(shí)時(shí)性較好，控制電路比ARQ的簡(jiǎn)單。缺點(diǎn)：是譯碼設(shè)備比較復(fù)雜，所選用的糾錯(cuò)碼必須與信道的干擾情況

14、相匹配，因而對(duì)信道的適應(yīng)性較差。為了要獲得比較低的誤碼率，往往必須以最壞的信道條件來(lái)設(shè)計(jì)糾錯(cuò)碼，故所需的多余度碼元比檢錯(cuò)碼要多得多，從而使編碼效率很低。但由于這種方式能同播， 特別適用于軍用通信，并且隨著編碼理論的發(fā)展和編譯碼設(shè)備所需的大規(guī)模集成電路成本的不斷降低，譯碼設(shè)備有可能做得越來(lái)越簡(jiǎn)單，成本越來(lái)越低，因而在實(shí)際的數(shù)字通信中逐漸得到廣泛應(yīng)用。 第一章 糾錯(cuò)碼的基本概念 (3) 混合糾錯(cuò)方式(HEC)。這種方式是發(fā)送端發(fā)送的碼不僅能夠被檢測(cè)出錯(cuò)誤，而且還具有一定的糾錯(cuò)能力。接收端收到碼序列以后，首先檢驗(yàn)錯(cuò)誤情況，如果在糾錯(cuò)碼的糾錯(cuò)能力以?xún)?nèi)，則自動(dòng)進(jìn)行糾錯(cuò)。如果錯(cuò)誤很多，超過(guò)了碼的糾錯(cuò)能力，

15、 但能檢測(cè)出來(lái)，則接收端通過(guò)反饋信道，要求發(fā)端重新傳送有錯(cuò)的消息。 這種方式在一定程度上避免了FEC方式要求用復(fù)雜的譯碼設(shè)備和ARQ方式信息連貫性差的缺點(diǎn)，并能達(dá)到較低的誤碼率， 因此在實(shí)際中的應(yīng)用越來(lái)越廣。 第一章 糾錯(cuò)碼的基本概念 除了上述三種主要方式以外， 還有所謂狹義信息反饋系統(tǒng)(IRQ)。 這種方式是接收端把收到的消息原封不動(dòng)地通過(guò)反饋信道送回發(fā)送端，發(fā)送端比較發(fā)送的與反饋回來(lái)的消息，從而發(fā)現(xiàn)錯(cuò)誤，并且把傳錯(cuò)的消息再次傳送，最后達(dá)到使對(duì)方正確接收消息的目的。 為了便于比較，我們把上述幾種方式用圖 1 - 10所示的框圖表示。圖中，有斜線的方框表示在該端檢出錯(cuò)誤。在實(shí)際系統(tǒng)設(shè)計(jì)中，如何

16、根據(jù)實(shí)際情況選擇哪種差錯(cuò)控制方式是一個(gè)比較復(fù)雜的問(wèn)題，這里不再討論。 第一章 糾錯(cuò)碼的基本概念 圖圖 1 - 10 差錯(cuò)控制的基本方式差錯(cuò)控制的基本方式 第一章 糾錯(cuò)碼的基本概念 二、二、 糾錯(cuò)碼的分類(lèi)糾錯(cuò)碼的分類(lèi) 上述各種差錯(cuò)控制系統(tǒng)中所用到的碼，不外乎是能在譯碼器自動(dòng)發(fā)現(xiàn)錯(cuò)誤的檢錯(cuò)碼，或者不僅能發(fā)現(xiàn)錯(cuò)誤而且能自動(dòng)糾正錯(cuò)誤的糾錯(cuò)碼，或者能糾正刪除錯(cuò)誤的糾刪碼。但這三類(lèi)碼之間沒(méi)有明顯區(qū)分，以后將看到，任何一類(lèi)碼，按照譯碼方法不同， 均可作為檢錯(cuò)碼、 糾錯(cuò)碼或糾刪碼來(lái)使用。 除了上述的劃分方法以外， 通常還按以下方式對(duì)糾錯(cuò)碼進(jìn)行分類(lèi)： 第一章 糾錯(cuò)碼的基本概念 (1) 按照對(duì)信息元處理方法的不同

17、， 分為分組碼與卷積碼兩大類(lèi)。 分組碼分組碼是把信源輸出的信息序列，以k個(gè)碼元?jiǎng)澐譃橐欢危?通過(guò)編碼器把這段k個(gè)信息元按一定規(guī)則產(chǎn)生r個(gè)校驗(yàn)(監(jiān)督)元， 輸出長(zhǎng)為nk+r的一個(gè)碼組。因此每一碼組的校驗(yàn)元僅與本組的信息元有關(guān)，而與別組無(wú)關(guān)。分組碼用(n，k)表示，n表示碼長(zhǎng)，k表示信息位。 卷積碼卷積碼是把信源輸出的信息序列，以k0個(gè)(k0通常小于k)碼元分為一段，通過(guò)編碼器輸出長(zhǎng)為n0(k0)一段的碼段。 但是該碼段的n0-k0個(gè)校驗(yàn)元不僅與本組的信息元有關(guān)，而且也與其前m段的信息元有關(guān)，稱(chēng)m為編碼存貯。因此卷積碼用(n0，k0，m)表示。 第一章 糾錯(cuò)碼的基本概念 (2) 根據(jù)校驗(yàn)元與信息元

18、之間的關(guān)系分為線性碼與非線性碼。 若校驗(yàn)元與信息元之間的關(guān)系是線性關(guān)系(滿(mǎn)足線性疊加原理)， 則稱(chēng)為線性碼; 否則，稱(chēng)為非線性碼。 由于非線性碼的分析比較困難， 實(shí)現(xiàn)較為復(fù)雜， 故今后我們僅討論線性碼。 (3) 按照糾正錯(cuò)誤的類(lèi)型可分為糾正隨機(jī)(獨(dú)立)錯(cuò)誤的碼、 糾正突發(fā)錯(cuò)誤的碼和糾正同步錯(cuò)誤的碼，以及既能糾正隨機(jī)錯(cuò)誤又能糾正突發(fā)錯(cuò)誤的碼。 第一章 糾錯(cuò)碼的基本概念 (4) 按照每個(gè)碼元取值來(lái)分， 可分為二進(jìn)制碼與q進(jìn)制碼(q=pm，p為素?cái)?shù)，m為正整數(shù))。 (5) 按照對(duì)每個(gè)信息元保護(hù)能力是否相等可分為等保護(hù)糾錯(cuò)碼與不等保護(hù)(UEP)糾錯(cuò)碼。除非特別說(shuō)明，今后討論的糾錯(cuò)碼均指等保護(hù)能力的碼。

19、此外，在分組碼中按照碼的結(jié)構(gòu)特點(diǎn)， 又可分為循環(huán)碼與非循環(huán)碼。為了清楚起見(jiàn)，我們把上述分類(lèi)用圖 1 - 11表示。 第一章 糾錯(cuò)碼的基本概念 圖 1 - 11 糾錯(cuò)碼分類(lèi) 第一章 糾錯(cuò)碼的基本概念 1.3 最大似然譯碼和糾錯(cuò)碼的基本概念最大似然譯碼和糾錯(cuò)碼的基本概念 一、一、 基本定義基本定義 利用糾錯(cuò)碼進(jìn)行差錯(cuò)控制的數(shù)字通信系統(tǒng)如圖 1 - 12所示， 由此可如下定義分組碼。 定義定義1.3.1 分組碼是對(duì)每段k位長(zhǎng)的信息組，以一定規(guī)則增加r=n-k個(gè)校驗(yàn)元，組成長(zhǎng)為n的序列：(cn-1，cn-2，c1，c0)，稱(chēng)這個(gè)序列為碼字(碼組、碼矢)。在二進(jìn)制情況下，信息組總共有2k(q進(jìn)制為qk)

20、個(gè)，因此通過(guò)編碼器后，相應(yīng)的碼字也有2k個(gè)，稱(chēng)這2k個(gè)碼字集合為(n，k)分組碼。 第一章 糾錯(cuò)碼的基本概念 圖 1 - 12 利用分組碼的數(shù)字通信模型第一章 糾錯(cuò)碼的基本概念 n長(zhǎng)序列的可能排列總共有2n種(每一n長(zhǎng)序列稱(chēng)為n重)，而(n，k)分組碼的碼字集合只有2k種。所以，分組碼的編碼問(wèn)題就是定出一套規(guī)則，以便從2n個(gè)n重中選出2k個(gè)碼字，不同的選取規(guī)則就得到不同的碼。我們稱(chēng)被選取的2k個(gè)n重為許用碼組， 其余的2n-2k個(gè)為禁用碼組。 稱(chēng)Rkn為碼率，表示(n，k)分組碼中，信息位在碼字中所占的比重。R是衡量分組碼有效性的一個(gè)基本參數(shù)。 第一章 糾錯(cuò)碼的基本概念 圖 1 - 13是一個(gè)

21、(2, 1, 2)卷積碼編碼器。若輸入的信息序列以k01個(gè)碼元分段輸入，則輸出以n02個(gè)碼元為一段輸出， 如輸入的信息序列M(1 1 0 1 0 0)，輸出的碼序列為C(11， 10，10， 00， 01， 11， 00， )。可知隨著信息元的不斷輸入，輸出的是一個(gè)半無(wú)限長(zhǎng)的碼序列，由此可如下定義卷積碼。 第一章 糾錯(cuò)碼的基本概念 定義定義1.3.2 (n0，k0，m)卷積碼是對(duì)每段k0長(zhǎng)的信息組以一定的規(guī)則增加r0n0-k0個(gè)校驗(yàn)元，組成長(zhǎng)為n0的碼段。 n0-k0個(gè)校驗(yàn)元不僅與本段的信息元有關(guān)，且與前m段的信息元有關(guān)，當(dāng)信息元不斷輸入時(shí)，輸出的碼序列是一個(gè)半無(wú)限長(zhǎng)序列。 (n0，k0，m)

22、卷積碼的碼率Rk0 n0 。與分組碼的碼長(zhǎng)n相對(duì)應(yīng)，在卷積碼中稱(chēng)ncn0(m+1)為編碼約束長(zhǎng)度，說(shuō)明k0個(gè)信息元從輸入編碼器到離開(kāi)時(shí)在碼序列中影響的碼元數(shù)目，如圖 1 - 13中(2，1，2)卷積碼的nc 6。 第一章 糾錯(cuò)碼的基本概念 二、二、 最大似然譯碼最大似然譯碼 由圖1-2可知，信道輸出的R是一個(gè)二(或q)進(jìn)制序列，而譯碼器的輸出是一個(gè)信息序列M的估值序列 。 譯碼器的基本任務(wù)就是根據(jù)一套譯碼規(guī)則，由接收序列R給出與發(fā)送的信息序列M最接近(最好是相同)的估值序列 。由于M與碼字C之間存在一一對(duì)應(yīng)關(guān)系，所以這等價(jià)于譯碼器根據(jù)R產(chǎn)生一個(gè)C的估值序列 。顯然，當(dāng)且僅當(dāng) C時(shí)， M，這時(shí)譯

23、碼器正確譯碼。 MMCMC第一章 糾錯(cuò)碼的基本概念 如果譯碼器輸出的 C，則譯碼器產(chǎn)生了錯(cuò)誤譯碼。之所以產(chǎn)生錯(cuò)誤譯碼是由于：信道干擾很?chē)?yán)重， 超過(guò)了碼本身的糾錯(cuò)能力；其次，由于譯碼設(shè)備的故障(這點(diǎn)本書(shū)不予討論)。當(dāng)給定接收序列R時(shí)，譯碼器的條件譯碼錯(cuò)誤概率定義為 C)|()|(RCCPREP所以譯碼器的錯(cuò)誤譯碼概率 RERPREPP)()|(第一章 糾錯(cuò)碼的基本概念 P(R)是接收R的概率，與譯碼方法無(wú)關(guān)，所以譯碼錯(cuò)誤概率最小的最佳譯碼規(guī)則是使 )|(max)|(min)|(min)|(minminRCCPRCCPRCCPREPPRRE因此，如果譯碼器對(duì)輸入的R，能在2k個(gè)碼字中選擇一個(gè)使 最

24、大的碼字Ci作為C的估值序列 ，則這種譯碼規(guī)則一定使譯碼器輸出錯(cuò)誤概率最小，稱(chēng)這種譯碼規(guī)則為最大后驗(yàn)概率譯碼。 )2 , 2 , 1)(|(kiiRCCPC（1.3.1）第一章 糾錯(cuò)碼的基本概念 由貝葉斯公式 )()|()()|(RPCRPCPRCPiii可知，若發(fā)端發(fā)送每個(gè)碼字的概率P(Ci)均相同，且由于P(R)與譯碼方法無(wú)關(guān)，所以 kkiiiiCRPRCP2, , 2, 12, , 2, 1)|(max)|(max對(duì)DMC而言njijiicrPCRP1)|()|(（1.3.2）（1.3.3）這里碼字Ci(ci1，ci2，cin)，i1，2， ，2k。 第一章 糾錯(cuò)碼的基本概念 一個(gè)譯碼器

25、的譯碼規(guī)則若能在2k個(gè)碼字C中選擇某一個(gè)Ci使式(1.3.2)成為最大，則這種譯碼規(guī)則稱(chēng)為最大似然譯碼(MLD)，P(RC)稱(chēng)為似然函數(shù)，相應(yīng)的譯碼器稱(chēng)為最大似然譯碼器。由于logbx與x是單調(diào)關(guān)系，因此式(1.3.2)與式(1.3.3)可寫(xiě)成 njijibiibicrpCRPkk12, 2, 12, 2, 1)|(logmax)|(logmax稱(chēng)logb P(RC)為對(duì)數(shù)似然函數(shù)或似然函數(shù)。對(duì)于DMC信道， MLD是使譯碼錯(cuò)誤概率最小的一種最佳譯碼準(zhǔn)則或方法，但此時(shí)要求發(fā)端發(fā)送每一碼字的概率P(Ci)(i1，2，,2k)均相等，否則MLD不是最佳的。 在以后的討論中，都認(rèn)為P(Ci)均近似相

26、等。 第一章 糾錯(cuò)碼的基本概念 三、三、 漢明漢明(Hamming)距離與重量距離與重量 定義1.3.3 兩個(gè)n重x、y之間，對(duì)應(yīng)位取值不同的個(gè)數(shù)，稱(chēng)為它們之間的漢明距離，用d(x，y)表示。 例如，若x:(10101)，y： (01111)，則d(x，y)3 。 定義定義1.3.4 n重x中非零碼元的個(gè)數(shù)，稱(chēng)為它的漢明重量， 簡(jiǎn)稱(chēng)重量，用w(x)表示。 例如，若x： (10101)，則w(x)3。若y： (01111)，則w(y)4，等等。 第一章 糾錯(cuò)碼的基本概念 定義定義 1.3.5 (n，k)分組碼中，任兩個(gè)碼字之間距離的最小值， 稱(chēng)為該分組碼的最小漢明距離d0，簡(jiǎn)稱(chēng)最小距離 例如(3

27、,2)碼，n3，k2，共有224個(gè)碼字：000，011， 101，110，顯然d02。 d0是(n，k)分組碼的另一個(gè)重要參數(shù)。它表明了分組碼抗干擾能力的大小。以后將看到： d0越大，碼的抗干擾能力越強(qiáng)， 在同樣譯碼方法下它的譯碼錯(cuò)誤概率越小。由上可知，R和d0是(n，k)分組碼的兩個(gè)最重要參數(shù)。糾錯(cuò)編碼的基本任務(wù)之一就是構(gòu)造出R一定、 d0盡可能大的碼，或d0一定、R盡可能高的碼。 下面用幾個(gè)具體例子說(shuō)明碼的R、d0以及譯碼錯(cuò)誤概率之間的關(guān)系。 0,( , )min ( , )x yn kdd x y第一章 糾錯(cuò)碼的基本概念 例例1.1 重復(fù)碼 重復(fù)碼是k1的(n，1)碼，它的編碼規(guī)則(即在

28、2n個(gè)n重中挑選2k21 個(gè)碼字的規(guī)則)是(n-1)個(gè)校驗(yàn)元是信息元的重復(fù)，設(shè)信息元為cn-1，則校驗(yàn)元cicn-1(i=0，1，2，n-2)。 由于信息組只有2k2組：0和1，因此相應(yīng)的許用碼字只有兩個(gè)(000)和(111)。設(shè)它們通過(guò)BSC傳輸，信道的轉(zhuǎn)移概率為pe。 通常情況下，pe0.5，因此在傳輸中沒(méi)有錯(cuò)誤的可能性比出現(xiàn)一個(gè)錯(cuò)誤的可能性大，出現(xiàn)一個(gè)錯(cuò)誤的可能性比出現(xiàn)兩個(gè)錯(cuò)誤的大，等等。也就是說(shuō)信道錯(cuò)誤圖樣E中，出現(xiàn)重量最輕的圖樣可能性最大。 第一章 糾錯(cuò)碼的基本概念 P(w(E)0)P(w(E)1)P(w(E)2)或 221)1 ()1 ()1 (neeneeneppppp 由ER-

29、C及式(1.3.2)可知，MLD譯碼器尋求可能出現(xiàn)的錯(cuò)誤圖樣，就是由接收到的R在2k個(gè)碼字集中，尋求與R的漢明距離最小的碼字Ci，為最可能發(fā)送的碼字而接收，這就是最小漢明距離譯碼(或稱(chēng)最近臨區(qū)譯碼)。(試證明：在DMC中，最小漢明距離譯碼就是MLD。)在重復(fù)碼情況下這種譯碼方案就是根據(jù)收到序列中0和1的多少，來(lái)判斷信息組是0還是1。若接收序列中1的個(gè)數(shù)大于n2，則判為1；否則，判為0。這種譯碼方案就是大數(shù)準(zhǔn)則譯碼。 第一章 糾錯(cuò)碼的基本概念 當(dāng)n是奇數(shù)時(shí)，按照這種大數(shù)準(zhǔn)則譯碼方法，譯碼器總可以很快地作出是0還是1的判決。當(dāng)n是偶數(shù)時(shí)可能出現(xiàn)以下情況， 即接收序列中“1”的個(gè)數(shù)和“0”的個(gè)數(shù)剛好

30、相等，此時(shí)若按大數(shù)準(zhǔn)則無(wú)法作出判斷，造成譯碼失敗，這種譯碼稱(chēng)為不完備譯碼。 而n為奇數(shù)情況下的譯碼(即譯碼器一定作出是哪一個(gè)信息組的判決)稱(chēng)為完備譯碼。 譯碼失敗只表明譯碼器無(wú)法給出明確判斷， 但并不等于譯碼錯(cuò)誤，而僅表明接收序列中存在有錯(cuò)誤。此時(shí)， 如果我們與ARQ系統(tǒng)相結(jié)合，則可以利用此信息要求對(duì)方重發(fā)該組信息，直到譯碼器作出明確判決為止。 下面幾個(gè)具體例子說(shuō)明重復(fù)碼的抗干擾能力。 第一章 糾錯(cuò)碼的基本概念 (1) (1，1)碼。這種碼n1，k1，d1，R1，顯然無(wú)任何抗干擾能力。設(shè)BSC中的pe0.1，則這種碼的誤碼率仍為0.1。 (2) (2，1)重復(fù)碼。該重復(fù)碼的兩個(gè)許用碼字是(00

31、)和(11)， d02，R12。若用不完備譯碼(并與ARQ結(jié)合)則譯碼錯(cuò)誤概率為p2e10-2。也就是說(shuō)只有當(dāng)(00)錯(cuò)成(11)或(11)錯(cuò)成(00)時(shí)， 才造成譯碼錯(cuò)誤。 而(01)和(10)不是許用碼字，不會(huì)造成譯碼錯(cuò)誤。因此，這個(gè)碼能發(fā)現(xiàn)傳輸中的一個(gè)錯(cuò)誤，但不能自動(dòng)糾正。 第一章 糾錯(cuò)碼的基本概念 (3) (3，1)重復(fù)碼。顯然，它的兩個(gè)碼字是(000)和(111)，d03，R13。設(shè)發(fā)的是(000)，若收到的是(001)或(010)或(100)， 則根據(jù)大數(shù)譯碼準(zhǔn)則正確地判為(000)，信息組為0。若收到的是(011)，(101)，(110)，(111)中之一，則造成譯碼錯(cuò)誤， 錯(cuò)判

32、為信息組是1。因此，該碼若用完備譯碼能糾正序列中的一個(gè)錯(cuò)誤， 此時(shí)譯碼錯(cuò)誤概率p1-Q1-(1-pe)3+3pe(1- pe)2=2.810-2也就是誤碼率由0.1減至2.810-2。 若該碼不用作糾錯(cuò)，而采用不完備譯碼用作檢錯(cuò)， 則可以發(fā)現(xiàn)兩個(gè)錯(cuò)誤，與ARQ系統(tǒng)結(jié)合后，譯碼錯(cuò)誤概率減至p3e10-3。 第一章 糾錯(cuò)碼的基本概念 (4) (4，1)重復(fù)碼。顯然，該碼的d04，R14。由于n是偶數(shù)，故只能采取不完備譯碼。它的糾錯(cuò)能力如下： 能糾正一個(gè)錯(cuò)誤同時(shí)發(fā)現(xiàn)兩個(gè)錯(cuò)誤。 若發(fā)送的是(0000)， 則錯(cuò)一個(gè)時(shí)，根據(jù)大數(shù)準(zhǔn)則可正確判斷發(fā)送的是0信息組。 若錯(cuò)兩個(gè)變成(0011)，(1100)，(1

33、010)， (0101)， (1001)， (0110)之一時(shí)， 則譯碼器無(wú)法作出判決，而指出發(fā)生了兩個(gè)錯(cuò)誤。 僅在變成(1110)， (0111)， (1011)， (1101)和(1111)時(shí)， 譯碼器才作出錯(cuò)誤譯碼。 因此， 這時(shí)的譯碼錯(cuò)誤概率 434106 . 3)1 (4eeepppp第一章 糾錯(cuò)碼的基本概念 若僅用來(lái)檢錯(cuò)，則可檢測(cè)ed0-13個(gè)錯(cuò)誤。顯然，若發(fā)送的是(0000)， 則僅在變成(1111)時(shí)，才產(chǎn)生錯(cuò)誤譯碼，而其它情況均能正確譯碼或發(fā)現(xiàn)錯(cuò)誤。因此，此時(shí)的譯碼錯(cuò)誤概率pp4e10-4。 第一章 糾錯(cuò)碼的基本概念 (5) (5，1)重復(fù)碼。(5，1)碼的d05，R15。它

34、的糾錯(cuò)能力如下： 能糾正兩個(gè)隨機(jī)錯(cuò)誤， 這時(shí)的譯碼錯(cuò)誤概率 33245107993. 01)1 (25)1 (15)1(1eeeeepppppp 因此，傳送信息組0、1的錯(cuò)誤概率從0.1降至千分之七， 約降低了兩個(gè)量級(jí)。 第一章 糾錯(cuò)碼的基本概念 若僅用來(lái)檢錯(cuò)，則能發(fā)現(xiàn)ed0-14個(gè)錯(cuò)誤。若與ARQ系統(tǒng)結(jié)合進(jìn)行糾錯(cuò)，則譯碼錯(cuò)誤概率大約為pp5e10-5。 由上面有關(guān)重復(fù)碼的一系列例子可以看到： (1) 隨著碼長(zhǎng)n的增加，重復(fù)碼的d0n越來(lái)越大，抗干擾能力越來(lái)越強(qiáng)，即dn1，誤碼率也越來(lái)越小，但碼率R1n卻越來(lái)越低，并隨著n的增加而趨近于零。 (2) 在用同樣的(n，k)碼下，應(yīng)用非完備譯碼并與

35、ARQ系統(tǒng)相結(jié)合，譯碼器所給出的誤碼率比完備譯碼所產(chǎn)生的要低得多。 通過(guò)上面這些例子還可看出，(n，k)分組碼的最小距離d0(今后簡(jiǎn)稱(chēng)d)與糾錯(cuò)能力有如下關(guān)系。 第一章 糾錯(cuò)碼的基本概念 定理定理1.3.1 任一(n，k)分組碼，若要在碼字內(nèi)： (1) 檢測(cè)e個(gè)隨機(jī)錯(cuò)誤， 則要求碼的最小距離de+1； (2) 糾正t個(gè)隨機(jī)錯(cuò)誤，則要求d2t+1; (3) 糾正t個(gè)隨機(jī)錯(cuò)誤，同時(shí)檢測(cè)e(t)個(gè)錯(cuò)誤，則要求dt+e+1。 (4) 糾正t個(gè)錯(cuò)誤和個(gè)刪除，則要求d2t+1。 證明(1)由圖1-14(a)可知，若C1發(fā)生了e個(gè)錯(cuò)誤變?yōu)镃1， 則d(C1， C1)e，設(shè)ed-1，則d(C1 ，C2)1，故

36、C1 C2，因此譯碼器不會(huì)將C1錯(cuò)判成C2，檢測(cè)到e=d-1個(gè)錯(cuò)誤。 第一章 糾錯(cuò)碼的基本概念 圖 1 - 14 糾錯(cuò)碼糾錯(cuò)能力的幾何解釋 第一章 糾錯(cuò)碼的基本概念 (2) 設(shè)C1與C2是(n，k)碼中任兩碼字距離之最小者，且為2t+1。 則C1錯(cuò)了t個(gè)錯(cuò)誤以后變成C1，它們之間的距離d(C1，C1)=t， 但d(C1，C2)t+1。d(C1，C2)d(C1，C1)，如圖 1-14(b)所示，所以譯碼器可以根據(jù)它們之間的距離的大小正確譯碼， 從而糾正t個(gè)錯(cuò)誤。 (3) 這里所指的同時(shí)，是當(dāng)錯(cuò)誤個(gè)數(shù)t時(shí)，該碼能糾正t個(gè)錯(cuò)；當(dāng)錯(cuò)誤個(gè)數(shù)大于t而小于e時(shí)，則碼能發(fā)現(xiàn)e個(gè)錯(cuò)誤。 由(1)和(2)的證明可

37、直接得到結(jié)論(3)， 請(qǐng)讀者自行證明。 由此定理可知，一個(gè)距離為d的分組碼，至多能糾正t(d-1)2(x是x的整數(shù)部分)個(gè)錯(cuò)誤。該定理確定了碼的糾錯(cuò)能力與它的距離之間的關(guān)系，是糾錯(cuò)碼理論中最基本的定理之一。 第一章 糾錯(cuò)碼的基本概念 例例1.2 奇偶校驗(yàn)(監(jiān)督)碼 奇偶校驗(yàn)碼是只有一個(gè)校驗(yàn)元的(n， n-1)分組碼。 設(shè)給定kn-1位的二進(jìn)制信息碼組為:mk-1，mk-2，m1，m0，則按如下規(guī)則完成碼中一個(gè)碼字(cn-1，cn-2，c1，c0)的編碼：cn-1mk-1，cn-2mk-2，c2m1，c1m0，而一個(gè)校驗(yàn)元c0mk-1+mk-2+m1+m0或mk-1+mk-2+m1+m0 +c0

38、0cn-1+cn-2+c1+c00 (1.3.5)該式保證每個(gè)碼字中“1”的個(gè)數(shù)為偶數(shù)，所以稱(chēng)這種校驗(yàn)關(guān)系為奇偶校驗(yàn)。由于分組碼中的每一個(gè)碼字均按同一規(guī)則構(gòu)成，故稱(chēng)這種分組碼為一致校驗(yàn)碼。顯然，碼中的碼字?jǐn)?shù)目M2k2n-1。 第一章 糾錯(cuò)碼的基本概念 (1) (2，1)奇偶校驗(yàn)碼。此碼的n=2，k1，按c1+c00求出校驗(yàn)元c0=c1，所以?xún)蓚€(gè)許用碼組是00和11，此時(shí)d2，R12，能發(fā)現(xiàn)一個(gè)錯(cuò)誤。若在pe0.1的BSC中傳送，則利用不完備譯碼并與ARQ相結(jié)合，可使誤碼率大約減至p10-2。 (2) (3，2)碼。此碼有224個(gè)信息組，由式(1.3.5)求得校驗(yàn)元，得到相應(yīng)的4個(gè)碼字為：000

39、， 011，101，110。由此看出， 這4個(gè)信息組就是在8個(gè)二進(jìn)制三重中，把重量為偶數(shù)的4個(gè)三重挑選為許用碼字，重量為奇數(shù)的其它4個(gè)為禁用碼組。顯然，該碼的d2，也只能發(fā)現(xiàn)碼元中的一個(gè)錯(cuò)誤。譯碼誤碼率大約為 32R22107 . 2)1 (23eepPp第一章 糾錯(cuò)碼的基本概念 (3) (4，3)碼。該碼的8個(gè)碼字是按照式(1.3.5)的要求，在16個(gè)二進(jìn)制四重中挑選出來(lái)的，其重量均為偶數(shù)。該碼的d2， R34，故只能檢測(cè)碼字中的一位錯(cuò)誤。其譯碼誤碼率約為 。 由上看出，(n，n-1)奇偶校驗(yàn)碼。當(dāng)它的n時(shí)，R1，但d2，dn0，譯碼誤碼率ppe，接近未編碼時(shí)的情況。 即隨著碼長(zhǎng)的增加，抗干

40、擾能力接近于零。 上述(n，1)和(n，n-1)碼，隨著碼長(zhǎng)n的增加，前者R0， 后者抗干擾能力接近于零，或dn0，都不理想。那么是否存在有一種碼，隨著n的增加。其糾錯(cuò)能力和傳信率都保持一定呢？換言之，在R一定時(shí)，隨著n，dn0，從而使p0的碼是否存在？1949年香農(nóng)(Shannon)的信道編碼定理對(duì)此作了肯定的回答。 2432105)1 (24eeepppp第一章 糾錯(cuò)碼的基本概念 1.4 信道編碼定理信道編碼定理 信道編碼定理 每個(gè)信道具有確定的信道容量C，對(duì)任何小于C的碼率R，存在有速率為R碼長(zhǎng)為n的分組碼及(n0，k0，m)卷積碼，若用最大似然譯碼，則隨著碼長(zhǎng)的增加其譯碼錯(cuò)誤概率p可任

41、意小， 即 )(RnEbbeAp和 )()()1(0REncREnmcccceAeAp(1.4.1) 第一章 糾錯(cuò)碼的基本概念 式中，Ab和Ac為大于0的系數(shù)，Eb(R)和Ec(R)為正實(shí)函數(shù)，稱(chēng)為誤差指數(shù)，它與R、C的關(guān)系如圖1 - 15所示。圖中，C1、C2為信道容量，且C1C2。由信息論的基本知識(shí)可知，在高斯白噪聲信道時(shí)， 信道容量 )/(1log02sbitWNPWCS式中，W是信道所能提供的帶寬，PSEST是信號(hào)功率，ES是信號(hào)能量，T是分組碼信號(hào)的持續(xù)時(shí)間即信號(hào)寬度，PSW是單位頻帶的信號(hào)功率，N0是單位頻帶的噪聲功率， PS (WN0)是信噪比。 第一章 糾錯(cuò)碼的基本概念 由式(

42、1.4.1)和圖 1-15可看出，信道容量C、碼長(zhǎng)n和錯(cuò)誤概率p之間的轉(zhuǎn)換關(guān)系。為了滿(mǎn)足一定誤碼率p的要求，可用以下兩類(lèi)方法實(shí)現(xiàn)。 一是增加信道容量C，從而使E(R)增加。由C的表示式(1.4.2)可知，增加C的方法可以采用如加大系統(tǒng)帶寬或增加信噪比的方法來(lái)達(dá)到。例如，采用調(diào)頻、調(diào)相等寬帶調(diào)制方法； 增加發(fā)射機(jī)的功率；應(yīng)用高增益天線；采用分集接收及低噪聲器件等方法。這些措施是從根本上改善信道、增加信道容量、減少誤碼率的方法， 是通信設(shè)計(jì)工作者經(jīng)常采用的傳統(tǒng)方法。 第一章 糾錯(cuò)碼的基本概念 圖 1-15 信道容量C、碼長(zhǎng)n和錯(cuò)誤概率p之間的轉(zhuǎn)換關(guān)系第一章 糾錯(cuò)碼的基本概念 另一種方法是在R一定下，增加分組碼長(zhǎng)n(也就是增加分組信號(hào)持續(xù)時(shí)間T)，可使p隨n的增加而呈指數(shù)下降。 但由于碼長(zhǎng)n的增加，當(dāng)R保持一定時(shí)，可能發(fā)送的碼字?jǐn)?shù)2k指數(shù)增加， 從而增加了譯碼設(shè)備的復(fù)雜性。這種方法就是信道編碼定理所指出減少誤碼率的另一方向，它為通信設(shè)計(jì)工作者提供了一條新的途徑。下面通過(guò)幾個(gè)具體例子說(shuō)明R保持一定時(shí)，隨著n的增加，可使p下降。 第一章 糾錯(cuò)碼的基本概念 例例1.3 設(shè)有一個(gè)隨機(jī)產(chǎn)生二進(jìn)制序列的信源和一個(gè)轉(zhuǎn)移概率pe0.1的BSC。如果不編碼，則傳送