LTE系统Reed-Muller译码算法及DSP实现*

彭德义 ，李小文，刘 聪

（1.重庆邮电大学 重庆市移动通信技术重点实验室，重庆400065；2.海南大学 信息科学技术学院，海南 海口 570228）

在长期演进(LTE)系统中，上行控制信息（UCI）包括信道质量指示信息CQI/PMI和混合自动请求重传应答信息HARQ-ACK等，输入编码器的比特数目较少。同时为了保证一定的数据传输可靠性，在很大程度上依赖于有效的信道编码方法。Reed-Muller是一种能够纠正多个差错的线性分组码[1]。这种码的构造比较简单，结构特性也相当丰富，在实际工程中得到广泛的应用，特别是应用于编码比特较少的情况。但是与经典的RM码相比，3GPP LTE协议[2]中采用的是一种基于RM码的超码编码方式，编码矩阵还采用了更复杂的交织技术，同时也增加了更多的掩码序列，这使得接收端的译码实现难度大大的增加，因此需要研究出一种有效的译码算法。

数字信号处理芯片DSP，以其数字器件特有的稳定性、可重复性、可大规模集成、特别是可编程性和易于实现自适应处理等特点，给数字信号处理的发展带来巨大机遇，并且使得信号处理手段更加灵活，功能更加复杂，应用范围也扩展到移动通信的各个领域。近年来DSP芯片功能越来越强大，特别是TI公司推出的DSP芯片TMS320C64x,片内拥有8个并行处理单元，体系结构采用甚长指令字(VLIW)结构，最高时钟频率可以达到300 MHz[3]。在这些强大的功能支持下，使得信号处理研究的重点在很大程度上可以放在软件算法上，所以在TD-LTE综合测试仪表系统中采用了这款芯片。本文重点研究了RM译码算法在TMS320C64x芯片上的软件实现。

1 LTE系统中Reed-Muller编码

在TD-LTE上行发送端，即UE端，当输入序列长度在编码器范围内时,需要对上行控制信息UCI(包括HARQ-ACK和CQI)进行RM编码。由于承载UCI的信道包括PUSCH和PUCCH，故在这两个信道处理过程中采用不同的RM编码生成矩阵，在PUSCH上进行(32，11)编码过程，而在 PUCCH上进行(20，13)编码过程[2]。3GPP TS36.212协议上的编码矩阵是由交织之后的Walsh码和基本的掩码序列组成。其中（32，11）编码矩阵是由一阶Reed-Muller码和5个基本的掩码序列进行行交织而得到的，而（20，13）编码矩阵是由一阶 Reed-Muller码和7个基本的掩码序列进行行交织后对后12行进行打孔而得到的。具体的编码公式为:

式(1)中 On表示输入比特；Mi,n表示（32，11）或（20，13）编码表；bi表示编码输出比特，O表示输入编码器比特长度。

编码入口参数:TxPUSCHCQIDataIn,TxQ_cqi,TxPUSCH CQIDataout，其中编码矩阵M在CCS3.3中直接存储_PUSCHRMM和_PUCCHRMM。

2 RM译码算法的仿真与选择

Reed-Muller码是一种线性分组码，可以利用冗余比特对接收比特进行检错和纠错。对于线性分组码，尽管码的生成可以高效地实现，但一般线性分组码的译码问题却一直难以解决。为此，参考文献[4]提出一种全搜索算法，其实质是一种最大似然ML算法，基本思想是：在接收端将所有的码字都进行编码，然后将编码后的所有码字与接收到的码字进行比较，找出最相似的码字作为译码结果，具体方法为对于（32,11）或（20,13）RM译码，将2 048或8 192组长度为11或13的比特序列进行与发送端相同的编码,得到2 048或8 192组长度为32或20的比特序列，然后将接收到的比特序列分别减去这2 048或8 192组比特序列并统计非0元素的个数，即求相关值。这种算法存在两方面的问题：一是需要对所有可能的编码序列进行编码，运算量过大；二是要对每一组码字序列开辟存储空间，占用过多的内存空间。

通过研究可知参考文献[5]和参考文献[6]提出的基于软判决FHT译码算法，将接收到的码字进行简单的双极性化处理：若大于0则判为1，否则判为-1。这是因为哈达码矩阵是由1与-1组成的，这样处理便于后面的FHT。然而在TD-LTE无线综合测试系统中，eNodeB端进行解调解扰处理后的数据为软信息，所以本文主要对输入的软信息进行RM译码处理。

图1为在加性高斯白噪声信道AWGN(Additive White Gaussian Noise)下对全搜索算法和软判决FHT算法分别在PUSCH和PUCCH信道中的误比特率进行仿真比较。仿真结果表明：在同等情况下，基于快速哈达码变换的软判决算法的性能要比全搜索算法性能高2～3 dB，并且前者的运算效率也远大于后者。同时可以看出，在PUSCH信道中进行的（32,11）RM译码相对于在PUCCH信道中进行的 (20,13)RM译码有高达4 dB的编码增益,这是因为（20,13）RM编码矩阵是由（32,11）的编码矩阵进行打孔并增加两列掩码序列得到的，根据参考文献[7],编码矩阵的打孔和增加掩码序列都将损失一定的编码增益，该仿真结果验证了理论的正确性。

3 RM译码算法的DSP实现

3.1 硬件简介

TMS320C6000是最初主要为移动通信基站的信号处理而推出的超级处理芯片，200 MHz时钟的C64x完成2 048点定点 FFT的时间只需要 66 μs，比传统 DSPs要快一个数量级，因此在测试仪表的开发领域有广阔的应用前景。C64x系列DSP最主要的特点是在体系结构上采用了VelocoTI甚长指令集VLIW(Very Long Instruction Word)。在VLIW体系结构的DSP中，是由一个超长的机器指令字来驱动内部的多个功能单元。由于每条指令的字段之间是相互独立的，故可以单周期发射多条指令，从而实现更高的指令级并行效率。CPU采用哈佛结构，程序总线与数据总线分开，取指令与执行指令可并行运行。程序总线宽度为256 bit，每一次取指令操作都是取8条指令,称为一个取指包。C64x系列DSP芯片的大容量、高运算能力等这一些优点使其毫无疑问地在无线基站、终端等场合下得到广泛的应用，特别是运算精度能满足综合测试仪表的开发条件。

3.2 RM译码算法处理流程

基于快速哈达码FHT变换的RM译码是利用编码表的组成原理，求Hadamard矩阵与接收码字的相关值，从而根据相关值特性进行判决译码。UE通过PUSCH或PUCCH传输上行控制信息UCI,在网络端进行解调、解扰及解信道交织（仅在PUSCH）后得到的是软信息(16 bit位置表示1 bit软信息）。其具体处理过程如图2所示。由图2可以看出RM译码实现过程主要包括五个部分：双极性化、解交织、消掩码、Hadamard变换以及译码判决。基于此，本文提出的一种实现方案输入输出变量及调用格式如表1所示。

图2 FHT译码算法处理流程

调用格式：Turbo_Code(int*,int,int*,int,int),其中RxDecode_UCI_DataIn表示输入序列的首地址；RxRMInLen表示输入序列长度；Rx Decode_UCI_DataOut表示译码输出序列首地址；RxO_UCI表示译码输出序列长度；ChannelFlag用来区分信道，其中ChannelFlag=0表示PUSCH，ChannelFlag=1表示 PUCCH。

3.3 RM译码算法程序实现

接收端工程中,根据Channel Flag判定是调用PUSCH译码过程还是PUCCH译码过程，原因是PUSCH译码输入码字长度为32,而PUCCH译码输入码字长度为20,所以在PUCCH译码条件下首先在输入码字后面添加12 bit的占位符，即添加12个半字的 0,这是为了在进行FHT变换时保证是2的整阶乘次方。此外，需要预先开辟的存储空间如表2所示。

表1 输入输出参数

表2 预先开辟的存储空间

3.3.1 软合并、双极性化及解交织过程

在PUSCH信道条件下,当输入软信息长度大于32时，需要对每32个软信息进行软信息合并。具体过程为以起始的 32 bit软信息作为基准，地址偏移 32×2=64（因为输入序列是以每个软信息占16 bit位置而存储的）取下一个32 bit的软信息,将前32 bit的软信息与当前32 bit的软信息进行加权平均之后存储在_SoftCombineData，作为下一个32 bit软信息合并的基准值。如此循环整字数次，对于整32 bit的剩余比特进行单独处理如下：将剩余比特与前32 bit的软信息进行加权平均，然后存储在_SoftCombineData，循环剩余比特数次。

将接收的软信息根据其符号位进行双极性化[8],以便于后面的FHT变换操作。然后按照下列交织表进行解交织处理。

＜31,0,20,1,2,21,3,4,22,5,6,23,7,8,9,24,19,25,10,11,12,13,26,27,14,15,28,16,17,18,29,30＞

3.3.2 消掩码处理

将解交织之后的序列_RxRMtemp0或_RxRMtemp1分别与消掩表的每一行进行内积操作，具体过程如下，每次取消掩表的32 bit数据，根据这32 bit数据来决定解交织之后序列的符号，从而内循环32决 次，然后取消掩表的下一行，如此循环32次或者128次。

3.3.3 FHT变换

本文通过研究分析Hadamard矩阵的性质，将消掩码处理之后的32个或128个长度为32 bit的矩阵与32阶Hadamard矩阵相乘，转化为5级蝶形运算，从而大大减小了处理的运算复杂度。可以这样计算：每一级进行加法和减法各16次，从而得到总的运算量为16×2×5=160次。

3.3.4 译码判决

在进行 FHT变换后的 1 024(32×32)或者 4 096(128×32)个软信息比特中，找出绝对值最大值，并且记录其在矩阵中的行序号和列序号。由于编码矩阵中M0为全1序列，它对相关值矩阵的影响是改变矩阵中所有值的符号，因此根据绝对值最大数的实际符号来译第1 bit，即：正号时，译为0；负号时，译为 1。由于在发送端进行编码时第 2～6 bit与 Reed-Muller码相乘，故绝对值最大值列序号对应的二进制形式即为第2～6 bit。由于在发送端进行编码时第7～11 bit与掩码相乘，故绝对值最大值行序号对应的二进制形式即为第 7～11 bit。

4 性能分析

在进行DSP软件设计时，需要对程序进行优化，尽量减少或者消除程序中的“NOP”指令，特别是循环体内的“NOP”指令。通过在CCS3.3上进行程序的仿真运行，在理想信道环境下，统计得到各种条件下的译码仿真执行结果，如表3所示。

表3 不同数据长度的RM译码速率

表3仅列举了几种典型的数据长度，且不失一般性，总体性能基本不会受输入数据长度的约束。通过分析可以看出：PUSCH_100与PUSCH_32相比，处理时间主要耗费在软信息合并处理上，而PUCCH_20与PUSCH_32相比，由于消掩表为128×32的矩阵，在进行消掩码和FHT变换时，处理时间是后者的4倍，因此处理时间相对较长。TMS320C64x芯片的主频为1GHz，一个指令周期耗时1 ns,所以本文提出的译码算法DSP实现可以达到约兆比特每秒的速率，且误比特率相当低，满足LTE综合测试系统的性能要求。

本文从RM编码理论出发，根据TD-LTE综合测试系统的特点，通过Matlab链路级仿真比较，为LTE系统选择了一种最优的FHT译码算法，提出了一种简单有效的RM译码实现算法，特别是运用蝶型运算对FHT变换运算进行了大量简化，并对其在TMS320C64xDSP中进行实现。重点描述了FHT变换译码算法在DSP中的实现方法，通过程序在CCS3.3上运行仿真，证明本算法在高斯白噪声信道（AWGN）环境下具有较低的误码率和较高的译码运行速率，能够满足TD-LTE系统的性能需求。由于其实现的可行性和高效性，该实现方案已应用于TD-LTE无线综合测试仪表的开发当中。

[1]FREUDENBERGER J(著).编码理论——算法、结构和应用[M].北京：人民邮电出版社，2009:42-48.

[2]3GPP TS 36.212 v9.0.0 evolved universal terrestrial radio access(E-UTRA)multiplexing and channel coding(Release 9)[S].2009-12.

[3]Texas Instruments Incorporated.TMS320C6000系列DSP编程工具与指南[M].田黎育，何佩琨，朱梦宇，译.北京：清华大学出版社，2006:32-50.

[4]吴湛击，吴伟陵.3GPP中的Reed-Muller编译码算法[J].电子学报,2005,33(1)：147-149.

[5]BRUNASHEV M V,DUMER I.Error exponents for two soft-decicision decoding algorithms of reed-muller code[J].IEEE Transactions on Iformation Theory,2009,55(9):4108-4118.

[6]DUMER I.Soft-decision decoding of reed-muller codes:a simplified algorithm[J].IEEE Transactions on Information Theory,2006,52(3):956-963.

[7]JONES A E,WILKINSON T A.Performance of reed-muller codes and a maximum-likelyhood decoding algorithm for OFDM[J].IEEE Transaction On Communication,1999，47(7)：949-952.

[8]Prokis John G(著).数字通信（第五版）[M].张力军,张宗橙,郑宝玉，等（译）北京：电子工业出版社，2005:340-371.