← 研踪 PaperTrailarXiv:2611.07336 · v1
Energy-Time Optimal Decoding Using Expander-Graph LDPC Codes and Mesh Network Architecture
首次提交 2026-11-05 10:21
版本更新 2026-11-05 10:21
雷达观测 2026-11-06 10:04
摘要
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\le O(\sqrt{-\log(f(N)})\text{polylog}(N))$ and energy $E\le O(N\sqrt{-\log(f(N))}\text{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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 10:21 · 最新观测版本
Energy-Time Optimal Decoding Using Expander-Graph LDPC Codes and Mesh Network Architecture
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\le O(\sqrt{-\log(f(N)})\text{polylog}(N))$ and energy $E\le O(N\sqrt{-\log(f(N))}\text{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.
查看此版本解读 →查看此版本原文 ↗