1、2022-4-281第六章第六章信道編碼信道編碼 2022-4-282數字通信系統的一般模型數字通信系統的一般模型 等效信道等效信道 干擾源干擾源 物理信道物理信道 解調器解調器 編碼器編碼器 譯碼器譯碼器 信宿信宿 信源信源 調制器調制器 實際信道實際信道 編碼信道編碼信道 2022-4-283將模擬信號變為13比特線性碼聲電輸出RPE-LTP編碼器RPE-LTP譯碼器將13比特線性碼變換為8比特A律碼無線子系統將13比特線性碼變為模擬信號電聲輸出RPE-LTP譯碼器13 kb / sRPE-LTP編碼器將8比特A律碼變換為13比特線性碼移動交換中心公用電話交換網(PSTN/ISDN)模擬語

2、音8000樣本/秒13比特線性碼8000樣本/秒13比特線性碼8000樣本/秒8比特A律50幀260比特/幀無線接入和GMSK調制前向糾錯編碼交織話音編碼456比特/幀無線解調去交織糾錯編碼無線GMSK解調糾錯編碼去交織無線接入及調制交織前向糾錯編碼雙工器語音編碼456比特/幀104 kb / s移動臺MS基站系統BSSGSM系統的話音和信道編碼系統的話音和信道編碼2022-4-284語音編碼器（260bits）3bit奇偶校驗奇偶校驗半速卷積編碼器半速卷積編碼器8時隙交織時隙交織Ia類（50bit） Ib類（132bit） 類（78bit）53bit378編碼比特456bit（8個子塊，57

3、bit/子塊）4尾比特GSM語音編解碼的前向糾錯（全速業務信道）語音編解碼的前向糾錯（全速業務信道）2022-4-2852022-4-286香農編碼定理香農編碼定理n信息通過信道傳輸到信宿的過程即為信息通過信道傳輸到信宿的過程即為通信通信。要做到。要做到既不失真又快速地通信，需要解決兩個問題：既不失真又快速地通信，需要解決兩個問題：n在不失真或允許一定失真條件下，在不失真或允許一定失真條件下，如何提高信息傳輸如何提高信息傳輸速度速度-這是第這是第5 5章要討論的章要討論的信源編碼信源編碼問題問題. .n在信道受到干擾的情況下，在信道受到干擾的情況下，如何增加信號的抗干擾能如何增加信號的抗干擾能

4、力，同時又使得信息傳輸率最大力，同時又使得信息傳輸率最大-這是本章要討論的這是本章要討論的信道編碼信道編碼問題問題. .n信源編碼的基礎是信息論中的兩個編碼定理信源編碼的基礎是信息論中的兩個編碼定理n無失真信源編碼無失真信源編碼 第一極限定理第一極限定理 n限失真信源編碼限失真信源編碼 第三極限定理第三極限定理n信道編碼定理（離散和連續信道）信道編碼定理（離散和連續信道） 第二極限定理第二極限定理2022-4-287 XNUUY2022-4-288n信源編碼信源編碼n提高數字信號提高數字信號n將信源的模擬信號轉變為數字信號將信源的模擬信號轉變為數字信號n降低數碼率降低數碼率, ,壓縮傳輸頻帶壓

5、縮傳輸頻帶( (數據壓縮數據壓縮) )n信道編碼信道編碼n提高數字通信提高數字通信 n數字信號在信道的傳輸過程中數字信號在信道的傳輸過程中, ,由于實際由于實際信道信道的的傳傳輸特性不理想輸特性不理想以及存在加性以及存在加性噪聲噪聲, ,在接收端往往會在接收端往往會產生產生誤碼誤碼。2022-4-289信道編碼信道編碼是以信息在信道上的正確傳輸為目標是以信息在信道上的正確傳輸為目標的編碼，可分為兩個層次上的問題：的編碼，可分為兩個層次上的問題：n如何正確接收載有信息的信號如何正確接收載有信息的信號線路編碼線路編碼( (通信原理，基帶編碼）通信原理，基帶編碼）n如何避免少量差錯信號對信息內容的影

6、響如何避免少量差錯信號對信息內容的影響糾錯編碼糾錯編碼n糾錯編碼的理論體系屬于信息論，但糾錯編碼糾錯編碼的理論體系屬于信息論，但糾錯編碼的實現離不開有形載體的信號理論，因此信息的實現離不開有形載體的信號理論，因此信息的編碼與信號的編碼有天然的聯系。的編碼與信號的編碼有天然的聯系。2022-4-28106.1 有擾離散信道的編碼理論有擾離散信道的編碼理論6.2 糾錯編譯碼的基本原理與分析方法糾錯編譯碼的基本原理與分析方法6.3 線性分組碼線性分組碼6.4 卷積碼卷積碼6.5 其它信道編碼其它信道編碼內內 容容2022-4-28116.1 6.1 有擾離散信道的編碼定理有擾離散信道的編碼定理 6.

7、1 .1 差錯和差錯控制系統分類差錯和差錯控制系統分類 6.1 .2 矢量空間與碼空間矢量空間與碼空間 6.1 .3 隨機編碼與信道編碼定理隨機編碼與信道編碼定理2022-4-28126.1.1 6.1.1 差錯和差錯控制系統分類差錯和差錯控制系統分類是衡量傳輸質量的重要指標之一是衡量傳輸質量的重要指標之一,它有幾種不同它有幾種不同的定義。的定義。n碼元差錯率碼元差錯率/符號差錯率符號差錯率n指在傳輸的指在傳輸的碼元碼元總數中發生差錯的碼元數所占的比總數中發生差錯的碼元數所占的比例例(平均值平均值),簡稱簡稱誤碼率誤碼率(Error symbol rate)。n是指是指差錯概率差錯概率 n比特

8、差錯率比特差錯率 /比特誤碼率比特誤碼率(Error bit rate)：n在傳輸的在傳輸的比特比特總數中發生差錯的比特數所占比例總數中發生差錯的比特數所占比例n是指是指差錯概率差錯概率 n對對二進制二進制傳輸系統傳輸系統,符號差錯等效于比特差錯符號差錯等效于比特差錯;對多進制對多進制系統系統,一個符號差錯對應多少比特差錯卻難以確定一個符號差錯對應多少比特差錯卻難以確定2022-4-2813量級量級自然二進制碼自然二進制碼反射二進制碼反射二進制碼000000010010012010011301101041001105101111611010171111002022-4-2814差錯率差錯率n根

9、據不同的應用場合對差錯率有不同的要求根據不同的應用場合對差錯率有不同的要求:n在電報傳送時在電報傳送時,允許的比特差錯率約為允許的比特差錯率約為: 104105；n計算機數據傳輸計算機數據傳輸,一般要求比特差錯率小于一般要求比特差錯率小于: 108109；n在遙控指令和武器系統的指令系統中在遙控指令和武器系統的指令系統中,要求有要求有更小的誤比特率或碼組差錯率更小的誤比特率或碼組差錯率2022-4-2815差錯圖樣差錯圖樣n為定量地描述信號的差錯為定量地描述信號的差錯,定義定義差錯圖樣差錯圖樣E E=CR (模模M )n最常用的二進制碼可當作特例來研究最常用的二進制碼可當作特例來研究,其差錯圖

10、樣等其差錯圖樣等于收碼與發碼的模于收碼與發碼的模2加加,即即 E = C R 或或 C = R En設發送的碼字設發送的碼字C 1 1 1 1 1 1 1 1 1 1 接收的碼字接收的碼字R 1 0 0 1 0 0 1 1 1 1 差錯的圖樣差錯的圖樣E 0 1 1 0 1 1 0 0 0 0 n差錯圖樣中的差錯圖樣中的“1”既是符號差錯也是比特差錯既是符號差錯也是比特差錯,差錯差錯的個數叫的個數叫漢明距離漢明距離。0:傳輸中無錯1:傳輸中有錯2022-4-2816差錯圖樣類型差錯圖樣類型n隨機差錯隨機差錯：n差錯是差錯是相互獨立相互獨立的的,不相關不相關n存在這種差錯的信道是無記憶信道或隨機

11、信道存在這種差錯的信道是無記憶信道或隨機信道n突發差錯突發差錯：n指指成串成串出現的錯誤出現的錯誤,錯誤與錯誤間有相關性錯誤與錯誤間有相關性,一個差錯一個差錯往往要影響到后面一串字往往要影響到后面一串字nE: 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 突發長度= 4突發長度= 62022-4-2817糾錯碼分類糾錯碼分類 n從功能角度講從功能角度講, ,差錯碼分為檢錯碼和糾錯碼差錯碼分為檢錯碼和糾錯碼n檢錯碼檢錯碼：用于發現差錯：用于發現差錯n糾錯碼糾錯碼：能自動糾正差錯：能自動糾正差錯n糾錯碼與檢錯碼在理論上沒有本質區別糾錯碼與檢錯碼在理

12、論上沒有本質區別, ,只是只是應用場合不同應用場合不同, ,而側重的性能參數也不同。而側重的性能參數也不同。n本章的糾錯編碼包含檢錯碼本章的糾錯編碼包含檢錯碼. .2022-4-2818檢錯與糾錯原理檢錯與糾錯原理 n0:晴晴,1:雨雨n若若10,01。收端無法發現錯誤。收端無法發現錯誤00晴1001110011雨能發現一個錯誤禁用碼組n插入插入1位監督碼位監督碼后具有后具有檢出檢出1位錯碼位錯碼的能的能力（力（2位呢？）位呢？）,但不能予以糾正。但不能予以糾正。2022-4-2819檢錯與糾錯原理檢錯與糾錯原理 000晴010001111000111雨晴n在只有在只有1位錯碼位錯碼的情況下的

13、情況下,可以判決哪位是錯碼可以判決哪位是錯碼并予以并予以糾正糾正,可以可以檢出檢出2位位或或2位以下的錯碼。位以下的錯碼。100011101110雨2022-4-2820檢錯與糾錯原理檢錯與糾錯原理n最大似然譯碼最大似然譯碼：n將接收到的碼字譯碼為與它將接收到的碼字譯碼為與它的的許用碼字許用碼字,并且認為這個許用碼字就是它所對應的發送碼字并且認為這個許用碼字就是它所對應的發送碼字,從而在碼字的糾錯能力內實現自動糾錯。從而在碼字的糾錯能力內實現自動糾錯。n糾錯編碼之所以具有檢錯、糾錯能力糾錯編碼之所以具有檢錯、糾錯能力,是因為在信息是因為在信息碼元之外加入了碼元之外加入了監督碼監督碼。監督碼不載

14、信息。監督碼不載信息,只是用來只是用來監督信息碼在傳輸中有無差錯。監督信息碼在傳輸中有無差錯。n糾錯編碼所提高的可靠性糾錯編碼所提高的可靠性,是以犧牲信道利用率為代是以犧牲信道利用率為代價換取的。價換取的。n監督碼監督碼引入引入越多越多,檢錯、糾錯檢錯、糾錯能力能力越強越強,但信道的傳輸但信道的傳輸效率下降也越多。效率下降也越多。2022-4-2821n信道編碼信道編碼n在被傳輸信息中附加一些冗余碼在被傳輸信息中附加一些冗余碼, ,即即監督碼元監督碼元, ,利用附加碼元與信息碼元間的利用附加碼元與信息碼元間的約束關系約束關系加以校加以校驗驗, ,以以。n信源信源編碼編碼減少減少了了n冗余度是隨

15、機的、無規律的冗余度是隨機的、無規律的n信道信道編碼編碼增加增加了了n冗余度是特定的、有規律的冗余度是特定的、有規律的, ,故可利用其在接收故可利用其在接收端進行檢錯和糾錯。端進行檢錯和糾錯。信道編碼信道編碼2022-4-2822信道編碼的基本思想信道編碼的基本思想n信道編碼信道編碼n按一定規則給數字序列按一定規則給數字序列m增加一些增加一些多余多余的碼元的碼元,使使不具有規律性的信息序列不具有規律性的信息序列 m 變換為具有某種規律變換為具有某種規律性的數碼序列性的數碼序列 C；n碼序列中的碼序列中的信息序列碼元信息序列碼元與與多余碼元多余碼元之間是之間是的；的；n信道譯碼器利用這種信道譯碼

16、器利用這種預知的預知的編碼規則譯碼。檢驗編碼規則譯碼。檢驗接收到的數字序列接收到的數字序列 R 是否符合既定的是否符合既定的 規則規則,從而從而發現發現 R 中是否有錯中是否有錯,或者糾正其中的差錯；或者糾正其中的差錯；n根據根據來檢測來檢測/發現和糾正發現和糾正傳輸過程中產生的傳輸過程中產生的差錯就是信道編碼的基本思想。差錯就是信道編碼的基本思想。2022-4-2823糾錯碼分類糾錯碼分類 n按照對信息序列的處理方法按照對信息序列的處理方法,有有分組碼分組碼和和卷積碼卷積碼n分組碼分組碼：n將將k個信息碼元分成一組個信息碼元分成一組,由這由這k個碼元按照一定規個碼元按照一定規則產生則產生r個

17、監督碼元個監督碼元,組成長度組成長度n = k + r的碼字的碼字 n卷積碼卷積碼：n先將信息序列分組先將信息序列分組, ,不同的是編解碼運算不僅與不同的是編解碼運算不僅與本組信息有關本組信息有關, ,而且還與而且還與前面若干組有關前面若干組有關。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr2022-4-2824糾錯碼分類糾錯碼分類 n按照碼元與原始信息位的關系按照碼元與原始信息位的關系,分為分為n線性碼線性碼：所有碼元均是原始信息元的：所有碼元均是原始信息元的線性組合線性組合,編碼編碼器不帶反饋回路。器不帶反饋回路。n非線性碼非線性碼：

18、碼元并不都是信息元的線性組合：碼元并不都是信息元的線性組合,可能還可能還與前面已編的碼元有關與前面已編的碼元有關,編碼器可能含反饋回路。編碼器可能含反饋回路。n由于非線性碼的分析比較困難由于非線性碼的分析比較困難,早期實用的糾錯碼多為早期實用的糾錯碼多為線性碼線性碼,但當今發現的很多但當今發現的很多好碼好碼恰恰是非線性碼。恰恰是非線性碼。n假設假設i，j是某（是某（ n，k）分組碼的兩個碼字，）分組碼的兩個碼字， 是是碼元字符集里的任意兩個元素，碼元字符集里的任意兩個元素， 當且僅當當且僅當也是碼字時，才稱該碼是線性碼或群碼。也是碼字時，才稱該碼是線性碼或群碼。12, 2022-4-2825糾

19、錯碼分類糾錯碼分類 n按照適用的差錯類型按照適用的差錯類型, ,分成分成: :n糾隨機差錯碼糾隨機差錯碼: :用于隨機差錯信道用于隨機差錯信道, ,其糾錯能力用其糾錯能力用碼組內允許的獨立差錯的個數來衡量。碼組內允許的獨立差錯的個數來衡量。n糾突發差錯碼糾突發差錯碼: :針對突發差錯而設計針對突發差錯而設計, ,其糾錯能力其糾錯能力主要用可糾突發差錯的最大長度來衡量主要用可糾突發差錯的最大長度來衡量n 按照構造碼的理論：代數碼、幾何碼、算術碼和按照構造碼的理論：代數碼、幾何碼、算術碼和組合碼。代數碼：近世代數。組合碼。代數碼：近世代數。 幾何碼：投影幾何。幾何碼：投影幾何。 算術碼：數論和高等

20、算術。算術碼：數論和高等算術。 組合碼：排列組合和數論。組合碼：排列組合和數論。2022-4-2826差錯控制系統分類差錯控制系統分類 n前向糾錯前向糾錯(FEC(FEC，forward error correction)forward error correction)：n發送端的信道編碼器將信息碼組編成具有一定發送端的信道編碼器將信息碼組編成具有一定糾糾錯能力錯能力的碼。的碼。n接收端信道譯碼器對接收碼字進行譯碼接收端信道譯碼器對接收碼字進行譯碼, ,若傳輸若傳輸中產生的差錯數目在碼的糾錯能力之內時中產生的差錯數目在碼的糾錯能力之內時, ,譯碼譯碼器對差錯進行定位并加以糾正。器對差錯進行定

21、位并加以糾正。n應用在應用在實時性和容錯強實時性和容錯強的場合的場合, ,如語音如語音, ,圖像圖像2022-4-2827差錯控制系統分類差錯控制系統分類 n自動請求重發自動請求重發(ARQ, automatic repeat request)：n發端發送發端發送檢錯碼檢錯碼, 如如CRC(循環冗余校驗碼循環冗余校驗碼)，n收端譯碼器判斷當前碼字傳輸是否出錯；收端譯碼器判斷當前碼字傳輸是否出錯；n當有錯時按某種協議通過一個當有錯時按某種協議通過一個反向信道反向信道請求發送端請求發送端重傳已發送的碼字重傳已發送的碼字(全部或部分全部或部分)。n應用于數據通信網、計算機網絡應用于數據通信網、計算機

22、網絡2022-4-2828差錯控制系統分類差錯控制系統分類 n混合糾錯混合糾錯(HEC, hybrid error correction)：n是是FEC與與ARQ方式的結合。方式的結合。n發端發送同時具有自動糾錯和檢測能力的碼組發端發送同時具有自動糾錯和檢測能力的碼組,收端收收端收到碼組后到碼組后,檢查差錯情況檢查差錯情況,如果差錯在碼的糾錯能力以內如果差錯在碼的糾錯能力以內,則自動進行糾正。則自動進行糾正。n如果信道干擾很嚴重如果信道干擾很嚴重,錯誤很多錯誤很多,超過了碼的糾錯能力超過了碼的糾錯能力,但但能檢測出來能檢測出來,則經反饋信道請求發端重發這組數據。則經反饋信道請求發端重發這組數據

23、。n信息反饋信息反饋(IRQ)：n收端把收到的數據收端把收到的數據,原封不動地通過反饋信道送回到發原封不動地通過反饋信道送回到發端端,發端比較發的數據與反饋來的數據發端比較發的數據與反饋來的數據,從而發現錯誤從而發現錯誤,并并且把錯誤的消息再次傳送且把錯誤的消息再次傳送,直到發端沒有發現錯誤為止。直到發端沒有發現錯誤為止。只適于低速非實時數據通信，是一種較原始的做法。只適于低速非實時數據通信，是一種較原始的做法。 2022-4-28296.1.2 矢量空間與碼空間矢量空間與碼空間分組碼：把信源輸出的信息序列，以分組碼：把信源輸出的信息序列，以k個碼元個碼元化分為化分為一段，通過編碼器把這段一段

24、，通過編碼器把這段k個信息元按照一定的規則個信息元按照一定的規則產生產生 r個校驗元個校驗元，輸出長為，輸出長為n=k+r的一個碼組。每個碼的一個碼組。每個碼組的校驗元僅與本組的信息元有關，而與別組無關。組的校驗元僅與本組的信息元有關，而與別組無關。分組碼一般用分組碼一般用(n,k)來表示，其中來表示，其中n表示碼長表示碼長，k表示信表示信息位息位。分組碼的一個碼字可以看作一個分組碼的一個碼字可以看作一個n重矢量，所以可以用重矢量，所以可以用矢量空間矢量空間來分析和理解分組碼。來分析和理解分組碼。2022-4-2830線性（矢量）空間的概念線性（矢量）空間的概念F表示碼元所在的數域，對于二進制

25、碼，表示碼元所在的數域，對于二進制碼，F代表二元域代表二元域0,1。設。設n重有序元素的集合重有序元素的集合V= Vi , n若滿足條件：若滿足條件：nV中矢量元素在矢量加運算下構成加群；中矢量元素在矢量加運算下構成加群；nV中矢量元素與數域中矢量元素與數域F元素的標乘封閉在元素的標乘封閉在V中；中；n分配律、結合律成立，分配律、結合律成立， 則稱集合則稱集合V是數域是數域F上的上的n維維矢量空間矢量空間，或稱，或稱n維維線線性空間性空間，n維矢量又稱維矢量又稱n重重(n-tuples)。（關于（關于群，環，域群，環，域的概念）的概念）2022-4-2831矢量的運算規則矢量的運算規則0121

26、012100112211012100112(,.,)(,.,), (1)(,.,) (2)(,.,) (3)(,iiiiinjjjjjnijijijijinjniiiiinijijijiVvvvvVvvvvaFVVvvvvvvvvaVavavavavVVvvvvvv設和標量矢量加標量乘矢量矢量乘矢量2111211221212112212,.,) (4),.,. ,.,., .0,.,jinjnikkiiKiiiiivvFV VVVVaVa VaVVV VVa aaaVa VaVV VV線性相關與線性無關：對于域 上的若干矢量及若，則稱是的線性組合。如果存在一組不全為零的使得，則稱線性相關。如果

27、不存在一組不全12112212,., .0,.,iiiia aaaVa VaVV VV為零的使得，則稱線性無關。2022-4-2832線性空間的基底線性空間的基底空間的基底。為這個線性性空間。稱這組矢量的集合就構成了一個線則這些矢量的線性組合的矢量如果存在一組線性無關nnVVVVVV,.,.,2121然基底。，則把這組基底稱為自，其余的分量都為分量為且每個元素中只有一個是線性空間的基底，并如果矢量01,.,21nVVV自然基底自然基底子空間子空間的子空間。是，則稱也能構成一個矢量空間的一個元素子集若矢量空間VVVVss2022-4-2833 如在二元域如在二元域GF(2)上上n以（以（100）

28、為基底可張成）為基底可張成一維三重一維三重子空間子空間V1，含，含21 =2 個元素，即個元素，即n以以(010)(001)為基底可張成為基底可張成二維三重二維三重子空間子空間V2，含含 22 =4個元素，即個元素，即n以以(100)(010)(001)為基底可張成為基底可張成三維三重三維三重空間空間V,含含 23 =8個元素，個元素，V1和和V2都是都是V的子空間。的子空間。1(000),(100)V2(000),(001),(010),(011)V“重數重數”：構成矢量的有序元素的個數；：構成矢量的有序元素的個數；“維數維數”：張成矢量空間基底的個數；：張成矢量空間基底的個數；維數不可能大

29、于重數，而當維數小于重數時說明這是個子空間。維數不可能大于重數，而當維數小于重數時說明這是個子空間。2022-4-2834矢量正交矢量正交正交。和則稱，即如果兩個矢量的點積為2121, 00VVVV矢量空間正交矢量空間正交矢量空間正交。這兩個任意元素都正交，則稱如果兩個矢量空間中的對偶空間對偶空間是對偶空間。、正交，則稱、的兩個子空間，并且是空間、如果212121VVVVVVV2022-4-2835碼空間碼空間 消息消息k長長 (n , k) 碼字碼字n長長 qk 種種 分組編碼器分組編碼器 qn種種 k維維k重矢量重矢量 n維維n重矢量重矢量 通常通常qn qk，分組編碼的任務是要在，分組編

30、碼的任務是要在n維維n重重矢量空間的矢量空間的qn種可能組合中選擇其中的種可能組合中選擇其中的qk個構成個構成一個一個碼空間碼空間，其元素就是許用碼的，其元素就是許用碼的碼集碼集。 2022-4-2836分組編碼的任務分組編碼的任務 n選擇一個選擇一個維維n重子空間重子空間作為碼空間。作為碼空間。n確定由確定由k維維k重信息空間到重信息空間到維維n重碼空間的重碼空間的映映射方法射方法。 碼空間的不同選擇方法，以及信息組與碼組碼空間的不同選擇方法，以及信息組與碼組的不同映射算法，就構成了不同的分組碼。的不同映射算法，就構成了不同的分組碼。2022-4-28376.1.3 隨機編碼與信道編碼定理隨

31、機編碼與信道編碼定理 如果不考慮編碼的具體方法，而是運用概率統計的方法如果不考慮編碼的具體方法，而是運用概率統計的方法在特定信道條件下對編碼信號的性能作出統計分析，求出差在特定信道條件下對編碼信號的性能作出統計分析，求出差錯概率的上，下限邊界，其中最優碼所能達到的差錯概率上錯概率的上，下限邊界，其中最優碼所能達到的差錯概率上界稱為隨機碼界。界稱為隨機碼界。隨機編碼的含義隨機編碼的含義機編碼。間，則稱這種編碼為隨果隨機的選取一個子空種選法，如該子空間的選取有好多重空間的一個子空間。維成的空間為個碼字組由所有重空間中的一個元素，維所以碼字為碼字的長度為個不同的消息。而總共有元符號組成的碼組，則個，

32、由編成長度為種符號。其中每個消息有分組碼，設消息組對于NNqNNNqMqNNqmmmmKNkkk,),.,(),(1102022-4-2838n在在(N,k)分組編碼器中隨機選定的碼集有分組編碼器中隨機選定的碼集有qNM種種 n第第m個碼集個碼集(記作記作cm )被隨機選中的概率是被隨機選中的概率是n設與這種選擇相對應的條件差錯概率是設與這種選擇相對應的條件差錯概率是Pe(cm)n全部碼集的平均差錯概率是全部碼集的平均差錯概率是()( )NMmPqc11( ) ( )( )NMNMqqNMeemmemmmPPPqPccc隨機編碼隨機編碼2022-4-2839隨機編碼隨機編碼n必定存在某些碼集必

33、定存在某些碼集n某些碼集某些碼集n若若 ，就必然存在一批碼集，就必然存在一批碼集 即差錯概率趨于零的好碼一定存在即差錯概率趨于零的好碼一定存在 11( ) ( )( )NMNMqqNMeemmemmmPPPqPccc( )emePPc( )emePPc0eP ( )0emPc2022-4-2840隨機編碼隨機編碼n碼集點數碼集點數M=qK占占N維矢量空間總點數維矢量空間總點數qN的比例是的比例是 F =qK / qN = q-(N-K) n當當K和和N的差值拉大即冗余的空間點數增加時，平的差值拉大即冗余的空間點數增加時，平均而言碼字的分布將變得稀疏，碼字間的平均距離均而言碼字的分布將變得稀疏，

34、碼字間的平均距離將變大，平均差錯概率將變小。將變大，平均差錯概率將變小。 n當當F0 即即(N-K)時，能否讓平均差錯概時，能否讓平均差錯概率率 ？ nGallager在在1965年推導了年推導了 的上邊界，并證明這個的上邊界，并證明這個上邊界是按指數規律收斂的。上邊界是按指數規律收斂的。 eP0eP 2022-4-2841錯誤概率的上界錯誤概率的上界對于離散無記憶信道（對于離散無記憶信道（DMC）。錯誤平均）。錯誤平均概率的上界為：概率的上界為：exp( )erPNE RnE(R)為為可靠性函數可靠性函數，也叫誤差指數，也叫誤差指數 n碼率碼率：R =( lbM) / N nM是可能的信息組

35、合數，是可能的信息組合數，M=qKnN是每碼字的碼元數，是每碼字的碼元數，nR表示每碼元攜帶的信息量，單位是每符號比特表示每碼元攜帶的信息量，單位是每符號比特（bit / symbol）n 是全部碼集的平均差錯概率是全部碼集的平均差錯概率eP2022-4-2842可靠性函數可靠性函數Er( R )的曲線的曲線可靠性函數可靠性函數Er( R )與信息傳輸率與信息傳輸率R的關系曲線如下圖，的關系曲線如下圖，是一條下凹的函數曲線。是一條下凹的函數曲線。nR在在0,R0區間時區間時E(R) R曲線是斜率為曲線是斜率為-1（-45 ）的直線，的直線，E(R)反反比于比于R；而當而當R=C時時E(R)=0

36、即可即可靠性為零。靠性為零。 E(R) C 0 R0 -45 R E(R)和和R的關系曲線的關系曲線2022-4-2843n正定理正定理：只要傳信率：只要傳信率R小于信道容量小于信道容量C，總存在一種信，總存在一種信道碼（及解碼器），可以以所要求的任意小的差錯概道碼（及解碼器），可以以所要求的任意小的差錯概率實現可靠的通信。率實現可靠的通信。n逆定理逆定理：信道容量：信道容量C是可靠通信系統傳信率是可靠通信系統傳信率R的上邊界，的上邊界，如果如果R C，就不可能有任何一種編碼能使差錯概率任，就不可能有任何一種編碼能使差錯概率任意小。意小。 n上述兩定理統稱為有擾或噪聲信道的信道編碼定理上述兩定

37、理統稱為有擾或噪聲信道的信道編碼定理信道編碼定理信道編碼定理2022-4-28446.2 糾錯編譯碼的基本原理與分析方法糾錯編譯碼的基本原理與分析方法6.2.1 糾錯編碼的基本原理糾錯編碼的基本原理6.2.2 譯碼方法譯碼方法-最優譯碼最優譯碼 和最大似然譯碼和最大似然譯碼2022-4-28456.2.1 糾錯編碼的基本原理糾錯編碼的基本原理一、從編碼定理出發討論糾錯碼的基本原理一、從編碼定理出發討論糾錯碼的基本原理二、從冗余度和噪聲均化討論糾錯碼的基本原理二、從冗余度和噪聲均化討論糾錯碼的基本原理2022-4-2846增大增大Er( R )的途徑的途徑 Er( R ) R O R1R2 C1

38、C2C2C1R1R2一、從編碼定理出發討論糾錯碼的基本原理：一、從編碼定理出發討論糾錯碼的基本原理：)(RNEereP從上可以看出：要減小從上可以看出：要減小 Pe： （1）增大）增大N; （2）增大）增大Er( R )；2022-4-28471 增大信道容量增大信道容量C（1）擴展帶寬。）擴展帶寬。（2）加大功率。）加大功率。（3）減小噪聲功率。）減小噪聲功率。2 減小碼率減小碼率R(=KlbQ /N)（1）Q,N不變，減小不變，減小K,表示降低信息傳輸速率。表示降低信息傳輸速率。（2） Q,K不變，增大不變，增大N,表示提高符號速率。表示提高符號速率。（3） N，K不變，減小不變，減小Q,

39、表示減小信道的輸入表示減小信道的輸入 輸出符號集。輸出符號集。 增大碼長增大碼長N C,R,K/N不變不變一、從編碼定理出發討論糾錯碼的基本原理：一、從編碼定理出發討論糾錯碼的基本原理：2022-4-2848二、從冗余度和噪聲均化討論糾錯碼的基本原理：二、從冗余度和噪聲均化討論糾錯碼的基本原理：冗余度：冗余度：就是在信息流中插入冗余比特，插入的冗余比特與就是在信息流中插入冗余比特，插入的冗余比特與 信息比特存在著特定的相關性。這樣如果在傳輸過信息比特存在著特定的相關性。這樣如果在傳輸過 程中有個別信息比特受損，也可以從冗余比特中恢程中有個別信息比特受損，也可以從冗余比特中恢 復或發現受損比特。

40、從而保證了信息傳輸的可靠性。復或發現受損比特。從而保證了信息傳輸的可靠性。例如，假定信息為兩位共有四種組合（例如，假定信息為兩位共有四種組合（00，01，11，10）如果不加冗余位，直接傳輸，則接收端無法發現傳輸過程中如果不加冗余位，直接傳輸，則接收端無法發現傳輸過程中的錯誤。但是如果添加一位冗余位，并且有下面的對應關系的錯誤。但是如果添加一位冗余位，并且有下面的對應關系000000101110101111100000010100111001011101112022-4-2849n 傳輸傳輸冗余比特冗余比特 必然要動用必然要動用冗余的資源冗余的資源。n時間時間：比如一個比特重復發幾次：比如一個

41、比特重復發幾次,或一段消息重復發幾遍或一段消息重復發幾遍,或或根據收端的反饋重發受損信息組。根據收端的反饋重發受損信息組。n頻帶頻帶：插入冗余比特后傳輸效率下降：插入冗余比特后傳輸效率下降,若要保持有用信息的若要保持有用信息的速率不變速率不變,方法之一是增大符號傳遞速率方法之一是增大符號傳遞速率(波特率波特率),結果就占結果就占用了更大的帶寬用了更大的帶寬。n功率功率：采用多進制符號：采用多進制符號,用用8進制進制ASK符號代替符號代替4進制進制ASK符符號來傳送號來傳送2比特信息比特信息,可騰出位置另傳可騰出位置另傳1冗余比特。冗余比特。8進制進制ASK符號的平均功率肯定比符號的平均功率肯定

42、比4進制時要大（誤碼率相同時）進制時要大（誤碼率相同時）,這就是動用冗余的功率資源來傳輸冗余比特。這就是動用冗余的功率資源來傳輸冗余比特。n設備復雜度設備復雜度：加大碼長：加大碼長,采用網格編碼調制采用網格編碼調制,是在功率、帶寬是在功率、帶寬受限信道中實施糾錯編碼的有效方法受限信道中實施糾錯編碼的有效方法,代價是算法復雜度的代價是算法復雜度的提高提高,需動用設備資源。需動用設備資源。二、從冗余度和噪聲均化討論糾錯碼的基本原理：二、從冗余度和噪聲均化討論糾錯碼的基本原理：2022-4-2850噪聲均勻化：就是讓差錯隨機化，以便符合編碼定理的條件從噪聲均勻化：就是讓差錯隨機化，以便符合編碼定理的

43、條件從 而得到符合編碼定理結果。其基本思想是設法將而得到符合編碼定理結果。其基本思想是設法將 危害較大的，較為集中的噪聲干擾分攤開來，使危害較大的，較為集中的噪聲干擾分攤開來，使 不可恢復的信息損傷最小。不可恢復的信息損傷最小。（1）增加碼長。）增加碼長。 例如：設例如：設BSC信道的誤碼率為信道的誤碼率為Pe=0.01,編碼后的糾錯能力為編碼后的糾錯能力為10%，當碼長當碼長N=10時，碼字中多于時，碼字中多于1位誤碼就會產生譯碼差錯，差錯概率位誤碼就會產生譯碼差錯，差錯概率為：為： 當碼長變為當碼長變為40時，則碼字中多于時，則碼字中多于4個錯誤時產生差錯，其差錯概個錯誤時產生差錯，其差錯

44、概率為率為（2）卷積。）卷積。（3）交織。）交織。11031001(1)4.27 10mmmeemPC PP 44054001(1)4.92 10mmmeemPC PP 二、從冗余度和噪聲均化討論糾錯碼的基本原理：二、從冗余度和噪聲均化討論糾錯碼的基本原理：2022-4-285176543211413 1211 10982120 1918 1716 152827 2625 2423 223534 3332 3130 2976543211413 1211 10982120 1918 1716 152827 2625 2423 223534 3332 3130 29出出入入入入出出22292181

45、5交錯器交錯器去交錯器去交錯器交錯器工作原理圖交錯器工作原理圖2022-4-28526.2.2 譯碼方法譯碼方法-最優譯碼和最大似然譯碼最優譯碼和最大似然譯碼譯碼器的任務是從受損的信息序列中盡可能正確譯碼器的任務是從受損的信息序列中盡可能正確的恢復出原始信息。的恢復出原始信息。信息組碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100發送碼字發送碼字接收碼字接收碼字001110100001012022-4-2853譯碼算法的已知條件是要求已知：譯碼算法的已知條件是要求已知：（1）實際

46、接收到的碼字序列）實際接收到的碼字序列r,r=(r1,r2,.rN)。（2）發送端所采用的編碼算法和該算法產生的碼集）發送端所采用的編碼算法和該算法產生的碼集XN,滿足滿足。NiNiiiXcccc),.,(21（3）信道模型及信道參數。）信道模型及信道參數。消息組消息組m),.,(21kmmm(N,K)編碼器編碼器NiXC 碼字),.,(21iNiiccc信道信道r接收碼),.,(21Nrrr最佳最佳/最大最大似然譯碼似然譯碼ic碼字估值),.,(21iNiiccc消息消息還原還原),.,(21kmmmim消息2022-4-2854XNUUYf1fXFYXY12 ,rAa aa12 ,sBb

47、bbX12 ,rAa aaN2022-4-2855XY12 ,rAa aa12 ,sBb bbX12 ,rAa aaN*:(),1,2,.,jjF BAF baAjs2022-4-2856XY12 ,rAa aa12 ,sBb bbX12 ,rAa aaN*(),1,2,.,jjF baAjs *(|)()|jjjjP XaYbP F bb ()|1()|)|(jjjjjP XF bYbP FPbebb 11()() 1()(|)jssejjjjjjPP bP bbFPPbeb2022-4-2857XY12 ,rAa aa12 ,sBb bbX12 ,rAa aaN*(),1,2,.,jjF

48、baAjs11()() 1()(|)jssejjjjjjPP bP bbFPPbeb111(),1()|()ssejjjjjjjPP F bbP F bP bF b *,( ,)() (|)eijijiY XaY XaPP a bP a P ba*1,111|()(|)sejjjijY XaPP bF bP barr 2022-4-28580.80.90.20.12b1b1a2a3113322( ):()F baFF ba1()0.4P a1111121( ):()F baFF ba4124421( ):()F baFF ba2122222( ):()F baFF ba0.40.6XP1122|0.80.20.10.9Y XaPbba11220.320.080.060.54XYabbaP1111121()1(),1(,)(,)1(0.320.08)0.6sejjjP FP F bbP a bP a b 2221221()1(),1(,)(,)1 (0.060.54)0.4sejjjP FP F bbP a bP a b 33112210.()1(),1(,)(,)1 (0.320.514)4sejjjP FP F bbP a bP a b 44211210.()1(),1(,)(,)1 (0.080.086)6sejjjP FP F b