低时间复杂度的极化码译码算法

Decoding algorithm of polarization code with low time complexity

极化码的串行抵消列表(successive cancellation list,SCL)译码算法是目前应用最广泛的译码算法,但是复杂度和时延很高。为了降低时间复杂度,提出了一种基于综合检测(syndrome check,SC)的快速SCL译码与球形列表(list sphere decoding,LSD)译码相联合的办法,简称SC-SCSL(syndrome check successive cancellation sphere list)译码。该算法避免了SCL译码在不同路径的相同节点同时满足综合检测时,极易导致结果出错的情况,仿真结果表明,在同时满足综合检测时性能与SCL相差不大;同时联合了LSD译码,来降低时间复杂度。在几乎不损失性能的情况下,相比于循环冗余协助下的串行抵消列表(cyclic redundancy check aided successive cancellation list,CA-SCL)译码降低了50%~55%的时间复杂度。

The successive cancellation list(SCL)decoding algorithm of polarization codes is currently the most widely used decoding algorithm,but its complexity and delay are very high.In order to reduce the complexity,this paper proposes a fast SCL decoding method based on syndrome check(SC)combined with list sphere decoding(LSD)decoding algorithm,called syndrome check successive cancellation sphere list(SC-SCSL)decoding.The algorithm avoids the situation that SCL decoding meets the SC at the same node of different paths,which is easy to cause the result to be wrong,and the simulation results show that the performance is not much different from SCL when satisfying the SC at the same time.Compared with the cyclic redundancy check aided successive cancellation list(CA-SCL)decoding,it reduces the time complexity by 50%~55%with almost no performance loss.