When can an expander code correct $Ω(n)$ errors in $O(n)$ time?
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916326917799936 |
|---|---|
| author | Cheng, Kuan Ouyang, Minghui Shangguan, Chong Shen, Yuanting |
| author_facet | Cheng, Kuan Ouyang, Minghui Shangguan, Chong Shen, Yuanting |
| contents | 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 $C_0$. 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 $d_0$ must satisfy, so that \textit{every} bipartite expander $G$ with vertex expansion ratio $δ$ and \textit{every} linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $Ω(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 $δ>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 $C_0$, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that $d_0=Ω(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 $C_0$ by showing that $δd_0>3$ is sufficient and $δd_0>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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_16087 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | When can an expander code correct $Ω(n)$ errors in $O(n)$ time? Cheng, Kuan Ouyang, Minghui Shangguan, Chong Shen, Yuanting Information Theory Combinatorics 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 $C_0$. 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 $d_0$ must satisfy, so that \textit{every} bipartite expander $G$ with vertex expansion ratio $δ$ and \textit{every} linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $Ω(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 $δ>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 $C_0$, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that $d_0=Ω(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 $C_0$ by showing that $δd_0>3$ is sufficient and $δd_0>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. |
| title | When can an expander code correct $Ω(n)$ errors in $O(n)$ time? |
| topic | Information Theory Combinatorics |
| url | https://arxiv.org/abs/2312.16087 |