JPS6318432A - 情報検索装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔発明の目的］ （産業上の利用分野） この発明は、２値化された検索情報の検索開始ビットに
最も近い一方のビット情報となっているビットの位置を
検索する情報検索装置に関する。

（従来の技術） 複数の“０′″、“１″により構成された検索情報にお
いて、検索方向に対して最初に“０°′、あるいは°“
１″となっているビットの位置を検出する方法としては
、検索情報を最下位ビットあるいは最−り位ビット方向
から順次１ビツトずつ検索して、゛０パ、１′°の判別
を行なう所謂シリアル検索方式が用いられている。

第６図は複数ビットから構成される検索情報をシリアル
検索方式により最下位ビット方向から検索して、最初に
“１゛°となっているビットの位置を検出し、そのビッ
ト位置をＢＣＤコードで表わず情報検索装置の構成を示
す図である。同図に示す情報検索装置は、Ｄ型フリップ
フロップ１０１で構成され検索情報が格納されるシフト
レジスタ１０３、Ｒ８型フリップフロップ１０５、ＡＮ
Ｄ回路１０７、カウンタ１０９を有している。

シフトレジスタ１０３は、検索情報のビット数と同数の
Ｄ型フリップフロップ１０１を直列に接続されて構成さ
れている。それぞれのＤ型フリップフロップ１０１には
、１ビツトの検索情報が格納されており、それぞれのク
ロック）さ子ＣＫにはアンド回路１０７の出力が供給さ
れている。シフトレジスタ１０３は、それぞれのＤ型フ
リップフロップ１０１のクロック端子ＧＫにクロックが
与えられる毎に、Ｄ型フリップフロップ１０１に格納さ
れた検索情報を１ビツトずつシフトさせて出力する・乙
のである。

Ｒ８型フリップフロップ１０５は、その人力Ｒにシフト
レジスタ１０３の出力が与えられており、入力Ｓに検索
Ｕ１１信号が与えられている。Ｒ８型フリップフロップ
１０５は、検索開始信号が“１″になると出力Ｑは１′
′となり、この状態において人力Ｒが“１°′になると
、Ｒ８型フリップフロップ１０５はリセットされて、出
力Ｑは“ＯＩＩとなる。

ＡＮＤ回路１０７は、その一方の入力にＲ８型フリップ
フロップ１０５の出力Ｑが与えられて、他方の入力には
シフトクロック信号ＳＣＫが与えられており、出力はそ
れぞれのＤ型フリップフロップ１０１のクロック端子Ｇ
Ｋに与えられている。

Ａ　Ｎ　Ｄ回路１０７は、Ｒ８型フリップフロップ１０
５の出力Ｑが１′°の時にシフトクロック信号ＳＣＫを
それぞれのＤ型フリップフロップ１０１のクロック端子
ＣＫに供給する。

カウンタ１０９は、そのクロック端子ＣＫにＡＮＤ回路
１０７を介してシフトクロック信号ＳＣＫが与えられて
おり、このシフトクロック信号ＳＣＫの数をカウントア
ツプして、その値をＢＣＤコードで出力するものである
。また、カウンタ１０９のリセット端子Ｒには検索開始
信号が与えられており、検索開始信号が１′′になると
、カウンタ１０９はリセットされてカウント）直をクリ
アする。

このような構成において、検索開始信号が“１″になる
と、Ｒ３型フリップフロップ１０５はリセットされて、
出力Ｑは“１パとなりこれがＡＮＤ回路１０７の一方の
入力に与えられる。さらに、カウンタ１０９もリセット
されてカウント値がクリアされ検索が開始される。

このような状態において、シフトクロック信号ＳＣＫが
ＡＮＤ回路１０７を介してシフトレジスタ１０３を構成
するそれぞれのＤ型フリップ７Ｏツブ１０１のクロック
端子ＧＫに供給される毎に、シフトレジスタ１０３に格
納された検索情報は、１ビツトずつシフトアウトされて
Ｒ８型フリップフロップ１０５の入力Ｒに供給される。

さらに、シフ１−クロック信号ＳＧＫは、カウンタ１０
９のクロック端子ＣＫに供給されて、シフトクロック信
号ＳＣＫの数がカウンタ１０９によりカウントアツプさ
れる。

このように、シフトクロック信号ＳＣＫに同期して検索
情報が１ビツトずつシフトされている状態にあって、シ
フトレジスタ１０３からシフトアウトしてＲ３型フリッ
プフロップ１０５の入力Ｒに供給されたビットが°゛０
″である場合は、Ｒ８型フリップフロップ１０５の出力
Ｑは“１°′の状態であり、シフトクロック信号ＳＣＫ
はＡＮＤ回路１０７を介してシフトレジスタ１０３及び
カウンタ１０９に供給される。

一方、シフトレジスタ１０３からシフトアウトしてＲ８
型フリップフロップ１０５の入力Ｒに供給されたビット
が１°′である場合には、Ｒ３型フリップフロップ１０
５の出力Ｑは“Ｏ″となり、これにより、ＡＮＤ回路１
０７の出力も０′°となり、シフトクロック信＠　Ｓ　
ＣＫはシフトレジスタ１０３及びカウンタ１０９に供給
されなくなる。

このため、シフトレジスタ１０３のシフト動作及びカウ
ンタ１０９のカウント動作は停止される。

したがって、カウント動作が停止するまでに、カウンタ
１０９によりカウントアツプされたシフトクロック信＠
ｓｃＫのカウント値が、検索情報の“１″となっている
ビットの位置を表わすことになる。

例えば、検索情報が４ビツト長で構成され３ビツト〜０
ビツトが“’ｏｉｏｏ”であり、２ビツト目が゛１′°
になっている場合には、シフトレジスタ１０３は４個の
Ｄ型フリップフロップ１０１で構成され、第７図に示す
如く、３つ目のシフトクロツタ信号ＳＣＫにより、検索
情報の２ビツト目のＩＩ　１　ＩＩがシフトレジスタ１
０３からシフトアウトして、Ｒ３型フリップフロップ１
０５の出力Ｑが０″となる。したがって、３つ目のシフ
トクロック信号ＳＣＫでシフト動作及びカウント動作が
停止して、カウンタの出力は’ｏｏｉｏ”となり、検索
情報の″１ｎとなっているビットの位置が検出される。

（発明が解決しようとする問題点） 以上説明したように、シリアル検索方式にあっては、検
索情報をクロック信号により１ビツトずつシフトさせて
、検索情報の最初に例えば１１Ｎとなっているビットを
シフトアウトさせるために要したクロック信号の数をカ
ウントすることにより、“１パとなっているビットの位
置を検出していた。

このように、検索情報を１ビツトずつシフトさせて検索
を行なうために、検索時間は検索しようとする例えば“
１”となっているビットの位置に依存していた。このた
め、検索時間は例えば最上位ビットにのみ１″がある検
索情報を最下位ビット方向から検索した時に最長となり
、検索情報が多数のビットで構成されている場合に、か
なりの検索時間がかかるという問題があった。

そこで、この発明は上記に鑑みてなされたものであり、
検索情報のビット数及び検索情報の内容に依存すること
なく検索処理を高速に行なうことがでさる情報検索装置
を提供することを目的とする。

［発明の構成］ （問題点を解決するための手段） 上記目的を達成するために、この発明の情報検索装置は
、複数の２値化されたビット情報で構成された検索情報
のそれぞれのビットを最下位ビット方向あるいは最上位
ビット方向から並行して検索を行ない、検索を開始した
ビットに最も近い一方のビット情報となっているビット
の位置を検出する検索手段と、前記一方のビット情報と
なっているビットの位置を最下位ビット目からの相対位
置としてＢＣＤコードに変換する変換手段とにより構成
される。

（作用） この発明の情報検索装置においては、検索情報のそれぞ
れのビットを最下位ビット方向あるいは最上位ビット方
向から並行して検索を行ない、検索を開始したビットに
最も近い一方のビット情報となっているビットの位置を
検出して、この位置を最下位ビット目からの相対位置と
してＢＣＤコードに変換する。

（実施例） 以下図面を用いてこの発明の一実施例を説明する。

第１図及び第２図はこの発明の一実施例に係る情報検索
装置を示す構成図であり、この情報検索装置は検索部と
変換部とから構成されており、第１図は検索部の構成を
示す図であり、第２図は変換部の構成を示す図である。

この実施例における情報検索装置は、１′′、１１０　
Ｉ＋で２値化され３２ビツトで構成された検索情報を、
最下位ビットあるいは最上位ビット方向から最初に°“
１″となっているビットの位置を検索して、この位置を
ＢＣＤコードに変換するものである。

第１図に示す検索部は、上述したように、２１直化され
た３２ビツトの検索情報を最下位ビットあるいは最上位
ビット方向から最初に“１″となっているビットの位置
を検索して、検索結果において他のビットをすべてＯ″
とする。例えば、３２ビツトの検索情報にあって、Ｏビ
ット目及び１ビツト目がｔｏ１１．２ビツト目が“°１
゛′となっている検索情報を最下位ビット方向から検索
した場合には、検索情報の３ビツト目から３１ビツト目
の値にかかわらず、検索結果は２ビツト目は１°′とな
り、他のビットはすべて“０″となる。

検索部は４つのブロックに分割されており、第１ブロツ
ク１、第２ブロツク３、第３ブロツク５、第４ブロツク
７から構成されている。各ブロックは最下位ビット方向
からの検索において、第１ブロツク１は３２ビツトの検
索情報のうちＯビット目〜７ビツト目の検索情報の検索
処理を行ない、第２ブロツク３は８ビット目〜１５ピッ
１−目、第３ブロツク５は１６ビツト目〜２３ビツト目
、第４ブロツク７は２４ビツト目〜３１ビツト目の検索
情報の検索処理を行なう。また、各ブロックは最上位ビ
ット方向からの検索において、第１ブロツク１は３１ビ
ツト目〜２４ビツト目、第２ブロツク３は２３ビツト目
〜１６ビツト目、第３ブロツク５は１５ビツト目〜８ビ
ツト目、第４ブロツク７は７ビツト目〜Ｏビツト目の検
索情報の検索処理を行なう。

第１ブロツク１は、パストランジスタ１１ａ〜１１ｈ　
、１３ａ　〜１３ｈ　、インバータ回路１５ａ〜１５ｈ
ＳＮＯＲ回路１７ａ　〜１７ｈ　、　ＯＲ回路１９とか
ら構成されている。

パストランジスタ１１ａ〜１１ｈ及びパストランジスタ
１３ａ〜１３ｈは、検索情報を情報検索装置に与えるパ
スライン２１とインバータ回路１５ａ〜１５ｈの入力端
子との間にそれぞれ接続されている。パストランジスタ
１１８〜１１ｈは、最下位ビット方向からの検索におい
て検索信号りによりパスライン２１からＯピット目〜７
ビツト目の検索情報をそれぞれにインバータ回路１５ａ
〜１５ｈの入力端子に供給するものである。パストラン
ジスタ１３ａ〜１３ｈは、最上位ビット方向からの検索
において検索信号〜１によりパスライン２１から３１ビ
ツト目〜２４ビツト目の検索情報をそれぞれのインバー
タ回路１５ａ〜１５ｈの入力端子に供給するものである
。

これらのパストランジスタ１１８〜１１ｈ、１３ａ〜１
３ｈは、例えば第３図に示すような回路で構成されてい
る。同図に示すパストランジスタは、お互いのソース端
子及びドレイン端子が接続されたＰチャンネルＭＯＳト
ランジスタ（以下ｒＰＭＯ８Ｊ　、！：呼ぶ）２３とＮ
チャンネルＭＯＳトランジスタ（以下ｒＮＭＯ８Ｊと呼
ぶ）２５と、インバータ回路２７とから構成されている
。パストランジスタ１１８〜１１ｈにあっては、ＮＭＯ
８２５のゲート端子に検索信号りが与えられており、Ｐ
ＭＯ３２３のゲート端子にインバータ回路２７を介して
検索信号りが与えられている。また、パストランジスタ
１３ａ〜１３ｈにあっては、ＮＭＯ８２５のゲート端子
に検索信Ｑ　Ｍが与えられており、ＰＭＯ３２３のゲー
ト端子にインバータ回路２７を介して検索信号Ｍが与え
られている。

このような回路構成においては、検索信号りあるいは検
索信号Ｍがハイレベル状態になると、ＰＭＯ８２３及び
ＮＭＯ８２５は導通状態となり、パスライン２１から検
索情報がそれぞれインバータ回路１５ａ〜１５ｈに与え
られる。したがって、パストランジスタ１１８〜１１ｈ
は、最下位ビット方向からの検索時に検索信号りがハイ
レベル状態となることにより導通状態となり、０ビツト
目〜７ビツト目の検索情報をインバータ回路１５ａ〜１
５ｈに供給する。また、パストランジスタ１３ａ〜１３
ｈは、最上位ビット方向からの検索時に検索信号Ｍがハ
イレベル状態となることにより導通状態となり、３１ビ
ツト目〜２４ビツト目の検索情報をインバータ回路１５
ａ〜１５ｈに供給する。

ＮＯＲ回路１７ａ〜１７ｈは、それぞれの入力にインバ
ータ回路１５ａ〜１５ｈの出力が各別に供給されている
とともに、ＮＯＲ回路１７ａ〜１７ｇの出力は、次段以
降のＮＯＲ回路１７ｂ〜１７ｈの入力に供給されている
。また、ＮＯＲ回路１７ａ〜１７ｈの入力には、ブロッ
ク毎の検索結果を他のブロックに伝達するブロック信号
が与えられており、第１ブロツクには、ロウレベル状態
のブロック信号が与えられている。

ＮＯＲ回路１７ａ〜１７ｈは、最下位ビット方向からの
検索においては、検索情報の０ビツト目〜７ビツト目の
検索結果を、それぞれ出力ＰＥＯ〜ＰＥ７に出力し、最
上位ビット方向からの検索においては、検索情報の３１
ビツト目〜２４ビツト目の検索結果を、それぞれ出力Ｐ
Ｅ０−ＰＥ７に出力する。

ＮＯＲ回路１７ａ〜１７ｈは、それぞれの入力に各別に
与えられる検索情報の０″、“１″の判別を行ない、パ
スライン２１から０”の検索情報が、インバータ回路を
介してＮＯＲ回路に与えられると、ＮＯＲ回路の出力は
Ｏ″となる。

また、“１′′の検索情報が与えられると、この検索情
報が与えられたＮＯＲ回路の前段すべてのＮＯＲ回路の
出力が°“０″の場合には、“１″の検雷情報が与えら
れたＮＯＲ回路の出力は１″となる。ざらに、ＮＯＲ回
路の出力は次段以降のＮＯＲ回路の入力に与えられてい
るために、出力が１′となったＮＯＲ回路の次段以降の
すべてのＮＯＲ回路の出力は°°０″となる。

例えば、最下位ビット方向からの検索において、検索情
報のＯビット目〜３ビット目が“０”であり、４ビツト
目が１゛′である場合には、“ＯＩｓであるＯビット目
〜３ビット目の検索情報は、検索情報のそれぞれのビッ
トに対応したＮＯＲ回路１７ａ〜１７ｄにそれぞれ対応
したインバータ回路１５ａ〜１５ｄを介して供給されて
、ＮＯＲ回路１７８〜１７ｄのそれぞれの出力ＰＥＯ〜
ＰＥ３は“０パとなる。

また、“１”である４ビツト目の検索情報は、インバー
タ回路１５ｅを介してＮＯＲ回路１７ｅに供給される。

このＮＯＲＯＲ回路１９入力には、このＮＯＲ回路１７
ｅの前段すべてのＮＯＲ回路１５ａ〜１５ｄの出力が与
えられているため、すなわち、ＮＯＲ回路１７ａ　〜１
７ｄの出力ＰＥＯ〜ＰＥ３が与えられているため、ＮＯ
Ｒ回路１７ｅの出力ＰＥ４は“１″となる。

さらに、ＮＯＲ回路１７ｅの１″となった出力ＰＥ４は
、このＮＯＲ回路１７ｅの次段以降、すなわち、ＮＯＲ
回路１７ｆ〜１７ｈの入力に与えられて、５ビツト目〜
７ビツト目の検索情報の値にかかわらず、ＮＯＲ回路１
７ｆ〜１７ｈの出力ＰＥ５〜ＰＥ７はすべて“０′°と
なる。

ＯＲ回路１９は、その入力にＮＯＲ回路１７ａ〜１７ｈ
の出力ＰＥＯ〜ＰＥ７が与えられているとともに、ブロ
ック信号が与えられている。このＯＲ回路１９は、第１
ブロツク１の検索結果を第２ブロツク３、第３ブロツク
５、第４ブロツク７に伝ｉＷするものである。すなわら
、第１ブロツク１において、ＮＯＲ回路１７ａ〜１７ｈ
の出力ＰＥＯ〜ＰＥ７のうら、少な（とも１つが１′′
である場合には、第２ブロツク３〜第４ブロツク７の検
索結果をすべて０″にする。

第２ブロツク３、第３ブロツク５、第４ブロツク７は、
第１ブロツク１と同様に構成されており、同一の様能を
有している。なお、第４ブロツクにおいてはＯＲ回路を
有していない。第２ブロツク３は、供給される検索情報
の検索結果を出力ＰＥ８〜ＰＥ１５に与え、第３ブロツ
ク５は、供給される検索情報の検索結果を出力ＰＥ１６
〜２３に与え、第４ブロツク７は、供給される検索情報
の検索結果を出力ＰＥ２４〜ＰＥ３１に与える。

第２ブロツク３に供給されるブロック信号は、第１ブロ
ツク１の検索結果を示すＯＲ回路１９の出力となり、第
３ブロツク５に供給されるブロック信号は、第１ブロツ
ク１のＯＲ回路１９の出力と第２ブロツク３のＯＲ回路
の出力とのＯＲ回路２３による論理和出力となり、第４
ブロツク７のブロック信号は、第１ブロツク１、第２ブ
ロツク３、第３ブロツク５のそれぞれのＯＲ回路の出力
のＯＲ回路２５による論理和出力となる。

例えば、第１ブロツク１の検索結果において、ＮＯＲ回
路１７ａ〜１７ｈの出力ＰＥＯ〜ＰＥ７に１°゛がある
と、ＯＲ回路１９の出力は“１″となり、これは、第２
ブロツク３のブロック信号となり、第２ブロツク３のす
べてのＮＯＲ回路に与えられる。また、ＯＲ回路１９の
“１゛出力は、ＯＲ回路２３．２５を介して第３ブロツ
ク５及び第４ブロツク７に与えられ、第３ブロツク５及
び第４ブロツク７のすべてのＮＯＲ回路に与えられる。

したがって、第２ブロツク３、第３ブロツク５、第４ブ
ロツク７のそれぞれの検索結果となるＮＯＲ回路）出力
ＰＥ８〜ＰＥ３１はすべｒ”ｏ”となる。

このように、第１ブロツク１の検索結果は、第２ブロツ
ク３〜第４ブロツク７に、第２ブロツク３の検索結果は
、第３ブロツク５、第４ブロツク７に、第３ブロツク５
の検索結果は第４ブロツク７に並列に伝逐されている。

したがって、例えば第１ブロツク１の検索結果に“１″
′がある場合には、第４ブロツク７の検索結果は、第２
１０ツク３及び第３ブロツク５の検索結果にかかわらず
ＩＩ　Ｏ１１となり、検索情報の処理が高速に行なわれ
ることになる。

ところで、検索情報をシリアル方式により処理した場合
の回路構成の一例を第４図に示ず、同図に示すシリアル
方式は、３２ビツトの検索情報の検索処理を行なうもの
であり、検索情報が前段の検索結果とＡＮＤ回路２７に
より論理積をとることにより検索処理が行なわれて、こ
の検索結果がＮＯＲ回路２９及びインバータ回路３１を
介して次段に供給されるようになっている。寸なわら、
最下位ビット方向からの検索にあっては、検索結果が下
位ビット方向から順次上位ビット方向へ伝達される。

したがって、例えば、３２ビツトで構成されＯビット目
〜３０ビット目が゛０パであり３１ビツト目だけが１１
１　ＩＴである検索情報を、最下位ビット方向から検索
処理を行なった場合に、３１ビツト目の出力ＰＥ３１が
“１゛°となるためには、３０個のＮＯＲ回路２９及び
３１個のインバータ回路３１の遅延時間が必要となる。

このため、シリアル方式においては高速な検索処理は困
難となる。

しかしながら、この実施例においては、検索情報をブロ
ック毎に並列処理することで、検索処理ばかなりｇｉ″
ａに行なわれる。

第１図に示した構成において、例えば、３２ビツトの検
索情報の○ビット目のみが“０°′で他のビットがすべ
て１′°の場合の最下位ビット方向からの検索処理は、
ＮＯＲ回路１７ａの出力ＰＥＯに°°０°゛が出力され
ＮＯＲ回路１７１）の出力ＰＥ１に“１″が出力された
後、ＮＯＲ回路１７ｃ〜ＮＯＲ回路１７ｈの出力ＰＥ２
〜ＰＥ７にパ０°゛が出力されるとともにＯＲ回路１９
の出力が°″１′′となり、次いで、第２ブロツク３の
ＰＥ８〜ＰＥ１５に“０″が出力されるとともにＯＲ回
路２３゜２５の出力が“１°°となり、第３ブロツク５
、第４ブロツク７の出力ＰＥ１６〜ＰＥ３１に“０″が
出力される。

このため、検索結果を得るための遅延時間は、ＮＯＲ回
路１７ａ−＋ＮＯＲ回路１７１）→ＮＯＲ回路１７ｃ〜
Ｎ０ＲＩ　７ｈ　、ＯＲ回路１９→第２ブｏｙり（７）
ＮＯＲ回路、ＯＲ回路２３．ＯＲ回路２５→第３ブロツ
ク５及び第４ブロツク７のＮＯＲ回路の合計５個の論理
回路弁となり、検索処理はかなり高速に行なわれること
になる。

また、この実施例にあっては、検索情報をブロック毎に
処理しているが、ブロックに分割せずに検索情報の検索
を行なう場合には、前段のＮＯＲ回路の出力が次段以舒
のすべてのＮＯＲ回路の入力に供給されるようになる。

このため、最終段のＮＯＲ回路の入力には、前段すべて
のＮＯＲ回路の出力ＰＥ０−ＰＥ３０が供給されて、最
終段のＮＯＲ回路は３２人力のＮＯＲ回路となる。

第６図は、多入力ＮＯＲ回路の一例を示ず構成図である
。このＮＯＲ回路は、ｎ個の入力と同数だけ直列に接続
されたＰＭＯ８３３と、ｎ個の並列に接続されたＮＭＯ
８３５とから構成されており、Ｐ　Ｍ　ＯＳとＮＭＯ８
とを用いたＮ　ＯＲ回路にあっては、通常用いられてい
る回路構成である。

このような構成にあって、出力○ＵＴを０″とする場合
に警よ、少なくともＮＭＯ８３５のうちの１つが導通状
態になればよいので、Ｉｆ　ＯＩＩ比出力比較的高速に
行なわれる。しかしながら、出力ＯＵＴを″１′°とす
る場合には、ｎ個のＰＭＯ８をすべて導通状態にしなけ
ればならないので、°゛１″１″出力ｎ比出力比べてか
なり遅れることになる。

したがって、多入力構成のＮＯＲ回路にあっては、高速
動作を行なうことは困難となる。ゆえに、第１図に示し
た検索部においては、多入力構成を避けるために、検索
情報をブロックに分割して検索することにより、ＮＯＲ
回路の入力を９人力程度に抑えて、１”出力の遅れを小
さくするように対策した。

第２図は変換部の構成を示す図であり、この変換部は、
ＯＲ回路３７ａ　〜３７ｊ　、３９ａ　〜３９ｅ　、Ｅ
ＸＯＲ（排他的論理和）回路４１ａ〜４１ｅ１パストラ
ンジスタ４３ａ〜４３ｅとを有しており、検索結果をＢ
ＣＤコードに変換するものである。

３２ビツトの検索情報の検索結果において、“１″とな
ってビット位置は、次式によりＢＣＤコードで表わされ
る。

ａ４２’　＋ａ３２３＋ａ２２２＋ａ　＋　　２’＋ａ
０２゜ ここで、ａ４．ａ３．ａ２．ａｌ、ａＯはそれぞれ１６
．８，４．２．１の重みを有している。例えば、検索結
果の３ビツト目が１゛である場合には、ａ４＝１１０ｕ
、ａ３＝１１０１Ｚａ２＝”Ｏ”、ａ１＝“１”、ａ　
ｏ　＝　”　１　”となり、検索結果はＢＣＤコードで
、“０００１１°′と表わされる。

ＯＲ回路３７ａ〜３７ｊは、その入力に検索部のＮＯＲ
回路の出力ＰＥＯ〜ＰＥ３１が供給されている。具体的
には、ＯＲ回路３７ａの入力にはＰＥＩ、ＰＥ９、ＰＥ
１７、ＰＥ２５が与えられており、ＯＲ回路３７ｂの入
力にはＰＥ２、ＰＥ１０、ＰＥ１８、ＰＥ２６、ＯＲ回
路３７Ｃの入力にはＰＥ３、ＰＥＩ　１、ＰＥ１９、Ｐ
Ｅ２７、ＯＲ回路３７ｄの入力にはＰＥ４、ＰＥ１２、
ＰＥ２０．ＰＥ２８、ＯＲ回路３７ｅの入力にはＰＥ５
、ＰＥ１３、ＰＥ２１、ＰＥ２９、ＯＲ回路３７ｆ）入
力１．：はＰＥ６、ＰＥ１４、ＰＥ２２、ＰＥ３０、Ｏ
Ｒ回路３７ａの入力にはＰＥ７、ＰＥ１５、ＰＥ２３、
ＰＥ３１が与えられている。

ＯＲ回路３７ｈの入力にはＰＥ８〜ＰＥ１５、ＯＲ回路
３７ｉの入力にはＰＥ１６〜ＰＥ２３、ＯＲ回路３７ｊ
の入力にはＰＥ２４〜ＰＥ３１が与えられている。

ＯＲ回路３９８〜３９ｅは、その入力にＯＲ回路３７ａ
〜３７ｊの出力が供給されている。具体的には、ＯＲ回
路３９ａの入力には、ＯＲ回路３７ａ　、３７ｃ　、３
７ｅ　、３７（＋の出力が与えられており、ＯＲ回路３
９ｂの入力には、ＯＲ回路３７ｂ　、３７ｃ　、３７ｒ
　、３７ｆＪの出力、ＯＲ回路３９ｃの入力には、ＯＲ
回路３７ｄ　、３７ｅ　、３７ｒ、３７ｇの出力、オア
回路３９ｄの入力には、オア回路３７ｈ、３７ｊの出力
、オア回路３９ｅの入力には、オア回路３７ｉ　、３７
ｊの出力が与えられている。

オア回路３９ａ〜３９ｅは、その出力に検索結果のＢＣ
Ｄコードが出力される。すなわち、オア回路３９ａの出
力には前述したＢＣＤコードのａｏが出力され、オア回
路３９ｂの出力にはａｌ、オア回路３９ｃの出力にはａ
２、オア回路３９ｄの出力にはａ３、オア回路３９ｅの
出力にはａ４が出力される。

Ｅ　Ｘ　ＯＲ回路４１ａ〜４１ｅは、それぞれの−方の
入力に検索信号Ｍが与えられている。ＥＸＯＲ回路４１
ａの他方の入力にはオア回路３９ａの出力が与えられて
おり、ＥＸＯＲ回路４１ｂの他方の入力にはオア回路３
９ｂの出力、ＥＸＯＲ回路４１Ｃの他方の入力にはオア
回路３９ｃの出力、ＥＸＯＲ回路４１ｄの他方の入力に
はオア回路３９ｄの出力、ＥＸＯＲ回路４１ｅの他方の
入力にはオア回路３９ｅの出力が与えられている。

ところで、検索情報が最上位ビット方向から検索される
場合には、検索情報の３１ビツト目の検索結果はＰＥＯ
に出力され、０ビツト目の検索結果はＰＥ３１に出力さ
れることになり、検索結果は、検索情報が最下位ビット
方向から検索される場合と逆になる。例えば、最上位ビ
ット方向からの検索にあって、検索情報の３１ビツト目
が１″である場合には、ＰＥＯは“１″、ＰＥ１〜ＰＥ
３０は０゛′となり、ａＯ〜ａ４はすべて０′。

となる。これは、検索情報のＯビット目が゛１パである
ことを表わしており、検索結果はＯビット目からの相対
位置を表わさないことになる。

そこで、検索情報の最上位ビット方向からの検索にあっ
ては、検索結果がＯビット目からの相対位置として表わ
されるように補正を行なう必要がある。

この補正は、検索情報の最上位ビット方向からの検索時
に、ＯＲ回路３９ａ〜３９ｅの出力であるａ　Ｑ　−”
ａ　４を反転することにより行なわれる。

上述したように、検索情報の３１ビツト目が１″である
場合には、ａＯ〜ａ４を反転してａＯ〜ａ４をすべて°
゛１″とすれば、検索結果のＢＣＤコードは、”　１１
１１　”となる。これは、１０進法で３１を表わしてお
り、検索結果は０ビツト目からの相対位置どして表わさ
れることになる。

ＥＸＯＲ回路４１ａ〜４１ｅは、検索情報の最上位ビッ
ト方向からの検索時に、上述したａＱ〜ａ４の反転動作
を行なうものである。最上位ビット方向からの検索時に
は、検索信号Ｍは１°°となるので、ＥＸＯＲ回路４１
ａ〜４１ｅは、ソノ出力に他方の入力すなわち、ａ　Ｑ
　％ａ　４の反転信号を出力することになる。また、最
下位ビット方向からの検索時には、検索信号Ｍは“０”
となるので、ＥＸＯＲ回路４１ａ　〜４１０（７）出力
ニハ、ａ□〜ａ４がそのまま出力される。

パストランジスタ４３ａ〜４３ｅは、前述した検索部の
パストランジスタ１１８〜１１ｈ、１３ａ〜１３ｈと同
様な構成であり、バス信号により検索結果のＢＣＤコー
ドであるａｏ−８４をパスライン４５に供給するもので
ある。

以上説明したように、この発明の実ｍ例は構成されてお
り、次にこの実施例の作用を説明する。

検索情報が最下位ビット方向から検索される場合には、
検索信号りが゛１ルベルとなることでパストランジスタ
１１８〜１１ｈが導通状態となり、検索情報のＯピット
目〜７ビツト目は、それぞれにパストランジスタ１１ａ
〜１１ｈ及びインバータ回路１５ａ〜１５ｈを介してＮ
ＯＲ回路１７８〜１７ｈに供給される。同様に、検索情
報の８ビツト目〜１５ビツト目は第２ブロツク３のＮＯ
Ｒ回路に、検索情報の１６ビツト目〜２３ビツト目は第
３ブロツク５のＮＯＲ回路に、検索情報の２４ビツト目
〜３１ビツト目は第４ブロツク７のＮＯＲ回路に供給さ
れる。

また、検索情報が最上位ビット方向から検索される場合
には、検索信号Ｍが“１″レベルとなることでパストラ
ンジスタ１３ａ〜１３ｈが導通状態となり、検索情報の
３１ビツト目〜２４ビツト目は、それぞれにパストラン
ジスタ１１ａ〜１１ｈ及びインバータ回路１５８〜１５
ｈを介してＮＯＲ回路１７ａ〜１７ｈに供給される。同
様に、検索情報の２３ビツト目〜１６ビツト目は第２ブ
ロツク３のＮＯＲ回路に、検索情報の１５ビツト目〜８
ビツト目は第３ブロツクのＮＯＲ回路に、検索情報の７
ビツト目〜０ビツト目は第４ブロツクのＮＯＲ回路に供
給される。

それぞれのＮＯＲ回路では、検索情報の°“Ｏ°′、″
１゛°の判定が行なわれて、検索情報が°０″であれば
ＮＯＲ回路の出力は０″となり、この出力が次段以降の
すべてのＮＯＲ回路の入力に供給される。

検索情報が１”であり、最下位ビット方向からの検索で
はこの検索情報よりも下位側の検索情報、また、最上位
ビット方向からの検索では１″となっている検索情報よ
りも上位側の検索情報がすべて′Ｏ°′の場合には、“
１″である検索情報が与えられたＮＯＲ回路の出力は１
″となり、この出力が次段以降のすべてのＮＯＲ回路の
入力に供給される。

第１ブロツク１の出力ＰＥ０−ＰＥ７のうち少なくとも
１つが“１″になると、ＯＲ回路１９の出力は“１″と
なり、第２ブロツク３のブロック信号は°°１″となる
。さらに、ＯＲ回路１９の°１”出力はＯＲ回路２３．
２５に供給されて、ＯＲ回路２３．２５の出力はともに
“１°°となり、第３ブロツク５及び第４ブロツク７の
ブロック信号は１′°となる。これにより、第２ブロツ
ク３、第３ブロツク５、第４ブロツク７のＮＯＲ回路の
出力ＰＥ８〜ＰＥ３１はすべてＯ１１となる。

同様にして、ＰＥＯ〜ＰＥ７がすべて○″であり、第２
ブロツク３の出力ＰＥ８〜ＰＥ１５のうち少なくとも１
つが“１″になると、第２ブロツク３のＯＲ回路の出力
が１”となり、ＯＲ回路２３．２５の出力は１″となる
。これにより、第３ブロツク５及び第４ブロツク７のブ
ロック信号は“１″となり、第３ブロツク５及び第４ブ
ロツク７のＮＯＲ回路の出力ＰＥ１６〜ＰＥ３１はすべ
て“ＯＩＩとなる。また、ＰＥ０−ＰＥ１５がすべて“
Ｏｎであり、ＰＥ１６〜ＰＥ２３のうち少なくとも１つ
が１′°になると、ＯＲ回路２５の出力は１″となり、
第４ブロツク７のＮＯＲ回路の出力はすべて“０″とな
る。

このようにして、３２ビツトの検索情報が最下位ビット
方向あるいは最上位ビット方向から検索されて、最初に
１″となっている検索情報のビットに対応したＮＯＲ回
路の出力が１′′となり、他のＮＯＲ回路の出力はすべ
て″０″となり、検索情報の検索結果がＰＥＯ〜ＰＥ３
１に出力される。

検索情報の検索結果がＮＯＲ回路の出力ＰＥＯ〜ＰＥ３
１に出力されると、これらの出力は変換部のＯＲ回路３
７ａ〜３７ｊに供給される。ＰＥ９〜ＰＥ１５７ｊＰＥ
０−ＰＥ７のいずれか１つが１″である場合には、ＯＲ
回路３７ａ〜３７ｇのいずれかの出力が１゛°となり、
ＯＲ回路３９ａ〜３９ｃのいずれか１つあるいは２つ以
上の出力が１”となる。ＰＥ８が１″である場合には、
ＯＲ回路３７ｈの出力が１”となり、これによりＯＲ回
路３９（ｌの出力が１１１　Ｉｔとなる。

さらに、ＰＥ９〜ＰＥ１５のいずれか１つが１″である
場合には、ＯＲ回路３７ａ〜３７ｇのいずれか１つの出
力及びＯＲ回路３７ｈの出力が“１″となりＯＲ回路３
９８〜３９ｃのいずれか１つあるいは２つ以上及びＯＲ
回路３９ｄの出力が１”′となる。ＰＥ１６が゛１″で
ある場合には、ＯＲ回路３７ｉの出力が１′°となり、
これによりＯＲ回路３９ｅの出力が°゛１″となる。さ
らに、ＰＥ１７〜ＰＥ２３のいずれか１つが“１″であ
る場合には、ＯＲ回路３７ａ〜３７ｏのいずれか１つの
出力及びＯＲ回路３７ｉの出力が１′°となり、ＯＲ回
路３９ａ〜３９ｃのいずれか１つあるいは２つ以上及び
ＯＲ回路３９ｅの出力が１゛となる。ＰＥ２４が“１°
゛である場合には、ＯＲ回路３７ｊの出力が“１゛とな
り、これによりＯＲ回路３９ｄ　、３９ｅの出力が１″
となる。さらに、ＰＥ２５〜Ｐ　Ｅ　３．１の出力が″
゛１１パ合には、ＯＲ回路３７８〜３７ｇのいずれか１
つの出力及びＯＲ回路３７ｊの出力が１１１１１となり
、ＯＲ回路３９ａ〜３９ｃのいずれか１つあるいは２つ
以上及びＯＲ回路３９ｄ　、３９ｅの出力が“１”°と
なる。

このように、“１″となったＰＥ０−ＰＥ３１に応じて
ＯＲ回路３９ａ〜３９ｅの出力が“１″となり、検索結
果のＢＣＤコードとなるａＯ〜ａ４の値がＯＲ回路３９
ａ〜３９ｅから出力される。

ＯＲ回路３９８〜３９ｅの出力は、それぞれＥＸＯＲ回
路４１ａ〜４１ｅに供給され、検索情報の最下位ビット
方向からの検索時には、検索信号Ｍは°“０°゛となり
、それぞれのＯＲ回路３９ａ〜３９ｅの出力は、各別に
ＥＸＯＲ回路４１ａ〜４１ｅ及びパストランジスタ４１
８〜４１ｅを介してパスライン４５に供給される。また
、検索情報の最上位ビット方向からの検索時には、検索
信号Ｍは１″となるために、それぞれのＯＲ回路３９８
〜３９ｅの出力は、各別にＥＸＯＲ回路４１ａ〜４１ｅ
により反転されてパストランジスタ４３３〜４３ｅを介
してパスライン４５に供給される。

このようにして、“Ｉ　Ｊｌとなっているビットの位置
は、Ｏビット目からの相対位置としてＢＣＤコードに変
換され、検索を開始して最初に“１′′となっているビ
ットの位置が検索されてＢＣＤコードで表わされる。

なお、この発明は上述した実施例のみに限ることなく、
適宜の変更を行なうことによりその他の態様で実施し得
るものである。

［発明の効果コ 以上説明したように、この発明によれば、検索情報のそ
れぞれのビットを最下位ビット方向あるいは最上位ビッ
ト方向から並行して検索を行ない、検索を開始したビッ
トに最も近い一方のビット情報となっているビットの位
置を検索するようにしたので、検索情報のビット数にか
かわらず、２値化された一方のビット情報の位置を高速
に検出することができる。

【図面の簡単な説明】

第１図はこの発明の一実施例に係る情報検索装置におけ
る検索部の構成ブロック図、第２図はこの発明の一実施
例に係る情報検索装置における変換部の構成ブロック図
、第３図はパストランジスタの一員体例を示す構成図、
第４図はシリアル検索方式の一例を示す構成図、第５図
は多入力Ｎ。 Ｒ回路の一例を示す構成図、第６図は情報検索装置の一
従来例を示す構成図、第７図は第６図のタイミングチャ
ートである。 （図の主要な部分を表わす符号の説明）１・・・第１ブ
ロツク ３・・・第２ブロック ５・・・第３ブロツク ７・・・第４ブロツク

Claims (1)

【特許請求の範囲】
1. 複数の２値化されたビット情報で構成された検索情報の
   それぞれのビットを最下位ビット方向あるいは最上位ビ
   ット方向から、並行して検索を行ない、検索を開始した
   ビットに最も近い一方のビット情報となつているビット
   の位置を検出する検索手段と、前記一方のビット情報と
   なっているビットの位置を最下位ビット目からの相対位
   置としてＢＣＤコードに変換する変換手段とを有するこ
   とを特徴とする情報検索装置。