九州大学日高

論理関数の対称論理関数による最適表現とその応用

（昭和51年5月3］日 原稿受付）

九州大学日高  ^達

情報工学教室  江    口    賢    和

Representation of a Switching Function by a Symmetric Switching

       Function and its Application

      by Toru HITAKA       Yoshikazu EGUCHI

  Any switching function can be written as a totally symmetric function with some of its variables being repetitive． In this paper， a procedure for hnding the totally symmetric representatim for a given function that has山e minirnum number of variable8 is presented． And then， its applications to the prob】em of synthesizing a switching function with netwoTks of threshold elements and with network5 0f three−input majority elemems are 5hown by c加αete examples．

       る論理関数5、（晶，エ2，力，エ3）に等しくなる。この場合．

Lまえがき        靱5属．，コ，，為）描酬鱈（。．．、、．，）の4鞭

論理関数を対称論理関数を用いて表現する問題は理描   対称論理関数54（泊，エ2，口，エ、）による表現とよぷ。表現 的興味以外に，その応用として諭理関数の合成問題が考   54（fl，エ2，力，エ3）はつぎのようなことを意味している．

られる。       すなわち，4変数対称論理関数54（エ1，浜，ゐ，エ、）の合成  ある演算紫子で論理回路網を合成する問題（論理回路   回路において，入力屯、泊，泊，山をそれぞれ入力ヱ1，泊，

網の合成問題）では，すべての論理関数に対して効果的   泊，口で置き換えると回路の出力として瓦（泊、兵，為）が な合成法を発見するのは難しい場合が多い．このような   得られる。

場合には，先ずあるクラスの誼理関数に対して効果的な    論理関数を対称論理間数を用いて表現する場合，対称 合成法を研究し，つぎにこの合成法を一般の論理関数の   論理関数の変数の個数は，表現される側の論理関数の変 合成法へ拡張することがしばしば行なわれる。このよう  数の個数以上になる。一般に、対萄：論理関敷に対する合 な論理関数のクラスとLて，i頂算機能が豊富で，比較的   成問題でほ，変数の個数が多い対称論理閲数ほど合成に に構造が簡単で理論的に取扱い易いことから，対称論理   必要な回路素子数（または設廿手順）が増える傾向があ 関数のクラスが選ばれることが多い。      る。したがって，論理関数を対称論理関数によって表現  本稿で議論される，論理関数の対称論理関数による旺   する場合，（その論理関数を表現可能な対称論理関数の 適表現は，対称鵠理関数のクラスに対する効果的な合成   中で）変数の個数力「IRも少ない対称論理関数による表現 法を一般の論理閲数の合成法へ拡張する手段となるもの   （以後，簡略に最適表現とよぷ）を求めることが要求され である．      る。

 たとえば，3変数論理関数昂（泊．エ2，エ3）＝苅轟鳥    本稿では，先ず最適表現を求める方法（最適設計）を

〉巨、v泊巨，は，4変数対称論理関数＆（拍，．r2，泊，エ・）  与え，つぎに3入力多数決素子回路網の合成問題および

＝晶ま2f迂、∨（工2」じ3陥∨」τ1工3工4VJr1工2工4 V工1工2」「3｝にお   しきい値素子論理回路網の台・成問題への応用を具体例を

いて， 変数泊を晶で、変数工、を為で置換して得られ   示し述べる．

    2 最適表現      凡＝抑〈5用〉となるとき。そのときに限り，F．は5間     、鋼の郷数翻．，．…両℃論理和臓理積， によ・て表現される（8・は孔竺現可能である）と言

   論理否定噸をそ蜘∨・パ（二）で剛簡㌶蕊蕊撚鷲魏撒誌蕊

   略のため、泊∧乃等はくを省略して簡単に泊抱と略すこ

       現は無数に存在する、その中で，変数の個数が最少な対    とにする。また，」変数論理閲数をE，G．等で表わす。

   変数および論理徽は二値とL噛匡伽を偽値とす 繊理撒こよる表現を品の聯現とぷ

   る．π個の変数の値の組は，刀次元超立方体の頂点として

      ＿       例2．

   ㌶還あ慧蕊熟；三芦㌶  （1・2）〈一＆〉＝三：驚≡v

   成分は1，または0である。η変数論理関数の入力ベクト

   ルの全体を凡入力ベクトルρの第∫成分を〔ρ」謡 〔定馴   

一

理1熾棚値をとるよう G入力ベクト・レの全体を㌫㍑｛：㍑㌫：：↑：㍑㌣

  長1（1｝，凡が1ム値をとるよりな入力ベクトルの全体を

   片1（0｝と記す。      盟・ρ一苗・ρ 字O

    〔定義1〕対称論理関数の表現      である。ただし，・はベクトルの内積の演算記号である．

   た漂禦腰㌫霊輌合醐A酬ll：ll：1蒜㌶）…，，）｝

   ＝｛・・画……｝とすると・・5・旗伽をとるのは・ と仮定する．このよう1、仮定しても翻の一般性は井nな

   適当なロ」ε・4が存在して・丁度砂個の論理変数が真値1   われない。

   をとり・他の，1一叫個の論理変数が偽値oをとるとき・そ    脚は凡の表現ベクトルだから，摺＝lI｛，、1＋11司＋…

   のときだけである・       ＋1：0。1変数の対称論理関数刀5．が存在し，

   以上の定義より，

      F』＝1丑〈4s回〉．

     占S訓1）＝｛ρ1ρdVη，Σ2。、〔ρ〕A＆4｝

   である。      よって・任意の入力ペクトルρd㌃1（1）に対し・

    例1・      1助l    l地1

       へ

     一・s・＝」1ヱ・」・v（・1エ・∨・・為v・・エ1）・   ．s。（〔ρ〕1，…、〔ρMρ〕，，…1〔ρ〕、．…，

      ＿      1脚 l      l勘．11

 対称論理閲数β。は，集合Aを特に明ホする必要のな    ＿一一＿  ＿

い場合には，Aを省略して，単に5πと記すことにする．   〔ρ〕 … ｛ρ〕」・1−〔ρ〕1＋1・…・トー〔ρ〕田・…・

 〔定義2〕 対称論理関数による表現       h砺1

_勧・（ ＝】，2，…，，1｝は整数とし、      1−〔ρ〕。ド・・コー〔山）司

      1〃＝（批，晦，…，1砺），       だから，

      ロ       ベ      ロ

      m＝1助1÷1恥1＋…＋11ρ。1，       1D・ρ＋Σ1↓ 」．1＝Σ1ρ占〔ρ〕凸＋Σ1π川（1−tρ〕・〕

       エ よナコ      ムロバ       よロロヤベ

     ㎡＝｛1二窯1㌶  同様｛、＿意の入力ペクトル晒蒜」し，

とする。すると．口く5問〉は、m変数対称鐙理関数5厨        聞・〆＋ Σh￡叫か4．

      エヨかロ

の酬個噛醒数を・漁圃個の論酸数鰯℃ よって，甜・ρ㌔，〆とな・），綻理端立する．

・岡働論醒数を・：で鰍して得られ磁理鵬      （証明終）

である。       〔定理2〕

 1副＋1地1＋…＋1副＝m．かつ・各批が整数である    ，1本元ベクトル却＝｛勘，姫，…，脚。）は，各成分仙

ようなH次元ベクトル叩＝（批，識，…，齢）が存在し，    が整数で，かつ，任意のρεF㌃1（1）と任意のρ ε苦1（0｝

に対して，      step 2， lrull十11P21十…＋il凸1＝加であるような整数の        却−ρ一ω扇〆キO      H組（臥，伽，…，2｛のをつぎつぎに発生させ，

とする。このとき，      6（凡）に属するすべての関数の値が0にならない  ，H＝1 σ11＋1t｛戊・1＋…＋11u・1，       ような整数の，〜組（勘， rむ2，…，識）を捜す凸その  A＝｛！ρ・ρ＋Σ・．・。1〜o・11ρεFご1（1）｝      はうな｝r組が求まればstep 3へ進み，求まらなけ に対し，       1れば，ηr，1＋1にして再びstep 2へ戻る。

       F』＝田＜βm＞      step 3．．step 2で求まった整数の， 組を（地，ω2，…，

である。      砺）とし，η次元ベクトル田を苗＝｛抽，勘、…，

（証明）      …）とすると・仰幽1＋圃＋ ＋岡酬［が

A・一｛ぱ＋Σ＿．岡1ρ 。烈・n    最小な品の翻ペクトルである・したがって・

とおく．任肋ρ，濫1｛1）と任意の， ，宮1（。）1、対し，  鯉2で述ぺたよう妨絃聞よ1）・・＝1・・11 岬一岬幸。であるからぷ剖と胎酌ま互い  ÷1…ト ＋II・・麟の端論理関数・5・を求め・

、素（di，1。i。t）である。        醐唖表鋤〈・5・〉をf｛｝る・

 いま，G，＝苗＜A5m＞とおくと，定理1の証明と同様

にして酷融ρ，G；1｛1）と任意のゴ，G三1｛・）に対して， 例4・髄設計

      、。．。＋Σ＿。岡崩．     呂＝エ・繍∨漁vエ・L

      パ＋Σ＿．1，輌・．    竃四＝｛却1，一・・「f）一1・」・・1・1＋1・・，・・ 1−1…

       ω2＋1恥．1σ2−1砺，勘＋甜±÷！肪．助＋1L，空一ぬ｝

以上のことより，

ρd㌃1（1）1ρ ，呂1（o）とな1）、よって，    ・1＝』1＋11晦1＋1…1≦3であるような¶緻・・1、…，

馬＝G．＝担〈λ5問〉となる。        ｛証明終〕  鵡では，音（・呂）に属するいずれかの式が0になる・

 〔定義3〕       川＝4，すなわち・軌＝−L艶＝1・貼＝2のとき・

 ，r変数論理関数凡に対し，各係数が1，−1，または   審（1弓）に属するいずれの式も0になちない・よって・

0であるような，変数〜σ1，〜ロ2，…，r〃冒の一次多項式の集       ハ＝←ユ1・1・2）〈｛・・3・・，5・〉

集合審〔1『司をつぎのように定義する。       はF』の最適表現である・

欄些｛裏・（［ρレ〔〆鋼ρξ古 川 με ｱ剖 撚，畷論理関数を同値関㈱別し．各類を

ただL実数・≒°が存在して」＝・・であるよ櫛 代表する221個の噸論理関数に対して電子計算機を用

      最大12変数，平均7．50変数の対称論理関数によって表現

欄嘱する噛頻式では培係数は一1・°・ されること力励。た姫麟現がぽ錯の対称鋼

または1であることからぷ凡）に属する一次麺式の個 関数による表現になるような4変麟酬数は4つあっ

数は恒｝∫2以下である・     たが，その中の一つを例5に示す．

       例5．

   品＝加・∨エ1ヱ・・      ｛エ1エ，∨ヱ、1τ、∨fl」，［f3 v五）∨泊島脳、

   、F㌃1（1）＝｛（1，0｝，（0，1）｝，

       ＝（−1，5，4，2）〈lo山耶．6剤51言〉、

   古1（0）＝｛（0，0），（1，1）｝，

   魯四一｛＿，｝．     つぎ鴫馴本節噸表現を求める手順秘らず

      終了すること，すなわち，任意の論理関数に対して．そ

定融鯉2よい変麟馴数島の最醐を の最適翻が存在することを示している．

勅る1・ははのようにすればよL こと粉る・  〔定理3川櫨酬数｛、よる韻の髄

       任意の論理関数冗，に対し，凡を表現可能な対称論理 Slep 1古より一次多項式の綱］舗孔）を勅る・関数が存在する．

   また，η1・−1にしてstep 2へ進む。

例3．

鯉3の醐は・㌍（2°訊2コ∵ ・2n一り雄意の，・     X、1叉1

変数論理関数の表現ベクトルであることから自明である。

 3．合成問題への応用

       X3 1      0 ×3

 この節では，論理関数の合成問題への応用を実例を用

いて示す。

3．13入力多数決素子回路による蛤理関数の合成  対称論理関数に対する合成法としてはS．Amarelの合

成法を使用する。      N  S．Arnarelの合成法1｝

 3入力多数決論理関数を＃（泊，垣，均）と記し，卯変数

対称詮理閲数｛。，。丁1，．揺，一，叫5．をS9で表わす。すると，

59＝＃Cr月，5ξ吐， S 9＿1）となる。これはH変数対称詰i理

関数59が1個の3入力緻決素子と（，1−1）麹対称論     F・

理関数5ξ．1，5ξご｛の合成回路によって図1の｛1）のよ     図一2 3入力多数決素子と否定素子による       F3の合成回路

うに構成できることを意味する。したがって，この操作

を繰返し適用すオτぱ・3入力多数決素子回路網によつて    S．Amarelの合成法を，本稿の最適表現を用いて＿般の

S部合成できる・訟・一般の対称論酬数は  論酬数聞する紬法1、端するとき、つ軸照を

1妬・。＋1．一．α。一㌔・1、・1・1．一，・1−★1．…、d，．α。古一、α戸相S・      用いると能率がよい自

  ＝S㍗・←VSξ‥肝［V…

      （軌，r砺，…，1砺）＜S5＞

      ∨s9 ・研π    ＝＃（エ：，（r凸， H，，，…，1μ。．，）＜sξ二聞1＞，

であIL AND（．10R（v）は図1の｛2L｛3｝のように3    （甜1・・… ・1・・−1）〈5』〉）

入力多数決素子で合成できるので，一般の対称論理関数    いま，3変数論理関数

5。は否定素子と3入力多数決素子を用いて合成できる。        瓦＝晶」ユ∨エ1（エ耳，∨晶エ3）

以上がS・Ama「e1の合成法の継である・   を3入力多数決素子回路；、よ。て合成してみよう．

S二1X網后・叫51餌 E｛こ対璽燃1；）〈＿＆〉

       となる。これに上述の関係を使うと，

       」㌔＝（−1． ユ， 2）＜11．2｝54＞

      ＝（−1、1．2）〈5い思〉

      ＝（−1，ユ，2｝＜51＞・（−1， 1．2）〈百…「 〉       ＝・（−1，1，2）〈5i」〉・（−1， 1．2 ＜54＞

      ＝＃（O．（−1，1．2）〈5］〉，

5：       F「Gn     FnV Gn      て＝丁：土L 川    ｛2｝   （3）   （−1，1．2）〈5］〉＝＃（エ，，｛−1．1）＜5；1＞，

田＿13入力錯決糠子による         （−1コ）＜51＞｝

     論理関数の合成      二＃（力，1，（−1．1）〈5』〉），

       （−1，1）〈S』〉  ＝＃（エ2，｛−1）〈5『〉，

      （−1）〈S｛〉）

＝＃（エ2，ユ，ヱ1），

（−1・L2）〈5量〉＝＃｛エ・・〔−1・1）〈5；〉・    3   −41  F、

      （−1コ）〈5≧〉）         11         1

        ＝＃（エ3，（一工，1）〈5］〉，0）

となるから，3入力多数決素子と否定素子によるEの合

成回路網は図2のようになる。       XI X2 ×3 ×3   ×1 ×2 ×3 ×3 3・2 しきい値素子回路による論理関数の合成       図一4 しきい値素子によるF3の合成  対称論理関数に対する合成法としてはRC， Minnick      回路

の合成法を使用する。

RC Mimickの合成法4）       いま、最適表現を用いてR． C． Minnickの合成法を拡張 n変数対称論理関数      し，3．1における論理関数抗を合成してみよう。

 ｛・。、・一凸・一。．α1．・倒．一．・1桐告砺・．＋に・・．α。・耐Sπ      瓦＝（一］，ユ芦2）〈11．2β4〉

に対して，R・CMmickの回路構成は図3に示されるよ   となるので，論理関数携は図4の回路構成で合成できる。

うに二層回路網で，各しきい値素子への入力エ （∫＝1，2，

…，ぱ対す砥みはすべて1であり，しき剛丁，およ 4ぽと力寸き

び第一層の出力から第2層への入力に対する重みCfはそ    与えられた誼理閥数を，変数の個数が最小な対称論理 れそれっぎのような値である。      関数を用いて表現する方法（最適設計｝を示し，すべて

 T〆＝の十舟r十］， ＝0、1，…、カ Tρ，1＝σ。

 巳＝αr一θ∫、1、1＝⑪，1，…，♪−1

   ｛：−H−1：露：：：1㌶：

の4変数論理関数に対して，計算機を用いて最適設計し た結果を示した。

．      最適表現は，対称論理関数に対する効果的な合成法を、

一般の論理関数に対する合成法に拡張する際の拡張手段 Cp＝      となることをR、 C、MinnickおよびS． Amarelの合成法

を用いて示した。

 本稿における最適表現を求めるための手順は，与えら 拍一層        第二層         れる論理関数凡の変数の個数，rが大きくなるにつれ，臨        大なものになってゆき実際的でなくなる。したがって，

X  l To       大きな」1に対しても・それ程手順が増大しない近似解を

求める方法を開発することが必要である。このことにつ いては別の機会に発表したいと考えている。

X  lT        〔七

1      囲     n

1 1   qT 5    参考文献

l      D日高．江1コ声理噛碑1称齪畑数による最適表現、

｛       信学担一トマト・・端lf資，1A・酬19・・一・・｝

l       x     2）蹴江1コ：・鋼！関鋤）芒釧喘理1雌によ韻現・

       1、1亡芦会・， オートr7トンと書il吾t支報， AL75−31〔1975［10）

X lTp      3｝s・Ama・・LG・c・・k…dR・o・wi・d・・；M・j・・ityG・t・

       Network5，1EEE Trans−， EC−13． pp．卜13（196・1｝

      4） R．C．1∀1illllick； Lincar・lnput Logic， IEEE TI alls， EC一

図＿3Mi。。i，kの方部よ酬繊理   °・PP6 16（1961〕

    閲数の合成回路