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

(1.華僑大學(xué) 廈門市移動(dòng)多媒體通信重點(diǎn)實(shí)驗(yàn)室，福建 廈門 361021；2.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071)

閃存作為非易失性存儲(chǔ)方式的主流存儲(chǔ)器，具有低耗能、良好可靠性、高密度存儲(chǔ)等優(yōu)勢，已被廣泛應(yīng)用于便攜式電子設(shè)備、嵌入式設(shè)備等存儲(chǔ)部件。閃存數(shù)據(jù)通常受到電荷泄漏、單元間干擾、讀/寫干擾和數(shù)據(jù)保持噪聲等影響[1]，可能發(fā)生刪除、擦除、替換和移位等類型的錯(cuò)誤，導(dǎo)致讀取數(shù)據(jù)與原始數(shù)據(jù)不一致[2-4]。近年來，面向閃存設(shè)備的糾錯(cuò)編碼技術(shù)已成為差錯(cuò)控制編碼領(lǐng)域的一個(gè)重要研究方向，其中基于置換理論的等級調(diào)制編碼技術(shù)可糾正閃存中的非對稱錯(cuò)誤，是提高閃存設(shè)備可靠性的一個(gè)有效途徑[5-7]。

當(dāng)某個(gè)閃存單元被破壞而無法讀出所存儲(chǔ)的電荷值時(shí)，在相應(yīng)位置發(fā)生擦除或刪除錯(cuò)誤。若錯(cuò)誤位置已知，則發(fā)生擦除錯(cuò)誤；若錯(cuò)誤位置未知，則發(fā)生刪除錯(cuò)誤。擦除或刪除錯(cuò)誤進(jìn)一步分為兩類：穩(wěn)定錯(cuò)誤和非穩(wěn)定錯(cuò)誤。在傳統(tǒng)的分組等級調(diào)制模型中，通常假設(shè)閃存單元組中各個(gè)單元可能發(fā)生的擦除錯(cuò)誤或刪除錯(cuò)誤相互獨(dú)立，不會(huì)影響到其他單元的等級描述，這類錯(cuò)誤稱為“穩(wěn)定錯(cuò)誤”，要求不同等級對應(yīng)的存儲(chǔ)電荷值之間具有足夠大的差值，同時(shí)要求各個(gè)單元的存儲(chǔ)電荷值保持高度穩(wěn)定，從而具備足夠的抗干擾和抗噪聲的能力。隨著閃存容量不斷增大和封裝尺寸不斷減小的技術(shù)發(fā)展趨勢，為了降低實(shí)現(xiàn)成本，不同等級對應(yīng)的存儲(chǔ)電荷值之間的差值越來越??；一個(gè)單元發(fā)生擦除錯(cuò)誤或刪除錯(cuò)誤，會(huì)影響到其他單元存儲(chǔ)電荷值的等級識別，這類錯(cuò)誤稱為“非穩(wěn)定錯(cuò)誤”。進(jìn)一步，由于閃存單元間寄生電容的耦合效應(yīng)，使單元電荷向相鄰單元不斷滲透，從而導(dǎo)致連續(xù)多個(gè)閃存單元發(fā)生刪除或擦除錯(cuò)誤，稱為突發(fā)刪除(Burst Deletion，BD)錯(cuò)誤或突發(fā)擦除(Burst Erasure，BE)錯(cuò)誤[8]，糾正非穩(wěn)定的突發(fā)刪除或突發(fā)擦除錯(cuò)誤更為困難。

近年來，LEVENSHTEIN首先提出一種可糾正單個(gè)刪除錯(cuò)誤的置換碼[9]，奠定了置換碼的理論基礎(chǔ)。GABRYS等隨后提出了“穩(wěn)定/非穩(wěn)定”擦除(Stable/Unstable Erasure，SE/UE)、“穩(wěn)定/非穩(wěn)定”刪除(Stable/Unstable Deletion，SD/UD)等分類錯(cuò)誤模型，并針對這些模型提出了相應(yīng)的置換碼構(gòu)造方法[10]。CHEE等先后提出了可糾正單個(gè)穩(wěn)定和非穩(wěn)定突發(fā)刪除錯(cuò)誤的置換碼構(gòu)造方法[8，11]。SALA等首先將多重置換碼應(yīng)用于閃存差錯(cuò)控制領(lǐng)域，提出糾正單個(gè)或多個(gè)非穩(wěn)定刪除錯(cuò)誤的多重置換碼構(gòu)造方法[12]。HAN等提出可糾正穩(wěn)定突發(fā)刪除錯(cuò)誤的兩類置換碼和一類多重置換碼構(gòu)造方法[13]，隨后MU與HAN等又提出兩類糾正單個(gè)非穩(wěn)定的突發(fā)擦除錯(cuò)誤的多重置換碼構(gòu)造方法[14]。ZHAO等先后提出可糾正穩(wěn)定和非穩(wěn)定突發(fā)刪除錯(cuò)誤的多重置換碼構(gòu)造方法[15-16]。針對突發(fā)刪除錯(cuò)誤的置換碼技術(shù)已逐步成熟，而針對突發(fā)擦除錯(cuò)誤的置換碼還需進(jìn)一步深入研究。

筆者主要研究等級調(diào)制下閃存單元的突發(fā)擦除錯(cuò)誤，基于糾正單個(gè)刪除錯(cuò)誤的LEVENSHTEIN置換碼[9]，提出一種置換碼的交織構(gòu)造方法，可分別糾正穩(wěn)定和非穩(wěn)定的單突發(fā)擦除錯(cuò)誤。給定交織深度為s，單突發(fā)長度≤2s的穩(wěn)定擦除錯(cuò)誤問題將分解為s個(gè)單突發(fā)長度≤ 2的穩(wěn)定擦除錯(cuò)誤問題，單突發(fā)長度≤s的非穩(wěn)定擦除錯(cuò)誤問題則分解為s個(gè)單非穩(wěn)定擦除錯(cuò)誤問題，分解后的子問題可直接采用LEVENSHTEIN置換碼的譯碼方法分別糾正。

1 基本概念

1.1 置換的基本概念

對于任意兩個(gè)整數(shù)m和n，若滿足m≤n，則可定義一個(gè)連續(xù)整數(shù)集合[m，n]={m，m+1，…，n}。當(dāng)n為正整數(shù)時(shí)，可定義連續(xù)整數(shù)集[n]={1，2，…，n}，即[n]=[1，n]。集合[n]中所有元素的一個(gè)排列稱為一個(gè)置換，集合[n]上的所有置換構(gòu)成置換群Sn，有|Sn|=n!。一般而言，任意有限集X上的所有置換可構(gòu)成一個(gè)置換群，記為SX。若|X|=n，則SX和Sn同構(gòu)。

定義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(lǐng)?[n]表示一個(gè)位置子集，則置換α∈Sn中相應(yīng)位置上的元素構(gòu)成一個(gè)元素子集，記為α(I)={α(i)：i∈I}，這些元素保持原有次序可構(gòu)成α的一個(gè)子置換，亦由α(I)表示。

定義3(等級映射) 設(shè)有限集X由n個(gè)任意不同的數(shù)值元素構(gòu)成，每個(gè)元素x∈X按從小到大的次序，必在[n]中惟一對應(yīng)一個(gè)元素k，記為φ(x)=k，則k稱為元素x的次序值或“相對等級”，φ稱為集合X到集合[n]的相對等級映射，對β=(β1，β2，…，βn)∈SX，令φ(β)=(φ(β1)，φ(β2)，…，φ(βn))，則φ(β)∈Sn稱為β的相對等級置換。

例1 設(shè)α=(5，3，6，1，4，2)∈S6，則α-1=(4，6，2，5，1，3)∈S6，α-1(1)=4表示α中元素“1”在第4個(gè)位置，α-1(2)=6表示α中元素“2”在第6個(gè)位置，以此類推。設(shè)I={1，4，5}，有α(I)={5，1，4}。

例2 設(shè)X={1，2，5，7，10，13}，|X|=6，則相對等級映射φ表示如下：

設(shè)β=(5，10，2，7，1，13)∈SX，則φ(β)=(3，5，2，4，1，6)∈S6。

1.2 等級調(diào)制下的擦除錯(cuò)誤模型

α=(7，3，4，6，1，5，2，8)圖1 閃存單元組等級調(diào)制的相對等級置換

采用等級調(diào)制方式的閃存設(shè)備對數(shù)據(jù)進(jìn)行分組存儲(chǔ)，分組數(shù)據(jù)對應(yīng)表示相同長度閃存單元組存儲(chǔ)電荷值的相對等級置換，即實(shí)數(shù)向量的相對等級置換。當(dāng)采用置換碼時(shí)，閃存單元組中每個(gè)閃存單元的存儲(chǔ)電荷值不同[4]。當(dāng)采用多重置換碼時(shí)，不同閃存單元的存儲(chǔ)電荷值可以相同[12]。圖1給出了分組長度為n=8的一個(gè)閃存單元組等級調(diào)制的置換表示，閃存單元的位置順序?yàn)?到8，閃存單元的存儲(chǔ)電荷值表示為直方圖，其中第5單元的電荷值最低，第8單元的電荷值最高，相對等級置換為α=(7，3，4，6，1，5，2，8)∈S8。

等級調(diào)制閃存的穩(wěn)定擦除錯(cuò)誤模型和非穩(wěn)定擦除錯(cuò)誤模型統(tǒng)一定義如下。

(1) 穩(wěn)定擦除模型

(1)

(2) 非穩(wěn)定擦除模型

(2)

1.3 糾正單擦除錯(cuò)誤的置換碼

LEVENSHTEIN碼是一類可糾正單個(gè)穩(wěn)定刪除錯(cuò)誤的置換碼，碼構(gòu)造定義如下[9]。

(3)

其中，當(dāng)α(j)≤α(j+1)時(shí)，μ(α(j))=1；否則，μ(α(j))=0。則μ(α)=(μ(α(1))，μ(α(2))，…，μ(α(n)))，稱為置換α的簽名[9]。每個(gè)碼字的簽名是惟一的。

若碼字α在位置k∈[n]上發(fā)生單個(gè)非穩(wěn)定擦除錯(cuò)誤，則必存在i∈[n]，使得逆置換中α-1(i)=k，從而可確定被擦除的元素值為α(k)=i。因此，可利用LEVENSHTEIN碼字的逆置換來糾正單個(gè)非穩(wěn)定擦除錯(cuò)誤，具體定義如下。

定義6任意給定非負(fù)整數(shù)a∈Zn，可定義一個(gè)糾正單個(gè)非穩(wěn)定擦除錯(cuò)誤的置換碼為

(4)

2 糾突發(fā)擦除錯(cuò)誤的置換碼設(shè)計(jì)

針對等級調(diào)制下閃存的擦除錯(cuò)誤，提出一種可糾正單個(gè)突發(fā)擦除錯(cuò)誤的置換碼，給出了碼構(gòu)造及相應(yīng)的譯碼方法。

2.1 構(gòu)造方法

定義7給定正整數(shù)s，令C?Sn為一個(gè)n長置換碼，如果碼C能糾正單個(gè)突發(fā)長度不超過s的穩(wěn)定擦除錯(cuò)誤，則稱為“≤s-SBE”置換碼。類似地，如果C能糾正單個(gè)突發(fā)長度不超過s的非穩(wěn)定擦除錯(cuò)誤，則稱為“≤s-UBE”置換碼。

給定s個(gè)置換碼Ci，i∈[s]，碼長遞減但相差不超過1，則根據(jù)定義8可構(gòu)造一個(gè)交織碼為

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

(5)

應(yīng)用上述的交織方法，結(jié)合定義5和定義6的糾錯(cuò)碼構(gòu)造方法，下面提出一種可糾正單個(gè)突發(fā)擦除錯(cuò)誤的置換碼構(gòu)造方法，可分別糾正單個(gè)突發(fā)長度≤2s的穩(wěn)定擦除錯(cuò)誤(≤2s-SBE)和單個(gè)突發(fā)長度≤s的非穩(wěn)定擦除錯(cuò)誤(≤s-UBE)。

構(gòu)造：給定的正整數(shù)n，m，s，滿足n=sm，集合[n]劃分為s個(gè)互不相交的子集

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

(6)

且|Qi|=m，令正整數(shù)ai，bi∈Zn，SQi為Qi上所有置換構(gòu)成的置換群，結(jié)合定義5中糾正單個(gè)穩(wěn)定刪除錯(cuò)誤的置換碼和定義6中糾正單個(gè)非穩(wěn)定擦除錯(cuò)誤的置換碼

(7)

(8)

可構(gòu)造一個(gè)置換碼

(9)

則碼CBE，n可分別糾正單個(gè)突發(fā)長度≤2s-SBE和單個(gè)突發(fā)長度≤s-UBE的兩種擦除錯(cuò)誤。

2.2 譯碼方法

2.2.1 糾單個(gè)突發(fā)長度≤2 s的穩(wěn)定擦除錯(cuò)誤

2.2.2 糾單個(gè)突發(fā)長度≤s的非穩(wěn)定擦除錯(cuò)誤

下面通過具體例子，來驗(yàn)證單個(gè)≤2s-SBE錯(cuò)誤和單個(gè)≤s-UBE錯(cuò)誤的糾正。

例5 對于n=18，m=6，s=3，令CBE，n表示所得長度為n的置換碼。根據(jù)模s同余關(guān)系，將集合[n]劃分為3個(gè)子集：Q1={1，4，7，10，13，16}，Q2={2，5，8，11，14，17}，Q3={3，6，9，12，15，18}。任取3個(gè)置換β1∈Ca1

SD，6∩Cb1

UE，6，β2∈Ca2

SD，6，∩Cb2

UE，6，β3∈Ca3

SD，6∩Cb3

UE，6，經(jīng)過交織生成一個(gè)碼字β1°β2°β3∈CBE，18。

(1)假定發(fā)生5-SBE錯(cuò)誤，錯(cuò)誤位置集為I=[2，6]，讀取碼字為

(2) 假定發(fā)生3-UBE錯(cuò)誤，錯(cuò)誤位置集為I=[5，7]，讀取碼字為

3 結(jié)束語

基于糾正單個(gè)刪除錯(cuò)誤的LEVENSHTEIN置換碼構(gòu)造方法，針對閃存單元等級調(diào)制下置換碼發(fā)生突發(fā)刪除錯(cuò)誤的穩(wěn)定性問題，結(jié)合置換交織技術(shù)，提出一種新的置換碼構(gòu)造方法；可分別糾正單個(gè)突發(fā)長度≤2s的穩(wěn)定擦除錯(cuò)誤和單個(gè)突發(fā)長度≤s的非穩(wěn)定擦除錯(cuò)誤，并給出了相應(yīng)的譯碼方法。最后通過實(shí)例驗(yàn)證了所提出的構(gòu)造和譯碼方法的有效性。