隨著差錯控制編碼理論的完善和數字電路技術的發展，信道編碼已經成功地應用于各種通信系統中。其基本做法是：在發送端將被傳輸的信息序更上附加一些監督碼元，這些多余的碼元與信息序列之間以某種確定的規則相互約束；接收端按照既定的規則檢驗信息碼元與監督碼元之間的關系，一旦傳輸過程中發生錯誤，則信息碼元與監督碼元之間的關系將受到破壞，從而發現錯誤，甚至糾正錯誤。按照信息碼元和監督碼元之間的約速方式，可以分為組碼和卷積碼。在GSM和IS-95中主要采用了卷積碼，在每三代移動通信中，話音信號也主要采了卷積編碼。卷積碼的譯碼方法有許多種，其中最重要的就是Vertibi算法。為此，本文討論用DSP實現Vertibi譯碼器的方法。

1 卷積編碼器簡介

卷積碼是一種對付突發錯誤的有效編碼方法，通常記作（n,k,N）。它將k個信息編碼為n個比特，編碼效率為Rc=k/n。N為約束長度。與分組碼不同，卷積碼中編碼后的n個碼元不但與當前段的k個信息有關，而且與前面N-1段的信息有關，編碼過程中相互關聯的碼元為Nn個。其糾錯能力隨著N的增加而增大，而差錯率隨著N的增加而指數下降。卷積編碼器的結構如圖1所示。

由圖1可知，卷積編碼器包括兩部分：一個由N段組成的輸入移位寄存器，每段有k段，共有N·k位移位寄存器；n個模2和相加，其輸入分別對應于n個基于生成多項式的線性代數方程組。每輸入k個比特，編碼器輸出n個比特。在編碼器復雜度相同的情況下，卷積碼的性能優于分組碼。

2 Vertibi譯碼的基本原理

卷積碼的譯碼方法主要包括Vertibi算法、Fano算法和堆棧算法等等，其中最重要的和最常用的就是Vertibi算法。Vertibi算法是一種關于解卷積的最大似然譯碼法。它不是在網格上依次比較所有的可能路徑，而是接收一段，計算一段，保留最有可能的路徑，從而達到整個碼序列是一個最大似然序列。

    Vertibi算法可以算法描述如下：把在時刻i、狀態Sj所對應的網格圖節點記作（Sj，i），給每個網格圖節點賦值V（Sj，i）。節點值按照如下步驟計算：

①設V(S0,0)=0，i=1。

②在時刻i,對于進入每個節點的所有路徑計算其不完全路徑的長度。

③令V(Sj，i)為在i時刻，到達與狀態Sj相對應的節點（Sj,i）的最小不完全路徑長度，通過在前一節點隨機選擇一條路徑就可產生新的結果，非存留支路將從網格圖中刪除。以這種方式，可以從（S0,0）處產生一組最小路徑。

④用L表示輸入編碼段的數目。其中，每段為k比特，m為編碼器中最大寄存器的長度。如果i

一旦計算出所有節點值，則從i=L+m時刻，狀態S0開始，沿網格圖中的幸存路徑反向追尋即可。這樣被定義支路與解碼輸出將是一一對應的。關于不完全路徑長度，硬判斷決解碼采用漢明距離，軟判決解碼采用的是歐幾里德距離。軟判決的特性比硬判決要好2～3dB。

（n,k,N）卷積編碼器共有2 kn個狀態，因此Vertibi譯碼器必須具有同樣的2 kn個狀態，并且在譯碼過程中要存儲各狀態的幸存路徑和長度。Vertibi譯碼器的復雜程度隨2 kn指數增加。一般要求n<10。

3 Vertibi譯碼器的DSP實現

譯碼過程就是根據接收到的數據符號，按最大似然譯碼準則找出編碼器在網絡圖上所走過的路徑。Vertibi譯碼的處理過程如圖2所示。

3.1 度量值更新

度量值的更新包括以下4個步驟：

①計算每條可能輸入路徑的度量值；

②為每條支路計算總的距離；

③選擇保存最小度量值；

④保存幸存路徑。

Vertibi譯碼時，每收到一個符號就進行狀態轉移，需要計算前一個狀態到各個新狀態的分支度量值。我們用DSP設計的譯碼器采用軟判決輸入，度量值用歐氏距離表示。當編碼速率為1/C時，歐氏距離為：

其中SDn表示接收序列，Gn(j)為網格上每個路徑狀態的期望輸入值，j是路徑指示值，C為編碼速率的倒數。將（1）式展開得：

對于所有的路徑來說，都是一樣的，2只是個常數，在進行各路徑度量值比較時，可以不考慮。這樣可簡化為：

省去膠面的負號，在度量值的比較時取最大值。對于編碼速率為1/2的卷積碼，分支度量為：

T=SD0G0(j)+SD1G1(j)    (4)

當編碼速率為1/3時，分支度量為：

T=SD0G0（j）+SD1G1(j)+SD2G2(j)    （5）

Gn(j)用雙極性表示，即0用+1表示，1用-1表示。這樣分支度量值的計算可以進一步簡化為接收數據的加和減。

下面給出編碼速率為1/3時，DSP實現具體程序。

LD *AR1+，16，A ；A=SD(2*i)

ADD*AR1+,16,B,B ;B=SD（2*i）+SD（2*i+1）

ADD*AR1-，16，B，B ;B=SD(2*i)+SD(2*i+)+SD(2*i+2)

STH B,*AR2+ ;temp(0)=SD(2*i)+SD(2*i+2)

SUB*AR1+,16,A,B ;B=SD(2*i)-SD(2*i+)

ADD *AR1-,16,B,B ;B=SD(2*i)-SD(2*i+1)+SD(2*i+2)

STHB,*AR2+ ;temp(1)=SD(2*i)-SD(2*i+1)+SD（2*i+2）

SUB *AR1+，16，A，B ；B=SD(2*i)-SD(2*i+1)

SUB *AR1-,16,B,B ;B=SD(2*i)-SD(2*i+1)-SD(2*i+)

STH B,*AR2+ ;temp(2)=SD(2*i)-SD(2*i+1)-SD(2*i+2)

ADD *AR1+,16,A,B ;B=SD(2*i)+SD(2*i+1)

SUB *AR1+,16,B,B ;B=SD(2*i)+SD(2*i+1)-SD(2*i+2)

STH B,*AR2 ;temp(3)=SD(2*i)+SD(2*i+1)-SD(2*i+2)

加比選單元是Vertibi譯碼器的核心單元。它的主要功能是取出當前狀態的量度值，分別與其兩個后續支路的量度相加并比較，選擇羅小的一個作為后續狀態的量度，并保存幸存支路。圖3給出了該算法的示意圖。

C54X片內的比較、選擇和存儲單元（CSSU）就是專門為Viterbi算法設計的加法/比較/選擇（ACS）運算的硬件單元。圖3所示的運算包括加法、比較和選擇三部分操作。其加法運算由DSP的ALU完成。只要將狀態寄存器ST1中的C16位置成1，ALU就被配置成雙16位工作方式，這樣，就可以在一個機器周期內執行兩次加法運算。其結果（Old_Met1+D1和Old_Met2+D2）都是16位數，分別存放在累加器的高16位和低16位中。然后，利用CMPS指令對累加器的高16位和低16位進行比較，并選擇出較大的一個數放到指令所指定的存儲單元中。在CMPS指令執行的過程中，狀態轉移寄存器TRN自動記錄比較的結果，這一點非常有用。實現一個蝶式運算的程序如下：

LD *AR2，T ；T=本地距離

DADST *AR5，A ；A=Old_Met(2*j)+T//Old_Met(2*j+1)-T

CMPS A,*AR4+ ;New_Met(j)=(Max(Old_Met(2*j)+T,Old_Met(2*j+1)-T)

；TRN=RTN<<1

;若（Old_Met(2*j)+T=

TRN[0]=1

CMPS B，*AR3+ ;New_Met(j+2 K-2)=(Max(Old_Met(2*j)-T,Old_Met(2*j+1)+T)

TRN=TRN<<1

；若（Old_Met(2*j)-T=

3.2 回溯

當接收完1幀數據后，添加尾比特，強迫網格圖的最后一個狀態（0狀態）開始，反向追蹤最大似然路徑，完成原始數據的譯碼。回溯的計算過程如下：

①計算當前狀態在轉移數據塊中的數據；

②利用BITT指令從T寄存器中讀取當前狀態相應的轉稱比特；

③用上面讀取的轉移比特更新狀態。

溯的主要功能是，從每個符號間隔的轉移數據中提取正確的位。為了完成該功能，需要保存每個狀態相應的轉移比特。該比特表示選定碟形網絡的是上面分支還是下面分支，所有這些轉移比特構成一塊轉移字。表1給出轉移字塊中狀態數與相應轉移比特之間的關系。

表1 一個符號間隔內數據轉移的狀態順序

實現回溯的程序如下：

；以下程序中，累加器A存放狀態值，累加器B存放臨時的數據

；K為約束長度，MASK=2 K-5-1，ONE=1

RSBX OVM ；關閉溢出模式

STM *NTRAN_END，AR2；轉移表的結束地址

STM#NBWORDS-1，AR1；要計算的輸出字的序號

MVMM AR1，AR4 ；復制AR1的數值到AR4中

STM #OUTPUT+NBWORDS-1，AR3

；輸出比特的地址指針

LD #0，A 初始0狀態存入累加器A中

STM#15，BRC ；do i=0,NBWORDS-1

BACK：RPTB TBEND-1 ；do j=0,15

；在轉移字中計算比特位置

SFTL A，-（K-2），B ；B=A>>(K-2)

AND ONE，B ；B=B&1=msb of State

ADD A,1,B ;B=B+A<<1=2*State+msb of State

STLM B,T ;T=B(bit position)

；修正轉移字

SFTL A，-3，B ；B=A/8=State/8

AND MASK，B ；B=B&MASK=(K-5)lsb'sof State/8

STLM AR0 ;AR0=轉稱字索引

MAR *+AR2（-2K-5） ；修正寄存器值使其復位

MAR *AR2+0 ；加偏移量修正轉移字

BITT*AR2-0 ；測試轉移字中的比特位

ROLTC A

TBEND：STL A，*AR3-

BANZD：BACK，*AR1-

STM #15，BRC ；指向輸出緩沖區的首地址

LD*AR3，A ；將第一個字裝入累加器A中

RVS：SFTA A，-1，A

STM #15，BRC

RPTB RVS2-1

ROL B

SFTA A，-1，A

RVS2：BANZD RVS，*AR4- ；判斷所有的字是否都計算完

STL B，*AR3+ ；保存剛計算完的字

LD *AR3，A ；裝入下一個字