信道編碼(糾錯(cuò)碼)

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

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

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

4、 E = C⊕R 或 C = R⊕E設(shè)發(fā)送的碼字C 1 1 1 1 1 1 1 1 1 1 接收的碼字R 1 0 0 1 0 0 1 1 1 1 差錯(cuò)的圖樣E 0 1 1 0 1 1 0 0 0 0 差錯(cuò)圖樣中的“1”既是符號(hào)差錯(cuò)也是比特差錯(cuò),差錯(cuò)的個(gè)數(shù)叫漢明距離。,0:傳輸中無錯(cuò)1:傳輸中有錯(cuò),8,差錯(cuò)圖樣,隨機(jī)差錯(cuò)：差錯(cuò)是相互獨(dú)立的,不相關(guān)存在這種差錯(cuò)

5、的信道是無記憶信道或隨機(jī)信道突發(fā)差錯(cuò)：指成串出現(xiàn)的錯(cuò)誤,錯(cuò)誤與錯(cuò)誤間有相關(guān)性,一個(gè)差錯(cuò)往往要影響到后面一串字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,糾錯(cuò)碼分類,從功能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼檢錯(cuò)碼：用于發(fā)現(xiàn)差錯(cuò)糾錯(cuò)碼：能自動(dòng)糾正差錯(cuò)糾錯(cuò)碼與檢錯(cuò)碼在理論上沒有本質(zhì)區(qū)別,只是應(yīng)用場合不同,而側(cè)重的性能參數(shù)也不同。,1

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

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

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

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

10、止。,16,檢錯(cuò)與糾錯(cuò)原理,0:晴,1:雨若1→0,0→1。收端無法發(fā)現(xiàn)錯(cuò)誤,,,00晴,10,01,11,00,,,,,11雨,能發(fā)現(xiàn)一個(gè)錯(cuò)誤,禁用碼組,,插入1位監(jiān)督碼后具有檢出1位錯(cuò)碼的能力,但不能予以糾正。,,,17,檢錯(cuò)與糾錯(cuò)原理,,,000晴,010,001,111,000,,,,,111雨,晴,,在只有1位錯(cuò)碼的情況下,可以判決哪位是錯(cuò)碼并予以糾正,可以檢出2位或2位以下的錯(cuò)碼。,,100,,011,101,110,,

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

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

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

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

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

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

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

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

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

20、E = C⊕R 或 C = R⊕E設(shè)發(fā)送的碼字C 1 1 1 1 1 1 1 1 1 1 接收的碼字R 1 0 0 1 0 0 1 1 1 1 差錯(cuò)的圖樣E 0 1 1 0 1 1 0 0 0 0 差錯(cuò)圖樣中的“1”既是符號(hào)差錯(cuò)也是比特差錯(cuò),差錯(cuò)的個(gè)數(shù)叫漢明距離。,0:傳輸中無錯(cuò)1:傳輸中有錯(cuò),34,差錯(cuò)圖樣,隨機(jī)差錯(cuò)：差錯(cuò)是相互獨(dú)立的,不相關(guān)存在這種差錯(cuò)的信道是

21、無記憶信道或隨機(jī)信道突發(fā)差錯(cuò)：指成串出現(xiàn)的錯(cuò)誤,錯(cuò)誤與錯(cuò)誤間有相關(guān)性,一個(gè)差錯(cuò)往往要影響到后面一串字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,糾錯(cuò)碼分類,從功能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼檢錯(cuò)碼：用于發(fā)現(xiàn)差錯(cuò)糾錯(cuò)碼：能自動(dòng)糾正差錯(cuò)糾錯(cuò)碼與檢錯(cuò)碼在理論上沒有本質(zhì)區(qū)別,只是應(yīng)用場合不同,而側(cè)重的性能參數(shù)也不同。,36,糾

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

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

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

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

26、42,檢錯(cuò)與糾錯(cuò)原理,0:晴,1:雨若1→0,0→1。收端無法發(fā)現(xiàn)錯(cuò)誤,,,00晴,10,01,11,00,,,,,11雨,能發(fā)現(xiàn)一個(gè)錯(cuò)誤,禁用碼組,,插入1位監(jiān)督碼后具有檢出1位錯(cuò)碼的能力,但不能予以糾正。,,,43,檢錯(cuò)與糾錯(cuò)原理,,,000晴,010,001,111,000,,,,,111雨,晴,,在只有1位錯(cuò)碼的情況下,可以判決哪位是錯(cuò)碼并予以糾正,可以檢出2位或2位以下的錯(cuò)碼。,,100,,011,101,110,,雨,4

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

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

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

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

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

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

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

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

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

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

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

38、，可以通過增大信道容量，使P減小。如在信道容量及發(fā)送信息速率一定，可以通過增加碼長，使錯(cuò)誤概率下降。,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)錯(cuò)誤，因此能檢查出奇數(shù)個(gè)錯(cuò)誤，但不能檢測偶數(shù)個(gè)錯(cuò)誤。最小碼距為 dmin=

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

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

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

42、加到 r+1 位信息位不變碼長 碼結(jié)構(gòu)糾 1 位錯(cuò)，檢測 2 位錯(cuò)如 （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 個(gè)錯(cuò)誤的(n

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

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

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

46、 左移 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.一個(gè)(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

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

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

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

51、碼長為它的生成多項(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)式是否是 的因此。一個(gè)m階即約多項(xiàng)式一定能除盡如，m＝5，共有6個(gè)5階即約多項(xiàng)式。再加上 因子， 是以上7個(gè)多項(xiàng)式的乘積。,97,6.4.2 BCH

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

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

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

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

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

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

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