(57)【特許請求の範囲】
【請求項１】
複数のメモリバンクからなるメモリと、
検出パターンに基づいて、同時に読み出そうとする所望の複数データの並べ替え規則を判定する並べ替え判定手段と、
上記メモリに対するデータの書き込み／ 読み出しを制御するメモリ制御手段とを備え、
上記メモリ制御手段は、全データを上記複数バンクのメモリにデータを格納する際に、参照領域の大きさをＲｘ、メモリバンク数をｍ、参照データの数をｎとし、上記メモリバンク数ｍをｍ＝Ｒｘ／２として、上記並べ替え判定手段により判定された並べ替え規則に従って、同時に読み出したいデータの相対位置をｎ／２以下の２ｘ（ｘは正の整数）で割った余りが連続する（ｘ−１）種類あることを判定条件として格納パターンを決定し、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納する制御を行うことを特徴とするデータ格納装置。
【請求項２】
上記メモリ制御手段は、さらに、同時に読み出したいデータの相対位置をバンク数ｍで割った余りが、全ての上記同時に読み出したいデータで異なることを判定条件として格納パターンを決定し、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする請求項１記載のデータ格納装置。
【請求項３】
上記メモリ制御手段は、１次元配列のデータについて、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする請求項１記載のデータ格納装置。
【請求項４】
上記メモリ制御手段は、２次元配列のデータを、縦１次元又は横１次元のデータ群に分割し、分割したデータ群単位で上記メモリの各バンクへの格納順序を変えることを特徴とする請求項１記載のデータ格納装置。
【請求項５】
複数のメモリバンクからなるメモリに対するデータの書き込み／読み出しを制御するメモリ制御手段と、
検出パターンに基づいて、同時に読み出そうとする所望の複数データの並べ替え規則を判定する並べ替え判定手段とを備え、
上記メモリ制御手段は、全データを上記複数バンクのメモリにデータを格納する際に、参照領域の大きさをＲｘ、メモリバンク数をｍ、参照データの数をｎとし、上記メモリバンク数ｍをｍ＝Ｒｘ／２として、上記並べ替え判定手段により判定された並べ替え規則に従って、同時に読み出したいデータの相対位置をｎ／２以下の２ｘ（ｘは正の整数）で割った余りが連続する（ｘ−１）種類あることを判定条件として格納パターンを決定し、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納する制御を行うことを特徴とするデータ格納制御装置。
【請求項６】
上記メモリ制御手段は、さらに、同時に読み出したいデータの相対位置をバンク数ｍで割った余りが、全ての上記同時に読み出したいデータで異なることを判定条件として格納パターンを決定し、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする請求項５記載のデータ格納制御装置。
【請求項７】
上記メモリ制御手段は、１次元配列のデータについて、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする請求項５記載のデータ格納制御装置。
【請求項８】
上記メモリ制御手段は、２次元配列のデータを、縦１次元又は横１次元のデータ群に分割し、分割したデータ群単位で上記メモリの各バンクへの格納順序を変えることを特徴とする請求項５記載のデータ格納制御装置。
【請求項９】
複数バンクのメモリにデータを格納する際に、
参照領域の大きさをＲｘ、メモリバンク数をｍ、参照データの数をｎとし、上記メモリバンク数ｍをｍ＝Ｒｘ／２として、同時に読み出したいデータの相対位置をｎ／２以下の２ｘ（ｘは正の整数）で割った余りが連続する（ｘ−１）種類あることを判定条件として格納パターンを決定し、
上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とするデータ格納制御方法。
【請求項１０】
さらに、同時に読み出したいデータの相対位置をバンク数ｍで割った余りが、全ての上記同時に読み出したいデータで異なることを判定条件として格納パターンを決定し、
上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする請求項９記載のデータ格納制御方法。
【請求項１１】
１次元配列のデータについて、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする請求項９記載のデータ格納制御方法。
【請求項１２】
２次元配列のデータを、縦１次元又は横１次元のデータ群に分割し、分割したデータ群単位で上記メモリの各バンクへの格納順序を変えることを特徴とする請求項９記載のデータ格納制御方法。
【請求項１３】
全データから所望の複数データの同時読み出しできる状態にデータの並べ替えを行って複数のメモリバンクからなるメモリに格納するデータ格納制御をコンピュータにより実行するためのデータ格納制御プログラムであって、
複数バンクのメモリにデータを格納する際に、
参照領域の大きさをＲｘ、メモリバンク数をｍ、参照データの数をｎとし、上記メモリバンク数ｍをｍ＝Ｒｘ／２として、同時に読み出したいデータの相対位置をｎ／２以下の２ｘ（ｘは正の整数）で割った余りが連続する（ｘ−１）種類あることを判定条件として格納パターンを決定し、
上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納する
ことを特徴とするデータ格納制御プログラム。
【請求項１４】
さらに、同時に読み出したいデータの相対位置をバンク数ｍで割った余りが、全ての上記同時に読み出したいデータで異なることを判定条件として格納パターンを決定し、
上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする請求項１３記載のデータ格納制御プログラム。
【請求項１５】
１次元配列のデータについて、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする請求項１３記載のデータ格納制御プログラム。
【請求項１６】
２次元配列のデータを、縦１次元又は横１次元のデータ群に分割し、分割したデータ群単位で上記メモリの各バンクへの格納順序を変えることを特徴とする請求項１３記載のデータ格納制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のメモリバンクからなるメモリに全データを格納して、所望の複数データの同時読み出しを行うデータ格納装置、データ格納制御装置、データ格納制御方法及びデータ格納制御プログラムに関する。
【背景技術】
【０００２】
半導体メモリは、図１２に示すように、ワード線ＷＬとビット線ＢＬを指定してメモリセルＭＣをアクセスする構造となっており、活性化された１ワード線とビット線の交差する位置にあるメモリセルＭＣに格納されたデータが読み出される。
【０００３】
このような構造の半導体メモリでは、同じビット線を複数のワード線のデータが共有しているので、図１３のように、複数のワード線ＷＬ１，ＷＬ２を指定するとビット線に出てきたデータが壊れてしまうため、異なるワード線のデータには同時アクセスできない。
【０００４】
一方、独立したバンクからは同時にデータを読み出すことが可能であり、図１４に示すように、メモリを複数のバンクＢＫ１〜ＢＫｎに分け、それぞれのバンクに異なるアドレスを指定することで複数のワード線のデータに同時アクセスすることができるが、バンク内の異なるワード線のデータには同時アクセスできない。すなわち、同時に読み出すことが出来るのは各バンクから同一ワード線上に格納されたデータであり、同一バンクにおける異なるワード線上に格納されたデータは同時読みだし不可能である。
【０００５】
ここで、バンクとは、複数のワード線と複数のビット線からなるメモリにおいて選択されるワード・アドレスが単一であるメモリ単位をいう。
【０００６】
従来より、入力データに含まれる特定のデータ配列を認識することにより、例えば画像データのパターン認識等の処理が行われている。
【０００７】
例えば、数ライン画像データを蓄積でき画素単位で出力できるバッファメモリと、数ビット幅データを処理可のプロセッサエレメントの複数を含み複数プロセッサエレメントで同時並行してデータ処理ができるデータ処理器と、マッチング参照データと制御データを格納する制御情報メモリとを備え、データ処理器の各プロセッサエレメントが、バッファメモリが出力した画像データの中の、自己に宛てられた注目画素中心のマトリクスの画像データ群を、閾値を用いて２値化して該プロセッサエレメントが処理可能なシリアル配列のビット幅に区切った対象データに変換し、同形式で制御情報メモリにあった参照データと合致か判定することが行われている（例えば、特許文献１参照）。
【０００８】
【特許文献１】特開２００３−２０３２３６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ここで、画像データのパターン認識の例として、画像データの中からある文字やパターンを抽出する場合を考える。文字を抽出する方法には様々な方法が考えられるが、ここでは簡単な例として図１５に示すような「Ｔ」字パターンを検出するについて説明する。
【００１０】
画像データは半導体メモリに格納されているものとする。図１５に示した「Ｔ」字パターンを検出するには、１〜６の番号をふった６点のデータＤ１〜Ｄ６を半導体メモリＭＹから読み出し、読み出したデータＤ１とデータＤ２、データＤ３、データＤ５が黒で、データＤ４とデータＤ６が白であればそこに「Ｔ」字パターンが存在していると判定することができる。逆に、データＤ１とデータＤ２、データＤ３、データＤ５が白で、データＤ４とデータＤ６が黒であればそこに白抜きの「Ｔ」字パターンが存在していると判定することができる。
【００１１】
ここで、画像データ中のどこに所望の文字もしくはパターンが存在するか分からない場合は、図１６に示すように、目的の文字を抽出するために全画像データ上を走査、つまり半導体メモリから順次必要なデータを読み出す必要がある。
【００１２】
また、異なる文字を抽出する場合には同時に読み出し比較検討を行う画素データの組を変える必要がある。
【００１３】
このように、文字やパターンを抽出する際には、半導体メモリに格納されている画像データの中から目的に応じた複数のデータを同時に読み出す必要がある。
【００１４】
ところが、半導体メモリにおいては、同一バンク内の異なるワード線上に記録されたデータを同時に読み出すことが機構的に不可能である。
【００１５】
例えば図１７に示すように、同一バンク内の異なるワード線ＷＬ１，ＷＬ２上に必要とするデータＤ１〜Ｄ３とデータＤ４〜Ｄ６が格納されている場合には、必要とするデータＤ１〜Ｄ６を同時に読み出すことができない。
【００１６】
また、図１８の（Ａ），（Ｂ）に画像上のデータ配置とメモリ上のデータ配置を示すように、抽出しようとする文字やパターンが同じであっても参照領域の位置によっては半導体メモリから同時に読み出すことができない場合がある。
【００１７】
したがって従来では、同時読み出しを可能とするためメモリバンクを細かく分割する必要があった。例えば、図１９に示すように、参照領域の大きさが１０画素×１０画素であれば必要とするメモリバンクの数は１００になるが、バンクの数が多くなるとバンク・アドレス管理が難しくなり、アドレス線の増加やチップ面積が増加する、消費電力が増大するなどの問題があった。
【００１８】
なお、バッファやキャッシュなどを利用する方法もあるがチップ面積の増加、消費電力の増加が問題となる。
【００１９】
以上のような従来の問題を鑑み、本発明は、同時に読み出すべきデータの分布に応じてデータの格納方法を工夫することにより、バンク数を増やすことなくデータアクセスの衝突、すなわち、同一バンク内の異なるワード線を同時にアクセスすることを回避して、一次元ないし二次元に配置されたデータ群の中から、任意の位置にある複数のデータを同時に読み出すことを可能にしたデータ格納装置、データ格納制御装置、データ格納制御方法及びデータ格納制御プログラムを提供するものである。
【００２０】
本発明の更に他の目的、本発明によって得られる具体的な利点は、以下に説明される実施の形態の説明から一層明らかにされる。
【課題を解決するための手段】
【００２１】
本発明に係るデータ格納装置は、複数のメモリバンクからなるメモリと、検出パターンに基づいて、同時に読み出そうとする所望の複数データの並べ替え規則を判定する並べ替え判定手段と、上記メモリに対するデータの書き込み／ 読み出しを制御するメモリ制御手段とを備え、上記メモリ制御手段は、全データを上記複数バンクのメモリにデータを格納する際に、参照領域の大きさをＲｘ、メモリバンク数をｍ、参照データの数をｎとし、上記メモリバンク数ｍをｍ＝Ｒｘ／２として、上記並べ替え判定手段により判定された並べ替え規則に従って、同時に読み出したいデータの相対位置をｎ／２以下の２ｘ（ｘは正の整数）で割った余りが連続する（ｘ−１）種類あることを判定条件として格納パターンを決定し、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納する制御を行うことを特徴とする。
【００２２】
本発明に係るデータ格納制御装置は、複数のメモリバンクからなるメモリに対するデータの書き込み／ 読み出しを制御するメモリ制御手段と、検出パターンに基づいて、同時に読み出そうとする所望の複数データの並べ替え規則を判定する並べ替え判定手段とを備え、上記メモリ制御手段は、全データを上記複数バンクのメモリにデータを格納する際に、参照領域の大きさをＲｘ、メモリバンク数をｍ、参照データの数をｎとし、上記メモリバンク数ｍをｍ＝Ｒｘ／２として、上記並べ替え判定手段により判定された並べ替え規則に従って、同時に読み出したいデータの相対位置をｎ／２以下の２ｘ（ｘは正の整数）で割った余りが連続する（ｘ−１）種類あることを判定条件として格納パターンを決定し、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納する制御を行うことを特徴とする。
【００２３】
本発明に係るデータ格納制御方法は、複数バンクのメモリにデータを格納する際に、参照領域の大きさをＲｘ、メモリバンク数をｍ、参照データの数をｎとし、上記メモリバンク数ｍをｍ＝Ｒｘ／２として、同時に読み出したいデータの相対位置をｎ／２以下の２ｘ（ｘは正の整数）で割った余りが連続する（ｘ−１）種類あることを判定条件として格納パターンを決定し、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする。
【００２４】
本発明に係るデータ格納制御プログラムは、全データから所望の複数データの同時読み出しできる状態にデータの並べ替えを行って複数のメモリバンクからなるメモリに格納するデータ格納制御をコンピュータにより実行するためのデータ格納制御プログラムであって、複数バンクのメモリにデータを格納する際に、参照領域の大きさをＲｘ、メモリバンク数をｍ、参照データの数をｎとし、上記メモリバンク数ｍをｍ＝Ｒｘ／２として、同時に読み出したいデータの相対位置をｎ／２以下の２ｘ（ｘは正の整数）で割った余りが連続する（ｘ−１）種類あることを判定条件として格納パターンを決定し、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することを特徴とする。
【発明の効果】
【００２５】
本発明では、メモリバンク数を増やすことなくアクセスの衝突を回避することができる。
【００２６】
また、本発明では、メモリ容量を増やすことなくアクセスの衝突を回避することができる。
【発明を実施するための最良の形態】
【００２７】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。なお、本発明は以下の例に限定されるものではなく、本発明の要旨を逸脱しない範囲で、任意に変更可能であることは言うまでもない。
【００２８】
本発明は、例えば図１に示すような構成のデータ格納装置１００に適用される。
【００２９】
このデータ格納装置１００は、複数バンクの半導体メモリ１０と、この複数バンクの半導体メモリ１０に接続されたメモリ制御部２０と、このメモリ制御部２０に接続されたアドレス生成部３０、並べ替え判定部４０及びシャフリング・パターン格納部５０を備える。
【００３０】
このデータ格納装置１００では、画像データがメモリ制御部１０に供給されるととともに、上記画像データに含まれる検出対象のデータパターンを指定する検出パターンが上記メモリ制御部２０及び並べ替え判定部４０に供給される。
【００３１】
上記アドレス生成部３０は、画像上のアドレスに対応する論理アドレスを生成して上記メモリ制御部２０に供給する。
【００３２】
また、上記並べ替え判定部４０は、供給される検出パターンについてデータの並べ替え判定を行い、並べ替えルールをシャフリング・パターン格納部５０に与える。
【００３３】
さらに、上記シャフリング・パターン格納部５０は、上記並べ替え判定部２０により与えられる並べ替えルールに従って並べ替えパターンを上記メモリ制御部１０に供給する。
【００３４】
そして、上記メモリ制御部２０は、上記シャフリング・パターン格納部５０から供給される並べ替えパターンに応じて画像データを並べ替えて、上記半導体メモリ１０に画素データを書き込み、また、上記アドレス生成部３０により供給される論理アドレスを並べ替えパターンに応じて上記半導体メモリ１０の物理アドレスに変換することにより、上記半導体メモリ１０から複数データの同時に読み出す。
【００３５】
このデータ格納装置１００において、上記メモリ制御部２０は、上記シャフリング・パターン格納部５０から供給される並べ替えパターンに応じて、上記半導体メモリ１０から同時に読み出すべき複数の画素データの分布に応じて予め上記半導体メモリ１０への書き込み方法を変えることにより、上記半導体メモリ１０から複数データの同時読み出しを可能にする。
【００３６】
このデータ格納装置１００は、半導体メモリ１０から同時に読み出すべき複数の画素データの分布に応じて、予め上記半導体メモリ１０への書き込み方法を変えることにより、複数の画素データの同時読み出しを可能とするものであって、参照領域の位置にも依存することなく、複数の画素データを同時に読み出すことができる。
【００３７】
このデータ格納装置１００におけるデータの格納方法を説明する。
【００３８】
ここでは、分かりやすくするために画像データの配列を一次元とし、この1次元配列の中から複数の画素データを同時に読み出す場合について説明する。そのあとに2次元配列の場合について説明する。
【００３９】
図２及び図３は、参照領域ＲＥＦの大きさを「４」、同時に読み出す画素データの数を「２」、メモリのバンク数を「２」としたときのデータの格納方法を示したものである。
【００４０】
図２の（Ａ）に示すように２つの参照データＤＡ，ＤＢが横に並んでいる場合には、画像データを図２の（Ｂ）に示すバンク番号［１］，［２］の順に、すなわち、各バンクに交互に格納する。これにより、参照領域ＲＥＦの位置に拘わらず２つの参照データＤＡ，ＤＢは、常にそれぞれ異なるメモリバンクに格納されていることになるので、図２の（Ｂ）に示すように、２つの参照データＤＡ，ＤＢを同時に読み出すことができる。
【００４１】
また、図３の（Ａ）に示すように、２つの参照データＤＡ，ＤＢが1つ置きに並んでいる場合には、画像データを図３の（Ｂ）に示すバンク番号［１］，［１］，［２］，［２］の順に、すなわち、各バンク２回ずつ交互に格納する。こうすることによって２つの参照データＤＡ，ＤＢを同時読み出しが可能となる。また、図３の（Ｃ）に示すように、参照領域ＲＥＦが移動した場合にも同時読み出しが可能であるのは、図２の場合と同じである。
【００４２】
従来は、同様の読み出しを行おうとするとメモリバンクを４つ用意する必要があったが、本発明により、必要とするメモリバンクの数を２に削減することができる。
【００４３】
さらに、参照領域ＲＥＦの大きさを「８」、参照データの数を「３」、メモリバンク数を「４」とした場合のデータの格納方法を図４に示す。
【００４４】
この場合、参照データの分布に応じて適切なデータの格納方法があり、データの格納方法は、次の表１に示すように、格納パターンＡ、格納パターンＢそして格納パターンＣに対応する３通りの方法がある。また、参照領域ＲＥＦ内で参照データをローテーションしてもデータの格納方法には変わりがない。
【００４５】
【表１】
0004701620.tif 000002
【００４６】
すなわち、格納パターンＡでは、画像データをバンク番号［１］，［２］，［３］，［４］，［１］，［２］，［３］，［４］の順に各バンクに格納することによって４つの参照データを同時読み出しが可能となる。
【００４７】
また、格納パターンＢでは、画像データをバンク番号［１］，［２］，［１］，［２］，［３］，［４］，［３］，［４］の順に各バンクに格納することによって４つの参照データを同時読み出しが可能となる。
【００４８】
さらに、格納パターンＣでは、画像データをバンク番号［１］，［１］，［２］，［２］，［３］，［３］，［４］，［４］の順に各バンクに格納することによって４つの参照データを同時読み出しが可能となる。
【００４９】
そこで、このデータ格納装置１００において、上記メモリ制御部１０は、例えばマイクロプロセッサにて構成され、図示しないプロラムメモリに格納されたデータ格納制御プログラムに従って、図５のフローチャートに示す手順に従って、半導体メモリ１０へ画像データを格納する。
【００５０】
すなわち、上記メモリ制御部２０は、先ず、検出パターンを決定して（ステップＳ１）、第１の判定条件を満たすか否かを判定する（ステップＳ２）。
【００５１】
ここで、このステップＳ２における判定条件１の判定は、図６に模式的に示すように、次の手順１〜３に従って行われる。
【００５２】
手順１．参照データの分布を4等分して縦に並べる。
手順２．縦の一列に存在する参照データを計測する。
手順３．計測結果に基づいて参照データがどちらか一方にだけ存在しているか否かを判定する。
【００５３】
このステップＳ２における判定結果が正であれば、第１の格納ルールを採用して（ステップＳ３）、格納パターンＡで画像データを半導体メモリ１０に格納する（ステップＳ９）。
【００５４】
また、上記ステップＳ２における判定結果が偽であれば次の判定条件２で判定を行う（ステップＳ４）。
【００５５】
ここで、このステップＳ４における判定条件２の判定は、 図７に模式的に示すように、次の手順１〜３に従って行われる。
【００５６】
手順１．参照データの分布を２等分して縦に並べる。
手順２．縦の一列に存在する参照データを計測する。
手順３．計測結果に基づいて参照データが連続する２列にだけ存在しているかどうかを判定する。
【００５７】
このステップＳ４における判定結果が正であれば第１の格納ルールを採用して（ステップＳ５）、格納パターンＢで画像データを半導体メモリ１０に格納する（ステップＳ９）。
【００５８】
また、上記ステップＳ４におけるもし判定結果が偽であれば次の判定条件３で判定を行う（ステップＳ６）。
【００５９】
ここで、このステップＳ６における判定条件３の判定は、 図８に模式的に示すように、次の手順１〜３に従って行われる。
【００６０】
手順１．参照データの分布を2等分して縦に並べる。
手順２．縦の一列に存在する参照データを計測する。
手順３．計測結果に基づいて参照データが存在する数がいずれの列においても１以下であるか否かを判定する。
【００６１】
このステップＳ６における判定結果が正であれば、第３の格納ルールを採用して（ステップＳ７）、格納パターンＣでデータを格納する（ステップＳ９）。
【００６２】
また、上記ステップＳ６における判定結果が偽であれば、第４の格納ルールを採用して（ステップＳ８）、格納パターンＤでデータを格納する（ステップＳ９）。
【００６３】
そして、このデータ格納装置１００における上記半導体メモリ１０からの画像データの読み出しは、図９のフローチャートに示す手順に従って行われる。
【００６４】
すなわち、アドレス生成部３０により論理アドレス（画像上のアドレス）を生成し（ステップＳ１１）、メモリ制御部２０は、データ並べ替えルールに応じて上記論理アドレスを物理アドレス（メモリ上のアドレス）に変換して（ステップＳ１２）、半導体メモリ１０からデータ群を読み出し（ステップＳ１３）、画像の終わりまでデータを読み出したか否かを判定し（ステップＳ１４）、このステップＳ１４おける判定結果がＮＯ、すなわち、読み出すべきデータがある場合には、次の論理アドレスの生成を上記アドレス生成部３０に指示して（ステップＳ１５）、上記ステップＳ１１に戻ってデータの読み出しを繰り返し行い、上記ステップＳ１４おける判定結果がＹＥＳになると読み出し処理を終了する。
【００６５】
ここで、上記判定条件を数学的に書き換えると次のようになる。ここでは、参照領域における各参照データの相対位置を順にＡ１、Ａ２、・・・、Ａ８とする。
【００６６】
判定条件１：参照データの相対位置が全て偶数、もしくは奇数である場合。
この判定条件１は、相対位置を２で割った余り（Ａｉ  ｍｏｄ  ２）が全て０か、あるいは１である場合と定義することもできる。
判定条件２：全参照データの相対位置を４で割った余り（Ａｉ  ｍｏｄ  ４）が連続する２種ある場合。
この判定条件２は、具体的には０と１、もしくは１と２、あるいは２と３、３と０の場合である。
判定条件３：参照データの相対位置をバンク数ｍで割った余り（Ａｉ  ｍｏｄ  ｍ）が全ての参照データで異なる場合。
【００６７】
なお、判定領域の大きさの半分の数のバンク数ですみ、判定領域の大きさをＲｘとすると用意すべきメモリバンク数はｍ＝Ｒｘ／２となる。
【００６８】
これまでは同時に読み出すべきデータが１次元に並んでいる場合について説明してきたが、次に、同時に読み出すべきデータが２次元的に分布している場合のデータの格納方法について説明する。
【００６９】
図１０は、２次元的に分布しているデータの格納方法を模式的に示している。
【００７０】
すなわち、図１０の（Ａ）に示すように２次元的に分布している画像データＩＤは、図１０の（Ｂ）に示すように縦のストライプ状のデータ群に分割し、図１０の（Ｃ）に示すように１本のストライプに乗るデータ群をメモリバンクの１本のワード線に格納する。この際に、参照データの分布に応じてストライプ状のデータ群ごとに格納するメモリバンクを変えることにより、２次元的に分布しているデータの同時読み出しを可能にすることができる。
【００７１】
ここで、格納するメモリバンクを変えていく規則について図１１を使って説明する。
【００７２】
図１１の（Ａ）は、２次元の参照領域と参照データの分布例を示している。これを図１０と同様に、図１１の（Ｂ）に示すように縦のストライプに分割したものを想定し、このストライプを図１１の（Ｃ）に示すように縦方向に圧縮して、ストライプ上に参照データが１つでも存在すればフラグが立て、このフラグだけを見ると、先に１次元データ配列の場合と同じに取り扱うことができる。
【００７３】
すなわち、格納するメモリバンクを変える規則は、データ配列が１次元の場合に説明した規則と同じである。このように分割することで参照領域が縦方向に移動した場合にも所望の読み出しが可能となる。
【００７４】
つぎに、上記判定条件の一般例について説明する。
【００７５】
参照領域の大きさをＲｘとし、メモリバンク数をｍ、参照データの数をｎとすると、目標はｍ＝Ｒｘ／２であり、参照領域の大きさとその時の格納パターンは次の表２に示す通りとなる。取り得る格納パターンの数ｐは、ｐ＝ｌｏｇ２Ｒｘ（２を底とするＲｘの真数）である。
【００７６】
【表２】
0004701620.tif 000003
【００７７】
したがって、判定条件は、以下の通りとなる。  
判定条件１：参照データの相対位置が全て偶数、もしくは奇数である場合。（あるいは、相対位置を２で割った余り（Ａｉ  ｍｏｄ  ２）が全て０か、あるいは１である場合。）
判定条件２：全参照データの相対位置を４で割った余り（Ａｉ  ｍｏｄ  ４）が連続する２種ある場合。具体的には０と１、もしくは１と２、あるいは２と３、３と０の場合。
判定条件３：全参照データの相対位置を８で割った余り（Ａｉ  ｍｏｄ  ８）が連続する３種ある場合。
判定条件ｐ：割る数がｎ／２になるまで同様の操作を続け、「参照データ」の相対位置をバンク数ｍで割った余り（Ａｉ  ｍｏｄ  ｍ）が全ての参照データで異なる場合。
【００７８】
すなわち、全データを複数バンクのメモリにデータを格納する際に、参照領域の大きさをＲｘ、メモリバンク数をｍ、参照データの数をｎとし、上記メモリバンク数ｍをｍ＝Ｒｘ／２として、同時に読み出したいデータの相対位置をｎ／２ 以下の２ｘ（ｘは正の整数）で割った余りが連続する（ｘ−１）種類あることを判定条件として格納パターンを決定し、上記同時に読み出したいデータの分布に対応した格納パターンで上記メモリの各バンクへの格納順序を変えて、上記同時に読み出したいデータを異なるバンクに格納することによって、所望の複数データを同時に読み出すことが可能となる。
【００７９】
このデータ格納方法において、データの入れ替えにより参照データの同時読み出しを可能とする参照データ数の最大ｎ’は、ｎ’＝ｌｏｇ２ｍであることが数学的に証明できる。ｎ’がｌｏｇ２ｍ以下であればどのようなパターンであってもデータの入れ替えルールが存在し、同時に読み出すことを可能とするデータ格納方法が存在する。ｎ’がｌｏｇ２ｍを越えるとその分布によっては同時読み出しを可能とするデータ格納方法が存在する場合あるが、必ず存在するとは限らない。
【００８０】
以上説明した実施の形態では、画像データの中から文字やパターンを検出することを例にして本発明の説明を行ったが、同様の考え方はほかの分野に適用できることは明らかである。例えば、動きベクトル検出などにも応用できる。候補ベクトルの中から画素毎に最適なベクトルを選びだす際に適用できる。また、取り扱うデータが画像データは、画像データに限定されることなく、音声データなどであっても良い。
【図面の簡単な説明】
【００８１】
【図１】本発明を実施するデータ格納装置の構成を示すブロック図である。
【図２】参照領域の大きさを「４」、同時に読み出す画素データの数を「２」、メモリのバンク数を「２」としたときのデータの格納方法を参照データが横に並んでいる場合について模式的に示す図である。
【図３】参照領域の大きさを「４」、同時に読み出す画素データの数を「２」、メモリのバンク数を「２」としたときのデータの格納方法を２つの参照データが1つ置きに並んでいる場合について模式的に示す図である。
【図４】参照領域の大きさを「８」、参照データの数を「３」、メモリバンク数を「４」とした場合のデータの格納方法を模式的に示す図である。
【図５】上記データ格納装置におけるメモリへの画像データの格納処理の手順を示すフローチャートである。
【図６】上記画像データの格納処理における判定条件１の判定処理を模式的示す図である。
【図７】上記画像データの格納手順における判定条件２の判定処理を模式的示す図である。
【図８】上記画像データの格納手順における判定条件３の判定処理を模式的示す図である。
【図９】上記データ格納装置におけるメモリからの画像データの読み出し処理の手順を示すフローチャートである。
【図１０】２次元的に分布しているデータの格納方法を模式的に示す図である。
【図１１】格納するメモリバンクを変えていく規則を説明するための図である。
【図１２】一般的な半導体メモリの構造を模式的に示す図である。
【図１３】上記半導体メモリにおいて、同時アクセスできない状態を模式的に示す図である。
【図１４】複数メモリバンクのメモリ構成を示す図である。
【図１５】画像データのパターン認識の例として、画像データの中から検出する「Ｔ」字パターンを模式的に示す図である。
【図１６】画像データ中のどこに所望の文字もしくはパターンが存在するか分からない場合に、目的の文字を抽出するために全画像データ上を走査している状態を模式的に示す図である。
【図１７】半導体メモリにおいて、同時に読み出すことできない、同一バンク内の異なるワード線上にデータが格納された状態を模式的に示す図である。
【図１８】抽出しようとする文字やパターンが同じであっても参照領域の位置によっては半導体メモリから同時に読み出すことができない画像上のデータ配置とメモリ上のデータ配置を模式的に示す図である。
【図１９】メモリバンクの数を増やして同時アクセスを可能にした状態を模式的に示す図である。
【符号の説明】
【００８２】
１０  半導体メモリ、２０  メモリ制御部、３０  アドレス生成部、４０  並べ替え判定部、５０  シャフリング・パターン格納部、１００  データ格納装置
【図１】
0004701620.tif 000004
【図２】
0004701620.tif 000005
【図３】
0004701620.tif 000006
【図４】
0004701620.tif 000007
【図５】
0004701620.tif 000008
【図６】
0004701620.tif 000009
【図７】
0004701620.tif 000010
【図８】
0004701620.tif 000011
【図９】
0004701620.tif 000012
【図１０】
0004701620.tif 000013
【図１１】
0004701620.tif 000014
【図１２】
0004701620.tif 000015
【図１３】
0004701620.tif 000016
【図１４】
0004701620.tif 000017
【図１５】
0004701620.tif 000018
【図１６】
0004701620.tif 000019
【図１７】
0004701620.tif 000020
【図１８】
0004701620.tif 000021
【図１９】
0004701620.tif 000022