Polynomial time codes enable efficient symbol recovery from compressed data
Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes
Information Theory
Summary
Random access codes compress information but still let you recover any piece you want better than random guessing. The authors clarify what makes such codes good when data grows large and show how to build them efficiently. They use special linear codes that let you decode parts of compressed data with a guaranteed success rate. Their constructions work well for large data and come with practical algorithms to create these codes.
What this means in practice
- •For data storage engineers: Design storage systems that efficiently compress data while allowing fast partial data recovery with high accuracy using polynomial-time constructed codes.
- •For communication protocol developers: Implement communication protocols that transmit compressed messages enabling reliable retrieval of requested symbols using efficient RAC constructions.
Authors
Ruho Kondo, Yota Maeda
Abstract
Random access codes (RACs) encode a $q$-ary input string into fewer $q$-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value $1/q$. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an $[n,k,d]_q$ linear code with $d\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from $q$-ary Hamming codes and the trivial $(1,1)_q$-RAC yields asymptotically good RAC families at every prescribed RAC rate $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.