フラッシュファイルシステムの誤り訂正機能
【課題】フラッシュファイルシステムのようなフラッシュメモリにデータを読み書きする場合は誤り訂正手段が不可欠である。しかし、誤り訂正機能を使用するときの演算量は大変多くの時間を消費する。
【解決手段】そこで、誤り訂正を行う前に誤り検出のみ行い、誤りがあった場合だけ適切な誤り訂正を行ったり、フラッシュメモリ上のプログラムやデータの種類により、誤り訂正手段の誤り検出数と誤り訂正数を可変して、誤り訂正の処理時間を短縮した。
【解決手段】そこで、誤り訂正を行う前に誤り検出のみ行い、誤りがあった場合だけ適切な誤り訂正を行ったり、フラッシュメモリ上のプログラムやデータの種類により、誤り訂正手段の誤り検出数と誤り訂正数を可変して、誤り訂正の処理時間を短縮した。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フラッシュファイルシステムの誤り訂正機能であって、誤り検出を行った後、誤り訂正を行ったり、フラッシュメモリ上のプログラムの種類により誤り訂正機能の能力を変えることに関するものである。
【背景技術】
【０００２】
昨今、外部記憶装置の容量は指数関数的に大きくなり、転送時間も大きくなってきた。その為、転送スピードを速くし対応を取ってきた。しかし、転送スピードを上げるとデータの転送誤りが増加し、誤り訂正システムが必要不可欠となってきた。このような背景の元に誤り訂正システムも多くの種類のものが提案され、何bitの誤りを検出でき何bitの誤りを訂正できるか、その為には何bitの誤り訂正ビットを付加するかなど、誤り検出の数、誤り訂正の数により適切な誤り訂正のアルゴリズムが存在する。
【０００３】
NAND型フラッシュメモリを使用するフラッシュファイルシステムにおいて、メモリの容量の増加や読み書き時間の短縮に伴い、誤り訂正は必要不可欠となった。また、昨今、NAND型フラッシュメモリは多値を持つNAND型フラッシュメモリも増加し、データの誤り率も多くなり、誤り訂正手段はさらに重要な要素となった。一方誤り訂正手段はハミング距離が３であるハミングの誤り訂正を使用していたが、誤り検出と誤り訂正の数が増えるとBCH誤り訂正が必要となってきた。BCH誤り訂正は情報ビットと生成多項式により誤り訂正ビットをつくり、情報ビットに付加してフラッシュメモリに書き込み、フラッシュメモリから読み出すときは、読み出した後、シンドロームの計算を行い、誤りの存否を判断し、誤りがある場合は再度計算やルックアップテーブルにより誤りを訂正した。
【０００４】
具体的には図４のように、Ｉ（ｘ）：情報bitをＧ（ｘ）：生成多項式で割り算をして、ｈ（ｘ）：商とＲ（ｘ）：余りを求める。Ｒ（ｘ）：余りが誤り訂正bitとなり、Ｉ（ｘ）：情報bitの後ろにつけて、Ｉ（ｘ）＋Ｒ（ｘ）で誤り訂正付きのデータとなる。この形でフラッシュメモリに書き込み、読み出した後は、α＊４＋α＋１＝０の１つの解をＩ（ｘ）＋Ｒ（ｘ）のｘに代入してＳ（α）なるシンドロームを求める。Ｓ（α）：シンドロームが全て０であれば誤りは無い。しかし、Ｓ（α）が０で無いならば誤りが発生しているので、誤り訂正の計算かルックアップテーブルを用いて誤りを訂正する。
【０００５】
フラッシュファイルシステムの誤り訂正機能に関する文献は無いが、ファイルシステムの誤り訂正に関するものは以下のとおりである。
【特許文献１】特開２０００−０１１６８９
【特許文献２】特開平１１−２７２５６８
【特許文献３】特開平１１−１４３７８７
【特許文献４】特開平１１−２３２７７８
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記で示すように、誤り訂正の処理は生成多項式による計算など多大な時間を消費しシンドロームから誤りを訂正する過程も多大な時間を消費する。即ち、読み書きごとの誤り訂正作業はフラッシュファイルシステムにとっては重い処理であった。つまり、誤り訂正の数と誤り検出の数を多くすることで処理時間が長くなることが課題であった。
【課題を解決するための手段】
【０００７】
そこで、所定の数の誤り検出と誤り訂正が可能な誤り訂正ビットを生成多項式により演算し情報ビットに付加してフラッシュメモリに書き込み、読み出すときは、先ず誤り検出数を最大として誤り検出のみ行い、検出した誤りの数に基づき、再度誤り訂正をしたり、フラッシュメモリ上のプログラムやデータの種類により、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変え、または、フラッシュメモリ上のプログラムやデータの格納場所により、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変え、または、フラッシュメモリ上のプログラムやデータに付加したフラグにより、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変えた。
【発明の効果】
【０００８】
一般に誤り訂正手段の処理時間が多くかかる中で、誤りがあるかないかを先に検出したり、プログラムの重要度に応じて誤り検出機能を下げるなど、誤り訂正処理の時間を短くすることにより、システムは非常に効率的となった。
【実施例１】
【０００９】
最小距離が６以上の誤り訂正機能を持った誤り訂正検出手段を例に挙げると、誤り訂正処理をしない場合は５bitの誤り検出ができる。またシンドロームから１bitの誤り訂正を行う場合は４bitの誤り検出ができる。また、２つのシンドロームから２bitの誤り訂正を行う場合は３bitの誤り検出ができる。この事から、先ず５bitの誤り検出を行い、どれくらいの誤り数があるかを判断した後適正な誤り訂正を行う。これにより先ずは最大数の誤り検出機能で誤り検出の不能を避け、次いで、確定した誤り検出数を得て、適切な誤り訂正を行うことが可能となる。
【実施例２】
【００１０】
図1において、１はフラッシュメモリ空間である。２のブートコード格納領域には例えば誤り3bit訂正、4bit検出をできる誤り訂正機能を付けて格納する。３のＯＳ格納領域には例えば誤り２bit訂正、３bit検出をできる誤り訂正機能を付けて格納する。４のユーザデータ格納領域には例えば誤り１it訂正、２bit検出をできる誤り訂正機能を付けて格納する。
【００１１】
このようなプログラムの種類により誤り訂正機能の能力を変えることにより、もっとも誤り訂正能力の高い誤り訂正機能をブートコードに付けて、その次に誤り訂正能力の高い誤り訂正機能をＯＳに付けて、最後に、最も誤り訂正能力の低い誤り訂正機能をユーザデータに取り付けた。このようにすることにより、誤りがあってはならないものには、たとえ処理時間がかかっても誤り訂正機能の高いものを付加し、そうでないものには、処理時間を優先する方法を取った。
【００１２】
図２において、１はフラッシュメモリ空間である。２のブートコードには例えば誤り3bit訂正、4bit検出をできる誤り訂正機能を付けてフラッシュメモリの先頭ブロックに格納する。フラッシュメモリの先頭ブロックは先天性の不良ブロックがないため連続して格納することが可能となる。３のＯＳには例えば誤り２bit訂正、３bit検出をできる誤り訂正機能を付けて予め決めておいたブロックに格納する。４のユーザデータには例えば誤り１it訂正、２bit検出をできる誤り訂正機能を付けて予め決めておいた格納する。
【００１３】
このように、プログラムの種類を予め決めておいたブロックに格納し、各ブロック毎に誤り訂正機能の能力を変えることにより、もっとも誤り訂正能力の高い誤り訂正機能をブートコードが格納されているブロックに割り付けて、その次に誤り訂正能力の高い誤り訂正機能をＯＳが格納されているブロックに割り付けて、最後に、最も誤り訂正能力の低い誤り訂正機能をユーザデータが格納されているブロックに割り付けた。このようにすることにより、誤りがあってはならないものには、たとえ処理時間がかかっても誤り訂正機能の高いものを付加し特定のブロックに割付し、そうでないものには、処理時間を優先するために特定のブロックに割り付けた。よってブロックの種類により、プログラムの種類が特定でき、自由な誤り訂正能力を有する誤り訂正機能を付けることができる。
【００１４】
図３において、１はフラッシュメモリ空間である。２のブートコードには例えば誤り3bit訂正、4bit検出をできる誤り訂正機能を付けて、またブートコードであることがわかるフラグ１をつけてフラッシュメモリに格納する。３のＯＳには例えば誤り２bit訂正、３bit検出をできる誤り訂正機能を付けて、またＯＳであることがわかるフラグ２を付けてフラッシュメモリに格納する。４のユーザデータには例えば誤り１it訂正、２bit検出をできる誤り訂正機能を付けて、またユーザデータであることがわかるフラグ３を付けてフラッシュメモリに格納する。
【００１５】
このように、プログラムの種類を予め決めておいたフラグで認識できるようにし、各プログラムの種類毎に誤り訂正機能の能力を変えることにより、もっとも誤り訂正能力の高い誤り訂正機能をブートコードに付けフラグ１とともにフラッシュメモリに格納し、その次に誤り訂正能力の高い誤り訂正機能をＯＳに付け、フラグ２とともにフラッシュメモリに格納し、最後に、最も誤り訂正能力の低い誤り訂正機能をユーザデータに付け、フラグ３とともにフラッシュメモリに格納する。このようにすることにより、誤りがあってはならないものには、たとえ処理時間がかかっても誤り訂正機能の高い誤り訂正を付加し、その存在をフラグで認識する。また、そうでないものには、処理時間を優先する方法を取るために特定のフラグをつけることによりプログラムの種類が特定でき、自由な誤り訂正能力を有する誤り訂正機能を付けることができる。
【産業上の利用可能性】
【００１６】
一般に誤り訂正手段の処理時間が多くかかる中で、誤りがあるかないかを先に検出したり、プログラムの重要度に応じて誤り検出機能を下げるなど、誤り訂正処理の時間を短くすることにより、フラッシュファイルシステムの産業上の利用可能性は非常に高くなった。
【図面の簡単な説明】
【００１７】
【図１】フラッシュメモリ空間上の、ブートコード、ＯＳ、ユーザデータの配置の構成図である。
【図２】フラッシュメモリ空間上の、ブートコード、ＯＳ、ユーザデータの配置の構成図である。
【図３】フラッシュメモリ空間上の、ブートコード、ＯＳ、ユーザデータの配置の構成図である。
【図４】誤り訂正機能の誤り訂正bitの作り方と、読み出し後の誤り検出、訂正の方法についての図である。
【符号の説明】
【００１８】
１ フラッシュメモリ空間
２ ブートコード格納領域
３ ＯＳ格納領域
４ ユーザデータ格納領域
５ ブートコード
６ ＯＳ
７ ユーザデータ
【技術分野】
【０００１】
本発明は、フラッシュファイルシステムの誤り訂正機能であって、誤り検出を行った後、誤り訂正を行ったり、フラッシュメモリ上のプログラムの種類により誤り訂正機能の能力を変えることに関するものである。
【背景技術】
【０００２】
昨今、外部記憶装置の容量は指数関数的に大きくなり、転送時間も大きくなってきた。その為、転送スピードを速くし対応を取ってきた。しかし、転送スピードを上げるとデータの転送誤りが増加し、誤り訂正システムが必要不可欠となってきた。このような背景の元に誤り訂正システムも多くの種類のものが提案され、何bitの誤りを検出でき何bitの誤りを訂正できるか、その為には何bitの誤り訂正ビットを付加するかなど、誤り検出の数、誤り訂正の数により適切な誤り訂正のアルゴリズムが存在する。
【０００３】
NAND型フラッシュメモリを使用するフラッシュファイルシステムにおいて、メモリの容量の増加や読み書き時間の短縮に伴い、誤り訂正は必要不可欠となった。また、昨今、NAND型フラッシュメモリは多値を持つNAND型フラッシュメモリも増加し、データの誤り率も多くなり、誤り訂正手段はさらに重要な要素となった。一方誤り訂正手段はハミング距離が３であるハミングの誤り訂正を使用していたが、誤り検出と誤り訂正の数が増えるとBCH誤り訂正が必要となってきた。BCH誤り訂正は情報ビットと生成多項式により誤り訂正ビットをつくり、情報ビットに付加してフラッシュメモリに書き込み、フラッシュメモリから読み出すときは、読み出した後、シンドロームの計算を行い、誤りの存否を判断し、誤りがある場合は再度計算やルックアップテーブルにより誤りを訂正した。
【０００４】
具体的には図４のように、Ｉ（ｘ）：情報bitをＧ（ｘ）：生成多項式で割り算をして、ｈ（ｘ）：商とＲ（ｘ）：余りを求める。Ｒ（ｘ）：余りが誤り訂正bitとなり、Ｉ（ｘ）：情報bitの後ろにつけて、Ｉ（ｘ）＋Ｒ（ｘ）で誤り訂正付きのデータとなる。この形でフラッシュメモリに書き込み、読み出した後は、α＊４＋α＋１＝０の１つの解をＩ（ｘ）＋Ｒ（ｘ）のｘに代入してＳ（α）なるシンドロームを求める。Ｓ（α）：シンドロームが全て０であれば誤りは無い。しかし、Ｓ（α）が０で無いならば誤りが発生しているので、誤り訂正の計算かルックアップテーブルを用いて誤りを訂正する。
【０００５】
フラッシュファイルシステムの誤り訂正機能に関する文献は無いが、ファイルシステムの誤り訂正に関するものは以下のとおりである。
【特許文献１】特開２０００−０１１６８９
【特許文献２】特開平１１−２７２５６８
【特許文献３】特開平１１−１４３７８７
【特許文献４】特開平１１−２３２７７８
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記で示すように、誤り訂正の処理は生成多項式による計算など多大な時間を消費しシンドロームから誤りを訂正する過程も多大な時間を消費する。即ち、読み書きごとの誤り訂正作業はフラッシュファイルシステムにとっては重い処理であった。つまり、誤り訂正の数と誤り検出の数を多くすることで処理時間が長くなることが課題であった。
【課題を解決するための手段】
【０００７】
そこで、所定の数の誤り検出と誤り訂正が可能な誤り訂正ビットを生成多項式により演算し情報ビットに付加してフラッシュメモリに書き込み、読み出すときは、先ず誤り検出数を最大として誤り検出のみ行い、検出した誤りの数に基づき、再度誤り訂正をしたり、フラッシュメモリ上のプログラムやデータの種類により、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変え、または、フラッシュメモリ上のプログラムやデータの格納場所により、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変え、または、フラッシュメモリ上のプログラムやデータに付加したフラグにより、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変えた。
【発明の効果】
【０００８】
一般に誤り訂正手段の処理時間が多くかかる中で、誤りがあるかないかを先に検出したり、プログラムの重要度に応じて誤り検出機能を下げるなど、誤り訂正処理の時間を短くすることにより、システムは非常に効率的となった。
【実施例１】
【０００９】
最小距離が６以上の誤り訂正機能を持った誤り訂正検出手段を例に挙げると、誤り訂正処理をしない場合は５bitの誤り検出ができる。またシンドロームから１bitの誤り訂正を行う場合は４bitの誤り検出ができる。また、２つのシンドロームから２bitの誤り訂正を行う場合は３bitの誤り検出ができる。この事から、先ず５bitの誤り検出を行い、どれくらいの誤り数があるかを判断した後適正な誤り訂正を行う。これにより先ずは最大数の誤り検出機能で誤り検出の不能を避け、次いで、確定した誤り検出数を得て、適切な誤り訂正を行うことが可能となる。
【実施例２】
【００１０】
図1において、１はフラッシュメモリ空間である。２のブートコード格納領域には例えば誤り3bit訂正、4bit検出をできる誤り訂正機能を付けて格納する。３のＯＳ格納領域には例えば誤り２bit訂正、３bit検出をできる誤り訂正機能を付けて格納する。４のユーザデータ格納領域には例えば誤り１it訂正、２bit検出をできる誤り訂正機能を付けて格納する。
【００１１】
このようなプログラムの種類により誤り訂正機能の能力を変えることにより、もっとも誤り訂正能力の高い誤り訂正機能をブートコードに付けて、その次に誤り訂正能力の高い誤り訂正機能をＯＳに付けて、最後に、最も誤り訂正能力の低い誤り訂正機能をユーザデータに取り付けた。このようにすることにより、誤りがあってはならないものには、たとえ処理時間がかかっても誤り訂正機能の高いものを付加し、そうでないものには、処理時間を優先する方法を取った。
【００１２】
図２において、１はフラッシュメモリ空間である。２のブートコードには例えば誤り3bit訂正、4bit検出をできる誤り訂正機能を付けてフラッシュメモリの先頭ブロックに格納する。フラッシュメモリの先頭ブロックは先天性の不良ブロックがないため連続して格納することが可能となる。３のＯＳには例えば誤り２bit訂正、３bit検出をできる誤り訂正機能を付けて予め決めておいたブロックに格納する。４のユーザデータには例えば誤り１it訂正、２bit検出をできる誤り訂正機能を付けて予め決めておいた格納する。
【００１３】
このように、プログラムの種類を予め決めておいたブロックに格納し、各ブロック毎に誤り訂正機能の能力を変えることにより、もっとも誤り訂正能力の高い誤り訂正機能をブートコードが格納されているブロックに割り付けて、その次に誤り訂正能力の高い誤り訂正機能をＯＳが格納されているブロックに割り付けて、最後に、最も誤り訂正能力の低い誤り訂正機能をユーザデータが格納されているブロックに割り付けた。このようにすることにより、誤りがあってはならないものには、たとえ処理時間がかかっても誤り訂正機能の高いものを付加し特定のブロックに割付し、そうでないものには、処理時間を優先するために特定のブロックに割り付けた。よってブロックの種類により、プログラムの種類が特定でき、自由な誤り訂正能力を有する誤り訂正機能を付けることができる。
【００１４】
図３において、１はフラッシュメモリ空間である。２のブートコードには例えば誤り3bit訂正、4bit検出をできる誤り訂正機能を付けて、またブートコードであることがわかるフラグ１をつけてフラッシュメモリに格納する。３のＯＳには例えば誤り２bit訂正、３bit検出をできる誤り訂正機能を付けて、またＯＳであることがわかるフラグ２を付けてフラッシュメモリに格納する。４のユーザデータには例えば誤り１it訂正、２bit検出をできる誤り訂正機能を付けて、またユーザデータであることがわかるフラグ３を付けてフラッシュメモリに格納する。
【００１５】
このように、プログラムの種類を予め決めておいたフラグで認識できるようにし、各プログラムの種類毎に誤り訂正機能の能力を変えることにより、もっとも誤り訂正能力の高い誤り訂正機能をブートコードに付けフラグ１とともにフラッシュメモリに格納し、その次に誤り訂正能力の高い誤り訂正機能をＯＳに付け、フラグ２とともにフラッシュメモリに格納し、最後に、最も誤り訂正能力の低い誤り訂正機能をユーザデータに付け、フラグ３とともにフラッシュメモリに格納する。このようにすることにより、誤りがあってはならないものには、たとえ処理時間がかかっても誤り訂正機能の高い誤り訂正を付加し、その存在をフラグで認識する。また、そうでないものには、処理時間を優先する方法を取るために特定のフラグをつけることによりプログラムの種類が特定でき、自由な誤り訂正能力を有する誤り訂正機能を付けることができる。
【産業上の利用可能性】
【００１６】
一般に誤り訂正手段の処理時間が多くかかる中で、誤りがあるかないかを先に検出したり、プログラムの重要度に応じて誤り検出機能を下げるなど、誤り訂正処理の時間を短くすることにより、フラッシュファイルシステムの産業上の利用可能性は非常に高くなった。
【図面の簡単な説明】
【００１７】
【図１】フラッシュメモリ空間上の、ブートコード、ＯＳ、ユーザデータの配置の構成図である。
【図２】フラッシュメモリ空間上の、ブートコード、ＯＳ、ユーザデータの配置の構成図である。
【図３】フラッシュメモリ空間上の、ブートコード、ＯＳ、ユーザデータの配置の構成図である。
【図４】誤り訂正機能の誤り訂正bitの作り方と、読み出し後の誤り検出、訂正の方法についての図である。
【符号の説明】
【００１８】
１ フラッシュメモリ空間
２ ブートコード格納領域
３ ＯＳ格納領域
４ ユーザデータ格納領域
５ ブートコード
６ ＯＳ
７ ユーザデータ
【特許請求の範囲】
【請求項１】
所定の数の誤り検出と誤り訂正が可能な誤り訂正ビットを生成多項式により演算し情報ビットに付加してフラッシュメモリに書き込み、読み出すときは、先ず誤り検出数を最大として誤り検出のみ行い、検出した誤りの数に基づき、再度誤り訂正をすることを特徴とするフラッシュファイルシステム。
【請求項２】
NAND型フラッシュメモリをもつフラッシュファイルシステムにおいて、当該フラッシュメモリ上のプログラムやデータの種類により、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変えることを特徴としたフラッシュファイルシステム。
【請求項３】
NAND型フラッシュメモリをもつフラッシュファイルシステムにおいて、当該フラッシュメモリ上のプログラムやデータの格納場所により、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変えることを特徴としたフラッシュファイルシステム。
【請求項４】
NAND型フラッシュメモリをもつフラッシュファイルシステムにおいて、当該フラッシュメモリ上のプログラムやデータに付加したフラグにより、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変えることを特徴としたフラッシュファイルシステム。
【請求項１】
所定の数の誤り検出と誤り訂正が可能な誤り訂正ビットを生成多項式により演算し情報ビットに付加してフラッシュメモリに書き込み、読み出すときは、先ず誤り検出数を最大として誤り検出のみ行い、検出した誤りの数に基づき、再度誤り訂正をすることを特徴とするフラッシュファイルシステム。
【請求項２】
NAND型フラッシュメモリをもつフラッシュファイルシステムにおいて、当該フラッシュメモリ上のプログラムやデータの種類により、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変えることを特徴としたフラッシュファイルシステム。
【請求項３】
NAND型フラッシュメモリをもつフラッシュファイルシステムにおいて、当該フラッシュメモリ上のプログラムやデータの格納場所により、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変えることを特徴としたフラッシュファイルシステム。
【請求項４】
NAND型フラッシュメモリをもつフラッシュファイルシステムにおいて、当該フラッシュメモリ上のプログラムやデータに付加したフラグにより、当該フラッシュメモリ上のプログラムやデータを読み書きする誤り訂正手段の誤り検出数と誤り訂正数を変えることを特徴としたフラッシュファイルシステム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１０−９２５７４（Ｐ２０１０−９２５７４Ａ）
【公開日】平成２２年４月２２日（２０１０．４．２２）
【国際特許分類】
【出願番号】特願２００８−２６４７０１（Ｐ２００８−２６４７０１）
【出願日】平成２０年１０月１２日（２００８．１０．１２）
【出願人】（３０２００４８５０）株式会社京都ソフトウェアリサーチ (7)
【Ｆターム（参考）】
【公開日】平成２２年４月２２日（２０１０．４．２２）
【国際特許分類】
【出願日】平成２０年１０月１２日（２００８．１０．１２）
【出願人】（３０２００４８５０）株式会社京都ソフトウェアリサーチ (7)
【Ｆターム（参考）】
[ Back to top ]