用TMS320C54X實(shí)現(xiàn)Vertibi譯碼器
關(guān)鍵詞：Vertibi譯碼 TMS320C54X DSP 度量值 回溯 卷積編碼
引言
隨著差錯控制編碼理論的完善和數(shù)字電路技術(shù)的發(fā)展，信道編碼已經(jīng)成功地應(yīng)用于各種通信系統(tǒng)中。其基本做法是：在發(fā)送端將被傳輸?shù)男畔⑿蚋细郊右恍┍O(jiān)督碼元，這些多余的碼元與信息序列之間以某種確定的規(guī)則相互約束；接收端按照既定的規(guī)則檢驗(yàn)信息碼元與監(jiān)督碼元之間的關(guān)系，一旦傳輸過程中發(fā)生錯誤，則信息碼元與監(jiān)督碼元之間的關(guān)系將受到破壞，從而發(fā)現(xiàn)錯誤，甚至糾正錯誤。按照信息碼元和監(jiān)督碼元之間的約速方式，可以分為組碼和卷積碼。在GSM和IS-95中主要采用了卷積碼，在每三代移動通信中，話音信號也主要采了卷積編碼。卷積碼的譯碼方法有許多種，其中最重要的就是Vertibi算法。為此，本文討論用DSP實(shí)現(xiàn)Vertibi譯碼器的方法。
1 卷積編碼器簡介
卷積碼是一種對付突發(fā)錯誤的有效編碼方法，通常記作（n,k,N）。它將k個(gè)信息編碼為n個(gè)比特，編碼效率為Rc=k/n。N為約束長度。與分組碼不同，卷積碼中編碼后的n個(gè)碼元不但與當(dāng)前段的k個(gè)信息有關(guān)，而且與前面N-1段的信息有關(guān)，編碼過程中相互關(guān)聯(lián)的碼元為Nn個(gè)。其糾錯能力隨著N的增加而增大，而差錯率隨著N的增加而指數(shù)下降。卷積編碼器的結(jié)構(gòu)如圖1所示。
由圖1可知，卷積編碼器包括兩部分：一個(gè)由N段組成的輸入移位寄存器，每段有k段，共有N·k位移位寄存器；n個(gè)模2和相加，其輸入分別對應(yīng)于n個(gè)基于生成多項(xiàng)式的線性代數(shù)方程組。每輸入k個(gè)比特，編碼器輸出n個(gè)比特。在編碼器復(fù)雜度相同的情況下，卷積碼的性能優(yōu)于分組碼。
2 Vertibi譯碼的基本原理
卷積碼的譯碼方法主要包括Vertibi算法、Fano算法和堆棧算法等等，其中最重要的和最常用的就是Vertibi算法。Vertibi算法是一種關(guān)于解卷積的最大似然譯碼法。它不是在網(wǎng)格上依次比較所有的可能路徑，而是接收一段，計(jì)算一段，保留最有可能的路徑，從而達(dá)到整個(gè)碼序列是一個(gè)最大似然序列。
Vertibi算法可以算法描述如下：把在時(shí)刻i、狀態(tài)Sj所對應(yīng)的網(wǎng)格圖節(jié)點(diǎn)記作（Sj，i），給每個(gè)網(wǎng)格圖節(jié)點(diǎn)賦值V（Sj，i）。節(jié)點(diǎn)值按照如下步驟計(jì)算：
①設(shè)V(S0,0)=0，i=1。
②在時(shí)刻i,對于進(jìn)入每個(gè)節(jié)點(diǎn)的所有路徑計(jì)算其不完全路徑的長度。
③令V(Sj，i)為在i時(shí)刻，到達(dá)與狀態(tài)Sj相對應(yīng)的節(jié)點(diǎn)（Sj,i）的最小不完全路徑長度，通過在前一節(jié)點(diǎn)隨機(jī)選擇一條路徑就可產(chǎn)生新的結(jié)果，非存留支路將從網(wǎng)格圖中刪除。以這種方式，可以從（S0,0）處產(chǎn)生一組最小路徑。
④用L表示輸入編碼段的數(shù)目。其中，每段為k比特，m為編碼器中最大寄存器的長度。如果i<L+m，則令i=i+1，返回第②步。
一旦計(jì)算出所有節(jié)點(diǎn)值，則從i=L+m時(shí)刻，狀態(tài)S0開始，沿網(wǎng)格圖中的幸存路徑反向追尋即可。這樣被定義支路與解碼輸出將是一一對應(yīng)的。關(guān)于不完全路徑長度，硬判斷決解碼采用漢明距離，軟判決解碼采用的是歐幾里德距離。軟判決的特性比硬判決要好2～3dB。
（n,k,N）卷積編碼器共有2 kn個(gè)狀態(tài)，因此Vertibi譯碼器必須具有同樣的2 kn個(gè)狀態(tài)，并且在譯碼過程中要存儲各狀態(tài)的幸存路徑和長度。Vertibi譯碼器的復(fù)雜程度隨2 kn指數(shù)增加。一般要求n<10。
3 Vertibi譯碼器的DSP實(shí)現(xiàn)
譯碼過程就是根據(jù)接收到的數(shù)據(jù)符號，按最大似然譯碼準(zhǔn)則找出編碼器在網(wǎng)絡(luò)圖上所走過的路徑。Vertibi譯碼的處理過程如圖2所示。
3.1 度量值更新
度量值的更新包括以下4個(gè)步驟：
①計(jì)算每條可能輸入路徑的度量值；
②為每條支路計(jì)算總的距離；
③選擇保存最小度量值；
④保存幸存路徑。
Vertibi譯碼時(shí)，每收到一個(gè)符號就進(jìn)行狀態(tài)轉(zhuǎn)移，需要計(jì)算前一個(gè)狀態(tài)到各個(gè)新狀態(tài)的分支度量值。我們用DSP設(shè)計(jì)的譯碼器采用軟判決輸入，度量值用歐氏距離表示。當(dāng)編碼速率為1/C時(shí)，歐氏距離為：
其中SDn表示接收序列，Gn(j)為網(wǎng)格上每個(gè)路徑狀態(tài)的期望輸入值，j是路徑指示值，C為編碼速率的倒數(shù)。將（1）式展開得：
對于所有的路徑來說，
都是一樣的，2只是個(gè)常數(shù)，在進(jìn)行各路徑度量值比較時(shí)，可以不考慮。這樣可簡化為：
省去膠面的負(fù)號，在度量值的比較時(shí)取最大值。對于編碼速率為1/2的卷積碼，分支度量為：
T=SD0G0(j)+SD1G1(j) (4)
當(dāng)編碼速率為1/3時(shí)，分支度量為：
T=SD0G0（j）+SD1G1(j)+SD2G2(j) （5）
Gn(j)用雙極性表示，即0用+1表示，1用-1表示。這樣分支度量值的計(jì)算可以進(jìn)一步簡化為接收數(shù)據(jù)的加和減。
下面給出編碼速率為1/3時(shí)，DSP實(shí)現(xiàn)具體程序。
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譯碼器的核心單元。它的主要功能是取出當(dāng)前狀態(tài)的量度值，分別與其兩個(gè)后續(xù)支路的量度相加并比較，選擇羅小的一個(gè)作為后續(xù)狀態(tài)的量度，并保存幸存支路。圖3給出了該算法的示意圖。
C54X片內(nèi)的比較、選擇和存儲單元（CSSU）就是專門為Viterbi算法設(shè)計(jì)的加法/比較/選擇（ACS）運(yùn)算的硬件單元。圖3所示的運(yùn)算包括加法、比較和選擇三部分操作。其加法運(yùn)算由DSP的ALU完成。只要將狀態(tài)寄存器ST1中的C16位置成1，ALU就被配置成雙16位工作方式，這樣，就可以在一個(gè)機(jī)器周期內(nèi)執(zhí)行兩次加法運(yùn)算。其結(jié)果（Old_Met1+D1和Old_Met2+D2）都是16位數(shù)，分別存放在累加器的高16位和低16位中。然后，利用CMPS指令對累加器的高16位和低16位進(jìn)行比較，并選擇出較大的一個(gè)數(shù)放到指令所指定的存儲單元中。在CMPS指令執(zhí)行的過程中，狀態(tài)轉(zhuǎn)移寄存器TRN自動記錄比較的結(jié)果，這一點(diǎn)非常有用。實(shí)現(xiàn)一個(gè)蝶式運(yùn)算的程序如下：
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=<Old_Met(2*j+1)-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=<Old_Met(2*j+1)+T）則TRN[0]=1
3.2 回溯
當(dāng)接收完1幀數(shù)據(jù)后，添加尾比特，強(qiáng)迫網(wǎng)格圖的最后一個(gè)狀態(tài)（0狀態(tài)）開始，反向追蹤最大似然路徑，完成原始數(shù)據(jù)的譯碼?；厮莸挠?jì)算過程如下：
①計(jì)算當(dāng)前狀態(tài)在轉(zhuǎn)移數(shù)據(jù)塊中的數(shù)據(jù)；
②利用BITT指令從T寄存器中讀取當(dāng)前狀態(tài)相應(yīng)的轉(zhuǎn)稱比特；
③用上面讀取的轉(zhuǎn)移比特更新狀態(tài)。
溯的主要功能是，從每個(gè)符號間隔的轉(zhuǎn)移數(shù)據(jù)中提取正確的位。為了完成該功能，需要保存每個(gè)狀態(tài)相應(yīng)的轉(zhuǎn)移比特。該比特表示選定碟形網(wǎng)絡(luò)的是上面分支還是下面分支，所有這些轉(zhuǎn)移比特構(gòu)成一塊轉(zhuǎn)移字。表1給出轉(zhuǎn)移字塊中狀態(tài)數(shù)與相應(yīng)轉(zhuǎn)移比特之間的關(guān)系。
表1 一個(gè)符號間隔內(nèi)數(shù)據(jù)轉(zhuǎn)移的狀態(tài)順序
| 狀態(tài)字中的比特序號 | |||||||||
| 15 | 14 | 13 | 12 | … | 2 | 1 | 0 | ||
| 轉(zhuǎn)移字序號 | 0 | 0 | 2K-2 | 1 | 2K-2 +1 | … | 2K-2 +6 | 7 | 2K-2 +7 |
| 1 | 8 | 2K-2 +8 | 9 | 2K-2 +9 | … | 2K-2+E | F | 2K-2 +F | |
| 2 | 10 | 2K-2+10 | 11 | 2K-2 +11 | … | 2K-2 +16 | 17 | 2K-2 +17 | |
| … | … | … | … | … | … | … | … | … | |
| 2K-5 -1 | 2K-2 -8 | 2K-1 -8 | 2K-2 -7 | 2K-2 -7 | … | 2K-1 -2 | 2K-2 -1 | 2K-1 -1 | |
實(shí)現(xiàn)回溯的程序如下：
；以下程序中，累加器A存放狀態(tài)值，累加器B存放臨時(shí)的數(shù)據(jù)
；K為約束長度，MASK=2 K-5-1，ONE=1
RSBX OVM ；關(guān)閉溢出模式
STM *NTRAN_END，AR2；轉(zhuǎn)移表的結(jié)束地址
STM#NBWORDS-1，AR1；要計(jì)算的輸出字的序號
MVMM AR1，AR4 ；復(fù)制AR1的數(shù)值到AR4中
STM #OUTPUT+NBWORDS-1，AR3
；輸出比特的地址指針
LD #0，A 初始0狀態(tài)存入累加器A中
STM#15，BRC ；do i=0,NBWORDS-1
BACK：RPTB TBEND-1 ；do j=0,15
；在轉(zhuǎn)移字中計(jì)算比特位置
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)
；修正轉(zhuǎn)移字
SFTL A，-3，B ；B=A/8=State/8
AND MASK，B ；B=B&MASK=(K-5)lsb'sof State/8
STLM AR0 ;AR0=轉(zhuǎn)稱字索引
MAR *+AR2（-2K-5） ；修正寄存器值使其復(fù)位
MAR *AR2+0 ；加偏移量修正轉(zhuǎn)移字
BITT*AR2-0 ；測試轉(zhuǎn)移字中的比特位
ROLTC A
TBEND：STL A，*AR3-
BANZD：BACK，*AR1-
STM #15，BRC ；指向輸出緩沖區(qū)的首地址
LD*AR3，A ；將第一個(gè)字裝入累加器A中
RVS：SFTA A，-1，A
STM #15，BRC
RPTB RVS2-1
ROL B
SFTA A，-1，A
RVS2：BANZD RVS，*AR4- ；判斷所有的字是否都計(jì)算完
STL B，*AR3+ ；保存剛計(jì)算完的字
LD *AR3，A ；裝入下一個(gè)字
下載文檔
