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

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

作　　者：韩辉 慕建君[1,2] 焦晓鹏 赵展展[1] HAN Hui;MU Jianjun;JIAO Xiaopeng;ZHAO Zhanzhan(School of Computer Science and Technology,Xidian University,Xi’an 710071,China;Chongqing Key Lab of Computer Network and Communication Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

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

出　　处：《西安电子科技大学学报》2023年第3期105-111,共7页Journal of Xidian University

基　　金：国家自然科学基金(62001362,61977051,61971322);重庆市/信息产业部计算机网络与通信技术重点实验室开放基金(CY-CNCL-2021-01);中央高校基本科研业务费专项资金(XJS220310);中国博士后科学基金(2020M683427)。

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TN911.22[自动化与计算机技术—计算机科学与技术]