两类多重置换阵列码的构造方法

doi:10.19665/j.issn1001-2400.20240802

西安电子科技大学学报 ›› 2024, Vol. 51 ›› Issue (6): 84-90.doi: 10.19665/j.issn1001-2400.20240802

两类多重置换阵列码的构造方法

王丹¹^,²(), 孙蓉²(), 韩辉¹()

1.西安电子科技大学计算机科学与技术学院,陕西西安 710071
2.西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安 710071

收稿日期:2024-04-24 出版日期:2024-09-05 发布日期:2024-09-05
通讯作者: 孙蓉(1976—),女,副教授,博士,E-mail:rsun@mail.xidian.edu.cn
作者简介:王丹(1996—),女,西安电子科技大学博士研究生,E-mail:wd19960921@126.com;
韩辉(1985—),男,讲师,博士,E-mail:huihan0424@163.com
基金资助:
国家自然科学基金(62371371);中央高校基本科研业务费专项资金资助(ZYTS24091)

Construction of two classes of multi-permutation array codes

WANG Dan¹^,²(), SUN Rong²(), HAN Hui¹()

1. School of Computer Science and Technology,Xidian University,Xi’an 710071,China
2. State Key Laboratory of Integrated Services Networks,Xidian University,Xi’an 710071,China

Received:2024-04-24 Online:2024-09-05 Published:2024-09-05

摘要/Abstract

摘要：

具有高存储密度与良好可靠性的闪存是一种重要的非易失性存储技术。读/写干扰、单元间干扰与电荷泄漏等噪声可能导致闪存数据不能被正确读出而出现删除错误。等级调制方案下置换码/多重置换码等纠错编码技术可以克服闪存中的删除/插入错误。与置换码相比较,多重置换码可以达到更高的信息存储率。近年来,学者们仅仅研究了纠单个或多个交叉插入/删除错误的几类二元码的构造及译码方法。然而,目前没有纠正交叉插入/删除错误的多重置换阵列码的相关研究工作。针对这一问题,利用置换的交织技术与重复码的思想,提出了纠单个交叉删除错误的平衡多重置换阵列码的两个构造方法,而且在其证明中给出了相应的译码方法。第一个构造方法基于置换的奇偶交织技术来确定码字阵列中被删除列的位置,而第二个构造方法基于LEVENSHTEIN置换码来确定码字阵列中被删除列的位置。而且,与第一个构造方法相比较,第二个构造方法得到的平衡多重置换阵列码可以达到更高的码率。通过实例验证了所提出的平衡多重置换阵列码的两个构造及其相应译码方法的正确性。

关键词: 平衡多重置换阵列码, 交叉删除错误, 交织技术, 闪存

Abstract:

The flash memory with a high storage density and good reliability is a dominant nonvolatile memory technology.Such noises as read/write interference,inter-cell interference,and charge leakage may cause deletion errors in flash memory data that cannot be read correctly.Error-correcting coding techniques such as permutation codes/multi-permutation codes under the rank-modulation scheme can overcome deletion/insertion errors.Moreover,multi-permutation codes can achieve a higher information rate compared with permutation codes.In recent years,only the construction and decoding methods of binary codes correcting single or multiple criss-cross insertion/deletion errors have been investigated.However,there are no studies of multi-permutation array codes correcting criss-cross insertion/deletion errors.In order to solve this problem,by using the interleaving technique of permutations and the idea of repetition codes,two constructions of balanced multi-permutation array codes capable of correcting the single criss-cross deletion error are proposed with their decoding methods included in proofs.The first construction is based on the parity interleaving technique of permutations to determine the position of the deleted column in the codeword array,while the second construction is based on the Levenshtein permutation code to determine the position of the deleted column in the codeword array.Moreover,the balanced multi-permutation array codes obtained by the second construction can achieve a higher rate compared with the first construction.The correctness of our constructions and their decoding methods is verified with examples.

Key words: balanced multi-permutation array codes, criss-cross deletion errors, interleaving technique, flash memories

中图分类号:

TN911.22

王丹, 孙蓉, 韩辉. 两类多重置换阵列码的构造方法[J]. 西安电子科技大学学报, 2024, 51(6): 84-90.

WANG Dan, SUN Rong, HAN Hui. Construction of two classes of multi-permutation array codes[J]. Journal of Xidian University, 2024, 51(6): 84-90.

参考文献 22

[1]	FAMOUD F, SKACHEK V, MILENKOVIC O. Error-Correction in Flash Memories via Codes in the Ulam Metric[J]. IEEE Transactions on Information Theory, 2013, 59(5):3003-3020.
[2]	FAMOUD 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.
[3]	JIANG A, MATEESCU R, SCHWARTZ M, et al. Rank Modulation for Flash Memories[J]. IEEE Transactions on Information Theory, 2009, 55(6):2659-2673.
[4]	韩辉, 慕建君, 焦晓鹏, 等. 纠单个相邻对换错误置换码的构造与编译码方法[J]. 西安电子科技大学学报, 2023, 50(3):105-111.
	HAN Hui, MU Jianjun, JIAO Xiaopeng, et al. Construction and Encoding/Decoding Methods of the Permutation Codes Correcting a Single Adjacent Transposition Error[J]. Journal of Xidian University, 2023, 50(3):105-111.
[5]	HAN H, MU JJ, JIAO X P, et al. Codes Correcting a Burst of Deletions for Permutations and Multi-Permutations[J]. IEEE Communications Letters, 2018, 22(10):1968-1971.
[6]	HAN H, MU JJ, HE Y C, et al. Rate-Improved Permutation Codes for Correcting a Single Burst of Deletions[J]. IEEE Communications Letters, 2021, 25(1):49-53.
[7]	HAN H, MU JJ, JIAO X P, et al. Constructions of Multi-Permutation Codes Correcting a Single Burst of Deletions[J]. Designs,Codes and Cryptography, 2023, 91:1923-1934.
[8]	SUN Y B, ZHANG Y W, GE G N. Improved Constructions of Permutation and Multi-Permutation Codes Correcting a Burst of Stable Deletions[J]. IEEE Transactions on Information Theory, 2023, 69(7):4429-4441.
[9]	LEVENSHTEIN V I. On Perfect Codes in Deletion and Insertion Metric[J]. Discrete Mathematics and Applications, 1992, 2(3):241-258.
[10]	VARSHAMOV R R, TENENGOLTS G M. Codes Which Correct Single Asymmetric Errors[J]. Automation and Remote Control, 1965, 26(2):286-290.
[11]	LEVENSHTEIN V I. Binary Codes Capable of Correcting Deletions,Insertions,and Reversals[J]. Soviet Physics Doklady, 1966, 10(8):707-710.
[12]	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.
[13]	SALA F, GABRYS R, DOLECEK L. Deletions in Multipermutations[C]// 2014 IEEE International Symposium on Information Theory. Piscataway:IEEE, 2014:2769-2773.
[14]	ZHAO P, MU J J, JIAO X P. Multi-Permutation Codes Correcting a Predetermined Number of Adjacent Deletions[J]. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences, 2017, E100-A(10):2176-2179.
[15]	CHEE Y M, LING S, NGUYEN T T, et al. Burst-Deletion-Correcting Codes for Permutations and Multipermutations[J]. IEEE Transactions on Information Theory, 2020, 66(2):957-969.
[16]	WANG S, TANG Y, SIMA J, et al. Non-Binary Codes for Correcting a Burst of at Mostt Deletions[J]. IEEE Transactions on Information Theory, 2024, 70(2):964-979.
[17]	WANG S, TANG Y, SIMA J, et al. Permutation Codes for Correcting a Burst of at Mostt Deletions[C]// 2022 58th Annual Allerton Conference on Communication, Control,and Computing(Allerton).Piscataway:IEEE, 2022:1-6.
[18]	HAGIWARA M. Conversion Method from Erasure Codes to Multi-Deletion Error-Correcting Codes for Information in Array Design[C]// 2020 International Symposium on Information Theory and Its Applications(ISITA). Piscataway:IEEE, 2020: 274-278.
[19]	CHEE Y M, HAGIWARA M, KHU V V. Two Dimensional Deletion Correcting Codes and Their Applications[C]// 2021 IEEE International Symposium on Information Theory(ISIT). Piscataway:IEEE, 2021:2792-2797.
[20]	BITAR R, WELTER L, SMAGLOY I, et al. Criss-Cross Insertion and Deletion Correcting Codes[J]. IEEE Transactions on Information Theory, 2021, 67(12):7999-8015.
[21]	WELTER L, BITAR R, WACHTER-ZEH A, et al. Multiple Criss-Cross Insertion and Deletion Correcting Codes[J]. IEEE Transactions on Information Theory, 2022, 68(6):3767-3779.
[22]	LIU S, TJUAWINATA I, XING C. Explicit Construction of q-Ary 2-Deletion Correcting Codes with Low Redundancy[J]. IEEE Transactions on Information Theory, 2024, 70(6):4093-4101.

两类多重置换阵列码的构造方法

Construction of two classes of multi-permutation array codes

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 22

相关文章 4

Metrics

本文评价

推荐阅读 0

[1]	韩辉,慕建君,焦晓鹏,赵展展. 纠单个相邻对换错误置换码构造与编译码方法[J]. 西安电子科技大学学报, 2023, 50(3): 105-111.
[2]	何雅萍,贺玉成,周林. 纠正稳定和非稳定突发擦除错误的置换码[J]. 西安电子科技大学学报, 2021, 48(3): 49-55.
[3]	贺秦禄,边根庆,邵必林,张维琪. 移动闪存的重复数据删除技术[J]. 西安电子科技大学学报, 2020, 47(1): 128-134.
[4]	慕建君;赵鹏;焦晓鹏. 一种纠单个闪存单元移位错误码的译码方法[J]. 西安电子科技大学学报, 2016, 43(6): 51-55+121.