2023/12/26 by Cheng, Kuan, Ouyang, Minghui, Shangguan, Chong +1 · 1 citation
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2312.16087
Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph G together with a linear inner code C0. Expander codes are Tanner codes whose defining bipartite graph G has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ and d0 must satisfy, so that every bipartite expander G with vertex expansion ratio δ and every linear inner code C0 with minimum distance d0 together define an expander code that corrects Ω(n) errors in O(n) time? For C0 being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that δ>3/4 is sufficient; later Viderman (ACM-TOCT'13) improved this to δ>2/3-Ω(1) and he also showed that δ>1/2 is necessary. For general linear code C0, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that d0=Ω(cδ-2) is sufficient, where c is the left-degree of G. In this paper, we give a near-optimal solution to the above question for general C0 by showing that δd0>3 is sufficient and δd0>1 is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.