卷積碼的維特比譯碼

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)卷積碼的維特比譯碼卷積編碼器自身具有網(wǎng)格結(jié)構(gòu)，基于此結(jié)構(gòu)我們給出兩種譯碼算法：Viterbi 譯碼算法和 BCJR 譯碼算法。基于某種準則，這兩種算法都是最優(yōu)的。1967 年，Viterbi 提出了卷積碼的 Viterbi 譯碼算法，后來 Omura 證明 Viterbi 譯碼算法等效于在加權圖中尋找最優(yōu)路徑問題的一個動態(tài)規(guī)劃（Dynamic Programming）解決方案，隨后，F(xiàn)orney 證明它實際上是最大似然（ML，Maximum Likelihood）譯碼算

2、法，即譯碼器選擇輸出的碼字通常使接收序列的條件概率最大化。BCJR 算法是 1974 年提出的，它實際上是最大后驗概率（MAP，Maximum A Posteriori probability）譯碼算法。這兩種算法的最優(yōu)化目標略有不同：在 MAP 譯碼算法中，信息比特錯誤概率是最小的，而在 ML 譯碼算法中，碼字錯誤概率是最小的，但兩種譯碼算法的性能在本質(zhì)上是相同的。由于 Viterbi 算法實現(xiàn)更簡單，因此在實際應用比較廣泛，但在迭代譯碼應用中，例如逼近 Shannon 限的 Turbo 碼，常使用 BCJR 算法。另外，在迭代譯碼應用中，還有一種 Viterbi 算法的變種：軟輸出 Vit

3、erbi 算法（SOVA，Soft-Output Viterbi Algorithm），它是 Hagenauer 和 Hoeher 在 1989 年提出的。為了理解 Viterbi 譯碼算法，我們需要將編碼器狀態(tài)圖按時間展開（因為狀態(tài)圖不能反映出時間變化情況），即在每個時間單元用一個分隔開的狀態(tài)圖來表示。例如（3，1，2）非系統(tǒng)前饋編碼器，其生成矩陣為： GD=1+D1+D21+D+D2 （1）圖1 （a）（3，1，2）編碼器 （b）網(wǎng)格圖（h5） 假定信息序列長度為 h5，則網(wǎng)格圖包含有 hm18 個時間單元，用 0 到 hm 7 來標識，如圖1（b）所示。假設編碼器總是從全 0 態(tài) S0

4、開始，又回到全 0 態(tài)，前 m2 個時間單元對應于編碼器開始從 S0“啟程”，最后 m2 個時間單元對應于向 S0 “返航”。從圖中我們也可以看到，在前 m 個時間單元或最后 m 個時間單元，并不是所有狀態(tài)都會出現(xiàn)，但在網(wǎng)格圖的中央部分，在每個時間單元都會包含所有狀態(tài)，且在每個狀態(tài)都有 2k2 個分支離開和到達。離開每個狀態(tài)的上面分支表示輸入比特為 1（即 ui1，i 表示第 i 個時間單元），下面的分支表示輸入比特為 0。每個分支的輸出vi 由 n 個比特組成，共有 2h32 個碼字，每個碼字都可用網(wǎng)格圖中的唯一路徑表示，碼字長度 Nn(hm)21。例如當信息序列為u（11101）時，對應的

5、碼字如圖1（b）中紅線所示，v（111，010，001， 110，100，101，011）。在一般的（n，k，v）編碼器情況下，信息序列長度 K*=kh，離開和進入每個狀態(tài)都有 2k 個分支，有2K* 個不同路徑通過網(wǎng)格圖，對應著2K* 個碼字。假設長度K*=kh的信息序列u=(u0,u1 uh-1) 被編碼成長度為 N=n(h+m) 的碼字v=(v0, v1 vh+m+1) ，在經(jīng)過一個二進制輸入、Q-ary 輸出的離散無記憶信道（DMC， Discrete Memoryless Channel ）后，接收序列為r=(r0 ,r1 rh+m+1)。也可表示為： u=(u0 ,u1 uK*-1

6、) ，v=(v0 ,v1 vN-1)，r=(r0,r1 rN-1)，譯碼器對接收到的序列r進行處理，得到 v 的估計v。在離散無記憶信道情況下，最大似然譯碼器是按照最大化對數(shù)似然函數(shù)log P(r | v) 作為選擇v的準則。因為對于 DMC， Prv=l=0h+m-1Prlvl=l=0N-1Prlvl （2）兩邊取對數(shù)后為： logPrv=l=0h+m-1logPrlvl=l=0N-1logPrlvl （3）其中P(rl | vl )是信道轉(zhuǎn)移概率，當所有碼字等概時，這是個最小錯誤概率譯碼準則。對數(shù)似然函數(shù) log P(r | v) ，用 M(r |v )表示，稱為路徑度量（path met

7、ric）；log P(rl | vl ) ，稱為分支度量（branch metric），用M(rl | vl ) 表示；log P(rl | vl ) 稱為比特度量（bit metric），用M(rl | vl )表示，這樣（3）式可寫為： M(r|v)=l=0h+m-1M(rl | vl )=l=0N-1M(rl | vl ) （4）如果我們只考慮前 t 個分支，則部分路徑度量可表示為： M(r|v)=l=0t-1M(rl | vl )=l=0nt-1M(rl | vl ) （5）對于接收序列r，Viterbi 算法就是通過網(wǎng)格圖找到具有最大度量的路徑，即最大似然路徑（碼字）。在每個時間單元

8、的每個狀態(tài)，都增加2k個分支度量到以前存儲的路徑度量中（加）；然后對進入每個狀態(tài)的所有 2k 個路徑度量進行比較（比），選擇具有最大度量的路徑（選），最后存儲每個狀態(tài)的幸存路徑及其度量。 Viterbi 算法： Step 1: 在 tm 時間單元開始，計算進入每個狀態(tài)的單個路徑的部分度量，存儲每個狀態(tài)的路徑（幸存）及其度量； Step 2: tt1，對進入每個狀態(tài)的所有 2k 個路徑計算部分度量，并加上前一時間單元的度量。對于每個狀態(tài)，比較進入該狀態(tài)的所有 2k 個路徑度量，選擇具有最大度量的路徑，存儲其度量，并刪掉其他路徑。 Step 3: 如果 th+m，返回 step 2；否則，就停止。

9、 Viterbi 算法的基本計算“加、比、選”體現(xiàn)在 step 2。注：實際工程中，在每個狀態(tài)存儲（在 step 1 和 step 2）的是對應于幸存路徑的信息序列，而不是幸存路徑自身，這樣當算法結(jié)束時，就無需再通過估計碼字v 來恢復信息序列u 。從時間單元 m 到 h，有2v 個幸存路徑，每個狀態(tài)（共有 2v 個狀態(tài)）一個。隨后，幸存路徑數(shù)就會變少，因為當編碼器回到全 0 態(tài)時，狀態(tài)數(shù)就會變少。最后，在時間單元 hm，就只有一個狀態(tài)（即全 0 態(tài)），因此，也就只有一個幸存路徑了，算法中止。定理1：在 Viterbi 算法中最后的幸存路徑v 是最大似然路徑，即 MrvMrv, for vv （

10、6）從實現(xiàn)的角度看，用正整數(shù)度量來表示要比用實際的比特度量表示更方便。比特度量M(rl | vl )=log P(rl | vl )可用c2log P(rl | vl )+c1來代替，其中 c1 是任意實數(shù)，c2 是任意正實數(shù)。可證明，如果路徑 v 最大化M(r|v)=l=0N-1M(rl | vl )=l=0N-1logPrlvl，則它也最大化c2log P(rl | vl )+c1，因此可以使用修正的度量，且不影響 Viterbi 算法的性能。如果選擇 c1 使最小度量為 0，則 c2 可選擇為使所有度量近似為整數(shù)。這樣，由于用整數(shù)來近似表示度量，Viterbi 算法的性能變成了次最優(yōu)算法

11、，但通過選擇 c1 和 c2 可使得這種性能降低非常小。 例1：對于二輸入、4-ary 輸出的 DMC 信道下的 Viterbi 算法 二輸入、4-ary 輸出的 DMC 如圖2 所示。該信道的比特度量如圖3（a）所示（按照底為 10 的對數(shù)計算），選擇 c11，c217.3，得到整數(shù)度量表如圖3（b）所示。 0.40.40.20.30.10.30.2 0.1 0 1 01 02 11 12 圖2 二輸入、4-ary 輸出 DMC 信道模型 l rl v 01021211l r l v010212110-0.4-0.52-0.7-1.001085011.0-0.7-0.52-0.4105810

12、 (b) 圖3 度量表 假設圖1 中的一個碼字在這樣的信道中傳輸，接收到的序列為： r（，） (7)對該序列進行 Viterbi 譯碼如圖4 所示。每個狀態(tài)上的數(shù)字表示幸存路徑的度量，另一個路徑就將被刪除（綠線部分）。這樣最后的碼字（紅線部分的輸出）判決為： v=(111,010,110,011,000,000,000) （5.8）它對應的輸入序列為u=(11000)。注意：網(wǎng)格圖中最后的 m2 個分支是清空寄存器的，不能算作為輸入信息序列。圖4 DMC 信道下的 Viterbi 算法在 BSC 信道情況下，轉(zhuǎn)移概率為 p1/2，接收序列r是 2-ary 輸出的，此時對數(shù)似然函數(shù)為：log P(r | v) = d(r, v) log p/(1-p) + N log(1-p) （9）其中d(r, v) 是r和v之間的 Hamming 距離。由于log p/(1-p)0，且N log(1 - p) 對所有v來說都是一個常數(shù)，因此最大似然譯碼（ max log P(r | v) ）就是最小化 Hamming 距離（ min d(r, v) ）。 d(r