37
計算機を用いた論理回路の自動設計
（第1報）
菅原英一。堅固山幸治
(昭和51年10月31日受理）
DesignAutomationofLogicalCircuitbyComPuter (1stReport)
EiichiSugawara, KojiKengoyama
1． 緒
言巨
論理回路の設計に関して現実的な問題は，複数の入力 始
に対して所用の出力を得ようとするとき，いかに低価格
に実現できるかであり，その実現のためには，与えられ
た論理式をできるだけ簡単なものとすべきことは異論の ないところである。本報告では，与えられた論理式を計算機を用いて一定 の規則に従って簡単化し，その最も簡単な論理式が得ら れたら,X‑Yプロッタによって記号化された論理回路 を相乗項の和の形で図形出力しようとしたものであり，
1出力の場合について一応の成果を得たので報告する。
2． 論理式の簡単化 2−1 簡単化の基準
最も簡単な論理式の定義はきわめて困難であるが，本 報告ではその目安として以下のような簡単化の基準を与
えることにした。
①出力は相乗項の和の形式とするので, OR回路は 必ず1個必要となる。
②AND回路の数が最少の論理式を最も簡単な論理 式とする。
③AND回路の数が等しいならば，各AND回路へ の入力数の総和が最少の論理式を最も簡単な論理式 とする。
④論理式には否定形の論理変数も含まれているが，
多くの場合は否定形の信号端子も同時に備えている ので， ここではNOT回路の多少を簡単化の基準と しては考慮しないことにする。
2−2入力データの形式 例えば,論理関数Fが
入力データの読込み
①︒
IhrvardChartの作成
必須項および選択項の決定
疵へ
選択項の有無
グ0、、①
有卜
■■■■■■■■■■■■■■■
最も簡単な選択項の組 訳項の組 合せの抽出
①
最も簡単な論理式の出力
終
図‑1 HarvardChart法による最簡化 の処理過程
で与えられるとき， このままでは計算機への入：
で与えられるとき， このままでは計算機への入力として 取扱えないので，論理変数の否定形は<＞で囲むこと にする。したがって， (1)式は計算機への入力データとし
F=(A+亙るC)･面｡D+F+B･(A･F+X･
で)＋瓦･面．(B･で十百・C) ・…………．･(1) 昭和52年2月
一・堅固山
38 菅原英一
ては次のように表わされる。
F=(A+<A>C)<B>D+<C+D>+B (A<D>+<A><C>)+<A><D>
(B<C>+<B>C)………(2)
2‑3 HARVARDCHART法
論理式の簡単化の方法としては，真理値表による直観 的な方法，論理代数を用いたCutandTry法,Veitch Mapによる方法,KarnaughMapによる方法,Quine‑
McClusky法およびHarvardChart法等が知られてい る。本報告では簡単化の方法としてHarvardChart法 を採用し,Chartの処理を計算機で行なうことにした。
R2'･vardChart法による簡単化の手順をブロック･ダ イヤグラムを用いて示すと図−1のようである。このブ ロック・ダイヤグラムに従って(1)式の論理関数（入力デ ータとしては(2)式）を例にとって，その手順と途中結果 を以下に述べる。
①RarvardChartの作成
すべての論理変数の組合せに対応する2進数を10 進数に置き換えてChartを完成する。たとえば，
否定形の変数には'0',そうでない変数には!1!を対応
させるので,A･宮｡Cに対してはllO1!という2進数 が得られ， これを1唯数に置き換えて'5Iとする。こ のようにして完成されたChartを表‑1に示す。②Chartの処理
③表−1のINPUTの欄は真理値表による関数
出力値であるから, INPUTがIO!の行は与えら
れた詣鯉関数に含まれていないことになる。した がって， この行は消去しても差支えない。この操 作としてINPUTが'O!の各行の10進数をI*Iで置 き換えることにする。ここまでの途中結果を示す と表−2のようである。一 幸治狸ハＵ へ︾︑Ｄ ︐０
ｎＢ０ ｎＣＯ ｍ︐Ｏ ＤＣ０ ︺︐Ｏ ︶︐０ ＰＣ０
座ｒしハＵ 地一ｍｌ ０
乱
０１２３４５０１２３４５６７８９１１１１１１ｍｍｍｍｍｍｍｍｍｍｍｍｍｍｍｍ
０１０１ １１００ ００１１ ０１０１ １１００ ００１１ ０１ ０１ Ｊ︐ ０１ ００ ００
J C k
オ l C−
表‑2 HarvardChart処理③
｜
J BCDCU
L］k＊＊＊＊＊0
、 0 ml
m2
ドｋ︐ １１２ ０＊＊
誹謝．０３４ ｍｍ ５６ ｍｍ
m7ｍｍｍｍｍｍｍｍ ８９ｍ皿腿圃Ｍ鴫
−
表‑3 HarvardChart処理⑥
一一
’
ＩＮＰＵＴ
■ⅡＩＩＩＩ８１１０ⅡｌｌｌｌｌｌｌＩ・■０６１０日 ＡＢＣＤｌ０１２３４５６７８９ｍｎ廻昭皿晦
ＢＣＤ−０１２３４５６７０１２３４５６７
ＡＢＤ−０１０１２３２３４５４５６７６７ ＡＣＤ−０１２３０１２３４５６７４５６７
ＡＢＣ
AAABBC
ABCDBCDCDD
〕 DDE， ＊＊淵
ＥＯＵ＊Ｃ＊︐＊Ｃ＊Ｂ＊﹄龍
１１
０１２３４５６７８９１１１１１１０１２３４５ｍｍｍｍｍｍｍｍｍｍｍｍｍｍｍｍ ０１０１０１０１０１０１０１０１００００００００１１１１１１１１１０１１１１００１１０１１０１０ ００００１１１１００００１１１１ ００１１００１１００１１００１１ ００００１１１１２２２２３３３３ ００１１００１１２２３３２２３３ ０１０１０１０１２３２３２３２３ ００１１２２３３００１１２２３３ ０１０１２３２３０１０１２３２３ ０１２３０１２３０１２３０１２３ ００１１２２３３４４５５６６７７ml
２３ ｍｍ
m4
︐ｍｍ︑ ５６７８
m9ｍｍｍｍｍｍ
０１２３４５１１１１１１
1■■■■■■■■■■■■■■
表‑1 HarvardChart
表‑4HarvardChart処理⑥秋田高専研究紀要第12号
ＩＮＰＵＴ１０１１１１００１１０１１０１０ＩＮＰＵＴ１０１１１１００１１０１１０１０ＩＮＰＵＴ１０１１１１００１１０１１０１０
I
計算機を用いた論理回路の自動設計（第1報）
39
一−
l ＊
＊ 0 ＊ 0 ＊ l ＊ 1 ＊
（） ＊
l ＊ l ＊ 0 ＊ l ＊ 0 ＊
ＡＢＣＤ ＢＣＤ
ＡＣＤ
始
ＡＢＤ
ＡＢＣ一＊＊１１＊︒＊＊４４＊＊＊＊＊＊ＣＤＯ＊＊＊＊＊＊＊０＊＊＊＊＊＊＊ＢＤ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ＡＣ＊．＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ＡＢ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ ＢＣ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ＡＤ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Ｃ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊Ｂ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ Ｄ｜＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
０１２３ ︐ｍｍ︑
0＊
＊＊
0＊
＊＊
＊＊
＊＊
＊＊
＊＊
＊＊
5 ＊
＊＊
5 ＊
＊＊
＊＊
。＊
＊＊
＊＊
＊＊
＊＊
3＊
＊＊
＊＊
＊＊
＊＊
＊＊
＊＊
＊＊
3 ＊
＊＊
＊＊
＊＊
＊＊
入力データの読込み
:; ￨ I６７８９１１１１１１
０１２３４５ｍｍｍｍｍｍｍｍｍｍ
AND回路への入力点座標の計算
論理変数および信号端子を描く 論理変数およ
表‑5 HarvardChart処理⑥
この変数に関し 座標の最大値点
この変数に関して信号端子からY
座標の最大値点まで直線を引く⑤次に各列を調べて，上の操作で!*Iに置き換えら
れた欄の数と同じ数があったら， これは前に消去 された論理変数と同じ変数を表わしているから同 様にI*Iで置き換えることにする。ここまでの途中 結果を示すと表−3のようである。、次に各行を左端から調べて，消去されていない
(I*!になっていない）項を見出し，その項の変数
をすべて含む消去されていない項をすべて消去す る。すなわち，表−3におけるmo行について調 べると，消去されていない項はCDであるから，これを含むACD,BCD,ABCDの3項を消 去するためこれらの欄を前と同様にI*Iで置き換え ることにする。ここまでの途中結果を示すと表一 4のようである。
④各行について消去されていない項が唯一つあれ ば， これは必ず必要な項(必須項という）であり，
この例では、5行目のABC列のI2!および、14行 目のABD列のI6'がこれに相当する。すなわち，
2!および'6Iを進表現に戻すとI10Iおよび'110Iとなる からxBでおよびAB万が必須項である。これら 必須項についてはその欄を'。'で置き換えること にする。このようにして消去されなかった項は選 択項として残り， この組承合わせによって最も簡 単な論理式が得られる。なお,上述の2項が必須 項として取上げられると， これらと同列にある同 値の項は選択項からは除去される。さらに， この 除去された項と同行にある未消去の項も不要とな るので除去される。除去の操作は前述同様l*Iで置 き換えることにすると， ここまでの結果は表一5
のようになる。
③選択項の組承合わせ 昭和52年2月
NO 全論理変数につい
エ直線を引いたか YES
相乗項の各変数に関して接続点 からAND回路まで直線を引く 相乗項の各変
からAND回
NO 全項について直
線を引いたか
ー
YES
OR回路を描 〈
出力端子と出力シンボルFを描く
終
図−2論理回路図の出力過程
前述までの操作で選択項がなければ必須項の象の 和が最も簡単な論理式となるが， もし選択項あがる 場合には，すべての組承合わせを調べて2−1の簡 単化の基準に合った組承合わせを決定する。
④出 力
必須項および選択項の組承合わせが決まったなら ば，それは最も簡単な論理式であるから出力する。
このような操作の結果，出力された(1)式の最も簡単な 論理式は次のようになる。
菅原英一・堅固山幸治
40
わち， (3)式の4変数の論理式の各項を(4)式のように対応
する2進表現で置き換えることにする。F=010｣+11uO+uuOO+001u+10ul…･･･(4) なお，上式でのuは空白を意味する。
3‑2 X−Yプロッタによる図形出力
図−2は(4)式をデータとして入力した場合のX−Yプ ロッタによる図形出力の処理をブロック・ダイヤグラム で示したものであり，その結果出力された論理回路図が
図−3である。A B C D
O O O C
4． 結 言
(1)式のような論理関数が与えられた場合， これを最簡
化の処理によって最も簡単な関数とし，さらに記号化された論理回路として図形出力するという初期の目的は一 応達成された。しかし， これは1出力についての承達成 されたということで，今後は多出力の場合についても最 簡化から図形出力という処理が可能となるようプログラ
ムの拡張を考えている。
F
図−3論理回路図の出力 F=X･B･で+A･B･万十百・万一 参考文献
一
十瓦･宮｡C+A･宮｡D……．．……･………(3) 3． 論理向路の図形出力
3−1 入力データの変換
2−3で得られた出力データを論理回路図作成の入力 とするため，以下のようにデータの変換を行なう。すな
1）当麻喜弘：ディジタル回路の論理設計入門 2）佐々木次郎，中野馨： トランジスタ・ディジタル
計算機の設理設計
3)MontgomeryPhister, Jr. :ディジタル計算機の
論理設計秋田高専研究紀要第12号
