差錯控制編碼

1、1第九章第九章 差錯控制編碼差錯控制編碼主要內(nèi)容：主要內(nèi)容：糾錯編碼的原理糾錯編碼的原理線性分組碼線性分組碼循環(huán)碼循環(huán)碼卷積碼卷積碼（數(shù)字通信特有）（數(shù)字通信特有）29.1 9.1 引引 言言 信號在信道中受到干擾信號在信道中受到干擾干擾種類：乘性干擾種類：乘性碼間干擾；克服方法：均衡器碼間干擾；克服方法：均衡器 加性干擾的類型：加性干擾的類型：突發(fā)突發(fā)型型錯碼錯碼：錯碼成串集中出現(xiàn)；：錯碼成串集中出現(xiàn)； 原因：脈沖干擾，衰落原因：脈沖干擾，衰落混合型錯碼混合型錯碼：加性加性錯碼；克服方法：差錯控制編碼錯碼；克服方法：差錯控制編碼隨機(jī)型錯碼隨機(jī)型錯碼：錯碼是隨機(jī)出現(xiàn)的，相互間統(tǒng)計獨立：錯碼是隨

2、機(jī)出現(xiàn)的，相互間統(tǒng)計獨立 原因：白噪聲。原因：白噪聲。提高信號抗加性干擾的能力提高信號抗加性干擾的能力3速率速率( b/s )線路類別線路類別誤碼率標(biāo)準(zhǔn)誤碼率標(biāo)準(zhǔn)300電話交換線電話交換線專用線專用線10- - 45510- - 5600電話交換線電話交換線專用線專用線10- - 35510- - 51200電話交換線電話交換線專用線專用線10- - 55510- - 52400專用線專用線10- - 5CCITT 建議的誤碼率標(biāo)準(zhǔn)建議的誤碼率標(biāo)準(zhǔn)檢錯重發(fā)、檢錯重發(fā)、前向糾錯、反饋校驗、檢錯刪除前向糾錯、反饋校驗、檢錯刪除 差錯控制的方法差錯控制的方法4檢錯重發(fā)：如接收端檢測出錯碼，通知發(fā)端重

3、發(fā)，直到檢錯重發(fā)：如接收端檢測出錯碼，通知發(fā)端重發(fā)，直到 (ARQ) 接收正確為止。此方法只能判斷是否有錯碼，接收正確為止。此方法只能判斷是否有錯碼， 不能判斷具體的錯碼位置。所以，只能檢錯不不能判斷具體的錯碼位置。所以，只能檢錯不 能糾錯，且需要能糾錯，且需要雙向雙向通道。通道。前向糾錯：前向糾錯：收端能檢測出錯碼，并可以確定錯碼的位收端能檢測出錯碼，并可以確定錯碼的位 (FEC) 置，并予糾正。此方法只需要置，并予糾正。此方法只需要單向單向通道。實通道。實 時性好，但設(shè)備復(fù)雜。時性好，但設(shè)備復(fù)雜。反饋校驗：接反饋校驗：接收端將收到的信號原封不動的發(fā)回發(fā)端，收端將收到的信號原封不動的發(fā)回發(fā)端

4、，由發(fā)端將其與原發(fā)信號相比較，如果有錯則重由發(fā)端將其與原發(fā)信號相比較，如果有錯則重發(fā)。這種方法需發(fā)。這種方法需雙向雙向通道，效率低，設(shè)備簡單通道，效率低，設(shè)備簡單檢錯刪除：如：重復(fù)發(fā)送的的遙測信號。檢錯刪除：如：重復(fù)發(fā)送的的遙測信號。5自動請求重發(fā)系統(tǒng)自動請求重發(fā)系統(tǒng)（ARQ） 工作過程：工作過程：2 2）重發(fā)控制器收到重發(fā)命令時，控制輸入緩沖儲存器重發(fā)控制器收到重發(fā)命令時，控制輸入緩沖儲存器重發(fā)一次當(dāng)前碼組，否則發(fā)送后一碼組。重發(fā)一次當(dāng)前碼組，否則發(fā)送后一碼組。1 1）收端解碼器檢測出錯碼時由指令發(fā)生器產(chǎn)生重發(fā)收端解碼器檢測出錯碼時由指令發(fā)生器產(chǎn)生重發(fā)命令傳給發(fā)端，同時發(fā)出刪除命令，刪除輸出

5、緩沖命令傳給發(fā)端，同時發(fā)出刪除命令，刪除輸出緩沖器內(nèi)容。器內(nèi)容。重發(fā)控制重發(fā)控制信信源源雙雙向向通通道道指令發(fā)生器指令發(fā)生器解碼器解碼器輸出緩存器輸出緩存器收收信信者者錯誤時刪除錯誤時刪除編碼編碼輸入緩存器輸入緩存器6優(yōu)點：優(yōu)點：1 1）監(jiān)督碼少）監(jiān)督碼少; ; 2 2）對各種信道有一定的適應(yīng)能力；）對各種信道有一定的適應(yīng)能力； 3 3）成本及復(fù)雜性低。）成本及復(fù)雜性低。缺點：缺點：1 1）需要雙向通道；）需要雙向通道； 2 2）干擾大時系統(tǒng)可能處于重發(fā)循）干擾大時系統(tǒng)可能處于重發(fā)循環(huán)中，效率降低；環(huán)中，效率降低； 3 3）實時性差。）實時性差。7在信息碼序列中加在信息碼序列中加監(jiān)督碼元監(jiān)督碼

6、元，監(jiān)督碼和信息碼之監(jiān)督碼和信息碼之間存在一種邏輯關(guān)系。因此，收端可以利用這種邏輯間存在一種邏輯關(guān)系。因此，收端可以利用這種邏輯關(guān)系發(fā)現(xiàn)或糾正存在的錯碼。關(guān)系發(fā)現(xiàn)或糾正存在的錯碼。一般來說，一般來說，監(jiān)督碼元越多監(jiān)督碼元越多，檢、糾錯檢、糾錯能力越強(qiáng)能力越強(qiáng)。用降低傳輸速率換取傳輸可靠性的提高。用降低傳輸速率換取傳輸可靠性的提高。不同的編碼方法，有不同的檢錯或糾錯能力。不同的編碼方法，有不同的檢錯或糾錯能力。目標(biāo)：監(jiān)督碼元要少，目標(biāo)：監(jiān)督碼元要少，檢、糾錯能力要強(qiáng)。檢、糾錯能力要強(qiáng)。9.2 9.2 糾錯編碼的基本原理糾錯編碼的基本原理8例：例：表示天氣表示天氣信源信源發(fā)送信息碼發(fā)送信息碼晴晴0

7、 0云云0 1陰陰1 0雨雨1 1接收信息碼接收信息碼 判別判別(錯誤錯誤)0 1云云11 雨雨0 0晴晴1 0陰陰結(jié)論：結(jié)論：雖然接收碼組有錯，但接收端無法識別。雖然接收碼組有錯，但接收端無法識別。錯錯 1 位位9信源信源發(fā)送信息碼發(fā)送信息碼監(jiān)督碼監(jiān)督碼晴晴0 00云云0 11陰陰1 01雨雨1 10接收碼組接收碼組判別判別001、010、100 010、001、111 100、111、001 111、100、010 增加一位監(jiān)督碼增加一位監(jiān)督碼錯錯 1 位位接收碼組接收碼組判別判別(錯誤錯誤)011、110、101 云、雨、陰云、雨、陰000、101、110 晴、陰、雨晴、陰、雨110、0

8、00、011 雨、晴、云雨、晴、云101、000、011 陰、晴、云陰、晴、云錯錯 2 位位結(jié)論：可以檢測出結(jié)論：可以檢測出 1 位錯碼，但不能糾錯。位錯碼，但不能糾錯。禁用碼組：非禁用碼組：非信息信息碼組碼組許用碼組：有效許用碼組：有效信息信息碼組碼組碼距碼距10結(jié)論：結(jié)論：能糾正能糾正 1 位錯碼位錯碼，或，或檢測出檢測出 2 位錯碼位錯碼。信源信源 發(fā)送信息碼發(fā)送信息碼 監(jiān)督碼監(jiān)督碼晴晴0 0000云云0 1011陰陰1 0101雨雨1 1110接收碼組接收碼組判別判別00001,00010,00100,01000,10000晴晴01010,01001,01111,00011,11011

9、云云10100,10111,10001,11101,00101陰陰11111,11100,11010,10110,01110雨雨錯錯 1 位位接收碼組接收碼組判別判別11000,10100,10010,10001,01100,01010,01001,00110,00101,0001110011,11111,11001,11010,00111,00001,00010,01101,01110,0101001101,00001,00111,00110,11001,11110,11101,10011,10000,1010000110,01010,01100,01111,10010,10100,1011

10、1,11000,11011,11111錯錯 2 位位增加三位監(jiān)督碼增加三位監(jiān)督碼碼距關(guān)系碼距關(guān)系11特征：特征：分組碼中的監(jiān)督碼元僅監(jiān)督本碼組分組碼中的監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。中的信息碼元。分組碼分組碼定義：定義：將信息碼分組，為每組信息碼將信息碼分組，為每組信息碼后附加若干監(jiān)督碼元形成的碼集合。后附加若干監(jiān)督碼元形成的碼集合。 分組碼分組碼 k ： 碼組中碼組中信息碼元信息碼元的數(shù)目。的數(shù)目。 n ： 碼組的總位數(shù)，又稱為碼組的總位數(shù)，又稱為碼組長度碼組長度。 r = n - - k ：碼組中：碼組中監(jiān)督碼元監(jiān)督碼元的數(shù)目。的數(shù)目。編碼效率：編碼效率：k/n；冗余度：；冗余度：(n

11、-k)/k符號：符號：( n , k )12結(jié)構(gòu)結(jié)構(gòu) 碼長碼長 n = k + r k 個信息位個信息位 r 個監(jiān)督位個監(jiān)督位碼組重量碼組重量：碼組中：碼組中 “1 ” 的數(shù)目。的數(shù)目。an-1an-2arar-1a0碼距碼距 d ：兩個碼組對應(yīng)位上不同的碼元個數(shù)，：兩個碼組對應(yīng)位上不同的碼元個數(shù)，稱為稱為漢明距離漢明距離。最小碼距最小碼距 d0 ：碼集合中任意兩兩碼組間距離：碼集合中任意兩兩碼組間距離的最小值。的最小值。天氣編碼舉例天氣編碼舉例13 檢測檢測 e 個錯碼，要求最小碼距個錯碼，要求最小碼距1ed0 糾正糾正 t 個錯碼，要求最小碼距個錯碼，要求最小碼距1t2d0 糾正糾正 t

12、個錯碼、同時檢測個錯碼、同時檢測 e 個錯碼，要求最小碼距個錯碼，要求最小碼距1ted0 )te( 碼距與碼集合檢、糾錯能力的關(guān)系碼距與碼集合檢、糾錯能力的關(guān)系A(chǔ)B例：例： A = ( 00000 ) 、B = ( 11111 )， d0 = 5 結(jié)論：結(jié)論：e = 4 或或 t = 2 或或 t = 1 、 e = 3d = 1d = 2d = 3天氣編碼舉例天氣編碼舉例14 奇數(shù)監(jiān)督碼奇數(shù)監(jiān)督碼: :使碼組中使碼組中“1” 的個數(shù)為奇數(shù)的個數(shù)為奇數(shù) 偶數(shù)監(jiān)督碼偶數(shù)監(jiān)督碼: :使碼組中使碼組中“1” 的個數(shù)為偶數(shù)的個數(shù)為偶數(shù)碼距為碼距為2 2，能檢，能檢測奇數(shù)個錯碼測奇數(shù)個錯碼二維奇偶監(jiān)督碼

13、（矩陣碼）二維奇偶監(jiān)督碼（矩陣碼）生成規(guī)則：生成規(guī)則： 許用碼組寫成一行（包括信息碼和許用碼組寫成一行（包括信息碼和1 位監(jiān)位監(jiān)督碼），設(shè)共有督碼），設(shè)共有m 行。第行。第 m+1 行為按列增加的行為按列增加的監(jiān)督碼。（構(gòu)成監(jiān)督碼行）監(jiān)督碼。（構(gòu)成監(jiān)督碼行） 1 1、奇偶監(jiān)督碼奇偶監(jiān)督碼一維奇偶監(jiān)督碼：一維奇偶監(jiān)督碼： 1 位監(jiān)督碼；位監(jiān)督碼；9.3 9.3 常用的簡單編碼常用的簡單編碼常用常用an-1 an-2 a0=1an-1 an-2 a0=015消息消息發(fā)送信息碼發(fā)送信息碼a2 a1 監(jiān)督碼監(jiān)督碼a0晴晴0 00云云0 11陰陰1 01雨雨1 10例例 :一維偶數(shù)監(jiān)督碼一維偶數(shù)監(jiān)督碼接

14、收碼組接收碼組判別判別001、010、100010、001、111100、111、001111、100、010錯錯 1 位位滿足：滿足：0aaa012 檢驗檢驗:0aaa012 只能檢錯，不能糾錯只能檢錯，不能糾錯返回返回161）設(shè)）設(shè) 和和 發(fā)生錯碼，按行無法檢測出有錯，而發(fā)生錯碼，按行無法檢測出有錯，而按列可檢測。按列可檢測。11na 10aa2 a1 a00 0 00 1 11 0 11 1 00 0 0例例 二維偶數(shù)監(jiān)督碼二維偶數(shù)監(jiān)督碼通式通式突發(fā)性錯碼突發(fā)性錯碼111n1n20222n1n20mmmn1n20n1n20aaaaaaaaaccc 2 2）能檢測突發(fā)性錯碼；適用于突發(fā)信道

15、。）能檢測突發(fā)性錯碼；適用于突發(fā)信道。173）若僅一行有奇數(shù)個錯碼時，可通過列確定錯碼位置若僅一行有奇數(shù)個錯碼時，可通過列確定錯碼位置并糾正。并糾正。4）當(dāng)當(dāng) 同時出錯，則按行按列均不能檢測同時出錯，則按行按列均不能檢測 出有錯。出有錯。5）方陣碼除了在行列上的錯碼都為偶數(shù)時，無法檢測）方陣碼除了在行列上的錯碼都為偶數(shù)時，無法檢測外，其余均能檢測。外，其余均能檢測。上頁上頁m0m1n1011naaaa 182 2恒比碼恒比碼在恒比碼中，每個碼組均含有在恒比碼中，每個碼組均含有相同數(shù)目相同數(shù)目的的“1 1”( (和和“0 0”) )。這種碼在檢測時，只要判斷接收碼組中。這種碼在檢測時，只要判斷接

16、收碼組中“1 1”的的數(shù)目是否正確，就能判斷有無錯誤。數(shù)目是否正確，就能判斷有無錯誤。P286P286表表9-29-2中的保護(hù)電碼，每個碼組的長度為中的保護(hù)電碼，每個碼組的長度為5 5，其，其中恒有中恒有3 3個個“1 1”，稱為，稱為5/35/3恒比碼恒比碼。用于我國的漢字電傳。用于我國的漢字電傳編碼。編碼。從從5 5中取中取3 3的組合數(shù)的組合數(shù)C C3 35 5=5!/(3! 2!)=10=5!/(3! 2!)=10。這。這1010種許用種許用碼組恰好可用來表示碼組恰好可用來表示1010個阿拉伯?dāng)?shù)字。用個阿拉伯?dāng)?shù)字。用4 4位阿拉伯?dāng)?shù)位阿拉伯?dāng)?shù)字表示一個漢字。字表示一個漢字。在無線電報通

17、信中，廣泛采用的是在無線電報通信中，廣泛采用的是 7/37/3恒比碼恒比碼，這，這種碼組中總是有種碼組中總是有3 3個個“1 1”。共有。共有7!/(37!/(3！4!)=354!)=35種許用碼種許用碼組，它們可用來代表組，它們可用來代表2626個英文字母及其他控制符號個英文字母及其他控制符號。 19特征：特征：具有糾正具有糾正 1 位錯碼、檢測位錯碼、檢測 2 位和大部分位和大部分 2 位以上錯碼位以上錯碼的能力的能力定義：定義：信息碼位數(shù)與監(jiān)督碼位數(shù)信息碼位數(shù)與監(jiān)督碼位數(shù)相同相同 編碼編碼規(guī)則：規(guī)則： 1）當(dāng)信息位中有）當(dāng)信息位中有奇奇數(shù)個數(shù)個“1”時，監(jiān)督位是信息位的重復(fù)時，監(jiān)督位是信

18、息位的重復(fù)2）當(dāng)信息位中有）當(dāng)信息位中有偶偶數(shù)個數(shù)個“1”時，監(jiān)督位是信息位的反碼時，監(jiān)督位是信息位的反碼1 0 0 0 1 例：例：若信息碼為若信息碼為 1 1 0 0 1 3 3、 正反碼正反碼 則正反碼為則正反碼為 1 1 0 0 1 1 1 0 0 11 0 0 0 1 0 1 1 1 01）將接收碼組中信息碼和監(jiān)督碼對應(yīng)按位模將接收碼組中信息碼和監(jiān)督碼對應(yīng)按位模2 加，得加，得合成碼組合成碼組2）根據(jù)接收碼組中信息碼含）根據(jù)接收碼組中信息碼含 “1” 的奇偶情況，的奇偶情況，由合成碼組生成由合成碼組生成校驗碼組校驗碼組 3）根據(jù)校驗碼組的組成，依表判斷錯碼情況，并予檢錯與糾錯）根據(jù)校

19、驗碼組的組成，依表判斷錯碼情況，并予檢錯與糾錯譯碼譯碼規(guī)則：規(guī)則：“1”為奇為奇 校驗校驗 = 合成合成“1”為偶為偶 校驗校驗 =合合成成20例：發(fā)例：發(fā) 1 1 0 0 1 1 1 0 0 1 1）收無錯）收無錯 信息碼中含奇數(shù)個信息碼中含奇數(shù)個“1”2）收有錯、為）收有錯、為 1 0 0 0 1 1 1 0 0 1合成碼組合成碼組= 1 1 0 0 1 1 1 0 0 10 0 0 0 0譯碼判決：譯碼判決：校驗碼組校驗碼組錯碼情況錯碼情況 1全全 “0” 無錯碼無錯碼 24 個個“1”1 個個“0” 信息碼中有一位錯碼，信息碼中有一位錯碼，對應(yīng)校驗碼組中的對應(yīng)校驗碼組中的“0” 的位置

20、的位置 34 個個“0”1 個個“1” 監(jiān)督碼中有一位錯碼，監(jiān)督碼中有一位錯碼，對應(yīng)校驗碼組中的對應(yīng)校驗碼組中的“1” 的位置的位置 4 其他組成其他組成 錯碼多于錯碼多于 1 個個 校驗碼組校驗碼組 = 合成碼組合成碼組 = 00000判斷接收無錯碼判斷接收無錯碼合成碼組合成碼組= 1 0 0 0 1 1 1 0 0 10 1 0 0 0 信息碼中含偶數(shù)個信息碼中含偶數(shù)個“1”查表知信息碼第二位錯查表知信息碼第二位錯10111 合合成成碼碼組組校校驗驗碼碼組組特征：特征：編碼效率低編碼效率低219.4 9.4 線性分組碼線性分組碼漢明碼的編碼原理漢明碼的編碼原理一般線性分組碼的編碼原理一般線

21、性分組碼的編碼原理（可以糾錯）（可以糾錯）線性碼：監(jiān)督碼和信息碼之間的關(guān)系是線性關(guān)系線性碼：監(jiān)督碼和信息碼之間的關(guān)系是線性關(guān)系22分析偶數(shù)監(jiān)督碼，尋找邏輯組合分析偶數(shù)監(jiān)督碼，尋找邏輯組合 監(jiān)督方程監(jiān)督方程 所以解碼就是要計算所以解碼就是要計算0 無錯無錯1 有錯有錯s =只能表示出錯只能表示出錯不能描述錯碼位置不能描述錯碼位置一位監(jiān)督碼對一位監(jiān)督碼對應(yīng)一個監(jiān)督方應(yīng)一個監(jiān)督方程程，即，即對應(yīng)一對應(yīng)一個校正子個校正子結(jié)論：若增加監(jiān)督碼元，建立多個監(jiān)督方程，多個結(jié)論：若增加監(jiān)督碼元，建立多個監(jiān)督方程，多個校正子就能形成邏輯組合描述錯碼位置。校正子就能形成邏輯組合描述錯碼位置。r位監(jiān)督碼對應(yīng)位監(jiān)督碼對

22、應(yīng)r個校正子，就有個校正子，就有2r 種組合，用其中種組合，用其中一種組合表示無錯，其余一種組合表示無錯，其余2r-1種組合表示錯碼的位置。種組合表示錯碼的位置。9.4.1 9.4.1 漢明碼漢明碼s=an-1 an-2 a0an-1 an-2 a0=0校正子校正子 23確定監(jiān)督關(guān)系表確定監(jiān)督關(guān)系表建立監(jiān)督方程建立監(jiān)督方程建立編碼方程建立編碼方程如果只錯一位，分組碼如果只錯一位，分組碼(n,k)中的錯碼有中的錯碼有n個可能的位個可能的位置置 ，要用要用r 位監(jiān)督碼表示這位監(jiān)督碼表示這n 個錯碼的位置，個錯碼的位置， 為提高編碼效率，為提高編碼效率， r 取最小值取最小值n12r 例：例：已知已

23、知( 7 , 4 )碼，碼，r = 3 共有共有3個監(jiān)督方程，個監(jiān)督方程， 構(gòu)成構(gòu)成 3個校正子個校正子 S1 S2 S3S1 S2 S30 0 0無錯無錯0 0 1a0 錯錯0 1 0a1 錯錯1 0 0a2 錯錯1 1 0a3 錯錯0 1 1a4 錯錯1 1 1a5 錯錯1 0 1a6 錯錯0aaaa2356456034513562aaaaaaaaaaaa 0aaaa04560aaaa1345只糾正一位錯碼只糾正一位錯碼n7123 監(jiān)督碼出錯只與監(jiān)督碼出錯只與一個校正子有關(guān)一個校正子有關(guān)24求碼組集合求碼組集合 k = 4，信息碼組有信息碼組有 16 個個a6 a5 a4 a3a2 a1

24、a00 0 0 00 0 00 0 0 11 1 00 0 1 00 1 10 0 1 11 0 1.1 1 0 00 1 01 1 0 11 0 01 1 1 00 0 11 1 1 11 1 1能糾正一位錯碼，且能糾正一位錯碼，且2r-1=n的的線性分組碼，稱為線性分組碼，稱為漢明碼漢明碼。其編碼效率為其編碼效率為k/n=(2r-1-r)/(2r-1)=1-r/(2r-1)=1-r/n當(dāng)當(dāng)n很大時，則編碼效率接近很大時，則編碼效率接近1?？梢姡瑵h明碼是。可見，漢明碼是一種高效碼。一種高效碼。25 漢明碼的監(jiān)督方程為漢明碼的監(jiān)督方程為用用矩陣表示矩陣表示6543210110110000111

25、01001110 0010aaaaaaa 9.4.2 9.4.2 一般線性分組碼的編碼原理一般線性分組碼的編碼原理0aaaa0aaaa0aaaa045613452356 記為：記為：0AHT 監(jiān)督矩陣監(jiān)督矩陣碼組向量碼組向量111000101110101101100H0123456aaaaaaaA 當(dāng)當(dāng) 稱稱 H 為典型監(jiān)督矩陣為典型監(jiān)督矩陣（含單位陣）（含單位陣）rIPH階階為為krP階階為為rrIr錯誤圖樣錯誤圖樣26QIGk根據(jù)監(jiān)督方程確定了根據(jù)監(jiān)督方程確定了編碼方程編碼方程34563456012aaaaPaaaa111001111101aaa456034513562aaaaaaaaaa

26、aa 兩邊同取轉(zhuǎn)置兩邊同取轉(zhuǎn)置QaaaaPaaaaaaa3456T3456012階階其其中中rkPQT構(gòu)造構(gòu)造生成矩陣生成矩陣GaaaaaaaaaaaA34560123456G 為典型生成矩陣為典型生成矩陣 編碼矩陣方程編碼矩陣方程特點：信息位不變，監(jiān)督位附加于其后。特點：信息位不變，監(jiān)督位附加于其后。由典型生成矩陣得出的碼組由典型生成矩陣得出的碼組 A是是系統(tǒng)碼系統(tǒng)碼27QIGk生成矩陣生成矩陣0111000110010011100101010001G 中中每行均為一個碼組，且線性無關(guān)每行均為一個碼組，且線性無關(guān)若能找到若能找到k個線性無關(guān)的已知碼組，就能構(gòu)成矩陣個線性無關(guān)的已知碼組，就能構(gòu)

27、成矩陣G。 nk TkPI循環(huán)碼生成矩陣循環(huán)碼生成矩陣28譯碼運算，當(dāng)譯碼運算，當(dāng)TTH)EA(HBTTTHESSHEHAS 為校正子。說明為校正子。說明 S 與與E 有確定的線性關(guān)系有確定的線性關(guān)系若若 E 的數(shù)目有限的數(shù)目有限，能與能與 S 一一對應(yīng)，一一對應(yīng)，則則 說明說明 S 能描述錯碼的位置，具有糾錯能力。能描述錯碼的位置，具有糾錯能力。令令 發(fā)碼組為發(fā)碼組為 A、收碼組為、收碼組為 B 錯碼圖樣錯碼圖樣 E = B- - A錯誤圖樣錯誤圖樣收發(fā)碼組的關(guān)系收發(fā)碼組的關(guān)系THB0 無錯無錯1 有錯有錯 令令 B =E + + A29發(fā)碼組發(fā)碼組 A = 1 1 0 0 0 1 0收碼組

28、收碼組 B = 1 0 0 0 0 1 0 譯碼運算譯碼運算例：例： ( 7 , 4 )漢明碼漢明碼, 111000101110101101100H001010100110011111101)1000010(HBT)111(S1 S2 S30 0 0無錯無錯0 0 1a0 錯錯0 1 0a1 錯錯1 0 0a2 錯錯1 1 0a3 錯錯0 1 1a4 錯錯1 1 1a5 錯錯1 0 1a6 錯錯 a5 錯錯含義：含義：錯碼圖樣錯碼圖樣 E =（0 1 0 0 0 0 0） 只有一位錯碼只有一位錯碼)111(HET30線性碼中任意線性碼中任意兩個碼組之和兩個碼組之和仍為這種碼中的一個碼組仍為這種

29、碼中的一個碼組證：證： 設(shè)設(shè) A1 、 A2 為線性碼中兩個許用碼組為線性碼中兩個許用碼組0HAT10HAT2兩式相加兩式相加0H)AA(HAHAT21T2T121AA 是許用碼組是許用碼組推廣：推廣： 1）兩個碼組間的）兩個碼組間的距離距離必是另一碼組的必是另一碼組的重量重量2）除）除 全全0 碼組之外，編碼的碼組之外，編碼的最小碼重最小碼重是碼集是碼集合的合的最小碼距最小碼距。線性分組碼的性質(zhì)：線性分組碼的性質(zhì)：封閉性封閉性3)線性分組碼中必有全線性分組碼中必有全0碼；碼；（信息碼全（信息碼全0，監(jiān)督碼全，監(jiān)督碼全0）319.5 9.5 循環(huán)碼循環(huán)碼 9.5.1 9.5.1 碼多項式碼多項

30、式9.5.2 9.5.2 循環(huán)碼的特性循環(huán)碼的特性9.5.3 9.5.3 循環(huán)碼的編碼方法循環(huán)碼的編碼方法 循環(huán)碼是線性分組碼中一種重要的編碼。它是在嚴(yán)循環(huán)碼是線性分組碼中一種重要的編碼。它是在嚴(yán)密的代數(shù)理論基礎(chǔ)上建立起來的。其編碼和解碼不密的代數(shù)理論基礎(chǔ)上建立起來的。其編碼和解碼不太復(fù)雜，但檢太復(fù)雜，但檢(糾糾)錯的能力較強(qiáng)。循環(huán)碼除了具有線錯的能力較強(qiáng)。循環(huán)碼除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，見表性碼的一般性質(zhì)外，還具有循環(huán)性，見表11-5。32碼多項式的模運算：碼多項式的模運算：9.5.1 9.5.1 碼多項式碼多項式碼多項式碼多項式以碼組中各碼元為系數(shù)的多項式以碼組中各碼元為系

31、數(shù)的多項式T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0設(shè)設(shè) 多項式多項式 F(x)、除式為、除式為 N(x)x(N)x(R)x(Q)x(N)x(F)()(xRxF注：注：多項式按模多項式按模 N(x) 運算過程中，其系數(shù)均為運算過程中，其系數(shù)均為模模2 運算。運算。x 僅為碼元位置的標(biāo)記僅為碼元位置的標(biāo)記模模 N( x )； R( x )：余式：余式例：例：( 110 0101 ) T( x ) = x 6 + x 5 + x 2 + 133例：例：1x1xx324xxx1xx1x42431xx21xx1xx224解：解：記為：記為：余式余式

32、系數(shù)為二進(jìn)制，只能取系數(shù)為二進(jìn)制，只能取0或或1，二進(jìn)制的加減都是一樣的，二進(jìn)制的加減都是一樣的34 用碼多項式的運算來表示：若用碼多項式的運算來表示：若T(x)對應(yīng)一個碼長為對應(yīng)一個碼長為 n 的許用碼組，則的許用碼組，則x i T(x)按模按模x n+1運算后余式運算后余式T (x)仍為仍為許用碼組許用碼組。證：證： 令令( )( )ixT xTx 1xn模模 T (x)的系數(shù)是的系數(shù)是T(x)中系數(shù)向左循環(huán)移位中系數(shù)向左循環(huán)移位 i 次的結(jié)果次的結(jié)果9.5.2 9.5.2 循環(huán)碼的特性循環(huán)碼的特性 編碼中任意一個碼組，左移或右移一位得到的新碼編碼中任意一個碼組，左移或右移一位得到的新碼組

33、必是該碼集合中另一碼組。組必是該碼集合中另一碼組。生成多項式生成多項式 T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0 x iT( x ) = an-1 x n-1+i + . + an-1-i x n-1+ . + a0 xix iT(x) an-1-i x n-1 +. + a0 x i + an-1 x i-1 + . +an-i1xn模模35例：例： ( 7 , 3 )循環(huán)碼循環(huán)碼, 碼組為碼組為( 110 0101 )，驗證驗證 x 3 T( x ) 按模按模 x 7 +1 運算后余式仍是一個許用碼組運算后余式仍是一個許用碼組 。 解

34、：解： T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0 T( x ) = x 6 + x 5 + x 2 + 1 x 3 T( x ) = x 9 + x 8 + x 5 + x 3xxxxxxxxxxxxxxxxxx1x2235823582935897xxxxxTx2353)( 余式余式T (x) 對應(yīng)碼組為對應(yīng)碼組為(0101110) 是是T(x)碼組循環(huán)左移三位的結(jié)果碼組循環(huán)左移三位的結(jié)果369.5.3 9.5.3 循環(huán)碼的編碼方法循環(huán)碼的編碼方法思路：思路：由碼的循環(huán)性，由碼的循環(huán)性，可知找到一個碼多項式，可知找到一個碼多項式，就能就能

35、得到其他的碼多項式得到其他的碼多項式一個一個(n,k)碼有碼有2k個不同碼組。用個不同碼組。用g(x)表示其中表示其中前前(k-1)位皆為位皆為“0”的碼組。則的碼組。則g(x)，xg(x)，x2g(x)，xk-1g(x)都是該循環(huán)碼的碼組，而且這都是該循環(huán)碼的碼組，而且這k個碼組個碼組是線性無關(guān)的，是線性無關(guān)的，用它們可以構(gòu)成此循環(huán)碼的用它們可以構(gòu)成此循環(huán)碼的生成矩陣生成矩陣G。循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣 G)()()()()(xgxgxxgxxgxxG2k1kk是一個碼是一個碼組中信息組中信息碼的長度碼的長度37對對g(x)的說明：的說明： 是該循環(huán)碼中是該循環(huán)碼中階數(shù)最低階數(shù)最低的

36、碼多項式。的碼多項式。 在循環(huán)碼中除全在循環(huán)碼中除全“0”碼組外，即碼組外，即連連“0”的長度的長度最多最多只能有只能有(k-1)位位。否則在經(jīng)過若干次循環(huán)移位后將得到。否則在經(jīng)過若干次循環(huán)移位后將得到一個一個k個信息位全為個信息位全為“0”，但監(jiān)督位不全為，但監(jiān)督位不全為“0”的碼組。的碼組。這顯然是不可能的。這顯然是不可能的。 g(x)必須是必須是一個常數(shù)項不為一個常數(shù)項不為“0”的的(n-k)次多項式次多項式。 而且還是而且還是唯一唯一的。因為如果有兩個，則由碼的封閉的。因為如果有兩個，則由碼的封閉性，把這兩個相加也應(yīng)該是一個碼組，且此碼組多項性，把這兩個相加也應(yīng)該是一個碼組，且此碼組多

37、項式的次數(shù)將小于式的次數(shù)將小于(n-k)，即連續(xù)，即連續(xù)“0”的個數(shù)多于的個數(shù)多于(n-k)，這是不可能的。這是不可能的。 我們稱這唯一的我們稱這唯一的(n-k)次多項式次多項式g(x)為碼的為碼的生成多項生成多項式式。一旦確定一旦確定g(x)，則整個，則整個(n-k)循環(huán)碼就被確定了。循環(huán)碼就被確定了。38(7,3)循環(huán)碼的碼組循環(huán)碼的碼組:T(x)=a6a5a4G(x) =a6a5a4 =(a6 x2+a5 x+a4)g(x) 這表明，所有碼多項式這表明，所有碼多項式T(x)都是都是g(x)倍式倍式，而且任一，而且任一次數(shù)不大于次數(shù)不大于(k-1)的多項式乘的多項式乘g(x)都是碼多項式。

38、都是碼多項式。在表在表11-5中找出生成多項式中找出生成多項式)()()(xgxxgxgx2所有的信息碼組合所有的信息碼組合39碼生成多項式碼生成多項式 g( x ) 的求解的求解定理：定理：循環(huán)碼循環(huán)碼( n , k ) 的的 g( x ) 是是 xn +1 的一個的一個( n- - k ) 次次 因子。因子。證：證： 任意一個碼多項式任意一個碼多項式 T( x ) 都是都是 g( x ) 倍式倍式令令 T( x ) = h( x ) g( x ) ( )( )( )knnx g xT xQ xx1x1 1x)x(T1n而而 x k g( x ) = x n + 1 + T( x ) x n

39、 +1 = x k g( x ) + T( x ) = x k g( x ) + h( x ) g( x ) = x k + h( x ) g( x ) g(x)為一為一(n-k)次多項式，次多項式，故故xkg(x)為一為一n次多項式。次多項式。余式余式T(x) 也是一個許用也是一個許用碼組。碼組。按模運算按模運算40例：已知例：已知 (7,3) 循環(huán)碼，求碼組集合循環(huán)碼，求碼組集合 、監(jiān)督矩陣、監(jiān)督矩陣 H 。解：解： n = 7 x7 + 1 = ( x +1 )( x 6 + x 5+ x 4 + x 3 + x 2+ x + 1 ) = ( x +1 )( x 3 + x 2+ 1 )

40、( x 3 + x + 1 ) g1( x ) = ( x +1 )( x 3 + x 2+ 1 ) = x 4 + x 2+ x + 1 g2( x ) = ( x +1 )( x 3 + x + 1 ) = x 4 + x 3+ x 2 + 1 取取 g( x ) = g1( x ) = x 4 + x 2+ x + 1 )x( g)x( gx)x( gx)x( gx)x(G2k1k1xxxxxxxxxxx242352346 111010001110100011101G互逆互逆(生成多項式的逆多項式也是生成多項式生成多項式的逆多項式也是生成多項式)表表11-5（2）41 A = ( a6

41、a5 a4 a3 a2 a1 a0 ) G)aaa(456 a6 a5 a4 a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 0 0 00 0 1 1） 0 0 1 0 1 1 10 1 0 2） 0 1 0 1 1 1 00 1 1 3） 0 1 1 1 0 0 11 0 0 5） 1 0 1 1 1 0 01 0 1 4） 1 0 0 1 0 1 11 1 0 7） 1 1 1 0 0 1 01 1 1 6） 1 1 0 0 1 0 1111010001110100011101G111010001110101101001 00011010010111010001110

42、00110H 111010001110100011101)aaa(456監(jiān)督方程：監(jiān)督方程：0aaa356 0aaa245 0aaaa1456 0aaa046 d0 = 3 , t = 1 非典型非典型非系統(tǒng)非系統(tǒng)429.5.4 循環(huán)碼的編、解電路循環(huán)碼的編、解電路1、循環(huán)碼的編碼電路、循環(huán)碼的編碼電路設(shè)設(shè)m(x)為信息碼多項式，其次數(shù)小于為信息碼多項式，其次數(shù)小于k。 (1)用用xn-k乘乘m(x)。得到的得到的xn-km(x)的次數(shù)必小于的次數(shù)必小于n。也。也就是把信息碼后附加上就是把信息碼后附加上(n-k)個個“0”，這是監(jiān)督位的位，這是監(jiān)督位的位置。置。 (2)用用g(x)除除xn-k

43、m(x): xn-km(x)/ /g(x)=Q(x)r(x)得到得到余式余式r(x) 。 (3) T(x)=xn-km(x)+r(x)由于由于xn-km(x)+r(x)=Q(x)g(x)，能被，能被g(x)整除，因此整除，因此T(x)必為一碼多項式必為一碼多項式。 余式余式r(x) 就是就是監(jiān)督碼多項式監(jiān)督碼多項式。43上述三步運算，可由除法電路來實現(xiàn)。上述三步運算，可由除法電路來實現(xiàn)。 ( (移存器的反饋抽頭取決于生成多項式移存器的反饋抽頭取決于生成多項式) ) 44452循環(huán)碼的解碼電路循環(huán)碼的解碼電路 接收端解碼的要求有兩個：檢錯和糾錯。接收端解碼的要求有兩個：檢錯和糾錯。 用于檢錯的解

44、碼電路比較簡單。用于檢錯的解碼電路比較簡單。 把接收碼組把接收碼組R(x)除以除以生成多項式生成多項式g(x)。 當(dāng)傳輸中當(dāng)傳輸中未發(fā)生錯誤未發(fā)生錯誤時，接收碼組與發(fā)送碼組相時，接收碼組與發(fā)送碼組相同，即同，即R(x)=T(x)，故接收碼組，故接收碼組R(x)必定必定能被能被g(x)整除整除 若碼組在傳輸中若碼組在傳輸中發(fā)生錯誤發(fā)生錯誤，則，則R(x)T(x)，R(x)被被g(x)除時可能除時可能除不盡除不盡而有余項，即有而有余項，即有 R(x)/ /g(x)=Q(x)+r(x)/ /g(x) 當(dāng)錯碼數(shù)超過了這種編碼的檢錯能力時，有錯碼當(dāng)錯碼數(shù)超過了這種編碼的檢錯能力時，有錯碼的接收碼組也可能

45、被的接收碼組也可能被g(x)整除，這時的錯碼就不能檢整除，這時的錯碼就不能檢出了。這種錯誤稱為出了。這種錯誤稱為不可檢錯誤不可檢錯誤。4647 用于糾錯的解碼方法比較復(fù)雜。要求每個可糾正的用于糾錯的解碼方法比較復(fù)雜。要求每個可糾正的錯誤圖樣錯誤圖樣必須與一個特定必須與一個特定余式余式有有一一對應(yīng)一一對應(yīng)關(guān)系。可按關(guān)系?？砂聪率霾襟E進(jìn)行：下述步驟進(jìn)行： (1)用生成多項式用生成多項式g(x)除接收碼組除接收碼組R(x)=T(x)+E(x)，得，得出出余式余式r(x)； (2)按余式按余式r(x)用用查表查表的方法或通過某種的方法或通過某種運算運算得到得到錯誤錯誤圖樣圖樣E(x)。 (3)從從R(

46、x)中中減去減去E(x)，便得到已糾正錯誤的原發(fā)送碼便得到已糾正錯誤的原發(fā)送碼組組T(x)； 上述運算第上述運算第(2)步較復(fù)雜，并且在計算余式和決定步較復(fù)雜，并且在計算余式和決定E(x)的時候需要把整個接收碼組的時候需要把整個接收碼組R(x)暫時存儲起來。暫時存儲起來。 對于糾正突發(fā)錯誤或單個錯誤的編碼還算簡單，而對于糾正突發(fā)錯誤或單個錯誤的編碼還算簡單，而對于糾正多個隨機(jī)錯誤的編碼卻是十分復(fù)雜的。對于糾正多個隨機(jī)錯誤的編碼卻是十分復(fù)雜的。 48 這種解碼方法稱為這種解碼方法稱為捕錯解碼法捕錯解碼法。一種編碼可以有幾。一種編碼可以有幾種不同的糾錯解碼法。對于循環(huán)碼來說，可用捕錯解碼、種不同的糾錯解碼法。對于循環(huán)碼來說，可用捕錯解碼、大數(shù)邏輯解碼等大數(shù)邏輯解碼等 現(xiàn)在主要用現(xiàn)在主要用軟件軟件來做編解碼來做編解碼499.5.5 縮短循環(huán)碼縮短循環(huán)碼并不是在所有碼長并不是在所有碼長(n,k)碼中，都能找到相應(yīng)的滿足碼中，都能找到相應(yīng)的滿足某糾錯能力的循環(huán)碼。但在系統(tǒng)設(shè)計中，碼長某糾錯能力的循環(huán)碼。但在系統(tǒng)設(shè)計中，碼長n、信、信息位數(shù)息位數(shù)k和和糾錯能力糾錯能力常常是預(yù)先確定的。常常是預(yù)先確定的。這時可采用縮短循環(huán)碼來