On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes

Philippe Gaborit; Gilles Zémor

首页> 外文期刊>IEEE Transactions on Information Theory >On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes

【24h】

On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes

机译：等级码的解码难度和最小距离问题

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We give a randomized reduction for the Rank Syndrome Decoding problem and Rank Minimum Distance problem for rank codes over extension fields. Our results are based on embedding linear codes in the Hamming space into linear codes over an extension field equipped with the rank metric. We prove that if any of the previous problems for the rank metric is in ZPP = RP ∩ coRP, then we would have NP = ZPP. We also give complexity results for the respective rank metric approximation problems.

机译：对于扩展域上的秩码，我们对秩综合症解码问题和秩最小距离问题进行了随机归约。我们的结果基于将汉明空间中的线性代码嵌入到配备有秩度量的扩展字段上的线性代码中。我们证明，如果先前的等级度量问题是ZPP = RP∩coRP，那么我们将NP = ZPP。我们还给出了各个等级度量近似问题的复杂度结果。

著录项

来源
《IEEE Transactions on Information Theory》 |2016年第12期|7245-7252|共8页
作者
Philippe Gaborit; Gilles Zémor;
展开▼
作者单位

XLIM Research Institute, Université de Limoges, Limoges, France;

Institut de Mathématiques de Bordeaux, Université de Bordeaux, Talence, France;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类
关键词
Decoding; Measurement; Cryptography; Complexity theory; Hamming distance; Lattices;

机译：解码;测量;密码学;复杂度理论;汉明距离;格;

相似文献

外文文献
中文文献
专利

1. On the Decoder Error Probability of Bounded Rank-Distance Decoders for Maximum RankDistance Codes [J] . Gadouleau M., Yan Z. IEEE Transactions on Information Theory . 2008,第7期

机译：关于最大秩距离代码的有界秩距离解码器的解码器错误概率
2. Efficient Generalized Minimum-distance Decoders of Reed-Solomon Codes [J] . Jiangli Zhu, Xinmiao Zhang Journal of signal processing systems for signal, image, and video technology . 2012,第3期

机译：里德-所罗门码的高效通用最小距离解码器
3. Use of Grobner bases to decode binary cyclic codes up to the true minimum distance [J] . Xuemin Chen, Reed I.S. IEEE Transactions on Information Theory . 1994,第5期

机译：使用Grobner基解码二进制循环码，直到真正的最小距离
4. On the decoder error probability of bounded rank distance decoders for rank metric codes [C] . Gadouleau M., Zhiyuan Yan Information Theory Workshop, 2009. ITW 2009 . 2009

机译：关于秩度量码的有界秩距离解码器的解码器错误概率
5. Rethinking the minimum distance: Channels with varying sampling rate and interative decoding of LDPC codes. [D] . Dolecek, Lara. 2007

机译：重新考虑最小距离：具有不同采样率的信道和LDPC码的中间解码。
6. Rank Order Coding: a Retinal Information Decoding Strategy Revealed by Large-Scale Multielectrode Array Retinal Recordings [O] . Geoffrey Portelli, John M. Barrett, Gerrit Hilgen, 2016

机译：等级顺序编码：大型多电极阵列视网膜记录揭示的视网膜信息解码策略
7. On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes [O] . Gaborit, Philippe, Zémor, Gilles 2016

机译：等级码的解码难度和最小距离问题
8. On the Minimum Distance Structure of Cyclic Codes and Decoding Beyond the Bch Bound [R] . Hartmann, C. R. P. 1970

机译：关于循环码的最小距离结构和超出Bch界限的解码

On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes

摘要

著录项

相似文献

相关主题

期刊订阅