JPH04239910A - 多入力最大値演算方法及びその装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ファジイ推論における
複数の入力値の最大値を高速に演算する並列最大値演算
方法及びその装置に関するものである。

【０００２】

【従来の技術】ロボットなどの制御にファジイ推論を用
いる場合には、実時間推論を行うための高速演算回路が
必要とされる。高速に推論を行うための工夫としては、
推論方法を簡略化し演算回数を少なくして高速処理を行
う方法（例えば特開平２−９３９３９号）や、前件部の
処理を工夫して高速処理を可能にする方法（例えば特開
平２−９３９４３号）等がある。さらに高速化するため
に、複数の演算器を並列に動作させる方法も考えられる
。従来、図４に示すように各ルールに対して最小値演算
を行った後の最大値演算は、複数の２入力最大値演算回
路（ＭＡＸ回路）４０，４０〜を木（Ｔｒｅｅ）構造に
接続して並列出力の一括処理を行っていた。２入力ＭＡ
Ｘ回路４０は図５に示すように、ビット比較器とトライ
ステートのバッファを組み合わせて実現している。ビッ
ト比較器としては、一般に、図６に示すようなアルゴリ
ズムに従って、例えば、入力値ＡとＢを比較する場合、
上位ビットからＢが大きくなる条件を選択して排除し、
それ以外の場合にＡ＞Ｂであるとする方法を用いてきた
。これを回路で実現すると、図７のようになる。同図波
線で示すビット比較器４１において、先に各ビット毎の
比較を行い、終段２段のＡＮＤ及びＮＯＲ回路によって
図６の条件判断を同時に行っている。

【０００３】

【発明が解決しようとする課題】先に示したように、従
来例にしたがって最大値を算出する場合、図４に示した
ようなＴｒｅｅ構造に従って、次段の２入力ＭＡＸ回路
において再び各ビット比較から始めなければならず、ま
た、入力数が多くなるほど多段になり、出力に現われな
い中間部での無駄な演算を数多く含むことになる。この
ため、入力数の増加に伴い素子数が増大し、また、多段
に接続されるため演算の遅れ時間が増し、高速演算の妨
げになる。

【０００４】本発明は、素子数を不必要に増大させるこ
となく、演算の遅れ時間を最小限に抑えた、高速に演算
し得る、並列最大値演算器を提供することを目的とする
。

【０００５】

【課題を解決するための手段】前記目的を達成するため
、本発明に係る多入力最大値演算方法においては、２以
上のデジタル入力値の最大値を演算する方法において、
全入力の最上位ビットを比較し、その中に１が存在する
場合には１以外の入力値の以下の下位ビットを全て０、
出力の最上位ビットを１にし、また、全てが０の場合に
は以下のビットを変更せず、出力の最上位ビットを０に
するという行程を、最上位から第２番目以降のビットに
対しても同様に順次行うことによって、最下位ビットの
比較が終わった時点で出力に全入力の最大値を算出する
ものである。

【０００６】また、本発明に係る多入力最大値演算装置
においては、２以上のデジタル入力値の最大値を演算す
る多入力最大値演算装置において、上位ビットにおける
演算から出力される最大値認識信号と全入力の各ビット
との論理積を演算する第１のＡＮＤ回路と、第１のＡＮ
Ｄ回路の出力信号と全ビット零検知信号との論理和を演
算するＯＲ回路と、最大値認識信号とＯＲ回路の出力信
号との論理積を演算し次の下位ビットの最大値認識信号
とする第２のＡＮＤ回路と、各ビット毎に全ての入力に
対する第１のＡＮＤ回路の出力信号を入力し、全ビット
零検知信号を出力するＮＯＲ回路と、各ビットのＮＯＲ
回路の出力の否定値を演算するＮＯＴ回路とを有し、各
ビットのＮＯＴ回路の出力を全入力の最大値とするよう
にしたものである。

【０００７】

【作用】まず、本発明の多入力最大値演算法について、
以下に述べる。ビット幅の揃った複数の入力値の最大値
を求める。最初に、各入力値の最上位ビットを比較する
。全入力値の最上位ビットに何れか１が存在すれば、そ
の入力値が最大値になる可能性がある。それがただ１つ
であれば、その時点で最大値が決定されるが、最上位ビ
ットの１の数が複数個の場合この段階では最大値がどれ
であるかは決定できない。しかし、最初の最上位ビット
の比較で１でなかった入力値は以下どのような値であっ
ても最大値とはなり得ない。そこで、順次下位ビットを
比較する前に、下位ビットの比較から除外させる。その
方法としては、以下の下位ビットを全て０にする。これ
によって、これらは下位ビットの比較において、最大値
として選択されることはなくなる。この処理を各段のビ
ット比較後に行ってから次の段のビット比較に進める。 この操作を最上位ビットから順次下位ビットへと行うこ
とによって、最終的には、全入力値の中の最大値が出力
される。最初のビット比較において全ビットが全て零だ
った場合は、最大値は下位ビットを比較しないと決定で
きないので、下位ビットを零にすることなく次のビット
の比較へと進む。

【０００８】本方式では、全入力に対し上位ビットから
順に１ビットずつ比較しており、その比較の結果最大値
の候補から外され多入力値の下位ビットを全て零にする
ところに特徴がある。これによって、下位ビットの比較
において、候補から外された入力値の比較ビットが１で
、かつ、最大値の候補の比較ビットが０である場合でも
誤認識することがない。また、本方式により上位ビット
から順に最大値を得ることができるので、最下位のビッ
ト比較まで行わなくても、おおよそ最大値（概算値）を
短時間に得ることができる。これは、従来法では不可能
だったことである。

【０００９】本発明は最大値演算の手法について述べて
いるが、最小値演算も同様の手法で行うことができる。 即ち、上位ビットから比較を行い、上位ビットが零でな
かった入力値に対しては以下の下位ビットを全て１にし
てしまうのである。以下同様に、下位ビットの比較を行
えばよい。

【００１０】本願の請求項２に係る本発明の並列最大値
演算装置について、以下に述べる。本装置は大きく２つ
に分けられる。１つは、全入力の各ビットを比較し、何
れかに１があるのか又は全くないのかを判定する全ビッ
ト零検知回路であり、もう１つは、最大値の候補を示す
最大値認識信号を用いて、各ビット毎に、上位ビットか
らこの信号を受け、各ビット比較の入力ゲートを操作す
るとともに、下位ビットにおくる最大値認識信号を生成
する役割をもつビット演算器である。ここで、特徴的な
のは、ビット演算器の構成である。図２に本特許の演算
装置に用いるビット演算器の詳細回路図を示す。２つの
ＡＮＤ回路と１つのＯＲ回路からなる。まず、第１のＡ
ＮＤ回路１において上位ビットから出力される最大値認
識信号と入力ビットとの比較を行う。最大値認識信号が
１ならば、その入力は最大値の候補であることを示して
おり、第１のＡＮＤ回路１の出力は各ビットの入力値の
状態が伝達される。もし、０ならば、上位ビットの比較
において他に最大値の候補があったため、下位ビットを
零にするような決定がなされたことを示しており、第１
のＡＮＤ回路１の出力は入力の状態に拘らず０になる。 最上位ビットの比較においては、最大値認識信号として
は全て１を入力する。

【００１１】一方、全入力の第１のＡＮＤ回路１の出力
は全ビット零検知回路（図示しないＮＯＲ回路）に接続
される。ＮＯＲ回路は全ての入力値が０のときのみ１を
出力する。

【００１２】全ビット零検知信号は第１のＡＮＤ回路１
の出力とともにＯＲ回路２に接続される。第１のＡＮＤ
回路１の出力が１であれば、これは最大値の候補であり
、ＯＲ回路２の出力には１が伝達され、従って、入力し
た最大値認識信号と比較する第２のＡＮＤ回路３の出力
にも１が送られる。

【００１３】一方、第１のＡＮＤ回路１の出力が０にな
るのは、最大値認識信号が０か、又は、最大値認識信号
は１であって、入力値の０の場合のいずれかである。前
者は最大値の候補ではないことを示しており、この場合
は第２のＡＮＤ回路３を通して直接最大値認識信号に０
が出力される。しかし、後者の場合は、ビット比較を行
った際の他の入力値の状態に影響される。即ち、他の入
力値のビットも全て零の場合は全ビット零検知信号が１
で返され、ＯＲ回路２の出力は１となり、第２のＡＮＤ
回路３の出力、即ち最大値認識信号も１となるので、最
大値の決定は下位ビットでの判断に委ねられる。しかし
、第１のＡＮＤ回路１の出力が０であっても、他の入力
値に１があり、他に最大値の候補が存在する場合、全ビ
ット零検知信号が０になるので、ＯＲ回路２の出力も０
になる。結局、上位ビットからの最大値認識信号が１で
あっても、第２のＡＮＤ回路３の出力は０となり、この
入力値は最大値の候補から外されることになる。

【００１４】最終的には、最下位ビットまで最大値認識
信号に１を送り続けた入力値が最大値ということになり
、最大値が複数ある場合には最大値認識信号も複数１が
存在する。そして、最大値そのものは、次のように得る
ことができる。

【００１５】各ビット比較において、どこかの入力値が
１を出力する限り全ビット零検知信号は０である。逆に
全ビット零検知信号が１の場合、それが最上位ビットで
あれば、全入力値ビットが０であることを示し、また、
それが下位ビットであれば、少なくとも最大値の候補と
して残されている入力値の全てについてそのビットが０
であることを示している。従って、最大値は、全ビット
零検知信号の否定をとることによって得られる。

【００１６】本装置の特徴は、この同じビット比較器が
最上位ビットから最下位ビットまで従属に接続が可能な
点にある。同じ構成単位の回路を組み合わせることによ
ってビットの拡張が容易にできる。さらに特徴として、
ビット毎の第１のＡＮＤ回路１の出力をＮＯＲ回路に接
続することにより、全ての入力値を同時に比較すること
ができる。即ち、多入力の任意なサイズのビット数に対
して並列演算が可能な点も特徴としてあげられる。

【００１７】

【実施例】本発明の一実施例を図１及び図３を用いて示
す。図１は、本願の請求項１に係る本発明の多入力最大
値演算方法の一例を示すアルゴリズムである。これは複
数のデジタル入力値のなかの最大値を求めるものである
。先ず、最初の条件判断において、全入力に対し最上位
ビット（ｎ＝１に相当）同士を比較する。その中に１が
あれば、出力の最上位ビットを１にする。そして次に、
最上位ビットが０だった入力値の以下のビットを全て零
にする。１ビットずつ、又は、入力値そのものを０で置
き換えても同じことである。一方、最初の条件判断にお
いて、最上位ビットに１がなければ、即ち、最上位ビッ
トが全て０だった場合は出力の最上位ビットを０にする
。この後、２番目の条件判断に進む。単に比較するビッ
ト数をモニタしている。最下位のビットに達していたら
、「終了」に進む。入力値が４ビットデータならば、ｎ
＝４のとき、最下位と判断する。最下位でなかった場合
は次に進み、ｎをカウントアップして、最初の条件判断
に戻す。すると、今度はｎ＝２、即ち、第２番目のビッ
トの比較を前回と同様の方法で行う。結局、最終的には
最下位ビットの比較を終え、終了した時点で出力に最大
値が現われる。この方法を用いることにより、各入力値
の各ビットはただ１回比較されるだけでよく、無駄な比
較を繰り返し行う必要が無くなる。

【００１８】次に、本願の請求項２に係る本発明の多入
力最大値演算装置について、その一例を図３に示す。図
３は、４ビットの入力値４つを同時に比較し、４入力中
の最大値を求める回路図である。図２に示したビット演
算器を４ビット分従属接続し、それを４入力分設け、最
上位ビットから、各ビット毎に第１のＡＮＤ回路１の出
力を全ビット零検知回路である４入力ＮＯＲ回路４に接
続している。ＮＯＲ回路４の出力４ビット分は、それぞ
れ。ＮＯＴ回路５を通して全入力中の最大値として出力
される。

【００１９】入力数を拡張するには、ビット比較器をビ
ット幅分従属接続詞、それを入力数分拡張し、それぞれ
、第１のＡＮＤ回路１の出力を全ビット零検知回路に接
続すればよい。

【００２０】本回路の特徴は、全入力値の全ビットがた
だ１回だけ比較されることにあり、従来のＴｒｅｅ構造
に見られるような無駄な比較はまったく行われない。し
かも、下位ビットを零にするかどうかの判断も全ビット
零検知信号を利用してどのビットも同一の判断方法に統
一されており、その結果を最大値認識信号として最上位
ビットから最下位ビットまで一貫して管理できるところ
にある。従って、最下位ビットから出力される最大値認
識信号をモニタすることにより、どの入力値として出力
されたかが分かる。これは、従来のＴｒｅｅ構造のＭＡ
Ｘ演算器では、成し得なかったことである。

【００２１】また、この回路はクロックを必要としない
ため、１クロックの信号処理の途中に設けることにより
無駄なクロックを追加する必要がない。さらに、最小限
のビット比較で演算結果が得られるので演算の遅れ時間
を最小限に抑えることができ、高速な動作クロックを維
持することができる。

【００２２】さらに、従来のＴｒｅｅ構造では最終段の
２入力ＭＡＸ回路の出力まで待たなければ、概略的な最
大値を得ることができなかったが、本回路の特徴は、さ
きに述べたように全ビット同時に最上位ビットから比較
していくので、演算結果も最上位ビットから得られる。 従って、大ざっぱな最大値が必要な場合、上位ビットか
ら必要なビット数分だけの比較を終える時間さえあれば
、あまり重要でない下位ビットの演算を待たずに次のス
テップに進ませることも可能である。これは、曖味なデ
ータを扱うファジイ推論において、入力値のデータ幅が
大きくなる大規模演算の高速化を考える上では重要な手
法である。

【００２３】以上、多入力最大値演算装置についてその
回路例を示したが、最小値演算も少しの変更で実現する
ことができる。即ち、入力値の各ビットの入力の際に全
ビットをＮＯＴ回路を通して入力すればよい。即ち、一
度否定しておいて最大値を求めれば得られた結果は最小
値になる。また、最下位ビット比較後の最大値認識信号
に１が残されている入力値が最小値であることを示して
いる。

【００２４】

【発明の効果】本発明の最大の特徴は、並列演算指向の
手法による演算の高速化と無駄演算の排除にある。そこ
で、ここでは先ず、演算の遅れ時間で高速化の度合を比
較する。ファジイ推論を並列に行う場合、ルール数分並
列演算を行うと、最大１２８ルール程度の入力数を処理
しなければならない。そこで、１２８入力のＭＡＸ回路
を考える。従来方式では、７段のＴｒｅｅ構造（格段は
図５に示すような比較器とバッファで構成される）のＭ
ＡＸ回路になる。比較器の内部構造は図７に示すように
５段である。トライステートのバッファを最低１段以上
の論理回路からなるとする。７段階層のＴｒｅｅを通し
て出力を得るまで最低４２（＝（５＋１）×７））段以
上の論理回路を経なければならない。一方、本発明の並
列最大値演算回路は図３の最下位ビットの出力段までで
１５段必要であり、入力数が１２８個に増加しても基本
的には１５段でよい。この場合、ＮＯＲ回路には多くの
入力部が必要となるが、ＮＯＲ回路は内部構造が簡単で
、段数を増やさずに多入力構成にできるので、段数の増
加はないものとする。この場合、全体では、段数を従来
の３６％に削減できる。

【００２５】次に、無駄演算の排除について示す。基本
的に本発明の並列演算器は従来方法のＴｒｅｅ構造の第
１段だけを行うに等しい。従って２段目以降が無い分だ
け演算器を少なくできるが、最大値認識信号と全ビット
零検知信号を得るための演算器が別途必要である。そこ
で、両者の比較を演算器の数で行う。従来、比較器に２
０個、バッファで５個の演算器が必要である。７段階層
のＴｒｅｅ回路では１２７個の２入力ＭＡＸ回路が必要
であり、全体では３１７５（＝（２０＋５）×１２７）
個の演算器が必要となる。ところが、本演算器では１２
８入力でビット比較器が１５３６（＝３×４（ビット）
×１２８）個、さらに、全ビット零検知回路のＮＯＲ回
路が４つで、合計１５４０個の演算器が必要となる。従
って、演算器の数を従来の約半分に削減することができ
る。

【００２６】以上に示したように、本発明の多入力演算
器を用いることにより無駄の無い高速演算器が可能にな
る。この手法は特に演算規模が大きくなる場合に有効で
ある。

【図面の簡単な説明】

【図１】本発明に係る多入力最大値演算方法の一実施例
を示す図である。

【図２】本発明に係る多入力最大値演算装置を示す図で
ある。

【図３】本発明装置の具体例を示す図である。

【図４】従来のＴｒｅｅ構造の最大値演算回路を示す構
成図である。

【図５】従来の最大値演算回路の具体例を示す図である
。

【図６】従来の比較器の比較方法の一例を示した図であ
る。

【図７】従来の比較器の内部構造の一例を示した図であ
る。

【符号の説明】

１　　第１のＡＮＤ回路 ２　　ＯＲ回路 ３　　第２のＡＮＤ回路 ４　　ＮＯＲ回路 ５　　ＮＯＴ回路

Claims (2)

【特許請求の範囲】
1. 【請求項１】　　２以上のデジタル入力値の最大値を演
   算する方法において、全入力の最上位ビットを比較し、
   その中に１が存在する場合には１以外の入力値の以下の
   下位ビットを全て０、出力の最上位ビットを１にし、ま
   た、全てが０の場合には以下のビットを変更せず、出力
   の最上位ビットを０にするという行程を、最上位から第
   ２番目以降のビットに対しても同様に順次行うことによ
   って、最下位ビットの比較が終わった時点で出力に全入
   力の最大値を算出することを特徴とする多入力最大値演
   算方法。
2. 【請求項２】　　２以上のデジタル入力値の最大値を演
   算する多入力最大値演算装置において、上位ビットにお
   ける演算から出力される最大値認識信号と全入力の各ビ
   ットとの論理積を演算する第１のＡＮＤ回路と、第１の
   ＡＮＤ回路の出力信号と全ビット零検知信号との論理和
   を演算するＯＲ回路と、最大値認識信号とＯＲ回路の出
   力信号との論理積を演算し次の下位ビットの最大値認識
   信号とする第２のＡＮＤ回路と、各ビット毎に全ての入
   力に対する第１のＡＮＤ回路の出力信号を入力し、全ビ
   ット零検知信号を出力するＮＯＲ回路と、各ビットのＮ
   ＯＲ回路の出力の否定値を演算するＮＯＴ回路とを有し
   、各ビットのＮＯＴ回路の出力を全入力の最大値とする
   ようにしたことを特徴とする多入力最大値演算装置。