2025/01/21 by Zhou, Zhaienhe, Zeyu Guo, Guo, Zeyu
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Algorithms and Data Compression #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2501.12293
openalex publication_date 2025/01/21 · openalex created_date 2025/01/24 · openalex updated_date 2026/07/28
In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that δd0 > 2 , corrects up to αn errors for a Tanner code T(G, C0) , where G is a (c, d, α, δ) -bipartite expander with n left vertices, and C0 ⊆ \mathbbF2d is a linear inner code with minimum distance d0 . This result improves upon the previous work of Shen, Shangguan, Ouyang and Cheng (IEEE TIT 2025), which required δd0 > 3 . We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius of αn , compared with the previous radius of (2α)/(d0(1 + 0.5cδ) )n. Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code T(G,C0) is approximately fδ-1 ( (1)/(d0) ) αn , where fδ(⋅) is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from αn to approximately fδ-1((2)/(d0))αn. Finally, we extend Viderman's find-erasures-and-decode framework (ACM TOCT 2013) to general linear inner codes, obtaining a deterministic linear-time decoder for δd0>1.8 when d0=3, thus pushing below the δd0 > 2 threshold of our general result.