An Optimization Model for Binary Deletion/Insertion Channel Decoding
Kai Jin · 2024
Synchronization channels, including binary deletion channel (BDC) and binary insertion channel (BIC) present a significantly more challenging analytical landscape in comparison to memoryless channels such as binary symmetric channel. These channels are at the heart of numerous fundamental challenges within the domains of information theory and theoretical computer science. While there exists decoding algorithm tailored for BDC and BIC channels, it remains under-explored to carry out channel decoding for BIC and BDC through a unified optimization perspective. In this paper, we first develop an unified optimization model to characterize the decoding process of binary deletion insertion channels. We then propose a reinforcement learning aided branch and bound (RLBB) decoder for binary deletion insertion channels. We further employ the alternating direction method of multipliers (ADMM) algorithm to address this optimization problem by incorporating a penalty term into the objective function. Extensive simulation experiments have been carried out to assess the performance of the proposed decoding algorithms. It is seen that the proposed decoders perform favorably with competing methods.