彭 沖，鄭建宏，吳廣富

(重慶郵電大學(xué)新一代寬帶移動通信終端系統(tǒng)研究所，重慶400065)

在信道編碼中，一個傳輸信道中的比特數(shù)在不同的傳輸時間間隔可以發(fā)生變化，而所配置的物理信道容量(或承載比特數(shù))卻是固定的。因而，當(dāng)不同的傳輸時間間隔的數(shù)據(jù)比特發(fā)生改變時，為了匹配無線物理信道和傳輸信道之間的速率差，輸入序列中的一些比特將被重發(fā)或打孔，即速率匹配，以確保在傳輸信道復(fù)用后總的比特率與所配置的物理信道承載能力一致［1－2］。從實(shí)現(xiàn)上看，重發(fā)和打孔沒太大的區(qū)別，都是進(jìn)行比特移位操作。不同的是重發(fā)是在當(dāng)前比特和后面比特之間插入一次當(dāng)前比特，同時后面的比特依次向后移位;打孔是將當(dāng)前的比特去掉，同時將后面的比特依次向前移位［3］。在解碼端，則要進(jìn)行對應(yīng)的反操作，即打掉重復(fù)的比特，或者恢復(fù)被打掉的比特。在GSM系統(tǒng)中，打孔操作采用的是查表方式進(jìn)行，即在表中存放打孔位置信息，然后依據(jù)表中的信息對輸入信息比特進(jìn)行操作［4－6］。但是由于不同信道的輸入數(shù)據(jù)格式不一樣，需要進(jìn)行打孔的方式也不同，那么就需要許多張不同的表來表示這些打孔方案。這種將每張表都依次分開列出的方法對系統(tǒng)的內(nèi)存消耗非常大。在當(dāng)今追求更小的計算復(fù)雜度和更小的內(nèi)存占用的實(shí)時系統(tǒng)中，這種將表一一分開列出搜索的算法顯然不是最優(yōu)的。在這種情況下，本文提出了一種改進(jìn)的打孔方法，在減低其計算復(fù)雜度的同時有效地減小了系統(tǒng)的內(nèi)存消耗，并基于低功耗、低成本、多媒體性能強(qiáng)大的ZSP800平臺［7］對該方法與傳統(tǒng)的方法進(jìn)行了對比驗(yàn)證。

1 傳統(tǒng)的打孔方法

在GSM系統(tǒng)中，不同信道信息的打孔位置通過計算后，以碼表的形式表現(xiàn)出來，在執(zhí)行打孔操作時，直接調(diào)用碼表中存儲的比特打孔位置對信息進(jìn)行操作［8］。

以MCS1信道為例，該信道存在2種打孔方式P1和P2，如表1所示。在打孔前的信息比特為588 bit，打孔后為372 bit，那么該信道在經(jīng)過打孔處理后一共打掉了588－372=216 bit。傳統(tǒng)的打孔表中存放的是需要打孔比特的絕對位置，并且一個位置需要用1個word表示，那么對于該信道來說則需要216×2=432 word來存放這2塊打孔碼表。

在計算出打孔碼表后，剩余的工作則是通過查表找到需打掉的比特，并將打掉后剩余的信息比特重新進(jìn)行連續(xù)排列。以MCS1信道的P1打孔方式為例，打孔表如表2所示。

表1 MCS1打孔方式P1和P2

表2 MCS1的P1打孔方式表

算法描述如下:

第一步:先找到表中第1個位置MCSI_Punc_Tab［0］，取出其中的需要打掉的第1個比特位置2，然后通過一次循環(huán)保存第0、1比特。并將指向輸入比特數(shù)據(jù)的指針加1，跳過第一個需打掉的比特。

第二步:找到表中第2個位置MCSI_Punc_Tab［1］，取出其中的需要打掉的第2個比特位置5，將該值與MCSI_Punc_Tab［0］中的值2比較，得到第2個要打孔的位置與第1個打孔位置之間需要存儲的有效比特數(shù)為2，并且其位置為3和4比特位置，然后通過一次循環(huán)保存該2個比特。然后將指向輸入比特數(shù)據(jù)的指針加1，跳過第2個需打掉的比特。然后重復(fù)第2步操作，直到將打孔表中的數(shù)都取出為止，這樣便存儲了對后一個打孔比特之前的需要存儲的所有比特。

第三步:檢查最后一個打孔比特的位置是否等于輸入的比特數(shù)。若不相等，則還有剩余的比特需要存儲，并且其個數(shù)為輸入的比特數(shù)減去最后一個打孔比特的位置后減1，需要通過一次循環(huán)保存這些比特后打孔操作完畢;若相等，則說明打孔操作完畢。

2 改進(jìn)的打孔方法

雖然上述傳統(tǒng)的打孔方法利用查表的途徑很大程度上降低了算法復(fù)雜度，有效地提高了計算效率，但是一種打孔方法開辟一張表格的做法卻大大增加了系統(tǒng)的內(nèi)存消耗，對于同樣追求內(nèi)存占用效率的系統(tǒng)來說仍存在改進(jìn)空間。因此，本文通過分析打孔算法及打孔位置的特點(diǎn)，提出一種新的打孔方法，并基于新的打孔方法提出一張新的打孔碼表，同時將多張新打孔表整合到同一張表中，降低了算法復(fù)雜度的同時大大降低了系統(tǒng)內(nèi)存占用。

2.1 改進(jìn)的打孔算法

傳統(tǒng)的打孔算法是通過查表去除信息比特中的無效比特實(shí)現(xiàn)打孔操作，該方法雖然能降低算法復(fù)雜度，但是其算法復(fù)雜度會隨著需打孔的比特數(shù)的增加而急劇增大。本文通過分析信道的打孔特點(diǎn)，發(fā)現(xiàn)同一類型的信道其打孔后的比特數(shù)基本一致，基于該種結(jié)論，本文提出一種新的算法，通過保存信息比特中的有效比特來實(shí)現(xiàn)打孔，與傳統(tǒng)算法相比，改進(jìn)的算法其復(fù)雜度更低，并且在有效比特信息數(shù)相同的情況下，算法復(fù)雜度不會隨著所需打孔的無效比特數(shù)的增加而增大。

設(shè)Pp_U16InputDataAddr為待打孔比特信息數(shù)組首地址，Pp_U16InputDataAddr為存放打孔后輸出比特信息數(shù)組首地址，GTa_U16MCS_Punc_Tab為存放需保存比特位置信息的打孔碼表，則改進(jìn)的打孔算法描述如下文。

第一步:取出打孔碼表的第一個比特位置信息GTa_U16MCS_Punc_Tab［0］，得到第一個需存放比特的相對位置L_U16Relative_Position，那么第一個待存放比特的絕對位置為基地址加上相對位置，即Pp_U16InputDataAddr=Pp_U16OutputDataAddr+L_U16Relative_Position;將該位置比特信息存放到輸出信息比特數(shù)組，同時將輸出比特信息數(shù)組的地址指向下一個待存放信息比特的地址，即(*Pp_U16InputDataAddr++)=*Pp_U16InputDataAddr;

第二步:取出打孔碼表的第2個比特信息GTa_U16MCS_Punc_Tab［1］，得到第2個需存放比特的相對位置L_U16Relative_Position;那么第2個待存放的信息比特的絕對位置為Pp_U16InputDataAddr=Pp_U16OutputDataAddr+L_U16Relative_Position;將該位置比特信息存放到輸出信息比特數(shù)組，同時將輸出比特信息數(shù)組的地址指向下一個待存放信息比特的地址，即(*Pp_U16InputDataAddr++)=*Pp_U16InputDataAddr;

然后重復(fù)第二步操作，一直到所有比特信息都全部存儲完畢，則完成該信道的打孔操作。

2.2 改進(jìn)的打孔碼表

根據(jù)上述打孔算法，可以知道改進(jìn)的打孔表中需存放的應(yīng)該是需要存儲的比特位置的相對偏移信息。以MCS1的P1打孔方式為例，傳統(tǒng)的打孔碼表中前2個位置存放的是2和5，表示第2個和第5個位置的比特需要去除，則其存儲了第0，1，3，4這4個位置的比特。那么按照新的打孔算法來實(shí)現(xiàn)時，則新的打孔碼表中需存放0，1，2，1，其表示的意思為較前一個存儲信息位置的下一個位置的偏移。即第1個需存儲的比特的地址為L_U16Base_Position+0，第2個需存儲的比特的地址為L_U16Base_Position+0+1，第3個需存儲的比特的地址為L_U16Base_Position+0+1+2…依此類推。基于該種思想，本文對MCS1打孔表進(jìn)行如下改進(jìn)，如表3所示。

表3 MCS1改進(jìn)的P1打孔方式表

通過比較傳統(tǒng)打孔碼表與改進(jìn)的打孔碼表，不難發(fā)現(xiàn)由于傳統(tǒng)打孔碼表中存放的是需要打孔的比特的絕對位置，并且該絕對位置可能很大，那么其1個word只能容納1個打孔位置信息。以MCS1為例，在傳統(tǒng)打孔碼表中，打孔方式P1最后一個需要打孔的位置為587，其在存儲這個數(shù)據(jù)時的2進(jìn)制表示為1001001011，1個無符號整形word為16 bit，那么對于這類打孔表來說，1個word只能存放一個打孔位置信息。然而通過分析改進(jìn)的打孔碼表，發(fā)現(xiàn)其前后兩個需要存儲的比特位置最大距離都不超過7，而7的2進(jìn)制表示為111，只需要3 bit即可表示，那么該種表的一個word便可以存放16/3≈5個位置信息，基于該種分析，本文將其余MCS類型信道打孔表按表3方式改進(jìn)后，然后按表4方式進(jìn)行合并。

如表4所示，改進(jìn)后的一張打孔表可以存放5種類型打孔表信息，其中MCS1的P1打孔方式占據(jù)1個word的0～2 bit，P2打孔方式占據(jù)1個word的3～5 bit;MCS2的P1打孔方式占據(jù)1個word的6～8 bit，P2打孔方式占據(jù)1個word的9～11 bit;MCS3的P1打孔方式占據(jù)1個word的12～14 bit，最高比特位空出，剩余的打孔表依次按此方式列出。那么在新的打孔算法中利用該改進(jìn)的打孔碼表時，還需增加一步，在取比特位置信息的時候通過移位相與取出該信道的該種打孔方式下的比特偏移位置。以MCS1的P2為例，則在取第1個word后需要將該word向右移3 bit，然后與0x7相與得到該打孔方式的第一個需存儲比特相對位置，若是MCS2的P1打孔方式，則需要先向右移6 bit然后與0x7相與得到需存儲比特相對位置，其余以此類推。

表4 改進(jìn)的打孔碼表

3 性能分析

比較改進(jìn)前和改進(jìn)后的算法實(shí)現(xiàn)，改進(jìn)前的算法中由于打孔表中存放的是需打孔信息的絕對位置，每一次需要與前一位置相減后得到2個打孔位置之間的有效信息比特，然后存儲，這中間就存在了2層循環(huán)嵌套的計算，而且該2層循環(huán)嵌套的計算會隨著需打孔比特數(shù)的增加而加大計算復(fù)雜度。而改進(jìn)后的打孔表中由于存放的是需存儲比特的相對位置，故只需要通過簡單的地址相加，然后通過一層循環(huán)便可以存儲有效信息比特。

比較改進(jìn)前和改進(jìn)后的碼表，改進(jìn)前每一種打孔方式都需要進(jìn)行單獨(dú)存放，若是對MCS1、MCS2的兩種打孔方式和MCS3的P1打孔方式進(jìn)行傳統(tǒng)存放，則需要216×2+360×2+576=1 728個word的內(nèi)存空間，然而進(jìn)行改進(jìn)后的打孔碼表存放該5種打孔信息只需要372個word的內(nèi)存空間，比傳統(tǒng)的碼表存放節(jié)約了約78.5%的內(nèi)存空間。

以上只是簡單地分析了其內(nèi)存占用和算法復(fù)雜度情況，下面在ZSP800平臺上來對這兩種方法進(jìn)行對比實(shí)現(xiàn)，比較其實(shí)際的性能情況。

由于算法復(fù)雜度在DSP平臺上直接地反映是其執(zhí)行周期數(shù)，因此本文在ZSP800平臺上對MCS1～MCS3采用不同打孔方式的改進(jìn)前后算法進(jìn)行了Cycle數(shù)的對比統(tǒng)計分析，如表5所示。由表5可以看出，改進(jìn)前算法的執(zhí)行周期會隨需打孔的比特數(shù)目的增加而急劇上升，而改進(jìn)后的算法由于其存儲的是有效比特的相對位置，其循環(huán)次數(shù)是穩(wěn)定的，故其執(zhí)行周期數(shù)比較穩(wěn)定，而且總體比改進(jìn)前持下降趨勢。隨著需打孔比特數(shù)目的增多，其下降幅度越大。

表5 改進(jìn)前后算法復(fù)雜度對比

表6為改進(jìn)前后各.map文件中對打孔表占據(jù)的內(nèi)存空間的統(tǒng)計。由表6可以看出，在傳統(tǒng)的打孔方式，即每種打孔方式占據(jù)1張打孔表的情況下，其內(nèi)存空間占據(jù)消耗較大，MCS1～MCS3的5種打孔碼表共占據(jù)了0xd8×2+0x168×2+0x240=0x6c0的word空間，而新的方式下只需要0x174的word空間，只占據(jù)改進(jìn)前碼表21.5%的空間大小。綜上分析，本文提出的打孔方法不僅大大降低了其計算復(fù)雜度，而且有效地減少了其數(shù)據(jù)內(nèi)存占用空間。

4 結(jié)論

本文提出了一種新的打孔方法，通過在傳統(tǒng)算法中去除需打孔比特的算式改為存放有效信息比特的算式，有效地提高了計算效率。同時根據(jù)這一算法將傳統(tǒng)打孔碼表中存放需打孔比特位置的方式改進(jìn)為存放有效信息比特相對位置的方式，同時將改進(jìn)后的多張打孔表合并到一張表中，有效地降低了數(shù)據(jù)內(nèi)存空間占用。最后基于DSP實(shí)現(xiàn)驗(yàn)證了該方法的可行性和有效性，并對比了其與傳統(tǒng)算法的算法復(fù)雜度和內(nèi)存占用情況，對其他模式下打孔算法的DSP實(shí)現(xiàn)具有一定參考意義。

表6 MCS1改進(jìn)的P1打孔方式表

［1］崔雁松.移動通信技術(shù)［M］.西安:西安電子科技大學(xué)出版社，2012.

［2］張永光，樓才義.信道編碼及其識別分析［M］.北京:電子工業(yè)出版社，2010.

［3］臧嵐.一種基于貪婪搜索的碼率兼容LDPC碼打孔算法［J］.電視技術(shù)，2013，37(13):105－108.

［4］ 3GPP TS 45.001，Physical layer on the radio path;General description(Release 5)［S］.2005.

［5］ 3GPP TS45.002，Multiplexingandmultipleaccesson the radio path(Release 5)［S］.2005.

［6］ 3GPP TS 45.003，Channel coding(Release 5)［S］.2006.

［7］ ZSP800 digital signal processor core technicalmanual［EB/OL］.［2013－05－20］.http://www.verisilicon.com/IPPortfolio_cn_13_50_2_ZSP800.html.

［8］韓斌杰，杜新顏，張建斌.GSM原理及其網(wǎng)絡(luò)優(yōu)化［M］.北京:機(jī)械工業(yè)出版社，2009.