SBDDを用いた最小単符号単発状態割当

• 権 容珍

  京都大学工学部情報工学科

• 矢島 脩三

  京都大学工学部情報工学科

書誌事項

タイトル別名

• Minimum Unicode One-Shot State Assignment Using SBDD

抄録

非同期式順序回路に対する状態割当の一つである単符号単発状態割当において、命題論理を用いて最小解を得る新手法を提案する。この状態割当問題は、NP-completeであることが知られているHypercube-embedding問題と同値で、今までのHypercube-embedding問題を解くアルゴリズムはbacktracking手法によるものが大部分を占めている。ここでは、新たに導入されたプール変数による命題論理式を作成してみることのみで、その可能性の判定ができ、データの内部表現として共用二分決定図を用いてることにより、大きな論理式を扱うことができる。実験結果で提案された手法の有効性を示す。
We propose a new method of the unicode one-shot state assignments for asynchronous sequential circuits,in which the propositional calculus,or Boolean algebra is adopted.Exact minimum solutions of the unicode assignment are obtained by our method.The problem of the unicode one-shot state assignment coincides with the hypercube embedding problem,which is known to be NP-complete. The known algorithms for the hypercube embedding problem almost consist of the mechanism of backtracking.Using newly introduced Boolean variables here,we can check the possibility of the unicode one-shot state assignment or the hypercube embedding for a given flow table or graph by even making propositional formula.In order to handle huge propositional formulas,the shared binary decision diagrams(SBDD′s)are used as an internal representation of the form ulas which denote the unicode assignment for a given flow table. Experimental results show that methods are effective to obtain minimum solutions at significantly reduced computation cost.

収録刊行物

• 電子情報通信学会技術研究報告. COMP, コンピュテーション

  電子情報通信学会技術研究報告. COMP, コンピュテーション 93 (81), 61-67, 1993-05-27

  一般社団法人電子情報通信学会

キーワード

• 単符号単発状態割当
• 最小
• 命題論理
• Hypercube embedding
• SB DD's

詳細情報

• CRID: 1573105977190852736
• NII論文ID: 110003191587
• NII書誌ID: AN10013152
• 本文言語コード: en
• データソース種別:
  • CiNii Articles