基于置换理论的等级调制纠错码新构造方法*

张用宇

（中国人民解放军91469部队，北京 100841）

0 引 言

闪存（Flash Memory）是一种采用浮栅结构的长寿命非易失性存储器[1]，即使在断电情况下仍能保持所存储的数据信息。置换码是一种多进制纠错码。近年来，由于陆续发现了置换码在电力线数据传输和多级闪存等领域的新应用[2-3]，置换码重新引起了学者的关注。虽然闪存技术飞速发展，但仍然存在两个问题制约其发展。一是闪存读写操作过程中电荷注入的问题，如过量注入导致的过度编程（单元注入电荷值高于目标电荷值）；二是数据的可靠性，如闪存中存储的数据受到了电荷泄漏、数据保持问题、读/写干扰等影响而受到损坏。采用等级调制方案[4-6]可以避免闪存单元过度编程的风险，还可以降低电荷泄漏等噪声引起的非对称错误影响。当读写单元的电平值时，仅需要比较不同单元之间的电位值。当电位值向一个方向偏离时，它们的等级不会像绝对值受到影响。因此，等级调制可有效提高写入速度，减少非对称错误，提高数据可靠性。

因为闪存设备中产生错误的特殊性，所以RS码、LDPC码等差错控制编码方法不能有效纠正这些错误。基于置换理论的等级调制纠错码适合于多级闪存中多个单元电位值具有相同等级的等级调制纠错方案。与置换码[7-8]相比，基于置换理论的等级调制纠错码可以有效提高闪存的可靠性，达到较高的信息存储率。

针对有限强度错误的研究，文献[2，9]提出了等级调制纠错码的构造方法。在Chebychev度量下，Min-Zheng Shieh提出了直接和递归的多重置换码构造方法[7]。在此基础上，本文提出了两种基于置换理论的等级调制纠错码的构造方法，一种是直接方法，即通过多重置换集进行直积运算得到；另一种是间接方法，即通过对已有多重置换集进行运算得到新的多重置换集，进而再进行直积运算构造出等级调制纠错码。

1 基本概念

对于正整数n∈ℕ，设[]n表示集合{1,2,…,n}，SA是集合A的对称群，即基数为n的集合A上所有置换的集合， []nS 简记为nS。对于具有n个闪存单元的等级调制编码，假设n个闪存记忆单元分别命名为1,2,,n…。每个单元的电平等级记为ic，其中i。n个闪存单元的排序为集合Sn上的一个置换，并设其中一个置换为一个闪存单元等级相对值由高到低的一个排列。设表示置换映射其中等级调制方法由编码和译码两个函数定义。编码函数输入信息a∈Q映射成一个置换译码函数D：nSQ→。由于置换f会被可能的扰动影响，影响后的置换记为f′，译码的目标是使()D fa′=。

定义一个多重集（Multiset）为：

其中，且

考虑一种特殊的情况，令且则多重集变为：

设是式（2）的对称群，即式（2）所有置换的集合。

定义1 对于定义f与g之间的切比雪夫距离函数为：

定义2 基于置换理论参数为(λ,n,d)的等级调制码C定义为 Sn的子集，即其基数为C中码字的个数，记为M，且对于所有,f gC∈，fg≠，有

2 构造方法

构造1 设,,mdλ∈ℕ，nmλ=，2λ≥，对于

i∈[d]，令：

设是iA（[]id∈）的对称群，构造多重置换码的直积，即：

构造的码C是Chebyshev度量下的一个基于置换理论的(,,)n dλ等级调制码。

定理1 构造的(,,)n dλ等级调制码的基数为：

证明：令,f gC∈是任意2个不同的码字。对于i∈[n]，有由多重置换集Ai的定义，可知可得对于由Chebyshev距离函数定义可得：

因此，构造的码C是一个(,,)n dλ多重置换码。

由构造条件可知，d个多重集iA（[]id∈）是多重集的一个划分，其中n=mλ。设正整数[]id∈，如果d不能整除m，每一个多重集iA（[]id∈）中元素的个数至多为如果d能整除m，每一个多重集中元素的个数都为在Ai个多重集中恰好有m (m odd)个多重集，其中每个多重集包含个元素。由于每个元素在对应的多重集中分别出现λ次，每个多重集中重复的个数为其余的个多重集，其中每个多重集包含个元素。考虑到每个元素的重复次数，每个多重集中重复的个数为因此，构造的(λ,n, d)等级调制码的基数为：

例1：设正整数11m=，2λ=，3d=。由构造1中的定义可得对于表示 A 的对称群，i即多重集iA上所有置换的集合。它在Chebyshev度量下的最小距离为 d = 3 。例如，当 i = 3 时，的基数为由构造方法1得到等级调制码它在Chebyshev度量下的最小距离为 3d=，码长即C是一个(2,22,3)等级调制码。通过式（6）可得，码C的基数M为571 536 000。

例2：设正整数12m=，2λ=，3d=。此时，d能整除m。由构造1中的定义可得

每一个多重集Ai包含8个元素，集合的基数都为2 520，在Chebyshev度量下的最小距离为d= 3 。由构造方法1得到等级调制码其在Chebyshev度量下的最小距离为 3d= ，码长即C是一个(2,24,3)等级调制码。通过式（6），可得码C的基数M为16 003 008 000。

构造2 设,,mkλ∈ℕ，nmλ=，2λ≥，对于令：

定义运算：

其中

构造码字

定理2 构造的码字C是一个基于置换理论的(,,)n dλ等级调制码，其基数最小距离

证明：由构造方法容易得到码字的长度nmλ=，等级调制码C的基数大小

由构造2可知，是最小距离为ikd的多重置换集。令,f gC∈是任意2个不同的码字，对于有是k的倍数。因此，最小距离

例3：设正整数7m=，2λ=，3k=。由构造2给出的方法可得到其基数13M=，22M= ，32M= 。设码1

C是由构造1的方法得到的码长最小距离12d=的(2,6,2)等级调制码：

根据构造2的方法，中各码字在集合1A上构成一个多重置换集即：

在Chebyshev度量下最小距离为 k d= 6 。1

同理，设码2

C是由构造的方法得到的码长最小距离d2=1的(2,4,1)等级调制码：

C2中各码字在集合 A2上构成一个多重置换集

在Chebyshev度量下最小距离为 k d= 3 。2

设码3C 是由构造的方法得到的码长最小距离d3=1的(4,2,1)等级调制码：

中各码字在集合3A上构成一个多重置换集最小距离为的(2,14,3)等级调制码C，其基数为：

在Chebyshev度量下最小距离为 k d= 3 。3

由提出的构造2的方法，可得到一个码长为

(2,14,3)等级调制码C如表1所示。

表1 (2,14,3)等级调制码C

3 结 语

闪存具有高性能、非易失性、能耗低和存储容量大等优点。在多级闪存中，采用等级调制方案可有效克服闪存的有限强度错误。针对这一问题，基于多重置换理论提出了采用直积运算直接和间接等级调制纠错码的两种构造方法，构造方法简单直观，易于编译码，并通过计算实例表明了构造方法的正确性。多重置换码的研究对基于多重置换码的等级调制方案的设计具有重要意义，在多级闪存和无线通信等领域可有效对抗信道中的脉冲噪声、窄带噪声、背景噪声和衰落等干扰。

[1] Cappelletti P,Golla C,Olivo P,et al.Flash Memories[M].Boston MA:Kluwer,1999.

[2] Tamo I,Schwatz M.Correcting Limited-magnitude Errors in the Rank-modulation Scheme[J].IEEE Transactions on Information Theory,2010,56(06):2551-2560.

[3] 慕建君,赵鹏,焦晓鹏.一种纠单个闪存单元移位错误的译码方法[J].西安电子科技大学学报(自然科学版),2016,43(06):51-55.

MU Jian-jun,ZHAO Peng,JIAO Xiao-peng.Decoding of Codes Correcting a Single Translocation Error for the Cell’s Level of Flash Memory[J].Journal of Xidian University,2016,43(06):51-55.

[4] Jiang A,Mateescu R,Schwartz M,et al.Rank Modulation for Flash Memories[J].IEEE Transactions on Information Theory,2009,55(06):2659-2673.

[5 Gabrys R,Yaakobi E,Farnoud F.Codes Correcting Erasures and Deletions for Rank Modulation[J].IEEE Communications Letters,2016,62(01):136-150.

[6] Holroyd A E.Perfect Snake-in-the-box Codes for Rank Modulation[J].IEEE Transactions on Information Theory,2017, 63(01):104-110.

[7] Shieh M Z,Tsai S C.Decoding Frequency Permutation Arrays under Chebyshev Distance[J].IEEE Transactions on Information Theory,2010,56(11):5730-5737.

[8] Liu X,Draper S C.LP-decodable Multipermutation Codes[J].IEEE Transactions on Information Theory,2016,62(04):1631-1648.

[9] Klϕve T,Lin T T,Tsai S C,et al.Permutation Arrays under the Chebyshev Distance[J].IEEE Transactions on Information Theory,2010,56(06):2611-2617.