第九章 糾錯(cuò)編碼1

1、第九章第九章 糾錯(cuò)編碼糾錯(cuò)編碼1 1 糾錯(cuò)碼的分類糾錯(cuò)碼的分類2 2 糾錯(cuò)碼的基本概念糾錯(cuò)碼的基本概念 3 3 線性分組碼線性分組碼 4 4 漢明碼漢明碼 5 5 循環(huán)碼循環(huán)碼l 香農(nóng)第二定理證明，當(dāng)香農(nóng)第二定理證明，當(dāng) 時(shí)時(shí) 的碼存在。的碼存在。l 證明過程采用的是隨機(jī)編碼的方法：證明過程采用的是隨機(jī)編碼的方法：隨機(jī)編碼所得的碼集很大，通過搜索得到好碼的方法在實(shí)隨機(jī)編碼所得的碼集很大，通過搜索得到好碼的方法在實(shí)際上很難實(shí)現(xiàn)；際上很難實(shí)現(xiàn)；即時(shí)找到了好碼，這種碼的碼字也沒有規(guī)律，不便于譯碼。即時(shí)找到了好碼，這種碼的碼字也沒有規(guī)律，不便于譯碼。l 真正實(shí)用的信道編碼方法還需要通過各種數(shù)學(xué)工具真正

2、實(shí)用的信道編碼方法還需要通過各種數(shù)學(xué)工具來構(gòu)造，使碼具有好的結(jié)構(gòu)性以便于譯碼。來構(gòu)造，使碼具有好的結(jié)構(gòu)性以便于譯碼。RC0EP l 糾錯(cuò)編碼的糾錯(cuò)編碼的基本思路基本思路： 根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些冗余碼元，這些冗余碼元與信息碼元之間以某入一些冗余碼元，這些冗余碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。種確定的規(guī)則相互關(guān)聯(lián)（約束）。 在接收端按照既定的規(guī)則檢驗(yàn)信息碼元與監(jiān)督碼在接收端按照既定的規(guī)則檢驗(yàn)信息碼元與監(jiān)督碼元之間的關(guān)系。如果傳輸過程出錯(cuò)，則信息碼元與監(jiān)元之間的關(guān)系。如果傳輸過程出錯(cuò)，則信息碼元與監(jiān)督碼元之間的關(guān)

3、系將受到破壞，從而可以發(fā)現(xiàn)錯(cuò)誤乃督碼元之間的關(guān)系將受到破壞，從而可以發(fā)現(xiàn)錯(cuò)誤乃至糾正錯(cuò)誤。至糾正錯(cuò)誤。概述概述干擾一般分為兩種形式：干擾一般分為兩種形式：一是隨機(jī)噪聲，它主要來源于設(shè)備的熱噪聲和散彈一是隨機(jī)噪聲，它主要來源于設(shè)備的熱噪聲和散彈噪聲以及傳播媒介的熱噪聲，它是通信系統(tǒng)中的主噪聲以及傳播媒介的熱噪聲，它是通信系統(tǒng)中的主要噪聲；要噪聲；二是脈沖干擾和信道衰落，它的特點(diǎn)是突發(fā)出現(xiàn)，二是脈沖干擾和信道衰落，它的特點(diǎn)是突發(fā)出現(xiàn)，主要來源于雷電、通電開關(guān)、負(fù)荷突變或設(shè)備故障主要來源于雷電、通電開關(guān)、負(fù)荷突變或設(shè)備故障等。等。 概述概述信道可分為三類：信道可分為三類：1. 只產(chǎn)生隨機(jī)錯(cuò)誤的信道稱

4、為隨機(jī)信道。比如衛(wèi)星信道、只產(chǎn)生隨機(jī)錯(cuò)誤的信道稱為隨機(jī)信道。比如衛(wèi)星信道、同軸電纜、光纜信道以及大多數(shù)微波中繼信道。同軸電纜、光纜信道以及大多數(shù)微波中繼信道。2. 產(chǎn)生突發(fā)錯(cuò)誤的信道稱為突發(fā)信道。實(shí)際的短波信道、產(chǎn)生突發(fā)錯(cuò)誤的信道稱為突發(fā)信道。實(shí)際的短波信道、移動(dòng)通信信道、由于差傷造成成串差錯(cuò)的光盤和磁盤，均移動(dòng)通信信道、由于差傷造成成串差錯(cuò)的光盤和磁盤，均為這一類信道。為這一類信道。3. 有些實(shí)際信道既有隨機(jī)錯(cuò)誤又有突發(fā)錯(cuò)誤，稱為混合有些實(shí)際信道既有隨機(jī)錯(cuò)誤又有突發(fā)錯(cuò)誤，稱為混合信道。信道。 根據(jù)不同的信道類型設(shè)計(jì)的信道編碼分為糾隨機(jī)錯(cuò)誤根據(jù)不同的信道類型設(shè)計(jì)的信道編碼分為糾隨機(jī)錯(cuò)誤碼、糾突

5、發(fā)錯(cuò)誤碼和糾混合錯(cuò)誤碼。碼、糾突發(fā)錯(cuò)誤碼和糾混合錯(cuò)誤碼。 概述概述在通信系統(tǒng)中，糾檢錯(cuò)的工作方式有：在通信系統(tǒng)中，糾檢錯(cuò)的工作方式有：(1) 反饋重傳反饋重傳(ARQ)(2) 前向糾錯(cuò)前向糾錯(cuò)(FEC)(3) 混合糾錯(cuò)混合糾錯(cuò)概述概述 發(fā)送端經(jīng)編碼后發(fā)出能夠發(fā)現(xiàn)錯(cuò)誤的碼，接收端收到后經(jīng)發(fā)送端經(jīng)編碼后發(fā)出能夠發(fā)現(xiàn)錯(cuò)誤的碼，接收端收到后經(jīng)檢驗(yàn)，如果發(fā)現(xiàn)傳輸中有錯(cuò)誤，則通過反饋系統(tǒng)把這一判斷結(jié)檢驗(yàn)，如果發(fā)現(xiàn)傳輸中有錯(cuò)誤，則通過反饋系統(tǒng)把這一判斷結(jié)果反饋回發(fā)端，然后發(fā)送端把前面發(fā)出的信息重新傳送一次，果反饋回發(fā)端，然后發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為正確地收到信息為止。直到接收端認(rèn)為

6、正確地收到信息為止。 (1) 反饋重傳反饋重傳(ARQ)mCRm檢錯(cuò)檢錯(cuò)編碼編碼信道信道檢錯(cuò)檢錯(cuò)譯碼譯碼反饋反饋(2) 前向糾錯(cuò)前向糾錯(cuò)(FEC)mCRm糾錯(cuò)糾錯(cuò)編碼編碼信道信道糾錯(cuò)糾錯(cuò)譯碼譯碼 發(fā)送端發(fā)出的是具有糾錯(cuò)能力的糾錯(cuò)碼，接收端根據(jù)譯發(fā)送端發(fā)出的是具有糾錯(cuò)能力的糾錯(cuò)碼，接收端根據(jù)譯碼規(guī)則進(jìn)行譯碼。當(dāng)誤碼個(gè)數(shù)在碼的糾錯(cuò)能力范圍內(nèi)時(shí)，譯碼規(guī)則進(jìn)行譯碼。當(dāng)誤碼個(gè)數(shù)在碼的糾錯(cuò)能力范圍內(nèi)時(shí)，譯碼器可以自動(dòng)糾正錯(cuò)誤。碼器可以自動(dòng)糾正錯(cuò)誤。特點(diǎn)：特點(diǎn)： 1 1）前向糾錯(cuò)方式不需要反饋信道，特別適合于只能）前向糾錯(cuò)方式不需要反饋信道，特別適合于只能 提供單向信道的場合。提供單向信道的場合。2 2）由

7、于能自動(dòng)糾錯(cuò)，不要求檢錯(cuò)重發(fā)，因而延時(shí)小，）由于能自動(dòng)糾錯(cuò)，不要求檢錯(cuò)重發(fā)，因而延時(shí)小， 實(shí)時(shí)性好。實(shí)時(shí)性好。3 3）隨著糾錯(cuò)能力的增強(qiáng)，譯碼設(shè)備也變得復(fù)雜。）隨著糾錯(cuò)能力的增強(qiáng)，譯碼設(shè)備也變得復(fù)雜。 (3) 混合糾錯(cuò)混合糾錯(cuò) 對發(fā)送端進(jìn)行適當(dāng)?shù)木幋a。當(dāng)對發(fā)送端進(jìn)行適當(dāng)?shù)木幋a。當(dāng)錯(cuò)誤不嚴(yán)重錯(cuò)誤不嚴(yán)重，在碼的，在碼的糾錯(cuò)能力范圍之內(nèi)時(shí)，采用自動(dòng)糾錯(cuò)；當(dāng)產(chǎn)生的糾錯(cuò)能力范圍之內(nèi)時(shí)，采用自動(dòng)糾錯(cuò)；當(dāng)產(chǎn)生的差錯(cuò)超差錯(cuò)超出碼的糾錯(cuò)能力范圍出碼的糾錯(cuò)能力范圍時(shí)，通過反饋系統(tǒng)要求發(fā)端重發(fā)。時(shí)，通過反饋系統(tǒng)要求發(fā)端重發(fā)。(1) 按按功能功能分：分： 檢錯(cuò)碼：僅能檢測誤碼檢錯(cuò)碼：僅能檢測誤碼 糾錯(cuò)碼：可糾正誤碼糾

8、錯(cuò)碼：可糾正誤碼 糾刪碼：兼糾錯(cuò)和檢錯(cuò)能力糾刪碼：兼糾錯(cuò)和檢錯(cuò)能力糾錯(cuò)碼糾錯(cuò)碼1 1 糾錯(cuò)碼的分類糾錯(cuò)碼的分類(2) 按信息碼元與監(jiān)督碼元之間的檢驗(yàn)關(guān)系分： - 線性碼線性碼：滿足線性關(guān)系- 非線性碼非線性碼：不存在線性關(guān)系 (3) 按信息碼元與監(jiān)督碼元之間的按信息碼元與監(jiān)督碼元之間的約束方式約束方式不同分：不同分： 分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關(guān)。分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關(guān)。 卷積碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相卷積碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相關(guān)，而且與前面碼組的信息碼元有關(guān)。關(guān)，而且與前面碼組的信息碼元有關(guān)。碼與碼相互影響不能碼與

9、碼相互影響不能分開，又稱數(shù)碼或鏈碼分開，又稱數(shù)碼或鏈碼重點(diǎn)討論線性分組碼重點(diǎn)討論線性分組碼(4) 按信息碼元在編碼后是否保持原形式不變：按信息碼元在編碼后是否保持原形式不變： 即：根據(jù)信息元在分組碼中的位置分為系統(tǒng)碼，非系統(tǒng)碼系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內(nèi)有確定位置，系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內(nèi)有確定位置，編碼后的信息碼元保持不變；編碼后的信息碼元保持不變；非系統(tǒng)碼：信息位打亂，與編碼前不同。非系統(tǒng)碼：信息位打亂，與編碼前不同。(5)(5)按糾正差錯(cuò)的類型可分為：按糾正差錯(cuò)的類型可分為： 糾糾隨機(jī)錯(cuò)誤隨機(jī)錯(cuò)誤碼碼 糾糾突發(fā)錯(cuò)誤突發(fā)錯(cuò)誤碼碼 糾糾隨機(jī)和突發(fā)錯(cuò)誤隨機(jī)和突發(fā)錯(cuò)誤碼碼非線性卷

10、積碼線性樹碼非線性非循環(huán)碼循環(huán)碼線性分組碼糾錯(cuò)碼糾錯(cuò)碼按結(jié)構(gòu)分類如下：糾錯(cuò)碼按結(jié)構(gòu)分類如下： 1 1 糾錯(cuò)碼的分類糾錯(cuò)碼的分類(續(xù)續(xù))l 分組碼的表示方法：分組碼的表示方法： （二元分組碼）（二元分組碼） 信息碼組由信息碼組由 k 個(gè)信息碼元組成，共有個(gè)信息碼元組成，共有 2k 個(gè)不同的個(gè)不同的信息碼組；信息碼組；信息位信息位 附加附加 個(gè)校驗(yàn)碼元，每個(gè)校驗(yàn)碼元是該信息個(gè)校驗(yàn)碼元，每個(gè)校驗(yàn)碼元是該信息碼組的某些信息碼元模碼組的某些信息碼元模2和；和；校驗(yàn)位或監(jiān)督位校驗(yàn)位或監(jiān)督位 編碼器輸出長度為編碼器輸出長度為n的碼字；的碼字；碼字的數(shù)目共有碼字的數(shù)目共有 2k ；這這2k 個(gè)碼字的集合稱為個(gè)

11、碼字的集合稱為 (n,k) 分組碼；分組碼；rnk2 2 糾錯(cuò)碼的基本概念糾錯(cuò)碼的基本概念信息傳輸率（碼率），編碼效率信息傳輸率（碼率），編碼效率o對 二進(jìn)制(n, k)線性分組碼，合法碼字?jǐn)?shù)為2k，可用編碼空間的序列數(shù)為2n個(gè)。許用序列 ，禁用序列 o任一種2k信息集合到二進(jìn)制序列集合(2n)的映射都是一種(n, k)碼。因此總共可能的編碼方案有 種。22knC2 2 糾錯(cuò)碼的基本概念（續(xù)）糾錯(cuò)碼的基本概念（續(xù)）o發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問題：編碼方案太多，以至全局搜索是不可能的。現(xiàn)實(shí)的做法是對編碼方案加以一定的約束，在一個(gè)子集中尋找局部最優(yōu)。這種約束即要能包含盡可能好的碼，又要便

12、于分析，便于譯碼。o線性分組碼是最具實(shí)用價(jià)值的一類碼，比如漢明碼、循環(huán)碼、BCH碼、RS碼等。2 2 糾錯(cuò)碼的基本概念糾錯(cuò)碼的基本概念（續(xù)）（續(xù)）2 2 糾錯(cuò)碼的基本概念糾錯(cuò)碼的基本概念（續(xù)）（續(xù)）對信道編碼的一般要求是：對信道編碼的一般要求是：糾錯(cuò)檢錯(cuò)能力強(qiáng)；糾錯(cuò)檢錯(cuò)能力強(qiáng)；信息傳輸率高；信息傳輸率高；編碼規(guī)律簡單，實(shí)現(xiàn)設(shè)備簡單且費(fèi)用合理；編碼規(guī)律簡單，實(shí)現(xiàn)設(shè)備簡單且費(fèi)用合理；與信道的差錯(cuò)統(tǒng)計(jì)特性相匹配。與信道的差錯(cuò)統(tǒng)計(jì)特性相匹配。 漢明距離漢明距離niiiiccc21cnjjjjccc21cnkjijikkccd1),(cc漢明距離滿足距離公理漢明距離滿足距離公理(1) 非負(fù)性非負(fù)性 對稱

13、性對稱性(3) 三角不等式三角不等式 0),(jidcc),(),(ijjiddcccc),(),(),(jllijidddcccccc2 2 糾錯(cuò)碼的基本概念糾錯(cuò)碼的基本概念漢明重量漢明重量 nkiikcW1)(cniiiiccc21c碼碼C 的最小漢明距離的最小漢明距離 jiddjiji,: ),(minminCcccc),()()(),(10cccccclljijnkijidWWccdkk線性分組碼的最小漢明距離等于非零碼字的最小重量。線性分組碼的最小漢明距離等于非零碼字的最小重量。2 2 糾錯(cuò)碼的基本概念糾錯(cuò)碼的基本概念3 3 線性分組碼線性分組碼3272163215314CCCCCC

14、CCCCCCC00007326215321431CCCCCCCCCCCCC3.1 3.1 校驗(yàn)矩陣與生成矩陣校驗(yàn)矩陣與生成矩陣 7654321CCCCCCCC(1) 校驗(yàn)矩陣校驗(yàn)矩陣000010001100100011001011100011017654321CCCCCCCTT0HC0CHTIQH 1011000111010011000100110001H1234567 ,c c c c c c cC C0,0,0,00 0則則TTH HC C0 0TCH0CH0令令l 被稱為被稱為校驗(yàn)矩陣校驗(yàn)矩陣。l 對對 線性分組碼，校驗(yàn)矩陣為線性分組碼，校驗(yàn)矩陣為 維矩陣。維矩陣。l對于系統(tǒng)碼，校驗(yàn)矩陣

15、可以表示為對于系統(tǒng)碼，校驗(yàn)矩陣可以表示為H, )n k（()nkn=HQI其中 為 維矩陣， 為 維單位矩陣。Q()nkk()()nknkI3272163215314332211CCCCCCCCCCCCCCCCCCC3272163215314CCCCCCCCCCCCCl由校驗(yàn)方程，得到由校驗(yàn)方程，得到(2) (2) 生成矩陣生成矩陣101110011100100111001321CCCCPIG l令令123 ,c c cm100111001001110011101GIPCmG其中其中 為為 維矩陣，維矩陣， 為為 維單位矩陣。維單位矩陣。l 被稱為被稱為生成矩陣生成矩陣。l 對對 線性分組碼，

16、生成矩陣為線性分組碼，生成矩陣為 維矩陣。維矩陣。l對于系統(tǒng)碼，生成矩陣可以表示為對于系統(tǒng)碼，生成矩陣可以表示為G, )n k（knP()knkkkGIPIl把生成矩陣的每一行用一個(gè)行向量把生成矩陣的每一行用一個(gè)行向量 來來表示，則生成矩陣可以表示為表示，則生成矩陣可以表示為12kmmmm12kGGGG1kiiimCmGG,1,2,iikG Gl令令 ，則，則l由于生成矩陣由于生成矩陣GG的每一行都是一個(gè)碼字，所以的每一行都是一個(gè)碼字，所以G G 的每的每行都滿足行都滿足 ，則有，則有l(wèi)對于標(biāo)準(zhǔn)形式的校驗(yàn)矩陣和監(jiān)督矩陣，有對于標(biāo)準(zhǔn)形式的校驗(yàn)矩陣和監(jiān)督矩陣，有TTi iHG0HG0THG0HG0

17、TTT+Q QI II IP PQ QP P0 0HGTQPQP(3) (3) 校驗(yàn)矩陣和生成矩陣的關(guān)系校驗(yàn)矩陣和生成矩陣的關(guān)系l線性分組碼的封閉性線性分組碼的封閉性：線性分組碼中任意兩個(gè)碼字之：線性分組碼中任意兩個(gè)碼字之后仍然是該碼的碼字。后仍然是該碼的碼字。證明：設(shè)證明：設(shè) 和和 分別是碼分別是碼 中的兩個(gè)碼字，因此有中的兩個(gè)碼字，因此有即即 滿足監(jiān)督方程，所以是碼滿足監(jiān)督方程，所以是碼 中的一個(gè)碼字。中的一個(gè)碼字。TT1TTTT1212TT2(+)H HC C0 0H H C CC CH HC CH HC C0 0H HC C0 01C CC CC C2C C12+CCCC例：重復(fù)碼是一

18、個(gè)（例：重復(fù)碼是一個(gè)（3,1）線性分組碼。其生成矩陣為）線性分組碼。其生成矩陣為111G1111111321mmmmCCCC例：（例：（4,3）偶校驗(yàn)碼是一個(gè)（）偶校驗(yàn)碼是一個(gè)（4,3）線性分組碼，其生成）線性分組碼，其生成矩陣為矩陣為 110010101001G1100101010013213213214321mmmmmmmmmCCCCC例例 已知生成矩陣為已知生成矩陣為 求生成的線性分組碼及由求生成的線性分組碼及由H 生成的線性生成的線性分組碼。分組碼。 101110011100100111001G1110100111110100111010100111011001110100011101

19、0011010011101000111010010000000000CmmGC 1000110010001100101110001101IQHQPT101111100111PPIG 101110011100100111001G1000110010001100101110001101IQH110100001101001110010101000111111111111111010011101101001110111000101100101100010111010011101010011101001100010110000111010011101100010110010110001010100111

20、010000111010011001011000100001011000100000000000Cm關(guān)于碼的最小距離與糾、檢錯(cuò)能力的關(guān)系有以下結(jié)論：關(guān)于碼的最小距離與糾、檢錯(cuò)能力的關(guān)系有以下結(jié)論：對于（對于（n，k）線性分組碼，設(shè)）線性分組碼，設(shè) 為最小漢明距離。為最小漢明距離。（）（）這組碼有糾正這組碼有糾正 u 個(gè)錯(cuò)誤的充要條件是個(gè)錯(cuò)誤的充要條件是mind12min uduu2u+1對于一個(gè)二進(jìn)制對稱信道，當(dāng)輸入為對于一個(gè)二進(jìn)制對稱信道，當(dāng)輸入為2k個(gè)等可能的個(gè)等可能的n長長碼字，則最大后驗(yàn)概率準(zhǔn)則等效于最小漢明距離譯碼準(zhǔn)則。碼字，則最大后驗(yàn)概率準(zhǔn)則等效于最小漢明距離譯碼準(zhǔn)則。 3.2 3

21、.2 線性分組碼的糾、檢錯(cuò)能力線性分組碼的糾、檢錯(cuò)能力 lll+1（）具有檢測（）具有檢測l個(gè)錯(cuò)誤的充要條件是個(gè)錯(cuò)誤的充要條件是1min lduutlt+l+1（）具有糾正（）具有糾正 t 個(gè)錯(cuò)誤，同時(shí)可以發(fā)現(xiàn)個(gè)錯(cuò)誤，同時(shí)可以發(fā)現(xiàn)l個(gè)錯(cuò)誤的充分必個(gè)錯(cuò)誤的充分必要條件為要條件為1minltd碼的糾錯(cuò)能力碼的糾錯(cuò)能力u與碼字的長度與碼字的長度n和消息數(shù)和消息數(shù)M滿足以下關(guān)系：滿足以下關(guān)系：02uinniMC3.3 校驗(yàn)矩陣與最小距離的關(guān)系校驗(yàn)矩陣與最小距離的關(guān)系 對于（對于（n，k）線性分組碼：校驗(yàn)矩陣）線性分組碼：校驗(yàn)矩陣H中的任意中的任意t列線列線性無關(guān)而性無關(guān)而t +1列線性相關(guān)，則碼的最小

22、距離列線性相關(guān)，則碼的最小距離(碼字的最小碼字的最小重量重量)為為t+1。反過來說，若碼的最小距離。反過來說，若碼的最小距離(碼字的最小碼字的最小重量重量)為為t+1則則H 的任意的任意t列線性無關(guān)而列線性無關(guān)而t+1列線性相關(guān)。列線性相關(guān)。3.4 線性分組碼的伴隨式線性分組碼的伴隨式 0CHTR=C+E E=e1 e2 en TTTTTEHCHEHHCERHS)(1) ，說明，說明R 是一個(gè)碼字是一個(gè)碼字;2) 2) ，說明，說明R 不是碼字，傳輸過程產(chǎn)生了誤碼。不是碼字，傳輸過程產(chǎn)生了誤碼。0S S0S STTS = HRTTS = HEl 令令12121nTTniiinee=eeSHEH

23、HHHSHEHHHH12n= eeeE E12n=HHHHHHHHiH HH H 則則（其中（其中 表示表示 的列向量）的列向量） 結(jié)論：結(jié)論：1) 當(dāng)傳輸過程沒有錯(cuò)誤時(shí)當(dāng)傳輸過程沒有錯(cuò)誤時(shí) ，即，即 ， 2)2)當(dāng)發(fā)生一位錯(cuò)誤時(shí)，當(dāng)發(fā)生一位錯(cuò)誤時(shí)， 是校驗(yàn)矩陣的某一列。是校驗(yàn)矩陣的某一列。3)3)當(dāng)發(fā)生多個(gè)錯(cuò)誤時(shí)，當(dāng)發(fā)生多個(gè)錯(cuò)誤時(shí)， 為校驗(yàn)矩陣對應(yīng)列的模為校驗(yàn)矩陣對應(yīng)列的模2 2和。和。0 00=E ET0S STS STS S例例： 設(shè)設(shè)(7,3)線性分組碼的校驗(yàn)矩陣為線性分組碼的校驗(yàn)矩陣為1011000111010011000100110001H（1）接收碼字）接收碼字R R=(1010

24、011)，TT101011000011110100001100010000110001011 S = HR傳輸過程中沒有誤碼，傳輸過程中沒有誤碼，=CRCR（2）接收碼字）接收碼字R R=(1110011)，TT111011000011110100101100010100110001111 S = HR ，第，第2位出錯(cuò)，位出錯(cuò)，= (1010011)=+CRECRET2SH(0100000)=E E（3）接收碼字）接收碼字R R=(0011011)，TT001011000011110100111100010100110001011 S = HR與與 中的任一列都不相同，中的任一列都不相同，T

25、SHT142756SHHHHHH不能確定到底是哪兩位出錯(cuò)，不能正確譯碼。不能確定到底是哪兩位出錯(cuò)，不能正確譯碼。niiinnnnTTeeeeeee122112121HHHHHHHHES線性分組碼的伴隨式譯碼線性分組碼的伴隨式譯碼 ERCEEHST編碼C=mG計(jì)算Em輸出CER0RHTCRECnoyes輸出R02uinniMC若（若（n，k）線性分組碼能夠糾正）線性分組碼能夠糾正 u 個(gè)錯(cuò)誤，則其校驗(yàn)位個(gè)錯(cuò)誤，則其校驗(yàn)位的數(shù)目必須滿足的數(shù)目必須滿足 uiinknC02完備碼完備碼l漢明碼是一種能夠糾正單個(gè)錯(cuò)誤的完備碼。漢明碼是一種能夠糾正單個(gè)錯(cuò)誤的完備碼。漢明碼最小碼距漢明碼最小碼距設(shè)監(jiān)督碼共有

26、設(shè)監(jiān)督碼共有m位，對于漢明碼必然有位，對于漢明碼必然有 。通常漢明碼可以表示成通常漢明碼可以表示成 。mn = 21mm(21,21)mmin3d4 漢明碼漢明碼 在同樣的糾錯(cuò)能力下，漢明碼的碼率是最高的在同樣的糾錯(cuò)能力下，漢明碼的碼率是最高的 12111212mmmmRl漢明碼監(jiān)督矩陣構(gòu)成的兩種方式：漢明碼監(jiān)督矩陣構(gòu)成的兩種方式：構(gòu)成構(gòu)成 H H 陣的標(biāo)準(zhǔn)形式，陣的標(biāo)準(zhǔn)形式， 。按按m位的二進(jìn)制數(shù)的位的二進(jìn)制數(shù)的自然自然順序從左到右排列（不包順序從左到右排列（不包括全括全0列）。當(dāng)發(fā)生可糾的單個(gè)錯(cuò)誤時(shí)，伴隨式為列）。當(dāng)發(fā)生可糾的單個(gè)錯(cuò)誤時(shí)，伴隨式為 H H 陣中對應(yīng)的列，譯碼比較方便。陣中對

27、應(yīng)的列，譯碼比較方便。非標(biāo)準(zhǔn)形式的監(jiān)督矩陣可以通過列置換變成標(biāo)準(zhǔn)形非標(biāo)準(zhǔn)形式的監(jiān)督矩陣可以通過列置換變成標(biāo)準(zhǔn)形式的監(jiān)督矩陣，糾錯(cuò)能力保持不變。式的監(jiān)督矩陣，糾錯(cuò)能力保持不變。mHQIl如果給漢明碼添加一位奇偶校驗(yàn)位，可得到擴(kuò)展?jié)h明碼：如果給漢明碼添加一位奇偶校驗(yàn)位，可得到擴(kuò)展?jié)h明碼： 信息位保持不變，監(jiān)督位增加一位。信息位保持不變，監(jiān)督位增加一位。 最小碼距最小碼距 ， 可糾正一位錯(cuò)誤，可糾正一位錯(cuò)誤，同時(shí)發(fā)現(xiàn)兩位錯(cuò)誤。同時(shí)發(fā)現(xiàn)兩位錯(cuò)誤。min4d111000HH1214mindl擴(kuò)展?jié)h明碼的監(jiān)督方程：擴(kuò)展?jié)h明碼的監(jiān)督方程： l循環(huán)碼是線性分組碼的一個(gè)重要子集。循環(huán)碼是線性分組碼的一個(gè)重要子集

28、。l循環(huán)碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)碼除了具有線性分組碼的一般性質(zhì)外，還具有循循環(huán)性環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。到的碼組仍然是許用碼組。 l循環(huán)碼有嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)，檢錯(cuò)和糾錯(cuò)能力較循環(huán)碼有嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)，檢錯(cuò)和糾錯(cuò)能力較強(qiáng)，而且編碼和解碼設(shè)備都不太復(fù)雜。強(qiáng)，而且編碼和解碼設(shè)備都不太復(fù)雜。5 循環(huán)碼循環(huán)碼5 循環(huán)碼循環(huán)碼 1)對于二進(jìn)制碼，碼多項(xiàng)式的每個(gè)系數(shù)不是對于二進(jìn)制碼，碼多項(xiàng)式的每個(gè)系數(shù)不是0就是就是1。 2) 僅是碼元僅是碼元位置的標(biāo)記。我們并不關(guān)心位置的標(biāo)記。我們并不關(guān)心 的

29、取值。的取值。 l設(shè)循環(huán)碼的碼字為設(shè)循環(huán)碼的碼字為 ，用碼多項(xiàng)式表，用碼多項(xiàng)式表示為示為120nnCccc121210( ).nnnnC xcxcxc xcl碼字（碼字（1100101）可以表示為：）可以表示為：xx 654321652( )11001011C xxxxxxxxxx l循環(huán)碼的循環(huán)特性可以用碼多項(xiàng)式來證明。循環(huán)碼的循環(huán)特性可以用碼多項(xiàng)式來證明。,mpQpnnn()mpn模l在整數(shù)運(yùn)算中，有在整數(shù)運(yùn)算中，有模模n運(yùn)算運(yùn)算。若一個(gè)整數(shù)。若一個(gè)整數(shù)m可以表示為可以表示為: 則則在模在模n運(yùn)算下，一整數(shù)運(yùn)算下，一整數(shù)m等于其被等于其被n除所得的余數(shù)。除所得的余數(shù)。5 循環(huán)碼循環(huán)碼l在碼

30、多項(xiàng)式運(yùn)算中也有類似的按模運(yùn)算法則。在碼多項(xiàng)式運(yùn)算中也有類似的按模運(yùn)算法則。l若一任意多項(xiàng)式若一任意多項(xiàng)式F(x)被一個(gè)被一個(gè)n次多項(xiàng)式次多項(xiàng)式N(x)除，得到商除，得到商式式Q(x)和一個(gè)次數(shù)小于和一個(gè)次數(shù)小于n的余式的余式R(x)，也就是：，也就是： 則可以寫為：則可以寫為： ( )()( )( )( )F xR XQ xN xN x( )( )( )F xR xN x模l在循環(huán)碼中，若在循環(huán)碼中，若 是一個(gè)長為是一個(gè)長為n的許用碼字，則的許用碼字，則 在模在模 運(yùn)算下，也是一個(gè)許用碼字。運(yùn)算下，也是一個(gè)許用碼字。( )C x( )ix C x1nx 例例 某循環(huán)碼的一個(gè)碼字為某循環(huán)碼的一

31、個(gè)碼字為1100101，則，則 若將此碼左移一位，得：若將此碼左移一位，得： 對應(yīng)的碼字為對應(yīng)的碼字為1001011，與將碼字，與將碼字1100101循環(huán)左移循環(huán)左移一位相同。一位相同。 652( )1C xxxx763( )xC xxxxx763763mod11xxxxxxxx5 循環(huán)碼循環(huán)碼012211)(cxcxcxcxCnn102112) 1 ()()(nnncxcxcxcxxCxC2120132)2()()(nnnncxcxcxcxCxxC1223101) 1()()(cxcxcxcxCxxCnnn5 循環(huán)碼循環(huán)碼l從碼中取出一個(gè)前面從碼中取出一個(gè)前面k-1位都是位都是0的碼字，定義

32、這個(gè)碼的碼字，定義這個(gè)碼字的碼多項(xiàng)式為生成多項(xiàng)式字的碼多項(xiàng)式為生成多項(xiàng)式 。l 在在 循環(huán)碼中，除了全循環(huán)碼中，除了全0碼字以外，其他碼字的連碼字以外，其他碼字的連0個(gè)數(shù)最多只有個(gè)數(shù)最多只有k-1個(gè)。個(gè)。( , )n k( )g xnkl 碼多項(xiàng)式的次數(shù)為碼多項(xiàng)式的次數(shù)為 ，且常數(shù)項(xiàng)不為，且常數(shù)項(xiàng)不為0。5 循環(huán)碼循環(huán)碼信息比特碼字（循環(huán)1）信息比特碼字(循環(huán)2）信息比特碼字000100100101011010001011110000010110010110010110001100011000101101100011000100011 0100011110011010110111100011101010011101110101001110