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

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)在信道的傳輸過(guò)程中,由于實(shí)際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會(huì)產(chǎn)生誤碼。,編碼,4,6.1 糾錯(cuò)編譯碼的基本原理與分析方法,5,6.1.1 差錯(cuò)和差錯(cuò)控制系統(tǒng)分類(lèi),差錯(cuò)率是衡量傳輸質(zhì)量的重要指標(biāo)之一,它有幾種不同的定義。 碼元差錯(cuò)率/符號(hào)差錯(cuò)率 指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯(cuò)的碼元數(shù)所占的比例(平均值),簡(jiǎn)稱(chēng)誤碼率。 是指信號(hào)差錯(cuò)概率

2、比特差錯(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)用場(chǎng)合對(duì)差錯(cuò)率有不同的要求: 在電報(bào)傳送時(shí),允許的比特差錯(cuò)率約為: 104105； 計(jì)算機(jī)數(shù)據(jù)傳輸,一般要求比特差錯(cuò)率小于: 108109； 在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯(cuò)率,7,差錯(cuò)圖樣,為定量地描述信號(hào)的差錯(cuò),定義差錯(cuò)圖樣E E=CR (模M ) 最常用的二進(jìn)制碼可當(dāng)作特例來(lái)研究,其差錯(cuò)圖樣等于收碼與發(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 差錯(cuò)的圖樣E 0 1 1 0 1 1 0 0 0 0 差錯(cuò)圖樣中的“1”既是符號(hào)差錯(cuò)也是比特差錯(cuò),差錯(cuò)的個(gè)數(shù)叫漢明距離。,0:傳輸中無(wú)錯(cuò) 1:傳輸中有錯(cuò),8,差錯(cuò)圖樣,隨機(jī)差錯(cuò)： 差錯(cuò)是相互獨(dú)立的,不相關(guān) 存在這種差錯(cuò)的信道是無(wú)記憶信道或隨機(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ā)長(zhǎng)度= 4,突發(fā)長(zhǎng)度= 6,9,糾錯(cuò)碼分類(lèi),從功

4、能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼 檢錯(cuò)碼：用于發(fā)現(xiàn)差錯(cuò) 糾錯(cuò)碼：能自動(dòng)糾正差錯(cuò) 糾錯(cuò)碼與檢錯(cuò)碼在理論上沒(méi)有本質(zhì)區(qū)別,只是應(yīng)用場(chǎng)合不同,而側(cè)重的性能參數(shù)也不同。,10,糾錯(cuò)碼分類(lèi),按照對(duì)信息序列的處理方法,有分組碼和卷積碼 分組碼： 將k個(gè)信息碼元分成一組,由這k個(gè)碼元按照一定規(guī)則產(chǎn)生r個(gè)監(jiān)督碼元,組成長(zhǎng)度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,糾錯(cuò)碼分類(lèi),按照碼元與原始信息位的關(guān)系,分為 線性碼：所

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

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

7、道送回到發(fā)端,發(fā)端比較發(fā)的數(shù)據(jù)與反饋來(lái)的數(shù)據(jù),從而發(fā)現(xiàn)錯(cuò)誤,并且把錯(cuò)誤的消息再次傳送,直到發(fā)端沒(méi)有發(fā)現(xiàn)錯(cuò)誤為止。,16,檢錯(cuò)與糾錯(cuò)原理,0:晴,1:雨 若10,01。收端無(wú)法發(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,雨,18,檢錯(cuò)與糾錯(cuò)原理,最大似然譯碼： 將接收到的碼字譯碼為與它差別最小的許用碼字,并且認(rèn)為

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

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

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

11、碼組中非0的數(shù)目。,23,碼距與檢錯(cuò)、糾錯(cuò)能力,定理：若糾錯(cuò)碼的最小距離為dmin， 可以檢測(cè)出任意小于等于l = dmin1個(gè)差錯(cuò) 可以糾正任意小于等于 個(gè)差錯(cuò),可以檢測(cè)出任意小于等于l同時(shí)糾正小于等于t個(gè)差錯(cuò)， 其中l(wèi)、t滿(mǎn)足： l + t dmin1 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+ r r：監(jiān)督碼元的數(shù)目,信道編碼,第6章,28,6.1 糾錯(cuò)編

12、譯碼的基本原理與分析方法 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)在信道的傳輸過(guò)程中,由于實(shí)際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會(huì)產(chǎn)生誤碼。,編碼,30,6.1 糾錯(cuò)編譯碼的基本原理與分析方法,31,6.1.1 差錯(cuò)和差錯(cuò)控制系統(tǒng)分類(lèi),差錯(cuò)率是衡量傳輸質(zhì)量的重要指標(biāo)之一,它有幾種不同的定義。 碼元差錯(cuò)率/符號(hào)差錯(cuò)率 指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯(cuò)的碼元數(shù)所占的比例(平均值),簡(jiǎn)稱(chēng)誤碼率。 是指信號(hào)差錯(cuò)概率 比特差錯(cuò)率 /比特誤碼率： 在

13、傳輸?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)用場(chǎng)合對(duì)差錯(cuò)率有不同的要求: 在電報(bào)傳送時(shí),允許的比特差錯(cuò)率約為: 104105； 計(jì)算機(jī)數(shù)據(jù)傳輸,一般要求比特差錯(cuò)率小于: 108109； 在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯(cuò)率,33,差錯(cuò)圖樣,為定量地描述信號(hào)的差錯(cuò),定義差錯(cuò)圖樣E E=CR (模M ) 最常用的二進(jìn)制碼可當(dāng)作特例來(lái)研究,其差錯(cuò)圖樣等于收碼與發(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 差錯(cuò)的圖樣E 0 1 1 0 1 1 0 0 0 0 差錯(cuò)圖樣中的“1”既是符號(hào)差錯(cuò)也是比特差錯(cuò),差錯(cuò)的個(gè)數(shù)叫漢明距離。,0:傳輸中無(wú)錯(cuò) 1:傳輸中有錯(cuò),34,差錯(cuò)圖樣,隨機(jī)差錯(cuò)： 差錯(cuò)是相互獨(dú)立的,不相關(guān) 存在這種差錯(cuò)的信道是無(wú)記憶信道或隨機(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ā)長(zhǎng)度= 4,突發(fā)長(zhǎng)度= 6,35,糾錯(cuò)碼分類(lèi),從功能角度講,差錯(cuò)碼分為檢

15、錯(cuò)碼和糾錯(cuò)碼 檢錯(cuò)碼：用于發(fā)現(xiàn)差錯(cuò) 糾錯(cuò)碼：能自動(dòng)糾正差錯(cuò) 糾錯(cuò)碼與檢錯(cuò)碼在理論上沒(méi)有本質(zhì)區(qū)別,只是應(yīng)用場(chǎng)合不同,而側(cè)重的性能參數(shù)也不同。,36,糾錯(cuò)碼分類(lèi),按照對(duì)信息序列的處理方法,有分組碼和卷積碼 分組碼： 將k個(gè)信息碼元分成一組,由這k個(gè)碼元按照一定規(guī)則產(chǎn)生r個(gè)監(jiān)督碼元,組成長(zhǎng)度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,糾錯(cuò)碼分類(lèi),按照碼元與原始信息位的關(guān)系,分為 線性碼：所有碼元均是原始信息元的

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

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

18、發(fā)的數(shù)據(jù)與反饋來(lái)的數(shù)據(jù),從而發(fā)現(xiàn)錯(cuò)誤,并且把錯(cuò)誤的消息再次傳送,直到發(fā)端沒(méi)有發(fā)現(xiàn)錯(cuò)誤為止。,42,檢錯(cuò)與糾錯(cuò)原理,0:晴,1:雨 若10,01。收端無(wú)法發(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,雨,44,檢錯(cuò)與糾錯(cuò)原理,最大似然譯碼： 將接收到的碼字譯碼為與它差別最小的許用碼字,并且認(rèn)為這個(gè)許用碼字就是它所對(duì)

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

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

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

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

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

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

25、0不同的位數(shù)，又叫漢明(Hamming)距。 10 1 1 0 碼重：3 01 1 0 0 2 距離：3,61,檢錯(cuò)、糾錯(cuò)能力,為檢查出 個(gè)錯(cuò)誤，要求最小碼距為 為糾正 個(gè)錯(cuò)誤，要求最小碼距為 為糾正 個(gè)錯(cuò)誤，同時(shí)檢查出 個(gè)錯(cuò)誤，要求最小碼距為,62,63,6.1.3. 差錯(cuò)控制編碼分類(lèi),按功能分 檢錯(cuò)碼 糾錯(cuò)碼 糾刪碼（發(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為輸入到

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

27、法提高呢？,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)督方程 矩陣形式,6.2 線性分組碼,69,分組碼 (2),監(jiān)督矩陣 H矩陣稱(chēng)為典型形式，各行一定是線性無(wú)關(guān)的。而一個(gè)非典型形式的經(jīng)過(guò)運(yùn)算可以化成典型形式，通過(guò)監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關(guān)系。,

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

29、1 位 信息位不變 碼長(zhǎng) 碼結(jié)構(gòu) 糾 1 位錯(cuò)，檢測(cè) 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 列 去掉 縮短漢明碼的最小碼距至少和原來(lái)碼的碼距相同，因?yàn)楸O(jiān)督位沒(méi)有變。,76,能糾 t 個(gè)錯(cuò)誤的(n,k)應(yīng)滿(mǎn)足 取等號(hào)時(shí)為完備碼 不同結(jié)構(gòu)的線性碼其糾錯(cuò)能力不同，能力和dmin 有關(guān)，dmin 越大越好。,77,最小碼距界限,上界： 漢明界， 普洛特金界 下界： 吉爾伯特界 問(wèn)題： 給定碼長(zhǎng)與編碼效率，尋找 dmin 例：

30、dmin=5, 碼長(zhǎng)=63 的分組碼設(shè)計(jì) 從漢明界得， 因此信息位最多可以取,78,最小碼距界限,通過(guò)吉爾伯特界求下界 線性碼 k 越接近 52， 效率越高。,79,6.3 循環(huán)碼 (Cyclic code),1957 年發(fā)現(xiàn) 特點(diǎn) 線性分組碼 循環(huán)性任一許用碼字經(jīng)過(guò)循環(huán)移位后，得到的碼組仍為一個(gè)許用碼組 如 是循環(huán)碼的一許用碼組 則 也是一許用碼組,80,碼多項(xiàng)式表示,碼組 碼多項(xiàng)式 碼組 碼多項(xiàng)式 左移一位 左移 位,81,循環(huán)碼性質(zhì),為許用碼組，則 也是許用碼組 性質(zhì) 若 是長(zhǎng)度為n的循環(huán)碼組，則 在按模 進(jìn)行運(yùn)算后，也是一個(gè)循環(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.一個(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,循環(huán)碼生成多項(xiàng)式g(D),85,生成矩陣 G(D),由于 k 位信息位共有 個(gè)碼組，都可用此法產(chǎn)生，如果現(xiàn)有信息碼 生成 k 個(gè)碼字，且這 k 個(gè)碼字都線性無(wú)關(guān)，用這 k 個(gè)碼字作為

32、一個(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)碼 系統(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的計(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)除盡的 的最小正整數(shù) n 滿(mǎn)足 ，就稱(chēng)為本原的。 如 能除盡 ，但除不盡 的。 如 ： 是即約的，但不是本原的，因它能除盡 。,95,6.4.1 本原循環(huán)碼,由本原多項(xiàng)式構(gòu)成的碼稱(chēng)為本原碼。 特點(diǎn) 碼長(zhǎng)為 它的生成多項(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)式一定能除盡 如，m5，共有6個(gè)5階即約多項(xiàng)式。 再加上 因子， 是以上7個(gè)多項(xiàng)式的乘積。,97,6.4.2 BCH 碼的生成多項(xiàng)式,如果循環(huán)碼形式的形式為 為糾錯(cuò)個(gè)數(shù) ， 為最小多項(xiàng)式， 為最小公倍數(shù) 最小碼距 碼長(zhǎng)為 的BCH碼稱(chēng)為 本BCH碼（俠義） 碼長(zhǎng)為 則稱(chēng)為非本原BCH碼,98,BCH 碼,由于g(D)有t個(gè)因式，且每個(gè)因式的最高次為m，因此監(jiān)督碼元最多有mt位。 對(duì)于糾t 個(gè)錯(cuò)誤的本原BCH碼，其生成多項(xiàng)式 糾單個(gè)