特許
J-GLOBAL ID：201303042274981736
メモリ装置内のデータ値の記憶アドレスを決定するための方法並びにアクセス装置
発明者：
,
,
出願人/特許権者：
代理人 (4件)：
浅村 皓
, 浅村 肇
, 林 鉐三
, 員見 正文
公報種別：特許公報
出願番号（国際出願番号）：特願2000-536013
特許番号：特許第4807686号
出願日： 1999年03月11日
請求項（抜粋）：
【請求項1】 複数のデータ値(D)が列アドレスA(X)と行アドレスB(X)に対応したメモリ位置Xに記憶されるようにしたメモリ装置(DRAM)内の所定のデータ値(D)の記憶アドレス(A(X),B(X))を決定するための方法であって、
前記メモリ位置Xはバイナリ・ツリーデータ構造のノードに対応し、当該バイナリ・ツリーデータ構造は、バイナリ・ツリー・ルートノード(RN)からなる最高位のツリーレベルから、複数のバイナリ・ツリー・リーフノード(LN)からなる最低位のツリーレベルに至る、データ値をともなった複数のノードからなり、ツリーレベルの各上位のノードとその次に低いツリーレベルにある2つの下位のノードは、当該下位の2つのノードのうちの1つのノードが前記上位のノードのデータ値に対して小さいデータ値を有し、当該下位の2つのノードのうちの他の1つのノードが前記上位のノードのデータ値に対して大きいデータ値を有しており、さらに、
前記バイナリ・ツリーデータ構造は、1又は2以上のツリーレベル(k=1、k=2、k=3)からなる所定のサブツリー深さKを有する複数のサブツリーとして論理的に構成され、各サブツリーは、ルートノードと、前記所定のサブツリー深さKに対応した中間ノードと、その次の下位のサブツリーのルートノードを構成する複数のリーフノードとを有し、
ある1つのサブツリーのルートノードと当該サブツリーの中間ノードと当該サブツリーのリーフノードのデータ値が前記メモリ装置(DRAM)の1つの行に対応し、それぞれのサブツリーのルートノードのデータ値は第1の列位置となるように、前記メモリ装置(DRAM)にデータ値(D)が記憶されて、前記メモリ装置(DRAM)の1つの行が1つのサブツリーの2K-1個のデータ値を含み、
a) 予め定められた現行の検索アドレス(A(X),B(X))のデータ値(D)を前記メモリ装置から読み出すステップと、
b) 読み出されたデータ値(D)が検索されるべきデータ値(I)より大きいかまたは小さいかを決定するために、前記読み出されたデータ値(D)を検索されるべき前記データ値(I)とを比較するステップと、
c1)前記ステップb)で実施された比較の回数が前記所定のサブツリー深さKに等しくない場合、データ値が検索されるべき次検索アドレス(A’,B’)の次列アドレスA(L(X)),A(R(X))を比較結果(C)と前記現行の列アドレスA(X)に基づいて計算する一方、次行アドレスB(L(X)),B(R(X))を現行の行アドレスB(X)のまま設定するステップと、
c2)前記ステップb)で実施された比較の回数が前記所定のサブツリー深さKに等しい場合、データ値に対して検索されるべき次検索アドレス(A’,B’)の次行アドレスB(L(X)),B(R(X))を比較結果(C)、前記現行の列アドレスA(X)、前記現行の行アドレスB(X)および前記レベルKの数に基づいて計算する一方、次列アドレスA(L(X)),A(R(X))を1に設定するステップとを含み、
d) 前記読み出しデータ値(D)が検索されるべき前記データ値(I)と予め定められた許容範囲(△D)内で一致するまで、ステップa)-c)が再帰的に実行される、前記方法。
IPC (3件)：
G06F 17/30 ( 200 6.01)
, G06F 12/00 ( 200 6.01)
, G06F 12/02 ( 200 6.01)
G06F 17/30 411
, G06F 17/30 150 A
, G06F 17/30 419 A
, G06F 12/00 520 A
, G06F 12/02 510 A
