Improved Decoding of Tanner Codes Article Swipe

MAKE IMPACT

Zeyu Guo , Zhongliang Zhou · YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2501.12293

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 $ δd_0 > 2 $, corrects up to $ αn $ errors for a Tanner code $ T(G, C_0) $, where $ G $ is a $ (c, d, α, δ) $-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 $ δ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 $ αn $, compared with the previous radius of $ \frac{2α}{d_0(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,C_0)$ is approximately $f_δ^{-1} \left( \frac{1}{d_0} \right) αn $, where $ f_δ(\cdot) $ is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from $αn$ to approximately $f_δ^{-1}\left(\frac{2}{d_0}\right)αn$.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2501.12293

PDF

https://arxiv.org/pdf/2501.12293

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4406755345

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4406755345

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2501.12293

Digital Object Identifier

Title

Improved Decoding of Tanner Codes

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2025

Year of publication

Publication date

2025-01-21

Full publication date if available

Authors

Zeyu Guo, Zhongliang Zhou

List of authors in order

Landing page

https://arxiv.org/abs/2501.12293

Publisher landing page

PDF URL

https://arxiv.org/pdf/2501.12293

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2501.12293

Direct OA link when available

Concepts

Decoding methods, Computer science, Telecommunications

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload