一种改进的打孔方法及其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.