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

doi:10.19665/j.issn1001-2400.20240802

Abstract

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

CLC Number:

TN911.22

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.

References 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)

Like

Knowledge

Abstract

Cite this article

share this article

References 22

Related Articles 1

Metrics

Comments

Recommended 0