信道編碼糾錯(cuò)碼

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

2、一6.1.1 差錯(cuò)和差錯(cuò)控制系統(tǒng)分類差錯(cuò)率是衡量傳輸質(zhì)量的重要指標(biāo)之一,它有幾種不同的定義。碼元差錯(cuò)率/符號(hào)差錯(cuò)率指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯(cuò)的碼元數(shù)所占的比例(平均值),簡(jiǎn)稱誤碼率。是指信號(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ò)卻難以確定5第5頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(cuò)率根據(jù)不同的應(yīng)用場(chǎng)合對(duì)差錯(cuò)率有不同的要求:在電報(bào)傳送時(shí),允許的比特差錯(cuò)率約為: 104105；計(jì)算機(jī)數(shù)據(jù)傳輸,一般要求比特差錯(cuò)率小于: 108109；

3、在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯(cuò)率6第6頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(cuò)圖樣為定量地描述信號(hào)的差錯(cuò),定義差錯(cuò)圖樣E E=CR (模M )最常用的二進(jìn)制碼可當(dāng)作特例來研究,其差錯(cuò)圖樣等于收碼與發(fā)碼的模2加,即 E = CR 或 C = RE設(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ò) 7第7頁，共107頁，2022年，5月2

4、0日，1點(diǎn)34分，星期一差錯(cuò)圖樣隨機(jī)差錯(cuò)：差錯(cuò)是相互獨(dú)立的,不相關(guān)存在這種差錯(cuò)的信道是無記憶信道或隨機(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)度= 68第8頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一糾錯(cuò)碼分類 從功能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼檢錯(cuò)碼：用于發(fā)現(xiàn)差錯(cuò)糾錯(cuò)碼：能自動(dòng)糾正差錯(cuò)糾錯(cuò)碼與檢錯(cuò)碼在理論上沒有本質(zhì)區(qū)別,只是應(yīng)用場(chǎng)合不同,而側(cè)重的性能參數(shù)也不同。9第9頁，共107頁，2022年，5月20日，

5、1點(diǎn)34分，星期一糾錯(cuò)碼分類 按照對(duì)信息序列的處理方法,有分組碼和卷積碼分組碼：將k個(gè)信息碼元分成一組,由這k個(gè)碼元按照一定規(guī)則產(chǎn)生r個(gè)監(jiān)督碼元,組成長(zhǎng)度n = k + r的碼字 卷積碼：先將信息序列分組,不同的是編解碼運(yùn)算不僅與本組信息有關(guān),而且還與前面若干組有關(guān)。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr10第10頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一糾錯(cuò)碼分類 按照碼元與原始信息位的關(guān)系,分為線性碼：所有碼元均是原始信息元的線性組合,編碼器不帶反饋回路。非線性碼：碼元并不都是信息元的線性組合,可能還與前面已編的

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

7、數(shù)目在碼的糾錯(cuò)能力之內(nèi)時(shí),譯碼器對(duì)差錯(cuò)進(jìn)行定位并加以糾正。13第13頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(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ā)送的碼字(全部或部分)。14第14頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(cuò)控制系統(tǒng)分類 混合糾錯(cuò)(HEC)：是FEC與ARQ方式的結(jié)合。發(fā)端發(fā)送同時(shí)具有自動(dòng)糾錯(cuò)和檢測(cè)能力的碼組,收端收到碼組后,檢查差錯(cuò)情況,如果差錯(cuò)在碼的糾錯(cuò)能力以內(nèi),則自動(dòng)進(jìn)行糾正。如果信道干擾很嚴(yán)重,錯(cuò)誤很多,超過了碼的糾錯(cuò)能力,但能

8、檢測(cè)出來,則經(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ò)誤為止。15第15頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一檢錯(cuò)與糾錯(cuò)原理 0:晴,1:雨若10,01。收端無法發(fā)現(xiàn)錯(cuò)誤00晴1001110011雨能發(fā)現(xiàn)一個(gè)錯(cuò)誤禁用碼組插入1位監(jiān)督碼后具有檢出1位錯(cuò)碼的能力,但不能予以糾正。16第16頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一檢錯(cuò)與糾錯(cuò)原理 000晴010001111000111雨晴在只有1位錯(cuò)碼的情況下,可

9、以判決哪位是錯(cuò)碼并予以糾正,可以檢出2位或2位以下的錯(cuò)碼。100011101110雨17第17頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一檢錯(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),但信道的傳輸效率下降也越多。18第18頁，共107頁，2022年，5月20日，1點(diǎn)3

10、4分，星期一信道編碼在被傳輸信息中附加一些冗余碼,即監(jiān)督碼元,利用附加碼元與信息碼元間的約束關(guān)系加以校驗(yàn),以檢測(cè)和糾正錯(cuò)誤。信源編碼減少了冗余度冗余度是隨機(jī)的、無規(guī)律的信道編碼增加了冗余度冗余度是特定的、有規(guī)律的,故可利用其在接收端進(jìn)行檢錯(cuò)和糾錯(cuò)。信道編碼19第19頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一傳輸冗余比特必然要?jiǎng)佑萌哂嗟馁Y源。時(shí)間：比如一個(gè)比特重復(fù)發(fā)幾次,或一段消息重復(fù)發(fā)幾遍,或根據(jù)收端的反饋重發(fā)受損信息組。頻帶：插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一是增大符號(hào)傳遞速率(波特率),結(jié)果就占用了更大的帶寬。功率：采用多進(jìn)制符號(hào),用8進(jìn)制AS

11、K符號(hào)代替4進(jìn)制ASK符號(hào)來傳送2比特信息,可騰出位置另傳1冗余比特。8進(jìn)制ASK符號(hào)的平均功率肯定比4進(jìn)制時(shí)要大,這就是動(dòng)用冗余的功率資源來傳輸冗余比特。設(shè)備復(fù)雜度：加大碼長(zhǎng),采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實(shí)施糾錯(cuò)編碼的有效方法,代價(jià)是算法復(fù)雜度的提高,需動(dòng)用設(shè)備資源。20第20頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一信道編碼的基本思想信道編碼按一定規(guī)則給數(shù)字序列m增加一些多余的碼元,使不具有規(guī)律性的信息序列 m 變換為具有某種規(guī)律性的數(shù)碼序列 C；碼序列中的信息序列碼元與多余碼元之間是相關(guān)的；信道譯碼器利用這種預(yù)知的編碼規(guī)則譯碼。檢驗(yàn)接收到的數(shù)字序列 R 是否

12、符合既定的 規(guī)則,從而發(fā)現(xiàn) R 中是否有錯(cuò),或者糾正其中的差錯(cuò)；根據(jù)相關(guān)性來檢測(cè)/發(fā)現(xiàn)和糾正傳輸過程中產(chǎn)生的差錯(cuò)就是信道編碼的基本思想。21第21頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一碼距與檢錯(cuò)、糾錯(cuò)能力糾錯(cuò)編碼的檢錯(cuò)糾錯(cuò)能力,要取決于碼組的碼距碼距越大,檢錯(cuò)、糾錯(cuò)能力越強(qiáng)。漢明距離：二個(gè)碼組對(duì)應(yīng)碼位碼元不同的個(gè)數(shù)。最小碼距dmin：一個(gè)碼組的集合中任意二個(gè)碼組間的最小漢明距離。碼重W：碼組中非0的數(shù)目。22第22頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一碼距與檢錯(cuò)、糾錯(cuò)能力定理：若糾錯(cuò)碼的最小距離為dmin，可以檢測(cè)出任意小于等于l = dmin1個(gè)差錯(cuò)可

13、以糾正任意小于等于 個(gè)差錯(cuò)可以檢測(cè)出任意小于等于l同時(shí)糾正小于等于t個(gè)差錯(cuò)，其中l(wèi)、t滿足： l + t dmin1 t l23第23頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一檢錯(cuò)、糾錯(cuò)能力為檢查出 個(gè)錯(cuò)誤，要求最小碼距為為糾正 個(gè)錯(cuò)誤，要求最小碼距為為糾正 個(gè)錯(cuò)誤，同時(shí)檢查出 個(gè)錯(cuò)誤，要求最小碼距為24第24頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一糾錯(cuò)檢錯(cuò)示意圖25第25頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一編碼效率編碼效率：一個(gè)組中信息所占的比重k：信息碼元的數(shù)目n：編碼組碼元的總數(shù)目 n = k+ rr：監(jiān)督碼元的數(shù)目26第26頁，共

14、107頁，2022年，5月20日，1點(diǎn)34分，星期一信道編碼 第6章第27頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.1 糾錯(cuò)編譯碼的基本原理與分析方法6.2 線性分組碼6.3 卷積碼內(nèi)容28第28頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一信源編碼提高數(shù)字信號(hào)有效性將信源的模擬信號(hào)轉(zhuǎn)變?yōu)閿?shù)字信號(hào)降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮)信道編碼提高數(shù)字通信可靠性 數(shù)字信號(hào)在信道的傳輸過程中,由于實(shí)際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會(huì)產(chǎn)生誤碼。編碼29第29頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.1 糾錯(cuò)編譯碼的基本原理與分析方

15、法30第30頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.1.1 差錯(cuò)和差錯(cuò)控制系統(tǒng)分類差錯(cuò)率是衡量傳輸質(zhì)量的重要指標(biāo)之一,它有幾種不同的定義。碼元差錯(cuò)率/符號(hào)差錯(cuò)率指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯(cuò)的碼元數(shù)所占的比例(平均值),簡(jiǎn)稱誤碼率。是指信號(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ò)卻難以確定31第31頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(cuò)率根據(jù)不同的應(yīng)用場(chǎng)合對(duì)差錯(cuò)率有不同的要求:在電報(bào)傳送時(shí),允許的比特差錯(cuò)率約為:

16、 104105；計(jì)算機(jī)數(shù)據(jù)傳輸,一般要求比特差錯(cuò)率小于: 108109；在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯(cuò)率32第32頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(cuò)圖樣為定量地描述信號(hào)的差錯(cuò),定義差錯(cuò)圖樣E E=CR (模M )最常用的二進(jìn)制碼可當(dāng)作特例來研究,其差錯(cuò)圖樣等于收碼與發(fā)碼的模2加,即 E = CR 或 C = RE設(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ù)叫漢明

17、距離。0:傳輸中無錯(cuò)1:傳輸中有錯(cuò) 33第33頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(cuò)圖樣隨機(jī)差錯(cuò)：差錯(cuò)是相互獨(dú)立的,不相關(guān)存在這種差錯(cuò)的信道是無記憶信道或隨機(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)度= 634第34頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一糾錯(cuò)碼分類 從功能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼檢錯(cuò)碼：用于發(fā)現(xiàn)差錯(cuò)糾錯(cuò)碼：能自動(dòng)糾正差錯(cuò)糾錯(cuò)碼與檢錯(cuò)碼在理論上沒有本質(zhì)區(qū)別,只是

18、應(yīng)用場(chǎng)合不同,而側(cè)重的性能參數(shù)也不同。35第35頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一糾錯(cuò)碼分類 按照對(duì)信息序列的處理方法,有分組碼和卷積碼分組碼：將k個(gè)信息碼元分成一組,由這k個(gè)碼元按照一定規(guī)則產(chǎn)生r個(gè)監(jiān)督碼元,組成長(zhǎng)度n = k + r的碼字 卷積碼：先將信息序列分組,不同的是編解碼運(yùn)算不僅與本組信息有關(guān),而且還與前面若干組有關(guān)。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr36第36頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一糾錯(cuò)碼分類 按照碼元與原始信息位的關(guān)系,分為線性碼：所有碼元均是原始信息元的

19、線性組合,編碼器不帶反饋回路。非線性碼：碼元并不都是信息元的線性組合,可能還與前面已編的碼元有關(guān),編碼器可能含反饋回路。由于非線性碼的分析比較困難,早期實(shí)用的糾錯(cuò)碼多為線性碼,但當(dāng)今發(fā)現(xiàn)的很多好碼恰恰是非線性碼。37第37頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一糾錯(cuò)碼分類 按照適用的差錯(cuò)類型,分成:糾隨機(jī)差錯(cuò)碼:用于隨機(jī)差錯(cuò)信道,其糾錯(cuò)能力用碼組內(nèi)允許的獨(dú)立差錯(cuò)的個(gè)數(shù)來衡量。糾突發(fā)差錯(cuò)碼:針對(duì)突發(fā)差錯(cuò)而設(shè)計(jì),其糾錯(cuò)能力主要用可糾突發(fā)差錯(cuò)的最大長(zhǎng)度來衡量38第38頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(cuò)控制系統(tǒng)分類 前向糾錯(cuò)(FEC)：發(fā)送端的信道編碼器將

20、信息碼組編成具有一定糾錯(cuò)能力的碼。接收端信道譯碼器對(duì)接收碼字進(jìn)行譯碼,若傳輸中產(chǎn)生的差錯(cuò)數(shù)目在碼的糾錯(cuò)能力之內(nèi)時(shí),譯碼器對(duì)差錯(cuò)進(jìn)行定位并加以糾正。39第39頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(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ā)送的碼字(全部或部分)。40第40頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(cuò)控制系統(tǒng)分類 混合糾錯(cuò)(HEC)：是FEC與ARQ方式的結(jié)合。發(fā)端發(fā)送同時(shí)具有自動(dòng)糾錯(cuò)和檢測(cè)能力的碼組,收端收到碼組后,檢查差錯(cuò)情況,如果差錯(cuò)在

21、碼的糾錯(cuò)能力以內(nèi),則自動(dòng)進(jìn)行糾正。如果信道干擾很嚴(yán)重,錯(cuò)誤很多,超過了碼的糾錯(cuò)能力,但能檢測(cè)出來,則經(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ò)誤為止。41第41頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一檢錯(cuò)與糾錯(cuò)原理 0:晴,1:雨若10,01。收端無法發(fā)現(xiàn)錯(cuò)誤00晴1001110011雨能發(fā)現(xiàn)一個(gè)錯(cuò)誤禁用碼組插入1位監(jiān)督碼后具有檢出1位錯(cuò)碼的能力,但不能予以糾正。42第42頁，共107頁，2022年，5月20日，1點(diǎn)34分，星

22、期一檢錯(cuò)與糾錯(cuò)原理 000晴010001111000111雨晴在只有1位錯(cuò)碼的情況下,可以判決哪位是錯(cuò)碼并予以糾正,可以檢出2位或2位以下的錯(cuò)碼。100011101110雨43第43頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一檢錯(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ò)能力越

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

24、是增大符號(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ù)雜度：加大碼長(zhǎng),采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實(shí)施糾錯(cuò)編碼的有效方法,代價(jià)是算法復(fù)雜度的提高,需動(dòng)用設(shè)備資源。46第46頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一信道編碼的基本思想信道編碼按一定規(guī)則給數(shù)字序列m增加一些多余的碼元,使不具有規(guī)律性的信息序列 m 變換為具有某種規(guī)律性的數(shù)碼序列 C；碼序列中的信息序列碼元與多

25、余碼元之間是相關(guān)的；信道譯碼器利用這種預(yù)知的編碼規(guī)則譯碼。檢驗(yàn)接收到的數(shù)字序列 R 是否符合既定的 規(guī)則,從而發(fā)現(xiàn) R 中是否有錯(cuò),或者糾正其中的差錯(cuò)；根據(jù)相關(guān)性來檢測(cè)/發(fā)現(xiàn)和糾正傳輸過程中產(chǎn)生的差錯(cuò)就是信道編碼的基本思想。47第47頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一碼距與檢錯(cuò)、糾錯(cuò)能力糾錯(cuò)編碼的檢錯(cuò)糾錯(cuò)能力,要取決于碼組的碼距碼距越大,檢錯(cuò)、糾錯(cuò)能力越強(qiáng)。漢明距離：二個(gè)碼組對(duì)應(yīng)碼位碼元不同的個(gè)數(shù)。最小碼距dmin：一個(gè)碼組的集合中任意二個(gè)碼組間的最小漢明距離。碼重W：碼組中非0的數(shù)目。48第48頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一碼距與檢錯(cuò)、糾錯(cuò)

26、能力定理：若糾錯(cuò)碼的最小距離為dmin，可以檢測(cè)出任意小于等于l = dmin1個(gè)差錯(cuò)可以糾正任意小于等于 個(gè)差錯(cuò)可以檢測(cè)出任意小于等于l同時(shí)糾正小于等于t個(gè)差錯(cuò)，其中l(wèi)、t滿足： l + t dmin1 t l49第49頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一編碼效率編碼效率：一個(gè)組中信息所占的比重k：信息碼元的數(shù)目n：編碼組碼元的總數(shù)目 n = k+ rr：監(jiān)督碼元的數(shù)目50第50頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一檢錯(cuò)碼奇偶校驗(yàn)碼(n，n-1)(k+1，k)偶校驗(yàn)碼字51第51頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.1 概述誤

27、碼分類隨機(jī)信道噪聲引入的隨機(jī)誤碼，均勻分布突發(fā)信道由干擾、快衰落引起的突發(fā)誤碼如何減少誤碼？從信源編碼看，誤碼引起的性能惡化盡可能小，容錯(cuò)技術(shù)從傳輸看，可采用抗干擾能力強(qiáng)的調(diào)制方式，信道特性不理想可采用均衡。特別需要差錯(cuò)控制技術(shù)。數(shù)字通信中，要求誤碼率108以下，必須采用差錯(cuò)控制。52第52頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一二元碼產(chǎn)生誤碼的情況53第53頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.1.1 差錯(cuò)控制分類需要雙向信道，和前向信道有相同的通信容。引入較大的停頓（不實(shí)時(shí)）。可以糾正任何錯(cuò)誤。1. 反饋檢驗(yàn)法54第54頁，共107頁，2022年，

28、5月20日，1點(diǎn)34分，星期一2. 檢錯(cuò)重發(fā)法（ARQ）自動(dòng)請(qǐng)求重發(fā)也需要反向信道，但容量可以降低，也會(huì)引入停頓55第55頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一3. 前向糾錯(cuò)（FEC）不需要雙向信道不會(huì)引入停頓靠糾錯(cuò)編碼56第56頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一4. 混合糾錯(cuò)（HEC）需要反饋信道可能會(huì)引入停頓靠糾錯(cuò)編碼和檢錯(cuò)碼57第57頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.1.2 差錯(cuò)控制編碼的基本原理如用三位二進(jìn)制編碼來代表八個(gè)字母000 A100E001 B101F010C110G011D111H不管哪一位發(fā)生錯(cuò)誤，都

29、會(huì)使傳輸字母錯(cuò)誤如用三位字母?jìng)魉膫€(gè)字母000 A011B101 C110D發(fā)生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道出錯(cuò)，但是不能糾錯(cuò)。58第58頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一差錯(cuò)控制編碼如用三位字母?jìng)鞫€(gè)字母000 A 111B檢二個(gè)錯(cuò)誤，糾正一個(gè)錯(cuò)誤。結(jié)論具有檢錯(cuò)或糾錯(cuò)的碼組，其所用的比特?cái)?shù)必須大于信息碼組原來的比特?cái)?shù)引入余度。59第59頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一碼重、碼距碼重(weight)一個(gè)碼組中“1”的數(shù)目碼距(distance)兩個(gè)碼組之間對(duì)應(yīng)位置上1、0不同的位數(shù)，又叫漢明(Hamming)距。10 1 1

30、0 碼重：301 1 0 0 2 距離：360第60頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一檢錯(cuò)、糾錯(cuò)能力為檢查出 個(gè)錯(cuò)誤，要求最小碼距為為糾正 個(gè)錯(cuò)誤，要求最小碼距為為糾正 個(gè)錯(cuò)誤，同時(shí)檢查出 個(gè)錯(cuò)誤，要求最小碼距為61第61頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一62第62頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.1.3. 差錯(cuò)控制編碼分類按功能分檢錯(cuò)碼 糾錯(cuò)碼糾刪碼（發(fā)現(xiàn)不可糾正的錯(cuò)誤時(shí)，可發(fā)出指示或刪除）按信息碼元和監(jiān)督碼元之間的校驗(yàn)關(guān)系分線性碼非線性碼按信息碼元和監(jiān)督碼元之間的約束方式分分組碼卷積碼63第63頁，共107頁，20

31、22年，5月20日，1點(diǎn)34分，星期一香農(nóng)理 糾錯(cuò)碼的理論基礎(chǔ)香農(nóng)定理存在噪聲干擾的信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入到編碼器的二進(jìn)制碼元速率），則一定存在一種編碼方式，使編碼的錯(cuò)誤概率隨著碼長(zhǎng)n的增加將按指數(shù)下降到任一的值，即 P120結(jié)論如碼長(zhǎng)及發(fā)送信息速率一定，可以通過增大信道容量，使P減小。如在信道容量及發(fā)送信息速率一定，可以通過增加碼長(zhǎng)，使錯(cuò)誤概率下降。64第64頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一分組碼表示： (n,k)n : 幀長(zhǎng)k/n : 編碼效率特點(diǎn)監(jiān)督碼只用來監(jiān)督本幀中的信息位分類線性碼 信息碼與監(jiān)督碼之間為線性關(guān)系非線

32、性碼 不存在線性關(guān)系65第65頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一 奇偶監(jiān)督碼偶監(jiān)督奇監(jiān)督如果以上關(guān)系被破壞，則出現(xiàn)錯(cuò)誤，因此能檢查出奇數(shù)個(gè)錯(cuò)誤，但不能檢測(cè)偶數(shù)個(gè)錯(cuò)誤。最小碼距為 dmin=2這種碼檢錯(cuò)能力不高，采用什么方法提高呢？66第66頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一水平奇偶監(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ò)誤。水平垂直奇

33、偶監(jiān)督碼不僅對(duì)行進(jìn)行奇偶校驗(yàn)，而且也對(duì)列進(jìn)行奇偶校驗(yàn)。67第67頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一分組碼 (1)分組碼的監(jiān)督方程矩陣形式6.2 線性分組碼68第68頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一分組碼 (2)監(jiān)督矩陣H矩陣稱為典型形式，各行一定是線性無關(guān)的。而一個(gè)非典型形式的經(jīng)過運(yùn)算可以化成典型形式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關(guān)系。69第69頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一分組碼 (3)生成矩陣 ，通過生成矩陣可以得到生成碼組。如果輸入碼組為 001170第70頁，共107頁，2022年，5月20日，1

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

35、碼字由 r 位增加到 r+1 位信息位不變碼長(zhǎng) 碼結(jié)構(gòu)糾 1 位錯(cuò)，檢測(cè) 2 位錯(cuò)如 （8，4），（16，11）73第73頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一擴(kuò)展?jié)h明碼矩陣如 (7,4) (8,4)74第74頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一縮短漢明碼(n,k) (n-s, k-s)如 (15,11) (12,8)監(jiān)督矩陣 Hs 是將原 H 的前 3 列 去掉縮短漢明碼的最小碼距至少和原來碼的碼距相同，因?yàn)楸O(jiān)督位沒有變。75第75頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一能糾 t 個(gè)錯(cuò)誤的(n,k)應(yīng)滿足取等號(hào)時(shí)為完備碼不同結(jié)構(gòu)的線

36、性碼其糾錯(cuò)能力不同，能力和dmin 有關(guān)，dmin 越大越好。76第76頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一最小碼距界限上界： 漢明界， 普洛特金界下界： 吉爾伯特界問題： 給定碼長(zhǎng)與編碼效率，尋找 dmin例： dmin=5, 碼長(zhǎng)=63 的分組碼設(shè)計(jì)從漢明界得，因此信息位最多可以取77第77頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一最小碼距界限通過吉爾伯特界求下界線性碼 k 越接近 52， 效率越高。78第78頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.3 循環(huán)碼 (Cyclic code) 1957 年發(fā)現(xiàn)特點(diǎn)線性分組碼循環(huán)性任一許

37、用碼字經(jīng)過循環(huán)移位后，得到的碼組仍為一個(gè)許用碼組如 是循環(huán)碼的一許用碼組 則 也是一許用碼組 79第79頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一碼多項(xiàng)式表示碼組碼多項(xiàng)式碼組碼多項(xiàng)式左移一位左移 位80第80頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一循環(huán)碼性質(zhì) 為許用碼組，則 也是許用碼組性質(zhì)若 是長(zhǎng)度為n的循環(huán)碼組，則 在按模 進(jìn)行運(yùn)算后，也是一個(gè)循環(huán)碼組，也就是 用 多項(xiàng)式除后所得之余式，即為所求的碼組。81第81頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一循環(huán)碼例子碼組左移 3 位去除 得余式如 左移 3 位后，得 是許用碼組82第82頁，共

38、107頁，2022年，5月20日，1點(diǎn)34分，星期一循環(huán)碼生成多項(xiàng)式g(D)g(D) 是 D的 (n-k) 次即r 次多項(xiàng)式信息多項(xiàng)式為M(D),k 位，(k-1)次多項(xiàng)式83第83頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一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)84第84頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一生成矩陣 G(D)由于 k 位信息位共有 個(gè)碼組，都可用此法產(chǎn)生，如果現(xiàn)有信息碼

39、生成 k 個(gè)碼字，且這 k 個(gè)碼字都線性無關(guān)，用這 k 個(gè)碼字作為一個(gè)矩陣G 的 k行 構(gòu)成生成矩陣 G(D)85第85頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一循環(huán)碼(7,3) 循環(huán)碼86第86頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一生成矩陣和監(jiān)督矩陣這樣構(gòu)成的循環(huán)碼并非是系統(tǒng)碼系統(tǒng)碼的生成矩陣典型形式 非系統(tǒng)碼 系統(tǒng)碼生成矩陣監(jiān)督矩陣87第87頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一非系統(tǒng)碼 系統(tǒng)碼系統(tǒng)碼的碼多項(xiàng)式為例如，(7,4)碼，101188第88頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一非系統(tǒng)碼 系統(tǒng)碼89第89頁

40、，共107頁，2022年，5月20日，1點(diǎn)34分，星期一尋找生成多項(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)碼90第90頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一循環(huán)碼的編碼器原理：按系統(tǒng)碼的生成方式以(7,4)碼為例 91第91頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一循環(huán)碼的譯碼器譯碼比編碼復(fù)雜得多譯碼三步伴隨式S的計(jì)算由S得到錯(cuò)誤圖樣糾正92第92頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一伴隨式的計(jì)算發(fā)送碼組 接收碼

41、組誤差碼組校正子只與 E 有關(guān)，根本是計(jì)算校正子93第93頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.4 BCH碼即約多項(xiàng)式一個(gè) m 次多項(xiàng)式不能被二元域上任何二次數(shù)小于的，但大于0的多項(xiàng)式除盡，如 是即約的。本原多項(xiàng)式若m次多項(xiàng)式P(x)除盡的 的最小正整數(shù) n 滿足 ，就稱為本原的。如 能除盡 ，但除不盡 的。如 ： 是即約的，但不是本原的，因它能除盡 。94第94頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.4.1 本原循環(huán)碼由本原多項(xiàng)式構(gòu)成的碼稱為本原碼。特點(diǎn)碼長(zhǎng)為它的生成多項(xiàng)式是由若干m階或以m的因子為最高階的多項(xiàng)式相乘而構(gòu)成。要判定(n,k) 的循

42、環(huán)碼是否存在，只需要判斷 n-k 階的生成多項(xiàng)式是否能由 Dn+1的因式構(gòu)成。95第95頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一循環(huán)碼例子生成多項(xiàng)式的階次為 r, 該生成多項(xiàng)式是否是 的因此。一個(gè)m階即約多項(xiàng)式一定能除盡如，m5，共有6個(gè)5階即約多項(xiàng)式。再加上 因子， 是以上7個(gè)多項(xiàng)式的乘積。96第96頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一6.4.2 BCH 碼的生成多項(xiàng)式如果循環(huán)碼形式的形式為 為糾錯(cuò)個(gè)數(shù) ， 為最小多項(xiàng)式， 為最小公倍數(shù)最小碼距 碼長(zhǎng)為 的BCH碼稱為 本BCH碼（俠義） 碼長(zhǎng)為 則稱為非本原BCH碼97第97頁，共107頁，2022年，5月20日，1點(diǎn)34分，星期一BCH 碼由于g(D)有t個(gè)因式，且每個(gè)因式的最高次為m，因此監(jiān)督碼元最多有mt位。對(duì)于糾t 個(gè)錯(cuò)誤的本原BCH碼，其生成多項(xiàng)式糾單個(gè)錯(cuò)誤的本原BCH碼字