(57)【要約】  本発明の方法には、情報ビットの第１のセットに対応する第１のパリティビットの第１のセットおよび情報ビットの第２のセットに対応する第１のパリティビットの第２のセットを生成する第１の代数エラー訂正符号と関連付けられた第１の符号化動作が含まれる。第２の代数エラー訂正符号と関連付けられた第２の符号化動作は、情報ビットの第１のセットに対応する第２のパリティビットの第１のセットおよび情報ビットの第２のセットに対応する第２のパリティビットの第２のセットを生成する。第３の符号化動作は、ジョイントパリティビットのセットを生成する。情報ビットの第１のセット、情報ビットの第２のセット、第１のパリティビットの第１のセット、第１のパリティビットの第２のセットおよびジョイントパリティビットは、単一の符号語としてデータストレージデバイスに格納され得る。
2015507409.tif 000002
【特許請求の範囲】
【請求項１】
データを符号化する方法であって、
データストレージデバイスにおいて、
情報ビットの第１のセットに対応する第１のパリティビットの第１のセットを生成するとともに情報ビットの第２のセットに対応する第１のパリティビットの第２のセットを生成するために、代数符号である第１のエラー訂正符号と関連付けられた第１の符号化動作を開始するステップと、
情報ビットの第１のセットに対応する第２のパリティビットの第１のセットを生成するとともに情報ビットの第２のセットに対応する第２のパリティビットの第２のセットを生成するために、第１のエラー訂正符号より大きなエラー訂正能力を有する他の代数符号である第２のエラー訂正符号と関連付けられた第２の符号化動作を開始するステップと、
情報ビットの第１のセットおよび情報ビットの第２のセットと関連付けられるジョイント情報ビットのセットに対応するジョイントパリティビットのセットを生成するために、第３の符号化動作を開始するステップと、
情報ビットの第１のセット、情報ビットの第２のセット、第１のパリティビットの第１のセット、第１のパリティビットの第２のセットおよびジョイントパリティビットを単一の符号語として前記データストレージデバイスのメモリに格納するステップと、
を実行することを含む方法。
【請求項２】
請求項１記載の方法において、
ジョイントパリティビットに対応するジョイントパリティ保護ビットのセットを生成するために、第４の符号化動作を開始するステップをさらに含み、
単一の符号語は、ジョイントパリティ保護ビットのセットをさらに含む方法。
【請求項３】
請求項１記載の方法において、
第３の符号化動作は、単一の消去を訂正し得るシングルパリティ検査符号を含む方法。
【請求項４】
請求項１記載の方法において、
第３の符号化動作は、非バイナリ代数符号を含む方法。
【請求項５】
請求項１記載の方法において、
第１のエラー訂正符号は、第１の生成多項式に対応し、
ジョイント情報ビットのセットは、第１の生成多項式で除された第２のパリティビットの第１のセットを含むとともに第１の生成多項式で除された第２のパリティビットの第２のセットを含む方法。
【請求項６】
データを復号化する方法であって、
データストレージデバイスにおいて、
復号化の第１のフェーズの間に、第１のエラー訂正符号と関連付けられた第１の復号化動作を開始するステップと、
第１の復号化動作での復号化失敗に応答して復号化の第２のフェーズを開始するステップと、を実行することを含み、
第１の復号化動作は、符号語の情報ビットの第１のセットおよび第１のパリティビットの第１のセットを用い、
第１のエラー訂正符号は、代数符号であり、
符号語は、情報ビットの第２のセット、第１のパリティビットの第２のセットおよびジョイントパリティビットのセットをさらに含み、
前記第２のフェーズには、
情報ビットの第２のセットおよびパリティビットの第２のセットを用いて、第１のエラー訂正符号と関連付けられる第２の復号化動作を開始し、
情報ビットの第２のセットに対応する第２のパリティビットの第２のセットを生成するために、第１のエラー訂正符号より大きなエラー訂正能力を有する他の代数符号である第２のエラー訂正符号と関連付けられた符号化動作を開始し、
第１の情報ビットと関連付けられる第２のパリティビットの第１のセットに対応するジョイント情報ビットを生成するために、第２のパリティビットの第２のセットに対応するジョイントパリティビットおよびジョイント情報ビットのセットを用いて第３の復号化動作を開始し、かつ
情報ビットの第１のセットおよび第２のパリティビットの第１のセットを用いて、第２のエラー訂正符号と関連付けられる第４の復号化動作を開始することが含まれる方法。
【請求項７】
請求項６記載の方法において、
符号語は、ジョイントパリティ保護ビットのセットをさらに含み、
前記方法は、第３の復号化動作を開始する前にジョイントパリティビットのセットの中のエラーを訂正するためにジョイントパリティビットのセットおよびジョイントパリティ保護ビットのセットを用いるジョイントパリティ復号化動作を開始するステップをさらに含む方法。
【請求項８】
請求項７記載の方法において、
ジョイントパリティ復号化動作は、単一の消去を訂正し得るシングルパリティ検査符号に基づく方法。
【請求項９】
請求項７記載の方法において、
ジョイントパリティ復号化動作は、非バイナリ代数符号に基づく方法。
【請求項１０】
請求項６記載の方法において、
第１のエラー訂正符号は、第１の生成多項式に対応し、
第２のパリティビットの第２のセットに対応するジョイント情報ビットは、第１の生成多項式で除された第２のパリティビットの第２のセットを含む方法。
【請求項１１】
データストレージデバイスであって、
メモリと、
マルチフェーズエラー訂正符号（ＥＣＣ）エンコーダと、を備え、
前記マルチフェーズＥＣＣエンコーダは、
代数符号である第１のエラー訂正符号と関連付けられ、情報ビットの第１のセットに対応する第１のパリティビットの第１のセットを生成するとともに情報ビットの第２のセットに対応する第１のパリティビットの第２のセットを生成するように構成された第１のエンコーダと、
第１のエラー訂正符号より大きなエラー訂正能力を有する他の代数符号である第２のエラー訂正符号と関連付けられ、情報ビットの第１のセットに対応する第２のパリティビットの第１のセットを生成するとともに情報ビットの第２のセットに対応する第２のパリティビットの第２のセットを生成するように構成された第２のエンコーダと、
情報ビットの第１のセットおよび情報ビットの第２のセットと関連付けられるジョイント情報ビットのセットに対応するジョイントパリティビットのセットを生成するように構成された第３のエンコーダと、を備え、かつ
前記メモリに格納されるべき情報ビットの第１のセット、情報ビットの第２のセット、第１のパリティビットの第１のセット、第１のパリティビットの第２のセットおよびジョイントパリティビットを含む符号語を生成するように構成されるデータストレージデバイス。
【請求項１２】
請求項１１記載のデータストレージデバイスにおいて、
前記マルチフェーズＥＣＣエンコーダは、
ジョイントパリティビットに対応するジョイントパリティ保護ビットのセットを生成するように構成された第４のＥＣＣエンコーダをさらに備え、かつ
ジョイントパリティ保護ビットのセットを符号語に含めるように構成されるデータストレージデバイス。
【請求項１３】
請求項１１記載のデータストレージデバイスにおいて、
前記第３のエンコーダは、符号語あたりに単一の消去を訂正し得るシングルパリティ検査符号を用いるように構成されるデータストレージデバイス。
【請求項１４】
請求項１１記載のデータストレージデバイスにおいて、
前記第３のエンコーダは、非バイナリ代数符号を用いるように構成されるデータストレージデバイス。
【請求項１５】
請求項１１記載のデータストレージデバイスにおいて、
第１のエラー訂正符号は、第１の生成多項式に対応し、
ジョイント情報ビットのセットは、第１の生成多項式で除された第２のパリティビットの第１のセットを含むとともに第１の生成多項式で除された第２のパリティビットの第２のセットを含むデータストレージデバイス。
【請求項１６】
データストレージデバイスであって、
メモリと、
マルチフェーズエラー訂正符号（ＥＣＣ）デコーダと、を備え、
前記マルチフェーズＥＣＣデコーダは、
第１の代数符号である第１のエラー訂正符号と関連付けられ、前記メモリに格納されている符号語の情報ビットの第１のセットおよび第１のパリティビットの第１のセットを受け取るように構成された第１のデコーダであって、前記符号語は情報ビットの第２のセット、第１のパリティビットの第２のセットおよびジョイントパリティビットのセットをさらに含む、第１のデコーダと、
第１のエラー訂正符号より大きなエラー訂正能力を有する他の代数符号である第２のエラー訂正符号と関連付けられ、情報ビットの第１のセットおよび第２のパリティビットの第１のセットを受け取るとともに情報ビットの第１のセットのエラー訂正済みバージョンを生成するように構成された第２のデコーダと、
ジョイントパリティビットのセットおよびジョイント情報ビットのセットを受け取ってジョイント情報ビットのセットのエラー訂正済みバージョンを生成するように構成された第３のデコーダであって、ジョイント情報ビットのセットは情報ビットの第１のセットおよび情報ビットの第２のセットと関連付けられる、第３のデコーダと、を備え、かつ
前記第１のデコーダを用いる情報ビットの第１のセットの第１のフェーズ復号化を実行するとともに、第１のフェーズ復号化中の復号化失敗に応答して、第２のフェーズ復号化を実行するように構成され、
前記第２のフェーズ復号化には、
前記第１のデコーダを用いて情報ビットの第２のセットを復号化し、
情報ビットの第２のセットに対応する第２のパリティビットの第２のセットを生成し、
前記第３のデコーダを用いて情報ビットの第１のセットに対応するジョイント情報ビットを復号化し、かつ
前記第２のデコーダを用いて情報ビットの第１のセットを復号化することが含まれ、
前記第２のデコーダに提供される第２のパリティビットの第１のセットは、情報ビットの第１のセットに対応する復号化済みジョイント情報ビットに対応するデータストレージデバイス。
【請求項１７】
請求項１６記載のデータストレージデバイスにおいて、
符号語は、ジョイントパリティ保護ビットのセットをさらに含み、
前記マルチフェーズＥＣＣデコーダは、ジョイントパリティビットのセットおよびジョイントパリティ保護ビットのセットを用いてジョイントパリティビットのセットのエラー訂正済みバージョンを生成するために、ジョイントパリティ復号化動作を実行するように構成された第４のデコーダをさらに備えるデータストレージデバイス。
【請求項１８】
請求項１７記載のデータストレージデバイスにおいて、
ジョイントパリティ復号化動作は、符号語あたりに単一の消去を訂正し得るシングルパリティ検査符号に基づくデータストレージデバイス。
【請求項１９】
請求項１７記載のデータストレージデバイスにおいて、
ジョイントパリティ復号化動作は、非バイナリ代数符号に基づくデータストレージデバイス。
【請求項２０】
請求項１６記載のデータストレージデバイスにおいて、
第１のエラー訂正符号は、第１の生成多項式に対応し、
情報ビットの第１のセットに対応するジョイント情報ビットは、第１の生成多項式で除された第２のパリティビットの第１のセットを含むデータストレージデバイス。
【請求項２１】
請求項１記載の方法において、
第２のエラー訂正符号の符号語のビットのサブセットは、第１のエラー訂正符号の符号語を構成する方法。
【請求項２２】
請求項６記載の方法において、
第２のエラー訂正符号の符号語のビットのサブセットは、第１のエラー訂正符号の符号語を構成する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、エラー訂正符号（ＥＣＣ）データの復号化に関する。
【背景技術】
【０００２】
ユニバーサルシリアルバス（ＵＳＢ）フラッシュメモリデバイスあるいは取り外し可能なストレージカードなどの不揮発性データストレージデバイスは、データおよびソフトウェアアプリケーションの可搬性の向上を可能にしている。フラッシュメモリデバイスは、各フラッシュメモリセルに複数のビットを格納することによってデータストレージ密度を高めることができる。例えば、マルチレベルセル（ＭＬＣ）フラッシュメモリデバイスは、セルあたりに３ビット、セルあたりに４ビット、あるいはそれ以上を格納することによって大きくされたストレージ密度を提供する。セルあたりのビット数を大きくし、かつデバイスフィーチャ寸法を小さくすることによってメモリデバイスのストレージ密度を大きくすることはできるけれども、メモリデバイスに格納されたデータのビットエラー率も大きくなることがある。
【０００３】
エラー訂正符号（ＥＣＣ）は、メモリデバイスからのデータ読み出し時に発生するエラーを訂正するためによく使われる。格納される前に、データは、データとともに格納され得る冗長情報（例えば、「パリティビット」）を生成するためにＥＣＣエンコーダによって符号化され得る。例えば、ＥＣＣは、ハミング符号化方式、リードソロモン（ＲＳ）符号化方式、ボーズ−チャウドゥリ−ホッケンゲム（ＢＣＨ）符号化方式などの代数符号に基づくことができ、あるいはターボ符号の符号化方式または低密度パリティチェック（ＬＤＰＣ）符号化方式などの反復符号化方式に基づくことができる。
【０００４】
ＥＣＣ方式の効率は、種々の態様に基づいて測られ得る。例えば、その効率は、所与の量の冗長性で補正され得るエラーの量、あるいは特定のエラー率に起因するエラーが生じるデータの訂正のための冗長性の量などの、冗長性と比べてのエラー訂正能力に基づいて測られ得る。代わりにあるいはこのことに加えて、その効率は、ＥＣＣエンジンの複雑さ（例えば、ＥＣＣコアのサイズまたはコスト）、ＥＣＣエンジンのパワー消費量、あるいは復号化スループットおよび待ち時間に少なくとも部分的に基づいて測られ得る。例えば、ランダム読み出し性能は、モバイルデバイスアプリケーションのためのソリッドステートドライブ（ＳＳＤ）およびメモリカードなどで、スループットが大きくなり待ち時間が減少すると、向上する。
【発明の概要】
【０００５】
マルチフェーズＥＣＣ方式において代数符号が使用される。データは情報ビットの複数のセットとして符号化され得る。情報ビットの各セットについて、パリティビットの第１のセットを生成するために第１の符号が使用され、パリティビットの第２のセットを生成するために第２の符号が使用され得る。情報ビットの複数のセットの各々についてのパリティビットの第２のセットは、データのジョイントパリティビットとして機能するパリティビットの第３のセットを生成するために第３の符号を使用して処理され符号化され得る。ジョイントパリティビットは、ジョイントパリティ保護ビットとして機能するパリティビットの第４のセットを生成するために第４の符号を使用して符号化され得る。情報ビット、第１のパリティビット、ジョイントパリティビットおよびジョイントパリティ保護ビットのセットはメモリに格納され得る。
【０００６】
第１の復号化フェーズの間にメモリから情報ビットのセットが読み出される場合に、対応する第１のパリティビットを第１の符号に基づく復号化試行に使用する。第１の復号化フェーズの間に情報ビットのセットについての復号化が失敗したならば、データの情報セットの全てが、第１のフェーズにおいて復号化に失敗した情報のセットについてのパリティビットの第２のセットを生成するためにジョイントパリティビットと関連して第２の復号化フェーズの間に第１の符号に基づいて復号化され、処理され得る。パリティビットの第２のセットを使用する復号化は、第１の符号と比べて改善されたエラー訂正能力を有する第２の符号を使用して実行され得る。
【０００７】
代数符号を使用すれば、ジョイントパリティビットのセットを通して互いに結合された数個のより短いサブ符号（例えば、ＢＣＨサブ符号）の連結としてエラー訂正符号を構築することが可能となる。エラー訂正符号は、長いＬＤＰＣ符号を構築するために連結された低密度パリティチェック（ＬＤＰＣ）サブ符号を用いる実施例などの、比較的に高い複雑度の反復デコーダに基づく実施例と比べて、比較的に低い複雑度の復号化エンジンを用いているのに、高いエラー訂正能力を有する。
【図面の簡単な説明】
【０００８】
【図１】代数符号に基づくマルチフェーズＥＣＣ復号化を用いるように構成されたデータストレージデバイスを含むシステムの特定の実施形態の図である。
【図２】代数符号に基づくマルチフェーズＥＣＣ復号化とともに用いるジョイントパリティビットを生成する第１の実施形態を示す図である。
【図３】代数符号に基づくマルチフェーズＥＣＣ復号化とともに用いるジョイントパリティビットを生成する第２の実施形態を示す図である。
【図４】代数符号に基づくマルチフェーズＥＣＣ復号化とともに用いるジョイントパリティビットを生成する第３の実施形態を示す図である。
【図５】代数符号に基づくマルチフェーズＥＣＣ符号化の方法の特定の実施形態のフローチャートである。
【図６】代数符号に基づくマルチフェーズＥＣＣ復号化の方法の特定の実施形態のフローチャートである。
【発明を実施するための形態】
【０００９】
図１を参照すると、代数符号に基づくマルチフェーズＥＣＣ復号化を用いるように構成されたデータストレージデバイス１０２を含むシステム１００の特定の例示的な実施形態が描かれている。システム１００は、ホストデバイス１３０に結合されたデータストレージデバイス１０２を含む。データストレージデバイス１０２は、コントローラ１０６に結合されたメモリ１０４を含む。コントローラ１０６は、代数符号に基づくマルチフェーズＥＣＣ復号化を可能にするためにメモリ１０４に格納されるべきデータを符号化するように構成されている。コントローラ１０６は、代数符号に基づくマルチフェーズＥＣＣ復号化を用いてメモリ１０４から読み出されたデータを復号化するようにも構成されている。
【００１０】
ホストデバイス１３０は、メモリ１０４に格納されるべきデータを提供するか、あるいはデータをメモリ１０４から読み出すことを要求するように構成され得る。例えば、ホストデバイス１３０は、携帯電話機、音楽もしくはビデオプレーヤ、ゲームコンソール、電子ブックリーダ、個人用携帯情報端末（ＰＤＡ）、ラップトップコンピュータ、ノートブックコンピュータ、もしくはタブレットなどのコンピュータ、他の任意の電子装置、またはそれらの任意の組み合わせを含み得る。
【００１１】
データストレージデバイス１０２は、Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ（登録商標）（ＳＤ）カード、ｍｉｃｒｏＳＤ（登録商標）カード、ｍｉｎｉＳＤ（登録商標）カード（デラウェア州ウィルミントンのＳＤ−３Ｃ  ＬＬＣの商標）、ＭｕｌｔｉＭｅｄｉａＣａｒｄ（登録商標）（ＭＭＣ（登録商標）カード（バージニア州アーリントンのJEDEC Solid State Technology Associationの商標）、またはＣｏｍｐａｃｔＦｌａｓｈ（登録商標）（ＣＦ）カード（カリフォルニア州ミルピタスのサンディスク  コーポレーションの商標）などのメモリカードであり得る。他の例として、データストレージデバイス１０２は、実例として、ｅＭＭＣ（登録商標）（バージニア州アーリントンのJEDEC Solid State Technology Associationの商標）メモリおよびｅＳＤメモリなどの、ホストデバイス１３０内のソリッドステートドライブ（ＳＳＤ）または埋め込みメモリであり得る。
【００１２】
メモリ１０４はフラッシュメモリを含み得る。例えば、メモリ１０４は、ＮＡＮＤフラッシュデバイス、ＮＯＲフラッシュデバイス、または他の任意のタイプのフラッシュデバイスなどの、フラッシュデバイスの不揮発性メモリであり得る。メモリ１０４は、マルチレベルセル（ＭＬＣ）メモリのメモリセルなどの、複数の記憶素子を含む。
【００１３】
コントローラ１０６は、データストレージデバイス１０２がホストデバイス１３０に動作可能に結合されている間、ホストデバイス１３０からメモリアクセス要求を受け取るように構成され得る。例えば、コントローラ１０６は、ホストデバイス１３０からデータ１４０を受け取り、データ１４０を符号化して符号語１４９を生成し、符号語１４９をメモリ１０４に格納するように構成され得る。コントローラ１０６は、データ１４０を取り出す要求をホストデバイス１３０から受け取るようにも構成され得る。これに応答して、コントローラ１０６は、メモリ１０４から符号語１５９を読み出し、符号語１５９の要求された１つ以上の部分を、符号語１５９の要求された部分に生じているかも知れないビットエラーを訂正するために、復号化し、復号化済みデータ１７０をホストデバイス１３０に提供するように構成され得る。符号語１５９は符号語１４９の１つの表現であり得る。すなわち、符号語１５９は、メモリ１０４での格納中に生じたかもしれない１つ以上のビットエラーに起因して符号語１４９とは異なり得る。
【００１４】
コントローラ１０６は、代数符号に基づくマルチフェーズＥＣＣ復号化を可能にするためにデータを符号化するように構成されたマルチフェーズＥＣＣ符号化エンジン１１０を含む。マルチフェーズＥＣＣ符号化エンジン１１０は、第１のＥＣＣエンコーダ１１２、第２のＥＣＣエンコーダ１１４、第３のＥＣＣエンコーダ１１６、および第４のＥＣＣエンコーダ１１８を含み得る。コントローラ１０６は、代数符号に基づくマルチフェーズＥＣＣ復号化に従ってデータを復号化するように構成されたマルチフェーズＥＣＣ復号化エンジン１２０を含む。ＥＣＣ復号化エンジン１２０は、第１のＥＣＣデコーダ１２２、第２のＥＣＣデコーダ１２４、第３のＥＣＣデコーダ１２６、および第４のＥＣＣデコーダ１２８を含み得る。
【００１５】
第１のＥＣＣエンコーダ１１２は、第１の代数符号に従ってデータを符号化してパリティビットの第１のセットを生成するように構成される。例えば、第１の代数符号はハミング符号、リードソロモン（ＲＳ）符号、あるいはボーズ−チャウドリ−ホッケンゲム（ＢＣＨ）符号であり得る。本願明細書で用いられる「代数符号」は、生成多項式により定義される任意の巡回（または非巡回）符号を含むことができ、ターボ符号および低密度パリティチェック（ＬＤＰＣ）などの反復符号化方式を除外する。特別な例として、第１のＥＣＣエンコーダ１１２は、次数ｍ1 の多項式生成関数ｇ1 （ｘ）を入力データに適用してｍ1 個の第１のパリティビットのセットを生成することができる。パリティビットの第１のセットは、メモリ１０４から取り出されたデータの第１の復号化フェーズの間に用いられ得る。
【００１６】
第２のＥＣＣエンコーダ１１４は、データを第２の代数符号に従って符号化してパリティビットの第２のセットを生成するように構成される。第２の代数符号は第１の代数符号より強力であり得る（すなわち、より強いエラー訂正能力を提供し得る）。例えば、第２のＥＣＣエンコーダ１１４は、次数ｍ1 ＋ｍ2 の多項式生成関数ｇ（ｘ）を適用してｍ1 ＋ｍ2 個の第２のパリティビットを生成することができる。第２のＥＣＣエンコーダ１１４は次数ｍ1 ＋ｍ2 の多項式生成関数ｇ（ｘ）＝ｇ１（ｘ）・ｇ２（ｘ）を適用することができ、ここでｇ１（ｘ）は（次数ｍ1 を有する）第１の代数符号の多項式生成関数であり、ｇ２（ｘ）は追加のｍ2 個のパリティビットを生成する次数ｍ2 の多項式生成関数である。パリティビットの第２のセットは、メモリ１０４から取り出されたデータの第２の復号化フェーズの間に用いられ得る。
【００１７】
第３のＥＣＣエンコーダ１１６は、データを第３の代数符号に従って符号化してパリティビットの第３のセットを生成するように構成される。図２〜４に関して以下でさらに詳しく記述するように、第３の代数符号は、ジョイントパリティビットを生成するために（第２のＥＣＣエンコーダ１１４の出力に基づいて）ジョイント情報ビットの複数のセットの部分に適用され得る。
【００１８】
第４のＥＣＣエンコーダ１１８は、データを第４の代数符号に従って符号化してパリティビットの第４のセットを生成するように構成される。第４の代数符号は、ジョイントパリティ保護ビットを形成するためにジョイントパリティビットに適用され得る。
【００１９】
マルチフェーズＥＣＣ符号化エンジン１１０は、データ１４０などのデータを情報ビットの複数のセット（ｉ1 １４１，・・・ｉr １４２）として第１のＥＣＣエンコーダ１１２に提供して情報ビットの各セットのためにパリティビット（ｐ）の第１のセット（すなわち、パリティビットの第１のセットｐ1 １４３，・・・ｐr １４４、ここでセットｐi の各々はｍ1 個のパリティビットをそれぞれ含む）を生成することによって符号語１４９を生成するように構成される。マルチフェーズＥＣＣ符号化エンジン１１０は、情報ビットの各セットのためにパリティビットの第２のセット（ｐ(2) ）（すなわち、それぞれ、パリティビットの第２のセットｐ1 (2) １４５，・・・ｐr (2) １４６、ここでｐi (2) の各々はｍ1 ＋ｍ2 個のパリティビットを含む）を生成するために情報ビットの各セットと第１のパリティビットの対応するセットとを第２のＥＣＣエンコーダ１１４に提供するように構成される。マルチフェーズＥＣＣ符号化エンジン１１０は、第３のＥＣＣエンコーダ１１６において、符号語の第３のセットを生成するように構成されるが、第３の符号語の情報ビットは第２の符号語に基づくものとし（例えば、第２の符号語のパリティビットｐ(2) の部分からなどの、第２の符号語のパリティビットに基づくものとし）、さらにデータ１４０のためにジョイントパリティビット（ｐJ ）１４７を生成するように構成され得る。マルチフェーズＥＣＣ符号化エンジン１１０は、データ１４０のためにジョイントパリティ保護ビット（ｐJP）１４８を生成するためにジョイントパリティビット１４７を第４のＥＣＣエンコーダ１１８に提供するように構成され得る。
【００２０】
マルチフェーズＥＣＣ符号化エンジン１１０は、情報ビットの複数のセット１４１〜１４２、第１のパリティビットの複数のセット１４３〜１４４、ジョイントパリティビット１４７、およびジョイントパリティ保護ビット１４８を含む符号語１４９を生成するように構成され得る。ｐ(2) パリティビットのセット１４５〜１４６は、メモリ１０４に格納されずに廃棄されてもよい。
【００２１】
第１のＥＣＣデコーダ１２２は、第１のＥＣＣエンコーダ１１２により使用された第１の代数符号に従ってデータを復号化するように構成される。第１のＥＣＣデコーダ１２２は、情報ビットのセットおよびパリティビットの対応する第１のセットを受け取ってＥＣＣ復号化動作を行うように構成される。情報ビットおよび第１のパリティビットのビットエラーの数が第１の代数符号のエラー訂正能力を超えなければ、第１のＥＣＣデコーダ１１２は情報ビットの復号化されたセット（すなわち、情報ビットのセットのエラー訂正済みバージョン）を生成する。そうでなければ、情報ビットおよび第１のパリティビットのエラーの数が第１の代数符号のエラー訂正能力を超えていることに応答して、第１のＥＣＣデコーダ１１２は復号化失敗インジケータを生成する。
【００２２】
第２のＥＣＣデコーダ１２４は、第２のＥＣＣエンコーダ１１４により使用された第２の代数符号に従ってデータを復号化するように構成される。第２のＥＣＣデコーダ１２４は、情報ビットのセットおよびパリティビットの対応する第２のセットを受け取り、ＥＣＣ復号化動作を行って情報ビットのセットのエラー訂正済みバージョンを生成するように構成される。
【００２３】
第３のＥＣＣデコーダ１２６は、第３のＥＣＣエンコーダ１２６により使用された第３の代数符号に従ってデータを復号化するように構成される。図２〜４に関してさらに詳しく記述するように、第３の代数符号は、第３の符号語のセットの中のエラーあるいは消去を訂正して第３の符号語のセットのエラー訂正済みバージョンを生成するために第３の符号語のセットの部分に適用され得る。
【００２４】
第４のＥＣＣデコーダ１２８は、第４のＥＣＣエンコーダ１２８により使用された第４の代数符号に従ってデータを復号化するように構成される。第４のＥＣＣデコーダ１２８は、ジョイントパリティビットおよびジョイントパリティ保護ビットを受け取って、ジョイントパリティビットのエラーを訂正してジョイントパリティビットのエラー訂正済みバージョンを生成するためにＥＣＣ復号化動作を行う。
【００２５】
マルチフェーズＥＣＣ復号化エンジン１２０は、取り出された符号語１５９からの情報ビットの１つ以上の要求されたセットおよび対応する第１のパリティビット（例えば、ｉ1 １５１およびｐ1 １５３）を第１のＥＣＣデコーダ１２２に提供することによってＥＣＣ復号化の第１のフェーズを実行するように構成される。取り出された符号語１５９からの情報ビットの要求された全セット１５１〜１５２が第１のＥＣＣデコーダ１２２によって首尾よく復号化されたならば、取り出された符号語１５９の復号化処理を終わることができ、また要求された復号化済みデータを復号化済みデータ１７０としてホストデバイス１３０に提供することができる。
【００２６】
そうでなければ、取り出された符号語１５９からの情報ビットの少なくとも１つの要求されたセットが第１のＥＣＣデコーダ１２２によって首尾よく復号化されなかったときには、マルチフェーズ復号化エンジン１２０は、取り出された符号語１５９の情報ビットの全てのセット１５１〜１５２の復号化処理を開始するように構成される。従って、取り出された符号語１５９の情報ビットの全てのセット１５１〜１５２が、対応する第１のパリティビット１５３〜１５４を用いて復号化を試みるために第１のＥＣＣデコーダ１２２に提供される。
【００２７】
マルチフェーズ復号化エンジン１２０は、第１のＥＣＣデコーダ１２２により首尾よく復号化された情報ビットおよび第１のパリティビットのセット（例えば、ｉ1 １４１）を第２のＥＣＣエンコーダ１１４に提供して、情報ビットの各々の首尾よく復号化されたセットについてｐ(2) パリティビット（例えば、ｐ1 (2) １４５）を生成することによって復号化処理の第２のフェーズを開始するように構成され得る。
【００２８】
マルチフェーズ復号化エンジン１２０は、ジョイントパリティビット１５７およびジョイントパリティ保護ビット１５８を第４のＥＣＣデコーダ１２８に提供して復号化済みジョイントパリティビット１４７を生成するように構成され得る。首尾よく復号化された情報ビットの各セットについての復号化済みジョイントパリティビット１４７およびｐ(2) パリティビットの生成されたセット１７１は、第３の符号語のセットからの符号語を復号化するために第３のＥＣＣデコーダ１１６に提供され得る。マルチフェーズ復号化エンジン１２０は、復号化済みの第３の符号語１７２を処理して、情報ビットの各々の未復号化セットについてのｐ(2) パリティビットを生成するように構成され得る。情報ビットの未復号化セットと関連付けられている復号化済みの第３の符号語ビット（例えば、Ｗ1 （ｘ））は、図２に関して記述するように、第１の生成多項式で除された第２のパリティビットの第２のセットであるものとして、情報ビットの未復号化セット（例えば、ｐ1 (2) ）についての第２のパリティビットのセットに対応し得る（例えば、Ｗ1 （ｘ）＝ｐ1 (2) （ｘ）／ｇ1 （ｘ））。生成されたｐ(2) パリティビットは、第２の、より強力な代数符号を用いて復号化を行って復号化済み情報ビット１７５を生成するために、未復号化情報ビット１７４とともに第２のＥＣＣデコーダ１２４に提供され得る。
【００２９】
動作中、データストレージデバイス１０２がホストデバイス１３０に動作可能に結合されている間にデータストレージデバイス１０２はホストデバイス１３０からデータ１４０を受け取ることができる。コントローラ１０６は、データ１４０をマルチフェーズＥＣＣ符号化エンジン１１０に提供して第１のＥＣＣエンコーダ１１２において第１のパリティビットのセット１４３〜１４４を生成することができる。マルチフェーズＥＣＣ符号化エンジン１１０は、第２のＥＣＣエンコーダ１１４において第２のパリティビットのセット１４５〜１４６を生成するために情報ビットのセット１４１〜１４２および第１のパリティビットのセット１４３〜１４４を提供することができる。マルチフェーズＥＣＣ符号化エンジン１１０は、第２のパリティビットのセット１４５〜１４６を第３のＥＣＣエンコーダ１１６に提供してジョイントパリティビットのセット１４７を生成することができる。マルチフェーズＥＣＣ符号化エンジン１１０は、ジョイントパリティビットのセット１４７を第４のＥＣＣエンコーダ１１８に提供してジョイントパリティ保護ビット１４８を生成することができる。コントローラ１０６は、符号語１４９を格納するためにメモリ１０４に送ることができる。
【００３０】
符号化プロセスにより生成されたビットの全てが保存されるわけではない。具体的に説明すると、第２のエンコーダにより生成されたｒ・ｍ2 個のパリティビット（例えば、ｒ個の符号語の１つずつについてそれぞれｍ2 個のパリティビット）が符号語１４９の部分として格納されなくてもよく、代わりに第３のエンコーダのジョイントパリティビット１４７が格納され、これにより高価な記憶空間を節約する。廃棄されたビットは、必要ならば復号化の間に再構築され得る。
【００３１】
データストレージデバイス１０２は、データストレージデバイス１０２がホストデバイス１３０に動作可能に結合されている間に、データ１４０の１つ以上の部分を求める要求をホストデバイス１３０から受け取り得る。コントローラ１０６は、メモリから符号語１５９を取り出し、情報ビットの要求されたセット１５１〜１５２の第１のフェーズ復号化を第１のパリティビットの対応するセット１５３〜１５４を用いて開始することができる。情報ビットの要求されたセット１５１〜１５２の全てが第１のフェーズで首尾よく復号化されたならば、その復号化されたデータがホストデバイス１３０に提供される。
【００３２】
要求された情報ビットの１つ以上のセットが第１の復号化フェーズの間に正しく復号化され得なかったならば、マルチフェーズＥＣＣ復号化エンジン１２０は、ジョイントパリティビットのセット１４７のエラー訂正済みバージョンを生成するためにジョイントパリティ保護ビット１５８およびジョイントパリティビットのセット１５７を第４のＥＣＣエンコーダ１２８に提供することを含む第２の復号化フェーズを開始することができる。第１のフェーズでまだ処理されていない符号語１５９の情報ビットの全てのセットが第１のＥＣＣデコーダ１２２に提供され、結果として生じた情報ビットのセットのエラー訂正済みバージョンは、第２のパリティビットのセットを生成するために第２のＥＣＣエンコーダ１１４により符号化される。
【００３３】
第２のパリティビットのセットおよびジョイントパリティビット１４７は、復号化済みの第３の符号語を生成するために第３のＥＣＣデコーダ１２６に提供される。復号化済みの第３の符号語は、情報ビットの復号化済みセットを生成するために第２のＥＣＣデコーダ１２４に提供される第２のパリティビットのセットを生成するために処理され得る。情報ビットの要求されたセットは、復号化済みデータ１７０としてホストデバイス１３０に提供され得る。
【００３４】
マルチフェーズＥＣＣ符号化エンジン１１０が第４のＥＣＣエンコーダ１１８を含むものとして説明し、マルチフェーズＥＣＣ復号化エンジン１２０が第４のＥＣＣデコーダ１２８を含むものとして説明してきたけれども、他の実施形態では第４のＥＣＣエンコーダ１１８および第４のＥＣＣデコーダ１２８は含まれないかもしれない。例えば、ジョイントパリティビット１４７は、フラッシュメモリのシングルレベルセル（ＳＬＣ）部分などの、割合に少ないエラー発生と関連するメモリ１０４の部分に格納され得る。他の１つの例として、情報ビットの各セットについてジョイント情報ビット１７２が（第２のパリティビットの多項式除算剰余ではなくて）第２のパリティビットと同じである場合、ジョイントパリティビットに発生することのある個々のエラーの影響は軽減される。結果として、ジョイントパリティ保護ビット１４８を使用せずにエラー訂正の高い確率が達成され得る。
【００３５】
従って、図１は、短いサブ符号に基づく低複雑度の復号化エンジンを用いて、大きなエラー訂正能力を有する長いＥＣＣ符号を構築するためにジョイントパリティビットのセットを通してＢＣＨサブ符号などの数個の短いサブ符号が互いに結合され得るシステムの例を提供する。さらに、マルチフェーズ復号化方式は、ランダムな読み出しサポートおよび短い復号化待ち時間を考慮して用いられている。各々のサブ符号を別々に復号化するために第１の試行が行われ得る。メモリ１０４から読み出されるデータの予測エラー率に基づいて、短いサブ符号は、復号化成功という割合に高い確率を提供するように設計され得る。結果として、データはメモリ１０４から読み出され、コントローラ１０６に転送され、短いサブ符号が復号化され得る（例えば、ｉ1 １４１およびｐ1 １４３が第１のＥＣＣデコーダ１２２で復号化される）。第１の復号化試行が失敗するという割合に低い確率のイベントにおいて、同じＥＣＣブロックに（例えば、符号語１５９に）属する他のサブ符号もメモリ１０４から読み出され、コントローラ１０６に転送され、復号化される。他のサブ符号が首尾よく復号化されたならば、ジョイントパリティビットと、他のサブ符号の復号化の結果とに基づいて、失敗したサブ符号について第２の復号化試行が行われる。第２の復号化試行は、第１の試行より大きなエラー訂正能力を（従って、より低い失敗確立を）有する代数符号を用いる。
【００３６】
2015507409.tif 000003
【００３７】
2015507409.tif 000004
【００３８】
マルチフェーズＥＣＣエンコーダは、ｋ個の情報ビットのｒ個のベクトル（１サブ符号あたりに１ベクトル）ｉ1 ，ｉ2 ，・・・，ｉr を受け取ることができ、出力としてｍ1 個のパリティビットのｒ個のベクトル（１サブ符号あたりに１ベクトル）ｐ1 ，ｐ2 ，・・・，ｐr を生成することができる。マルチフェーズＥＣＣエンコーダは、さらに全サブ符号についてｍ3 ×ｍ2 個のジョイントパリティビットのベクトルｗを生成することができ、ジョイントパリティビットを保護するためのｍ4 個のパリティビットのベクトルｖを生成することができる。
【００３９】
符号化は、マルチフェーズＥＣＣエンコーダにおいて、サブ符号あたりにパリティビット（ｐ1 ，ｐ2 ，・・・，ｐr ）を計算するとともにジョイントパリティビット（ｗ）を計算することによって実行され得る。サブ符号あたりのパリティビット（ｐ1 ，ｐ2 ，・・・，ｐr ）は、各ｊ＝１，２，・・・，ｒについて、多項式除算の商結果Ｑ（ｘ）、
2015507409.tif 000005
を計算することによって生成され得る。
【００４０】
第１のパリティｐj （ｘ）（次数ｍ1 −１の多項式）あるいはベクトルｐj は、
2015507409.tif 000006
として計算され得る。
第２のパリティビットｐj(2)（ｘ）および／またはジョイント情報ビットＷj （ｘ）（次数ｍ2 −１の多項式、Ｗｊと等価である）は多項式除算の商結果Ｕ（ｘ）、
2015507409.tif 000007
に従って
2015507409.tif 000008
として計算され得る。Ｗj （ｘ）は、
2015507409.tif 000009
としても計算され得ることに留意するべきである。
代わりに、Ｗj （ｘ）は、
2015507409.tif 000010
としても計算され得る。
【００４１】
ジョイントパリティビット（ｗ）の計算は、ベクトルＷj （ｊ＝１、２、・・・、ｒ）からｍ3 ×ｍ2 個のジョイントパリティビット（ｗ）を計算するために符号Ｃ3 を用いて実行され得る。図２に示されているように、Ｗj ベクトルをマトリクスの行として配列することができ、符号Ｃ3 を用いてマトリクス中のｒ個のシンボルの各列についてｍ3 個のパリティシンボルが計算され得る。
【００４２】
図２は、代数符号に基づくマルチフェーズＥＣＣ復号化に用いられるジョイントパリティビットを生成する特定の実施形態を示す。ジョイント情報ビットのセット２０２はｒ個の行（Ｗ1 ２０３、Ｗ2 ２０４、・・・Ｗr ２０５）を含むマトリクスとして配列されている。前述したように、各行Ｗj は、生成多項式ｇ2 （ｘ）で除されたパリティビットの第２のセットｐj (2) に対応し得る（ここで、パリティビットの第２のセットｐ(2) は生成多項式ｇ（ｘ）＝ｇ1 （ｘ）・ｇ2 （ｘ）に基づいている）。代わりの実施形態では、各行Ｗj はパリティビットの第２のセットｐj(2)であり得る。代表的なＣ3 符号語２１０は、ジョイント情報ビットのセット２０２の各行からの１ビットと、ジョイントパリティビット（ｗ）１４７の各行からの１パリティビットとを含む。Ｃ3 符号をジョイント情報ビットのセット２０２の各列に適用することにより（例えば、図１の第３のＥＣＣエンコーダ１１６においてジョイント情報ビットを符号化することにより）、ジョイントパリティビットの各列（ｗ）１４７に対応するパリティビットが生成される。
【００４３】
図３は、代数符号に基づくマルチフェーズＥＣＣ復号化に用いられるジョイントパリティビットを生成する特定の実施形態を示し、ここで符号Ｃ3 は、単一の消去を訂正し得るシングルパリティ検査符号などのバイナリ符号である（すなわち、ＧＦ（２）で除されたＣ3 （ｒ＋１，ｒ，１））。ジョイント情報ビットのセット２０２はｒ個の行（Ｗ1 ２０３，Ｗ2 ２０４，・・・Ｗr ２０５）を含むマトリクスとして配列される。ジョイント情報ビットのセット２０２の各列のビットにＣ3 符号を適用すると（排他的論理和（ＸＯＲ）演算３１０）、ジョイントパリティビットの対応するパリティビット（ｗ）１４７が生成される。ＸＯＲ演算３１０を使用すれば、割合に複雑度の低いハードウェアを用いてジョイントパリティビット（ｗ）１４７を生成することが可能となり、列あたりに単一の消去を訂正することが可能となる。結果として、ｒ個の行のうちの１つを除いて他の全てが生成されたならば、その欠けている行はジョイントパリティビット（ｗ）１４７を用いて復元され得る。
【００４４】
2015507409.tif 000011
【００４５】
図４は、符号語４１０の各々の非バイナリシンボルがジョイント情報ビットのセット２０２の単一の行のビットから形成されることを示しているけれども、他の実施形態では、符号語４１０のシンボルはジョイント情報ビットのセット２０２の複数の行にわたり得る。具体的に説明すると、単一のシンボルが、１つの列に存する行Ｗ1 ２０３からの１ビットと、他の列に存する行Ｗ2 ２０４からの他の１ビットとを含み得る。第２のフェーズの復号化に関してさらに詳しく記述するように、ジョイント情報ビットのセット２０２の複数の行にわたるマルチビットシンボルを用いることにより、第１のフェーズの復号化失敗に対する付加的な耐性が提供され得る。
【００４６】
ジョイントパリティビットを保護するためのパリティビット（ｖ）（例えば、図１のジョイントパリティ保護ビット１４８）の計算は、ｍ3 ×ｍ2 個のジョイントパリティビットｗを保護するためのｍ4 個のパリティビット（ｖ）を計算するために符号Ｃ4 （ｎ4 ＝ｍ3 ×ｍ2 ＋ｍ4 ，ｋ4 ＝ｍ3 ×ｍ2 ，ｔ4 ）を用いて行われ得る。例えば、図１の第４のＥＣＣエンコーダ１１８は、ジョイントパリティ保護ビット１４８を生成するためにジョイントパリティビット１４７を符号化することができる。
【００４７】
メモリに格納されるビットの総数は、ｉ1 ，ｉ2 ，・・・，ｉr ，ｐ1 ，ｐ2 ，・・・，ｐr ，ｗ，およびｖの格納（例えば、ｉ1 ・・・ｉr １４１〜１４２，ｐ1 ・・・ｐr １４３〜１４４，ｐJ １４７，およびｐJP１４８を含む図１の符号語１４９の格納）に対応するｒ×ｋ＋ｒ×ｍ1 ＋ｍ2 ×ｍ3 ＋ｍ4 であり得る。具体的に説明すると、ｋ個の情報ビットのｒ個のセット（ｉ）を格納することはｒ×ｋビットを格納する結果をもたらす。第１のパリティビットのｒ個のセット（ｐ）を格納すれば、第１のパリティビットの各セットがｍ1 個のビットを含み、ｒ×ｍ1 ビットが格納されるという結果がもたらされる。ジョイントパリティビットのｍ3 個の行（ｗ）を格納すれば、各行がｍ2 ビットを有し、ｍ2 ×ｍ3 ビットが格納されるという結果がもたらされる。ジョイントパリティ保護ビット（ｖ）を格納すれば、ｍ4 ビットが格納されるという結果がもたらされる。
【００４８】
2015507409.tif 000012
【００４９】
2015507409.tif 000013
【００５０】
2015507409.tif 000014
【００５１】
第１のフェーズ復号化において首尾よく復号化された各サブ符号ｊについて、
2015507409.tif 000015
を計算するためにｉj およびｐj が使用され得る。
サブ符号ｊの第３の符号語Ｃ3 への寄与は、
2015507409.tif 000016
として生成され得る。
代わりに、Ｗj （ｘ）が、
2015507409.tif 000017
として生成され得る。符号の定義は既知であると仮定されているので、ｇ1 （ｘ）およびｇ2 （ｘ）はデコーダにおいて既知であり得るということに留意するべきである。さらに、特定の実施例の場合では、Ｗj （ｘ）の計算は、
2015507409.tif 000018
を、次に
2015507409.tif 000019
を計算することにより実行され得るということにも留意するべきである。
【００５２】
2015507409.tif 000020
【００５３】
2015507409.tif 000021
【００５４】
2015507409.tif 000022
【００５５】
代数符号を用いるマルチフェーズ復号化は、在来のＥＣＣ符号化と比べて所与の量の冗長性についてほぼ同じエラー訂正能力を維持すると同時に複雑度および復号化待ち時間を著しく低減することができる。幾つかの例が表１に示されている。表１の例では、マルチフェーズ符号語（例えば、図１の符号語１４９）は、９３２Ｂにはまり込み、８ＫＢブロックあたりに＜１０-10 のブロックエラー率を提供する。基準として、在来の１２２ｂ／２ＫＢ  ＢＣＨが用いられ得る。
【００５６】
表１
2015507409.tif 000023
・基準：在来のＢＣＨ：ｋref ＝２ＫＢ、ｔref ＝１２２
・例１：ｒ＝８、ｋ＝１ＫＢ、ｔ1 ＝６４、ｔ2 ＝７９、ｔ3 ＝１、ｔ4 ＝８
（Ｃ1 、Ｃ2 、Ｃ4 はＢＣＨ符号であり、Ｃ3 はシングルパリティ検査符号である。）
・例２：ｒ＝４、ｋ＝１ＫＢ、ｔ1 ＝６２、ｔ2 ＝７６、ｔ3 ＝１、ｔ4 ＝７
（Ｃ1 、Ｃ2 、Ｃ4 はＢＣＨ符号であり、Ｃ3 はシングルパリティ検査符号である。）
・例３：ｒ＝２、ｋ＝１ＫＢ、ｔ1 ＝５６、ｔ2 ＝７２、ｔ3 ＝１、ｔ4 ＝８
（Ｃ1 、Ｃ2 、Ｃ4 はＢＣＨ符号であり、Ｃ3 はシングルパリティ検査符号である。）
・例４：ｒ＝８、ｋ＝０．５ＫＢ、ｔ1 ＝３１、ｔ2 ＝４６、ｔ3 ＝２、ｔ4 ＝１１
（Ｃ1 、Ｃ2 、Ｃ4 はＢＣＨ符号であり、Ｃ3 はＧＦ（１６）で除されたＲＳ符号である。）
・例５：ｒ＝８、ｋ＝０．５ＫＢ、ｔ1 ＝３４、ｔ2 ＝４５、ｔ3 ＝１、ｔ4 ＝６
（Ｃ1 、Ｃ2 、Ｃ4 はＢＣＨ符号であり、Ｃ3 はシングルパリティ検査符号である。）
【００５７】
長さがｎref で訂正能力がｔref である在来のＢＣＨ符号化方式と比べて、符号Ｃ1 、Ｃ2 およびＣ4 がＢＣＨ符号であり符号Ｃ3 がシングルパリティ検査符号またはＲＳ符号であるときの、代数符号を用いるマルチフェーズＥＣＣの複雑度改善は、
2015507409.tif 000024
により与えられ得る。
長さｎref の在来のＢＣＨ符号化方式と比べて、代数符号を用いるマルチフェーズＥＣＣの待ち時間の改善は、待ち時間比＝ｎ1 ／ｎref により与えられ得る。
第１の復号化フェーズの間にサブ符号が失敗する確率は小さいかもしれないので（例えば、１０-5未満なので）、待ち時間比は第１の復号化段階により主として決まる復号化待ち時間に基づくことができる。
【００５８】
図５を参照すると、データを符号化する方法５００の特定の実施形態のフローチャートが描かれている。方法５００は、図１のデータストレージデバイス１０２などのデータストレージデバイスで実行され得る。５０２で、情報ビットの第１のセットに対応する第１のパリティビットの第１のセットを生成するとともに情報ビットの第２のセットに対応する第１のパリティビットの第２のセットを生成するために、第１のエラー訂正符号と関連する第１の符号化動作が開始され得る。第１のエラー訂正符号は代数符号である。例えば、第１の符号化動作は、図１の第１のＥＣＣエンコーダ１１２において、情報ビットの第１のセットを第１のＥＣＣエンコーダ１１２の符号化入力に提供し、第１のＥＣＣエンコーダ１１２の制御入力に信号を送って第１のＥＣＣエンコーダに符号化入力に存する情報ビットの第１のセットを読ませ、情報ビットの第１のセットに対して第１の符号化動作を実行させることによって、開始され得る。
【００５９】
５０４で、情報ビットの第１のセットに対応する第２のパリティビットの第１のセットを生成するとともに情報ビットの第２のセットに対応する第２のパリティビットの第２のセットを生成するために、第２のエラー訂正符号と関連する第２の符号化動作が開始される。第２のエラー訂正符号は、第１のエラー訂正符号より大きなエラー訂正能力を有する他の１つの代数符号である。例えば、第２の符号化動作は、図１の第２のＥＣＣエンコーダ１１４において、情報ビットの第１のセットを第２のＥＣＣエンコーダ１１４の符号化入力に提供し、第２のＥＣＣエンコーダ１１４の制御入力に信号を送って第２のＥＣＣエンコーダ１１４に符号化入力に存する情報ビットの第１のセットを読ませ、情報ビットの第１のセットに対して第２の符号化動作を実行させることによって、開始され得る。
【００６０】
５０６で、ジョイント情報ビットのセットに対応するジョイントパリティビットのセットを生成するために第３の符号化動作が開始される。ジョイント情報ビットのセットは、情報ビットの第１のセットおよび情報ビットの第２のセットと関連付けられている。例えば、第１のエラー訂正符号は第１の生成多項式ｇ1 （ｘ）に対応することができ、ジョイント情報ビットのセットは、第１の生成多項式で除された第２のパリティビットの第１のセットを含むことができる（例えば、Ｗ1 （ｘ）＝ｐ(2) （ｘ）／ｇ1 （ｘ））とともに第１の生成多項式で除された第２のパリティビットの第２のセットを含むことができる（Ｗ2 （ｘ）＝ｐ2 (2) （ｘ）／ｇ1 （ｘ））。第３の符号化動作は、ジョイント情報ビットのセットを生成し、ジョイント情報ビットのセットを第３のＥＣＣエンコーダ１１６の符号化入力に提供し、第３のＥＣＣエンコーダ１１６の制御入力に信号を送って、第３のＥＣＣエンコーダ１１６に符号化入力に存するジョイント情報ビットのセットを読ませ、ジョイント情報ビットのセットに対して第３の符号化動作を実行させることによって、図１の第３のＥＣＣエンコーダ１１６において開始され得る。一例として、ジョイント情報ビットのセットは図２〜４に示されているようにマトリクスに配列され、マトリクスの列のシーケンス（あるいは列のセット）として符号化入力に提供され得る。例えば、第３の符号化動作は、図３に関して記述したように、単一の消去を訂正し得るシングルパリティ検査符号を含み得る。他の一例として、第３の符号化動作は、図４に関して記述したように、非バイナリ代数符号を含み得る。
【００６１】
方法５００は、５０８で、情報ビットの第１のセット、情報ビットの第２のセット、第１のパリティビットの第１のセット、第１のパリティビットの第２のセット、およびジョイントパリティビットをデータストレージデバイスのメモリに単一の符号語として格納することも含む。
例えば、その単一の符号語は、図１の符号語１４９であり得る。
【００６２】
方法５００は、図１の第４のＥＣＣエンコーダ１２８によるなどして、ジョイントパリティビットに対応するジョイントパリティ保護ビットのセットを生成するために第４の符号化動作を開始することも含み得る。単一の符号語は、ジョイントパリティ保護ビットのセットをさらに含み得る。第４の符号化動作は、ジョイントパリティビットのセットを第４のＥＣＣエンコーダ１１８の符号化入力に提供し、第４のＥＣＣエンコーダ１１８の制御入力に信号を送って第４のＥＣＣエンコーダ１１８に符号化入力に存するジョイントパリティビットのセットを読ませ、ジョイントパリティビットのセットに対して第４の符号化動作を実行させることによって、開始され得る。
【００６３】
代数符号に基づくマルチフェーズＥＣＣ復号化を可能にするために情報を符号化することにより、マルチフェーズＥＣＣ復号化方式と同等のエラー訂正能力を有するＢＣＨ符号と比べて短縮された待ち時間で短いサブ符号を復号化する第１の復号化フェーズが実行され得る。第２の復号化フェーズは、同等のエラー訂正能力を有するＢＣＨ符号と比べて縮減されたメモリストレージ要件を有するより長い符号に基づくより強力なＥＣＣ保護を提供し得る。代数符号を用いるＥＣＣは、ターボ符号またはＬＤＰＣなどの反復復号化方式と比べてデコーダ複雑度および復号化待ち時間を低減することができる。
【００６４】
図６を参照すると、データを復号化する方法６００の特定の実施形態のフローチャートが描かれている。方法６００は、図１のデータストレージデバイス１０２などのデータストレージデバイスで実行され得る。
【００６５】
復号化の第１のフェーズの間に、６０２で、第１のエラー訂正符号と関連する第１の復号化動作が開始される。第１の復号化動作は、符号語の情報ビットの第１のセットおよび第１のパリティビットの第１のセットを用いる。第１のエラー訂正符号は代数符号である。例えば、第１の復号化動作は、図１の第１のＥＣＣデコーダ１２２において、情報ビットの第１のセットおよびパリティビットの第１のセットを第１のＥＣＣデコーダ１２２の復号化入力に提供し、第１のＥＣＣデコーダ１２２の制御入力に信号を送って第１のＥＣＣデコーダ１２２に復号化入力に存する情報ビットの第１のセットおよびパリティビットの第１のセットを読ませ、第１の復号化動作を実行させることによって、開始され得る。図１の符号語１５９などの符号語は、情報ビットの第２のセット、第１のパリティビットの第２のセット、およびジョイントパリティビットのセットをさらに含む。
【００６６】
復号化の第２のフェーズは、６０４で、第１の復号化動作での復号化失敗に応答して開始される。第２のフェーズは、６０６で、情報ビットの第２のセットおよびパリティビットの第２のセットを用いる第２の復号化動作を開始することを含む。第２の復号化動作は、第１のエラー訂正符号と関連付けられる。例えば、第２の復号化動作は、図１の第１のＥＣＣデコーダ１２２において、情報ビットの第２のセットおよびパリティビットの第２のセットを第１のＥＣＣデコーダ１２２の復号化入力に提供し、第１のＥＣＣデコーダ１２２の制御入力に信号を送って第１のＥＣＣデコーダ１２２に復号化入力に存する情報ビットの第２のセットおよびパリティビットの第２のセットを読ませ、第２の復号化動作を実行させることによって、開始され得る。
【００６７】
第２のフェーズは、６０６で、情報ビットの第２のセットに対応する第２のパリティビットの第２のセットを生成するために第２のエラー訂正符号と関連付けられた符号化動作を開始することを含む。第２のエラー訂正符号は、第１のエラー訂正符号より大きなエラー訂正能力を有する他の１つの代数符号である。例えば、符号化動作は、情報ビットの第２のセットを第２のＥＣＣエンコーダ１１４の符号化入力に提供し、第２のＥＣＣエンコーダ１１４の制御入力に信号を送って第２のＥＣＣエンコーダ１１４に符号化入力に存する情報ビットの第２のセットを読ませ、情報ビットの第２のセットに対して符号化動作を実行させることによって、図１の第２のＥＣＣエンコーダ１１４において開始され得る。
【００６８】
第２のフェーズは、６０８で、第２のパリティビットの第２のセットに対応するジョイントパリティビットおよびジョイント情報ビットのセットを用いて第２のパリティビットの第１のセットに対応するジョイント情報ビットを生成する第３の復号化動作を開始することを含む。第２のパリティビットの第１のセットは第１の情報ビットと関連付けられている。例えば、第１のエラー訂正符号は、ｇ1 （ｘ）などの第１の生成多項式に対応し得る。第２のパリティビットの第２のセットに対応するジョイント情報ビット（例えば、Ｗ2 （ｘ））は、第１の生成多項式で除された第２のパリティビットの第２のセットを含み得る（例えば、ｐ(2) （ｘ）／ｇ1 （ｘ））。一例として、第３の復号化動作は、パリティビットの第２のセットに対応するジョイント情報ビットを含む（ただし、情報ビットの第１のセットに対応するジョイント情報ビットを除く）ジョイント情報ビットのセットを生成し、ジョイント情報ビットのセットおよびジョイントパリティビットを第３のＥＣＣデコーダ１２６の復号化入力に提供し、第３のＥＣＣデコーダ１２６の制御入力に信号を送って、第３のＥＣＣデコーダ１２６に復号化入力に存するジョイント情報ビットのセットおよびジョイントパリティビットのセットを読ませ、ジョイント情報ビットのセットおよびジョイントパリティビットのセットに対して第３の復号化動作を実行させることによって、図１の第３のＥＣＣデコーダ１２６において開始され得る。
【００６９】
第２のフェーズは、６１０で、情報ビットの第１のセットおよび第２のパリティビットの第１のセットを用いて第４の復号化動作を開始することも含む。第４の復号化動作は、第２のエラー訂正符号と関連付けられる。例えば、第４の復号化動作は、情報ビットの第１のセットおよび第２のパリティビットの第１のセットを第２のＥＣＣデコーダ１２４の復号化入力に提供し、第２のＥＣＣデコーダ１２４の制御入力に信号を送って第２のＥＣＣデコーダ１２４に復号化入力に存する情報ビットの第１のセットおよび第２のパリティビットの第１のセットを読ませ、第４の復号化動作を実行させることによって、図１の第２のＥＣＣデコーダ１２４において開始され得る。
【００７０】
或る実施形態では、符号語はジョイントパリティ保護ビットのセットをさらに含み、第２のフェーズは、ジョイントパリティビットのセットおよびジョイントパリティ保護ビットのセットを用いて、第３の復号化動作を開始する前にジョイントパリティビットのセットの中のエラーを訂正するジョイントパリティ復号化動作を開始することを含む。例えば、ジョイントパリティ復号化動作は図１の第４のＥＣＣデコーダ１２８で実行され得る。一例として、ジョイントパリティ復号化動作は、図３に関して記述したように単一の消去を訂正できるシングルパリティ検査符号に基づくことができる。他の例として、ジョイントパリティ復号化動作は、図４に関して記述したように非バイナリ代数符号に基づくことができる。
【００７１】
代数符号に基づくマルチフェーズＥＣＣ復号化を用いて復号化を行うことにより、マルチフェーズＥＣＣ復号化方式と同等のエラー訂正能力を有するＢＣＨ符号と比べて縮減された待ち時間および複雑度を有する短いサブ符号を復号化する第１の復号化フェーズが実行され得る。第２の復号化フェーズは、同等のエラー訂正能力を有するＢＣＨ符号と比べて縮減されたメモリストレージ要件を有するより長い符号に基づくより強力なＥＣＣ保護を提供し得る。代数符号を用いるＥＣＣは、ターボ符号またはＬＤＰＣなどの反復復号化方式と比べてデコーダ複雑度および復号化待ち時間を低減することができる。
【００７２】
本願明細書において述べられている種々のコンポーネントをブロックコンポーネントとして図に示して一般的用語で記述しているけれども、そのようなコンポーネントは、図１のデータストレージデバイス１０２などのデータストレージデバイスがそのようなコンポーネントに備わっている特定の機能またはその組み合わせを実行することを可能にするように構成された１つ以上のマイクロプロセッサ、状態マシン、または他の回路を含むことができる。例えば、図１のマルチフェーズＥＣＣ符号化エンジン１１０およびマルチフェーズＥＣＣ復号化エンジン１２０の一方または両方は、代数符号を用いるマルチフェーズＥＣＣ方式に従ってデータの符号化および復号化を可能にするプロセッサ、状態マシン、論理回路、または他の構造などの物理的コンポーネントを代表することができる。
【００７３】
図１のマルチフェーズＥＣＣ符号化エンジン１１０およびマルチフェーズＥＣＣ復号化エンジン１２０の一方または両方は、マイクロプロセッサまたはマイクロコントローラを用いて実装され得る。特定の一実施形態では、マルチフェーズＥＣＣ復号化エンジン１２０は、メモリ１０４に格納されている命令を実行するプロセッサを含む。代わりに、あるいはこのことに加えて、実行可能な命令は、読み出し専用メモリ（ＲＯＭ）など、メモリ１０４の一部ではない別の記憶場所に格納され得る。
【００７４】
特定の一実施形態では、データストレージデバイス１０２は、１つ以上の外部デバイスに選択的に結合されるように構成された携帯可能なデバイスであり得る。例えば、データストレージデバイス１０２は、ユニバーサルシリアルバス（ＵＳＢ）フラッシュドライブまたは取り外し可能なメモリカードなどの取り外し可能なデバイスであり得る。しかし、他の実施形態では、データストレージデバイス１０２を、携帯可能な通信装置のハウジングの中など、１つ以上のホストデバイスに取り付けるかあるいは埋め込むことができる。例えば、データストレージデバイス１０２は、内部不揮発性メモリを用いる無線電話機、個人用携帯情報端末（ＰＤＡ）、ゲームデバイスもしくはコンソール、携帯ナビゲーションデバイス、コンピュータ、または他のデバイスなどのパッケージ装置の中に存在し得る。特定の一実施形態では、データストレージデバイス１０２は、フラッシュメモリ（例えば、ＮＡＮＤ、ＮＯＲ、マルチレベルセル（ＭＬＣ）、ディバイデッドビットラインＮＯＲ（ＤＩＮＯＲ）、ＡＮＤ、ハイキャパシティブカップリングレシオ（ＨｉＣＲ）、非対称コンタクトレストランジスタ（ＡＣＴ）、あるいは他のフラッシュメモリ）、消去可能でプログラム可能な読み出し専用メモリ（ＥＰＲＯＭ）、電気的に消去可能でプログラム可能な読み出し専用メモリ（ＥＥＰＲＯＭ）、読み出し専用メモリ（ＲＯＭ）、ワンタイムプログラマブルメモリ（ＯＴＰ）、あるいは他の任意のタイプのメモリなどの、不揮発性メモリを含む。
【００７５】
本願明細書に記載した実施形態についての説明は、種々の実施形態の全般的理解を提供するように意図されている。本願明細書で開示した範囲から逸脱せずに構造的および論理的置換および変更が行われ得るように、他の実施形態が利用され、このような開示から引き出され得る。この開示は、種々の実施形態のありとあらゆる爾後適合あるいはバリエーションを包含するように意図されている。
【００７６】
前に開示された主題は実例を示すものであって、限定をするものではないと見なされなければならず、添付されている特許請求の範囲は、本願明細書で開示した範囲に属するようなすべての改変、向上、および他の実施形態を包含するように意図されている。従って、法により許される最大限度まで、本発明の範囲は、添付されている特許請求の範囲およびそれらの同等物の最大限に広い許容可能な解釈により決定されるべきであり、前述した詳細な記述により制限あるいは限定されてはならない。
【図１】
2015507409.tif 000025
【図２】
2015507409.tif 000026
【図３】
2015507409.tif 000027
【図４】
2015507409.tif 000028
【図５】
2015507409.tif 000029
【図６】
2015507409.tif 000030
【国際調査報告】
2015507409.tif 000031
2015507409.tif 000032