パストランジスタ回路の網羅的列挙による素子数最小回路の探索

情報処理学会

書誌事項

タイトル別名
  • Exploring Minimum Pass Transistor Circuits Based on Exhaustive Enumeration

説明

パストランジスタ回路のような導通/非導通のスイッチを自由に接続し作成される論理回路を変数ラベル付きのグラフ構造でモデル化した際に，指定したサイズ以下のグラフで設計可能な全ての論理関数を網羅的に列挙する方法について述べる．ある論理関数を最も少ない素子数で表現するパストランジスタ回路を探索する方法や，パストランジスタ回路になるためのグラフ的性質や論理関数の同値類と呼ばれる特徴を用いてアルゴリズムの高速化を図る手法などの研究内容を示す．また，本手法を適用することで列挙されたグラフを用いて，3 入力までの論理関数を表現する最小のパストランジスタ回路を明らかにする．

We model pass-transistor circuits with the graph whose edges are labeled with input variables, and we show a method of exhaustive enumeration of all Boolean functions designed by the graphs bounded by a given size. We also show a method for finding the minimum pass-transistor circuit that represents a given Boolean function, and discuss the way to speed up the enumeration algorithm based on some properties of graphs and NP-equivalent class of Boolean functions. Finally, we show a catalogue of the minimum pass-transistor circuits that represent all three-input Boolean functions.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ