【24h】

Combinatorial Limitations of Average-Radius List Decoding

机译:平均半径列表解码的组合限制

获取原文
获取原文并翻译 | 示例

摘要

We study certain combinatorial aspects of list-decoding, motivated by the exponential gap between the known upper bound (of O(1/γ)) and lower bound (of Ω_p(log(l/γ))) for the list-size needed to list decode up to error fraction p with rate 7 away from capacity, i.e., 1 - h(p) -γ (here ∈ (0, 1/2) and γ > 0). Our main result is the following: We prove that in any binary code C ⊂ {0,1}~n of rate 1 - h(p) -γ, there must exist a set L⊂C of Ω_p(1/γ~(1/2)) codewords such that the average distance of the points in L from their centroid is at most pn. In other words, there must exist Ω_p(1/γ~(1/2)) codewords with low "average radius." The standard notion of list-decoding corresponds to working with the maximum distance of a collection of codewords from a center instead of average distance. The average-radius form is in itself quite natural; for instance, the classical Johnson bound in fact implies average-radius list-decodability. The remaining results concern the standard notion of list-decoding, and help clarify the current state of affairs regarding combinatorial bounds for list-decoding: - We give a short simple proof, over all fixed alphabets, of the above-mentioned Ω_p(log(l/γ)) lower bound. Earlier, this bound followed from a complicated, more general result of Blinovsky. - We show that one cannot improve the Ω_p(log(l/γ)) lower bound via techniques based on identifying the zero-rate regime for list-decoding of constant-weight codes. On a positive note, our Ω_p(1/γ~(1/2)) lower bound for average-radius list-decoding circumvents this barrier. - We exhibit a "reverse connection" between the existence of constant-weight and general codes for list-decoding, showing that the best possible list-size, as a function of the gap γ of the rate to the capacity limit, is the same up to constant factors for both constant-weight codes (whose weight is bounded away from p) and general codes. - We give simple second moment based proofs that w.h.p. a list-size of Ω_p(1/γ) is needed for list-decoding random codes from errors as well as erasures. For random linear codes, the corresponding list-size bounds are Ω_p(1/γ) for errors and exp(Ω_p(1/γ)) for erasures.
机译:我们研究列表解码的某些组合方面,这是由所需的列表大小的已知上限(O(1 /γ)的上限和Ω_p(log(l /γ))的下限之间的指数间隙所驱动的列出解码直至误差分数p的速率,其速率远离容量的比率为7,即1-h(p)-γ(此处∈(0,1/2)和γ> 0)。我们的主要结果如下:我们证明,在速率为1-h(p)-γ的任何二进制代码C⊂{0,1}〜n中,必须存在一个Ω_p(1 /γ〜( 1/2))码字,以使L中的点到它们的质心的平均距离最大为pn。换句话说,必须存在“平均半径”很低的Ω_p(1 /γ〜(1/2))码字。列表解码的标准概念对应于使用一组码字距中心的最大距离而不是平均距离。平均半径形式本身是很自然的。例如,经典约翰逊界实际上意味着平均半径列表可解码性。其余结果与列表解码的标准概念有关,并有助于阐明有关列表解码组合范围的当前状况:-我们在所有固定字母上给出了上述Ω_p(log( l /γ))下限。早些时候,这个界限是由Blinovsky的复杂,更普遍的结果引起的。 -我们证明了无法通过基于识别恒权码列表解码的零速率机制的技术来改善Ω_p(log(l /γ))下限。积极的一点是,我们的平均半径列表解码的Ω_p(1 /γ〜(1/2))下界规避了这一障碍。 -我们展示了恒定权重和用于列表解码的通用代码之间的“反向联系”,表明作为速率到容量限制的间隙γ的函数,最佳列表大小是相同的对于恒定权重代码(权重限制为p)和一般代码,均不得超过恒定因子。 -我们给出了基于第二矩的简单证明为了从错误和擦除中对随机码进行列表解码,需要一个Ω_p(1 /γ)的列表大小。对于随机线性码,相应的列表大小范围对于错误为Ω_p(1 /γ),对于擦除为exp(Ω_p(1 /γ))。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号