通信原理教程第十章

1、大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院1 1 1 1第第1010章章 信道編碼和差錯(cuò)控制信道編碼和差錯(cuò)控制10.1 10.1 引言引言 10.10.2 2 常用的幾種簡(jiǎn)單分組碼常用的幾種簡(jiǎn)單分組碼 10.3 10.3 線性分組碼線性分組碼 10.4 10.4 循環(huán)碼循環(huán)碼 10.5 10.5 卷積碼卷積碼 10.6 10.6 本章小結(jié)本章小結(jié)大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院2 2 2 210.1 引言引言10.1.1 信道編碼信道編碼 在數(shù)字通信中，編碼可分為信源編碼信源編碼和信道編碼信道編碼。 信源編碼是為了提高數(shù)字信號(hào)的有效性以及為了使模擬信號(hào)數(shù)字

2、化而采取的編碼。 信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。 數(shù)字信號(hào)在傳輸過(guò)程中，加性噪聲、碼間串?dāng)_等都會(huì)產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)信道編碼技術(shù)。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院3 3 3 3信道編碼：n目的：提高信號(hào)傳輸?shù)目煽啃?。n方法：增加多余比特，以發(fā)現(xiàn)或糾正錯(cuò)誤。 差錯(cuò)控制：包括信道編碼在內(nèi)的一切糾正錯(cuò)誤手段。產(chǎn)生錯(cuò)碼的原因：n乘性干擾引起的碼間串?dāng)_n加性干擾引起的信噪比降低大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院4

3、4 4 4信道分類(lèi)：按照加性干擾造成錯(cuò)碼的統(tǒng)計(jì)特性不同加性干擾造成錯(cuò)碼的統(tǒng)計(jì)特性不同劃分n隨機(jī)信道：錯(cuò)碼隨機(jī)出現(xiàn)，各個(gè)錯(cuò)碼出現(xiàn)是統(tǒng)計(jì)獨(dú)立的。例如由白噪聲引起的錯(cuò)碼。恒參高斯白噪聲信道是典型的隨機(jī)信道n突發(fā)信道：錯(cuò)碼相對(duì)集中出現(xiàn)，即在短時(shí)間段內(nèi)有很多錯(cuò)碼出現(xiàn)，而在這些短時(shí)間段之間有較長(zhǎng)的無(wú)錯(cuò)碼時(shí)間段，例如由脈沖干擾引起的錯(cuò)碼。具有脈沖干擾的信道是典型的突發(fā)信道。 n混合信道：信道中的錯(cuò)碼既有隨機(jī)的又有突發(fā)的。短波信道和對(duì)流層散射信道是典型的混合信道。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院5 5 5 510.1.2 差錯(cuò)控制方式差錯(cuò)控制方式 圖 10-1 差錯(cuò)控制方式 發(fā)端糾錯(cuò)碼

4、收端前向糾錯(cuò)FEC發(fā)端檢錯(cuò)碼收端檢錯(cuò)重發(fā)ARQ判決信號(hào)發(fā)端檢錯(cuò)和糾錯(cuò)碼收端混合糾錯(cuò)HEC判決信號(hào)大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院6 6 6 6 1. 檢錯(cuò)重發(fā)方式檢錯(cuò)重發(fā)方式 檢錯(cuò)重發(fā)又稱(chēng)自動(dòng)請(qǐng)求重傳方式，記作ARQ (Automatic Repeat Request)。 需要反饋信道 譯碼設(shè)備簡(jiǎn)單 對(duì)突發(fā)錯(cuò)誤和信道干擾較嚴(yán)重時(shí)有效（相對(duì)于FEC而言） 但實(shí)時(shí)性差。 主要用在計(jì)算機(jī)數(shù)據(jù)通信中，另外海上通信NBDP中也使用ARQ。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院7 7 7 7 2. 前向糾錯(cuò)方式前向糾錯(cuò)方式 前向糾錯(cuò)方式記作FEC ( Forwar

5、d Error Correction)。 發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動(dòng)地糾正傳輸中的錯(cuò)誤。 單向傳輸 實(shí)時(shí)性好 但譯碼設(shè)備較復(fù)雜。 海上衛(wèi)星通信Inmarsat-A中采用。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院8 8 8 8 3. 混合糾錯(cuò)方式混合糾錯(cuò)方式 混合糾錯(cuò)方式記作HEC (Hybrid Error Correction)是FEC和ARQ方式的結(jié)合。 發(fā)端發(fā)送具有自動(dòng)糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能力范圍以內(nèi)，則自動(dòng)糾錯(cuò)，如果超過(guò)了碼的糾錯(cuò)能力，但能檢測(cè)出來(lái)，則經(jīng)過(guò)反饋信道請(qǐng)求發(fā)端重發(fā)。 這種方式具有自動(dòng)糾錯(cuò)

6、和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可以達(dá)到較低的誤碼率。近年來(lái)得到廣泛應(yīng)用，如海上衛(wèi)星通信Inmarsat-C中應(yīng)用。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院9 9 9 910.1.3 糾錯(cuò)碼的分類(lèi)糾錯(cuò)碼的分類(lèi) (1) 根據(jù)糾錯(cuò)碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼線性碼和非線性碼非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱(chēng)為線性碼，否則為非線性碼。 (2) 根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。 (3) 根據(jù)碼的用途，可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼

7、以檢錯(cuò)為目的，不一定能糾錯(cuò)；而糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。 大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院10101010編碼序列的參數(shù)nn 編碼序列中總碼元數(shù)量nk 編碼序列中信息碼元數(shù)量nr 編碼序列中差錯(cuò)控制碼元數(shù)量；n差錯(cuò)控制碼元稱(chēng)為監(jiān)督碼元或監(jiān)督位nk/n 編碼效率n(n - k) / k = r / k 冗余度大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院11 11 11 1110.1.4 糾錯(cuò)編碼的基本原理分組碼舉例n設(shè)：有一種由3個(gè)二進(jìn)制碼元構(gòu)成的編碼，它共有23 = 8種n不同的可能碼組：000 晴 001 云 010 陰 011 雨100 雪 101

8、 霜 110 霧 111 雹這時(shí)，若一個(gè)碼組中發(fā)生錯(cuò)碼，則將收到錯(cuò)誤信息。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院12121212 若在此8種碼組中僅允許使用4種來(lái)傳送天氣，例如：令000 晴 011 云 101 陰 110 雨為許用碼組，其他4種不允許使用，稱(chēng)為禁用碼組。 這時(shí)，接收端有可能發(fā)現(xiàn)（檢測(cè)到）碼組中的一個(gè)錯(cuò)碼。p這種編碼只能檢測(cè)錯(cuò)碼，不能糾正錯(cuò)碼。 n若規(guī)定只許用兩個(gè)碼組：例如000 晴 111 雨就能檢測(cè)兩個(gè)以下錯(cuò)碼，或糾正一個(gè)錯(cuò)碼。 大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院13131313 00 ：晴 01 ：云 10 ：陰 11 ：雨0001

9、1011如果不要求檢（糾）錯(cuò)，為了傳輸4種不同的信息，只需兩位碼組就夠了，它們是：00，01，10，11。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院14141414 00 0：晴 01 1：云 10 1：陰 11 0：雨000010100110001101111011信息位監(jiān)督位代表所傳輸信息的這些兩位碼稱(chēng)為信息位。多增加的那位稱(chēng)為監(jiān)督位。把這種將信息碼分組，為每組信碼附加若干監(jiān)督碼的編碼集合，稱(chēng)為分組碼。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。第1位：1第2位：1第3位：1大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院15151515 1. 分組碼分組碼 分組碼

10、一般可用(n, k)表示。其中，k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱(chēng)為碼組長(zhǎng)度，簡(jiǎn)稱(chēng)碼長(zhǎng)。n-k=r為每個(gè)碼組中的監(jiān)督碼元數(shù)目。簡(jiǎn)單地說(shuō)，分組碼是對(duì)每段k位長(zhǎng)的信息組以一定的規(guī)則增加r個(gè)監(jiān)督元，組成長(zhǎng)為n的碼字。在二進(jìn)制情況下，共有2k個(gè)不同的信息組，相應(yīng)地可得到2k個(gè)不同的碼字，稱(chēng)為許用碼組。其余 2n-2k個(gè)碼字未被選用，稱(chēng)為禁用碼組。 krn大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院16161616k個(gè)信息位r個(gè)監(jiān)督位an-1an-2.arar-1ar-2.a0t碼長(zhǎng) n = k + r分組碼的結(jié)構(gòu)大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)

11、學(xué)院17171717 在分組碼中，非零碼元“1”的數(shù)目稱(chēng)為碼字的漢明(Hamming)重量， 簡(jiǎn)稱(chēng)碼重。例如，碼字 10110，碼重w=3。 兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的數(shù)目稱(chēng)為這兩個(gè)碼組的漢明(Hamming)距離，簡(jiǎn)稱(chēng)碼距。例如 11000 與 10011之間的距離d=3。 在碼組集中，任意兩個(gè)碼字之間距離的最小值稱(chēng)為碼的最小距離，用d表示。 最小碼距是碼的一個(gè)重要參數(shù)，它是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。 大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院18181818 碼距的幾何意義：以n = 3的編碼為例 一般而言，碼距是 n 維空間中單位正多面體頂點(diǎn)之間的漢明距離。 各頂點(diǎn)

12、之間沿多面體各邊行走的幾何距離。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1碼字（a2 a1 a0 )大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院191919192. 檢錯(cuò)和糾錯(cuò)能力檢錯(cuò)和糾錯(cuò)能力 若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡(jiǎn)單重復(fù)，則稱(chēng)該分組碼為重復(fù)碼重復(fù)碼。它是一種簡(jiǎn)單實(shí)用的檢錯(cuò)碼，并有一定的糾錯(cuò)能力。 例如，(2,1)重復(fù)碼，兩個(gè)許用碼組是 00 與 11，d0=2，收端譯碼，出現(xiàn) 01、10 禁用碼組時(shí)，可以發(fā)現(xiàn)傳輸中的一位錯(cuò)誤。如果是(3,1)重復(fù)碼，兩個(gè)許用碼組是 0

13、00 與111, d0=3; 當(dāng)收端出現(xiàn)兩個(gè)或三個(gè) 1 時(shí)，判為 1，否則判為0。此時(shí)，可以糾正單個(gè)錯(cuò)誤，或者該碼可以檢出兩個(gè)錯(cuò)誤。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院20202020 碼的最小距離碼的最小距離d0直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力：直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力： 任一任一(n, k)分組碼，若要在碼字內(nèi)分組碼，若要在碼字內(nèi): (1) 檢測(cè)檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0e+1; 0 1 2 3BAed0碼距等于3的兩個(gè)碼組大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院21212121 設(shè)一碼組A位于0點(diǎn)，若碼組A中

14、發(fā)生一位錯(cuò)碼，則可以認(rèn)為A的位置將移到以0點(diǎn)為圓心、以1為半徑的圓上某點(diǎn)，但其位置不會(huì)超過(guò)此圓； 若碼組A中發(fā)生兩位錯(cuò)碼，則其位置不會(huì)超出以0點(diǎn)為圓心，以2為半徑的圓，因此，只要最小碼距不小于3(如圖中B點(diǎn))，在此半徑為2的圓上及圓內(nèi)就不會(huì)有其他碼組，也就是說(shuō)，碼組A發(fā)生兩位以下錯(cuò)碼時(shí)，不可能變成另一任何許用碼組，因而能檢測(cè)錯(cuò)碼的位數(shù)為2。 同理，若一種編碼的最小碼距為d0，則將能檢測(cè)（ d0 -1）個(gè)錯(cuò)碼；反之，若要檢測(cè)e個(gè)錯(cuò)碼，則最小碼距至少應(yīng)不少于（e+1）。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院22222222 (2) 糾正糾正t個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離個(gè)隨機(jī)錯(cuò)

15、誤，則要求碼的最小距離d02t+1;BtA012345td0碼距等于5的兩個(gè)碼組若碼組A和B發(fā)生不多于t位錯(cuò)誤，則其位置均不會(huì)超出以C1和C2為圓心，t為半徑的圓，只要這兩個(gè)圓不相交，則當(dāng)誤碼小于t時(shí)，可根據(jù)它們落入哪個(gè)圓內(nèi)，就可正確地判為A或B，即可糾錯(cuò)。以C1、C2為圓心，以t為半徑的兩圓不相交的最近圓心距離為2t+1，即為糾t個(gè)錯(cuò)誤的最小距離。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院23232323(3) 糾正糾正t個(gè)同時(shí)檢測(cè)個(gè)同時(shí)檢測(cè)e(t)個(gè)隨機(jī)錯(cuò)誤，則要求碼的個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離最小距離d0t+e+1。AB1tte碼距等于(e+t+1)的兩個(gè)碼組 “糾正t

16、個(gè)錯(cuò)誤，同時(shí)檢測(cè)e個(gè)錯(cuò)誤”，簡(jiǎn)稱(chēng)“糾檢結(jié)合”。差錯(cuò)控制設(shè)備按照接收碼組與許用碼組的距離自動(dòng)改變工作方式。若接收碼組與某一許用碼組間的距離在糾錯(cuò)能力t范圍內(nèi)，則將按糾錯(cuò)方式工作，若與任何碼組間的距離都超過(guò)t，則按檢錯(cuò)方式工作。 大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院24242424AB1tte碼距等于(e+t+1)的兩個(gè)碼組 證明：設(shè)碼的檢錯(cuò)能力為e，則當(dāng)碼組A中存在e個(gè)錯(cuò)碼時(shí)，該碼組與任一許用碼組的距離至少應(yīng)為t+1，否則將進(jìn)入許用碼組B的糾錯(cuò)能力范圍內(nèi)，而被錯(cuò)糾為B。 因此，要求最小碼距滿足(3)。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院25252525 3

17、. 編碼效率編碼效率 用差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價(jià)換來(lái)的。定義編碼效率R來(lái)衡量有效性:R=k/n其中, k是信息元的個(gè)數(shù)，n為碼長(zhǎng)。 對(duì)糾錯(cuò)碼的基本要求是: 檢錯(cuò)和糾錯(cuò)能力盡量強(qiáng)；編碼效率盡量高；編碼規(guī)律盡量簡(jiǎn)單。 實(shí)際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯(cuò)能力和編碼效率，并且易于實(shí)現(xiàn)。 大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院262626264. 差錯(cuò)控制編碼的效用 設(shè)信道發(fā)生01和10的錯(cuò)誤概率都為p，則在碼長(zhǎng)為n的碼組中，恰好發(fā)生r個(gè)錯(cuò)碼的概率為 以n=7, p=10-3為例，則 P7(1)=7p=710-3 P7(2)=21p2=2.110

18、-5 P7(3)=35p3=3.510-8!( )(1)()!()!1( )!()!rrnrrnrnnrnpnP rC ppprnrnP rprnr-=-=-可見(jiàn)，采用差錯(cuò)控制編碼，即使僅能糾正(或檢測(cè))1-2個(gè)錯(cuò)誤，也可使誤碼率下降幾個(gè)數(shù)量級(jí)。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院2727272710.2 常用的幾種簡(jiǎn)單分組碼常用的幾種簡(jiǎn)單分組碼10.2.1 奇偶監(jiān)督碼奇偶監(jiān)督碼 奇偶監(jiān)督碼是在原信息碼后面附加一個(gè)監(jiān)督元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)?；蛘哒f(shuō)，它是含一個(gè)監(jiān)督元，碼它是含一個(gè)監(jiān)督元，碼重為奇數(shù)或偶數(shù)的重為奇數(shù)或偶數(shù)的(n, n-1)(n, n-1)分組碼

19、分組碼。 奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼，檢錯(cuò)能力相同。 設(shè)碼字A=an-1,an-2,a1,a0對(duì)偶監(jiān)督碼有對(duì)奇監(jiān)督碼有奇偶監(jiān)督碼的編碼效率12100nnaaaa-排排=12101nnaaaa-排排=1nRn-=大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院28282828 檢錯(cuò)能力：能夠檢測(cè)奇數(shù)個(gè)錯(cuò)碼。奇偶監(jiān)督碼不能檢測(cè)碼組中出現(xiàn)的偶數(shù)個(gè)錯(cuò)碼。10.2.2 行列監(jiān)督碼（二維奇偶監(jiān)督碼、方陣碼） 11na12na11a10a21na22na21a20amna1mna2ma1ma01nc2nc1c0c.有可能檢測(cè)偶數(shù)個(gè)錯(cuò)碼適合檢測(cè)突發(fā)錯(cuò)碼 能夠糾正部分錯(cuò)碼水平校驗(yàn)元垂直校驗(yàn)元信元

20、大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院29292929 編碼器按行（每行n-1個(gè)碼）分組（共m組）輸入信元，對(duì)每行按奇或偶校驗(yàn)加水平校驗(yàn)元，再對(duì)每列按奇或偶校驗(yàn)加垂直校驗(yàn)元后，按列次序輸出傳送。 方陣碼可以檢測(cè)全部奇數(shù)個(gè)錯(cuò)碼和大部分偶數(shù)個(gè)錯(cuò)碼；但不能檢測(cè)出行、列中同時(shí)出現(xiàn)偶數(shù)個(gè)錯(cuò)的情況（即不能檢測(cè)出矩形四角位置上同時(shí)出現(xiàn)錯(cuò)碼的情況）；適合檢測(cè)突發(fā)長(zhǎng)度 （m+1)的所有突發(fā)差錯(cuò)；且能夠糾正部分錯(cuò)碼，例如，當(dāng)碼組中僅在某一行中有奇數(shù)個(gè)錯(cuò)碼時(shí)就能夠確定錯(cuò)碼的位置，從而糾正錯(cuò)碼。 方陣碼容易實(shí)現(xiàn)，檢錯(cuò)性能優(yōu)良，故被廣泛應(yīng)用。 編碼效率為：(1)(1)m nRmn-=+大連海事大學(xué)信息

21、科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院3030303010.2.3 恒比碼恒比碼 碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱(chēng)為恒比碼。 由于恒比碼中，每個(gè)碼組均含有相同數(shù)目的 1 和 0，因此恒比碼又稱(chēng)等重碼，定 1 碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中 1 的數(shù)目是否正確，就知道有無(wú)錯(cuò)誤。 目前我國(guó)電傳通信中普遍采用 3 2 碼，又稱(chēng)“5 中取 3”的恒比碼，即每個(gè)碼組的長(zhǎng)度為 5，其中 3 個(gè)“1”。這時(shí)可能編成的不同碼組數(shù)目等于從 5 中取 3 的組合數(shù) 10，這 10 個(gè)許用碼組恰好可表示 10 個(gè)阿拉伯?dāng)?shù)字，如表 9 - 1 所示。而每個(gè)漢字又是以四位十進(jìn)制數(shù)來(lái)代表的。實(shí)踐證明，

22、采用這種碼后，我國(guó)漢字電報(bào)的差錯(cuò)率大為降低。 大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院31313131表表 10-1 3 2 恒比碼恒比碼 每個(gè)碼組的長(zhǎng)度為 5，其中 3 個(gè)“1”大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院3232323210.2.4 正反碼 正反碼是一種簡(jiǎn)單的能夠糾正錯(cuò)碼的編碼。其監(jiān)督位數(shù)目與信息位數(shù)目相同。 （1）當(dāng)信息位中有奇數(shù)個(gè)“1”時(shí)，監(jiān)督碼元與信息碼元相同（是信息碼元的重復(fù)） （2）當(dāng)信息位中有偶數(shù)個(gè)“1”時(shí)，監(jiān)督碼元與信息碼元相反（是信息碼的反碼）。 編碼效率：R1/2大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院33333

23、33310.3 線線 性性 分分 組組 碼碼 1. 基本概念：基本概念： 代數(shù)碼代數(shù)碼 ：利用代數(shù)關(guān)系式產(chǎn)生監(jiān)督位的編碼。 線性分組碼線性分組碼：代數(shù)碼的一種，其監(jiān)督位和信息位的關(guān)系由線性代數(shù)方程決定。 漢明碼漢明碼：一種能夠糾正一個(gè)錯(cuò)碼的線性分組碼。：一種能夠糾正一個(gè)錯(cuò)碼的線性分組碼。 校正子校正子： 在偶數(shù)監(jiān)督碼中，計(jì)算 實(shí)際上就是計(jì)算 ，并檢驗(yàn)S是否等于0。S稱(chēng)為校正子。 監(jiān)督關(guān)系式監(jiān)督關(guān)系式： 稱(chēng)為監(jiān)督關(guān)系式。稱(chēng)為監(jiān)督關(guān)系式。0021aaann021aaaSnn021aaaSnn大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院343434342. 糾錯(cuò)基本原理糾錯(cuò)基本原理 中，

24、S只有兩種取值，只能表示有錯(cuò)和無(wú)錯(cuò)，而不能進(jìn)一步指明錯(cuò)碼的位置。 若此碼組長(zhǎng)度增加一位，則能增加一個(gè)監(jiān)督關(guān)系式。這樣，就能得到兩個(gè)校正子。 兩個(gè)校正子的可能取值有4種組合，即00，01，10，11，能表示4種不同的信息。 若用其中一種組合表示無(wú)錯(cuò)碼，則其他3種組合可以用于指明一位錯(cuò)碼的3種不同位置，從而可以有糾錯(cuò)能力。021aaaSnn大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院35353535 一般而言，若有一般而言，若有 r r 個(gè)監(jiān)督關(guān)系式，則個(gè)監(jiān)督關(guān)系式，則 r r 個(gè)校正個(gè)校正子可以指明一個(gè)錯(cuò)碼的子可以指明一個(gè)錯(cuò)碼的 (2(2r r 1) 1) 個(gè)不同位置個(gè)不同位置。 當(dāng)

25、校正子可以指明的錯(cuò)碼位置數(shù)目等于或大于碼組長(zhǎng)度n時(shí)，才能夠糾正碼組中任何一個(gè)位置上的錯(cuò)碼，即要求2121rrnkr 或大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院36363636漢明碼：一種能夠糾正一個(gè)錯(cuò)碼的線性分組碼。一種能夠糾正一個(gè)錯(cuò)碼的線性分組碼。例：要求設(shè)計(jì)一個(gè)能夠糾正1個(gè)錯(cuò)碼的分組碼(n, k)，設(shè)給定的碼組中有4個(gè)信息位，即k = 4。 由 知，這時(shí)要求監(jiān)督位數(shù)r 3。若取r = 3，則n = k + r = 7?，F(xiàn)在用a6 a5 a4 a3 a2 a1 a0表示這7個(gè)碼元，用S1 S2 S3表示校正子，則這3個(gè)校正子恰好能夠指明23 1 = 7個(gè)錯(cuò)碼的位置。若規(guī)定校正

26、子和錯(cuò)碼位置的關(guān)系如下表：注：也可規(guī)定另外的關(guān)系表。2121rrnkr 或大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院37373737S1 S2 S3錯(cuò)碼位置錯(cuò)碼位置S1 S2 S3錯(cuò)碼位置錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無(wú)錯(cuò)碼無(wú)錯(cuò)碼24561aaaaS13562aaaaS03463aaaaS則僅當(dāng)一錯(cuò)碼位置在a6 、a5 、a4 或a2時(shí)，校正子S1的值才等于1；否則S1的值為零。這就意味著a6 a5 a4 a2四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：同理有大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院38383838在編碼時(shí)，信息

27、位a6 a5 a4 a3的值決定于輸入信號(hào)，它們是隨機(jī)的。監(jiān)督位a2 a1 a0是根據(jù)信息位的取值，按照監(jiān)督關(guān)系確定的，它們應(yīng)保證上列3式中的校正子等于0，即有給定信息位后，為了計(jì)算監(jiān)督位，上式可以改寫(xiě)為000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院39393939按照上式計(jì)算結(jié)果為信息位信息位a6 a5 a4 a3監(jiān)督位監(jiān)督位a2 a1 a0信息位信息位a6 a5 a4 a3監(jiān)督位監(jiān)督位a2 a1 a00000000100011100010111001100001010110100

28、100011110101100101001101100001010110111010100110011111010001110001111111大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院40404040在接收端解碼時(shí)，對(duì)于每個(gè)接收碼組，先按式計(jì)算出校正子S1，S2和S3，然后按照下表判斷錯(cuò)碼的位置。24561aaaaS13562aaaaS03463aaaaSS1 S2 S3錯(cuò)碼位置錯(cuò)碼位置S1 S2 S3錯(cuò)碼位置錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無(wú)錯(cuò)碼無(wú)錯(cuò)碼大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院41414141

29、例：若接收碼組為0000011，則按上三式計(jì)算得到：S1 = 0，S2 = 1，S3 = 1。這樣，由上表可知，錯(cuò)碼位置在a3。 上例中的漢明碼是(7, 4)碼，其最小碼距d0 = 3。由式 和 可知，此碼能夠檢測(cè)2個(gè)錯(cuò)碼，或糾正1個(gè)錯(cuò)碼。 漢明碼的碼率：當(dāng)r (或n)很大時(shí)，上式趨近于1。所以漢明碼是一種高效編碼。 漢明碼是一種可糾一位錯(cuò)的線性分組碼，漢明碼是一種可糾一位錯(cuò)的線性分組碼，其碼參數(shù)為其碼參數(shù)為：n = 2r-1, k = n - r = 2r - 1 - r, r 3 , d0 = 3。 如：如：（1515，1111）漢明碼中漢明碼中 r = 4。10 ed120 td1212

30、rrrnk大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院42424242分組碼的一般原理線性分組碼是監(jiān)督位和信息位滿足一組線性方程的碼，如前述(7, 4)碼滿足如下關(guān)系： 可以改寫(xiě)為上式中，已經(jīng)將“”簡(jiǎn)寫(xiě)成“+”。本章中除非特別說(shuō)明，都是指模加。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院43434343上式可以寫(xiě)成矩陣形式： （模2） 將上式簡(jiǎn)寫(xiě)為HAT = 0T 或AHT = 000

31、01011001110101011101000123456aaaaaaa大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院44444444式中，稱(chēng)為監(jiān)督矩陣。 H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來(lái)作為判斷接收碼字A是否出錯(cuò)的依據(jù)監(jiān)督矩陣的性質(zhì)監(jiān)督矩陣的性質(zhì)：監(jiān)督矩陣H確定碼組中的信息位和監(jiān)督位的關(guān)系。H 的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，即監(jiān)督位數(shù) r 。H 的每行中“1”的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。101100111010101110100HA = a6 a5 a4 a3 a2 a1 a0 稱(chēng)為碼字 0 = 000大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院4545454

32、5 H 可以分成兩部分：例如 典型監(jiān)督矩陣 式中，P 為r k階矩陣，Ir為 r r 階單位方陣。將具有PIr 形式的H矩陣稱(chēng)為典型陣。H 矩陣的各行應(yīng)該是線性無(wú)關(guān)的矩陣的各行應(yīng)該是線性無(wú)關(guān)的，否則將得不到 r 個(gè)線性無(wú)關(guān)的監(jiān)督關(guān)系式。若一個(gè)矩陣能寫(xiě)成典型陣形式P Ir，則其各行一定是線性無(wú)關(guān)的。rPIH001101101011011001110大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院46464646生成矩陣生成矩陣 可以寫(xiě)為上式兩端分別轉(zhuǎn)置后，可以變成式中，Q為k r 階矩陣，是P的轉(zhuǎn)置，即Q = PT。3456012101111011110aaaaaaa3460356145

33、62aaaaaaaaaaaaQ34563456012011101110111aaaaaaaaaaa大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院47474747將Q的左邊加上一個(gè)k階單位方陣，稱(chēng)為生成矩陣，即 生成矩陣 G稱(chēng)為生成矩陣，因?yàn)榭梢杂盟a(chǎn)生整個(gè)碼組A，即有0110001101001011001001111000QGkI IG34560123456aaaaaaaaaaaA大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院48484848生成矩陣的性質(zhì)： 具有IkQ形式的生成矩陣稱(chēng)為典型生成矩陣典型生成矩陣。 由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于

34、其后。這種形式的碼組稱(chēng)為系統(tǒng)碼系統(tǒng)碼。 生成矩陣G的各行也必須是線性無(wú)關(guān)的。原因 如果已有k個(gè)線性無(wú)關(guān)的碼組，則可以將其用來(lái)作為生成矩陣G，并由它生成其余碼組。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院49494949 任一碼組A都是G的各行的線性組合； 共有行，若它們線性無(wú)關(guān)，則可組合出k種不同的碼組A，它恰好是k位信息位的全部碼組； 若G的各行有線性相關(guān)的，則不可能由G生出k種不同碼組。 實(shí)際上，G的各行本身就是一個(gè)碼組。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院50505050錯(cuò)誤圖樣錯(cuò)誤圖樣設(shè)：發(fā)送碼組A是一個(gè)n列的行矩陣： 接收碼組是一個(gè)n列的行矩陣B：

35、令接收碼組和發(fā)送碼組之差為 E就是錯(cuò)碼的行矩陣： ，稱(chēng)為錯(cuò)誤圖樣。0121aaaaAnn0121bbbbBnnB A = E (模2)0121eeeeEnn大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院51515151式中， (i = 0, 1, , n-1)若ei = 0，表示該碼元未錯(cuò)；若ei = 1，表示該碼元為錯(cuò)碼。 B A = E 可以改寫(xiě)成 B = A + E上式表示發(fā)送碼組A與錯(cuò)碼矩陣E之和等于接收碼組B。 例如， 若發(fā)送碼組A = 1 0 0 0 1 1 1， 錯(cuò)碼矩陣E = 0 0 0 0 1 0 0， 則 接收碼組B = 1 0 0 0 0 1 1。iiiiiab

36、abe當(dāng)當(dāng), 1, 0校正子矩陣校正子矩陣：大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院52525252在接收端解碼時(shí)，將接收碼組B代入式AHT = 0中A的位置進(jìn)行計(jì)算。（1）若接收碼組中無(wú)錯(cuò)碼，則B = A。代入后，該式仍成立，即有BH T = 0（2）當(dāng)接收碼組有錯(cuò)時(shí)，E0，將B帶入AHT = 0 中，該式不一定成立。 (a)只有當(dāng)錯(cuò)碼較多，已經(jīng)超出這種編碼的檢測(cè)能力時(shí)，B變?yōu)榱硪辉S用碼組，上式才成立。 (b)當(dāng)錯(cuò)碼未超過(guò)檢錯(cuò)能力時(shí)，上式不成立，即其右端不為0。假設(shè)此時(shí)該式的右端等于S，即有大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院53535353 BH T =

37、 S將B = A + E 代入上式，得到: S = (A + E) H T = AH T + EH T 上式右端第一項(xiàng)等于0，所以 S = EH T將S稱(chēng)為校正子校正子。 當(dāng)H 確定后，上式中S只與E 有關(guān)，而與A 無(wú)關(guān)。這意味著，S 和錯(cuò)碼和錯(cuò)碼E 之間有確定的線性變換關(guān)系之間有確定的線性變換關(guān)系。 若S 和E 有一一對(duì)應(yīng)關(guān)系，則S 將能代表錯(cuò)碼位置。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院54545454線性碼的封閉性：線性碼的封閉性： 若若A1和和A2是一種線性碼中的兩個(gè)碼組，則是一種線性碼中的兩個(gè)碼組，則(A1+A2)仍是其仍是其中一個(gè)碼組。中一個(gè)碼組。 證 若A1和A

38、2是兩個(gè)碼組，則有：A1HT = 0, A2HT = 0 將上兩式相加，得出 A1HT + A2HT = (A1 + A2 ) HT = 0 所以，(A1 + A2)也是一個(gè)碼組。 由于線性碼具有封閉性，所以兩個(gè)碼組兩個(gè)碼組(A1和和A2)之間的距之間的距離（即對(duì)應(yīng)位不同的數(shù)目）必定是另一個(gè)碼組離（即對(duì)應(yīng)位不同的數(shù)目）必定是另一個(gè)碼組(A1 + A2)的重量的重量（即（即“1”的數(shù)目）的數(shù)目）。因此，碼的最小距離就是碼的最小重量碼的最小距離就是碼的最小重量（除全（除全“0”碼組外）碼組外）。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院55555555例：已知（7，3）分組碼的監(jiān)督關(guān)

39、系為632152106515400000aaaaaaaaaaaaaa求其監(jiān)督矩陣、生成矩陣、全部碼字及糾錯(cuò)能力。求其監(jiān)督矩陣、生成矩陣、全部碼字及糾錯(cuò)能力。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院56565656解：解：將非典型H陣化為典型H陣：22341123HAT = 0T大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院5757575701大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院5858585810.4 循環(huán)碼10.4.1 循環(huán)碼的概念： 循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個(gè)碼組。 例：一種(7, 3)循環(huán)碼的全部碼組如下碼組碼組編號(hào)編號(hào)

40、信息位信息位監(jiān)督位監(jiān)督位碼組碼組編號(hào)編號(hào)信息位信息位監(jiān)督位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院59595959一般情況 若(an-1 an-2 a0)是循環(huán)碼的一個(gè)碼組，則循環(huán)移位后的碼組： (an-2 an-3 a0 an-1) (an-3 an-4 an-1 an-2) (a0 an-1 a2 a1) 仍然是該編

41、碼中的碼組。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院60606060多項(xiàng)式表示法: 一個(gè)長(zhǎng)度為n的碼組(an-1 an-2 a0)可以表示成 上式中x 的值沒(méi)有任何意義，僅用它的冪代表碼元的位置。 例如：碼組1 1 0 0 1 0 1可以表示為 012211)(axaxaxaxTnnnn11010011)(25623456xxxxxxxxxxT大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院6161616110.4.2 循環(huán)碼的運(yùn)算(1) 整數(shù)的按模運(yùn)算在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中，有1 + 1 = 2 0 (模2)，1 + 2 = 3 1 (模2)，2

42、 3 = 6 0 (模2)等等。 一般說(shuō)來(lái)，若一個(gè)整數(shù)m可以表示為式中，Q為整數(shù)，則在模n運(yùn)算下，有m p (模n) 在模在模n n運(yùn)算下，一個(gè)整數(shù)運(yùn)算下，一個(gè)整數(shù)m m等于它被等于它被n n除所得的余數(shù)除所得的余數(shù)。npnpQnm,大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院62626262（2）碼多項(xiàng)式的按模運(yùn)算 若任意一個(gè)多項(xiàng)式F(x)被一個(gè)n次多項(xiàng)式N(x)除，得到商式Q(x)和一個(gè)次數(shù)小于n的余式R(x)，即則在按模N(x)運(yùn)算下，有 這時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算。 例1：x3被(x3 + 1)除，得到余項(xiàng)即 )()()()(xRxQxNxF）（模)()()(xNxRx

43、F）（模) 1(133xx大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院63636363 例2：因?yàn)閤x3 + 1 x4 +x2 + 1x4 +x x2 +x +1 在模2運(yùn)算中加法和減法一樣。）（模) 1(113224xxxxx大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院64646464（3）循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，設(shè)T(x)是一個(gè)長(zhǎng)度為n的碼組，若則T (x)也是該編碼中的一個(gè)碼組。 證 設(shè)一循環(huán)碼為則有 上式中的T (x) 正是碼組T (x)向左循環(huán)移位 i 次的結(jié)果。）（模) 1()()(nixxTxTx012211)(axaxaxaxTnnnn)()(1

44、102211011112211xTaxaxaxaxaxaxaxaxaxaxTxininininniniinininninni大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院65656565例： 一循環(huán)碼為1100101，即 若給定 i = 3，則有 上式對(duì)應(yīng)的碼組為0101110，它正是T(x)向左移3位的結(jié)果。結(jié)論：一個(gè)長(zhǎng)為n的循環(huán)碼必定為按模(xn + 1)運(yùn)算的一個(gè)余式。 ）（模) 1()(723535893xxxxxxxxxxTx1)(256xxxxT大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院66666666（4）循環(huán)碼的生成 有了生成矩陣G，就可以由k個(gè)信息位得

45、出整個(gè)碼組：例：式中，生成矩陣G的每一行都是一個(gè)碼組。若能找到 k 個(gè)已知的碼組，就能構(gòu)成矩陣G。如前所述，這k個(gè)已知碼組必須是線性不相關(guān)的。在循環(huán)碼中，一個(gè)(n, k)碼有2k個(gè)不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是碼組，而且這k個(gè)碼組是線性無(wú)關(guān)的。因此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣G。G34560123456aaaaaaaaaaaA0110001101001011001001111000QGkI I大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院67676767 在循環(huán)碼中除全“0”碼組外

46、，再?zèng)]有連續(xù)k位均為“0”的碼組 ，即連0的長(zhǎng)度最多只能有k-1位。否則，在經(jīng)過(guò)若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個(gè)碼組。這在線性碼中顯然是不可能的。 g(x)必須是一個(gè)常數(shù)項(xiàng)不為“0”的(n - k)次多項(xiàng)式，而且這個(gè)g(x)還是這種(n, k)碼中次數(shù)為(n k)的唯一一個(gè)多項(xiàng)式。（常數(shù)項(xiàng)為0，右循環(huán)一次將導(dǎo)致k個(gè)連0）因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次數(shù)將小于(n k)，即連續(xù)“0”的個(gè)數(shù)多于(k 1)。顯然，這是與前面的結(jié)論矛盾的。 稱(chēng)這唯一的(n k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式碼的生成多項(xiàng)式。一旦確

47、定了g(x)，則整個(gè)(n, k)循環(huán)碼就被確定了。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院68686868 循環(huán)碼的生成矩陣G可以寫(xiě)成 例：)()()()()(21xgxxgxgxxgxxkkG碼組碼組編號(hào)編號(hào)信息位信息位監(jiān)督位監(jiān)督位碼組碼組編號(hào)編號(hào)信息位信息位監(jiān)督位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院69696969 上表中的編碼為(7, 3)循環(huán)碼，n = 7, k

48、= 3, n k = 4，其中唯一的一個(gè)(n k) = 4次碼多項(xiàng)式代表的碼組是第二碼組0010111，與它對(duì)應(yīng)的碼多項(xiàng)式，即生成多項(xiàng)式，為g(x) = x4 + x2 + x + 1。將此g(x)代入上矩陣，得到)()()()(2xgxxgxgxxG101110001011100010111G或大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院70707070上式不符合G = IkQ形式，所以它不是典型生成矩陣。但它經(jīng)過(guò)線性變換后，不難化成典型陣。 此循環(huán)碼組的多項(xiàng)式表示式T(x)：上式表明：所有碼多項(xiàng)式T(x)都能夠被g(x)整除，而且任意一個(gè)次數(shù)不大于(k 1)的多項(xiàng)式乘g(x)都

49、是碼多項(xiàng)式。 )()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院71717171（5）尋求碼生成多項(xiàng)式 因?yàn)槿我庖粋€(gè)循環(huán)碼T(x)都是g(x)的倍式，故它可以寫(xiě)成T(x) = h(x)g(x) 而生成多項(xiàng)式g(x)本身也是一個(gè)碼組，即有 T (x) = g(x) 由于碼組T (x)是一個(gè)(n k)次多項(xiàng)式，故xk T (x)是一個(gè)n次多項(xiàng)式。由可知，xk T (x)在模(xn + 1)運(yùn)算下也是一個(gè)碼組，所以有）（模) 1()()(nixxTxTx

50、1)()(1)(nnkxxTxQxxTx大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院72727272上式左端分子和分母都是n次多項(xiàng)式，故相除的商式Q(x) = 1。因此，上式可以寫(xiě)成將 T(x) = h(x)g(x) 和 T (x) = g(x) 代入化簡(jiǎn)后，得到上式表明：生成多項(xiàng)式g(x)應(yīng)該是(xn + 1)的一個(gè)因子。)() 1()(xTxxTxnk)() 1()(xTxxTxnk)()(1xhxxgxkn大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院73737373例：(x7 + 1)可以分解為為了求出(7, 3)循環(huán)碼的生成多項(xiàng)式 g(x)，需要從上式中找到一個(gè)

51、(n k) = 4次的因子。這樣的因子有兩個(gè)，即以上兩式都可以作為生成多項(xiàng)式。 選用的生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼碼組也不同。 ) 1)(1)(1(13237xxxxxx1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx二者互逆大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院7474747410.4.3 循環(huán)碼的編碼方法（1） 根據(jù)給定的(n, k)值選定生成多項(xiàng)式g(x)，即從(xn+1)的因式中選一(n-k)次多項(xiàng)式作為g(x)。（2）設(shè)待編碼的k位信息多項(xiàng)式為m(x)，用xn-k 乘m(x)：這一運(yùn)算實(shí)際上是在信息碼后附加上(n k)個(gè)“0”。 例如，信息

52、碼為110，它寫(xiě)成多項(xiàng)式為m(x) = x2 + x。當(dāng)n k = 7 3 =4時(shí)，xn-k m(x) = x4 (x2 +x) = x6 +x5，它表示碼組1100000。 （3）用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即有 )()()()()(xgxrxQxgxmxkn大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院7575例：若選定g(x) = x4 + x2 + x + 1，則有 （多項(xiàng)式長(zhǎng)除）上式是用碼多項(xiàng)式表示的運(yùn)算。它和下式（長(zhǎng)除）等效： （4）由（3）的結(jié)果經(jīng)整理得： Q(x) g(x) = xn-k m(x) + r(x) T(x)（令）可見(jiàn)：T

53、(x)可被g(x)整除且其次數(shù)不大于（n1）次，則T(X)必為一許用碼組多項(xiàng)式，編出的系統(tǒng)碼碼組T(x)為： T(x) = xn-k m(x) +r(x) 在上例中，T(x) = 1100000 + 101 = 110 0101 11) 1(1)()(24222456xxxxxxxxxxxxgxmxkn10111101111101111100000注：g(x): n-k次m(x): k-1次Q(x): k-1次r(x): n-k次 信元 監(jiān)元大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院7676（5）上述4個(gè)編碼步驟的實(shí)現(xiàn)1.軟件法：a.長(zhǎng)除法b.查表法（預(yù)先算出各種信元狀態(tài)所對(duì)應(yīng)的

54、r(x)， 列表成庫(kù)備查）2.硬件法： 用除法電路實(shí)現(xiàn)，除法電路主要由一些移存器、模2加法器和控制開(kāi)關(guān)構(gòu)成。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院7777移位寄存器的個(gè)數(shù)為g(x)最高項(xiàng)的次數(shù)，即r個(gè)移位寄存器為P0, P1, , Pr-1。反饋線gi的連接與g(x)的非零系數(shù)相對(duì)應(yīng)，且g0= gr = 1, 得出的是系統(tǒng)碼。除法電路的一般結(jié)構(gòu)如下圖所示：ba大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院7878(7, 3)循環(huán)碼系統(tǒng)碼編碼電路， 取g(x) = x4 + x2 + x + 1例如：上述(7, 3)碼的編碼器包含四級(jí)移存器，分別用a, b, c, d

55、表示，一個(gè)雙刀雙擲開(kāi)關(guān)S。當(dāng)信息位輸入時(shí)，開(kāi)關(guān)向下，輸入信碼一方面送入除法器進(jìn)行運(yùn)算，另一方面直接輸出。輸入k位信息全部進(jìn)入除法器后，開(kāi)關(guān)轉(zhuǎn)向上，此時(shí)輸出端接到移存器，將移存器中存貯的除法余項(xiàng)依次取出，同時(shí)切斷反饋線，并從左到右逐次清零。fmg0gr大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院79797979工作時(shí)，首先所有移存器清零。大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院80808080 10.4.4 循環(huán)碼的解碼方法（1）在檢錯(cuò)時(shí)：當(dāng)接收碼組沒(méi)有錯(cuò)碼時(shí)，接收碼組R(x)必定能被g(x)整除，即下式中余項(xiàng)r(x)應(yīng)為零；否則，有誤碼。當(dāng)接收碼組中的錯(cuò)碼數(shù)量過(guò)多，

56、超出了編碼的檢錯(cuò)能力時(shí)，有錯(cuò)碼的接收碼組也可能被g(x)整除。這時(shí)，錯(cuò)碼就不能檢出。 （2）在糾錯(cuò)時(shí)：用生成多項(xiàng)式g(x)除接收碼組R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或計(jì)算方法得出錯(cuò)誤圖樣E(x)。注：r(x)與E(x)必須有一一對(duì)應(yīng)關(guān)系才可糾錯(cuò)。從R(x)中減去E(x)，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組T(x)。)(/)()()(/)(xgxrxQxgxR大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院8181818110.4.5 截短循環(huán)碼 截短目的： 在設(shè)計(jì)時(shí)，通常信息位數(shù)k、碼長(zhǎng)n和糾錯(cuò)能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。故采

57、用截短碼長(zhǎng)，得出滿足要求的編碼。 截短方法： 設(shè)給定一個(gè)(n, k)循環(huán)碼，它共有2k種碼組，現(xiàn)使其前i (0 i N時(shí)碼樹(shù)中節(jié)點(diǎn)自上而下重復(fù)取4種狀態(tài)。在網(wǎng)格圖中，將碼樹(shù)中具有相同狀態(tài)的節(jié)點(diǎn)合并在一起，碼樹(shù)中的上支路用實(shí)線表示，下支路用虛線表示，支路上標(biāo)注的碼元為輸出比特。自上而下的四行節(jié)點(diǎn)分別表示a, b, c, d四種狀態(tài)。下圖畫(huà)出了5個(gè)時(shí)隙?？梢钥闯觯涸诘?時(shí)隙以后的網(wǎng)格圖形完全是重復(fù)第3時(shí)隙的圖形。這也反映了此(3, 1, 3)卷積碼的約束長(zhǎng)度為3。 110110110110011011011010010010101101101001001001001abcdabcd00000000

58、0000000111111111111111100100100大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院97979797abcdabcd110010001111100對(duì)于一般的(n, k, N)卷積碼，可以由此推廣出來(lái)以下結(jié)論： (1) 對(duì)應(yīng)于每組k個(gè)輸入比特，編碼后產(chǎn)生n個(gè)輸出比特。 (2) 樹(shù)狀圖中每個(gè)節(jié)點(diǎn)引出2k條支路。 (3) 網(wǎng)格圖和狀態(tài)圖都有2k(N-1)種可能的狀態(tài)。每個(gè)狀態(tài)引出2k條支路，同時(shí)也有2k條支路從其他狀態(tài)或本狀態(tài)引入。網(wǎng)格圖中的編碼路徑舉例：設(shè)起始狀態(tài)為a，輸入信息位為11010時(shí)，則輸出編碼序列是：111 110 010 100 001大連海事大學(xué)信

59、息科學(xué)技術(shù)學(xué)院大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院98989898(4) 維特比算法卷積碼的譯碼有大數(shù)邏輯譯碼（門(mén)限譯碼）和概率譯碼。維特比譯碼屬于概率譯碼。 基本原理：將接收到的序列和所有可能的發(fā)送序列作比較，選擇其中漢明距離最小的序列當(dāng)作是現(xiàn)在的發(fā)送序列。 例：設(shè)卷積碼為(n, k, N) = (3, 1, 3)碼 現(xiàn)在的發(fā)送信息位為1101為了使移存器中的信息位全部移出，在信息位后面加入了3個(gè)“0”，即1101000編碼后的發(fā)送序列：111 110 010 100 001 011 000接收序列：111 010 010 110 001 011 000 (紅色為錯(cuò)紅色為錯(cuò)碼碼) 由于這是一個(gè) (3, 1, 3)卷積碼，發(fā)送序列的約束長(zhǎng)度為N = 3，所以首先需