第七講差錯控制編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、的多項式計算驗證上式循環(huán)碼循環(huán)碼n 循環(huán)碼的循環(huán)性循環(huán)碼的循環(huán)性循環(huán)性的一般描述循環(huán)性的一般描述n 循環(huán)碼的構造循環(huán)碼的構造信息碼組的多項式表示為信息碼組的多項式表示為M(D)，則循環(huán)碼編碼后的碼，則循環(huán)碼編碼后的碼組多項式為組多項式為g(D)為生成多項式為生成多項式g(D)是是n-k階多項式階多項式G(D)能被能被 整除整除循環(huán)碼循環(huán)碼n 循環(huán)碼的構造循環(huán)碼的構造生成多項式生成多項式每一個每一個g(D)對應一個循環(huán)碼，階數(shù)低于對應一個循環(huán)碼，階數(shù)低于n且能被且能被g(D)整除的一組多項式就構成一個循環(huán)碼整除的一組多項式就構成一個循環(huán)碼循環(huán)碼（循環(huán)碼（n,k)的構造：給定的構造：給定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)碼的構造循環(huán)碼的構造一個例子一個例子循環(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)碼的矩陣形式應該什么樣子？系統(tǒng)循環(huán)碼的矩陣形式應該什么樣子？G(D)如何構造，保證循環(huán)性？如何構造，保證循環(huán)性？循環(huán)碼循環(huán)碼n 循環(huán)碼的

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

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

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

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

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

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