Constant-Weight Gray Codes for Local Rank Modulation
Constant-Weight Gray Codes for Local Rank Modulation
复制标题
DOI：
10.1109/tit.2011.2162570
复制
发表时间：
2011-11
影响因子：
2.5
通讯作者：
Eyal En Gad;M. Langberg;Moshe Schwartz;Jehoshua Bruck
中科院分区：
文献类型：
--
作者：
Eyal En Gad;M. Langberg;Moshe Schwartz;Jehoshua Bruck
我们考虑局部秩调制（LRM）方案，其中滑动窗口遍历一系列实值变量会引发一系列排列。 LRM 是排序调制方案的推广，最近被建议作为闪存中存储信息的一种方式。我们研究 LRM 方案的恒重格雷码，以便模拟传统的多级闪存单元，同时保留等级调制的优点。我们提出了一种实用的代码构造，其速率和权重渐近一半长度，从而在相邻单元之间具有渐近最优电荷差。接下来，我们通过专门研究权重为2和3的代码来检验最优代码的存在性。在前一种情况下，我们对代码效率进行了上限，证明不存在这样的渐近最优循环码。相反，对于后一种情况，我们构造渐近最优的代码。我们通过提供循环和循环最优格雷码存在的必要条件来得出结论。
We consider the local rank-modulation (LRM) scheme in which a sliding window going over a sequence of real-valued variables induces a sequence of permutations. LRM is a generalization of the rank-modulation scheme, which has been recently suggested as a way of storing information in flash memory. We study constant-weight Gray codes for the LRM scheme in order to simulate conventional multilevel flash cells while retaining the benefits of rank modulation. We present a practical construction of codes with asymptotically-optimal rate and weight asymptotically half the length, thus having an asymptotically-optimal charge difference between adjacent cells. Next, we turn to examine the existence of optimal codes by specifically studying codes of weight 2 and 3. In the former case, we upper bound the code efficiency, proving that there are no such asymptotically-optimal cyclic codes. In contrast, for the latter case we construct codes which are asymptotically-optimal. We conclude by providing necessary conditions for the existence of cyclic and cyclic optimal Gray codes.