• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex
【24h】

Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved Codex

机译：里德-穆勒码通过交错式码本的高效多点本地解码

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity. In this paper, we focus on Reed-Muller codes with usual parameter regime, namely, the total degree of evaluation polynomials is d = Theta(q), where q is the code alphabet size (in fact, d can be as big as q/4 in our setting). By introducing a novel variation of codex, i.e., interleaved codex (the concept of codex has been used for arithmetic secret sharing), we are able to locally recover arbitrarily large number k of coordinates of a Reed-Muller code simultaneously with error probability exp(-Omega(k)) at the cost of querying merely O(q(2)k) coordinates. It turns out that our local decoding of Reed-Muller codes shows (perhaps surprisingly) that accessing k locations is in fact cheaper than repeating the procedure for accessing a single location for k times. Precisely speaking, to get the same success probability by repeating the local decoding algorithm of a single coordinate, one has to query Omega(qk(2)) coordinates. Thus, the query complexity of our local decoding is smaller for k = Omega (q). If we impose the same query complexity constraint on both algorithm, our local decoding algorithm yields smaller error probability when k = Omega (q(q)). In addition, our local decoding is efficient, i.e., the decoding complexity is Poly(k, q). Construction of an interleaved codex is based on concatenation of a codex with a multiplication friendly pair, while the main tool to realize codex is based on algebraic function fields (or more precisely, algebraic geometry codes).
机译：里德·穆勒（Reed-Muller）码是本地可纠正码的最重要类别。目前，对里德-穆勒码的本地解码是基于对直线或二次曲线的解码以恢复一个坐标。为了同时恢复多个坐标，幼稚的方法是重复本地解码以恢复单个坐标。该解码算法可能更昂贵，即要求更高的查询复杂度。在本文中，我们着眼于具有通常参数范围的里德穆勒码，即，评估多项式的​​总度为d = Theta（q），其中q是代码字母的大小（实际上，d可以和q一样大）。 / 4）。通过引入一种新的编解码器变体，即交错编解码器（编解码器的概念已用于算术秘密共享），我们能够以错误概率exp（）同时本地恢复任意数量的Reed-Muller码坐标。 -Omega（k）），其代价是仅查询O（q（2）k）坐标。事实证明，我们对Reed-Muller码的本地解码显示（也许令人惊讶），实际上，访问k个位置实际上要比重复访问k个位置的过程便宜。准确地说，要通过重复单个坐标的局部解码算法来获得相同的成功概率，必须查询Omega（qk（2））坐标。因此，对于k = Omega（q），我们本地解码的查询复杂度较小。如果我们对两种算法施加相同的查询复杂性约束，则当k = Omega（q（q））时，我们的本地解码算法会产生较小的错误概率。此外，我们的本地解码效率很高，即解码复杂度为Poly（k，q）。交错式编解码器的构造是基于一个具有乘法友好对的编解码器的级联，而实现编解码器的主要工具是基于代数函数域（或更精确地说，是代数几何代码）。

著录项

  • 来源
    《IEEE Transactions on Information Theory》 |2020年第1期|263-272|共10页
  • 作者

  • 作者单位

    CWI NL-1098 XG Amsterdam Netherlands|Leiden Univ Math Inst NL-2333 CA Leiden Netherlands;

    Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China;

    CWI NL-1098 XG Amsterdam Netherlands;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Block codes; Reed-Muller codes; Local decoding;

    机译：分组代码;里德-穆勒码本地解码;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号