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

doi:10.19665/j.issn1001-2400.2023.03.010

西安电子科技大学学报 ›› 2023, Vol. 50 ›› Issue (3): 105-111.doi: 10.19665/j.issn1001-2400.2023.03.010

• 计算机科学与技术 & 网络空间安全 • 上一篇下一篇

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

韩辉^1,²(),慕建君^1,²(),焦晓鹏¹(),赵展展¹()

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

收稿日期:2022-07-28 出版日期:2023-06-20 发布日期:2023-10-13
通讯作者: 慕建君
作者简介:韩辉(1985—),男,讲师,E-mail:huihan0424@163.com；|焦晓鹏(1984—),男,教授,E-mail:jiaozi1216@126.com；|赵展展(1993—),女,西安电子科技大学博士研究生,E-mail:1983440957@qq.com
基金资助:
国家自然科学基金(62001362);国家自然科学基金(61977051);国家自然科学基金(61971322);重庆市/信息产业部计算机网络与通信技术重点实验室开放基金(CY-CNCL-2021-01);中央高校基本科研业务费专项资金(XJS220310);中国博士后科学基金(2020M683427)

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

HAN Hui^1,²(),MU Jianjun^1,²(),JIAO Xiaopeng¹(),ZHAO Zhanzhan¹()

1. School of Computer Science and Technology,Xidian University,Xi’an 710071,China
2. Chongqing Key Lab of Computer Network and Communication Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China

Received:2022-07-28 Online:2023-06-20 Published:2023-10-13
Contact: Jianjun MU

摘要/Abstract

摘要：

等级调制方案是一种利用置换表示信息的编码方法,用来高效地写入和存储闪存设备的数据。该方案中,信息由单元电荷值的相对等级表示,而不是由单元电荷绝对值来表示。因此,可以构造置换上的等级调制码来缓解闪存单元的过度编程问题与电荷泄漏产生的相邻对换错误问题。从而,等级调制方案下的置换码可以提高闪存系统的可靠性。但是,对于多级存储单元的闪存系统,现有的纠单个相邻对换错误的等级调制置换码缺乏有效的编译码算法。为了解决这个问题,通过交织置换符号集的划分块集合上的两个置换码,提出了一种新的Kendall τ距离度量下可纠正单个相邻对换错误置换码的构造方法。然后,借助unranking映射与置换码的交织技术,提出了一种该类置换码的编码算法。同时,利用置换的ranking映射,提出了一种该类置换码的有效译码算法。所提出的置换码具有简单的结构,而且,通过计算实例验证了所提出的置换码构造方法及其编译码算法的有效性。

关键词: 等级调制, 置换码, 相邻对换错误, Kendall τ距离, 交织技术

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

中图分类号:

TP301.6

韩辉,慕建君,焦晓鹏,赵展展. 纠单个相邻对换错误置换码构造与编译码方法[J]. 西安电子科技大学学报, 2023, 50(3): 105-111.

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.

图/表 1

参考文献 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)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 18

相关文章 4

Metrics

本文评价

推荐阅读 10

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