《數(shù)字通信原理》第8章 差錯(cuò)控制編碼：基本概念與線性分組碼

1、數(shù)字通信原理(8-1)馮穗力等編著電子工業(yè)出版社2012年8月2010 Copyright 1SCUT DT&P Labs第 8 章 差錯(cuò)控制編碼基本概念與線性分組碼本章第一部份的基本內(nèi)容：差錯(cuò)控制編碼的基本概念；簡單的差錯(cuò)控制方法；信道編碼的基本概念與定理*；線性分組碼的代數(shù)基礎(chǔ)*；線性分組碼的基本性質(zhì)循環(huán)碼。2010 Copyright 2SCUT DT&P Labs8.1 引言 2010 Copyright 3SCUT DT&P Labs 引言 數(shù)據(jù)在物理信道中傳輸時(shí)通常會(huì)因?yàn)樾诺赖姆抢硐胩匦院鸵氲脑肼曉斐蓚鬏數(shù)腻e(cuò)誤。 差錯(cuò)控制編碼的基本概念：通過對(duì)數(shù)據(jù)進(jìn)行某種編碼處理，使得接收端可以

2、判斷接收到的數(shù)據(jù)，是否出現(xiàn)錯(cuò)誤，甚至可以糾正一定范圍內(nèi)錯(cuò)誤。 差錯(cuò)控制編碼是將有誤碼的物理信道改造成無差錯(cuò)的邏輯信道的一種方法。 所謂差錯(cuò)控制編碼，通常是通過代數(shù)的方法，加入與待傳輸?shù)臄?shù)據(jù)有一定關(guān)聯(lián)關(guān)系的監(jiān)督位來實(shí)現(xiàn)的。 在接收端可根據(jù)特定的關(guān)聯(lián)關(guān)系是否受到破環(huán)來判別是否出現(xiàn)錯(cuò)誤，并可在一定程度上根據(jù)出錯(cuò)的情況糾正錯(cuò)誤。 在糾錯(cuò)編碼中加入的監(jiān)督位本身并不攜帶信息，因此有時(shí)也將監(jiān)督位成為冗余位。第8章 差錯(cuò)控制編碼2010 Copyright 4SCUT DT&P Labs 引言 若每一組 位信息位，編碼后生成 位長度的碼字 則定義編碼效率 冗余度第8章 差錯(cuò)控制編碼2010 Copyright

3、 5SCUT DT&P Labs8.2 差錯(cuò)控制編碼的主要類型和方式 2010 Copyright 6SCUT DT&P Labs 差錯(cuò)控制編碼的主要類型和方式 差錯(cuò)控制編碼的主要類型 (1)線性碼與非線性碼 線性碼：監(jiān)督碼元與信息碼元間的關(guān)系是一種線性關(guān)系； 非線性碼：監(jiān)督碼元與信息碼元間的關(guān)系則是一種非線性的關(guān)系。 (2)分組碼與卷積碼 分組碼：監(jiān)督碼元與信息碼元間以碼組為單位建立關(guān)系； 卷積碼：監(jiān)督碼元不僅與本組的信息碼元有關(guān)，還與前面若干個(gè)碼組的信息碼元有關(guān)。 第8章 差錯(cuò)控制編碼2010 Copyright 7SCUT DT&P Labs第8章 差錯(cuò)控制編碼 差錯(cuò)控制編碼的主要類型和

4、方式(續(xù)) 差錯(cuò)控制編碼的主要類型 (3)系統(tǒng)碼與非系統(tǒng)碼 系統(tǒng)碼：編碼后信息碼元部分的排列結(jié)構(gòu)保持不變； 非系統(tǒng)碼，編碼后碼組中信息碼元部分的排列結(jié)構(gòu)發(fā)生了變化，一般不能看出原來信息碼元的圖樣結(jié)構(gòu)。 2010 Copyright 8SCUT DT&P Labs 差錯(cuò)控制編碼的主要類型和方式(續(xù)) 通信系統(tǒng)通常可分為單工、半雙工、和全雙工三種工作方式。 單工：單向、沒有回傳通道的系統(tǒng)稱之； 半雙工：雙向，但發(fā)送和接收必須分時(shí)進(jìn)行的系統(tǒng)稱之； 全雙工：雙向，發(fā)送和接收可同時(shí)進(jìn)行的系統(tǒng)稱之。 不同的差錯(cuò)控制方式，對(duì)系統(tǒng)有不同的要求。 差錯(cuò)控制方式 (1)檢錯(cuò)重發(fā)：通過差錯(cuò)控制編碼，使得接收端具有檢

5、錯(cuò)能力，接收端如果發(fā)現(xiàn)傳輸出錯(cuò)，通過反向信道請(qǐng)求重發(fā)。 檢錯(cuò)重發(fā)方式，要求系統(tǒng)具有反向傳輸通道； 檢錯(cuò)重發(fā)方式通常具有較高的編碼效率。 第8章 差錯(cuò)控制編碼2010 Copyright 9SCUT DT&P Labs 差錯(cuò)控制編碼的主要類型和方式(續(xù)) (2)前向糾錯(cuò)：采用具有檢錯(cuò)和糾錯(cuò)的編碼算法，接收端不僅能夠檢測(cè)出錯(cuò)誤，而且定位出碼字中錯(cuò)誤的位置并加以糾正。 前向糾錯(cuò)的方法適用于包括單工通信系統(tǒng)的應(yīng)用場(chǎng)合。 在一些對(duì)實(shí)時(shí)性要求較高的通信場(chǎng)合，必須采用前向糾錯(cuò)的方法。 前向糾錯(cuò)需要定位錯(cuò)誤的位置和出現(xiàn)何種錯(cuò)誤(對(duì)二進(jìn)制以外的糾錯(cuò)編碼)，通常編譯碼的方法比較復(fù)雜，效率較低、 (3)混合差錯(cuò)控制

6、：結(jié)合檢錯(cuò)重發(fā)和前向糾錯(cuò)方式優(yōu)點(diǎn)的差錯(cuò)控制方法； 對(duì)于出現(xiàn)較少錯(cuò)誤時(shí)，由前向糾錯(cuò)方式加以糾正；當(dāng)經(jīng)糾錯(cuò)后仍有錯(cuò)誤時(shí)，則啟動(dòng)檢錯(cuò)重發(fā)機(jī)制。 混合差錯(cuò)是一種兼顧效率和復(fù)雜性的方法。第8章 差錯(cuò)控制編碼2010 Copyright 10SCUT DT&P Labs8.3 簡單的差錯(cuò)控制方法 2010 Copyright 11SCUT DT&P Labs 簡單的差錯(cuò)控制方法 奇偶校驗(yàn)碼 奇偶校驗(yàn)碼是一種通過增加1位監(jiān)督位，從而使得碼組具有檢測(cè)1位誤碼的差錯(cuò)控制方法。 (1)偶校驗(yàn) 設(shè)待發(fā)送的信息碼組： 加入監(jiān)督位 其中 由此可得監(jiān)督位與信息位的關(guān)聯(lián)關(guān)系 若傳輸過程中出現(xiàn)1位的誤碼，上述關(guān)聯(lián)關(guān)系將被破壞

7、，因此可發(fā)現(xiàn)出現(xiàn)錯(cuò)誤。 因編碼后碼組 中有偶數(shù)個(gè)1，故稱為偶校驗(yàn)。第8章 差錯(cuò)控制編碼2010 Copyright 12SCUT DT&P Labs 簡單的差錯(cuò)控制方法(續(xù)) (2)奇校驗(yàn) 若加入的監(jiān)督位由下式確定 則由此建立的關(guān)聯(lián)關(guān)系為 編碼后產(chǎn)生的碼組 中將有奇數(shù)個(gè)1，故稱奇校驗(yàn)。 同樣，傳輸過程的1位誤碼將破壞上述的關(guān)聯(lián)關(guān)系。 容易驗(yàn)證：當(dāng)出現(xiàn)奇數(shù)位的誤碼時(shí)，關(guān)聯(lián)關(guān)系均被破壞，因此可以發(fā)現(xiàn)錯(cuò)誤。而當(dāng)出現(xiàn)偶數(shù)位的錯(cuò)誤時(shí)，不能發(fā)現(xiàn)錯(cuò)誤。第8章 差錯(cuò)控制編碼2010 Copyright 13SCUT DT&P Labs 簡單的差錯(cuò)控制方法(續(xù)) 所有可能的信息碼組經(jīng)過差錯(cuò)控制編碼后，得到的輸出

8、碼組(也稱為碼字)構(gòu)成了一個(gè)稱為許用碼字的集合：許用碼字集 不在許用碼字集中的碼字稱為禁用碼字。 一般地，如果傳輸出錯(cuò)使得原來的許用碼字變?yōu)榻么a字，則這種錯(cuò)誤可被發(fā)現(xiàn)； 示例：偶校驗(yàn)碼字中所有含偶數(shù)個(gè)“1”的碼字為許用碼字； 所有含奇數(shù)個(gè)“1”的碼字為禁用碼字。 奇校驗(yàn)碼字中所有含奇數(shù)個(gè)“1”的碼字為許用碼字； 所有含偶數(shù)個(gè)“1”的碼字為禁用碼字。 如果傳輸過出錯(cuò)使得原來的許用碼字變?yōu)榱硗庖粋€(gè)許用碼字，則這種錯(cuò)誤不能被發(fā)現(xiàn)。第8章 差錯(cuò)控制編碼2010 Copyright 14SCUT DT&P Labs 簡單的差錯(cuò)控制方法(續(xù)) 示例: 3位二進(jìn)制碼組的所有組合 000，001，010，0

9、11，100，101，110，111 (1)若所有組合均為許用碼字，每個(gè)碼字可攜帶3比特信息； 任一許用碼字出錯(cuò)都變?yōu)榱硪辉S用碼字，無差錯(cuò)控制功能 (2) 若選擇 許用碼字：000，011，101，110 禁用碼字：111，001，010，100 編碼后每個(gè)3位的許用碼字可攜帶2比特信息； 任一許用碼字的1位誤碼都會(huì)變?yōu)榻么a字，因此可發(fā)現(xiàn)任意的1位誤碼；該碼實(shí)際上是一種偶校驗(yàn)碼。 2位的誤碼將變?yōu)榱硪辉S用碼字，錯(cuò)誤不能被發(fā)現(xiàn)。 注意：需要合理地確定許用碼字方可使編碼碼字具有檢錯(cuò)能力。第8章 差錯(cuò)控制編碼2010 Copyright 15SCUT DT&P Labs第8章 差錯(cuò)控制編碼 簡單的

10、差錯(cuò)控制方法(續(xù)) (2) 若選擇 許用碼字：000，111 禁用碼字：001，010，100，011，101，110 編碼后每個(gè)3位的許用碼字可攜帶1比特信息； 任一許用碼字的2位以下的誤碼都會(huì)變?yōu)榻么a字，因此可發(fā)現(xiàn)任意的2位誤碼； 采用擇多邏輯的方法可糾正出現(xiàn)1位誤碼時(shí)的錯(cuò)誤 3位的誤碼將使“000” “111” ，錯(cuò)誤不能被發(fā)現(xiàn)。 本例的啟示： 差錯(cuò)控制能力越強(qiáng)，相應(yīng)的冗余的開銷越大； 任何一種差錯(cuò)控制編碼，其差錯(cuò)控制能力都有一定限制； 需要合理地選擇許用碼字。2010 Copyright 16SCUT DT&P Labs 簡單的差錯(cuò)控制方法(續(xù)) 重復(fù)碼 在上例中可見，“000”和“

11、111”是3位碼元均相同，是一種3位的重復(fù)碼，可發(fā)現(xiàn)任意的2位錯(cuò)誤和糾正1位錯(cuò)誤。 3位的重復(fù)編碼可推廣到一般的情形，若 n 位的重復(fù)碼用于表示1比特信息。如 “0000” 0 ； “1111” 1 則可發(fā)現(xiàn)任意的 位誤碼；采用擇多邏輯進(jìn)行判決，可糾正任意的少于 位的誤碼。 重復(fù)碼編譯碼簡單，但效率較低。第8章 差錯(cuò)控制編碼2010 Copyright 17SCUT DT&P Labs 簡單的差錯(cuò)控制方法(續(xù)) 水平奇偶校驗(yàn)碼 奇偶校驗(yàn)碼簡單且效率高 但只能檢測(cè)出奇數(shù)位的錯(cuò)誤。 水平奇偶校驗(yàn)碼是一種通過組合 個(gè)簡單奇偶校驗(yàn)碼字而構(gòu)建的一種能夠檢測(cè)任意的小于等于 位連續(xù)誤碼的編碼方法。第8章 差

12、錯(cuò)控制編碼2010 Copyright 18SCUT DT&P Labs 簡單的差錯(cuò)控制方法(續(xù)) 編碼： 個(gè)簡單的奇偶校驗(yàn)碼字按照如下的方式排列 信息碼組 監(jiān)督碼元 (*) 傳輸： 按列順序發(fā)送數(shù)據(jù) 譯碼： 接收到數(shù)據(jù)后重新按照(*)排列，當(dāng)連續(xù)誤碼的個(gè)數(shù)小于等于 時(shí)，每一行中只會(huì)1位誤碼，因此可以檢測(cè)出相應(yīng)的誤碼。第8章 差錯(cuò)控制編碼2010 Copyright 19SCUT DT&P Labs8.4 信道編碼的基本概念和定理* 2010 Copyright 20SCUT DT&P Labs 信道編碼的基本概念和定理 編碼信道的基本模型 記 信源符號(hào)集 編碼輸出碼字集 接收碼字集 信道譯碼

13、輸出碼字集 發(fā)送碼字的先驗(yàn)概率 注：在本教材中，只討論離散無記憶信道的情形。第8章 差錯(cuò)控制編碼2010 Copyright 21SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 記接收碼字的統(tǒng)計(jì)特性為 對(duì)于離散信道，其特性可由轉(zhuǎn)移概率矩陣來表示 因?yàn)橛械?章 差錯(cuò)控制編碼2010 Copyright 22SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 由先驗(yàn)概率 及轉(zhuǎn)移概率矩陣，可導(dǎo)出后驗(yàn)概率矩陣 及 的分布特性第8章 差錯(cuò)控制編碼2010 Copyright 23SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 譯碼規(guī)則對(duì)譯碼性能的影響 示例 設(shè)發(fā)送碼

14、字集 接收碼字集 兩不同的二元對(duì)稱信道分別為 (1) (2) 分析在兩種信道下不同譯碼規(guī)則對(duì)譯碼性能的影響。 解：若記譯碼的規(guī)則為第8章 差錯(cuò)控制編碼2010 Copyright 24SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 可能的譯碼方法包括如下 4 種 對(duì)于信道1： 不同譯碼規(guī)則導(dǎo)致的出錯(cuò)概率依次分別為 采用規(guī)則(2),出錯(cuò)概率最??；第8章 差錯(cuò)控制編碼2010 Copyright 25SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 對(duì)于信道2： 不同的譯碼規(guī)則導(dǎo)致的出錯(cuò)概率依次分別為 采用規(guī)則(3),出錯(cuò)概率最小。 啟示： 不同的譯碼規(guī)則，對(duì)誤碼率的影響

15、很大； 對(duì)不同的信道特性，應(yīng)選擇不同的譯碼規(guī)則。第8章 差錯(cuò)控制編碼2010 Copyright 26SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 最大后驗(yàn)譯碼準(zhǔn)則 已知后驗(yàn)概率矩陣 若 譯碼正確 譯碼錯(cuò)誤 誤碼的概率 正確譯碼的概率第8章 差錯(cuò)控制編碼2010 Copyright 27SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 若規(guī)定譯碼規(guī)則 則可使得差錯(cuò)概率最小最佳譯碼方法。 具體的譯碼操作方法 由 若 則取 作為譯碼輸出。第8章 差錯(cuò)控制編碼2010 Copyright 28SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 示例：利用最大后驗(yàn)

16、譯碼準(zhǔn)則分析上一示例的譯碼問題。 (1)首先確定系統(tǒng)的后驗(yàn)概率矩陣 a.若轉(zhuǎn)移概率矩陣為 因?yàn)橛?可得 導(dǎo)出后驗(yàn)概率矩陣第8章 差錯(cuò)控制編碼2010 Copyright 29SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 最佳的譯碼規(guī)則 正確譯碼的概率 誤碼率第8章 差錯(cuò)控制編碼2010 Copyright 30SCUT DT&P Labs第8章 差錯(cuò)控制編碼 信道編碼的基本概念和定理(續(xù)) b.若轉(zhuǎn)移概率矩陣為 同理可得 相應(yīng)的后驗(yàn)概率矩陣 2010 Copyright 31SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 此時(shí)譯碼規(guī)則相應(yīng)地變?yōu)?正確譯碼的概率 誤

17、碼率為 由本例可見： 采用后驗(yàn)概率譯碼準(zhǔn)則，無論哪一種情形，總是可以得到最好的譯碼效果。 第8章 差錯(cuò)控制編碼2010 Copyright 32SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 最大似然譯碼準(zhǔn)則 已知概率的基本關(guān)系式 對(duì)于離散無記憶信道 因而 在先驗(yàn)等概的條件下，最大后驗(yàn)概率譯碼規(guī)則可變?yōu)?即此時(shí)直接可根據(jù)轉(zhuǎn)移概率矩陣進(jìn)行最佳判決。 注意在上例中轉(zhuǎn)移概率矩陣與后驗(yàn)概率矩陣完全相同。第8章 差錯(cuò)控制編碼2010 Copyright 33SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 費(fèi)諾不等式 若記 發(fā)送符號(hào)集及分布 接收符號(hào)集及分布 發(fā)送與接收符號(hào)集中

18、元素相同 發(fā)送符號(hào)經(jīng)信道傳輸后出錯(cuò)的概率(誤碼率)可表示為 疑義度：發(fā)送 接收到 后，關(guān)于 仍然存在的平均不確定性稱之。 根據(jù)條件熵的定義，疑義度為第8章 差錯(cuò)控制編碼2010 Copyright 34SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 接收譯碼錯(cuò)誤判決的概率 正確的判決概率 與熵的定義類似，可定義判決的不確定性 定理 8.4.1(費(fèi)諾不等式) 與 間有如下的關(guān) 系式 費(fèi)諾不等式表明 的大小主要由判決不確定性及判決錯(cuò)誤導(dǎo)致信息的丟失的多少?zèng)Q定。 平均每個(gè)符號(hào)判決錯(cuò)誤導(dǎo)致信息的丟失小于等于 。第8章 差錯(cuò)控制編碼2010 Copyright 35SCUT DT&P La

19、bs 信道編碼的基本概念和定理(續(xù)) 聯(lián)合典型序列集 滿足下列條件的序列集 分別稱之 的 典型序列集和聯(lián)合典型序列集。 分別記為 和 。第8章 差錯(cuò)控制編碼2010 Copyright 36SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 條件下 的典型序列集定義為 記為 。 典型序列的有關(guān)性質(zhì) 性質(zhì)1 當(dāng) N 足夠大時(shí)，有 性質(zhì)2 當(dāng) N 足夠大時(shí)，有 上述性質(zhì)描述了典型序列集與熵函數(shù)及平均互信息之間的關(guān)系。第8章 差錯(cuò)控制編碼2010 Copyright 37SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 定義8.4.3 編碼速率(糾錯(cuò)編碼的信息率)定義為: 其中

20、 信息位長度， 編碼輸出碼字長度。 歸一化信道容量 已知離散信道的容量 有信息論的基本知識(shí)，有 定義歸一化信道容量為第8章 差錯(cuò)控制編碼2010 Copyright 38SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 若記發(fā)送序列為 接收序列為 對(duì)于離散無記憶信道： 對(duì)于N位的二元碼元序列，若編碼速率為 則 可能的碼字組合數(shù) 合法的碼字組合數(shù) 合法的碼字標(biāo)號(hào)集 設(shè)發(fā)送的消息編號(hào)為 ； 編碼 譯碼第8章 差錯(cuò)控制編碼2010 Copyright 39SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 發(fā)送編號(hào)為 消息時(shí)出錯(cuò)的概率 平均誤碼率可定義為 定義8.4.4 (可達(dá)

21、編碼速率) 若 則稱 是可達(dá)的。 第8章 差錯(cuò)控制編碼2010 Copyright 40SCUT DT&P Labs 信道編碼的基本概念和定理(續(xù)) 定理8.4.5 (信道編碼定理) 給定歸一化信道容量 若 ，則 是可達(dá)的。 信道編碼定理給出了編碼速率 可達(dá)的基本條件。 信道可達(dá)性的定義包含了可通過增大碼字的長度來改善信道編碼誤碼性能的思想。 信道編碼定理并沒有告訴我們?nèi)绾尉唧w應(yīng)如何編碼，才能保證譯碼能夠滿足 的條件。 第8章 差錯(cuò)控制編碼2010 Copyright 41SCUT DT&P Labs第8章 差錯(cuò)控制編碼 信道編碼的基本概念和定理(續(xù)) 例8.4.4 設(shè)某通信系統(tǒng)的不加編碼的錯(cuò)

22、誤概率為 編碼速率為 ，分析不同編碼方式的效果。 (1)每兩比特信息為一組進(jìn)行編碼 詳見書中的分析，相應(yīng)的錯(cuò)誤概率變?yōu)?2010 Copyright 42SCUT DT&P Labs第8章 差錯(cuò)控制編碼 信道編碼的基本概念和定理(續(xù)) (2)每三比特信息為一組進(jìn)行編碼 相應(yīng)的錯(cuò)誤概率變?yōu)?本例給出了一個(gè)示例，說明在反映編碼效率的編碼速率不變的情況下，可以通過改變碼字的長度來改善誤碼性能。2010 Copyright 43SCUT DT&P Labs8.5 線性分組碼的代數(shù)基礎(chǔ)* 2010 Copyright 44SCUT DT&P Labs 線性分組碼的代數(shù)基礎(chǔ) 定義8.5.1 對(duì)于某種代數(shù)運(yùn)

23、算法則“*”的非空集合G,滿足下列公理?xiàng)l件的時(shí)稱之為一個(gè)群： 封閉性： 結(jié)合率： 存在恒等元素： 存在逆元素： 定義8.5.2 稱群為交換群，若滿足如下的交換率 第8章 差錯(cuò)控制編碼2010 Copyright 45SCUT DT&P Labs 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 示例：整數(shù)集，按照加法運(yùn)算規(guī)則，構(gòu)成一個(gè)交換群。其中的恒等元素為“0”，任一元素的逆元素為即為該整數(shù)的負(fù)數(shù)。 示例：在二元的非空集合0,1中，定義運(yùn)算法則 該二元集合構(gòu)成一個(gè)交換群，其中的恒等元素為“0”，每個(gè)元素的逆元素為其自身。 第8章 差錯(cuò)控制編碼2010 Copyright 46SCUT DT&P Labs 線性分組

24、碼的代數(shù)基礎(chǔ)(續(xù)) 定理8.5.3 群G具有以下的性質(zhì)： (1) 群G的恒等元是唯一的，群中每個(gè)元素的逆元素也是唯一的； (2) 定義了運(yùn)算法則“*”的群G， ，有 定義8.5.4 若H是群G的一個(gè)非空子集，如果在同樣的運(yùn)算法則“*”下，集合H也構(gòu)成一個(gè)群，則非空子集稱為群G的一個(gè)子群。 定義8.5.5 設(shè)集合 是群 的一個(gè)子群， 是G中的一個(gè)滿足條件 的元素，則把 定義為子群H在群中的一個(gè)關(guān)于的左陪集；把 定義為子群H在群中的一個(gè)關(guān)于的右陪集。 第8章 差錯(cuò)控制編碼2010 Copyright 47SCUT DT&P Labs 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 對(duì)于交換群，左陪集和右陪集相等，簡稱

25、為陪集。 定理8.5.6 子群具有以下的主要性質(zhì)（1）群 的所有元素可由子群 以及它的若干陪集構(gòu)成的集合表示其中 。（2）群G中的兩個(gè)元素 和 在子群的同一陪集之中的充分必要條件是： （3）子群H的兩個(gè)不相同的陪集一定不相交，即兩個(gè)不同的陪集一定沒有公共元素。 第8章 差錯(cuò)控制編碼2010 Copyright 48SCUT DT&P Labs 線性分組碼的代數(shù)基礎(chǔ)(續(xù))定義8.5.7 若在非空集合F中，規(guī)定了“”和“*”兩種運(yùn)算，且如下的條件（1）非空集合構(gòu)成運(yùn)算法則“”的交換群；（2）非空集合構(gòu)成運(yùn)算法則“*”的交換群；（3）對(duì)兩種運(yùn)算法則“”和“*”，非空集合中的元素滿足分配律，即對(duì)任意的

26、 ，有 則稱非空集合F構(gòu)成一個(gè)域，其集合中包含的元素的個(gè)數(shù)稱為該集合的階數(shù)。示例：對(duì)于普通的加法和乘法運(yùn)算 全體有理數(shù)構(gòu)成一個(gè)有理數(shù)域； 全體實(shí)數(shù)構(gòu)成一個(gè)實(shí)數(shù)域； 全體復(fù)數(shù)則構(gòu)成一個(gè)復(fù)數(shù)域。第8章 差錯(cuò)控制編碼2010 Copyright 49SCUT DT&P Labs 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 有限域的概念 有限域：包含有限的q個(gè)元素的域稱之； 有限域又稱為伽羅華（Galois）域，記為 。 有限域中元素的個(gè)數(shù)q，一定是某個(gè)素?cái)?shù)p的冪，即 。 示例：非空的二元集合0,1中，定義加、乘運(yùn)算 加運(yùn)算 乘運(yùn)算 構(gòu)成二元有限域第8章 差錯(cuò)控制編碼2010 Copyright 50SCUT DT&

27、P Labs 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 包含素?cái)?shù) 的 n 次冪 個(gè)元素的有限域 是線性分組碼中最常用的有限域。 元素 的階 ，因?yàn)?中只有有限個(gè)元素 一定存在正整數(shù)k，使得 ，能使上式成立的最小的k 稱為元素 的階。 本原元 若對(duì)于元素 ，其階等于 ，則該元素稱為有限域 的本原元。 任何有限域都存在本原元。 有限域中的任一非零元素都可以用本原元的某次冪來表示。第8章 差錯(cuò)控制編碼2010 Copyright 51SCUT DT&P Labs 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 示例：有限域 ，其中 為本原元。 由本原元的定義，有 。 對(duì)該有限域，加法和乘法可分別定義為第8章 差錯(cuò)控制編碼 *2010

28、 Copyright 52SCUT DT&P Labs 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 系數(shù)定義在二元有限域上的多項(xiàng)式 一般地，總有 其中的余式可記為 ，稱 為模。 多項(xiàng)式關(guān)于模 的加法和乘法運(yùn)算 加法 乘法 若 為 次的多項(xiàng)式，則余式具有如下的一般形式第8章 差錯(cuò)控制編碼2010 Copyright 53SCUT DT&P Labs 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 因?yàn)?若 則 共有 種不同的組合， 相應(yīng)地有 種不同的 余式。 若將每個(gè)余式 看作一個(gè)元素，若 是一個(gè)不可約多項(xiàng)式，則所對(duì)應(yīng)的 個(gè)余式 作為元素的集合構(gòu)成一個(gè)有限域。第8章 差錯(cuò)控制編碼2010 Copyright 54SCUT DT&P

29、 Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 示例：多項(xiàng)式 是一不可約多項(xiàng)式，以此為模的余式為元素的集合： 構(gòu)成一有限域。 元素間的加法 與乘法運(yùn)算， 參見加法表與 乘法表。2010 Copyright 55SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 本原多項(xiàng)式 n 次不可約多項(xiàng)式 模 有限域 若 的根是本原元，則稱 是本原多項(xiàng)式。 示例：多項(xiàng)式 是一不可約多項(xiàng)式。 由此 因?yàn)閷?duì)于模 因此 是多項(xiàng)式 的根 即有2010 Copyright 56SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 示例(續(xù)) 參見右表，元素

30、 的階為 ， 可見 是一本 原元。 多項(xiàng)式 為本原多項(xiàng)式。2010 Copyright 57SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 多項(xiàng)式的根 這里所討論的多項(xiàng)式是指系數(shù)與根均定義在有限域中的多項(xiàng)式。 示例：求解定義在有限域 上的多項(xiàng)式 的根。 注意：在上面的方程中，未知數(shù)是 。 有限域上的方程并無一般解，因?yàn)榉匠痰慕馐嵌x在有限域上的，所有可能的解只有有限多個(gè)，所以可用試探法求解； 根據(jù)上一示例的元素表，可得 2010 Copyright 58SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 同樣可得 可見 是方程的根。 多項(xiàng)

31、式的一個(gè)重要性質(zhì) 定理8.5.8 系數(shù)取值在二元域0,1上的多項(xiàng)式 對(duì)任意的整數(shù) l ，均有2010 Copyright 59SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 極小多項(xiàng)式 定義8.5.9 設(shè) 是 中的元素， 是系數(shù)為二元域上元素、以 為根的最低次多項(xiàng)式，則稱 是 的極小多項(xiàng)式。 定理8.5.10 上的任何元素 必有一個(gè)極小多項(xiàng)式。 定理8.5.11 有限域 上的極小多項(xiàng)式一定是不可約、且是唯一的。 若 的極小多項(xiàng)是 ，則應(yīng)有 ，由定理8.5.8，有 即 均為該極小多項(xiàng)式的根。2010 Copyright 60SCUT DT&P Labs第8章 差錯(cuò)控

32、制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 示例：求有限域 上，元素 的極小多項(xiàng) 。 由前面分析，對(duì) 均有： 因?yàn)?可見從 的第四項(xiàng)后開始重復(fù)，因此最小多項(xiàng)式為2010 Copyright 61SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 線性空間與其子空間 定義8.5.12 設(shè) 是一個(gè)數(shù)域， 是某一類運(yùn)算對(duì)象的非空集合，在“”和“*”兩種運(yùn)算規(guī)則下，滿足下列條件（1）非空集合 對(duì)“”運(yùn)算規(guī)則構(gòu)成一交換群；（2）非空集合 和數(shù)域 在運(yùn)算規(guī)則“*”下滿足封閉性，即對(duì)任 ，有（3）非空集合 和數(shù)域 在運(yùn)算規(guī)則“*”下滿足結(jié)合律，即對(duì)任 ，有（4）

33、非空集合和數(shù)域在運(yùn)算規(guī)則“”和“*”下滿足分配律，即對(duì)任 ，有 則稱非空集合 為 上的線性空間。2010 Copyright 62SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 線性分組碼與線性空間 線性分組碼的碼字是定義在有限域上的線性空間中的元素。 碼字 碼字 的“+”運(yùn)算定義為 系數(shù)的“*”運(yùn)算定義為 在本章中，均假定2010 Copyright 63SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 定義8.5.13 在n維的線性空間 中，若某非空子集 滿足線性空間的條件，則稱 為線性空間的子空間。 子空間的基本性質(zhì)（1）子空間

34、在“”運(yùn)算規(guī)則下滿足封閉性，即對(duì)任意的 ，有 （2）子空間 在“”運(yùn)算規(guī)則下滿足交換律 （3）子空間 滿足結(jié)合律，即對(duì)任意2010 Copyright 64SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的代數(shù)基礎(chǔ)(續(xù)) 子空間的基本性質(zhì)（4）恒等元 一定在子空間 中: （5）若 ，則其逆元素 一定在子空間 中，即有 （6）子空間 在“*”運(yùn)算規(guī)則下滿足封閉性，即若 則 （7）子空間 在“*”運(yùn)算規(guī)則下滿足結(jié)合律，即若 則（8）子空間 在“”運(yùn)算規(guī)則和“*”運(yùn)算規(guī)則下，滿足分配律，即若 ,則 2010 Copyright 65SCUT DT&P Labs8.6 線性分組碼的基本性質(zhì)

35、 2010 Copyright 66SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì) 線性分組碼編碼的一般表達(dá)形式 輸入信息碼組 輸出編碼碼字 其中 線性分組碼的一般記法： 其中k表示碼字中信息位的個(gè)數(shù)，n為碼字的長度。 線性分組碼 中許用碼字的個(gè)數(shù)為 。2010 Copyright 67SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 許用碼字間的距離碼距 定義8.6.1 兩個(gè)n元的碼字： 與 兩者間的漢明距離定義為 有關(guān)碼距的性質(zhì)（1）自反性：任一碼字 與其自身間的碼距為零。（2）對(duì)稱性：對(duì)任兩碼字 與 ， 與 間的碼距與 與 間的碼距相等

36、 （3）三角不等式成立：對(duì)任意的三個(gè)碼字 、 和 ，它們間的碼距關(guān)系滿足 2010 Copyright 68SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 碼距與碼的檢錯(cuò)糾錯(cuò)能力之間的關(guān)系 碼字間的最小距離：最小碼距定義為 線性分組碼的基本性質(zhì) 性質(zhì)1 若要線性分組碼能夠檢測(cè)出任一碼字中的小于等于 位的誤碼，則應(yīng)滿足 2010 Copyright 69SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 性質(zhì)2 若要線性分組碼能夠檢出并糾正任一碼字中的小于等于 位的誤碼，則應(yīng)滿足 性質(zhì)3 若要線性分組碼能夠檢出任一碼字中的 位誤碼，同時(shí)能夠

37、糾正其中 ( )位的誤碼，則應(yīng)滿足 2010 Copyright 70SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 線性分組碼的生成矩陣與監(jiān)督矩陣 差錯(cuò)控制編碼一般可表示為 特別地，對(duì)線性分組碼 表示為矩陣形式2010 Copyright 71SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 生成矩陣 生成矩陣定義為 系統(tǒng)碼的生成矩陣 系統(tǒng)碼的特點(diǎn) 系統(tǒng)碼的編碼輸出結(jié)構(gòu) 信息位部份 監(jiān)督位部份2010 Copyright 72SCUT DT&P Labs 線性分組碼的基本性質(zhì)(續(xù)) 由 可得生成矩陣 若系統(tǒng)碼結(jié)構(gòu)為 生成矩陣相應(yīng)地為第

38、8章 差錯(cuò)控制編碼2010 Copyright 73SCUT DT&P Labs 線性分組碼的基本性質(zhì)(續(xù)) 監(jiān)督矩陣 在線性分組碼的碼生成方程組中的監(jiān)督位為 因?yàn)?因此可得第8章 差錯(cuò)控制編碼2010 Copyright 74SCUT DT&P Labs 線性分組碼的基本性質(zhì)(續(xù)) 方程的矩陣形式 定義監(jiān)督矩陣為 監(jiān)督矩陣確定了碼字沒有錯(cuò)誤的必要條件。第8章 差錯(cuò)控制編碼2010 Copyright 75SCUT DT&P Labs 線性分組碼的基本性質(zhì)(續(xù)) 錯(cuò)誤圖樣：描述錯(cuò)誤及位置的一個(gè)矢量。 對(duì)于定義在二元域上的碼字，知道了錯(cuò)誤的位置等效于知道了錯(cuò)誤。 若將 看作一特殊的錯(cuò)誤圖樣 接收

39、碼字可一般地表示為： 若沒有出錯(cuò)，顯然有第8章 差錯(cuò)控制編碼2010 Copyright 76SCUT DT&P Labs 線性分組碼的基本性質(zhì)(續(xù)) 伴隨式(校正子) 因?yàn)?定義伴隨式為 伴隨式是一個(gè) 維的向量，總共有 種不同的組合。 個(gè)不同的伴隨式可對(duì)應(yīng) 種不同錯(cuò)誤圖樣。 伴隨式只與錯(cuò)誤圖樣和監(jiān)督矩陣有關(guān)。 若 則接收碼字 中一定出現(xiàn)了錯(cuò)誤； 若 如果錯(cuò)誤圖樣是一個(gè)許用碼字，在錯(cuò)誤不能被檢測(cè)出； 如何錯(cuò)誤圖樣不是一個(gè)許用圖樣，則可檢測(cè)出該錯(cuò)誤。第8章 差錯(cuò)控制編碼2010 Copyright 77SCUT DT&P Labs 線性分組碼的基本性質(zhì)(續(xù)) 示例：構(gòu)建一個(gè)可糾正一位誤碼、具有系

40、統(tǒng)碼結(jié)構(gòu)的（7，4）線性分組碼。 解：該碼的碼字長度n7，信息位k4，監(jiān)督位有nk3位 伴隨式共有 剛好可對(duì)于無誤碼，不同位置的7種1比特誤碼共8種狀態(tài) 設(shè)建立伴隨式與誤碼的對(duì)應(yīng)關(guān)系第8章 差錯(cuò)控制編碼2010 Copyright 78SCUT DT&P Labs 線性分組碼的基本性質(zhì)(續(xù)) 當(dāng)僅出現(xiàn)一位誤碼時(shí)，有如下關(guān)系 若沒有誤碼： 應(yīng)使得 因?yàn)殄e(cuò)誤的比特實(shí)際上并不能夠單獨(dú)提出進(jìn)行伴隨式的計(jì)算 因此編碼時(shí)應(yīng)保證 (*)第8章 差錯(cuò)控制編碼2010 Copyright 79SCUT DT&P Labs 線性分組碼的基本性質(zhì)(續(xù)) 對(duì)于系統(tǒng)碼結(jié)構(gòu)的分組碼， 已由輸入信息位決定 因此應(yīng)選擇監(jiān)督位

41、， ，使得上述關(guān)系式成立，即 由上面的(*)式可得監(jiān)督方程第8章 差錯(cuò)控制編碼2010 Copyright 80SCUT DT&P Labs 線性分組碼的基本性質(zhì)(續(xù)) 相應(yīng)地監(jiān)督矩陣為 由監(jiān)督矩陣與生成矩陣的關(guān)系式，可得生成矩陣 注意：線性分組碼中伴隨式與誤碼的對(duì)應(yīng)關(guān)系并非可任意設(shè)定 糾錯(cuò)編碼監(jiān)督矩陣和生成矩陣更一般的求解方法將在稍后討論。第8章 差錯(cuò)控制編碼2010 Copyright 81SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 生成矩陣與監(jiān)督矩陣的有關(guān)性質(zhì) 系統(tǒng)碼結(jié)構(gòu)的生成矩陣與監(jiān)督矩陣結(jié)構(gòu) 2010 Copyright 82SCUT DT&P La

42、bs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 主要性質(zhì)（1）生成矩陣G中的每一行都是一個(gè)許用碼字； 因?yàn)?若取 即有 因而有上述結(jié)論。2010 Copyright 83SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù))（2）生成矩陣G的秩等于k，生成矩陣中的個(gè)獨(dú)立的行向量碼字構(gòu)成碼字子空間的一組基； 因?yàn)镚中的行向量 因此任一碼字可表示為 由此可得上述結(jié)論。2010 Copyright 84SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) （3）生成矩陣G和監(jiān)督矩陣H滿足如下的關(guān)系 因?yàn)?因此有 由此可得上述結(jié)論。2010 Copy

43、right 85SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 線性分組碼的最小碼距與最小碼重的關(guān)系 定義8.6.2 線性分組碼每個(gè)碼字中“1”的碼元的個(gè)數(shù)定義為該碼字的重量，簡稱為碼重；碼字集中碼重最小的碼字的重量定義為最小碼重。 定理8.6.3 線性分組碼的最小碼距等于其非零碼字的最小碼重。 記碼字 碼重 因?yàn)?碼字間距離 因此有2010 Copyright 86SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 示例：已知某線性分組碼的生成矩陣 (1)分析該碼的差錯(cuò)控制能力。該分組碼所有可能的碼字 直接觀測(cè)可得最小碼重為3，由此可得

44、最小碼距3； 該碼若用于檢錯(cuò)，可檢出2位誤碼； 該碼若用于糾錯(cuò)，可糾正1位誤碼。2010 Copyright 87SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) (2)求監(jiān)督矩陣 由監(jiān)督矩陣與生成矩陣間的關(guān)系 可得監(jiān)督矩陣2010 Copyright 88SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) (3)1位誤碼與伴隨式之間的關(guān)系，1位誤碼的所有圖樣 可得 歸納可得2010 Copyright 89SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) (4)糾錯(cuò)能力分析 a、假定只出現(xiàn)1位誤碼，若收到碼字

45、計(jì)算伴隨式 查表可知該伴隨式對(duì)應(yīng)錯(cuò)誤圖樣 糾錯(cuò) 獲得正確的碼字 。2010 Copyright 90SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) b、假定出現(xiàn)2位誤碼，例如收到碼字 該碼字由許用碼字 出現(xiàn)2位誤碼得到。 計(jì)算伴隨式 查表可知該伴隨式對(duì)應(yīng)錯(cuò)誤圖樣 糾錯(cuò)操作 并不能獲得正確的碼字。2010 Copyright 91SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 出現(xiàn)2位誤碼時(shí)伴隨式的計(jì)算結(jié)果可分解為 與出現(xiàn)錯(cuò)誤圖樣 所得的伴隨式相同。 應(yīng)為該伴隨式已經(jīng)用于對(duì)應(yīng)1位誤碼 的錯(cuò)誤圖樣，因而不能糾正該2位誤碼。 兩位誤碼已經(jīng)超

46、出了該分組碼的糾錯(cuò)能力范圍。2010 Copyright 92SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 線性分組碼的標(biāo)準(zhǔn)陣、陪集首和陪集 線性分組碼 具有 個(gè)不同的伴隨式，除全零的圖樣 外，可分別對(duì)應(yīng) 種不同的錯(cuò)誤圖樣： 這 種錯(cuò)誤圖樣與伴隨式建立的確定的對(duì)應(yīng)關(guān)系，是所有可糾正的錯(cuò)誤圖樣。 許用碼字 與 的任意組合 ，均可正確譯碼2010 Copyright 93SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 所有可正確譯碼的接收碼字可用如下的矩陣表示 該矩陣稱為線性分組碼 的標(biāo)準(zhǔn)陣。 標(biāo)準(zhǔn)陣中第一列的每個(gè)元素稱為一個(gè)陪集首 標(biāo)

47、準(zhǔn)陣的每一行為該行陪集首所對(duì)應(yīng)的陪集 2010 Copyright 94SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 綜上， 對(duì)于標(biāo)準(zhǔn)陣中的陪集首，有特定的伴隨式與其對(duì)應(yīng) 一般地，記接收碼字為 若 則 若2010 Copyright 95SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 示例：分析生成矩陣如下的 線性分組碼的標(biāo)準(zhǔn)陣等特性 由生成矩陣可得許用碼字集為 確定可糾錯(cuò)的誤碼圖樣 可糾正的錯(cuò)誤圖樣的選擇： (1)具有不同伴隨式的圖樣； (2)通常正常工作的通信系統(tǒng)誤碼出現(xiàn)少的概率較大，選擇可糾正的錯(cuò)誤圖樣通常從1比特的錯(cuò)誤圖樣開

48、始。2010 Copyright 96SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 標(biāo)準(zhǔn)陣 錯(cuò)誤圖樣與 伴隨式的關(guān)系2010 Copyright 97SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 漢明碼 定義8.6.4 如果線性分組碼 滿足碼字長度 ，信息位 的參數(shù)條件，則稱這種碼為漢明碼。 漢明碼的編碼效率所以當(dāng)碼字足夠長時(shí)，漢明碼是一種高效碼。 漢明碼的糾錯(cuò)能力分析 漢明碼碼字長度 信息位長度 監(jiān)督位長度 伴隨式個(gè)數(shù) 2010 Copyright 98SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù))

49、 其中全零的伴隨式用于對(duì)應(yīng)無誤碼的狀態(tài) 其余的 個(gè)伴隨式可分別對(duì)應(yīng) 種錯(cuò)誤圖樣。 因?yàn)楹侠淼耐ㄐ畔到y(tǒng)設(shè)計(jì)應(yīng)使得一個(gè)碼字中誤碼位數(shù)少的概率大于誤碼位數(shù)大的概率。 因此伴隨式應(yīng)用于對(duì)應(yīng)誤碼位數(shù)少的錯(cuò)誤圖樣。 漢明碼長度為 。漢明碼的非零伴隨式全部用于對(duì)應(yīng)1位誤碼，所以漢明碼能糾正所有的1位誤碼。2010 Copyright 99SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 系統(tǒng)碼結(jié)構(gòu)的漢明碼的構(gòu)建 監(jiān)督矩陣共有n列，其中第i列對(duì)應(yīng)碼字第i位錯(cuò)誤圖樣的伴隨式，系統(tǒng)碼結(jié)構(gòu)的監(jiān)督矩陣右側(cè)的子陣必須是一個(gè)單位陣。 監(jiān)督矩陣的n個(gè)不同組合的列除了構(gòu)成單位陣的 列外，其余的k列

50、可任意的排列。 確定監(jiān)督矩陣之后，可得生成矩陣如下2010 Copyright 100SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 示例：設(shè)計(jì)一個(gè) 的漢明碼 構(gòu)建監(jiān)督矩陣 由此可得2010 Copyright 101SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 可得生成矩陣2010 Copyright 102SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 擴(kuò)展?jié)h明碼 已知普通漢明碼可糾正所有1位誤碼，所以最小碼距 當(dāng)同時(shí)出現(xiàn)第 i 位和第 j 兩位不同的誤碼時(shí)，有 因?yàn)?已經(jīng)用于對(duì)應(yīng)第 k 位誤碼的伴

51、隨式，因此該伴隨式用于糾錯(cuò)時(shí)將產(chǎn)生錯(cuò)誤。即兩位或兩位以上誤碼無法發(fā)現(xiàn)，因此 綜合上面有關(guān)最小碼距的關(guān)系式，且碼距必須為整數(shù)，因此2010 Copyright 103SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 擴(kuò)展?jié)h明碼可通過增加1位編碼的監(jiān)督位長度，使得該碼可以糾正任意的1位錯(cuò)誤，同時(shí)發(fā)現(xiàn)任意的2位錯(cuò)誤。 擴(kuò)展?jié)h明碼的監(jiān)督矩陣 其中 是原來普通漢明碼的監(jiān)督矩陣。2010 Copyright 104SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 擴(kuò)展?jié)h明碼碼字 其中原漢明碼碼字 新增監(jiān)督位 當(dāng)無誤碼時(shí) 擴(kuò)展?jié)h明碼的伴隨式仍然為零向量

52、。 2010 Copyright 105SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 當(dāng)出現(xiàn)任意的1位，如第 j 位誤碼時(shí) 伴隨式等于監(jiān)督矩陣的第 j 列，可發(fā)現(xiàn)出錯(cuò)并可糾正。2010 Copyright 106SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 若第 i 和 j 位同時(shí)出錯(cuò)，伴隨式 其中的最后1位為零。由此可判斷出現(xiàn)了2位錯(cuò)誤。 擴(kuò)展?jié)h明碼通過增加1位監(jiān)督為，使得碼字間的最小距離2010 Copyright 107SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 線性分組碼的糾錯(cuò)能力分析 漢

53、明界：漢明界確定了一個(gè)參數(shù)為 的線性分組碼可能獲得的最大糾錯(cuò)能力。有關(guān)漢明界有如下的定理： 定理8.6.5 線性分組碼 能夠糾正碼字中任意的小于等于 位誤碼的圖樣數(shù)小于 。 若符號(hào) 表示所有的 個(gè)元素中取 個(gè)的組合數(shù)。 長度為 的碼字中任意的小于等于 位錯(cuò)誤的圖樣數(shù)為 線性分組碼 不同的伴隨式的個(gè)數(shù)為 ，要保證每個(gè)不同的錯(cuò)誤圖樣有不同的伴隨式與其對(duì)應(yīng)，應(yīng)有 因而有上述結(jié)論。2010 Copyright 108SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 定義8.6.6 若能夠糾正 個(gè)及個(gè)以下的全部錯(cuò)誤的線性分組碼滿足條件 則稱這種線性分組碼為完備碼。 漢明碼是一

54、種完備碼。 普洛特金界：普洛特金界確定了線性分組碼 差錯(cuò)控制能力的上限。 定理8.6.6 線性分組碼 的最小碼距 小于由下式確定的所謂的普洛特金界 2010 Copyright 109SCUT DT&P Labs第8章 差錯(cuò)控制編碼 線性分組碼的基本性質(zhì)(續(xù)) 示例 (1)判斷線性分組碼 有無糾正2位誤碼的可能性； (2)判斷線性分組碼 有無糾正2位誤碼的可能性。 分析 (1)對(duì)于線性分組碼 ，因?yàn)?所以不可能構(gòu)建能夠糾正2位錯(cuò)誤的分組碼； (2)對(duì)于線性分組碼 ，因?yàn)?因此有可能可以構(gòu)建能夠糾正2位錯(cuò)誤的分組碼。2010 Copyright 110SCUT DT&P Labs8.7 循環(huán)碼2

55、010 Copyright 111SCUT DT&P Labs 循環(huán)碼 循環(huán)碼是線性分組碼的一個(gè)重要子類。 循環(huán)碼為我們根據(jù)糾錯(cuò)的要求進(jìn)行編碼參數(shù)的設(shè)計(jì)和結(jié)構(gòu)的實(shí)現(xiàn)提供了一種系統(tǒng)的方法。 定義 8.7.1 記 為線性分組碼的碼字集，如果對(duì)任意的 ， 循環(huán)左移或循環(huán)右移任意位后得到的碼字 ，仍有 ，則稱該線性分組碼為循環(huán)碼。 碼多項(xiàng)式 碼字與多項(xiàng)式可建立如下的對(duì)應(yīng)關(guān)系，相應(yīng)的多項(xiàng)式稱之。 碼多項(xiàng)式系數(shù)的加乘運(yùn)算規(guī)則 加運(yùn)算 乘運(yùn)算 第8章 差錯(cuò)控制編碼2010 Copyright 112SCUT DT&P Labs 循環(huán)碼(續(xù)) 整數(shù)域中的同余類 在整數(shù)除法中，取定整數(shù)除數(shù)n，將所有整數(shù)m按除以

56、所得的余數(shù)進(jìn)行分類，余數(shù)相同的整數(shù)歸為一類，稱為關(guān)于n的同余類 Q與p均為整數(shù)。關(guān)于n的同余類記為 多項(xiàng)式域中的同余類 同理可定義關(guān)于 多項(xiàng)式的同余類 記為第8章 差錯(cuò)控制編碼2010 Copyright 113SCUT DT&P Labs 循環(huán)碼(續(xù)) 示例：多項(xiàng)式 關(guān)于多項(xiàng)式 因?yàn)?即兩者的余式相同。第8章 差錯(cuò)控制編碼2010 Copyright 114SCUT DT&P Labs 循環(huán)碼(續(xù)) 循環(huán)碼的代數(shù)結(jié)構(gòu)(有關(guān)循環(huán)碼的主要定理) 定理 8.7.2 若 是長度為n的循環(huán)碼中的一個(gè)碼多項(xiàng)式，i為不等于零的整數(shù)，則 按模 運(yùn)算的余式必為循環(huán)碼中的另一碼多項(xiàng)式。 定理 8.7.3 在循環(huán)

57、碼 中，冪次數(shù)為 ，且其常數(shù)項(xiàng)不等于“0”的碼字多項(xiàng)式有一個(gè)且只有一個(gè)。 因?yàn)槎囗?xiàng)式 的冪均小于n，由上述兩個(gè)定理，可知這些多項(xiàng)式均為碼多項(xiàng)式。第8章 差錯(cuò)控制編碼2010 Copyright 115SCUT DT&P Labs第8章 差錯(cuò)控制編碼 循環(huán)碼(續(xù)) 由 可知矩陣g中的每一行均為一個(gè)碼字。 因?yàn)榫仃噂的秩為k，可知相應(yīng)的k個(gè)碼字互不相關(guān)，因此可以構(gòu)成相應(yīng)的碼字空間的一組基。 因此可定義相應(yīng)的碼多項(xiàng)式生成矩陣2010 Copyright 116SCUT DT&P Labs 循環(huán)碼(續(xù)) 相應(yīng)地可定義碼的生成多項(xiàng)式 給定信息碼組 ，由碼多項(xiàng)式生成矩陣，可得相應(yīng)的碼多項(xiàng)式為第8章 差錯(cuò)控

58、制編碼2010 Copyright 117SCUT DT&P Labs 循環(huán)碼(續(xù)) 定理 8.7.4 在循環(huán)碼中，所有的碼多項(xiàng)式 都可以被生成多項(xiàng)式 整除。 因?yàn)?所以定理的結(jié)論。 推論 8.7.5 次數(shù)不大于 次的任何多項(xiàng)式與生成多項(xiàng)式 的乘積都為碼多項(xiàng)式。 有上式很容易看出結(jié)論成立。 定理 8.7.6 循環(huán)碼的生成多項(xiàng)式 是多項(xiàng)式 的一個(gè)因式。 第8章 差錯(cuò)控制編碼2010 Copyright 118SCUT DT&P Labs 循環(huán)碼(續(xù)) 由定理8.7.3，定理8.7.6，可歸納判斷生成多項(xiàng)式的充要條件 （1） 是一個(gè) 次的多項(xiàng)式； （2） 的常數(shù)項(xiàng)不等于0； （3） 是 的一個(gè)因式

59、。 定義 8.7.7 定義式 為循環(huán)碼的一致校驗(yàn)多項(xiàng)式。 因?yàn)榇a多項(xiàng)式可以表示為 因此有 由此，可利用一致校驗(yàn)多項(xiàng)式對(duì)接收的碼字進(jìn)行差錯(cuò)校驗(yàn)。第8章 差錯(cuò)控制編碼2010 Copyright 119SCUT DT&P Labs 循環(huán)碼(續(xù)) 示例：分析多項(xiàng)式 能否作為循環(huán)碼 的生成多項(xiàng)式。 因?yàn)?且其冪 及常數(shù)項(xiàng)不為零，所以可作為 的生成多項(xiàng)式。 所得到的循環(huán)碼的生成矩陣 輸入信息位 編碼輸出 是一種非系統(tǒng)碼的編碼方式。第8章 差錯(cuò)控制編碼2010 Copyright 120SCUT DT&P Labs 循環(huán)碼(續(xù)) 系統(tǒng)碼結(jié)構(gòu)的循環(huán)碼 輸入信息位與對(duì)應(yīng)的多項(xiàng)式 由 可得 整理后可得 取編碼輸

60、出 根據(jù)推論 8.7.5，且該多項(xiàng)式對(duì)應(yīng)的碼字具有系統(tǒng)碼結(jié)構(gòu) 因此該碼為系統(tǒng)碼結(jié)構(gòu)的循環(huán)碼。第8章 差錯(cuò)控制編碼2010 Copyright 121SCUT DT&P Labs 循環(huán)碼(續(xù)) 示例：已知循環(huán)碼 的生成多項(xiàng)式 輸入信息碼組 求系統(tǒng)碼編碼輸出。 由 可得 碼字多項(xiàng)式為 或 系統(tǒng)碼編碼輸出第8章 差錯(cuò)控制編碼2010 Copyright 122SCUT DT&P Labs 循環(huán)碼(續(xù)) 系統(tǒng)碼結(jié)構(gòu)的循環(huán)碼的生成矩陣和監(jiān)督矩陣 已知系統(tǒng)碼結(jié)構(gòu)的線性分組碼生成矩陣為 系統(tǒng)碼結(jié)構(gòu)的循環(huán)碼碼多項(xiàng)式的一般形式 根據(jù)生成矩陣每一行對(duì)應(yīng)相應(yīng)一個(gè)特殊碼字的特點(diǎn) 分別取 計(jì)算 可得 由此可導(dǎo)出系統(tǒng)碼結(jié)