2025/09/16 by Qingqing Peng, Ke Liu, Peng, Qingqing +5
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Cooperative Communication and Network Coding #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2509.13040
openalex publication_date 2025/09/16 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
It is well known that, given \(b≥ 0\), finding an (a,b)-trapping set with the minimum \(a\) in a binary linear code is NP-hard. In this paper, we demonstrate that this problem can be solved with linear complexity with respect to the code length for codes with bounded treewidth. Furthermore, suppose a tree decomposition corresponding to the treewidth of the binary linear code is known. In that case, we also provide a specific algorithm to compute the minimum \(a\) and the number of the corresponding \((a, b)\)-trapping sets for a given \(b\) with linear complexity. Simulation experiments are presented to verify the correctness of the proposed algorithm.