電子情報通信学会Acta Medica Okayama18810225J100-D62017パイプライン化依存性グラフを簡単化するための効率的な等価性判定アルゴリズム616626ENHirotoKagotaniGraduate School of Natural Science and TechnologyYujiSugiyamaGraduate School of Natural Science and TechnologyTakujiOkamoto 依存性グラフに基づいた非同期式パイプライン制御回路の設計方法が提案されている.この設計法の最終段階においては,依存性グラフと縮小した依存性グラフの等価性を何度も繰返し判定することにより,簡単化した依存性グラフが得られる.しかし,この判定には多数の状態をもつオートマトンを扱うため,その計算量は極めて大きい.本論文では,この等価性判定のための新たな効率的なアルゴリズムを提案する.まず,基本操作の実行順序の半順序をコンパクトに表現するために,基本操作直結因果関係グラフ O˙ を定義する.次に,分
岐系列ごとに O˙ の高々二つの部分グラフが一致するとき,かつそのときに限り,二つの依存性グラフが等価であることを証明する.更に,等価性の判定に必要な分岐系列のサイズと数が有限であることを証明する.最後に,上述の原理を用いたアルゴリズムの計算量が従来法に比べて大幅に小さいことを示す.No potential conflict of interest relevant to this article was reported.Acta Medica Okayama1994Minimum test sets for locally exhaustive testing of combinational circuits with five outputs280285ENTokumiYokohiraToshimiShimizuHiroyukiMichinishiYujiSugiyamaTakujiOkamoto<p>In this paper, features of dependence matrices of combinational circuits with five outputs are discussed, and it is shown that a minimum test set for locally exhaustive testing of such circuits always has 2 w test patterns, where w is the maximum number of inputs on which any output depends</p>
No potential conflict of interest relevant to this article was reported.