基于TMS320C54X的RS+變織+卷積的級聯(lián)糾錯碼

摘要：糾錯編碼被廣泛應用在各種數(shù)字通訊、數(shù)字廣播和數(shù)據(jù)存儲系統(tǒng)中。隨著單片機、DSP和FPGA等器件的發(fā)展，越來越容易在各種通用硬件平臺上實現(xiàn)糾錯編碼。本文基于TI的54系列DSP，實現(xiàn)由常用RS碼、卷積編碼、Viterbi解碼、交織技術構成的級聯(lián)碼，并提供編碼原理和實現(xiàn)方案。

關鍵詞：RS碼 Viterbi解碼 級聯(lián)糾錯碼

隨著越來越多的系統(tǒng)采用數(shù)字技術來實現(xiàn)，糾錯編碼技術也得到了越來越廣泛的應用。如GSM標準中，對語音的信道編碼采用卷積糾錯、分組碼檢錯。美國的蜂窩數(shù)字分組數(shù)據(jù)系統(tǒng)（CDPD）中采用了m=6的（63，47）RS(Reed Solomon)碼。CDMA標準中，主要包括卷積編碼（Turbo碼等）、交織編碼、幀循環(huán)校驗等。DVD采用RS糾錯編碼。近些年來，隨著軟件無線電技術的發(fā)展，糾錯編碼一般都在通用的硬件平臺上實現(xiàn)，這樣有利于保證靈活性和通用性。通常采用基于FPGA的VHDL編碼硬件實現(xiàn)，或者在DSP、單片機上用C和匯編編程軟件實現(xiàn)。本文基于TMS320C54X的DSP，實現(xiàn)一種RS+交織+卷積的級聯(lián)糾錯碼。

1 級聯(lián)糾錯編碼原理

糾錯編碼技術是通過引入可控制的冗余來提高系統(tǒng)的可靠性。它的理論基石是1948年Shannon在《通信的數(shù)字理論》中提出的著名的有擾信道編碼定理。糾錯碼按照不同的分類標準，有著不同的分類。我們常用的是按照對信息元處理的不同方法來分類的，分為分組碼和卷積碼。分組碼是把信源輸出的信息序列，以k個碼元劃分為一段，通過編碼器把這段的k個信息元，按一定規(guī)則產(chǎn)生r個校驗（監(jiān)督）元，輸出長為n=k+r的一個碼組。比較常用的有BCH碼、RS碼、Hamming碼等。卷積碼是把輸出信源輸出的信息序列，以k0個（k0通常小于k）碼元分為段，通過編碼器輸出長為n0(≥通常小于k)碼元分為一段，通過編碼器輸出長為n0(≥通常小于k)碼元分為一段，通過編碼器輸出為n0(≥k0)的一的碼以。但是該碼段的n0-k0個校驗元不僅與本組的信息有關，而且也與其前m段信息元有關，稱m為編碼存儲。因此卷積碼用（n0，k0,k）表示。

由信道編碼理論可知，隨著碼長n的增加，解碼錯誤概率以指數(shù)方式趨近于零。因此，為提高糾錯碼的有效性，就必須使用長碼。但碼長增加，碼率會相應下降，解碼設備的復雜性與計算量也相應增加，級聯(lián)碼有針對性的解決這了一矛盾。它將編碼過程分為前后串行的幾級完成，可以滿足信道糾錯對編碼長度的要求，得到與長碼相同的糾錯能力和高編碼增益；而且增加的編/解碼復雜度不是很大。其原理示意框圖如圖1所示。

級聯(lián)碼有內(nèi)碼和外碼兩級，內(nèi)碼是GF（2）上的一個[n,k]碼，外碼是GF（2k）上的[N,K]壽終正寢，編碼規(guī)則如下。

①先將kk個二進制信息元劃分成K段，每段有k個信息元。

②每段的k個信息元可看成是GF（2k）上的一個符號。將K個符號按外碼的編碼規(guī)則編成一個外碼，碼長為N，有K個信息符號，N-K個校驗符號，最小碼距為do，碼率Ro=K/N。

③外碼的每一個符號，看成是k個二進制碼元的碼組，輸入內(nèi)碼編碼器，得到一個內(nèi)存，碼長n，有n-k個校驗元，最小碼距為di，碼率Ri=k/n，由此得到N個[n,k]內(nèi)碼的碼字序徇。兩級編碼總共得到Nn個二進制碼元，Kk個信息元，組成[Kn，Kk，dodi]級聯(lián)碼的碼。

我們選用的外碼為RS（31，15）碼，生成多項式為G（X）=1+x2+x3，內(nèi)碼用卷積碼（2，1，7），其生成多項式G0=171，G1=131（都是八進制）。RS碼是GF（q）(q!=2)上，碼長N=q-1的本原BCH碼，具有很強的糾錯能力，其最大可能的最小距離是校驗元的個數(shù)加1，因而RS碼是一種極大最小距離可分碼（MDS），是一種最佳的線性循環(huán)碼。本例中使用的RS（31，15）碼的漢明距為17，可以糾8個錯誤。交織技術是抗突發(fā)干擾的重要手段，它是采用一個交織矩陣，存儲方向與發(fā)送時的方向不一樣，從而將突發(fā)錯誤離散化，提高抗突發(fā)干擾的能力。本方案中RS編碼按行存儲，發(fā)送時按列，并且對每列都進行卷積編碼，可以抵抗8列長的突發(fā)干擾。卷積編碼Viterbi軟判決解碼，可以充分的利用各個碼組之間的相關性，提高很高的編碼增益。各個組成碼和級聯(lián)后的糾錯性能仿真圖如圖2所示。

2 級聯(lián)碼的DSP編程實現(xiàn)

由于RS碼和卷積碼的Viterbi解碼運算量都很大，所以需要大量的存儲空間。本方案中實現(xiàn)在100kbps的信道上，RS碼的解碼運算量為8MIPS，Viterbi解碼需要14MIPS。整個編解碼程序需要24MIPS，因而選用在TMS320C54X芯片上實現(xiàn)。使用TI公司推出有XXA進行編程開發(fā)，考慮到編程的可移植性、可讀性和效率，采用C語言與DSP匯編語言混合編程實現(xiàn)。Viterbi解碼的算法由于程序運算量很大，采用DSP匯編語言來實現(xiàn)，蓁部分結構如圖3所示。下面我們分別對整個系統(tǒng)中的關鍵部分RS碼迭代解碼和卷積碼Viterbi解碼中的編程進行闡述。

2.1 RS碼迭代解碼的實現(xiàn)

RS解碼分頻域解碼和時域解碼，比較常用的解碼方法是時域的迭代解碼。解碼的主要步驟如下：①由接收碼字r(x)求出部分伴隨式Si的值，若Si全為0，則輸出接收碼字r(x)；②由伴隨式Si求出σi(i=1,2,…K)，確定差錯多項式σ（x）；③通過搜索法得到σ（x）的根，進一步確定差錯位置βi；

④由部分伴隨式Si及其差錯位置βi求出差錯大小；⑤由差錯位置和差錯大小求出誤碼多項式e(x)，計算c(x)=r(x)-e(x)；⑥校驗是否成立，若成立，則輸出c(x)，否則輸出r(x)。

程序設計的關鍵在于域中運算的實現(xiàn)。對于中的乘法，可以采用指數(shù)形式表示元素，從而將相乘運算轉換成相加運算。對于域中的加法，我們采用矢量形式表示，從而將加法運算轉換成位異或運算。因而我們需要設計兩張查找表，當遇到加法運算時，可以很方便的將元素從指數(shù)形式轉換成矢量形式；遇到乘法時，可以將元素從矢量從指數(shù)形式轉換成矢量形式；遇到乘法時，可以將元素從矢量形式轉換成多項式形式。下面給出的是GF（2 4）域中，元素從指數(shù)形式轉換矢量形式查表Alpha_to，由矢量形式轉換成指數(shù)形式查表Index_of，其中域的生成多項式是g(x)=x5+x2+1。

Int Index_of[]={-1,31,1,18,2,5,19,11,3,29,6,27,20,8,12,23,4,10,30,17,7,22,28,26,21,25,9,16,13,14,24,15};

Int Alpha_to[]={1,2,4,8,16,5,10,20,13,26,17,7,14,28,29,31,27,19,3,6,12,24,21,15,30,25,23,11,22,9,18,1}；

由上面我們可以很方便地進行運算，例如伴隨式的計算程序如下：

for(j=0;jNN;j++)

if(recd[j]!=0) s[i]^=Alpha_to[(Index_of[j])+i*j]]+i*j)%NN]；其中recd[]存儲的是Yi的值。是域中的本原元。

2.2 卷積碼Viterbi解碼的實現(xiàn)

Viterbi解碼算法是一種最大似然算法，它不是在網(wǎng)格圖上依次比較所有可能的路徑，而是接收一段，計算、比較一段，保留最有可能的路徑，從而達到整個碼序列是一個最大似然序列。雖然如此，Viterbi解碼算法的運算量還是巨大的，而且隨著卷積碼結束長度的增大成幾何級數(shù)增長。

2.2 卷積碼Viterbi解碼的實現(xiàn)

Viterbi解碼算法是一種最大似然算法，它不是在網(wǎng)絡圖上依次比較所有可能的路徑，而是接收一段，計算，比較一段，保留最有可能的路徑，從而達到整個碼序列是一個最大似然序列。雖然如此，Viterbi解碼算法的運算量還是巨大的，而且隨著卷積碼約束長度的增大成幾何級數(shù)增長。因而如何減少運算量，盡可能的采用結束長度長的碼，成為Viterbi解碼程序設計的關鍵。54X系列DSP中的結構和指令系統(tǒng)，通過精巧的算法和編程，可以使Viterbi解碼快速實現(xiàn)。許多卷積碼網(wǎng)絡圖中存在蝶形結構，因而可以利用DSP的相加、比較和存儲單元（ACS）快速地實現(xiàn)蝶形運算。DSP的雙字節(jié)指令，可以在個周期內(nèi)進行單字節(jié)加減運算。指令系統(tǒng)包括單尋址重復和塊指令重復操作?？傊ㄟ^充分利用DSP芯片的特點進行編程，可以達到較快的速度。蝶形單元運算的宏編程如下：

BFLY_DIR .macro

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

DSADT *AR5+,B ;B=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=TRN1

;If(Old_Met(2*j)+T=Old_Met(2*j+1)

;T)Then 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=TRN1

;If(Old_Met(2*j)+T=Old_Met(2*j+1)

;T) Then TRN[0]=1

.endm

(2,1,7)的卷積碼共有64個狀態(tài)，需保留一條重量最大路徑（幸存路徑）。對每一個節(jié)點的組輸入解碼碼元（2個），需要計算碼元重量增量，通過32個蝶形運算單元來選擇更新64個狀態(tài)的存儲路徑。

由于解碼處理的一個數(shù)據(jù)流，不可能等待所有輸入完以后再解碼，因而需要回溯。實驗證明，當存儲路徑是約束長度的5倍時，每條路徑的前端節(jié)點就收斂了，因而不需要等接收完成就可以輸出。我們在編程中，采用了需要等接收完成就可以輸出。我們在編程中，采用了固定長度的Viterbi解碼算法，即一個幀長。因而在卷積碼的編程器端需要添加0，使編碼器的狀態(tài)因而在卷積碼的編碼器端需要添加0，使編碼器的狀態(tài)最后歸0。同樣，在解碼器端最后也是收斂于0狀態(tài)。

結語

本文就在TMS320C54X上實現(xiàn)RS+交織+卷積的級聯(lián)編碼技術進行了探討，給出了性能仿真和編程實現(xiàn)中的一些關鍵思想。