JPS58121455A

JPS58121455A - 優先回路

Info

Publication number: JPS58121455A
Application number: JP393882A
Authority: JP
Inventors: Mamoru Tanaka; 衛田中; Kazuo Nakamura; 一夫中村; Hiroaki Yajima; 矢島　宏明
Original assignee: Individual
Current assignee: Individual
Priority date: 1982-01-13
Filing date: 1982-01-13
Publication date: 1983-07-19
Also published as: JPH0157819B2

Abstract

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

Description

【発明の詳細な説明】本発明は、論理１と論理０とからなる２値系列を入力し
たとき最も左にあるあるいは最も右にある優先順位の高
い論理１の位置に対応する出力のみ論理ｌにする優先回
路あるいは前記優先順位の高い論理１の位置に対応する
出力を境にしてそれよりも左側にある出力をすべて強制
的に論理１にしそれよりも右側にある出力をすべて強制
的に論理Ｏにする優先回路の構成に関し、特に複数の行
線と複数の列線よりなるアレイ構造の優先回路の構成に
関する。

一般的に優先回路とは次のようなものである。

第１図において１１を優先回路１の入力線、０１をｒｌ
に対応する出力線とする。今、■＋のデータの優先順位
を上位ｉ番目と定める（ｉ＝１．２゜・・・、ｎ）。そ
して、正論理で考えた場合人力１１の中でデータが“１
”であるもののうち、最も優先順位の高い線で仮に１ｍ
とすると１＋＝　　”Ｏ″　　　　　　ｉ＜ｍ＠　１　″　　　　　　　　ｉ＝ｍ “Ｏ”ｏｒ“　１　″　　ｉ＞ｍの入力データに対し、０１＝　“Ｏ″　　　　　　ｉ≠Ｉ “１”　　　　　　■＝階を出力するものである。（第１図（ｂ）参照）従来、こ
の種の優先回路は、優先順位が割り当てられた複数本の
入力導線の１本以上が同時に活性化されたとき最も優先
順位の高い入力導線の高い入力導線の２進アドレスを提
供するプライオリティ・エンコーダ回路として第２図に
示すようなランダムロジックで構成されていた。第２図
（ａｌは８ビツト・プライオリティ・エンコーダ２の真
理値表であって、入力導線Ｄｏ＝Ｄ７には番号の太き（
なる順に高い優先順位が割り当てられている。

Ｅｉｎが１のとき最も優先順位の高い活性化された導線
の２進アドレスＱ２．Ｑｌ、ＱＯを提供する。

Ｇｓなる出力はＥ　ｉｎ＝　１のとき入力導線の少なく
とも１本が活性化されているならば１出力を発生する。

一方Ｅｏｕｔなる出力はＥｉｎ＝１のときり。

〜Ｄ７の入力導線のいずれも活性化されていないとき１
出力を発生ずる。このような８ビ・ノド・プライオリテ
ィ・エンコーダを実現するランダムロジックを第２図（
ｂ）に示す。

しかし、この種の従来の優先回路２は、メモリ構造でな
いため、入力数が非常に多くなると、チップ面積が大き
くなり、しかも遅延時間が非常に大きくなり、大規模集
！Ｉｆ（ＬＳＩ）化には適さなかった。

本発明は、回路構造を複数の行線と列線よりなるメモリ
構造にし、前記列線のうち優先順位の高い列線の論理１
または前記論理１をインバータで反転させた論理Ｏを前
記行線の定められた行線に伝達することによって他の列
線を強制的に論理０あるいは論理１にすることを利用し
て、チップ面積を小さくし、遅延時間も小さい優先回路
を提供するものである。

複数の行線と複数の列線よりなるメモリ構造において、
前記列線のうちある列線の論理状態あるいは前記論理状
態の反転論理を前記行線のあらかじめ定められた行線に
伝達することによって他の列線を前記行線と前記列線と
の各交点に存在する論理回路で強制的に特定の論理状態
にすることである。

次に本発明の優先回路の実施例を図面を参照にして説明
する。

優先回路を実現するにあたって入力数ｎが非常に大きい
場合でも回路面積をできるだけ小さくしなければならず
、さらにディレィを短くしなければならない。このよう
な点を満足する回路を考案したが、その基本は第３図に
示す回路である。ここでは正論理で考える。

第３図において横線は・印において交差する列線のデー
タを入力として行線にＯＲの結果を伝達するＯＲアレイ
を構成し、列線はＯにおいて交差する行線のデータを入
力としてＡＮＤの結果を取ることを示す、動作原理は任
意の優先順位のデータに対し、それよりも優先順位の高
いすべてのデータの中に値が１”であるようなデータの
存在によって強制的に０”するもので一種のルックアヘ
ッド方式であり、ディレィは入力数あるいは入力状態に
影響されない、第３図の回路３の面積Ｓを行線と列線の
数を基準にして表すとｎ入力のの場合３＝ｎｘ　（ｎ−１）　　　・・・・・・・・（１１と
なる。ｎは応用上かなり大きいことが要求されるので第
３図の回路３では付加回路としては面積が大きすぎて実
現が困難である。

そこで第３図の回路３を分割し、小規模な同一回路の階
層構造を考え、密度を上げることにより、同一機能で面
積の小さな回路を考案した。

第３図の回路の４人力の場合を階層的に接続した優先回
路４を第４図に示す。２段目においてはＡＮＤおよびＯ
Ｒの機能が列線４本分を１単位として同時に制御されて
いることに注意すれば１段目と相似な機能であることが
理解できよう。

一般に分割の基本回路の入力数をＰとし、階層の段数を
ｍとするとく第４図ではＰ＝４．ｍ＝２である）階層構
造の優先回路について次のことが言える。

入力数がＮであるような優先回路を構成する場合同一の
列線と交差する行線の最大数をＭとするとｐｍ≧Ｎ　　　・　・　・　・　・　・　・　・　・　
・　・　・　・　（２）Ｍ÷ｍ（Ｐ−１）　　　・　・
　・　・　・　・　・　・　・（３）が成り立つ。（２
）式において符号が成り立つ時が最も効率的であるからＰｍ＝Ｎ　　・・・、・・・・・・・・・・（２）とし
て優先回路としての面積が最小になるような分割の仕方
をもとめる。面積ＳＰはＳ　Ｐ＝ＭＸＮで表され、Ｎは定数であるからＭを最小にするＰを（２
）′と（３）から求める。（２）　”　＋３１よりＭ−
（（Ｐ−１）　／１ｎＰ）　１ｎＮ　　・・１４１ｄＭ
／ａ　ｐ＝　（１ｎＰ−（Ｐ−１）、　／Ｐ）　／＜ｘ
ｎｐｆ＝０　・・・・・・・・・・・・・（５）としてＩｎＰ−（Ｐ−１）／Ｐ　　・　・　・　・　・　・　
・（６）が条件となる。（６）式を満たすのはＰ＝１の
時であるがこれは（２）式を満足せず、Ｐは整数という
条件よりＭを最小にするＰはＰ＝＝２　・・・・・・・・・・・・・・（７）Ｍ−（
１／１ｎ２）ｌｎＮ・・・・・・・（８）となる。例と
して入力数Ｎ−２”＝１０２４の場合（８）よりＭ＝１
０となり、行線はわずかに１０本ですむ。第３図の回路
ではＮ−１＝１０２３本必要であったのと比較すると大
幅な面積の制約である。最適化されたＰ＝２の優先回路
を拡張用付加回路等を加えてできる優先回路５を第５図
に示す。

第５図では第３図と同様に行線は・印において交差する
列線のデータを入力としてＯＲアレイを構成し、列線は
○印において交差する横線のデータを入力としてＡＮＤ
アレイを構成する。入力１１〜Ｉ２−１はそれぞれＡＮ
Ｄアレイの入力として加える。第５図の横線ａおよびｂ
はこの優先回路の多段接続用の拡張回路で入力ＥＴは上
位優先回路の出力ＥＯに直接接続するか、一般のキャリ
ルックアヘッドジェネレータに接続することにより容易
に拡張できる。

具体的な回路としてはＭＯＳで容易に実現できる。

第６図に回路例６として行線９列線ともＮＯＲアレイに
し、入力Ｉ、〜Ｉ２鴫を負論理にした場合を示す。

また第７図に論理１と論理０とからなる２値系列を入力
したとき最も右にある優先順位の高い論理１の位置に対
応する出力を境にしてそれよりも左側にある出力をｘ印
のＯＲ素子ですべて強制的に論理１にし、それよりも右
側にある出力を○印のＡＮＤ素子ですべて強制的に論理
０にする優先回路７を示す、ここで・印は単に列線行線
の接続を意味する。

本発明の優先回路を連想メモリと組合せればアドレスデ
コーダの工夫やカウンタの付加等によって連想機能、す
なわちｋｅｙ部の一致動作の有効領域の指定や書込み動
作をスタック的に行うシステムができる。

第８図に本システム８のブロック図を示す。ここでデコ
ーダ１０は特殊である。従来のデコーダは入力Ｉ　’ｏ
〜−−１、出力Ｏｏ〜０ｆ−１との間には次の関係があ
った。

ただしＡ　”＝　Ｉ、、　２″＋−１＋　ＩＦｌ−、２
″−２＋・・・これを次のような関係が成り立つように
変更する。

このデコーダ１０は汎用のデコーダに第７図の優先回路
７を結合して実現できる。

デコーダ１０の出力１０１とｋｅｙ部２０の出力２０１
すなわち一致情報出力とは３０でＡＮＤされて第５図の
優先回路４０の入力となる。優先回路の出力４０１はＲ
ＡＭで構成される　ｖａｌｕｅ部５０のリード／ライト
アドレス線およびｋｅｙ部のライトアドレス線２０２に
接続される。まずｋｅｙ部およびｖａｌｕｅ部への書込
み動作を説明する。ライトアドレスはｋｅｙ部、　ｖａ
ｌｕｅ部共に共通で、カウンタレジスタ６０の値によっ
てアドレス順に指定される。アドレスデータは、前述の
デコーダ１０、ＡＮＤ回路３０．優先回路４０を経て、
ｋｅｙ部およびｖａｌｕｅ部のアドレス線が決定される
。

なお、書込みモードではｋｅｙ部の出力がａｌｌ″１”
であるようにする。従ってデコーダ出力は優先回路４０
によって（９）式のように制御され、カウンタレジスタ
６０のすケ定するＲＡＭのワード線のみが１″となる。

λ 次に探索モードについて述べる。この場合、カウンタレ
ジスタ６０はｋｅｙ部の一致動作の有効領域の境を指す
ポインタとして使用される。入力データはｋｅｙ部にお
いて記憶内容との比較が行われ、−数情報が出力される
。なお、マスクレジスタ７０は、入力データの任意のｂ
ｉｔを一致動作に対してｄｏｎ’ｔ　ｃａｒｅにするも
のである。　ｋｅｙ部の出力２０１はデコーダ出力１０
１とＡＮＤされて優先回路４０に入力される。デコーダ
１０の出力１０１が“１”である領域が有効領域である
。そして、優先回路４０によって優先順位の最も高いも
のが選択されｖａｌｕｅ部において対応したデータが出
力される。

このように書込みはアドレス順にスタック的に行われ書
込まれた領域が一致動作の有効領域となる。さらにカウ
ンタレジスタ６０にアドレスをセットすることにより、
任意の場所の書込みおよび任意の有効領域指定が可能で
ある。なお、ＡＮＤ回路３０は優先回路４０のＡＮＤア
レイに含めることができ、デコーダもアレイ構造によっ
て実現は容易である。

、　　　　　　　　第８図に示す連想は将来ＭＯ５ＬＳ
ＩＩチップで実現することは充分可能であろう。また容
量の点で不利な場合にはｖａｌｕｅ部を分離して、優先
回路出力にエンコーダを通すことによってアドレスの形
で出力し、　ｖａｌｕｅ部として外部にＲＡＭを用いる
ことも可能である。さらに前述の優先回路の拡張機能に
より、多段接続して大きなシステムにすることも可能で
ある。

４、図面の説明第１図は優先回路の入出力関係の説明図、第２図（ａ）
、　（ｂ）はそれぞれ優先回路の真理値表と従来の優先
回路の構成図、第３図は本発明の動作原理を説明するた
めの優先回路、第４図は本発明の詳細な説明するための
優先回路、第５図は本発明の分割法に従って面積最小に
なった優先回路、第６図はＭＯＳ）ランジスタを使って
実現した本発明の面積最小の優先回路の回路構成図、１
１８７図は優先順位の高い論理１の位置を境にしてそれ
よりも左側にある出力をすべて論理１にし、それよりも
右側にある出力をすべて強制的に論理０にする本発明の
優先回路、第８図は本発明の優先回路と連想メモリを組
合せて構成された連想スタックのシステム図である。

１・・・優先回路の概念図、２・・・従来の優先回路、
３．　４．　５・・・本発明の分割方法を示す優先回路
、６・・・優先回路の具体的囲路、７・・・境界領域を
与える優先回路、８・・・連想スタック、１０・・・デ
コーダ、２０・・・　ｋｅｙ部、４０・・・優先回路、
５０・・・　ｖａｌｕｅ部。

特許出願人　　　１）中　衡代理人弁理士　　大　管　義　之（（Ｌ）ｋｌＡｌ　　図１Ａ２図（（Ｌ）算２因　（ｂ）瀉　　６　　図ｆ′＝Ｏｒ　　　　０２　　　０３０４ｏ５ｏ６葛　７　巴

Claims

【特許請求の範囲】（１）複数の行線と複数の列線よりなるメモリ構造にお
いて、前記列線のうちある列線の論理状態あるいは前記
論理状態の反転論理を前記行線のあらかじめ定められた
行線に伝達することによって他の列線を前記行線と前記
列線との各交点に存在する論理回路で強制的に特定の論
理状態にすることを特徴とする優先回路。（２、特許請求の範囲第１項記載の優先回路において、
回路の機能を変えることなく前記メモリ構造の面積を最
小にする回路の分割手段。（３）記憶回路の出力に連結され前記記憶回路の活性化
された出力のうち優先順位の高い位置の出力のみを活性
化して出力する特許請求の範囲＄１項記載の優先回路。（４）記憶回路の出力に連結され前記記憶回路の活性化
された出力のうち優先順位の高い位置から低い位置にあ
る出力を順に選択する手段を有する階層構造の特許請求
の範囲第１項記載の優先回路。