切比雪夫距离度量下多重置换码的新构造方法

doi:10.3969/j.issn.1001-2400.2018.04.010

Abstract

Abstract:

For the limited-magnitude errors occurring in a flash memory system and the disadvantage that the information rates of rank-modulation permutation codes are not high enough, a simple construction method for regular multipermutation codes that can correct these errors is proposed by using the direct product operation on multipermutation sets which have the same minimum distance under the Chebyshev distance metric. Moreover, by using the projection operation on the known simple regular multipermutation codes, the multipermutation sets with different minimum distances are obtained. Based on the direct product of these multipermutation sets, a generalized construction method for regular multipermutation codes is proposed. Compared with the existing construction methods of multipermutation codes under the Chebyshev distance metric, the proposed construction methods of multipermutation codes based on direct product operation are more intuitive. Some calculation examples are provided to verify the validity of the proposed construction methods.

Key words: rank modulation, multipermutation codes, limited-magnitude errors, Chebyshev distance, direct product

ZHAO Peng;MU Jianjun;JIAO Xiaopeng. New construction methods for multipermutation codes under the Chebyshev distance metric[J].Journal of Xidian University, 2018, 45(4): 51-56.

References

［1］ JIANG A, MATEESCU R, SCHWARTZ M, et al. Rank Modulation for Flash Memories［J］. IEEE Transactions on Information Theory, 2009, 55(6): 2659-2673.
［2］ TAMO I, SCHWARTZ M. Correcting Limited-magnitude Errors in the Rank-modulation Scheme［J］. IEEE Transactions on Information Theory, 2010, 56(6): 2551-2560.
［3］ GABRYS R, YAAKOBI E, FARNOUD F, et al. Codes Correcting Erasures and Deletions for Rank Modulation［J］. IEEE Transactions on Information Theory, 2016, 62(1): 136-150.
［4］ BUZAGLO S, YAAKOBI E. On the Capacity of Constrained Permutation Codes for Rank Modulation［J］. IEEE Transactions on Information Theory, 2016, 62(4): 1649-1666.
［5］ HOLROYD A E. Perfect Snake-in-the-box Codes for Rank Modulation［J］. IEEE Transactions on Information Theory, 2017, 63(1): 104-110.
［6］ FARNOUD HASSANZADEH F, MILENKOVIC O. Multipermutation Codes in the Ulam Metric for Nonvolatile Memories［J］. IEEE Journal on Selected Areas in Communications, 2014, 32(5): 919-932.
［7］ HUCZYNSKA S, MULLEN G L. Frequency Permutation Arrays［J］. Journal of Combinatorial Designs, 2006, 14(6): 463-478.
［8］ GAD E E, YAAKOBI E, JIANG A A, et al. Rank-modulation Rewriting Codes for Flash Memories［C］//Proceedings of the 2013 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2013: 704-708.
［9］ SALA F, GABRYS R, DOLECEK L. Dynamic Threshold Schemes for Multi-level Non-volatile Memories［J］. IEEE Transactions on Communications, 2013, 61(7): 2624-2634.
［10］ BUZAGLO S, YAAKOBI E, ETZION T, et al. Error-correcting Codes for Multipermutations［C］//Proceedings of the 2013 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2013: 724-728.
［11］ BUZAGLO S, YAAKOBI E, ETZION T, et al. Systematic Error-correcting Codes for Permutations and Multipermutations［J］. IEEE Transactions on Information Theory, 2016, 62(6): 3113-3124.
［12］ KONG J, HAGIWARA M. Nonexistence of Perfect Permutation Codes in the Ulam Metric［C］//Proceedings of the 2016 International Symposium on Information Theory and Its Applications. Piscataway: IEEE, 2016: 691-695.
［13］ KONG J, HAGIWARA M. Multipermutation Ulam Sphere Analysis toward Characterizing Maximal Code Size［C］//Proceedings of the 2017 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2017: 1608-1612.
［14］ SHIEH M Z, TSAI S C. Decoding Frequency Permutation Arrays Under Chebyshev Distance［J］. IEEE Transactions on Information Theory, 2010, 56(11): 5730-5737.
［15］ LIU X, DRAPER S C. LP-decodable Multipermutation Codes［J］. IEEE Transactions on Information Theory, 2016, 62(4): 1631-1648.

[1]	HE Yaping,HE Yucheng,ZHOU Lin. Permutation codesable to correct stable and unstable burst erasure errors [J]. Journal of Xidian University, 2021, 48(3): 49-55.
[2]	HAN Hui, MU Jianjun, JIAO Xiaopeng. Coding and decoding algorithms for systematic permutation codes at the Chebyshev distance [J]. Journal of Xidian University, 2018, 45(6): 26-30+98.
[3]	MU Jianjun;ZHAO Peng;JIAO Xiaopeng. Decoding of codes correcting a single translocation error for the cell's level of flash memory [J]. Journal of Xidian University, 2016, 43(6): 51-55+121.

New construction methods for multipermutation codes under the Chebyshev distance metric

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Metrics

Comments

Recommended 10