第七講差錯控制編碼

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

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

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

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

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

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

7、編碼n 重要性重要性信息系統(tǒng)不可或缺的重要技術(shù)信息系統(tǒng)不可或缺的重要技術(shù)移動通信移動通信深空通信與探測深空通信與探測可靠計(jì)算可靠計(jì)算存儲設(shè)備存儲設(shè)備信道編碼的分類信道編碼的分類n 按功能分按功能分檢錯碼：僅能檢錯檢錯碼：僅能檢錯 糾錯碼：僅能糾錯糾錯碼：僅能糾錯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 按照信息碼元在編碼后是否保持原來形式按照信息碼元在編碼后是否保持原來形式系統(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、碼的錯誤概元速率），則一定存在一種編碼方式，使編碼的錯誤概率隨著碼長率隨著碼長n的增加將按指數(shù)下降到任意小的值的增加將按指數(shù)下降到任意小的值兩個(gè)結(jié)論兩個(gè)結(jié)論如碼長及發(fā)送信息速率一定，可以通過增大信道容如碼長及發(fā)送信息速率一定，可以通過增大信道容量，使錯誤概率減小量，使錯誤概率減小如在信道容量及發(fā)送信息速率一定，可以通過增加如在信道容量及發(fā)送信息速率一定，可以通過增加碼長，使錯誤概率減小碼長，使錯誤概率減小給出了努力的方向，但怎么做？信道編碼的基本原理信道編碼的基本原理n 看一個(gè)例子看一個(gè)例子如用三位二進(jìn)制編碼來代表八個(gè)字母如用三位二進(jìn)制編碼來代表八個(gè)字母000 A100E001 B101F01

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

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

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

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

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

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

16、 概念概念編碼后的碼元序列每編碼后的碼元序列每n為分為一組，其中為分為一組，其中k個(gè)信息碼元，個(gè)信息碼元，r個(gè)附加的監(jiān)督碼元，而且監(jiān)督碼元僅與本組的信息碼個(gè)附加的監(jiān)督碼元，而且監(jiān)督碼元僅與本組的信息碼元有關(guān)，而與其他碼組的的信息碼元無關(guān)元有關(guān)，而與其他碼組的的信息碼元無關(guān)二進(jìn)制序列分段，每段二進(jìn)制序列分段，每段k個(gè)，針對每段按照一定規(guī)則個(gè)，針對每段按照一定規(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)電路簡單，復(fù)雜度低實(shí)現(xiàn)電路簡單，復(fù)雜度低線性分組碼線性分組碼信息碼元和監(jiān)督碼元之間的關(guān)系可以用線性方程表信息碼元和監(jiān)

17、督碼元之間的關(guān)系可以用線性方程表示示分組碼分組碼n 檢錯分組碼的例子檢錯分組碼的例子奇偶監(jiān)督碼奇偶監(jiān)督碼偶監(jiān)督偶監(jiān)督奇監(jiān)督奇監(jiān)督如果以上關(guān)系被破壞，則出現(xiàn)錯誤，因此能檢查出如果以上關(guān)系被破壞，則出現(xiàn)錯誤，因此能檢查出奇數(shù)個(gè)錯誤，但不能檢測偶數(shù)個(gè)錯誤。奇數(shù)個(gè)錯誤，但不能檢測偶數(shù)個(gè)錯誤。最小碼距為最小碼距為 dmin=2檢錯能力不高檢錯能力不高分組碼分組碼 水平奇偶監(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è)錯誤，而且在不增加冗余度時(shí)，不僅能發(fā)現(xiàn)某一行上奇數(shù)個(gè)錯誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯誤也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯誤沒有增加冗余度，但通過增加碼長提高了檢錯能力沒有增加冗余度，但通過增加碼長提高了檢錯能力最小碼距最小碼距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位錯誤位錯誤1位錯誤可能出現(xiàn)在位錯誤可能出現(xiàn)在7個(gè)碼位中的任何一位上，錯誤的個(gè)碼位中的任何一位上，錯誤的情形有情形有7種，加上無錯，共種，加上無錯，共8種狀態(tài)需要知識種狀態(tài)需要知識構(gòu)造構(gòu)造3位校正子，共位校正子，共8種組合，正好可以指示種組合，正好可以指示7種錯誤種錯誤和無錯的狀態(tài)和無錯的狀態(tài)線性分組碼線性分組碼 任意設(shè)計(jì)一種錯誤位置和校正子的對應(yīng)關(guān)系任意設(shè)計(jì)一種錯誤位置和校正子的對應(yīng)關(guān)系 由上表得到校正子與各碼元關(guān)系由上表得到校正子與各碼元關(guān)系線性分組碼線性分組碼由校正子關(guān)系確定編碼方程，保證無誤碼及校正子為由校正子關(guān)系確定編碼方程，

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

21、碼過程可以看成信息序列與一個(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)分組碼的矩陣表示檢錯的矩陣表示檢錯的矩陣表示出錯的條件出錯的條件監(jiān)督矩陣監(jiān)督矩陣線性分組碼線性分組碼n 線性系統(tǒng)分組碼的矩陣表示線性系統(tǒng)分組碼的矩陣表示校正子計(jì)算的矩陣表示校正子計(jì)算的矩陣表示接收信號的表示接收

22、信號的表示校正子的計(jì)算校正子的計(jì)算校正子與錯誤圖樣有確定的關(guān)系校正子與錯誤圖樣有確定的關(guān)系糾錯：根據(jù)錯誤圖樣與校正子的關(guān)系確定錯誤位置糾錯：根據(jù)錯誤圖樣與校正子的關(guān)系確定錯誤位置進(jìn)行糾正進(jìn)行糾正線性分組碼線性分組碼n 線性系統(tǒng)分組碼的矩陣表示線性系統(tǒng)分組碼的矩陣表示校正子與誤碼位置的關(guān)系校正子與誤碼位置的關(guān)系對于糾對于糾1比特錯誤的校正子（以書比特錯誤的校正子（以書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è)問題：先構(gòu)造生成矩陣還是監(jiān)督矩陣？第一個(gè)問題：先構(gòu)造生成矩陣還是監(jiān)督矩陣？回顧第一個(gè)例子，監(jiān)督矩陣確定了如何糾錯，是構(gòu)造者自己確定的回顧第一個(gè)例子，監(jiān)督矩陣確定了如何糾錯，是構(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如何確定如何確定只考慮糾正一位錯誤只考慮糾正一位錯誤線性分組碼的基本思想：用校正子指示錯誤位置線性分組碼的基本思想：用校正子指示錯誤位置校正子有校正子有r位，可以指示的錯誤圖樣位，可以指示的錯誤圖樣線性分組碼碼長為線性分組碼碼長為n位，如果只考慮一位錯誤，共位，如果只考慮一位錯誤，共有錯誤情況有錯誤情況n種，還需要一

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

26、性分組碼能糾正單個(gè)錯誤的線性分組碼碼長碼長監(jiān)督碼位監(jiān)督碼位信息碼位信息碼位最小碼距最小碼距碼率碼率循環(huán)碼循環(huán)碼n 概念概念是一種線性分組碼，通常是系統(tǒng)碼是一種線性分組碼，通常是系統(tǒng)碼具有循環(huán)性質(zhì)，即需用碼組經(jīng)過若干位的循環(huán)移位后仍具有循環(huán)性質(zhì)，即需用碼組經(jīng)過若干位的循環(huán)移位后仍未需用碼組未需用碼組實(shí)現(xiàn)簡單，可用帶反饋的移位寄存器實(shí)現(xiàn)實(shí)現(xiàn)簡單，可用帶反饋的移位寄存器實(shí)現(xiàn)糾錯能力強(qiáng)，可糾正突發(fā)錯誤糾錯能力強(qiáng)，可糾正突發(fā)錯誤循環(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)碼組，對這一表達(dá)式進(jìn)行變形循環(huán)碼組，對這一表達(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)對應(yīng)一個(gè)循環(huán)碼，階數(shù)低于對應(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è)特殊碼字有對應(yīng)的監(jiān)督碼多項(xiàng)式有對應(yīng)的監(jiān)督碼多項(xiàng)式由此，生成矩陣的每行對應(yīng)的碼多項(xiàng)式由此，生成矩陣的每行對應(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)式長除的方法，利用線系統(tǒng)循環(huán)碼的編碼可以采用多項(xià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)碼的譯碼由校正子確定錯誤圖樣由校正子確定錯誤圖樣例如：對于例如：對于1位錯誤，如錯誤在第位錯誤，如錯誤在第i位，則校正子為位，則校正子為譯碼結(jié)果譯碼結(jié)果循環(huán)碼循環(huán)碼n 循環(huán)碼的譯碼循環(huán)碼的譯碼BCH碼碼n 上述循環(huán)碼有一個(gè)問題沒有講？上述循環(huán)碼有一個(gè)問題沒有講？循環(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ī)錯誤

33、的能力具有糾多個(gè)隨機(jī)錯誤的能力 構(gòu)造容易構(gòu)造容易由碼的最小距離，可以很快得到碼的生成多項(xiàng)式由碼的最小距離，可以很快得到碼的生成多項(xiàng)式BCH碼碼n 本原本原BCH碼碼碼長為碼長為生成多項(xiàng)式生成多項(xiàng)式最小碼距最小碼距 LCM：最小公倍數(shù)：最小多項(xiàng)式由碼長及碼距可快速確定生成多項(xiàng)式由碼長及碼距可快速確定生成多項(xiàng)式線性分組碼的擴(kuò)展與縮短線性分組碼的擴(kuò)展與縮短n 線性分組碼的擴(kuò)展線性分組碼的擴(kuò)展在原有碼組基礎(chǔ)上增加一位校驗(yàn)位，對所有碼字進(jìn)行校在原有碼組基礎(chǔ)上增加一位校驗(yàn)位，對所有碼字進(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)線性分組碼的碼長和信息位同時(shí)縮短線性分組碼的碼長和信息位同時(shí)縮短s位，形成新位，形成新的的(n-s,k-s)分組碼為縮短線性分組碼分組碼為縮短線性分組碼縮短線性分組碼的監(jiān)督矩陣：去掉元監(jiān)督矩陣的前縮短線性分組碼的監(jiān)督矩陣：去掉元監(jiān)督矩陣的前s列列即可即可交織編碼交織編碼n 為什么要采用交織？為什么要采用交織？前述的線性分組碼只能糾正零散隨機(jī)錯誤前述的線性分組碼只能糾正零散隨機(jī)錯誤通信系統(tǒng)中往往存在不可抗拒的突發(fā)錯誤通信系統(tǒng)中往往存在不可抗拒的突發(fā)錯誤無線信道的衰落引起的誤碼無線信道的衰落引起的誤碼突發(fā)強(qiáng)干擾

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