論理関数表現のモデルとシンボリックアルゴリズム

逻辑函数表达式模型和符号算法

基本信息

批准号：
16092207
负责人：
武永康彦
金额：
$ 7.17万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2007
项目状态：
已结题

项目摘要

1.二分決定グラフによるデータ表現については、第一に、二分決定グラフの構造を論理関数で表現する二分決定グラフの非明示的表現を用いて、効率的な表現が可能な論理関数について研究を行ない、多変量閾値関数を入力変数のビット長に依存しないサイズで表現できることを示した。第二に、A07班山下との共同研究により、量子論理関数を効率よく表現するためのOBDDの変種データ構造を比較検討し、山下が以前に提案したDecisionDiagrams for Matrix Functions(DDMFs)の有効性を理論的に考察した。このデータ構造が、量子論理回路に特有の制約条件をうまく利用しており、単純なOBDDよりも一層データを圧縮し、処理効率を高めていることを明らかにした。2.OBDDに基づくシンボリックアルゴリズムについては、前年度に引き続き、トポロジカルソートの列挙、OBDDによる画像処理アルゴリズムについて研究を行なった。前者では先行頂点数等を求めることにより従来法より計算過程でのOBDDサイズを大幅に抑えられることを示した。後者ではOBDD予測符号化を用いることによりOBDDサイズが圧縮可能であり、提案済みの画像処理アルゴリズムをほぼそのまま利用できることを示した。また、OBDDを用いたナンバーリンクの解法、問題の正当性の判定手法の提案・実装を行なった。

1。关于使用二进制决策图的数据表示，首先，我们对逻辑函数进行了研究，可以使用二进制决策图的隐式表示可以有效地表达，该二进制决策图表达具有逻辑函数的二进制决策图的结构，并证明可以独立于输入变量的位长度表示多元阈值函数。其次，我们与A07组Yamashita合作，我们比较并检查了OBDD的变化数据结构，以有效地表示量子逻辑函数，理论上检查了Yamashita先前提出的MATRIX功能（DDMF）的决策图的有效性。据透露，这种数据结构可以很好地利用量子逻辑电路所独有的约束，比简单的OBDD更快地压缩数据，并提高了处理效率。 2。关于基于OBDD的符号算法，与上一年一样，我们使用OBDD进行了拓扑排序枚举和图像处理算法的研究。在前者中，已经表明，通过计算先前的顶点的数量，与常规方法相比，计算过程中的OBDD大小可以大大减少。在后者中，可以通过使用OBDD预测性编码来压缩OBDD大小，并且显示出所提出的图像处理算法几乎可以按原样使用。此外，我们提出并实施了一种使用OBDD解决数字链接的方法，并提出了一种判断问题有效性的方法。