Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Applicable Algebra in Engineering Communication and Computing

On Tanner Codes: Minimum Distance and Decoding

Heeralal Janwa, Arbind Kumar Lal

Published Feb 1, 2003• 25 citations
Publisher
DOI
10.1007/s00200-003-0098-4

Related papers

A Comparison of Minimum Distance Bounds on Tanner/Expander Codes

H. L. Janwa, A. K. Lal

•Oct 3, 2001•0 citations

On tightness of Tanner's lower bound for the minimum distance of regular LDPC codes

Tomoharu Shibuya

•Jan 1, 2002•0 citations

Generalized minimum distance iterative decoding of Tanner codes

Saejoon Kim

In this letter, we present a linear-time decoding algorithm for Tanner codes that can correct errors up to close to half the minimum distance of the code. The algorithm is a simple generalization to the iterative decoding algorithm of expander codes proposed by Skachek and Roth (2003).

IEEE Communications Letters•Aug 1, 2005•1 citation

Improved Decoding of Tanner Codes

Zhaienhe Zhou, Zeyu Guo

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$\delta d_{0}>2$, corrects up to$\alpha n$errors for a Tanner code$T\left(G, C_{0}\right)$, where$G$is a ($c, d, \alpha, \delta$) bipartite expander with$n$left vertices, and$C_{0} \subseteq \mathbb{F}_{2}^{d}$is a linear inner code with minimum distance$d_{0}$. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which required$\delta d_{0}>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$\alpha n$, compared with the previous radius of$\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} 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\left(G, C_{0}\right)$is approximately$f_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha n$, where$f_{\delta}(\cdot)$is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from$\alpha n$to approximately$f_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha n$.

arXiv:2501.12293•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•2 citations

An Improvement to Generalized-Minimum-Distance Decoding

Steven S. Pietrobon, Robert Huijie Deng, A. Lafanechere +1 more

•Jan 1, 1991•0 citations

Soft-Decision Minimum-Distance Decoding

Patrick Guy Farrell

Springer eBooks•Jan 1, 1978•2 citations
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\delta d_{0}>2δd0​>2, corrects up toαn\alpha nαnerrors for a Tanner codeT(G,C0)T\left(G, C_{0}\right)T(G,C0​), whereGGGis a (c,d,α,δc, d, \alpha, \deltac,d,α,δ) bipartite expander withnnnleft vertices, andC0⊆F2dC_{0} \subseteq \mathbb{F}_{2}^{d}C0​⊆F2d​is a linear inner code with minimum distanced0d_{0}d0​. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which requiredδd0>3\delta d_{0}>3δ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\alpha nαn, compared with the previous radius of2αd0(1+0.5cδ)n\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} nd0​(1+0.5cδ)2α​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 codeT(G,C0)T\left(G, C_{0}\right)T(G,C0​)is approximatelyfδ−1(1d0)αnf_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha nfδ−1​(d0​1​)αn, wherefδ(⋅)f_{\delta}(\cdot)fδ​(⋅)is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms fromαn\alpha nαnto approximatelyfδ−1(2d0)αnf_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha nfδ−1​(d0​2​)αn.