切比雪夫距離下系統(tǒng)置換碼的編譯碼算法

韓 輝，慕建君，焦曉鵬

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

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

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

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

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

1 置換理論

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

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

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

定義4 對(duì)于給定集合A上的置換f∈SA和子集B?A，通過(guò)保留f中屬于B的元素而去掉其他所有元素后得到的置換稱(chēng)為f在集B上的投影，記為f|B．例如，對(duì)于置換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 對(duì)于給定的對(duì)稱(chēng)群S[n+1，n+k]，若一個(gè)(k+n，k!，d)置換碼C滿足 {g|[n+1，n+k]|g∈C}=S[n+1，n+k]，則稱(chēng)置換碼C為一個(gè) [k+n，k，d]系統(tǒng)置換碼．[k+n，k，d]系統(tǒng)置換碼C的任意一個(gè)碼字的第1到k位表示碼字的信息位，而其第k+1 位到第n+k位表示碼字的冗余位．

2 Ranking置換

對(duì)于集合A上的對(duì)稱(chēng)群SA，為了建立字典序排序中置換f∈SA與其對(duì)應(yīng)位置的關(guān)系，Lehmer給出了對(duì)稱(chēng)群上的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 對(duì)于給定的正整數(shù)d(1≤d≤n)，令Cr= {f∈Sn|f(i)≡i(modd)，i∈ [1，n]}，則Cr是一個(gè)(n，M，d)置換碼[12]，且Cr的碼字個(gè)數(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!]}，其中‖表示向量的級(jí)聯(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)鍵是建立碼字中信息位與冗余位之間確定的對(duì)應(yīng)關(guān)系． 筆者利用對(duì)稱(chēng)群上的ranking及unranking映射和(n，M，d)置換碼Cr的一種交織編碼方法來(lái)建立信息位與冗余位之間的對(duì)應(yīng)關(guān)系．

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

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

(1) 信息置換的ranking映射: 對(duì)于信息置換m∈S[n+1， n+k]，利用對(duì)稱(chēng)群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． 對(duì)于 [3+ 6， 3， 3]系統(tǒng)置換碼Cs，令t= 6/3= 2，下面給出一個(gè)碼字信息位m= (7， 9， 8)∈S[7， 9]的 [3+ 6， 3， 3]系統(tǒng)置換碼Cs的編碼過(guò)程:

(1) 信息置換m=(7， 9， 8)的ranking映射: 對(duì)于[3+6， 3， 3]系統(tǒng)置換碼Cs的信息置換m= (7， 9， 8)∈S[7， 9]，利用對(duì)稱(chēng)群S[7， 9]上的映射ranking:S[7， 9]→ [0，3!-1] 計(jì)算得 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}; 利用對(duì)稱(chēng)群SAi上的映射unranking: [0， |Ai|!-1]→SAi(i∈ [3])， 可得到(a1，a2，a3)= (1， 0， 0)的分量a1=1 所對(duì)應(yīng)集合A1上的置換 unranking(1)= (4， 1)、a2=0 所對(duì)應(yīng)集合A2上的置換 unranking(0)= (2， 5)和a3=0 所對(duì)應(yīng)集合A3上的置換 unranking(0)= (3， 6); 從而利用向量交織方法得到信息置換m= (7， 9， 8)∈S[7， 9]所對(duì)應(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)置換碼的譯碼算法

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

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

(4) 信息置換的糾錯(cuò): 對(duì)于步驟(2)中所得到的冗余位對(duì)應(yīng)的參數(shù)a，利用對(duì)稱(chēng)群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é) 束 語(yǔ)

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