多階邏輯最佳化的研究與設計

Abstract

多階邏輯最佳化是一個相當困難的問題，因為它缺乏有效的表達方式，又沒有良好 的結構性。大多數的多階邏輯表達沒有標準唯一的特性，所以一般人很難找到一個 最佳的結果。在這篇論文中，我們使用一種合適的表達法，並且在這種表達法上面 設計一個良好的演算法。 二元決策圖提供一個表達布林函數的有效方法，它不但具備標準唯一性，而且裡面 不含多餘的部分。然而，在以前的應用中，它只被使用於表達邏輯函數，所以我們 將擴充它在多階邏輯最佳化上的使用，發展一個方法，直接在二元決策圖上操作， 而不是在傳統的布林表達網路上。除此之外，我們還提出一個在BDD 上決定變數順 序的方法，它不需要一個化簡後的布林網路做輸入。最後，實驗的結果顯示，我們 的結果不但快速，而且得到不錯的結果。