首页> 外文会议>Computing and combinatorics >Limits to List Decoding Random Codes
【24h】

Limits to List Decoding Random Codes

机译:列表解码随机码的限制

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

摘要

It has been known since [Zyablov and Pinsker 1982] that a random q-ary code of rate 1 - H_q(ρ)- ε (where 0 < p <1-1/q, ε > 0 and H_q(·) is the q-ary entropy function) with high probability is a (ρ, 1/ε)-list decodable code. (That is, every Hamming ball of radius at most pn has at most 1/ε codewords in it.) In this paper we prove the "converse" result. In particular, we prove that for every 0 < ρ < 1-1/q, a random code of rate 1 - H_q(ρ) - ε, with high probability, is not a (ρ, L)-list decodable code for any L ≤ c/ε, where c is a constant that depends only on ρ and q. We also prove a similar lower bound for random linear codes.
机译:从[Zyablov and Pinsker 1982]开始,速率为1-H_q(ρ)-ε的随机q元代码(其中0

0和H_q(·)是概率较高的q元熵函数是(ρ,1 /ε)列表可编码的代码。 (也就是说,每个半径最大为pn的汉明球中最多具有1 /ε个码字。)在本文中,我们证明了“相反”的结果。尤其是,我们证明,对于每一个0 <ρ<1-1 / q,速率为1-H_q(ρ)-ε的随机码的概率很高,对于任何一个都不是(ρ,L)列表可编码的代码L≤c /ε,其中c是仅取决于ρ和q的常数。我们还证明了随机线性代码的相似下限。

著录项

  • 来源
    《Computing and combinatorics》|2009年|27-36|共10页
  • 会议地点 Niagara Falls NY(US);Niagara Falls NY(US);Niagara Falls NY(US)
  • 作者

    Atri Rudra;

  • 作者单位

    Department of Computer Science and Engineering, University at Buffalo, SUNY, Buffalo, NY, 14620;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算技术、计算机技术;
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号