1、1第第 6 章章 信道編碼信道編碼26.1 概述概述 作用作用提高信息傳輸時的抗干擾能力提高信息傳輸時的抗干擾能力 目的目的增加信息傳輸的可靠性增加信息傳輸的可靠性 手段手段增加信息冗余度增加信息冗余度 名稱名稱信道碼、數據傳輸碼、差錯控制碼信道碼、數據傳輸碼、差錯控制碼36.1 概述概述 信道編碼器在通信系統中的位置信道編碼器在通信系統中的位置信源編碼信源編碼信道編碼信道編碼信源譯碼信源譯碼信道譯碼信道譯碼解密解密加密加密信宿信宿信源信源4 分類分類6.1 概述分分組組碼碼樹樹碼碼線線性性碼碼非非線線性性碼碼檢檢錯錯碼碼糾糾錯錯碼碼抗抗隨隨機機差差錯錯碼碼抗抗突突發發差差錯錯碼碼代代數數碼碼

2、幾幾何何碼碼組組合合碼碼線性分組碼線性分組碼群碼群碼 線性樹碼線性樹碼卷積碼卷積碼 5 最小差錯概率準則最小差錯概率準則 理想譯碼器，依賴于輸入概率分布。理想譯碼器，依賴于輸入概率分布。 最大似然準則最大似然準則 實用譯碼準則，與最小差錯概率準則等價。實用譯碼準則，與最小差錯概率準則等價。 6.2 信道譯碼準則66.3 碼例碼例信道編譯碼方法的最初范例。信道編譯碼方法的最初范例。 基本思路基本思路將碼字分成兩段將碼字分成兩段 用模二和對二元分組碼進行一致性校驗。用模二和對二元分組碼進行一致性校驗。 奇偶校驗碼奇偶校驗碼只有一個校驗位的漢明碼只有一個校驗位的漢明碼。二元分組碼信息位二元分組碼信息

3、位校驗位校驗位奇校驗、偶校驗。奇校驗、偶校驗。76.3 碼例碼例 奇校驗奇校驗 DES算法算法例例1 1 0 0 1 0 111 1 0 0 1 0 10偶校驗偶校驗86.3 碼例碼例多個校驗位的漢明碼多個校驗位的漢明碼 每個校驗位是部分或全部信息位每個校驗位是部分或全部信息位按模二和規則確定。按模二和規則確定。例例N=7，k=4c4c6c5u3u2u1u0401251236013cuuucuuucuuuc4c6c5c3c2c1c096.3 碼例碼例0101011可以糾正一個錯誤。可以糾正一個錯誤。 譯碼譯碼 - 驗證校驗位驗證校驗位 - 錯誤位取反錯誤位取反106.4 線性分組碼 同時具有線

4、性特性和分組特性把符號同時看成是運算的數把符號同時看成是運算的數引入模引入模2 2算術算術 二元有限域 有限個元素的集合，定義兩種運算有限個元素的集合，定義兩種運算加和乘加和乘 加法有零元，乘法有幺元加法有零元，乘法有幺元 有加逆元和乘逆元有加逆元和乘逆元 加、乘滿足結合律和交換律，加和乘滿足分配加、乘滿足結合律和交換律，加和乘滿足分配律律 116.4 線性分組碼 加法加法 a+b 011011001111, , ,(,)mmmma aab bbab abab 乘法乘法 ab=c101111011011()() mod ( )mmmmmmccxc xaaxa xbbxb xp x不可約不可約多

5、項式多項式126.4 線性分組碼 線性分組碼的基本參數碼碼 長：長： n信息位長：信息位長： k碼碼 字字 數：數：M監督位長：監督位長：r最小碼距：最小碼距：dmin例例重復碼重復碼0001 1 1136.4 線性分組碼（4，3）偶校驗碼）偶校驗碼例例例例例例 奇校驗碼？奇校驗碼？ 恒比碼？恒比碼？0101 10110 114 6.4 線性分組碼 衡量碼的重要指標衡量碼的重要指標 漢明重量（碼重）漢明重量（碼重）碼字中非零碼元的數目。碼字中非零碼元的數目。漢明重量（碼重）漢明重量（碼重）=例例10110101156.4 線性分組碼兩個碼字中相應碼元取不同數值的碼元數。兩個碼字中相應碼元取不同

6、數值的碼元數。 漢明距離（碼距）漢明距離（碼距）漢明距離（碼距）漢明距離（碼距）=1011010111010011例例16 6.4 線性分組碼 最小最小漢明距離（最小碼距）漢明距離（最小碼距）同一碼所有漢明距離中最小的一個。同一碼所有漢明距離中最小的一個。例例（4，3）偶校驗碼）偶校驗碼10010000001111001010111101010110最小漢明距離（最小碼距）最小漢明距離（最小碼距）=176.4 線性分組碼檢錯和糾錯能力檢錯和糾錯能力1檢錯檢錯l=dmin-12糾錯糾錯t=（dmin-1）/23l+t= dmin-1, tl最小漢明距離最小漢明距離 （最小碼距（最小碼距d d）：

7、任意兩碼）：任意兩碼字之間的漢明距離的最小值字之間的漢明距離的最小值 mind186.4 線性分組碼線性分組碼檢、糾錯能力圖示檢、糾錯能力圖示190011001110101010110001106.4 線性分組碼線性分組碼檢、糾錯能力圖示檢、糾錯能力圖示20 漢明碼簡介6.4 線性分組碼碼碼 長：長： n=2r-1信息位長：信息位長： k=n-r=2r-r-1碼碼 字字 數：數：M=2k監督位長：監督位長：r=n-k最小碼距：最小碼距：dmin=3糾錯能力：糾錯能力：t=1216.4 線性分組碼 線性分組碼編碼線性分組碼編碼cuG信息矢量信息矢量生成矩陣生成矩陣1000101010011100

8、101100001011G226.4 線性分組碼一致校驗方程組一致校驗方程組0TcH 1 1 1 0 1 0 00 1 1 1 0 1 01 1 0 1 0 0 1H校校驗驗矩矩陣陣236.4 線性分組碼(1101)u cuG例例1000101010011100101100001011G(1 1 0 1 0 0 1)c 編碼：編碼：246.4 線性分組碼譯碼（無差錯）：譯碼（無差錯）：cHT101111110= 1101001= 0011100010001(1101)u 256.4 線性分組碼譯碼（有差錯）：譯碼（有差錯）：011011011(,)(,)(,)NNNyyyyc ccz zz接收

9、矢量接收矢量伴隨式伴隨式()0TTTsHyH czHzS可以指示差錯的存在可以指示差錯的存在266.4 線性分組碼例例0120123456111010001110101101001TTss s sH zzzzzzzz27 6.4 線性分組碼101242123530136szzzzszzzzszzzz伴隨式伴隨式s0s1s2錯誤錯誤位置位置錯誤圖樣錯誤圖樣101z01000000111z10100000110z20010000011z30001000100z40000100010z50000010001 z6000000128 6.4 線性分組碼譯碼步驟：譯碼步驟：1計算伴隨式，構造伴隨式計算伴

10、隨式，構造伴隨式-差錯圖案表差錯圖案表（s，e）；）；2對接收向量計算伴隨式；對接收向量計算伴隨式；3查（查（s，e）表得）表得e；4糾錯。糾錯。29 6.4 線性分組碼 系統碼系統碼線性線性(N，k)碼生成矩陣碼生成矩陣G具有形式具有形式 由此產生的碼稱為系統碼。系統碼的一致由此產生的碼稱為系統碼。系統碼的一致監督矩陣具有形式監督矩陣具有形式,kGIA,TNkHAI 二元有限域上的二元有限域上的 -AT=AT碼長為碼長為N，信息位長度為，信息位長度為k的分組碼稱為的分組碼稱為(N，k)碼。碼。306.4 線性分組碼 線性分組碼的性質線性分組碼的性質 零向量零向量 是一個碼字，稱為零碼字是一個

11、碼字，稱為零碼字 兩碼字之和或差仍是一個碼字兩碼字之和或差仍是一個碼字線性性線性性 在碼的所有碼字上減去任一特在碼的所有碼字上減去任一特定的碼字，結果仍是這同一碼定的碼字，結果仍是這同一碼的全部碼字。的全部碼字。對稱性對稱性 二元有限域上最小碼距二元有限域上最小碼距 最小碼重。最小碼重。316.5 線性循環碼 漢明碼的對偶碼漢明碼的對偶碼101110001011100010111G 線性循環碼線性循環碼例例1101000011010000110100001101H321000101010011100101100001011G（1） （3） （4）（2） （4）11010000110100001

12、10100001101G6.5 線性循環碼336.5 線性循環碼循環碼的多項式描述循環碼的多項式描述 g(x)一致校驗多項式一致校驗多項式)(1)(xgxxhn 編碼編碼 譯碼譯碼)()(mod()(xgxrxs34 更好的設計和實現線性分組碼的方法是引入特定的數學結構來界定某一類線性分組碼。循環碼即是采用循環移位特性界定的一類線性分組碼。 6.5.1 6.5.1 循環碼的多項式描述循環碼的多項式描述35 012111013211011,0,1,1,2,nninnnin in inniaa aaaaaaa aaaaaaaa aain 121210112223101211121010,1nnnn

13、innnnninniiinininn ia xaxaxa xaaaxaxaxa xa xaaxaxaxa xa xaxa 36 1 mod1 mod1niinaxxa xxaxx a xx37將循環碼的碼字用多項式將循環碼的碼字用多項式c(x)c(x)，稱為碼多，稱為碼多項式（簡稱碼式）表示后，循環碼集合表項式（簡稱碼式）表示后，循環碼集合表示示C(x),C(x), ,iiCc cbb CC xc x c xbx b xC x38例 6.3.2 如下確定的如下確定的C CA A是線性循環碼，是線性循環碼，C CB B是非循環的線性分組碼，是非循環的線性分組碼，C CC C是非線性的循環是非線性

14、的循環碼。碼。 ， ， 39定理：定理： （n,k）循環碼循環碼C( x)中存在唯一的一個中存在唯一的一個非零的，首一的和最低次為非零的，首一的和最低次為r（rn）的碼）的碼 多項式多項式g(x)滿足：滿足： g(x)=xr+gr-1xr-1+.+g1X+g0 g00 r=n-k并且并且c(x)是碼式當且僅當是碼式當且僅當c(x)是是g(x)的倍式的倍式40生成多項式生成多項式. . 因此因此(n,k)(n,k)循環碼的構造是如何構造生成循環碼的構造是如何構造生成多項式多項式g(x)g(x)。 ,C xc x c xa x g xa xk循環碼由生成多項式的倍式組成循環碼由生成多項式的倍式組成

15、41定理：定理： g(x)是（是（n,k）循環碼的生成多項式）循環碼的生成多項式，當且僅當當且僅當g(x)是是xn-1的的r=n-k次因式。次因式。42434445 6.3.1循環碼的多項式描述循環碼的多項式描述6.3.2 循環碼的生成矩陣循環碼的生成矩陣 6.3.3系統循環碼系統循環碼 6.3.4多項式運算電路多項式運算電路 6.3.5循環碼的編碼電路循環碼的編碼電路 6.3.6循環碼的伴隨多項式與檢測循環碼的伴隨多項式與檢測 6.3.7BCH碼與碼與RS碼碼466.3.2循環碼的生成矩陣和校驗矩陣(n,k)循環碼的生成矩陣為循環碼的生成矩陣為01210121011, 0, ,00, ,00, 0, ,0, , rrrrrrrk nggggggggggGgggg47101010,0,0,00,0,00,0,kkkkkr nh hhhh hHhhh486