【正文】 我們已經(jīng)知道最末端的狀態(tài)為0，我們可以知道分支輸入值，從tab_trn的最后一個單元的第0字第0位，由回溯蝶形結(jié)構(gòu)我們可以知道初始狀態(tài)。0(trn)1(trn)1(trn)0(trn)j/2j/2+1jj+1圖510 回溯蝶形結(jié)構(gòu)其中0≤j＜255，其j為偶數(shù)。那么我們?nèi)绻拦?jié)點位于哪一級哪一狀態(tài)，我們就可以知道該節(jié)點的路徑選擇情況。否則*AR4存入的是A(150)，同時TRN左移一位將1存入TRN的第0位。例: CMPS A,*AR4+ 說明：比較A累加器的低16位和高16位，把較大值放在*AR4中。為“1”則表示選擇兩條路徑中下面的一條。tab_trn存儲了輸入序列后面的88級的路徑選擇情況，所以需要88*16=1408字的空間。tab_trn中1個字16bit，用了16個字表示256個狀態(tài)，即一級的狀態(tài)。bef表示的是接收192bit輸入序列得到的最終的分支度量值，tab_trn表示的是968=88級的路徑選擇情況。圖57存儲所選路徑的兩個基本類型狀態(tài)i狀態(tài)i+128狀態(tài)2i狀態(tài)i狀態(tài)i+128狀態(tài)2i+10101初始化i空間置0，i4置8,ar5=87Tbefbef[2] ar7=127由i0更新iii3 bfly_a bfly_b ar1=0？ ar5=0？回溯圖58 將上面的路徑記為0，下面的路徑記為1,如圖57所示。這里有點可以改進(jìn)的地方，aft到bef空間的復(fù)制不是必須的，完成一次bef到aft更新分支度量值后，可以調(diào)整ar3與ar4指向，忽略aft到bef的復(fù)制，節(jié)省一定的時間，完成一次bef到aft更新分支度量值如此循環(huán)。*ar4指向aft空間，它用于存放碟算后的分支度量值。當(dāng)i[2]=0時，選擇宏bfly_a；當(dāng)i[2]=1時，選擇宏bfly_b。bfly_a .macro ssbx c16 dadst *ar3,a ；分支輸入為0時，狀態(tài)i+T，狀態(tài)i+128T dsadt *ar3,b ；分支輸入為1時，狀態(tài)iT，狀態(tài)i+128+T cmps a,*ar4+ ；比較選擇存儲到達(dá)狀態(tài)2i的路徑 cmps b,*ar4+ ；比較選擇存儲到達(dá)狀態(tài)2i+1的路徑 rsbx c16 .endm bfly_b .macro ssbx c16 dsadt *ar3,a ；分支輸入為0時，狀態(tài)iT，狀態(tài)i+128+T dadst *ar3,b ；分支輸入為1時，狀態(tài)i+T，狀態(tài)i+128T cmps a,*ar4+ ；比較選擇存儲到達(dá)狀態(tài)2i的路徑 cmps b,*ar4+ ；比較選擇存儲到達(dá)狀態(tài)2i+1的路徑 rsbx c16 .endm上述宏bfly_a描述的就是圖56 碟型運算的基本形式2，宏bfly_b描述的是圖55 碟型運算的基本形式1。 圖56 碟型運算的基本形式2狀態(tài)i狀態(tài)2i狀態(tài)2j+1+TT狀態(tài)i+128T+T，這是專門為Viterbi算法設(shè)計的加法比較選擇操作的硬件單元。狀態(tài)i狀態(tài)2i狀態(tài)2i+1+TT狀態(tài)i+128+TT圖55 碟型運算的基本形式1在圖45（2,1,9）卷積碼的蝶形結(jié)構(gòu)中我們提到這圖有助于我們理解Viterbi譯碼。上述譯碼過程的基本操作就是“加—比—選”，每級求出對歐氏距離累計值，然后倆倆比較，并做出選擇。經(jīng)挑選后第9級只留下256條幸存路徑，選出的路徑連同它們的歐氏距離累加值一起存儲起來。 加比選當(dāng)接收到第9條支路時，每條路徑都有2條支路延伸到第9級上，而第9級上的倆條支路又都匯聚到節(jié)點上面。開始i空間置0i0==i5 j=i5 T由i0更新iii3 dadst dsadt(j)≥0？i4++ ,i5=2*i5+1加比選圖53 初始化流程圖 初始化流程圖是否否i4=8?是 初始化程序仿真圖54 初始化程序仿真通過初始化模塊的運行，我們可以得到第8級的分支度量值。狀態(tài)i狀態(tài)2i狀態(tài)2i+1+TT狀態(tài)j狀態(tài)2i狀態(tài)2i+1+TT圖52 狀態(tài)展開兩種基本模塊本地狀態(tài)度量值先加后減DSP指令dadst或先減后加DSP指令dsadt一個值得到新狀態(tài)度量值，i是初始狀態(tài)，而2i或2i+1則是初始狀態(tài)接受分支輸入0或1的到達(dá)狀態(tài)，其中T值是由輸入序列值tab_in決定的歐氏距離值TO或T1。我們可以把它分成八級，逐行展開即按初始狀態(tài)展開再逐級展開。 初始化前面提到當(dāng)從全0狀態(tài)開始討論時由于網(wǎng)格圖的前8條連續(xù)支路構(gòu)成的路徑互不相交，在第8級時最初的256條各不相同的路徑分別到達(dá)256個狀態(tài)。數(shù)組aft記錄碟算后256個節(jié)點的度量值。數(shù)組bef_2存放長數(shù)據(jù)數(shù)，便于用于DSP的特殊指令dadst、dsadt。i[5]表示初始化時，i[4]級最多的初始狀態(tài)最大值。數(shù)組i有6個元素，i[0]表示初始狀態(tài)，i[1]表示結(jié)合初始狀態(tài)i[0]和輸入序列tab_in查圖47 tab_state獲得的分支輸出值，i[2]、i[3]表示結(jié)合分支輸出值i[1]和輸入序列tab_in查圖52 tab_in_fcANDt獲得的分支度量正負(fù)和分支度量T。8~95 88*256/16數(shù)組output存儲輸出序列。t0 t1 .bss i,6 。取分支度量正負(fù)、分支度量T，我們可以在DSP中這樣定義。通過上述公式（54），可以很容易地得到分支輸出值與T之間的關(guān)系，如下表52所示表52 tab_in_fcANDt分支輸出值分支度量值分支度量正負(fù)分支度量T00+T00001+T10110T11111T010 其中“+”用0表示，“”用1表示；T0用0表示，T1用1表示。表51 tab_in_tTab_inT0T10020010210021120在DSP中，我們可以這樣定義。本文采用T0、T1寄存器表示，其中T0=+sd0+sd1,T1=+sd0sd1。所有我們可以有個簡化的公式T=sdnGn （53）再去掉表達(dá)式的負(fù)號，可以知道在分支度量比較時應(yīng)該取大值，這是與硬判決不同的一個地方。將上述展開得T=sdnsdn2sdnGnJ+GnJGnJ （52）其中所有的分支的sdnsdn 和 Gn(J)Gn(J) 都是相等的。本文采用的是軟判決，這需要歐氏距離表示。 開始初始化加比選回溯結(jié)束圖51 Viterbi譯碼算法流程圖Viterbi譯碼要求計算前一個狀態(tài)bef到后一個狀態(tài)aft的分支度量值。 Viterbi譯碼算法Viterbi譯碼算法就是根據(jù)接收到的數(shù)據(jù)信息，按最大似然譯碼準(zhǔn)則找出編碼器在狀態(tài)轉(zhuǎn)移圖上所走過的路徑。這就是譯碼所得的路徑。在結(jié)束信息到來的時候，由于每一狀態(tài)中只有已知發(fā)送信息相符的那條支路被延伸，因而在每級比較后，幸存路徑減少一半。這一過程被稱為“加—比—選”，也稱為“碟型”運算，是Viterbi算法的基本操作。同時，保存具有較小累積度量的路徑稱之為“幸存”路徑，而丟棄其他的路徑。這一過程被稱為“初始化”。k=1，從全0狀態(tài)開始討論。由于信息序列和碼序列有一一對應(yīng)的關(guān)系，任何信息序列和碼序列都將與網(wǎng)格圖中的唯一一條路徑相聯(lián)系，而譯碼的工作，主要就是尋找網(wǎng)格圖中的這一最大似然路徑。在編碼器的基礎(chǔ)上，我們又用DSP獲得了（2,1,9）卷積碼的狀態(tài)轉(zhuǎn)移表，得到了tab_state，這有助于我們Viterbi譯碼程序。Viterbi譯碼程序中的tab_state空間如程序段 tab_state所示tab_state: .word 0, 2, 3, 1, 3, 1, 0, 2, 1, 3, 2, 0, 2, 0, 1, 3, 2, 0, 1.word 3, 1, 3, 2, 0, 3, 1, 0, 2, 0, 2, 3, 1, 0, 2, 3, 1, 3, 1.word 0, 2, 1, 3, 2, 0, 2, 0, 1, 3, 2, 0, 1, 3, 1, 3, 2, 0, 3.word 1, 0, 2, 0, 2, 3, 1, 2, 0, 1, 3, 1, 3, 2, 0, 3, 1, 0, 2.word 0, 2, 3, 1, 0, 2, 3, 1, 3, 1, 0, 2, 1, 3, 2, 0, 2, 0, 1.word 3, 2, 0, 1, 3, 1, 3, 2, 0, 3, 1, 0, 2, 0, 2, 3, 1, 0, 2.word 3, 1, 3, 1, 0, 2, 1, 3, 2, 0, 2, 0, 1, 3 本章小結(jié)在第三章卷積碼的原理概念指導(dǎo)下，本章完成了用DSP實現(xiàn)（2,1,9）卷積碼的編碼器。那么當(dāng)我們知道初始狀態(tài)i和分支輸出a時，我們就可以知道了分支輸入為0或1時，初始狀態(tài)為i、i+128的分支輸出和到達(dá)狀態(tài)。a與b呈按位相異關(guān)系。a、b表示分支輸出。tttt2i2i+1ii+2圖45 （2,1,9）卷積碼的蝶形結(jié)構(gòu)其中i、i+128表示初始狀態(tài)，2i、2i+1表示到達(dá)狀態(tài)，其中0≤i≤127 (i為整數(shù))。即輸出序列為1110 0010 。例：在（2,1,9）卷積編碼器中，若初始狀態(tài)為0000 0000，用十進(jìn)制表示即為0，輸入序列為1011，求輸出序列和狀態(tài)變化情況。其中分支輸入表示輸入碼，分支輸出表示分支輸入碼在初始狀態(tài)下通過（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è)計算法（2,1,9）卷積碼，有28個狀態(tài)，即從0000 0000到 1111 1111。而本文所討論的Viterbi譯碼的關(guān)鍵算法查表法就是依賴狀態(tài)轉(zhuǎn)換表來提高程序效率。a1放c0 (2,1,9)的程序仿真圖42是用CCS卷積碼編碼器的96bit的輸入信息，w空間的數(shù)據(jù)圖42 編碼輸入經(jīng)過程序正確運行后，我們可以得到192bit的輸出數(shù)據(jù)即wa空間的數(shù)據(jù)圖43 編碼輸出Wa空間的數(shù)據(jù)就是w空間的數(shù)據(jù)經(jīng)過（2,1,9）卷積后得到的卷積碼。a==b0xorb1xorb2xorb3xorb5xorb7 xor b,8,a 。a==b0xorb1xorb2xorb3 xor b,5,a 。a==b0xorb1 xor b,2,a 。 ld *ar2,a 。其中卷積碼編碼程序的重點就是理解A累加器與B累加器的特點位的異或操作。分步的值分別放在A累加器的第1位和第0位，即A累加器的第1位放c0,第0位放c1,再將A累加器的值存入wa空間。 (2,1,9)卷積碼編碼流程圖開始B累加器低9位清0后，最低位取輸入信息wA取輸入信息wA累加器與B累加器的特定位異或產(chǎn)生c0 c1 ，存入wa空間B累加器左移1位，最低位取輸入信息w96次？結(jié)束是否圖41 編碼流程圖 (2,1,9)卷積編碼程序?qū)崿F(xiàn)把B累加器的低9位當(dāng)做狀態(tài)移存器，左移一位是輸入信息從最低位即第0位進(jìn)入，第8位狀態(tài)舍去。所以要在數(shù)據(jù)區(qū)開一個96字的空間w用來接受輸入數(shù)據(jù)序列，并要開一個192字的空間wa來存儲輸出。然后，再將c0和c1合一個兩位數(shù)c0 c1，即所要求的輸出。即先將移存器所存儲的狀態(tài)字左移一位，將輸入的0或1放在最低位，然后再計算輸出c0 c1。常常用延遲算子多項式來描述卷積碼。編碼過程中用到的輸入位數(shù)稱為約束長度，它的值等于延遲單元的數(shù)目加上1。信息位輸入到移位寄存器中，經(jīng)過抽頭的提取，采用模2和的方式產(chǎn)生輸出。最后以（2,1,3）卷積碼譯碼為例，詳細(xì)討論了Viterbi譯碼算法中的各個步驟。其中網(wǎng)格圖對本文的Viterbi譯碼起到促進(jìn)我們理解的作用。 本章小結(jié)本章簡要介紹了卷積碼的概念、表示方法和譯碼。Viterbi在衛(wèi)星和深空通信中有廣泛的應(yīng)用。例如，在圖38中幸存路徑為a→b→d→c→b。 圖36 對應(yīng)信息位“1101”的幸存路徑網(wǎng)格圖狀態(tài)a（00）狀態(tài)b（01)狀態(tài)d（11）狀態(tài)c（10）100101000011010110111由卷積碼編碼的網(wǎng)格圖36可知，當(dāng)?shù)玫綖橐粭l譯碼路徑后，前一級輸入信息位就是下一級4個狀態(tài)a（00）,b（01）,c（10）,d（11）的最后一位。若把這三個“0”仍然看作是信息位，則可以按照上面的算法繼續(xù)解碼。圖中粗線路徑時漢明距離最小（等于1）的路徑。它和發(fā)送序列相同，故對應(yīng)發(fā)送信息位1101。計算結(jié)果列于圖37中。表31 維特比算法解碼第一步運算結(jié)