切比雪夫距離下系統置換碼的編譯碼算法

韓 輝，慕建君，焦曉鵬

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

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

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

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

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

1 置換理論

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

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

定義2 對于給定集合A={a1，a2， …，an}上對稱群SA的置換f= (f(1)，f(2)， …，f(n))∈SA，若if(j)，則稱(f(i)，f(j))為置換f的一個逆序． 設N(f(i))表示置換f的逆序中第1個分量為f(i)的逆序的個數 (i∈ [n])，則稱向量(N(f(1))，N(f(2))， …，N(f(n)))為置換f的逆序向量． 而且置換f與其逆序向量是一一對應的關系[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]系統置換碼．[k+n，k，d]系統置換碼C的任意一個碼字的第1到k位表示碼字的信息位，而其第k+1 位到第n+k位表示碼字的冗余位．

2 Ranking置換

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

3 系統置換碼的編碼算法

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

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

(1)

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

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

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

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

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

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

(1) 信息置換m=(7， 9， 8)的ranking映射: 對于[3+6， 3， 3]系統置換碼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!進制形式 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 所對應集合A1上的置換 unranking(1)= (4， 1)、a2=0 所對應集合A2上的置換 unranking(0)= (2， 5)和a3=0 所對應集合A3上的置換 unranking(0)= (3， 6); 從而利用向量交織方法得到信息置換m= (7， 9， 8)∈S[7， 9]所對應碼字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]系統置換碼的碼字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 系統置換碼的譯碼算法

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

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

(4) 信息置換的糾錯: 對于步驟(2)中所得到的冗余位對應的參數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 結 束 語

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