通信原理精品第10章 信道編碼ppt課件

1、第10章信道編碼 10.1 引言引言 10.2 信道編碼的根本概念信道編碼的根本概念 10.3 常用檢錯碼常用檢錯碼 10.4 線性分組碼線性分組碼 10.5 循環(huán)碼循環(huán)碼 10.6 卷積碼卷積碼 10.7 交錯碼與級聯(lián)碼交錯碼與級聯(lián)碼 10.8 m序列序列 本章小結(jié)本章小結(jié) 習(xí)題習(xí)題 第第10章信道編碼章信道編碼第10章信道編碼 10.1 引引 言言數(shù)字信號在信道的傳輸過程中，由于實數(shù)字信號在信道的傳輸過程中，由于實踐信道的傳輸特性不理想以及存在噪聲及干踐信道的傳輸特性不理想以及存在噪聲及干擾，在接納端往往會產(chǎn)生誤碼。為了提高數(shù)擾，在接納端往往會產(chǎn)生誤碼。為了提高數(shù)字通訊的可靠性，可合理設(shè)計

2、系統(tǒng)的發(fā)送和字通訊的可靠性，可合理設(shè)計系統(tǒng)的發(fā)送和接納濾波器，采用平衡技術(shù)，消除數(shù)字系統(tǒng)接納濾波器，采用平衡技術(shù)，消除數(shù)字系統(tǒng)中碼間干擾的影響，還可選擇適宜的調(diào)制解中碼間干擾的影響，還可選擇適宜的調(diào)制解調(diào)技術(shù)，添加發(fā)射機功率，采用先進的天線調(diào)技術(shù)，添加發(fā)射機功率，采用先進的天線技術(shù)等。假設(shè)數(shù)字系統(tǒng)的誤碼仍不能滿足要技術(shù)等。假設(shè)數(shù)字系統(tǒng)的誤碼仍不能滿足要求，那么可以采用信道編碼技術(shù)，進一步降求，那么可以采用信道編碼技術(shù)，進一步降低誤碼率。采用信道編碼技術(shù)的數(shù)字通訊系低誤碼率。采用信道編碼技術(shù)的數(shù)字通訊系統(tǒng)如圖統(tǒng)如圖10.1.1所示。所示。第10章信道編碼 圖10.1.1 采用信道編碼技術(shù)的數(shù)字通

3、訊系統(tǒng)第10章信道編碼 信道編碼是按一定的規(guī)律給信息添加冗余度，使不帶規(guī)律的原始數(shù)字信息變換為具有一定規(guī)律的數(shù)字信息。信道譯碼那么是利用這些規(guī)律性來鑒別能否發(fā)生錯誤，進而糾正錯誤。詳細(xì)地說，信道編碼就是在發(fā)送端被傳輸?shù)男畔⒋a元序列中，以一定的編碼規(guī)那么附加一些監(jiān)視碼元，接納端利用該規(guī)那么進展譯碼，譯碼的結(jié)果可以發(fā)現(xiàn)錯誤或糾正錯誤。信道編碼是用添加數(shù)碼，利用冗余來提高抗干擾才干的。亦是以降低信息傳輸速率為代價來減少錯誤的，或者說是用減弱有效性來加強其可靠性的。第10章信道編碼 信道編碼不同于信源編碼。信源編碼是為提高數(shù)字信號有效性而采取的一種編碼技術(shù)，其目的是盡能夠緊縮冗余度。它可降低數(shù)碼率，緊

4、縮傳輸頻帶。而信道編碼的目的在于提高數(shù)字通訊的可靠性。需求強調(diào)的是：信源編碼減少了冗余度，而信道編碼添加了冗余度，但這兩種冗余度是不同的。信源編碼減少的冗余度是隨機的、無規(guī)律的，即使不減少它，它也不能用來檢錯或糾錯；信道編碼添加的冗余度那么是特定的、有規(guī)律的、有用的，可用它來檢錯和糾錯。本章主要引見常用的信道編碼技術(shù)，主要內(nèi)容有常用檢錯碼、常用糾錯碼的編碼和譯碼原理，最后還將引見m序列及其運用。第10章信道編碼 10.2 信道編碼的根本概念信道編碼的根本概念10.2.1 信道編碼的檢錯、糾錯原理信道編碼的檢錯、糾錯原理信道編碼的根本思想是在被傳輸信息中附信道編碼的根本思想是在被傳輸信息中附加一

5、些冗余碼元，我們稱這些冗余碼元為監(jiān)視加一些冗余碼元，我們稱這些冗余碼元為監(jiān)視碼元。監(jiān)視碼元和信息碼元有一定的關(guān)系碼元。監(jiān)視碼元和信息碼元有一定的關(guān)系(規(guī)規(guī)律律)，接納端利用監(jiān)視碼元和信息碼元的這種關(guān)，接納端利用監(jiān)視碼元和信息碼元的這種關(guān)系加以校驗，以檢測和糾正錯誤。這種糾、檢系加以校驗，以檢測和糾正錯誤。這種糾、檢錯才干是用編碼的冗余度換取的。錯才干是用編碼的冗余度換取的。設(shè)發(fā)送端發(fā)送設(shè)發(fā)送端發(fā)送A和和B兩個音訊，要表示兩個音訊，要表示A、B兩種音訊只需求一位編碼，即用兩種音訊只需求一位編碼，即用“1表示表示A，用用“0表示表示B。這種編碼無冗余度，效率最高，。這種編碼無冗余度，效率最高，但同

6、時它也無抗干擾才干。假設(shè)在傳輸過程中但同時它也無抗干擾才干。假設(shè)在傳輸過程中發(fā)生誤碼，即發(fā)生誤碼，即“1錯成錯成“0或或“0錯成錯成“1，收端無法判別收到的碼元能否發(fā)生錯誤，由于收端無法判別收到的碼元能否發(fā)生錯誤，由于“1和和“0都是發(fā)送端能夠發(fā)送的碼元，所以都是發(fā)送端能夠發(fā)送的碼元，所以這種編碼方法無糾、檢錯才干。這種編碼方法無糾、檢錯才干。第10章信道編碼 假設(shè)添加一位監(jiān)視碼元，添加的監(jiān)視碼元與信息碼元一樣，即用“11表示音訊A，用“00表示信息B。如傳輸過程中發(fā)生1位錯誤，那么“11、“00變成“10或“01。此時接納端能發(fā)現(xiàn)這種錯誤，由于發(fā)送端不能夠發(fā)送“01或“10。但它不能糾錯，由

7、于“11和“00出現(xiàn)1位錯誤時都可變成“10或“01。所以，當(dāng)接納端收到“10或“01時，它無法確定發(fā)送端發(fā)送的是“11還是“00。第10章信道編碼 假設(shè)添加二位監(jiān)視碼元，監(jiān)視碼元仍和信息碼元一樣，即用“111表示音訊A，用“000表示音訊B。那么假設(shè)傳輸過程中出現(xiàn)1位錯誤，可以糾正。如發(fā)送端發(fā)送“111，傳輸中出現(xiàn)1位錯誤，使得接納端收到“110。此時顯然能發(fā)現(xiàn)這個錯誤，由于發(fā)送端只能夠發(fā)送“111或“000。再根據(jù)“110與“111及“000的類似程度，將“110翻譯為“111，這時“110中的1位錯誤得到了糾正。假設(shè)“111在傳輸過程中出現(xiàn)2位錯誤，接納端收到“100、“010或“001

8、。由于它們即不代表音訊A，也不代表音訊B，所以接納端能發(fā)現(xiàn)出了錯誤，但無法糾正這2位錯誤。假設(shè)硬要糾錯，會將“100、“010或“001翻譯成“000，顯然糾錯沒有勝利。第10章信道編碼 10.2.2 碼長、碼重、碼距和編碼效率碼長、碼重、碼距和編碼效率原始數(shù)字信息是分組傳輸?shù)?，以二進制編碼為例，每原始數(shù)字信息是分組傳輸?shù)?，以二進制編碼為例，每k個個二進制位為一組，稱為信息組，經(jīng)信道編碼后轉(zhuǎn)換為每二進制位為一組，稱為信息組，經(jīng)信道編碼后轉(zhuǎn)換為每n個二個二進制位為一組的碼字進制位為一組的碼字(也稱為碼組也稱為碼組)，碼字中的二進制位稱為碼，碼字中的二進制位稱為碼元。碼字中監(jiān)視碼元數(shù)為元。碼字中監(jiān)

9、視碼元數(shù)為n-k。一個碼字中碼元的個數(shù)稱為碼。一個碼字中碼元的個數(shù)稱為碼字的長度，簡稱為碼長，通常用字的長度，簡稱為碼長，通常用n表示。如碼字表示。如碼字“11011， 碼碼長長n=5。碼字中。碼字中“1碼元的數(shù)目稱為碼字的分量，簡稱為碼重，碼元的數(shù)目稱為碼字的分量，簡稱為碼重，通常用通常用W表示。如碼字表示。如碼字“11011， 碼重碼重W=4。第10章信道編碼 兩個等長碼字之間對應(yīng)碼元不同的數(shù)目稱為這兩個碼字的漢明間隔，簡稱為碼距，通常用d表示。如碼字“11011和“00101之間有四個對應(yīng)碼元不同，故碼距d=4。由于兩個碼字模2相加，對應(yīng)碼元不同的位必為1，對應(yīng)碼元一樣的位必為0，所以兩

10、個碼字模2相加得到的新碼組的分量就是這兩個碼字之間的間隔。如： 1101100101=11110，11110的碼重為4，與上述所得到的碼距一樣。碼字集合中兩兩碼字之間間隔的最小值稱為碼的最小間隔，通常用d0表示，它決議了一個碼的糾、檢錯才干，因此是極重要的參數(shù)。第10章信道編碼 信息碼元數(shù)與碼長之比定義為編碼效率，通常用表示， 的表達式為 (10-2-1)編碼效率是衡量碼性能的又一個重要參數(shù)。編碼效果越高，傳信率越高，但此時糾、檢錯才干要降低，當(dāng)=1時就沒有糾、檢錯才干了。nk第10章信道編碼 10.2.3 最小碼距最小碼距d0與碼的糾、檢錯才干之間的關(guān)系與碼的糾、檢錯才干之間的關(guān)系最小碼距最

11、小碼距d0決議了碼的糾、檢錯才干。它們之間的關(guān)系決議了碼的糾、檢錯才干。它們之間的關(guān)系如下：如下：(1) 檢測檢測e個錯誤，那么要求最小碼距為個錯誤，那么要求最小碼距為d0e+1 (10-2-2)(2) 糾正糾正t個錯誤，那么要求最小碼距為個錯誤，那么要求最小碼距為d02t+1 (10-2-3)(3) 糾正糾正t個錯誤的同時檢測個錯誤的同時檢測e(et)個錯誤，那么要求最小個錯誤，那么要求最小碼距為碼距為d0t+e+1(10-2-4)第10章信道編碼 下面舉例闡明給定碼距時，如何根據(jù)式(10-2-2)、(10-2-3)及(10-2-4)來確定碼的糾、檢錯才干。仍以發(fā)送端發(fā)送A、B兩種音訊為例，

12、信源編碼用“1表示音訊A，用“0表示音訊B。信道編碼器每收到一個“1，輸出一個碼字“1111； 每收到一個“0，輸出一個碼字“0000。顯然，每個碼字中一個碼元是信息，另三個碼元是監(jiān)視元，這個碼共有兩個碼字，這兩個碼字間的間隔就是碼的最小間隔，所以這個碼的最小碼距d0=4。第10章信道編碼 當(dāng)此碼只用于檢錯目的時，那么根據(jù)式(10-2-2)， d03+1，所以此碼最多可檢測出3個錯誤。如“1111中發(fā)生3位錯誤變成“0001、“0010、“0100、或“1000，由于發(fā)送碼字中無這四個碼字，所以接納端能發(fā)現(xiàn)錯誤。但它無法發(fā)現(xiàn)大于3個的錯誤，如發(fā)生4個錯誤時，發(fā)送“1111時會收到“0000，由

13、于“0000也是能夠發(fā)送的碼字，接納端收到“0000時以為沒有錯誤，發(fā)送的是音訊B。第10章信道編碼 當(dāng)此碼只用于糾錯時，那么根據(jù)式(10-2-3)， d021+1，所以此碼只能糾正1位錯誤。如發(fā)送端發(fā)送“1111，傳輸中發(fā)生一位錯誤，錯成“1110、“1101、“1011或“0111，由于這些碼字與“1111的間隔小，接納端將它們復(fù)原為“1111，這樣，接納碼字中的1位錯誤得到糾正。假設(shè)傳輸過程中發(fā)生2位錯誤，如“1111錯成“1100，接納端只知道有錯，但無法知道是“1111錯成“1100還是“0000錯成“1100，所以無法糾正錯誤。第10章信道編碼 當(dāng)此碼用于同時進展糾錯和檢錯的系統(tǒng)時

14、，根據(jù)式(10-2-4)， d01+2+1，所以此碼糾1位錯誤的同時能檢測2位錯誤。假設(shè)此碼中發(fā)生1位錯誤，如“1111錯成“1110，接納端將糾正成“1111，這1位錯誤得到糾正。假設(shè)碼中發(fā)生2位錯誤，如“1111錯成“1100，接納端能發(fā)現(xiàn)錯誤，但無法糾正。假設(shè)碼中發(fā)生3位錯誤，如“1111錯成“0001，由于系統(tǒng)有糾錯功能，因此這種情況發(fā)生時，系統(tǒng)以為“0001中有1位錯誤，將“0001自動糾成“0000，所以系統(tǒng)無法發(fā)現(xiàn)3位錯誤?？梢姡a距為4的碼用于糾錯的同時檢錯，發(fā)現(xiàn)不了3位錯誤，與只用于檢錯這種情況是不一樣的，這一點請讀者仔細(xì)領(lǐng)會。第10章信道編碼 10.2.4 信道編碼的分類信

15、道編碼的分類信道編碼有許多分類方法。信道編碼有許多分類方法。(1) 根據(jù)信息碼元和附加的監(jiān)視碼元之間的關(guān)系可以分為根據(jù)信息碼元和附加的監(jiān)視碼元之間的關(guān)系可以分為線性碼和非線性碼。假設(shè)監(jiān)視碼元與信息碼元之間的關(guān)系可線性碼和非線性碼。假設(shè)監(jiān)視碼元與信息碼元之間的關(guān)系可用線性方程來表示，即監(jiān)視碼元是信息碼元的線性組合，那用線性方程來表示，即監(jiān)視碼元是信息碼元的線性組合，那么稱為線性碼。反之，假設(shè)兩者不存在線性關(guān)系，那么稱為么稱為線性碼。反之，假設(shè)兩者不存在線性關(guān)系，那么稱為非線性碼。非線性碼。(2) 根據(jù)上述關(guān)系涉及的范圍來分，可分為分組碼及卷積根據(jù)上述關(guān)系涉及的范圍來分，可分為分組碼及卷積碼。分組

16、碼的各碼元僅與本組的信息碼元有關(guān)；卷積碼中的碼。分組碼的各碼元僅與本組的信息碼元有關(guān)；卷積碼中的碼元不僅與本組信息碼元有關(guān)，而且還與前面假設(shè)干組的信碼元不僅與本組信息碼元有關(guān)，而且還與前面假設(shè)干組的信息碼元有關(guān)，因此卷積碼又稱為連環(huán)碼。線性分組碼中，把息碼元有關(guān)，因此卷積碼又稱為連環(huán)碼。線性分組碼中，把具有循環(huán)移位特性的碼稱為循環(huán)碼，否那么稱為非循環(huán)碼。具有循環(huán)移位特性的碼稱為循環(huán)碼，否那么稱為非循環(huán)碼。(3) 根據(jù)碼字中信息碼元在編碼前后能否一樣可分為系統(tǒng)根據(jù)碼字中信息碼元在編碼前后能否一樣可分為系統(tǒng)碼和非系統(tǒng)碼。編碼前后信息碼元堅持原樣不變的稱為系統(tǒng)碼和非系統(tǒng)碼。編碼前后信息碼元堅持原樣不

17、變的稱為系統(tǒng)碼，反之稱為非系統(tǒng)碼。碼，反之稱為非系統(tǒng)碼。第10章信道編碼 (4) 根據(jù)碼的用途可分為檢錯碼和糾錯碼。以檢測(發(fā)現(xiàn))錯誤為目的的碼稱為檢錯碼。以糾正錯誤為目的的碼稱為糾錯碼。糾錯碼一定能檢錯，但檢錯碼不一定能糾錯。通常將糾、檢錯碼統(tǒng)稱為糾錯碼。(5) 根據(jù)糾(檢)錯誤的類型可分為糾(檢)隨機錯誤碼、糾(檢)突發(fā)錯誤碼和既能糾(檢)隨機錯誤同時又能糾(檢)突發(fā)錯誤碼。(6) 根據(jù)碼元取值的進制可分為二進制碼和多進制碼。本章僅引見二進制碼。第10章信道編碼 10.2.5 過失控制方式過失控制方式常用的過失控制方式主要有三種：前向糾錯常用的過失控制方式主要有三種：前向糾錯(FEC)、檢

18、錯、檢錯重發(fā)重發(fā)(ARQ)和混合糾錯和混合糾錯(HEC)。它們所對應(yīng)的過失控制系統(tǒng)如。它們所對應(yīng)的過失控制系統(tǒng)如圖圖10.2.1所示。所示。第10章信道編碼 圖10.2.1 三種主要的過失控制方式第10章信道編碼 前向糾錯記作FEC，又稱自動糾錯。在這種系統(tǒng)中，發(fā)端發(fā)送糾錯碼，收端譯碼器自動發(fā)現(xiàn)并糾正錯誤。ARQ的特點是不需求反向信道，實時性好，ARQ適宜于要務(wù)虛時傳輸信號的系統(tǒng)，但編碼、譯碼電路相對較復(fù)雜。檢錯重發(fā)記作ARQ，又叫自動懇求重發(fā)。在這種系統(tǒng)中，發(fā)端發(fā)送檢錯碼，經(jīng)過正向信道送到收端，收端譯碼器檢測收到的碼字中有無錯誤。假設(shè)接納碼字中無錯誤，那么向發(fā)送端發(fā)送確認(rèn)信號ACK，通知發(fā)送

19、端此碼字已正確接納； 假設(shè)收到的碼字中有錯誤，收端不向發(fā)送端發(fā)送確認(rèn)信號ACK，發(fā)送端等待一段時間后再次發(fā)送此碼字，不斷到正確接納為止。ARQ的特點是需求反向信道，編、譯碼設(shè)備簡單。ARQ適宜于不要務(wù)虛時傳輸?shù)笳`碼率很低的數(shù)據(jù)傳輸系統(tǒng)。第10章信道編碼 混合糾錯記作HEC，是FEC與ARQ的混合。發(fā)端發(fā)送糾、檢錯碼(糾錯的同時檢錯)，經(jīng)過正向信道送到收端，收端對錯誤能糾正的就自動糾正，糾正不了時就等待發(fā)送端重發(fā)。HEC同時具有FEC的高傳輸效率，ARQ的低誤碼率及編碼、譯碼設(shè)備簡單等優(yōu)點。但HEC需求反向信道，實時性差，所以不適宜于實時傳輸信號。第10章信道編碼 10.3 常用檢錯碼常用檢

20、錯碼10.3.1 奇偶監(jiān)視碼奇偶監(jiān)視碼奇偶監(jiān)視碼是一種最簡單也是最根本的檢奇偶監(jiān)視碼是一種最簡單也是最根本的檢錯碼，又稱為奇偶校驗碼。其編碼方法是把信錯碼，又稱為奇偶校驗碼。其編碼方法是把信息碼元先分組，然后在每組的最后加息碼元先分組，然后在每組的最后加1位監(jiān)視位監(jiān)視碼元，使該碼字中碼元，使該碼字中“1的數(shù)目為奇數(shù)或偶數(shù)，的數(shù)目為奇數(shù)或偶數(shù)，奇數(shù)時稱為奇監(jiān)視碼，偶數(shù)時稱為偶監(jiān)視碼。奇數(shù)時稱為奇監(jiān)視碼，偶數(shù)時稱為偶監(jiān)視碼。信息碼元長度為信息碼元長度為3時的奇監(jiān)視碼和偶監(jiān)視碼如時的奇監(jiān)視碼和偶監(jiān)視碼如表表10-3-1所示。所示。第10章信道編碼 第10章信道編碼 奇偶監(jiān)視碼的譯碼也很簡單。譯碼器檢

21、查接納碼字中“1的個數(shù)能否符合編碼時的規(guī)律。如奇監(jiān)視碼，接納碼字中“1的個數(shù)為奇數(shù)，假設(shè)“1的個數(shù)符合編碼時的規(guī)律，那么譯碼器以為接納碼字沒有錯誤； 如“1的個數(shù)為偶數(shù)，不符合編碼時的規(guī)律，那么譯碼器以為接納碼字中有錯誤。不難看出，這種奇偶監(jiān)視碼只能發(fā)現(xiàn)單個和奇數(shù)個錯誤，而不能檢測出偶數(shù)個錯誤，因此它的檢錯才干不高。但是由于該碼的編、譯碼方法簡單，而且在很多實踐系統(tǒng)中，碼字中發(fā)生單個錯誤的能夠性比發(fā)生多個錯誤的能夠性大得多，所以奇偶監(jiān)視碼得到廣泛運用。第10章信道編碼 10.3.2 行列奇偶監(jiān)視碼行列奇偶監(jiān)視碼行列奇偶監(jiān)視碼又稱二維奇偶監(jiān)視碼或矩陣碼。編碼時首行列奇偶監(jiān)視碼又稱二維奇偶監(jiān)視碼或

22、矩陣碼。編碼時首先將信息排成一個矩陣，然后對每一行、每一列分別進展奇或先將信息排成一個矩陣，然后對每一行、每一列分別進展奇或偶監(jiān)視編碼。編碼完成后可以逐行傳輸，也可以逐列傳輸。譯偶監(jiān)視編碼。編碼完成后可以逐行傳輸，也可以逐列傳輸。譯碼時分別檢查各行、各列的奇偶監(jiān)視關(guān)系，判別能否有錯。一碼時分別檢查各行、各列的奇偶監(jiān)視關(guān)系，判別能否有錯。一個行列監(jiān)視碼字的例子如下所示：個行列監(jiān)視碼字的例子如下所示：監(jiān)視碼元監(jiān)視碼元(奇監(jiān)視奇監(jiān)視)11 0 0 1 00 1 0 1 0 10 0 0 0 1 01 1 1 1 1 0監(jiān)視碼元監(jiān)視碼元(奇監(jiān)視奇監(jiān)視) 1 0 0 1 0 0第10章信道編碼 行列監(jiān)視

23、碼字的右下角這個碼元可以對行進展監(jiān)視，也可以對列進展監(jiān)視，甚至可以對整個碼字進展監(jiān)視，本例中此碼元對列進展奇監(jiān)視。行列監(jiān)視碼具有較強的檢測隨機錯誤的才干，能發(fā)現(xiàn)1、2、3及其它奇數(shù)個錯誤，也能發(fā)現(xiàn)大部分偶數(shù)個錯誤，但分布在矩形的四個項點上的偶數(shù)個錯誤無法發(fā)現(xiàn)。這種碼還能發(fā)現(xiàn)長度不大于行數(shù)或列數(shù)的突發(fā)錯誤。這種碼也能糾正單個錯誤或僅在一行中的奇數(shù)個錯誤，由于這些錯誤的位置是可以由行、列監(jiān)視而確定的。第10章信道編碼 10.3.3 恒比碼恒比碼恒比碼又稱為等重碼或等比碼。這種碼的碼字中恒比碼又稱為等重碼或等比碼。這種碼的碼字中“1和和“0的位數(shù)堅持恒定的比例。由于每個碼字的長度是一樣的，的位數(shù)堅持

24、恒定的比例。由于每個碼字的長度是一樣的，假設(shè)假設(shè)“1、“0恒比，那么碼字必等重。這種碼在收端進展恒比，那么碼字必等重。這種碼在收端進展檢測時，只需檢測碼字中檢測時，只需檢測碼字中“1的個數(shù)能否與規(guī)定的一樣，就的個數(shù)能否與規(guī)定的一樣，就可判別有無錯誤?？膳袆e有無錯誤。我們國家郵電部門采用的五單位數(shù)字維護電碼，是一種我們國家郵電部門采用的五單位數(shù)字維護電碼，是一種“1、“0個數(shù)之比為個數(shù)之比為3 2的恒比碼。此碼有的恒比碼。此碼有10個碼字，恰個碼字，恰好可用來表示好可用來表示10個阿拉伯?dāng)?shù)字，如表個阿拉伯?dāng)?shù)字，如表10-3-2所示。所示。第10章信道編碼 第10章信道編碼 10.4 線性分組碼線

25、性分組碼10.4.1 線性分組碼的特點線性分組碼的特點既是線性碼又是分組碼的碼稱為線性分組既是線性碼又是分組碼的碼稱為線性分組碼。由碼的分類我們知道，監(jiān)視碼元僅與本組碼。由碼的分類我們知道，監(jiān)視碼元僅與本組信息碼元有關(guān)的碼稱為分組碼，監(jiān)視碼元與信信息碼元有關(guān)的碼稱為分組碼，監(jiān)視碼元與信息碼元之間的關(guān)系可以用線性方程表示的碼稱息碼元之間的關(guān)系可以用線性方程表示的碼稱為線性碼。所以，在線性分組碼中，一個碼字為線性碼。所以，在線性分組碼中，一個碼字中的監(jiān)視碼元只與本碼字中的信息碼元有關(guān)，中的監(jiān)視碼元只與本碼字中的信息碼元有關(guān)，而且這種關(guān)系可以用線性方程來表示。如而且這種關(guān)系可以用線性方程來表示。如(

26、7，3)分組碼，碼字長度為分組碼，碼字長度為7，一個碼字內(nèi)信息碼，一個碼字內(nèi)信息碼元數(shù)為元數(shù)為3，監(jiān)視碼元數(shù)為，監(jiān)視碼元數(shù)為4。碼字用。碼字用A=a6a5a4a3a2a1a0表示，前三位表示信息碼表示，前三位表示信息碼元，后四位表示監(jiān)視碼元，監(jiān)視碼元與信息碼元，后四位表示監(jiān)視碼元，監(jiān)視碼元與信息碼元之間的關(guān)系可用如下方程組表示：元之間的關(guān)系可用如下方程組表示：第10章信道編碼 4505614562463aaaaaaaaaaaaa(10-4-1)第10章信道編碼 顯然，當(dāng)三位信息碼元a6a5a4給定時，根據(jù)式(10-4-1)即可計算出四位監(jiān)視碼元a3a2a1a0，然后由這7位構(gòu)成一個碼字輸出。所

27、以編碼器的任務(wù)就是根據(jù)收到的信息碼元，按編碼規(guī)那么計算監(jiān)視碼元，然后將由信息碼元和監(jiān)視碼元構(gòu)成的碼字輸出。由編碼規(guī)那么(10-4-1)得到的(7，3)線性分組碼的全部碼字列于表10-4-1中。讀者可根據(jù)式(10-4-1)自行計算監(jiān)視碼元加以驗證。需求闡明的是，式(10-4-1)中的“+是模2加，以后不再另行闡明。第10章信道編碼 線性分組碼有一個重要特點：封鎖性。利用這一特點可方便地求出線性分組碼的最小碼距，進而可確定線性分組碼的糾、檢錯才干。線性分組碼的封鎖性是指：碼字集中恣意兩個碼字對應(yīng)位模2加后，得到的碼字依然是該碼字集中的一個碼字。如表10-4-1中，碼字“0011101和碼字“111

28、0100對應(yīng)位模2加得“1101001，“1101001是表10-4-1中的6號碼字。由于兩個碼字模2加所得的碼字的分量等于這兩個碼字的間隔，故(n, k)線性分組碼中兩個碼字之間的碼距一定等于該分組碼中某一非全0碼字的分量。因此，線性分組碼的最小碼距必等于碼字集中非全0碼字的最小分量。線性分組碼中一定有全0碼字，設(shè)全0碼字為A0，那么線性分組碼(n, k) 的最小碼距為d0=Wmin(Ai) Ai(n, k), i0 (10-4-2)第10章信道編碼 第10章信道編碼 一個碼字集的最小碼距決議了這個碼的糾、檢錯才干，線性分組碼的封鎖性給碼距的求解帶來了便利。利用式(10-4-2)可方便地求出

29、上述(7，3)分組碼的碼距，詳細(xì)方法是：全0碼字除外，求出余下7個碼字的分量，由于7個碼字的分量都等于4，所以最小分量等于4，最小碼距d0=4。此(7，3)分組碼用于檢錯，最多能檢3個錯誤，用于糾錯，那么最多能糾1個錯誤。對線性分組有了普通性了解后，下面我們系統(tǒng)討論線性分組碼的編碼、譯碼方法。第10章信道編碼 10.4.2 線性分組碼的編碼線性分組碼的編碼下面我們?nèi)砸陨鲜鱿旅嫖覀內(nèi)砸陨鲜?7，3)線性分組碼為例，用矩陣實際來線性分組碼為例，用矩陣實際來討論線性分組碼的編碼過程，并得到兩個重要的矩陣：生成矩討論線性分組碼的編碼過程，并得到兩個重要的矩陣：生成矩陣陣G和監(jiān)視矩陣和監(jiān)視矩陣H。式式(

30、10-4-1)所示監(jiān)視方程組可改寫為所示監(jiān)視方程組可改寫為(10-4-3)00000451562456346aaaaaaaaaaaaa第10章信道編碼 寫成矩陣方式有簡記為 (10-4-4)或(10-4-5)0000 10001100100011001011100011010123456aaaaaaaTTAH00THA第10章信道編碼 其中，AT是碼字A的轉(zhuǎn)置，0T是0=0 0 0 0的轉(zhuǎn)置， HT是H的轉(zhuǎn)置， H為 (10-4-6)式(10-4-6)稱為此(7,3)分組碼的監(jiān)視矩陣。(n, k)線性分組碼的監(jiān)視矩陣H由r行n列組成，且這r行是線性無關(guān)的。系統(tǒng)碼的監(jiān)視矩陣可寫成如下方式H=PI

31、r1000110010001100101110001101H第10章信道編碼 這樣的監(jiān)視矩陣稱為典型監(jiān)視矩陣。其中Ir為rr的單位矩陣。 P是rk的矩陣。對式(10-4-6)有1000010000100001 110011111101rIP第10章信道編碼 假設(shè)信息碼元知，可經(jīng)過以下矩陣運算求監(jiān)視元： (10-4-7)或由信息碼元和監(jiān)視碼元即可構(gòu)成碼字A=a6a5a4a3 a2a1a0。讀者可根據(jù)這種方法求出此(7，3)碼的全部碼字，并與表10-4-1所列碼字進展比較。4560123aaaPaaaa TPaaaaaaa4560123第10章信道編碼 還可以用生成矩陣來求碼字。系統(tǒng)碼(n, k)

32、的生成矩陣為G=IkPT(10-4-8)G稱為典型生成矩陣。其中，Ik是kk的單位矩陣。顯然，生成矩陣G可以由監(jiān)視矩陣H確定。因此，與式(10-4-6)相對應(yīng)的生成矩陣為(10-4-9)101110011100100111001G第10章信道編碼 當(dāng)信息給定時，由生成矩陣求碼字的方法是A=MG (10-4-10)其中，M為信息矩陣。如M=0 0 1時，經(jīng)過生成矩陣G生成的碼字為改動信息矩陣M可求出(7，3)碼的全部碼字，它們與表10-4-1所列碼字完全一樣。1011100101110011100100111001001A第10章信道編碼 例10.4.1 漢明碼是一種高效率的糾單個錯誤的線性分組

33、碼。其特點是最小碼距d0=3， 碼長n與監(jiān)視碼元個數(shù)r滿足關(guān)系式n=2r-1(10-4-11)其中，r3。所以有(7，4)、(15，11)、(31，26)等漢明碼。設(shè)(7，4)漢明碼的3個監(jiān)視碼元與4個信息碼元之間的關(guān)系如下(10-4-12)試求(7，4)漢明碼的全部碼字。000034613562456aaaaaaaaaaaa第10章信道編碼 解 我們用式(10-4-10)來求碼字。首先求出(7，4)漢明碼的典型生成矩陣G。由式(10-4-12)給定的監(jiān)視關(guān)系求出監(jiān)視矩陣如下所以3100110101010110010111PIH110110110111P第10章信道編碼 根據(jù)式(10-4-8)

34、得到典型生成矩陣G為根據(jù)式(10-4-10)，當(dāng)信息矩陣M=0 0 0 0時，碼字為1101000101010001100101110001G000000011010001010100011001011100010000第10章信道編碼 當(dāng)信息矩陣M=0 0 0 1時，碼字為按此方法求出(7，4)漢明碼的一切16個碼字并列于表10-4-2中。110100011010001010100011001011100011000第10章信道編碼 第10章信道編碼 根據(jù)表10-4-2，除全“0碼字以外，分量最輕的碼字的分量為3，所以(7，4)漢明碼的最小碼距d0=3。(7，4)漢明碼能糾1位錯誤，能檢2位

35、錯誤。例10.4.2 反復(fù)碼是最簡單的一類線性分組碼。詳細(xì)地說，反復(fù)碼是將1位信息編碼成n位都一樣的碼字，用(n, 1)表示。由于這類碼字中只需1位信息，一切總共只需2個碼字，一個是全“0碼字，另一個是全“1碼字。如(5，1)反復(fù)碼的兩個碼字為：“00000和“11111。試求出(5，1)反復(fù)碼的監(jiān)視矩陣H和生成矩陣G。第10章信道編碼 解 (5，1)反復(fù)碼的碼字長度為5，其中1位信息碼元，4位監(jiān)視碼元，4位監(jiān)視碼元都與信息碼元一樣，所以監(jiān)視關(guān)系(方程組)如下(10-4-13) 40414243aaaaaaaa第10章信道編碼 改寫式(10-4-13)所示的監(jiān)視方程組得(10-4-14)000

36、004142434aaaaaaaa第10章信道編碼 將式(10-4-14)用矩陣表示為00001000101001001010001101234aaaaa第10章信道編碼 所以，(5，1)反復(fù)碼的監(jiān)視矩陣為其中410001010010010100011PIH1111P第10章信道編碼 由于典型生成矩陣G為G=PTIk所以(5，1)反復(fù)碼的典型生成矩陣為 111111IPIPGTkT第10章信道編碼 例10.4.3 奇、偶監(jiān)視碼是另一類簡單的線性分組碼，用(n, n-1)表示，長度為n的碼字中信息碼元為n-1個，只需1位監(jiān)視碼元。求長度為4的偶監(jiān)視碼的監(jiān)視矩陣H和生成矩陣G。解 設(shè)長度為4的偶監(jiān)

37、視碼的碼字為A=a3a2a1a0，其中前3位表示信息碼元，最后1位表示監(jiān)視碼元。由于偶監(jiān)視碼要求碼字中“1的碼元數(shù)為偶數(shù)，即各碼元模2加為0，所以(4，3)偶監(jiān)視碼中監(jiān)視碼元與信息碼元滿足如下關(guān)系00123aaaa第10章信道編碼 此方程用矩陣表示為所以監(jiān)視矩陣為H=1 1 1 1=PI1其中P=1 1 1 0 11110123aaaa第10章信道編碼 得典型生成矩陣為利用生成矩陣G及式(10-4-10)可求出全部8個碼字，所求得碼字與表10-3-1中所列的偶監(jiān)視碼碼字完全一樣，讀者可自行加以驗證。1100101010013TPIG第10章信道編碼 10.4.3 線性分組碼的譯碼線性分組碼的譯

38、碼設(shè)發(fā)送端發(fā)送碼字設(shè)發(fā)送端發(fā)送碼字A=an-1an-2a1a0，此碼字在傳，此碼字在傳輸中能夠由于干擾引入錯誤，故接納碼字普通說來與輸中能夠由于干擾引入錯誤，故接納碼字普通說來與A不一不一定一樣。設(shè)接納碼字定一樣。設(shè)接納碼字B=bn-1bn-2b1b0，那么發(fā)送碼，那么發(fā)送碼字和接納碼字之差為字和接納碼字之差為B-A=E，或?qū)懗桑驅(qū)懗葿=A+E。 E是碼字是碼字A在在傳輸中產(chǎn)生的錯碼矩陣，傳輸中產(chǎn)生的錯碼矩陣，E=en-1en-2e1e0。 假設(shè)假設(shè)A在傳輸過程中第在傳輸過程中第i位發(fā)生錯誤，那么位發(fā)生錯誤，那么ei=1，反之，反之，那么那么ei=0。例如，假設(shè)發(fā)送碼字。例如，假設(shè)發(fā)送碼字A

39、=1001110，接納碼字，接納碼字B=1001100，那么錯碼矩陣，那么錯碼矩陣E=0000010。錯碼矩陣。錯碼矩陣通常稱為錯誤圖樣。通常稱為錯誤圖樣。第10章信道編碼 譯碼器的義務(wù)就是判別接納碼字B中能否有錯，假設(shè)有錯，那么設(shè)法確定錯誤位置并加以糾正，以恢復(fù)發(fā)送碼字A。由式(10-4-5)可知，碼字A與監(jiān)視矩陣H有如下約束關(guān)系A(chǔ)HT=0當(dāng)B=A時，有BHT=00為1行r列的全“0矩陣。第10章信道編碼 當(dāng)BA時，闡明傳輸過程中發(fā)生了錯誤，此時令矩陣S=BHT=EHT (10-4-15)稱S為伴隨式，伴隨式S是個1行r列的矩陣， r是線性分組碼中監(jiān)視碼元的個數(shù)。由上面的分析可知，當(dāng)接納碼字

40、無錯誤時，S=0；當(dāng)接納碼字有錯誤時，S0。又由式(10-4-15)可知， S與錯誤圖樣有對應(yīng)關(guān)系，與發(fā)送碼字無關(guān)。故S能確定傳輸中能否發(fā)生了錯誤及錯誤的位置。0)(TTTTTHEHEHAHEAHB第10章信道編碼 下面以上一節(jié)中所列舉的(7，3)碼為例，詳細(xì)闡明線性分組碼的譯碼過程。(1) 首先根據(jù)式(10-4-15)求出錯誤圖樣E與伴隨式S之間的關(guān)系，并把它保管在譯碼器中。由(7，3)線性分組碼編碼一節(jié)可知，此碼最小碼距d0=4，能糾正碼字中恣意一位錯誤，碼長為7的碼字中錯1位的情況有7種，即碼字中錯1位的錯誤圖樣有7種，如碼字第一位發(fā)生錯誤，錯誤圖樣為E=1000000第10章信道編碼

41、由式(10-4-15)求得伴隨式為由上式可看出，伴隨式S6等于HT中的第一行。1110100001000010000110111110011110000006THES第10章信道編碼 如碼字在傳輸過程中第二位發(fā)生錯誤，錯誤圖樣為E=0 1 0 0 0 0 0那么伴隨式為即伴隨式S5等于HT中的第二行。0111100001000010000110111110011101000005THES第10章信道編碼 由此可求出錯1位的7種錯誤圖樣所對應(yīng)的伴隨式，它們剛好對應(yīng)HT中的7行。錯誤圖樣與伴隨式之間的對應(yīng)關(guān)系如表10-4-3所示。第10章信道編碼 第10章信道編碼 (2) 當(dāng)譯碼器任務(wù)時，首先計算

42、接納碼字B的伴隨式S，然后查表10-4-3得錯誤圖樣E。如接納碼字為B=1100111，用式(10-4-15)求出其伴隨式為根據(jù)此伴隨式，查表10-4-3得錯誤圖樣E=1000000，可知接納碼字B中第一位有錯誤。 0111010000100001000011011111001111100111THBS第10章信道編碼 (3) 最后用錯誤圖樣糾正接納碼字中的錯誤。根據(jù)接納碼字B及錯誤圖樣E即可得到發(fā)送碼字A，方法是A=B+E=1 1 0 0 1 1 1+1 0 0 0 0 0 0=0100111假設(shè)此(7，3)分組碼用于檢錯，碼距d0=4的(7，3)分組碼最多能檢3位錯誤。檢錯譯碼的方法是：計

43、算接納碼字的伴隨式S，假設(shè)S=0，譯碼器以為接納碼字中沒有錯誤；假設(shè)S0，那么譯碼器以為接納碼字中有錯誤，譯碼器會以某種方式將此信息反響給發(fā)送端，發(fā)送端將重發(fā)此碼字。第10章信道編碼 最后還要指出，假設(shè)接納碼字中錯誤位數(shù)超越1時， S也有能夠正好與發(fā)生1位錯誤時的某個伴隨式一樣，這樣，經(jīng)糾錯后反而“越糾越錯。如發(fā)送碼字A=0100111，傳輸過程中發(fā)生3位錯誤，設(shè)錯誤圖樣E=0000111，此時接納碼字B=0100000。根據(jù)上述所引見的糾錯譯碼方法，計算出此接納碼字的伴隨式S=0111，查表10-4-3得錯誤圖樣E=0100000，譯碼器以為第二位發(fā)生了錯誤，將第二位糾正，得糾正后的碼字為0

44、000000。由此可見，本來接納碼字中有3位錯誤，但經(jīng)過糾錯譯碼后，錯誤不但沒有減少反而添加了1位，這就所謂的“越糾越錯。 第10章信道編碼 在傳輸過程中，也會發(fā)生發(fā)送碼字的某幾位發(fā)生錯誤后成為另一發(fā)送碼字的情況，這種情況收端也無法檢測，這種錯誤我們稱之為不可檢測的錯誤。從統(tǒng)計觀念來看，這種情況出現(xiàn)的概率很小。如發(fā)送碼字A=0100111，傳輸過程中發(fā)生4位錯誤變成B=0111010，計算其伴隨式發(fā)現(xiàn)S=0，譯碼器以為沒錯?，F(xiàn)實上，接納到的B是另一個發(fā)送碼字。不論是這種情況還是上述的“越糾越錯，發(fā)生緣由都是由于碼字中的錯誤個數(shù)超出了碼的糾錯才干。所以在設(shè)計信道編碼方案時，應(yīng)充分思索信道發(fā)生錯誤

45、的情況。第10章信道編碼 例10.4.4 (例10.4.1續(xù))(7，4)漢明碼的譯碼。解例10.4.1中(7，4)漢明碼的監(jiān)視矩陣為由例10.4.1知，(7，4)漢明碼的碼距d0=3，能糾正1個錯誤。碼長為7的碼字錯1位的錯誤圖樣有7種，利用式(10-4-15)可求出這7種錯誤圖樣所對應(yīng)的伴隨式。對應(yīng)關(guān)系如表10-4-4所示。100110101010110010111H第10章信道編碼 第10章信道編碼 由表10-4-4可知， HT中的每一行都是一個伴隨式。由于(7，4)漢明碼中監(jiān)視碼元的個數(shù)為3，所以伴隨式是個1行3列的矩陣。三位二進制不同的組合共有8種，除全“0組合外還有7種，這7種組合剛

46、好與錯1位的7種錯誤圖樣一一對應(yīng)。所以，碼長為7的碼字中至少參與3位監(jiān)視碼元才干糾單個錯誤。(7，4)漢明碼在7位碼字中只需3位監(jiān)視碼元，因此，(7，4)碼是一種糾單個錯誤的高效的線性分組碼。第10章信道編碼 7種錯誤圖樣與7個伴隨式之間的關(guān)系只需一一對應(yīng)就不會影響碼的糾、檢錯才干。所以，我們也可改動表10-4-4的對應(yīng)關(guān)系，進而得到不同于例10.4.1中的HT，即得到不同于例10.4.1中(7，4)漢明碼的監(jiān)視關(guān)系。如改動表10-4-4中的對應(yīng)關(guān)系得到100010001111110011101TH第10章信道編碼 所以，監(jiān)視矩陣為100110101011100011011H第10章信道編碼

47、由 ,得到另一個(7，4)漢明碼的監(jiān)視關(guān)系方程組為0000123456aaaaaaaH000034613452356aaaaaaaaaaaa第10章信道編碼 按此方法還可構(gòu)造出不同的(7，4)漢明碼的監(jiān)視關(guān)系。我們知道，監(jiān)視關(guān)系不同，碼字集中的碼字也會不同，但按這種方法構(gòu)造的一切(7，4)漢明碼具有一樣的性能，即編碼效率一樣，糾、檢錯才干一樣。第10章信道編碼 例10.4.5 實驗證(5，1)反復(fù)碼最多能糾2位錯誤。解 最多能糾2位錯誤的碼必需能糾恣意位置上的單個錯誤及恣意位置上的2個錯誤。長度為5的碼字發(fā)生單個錯誤的錯誤圖樣有種，分別是515C00001 0001000100 01000 1

48、000054321EEEEE第10章信道編碼 恣意錯2位的錯誤圖樣有種，它們是1024525C0001100101 00110 0100101010 01100 1000110010 10100 110001514131211109876EEEEEEEEEE第10章信道編碼 由例10.4.2 可知(5,1)反復(fù)碼的監(jiān)視矩陣為10001010010010100011H第10章信道編碼 根據(jù)式(10-4-15)求出這15個錯誤圖樣所對應(yīng)的伴隨式，并將它們列于表10-4-5中。由表10-4-5可看到，每個錯誤圖樣對應(yīng)不同的伴隨式，所以當(dāng)碼字中錯1位或2位時，根據(jù)伴隨式即可確定錯誤圖樣，以此可糾正碼字

49、中的1位或2位錯誤。由該表還可看出，伴隨式由4位二進制組成，除全“0外的一切4位二進制組合全在表10-4-5中了，假設(shè)碼字中發(fā)生3位或4位錯誤，其伴隨式一定是該表中的一個，譯碼器會按單個錯誤或2個錯來糾錯，導(dǎo)致“越糾越錯；假設(shè)碼字中發(fā)生5位錯誤，如碼字11111錯成了00000，此時伴隨式為0000，譯碼器無法發(fā)現(xiàn)此錯誤。所以，(5，1)反復(fù)碼最多能糾2位錯誤。第10章信道編碼 第10章信道編碼 10.5 循循 環(huán)環(huán) 碼碼10.5.1 循環(huán)碼的特點循環(huán)碼的特點假設(shè)線性分組碼的任一碼字循環(huán)移位所得假設(shè)線性分組碼的任一碼字循環(huán)移位所得的碼字仍在該碼字集中，那么此線性分組碼稱的碼字仍在該碼字集中，那

50、么此線性分組碼稱為循環(huán)碼。很明顯，為循環(huán)碼。很明顯， (n, 1)反復(fù)碼是一個循環(huán)反復(fù)碼是一個循環(huán)碼。表碼。表10-5-1中的中的(7，3)碼及表碼及表10-5-2中的中的(6，3)碼也都是循環(huán)碼，其循環(huán)特性分別如圖碼也都是循環(huán)碼，其循環(huán)特性分別如圖10.5.1所示。循環(huán)圈上的數(shù)字為碼字的序號。所示。循環(huán)圈上的數(shù)字為碼字的序號。由圖由圖10.5.1可見，同一循環(huán)圈上的各碼字分量可見，同一循環(huán)圈上的各碼字分量是相等的。全是相等的。全“0、全、全“1碼字分別自成循環(huán)碼字分別自成循環(huán)圈。循環(huán)碼的循環(huán)圈數(shù)目大于等于圈。循環(huán)碼的循環(huán)圈數(shù)目大于等于2。第10章信道編碼 第10章信道編碼 第10章信道編碼

51、在討論循環(huán)碼時，常用代數(shù)多項式來表示循環(huán)碼的碼字，這種多項式稱為碼多項式。 對于(n, k)循環(huán)碼的碼字，其碼多項式的普通方式為 (10-5-1)碼字中各位碼元的數(shù)值是其碼多項式中相應(yīng)各項的系數(shù)值(0或1)。碼字A=1001110的碼多項式012211.)(axaxaxaxAnnnnxxxxxA236)(第10章信道編碼 10.5.2 循環(huán)碼的編碼循環(huán)碼的編碼循環(huán)碼完全由其碼字長度循環(huán)碼完全由其碼字長度n及生成多項式及生成多項式g(x)所決議。循所決議。循環(huán)碼中，除全環(huán)碼中，除全“0碼字外，次數(shù)最低的碼字多項式稱為生成碼字外，次數(shù)最低的碼字多項式稱為生成多項式。如多項式。如(7，3)循環(huán)碼中，

52、生成多項式為循環(huán)碼中，生成多項式為g(x)=x4+x3+x2+1 (碼字碼字0011101的碼多項式的碼多項式)?？梢宰C明，。可以證明， (n, k)循環(huán)碼的生成循環(huán)碼的生成多項式多項式g(x)具有如下三個特性：具有如下三個特性：(1) g(x)是是xn+1的一個因子。的一個因子。(2) g(x)是是r=n-k次多項式。次多項式。(3) g(x)的常數(shù)項為的常數(shù)項為1。第10章信道編碼 為了尋覓生成多項式，首先應(yīng)對xn+1進展因式分解，并選擇滿足上述(2)、(3)兩個特點的因式或因式的乘積。如尋覓(7，3)循環(huán)碼，首先對x7+1進展因式分解，有x7+1=(x+1)(x3+x+1)(x3+x2+

53、1)x+1和x3+x+1乘積為x4+x3+x2+1，此乘積可作為(7，3)循環(huán)碼的生成多項式，由于它滿足生成多項式的三個條件，所以(7，3)循環(huán)碼的一個生成多項式為g(x)=x4+x3+x2+1此生成多項式可生成表10-5-1中所列的循環(huán)碼。顯然， x+1和x3+x2+1的乘積x4+x2+x+1也滿足上述生成多項式的三個條件，所以x4+x2+x+1是(7，3)循環(huán)碼的另一個生成多項式。第10章信道編碼 用多項式來表示生成矩陣的各行，那么生成矩陣可寫成 (10-5-2)()(.)()()(21xgxxgxgxxgxxGkk第10章信道編碼 例如表10-5-1中(7，3)循環(huán)碼， n=7， k=3

54、， r=4，其生成多項式及生成矩陣分別為1)(234xxxxg1)()()()(23434524562xxxxxxxxxxxxgxxgxgxxG第10章信道編碼 即 (10-5-3)101110001011100010111G第10章信道編碼 有了生成多項式及生成矩陣后，就可求出循環(huán)碼的一切碼字了。求循環(huán)碼碼字的方法有三種： (1) 循環(huán)碼的碼字多項式都是生成多項式g(x)的倍式，設(shè)信息矩陣為M=mk-1 mk-2 m1 m0那么(n, k)循環(huán)碼的一切碼字由下式生成A(x)=M(x)g(x)(10-5-4)其中，M(x)=mk-1xk-1+mk-2xk-2+m1x+m0為信息多項式。按此方法

55、可產(chǎn)生循環(huán)碼的一切碼字，但這種方法產(chǎn)生的碼不是系統(tǒng)碼。如信息M=110，那么信息多項式為M(x)=x2+x第10章信道編碼 設(shè)生成多項式為g(x)=x4+x3+x2+1由式(10-5-4)可得碼字多項式為A(x)=(x2+x)(x4+x3+x2+1)=x6+x3+x2+x所以碼字為1001110，顯然它不是系統(tǒng)碼的碼字。 第10章信道編碼 (2) 用生成多項式也可產(chǎn)生系統(tǒng)碼的碼字，系統(tǒng)循環(huán)碼的碼多項式可表示為A(x)=xn-kM(x)+xn-kM(x) (10-5-5)其中，前一部分代表信息碼元組，后一部分用 表示，是xn-kM(x)被g(x)除得的余式，它代表監(jiān)視碼元組。如(7，3)循環(huán)碼，

56、設(shè)信息M=110，那么M(x)=x2+xxn-kM(x)=x4M(x)=x6+x5第10章信道編碼 當(dāng)g(x)=x4+x3+x2+1時，求得余式為xn-kM(x)=x4M(x)=x6+x5=x3+1根據(jù)式(10-5-5)得碼多項式為A(x)=x6+x5+x3+1此碼多項式對應(yīng)的碼字為“1101001，是系統(tǒng)碼的碼字，前三位是信息碼元，后四位是監(jiān)視碼元。第10章信道編碼 根據(jù)式(10-5-5)，利用多項式除法電路求xn-kM(x)除以g(x)的余式，即可產(chǎn)生(n, k)系統(tǒng)循環(huán)碼。g(x)=x4+x3+x2+1時，(7，3)循環(huán)碼的編碼器如圖10.5.2所示。第10章信道編碼 圖10.5.2 (

57、7，3)循環(huán)碼編碼器第10章信道編碼 D0D1D2D3是四級移位存放器，反響線的銜接與g(x)的非0系數(shù)相對應(yīng)。編碼時，首先將四級移存器清零。三位信息碼元輸入時，門1斷開，門2接通，直接輸出信息元。第3個移位脈沖后，D0D1D2D3中數(shù)據(jù)為除法余數(shù)，就是輸入信息的監(jiān)視碼元。第47次移位時，門2斷開，門1接通，輸出監(jiān)視元。當(dāng)一個碼字輸出終了就將移位存放器清零，等待下一組信息輸入后重新編碼。設(shè)輸入的信息碼元為110，圖10.5.2中各器件及端點形狀變化情況如表10-5-3所示。該編碼器輸入不同信息組時的碼字如表10-5-1所示。第10章信道編碼 第10章信道編碼 (3) 由于循環(huán)碼也是線性分組碼，

58、所以前面引見過的線性分組碼的編碼方法同樣適用于循環(huán)碼。由式 (10-5-3)所示的生成矩陣即可生成循環(huán)碼的碼字，方法如下A=MG(10-5-6)其中，M是信息矩陣。由于式(10-5-3)所示的生成矩陣不是典型生成矩陣，所以由式(10-5-6)生成的碼字不是系統(tǒng)碼的碼字。要想用生成矩陣生成系統(tǒng)碼的碼字，生成矩陣必需為典型生成矩陣。將非典型生成矩陣中的行進展一些線性變換，即可得到典型生成矩陣。如將式(10-5-3)所示矩陣中第二行加到第一行(對應(yīng)位模2加)，得生成矩陣(10-5-7)101110001011100111001G第10章信道編碼 再將式(10-5-7)中的第三行加到第二行，得典型生成

59、矩陣為 (10-5-8)其中 (10-5-9)將式(10-5-8)所示的典型生成矩陣代入式(10-5-6)，即可求得循環(huán)碼的系統(tǒng)碼字，改動式(10-5-6)中的信息矩陣可求得(7，3)循環(huán)碼的一切碼字。這個任務(wù)請讀者完成，并把所得碼字與表10-5-1所示碼字進展比較。1011100111001001110013TPIG101111100111TP第10章信道編碼 由式(10-5-9)可得循環(huán)碼的監(jiān)視矩陣H為有了監(jiān)視矩陣，就可用線性分組碼的譯碼方法對循環(huán)碼進展譯碼。所以，完全可以用前面引見的線性分組碼的編譯碼方法對循環(huán)碼進展編碼和譯碼，但這種方法沒有利用循環(huán)碼的循環(huán)移位特性。 100011001

60、00011001011100011013PIPIHr第10章信道編碼 10.5.3 循環(huán)碼的譯碼循環(huán)碼的譯碼由式由式(10-5-4)可知，發(fā)送碼字多項式可知，發(fā)送碼字多項式A(x)是生成多項式是生成多項式g(x)的倍式，換句話說，生成多項式的倍式，換句話說，生成多項式g(x) 能整除發(fā)送碼字多項式能整除發(fā)送碼字多項式A(x)。假設(shè)碼字經(jīng)信道傳輸后不發(fā)生錯誤，那么接納碼字多項。假設(shè)碼字經(jīng)信道傳輸后不發(fā)生錯誤，那么接納碼字多項式式B(x)也是生成多項式也是生成多項式g(x)的倍式，但假設(shè)碼字在傳輸過程中的倍式，但假設(shè)碼字在傳輸過程中發(fā)生錯誤，那么接納碼字多項式不再是生成多項式發(fā)生錯誤，那么接納碼字