一種改進的打孔方法及其DSP實現

彭 沖，鄭建宏，吳廣富

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

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

1 傳統的打孔方法

在GSM系統中，不同信道信息的打孔位置通過計算后，以碼表的形式表現出來，在執行打孔操作時，直接調用碼表中存儲的比特打孔位置對信息進行操作［8］。

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

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

表1 MCS1打孔方式P1和P2

表2 MCS1的P1打孔方式表

算法描述如下:

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

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

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

2 改進的打孔方法

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

2.1 改進的打孔算法

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

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

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

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

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

2.2 改進的打孔碼表

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

表3 MCS1改進的P1打孔方式表

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

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

表4 改進的打孔碼表

3 性能分析

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

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

以上只是簡單地分析了其內存占用和算法復雜度情況，下面在ZSP800平臺上來對這兩種方法進行對比實現，比較其實際的性能情況。

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

表5 改進前后算法復雜度對比

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

4 結論

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

表6 MCS1改進的P1打孔方式表

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

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

［3］臧嵐.一種基于貪婪搜索的碼率兼容LDPC碼打孔算法［J］.電視技術，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原理及其網絡優化［M］.北京:機械工業出版社，2009.