信道編碼(糾錯碼)

1、信道編碼,第6章,2,6.1 糾錯編譯碼的基本原理與分析方法6.2 線性分組碼6.3 卷積碼,內(nèi)容,3,信源編碼提高數(shù)字信號有效性將信源的模擬信號轉(zhuǎn)變?yōu)閿?shù)字信號降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮)信道編碼提高數(shù)字通信可靠性 數(shù)字信號在信道的傳輸過程中,由于實際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會產(chǎn)生誤碼。,編碼,,4,6.1 糾錯編譯碼的基本原理與分析方法,5,6.1.1 差錯和差錯控制系統(tǒng)分

2、類,差錯率是衡量傳輸質(zhì)量的重要指標之一,它有幾種不同的定義。碼元差錯率/符號差錯率指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯的碼元數(shù)所占的比例(平均值),簡稱誤碼率。是指信號差錯概率 比特差錯率 /比特誤碼率：在傳輸?shù)谋忍乜倲?shù)中發(fā)生差錯的比特數(shù)所占比例是指信息差錯概率 對二進制傳輸系統(tǒng),符號差錯等效于比特差錯;對多進制系統(tǒng),一個符號差錯對應多少比特差錯卻難以確定,6,差錯率,根據(jù)不同的應用場合對差錯率有不同的要求:在電報傳送時,允許的

3、比特差錯率約為: 10－4～10－5；計算機數(shù)據(jù)傳輸,一般要求比特差錯率小于: 10－8～10－9；在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯率,7,差錯圖樣,為定量地描述信號的差錯,定義差錯圖樣E E=C－R (模M )最常用的二進制碼可當作特例來研究,其差錯圖樣等于收碼與發(fā)碼的模2加,即

4、 E = C⊕R 或 C = R⊕E設發(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,差錯圖樣,隨機差錯：差錯是相互獨立的,不相關存在這種差錯

5、的信道是無記憶信道或隨機信道突發(fā)差錯：指成串出現(xià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,糾錯碼分類,從功能角度講,差錯碼分為檢錯碼和糾錯碼檢錯碼：用于發(fā)現(xiàn)差錯糾錯碼：能自動糾正差錯糾錯碼與檢錯碼在理論上沒有本質(zhì)區(qū)別,只是應用場合不同,而側(cè)重的性能參數(shù)也不同。,1

6、0,糾錯碼分類,按照對信息序列的處理方法,有分組碼和卷積碼分組碼：將k個信息碼元分成一組,由這k個碼元按照一定規(guī)則產(chǎn)生r個監(jiān)督碼元,組成長度n = k + r的碼字,卷積碼：先將信息序列分組,不同的是編解碼運算不僅與本組信息有關,而且還與前面若干組有關。,,k,,k,,,,010 101 010 001 110,010xxxx 101xxxx 010 xxxx,,r,,n,,,r,11,糾錯碼分類,按照碼元與原始信息位的關系,分為

7、線性碼：所有碼元均是原始信息元的線性組合,編碼器不帶反饋回路。非線性碼：碼元并不都是信息元的線性組合,可能還與前面已編的碼元有關,編碼器可能含反饋回路。由于非線性碼的分析比較困難,早期實用的糾錯碼多為線性碼,但當今發(fā)現(xiàn)的很多好碼恰恰是非線性碼。,12,糾錯碼分類,按照適用的差錯類型,分成:糾隨機差錯碼:用于隨機差錯信道,其糾錯能力用碼組內(nèi)允許的獨立差錯的個數(shù)來衡量。糾突發(fā)差錯碼:針對突發(fā)差錯而設計,其糾錯能力主要用可糾突發(fā)差錯

8、的最大長度來衡量,13,差錯控制系統(tǒng)分類,前向糾錯(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。接收端信道譯碼器對接收碼字進行譯碼,若傳輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)時,譯碼器對差錯進行定位并加以糾正。,14,差錯控制系統(tǒng)分類,自動請求重發(fā)(ARQ)：發(fā)端發(fā)送檢錯碼，收端譯碼器判斷當前碼字傳輸是否出錯；當有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字(全部或部分)。,15,差錯控制系統(tǒng)分類

9、,混合糾錯(HEC)：是FEC與ARQ方式的結(jié)合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組,收端收到碼組后,檢查差錯情況,如果差錯在碼的糾錯能力以內(nèi),則自動進行糾正。如果信道干擾很嚴重,錯誤很多,超過了碼的糾錯能力,但能檢測出來,則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。信息反饋(IRQ)：收端把收到的數(shù)據(jù),原封不動地通過反饋信道送回到發(fā)端,發(fā)端比較發(fā)的數(shù)據(jù)與反饋來的數(shù)據(jù),從而發(fā)現(xiàn)錯誤,并且把錯誤的消息再次傳送,直到發(fā)端沒有發(fā)現(xiàn)錯誤為

10、止。,16,檢錯與糾錯原理,0:晴,1:雨若1→0,0→1。收端無法發(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,,

11、雨,18,檢錯與糾錯原理,最大似然譯碼：將接收到的碼字譯碼為與它差別最小的許用碼字,并且認為這個許用碼字就是它所對應的發(fā)送碼字,從而在碼字的糾錯能力內(nèi)實現(xiàn)自動糾錯。糾錯編碼之所以具有檢錯、糾錯能力,是因為在信息碼元之外加入了監(jiān)督碼。監(jiān)督碼不載信息,只是用來監(jiān)督信息碼在傳輸中有無差錯。糾錯編碼所提高的可靠性,是以犧牲信道利用率為代價換取的。監(jiān)督碼引入越多,檢錯、糾錯能力越強,但信道的傳輸效率下降也越多。,19,信道編碼在被傳輸信

12、息中附加一些冗余碼,即監(jiān)督碼元,利用附加碼元與信息碼元間的約束關系加以校驗,以檢測和糾正錯誤。信源編碼減少了冗余度冗余度是隨機的、無規(guī)律的信道編碼增加了冗余度冗余度是特定的、有規(guī)律的,故可利用其在接收端進行檢錯和糾錯。,信道編碼,20,傳輸冗余比特必然要動用冗余的資源。時間：比如一個比特重復發(fā)幾次,或一段消息重復發(fā)幾遍,或根據(jù)收端的反饋重發(fā)受損信息組。頻帶：插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一

13、是增大符號傳遞速率(波特率),結(jié)果就占用了更大的帶寬。功率：采用多進制符號,用8進制ASK符號代替4進制ASK符號來傳送2比特信息,可騰出位置另傳1冗余比特。8進制ASK符號的平均功率肯定比4進制時要大,這就是動用冗余的功率資源來傳輸冗余比特。設備復雜度：加大碼長,采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實施糾錯編碼的有效方法,代價是算法復雜度的提高,需動用設備資源。,21,信道編碼的基本思想,信道編碼按一定規(guī)則給數(shù)字序列

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

15、力越強。漢明距離：二個碼組對應碼位碼元不同的個數(shù)。最小碼距dmin：一個碼組的集合中任意二個碼組間的最小漢明距離。碼重W：碼組中非0的數(shù)目。,23,碼距與檢錯、糾錯能力,定理：若糾錯碼的最小距離為dmin，可以檢測出任意小于等于l = dmin－1個差錯⑵可以糾正任意小于等于 個差錯,⑶可以檢測出任意小于等于l同時糾正小于等于t個差錯，其中l(wèi)、t滿足： l + t ≤ dm

16、in－1 t ＜l,24,檢錯、糾錯能力,為檢查出 個錯誤，要求最小碼距為為糾正 個錯誤，要求最小碼距為為糾正 個錯誤，同時檢查出 個錯誤，要求最小碼距為,25,,糾錯檢錯示意圖,26,編碼效率,編碼效率：一個組中信息所占的比重,k：信息碼元的數(shù)目n：編碼組碼元的總數(shù)目 n = k+ rr：監(jiān)督碼元的數(shù)目,信道編碼,第6章,28

17、,6.1 糾錯編譯碼的基本原理與分析方法6.2 線性分組碼6.3 卷積碼,內(nèi)容,29,信源編碼提高數(shù)字信號有效性將信源的模擬信號轉(zhuǎn)變?yōu)閿?shù)字信號降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮)信道編碼提高數(shù)字通信可靠性 數(shù)字信號在信道的傳輸過程中,由于實際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會產(chǎn)生誤碼。,編碼,,30,6.1 糾錯編譯碼的基本原理與分析方法,31,6.1.1 差錯和差錯控制系統(tǒng)分類,差錯率是衡

18、量傳輸質(zhì)量的重要指標之一,它有幾種不同的定義。碼元差錯率/符號差錯率指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯的碼元數(shù)所占的比例(平均值),簡稱誤碼率。是指信號差錯概率 比特差錯率 /比特誤碼率：在傳輸?shù)谋忍乜倲?shù)中發(fā)生差錯的比特數(shù)所占比例是指信息差錯概率 對二進制傳輸系統(tǒng),符號差錯等效于比特差錯;對多進制系統(tǒng),一個符號差錯對應多少比特差錯卻難以確定,32,差錯率,根據(jù)不同的應用場合對差錯率有不同的要求:在電報傳送時,允許的比特差錯率約

19、為: 10－4～10－5；計算機數(shù)據(jù)傳輸,一般要求比特差錯率小于: 10－8～10－9；在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯率,33,差錯圖樣,為定量地描述信號的差錯,定義差錯圖樣E E=C－R (模M )最常用的二進制碼可當作特例來研究,其差錯圖樣等于收碼與發(fā)碼的模2加,即

20、E = C⊕R 或 C = R⊕E設發(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:傳輸中有錯,34,差錯圖樣,隨機差錯：差錯是相互獨立的,不相關存在這種差錯的信道是

21、無記憶信道或隨機信道突發(fā)差錯：指成串出現(xià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,糾錯碼分類,從功能角度講,差錯碼分為檢錯碼和糾錯碼檢錯碼：用于發(fā)現(xiàn)差錯糾錯碼：能自動糾正差錯糾錯碼與檢錯碼在理論上沒有本質(zhì)區(qū)別,只是應用場合不同,而側(cè)重的性能參數(shù)也不同。,36,糾

22、錯碼分類,按照對信息序列的處理方法,有分組碼和卷積碼分組碼：將k個信息碼元分成一組,由這k個碼元按照一定規(guī)則產(chǎn)生r個監(jiān)督碼元,組成長度n = k + r的碼字,卷積碼：先將信息序列分組,不同的是編解碼運算不僅與本組信息有關,而且還與前面若干組有關。,,k,,k,,,,010 101 010 001 110,010xxxx 101xxxx 010 xxxx,,r,,n,,,r,37,糾錯碼分類,按照碼元與原始信息位的關系,分為線性

23、碼：所有碼元均是原始信息元的線性組合,編碼器不帶反饋回路。非線性碼：碼元并不都是信息元的線性組合,可能還與前面已編的碼元有關,編碼器可能含反饋回路。由于非線性碼的分析比較困難,早期實用的糾錯碼多為線性碼,但當今發(fā)現(xiàn)的很多好碼恰恰是非線性碼。,38,糾錯碼分類,按照適用的差錯類型,分成:糾隨機差錯碼:用于隨機差錯信道,其糾錯能力用碼組內(nèi)允許的獨立差錯的個數(shù)來衡量。糾突發(fā)差錯碼:針對突發(fā)差錯而設計,其糾錯能力主要用可糾突發(fā)差錯的最大

24、長度來衡量,39,差錯控制系統(tǒng)分類,前向糾錯(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。接收端信道譯碼器對接收碼字進行譯碼,若傳輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)時,譯碼器對差錯進行定位并加以糾正。,40,差錯控制系統(tǒng)分類,自動請求重發(fā)(ARQ)：發(fā)端發(fā)送檢錯碼，收端譯碼器判斷當前碼字傳輸是否出錯；當有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字(全部或部分)。,41,差錯控制系統(tǒng)分類,混合

25、糾錯(HEC)：是FEC與ARQ方式的結(jié)合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組,收端收到碼組后,檢查差錯情況,如果差錯在碼的糾錯能力以內(nèi),則自動進行糾正。如果信道干擾很嚴重,錯誤很多,超過了碼的糾錯能力,但能檢測出來,則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。信息反饋(IRQ)：收端把收到的數(shù)據(jù),原封不動地通過反饋信道送回到發(fā)端,發(fā)端比較發(fā)的數(shù)據(jù)與反饋來的數(shù)據(jù),從而發(fā)現(xiàn)錯誤,并且把錯誤的消息再次傳送,直到發(fā)端沒有發(fā)現(xiàn)錯誤為止。,

26、42,檢錯與糾錯原理,0:晴,1:雨若1→0,0→1。收端無法發(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,,雨,4

27、4,檢錯與糾錯原理,最大似然譯碼：將接收到的碼字譯碼為與它差別最小的許用碼字,并且認為這個許用碼字就是它所對應的發(fā)送碼字,從而在碼字的糾錯能力內(nèi)實現(xiàn)自動糾錯。糾錯編碼之所以具有檢錯、糾錯能力,是因為在信息碼元之外加入了監(jiān)督碼。監(jiān)督碼不載信息,只是用來監(jiān)督信息碼在傳輸中有無差錯。糾錯編碼所提高的可靠性,是以犧牲信道利用率為代價換取的。監(jiān)督碼引入越多,檢錯、糾錯能力越強,但信道的傳輸效率下降也越多。,45,信道編碼在被傳輸信息中附

28、加一些冗余碼,即監(jiān)督碼元,利用附加碼元與信息碼元間的約束關系加以校驗,以檢測和糾正錯誤。信源編碼減少了冗余度冗余度是隨機的、無規(guī)律的信道編碼增加了冗余度冗余度是特定的、有規(guī)律的,故可利用其在接收端進行檢錯和糾錯。,信道編碼,46,傳輸冗余比特必然要動用冗余的資源。時間：比如一個比特重復發(fā)幾次,或一段消息重復發(fā)幾遍,或根據(jù)收端的反饋重發(fā)受損信息組。頻帶：插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一是增大

29、符號傳遞速率(波特率),結(jié)果就占用了更大的帶寬。功率：采用多進制符號,用8進制ASK符號代替4進制ASK符號來傳送2比特信息,可騰出位置另傳1冗余比特。8進制ASK符號的平均功率肯定比4進制時要大,這就是動用冗余的功率資源來傳輸冗余比特。設備復雜度：加大碼長,采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實施糾錯編碼的有效方法,代價是算法復雜度的提高,需動用設備資源。,47,信道編碼的基本思想,信道編碼按一定規(guī)則給數(shù)字序列m增加

30、一些多余的碼元,使不具有規(guī)律性的信息序列 m 變換為具有某種規(guī)律性的數(shù)碼序列 C；碼序列中的信息序列碼元與多余碼元之間是相關的；信道譯碼器利用這種預知的編碼規(guī)則譯碼。檢驗接收到的數(shù)字序列 R 是否符合既定的 規(guī)則,從而發(fā)現(xiàn) R 中是否有錯,或者糾正其中的差錯；根據(jù)相關性來檢測/發(fā)現(xiàn)和糾正傳輸過程中產(chǎn)生的差錯就是信道編碼的基本思想。,48,碼距與檢錯、糾錯能力,糾錯編碼的檢錯糾錯能力,要取決于碼組的碼距碼距越大,檢錯、糾錯能力越強

31、。漢明距離：二個碼組對應碼位碼元不同的個數(shù)。最小碼距dmin：一個碼組的集合中任意二個碼組間的最小漢明距離。碼重W：碼組中非0的數(shù)目。,49,碼距與檢錯、糾錯能力,定理：若糾錯碼的最小距離為dmin，⑴可以檢測出任意小于等于l = dmin－1個差錯⑵可以糾正任意小于等于 個差錯,⑶可以檢測出任意小于等于l同時糾正小于等于t個差錯，其中l(wèi)、t滿足： l + t ≤ dmin

32、－1 t ＜l,50,編碼效率,編碼效率：一個組中信息所占的比重,k：信息碼元的數(shù)目n：編碼組碼元的總數(shù)目 n = k+ rr：監(jiān)督碼元的數(shù)目,51,檢錯碼,奇偶校驗碼(n，n-1)(k+1，k),偶校驗碼字,,52,6.1 概述,誤碼分類隨機信道——噪聲引入的隨機誤碼，均勻分布突發(fā)信道——由干擾、快衰落引起的突發(fā)誤碼如何減少誤碼？從信源編碼看，誤碼引

33、起的性能惡化盡可能小，容錯技術從傳輸看，可采用抗干擾能力強的調(diào)制方式，信道特性不理想可采用均衡。特別需要差錯控制技術。數(shù)字通信中，要求誤碼率10－8以下，必須采用差錯控制。,53,,,二元碼產(chǎn)生誤碼的情況,54,6.1.1 差錯控制分類,需要雙向信道，和前向信道有相同的通信容。引入較大的停頓（不實時）?？梢约m正任何錯誤。,1. 反饋檢驗法,55,2. 檢錯重發(fā)法（ARQ）,自動請求重發(fā)也需要反向信道，但容量可以降低，也會引入停

34、頓,56,3. 前向糾錯（FEC）,不需要雙向信道不會引入停頓靠糾錯編碼,57,4. 混合糾錯（HEC）,需要反饋信道可能會引入停頓靠糾錯編碼和檢錯碼,58,6.1.2 差錯控制編碼的基本原理,如用三位二進制編碼來代表八個字母000 A100E001 B101F010C110G011D111H不管哪一位發(fā)生錯誤，都會使傳輸字母錯誤如用三位字母傳四個字母000

35、A011B101 C110D發(fā)生一位錯誤，準用碼字將變成禁用碼字，接收端就能知道出錯，但是不能糾錯。,59,差錯控制編碼,如用三位字母傳二個字母000 A 111B檢二個錯誤，糾正一個錯誤。結(jié)論具有檢錯或糾錯的碼組，其所用的比特數(shù)必須大于信息碼組原來的比特數(shù)－>引入余度。,60,碼重、碼距,碼重(weight)一個碼組中“1”的數(shù)目碼距(distance)兩個碼組之間對應位

36、置上1、0不同的位數(shù)，又叫漢明(Hamming)距。10 1 1 0 碼重：301 1 0 0 2 距離：3,61,檢錯、糾錯能力,為檢查出 個錯誤，要求最小碼距為為糾正 個錯誤，要求最小碼距為為糾正 個錯誤，同時檢查出 個錯誤，要求最小碼距為,62,,,63,6.1.3. 差錯控制編碼分類,按功能分檢錯碼 糾錯碼

37、糾刪碼（發(fā)現(xiàn)不可糾正的錯誤時，可發(fā)出指示或刪除）按信息碼元和監(jiān)督碼元之間的校驗關系分線性碼非線性碼按信息碼元和監(jiān)督碼元之間的約束方式分分組碼卷積碼,64,香農(nóng)理 糾錯碼的理論基礎,香農(nóng)定理存在噪聲干擾的信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入到編碼器的二進制碼元速率），則一定存在一種編碼方式，使編碼的錯誤概率隨著碼長n的增加將按指數(shù)下降到任一的值，即 P120結(jié)論如碼長及發(fā)送信息速率一定

38、，可以通過增大信道容量，使P減小。如在信道容量及發(fā)送信息速率一定，可以通過增加碼長，使錯誤概率下降。,65,分組碼,表示： (n,k)n : 幀長k/n : 編碼效率特點監(jiān)督碼只用來監(jiān)督本幀中的信息位分類線性碼 － 信息碼與監(jiān)督碼之間為線性關系非線性碼 － 不存在線性關系,66,奇偶監(jiān)督碼,偶監(jiān)督奇監(jiān)督如果以上關系被破壞，則出現(xiàn)錯誤，因此能檢查出奇數(shù)個錯誤，但不能檢測偶數(shù)個錯誤。最小碼距為 dmin=

39、2這種碼檢錯能力不高，采用什么方法提高呢？,67,水平奇偶監(jiān)督碼和水平垂直監(jiān)督碼,又叫 二維奇偶監(jiān)督碼水平奇偶監(jiān)督碼檢碼字按行排成方陣，每行采用奇偶監(jiān)督碼，發(fā)送時按列的順序傳送，接收時仍將碼字排列成發(fā)送時方陣形式，然后按行進行奇偶校驗。在不增加冗余度時，不僅發(fā)現(xiàn)某一行上奇數(shù)個錯誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯誤。水平垂直奇偶監(jiān)督碼不僅對行進行奇偶校驗，而且也對列進行奇偶校驗。,68,分組碼 (1),分組碼的監(jiān)督方程

40、矩陣形式,6.2 線性分組碼,69,分組碼 (2),監(jiān)督矩陣H矩陣稱為典型形式，各行一定是線性無關的。而一個非典型形式的經(jīng)過運算可以化成典型形式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關系。,70,分組碼 (3),生成矩陣 ，通過生成矩陣可以得到生成碼組。如果輸入碼組為 0011,71,分組碼 (4),由這種方式得到的生成矩陣稱為典型生成矩陣，由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信

41、息碼字保持不變，監(jiān)督位附加其后，每行一定是線性無關的，每行都是一個生成碼組。,72,漢明碼,漢明碼監(jiān)督位為 位，因此它可以組成 種可能情況，其中一個為無錯。因此可以監(jiān)督碼位共 要糾正一個錯誤，必須滿足最小碼距如果 r 位監(jiān)督位所組成的校正子碼組與誤碼圖樣一一對應，這種碼組稱為完備碼（取等號時）,73,擴展?jié)h明碼,如果在漢明碼基礎上，再加上一位對所有碼字進行校驗的監(jiān)督位監(jiān)督碼字由 r 位增

42、加到 r+1 位信息位不變碼長 碼結(jié)構(gòu)糾 1 位錯，檢測 2 位錯如 （8，4），（16，11）,74,擴展?jié)h明碼矩陣,如 (7,4)－> (8,4),75,縮短漢明碼,(n,k) －> (n-s, k-s)如 (15,11)－> (12,8)監(jiān)督矩陣 Hs 是將原 H 的前 3 列 去掉縮短漢明碼的最小碼距至少和原來碼的碼距相同，因為監(jiān)督位沒有變。,76,能糾 t 個錯誤的(n

43、,k)應滿足取等號時為完備碼不同結(jié)構(gòu)的線性碼其糾錯能力不同，能力和dmin 有關，dmin 越大越好。,77,最小碼距界限,上界： 漢明界， 普洛特金界下界： 吉爾伯特界問題： 給定碼長與編碼效率，尋找 dmin例： dmin=5, 碼長=63 的分組碼設計從漢明界得，因此信息位最多可以取,78,最小碼距界限,通過吉爾伯特界求下界線性碼

44、 k 越接近 52， 效率越高。,79,6.3 循環(huán)碼 (Cyclic code),1957 年發(fā)現(xiàn)特點線性分組碼循環(huán)性——任一許用碼字經(jīng)過循環(huán)移位后，得到的碼組仍為一個許用碼組如 是循環(huán)碼的一許用碼組 則 也是一許用碼組,80,碼多項式表示,碼組碼多項式碼組碼多項式左移一位左移 位

45、,81,循環(huán)碼性質(zhì),為許用碼組，則 也是許用碼組性質(zhì)若 是長度為n的循環(huán)碼組，則 在按模 進行運算后，也是一個循環(huán)碼組，也就是 用 多項式除后所得之余式，即為所求的碼組。,82,循環(huán)碼例子,碼組左移 3 位去除 得余式如

46、 左移 3 位后，得 是許用碼組,83,循環(huán)碼生成多項式g(D),g(D) 是 D的 (n-k) 次即r 次多項式信息多項式為M(D),k 位，(k-1)次多項式,84,Theo.一個(n,k) 的二進制循環(huán)碼可以看成是唯一由它的生成多項式產(chǎn)生，即如(7,3)循環(huán)碼，n=7, k=3, r=4如果信息位為 010， M(D)=D 生成碼為 0111010

47、,循環(huán)碼生成多項式g(D),85,生成矩陣 G(D),由于 k 位信息位共有 個碼組，都可用此法產(chǎn)生，如果現(xiàn)有信息碼 生成 k 個碼字，且這 k 個碼字都線性無關，用這 k 個碼字作為一個矩陣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)碼? 系

48、統(tǒng)碼,系統(tǒng)碼的碼多項式為例如，(7,4)碼，1011,89,非系統(tǒng)碼? 系統(tǒng)碼,90,尋找生成多項式,Theo. 循環(huán)碼的生成多項式必須能除盡 h(D)是監(jiān)督多項式例：要構(gòu)成(7,3)循環(huán)碼，求g(D). 解：g(D)應為4階 生成(7,6)循環(huán)碼生成(7,1)循環(huán)碼,91,循環(huán)碼的編碼器,原理：按系統(tǒng)碼的生成方

49、式以(7,4)碼為例,92,循環(huán)碼的譯碼器,譯碼比編碼復雜得多譯碼三步伴隨式S的計算由S得到錯誤圖樣糾正,93,伴隨式的計算,發(fā)送碼組 接收碼組誤差碼組校正子只與 E 有關，根本是計算校正子,94,6.4 BCH碼,即約多項式一個 m 次多項式不能被二元域上任何二次數(shù)小于的，但大于0的多項式除盡，如 是即約的。本原多項式若m次多項式P(x)除盡的

50、 的最小正整數(shù) n 滿足 ，就稱為本原的。如 能除盡 ，但除不盡 的。如 ： 是即約的，但不是本原的，因它能除盡 。,95,6.4.1 本原循環(huán)碼,由本原多項式構(gòu)成的碼稱為本原碼。特點

51、碼長為它的生成多項式是由若干m階或以m的因子為最高階的多項式相乘而構(gòu)成。要判定(n,k) 的循環(huán)碼是否存在，只需要判斷 n-k 階的生成多項式是否能由 Dn+1的因式構(gòu)成。,96,循環(huán)碼例子,生成多項式的階次為 r, 該生成多項式是否是 的因此。一個m階即約多項式一定能除盡如，m＝5，共有6個5階即約多項式。再加上 因子， 是以上7個多項式的乘積。,97,6.4.2 BCH

52、 碼的生成多項式,如果循環(huán)碼形式的形式為 為糾錯個數(shù) ， 為最小多項式， 為最小公倍數(shù)最小碼距 碼長為 的BCH碼稱為 本BCH碼（俠義） 碼長為 則稱為非本原BCH碼,98,BCH 碼,由于g(D)有t個因式，且每個因式的最高次為m，因此監(jiān)督碼元最多有mt位。對于糾t 個錯誤的本原

53、BCH碼，其生成多項式糾單個錯誤的本原BCH碼字為漢明碼。表11－13給出了 n<5的本原BCH碼。 11－14給出了部分非本原BCH碼。,99,BCH 碼例子,糾正 3 個錯誤，碼長為15的BCH碼解：n=15, m=5 查表11-12得，233707 這是(15,5)碼。,100,重要的BCH碼 (23,12),表11－14中最重要的BCH碼是(23,12

54、)稱為格雷碼，碼間為7，能糾正3個錯誤。生成多項式在實際通信系統(tǒng)中，所要求的n、k并不是碼表中所推薦的值，在這時我們可以采用縮短或擴展的方式加以修正，也就是通過增加信息符號或校驗符號來增加碼組長度，或減少信息和校驗位來減少碼組長度。,101,BCH碼,如 BCH碼的碼長為奇數(shù)，而有時需要偶數(shù)碼長，這時可以在原BCH碼生成多項式中乘以（D+1)因子，從而得到（n+1,k）擴展BCH碼，這時相當于在原BCH碼上加一個全校驗位，從

55、而將碼距增加1，這時的碼字不具有循環(huán)性。如果BCH碼不是2m-1或它的因式，這時可以采用縮短的方式，去掉s位信息，(n-s , k-s),102,RS碼 Reed-Solomon,非二進制BCH碼，輸入以符號來考慮假定每組有 K 個符號，每個符號用m比特，輸入信息將是 K×m 比特。,103,RS碼,RS碼適合于糾正突發(fā)錯誤，糾正的錯誤圖樣有對于一個長度為 符號的RS碼，每個符號都可以看成是

56、有限域 中的一個元素，如RS碼的最小碼距為d符號，則生成多項式,104,6.5 糾正和檢測突發(fā)錯誤的分組碼－交織碼interleaved,在水平垂直監(jiān)督碼中將信息碼排列成方陣，然后對行和列分別進行檢驗，可以達到檢測突發(fā)錯誤的目的。如果方陣中行碼是能糾 t 個隨機錯誤，交織后能糾t個長度為i的突發(fā)錯誤。i稱為交織深度。,105,循環(huán)碼構(gòu)成交織碼,采用循環(huán)碼構(gòu)成交織碼時，可以不采用方陣就能實現(xiàn)編碼。假設交織碼每行為

57、 循環(huán)碼，其生成多項式為 ， 可以除盡 ，如交織深度為 其交織碼為 ,其生成多項式為 可以除盡 ，所以 也是循環(huán)碼。,106,循環(huán)碼構(gòu)成交織碼 (續(xù)),如，循環(huán)碼(7,4)， 其生成多項式為構(gòu)成交織深度為3 的(21,12)交織碼。交織碼的生成多項

58、式為它也是循環(huán)碼，可以用循環(huán)碼的方式構(gòu)成。在發(fā)送端可以不排成方陣，但是在譯碼時，必須將碼字排列成 陣列，然后分別獨立的對每行碼字進行譯碼。,107,交織碼 之小結(jié),為了進一步提高糾錯能力，可以在交織陣列中不僅對每行進行糾錯編碼，而且也對每列進行糾錯編碼，這種形式的交織碼稱為乘積碼。若乘積碼的行碼和列碼 分別能糾長度超過 的突發(fā)錯誤，則乘積碼能糾正長度為