Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes
Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes
复制标题
适用于高噪声和高速率状态的有效可解码插入/删除代码
DOI：
10.1109/isit.2016.7541373
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ray Li
中科院分区：
文献类型：
--
作者：
V. Guruswami;Ray Li
这项工作构建了可以在三个参数设置中恒定的最坏情况插入和删除误差的恒定分数有效解码的代码：（i）速率接近1的二进制代码； （ii）误差分数的恒定速率的代码接近固定字母大小的1； （iii）在大小k的字母上使用恒定速率代码接近误差分数（k -1）/（k + 1）。当错误仅限于缺失时，最近构建了这些制度中每一个中有效可解码的代码。我们通过构建在插入/删除措施中有效解码的类似代码来完成图片。
This work constructs codes that are efficiently decodable from a constant fraction of worst-case insertion and deletion errors in three parameter settings: (i) Binary codes with rate approaching 1; (ii) Codes with constant rate for error fraction approaching 1 over fixed alphabet size; and (iii) Constant rate codes over an alphabet of size k for error fraction approaching (k - 1)/(k + 1). When errors are constrained to deletions alone, efficiently decodable codes in each of these regimes were constructed recently. We complete the picture by constructing similar codes that are efficiently decodable in the insertion/deletion regime.