《通信原理》10信道編碼和差錯控制

1、信道編碼和差錯控制信道編碼和差錯控制糾錯編碼糾錯編碼線性分組碼線性分組碼循環(huán)碼循環(huán)碼22022-7-5基本要求基本要求了解信道編碼的目的和要求了解信道編碼的目的和要求掌握糾錯編碼的基本原理和糾錯編碼系統(tǒng)的性掌握糾錯編碼的基本原理和糾錯編碼系統(tǒng)的性能分析能分析熟悉常用的簡單編碼熟悉常用的簡單編碼掌握線性分組碼、循環(huán)碼的編碼和解碼方法掌握線性分組碼、循環(huán)碼的編碼和解碼方法32022-7-5基本內(nèi)容基本內(nèi)容信道編碼信道編碼概念概念，指數(shù)字信號為了適應(yīng)信道的傳指數(shù)字信號為了適應(yīng)信道的傳輸特性，達到高效可靠的傳輸而進行的相應(yīng)的輸特性，達到高效可靠的傳輸而進行的相應(yīng)的信號處理過程。信號處理過程。信道編碼的

2、信道編碼的目的目的：降低誤碼率，降低誤碼率，提高信號傳輸提高信號傳輸?shù)目煽啃?。的可靠性。信道編碼的信道編碼的基本原理基本原理是在信號碼元序列中增加是在信號碼元序列中增加監(jiān)督碼元，并利用監(jiān)督碼元去發(fā)現(xiàn)或糾正傳輸監(jiān)督碼元，并利用監(jiān)督碼元去發(fā)現(xiàn)或糾正傳輸中發(fā)生的錯誤。中發(fā)生的錯誤。42022-7-5基本內(nèi)容基本內(nèi)容在信道編碼只有發(fā)現(xiàn)錯碼能力而無糾正錯在信道編碼只有發(fā)現(xiàn)錯碼能力而無糾正錯碼能力時，必須結(jié)合其他措施來糾正錯碼，碼能力時，必須結(jié)合其他措施來糾正錯碼，否則只能將發(fā)現(xiàn)為錯碼的碼元刪除。這些否則只能將發(fā)現(xiàn)為錯碼的碼元刪除。這些手段統(tǒng)稱為手段統(tǒng)稱為差錯控制差錯控制。差錯控制編碼是一種信道編碼。差錯

3、控制編碼是一種信道編碼。52022-7-5基本內(nèi)容基本內(nèi)容 信道的分類信道的分類v 隨機信道隨機信道v 突發(fā)信道突發(fā)信道v 混合信道混合信道62022-7-5基本內(nèi)容基本內(nèi)容常用的差錯控制方式主要有常用的差錯控制方式主要有v檢錯重發(fā)（簡稱檢錯重發(fā)（簡稱ARQ）v前向糾錯（簡稱前向糾錯（簡稱FECFEC）v混合糾錯（簡稱混合糾錯（簡稱HECHEC）目的：目的：克服線路傳輸中出現(xiàn)的數(shù)據(jù)差錯，實現(xiàn)克服線路傳輸中出現(xiàn)的數(shù)據(jù)差錯，實現(xiàn) 調(diào)制解調(diào)器至終端調(diào)制解調(diào)器的無差錯數(shù)調(diào)制解調(diào)器至終端調(diào)制解調(diào)器的無差錯數(shù) 據(jù)傳送。據(jù)傳送。72022-7-5基本內(nèi)容基本內(nèi)容差錯控制編碼方法差錯控制編碼方法/ /糾錯編碼

4、方法：糾錯編碼方法： 為了在接收端能夠發(fā)現(xiàn)或糾正錯碼，為了在接收端能夠發(fā)現(xiàn)或糾正錯碼，在發(fā)送碼元序列中加入一些差錯控制碼在發(fā)送碼元序列中加入一些差錯控制碼元（監(jiān)督碼元元（監(jiān)督碼元/監(jiān)督位）。監(jiān)督位）。 加入的監(jiān)督碼元越多，糾加入的監(jiān)督碼元越多，糾/檢錯的能檢錯的能力越強，傳輸效率越低，從而可以用降力越強，傳輸效率越低，從而可以用降低傳輸效率換取傳輸可靠性的提高。低傳輸效率換取傳輸可靠性的提高。82022-7-5基本內(nèi)容基本內(nèi)容差錯控制編碼分類：差錯控制編碼分類： 按照差錯控制編碼的不同功能分為按照差錯控制編碼的不同功能分為檢錯碼、糾錯碼和糾刪碼；檢錯碼、糾錯碼和糾刪碼； 按照信息碼元和附加的監(jiān)

5、督碼元之間的檢驗關(guān)系分為按照信息碼元和附加的監(jiān)督碼元之間的檢驗關(guān)系分為線性碼和非線性碼；線性碼和非線性碼； 按照信息碼元和監(jiān)督碼元之間的約束方式不同分為按照信息碼元和監(jiān)督碼元之間的約束方式不同分為分組碼和卷積碼；分組碼和卷積碼；92022-7-5基本內(nèi)容基本內(nèi)容差錯控制編碼分類：差錯控制編碼分類： 按照信息碼元在編碼后是否保持原來的形式不變分為按照信息碼元在編碼后是否保持原來的形式不變分為系統(tǒng)碼和非系統(tǒng)碼；系統(tǒng)碼和非系統(tǒng)碼； 按照糾正錯誤的類型不同分為按照糾正錯誤的類型不同分為糾正隨機錯誤的碼和糾正突發(fā)錯誤的碼；糾正隨機錯誤的碼和糾正突發(fā)錯誤的碼； 按照構(gòu)造差錯控制編碼的數(shù)學(xué)方法分為按照構(gòu)造差

6、錯控制編碼的數(shù)學(xué)方法分為代數(shù)碼、幾何碼和算術(shù)碼；代數(shù)碼、幾何碼和算術(shù)碼；按照每個碼元取值不同分為按照每個碼元取值不同分為 二進制和多進制碼。二進制和多進制碼。102022-7-5基本內(nèi)容基本內(nèi)容碼率：碼率：編碼序列中信息碼元數(shù)量編碼序列中信息碼元數(shù)量k k和總碼元數(shù)量和總碼元數(shù)量n n之比：之比：k/nk/n冗余度：冗余度： 監(jiān)督碼元數(shù)（監(jiān)督碼元數(shù)（n-kn-k）和）和總總碼元數(shù)量碼元數(shù)量n n之比之比: : ( (n-k)/nn-k)/n112022-7-5糾錯編碼糾錯編碼糾錯編碼中的基本概念糾錯編碼中的基本概念v糾錯編碼：具有檢錯能力或糾錯能力的編碼。糾錯編碼：具有檢錯能力或糾錯能力的編碼

7、。 v糾錯編碼分為糾錯編碼分為分組碼分組碼和和卷積碼卷積碼兩大類。兩大類。v分組碼分組碼：將若干監(jiān)督碼元附加在一組信息位上：將若干監(jiān)督碼元附加在一組信息位上構(gòu)成一個具有糾錯能力的獨立碼組，并且監(jiān)督構(gòu)成一個具有糾錯能力的獨立碼組，并且監(jiān)督位僅監(jiān)督本組中的信息碼元。位僅監(jiān)督本組中的信息碼元。v分組碼用符號（分組碼用符號（n,k）表示，其中）表示，其中n是碼組長度，是碼組長度，k為信息碼元數(shù)目，為信息碼元數(shù)目，r=n-k為監(jiān)督碼元數(shù)目。為監(jiān)督碼元數(shù)目。122022-7-5糾錯編碼糾錯編碼糾錯編碼中的基本概念糾錯編碼中的基本概念v由代數(shù)關(guān)系確定監(jiān)督位的分組碼稱為由代數(shù)關(guān)系確定監(jiān)督位的分組碼稱為代數(shù)碼代

8、數(shù)碼。v在代數(shù)碼中，若監(jiān)督位和信息位的關(guān)系是由在代數(shù)碼中，若監(jiān)督位和信息位的關(guān)系是由線性方程式?jīng)Q定的，則稱這種編碼為線性方程式?jīng)Q定的，則稱這種編碼為線性分線性分組碼組碼。例如：奇偶監(jiān)督碼、漢明碼、循環(huán)碼。例如：奇偶監(jiān)督碼、漢明碼、循環(huán)碼。132022-7-5糾錯編碼糾錯編碼糾錯編碼中的基本概念糾錯編碼中的基本概念v漢明碼漢明碼：能夠糾正：能夠糾正1位錯碼的效率較高的線性位錯碼的效率較高的線性 分組碼。分組碼。v循環(huán)碼循環(huán)碼：就有循環(huán)性的線性分組碼。：就有循環(huán)性的線性分組碼。vBCH碼碼：能夠糾正多個隨機錯碼的循環(huán)碼。：能夠糾正多個隨機錯碼的循環(huán)碼。vRS碼碼：具有很強糾錯能力的多進制：具有很強

9、糾錯能力的多進制BCH碼。碼。142022-7-5糾錯編碼糾錯編碼糾錯編碼中的基本概念糾錯編碼中的基本概念v碼長：一個碼組中碼元的數(shù)目。碼長：一個碼組中碼元的數(shù)目。v碼重：一個碼組中碼重：一個碼組中“1”的個數(shù)。的個數(shù)。v碼距碼距d：兩個等長碼組之間對應(yīng)位不同的個數(shù)。：兩個等長碼組之間對應(yīng)位不同的個數(shù)。v最小碼距最小碼距 ：碼組集合中所有碼距的最小值。：碼組集合中所有碼距的最小值。0d152022-7-5糾錯編碼糾錯編碼糾錯編碼糾錯編碼糾檢錯能力與最小碼距糾檢錯能力與最小碼距 的關(guān)系的關(guān)系：0dv一個碼組內(nèi)檢測一個碼組內(nèi)檢測e個誤碼：個誤碼：v一個碼組內(nèi)糾正一個碼組內(nèi)糾正t t個誤碼：個誤碼：

10、v一個碼組內(nèi)糾正一個碼組內(nèi)糾正t t個誤碼同時檢測個誤碼同時檢測 e e（etet）個誤碼：個誤碼： 10 ed120 td)(10teted162022-7-5糾錯編碼糾錯編碼碼距與檢錯和糾錯能力的關(guān)系：碼距與檢錯和糾錯能力的關(guān)系： 0d0dBAABett0123012345(a)(b)ABett1(c)172022-7-5糾錯編碼糾錯編碼糾錯編碼系統(tǒng)的性能：糾錯編碼系統(tǒng)的性能：v誤碼率性能和帶寬的關(guān)系：誤碼率性能和帶寬的關(guān)系：采用編碼降低采用編碼降低誤碼率所付出的代價是帶寬的增大。誤碼率所付出的代價是帶寬的增大。v功率和帶寬的關(guān)系：功率和帶寬的關(guān)系：采用編碼以節(jié)省功率，采用編碼以節(jié)省功率，

11、并保持誤碼率不變，付出的代價也是帶寬并保持誤碼率不變，付出的代價也是帶寬的增大。的增大。182022-7-5糾錯編碼糾錯編碼糾錯編碼系統(tǒng)的性能：糾錯編碼系統(tǒng)的性能：v傳輸速率和帶寬的關(guān)系：傳輸速率和帶寬的關(guān)系：對于給定的傳輸系對于給定的傳輸系統(tǒng)，其傳輸速率和信噪比統(tǒng)，其傳輸速率和信噪比 的關(guān)系為的關(guān)系為0/bEn0000(1/)bsssBEPTPPnnnTn R 提高傳輸速率，采用編碼以保持誤碼提高傳輸速率，采用編碼以保持誤碼率不變，代價是帶寬增大。率不變，代價是帶寬增大。192022-7-5糾錯編碼糾錯編碼糾錯編碼系統(tǒng)的性能：糾錯編碼系統(tǒng)的性能：v編碼增益：編碼增益：在保持誤碼率恒定的條件下

12、，采在保持誤碼率恒定的條件下，采用糾錯編碼所節(jié)省的信噪比用糾錯編碼所節(jié)省的信噪比0/bEn00(/)(/)dBbubcGEnEndB 未編碼時的信噪比未編碼時的信噪比編碼后所需的信噪比編碼后所需的信噪比202022-7-5奇偶監(jiān)督碼奇偶監(jiān)督碼 監(jiān)督位只有監(jiān)督位只有1位，碼率為位，碼率為 k/(k+1) 奇偶監(jiān)督碼能夠檢測奇數(shù)個錯碼奇偶監(jiān)督碼能夠檢測奇數(shù)個錯碼 分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼 在奇數(shù)監(jiān)督碼中，監(jiān)督位使碼組中在奇數(shù)監(jiān)督碼中，監(jiān)督位使碼組中“1”的個的個數(shù)數(shù) 為奇數(shù)為奇數(shù)212022-7-5奇偶監(jiān)督碼奇偶監(jiān)督碼在偶數(shù)監(jiān)督碼中，監(jiān)督位使碼組中在偶數(shù)監(jiān)督碼中，監(jiān)督位

13、使碼組中“1”的個數(shù)的個數(shù)為偶數(shù)。在接收端檢測時，將接收碼組按照式為偶數(shù)。在接收端檢測時，將接收碼組按照式求求“模模2和和”，若計算結(jié)果為，若計算結(jié)果為“1”就說明有錯碼，就說明有錯碼，為為“0”就認(rèn)為無錯碼。（就認(rèn)為無錯碼。（a0為監(jiān)督位，其余位為監(jiān)督位，其余位為信息位）為信息位）1200nnaaa222022-7-5二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼 方陣碼或矩形碼方陣碼或矩形碼 構(gòu)造方法構(gòu)造方法：先將若干奇偶監(jiān)督碼按行排列成：先將若干奇偶監(jiān)督碼按行排列成矩陣，再按列增加第二維監(jiān)督位矩陣，再按列增加第二維監(jiān)督位 碼率為：碼率為： 有可能檢測出偶數(shù)個錯碼有可能檢測出偶數(shù)個錯碼 適合檢測突發(fā)錯碼，能

14、夠糾正部分錯碼適合檢測突發(fā)錯碼，能夠糾正部分錯碼(1)(1)km nnmn232022-7-5線性分組碼線性分組碼代數(shù)碼代數(shù)碼是利用代數(shù)關(guān)系式產(chǎn)生監(jiān)督位的編碼。是利用代數(shù)關(guān)系式產(chǎn)生監(jiān)督位的編碼。線性分組碼線性分組碼是代數(shù)碼的一種，其監(jiān)督位和信息是代數(shù)碼的一種，其監(jiān)督位和信息位的關(guān)系由線性方程決定。位的關(guān)系由線性方程決定。漢明碼漢明碼是能夠糾正一個錯誤的效率較高的線性是能夠糾正一個錯誤的效率較高的線性分組碼。分組碼。242022-7-5線性分組碼線性分組碼校正子校正子S（監(jiān)督關(guān)系式）（監(jiān)督關(guān)系式） 糾錯就是通過計算糾錯就是通過計算S，實際中，實際中S只有兩種只有兩種取值，故只能表示有錯和無錯，而

15、不能進一取值，故只能表示有錯和無錯，而不能進一步指明錯碼的位置。步指明錯碼的位置。120nnSaaa 252022-7-5線性分組碼線性分組碼若有若有r個監(jiān)督關(guān)系式，則個監(jiān)督關(guān)系式，則r個校正子可以指明一個個校正子可以指明一個錯碼的（錯碼的（2r-1）個不同位置。）個不同位置。當(dāng)校正子可以指明的錯碼位置數(shù)目等于或大于當(dāng)校正子可以指明的錯碼位置數(shù)目等于或大于碼組長度碼組長度n時，才能糾正碼組中任何一個位置上時，才能糾正碼組中任何一個位置上的錯碼，即要求的錯碼，即要求2121rrnkr 或 262022-7-5線性分組碼線性分組碼漢明碼漢明碼要求設(shè)計一個能夠糾正要求設(shè)計一個能夠糾正1個錯誤的分組碼

16、個錯誤的分組碼(n,k)，給定的碼組中有給定的碼組中有4個信息位，個信息位，k=4，則監(jiān)督位數(shù)，則監(jiān)督位數(shù)r3。若取。若取r=3，則，則n=k+r=7?，F(xiàn)在用現(xiàn)在用a6a5a4a3a2a1a0表示這表示這7個碼元，用個碼元，用S1S2S3表示校正子，則這表示校正子，則這3個校正子恰好能夠指個校正子恰好能夠指明明7個錯碼的位置。個錯碼的位置。272022-7-5線性分組碼線性分組碼S1S2S3錯碼位置S1S2S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯碼165422653136430SaaaaSaaaaSaaaa漢明碼漢明碼282022-7-5線性

17、分組碼線性分組碼265416530643aaaaaaaaaaaa漢明碼漢明碼 信息位的值決定于輸入信號，是隨機的。信息位的值決定于輸入信號，是隨機的。監(jiān)督位是按監(jiān)督關(guān)系確定的，應(yīng)保證校正子監(jiān)督位是按監(jiān)督關(guān)系確定的，應(yīng)保證校正子S等于等于0，既有：，既有：654265316430000aaaaaaaaaaaa292022-7-5漢明碼漢明碼（7,4）碼，若）碼，若 代表代表4個信息個信息 位，這位，這 代表代表3個監(jiān)督碼元。個監(jiān)督碼元。線性分組碼線性分組碼3456aaaa、012aaa、（信息位）3456aaaa（監(jiān)督位）012aaa（信息位）3456aaaa（監(jiān)督位）012aaa0000000

18、100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111302022-7-5線性分組碼線性分組碼漢明碼漢明碼接收端解碼方法：接收端解碼方法： 根據(jù)接收碼組，先計算出校正子根據(jù)接收碼組，先計算出校正子S1S2S3 ，然后查表判斷錯碼位置。然后查表判斷錯碼位置。165422653136430SaaaaSaaaaSaaaa312022-7-5線性分組碼線性分組碼漢明碼漢明碼碼率：碼率：2121rrkrn 322022-7-5線性分組碼線性分組碼用矩

19、陣形式表示用矩陣形式表示）模 2(0001011001110101011101000123456aaaaaaaTTTH AOA HO或332022-7-5線性分組碼線性分組碼監(jiān)督矩陣監(jiān)督矩陣H矩陣可以分成兩部分矩陣可以分成兩部分rPIH001101101011011001110典型形式監(jiān)督矩陣典型形式監(jiān)督矩陣具有具有 形式的形式的H矩陣矩陣rPI各行必須是線各行必須是線性無關(guān)的性無關(guān)的rn342022-7-5線性分組碼線性分組碼0001011001010101001101000111QIGr生成矩陣生成矩陣TPQ 轉(zhuǎn)置矩陣轉(zhuǎn)置矩陣65432106543Aa a a a a a aa a a a

20、 GG的各行必須是的各行必須是線性無關(guān)的線性無關(guān)的knkrrk352022-7-5線性分組碼線性分組碼解碼過程解碼過程 發(fā)送碼組發(fā)送碼組A，接收到的碼組，接收到的碼組B，收發(fā)碼，收發(fā)碼 組之差記為組之差記為E（錯誤圖樣錯誤圖樣）ABE021eeenn()SB HAE HE HTTT校正子校正子若若S和和E之間有一一對應(yīng)，則能代表錯碼的位置。之間有一一對應(yīng)，則能代表錯碼的位置。362022-7-5線性分組碼線性分組碼00000010a00100004a0000010010000000001002a10000006a00010003a0000000無錯00110101011010011101100

21、01a5aSSEE錯碼位置錯碼位置錯碼位置錯碼位置372022-7-5線性分組碼線性分組碼線性碼的封閉性線性碼的封閉性若若M1和和M2是一種線性分組碼中的兩個碼組，是一種線性分組碼中的兩個碼組，則則( M1 + M2 )仍是其中一個碼組。仍是其中一個碼組。碼的最小距離就是碼的最小重量碼的最小距離就是碼的最小重量382022-7-5循環(huán)碼循環(huán)碼具有循環(huán)性。即循環(huán)碼中任一碼組循環(huán)一位具有循環(huán)性。即循環(huán)碼中任一碼組循環(huán)一位（將最右端的碼元移至左端，或反之）以后，（將最右端的碼元移至左端，或反之）以后，仍為該碼中的一個碼組。仍為該碼中的一個碼組。為便于計算，把這樣的碼組中個碼元當(dāng)作是一為便于計算，把這

22、樣的碼組中個碼元當(dāng)作是一個多項式的系數(shù)，即把一個長為個多項式的系數(shù)，即把一個長為n的碼組表示成的碼組表示成 為信息碼多項式為信息碼多項式121210( )nnnnT xaxaxa xax僅是碼元位置的標(biāo)記，我們并不關(guān)心僅是碼元位置的標(biāo)記，我們并不關(guān)心x的取的取值，這種多項式稱為值，這種多項式稱為碼多項式碼多項式。( )m x392022-7-5循環(huán)碼循環(huán)碼)()()()()(21xgxxgxgxxgxxGkk循環(huán)碼的循環(huán)碼的生成多項式生成多項式 是常數(shù)項不是常數(shù)項不為為”0” 的的 的一個（的一個（n-k）次因式）次因式)(xg) 1(nx循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣402022-7-5循環(huán)碼循環(huán)碼循環(huán)碼的編碼方法循環(huán)碼的編碼方法根據(jù)給定的根據(jù)給定的(n,k)值選定生成多項式值選定生成多項式)(xg( )g x即從即從 的因子中選一的因子中選一(n-k)次多項次多項式作為式作為) 1(nx412022-7-5循環(huán)碼循環(huán)碼循環(huán)碼的編碼方法循環(huán)碼的編碼方法 將信息碼多項式將信息碼多項式 升升(n-k)次冪后除以生成多次冪后除以生成多 項式項式得到的系統(tǒng)循環(huán)碼多項式得到的系統(tǒng)循環(huán)碼多項式)(xm)(xg)()()()()(xgxrxQxgxmxkn)()()(