Constructions of Rank Modulation Codes
Constructions of Rank Modulation Codes
复制标题
DOI：
10.1109/tit.2012.2221121
复制
发表时间：
2013-02-01
影响因子：
2.5
通讯作者：
Zemor, Gilles
中科院分区：
文献类型：
--
作者：
Mazumdar, Arya;Barg, Alexander;Zemor, Gilles
秩调制是一种对信息进行编码以校正闪存设备中的错误以及传输线中的脉冲噪声的方式。建模秩调制涉及构建配备Kendall tau距离的排列空间的包装。作为我们的主要结果集，我们提出了几个一般结构的代码排列，涵盖了广泛的代码参数。特别是，我们展示了一些方法，可以修改传统的纠错码，以纠正错误的肯德尔空间。我们的建设是非渐近的，并提供简单的编码和解码算法，基本上相同的复杂性，需要纠正错误的汉明度量。作为一个例子，从二进制Bose-Chaudhuri-Hocquenghem码，我们获得了在n个存储器单元中校正t个肯德尔错误的码，其支持n的阶数！（log（2）n！）(t)消息，对于任何常数t = 1，2，....我们给出了许多具有特定参数的秩调制码的例子。转向渐近分析，我们构造了秩调制码的家族，这些秩调制码纠正了从Theta（n）到Theta（n（2））以不同速率随n增长的许多错误。我们的一个构造产生了一个家庭的秩调制码的消息的数量和可纠正的肯德尔错误的数量之间的权衡接近最佳缩放率。
Rank modulation is a way of encoding information to correct errors in flash memory devices as well as impulse noise in transmission lines. Modeling rank modulation involves construction of packings of the space of permutations equipped with the Kendall tau distance. As our main set of results, we present several general constructions of codes in permutations that cover a broad range of code parameters. In particular, we show a number of ways in which conventional error-correcting codes can be modified to correct errors in the Kendall space. Our constructions are nonasymptotic and afford simple encoding and decoding algorithms of essentially the same complexity as required to correct errors in the Hamming metric. As an example, from binary Bose-Chaudhuri-Hocquenghem codes, we obtain codes correcting t Kendall errors in n memory cells that support the order of n!/(log(2) n!)(t) messages, for any constant t = 1, 2, .... We give many examples of rank modulation codes with specific parameters. Turning to asymptotic analysis, we construct families of rank modulation codes that correct a number of errors that grows with n at varying rates, from Theta(n) to Theta(n(2)). One of our constructions gives rise to a family of rank modulation codes for which the tradeoff between the number of messages and the number of correctable Kendall errors approaches the optimal scaling rate.