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

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

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

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

4、錯(cuò)控制編碼來(lái)檢錯(cuò)和糾錯(cuò)的原因用差錯(cuò)控制編碼來(lái)檢錯(cuò)和糾錯(cuò)的原因 LCU 8 u在中等傳輸速率（在中等傳輸速率（1200/2400波特）下，對(duì)于干線波特）下，對(duì)于干線 有線載波信道，有線載波信道， Pe約為約為10-410-6的數(shù)量級(jí)，對(duì)于無(wú)的數(shù)量級(jí)，對(duì)于無(wú) 線短波通信，線短波通信， Pe只有只有10-210-3的數(shù)量級(jí)。的數(shù)量級(jí)。 u對(duì)碼速為對(duì)碼速為64kbps的系統(tǒng)的系統(tǒng),國(guó)際電報(bào)電話咨詢委員會(huì)國(guó)際電報(bào)電話咨詢委員會(huì) 把誤碼率把誤碼率10-3的稱為嚴(yán)重誤碼。的稱為嚴(yán)重誤碼。 u我國(guó)長(zhǎng)途光纜通信系統(tǒng)的進(jìn)網(wǎng)要求之一：誤碼性能我國(guó)長(zhǎ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ò)展信道頻帶寬度等辦法來(lái)減等辦法來(lái)減 少少加性干擾。加性干擾。 采用上述方法仍難以滿足要求時(shí)，必須采用上述方法仍難以滿足要求時(shí)，必須 采用差錯(cuò)控制措施，即用采用差錯(cuò)控制措施，即用差錯(cuò)控制編碼差錯(cuò)控制編碼來(lái)來(lái) 和和。 LCU 10 1 1、隨機(jī)信道隨機(jī)信道：誤碼的出現(xiàn)是隨機(jī)的，誤碼的出現(xiàn)是隨機(jī)的，誤碼

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

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

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

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

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

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

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

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

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

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

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

17、值。有較大實(shí)用價(jià)值。 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 幾種常用的簡(jiǎn)單檢錯(cuò)碼幾種常用的簡(jiǎn)單檢錯(cuò)碼 1、奇偶監(jiān)督碼、奇偶監(jiān)督碼 2、二維奇偶監(jiān)督碼、二維奇偶監(jiān)督碼 3、恒比碼、恒比碼 4、正反碼、正反碼 LCU 35 奇偶監(jiān)督碼的編碼規(guī)則是在信息位后加上奇偶監(jiān)督碼的編碼規(guī)則是在信息位后加上一位監(jiān)督位一位監(jiān)督位形成形成 具有檢錯(cuò)能力的碼。具有檢錯(cuò)能力的碼。 如果是偶校驗(yàn)，則要求整個(gè)碼字中如果是偶校驗(yàn)，則要求整個(gè)碼字中“1”的個(gè)數(shù)為偶數(shù)的個(gè)數(shù)為偶數(shù)，例，例 如如 1 0 1 1 0 0

18、 1 0 當(dāng)傳輸過(guò)程中當(dāng)傳輸過(guò)程中出現(xiàn)奇數(shù)個(gè)錯(cuò)誤出現(xiàn)奇數(shù)個(gè)錯(cuò)誤，接收端都能發(fā)現(xiàn)有無(wú)錯(cuò)誤，但，接收端都能發(fā)現(xiàn)有無(wú)錯(cuò)誤，但 不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤，比如，比如 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 有錯(cuò)有錯(cuò) 1 1 1 0 0 1 1 0 有錯(cuò)有錯(cuò) 1 0 1 0 0 1 1 0 不能確定不能確定 如果是奇校驗(yàn)，則要求整個(gè)碼字中如果是奇校驗(yàn)，則要求整個(gè)碼字中“1”的個(gè)數(shù)為奇數(shù)的個(gè)數(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、若干個(gè)它是將若干個(gè) 信息碼字按每個(gè)碼字一行排列成矩陣形式，然后在每一行和每信息碼字按每個(gè)碼字一行排列成矩陣形式，然后在每一行和每 一列的碼元后面附加一位奇（偶）監(jiān)督碼元。一列的碼元后面附加一位奇（偶）監(jiān)督碼元。 行列奇偶監(jiān)督碼不但能檢測(cè)出某一行或某一列的所有奇數(shù)行列奇偶監(jiān)督碼不但能檢測(cè)出某一行或某一列的所有奇數(shù) 個(gè)錯(cuò)誤，有時(shí)還能檢測(cè)出某些偶數(shù)個(gè)錯(cuò)誤。個(gè)錯(cuò)誤，有時(shí)還能檢測(cè)出某些偶數(shù)個(gè)錯(cuò)誤。 不能檢測(cè)構(gòu)成矩形四角的錯(cuò)碼。不能檢測(cè)構(gòu)成矩形四角的錯(cuò)碼。 信息碼元信息碼元 監(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 恒比碼是從某種特定長(zhǎng)度的碼字中選出那些恒比碼是從某種特定長(zhǎng)度的碼字中選出那些“1 1”的個(gè)數(shù)與的個(gè)數(shù)與 “0 0”的個(gè)數(shù)保持恒定比例的碼字作為許用碼字。的個(gè)數(shù)保持恒定比例的碼字作為許用碼字。 五單位數(shù)字保護(hù)電碼五單位數(shù)字保護(hù)

21、電碼 碼字長(zhǎng)度為碼字長(zhǎng)度為5，只選用碼字中含有，只選用碼字中含有三個(gè)三個(gè)“1”和兩個(gè)和兩個(gè)“0”的碼字作為許用的碼字作為許用 碼字來(lái)表示碼字來(lái)表示10個(gè)阿拉伯?dāng)?shù)字個(gè)阿拉伯?dāng)?shù)字1，2，9，0，這種碼亦稱，這種碼亦稱“5中取中取3碼碼”。 例：中文電報(bào)編碼：例：中文電報(bào)編碼： 通通 信信 6639 0207 10101 10101 10110 10011 01101 11001 01101 11100 國(guó)際電報(bào)通信中廣泛采用的是國(guó)際電報(bào)通信中廣泛采用的是“7中中 取取3碼碼”，許用碼字共有個(gè)，可分別表，許用碼字共有個(gè)，可分別表 示示26個(gè)字母和其它的一些符號(hào)。個(gè)字母和其它的一些符號(hào)。 數(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)單的能夠糾正錯(cuò)碼的編碼。正反碼是一種簡(jiǎn)單的能夠糾正錯(cuò)碼的編碼。其中監(jiān)督位數(shù)與信其中監(jiān)督位數(shù)與信 息位數(shù)相同，監(jiān)督碼元與信息碼元相同（是信息碼的重復(fù)）或者息位數(shù)相同，監(jiān)督碼元與信息碼元相同（是信息碼的重復(fù)）或者 相反（是信息碼的反碼），則由信息碼中相反（是信息碼的反碼），則由信息碼

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

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

25、=00000 校驗(yàn)碼組校驗(yàn)碼組 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é)中把對(duì)某種運(yùn)算滿足以下條件的一類集合稱為代數(shù)學(xué)中把對(duì)某種運(yùn)算滿足以下條件的一類集合稱為群群： u封閉性封閉性：集合中任意兩個(gè)元素經(jīng)該運(yùn)算后仍為該集合的元素：集合中任意兩個(gè)元素經(jīng)該運(yùn)算后仍為該集合

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

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

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

29、,a,a5 5,a,a4 4,a,a3 3共共4 4位數(shù)據(jù)，要求能自動(dòng)糾正一個(gè)位數(shù)據(jù)，要求能自動(dòng)糾正一個(gè) 誤碼，須增加誤碼，須增加3 3位監(jiān)督碼位監(jiān)督碼a a2 2,a,a1 1,a,a0 0。 假設(shè)有三個(gè)相應(yīng)的監(jiān)督方程，假設(shè)有三個(gè)相應(yīng)的監(jiān)督方程， S1，S2，S3表示三個(gè)監(jiān)督關(guān)系表示三個(gè)監(jiān)督關(guān)系 式中的校正子。式中的校正子。 在接收端根據(jù)校正子的在接收端根據(jù)校正子的取值組取值組 合合能糾正某一位的錯(cuò)誤。能糾正某一位的錯(cuò)誤。 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ā)送端編碼時(shí)，信息位在發(fā)送端編碼時(shí)，信息位a6,a5, a4,a3的值決定于輸?shù)闹禌Q定于輸 入信號(hào)，因此它們是隨機(jī)的。入信號(hào)，因此它們是隨機(jī)的。監(jiān)督位監(jiān)督位a2,a1,a0應(yīng)根據(jù)應(yīng)根據(jù) 信息位的取值按監(jiān)督關(guān)系來(lái)確定信息位的取值按監(jiān)督關(guān)系來(lái)確定。 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 接收端收到每個(gè)碼組后，接收端收到每個(gè)碼組后，先按式計(jì)算出先按式計(jì)算出S1,S2,S3，再，再 按表判斷錯(cuò)碼情況按表判斷錯(cuò)碼情況。 例如：接收碼組為例如：接收碼組為000 0011 則則S1？ S2？ S3？ LCU 51 7.3.2 7.3.2 線性分組碼的一般原理線性分組碼的一般原理 從上節(jié)例子可以看出，線性分組碼的監(jiān)督方程可從上節(jié)例子可以看出，線性分組碼的監(jiān)督方程可 以用矩陣形式來(lái)表達(dá)（以用矩陣形式來(lái)表達(dá)（無(wú)誤碼時(shí)，下式成立）：無(wú)誤碼時(shí)，下式成立）： 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)督方程也可以寫(xiě)為：，則監(jiān)督方程也可以寫(xiě)為： 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矩陣，是一個(gè)矩陣，是一個(gè)r*k階矩階矩 陣；右邊為陣；右邊為Ir矩陣，是一個(gè)矩陣

33、，是一個(gè)r*r階單位方陣。這種階單位方陣。這種 形式的形式的H矩陣也被稱為矩陣也被稱為典型陣。典型陣。 1110 100 1101 010 1011 001 H Ir P LCU 54 已知監(jiān)督方程和信號(hào)碼元時(shí)可以已知監(jiān)督方程和信號(hào)碼元時(shí)可以按下式按下式算出算出監(jiān)督碼元監(jiān)督碼元，式，式 中用的是中用的是P矩陣矩陣。 或者用下式來(lái)計(jì)算，式中的矩陣是或者用下式來(lái)計(jì)算，式中的矩陣是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的左邊加一個(gè)的左邊加一個(gè)k*k階單位方陣，就生成階單位方陣，就生成 一個(gè)新的矩陣一個(gè)新的矩陣G。 1101000 1010100 0110010 1110001 G 這個(gè)新矩陣這個(gè)新矩陣G稱為稱為生成矩陣生成矩陣，因?yàn)榭捎伤?，因?yàn)榭捎伤?產(chǎn)生整個(gè)碼組產(chǎn)生整個(gè)碼組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)督矩陣、生成矩陣、該碼的最小距 離和糾錯(cuò)能力離和糾錯(cuò)能力 57 00

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

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

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

38、錯(cuò)誤的循環(huán) 編碼。一般漢明碼的參數(shù)如下編碼。一般漢明碼的參數(shù)如下： 碼長(zhǎng)碼長(zhǎng): 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 糾錯(cuò)一位糾錯(cuò)一位的一般漢明碼結(jié)構(gòu)的一般漢明碼結(jié)構(gòu) 監(jiān)督位監(jiān)督位r信息位信息位k碼字長(zhǎng)度碼字長(zhǎng)度n 347 41115 52631 65763 LCU 64 監(jiān)督矩陣監(jiān)督矩陣：它的：它的n列分別由全零之外的列分別由全零之外的2r-1個(gè)個(gè)r 位碼組構(gòu)成，并且每個(gè)碼組只出現(xiàn)一次。如位碼組構(gòu)成，并且每個(gè)碼組只出

39、現(xiàn)一次。如 與前不同的另一個(gè)監(jiān)督矩陣：與前不同的另一個(gè)監(jiān)督矩陣： 1110 100 0111 010 1101 001 H LCU 65 循環(huán)碼是線性分組碼中的一類，是以現(xiàn)代代數(shù)理論循環(huán)碼是線性分組碼中的一類，是以現(xiàn)代代數(shù)理論 作為基礎(chǔ)建立起來(lái)的。作為基礎(chǔ)建立起來(lái)的。 循環(huán)碼的編碼和譯碼設(shè)備相對(duì)簡(jiǎn)單循環(huán)碼的編碼和譯碼設(shè)備相對(duì)簡(jiǎn)單 循環(huán)碼的檢錯(cuò)和糾錯(cuò)能力較強(qiáng)，常用于循環(huán)碼的檢錯(cuò)和糾錯(cuò)能力較強(qiáng)，常用于CRCCRC校驗(yàn)。校驗(yàn)。 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)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式 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)移動(dòng)一位循環(huán)移動(dòng)一位( (將最右端的碼元將最右端的碼元 移至左端，或反之移至左端，或反之) )以后，仍為該碼中的一個(gè)碼組以后，仍為該碼中的一個(gè)碼組。 即若即若 是許用碼組，則是許用碼組，則 也是許用碼組。也是許用碼組。（不論左移、右移和移位位數(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ù)矩陣： 碼多項(xiàng)式：碼多項(xiàng)式： LCU 70 a.線性線性碼碼（封閉性、單位元素、逆元素、結(jié)合律）（封閉性、單位元素、逆元素、結(jié)合律） b.碼多項(xiàng)式按模運(yùn)算，碼多項(xiàng)式按模運(yùn)算，模為模為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 碼多項(xiàng)式系數(shù)仍按碼多項(xiàng)式系數(shù)仍按模模2 2運(yùn)算，即運(yùn)算，即只取值只取值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運(yùn)算加法和減法是等價(jià)的，在式子中通運(yùn)算加法和減法是等價(jià)的，在式子中通 常用加法運(yùn)算符，具體模常用加法運(yùn)算符，具體模2運(yùn)算的規(guī)則定義如下：運(yùn)算的規(guī)則定義如下： 一般情況下，取碼多項(xiàng)式的模為一般情況下，取碼多項(xiàng)式的模為xn+1 LCU 73 若若T（X）是長(zhǎng)度為）是長(zhǎng)度為n的循環(huán)碼一個(gè)許用碼組，則的循環(huán)碼一個(gè)許用碼組，則 左移左移i位后的位后的xiT（X）按模）按模xn+1 運(yùn)算也是一個(gè)許運(yùn)算也是一個(gè)許 用碼組。即若用

44、碼組。即若 xiT（X） T (X)，則則T(X)也是也是 一個(gè)許用碼組。一個(gè)許用碼組。 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位等價(jià)于位等價(jià)于 相應(yīng)多項(xiàng)式乘以相應(yīng)多項(xiàng)式乘以xi后取后取xn+1的模所得余數(shù)的模所得余數(shù)。 LCU 76 循環(huán)碼舉例循環(huán)碼舉例( (7,3) )循環(huán)碼循環(huán)碼 編號(hào)編號(hào)a6a5a4a3a2a1a0編號(hào)編號(hào)a6a5a4a3a2a1a0 0000000041001011 1001011151011100 201

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

47、一個(gè)(n，k)碼有碼有2k 個(gè)不同碼組，個(gè)不同碼組， 若用若用g(x)表示其中表示其中前前(k-1)位皆為位皆為0的碼組的碼組，即，即 則則 都是碼組，而都是碼組，而 且這且這k個(gè)碼組是線性無(wú)關(guān)的。因此可以個(gè)碼組是線性無(wú)關(guān)的。因此可以 用來(lái)構(gòu)成用來(lái)構(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.生成多項(xiàng)式生成多項(xiàng)式g(x) ： l連連0長(zhǎng)度最多有長(zhǎng)度最多有k-1位，滿足位，滿足常數(shù)項(xiàng)常數(shù)項(xiàng)a0=1； 如如001 1101 因?yàn)檠h(huán)碼中除全因?yàn)檠h(huán)碼中除全“0

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

49、，稱為來(lái)標(biāo)識(shí)，稱為循環(huán)碼的生成多循環(huán)碼的生成多 項(xiàng)式項(xiàng)式。 （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 寫(xiě)出該循環(huán)碼的循環(huán)圈及生成多項(xiàng)式寫(xiě)出該循環(huán)碼的循環(huán)圈及生成多項(xiàng)式 LCU 82 )( )( )( )( 2 1 xg xxg xgx xgx G k k 一旦確定了一旦確定了g(x)，則整個(gè)，則整個(gè)(n,k)循環(huán)碼就被循環(huán)碼就被 確定了。因此確定了。因此,循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣G可以寫(xiě)可以寫(xiě) 成成 LCU 83 利用多項(xiàng)式表示利用多項(xiàng)式表示(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.所有碼多項(xiàng)式所有碼多項(xiàng)式T(x) 都可以被都可以被g(x)整除整除 2.任一次數(shù)不大于任一次數(shù)不大于(k-1) 的多項(xiàng)式乘的多項(xiàng)式乘g(x)都是都是 碼多項(xiàng)式碼多項(xiàng)式 LCU 84 這個(gè)生成矩陣不是系統(tǒng)碼的典型生成矩陣，可以通這個(gè)生成矩陣不是系統(tǒng)碼的典型生成矩陣，可以通 過(guò)行變換（第一行加上第三行），變換成系統(tǒng)碼的過(guò)行變換（第一行加上第三行），變換成系統(tǒng)碼的 生成矩陣：生成矩陣： 0010111 0101110 1011100 )( )( )( 2 xg xxg xgx G 將此將此g(x)代入上式，得到代入上式，得到 例例2 (7,3)循環(huán)碼循環(huán)碼,

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

53、是n次多項(xiàng)式（一許用碼組次多項(xiàng)式（一許用碼組 ），在模），在模 xn+1 運(yùn)算下，假設(shè)運(yùn)算下，假設(shè) ( )( )(1) kn x g xT xx模 1 )( )( 1 )( nn k x xT xQ x xgx 即即 ( )( )( )T xh xg x ( )T x LCU 87 因?yàn)橐驗(yàn)閤kg(x)是是n次的，所以次的，所以Q(x)=1 。所以。所以 即即 g(x)是是xn+1的一個(gè)的一個(gè)(n-k)次因式次因式。 這樣就這樣就 可以通過(guò)對(duì)可以通過(guò)對(duì)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：對(duì)于一（：對(duì)于一（7，3）循環(huán)碼，其生成多）循環(huán)碼，其生成多 項(xiàng)式項(xiàng)式 g(x)=(x3+x+1)(x+1) 求生成矩陣求生成矩陣G和信息碼和信息碼111,110對(duì)應(yīng)的碼組對(duì)應(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次多項(xiàng)式次多項(xiàng)式h(x)稱為監(jiān)督多項(xiàng)式。設(shè)稱為監(jiān)督多項(xiàng)式。設(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)碼的生成多項(xiàng)式為的生成多項(xiàng)式為

57、g(x) x4+x2+x+1，寫(xiě)出它的監(jiān)督矩陣，寫(xiě)出它的監(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.用用 乘信息碼多項(xiàng)式乘信息碼多項(xiàng)式 （相當(dāng)于添加（相當(dāng)于添加 n-k個(gè)個(gè)0，例如，例如g(x)x4+x3+x2+1時(shí)時(shí)發(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)與與 相加，相加， 得到的多項(xiàng)式必為得到的多項(xiàng)式必為 一碼多項(xiàng)式，因?yàn)樗啬鼙灰淮a多項(xiàng)式，因?yàn)樗啬鼙籫(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：對(duì)于一個(gè)：對(duì)于一個(gè)(15,11)循環(huán)碼，發(fā)送的信息序循環(huán)碼，發(fā)送的信息序 列列I(x)=11101010001，其生成多項(xiàng)式，其生成多項(xiàng)式 g(x)=x4+x+1， 寫(xiě)出它的循環(huán)碼組。寫(xiě)出它的循環(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)碼編碼的硬件實(shí)現(xiàn)）循環(huán)碼編碼的硬件實(shí)現(xiàn)x x4 4+x+x2 2+x+1+x+1 a+b+cd+ 輸入m 輸出f e S u 硬件實(shí)現(xiàn)循環(huán)碼編碼，可以由除法電路實(shí)現(xiàn)。除法電路的主硬件實(shí)現(xiàn)循環(huán)碼編碼，可以由除法電路實(shí)現(xiàn)。除法電路的主 體由一些體由一些移存器和模移存器和模2加法器加法器組成。組成。 u g(x)的次數(shù)等于移位寄存器的級(jí)數(shù)；另外有一雙刀雙擲開(kāi)關(guān)的次數(shù)等于移位寄存器的級(jí)數(shù)；另外有一雙刀雙擲開(kāi)關(guān) S。如當(dāng)如當(dāng)(7,4)循環(huán)碼