《信道編碼》PPT課件

《《信道編碼》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《信道編碼》PPT課件（154頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第1章：概述,第2章：信源熵,第3章：信道容量,第4章：信息率失真函數(shù),第5章：信源編碼,第6章：信道編碼,第7章：密碼體制的安全性測(cè)度,6.1 信道編碼的概念 6.2 線形分組碼 6.3 循環(huán)碼 6.4 卷積碼,6.1.1 信道編碼的作用和分類 6.1.2：編碼信道 6.1.3：檢錯(cuò)和糾錯(cuò)原理 6.1.4：檢錯(cuò)和糾錯(cuò)方式和能力,信道編碼是以信息在信道上的正確傳輸為目標(biāo)的編碼，可分為兩個(gè)層次上的問題： 如何正確接收載有信息的信號(hào) 線路編碼 如何避免少量差錯(cuò)信號(hào)對(duì)信息內(nèi)容的影響 糾錯(cuò)編碼,廣義信道編碼=特定信道上傳輸信息而進(jìn)行的傳輸信號(hào)或信號(hào)格式的設(shè)計(jì)與實(shí)現(xiàn),描述編碼 用于對(duì)特定數(shù)據(jù)信號(hào)的

2、描述 約束編碼 用于對(duì)特定信號(hào)特性的約束 擴(kuò)頻編碼 用于擴(kuò)展信號(hào)頻譜為近似白噪聲譜并滿足某些相關(guān)特性 糾錯(cuò)編碼 用于檢測(cè)與糾正信號(hào)傳輸過程中因噪聲干擾導(dǎo)致的差錯(cuò),1,2,3,4, 6.1.1：信道編碼的作用和分類 6.1.2 編碼信道 6.1.3：檢錯(cuò)和糾錯(cuò)原理 6.1.4：檢錯(cuò)和糾錯(cuò)方式和能力,消息,編碼信道模型,n-1,當(dāng)碼字C和接受向量R均由二元序列表時(shí)，稱編碼信道為二進(jìn)制信道 C=(c0,c1,cn-1) 如果對(duì)于任意的n都有： P(r/c)=p(ri/ci) 則稱此二進(jìn)制信道為無記憶二進(jìn)制信道。 p(0/1)=p(1/0)=p0 則稱此

3、信道為無記憶二進(jìn)制對(duì)稱信道BSC,i=0,BSC輸入輸出關(guān)系等效為,差錯(cuò)圖案：隨機(jī)序列 或 ，,第位上的一個(gè)隨機(jī)錯(cuò)誤：,長(zhǎng)的突發(fā)錯(cuò)誤：第 至第 位之間有很多錯(cuò)誤,對(duì)于一個(gè)BSC信道總有轉(zhuǎn)移概率 1/2， 比特傳輸中發(fā)生差錯(cuò)數(shù)目越少，概率越大，即,從而總認(rèn)為發(fā)生差錯(cuò)的圖案是差錯(cuò)數(shù)目較少的圖案,二元軟判決信道,用多個(gè)比特（理想情況下為實(shí)數(shù)）表示每一個(gè)無記憶編碼信道的二元符號(hào)輸出,信道干擾z為零均值正態(tài)分布的隨機(jī)變量，噪聲干擾功率為均方差 ，z的概率分布為 。對(duì)于BPSK調(diào)制，二元輸入符號(hào) 為二元符號(hào)取值為+1或-1, 6.1.1：信道編碼的作用和分類 6.1.2：編碼信道 6.1.3

4、檢錯(cuò)和糾錯(cuò)原理 6.1.4：檢錯(cuò)和糾錯(cuò)方式和能力,檢糾錯(cuò)是根據(jù)信道輸出序列 自身判斷 是否可能是發(fā)送 的，或糾正導(dǎo)致 不等于 的錯(cuò)誤。 冗余編碼：碼字 的長(zhǎng)度 一定大于消息 的長(zhǎng)度,編碼碼率 ：每個(gè)碼字的序列符號(hào)（或碼元）平均傳送的消息比特?cái)?shù),偶（或奇）校驗(yàn)方法：實(shí)現(xiàn)檢糾錯(cuò) 目的的一個(gè)基本方法。,一個(gè)偶校驗(yàn)位 是對(duì)消息 使得如下校驗(yàn)方程成立的二進(jìn)制符號(hào)，即,一個(gè)偶校驗(yàn)碼碼字,一個(gè)碼率為 的 偶校驗(yàn)碼，所有可能的 的全體,校驗(yàn)方程為1表明一定有奇數(shù)個(gè)差錯(cuò)，校驗(yàn)方程為0表明可能有偶數(shù)個(gè)差錯(cuò),m0+m1+m2++mk1+p=0 （mod 2） 稱c=(m0,m1,m2mk-1,p)為一個(gè)偶校

5、驗(yàn)字 確定校驗(yàn)位P的編碼方程為： P=m0+m1++mk-1,編碼可以產(chǎn)生多個(gè)奇偶校驗(yàn)位，即一個(gè)校驗(yàn)位可以由消息位的部分或全部按某種校驗(yàn)方程產(chǎn)生，例如對(duì)陣列消息進(jìn)行垂直與水平校驗(yàn)以及總校驗(yàn)的碼字 和其碼率分別為,重復(fù)消息位：實(shí)現(xiàn)檢糾錯(cuò)目的第二個(gè)基本方法,一個(gè) 重復(fù)碼是一個(gè)碼率為 的碼，僅有兩個(gè)碼字 和 ，傳送1比特（ ）消息。,重復(fù)碼可以檢測(cè)出任意小于 個(gè)差錯(cuò)的錯(cuò)誤圖案，糾正任意小于 個(gè)差錯(cuò)的錯(cuò)誤圖案。,糾1位差錯(cuò) 的3重復(fù)碼,等重碼或定比碼：實(shí)現(xiàn)檢糾錯(cuò)的第三個(gè)方法。,設(shè)計(jì)碼字重量 恒為常數(shù)，即,例如一種用于表示0至9數(shù)字的5中取3等重碼如表（6.1.1）所示，其碼率 為,5中取3等

6、重碼,5中取3等重碼可以檢測(cè)出全部奇數(shù)位差錯(cuò)，對(duì)某些碼字的傳輸則可以檢測(cè)出部分偶數(shù)位差錯(cuò), 6.1.1：信道編碼的作用和分類 6.1.2：編碼信道 6.1.3：檢錯(cuò)和糾錯(cuò)原理 6.1.4 檢錯(cuò)和糾錯(cuò)方式和能力,糾錯(cuò)碼的應(yīng)用方式：前向糾錯(cuò)方式（FEC），自動(dòng)請(qǐng)求重發(fā)（ARQ）方式，混合糾錯(cuò)（HEC）方式以及信息反饋（IRQ方式）,FEC與ARQ糾錯(cuò)應(yīng)用方式,常用漢明距離來描述檢糾差錯(cuò)的數(shù)目，對(duì)于兩n 長(zhǎng)向量u，v漢明距離為：,最小漢明距離 （最小碼距d）：任意兩碼字之間的漢明距離的最小值,定理 對(duì)一個(gè)最小距離為 糾錯(cuò)碼，如下三個(gè)結(jié)論僅有其中任意一個(gè)結(jié)論成立，,（1） 可以檢測(cè)出任意小于等于 個(gè)

7、差錯(cuò)；,（2） 可以糾正任意小于等于 個(gè)差錯(cuò)；,（3）可以檢測(cè)出任意小于等于l同時(shí)糾正小于等于t個(gè)差錯(cuò)，其中l(wèi)和t滿足,最小碼距與檢糾錯(cuò)能力,差錯(cuò)概率：通信作為一個(gè)統(tǒng)計(jì)過程時(shí)，糾檢錯(cuò)能力的統(tǒng)計(jì)特性。,FEC方式糾錯(cuò)碼的碼字差錯(cuò)概率,：發(fā)送碼字 的先驗(yàn)概率,：碼字?jǐn)?shù)，對(duì)于充分隨機(jī)的消息源,對(duì)BSC信道,最大化 等價(jià)于 最小化，最小差錯(cuò)概率譯碼等價(jià)為使接收向量與輸出碼字距離最小的最小距離譯碼，即,信息比特信噪比 ：傳輸一個(gè)比特信息所需的最小信噪比,比特差錯(cuò)概率 （又稱誤碼率）與信噪比 的關(guān)系如下圖所示，采用糾錯(cuò)碼后，達(dá)到同樣比特差錯(cuò)概率實(shí)際需要的信噪比減小量稱為編碼增益。,編碼增益,6.

8、2 線性碼,6.2.1 線性分組碼的描述,6.2.2 線性分組碼的譯碼,6.2.3 碼例與碼的重構(gòu),6.2.1 線性分組碼的描述 6.2.2 線性分組碼的譯碼 6.2.3 碼例與碼的重構(gòu),一個(gè)（n,k）線形分組碼C是稱為碼字c的n維 向量的集合 C=c| c=mG 其中m為任意的k維向量并稱為消息向量。 G是k行n行列秩為k（nk）的矩陣并稱為 生成矩陣，,對(duì)于二元編碼， 和 是二元向量， 是一個(gè)二元矩陣， ，向量與矩陣，矩陣與矩陣之間的基本運(yùn)算是模二加和模二乘運(yùn)算。,表6.2.1 模二加/乘法表,例6.2.1 3重復(fù)碼是一個(gè)（3，1）線性分組碼,例6.2.2（4，3）偶校驗(yàn)碼是一個(gè)

9、（4，3）線性分組碼,當(dāng)生成矩陣 給定時(shí)線性分組碼有如下性質(zhì)： （1）零向量 一定是一個(gè)碼字，稱為零碼字； （2）任意兩碼字的和仍是一個(gè)碼字； （3）任意碼字 是 的行向量 的線性組合； （4）線性分組碼的最小距離等于最小非零碼字重量。,由偶校驗(yàn)碼的檢錯(cuò)概念，可以通過計(jì)算接收向量的所有校驗(yàn)方程值是否為0來判斷傳輸是否可能有錯(cuò)，那么必有一個(gè)矩陣 滿足,顯然 的每一列或 的每一行確定了一個(gè)可能的分組碼的校驗(yàn)方程， 的線性不相關(guān)行數(shù)最少要等于該碼的所有可能的校驗(yàn)方程數(shù)，稱這樣的 矩陣 為 線性分組碼的一致校驗(yàn)矩陣。,由 的每一行都是一個(gè)碼字有,由現(xiàn)行空間的理論，當(dāng)H的行秩為r時(shí)，H作為一個(gè)

10、(n,k) 線性分組碼的生成矩陣所生成的碼是與G對(duì)應(yīng)空間正交 的r維線性子空間，稱為(n,k)線性分組碼的對(duì)偶碼或?qū)?偶空間，并且有如下的維數(shù)關(guān)系成立,T,定理： 任何滿足下式的n維向量a均是一 （n,k）線形分組碼的碼字 aH= 其中滿足公式的H矩陣形式不唯一，但一 個(gè)碼的對(duì)偶碼是惟一的。,T,系統(tǒng)碼：生成矩陣 具有如下形式,在碼字集合不變的情況下，任何一個(gè)線性分組碼都可以一對(duì)一的去對(duì)應(yīng)一個(gè)系統(tǒng)碼。,對(duì)于系統(tǒng)碼相應(yīng)的一致校驗(yàn)矩陣,注意 與 仍然滿足 。,以線性分組碼的一致校驗(yàn)矩陣為生成產(chǎn)生的線性分組碼稱為原線性分組碼的對(duì)偶碼。,,,例6.2.3一個(gè)（5，3）線性

11、分組碼的,其中 到 的行初等變換過程為（ 表示第i行），,（5，3）線性分組碼碼例,由一致校驗(yàn)矩陣可以比較容易確定線性分組碼的最小碼距,定理 線性分組碼的最小碼距為 ，當(dāng)且僅當(dāng)其一致校驗(yàn)矩陣H中任意 列線性無關(guān)，某 列線性相關(guān)。,該定理實(shí)際給出了計(jì)算線性分組碼最小碼距的一種方法。,6.2.1 線性分組碼的描述 6.2.2 線性分組碼的譯碼 6.2.3 碼例與碼的重構(gòu),譯碼的概念,檢錯(cuò)譯碼：譯碼器輸出為當(dāng)前接收向量r和r是否有差錯(cuò)的標(biāo)志s，即 。,糾錯(cuò)譯碼的譯碼成功狀態(tài)：譯碼器能夠在達(dá)到譯碼碼字差錯(cuò)概率最小條件下輸出一個(gè)確切的碼字 ，即 。,糾錯(cuò)譯碼的譯碼成功狀態(tài)：譯碼器能夠在達(dá)到譯碼碼字差

12、錯(cuò)概率最小條件下輸出一個(gè)確切的碼字 ，即 。,糾錯(cuò)譯碼的譯碼失敗狀態(tài)：譯碼器不能輸出一個(gè)確切的碼字，通常此時(shí)的輸出y與檢錯(cuò)譯碼輸出相同。,定義：,(n,k）線形分組碼的伴隨式是一個(gè)r(r=n-k)維向量s,，則傳輸中一定有錯(cuò)誤發(fā)生,，則傳輸中要么無差錯(cuò)發(fā)生，要么差錯(cuò)圖案恰好為一個(gè)碼字。,定理 可糾t錯(cuò)的q元線性分組碼滿足,伴隨式糾錯(cuò)譯碼的通用譯碼方法,（1）按最可能出現(xiàn)的 個(gè)差錯(cuò)圖案 ，計(jì)算相應(yīng) 的伴隨式 ，并構(gòu)造伴隨式差錯(cuò)圖案表 ； （2）對(duì)接收向量 計(jì)算伴隨式 ； （3）查 表得 ； （4）糾錯(cuò)計(jì)算 。,6.2.1 線性分組碼的描述 6.2.2 線性分組碼的譯碼 6.2.3 碼例與

13、碼的重構(gòu),常見的線形分組碼有重復(fù)碼，漢明 碼，里德-穆勒碼，戈雷碼 （1）漢明碼：,二元 Hamming碼是一種 的完備碼，滿足,其中列向量 為全部可能的非零 元組。,Hamming碼的對(duì)偶碼是一個(gè) 線性分組碼，稱為最大長(zhǎng)度碼，由于所有非零碼字的重量均為 ，又稱為等距碼或單形（simplex）碼。,例6.2.4 一個(gè)二元（7，4）Hamming碼的系統(tǒng)碼形式的矩陣和校驗(yàn)矩陣分別為,等價(jià)的編碼方程為,伴隨式計(jì)算方程,（2）Hadamard碼,Hadamard碼是由Hadamard矩陣派生出的一種糾錯(cuò)碼。,階實(shí)Hadamard矩陣由元素為+1，-1的矩陣遞歸定義為,例如,Hadamard

14、矩陣為正交矩陣，即 中的任意不同兩行（列）的點(diǎn)積為0，即,超正交矩陣 ：Hadamard矩陣 中的第1列（全+1列）去掉后由于任兩行的點(diǎn)積為-1。,將Hadamard矩陣元素+1/-1映射為0/1，則Hadamard矩陣映射后的行向量為一個(gè)二元向量，以這些二元向量的部份或全體就構(gòu)成標(biāo)準(zhǔn)0/1二元意義上的分組碼，并稱為Hadamard碼。具體的Hadamard碼的選擇構(gòu)成有正交碼、雙正交碼和超正交碼三種形式。,（A）正交碼：以 的全部行向量的0/1映射向量為碼字。,（B）雙正交碼：以 和- 的全部行向量的0/1映射向量為碼字。,（C）超正交碼：以 的全部行向量的0/1映射向量為碼字。,可以證明正

15、交碼、雙正交碼和超正交碼均是線性分組碼。,例6.2.5（7，3）超正交碼的超正交矩陣 和生成矩陣G分別為,(3)里德-穆勒（Reed-Muller）,階碼 是一種線性分組碼，滿足,其中各個(gè)子矩陣的定義為 1） 為 矩陣，由全1向量構(gòu)成。 2） 為 矩陣，由所有可能的m元組組成矩陣的列向量。 3） 為 的所有兩不同行向量的叉積構(gòu)成其全部行向量的矩陣。兩向量的叉積為 4） 為 的所有三不同行向量的叉積構(gòu)成其全部行向量的矩陣。 5） 為 的所有 個(gè)不同行向量的叉積構(gòu)成其全部行向量的矩陣。,例6.2.6 的 階RM碼的各個(gè)子矩陣有,碼的對(duì)偶碼仍是一個(gè)Reed-Muller碼，為 碼。,（4）

16、戈雷碼 二元戈雷碼是一種就糾3個(gè)錯(cuò)的完備線形分組碼， 滿足： n=23 k=12,,由于,因此某種二元（23,12）碼一定可以糾正任意小于等于3個(gè)差錯(cuò)，所以,6.3 循環(huán)碼,6.3.1循環(huán)碼的多項(xiàng)式描述,6.3.2循環(huán)碼的生成矩陣,6.3.4多項(xiàng)式運(yùn)算電路,6.3.3系統(tǒng)循環(huán)碼,6.3.5循環(huán)碼的編碼電路,6.3.6循環(huán)碼的伴隨多項(xiàng)式與檢測(cè),6.3.7BCH碼與RS碼,6.3.1 循環(huán)碼的多項(xiàng)式描述 6.3.2循環(huán)碼的生成矩陣 6.3.3系統(tǒng)循環(huán)碼 6.3.4多項(xiàng)式運(yùn)算電路 6.3.5循環(huán)碼的編碼電路 6.3.6循環(huán)碼的伴隨多項(xiàng)式與檢測(cè) 6.3.7BCH碼與RS碼,更好

17、的設(shè)計(jì)和實(shí)現(xiàn)線性分組碼的方法是引入特定的數(shù)學(xué)結(jié)構(gòu)來界定某一類線性分組碼。循環(huán)碼即是采用循環(huán)移位特性界定的一類線性分組碼。,6.3.1 循環(huán)碼的多項(xiàng)式描述,定義 如果一個(gè)線性分組碼的任意一個(gè)碼字c(n元組)都是另外一個(gè)碼字c 的循環(huán)移位,稱此線性分組碼為一個(gè)循環(huán)碼.,將循環(huán)碼的碼字用多項(xiàng)式c(x)，稱為碼多項(xiàng)式（簡(jiǎn)稱碼式）表示后，循環(huán)碼集合表示C(x),,例 6.3.2 如下確定的CA是線性循環(huán)碼，CB是非循環(huán)的線性分組碼，CC是非線性的循環(huán)碼。,， ，,定理： （n,k）循環(huán)碼C( x)中存在唯一的一個(gè) 非零的，首一的和最低次為r（r

18、gr-1xr-1+.+g1X+g0 g00 r=n-k 并且c(x)是碼式當(dāng)且僅當(dāng)c(x)是g(x)的倍式,定義 由上述定理確定的碼式g(x)稱為循環(huán)碼(n,k)的生成多項(xiàng)式.,因此(n,k)循環(huán)碼的構(gòu)造是如何構(gòu)造生成多項(xiàng)式g(x)。,循環(huán)碼由生成多項(xiàng)式的倍式組成,定理： g(x)是（n,k）循環(huán)碼的生成多項(xiàng)式， 當(dāng)且僅當(dāng)g(x)是xn-1的r=n-k次因式。,6.3.1循環(huán)碼的多項(xiàng)式描述 6.3.2 循環(huán)碼的生成矩陣 6.3.3系統(tǒng)循環(huán)碼 6.3.4多項(xiàng)式運(yùn)算電路 6.3.5循環(huán)碼的編碼電路 6.3.6循環(huán)碼的伴隨多項(xiàng)式與檢測(cè) 6.3.7BCH碼與RS碼,6.3.2循環(huán)碼的生成

19、矩陣和校驗(yàn)矩陣,(n,k)循環(huán)碼的生成矩陣為,(n,k)循環(huán)碼的校驗(yàn)矩陣為,6.3.1循環(huán)碼的多項(xiàng)式描述 6.3.2循環(huán)碼的生成矩陣 6.3.3 系統(tǒng)循環(huán)碼 6.3.4多項(xiàng)式運(yùn)算電路 6.3.5循環(huán)碼的編碼電路 6.3.6循環(huán)碼的伴隨多項(xiàng)式與檢測(cè) 6.3.7BCH碼與RS碼,6.3.3 系統(tǒng)循環(huán)碼,循環(huán)碼的系統(tǒng)碼碼式為,6.3.1循環(huán)碼的多項(xiàng)式描述 6.3.2循環(huán)碼的生成矩陣 6.3.3系統(tǒng)循環(huán)碼 6.3.4 多項(xiàng)式運(yùn)算電路 6.3.5循環(huán)碼的編碼電路 6.3.6循環(huán)碼的伴隨多項(xiàng)式與檢測(cè) 6.3.7BCH碼與RS碼,6.3.4 多項(xiàng)式運(yùn)算電路,因?yàn)槎囗?xiàng)式,表示時(shí)間序列,所以多項(xiàng)式的計(jì)算表現(xiàn)為對(duì)

20、時(shí)間序列的操作.,多項(xiàng)式a(x)與b(x相加電路,a(x)與g(x)的一般乘法電路,6.3.1循環(huán)碼的多項(xiàng)式描述 6.3.2循環(huán)碼的生成矩陣 6.3.3系統(tǒng)循環(huán)碼 6.3.4多項(xiàng)式運(yùn)算電路 6.3.5 循環(huán)碼的編碼電路 6.3.6循環(huán)碼的伴隨多項(xiàng)式與檢測(cè) 6.3.7BCH碼與RS碼,非循環(huán)碼編碼器 根據(jù)多項(xiàng)式乘法電路和循環(huán)碼碼式是生多 項(xiàng)式倍式原理，多項(xiàng)式乘法電路(圖6.3.4) 是循環(huán)碼的非系統(tǒng)碼電路，又稱為循環(huán)碼乘法編碼電路,圖 6.3.4,2. 系統(tǒng)編碼電路 循環(huán)碼系統(tǒng)編碼電路由乘法電路，求余式電路以及加法開關(guān)電路組成,如圖6.3.14所示,電路工作過程如表6.3.2所示.,圖 6.3

21、.14,表 6.3.2 循環(huán)碼系統(tǒng)碼編碼電路工作過程,6.3.1 循環(huán)碼的多項(xiàng)式描述 6.3.2 循環(huán)碼的生成矩陣 6.3.3 系統(tǒng)循環(huán)碼 6.3.4 多項(xiàng)式運(yùn)算電路 6.3.5 循環(huán)碼的編碼電路 6.3.6 循環(huán)碼的伴隨多項(xiàng)式與檢測(cè) 6.3.7 BCH碼與RS碼,循環(huán)碼的譯碼分成檢錯(cuò)譯碼與糾錯(cuò)譯碼兩類.,1.檢錯(cuò)譯碼原理,2.糾錯(cuò)譯碼 循環(huán)碼的糾錯(cuò)譯碼要達(dá)到碼的最小距離依賴于具體的循環(huán)碼的結(jié)構(gòu).,6.3.1循環(huán)碼的多項(xiàng)式描述 6.3.2循環(huán)碼的生成矩陣 6.3.3系統(tǒng)循環(huán)碼 6.3.4多項(xiàng)式運(yùn)算電路 6.3.5循環(huán)碼的編碼電路 6.3.6循環(huán)碼的伴隨多項(xiàng)式與檢測(cè) 6.3.7 BCH碼與RS

22、碼,BCH碼是一類能夠先確定糾錯(cuò)能力t，然后設(shè)計(jì)碼長(zhǎng)和生成多項(xiàng)式的碼。對(duì)于任意的整數(shù)m和可達(dá)到糾錯(cuò)數(shù)t，都可以構(gòu)造出一個(gè)設(shè)計(jì)距離為d0的二元本原BCH碼滿足： n=2m-1,r=n-kmt,dmind0=2t+1,RS碼是多元BCH碼的一個(gè)子類，碼字向量 的每個(gè)分量可以表示為m比特，其基本參數(shù)為： 碼長(zhǎng)：n=2m-1( 符號(hào))=m(2m-1)（比特） 校驗(yàn)位長(zhǎng)： r=n-k=2t(符號(hào))=m2t 其中t為RS碼可以糾正的差錯(cuò)符號(hào)數(shù).,6.4 卷積碼,6.4.2卷積碼的多項(xiàng)式描述,6.4.3卷積碼的狀態(tài)轉(zhuǎn)移圖與格描述,6.4.4維特比（Viterbi）譯碼算法,6.4.1卷積碼的

23、矩陣描述,6.4.1 卷積碼的矩陣描述 6.4.2卷積碼的多項(xiàng)式描述 6.4.3卷積碼的狀態(tài)轉(zhuǎn)移圖與格描述 6.4.4維特比（Viterbi）譯碼算法,卷積碼編碼：,二元線性卷積碼：,是僅由模二加運(yùn)算組成的布爾函數(shù),,,,,,,線性分組碼的編碼,,,卷積編碼的離散卷積表達(dá)式,,,卷積碼的記憶長(zhǎng)度（段）：,,,結(jié)尾處理：額外輸入,,段無效的0數(shù)據(jù),比特，保證編碼器回到全0的初態(tài),有限,,段長(zhǎng)消息的編碼速率為：,,漸近編碼速率：,,,,,,,,卷積碼的生成矩陣,,,基本生成矩陣,,,,第,,個(gè)生成元,,：,,的第,,行，描述,了所有各段輸入中的第,,位輸入比特,對(duì)所有輸出比特的影響,,將,,的元素

24、,,的列下標(biāo),,表示為,,則輸入移位寄存器中的第,,段的第,,位輸入比特,,參與第,,位輸出比特的編碼,,,不參與第,,位輸出比特的編碼 ,,,線性卷積碼的矩陣（或向量）描述：,生成矩陣,,，基本生成矩陣,,，生成序列（生成元）,,系統(tǒng)卷積碼：卷積碼每段輸出的,,位中有,,位（如當(dāng)前,,位）恒等于每段輸入的,,位,,其中,,均為,,矩陣。,由于對(duì)每個(gè)獨(dú)立的輸入段（每段,,比特，共3段）分別有,,基本生成矩陣,,為,,，生成矩陣為,,，生成元為,,，生成,序列為,,6.4.1卷積碼的矩陣描述 6.4.2 卷積碼的多項(xiàng)式描述 6.4.3卷積碼的狀態(tài)轉(zhuǎn)移圖與格描述 6.4.4維特比（Viterbi）

25、譯碼算法,,,,6.4.2 卷積碼的多項(xiàng)式描述,消息段序列的多項(xiàng)式表示,編碼輸出段序列的多項(xiàng)式表示,,,,,,,定理 線性,,卷積碼的多項(xiàng)式生成矩陣,,,對(duì),,滿足,,的,,冪次項(xiàng)系數(shù)等于,生成序列,,的第,,個(gè)分量，,,1,即,,,的最大次數(shù)等于卷積碼的記,憶長(zhǎng)度,,，即,,2,例6.4.5 前述例（2,1,2）卷積碼重畫如圖,,6.4.1卷積碼的矩陣描述 6.4.2卷積碼的多項(xiàng)式描述 6.4.3 卷積碼的狀態(tài) 轉(zhuǎn)移圖與格描述 6.4.4維特比（Viterbi）譯碼算法,卷積碼與分組碼的明顯區(qū)別是卷積碼編 碼器要存儲(chǔ)m段信息，這些信息數(shù)據(jù)既要 因新的輸入而改變，又要影響當(dāng)前的編碼 輸出，因此

26、稱存儲(chǔ)表達(dá)這些數(shù)據(jù)的參量為 卷積編碼器的內(nèi)部狀態(tài)，簡(jiǎn)稱狀態(tài)。,狀態(tài)：既要因新的輸入而改變，又要,影響當(dāng)前的編碼輸出的數(shù)據(jù)。,,卷積編碼器有效的存貯單元數(shù)為,其中,,為每個(gè)輸入移位寄存器的,有效級(jí)數(shù)（寄存單元數(shù)）。因此二元卷積,碼的狀態(tài)變量記為狀態(tài)向量,,或簡(jiǎn)記為,,狀態(tài)數(shù)：二元,,卷積碼共有,,個(gè)不同的狀態(tài)，記為,,狀態(tài)轉(zhuǎn)移：當(dāng)狀態(tài)為,,（或,,）時(shí)，,輸入段,,（或,,）產(chǎn)生編碼輸出段,,（或,,），并使該,狀態(tài)改變（稱為,轉(zhuǎn)移）到新的狀態(tài),,（或,,）。,狀態(tài)轉(zhuǎn)移方程：,,與,,的關(guān)系,,輸出方程：,,與,,的關(guān)系,,盡管卷積碼有,,個(gè)狀態(tài)，但是由于每段,,的輸入為,,比特只有,,種狀態(tài)的

27、變,化，每個(gè)狀態(tài)只轉(zhuǎn)移到,,個(gè)狀態(tài)的某個(gè),子集（,,個(gè)狀態(tài)）中去，每個(gè)狀態(tài),也只能由某,,個(gè)狀態(tài)的狀態(tài)子集轉(zhuǎn)移,而來。,例 6.4.10,狀態(tài)轉(zhuǎn)移圖（閉合形）,狀態(tài)轉(zhuǎn)移圖（開放形）,狀態(tài)轉(zhuǎn)移方程和輸出方程分別為,卷積編碼器工作過程：,* 卷積編碼器工作初態(tài)為 （全0狀態(tài)）,* 消息段序列 產(chǎn)生輸出段序列,* 消息段序列 產(chǎn)生狀態(tài)序列,柵格圖或籬笆圖：開放形的狀態(tài)轉(zhuǎn)移圖按時(shí)間順序級(jí)聯(lián),編碼路徑：狀態(tài)序列 在柵格圖中形成一條有向路徑,一個(gè)卷積碼碼字：有向路徑始于全0狀態(tài) ，又終于 時(shí)的一條有向路徑,對(duì)于 的卷積碼，常用實(shí)線表示時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支，用虛線表示時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支,例 6.4

28、.13 前述例6.4.1（2，1，2）碼的柵格圖及幾條路徑例,路徑A 消息A（100） 輸出A（11 10 11） 路徑B 消息B（10110） 輸出B（11 10 00 01 01） 路徑C 消息C（110100） 輸出C（11 01 10 01 11）,（1）卷積碼的一個(gè)分支或轉(zhuǎn)移是柵格圖（或狀態(tài)圖）中接續(xù)狀態(tài)的容許連接。 （2） 卷積碼的一條路徑是可容許連接的分支串。 （3）卷積碼的碼字是始于零狀態(tài)并首次終于零狀態(tài)的路徑。,結(jié)論,6.4.1卷積碼的矩陣描述 6.4.2卷積碼的多項(xiàng)式描述 6.4.3卷積碼的狀態(tài)轉(zhuǎn)移圖與格描述 6.4.4 維特比（Viter

29、bi）譯碼算法,卷積碼的最大似然譯碼的基本方法：,尋找一條路徑 使似然值（概率）或?qū)?shù)似然值最大 * 對(duì)應(yīng)于發(fā)送碼字或路徑的接收段序列為 * 各個(gè)碼字假設(shè)為等概發(fā)送,對(duì)于無記憶信道和有限 段接收序列，最大似然譯碼是尋求一條路徑 ，使得,其中 表示一條段記號(hào)從 到 的 段長(zhǎng)路徑,分支似然值：第 時(shí)刻連接至狀態(tài) 的分支的分支度量值 ，簡(jiǎn)記,連接至 最大累積度量值 ：路徑的分支度量值之和的最大值，簡(jiǎn)記,定義,定義,連接至狀態(tài) 幸存路徑：具有最大累積度量值的路徑 的幸存分支： 的最后分支,顯然每個(gè)狀態(tài)有 個(gè)可能的分支度量，每個(gè)狀態(tài)只有一條幸存路徑，每個(gè)時(shí)刻有 個(gè)可能的分支度量，每個(gè)時(shí)刻有

30、 條幸存路徑,定義,有限長(zhǎng)度 的Viterbi算法：,（1.1） 段計(jì)數(shù) =0 （1.2） 最大累積度量值 （1.3）幸存路徑,（1）初始化,（2）迭代,（2.1）接收序列段 （2.2）段計(jì)數(shù)加1， （2.3）對(duì) 重復(fù)進(jìn)行,（2.3.1）對(duì)分別計(jì)算分支度量值 （2.3.2）對(duì) 分別計(jì)算累積度量值 （2.3.3）計(jì)算最大累積度量值 （2.3.4）形成第 狀態(tài) 的幸存分支 ，并存貯到達(dá)此狀態(tài)的幸存路徑,（3）輸出,（3.1）若 ，則返回第（2）步迭代,（3.2）若 ，則求最大累積度量值為的幸存路徑 并輸出該條路徑對(duì)應(yīng)的消息序列 。,例6.4.14 對(duì)例6.4.1非系統(tǒng)（2，1，2）卷積碼的Viterbi譯碼例,設(shè)編碼器輸出為全0比特序列，經(jīng)過BSC，接收序列 為,,* 在Viterbi譯碼的極?。ù螅┯?jì)算中，如果有兩條以上路徑的累積路徑值相等，則任選一條為幸存路徑 * 當(dāng)差錯(cuò)圖案是可糾正的情形時(shí)，Viterbi譯碼過程會(huì)產(chǎn)生路徑合并現(xiàn)象,=（10 00 01 00 00 00 00 ）,自由距離 ：所有非零碼字路徑的最小Hamming重量，即,其中 是長(zhǎng)為 段的非零消息， 是對(duì)應(yīng)的卷積編碼碼字。,例6.4.15對(duì)例6.4.1非系統(tǒng)（2，1，2）碼其自由距離 =5,定義,