纠正稳定和非稳定突发擦除错误的置换码

何雅萍，贺玉成，2，周 林，2

(1.华侨大学 厦门市移动多媒体通信重点实验室，福建 厦门 361021；2.西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071)

闪存作为非易失性存储方式的主流存储器，具有低耗能、良好可靠性、高密度存储等优势，已被广泛应用于便携式电子设备、嵌入式设备等存储部件。闪存数据通常受到电荷泄漏、单元间干扰、读/写干扰和数据保持噪声等影响[1]，可能发生删除、擦除、替换和移位等类型的错误，导致读取数据与原始数据不一致[2-4]。近年来，面向闪存设备的纠错编码技术已成为差错控制编码领域的一个重要研究方向，其中基于置换理论的等级调制编码技术可纠正闪存中的非对称错误，是提高闪存设备可靠性的一个有效途径[5-7]。

当某个闪存单元被破坏而无法读出所存储的电荷值时，在相应位置发生擦除或删除错误。若错误位置已知，则发生擦除错误；若错误位置未知，则发生删除错误。擦除或删除错误进一步分为两类：稳定错误和非稳定错误。在传统的分组等级调制模型中，通常假设闪存单元组中各个单元可能发生的擦除错误或删除错误相互独立，不会影响到其他单元的等级描述，这类错误称为“稳定错误”，要求不同等级对应的存储电荷值之间具有足够大的差值，同时要求各个单元的存储电荷值保持高度稳定，从而具备足够的抗干扰和抗噪声的能力。随着闪存容量不断增大和封装尺寸不断减小的技术发展趋势，为了降低实现成本，不同等级对应的存储电荷值之间的差值越来越小；一个单元发生擦除错误或删除错误，会影响到其他单元存储电荷值的等级识别，这类错误称为“非稳定错误”。进一步，由于闪存单元间寄生电容的耦合效应，使单元电荷向相邻单元不断渗透，从而导致连续多个闪存单元发生删除或擦除错误，称为突发删除(Burst Deletion，BD)错误或突发擦除(Burst Erasure，BE)错误[8]，纠正非稳定的突发删除或突发擦除错误更为困难。

近年来，LEVENSHTEIN首先提出一种可纠正单个删除错误的置换码[9]，奠定了置换码的理论基础。GABRYS等随后提出了“稳定/非稳定”擦除(Stable/Unstable Erasure，SE/UE)、“稳定/非稳定”删除(Stable/Unstable Deletion，SD/UD)等分类错误模型，并针对这些模型提出了相应的置换码构造方法[10]。CHEE等先后提出了可纠正单个稳定和非稳定突发删除错误的置换码构造方法[8，11]。SALA等首先将多重置换码应用于闪存差错控制领域，提出纠正单个或多个非稳定删除错误的多重置换码构造方法[12]。HAN等提出可纠正稳定突发删除错误的两类置换码和一类多重置换码构造方法[13]，随后MU与HAN等又提出两类纠正单个非稳定的突发擦除错误的多重置换码构造方法[14]。ZHAO等先后提出可纠正稳定和非稳定突发删除错误的多重置换码构造方法[15-16]。针对突发删除错误的置换码技术已逐步成熟，而针对突发擦除错误的置换码还需进一步深入研究。

笔者主要研究等级调制下闪存单元的突发擦除错误，基于纠正单个删除错误的LEVENSHTEIN置换码[9]，提出一种置换码的交织构造方法，可分别纠正稳定和非稳定的单突发擦除错误。给定交织深度为s，单突发长度≤2s的稳定擦除错误问题将分解为s个单突发长度≤ 2的稳定擦除错误问题，单突发长度≤s的非稳定擦除错误问题则分解为s个单非稳定擦除错误问题，分解后的子问题可直接采用LEVENSHTEIN置换码的译码方法分别纠正。

1 基本概念

1.1 置换的基本概念

对于任意两个整数m和n，若满足m≤n，则可定义一个连续整数集合[m，n]={m，m+1，…，n}。当n为正整数时，可定义连续整数集[n]={1，2，…，n}，即[n]=[1，n]。集合[n]中所有元素的一个排列称为一个置换，集合[n]上的所有置换构成置换群Sn，有|Sn|=n!。一般而言，任意有限集X上的所有置换可构成一个置换群，记为SX。若|X|=n，则SX和Sn同构。

定义1(逆置换) 令置换α=(α(1)，α(2)，…，α(n))∈Sn，其逆置换记为α-1=(α-1(1)，α-1(2)，…，α-1(n))∈Sn，若α(k)=i，则α-1(i)=k。

因此，α-1(i)表示元素i∈[n]在置换α中的位置值k，集合[n]表示置换α∈Sn中所有元素的位置集。

定义2(子置换) 令I⊆[n]表示一个位置子集，则置换α∈Sn中相应位置上的元素构成一个元素子集，记为α(I)={α(i)：i∈I}，这些元素保持原有次序可构成α的一个子置换，亦由α(I)表示。

定义3(等级映射) 设有限集X由n个任意不同的数值元素构成，每个元素x∈X按从小到大的次序，必在[n]中惟一对应一个元素k，记为φ(x)=k，则k称为元素x的次序值或“相对等级”，φ称为集合X到集合[n]的相对等级映射，对β=(β1，β2，…，βn)∈SX，令φ(β)=(φ(β1)，φ(β2)，…，φ(βn))，则φ(β)∈Sn称为β的相对等级置换。

例1 设α=(5，3，6，1，4，2)∈S6，则α-1=(4，6，2，5，1，3)∈S6，α-1(1)=4表示α中元素“1”在第4个位置，α-1(2)=6表示α中元素“2”在第6个位置，以此类推。设I={1，4，5}，有α(I)={5，1，4}。

例2 设X={1，2，5，7，10，13}，|X|=6，则相对等级映射φ表示如下：

设β=(5，10，2，7，1，13)∈SX，则φ(β)=(3，5，2，4，1，6)∈S6。

1.2 等级调制下的擦除错误模型

α=(7，3，4，6，1，5，2，8)图1 闪存单元组等级调制的相对等级置换

采用等级调制方式的闪存设备对数据进行分组存储，分组数据对应表示相同长度闪存单元组存储电荷值的相对等级置换，即实数向量的相对等级置换。当采用置换码时，闪存单元组中每个闪存单元的存储电荷值不同[4]。当采用多重置换码时，不同闪存单元的存储电荷值可以相同[12]。图1给出了分组长度为n=8的一个闪存单元组等级调制的置换表示，闪存单元的位置顺序为1到8，闪存单元的存储电荷值表示为直方图，其中第5单元的电荷值最低，第8单元的电荷值最高，相对等级置换为α=(7，3，4，6，1，5，2，8)∈S8。

等级调制闪存的稳定擦除错误模型和非稳定擦除错误模型统一定义如下。

(1) 稳定擦除模型

(1)

(2) 非稳定擦除模型

(2)

1.3 纠正单擦除错误的置换码

LEVENSHTEIN码是一类可纠正单个稳定删除错误的置换码，码构造定义如下[9]。

(3)

其中，当α(j)≤α(j+1)时，μ(α(j))=1；否则，μ(α(j))=0。则μ(α)=(μ(α(1))，μ(α(2))，…，μ(α(n)))，称为置换α的签名[9]。每个码字的签名是惟一的。

若码字α在位置k∈[n]上发生单个非稳定擦除错误，则必存在i∈[n]，使得逆置换中α-1(i)=k，从而可确定被擦除的元素值为α(k)=i。因此，可利用LEVENSHTEIN码字的逆置换来纠正单个非稳定擦除错误，具体定义如下。

定义6任意给定非负整数a∈Zn，可定义一个纠正单个非稳定擦除错误的置换码为

(4)

2 纠突发擦除错误的置换码设计

针对等级调制下闪存的擦除错误，提出一种可纠正单个突发擦除错误的置换码，给出了码构造及相应的译码方法。

2.1 构造方法

定义7给定正整数s，令C⊆Sn为一个n长置换码，如果码C能纠正单个突发长度不超过s的稳定擦除错误，则称为“≤s-SBE”置换码。类似地，如果C能纠正单个突发长度不超过s的非稳定擦除错误，则称为“≤s-UBE”置换码。

给定s个置换码Ci，i∈[s]，码长递减但相差不超过1，则根据定义8可构造一个交织码为

C=C1∘C2∘…∘Cs={β1∘β2∘…∘βs：βi∈Ci，i∈[s]}。

(5)

应用上述的交织方法，结合定义5和定义6的纠错码构造方法，下面提出一种可纠正单个突发擦除错误的置换码构造方法，可分别纠正单个突发长度≤2s的稳定擦除错误(≤2s-SBE)和单个突发长度≤s的非稳定擦除错误(≤s-UBE)。

构造：给定的正整数n，m，s，满足n=sm，集合[n]划分为s个互不相交的子集

Qi={j∈[n]：j≡i(mods)}，i∈[s]。

(6)

且|Qi|=m，令正整数ai，bi∈Zn，SQi为Qi上所有置换构成的置换群，结合定义5中纠正单个稳定删除错误的置换码和定义6中纠正单个非稳定擦除错误的置换码

(7)

(8)

可构造一个置换码

(9)

则码CBE，n可分别纠正单个突发长度≤2s-SBE和单个突发长度≤s-UBE的两种擦除错误。

2.2 译码方法

2.2.1 纠单个突发长度≤2 s的稳定擦除错误

2.2.2 纠单个突发长度≤s的非稳定擦除错误

下面通过具体例子，来验证单个≤2s-SBE错误和单个≤s-UBE错误的纠正。

例5 对于n=18，m=6，s=3，令CBE，n表示所得长度为n的置换码。根据模s同余关系，将集合[n]划分为3个子集：Q1={1，4，7，10，13，16}，Q2={2，5，8，11，14，17}，Q3={3，6，9，12，15，18}。任取3个置换β1∈Ca1

SD，6∩Cb1

UE，6，β2∈Ca2

SD，6，∩Cb2

UE，6，β3∈Ca3

SD，6∩Cb3

UE，6，经过交织生成一个码字β1∘β2∘β3∈CBE，18。

(1)假定发生5-SBE错误，错误位置集为I=[2，6]，读取码字为

(2) 假定发生3-UBE错误，错误位置集为I=[5，7]，读取码字为

3 结束语

基于纠正单个删除错误的LEVENSHTEIN置换码构造方法，针对闪存单元等级调制下置换码发生突发删除错误的稳定性问题，结合置换交织技术，提出一种新的置换码构造方法；可分别纠正单个突发长度≤2s的稳定擦除错误和单个突发长度≤s的非稳定擦除错误，并给出了相应的译码方法。最后通过实例验证了所提出的构造和译码方法的有效性。