(57)【要約】【課題】書き換え可能メモリに書き込まれるデータおよびこのメモリから読み出されるデータにエラー訂正アルゴリズムを適用するデータ処理装置を開示する。【解決手段】前記データ処理装置はハードウェアで実現されたコーディングユニットを備え、このコーディングユニットはコーディング動作を実行でき、このコーディングユニット動作において、コーディングユニットはメモリに書き込まれる第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、第２データセットを出力してメモリに書き込む。前記データ処理装置はさらにソフトウェアで実現されたエラー訂正ユニットを備える。【選択図】図１
2009501380.tif 000002
【特許請求の範囲】
【請求項１】
書き換え可能メモリに書き込まれるデータおよびこのメモリから読み出されるデータにエラー訂正アルゴリズムを適用するデータ処理装置であって、
ハードウェアに実装されたコーディングユニットであって、コーディング動作を実行でき、このコーディング動作において、前記メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、前記メモリへの書込み用にこの第２データセットを出力し、さらにエラー検出動作を実行でき、このエラー検出動作では、前記メモリから読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する、コーディングユニットと、
ソフトウェアに実装されたエラー訂正ユニットであって、エラーを含む読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理してエラーを訂正し、これにより訂正されたデータを生成し、この訂正されたデータを出力する、エラー訂正ユニットとを備えたデータ処理装置。
【請求項２】
請求項１において、前記コーディングユニットは、メモリから読み出されたデータがエラーを含まないと判別すると、メモリから読み出されたデータを出力する、データ処理装置。
【請求項３】
請求項１または２において、前記コーディングユニットは、前記コーディング動作中に第１データセットに実行する処理と同一の処理を、前記エラー検出動作中にメモリから読み出されたデータのエラー検出処理に実行する、データ処理装置。
【請求項４】
請求項３において、前記コーディングユニットは、エラー検出動作中に、メモリから読み出されたデータをコーディング動作に合わせて第１データセットとみなし、このデータを前記エラー訂正アルゴリズムに従って処理して第２データセットを生成する、データ処理装置。
【請求項５】
請求項１から４のいずれか一項において、前記コーディングユニットは、第１データセットが既に書き込まれた前記メモリ内の第１位置から読み出される情報データと、第２データセットが既に書き込まれた前記メモリ内の第２位置から読み出される情報データについてのパリティデータとを受け取るように構成されており、前記第２データセットはコーディング動作中に前記第１データセットから既に生成されたものである、データ処理装置。
【請求項６】
請求項４に従属する請求項５において、前記コーディングユニットは、前記エラー訂正アルゴリズムに従って前記情報データを処理して第２データセットを生成し、この第２データセットを前記パリティデータと比較して、前記第２データセットが前記パリティデータと一致しない場合にその情報データがエラーを含むと判別することによって、メモリから読み出されたデータがエラーを含むか否かを判別する、データ処理装置。
【請求項７】
請求項１から６のいずれか一項において、前記コーディングユニットは、第１データセットを受け取り、このデータに生成多項式を乗算し、この乗算の結果を第２データセットとして出力する符号語生成器を備えた、データ処理装置。
【請求項８】
請求項５から７のいずれか一項において、前記コーディングユニットは、前記メモリから読み出されたデータを受け取り、この読み出されたデータに含まれる前記情報データに生成多項式を乗算し、この乗算の結果を、読み出されたデータに含まれる前記パリティデータと比較する符号語生成器を備えた、データ処理装置。
【請求項９】
請求項５から８のいずれか一項において、前記コーディングユニットは、前記メモリから読み出された前記データを受け取り、この読み出されたデータに含まれる前記情報データとパリティデータとを連結し、前記生成多項式の根を前記連結されたデータに代入し、その結果の値を加算するシンドローム生成器を備えた、データ処理装置。
【請求項１０】
請求項９において、前記コーディングユニットは、前記結果の値の総和がゼロでない場合、前記情報データがエラーを含むと判別する、データ処理装置。
【請求項１１】
請求項１０において、前記シンドローム生成器は、前記生成多項式の複数の根を前記連結されたデータにそれぞれ代入し、各代入から得た値を加算するように構成されており、加算の結果は、情報データ内のエラーの場所を表すものである、データ処理装置。
【請求項１２】
請求項１から１１のいずれか一項において、前記コーディングユニットは、メモリから読み出された前記データがエラーを含むと判別すると、その情報データを前記エラー訂正ユニットに出力する、データ処理装置。
【請求項１３】
請求項１から１２のいずれか一項において、前記エラー訂正ユニットは、前記メモリに書き込まれるデータをインターリーブし、前記メモリから読み出されたデータをデインターリーブする、データ処理装置。
【請求項１４】
請求項１から１３のいずれか一項において、前記コーディングユニットは、メモリから読み出される256バイトごとに２つ以上のビットエラーを検出できる、データ処理装置。
【請求項１５】
請求項１から１４のいずれか一項において、前記エラー訂正ユニットは、メモリから読み出される512バイトごとに２つ以上のビットエラーを訂正できる、データ処理装置。
【請求項１６】
請求項の１から１５いずれか一項において、前記エラー訂正アルゴリズムはリードソロモン・コードである、データ処理装置。
【請求項１７】
請求項１から１６のいずれか一項において、前記エラー訂正アルゴリズムはクロスインターリーブ・リードソロモン・コードである、データ処理装置。
【請求項１８】
請求項１から１７のいずれか一項において、前記エラー訂正ユニットはデジタルプロセッサである、データ処理装置。
【請求項１９】
書き換え可能メモリと、
ハードウェアに実装されたコーディングユニットであって、コーディング動作を実行でき、このコーディング動作において、前記メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、前記メモリへの書込み用にこの第２データセットを出力し、さらにエラー検出動作を実行でき、このエラー検出動作では、前記メモリから読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する、コーディングユニットと、
ソフトウェアに実装されたエラー訂正ユニットであって、エラーを含む読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して前記エラーを訂正し、これにより訂正されたデータを生成し、この訂正されたデータを出力する、エラー訂正ユニットとを備えたデータ記憶装置。
【請求項２０】
請求項１９において、前記プロセッサによるデータ読出しとデータ書込みの両方または一方に用いられる前記メモリの少なくとも1つのセクタは、512バイト当たり１ビットよりも大きいエラー率を有する、データ記憶装置。
【請求項２１】
請求項１９または２０において、前記メモリはリサイクルされた集積メモリである、データ記憶装置。
【請求項２２】
請求項１９または２０において、前記メモリは従来の許容できる製造標準を超えるエラー率を有する、データ記憶装置。
【請求項２３】
請求項１９から２２のいずれか一項において、前記メモリはフラッシュメモリである、データ記憶装置。
【請求項２４】
請求項１９から２３のいずれか一項において、前記メモリはＮＡＮＤフラッシュメモリである、データ記憶装置。
【請求項２５】
請求項１９から２４のいずれか一項において、前記メモリは、そのビットが単独でアクセスされないものである、データ記憶装置。
【請求項２６】
書き換え可能メモリに書き込まれるデータおよびこのメモリから読み出されるデータを処理する方法であって、
ハードウェアでコーディング動作を実行する工程であって、このコーディング動作は、前記メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、前記メモリへの書込み用に第２データセットを出力する工程と、
ハードウェアでエラー検出動作を実行する工程であって、このエラー検出動作は、前記メモリから読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する工程と、
ソフトウェアでエラー訂正動作を実行する工程であって、このエラー訂正動作は、エラーを含む読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理してエラーを訂正し、この訂正されたデータを出力する工程とを備えた、データ処理方法。
【請求項２７】
メモリが機能している装置からこのメモリを取り除いて、このメモリを別の装置内に設置する工程を備えた、書き換え可能メモリをリサイクルする方法であって、
前記別の装置はデータ処理装置を有し、このデータ処理装置は、
ハードウェアに実装されたコーディングユニットであって、コーディング動作を実行でき、このコーディング動作において、前記メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、前記メモリへの書込み用にこの第２データセットを出力し、さらにエラー検出動作を実行でき、このエラー検出動作では、前記メモリから読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する、コーディングユニットと、
ソフトウェアに実装されたエラー訂正ユニットであって、エラーを含む読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理してエラーを訂正し、これにより訂正されたデータを生成し、この訂正されたデータを出力する、エラー訂正ユニットとを備えた、メモリのリサイクル方法。
【請求項２８】
添付図面に関して本明細書において記載された内容に実質的に一致する、データ処理装置。
【請求項２９】
添付図面に関して本明細書において記載された内容に実質的に一致する、データ記憶装置。
【請求項３０】
添付図面に関して本明細書において記載された内容に実質的に一致する、データを処理する方法。
【請求項３１】
添付図面に関して本明細書において記載された内容に実質的に一致する、書き換え可能メモリをリサイクルする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、書き換え可能メモリに書き込まれるデータおよび書き換え可能メモリから読み出されるデータにエラー訂正アルゴリズムを適用するデータ処理装置に関する。
【背景技術】
【０００２】
フラッシュメモリは、電気的に消去および再プログラムすることができる不揮発性メモリの一形態である。フラッシュメモリは、デジタルオーディオプレーヤ、デジタルカメラおよび携帯電話などの広範囲の消費者製品に組み込まれている。しかし、全てのフラッシュメモリは、限定された回数の消去サイクルにしか耐えられないという欠点を免れていない。フラッシュメモリのダイ領域（半導体チップ上の面積）が絶えず大きくなっているため、メモリ内の任意のビットが破壊される統計的確率も増加している。
【０００３】
大容量記憶用途に対しては、ＮＯＲフラッシュに比べて、高いデータ密度を理由として、ＮＡＮＤフラッシュが一般的に選択される。ＮＡＮＤフラッシュを使用することに関する主な欠点は、バイトの個々のビットにランダムにアクセスできないことである。代わりに、装置はハードディスクドライブのように、512バイトのセクタに構成される。フラッシュＩＣが製造されて試験されるとき、これらセクタのいくつかはそのプロセスにおいて破壊されると予測されるので、追加のセクタを利用可能にしてこれらの損失を一般的な半導体歩留まりの問題に置き換える。多くの場合、このプロセスを外部から見えなくする複雑なコントローラが存在し、典型的には、このために2％の追加セクタが利用可能とされる。典型的なＮＡＮＤフラッシュセクタは、約10000回再プログラム可能である。
【０００４】
フラッシュメモリに固有の耐久限度のために、多くの製造者は何らかの簡単なエラー訂正をメモリに組み込んでいる。典型的には、製造者はハミングコードを使用し、セクタサイズをさらに16バイト増加して、エラー訂正オーバーヘッドに対応しているが、このデータ空間は外部システムからは利用できない。これら技術の全ては、エラー訂正機能を実行するのに、フラッシュ装置上に追加のダイ領域を必要とする。
【０００５】
エラー訂正を用いると、フラッシュメモリは１つのセクタ内の1ビットのみを訂正でき（4096ビット中の1ビット）、セクタ当たり2ビットのエラーを検出できる。フラッシュ製造者は、この程度の訂正によって大部分の目的は満足されていると主張するが、ファイリングシステムによっては、特定のセクタが受ける破壊のレベルが大幅に増加する可能性があり、極めて短期間で製品故障を発生させる。
【０００６】
ＦＡＴ１６およびＦＡＴ３２などのファイリングシステムは、全てのデータが装置上において格納されている場所をホストプロセッサに通知するのに使用されるテーブルの２つのコピーを保存する。大容量メモリの任意の部分が変更されるたびに、ファイリングシステムによってこの必須のデータは書き換えられる。ＮＡＮＤフラッシュメモリでは、単一位置すなわち単一バイトを独立に消去できないので、ブロック全体（いくつかのセクタを包含している）をフォーマットして、大容量メモリが変更さるたびに書き直す必要がある。これはＵＳＢメモリのような多くの装置に初期故障を発生させる。
【０００７】
この問題に対する１つの解決策は、特定の頻繁にアクセスされるデータ項目が、フラッシュメモリの同一領域にライトバック（書戻し）されずに、そのフラッシュメモリのまわりに散りばめて装置全体にわたって「疲労」を分散させることを保証することである。
【０００８】
明らかに、製造者は、フラッシュドライブに組み込まれる複雑性が絶え間なく増加していくことを望まない。この理由は、このような複雑性の増加はユーザに認知される利点を必ずしも与えることなくコストを増加させるからである。フラッシュ製造者はまた、製品の固有の信頼性欠如に関して大きな問題を発生させることを望まない。
【０００９】
民生オーディオ製造者が直面する１つの問題は、コストがコモディティメモリ市場価格にますます大きく関連してきていることである。デジタルメディアの人気が増大するに伴い、この傾向は大きくなる。しかし、最終消費者は、ＰＣ市場と同様に、オーディオ供給者がこのメモリ価格変動を消費者の購入価格に組み込むことを許さない。したがって、オーディオ供給者は、メモリ市場の変わりやすく気まぐれな傾向に曝されることになる。
【００１０】
民生オーディオ産業はこれを克服する方法を探求してきており、メモリのリサイクルが一般化してきている。別のコモディティメモリ製品であるＤＲＡＭは、古いＳＩＭＭＳから頻繁に回収されて、多くの場合周囲の市場価格の何分の１かである。リサイクルの構えができているオーディオ電子機器産業からのＮＡＮＤフラッシュ需要の改革によって、この種のメモリ製品も部品リサイクル企業のターゲットになるように思われる。
【００１１】
リサイクルされたフラッシュメモリは多くの要因、すなわち(i)古い技術および(ii)欠陥セクタの高い確率、によって特徴付けられる。市場に参入するフラッシュコントローラは全て、リサイクルされたフラッシュメモリを使用可能にするように、これらの欠点を処理する必要がある。
【００１２】
したがって、リサイクルされたメモリに書き込まれるデータおよび／または読み出されるデータを処理する改良されたデータ処理装置が必要とされる。
【発明の開示】
【００１３】
本発明の第１構成によれば、書き換え可能メモリに書き込まれるデータおよびこのメモリから読み出されるデータにエラー訂正アルゴリズムを適用するデータ処理装置が提供される。このデータ処理装置は、ハードウェアに実装されたコーディングユニットと、ソフトウェアに実装されたエラー訂正ユニットとを備える。
【００１４】
前記コーディングユニットは、コーディング動作を実行でき、このコーディングユニット動作において、メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、メモリへの書込み用に第２データセットを出力する。前記コーディングユニットは、さらにエラー検出動作を実行でき、このエラー検出動作では、メモリから読み出されたデータを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する。
【００１５】
前記エラー訂正ユニットは、エラーを含む読み出されたデータを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して前記エラーを訂正し、これにより訂正されたデータを生成し、この訂正されたデータを出力する。
【００１６】
好ましくは、コーディングユニットは、メモリから読み出されたデータがエラーを含まないと判別すると、メモリから読み出されたデータを出力する。
【００１７】
コーディングユニットは、コーディング動作中に第１データセットに実行する処理と同一の処理を、エラー検出動作中にメモリから読み出されたデータのエラー検出処理に実行してもよい。
【００１８】
コーディングユニットは、エラー検出動作中に、メモリから読み出されたデータをコーディング動作に合わせて第１データセットとみなし、このデータをエラー訂正アルゴリズムに従って処理して第２データセットを生成してもよい。
【００１９】
好ましくは、コーディングユニットは、第１データセットが既に書き込まれたメモリ内の第１位置から読み出される情報データと、第２データセットが既に書き込まれたメモリ内の第２位置から読み出される、情報データについてのパリティデータとを受け取る。第２データセットは、コーディング動作中に前記第１データセットから既に生成されたものである。
【００２０】
コーディングユニットは、エラー訂正アルゴリズムに従って情報データを処理して第２データセットを生成し、この第２データセットをパリティデータと比較して、第２データセットがパリティデータと一致しない場合にその情報データがエラーを含むと判別することによって、メモリから読み出されたデータがエラーを含むか否かを判別してもよい。
【００２１】
コーディングユニットは、第１データセットを受け取り、このデータに生成多項式を乗算し、この乗算の結果を第２データセットとして出力する符号語生成器を備えてもよい。
【００２２】
コーディングユニットは、メモリから読み出されたデータを受け取り、この読み出されたデータに含まれる情報データに生成多項式を乗算し、この乗算の結果を読み出されたデータに含まれるパリティデータと比較する符号語生成器を備えてもよい。
【００２３】
コーディングユニットは、メモリから読み出されたデータを受け取り、読み出されたデータに含まれる情報データとパリティデータとを連結し（concatenate）、生成多項式の根を連結されたデータに代入し、その結果の値を加算するシンドローム生成器を備えてもよい。好ましくは、コーディングユニットは、その結果の値の総和（加算値）がゼロでない場合、情報データがエラーを含むと判別する。
【００２４】
シンドローム生成器は、生成多項式の複数の根を連結されたデータにそれぞれ代入し、各代入から得た値を加算してもよい。各代入から得た値の結果は、情報データ内のエラーの場所を表す。
【００２５】
好ましくは、コーディングユニットは、メモリから読み出されたデータがエラーを含むと判別すると、その情報データをエラー訂正ユニットに出力する。
【００２６】
エラー訂正ユニットは、メモリに書き込まれるデータをインターリーブし、メモリから読み出されたデータをデインターリーブしてもよい。
【００２７】
好ましくは、コーディングユニットは、メモリから読み出される256バイトごとに２つ以上のビットエラーを検出できる。
【００２８】
好ましくは、エラー訂正ユニットは、メモリから読み出される512バイトごとに２つ以上のビットエラーを訂正できる。
【００２９】
エラー訂正アルゴリズムはリードソロモン・コード（Reed-Solomon code）であってもよい。好ましくは、エラー訂正アルゴリズムはクロスインターリーブ・リードソロモン・コード（ＣＩＲＣ）である。
【００３０】
好ましくは、エラー訂正ユニットはデジタルプロセッサである。
【００３１】
本発明の第２構成によれば、データ記憶装置が提供され、このデータ記憶装置は、書き換え可能メモリと、ハードウェアに実装されたコーディングユニットと、ソフトウェアに実装されたエラー訂正ユニットとを備える。
【００３２】
前記コーディングユニットは、コーディング動作を実行でき、このコーディングユニット動作において、メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、メモリへの書込み用に第２データセットを出力する。前記コーディングユニットは、さらにエラー検出動作を実行でき、このエラー検出動作では、メモリから読み出されたデータを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する。
【００３３】
前記エラー訂正ユニットは、エラーを含む読み出されたデータを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して前記エラーを訂正し、これにより訂正されたデータを生成し、その訂正されたデータを出力する。
【００３４】
プロセッサによってデータを読出しおよび／または書込みするのに用いられるメモリの少なくとも1つのセクタは、512バイト当たり１ビットよりも大きいエラー率を有してもよい。
【００３５】
メモリはリサイクルされた集積メモリであってもよい。
【００３６】
メモリは従来の許容できる製造標準を超えるエラー率を有してもよい。
【００３７】
好ましくは、メモリはフラッシュメモリである。メモリは、さらに好ましくは、ＮＡＮＤフラッシュメモリである。
【００３８】
メモリは、そのビットが単独でアクセスされないものであってもよい。
【００３９】
本発明の第３構成によれば、書き換え可能メモリに書き込まれるデータおよびこのメモリから読み出されるデータを処理する方法が提供される。この方法は、ハードウェアでコーディング動作を実行し、ハードウェアでエラー検出動作を実行し、ソフトウェアでエラー訂正動作を実行する。
【００４０】
前記コーディング動作は、メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、メモリへの書込み用に第２データセットを出力する。
前記エラー検出動作は、メモリから読み出されたデータを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する。
【００４１】
前記エラー訂正動作は、エラーを含む読み出されたデータを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して前記エラーを訂正し、訂正されたデータを出力する。
【００４２】
本発明の第４構成によれば、書き換え可能メモリをリサイクルする方法であって、メモリが機能している装置からそのメモリを取り除いて、このメモリを別の装置内に設置する。この別の装置はデータ処理装置を有し、このデータ処理装置は、ハードウェアに実装されたコーディングユニットと、ソフトウェアに実装されたエラー訂正ユニットとを備える。
【００４３】
前記コーディングユニットは、コーディング動作を実行でき、このコーディングユニット動作において、メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、メモリへの書込み用に第２データセットを出力する。前記コーディングユニットは、さらにエラー検出動作を実行でき、このエラー検出動作では、メモリから読み出されたデータを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する。
【００４４】
前記エラー訂正ユニットは、エラーを含む読み出されたデータを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して前記エラーを訂正し、これにより訂正されたデータを生成し、その訂正されたデータを出力する。
【発明を実施するための最良の形態】
【００４５】
本発明を添付図面に関連する例を用いて説明する。
【００４６】
本発明の各実施形態は、書き換え可能メモリにおいて使用するためのデータ処理装置を提供する。この装置は特に、多数の破壊されたセクタを含むリサイクルメモリ、または正常装置として販売されるにはエラー率が高すぎる製造メモリにおいて使用するのに適する。このデータ処理装置は、エラー訂正コードに従って、メモリに書き込まれるデータおよび／またはこのメモリから読み出されるデータを処理するように構成されている。有利なことには、このデータ処理装置はコーディングと訂正機能をハードウェアとソフトウェアとに分けて、これにより、読出し時間および書込み時間に大きなオーバーヘッドを付加させることなく、またプロセッサに要求される処理能力を増大させることなく、極めて有効なエラー訂正コード（破壊されたメモリセクタによって生じるデータエラーを処理するのに必要である）を実現できる。この点が、メモリに書き込まれるデータおよびメモリから読み出されるデータ全てをソフトウェアで処理する多くの既存のメモリコントローラとは異なる。
【００４７】
図１に、本発明の一実施形態にかかるデータ処理装置を示す。データ処理装置は全体を１０１で示され、メモリ１０２に結合されている。データ処理装置１０１は、ハードウェアで実現されたコーディングユニット１０３とソフトウェアで実現されたエラー訂正ユニット１０４とを備える。エラー訂正ユニット１０４にはデジタルプロセッサが適する。
【００４８】
コーディングユニット１０３はメモリ１０２に書き込まれるデータを受け取るように構成されている。コーディングユニット１０３は、メモリに書き込まれるデータをコード化し、このコード化データを出力する。コーディングユニット１０３は、また、コード化データをメモリに書き込むことができる。好ましくは、コーディングユニット１０３は組織コード（システマティックコード(systematic code)）を実現する。このユニット１０３では、コーディングプロセスがメモリへの書込み対象のデータから、データ自体を変更するのではなく、追加のコード化データ（すなわち、パリティデータ）を生成する。
【００４９】
コーディングユニット１０３は、メモリ１０２に書き込まれるコード化データのみを出力してもよく、またはコード化データおよびメモリ１０２への書込み用に実際のデータの両方を出力してもよい。その後、コード化データおよび実際のデータは異なるメモリ位置に記憶されてもよい。すなわち、実際のデータはそのデータについてのパリティデータの近く記憶される必要はない。
【００５０】
コーディングユニット１０３はまた、メモリ１０２から読み出されたデータを受け取るように構成されている。このデータには、オリジナルデータが書き込まれたメモリ位置から読み出された情報データと、その情報データについてのパリティデータ、すなわちオリジナルデータから生成されたコード化データが書き込まれたメモリ位置から読み出されたデータとが含まれる。コーディングユニット１０３は、メモリ１０２から読み出されたデータを処理して、そのデータがエラーを含むか否かを検出する。この処理にはパリティデータおよび情報データの両方、またはパリティデータのみを含んでもよい。メモリ１０２から読み出されたデータ内において１つまたは複数のエラーをコーディングユニット１０３が検出すると、コーディングユニット１０３はエラーのあるデータをエラー訂正ユニット１０４に送る。コーディングユニット１０３がエラーを検出しない場合、コーディングユニットはその情報データを出力する。代わりに、コーディングユニット１０３は、メモリに結合されているコントローラのような別の構成要素に信号を送ってもよく、この構成要素によって情報データは安全に出力される。
【００５１】
上述のエラーコーディングおよび検出動作に加えて、コーディングユニット１０３はまた、エラー訂正動作の間において、エラー訂正ユニット１０４にハードウェアサポートを提供する。リードソロモン・コードのようなエラー訂正アルゴリズムによって必要とされるデータ処理動作のいくつかは、特にハードウェアでの実現に適している。コーディングユニット１０３にこの処理の一部を実行する能力を備えることによって、エラー訂正プロセスを加速できる。この追加の処理には、例えばシンドロームの算出および処理を含むことができ、これに関しては以下に詳細に説明される。このような追加の処理は、メモリ１０２から読み出されたデータがエラーを含むことをコーディングユニット１０３が判別すると直ぐに、コーディングユニット１０３によって実行され、この処理から生成される追加データ（例えば、シンドローム）全てが、エラーのあるデータと共にエラー訂正ユニット１０４に送られる。代わりに、コーディングユニット１０３がこのような追加の処理をエラー訂正ユニット１０４の制御の下で実行してもよい。すなわち、エラー訂正ユニット１０４によって処理されるのに適切なデータが送出される場合、コーディングユニット１０３は、エラーのあるデータ全てを直ちにエラー訂正ユニット１０４に送り、追加処理のみを実行してもよい。
【００５２】
コーディングユニット１０３は、メモリに書き込まれるデータおよび／またはメモリから読み出されるデータを処理するために、様々な専用ハードウェアブロックと協働してもよい。例えば、コーディングユニット１０３は、上述のコーディングおよびエラー検出動作を実行するのに、同一ハードウェアブロックを使用してもよい。代わりに、コーディングユニットは２つのハードウェアブロック、すなわち、メモリに書き込まれるデータのコーディング用の１つのブロック、およびメモリから読み出されるデータにおけるエラー検出用の１つのブロックを備えてもよい。コーディングユニット１０３は、任意の追加処理を実行するためにさらに専用ハードウェアを備えてもよい。コーディングユニット１０３は、様々な専用ハードウェアブロックを備えることにより、エラー訂正ユニット１０４のソフトウェアによって実行される、様々なエラー訂正アルゴリズムに対してハードウェアサポートを提供してもよい。
【００５３】
コーディングユニット１０３において追加のデータ処理を実行する代わりとして、任意のエラー訂正処理のために別個のハードウェアユニットをエラー訂正ユニット１０４に結合してもよい。この任意のエラー訂正処理は、ハードウェアで効率的に実行され、これによりエラー訂正動作を加速できる。
【００５４】
エラー訂正ユニット１０４は、コーディングユニット１０３からのデータを受け取り、その情報データ内に含まれるエラーを訂正するように構成されている。エラー訂正ユニット１０４によって受け取られるデータは、情報データ、パリティデータ、およびコーディングユニット１０３によって算出された随意の何らかのさらなるデータ（例えばシンドロームデータ）を含んでもよい。
【００５５】
これを実現する（エラー検出はハードウェアで実行されるが、エラー訂正はソフトウェアで実行される）ことによって提供される利点の１つは、ハードウェアのコーディングユニット１０３が追加の複雑性に注意を払うことなく、プロセッサによって、複雑な追加層をエラー訂正コーディング方式内に導入できることである。例えば、プロセッサは、メモリに書き込まれるデータおよびメモリから読み出されるデータにインターリーブおよびデインターリーブを実行してもよい。インターリーブ／デインターリーブされたデータは、プロセッサによって必要に応じてコーディングユニット１０３に送られる。この際にコーディングユニット１０３によって実行されるコーディングおよびエラー検出動作は、追加機能が付加される前のままである。
【００５６】
本発明の実施形態によるデータ処理装置の別の利点は、プロセッサによって用いられるアルゴリズムを変更することによって広範囲のエラー訂正方式を実現するのに、このデータ処理装置が用いられることである。コーディングユニット１０３によって実行される基本のコーディングおよびエラー検出機能は変更されない。また、エラー検出機能がハードウェアで実行されるため、プロセッサによって実現されるアルゴリズムを変更することに起因して読込み動作に付加されるオーバーヘッドの増加の影響を最小にできる。この理由は、任意の追加オーバーヘッドが全ての読込み動作内に存在するのではなく、エラーが検出される読込み動作に限定されるからである。
【００５７】
本発明の各実施形態によるデータ処理装置の全体動作が、図２Ａおよび２Ｂに示されている。図２Ａは書込み動作を示す。この動作では、データ処理装置が、書込みデータをステップＳ２０２で受け取り、ステップＳ２０４でこのデータを処理し、ステップＳ２０６でコード化データを出力する。図２Ｂは読出し動作を示す。この動作では、メモリから読み出されたデータはステップＳ２０８で受け取られ、データがエラーを含むか否かを判別するためにステップＳ２１０で処理される。データがエラーを含むと判別されると、ステップＳ２１２でそのエラーを訂正するようにデータが処理され、訂正されたデータはステップＳ２１４で出力される。メモリから読み出されたデータがステップＳ２１０でエラーを含まないと判別されると、メモリから読み出されたデータはステップＳ２１６で出力される。上述のとおり、メモリから読み出されたデータは、データ処理装置自体によって出力されてもよく、あるいはメモリに結合されている別の装置によって出力されてもよい。この別の装置には、データ処理装置が信号を出して、メモリから読み出されたデータがこのままの形で出力可能であること指示する。
【００５８】
コード化データを生成し、メモリから読み出されたデータのエラーを検出し、これらのエラーを訂正する上述の各ステップは、エラー訂正コードを用いて実行される。上述のように、既存メモリのなかには、何らかの簡単なエラー訂正を組み込むために、ハミングコードを用いるものもある。しかし、このハミングコードによるエラー訂正レベルは、リサイクルメモリまたは正常装置として販売されるには過大なエラー率を有するメモリ内に存在する多数の破壊されたセクタを処理するのに不十分である。フラッシュメモリは一般に、使用不可能ブロックの最大は2％（すなわち、2048中の最大40ブロック）で販売される。一般に、使用不可能ブロックの割合が2％を超えるメモリは全て除外される。
【００５９】
古いリサイクルされたフラッシュメモリの使用を可能にするために、拡張エラー訂正方式を適用することが２つの理由のために必要である。これら理由は、(i)古いタイプのメモリが内部に簡単なハミングコードエラー訂正さえも含まないこと、および(ii)ハミングコードの能力をすでに超えており（これがそもそもリサイクルされる理由である）、フラッシュメモリはすでに「破壊されている」と考えられること、である。
【００６０】
デジタルデータストリームに対してエラー訂正を実行する方法は多数存在し、これらの全ては計算およびメモリオーバーヘッドを含み、さらにそのうちのいくつかは他に比べてより煩わしい処理である。全ての順方向エラー訂正（ＦＦＣ）の訂正システムは複雑で高度であり、一般に、開発にかなりの時間と労力を要する。
【００６１】
本発明の各実施形態によるデータ処理装置によって用いられるいくつかのエラー訂正方式は以下に説明される。これは単に例示のためであり、本発明は特定のいずれかのコーディング方式に限定されないことが理解されるべきである。上述のとおり、本発明の各実施形態によるデータ処理装置を用いて、広範囲のエラー訂正方式を実現できる。また、後述するように、プロセッサは、メモリに書き込まれるデータおよび／またはメモリから読み出されるデータに追加レベルのエラー訂正コーディングを適用するように構成されてもよい。
【００６２】
本発明の各実施形態によるデータ処理装置によって用いられる適切なエラー訂正方式は、リードソロモンエラー訂正コードを含む。一般に、これらのコードはデータフレームにパリティバイトを追加することを含む。エラーが存在していることを判別するのが可能であるばかりでなく、いかなるエラーであり、いずれの位置にそのエラーが存在するかを判別するように、パリティバイトが算出される。ある一定の制限内で、１つのフレーム内のいくつかのエラーを訂正することができる。この基本エラー訂正能力は、クロスインターリーブ・リードソロモン・コーディング（ＣＩＲＣ）として知られているクロスインターリービングによって拡張される。一般的なリードソロモン・コードおよびＣＩＲＣコードは、ガロアフィールド（Galois field）演算の説明と共に以下で詳細に説明される。このガロアフィールド演算は、直接ハードウェアデコーダを作り出すのに有効に利用できる。
【００６３】
リードソロモン・コードは、ディジタルデータのブロックに冗長パリティビットを追加することを含むエラー訂正コードである（図３に示されるとおり）。各リードソロモン・コードはｓビットのシンボルのＲＳ（ｎ，ｋ）として定義される。これは、それぞれｓビットのｋデータシンボルを処理して、冗長パリティビットを得ることを意味し、このパリティビットがデータシンボルに加えられると、ｎシンボル符号語を生成する。リードソロモン・デコーダは、１つの符号語において最大２ｔ個のエラーを検出でき、１つの符号語において最大ｔ個のエラーを訂正できる。ここで、２ｔ＝ｎ−ｋである（すなわち、パリティビットの数である）。エラーを有するシンボルの位置が分かる場合、このエラーを有するシンボルは消失と呼ばれる。リードソロモン・デコーダは、１つの符号語において最大２ｔ個の消失を訂正できる。
【００６４】
リードソロモン符号語は、生成多項式として知られる特殊多項式によって生成される。全ての有効な符号語は生成多項式によって割り切れる。生成多項式の一般形は以下の式で与えられる。
【００６５】
【数１】
2009501380.tif 000003
【００６６】
符号語は以下の式で構成される。
【００６７】
【数２】
2009501380.tif 000004
【００６８】
ここでｇ（ｘ）は生成多項式であり、ｉ（ｘ）は情報ブロックであり、ｃ（ｘ）は有効な符号語であり、αは原始元として知られている。
【００６９】
１つの例として、６個のパリティビットを生成するリードソロモン・コードに対して、式（１）は以下のように書くことができる。
【００７０】
【数３】
2009501380.tif 000005
【００７１】
組織リードソロモン符号語における２ｔ個のパリティシンボルは以下の式で与えられる。
【００７２】
【数４】
2009501380.tif 000006
【００７３】
リードソロモン・エンコーダのアーキテクチャの１つの例が、図４に示されている。この図に示された各レジスタは、１つのシンボルを保持し、算術演算子が完全シンボル（complete symbol）に加算または乗算を実行する。
【００７４】
本発明の各実施形態によるデータ処理装置では、メモリ１０２に書き込まれる各情報ブロックに対するパリティビットの算出は、コーディングユニット１０３内の専用ハードウェアによって実行される。ソフトウェア実装を用いずにハードウェア実装においてパリティビットを算出することによって、パリティシンボルはより高速に算出される。これにより、各書込み動作に付加されるオーバーヘッドを低減することができる。
【００７５】
データがメモリ１０２から読み出される際に、パリティシンボルの書込みと同一の算出がデータコーディングユニット１０３内のこの専用ハードウェアによって実行されてもよい。例えば、コーディングユニット１０３はメモリ１０２から読み出された符号語を受け取り、この符号語を情報データとパリティデータとに分離してもよい。メモリから読み出された情報データに生成多項式で書込みと同一の乗算を実行することによって、パリティシンボルの新しいセットを生成できる。次に、この新しいパリティシンボルをメモリ１０２から読み出されたパリティシンボルと比較して、符号語がエラーを含むか否かを判別できる。新しく算出されたパリティシンボルがメモリから読み出されたパリティシンボルに一致しない場合に、メモリから読み出された符号語におけるエラーが検出される。これは、メモリ１０２から読み出されたパリティシンボルから新しく生成されたパリティシンボルを減算することによって直接得られてもよい。減算の結果がゼロでない場合、メモリから読み出された符号語はエラーを含むと判別される。
【００７６】
上述のとおり、パリティシンボルと、特定の符号語を含むデータシンボルとは、メモリ内において隣接データとして格納される必要はない。したがって、特定の情報ブロックについてのパリティデータが記憶されているメモリ１０２内の位置は情報ブロックの位置と共に記録され、これにより、その情報ブロックがメモリ１０２から読み出されるとき、その情報についてのパリティデータもまた読み出される。このようにして、完全符号語（complete codeword）がエラー検出のためにコーディングユニット１０３に渡される。
【００７７】
メモリから読み出されたデータについてのコーディングユニット１０３によって実行される処理が、符号語内にエラーが存在することを示すと、この符号語はすぐにエラー訂正ユニット１０４に渡され、ソフトウェアで処理される。符号語内の任意のエラーを訂正するタスクは、エラーを検出するタスクに比べて煩わしことより、このタスクはエラー訂正ユニット１０４によってソフトウェアで有利に実行される。いくつかの実装においては、コーディングユニット１０３はエラーが存在する符号語の何らかの追加処理を実行することによって、ソフトウェア処理を加速してもよい。例えば、有利には、メモリ１０２から読み出された符号語から「シンドローム」を生成してもよい。シンドロームは以下にさらに詳細に説明される。
【００７８】
「シンドローム」は、生成多項式の根をメモリ１０２から読み出された符号語に代入することによって生成される。各代入（すなわち、生成多項式の各根に対して）によって生成されたシンボルを加算することにより、シンドロームを生成する。訂正された符号語に対するシンドロームのそれぞれはゼロである。シンドロームがゼロでない場合、これは符号語がエラーを含むことを意味する。生成多項式の２ｔ個の根が存在するので、１つの符号語に対して２ｔ個のシンドロームが存在する。各シンドロームは各符号語におけるエラーにのみ依存する。これらシンドロームは、符号語内のエラーの検出およびエラー位置の判別の両方に用いられることができる。
【００７９】
シンドロームはエラーの検出および訂正の両方に用いられることができるため、本発明のいくつかの実施形態においては、有利には、コーディングユニット１０３が、パリティデータを算出する代わりに、メモリ１０２から読み出された符号語からシンドロームを算出するように構成されてもよい。次に、コーディングユニット１０３は、そのデータから２ｔ個のシンドロームを算出し、これらシンドロームのうちにゼロでないものがあるか否かを判別することによって、メモリ１０２から読み出された符号語がエラーを含むことを検出できる。エラーが検出されると、エラーが存在する符号語およびその符号語から算出されたシンドロームは、コーディングユニット１０３によってエラー訂正ユニット１０４に渡される。これは本発明の特に有効な実施形態である。その理由は、エラーを検出するためにコーディングユニット１０３によって算出されるシンドロームデータが、任意の検出エラーを訂正するためにエラー訂正ユニット１０３によって用いられるからである。本発明のこのような実施形態によるコーディングユニットは、別々のハードウェアブロックに設けられてもよい。すなわち、１つのハードウェアブロックは、コーディング動作の間にパリティデータを算出するものであり、別の１つのハードウェアブロックは、エラー検出動作の間にシンドロームを算出するものである。図５には、シンドロームデータを算出するのに適した一般的なアーキテクチャが示されている。一般に、コーディングユニット１０３には、２ｔ個のこれらアーキテクチャが設けられている。１つのアーキテクチャが、符号語の１つのシンドロームを算出するものである。これにより、特定の符号語の各シンドロームを並列に算出できる。
【００８０】
上記の式（３）からわかるように、生成多項式の各根が原始元αの累乗の違いを有するので、シンドロームもそれぞれも原始元αの累乗の違いを有する（これはまた、以下の式（７）からも明らかである）。したがって、エラーの位置は、シンドロームを除算し、対数を取ることによって判別できる。このような計算は、ガロアフィールド演算を利用できる、簡略化可能なハードウェア実装に好適である。
【００８１】
ガロアフィールド演算では、バイトの各ビットは原始元の累乗のモジュロ２の係数と考えられる。上述のシンドロームを処理するとき、この原始元は生成多項式の原始元αである。
【００８２】
データのこの処理の実際の利点は、データを加算、減算、乗算、除算でき、その結果は常にフィールド内、すなわちバイト幅内に収まることである。これは、データバイトの演算組合せであるエラー検出コードまたはエラー訂正コードが実際のデータに関係なく常にバイト幅である、ということを意味する。
【００８３】
ガロアフィールドの要素は、疑似乱数発生器と類似のフィードバックを有するシフトレジスタによって生成されることができる。ＣＤにおいては、シフトレジスタはＬＳＢからＭＳＢにシフトし、実行されると、値１Ｄ（16進）はＸＯＲ（排他的論理和）演算されてバイトに格納される。したがってガロアフィールドの第１要素は、１６進数で以下のようになる。
1，2，4，8，10，20，40，80，1D，3A，74、E8，CD…
【００８４】
255回シフト後にこのサイクルが繰り返される。数学的には、各シフトはαの乗算と考えられるため、フィールドの各要素はαの累乗と考えることができる。ゼロはフィールドの要素ではないことに注意されるべきである。これは２つの理由から当然のことである。第１に、シフトレジスタ内のゼロは、シフト回数に関係なく常にゼロとなるからである。第２に、αの累乗はゼロでありえないからである。ゼロの場合には、特殊事例として扱われる必要がある。
【００８５】
フィールド内の２つの要素の加算および減算は同一である。これらの結果は単に、２バイトのＸＯＲ（排他的論理和）である。これは、各ビットがモジュロ２係数であるからである。
【００８６】
乗算および除算は多少複雑である。各要素はαの累乗と考えることができるため、任意の要素の対数を取ることができる。対数は単に、上述のシーケンス内の位置、すなわち、シフトの数つまりαの指数である。したがって、１の対数は０であり、３Ａの対数は９である。２バイトを乗算または除算するために、最初に各要素の対数を取り、次にその対数を加算または減算し、次にαをこの指数で累乗して結果を得る。
【００８７】
フィールド内には255個の要素のみしか存在しないので、乗算および除算はさらに複雑になる。これは、対数を加算または減算するとき、モジュロ２５５をとらなければならないことを意味する。
【００８８】
上述のリードソロモン・コードのエラー訂正能力は、インターリービングを使用することによってさらに向上できる。クロスインターリーブ・リードソロモン・コード（ＣＩＲＣ）におけるこの結果は、極めて強力なエラー訂正アルゴリズムである。
【００８９】
リードソロモン・コードの基本エラー訂正能力は、クロスインターリービングによって拡張される。これは、データを２次元配列に配置し、行および列に対してそれぞれのパリティバイトを計算することを実質的に意味する。これは、メモリの欠陥セクタから一次元における多数の隣接バイトに影響を与えると予測されるバーストエラーが、他の次元においてはフレーム当たり１バイトまたは２バイトのみに影響を与えることを意味する。このような配列は図６に示されている。
【００９０】
「垂直」すなわち列の方向のフレームはＣ１で表され、32バイトを含み、このうちの4バイトはパリティである。「水平」すなわち行の方向のフレームはＣ２で表され、28バイトを含み、このうちの4バイトはパリティである。Ｃ１およびＣ２を処理した後、２４データバイトが残る。これらは６個のステレオサンプルと等価である。
【００９１】
Ｃ１およびＣ２の両方に対するパリティバイトはほぼ同一の方法で算出される。Ｃ１のパリティは、以下の式が成立するようにして算出される。
【００９２】
【数５】
2009501380.tif 000007
【００９３】
シンボルｄ0〜ｄ31はフレーム内のバイトである。Ｃ２は２８バイトのみ存在するので、わずかに異なり、そのためαの指数は小さい。
【００９４】
データはシンドローム生成ロジックを用いて容易にチェックされる。このロジックは４個のアキュムレータを含む。バイトにシンドロームロジックが書き込まれる場合、各アキュムレータの以前の値には、それぞれ、１、α１、α２およびα３が乗算され、その後、新しいバイトに加算される。これにより、フレームのサイズに関係なく、上記計算は効率的に実行される。
【００９５】
データが正しい場合、アキュムレータにおけるシンドロームとして知られている値は全てゼロになる。シンドロームがゼロでない場合、シンドロームを用いて、３つの方法の内の１つ、すなわち単一エラー訂正、２重エラー訂正および４−消失訂正のいずれかでエラーを訂正できる。
【００９６】
メモリ１０２から読み出されたデータからパリティデータの新しいセットを算出して、そのデータがエラーを含むか否かを決定するよりもむしろ、コーディングユニット１０３は、受け取った符号語のシンドロームを算出するように構成されてもよい。シンドロームがゼロでなければ、エラーが検出される。
【００９７】
＜単一エラー訂正＞
１つのみのエラー、例えばｄ5のみエラーが存在する場合、４つのシンドロームバイトは以下で与えられる。
【００９８】
【数６】
2009501380.tif 000008
【００９９】
ここで、ｅはｄ5の訂正値と受け取った値との差である。
【０１００】
エラーがｓ0で与えられるのは明らかである。エラーの位置は、ｓ1をｓ0で割算することによって、かつ、対数を取ってαの累乗を算出することによって、判別できる。複数のエラーを単一エラーに見せかけることは常に可能である。ｓ2およびｓ3を用いて再度位置を算出することによって、信頼性を高めることができる。これらの位置は一致しており、0〜31の範囲である。このとき、訂正失敗の確率はわずかに524,288分の1である。
【０１０１】
＜２重エラー訂正＞
シンドロームバイト内には、２つのエラーの値および位置を特定するのに十分な情報が存在する。このアルゴリズムは比較的複雑である。Peterson-Berlekampアルゴリズムを用いて位置多項式と呼ばれる式を見出すことができる。位置多項式の値が求められると、多項式の根を見出すことができる。これはChien検索法を用いて達成してもよい。位置多項式はまた、ユークリッド・アルゴリズムを用いて見出すこともできる。このアルゴリズムは通常、Peterson-Berlekampアルゴリズムよりも効率は低いが、ハードウェアでの解決法にはより適している。
【０１０２】
２重エラーの訂正失敗の確率は32分の1である。しかし、Ｃ１における２回のエラー訂正によって提供される低い信頼性は、Ｃ２において提供される２重チェックによって向上する。
【０１０３】
１つの符号語内に２つのエラーが存在する場合、最初の２つのシンドロームは以下の式になる。
【０１０４】
【数７】
2009501380.tif 000009
【０１０５】
ここで、Ｌ0およびＬ1は既知のエラー位置である。この式はｅ0およびｅ1について以下のように解くことができる。
【０１０６】
【数８】
2009501380.tif 000010
【０１０７】
減算はこれらの式を解く場合は加算と等価であることに注意すべきである。
【０１０８】
＜４−消失訂正＞
上述のとおり、消失は、エラーの位置が既知であるがエラーの値が未知である場合のフレーム内のエラーに付けられている名称である。これが発生するのは、データの列がＣ１ステージにおいて不具合のフラグを立てるときであって、その後、そのデータがＣ２ステージで処理されるとき、単一バイトのみが不具合とマークされる。フラグを立てられた列はエラー位置に移る。Ｃ２は最大４つの消失を訂正できるので、４つの隣接する列にエラーがあってもよい。別々の４つの列から連続行データが生じるように、データをずらす（スキューする）ことによって、この能力はさらに４倍に向上する。このようにして、１６の連続するエラーのあるフレームを訂正できる。
【０１０９】
４つのエラーを有するフレームに対するシンドロームは以下の式で与えられる。
【０１１０】
【数９】
2009501380.tif 000011
【０１１１】
Ｌ0、Ｌ１、Ｌ2およびＬ3の値はＣ１からのフラグによって与えられる。
【０１１２】
したがって、４つの未知数のｅ0、ｅ1、ｅ2およびｅ3を有する４つの一次方程式が存在し、多数の方法で解くことができる。１つの方法は４つの式をマトリクスと考える方法である。
【０１１３】
【数１０】
2009501380.tif 000012
【０１１４】
行を乗除算し、１つの行を別の行から減算することによって、マトリクスは恒等行列に変換できる。
【０１１５】
【数１１】
2009501380.tif 000013
【０１１６】
このとき、エラーは、変更されたシンドロームバイトに等しくなる。コードは速度向上のために特定のショートカットを用いる。係数がその最終値に達すると、係数は必要とされなくなるので、その値を計算して記憶する必要はなくなる。
【０１１７】
４つよりも少ないエラーしか存在しない場合、フレーム外のダミー位置を生成して、４つのエラーにまでする。１、２および３の消失に対応する専用コードを設けることで、個々のフレームを高速化してもよい。しかし、システムは連続する４つの消失を扱う必要があるため、一般に、システムにはこのような専用コードを設ける利点はない。訂正されたフレームについてシンドロームの最終チェックが実行される。
【０１１８】
エラー訂正の第２ステージのみが用いられる場合、デインターリーブするバッファを伴うこのステージは、エラーのあるデータの単一ビットさえもホストＣＰＵによって発見されることなく、エラー内の最大4096個の連続ビットを訂正できる。これは現在のエラー訂正に比べて4096倍の性能向上であり、略式検査で予測される大きなオーバーヘッドもない。
【０１１９】
メモリ供給者によって用いられる典型的なメモリエラー訂正アルゴリズムにおいては、冗長度は512バイトごとに16バイトである。したがって、フラッシュメモリに記憶されるデータの3.1％がエラー訂正オーバーヘッドであり、ＣＩＲＣに基づくシステムでは、この冗長度レベルは12.5％になる（Ｃ２のみを用いる場合）。しかし、上述の方法の場合、エラー訂正能力が4096：1となる。ＣＩＲＣエラー訂正はまた、現在使用されていないハミングコードシステムから利用可能な追加空間を再利用して、データ冗長度をわずか9.4％にまで下げることができる。
【０１２０】
エラー訂正能力をさらに向上させる方法として、複数セクタの訂正を可能とするために、データをさらにインターリーブすることができる。例えば、４つのセクタにわたってインターリーブされたデータを用いてメモリ装置にデータが書き込まれた場合、エラー訂正システムは、完全に破壊された４つの連続セクタからデータを完全に回復できる。この追加のインターリーブは、データ処理に必要とされる追加メモリのコストを伴うが、ＣＰＵ内に十分なワーキングメモリがあれば、訂正可能データの最大長さを任意の長さにまで拡張できることは明らかである。
【０１２１】
図７は、典型的なＮＡＮＤフラッシュメモリの４つの512バイトセクタにわたって動作するときの、さらなるインターリービング構造を示す。図７では、ｂｎはビット数であり、ｗｎはワード数である。この場合においては、ワードは８ビット長さである。
【０１２２】
完全なエンコードおよびデコーダのための処理オーバーヘッドは、データ内で見つかるエラーのレベルに応じて典型的な128kbpsのＭＰ３ファイルについては1〜4MIPSよりも小さくするべきであり、全体メモリ使用量は約1.5Kbyteとする。
【０１２３】
本発明の各実施形態によるデータ処理装置のプロセッサは、ＣＤデータデコーダ内に存在する既存の命令を使用してもよい。これは、データ訂正プロセスを加速するのに役立つ。
【０１２４】
エラー訂正の目的：リサイクルされたフラッシュメモリを再使用可能にすることがこのシステムが提供する唯一の利点でなく、フラッシュメモリ装置の搭載シリコンにコストがかかるという問題の解決を必要とせずに、フラッシュ製品の寿命も大幅に長くすることである。
【０１２５】
本発明の各実施形態によるデータ処理装置は、リサイクルメモリ、または正常に販売されるにはエラー率が高すぎる製造メモリであって、正常に販売されない場合は製品から除去される製造メモリなどの、多数の破壊されたセクタを含むメモリと共に使用されるのが、特に有利である。しかし、このデータ処理装置は、このような破壊されたメモリに結合された実装に限定されない。このデータ処理装置は、ソフトウェアのみでこのようなエラー訂正コードを実現する場合に一般に必然的に伴う読出しおよび書込みオーバーヘッドを増加させずに、任意の実装において有利に利用できる。
【０１２６】
本発明の各実施形態によるデータ処理装置は特にフラッシュメモリに関して上述した。しかし、この技術はＤＲＡＭまたは任意の別の種類の固体メモリ装置にも同様に適用できる。
【０１２７】
有利には、本発明によるデータ処理装置は、ＣＤプレーヤ、デジタルオーディオプレーヤ、デジタルカメラ、携帯電話などの広範囲の消費者電気製品に組み込まれてもよい。
【０１２８】
本件出願人は、本明細書において個々の形態をそれぞれ単独で開示している。これら形態の２つ以上の組み合わせは、このような形態または組み合わせが本明細書全体の記載に基づき、当業者の一般的知識に照らして実施が可能であれば、ここに開示の諸問題を解決するかどうかにかかわらず、実施可能であるが、これらが請求項の範囲を限定するものではない。本件出願人は、本発明の態様が、これら各形態のいずれかあるいはこれら形態の任意の組み合わせから構成できることを指摘しておく。以上の説明に照らし、当業者には、本発明の範囲内で各種の変更が可能であることは明らかであろう。
【図面の簡単な説明】
【０１２９】
【図１】本発明の一実施形態によるデータ処理装置を示す図である。
【図２Ａ】本発明の一実施形態によるデータ処理装置の動作のうち、書込み動作を示すフローチャートである。
【図２Ｂ】本発明の一実施形態によるデータ処理装置の動作のうち、読出し動作を示すフローチャートである。
【図３】データおよびパリティビットを有する、リードソロモン・コードによって生成された符号語を示す図である。
【図４】組織エンコーダの全体アーキテクチャを示す図である。
【図５】シンドローム計算器の全体アーキテクチャを示す図である。
【図６】クロスインターリーブ・リードソロモン・コードに従って構成されるデータビットおよびパリティビットを示す図である。
【図７】複数セクタを訂正可能にするインターリーブ・データを示す図である。
【符号の説明】
【０１３０】
１０２  メモリ
１０３  コーディングユニット
１０４  エラー訂正ユニット
【図１】
2009501380.tif 000014
【図２Ａ】
2009501380.tif 000015
【図２Ｂ】
2009501380.tif 000016
【図３】
2009501380.tif 000017
【図４】
2009501380.tif 000018
【図５】
2009501380.tif 000019
【図６】
2009501380.tif 000020
【図７】
2009501380.tif 000021
【手続補正書】
【提出日】平成20年7月31日(2008.7.31)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
書き換え可能メモリに書き込まれるデータおよびこのメモリから読み出されるデータにエラー訂正アルゴリズムを適用するデータ処理装置であって、
ハードウェアに実装されたコーディングユニットであって、コーディング動作を実行でき、このコーディング動作において、前記メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、前記メモリへの書込み用にこの第２データセットを出力し、さらにエラー検出動作を実行でき、このエラー検出動作では、前記メモリから読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する、コーディングユニットと、
ソフトウェアに実装されたエラー訂正ユニットであって、エラーを含む読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理してエラーを訂正し、これにより訂正されたデータを生成し、この訂正されたデータを出力する、エラー訂正ユニットとを備えたデータ処理装置。
【請求項２】
請求項１において、前記コーディングユニットは、メモリから読み出されたデータがエラーを含まないと判別すると、メモリから読み出されたデータを出力する、データ処理装置。
【請求項３】
請求項１または２において、前記コーディングユニットは、前記コーディング動作中に第１データセットに実行する処理と同一の処理を、前記エラー検出動作中にメモリから読み出されたデータのエラー検出処理に実行する、データ処理装置。
【請求項４】
請求項３において、前記コーディングユニットは、エラー検出動作中に、メモリから読み出されたデータをコーディング動作に合わせて第１データセットとみなし、このデータを前記エラー訂正アルゴリズムに従って処理して第２データセットを生成する、データ処理装置。
【請求項５】
請求項１から４のいずれか一項において、前記コーディングユニットは、第１データセットが既に書き込まれた前記メモリ内の第１位置から読み出される情報データと、第２データセットが既に書き込まれた前記メモリ内の第２位置から読み出される情報データについてのパリティデータとを受け取るように構成されており、前記第２データセットはコーディング動作中に前記第１データセットから既に生成されたものである、データ処理装置。
【請求項６】
請求項４において、前記コーディングユニットは、第１データセットが既に書き込まれた前記メモリ内の第１位置から読み出される情報データと、第２データセットが既に書き込まれた前記メモリ内の第２位置から読み出される情報データについてのパリティデータとを受け取るように構成されており、前記第２データセットはコーディング動作中に前記第１データセットから既に生成されたものであり、前記コーディングユニットは、前記エラー訂正アルゴリズムに従って前記情報データを処理して第２データセットを生成し、この第２データセットを前記パリティデータと比較して、前記第２データセットが前記パリティデータと一致しない場合にその情報データがエラーを含むと判別することによって、メモリから読み出されたデータがエラーを含むか否かを判別する、データ処理装置。
【請求項７】
請求項１から６のいずれか一項において、前記コーディングユニットは、第１データセットを受け取り、このデータに生成多項式を乗算し、この乗算の結果を第２データセットとして出力する符号語生成器を備えた、データ処理装置。
【請求項８】
請求項５から７のいずれか一項において、前記コーディングユニットは、前記メモリから読み出されたデータを受け取り、この読み出されたデータに含まれる前記情報データに生成多項式を乗算し、この乗算の結果を、読み出されたデータに含まれる前記パリティデータと比較する符号語生成器を備えた、データ処理装置。
【請求項９】
請求項５から８のいずれか一項において、前記コーディングユニットは、前記メモリから読み出された前記データを受け取り、この読み出されたデータに含まれる前記情報データとパリティデータとを連結し、前記生成多項式の根を前記連結されたデータに代入し、その結果の値を加算するシンドローム生成器を備えた、データ処理装置。
【請求項１０】
請求項９において、前記コーディングユニットは、前記結果の値の総和がゼロでない場合、前記情報データがエラーを含むと判別する、データ処理装置。
【請求項１１】
請求項１０において、前記シンドローム生成器は、前記生成多項式の複数の根を前記連結されたデータにそれぞれ代入し、各代入から得た値を加算するように構成されており、加算の結果は、情報データ内のエラーの場所を表すものである、データ処理装置。
【請求項１２】
請求項１から１１のいずれか一項において、前記コーディングユニットは、メモリから読み出された前記データがエラーを含むと判別すると、その情報データを前記エラー訂正ユニットに出力する、データ処理装置。
【請求項１３】
請求項１から１２のいずれか一項において、前記エラー訂正ユニットは、前記メモリに書き込まれるデータをインターリーブし、前記メモリから読み出されたデータをデインターリーブする、データ処理装置。
【請求項１４】
請求項１から１３のいずれか一項において、前記コーディングユニットは、メモリから読み出される256バイトごとに２つ以上のビットエラーを検出できる、データ処理装置。
【請求項１５】
請求項１から１４のいずれか一項において、前記エラー訂正ユニットは、メモリから読み出される512バイトごとに２つ以上のビットエラーを訂正できる、データ処理装置。
【請求項１６】
請求項の１から１５いずれか一項において、前記エラー訂正アルゴリズムはリードソロモン・コードである、データ処理装置。
【請求項１７】
請求項１から１６のいずれか一項において、前記エラー訂正アルゴリズムはクロスインターリーブ・リードソロモン・コードである、データ処理装置。
【請求項１８】
請求項１から１７のいずれか一項において、前記エラー訂正ユニットはデジタルプロセッサである、データ処理装置。
【請求項１９】
書き換え可能メモリと、
ハードウェアに実装されたコーディングユニットであって、コーディング動作を実行でき、このコーディング動作において、前記メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、前記メモリへの書込み用にこの第２データセットを出力し、さらにエラー検出動作を実行でき、このエラー検出動作では、前記メモリから読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する、コーディングユニットと、
ソフトウェアに実装されたエラー訂正ユニットであって、エラーを含む読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して前記エラーを訂正し、これにより訂正されたデータを生成し、この訂正されたデータを出力する、エラー訂正ユニットとを備えたデータ記憶装置。
【請求項２０】
請求項１９において、前記プロセッサによるデータ読出しとデータ書込みの両方または一方に用いられる前記メモリの少なくとも1つのセクタは、512バイト当たり１ビットよりも大きいエラー率を有する、データ記憶装置。
【請求項２１】
請求項１９または２０において、前記メモリはリサイクルされた集積メモリである、データ記憶装置。
【請求項２２】
請求項１９または２０において、前記メモリは従来の許容できる製造標準を超えるエラー率を有する、データ記憶装置。
【請求項２３】
請求項１９から２２のいずれか一項において、前記メモリはフラッシュメモリである、データ記憶装置。
【請求項２４】
請求項１９から２３のいずれか一項において、前記メモリはＮＡＮＤフラッシュメモリである、データ記憶装置。
【請求項２５】
請求項１９から２４のいずれか一項において、前記メモリは、そのビットが単独でアクセスされないものである、データ記憶装置。
【請求項２６】
書き換え可能メモリに書き込まれるデータおよびこのメモリから読み出されるデータを処理する方法であって、
ハードウェアでコーディング動作を実行する工程であって、このコーディング動作は、前記メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、前記メモリへの書込み用に第２データセットを出力する工程と、
ハードウェアでエラー検出動作を実行する工程であって、このエラー検出動作は、前記メモリから読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する工程と、
ソフトウェアでエラー訂正動作を実行する工程であって、このエラー訂正動作は、エラーを含む読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理してエラーを訂正し、この訂正されたデータを出力する工程とを備えた、データ処理方法。
【請求項２７】
メモリが機能している装置からこのメモリを取り除いて、このメモリを別の装置内に設置する工程を備えた、書き換え可能メモリをリサイクルする方法であって、
前記別の装置はデータ処理装置を有し、このデータ処理装置は、
ハードウェアに実装されたコーディングユニットであって、コーディング動作を実行でき、このコーディング動作において、前記メモリへの書込み対象である第１データセットを受け取り、エラー訂正アルゴリズムに従ってそのデータを処理して第２データセットを生成し、前記メモリへの書込み用にこの第２データセットを出力し、さらにエラー検出動作を実行でき、このエラー検出動作では、前記メモリから読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理して読み出されたデータがエラーを含むか否かを判別する、コーディングユニットと、
ソフトウェアに実装されたエラー訂正ユニットであって、エラーを含む読み出されたデータを受け取り、前記エラー訂正アルゴリズムに従ってそのデータを処理してエラーを訂正し、これにより訂正されたデータを生成し、この訂正されたデータを出力する、エラー訂正ユニットとを備えた、メモリのリサイクル方法。
【国際調査報告】
2009501380.tif 000022
2009501380.tif 000023
2009501380.tif 000024
2009501380.tif 000025