信道編碼(糾錯碼).ppt

1、信道編碼,第6章,2,6.1 糾錯編譯碼的基本原理與分析方法 6.2 線性分組碼 6.3 卷積碼,內(nèi)容,3,信源編碼 提高數(shù)字信號有效性 將信源的模擬信號轉(zhuǎn)變?yōu)閿?shù)字信號 降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮) 信道編碼 提高數(shù)字通信可靠性 數(shù)字信號在信道的傳輸過程中,由于實(shí)際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會產(chǎn)生誤碼。,編碼,4,6.1 糾錯編譯碼的基本原理與分析方法,5,6.1.1 差錯和差錯控制系統(tǒng)分類,差錯率是衡量傳輸質(zhì)量的重要指標(biāo)之一,它有幾種不同的定義。 碼元差錯率/符號差錯率 指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯的碼元數(shù)所占的比例(平均值),簡稱誤碼率。 是指信號差錯概率

2、比特差錯率 /比特誤碼率： 在傳輸?shù)谋忍乜倲?shù)中發(fā)生差錯的比特數(shù)所占比例 是指信息差錯概率 對二進(jìn)制傳輸系統(tǒng),符號差錯等效于比特差錯;對多進(jìn)制系統(tǒng),一個符號差錯對應(yīng)多少比特差錯卻難以確定,6,差錯率,根據(jù)不同的應(yīng)用場合對差錯率有不同的要求: 在電報傳送時,允許的比特差錯率約為: 104105； 計算機(jī)數(shù)據(jù)傳輸,一般要求比特差錯率小于: 108109； 在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯率,7,差錯圖樣,為定量地描述信號的差錯,定義差錯圖樣E E=CR (模M ) 最常用的二進(jìn)制碼可當(dāng)作特例來研究,其差錯圖樣等于收碼與發(fā)碼的模2加,即 E = CR 或 C = RE

3、設(shè)發(fā)送的碼字C 1 1 1 1 1 1 1 1 1 1 接收的碼字R 1 0 0 1 0 0 1 1 1 1 差錯的圖樣E 0 1 1 0 1 1 0 0 0 0 差錯圖樣中的“1”既是符號差錯也是比特差錯,差錯的個數(shù)叫漢明距離。,0:傳輸中無錯 1:傳輸中有錯,8,差錯圖樣,隨機(jī)差錯： 差錯是相互獨(dú)立的,不相關(guān) 存在這種差錯的信道是無記憶信道或隨機(jī)信道 突發(fā)差錯： 指成串出現(xiàn)的錯誤,錯誤與錯誤間有相關(guān)性,一個差錯往往要影響到后面一串字 E: 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0,突發(fā)長度= 4,突發(fā)長度= 6,9,糾錯碼分類,從功

4、能角度講,差錯碼分為檢錯碼和糾錯碼 檢錯碼：用于發(fā)現(xiàn)差錯 糾錯碼：能自動糾正差錯 糾錯碼與檢錯碼在理論上沒有本質(zhì)區(qū)別,只是應(yīng)用場合不同,而側(cè)重的性能參數(shù)也不同。,10,糾錯碼分類,按照對信息序列的處理方法,有分組碼和卷積碼 分組碼： 將k個信息碼元分成一組,由這k個碼元按照一定規(guī)則產(chǎn)生r個監(jiān)督碼元,組成長度n = k + r的碼字,卷積碼： 先將信息序列分組,不同的是編解碼運(yùn)算不僅與本組信息有關(guān),而且還與前面若干組有關(guān)。,k,k,010 101 010 001 110,010 xxxx 101xxxx 010 xxxx,r,n,r,11,糾錯碼分類,按照碼元與原始信息位的關(guān)系,分為 線性碼：所

5、有碼元均是原始信息元的線性組合,編碼器不帶反饋回路。 非線性碼：碼元并不都是信息元的線性組合,可能還與前面已編的碼元有關(guān),編碼器可能含反饋回路。 由于非線性碼的分析比較困難,早期實(shí)用的糾錯碼多為線性碼,但當(dāng)今發(fā)現(xiàn)的很多好碼恰恰是非線性碼。,12,糾錯碼分類,按照適用的差錯類型,分成: 糾隨機(jī)差錯碼:用于隨機(jī)差錯信道,其糾錯能力用碼組內(nèi)允許的獨(dú)立差錯的個數(shù)來衡量。 糾突發(fā)差錯碼:針對突發(fā)差錯而設(shè)計,其糾錯能力主要用可糾突發(fā)差錯的最大長度來衡量,13,差錯控制系統(tǒng)分類,前向糾錯(FEC)： 發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。 接收端信道譯碼器對接收碼字進(jìn)行譯碼,若傳輸中產(chǎn)生的差

6、錯數(shù)目在碼的糾錯能力之內(nèi)時,譯碼器對差錯進(jìn)行定位并加以糾正。,14,差錯控制系統(tǒng)分類,自動請求重發(fā)(ARQ)： 發(fā)端發(fā)送檢錯碼， 收端譯碼器判斷當(dāng)前碼字傳輸是否出錯； 當(dāng)有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字(全部或部分)。,15,差錯控制系統(tǒng)分類,混合糾錯(HEC)： 是FEC與ARQ方式的結(jié)合。 發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組,收端收到碼組后,檢查差錯情況,如果差錯在碼的糾錯能力以內(nèi),則自動進(jìn)行糾正。 如果信道干擾很嚴(yán)重,錯誤很多,超過了碼的糾錯能力,但能檢測出來,則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。 信息反饋(IRQ)： 收端把收到的數(shù)據(jù),原封不動地通過反饋信

7、道送回到發(fā)端,發(fā)端比較發(fā)的數(shù)據(jù)與反饋來的數(shù)據(jù),從而發(fā)現(xiàn)錯誤,并且把錯誤的消息再次傳送,直到發(fā)端沒有發(fā)現(xiàn)錯誤為止。,16,檢錯與糾錯原理,0:晴,1:雨 若10,01。收端無法發(fā)現(xiàn)錯誤,00晴,10,01,11,00,11雨,能發(fā)現(xiàn) 一個錯誤,禁用碼組,插入1位監(jiān)督碼后具有檢出1位錯碼的能力,但不能予以糾正。,17,檢錯與糾錯原理,000晴,010,001,111,000,111雨,晴,在只有1位錯碼的情況下,可以判決哪位是錯碼并予以糾正,可以檢出2位或2位以下的錯碼。,100,011,101,110,雨,18,檢錯與糾錯原理,最大似然譯碼： 將接收到的碼字譯碼為與它差別最小的許用碼字,并且認(rèn)為

8、這個許用碼字就是它所對應(yīng)的發(fā)送碼字,從而在碼字的糾錯能力內(nèi)實(shí)現(xiàn)自動糾錯。 糾錯編碼之所以具有檢錯、糾錯能力,是因?yàn)樵谛畔⒋a元之外加入了監(jiān)督碼。監(jiān)督碼不載信息,只是用來監(jiān)督信息碼在傳輸中有無差錯。 糾錯編碼所提高的可靠性,是以犧牲信道利用率為代價換取的。 監(jiān)督碼引入越多,檢錯、糾錯能力越強(qiáng),但信道的傳輸效率下降也越多。,19,信道編碼 在被傳輸信息中附加一些冗余碼,即監(jiān)督碼元,利用附加碼元與信息碼元間的約束關(guān)系加以校驗(yàn),以檢測和糾正錯誤。 信源編碼減少了冗余度 冗余度是隨機(jī)的、無規(guī)律的 信道編碼增加了冗余度 冗余度是特定的、有規(guī)律的,故可利用其在接收端進(jìn)行檢錯和糾錯。,信道編碼,20,傳輸冗余比

9、特必然要動用冗余的資源。 時間： 比如一個比特重復(fù)發(fā)幾次,或一段消息重復(fù)發(fā)幾遍,或根據(jù)收端的反饋重發(fā)受損信息組。 頻帶： 插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一是增大符號傳遞速率(波特率),結(jié)果就占用了更大的帶寬。 功率： 采用多進(jìn)制符號,用8進(jìn)制ASK符號代替4進(jìn)制ASK符號來傳送2比特信息,可騰出位置另傳1冗余比特。 8進(jìn)制ASK符號的平均功率肯定比4進(jìn)制時要大,這就是動用冗余的功率資源來傳輸冗余比特。 設(shè)備復(fù)雜度： 加大碼長,采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實(shí)施糾錯編碼的有效方法,代價是算法復(fù)雜度的提高,需動用設(shè)備資源。,21,信道編碼的基本思想,信道

10、編碼 按一定規(guī)則給數(shù)字序列m增加一些多余的碼元,使不具有規(guī)律性的信息序列 m 變換為具有某種規(guī)律性的數(shù)碼序列 C； 碼序列中的信息序列碼元與多余碼元之間是相關(guān)的； 信道譯碼器利用這種預(yù)知的編碼規(guī)則譯碼。檢驗(yàn)接收到的數(shù)字序列 R 是否符合既定的 規(guī)則,從而發(fā)現(xiàn) R 中是否有錯,或者糾正其中的差錯； 根據(jù)相關(guān)性來檢測/發(fā)現(xiàn)和糾正傳輸過程中產(chǎn)生的差錯就是信道編碼的基本思想。,22,碼距與檢錯、糾錯能力,糾錯編碼的檢錯糾錯能力,要取決于碼組的碼距 碼距越大,檢錯、糾錯能力越強(qiáng)。 漢明距離： 二個碼組對應(yīng)碼位碼元不同的個數(shù)。 最小碼距dmin： 一個碼組的集合中任意二個碼組間的最小漢明距離。 碼重W：

11、碼組中非0的數(shù)目。,23,碼距與檢錯、糾錯能力,定理：若糾錯碼的最小距離為dmin， 可以檢測出任意小于等于l = dmin1個差錯 可以糾正任意小于等于 個差錯,可以檢測出任意小于等于l同時糾正小于等于t個差錯， 其中l(wèi)、t滿足： l + t dmin1 t l,24,檢錯、糾錯能力,為檢查出 個錯誤，要求最小碼距為 為糾正 個錯誤，要求最小碼距為 為糾正 個錯誤，同時檢查出 個錯誤，要求最小碼距為,25,糾錯檢錯示意圖,26,編碼效率,編碼效率： 一個組中信息所占的比重,k：信息碼元的數(shù)目 n：編碼組碼元的總數(shù)目 n = k+ r r：監(jiān)督碼元的數(shù)目,信道編碼,第6章,28,6.1 糾錯編

12、譯碼的基本原理與分析方法 6.2 線性分組碼 6.3 卷積碼,內(nèi)容,29,信源編碼 提高數(shù)字信號有效性 將信源的模擬信號轉(zhuǎn)變?yōu)閿?shù)字信號 降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮) 信道編碼 提高數(shù)字通信可靠性 數(shù)字信號在信道的傳輸過程中,由于實(shí)際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會產(chǎn)生誤碼。,編碼,30,6.1 糾錯編譯碼的基本原理與分析方法,31,6.1.1 差錯和差錯控制系統(tǒng)分類,差錯率是衡量傳輸質(zhì)量的重要指標(biāo)之一,它有幾種不同的定義。 碼元差錯率/符號差錯率 指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯的碼元數(shù)所占的比例(平均值),簡稱誤碼率。 是指信號差錯概率 比特差錯率 /比特誤碼率： 在

13、傳輸?shù)谋忍乜倲?shù)中發(fā)生差錯的比特數(shù)所占比例 是指信息差錯概率 對二進(jìn)制傳輸系統(tǒng),符號差錯等效于比特差錯;對多進(jìn)制系統(tǒng),一個符號差錯對應(yīng)多少比特差錯卻難以確定,32,差錯率,根據(jù)不同的應(yīng)用場合對差錯率有不同的要求: 在電報傳送時,允許的比特差錯率約為: 104105； 計算機(jī)數(shù)據(jù)傳輸,一般要求比特差錯率小于: 108109； 在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯率,33,差錯圖樣,為定量地描述信號的差錯,定義差錯圖樣E E=CR (模M ) 最常用的二進(jìn)制碼可當(dāng)作特例來研究,其差錯圖樣等于收碼與發(fā)碼的模2加,即 E = CR 或 C = RE 設(shè)發(fā)送的碼字C 1 1 1

14、 1 1 1 1 1 1 1 接收的碼字R 1 0 0 1 0 0 1 1 1 1 差錯的圖樣E 0 1 1 0 1 1 0 0 0 0 差錯圖樣中的“1”既是符號差錯也是比特差錯,差錯的個數(shù)叫漢明距離。,0:傳輸中無錯 1:傳輸中有錯,34,差錯圖樣,隨機(jī)差錯： 差錯是相互獨(dú)立的,不相關(guān) 存在這種差錯的信道是無記憶信道或隨機(jī)信道 突發(fā)差錯： 指成串出現(xiàn)的錯誤,錯誤與錯誤間有相關(guān)性,一個差錯往往要影響到后面一串字 E: 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0,突發(fā)長度= 4,突發(fā)長度= 6,35,糾錯碼分類,從功能角度講,差錯碼分為檢

15、錯碼和糾錯碼 檢錯碼：用于發(fā)現(xiàn)差錯 糾錯碼：能自動糾正差錯 糾錯碼與檢錯碼在理論上沒有本質(zhì)區(qū)別,只是應(yīng)用場合不同,而側(cè)重的性能參數(shù)也不同。,36,糾錯碼分類,按照對信息序列的處理方法,有分組碼和卷積碼 分組碼： 將k個信息碼元分成一組,由這k個碼元按照一定規(guī)則產(chǎn)生r個監(jiān)督碼元,組成長度n = k + r的碼字,卷積碼： 先將信息序列分組,不同的是編解碼運(yùn)算不僅與本組信息有關(guān),而且還與前面若干組有關(guān)。,k,k,010 101 010 001 110,010 xxxx 101xxxx 010 xxxx,r,n,r,37,糾錯碼分類,按照碼元與原始信息位的關(guān)系,分為 線性碼：所有碼元均是原始信息元的

16、線性組合,編碼器不帶反饋回路。 非線性碼：碼元并不都是信息元的線性組合,可能還與前面已編的碼元有關(guān),編碼器可能含反饋回路。 由于非線性碼的分析比較困難,早期實(shí)用的糾錯碼多為線性碼,但當(dāng)今發(fā)現(xiàn)的很多好碼恰恰是非線性碼。,38,糾錯碼分類,按照適用的差錯類型,分成: 糾隨機(jī)差錯碼:用于隨機(jī)差錯信道,其糾錯能力用碼組內(nèi)允許的獨(dú)立差錯的個數(shù)來衡量。 糾突發(fā)差錯碼:針對突發(fā)差錯而設(shè)計,其糾錯能力主要用可糾突發(fā)差錯的最大長度來衡量,39,差錯控制系統(tǒng)分類,前向糾錯(FEC)： 發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。 接收端信道譯碼器對接收碼字進(jìn)行譯碼,若傳輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之

17、內(nèi)時,譯碼器對差錯進(jìn)行定位并加以糾正。,40,差錯控制系統(tǒng)分類,自動請求重發(fā)(ARQ)： 發(fā)端發(fā)送檢錯碼， 收端譯碼器判斷當(dāng)前碼字傳輸是否出錯； 當(dāng)有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字(全部或部分)。,41,差錯控制系統(tǒng)分類,混合糾錯(HEC)： 是FEC與ARQ方式的結(jié)合。 發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組,收端收到碼組后,檢查差錯情況,如果差錯在碼的糾錯能力以內(nèi),則自動進(jìn)行糾正。 如果信道干擾很嚴(yán)重,錯誤很多,超過了碼的糾錯能力,但能檢測出來,則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。 信息反饋(IRQ)： 收端把收到的數(shù)據(jù),原封不動地通過反饋信道送回到發(fā)端,發(fā)端比較

18、發(fā)的數(shù)據(jù)與反饋來的數(shù)據(jù),從而發(fā)現(xiàn)錯誤,并且把錯誤的消息再次傳送,直到發(fā)端沒有發(fā)現(xiàn)錯誤為止。,42,檢錯與糾錯原理,0:晴,1:雨 若10,01。收端無法發(fā)現(xiàn)錯誤,00晴,10,01,11,00,11雨,能發(fā)現(xiàn) 一個錯誤,禁用碼組,插入1位監(jiān)督碼后具有檢出1位錯碼的能力,但不能予以糾正。,43,檢錯與糾錯原理,000晴,010,001,111,000,111雨,晴,在只有1位錯碼的情況下,可以判決哪位是錯碼并予以糾正,可以檢出2位或2位以下的錯碼。,100,011,101,110,雨,44,檢錯與糾錯原理,最大似然譯碼： 將接收到的碼字譯碼為與它差別最小的許用碼字,并且認(rèn)為這個許用碼字就是它所對

19、應(yīng)的發(fā)送碼字,從而在碼字的糾錯能力內(nèi)實(shí)現(xiàn)自動糾錯。 糾錯編碼之所以具有檢錯、糾錯能力,是因?yàn)樵谛畔⒋a元之外加入了監(jiān)督碼。監(jiān)督碼不載信息,只是用來監(jiān)督信息碼在傳輸中有無差錯。 糾錯編碼所提高的可靠性,是以犧牲信道利用率為代價換取的。 監(jiān)督碼引入越多,檢錯、糾錯能力越強(qiáng),但信道的傳輸效率下降也越多。,45,信道編碼 在被傳輸信息中附加一些冗余碼,即監(jiān)督碼元,利用附加碼元與信息碼元間的約束關(guān)系加以校驗(yàn),以檢測和糾正錯誤。 信源編碼減少了冗余度 冗余度是隨機(jī)的、無規(guī)律的 信道編碼增加了冗余度 冗余度是特定的、有規(guī)律的,故可利用其在接收端進(jìn)行檢錯和糾錯。,信道編碼,46,傳輸冗余比特必然要動用冗余的資源

20、。 時間： 比如一個比特重復(fù)發(fā)幾次,或一段消息重復(fù)發(fā)幾遍,或根據(jù)收端的反饋重發(fā)受損信息組。 頻帶： 插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一是增大符號傳遞速率(波特率),結(jié)果就占用了更大的帶寬。 功率： 采用多進(jìn)制符號,用8進(jìn)制ASK符號代替4進(jìn)制ASK符號來傳送2比特信息,可騰出位置另傳1冗余比特。 8進(jìn)制ASK符號的平均功率肯定比4進(jìn)制時要大,這就是動用冗余的功率資源來傳輸冗余比特。 設(shè)備復(fù)雜度： 加大碼長,采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實(shí)施糾錯編碼的有效方法,代價是算法復(fù)雜度的提高,需動用設(shè)備資源。,47,信道編碼的基本思想,信道編碼 按一定規(guī)則給數(shù)字

21、序列m增加一些多余的碼元,使不具有規(guī)律性的信息序列 m 變換為具有某種規(guī)律性的數(shù)碼序列 C； 碼序列中的信息序列碼元與多余碼元之間是相關(guān)的； 信道譯碼器利用這種預(yù)知的編碼規(guī)則譯碼。檢驗(yàn)接收到的數(shù)字序列 R 是否符合既定的 規(guī)則,從而發(fā)現(xiàn) R 中是否有錯,或者糾正其中的差錯； 根據(jù)相關(guān)性來檢測/發(fā)現(xiàn)和糾正傳輸過程中產(chǎn)生的差錯就是信道編碼的基本思想。,48,碼距與檢錯、糾錯能力,糾錯編碼的檢錯糾錯能力,要取決于碼組的碼距 碼距越大,檢錯、糾錯能力越強(qiáng)。 漢明距離： 二個碼組對應(yīng)碼位碼元不同的個數(shù)。 最小碼距dmin： 一個碼組的集合中任意二個碼組間的最小漢明距離。 碼重W： 碼組中非0的數(shù)目。,4

22、9,碼距與檢錯、糾錯能力,定理：若糾錯碼的最小距離為dmin， 可以檢測出任意小于等于l = dmin1個差錯 可以糾正任意小于等于 個差錯,可以檢測出任意小于等于l同時糾正小于等于t個差錯， 其中l(wèi)、t滿足： l + t dmin1 t l,50,編碼效率,編碼效率： 一個組中信息所占的比重,k：信息碼元的數(shù)目 n：編碼組碼元的總數(shù)目 n = k+ r r：監(jiān)督碼元的數(shù)目,51,檢錯碼,奇偶校驗(yàn)碼(n，n-1)(k+1，k),偶校驗(yàn)碼字,52,6.1 概述,誤碼分類 隨機(jī)信道噪聲引入的隨機(jī)誤碼，均勻分布 突發(fā)信道由干擾、快衰落引起的突發(fā)誤碼 如何減少誤碼？ 從信源編碼看，誤碼引起的性能惡化盡

23、可能小，容錯技術(shù) 從傳輸看，可采用抗干擾能力強(qiáng)的調(diào)制方式，信道特性不理想可采用均衡。特別需要差錯控制技術(shù)。數(shù)字通信中，要求誤碼率108以下，必須采用差錯控制。,53,二元碼產(chǎn)生誤碼的情況,54,6.1.1 差錯控制分類,需要雙向信道，和前向信道有相同的通信容。 引入較大的停頓（不實(shí)時）。 可以糾正任何錯誤。,1. 反饋檢驗(yàn)法,55,2. 檢錯重發(fā)法（ARQ）,自動請求重發(fā) 也需要反向信道，但容量可以降低，也會引入停頓,56,3. 前向糾錯（FEC）,不需要雙向信道 不會引入停頓 靠糾錯編碼,57,4. 混合糾錯（HEC）,需要反饋信道 可能會引入停頓 靠糾錯編碼和檢錯碼,58,6.1.2 差錯

24、控制編碼的基本原理,如用三位二進(jìn)制編碼來代表八個字母 000 A100E 001 B101F 010C110G 011D111H 不管哪一位發(fā)生錯誤，都會使傳輸字母錯誤 如用三位字母傳四個字母 000 A011B101 C110D 發(fā)生一位錯誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道出錯，但是不能糾錯。,59,差錯控制編碼,如用三位字母傳二個字母 000 A 111B 檢二個錯誤，糾正一個錯誤。 結(jié)論 具有檢錯或糾錯的碼組，其所用的比特數(shù)必須大于信息碼組原來的比特數(shù) 引入余度。,60,碼重、碼距,碼重(weight) 一個碼組中“1”的數(shù)目 碼距(distance) 兩個碼組之間對應(yīng)位置上1、

25、0不同的位數(shù)，又叫漢明(Hamming)距。 10 1 1 0 碼重：3 01 1 0 0 2 距離：3,61,檢錯、糾錯能力,為檢查出 個錯誤，要求最小碼距為 為糾正 個錯誤，要求最小碼距為 為糾正 個錯誤，同時檢查出 個錯誤，要求最小碼距為,62,63,6.1.3. 差錯控制編碼分類,按功能分 檢錯碼 糾錯碼 糾刪碼（發(fā)現(xiàn)不可糾正的錯誤時，可發(fā)出指示或刪除） 按信息碼元和監(jiān)督碼元之間的校驗(yàn)關(guān)系分 線性碼 非線性碼 按信息碼元和監(jiān)督碼元之間的約束方式分 分組碼 卷積碼,64,香農(nóng)理 糾錯碼的理論基礎(chǔ),香農(nóng)定理 存在噪聲干擾的信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入到

26、編碼器的二進(jìn)制碼元速率），則一定存在一種編碼方式，使編碼的錯誤概率隨著碼長n的增加將按指數(shù)下降到任一的值，即 P120 結(jié)論 如碼長及發(fā)送信息速率一定，可以通過增大信道容量，使P減小。 如在信道容量及發(fā)送信息速率一定，可以通過增加碼長，使錯誤概率下降。,65,分組碼,表示： (n,k) n : 幀長k/n : 編碼效率 特點(diǎn) 監(jiān)督碼只用來監(jiān)督本幀中的信息位 分類 線性碼 信息碼與監(jiān)督碼之間為線性關(guān)系 非線性碼 不存在線性關(guān)系,66,奇偶監(jiān)督碼,偶監(jiān)督 奇監(jiān)督 如果以上關(guān)系被破壞，則出現(xiàn)錯誤，因此能檢查出奇數(shù)個錯誤，但不能檢測偶數(shù)個錯誤。 最小碼距為 dmin=2 這種碼檢錯能力不高，采用什么方

27、法提高呢？,67,水平奇偶監(jiān)督碼和水平垂直監(jiān)督碼,又叫 二維奇偶監(jiān)督碼 水平奇偶監(jiān)督碼 檢碼字按行排成方陣，每行采用奇偶監(jiān)督碼，發(fā)送時按列的順序傳送，接收時仍將碼字排列成發(fā)送時方陣形式，然后按行進(jìn)行奇偶校驗(yàn)。 在不增加冗余度時，不僅發(fā)現(xiàn)某一行上奇數(shù)個錯誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯誤。 水平垂直奇偶監(jiān)督碼 不僅對行進(jìn)行奇偶校驗(yàn)，而且也對列進(jìn)行奇偶校驗(yàn)。,68,分組碼 (1),分組碼的監(jiān)督方程 矩陣形式,6.2 線性分組碼,69,分組碼 (2),監(jiān)督矩陣 H矩陣稱為典型形式，各行一定是線性無關(guān)的。而一個非典型形式的經(jīng)過運(yùn)算可以化成典型形式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關(guān)系。,

28、70,分組碼 (3),生成矩陣 ，通過生成矩陣可以得到生成碼組。 如果輸入碼組為 0011,71,分組碼 (4),由這種方式得到的生成矩陣稱為典型生成矩陣，由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信息碼字保持不變，監(jiān)督位附加其后，每行一定是線性無關(guān)的，每行都是一個生成碼組。,72,漢明碼,漢明碼監(jiān)督位為 位，因此它可以組成 種可能情況，其中一個為無錯。因此可以監(jiān)督碼位共 要糾正一個錯誤，必須滿足 最小碼距 如果 r 位監(jiān)督位所組成的校正子碼組與誤碼圖樣一一對應(yīng)，這種碼組稱為完備碼（取等號時）,73,擴(kuò)展?jié)h明碼,如果在漢明碼基礎(chǔ)上，再加上一位對所有碼字進(jìn)行校驗(yàn)的監(jiān)督位 監(jiān)督碼字由 r 位增加到 r+

29、1 位 信息位不變 碼長 碼結(jié)構(gòu) 糾 1 位錯，檢測 2 位錯 如 （8，4），（16，11）,74,擴(kuò)展?jié)h明碼矩陣,如 (7,4) (8,4),75,縮短漢明碼,(n,k) (n-s, k-s) 如 (15,11) (12,8) 監(jiān)督矩陣 Hs 是將原 H 的前 3 列 去掉 縮短漢明碼的最小碼距至少和原來碼的碼距相同，因?yàn)楸O(jiān)督位沒有變。,76,能糾 t 個錯誤的(n,k)應(yīng)滿足 取等號時為完備碼 不同結(jié)構(gòu)的線性碼其糾錯能力不同，能力和dmin 有關(guān)，dmin 越大越好。,77,最小碼距界限,上界： 漢明界， 普洛特金界 下界： 吉爾伯特界 問題： 給定碼長與編碼效率，尋找 dmin 例：

30、dmin=5, 碼長=63 的分組碼設(shè)計 從漢明界得， 因此信息位最多可以取,78,最小碼距界限,通過吉爾伯特界求下界 線性碼 k 越接近 52， 效率越高。,79,6.3 循環(huán)碼 (Cyclic code),1957 年發(fā)現(xiàn) 特點(diǎn) 線性分組碼 循環(huán)性任一許用碼字經(jīng)過循環(huán)移位后，得到的碼組仍為一個許用碼組 如 是循環(huán)碼的一許用碼組 則 也是一許用碼組,80,碼多項(xiàng)式表示,碼組 碼多項(xiàng)式 碼組 碼多項(xiàng)式 左移一位 左移 位,81,循環(huán)碼性質(zhì),為許用碼組，則 也是許用碼組 性質(zhì) 若 是長度為n的循環(huán)碼組，則 在按模 進(jìn)行運(yùn)算后，也是一個循環(huán)碼組，也就是 用 多項(xiàng)式除后所得之余式，即為所求的碼組。,

31、82,循環(huán)碼例子,碼組 左移 3 位 去除 得余式 如 左移 3 位后，得 是許用碼組,83,循環(huán)碼生成多項(xiàng)式g(D),g(D) 是 D的 (n-k) 次即r 次多項(xiàng)式 信息多項(xiàng)式為M(D),k 位，(k-1)次多項(xiàng)式,84,Theo.一個(n,k) 的二進(jìn)制循環(huán)碼可以看成是唯一由它的生成多項(xiàng)式產(chǎn)生，即 如(7,3)循環(huán)碼，n=7, k=3, r=4 如果信息位為 010， M(D)=D 生成碼為 0111010,循環(huán)碼生成多項(xiàng)式g(D),85,生成矩陣 G(D),由于 k 位信息位共有 個碼組，都可用此法產(chǎn)生，如果現(xiàn)有信息碼 生成 k 個碼字，且這 k 個碼字都線性無關(guān)，用這 k 個碼字作為

32、一個矩陣G 的 k行 構(gòu)成生成矩陣 G(D),86,循環(huán)碼,(7,3) 循環(huán)碼,87,生成矩陣和監(jiān)督矩陣,這樣構(gòu)成的循環(huán)碼并非是系統(tǒng)碼 系統(tǒng)碼的生成矩陣典型形式 非系統(tǒng)碼 系統(tǒng)碼 生成矩陣 監(jiān)督矩陣,88,非系統(tǒng)碼 系統(tǒng)碼,系統(tǒng)碼的碼多項(xiàng)式為 例如，(7,4)碼，1011,89,非系統(tǒng)碼 系統(tǒng)碼,90,尋找生成多項(xiàng)式,Theo. 循環(huán)碼的生成多項(xiàng)式必須能除盡 h(D)是監(jiān)督多項(xiàng)式 例：要構(gòu)成(7,3)循環(huán)碼，求g(D). 解：g(D)應(yīng)為4階 生成(7,6)循環(huán)碼 生成(7,1)循環(huán)碼,91,循環(huán)碼的編碼器,原理：按系統(tǒng)碼的生成方式 以(7,4)碼為例,92,循環(huán)碼的譯碼器,譯碼比編碼復(fù)雜得多

33、 譯碼三步 伴隨式S的計算 由S得到錯誤圖樣 糾正,93,伴隨式的計算,發(fā)送碼組 接收碼組 誤差碼組 校正子只與 E 有關(guān)，根本是計算校正子,94,6.4 BCH碼,即約多項(xiàng)式 一個 m 次多項(xiàng)式不能被二元域上任何二次數(shù)小于的，但大于0的多項(xiàng)式除盡，如 是即約的。 本原多項(xiàng)式 若m次多項(xiàng)式P(x)除盡的 的最小正整數(shù) n 滿足 ，就稱為本原的。 如 能除盡 ，但除不盡 的。 如 ： 是即約的，但不是本原的，因它能除盡 。,95,6.4.1 本原循環(huán)碼,由本原多項(xiàng)式構(gòu)成的碼稱為本原碼。 特點(diǎn) 碼長為 它的生成多項(xiàng)式是由若干m階或以m的因子為最高階的多項(xiàng)式相乘而構(gòu)成。 要判定(n,k) 的循環(huán)碼是否存在，只需要判斷 n-k 階的生成多項(xiàng)式是否能由 Dn+1的因式構(gòu)成。,96,循環(huán)碼例子,生成多項(xiàng)式的階次為 r, 該生成多項(xiàng)式是否是 的因此。 一個m階即約多項(xiàng)式一定能除盡 如，m5，共有6個5階即約多項(xiàng)式。 再加上 因子， 是以上7個多項(xiàng)式的乘積。,97,6.4.2 BCH 碼的生成多項(xiàng)式,如果循環(huán)碼形式的形式為 為糾錯個數(shù) ， 為最小多項(xiàng)式， 為最小公倍數(shù) 最小碼距 碼長為 的BCH碼稱為 本BCH碼（俠義） 碼長為 則稱為非本原BCH碼,98,BCH 碼,由于g(D)有t個因式，且每個因式的最高次為m，因此監(jiān)督碼元最多有mt位。 對于糾t 個錯誤的本原BCH碼，其生成多項(xiàng)式 糾單個