.png){kind=icon}
.png){kind=icon}
Return
When Can an Expander Code Correct Ω(n) Errors in O(n) Time?
.png){kind=icon}
PRE
AI
DOI：10.1109/TIT.2025.3586842.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Tanner codes are error-correcting codes built from a bipartite graph G and a short inner code C-0 Expander codes are a special type of Tanner code, where the graph is highly interconnected, ensuring stronger error correction capabilities. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that delta is an element of [0,1] and d(0 )is an element of N must satisfy, so that every bipartite expander G with vertex expansion ratio delta and every linear inner code C-0 with minimum distance d(0) together define an expander code that corrects Omega(n) errors in O(n) time? For C-0 being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that delta > 3/4 is sufficient; later, Viderman (ACM-TOCT'13) improved this to delta > 2/3 - Omega(1) and he also showed that delta > 1/2 is necessary. For general linear code C-0, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that d(0 )= Omega(c delta(-2)) is sufficient, where c is the left-degree of G. We present a near-optimal solution to the above problem for general C0 by showing that delta d(0 )> 3 is sufficient and delta d(0 )> 1 is necessary, thereby significantly improving Dowling-Gao's result. To prove the sufficient condition, we present two novel algorithms for decoding arbitrary expander codes with delta d(0 )> 3, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius. To prove the necessary condition, we generalize the aforementioned necessary result of Viderman, and construct for every pair of delta,d0 with delta d(0 )= 1 , an expander code with constant distance, that only corrects a constant number of errors.
Keywords:
Codes
Graph theory
Decoding
Parity check codes
Linear codes
Bipartite graph
Error correction codes
Training
Data mining
Artificial intelligence
Tanner codes
expander codes
expander graph
linear-time decoding
asymptotically good codes
Journal
I
IF:
2.9
Papers:
317
Citations:
0