JP2008204155A - メモリシステム、コンピュータシステム及びメモリ - Google Patents

Abstract

【課題】アクセス速度を低下させることなく、論理アドレスと物理アドレスとの変換に用いられる予備的な記憶領域の必要容量を抑制する。
【解決手段】論理アドレスを昇順に、メモリの欠陥ブロックの物理アドレスをスキップさせながら、物理アドレスの昇順に対応づけるように、論理アドレスと物理アドレスとの相関関係を定める。そして、欠陥ブロックの物理アドレスを、当該物理アドレスの昇順に、第２ブロック５６の物理アドレスの昇順に、連続して個々に格納する。論理アドレスから物理アドレスを求める場合は、論理アドレスに基づいて、複数の第２ブロック５６からターゲットブロックを検索し、ターゲットブロックの物理アドレスを論理アドレスに加算することにより物理アドレスを求める。
【選択図】図８

Description

本発明は、ユーザによって直接利用されるデータ（ユーザデータ）を記憶するメモリにおいて、ユーザデータを直接記憶しない予備的な記憶領域の容量を抑制する技術に関する。

一般的に、メモリでは、欠陥ブロックを許容するために、論理アドレスと物理アドレスとをそのまま対応付けることができない。したがって、従来より、メモリにおいて、論理アドレスと物理アドレスとの変換に必要な情報を記憶しておく予備的な記憶領域を設ける技術が知られている。

このような方法としては、アクセスの単位となるデータ領域（ブロック）に対応してそれぞれ予備領域を設け、当該予備領域に当該ブロックの良否を示す特性情報を記憶しておく。そして、所定のタイミング（例えば電源投入時）に、コントローラが全ての予備領域から特性情報を読み込んで、論理アドレスと物理アドレスとの対応関係を示すテーブルを作成する方法がある。また、メモリ内にこのようなテーブルを格納しておく方法もある。

特開平１０−０４９４４７号公報

ところが、各ブロックの可否を示す特性情報は、比較的小さい情報ではあるが、これを全てのブロックについて記憶すれば、そもそもブロックの数が膨大であるために、それなりに大きな予備領域が必要となる。

また、アクセスしたブロックがたまたま欠陥であった場合に、他のブロックをサーチするという方法も考えられるが、この場合は、欠陥か否かによってアクセス速度が異なるため、保証可能なアクセス速度が低下する。

本発明は、上記課題に鑑みなされたものであり、アクセス速度を低下させることなく、論理アドレスと物理アドレスとの変換に用いられる予備的な記憶領域の必要容量を抑制することを目的とする。

上記の課題を解決するため、請求項１の発明は、メモリシステムであって、ユーザ情報を記憶するために設けられ、互いに重複しない第１物理アドレスが個々に割り当てられる複数の第１ブロックと、前記複数の第１ブロックのうちの欠陥ブロックの第１物理アドレスを個々に記憶するために設けられる複数の第２ブロックと、論理アドレスと前記複数の第２ブロックに格納される情報とに基づいて、前記論理アドレスに対応する第１物理アドレスを求める演算装置とを備えることを特徴とする。

また、請求項２の発明は、前記複数の第２ブロックには、互いに重複しない第２物理アドレスが個々に割り当てられており、前記演算装置は、論理アドレスを用いて、前記複数の第２ブロックからターゲットブロックを検索し、前記ターゲットブロックから読み出される欠陥ブロックの第１物理アドレスと、前記ターゲットブロックの第２物理アドレスとに基づいて、前記ターゲットブロックから読み出された欠陥ブロックの第１物理アドレスより前方に存在する正常な第１ブロックの個数を求め、前記論理アドレスと前記個数とに基づいて、前記論理アドレスに対応する第１物理アドレスを求めることを特徴とする。

また、請求項３の発明は、請求項１または請求項２の発明に係るメモリシステムであって、前記複数の第２ブロックに記憶される複数の欠陥ブロックの第１物理アドレスは、前記第１物理アドレスの順に従って、前記第２物理アドレスの順で、前記複数の第２ブロックに格納されることを特徴とする。

また、請求項４の発明は、請求項１ないし請求項３のいずれかの発明に係るメモリシステムであって、前記複数の第１ブロックのうちの欠陥ブロックの第１物理アドレスを記憶する複数の予備ブロックと、前記複数の予備ブロックに記憶されている情報を前記複数の第２ブロックに転送する転送部とをさらに備えることを特徴とする。

また、請求項５の発明は、コンピュータシステムであって、必要に応じて論理アドレスを生成するコンピュータと、ユーザ情報を記憶するために設けられ、互いに重複しない第１物理アドレスが個々に割り当てられる複数の第１ブロックを有するメモリと、前記複数の第１ブロックのうちの欠陥ブロックの第１物理アドレスを個々に記憶するために設けられ、互いに重複しない第２物理アドレスが個々に割り当てられる複数の第２ブロックを有するコントローラメモリと、前記コンピュータから受信した論理アドレスを用いて、前記複数の第２ブロックからターゲットブロックを検索し、前記ターゲットブロックから読み出される欠陥ブロックの第１物理アドレスと、前記ターゲットブロックの第２物理アドレスとに基づいて、前記ターゲットブロックから読み出された欠陥ブロックの第１物理アドレスより前方に存在する正常な第１ブロックの個数を求め、前記論理アドレスと前記個数とに基づいて、前記論理アドレスに対応する第１物理アドレスを求める演算装置とを備えることを特徴とする。

また、請求項６の発明は、論理アドレスから物理アドレスを得る演算装置から物理アドレスを用いてアクセスされるメモリであって、記憶素子群から構成され、互いに重複しない物理アドレスが割り当てられる複数のブロックを備え、前記複数のブロックは、ユーザ情報を記憶するために設けられる複数の第１ブロックと、前記複数の第１ブロックのうちの欠陥ブロックの物理アドレスを個々に記憶するために設けられる複数の第２ブロックとを備え、前記複数の第２ブロックに記憶される複数の欠陥ブロックの物理アドレスは、前記物理アドレスの順に従って、前記複数の第２ブロックに割り当てられた物理アドレスの順に、前記複数の第２ブロックに格納されることを特徴とする。

請求項１ないし請求項５に記載の発明では、複数の第１ブロックのうちの欠陥ブロックの第１物理アドレスを個々に記憶するために設けられる複数の第２ブロックと、論理アドレスと複数の第２ブロックに格納される情報とに基づいて、論理アドレスに対応する第１物理アドレスを求める演算装置とを備えることにより、正常な第１ブロックの物理アドレスを記憶する必要がない。あるいは、全てのブロックに関する特性（欠陥の有無）と転送先の物理アドレスとを記憶する必要がない。したがって、第２ブロックの数を減らすことが可能となる。

また、請求項２に記載の発明では、論理アドレスを用いて、複数の第２ブロックからターゲットブロックを検索し、ターゲットブロックから読み出される欠陥ブロックの第１物理アドレスと、ターゲットブロックの第２物理アドレスとに基づいて、ターゲットブロックから読み出された欠陥ブロックの第１物理アドレスより前方に存在する正常な第１ブロックの個数を求め、論理アドレスと個数とに基づいて、論理アドレスに対応する第１物理アドレスを求めることにより、請求項１に記載の発明を容易に実現できる。

また、請求項６に記載の発明では、複数の第２ブロックに記憶される複数の欠陥ブロックの物理アドレスは、物理アドレスの順に従って、複数の第２ブロックに割り当てられた物理アドレスの順に、複数の第２ブロックに格納されることにより、物理アドレスを求めるために必要となる、第２ブロックの数を減らすことが可能となる。

以下、本発明の好適な実施の形態について、添付の図面を参照しつつ、詳細に説明する。

＜１． 第１の実施の形態＞
図１は、本発明に係るコンピュータシステム１を示す図である。コンピュータシステム１は、一般的なパーソナルコンピュータとしての機能を有するコンピュータ２と、コンピュータ２のカードスロットに挿入されるメモリカード３とから構成される。

図２は、コンピュータ２の構成を示すブロック図である。コンピュータ２は、各種データの演算や制御信号の生成等を行うＣＰＵ２１、各種データを格納する記憶装置２２、ユーザがコンピュータ２への指示を入力するために使用される操作部２３、ユーザに各種データを提示する表示部２４、およびインタフェース２５を備えている。操作部２３とは、例えば、マウスやキーボード等であり、表示部２４とは、例えば、液晶ディスプレイやＣＲＴ等である。

コンピュータ２は、例えば、記憶装置２２に記憶されているアプリケーションソフトウェア等のプログラムに従って動作し、必要に応じてメモリカード３に対してアクセス要求を送信する。

なお、以下に言うアクセス要求とは、ユーザデータの書き込み要求や、メモリカード３（メモリ４）に記憶されているユーザデータの読み出し要求である。したがって、書き込み要求の場合は書き込むユーザデータの書き込み位置を示す論理アドレスが生成され、読み出し要求の場合は読み込むユーザデータが格納されている位置を示す論理アドレスが生成される。すなわち、コンピュータ２において生成されるアクセス要求には、論理アドレスが含まれており、インタフェース２５を介して、メモリカード３に送信される。

図３は、メモリカード３の構成を示すブロック図である。メモリカード３は、メモリ４と、メモリ４を制御するメモリコントローラ５とを備え、コンピュータ２に対して着脱自在な構造となっている。

図４は、メモリ４の内部構造を示す概略図である。図４に示すように、メモリ４は、複数の第１ブロック４２から構成されるユーザ情報記憶領域４０と、複数の予備ブロック４３から構成される予備記憶領域４１とを備えている。

図５は、メモリ４におけるブロック６（第１ブロック４２及び予備ブロック４３）の構造を示す図である。メモリ４が有する複数のブロック６は、図５に示すように、それぞれが複数の記憶素子６０（記憶素子群）から構成され、互いに重複しない１の物理アドレス（第１物理アドレス）によってアクセスされる記憶素子の集まりである。

なお、本実施の形態では、メモリ４の記憶素子６０は不揮発性の記憶素子であるがこれに限られるものではない。

また、本実施の形態では、図５において、第１ブロック４２と予備ブロック４３とが、同数の記憶素子６０を備えているものとして図示している。しかし、第１ブロック４２に含まれる記憶素子６０の数は、少なくとも、１の物理アドレスによって指定されるユーザデータを記憶するために必要な記憶素子６０の数であればよい。すなわち、１回のアクセスで読み込まれる（又は、書き込まれる）ユーザデータの容量によって決定される。また、予備ブロック４３に含まれる記憶素子６０の数は、少なくとも、第１ブロック４２を個々に指定する物理アドレスを記憶するために必要な記憶素子６０の数であればよい。すなわち、物理アドレスの長さ（容量）はメモリ４が備える第１ブロック４２の数によって決定される。したがって、第１ブロック４２が備える記憶素子６０の数は、予備ブロック４３が備える記憶素子６０の数と異なっていてもよい。

図６は、ユーザ情報記憶領域４０を例示する図である。本明細書では、例えば、特定（Ａ）の物理アドレス空間における物理アドレスを、「物理アドレスＡ」と総称し、そのうちのｋ番目の物理アドレスＡを「物理アドレスＡｋ」と称する（ただしｋは０以上の整数）。

ユーザ情報記憶領域４０は、先述のように、複数（Ｎ個）の第１ブロック４２から構成される記憶領域であって、ユーザデータを記憶する（Ｎは自然数）。各第１ブロック４２には、それぞれ重複しない物理アドレスＰＢＡ（物理アドレスＰＢＡ０乃至ＰＢＡ（Ｎ−１））が割り当てられる。なお、メモリ４上の物理アドレスＰＢＡは、本発明における第１物理アドレスに相当する。

一般に、製品としてのメモリ４に形成される第１ブロック４２には、正常にアクセスすることができるもの（正常ブロック４２０）と、アクセスすることができないもの（欠陥ブロック４２１）とが存在する。欠陥ブロック４２１に対してはアクセスすることができない（利用することができない）ので、欠陥ブロック４２１にはユーザデータは記憶されず、論理アドレスが割り当てられることはない。

図示の都合上、図６では、正常ブロック４２０に「Ｇｏｏｄ」、欠陥ブロック４２１に「Ｂａｄ」が、それぞれ情報として格納されているかのように示している。しかし、本実施の形態では、ユーザデータを格納する１つの単位を第１ブロック４２と定義するのであって、第１ブロック４２には、ブロックの状態を示す情報は記憶しない。ただし、このことは、メモリ４において、第１ブロック４２（ユーザ情報記憶領域４０）以外の記憶領域に、ブロックの状態を示す情報等を記憶することを禁止するものではない。

図７は、図６に示すユーザ情報記憶領域４０に対する予備記憶領域４１を例示する図である。予備記憶領域４１は、先述のように、複数（Ｍ個）の予備ブロック４３から構成される記憶領域であって、冗長情報４４（図３）を記憶する。すなわち、冗長情報４４は、個々の予備ブロック４３が記憶する個々の情報の集合体となる。なお、本実施の形態では、Ｍ＝２ｎ（ｎは自然数）とする。

本実施の形態における冗長情報４４とは、後述するメモリコントローラ５が論理アドレスを物理アドレスに変換する際に必要な情報であって、メモリ４に記憶される情報のうちユーザ情報以外の全ての情報を指す概念ではない。本実施の形態では、冗長情報４４を格納する領域として予備記憶領域４１を定義するのであって、メモリ４において、ユーザ情報以外の情報を記憶する領域として予備記憶領域４１のみ設けるという意味ではない。したがって、メモリ４は、ユーザ情報及び冗長情報４４以外の情報（例えばＥＣＣ用の情報等）を記憶する予備的な他の記憶領域を備えていてもよい。

個々の予備ブロック４３は、それぞれメモリ４上の物理アドレス（物理アドレスＰＢＡＮ乃至ＰＢＡ（Ｎ＋Ｍ−１））が割り当てられている。なお、本実施の形態では、ユーザ情報記憶領域４０における最後の第１ブロック４２の物理アドレスは、物理アドレスＰＢＡ（Ｎ−１）であり、予備記憶領域４１における先頭の予備ブロック４３の物理アドレスは物理アドレスＰＢＡＮである。すなわち、ユーザ情報記憶領域４０と予備記憶領域４１とは連続する記憶領域として割り当てられているが、もちろんこれに限定されるものではない。

また、予備ブロック４３には、当該予備ブロック４３が使用されていないことを示す無効情報（図７に示す「ＮＯＵ」）、又は、欠陥ブロック４２１の物理アドレスＰＢＡ（図７に示す例では物理アドレスＰＢＡ３，５，７，１５，２０，２１，２７）を格納する。なお、予備ブロック４３に格納する情報は、欠陥ブロック４２１の物理アドレスＰＢＡを得ることができる情報であればよい。

予備ブロック４３の個数Ｍは、メモリ４が製品として許容する欠陥ブロック４２１の数に応じて決定される。例えば、メモリ４が最大で２５６個の欠陥ブロック４２１を許容するならば、少なくとも２５６個の予備ブロック４３を設けるように、メモリ４が設計される。したがって、実際の欠陥ブロック４２１の個数の予備ブロック４３には、それぞれ欠陥ブロック４２１の物理アドレスＰＢＡが格納され、その他の予備ブロック４３には、それぞれ無効情報ＮＯＵが格納される。

本実施の形態では、無効情報ＮＯＵの値として、第１ブロック４２の個数Ｎに対して充分に大きい値を採用する。ただし、無効情報ＮＯＵとして格納される情報は、欠陥ブロック４２１の物理アドレスＰＢＡと区別できる情報であればよい。

欠陥ブロック４２１はメモリ４に対する検査工程等で検出され、その物理アドレスＰＢＡがいずれかの予備ブロック４３に記憶される。ここでは検査工程について詳細には述べないが、検出された欠陥ブロック４２１の物理アドレスＰＢＡは、後述するメモリコントローラ５が予備記憶領域４１を読み出す順序（本実施の形態では、予備ブロック４３の物理アドレスＰＢＡの昇順）に、順次（欠陥ブロック４２１の物理アドレスＰＢＡの小さい順）に格納される。また、全ての欠陥ブロック４２１の検出が終了したときに、残りの予備ブロック４３に無効情報ＮＯＵを格納する。このようにして、全ての予備ブロック４３に対する情報の書き込みが完了することによって、予備記憶領域４１に冗長情報４４が作成される。

なお、メモリ４における欠陥ブロック４２１がまったく存在しない場合には、冗長情報４４は欠陥ブロック４２１の物理アドレスＰＢＡを含むことはない。また、メモリ４が備える予備ブロック４３の数と同数の欠陥ブロック４２１が存在する場合、冗長情報４４は無効情報ＮＯＵを含むことはない。

図３に戻って、メモリコントローラ５は、演算器５０、プログラム５４を格納するＲＯＭ５１、ＳＲＡＭとして構成されるコントローラメモリ５２、及びコンピュータ２に接続するためのインタフェース５３を備える。メモリコントローラ５は、コンピュータ２から受信するアクセス要求に応じて、メモリ４にアクセスする。

メモリコントローラ５の演算器５０は、ＲＯＭ５１に格納されているプログラム５４に従って動作し、コントローラメモリ５２に記憶されている参照情報５５に基づいて、コンピュータ２から受信したアクセス要求に含まれる論理アドレスＬＢＡから、アクセス要求された第１ブロック４２の物理アドレスＰＢＡを演算により得る。

演算器５０による演算処理の詳細は後述するが、演算器５０は、論理アドレスＬＢＡとオフセットＯＦＦとを用いて、式１を演算することにより、アクセス要求された第１ブロック４２の物理アドレスＰＢＡを得る。

コントローラメモリ５２は、メモリ４のブロック６を構成する記憶素子６０よりも高速にアクセス可能な記憶素子（図示せず）で構成され、予備記憶領域４１に記憶されている冗長情報４４が転送された結果である参照情報５５を記憶する。コントローラメモリ５２に記憶された参照情報５５は、演算器５０により参照される。なお、本実施の形態では、コントローラメモリ５２を構成する記憶素子として、高速なアクセスを実現するために、揮発性の記憶素子を用いる。

図８は、図７に示す冗長情報４４がコントローラメモリ５２に参照情報５５として記憶される状態を例示する図である。

コントローラメモリ５２は、予備ブロック４３に格納されている情報を個々に格納することが可能な複数（Ｍ個）の第２ブロック５６を備えている。これら複数の第２ブロック５６には、互いに重複しない物理アドレスＲＡＤ（第２物理アドレス）が割り当てられている。

メモリコントローラ５の演算器５０は、冗長情報４４をコントローラメモリ５２に転送する際に、予備記憶領域４１の物理アドレスＰＢＡの順に従って予備ブロック４３にアクセスし、当該予備ブロック４３に格納されている情報（欠陥ブロック４２１の物理アドレスＰＢＡ又は無効情報ＮＯＵ）を、第２ブロック５６の物理アドレスＲＡＤの順に、第２ブロック５６に格納する。すなわち、演算器５０は、本発明における転送部としての機能も備えている。

参照情報５５は、各第２ブロック５６に格納された情報の集合体であるから、本実施の形態における参照情報５５は、冗長情報４４と同一の情報としてコントローラメモリ５２上に作成される。

このような参照情報５５を作成することにより、第２ブロック５６に格納されている欠陥ブロック４２１の物理アドレスＰＢＡから、当該第２ブロック５６の物理アドレスＲＡＤを引くと、その値は、当該第２ブロック５６に格納されている欠陥ブロック４２１の物理アドレスＰＢＡより前方に存在する正常ブロック４２０の個数を示すこととなる。

図６及び図８に示す例で説明すると、例えば物理アドレスＲＡＤ３で指定される第２ブロック５６から読み出される値は、「１５（ＰＢＡ１５）」であり、これから「３（ＲＡＤ３）」を引くと、その値は「１２」となる。図６で確認すれば、物理アドレスＰＢＡ１５で指定される欠陥ブロック４２１（第１ブロック４２）の前方には、１２個の正常ブロック４２０が存在している。言い換えれば、物理アドレスＰＢＡ１５より前方には、論理アドレスＬＢＡを割り当て可能な正常ブロック４２０が１２個存在すると言える。したがって、最初から数えて１２個目までの論理アドレスＬＢＡは、物理アドレスＰＢＡ１５より前方に存在する第１ブロック４２の物理アドレスＰＢＡに割り当て可能であることがわかる。

インタフェース５３は、コンピュータ２のインタフェース２５と迎合する形状であり、コンピュータ２とメモリカード３とを電気的にも接続する。このようなインタフェース２５，５３としては、例えば、ＰＣＭＣＩＡやＡＴＡといった規格に準拠したものが存在するが、もちろんこれらに限られるものではない。また、インタフェース２５とインタフェース５３とは、必ずしも直接接続される必要はなく、両者間にケーブルを介してもよいし、メモリカード３がいわゆる非接触型である場合には、無線であってもよい。すなわち、コンピュータ２とメモリカード３との間で、データ通信が可能な接続形態であれば、どのような構造であってもよい。

以上が、コンピュータシステム１の構造及び機能の説明である。次に、コンピュータシステム１の動作について説明する。

図９は、主にメモリカード３（メモリコントローラ５）の動作を示す流れ図である。

まず、メモリコントローラ５は、メモリカード３に電源が投入されると、ステップＳ１でＹｅｓと判定する。メモリカード３に電源が投入されるとは、メモリカード３への電源の供給が開始された場合であって、既に電源が投入されているコンピュータ２にメモリカード３が装着された場合を含む。

ステップＳ１でＹｅｓと判定すると、メモリコントローラ５は、メモリ４の予備記憶領域４１にアクセスして、そこに記憶されている冗長情報４４を読み出し、読み出した冗長情報４４のコントローラメモリ５２への転送を開始する（ステップＳ２）。なお、メモリ４の予備記憶領域４１（各予備ブロック４３）の物理アドレスＰＢＡは、製品に固定であり、ステップＳ２の実行に先立って、メモリコントローラ５は、これを予め取得しているものとする。

本実施の形態におけるメモリコントローラ５は、予備記憶領域４１を構成する予備ブロック４３のうち、先頭の予備ブロック４３から順に最後までアクセスして（すなわちＭ回アクセスすることとなる）、アクセスした予備ブロック４３に格納されている情報を、順次、第２ブロック５６に転送する。これによって、図９に示すように、コントローラメモリ５２には、図７に示す予備記憶領域４１に記憶されている情報と同等の情報が記憶される。

なお、最終的に、コントローラメモリ５２に、図９に示すような参照情報５５が形成されるのであれば、予備記憶領域４１における格納順序、及びメモリコントローラ５による読み出し順序はどのようなものであってもよい。

冗長情報４４の転送（参照情報５５の作成と格納）が終了すると、メモリコントローラ５はステップＳ３においてＹｅｓと判定し、コンピュータ２からのアクセス要求があるか、又は終了要求があるかを監視しつつ待機する（ステップＳ４，Ｓ７）。

コンピュータ２において、メモリ４に対して、ユーザデータの書き込み又は読み出しの必要が生じると、コンピュータ２は、アクセス要求を生成して、メモリカード３に送信する。コンピュータ２から送信されるアクセス要求には、先述のように、論理アドレスＬＢＡが含まれる。

待機状態において、アクセス要求（論理アドレスＬＢＡ）を受信すると、メモリコントローラ５はステップＳ４においてＹｅｓと判定し、演算器５０が物理アドレスＰＢＡを演算する（ステップＳ５）。

ステップＳ５の処理を以下に説明する。なお、以下の説明では、演算器５０が注目する第２ブロック５６の物理アドレスＲＡＤを「インデックスＩ」と称し、インデックスＩで指定される第２ブロック５６（注目する第２ブロック５６）から読み出された値を「ＲＤＶ（Ｉ）」と称する。また、複数の第２ブロック５６のうち、オフセットＯＦＦを求めるための第２ブロック５６を「ターゲットブロック」と称する。

式１を演算するためには、演算器５０はオフセットＯＦＦを決定する必要がある。演算器５０は、１つの論理アドレスＬＢＡに対して１つのターゲットブロックを決定することによりオフセットＯＦＦを演算により求める。言い換えれば、演算器５０は、論理アドレスＬＢＡに基づいて、コントローラメモリ５２に含まれる複数の第２ブロック５６からターゲットブロックを検索し、オフセットＯＦＦを求める。

まず、演算器５０は、インデックスＩをＲＡＤ０（＝０）にセットし、先頭の第２ブロック５６に注目して、式２を演算する。

すなわち、ＮＵＭの値は、現在のインデックスＩで特定される注目している第２ブロック５６に格納されている欠陥ブロック４２１の物理アドレスＰＢＡから、当該注目している第２ブロック５６の物理アドレスＲＡＤを減算した値となる。このＮＵＭは、先述のように、注目している第２ブロック５６に格納されている物理アドレスＰＢＡによって特定される欠陥ブロック４２１の前方に存在する正常ブロック４２０の個数を示す。

次に、演算器５０は、式３の真偽を判定する。

式３が「真」の場合は、インデックスＩ（物理アドレスＲＡＤ０）で指定される第２ブロック５６をターゲットブロックと決定する。

一方、式３が「偽」の場合において、複数の第２ブロック５６からターゲットブロックを検索する手法は、様々なバリエーションが考えられるが、本実施の形態では、２分探索法の一種を用いた例を説明する。

図１０は、ターゲットブロックを決定する処理を示す流れ図である。

まず、カウンタに「ｎ」にセット（ステップＳ１１）し、ターゲットブロックの候補として残っている第２ブロック５６のうちで、中央に位置する第２ブロック５６に注目するように、インデックスＩを更新する（ステップＳ１２）。

ここで、偶数個の第２ブロック５６が存在する場合、中央の第２ブロック５６とは、物理アドレスＲＡＤの値の大きい方する。例えば、物理アドレスＲＡＤ０乃至ＲＡＤ３で指定される４個の第２ブロック５６が候補として残っている場合、中央の第２ブロック５６は、物理アドレスＲＡＤ２で指定される第２ブロック５６とする。

インデックスＩを更新すると、カウンタの値をチェックする（ステップＳ１３）。

カウンタの値が「１」より大きければ（ステップＳ１３においてＹｅｓ）、演算器５０は、再び、式２を演算してから、式３の真偽を判定する（ステップＳ１４）。

式３の判定結果が「真」であれば（ステップＳ１４においてＹｅｓ）、インデックスＩで示される第２ブロック５６から後方の第２ブロック５６（インデックスＩで示される第２ブロック５６を含む）を、ターゲットブロックの候補から除外し（ステップＳ１５）、カウンタをデクリメントしてから（ステップＳ１６）、ステップＳ１２に戻る。

一方、式３の判定結果が「偽」であれば（ステップＳ１４においてＮｏ）、インデックスＩで示される第２ブロック５６から前方の第２ブロック５６（インデックスＩで示される第２ブロック５６を含む）を、ターゲットブロックの候補から除外し（ステップＳ１７）、カウンタをデクリメントしてから（ステップＳ１６）、ステップＳ１２に戻る。

このようにして、Ｍ（２ⁿ）個の第２ブロック５６が存在する場合、ターゲットブロックの候補から、不要な第２ブロック５６を除外する処理をｎ−１回繰り返せば、ターゲットブロックの候補は１つに絞られる。

ステップＳ１２乃至Ｓ１７が繰り返され、カウンタの値が「１」となると、ステップＳ１３においてＮｏと判定される。ここで、演算器５０は、再び、式２を演算してから、式３の真偽を判定する（ステップＳ１８）。

このステップＳ１８の判定は、変換先の第１ブロック４２が欠陥ブロック４２１であるか否かを判定することを意味する。

ステップＳ１８においてＮｏと判定すると、変換先の第１ブロック４２を１つ後方にずらすために、インデックスＩをインクリメントして（ステップＳ１９）、インデックスＩで指定される第２ブロック５６をターゲットブロックとする。

なお、詳細は説明しないが、第１ブロック４２が連続して欠陥ブロック４２１となっている場合、ステップＳ１２乃至Ｓ１７の処理において、その連続する欠陥ブロック４２１のうちの最後尾以外の欠陥ブロック４２１が変換先となる場合はない。したがって、最後尾の欠陥ブロック４２１の次の第１ブロック４２は必ず正常ブロック４２０であるから、ステップＳ１９においてインクリメントした先の第１ブロック４２が、再び欠陥ブロック４２１となることは、あり得ない。

一方、ステップＳ１８においてＹｅｓと判定すると、変換先は正常ブロック４２０であるから、インデックスＩをインクリメントすることなく、ステップＳ２０を実行する。

ステップＳ２０によりターゲットブロックが決定されると、演算器５０は、インデックスＩ（ターゲットブロックを指定する物理アドレスＲＡＤとなっている）をオフセットＯＦＦとし、式１を演算して、物理アドレスＰＢＡを得る。

図１１は、論理アドレスＬＢＡと物理アドレスＰＢＡとの対応を例示する図である。図１１では、図６に示すように欠陥ブロック４２１が存在している例について示す。ここまでに示したように、論理アドレスＬＢＡから物理アドレスＰＢＡが求められることにより、本実施の形態におけるコンピュータシステム１では、図１１に示される変換関係となる。

ここで、Ｎ＝３２、Ｍ＝２ⁿ＝２⁴＝１６であり、欠陥ブロック４２１が、図６に示すように存在している場合を例に、論理アドレスＬＢＡ５と、論理アドレスＬＢＡ１６とについて物理アドレスＰＢＡが求められる様子を示す。

まず、論理アドレスＬＢＡ５が与えられると、式３は「偽」となるので、図１０に示す２分探索法が実行され、カウンタにｎ（＝４）がセットされる。そして、２^4-1＋１＝９であるから、インデックスＩは中央の第２ブロック５６として９番目の第２ブロック５６を指定する「ＲＡＤ（２^4-1）」にセットされる。

物理アドレスＲＡＤ（２^4-1）（すなわち、物理アドレス８）には、ＮＯＵが格納されている。ここで、ＮＯＵは充分に大きい値であるから、式２によって得られるＮＵＭは充分に大きい値となり、ステップＳ１４において式３は「真」と判定される。したがって、物理アドレスＲＡＤ８より後方の第２ブロック５６は、ターゲットブロックの候補から除外され、カウンタの値が「３」にデクリメントされる。

次に、インデックスＩは、残った候補の中央の「ＲＡＤ４」にセットされる。このとき、カウンタは「３」となっているからステップＳ１３においてＹｅｓと判定される。

これにより、再びステップＳ１４が実行され、式２からＮＵＭ＝１６となる。今、与えられている論理アドレスは「ＬＢＡ５」であるから、ステップＳ１４における式３の判定結果は再び「真」となる。したがって、ステップＳ１５が実行されて、物理アドレスＲＡＤ４乃至ＲＡＤ７が候補から除外され、カウンタの値が「２」にデクリメントされる。

次に、インデックスＩは、残った候補の中央の「ＲＡＤ２」にセットされる。このとき、カウンタは「２」となっているからステップＳ１３においてＹｅｓと判定される。

これにより、再びステップＳ１４が実行され、式２からＮＵＭ＝５となり、ステップＳ１４における式３の判定結果は「偽」となる。したがって、ステップＳ１７が実行されて、物理アドレスＲＡＤ０乃至ＲＡＤ２が候補から除外され、カウンタの値が「１」にデクリメントされる。

次に、インデックスＩが「ＲＡＤ３」にセットされるが、このとき候補は、アドレスＲＡＤ３で指定される第２ブロック５６の１つに絞られており、カウンタの値は「１」であるからステップＳ１３においてＮｏと判定される。

ステップＳ１８が実行されると、式２からＮＵＭ＝１２となり、式３の判定結果は「真」となる。したがって、ステップＳ１９は実行されず、ステップＳ２０により、ターゲットブロックの物理アドレスは、物理アドレスＲＡＤ３であると決定され、オフセットＯＦＦは「３」となる。

したがって、式１により、５＋３＝８となり、論理アドレスＬＢＡ５は、物理アドレスＰＢＡ８に変換される。すなわち、論理アドレスＬＢＡ５によってアクセスされる第１ブロック４２は、物理アドレスＰＢＡ８で指定される第１ブロック４２であることがわかる。

同様にして論理アドレスＬＢＡ１６が与えられる場合を考察する。この場合も、式３は「偽」となるので、図１０に示す２分探索法が実行され、カウンタにｎ（＝４）がセットされる。そして、２^4-1＋１＝９であるから、インデックスＩは中央の第２ブロック５６として９番目の第２ブロック５６を指定する「ＲＡＤ（２^4-1）」にセットされる。

物理アドレスＲＡＤ（２^4-1）（すなわち、物理アドレス８）には、ＮＯＵが格納されている。ここで、ＮＯＵは充分に大きい値であるから、式２によって得られるＮＵＭは充分に大きい値となり、ステップＳ１４において式３は「真」と判定される。したがって、物理アドレスＲＡＤ８より後方の第２ブロック５６は、ターゲットブロックの候補から除外され、カウンタの値が「３」にデクリメントされる。

次に、インデックスＩは、残った候補の中央の「ＲＡＤ４」にセットされる。このとき、カウンタは「３」となっているからステップＳ１３においてＹｅｓと判定される。

これにより、再びステップＳ１４が実行され、式２からＮＵＭ＝１６となる。今、与えられている論理アドレスは「ＬＢＡ１６」であるから、ステップＳ１４における式３の判定結果は「偽」となる。したがって、ステップＳ１７が実行されて、物理アドレスＲＡＤ０乃至ＲＡＤ４が候補から除外され、カウンタの値が「２」にデクリメントされる。

次に、インデックスＩは、残った候補の中央の「ＲＡＤ６」にセットされる。このとき、カウンタは「２」となっているからステップＳ１３においてＹｅｓと判定される。

これにより、再びステップＳ１４が実行され、式２からＮＵＭ＝２１となり、ステップＳ１４における式３の判定結果は「真」となる。したがって、ステップＳ１５が実行されて、物理アドレスＲＡＤ６，ＲＡＤ７が候補から除外され、カウンタの値が「１」にデクリメントされる。

次に、インデックスＩが「ＲＡＤ５」にセットされる。このとき候補は、アドレスＲＡＤ５で指定される第２ブロック５６の１つに絞られており、カウンタの値は「１」であるからステップＳ１３においてＮｏと判定される。

ステップＳ１８が実行されると、式２からＮＵＭ＝１６となり、式３の判定結果は「偽」となる。したがって、ステップＳ１９が実行され、インデックスＩがインクリメントされることによって、インデックスＩは「物理アドレスＲＡＤ６」となる。そして、ステップＳ２０により、ターゲットブロックの物理アドレスは、物理アドレスＲＡＤ６であると決定され、オフセットＯＦＦは「６」となる。

したがって、式１により、１６＋６＝２２となり、論理アドレスＬＢＡ１６は、物理アドレスＰＢＡ２２に変換される。すなわち、論理アドレスＬＢＡ１６によってアクセスされる第１ブロック４２は、物理アドレスＰＢＡ２２で指定される第１ブロック４２であることがわかる。

このような２分探索法は、第２ブロック５６の数が比較的多い場合でも、高速に検索できるという利点がある。すなわち、２ｎ個の第２ブロック５６を、ｎ回程度の演算で検索できる。

図９に戻って、演算器５０により、受信した論理アドレスＬＢＡから物理アドレスＰＢＡが求まると、メモリコントローラ５は、求められた物理アドレスＰＢＡに基づいて、メモリ４にアクセスする（ステップＳ６）。

このとき、アクセス要求が書き込み処理である場合は、求めた物理アドレスＰＢＡで指定される第１ブロック４２にユーザデータを書き込むようにメモリ４を制御する。一方、アクセス要求が読み出し処理である場合は、求めた物理アドレスＰＢＡで指定される第１ブロック４２に格納されているユーザデータを読み出すようにメモリ４を制御する。読み出されたユーザデータは、インタフェース５３を介してコンピュータ２に転送される。

そして、ステップＳ６が終了すると、メモリコントローラ５は再び待機状態に戻る。なお、待機状態において、終了要求を受信すると、メモリコントローラ５はステップＳ７においてＹｅｓと判定し、処理を終了する。

以上のように、本実施の形態では、コントローラメモリ５２が複数の第１ブロック４２のうちの欠陥ブロック４２１の物理アドレスＰＢＡを個々に記憶するために設けられる複数の第２ブロック５６を備えており、演算器５０が論理アドレスＬＢＡと複数の第２ブロック５６に格納される情報（欠陥ブロック４２１の物理アドレスＰＢＡ）とに基づいて、論理アドレスＬＢＡに対応する物理アドレスＰＢＡを求める。

これにより、メモリ４やコントローラメモリ５２に、正常な第１ブロック４２の物理アドレスＰＢＡを記憶しておく必要がない。あるいは、全ての第１ブロック４２に関する特性（欠陥の有無）と、転送先の物理アドレスＰＢＡとを記憶する必要がない。すなわち、論理アドレスＬＢＡから物理アドレスＰＢＡに変換するために必要となる情報の容量を抑制できる。

特に、演算器５０は、論理アドレスＬＢＡを用いて、複数の第２ブロック５６からターゲットブロックを検索し、ターゲットブロックから読み出される欠陥ブロック４２１の第１物理アドレスと、ターゲットブロックの第２物理アドレスとに基づいて、ターゲットブロックから読み出された欠陥ブロックの第１物理アドレスより前方に存在する正常な第１ブロックの個数を求め、論理アドレスＬＢＡと個数とに基づいて、論理アドレスＬＢＡに対応する物理アドレスＰＢＡを求める。

これにより、論理アドレスＬＢＡに対応する物理アドレスＰＢＡを容易に求めることができる。

すなわち、論理アドレスＬＢＡを昇順に、欠陥ブロック４２１を飛ばしつつ、物理アドレスＰＢＡの昇順に割り当て（図１１に示す相関関係となる）、欠陥ブロック４２１として検出された第１ブロック４２の物理アドレスＰＢＡを、物理アドレスＰＢＡの順に、連続する第２ブロック５６に個々に格納しておくことにより、格納しておく情報の容量を抑制できる。

＜２． 第２の実施の形態＞
上記第１の実施の形態では、ターゲットブロックを検索する手法として２分探索法を紹介したが、もちろんこれに限定されるものではない。第２の実施の形態では、先頭から後方に向けて順次に探索する方法について説明する。

図１２は、第２の実施の形態におけるターゲットブロックの検索処理を示す流れ図である。

まず、演算器５０は、インデックスＩに「ＲＡＤ０（＝０）」をセットし（ステップＳ２１）、式２を演算してＮＵＭを求め、式３を判定する（ステップＳ２２）。

ステップＳ２２においてＮｏと判定すると、インデックスＩをインクリメントしてステップＳ２１に戻る。

一方、ステップＳ２２においてＹｅｓとすると、インデックスＩで指定される第２ブロックをターゲットブロックと決定し、当該インデックスＩの値をオフセットＯＦＦとして式１を演算し、物理アドレスＰＢＡを求める。

以上のように、第２の実施の形態に示す手法であっても、適切なターゲットブロックを決定できるので、適切な物理アドレスＰＢＡを求めることができる。なお、ここに示した手法は、演算が比較的容易であるという利点がある。

＜３． 変形例＞
以上、本発明の実施の形態について説明してきたが、本発明は上記実施の形態に限定されるものではなく様々な変形が可能である。

例えば、本実施の形態では、メモリ４及びメモリコントローラ５はメモリカード３を構成しており、コンピュータ２に対して着脱自在な構造であったが、メモリ４及びメモリコントローラ５がコンピュータ２内に組み込まれていてもよい。すなわち、コンピュータシステム１は、一体構造物として構成されていてもよい。

また、メモリ４のみが着脱自在な構造であってもよい。すなわち、コンピュータ２内に、メモリコントローラ５として機能する専用のデバイスコントローラを設け、メモリ４のみが内部のメモリスロットに着脱される構造でもよい。あるいは、ＣＰＵ２１及び記憶装置２２がメモリコントローラ５としての機能を備えていてもよい。

また、参照情報５５はメモリ４の予備記憶領域４１に存在していてもよい。すなわち、システム設計上、要求されるアクセス時間を満足することができるのであれば、予めコントローラメモリ５２に転送されなくてもよい。

本発明に係るコンピュータシステムを示す図である。 コンピュータの構成を示すブロック図である。 メモリカードの構成を示すブロック図である。 メモリの内部構造を示す概略図である。 メモリにおけるブロック（第１ブロック及び予備ブロック）の構造を示す図である。 ユーザ情報記憶領域を例示する図である。 図６に示すユーザ情報記憶領域に対する予備記憶領域を例示する図である。 図７に示す冗長情報がコントローラメモリに参照情報として記憶される状態を例示する図である。 主にメモリカード（メモリコントローラ）の動作を示す流れ図である。 ターゲットブロックを決定する処理を示す流れ図である。 論理アドレスＬＢＡと物理アドレスＰＢＡとの対応を例示する図である。 第２の実施の形態におけるターゲットブロックの検索処理を示す流れ図である。

符号の説明

１ コンピュータシステム
２ コンピュータ
２１ ＣＰＵ
２２ 記憶装置
３ メモリカード
４ メモリ
４０ ユーザ情報記憶領域
４１ 予備記憶領域
４２ 第１ブロック
４２０ 正常ブロック
４２１ 欠陥ブロック
４３ 予備ブロック
４４ 冗長情報
５ メモリコントローラ
５０ 演算器
５２ コントローラメモリ
５４ プログラム
５５ 参照情報
５６ 第２ブロック
１ 記憶素子

Claims (6)

1. メモリシステムであって、
   ユーザ情報を記憶するために設けられ、互いに重複しない第１物理アドレスが個々に割り当てられる複数の第１ブロックと、
   前記複数の第１ブロックのうちの欠陥ブロックの第１物理アドレスを個々に記憶するために設けられる複数の第２ブロックと、
   論理アドレスと前記複数の第２ブロックに格納される情報とに基づいて、前記論理アドレスに対応する第１物理アドレスを求める演算装置と、
   を備えることを特徴とするメモリシステム。
2. 前記複数の第２ブロックには、互いに重複しない第２物理アドレスが個々に割り当てられており、
   前記演算装置は、論理アドレスを用いて、前記複数の第２ブロックからターゲットブロックを検索し、前記ターゲットブロックから読み出される欠陥ブロックの第１物理アドレスと、前記ターゲットブロックの第２物理アドレスとに基づいて、前記ターゲットブロックから読み出された欠陥ブロックの第１物理アドレスより前方に存在する正常な第１ブロックの個数を求め、前記論理アドレスと前記個数とに基づいて、前記論理アドレスに対応する第１物理アドレスを求めることを特徴とするメモリシステム。
3. 請求項１または請求項２に記載のメモリシステムであって、
   前記複数の第２ブロックに記憶される複数の欠陥ブロックの第１物理アドレスは、前記第１物理アドレスの順に従って、前記第２物理アドレスの順で、前記複数の第２ブロックに格納されることを特徴とするメモリシステム。
4. 請求項１ないし請求項３のいずれかに記載のメモリシステムであって、
   前記複数の第１ブロックのうちの欠陥ブロックの第１物理アドレスを記憶する複数の予備ブロックと、
   前記複数の予備ブロックに記憶されている情報を前記複数の第２ブロックに転送する転送部と、
   をさらに備えることを特徴とするメモリシステム。
5. コンピュータシステムであって、
   必要に応じて論理アドレスを生成するコンピュータと、
   ユーザ情報を記憶するために設けられ、互いに重複しない第１物理アドレスが個々に割り当てられる複数の第１ブロックを有するメモリと、
   前記複数の第１ブロックのうちの欠陥ブロックの第１物理アドレスを個々に記憶するために設けられ、互いに重複しない第２物理アドレスが個々に割り当てられる複数の第２ブロックを有するコントローラメモリと、
   前記コンピュータから受信した論理アドレスを用いて、前記複数の第２ブロックからターゲットブロックを検索し、前記ターゲットブロックから読み出される欠陥ブロックの第１物理アドレスと、前記ターゲットブロックの第２物理アドレスとに基づいて、前記ターゲットブロックから読み出された欠陥ブロックの第１物理アドレスより前方に存在する正常な第１ブロックの個数を求め、前記論理アドレスと前記個数とに基づいて、前記論理アドレスに対応する第１物理アドレスを求める演算装置と、
   を備えることを特徴とするコンピュータシステム。
6. 論理アドレスから物理アドレスを得る演算装置から物理アドレスを用いてアクセスされるメモリであって、
   記憶素子群から構成され、互いに重複しない物理アドレスが割り当てられる複数のブロックを備え、
   前記複数のブロックは、
   ユーザ情報を記憶するために設けられる複数の第１ブロックと、
   前記複数の第１ブロックのうちの欠陥ブロックの物理アドレスを個々に記憶するために設けられる複数の第２ブロックと、
   を備え、
   前記複数の第２ブロックに記憶される複数の欠陥ブロックの物理アドレスは、前記物理アドレスの順に従って、前記複数の第２ブロックに割り当てられた物理アドレスの順に、前記複数の第２ブロックに格納されることを特徴とするメモリ。

Images