arXiv:2609.01474 · v3

Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality

首次提交 2026-09-02 00:09

版本更新 2026-11-10 09:02

雷达观测 2026-11-11 11:04

摘要

Codes over graphs store symbols on edges of a complete undirected graph on $n$ vertices with a self-loop at each vertex; erasing a node removes all its incident edges. Extending Yohananov, Efron, and Yaakobi's construction, we obtain binary codes correcting any three node erasures at infinitely many prime lengths $n$, unconditionally, with redundancy $3n-2$, one bit above the graph Singleton bound. The earlier construction has the same redundancy but requires $2$ to be primitive modulo $n$, which is not known for infinitely many primes. We give a deterministic decoder for these triple-node codes using $O(n^2)$ binary operations and construct Singleton-optimal binary triple-node codes at $n=6,8,10,12$. When $2$ is primitive modulo an odd prime $n$, we extend their double- and triple-node codes to binary codes correcting $ρ$ node erasures with redundancy $ρn-(ρ-1)$ for $2\leqρ\leq(n+1)/2$, saving $ρ-1$ bits over the binary symmetric rank-metric construction when $ρ<(n+1)/2$. Over every finite field of size $q$, the node weight of a word is the least number of vertices whose erasure removes its support. We give exact formulas for ball volumes in this node metric and prove that, for fixed $q,t$, the radius-$t$ volume is asymptotic to $\binom nt q^{tn-\binom t2}$ as $n\to\infty$. We obtain existence and covering bounds; for fixed $q,ρ$, we show that linear $ρ$-node-erasure-correcting codes exist with redundancy at most $ρ\log_q n+O_{q,ρ}(1)$ above the graph Singleton bound. Finally, reformulating Yohananov and Yaakobi's criterion, we show that a linear code over any finite field is Singleton-optimal for $ρ$ node erasures if and only if its dual is Singleton-optimal for erasures of the coordinates inside any $n-ρ$ vertices.

作者备注：44 pages