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

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

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

韩辉1,2(),慕建君1,2(),焦晓鹏1(),赵展展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 Hui1,2(),MU Jianjun1,2(),JIAO Xiaopeng1(),ZHAO Zhanzhan1()   

  1. 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

摘要:

等级调制方案是一种利用置换表示信息的编码方法,用来高效地写入和存储闪存设备的数据。该方案中,信息由单元电荷值的相对等级表示,而不是由单元电荷绝对值来表示。因此,可以构造置换上的等级调制码来缓解闪存单元的过度编程问题与电荷泄漏产生的相邻对换错误问题。从而,等级调制方案下的置换码可以提高闪存系统的可靠性。但是,对于多级存储单元的闪存系统,现有的纠单个相邻对换错误的等级调制置换码缺乏有效的编译码算法。为了解决这个问题,通过交织置换符号集的划分块集合上的两个置换码,提出了一种新的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