聊城大學(xué)數(shù)字通信課件!第七章糾錯編碼12-3-31

1、數(shù)字通信原理數(shù)字通信原理LCU 1 第七章第七章 差錯控制編碼差錯控制編碼 LCU 2 單元概述單元概述 實際信道傳輸數(shù)字信號時，不可避免地實際信道傳輸數(shù)字信號時，不可避免地 會產(chǎn)生誤碼。差錯控制編碼的目的是會產(chǎn)生誤碼。差錯控制編碼的目的是用信道用信道 編碼的方法檢測和糾正誤碼，編碼的方法檢測和糾正誤碼，降低誤碼率。降低誤碼率。 LCU 3 單元學(xué)習(xí)提綱單元學(xué)習(xí)提綱 （1 1）前向糾錯、檢錯重發(fā)差錯控制方法；）前向糾錯、檢錯重發(fā)差錯控制方法； （2 2）檢錯和糾錯的基本原理；）檢錯和糾錯的基本原理； （3 3）碼距的定義，它與檢錯、糾錯能力的關(guān)系；）碼距的定義，它與檢錯、糾錯能力的關(guān)系； 糾錯

2、編碼誤碼率的計算糾錯編碼誤碼率的計算 （4 4）分組碼、卷積碼、線性碼、系統(tǒng)碼的定義；）分組碼、卷積碼、線性碼、系統(tǒng)碼的定義； （5 5）線性分組碼中監(jiān)督方程、監(jiān)督矩陣、生成方）線性分組碼中監(jiān)督方程、監(jiān)督矩陣、生成方 程、生成矩陣的含義；程、生成矩陣的含義； LCU 4 （6 6）漢明碼的特點及構(gòu)造；）漢明碼的特點及構(gòu)造； （7 7）循環(huán)碼的特點及編碼方法；）循環(huán)碼的特點及編碼方法； （8 8）循環(huán)碼的一種解碼方法；）循環(huán)碼的一種解碼方法； （9 9）卷積碼的編碼方法，生成多項式與編碼器的）卷積碼的編碼方法，生成多項式與編碼器的 構(gòu)造；構(gòu)造； （1010）卷積碼的樹狀圖、網(wǎng)格圖表示；）卷積碼的

3、樹狀圖、網(wǎng)格圖表示； （1111）卷積碼維特比譯碼的基本原理和譯碼過程；）卷積碼維特比譯碼的基本原理和譯碼過程； LCU 主要內(nèi)容主要內(nèi)容 7.1 差錯控制編碼的基本概念差錯控制編碼的基本概念 7.2 糾錯編碼的基本原理糾錯編碼的基本原理 7.3 線性分組碼線性分組碼 7.4 循環(huán)碼循環(huán)碼 7.5 卷積碼卷積碼 5 LCU 6 7.1 7.1 差錯控制編碼的基本概念差錯控制編碼的基本概念 1、用差錯控制編碼來檢錯和糾錯的原因用差錯控制編碼來檢錯和糾錯的原因 2、信道的分類信道的分類 3、差錯控制方式差錯控制方式 4、差錯控制編碼的分類差錯控制編碼的分類 LCU 7 7.1.1 7.1.1 用差

4、錯控制編碼來檢錯和糾錯的原因用差錯控制編碼來檢錯和糾錯的原因 LCU 8 u在中等傳輸速率（在中等傳輸速率（1200/2400波特）下，對于干線波特）下，對于干線 有線載波信道，有線載波信道， Pe約為約為10-410-6的數(shù)量級，對于無的數(shù)量級，對于無 線短波通信，線短波通信， Pe只有只有10-210-3的數(shù)量級。的數(shù)量級。 u對碼速為對碼速為64kbps的系統(tǒng)的系統(tǒng),國際電報電話咨詢委員會國際電報電話咨詢委員會 把誤碼率把誤碼率10-3的稱為嚴(yán)重誤碼。的稱為嚴(yán)重誤碼。 u我國長途光纜通信系統(tǒng)的進(jìn)網(wǎng)要求之一：誤碼性能我國長途光纜通信系統(tǒng)的進(jìn)網(wǎng)要求之一：誤碼性能 要優(yōu)于要優(yōu)于10-9。 u千

5、兆以太網(wǎng)的可接受的最高限度誤碼率為千兆以太網(wǎng)的可接受的最高限度誤碼率為10-10 LCU 9 為保證傳輸數(shù)據(jù)的完整性，通常采用一定為保證傳輸數(shù)據(jù)的完整性，通常采用一定 的措施，的措施， 如如利用均衡器糾正信道中的利用均衡器糾正信道中的乘性干擾；乘性干擾； 加大發(fā)送功率、擴(kuò)展信道頻帶寬度加大發(fā)送功率、擴(kuò)展信道頻帶寬度等辦法來減等辦法來減 少少加性干擾。加性干擾。 采用上述方法仍難以滿足要求時，必須采用上述方法仍難以滿足要求時，必須 采用差錯控制措施，即用采用差錯控制措施，即用差錯控制編碼差錯控制編碼來來 和和。 LCU 10 1 1、隨機(jī)信道隨機(jī)信道：誤碼的出現(xiàn)是隨機(jī)的，誤碼的出現(xiàn)是隨機(jī)的，誤碼

6、之間誤碼之間 是統(tǒng)計獨立的。是統(tǒng)計獨立的。如由正態(tài)分布白噪聲引起的誤碼如由正態(tài)分布白噪聲引起的誤碼 （稱為（稱為） 2 2、突發(fā)信道突發(fā)信道：誤碼是成串集中出現(xiàn)的，誤碼是成串集中出現(xiàn)的，即在短促即在短促 的時間區(qū)間存在大量誤碼，在較長的時間區(qū)間無誤的時間區(qū)間存在大量誤碼，在較長的時間區(qū)間無誤 碼出現(xiàn)。碼出現(xiàn)。產(chǎn)生產(chǎn)生的主要原因是脈沖干擾的主要原因是脈沖干擾 3 3、混合信道混合信道：既存在隨機(jī)誤碼又存在突發(fā)誤碼的既存在隨機(jī)誤碼又存在突發(fā)誤碼的 信道稱為混合信道信道稱為混合信道。 7.1.2 7.1.2 信道的分類信道的分類 LCU 11 1、檢錯重發(fā)方式（、檢錯重發(fā)方式（ARQ） 2、前向糾錯

7、方式（、前向糾錯方式（FEC） 3、混合糾錯檢錯方式（、混合糾錯檢錯方式（HEC） 4、反饋校驗方式（、反饋校驗方式（IRQ） 7.1.3 7.1.3 差錯控制方式差錯控制方式 LCU 12 LCU 13 1 1、檢錯重發(fā)方式、檢錯重發(fā)方式（ARQ） 原理原理: :采用檢錯重發(fā)方式，發(fā)端經(jīng)編碼后發(fā)出能采用檢錯重發(fā)方式，發(fā)端經(jīng)編碼后發(fā)出能 檢測錯誤的碼；接收端收到后經(jīng)檢驗如果發(fā)現(xiàn)傳檢測錯誤的碼；接收端收到后經(jīng)檢驗如果發(fā)現(xiàn)傳 輸中有錯誤，則通過反向信道把這一判斷結(jié)果反輸中有錯誤，則通過反向信道把這一判斷結(jié)果反 饋給發(fā)送端。然后發(fā)送端把信息重發(fā)一次，直到饋給發(fā)送端。然后發(fā)送端把信息重發(fā)一次，直到 接

8、收端確認(rèn)為止。接收端確認(rèn)為止。 要求要求: :采用這種差錯控制方法采用這種差錯控制方法， 一般在計算機(jī)數(shù)據(jù)通信中應(yīng)用。一般在計算機(jī)數(shù)據(jù)通信中應(yīng)用。 LCU 14 ARQ停發(fā)等待重發(fā)方式停發(fā)等待重發(fā)方式：發(fā)對或發(fā)錯，發(fā)送端均要發(fā)對或發(fā)錯，發(fā)送端均要 等待接收端的回應(yīng)。特點是系統(tǒng)簡單，時延長。等待接收端的回應(yīng)。特點是系統(tǒng)簡單，時延長。 圖中圖中ACK是確認(rèn)信號，是確認(rèn)信號，NAK是否認(rèn)信號。是否認(rèn)信號。 LCU 15 2、前向糾錯方式（、前向糾錯方式（FEC） 原理：原理：發(fā)送端經(jīng)編碼發(fā)出能糾正錯誤的碼，接收發(fā)送端經(jīng)編碼發(fā)出能糾正錯誤的碼，接收 端收到這些碼組后，通過譯碼能發(fā)現(xiàn)并糾正誤碼。端收到這

9、些碼組后，通過譯碼能發(fā)現(xiàn)并糾正誤碼。 要求：要求：前向糾錯方式不需要反饋通道，特別適合前向糾錯方式不需要反饋通道，特別適合 只能提供只能提供單向信道單向信道的場合，特點是時延小，實時性的場合，特點是時延小，實時性 好，但系統(tǒng)復(fù)雜。但隨著編碼理論和微電子技術(shù)的好，但系統(tǒng)復(fù)雜。但隨著編碼理論和微電子技術(shù)的 發(fā)展，編譯碼設(shè)備成本下降，加之有單向通信和控發(fā)展，編譯碼設(shè)備成本下降，加之有單向通信和控 制電路簡單的優(yōu)點，在實際應(yīng)用中日益增多。制電路簡單的優(yōu)點，在實際應(yīng)用中日益增多。 LCU 16 3、混合糾錯檢錯方式（、混合糾錯檢錯方式（HEC） 原理：原理：混合糾錯檢錯方式是前向糾錯方式和檢錯混合糾錯檢

10、錯方式是前向糾錯方式和檢錯 重發(fā)方式的結(jié)合，重發(fā)方式的結(jié)合，發(fā)送端發(fā)出的碼不但有一定的糾錯發(fā)送端發(fā)出的碼不但有一定的糾錯 能力，對于超出糾錯能力的錯誤要具有檢錯能力。能力，對于超出糾錯能力的錯誤要具有檢錯能力。 這種方式在實時性和復(fù)雜性方面是前向糾錯和檢錯這種方式在實時性和復(fù)雜性方面是前向糾錯和檢錯 重發(fā)方式的折衷，因而在近年來，在數(shù)據(jù)通信系統(tǒng)中重發(fā)方式的折衷，因而在近年來，在數(shù)據(jù)通信系統(tǒng)中 采用較多。采用較多。 LCU 17 4、反饋校驗方式（、反饋校驗方式（IRQ） 原理：原理：又稱回程校驗。收端把收到的數(shù)據(jù)序列全部又稱回程校驗。收端把收到的數(shù)據(jù)序列全部 由反向信道送回發(fā)送端，發(fā)送端比較發(fā)

11、送數(shù)據(jù)與回由反向信道送回發(fā)送端，發(fā)送端比較發(fā)送數(shù)據(jù)與回 送數(shù)據(jù)，從而發(fā)現(xiàn)是否有錯誤，并把認(rèn)為錯誤的數(shù)送數(shù)據(jù)，從而發(fā)現(xiàn)是否有錯誤，并把認(rèn)為錯誤的數(shù) 據(jù)重新發(fā)送，直到發(fā)送端沒有發(fā)現(xiàn)錯誤為止。據(jù)重新發(fā)送，直到發(fā)送端沒有發(fā)現(xiàn)錯誤為止。 不需要糾錯、檢錯的編譯器，設(shè)備簡單。不需要糾錯、檢錯的編譯器，設(shè)備簡單。 需要反向信道；實時性差；發(fā)送端需要一定需要反向信道；實時性差；發(fā)送端需要一定 容量的存儲器。容量的存儲器。IRQ方式僅適用于傳輸速率較低、方式僅適用于傳輸速率較低、 數(shù)據(jù)差錯率較低的控制簡單的系統(tǒng)中。數(shù)據(jù)差錯率較低的控制簡單的系統(tǒng)中。 LCU 18 7.1.4 7.1.4 差錯控制編碼的分類差錯控

12、制編碼的分類 1、按照差錯控制編碼的不同功能，可以分為、按照差錯控制編碼的不同功能，可以分為檢錯檢錯 碼碼（僅能檢測誤碼）、（僅能檢測誤碼）、糾錯碼糾錯碼（僅可以糾正誤碼）（僅可以糾正誤碼） 和和糾刪碼糾刪碼（兼有糾錯和檢錯功能）。（兼有糾錯和檢錯功能）。 2、按照、按照和附加的和附加的之間的檢驗關(guān)之間的檢驗關(guān) 系可以分為系可以分為線性碼線性碼（信息碼元和監(jiān)督碼元滿足一（信息碼元和監(jiān)督碼元滿足一 組線性方程）和組線性方程）和非線性碼非線性碼 3、按照、按照和和之間的約束關(guān)系可以之間的約束關(guān)系可以 分為分為分組碼分組碼和和卷積碼卷積碼。 LCU 19 4.根據(jù)信息碼元在編碼前后是否保持原來的形式

13、不根據(jù)信息碼元在編碼前后是否保持原來的形式不 變，可分為變，可分為系統(tǒng)碼系統(tǒng)碼和和非系統(tǒng)碼非系統(tǒng)碼。 5、按照糾正錯誤的類型不同，可以分為、按照糾正錯誤的類型不同，可以分為糾正隨機(jī)糾正隨機(jī) 錯誤的碼錯誤的碼和和糾正突發(fā)錯誤的碼糾正突發(fā)錯誤的碼。 6、按照構(gòu)成差錯控制編碼的數(shù)學(xué)方法來分類，可以、按照構(gòu)成差錯控制編碼的數(shù)學(xué)方法來分類，可以 分為分為代數(shù)碼、幾何碼代數(shù)碼、幾何碼和和算術(shù)碼算術(shù)碼。其中代數(shù)碼建立在近。其中代數(shù)碼建立在近 代數(shù)學(xué)基礎(chǔ)上，是目前發(fā)展最為完善的編碼，其中線代數(shù)學(xué)基礎(chǔ)上，是目前發(fā)展最為完善的編碼，其中線 性碼是是代數(shù)碼的一個最重要的分支。性碼是是代數(shù)碼的一個最重要的分支。 7、

14、按照每個碼元的取值不同，可以分為、按照每個碼元的取值不同，可以分為二進(jìn)制碼二進(jìn)制碼和和 多進(jìn)制碼多進(jìn)制碼。 LCU 20 卷積碼卷積碼 非線性碼非線性碼 線性碼線性碼 糾錯碼糾錯碼 分組碼分組碼 循環(huán)碼循環(huán)碼 非循環(huán)碼非循環(huán)碼 糾隨機(jī)糾隨機(jī) 錯誤碼錯誤碼 糾突發(fā)糾突發(fā) 錯誤碼錯誤碼 糾隨機(jī)和突糾隨機(jī)和突 發(fā)錯誤碼發(fā)錯誤碼 糾同步糾同步 錯誤碼錯誤碼 糾錯碼分類糾錯碼分類 LCU 21 7.2 7.2 糾錯編碼的基本原理糾錯編碼的基本原理 1、糾錯編碼的基本思想糾錯編碼的基本思想 2、碼重、碼距、最小碼距的定義碼重、碼距、最小碼距的定義 3、碼距與檢錯和糾錯能力碼距與檢錯和糾錯能力 4、差錯控制

15、編碼的效率差錯控制編碼的效率 5、幾種常用的簡單檢錯碼幾種常用的簡單檢錯碼 LCU 22 回憶：回憶： 香農(nóng)的信道編碼定理香農(nóng)的信道編碼定理 RC R=e+1 A e 1 dmi n (a) LCU 30 （2）在一個碼組內(nèi)糾正）在一個碼組內(nèi)糾正t個誤碼，要求最小碼個誤碼，要求最小碼 距距 dmin=2t+1 1 t A B t dmin LCU 31 （3）在一個碼組內(nèi)糾正）在一個碼組內(nèi)糾正t個誤碼，同時檢測個誤碼，同時檢測e個個(et) 誤碼（當(dāng)誤碼數(shù)大于誤碼（當(dāng)誤碼數(shù)大于t時就不能糾錯，只能檢測時就不能糾錯，只能檢測e個個 誤碼），要求最小碼距誤碼），要求最小碼距 dmint+e+1 A

16、B t e dmin t (c) LCU 32 假設(shè)在隨機(jī)信道中發(fā)送假設(shè)在隨機(jī)信道中發(fā)送“0”時的錯誤概率和發(fā)送時的錯誤概率和發(fā)送“1” 時的相等，都等于時的相等，都等于p,且且p1，則容易證明，則容易證明，在碼長為在碼長為 n的碼組中恰好發(fā)生的碼組中恰好發(fā)生r個錯碼的概率為個錯碼的概率為 ! ( )(1) !()! rrn rr nn n P rC ppp r nr 7.2.4 7.2.4 差錯控制編碼的效率差錯控制編碼的效率 LCU 33 例如：當(dāng)碼長例如：當(dāng)碼長n=7,p=1e-3時，有時，有 上式表明，即使是較簡單的差錯控制編碼也具上式表明，即使是較簡單的差錯控制編碼也具 有較大實用價

17、值。有較大實用價值。 3 7 25 7 38 7 (1)77 10 (2)212.1 10 (3)353.5 10 Pp Pp Pp LCU 34 7.2.5 7.2.5 幾種常用的簡單檢錯碼幾種常用的簡單檢錯碼 1、奇偶監(jiān)督碼、奇偶監(jiān)督碼 2、二維奇偶監(jiān)督碼、二維奇偶監(jiān)督碼 3、恒比碼、恒比碼 4、正反碼、正反碼 LCU 35 奇偶監(jiān)督碼的編碼規(guī)則是在信息位后加上奇偶監(jiān)督碼的編碼規(guī)則是在信息位后加上一位監(jiān)督位一位監(jiān)督位形成形成 具有檢錯能力的碼。具有檢錯能力的碼。 如果是偶校驗，則要求整個碼字中如果是偶校驗，則要求整個碼字中“1”的個數(shù)為偶數(shù)的個數(shù)為偶數(shù)，例，例 如如 1 0 1 1 0 0

18、 1 0 當(dāng)傳輸過程中當(dāng)傳輸過程中出現(xiàn)奇數(shù)個錯誤出現(xiàn)奇數(shù)個錯誤，接收端都能發(fā)現(xiàn)有無錯誤，但，接收端都能發(fā)現(xiàn)有無錯誤，但 不能發(fā)現(xiàn)偶數(shù)個錯誤不能發(fā)現(xiàn)偶數(shù)個錯誤，比如，比如 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 有錯有錯 1 1 1 0 0 1 1 0 有錯有錯 1 0 1 0 0 1 1 0 不能確定不能確定 如果是奇校驗，則要求整個碼字中如果是奇校驗，則要求整個碼字中“1”的個數(shù)為奇數(shù)的個數(shù)為奇數(shù)，例，例 如如 1 0 1 1 0 0 1 1 一、奇偶監(jiān)督碼一、奇偶監(jiān)督碼 LCU 36 行列奇偶監(jiān)督碼亦稱水平垂直奇偶監(jiān)督碼，行列奇偶監(jiān)督碼亦稱水平垂直奇偶監(jiān)督碼，它是將

19、若干個它是將若干個 信息碼字按每個碼字一行排列成矩陣形式，然后在每一行和每信息碼字按每個碼字一行排列成矩陣形式，然后在每一行和每 一列的碼元后面附加一位奇（偶）監(jiān)督碼元。一列的碼元后面附加一位奇（偶）監(jiān)督碼元。 行列奇偶監(jiān)督碼不但能檢測出某一行或某一列的所有奇數(shù)行列奇偶監(jiān)督碼不但能檢測出某一行或某一列的所有奇數(shù) 個錯誤，有時還能檢測出某些偶數(shù)個錯誤。個錯誤，有時還能檢測出某些偶數(shù)個錯誤。 不能檢測構(gòu)成矩形四角的錯碼。不能檢測構(gòu)成矩形四角的錯碼。 信息碼元信息碼元 監(jiān)督碼元監(jiān)督碼元 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1

20、 1 0 0 1 0 0 1 1 0 0 1 監(jiān)督碼元監(jiān)督碼元 1 0 1 1 0 0 0 1 二、二維奇偶監(jiān)督碼二、二維奇偶監(jiān)督碼 信息碼元信息碼元 監(jiān)督碼元監(jiān)督碼元 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 LCU 37 恒比碼是從某種特定長度的碼字中選出那些恒比碼是從某種特定長度的碼字中選出那些“1 1”的個數(shù)與的個數(shù)與 “0 0”的個數(shù)保持恒定比例的碼字作為許用碼字。的個數(shù)保持恒定比例的碼字作為許用碼字。 五單位數(shù)字保護(hù)電碼五單位數(shù)字保護(hù)

21、電碼 碼字長度為碼字長度為5，只選用碼字中含有，只選用碼字中含有三個三個“1”和兩個和兩個“0”的碼字作為許用的碼字作為許用 碼字來表示碼字來表示10個阿拉伯?dāng)?shù)字個阿拉伯?dāng)?shù)字1，2，9，0，這種碼亦稱，這種碼亦稱“5中取中取3碼碼”。 例：中文電報編碼：例：中文電報編碼： 通通 信信 6639 0207 10101 10101 10110 10011 01101 11001 01101 11100 國際電報通信中廣泛采用的是國際電報通信中廣泛采用的是“7中中 取取3碼碼”，許用碼字共有個，可分別表，許用碼字共有個，可分別表 示示26個字母和其它的一些符號。個字母和其它的一些符號。 數(shù)數(shù) 字字

22、數(shù)字保護(hù)數(shù)字保護(hù) 電碼電碼 1 2 3 4 5 6 7 8 9 0 0 1 0 1 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 1 三、三、 恒比碼恒比碼 LCU 38 正反碼是一種簡單的能夠糾正錯碼的編碼。正反碼是一種簡單的能夠糾正錯碼的編碼。其中監(jiān)督位數(shù)與信其中監(jiān)督位數(shù)與信 息位數(shù)相同，監(jiān)督碼元與信息碼元相同（是信息碼的重復(fù)）或者息位數(shù)相同，監(jiān)督碼元與信息碼元相同（是信息碼的重復(fù)）或者 相反（是信息碼的反碼），則由信息碼中相反（是信息碼的反碼），則由信息碼

23、中“1 1”的個數(shù)而定。的個數(shù)而定。 四、四、 正反碼正反碼 電報通信中使用的正反碼的碼長電報通信中使用的正反碼的碼長n=10,信息位信息位k=5,監(jiān)監(jiān) 督位督位r=5，編碼規(guī)則為：，編碼規(guī)則為： a.信息位中有信息位中有奇數(shù)個奇數(shù)個“1”時，監(jiān)督位是信息位的簡單時，監(jiān)督位是信息位的簡單 重復(fù)。重復(fù)。 b.信息位中有信息位中有偶數(shù)個偶數(shù)個“1”時，監(jiān)督位是信息位的反碼。時，監(jiān)督位是信息位的反碼。 信息位是信息位是11001碼組是碼組是11001 11001 信息位是信息位是10001碼組是碼組是10001 01110 LCU 39 電報通信中使用的正反碼的譯碼規(guī)則為：電報通信中使用的正反碼的譯

24、碼規(guī)則為： 先將接收碼組中信息位和監(jiān)督位按位模先將接收碼組中信息位和監(jiān)督位按位模2相加，得相加，得 到一個到一個5位的合成碼組，然后由此合成碼組產(chǎn)生一個位的合成碼組，然后由此合成碼組產(chǎn)生一個 校驗碼組校驗碼組 a.若接收碼組的信息位有若接收碼組的信息位有奇數(shù)個奇數(shù)個“1”，則合成，則合成 碼組就是校驗碼組；碼組就是校驗碼組； b.若接收碼組的信息位有若接收碼組的信息位有偶數(shù)個偶數(shù)個“1”，則合成，則合成 碼組的反碼作為校驗碼組；碼組的反碼作為校驗碼組； LCU 40 發(fā)送碼組是發(fā)送碼組是11001 11001 接收碼組是接收碼組是11001 11001 合成碼組合成碼組 11001 11001

25、=00000 校驗碼組校驗碼組 00000 發(fā)送碼組是發(fā)送碼組是11001 11001 接收碼組是接收碼組是10001 11001 ？ LCU 41 7.3 7.3 線性分組碼線性分組碼 1、線性分組碼的基本概念、線性分組碼的基本概念 2、監(jiān)督矩陣、生成矩陣、校正子、監(jiān)督矩陣、生成矩陣、校正子 3、漢明碼、漢明碼 LCU 42 7.3.1 7.3.1 線性分組碼的基本概念線性分組碼的基本概念 1.代數(shù)學(xué)中把對某種運算滿足以下條件的一類集合稱為代數(shù)學(xué)中把對某種運算滿足以下條件的一類集合稱為群群： u封閉性封閉性：集合中任意兩個元素經(jīng)該運算后仍為該集合的元素：集合中任意兩個元素經(jīng)該運算后仍為該集合

26、的元素 u存在單位元素存在單位元素：集合中任意元素與該元素運算后仍為原來的元素：集合中任意元素與該元素運算后仍為原來的元素 u存在逆元素存在逆元素：集合中任一元素與某元素運算后能得到單位元素：集合中任一元素與某元素運算后能得到單位元素 u結(jié)合律成立結(jié)合律成立：（：（A+B）+C=A+(B+C) 線性分組碼：線性分組碼：信息位和監(jiān)督位是由一些信息位和監(jiān)督位是由一些線性代數(shù)方程線性代數(shù)方程聯(lián)系起來，聯(lián)系起來， 建立在代數(shù)學(xué)群論基礎(chǔ)上，又稱建立在代數(shù)學(xué)群論基礎(chǔ)上，又稱群碼群碼。 LCU 線性分組碼的性質(zhì)線性分組碼的性質(zhì) 43 LCU 44 2. 2.對于奇偶監(jiān)督碼的偶校驗，我們用下式作為作為對于奇偶

27、監(jiān)督碼的偶校驗，我們用下式作為作為 021 .aaaS nn 在接收端譯碼時，若在接收端譯碼時，若S=0，就認(rèn)為無錯。，就認(rèn)為無錯。 若若S=1，就認(rèn)為有錯。，就認(rèn)為有錯。 這里稱這里稱S為為校正子校正子（校驗子），又稱伴隨式。（校驗子），又稱伴隨式。 在此例中，由于只有一位監(jiān)督碼元，一個監(jiān)督方程，在此例中，由于只有一位監(jiān)督碼元，一個監(jiān)督方程， 所以所以只能檢錯，無法糾錯。只能檢錯，無法糾錯。 LCU 45 如果監(jiān)督位增加一位，變成兩位，則能增加一個類如果監(jiān)督位增加一位，變成兩位，則能增加一個類 似上式的監(jiān)督關(guān)系式。兩個校正子的組合：似上式的監(jiān)督關(guān)系式。兩個校正子的組合：00、01、 10、1

28、1，一種表示無錯，其余三種指示一位錯碼的一種表示無錯，其余三種指示一位錯碼的 3種不同位置。種不同位置。 r個監(jiān)督關(guān)系式能指示一位錯碼有個監(jiān)督關(guān)系式能指示一位錯碼有 21 r 個可能位置個可能位置 LCU 46 一般說來，若碼長為一般說來，若碼長為n，信息位數(shù)為，信息位數(shù)為k，則監(jiān)督位，則監(jiān)督位 數(shù)為數(shù)為r=n-k。 如果希望如果希望用用r個監(jiān)督關(guān)系式來指示一位錯碼的個監(jiān)督關(guān)系式來指示一位錯碼的n種種 可能位置，可能位置，則要求：則要求： 21 21 r r n kr 或 LCU 47 3. 3. 對于（對于（7 7，4 4）線性分組碼，碼元為）線性分組碼，碼元為 如果傳送如果傳送a a6 6

29、,a,a5 5,a,a4 4,a,a3 3共共4 4位數(shù)據(jù)，要求能自動糾正一個位數(shù)據(jù)，要求能自動糾正一個 誤碼，須增加誤碼，須增加3 3位監(jiān)督碼位監(jiān)督碼a a2 2,a,a1 1,a,a0 0。 假設(shè)有三個相應(yīng)的監(jiān)督方程，假設(shè)有三個相應(yīng)的監(jiān)督方程， S1，S2，S3表示三個監(jiān)督關(guān)系表示三個監(jiān)督關(guān)系 式中的校正子。式中的校正子。 在接收端根據(jù)校正子的在接收端根據(jù)校正子的取值組取值組 合合能糾正某一位的錯誤。能糾正某一位的錯誤。 a6,a5,a4,a3,a2,a1,a0 LCU 48 監(jiān)督碼監(jiān)督碼: : 3460 3561 4562 aaaa aaaa aaaa 03463 13562 24561

30、 aaaaS aaaaS aaaaS 由上表得到關(guān)系式：由上表得到關(guān)系式： 0 0 0 LCU 49 在發(fā)送端編碼時，信息位在發(fā)送端編碼時，信息位a6,a5, a4,a3的值決定于輸?shù)闹禌Q定于輸 入信號，因此它們是隨機(jī)的。入信號，因此它們是隨機(jī)的。監(jiān)督位監(jiān)督位a2,a1,a0應(yīng)根據(jù)應(yīng)根據(jù) 信息位的取值按監(jiān)督關(guān)系來確定信息位的取值按監(jiān)督關(guān)系來確定。 a2a1a0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 a6a5a4a3 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1

31、 1 LCU 50 接收端收到每個碼組后，接收端收到每個碼組后，先按式計算出先按式計算出S1,S2,S3，再，再 按表判斷錯碼情況按表判斷錯碼情況。 例如：接收碼組為例如：接收碼組為000 0011 則則S1？ S2？ S3？ LCU 51 7.3.2 7.3.2 線性分組碼的一般原理線性分組碼的一般原理 從上節(jié)例子可以看出，線性分組碼的監(jiān)督方程可從上節(jié)例子可以看出，線性分組碼的監(jiān)督方程可 以用矩陣形式來表達(dá)（以用矩陣形式來表達(dá)（無誤碼時，下式成立）：無誤碼時，下式成立）： 6 5 4 3 2 1 0 11101000 11010100 10110010 a a a a a a a 1 1、監(jiān)

32、督矩陣、監(jiān)督矩陣 LCU 52 設(shè)發(fā)送序列為設(shè)發(fā)送序列為A A，則監(jiān)督方程也可以寫為：，則監(jiān)督方程也可以寫為： 000O 行數(shù)就是監(jiān)督關(guān)系式的數(shù)行數(shù)就是監(jiān)督關(guān)系式的數(shù) 目目 每行中每行中“1 1”的數(shù)目表示相的數(shù)目表示相 應(yīng)碼元之間存在的監(jiān)督應(yīng)碼元之間存在的監(jiān)督 關(guān)系關(guān)系 TT H AO 6543210 Aaaaaaaa 其中 1110 100 1101 010 1011 001 H LCU 53 式中的系數(shù)矩陣稱為式中的系數(shù)矩陣稱為，用，用H表示。如果用表示。如果用 虛線分為兩部分，左邊為虛線分為兩部分，左邊為P矩陣，是一個矩陣，是一個r*k階矩階矩 陣；右邊為陣；右邊為Ir矩陣，是一個矩陣

33、，是一個r*r階單位方陣。這種階單位方陣。這種 形式的形式的H矩陣也被稱為矩陣也被稱為典型陣。典型陣。 1110 100 1101 010 1011 001 H Ir P LCU 54 已知監(jiān)督方程和信號碼元時可以已知監(jiān)督方程和信號碼元時可以按下式按下式算出算出監(jiān)督碼元監(jiān)督碼元，式，式 中用的是中用的是P矩陣矩陣。 或者用下式來計算，式中的矩陣是或者用下式來計算，式中的矩陣是P的轉(zhuǎn)置矩陣，的轉(zhuǎn)置矩陣， 稱為稱為Q矩陣矩陣。 6 2 5 1 4 0 3 1110 1101 1011 a a a a a a a 2106543 111 110 101 011 aaaaaaa 2 2、生成矩陣、生成

34、矩陣 Q P LCU 55 在在Q的左邊加一個的左邊加一個k*k階單位方陣，就生成階單位方陣，就生成 一個新的矩陣一個新的矩陣G。 1101000 1010100 0110010 1110001 G 這個新矩陣這個新矩陣G稱為稱為生成矩陣生成矩陣，因為可由它，因為可由它 產(chǎn)生整個碼組產(chǎn)生整個碼組A。 6543 AaaaaG Ik LCU 56 監(jiān)督矩陣監(jiān)督矩陣生成矩陣生成矩陣 r HPI T QP k GI Q LCU 例題：已知某線性碼的監(jiān)督矩陣?yán)}：已知某線性碼的監(jiān)督矩陣 求其典型監(jiān)督矩陣、生成矩陣、該碼的最小距求其典型監(jiān)督矩陣、生成矩陣、該碼的最小距 離和糾錯能力離和糾錯能力 57 00

35、01 111 0110 011 1010 101 H 0111 100 010 1101 H 1000 011 0010 0001 G 最小距離為最小距離為3 3， 糾正糾正1 1位錯碼位錯碼 LCU 58 3 3 校正子校正子 設(shè)發(fā)送碼組設(shè)發(fā)送碼組A為一為一n列的行矩陣，發(fā)送碼組在傳列的行矩陣，發(fā)送碼組在傳 輸過程中出現(xiàn)了誤碼，接收端收到了輸過程中出現(xiàn)了誤碼，接收端收到了B矩陣，也是矩陣，也是 一一n列的行矩陣。列的行矩陣。 設(shè)收發(fā)碼組之差設(shè)收發(fā)碼組之差E=B-A（模（模2），稱為），稱為錯誤圖樣錯誤圖樣。 1230 ,. 0, 1, nnn ii i ii Eeeee ba e ba 當(dāng)

36、當(dāng) LCU 59 校正子校正子S可以根據(jù)可以根據(jù)接收序列接收序列B和和H矩陣矩陣來計算。來計算。 () TT TT TT SBHAE H AHEH OEHEH 可見校正子只與錯誤圖樣有關(guān)，與發(fā)送序列可見校正子只與錯誤圖樣有關(guān)，與發(fā)送序列 無關(guān)，是一個信道參數(shù)。無關(guān)，是一個信道參數(shù)。 u 如果不出現(xiàn)誤碼，校正子如果不出現(xiàn)誤碼，校正子S=0。 u 如果有誤碼，通過計算校正子如果有誤碼，通過計算校正子S來指示誤碼的來指示誤碼的 位置和糾正誤碼。位置和糾正誤碼。 LCU 60 舉例：設(shè)發(fā)送的序列舉例：設(shè)發(fā)送的序列A=0001011 錯誤圖樣錯誤圖樣 E=0001000 接收到的序列接收到的序列B=00

37、00011，計算校正子：，計算校正子： 100 010 001 110 101 011 111 1100000 T HBS =(0 1 1) 指示指示a3有錯誤有錯誤 LCU 61 1.漢明碼是漢明碼是1950年由年由美國貝爾實驗室美國貝爾實驗室漢明提出來的，漢明提出來的， 是第一個設(shè)計用來糾正錯誤的線性分組碼，漢明碼是第一個設(shè)計用來糾正錯誤的線性分組碼，漢明碼 被廣泛用于數(shù)字通信和數(shù)據(jù)存儲系統(tǒng)中。被廣泛用于數(shù)字通信和數(shù)據(jù)存儲系統(tǒng)中。 7.3.3 7.3.3 漢明（漢明（Hamming) )碼碼 LCU 62 2.漢明碼（漢明碼（n,k)是一種可用于糾正是一種可用于糾正1個隨機(jī)錯誤的循環(huán)個隨機(jī)

38、錯誤的循環(huán) 編碼。一般漢明碼的參數(shù)如下編碼。一般漢明碼的參數(shù)如下： 碼長碼長: n=2r-1 信息位信息位: k=2r-1-r 最小碼距：最小碼距： d0=3，通常用于通常用于FEC系統(tǒng)系統(tǒng) 漢明碼的編碼效率漢明碼的編碼效率 r rr k2 -1-rr =1- n2 -12 -1 LCU 63 糾錯一位糾錯一位的一般漢明碼結(jié)構(gòu)的一般漢明碼結(jié)構(gòu) 監(jiān)督位監(jiān)督位r信息位信息位k碼字長度碼字長度n 347 41115 52631 65763 LCU 64 監(jiān)督矩陣監(jiān)督矩陣：它的：它的n列分別由全零之外的列分別由全零之外的2r-1個個r 位碼組構(gòu)成，并且每個碼組只出現(xiàn)一次。如位碼組構(gòu)成，并且每個碼組只出

39、現(xiàn)一次。如 與前不同的另一個監(jiān)督矩陣：與前不同的另一個監(jiān)督矩陣： 1110 100 0111 010 1101 001 H LCU 65 循環(huán)碼是線性分組碼中的一類，是以現(xiàn)代代數(shù)理論循環(huán)碼是線性分組碼中的一類，是以現(xiàn)代代數(shù)理論 作為基礎(chǔ)建立起來的。作為基礎(chǔ)建立起來的。 循環(huán)碼的編碼和譯碼設(shè)備相對簡單循環(huán)碼的編碼和譯碼設(shè)備相對簡單 循環(huán)碼的檢錯和糾錯能力較強(qiáng)，常用于循環(huán)碼的檢錯和糾錯能力較強(qiáng)，常用于CRCCRC校驗。校驗。 7.4 循環(huán)碼概述循環(huán)碼概述 LCU 66 7.4 7.4 循環(huán)碼內(nèi)容循環(huán)碼內(nèi)容 1.循環(huán)碼的基本概念循環(huán)碼的基本概念 2.循環(huán)碼的性質(zhì)循環(huán)碼的性質(zhì) 3.循環(huán)碼的生成矩陣循環(huán)

40、碼的生成矩陣 4.尋找任一尋找任一(n,k)循環(huán)碼的生成多項式循環(huán)碼的生成多項式 5.循環(huán)碼的監(jiān)督矩陣循環(huán)碼的監(jiān)督矩陣 6.循環(huán)碼的編碼方法循環(huán)碼的編碼方法 7.循環(huán)碼的解碼方法循環(huán)碼的解碼方法 LCU 67 循環(huán)碼除了具有線性碼的一般性質(zhì)外，還具有循循環(huán)碼除了具有線性碼的一般性質(zhì)外，還具有循 環(huán)性，即任一碼組環(huán)性，即任一碼組循環(huán)移動一位循環(huán)移動一位( (將最右端的碼元將最右端的碼元 移至左端，或反之移至左端，或反之) )以后，仍為該碼中的一個碼組以后，仍為該碼中的一個碼組。 即若即若 是許用碼組，則是許用碼組，則 也是許用碼組。也是許用碼組。（不論左移、右移和移位位數(shù)）（不論左移、右移和移位

41、位數(shù)） 120 ,., nn Taaa 201 ,., nn Taa a 一、一、循環(huán)碼的基本概念循環(huán)碼的基本概念 LCU 68 循環(huán)碼舉例循環(huán)碼舉例(7,3)循環(huán)碼（左移）循環(huán)碼（左移） 0010111 01011101011100 011100111100101100101 1001011 0000000 循環(huán)碼舉例循環(huán)碼舉例2(6,3)循環(huán)碼（循環(huán)碼（P312） LCU 69 例如例如 A=1100101 120 ,., nn Taaa 121 1210 ( ). nn nn T xaxaxa xa 1 1010011)( 256 123456 xxx xxxxxxxT 循環(huán)碼的系數(shù)矩陣

42、：循環(huán)碼的系數(shù)矩陣： 碼多項式：碼多項式： LCU 70 a.線性線性碼碼（封閉性、單位元素、逆元素、結(jié)合律）（封閉性、單位元素、逆元素、結(jié)合律） b.碼多項式按模運算，碼多項式按模運算，模為模為xn+1 121 1210 ( ). nn nn T xaxaxa xa 二、循環(huán)碼的性質(zhì)二、循環(huán)碼的性質(zhì) LCU 71 n p Q n m ( )( ) ( ) ( )( ) F xR x Q x N xN x LCU 72 碼多項式系數(shù)仍按碼多項式系數(shù)仍按模模2 2運算，即運算，即只取值只取值0 0和和1 1。 例如例如 有有 1 1 1 1 11 1 33 3 3 3 xx x x x 33 1

43、(1)xx模 模模2加加 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0 模模2乘乘00 = 001 = 010 = 011 = 1 注意注意:模模2運算加法和減法是等價的，在式子中通運算加法和減法是等價的，在式子中通 常用加法運算符，具體模常用加法運算符，具體模2運算的規(guī)則定義如下：運算的規(guī)則定義如下： 一般情況下，取碼多項式的模為一般情況下，取碼多項式的模為xn+1 LCU 73 若若T（X）是長度為）是長度為n的循環(huán)碼一個許用碼組，則的循環(huán)碼一個許用碼組，則 左移左移i位后的位后的xiT（X）按模）按模xn+1 運算也是一個許運算也是一個許 用碼組。即若用

44、碼組。即若 xiT（X） T (X)，則則T(X)也是也是 一個許用碼組。一個許用碼組。 12 1210 ( ). nn nn T xaxaxa xa 121 1201 ( ). nnii n in inn i T xaxaxa xa xa 12 12 11 110 ( ). . in in i nn nnii n in i x T xaxax axaxa xa x c.循環(huán)移位循環(huán)移位 LCU 74 例如某循環(huán)碼例如某循環(huán)碼1100101， 則則T(X)=X6+X5+X2+1, XT(X)=X7+X6+X3+X, 1 1 11 36 7 367 7 XXX X XXXX X 余數(shù) 余數(shù)構(gòu)成的

45、碼是余數(shù)構(gòu)成的碼是1001011，正好是左移一位的結(jié)果，正好是左移一位的結(jié)果 LCU 75 例如某循環(huán)碼例如某循環(huán)碼1100101， 則則T(X)=X6+X5+X2+1,左移兩位左移兩位 余數(shù)構(gòu)成的碼是余數(shù)構(gòu)成的碼是0010111 重要結(jié)論：重要結(jié)論： 即即 n位碼組循環(huán)左移位碼組循環(huán)左移i位等價于位等價于 相應(yīng)多項式乘以相應(yīng)多項式乘以xi后取后取xn+1的模所得余數(shù)的模所得余數(shù)。 LCU 76 循環(huán)碼舉例循環(huán)碼舉例( (7,3) )循環(huán)碼循環(huán)碼 編號編號a6a5a4a3a2a1a0編號編號a6a5a4a3a2a1a0 0000000041001011 1001011151011100 201

46、0100061100101 3011100171110010 LCU 77 什么是生成矩陣？什么是生成矩陣？可以產(chǎn)生整個碼組的矩陣?？梢援a(chǎn)生整個碼組的矩陣。 有了生成矩陣有了生成矩陣G，就可以由，就可以由k個信息位得出整個信息位得出整 個碼組，而且生成矩陣個碼組，而且生成矩陣G的每一行都是一個碼組。的每一行都是一個碼組。 若能找到若能找到k個線性無關(guān)的碼組個線性無關(guān)的碼組,就能構(gòu)成矩陣就能構(gòu)成矩陣G。 否則，給定的信息位與編出的碼組就不是一一對否則，給定的信息位與編出的碼組就不是一一對 應(yīng)的。應(yīng)的。 三、循環(huán)碼的生成矩陣三、循環(huán)碼的生成矩陣G G LCU 78 1.在循環(huán)碼中，一個在循環(huán)碼中，

47、一個(n，k)碼有碼有2k 個不同碼組，個不同碼組， 若用若用g(x)表示其中表示其中前前(k-1)位皆為位皆為0的碼組的碼組，即，即 則則 都是碼組，而都是碼組，而 且這且這k個碼組是線性無關(guān)的。因此可以個碼組是線性無關(guān)的。因此可以 用來構(gòu)成用來構(gòu)成循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣G。 21 ( ),( ),( ).,( ) k g x xg x x g xxg x g(x)=0 1x x k位位 n-k位位 LCU 79 2.生成多項式生成多項式g(x) ： l連連0長度最多有長度最多有k-1位，滿足位，滿足常數(shù)項常數(shù)項a0=1； 如如001 1101 因為循環(huán)碼中除全因為循環(huán)碼中除全“0

48、”碼外，再沒有連續(xù)碼外，再沒有連續(xù)k位均為位均為“0” 的碼組。否則會出現(xiàn)的碼組。否則會出現(xiàn)k個信息位全為個信息位全為“0”，但是監(jiān)督位，但是監(jiān)督位 不為不為“0”的碼組。的碼組。 l唯一的唯一的(n-k)次多項式次多項式(在非零碼組中次在非零碼組中次 數(shù)最低數(shù)最低)； lg(x)必須是必須是xn+1的因式的因式（見后面分析）。（見后面分析）。 42 432 ( )1 ( )1 g xxxx g xxxx LCU 80 循環(huán)碼生成多項式的定義：循環(huán)碼生成多項式的定義： 前前k-1位為位為0，第，第k位和第位和第n位為位為1的許用碼組可以的許用碼組可以 用一個碼多項式用一個碼多項式g(x)來標(biāo)識

49、，稱為來標(biāo)識，稱為循環(huán)碼的生成多循環(huán)碼的生成多 項式項式。 （7,k）g(x) (7,6) x+1 (7,4) x3+x2+1或或x3+x+1 (7,3) (x+1)(x3+x2+1)或或 (x3+x+1)(x+1) (7,1) (x3+x+1)(x3+x2+1) LCU 81 例例1 1 已知（已知（7 7，4 4）循環(huán)碼的全部碼組為）循環(huán)碼的全部碼組為 0000000 1000101 0001011 1001110 0010110 1010011 0011101 1011000 0100111 1100010 0101100 1101001 0110001 1110100 0111010

50、1111111 寫出該循環(huán)碼的循環(huán)圈及生成多項式寫出該循環(huán)碼的循環(huán)圈及生成多項式 LCU 82 )( )( )( )( 2 1 xg xxg xgx xgx G k k 一旦確定了一旦確定了g(x)，則整個，則整個(n,k)循環(huán)碼就被循環(huán)碼就被 確定了。因此確定了。因此,循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣G可以寫可以寫 成成 LCU 83 利用多項式表示利用多項式表示(7,3)循環(huán)碼：循環(huán)碼： 654 2 654 2 654 2 654 ( ) ( ) ( ) ( ) ( ) ( )( )( ) ()( ) T xa a a G x x g x a a axg x g x a x g xa xg

51、 xa g x a xa xag x 1.所有碼多項式所有碼多項式T(x) 都可以被都可以被g(x)整除整除 2.任一次數(shù)不大于任一次數(shù)不大于(k-1) 的多項式乘的多項式乘g(x)都是都是 碼多項式碼多項式 LCU 84 這個生成矩陣不是系統(tǒng)碼的典型生成矩陣，可以通這個生成矩陣不是系統(tǒng)碼的典型生成矩陣，可以通 過行變換（第一行加上第三行），變換成系統(tǒng)碼的過行變換（第一行加上第三行），變換成系統(tǒng)碼的 生成矩陣：生成矩陣： 0010111 0101110 1011100 )( )( )( 2 xg xxg xgx G 將此將此g(x)代入上式，得到代入上式，得到 例例2 (7,3)循環(huán)碼循環(huán)碼,

52、 唯一的一個唯一的一個(n-k)次碼多項式代表次碼多項式代表 的碼組是的碼組是0010111，寫出它的生成矩陣，寫出它的生成矩陣 LCU 85 1001011 0101110 0010111 G 利用下式可以產(chǎn)生全部許用碼組利用下式可以產(chǎn)生全部許用碼組 6543210654 aaaaaa aaaaG LCU 86 因為任一碼多項式因為任一碼多項式T(x)都是都是g(x)的倍式的倍式，所以有，所以有 四、如何尋找任一（四、如何尋找任一（n,k）循環(huán)碼的生成多項式）循環(huán)碼的生成多項式 1. g(x)本身也是一個碼組，其次數(shù)為本身也是一個碼組，其次數(shù)為n-k次。左移次。左移k位位 后后xkg(x)是

53、是n次多項式（一許用碼組次多項式（一許用碼組 ），在模），在模 xn+1 運算下，假設(shè)運算下，假設(shè) ( )( )(1) kn x g xT xx模 1 )( )( 1 )( nn k x xT xQ x xgx 即即 ( )( )( )T xh xg x ( )T x LCU 87 因為因為xkg(x)是是n次的，所以次的，所以Q(x)=1 。所以。所以 即即 g(x)是是xn+1的一個的一個(n-k)次因式次因式。 這樣就這樣就 可以通過對可以通過對xn+1的因式分解得到的因式分解得到g(x). 1 )()( 1 1 )( 1 1 )( nnn k x xgxh x xT x xgx 1(

54、)( ) nk xg x xh x LCU 88 2. 舉例：模為舉例：模為X7+1，構(gòu)成的循環(huán)碼，構(gòu)成的循環(huán)碼 x7+1=(x+1)(x3+x+1)(x3+x2+1) （7,k）g(x) (7,6) x+1 (7,4) x3+x2+1或或x3+x+1 (7,3) (x+1)(x3+x2+1)或或 (x3+x+1)(x+1) (7,1) (x3+x+1)(x3+x2+1) LCU 89 例題例題3：對于一（：對于一（7，3）循環(huán)碼，其生成多）循環(huán)碼，其生成多 項式項式 g(x)=(x3+x+1)(x+1) 求生成矩陣求生成矩陣G和信息碼和信息碼111,110對應(yīng)的碼組對應(yīng)的碼組 26542 5

55、43 432 ( )00 0 ( )( )000 ( )0 00 1 x g xxxxx G Xxg xxxxx g xxxx 11101001001110 01110100100111 00111010011101 G LCU 90 假設(shè)信息碼是假設(shè)信息碼是111，生成序列為，生成序列為 1 0 0 1 1 1 0 1 1 10 1 0 0 1 1 11 1 1 0 1 0 0 0 0 1 1 1 0 1 A 假設(shè)信息碼是假設(shè)信息碼是110，生成序列為，生成序列為 1 0 0 1 1 1 0 1 1 00 1 0 0 1 1 11 1 0 1 0 0 1 0 0 1 1 1 0 1 A LC

56、U 91 五五. .監(jiān)督矩陣監(jiān)督矩陣 得到得到k次多項式次多項式h(x)稱為監(jiān)督多項式。設(shè)稱為監(jiān)督多項式。設(shè) 1()() n xgx h x由 10 10 (). (). nk nk k k gxgxg xg h xh xh xh 可得可得00 0110 021120 10211 1 1 0 0 . .0 nkk nnnkk gh g h g hg h g hg hg h ghghgh LCU 92 由此可得到循環(huán)碼的監(jiān)督矩陣由此可得到循環(huán)碼的監(jiān)督矩陣(r行行n列列) 01 01 01 k k k h hh h hh H h hh 例：（例：（7，3）循環(huán)碼）循環(huán)碼的生成多項式為的生成多項式為

57、g(x) x4+x2+x+1，寫出它的監(jiān)督矩陣，寫出它的監(jiān)督矩陣 先得到先得到h(x)x3+x+1 1101000 0110100 0011010 0001101 H 也可利用也可利用G與與H的關(guān)系求解！的關(guān)系求解！ 1101000 0110100 1110010 1010001 H LCU 93 六、循環(huán)碼的編碼方法六、循環(huán)碼的編碼方法 LCU 94 3.編出的碼組編出的碼組 為：為： ( )T x 1.用用 乘信息碼多項式乘信息碼多項式 （相當(dāng)于添加（相當(dāng)于添加 n-k個個0，例如，例如g(x)x4+x3+x2+1時時發(fā)送發(fā)送100） ( )m x n k x 2.用用 除除 ，得到商，得

58、到商 和和 ，即，即( )g x( ) n k xm x ( )Q x( )r x ( )( )( ) n k T xxm xr x ( )( ) ( ) ( )( ) n k xm xr x Q x g xg x 信息位信息位 監(jiān)督位監(jiān)督位 LCU 95 4.將此余式加于信息位之后作為監(jiān)督位將此余式加于信息位之后作為監(jiān)督位 即將即將r(x)與與 相加，相加， 得到的多項式必為得到的多項式必為 一碼多項式，因為它必能被一碼多項式，因為它必能被g(x)整除，且商的整除，且商的 次數(shù)不大于次數(shù)不大于(k-1)。 ( ) r x m x LCU 96 監(jiān)督位 信息位信息位 例例3 (7,3)循環(huán)碼循

59、環(huán)碼 m(x)=x2+x, g(x)= x4 +x2+ x+1 解解 5637 )(xxxmx 1)( )( 24 56 xxx xx xg xmx kn 1 1 1 24 2 2 xxx x xx r(x) 11001011)( 256 xxxxT LCU 97 例例4：對于一個：對于一個(15,11)循環(huán)碼，發(fā)送的信息序循環(huán)碼，發(fā)送的信息序 列列I(x)=11101010001，其生成多項式，其生成多項式 g(x)=x4+x+1， 寫出它的循環(huán)碼組。寫出它的循環(huán)碼組。 15 11109864 1413121084 ( )(1) n k xI xxxxxxx xxxxxx 3 ( )R xx

60、x( )( )( ) n k F xxI xR x xxxxxxxx 111010100011010F LCU 98 （7 7，3 3）循環(huán)碼編碼的硬件實現(xiàn)）循環(huán)碼編碼的硬件實現(xiàn)x x4 4+x+x2 2+x+1+x+1 a+b+cd+ 輸入m 輸出f e S u 硬件實現(xiàn)循環(huán)碼編碼，可以由除法電路實現(xiàn)。除法電路的主硬件實現(xiàn)循環(huán)碼編碼，可以由除法電路實現(xiàn)。除法電路的主 體由一些體由一些移存器和模移存器和模2加法器加法器組成。組成。 u g(x)的次數(shù)等于移位寄存器的級數(shù)；另外有一雙刀雙擲開關(guān)的次數(shù)等于移位寄存器的級數(shù)；另外有一雙刀雙擲開關(guān) S。如當(dāng)如當(dāng)(7,4)循環(huán)碼