


























We construct explicit algebraic geometry codes built from the Garcia-Stichtenoth function field tower beating the Gilbert-Varshamov bound for alphabet sizes at least 192. Messages are identied with functions in certain Riemann-Roch spaces associated with divisors supported on multiple places. Encoding amounts to evaluating these functions at degree one places. By exploiting algebraic structures particular to the Garcia-Stichtenoth tower, we devise an intricate deterministic ω/2 < 1.19 runtime exponent encoding and 1+ω/2 < 2.19 expected runtime exponent randomized (unique and list) decoding algorithms. Here ω< 2.373 is the matrix multiplication exponent. If ω= 2, as widely believed, the encoding and decoding runtimes are respectively nearly linear and nearly quadratic. Prior to this work, encoding (resp. decoding) time of code families beating the Gilbert-Varshamov bound were quadratic (resp. cubic) or worse.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。