纠单个相邻对换错误置换码构造与编译码方法

doi:10.19665/j.issn1001-2400.2023.03.010

Abstract

Abstract:

The rank modulation scheme is an encoding method that uses permutations to represent information for efficiently writing and storing data in flash memory storage.In this setup,the information is represented by the relative ranking but not the absolute value of the cell charge levels.Therefore,rank modulation codes can be constructed on permutations for alleviating the problems of cell over-injection and the adjacent transposition errors caused by charge leakage.Thus,permutation codes in the rank modulation scheme can improve the reliability of flash memory systems.However,for the multi-level flash memory systems,the existing rank-modulated permutation codes that correct a single adjacent transposition error lack effective coding and decoding algorithms.To solve this problem,a construction method for permutation codes correcting a single adjacent transposition error is proposed under the Kendall τ-distance metric by interleaving two kinds of permutation codes on the partitioned block set of the permutation symbol set.Then,an encoding algorithm for this kind of permutation codes is proposed by using unranking mapping and the interleaving technology of permutation codes.At the same time,an effective decoding algorithm for this kind of permutation codes is proposed by using ranking mapping of permutations.The proposed permutation codes have a simple structure.In addition,the effectiveness of the proposed construction method and its encoding/decoding algorithm is verified by some computational examples.

Key words: rank modulation, permutation codes, adjacent transposition errors, Kendall τ-distance, interleaving technique

CLC Number:

TP301.6

HAN Hui,MU Jianjun,JIAO Xiaopeng,ZHAO Zhanzhan. Construction and encoding/decoding methods for the permutation codes correcting a single adjacent transposition error[J].Journal of Xidian University, 2023, 50(3): 105-111.

Figures/Tables 1

References 18

[1]	CAI K, CHEE Y M, GABRYS R, et al. Correcting a Single Indel/Edit for DNA-Based Data Storage:Linear-Time Encoders and Order-Optimality[J]. IEEE Transactions on Information Theory, 2021, 67(6) :3438-3451. doi: 10.1109/TIT.2021.3049627
[2]	WEI H, SCHWARTZ M. Improved Coding over Sets for DNA-Based Data Storage[J]. IEEE Transactions on Information Theory, 2022, 68(1):118-129. doi: 10.1109/TIT.2021.3119584
[3]	GABRYS R, GURUSWANI V, RIBEIRO J, et al. Beyond Single-Deletion Correcting Codes:Substitutions and Transpositions (2021)[J/OL].[2021-12-18]. https://arxiv.org/pdf/2112.09971.pdf.
[4]	SIMA J, BRUCK J. On Optimal k-Deletion Correcting Codes[J]. IEEE Transactions on Information Theory, 2021, 67(6):3360-3375. doi: 10.1109/TIT.2020.3028702
[5]	HAN H, MU J, HE Y, et al. Rate-Improved Permutation Codes for Correcting a Single Burst of Deletions[J]. IEEE Communications Letters, 2021, 25(1):49-53. doi: 10.1109/COML.4234
[6]	BEERI N, SCHWARTZ M. Improved Rank-Modulation Codes for DNA Storage with Shotgun Sequencing[J]. IEEE Transactions on Information Theory, 2022, 68(6):3719-3730. doi: 10.1109/TIT.2022.3152392
[7]	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
[8]	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. doi: 10.1109/TIT.2015.2493147
[9]	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. doi: 10.1109/TIT.2016.2519400
[10]	HOLROYD A E. Perfect Snake-in-the-Box Codes for Rank Modulation[J]. IEEE Transactions on Information Theory, 2017, 63(1):104-110. doi: 10.1109/TIT.2016.2620160
[11]	FARNOUD 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. doi: 10.1109/JSAC.2014.140512
[12]	何雅萍, 贺玉成, 周林. 纠正稳定和非稳定突发擦除错误的置换码[J]. 西安电子科技大学学报, 2021, 48(3):49-55.
	HE Yaping, HE Yucheng, ZHOU Lin. Permutation Codes Able to Correct Stable and Unstable Burst Erasure Errors[J]. Journal of Xidian University, 2021, 48(3):49-55.
[13]	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
[14]	BARG A, MAZUMDAR A. Codes in Permutations and Error Correction for Rank Modulation[J]. IEEE Transactions on Information Theory, 2010, 56(7):3158-3165. doi: 10.1109/TIT.2010.2048455
[15]	MAZUMDAR A, BARG A, ZÉMOR G. Constructions of Rank Modulation Codes[J]. IEEE Transactions on Information Theory, 2013, 59(2):1018-1029. doi: 10.1109/TIT.2012.2221121
[16]	BUZAGLO S, ETZION T. Bounds on the Size of Permutation Codes with the Kendall τMetric[J]. IEEE Transactions on Information Theory, 2015, 61(6):3241-3250. doi: 10.1109/TIT.2015.2424701
[17]	FARNOUD 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. doi: 10.1109/TIT.2013.2239700
[18]	MYROVLD W, RUSKEY F. Ranking and Unranking Permutations in Linear Time[J]. Information Processing Letters, 2001, 79(6):281-284. doi: 10.1016/S0020-0190(01)00141-7

r	0	1	2	3	4	5	6	7
π	(2,3,4,1)	(3,2,4,1)	(3,4,2,1)	(4,3,2,1)	(2,4,3,1)	(4,2,3,1)	(4,3,1,2)	(3,4,1,2)
r	8	9	10	11	12	13	14	15
π	(3,1,4,2)	(1,3,4,2)	(4,1,3,2)	(1,4,3,2)	(2,4,1,3)	(4,2,1,3)	(4,1,2,3)	(1,4,2,3)
r	16	17	18	19	20	21	22	23
π	(2,1,4,3)	(1,2,4,3)	(2,3,1,4)	(3,2,1,4)	(3,1,2,4)	(1,3,2,4)	(2,1,3,4)	(1,2,3,4)

Construction and encoding/decoding methods for the permutation codes correcting a single adjacent transposition error

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 18

Related Articles 4

Metrics

Comments

Recommended 10

[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]	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.
[4]	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.