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

doi:10.3969/j.issn.1001-2400.2018.04.010

西安电子科技大学学报

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

赵鹏1;慕建君1,2;焦晓鹏1,2

(1. 西安电子科技大学计算机学院，陕西西安 710071；
2. 重庆邮电大学重庆市/信息产业部计算机网络与通信技术重点实验室，重庆 400065)

收稿日期:2017-09-26 出版日期:2018-08-20 发布日期:2018-09-25
作者简介:赵鹏(1987-)，女，西安电子科技大学博士研究生，E-mail: arpeng1000@126.com
基金资助:
国家自然科学基金资助项目(61471286, 61271004); 重庆市/信息产业部计算机网络与通信技术重点实验室开放基金资助项目(CY-CNCL-2017-03)

New construction methods for multipermutation codes under the Chebyshev distance metric

ZHAO Peng1;MU Jianjun1,2;JIAO Xiaopeng1,2

(1. School of Computer Science and Technology, Xidian Univ., Xian 710071, China;
2. Chongqing Key Lab. of Computer Network and Communication Technology, Chongqing Univ. of Posts and Telecommunications, Chongqing 400065, China)

Received:2017-09-26 Online:2018-08-20 Published:2018-09-25

摘要/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

赵鹏;慕建君;焦晓鹏. 切比雪夫距离度量下多重置换码的新构造方法[J]. 西安电子科技大学学报, 2018, 45(4): 51-56.

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.

参考文献

［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]	何雅萍,贺玉成,周林. 纠正稳定和非稳定突发擦除错误的置换码[J]. 西安电子科技大学学报, 2021, 48(3): 49-55.
[2]	韩辉, 慕建君, 焦晓鹏. 切比雪夫距离下系统置换码的编译码算法[J]. 西安电子科技大学学报, 2018, 45(6): 26-30+98.
[3]	慕建君;赵鹏;焦晓鹏. 一种纠单个闪存单元移位错误码的译码方法[J]. 西安电子科技大学学报, 2016, 43(6): 51-55+121.

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

New construction methods for multipermutation codes under the Chebyshev distance metric

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

Metrics

本文评价

推荐阅读 10