多值函式之對稱性編碼

在高階(High-level)的電路設計中，將變數表示成多值形式(multi-valued form)會比二元形式(binary form)來得直接且容易讓人了解。而二元編碼(binary encoding)是將這樣的設計實體化成二元電路的重要過程。對於一個多值函式或多值網路而言，其二元編碼並不唯一，所以我們可以針對不同最佳化的準則進行二元編碼。二元編碼會顯著影響實體化後的電路，所以需要特別考慮。大部分以往發展的編碼，是以減少編碼後所形成的布林表示式(Boolean expression)裡的cube與literal為手段，希望減小電路合成後的面積。然而，除了編碼之外，cube與literal的數量也會受到布林轉換(Boolean transformation)的影響，因此我們很難預測在電路實體化之後，減少的效果還會存留多少。在本篇碩士論文中，我們探討了不同以往的編碼策略，希望最大化對稱(symmetry)的程度。對稱性是一種凾式性質，所以在任何的布林轉換下都不會改變。如此一來，針對對稱性所發展出的編碼方式，其效果可以在任何等價的布林轉換中保存。對稱性還有許多獨特的優點，包括有利於timing engineering change order、二元決策圖(binary decision diagram)的變數排序(variable ordering)，並對函式分解(functional decomposition)有潛在的助益。我們提出了一個基於子集合限制求解的演算法，處理多值函式的二元編碼，並最大化編碼後的布林表示式的對稱程度。另外，我們也將此演算法推廣到多值網路和不完全函式(incompletely specified function)的編碼上。實驗結果顯示，我們的演算法與以往的方法相比，確實達到了較高的對稱程度，同時電路面積維持在一定的程度。

關鍵字

對稱性；編碼；子集合限制問題；不完全函式；多值函式；多值網路

並列摘要

In high-level designs, variables are often naturally represented in a symbolic multi-valued form. Binary encoding is an essential step in realizing these designs in Boolean circuits. Since binary encoding of a multi-valued function and network may not be unique, there exists room for exploiting various ways of encoding with respect to different optimization criteria. It is well known that a multi-value encoding may have drastic effects on its final circuit implementation and should be carefully selected. Nevertheless most prior encoding efforts focused on minimizing area in term of the numbers of literals and cubes in the resultant encoded Boolean expressions. Unfortunately the numbers of literals and cubes can be affected not only by encoding, but also by further circuit transformation. It is thus hard to predict the net effect of encoding on final circuit realization. In this thesis we explore a different encoding strategy of encoding for maximizing the degree of symmetry, rather than minimizing area. Since symmetry is a functional property, it is an invariant under circuit transformation. The effect of encoding with the new optimization objective can be well preserved throughout any function-equivalent circuit transformation. It was observed that symmetric functions have various unique benefits, and can be useful in timing engineering change order (ECO); they have good variable ordering for BDD representation; they may achieve better functional decomposition, and so on. We propose an algorithm based on subset-sum constraint solving for encoding a multi-valued function for symmetry. We further extend our method to encode multi-valued networks as well as incompletely specified multi-valued functions. Experiments show that our method achieves higher degrees in final circuit realization with comparable circuit sizes.

並列關鍵字

symmetry ； encoding ； subset-sum constraint ； incompletely specified function ； multi-valued function and network

參考文獻

[2] P. Ashar, S. Devadas, and R. Newton. Sequential Logic Synthesis, Kluwer Academic Publishers, 1992.

[7] R. Murgai, R. K. Brayton, and A. Sangiovanni-Vincentelli. Optimum Functional Decomposition Using Encoding. In Proceedings of Design Automation

Conference, pages 408-414, 1994.

[9] Y.-J. Jiang and R. K. Brayton. Don't Cares and Multi-Valued Logic Network Minimization. In Proceedings of International Conference on Computer-Aided

Design, pages 520-525, 2000.

國際替代計量

多值函式之對稱性編碼

全文下載

主題瀏覽