ブールの充足可能性を実現する構成可能ハードウェアシステム及びそのための方法

発明者： , , ,
出願人/特許権者： ,
代理人 (1件)：後藤洋介 (外2名)
公報種別：公開公報
出願番号（国際出願番号）：特願平10-135138
公開番号（公開出願番号）：特開平10-326292
出願日： 1998年05月18日
公開日（公表日）： 1998年12月08日
要約：

【要約】【課題】実例特定SAT問題を迅速に解くために構成されたFPGAシステムを提供し、このFPGAシステムを使用してSAT問題を解くための方法を提供する。【解決手段】実例特定(式単位)形式で、SAT解決用回路を実現するための構成可能ハードウェアシステム及び方法を開示した。式単位で、それらの回路を生成するテンプレート設計が行われる。ハードウェア・シミュレーションは、多くの難解なSAT問題のためのものを示しており、本発明によるシステムは、先行技術のソフトウェア実現よりも101倍から103倍のスピードアップを提供できる。

請求項（抜粋）：

ブール式の変数に対して満足する変数割当を生成するための方法であって、前記ブール式の正規結合形式表示を抽出し、構成可能論理回路において、前記正規結合形式を利用した前記ブール式の変数間の関係を導き出す前記正規結合形式に対応する含意回路を生成し、前記変数に値を順次割当し、その割当した値に基づいてバックトラック操作を実行し、矛盾が起こるかどうかを決定する前記構成可能論理回路内の状態マシンを生成して、全ての変数に矛盾を起こさない値を割り当てたとき、前記ブール式の変数に対して満足する変数割当として前記値を定義する段階を含む満足する変数割当を引き出すための方法。

前のページに戻る