纠正稳定和非稳定突发擦除错误的置换码

doi:10.19665/j.issn1001-2400.2021.03.006

西安电子科技大学学报 ›› 2021, Vol. 48 ›› Issue (3): 49-55.doi: 10.19665/j.issn1001-2400.2021.03.006

• 信息与通信工程&机械工程 • 上一篇下一篇

纠正稳定和非稳定突发擦除错误的置换码

何雅萍¹(),贺玉成^1,²(),周林^1,²()

1.华侨大学厦门市移动多媒体通信重点实验室,福建厦门 361021
2.西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安 710071

收稿日期:2020-12-14 出版日期:2021-06-20 发布日期:2021-07-05
通讯作者: 贺玉成
作者简介:何雅萍(1995—),女,华侨大学硕士研究生,E-mail:yaping_he@hqu.edu.cn|周林(1982—),男,副教授,博士, E-mail:linzhou@hqu.edu.cn
基金资助:
国家自然科学基金(61302095);福建省自然科学基金(2018J01096);泉州市科技计划(2018C108R);华侨大学研究生科研创新基金资助项目(17013082027)

Permutation codesable to correct stable and unstable burst erasure errors

HE Yaping¹(),HE Yucheng^1,²(),ZHOU Lin^1,²()

1. Xiamen Key Laboratory of Mobile Multimedia Communications,Huaqiao Univesity,Xiamen 361021,China
2. State Key Laboratory of Integrated Services Networks,Xidian Univesity,Xi’an 710071,China

Received:2020-12-14 Online:2021-06-20 Published:2021-07-05
Contact: Yucheng HE

摘要/Abstract

摘要：

为了提高闪存存储的可靠性,利用置换来表示闪存单元电荷大小的等级调制方案。基于置换群理论的纠错码可纠正采用等级调制方案存储引发的多种特殊错误类型。当闪存单元被破坏而无法正确读出存储电荷值时,可能导致相应位置发生擦除错误或删除错误。针对闪存单元等级调制下置换码发生突发擦除错误的稳定性问题,基于纠正单个删除错误的LEVENSHTEIN置换码的构造方法,结合置换交织技术,提出了一种新的置换码构造方法,可分别纠正单个稳定的突发擦除错误和单个非稳定的突发擦除错误,并给出了两种错误相应的译码方法。通过实例验证了构造方法及其译码方法的有效性。

关键词: 置换码, 闪存, 等级调制, 突发擦除错误

Abstract:

In order to improve the reliability of flash memories,permutation is used to represent the rank modulation scheme of the flash cell charge.Error-correcting codes based on permutation groups can correct a variety of special error types that are caused by the rank modulation scheme.When a flash memory cell is damaged and the stored charge value cannot be read correctly,an erase error or a delete error may occur in the corresponding position.Aiming at the problem of the stability of burst erasure errors in rank modulation of the flash memory,a new construction of permutation codes combined with the permutation interleaving technique is proposed by the existing Levenshtein permutation code that can correct a single deletion error.The proposed construction can correct a single stable burst erasure and a single unstable burst erasure,respectively.Two corresponding decoding methods are presented in the proof of the proposed construction.The code construction and the decoding methods are validated with examples.

Key words: permutation code, flash memory, rank modulation, burst erasure errors

中图分类号:

TN911.22

何雅萍,贺玉成,周林. 纠正稳定和非稳定突发擦除错误的置换码[J]. 西安电子科技大学学报, 2021, 48(3): 49-55.

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.

图/表 3

参考文献 16

[1]	JIANG A, SCHWARTZ M, BRUCK J. Correcting Charge-constrained Errors in the Rank-modulation Scheme[J]. IEEE Transactions on Information Theory, 2010,56(5):2112-2120. doi: 10.1109/TIT.2010.2043764
[2]	KOVACEVIC M, TAN V Y F. Coding for the Permutation Channel with Insertions,Deletions,Substitutions,and Erasures[C]// Proceedings of the 2017 IEEE International Symposium on Information Theory.Piscataway:IEEE, 2017: 1933-1937.
[3]	慕建君, 赵鹏, 焦晓鹏. 一种纠单个闪存单元移位错误码的译码方法[J]. 西安电子科技大学学报, 2016,43(6):51-55.
	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.
[4]	GABRYS R, YAAKOBI E, MILENKOVIC O. Codes in theDamerau Distance for Deletion and Adjacent Transposition Correction[J]. IEEE Transactions on Information Theory, 2018,64(4):2550-2570. doi: 10.1109/TIT.2017.2778143
[5]	JIANG A, MATEESCU R, SCHWARTZ M, et al. Rank Modulation for Flash Memories[J]. IEEE Transactions on Information Theory, 2009,55(6):2659-2673. doi: 10.1109/TIT.2009.2018336
[6]	韩辉, 慕建君, 焦晓鹏. 切比雪夫距离下系统置换码的编译码算法[J]. 西安电子科技大学学报, 2018,45(6):26-30.
	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.
[7]	HAN H, MU J, HE Y C, et al. CosetPartitioning Construction of Systematic Permutation Codes Under the Chebyshev Metric[J]. IEEE Transactions on Communications, 2019,67(6):3842-3851. doi: 10.1109/TCOMM.26
[8]	CHEE Y M, VU V K, ZHANG X. Permutation Codes Correcting a Single Burst Deletion I:Unstable Deletions[C]// Proceedings of the 2015 IEEE International Symposium on Information Theory.Piscataway:IEEE, 2015: 1741-1745.
[9]	LEVENSHTEIN V I. On Perfect Codes in Deletion and Insertion Metric[J]. Discrete Mathematics and Applications, 1992,2(3):241-258.
[10]	GABRYS R, YAAKOBI E, FAMOUD F, et al. Codes Correcting Erasures and Deletions for Rank Modulation[J]. IEEE Transactions on Information Theory, 2016,62(1):136-150. doi: 10.1109/TIT.2015.2493147
[11]	CHEE Y M, LING S, NGUYEN T T, et al. Permutation Codes Correcting a Single Burst Deletion II:Stable Deletions[C]// Proceedings of the 2017 IEEE International Symposium on Information Theory.Piscataway:IEEE, 2017: 2688-2692.
[12]	SALA F, GABRYS R, DOLECEK L. Deletions in Multipermutations[C]// Proceedings of the 2014 IEEE International Symposium on Information Theory.Piscataway:IEEE, 2014: 2769-2773.
[13]	HAN H, MU J, JIAO X, et al. Codes Correcting a Burst of Deletions for Permutations and Multi-permutations[J]. IEEE Communications Letters, 2018,22(10):1968-1971. doi: 10.1109/LCOMM.2018.2859962
[14]	MU J, HAN H, HE Y C, et al. Multi-permutation Codes Correcting a Single Burst Unstable Erasure[J]. IEEE Communications Letters, 2019,23(4):572-575. doi: 10.1109/COML.4234
[15]	ZHAO P, MU J, JIAO X. Multipermutation Codes Correcting a Predetermined Number of Adjacent Deletions[J]. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences, 2017,100(10):2176-2179.
[16]	ZHAO P, MU J, HE Y, et al. Multipermutation Codes Correcting aBurst of Deletions[J]. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences, 2018,101(2):535-538.

纠正稳定和非稳定突发擦除错误的置换码

Permutation codesable to correct stable and unstable burst erasure errors

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 16

相关文章 4

Metrics

本文评价

推荐阅读 10

[1]	贺秦禄,边根庆,邵必林,张维琪. 移动闪存的重复数据删除技术[J]. 西安电子科技大学学报, 2020, 47(1): 128-134.
[2]	韩辉, 慕建君, 焦晓鹏. 切比雪夫距离下系统置换码的编译码算法[J]. 西安电子科技大学学报, 2018, 45(6): 26-30+98.
[3]	赵鹏;慕建君;焦晓鹏. 切比雪夫距离度量下多重置换码的新构造方法[J]. 西安电子科技大学学报, 2018, 45(4): 51-56.
[4]	慕建君;赵鹏;焦晓鹏. 一种纠单个闪存单元移位错误码的译码方法[J]. 西安电子科技大学学报, 2016, 43(6): 51-55+121.