Energy-Time Optimal Decoding Using Expander-Graph LDPC Codes and Mesh Network Architecture
Abstract
Within the Thompson VLSI model, the first energy optimal decoding schemes (up to polylogarithmic factors) that also reach clock cycle lower bounds are constructed. Let N be block length. Then, there is an exponential error scaling function and a binary symmetric channel, such that for all f(N) that scales to zero more slowly than this, there is a decoding scheme for this channel with error probability that scales as O(f(N)) that has number of clock cycles T≤ O(√(−log(f(N)))polylog(N)) and energy E≤ O(N√(−log(f(N)))polylog(N)). This matches fundamental lower bounds up to polylogarithmic factors. The technique uses expander-graph based LDPC codes, a mesh network architecture, and a parallelization technique. The key technical result needed for this is a lemma in graph theory. This lemma is used to show that communication graphs of bounded node degree can be routed through two- and three-dimensional mesh networks without overflowing the memory of any mesh node. Upper bounds are also extended to three dimensions.
Related
- A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding
- Efficient Polynomial-Time Decoding of Simplicial Anticodes with Near-Optimal Performance
- Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes
- Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding
- Instability of mean curvature flow in expander coordinates
BibTeX
@misc{blake2026energytime,
title = {{Energy-Time Optimal Decoding Using Expander-Graph LDPC Codes and Mesh Network Architecture}},
author = {Christopher Blake},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07336},
eprint = {2611.07336},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07336},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Energy-Time Optimal Decoding Using Expander-Graph LDPC Codes and Mesh Network Architecture
AU - Christopher Blake
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07336
UR - https://arxiv.org/abs/2611.07336
AB - Within the Thompson VLSI model, the first energy optimal decoding schemes (up to polylogarithmic factors) that also reach clock cycle lower bounds are constructed. Let N be block length. Then, there is an exponential error scaling function and a binary symmetric channel, such that for all f(N) that scales to zero more slowly than this, there is a decoding scheme for this channel with error probability that scales as O(f(N)) that has number of clock cycles T≤ O(√(−log(f(N)))polylog(N)) and energy E≤ O(N√(−log(f(N)))polylog(N)). This matches fundamental lower bounds up to polylogarithmic factors. The technique uses expander-graph based LDPC codes, a mesh network architecture, and a parallelization technique. The key technical result needed for this is a lemma in graph theory. This lemma is used to show that communication graphs of bounded node degree can be routed through two- and three-dimensional mesh networks without overflowing the memory of any mesh node. Upper bounds are also extended to three dimensions.
ER -