JPH02144670A - 比較装置 - Google Patents
比較装置Info
- Publication number
- JPH02144670A JPH02144670A JP1260385A JP26038589A JPH02144670A JP H02144670 A JPH02144670 A JP H02144670A JP 1260385 A JP1260385 A JP 1260385A JP 26038589 A JP26038589 A JP 26038589A JP H02144670 A JPH02144670 A JP H02144670A
- Authority
- JP
- Japan
- Prior art keywords
- comparison
- bit
- output
- register
- gate
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/02—Comparing digital values
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/02—Indexing scheme relating to groups G06F7/02 - G06F7/026
- G06F2207/025—String search, i.e. pattern matching, e.g. find identical word or best match in a string
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Synchronisation In Digital Transmission Systems (AREA)
- Time-Division Multiplex Systems (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
Ａ、産業上の利用分野
本発明は、データ処理システムに関し、詳しくは、デー
タ処理システム内におけるデータ・ストリーム内の文字
列を位置決めし検出するための装置に関するものである
。
タ処理システム内におけるデータ・ストリーム内の文字
列を位置決めし検出するための装置に関するものである
。
Ｂ、従来技術
データ処理システムはデータにアクセスし、それを処理
する。データは２進値またはビットのグループとして処
理され、転送される。通常、特定の情報を表すには、指
定されたビット単位が使用される。たとえば、４ビツト
にプル）または８ビツト（バイト）が文字を表すのに使
用される。
する。データは２進値またはビットのグループとして処
理され、転送される。通常、特定の情報を表すには、指
定されたビット単位が使用される。たとえば、４ビツト
にプル）または８ビツト（バイト）が文字を表すのに使
用される。
これらの文字は、記憶装置と中央演算処理装置の間で連
続したビット・ストリームとして転送される。これらの
データ・ストリームを処理する際、データ・ストリーム
内の特定の文字を検出し位置決めすることが必要である
。
続したビット・ストリームとして転送される。これらの
データ・ストリームを処理する際、データ・ストリーム
内の特定の文字を検出し位置決めすることが必要である
。
従来技術では、米国特許第４１４５７５３号「可変長ワ
ード用比較装置（Ｃｏａ＋ｐａｒｉｎｇ Ａｐｐａｒａ
ｔｕｓｆｏｒ Ｖａｒｉａｂｌｅ Ｌｅｎｇｔｈ １Ｊ
ｏｒｄ） Ｊに、可変長ワードの比較を行なうため、最
上位桁または最下位桁が比較されるワード情報と位置合
せされるようにして、可変長ワード情報を比較するため
の回路が開示されている。米国特許第４６４６３２９号
「ディジタル伝送信号内に分散されたビットを有するフ
１／−ム位置合せワードの回復（Ｒｅｃｏｖｅｒｙ ｏ
ｆＦｒａｍｅ Ａｌｉｇｎｍｅｎｔ Ｗｏｒｄ ｆｌａ
ｙｉｎｇ Ｂｉｔｓ Ｄｉｓｔｒｉｂｕｔｅｄｉｎ ａ
Ｄｉｇｉｔａｌ Ｔｒａｎｓｍｉｓｓｉｏｎ Ｓｉｇ
ｎａｌ） Ｊには、ディジタル信号情報の循環比較を行
なうための手段が開示されている。米国特許第４６２５
２９５号「望みの文字列及び区切り文字を見つけるため
のテキスト比較システム（Ｔｅｘｔｕｒａｌ Ｃｏｍｐ
ａｒｉｓｏｎＳｙｓｔｅｍ ｆｏｒ Ｌｏｃａｔｉｏｎ
Ｄｅｓｉｒｅｄ Ｃｈａｒａｅｔ、ｅｒ Ｓｔｒｉｎ
ｇｓａｎｄ Ｄｅｌｉｍｉｔｅｒ Ｃｈａｒａｃｔｅｒ
ｓ） Ｊには、受信した文字列がいつ見つかったかを判
定するため、記憶されているテキスト文字の順次復号を
行なうシステムが開示されている。米国特許第４５５８
９５１号ｒ文字シーケンス処理のための命令をイする中
央処理装置（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｏｒ ｗ
ｉｔｈＩｎｓｔｒｕｃｔｉｏｎｓ ｆｏｒ Ｐｒｏｃｅ
ｓｓｉｎｇ ５ｅｑｕｅｎｃｅｓ ｏｆＣｈａｒａｃｔ
ｅｒｓ） 、、Ｉには、文字シーケンスを処理するよう
に適合されたデータ処理システムが開示されている。い
くつかの文字列命令のうちの１つが、中央演算処理Ｑ
Ｒがメモリから各文字を検索し、それを所定の特性と比
較することにより、このデータ処理システムで処理でき
る。米国特許第４２５１８６４号ｒデータ処理システム
において、信号グループ記憶スペースの境界と一致しな
い境界を有する信号グループを扱うための装置と手法（
Ａｐｐａｒａｔｕｓ ａｎｄ Ｍｅｔｈｏｄ ｉｎ ａ
Ｄａｔａ ＰｒｏｃｅｓｓｉｎｇＳｙｓｔｅｍ ｆｏ
ｒ Ｍａｎｉｐｕｌａｔｉｏｎ ｏｆ Ｓｉｇｎａｌ
ＧｒｏｕｐｓＨａｖｉｎｇ Ｂｏｕｎｄａｒｉｅｓ Ｈ
ｏｔ Ｃｏｉｎｃｉｄｉｎｇ ＷｉｔｈＢｏｕｎｄａｒ
ｉｅｓ ｏｆ Ｓｉｇｎａｌ Ｇｒｏｕｐ Ｓｔｏｒａ
ｇｅ ５ｐａｃｅ） Ｊには、境界ワード中の任意の位
置にオペランド境界を有するオペランドを扱うデータ処
理システムが開示されている。
ード用比較装置（Ｃｏａ＋ｐａｒｉｎｇ Ａｐｐａｒａ
ｔｕｓｆｏｒ Ｖａｒｉａｂｌｅ Ｌｅｎｇｔｈ １Ｊ
ｏｒｄ） Ｊに、可変長ワードの比較を行なうため、最
上位桁または最下位桁が比較されるワード情報と位置合
せされるようにして、可変長ワード情報を比較するため
の回路が開示されている。米国特許第４６４６３２９号
「ディジタル伝送信号内に分散されたビットを有するフ
１／−ム位置合せワードの回復（Ｒｅｃｏｖｅｒｙ ｏ
ｆＦｒａｍｅ Ａｌｉｇｎｍｅｎｔ Ｗｏｒｄ ｆｌａ
ｙｉｎｇ Ｂｉｔｓ Ｄｉｓｔｒｉｂｕｔｅｄｉｎ ａ
Ｄｉｇｉｔａｌ Ｔｒａｎｓｍｉｓｓｉｏｎ Ｓｉｇ
ｎａｌ） Ｊには、ディジタル信号情報の循環比較を行
なうための手段が開示されている。米国特許第４６２５
２９５号「望みの文字列及び区切り文字を見つけるため
のテキスト比較システム（Ｔｅｘｔｕｒａｌ Ｃｏｍｐ
ａｒｉｓｏｎＳｙｓｔｅｍ ｆｏｒ Ｌｏｃａｔｉｏｎ
Ｄｅｓｉｒｅｄ Ｃｈａｒａｅｔ、ｅｒ Ｓｔｒｉｎ
ｇｓａｎｄ Ｄｅｌｉｍｉｔｅｒ Ｃｈａｒａｃｔｅｒ
ｓ） Ｊには、受信した文字列がいつ見つかったかを判
定するため、記憶されているテキスト文字の順次復号を
行なうシステムが開示されている。米国特許第４５５８
９５１号ｒ文字シーケンス処理のための命令をイする中
央処理装置（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｏｒ ｗ
ｉｔｈＩｎｓｔｒｕｃｔｉｏｎｓ ｆｏｒ Ｐｒｏｃｅ
ｓｓｉｎｇ ５ｅｑｕｅｎｃｅｓ ｏｆＣｈａｒａｃｔ
ｅｒｓ） 、、Ｉには、文字シーケンスを処理するよう
に適合されたデータ処理システムが開示されている。い
くつかの文字列命令のうちの１つが、中央演算処理Ｑ
Ｒがメモリから各文字を検索し、それを所定の特性と比
較することにより、このデータ処理システムで処理でき
る。米国特許第４２５１８６４号ｒデータ処理システム
において、信号グループ記憶スペースの境界と一致しな
い境界を有する信号グループを扱うための装置と手法（
Ａｐｐａｒａｔｕｓ ａｎｄ Ｍｅｔｈｏｄ ｉｎ ａ
Ｄａｔａ ＰｒｏｃｅｓｓｉｎｇＳｙｓｔｅｍ ｆｏ
ｒ Ｍａｎｉｐｕｌａｔｉｏｎ ｏｆ Ｓｉｇｎａｌ
ＧｒｏｕｐｓＨａｖｉｎｇ Ｂｏｕｎｄａｒｉｅｓ Ｈ
ｏｔ Ｃｏｉｎｃｉｄｉｎｇ ＷｉｔｈＢｏｕｎｄａｒ
ｉｅｓ ｏｆ Ｓｉｇｎａｌ Ｇｒｏｕｐ Ｓｔｏｒａ
ｇｅ ５ｐａｃｅ） Ｊには、境界ワード中の任意の位
置にオペランド境界を有するオペランドを扱うデータ処
理システムが開示されている。
１８Ｍテクニカル・ディスクロージャ・プルテン、Ｖｏ
ｌ、２３、Ｎｏ、５ （１９８０年１０月）、ｐｌ）、
２０５ｆ〜２０５θ所載の論文「走査命令（Ｓｃａｎ
Ｉｎ５ｔｒｕｃｔｉｏｎ） Ｊには、１バイトずつ左か
ら右へ文字列を走査するための命令が開示されている。
ｌ、２３、Ｎｏ、５ （１９８０年１０月）、ｐｌ）、
２０５ｆ〜２０５θ所載の論文「走査命令（Ｓｃａｎ
Ｉｎ５ｔｒｕｃｔｉｏｎ） Ｊには、１バイトずつ左か
ら右へ文字列を走査するための命令が開示されている。
１８Ｍテクニカル・ディスクロージャ・プルテン、Ｖｏ
ｉ、２０、Ｎｏ、８ （１９７８年１月）に所載の論文
「可変長バイト文字列の比較及び転送命令（Ｖａｒｉａ
ｂｌｅ Ｌｅｎｇｔｈ ＢｙｔｅＳｔｒｉｎｇ Ｃｏｍ
ｐａｒｅ ａｒｉｄ Ｍｏｖｅ Ｉｎ５ｔｒｕｃｔｉｏ
ｎ） Ｊには１区切り文字または最初の非区切り文字を
探してコマンド文字列を走査するための命令が開示され
ている。
ｉ、２０、Ｎｏ、８ （１９７８年１月）に所載の論文
「可変長バイト文字列の比較及び転送命令（Ｖａｒｉａ
ｂｌｅ Ｌｅｎｇｔｈ ＢｙｔｅＳｔｒｉｎｇ Ｃｏｍ
ｐａｒｅ ａｒｉｄ Ｍｏｖｅ Ｉｎ５ｔｒｕｃｔｉｏ
ｎ） Ｊには１区切り文字または最初の非区切り文字を
探してコマンド文字列を走査するための命令が開示され
ている。
Ｃ１発明が解決しようとする問題点
上記の従来技術はすべて、データ・ス） Ｕ−ム内のコ
マンド゛文字列を位置決めするための機能について論じ
ている。しかし、上記従来技術のすべてで、この機能を
実行するのに複数のクロック・サイクルを必要とする技
術が開示されている。文字列を扱う短縮命令セット・コ
ンピュータ（ＲＩＳＣ）データ処理システムでは、デー
タ・ストリーム内の文字列をできるだけ速く検出し位置
決めすることが大切である。
マンド゛文字列を位置決めするための機能について論じ
ている。しかし、上記従来技術のすべてで、この機能を
実行するのに複数のクロック・サイクルを必要とする技
術が開示されている。文字列を扱う短縮命令セット・コ
ンピュータ（ＲＩＳＣ）データ処理システムでは、デー
タ・ストリーム内の文字列をできるだけ速く検出し位置
決めすることが大切である。
本発明の一目的は、単一のクロック・サイクル内の文字
列よりも多くの文字数を仔するデータ・ストリーム中ｉ
ご所定の文字列を検出することにある。
列よりも多くの文字数を仔するデータ・ストリーム中ｉ
ご所定の文字列を検出することにある。
本発明の別の目的は、検出された文字列の始めの実際の
ビット位置を指定する情報を提供することにある。
ビット位置を指定する情報を提供することにある。
Ｄ。問題点を解決するための手段
本発明によれば、クロックに接続された比較機構が、単
一クロック・サイクル内のＭビットのデータ・ストリー
ムにおけるＮビットのストリームを検出するために設け
られる。この比較機構は、Ｎビットの文字列を記憶する
ための第１レジスタ、Ｍビットのデー・夕・ストリーム
を記憶するための第２レジスタ、及び第１レジスタと第
２レジスタに接続される比較回路と、Ｎビットの文字列
を、Ｍビットのデータ・ストリーム内の幅Ｎビットの名
グループと同時に比較して、肯定比較標識を与えるため
のクロックを含む。本発明の別の態様は、さらにＭビッ
トのデータ・ストリーム内の比較されるＮビットの文字
列の第１ビツトの位置の標識を提供する能力も含んでい
る。
一クロック・サイクル内のＭビットのデータ・ストリー
ムにおけるＮビットのストリームを検出するために設け
られる。この比較機構は、Ｎビットの文字列を記憶する
ための第１レジスタ、Ｍビットのデー・夕・ストリーム
を記憶するための第２レジスタ、及び第１レジスタと第
２レジスタに接続される比較回路と、Ｎビットの文字列
を、Ｍビットのデータ・ストリーム内の幅Ｎビットの名
グループと同時に比較して、肯定比較標識を与えるため
のクロックを含む。本発明の別の態様は、さらにＭビッ
トのデータ・ストリーム内の比較されるＮビットの文字
列の第１ビツトの位置の標識を提供する能力も含んでい
る。
本発明の１つの実施例では、比較装置は、データ・スト
リームを記憶するためのシフト・レノスタとＮビットの
文字列を記憶するための第２レジスタを含む。これらの
両レジスタのビット出力部は、排他的ＯＲゲート論理回
路のアレイに接続されている。このアレイは、合致標識
信号を供給しまたシフト・レジスタに記憶されたデータ
・ストリーム中の文字列の第１ビツトの位置を示す複数
ビット信号を供給する、突合せ／位置決め論理回路に信
号出力を供給する。
リームを記憶するためのシフト・レノスタとＮビットの
文字列を記憶するための第２レジスタを含む。これらの
両レジスタのビット出力部は、排他的ＯＲゲート論理回
路のアレイに接続されている。このアレイは、合致標識
信号を供給しまたシフト・レジスタに記憶されたデータ
・ストリーム中の文字列の第１ビツトの位置を示す複数
ビット信号を供給する、突合せ／位置決め論理回路に信
号出力を供給する。
Ｅ、実施例
本発明は、データ・ストリーム内での特定の文字列の発
生を検出し位置決めするものである。第１図は、本発明
のブロック・ダイヤグラムである。
生を検出し位置決めするものである。第１図は、本発明
のブロック・ダイヤグラムである。
事前定義された文字列が線１０を介して比較文字レジス
タ１２に入れられる。データ・ストリームが線１６を介
して入力シフト・レジスタ１８に入力される。比較文字
レジスタｊ２の出力は、線１４を介して比較回路２２に
供給される。同様に、入力シフト・レジスタ１８の出力
は、線２０を介して比較回路２２に供給される。比較回
路の出力は、線２４を介して、突合せ７／位置決め論理
回路２６に供給される。突合せ／位置決め論理回路２６
は２種類の出力を供給する。線２８士の最初の出力は、
レジスタ１２に記憶されている文字列が実際に入力シフ
ト・レジスタ１８で検出されたかどうかを示φ−単一ビ
ットの標識である。また線３０」−の突合せ／位置決め
論理回路２６の２番目の出力は、入力シフト・レジスタ
１８内の比較される文字列の第１ビツトの実際の位置を
示す複数ビットの指定である３、クロック３２は、クロ
ック・サイクル信号を線４０を介し７て突合せ／位置決
め論理回路２６、比較文字レジスタ１２、大力シフト・
レジスタ１８及び制御回路３４に供給する。
タ１２に入れられる。データ・ストリームが線１６を介
して入力シフト・レジスタ１８に入力される。比較文字
レジスタｊ２の出力は、線１４を介して比較回路２２に
供給される。同様に、入力シフト・レジスタ１８の出力
は、線２０を介して比較回路２２に供給される。比較回
路の出力は、線２４を介して、突合せ７／位置決め論理
回路２６に供給される。突合せ／位置決め論理回路２６
は２種類の出力を供給する。線２８士の最初の出力は、
レジスタ１２に記憶されている文字列が実際に入力シフ
ト・レジスタ１８で検出されたかどうかを示φ−単一ビ
ットの標識である。また線３０」−の突合せ／位置決め
論理回路２６の２番目の出力は、入力シフト・レジスタ
１８内の比較される文字列の第１ビツトの実際の位置を
示す複数ビットの指定である３、クロック３２は、クロ
ック・サイクル信号を線４０を介し７て突合せ／位置決
め論理回路２６、比較文字レジスタ１２、大力シフト・
レジスタ１８及び制御回路３４に供給する。
第２図は、制御回路３４の動作を示すフロー・チャー・
トである。制御回路３４は、線４６を介して開始信号を
受は取り、線４２を介して入力シフト・レジスタ１８が
第１ビツト・グループを入力できるようにする使用可能
信号を供給する。好ましい実施例では、クロック・サイ
クル中に入力されるビットの数は、入力シフト・レジス
タ１８に記憶されるビットの数より少ない。したがって
、制御回路３４は、入力シフト・レジスタ１８内の特定
のビットが有効でないことを、突合せ／位置決め論理回
路２θに示さなくてはならない。この標畠は、線４４を
介して供給される。第２図で、ステップ２００で、制御
回路３４が線４６を介して開始信号を受は取る。この開
始信号は、命令の復号によって得られるもので、比較を
開始する。
トである。制御回路３４は、線４６を介して開始信号を
受は取り、線４２を介して入力シフト・レジスタ１８が
第１ビツト・グループを入力できるようにする使用可能
信号を供給する。好ましい実施例では、クロック・サイ
クル中に入力されるビットの数は、入力シフト・レジス
タ１８に記憶されるビットの数より少ない。したがって
、制御回路３４は、入力シフト・レジスタ１８内の特定
のビットが有効でないことを、突合せ／位置決め論理回
路２θに示さなくてはならない。この標畠は、線４４を
介して供給される。第２図で、ステップ２００で、制御
回路３４が線４６を介して開始信号を受は取る。この開
始信号は、命令の復号によって得られるもので、比較を
開始する。
ステップ２０２で、制御回路３４が、前述のように、線
４２及び４４を介して、第１ビツト・グループを入力し
、突合せ／位置決め論理回路２６内の適切なビット位置
に関する無効信号を供給するための信号を供給する。次
のクロック・サイクルで、制御回路は、ステップ２０４
に示すように線４４を介して在勤信号を送る。ステップ
２０５で、文字列の終わりに遭遇したかどうか判定する
ためのテストが行なわれる。遭遇していない場合には、
制〕回路３４がステップ２０４に戻る。遭遇した場合に
は、制御回路がステップ２００に戻り、次の開始信号を
待つ。
４２及び４４を介して、第１ビツト・グループを入力し
、突合せ／位置決め論理回路２６内の適切なビット位置
に関する無効信号を供給するための信号を供給する。次
のクロック・サイクルで、制御回路は、ステップ２０４
に示すように線４４を介して在勤信号を送る。ステップ
２０５で、文字列の終わりに遭遇したかどうか判定する
ためのテストが行なわれる。遭遇していない場合には、
制〕回路３４がステップ２０４に戻る。遭遇した場合に
は、制御回路がステップ２００に戻り、次の開始信号を
待つ。
第３図は、シフト・レジスタ１８と文字比較レジスタ１
２に接続されている比較論理回路２２の図である。この
例における比較文字は８ビツトで、データは８ビツト／
サイクルの速度で到着する。
２に接続されている比較論理回路２２の図である。この
例における比較文字は８ビツトで、データは８ビツト／
サイクルの速度で到着する。
入力シフト・レジスタ１８は１５ビツトの容量を要する
。動作の際には、ビット位置８ないし１４がビット位１
１０ないし６にシフトされ、着信ビット・ストリームが
単一クロック・サイクルでビット位置フないし１４に入
れられる。これらのビットは、レジスタ１８から線２０
を介して出力される。比較文字レジスタ１２は８ビツト
を含む。この８ビツトは、検出される文字を定義する。
。動作の際には、ビット位置８ないし１４がビット位１
１０ないし６にシフトされ、着信ビット・ストリームが
単一クロック・サイクルでビット位置フないし１４に入
れられる。これらのビットは、レジスタ１８から線２０
を介して出力される。比較文字レジスタ１２は８ビツト
を含む。この８ビツトは、検出される文字を定義する。
レジスタ１２の出力は、線１４を介して、比較論理回路
２２に供給される。比較論理回路２２は、υト他的０１
１’−トのアレイ６５を含む。このアレイは、５０ない
し５７行、５７ないし６４列を含む。各排他的ＯＲゲー
トは１つの出力を供給する。これらの出力を、列標ｍＡ
ないし１（で表し、行出力を数字Ｏないし７で表す。し
たがって、この図では、線２４上の比較論理回路２２か
らの出力線の数は、１２０出力信号となる。
２２に供給される。比較論理回路２２は、υト他的０１
１’−トのアレイ６５を含む。このアレイは、５０ない
し５７行、５７ないし６４列を含む。各排他的ＯＲゲー
トは１つの出力を供給する。これらの出力を、列標ｍＡ
ないし１（で表し、行出力を数字Ｏないし７で表す。し
たがって、この図では、線２４上の比較論理回路２２か
らの出力線の数は、１２０出力信号となる。
突合せ／位置決め論理回路２６を第３図及び第４図に示
す。第４図では、突合せ論理回路は一連のＯＲアゲ−７
０ないし７７を含むものとして示されている。ＯＲゲー
ト７０などの各ＯＲゲートは、比較論理回路２２内の排
他的ＯＲアレイの１列から出力を受は取る。ＯＲゲート
の出力は、刈入力線に関する論理的ＯＲである。ＯＲゲ
ート７０ないし７７の否定出力が線４４からの有効信号
とともにＡＮＤゲート３００ないし３０６に供給される
。ＡＮＤゲート３００ないし３０６の出力は、ＯＲゲー
ト７Ｂに入力される。ＯＲゲート７８は、ラッチ７９に
合致信号を出力し、ラフチア９は線２８上にラッチされ
た出力を供給する。線２８上の合致信号は、レジスタ１
２内の８ビツト文字列が、シフト・レジスタ１８の１５
ビツト内のどこかに置かれたことを示す単一ビット信号
である。
す。第４図では、突合せ論理回路は一連のＯＲアゲ−７
０ないし７７を含むものとして示されている。ＯＲゲー
ト７０などの各ＯＲゲートは、比較論理回路２２内の排
他的ＯＲアレイの１列から出力を受は取る。ＯＲゲート
の出力は、刈入力線に関する論理的ＯＲである。ＯＲゲ
ート７０ないし７７の否定出力が線４４からの有効信号
とともにＡＮＤゲート３００ないし３０６に供給される
。ＡＮＤゲート３００ないし３０６の出力は、ＯＲゲー
ト７Ｂに入力される。ＯＲゲート７８は、ラッチ７９に
合致信号を出力し、ラフチア９は線２８上にラッチされ
た出力を供給する。線２８上の合致信号は、レジスタ１
２内の８ビツト文字列が、シフト・レジスタ１８の１５
ビツト内のどこかに置かれたことを示す単一ビット信号
である。
第４図のＯＲゲート論理回路（特にＯＲゲート７０ない
し７７）は、第５図に示す位置決め論理回路への入力も
供給する。この実施例では、位置決め論理信号は、シフ
ト・レジスタ１８内のレジ表１ スタ１２の文字列の第１ビツトの位置を示す、３ビット
信号である。３ビツトの位置決め標識へのＯＲゲート７
０ないし７７の出力の実際の復号は第１表のとおりであ
る。３ビツトの出力は、ビットＸ、Ｙ、Ｚからなる。ビ
ットＸはラッチ３１４からの出力である。これは、ＯＲ
ゲート７０１７３．７６及び７１から入力を受は取るＡ
ＮＤゲート３１３からのクロックされた出力である。ビ
ットＹは、ラッチ３１６からの出力で、ＡＮＤゲート８
０、ＯＲゲート８１及びＡＮＤゲート８２からなる３つ
の論理段からのクロックされた出力である。ＡＮＤゲー
ト８０は、ＯＲゲート７４と７７から入力を受は取る。
し７７）は、第５図に示す位置決め論理回路への入力も
供給する。この実施例では、位置決め論理信号は、シフ
ト・レジスタ１８内のレジ表１ スタ１２の文字列の第１ビツトの位置を示す、３ビット
信号である。３ビツトの位置決め標識へのＯＲゲート７
０ないし７７の出力の実際の復号は第１表のとおりであ
る。３ビツトの出力は、ビットＸ、Ｙ、Ｚからなる。ビ
ットＸはラッチ３１４からの出力である。これは、ＯＲ
ゲート７０１７３．７６及び７１から入力を受は取るＡ
ＮＤゲート３１３からのクロックされた出力である。ビ
ットＹは、ラッチ３１６からの出力で、ＡＮＤゲート８
０、ＯＲゲート８１及びＡＮＤゲート８２からなる３つ
の論理段からのクロックされた出力である。ＡＮＤゲー
ト８０は、ＯＲゲート７４と７７から入力を受は取る。
ＡＮＤゲート８０の出力は、ＯＲゲート７６と７１の否
定出力とともにＯＲゲート８１に供給される。ＯＲゲー
ト８１の出力は、ＯＲゲート７０と７３の出力とともに
ＡＮＤゲート８２に供給される。Ｚビットはラッチ３１
８からの出力で、ＯＲアゲ−８３、ＡＮＤゲート８１１
、ＡＮＤゲート８５、ＯＲゲート８６及びＡＮＤゲート
８７からのクロックされた出力である。ＯＲゲート８３
は、ＯＲゲート７７の否定出力とＯＲゲート７２の出力
を受は取る。ＯＲゲート８３の出力は、ＯＲゲート７８
と７４の出力とともにＡＮＤゲート８４に供給される。
定出力とともにＯＲゲート８１に供給される。ＯＲゲー
ト８１の出力は、ＯＲゲート７０と７３の出力とともに
ＡＮＤゲート８２に供給される。Ｚビットはラッチ３１
８からの出力で、ＯＲアゲ−８３、ＡＮＤゲート８１１
、ＡＮＤゲート８５、ＯＲゲート８６及びＡＮＤゲート
８７からのクロックされた出力である。ＯＲゲート８３
は、ＯＲゲート７７の否定出力とＯＲゲート７２の出力
を受は取る。ＯＲゲート８３の出力は、ＯＲゲート７８
と７４の出力とともにＡＮＤゲート８４に供給される。
ＡＮＤゲート８５は、ＯＲゲート７６からの出力とＯＲ
ゲート７１からの否定出力を受は取る。ＡＮＤゲート８
４と８５の出力は、ＯＲゲート７３の否定出力とともに
ＯＲゲート８６に供給される。ＯＲゲート８６の出力は
、ＯＲゲート７０からの出力とともにＡＮＤゲート８７
に供給される。
ゲート７１からの否定出力を受は取る。ＡＮＤゲート８
４と８５の出力は、ＯＲゲート７３の否定出力とともに
ＯＲゲート８６に供給される。ＯＲゲート８６の出力は
、ＯＲゲート７０からの出力とともにＡＮＤゲート８７
に供給される。
本発明の動作を表す例について説明する。この例では、
比較文字１ｏｉｏｉｏｔｏが比較文字レジスタ１２に供
給される（第６図を参照）。ビット列１１００１０１０
１０−１０１１００が、８ビツト／クロツク・サイクル
の速度で大力シフト・レジスタ１８に供給される。第６
図は、最初のサイクルの後のレジスタ１８の内容を示す
。比較論理回路２２及び突合せ／位置決め論理回路２６
の出力は、合致が起こらなかったことを示す。この場合
、位置決め線３０上のどのデータも否定または無視され
る。
比較文字１ｏｉｏｉｏｔｏが比較文字レジスタ１２に供
給される（第６図を参照）。ビット列１１００１０１０
１０−１０１１００が、８ビツト／クロツク・サイクル
の速度で大力シフト・レジスタ１８に供給される。第６
図は、最初のサイクルの後のレジスタ１８の内容を示す
。比較論理回路２２及び突合せ／位置決め論理回路２６
の出力は、合致が起こらなかったことを示す。この場合
、位置決め線３０上のどのデータも否定または無視され
る。
第２サイクルでは、比較文字１０１０１０１０が比較文
字レジスタ１２に残っている。レジスタ１８のビット位
置８ないし１４がビット位ｒａＯないしθに左シフトさ
れ、着信ビット列の次の８ビツトが、レジスタ１８のビ
ット位置７ないし１４に入れられて、１００１０１０１
０１０１１００の値になる。このとき、ＯＲゲート７０
．７２ないし７７の出力は１となる（非合致を示す）。
字レジスタ１２に残っている。レジスタ１８のビット位
置８ないし１４がビット位ｒａＯないしθに左シフトさ
れ、着信ビット列の次の８ビツトが、レジスタ１８のビ
ット位置７ないし１４に入れられて、１００１０１０１
０１０１１００の値になる。このとき、ＯＲゲート７０
．７２ないし７７の出力は１となる（非合致を示す）。
ただし、ＯＲゲート７１の出力は、０で、合致が生じた
ことを示す。ＯＲゲート７１からの出力が０であるため
、ＸＹＺは０１１である（第１表を参照）。０１１は、
検出された文字列の最初のビット位置を表す。
ことを示す。ＯＲゲート７１からの出力が０であるため
、ＸＹＺは０１１である（第１表を参照）。０１１は、
検出された文字列の最初のビット位置を表す。
第８図は、検出すべき文字列の位置が必ずバイト境界上
に（るような本発明の実施例を示す。すなわち、バイト
が、レジスタ１１８に示されているように、ビット位置
０ないし７、もしくは８ないし１５のいずれかとなる。
に（るような本発明の実施例を示す。すなわち、バイト
が、レジスタ１１８に示されているように、ビット位置
０ないし７、もしくは８ないし１５のいずれかとなる。
前に説明した実施例ト同様に、８ビツトの比較文字は、
レジスタ１１２に記憶される。比較論理回路１２２は単
一行の排他的ＯＲゲートからなる。これは、２つのＯＲ
ゲート１２６Ａと１２６Ｂのどちらか一方に出力を供給
する。これらのＯＲゲー）１２６Ａ及び１２６Ｂの出力
は、合致が生じたことを示すだけでなく、合致の位置を
も明白に示す。したがって、文字列がビット境界上にき
たとき、第８図の実施例では、単一クロック・サイクル
内で特定の文字列の発生を検出する。
レジスタ１１２に記憶される。比較論理回路１２２は単
一行の排他的ＯＲゲートからなる。これは、２つのＯＲ
ゲート１２６Ａと１２６Ｂのどちらか一方に出力を供給
する。これらのＯＲゲー）１２６Ａ及び１２６Ｂの出力
は、合致が生じたことを示すだけでなく、合致の位置を
も明白に示す。したがって、文字列がビット境界上にき
たとき、第８図の実施例では、単一クロック・サイクル
内で特定の文字列の発生を検出する。
Ｆ１発明の詳細
な説明したように本発明ではＭビットのストリーム中の
すべてのＮビット・グループを同時に比較対象シーケン
スに比較するようにしているので、１クロツクで所望の
比較を終了することができる。
すべてのＮビット・グループを同時に比較対象シーケン
スに比較するようにしているので、１クロツクで所望の
比較を終了することができる。
第１図は、本発明のブロック・ダイヤグラムである。
第２図は、制御回路の動作を表すフロー・チャートであ
る。 第３図は、比較論理回路に接続されているシフト・レジ
スタと比較レジスタを示す概略図である。 第４図は、突合せ回路を示す図である。 第５図は、位置決め回路のブロック・ダイヤグラムであ
る。 第６図は、比較論理回路でデータ・ストリームを事前定
義された文字列と比較す、る例を示す図である。 第７図は、データ・ストリームと事前定義された文字列
との比較を示す最初の例の第２サイクルの図である。 第８図は、文字列がデータ・ストリーム内の特定の境界
上に発生するように指定されている第２の実施例を示す
図である。 出願人 インターナシＪナル・ビジネス・マシーンズ
やコーポレーシ「ン
る。 第３図は、比較論理回路に接続されているシフト・レジ
スタと比較レジスタを示す概略図である。 第４図は、突合せ回路を示す図である。 第５図は、位置決め回路のブロック・ダイヤグラムであ
る。 第６図は、比較論理回路でデータ・ストリームを事前定
義された文字列と比較す、る例を示す図である。 第７図は、データ・ストリームと事前定義された文字列
との比較を示す最初の例の第２サイクルの図である。 第８図は、文字列がデータ・ストリーム内の特定の境界
上に発生するように指定されている第２の実施例を示す
図である。 出願人 インターナシＪナル・ビジネス・マシーンズ
やコーポレーシ「ン
Claims (1)
- （１）クロックに接続された、単一クロック・サイクル
でＭビット・データ・ストリーム中のＮビット列を検出
する比較装置において、 前記Ｎビット列を記憶する第１レジスタ手段と、前記Ｍ
ビット・データ・ストリームを記憶する第２レジスタ手
段と、 前記第１レジスタ手段、前記第２レジスタ手段及び前記
クロックに接続された、前記Ｎビット列を前記Ｍビット
・データ・ストリーム内の各Ｎビット幅のグループと同
時に比較する比較手段とを有することを特徴とする比較
装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US25509788A | 1988-10-07 | 1988-10-07 | |
| US255097 | 1988-10-07 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH02144670A true JPH02144670A (ja) | 1990-06-04 |
Family
ID=22966830
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1260385A Pending JPH02144670A (ja) | 1988-10-07 | 1989-10-06 | 比較装置 |
Country Status (2)
| Country | Link |
|---|---|
| EP (1) | EP0363175A3 (ja) |
| JP (1) | JPH02144670A (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE4136960A1 (de) * | 1991-11-11 | 1993-05-13 | Univ Magdeburg Tech | Verfahren zum seriellen vergleich von elementen aus bitstroemen |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3298000A (en) * | 1963-10-31 | 1967-01-10 | Sperry Rand Corp | Character correlation system |
| EP0352279A4 (en) * | 1987-02-10 | 1991-10-30 | Davin Computer Corporation | Parallel string processor and method for a minicomputer |
-
1989
- 1989-10-04 EP EP19890310150 patent/EP0363175A3/en not_active Withdrawn
- 1989-10-06 JP JP1260385A patent/JPH02144670A/ja active Pending
Also Published As
| Publication number | Publication date |
|---|---|
| EP0363175A2 (en) | 1990-04-11 |
| EP0363175A3 (en) | 1991-11-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4550436A (en) | Parallel text matching methods and apparatus | |
| US4314356A (en) | High-speed term searcher | |
| US4053871A (en) | Method and system for the iterative and simultaneous comparison of data with a group of reference data items | |
| US4152762A (en) | Associative crosspoint processor system | |
| US5450605A (en) | Boundary markers for indicating the boundary of a variable length instruction to facilitate parallel processing of sequential instructions | |
| US4241402A (en) | Finite state automaton with multiple state types | |
| US5612693A (en) | Sliding window data compression using a toroidal bit shift register | |
| US5060143A (en) | System for string searching including parallel comparison of candidate data block-by-block | |
| JPS63500548A (ja) | ル−ルベ−スのデ−タ検索方法及び装置 | |
| JPS61210478A (ja) | ベクトル処理装置 | |
| JPH02144670A (ja) | 比較装置 | |
| US3422405A (en) | Digital computer having an indirect field length operation | |
| JP2880199B2 (ja) | 記号列検索方法および検索装置 | |
| US2925588A (en) | Memory reading system | |
| JPS63261421A (ja) | 文字列処理装置 | |
| Healy | A character-oriented context-addressed segment-sequential storage | |
| JPS63187334A (ja) | 文字列パタ−ンマツチング装置 | |
| US4350455A (en) | High speed basic and condensed tab racks | |
| JPS6373422A (ja) | 情報検索装置 | |
| JP2772124B2 (ja) | 辞書検索方式 | |
| JP2772125B2 (ja) | 辞書検索方式 | |
| JP2835065B2 (ja) | 文字列検索方法 | |
| JPH06202849A (ja) | 情報処理装置 | |
| JPH0664586B2 (ja) | 文字列照合方法 | |
| JPH0833812B2 (ja) | ソート処理装置 |