FIT2008（第7回情報科学技術フォーラム）RC-012

フラッシュメモリを用いた大容量 SSD のための2 段階誤り制御符号
Two-Level Error Control Coding for High-Capacity SSD using Flash Memories
金子晴彦∗
松坂拓哉 ∗
藤原英二 ∗
Haruhiko Kaneko
Takuya Matsuzaka
Eiji Fujiwara
1

はじめにフラッシュメモリの急速な大容量化に伴い，ハードディ
スクドライブ (HDD) の代替として，フラッシュメモリにより構成されるソリッドステートドライブ (SSD) が製品化されている．SSD は HDD と比較して消費電力が少なく，また耐衝撃性が高いことから，モバイル機器への適用に適している．HDD 及び SSD の仕様の例を表 1 に示す．フラッシュメモリ素子の容量は一般に数ギガビッ
ト程度であることから，SSD は複数のメモリ素子を用いて構成される．本稿では，大容量 SSD の誤り特性について述べ，高信頼化に有効な 2 段階誤り制御符号を提案する．
表1

SSD 及び HDD の仕様の例

る場合がある [4]．このような誤りを訂正・検出するため，各ページの情報部を符号化するための誤り制御符号として，一般に Hamming 符号や BCH 符号 [5] が用いられている．
フラッシュメモリを用いた SSD を大容量化するための手法として，メモリ素子の製造プロセスの微細化，多値レベルセルの採用，等によりメモリ素子の記憶容量を大きくする手法，及びメモリ素子数を増やしてドライブの記憶容量を大きくする手法が考えられる．しかし，これらの手法は信頼性の観点から以下のような問題を有する．

• 製造プロセスの微細化に伴い，ノイズや放射線等に対する耐性が低下し，ソフトエラーの発生が増加する．
• 多値レベルセルを用いることにより閾値電圧の間隔が狭くなり，読み出し値に誤りが発生する [6]．
• メモリ素子の数を増やすことにより，装置全体での故障率が上昇する．すなわち，メモリ素子の故障率を p とすると，N 個のメモリ素子を用いた装置の故障率は 1 − (1 − p)N となる．メモリ素子が故障した場合，ページ内のデータはすべて消失する．

2

フラッシュメモリの構成と大容量ソリッドステートドライブ (SSD) における誤りの特性
SSD において一般に用いられている NAND 型フラッシュメモリは，図 1 に示すようなページ構成を有する [3]．
ここで，メモリの記憶領域は M ページに分割され，各ページは n × b ビットを有する 2 次元配列で表現される．よって，メモリの記憶容量は M × n × b ビットである．各ページは情報を記憶するための情報部と，誤り制御符号の検査ビットを記憶するための検査部からなる．
情報部及び検査部の大きさはそれぞれ k × b ビット及びr × b ビットである．例えば，4Gb のフラッシュメモリ
は，k = 2048 ビット，r = 64 ビット，b = 8 ビット，M = 256K ページとすることにより構成できる．
フラッシュメモリセルでは，浮遊ゲートに電荷を蓄えることにより情報を記憶するため，浮遊ゲートにおける電荷量の変動などにより記憶している情報に誤りが生じ

大容量 SSD における誤りの特性を図 2 に示す．このことから，大容量 SSD に対する誤り制御符号として，従来よりも多数のランダム誤りを効率的に訂正し，かつメモリ素子の故障による消失データを復元できる能力を有する符号が有効である．

3

大容量 SSD に対する 2 段階誤り制御符号
SSD は，データを記憶するための N − 1 個のメモリ素子と，これらの素子に対するパリティ検査ビットを記憶するためのメモリ素子を有するものとし，これに対し2 段階誤り制御符号を適用する手法を提案する．すなわ
ち，図 3 に示すように，N 個のメモリ素子から出力される N ページのグループをクラスタと称し，各ページに対してランダムビット誤り訂正符号 C を適用するとともに，クラスタに対して単一消失訂正パリティ検査符号を適用する．図 3 において，Di (i ∈ {0, 1, . . . , N − 2}) はページ内における kb ビットの情報部を示す．また，符号 C の情報長は K = kb ビット，検査長は R ≤ rb ビット，符号長は N = K + R ビットである．

図 1 NAND 型フラッシュメモリの構成∗ 東京工業大学 大学院情報理工学研究科

図259（第1分冊）

大容量 SSD における誤りの特性

FIT2008（第7回情報科学技術フォーラム）図32 段階誤り制御符号を用いた符号化

図5

図42. 誤り検出ベクトル F の Hamming 重み w(F ) を求め，以下の処理を行なう．
e0 ⊕(i) w(F ) = 0 の場合: シンドロームを S = U
e N −1 とおく．シンドローム S が全零で··· ⊕ U
e 0, . . . , U
e N−2 ) の情報部を出力して終あれば (U符号化手順

3.1 符号化手順
書き込みデータを 2 元 k × b(N − 1) 行列 D とおく．
ここで，書き込みデータ D のサイズはクラスタにおける情報部のサイズと同一である．データ D の書き込み手順は以下のとおりである．
1. 書き込みデータ D を N − 1 個のブロックに等分割し，D = (D0 , . . . , DN −2 ) とする．ただし，Di (0 ≤i ≤ N − 2) は k × b 行列である．
2. パリティ検査ビットを DN −1 = D0 ⊕ · · · ⊕ DN −2 とおく．ただし，DN −1 は 2 元 k × b 行列であり，⊕ は2 元行列の GF(2) 上での加算を示す．
−1
3. すべての i ∈ ZN= {0, 1, . . . , N − 1} について，0Di を符号 C により符号化し，(k + r) × b ビットを有する符号語 Ui を得る．

4.

復号手順

−1
すべての i ∈ ZNについて，Ui を第 i 番目のメモ0リ素子へ書き込む．
符号化手順を図 4 に示す．

3.2 復号手順
メモリ素子から読み出した N ページからなるクラスタを U0 = (U00 , . . . , U0N −1 ) とおき，このクラスタに対す
る誤り検出ベクトルを F = (f0 , . . . , fN −1 ) = (0, . . . , 0)
−1と初期化する．ただし，i ∈ ZNに対して，U0i は 2 元0(k + r) × b 行列である．クラスタ U0 に存在する誤りを訂正するための復号手順は以下のとおりである．
−1
1. すべての i ∈ ZNについて，U0i を符号 C により復0e i とおく．ただし，符号 C によ号し，復号結果を Ue i = U0 とり訂正不可能な誤りを検出した場合は，Uiおき，fi = 1 とする．

了する．それ以外の場合は，誤りを検出して終了する．
(ii) w(F ) = 1 の場合: 誤りが検出されたメモリ素子の位置を l とする．すなわち，fl = 1 であり，−1i ∈ ZN− {l} に対して fi = 0 であるとする．
0e l を以下の式により計算する．
UXeiel =UU
1−{l}i∈ZN−0

ただし，Pは GF(2) 上の和を示す．最後に

e 0, . . . , U
e N −2 ) の情報部を出力して終了する．
(U(iii) w(F ) ≥ 2 の場合: 誤りを検出して終了する．
復号手順を図 5 に示す．

3.3 スペア素子を用いた消失データの回復
SSD 内部にスペアのメモリ素子を用いることにより，素子故障による消失データを回復することができる．N 個のメモリ素子のうち第 l 番目の素子が故障し，ページ Ul のデータが消失したと仮定する．故障素子以外の N − 1 素子から読み出したページの組を(U00 , . . . , U0l−1 , U0l+1 , . . . , U0N −1 ) とおく．このとき消失したページ Ul は以下の手順により回復する．
−11. すべての i ∈ ZN− {l} について，U0i を符号 C に
0e i とおく．ただし，符号より復号し，復号結果を UC により訂正不可能な誤りを検出した場合は，消失データの復元は不可能であるから終了する．
2. 以下の式により消失データ Ul を復元する．
Xei
Ul =U60（第1分冊）

1i∈ZN−−{l}0FIT2008（第7回情報科学技術フォーラム）表2

評価に用いる符号 C のパラメータ

PD ,PEw=8, k’=2048, r’=60
Simulated value of PDBCH
Theoretical value of PDBCH-210 -1
1010 -310 -410 -510 -610 -7

Simulated value of PEBCH
Theoretical value of PEBCH

10 -8
3.0x10 -4

3. 復元したデータ Ul をスペア素子に書き込む．
4 評価
4.1 ランダムビット誤り訂正能力提案した 2 段階誤り制御符号のランダムビット誤りに対する訂正能力を評価するため，以下の確率を求める．
正復号率 PC : クラスタが正常に復号される確率．すな
わち復号後のクラスタと書き込んだクラスタが一致する確率．
誤り検出率 PD : クラスタの復号時に誤りを検出し，正しいクラスタが得られない確率．
誤訂正率 PE : 復号後のクラスタが書き込んだクラスタと一致せず，かつ誤り検出もされない確率．
上記の定義より PC + PD + PE = 1 である．
以下の評価では，符号 C として t ビット誤り訂正 BCH符号を用いる．ただし，フラッシュメモリのページサイズは一般に 2KB 程度であるため，符号 C として単一の符号を用いると復号回路量が増大する可能性がある．例
えば，符号長 n0 = 17194 ビットを有する t0 = 102 ビット
誤り訂正 BCH 符号の復号回路を，0.13 µm CMOS 回路で実装した場合，回路面積は 2.14 mm2 ，遅延は 40.2 µs，スループットは 1.6 Gbps となる [7]．
復号回路量の削減が必要となる場合を考慮し，ページの情報部を w 個に分割してそれぞれに BCH 符号を適用する場合についても評価する．ここで，BCH 符号の情報長を k 0 ビット，検査長を r0 ビット，符号長を n0 = k 0 +r0 ビットとする．ただし，k 0 w ≥ K = kb かつ r0 w ≤ R = rbである．以下では符号 C として，表 2 に示す 3 種の符号 C1 , C2 及び C3 を用いる．
フラッシュメモリ素子におけるランダムビット誤りの発生確率を ² とする．符号長 n0 ビット，検査長 r0 ビットを有する t ビット誤り訂正 BCH 符号について，受信語をBCH正しく復号する確率 PCBCH ，誤りを検出する確率 PD，BCH
及び受信語を誤訂正する確率 PE
はそれぞれ以下の式により与えられる．
Pt ¡ 0 ¢0PCBCH = i=0 ni ²i (1 − ²)n −iµ0 ¶Pt(ni )
BCHPD' (1 − PCBCH ) × 1 − i=02r 0

PEBCH ' (1 − PCBCH ) ×

Pt0(ni )i=02r 0

図6

6.0x10 -4 1.0x10 -3
Bit error rate ε

2.0x10 -3

BCHと誤訂正率 PEBCHBCH 符号の誤り検出率 PD

BCH
ただし，PD及び PEBCH の値は，受信語に訂正不可能な誤りが存在するとき，受信語のシンドロームはシンドローム空間上に均一に分布するという仮定 [5] の下でのBCH及び誤訂理論値である．BCH 符号の誤り検出率 PD
BCHについて，上記の理論値と計算機シミュレー正率 PE
ションによる値の例を図 6 に示す．ここで，BCH 符号
は符号長 n = 2108 ビット，検査長 60 ビットを有するラBCH
ンダム 5 ビット誤り訂正符号である．図 6 より，PD及び PEBCH の理論値とシミュレーションによる値がほぼ一致することが示された．
復号手順の 1 において，ページ U0i が正しく復号される確率を PCPG ，ページ U0i に誤りが検出される確率をPG
PD，ページ U0i が正しく復号されず，かつ誤り検出もされない確率を PEPG とする．これらの確率は以下の式により与えられる．

PCPG = (PCBCH )w©Pw ¡w¢ BCH iª
PG
BCH w−iPD=) (1 − PD)
i=1 i (PD©Pw ¡w¢ BCH i BCH w−i ª
PEPG =) (PC )i=1 i (PE
上記の確率を用いて，クラスタの正復号率 PCCL ，誤りCL検出率 PD
及び誤訂正率 PECL はそれぞれ以下の式で与えられる．
PG
PCCL = (PCPG )N + N · PD(PCPG )N −1¡¢
PN
CLPG iPG N −i
PD= i=2 Ni (PD) (1 − PD)
+³P
´ ¡¢
¡¢NN
1PG i
PG N −i× 1 − 2nw
i=1 i (PE ) (PC )³P´N ¡N ¢
1PG i
PG N −i+PECL =× 2nwi=1 i (PE ) (PC )³P´
N −1 ¡N −1¢
PG
PG i
PG N −1−i
N · PD(P)(P)
ECi=1iPG
図 7 にページにおける誤り検出率 PD
及びクラスタCLにおける誤り検出率 PD を示す．ほぼすべての領域にCLPG
おいて PD¿ PDとなっていることから，クラスタに対してパリティ検査符号を適用することにより，誤り検出率が大きく低下することが示された．また，符号 Cにおける符号語の分割数 w を小さくすることにより，誤り検出率が低下する．図 8 にページにおける誤訂正率

61（第1分冊）

FIT2008（第7回情報科学技術フォーラム）PD

60

N=8Error Detection Probability

10 -5

50

10 -10
10 -15PDCL

10 -20PDPG

10 -25

MTTDL [years]

Code C3PDPG
Code C2

Code C1
PDCL

PDPG

PDCL

10 -4
Bit error rate ε

10 -5

Miscorrection Probability

PEPG

10 -20

10 -6030200

Without spare chip
20406080 100 120 140 160
MTTF of memory chip [years]

180200

図 9 SSD の記録部 (N = 8 メモリ素子) における平均データ喪失時間場合と比較して 2 倍程度となることが示された．

5PECL
Code C2PECL
Code C1PEPG

10 -80
PECL
10 -5

40

10 -3

Code C3
PEPG

10 -40

Proposed two-level error control codingwith one spare chip

10PG及びクラスタに
図 7 ページにおける誤り検出率 PD
CLおける誤り検出率 PD (符号 C1 , C2 , C3 は表 2 を参照)

PE

N=8 memory chips

10 -4
Bit error rate εN=810 -3

図 8 ページにおける誤訂正率 PEPG 及びクラスタにおける誤訂正率 PECLPEPG 及びクラスタにおける誤訂正率 PECL を示す．誤訂正率は誤り検出率と比較して非常に小さく，また，ほぼすべての領域において PECL ¿ PEPG となっていることから，クラスタに対してパリティ検査符号を適用することにより，誤訂正率も大きく低下することが示された．
上記の結果より，提案手法はメモリ素子のビット誤り率が高い場合でも，十分に信頼度の高いデータの記憶が可能であることが示された．例えば，w = 4 として，メモリ素子におけるビット誤り率を ² = 1.0 × 10−4 としたCL
とき，クラスタの誤り検出確率は PD= 1.0 × 10−17 でCL−26あり，誤訂正率は PE = 1.0 × 10である．
4.2 平均データ喪失時間提案した 2 段階誤り制御符号と 1 個のスペア素子を用いた場合について，メモリ素子の平均故障時間 (MTTF:
mean time to failure) と SSD の平均データ喪失時間(MTTDL: mean time to data loss) の関係を図 9 に示す．
ただし，素子故障とは素子からページを読み出せなくなる状態を意味し，SSD が有するメモリ素子数は N = 8とする．MTTDL はマルコフモデルを用いて導出したものである．比較として，スペア素子を用いない場合のMTTDL を同図に示す．2 段階誤り制御符号とスペア素子を用いた場合の MTTDL は，スペア素子を用いないまとめ
本稿ではフラッシュメモリを用いた大容量ソリッドス
テートドライブ (SSD) のための 2 段階誤り制御符号を提案した．フラッシュメモリ素子の各ページにランダムビット誤り訂正符号を適用することに加えて，N 個のメモリ素子から出力される N ページの組をクラスタと称し，クラスタに対して単一消失訂正パリティ検査符号を適用することにより，2 段階誤り制御符号を構成する手法を示した．提案手法について，クラスタの誤り検出率及び誤訂正率を導出し，本手法により信頼度の高いデータの記憶が可能であることを示した．例えば，メモリ素子におけるビット誤り率を ² = 1.0 × 10−4 としたとき，CLクラスタの誤り検出確率は PD= 1.0 × 10−17 であり，誤訂正率は PECL = 1.0 × 10−26 である．
今後はメモリ素子への書き込み回数を考慮した信頼性の評価と，符号化・復号回路の構成及び評価を行なう必要がある．
参考文献[1] http://www.sandisk.com/Assets/File/pdf/oem/
SSD Family Brochure.pdf[2] http://www.hitachigst.com/tech/techlib.nsf/techdocs/
AAD443B70157A1B18625738600704C2C/$file/
CinemaStar C5K250 datasheet.pdf[3] 肥後, 金子, 藤原; 半導体ファイル記憶システムにおける誤り制御符号の構成; 信学技報, FIIS-07-197, March 2007.
[4] S. Gregori, A. Cabrini, O. Khouri, and G. Torelli, “OnChip Error Correcting Techniques for New-GenerationFlash Memories,” Proc. of the IEEE, Vol.91, No.4,pp.602–616, April 2003.
[5] E. Fujiwara, Code Design for Dependable Systems,
Theory and Practical Applications, Wiley-Interscience,2006.
[6] M. Grossi, M. Lanzoni, and B. Ricco, “Program
Schemes for Multilevel Flash Memories,” Proc. of theIEEE, Vol.91, No.4, pp.594–600, April 2003.
[7] http://www.ecse.rpi.edu/Homepages/tzhang/RVSAL/
pub/FLASHSiPS06.pdf

62（第1分冊）