论文部分内容阅读
近年来，为了满足新的通信需求，实现移动设备之间低时延、高速率和高可靠性连接，第五代（Fifth-Generation,5G）移动通信系统在数据信道和控制信道中引入了新的编码技术。低密度奇偶校验（Low-Density Parity-Check,LDPC）码由于其性能非常接近香农极限，已被确定为5G标准中的数据信道编码方案。因此设计一种高速率、高纠错性能的LDPC译码器对工程实践具有重要意义。
在LDPC码的置信传播（Belief Propagation,BP）译码算法中，同一类节点更新时可以并行处理，如算法中变量节点更新或校验节点更新过程中只需要关注校验矩阵中行或列中‘1’元素所在的位置，所以可以用现场可编程门阵列（Field Programmable Gate Array,FPGA），专用集成电路（Application Specific Integrated Circuit,ASIC）和图形处理器（Graphic Processing Unit,GPU）来设计LDPC码译码器，来提高译码速度。虽然基于FPGA和ASIC平台实现LDPC译码算法取得了一定的成果，但硬件平台的可扩展性和灵活性与软件平台相比较差，且硬件平台费用相对较高。而采用GPU实现译码方案可以较好地满足高扩展性、高灵活性和低成本的需求。尤其是近年来英伟达提出了计算机统一设备架构（Compute Unified Device Architecture,CUDA）平台，其卓越的处理能力使基于GPU实现LDPC译码算法可望具有光明的前景。
对于LDPC长码，校验矩阵中没有短环，在BP迭代译码过程中的变量节点输出的消息可以成功地收敛：而当LDPC码长较短时，校验矩阵存在大量的短环。因为短环的存在，使得各节点在译码迭代过程中存在相关性，从而导致消息在迭代过程中变得不可靠。所以短环的存在会造成译码性能急剧下降，不利于迭代算法的收敛。为了解决短环带来的译码性能的损失，一种准最大似然（Quasi-Maximum Likelihood,QML）译码器被提出来。这种译码器是在传统的BP译码失败后引入一种再处理（Reprocessing）过程，通过再处理过程消除大量导致BP译码器不收敛的伪码字。Kang Peng等人提出的增强准最大似然（Enhanced Quasi-Maximum Likelihood,EQML）译码器能在0.3dB的误帧率（Frame Error Rate,FER）范围内接近最大似然（Maximum Likelihood,ML）译码器的译码性能。但是由于这种译码器的复杂计算结构会造成译码时间大幅度增加。
为了解决EQML译码器造成的译码时间增加的问题，本文提出了一种利用基于GPU的CUDA平台来高效实现EQML译码器的解决方案，使用CUDA平台将EQML译码器中需要进行大量迭代的译码过程通过GPU多线程加速，达到提高译码速度的目的。本论文主要的完成的工作有：
（1）对于LDPC码的校验矩阵占据大量空间的问题，设计了压缩存储校验矩阵方案。通过压缩校验矩阵使得只用储存非零元素的索引信息，在译码过程中通过索引得到非零元素在校验矩阵中的位置，既能节省GPU上的内存空间又能提高数据处理速度。
（2）对于BP译码算法校验节点和变量节点更新过程存在计算复杂度高的问题，设计了对BP译码算法重新排列的译码方案。重新排列后的算法不仅可以降低变量节点和校验节点更新过程中计算差集带来的循环和判断计算的时间复杂度，还可以在更新过程中采用最大量的线程进行计算，同时可以利用GPU的合并访存机制提高数据的访存速度，这种方案既能降低译码算法的复杂度又能利用GPU内合并访存机制。
（3）对于EQML译码器再处理过程中每个阶段码字间译码的不相关性，利用GPU采用多码字并行译码方案提高译码速度，这样可以充分利用GPU的多线程的优势，避免了基于CPU的EQML译码线程瓶颈。
（4）利用GPU内不同储存器访存速度不同的特点，设计了把译码迭代过程中需要进行频繁读写的数据存储在带宽更高的共享存储器中的方案，加速数据的读写速度。同时对于那些只需要进行读操作的数据，把它们存储到GPU内只读存储器即常量内存中，充分提高了译码器的处理速度。
（5）设计了利用GPU内有独有的页锁机制，降低可分页内存在进行译码时对数据进行两次复制引入译码延迟的方案。利用GPU内流并行机制，使通过深度优先的任务调度次序，降低数据在CPU与GPU之间通过PCI-E总线传输时的空闲等待时间。
（6）最后，对本文提出的GPU实现方案下译码器的加速效果与CPU串行实现方案进行仿真对比，对能够影响译码器译码速度的因素：信噪比、码字长度、再处理最大阶段数等进行了对比实验。
通过研究表明本文设计的基于GPU实现的EQML译码器与CPU实现方案相比能够带来接近两个数量级的速度提升。大大提高了译码器的译码速度，为未来LDPC码在5G领域的进一步应用提供了支撑。
在LDPC码的置信传播（Belief Propagation,BP）译码算法中，同一类节点更新时可以并行处理，如算法中变量节点更新或校验节点更新过程中只需要关注校验矩阵中行或列中‘1’元素所在的位置，所以可以用现场可编程门阵列（Field Programmable Gate Array,FPGA），专用集成电路（Application Specific Integrated Circuit,ASIC）和图形处理器（Graphic Processing Unit,GPU）来设计LDPC码译码器，来提高译码速度。虽然基于FPGA和ASIC平台实现LDPC译码算法取得了一定的成果，但硬件平台的可扩展性和灵活性与软件平台相比较差，且硬件平台费用相对较高。而采用GPU实现译码方案可以较好地满足高扩展性、高灵活性和低成本的需求。尤其是近年来英伟达提出了计算机统一设备架构（Compute Unified Device Architecture,CUDA）平台，其卓越的处理能力使基于GPU实现LDPC译码算法可望具有光明的前景。
对于LDPC长码，校验矩阵中没有短环，在BP迭代译码过程中的变量节点输出的消息可以成功地收敛：而当LDPC码长较短时，校验矩阵存在大量的短环。因为短环的存在，使得各节点在译码迭代过程中存在相关性，从而导致消息在迭代过程中变得不可靠。所以短环的存在会造成译码性能急剧下降，不利于迭代算法的收敛。为了解决短环带来的译码性能的损失，一种准最大似然（Quasi-Maximum Likelihood,QML）译码器被提出来。这种译码器是在传统的BP译码失败后引入一种再处理（Reprocessing）过程，通过再处理过程消除大量导致BP译码器不收敛的伪码字。Kang Peng等人提出的增强准最大似然（Enhanced Quasi-Maximum Likelihood,EQML）译码器能在0.3dB的误帧率（Frame Error Rate,FER）范围内接近最大似然（Maximum Likelihood,ML）译码器的译码性能。但是由于这种译码器的复杂计算结构会造成译码时间大幅度增加。
为了解决EQML译码器造成的译码时间增加的问题，本文提出了一种利用基于GPU的CUDA平台来高效实现EQML译码器的解决方案，使用CUDA平台将EQML译码器中需要进行大量迭代的译码过程通过GPU多线程加速，达到提高译码速度的目的。本论文主要的完成的工作有：
（1）对于LDPC码的校验矩阵占据大量空间的问题，设计了压缩存储校验矩阵方案。通过压缩校验矩阵使得只用储存非零元素的索引信息，在译码过程中通过索引得到非零元素在校验矩阵中的位置，既能节省GPU上的内存空间又能提高数据处理速度。
（2）对于BP译码算法校验节点和变量节点更新过程存在计算复杂度高的问题，设计了对BP译码算法重新排列的译码方案。重新排列后的算法不仅可以降低变量节点和校验节点更新过程中计算差集带来的循环和判断计算的时间复杂度，还可以在更新过程中采用最大量的线程进行计算，同时可以利用GPU的合并访存机制提高数据的访存速度，这种方案既能降低译码算法的复杂度又能利用GPU内合并访存机制。
（3）对于EQML译码器再处理过程中每个阶段码字间译码的不相关性，利用GPU采用多码字并行译码方案提高译码速度，这样可以充分利用GPU的多线程的优势，避免了基于CPU的EQML译码线程瓶颈。
（4）利用GPU内不同储存器访存速度不同的特点，设计了把译码迭代过程中需要进行频繁读写的数据存储在带宽更高的共享存储器中的方案，加速数据的读写速度。同时对于那些只需要进行读操作的数据，把它们存储到GPU内只读存储器即常量内存中，充分提高了译码器的处理速度。
（5）设计了利用GPU内有独有的页锁机制，降低可分页内存在进行译码时对数据进行两次复制引入译码延迟的方案。利用GPU内流并行机制，使通过深度优先的任务调度次序，降低数据在CPU与GPU之间通过PCI-E总线传输时的空闲等待时间。
（6）最后，对本文提出的GPU实现方案下译码器的加速效果与CPU串行实现方案进行仿真对比，对能够影响译码器译码速度的因素：信噪比、码字长度、再处理最大阶段数等进行了对比实验。
通过研究表明本文设计的基于GPU实现的EQML译码器与CPU实现方案相比能够带来接近两个数量级的速度提升。大大提高了译码器的译码速度，为未来LDPC码在5G领域的进一步应用提供了支撑。