An Improvement on the Gilbert–Varshamov Bound for Permutation Codes
An Improvement on the Gilbert–Varshamov Bound for Permutation Codes
复制标题
DOI：
10.1109/tit.2013.2237945
复制
发表时间：
2013-05
影响因子：
2.5
通讯作者：
Fei Gao;Yiting Yang;G. Ge
中科院分区：
文献类型：
--
作者：
Fei Gao;Yiting Yang;G. Ge
排列码在电力线通信、分组密码和多级闪存模型中已经被证明是有用的。这种代码的构建是非常困难的。事实上，唯一已知的一般下界是Gilbert-Varshamov型界。在本文中，我们建立了置换码与某些图中的独立集之间的联系。使用的连接，我们改善Gilbert-Varshamov界渐近的一个因子log（n），当代码长度n趋于无穷大。
Permutation codes have been shown to be useful in power line communications, block ciphers, and multilevel flash memory models. Construction of such codes is extremely difficult. In fact, the only general lower bound known is the Gilbert-Varshamov type bound. In this paper, we establish a connection between permutation codes and independent sets in certain graphs. Using the connection, we improve the Gilbert-Varshamov bound asymptotically by a factor log(n), when the code length n goes to infinity.