第八講卷積碼

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

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

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

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

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

6、碼卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖第一步：假設(shè)寄存器中初始狀態(tài)為全第一步：假設(shè)寄存器中初始狀態(tài)為全0，給出樹的根節(jié)，給出樹的根節(jié)點(diǎn)點(diǎn)卷積碼的表示卷積碼的表示n 樹狀圖樹狀圖第二步：根據(jù)輸入的各種變化，畫出樹的第一層第二步：根據(jù)輸入的各種變化，畫出樹的第一層輸入的比特?cái)?shù)為輸入的比特?cái)?shù)為k，共有，共有 種變化種變化每一種變化對應(yīng)樹的一個(gè)分叉，共有每一種變化對應(yīng)樹的一個(gè)分叉，共有 個(gè)分叉?zhèn)€分叉每輸入每輸入k個(gè)比特，對應(yīng)個(gè)比特，對應(yīng)n個(gè)輸入，每一分叉上標(biāo)上輸出的序列，分叉?zhèn)€輸入，每一分叉上標(biāo)上輸出的序列，分叉的端點(diǎn)為新的狀態(tài)的端點(diǎn)為新的狀態(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)了，則后邊的都是重復(fù)，沒有必要?jiǎng)t后邊的都是重復(fù)，沒有必要再繼續(xù)了再繼續(xù)

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

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

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

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

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

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

14、態(tài)中的一節(jié)狀態(tài)圖對應(yīng)網(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、個(gè)數(shù)的個(gè)數(shù)路徑abca，輸出碼序列111011，最小自由距5卷積碼的表示卷積碼的表示n 解析表示解析表示編碼器的多項(xiàng)式表示編碼器的多項(xiàng)式表示多項(xiàng)式系數(shù)的多項(xiàng)式系數(shù)的8進(jìn)制表示進(jìn)制表示卷積碼的譯碼卷積碼的譯碼n 卷積碼的譯碼方法卷積碼的譯碼方法 維特比譯碼維特比譯碼基于最大似然譯碼基于最大似然譯碼性能接近最優(yōu)性能接近最優(yōu)硬件實(shí)現(xiàn)復(fù)雜硬件實(shí)現(xiàn)復(fù)雜 序列譯碼序列譯碼基于最大似然譯碼基于最大似然譯碼性能接近維特比譯碼時(shí)，譯碼延時(shí)大性能接近維特比譯碼時(shí)，譯碼延時(shí)大譯碼延時(shí)小時(shí)，誤碼率增大譯碼延時(shí)小時(shí)，誤碼率增大 門限譯碼門限譯碼基于分組碼的譯碼思想基于分組碼的譯碼思想性能最差性能最差硬件最簡單硬件最簡單

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

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

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

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

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

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