List Decoding of Polar Codes
List Decoding of Polar Codes
复制标题
DOI：
10.1109/tit.2015.2410251
复制
发表时间：
2015-05-01
影响因子：
2.5
通讯作者：
Vardy, Alexander
中科院分区：
文献类型：
--
作者：
Tal, Ido;Vardy, Alexander
我们描述了一种极性码的连续消除列表解码器，它是 Arikan 经典连续消除解码器的推广。在所提出的列表解码器中，在每个解码阶段同时考虑L个解码路径，其中L是整数参数。在解码过程结束时，L 个路径中最有可能的路径被选择作为解码器输出处的单个码字。模拟表明，即使 L 值适中，所得性能也非常接近最大似然解码。或者，如果允许精灵从列表中选择传输的码字，则结果与当前最先进的 LDPC 码的性能相当。我们证明，使用简单的 CRC 预编码可以轻松实现这样的精灵。实现此性能的特定列表解码算法将每个信息位的解码路径数量加倍，然后使用修剪过程丢弃除 L 个最可能路径之外的所有路径。然而，直接实现该算法需要 Omega(Ln(2)) 时间，这与原始逐次消除解码器的 O(n log n) 复杂度形成鲜明对比。在本文中，我们利用极性码的结构以及某些算法转换来克服这个问题：我们设计了一种高效、数值稳定的列表解码器实现，仅需要 O(Ln log n) 时间和 O(Ln) 空间。
We describe a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arikan. In the proposed list decoder, L decoding paths are considered concurrently at each decoding stage, where L is an integer parameter. At the end of the decoding process, the most likely among the L paths is selected as the single codeword at the decoder output. Simulations show that the resulting performance is very close to that of maximum-likelihood decoding, even for moderate values of L. Alternatively, if a genie is allowed to pick the transmitted codeword from the list, the results are comparable with the performance of current state-of-the-art LDPC codes. We show that such a genie can be easily implemented using simple CRC precoding. The specific list-decoding algorithm that achieves this performance doubles the number of decoding paths for each information bit, and then uses a pruning procedure to discard all but the L most likely paths. However, straightforward implementation of this algorithm requires Omega(Ln(2)) time, which is in stark contrast with the O(n log n) complexity of the original successive-cancellation decoder. In this paper, we utilize the structure of polar codes along with certain algorithmic transformations in order to overcome this problem: we devise an efficient, numerically stable, implementation of the proposed list decoder that takes only O(Ln log n) time and O(Ln) space.