JPH05174582A - 連想メモリの優先度決定回路 - Google Patents
連想メモリの優先度決定回路Info
- Publication number
- JPH05174582A JPH05174582A JP4140801A JP14080192A JPH05174582A JP H05174582 A JPH05174582 A JP H05174582A JP 4140801 A JP4140801 A JP 4140801A JP 14080192 A JP14080192 A JP 14080192A JP H05174582 A JPH05174582 A JP H05174582A
- Authority
- JP
- Japan
- Prior art keywords
- signal
- circuit
- block
- signals
- match
- 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
- G11—INFORMATION STORAGE
- G11C—STATIC STORES
- G11C15/00—Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
- G11C15/04—Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores using semiconductor elements
Landscapes
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Logic Circuits (AREA)
Abstract
(57)【要約】
【目的】 この発明は連想メモリからの一致信号が得ら
れた場合に、この一致信号を所定の優先順位に従って順
次選択的に出力し、アドレスコードに変換するまでの時
間を短縮することができるような連想メモリに用いられ
る優先度決定回路を提供することを主要な特徴とする。 【構成】 各一致信号が直接それより優先順位の低い禁
止信号を一括して活性化するような下位サブ競合裁定回
路７１と、上位サブ競合裁定回路７２とを設け、一致信
号の上位半数のＭ１〜Ｍ４を昇順に配置し、下位半数を
降順Ｍ８〜Ｍ５にそれぞれ配置し、それに応じて下位サ
ブ競合裁定回路７１と上位サブ競合裁定回路７２とを三
角形と逆三角形とを組合わせた相補形の形状のパターン
で配置する。
れた場合に、この一致信号を所定の優先順位に従って順
次選択的に出力し、アドレスコードに変換するまでの時
間を短縮することができるような連想メモリに用いられ
る優先度決定回路を提供することを主要な特徴とする。 【構成】 各一致信号が直接それより優先順位の低い禁
止信号を一括して活性化するような下位サブ競合裁定回
路７１と、上位サブ競合裁定回路７２とを設け、一致信
号の上位半数のＭ１〜Ｍ４を昇順に配置し、下位半数を
降順Ｍ８〜Ｍ５にそれぞれ配置し、それに応じて下位サ
ブ競合裁定回路７１と上位サブ競合裁定回路７２とを三
角形と逆三角形とを組合わせた相補形の形状のパターン
で配置する。
Description
【０００１】
【産業上の利用分野】この発明は連想メモリの優先度決
定回路に関し、特に、連想メモリの格納データと外部か
ら与えられる検索データとの一致照合に応じて、その一
致した格納データのアドレスから出力される一致信号を
所定の優先順位に従って順次選択して出力し、この選択
して出力された一致信号を所定のアドレスコードに変換
するようなデータ処理回路に用いられる連想メモリの優
先度決定回路に関する。
定回路に関し、特に、連想メモリの格納データと外部か
ら与えられる検索データとの一致照合に応じて、その一
致した格納データのアドレスから出力される一致信号を
所定の優先順位に従って順次選択して出力し、この選択
して出力された一致信号を所定のアドレスコードに変換
するようなデータ処理回路に用いられる連想メモリの優
先度決定回路に関する。
【０００２】
【従来の技術】図３は連想メモリに格納されている所望
のデータを読出すための周辺回路部分を含む従来例を示
すブロック図である。図３を参照して、連想メモリ１は
ｎ個のワード（１ワードはビット）、つまりｎ×ｍビッ
トの記憶容量を有している。連想メモリ１に格納されて
いるデータを検索するために、連想メモリ１に対して外
部からｎビットのワード長を持つ検索データからラッチ
回路２を介して連想メモリ１に与えられる。この検索デ
ータは連想メモリ１内に格納されているｎ個のすべての
データと比較される。検索データと一致したデータが存
在すれば、その一致したデータが格納されているワード
位置に対応するアドレスから一致信号が出力され、この
一致信号がラッチ回路３を介して優先度決定回路４に与
えられる。
のデータを読出すための周辺回路部分を含む従来例を示
すブロック図である。図３を参照して、連想メモリ１は
ｎ個のワード（１ワードはビット）、つまりｎ×ｍビッ
トの記憶容量を有している。連想メモリ１に格納されて
いるデータを検索するために、連想メモリ１に対して外
部からｎビットのワード長を持つ検索データからラッチ
回路２を介して連想メモリ１に与えられる。この検索デ
ータは連想メモリ１内に格納されているｎ個のすべての
データと比較される。検索データと一致したデータが存
在すれば、その一致したデータが格納されているワード
位置に対応するアドレスから一致信号が出力され、この
一致信号がラッチ回路３を介して優先度決定回路４に与
えられる。
【０００３】連想メモリ１の特性上、連想メモリ１内に
は検索データと一致するデータが複数個存在する場合が
ある。そのときは、連想メモリ１から同時にそれぞれの
優先順位が異なるように定められた複数の一致信号が出
力される。これを同時並列的に処理するのは困難である
ため、優先度決定回路４はこれらの一致信号を所定の優
先度に従って１つずつ選択して出力する。
は検索データと一致するデータが複数個存在する場合が
ある。そのときは、連想メモリ１から同時にそれぞれの
優先順位が異なるように定められた複数の一致信号が出
力される。これを同時並列的に処理するのは困難である
ため、優先度決定回路４はこれらの一致信号を所定の優
先度に従って１つずつ選択して出力する。
【０００４】優先度決定回路４で選択された一致信号は
次段のエンコード回路５に与えられ、所定のアドレスコ
ード（たとえば２進数）に変換され、このアドレスコー
ドはデコード回路６に転送される。デコード回路６は、
アドレスコードをデコードして連想メモリ１に対して特
定の１つの読出用アドレスを与える。これにより、連想
メモリ１に格納されているデータの中から、検索データ
に一致するデータ（ｎビット）が出される。
次段のエンコード回路５に与えられ、所定のアドレスコ
ード（たとえば２進数）に変換され、このアドレスコー
ドはデコード回路６に転送される。デコード回路６は、
アドレスコードをデコードして連想メモリ１に対して特
定の１つの読出用アドレスを与える。これにより、連想
メモリ１に格納されているデータの中から、検索データ
に一致するデータ（ｎビット）が出される。
【０００５】図４は図３に示した優先度決定回路とエン
コード回路の具体的なブロック図である。図４を参照し
て、優先度決定回路４は競合裁定回路４１と信号選別回
路４２とを含む。競合裁定回路４１は図３に示したラッ
チ回路３から与えられる一致信号Ｍ１〜Ｍ８を受け（図
４に示した例ではワード数を８とする）、禁止信号／Ｉ
１〜／Ｉ８を出力する。
コード回路の具体的なブロック図である。図４を参照し
て、優先度決定回路４は競合裁定回路４１と信号選別回
路４２とを含む。競合裁定回路４１は図３に示したラッ
チ回路３から与えられる一致信号Ｍ１〜Ｍ８を受け（図
４に示した例ではワード数を８とする）、禁止信号／Ｉ
１〜／Ｉ８を出力する。
【０００６】競合裁定回路４１はＰチャネルＭＯＳトラ
ンジスタＰ１〜Ｐ８とＮチャネルＭＯＳトランジスタＮ
１〜Ｎ８を含む。ＰチャネルＭＯＳトランジスタＰ１〜
Ｐ８は直列接続され、それぞれのゲートに一致信号Ｍj
（１≦ｊ≦８）が入力され、ｐチャネルＭＯＳトランジ
スタＰ８のドレインにはブロック禁止信号／ＩＮＨが与
えられ、ＰチャネルＭＯＳトランジスタＰ１のソースか
らブロック一致信号／ＨＩＴが出力される。Ｐチャネル
ＭＯＳトランジスタＰ１〜Ｐ８のそれぞれのドレインは
信号選別回路４２に含まれるＡＮＤゲートＡＮＤ１〜８
のそれぞれの一方入力端に接続され、ＡＮＤゲートＡＮ
Ｄ１〜８の他方入力端には一致信号Ｍ１〜Ｍ８が与えら
れる。
ンジスタＰ１〜Ｐ８とＮチャネルＭＯＳトランジスタＮ
１〜Ｎ８を含む。ＰチャネルＭＯＳトランジスタＰ１〜
Ｐ８は直列接続され、それぞれのゲートに一致信号Ｍj
（１≦ｊ≦８）が入力され、ｐチャネルＭＯＳトランジ
スタＰ８のドレインにはブロック禁止信号／ＩＮＨが与
えられ、ＰチャネルＭＯＳトランジスタＰ１のソースか
らブロック一致信号／ＨＩＴが出力される。Ｐチャネル
ＭＯＳトランジスタＰ１〜Ｐ８のそれぞれのドレインは
信号選別回路４２に含まれるＡＮＤゲートＡＮＤ１〜８
のそれぞれの一方入力端に接続され、ＡＮＤゲートＡＮ
Ｄ１〜８の他方入力端には一致信号Ｍ１〜Ｍ８が与えら
れる。
【０００７】ブロック禁止信号／ＩＮＨは禁止信号／Ｉ
１〜／Ｉ８をすべて活性化する信号であり、Ｐチャネル
ＭＯＳトランジスタＰ８のドレインに与えられている。
ブロック一致信号／ＨＩＴは一致信号のうち、少なくと
も１つが活性状態であることを示す信号である。
１〜／Ｉ８をすべて活性化する信号であり、Ｐチャネル
ＭＯＳトランジスタＰ８のドレインに与えられている。
ブロック一致信号／ＨＩＴは一致信号のうち、少なくと
も１つが活性状態であることを示す信号である。
【０００８】図４に示した競合裁定回路４１において、
たとえば一致信号Ｍ４が活性化状態（“Ｈ”レベル）に
ある場合、ＮチャネルＭＯＳトランジスタＮ４が導通
し、それによってそれより優先順位が１つだけ低い禁止
信号／Ｉ３が活性化される。このため、たとえば一致信
号Ｍ３が“Ｈ”レベルになっても、ＡＮＤゲートＡＮＤ
３の出力は“Ｌ”レベルになる。一方、一致信号Ｍ４が
非活性状態（“Ｌ”レベル）にある場合、ＰチャネルＭ
ＯＳトランジスタＰ４が導通し、それによって自らの禁
止信号／Ｉ４をそれより優先順位が１つだけ低い禁止信
号／Ｉ３として伝搬する。一致信号Ｍ１が活性化状態に
ある場合、ＮチャネルＭＯＳトランジスタＮ１が導通
し、それによってブロック一致信号／ＨＩＴが“Ｌ”レ
ベルに活性化される。しかし、一致信号Ｍ１が非活性状
態にある場合、ＰチャネルＭＯＳトランジスタが導通
し、それにより禁止信号／Ｉ１がブロック一致信号／Ｈ
ＩＴとして伝搬する。このように、一致信号で下位の信
号が出力されるのをゲート回路で禁止して遅延時間を減
少する方法は、たとえばTeuvo Kohonen が発表した“Co
ntent-Addressable Memories”（Spriger Series in In
formation Sciences）やJon Patrick Wadeが発表したAn
integrated Content Addressable Memory Systemにお
いて知られている。
たとえば一致信号Ｍ４が活性化状態（“Ｈ”レベル）に
ある場合、ＮチャネルＭＯＳトランジスタＮ４が導通
し、それによってそれより優先順位が１つだけ低い禁止
信号／Ｉ３が活性化される。このため、たとえば一致信
号Ｍ３が“Ｈ”レベルになっても、ＡＮＤゲートＡＮＤ
３の出力は“Ｌ”レベルになる。一方、一致信号Ｍ４が
非活性状態（“Ｌ”レベル）にある場合、ＰチャネルＭ
ＯＳトランジスタＰ４が導通し、それによって自らの禁
止信号／Ｉ４をそれより優先順位が１つだけ低い禁止信
号／Ｉ３として伝搬する。一致信号Ｍ１が活性化状態に
ある場合、ＮチャネルＭＯＳトランジスタＮ１が導通
し、それによってブロック一致信号／ＨＩＴが“Ｌ”レ
ベルに活性化される。しかし、一致信号Ｍ１が非活性状
態にある場合、ＰチャネルＭＯＳトランジスタが導通
し、それにより禁止信号／Ｉ１がブロック一致信号／Ｈ
ＩＴとして伝搬する。このように、一致信号で下位の信
号が出力されるのをゲート回路で禁止して遅延時間を減
少する方法は、たとえばTeuvo Kohonen が発表した“Co
ntent-Addressable Memories”（Spriger Series in In
formation Sciences）やJon Patrick Wadeが発表したAn
integrated Content Addressable Memory Systemにお
いて知られている。
【０００９】信号選別回路４２は前述の禁止信号／Ｉ１
〜／Ｉ８を受け、裁定信号Ｔ１〜Ｔ８を出力する。この
信号選別回路４２は禁止信号／Ｉ１〜Ｉ８の状態によっ
て一致信号Ｍ１〜Ｍ８が裁定信号Ｔ１〜Ｔ８として出力
されるのを禁止または承認する。したがって、裁定信号
Ｔ１〜Ｔ８のうち活性状態にあるのは１つのみとなる。
〜／Ｉ８を受け、裁定信号Ｔ１〜Ｔ８を出力する。この
信号選別回路４２は禁止信号／Ｉ１〜Ｉ８の状態によっ
て一致信号Ｍ１〜Ｍ８が裁定信号Ｔ１〜Ｔ８として出力
されるのを禁止または承認する。したがって、裁定信号
Ｔ１〜Ｔ８のうち活性状態にあるのは１つのみとなる。
【００１０】エンコード回路５は３個の４入力ＮＯＲ回
路を含み、信号選別回路４２から出力される裁定信号Ｔ
１〜Ｔ８を受け、エンコード信号Ｆ０〜Ｆ２を出力す
る。エンコード回路５は連想メモリ１からの一致情報を
２進数のアドレスコードに変換するものであり、図４に
示した例では、ワード数が２3 であるので３ビット出力
が得られる。
路を含み、信号選別回路４２から出力される裁定信号Ｔ
１〜Ｔ８を受け、エンコード信号Ｆ０〜Ｆ２を出力す
る。エンコード回路５は連想メモリ１からの一致情報を
２進数のアドレスコードに変換するものであり、図４に
示した例では、ワード数が２3 であるので３ビット出力
が得られる。
【００１１】図５は符号化回路の他の例を示すブロック
図である。この図５に示した符号化回路４ａの競合裁定
回路４３はＯＲゲートＯＲ１〜ＯＲ８を用いて一致信号
Ｍ１〜Ｍ８を受け、禁止信号／Ｉ１〜Ｉ８を出力する。
すなわち、たとえば一致信号Ｍ４が“Ｈ”レベルに活性
化されると、ＯＲゲートＯＲ５の出力、すなわち禁止信
号／Ｉ３が“Ｌ”レベルになって、優先順位が１つだけ
低いＡＮＤゲートＡＮＤ３を閉じる。それによって、一
致信号Ｍ３が“Ｈ”レベルになっても、ＡＮＤゲートＡ
ＮＤ３から出力される裁定信号Ｔ３は“Ｌ”レベルにな
る。
図である。この図５に示した符号化回路４ａの競合裁定
回路４３はＯＲゲートＯＲ１〜ＯＲ８を用いて一致信号
Ｍ１〜Ｍ８を受け、禁止信号／Ｉ１〜Ｉ８を出力する。
すなわち、たとえば一致信号Ｍ４が“Ｈ”レベルに活性
化されると、ＯＲゲートＯＲ５の出力、すなわち禁止信
号／Ｉ３が“Ｌ”レベルになって、優先順位が１つだけ
低いＡＮＤゲートＡＮＤ３を閉じる。それによって、一
致信号Ｍ３が“Ｈ”レベルになっても、ＡＮＤゲートＡ
ＮＤ３から出力される裁定信号Ｔ３は“Ｌ”レベルにな
る。
【００１２】
【発明が解決しようとする課題】上述の図４に示した従
来の優先度決定回路４において、ブロック禁止信号／Ｉ
ＮＨは直列接続されたＰチャネルＭＯＳトランジスタＰ
８〜Ｐ１を介して伝搬していく。したがって、一致信号
Ｍj が優先度決定回路４１に与えられてから裁定信号Ｔ
１〜Ｔ８が適正値に落着くまでに時間を要する。すなわ
ち、図４に示した例において、一致信号Ｍ８が活性状態
で、他の一致信号Ｍ１〜Ｍ７がすべて非活性状態にある
場合、ブロック禁止信号／ＩＮＨがＰチャネルＭＯＳト
ランジスタＰ８から順次下位側に向けて順次伝搬してい
く必要があり、ブロック一致信号／ＨＩＴが活性化され
るまでには、ワード数をｎとすれば、１個のＮチャネル
ＭＯＳトランジスタとｎ−１個のＰチャネルＭＯＳトラ
ンジスタを、つまり図４に示した従来例によれば、１個
のＮチャネルＭＯＳトランジスタと７個のＰチャネルＭ
ＯＳトランジスタを通過しなければならない。連想メモ
リ１のワード数が少なければ、このような伝搬遅延があ
っても問題になることはなかった。しかしながら、連想
メモリの大容量化に伴い、伝搬遅延の時間が長くなるに
従って、優先順位を決定する時間が長くなってしまうと
いう問題点があった。
来の優先度決定回路４において、ブロック禁止信号／Ｉ
ＮＨは直列接続されたＰチャネルＭＯＳトランジスタＰ
８〜Ｐ１を介して伝搬していく。したがって、一致信号
Ｍj が優先度決定回路４１に与えられてから裁定信号Ｔ
１〜Ｔ８が適正値に落着くまでに時間を要する。すなわ
ち、図４に示した例において、一致信号Ｍ８が活性状態
で、他の一致信号Ｍ１〜Ｍ７がすべて非活性状態にある
場合、ブロック禁止信号／ＩＮＨがＰチャネルＭＯＳト
ランジスタＰ８から順次下位側に向けて順次伝搬してい
く必要があり、ブロック一致信号／ＨＩＴが活性化され
るまでには、ワード数をｎとすれば、１個のＮチャネル
ＭＯＳトランジスタとｎ−１個のＰチャネルＭＯＳトラ
ンジスタを、つまり図４に示した従来例によれば、１個
のＮチャネルＭＯＳトランジスタと７個のＰチャネルＭ
ＯＳトランジスタを通過しなければならない。連想メモ
リ１のワード数が少なければ、このような伝搬遅延があ
っても問題になることはなかった。しかしながら、連想
メモリの大容量化に伴い、伝搬遅延の時間が長くなるに
従って、優先順位を決定する時間が長くなってしまうと
いう問題点があった。
【００１３】それゆえに、この発明の主たる目的は、連
想メモリからの一致信号が得られた場合に、この一致信
号を所定のアドレスコードに変換するまでの時間を短縮
し得る連想メモリの優先度決定回路を提供することであ
る。
想メモリからの一致信号が得られた場合に、この一致信
号を所定のアドレスコードに変換するまでの時間を短縮
し得る連想メモリの優先度決定回路を提供することであ
る。
【００１４】
【課題を解決するための手段】請求項１に係る発明は、
連想メモリの格納データと外部から与えられた検索デー
タとの一致に応じて、その一致したデータが格納されて
いるワード位置に対応するアドレスから出力されるｎ個
の一致信号を所定の優先順位に従って順次選択して出力
する優先度決定回路であって、外部から与えられる検索
データと連想メモリにストアされている一致データとに
応じて、連想メモリから種々の優先順位の一致信号を受
ける手段と、連想メモリに格納されているデータと検索
データとの一致に応じて、優先順位の最も高いワード位
置を検出し、その優先順位の最も高いワード位置に対応
する一致信号を出力する検出手段と、検出手段の検出出
力に応じて、優先順位の低いすべてのワード位置に対応
する一致信号が出力されるのを同時に禁止する禁止手段
とを備えて構成される。
連想メモリの格納データと外部から与えられた検索デー
タとの一致に応じて、その一致したデータが格納されて
いるワード位置に対応するアドレスから出力されるｎ個
の一致信号を所定の優先順位に従って順次選択して出力
する優先度決定回路であって、外部から与えられる検索
データと連想メモリにストアされている一致データとに
応じて、連想メモリから種々の優先順位の一致信号を受
ける手段と、連想メモリに格納されているデータと検索
データとの一致に応じて、優先順位の最も高いワード位
置を検出し、その優先順位の最も高いワード位置に対応
する一致信号を出力する検出手段と、検出手段の検出出
力に応じて、優先順位の低いすべてのワード位置に対応
する一致信号が出力されるのを同時に禁止する禁止手段
とを備えて構成される。
【００１５】
【作用】この発明に係る連想メモリの優先度決定回路
は、連想メモリに格納されているデータと検索データと
の一致に応じて優先順位の最も高いワード位置を検出す
るとともに、そのワード位置に対応する一致信号を出力
し、それよりも優先順位の低いすべてのワード位置に対
応する一致信号が出力されるのを禁止することにより、
一致信号を所定のアドレスコードに変換するまでの時間
を従来よりも短縮することができる。
は、連想メモリに格納されているデータと検索データと
の一致に応じて優先順位の最も高いワード位置を検出す
るとともに、そのワード位置に対応する一致信号を出力
し、それよりも優先順位の低いすべてのワード位置に対
応する一致信号が出力されるのを禁止することにより、
一致信号を所定のアドレスコードに変換するまでの時間
を従来よりも短縮することができる。
【００１６】
【実施例】図１はこの発明の一実施例における優先度決
定回路の回路図である。なお、この図１に示した実施例
は、前述の図３に示した優先度決定回路４とエンコード
回路５とに代えて用いられる。連想メモリ１は８ワード
の記憶容量を有するものとする。図１を参照して、優先
度決定回路７はｎ個の一致信号を優先順位の高い上位半
数ｎ／２＋１からｎ（この例ではＭ５〜Ｍ８）と、それ
より優先順位の低い下位半数１〜ｎ／２（この例ではＭ
１〜Ｍ４）の２つのサブグループに分割され、上位半数
は上位サブ競合裁定回路７１によって裁定され、下位半
数は下位サブ競合裁定回路７２によって選定される。
定回路の回路図である。なお、この図１に示した実施例
は、前述の図３に示した優先度決定回路４とエンコード
回路５とに代えて用いられる。連想メモリ１は８ワード
の記憶容量を有するものとする。図１を参照して、優先
度決定回路７はｎ個の一致信号を優先順位の高い上位半
数ｎ／２＋１からｎ（この例ではＭ５〜Ｍ８）と、それ
より優先順位の低い下位半数１〜ｎ／２（この例ではＭ
１〜Ｍ４）の２つのサブグループに分割され、上位半数
は上位サブ競合裁定回路７１によって裁定され、下位半
数は下位サブ競合裁定回路７２によって選定される。
【００１７】上位サブ競合裁定回路７１はＰチャネルＭ
ＯＳトランジスタＰ５〜Ｐ９とＮチャネルＭＯＳトラン
ジスタＮ５４，Ｎ６４，Ｎ６５，Ｎ７４〜Ｎ７６，Ｎ８
４〜Ｎ８７，Ｎ９４〜Ｎ９８を含む。一致信号Ｍ５はＰ
チャネルＭＯＳトランジスタＰ５とＮチャネルＭＯＳト
ランジスタＮ５４の各ゲートに与えられる。一致信号Ｍ
６はＰチャネルＭＯＳトランジスタＰ６とＮチャネルＭ
ＯＳトランジスタＮ６４，Ｎ６５の各ゲートに与えられ
る。一致信号Ｍ７はＰチャネルＭＯＳトランジスタＰ７
とＮチャネルＭＯＳトランジスタＮ７４〜Ｎ７６の各ゲ
ートに与えられる。一致信号Ｍ８はＰチャネルＭＯＳト
ランジスタＰ８とＮチャネルＭＯＳトランジスタＮ８４
〜Ｎ８７の各ゲートに与えられる。
ＯＳトランジスタＰ５〜Ｐ９とＮチャネルＭＯＳトラン
ジスタＮ５４，Ｎ６４，Ｎ６５，Ｎ７４〜Ｎ７６，Ｎ８
４〜Ｎ８７，Ｎ９４〜Ｎ９８を含む。一致信号Ｍ５はＰ
チャネルＭＯＳトランジスタＰ５とＮチャネルＭＯＳト
ランジスタＮ５４の各ゲートに与えられる。一致信号Ｍ
６はＰチャネルＭＯＳトランジスタＰ６とＮチャネルＭ
ＯＳトランジスタＮ６４，Ｎ６５の各ゲートに与えられ
る。一致信号Ｍ７はＰチャネルＭＯＳトランジスタＰ７
とＮチャネルＭＯＳトランジスタＮ７４〜Ｎ７６の各ゲ
ートに与えられる。一致信号Ｍ８はＰチャネルＭＯＳト
ランジスタＰ８とＮチャネルＭＯＳトランジスタＮ８４
〜Ｎ８７の各ゲートに与えられる。
【００１８】第１のブロック禁止信号ＩＮＨ１はＰチャ
ネルＭＯＳトランジスタＰ９とＮチャネルＭＯＳトラン
ジスタＮ９４〜Ｎ９８の各ゲートに与えられる。Ｐチャ
ネルＭＯＳトランジスタＰ５〜Ｐ９は直列接続され、Ｐ
チャネルＭＯＳトランジスタＰ９のドレインは電源に接
続され、ＰチャネルＭＯＳトランジスタＰ５のソースか
ら第２のブロック禁止信号ＩＮＨ２が出力される。Ｎチ
ャネルＭＯＳトランジスタＮ５４，Ｎ６４，Ｎ６５，Ｎ
７４〜Ｎ７６，Ｎ８４〜Ｎ８７，Ｎ９４〜Ｎ９８の各ソ
ースは接地される。
ネルＭＯＳトランジスタＰ９とＮチャネルＭＯＳトラン
ジスタＮ９４〜Ｎ９８の各ゲートに与えられる。Ｐチャ
ネルＭＯＳトランジスタＰ５〜Ｐ９は直列接続され、Ｐ
チャネルＭＯＳトランジスタＰ９のドレインは電源に接
続され、ＰチャネルＭＯＳトランジスタＰ５のソースか
ら第２のブロック禁止信号ＩＮＨ２が出力される。Ｎチ
ャネルＭＯＳトランジスタＮ５４，Ｎ６４，Ｎ６５，Ｎ
７４〜Ｎ７６，Ｎ８４〜Ｎ８７，Ｎ９４〜Ｎ９８の各ソ
ースは接地される。
【００１９】ＮチャネルＭＯＳトランジスタＮ９４のド
レインはＮチャネルＭＯＳトランジスタＮ８４，Ｎ７
４，Ｎ６４，Ｎ５４の各ドレインとＰチャネルＭＯＳト
ランジスタＰ５のソースに接続される。ＮチャネルＭＯ
ＳトランジスタＮ９５のドレインはＮチャネルＭＯＳト
ランジスタＮ８５，Ｎ７５，Ｎ６５の各ドレインとＰチ
ャネルＭＯＳトランジスタＰ５のドレインに接続され
る。ＮチャネルＭＯＳトランジスタＮ９６のドレインは
ＮチャネルＭＯＳトランジスタＮ８６，Ｎ７６の各ドレ
インとＰチャネルＭＯＳトランジスタＰ６のドレインと
に接続される。ＮチャネルＭＯＳトランジスタＮ９７の
ドレインはＮチャネルＭＯＳトランジスタＮ８７のドレ
インとＰチャネルＭＯＳトランジスタＰ７のドレインに
接続される。ＮチャネルＭＯＳトランジスタＮ９８のド
レインはＰチャネルＭＯＳトランジスタＰ８のドレイン
に接続される。ＰチャネルＭＯＳトランジスタＰ５，Ｐ
６，Ｐ７，Ｐ８の各ドレインはＡＮＤゲートＡＮＤ５〜
ＡＮＤ８の一方入力端に接続され、ＡＮＤゲートＡＮＤ
５〜８の他方入力端には一致信号Ｍ５〜Ｍ８が入力され
る。
レインはＮチャネルＭＯＳトランジスタＮ８４，Ｎ７
４，Ｎ６４，Ｎ５４の各ドレインとＰチャネルＭＯＳト
ランジスタＰ５のソースに接続される。ＮチャネルＭＯ
ＳトランジスタＮ９５のドレインはＮチャネルＭＯＳト
ランジスタＮ８５，Ｎ７５，Ｎ６５の各ドレインとＰチ
ャネルＭＯＳトランジスタＰ５のドレインに接続され
る。ＮチャネルＭＯＳトランジスタＮ９６のドレインは
ＮチャネルＭＯＳトランジスタＮ８６，Ｎ７６の各ドレ
インとＰチャネルＭＯＳトランジスタＰ６のドレインと
に接続される。ＮチャネルＭＯＳトランジスタＮ９７の
ドレインはＮチャネルＭＯＳトランジスタＮ８７のドレ
インとＰチャネルＭＯＳトランジスタＰ７のドレインに
接続される。ＮチャネルＭＯＳトランジスタＮ９８のド
レインはＰチャネルＭＯＳトランジスタＰ８のドレイン
に接続される。ＰチャネルＭＯＳトランジスタＰ５，Ｐ
６，Ｐ７，Ｐ８の各ドレインはＡＮＤゲートＡＮＤ５〜
ＡＮＤ８の一方入力端に接続され、ＡＮＤゲートＡＮＤ
５〜８の他方入力端には一致信号Ｍ５〜Ｍ８が入力され
る。
【００２０】下位サブ競合裁定回路７２はＰチャネルＭ
ＯＳトランジスタＰ０〜Ｐ４とＮチャネルＭＯＳトラン
ジスタＮ１０，Ｎ２０，Ｎ２１，Ｎ３０〜Ｎ３２，Ｎ４
０〜Ｎ４３，Ｎ５０〜Ｎ５４を含む。一致信号Ｍ１はＰ
チャネルＭＯＳトランジスタＰ０とＮチャネルＭＯＳト
ランジスタＮ１０のゲートに与えられ、一致信号Ｍ２は
ＰチャネルＭＯＳトランジスタＰ１とＮチャネルＭＯＳ
トランジスタＮ２０，Ｎ２１の各ゲートに与えられる。
一致信号Ｍ３はＰチャネルＭＯＳトランジスタＰ２とＮ
チャネルＭＯＳトランジスタＮ３０〜Ｎ３２の各ゲート
に与えられる。一致信号Ｍ４はＰチャネルＭＯＳトラン
ジスタＰ３とＮチャネルＭＯトランジスタＮ４０〜Ｎ４
３の各ゲートに与えられる。第２のブロック禁止信号Ｉ
ＮＨ２はインバータＩＮＶで反転された後、Ｐチャネル
ＭＯＳトランジスタＰ４とＮチャネルＭＯＳトランジス
タＮ５０〜Ｎ５４の各ゲートに与えられる。Ｐチャネル
ＭＯトランジスタＰ０〜Ｐ４は直列接続され、Ｐチャネ
ルＭＯＳトランジスタＰ４のドレインには電源電圧が与
えられ、ＰチャネルＭＯＳトランジスタＰ０のソースか
らブロック一致信号／ＨＩＴが出力される。
ＯＳトランジスタＰ０〜Ｐ４とＮチャネルＭＯＳトラン
ジスタＮ１０，Ｎ２０，Ｎ２１，Ｎ３０〜Ｎ３２，Ｎ４
０〜Ｎ４３，Ｎ５０〜Ｎ５４を含む。一致信号Ｍ１はＰ
チャネルＭＯＳトランジスタＰ０とＮチャネルＭＯＳト
ランジスタＮ１０のゲートに与えられ、一致信号Ｍ２は
ＰチャネルＭＯＳトランジスタＰ１とＮチャネルＭＯＳ
トランジスタＮ２０，Ｎ２１の各ゲートに与えられる。
一致信号Ｍ３はＰチャネルＭＯＳトランジスタＰ２とＮ
チャネルＭＯＳトランジスタＮ３０〜Ｎ３２の各ゲート
に与えられる。一致信号Ｍ４はＰチャネルＭＯＳトラン
ジスタＰ３とＮチャネルＭＯトランジスタＮ４０〜Ｎ４
３の各ゲートに与えられる。第２のブロック禁止信号Ｉ
ＮＨ２はインバータＩＮＶで反転された後、Ｐチャネル
ＭＯＳトランジスタＰ４とＮチャネルＭＯＳトランジス
タＮ５０〜Ｎ５４の各ゲートに与えられる。Ｐチャネル
ＭＯトランジスタＰ０〜Ｐ４は直列接続され、Ｐチャネ
ルＭＯＳトランジスタＰ４のドレインには電源電圧が与
えられ、ＰチャネルＭＯＳトランジスタＰ０のソースか
らブロック一致信号／ＨＩＴが出力される。
【００２１】ＮチャネルＭＯＳトランジスタＮ５０のド
レインはＮチャネルＭＯＳトランジスタＮ４０，Ｎ３
０，Ｎ２０，Ｎ１０の各ドレインとＰチャネルＭＯＳト
ランジスタＰ０のソースとに接続される。ＮチャネルＭ
ＯＳトランジスタＮ５１のドレインはＮチャネルＭＯＳ
トランジスタＮ４１，Ｎ３１，Ｎ２１の各ドレインとＰ
チャネルＭＯＳトランジスタＰ１のソースとに接続され
る。ＮチャネルＭＯＳトランジスタＮ５２のドレインは
ＮチャネルＭＯＳトランジスタＮ４２，Ｎ３２の各ドレ
インとＰチャネルＭＯＳトランジスタＰ２のソースとに
接続される。ＮチャネルＭＯＳトランジスタＮ５３のド
レインはＮチャネルＭＯＳトランジスタＮ４３のドレイ
ンとＰチャネルＭＯＳトランジスタＰ３のソースに接続
される。ＮチャネルＭＯＳトランジスタＮ５４のドレイ
ンはＰチャネルＭＯＳトランジスタＰ４のソースに接続
される。ＰチャネルＭＯＳトランジスタＰ０，Ｐ１，Ｐ
２，Ｐ３の各ドレインはＡＮＤゲートＡＮＤ１〜ＡＮＤ
４の一方入力端に与えられ、ＡＮＤゲートＡＮＤ１〜Ａ
ＮＤ４の他方入力端には一致信号Ｍ１〜Ｍ４が入力され
る。
レインはＮチャネルＭＯＳトランジスタＮ４０，Ｎ３
０，Ｎ２０，Ｎ１０の各ドレインとＰチャネルＭＯＳト
ランジスタＰ０のソースとに接続される。ＮチャネルＭ
ＯＳトランジスタＮ５１のドレインはＮチャネルＭＯＳ
トランジスタＮ４１，Ｎ３１，Ｎ２１の各ドレインとＰ
チャネルＭＯＳトランジスタＰ１のソースとに接続され
る。ＮチャネルＭＯＳトランジスタＮ５２のドレインは
ＮチャネルＭＯＳトランジスタＮ４２，Ｎ３２の各ドレ
インとＰチャネルＭＯＳトランジスタＰ２のソースとに
接続される。ＮチャネルＭＯＳトランジスタＮ５３のド
レインはＮチャネルＭＯＳトランジスタＮ４３のドレイ
ンとＰチャネルＭＯＳトランジスタＰ３のソースに接続
される。ＮチャネルＭＯＳトランジスタＮ５４のドレイ
ンはＰチャネルＭＯＳトランジスタＰ４のソースに接続
される。ＰチャネルＭＯＳトランジスタＰ０，Ｐ１，Ｐ
２，Ｐ３の各ドレインはＡＮＤゲートＡＮＤ１〜ＡＮＤ
４の一方入力端に与えられ、ＡＮＤゲートＡＮＤ１〜Ａ
ＮＤ４の他方入力端には一致信号Ｍ１〜Ｍ４が入力され
る。
【００２２】なお、信号選別回路８の各ＡＮＤゲートＡ
ＮＤ１〜ＡＮＤ８の出力である裁定信号Ｔ１〜Ｔ８はエ
ンコード回路９に与えられる。エンコード回路９は３個
の４入力ＮＯＲゲートを含み、裁定信号Ｔ１〜Ｔ８を受
け、エンコード信号Ｆ０〜Ｆ２を出力する。
ＮＤ１〜ＡＮＤ８の出力である裁定信号Ｔ１〜Ｔ８はエ
ンコード回路９に与えられる。エンコード回路９は３個
の４入力ＮＯＲゲートを含み、裁定信号Ｔ１〜Ｔ８を受
け、エンコード信号Ｆ０〜Ｆ２を出力する。
【００２３】次に、図１に示した優先度決定回路７の動
作について説明する。上位サブ競合裁定回路７１は、一
致信号Ｍj （この例では５≦ｊ≦８）が活性化状態にあ
る場合、複数個（この例では（ｊ−４）個）のＮチャネ
ルＭＯＳトランジスタによって、それより優先順位が低
いサブグループ内の禁止信号／Ｉｋ（この例では５≦ｋ
≦ｊ）と第２のブロック禁止信号ＩＮＨ２をそれぞれ同
時に活性化させる。一方、一致信号Ｍj （この例では５
≦ｊ≦８）が非活性状態にある場合、ＰチャネルＭＯＳ
トランジスタによって、自らの禁止信号／Ｉj をそれよ
り優先順位が１つだけ低い禁止信号／Ｉj-1 に伝搬され
る。
作について説明する。上位サブ競合裁定回路７１は、一
致信号Ｍj （この例では５≦ｊ≦８）が活性化状態にあ
る場合、複数個（この例では（ｊ−４）個）のＮチャネ
ルＭＯＳトランジスタによって、それより優先順位が低
いサブグループ内の禁止信号／Ｉｋ（この例では５≦ｋ
≦ｊ）と第２のブロック禁止信号ＩＮＨ２をそれぞれ同
時に活性化させる。一方、一致信号Ｍj （この例では５
≦ｊ≦８）が非活性状態にある場合、ＰチャネルＭＯＳ
トランジスタによって、自らの禁止信号／Ｉj をそれよ
り優先順位が１つだけ低い禁止信号／Ｉj-1 に伝搬され
る。
【００２４】より具体的に説明すると、たとえば一致信
号Ｍ５が“Ｈ”レベルに活性化されると、ＮチャネルＭ
ＯＳトランジスタＮ５４が導通し、そのドレインが
“Ｌ”レベルになる。この“Ｌ”レベル信号はインバー
タＩＮＶによって“Ｈ”レベルに反転され、下位サブ競
合裁定回路７２のＮチャネルトランジスタＮ５０〜Ｎ５
４のゲートに与えられ、これらのＮチャネルＭＯＳトラ
ンジスタＮ５０〜Ｎ５４が導通する。その結果、禁止信
号／Ｉ１〜Ｉ４が“Ｌ”レベルに活性化され、ＡＮＤゲ
ートＡＮＤ１〜ＡＮＤ４が閉じられる。このため、一致
信号Ｍ５よりも下位の一致信号Ｍ１〜Ｍ４が“Ｈ”レベ
ルに活性化されても、裁定信号Ｔ１〜Ｔ４が出力される
ことはなく、一致信号Ｍ５がそれよりも下位の一致信号
Ｍ１〜Ｍ４よりも優先される。しかし、一致信号Ｍ５と
Ｍ８とが同時に“Ｈ”レベルに活性化されたときには、
一致信号Ｍ８によりＮチャネルＭＯＳトランジスタＮ８
４〜Ｎ８７が導通し、禁止信号／Ｉ１〜／Ｉ７が“Ｌ”
レベルになり、一致信号Ｍ５が“Ｈ”レベルになって
も、裁定信号Ｔ５が出力されることはなく、一致信号Ｍ
８がＭ５よりも優先される。
号Ｍ５が“Ｈ”レベルに活性化されると、ＮチャネルＭ
ＯＳトランジスタＮ５４が導通し、そのドレインが
“Ｌ”レベルになる。この“Ｌ”レベル信号はインバー
タＩＮＶによって“Ｈ”レベルに反転され、下位サブ競
合裁定回路７２のＮチャネルトランジスタＮ５０〜Ｎ５
４のゲートに与えられ、これらのＮチャネルＭＯＳトラ
ンジスタＮ５０〜Ｎ５４が導通する。その結果、禁止信
号／Ｉ１〜Ｉ４が“Ｌ”レベルに活性化され、ＡＮＤゲ
ートＡＮＤ１〜ＡＮＤ４が閉じられる。このため、一致
信号Ｍ５よりも下位の一致信号Ｍ１〜Ｍ４が“Ｈ”レベ
ルに活性化されても、裁定信号Ｔ１〜Ｔ４が出力される
ことはなく、一致信号Ｍ５がそれよりも下位の一致信号
Ｍ１〜Ｍ４よりも優先される。しかし、一致信号Ｍ５と
Ｍ８とが同時に“Ｈ”レベルに活性化されたときには、
一致信号Ｍ８によりＮチャネルＭＯＳトランジスタＮ８
４〜Ｎ８７が導通し、禁止信号／Ｉ１〜／Ｉ７が“Ｌ”
レベルになり、一致信号Ｍ５が“Ｈ”レベルになって
も、裁定信号Ｔ５が出力されることはなく、一致信号Ｍ
８がＭ５よりも優先される。
【００２５】また、第１のブロック禁止信号ＩＮＨ１が
活性化状態にある場合、複数個（この例では５個）のＮ
チャネルＭＯＳトランジスタＮ９４〜Ｎ９８が導通し、
上位のサブグループ内のすべての禁止信号（この例では
／Ｉ５〜／Ｉ８）と第２のブロック禁止信号ＩＮＨ２が
同時に活性化される。一方、第１のブロック禁止信号Ｉ
ＮＨ１が非活性状態にある場合、ＰチャネルＭＯＳトラ
ンジスタＰ９が導通し、サブブロック内の最上位の禁止
信号（この例では／Ｉ８）が非活性にされる。このた
め、ＡＮＤゲートＡＮＤ１が閉じられ、裁定信号Ｔ１が
出力されることはない。
活性化状態にある場合、複数個（この例では５個）のＮ
チャネルＭＯＳトランジスタＮ９４〜Ｎ９８が導通し、
上位のサブグループ内のすべての禁止信号（この例では
／Ｉ５〜／Ｉ８）と第２のブロック禁止信号ＩＮＨ２が
同時に活性化される。一方、第１のブロック禁止信号Ｉ
ＮＨ１が非活性状態にある場合、ＰチャネルＭＯＳトラ
ンジスタＰ９が導通し、サブブロック内の最上位の禁止
信号（この例では／Ｉ８）が非活性にされる。このた
め、ＡＮＤゲートＡＮＤ１が閉じられ、裁定信号Ｔ１が
出力されることはない。
【００２６】下位サブ競合裁定回路７２においては、一
致信号Ｍj （この例では１≦ｊ≦４）が活性化状態にあ
る場合、複数個（この例ではｊ個）のＮチャネルＭＯＳ
トランジスタによってそれより優先順位が低いサブグル
ープ内の禁止信号／Ｉｋ（この例では１≦ｋ≦ｊ）とブ
ロック一致信号／ＨＩＴがそれぞれ同時に活性化され
る。一方、一致信号Ｍj （この例では１≦ｊ≦４）が非
活性状態にある場合、ＰチャネルＭＯＳトランジスタに
よって自らの禁止信号／Ｉj をそれより優先順位が１つ
だけ低い禁止信号／Ｉj-1 に伝搬する。
致信号Ｍj （この例では１≦ｊ≦４）が活性化状態にあ
る場合、複数個（この例ではｊ個）のＮチャネルＭＯＳ
トランジスタによってそれより優先順位が低いサブグル
ープ内の禁止信号／Ｉｋ（この例では１≦ｋ≦ｊ）とブ
ロック一致信号／ＨＩＴがそれぞれ同時に活性化され
る。一方、一致信号Ｍj （この例では１≦ｊ≦４）が非
活性状態にある場合、ＰチャネルＭＯＳトランジスタに
よって自らの禁止信号／Ｉj をそれより優先順位が１つ
だけ低い禁止信号／Ｉj-1 に伝搬する。
【００２７】より具体的に説明すると、たとえば、一致
信号Ｍ３が“Ｈ”レベルで活性状態にあると、Ｎチャネ
ルＭＯＳトランジスタＮ３０〜Ｎ３２が導通し、一致信
号Ｍ３よりも優先順位が低いグループの禁止信号／Ｉ
１，／Ｉ２とブロック一致信号／ＨＩＴがそれぞれ
“Ｌ”レベルに活性化される。このため、一致信号Ｍ
１，Ｍ２が“Ｈ”レベルに活性化されても、裁定信号Ｔ
１，Ｔ２が出力されることはない。
信号Ｍ３が“Ｈ”レベルで活性状態にあると、Ｎチャネ
ルＭＯＳトランジスタＮ３０〜Ｎ３２が導通し、一致信
号Ｍ３よりも優先順位が低いグループの禁止信号／Ｉ
１，／Ｉ２とブロック一致信号／ＨＩＴがそれぞれ
“Ｌ”レベルに活性化される。このため、一致信号Ｍ
１，Ｍ２が“Ｈ”レベルに活性化されても、裁定信号Ｔ
１，Ｔ２が出力されることはない。
【００２８】また、第２のブロック禁止信号ＩＮＨ２が
活性化状態にある場合、複数個（この例では５個）のＮ
チャネルＭＯＳトランジスタによって下位のサブグルー
プ内のすべての禁止信号（この例では／Ｉ１〜／Ｉ３）
とブロック一致信号／ＨＩＴが同時に活性化される。一
方、第２のブロック禁止信号ＩＮＨ２が非活性状態にあ
る場合、ＰチャネルＭＯＳトランジスタによってサブブ
ロック内の最上位の禁止信号（この例では／Ｉ４）が非
活性化される。
活性化状態にある場合、複数個（この例では５個）のＮ
チャネルＭＯＳトランジスタによって下位のサブグルー
プ内のすべての禁止信号（この例では／Ｉ１〜／Ｉ３）
とブロック一致信号／ＨＩＴが同時に活性化される。一
方、第２のブロック禁止信号ＩＮＨ２が非活性状態にあ
る場合、ＰチャネルＭＯＳトランジスタによってサブブ
ロック内の最上位の禁止信号（この例では／Ｉ４）が非
活性化される。
【００２９】図１に示した優先度決定回路７において
は、上位半数のサブグループの一致信号Ｍ５〜Ｍ８が昇
順に配置され、下位半数のサブグループの一致信号Ｍ１
〜Ｍ４は降順にそれそれ配置されており、上位サブ競合
裁定回路７１と下位サブ競合裁定回路７２においては、
優先順位の高い一致信号ほどそれより優先順位の低い禁
止信号を活性化するためのＮチャネルＭＯＳトランジス
タの数が多いことから、そのレイアウトパターンが三角
状になる。そして、上位サブ競合裁定回路７１と下位サ
ブ競合裁定回路７２は、一致信号の配置に応じて、三角
形と逆三角形を組合わせた相補形形状となるように配置
されており、このような配置により三角状レイアウトパ
ターンの持つエリアロスをなくすことができる。
は、上位半数のサブグループの一致信号Ｍ５〜Ｍ８が昇
順に配置され、下位半数のサブグループの一致信号Ｍ１
〜Ｍ４は降順にそれそれ配置されており、上位サブ競合
裁定回路７１と下位サブ競合裁定回路７２においては、
優先順位の高い一致信号ほどそれより優先順位の低い禁
止信号を活性化するためのＮチャネルＭＯＳトランジス
タの数が多いことから、そのレイアウトパターンが三角
状になる。そして、上位サブ競合裁定回路７１と下位サ
ブ競合裁定回路７２は、一致信号の配置に応じて、三角
形と逆三角形を組合わせた相補形形状となるように配置
されており、このような配置により三角状レイアウトパ
ターンの持つエリアロスをなくすことができる。
【００３０】図２はこの発明の他の実施例を示すブロッ
ク図である。前述の図１に示した実施例は、Ｎチャネル
ＭＯＳトランジスタとＰチャネルＭＯＳトランジスタを
組合わせて優先度決定回路７を構成したが、この図２に
示した優先度決定回路９はインバータＩＮＶ１，ＩＮＶ
２とＮＯＲゲートＮＯＲ１〜ＮＯＲ８とによって構成し
たものである。すなわち、上位サブ競合調停回路９１は
インバータＩＮＶ１とＮＯＲゲートＮＯＲ１〜ＮＯＲ４
を含み、インバータＩＮＶ１は禁止信号ＩＮＨ１を反転
してＡＮＤゲート８の一方入力に与える。ＮＯＲゲート
ＮＯＲ１は一致信号Ｍ８と禁止信号ＩＮＨ１を入力とし
て受け、それをＡＮＤゲートＡＮＤ７の一方入力に与え
る。ＮＯＲゲートＮＯＲ２は一致信号Ｍ７とＭ８と禁止
信号ＩＮＨ１とを受け、出力をＡＮＤゲートＡＮＤ６の
一方入力に与える。ＮＯＲゲートＮＯＲ３は一致信号Ｍ
６とＭ７とＭ８と禁止信号ＩＮＨ１をＡＮＤゲートＡＮ
Ｄ４の一方入力に与える。ＮＯＲゲートＮＯＲ４は一致
信号Ｍ５とＭ６とＭ７とＭ８と禁止信号ＩＮＨ１とを受
け、その出力をインバータＩＮＶに与える。
ク図である。前述の図１に示した実施例は、Ｎチャネル
ＭＯＳトランジスタとＰチャネルＭＯＳトランジスタを
組合わせて優先度決定回路７を構成したが、この図２に
示した優先度決定回路９はインバータＩＮＶ１，ＩＮＶ
２とＮＯＲゲートＮＯＲ１〜ＮＯＲ８とによって構成し
たものである。すなわち、上位サブ競合調停回路９１は
インバータＩＮＶ１とＮＯＲゲートＮＯＲ１〜ＮＯＲ４
を含み、インバータＩＮＶ１は禁止信号ＩＮＨ１を反転
してＡＮＤゲート８の一方入力に与える。ＮＯＲゲート
ＮＯＲ１は一致信号Ｍ８と禁止信号ＩＮＨ１を入力とし
て受け、それをＡＮＤゲートＡＮＤ７の一方入力に与え
る。ＮＯＲゲートＮＯＲ２は一致信号Ｍ７とＭ８と禁止
信号ＩＮＨ１とを受け、出力をＡＮＤゲートＡＮＤ６の
一方入力に与える。ＮＯＲゲートＮＯＲ３は一致信号Ｍ
６とＭ７とＭ８と禁止信号ＩＮＨ１をＡＮＤゲートＡＮ
Ｄ４の一方入力に与える。ＮＯＲゲートＮＯＲ４は一致
信号Ｍ５とＭ６とＭ７とＭ８と禁止信号ＩＮＨ１とを受
け、その出力をインバータＩＮＶに与える。
【００３１】下位サブ競合裁定回路９２はインバータＩ
ＮＶ２とＮＯＲゲートＮＯＲ５〜ＮＯＲ８とを含む。イ
ンバータＩＮＶ２は禁止信号ＩＮＨ２を反転してＡＮＤ
ゲートＡＮＤ４の一方入力に与え、ＮＯＲゲートＮＯＲ
５は一致信号Ｍ４と禁止信号ＩＮＨ２とを受け、出力を
ＡＮＤゲートＡＮＤゲート３の一方入力に与える。ＮＯ
ＲゲートＮＯＲ６は一致信号Ｍ３とＭ４と禁止信号ＩＮ
Ｈ２とを受け、出力をＡＮＤゲート２の一方入力に与え
る。ＮＯＲゲート７は一致信号Ｍ２とＭ３とＭ４と禁止
信号ＩＮＨ２とを受け、出力をＡＮＤゲートＡＮＤ１に
与える。ＮＯＲゲートＮＯＲ８は一致信号Ｍ１とＭ２と
Ｍ３とＭ４と禁止信号ＩＮＨ２とを受け、入力一致信号
／ＨＩＴとして出力する。
ＮＶ２とＮＯＲゲートＮＯＲ５〜ＮＯＲ８とを含む。イ
ンバータＩＮＶ２は禁止信号ＩＮＨ２を反転してＡＮＤ
ゲートＡＮＤ４の一方入力に与え、ＮＯＲゲートＮＯＲ
５は一致信号Ｍ４と禁止信号ＩＮＨ２とを受け、出力を
ＡＮＤゲートＡＮＤゲート３の一方入力に与える。ＮＯ
ＲゲートＮＯＲ６は一致信号Ｍ３とＭ４と禁止信号ＩＮ
Ｈ２とを受け、出力をＡＮＤゲート２の一方入力に与え
る。ＮＯＲゲート７は一致信号Ｍ２とＭ３とＭ４と禁止
信号ＩＮＨ２とを受け、出力をＡＮＤゲートＡＮＤ１に
与える。ＮＯＲゲートＮＯＲ８は一致信号Ｍ１とＭ２と
Ｍ３とＭ４と禁止信号ＩＮＨ２とを受け、入力一致信号
／ＨＩＴとして出力する。
【００３２】次に、図２に示した優先度決定回路９０の
動作について説明する。たとえば、一致信号Ｍ６が活性
化されると、この一致信号Ｍ６はＮＯＲゲートＮＯＲ３
とＮＯＲ４とに与えられており、ＮＯＲゲートＮＯＲ３
の出力、すなわち禁止信号／Ｉ５は“Ｌ”レベルにな
り、ＡＮＤゲートＡＮＤ５が閉じられる。また、ＮＯＲ
ゲートＮＯＲ４の出力は“Ｌ”レベルになり、インバー
タＩＮＶで反転され、ブロック禁止信号ＩＮＨ２が
“Ｈ”になる。すると、インバータＩＮＶ２とＮＯＲゲ
ートＮＯＲ５〜ＮＯＲ８の出力はそれぞれ“Ｌ”レベル
となり、ＡＮＤゲートＡＮＤ１〜ＡＮＤ４が閉じられ、
裁定信号Ｔ１〜Ｔ５が出力されることはない。すなわ
ち、一致信号Ｍ６が活性化されると、それよりも下位の
一致信号Ｍ１〜Ｍ５よりも優先される。
動作について説明する。たとえば、一致信号Ｍ６が活性
化されると、この一致信号Ｍ６はＮＯＲゲートＮＯＲ３
とＮＯＲ４とに与えられており、ＮＯＲゲートＮＯＲ３
の出力、すなわち禁止信号／Ｉ５は“Ｌ”レベルにな
り、ＡＮＤゲートＡＮＤ５が閉じられる。また、ＮＯＲ
ゲートＮＯＲ４の出力は“Ｌ”レベルになり、インバー
タＩＮＶで反転され、ブロック禁止信号ＩＮＨ２が
“Ｈ”になる。すると、インバータＩＮＶ２とＮＯＲゲ
ートＮＯＲ５〜ＮＯＲ８の出力はそれぞれ“Ｌ”レベル
となり、ＡＮＤゲートＡＮＤ１〜ＡＮＤ４が閉じられ、
裁定信号Ｔ１〜Ｔ５が出力されることはない。すなわ
ち、一致信号Ｍ６が活性化されると、それよりも下位の
一致信号Ｍ１〜Ｍ５よりも優先される。
【００３３】
【発明の効果】以上のように、この発明によれば、活性
状態にある一致信号がそれより優先順位の低い複数の禁
止信号を一括して活性化させることによって、禁止信号
の伝搬遅延を低減でき、したがって、一致信号を所定の
アドレスコードに変換するまでの時間を従来よりも短縮
することが可能になる。また、第１および第２の回路を
三角形と逆三角形を組合わせた相補形形状とすることに
よって、エリアロスを最小限に止めることができる。
状態にある一致信号がそれより優先順位の低い複数の禁
止信号を一括して活性化させることによって、禁止信号
の伝搬遅延を低減でき、したがって、一致信号を所定の
アドレスコードに変換するまでの時間を従来よりも短縮
することが可能になる。また、第１および第２の回路を
三角形と逆三角形を組合わせた相補形形状とすることに
よって、エリアロスを最小限に止めることができる。
【図１】この発明の一実施例の回路構成を示す図であ
る。
る。
【図２】この発明の他の実施例を示すブロック図であ
る。
る。
【図３】従来の連想メモリに対する周辺回路の全体のブ
ロック図である。
ロック図である。
【図４】従来の優先順位決定回路とエンコード回路のブ
ロック図である。
ロック図である。
【図５】従来の優先順位決定回路とエンコード回路の他
の例を示す図である。
の例を示す図である。
１ 連想メモリ ２，３ ラッチ回路 ７，９０ 優先度決定回路 ８ 信号選別回路 ９ デコード回路 ７１，９１ 上位サブ競合裁定回路 ７２，９２ 下位サブ競合裁定回路
Claims (6)
- 【請求項１】 連想メモリの格納データと外部から与え
られた検索データとの一致に応じて、その一致したデー
タが格納されているワード位置に対応するアドレスから
出力されるｎ個の一致信号を所定の優先順位に従って順
次選択して出力する優先度決定回路であって、 外部から与えられる検索データと前記連想メモリに格納
されている一致データに応じて、前記連想メモリから種
々の優先順位の一致信号を受ける手段、 前記連想メモリに格納されているデータと前記検索デー
タとの一致に応じて、優先順位のもっとも高いワード位
置を検出し、その優先順位の最も高いワード位置に対応
する一致信号を出力する検出手段、および前記検出手段
の検出出力に応じて、優先順位の低いすべてのワード位
置に対応する一致信号が出力されるのを同時に禁止する
禁止手段を備えた、連想メモリの優先度決定回路。 - 【請求項２】 前記検出手段は、 ｎ／２＋１番目からｎ番目までの一致信号と第１のブロ
ック禁止信号とを受け、ｎ／２＋１番目からｎ番目まで
の禁止信号と第２のブロック禁止信号を出力する第１の
回路と、 １番目からｎ／２番目までの一致信号と前記第２のブロ
ック禁止信号とを受け、１番目からｎ／２番目までの禁
止信号と第３のブロック禁止信号とを出力する第２の回
路と、 前記ｎ個の禁止信号に応じて、前記ｎ個の一致信号をｎ
個の裁定信号として出力するか否かを決定するための第
３の回路とを含む、請求項１の連想メモリの優先度決定
回路。 - 【請求項３】 前記第１の回路は、前記第１のブロック
禁止信号が活性状態になったことに応じて、前記第２の
ブロック禁止信号とｎ／２＋１番目からｎ番目までの禁
止信号を同時に活性化し、前記第１のブロック禁止信号
が非活性状態になったことに応じて、前記ｎ番目の禁止
信号を非活性にする第１の活性，非活性化手段を含み、 前記第２の回路は、前記第２のブロック禁止信号が活性
状態になったことに応じて、前記第３のブロック禁止信
号と１番目からｎ／２番目までの禁止信号を同時に活性
化し、前記第２のブロック禁止信号が非活性状態になっ
たことに応じて、ｎ／２番目の禁止信号を非活性にする
第２の活性，非活性化手段を含む、請求項２の連想メモ
リの優先度決定回路。 - 【請求項４】 前記第１の回路は、 ｉ番目の一致信号（ｎ／２＋２≦ｉ≦ｎ）が活性状態に
なったことに応じて、前記第２のブロック禁止信号と、
ｎ／２＋１番目からｉ−１番目までの禁止信号を同時に
活性化し、前記ｉ番目の一致信号（ｎ／２＋２≦ｉ≦
ｎ）が非活性状態になったことに応じて、ｉ番目の禁止
信号の状態をｉ−１番目の禁止信号に伝達する第１の伝
達手段と、 ｎ／２＋１番目の一致信号が活性状態になったことに応
じて、前記第２のブロック禁止信号を活性化し、前記ｎ
／２＋１番目の一致信号が非活性状態になったことに応
じて、ｎ／２＋１番目の禁止信号の状態を前記第２のブ
ロック禁止信号に伝達する第２の伝達手段とを含み、 前記第２の回路は、 ｊ番目の一致信号（２≦ｊ±ｎ／２）が活性状態になっ
たことに応じて、前記第３のブロック禁止信号と１番目
からｊ−１番目までの禁止信号を同時に活性化し、前記
ｊ番目の一致信号（２≦ｊ≦ｎ／２）が非活性状態にな
ったことに応じて、ｊ番目の禁止信号の状態をｊ−１番
目の禁止信号に伝達する第３の伝達手段と、 １番目の一致信号が活性状態になったことに応じて、前
記第３のブロック禁止信号を活性化し、前記１番目の一
致信号が非活性状態になったことに応じて、１番目の禁
止信号の状態を前記第３のブロック禁止信号に伝達する
第４の伝達手段とを含む、請求項３の連想メモリの優先
度決定回路。 - 【請求項５】 前記ｎ／２＋１番目からｎ番目までの一
致信号を昇順に配置し、前記１番目からｎ／２番目まで
の一致信号を降順に配置し、 前記第１の回路をほぼ三角形状のレイアウトパターンで
配置し、前記第２の回路を前記三角形に対して相補的な
三角形状のレイアウトパターンで配置したことを特徴と
する、請求項２ないし４のいずれかに記載の連想メモリ
の優先度決定回路。 - 【請求項６】 連想メモリの格納データと外部から与え
られた検索データとの一致に応じて、その一致したデー
タが格納されているワード位置に対応するアドレスから
出力されるｎ個の一致信号を所定の優先順位に従って順
次選択して出力する優先度決定回路であって、 ｎ／２＋１番目からｎ番目までの一致信号と第１の禁止
信号とを受け、ｎ／２＋１番目からｎ番目までの禁止信
号と第２のブロック禁止信号とを出力する複数の論理素
子を含み、かつほぼ三角形状のレイアウトパターンで配
列された第１の回路、 １番目からｎ／２番目までの一致信号と前記第２のブロ
ック禁止信号とを受け、１番目からｎ／２番目までの禁
止信号と第３のブロック禁止信号とを出力する複数の論
理素子を含み、かつ前記三角形状に対して相補的な逆三
角形状のレイアウトパターンで配列された第２の回路、
および前記ｎ個の禁止信号に応じて、前記ｎ個の一致信
号をｎ個の裁定信号として出力するか否かを決定するた
めの第３の回路を備えた、連想メモリの優先度決定回
路。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4140801A JPH05174582A (ja) | 1991-09-02 | 1992-06-01 | 連想メモリの優先度決定回路 |
| US07/937,763 US5418923A (en) | 1991-09-02 | 1992-09-01 | Circuit for prioritizing outputs of an associative memory with parallel inhibition paths and a compact architecture |
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3-221691 | 1991-09-02 | ||
| JP22169191 | 1991-09-02 | ||
| JP4140801A JPH05174582A (ja) | 1991-09-02 | 1992-06-01 | 連想メモリの優先度決定回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05174582A true JPH05174582A (ja) | 1993-07-13 |
Family
ID=26473216
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4140801A Pending JPH05174582A (ja) | 1991-09-02 | 1992-06-01 | 連想メモリの優先度決定回路 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5418923A (ja) |
| JP (1) | JPH05174582A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6859376B2 (en) | 2002-02-27 | 2005-02-22 | Kawasaki Microelectronics, Inc. | Signal detection circuit for detecting multiple match in arranged signal lines |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3707890B2 (ja) * | 1996-12-26 | 2005-10-19 | 三星電子株式会社 | 外部記憶装置のデータ出力方法 |
| US6864810B2 (en) * | 2003-07-24 | 2005-03-08 | Micron Technology, Inc. | Converting digital signals |
| US9275735B2 (en) | 2014-01-06 | 2016-03-01 | International Business Machines Corporation | Array organization and architecture to perform range-match operations with content addressable memory (CAM) circuits |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6267794A (ja) * | 1985-09-20 | 1987-03-27 | Hitachi Ltd | 内容呼び出しメモリ |
| JPS6419430A (en) * | 1987-07-15 | 1989-01-23 | Fujitsu Ltd | Priority encoder |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3913075A (en) * | 1972-11-21 | 1975-10-14 | Vitaliev Georgy | Associative memory |
| JPS58212698A (ja) * | 1982-06-04 | 1983-12-10 | Matsushita Electric Ind Co Ltd | 記憶装置 |
| JPS62132297A (ja) * | 1985-12-02 | 1987-06-15 | Hitachi Ltd | 半導体記憶素子 |
-
1992
- 1992-06-01 JP JP4140801A patent/JPH05174582A/ja active Pending
- 1992-09-01 US US07/937,763 patent/US5418923A/en not_active Expired - Fee Related
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6267794A (ja) * | 1985-09-20 | 1987-03-27 | Hitachi Ltd | 内容呼び出しメモリ |
| JPS6419430A (en) * | 1987-07-15 | 1989-01-23 | Fujitsu Ltd | Priority encoder |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6859376B2 (en) | 2002-02-27 | 2005-02-22 | Kawasaki Microelectronics, Inc. | Signal detection circuit for detecting multiple match in arranged signal lines |
Also Published As
| Publication number | Publication date |
|---|---|
| US5418923A (en) | 1995-05-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7243290B2 (en) | Data encoding for fast CAM and TCAM access times | |
| JPH03130994A (ja) | 連想メモリ装置およびそれを用いたマイクロコンピュータ | |
| JPH0245277B2 (ja) | ||
| US5657291A (en) | Multiport register file memory cell configuration for read operation | |
| US5483498A (en) | Semiconductor memory device incorporating address change detection circuit for page mode access | |
| Onizawa et al. | High-throughput low-energy self-timed CAM based on reordered overlapped search mechanism | |
| JP3631146B2 (ja) | データハザードを検出するシステム | |
| US5860094A (en) | System for protecting information stored on physical media | |
| JP3110230B2 (ja) | データアクセス命令解読方法及び装置 | |
| JPH05174582A (ja) | 連想メモリの優先度決定回路 | |
| US7516271B2 (en) | Obtaining search results based on match signals and search width | |
| JPH10134584A (ja) | 連想メモリ | |
| US5881076A (en) | Comparator utilizing redundancy | |
| US7386660B2 (en) | CAM with automatic writing to the next free address | |
| US7003624B2 (en) | Method and apparatus for detecting “almost match” in a CAM | |
| US7107391B2 (en) | Automatic learning in a CAM | |
| US5845131A (en) | Multiprocessor system employing an improved self-coded distributed interrupt arbitration technique | |
| US6831587B1 (en) | Priority encoding | |
| US6879523B1 (en) | Random access memory (RAM) method of operation and device for search engine systems | |
| US6865097B2 (en) | Priority encoder | |
| US6934172B2 (en) | Priority encoder for successive encoding of multiple matches in a CAM | |
| JPH07161186A (ja) | 情報伝播用ダイナミック回路 | |
| JPH03501659A (ja) | パイプラインアドレスチエツクビツトスタツクコントローラ | |
| US5672984A (en) | Programmable logic array having power-saving banks | |
| JPH05282362A (ja) | データ検索回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 19980428 |