第10章---信道編碼與差錯控制課件

1、1現(xiàn)代通信原理第十章第十章 信道編碼與差錯控制信道編碼與差錯控制2學(xué)習(xí)要求學(xué)習(xí)要求1. 理解差錯控制的基本概念及其原理等；理解差錯控制的基本概念及其原理等；2. 掌握信道編碼的基本原理；掌握信道編碼的基本原理；3. 了解常用檢錯碼的特性；了解常用檢錯碼的特性；4. 掌握線性分組碼的一般特性；掌握線性分組碼的一般特性；5. 掌握漢明碼以及循環(huán)碼的編譯碼及其實現(xiàn)原掌握漢明碼以及循環(huán)碼的編譯碼及其實現(xiàn)原理；理；6. 了解卷積碼的基本概念。了解卷積碼的基本概念。3差錯控制與信道編碼l概述概述l糾錯編碼的基本原理糾錯編碼的基本原理l糾錯編碼系統(tǒng)的性能糾錯編碼系統(tǒng)的性能l奇偶監(jiān)督碼奇偶監(jiān)督碼l線性分組碼線

2、性分組碼l循環(huán)碼循環(huán)碼l卷積碼卷積碼lTurbo碼和碼和LDPC碼碼4n 為什么需要信道編碼？為什么需要信道編碼？ 在數(shù)字信號的傳輸中，實際信道不是理想的，在數(shù)字信號的傳輸中，實際信道不是理想的，存在噪聲和干擾，會導(dǎo)致接收端的誤判，這樣就存在噪聲和干擾，會導(dǎo)致接收端的誤判，這樣就產(chǎn)生了差錯。產(chǎn)生了差錯。n可采取的辦法：可采取的辦法：合理設(shè)計基帶信號合理設(shè)計基帶信號選擇調(diào)制、解調(diào)方式選擇調(diào)制、解調(diào)方式采用均衡技術(shù)采用均衡技術(shù)增大發(fā)送功率增大發(fā)送功率n 仍然達(dá)不到要求，就需要信道編碼仍然達(dá)不到要求，就需要信道編碼概述概述n信道編碼：u目的：提高信號傳輸?shù)目煽啃?。u方法：增加多余比特，以發(fā)現(xiàn)或糾正錯

3、誤。 n差錯控制：包括信道編碼在內(nèi)的一切糾正錯誤手段。n產(chǎn)生錯碼的原因：u乘性干擾引起的碼間串?dāng)_u加性干擾引起的信噪比降低 n信道分類：按照加性干擾造成錯碼的統(tǒng)計特性不同劃分u隨機信道：錯碼隨機出現(xiàn)，例如由白噪聲引起的錯碼 u突發(fā)信道：錯碼相對集中出現(xiàn)，例如由脈沖干擾引起的錯碼。 u混合信道概述概述n差錯控制技術(shù)的種類：u檢錯重發(fā)：p能發(fā)現(xiàn)錯碼，但是不能確定錯碼的位置。p通信系統(tǒng)需要有雙向信道。 u前向糾錯(FEC)：利用加入的差錯控制碼元，不但能夠發(fā)現(xiàn)錯碼，還能糾正錯碼。u 反饋校驗：p將收到的碼元轉(zhuǎn)發(fā)回發(fā)送端，將它和原發(fā)送碼元比較。p缺點：需要雙向信道，傳輸效率也較低。u檢錯刪除：p在接收

4、端發(fā)現(xiàn)錯碼后，立即將其刪除。p適用在發(fā)送碼元中有大量多余度，刪除部分接收碼元不影響應(yīng)用之處。 7l信源編碼，目的是實現(xiàn)模擬信號數(shù)字化信源編碼，目的是實現(xiàn)模擬信號數(shù)字化l信道編碼，目的是提高數(shù)字通信的可靠性信道編碼，目的是提高數(shù)字通信的可靠性n 差錯率是信噪比的函數(shù)差錯率是信噪比的函數(shù)u 信道編碼，差錯控制編碼，抗干擾編碼信道編碼，差錯控制編碼，抗干擾編碼l信道編碼過程：信道編碼過程：n信息碼元序列監(jiān)督碼元信息碼元序列監(jiān)督碼元編碼碼組編碼碼組 l信道譯碼過程：信道譯碼過程：n編碼碼組編碼碼組檢錯或糾錯檢錯或糾錯信息碼元序列信息碼元序列概述概述8n信道編碼的構(gòu)造信道編碼的構(gòu)造u在發(fā)送端，在待發(fā)送的

5、信息序列中加入一些多在發(fā)送端，在待發(fā)送的信息序列中加入一些多余的碼元（監(jiān)督碼元），這些監(jiān)督碼元和信息余的碼元（監(jiān)督碼元），這些監(jiān)督碼元和信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)，即滿足碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)，即滿足一定的約束關(guān)系。一定的約束關(guān)系。u在接收端，按既定的規(guī)則檢驗信息碼元與監(jiān)在接收端，按既定的規(guī)則檢驗信息碼元與監(jiān)督碼元之間的約束關(guān)系。約束關(guān)系被破壞就意督碼元之間的約束關(guān)系。約束關(guān)系被破壞就意味著傳輸中有差錯（檢錯）；借助于約束關(guān)味著傳輸中有差錯（檢錯）；借助于約束關(guān)系甚至還可以糾正錯誤（糾錯）。系甚至還可以糾正錯誤（糾錯）。概述概述n編碼序列的參數(shù)un 編碼序列中總碼元數(shù)量uk

6、 編碼序列中信息碼元數(shù)量ur 編碼序列中差錯控制碼元數(shù)量（差錯控制碼元，以后稱為監(jiān)督碼元或監(jiān)督位 ）uk/n 碼率u(n - k) / n = r / n 冗余度概述概述10l常用的常用的差錯控制方式差錯控制方式有三種：有三種：n前向糾錯（FEC:forward error correction）u發(fā)送能糾錯的碼，在譯碼時自動發(fā)現(xiàn)并糾正傳輸中的錯誤u只需正向信道，實時性好u編譯碼設(shè)備復(fù)雜，適合單向信道和一發(fā)多收系統(tǒng)n檢錯重發(fā)（ARQ:automatic repeat request）u發(fā)送端發(fā)出能夠檢錯的碼，接收端檢驗，接收端發(fā)出反饋應(yīng)答信號，發(fā)送端重新傳輸 直到正確接收為止u工作原理簡單，正

7、向信道+反向信道，傳輸效率低n混合糾錯（HEC:hybrid error correction）u前向糾錯方式和檢錯重發(fā)方式的結(jié)合與折衷u外層先采用前向糾錯，當(dāng)前向糾錯不能解決問題時，內(nèi)層再采用檢錯重發(fā)。概述概述n自動要求重發(fā)(ARQ)系統(tǒng)u停止等待ARQ系統(tǒng) u拉后ARQ系統(tǒng) u選擇重發(fā)ARQ系統(tǒng) uARQ和前向糾錯比較：p優(yōu)點監(jiān)督碼元較少，即碼率較高 檢錯的計算復(fù)雜度較低能適應(yīng)不同特性的信道 p缺點需要雙向信道。不適用于一點到多點的通信系統(tǒng)或廣播系統(tǒng)。傳輸效率降低，可能因反復(fù)重發(fā)而造成事實上的通信中斷。 13糾錯編碼的基本原理l差錯控制編碼的分類差錯控制編碼的分類l分組碼舉例分組碼舉例l分

8、組碼概念分組碼概念l編碼的糾檢錯能力編碼的糾檢錯能力14 在編碼前先把信息序列分為在編碼前先把信息序列分為k位一組（稱為位一組（稱為信息信息碼碼），然后附加），然后附加m位位監(jiān)督碼監(jiān)督碼，形成，形成n = k + m位的碼組。位的碼組。1、按信息碼和附加監(jiān)督碼間的檢驗關(guān)系、按信息碼和附加監(jiān)督碼間的檢驗關(guān)系n線性碼：監(jiān)督碼是信息碼的線性組合n非線性碼：監(jiān)督碼是信息碼的非線性組合2、按信息碼和監(jiān)督碼間的約束方式、按信息碼和監(jiān)督碼間的約束方式n分組碼：監(jiān)督碼僅與本碼組的信息碼有關(guān)n卷積碼：監(jiān)督碼與之前的若干個信息碼組的碼元有約束關(guān)系差錯控制編碼的分類差錯控制編碼的分類n分組碼舉例u設(shè)：有一種由3個二

9、進(jìn)制碼元構(gòu)成的編碼，它共有23 = 8種不同的可能碼組：000 晴 001 云 010 陰 011 雨100 雪 101 霜 110 霧 111 雹 這時，若一個碼組中發(fā)生錯碼，則將收到錯誤信息。 u若在此8種碼組中僅允許使用4種來傳送天氣，例如：令000 晴 011 云 101 陰 110 雨 為許用碼組，其他4種不允許使用，稱為禁用碼組。 這時，接收端有可能發(fā)現(xiàn)（檢測到）碼組中的一個錯碼。p這種編碼只能檢測錯碼，不能糾正錯碼。 u若規(guī)定只許用兩個碼組：例如000 晴 111 雨就能檢測兩個以下錯碼，或糾正一個錯碼。 n分組碼概念u分組碼 信息位 監(jiān)督位u分組碼符號：(n, k) 其中，n

10、碼組總長度， k 信息碼元數(shù)目。 r = n k 監(jiān)督碼元數(shù)目。右表中的碼組為(3, 2)碼。 u分組碼的一般結(jié)構(gòu)：u分組碼的參數(shù)：p碼重：碼組內(nèi)“1”的個數(shù)p碼距：兩碼組中對應(yīng)位取值不同的位數(shù)，又稱漢明距離 p最小碼距(d0) ：各碼組間的最小距離u碼距的幾何意義：以n = 3的編碼為例 u一般而言，碼距是 n 維空間中單位正多面體頂點之間的漢明距離。u一種編碼的糾檢錯能力：決定于最小碼距d0的值。 p為了能檢測e個錯碼，要求最小碼距p為了能糾正 t 個錯碼，要求最小碼距 p為了能糾正t個錯碼，同時檢測e個錯碼，要求最小碼距糾檢結(jié)合工作方式：當(dāng)錯碼數(shù)量少時，系統(tǒng)按前向糾錯方式工作，以節(jié)省重發(fā)

11、時間，提高傳輸效率；當(dāng)錯碼數(shù)量多時，系統(tǒng)按反饋重發(fā)的糾錯方式工作，以降低系統(tǒng)的總誤碼率。 20糾錯編碼系統(tǒng)的性能l誤碼率性能和帶寬的關(guān)系誤碼率性能和帶寬的關(guān)系l功率和帶寬的關(guān)系功率和帶寬的關(guān)系l傳輸速率和帶寬的關(guān)系傳輸速率和帶寬的關(guān)系l編碼增益編碼增益 采用編碼降低誤碼率 所付出的代價是 帶寬的增大。誤碼率性能和帶寬的關(guān)系誤碼率性能和帶寬的關(guān)系采用編碼以節(jié)省功率，并保持誤碼率不變，付出的代價也是帶寬增大。 功率和帶寬的關(guān)系功率和帶寬的關(guān)系對于給定的傳輸系統(tǒng)，其傳輸速率和對于給定的傳輸系統(tǒng)，其傳輸速率和Eb/n0的關(guān)系：的關(guān)系：式中，RB 碼元速率。 提高傳輸速率，采用編碼以保持誤碼率不變；付出

12、的代價仍是帶寬增大。傳輸速率和帶寬的關(guān)系傳輸速率和帶寬的關(guān)系定義：在保持誤碼率恒定條件下，采用糾錯編碼所節(jié)省的信噪比Eb/n0稱為編碼增益： 式中，(Eb/n0)u 未編碼時的信噪比(dB)； (Eb/n0)c 編碼后所需的信噪比(dB)。編碼增益編碼增益25奇偶監(jiān)督碼l一維奇偶監(jiān)督碼一維奇偶監(jiān)督碼l二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼l重復(fù)碼（補充）重復(fù)碼（補充）l恒比碼（補充）恒比碼（補充）l正反碼（補充）正反碼（補充）n奇偶監(jiān)督碼 分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩類。n在奇偶監(jiān)督碼中，監(jiān)督位只有1位，故碼率等于k/(k+1)。n偶數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中“1”的個數(shù)為偶數(shù)：式中，a0為監(jiān)督位，其

13、他位為信息位。n奇數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中“1”的個數(shù)為奇數(shù)：一維奇偶監(jiān)督碼一維奇偶監(jiān)督碼27一般情況下：一般情況下：n譯碼方法(與編碼方法相對應(yīng))l不滿足校驗關(guān)系，傳輸一定錯誤！不滿足校驗關(guān)系，傳輸一定錯誤！l奇偶校驗只能發(fā)現(xiàn)奇數(shù)個奇偶校驗只能發(fā)現(xiàn)奇數(shù)個(單個單個)錯誤，不能錯誤，不能 檢測出偶數(shù)個錯誤。檢測出偶數(shù)個錯誤。n編碼方法簡單且實用性強，適用于檢測隨機零星錯碼l滿足校驗關(guān)系，傳輸一定準(zhǔn)確嗎？滿足校驗關(guān)系，傳輸一定準(zhǔn)確嗎？一維奇偶監(jiān)督碼一維奇偶監(jiān)督碼n檢錯能力 能夠檢測奇數(shù)個錯碼。 u設(shè)：碼組長度為n， 碼組中各個錯碼的發(fā)生是獨立的和等概率的， 則在一個碼組中出現(xiàn) j 個錯碼的概

14、率為 式中， 為在n個碼元中有j個錯碼的組合數(shù)。u奇偶監(jiān)督碼不能檢測碼組中出現(xiàn)的偶數(shù)個錯碼，所以在一個碼組中有錯碼而不能檢測的概率等于: 當(dāng)n為偶數(shù)時 當(dāng)n為奇數(shù)時 u例 右表中的編碼是偶數(shù)監(jiān)督碼。設(shè)信道的誤碼率為10-4，錯碼的出現(xiàn)是獨立的。試計算其不能檢測的誤碼率。將給定條件代入式計算得出由計算結(jié)果可見，此編碼可以將誤碼率從10-4降低到10-8量級。效果非常明顯。一維奇偶監(jiān)督碼一維奇偶監(jiān)督碼30l將奇偶校驗碼的若干碼組排列成矩陣將奇偶校驗碼的若干碼組排列成矩陣l每一碼組寫成一行每一碼組寫成一行nm個碼組m行nm個監(jiān)督位構(gòu)成了一監(jiān)督位列l(wèi)按列的方向增加第二維校驗位按列的方向增加第二維校驗位

15、nn個監(jiān)督位構(gòu)成了一監(jiān)督位行maaa02010 021cccnn012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼u碼率等于u有可能檢測偶數(shù)個錯碼u適合檢測突發(fā)錯碼 u能夠糾正部分錯碼 二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼32 (3，1)重復(fù)碼兩個碼字為重復(fù)碼兩個碼字為000和和111，其最小碼距為，其最小碼距為3； (n，1)重復(fù)碼也只有全重復(fù)碼也只有全0碼和全碼和全1碼兩個碼字，其最小碼碼兩個碼字，其最小碼距為距為n， 卻有卻有2n-2個禁用碼組，隨著碼長的增大，其冗余也變得個禁用碼組，隨著碼長的增大，其冗余也變得很

16、大；很大； 該碼隨碼長增加，具有很強的糾檢錯能力，該碼隨碼長增加，具有很強的糾檢錯能力， 但其編碼效率的急劇下降；但其編碼效率的急劇下降；重復(fù)碼并不是一種優(yōu)秀的編碼方案，重復(fù)碼并不是一種優(yōu)秀的編碼方案， 僅用于速率很低的數(shù)據(jù)通信系統(tǒng)中。僅用于速率很低的數(shù)據(jù)通信系統(tǒng)中。重復(fù)碼只有一位信息碼元，監(jiān)督碼元是信息碼元的重復(fù)，重復(fù)碼只有一位信息碼元，監(jiān)督碼元是信息碼元的重復(fù)，所以僅有兩個碼字；所以僅有兩個碼字；重復(fù)碼重復(fù)碼33 從固定碼長的碼組中選擇那些從固定碼長的碼組中選擇那些1和和0的比例的比例恒定的碼組作為許用碼組，如五單位保護(hù)電碼等。恒定的碼組作為許用碼組，如五單位保護(hù)電碼等。 目前我國電傳通信

17、中普遍采用目前我國電傳通信中普遍采用3：2碼，碼， 又稱又稱5中取中取3碼。碼。 國際上通用的國際上通用的ARQ電報通信系統(tǒng)中，電報通信系統(tǒng)中， 采用采用7中取中取3碼。碼。 恒比碼恒比碼34該碼型多用于該碼型多用于10單位碼的前向糾錯設(shè)備中，可以糾正單位碼的前向糾錯設(shè)備中，可以糾正一位錯誤，發(fā)現(xiàn)全部兩個以下的錯誤，以及大部分兩個以一位錯誤，發(fā)現(xiàn)全部兩個以下的錯誤，以及大部分兩個以上的錯誤，其本質(zhì)就是五單位碼的重復(fù)；上的錯誤，其本質(zhì)就是五單位碼的重復(fù)； 編碼規(guī)則編碼規(guī)則信息碼組中信息碼組中1的數(shù)目為奇數(shù)時，監(jiān)督碼是信息碼的重復(fù)的數(shù)目為奇數(shù)時，監(jiān)督碼是信息碼的重復(fù)即正碼；即正碼； 信息碼組中信息

18、碼組中1的數(shù)目為偶數(shù)時，監(jiān)督碼是信息碼的的數(shù)目為偶數(shù)時，監(jiān)督碼是信息碼的反碼。反碼。 譯碼方法譯碼方法首先將收到的碼字重的信息位和監(jiān)督位按對應(yīng)位作模首先將收到的碼字重的信息位和監(jiān)督位按對應(yīng)位作模2運算，運算， 得到一個得到一個5位碼組，若該碼字中有奇數(shù)個位碼組，若該碼字中有奇數(shù)個1，則將，則將其作為校驗碼組，若有偶數(shù)個其作為校驗碼組，若有偶數(shù)個1，則取其反碼作為校驗碼，則取其反碼作為校驗碼組。然后，按照下表進(jìn)行糾檢錯譯碼組。然后，按照下表進(jìn)行糾檢錯譯碼正反碼正反碼35 正反碼錯誤判決表正反碼錯誤判決表 正反碼正反碼36線性分組碼l基本概念基本概念l糾錯基本原理糾錯基本原理l漢明碼漢明碼l分組碼

19、的一般原理分組碼的一般原理u代數(shù)碼 利用代數(shù)關(guān)系式產(chǎn)生監(jiān)督位的編碼u線性分組碼 代數(shù)碼的一種，其監(jiān)督位和 信息位的關(guān)系由線性代數(shù)方程決定u漢明碼 一種能夠糾正一個錯碼的線性分組碼u校正子：在偶數(shù)監(jiān)督碼中，計算實際上就是計算并檢驗S是否等于0。S稱為校正子。u監(jiān)督關(guān)系式：基本概念基本概念38l近世代數(shù)學(xué)近世代數(shù)學(xué)有限域有限域的概念：的概念：n有限個元素的集合，按規(guī)定可以進(jìn)行的代數(shù)有限個元素的集合，按規(guī)定可以進(jìn)行的代數(shù)四則運算，其運算結(jié)果仍屬于該集合中有限四則運算，其運算結(jié)果仍屬于該集合中有限的元素。的元素。n最簡單的有限域最簡單的有限域 0，1Galois域域u1+1=0、 1+0=1、 0+1

20、=1、 0+0=0 u1x1=1、 1x 0=0、 0 x0 =0、 0 x1 =0l定義線性分組碼的加法為模定義線性分組碼的加法為模2加，乘法為二加，乘法為二進(jìn)制乘法。且碼字與碼字的運算是各個相進(jìn)制乘法。且碼字與碼字的運算是各個相應(yīng)比特位上的上述二進(jìn)制運算規(guī)則。應(yīng)比特位上的上述二進(jìn)制運算規(guī)則?；靖拍罨靖拍?9u 中，中，S只有兩種取值，故只能表示只有兩種取值，故只能表示有錯和無錯，而不能進(jìn)一步指明錯碼的位置。有錯和無錯，而不能進(jìn)一步指明錯碼的位置。 u若此碼組長度增加一位，則能增加一個監(jiān)督關(guān)系式。這樣，若此碼組長度增加一位，則能增加一個監(jiān)督關(guān)系式。這樣，就能得到兩個校正子。兩個校正子的可

21、能取值有就能得到兩個校正子。兩個校正子的可能取值有4種組合，種組合，即即00，01，10，11，故能表示，故能表示4種不同的信息。若用其中一種不同的信息。若用其中一種組合表示無錯碼，則還有其他種組合表示無錯碼，則還有其他3種組合可以用于指明一個種組合可以用于指明一個錯碼的錯碼的3種不同位置。種不同位置。 從而可以有糾錯能力。從而可以有糾錯能力。u一般而言，若有一般而言，若有 r 個監(jiān)督關(guān)系式，則個監(jiān)督關(guān)系式，則 r 個校正子可以指明個校正子可以指明一個錯碼的一個錯碼的 (2r 1) 個不同位置。個不同位置。 u當(dāng)校正子可以指明的錯碼位置數(shù)目等于或大于碼組長度當(dāng)校正子可以指明的錯碼位置數(shù)目等于或

22、大于碼組長度n時，才能夠糾正碼組中任何一個位置上的錯碼，即要求時，才能夠糾正碼組中任何一個位置上的錯碼，即要求021aaaSnn1212rknrr或糾錯基本原理糾錯基本原理40u例：要求設(shè)計一個能夠糾正例：要求設(shè)計一個能夠糾正1個錯碼的分組碼個錯碼的分組碼(n, k)，給定，給定的碼組中有的碼組中有4個信息位，即個信息位，即k = 4。 p由由這時要求監(jiān)督位數(shù)這時要求監(jiān)督位數(shù)r 3。若取。若取r = 3，則，則n = k + r = 7。現(xiàn)在用?，F(xiàn)在用a6 a5 a4 a3 a2 a1 a0表示這表示這7個碼元，用個碼元，用S1 S2 S3表示校正子，則表示校正子，則這這3個校正子恰好能夠指明

23、個校正子恰好能夠指明23 1 = 7個錯碼的位置。個錯碼的位置。p若規(guī)定校正子和錯碼位置的關(guān)系如下表，則僅當(dāng)在若規(guī)定校正子和錯碼位置的關(guān)系如下表，則僅當(dāng)在a6 a5 a4 a2位置上有錯碼時，校正子位置上有錯碼時，校正子S1的值才等于的值才等于1；否則；否則S1的值為零。的值為零。這就意味著這就意味著a6 a5 a4 a2四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：p同理，有同理，有1212rknrr或24561aaaaS13562aaaaS03463aaaaS漢明碼漢明碼41p在編碼時，信息位在編碼時，信息位a6 a5 a4 a3的值決定于輸入信號，它們是隨的值決定于輸入信號，它們是

24、隨機的。監(jiān)督位機的。監(jiān)督位a2 a1 a0是按監(jiān)督關(guān)系確定的，應(yīng)該保證上列是按監(jiān)督關(guān)系確定的，應(yīng)該保證上列3式中的校正子等于式中的校正子等于0，即有，即有給定信息位后，為了給定信息位后，為了計算監(jiān)督位，上式可計算監(jiān)督位，上式可以改寫為以改寫為按照上式計算結(jié)果為按照上式計算結(jié)果為000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa漢明碼漢明碼42p在接收端解碼時，對于每個接收碼組，先按式在接收端解碼時，對于每個接收碼組，先按式計算出校正子計算出校正子S1，S2和和S3，然后按照表，然后按照表判斷錯碼的位置。判斷錯碼的位置。 例：若接收碼組為例：若

25、接收碼組為0000011，則按上三式計算得到：，則按上三式計算得到：S1 = 0，S2 = 1，S3 = 1。這樣，由上表可知，錯碼位置在。這樣，由上表可知，錯碼位置在a3。24561aaaaS13562aaaaS03463aaaaS漢明碼漢明碼43p上例中的漢明碼是上例中的漢明碼是(7, 4)碼，其最小碼距碼，其最小碼距d0 = 3。p由式由式p可知，此碼能夠檢測可知，此碼能夠檢測2個錯碼，或糾正個錯碼，或糾正1個錯碼。個錯碼。u漢明碼的碼率：漢明碼的碼率：當(dāng)當(dāng)r (或或n)很大時，上式趨近于很大時，上式趨近于1。所以漢明碼是一種高效編。所以漢明碼是一種高效編碼。碼。10 ed120 td1

26、212rrrnk漢明碼漢明碼44u線性分組碼的監(jiān)督位和信息位的關(guān)系線性分組碼的監(jiān)督位和信息位的關(guān)系 可以改寫為可以改寫為上式中，已經(jīng)將上式中，已經(jīng)將“ ”簡寫成簡寫成“+”。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa分組碼的一般原理分組碼的一般原理45u監(jiān)督矩陣監(jiān)督矩陣上式可以寫成矩陣形式：上式可以寫成矩陣形式： （模（模2） 將上式簡寫為將上式簡寫為HAT = 0T 或或AHT = 001001101001010110001011101234560

27、1234560123456aaaaaaaaaaaaaaaaaaaaa0001011001110101011101000123456aaaaaaa分組碼的一般原理分組碼的一般原理46 HAT = 0T 式中，式中， 稱為監(jiān)督矩陣稱為監(jiān)督矩陣 u監(jiān)督矩陣的性質(zhì)監(jiān)督矩陣的性質(zhì)p監(jiān)督矩陣監(jiān)督矩陣H確定碼組中的信息位和監(jiān)督位的關(guān)系。確定碼組中的信息位和監(jiān)督位的關(guān)系。pH 的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，即監(jiān)督位數(shù)的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，即監(jiān)督位數(shù) r 。pH 的每行中的每行中“1”的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。p H 可以分成兩部分，例如可以分成兩部分，例如 典型監(jiān)

28、督矩陣典型監(jiān)督矩陣 式中，式中，P 為為r k階矩陣，階矩陣，Ir為為 r r 階單位方陣。階單位方陣。 101100111010101110100HrPIH001101101011011001110A = a6 a5 a4 a3 a2 a1 a0 0 = 00047pH 矩陣的各行應(yīng)該是線性無關(guān)的，否則將得不到矩陣的各行應(yīng)該是線性無關(guān)的，否則將得不到 r 個線性無個線性無關(guān)的監(jiān)督關(guān)系式。關(guān)的監(jiān)督關(guān)系式。p若一個矩陣能寫成典型陣形式若一個矩陣能寫成典型陣形式P Ir，則其各行一定是線性無，則其各行一定是線性無關(guān)的。關(guān)的。u生成矩陣生成矩陣p例：例： 可以寫為可以寫為上式兩端分別轉(zhuǎn)置后，可以變成

29、上式兩端分別轉(zhuǎn)置后，可以變成式中，式中，Q為為k r 階矩陣，是階矩陣，是P的轉(zhuǎn)置，即的轉(zhuǎn)置，即 Q = PT3456012101111011110aaaaaaa346035614562aaaaaaaaaaaaQ34563456012011101110111aaaaaaaaaaa48將將Q的左邊加上一個的左邊加上一個k階單位方陣，稱為生成矩陣：階單位方陣，稱為生成矩陣： 生成矩陣生成矩陣 G稱為生成矩陣，因為可以用它產(chǎn)生整個碼組稱為生成矩陣，因為可以用它產(chǎn)生整個碼組A，即有，即有p生成矩陣的性質(zhì)生成矩陣的性質(zhì)具有IkQ形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位的位置不

30、變，監(jiān)督位附加于其后。這種形式的碼組稱為系統(tǒng)碼。 矩陣G的各行也必須是線性無關(guān)的。如果已有k個線性無關(guān)的碼組，則可以將其用來作為生成矩陣G，并由它生成其余碼組。0110001101001011001001111000QGkI IG34560123456aaaaaaaaaaaA分組碼的一般原理分組碼的一般原理49u錯誤圖樣錯誤圖樣設(shè)：發(fā)送碼組設(shè)：發(fā)送碼組A是一個是一個n列的行矩陣：列的行矩陣：接收碼組是一個接收碼組是一個n列的行矩陣列的行矩陣B： 令接收碼組和發(fā)送碼組之差為令接收碼組和發(fā)送碼組之差為E就是錯碼的行矩陣就是錯碼的行矩陣 稱為錯誤圖樣稱為錯誤圖樣 式中，式中， (i = 0, 1,

31、, n-1)若若ei = 0，表示該碼元未錯；若，表示該碼元未錯；若ei = 1，表示該碼元為錯碼。，表示該碼元為錯碼。 0121aaaaAnn0121bbbbBnnB A = E (模模2)0121eeeeEnniiiiiababe當(dāng)當(dāng), 1, 0分組碼的一般原理分組碼的一般原理50u校正子矩陣校正子矩陣 B A = E 可以改寫成可以改寫成 B = A + E上式表示發(fā)送碼組上式表示發(fā)送碼組A與錯碼矩陣與錯碼矩陣E之和等于接收碼組之和等于接收碼組B。 例如，例如， 若發(fā)送碼組若發(fā)送碼組A = 1 0 0 0 1 1 1， 錯碼矩陣錯碼矩陣E = 0 0 0 0 1 0 0， 則則 接收碼組

32、接收碼組B = 1 0 0 0 0 1 1。 在接收端解碼時，將接收碼組在接收端解碼時，將接收碼組B代入式代入式AHT = 0中中A的位置進(jìn)行計算。若接收碼組中無錯碼，則的位置進(jìn)行計算。若接收碼組中無錯碼，則B = A。代。代入后，該式仍成立，即有入后，該式仍成立，即有BH T = 0只有當(dāng)錯碼未超出檢測能力時，上式才不成立。只有當(dāng)錯碼未超出檢測能力時，上式才不成立。 假設(shè)，這時該式的右端等于假設(shè)，這時該式的右端等于S，即有，即有BH T = S將將B = A + E 代入上式，得到代入上式，得到:S = (A + E) H T = AH T + EH T51S = (A + E) H T =

33、 AH T + EH T上式右端第一項等于上式右端第一項等于0，所以，所以 S = EH T 校正子矩陣校正子矩陣當(dāng)當(dāng)H 確定后，上式中確定后，上式中S只與只與E 有關(guān)，而與有關(guān)，而與A 無關(guān)。無關(guān)。 這意味著，這意味著，S 和錯碼和錯碼E 之間有確定的線性變換關(guān)系。之間有確定的線性變換關(guān)系。 若若S 和和E 有一一對應(yīng)關(guān)系，則有一一對應(yīng)關(guān)系，則S 將能代表錯碼位置。將能代表錯碼位置。u線性碼的封閉性線性碼的封閉性：若：若A1和和A2是一種線性碼中的兩個碼組，是一種線性碼中的兩個碼組，則則(A1+A2)仍是其中一個碼組。仍是其中一個碼組。 證若證若A1和和A2是兩個碼組，則有：是兩個碼組，則有

34、：A1HT = 0, A2HT = 0 將上兩式相加，得出將上兩式相加，得出A1HT + A2HT = (A1 + A2 ) HT = 0 所以所以(A1 + A2)也是一個碼組。也是一個碼組。 由于線性碼具有封閉性，所以兩個碼組由于線性碼具有封閉性，所以兩個碼組(A1和和A2)之間之間的距離（即對應(yīng)位不同的數(shù)目）必定是另一個碼組的距離（即對應(yīng)位不同的數(shù)目）必定是另一個碼組(A1 + A2)的重量（即的重量（即“1”的數(shù)目）。因此，碼的最小距離就是碼的最的數(shù)目）。因此，碼的最小距離就是碼的最小重量（除全小重量（除全“0”碼組外）。碼組外）。52循環(huán)碼l循環(huán)碼的概念循環(huán)碼的概念l循環(huán)碼的運算循環(huán)

35、碼的運算l循環(huán)碼的編碼方法循環(huán)碼的編碼方法l循環(huán)碼的解碼方法循環(huán)碼的解碼方法l截短循環(huán)碼截短循環(huán)碼lBCH碼碼lRS碼碼53 循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個碼循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個碼組。組。n例：一種例：一種(7, 3)循環(huán)碼的全部碼組如下循環(huán)碼的全部碼組如下 表中第表中第2碼組向右移一位即得到第碼組向右移一位即得到第5碼組；第碼組；第5碼組向右移一位即得到第碼組向右移一位即得到第7碼組。碼組。 循環(huán)碼的概念循環(huán)碼的概念54n一般情況一般情況 若若(an-1 an-2 a0)是循環(huán)碼的一個碼組，則循環(huán)移位后是循環(huán)碼的一個碼組，則循環(huán)移位后的碼組：的碼

36、組： (an-2 an-3 a0 an-1) (an-3 an-4 an-1 an-2) (a0 an-1 a2 a1)仍然是該編碼中的碼組。仍然是該編碼中的碼組。n多項式表示法多項式表示法一個長度為一個長度為n的碼組的碼組(an-1 an-2 a0)可以表示成可以表示成 上式中上式中x 的值沒有任何意義，僅用它的冪代表碼元的位的值沒有任何意義，僅用它的冪代表碼元的位置。例：碼組置。例：碼組1 1 0 0 1 0 1可以表示為可以表示為 012211)(axaxaxaxTnnnn11010011)(25623456xxxxxxxxxxT循環(huán)碼的概念循環(huán)碼的概念55n 整數(shù)的按模運算整數(shù)的按模運

37、算在整數(shù)運算中，有模在整數(shù)運算中，有模n運算。例如，在模運算。例如，在模2運算中，運算中，有有1 + 1 = 2 0 (模模2)，1 + 2 = 3 1 (模模2)， 2 3 = 6 0 (模模2)等等。等等。 一般說來，若一個整數(shù)一般說來，若一個整數(shù)m可以表示為可以表示為式中，式中，Q為整數(shù)，則在模為整數(shù)，則在模n運算下，有運算下，有m p (模模n) 所以，在模所以，在模n運算下，一個整數(shù)運算下，一個整數(shù)m等于它被等于它被n除除得的余數(shù)。得的余數(shù)。npnpQnm,循環(huán)碼的運算循環(huán)碼的運算56n碼多項式的按模運算碼多項式的按模運算 若任意一個多項式若任意一個多項式F(x)被一個被一個n次多項

38、式次多項式N(x)除，得除，得到商式到商式Q(x)和一個次數(shù)小于和一個次數(shù)小于n的余式的余式R(x)，即，即則在按模則在按模N(x)運算下，有運算下，有這時，碼多項式系數(shù)仍按模這時，碼多項式系數(shù)仍按模2運算。運算。 例例1：x3被被(x3 + 1)除，得到余項除，得到余項1，即，即 例例2：因為因為xx3 + 1 x4 +x2 + 1x4 + x x2 +x +1 在模在模2運算中加法和減法一樣。運算中加法和減法一樣。)()()()(xRxQxNxF）（模)()()(xNxRxF）（模) 1(133xx）（模) 1(113224xxxxx57n循環(huán)碼的數(shù)學(xué)表示法循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，

39、設(shè)在循環(huán)碼中，設(shè)T(x)是一個長度為是一個長度為n的碼組，若的碼組，若則則T (x)也是該編碼中的一個碼組。也是該編碼中的一個碼組。 證證 設(shè)一循環(huán)碼為設(shè)一循環(huán)碼為 則有則有 上式中的上式中的T (x) 正是碼組正是碼組T (x)向左循環(huán)移位向左循環(huán)移位 i 次的結(jié)果。次的結(jié)果。例：例： 一循環(huán)碼為一循環(huán)碼為1100101，即，即 若給定若給定 i = 3，則有，則有 上式對應(yīng)的碼組為上式對應(yīng)的碼組為0101110，它正是，它正是T(x)向左移向左移3位的結(jié)果。位的結(jié)果。結(jié)論：一個長為結(jié)論：一個長為n的循環(huán)碼必定為按模的循環(huán)碼必定為按模(xn + 1)運算的一個余式。運算的一個余式。 ）（模)

40、 1()()(nixxTxTx012211)(axaxaxaxTnnnn)()(1102211011112211xTaxaxaxaxaxaxaxaxaxaxTxininininniniinininninni1)(256xxxxT）（模) 1()(723535893xxxxxxxxxxTx58n循環(huán)碼的生成循環(huán)碼的生成 u有了生成矩陣有了生成矩陣G，就可以由，就可以由k個信息位得出整個碼組：個信息位得出整個碼組：例：例：式中，式中，生成矩陣生成矩陣G的每一行都是一個碼組。的每一行都是一個碼組。u因此，若能找到因此，若能找到 k 個已知的碼組，就能構(gòu)成矩陣個已知的碼組，就能構(gòu)成矩陣G。如前。如前所

41、述，這所述，這k個已知碼組必須是線性不相關(guān)的。個已知碼組必須是線性不相關(guān)的。u在循環(huán)碼中，一個在循環(huán)碼中，一個(n, k)碼有碼有2k個不同的碼組。若用個不同的碼組。若用g(x)表表示其中前示其中前(k-1)位皆為位皆為“0”的碼組，則的碼組，則g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是碼組，而且這都是碼組，而且這k個碼組是線性無關(guān)的。因個碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。G34560123456aaaaaaaaaaaA0110001101001011001001111000QGkI I循環(huán)碼的運算循環(huán)碼的運算5

42、9u在循環(huán)碼中除全在循環(huán)碼中除全“0”碼組外，再沒有連續(xù)碼組外，再沒有連續(xù)k位均為位均為“0”的碼組。的碼組。否則，在經(jīng)過若干次循環(huán)移位后將得到否則，在經(jīng)過若干次循環(huán)移位后將得到k位信息位全為位信息位全為“0”，但監(jiān)督位不全為但監(jiān)督位不全為“0”的一個碼組。這在線性碼中顯然是不可的一個碼組。這在線性碼中顯然是不可能的。能的。u因此，因此，g(x)必須是一個常數(shù)項不為必須是一個常數(shù)項不為“0”的的(n - k)次多項式，次多項式，而且這個而且這個g(x)還是這種還是這種(n, k)碼中次數(shù)為碼中次數(shù)為(n k)的唯一一個的唯一一個多項式。因為如果有兩個，則由碼的封閉性，把這兩個相多項式。因為如果

43、有兩個，則由碼的封閉性，把這兩個相加也應(yīng)該是一個碼組，且此碼組多項式的次數(shù)將小于加也應(yīng)該是一個碼組，且此碼組多項式的次數(shù)將小于(n k)，即連續(xù)，即連續(xù)“0”的個數(shù)多于的個數(shù)多于(k 1)。顯然，這是與前面的結(jié)。顯然，這是與前面的結(jié)論矛盾的。論矛盾的。u我們稱這唯一的我們稱這唯一的(n k)次多項式次多項式g(x)為碼的生成多項式。一為碼的生成多項式。一旦確定了旦確定了g(x)，則整個，則整個(n, k)循環(huán)碼就被確定了。循環(huán)碼就被確定了。循環(huán)碼的運算循環(huán)碼的運算60u因此，循環(huán)碼的生成矩陣因此，循環(huán)碼的生成矩陣G可以寫成可以寫成u例：例：上表中的編碼為上表中的編碼為(7, 3)循環(huán)碼，循環(huán)碼

44、，n = 7, k = 3, n k = 4，其中唯一的一個其中唯一的一個(n k) = 4次碼多項式代表的碼組是第二碼次碼多項式代表的碼組是第二碼組組0010111，與它對應(yīng)的碼多項式，即生成多項式，為，與它對應(yīng)的碼多項式，即生成多項式，為g(x) = x4 + x2 + x + 1。 )()()()()(21xgxxgxgxxgxxkkG61g(x) = x4 + x2 + x + 1 即即 “1 0 1 1 1”將此將此g(x)代入上矩陣，得到代入上矩陣，得到 或或上式不符合上式不符合G = IkQ形式，所以它不是典型生成矩陣。但形式，所以它不是典型生成矩陣。但它經(jīng)過線性變換后，不難化成

45、典型陣。它經(jīng)過線性變換后，不難化成典型陣。此循環(huán)碼組的多項式表示式此循環(huán)碼組的多項式表示式T(x)： 上式表明，所有碼多項式上式表明，所有碼多項式T(x)都能夠被都能夠被g(x)整除，而且整除，而且任意一個次數(shù)不大于任意一個次數(shù)不大于(k 1)的多項式乘的多項式乘g(x)都是碼多項式。都是碼多項式。 )()()()(2xgxxgxgxxG001011101011101011100)(xG)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG62n尋求碼生成多項式尋求碼生成多項式 因為任意一個循環(huán)碼因為任意一

46、個循環(huán)碼T(x)都是都是g(x)的倍式，故它可以寫成的倍式，故它可以寫成T(x) = h(x) g(x)而生成多項式而生成多項式g(x)本身也是一個碼組，即有本身也是一個碼組，即有 T (x) = g(x)由于碼組由于碼組T (x)是一個是一個(n k)次多項式，故次多項式，故xk T (x)是一個是一個n次次多項式。由多項式。由可知，可知，xk T (x)在模在模(xn + 1)運算下也是一個碼組，所以有運算下也是一個碼組，所以有上式左端分子和分母都是上式左端分子和分母都是n次多項式，故相除的商式次多項式，故相除的商式Q(x) = 1。因此，上式可以寫成因此，上式可以寫成）（模) 1()()

47、(nixxTxTx1)()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk循環(huán)碼的運算循環(huán)碼的運算63將將 T(x) = h(x) g(x) 和和 T (x) = g(x) 代入代入化簡后，得到化簡后，得到上式表明，生成多項式上式表明，生成多項式g(x)應(yīng)該是應(yīng)該是(xn + 1)的一個因子。的一個因子。例：例：(x7 + 1)可以分解為可以分解為為了求出為了求出(7, 3)循環(huán)碼的生成多項式循環(huán)碼的生成多項式 g(x)，需要從上式，需要從上式中找到一個中找到一個(n k) = 4次的因子。這樣的因子有兩個，即次的因子。這樣的因子有兩個，即以上兩式都可以作為生成多項式。以上兩式

48、都可以作為生成多項式。 選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組也不同。選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組也不同。 )() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx循環(huán)碼的運算循環(huán)碼的運算64n用用xn-k乘乘m(x)。這一運算實際上是在信息碼后附加上。這一運算實際上是在信息碼后附加上(n k)個個“0”。例如，信息碼為。例如，信息碼為110，它寫成多項式為，它寫成多項式為m(x) = x2 + x。當(dāng)當(dāng)n k = 7 3 =4時，時，xn-k m(x) = x4

49、(x2 +x) = x6 +x5，它表示，它表示碼組碼組1100000。n用用g(x)除除xn-k m(x)，得到商，得到商Q(x)和余式和余式r(x)，即有，即有例：若選定例：若選定g(x) = x4 + x2 + x + 1，則有，則有 上式是用碼多項式表示的運算。它和下式等效：上式是用碼多項式表示的運算。它和下式等效：n編出的碼組編出的碼組T(x)為：為：T(x) = xn-k m(x) +r(x)在上例中，在上例中，T(x) = 1100000 + 101 = 1100101 )()()()()(xgxrxQxgxmxkn11) 1(1)()(24222456xxxxxxxxxxxxg

50、xmxkn10111101111101111100000循環(huán)碼的編碼方法循環(huán)碼的編碼方法65n在檢錯時：當(dāng)接收碼組沒有錯碼時，接收碼組在檢錯時：當(dāng)接收碼組沒有錯碼時，接收碼組R(x)必定能被必定能被g(x)整除，即下式整除，即下式中余項中余項r(x)應(yīng)為零；否則，有誤碼。應(yīng)為零；否則，有誤碼。u當(dāng)接收碼組中的錯碼數(shù)量過多，超出了編碼的檢錯能當(dāng)接收碼組中的錯碼數(shù)量過多，超出了編碼的檢錯能力時，有錯碼的接收碼組也可能被力時，有錯碼的接收碼組也可能被g(x)整除。這時，錯整除。這時，錯碼就不能檢出了。碼就不能檢出了。 n在糾錯時：在糾錯時：u用生成多項式用生成多項式g(x)除接收碼組除接收碼組R(x

51、)，得出余式，得出余式r(x)。u按照余式按照余式r(x)，用查表的方法或計算方法得出錯誤圖樣，用查表的方法或計算方法得出錯誤圖樣E(x)。u從從R(x)中減去中減去E(x)，便得到已經(jīng)糾正錯碼的原發(fā)送碼組，便得到已經(jīng)糾正錯碼的原發(fā)送碼組T(x)。)(/)()()(/)(xgxrxQxgxR循環(huán)碼的解碼方法循環(huán)碼的解碼方法66n截短目的截短目的： 在設(shè)計時，通常信息位數(shù)在設(shè)計時，通常信息位數(shù)k、碼長、碼長n和糾錯能力都是預(yù)先和糾錯能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。故采用截短碼長截短，得出滿足要求的編碼。在。故采用

52、截短碼長截短，得出滿足要求的編碼。n截短方法截短方法： 設(shè)給定一個設(shè)給定一個(n, k)循環(huán)碼，它共有循環(huán)碼，它共有2k種碼組，現(xiàn)使其前種碼組，現(xiàn)使其前i (0 i k)個信息位全為個信息位全為“0”，于是它變成僅有，于是它變成僅有2k-i種碼組。然種碼組。然后從中刪去這后從中刪去這 i 位全位全“0”的信息位，最終得到一個的信息位，最終得到一個 (n i，k i)的線性碼。將這種碼稱為截短循環(huán)碼。的線性碼。將這種碼稱為截短循環(huán)碼。 n截短循環(huán)碼與截短前的循環(huán)碼至少具有相同的糾錯能力，截短循環(huán)碼與截短前的循環(huán)碼至少具有相同的糾錯能力，并且截短循環(huán)碼的編解碼方法仍和截短前的方法一樣。并且截短循環(huán)

53、碼的編解碼方法仍和截短前的方法一樣。 n例：要求構(gòu)造一個能夠糾正例：要求構(gòu)造一個能夠糾正1位錯碼的位錯碼的(13, 9)碼。碼。 這時可以由這時可以由(15, 11)循環(huán)碼的循環(huán)碼的11種碼組中選出前兩信息種碼組中選出前兩信息位均為位均為“0”的碼組，構(gòu)成一個新的碼組集合。然后在發(fā)送時的碼組，構(gòu)成一個新的碼組集合。然后在發(fā)送時不發(fā)送這兩位不發(fā)送這兩位“0”。于是發(fā)送碼組成為。于是發(fā)送碼組成為(13, 9)截短循環(huán)碼。截短循環(huán)碼。 截短循環(huán)碼截短循環(huán)碼67nBCH碼是能夠糾正多個隨機錯碼的循環(huán)碼。碼是能夠糾正多個隨機錯碼的循環(huán)碼。n BCH碼分為兩類：本原碼分為兩類：本原BCH碼和非本原碼和非本

54、原BCH碼。碼。 u本原本原BCH碼：碼長碼：碼長n = 2m 1 (m 3，任意正整數(shù)，任意正整數(shù))，它的生成多項式，它的生成多項式g(x)中含有最高次數(shù)為中含有最高次數(shù)為m次的本原多項式；次的本原多項式；u非本原非本原BCH碼：碼長碼：碼長n是是(2m 1)的一個因子，它的生成多項式的一個因子，它的生成多項式g(x)中中不含有最高次數(shù)為不含有最高次數(shù)為m的本原多項式。的本原多項式。nBCH碼的工程設(shè)計：可以用查表法找到所需的生成多項式。碼的工程設(shè)計：可以用查表法找到所需的生成多項式。例：二進(jìn)制非本原例：二進(jìn)制非本原BCH碼的生成多項式系數(shù)碼的生成多項式系數(shù) 表中表中g(shù)(x)是用是用8進(jìn)制數(shù)

55、字表示的；進(jìn)制數(shù)字表示的；t 為糾錯能力。為糾錯能力。BCH碼碼68n常用常用BCH碼碼：u戈萊戈萊(Golay)碼：碼： (23, 12)非本原非本原BCH碼，它能糾正碼，它能糾正3個個隨機錯碼，并且容易解碼隨機錯碼，并且容易解碼 。u擴(kuò)展擴(kuò)展BCH碼碼(n + 1, k) ：pBCH碼的長度為奇數(shù)。在應(yīng)用中，為了得到偶數(shù)長度的碼的長度為奇數(shù)。在應(yīng)用中，為了得到偶數(shù)長度的碼，并增大檢錯能力，可以在碼，并增大檢錯能力，可以在BCH碼生成多項式中乘上碼生成多項式中乘上一個因式一個因式(x + 1)，從而得到擴(kuò)展，從而得到擴(kuò)展BCH碼碼(n + 1, k)。 p擴(kuò)展擴(kuò)展BCH碼已經(jīng)不再具有循環(huán)性。

56、碼已經(jīng)不再具有循環(huán)性。 u擴(kuò)展戈萊碼擴(kuò)展戈萊碼(24, 12)：其最小碼距為：其最小碼距為8，碼率為，碼率為1/2，能夠，能夠糾正糾正3個錯碼和檢測個錯碼和檢測4個錯碼。個錯碼。 BCH碼碼69n幾種二進(jìn)制分組碼的性能比較幾種二進(jìn)制分組碼的性能比較 2PSK漢明碼(7, 4) t=1 漢明碼(31, 26) t=1擴(kuò)展戈萊碼(24, 12) t=3BCH碼(127, 64) t=10Eb / n0 (dB)Pe70nRS碼：是碼：是q進(jìn)制進(jìn)制BCH碼的一個特殊子類，并且具有很碼的一個特殊子類，并且具有很強的糾錯能力。強的糾錯能力。nRS碼的參數(shù)：碼長碼的參數(shù)：碼長n = q 1，監(jiān)督位數(shù)目，監(jiān)

57、督位數(shù)目r = 2t，其，其中中t是能夠糾正的錯碼數(shù)目；其生成多項式為是能夠糾正的錯碼數(shù)目；其生成多項式為g(x) = (x + )(x + 2) (x + 2t)式中，式中， 為伽羅華域為伽羅華域GF(2m)中的本原元。中的本原元。 nRS碼的主要優(yōu)點：碼的主要優(yōu)點：u它是多進(jìn)制糾錯編碼，所以特別適合用于多進(jìn)制調(diào)制的場它是多進(jìn)制糾錯編碼，所以特別適合用于多進(jìn)制調(diào)制的場合；合；u它能夠糾正它能夠糾正t個個q位二進(jìn)制錯碼，即能夠糾正不超過位二進(jìn)制錯碼，即能夠糾正不超過q個連續(xù)個連續(xù)的二進(jìn)制錯碼，所以適合在衰落信道中糾正突發(fā)性錯碼。的二進(jìn)制錯碼，所以適合在衰落信道中糾正突發(fā)性錯碼。RS碼碼71卷積

58、碼l卷積碼的編碼卷積碼的編碼l卷積碼的解碼卷積碼的解碼72n卷積碼的特點卷積碼的特點：u監(jiān)督碼元不僅和當(dāng)前的監(jiān)督碼元不僅和當(dāng)前的k比特信息段有關(guān)，而且還比特信息段有關(guān)，而且還同前面同前面m = (N 1)個信息段有關(guān)。個信息段有關(guān)。u將將N稱為碼組的約束度。稱為碼組的約束度。u將卷積碼記作將卷積碼記作(n, k, m)，其碼率為，其碼率為k/n。卷積碼卷積碼73u一般原理方框圖一般原理方框圖編碼輸出每次輸入k比特1k1k1k1k 1 k2k3kNk 12nNk級移存器n個模2加法器每輸入k比特旋轉(zhuǎn)1周卷積碼的編碼卷積碼的編碼74u卷積碼編碼器的實例方框圖：卷積碼編碼器的實例方框圖：(n, k,

59、 m) =（3, 1, 2）p每當(dāng)輸入每當(dāng)輸入1比特時，此編碼器輸出比特時，此編碼器輸出3比特比特c1c2 c3：p編碼器的工作狀態(tài)編碼器的工作狀態(tài) 123b3b1輸入b2編碼輸出c2c1c3321331211bbbcbbcbc75n碼樹搜索法：碼樹搜索法：(3, 1, 2)卷積碼的碼樹圖卷積碼的碼樹圖此法不實用：因為隨信息位增多，分支數(shù)目按指數(shù)規(guī)律增長此法不實用：因為隨信息位增多，分支數(shù)目按指數(shù)規(guī)律增長000111001110011100010101000111001110011100010101c1c2c3000100111011001101110010c1c2c3111000001110

60、c1c2c3信息位 1 1 0 1ba起點信息位000111c1c2c3abcdabcdabcdabcd上半部下半部10a狀態(tài) b3b2 a 0 0 b 0 1 c 1 0 d 1 1abcdabcdcdab01100176n狀態(tài)圖和網(wǎng)格圖狀態(tài)圖和網(wǎng)格圖u移存器狀態(tài)和輸入輸出碼元的關(guān)系移存器狀態(tài)和輸入輸出碼元的關(guān)系u狀態(tài)圖狀態(tài)圖321331211bbbcbbcbc123b3b1輸入b2編碼輸出c2c1c3abcd00011110111001001110000177u(3, 1, 2)卷積碼網(wǎng)格圖卷積碼網(wǎng)格圖u網(wǎng)格圖中的編碼路徑舉例網(wǎng)格圖中的編碼路徑舉例p輸入信息位為輸入信息位為1101時時p輸