Linear Complexity Computation of Code Distance and Minimum Size of Trapping Sets for LDPC Codes with Bounded Treewidth
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911408018423808 |
|---|---|
| author | Peng, Qingqing Liu, Ke Yan, Guiying Wang, Guanghui |
| author_facet | Peng, Qingqing Liu, Ke Yan, Guiying Wang, Guanghui |
| contents | It is well known that, given \(b\ge 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13040 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Complexity Computation of Code Distance and Minimum Size of Trapping Sets for LDPC Codes with Bounded Treewidth Peng, Qingqing Liu, Ke Yan, Guiying Wang, Guanghui Information Theory It is well known that, given \(b\ge 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. |
| title | Linear Complexity Computation of Code Distance and Minimum Size of Trapping Sets for LDPC Codes with Bounded Treewidth |
| topic | Information Theory |
| url | https://arxiv.org/abs/2509.13040 |