韓 輝，慕建君，焦曉鵬

(西安電子科技大學(xué) 計算機(jī)學(xué)院，陜西 西安 710071)

目前，多級存儲單元(Multi-Level Cell，MLC)技術(shù)能夠提高NAND閃存的數(shù)據(jù)存儲密度(容量)． 然而，隨著NAND閃存芯片封裝尺寸的縮小，大容量、高可靠閃速存儲器的研究及應(yīng)用面臨著閃存單元編程和單元擦除之間的非對稱性問題． 2009年，文獻(xiàn)[1]提出的等級調(diào)制方案給出了解決這一問題的一種新框架． 該方案中，數(shù)據(jù)的存儲是以單元間電荷值相對等級的形式表示，而不是以電荷絕對等級的形式表示．

閃存面臨的第2個問題是所存儲數(shù)據(jù)的可靠性問題，特別是多級存儲單元型閃存中出現(xiàn)的單元間干擾(Cell-to-Cell Interference)現(xiàn)象使得數(shù)據(jù)損壞的問題更為突出[2]． 基于等級調(diào)制方案的糾錯置換碼可以提高閃速存儲設(shè)備數(shù)據(jù)存儲的可靠性[3-6]． 基于等級調(diào)制方案的糾錯置換碼的大多數(shù)研究主要選擇切比雪夫距離度量和Kendallτ-距離度量． 文獻(xiàn)[7]中關(guān)于等級調(diào)制糾錯碼的研究表明，閃存單元發(fā)生的小電荷受限錯誤(Charge-Constrained Error)對應(yīng)一個小的Kendallτ-距離，而文獻(xiàn)[8]的研究表明，閃存單元發(fā)生的小強度有限錯誤(Limited-Magnitude Error)對應(yīng)一個小的切比雪夫距離度量．

針對Kendallτ-距離度量，文獻(xiàn)[7]利用測度嵌入技術(shù)提出了Kendallτ-距離度量下可以糾正單個相鄰對換錯誤的置換碼的構(gòu)造方法． 而針對切比雪夫距離度量，文獻(xiàn)[8]設(shè)計了可以糾正閃存單元幅度為t的強度有限錯誤的子群置換碼．2015年，文獻(xiàn)[9]構(gòu)造了Kendallτ-距離度量和切比雪夫距離距離度量下基于等級調(diào)制方案的兩類系統(tǒng)置換碼，同時給出了所構(gòu)造Kendallτ-距離度量下系統(tǒng)置換碼的編譯碼思路．

盡管文獻(xiàn)[9]提出了切比雪夫距離度量下基于等級調(diào)制方案的系統(tǒng)置換碼的構(gòu)造方法，但是沒有給出該類系統(tǒng)置換碼的編碼和譯碼方法． 基于文獻(xiàn)[8]所設(shè)計的切比雪夫距離度量下的(n，M，d)子群置換碼的編譯碼思路，通過利用對稱群上的ranking與unranking映射以及(n，M，d)置換碼的交織技術(shù)，提出了 [k+n，k，d]系統(tǒng)置換碼的一種編碼算法． 同時，借助利用對稱群上的ranking與unranking映射以及切比雪夫距離度量下(n，M，d)置換碼的投影技術(shù)，提出了該 [k+n，k，d]系統(tǒng)置換碼的一種譯碼算法．

1 置換理論

設(shè)[m，n]表示由n-m+1個整數(shù)組成的集合{m，m+1， …，n}，其中m∈N，n∈N(m

下面給出置換交織[10]、置換逆序[7]、切比雪夫距離度量[8,11]、系統(tǒng)置換碼[9]等與置換相關(guān)的幾個定義．

定義2 對于給定集合A={a1，a2， …，an}上對稱群SA的置換f= (f(1)，f(2)， …，f(n))∈SA，若if(j)，則稱(f(i)，f(j))為置換f的一個逆序． 設(shè)N(f(i))表示置換f的逆序中第1個分量為f(i)的逆序的個數(shù) (i∈ [n])，則稱向量(N(f(1))，N(f(2))， …，N(f(n)))為置換f的逆序向量． 而且置換f與其逆序向量是一一對應(yīng)的關(guān)系[7]．

定義4 對于給定集合A上的置換f∈SA和子集B?A，通過保留f中屬于B的元素而去掉其他所有元素后得到的置換稱為f在集B上的投影，記為f|B．例如，對于置換f= (6， 4，3， 1，5， 2)∈S6和子集B= {2， 4， 6}?A= {1，2，3，4，5，6}，f在B上投影f|B= (6，4，2)．

定義5 對于給定的對稱群S[n+1，n+k]，若一個(k+n，k!，d)置換碼C滿足 {g|[n+1，n+k]|g∈C}=S[n+1，n+k]，則稱置換碼C為一個 [k+n，k，d]系統(tǒng)置換碼．[k+n，k，d]系統(tǒng)置換碼C的任意一個碼字的第1到k位表示碼字的信息位，而其第k+1 位到第n+k位表示碼字的冗余位．

2 Ranking置換

對于集合A上的對稱群SA，為了建立字典序排序中置換f∈SA與其對應(yīng)位置的關(guān)系，Lehmer給出了對稱群上的ranking及unranking映射的具體方法[11]．

3 系統(tǒng)置換碼的編碼算法

借助文獻(xiàn)[12]所構(gòu)造的(n，M，d)置換碼Cr，文獻(xiàn)[9]提出了切比雪夫距離度量下 [k+n，k，d]系統(tǒng)置換碼Cs的一種構(gòu)造方法，即:

構(gòu)造1 對于給定的正整數(shù)d(1≤d≤n)，令Cr= {f∈Sn|f(i)≡i(modd)，i∈ [1，n]}，則Cr是一個(n，M，d)置換碼[12]，且Cr的碼字個數(shù)

(1)

令k是滿足M≥k!的最大正整數(shù)，S[n+1， n+k]表示[n+1，n+k]上所有置換的集合．假定Cr= {f1，f2， …，fM}和S[n+1， n+k]= {g1，g2， …，gk!}，則可構(gòu)造得置換碼Cs= {gi‖fi|i∈ [k!]}，其中‖表示向量的級聯(lián)．

由文獻(xiàn)[9]可知，構(gòu)造1所得的置換碼Cs={gi‖fi|i∈[k!]}是切比雪夫距離度量下的 [k+n，k，d]系統(tǒng)置換碼．

系統(tǒng)置換碼的編碼: 文獻(xiàn)[9]構(gòu)造的切比雪夫距離度量下[k+n，k，d]系統(tǒng)置換碼Cs編碼的關(guān)鍵是建立碼字中信息位與冗余位之間確定的對應(yīng)關(guān)系． 筆者利用對稱群上的ranking及unranking映射和(n，M，d)置換碼Cr的一種交織編碼方法來建立信息位與冗余位之間的對應(yīng)關(guān)系．

圖1 [k+n, k, d]系統(tǒng)置換碼的編碼算法流程圖

假設(shè)信息置換m=(m(1)，m(2)， …，m(k))∈S[n+1， n+k]，而通過切比雪夫距離度量下 [k+n，k，d]系統(tǒng)置換碼Cs編碼得到的碼字為c= (c(1)，c(2)，…，c(k)，c(k+1)，…，c(k+n))．對于集合[n]，令A(yù)i= {j∈ [n]|j≡i(modd)}，其中i∈ [d]．下面給出切比雪夫距離度量下可以糾正“強度有限錯誤”的 [k+n，k，d]系統(tǒng)置換碼的編碼算法(為了描述方便，假定d|n，且令t=n/d，該系統(tǒng)置換碼的編碼算法流程圖如圖1所示):

(1) 信息置換的ranking映射: 對于信息置換m∈S[n+1， n+k]，利用對稱群S[n+1， n+k]上的映射ranking:S[n+1，n+k]→ [0，k!-1] 得 ranking(m)=a．

(3) 碼字的確定: 由信息置換m編碼得到的 [k+n，k，d]系統(tǒng)置換碼Cs的碼字c=m‖α．

例3 考慮構(gòu)造1所給出的[3+6，3， 3]系統(tǒng)置換碼Cs，其中Cs的冗余位是利用構(gòu)造1的方法所得到的(6， 8， 3)置換碼Cr． 對于 [3+ 6， 3， 3]系統(tǒng)置換碼Cs，令t= 6/3= 2，下面給出一個碼字信息位m= (7， 9， 8)∈S[7， 9]的 [3+ 6， 3， 3]系統(tǒng)置換碼Cs的編碼過程:

(1) 信息置換m=(7， 9， 8)的ranking映射: 對于[3+6， 3， 3]系統(tǒng)置換碼Cs的信息置換m= (7， 9， 8)∈S[7， 9]，利用對稱群S[7， 9]上的映射ranking:S[7， 9]→ [0，3!-1] 計算得 ranking(m)= 0· 0!+ 1· 1!+ 0· 2!=1=a．

(2) 冗余位(c(4)，c(5)，c(6)，c(7)，c(8)，c(9))的確定: 將a=1表示成2!進(jìn)制形式 1= 1· (2!)0+ 0· (2!)1+ 0· (2!)2得(a1，a2，a3)= (1， 0， 0) ; 然后，利用Ai= (j∈ [6]|j≡i(mod 3)) (i∈ [3])可得A1= {1，4}、A2= {2，5}與A3= {3，6}; 利用對稱群SAi上的映射unranking: [0， |Ai|!-1]→SAi(i∈ [3])， 可得到(a1，a2，a3)= (1， 0， 0)的分量a1=1 所對應(yīng)集合A1上的置換 unranking(1)= (4， 1)、a2=0 所對應(yīng)集合A2上的置換 unranking(0)= (2， 5)和a3=0 所對應(yīng)集合A3上的置換 unranking(0)= (3， 6); 從而利用向量交織方法得到信息置換m= (7， 9， 8)∈S[7， 9]所對應(yīng)碼字c的冗余位(c(4)，c(5)，c(6)，c(7)，c(8)，c(9))= (4，1)° (2，5)° (3，6)= (4，2，3，1，5，6)．

(3) 碼字c的確定: 由信息置換m=(7， 9， 8)∈S[7， 9]編碼得到的[3+6， 3， 3]系統(tǒng)置換碼的碼字c= (c(1)，c(2)，c(3)，c(4)，c(5)，c(6)，c(7)，c(8)，c(9))= (7， 9， 8)‖ (4， 2， 3， 1， 5， 6)= (7， 9， 8， 4， 2， 3， 1， 5， 6)．

4 系統(tǒng)置換碼的譯碼算法

針對上節(jié)所給出的[k+n，k，d]系統(tǒng)置換碼Cs的編碼方法，利用對稱群上的ranking和unranking映射及文獻(xiàn)[12]給出的切比雪夫距離度量下(n，M，d)置換碼的譯碼思路，下面提出了切比雪夫距離度量下可糾幅度至多為l的強度有限錯誤 [k+n，k，d]系統(tǒng)置換碼Cs的一種譯碼算法 (d≥ 2l+1，l≥0)．

圖2 [k+n, k, d]系統(tǒng)置換碼的譯碼算法流程圖

(4) 信息置換的糾錯: 對于步驟(2)中所得到的冗余位對應(yīng)的參數(shù)a，利用對稱群S[n+1， n+k]上的映射unranking: [0，k!-1]→S[n+1，n+k]得到正確的信息位m= unranking(a)= (c(1)，c(2)， …，c(k))∈S[n+1， n+k]．

5 結(jié) 束 語

針對文獻(xiàn)[9]所構(gòu)造的切比雪夫距離度量下可以糾正“強度有限錯誤”的 [k+n，k，d]系統(tǒng)置換碼缺乏編譯碼方法的問題，利用對稱群上的ranking與 unranking映射以及切比雪夫距離度量下(n，M，d)置換碼的交織技術(shù)，筆者提出了該系統(tǒng)置換碼的一種編碼方法及其相應(yīng)的譯碼方法． 通過計算實例，說明了文中所提出的切比雪夫距離度量下 [k+n，k，d]系統(tǒng)置換碼編碼方法及其相應(yīng)譯碼方法的正確性．