北郵-通信原理-第九章-信道編碼.ppt

《北郵-通信原理-第九章-信道編碼.ppt》由會員分享，可在線閱讀，更多相關(guān)《北郵-通信原理-第九章-信道編碼.ppt（168頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第九章 信道編碼,,主要內(nèi)容,信道編碼的基本概念和分類 兩種主要的信道編碼 分組碼 卷積碼 其他類型編碼和編碼界限 （工程應(yīng)用）,章節(jié),信道編碼的基本概念 線形分組碼 循環(huán)碼 BCH碼 卷積碼 其他編碼類型 糾正突發(fā)錯誤碼、交織碼、級聯(lián)碼、Turbo碼、高效率信道編碼TCM,9.1 信道編碼的基本概念,為什么需要信道編碼？ 在數(shù)字信號的傳輸中，實際信道不是理想的，存在噪聲和干擾，會導(dǎo)致接收端的誤判，這樣就產(chǎn)生了差錯。 可采取的辦法： 合理設(shè)計基帶信號 選擇調(diào)制、解調(diào)方式 采用均衡技術(shù) 增大發(fā)送功率 仍然達不到要求，就需要信道編碼,9.1 信道編碼的基本概念,信道分類（按差錯出現(xiàn)類型） 獨立隨機

2、差錯信道 差錯隨機出現(xiàn)，且相互獨立（無記憶性） 原因：由高斯白噪引起（信道本身的傳輸特性比較理想） 太空信道、衛(wèi)星信道、同軸電纜、光纜信道、視距微波信道,9.1 信道編碼的基本概念,信道分類（按差錯出現(xiàn)類型） 突發(fā)差錯信道 差錯成串出現(xiàn)（記憶性） 原因：信道傳輸特性不理想（衰落和碼間干擾），有大的脈沖干擾 短波信道、移動通信信道、散射信道、明線和電纜信道 混合信道,9.1 信道編碼的基本概念,信道編碼的構(gòu)造 在發(fā)送端，在待發(fā)送的信息序列中加入一些多余的碼元（監(jiān)督碼元），這些監(jiān)督碼元和信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)，即滿足一定的約束關(guān)系。 在接收端，按既定的規(guī)則檢驗信息碼元與監(jiān)督碼元之間的

3、約束關(guān)系。約束關(guān)系被破壞就意味著傳輸中有差錯（檢錯）；借助于約束關(guān)系甚至還可以糾正錯誤（糾錯）。,9.1 信道編碼的基本概念,信道編碼分類（按糾正錯誤類型分類） 糾獨立隨機差錯碼：分組碼和卷積碼中的大部分種類 糾突發(fā)差錯碼：分組碼和卷積碼中的幾類、交織碼 糾混合差錯碼：級聯(lián)碼,9.1 信道編碼的基本概念,信道編碼分類（按約束關(guān)系分類） 線性碼：信息碼元與監(jiān)督碼元之間的約束關(guān)系是線性關(guān)系，即滿足一組線性方程式 非線性碼：約束關(guān)系不是線性關(guān)系。（缺少理論和應(yīng)用上的研究）,9.1 信道編碼的基本概念,信道編碼分類（按編碼方式分類） 分組碼：將信息序列分成獨立的若干組進行編碼。編碼后，一組中的碼元只與

4、本組的原始信息碼元有關(guān)，而與其他組的信息碼元無關(guān)。 分組碼用符號（n，k）表示。k是一組中信息碼元的數(shù)目，n是碼元總數(shù)目，則監(jiān)督碼元有n-k位 編碼效率k/n，編碼冗余度1-k/n 非分組碼：卷積碼是其中最主要的一類。,9.1 信道編碼的基本概念,信道編碼分類（按編碼后是否包含原始信息碼元分類） 系統(tǒng)碼：編碼后的信息序列中包含原始信息碼元（位置可能變化） 非系統(tǒng)碼：編碼后的信息序列中不包含原始信息碼元,9.1 信道編碼的基本概念,在數(shù)字通信系統(tǒng)中，利用信道編碼可提高系統(tǒng)可靠性，控制差錯。其控制差錯的方式主要分為三種。 前向糾錯（FEC）：發(fā)端發(fā)送有一定糾錯能力的碼，若傳輸中產(chǎn)生的差錯的數(shù)目在碼

5、的糾錯能力內(nèi)，收端可以糾正。 優(yōu)點：單向通信（不需要反饋信道），實時性好。 缺點：碼的構(gòu)造復(fù)雜，譯碼電路復(fù)雜。,9.1 信道編碼的基本概念,反饋重傳（ARQ）：發(fā)端發(fā)送有一定檢錯能力的碼，收端譯碼時如發(fā)現(xiàn)有錯，則通知發(fā)端重發(fā)，直到正確接收。也稱為檢錯重傳或自動請求重復(fù)。 優(yōu)點：檢錯比較簡單，碼的效率和結(jié)構(gòu)簡單，譯碼電路簡單。 缺點：需要反饋信道，不能單向通信；實時性差。 三種類型：等待式ARQ、退N步ARQ，選擇重傳ARQ。,9.1 信道編碼的基本概念,混合差錯控制（HEC）：是FEC和ARQ的結(jié)合。 需要反饋信道。實時性和譯碼復(fù)雜性是FEC和ARQ兩種方式的折衷。,9.1 信道編碼的基本概念

6、,檢錯和糾錯的基本原理 例1：一個由3位二進制數(shù)字構(gòu)成的碼組，共有8種組合。若用其表示不同的天氣，如：000（晴）、001（云）、010（陰）、011（雨）、100（雪）、101（霜）、110（霧）、111（雹）。 任一碼組在傳輸中產(chǎn)生傳輸中產(chǎn)生一個或多個錯誤，都會變成另一個信息碼組。無法檢錯和糾錯。 原因：碼組中只有信息碼元，沒有監(jiān)督碼元,9.1 信道編碼的基本概念,檢錯和糾錯的基本原理 例2：利用2位二進制數(shù)字的4種組合表示4種天氣，再加1位奇偶校驗位。 可以檢測出傳輸中的1個或3個錯誤（無法檢測2個錯誤，無法糾錯） 原因：監(jiān)督碼元的引入使得8個組合中只有4個是許用組合，其余4個是禁用組合

7、,9.1 信道編碼的基本概念,碼重，碼距，最小碼距 碼重：在分組碼中，把一個碼組/字（A）中所含1的數(shù)目定義為碼組/字重量，簡稱碼重，記為W(A) 碼距：把兩碼組A、B中對應(yīng)位置上碼元不同的數(shù)目定義為兩碼組的距離，簡稱碼距或漢明距，記為d(A,B) 最小碼距：把某種編碼中各個碼組間距離的最小值定義為最小碼距dmin,9.1 信道編碼的基本概念,碼重，碼距，最小碼距 碼距的幾何解釋（圖）,9.1 信道編碼的基本概念,一種編碼的最小碼距直接關(guān)系到這種編碼的檢錯和糾錯能力（圖9.1.2） 為檢測e個誤碼，要求最小碼距 為糾正t個誤碼，要求最小碼距 為糾正t個誤碼，同時檢測e（et），要求最小碼距,

8、,9.1 信道編碼的基本概念,兩種簡單的信道編碼 (n,1)重復(fù)碼（以(3,1) 重復(fù)碼為例） 許用碼組(000),(111) dmin=n 可糾1位錯或檢2位錯 用來糾錯時，出現(xiàn)錯誤的概率為,9.1 信道編碼的基本概念,兩種簡單的信道編碼 (n,n-1)奇偶校驗碼（以(4,3)偶校驗為例） 最后一位為校驗位（例9.1.2） 偶校驗：碼字中1的個數(shù)為偶數(shù)；奇校驗：碼字中1的個數(shù)為奇數(shù) 最小碼距為2 只能用于檢錯：只能檢奇數(shù)個錯誤，無法檢偶數(shù)個錯誤,9.1 信道編碼的基本概念,兩種簡單的信道編碼 (n,1)重復(fù)碼 編碼效率1/n，dmin=n 隨著n的增大，檢錯、糾錯能力越來越強，但編碼效率越來

9、越低 (n,n-1)奇偶校驗碼 編碼效率1-1/n，dmin=2 隨著n的增大，編碼效率越來越高，但只能檢奇數(shù)個錯誤,9.1 信道編碼的基本概念,有限域 定義：一個有限個元素的集合，進行規(guī)定的代數(shù)四則運算后，結(jié)果仍是屬于該集合的元素（自封閉性）。 GF(2)：集合0,1對規(guī)定的模二和“”及點乘“”運算是自封閉的，所以是一個有限域，稱之為二元域,9.1 信道編碼的基本概念,有限域 GF(2k)：以0,1中的元素構(gòu)成的所有長度為k的序列所組成的集合，對規(guī)定的模二和“”及點乘“”運算也是自封閉的。,9.2 線性分組碼,定義 分組：將k個信息位作為一組進行編碼，變換成長度為n（nk）的二進制碼組 線性

10、：信息碼元與監(jiān)督碼元的約束關(guān)系是一組線性代數(shù)方程。 記為（n，k）碼，編碼效率=k/n，冗余度為1-=1-k/n,9.2 線性分組碼,數(shù)學(xué)定義 分組： 線性： 線性編碼f就是從矢量空間GF(2k)到另一個矢量空間GF(2n)的一組線性變換。它可以用線性代數(shù)中的有限維矩陣來表示。,9.2 線性分組碼,線性分組碼的碼距 兩個碼組的距離必等于另一個碼組的碼重 編碼的最小碼距等于非零碼的最小重量（決定該編碼的糾錯能力）,9.2 線性分組碼,例：(7,3)線性分組碼,9.2 線性分組碼,例 將(9-1)表示成矩陣形式,9.2 線性分組碼,(n,k)線性分組碼可以由k個輸入信息位通過一線性變換矩陣G（k

11、行n列）產(chǎn)生，G稱為該線性分組碼的生成矩陣 若G能分解成兩個子矩陣，其中I為k維單位方陣，則稱該線性分組碼c為系統(tǒng)碼或組織碼，G為該系統(tǒng)碼的典型生成矩陣,9.2 線性分組碼,例 將(9-2)表示成矩陣形式,9.2 線性分組碼,(n,k)線性分組碼的監(jiān)督關(guān)系（n-k個線性監(jiān)督方程）用H矩陣（n-k行n列）表示，H稱為該線性分組碼的監(jiān)督矩陣 若H可以分解成兩個子矩陣，其中I是(n-k)維單位方陣，則稱該線性分組碼c為系統(tǒng)碼或組織碼，H為該線性分組碼的典型監(jiān)督矩陣,9.2 線性分組碼,生成矩陣G與監(jiān)督矩陣H之間的關(guān)系 生成矩陣G與監(jiān)督矩陣H可以互相轉(zhuǎn)換。知道了其中一個，另一個就容易求得,9.2 線

12、性分組碼,對偶碼 定義：若把(n,k)碼的監(jiān)督矩陣H作為(n,n-k)碼的生成矩陣G，把(n,k)碼的生成矩陣G作為(n,n-k)碼的監(jiān)督矩陣H，則這樣的(n,k)碼和(n,n-k)碼互為對偶碼,9.2 線性分組碼,系統(tǒng)碼與非系統(tǒng)碼 系統(tǒng)碼的廣義定義：只要編碼前的信息碼元以不變的形式在碼組中的k位出現(xiàn)，都可稱為系統(tǒng)碼。否則，就是非系統(tǒng)碼 對線性分組碼而言，在檢糾錯方面，系統(tǒng)碼和非系統(tǒng)碼是完全一樣的。,9.2 線性分組碼,系統(tǒng)碼與非系統(tǒng)碼 任何一個線性分組(n,k)碼都可等價于一個系統(tǒng)碼 非系統(tǒng)碼的生成矩陣可通過初等行變換和列交換得到等價的系統(tǒng)碼的生成矩陣 初等行變換：矩陣的兩行交換位置；將矩陣

13、的一行加到另一行 列交換：矩陣的兩列交換位置 思考：為什么？,9.2 線性分組碼,例,9.2 線性分組碼,例,9.2 線性分組碼,線性分組碼的編碼實現(xiàn) 由生成矩陣，非常容易得到線性分組碼的電路實現(xiàn)方式,9.2 線性分組碼,伴隨子（校正子）,9.2 線性分組碼,伴隨子（校正子） 校正子只與傳輸差錯E有關(guān)，可見錯誤圖樣和校正子之間有確定的關(guān)系 碼組有n位，可產(chǎn)生2n個錯誤圖樣；而校正子S是(n-k)維矢量，只有2n-k種組合的校正式；這樣對每一種校正式，都有2k個錯誤圖樣與之對應(yīng),9.2 線性分組碼,二進制對稱信道（BSC）下的譯碼 在輸入信息0、1等概的情況下，二進制對稱信道下的最優(yōu)譯碼準(zhǔn)則等效

14、為最小漢明距離準(zhǔn)則 在譯碼時，得到伴隨式S后，應(yīng)該選擇與S對應(yīng)的2k個可能的錯誤圖樣中重量最小的進行譯碼 若收到的碼字為Y，得到的伴隨式為S，若S對應(yīng)的碼重最小的錯誤圖樣是E，那么譯碼輸出就是C=YE,9.2 線性分組碼,利用監(jiān)督矩陣進行譯碼 例9.2.5,9.2 線性分組碼,利用監(jiān)督矩陣進行譯碼 若接收碼字中只有一個碼元出現(xiàn)差錯，比如yi出錯，則校正子S等于監(jiān)督矩陣第i列。 比較(7,4)碼的監(jiān)督矩陣和碼重最小的E,9.2 線性分組碼,漢明碼 漢明碼是一種能糾正一位錯碼的線性分組碼 主要參數(shù)： 碼長n=2m-1 信息位k=2m-1-m 監(jiān)督位n-k=m 最小碼距dmin=3，糾錯能力t=1

15、碼效率R=k/n=1-m/n=1-m/(2m-1) 當(dāng)n很大時，R趨近于1，所以漢明碼是一類高效率的糾錯碼。,9.2 線性分組碼,漢明碼 當(dāng)m=3時，n=7，k=4。之前的(7,4)碼就是漢明碼。 特點：監(jiān)督矩陣中的n=2m-1列正好是m位碼元的2m種組合中除全0組合外的其它組合，且每種組合出現(xiàn)一次。每種組合對應(yīng)該列對應(yīng)的碼元出現(xiàn)傳輸錯誤時的校正子。,9.2 線性分組碼,漢明碼的譯碼電路 利用最小碼重錯誤圖樣進行譯碼的電路實現(xiàn)（圖9.2.4） 利用校正子與錯碼位置的對應(yīng)關(guān)系，也可以使用地址譯碼器來幫助實現(xiàn)譯碼,9.3 循環(huán)碼,循環(huán)碼 是線性分組碼的一個重要子類 BCH碼是其主要的一大類 漢明碼

16、、R-M碼、Golay碼、RS碼等可變換或納入循環(huán)碼內(nèi)，Goppa碼的一個子類也屬于循環(huán)碼 用反饋線性移位寄存器可以容易的實現(xiàn)其編碼和得到伴隨式 由于數(shù)學(xué)上的特性，譯碼方法簡單,9.3 循環(huán)碼,循環(huán)碼的循環(huán)移位特性 循環(huán)碼具有線性分組碼的一般特性 循環(huán)移位特性：任一許用碼組經(jīng)過任意位的循環(huán)移位后得到的碼組仍是一個許用碼組,9.3 循環(huán)碼,定義： 循環(huán)移位推廣：,9.3 循環(huán)碼,舉例：（7,3）碼,9.3 循環(huán)碼,循環(huán)碼的多項式描述 碼字的多項式描述，一個n元碼字可以用一次數(shù)不超過n-1的多項式唯一的表示 其中，我們不關(guān)心x的具體取值，其次數(shù)只表示相應(yīng)碼元的位置 稱這樣的c(x)為c的碼字多項式

17、,9.3 循環(huán)碼,多項式的加法 注意多項式加法與向量加法的對應(yīng)關(guān)系,9.3 循環(huán)碼,多項式的乘法 注意多項式乘法與矩陣乘法的對應(yīng)關(guān)系,9.3 循環(huán)碼,模運算 整數(shù)的模運算 碼字多項式的模運算（其中p(x)次數(shù)為n，r(x)次數(shù)小于n）,9.3 循環(huán)碼,模運算 碼字多項式的模運算舉例,9.3 循環(huán)碼,循環(huán)移位特性的多項式描述 碼字c及其碼多項式c(x) 其左移i位后的碼字ci和碼多項式ci(x),9.3 循環(huán)碼,循環(huán)移位特性的多項式描述 c的碼字多項式c(x)乘以xi,9.3 循環(huán)碼,循環(huán)移位特性的多項式描述 上面的表達式說明碼字循環(huán)移位i位后的多項式ci(x)在模xn+1的運算下與xic(x

18、)是相同的 在循環(huán)碼的研究中可以用xic(x)代替ci(x),9.3 循環(huán)碼,循環(huán)碼的生成矩陣 循環(huán)碼中除全0碼組外必然有一個且僅有一個前k-1位均為0的碼組，且其最后一位為1 存在性：循環(huán)碼屬于線性分組碼，必可以變換為一個系統(tǒng)碼；系統(tǒng)碼的信息碼元可以有k-1位0 不存在前k位均為0的非全0碼組：k位輸入信息碼元為0則編碼后必定是全0碼組 唯一性：如果有兩個碼組滿足此條件，由線性分組碼對運算的封閉性，兩個碼組相加前k位為0 此碼組最后一位為1：若為0則移位后會成為前k位為0的非全0碼組,9.3 循環(huán)碼,循環(huán)碼的生成矩陣 (n,k)線性分組碼的生成矩陣（k行n列）的每一行均為一個許用碼組，且線性

19、無關(guān) 利用循環(huán)碼的唯一的前k-1位為0的非全0碼組g(x)，容易得到生成多項式：將g(x)和其依次循環(huán)移位直到k-1次的各個碼組g(1)(x)，g(2)(x)，，g(k-1)(x)，分別作為生成矩陣的k行（容易知道它們互不相關(guān)），即得到生成矩陣 g(x)（次數(shù)為n-k）稱為循環(huán)碼的生成多項式,9.3 循環(huán)碼,循環(huán)碼的生成矩陣 舉例：若已知某(7,3)循環(huán)碼的一個碼字為(0111001)，則其循環(huán)移位4次后的碼字(0010111)也是一許用碼字，易得生成矩陣,9.3 循環(huán)碼,循環(huán)碼的生成矩陣 (n,k)循環(huán)碼的每個碼字的碼多項式都是g(x)的倍數(shù) 凡次數(shù)小于n的多項式，若能被g(x)除盡，則必

20、是該循環(huán)碼的碼多項式,9.3 循環(huán)碼,循環(huán)碼的生成矩陣 用上面的辦法所產(chǎn)生的生成矩陣所表示的循環(huán)碼不是系統(tǒng)循環(huán)碼 系統(tǒng)循環(huán)碼的生成矩陣的形式為 第i行也為一許用碼字，多項式表示為,9.3 循環(huán)碼,循環(huán)碼的生成矩陣 系統(tǒng)循環(huán)碼的生成矩陣的多項式表示,9.3 循環(huán)碼,循環(huán)碼的生成矩陣 系統(tǒng)循環(huán)碼的生成矩陣舉例：(7,3)循環(huán)碼的生成多項式g(x)=x4+x2+x+1，g=(0010111),9.3 循環(huán)碼,循環(huán)碼的生成矩陣 非系統(tǒng)循環(huán)碼變換為系統(tǒng)循環(huán)碼也可以用矩陣變換的辦法，但只能用簡單行變換，不能用列的交換,9.3 循環(huán)碼,循環(huán)碼的生成多項式 g(x)為n-k次多項式，則xkg(x)為n次多項式

21、 c(x)為許用碼組，所以必是g(x)的倍數(shù) 生成多項式g(x)必是xn+1的因式，為尋找生成多項式指出了方法,9.3 循環(huán)碼,循環(huán)碼的生成多項式 舉例：尋找(7,3)循環(huán)碼的生成多項式g(x)，其次數(shù)為n-k=4,9.3 循環(huán)碼,循環(huán)碼的生成多項式 對任意n，有： 若取x+1為生成多項式，構(gòu)成的循環(huán)碼是簡單的偶監(jiān)督碼(n,n-1)。最小碼距dmin=2 若用xn-1+ xn-2++x+1為生成多項式，構(gòu)成的(n,1)循環(huán)碼信息位個數(shù)為1，校驗碼個數(shù)為n-1。容易知道實際就是重復(fù)碼。,9.3 循環(huán)碼,循環(huán)碼的生成多項式 (7,k)循環(huán)碼,9.3 循環(huán)碼,循環(huán)碼的監(jiān)督多項式 循環(huán)碼的生成多項式g

22、(x)是xn+1的因式 h(x)稱為此循環(huán)碼的監(jiān)督多項式 舉例，(7,3)循環(huán)碼,9.3 循環(huán)碼,循環(huán)碼的監(jiān)督矩陣,9.3 循環(huán)碼,循環(huán)碼的監(jiān)督矩陣 由上面的式子，可知循環(huán)碼的監(jiān)督矩陣可表示為 容易驗證，由g(x)移位得到的生成矩陣與上面的監(jiān)督矩陣相乘得到0陣,9.3 循環(huán)碼,循環(huán)碼的監(jiān)督矩陣 舉例：(7,3)循環(huán)碼，g(x)=x4+x2+x+1，h(x)=x3+x+1,9.3 循環(huán)碼,循環(huán)碼的監(jiān)督矩陣 系統(tǒng)循環(huán)碼的監(jiān)督矩陣 例:(7,3)系統(tǒng)循環(huán)碼,9.3 循環(huán)碼,系統(tǒng)循環(huán)碼的編碼器 系統(tǒng)循環(huán)碼的編碼方式是將信息碼多項式升n-k次冪后除以生成多項式，然后將所得余式置于升冪后的信息多項式之后

23、,9.3 循環(huán)碼,系統(tǒng)循環(huán)碼的編碼器 舉例：(7,4)系統(tǒng)循環(huán)碼的生成多項式為g(x)=x3+x+1，輸入信息多項式為u(x)= x3+1,9.3 循環(huán)碼,系統(tǒng)循環(huán)碼的編碼器 多項式除法電路可以用帶反饋的線性移位寄存器來實現(xiàn)（圖9.3.2） 與采用手算進行多項式長除運算的過程類似 用除法電路進行系統(tǒng)碼的編碼的過程（表9.3.3）（板書）,,9.3 循環(huán)碼,系統(tǒng)循環(huán)碼的譯碼器 校正子,9.3 循環(huán)碼,系統(tǒng)循環(huán)碼的譯碼器 校正子與錯誤圖樣的關(guān)系,9.3 循環(huán)碼,系統(tǒng)循環(huán)碼的譯碼器 校正子的一個重要性質(zhì)： 一碼組移位i次后的碼組的校正子等于原碼組的校正子在除法電路中移位i次的結(jié)果,9.3 循環(huán)

24、碼,系統(tǒng)循環(huán)碼的譯碼器 舉例： (7,4)系統(tǒng)循環(huán)碼的生成多項式為g(x)=x3+x+1,9.3 循環(huán)碼,系統(tǒng)循環(huán)碼的譯碼器 上面的性質(zhì)使得譯碼器需要識別的錯誤圖樣的數(shù)目大大減小（如果某(n,k)碼可糾正m個錯誤，則識別錯誤圖樣數(shù)目由 減為 ）；(7,4)碼的識別數(shù)由7減為1。,9.3 循環(huán)碼,系統(tǒng)循環(huán)碼的譯碼器 譯碼器電路（圖9.3.3） 譯碼過程（板書） 一次譯碼需要2n個節(jié)拍才能完成。所以真正的譯碼電路需要兩個除法電路（圖）,,9.3 循環(huán)碼,碼字的擴展與收縮：可增加信息位、校驗位來增加碼字長度，減少信息位、校驗位來減少碼字長度（圖9.3.4）,,9.3 循環(huán)碼,CRC（Cycli

25、c Redundancy Check）:循環(huán)冗余校驗 檢錯能力很強 實現(xiàn)簡單 CRC校驗已成為國際標(biāo)準(zhǔn)，在數(shù)據(jù)通信和移動通信中廣為使用,9.3 循環(huán)碼,CRC的檢錯原理 c(x)能被生成多項式g(x)整除，如接收到的y(x)不能被g(x)整除，意味著傳輸出錯 編碼電路與循環(huán)碼一樣(圖9.3.5) 譯碼電路檢查對g(x)的整除性(圖9.3.6),9.3 循環(huán)碼,CRC的檢錯原理,,9.3 循環(huán)碼,CRC的檢錯原理,,,9.3 循環(huán)碼,注意：CRC并不一定是循環(huán)碼 因為g(x)可以對任意信息碼長k的分組進行編碼，作為生成多項式,9.3 循環(huán)碼,CRC的檢錯能力 錯誤圖樣總個數(shù):2k+r 無法檢出的

26、錯誤圖樣個數(shù):2k-1 無法檢出的錯誤圖樣的比例:(2k-1)/ 2k+r =1/2r,9.4 BCH碼,BCH碼 由Bose，Chaudhuri和Hocquenghem發(fā)現(xiàn) 屬于循環(huán)碼 糾錯能力強，能糾正多個隨機錯誤 構(gòu)造方便 （我們不從理論上研究BCH碼的性質(zhì)，只學(xué)習(xí)如何使用BCH碼）,9.4 BCH碼,BCH碼的構(gòu)造 其生成多項式為 t為糾錯個數(shù)，mi(x)為最小多項式，LCM表示取最小公倍式 其能糾正t個隨機差錯，最小碼距,9.4 BCH碼,本原BCH碼 碼長 非本原BCH碼 碼長n為2m-1的因子,9.4 BCH碼,最小多項式表（表） 階數(shù)m表示碼長n=2m-1中的m 十進制數(shù)字表示

27、mi(x)中的i 最小多項式用8進制數(shù)表示，如 最小多項式后的字母意義：ABCD表示非本原多項式，EFGH表示本原多項式,9.4 BCH碼,BCH碼構(gòu)造舉例 例9.4.1：碼長15的BCH碼，能糾正3個錯誤,9.4 BCH碼,表9.4.1（本原BCH碼） 表9.4.2（非本原BCH碼） （學(xué)會根據(jù)需要查找）,9.4 BCH碼,Golay碼 (23,12)非本原BCH碼，生成多項式為 碼距為7，能糾正3個隨機錯誤 是GF(2)上糾多個隨機差錯的唯一一個完備碼，監(jiān)督碼元得到了最充分的利用,9.4 BCH碼,RS（Reed-Solomon，里德-所羅門）碼 一種非二進制BCH碼，編碼的單位是符號；一

28、個符號由m個二進制碼元組成，即為2m進制 糾正t個符號錯誤的RS碼的參數(shù)： 碼長n=2m-1個符號（即m(2m-1)比特） 信息位數(shù)k=n-2t個符號（即m(n-2t)比特） 監(jiān)督位數(shù)2t個符號（即2mt比特） 最小碼距d=2t+1個符號（即m(2t+1)比特） 糾正突發(fā)錯誤的能力強,9.5 卷積碼,簡單介紹 不是分組碼 1955年，由P. Elias提出 沒有進行理論研究的好的數(shù)學(xué)工具 糾錯性能和碼字構(gòu)成之間的直接關(guān)系沒找到 性能好的碼的構(gòu)成不能從理論上推導(dǎo)得到，只能用計算機搜索,9.5 卷積碼,編碼器一般結(jié)構(gòu),,9.5 卷積碼,編碼器一般結(jié)構(gòu),,9.5 卷積碼,編碼器一般結(jié)構(gòu) 有k個輸入信

29、息端，n個輸出端（k

30、組碼的區(qū)別 性能：在編碼結(jié)構(gòu)相當(dāng)?shù)那闆r下，卷積碼的性能優(yōu)于分組碼，因而是作為前向糾錯碼的好的選擇之一。 研究成熟度：分組碼有好的代數(shù)工具，研究比較成熟透徹；卷積碼沒有好的代數(shù)工具，研究不是很透徹。,9.5 卷積碼,卷積碼的表示方法 圖形表示法 狀態(tài)圖法 樹圖法 格圖法 解析表示法 離散卷積法 生成矩陣法 碼多項式法,9.5 卷積碼,狀態(tài)圖 狀態(tài)：k(K-1)個寄存器單元中存儲的數(shù)據(jù)表示狀態(tài)（共有2k(K-1)種狀態(tài)） 卷積編碼是個Markov鏈：當(dāng)前輸出和下一步的狀態(tài)決定于當(dāng)前的狀態(tài)和當(dāng)前輸入 k位輸入：輸入的可能組合有2k種 狀態(tài)轉(zhuǎn)移：對每一種狀態(tài)，均有2k種狀態(tài)轉(zhuǎn)移方式（對應(yīng)2k種輸入和輸

31、出）,9.5 卷積碼,狀態(tài)圖舉例：(2,1,3)卷積碼,,9.5 卷積碼,狀態(tài)圖舉例：(2,1,3)卷積碼,,9.5 卷積碼,樹圖 狀態(tài)圖的缺點：時序關(guān)系不清晰，整個編碼過程看不清楚 卷積碼的樹圖就是將編碼過程的所有的狀態(tài)轉(zhuǎn)移的可能性用樹的方式表示 一個節(jié)點表示一個狀態(tài)（節(jié)點級數(shù)l表示經(jīng)過了l個輸入，樹根總是全零狀態(tài)）；一個分支表示當(dāng)有一種輸入時從一個節(jié)點到下一級某個節(jié)點的狀態(tài)轉(zhuǎn)移,9.5 卷積碼,樹圖舉例：(2,1,3)卷積碼,,9.5 卷積碼,格圖 樹圖缺點：當(dāng)級數(shù)lK-1后，樹圖中的2k(K-1)個狀態(tài)開始重復(fù)出現(xiàn) 格圖是從l=K開始，合并重復(fù)出現(xiàn)的狀態(tài) 格圖特點：保持了時序的清晰性，表

32、達也比較簡潔 格圖是研究維特比譯碼算法的重要工具,9.5 卷積碼,格圖舉例：(2,1,3)卷積碼,,9.5 卷積碼,離散卷積法：以(2,1,4)卷積碼為例說明 輸出的各個分支所構(gòu)成的系統(tǒng)都是線性時不變系統(tǒng)；而線性時不變系統(tǒng)可以用沖激相應(yīng)來表示（長為K），且輸出是輸入與沖激相應(yīng)的卷積,9.5 卷積碼,離散卷積法 舉例： (2,1,4)卷積碼,,9.5 卷積碼,離散卷積法 舉例： (2,1,4)卷積碼（圖9.5.3） 相應(yīng)的沖激相應(yīng)也叫生成序列,9.5 卷積碼,碼多項式法 將輸入序列、生成序列和輸出序列分別用碼多項式表示，容易驗證，輸出碼多項式等于輸入碼多項式和生成序列碼多項式的乘積,9.5 卷

33、積碼,碼多項式法 舉例： (2,1,4)卷積碼（圖9.5.3）,9.5 卷積碼,生成矩陣法：以(2,1,4)卷積碼為例推導(dǎo),9.5 卷積碼,生成矩陣法：以(2,1,4)卷積碼為例推導(dǎo),9.5 卷積碼,生成矩陣法：推廣到一般(n,k,K)卷積碼 (n,k,K)卷積碼的生成序列一般表示式為 其中g(shù)li,j表示每組k個輸入比特中第i個比特經(jīng)延遲l后的輸出與每組n個輸出比特中第j個比特的模2和器件的輸入端的連接關(guān)系；為1表示有連接，為0表示沒有連接,9.5 卷積碼,生成矩陣法：推廣到一般(n,k,K)卷積碼 生成矩陣為,9.5 卷積碼,生成矩陣法：推廣到一般(n,k,K)卷積碼 舉例：(3,2,2)卷

34、積碼（圖9.5.4）,,9.5 卷積碼,生成矩陣法：推廣到一般(n,k,K)卷積碼 舉例：(3,2,2)卷積碼（圖9.5.4）,9.5 卷積碼,卷積碼的譯碼方法 代數(shù)譯碼：根據(jù)卷積碼的本身編碼結(jié)構(gòu)進行譯碼，譯碼時不考慮信道的統(tǒng)計特性 概率譯碼：這種譯碼在計算時要考慮信道的統(tǒng)計特性 門限譯碼 序貫譯碼 維特比譯碼（最佳譯碼，最大似然譯碼）,9.5 卷積碼,最大后驗概率（MAP）譯碼,9.5 卷積碼,最大似然（ML）譯碼 若發(fā)送碼字等概出現(xiàn)，MAP等價于ML,9.5 卷積碼,最大似然（ML）譯碼 對于無記憶信道 稱上式中的取對數(shù)部分為對數(shù)似然函數(shù)，簡稱似然函數(shù)（或度量值）,9.5 卷積碼,編碼信

35、道 硬輸出：解調(diào)器將信號硬判決為0或1 軟輸出：輸出模擬量或經(jīng)多電平量化的值,9.5 卷積碼,舉例（2PSK） V1(t)=s(t)+n(t)是軟輸出，或?qū)ζ溥M行Q=2m2的多電平量化也是軟輸出 V2(t) 是硬輸出，對V1(t)進行了硬判決,9.5 卷積碼,維特比譯碼 硬判決譯碼：對應(yīng)于解調(diào)器的硬輸出 軟判決譯碼：對應(yīng)于解調(diào)器的軟輸出,9.5 卷積碼,維特比硬判決譯碼 對于二進制對稱信道（BSC）,9.5 卷積碼,維特比硬判決譯碼 似然函數(shù) 譯碼準(zhǔn)則（因為P<1/2） 維特比硬判決譯碼準(zhǔn)則等效為最小漢明距離準(zhǔn)則,9.5 卷積碼,維特比硬判決譯碼 若節(jié)數(shù)為n，則編碼路徑總共約有2n條，有必

36、要求出所有路徑的似然函數(shù)（漢明距離）嗎？,Example-Principle of Optimality,,,,,,,EE Bld,Faculty Club,N,N,S,S,,,,,,,.5,.8,.7,.5,1.2,.8,,,.2,.3,.5,.8,,,,1.2,1.0,,,1.3,,,,Professor X chooses an optimum path on his trip to lunch,Optimal: 6 adds Brute force:8 adds,N bridges Optimal: 4(N+1) adds Brute force: (N-1)2N adds,Find

37、optimal path to each bridge,,9.5 卷積碼,維特比硬判決譯碼（幸存路徑）,,,,,,,00,00,10,,State i,State i-1,4,2,0,1,3,Search previous states,9.5 卷積碼,維特比硬判決譯碼（幸存路徑舉例）,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,shortest path-Hamming distance to s2,,,,,,,,,,9.5 卷積碼,維特比硬判

38、決譯碼（最小漢明距離路徑）,First step,Trace though successive states,,,,,,s0,s1,s2,s3,9.5 卷積碼,維特比硬判決譯碼（最小漢明距離路徑：舉例）,y： 11 01 01 10 01,9.5 卷積碼,維特比硬判決譯碼（收尾） 一般來講，不收尾也可以譯碼，但缺點是最后會有多條幸存路徑，最后幾個比特可能出現(xiàn)錯誤 編碼時加入確定的收尾比特，使得使得最后的狀態(tài)是確定的狀態(tài)（一般是全零狀態(tài)），這樣最后只有一條幸存路徑，它對應(yīng)的就是譯碼序列 對于k=1，只需要在編碼時加入m個尾比特0就可以使最后狀態(tài)回到全零狀態(tài),9.5 卷積碼,

39、維特比硬判決譯碼（收尾：舉例）,9.5 卷積碼,維特比硬判決譯碼（總結(jié)） 對每個狀態(tài)需存儲兩種信息：幸存路徑的度量值（硬判決譯碼中是漢明距離）和對應(yīng)的譯碼序列 ACS：對第i+1節(jié)的每個節(jié)點（狀態(tài)），對從第i節(jié)的所有節(jié)點中可能進入該節(jié)點的2k條路徑作度量值的累加；比較這些度量值；選擇度量值最大（漢明距離最小）的路徑為幸存路徑；更新存儲信息。,9.5 卷積碼,維特比硬判決譯碼（總結(jié)：過程） 初始化：對第0節(jié)節(jié)點存儲信息初始化（全零狀態(tài)漢明距離為0，其他狀態(tài)漢明距離為無窮大。因為全零狀態(tài)是確定的初始狀態(tài)） ACS的循環(huán)操作：以第0節(jié)存儲信息為基礎(chǔ)進行ACS得到到達第1節(jié)各節(jié)點的幸存路徑并更新各狀態(tài)

40、的存儲信息；重復(fù)直到最后 譯碼輸出：最后確定狀態(tài)（全零狀態(tài)）存儲的譯碼序列即為最終的譯碼輸出,9.5 卷積碼,維特比截短譯碼（傳統(tǒng)方法的缺點） 要全部接收數(shù)據(jù)進入譯碼器并進行完全部運算后才可以輸出譯碼結(jié)果，因而時延（編碼長度n）很大 需要存儲所有狀態(tài)的全部歷史數(shù)據(jù)，信息存儲量大（譯碼序列：n2km）,9.5 卷積碼,維特比截短譯碼（依據(jù)：匯聚特性） 譯碼中，各狀態(tài)的幸存路徑的先前部分通常會匯聚為一條（圖9.5.10）,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

41、,,,,,,,,,,,,所有路徑匯聚,9.5 卷積碼,維特比截短譯碼 在第i時刻，可以將i-L時刻前的路徑結(jié)果直接輸出，而在存貯空間中不再保存i-L時刻前的譯碼序列內(nèi)容（將其輸出）。這里的L就被稱做譯碼深度 維特比截短譯碼不是傳統(tǒng)的維特比譯碼（最大似然譯碼），其性能有所下降 當(dāng)L5m時，性能已經(jīng)非常接近最大似然譯碼,9.5 卷積碼,維特比截短譯碼（優(yōu)點） 時延降低：由n降為L 存儲量減小：譯碼序列存儲量由n2km減為L2km,9.5 卷積碼,維特比軟判決譯碼（直接輸出：2PSK） 直接以V1(l)作為軟輸出yl 其中cl =0,1,9.5 卷積碼,維特比軟判決譯碼（直接輸出：2PSK） 求最

42、大似然函數(shù)等價于求最小歐氏距離 若去掉公有項，則,9.5 卷積碼,維特比軟判決譯碼（多電平量化） 以V1(l)經(jīng)多電平量化后的值作為軟輸出yl 2PSK：將 作為度量值，或?qū)⑵浼由弦粋€常數(shù)使之恒為非負(fù),9.5 卷積碼,維特比軟判決譯碼（多電平量化舉例） c=(111,000,001,001,111,001,111,110) y=(101,100,001,011,110,110,111,110),9.5 卷積碼,維特比軟判決譯碼（總結(jié)） 解調(diào)直接輸出可以看作是多電平量化的一種 譯碼過程與硬判決譯碼一樣，唯一的區(qū)別是度量值不同 也具有匯聚特性，可以使用維特比截短譯碼 性能優(yōu)于硬判決譯碼，增

43、益有1.52.0dB 3比特量化即基本足夠,9.5 卷積碼,卷積碼的距離特性 碼的距離特性與糾錯能力有密切關(guān)系 分組碼：最小距離dmin 卷積碼 最小距離dmin ：長度為nK的編碼后序列之間的最小漢明距離（用于門限譯碼，不討論） 自由距離dfree：任意長度的編碼后序列的最小漢明距離（用于維特比譯碼） 分組碼與卷積碼的區(qū)別：卷積碼沒有固定的長度的碼字,9.5 卷積碼,卷積碼的距離特性 由卷積碼的編碼器結(jié)構(gòu)，可知卷積碼具有線性性質(zhì) 這樣，卷積碼的碼序列之間的自由距離就等于非全零碼序列的最小碼重,9.5 卷積碼,卷積碼的距離特性（自由距離dfree） 求自由距離dfree可以轉(zhuǎn)化為求任意長非全零

44、碼序列的最小碼重 進一步轉(zhuǎn)化：由于一條編碼路徑的碼重在與全0路徑匯聚以后不再增加（若在分離碼重繼續(xù)增加，顯然不是最小碼重），所以求dfree就是找到從全零狀態(tài)出發(fā)后重新匯聚到全零狀態(tài)的編碼路徑的最小碼重 求法：格圖法（圖）,9.5 卷積碼,卷積碼的距離特性 (n,k,K)卷積碼的構(gòu)造方法有多種，通過求生成函數(shù)可以求得它們的自由距離（解析方法） 隨著k，K的增大，狀態(tài)數(shù)目指數(shù)增加，求生成函數(shù)變得越來越復(fù)雜 好碼的尋找：通過計算機搜索,9.5 卷積碼,卷積碼的距離特性 Heller給出的編碼效率為1/n的卷積碼（即(n,1,K)卷積碼）的dfree的上界 在上式的基礎(chǔ)上，Daut等人給出了編碼效率

45、為k/n的卷積碼的dfree的修正上界，以及搜索的相應(yīng)號碼的列表,9.7 交織碼,長突發(fā)差錯帶來的問題 線性分組碼和卷積碼主要用于無記憶信道，即用于糾正獨立隨機差錯 線性分組碼和卷積碼中的少數(shù)種類可以用于糾正突發(fā)差錯，但一般僅限于單個短的突發(fā)差錯,9.7 交織碼,交織碼的原理 它實際上是一種信道改造技術(shù)，將產(chǎn)生突發(fā)差錯的有記憶信道近似改造成產(chǎn)生獨立隨機差錯的無記憶信道 原理框圖（圖9.7.1）,,9.7 交織碼,交織碼的原理 交織器（發(fā)送端）用于將原有的碼元序列的順序打亂；去交織器（接收端）則用于恢復(fù)碼元序列的順序 本質(zhì)上，去交織器將從信道接收的碼元序列的順序打亂了。這樣信道產(chǎn)生的突發(fā)差錯的順

46、序也被打亂，變成了近似的獨立隨機差錯 這樣由交織器、突發(fā)信道、去交織器組成的編碼信道就完成了信道改造的功能，使信道變成了近似的獨立隨機差錯信道,9.7 交織碼,交織的種類 分組交織 卷積交織 偽隨機交織,9.7 交織碼,分組交織 框圖（圖9.7.2） 交織器和去交織器中各有一存儲矩陣 在接收端進行交織時，將碼元序列以一定規(guī)則f1寫入存儲矩陣，再以另一一定規(guī)則f2讀出 在接收端進行去交織時，將接收碼元序列以規(guī)則f2寫入存儲矩陣，再以規(guī)則f1讀出,,9.7 交織碼,分組交織（舉例） 交織器列寫入，行讀出,9.7 交織碼,分組交織（舉例） 去交織器行寫入，列讀出,9.7 交織碼,分組交織 把具有M列N行的存儲矩陣的交織稱為(M,N)分組交織 收發(fā)時延：2MN,9.7 交織碼,卷積交織 框圖（9.7.3） 與分組交織相比：存儲器數(shù)量減少一半；收發(fā)時延減少一半,,9.7 交織碼,偽隨機交織 分組交織和卷積交織的缺點：其讀寫規(guī)則不變（呈周期性），這樣在特定情況下，會使周期的獨立隨機差錯變成周期的突發(fā)差錯 偽隨機交織的解決方法：碼元序列順序的打亂是偽隨機的，即讀寫規(guī)則是變化的（沒有周期性）,