第八講卷積碼

1、主要內容主要內容n 卷積碼卷積碼卷積碼與分組碼的區(qū)別與聯(lián)系卷積碼與分組碼的區(qū)別與聯(lián)系卷積碼的表示卷積碼的表示卷積碼的性質卷積碼的性質維特比譯碼原理維特比譯碼原理基于網(wǎng)格圖的維特比譯碼基于網(wǎng)格圖的維特比譯碼為什么要采用卷積碼？為什么要采用卷積碼？卷積碼可以用哪些形式進行表示？卷積碼可以用哪些形式進行表示？卷積碼的距離特性如何？如何求解？卷積碼的距離特性如何？如何求解？維特比譯碼的基本原理是什么？維特比譯碼的基本原理是什么？維特比譯碼如何實現(xiàn)？維特比譯碼如何實現(xiàn)？研究對象研究對象n 研究對象在通信系統(tǒng)中的位置研究對象在通信系統(tǒng)中的位置 格式化 信源 編碼 加密 信道 編碼 多路 復用 脈沖 調制

2、帶通 調制 頻率 擴展 復用 多址 接入 格式化 信源 譯碼 解密 信道 譯碼 多路 分接 檢測 解調 采樣 頻率 解擴 復用 多址 接入 信源 信宿 消息碼元 數(shù)字輸入消息碼元 消息碼元 數(shù)字輸出消息碼元 比特流 數(shù)字基帶波形 數(shù)字頻帶波形 信 道 同步 卷積碼的概念卷積碼的概念n 為什么要引入卷積碼為什么要引入卷積碼回顧分組碼回顧分組碼把把k位信息比特的序列編成位信息比特的序列編成n個比特的碼組，每個碼個比特的碼組，每個碼組的組的(n-k)位校驗碼僅與本碼組的位校驗碼僅與本碼組的k位信息有關，而與位信息有關，而與其他碼組無關其他碼組無關回顧香農信道編碼定理回顧香農信道編碼定理在信道容量與發(fā)

3、送信息速率一定的條件下，增加碼在信道容量與發(fā)送信息速率一定的條件下，增加碼長，可以使錯誤概率指數(shù)下降長，可以使錯誤概率指數(shù)下降由此引起的問題由此引起的問題線性分組碼增加碼長，必然導致編解碼的延時加大線性分組碼增加碼長，必然導致編解碼的延時加大，復雜度也隨之增大，如何解決這一矛盾？，復雜度也隨之增大，如何解決這一矛盾？卷積碼的概念卷積碼的概念n 卷積碼卷積碼將將k位信息編成位信息編成n個比特，但此個比特，但此n個比特不但與當前位的個比特不但與當前位的k個信息有關，而且與前面?zhèn)€信息有關，而且與前面(N-1)組的信息有關。編碼中組的信息有關。編碼中相互關聯(lián)的碼元為相互關聯(lián)的碼元為N*n位位卷積碼的糾

4、錯能力隨著卷積碼的糾錯能力隨著N的增加而增大，而差錯率隨著的增加而增大，而差錯率隨著N的增加而成指數(shù)下降的增加而成指數(shù)下降類似輸入序列與某一特定序列的卷積卷積碼的表示卷積碼的表示n 卷積碼的參數(shù)卷積碼的參數(shù)（n，k，N）N：約束長度，移位寄存器的級數(shù)（每級有：約束長度，移位寄存器的級數(shù)（每級有k個個)k：信息碼位的數(shù)目，是卷積碼編碼器的每級輸入的比：信息碼位的數(shù)目，是卷積碼編碼器的每級輸入的比特數(shù)目特數(shù)目n：k位信息碼對應編碼后的輸出的比特數(shù)，它與位信息碼對應編碼后的輸出的比特數(shù)，它與Nk個個輸入比特相關輸入比特相關碼率碼率卷積碼的表示卷積碼的表示n 最直觀的描述最直觀的描述編碼器框圖編碼器框

5、圖缺點：無法進行任何數(shù)學討論，無法給出解碼方案缺點：無法進行任何數(shù)學討論，無法給出解碼方案n 更有用的描述更有用的描述樹狀圖表示：遍歷可能性，用于分析最小距離樹狀圖表示：遍歷可能性，用于分析最小距離網(wǎng)格圖表示：用于網(wǎng)格圖表示：用于Viterbi解碼解碼狀態(tài)圖與生成函數(shù)：用于分析自由距狀態(tài)圖與生成函數(shù)：用于分析自由距半無限矩陣表示：用于類比分組碼半無限矩陣表示：用于類比分組碼從例子入手，從基本的樹狀圖開始，進一步到狀態(tài)圖及網(wǎng)格圖卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖基本思想基本思想利用樹的結構表征移位過程中產生的各種序列利用樹的結構表征移位過程中產生的各種序列例子例子（2，1，3）卷積碼）卷積

6、碼卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖第一步：假設寄存器中初始狀態(tài)為全第一步：假設寄存器中初始狀態(tài)為全0，給出樹的根節(jié)，給出樹的根節(jié)點點卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖第二步：根據(jù)輸入的各種變化，畫出樹的第一層第二步：根據(jù)輸入的各種變化，畫出樹的第一層輸入的比特數(shù)為輸入的比特數(shù)為k，共有，共有 種變化種變化每一種變化對應樹的一個分叉，共有每一種變化對應樹的一個分叉，共有 個分叉?zhèn)€分叉每輸入每輸入k個比特，對應個比特，對應n個輸入，每一分叉上標上輸出的序列，分叉?zhèn)€輸入，每一分叉上標上輸出的序列，分叉的端點為新的狀態(tài)的端點為新的狀態(tài)分支的排列順序相同，如上分支為輸入分支的排列順序相同，

7、如上分支為輸入0，下分支為輸入，下分支為輸入1狀態(tài)a卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖第三步：按照第二步的方法，繼續(xù)畫出樹的第二層、第第三步：按照第二步的方法，繼續(xù)畫出樹的第二層、第三層三層狀態(tài)b狀態(tài)c卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖第三步：繼續(xù)第三步：繼續(xù)狀態(tài)d卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖 第四步：還要再繼續(xù)嗎？第四步：還要再繼續(xù)嗎？狀態(tài)是有限的狀態(tài)是有限的 （n，k，N）卷積碼的狀）卷積碼的狀態(tài)數(shù)態(tài)數(shù) （2，1，3）卷積碼的狀態(tài)）卷積碼的狀態(tài)數(shù)數(shù)4只要狀態(tài)及其分支都出現(xiàn)了，只要狀態(tài)及其分支都出現(xiàn)了，則后邊的都是重復，沒有必要則后邊的都是重復，沒有必要再繼續(xù)了再繼續(xù)

8、了 （2，1，3）卷積碼共有）卷積碼共有4個狀態(tài)，樹狀圖第二層即個狀態(tài)，樹狀圖第二層即出現(xiàn)了所有狀態(tài)，因此畫出現(xiàn)了所有狀態(tài)，因此畫到樹狀圖的第三層就可以到樹狀圖的第三層就可以了，此后即是重復了，此后即是重復卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖由樹狀圖求卷積碼的最小距由樹狀圖求卷積碼的最小距卷積碼也是線性碼，卷積具有線性性質卷積碼也是線性碼，卷積具有線性性質類似于分組碼，卷積碼的最小碼距也定義為非零碼類似于分組碼，卷積碼的最小碼距也定義為非零碼字的最小碼重字的最小碼重卷積碼中的碼字卷積碼中的碼字:卷積碼沒有分組的概念卷積碼沒有分組的概念約束長度隱含某種獨立性，即可以考慮約束長度隱含某種獨立性

9、，即可以考慮kN個信息個信息比特編碼后輸出的碼序列，即比特編碼后輸出的碼序列，即nN個編碼輸出序列個編碼輸出序列非零碼字，離開全零狀態(tài)，經(jīng)過約束長度個輸入非零碼字，離開全零狀態(tài)，經(jīng)過約束長度個輸入后的一串編碼輸出后的一串編碼輸出卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖由樹狀圖求卷積碼的最小距由樹狀圖求卷積碼的最小距（2，1，3)卷積碼求最小距卷積碼求最小距因為要離開全零狀態(tài)，樹狀圖的上半部不用考慮因為要離開全零狀態(tài)，樹狀圖的上半部不用考慮約束長度為約束長度為3，只考慮，只考慮 三級即可三級即可卷積碼的表示卷積碼的表示n 狀態(tài)圖狀態(tài)圖從樹狀圖到狀態(tài)圖從樹狀圖到狀態(tài)圖對樹狀圖進行精簡，對樹狀圖進行

10、精簡，去掉冗余的部分（樹去掉冗余的部分（樹狀圖中重復的部分）狀圖中重復的部分）狀態(tài)圖狀態(tài)圖節(jié)點是編碼器的狀節(jié)點是編碼器的狀態(tài)態(tài)邊表示狀態(tài)的轉移邊表示狀態(tài)的轉移邊上標注對應該轉邊上標注對應該轉移的輸出移的輸出卷積碼的表示卷積碼的表示n 狀態(tài)圖狀態(tài)圖（2，1，3）的例子）的例子卷積碼的表示卷積碼的表示n 狀態(tài)圖狀態(tài)圖由狀態(tài)圖計算自由距由狀態(tài)圖計算自由距自由距：無限長編碼后序列之間的最小漢明距離（自由距：無限長編碼后序列之間的最小漢明距離（卷積碼不分組，自由距作為卷積碼糾錯性能的度量更卷積碼不分組，自由距作為卷積碼糾錯性能的度量更合理）合理）自由距不小于最小距自由距不小于最小距自由距的求解自由距的求

11、解全零是一個無限長的編碼后序列，因此編碼后的全零是一個無限長的編碼后序列，因此編碼后的非零序列應包含盡可能多的零，從而保證與全零非零序列應包含盡可能多的零，從而保證與全零序列之間具有最小的漢明距序列之間具有最小的漢明距從全零出發(fā)，經(jīng)歷非零狀態(tài)，又重新回到全零過從全零出發(fā)，經(jīng)歷非零狀態(tài)，又重新回到全零過程中輸出的程中輸出的1的最少的個數(shù)即為自由距的最少的個數(shù)即為自由距卷積碼的表示卷積碼的表示n 狀態(tài)圖狀態(tài)圖由狀態(tài)圖計算自由距由狀態(tài)圖計算自由距（2，1，3）卷積碼為例）卷積碼為例狀態(tài)圖變形：從狀態(tài)圖變形：從a出發(fā)重新回到出發(fā)重新回到a的所有路徑的所有路徑卷積碼的表示卷積碼的表示n 狀態(tài)圖狀態(tài)圖由狀

12、態(tài)圖計算自由距由狀態(tài)圖計算自由距狀態(tài)圖和碼距、轉移次數(shù)等關聯(lián)起來狀態(tài)圖和碼距、轉移次數(shù)等關聯(lián)起來定義轉移的增益為定義轉移的增益為 ，其中，其中 表示輸出表示輸出序列的漢明重量，序列的漢明重量， 表示輸入序列的漢明重量，表示輸入序列的漢明重量，L為轉移的支路數(shù)目為轉移的支路數(shù)目卷積碼的表示卷積碼的表示n 狀態(tài)圖狀態(tài)圖由狀態(tài)圖計算自由距由狀態(tài)圖計算自由距根據(jù)梅森公式計算從根據(jù)梅森公式計算從a到到a的轉移函數(shù)的轉移函數(shù)存在長度為3的支路（L的冪次為3），碼重為5（D的冪次為5），其它支路對應項中D的冪次大于5，所以5就是自由距卷積碼的表示卷積碼的表示n 網(wǎng)格圖網(wǎng)格圖 由樹狀圖到網(wǎng)格圖由樹狀圖到網(wǎng)格圖

13、樹狀圖中的狀態(tài)用分行的點表示，每一層樹狀圖中相同狀態(tài)的節(jié)點樹狀圖中的狀態(tài)用分行的點表示，每一層樹狀圖中相同狀態(tài)的節(jié)點合并到網(wǎng)格圖中的每列相同的點合并到網(wǎng)格圖中的每列相同的點樹狀圖的每一層對應網(wǎng)格圖中的每一級樹狀圖的每一層對應網(wǎng)格圖中的每一級樹狀圖中的分支對應網(wǎng)格圖中的連線（每一分支代表一種輸入，分樹狀圖中的分支對應網(wǎng)格圖中的連線（每一分支代表一種輸入，分支的排列按照相同的規(guī)則支的排列按照相同的規(guī)則(例如（例如（2，1，3）中上分支代表）中上分支代表0輸入，下輸入，下分支代表分支代表1輸入）輸入）卷積碼的表示卷積碼的表示n 網(wǎng)格圖網(wǎng)格圖網(wǎng)格圖與狀態(tài)圖的對應網(wǎng)格圖與狀態(tài)圖的對應狀態(tài)圖對應網(wǎng)格圖中穩(wěn)

14、態(tài)中的一節(jié)狀態(tài)圖對應網(wǎng)格圖中穩(wěn)態(tài)中的一節(jié)卷積碼的表示卷積碼的表示n 網(wǎng)格圖網(wǎng)格圖網(wǎng)格圖可以表征編碼過程網(wǎng)格圖可以表征編碼過程根據(jù)輸入的碼序列確定了一條路徑，這條路徑上的根據(jù)輸入的碼序列確定了一條路徑，這條路徑上的所有輸出連接起來就是輸出的碼序列所有輸出連接起來就是輸出的碼序列網(wǎng)格圖在卷積碼的維特比譯碼中具有非常重要的作用網(wǎng)格圖在卷積碼的維特比譯碼中具有非常重要的作用輸入：輸入：11001100輸出：輸出：1101010011010100卷積碼的表示卷積碼的表示n 網(wǎng)格圖網(wǎng)格圖由網(wǎng)格圖求解最小自由距由網(wǎng)格圖求解最小自由距從全零出發(fā)回到全零的輸出序列的最少的從全零出發(fā)回到全零的輸出序列的最少的1的

15、個數(shù)的個數(shù)路徑abca，輸出碼序列111011，最小自由距5卷積碼的表示卷積碼的表示n 解析表示解析表示編碼器的多項式表示編碼器的多項式表示多項式系數(shù)的多項式系數(shù)的8進制表示進制表示卷積碼的譯碼卷積碼的譯碼n 卷積碼的譯碼方法卷積碼的譯碼方法 維特比譯碼維特比譯碼基于最大似然譯碼基于最大似然譯碼性能接近最優(yōu)性能接近最優(yōu)硬件實現(xiàn)復雜硬件實現(xiàn)復雜 序列譯碼序列譯碼基于最大似然譯碼基于最大似然譯碼性能接近維特比譯碼時，譯碼延時大性能接近維特比譯碼時，譯碼延時大譯碼延時小時，誤碼率增大譯碼延時小時，誤碼率增大 門限譯碼門限譯碼基于分組碼的譯碼思想基于分組碼的譯碼思想性能最差性能最差硬件最簡單硬件最簡單

16、卷積碼的譯碼卷積碼的譯碼n 最大似然譯碼最大似然譯碼 模型模型 數(shù)學描述數(shù)學描述譯碼器必須根據(jù)接收序列譯碼器必須根據(jù)接收序列y來產生信息序列來產生信息序列M的一個估計的一個估計M。如果二者不同，則表明譯碼器出現(xiàn)差錯。如果二者不同，則表明譯碼器出現(xiàn)差錯。信息序列信息序列M經(jīng)過編碼器輸出經(jīng)過編碼器輸出X，二者之間有一一對應的關系；，二者之間有一一對應的關系；譯碼器產生的碼字是譯碼器產生的碼字是X的一個估值的一個估值X，只有當，只有當X=X時，時，M=M，即無誤碼，即無誤碼如果信道中傳送的碼字是如果信道中傳送的碼字是X，當且僅當，當且僅當X/=X 出現(xiàn)譯碼錯誤出現(xiàn)譯碼錯誤卷積碼的譯碼卷積碼的譯碼n

17、最大似然譯碼最大似然譯碼錯誤概率最小的條件錯誤概率最小的條件進一步推導進一步推導物理意義：譯碼器在收到物理意義：譯碼器在收到Y序列的情況下，選擇具有序列的情況下，選擇具有最大條件概率最大條件概率 的序列的序列X作為譯碼輸出，則作為譯碼輸出，則將使譯碼后的序列具有最小差錯概率。這種譯碼器稱將使譯碼后的序列具有最小差錯概率。這種譯碼器稱為為最大似然譯碼最大似然譯碼卷積碼的譯碼卷積碼的譯碼n 最大似然譯碼最大似然譯碼最大似然譯碼的具體做法最大似然譯碼的具體做法定義，編碼器輸出序列定義，編碼器輸出序列X的長度為的長度為L，經(jīng)信道傳輸后，經(jīng)信道傳輸后比特錯誤概率為比特錯誤概率為p，發(fā)生錯誤的比特數(shù)為，發(fā)

18、生錯誤的比特數(shù)為e上式中，上式中，A和和B為常數(shù)，由編碼序列長度以及信道所為常數(shù)，由編碼序列長度以及信道所決定，要使上式最大化，則要求決定，要使上式最大化，則要求e最小，即最小，即X和和Y序列序列之間的漢明距離最?。≈g的漢明距離最??！最大似然譯碼就是尋求和Y序列之間具有最小漢明距離的X序列！卷積碼的譯碼卷積碼的譯碼n 還是先看一個例子還是先看一個例子（2，1，3）卷積碼）卷積碼接收碼序列接收碼序列11010100路徑abdcb與接收序列完全對應，漢明距為0，譯碼輸出1100卷積碼的譯碼卷積碼的譯碼n 還是先看一個例子還是先看一個例子（2，1，3）卷積碼）卷積碼接收碼序列接收碼序列110101

19、10出現(xiàn)錯誤出現(xiàn)錯誤在網(wǎng)格圖上找一條路徑，其對應的編碼輸出與接收在網(wǎng)格圖上找一條路徑，其對應的編碼輸出與接收到的碼字漢明距離最小，并將其對應的信息碼元作為到的碼字漢明距離最小，并將其對應的信息碼元作為編碼輸出編碼輸出問題來了：漢明問題來了：漢明距一樣，選哪一距一樣，選哪一條？條？卷積碼的譯碼卷積碼的譯碼n 還是先看一個例子還是先看一個例子（2，1，3）卷積碼）卷積碼接收碼序列接收碼序列1101010011000001無限長，怎么辦？無限長，怎么辦？等所有碼都接收下來以后再找漢明距最小的路徑？等所有碼都接收下來以后再找漢明距最小的路徑？顯然不可行，實時性太差了顯然不可行，實時性太差了如果無限長則

20、根本做不到，存儲器不可能無限大如果無限長則根本做不到，存儲器不可能無限大n 總結最大似然譯碼中的兩個問題總結最大似然譯碼中的兩個問題可能出現(xiàn)多個具有相同漢明距離的分支可能出現(xiàn)多個具有相同漢明距離的分支譯碼的實時性如何保證譯碼的實時性如何保證n 維特比譯碼維特比譯碼基于動態(tài)規(guī)劃的方法進行實時譯碼基于動態(tài)規(guī)劃的方法進行實時譯碼維特比譯碼維特比譯碼n 幾個概念幾個概念路徑量度路徑量度該路徑輸出序列與接收序列之間的漢明距離該路徑輸出序列與接收序列之間的漢明距離含有多段路徑的一條路徑總的量度等于所有各段路含有多段路徑的一條路徑總的量度等于所有各段路徑量度的總和徑量度的總和幸存路徑幸存路徑經(jīng)過量度比較之后

21、總量度較小的路徑被保留下來，經(jīng)過量度比較之后總量度較小的路徑被保留下來，稱為幸存路徑稱為幸存路徑維特比譯碼維特比譯碼n 先看一個簡單例子先看一個簡單例子動態(tài)規(guī)劃方法動態(tài)規(guī)劃方法找出下圖中總量度最小的一條路徑（沒標量度值的為找出下圖中總量度最小的一條路徑（沒標量度值的為0)基本的規(guī)則：當前最優(yōu)路徑只能產生于上一步的最基本的規(guī)則：當前最優(yōu)路徑只能產生于上一步的最優(yōu)路徑優(yōu)路徑+當前一步的組合中當前一步的組合中第一步：第一步：aa、bb幸存，幸存，ab、ba淘汰淘汰第二步：第二步：aab、bba幸存，幸存，aaa、bbb淘汰淘汰第三步：第三步：aaba、aabb幸存，幸存，bbab、bbaa淘汰淘汰維特比譯碼維特比譯碼n 先看一個簡單例子先看一個簡單例子動態(tài)規(guī)劃方法動態(tài)規(guī)劃方法找出下圖中總量度最小的一條路徑找出下圖中總量度最小的一條路徑注意第三步的結果注意第三步的結果此時幸存的最優(yōu)路徑都是從此時幸存的最優(yōu)路徑都是從aab衍生出來，因此，衍生出來，因此，不管后邊如何發(fā)展，