整数計画法を用いた多値Tゲート回路網の合成

亀山 充隆  樋口 龍雄  

誌名
電子情報通信学会論文誌 D   Vol.J65-D   No.3   pp.410-417
発行日: 1982/03/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(628.4KB)>>
論文を購入




あらまし: 
多値論理回路網を系統的に実現するモジュールの一つとして,多値Tゲートの有用性が知られているが,本論文では,最小のTゲート数で,任意の論理関数を線形整数計画法により合成する手法が提案されている.一般に,論理回路網の合成は非線形問題となるが,これを線形問題に帰着させるために,多値Tゲート回路網におけるULMインプリカントが定義されている.これらのULMインプリカントが必要とされるTゲート数の最大の減少を与えるような両立集合のすべての組合せを,陰的に列挙することにより,最適な解を求めるアルゴリズムが示されている.次に,樹枝状構造において,共通な出力も使用することにより,Tゲートの個数を減少させる合成法が示されている.このため,共通項インプリカントが定義され,これらすべてのインプリカントに対する最適な両立集合を求める系統的手法が明らかにされている.最後に,以上の合成法に基づき,多出力関数の最小実現のための定式化と合成例が示されている.