一種改進(jìn)的打孔方法及其DSP實(shí)現(xiàn)

彭 沖，鄭建宏，吳廣富

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

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

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

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

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

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

表1 MCS1打孔方式P1和P2

表2 MCS1的P1打孔方式表

算法描述如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 性能分析

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

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

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

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

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

表6為改進(jìn)前后各.map文件中對(duì)打孔表占據(jù)的內(nèi)存空間的統(tǒng)計(jì)。由表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%的空間大小。綜上分析，本文提出的打孔方法不僅大大降低了其計(jì)算復(fù)雜度，而且有效地減少了其數(shù)據(jù)內(nèi)存占用空間。

4 結(jié)論

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

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

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

［2］張永光，樓才義.信道編碼及其識(shí)別分析［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.