差錯控制與信道編碼.ppt

《差錯控制與信道編碼.ppt》由會員分享，可在線閱讀，更多相關(guān)《差錯控制與信道編碼.ppt（92頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第五章 差錯控制與信道編碼,,,,結(jié)束放映,學(xué)習(xí)目錄,學(xué)習(xí)要求,內(nèi)容簡介,內(nèi)容簡介,差錯控制就是通過某種方法，發(fā)現(xiàn)并糾正數(shù)據(jù)傳輸中出現(xiàn)的錯誤。差錯控制技術(shù)是提高數(shù)據(jù)傳輸可靠性的重要手段之一，現(xiàn)代數(shù)據(jù)通信中使用的差錯控制方式大都是基于信道編碼技術(shù)來實現(xiàn)的，本章對差錯控制的基本概念以及常用的信道編碼方案作了比較詳細(xì)的論述。,,返回,,結(jié)束,學(xué)習(xí)要求,1. 理解差錯控制的基本概念及其原理等； 2. 掌握信道編碼的基本原理； 3. 了解常用檢錯碼的特性； 4. 掌握線性分組碼的一般特性； 5. 掌握漢明碼以及循環(huán)碼的編譯碼及其實現(xiàn)原理； 6. 了解卷積碼的基本概念。,,返回,,結(jié)束,學(xué)習(xí)目錄,,返回,

2、5.1 概述 5.2 常用的簡單信道編碼 5.3 線性分組碼 5.4 卷積碼,,結(jié)束,5.1 概 述,差錯控制是數(shù)據(jù)通信系統(tǒng)中提高傳輸可靠性，降低系統(tǒng)傳輸誤碼率的有效措施 。本節(jié)將介紹差錯控制和信道編碼的基本原理、差錯控制的實現(xiàn)方式等內(nèi)容。,5.1.1 差錯控制 5.1.2 信道編碼 5.1.3 基于信道編碼的差錯控制方式,本節(jié)內(nèi)容提要：,5.1.1 差錯控制,差錯控制 通過某種方法，發(fā)現(xiàn)并糾正傳輸中出現(xiàn)的錯誤。 香農(nóng)信道編碼定理 在具有確定信道容量的有擾信道中，若以低于信道容量的速率傳輸數(shù)據(jù)，則存在某種編碼方案，可以使傳輸?shù)恼`碼率足夠小。,基于信道編碼的差錯控制 在發(fā)送端根據(jù)一定的規(guī)則，在數(shù)

3、據(jù)序列中按照一定的規(guī)則附加一些監(jiān)督信息，接收端根據(jù)監(jiān)督信息進(jìn)行檢錯或者糾錯。,5.1.1 差錯控制,隨機錯誤 主要由起伏噪聲引起，錯誤碼元分布比較分散且彼此統(tǒng)計獨立； 突發(fā)錯誤 主要由脈沖噪聲引起，錯誤碼元分布集中且彼此具有某種相關(guān)性。,錯誤圖樣,差錯分析,E中，“0”表示正確，“1”表示錯誤,隨機錯誤錯誤圖樣,5.1.1 差錯控制,突發(fā)錯誤錯誤圖樣,5.1.2 信道編碼,在不采用信道編碼的時候，進(jìn)入信道的數(shù)據(jù)碼元相互獨立，一旦發(fā)生錯誤，將無法發(fā)現(xiàn)。例如氣象臺向電視臺傳輸氣象信息。,不可靠數(shù)據(jù)傳輸系統(tǒng),5.1.2 信道編碼,將信息序列按照k位碼元的長度分成若干個信息碼組M，再將信息碼組輸入到信

4、道編碼器，信道編碼器按照一定的算法，產(chǎn)生一個新的n位碼字A輸出，nk； 收端根據(jù)A中的相關(guān)性判斷接收是否正確，并將其恢復(fù)成M。 編碼效率為k/n，即所謂編碼效率是指信道編碼后碼字中信息碼元的數(shù)目與碼字總碼元數(shù)目之比 。,信道編碼的基本思想,5.1.2 信道編碼,信道編碼的冗余,信息碼組M由k個二進(jìn)制碼元（即比特）組成，所以就有2k個M； A長度為n，n位長度的碼字共有2n個，信道編碼實質(zhì)是通過一定 的規(guī)則，從2n個長度為n的碼字中選擇了其中的2k個，每個被選 中的碼字稱為許用碼字； 未被選中的2n-2k個n長的碼字稱為禁用碼字，反映冗余大小 。,5.1.2 信道編碼,對本節(jié)開始時的例子采

5、用(2，1)重復(fù)碼: 11”---- 晴,“00” --- 雨 許用碼組為:“11”和“00”,禁用碼組為：“01”和“10” 此時接收端可以發(fā)現(xiàn)單個錯誤，但不能糾正錯誤 也不能發(fā)現(xiàn)2位錯誤，如下圖所示：,實例分析 I,5.1.2 信道編碼,對本節(jié)開始時的例子采用(3，1)重復(fù)碼: 111”---- 晴,“000” --- 雨 許用碼組為: 111和000 禁用碼組為： 001、010、011、100、101、110 將這種編碼用來檢錯時，可以發(fā)現(xiàn)兩位以內(nèi)的錯誤 將這種編碼用來糾錯，可以糾正一位錯誤，如下圖所示：,實例分析 II,5.1.2 信道編碼,如此譯碼的原因是信道中錯一位的概率遠(yuǎn)遠(yuǎn)大

6、于錯多位的概率,例如要把該（3，1）重復(fù)碼在有一條誤碼率為10-5的信道傳輸，則： 錯一位的概率為：P1 = C31 Pe (1Pe)2 = 310-5 錯二位的概率為：P2 = C32 Pe2 (1Pe) = 310-10 錯三位的概率為：P3 = Pe3 = 10-15,這種譯碼方法稱為極大似然譯碼法,其基本原理為:構(gòu)造一個極大似 然函數(shù)L,從2k個許用碼組中找到一個碼字Ci，當(dāng) = Ci時,函數(shù)L可以取得最大值,則認(rèn)為C = Ci 。,5.1.2 信道編碼,線性碼和非線性碼 若f()是線性函數(shù)稱為線性碼 若f()是非線性函數(shù)則稱為非線性編碼,信道編碼的分類,信道編碼器函數(shù)關(guān)系式為

7、：,分組碼和卷積碼 分組碼：每個信息碼組M通過運算產(chǎn)生對應(yīng)的A ，記作(n，k),,,卷積碼：每個A是由m (m<2k)個M聯(lián)合運算得到，記作(n，k，m),5.1.2 信道編碼,系統(tǒng)碼和非系統(tǒng)碼,,檢錯碼、糾錯碼和糾檢錯碼,若A中的前k位或者后k位就是信息碼組M，則稱這種編碼為系統(tǒng) 碼，否則稱為非系統(tǒng)碼。,5.1.2 信道編碼,幾個概念,碼長 碼字的碼元數(shù)目，例如(n，k)分組碼的碼長為n,碼重 指碼字中“1”的數(shù)目，記作W(A)。例如W(110110)=4,碼距（漢明距） 兩個等長碼對應(yīng)位不同的數(shù)目，記作d(A，B)， 例如A=110110，B=101011，則d(A，B)=4,碼

8、距與碼重的關(guān)系 d(A，B)=W (A+B),5.1.2 信道編碼,最小碼距（最小漢明距）,,一個(n，k)分組碼的糾檢錯能力由其最小碼距決定 ：,當(dāng)最小碼距d0e+1時，能夠發(fā)現(xiàn)e個錯誤碼元 當(dāng)最小碼距d02t+1時，能夠糾正t個錯誤碼元 當(dāng)最小碼距d0t +e +1時，能夠糾正t個錯誤碼元， 同時發(fā)現(xiàn)e個錯誤碼元(et),(n，k)分組碼總共有2k個碼字，記作Ai（i=0,1,,2k-1）,則這些碼字兩兩之間都有一個碼距，定義該(n，k)分組碼的最小碼距為 ：,5.1.3 基于信道編碼的差錯控制方式,前向糾錯（FEC: Forward Error Correction）方式,原理

9、采用糾錯碼,收端發(fā)現(xiàn)錯誤后自動糾正。,特點 無需重發(fā)，解碼延遲固定，實時性好 無需反饋信道，能用于單向傳輸信道，特別適用于單點向多點同時傳送的方式 編碼效率較低，需較大的冗余度（通常約25-50%）,譯碼設(shè)備比較復(fù)雜 糾錯碼須與信道特性相匹配，對信道變化的適應(yīng)性較差 若錯誤超出糾錯碼糾錯能力,只好將其拋棄,應(yīng)用 移動通信系統(tǒng),5.1.3 基于信道編碼的差錯控制方式,反饋重傳（ARQ: Automatic Repeat Request）方式,原理 采用檢錯碼，接收端發(fā)現(xiàn)錯誤后，給發(fā)送端一個反饋信號，要求重新發(fā)送，直到正確為止。,特點 編碼效率比較高，只需少量的冗余碼（約5-20%）就能獲得極低的

10、傳輸誤碼率；對信道的適應(yīng)能力強 必須有反饋信道，故不能用于單向傳輸系統(tǒng)和同播系統(tǒng) 控制規(guī)程和過程比較復(fù)雜 重發(fā)導(dǎo)致信道的有效利用率較低，通信的實時性較差 由于反饋重傳的隨機性，故不適于實時傳輸系統(tǒng),5.1.3 基于信道編碼的差錯控制方式,反饋重傳（ARQ: Automatic Repeat Request）方式,工作方式 發(fā)送等待 連續(xù)工作方式 混合方式,應(yīng)用 數(shù)據(jù)通信系統(tǒng),5.1.3 基于信道編碼的差錯控制方式,混合糾錯（HEC: Hybrid Error Correction）方式,原理 采用糾檢錯碼，是ARQ和FEC方式的折衷方案,特點 集合了ARQ和FEC的優(yōu)點，在保證系統(tǒng)較高的有效性

11、的同時,大幅度提高了整個系統(tǒng)的可靠性,應(yīng)用 移動通信系統(tǒng) ，數(shù)據(jù)傳輸系統(tǒng)（特別是在使用衛(wèi)星信道等高時延、大容量的信道傳輸數(shù)據(jù)信號時更具優(yōu)勢）,5.1.3 基于信道編碼的差錯控制方式,信息反饋（IRQ: Information Repeat Request ）方式,原理 也稱回程校驗方式，在發(fā)端來檢測錯誤。,特點 無需采用糾檢錯編碼，故設(shè)備和控制由于規(guī)程較簡單； 需一條與前向信道相同的反饋信道； 由于采用發(fā)端檢錯，相當(dāng)于信息傳輸距離增加一倍，可能導(dǎo)致額外的差錯和重傳； 可能使整個通信系統(tǒng)的傳信率很低； 收發(fā)兩端需較大容量的存儲器來存儲傳輸信息。,,5.2 常用的簡單信道編碼,本節(jié)內(nèi)容提要：,檢錯

12、碼在ARQ系統(tǒng)中使用，其生成方式簡單，易于實現(xiàn)，檢錯效果較好，因此得到廣泛的應(yīng)用，本節(jié)將介紹奇偶校驗碼、行列監(jiān)督碼、恒比碼 、正反碼的編譯碼規(guī)則、特性以及應(yīng)用情況。,5.2.1 奇偶監(jiān)督碼 5.2.2 行列監(jiān)督碼 5.2.3 恒比碼 5.2.4 重復(fù)碼 5.2.5 正反碼,5.2.1 奇偶監(jiān)督碼,奇偶監(jiān)督碼 碼重為奇數(shù)或偶數(shù)的(n , n-1)系統(tǒng)分組碼,ITU-T建議 同步數(shù)據(jù)傳輸使用偶監(jiān)督 異步數(shù)據(jù)傳輸使用奇監(jiān)督 能檢查出傳輸碼組中的所有奇數(shù)個錯誤,監(jiān)督關(guān)系 假設(shè)將（n，n-1）的奇偶監(jiān)督碼的碼字記作：an-1,an-2,,a1,a0， 其中a0為監(jiān)督碼元，其余為信息碼元，則各碼元滿足

13、：,5.2.2 行列監(jiān)督碼,行列監(jiān)督碼（水平垂直一致校驗碼或方陣碼） 對水平方向(共L行)和垂直方向(共M列) ,同時進(jìn)行奇偶監(jiān)督的碼， 記作（LM+L+M+1 , LM）。,(66，50)行列監(jiān)督碼的一個碼字,該碼具有很強的糾檢錯能力，常用于短波散射信道等信道干擾比 較嚴(yán)重的通信中。,5.2.2 行列監(jiān)督碼,行列監(jiān)督碼（水平垂直一致校驗碼或g方陣碼） 根據(jù)按列或按行的次序傳輸，分別能發(fā)現(xiàn)小于等于M+1或L+1長度的突發(fā)性錯誤；,,可以檢出某些偶數(shù)個隨機誤差； 當(dāng)傳輸差錯數(shù)正好為4的倍數(shù)，而且構(gòu)成矩形的四個角，則不能發(fā)現(xiàn)這類差錯。,5.2.3 恒比碼,恒比碼（等比碼，定比碼，等重碼）

14、從所有一定長度的二進(jìn)制序列中選取“1”數(shù)目相同的序列作為碼字； 該碼的特點是碼字中1，0數(shù)目恒定，亦即1，0數(shù)目之比恒定。,目前我國電傳通信中普遍采用3：2碼，又稱5中取3碼，如下所示,國際上通用的ARQ電報通信系統(tǒng)中，采用7中取3碼。 可以檢測所有奇數(shù)個錯誤和部分偶數(shù)個錯誤。 主要優(yōu)點是簡單易實現(xiàn)。,,5.2.4 重復(fù)碼, (3，1)重復(fù)碼兩個碼字為000和111，其最小碼距為3； (n，1)重復(fù)碼也只有全0碼和全1碼兩個碼字，其最小碼距為n， 卻有2n-2個禁用碼組，隨著碼長的增大，其冗余也變得很大； 該碼隨碼長增加，具有很強的糾檢錯能力，但其編碼效率的急 劇下降； 重復(fù)碼并不是一種

15、優(yōu)秀的編碼方案，僅用于速率很低的數(shù)據(jù)通信系統(tǒng)中。,重復(fù)碼 重復(fù)碼只有一位信息碼元，監(jiān)督碼元是信息碼元的重復(fù)， 所以僅有兩個碼字；,5.2.5 正反碼,正反碼 該碼型多用于10單位碼的前向糾錯設(shè)備中，可以糾正一位錯誤， 發(fā)現(xiàn)全部兩個以下的錯誤，以及大部分兩個以上的錯誤，其本質(zhì) 就是五單位碼的重復(fù)；,編碼規(guī)則 信息碼組中1的數(shù)目為奇數(shù)時，監(jiān)督碼是信息碼的重復(fù)即正碼； 信息碼組中1的數(shù)目為偶數(shù)時，監(jiān)督碼是信息碼的反碼。,譯碼方法 首先將收到的碼字中的信息位和監(jiān)督位按對應(yīng)位作模2運算， 得到一個5位碼組，若該碼字中有奇數(shù)個1，則將其作為校驗碼 組，若有偶數(shù)個1，則取其反碼作為校

16、驗碼組。然后，按照下表 進(jìn)行糾檢錯譯碼,5.2.5 正反碼,正反碼錯誤判決表,,5.3 線性分組碼,本節(jié)內(nèi)容提要：,本節(jié)將對線性分組碼的特點、編譯碼規(guī)則以及應(yīng)用情況作介紹，主要包括以下四方面內(nèi)容。,5.3.1 基本概念 5.3.2 線性分組碼編碼 5.3.3 漢明碼 5.3.4 循環(huán)碼,,5.3.1 基本概念,1有限域,定義了加法“+”和乘法“”兩種運算的有限集合； q個元素的有限域又稱為伽羅瓦域，記作GF(q)； 對域的逆元操作又演繹出了減法“”和除法運算“”，,域具有封閉特性,域中總包含惟一的加法恒等元“0”和乘法恒等元“1”,,5.3.1 基本概念,域中任意元素存在惟一的加法逆元

17、域中任意非零元都存在惟一的乘法逆元 于是減法和除法運算可定義為：,,,,域中元素滿足交換律、結(jié)合律和分配律運算規(guī)則：,5.3.1 基本概念,GF(q)中定義的是模q的加法和乘法，例如GF(2)的運算表如表所示：,加法運算表,乘法運算表,5.3.1 基本概念,2矢量空間, 所有n維矢量組成的集合就構(gòu)成了n維矢量空間Vn；,矢量對矢量的加法構(gòu)成一個加法交換群， 即滿足封閉性、結(jié)合律和交換律，有恒等元和逆元。, 滿足分配律,,滿足結(jié)合律,矢量空間的性質(zhì),8PSK調(diào)制時給出的信號點矢量圖， 就是定義在GF(2)上的3維矢量空間V3,V3=000，001，010，011，100，101，110

18、，111,5.3.1 基本概念,集合S中存在全零矢量（0,0,,0），即零元； 集合S中任何兩個矢量和仍在該集合中，即滿足封閉性。,子空間 如果n維矢量空間Vn的一個子集S，滿足以下條件，則稱其為Vn的一個子空間：,矢量與碼字的關(guān)系 一個碼長為n的碼字可以看成是一個有n個元素的矢量； 所有2n個n長碼字就構(gòu)成了定義在GF(2)(兩個元素：0、1的伽羅瓦域)上的n維矢量空間Vn ；,對于一個(n，k)線性分組碼，其編碼過程是從GF(2)上的n維矢 量空間Vn中，尋找其中遵循某種編碼規(guī)則的一個子空間，而這 個子空間中的所有碼字正好構(gòu)成了一個加法交換群，所以線性 分組碼又稱為群碼 。,5

19、.3.1 基本概念,3線性分組碼性質(zhì),封閉性,具有零元 即具有全零碼，記作A0 。,具有負(fù)元 若Ai+ Aj =A0則稱其互為負(fù)元，（n , k）中Ai是它本身的負(fù)元。,滿足結(jié)合率和交換率,5.3.2 線性分組碼編碼,1生成距陣,,矢量的線性無關(guān) 若Vn中k個矢量A1,A2,,Ak，當(dāng)且僅當(dāng) ，i=1,2,,k時下式成立,,空間的基,在任意一個矢量空間或者子空間中，至少存在一組線性無關(guān)的矢量，可以張成這個空間, 這一組矢量稱為該空間的基，基中矢量的數(shù)目稱為空間的維數(shù)。,5.3.2 線性分組碼編碼,實例分析,v1=(1000)，v2=(0100)，v3=(0010)，v4=(0001) 線

20、性無關(guān)的，作為基，張成一個4維矢量空間V4：,5.3.2 線性分組碼編碼,生成矩陣,矩陣G的每行矢量是基中的矢量，故稱之為生成矩陣； 由其可以得到矢量空間中的全部矢量； 上例中選取的基得到的生成矩陣恰好是4階單位矩陣，實際上線性無關(guān)的行矢量都可以作為生成矩陣的行矢量 。,2編碼原理,線性分組碼標(biāo)記,（n，k）線性分組碼，其碼字通常記作： A=an-1 an-2 a0 1n 信息碼組M記作： M=mk-1 mk-2 m1 m0 1k,5.3.2 線性分組碼編碼,生成矩陣G記作 ：,編碼過程,,,5.3.2 線性分組碼編碼,實例,假設(shè)一個(6，3)分組生成矩陣為：,編

21、碼過程為：,5.3.2 線性分組碼編碼,該(6，3)碼是非系統(tǒng)碼，信息元m2、m0、m1分別出現(xiàn)在碼字A的第 1、3、5位，而2、4、6位是編碼器產(chǎn)生的監(jiān)督碼元，其碼表為：,,,5.3.2 線性分組碼編碼, 生成矩陣典型化,實例分析,3系統(tǒng)碼編碼原理,,,, 編碼過程,5.3.2 線性分組碼編碼, (6，3)系統(tǒng)分組碼表,監(jiān)督元與信息元之間的一般關(guān)系,,5.3.2 線性分組碼編碼,注意到系統(tǒng)碼中前k位即信息元，將其寫成線性方程組的形式,,監(jiān)督關(guān)系,,,5.3.2 線性分組碼編碼, 監(jiān)督矩陣,監(jiān)督關(guān)系一般表達(dá),,,或,生成矩陣典型陣一般形式,,5.3.2 線性分組碼編碼,(n，k)分組碼碼字

22、可表示為 ：,(n，k)碼的一般編碼過程,A =an-1 an-2 an-k ar-1 a1 a0 = mk-1 mk-2 m0 ar-1 a1 a0,對上式兩邊同時進(jìn)行矩陣轉(zhuǎn)置得：,,,5.3.2 線性分組碼編碼,也即,此時的系數(shù)矩陣，即監(jiān)督矩陣為,,,,5.3.2 線性分組碼編碼,生成矩陣和監(jiān)督距陣的關(guān)系, (n，k)碼的一般編碼過程,根據(jù)需要選定一監(jiān)督關(guān)系確定H陣； 由H陣和陣的關(guān)系確定G陣； 由A=MG生成所有碼字。,5.3.2 線性分組碼編碼,伴隨式S和錯誤圖樣E的關(guān)系,伴隨式,二者并不是一一對應(yīng)的關(guān)系，因為錯誤圖樣有2n種表現(xiàn)形 式，而伴隨式僅有2r種表現(xiàn)形式，（注意r=n-k

23、

24、式 ：對于任何的整數(shù)，必存在一個(n，k) 漢明碼，碼長n和監(jiān)督元數(shù)目r=n-k滿足 n=2r -1(除去全零情況),,漢明碼特點, 可以糾正一位傳輸錯誤，且d0=3， 碼長和監(jiān)督元的關(guān)系：n=2r-1,實例分析(7，4)漢明碼,首先構(gòu)造其監(jiān)督矩陣，此時監(jiān)督矩陣為H37， 3位二進(jìn)制碼元的組合有8種： 000、001、010、011、100、101、110、111 其中不全為零的7個正好可用作監(jiān)督矩陣的列,可得到監(jiān)督矩陣：,5.3.3 漢明碼,任意調(diào)換監(jiān)督矩陣各列位置并不影響碼的糾錯能力， 將其轉(zhuǎn)化成典型陣的形式，并由其可以得到生成矩陣G,,,,由A=MG得到其所有的碼字，如下表所示

25、：,5.3.3 漢明碼,假設(shè)發(fā)送端的碼字是A15=1111111， 傳輸過程中第4位a3出現(xiàn)了錯誤，即接收的碼字是B=1110111 此時對應(yīng)的伴隨式為：,,5.3.3 漢明碼,下表給出了該（7，4）漢明碼單個錯誤的錯誤圖樣與其對應(yīng)的伴 隨式，可以發(fā)現(xiàn)伴隨式正是監(jiān)督矩陣的每一列，且該列的位置恰 好是碼元出錯的位置。,由于S不是全零，可判斷傳輸出錯， 而ST=0 1 1T，是監(jiān)督矩陣H的第4列,這正是錯誤碼元發(fā)生的位置, 因此可以得到錯誤圖樣為E=0001000，進(jìn)而按B+E即可糾錯。,,,5.3.3 漢明碼,完備性定義,漢明碼完備碼 性,,,5.3.4 循環(huán)碼,一個(7，3)系統(tǒng)循環(huán)碼

26、碼表如下所示：,1基本概念,一類具有循環(huán)移位特性的線性分組碼， 即其中的一個碼字經(jīng)過循環(huán)移位后仍然是該分組碼的碼字,定義,5.3.4 循環(huán)碼,例如A4=0111001，對應(yīng)的碼多項式為 ：,碼多項式,(n，k)循環(huán)碼中，為了便于描述與計算，經(jīng)常使用n-1次碼多項式 來表示碼字，碼字A =an-1 an-2 a1 a0 ，它對應(yīng)的碼多項式為：,A4向左循環(huán)移1位得A7=1110010，這相當(dāng)于將A4(x)乘以x，即,5.3.4 循環(huán)碼,對于(7，3)循環(huán)碼的碼多項式，其最高次數(shù)不能超過6，解決該 問題的辦法是對上式作模x7+1運算 ：,A7向左循環(huán)移1位得A6=1100101，但若將A

27、7(x)乘以x得到多項式為,其計算過程如下 ：,,,,5.3.4 循環(huán)碼,2生成多項式和生成矩陣,(n，k)循環(huán)碼中的r=n-k次碼多項式，其次數(shù)最低（0元除外）； 其它所有的碼多項式都能被g(x)整除； 并且g(x)是xn+1的一個因式 。,生成多項式 g(x),例如本節(jié)前面給出的(7，3)循環(huán)碼，其生成多項式為：,,5.3.4 循環(huán)碼,若g(x)含有(x+1)因式，對應(yīng)的(n，k)系統(tǒng)循環(huán)碼， 能夠檢出所有奇數(shù)個錯誤；,(n，k)系統(tǒng)循環(huán)碼檢錯能力與g(x)的關(guān)系,,若g(x)含有常數(shù)項1因式，且不能整除xe+1， 則對應(yīng)的(n，k)系統(tǒng)循環(huán)碼，能夠檢出所有的兩位錯誤；,若g(x)

28、含有常數(shù)項1因式，對應(yīng)的(n，k)系統(tǒng)循環(huán)碼， 能夠檢出所有突發(fā)長度r的突發(fā)錯誤， 并且對突發(fā)長度等于r+1的突發(fā)錯誤的漏檢率為2-(r-1)， 對突發(fā)長度大于r+1的突發(fā)錯誤的漏檢率為2-r。,5.3.4 循環(huán)碼,CRC-12：,標(biāo)準(zhǔn)生成多項式,,CRC-16：,CRC-CCITT ：,CRC-32：,,,,,5.3.4 循環(huán)碼,g(x) 、x g(x)、x2 g(x)、、xk-1 g(x)是(n，k)循環(huán)碼的k個線性無 關(guān)的碼字，所以可得其生成距陣G，用碼多項式表示G的各行：,生成矩陣G,若信息碼組M= mk-1 mk-2 m0，則：,5.3.4 循環(huán)碼,上式同時提供了循環(huán)碼

29、的一種編碼方法，但由其得到的循環(huán)碼 是非系統(tǒng)碼，因為此時生成矩陣不是典型陣。,,例如本節(jié)前面給出的(7，3)循環(huán)碼，,將該矩陣典型化之后，再按照A=MG編碼才能得到表本節(jié)前面 給出的系統(tǒng)(7，3)循環(huán)碼； 實際應(yīng)用中，系統(tǒng)循環(huán)碼的編譯碼通常是由g(x)經(jīng)過簡單的代數(shù) 運算來實現(xiàn)。,,5.3.4 循環(huán)碼,系統(tǒng) (n，k)循環(huán)碼碼字：,編碼原理,用碼多項式來表示為：,3編碼,A =an-1 an-2 an-k ar-1 a1 a0 = mk-1 mk-2 m0 ar-1 a1 a0,,5.3.4 循環(huán)碼,式中M(x)是信息碼組碼多項式，所以只需要確定r(x) 已知循環(huán)碼的所有碼字都能

30、夠被g(x)整除，r(x)可由下式確定：,(n，k)循環(huán)碼的生成多項式為：,編碼器,,其中r=n-k，則該(n，k)系統(tǒng)循環(huán)碼的編碼電路如下圖所示：,5.3.4 循環(huán)碼,r級線性移位寄存器的初始狀態(tài)為全零，所有開關(guān)均向下連通 ；,在寄存器時鐘的控制下進(jìn)行k次移位，輸出M(x)的系數(shù)(即信息 碼組)，同時實現(xiàn)除法電路的功能；,編碼器工作過程,5.3.4 循環(huán)碼,所有開關(guān)向下連通，輸入下一組信息重復(fù)上述過程。,實例分析,所有開關(guān)均倒向上方連通，在寄存器時鐘的控制下再經(jīng)過r=n-k 次移位，將監(jiān)督元輸出到信道；,本節(jié)前面給出的(7，3)循環(huán)碼生成多項式：g(x)=x4+x2+x+1 由其

31、可得編碼電路如下圖所示：,5.3.4 循環(huán)碼,假設(shè)M=110，編碼器工作過程如下表所示,5.3.4 循環(huán)碼,現(xiàn)在檢驗上表編碼結(jié)果，因為M=110，所以,即所得的碼字為A=1100101 。,,,,,,5.3.4 循環(huán)碼,系統(tǒng)循環(huán)碼的每一個碼字都能夠被生成多項式g(x)整除 ：,檢錯譯碼原理,發(fā)送端發(fā)送的碼字為,3譯碼,接收的碼字為,錯誤圖樣,伴隨式,5.3.4 循環(huán)碼,可以證明：,若S等于0判定傳輸無錯，否則判定傳輸出錯 。,檢錯譯碼原理圖 ：,5.3.4 循環(huán)碼,寄存器置零，開關(guān)S向下連通；,在寄存器時鐘的控制下經(jīng)n次移位后將接收碼字B輸入，此時寄存器中存儲的即伴隨式,,(n，k)循環(huán)碼伴隨

32、式計算電路,其工作過程如下：,,將開關(guān)向上打開，經(jīng)r=n-k次移位讀出伴隨式。,5.3.4 循環(huán)碼,糾錯譯碼原理,確定循環(huán)碼的糾錯能力;,,根據(jù) 模g(x)計算伴隨式，若S(x)不為零則判定傳輸出錯。,根據(jù) 模g(x)找到伴隨式對應(yīng)的錯誤圖樣,由A(x)=B(x)+E(x)糾錯。,5.4 卷積碼,,本節(jié)內(nèi)容提要：,卷積碼是一類非線性有記憶編碼，本節(jié)將簡要介紹卷積碼的編 譯碼原理。,5.4.1 卷積編碼器 5.4.2 卷積碼的解析描述 5.4.3 卷積碼的圖解描述 5.4.4 維特比譯碼原理,5.4.1 卷積編碼器,卷積碼通常記作(n，k，m)， 其中k為一次移入編碼器的

33、比特數(shù)目， n為對應(yīng)于k比特輸入的編碼輸出， m為約束長度。,卷積碼,定義卷積碼的編碼效率為k/n， 可以將其理解為同一時刻，編碼器有k位比特信息輸入， 有n位編碼比特輸出,卷積碼有記憶的特性： 卷積編碼器的輸出不僅和當(dāng)前輸入的k比特信息有關(guān)， 而且還依賴于之前輸入的m-1組k比特信息。,5.4.1 卷積編碼器,(n，k，m)卷積編碼器結(jié)構(gòu),5.4.1 卷積編碼器,可以發(fā)現(xiàn)上圖中mk級寄存器中第一級是多余的，事實上只需要 m(k-1)級即可，所以可以得到卷積碼編碼器的另一種形式,5.4.1 卷積編碼器,(3，1，3)卷積碼的兩種等效編碼器,實例分析,3級編碼器,2級編碼

34、器,,5.4.2 卷積碼的解析描述,仍然以上圖中的(3，1，3)卷積碼為例， 由其單位沖擊響應(yīng)可構(gòu)造生成矩陣為：,生成矩陣法,其中未寫出的元素為0。 和分組碼不同，卷積碼并不以塊的形式出現(xiàn)， 即其碼字可能無限長，故5-68式所示的矩陣稱為半無限矩陣,,此時卷積碼可由C=MG得到，例如M=11101時,,5.4.2 卷積碼的解析描述,卷積編碼器也可以用n個生成多項式來描述， 分別對應(yīng)n個輸出支路。,生成多項式法, (3，1，3)卷積碼編碼器,上圖所示的卷積編碼器可以用以下所示的3個生成多項式描述,,5.4.2 卷積碼的解析描述,則對應(yīng)的碼多項式為,所以對應(yīng)的碼字是：C=111 110 101 010 100 001 011,,輸入信息為M=11101，對應(yīng)的多項式為 則各支路碼多項式分別為：,,5.4.2 卷積碼的解析描述,5.4.3 卷積碼的圖解描述,實例分析以下圖所示的(2，1，3)卷積碼器,假設(shè)初始狀態(tài)為a，輸入序列為M=110100， 則有狀態(tài)圖很容易得到編碼序列為C=100100011111。,狀態(tài)圖法,5.4.3 卷積碼的圖解描述,樹圖法,輸入為110100時，編碼輸出為100100011111，如圖中虛線所示,5.4.3 卷積碼的圖解描述,網(wǎng)格圖法,5.4.4 維特比譯碼原理,END,,返回,,結(jié)束,