SSDエラー訂正アルゴリズムの過去と現在

エラー訂正コード (ECC) は、送信プロセス中にエラーが発生した後に受信側でエラーを検出して訂正できるコードです。初期の通信分野では広く使用されており、送信側でデータのエンコード、受信側でデータのデコードを完了することで、信頼性の高いデータ伝送を実現していました。広く使用されているストレージ メディアである NAND フラッシュは、PE 時間、データ保持時間、温度、セル間干渉などの要因の影響を受けやすいです。データが書き込まれた後、読み出すときに絶対的な正確性を保証することはできないため、データ回復には ECC アルゴリズムが必要です。

2D NANDフラッシュの時代では、SSDコントローラは一般的にデータの正確性を保護するためにBCHエンコーディングを使用します。BCHのいくつかの特徴

1. 固定のコード長とコードレートの場合、固定の生成多項式と検査多項式のセットが存在するため、これらを個別に設計する必要はありません。

2. エンコードおよびデコードアルゴリズムが比較的固定されている。

3. エラーデータの数が指定値未満の場合、データは 100% 回復できます。データエラーの数が指定値を超える場合、データは 100% 回復できません。

4. BCH コーディングではハード情報のみを受信できます。つまり、有効なデータは 1 ビットでのみ表すことができます。

しかし、3D NAND フラッシュ技術が徐々に成熟するにつれて、3D NAND フラッシュはより優れた信頼性を示すようになりました。そのため、もともと 2D MLC を採用していた製品が 3D TLC に切り替わり (信頼性比較: 2D MLC > 3D TLC > 2D TLC)、SSD マスター コントロールの ECC エンコーディングに対する要件が高まりました。そのため、より強力なエラー訂正機能を備えた低密度パリティ チェック (LDPC) の採用が増えています。

BCH と比較して、LDPC には次の特徴があります。

1. 固定コード長とコードレートの場合、エンコードとデコードに使用する行列（通常はチェック行列）を別々に設計する必要があります。

2. デコードアルゴリズムは多数ありますが、最も一般的なエラー訂正アルゴリズムは計算量が多すぎてハードウェアベースにできません。アルゴリズムの特性とデコード精度のバランスを取り、アルゴリズムを簡素化する必要があります。

3. ソフト情報（つまり、1 つの有効なデータを複数のビットで表すことができる）を受信できます。これが、LDPC が BCH に取って代わる主な理由です。

4. デコードの成功と失敗の間には絶対的な境界はありません。つまり、数ビットだけが間違っている場合はエラー訂正を正常に完了できない可能性がありますが、200 ビットのエラーがあるデータは正常にデコードできます。

5. 同じビットレートでは、コード長が長いほど、エラー訂正能力が強くなります。

上記の 5 つの機能について詳しく説明します。

1. 低密度パリティ検査コードの低密度とは、検査行列のスパース性を指します（「0」要素と「1」要素のみで構成される行列では、「1」要素の割合が非常に低くなります）。 LDPC エンコードとデコードの両方でチェック マトリックスを利用できます。マトリックスの密度が低いということは、エンコードおよびデコード アルゴリズムの複雑さと計算量が少ないことを意味します。 LDPC 符号には、固定長および固定コードレートのチェック行列が多数存在します。しかし、計算量が少なく、複雑性が低く、強力なエラー訂正機能を備えたチェック行列を設計することは、LDPC 符号化アプリケーションでは困難です。

LDPC検査行列H

2. MITのロバート・ギャラガーは1963年に博士論文でLDPC符号を提案したが、復号アルゴリズムが複雑で実装が難しいため広く採用されなかった。 1981 年に Tanner は、グラフィカル モデルを使用してコードワードを記述するという概念を提案しました。これにより、LDPC コードのチェック マトリックスが Tanner グラフと呼ばれる双方向グラフにマッピングされます。Tanner グラフを使用して構築された LDPC コードは、並列デコードによってデコードの複雑さを大幅に軽減できます。

検査行列Hに対応するタナー

それ以来、ますます多くの LDPC デコード アルゴリズムが登場しており、その中で最も人気のあるのは、ビット フリッピング アルゴリズムと Min-Sum アルゴリズムです。同時に、上記 2 つのエラー訂正アルゴリズムに基づいた多くの変種アルゴリズムも登場しており、低コストでデコード精度が向上しています。

次の図は、チャネル上での送信後に「1001」になるコード化されたデータ ビット「1101」のビット反転デコード プロセスを示しています。

1 回の反復後、エラー ビットが修正されます。

3. ソフト情報とは、ビットの値を表すために複数のビットを使用することであり、これは、情報の信頼性を複数ビットの精度で表すことができることと同じです。

ハード情報を使用して、「0」または「1」のみになる情報を表します。ソフト情報は、情報の信頼性をより正確に表現します。ソフト情報は、「0.1」、「0.4」、「0.65」、「0.99」などと表現できます。ソフト情報を使用すると、デコーダーは同じビット レートでより多くのエラーを修正できます。

ただし、ストレージは通信分野とは異なり、メモリから読み取られるデータは 0 または 1 のみです。そのため、ソフト情報はメモリの読み取り方法を変えて複数回読み取ることでしか取得できません。同じ情報を複数回読み取ると、必然的に読み取りパフォーマンスが低下します。そのため、SSD コントローラでは、デコードにソフト情報を使用する確率を可能な限り減らす必要があります。

4. LDPC は確率的復号アルゴリズムです。異なるエラー率の下では復号が成功する確率があり、この確率には明らかな特性があります。デコードするデータのエラー率が低い場合、LDPC デコードに失敗する確率は非常に低く、1E-15 程度まで低くなることもありますが、失敗を 0 にすることは困難です。主な理由は、各マトリックスにトラップ セットがあるためです。トラップ セットに含まれる位置のポイントでデータ エラーが発生すると、LDPC を正常にデコードできません。エラー率が徐々に増加すると、デコードに失敗する確率が急速に増加し、ほぼ 100% の失敗になります。

5. BCH と LDPC の場合、同じ符号化率では、符号長が長いほど、誤り訂正能力が強くなります。市場で一般的な 3D TLC フラッシュのページ サイズ (ページ サイズによってエラー訂正アルゴリズムのビット レートが決まります) について、2KB/4KB BCH と 2KB/4KB LDPC ハード決定デコードのエラー訂正機能を比較しました。コード長が長くなると、同じデコードアルゴリズムと同じビットレートでエラー訂正能力が約 50% 向上します。ロングコードとロングECCアルゴリズムの適用により、エラー訂正アルゴリズムの機能が向上し、SSDマスター制御によって有効化されたLDPCソフト判定デコードの使用が遅延され、ソフト判定デコードの悪影響（パフォーマンスと消費電力の面で）が軽減されました。

要約:

データの正確性は SSD の最も基本的な要件であり、エラー訂正コーディングによってデータの完全性が保証されます。新しいフラッシュ構造がさらに登場するにつれて、エラー訂正コーディング アルゴリズムも徐々に進化しています。 LDPC アルゴリズムは、データの正確性を可能な限り最大限に保証します。さらに、4KB LDPC を採用する SSD コントローラが増えるにつれて、SSD の寿命はさらに延びます。