《通信系統(tǒng)原理》課件第10章

10.1概述

10.2檢錯碼

10.3線性分組碼

10.4卷積碼

10.5復(fù)合編碼

10.6m序列

思考題

習(xí)題第10章信道編碼原理10.1概述10.1.1信源編碼與信道編碼數(shù)字通信中，根據(jù)不同的目的，可將編碼分為信源編碼和信道編碼兩大類。為了提高數(shù)字信號的有效性而采取的編碼稱為信源編碼，又稱有效編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼(或者可靠編碼)，又稱抗干擾編碼，這是本章要討論的內(nèi)容。數(shù)字通信要求傳輸過程中所造成的碼元差錯足夠低。引起傳輸差錯的根本原因是信道內(nèi)存在噪聲以及信道傳輸特性不理想所造成的碼間串?dāng)_。通常，由于信道線性畸變所造成的碼間串?dāng)_可以通過均衡的辦法來消除,因此，常常只把信道中的噪聲作為造成傳輸差錯的根本原因。為了提高數(shù)字通信系統(tǒng)的抗噪聲性能，可以采取增大發(fā)射功率、降低接收設(shè)備本身的噪聲、選擇好的調(diào)制制度和解調(diào)方式、加強(qiáng)天線的方向性等措施。但是,這些措施只能將差錯減小到一定程度,要進(jìn)一步提高通信的可靠性，就需要采用信道編碼技術(shù)，對可能或者已經(jīng)出現(xiàn)的差錯進(jìn)行控制。

信道編碼是使不帶規(guī)律性或者規(guī)律性不強(qiáng)的原始數(shù)字信號變換為帶上規(guī)律性或者加強(qiáng)了規(guī)律性的數(shù)字信號，信道譯碼器則利用這些規(guī)律性來鑒別是否發(fā)生了錯誤，進(jìn)而糾正錯誤。信道編碼分為糾錯編碼和正交編碼兩大類。糾錯碼的規(guī)律性體現(xiàn)在各碼組的碼元之間，而正交碼的規(guī)律性體現(xiàn)在各碼組之間的正交性。這兩類碼有密切的聯(lián)系，有些正交碼就是糾錯碼。

原始數(shù)字信號是分組傳輸?shù)?，例如每k個二進(jìn)制碼元為一組，稱為信息組，經(jīng)信道編碼后轉(zhuǎn)換為每n個碼元一組的碼字(碼組)，n>k。可見，信道編碼是采用增加數(shù)碼，利用“多余”碼來提高抗干擾能力的，亦即以降低信息傳輸速率為代價來減少錯誤，或者說是通過采用削弱有效性來增強(qiáng)可靠性。10.1.2糾錯碼的分類

(1)根據(jù)糾錯碼各碼組的碼元與信息元之間的函數(shù)關(guān)系，糾錯碼可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，則稱為線性碼，否則稱為非線性碼。

(2)根據(jù)上述關(guān)系涉及的范圍，糾錯碼可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)，卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)，卷積碼又稱連環(huán)碼。線性分組碼中，把具有循環(huán)移位特性的碼稱為循環(huán)碼，否則稱非循環(huán)碼。

(3)根據(jù)糾錯碼組中信息元是否隱蔽，糾錯碼可分為系統(tǒng)碼和非系統(tǒng)碼。如果信息元能從碼組中截然分離出來(通常K個信息元與原始數(shù)字信號一致，且位于碼組的前K位)，則稱為系統(tǒng)碼或組織碼，否則稱為非系統(tǒng)碼或非組織碼。

(4)根據(jù)碼的用途,糾錯碼可分為檢錯碼和糾錯碼。前者以檢測(發(fā)現(xiàn))錯誤為目的，后者以糾正錯誤為目的。糾錯碼一定能檢錯，檢錯碼不一定能糾錯。平常所說的糾錯碼是兩者的統(tǒng)稱。

(5)根據(jù)糾(檢)錯碼的類型區(qū)分，糾錯碼可分為糾(檢)隨機(jī)錯碼、糾(檢)突發(fā)錯碼及既能糾(檢)隨機(jī)錯又能糾(檢)突發(fā)錯的碼。

(6)根據(jù)碼元取值的進(jìn)制，糾錯碼可分為二進(jìn)制碼和多進(jìn)制碼。本章主要介紹二進(jìn)制糾錯碼。10.1.3差錯控制的工作方式差錯控制的基本工作方式有4種，如圖10.1所示。圖中有斜線的方框圖表示在該端檢出錯誤。圖10.1差錯控制的基本工作方式前向糾錯(FEC，F(xiàn)orwardErrorCorrection)：又稱自動糾錯，發(fā)端發(fā)送糾錯碼，收端譯碼器自動發(fā)現(xiàn)并糾正錯誤。其特點是能單向連續(xù)傳輸，實時性好，但是譯碼電路比較復(fù)雜。檢錯重發(fā)(ARQ,AutoRepeat-reQuest):又稱反饋重發(fā)、自動重傳請求或者判決反饋，發(fā)端發(fā)出檢錯碼，通過正向信道送到收端，收端譯碼器判決碼組中有無錯誤出現(xiàn)，再把判決信號通過反饋信道送回發(fā)端，發(fā)端根據(jù)判決信號將收端認(rèn)為有錯的消息重發(fā)到收端，直到正確接收為止。其特點是需要反饋信道，但是譯碼設(shè)備簡單，對突發(fā)錯誤特別有效。信息反饋(IF，InformationFeedback)：又稱反饋檢驗，收端把收到的消息原封不動地通過反饋信道送回發(fā)端，發(fā)端把反饋回來的信息與原發(fā)送信息進(jìn)行比較，從而發(fā)現(xiàn)錯誤，并把二者不一致的部分重發(fā)到收端。其特點是沒有糾(檢)錯編碼，電路較簡單，但是需要反饋信道并且傳輸速率較低。

混合糾錯(HEC，HybridErrorCorrection)：是FEC與ARQ的混合，發(fā)端發(fā)出便于檢錯和糾錯的碼，通過正向信道送到收端，收端對錯誤能糾正的就自動糾正，糾正不了時自動發(fā)出判決信號并送回發(fā)端，發(fā)端把收端認(rèn)為有錯并且無法糾正的消息重發(fā)到收端，以達(dá)到正確傳輸。這種方式具有FEC與ARQ的特點，能充分發(fā)揮碼的糾錯和檢錯性能，在較差的信道中仍然可以收到好的效果，缺點是需要反饋信道以及復(fù)雜的譯碼設(shè)備。

以上4種工作方式在數(shù)字通信系統(tǒng)中都得到了廣泛的應(yīng)用。例如,在高速防空系統(tǒng)中常采用前向糾錯方式，在國際間的數(shù)字通信系統(tǒng)中往往采用檢錯重發(fā)的方式或者信息反饋的方式，而在復(fù)雜的短波信道與散射信道中則常采用混合糾錯的方式。10.1.4糾錯碼的基本概念

1．碼長、碼重和碼距碼組(碼字或碼矢)中碼元的數(shù)目稱為碼組的長度，簡稱碼長。碼組中非0位的數(shù)目稱為碼組的重量，簡稱碼重。對于二進(jìn)制碼而言，碼重W就是碼組中1的數(shù)目，例如碼組11010，碼長n=5，碼重W=3。兩個等長碼組之間對應(yīng)位不同的數(shù)目稱為這兩個碼組的漢明距離，簡稱碼距,例如碼組11000與10011的距離d=3。而碼組集合中全體碼組之間距離的最小數(shù)值d0稱為碼的最小距離。由于兩個碼組模二相加，其不同的對應(yīng)位必為1，而相同的對應(yīng)位必為0，因此兩個碼組模二相加得到的新碼組的重量就是這兩個碼組之間的距離。碼的最小距離是衡量該碼糾錯能力的依據(jù)，是重要的參數(shù)。

2．為什么糾錯碼能夠檢錯或者糾錯現(xiàn)在以二進(jìn)制碼組為例說明糾錯碼檢錯和糾錯的基本原理。分組碼對數(shù)字序列是分段處理的，設(shè)每一段由k個碼元組成，稱做長度為k的信息組，又稱k重。由于每個碼元有0或1兩個值，因此共有2k個不同的k重。每段長k的信息組，以一定的規(guī)則增加r個稱為監(jiān)督元的多余度碼元，來監(jiān)督這k個信息元，這樣就組成長為n=k+r的碼組，又稱n重，共得到2k個不同的n重。這2k個n重分別代表2k個不同的信息組，稱為許用碼組。長n的數(shù)字序列共有2n種可能的組合，其中2n-2k個n重未被選用，稱為禁用碼組。上述2k

個不同的長n的許用碼組的集合稱為分組碼。分組碼能夠檢錯或者糾錯的原因是每個n重中有多余度碼元，或者說2n個n重中有禁用碼組。舉例說明如下：

設(shè)發(fā)送端發(fā)送A和B兩個消息，分別用一位碼元(k=1)表示，1代表A，0代表B。如果這兩個信息組在傳輸中產(chǎn)生了錯誤，0錯成了1或者1錯成了0，則接收端不能發(fā)現(xiàn)這種錯誤，更談不上糾正錯誤,此時收到的消息就不可靠。如果每個一位長的信息組中添加上一個監(jiān)督元(r=1)，其規(guī)則是與信息元重復(fù)，則這樣編出的兩個長為n=2的碼組是11(代表A)和00(代表B)。11、00是許用碼組，這兩個碼字組成一個(2，1)分組碼，其特點是各碼字的碼元是重復(fù)的，因此又稱為重復(fù)碼。01、10是禁用碼組。設(shè)發(fā)送11經(jīng)信道傳輸錯了一位，變成01或10，收端譯碼器根據(jù)重復(fù)碼的規(guī)則，能發(fā)現(xiàn)有一位錯誤，但是不能指明錯在哪一位，亦即不能作出發(fā)送的消息是A(“11”)還是B(“00”)的判決。如果信道干擾嚴(yán)重，使發(fā)送碼字的兩位都產(chǎn)生錯誤，從而使11錯成了00，則收端譯碼器根據(jù)重復(fù)碼的規(guī)則檢驗，不認(rèn)為有錯，并且判決為消息B，造成了錯判。這種碼距為2的(2，1)重復(fù)碼能發(fā)現(xiàn)1個碼元的錯誤，不能發(fā)現(xiàn)2個碼元的錯誤(以下簡稱1個錯誤、2個錯誤、……)，也不能糾正錯誤。如果仍然按照重復(fù)碼的規(guī)則，再加一個監(jiān)督元，則得到(3，1)重復(fù)碼，它的兩個碼字為111和000，碼距為3；其余6個碼組(001，010，100，110，101，011)為禁用碼組。設(shè)發(fā)送111(代表消息A)，譯碼器收到的3重為110，根據(jù)重復(fù)碼的規(guī)則，發(fā)現(xiàn)有錯，并且當(dāng)采用最大似然法譯碼時，把與發(fā)送碼字最相似的碼組認(rèn)為是發(fā)送碼組。110與111只有一位不同，而與000有兩位不同，因此判決為111。事實上，一般情況下錯1位的可能性比錯2位的可能性大得多，從統(tǒng)計的觀點看，這樣判決是正確的。因此，這種(3，1)碼能糾正一個錯誤，但不能糾正兩個錯誤，因為如果發(fā)送111，收到100，根據(jù)譯碼規(guī)則將譯為000，這就判錯了。類似于前面的分析，如果用這種碼來檢錯，則可以發(fā)現(xiàn)兩個錯誤，但是不能發(fā)現(xiàn)3個錯誤。如果按照重復(fù)碼的規(guī)則編成(4，1)碼，則長度為4的碼組共有16個，其中1111和0000為許用碼組，分別代表消息A和B，其余14個碼組為禁用碼組。類似的方法可以證明，這種碼距為4的(4，1)碼能夠糾正一個錯誤，同時發(fā)現(xiàn)兩個錯誤，如果僅作檢錯用，則可以發(fā)現(xiàn)3個錯誤。上述例子表明，糾錯碼的抗干擾能力完全取決于許用碼組之間的距離。碼的最小距離d0越大，說明碼字間的最小差別越大，抗干擾能力就越強(qiáng)，即受較強(qiáng)的干擾時仍然可以不造成許用碼組之間的混淆。糾錯碼的糾錯效果與信道誤碼率有密切的關(guān)系：信道誤碼率越低，糾錯效果越顯著，反之不顯著，信道誤碼率很大時甚至?xí)霈F(xiàn)“越糾越錯”的現(xiàn)象。

香農(nóng)編碼定理告訴我們，只要信息傳輸速率不大于信道容量，在理論上存在一種方法，使得通過信道傳輸?shù)臄?shù)碼的差錯概率為任意小。香農(nóng)編碼定理沒有給出具體的編碼方法，但是它指明了研究的方向。

3．分組碼的糾(檢)錯能力與最小碼距的關(guān)系任一(n，k)分組碼，如果要在碼字內(nèi)：

(1)檢測e個隨機(jī)錯誤，則要求碼的最小距離d0≥e+1

(10.1)

(2)糾正t個隨機(jī)錯誤，則要求碼的最小距離

d0≥2t+1

(10.2)

(3)糾正t個同時檢測e(>t)個隨機(jī)錯誤，則要求碼的最小距離

d0≥t+e+1

(10.3)

下面利用幾何圖形進(jìn)行簡要證明。設(shè)A1、A2是分組碼中相距d0的兩個碼字，分別位于A1及A2兩點。由圖10.2(a)可見，如果A1發(fā)生e個錯誤，則位置將移動e，至以A1為圓心、e為半徑的圓上某點，考慮造成使A1、A2兩碼組最難分辨的情況是移至

點。如果譯碼器不將錯判成A2，則必須使

與A2之間的距離d(，A2)≥1，因此檢測e個錯誤的條件是d0≥e+1。圖10.2糾(檢)錯能力的幾何解釋由圖10.2(b)可見，如果A1發(fā)生t個錯誤，則位置移至，d(A1，

)=t。如果譯碼器能把

正確判成A1，則必須要求d(A1，)<d(A2，)，即d(A2，)≥t+1。因此糾正t個錯誤的條件是d0≥2t+1。由圖10.2(c)可見，如果A1發(fā)生t個錯誤的同時A2發(fā)生e(>t)個錯誤，則位置分別移至及

，為了保證糾正t個同時檢測e個錯誤，必須要求d(，)≥1，即d0≥t+e+1。這里說的“同時”是指在譯碼過程中,如果錯誤個數(shù)小于等于t，則能糾正；如果錯誤個數(shù)大于t

且小于等于e(e>t)，則能檢測這些錯誤，但是不能糾正，或者說能檢測t+e個錯誤，其中t個錯誤可以糾正。

4．對糾錯編碼的基本要求以上討論說明，碼的最小距離d0越大，碼的糾(檢)錯的能力越強(qiáng)。但是，隨著多余碼元的增多，信息傳輸速率降低越多。通常用R=k/n來表示碼字中信息元所占的比例，稱為編碼效率，簡稱碼率。它是衡量碼性能的又一個重要參數(shù)。碼率越高，傳信率就越高，但是此時糾錯能力要降低，R=1時就沒有糾錯能力了?？梢姡a率與糾錯能力之間是有矛盾的。對糾錯編碼的基本要求是：糾錯和檢錯能力盡量強(qiáng)；編碼效率盡量高；碼長盡量短；編碼規(guī)律盡量簡單。實際應(yīng)用中應(yīng)根據(jù)具體指標(biāo)要求，保證有一定的糾檢錯誤的能力和編碼效率，要易于實現(xiàn)，節(jié)省費用。10.2檢錯碼10.2.1奇偶監(jiān)督碼

1．意義及特點奇偶監(jiān)督碼是奇監(jiān)督碼和偶監(jiān)督碼的統(tǒng)稱，是一種最基本的檢錯碼。在n-1個信息元后面附加一個監(jiān)督元，使得長度為n的碼字中1的個數(shù)保持為奇數(shù)或者偶數(shù)的碼稱為奇偶監(jiān)督碼?；蛘哒f,奇偶監(jiān)督碼是r=1、W為奇數(shù)或偶數(shù)的系統(tǒng)分組碼。常用的奇偶監(jiān)督碼的碼重W為偶數(shù)。設(shè)碼字A=［an-1，an-2，…，a1，a0］滿足an-1+an-2+…+a1+a0=0

(10.4)式中:a0為監(jiān)督元；“+”為模二加(以后也這樣表示，請讀者注意)。由于這種碼的每一個碼字均按同一規(guī)則構(gòu)成，因此又稱為一致監(jiān)督碼。式(10.4)稱為一致監(jiān)督方程或監(jiān)督方程。

利用式(10.4)，由信息元即可求出監(jiān)督元。另外，如果發(fā)生單個或者奇數(shù)個錯誤，就會破壞這個關(guān)系式，因此，通過該式能檢測碼字中是否發(fā)生了奇數(shù)個錯誤。以碼長n=5為例，列出全部偶監(jiān)督碼字如表10.1所示。從表中可以看出，該碼的最小碼距為2，這是能檢測單個錯誤所要求的最小d0值。人們常把注意力集中在檢(糾)單個錯誤上，這是因為碼字中發(fā)生單個錯誤的概率比發(fā)生兩個、多個錯誤的概率要大得多。設(shè)碼字中各碼元的錯誤互相獨立，誤碼率為10-4，則n=5的碼字只錯一位的概率為

錯兩位的概率為

錯3、4、5位的概率分別為10-11、5×10-16、10-20。由此可見，要檢(糾)錯誤，首先要解決單個錯誤，這樣才抓住了主要矛盾。一般情況下用上述偶監(jiān)督碼來檢出奇數(shù)個錯誤，檢錯效果是令人滿意的。奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個錯誤。奇偶監(jiān)督碼的編碼效率很高，R=(n-1)/n，隨著n的增大而趨近于1。

2．編碼電路和檢錯電路奇偶監(jiān)督碼的編碼可以用數(shù)字軟件實現(xiàn)，也可以用編碼電路(硬件)實現(xiàn)。圖10.3是碼長為5的偶監(jiān)督碼編碼器。4位長的信息組，串行送入4級移位寄存器(輸入定時緩沖器)，一旦存滿，立即輸送給輸出定時緩沖器前4級，同時經(jīng)模2運算得到監(jiān)督元，存入輸出緩沖器末級。編碼完成后即可輸出碼字。圖10.3偶監(jiān)督碼編碼器接收端的檢錯電路如圖10.4所示。當(dāng)一個接收碼組B完全進(jìn)入5級移存器內(nèi)時，開關(guān)S立即接通，從而取得檢錯信號M=b4+b3+b2+b1+b0。如果接收碼組B無錯，B=A，則M=0；如果接收碼組B有奇數(shù)個錯誤，則M=1。圖10.4偶監(jiān)督碼的檢錯電路行列監(jiān)督碼又稱為水平垂直一致監(jiān)督碼、二維奇偶監(jiān)督碼或者矩陣碼。它同時對水平(行)方向的碼元和垂直(列)方向的碼元實施奇偶監(jiān)督。一般L×m個信息元，附加L+m+1個監(jiān)督元，由L+1行、m+1列組成一個(Lm+L+m+1，Lm)行列監(jiān)督碼的碼字。圖10.5是(66，50)行列監(jiān)督碼的一個碼字(L=5，m=10)，它的各行和各列對1的數(shù)目都實行偶數(shù)監(jiān)督。可以逐行傳輸，也可以逐列傳輸。譯碼時分別檢查各行、各列的監(jiān)督關(guān)系，判斷是否有錯。圖10.5行列監(jiān)督碼這種碼具有較強(qiáng)的檢測隨機(jī)錯誤的能力，能發(fā)現(xiàn)所有1、2、3及其它奇數(shù)個錯誤，也能發(fā)現(xiàn)大部分偶數(shù)個錯誤，但是分布在矩形的四個頂點這類偶數(shù)個錯誤則例外。這種碼適于檢測突發(fā)錯誤。逐行傳輸時，能檢測長度b≤m+1的突發(fā)錯誤；逐列傳輸時，能檢測長度b≤L+1的突發(fā)錯誤。這種碼還可以糾正單個錯誤以及僅在一行中的奇數(shù)個錯誤，因為這些錯誤的位置是可以由行、列監(jiān)督而確定的。10.2.3恒比碼恒比碼又稱為等重碼或者定1碼，這種碼的碼字中1和0的位數(shù)保持恒定的比例。由于每個碼字的長度是相同的，因此，如果1、0恒比，則碼字必等重。如果碼長為n，碼重為W，則此碼的碼字個數(shù)為，禁用碼字?jǐn)?shù)為。該碼的檢錯能力較強(qiáng)，除對換差錯(1和0成對地出錯)不能發(fā)現(xiàn)外，其他各種錯誤均能發(fā)現(xiàn)。目前我國電傳通信中普遍采用3∶2碼，該碼共有個許用碼字，用來傳送10個阿拉伯?dāng)?shù)字，如表10.2所示。這種碼又稱為5中取3數(shù)字保護(hù)碼。因為每個漢字是以4位十進(jìn)制數(shù)來代表的，所以提高十進(jìn)制數(shù)字傳輸?shù)目煽啃?，就等于提高漢字傳輸?shù)目煽啃?。實踐證明，采用這種碼后，我國漢字電報的差錯率大為降低。

目前國際上通用的ARQ電報通信系統(tǒng)中，采用3∶4碼,即7中取3碼，這種碼共有個許用碼字，93個禁用碼字。35個許用碼字用來代表不同的字母和符號。實踐證明，應(yīng)用這種碼后，使國際電報通信的誤碼率保持在10-6以下。10.3線性分組碼10.3.1基本概念可以用線性方程組表述碼的規(guī)律性的分組碼稱為線性分組碼。奇偶監(jiān)督碼是一種線性分組碼，因為它滿足線性方程式(10.4)?，F(xiàn)在以(7，3)分組碼為例來說明線性分組碼的意義及特點。設(shè)該碼的碼字為A=［a6，a5，a4，a3，a2，a1，a0］，其中前3位是信息元，后4位是監(jiān)督元，可以用下列線性方程組來表述這種線性分組碼，產(chǎn)生4個監(jiān)督元：顯然,上述方程中各方程是線性無關(guān)的。對上式進(jìn)行運算，可以得到(7，3)線性分組碼的8個碼字，如表10.3所示。我們可以把(n，k)線性分組碼的每一個碼字看成是一個n維線性空間中的一個矢量。長度為n的碼組共有2n個，組成一個n維線性空間，(n，k)線性分組碼共有2k個碼字(k<n)，構(gòu)成了一個k維的線性子空間。因此，(n，k)線性分組碼是n維線性空間的一個k維子空間，這是線性分組碼的另一個定義。由于該線性子空間在模二加法運算中構(gòu)成阿貝爾群，因此線性分組碼又稱為群碼。某種集合稱為群，此集合中的元素(在此為任一碼組)對于某種運算(在此為模二加法)必須滿足下列4個條件：

(1)封閉性(自閉律)。集合中的任意兩個元素經(jīng)此運算后得到的仍為該集合中的元素。例如A1+A2=A3，A6+A7=A1等(A1、A2、…分別是表10.3中序號為1、2、…的碼字)。

(2)有零元(乘法運算為單位元)。如上例中A0即是零元，

A0+Ai=Ai

i=0，1,…，7

(3)有負(fù)元(乘法運算為逆元)。線性分組碼中任一碼組即是它自身的負(fù)元,

Ai+Ai=A0

i=0，1，…，7

(4)結(jié)合律成立。例如，(A2+A3)+A4=A2+(A3+A4)。如果除滿足上述4個條件外，又滿足交換律，則稱為交換群或者阿貝爾群。由于線性分組碼是滿足交換律的，如A1+A2=A2+A1等，因此，線性分組碼對于模二加法運算構(gòu)成交換群。

(n，k)線性分組碼的封閉性表明，碼組集合中的任意兩個碼組模二相加所得的碼組，一定在該碼組集中。又由于兩個碼組模二和所得的碼組的重量等于這兩個碼組的距離，因此(n，k)線性分組碼中兩個碼組之間的距離一定等于該分組碼中某一非全0碼組的重量。所以，線性分組碼的最小距離必等于碼中非全0碼字的最小重量。設(shè)A0為全0碼矢，則有d0=Wmin(Ai)Ai∈(n，k)，i≠0

(10.6)

上述重要特點告訴我們，如何去查找一個線性分組碼的最小距離，進(jìn)而明確該碼的糾(檢)錯能力。除此之外，線性分組碼還有以下特點：

(1)d(A1，A2)≤W(A1)+W(A2)；

(2)d(A1，A2)+d(A2，A3)≥d(A1，A3)；

(3)碼字的重量或者全部為偶數(shù)，或者奇數(shù)重量的碼字?jǐn)?shù)等于偶數(shù)重量的碼字?jǐn)?shù)。10.3.2漢明碼漢明碼是一種高碼率的糾單個錯誤的線性分組碼，其特點是d0=3，碼長n與監(jiān)督元個數(shù)r滿足關(guān)系式n=2r-1。現(xiàn)以r=3、n=7的(7，4)漢明碼為例來說明(n，k)線性分組碼編碼和譯碼的理論依據(jù)。

1．監(jiān)督矩陣H和生成矩陣G

設(shè)(7，4)漢明碼的碼字A=［a6，a5，a4，a3，a2，a1，a0］，它有3個監(jiān)督元，可以建立3個互相獨立的監(jiān)督關(guān)系式

(10.7)寫成矩陣形式為

簡記為H·AT=OT

或者

A·HT=O

(10.9)

其中AT是A的轉(zhuǎn)置，OT是O=[000]的轉(zhuǎn)置，HT是H的轉(zhuǎn)置。

(10.10)稱為(7，4)漢明碼的監(jiān)督矩陣。(n，k)線性分組碼的監(jiān)督矩陣H由r行n列組成，這r行是線性無關(guān)的。系統(tǒng)碼的監(jiān)督矩陣可寫成如下形式：

H=[PIr]

(10.11)稱為典型監(jiān)督矩陣，Ir為r×r的單位矩陣，P是r×k的矩陣。對式(10.10)，有

如果信息元已知，則通過P矩陣可以求得監(jiān)督元。將式(10.7)變換成

(10.12)

即滿足

或者

(10.13)只要將PT矩陣擴(kuò)展一下，在其左邊加上4×4的單位矩陣，即可由已知的信息元求得碼組A，即

(10.14)其中。設(shè)信息組M=［a6，a5，a4，a3］，則式(10.14)可以寫成

A=M·G

(10.15)G稱為生成矩陣。由生成矩陣及信息組就可以產(chǎn)生出全部碼字。G由k行n列組成，每一行是一個碼字，k行線性無關(guān)。系統(tǒng)碼的生成矩陣可以寫成：

G=［IkPT］(10.16)

稱為典型生成矩陣。利用式(10.14)產(chǎn)生的全部(7，4)碼的碼字如表10.4所示。

2．伴隨式(校正子)

設(shè)發(fā)送碼組A=［an-1，an-2，…，a1，a0］，接收碼組B=［bn-1，bn-2，…，b1，b0］，錯誤圖樣(誤差矢量)為E=［en-1，en-2，…，e1，e0］

E=B-A=B+A

E矩陣中哪位出現(xiàn)1，就表示接收碼組B中相應(yīng)的碼元錯了。接收端利用監(jiān)督矩陣來檢測接收碼組B中的錯誤。令S=BHT，稱為伴隨式或者校正子，則

S=BHT=(A+E)HT=AHT+EHT=EHT

(10.17)

由于E為1×n矩陣，HT為n×r矩陣，因此S為1×r矩陣，即r列的行矩陣

S=［Sr-1，Sr-2，…，S1，S0］(10.18)

由式(10.17)可知，S與E之間有確定的線性變換關(guān)系，即S能代表B中錯誤的情況，B無錯則S=0，B有錯則S≠0(非全0矩陣)。S有2r種不同的形式，可以代表2r-1種錯誤圖樣。為了用伴隨式指明單個錯誤的位置以便糾正，要求

2r-1≥n

(10.19)

對于(7，4)漢明碼，n=7，r=3，n=2r-1，即對式(10.19)取等號。這就表明用來糾正單個錯誤時，漢明碼所用的監(jiān)督碼元位數(shù)最少。與碼長相同的其他糾單個錯誤的碼比較，其碼率最高。上述(7，4)漢明碼的伴隨式S與錯誤圖樣E的對應(yīng)關(guān)系可以由式(10.17)求得，如表10.5所示。在接收端的譯碼器中有專門的伴隨式計算電路，可實現(xiàn)檢錯和糾錯。10.3.3循環(huán)碼循環(huán)碼是一類重要的線性分組碼，它的構(gòu)造便于運用代數(shù)理論來研究。其編譯碼電路比較簡單，因此應(yīng)用十分廣泛。

1．循環(huán)碼的意義及特點如果線性分組碼的任一碼組循環(huán)移位所得的碼組仍在該碼組集合中，則此線性分組碼稱為循環(huán)碼。很明顯，(n，1)重復(fù)碼是一個循環(huán)碼。表10.6中的(7，3)碼及表10.7中的(6，3)碼也都是循環(huán)碼，其循環(huán)特性分別如圖10.6及圖10.7所示。循環(huán)圈上的數(shù)字為碼字的序號。由圖可見，同一循環(huán)圈上的各碼組重量是相等的。全0、全1碼組分別自成循環(huán)圈。循環(huán)碼的循環(huán)圈數(shù)目≥2。圖10.6(7，3)循環(huán)碼的循環(huán)圈圖10.7(6，3)循環(huán)碼的循環(huán)圈

人們常用代數(shù)多項式來表示循環(huán)碼的碼字，稱為碼多項式。(n，k)循環(huán)碼的碼多項式按降冪順序排列為

A(x)=an-1xn-1+an-2xn-2+…+a1x+a0

(10.20)

碼組中各位碼元的數(shù)值是其碼多項式中相應(yīng)各項的系數(shù)值(0或1)。例如,表10.6中第4號碼字可以用多項式A4(x)=x6+x3+x2+x表示。

2．生成多項式及生成矩陣循環(huán)碼中次數(shù)最低的多項式(全0碼字除外)稱為生成多項式g(x)?？梢宰C明，g(x)是常數(shù)項為1的r=n-k次多項式，是xn+1的一個因式。循環(huán)碼的碼多項式都是g(x)的倍式。用多項式來表示生成矩陣的各行，則生成矩陣可以寫成

(10.21)其中

g(x)=xr+gr-1xr-1+…+g1x+1

(10.22)例如表10.6中(7，3)循環(huán)碼，n=7，k=3，r=4，其生成多項式及生成矩陣分別為

即生成矩陣中的3行都是表10.6中的碼字，并且是線性無關(guān)的。表10.6中的所有碼字用多項式表示時，均是g(x)的倍式。g(x)可由x7+1分解因式(系數(shù)按模二運算)得到x7+1=(x4+x3+x2+1)

(x3+x2+1)。設(shè)信息組M=［mk-1，mk-2，…，m1，m0］，則(n，k)循環(huán)碼的所有碼字由下式生成：A(x)=MG(x)=(mk-1xk-1+mk-2xk-2+…+m1x+m0)·g(x)

=m(x)·g(x)(10.23)其中m(x)為信息組多項式，其最高次數(shù)為k-1。由上式可見，知道m(xù)(x)及g(x)就可以生成全部碼字。但是，由式(10.23)直接產(chǎn)生的碼字并非系統(tǒng)碼。由于(n，k)循環(huán)碼的所有碼多項式都是g(x)的倍式，最高次數(shù)為n-1，因此系統(tǒng)循環(huán)碼的碼多項式可以表示為A(x)=xn-k·m(x)+［xn-k·m(x)］′

(10.24)其中，前一部分代表信息組；后一部分用［］′表示，是xn-k·m(x)被g(x)除得的余式，代表監(jiān)督組。

3．監(jiān)督多項式及監(jiān)督矩陣由于(n，k)循環(huán)碼中的g(x)是xn+1的因式，因此可以令

(10.25)由于g(x)是常數(shù)項為1的r次多項式，因此h(x)必是常數(shù)項為1的k次多項式。h(x)稱為監(jiān)督多項式。與式(10.21)所表示的G(x)相對應(yīng)，監(jiān)督矩陣可以表示為(10.26)其中h*(x)=xk+h1xk-1+h2xk-2+…+hk-1x+1(10.27)是h(x)的逆多項式。例如表10.6中的(7，3)循環(huán)碼：g(x)=x4+x3+x2+1則h*(x)=x3+x+1于是即

4．編碼電路根據(jù)式(10.24)，利用多項式除法電路求xn-km(x)除以g(x)的余式，即可產(chǎn)生(n，k)系統(tǒng)循環(huán)碼。當(dāng)g(x)=x4+x3+x2+1時，(7，3)循環(huán)碼的編碼器如圖10.8所示。D0D1D2D3是4級移存器，反饋線的連接與g(x)的非0系數(shù)相對應(yīng)。首先，4級移存器清零，3位信息元輸入時，門1斷開，門2接通，直接輸出信息元。第3次移位脈沖來時,將除法電路運算所得的余數(shù)存入4級移存器中。第4~7次移位時，門2斷開，門1接通，輸出監(jiān)督元(即余數(shù))。當(dāng)一個碼字輸出完畢后,就將移存器清零，等待下一組信息數(shù)字送入后重新編碼。設(shè)輸入的信息組為110，圖10.8中各器件及端點狀態(tài)變化情況如表10.8所示。該編碼器編出的全部碼字如表10.6所示。圖10.8(7，3)循環(huán)碼編碼器

5．譯碼電路設(shè)接收碼組、錯誤圖樣及伴隨式的多項式分別為

B(x)=bn-1xn-1+bn-2xn-2+…+b1x+b0

E(x)=en-1xn-1+en-2xn-2+…+e1x+e0

S(x)=Sr-1xr-1+Sr-2xr-2+…+S1x+S0

可以證明

S(x)=B·HT(x)=［B(x)］′=［E(x)］′(10.28)即B(x)或E(x)除以g(x)所得的余式就是S(x)。用于檢錯時，根據(jù)S(x)是否為零來判決接收碼組B是否有錯，S(x)=0時,表明B無錯，S(x)≠0時,表明B有錯。用于糾錯時，需要根據(jù)不同的非零S(x)來指明不同的錯誤位置，從而糾正錯誤。伴隨式S(x)的計算由g(x)除法電路來實現(xiàn)。利用式(10.28)可以求得(7，3)循環(huán)碼單個錯誤的錯型多項式E(x)與伴隨式S(x)的對應(yīng)關(guān)系，如表10.9所示。針對接收碼組中單個錯誤出現(xiàn)在首位的錯誤圖樣及相應(yīng)的伴隨式來設(shè)計組合邏輯電路，以實現(xiàn)糾錯。由于循環(huán)碼的伴隨式也具有循環(huán)移位特性，因此利用移存器的循環(huán)移位就可以糾正任何一位上的單個錯誤。為了在g(x)除法電路的移存器中存放如表10.9所示的與E(x)對應(yīng)的伴隨式，接收碼組必須從除法電路的第一級移存器輸入。上述(7,3)循環(huán)碼的譯碼電路如圖10.9所示。接收到的B(x)(高次項在前，低次項在后)一方面送入7級緩沖移位寄存器，一方面送入g(x)除法電路計算伴隨式。第7次移位時，7個碼元一組的碼組全部送入緩存器，B(x)中首位b6輸出，同時g(x)除法電路也得到了伴隨式S(x)(共4項，由低次到高次分別存于D0、D1、D2、D3中)，如果首位b6有錯，則D0D1D2D3的狀態(tài)必為0111。經(jīng)與門輸出1(糾錯信號)，即可糾正b6的錯誤，該糾錯信號同時也送到S(x)計算電路去清零，如圖中虛線所示。此糾錯譯碼過程如表10.10所示。其他位上錯誤的糾正過程讀者可自行畫出。圖10.9(7，3)循環(huán)碼譯碼器之一為使譯碼連續(xù)不斷地進(jìn)行，在譯碼器中需要采用兩套g(x)除法電路。采用像編碼器中的變形除法電路進(jìn)行譯碼也是可以的，但是邏輯控制電路有所不同，如圖10.10所示，其譯碼過程供讀者自己研究。圖10.10(7，3)循環(huán)碼譯碼器之二10.3.4BCH碼

BCH碼是循環(huán)碼的一個子集，它是以三個發(fā)明者的名字Bose、Chaudhuri和Hocquenghem命名的，一般用于糾正t個錯誤。BCH碼的設(shè)計因具有良好的通用性并且有高效的譯碼算法而受到高度重視。對于任意碼長m≥2，糾錯數(shù)目為t的編碼，都存在滿足下列參數(shù)的BCH碼：n=2m-1，n-k≤mt，dmin=2t+1。由于m和t可以自由選擇，因此在碼長和碼率的設(shè)計上有很大的選擇余地。BCH碼已經(jīng)過了詳細(xì)的推導(dǎo)，并且有了碼長為7~255的BCH碼生成多項式的系數(shù)表，有興趣的讀者可以查閱相關(guān)文獻(xiàn)。10.3.5里德-索洛蒙碼里德-索洛蒙(R-S，Reed-Solomon)碼是BCH碼的子集，因此也屬于循環(huán)碼。它是一種非二進(jìn)制碼，即碼字c=(c1，c2,…，cn)中的任意元素ci是一個q進(jìn)制數(shù)，q=2k，這時每個q進(jìn)制字符包含k比特信息。在(N，K)R-S碼中，長度為K的q進(jìn)制碼元將映射為長度為N的q進(jìn)制碼元，然后在信道上傳送，如圖10.11所示。圖10.11R-S碼編碼器

R-S碼是按照下列條件定義的BCH碼：N=q-1=2k-1(k=2，3，…)，dmin=N-K+1，碼率Rc=K/N。R-S碼能夠糾正t=(dmin-1)/2個碼元錯誤。里德-索洛蒙碼具有優(yōu)越的距離特性，特別適于與q進(jìn)制調(diào)制聯(lián)合使用。R-S碼還能夠有效地糾正突發(fā)錯誤，因為突發(fā)錯誤在R-S碼中表現(xiàn)為少量幾個碼元錯誤，因而易于糾正。在二進(jìn)制編碼中，同樣的突發(fā)錯誤會導(dǎo)致許多比特的錯誤，因而不容易糾正。

R-S碼還可以與二進(jìn)制編碼進(jìn)行連接，以獲得更強(qiáng)的糾錯能力。與R-S碼連接的二進(jìn)制編碼可以是分組碼或者卷積碼。

圖10.12m=4的(28，16)交錯碼10.3.6交錯碼交錯碼又稱交織碼，是一種能糾正突發(fā)錯誤的碼。它是利用糾隨機(jī)錯誤的碼，以交錯的方法來構(gòu)造碼本的。把糾隨機(jī)錯誤的(n，k)線性分組碼的m個碼字，排成m行的一個碼陣，該碼陣稱為交錯碼陣。一個交錯碼陣就是交錯碼的一個碼字。交錯碼陣中的每一行稱為交錯碼的子碼或行碼，行數(shù)m稱為交錯度。圖10.12所示的是(28，16)交錯碼的一個碼字，其行碼是能糾單個隨機(jī)錯誤的(7，4)線性分組碼，交錯度m=4。傳輸時按列的次序進(jìn)行，因此送往信道的交錯碼的一個碼字為a61

a62

a63

a64

a51

a52…a01

a02

a03

a04。

圖10.12m=4的(28，16)交錯碼在傳輸過程中如果發(fā)生長度b≤4的單個突發(fā)錯誤，那么無論從哪一位開始，至多只影響圖10.12碼陣中每一行的一個碼元。接收端把收到的交錯碼的碼字再排成如圖10.12所示的碼陣，然后逐行分別譯碼，由于每一行碼能糾正一個錯誤，因此4行譯完后，就可把b≤4的突發(fā)錯誤糾正過來。如果要糾正較長的突發(fā)錯誤，則可以把碼陣中的行數(shù)增加，即增大交錯度(交織度)。一般，一個(n，k)碼能糾正t個隨機(jī)錯誤，按照上述方法交錯，交錯度為m時即可得到一個(nm，km)交錯碼,該交錯碼能糾正長度b≤mt的單個突發(fā)錯誤。可以證明，如果(n，k)是一個循環(huán)碼，它的生成多項式為g(x)，那么(nm，km)交錯碼也是一個循環(huán)碼，其生成多項式為g(xm)，且碼率與其行碼相同。10.4卷積碼卷積碼的規(guī)律性與分組碼有明顯的區(qū)別。(n，k)線性分組碼的規(guī)律性完全局限在各碼組之內(nèi),每個碼組的n個碼元完全由本組的k個信息元確定?；蛘哒f，各碼組中的監(jiān)督元只對本組的信息元起監(jiān)督作用。卷積碼則不同，每個(n，k)碼段(也稱子碼，通常較短)內(nèi)的n個碼元不僅與該碼段內(nèi)的信息元有關(guān)，而且與前面m段內(nèi)的信息元有關(guān)?；蛘哒f，各碼段內(nèi)的監(jiān)督元不僅對本碼段而且對前面m段內(nèi)的信息元起監(jiān)督作用。卷積碼序列的每一碼段與前后有關(guān)碼段互相關(guān)聯(lián)，一環(huán)扣一環(huán)，因此又稱為連環(huán)碼。這種碼能用卷積運算的線性方程組描述。分組碼各碼組彼此獨立地進(jìn)行編碼和譯碼。卷積碼則不然，無論編碼還是譯碼，各子碼都不能獨立地進(jìn)行。卷積碼子碼間的約束關(guān)系如圖10.13所示。圖中A1，A2,…表示卷積碼序列中的各個子碼，均是(n，k)線性分組碼，各子碼之間的約束范圍如圖中虛線方框所示。通常稱m為編碼存儲，它反映了輸入信息元在編碼器中需要存儲的時間長短；稱N=m+1為編碼約束度，它是相互約束的碼段個數(shù)；稱nN為編碼約束長度，它是相互約束的碼元個數(shù)。卷積碼常用子碼長度、子碼中的信息元個數(shù)及編碼存儲三個參數(shù)表示，記為(n，k，m)，或用約束度及子碼符號表示，記為N(n，k)，也可用約束長度內(nèi)的分組碼形式表示，記為(nN，kN)。如果卷積碼的各子碼是系統(tǒng)碼，則稱該卷積碼為系統(tǒng)卷積碼，否則為非系統(tǒng)卷積碼。很明顯，假如m=0，N=1，那么卷積碼就是(n，k)分組碼了。圖10.13卷積碼子碼間的約束關(guān)系圖10.14是一個(3，1，2)系統(tǒng)卷積碼的編碼器。由三級移位寄存器、兩個模二加法器及開關(guān)電路組成。編碼前，各級移存器清零，信息元按a1a2

a3…aj-2

aj-1

aj…的順序輸入編碼器。每輸入一個信息元aj，開關(guān)S依次接到aj、aj1、aj2各端點一次，編出一個子碼ajaj1aj2(n=3，k=1)，其中兩個監(jiān)督元由下式確定：

(10.29)編碼器編出的任一子碼均與前面兩段信息元有關(guān)，因此編碼存儲m=2，編碼約束度N=m+1=3，約束長度Nn=9。圖10.14(3，1，2)卷積碼編碼器及輸入輸出關(guān)系10.5復(fù)合編碼分組碼和卷積碼的性能都與其距離特性有關(guān)。為了設(shè)計一個達(dá)到給定碼率并且具有較好距離特性的分組碼或者卷積碼，只有增加碼字的分組長度n或者卷積碼的約束長度，這將導(dǎo)致譯碼器復(fù)雜度增加。為了在增加碼字的有效分組長度或約束長度的同時，限制設(shè)備復(fù)雜度的增加，人們提出了許多方案，其中大多數(shù)方法都是通過合成簡單編碼而得到復(fù)雜編碼，合成碼的譯碼方法也是基于前面討論的簡單編碼。如果采用復(fù)雜的最佳譯碼算法，則通常也能獲得滿意的效果。下面簡單討論三種使用較為廣泛的復(fù)合編碼，即乘積碼、鏈接碼和Turbo碼。10.5.1乘積碼乘積碼也稱陣列碼，由以矩陣形式列出的兩個線性分組碼構(gòu)成，如圖10.15所示。這兩個線性分組碼的參數(shù)分別是(n1，k1，dmin1)和(n2，k2，dmin2)，合成碼是參數(shù)為(n1n2，k1k2，dmin1

dmin2)的線性分組碼，它的最小距離是其組成碼的最小距離的乘積，即dmin=dmin1dmin2。如果采用復(fù)雜的最佳譯碼，則糾錯能力為

(10.30)圖10.15乘積碼的結(jié)構(gòu)示意圖其中［.］表示向下取整。也可以用組成碼的特性來譯碼，譯碼思路如下:先根據(jù)行上的碼字猜測每一比特的值，再根據(jù)對應(yīng)列上的碼字進(jìn)一步修改猜測的結(jié)果。這一過程可以用迭代的方法反復(fù)進(jìn)行，在每一步的迭代中逐漸提高猜測的準(zhǔn)確度，稱這種譯碼方式為迭代譯碼。10.5.2鏈接碼鏈接碼包括一個內(nèi)部碼和一個外部碼，兩者的連接方式如圖10.16所示。內(nèi)部碼是二進(jìn)制分組碼或者卷積碼，而典型的外部碼是R-S碼。設(shè)內(nèi)部碼是(n，k)碼，可以把內(nèi)部編碼器、數(shù)字調(diào)制器、波形信道、數(shù)字解調(diào)器和內(nèi)部譯碼器合并起來看成一個數(shù)字信道，信道的輸入、輸出都是長度為k的二進(jìn)制分組，或者說是q進(jìn)制字符集中的一個元素。隨后,對這個q進(jìn)制輸入、q進(jìn)制輸出的信道運用R-S碼(外部碼)，以達(dá)到更高的糾錯性能。如果內(nèi)部碼和外部碼的碼率分別是rc和Rc，則鏈接碼的碼率為

Rcc=Rcrc

(10.31)圖10.16鏈接碼結(jié)構(gòu)示意圖10.5.3Turbo碼

Turob碼是一類特殊的鏈接碼，在兩個并聯(lián)或者串聯(lián)的編碼器之間存在一個數(shù)字交織器，使得Turbo碼具有很大的碼字長度和優(yōu)越的性能，特別是在低SNR的情況下。采用Turbo碼可以在低SNR的情況下獲得接近0.7dB的香農(nóng)極限。

Turbo碼編碼器的結(jié)構(gòu)如圖10.17所示，兩個成員碼由長度為N的數(shù)字交織器分隔開。成員碼通常是碼率為1/2的遞歸系統(tǒng)卷積碼(RSCC，RecursiveSystematicConvolutionalCodes)，并且兩個成員碼通常是相同的。遞歸卷積碼與常見的非遞歸卷積碼的區(qū)別在于遞歸卷積碼移位寄存器中存在反饋，因此以無限脈沖響應(yīng)(IIR，InfiniteImpulseResponse)的濾波器形式實現(xiàn)。圖10.17Turbo碼的編碼原理框圖圖10.17所示的編碼器中，在N比特信息進(jìn)入第1編碼器的同時，通過交織器將此N比特信息傳送到第2編碼器。因為編碼器采用系統(tǒng)碼，所以每個編碼器的輸出在N個消息比特后加上了N個監(jiān)督比特，最終的比特輸出是3N比特，即N比特信息和兩個編碼器的2N監(jiān)督比特。因此總的碼率為R=N/(3N)=1/3。

Turbo碼中的數(shù)字交織器的長度通常都很大，采用偽隨機(jī)交織器可以獲得很好的性能。由于Turbo碼是由兩個成員碼構(gòu)成的，因此可以采用迭代算法進(jìn)行譯碼。所有服從比特的似然特性的譯碼都可以使用迭代算法實現(xiàn)，例如最大后驗概率譯碼及其各種變形等。還有一種復(fù)雜度較低的方法是軟輸出維特比算法(SOVA，SoftOutpotViterbiAlgorithm)，在這類譯碼中，第1級譯碼器計算出每一比特的似然度并送入第2級譯碼器，第2個譯碼器計算似然度后將結(jié)果進(jìn)行修正并返回給第1級譯碼器。重復(fù)這一過程，直到似然度顯示的正確譯碼概率很高為止，則在這一點上得到最終判決。迭代過程如圖10.18所示，圖中ys、y1p、y2p分別表示對應(yīng)于信息比特、系統(tǒng)比特編碼器1的監(jiān)督比特、編碼器2的監(jiān)督比特的接收數(shù)據(jù)，L12和L21表示在兩個譯碼器之間傳遞的信息。圖10.18Turbo碼迭代譯碼原理10.6m

序列

m序列是由線性反饋移位寄存器產(chǎn)生的周期最長的碼序列。m表示最長周期的意思。m序列是一種正交碼，它具有隨機(jī)特性，是目前廣泛應(yīng)用的一種偽隨機(jī)或偽噪聲(PN)碼。10.6.1正交碼及偽隨機(jī)碼的概念如果n個長度均為P的碼組X1，X2，…，Xn所組成的集合中任意兩個不同碼組的互相關(guān)系數(shù)均為零，即

ρ(Xi，Xj)=0i≠j

(10.32)則稱這種碼組集合為正交碼。如果ρ(Xi，Xj)<0，i≠j，則稱為超正交碼。有時把兩者統(tǒng)稱為正交碼。對于(+1，-1)二元序列，互相關(guān)系數(shù)為(10.33)式中,Xik、Xjk分別表示碼組Xi、Xj的第k個碼元值。互相關(guān)系數(shù)也可以表示為

(10.34)式中,A為Xi、Xj中對應(yīng)碼元相同的個數(shù)，D為Xi、Yj中對應(yīng)碼元不同的個數(shù)。顯然,A+D=P。對于(0,1)二元序列，其互相關(guān)系數(shù)用式(10.34)計算，或者規(guī)定0、1分別對應(yīng)+1、-1，再用式(10.33)計算。可以預(yù)先確定并且可以重復(fù)實現(xiàn)的序列稱為確定序列；具有隨機(jī)特性，貌似隨機(jī)序列的確定序列稱為偽隨機(jī)序列或偽噪聲(PN)碼。偽噪聲碼是很實用的正交碼。由于正交碼各碼組之間的相關(guān)性很弱，受到干擾后不容易互相混淆，因而具有較強(qiáng)的抗干擾能力。10.6.2線性反饋移位寄存器圖10.19是線性反饋移位寄存器的原理框圖，它由n級移位寄存器、時鐘脈沖產(chǎn)生器(省略未畫)及一些模二加法器經(jīng)適當(dāng)連接而成。圖中，ai(i=0，1，…，n-1)表示某一級移存器的狀態(tài);Ci表示反饋線的連接狀態(tài)(相當(dāng)于反饋系數(shù))，Ci=1表示此線接通，參與反饋，Ci=0表示此線斷開，不參與反饋。C0=Cn=1。圖10.19線性反饋移位寄存器

(1)遞推關(guān)系式(反饋邏輯函數(shù))。移位寄存器各級的初始狀態(tài)及反饋連接狀態(tài)如圖10.19所示，反饋到第1級的信號為一般，如果n級移存器的狀態(tài)為al-1，al-2，…，al-n，則反饋到第1級的信號為

(10.35)根據(jù)遞推關(guān)系式(10.35)，可以從移位寄存器的初始狀態(tài)(l=n時)a0，a1，…，an-1直接推導(dǎo)出an，an+1，…，從而得到整個輸出序列{ak}。

(2)序列多項式(母函數(shù))。輸出序列{ak}=a0，a1，a2，…用多項式表示時，可寫成

(10.36)稱為序列多項式。

(3)特征多項式(特征方程)。把反饋系數(shù)C0,C1,…,Cn寫成多項式形式，即

(10.37)稱為線性反饋移存器的特征多項式。由于C0=Cn=1，因此特征多項式必包含xn+1項。特征多項式的次數(shù)n就是移位寄存器的級數(shù)。Ci的取值(0或1)確定了反饋線的連接狀態(tài)。

(4)線性反饋移位寄存器的相繼狀態(tài)具有周期性，周期P≤2n-1。n級線性反饋移位寄存器能產(chǎn)生m序列(P=2n-1)的充要條件是：移存器的特征多項式f(x)為本原多項式。f(x)為n次本原多項式，必須滿足三個條件：第一，f(x)為既約(不可再分解的)多項式；第二，f(x)能整除xP+1，P=2n-1；第三，f(x)不能整除xq+1，q<P。10.6.3m序列產(chǎn)生器要構(gòu)成m序列產(chǎn)生器，關(guān)鍵是確定其特征多項式。現(xiàn)以4級移位寄存器構(gòu)成周期為P=24-1=15的m序列產(chǎn)生器為例來說明。先將x15+1分解因式，使各因式為既約多項式，再從中尋找次數(shù)為4的本原多項式,即x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)其中4次既約多項式有3個，但是x4+x3+x2+x+1能整除x5+1，因此它不是本原多項式，而x4+x+1或x4+x3+1不能整除xq+1(q<15)，因此它們均是本原多項式。取f(x)=1+x+x4，構(gòu)成的m序列產(chǎn)生器如圖10.20所示。設(shè)4級移位寄存器的初始狀態(tài)為1000，其相繼狀態(tài)如圖所示。由圖可見，輸出序列{ak}的周期長度為15。值得注意的是，移位寄存器的初始狀態(tài)不能為全0，否則輸出序列就是全0了。為此，m序列產(chǎn)生器中通常有所謂的全0排除電路，這樣才能確保m序列產(chǎn)生器正常工作。圖10.20m序列的產(chǎn)生10.6.4m序列的性質(zhì)

(1)均衡特性(平衡性)。m序列每一周期中1的個數(shù)比0的個數(shù)多1。P=2n-1為奇數(shù)，1的個數(shù)為(P+1)/2=2n-1(偶數(shù))，0的個數(shù)為(P-1)/2=2n-1-1(奇數(shù))。P足夠大時，在每一周期中1與0出現(xiàn)的次數(shù)基本相同(均衡)。上例中P=15，1為8個，0為7個。

(2)游程特性(游程分布的隨機(jī)性)。游程是序列中連續(xù)出現(xiàn)同種元素的統(tǒng)稱。一個游程中元素的個數(shù)稱為游程長度。m序列每個周期中的游程總數(shù)為2n-1(偶數(shù))，“1”游程與“0”游程的數(shù)目各占一半。其中:長度為n的“1”游程1個；長度為n-1的“0”游程1個；長度為n-2的游程21=2個;長度為n-3的游程22=4個。一般，長度為k的游程個數(shù)為2n-k-1個，1≤k≤n-1。在k的取值范圍內(nèi)，游程長度每減短1，則其游程數(shù)目加倍。長度為1的游程個數(shù)為2n-2，是游程總數(shù)的一半。上例中一個周期內(nèi)的碼元為000111101011001，可見長度為1的“1”游程、“0”游程各為2個，長為2的“1”游程、“0”游程各為1個，長為3的“0”游程1個，