通信原理精品課--第八章 差錯控制編碼

1、電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課通信原理通信原理主講人：吳海濤主講人：吳海濤 副教授副教授TEL:mail:第第1頁，共頁，共61頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課第第8 8章章 差錯控制編碼差錯控制編碼8.1 概述概述8.2 常用的幾種簡單分組碼常用的幾種簡單分組碼8.3 線性分組碼線性分組碼8.4 循環(huán)碼循環(huán)碼8.5 小結(jié)小結(jié)第第2頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1

2、 概述概述8.1.1 信道編碼信道編碼在數(shù)字通信中，根據(jù)不同的目的，編碼可分為在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼信源編碼和和信信道編碼道編碼。信源編碼是為了提高數(shù)字信號的有效性以及為了使。信源編碼是為了提高數(shù)字信號的有效性以及為了使模擬信號數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，模擬信號數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率， 提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號在傳輸過程提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號在傳輸過程中，加性噪聲、碼間串?dāng)_等都會產(chǎn)生誤碼。為了提高系統(tǒng)的中，加性噪聲、碼間串?dāng)_等都會產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接

3、收設(shè)備本身的噪聲，抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。碼技術(shù)。第第3頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.1 信道編碼信道編碼另外，按照噪聲或干擾的變化規(guī)律，可把信道分為三類：另外，按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機信道、突發(fā)信道和混合信道。隨機信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機信道，其中差錯的出現(xiàn)是恒參高斯白噪聲信道是典型的隨機

4、信道，其中差錯的出現(xiàn)是隨機的，而且錯誤之間是統(tǒng)計獨立的。具有脈沖干擾的信道隨機的，而且錯誤之間是統(tǒng)計獨立的。具有脈沖干擾的信道是典型的突發(fā)信道，是典型的突發(fā)信道， 錯誤是成串成群出現(xiàn)的，即在短時間內(nèi)錯誤是成串成群出現(xiàn)的，即在短時間內(nèi)出現(xiàn)大量錯誤。短波信道和對流層散射信道是混合信道的典出現(xiàn)大量錯誤。短波信道和對流層散射信道是混合信道的典型例子，隨機錯誤和成串錯誤都占有相當(dāng)比例。對于不同類型例子，隨機錯誤和成串錯誤都占有相當(dāng)比例。對于不同類型的信道，應(yīng)采用不同的差錯控制方式。型的信道，應(yīng)采用不同的差錯控制方式。 第第4頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理

5、精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.2 差錯控制方式差錯控制方式 發(fā)端糾錯碼收端前向糾錯FEC發(fā)端檢錯碼收端檢錯重發(fā)ARQ判決信號發(fā)端檢錯和糾錯碼收端混合糾錯HEC判決信號圖8-1 差錯控制方式 第第5頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.2 差錯控制方式差錯控制方式 1. 前向糾錯方式前向糾錯方式(80年代年代) 前向糾錯方式記作前向糾錯方式記作FEC (Forward Error Correction)。發(fā)。發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸端發(fā)

6、送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。在二進制碼元的情況下，能夠確定錯碼的位置，中的錯誤。在二進制碼元的情況下，能夠確定錯碼的位置，就相當(dāng)于能夠糾正錯碼。將錯碼就相當(dāng)于能夠糾正錯碼。將錯碼“0”改為改為“1”或或“1”改為改為“0”即可。其特點是單向傳輸，實時性好，但譯碼設(shè)備較復(fù)即可。其特點是單向傳輸，實時性好，但譯碼設(shè)備較復(fù)雜。雜。 第第6頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.2 差錯控制方式差錯控制方式 2. 檢錯重發(fā)方式（書上檢錯重發(fā)方式（書上3種方式）種方式） 檢錯

7、重發(fā)又稱自動請求重傳方式，記作檢錯重發(fā)又稱自動請求重傳方式，記作ARQ(Automatic Repeat reQuest)。 由發(fā)端送出能夠發(fā)現(xiàn)錯誤的碼，由收端判決傳輸中由發(fā)端送出能夠發(fā)現(xiàn)錯誤的碼，由收端判決傳輸中有無錯誤產(chǎn)生，如果發(fā)現(xiàn)錯誤，則通過反向信道把這一判決結(jié)有無錯誤產(chǎn)生，如果發(fā)現(xiàn)錯誤，則通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認為錯誤的信息再次重發(fā)，果反饋給發(fā)端，然后，發(fā)端把收端認為錯誤的信息再次重發(fā)，從而達到正確傳輸?shù)哪康摹Ｆ涮攸c是需要反饋信道，譯碼設(shè)備從而達到正確傳輸?shù)哪康摹Ｆ涮攸c是需要反饋信道，譯碼設(shè)備簡單，對突發(fā)錯誤和信道干擾較嚴重時有效，簡單，對突發(fā)錯誤和信道

8、干擾較嚴重時有效， 但實時性差，主但實時性差，主要在計算機數(shù)據(jù)通信與深空通信中得到應(yīng)用。要在計算機數(shù)據(jù)通信與深空通信中得到應(yīng)用。 第第7頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.2 差錯控制方式差錯控制方式 圖8-2 CFDP協(xié)議ARQ-延遲NAK模式 第第8頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.2 差錯控制方式差錯控制方式 3. 混合糾錯方式混合糾錯方式 混合糾錯方式記作混合糾錯方式記作HEC(

9、Hybrid Error Correction)是是FEC和和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動糾錯同時又具有檢錯方式的結(jié)合。發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力，糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力， 但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。這種方式具但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達到較低的誤碼率，因此，有自動糾錯和檢錯重發(fā)的優(yōu)點，可達到較低的誤碼率，因此， 近年來得到廣

10、泛應(yīng)用。近年來得到廣泛應(yīng)用。 第第9頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.3 糾錯碼的分類糾錯碼的分類 (1) 根據(jù)糾錯碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為根據(jù)糾錯碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。性方程式，則稱為線性碼，否則為非線性碼。(2) 根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分

11、組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。(3) 根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。 第第10頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編

12、碼的基本原理 無論是具有檢錯能力還是糾錯功能的編碼，統(tǒng)稱為糾錯編碼。無論是具有檢錯能力還是糾錯功能的編碼，統(tǒng)稱為糾錯編碼?，F(xiàn)在用一個例子說明其原理。設(shè)有一種由現(xiàn)在用一個例子說明其原理。設(shè)有一種由3 個二進制碼元構(gòu)個二進制碼元構(gòu)成的編碼，共有成的編碼，共有8種不同的可能碼組。若將其全部用來表示種不同的可能碼組。若將其全部用來表示天氣，則可以表示天氣，則可以表示8種不同的天氣。例如（種不同的天氣。例如（1）：）： 000晴晴 001云云 010陰陰 011雨雨 100雪雪 101霜霜 110霧霧 111雹雹這時，若一個碼組在傳輸中發(fā)生錯碼，則因接收端無法發(fā)現(xiàn)這時，若一個碼組在傳輸中發(fā)生錯碼，則因接

13、收端無法發(fā)現(xiàn)錯碼，而將收到錯誤信息。錯碼，而將收到錯誤信息。第第11頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 假設(shè)在此假設(shè)在此8種碼組中僅允許使用種碼組中僅允許使用4種來傳送天氣。例如（種來傳送天氣。例如（2）：）：000晴晴 011云云 101陰陰 110雨雨為許用碼組，其它為許用碼組，其它4種為禁用碼組。這時，接收端有可能發(fā)種為禁用碼組。這時，接收端有可能發(fā)現(xiàn)（檢測到）碼組中的一個錯碼。例如：若現(xiàn)（檢測到）碼組中的一個錯碼。例如：若000中有一個錯中有

14、一個錯碼，則它可能錯成碼，則它可能錯成100、010或或001。但是這。但是這3種碼組都是禁用種碼組都是禁用碼組，所以能夠發(fā)現(xiàn)錯碼。不難驗證，上面這碼組，所以能夠發(fā)現(xiàn)錯碼。不難驗證，上面這4個碼組的任個碼組的任一碼元出錯都將變成禁用碼組，所以這種編碼能發(fā)現(xiàn)一個錯一碼元出錯都將變成禁用碼組，所以這種編碼能發(fā)現(xiàn)一個錯碼。碼。第第12頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 當(dāng)當(dāng)000有有3個錯碼時，它變成個錯碼時，它變成111，也是禁用碼組，其它，也是禁用碼組

15、，其它3個碼個碼組情況也是如此。所以這種編碼也能發(fā)現(xiàn)組情況也是如此。所以這種編碼也能發(fā)現(xiàn)3個錯碼。但是它個錯碼。但是它不能發(fā)現(xiàn)不能發(fā)現(xiàn)2個錯碼，因為發(fā)生個錯碼，因為發(fā)生2個錯碼后得到的仍是許用碼組。個錯碼后得到的仍是許用碼組。這種編碼只能檢錯不能糾錯。例如，若接收到的碼組為這種編碼只能檢錯不能糾錯。例如，若接收到的碼組為100，它是禁用碼組，可以判斷其中有錯碼。若這時只有它是禁用碼組，可以判斷其中有錯碼。若這時只有1個錯碼，個錯碼，則則000、110、101這這3種許用碼錯了種許用碼錯了1個碼元后都可能變成個碼元后都可能變成100。所以不能判斷其中哪個碼組是原發(fā)送碼組，即不能糾正錯誤。所以不能

16、判斷其中哪個碼組是原發(fā)送碼組，即不能糾正錯誤。要想糾正錯誤還要增大冗余度。要想糾正錯誤還要增大冗余度。000晴晴 011云云 101陰陰 110雨雨第第13頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 例如（例如（3）規(guī)定）規(guī)定 只許用兩個碼組：只許用兩個碼組：000晴晴 111雨雨其它都是禁用碼組。這種編碼能檢測出兩個以下的錯碼，或其它都是禁用碼組。這種編碼能檢測出兩個以下的錯碼，或糾正一個錯碼。例如當(dāng)收到糾正一個錯碼。例如當(dāng)收到“100”時，若采用的是糾錯

17、技術(shù)，時，若采用的是糾錯技術(shù)，則認為它是由則認為它是由“000（晴）（晴）”中第一位出錯造成的，故糾正中第一位出錯造成的，故糾正為為“000（晴）（晴）”；若采用的是檢錯技術(shù)，它可以發(fā)現(xiàn)兩個；若采用的是檢錯技術(shù)，它可以發(fā)現(xiàn)兩個以下的錯碼，即以下的錯碼，即“000”錯一位，或錯一位，或“111”錯兩位都可能變成錯兩位都可能變成“100”，故能發(fā)現(xiàn)此碼組有錯，但是不能糾錯。從上面的例，故能發(fā)現(xiàn)此碼組有錯，但是不能糾錯。從上面的例子可以建立子可以建立“分組碼分組碼”的概念。的概念。第第14頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.

18、1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 用例（用例（2）的例子，由于）的例子，由于4種信息用種信息用2比特就能代表，現(xiàn)在為比特就能代表，現(xiàn)在為了糾錯用了了糾錯用了3比特，加了一位監(jiān)督位構(gòu)成可一個具有糾錯功比特，加了一位監(jiān)督位構(gòu)成可一個具有糾錯功能的獨立碼組，并且監(jiān)督位僅監(jiān)督本組中的信息碼元，則稱能的獨立碼組，并且監(jiān)督位僅監(jiān)督本組中的信息碼元，則稱這種編碼為這種編碼為分組碼分組碼。第第15頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理

19、 1. 分組碼分組碼分組碼一般可用分組碼一般可用(n,k)表示。其中，表示。其中，k是每組二進制信息碼元的是每組二進制信息碼元的數(shù)目，數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，分組分組碼是對每段碼是對每段k位長的信息組以一定的規(guī)則增加位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組個監(jiān)督元，組成長為成長為n的碼字。的碼字。在二進制情況下，共有在二進制情況下，共有2k個不同的信息組，個不同的信息組，相應(yīng)地可得到相應(yīng)地可得到2k個不同的碼字，稱為個不同的

20、碼字，稱為許用碼組許用碼組。其余。其余 2n-2k個個碼字未被選用，稱為碼字未被選用，稱為禁用碼組禁用碼組。 第第16頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 1. 分組碼分組碼在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量，在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量， 簡稱簡稱碼碼重重。例如，碼字。例如，碼字 10110，碼重，碼重w=3。兩個等長碼組之間對應(yīng)位取值不同的數(shù)目稱為這兩個碼組的兩個等長碼組之間對應(yīng)位取值不同的數(shù)目稱為這兩個碼組的漢明漢明(H

21、amming)距離距離， 簡稱簡稱碼距碼距。例如。例如 11000 與與 10011之間之間的距離的距離d=3。碼組集中任意兩個碼字之間距離的最小值稱為。碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用碼的最小距離，用d0表示。表示。最小碼距最小碼距是碼的一個重要參數(shù)，是碼的一個重要參數(shù)， 它是衡量碼檢錯、糾錯能力的依據(jù)。它是衡量碼檢錯、糾錯能力的依據(jù)。第第17頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 2. 檢錯和糾錯能力檢錯和糾錯能力若分組碼碼字

22、中的監(jiān)督元在信息元之后，而且是信息元的簡單若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡單重復(fù)，則稱該分組碼為重復(fù)，則稱該分組碼為重復(fù)碼重復(fù)碼。它是一種簡單實用的檢錯碼，。它是一種簡單實用的檢錯碼， 并有一定的糾錯能力。例如并有一定的糾錯能力。例如(2,1)重復(fù)碼，兩個許用碼組是重復(fù)碼，兩個許用碼組是 00 與與 11，d0=2，收端譯碼，出現(xiàn)，收端譯碼，出現(xiàn) 01、10 禁用碼組時，可以發(fā)現(xiàn)禁用碼組時，可以發(fā)現(xiàn)傳輸中的一位錯誤。如果是傳輸中的一位錯誤。如果是(3,1)重復(fù)碼，兩個許用碼組是重復(fù)碼，兩個許用碼組是 000 與與111, d0=3; 當(dāng)收端出現(xiàn)兩個或三個當(dāng)收端出現(xiàn)兩個或三個

23、 1 時，判為時，判為 1，否則判為，否則判為 0。此時，可以糾正單個錯誤，或者該碼可以檢出兩個錯誤。此時，可以糾正單個錯誤，或者該碼可以檢出兩個錯誤。 第第18頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 3.碼距的幾何意義碼距的幾何意義(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一般而言，碼距是一般而言，碼距是 n 維空間中單位正多面維空間中單位正多面體頂點間的漢明距離。體頂點

24、間的漢明距離。第第19頁，共頁，共68頁頁3位碼組位碼組3維空間頂點坐維空間頂點坐標（標（a0,a1,a2 ）各頂點之間沿立各頂點之間沿立方體各邊行走的方體各邊行走的幾何距離。幾何距離。電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 4. 糾檢錯能力糾檢錯能力一種編碼的糾檢錯能力：一種編碼的糾檢錯能力：決定于最小碼距決定于最小碼距d0的值。的值。為了能檢測為了能檢測e個錯碼，個錯碼，要求最小碼距要求最小碼距10 ed0123BA漢明距離ed0碼距等于3的兩個碼組設(shè)有一個碼組A，它位

25、于0點，若A中發(fā)生一個錯碼，則A的位置將移動到以0為中心，以1為半徑的圓上。若A中發(fā)生2個錯碼，則。因此，若最小碼距不小于3，例如圖中B點為最小碼距的碼組，則當(dāng)發(fā)生不多于兩個錯碼時，碼組A的位置就不會移動到另一個許用碼組B的位置上。P332第第20頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 4. 糾檢錯能力糾檢錯能力一種編碼的糾檢錯能力：一種編碼的糾檢錯能力：決定于最小碼距決定于最小碼距d0的值。的值。為了能糾正為了能糾正 t 個錯碼，個錯碼，要求最小碼距要

26、求最小碼距 120 tdBtA漢明距離012345td0碼距等于5的兩個碼組若A和B中的錯碼不多于兩個，其位置均不會超出以2為半徑的圓，因而不會錯到另一個碼組的范圍內(nèi)。若此編碼中任意兩個碼組之間的碼距都不小于5，則只要錯碼不超過兩個就能夠糾正。判決規(guī)則為：若接收碼組落于以A為圓心的圓上就判決收到的是碼組A，若落于以B為圓心的圓上就判決為碼組B。這樣，就能夠糾正兩位錯碼。第第21頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 4. 糾檢錯能力糾檢錯能力一種編碼的糾

27、檢錯能力：一種編碼的糾檢錯能力：決定于最小碼距決定于最小碼距d0的值。的值。為了能糾正為了能糾正t個錯碼，個錯碼，同時檢測同時檢測e個錯碼，個錯碼，要求最小碼距要求最小碼距 在解釋公式之前，先來分析上圖所示的例子。在解釋公式之前，先來分析上圖所示的例子。 )(10tetedBtA漢明距離012345td0第第22頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 4. 糾檢錯能力糾檢錯能力BtA漢明距離012345td0圖中碼組圖中碼組A和和B之間距離為之間距離為5

28、。按照。按照檢錯能力公式，最多能檢測檢錯能力公式，最多能檢測4個錯碼，個錯碼，即即e = d0 1 = 5 1 = 4，按照糾錯能，按照糾錯能力公式糾錯時，能糾正力公式糾錯時，能糾正2個錯碼。但個錯碼。但是，不能同時做到兩者，因為當(dāng)錯是，不能同時做到兩者，因為當(dāng)錯碼位數(shù)超過糾錯能力時，該碼組立碼位數(shù)超過糾錯能力時，該碼組立即進入另一碼組的圓內(nèi)而被錯誤地即進入另一碼組的圓內(nèi)而被錯誤地“糾正糾正”了。例如，碼組了。例如，碼組A若錯了若錯了3位，就會被誤認為碼組位，就會被誤認為碼組B錯了錯了2位造位造成的結(jié)果，從而被錯成的結(jié)果，從而被錯“糾糾”為為B。這。這就說，檢錯和糾錯公式不能同時成就說，檢錯和

29、糾錯公式不能同時成立或同時運用。立或同時運用。)(10teted第第23頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 4. 糾檢錯能力糾檢錯能力所以，為了在可以糾正所以，為了在可以糾正t個錯碼的同個錯碼的同時，能檢測時，能檢測e個錯碼，需要碼組個錯碼，需要碼組A發(fā)發(fā)生生e個錯碼的位置與碼組個錯碼的位置與碼組B的糾錯范的糾錯范圍至少距離為圍至少距離為1，否則落在該糾錯范，否則落在該糾錯范圍內(nèi)就會被錯誤地圍內(nèi)就會被錯誤地“糾正糾正”。糾檢結(jié)合工作方式：糾檢結(jié)合工作

30、方式：當(dāng)錯碼數(shù)量少時，系統(tǒng)按前向糾錯當(dāng)錯碼數(shù)量少時，系統(tǒng)按前向糾錯方式工作，以節(jié)省重發(fā)時間，提高方式工作，以節(jié)省重發(fā)時間，提高傳輸效率；傳輸效率；當(dāng)錯碼數(shù)量多時，系統(tǒng)按反饋重發(fā)當(dāng)錯碼數(shù)量多時，系統(tǒng)按反饋重發(fā)的糾錯方式工作，以降低系統(tǒng)的總的糾錯方式工作，以降低系統(tǒng)的總誤碼率。誤碼率。)(10tetedAB1tt漢明距離e碼距等于(e+t+1)的兩個碼組第第24頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編碼的基本原理糾錯編碼的基本原理 n 糾檢錯能力總結(jié)：糾檢錯能力總結(jié)：u 碼的最小距離碼的最

31、小距離d0直接關(guān)系著碼的檢錯和糾錯能力；任一直接關(guān)系著碼的檢錯和糾錯能力；任一(n,k)分組碼，若要在碼字內(nèi)分組碼，若要在碼字內(nèi): (1) 檢測檢測e個隨機錯誤，則要求碼的最小距離個隨機錯誤，則要求碼的最小距離d0e+1; (2) 糾正糾正t個隨機錯誤，則要求碼的最小距離個隨機錯誤，則要求碼的最小距離d02t+1; (3) 糾正糾正t個同時檢測個同時檢測e(t)個隨機錯誤，則要求碼的最小個隨機錯誤，則要求碼的最小 距離距離d0t+e+1。第第25頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.1 8.1 概述概述8.1.4 糾錯編

32、碼的基本原理糾錯編碼的基本原理 5.編碼效率編碼效率用差錯控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代用差錯控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價換來的。我們定義編碼效率價換來的。我們定義編碼效率R來衡量有效性來衡量有效性:R=k/n其中其中, k是信息元的個數(shù)，是信息元的個數(shù)，n為碼長。為碼長。對糾錯碼的基本要求是對糾錯碼的基本要求是: 檢錯和糾錯能力盡量強；編碼效率盡檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。實際中要根據(jù)具體指標要求，保證量高；編碼規(guī)律盡量簡單。實際中要根據(jù)具體指標要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。有一定糾、檢錯能力和編碼效

33、率，并且易于實現(xiàn)。 第第26頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.2 8.2 常用的幾種簡單分組碼常用的幾種簡單分組碼8.2.1 奇偶監(jiān)督碼奇偶監(jiān)督碼 奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼組中奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數(shù)是奇數(shù)或偶數(shù)。或者說，它是含一個監(jiān)督元，碼重的個數(shù)是奇數(shù)或偶數(shù)?；蛘哒f，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)系統(tǒng)分組碼。分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。第第27頁，共頁，共68頁

34、頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.2 8.2 常用的幾種簡單分組碼常用的幾種簡單分組碼8.2.1 奇偶監(jiān)督碼奇偶監(jiān)督碼 設(shè)碼字設(shè)碼字A=an-1,an-2,a1,a0，對于偶監(jiān)督碼有，對于偶監(jiān)督碼有式中，式中，a0為監(jiān)督碼，其它為信息碼。為監(jiān)督碼，其它為信息碼。奇監(jiān)督碼情況相似，只是碼組中奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，即滿足的數(shù)目為奇數(shù)，即滿足 而檢錯能力與偶監(jiān)督碼相同。而檢錯能力與偶監(jiān)督碼相同。 奇偶監(jiān)督碼的編碼效率奇偶監(jiān)督碼的編碼效率R為為 00121aaaann1021aaannnnR/ ) 1( 檢奇數(shù)個錯碼

35、第第28頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.2 8.2 常用的幾種簡單分組碼常用的幾種簡單分組碼8.2.2 行列監(jiān)督碼行列監(jiān)督碼 110010100000100001101001111000011100111000001010101010111000111100圖8-2 (66,50)行列監(jiān)督碼 又叫方陣碼或矩形碼，它的構(gòu)造方法是先將若干奇偶監(jiān)督碼組按行排列成矩陣，再按列增加第二維監(jiān)督位。第第29頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.2 8.2

36、常用的幾種簡單分組碼常用的幾種簡單分組碼8.2.3 恒比碼恒比碼碼字中碼字中 1 的數(shù)目與的數(shù)目與 0 的數(shù)目保持恒定比例的碼稱為的數(shù)目保持恒定比例的碼稱為恒比碼恒比碼。 由于恒比碼中，每個碼組均含有相同數(shù)目的由于恒比碼中，每個碼組均含有相同數(shù)目的 1 和和 0，因此恒比，因此恒比碼又稱等重碼，定碼又稱等重碼，定 1 碼。這種碼在檢測時，只要計算接收碼元碼。這種碼在檢測時，只要計算接收碼元中中 1 的數(shù)目是否正確，就知道有無錯誤。的數(shù)目是否正確，就知道有無錯誤。 第第30頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.2 8.2

37、常用的幾種簡單分組碼常用的幾種簡單分組碼8.2.3 恒比碼恒比碼目前我國電傳通信中普遍采用目前我國電傳通信中普遍采用 3：2 碼，又稱碼，又稱“5 中取中取 3”的恒比碼，即每個碼組的長度為的恒比碼，即每個碼組的長度為 5，其中其中 3 個個“1”。這時可能編成的不同碼組數(shù)目。這時可能編成的不同碼組數(shù)目等于從等于從 5 中取中取 3 的組合數(shù)的組合數(shù) 10，這，這 10 個許用碼組個許用碼組恰好可表示恰好可表示 10 個阿拉伯?dāng)?shù)字，如表個阿拉伯?dāng)?shù)字，如表 8-1 所示。所示。而每個漢字（區(qū)位碼）又是以四位十進制數(shù)來而每個漢字（區(qū)位碼）又是以四位十進制數(shù)來代表的（吳代表的（吳 4666 海海 2

38、603 濤濤 4446 ）。）。實踐證明，采用這種碼后，我國漢字電報的差實踐證明，采用這種碼后，我國漢字電報的差錯率大為降低。錯率大為降低。 四碼電報四碼電報第第31頁，共頁，共68頁頁表8-1 3 2 恒比碼 電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.2 8.2 常用的幾種簡單分組碼常用的幾種簡單分組碼8.2.3 恒比碼恒比碼由于漢字結(jié)構(gòu)復(fù)雜，字型繁多，一字一由于漢字結(jié)構(gòu)復(fù)雜，字型繁多，一字一“面孔面孔”，拍電報不直接，拍電報不直接用電碼來表示。因此，采用由四個阿拉伯?dāng)?shù)字代表一個漢字的用電碼來表示。因此，采用由四個阿拉伯?dāng)?shù)字代表一個漢字的方法

39、，簡稱方法，簡稱“四碼電報四碼電報”，中國漢字多達，中國漢字多達6萬字，常用的漢字只萬字，常用的漢字只有一萬個，所以用有一萬個，所以用10的的4次方（次方（10，000）來表示。）來表示。1873年，法年，法國駐華人員威基杰（國駐華人員威基杰（SAViguer）參照）參照康熙字典康熙字典的部首排的部首排列方法，挑選了常用漢字列方法，挑選了常用漢字6800多個，編成了第一部漢字電碼本，多個，編成了第一部漢字電碼本，名為名為電報新書電報新書。后來，由我國的鄭觀應(yīng)將其改編成為。后來，由我國的鄭觀應(yīng)將其改編成為中中國電報新編國電報新編，這是中國最早的漢字電碼本。，這是中國最早的漢字電碼本。 第第32頁

40、，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.1 定義及性質(zhì)定義及性質(zhì)n 如果信息碼元與監(jiān)督碼元之間的關(guān)系可以用一組線性方程如果信息碼元與監(jiān)督碼元之間的關(guān)系可以用一組線性方程來表示，且監(jiān)督碼元僅由本碼組的信息碼元來確定，而與來表示，且監(jiān)督碼元僅由本碼組的信息碼元來確定，而與其他碼組的碼元無關(guān)，則稱該編碼為其他碼組的碼元無關(guān)，則稱該編碼為線性分組碼線性分組碼。n 線性分組碼中信息碼元和監(jiān)督碼元是用線性方程聯(lián)系起來線性分組碼中信息碼元和監(jiān)督碼元是用線性方程聯(lián)系起來的。線性碼建立在代數(shù)學(xué)群論基礎(chǔ)上

41、的。線性碼建立在代數(shù)學(xué)群論基礎(chǔ)上,線性碼各許用碼組的線性碼各許用碼組的集合構(gòu)成代數(shù)學(xué)中的群集合構(gòu)成代數(shù)學(xué)中的群,因此又稱群碼。在群中只存在一種因此又稱群碼。在群中只存在一種運算，即模運算，即模2和，通常四則運算中的加、減法在這里都是模和，通常四則運算中的加、減法在這里都是模2和的關(guān)系。所以后面將簡化運算符號和的關(guān)系。所以后面將簡化運算符號 為為“+”。 第第33頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.1 定義及性質(zhì)定義及性質(zhì)性質(zhì)：性質(zhì)：封閉性：任意兩個許用碼組相加后（按位進行模封閉性

42、：任意兩個許用碼組相加后（按位進行模2和，所得和，所得編碼仍是許用碼組）編碼仍是許用碼組）1. 最小碼距等于非零碼的最小碼重最小碼距等于非零碼的最小碼重(除全除全0碼外碼外) 第第34頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.1 定義及性質(zhì)定義及性質(zhì)現(xiàn)以現(xiàn)以(7,4)分組碼為例來說明線性分組碼的特點。設(shè)其碼字為分組碼為例來說明線性分組碼的特點。設(shè)其碼字為A=a6 a5 a4 a3 a2 a1 a0，其中前，其中前 4 位是信息元，后位是信息元，后 3 位是監(jiān)位是監(jiān)督元，督元， 可用下列

43、線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元?？捎孟铝芯€性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。) 18(346035614562aaaaaaaaaaaa注意：注意：+表示表示模模2和和第第35頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼表 8-2 (7,4)碼的碼字表 最小碼最小碼距距d0=？第第36頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G 8-1第第

44、37頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G 并簡記為并簡記為 H AT = 0T 或或A HT = 0A = a6 a5 a4 a3 a2 a1 a00 = 000右上標右上標“T”表示將矩陣轉(zhuǎn)置。表示將矩陣轉(zhuǎn)置。將將H稱為監(jiān)督矩陣。只要監(jiān)督矩陣稱為監(jiān)督矩陣。只要監(jiān)督矩陣H給定，編給定，編碼時監(jiān)督位和信息位的關(guān)系就完全確定了。碼時監(jiān)督位和信息位的關(guān)系就完全確定了。 101100111010101110100H第第38頁，共頁，共68頁頁電

45、子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G H矩陣的性質(zhì)：矩陣的性質(zhì)：(1) H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于監(jiān)督位的數(shù)目的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于監(jiān)督位的數(shù)目r。H的每行中的每行中“1”的位置表示相應(yīng)碼元之間存在的監(jiān)督關(guān)系。例如，的位置表示相應(yīng)碼元之間存在的監(jiān)督關(guān)系。例如，H的第一行的第一行1110100表示監(jiān)督位表示監(jiān)督位a2是由是由a6 a5 a4之和決定的。之和決定的。H矩陣矩陣可以分成兩部分，例如可以分成兩部分，例如rIPH001101101

46、011011001110第第39頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G 其中，其中，P為為rk階矩陣，階矩陣，Ir為為rr階單位矩陣?？梢詫懗呻A單位矩陣?？梢詫懗蒆 =P Ir形式的矩陣稱為形式的矩陣稱為典型監(jiān)督矩陣典型監(jiān)督矩陣。HAT=0T，說明，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字用來作為判斷接收碼字A是否出錯的依據(jù)。是否出錯的依據(jù)。 第第40頁，共頁，共68頁頁rIPH00110

47、1101011011001110電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G H矩陣的性質(zhì)：矩陣的性質(zhì)：(2) 由代數(shù)理論可知，由代數(shù)理論可知，H矩陣的各行應(yīng)該是線性無關(guān)的，否則將矩陣的各行應(yīng)該是線性無關(guān)的，否則將得不到得不到 r個線性無關(guān)的監(jiān)督關(guān)系式，從而也得不到個線性無關(guān)的監(jiān)督關(guān)系式，從而也得不到 r個獨立的監(jiān)個獨立的監(jiān)督位。若一矩陣能寫成典型陣形式督位。若一矩陣能寫成典型陣形式P Ir，則其各行一定是線性，則其各行一定是線性無關(guān)的。因為容易驗證無關(guān)的。因為容

48、易驗證Ir的各行是線性無關(guān)的，故的各行是線性無關(guān)的，故P Ir的各行的各行也是線性無關(guān)的。也是線性無關(guān)的。rIPH001101101011011001110第第41頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G 若把監(jiān)督方程補充為下列方程若把監(jiān)督方程補充為下列方程 第第42頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.2 監(jiān)督矩陣監(jiān)督矩陣H和

49、生成矩陣和生成矩陣G 可改寫為矩陣形式可改寫為矩陣形式 第第43頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G 1101000101010001100101110001GQIGkTPQ110101011111G為生成矩陣，由由它可以產(chǎn)生整個碼它可以產(chǎn)生整個碼組，組，具有Ik Q形式的生成矩陣稱為典型生成矩陣。各行仍線性無關(guān)！各行仍線性無關(guān)！由典型生成矩陣得出的碼組由典型生成矩陣得出的碼組A中，信息位的位置不變，中，信息位的位置不變，監(jiān)督位附加于其

50、后。這種形監(jiān)督位附加于其后。這種形式的碼稱為式的碼稱為系統(tǒng)碼系統(tǒng)碼。 第第44頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.3伴隨式伴隨式(校正子校正子)S 設(shè)發(fā)送碼組設(shè)發(fā)送碼組A=an-1,an-2,a1,a0，在傳輸過程中可能發(fā)，在傳輸過程中可能發(fā)生誤碼。接收碼組生誤碼。接收碼組B=bn-1,bn-2,b1,b0，則收發(fā)碼組之，則收發(fā)碼組之差定義為錯誤圖樣差定義為錯誤圖樣E， 也稱為誤差矢量，也稱為誤差矢量， 即即其中其中E=en-1,en-2,e1,e0，且，且 ABE(8 - 2)

51、 10ie當(dāng)當(dāng)bi=ai 當(dāng)當(dāng)biai 碼元未錯碼元有錯第第45頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.3伴隨式伴隨式(校正子校正子)S 式式(8 - 2)也可寫作也可寫作令令S=BHT，稱為，稱為伴隨式或校正子伴隨式或校正子。當(dāng)當(dāng)H確定后，確定后，S只與只與E有關(guān)，而與有關(guān)，而與A無關(guān)。這意味著無關(guān)。這意味著S和錯和錯碼碼E之間有確定的線性變換關(guān)系。若之間有確定的線性變換關(guān)系。若S和和E有一一對應(yīng)關(guān)有一一對應(yīng)關(guān)系，則系，則S將能代表錯碼位置。將能代表錯碼位置。EAB表示發(fā)送碼組A與

52、錯碼矩陣之和等于接收碼組BTTTEHHEABHS)(第第46頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.3伴隨式伴隨式(校正子校正子)S 線性碼有一個重要性質(zhì)，就是它的封閉性。封閉性是指線性碼有一個重要性質(zhì)，就是它的封閉性。封閉性是指一種線性碼中任意兩個碼組之和仍為這種編碼一種線性碼中任意兩個碼組之和仍為這種編碼 中的一個中的一個碼組。也就是說，若碼組。也就是說，若A1和和A2是一種線性碼中的兩個碼組，是一種線性碼中的兩個碼組，則（則（A1+A2）仍是其中的一個碼組。（證明）仍是其中的一

53、個碼組。（證明）第第47頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.3 8.3 線性分組碼線性分組碼8.3.3伴隨式伴隨式(校正子校正子)S 表 8-3 (7,4)碼S與E的對應(yīng)關(guān)系 TEHS 第第48頁，共頁，共68頁頁檢錯能力？能糾錯兩個及以上？檢錯能力？能糾錯兩個及以上？電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.4 8.4 循環(huán)碼循環(huán)碼 8.4.1 定義定義循環(huán)性循環(huán)性是指任一碼組循環(huán)是指任一碼組循環(huán)（左移或右移）一位后仍（左移或右移）一位后仍然是該編碼中的一個碼組。然是

54、該編碼中的一個碼組。（仍屬于線性分組碼）（仍屬于線性分組碼）表 8-4 一種(7, 3)循環(huán)碼的全部碼組表中第表中第4碼組向右移一位即碼組向右移一位即得到第得到第2碼組；第碼組；第7碼組向碼組向左移一位即得到第左移一位即得到第6碼組。碼組。第第49頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.4 8.4 循環(huán)碼循環(huán)碼 8.4.1 定義定義循環(huán)碼的定義：循環(huán)碼的定義：如果如果 (n,k) 線性分組碼的任意碼矢線性分組碼的任意碼矢A=(an1, an2, a0) 的的 i 次循環(huán)移位，所得矢量次循環(huán)移位，所得矢量A(i)=(an1i

55、, an2i, , a0, an1, , ani) 仍是一個碼矢，則稱此線性碼為仍是一個碼矢，則稱此線性碼為 (n,k) 循環(huán)碼。循環(huán)碼。第第50頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.4 8.4 循環(huán)碼循環(huán)碼 8.4.1 定義定義在代數(shù)理論中，為了便于計算，常用碼多項式表示碼字。在代數(shù)理論中，為了便于計算，常用碼多項式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項式循環(huán)碼的碼字，其碼多項式(以降冪順序排列以降冪順序排列)為：為：注意：上式中注意：上式中x的值沒有任何意義，僅用它的冪代表碼元的值沒有任何意義，僅用它的冪代表碼元

56、的位置。例：碼組的位置。例：碼組1 1 0 0 1 0 1可以表示為可以表示為 012211)(axaxaxaxAnnnn11010011)(25623456xxxxxxxxxxA第第51頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.4 8.4 循環(huán)碼循環(huán)碼 8.4.2 生成多項式及生成矩陣生成多項式及生成矩陣 如果一種碼的所有碼多項式都是多如果一種碼的所有碼多項式都是多項式項式g(x)的倍式，則稱的倍式，則稱g(x)為該碼的為該碼的生成多項式生成多項式。在。在(n,k)循環(huán)碼中任意循環(huán)碼中任意碼多項式碼多項式A(x)都是最低次

57、碼多項式都是最低次碼多項式的倍式。如表的倍式。如表 8-4 的的(7,3)循環(huán)碼中，循環(huán)碼中，1)()(2341xxxxAxg第第52頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.4 8.4 循環(huán)碼循環(huán)碼 8.4.2 生成多項式及生成矩陣生成多項式及生成矩陣 其它碼多項式都是其它碼多項式都是g(x)的倍式，的倍式， 即即 )()()() 1()()() 1()()() 1()()()()() 1()()(0)(2726254320 xgxxAxgxxAxgxxxAxgxxxAxgxxAxgxxAxgxA)()(1xgxA第第53

58、頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.4 8.4 循環(huán)碼循環(huán)碼 8.4.2 生成多項式及生成矩陣生成多項式及生成矩陣 循環(huán)碼的生成矩陣常用多項式的形式來表示循環(huán)碼的生成矩陣常用多項式的形式來表示 )()()()()(21xgxxgxgxxgxxGkk在循環(huán)碼中，一個在循環(huán)碼中，一個(n, k)碼有碼有2k個不同個不同的碼組。若用的碼組。若用g(x)表示其中前表示其中前(k-1)位位皆為皆為“0”的碼組，則的碼組，則g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是碼組，而且這都是碼組，而且這k個碼組是線性無關(guān)

59、的。因此它們可個碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣以用來構(gòu)成此循環(huán)碼的生成矩陣G。若前k位為0會怎樣？由于由于G是是k行行n列的矩列的矩陣，因此若能找到陣，因此若能找到k個線性無關(guān)的已知碼個線性無關(guān)的已知碼組，就能構(gòu)成矩陣組，就能構(gòu)成矩陣G。1)(111xgxgxxgrrr為什么？第第54頁，共頁，共68頁頁電子信息與機電工程學(xué)院電子信息與機電工程學(xué)院通信原理通信原理精品資源共享課精品資源共享課8.4 8.4 循環(huán)碼循環(huán)碼 8.4.2 生成多項式及生成矩陣生成多項式及生成矩陣 在循環(huán)碼中除全在循環(huán)碼中除全“0”碼組外，再沒有連續(xù)碼組外，再沒有連續(xù)k位均為位均為“0”的的碼

60、組，即連碼組，即連“0”的長度最多只能有的長度最多只能有(k-1)位。否則，在經(jīng)位。否則，在經(jīng)過若干次循環(huán)移位后將得到一個過若干次循環(huán)移位后將得到一個k位信息位全為位信息位全為“0”，但，但監(jiān)督位不全為監(jiān)督位不全為“0”的一個碼組。這在線性碼中顯然是不的一個碼組。這在線性碼中顯然是不可能的。因此，可能的。因此，g(x)必須是一個必須是一個常數(shù)項不為常數(shù)項不為“0”的的(n-k)次次多項式多項式，而且這個，而且這個g(x)還是這種還是這種(n, k)碼中次數(shù)為碼中次數(shù)為(nk)的的唯一多項式唯一多項式。為什么常數(shù)項不為0？(n-1)-(k-1)=n-k=r第第55頁，共頁，共68頁頁電子信息與機