【正文】 例： 在（ 2,1,9）卷積編碼器中，若初始狀態(tài)為 0000 0000，用十進(jìn)制表示即為 0，輸入序列為 1011，求輸出序列和狀態(tài)變化情況。其中分支輸入表示輸入碼，分支輸出表示分支輸入碼在初始狀態(tài)下通過(guò)（ 2,1,9）卷積編碼器得到的輸出碼。 將狀態(tài)左移 1 位，最低位依次放 入 0、 1，那么 c0 就 是狀態(tài)的 0， 1， 2， 3， 5， 7， 8 位求異或而得到， c1是 狀態(tài) 的 0， 2， 3， 4， 8 位求異或而得到 。 (2,1,9)卷積碼狀態(tài)轉(zhuǎn)換 表 的設(shè)計(jì)算法 （ 2,1,9）卷積碼，有 28個(gè)狀態(tài)，即從 0000 0000 到 1111 1111。而本文所討論的 Viterbi 譯碼的關(guān)鍵算 畢業(yè)設(shè)計(jì)（論文） 第 18 頁(yè) 共 52 頁(yè) 法查表法就是依賴(lài)狀態(tài)轉(zhuǎn)換 表 來(lái)提高程 序效率。a1 放 c0 (2,1,9)的程序仿真 圖 42 是用 CCS 卷積碼編碼器的 96bit 的輸入信息， w 空間的數(shù)據(jù) 圖 42 編碼輸入 經(jīng)過(guò)程序正確運(yùn)行后，我們可以得到 192bit 的輸出數(shù)據(jù)即 wa 空間的數(shù)據(jù) 圖 43 編碼輸出 Wa 空間的數(shù)據(jù)就是 w 空間的數(shù)據(jù)經(jīng)過(guò)（ 2,1,9）卷積后得到的卷積碼。a==b0xorb1xorb2xorb3xorb5xorb7 xor b,8,a 。a==b0xorb1xorb2xorb3 開(kāi)始 B 累加器低 9 位清 0 后，最低位取輸入信息 w A 取輸入信息 w A 累加器與 B 累加器的特定位異或產(chǎn)生 c0 c1 ，存入 wa 空間 B 累加器左移 1 位，最低位取輸入信息 w 96 次？ 結(jié)束 是 否 畢業(yè)設(shè)計(jì)（論文） 第 17 頁(yè) 共 52 頁(yè) xor b,5,a 。a==b0xorb1 xor b,2,a 。 ld *ar2,a 。 其中 卷積碼編碼 程序的重點(diǎn)就是理解 A 累加器與 B 累加器的特點(diǎn)位的異或操作。 分步的值分別放在 A 累加器的第 1 位和第 0 位，即 A 累加器的第 1 位放 c0,第 0 位放 c1,再將 A累加器的值存入 wa 空間。 畢業(yè)設(shè)計(jì)（論文） 第 16 頁(yè) 共 52 頁(yè) (2,1,9)卷積碼編碼流程圖 圖 41 編碼流程圖 (2,1,9)卷積編碼程序?qū)崿F(xiàn) 把 B 累加器的低 9 位當(dāng)做狀態(tài)移存器，左移一位是輸入信息從最低位即第 0位進(jìn)入，第 8 位狀態(tài)舍去。所以要在數(shù)據(jù)區(qū)開(kāi)一個(gè) 96 字的空間 w 用來(lái)接受輸入數(shù)據(jù)序列，并要開(kāi)一個(gè) 192字的空間 wa 來(lái)存儲(chǔ)輸出。然后，再 將 c0 和 c1 合一個(gè)兩位數(shù) c0 c1，即所要求的輸出。即先將 移存 器所存儲(chǔ)的狀態(tài)字左移一位，將輸入的 0 或 1 放在最低位，然后再計(jì)算輸出 c0 c1。 常常用延遲算子多項(xiàng)式來(lái)描述卷積碼。編碼過(guò)程中用到的輸入位數(shù)稱(chēng)為約束長(zhǎng)度，它的值等于延遲單元的數(shù)目加上 1。信息位輸入到移位寄存器中，經(jīng)過(guò)抽頭的提取，采用模 2 和的方式產(chǎn)生輸出。最后以（ 2,1,3）卷積碼譯碼為例，詳細(xì)討論了 Viterbi 譯碼算法中的各個(gè)步驟。其中網(wǎng)格圖對(duì)本文的 Viterbi 譯碼起到促進(jìn)我們理解的作用。 本章小結(jié) 本章 簡(jiǎn)要介紹了卷積碼的概念、表示方法和譯碼。 Viterbi 在衛(wèi)星和深空通信中有廣泛的應(yīng)用。例如，在圖 38 中幸存路徑為 a→ b→ d→ c→ b。 由卷積碼編碼的網(wǎng)格圖 36 可知，當(dāng)?shù)玫綖橐粭l譯碼路徑后，前一級(jí)輸入信息位就是下一級(jí) 4 個(gè)狀態(tài) a（ 00） ,b（ 01） ,c（ 10） ,d（ 11）的最后一位。若把這三個(gè)“ 0”仍然看作是信息位，則可以按 畢業(yè)設(shè)計(jì)（論文） 第 14 頁(yè) 共 52 頁(yè) 照上面的算法 繼續(xù)解碼。圖中粗線路徑時(shí)漢明距離最?。ǖ扔?1）的路徑。它和發(fā)送序列相同，故對(duì)應(yīng)發(fā)送信息位 1101。計(jì)算結(jié)果列于 圖 37 中。 表 31 維特比算法解碼第一步運(yùn)算結(jié)果 序號(hào) 路徑 對(duì)應(yīng)序列 距離 幸存否 序號(hào) 路徑 對(duì)應(yīng)序列 距離 幸存否 1 aaaa 00 00 00 3 否 5 aabc 00 11 10 6 否 2 abca 11 10 11 2 是 6 abdc 11 01 01 1 是 3 aaab 00 00 11 3 否 7 aabd 00 11 01 4 否 4 abcb 11 10 00 2 是 8 abdd 11 01 10 3 是 第二步將繼續(xù)考察接收序列中的后繼 2 位“ 00”。則可以任意保留一條。 現(xiàn)在將達(dá)到的每個(gè)狀態(tài)的兩條路徑的漢明距離 作比較，將距離最小的一條保留，稱(chēng)為幸存路徑。 由出發(fā)點(diǎn)狀態(tài) a 經(jīng)過(guò)三級(jí)路徑到達(dá) b、 c 和 d 的路徑分別都有兩條，故共有 8 條路徑?，F(xiàn)在比較網(wǎng)格圖中的這 8 條路徑和接收序列間的漢明距離。每種狀態(tài)只有兩條路徑到達(dá)。第一步考察接收序列的前 6 位“ 11 00 01 00”。 設(shè)現(xiàn)在的發(fā)送信息位為 1101，為了是圖 25 中的移存器的信息位全部移出，在信息位后面加入三個(gè)“ 0”，故編碼后的發(fā)送序列為 11 01 01 00 10 11 00 并且假設(shè)接收序列為 11 00 01 00 10 11 00，其中第 4 個(gè)碼元為錯(cuò)誤。這條路徑就是要找的最大似然函數(shù)的路徑，也就是譯碼輸出序列。但在 L 時(shí)間單位后，網(wǎng)格圖上的狀態(tài)數(shù)目減少，幸存路徑也相應(yīng)減少。 若 jL+N，則重復(fù)以上步驟，否則停止，譯碼器得到了有最小路徑度量的路徑。對(duì)每一狀態(tài)，挑選并存儲(chǔ)一條最小度量的部分路徑及其部分度量值，稱(chēng)此路徑為幸存路徑。 Viterbi 譯碼算法并不是在網(wǎng)格上一次比較所有可能的 2kL 條路徑（序列），而是接收一段，計(jì)算、比較、選擇一段最可能的碼段（分支），從而達(dá)到整個(gè)碼序列是一個(gè)由最大似然函數(shù)的序列。一個(gè)譯碼器0 1 起始狀態(tài) 00 00 10 00 10 01 11 00 10 01 11 00 10 01 11 圖 33 卷積碼樹(shù)狀圖 畢業(yè)設(shè)計(jì)（論文） 第 12 頁(yè) 共 52 頁(yè) 的譯碼規(guī)則若能在碼字 C 中選擇某一個(gè) iC 使上式最大，則這種譯碼規(guī)則稱(chēng)為最大似然譯碼。C ，則這種譯碼規(guī)則一定使譯碼器輸出錯(cuò)誤概率最小，稱(chēng)這種譯碼規(guī)則為最大后驗(yàn)概率譯。因此，如果譯碼器對(duì)輸入的 R,能在 2K 個(gè)碼字中選擇一個(gè)使 39。( / )P C C R? 最 小，亦即使 39。 當(dāng)給定接收序列 R 時(shí)，譯碼器的條件譯碼錯(cuò)誤概率定義為 39。由于 M 與碼字 C 之間存在一一對(duì)應(yīng)關(guān)系，所以這等價(jià)于譯碼器根據(jù) R 產(chǎn)生一個(gè) C 的估值序列 C’。設(shè)信道輸出的 R 是一個(gè)二進(jìn)制 (或四進(jìn)制 )序列，而譯碼器的輸出是一個(gè)信息序列 M 的估值序列 M’。當(dāng)碼 的約束長(zhǎng)度較短時(shí)，它比 序列 譯碼算法的效率更高，速度更快，目前得到廣泛的應(yīng)用。概率譯碼（又稱(chēng)最大似然譯碼）則是基于信道的統(tǒng)計(jì)特性和卷積碼的特點(diǎn)進(jìn)行計(jì)算。大數(shù)邏輯譯碼，又稱(chēng)門(mén)限譯碼，是卷積碼代數(shù)譯碼的最主要的一種方式。 圖 32 卷積碼網(wǎng)格圖 狀態(tài) a（ 00) 狀態(tài) b（ 01） 狀態(tài) c（ 10） 狀態(tài) d（ 11） 畢業(yè)設(shè)計(jì)（論文） 第 11 頁(yè) 共 52 頁(yè) Viterbi 譯碼 的概述 卷積碼的譯碼方式可以分為兩大類(lèi)：代數(shù)譯碼和概率譯碼。按時(shí)間展開(kāi)，對(duì)應(yīng)每個(gè)狀態(tài)值指出去的上支路（實(shí)線）表示最新輸入數(shù)據(jù)為 0，下支路（虛線）表示最新輸入數(shù)據(jù)為 1，則 編碼過(guò)程的網(wǎng)狀圖如圖 32 所示。通過(guò)卷積碼的幾何描述表示，可以非常清楚和直觀地觀察編碼和解碼的過(guò)程。 可以證明，式（ 34）和（ 35）與時(shí)域運(yùn)算 c1=u*g1 和 c0=u*g0 是等效的，符號(hào) *代表卷積運(yùn)算，編碼輸出序列 c0,c1 是輸入信息序列 u 與編碼器生成多項(xiàng)式的卷積，這就是卷積碼名稱(chēng)的由來(lái)。通常，生成碼字還可以用時(shí)延算子來(lái)表示 84321)(1 DDDDDG ????? （ 31） 875321)(0 DDDDDDDG ??????? （ 32） 式（ 31）和（ 32）中， D 代表時(shí)延算子， D 的冪表示延遲時(shí)間單元數(shù)， D表示延遲 1bit，即上個(gè)時(shí)刻輸入碼元， D2 表示延遲 2bit，即上兩個(gè)時(shí)刻輸入碼元，以此類(lèi)推。 D D D D D D D D 信息比特 （輸入） c0 編碼輸出 c1 編碼輸出 畢業(yè)設(shè)計(jì)（論文） 第 10 頁(yè) 共 52 頁(yè) 卷積碼的表示方法 卷積編碼可以用生成多項(xiàng)式表示， 如果我們將參與異或的位設(shè)為 1，不參與異或的位設(shè)為 0，那么對(duì)應(yīng)于 c0 可以得到一個(gè)二進(jìn)制碼字 111101011，對(duì)應(yīng)于 c1可以得到一個(gè)二進(jìn)制碼字 101110001。 本文采用了的譯碼方式是概率譯碼 —— Viterbi 譯碼，衡量概率譯碼糾錯(cuò)能力是用自由距離 df 來(lái)描述。 衡量卷積碼的糾錯(cuò)能力是用它的距離特性（距離是指兩個(gè)碼字中對(duì)應(yīng)位取值不同的個(gè)數(shù)）來(lái)描述的。圖 31 就是一個(gè)（ 2,1,9）卷積碼編碼器的基本結(jié)構(gòu)。卷積碼的糾錯(cuò)能力隨著 N 的增加而增 大 ,而差錯(cuò)率則隨著 N 的增加呈指數(shù)下降 [17]。 N 表示約束長(zhǎng)度 ,代表編碼后的 n 位碼元不僅與當(dāng)前輸入碼段有關(guān) , 而且與前面 N1 個(gè)輸入碼段的信息有關(guān)。 設(shè)計(jì) 前期算法規(guī)劃 編輯和編譯 創(chuàng)建工程文件、源文件、配置文件 調(diào)試 語(yǔ)法調(diào)試、斷點(diǎn)調(diào)試和日志保存 分析 實(shí)時(shí)調(diào)試、分析統(tǒng)計(jì)和跟蹤 畢業(yè)設(shè)計(jì)（論文） 第 9 頁(yè) 共 52 頁(yè) 基礎(chǔ) 卷積 碼的概述 卷積碼基本原理 卷積碼通常記作 ( n， k， N)。 圖 22 ccs 開(kāi)發(fā)階段 本章小結(jié) 本章著重介紹 DSP 的特點(diǎn)與集成開(kāi)發(fā)環(huán)境 CCS。它有兩種工作模式，一是軟件仿真器，即脫離 DSP 芯片，在 PC 上模擬DSP 指令集與工作機(jī)制，主要用于前期算法和調(diào)試；二是硬件開(kāi)發(fā)板相結(jié)合在線編程，即實(shí)時(shí)運(yùn)行在 DSP 芯片上，可以在線編制和調(diào)試應(yīng)用程序。如此可以利用優(yōu)化的片內(nèi)硬件促進(jìn) Viterbi 的蝶形運(yùn)算。 CSSU 通過(guò) CMPS 指令完成比較、選擇操作 [7]。將 ST1 中的 C16 位置 1， ALU 被設(shè)為雙 16位工作模式，這樣 就可以在一個(gè)機(jī)器周期內(nèi)同時(shí)完成倆次加法運(yùn)算。 CSSU 支持信道譯碼器所用的各種 Viterbi 算法。 CSSU 單元概述 比較、 選擇和存儲(chǔ)單元是 TMS320C54X 器件專(zhuān)門(mén)為 Viterbi 算法設(shè)計(jì)的加法、比較、選擇（ ACS）操作的硬件單元。除了片內(nèi)程序存儲(chǔ)器外， DSP 芯片一般還集成數(shù)據(jù) RAM，用于存放參數(shù)和數(shù)據(jù)。而 DSP 算法的特點(diǎn)是需要大量的簡(jiǎn)單計(jì)算，其相應(yīng)的程序比較短小。通用微處理器的特點(diǎn)是程序一般都很大，片內(nèi)存儲(chǔ)器不會(huì)給處理器性能帶來(lái)明顯改善。 TI 宣稱(chēng)到 20xx 年，其 DSP 的處理能力可以達(dá)到3 10E6 兆條指令 /s。 (6) 高速的時(shí)鐘周期和強(qiáng)大的處理能力 DSP 芯片的主頻和處理能力不斷地提高， TMS320C5000 系列 DSP 的 主頻已經(jīng)達(dá)到 200MHz。由于有些算法通常需要一次從存儲(chǔ)器中取兩個(gè)操作數(shù)，因 畢業(yè)設(shè)計(jì)（論文） 第 7 頁(yè) 共 52 頁(yè) 此 DSP 內(nèi)的地址產(chǎn)生器一般也有兩個(gè)。 DSP 通常都有支持地址計(jì)算的算術(shù)單元 —— 地址產(chǎn)生器。伴隨著頻繁的數(shù)據(jù)訪問(wèn)，數(shù)據(jù)地址的計(jì)算時(shí)間也線性增長(zhǎng)，有時(shí)計(jì)算地址的時(shí)間比實(shí)際的算術(shù)操作還長(zhǎng)。硬件乘法器是 DSP 區(qū)別于通用微處理器的一個(gè)重要標(biāo)志。另一方面，各種算法也在不斷地改進(jìn)，盡量減少乘法運(yùn)算。 (4) 采用硬件乘法器 一般計(jì)算機(jī)沒(méi)有硬件乘法器，它的算術(shù)邏輯單元只能完成兩個(gè)操作數(shù)的加、減和邏輯運(yùn)算，而乘法和除法時(shí)由加法和 移 位來(lái)實(shí)現(xiàn)，因此在一般的計(jì)算機(jī)上實(shí)現(xiàn)乘法和除法很費(fèi)時(shí)間。采用線性匯編語(yǔ)言編程，程序效率可以達(dá)到標(biāo)準(zhǔn)匯編程序效率 的 95%— 100%。模擬設(shè)備