Abstract
This paper introduces a neural polar decoder (NPD) for deletion channels with a constant deletion rate. Existing polar decoders for deletion channels exhibit high computational complexity of $O(N^4)$, where $N$ is the block length. This limits the application of polar codes for deletion channels to short-to-moderate block lengths. In this work, we demonstrate that employing NPDs for deletion channels can reduce the computational complexity. First, we extend the architecture of the NPD to support deletion channels. Specifically, the NPD architecture consists of four neural networks (NNs), each replicating fundamental successive cancellation (SC) decoder operations. To support deletion channels, we change the architecture of only one. The computational complexity of the NPD is $O(AN\log N)$, where the parameter $A$ represents a computational budget determined by the user and is independent of the channel. We evaluate the new extended NPD for deletion channels with deletion rates $\delta\in\{0.01, 0.1\}$ and we verify the NPD with the ground truth given by the trellis decoder by Tal et al. We further show that due to the reduced complexity of the NPD, we are able to incorporate list decoding and further improve performance. We believe that the extended NPD presented here could have applications in future technologies like DNA storage.
Abstract (translated)
本文介绍了一种用于恒定删除率删除信道的神经极化解码器（NPD）。现有的针对删除信道的极化解码器具有较高的计算复杂度，为$O(N^4)$，其中$N$表示块长度。这限制了极化码在短至中等长度块中的应用。在这项工作中，我们证明采用NPD可以降低删除信道的计算复杂度。首先，我们将NPD架构扩展以支持删除信道。具体来说，NPD架构由四个神经网络（NN）组成，每个网络复制基础连续取消（SC）解码器的操作。为了支持删除信道，我们只修改了一个架构。 NPD的计算复杂度为$O(AN\log N)$，其中参数$A$代表用户确定的计算预算，并且与信道无关。我们评估了新的扩展型NPD在删除率为$\delta\in\{0.01, 0.1\}$的删除信道中的表现，并通过Tal等人提出的网格解码器验证了NPD的结果。 此外，由于NPD复杂度降低，我们可以引入列表解码以进一步提升性能。我们认为这里介绍的扩展型NPD可能在未来技术如DNA存储中有应用前景。
URL
https://arxiv.org/abs/2507.12329
