基于置換理論的等級調(diào)制糾錯碼新構(gòu)造方法*

張用宇

（中國人民解放軍91469部隊，北京 100841）

0 引 言

閃存（Flash Memory）是一種采用浮柵結(jié)構(gòu)的長壽命非易失性存儲器[1]，即使在斷電情況下仍能保持所存儲的數(shù)據(jù)信息。置換碼是一種多進制糾錯碼。近年來，由于陸續(xù)發(fā)現(xiàn)了置換碼在電力線數(shù)據(jù)傳輸和多級閃存等領(lǐng)域的新應(yīng)用[2-3]，置換碼重新引起了學(xué)者的關(guān)注。雖然閃存技術(shù)飛速發(fā)展，但仍然存在兩個問題制約其發(fā)展。一是閃存讀寫操作過程中電荷注入的問題，如過量注入導(dǎo)致的過度編程（單元注入電荷值高于目標(biāo)電荷值）；二是數(shù)據(jù)的可靠性，如閃存中存儲的數(shù)據(jù)受到了電荷泄漏、數(shù)據(jù)保持問題、讀/寫干擾等影響而受到損壞。采用等級調(diào)制方案[4-6]可以避免閃存單元過度編程的風(fēng)險，還可以降低電荷泄漏等噪聲引起的非對稱錯誤影響。當(dāng)讀寫單元的電平值時，僅需要比較不同單元之間的電位值。當(dāng)電位值向一個方向偏離時，它們的等級不會像絕對值受到影響。因此，等級調(diào)制可有效提高寫入速度，減少非對稱錯誤，提高數(shù)據(jù)可靠性。

因為閃存設(shè)備中產(chǎn)生錯誤的特殊性，所以RS碼、LDPC碼等差錯控制編碼方法不能有效糾正這些錯誤?；谥脫Q理論的等級調(diào)制糾錯碼適合于多級閃存中多個單元電位值具有相同等級的等級調(diào)制糾錯方案。與置換碼[7-8]相比，基于置換理論的等級調(diào)制糾錯碼可以有效提高閃存的可靠性，達(dá)到較高的信息存儲率。

針對有限強度錯誤的研究，文獻(xiàn)[2，9]提出了等級調(diào)制糾錯碼的構(gòu)造方法。在Chebychev度量下，Min-Zheng Shieh提出了直接和遞歸的多重置換碼構(gòu)造方法[7]。在此基礎(chǔ)上，本文提出了兩種基于置換理論的等級調(diào)制糾錯碼的構(gòu)造方法，一種是直接方法，即通過多重置換集進行直積運算得到；另一種是間接方法，即通過對已有多重置換集進行運算得到新的多重置換集，進而再進行直積運算構(gòu)造出等級調(diào)制糾錯碼。

1 基本概念

對于正整數(shù)n∈?，設(shè)[]n表示集合{1,2,…,n}，SA是集合A的對稱群，即基數(shù)為n的集合A上所有置換的集合， []nS 簡記為nS。對于具有n個閃存單元的等級調(diào)制編碼，假設(shè)n個閃存記憶單元分別命名為1,2,,n…。每個單元的電平等級記為ic，其中i。n個閃存單元的排序為集合Sn上的一個置換，并設(shè)其中一個置換為一個閃存單元等級相對值由高到低的一個排列。設(shè)表示置換映射其中等級調(diào)制方法由編碼和譯碼兩個函數(shù)定義。編碼函數(shù)輸入信息a∈Q映射成一個置換譯碼函數(shù)D：nSQ→。由于置換f會被可能的擾動影響，影響后的置換記為f′，譯碼的目標(biāo)是使()D fa′=。

定義一個多重集（Multiset）為：

其中，且

考慮一種特殊的情況，令且則多重集變?yōu)椋?/p>

設(shè)是式（2）的對稱群，即式（2）所有置換的集合。

定義1 對于定義f與g之間的切比雪夫距離函數(shù)為：

定義2 基于置換理論參數(shù)為(λ,n,d)的等級調(diào)制碼C定義為 Sn的子集，即其基數(shù)為C中碼字的個數(shù)，記為M，且對于所有,f gC∈，fg≠，有

2 構(gòu)造方法

構(gòu)造1 設(shè),,mdλ∈?，nmλ=，2λ≥，對于

i∈[d]，令：

設(shè)是iA（[]id∈）的對稱群，構(gòu)造多重置換碼的直積，即：

構(gòu)造的碼C是Chebyshev度量下的一個基于置換理論的(,,)n dλ等級調(diào)制碼。

定理1 構(gòu)造的(,,)n dλ等級調(diào)制碼的基數(shù)為：

證明：令,f gC∈是任意2個不同的碼字。對于i∈[n]，有由多重置換集Ai的定義，可知可得對于由Chebyshev距離函數(shù)定義可得：

因此，構(gòu)造的碼C是一個(,,)n dλ多重置換碼。

由構(gòu)造條件可知，d個多重集iA（[]id∈）是多重集的一個劃分，其中n=mλ。設(shè)正整數(shù)[]id∈，如果d不能整除m，每一個多重集iA（[]id∈）中元素的個數(shù)至多為如果d能整除m，每一個多重集中元素的個數(shù)都為在Ai個多重集中恰好有m (m odd)個多重集，其中每個多重集包含個元素。由于每個元素在對應(yīng)的多重集中分別出現(xiàn)λ次，每個多重集中重復(fù)的個數(shù)為其余的個多重集，其中每個多重集包含個元素。考慮到每個元素的重復(fù)次數(shù)，每個多重集中重復(fù)的個數(shù)為因此，構(gòu)造的(λ,n, d)等級調(diào)制碼的基數(shù)為：

例1：設(shè)正整數(shù)11m=，2λ=，3d=。由構(gòu)造1中的定義可得對于表示 A 的對稱群，i即多重集iA上所有置換的集合。它在Chebyshev度量下的最小距離為 d = 3 。例如，當(dāng) i = 3 時，的基數(shù)為由構(gòu)造方法1得到等級調(diào)制碼它在Chebyshev度量下的最小距離為 3d=，碼長即C是一個(2,22,3)等級調(diào)制碼。通過式（6）可得，碼C的基數(shù)M為571 536 000。

例2：設(shè)正整數(shù)12m=，2λ=，3d=。此時，d能整除m。由構(gòu)造1中的定義可得

每一個多重集Ai包含8個元素，集合的基數(shù)都為2 520，在Chebyshev度量下的最小距離為d= 3 。由構(gòu)造方法1得到等級調(diào)制碼其在Chebyshev度量下的最小距離為 3d= ，碼長即C是一個(2,24,3)等級調(diào)制碼。通過式（6），可得碼C的基數(shù)M為16 003 008 000。

構(gòu)造2 設(shè),,mkλ∈?，nmλ=，2λ≥，對于令：

定義運算：

其中

構(gòu)造碼字

定理2 構(gòu)造的碼字C是一個基于置換理論的(,,)n dλ等級調(diào)制碼，其基數(shù)最小距離

證明：由構(gòu)造方法容易得到碼字的長度nmλ=，等級調(diào)制碼C的基數(shù)大小

由構(gòu)造2可知，是最小距離為ikd的多重置換集。令,f gC∈是任意2個不同的碼字，對于有是k的倍數(shù)。因此，最小距離

例3：設(shè)正整數(shù)7m=，2λ=，3k=。由構(gòu)造2給出的方法可得到其基數(shù)13M=，22M= ，32M= 。設(shè)碼1

C是由構(gòu)造1的方法得到的碼長最小距離12d=的(2,6,2)等級調(diào)制碼：

根據(jù)構(gòu)造2的方法，中各碼字在集合1A上構(gòu)成一個多重置換集即：

在Chebyshev度量下最小距離為 k d= 6 。1

同理，設(shè)碼2

C是由構(gòu)造的方法得到的碼長最小距離d2=1的(2,4,1)等級調(diào)制碼：

C2中各碼字在集合 A2上構(gòu)成一個多重置換集

在Chebyshev度量下最小距離為 k d= 3 。2

設(shè)碼3C 是由構(gòu)造的方法得到的碼長最小距離d3=1的(4,2,1)等級調(diào)制碼：

中各碼字在集合3A上構(gòu)成一個多重置換集最小距離為的(2,14,3)等級調(diào)制碼C，其基數(shù)為：

在Chebyshev度量下最小距離為 k d= 3 。3

由提出的構(gòu)造2的方法，可得到一個碼長為

(2,14,3)等級調(diào)制碼C如表1所示。

表1 (2,14,3)等級調(diào)制碼C

3 結(jié) 語

閃存具有高性能、非易失性、能耗低和存儲容量大等優(yōu)點。在多級閃存中，采用等級調(diào)制方案可有效克服閃存的有限強度錯誤。針對這一問題，基于多重置換理論提出了采用直積運算直接和間接等級調(diào)制糾錯碼的兩種構(gòu)造方法，構(gòu)造方法簡單直觀，易于編譯碼，并通過計算實例表明了構(gòu)造方法的正確性。多重置換碼的研究對基于多重置換碼的等級調(diào)制方案的設(shè)計具有重要意義，在多級閃存和無線通信等領(lǐng)域可有效對抗信道中的脈沖噪聲、窄帶噪聲、背景噪聲和衰落等干擾。

[1] Cappelletti P,Golla C,Olivo P,et al.Flash Memories[M].Boston MA:Kluwer,1999.

[2] Tamo I,Schwatz M.Correcting Limited-magnitude Errors in the Rank-modulation Scheme[J].IEEE Transactions on Information Theory,2010,56(06):2551-2560.

[3] 慕建君,趙鵬,焦曉鵬.一種糾單個閃存單元移位錯誤的譯碼方法[J].西安電子科技大學(xué)學(xué)報(自然科學(xué)版),2016,43(06):51-55.

MU Jian-jun,ZHAO Peng,JIAO Xiao-peng.Decoding of Codes Correcting a Single Translocation Error for the Cell’s Level of Flash Memory[J].Journal of Xidian University,2016,43(06):51-55.

[4] Jiang A,Mateescu R,Schwartz M,et al.Rank Modulation for Flash Memories[J].IEEE Transactions on Information Theory,2009,55(06):2659-2673.

[5 Gabrys R,Yaakobi E,Farnoud F.Codes Correcting Erasures and Deletions for Rank Modulation[J].IEEE Communications Letters,2016,62(01):136-150.

[6] Holroyd A E.Perfect Snake-in-the-box Codes for Rank Modulation[J].IEEE Transactions on Information Theory,2017, 63(01):104-110.

[7] Shieh M Z,Tsai S C.Decoding Frequency Permutation Arrays under Chebyshev Distance[J].IEEE Transactions on Information Theory,2010,56(11):5730-5737.

[8] Liu X,Draper S C.LP-decodable Multipermutation Codes[J].IEEE Transactions on Information Theory,2016,62(04):1631-1648.

[9] Kl?ve T,Lin T T,Tsai S C,et al.Permutation Arrays under the Chebyshev Distance[J].IEEE Transactions on Information Theory,2010,56(06):2611-2617.