第七講差錯(cuò)控制編碼

1、主要內(nèi)容主要內(nèi)容n 差錯(cuò)編碼的概念差錯(cuò)編碼的概念n 差錯(cuò)控制的基本方法差錯(cuò)控制的基本方法n 線性分組碼的概念及基本原理線性分組碼的概念及基本原理n 漢明碼漢明碼n 循環(huán)碼循環(huán)碼n BCH碼碼n 交織的概念交織的概念為什么要進(jìn)行差錯(cuò)編碼？為什么要進(jìn)行差錯(cuò)編碼？差錯(cuò)控制的幾種基本方法各有何優(yōu)缺點(diǎn)？差錯(cuò)控制的幾種基本方法各有何優(yōu)缺點(diǎn)？如何構(gòu)造一個(gè)漢明碼？如何構(gòu)造一個(gè)漢明碼？如何構(gòu)造循環(huán)碼？如何構(gòu)造循環(huán)碼？如何構(gòu)造如何構(gòu)造BCH碼？碼？為什么要采用交織？為什么要采用交織？研究對(duì)象研究對(duì)象 格式化 信源 編碼 加密 信道 編碼 多路 復(fù)用 脈沖 調(diào)制 帶通 調(diào)制 頻率 擴(kuò)展 復(fù)用 多址 接入 格式化 信

2、源 譯碼 解密 信道 譯碼 多路 分接 檢測(cè) 解調(diào) 采樣 頻率 解擴(kuò) 復(fù)用 多址 接入 信源 信宿 消息碼元 數(shù)字輸入消息碼元 消息碼元 數(shù)字輸出消息碼元 比特流 數(shù)字基帶波形 數(shù)字頻帶波形 信 道 同步 n 研究對(duì)象在數(shù)字通信系統(tǒng)中的位置研究對(duì)象在數(shù)字通信系統(tǒng)中的位置差錯(cuò)控制差錯(cuò)控制n 為什么要采用差錯(cuò)控制為什么要采用差錯(cuò)控制噪聲所導(dǎo)致的傳輸差錯(cuò)與信息可靠傳輸需求的矛盾噪聲所導(dǎo)致的傳輸差錯(cuò)與信息可靠傳輸需求的矛盾在普通通信設(shè)備中，噪聲是不可消除的在普通通信設(shè)備中，噪聲是不可消除的此外，碼間串?dāng)_（此外，碼間串?dāng)_（ISI），多接入干擾（），多接入干擾（MAI）和鄰）和鄰小區(qū)干擾（小區(qū)干擾（ICI

3、）等均可能導(dǎo)致誤碼）等均可能導(dǎo)致誤碼匹配濾波，最佳判決等手段均不可能消除差錯(cuò)匹配濾波，最佳判決等手段均不可能消除差錯(cuò)問(wèn)題：是否可能實(shí)現(xiàn)可靠傳輸？或者至少降低傳輸?shù)牟顔?wèn)題：是否可能實(shí)現(xiàn)可靠傳輸？或者至少降低傳輸?shù)牟铄e(cuò)率？錯(cuò)率？解決問(wèn)題的方法：差錯(cuò)控制解決問(wèn)題的方法：差錯(cuò)控制差錯(cuò)控制的基本方法差錯(cuò)控制的基本方法n 三種基本方法三種基本方法反饋檢驗(yàn)反饋檢驗(yàn)檢錯(cuò)重發(fā)檢錯(cuò)重發(fā)ARQ前向糾錯(cuò)前向糾錯(cuò)FECn 反饋檢驗(yàn)反饋檢驗(yàn)最原始的差錯(cuò)控制最原始的差錯(cuò)控制需要雙向信道，和前向信道有相同的通信容量需要雙向信道，和前向信道有相同的通信容量引入較大的停頓，不實(shí)時(shí)引入較大的停頓，不實(shí)時(shí)反饋信道可靠時(shí)，可以糾正任何

4、錯(cuò)誤反饋信道可靠時(shí)，可以糾正任何錯(cuò)誤差錯(cuò)控制的基本方法差錯(cuò)控制的基本方法n 檢錯(cuò)重發(fā)檢錯(cuò)重發(fā)網(wǎng)絡(luò)常用的方式網(wǎng)絡(luò)常用的方式差錯(cuò)判決放在接收端，只反饋差錯(cuò)狀態(tài)差錯(cuò)判決放在接收端，只反饋差錯(cuò)狀態(tài)自動(dòng)請(qǐng)求重發(fā)，有效減少反饋量自動(dòng)請(qǐng)求重發(fā)，有效減少反饋量同樣難以適用于實(shí)時(shí)業(yè)務(wù)同樣難以適用于實(shí)時(shí)業(yè)務(wù)多種實(shí)現(xiàn)方式多種實(shí)現(xiàn)方式停發(fā)等候、返回重發(fā)、選擇重發(fā)停發(fā)等候、返回重發(fā)、選擇重發(fā)差錯(cuò)控制的基本方法差錯(cuò)控制的基本方法n 前向糾錯(cuò)前向糾錯(cuò)FEC無(wú)需反饋信道無(wú)需反饋信道直接在接收端對(duì)錯(cuò)誤進(jìn)行糾正，發(fā)端無(wú)需知道錯(cuò)誤直接在接收端對(duì)錯(cuò)誤進(jìn)行糾正，發(fā)端無(wú)需知道錯(cuò)誤的狀態(tài)的狀態(tài)適用于實(shí)時(shí)業(yè)務(wù)適用于實(shí)時(shí)業(yè)務(wù)無(wú)需重傳，發(fā)端不用

5、存儲(chǔ)，收端即時(shí)解碼，發(fā)送的無(wú)需重傳，發(fā)端不用存儲(chǔ)，收端即時(shí)解碼，發(fā)送的速率恒定速率恒定依靠糾錯(cuò)編碼依靠糾錯(cuò)編碼信道編碼信道編碼通過(guò)在碼流中引入有結(jié)構(gòu)的冗余信息，糾正在傳輸通過(guò)在碼流中引入有結(jié)構(gòu)的冗余信息，糾正在傳輸中出現(xiàn)的錯(cuò)誤中出現(xiàn)的錯(cuò)誤信道編碼信道編碼n 一個(gè)簡(jiǎn)單的例子一個(gè)簡(jiǎn)單的例子對(duì)稱二進(jìn)制信道對(duì)稱二進(jìn)制信道BSC1個(gè)比特，只傳個(gè)比特，只傳1次，差錯(cuò)概率次，差錯(cuò)概率1個(gè)比特，重復(fù)傳送個(gè)比特，重復(fù)傳送3次，接收端做多數(shù)判決，錯(cuò)誤概率次，接收端做多數(shù)判決，錯(cuò)誤概率付出或代價(jià)：增加了傳輸?shù)娜哂?，降低了傳輸?shù)男适杖牖蛟鲆妫禾岣吡藗鬏數(shù)目煽啃?，降低了誤碼率信道編碼信道編碼n 概念概念Channel

6、 Coding：通過(guò)合理的增加冗余信息，糾正信道：通過(guò)合理的增加冗余信息，糾正信道傳輸中可能出現(xiàn)的錯(cuò)誤，也稱為糾錯(cuò)碼：傳輸中可能出現(xiàn)的錯(cuò)誤，也稱為糾錯(cuò)碼：Error Correction Coding信道編碼的評(píng)價(jià)標(biāo)準(zhǔn)信道編碼的評(píng)價(jià)標(biāo)準(zhǔn)糾錯(cuò)性能糾錯(cuò)性能能糾正什么樣的錯(cuò)誤？能糾正多少錯(cuò)能糾正什么樣的錯(cuò)誤？能糾正多少錯(cuò)誤？最終的誤比特率性能如何？誤？最終的誤比特率性能如何？代價(jià)代價(jià)增加了多少冗余的比特？信息比特占整個(gè)增加了多少冗余的比特？信息比特占整個(gè)碼流的百分比即碼率如何？碼流的百分比即碼率如何？糾錯(cuò)碼的理論基礎(chǔ)糾錯(cuò)碼的理論基礎(chǔ)基于代數(shù)理論的結(jié)構(gòu)，便于譯碼基于代數(shù)理論的結(jié)構(gòu)，便于譯碼信道編碼信道

7、編碼n 重要性重要性信息系統(tǒng)不可或缺的重要技術(shù)信息系統(tǒng)不可或缺的重要技術(shù)移動(dòng)通信移動(dòng)通信深空通信與探測(cè)深空通信與探測(cè)可靠計(jì)算可靠計(jì)算存儲(chǔ)設(shè)備存儲(chǔ)設(shè)備信道編碼的分類信道編碼的分類n 按功能分按功能分檢錯(cuò)碼：僅能檢錯(cuò)檢錯(cuò)碼：僅能檢錯(cuò) 糾錯(cuò)碼：僅能糾錯(cuò)糾錯(cuò)碼：僅能糾錯(cuò)n 按信息碼元和監(jiān)督碼元之間的校驗(yàn)關(guān)系分按信息碼元和監(jiān)督碼元之間的校驗(yàn)關(guān)系分線性碼：監(jiān)督碼元與信息碼元之間線性關(guān)系線性碼：監(jiān)督碼元與信息碼元之間線性關(guān)系非線性碼：監(jiān)督碼元與信息碼元之間非線性關(guān)系非線性碼：監(jiān)督碼元與信息碼元之間非線性關(guān)系n 按信息碼元和監(jiān)督碼元之間的約束方式分按信息碼元和監(jiān)督碼元之間的約束方式分分組碼：監(jiān)督碼元僅與當(dāng)前碼

8、組相關(guān)分組碼：監(jiān)督碼元僅與當(dāng)前碼組相關(guān)卷積碼：監(jiān)督碼元與當(dāng)前及以前碼組都有關(guān)系卷積碼：監(jiān)督碼元與當(dāng)前及以前碼組都有關(guān)系n 按照信息碼元在編碼后是否保持原來(lái)形式按照信息碼元在編碼后是否保持原來(lái)形式系統(tǒng)碼：信息碼元編碼后不變系統(tǒng)碼：信息碼元編碼后不變非系統(tǒng)碼：信息碼元改變非系統(tǒng)碼：信息碼元改變信道編碼的香農(nóng)定理信道編碼的香農(nóng)定理n 有擾離散信道的編碼定理有擾離散信道的編碼定理存在噪聲干擾的信道，若信道容量為存在噪聲干擾的信道，若信道容量為C，只要發(fā)送端以，只要發(fā)送端以低于低于C的速率的速率R發(fā)送信息（發(fā)送信息（R為輸入到編碼器的二進(jìn)制碼為輸入到編碼器的二進(jìn)制碼元速率），則一定存在一種編碼方式，使編

9、碼的錯(cuò)誤概元速率），則一定存在一種編碼方式，使編碼的錯(cuò)誤概率隨著碼長(zhǎng)率隨著碼長(zhǎng)n的增加將按指數(shù)下降到任意小的值的增加將按指數(shù)下降到任意小的值兩個(gè)結(jié)論兩個(gè)結(jié)論如碼長(zhǎng)及發(fā)送信息速率一定，可以通過(guò)增大信道容如碼長(zhǎng)及發(fā)送信息速率一定，可以通過(guò)增大信道容量，使錯(cuò)誤概率減小量，使錯(cuò)誤概率減小如在信道容量及發(fā)送信息速率一定，可以通過(guò)增加如在信道容量及發(fā)送信息速率一定，可以通過(guò)增加碼長(zhǎng)，使錯(cuò)誤概率減小碼長(zhǎng)，使錯(cuò)誤概率減小給出了努力的方向，但怎么做？信道編碼的基本原理信道編碼的基本原理n 看一個(gè)例子看一個(gè)例子如用三位二進(jìn)制編碼來(lái)代表八個(gè)字母如用三位二進(jìn)制編碼來(lái)代表八個(gè)字母000 A100E001 B101F01

10、0C110G011D111H 不管哪一位發(fā)生錯(cuò)誤，都會(huì)使傳輸字母錯(cuò)誤不管哪一位發(fā)生錯(cuò)誤，都會(huì)使傳輸字母錯(cuò)誤如用三位二進(jìn)制碼傳四個(gè)字母如用三位二進(jìn)制碼傳四個(gè)字母000 A011B101 C110D發(fā)生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知發(fā)生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道出錯(cuò)，但是不能糾錯(cuò)。道出錯(cuò)，但是不能糾錯(cuò)。信道編碼的基本原理信道編碼的基本原理如用三位二進(jìn)制碼傳二個(gè)字母如用三位二進(jìn)制碼傳二個(gè)字母000 A111B檢兩個(gè)錯(cuò)誤，糾正一個(gè)錯(cuò)誤。檢兩個(gè)錯(cuò)誤，糾正一個(gè)錯(cuò)誤。結(jié)論結(jié)論具有檢錯(cuò)或糾錯(cuò)的碼組，其所用的比特?cái)?shù)必須大于具有檢錯(cuò)或糾錯(cuò)的碼組，其所用的比特?cái)?shù)必須大于信息碼組

11、原來(lái)的比特?cái)?shù)，引入信息碼組原來(lái)的比特?cái)?shù)，引入冗余度冗余度；引入的冗余必須具有一定的引入的冗余必須具有一定的結(jié)構(gòu)結(jié)構(gòu)，才能進(jìn)行檢錯(cuò)及，才能進(jìn)行檢錯(cuò)及糾錯(cuò)糾錯(cuò)信道編碼的基本原理信道編碼的基本原理n 幾個(gè)基本概念幾個(gè)基本概念碼字碼字二進(jìn)制序列二進(jìn)制序列碼重碼重(weight)一個(gè)碼組中一個(gè)碼組中“1”的數(shù)目的數(shù)目碼距碼距(distance) 兩個(gè)碼組之間對(duì)應(yīng)位置上兩個(gè)碼組之間對(duì)應(yīng)位置上1、0不同的位數(shù)不同的位數(shù) 又叫漢明又叫漢明(Hamming)距距10 1 1 0 碼重：碼重：301 1 00 碼重：碼重： 2 碼距：碼距：3信道編碼的基本原理信道編碼的基本原理n 檢錯(cuò)和糾錯(cuò)能力與碼距的關(guān)系檢錯(cuò)和

12、糾錯(cuò)能力與碼距的關(guān)系考慮碼字考慮碼字000錯(cuò)成錯(cuò)成001，Hamming距距1，概率，概率錯(cuò)成錯(cuò)成101，Hamming距距2，概率，概率錯(cuò)成錯(cuò)成111，Hamming距距3，概率，概率總結(jié)總結(jié)兩個(gè)碼字的兩個(gè)碼字的Hamming距離越大距離越大，則一個(gè)碼字誤判成另一個(gè)碼，則一個(gè)碼字誤判成另一個(gè)碼字的可能性越小字的可能性越小碼距與檢錯(cuò)、糾錯(cuò)能力緊密相碼距與檢錯(cuò)、糾錯(cuò)能力緊密相關(guān)關(guān)信道編碼的基本原理信道編碼的基本原理n 檢錯(cuò)和糾錯(cuò)能力與碼距的關(guān)系檢錯(cuò)和糾錯(cuò)能力與碼距的關(guān)系先考慮檢測(cè)碼字是否出錯(cuò)？先考慮檢測(cè)碼字是否出錯(cuò)？可檢測(cè)可檢測(cè)e個(gè)誤碼個(gè)誤碼一個(gè)碼字出錯(cuò)后不會(huì)變成另一個(gè)正確的碼字，即可一個(gè)碼字出

13、錯(cuò)后不會(huì)變成另一個(gè)正確的碼字，即可判斷出錯(cuò)；判斷出錯(cuò)；如果一個(gè)碼字內(nèi)出現(xiàn)如果一個(gè)碼字內(nèi)出現(xiàn)e個(gè)錯(cuò)誤，則正確碼字之間的間個(gè)錯(cuò)誤，則正確碼字之間的間距必須大于距必須大于e信道編碼的基本原理信道編碼的基本原理n 檢錯(cuò)和糾錯(cuò)能力與碼距的關(guān)系檢錯(cuò)和糾錯(cuò)能力與碼距的關(guān)系考慮單個(gè)碼字的糾錯(cuò)考慮單個(gè)碼字的糾錯(cuò)可糾正可糾正t個(gè)錯(cuò)誤個(gè)錯(cuò)誤碼字出現(xiàn)碼字出現(xiàn)t個(gè)錯(cuò)誤仍能正確判別的原則是：其他碼字個(gè)錯(cuò)誤仍能正確判別的原則是：其他碼字的各種錯(cuò)誤情況不會(huì)進(jìn)入到本碼字的各種錯(cuò)誤情況不會(huì)進(jìn)入到本碼字t為半徑的圓內(nèi)；為半徑的圓內(nèi)；其他碼字可能的最大圓的半徑也為其他碼字可能的最大圓的半徑也為t，則要求正確碼，則要求正確碼字之間的碼

14、距大于字之間的碼距大于2t信道編碼的基本原理信道編碼的基本原理n 檢錯(cuò)和糾錯(cuò)能力與碼距的關(guān)系檢錯(cuò)和糾錯(cuò)能力與碼距的關(guān)系考慮既檢錯(cuò)又糾錯(cuò)考慮既檢錯(cuò)又糾錯(cuò)檢測(cè)檢測(cè)e個(gè)錯(cuò)誤，糾個(gè)錯(cuò)誤，糾t個(gè)錯(cuò)誤個(gè)錯(cuò)誤檢測(cè)檢測(cè)e個(gè)錯(cuò)誤，要求碼字間距大于個(gè)錯(cuò)誤，要求碼字間距大于e考慮糾考慮糾t個(gè)錯(cuò)誤，則此時(shí)間距要考慮的不是正確碼字個(gè)錯(cuò)誤，則此時(shí)間距要考慮的不是正確碼字之間的距離。而是正確碼字和可能的錯(cuò)誤碼字之間的之間的距離。而是正確碼字和可能的錯(cuò)誤碼字之間的距離，所以在檢錯(cuò)基礎(chǔ)上還需要加距離，所以在檢錯(cuò)基礎(chǔ)上還需要加t信道編碼的基本原理信道編碼的基本原理n 檢錯(cuò)和糾錯(cuò)能力與碼距的關(guān)系檢錯(cuò)和糾錯(cuò)能力與碼距的關(guān)系總結(jié)總結(jié)在

15、一個(gè)碼組內(nèi)檢測(cè)在一個(gè)碼組內(nèi)檢測(cè)e個(gè)誤碼，則要求最小的碼間距個(gè)誤碼，則要求最小的碼間距在一個(gè)碼組內(nèi)糾正在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，則要求的最小碼間距個(gè)誤碼，則要求的最小碼間距在一個(gè)碼組內(nèi)糾正在一個(gè)碼組內(nèi)糾正t個(gè)錯(cuò)誤，同時(shí)檢測(cè)個(gè)錯(cuò)誤，同時(shí)檢測(cè)e個(gè)錯(cuò)誤，則要個(gè)錯(cuò)誤，則要求的最小碼間距求的最小碼間距信道編碼的基本原理信道編碼的基本原理n 信道編碼的準(zhǔn)則信道編碼的準(zhǔn)則可靠性準(zhǔn)則可靠性準(zhǔn)則能糾正更多的錯(cuò)誤能糾正更多的錯(cuò)誤最大化最小碼距最大化最小碼距有效性準(zhǔn)則有效性準(zhǔn)則給出盡可能多的需用碼字給出盡可能多的需用碼字碼率盡可能高碼率盡可能高碼率碼率k/n，k為信息位數(shù)，為信息位數(shù)，n為總碼長(zhǎng)為總碼長(zhǎng)分組碼分組碼n

16、 概念概念編碼后的碼元序列每編碼后的碼元序列每n為分為一組，其中為分為一組，其中k個(gè)信息碼元，個(gè)信息碼元，r個(gè)附加的監(jiān)督碼元，而且監(jiān)督碼元僅與本組的信息碼個(gè)附加的監(jiān)督碼元，而且監(jiān)督碼元僅與本組的信息碼元有關(guān)，而與其他碼組的的信息碼元無(wú)關(guān)元有關(guān)，而與其他碼組的的信息碼元無(wú)關(guān)二進(jìn)制序列分段，每段二進(jìn)制序列分段，每段k個(gè)，針對(duì)每段按照一定規(guī)則個(gè)，針對(duì)每段按照一定規(guī)則附加附加r個(gè)監(jiān)督碼元個(gè)監(jiān)督碼元分組碼的優(yōu)點(diǎn)分組碼的優(yōu)點(diǎn)容易以系統(tǒng)的數(shù)學(xué)理論進(jìn)行建模分析容易以系統(tǒng)的數(shù)學(xué)理論進(jìn)行建模分析實(shí)現(xiàn)電路簡(jiǎn)單，復(fù)雜度低實(shí)現(xiàn)電路簡(jiǎn)單，復(fù)雜度低線性分組碼線性分組碼信息碼元和監(jiān)督碼元之間的關(guān)系可以用線性方程表信息碼元和監(jiān)

17、督碼元之間的關(guān)系可以用線性方程表示示分組碼分組碼n 檢錯(cuò)分組碼的例子檢錯(cuò)分組碼的例子奇偶監(jiān)督碼奇偶監(jiān)督碼偶監(jiān)督偶監(jiān)督奇監(jiān)督奇監(jiān)督如果以上關(guān)系被破壞，則出現(xiàn)錯(cuò)誤，因此能檢查出如果以上關(guān)系被破壞，則出現(xiàn)錯(cuò)誤，因此能檢查出奇數(shù)個(gè)錯(cuò)誤，但不能檢測(cè)偶數(shù)個(gè)錯(cuò)誤。奇數(shù)個(gè)錯(cuò)誤，但不能檢測(cè)偶數(shù)個(gè)錯(cuò)誤。最小碼距為最小碼距為 dmin=2檢錯(cuò)能力不高檢錯(cuò)能力不高分組碼分組碼 水平奇偶監(jiān)督碼水平奇偶監(jiān)督碼將碼字按行排成方陣，每行采用奇偶監(jiān)督碼，發(fā)送時(shí)按列的將碼字按行排成方陣，每行采用奇偶監(jiān)督碼，發(fā)送時(shí)按列的順序傳送，接收時(shí)仍將碼字排列成發(fā)送時(shí)方陣形式，然后按順序傳送，接收時(shí)仍將碼字排列成發(fā)送時(shí)方陣形式，然后按行進(jìn)行奇

18、偶校驗(yàn)行進(jìn)行奇偶校驗(yàn)在不增加冗余度時(shí)，不僅能發(fā)現(xiàn)某一行上奇數(shù)個(gè)錯(cuò)誤，而且在不增加冗余度時(shí)，不僅能發(fā)現(xiàn)某一行上奇數(shù)個(gè)錯(cuò)誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯(cuò)誤也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯(cuò)誤沒(méi)有增加冗余度，但通過(guò)增加碼長(zhǎng)提高了檢錯(cuò)能力沒(méi)有增加冗余度，但通過(guò)增加碼長(zhǎng)提高了檢錯(cuò)能力最小碼距最小碼距dmin=2線性分組碼線性分組碼n 概念概念信息碼元和監(jiān)督碼元可以使用線性方程聯(lián)系信息碼元和監(jiān)督碼元可以使用線性方程聯(lián)系主要性質(zhì)主要性質(zhì)任意兩個(gè)需用碼組之和（模任意兩個(gè)需用碼組之和（模2和）仍為需用碼組和）仍為需用碼組最小碼距為非零碼的最小碼重最小碼距為非零碼的最小碼重n 先看一個(gè)例子先看一個(gè)例子構(gòu)造一個(gè)（

19、構(gòu)造一個(gè)（7，4）線性分組碼，能糾正）線性分組碼，能糾正1位錯(cuò)誤位錯(cuò)誤1位錯(cuò)誤可能出現(xiàn)在位錯(cuò)誤可能出現(xiàn)在7個(gè)碼位中的任何一位上，錯(cuò)誤的個(gè)碼位中的任何一位上，錯(cuò)誤的情形有情形有7種，加上無(wú)錯(cuò)，共種，加上無(wú)錯(cuò)，共8種狀態(tài)需要知識(shí)種狀態(tài)需要知識(shí)構(gòu)造構(gòu)造3位校正子，共位校正子，共8種組合，正好可以指示種組合，正好可以指示7種錯(cuò)誤種錯(cuò)誤和無(wú)錯(cuò)的狀態(tài)和無(wú)錯(cuò)的狀態(tài)線性分組碼線性分組碼 任意設(shè)計(jì)一種錯(cuò)誤位置和校正子的對(duì)應(yīng)關(guān)系任意設(shè)計(jì)一種錯(cuò)誤位置和校正子的對(duì)應(yīng)關(guān)系 由上表得到校正子與各碼元關(guān)系由上表得到校正子與各碼元關(guān)系線性分組碼線性分組碼由校正子關(guān)系確定編碼方程，保證無(wú)誤碼及校正子為由校正子關(guān)系確定編碼方程，

20、保證無(wú)誤碼及校正子為000，并由此解出監(jiān)督碼元的編碼方程，并由此解出監(jiān)督碼元的編碼方程由此得到許用碼組由此得到許用碼組最小碼距最小碼距3糾糾1個(gè)錯(cuò)個(gè)錯(cuò)檢檢2個(gè)錯(cuò)個(gè)錯(cuò)線性分組碼線性分組碼糾錯(cuò)糾錯(cuò) 對(duì)錯(cuò)誤碼組計(jì)算校正子，根據(jù)校正子與錯(cuò)誤位置的對(duì)應(yīng)對(duì)錯(cuò)誤碼組計(jì)算校正子，根據(jù)校正子與錯(cuò)誤位置的對(duì)應(yīng)關(guān)系糾正錯(cuò)誤關(guān)系糾正錯(cuò)誤接收到的碼字為接收到的碼字為1101110，計(jì)算校正子為，計(jì)算校正子為100，對(duì)應(yīng)錯(cuò)誤，對(duì)應(yīng)錯(cuò)誤位置為位置為3，則譯碼輸出為，則譯碼輸出為1100110線性分組碼線性分組碼n 線性系統(tǒng)分組碼的矩陣表示線性系統(tǒng)分組碼的矩陣表示編碼過(guò)程編碼過(guò)程編碼過(guò)程可以看成信息序列與一個(gè)矩陣的相乘，這編

21、碼過(guò)程可以看成信息序列與一個(gè)矩陣的相乘，這個(gè)矩陣成為個(gè)矩陣成為生成矩陣生成矩陣（n，k）線性分組碼，）線性分組碼，A為為n維行向量，維行向量，X為信息序?yàn)樾畔⑿蛄袠?gòu)成的列構(gòu)成的k維行向量，維行向量，I為為kXk的單位矩陣，的單位矩陣，Q為為kXr的矩陣的矩陣典型形式的生成矩陣，生成的一定是系統(tǒng)碼典型形式的生成矩陣，生成的一定是系統(tǒng)碼線性分組碼線性分組碼n 線性系統(tǒng)分組碼的矩陣表示線性系統(tǒng)分組碼的矩陣表示檢錯(cuò)的矩陣表示檢錯(cuò)的矩陣表示出錯(cuò)的條件出錯(cuò)的條件監(jiān)督矩陣監(jiān)督矩陣線性分組碼線性分組碼n 線性系統(tǒng)分組碼的矩陣表示線性系統(tǒng)分組碼的矩陣表示校正子計(jì)算的矩陣表示校正子計(jì)算的矩陣表示接收信號(hào)的表示接收

22、信號(hào)的表示校正子的計(jì)算校正子的計(jì)算校正子與錯(cuò)誤圖樣有確定的關(guān)系校正子與錯(cuò)誤圖樣有確定的關(guān)系糾錯(cuò)：根據(jù)錯(cuò)誤圖樣與校正子的關(guān)系確定錯(cuò)誤位置糾錯(cuò)：根據(jù)錯(cuò)誤圖樣與校正子的關(guān)系確定錯(cuò)誤位置進(jìn)行糾正進(jìn)行糾正線性分組碼線性分組碼n 線性系統(tǒng)分組碼的矩陣表示線性系統(tǒng)分組碼的矩陣表示校正子與誤碼位置的關(guān)系校正子與誤碼位置的關(guān)系對(duì)于糾對(duì)于糾1比特錯(cuò)誤的校正子（以書比特錯(cuò)誤的校正子（以書11-24的校驗(yàn)矩陣為的校驗(yàn)矩陣為例）例）按上述矩陣方式構(gòu)成的線性系統(tǒng)分組碼的監(jiān)督矩陣的每列實(shí)按上述矩陣方式構(gòu)成的線性系統(tǒng)分組碼的監(jiān)督矩陣的每列實(shí)際上是按照碼字順序給出了每個(gè)比特的校驗(yàn)子！際上是按照碼字順序給出了每個(gè)比特的校驗(yàn)子！線

23、性分組碼線性分組碼n 利用矩陣構(gòu)造線性系統(tǒng)分組碼利用矩陣構(gòu)造線性系統(tǒng)分組碼 第一個(gè)問(wèn)題：先構(gòu)造生成矩陣還是監(jiān)督矩陣？第一個(gè)問(wèn)題：先構(gòu)造生成矩陣還是監(jiān)督矩陣？回顧第一個(gè)例子，監(jiān)督矩陣確定了如何糾錯(cuò)，是構(gòu)造者自己確定的回顧第一個(gè)例子，監(jiān)督矩陣確定了如何糾錯(cuò)，是構(gòu)造者自己確定的，是根本，因此先確定監(jiān)督矩陣，是根本，因此先確定監(jiān)督矩陣線性系統(tǒng)碼的監(jiān)督矩陣的形式是確定的，要確定的是線性系統(tǒng)碼的監(jiān)督矩陣的形式是確定的，要確定的是QQ的列確定了信息位的校驗(yàn)子（的列確定了信息位的校驗(yàn)子（可任意確定，各列不同，且須與可任意確定，各列不同，且須與I中中的列不同的列不同），），I確定了監(jiān)督位的校驗(yàn)子確定了監(jiān)督位的校

24、驗(yàn)子線性分組碼線性分組碼n 利用矩陣構(gòu)造線性系統(tǒng)分組碼利用矩陣構(gòu)造線性系統(tǒng)分組碼第二步：由監(jiān)督矩陣得到生成矩陣第二步：由監(jiān)督矩陣得到生成矩陣第三步：由生成矩陣可得許用碼組第三步：由生成矩陣可得許用碼組線性分組碼線性分組碼n 線性分組碼的分析線性分組碼的分析（n. k）中）中n和和k如何確定如何確定只考慮糾正一位錯(cuò)誤只考慮糾正一位錯(cuò)誤線性分組碼的基本思想：用校正子指示錯(cuò)誤位置線性分組碼的基本思想：用校正子指示錯(cuò)誤位置校正子有校正子有r位，可以指示的錯(cuò)誤圖樣位，可以指示的錯(cuò)誤圖樣線性分組碼碼長(zhǎng)為線性分組碼碼長(zhǎng)為n位，如果只考慮一位錯(cuò)誤，共位，如果只考慮一位錯(cuò)誤，共有錯(cuò)誤情況有錯(cuò)誤情況n種，還需要一

25、種指示用于表征沒(méi)出錯(cuò)種，還需要一種指示用于表征沒(méi)出錯(cuò)，共需指示，共需指示n+1種情況種情況能夠糾正能夠糾正1位錯(cuò)誤需要滿足的關(guān)系式位錯(cuò)誤需要滿足的關(guān)系式等號(hào)成立時(shí)的特殊情況的碼稱為漢明碼等號(hào)成立時(shí)的特殊情況的碼稱為漢明碼線性分組碼線性分組碼n 線性分組碼的分析線性分組碼的分析考慮糾正考慮糾正t位錯(cuò)誤位錯(cuò)誤按照同樣的分析，可得到按照同樣的分析，可得到信息碼元的位數(shù)（信息碼元的位數(shù)（d為最小碼距）為最小碼距）線性分組碼存在的界線性分組碼存在的界吉爾伯特界吉爾伯特界漢明界，r的最小值普洛特金界，k的最大值吉爾伯特界，r的最大值線性分組碼線性分組碼n 漢明碼（漢明碼（hanming）能糾正單個(gè)錯(cuò)誤的線

26、性分組碼能糾正單個(gè)錯(cuò)誤的線性分組碼碼長(zhǎng)碼長(zhǎng)監(jiān)督碼位監(jiān)督碼位信息碼位信息碼位最小碼距最小碼距碼率碼率循環(huán)碼循環(huán)碼n 概念概念是一種線性分組碼，通常是系統(tǒng)碼是一種線性分組碼，通常是系統(tǒng)碼具有循環(huán)性質(zhì)，即需用碼組經(jīng)過(guò)若干位的循環(huán)移位后仍具有循環(huán)性質(zhì)，即需用碼組經(jīng)過(guò)若干位的循環(huán)移位后仍未需用碼組未需用碼組實(shí)現(xiàn)簡(jiǎn)單，可用帶反饋的移位寄存器實(shí)現(xiàn)實(shí)現(xiàn)簡(jiǎn)單，可用帶反饋的移位寄存器實(shí)現(xiàn)糾錯(cuò)能力強(qiáng)，可糾正突發(fā)錯(cuò)誤糾錯(cuò)能力強(qiáng)，可糾正突發(fā)錯(cuò)誤循環(huán)碼的數(shù)學(xué)描述方式循環(huán)碼的數(shù)學(xué)描述方式多項(xiàng)式多項(xiàng)式矩陣矩陣二元域上的預(yù)算：加法和乘法，注意與普通的數(shù)學(xué)二元域上的預(yù)算：加法和乘法，注意與普通的數(shù)學(xué)上的多項(xiàng)式運(yùn)算的不同上的多項(xiàng)式

27、運(yùn)算的不同循環(huán)碼循環(huán)碼n 循環(huán)碼的循環(huán)性循環(huán)碼的循環(huán)性循環(huán)碼的多項(xiàng)式表示循環(huán)碼的多項(xiàng)式表示循環(huán)碼循環(huán)碼n 循環(huán)碼的循環(huán)性循環(huán)碼的循環(huán)性左移一位左移一位與循環(huán)碼的多項(xiàng)式表示相比較，上式顯然不能表示一個(gè)與循環(huán)碼的多項(xiàng)式表示相比較，上式顯然不能表示一個(gè)循環(huán)碼組，對(duì)這一表達(dá)式進(jìn)行變形循環(huán)碼組，對(duì)這一表達(dá)式進(jìn)行變形余式可以表示一個(gè)新的碼字，是循環(huán)左移一位形成的新的碼字余式可以表示一個(gè)新的碼字，是循環(huán)左移一位形成的新的碼字循環(huán)碼循環(huán)碼n 循環(huán)碼的循環(huán)性循環(huán)碼的循環(huán)性左移左移k位的情況位的情況按循環(huán)碼的循環(huán)特性，新的碼字可以描述為按循環(huán)碼的循環(huán)特性，新的碼字可以描述為按照二指域的多項(xiàng)式計(jì)算驗(yàn)證上式按照二指域

28、的多項(xiàng)式計(jì)算驗(yàn)證上式循環(huán)碼循環(huán)碼n 循環(huán)碼的循環(huán)性循環(huán)碼的循環(huán)性循環(huán)性的一般描述循環(huán)性的一般描述n 循環(huán)碼的構(gòu)造循環(huán)碼的構(gòu)造信息碼組的多項(xiàng)式表示為信息碼組的多項(xiàng)式表示為M(D)，則循環(huán)碼編碼后的碼，則循環(huán)碼編碼后的碼組多項(xiàng)式為組多項(xiàng)式為g(D)為生成多項(xiàng)式為生成多項(xiàng)式g(D)是是n-k階多項(xiàng)式階多項(xiàng)式G(D)能被能被 整除整除循環(huán)碼循環(huán)碼n 循環(huán)碼的構(gòu)造循環(huán)碼的構(gòu)造生成多項(xiàng)式生成多項(xiàng)式每一個(gè)每一個(gè)g(D)對(duì)應(yīng)一個(gè)循環(huán)碼，階數(shù)低于對(duì)應(yīng)一個(gè)循環(huán)碼，階數(shù)低于n且能被且能被g(D)整除的一組多項(xiàng)式就構(gòu)成一個(gè)循環(huán)碼整除的一組多項(xiàng)式就構(gòu)成一個(gè)循環(huán)碼循環(huán)碼（循環(huán)碼（n,k)的構(gòu)造：給定的構(gòu)造：給定g(D)，

29、根據(jù)，根據(jù)g(D)的階數(shù)確的階數(shù)確定定M(D)的最高階數(shù)，所有的最高階數(shù)，所有M(D)和和g(D)相乘得到的就相乘得到的就是循環(huán)碼的許用碼組是循環(huán)碼的許用碼組g(D)尋找：尋找： 的因式的因式保證循環(huán)性保證循環(huán)性循環(huán)碼循環(huán)碼n 循環(huán)碼的構(gòu)造循環(huán)碼的構(gòu)造一個(gè)例子一個(gè)例子循環(huán)碼循環(huán)碼n 循環(huán)碼的生成矩陣和監(jiān)督矩陣循環(huán)碼的生成矩陣和監(jiān)督矩陣非系統(tǒng)碼！非系統(tǒng)碼！如何變成系如何變成系統(tǒng)碼？統(tǒng)碼？循環(huán)碼循環(huán)碼n 循環(huán)碼的生成矩陣和監(jiān)督矩陣循環(huán)碼的生成矩陣和監(jiān)督矩陣系統(tǒng)循環(huán)碼的矩陣形式應(yīng)該什么樣子？系統(tǒng)循環(huán)碼的矩陣形式應(yīng)該什么樣子？G(D)如何構(gòu)造，保證循環(huán)性？如何構(gòu)造，保證循環(huán)性？循環(huán)碼循環(huán)碼n 循環(huán)碼的

30、生成矩陣和監(jiān)督矩陣循環(huán)碼的生成矩陣和監(jiān)督矩陣考慮系統(tǒng)碼的碼多項(xiàng)式考慮系統(tǒng)碼的碼多項(xiàng)式如果生成多項(xiàng)式為如果生成多項(xiàng)式為g(D)，由循環(huán)碼的生成規(guī)則可知，由循環(huán)碼的生成規(guī)則可知g(D)和和r(D)的階數(shù)相同，則按照二值域上的運(yùn)算規(guī)則有的階數(shù)相同，則按照二值域上的運(yùn)算規(guī)則有考慮考慮k個(gè)特殊的信息碼字，即只有一個(gè)個(gè)特殊的信息碼字，即只有一個(gè)1的的k個(gè)特殊碼字個(gè)特殊碼字有對(duì)應(yīng)的監(jiān)督碼多項(xiàng)式有對(duì)應(yīng)的監(jiān)督碼多項(xiàng)式由此，生成矩陣的每行對(duì)應(yīng)的碼多項(xiàng)式由此，生成矩陣的每行對(duì)應(yīng)的碼多項(xiàng)式就是我們希望的！就是我們希望的！循環(huán)碼循環(huán)碼n 循環(huán)碼的生成矩陣和監(jiān)督矩陣循環(huán)碼的生成矩陣和監(jiān)督矩陣總結(jié)系統(tǒng)碼的生成矩陣總結(jié)系統(tǒng)碼

31、的生成矩陣根據(jù)根據(jù)g(D)求各行求各行r(D);由各行由各行r(D)，根據(jù)標(biāo)準(zhǔn)形式寫出生成矩陣，根據(jù)標(biāo)準(zhǔn)形式寫出生成矩陣系統(tǒng)碼的監(jiān)督矩陣系統(tǒng)碼的監(jiān)督矩陣循環(huán)碼循環(huán)碼n 系統(tǒng)循環(huán)碼的編碼器系統(tǒng)循環(huán)碼的編碼器系統(tǒng)循環(huán)碼的碼多項(xiàng)式系統(tǒng)循環(huán)碼的碼多項(xiàng)式只需要求出只需要求出r(D)系統(tǒng)循環(huán)碼的編碼可以采用多項(xiàng)式長(zhǎng)除的方法，利用線系統(tǒng)循環(huán)碼的編碼可以采用多項(xiàng)式長(zhǎng)除的方法，利用線性反饋移位寄存器實(shí)現(xiàn)性反饋移位寄存器實(shí)現(xiàn)循環(huán)碼循環(huán)碼n 循環(huán)碼的譯碼循環(huán)碼的譯碼定義誤差多項(xiàng)式定義誤差多項(xiàng)式校正子的定義和計(jì)算校正子的定義和計(jì)算和編碼一樣，可用和編碼一樣，可用反饋移位寄存器反饋移位寄存器循環(huán)碼循環(huán)碼n 循環(huán)碼的譯碼

32、循環(huán)碼的譯碼由校正子確定錯(cuò)誤圖樣由校正子確定錯(cuò)誤圖樣例如：對(duì)于例如：對(duì)于1位錯(cuò)誤，如錯(cuò)誤在第位錯(cuò)誤，如錯(cuò)誤在第i位，則校正子為位，則校正子為譯碼結(jié)果譯碼結(jié)果循環(huán)碼循環(huán)碼n 循環(huán)碼的譯碼循環(huán)碼的譯碼BCH碼碼n 上述循環(huán)碼有一個(gè)問(wèn)題沒(méi)有講？上述循環(huán)碼有一個(gè)問(wèn)題沒(méi)有講？循環(huán)碼的碼距循環(huán)碼的碼距循環(huán)碼是線性分組碼，線性分組碼的碼距的求解方循環(huán)碼是線性分組碼，線性分組碼的碼距的求解方法可以直接應(yīng)用法可以直接應(yīng)用碼距和生成多項(xiàng)式的關(guān)系如何？碼距和生成多項(xiàng)式的關(guān)系如何？確定碼距后能否快速確定生成多項(xiàng)式？確定碼距后能否快速確定生成多項(xiàng)式？n BCH碼的特點(diǎn)碼的特點(diǎn)BCH碼是循環(huán)碼碼是循環(huán)碼具有糾多個(gè)隨機(jī)錯(cuò)誤

33、的能力具有糾多個(gè)隨機(jī)錯(cuò)誤的能力 構(gòu)造容易構(gòu)造容易由碼的最小距離，可以很快得到碼的生成多項(xiàng)式由碼的最小距離，可以很快得到碼的生成多項(xiàng)式BCH碼碼n 本原本原BCH碼碼碼長(zhǎng)為碼長(zhǎng)為生成多項(xiàng)式生成多項(xiàng)式最小碼距最小碼距 LCM：最小公倍數(shù)：最小多項(xiàng)式由碼長(zhǎng)及碼距可快速確定生成多項(xiàng)式由碼長(zhǎng)及碼距可快速確定生成多項(xiàng)式線性分組碼的擴(kuò)展與縮短線性分組碼的擴(kuò)展與縮短n 線性分組碼的擴(kuò)展線性分組碼的擴(kuò)展在原有碼組基礎(chǔ)上增加一位校驗(yàn)位，對(duì)所有碼字進(jìn)行校在原有碼組基礎(chǔ)上增加一位校驗(yàn)位，對(duì)所有碼字進(jìn)行校驗(yàn)，碼距增加驗(yàn)，碼距增加1擴(kuò)展線性分組碼的監(jiān)督矩陣擴(kuò)展線性分組碼的監(jiān)督矩陣擴(kuò)展循環(huán)碼的生成多項(xiàng)式擴(kuò)展循環(huán)碼的生成多項(xiàng)

34、式線性分組碼的擴(kuò)展與縮短線性分組碼的擴(kuò)展與縮短n 縮短線性分組碼縮短線性分組碼(n,k)線性分組碼的碼長(zhǎng)和信息位同時(shí)縮短線性分組碼的碼長(zhǎng)和信息位同時(shí)縮短s位，形成新位，形成新的的(n-s,k-s)分組碼為縮短線性分組碼分組碼為縮短線性分組碼縮短線性分組碼的監(jiān)督矩陣：去掉元監(jiān)督矩陣的前縮短線性分組碼的監(jiān)督矩陣：去掉元監(jiān)督矩陣的前s列列即可即可交織編碼交織編碼n 為什么要采用交織？為什么要采用交織？前述的線性分組碼只能糾正零散隨機(jī)錯(cuò)誤前述的線性分組碼只能糾正零散隨機(jī)錯(cuò)誤通信系統(tǒng)中往往存在不可抗拒的突發(fā)錯(cuò)誤通信系統(tǒng)中往往存在不可抗拒的突發(fā)錯(cuò)誤無(wú)線信道的衰落引起的誤碼無(wú)線信道的衰落引起的誤碼突發(fā)強(qiáng)干擾

35、引起的錯(cuò)誤突發(fā)強(qiáng)干擾引起的錯(cuò)誤如何對(duì)抗突發(fā)的的錯(cuò)誤如何對(duì)抗突發(fā)的的錯(cuò)誤思想：將突發(fā)錯(cuò)誤化解為零散的錯(cuò)誤思想：將突發(fā)錯(cuò)誤化解為零散的錯(cuò)誤交織編碼交織編碼交織編碼交織編碼n 交織的基本思想交織的基本思想交織編碼交織編碼n 交織編碼的基本原理交織編碼的基本原理為了對(duì)付突發(fā)的信道差錯(cuò)，交織器改變發(fā)送碼元的時(shí)間為了對(duì)付突發(fā)的信道差錯(cuò)，交織器改變發(fā)送碼元的時(shí)間順序順序?qū)⒃鞠噜彽拇a元在時(shí)間上的距離最大化將原本相鄰的碼元在時(shí)間上的距離最大化時(shí)間上相鄰的突發(fā)錯(cuò)誤屬于不同的碼組，可分別糾錯(cuò)時(shí)間上相鄰的突發(fā)錯(cuò)誤屬于不同的碼組，可分別糾錯(cuò)交織編碼交織編碼n 交織碼的糾錯(cuò)能力交織碼的糾錯(cuò)能力交織碼的結(jié)構(gòu)交織碼的結(jié)構(gòu)碼組方陣碼組方陣行：分組碼的一個(gè)碼組行：分組碼的一個(gè)碼組列：交織的深度列：交織的深度i糾錯(cuò)能力糾錯(cuò)能力分組碼：糾正分組碼：糾正t個(gè)隨機(jī)錯(cuò)誤個(gè)隨機(jī)錯(cuò)誤交織碼：糾正交織碼：糾正tXi個(gè)突個(gè)突發(fā)錯(cuò)誤發(fā)錯(cuò)誤分組碼：糾正分組碼：糾正b個(gè)突發(fā)錯(cuò)誤個(gè)突發(fā)錯(cuò)誤交織碼：糾正交織碼：糾正bXi個(gè)個(gè)突發(fā)錯(cuò)誤突發(fā)錯(cuò)誤交織編碼交織編碼n 交織碼的解碼交織碼的解碼豎著寫入，橫著讀出豎著寫入，橫著讀出交織的代價(jià)：延時(shí)增大交織的代價(jià)