(57)【特許請求の範囲】
【請求項１】
データを格納する論理アドレスを物理アドレスに変換するための（ｎ＋１）個の変換テーブル（ｎは２以上の任意の整数）のうち、第０の変換テーブルを記憶する揮発性メモリと、
前記（ｎ＋１）個の変換テーブルのうち、第１の変換テーブルから第ｎの変換テーブルまでを記憶し、複数のデータ記憶領域と冗長領域との組を有し、前記データ記憶領域と冗長領域との組毎に物理アドレスが割り付けられる書き換え可能な不揮発性メモリと、を有し、
前記第０の変換テーブルは、所定のビットで表現可能な複数の論理アドレス範囲に基づいて、前記論理アドレスを第１の変換テーブルを格納する第１の物理アドレスに変換し、
第ｉの変換テーブル（ｉは、１≦ｉ≦ｎ−１を満たす任意の整数）は、前記第０の変換テーブルから第（ｉ−１）の変換テーブルまでに対応するビットが前記論理アドレスで与えられる論理アドレスの範囲内において第ｉの変換テーブルに対応するビットで表現可能な複数の論理アドレス範囲に基づいて、前記論理アドレスを第（ｉ＋１）の変換テーブルを格納する第（ｉ＋１）の物理アドレスに変換し、
第ｎの変換テーブルは、第０の変換テーブルから第（ｎ−１）の変換テーブルまでに対応するビットが前記論理アドレスで与えられる論理アドレス範囲内において第ｎの変換テーブルに対応するビットに基づいて、前記論理アドレスをデータが格納される前記物理アドレスに変換し、
前記不揮発性メモリのデータを書き換える場合は、前記論理アドレスに対応する前記物理アドレスを変更して何も記録されていない物理アドレスを選んでデータを書き、
書き換えるデータを格納する前記データ記憶領域と組をなし同じ物理アドレスを有する前記不揮発性メモリの前記冗長領域に前記第１〜第ｎの変換テーブルが記憶される
ことを特徴とする記憶装置。
【請求項２】
前記データの記憶領域と冗長領域との組毎に割り付けられる前記物理アドレスは、前記不揮発性メモリのデータの消去単位を単位として割り付けられることを特徴とする請求項１に記載の記憶装置。
【請求項３】
前記不揮発性メモリがnの値を記憶することを特徴とする請求項１に記載の記憶装置。
【請求項４】
前記第０の変換テーブルの前記所定のビットは、前記論理アドレスの最上位ビットを含むことを特徴とした請求項１に記載の記憶装置。
【請求項５】
前記第１の変換テーブルから前記第ｎの変換テーブルまでに対応する前記ビットは、前記論理アドレスの前記第０の変換テーブルの前記所定のビットより下位のビットに基づいて上位ビットから順に対応づけられた物理アドレスを有することを特徴とした請求項４に記載の記憶装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、書き換え可能な不揮発性メモリを有する記憶装置に関する。
【０００２】
【従来の技術】
近年、書き換え可能な不揮発性メモリ（例えばフラッシュメモリ）を用いた記憶装置（例えばメモリカード）が市場で広く使用されるようになってきている。半導体技術の進歩に伴い、不揮発性メモリの記憶容量は大きくなってきている。例えばフラッシュメモリを有するメモリカードであるＳＤカードの記憶容量は、発売当初は８ＭＢであったが、現在は５１２ＭＢのＳＤカードが発売されており、今後も記憶容量は増加していく見込みである。
【０００３】
ホスト（例えばＳＤカードスロットを有する携帯情報端末）は、記憶装置（例えば不揮発性メモリを有するＳＤカード）にデータを書込み、データを読み出す。フラッシュメモリ等の書き換え可能な不揮発性メモリにおいては、一定の領域を一括消去した後そこに新たなデータを書き込む。そのため、例えば記録されているデータを書き換えると、そのデータが記録されているアドレスは、書き換えの前後で異なる。データが実際に記録されているアドレス（物理アドレス）をホストが直接管理することは極めて煩雑であるため、ホストと記憶装置との通信においては論理アドレスを用いることが一般的である。ホストは、実際にデータが書き込まれているアドレス（物理アドレス）を管理することなく、一定の論理アドレスに基づいてデータを記憶装置に書き込み又は読み出すことが出来る。記憶装置が実際にデータが書き込まれる物理アドレスを管理する。記憶装置は、内部で論理アドレスを物理アドレスに変換し（論理アドレス／物理アドレス変換テーブル（以下、「変換テーブル」と略す。）を用いる。）、物理アドレスにデータを記録し、物理アドレスからデータを再生する。
【０００４】
しかし、ＳＤカードの記憶容量の増大に伴い、変換テーブルも大きくなる。記憶装置は一般に、不揮発性メモリから読み出した変換テーブルをＲＡＭ（Random Access Memory）に書き込み、この変換テーブルを参照しながら不揮発性メモリにデータを書き込み又は読み出す。変換テーブルが大きくなりすぎると、変換テーブル全体をＲＡＭに格納するために、ＲＡＭ容量が増え、メモリカードのコストがアップする。
【０００５】
特開２００１−１４２７７４号公報には、それぞれがＲＡＭに格納可能な大きさを有する複数の変換テーブルと、それらの変換テーブルの不揮発性メモリ内の格納場所を記憶するポインターテーブルとを有する従来例のメモリカードが記載されている。
図６は、上記の従来例のメモリカードの構成を示す。図６において、６１１はホストインターフェース、６１２は制御部、６１３はＲＯＭ（Read Only Memory）、６１４はＲＡＭ、６１５はフラッシュメモリである。フラッシュメモリ６１５は、管理情報記録領域６５３とユーザ領域６５４とを有する。
【０００６】
従来例のメモリカードにおいて、フラッシュメモリは複数のブロックを有する。データの一括消去はブロックを最小単位として行われる（ブロック内の全データを１にする。）。１ブロックは３２セクタからなる。データの書き込み又は読み出しは、セクタを最小単位として行われる。各セクタは、データ記憶領域と冗長領域とを有する。データ記録領域にはデータを記録し、冗長領域にはデータの属性情報等を記録する。
【０００７】
従来例の変換テーブルは、ブロックを単位として論理アドレスを物理アドレスに変換する。ブロックの論理アドレス及び物理アドレスはそれぞれ２Ｂのサイズを有する。
管理情報記録領域６５３には、ポインターテーブル６５１（ＬＴＰａ）と、複数の変換テーブル６５２−０〜６５２−３（ＬＴＰｂ（＃０）〜ＬＴＰｂ（＃３））とが記録されている。ユーザ領域には、データが記録されている。ＲＡＭ６１４のＬＴＰａ領域６４１にはポインターテーブル６５１（ＬＴＰａ）が格納されている。ＲＡＭ６１４のＬＴＰｂ領域６４２には、いずれか１つの変換テーブル（図６ではＬＴＰｂ（＃１））が格納されている。
【０００８】
ホストからデータの読み出し命令が来ると、制御部６１２は、もしＲＡＭ６１４に格納された変換テーブル（図６ではＬＴＰｂ（＃１））が読み出しアドレス（論理アドレス）を含んでいれば、その変換テーブルを用いてその論理アドレスを物理アドレスに変換して、データを読み出す。制御部６１２は、もしＲＡＭ６１４に格納された変換テーブルＬＴＰｂ（＃１）が読み出しアドレス（論理アドレス）を含んでいなければ、読み出しアドレス（論理アドレス）を含む変換テーブル（例えばＬＴＰｂ（＃３）。その記録アドレスはポインターテーブル６５１（ＬＴＰａ）に記載されている。）をフラッシュメモリ６１５から読み出してＲＡＭ６１４に格納し、その変換テーブルを用いてその論理アドレスを物理アドレスに変換して、データを読み出す。
【０００９】
ホストからデータの書き換え命令が来ると、制御部６１２は、フラッシュメモリ上の空き領域を確保し、そこにデータを書き込み、且つ１つの空き領域に新たな変換テーブル（例えばＬＴＰｂ（＃１））を書込む。ポインターテーブル６５１（ＬＴＰａ）も書き換える。
【００１０】
【特許文献１】
特開２００１−１４２７７４号公報
【００１１】
【発明が解決しようとする課題】
しかし、従来例のメモリーカードにおいては、フラッシュメモリの記録容量の大きさに比例して、変換テーブルを記録するための大きな管理情報記録領域を確保する必要があった。
従来のメモリーカードにおいては、データの記録領域と変換テーブルの記録領域とが全く別個の領域であった故に、データの読み出し動作と別個に、変換テーブルの読み出し動作をする必要があった。
従来のメモリーカードにおいては、データの書き換えを行う毎に、大きな変換テーブル（例えばＬＴＰｂ（＃１））と、ポインターテーブル６５１（ＬＴＰａ）とを書き換える必要があった。
【００１２】
本発明は、変換テーブルのための専用記録領域をわずかしか必要としない書き換え可能な不揮発性メモリを有する記憶装置を提供することを目的とする。
本発明は、データの読み出しの際、同時に変換テーブルを読み出すことが出来る書き換え可能な不揮発性メモリを有する記憶装置を提供することを目的とする。
本発明は、データの書き換えを行ったアドレスによっては、少数の小さな変換テーブルを書き換えるだけで済む書き換え可能な不揮発性メモリを有する記憶装置を提供することを目的とする。
【００１３】
【課題を解決するための手段】
上記課題を解決するため、本発明は下記の構成を有する。
本発明の請求項１に記載の発明は、データを格納する論理アドレスを物理アドレスに変換するための（ｎ＋１）個の変換テーブル（ｎは２以上の任意の整数）のうち、第０の変換テーブルを記憶する揮発性メモリと、前記（ｎ＋１）個の変換テーブルのうち、第１の変換テーブルから第ｎの変換テーブルまでを記憶し、複数のデータ記憶領域と冗長領域との組を有し、前記データ記憶領域と冗長領域との組毎に物理アドレスが割り付けられる書き換え可能な不揮発性メモリと、を有し、前記第０の変換テーブルは、所定のビットで表現可能な複数の論理アドレス範囲に基づいて、前記論理アドレスを第１の変換テーブルを格納する第１の物理アドレスに変換し、第ｉの変換テーブル（ｉは、１≦ｉ≦ｎ−１を満たす任意の整数）は、前記第０の変換テーブルから第（ｉ−１）の変換テーブルまでに対応するビットが前記論理アドレスで与えられる論理アドレスの範囲内において第ｉの変換テーブルに対応するビットで表現可能な複数の論理アドレス範囲に基づいて、前記論理アドレスを第（ｉ＋１）の変換テーブルを格納する第（ｉ＋１）の物理アドレスに変換し、第ｎの変換テーブルは、第０の変換テーブルから第（ｎ−１）の変換テーブルまでに対応するビットが前記論理アドレスで与えられる論理アドレス範囲内において第ｎの変換テーブルに対応するビットに基づいて、前記論理アドレスをデータが格納される前記物理アドレスに変換し、前記不揮発性メモリのデータを書き換える場合は、前記論理アドレスに対応する前記物理アドレスを変更して何も記録されていない物理アドレスを選んでデータを書き、書き換えるデータを格納する前記データ記憶領域と組をなし同じ物理アドレスを有する前記不揮発性メモリの前記冗長領域に前記第１〜第ｎの変換テーブルが記憶されることを特徴とする記憶装置。
【００１４】
本発明の請求項２に記載の発明は、前記データの記憶領域と冗長領域との組毎に割り付けられる前記物理アドレスは、前記不揮発性メモリのデータの消去単位を単位として割り付けられることを特徴とする請求項１に記載の記憶装置。である。好ましくはｎは３以上の任意の整数である。
【００１５】
本発明の請求項３に記載の発明は、前記不揮発性メモリがｎの値を記憶することを特徴とする請求項１に記載の記憶装置である。
【００１６】
本発明の請求項４に記載の発明は、前記第０の変換テーブルの前記所定のビットは、前記論理アドレスの最上位ビットを含むことを特徴とした請求項１に記載の記憶装置である。
【００１７】
本発明の請求項５に記載の発明は、前記第１の変換テーブルから前記第ｎの変換テーブルまでに対応する前記ビットは、前記論理アドレスの前記第０の変換テーブルの前記所定のビットより下位のビットに基づいて上位ビットから順に対応づけられた物理アドレスを有することを特徴とした請求項４に記載の記憶装置である。
【００１９】
本発明は、変換テーブルのための専用記録領域をわずかしか必要としない書き換え可能な不揮発性メモリを有する記憶装置を実現出来るという作用を有する。
本発明は、データの読み出しの際、同時に変換テーブルを読み出すことが出来る書き換え可能な不揮発性メモリを有する記憶装置を実現出来るという作用を有する。
本発明は、データの書き換えを行った場合、論理アドレスに関連する少数の小さな変換テーブルを書き換えるだけで良い、書き換え可能な不揮発性メモリを有する記憶装置を実現出来るという作用を有する。
【００２０】
【発明の実施の形態】
以下本発明の実施をするための最良の形態を具体的に示した実施例について図面とともに記載する。
【００２１】
《実施例１》
図１〜４を用いて、本発明の実施例１の記憶装置について説明する。実施例１の記憶装置は、メモリカードである。
実施例１のメモリカードは、書き換え可能な不揮発性メモリであるフラッシュメモリを有する。実施例１のメモリカードは、従来例と異なる変換テーブルを有する。これ以外の点において、実施例１のメモリカードは従来例（図６）と基本的に同一である。
実施例のメモリカードにおいて、フラッシュメモリは複数のブロックを有する。データの一括消去はブロックを最小単位として行われる（ブロック内の全データを１にする。）。１ブロックは３２セクタからなる。データの書き込み又は読み出しは、セクタを最小単位として行われる。各セクタは、データ記憶領域と冗長領域とを有する。データ記録領域にはデータを記録し、冗長領域にはデータの属性情報等を記録する。
一般にデータ記録領域には空き領域を作ることなくデータを記録する。冗長領域には限られた情報しか記録せず、実質的に未記録の領域が残っている。
【００２２】
上述の様に、ホストと記憶装置との間の通信においては、論理アドレスを用いてデータを送受信する。記憶装置は、変換テーブルを用いて論理アドレスを物理アドレスに変換し、物理アドレスにデータを記録し、物理アドレスからデータを再生する。
実施例１においては、ブロックの冗長領域にツリー構造を有する変換テーブルを記録する。
１ブロックは１６ｋＢの大きさを有している。１ＧＢのフラッシュメモリは、６５５３６個（＝１Ｇ／１６ｋ）のブロックを有する。ブロックの物理アドレスのサイズは２Ｂであるから、従来例であれば、不揮発性メモリの管理情報記録領域１３１に１２８ｋＢ（＝２Ｂ×６５５３６）の変換テーブル記録領域を確保する必要があった。
【００２３】
実施例１の記憶装置において、ＳＤカードの初期化時に制御部１１１はＲＡＭ１２２に論理／物理ブロックアドレス変換テーブルの起点となる第０の変換テーブル１４１（例えば３２Ｂ（＝（２Ｂ／１論理ブロックアドレス）×１６論理ブロックアドレス情報）を生成する。
不揮発性メモリ１１２のユーザ領域１３２の物理ブロックの冗長領域に、第１の変換テーブル１５１と、その第１の変換テーブル１５１が有効であるか否かを示す第１の変換テーブル有効フラグと、が格納されている。第１の変換テーブル有効フラグの値“１”は第１の変換テーブル１５１が有効であることを示し、値“０”が第１の変換テーブル１５１が無効であることを示す。
制御部１１１は、不揮発性メモリ１１２から第１の変換テーブル有効フラグと、第１の変換テーブル１５１と、を読み出し、第０の変換テーブル１４１を生成する。
制御部１１１は第１の変換テーブル有効フラグが有効である物理ブロックの冗長領域に登録されている第１の変換テーブル１５１の先頭の論理アドレスを読み出し、その論理アドレスと、第１の変換テーブル１５１が格納されている物理ブロックの物理アドレスとを対応づけて、ＲＡＭ１２２の第０の変換テーブル１４１に登録する。この基本動作を全物理ブロックアドレスについて処理することで、第０の変換テーブル１４１が生成される。
【００２４】
図１は、実施例１のメモリカードの構成を示す図である。図１において、１０１はホスト、１０２は実施例１のメモリカードである。メモリカード１０２は、制御部１１１及び不揮発性メモリ１１２を有する。制御部１１１は、外部インターフェース部１２１及びＲＡＭ１２２を有する。不揮発性メモリ１１２は、管理情報記録領域１３１、ユーザ領域１３２を有する。管理情報記録領域１３１には階層情報ｎ（＝３）１５５が記録されており、ユーザ領域１３２には第１〜第３の変換テーブル１５１〜１５３が記録されている。
実施例１において、ホスト１０１はメモリカードの挿入スロットを有する携帯情報端末である。制御部１１１の外部インターフェース部１２１はホスト１０１との間で通信を行う。インターフェース部１２１は、ホスト１０１からのコマンド（例えばデータ読み出しコマンド、データ書き込みコマンド等）及びデータを受信し、ホスト１０１にレスポンス及びデータを送信する。
【００２５】
実施例１のメモリカードは、第１の変換テーブルから第ｎの変換テーブルまでのｎ階層（ｎは２以上の任意の整数である。実施例１においてはｎ＝３）のツリー構造の変換テーブルを有する。
制御部１１１は、ＲＡＭ１２２に格納された変換テーブルを利用して、不揮発性メモリにデータを書き込み、又はデータを読み出す。
電源起動時、制御部１１１は、不揮発性メモリ１１２から３２Ｂ（＝２Ｂ×１６）の大きさを有する第１の変換テーブル１５１（１６対の論理アドレス及び物理アドレスを有する。各アドレスは２Ｂである。）が有効な物理ブロックをサーチし、論理アドレスと物理アドレスとを対応付けてＲＡＭ１２２に格納する（第０の変換テーブル１４１）。
【００２６】
制御部１１１は、第０の変換テーブル１４１に基づいて第１〜第３の変換テーブルのいずれか１つ又は複数の変換テーブル（第ｉの変換テーブル）を読み出し、ＲＡＭ１２２に格納する（第ｉの変換テーブル１４２）。制御部１１１は、第ｉの変換テーブル（１≦ｉ≦ｎ）に基づいて第（ｉ＋１）の変換テーブルを読み出すことが出来る。これを繰り返すことにより任意の変換テーブルを読み出すことが出来る。
制御部１１１は、ＲＡＭ１２２に格納された変換テーブルを用いて、任意の論理アドレスに対応づけられた不揮発性メモリ１１２の物理アドレスにデータを書き込み、物理アドレスからデータを読み出すことが出来る。
【００２７】
図２は、本発明の実施例１のメモリカードにおける、論理アドレスを物理アドレスに変換する変換テーブルの構造の詳細を説明する図である。上述の様に、実施例１のメモリカードの変換テーブルは、第１の変換テーブルから第ｎの変換テーブルまでのｎ階層（ｎは２以上の任意の整数。実施例１においてはｎ＝３）のツリー構造を有する。
第０の変換テーブル１４１に含まれる１６対の論理アドレス及び物理アドレスは、ユーザ領域にある１６個のブロックを指定する。明細書及び図面において、論理アドレス及び物理アドレスは１６進数で表示されている。それらのブロックの冗長領域には、第１の変換テーブル１５１−１〜１５１−１６（合計１６個の第１の変換テーブル１５１）が記録されている。
【００２８】
実施例１の第０の変換テーブル１４１は、一定間隔で、全アドレス空間に均等に位置する論理アドレスを有する。実施例１のメモリの全ブロックアドレス空間は００００Ｈ〜ＦＦＦＦＨであり、第０の変換テーブルは、ｊ０００Ｈ（ｊは０≦ｊ≦Ｆの任意の整数）の論理アドレスに対応づけられた物理アドレスを有する。例えば第０の変換テーブル１４１において、論理アドレス００００Ｈは物理アドレス５３ＡＣＨに対応付けられている。
ｊ０００Ｈの論理アドレスに対応付けられた物理アドレス、その物理アドレスに記録された第２の変換テーブル、及び第２の変換テーブルにツリー構造で繋がる第３の変換テーブルの全体は、ｊ０００Ｈ〜ｊＦＦＦＨの範囲の論理アドレスに対応付けられた物理アドレスを指定する。
【００２９】
物理アドレス５３ＡＣＨのブロックの冗長領域には、第１の変換テーブル１５１−１が記録されている。
第１の変換テーブル１５１−１に含まれる１６対の論理アドレス及び物理アドレスは、ユーザ領域にある１６個のブロックアドレスを指定する。実施例１の変換テーブル１５１−１は、ほぼ一定間隔で、００００Ｈ〜０ＦＦＦＨのアドレス空間に均等に位置する論理アドレスを有する。実施例１の第１の変換テーブル１５１−１は、００００Ｈ及び０ｊ００Ｈ（ｊは０≦ｊ≦Ｆの任意の整数）の論理アドレスに対応づけられた物理アドレスを有する。例えば第１の変換テーブル１５１−１において、論理アドレス００００Ｈ〜００ＦＦＨを示す物理アドレスは６４１０Ｈに対応付けられている。
【００３０】
物理アドレス６４１０Ｈのブロックの冗長領域には、第２の変換テーブル１５２−１が記録されている。
第２の変換テーブル１５２−１に含まれる１６対の論理アドレス及び物理アドレスは、ユーザ領域にある１６個のブロックを指定する。実施例１の第２の変換テーブル１５２−１は、ほぼ一定間隔で、００００〜００ＦＦＨのアドレス空間に均等に位置する論理アドレスを有する。実施例１の第２の変換テーブル１５２−１は、００００Ｈ及び００ｊ０Ｈ（ｊは０≦ｊ≦Ｆの任意の整数）の論理アドレスに対応づけられた物理アドレスを有する。例えば第２の変換テーブル１５２−１において、論理アドレス００１０Ｈ〜００１ＦＨは物理アドレス６５ＤＡＨに対応付けられている。
【００３１】
上記と同様に、物理アドレス６５ＤＡＨには第３の変換テーブル１５３−２が記録されている。
第３の変換テーブル１５３−２に含まれる１６対の論理アドレス及び物理アドレスは、ユーザ領域にある１６個のブロックを指定する。
例えば第３の変換テーブル１５３−２において、論理アドレス００１０Ｈは物理アドレス６５ＥＦＨに対応付けられている。物理アドレス６５ＥＦＨには論理アドレス００１０Ｈのデータが記録されている。
【００３２】
即ち、論理アドレスを物理アドレスに変換する多層構造の第ｉの変換テーブルに基づいて指定される物理アドレスに格納された最下層の変換テーブル（第ｎの変換テーブル）が指定する物理ブロックアドレスにデータが記憶されている。
【００３３】
例えば３階層のツリー構造の変換テーブルは、１６個の第１の変換テーブル、２５６個（＝１６２）の第２の変換テーブル、４０９６個（＝１６３）の第３の変換テーブル、６５５３６個（＝１６４）のデータを有する。この変換テーブルにより、１ＧＢのフラッシュメモリ（６５５３６個のブロックを有する。）のアドレス空間の論理アドレス／物理アドレス変換をすることが出来る。
第１〜第３の変換テーブルは、各ブロックの冗長領域（未使用領域がある。）に分散して書き込まれている故、これらの変換テーブル専用の記録領域は不要である。
【００３４】
例えば４階層のツリー構造の変換テーブルは、１６ＧＢフラッシュメモリ（１０４８５７６個のブロックを有する。）のアドレス空間の論理アドレス／物理アドレス変換をすることが出来る（ブロックのアドレスは３Ｂである。）。
このように、本発明によれば、小さな論理／物理アドレス変換テーブルを階層的に組み合わせることにより、大きなアドレス空間の論理アドレス／物理アドレス変換をすることが出来る。
不揮発性メモリ１１２に階層情報ｎ１５５を記録している故に、互換性を取ることが容易である。メモリカード毎に不揮発性メモリ１１２の容量に応じて階層数ｎを変更した場合にも、制御部１１１が階層数ｎを読み出すことにより論理アドレスから物理アドレスに正しく変換することが出来る。階層数ｎ１５５を記録しないで、不揮発性メモリ１１２の記録容量に応じた階層数ｎを規格で定めても良い。この場合、制御部１１１は、記録容量に応じて階層数ｎを求め、論理アドレスから物理アドレスに変換を行う。
【００３５】
図３は、本発明の実施例１のメモリカードにおける、データの読み出し方法のフローチャートを示す。図３において、メモリカード１０２はホスト１０１からデータの読み出し命令（論理アドレスを含む。）を入力する（ステップ３０１）。メモリカード１０２の制御部１１１は、ｉ＝１とする（初期設定）（ステップ３０２）。不揮発性メモリ１１２から第１の変換テーブル１５１を読み出す（ステップ３０３）。
次に制御部１１１は、読み出した変換テーブルが最下層の変換テーブル（第ｎの変換テーブル）か否かをチェックする（ステップ３０４）。もし最下層の変換テーブルであればステップ３０８に進む。もし最下層の変換テーブルでなければ、ｉ＝ｉ＋１とする（ステップ３０５）。
【００３６】
次に制御部１１１は、読み出した変換テーブルの中から、目的の論理アドレスに最も近く且つそのアドレスより値が大きくない論理アドレスを検索する（ステップ３０６）。次に制御部１１１は、検索した論理アドレスに対応する物理アドレスから第ｉの変換テーブルを読み出す（ステップ３０７）。ステップ３０４に進み、上記の処理を繰り返す。
ステップ３０４で読み出した変換テーブルが最下層の変換テーブルであれば、制御部１１１は、最下層の変換テーブルから目的の論理アドレスに対応した物理アドレスを読み出し、その物理アドレスからデータを読み出す（ステップ３０８）。制御部１１１は、読み出したデータをホスト１０１に出力する（ステップ３０９）。処理を終了する。
【００３７】
図４は、本発明の実施例１のメモリカードにおける、データの書き換え方法のフローチャートを示す。図４において、メモリカード１０２はホスト１０１からデータの書き換え命令（論理アドレスを含む。）を入力する（ステップ４０１）。メモリカード１０２の制御部１１１は、何も記録されていない（データが全て１である）物理アドレスを選び、そこに新しいデータを書く（ステップ４０２）。
次に制御部１１１は、変更した物理アドレスに関連する変換テーブルを変更して、新たなブロックに記録する（ステップ４０３）。第１の変換テーブルを有するブロックには第１の変換テーブル有効フラグが対応付けられている（有効であれば１、無効であれば０）。次に、制御部１１１は、第１の変換テーブルが記録されていたブロックの第１の変換テーブル有効フラグを０にする（ステップ４０４）。
【００３８】
ステップ４０３において、書き換えの必要がある変換テーブルは、変更した物理アドレスからツリーをさかのぼって第０の変換テーブル１４１までの変換テーブルである。即ち実施例１（階層数ｎ＝３）では最大でも４個のブロック（データ及び変換テーブル）を書き換えれば良い。
例えば図２において、論理アドレス００００Ｈのデータを書き換えたとする。図２において、論理アドレス００００Ｈの元のデータは物理アドレス６４８３Ｈに記録されているが、新たなデータを新たな物理アドレスであるＡ０２３Ｈに書き込んだとする。論理アドレス００００Ｈに対応する物理アドレスをＡ０２３Ｈに更新した第３の変換テーブル１５３−１を、新たな物理アドレスであるＡ０３５Ｈの冗長領域にコピーする。
【００３９】
次に制御部１１１は、第２の変換テーブル１５２−１の論理アドレス００００Ｈに対応する物理ブロックを６４１１ＨからＡ０３５Ｈに変更し、新たな物理アドレスであるＡ０３８Ｈの冗長領域に新たな第２の変換テーブル１５２−１を書き込む。
次に制御部１１１は、第１の変換テーブル１５１−１の論理アドレス００００Ｈに対応する物理ブロックを６４１０ＨからＡ０３８Ｈに変更し、新たな物理アドレスであるＡ０３ＢＨの冗長領域に新たな第１の変換テーブル１５１−１を書き込む。次に制御部１１１は、ＲＡＭ上の第０の変換テーブル１４１の論理アドレス００００Ｈに対応する物理ブロックを５３ＡＣＨからＡ０３ＢＨに変更する。
従来例においては、データを書き換えると、管理情報記録領域１３１の大きな変換テーブルを書き換える（実際には、未記録領域に新たな変換テーブルを書き込む）必要があった。実施例１の記憶装置においては、データを書き換えた場合、少数の小さな変換テーブルを書き換えるだけで良い。
【００４０】
《実施例２》
図５を用いて、本発明の実施例２の記憶装置について説明する。実施例２の記憶装置は、１ＧＢのフラッシュメモリを有するメモリカードである。実施例２のメモリカードは、実施例１と同一の構成を有する（図１）。実施例２において、ホスト１０１はメモリカードの挿入スロットを有する携帯型映像音声再生機である。
実施例２のメモリカードは、実施例１と異なる変換テーブルを有する。これ以外の点において、実施例２のメモリカードは実施例１と同一である。
【００４１】
実施例２の記憶装置は、不揮発性メモリのユーザ領域１３２の冗長領域に小さな第１の変換テーブル６４Ｂ（＝２Ｂ×２×１６）を複数個（実施例においては４個）記録しており、ユーザ領域１３２の他の冗長領域に鎖状構造を有する他の変換テーブル（第２〜第ｎの変換テーブル）を記録する。ｎは２以上の任意の整数である。実施例２の１ＧＢのメモリカードにおいてはｎ＝１０２４（＝１Ｇ／（１６ｋ×１６×４））である。第１の変換テーブルの大きさは任意である。
第２〜第ｎの変換テーブルは８Ｂ（＝２Ｂ×２×２）の大きさを有し、２対の論理アドレス及び物理アドレスを含む。第２〜第ｎの変換テーブルには１ビットの継続フラグが対応付けられている。
【００４２】
電源起動時、制御部１１１は、不揮発性メモリ１１２のユーザ領域１３２の冗長領域から６４Ｂ（＝２Ｂ×２×１６）の大きさを有する第１の変換テーブル５０１（１６対の論理アドレス及び物理アドレスを有する。各アドレスは２Ｂである。）を読み出し、ＲＡＭ１２２に格納する（第１の変換テーブル５０１）。
制御部１１１は、第１の変換テーブル５０１に基づいて第２〜第ｎの変換テーブルのいずれか１つ又は複数の変換テーブル（第ｉの変換テーブル）を読み出し、ＲＡＭ１２２に格納する。制御部１１１は、第ｉの変換テーブル（１≦ｉ≦（ｎ−１））に基づいて第（ｉ＋１）の変換テーブルを読み出すことが出来る。これを繰り返すことにより任意の変換テーブルを読み出すことが出来る。
制御部１１１は、ＲＡＭ１２２に格納された変換テーブルを用いて、任意の論理アドレスに対応づけられた不揮発性メモリ１１２の物理アドレスにデータを書き込み、物理アドレスからデータを読み出すことが出来る。
【００４３】
図５は、本発明の実施例２のメモリカードにおける、論理アドレスを物理アドレスに変換する変換テーブルの鎖状構造を説明する図である。図５を説明する。
第１の変換テーブル５０１に含まれる６４対の論理アドレス及び物理アドレスは、ユーザ領域にある６４個のブロックを指定する。それらのブロックのデータ記録領域にはデータが記録されており、それらのブロックの冗長領域には、第２の変換テーブル５０２（合計６４個の第２の変換テーブル）が記録されている。
【００４４】
実施例２の複数個（４個）の第１の変換テーブル５０１は、一定間隔で、全アドレス空間に均等に位置する論理アドレスを有する。実施例２のメモリの全ブロックアドレス空間は００００Ｈ〜ＦＦＦＦＨであり、第１の変換テーブル５０１は、０ｊ００Ｈ（ｊは０≦ｊ≦ＦＦＨであって、４の整数倍の整数）の論理アドレスに対応づけられた物理アドレスを有する。例えば第１の変換テーブル５０１において、論理アドレス００００Ｈは物理アドレス２５３８Ｈに対応付けられている。
０ｊ００Ｈの論理アドレスに対応付けられた物理アドレス、及びそれに鎖状に繋がる第２〜第ｎ（＝１０２４）の変換テーブルの全体は、０ｊ００Ｈ〜０（ｊ＋３）ＦＦＨの範囲の論理アドレスに対応付けられた物理アドレスを指定する。
【００４５】
物理アドレス２５３８Ｈのブロックのデータ記録領域には、論理アドレス００００Ｈのデータが書き込まれる。物理アドレス２５３８Ｈのブロックの冗長領域には、第２の変換テーブル５０２及び継続フラグ（＝０）が記録されている。第２の変換テーブル５０２に含まれる１対の論理アドレス及び物理アドレスは、鎖状に繋がる次の論理アドレス０００１Ｈ及び物理アドレス２７Ａ４Ｈを指定する。継続フラグは、それに対応付けられた変換テーブルによって指定された物理アドレスのブロックの冗長領域に、次の変換テーブルが記録されているか否かを示す。継続フラグ＝０であれば次の変換テーブルが記録されており、継続フラグ＝１であれば次の変換テーブルが記録されていない。これにより、鎖状の変換テーブルの最後か否かを識別できる。
【００４６】
物理アドレス２７Ａ４Ｈのブロックのデータ記録領域には、論理アドレス０００１Ｈのデータが書き込まれる。物理アドレス２７Ａ４Ｈのブロックの冗長領域には、第３の変換テーブル５０３及び継続フラグ（＝０）が記録されている。第３の変換テーブル５０３に含まれる２対の論理アドレス及び物理アドレスは、鎖状に繋がる次の論理アドレス０００２Ｈ及び物理アドレス２７ＢＢＨの対と、鎖状に繋がる前の論理アドレス００００Ｈ及び物理アドレス２５３８Ｈの対と、を指定する。
【００４７】
上記と同様に、第ｉの物理アドレスのブロックのデータ記録領域には、論理アドレス０００ｉＨのデータが書き込まれる。そのブロックの冗長領域には、第（ｉ＋２）の変換テーブル５０４及び継続フラグ（＝０）が記録されている。第（ｉ＋２）の変換テーブル５０４に含まれる２対の論理アドレス及び物理アドレスは、鎖状に繋がる次の第（ｉ＋１）の論理アドレス及び第（ｉ＋１）の物理アドレスの対と、鎖状に繋がる前の第（ｉ−１）の論理アドレス及び第（ｉ−１）の物理アドレスの対と、を指定する。
鎖状に繋がった最後の変換テーブルに対応する継続フラグは１である。その最後の変換テーブルによって指定された物理アドレスのブロックにはデータが記録されており、変換テーブルが記録されていない。
【００４８】
実施例２のメモリカードにおいて、第１〜第４の変換テーブルは、各ブロックの冗長領域（未使用領域がある。）に分散して書き込まれている故、これらの変換テーブル専用の記録領域は不要である。
実施例１又は実施例２において、第１の変換テーブルを不揮発性メモリ１１２の管理情報記録領域１３１に記録しても良い。この場合も、管理情報記録領域１３１に記録された情報量は小さい。本発明によれば、変換テーブル専用の記録領域を設けることなく（又は小さな管理情報記録領域で）、大きなアドレス空間の論理アドレス／物理アドレス変換をすることが出来る。
第（ｉ＋２）の変換テーブルには、鎖状で前に位置する第（ｉ＋１）の変換テーブルが書き込まれているブロックの論理アドレス及び物理アドレスが記載されている故、論理アドレスが小さくなる方向へのアクセスも容易である。不揮発性メモリ１１２に鎖状に連続する変換テーブルの数ｎを記録しても良いし、記録しなくても良い。
【００４９】
実施例２のメモリカードのデータの読み出し方法を説明する。最初に目的の論理アドレスが鎖に繋がっている論理アドレスを第１の変換テーブル５０１の中から探し出す。次に、その論理アドレスから順次変換テーブルをたどって行って、目的の論理アドレスに対応した物理アドレスを探し出す。その物理アドレスからデータを読み出す。
【００５０】
実施例２のメモリカードのデータの書き換え方法を説明する。新たな物理アドレスに新たなデータと第ｋの変換テーブルとを書き込み、旧いデータが書き込まれた物理アドレスのブロックの有効／無効ビットを０にする。実施例２においては第２〜ｎの変換テーブルが非常に小さいので、幾つもの変換テーブルを１つのブロックの冗長領域に書き込むことが出来る。又、変換テーブル毎に無効化ビットが対応付けられている（無効でない＝１／無効＝０）。第（ｋ−１）の変換テーブル及び第（ｋ＋１）の変換テーブルを無効化し（無効化ビット＝０）、同じブロックの冗長領域内に新たな第（ｋ−１）の変換テーブル及び第（ｋ＋１）の変換テーブル（第ｋの変換テーブルが書き込まれた物理アドレスが、更新されている。）を書き込む。
従来例においては、データを書き換えると、管理情報記録領域１３１の大きな変換テーブルを書き換える（実際には、未記録領域に新たな変換テーブルを書き込む）必要があった。実施例１の記憶装置においては、データを書き換えた場合、少数の小さな変換テーブルを書き換えるだけで良い。
制御部１１１は、セクタからデータを読み出す時、冗長領域に書かれた変換テーブルを同時に読み出すことが出来る。
【００５１】
【発明の効果】
本発明によれば、変換テーブルのための専用記録領域が不要な又はわずかしか必要としない書き換え可能な不揮発性メモリを有する記憶装置を実現出来るという有利な効果が得られる。
本発明によれば、データの読み出しの際、同時に変換テーブルを読み出すことが出来る書き換え可能な不揮発性メモリを有する記憶装置を実現出来るという有利な効果が得られる。
本発明によれば、データの書き換えを行ったアドレスによっては、少数の小さな変換テーブルを書き換えるだけで済む書き換え可能な不揮発性メモリを有する記憶装置を実現出来るという有利な効果が得られる。
【図面の簡単な説明】
【図１】本発明の実施例１及び２のメモリカードの構成を示す図
【図２】本発明の実施例１のメモリカードにおける、論理アドレスを物理アドレスに変換する変換テーブルのツリー構造を説明する図
【図３】本発明の実施例１のメモリカードにおける、データの読み出し方法のフローチャート
【図４】本発明の実施例１のメモリカードにおける、データの書き換え方法のフローチャート
【図５】本発明の実施例２のメモリカードにおける、論理アドレスを物理アドレスに変換する変換テーブルの鎖状構造を説明する図
【図６】従来例のメモリカードの構成を示す図
【符号の説明】
１０１    ホスト
１０２    メモリカード
１１１、６１２    制御部
１１２    不揮発性メモリ
１２１    外部インターフェース部
１２２、６１４    ＲＡＭ
１３１、６１５    管理情報記録領域
１３２、６５４    ユーザ領域
６１１    ホストインターフェース
６２１    ＲＯＭ
６１５    フラッシュメモリ
【図１】
0003694501.tif 000002
【図２】
0003694501.tif 000003
【図３】
0003694501.tif 000004
【図４】
0003694501.tif 000005
【図５】
0003694501.tif 000006
【図６】
0003694501.tif 000007