論理関数の共有二分決定グラフによる表現とその効率的処理手法 Shared Binary Decision Diagrams for Efficient Boolean Function Manipulation

この論文にアクセスする

この論文をさがす

著者

    • 湊 真一 MINATO S.
    • 京都大学工学部情報工学教室 Department of Information Science,Faculty of Engineering,Kyoto University
    • 矢島 脩三 YAJIMA SHUZO
    • 京都大学工学部情報工学教室 Department of Information Science,Faculty of Engineering,Kyoto University

抄録

論理関数を効率よく表現し 論理演算を高速に行うことは 論理設計支援システムを実現する上で重要な問題であるAkersやBryantが提案した二分決定グラフによる表現法は 入力変数の順序を固定することにより論理関数を一意に表すことができ また 多くの実用的な関数を比較的コンパクトに表現できるさらに 複数の関数を同時に効率良く表現できるように改良したものを共有二分決定グラフと呼ぶ本論文では 共有二分決定グラフを用いた論理関数の処理手法について述べ その効率化手法として 否定エッジ 入力反転エッジ 変数シフトエッジの3種類の属性エッジを用いて記憶量や処理時間を削減する方法を提案する共有二分決定グラフにおいては 入力変数の順序づけはグラフの大きさに著しい影響を与えるため この問題について考察し 効率のよい順序づけを行う動的重みづけ法を提案するさらに 不完全指定論理関数(Don't careを含む関数)について考察し D変数を導入した表現法を提案する最後に 本論文で提案した手法の効果を調べるため 実用的な論理回路を共有二分決定グラフで表現する実験を行い 本論文の手法が有効であることを示す

収録刊行物

  • 情報処理学会論文誌

    情報処理学会論文誌 32(1), 77-85, 1991-01-15

    情報処理学会

被引用文献:  24件中 1-24件 を表示

各種コード

  • NII論文ID(NAID)
    110002723171
  • NII書誌ID(NCID)
    AN00116647
  • 本文言語コード
    JPN
  • 資料種別
    Journal Article
  • ISSN
    1882-7764
  • データ提供元
    CJP引用  NII-ELS  IR  IPSJ 
ページトップへ