邏輯優化
邏輯優化是指在一個或多個限制條件下，找到指定邏輯電路等效表示的過程，是數字電路與集成電路設計中邏輯綜合的一部分。 電路一般來說會受到最小芯片面積和預定響應延遲的限制。對給定電路進行邏輯優化的目標是獲得最小的邏輯電路，且其值與原始電路相同。[1]通常具有相同功能的較小電路成本更低、[2]占用空間更小、功耗更低、延遲更短，且能最大限度地降低串擾、延遲信號處理的冒險/險象，以及集成電路上金屬結構納米級別的其他問題。
在邏輯代數領域中，將複雜的布爾表達式優化是尋找能最終產出相同結果，但更簡單的表達式。
動機
[編輯]複雜電子電路（即包含邏輯門等眾多元件的電路）的問題在於，每個元件都會占用物理空間，耗費生產時間和成本。「電路最小化」是邏輯優化的一種形式，用於減少集成電路中複雜邏輯的面積。
隨着邏輯綜合的出現，電子設計自動化（EDA）行業面臨的挑戰之一就是如何為給定設計找到最簡單的電路表示。[nb 1]兩級邏輯優化早已以奎因-麥克拉斯基算法的形式存在，後來又出現了啟發式邏輯壓縮器，但芯片密度的迅速提高及用於電路描述的硬件描述語言的普及，使邏輯優化成為今日的形式，有圖形界面的Logic Friday、Minilog、ESPRESSO-IISOJS（多值邏輯）等等。[3]
方法
[編輯]邏輯電路簡化方法同樣適用於布爾表達式最小化。
分類
[編輯]如今，邏輯優化分為多個類別：
- 基於電路表示
- 兩級邏輯優化
- 多級邏輯優化
基於電路特性
- 時序邏輯優化
- 組合邏輯優化
- 基於執行類型
- 圖形優化方法
- 表格優化方法
- 代數優化方法
圖形法
[編輯]圖形法通過表示邏輯變量與函數值的圖表表示所需邏輯函數。操作/檢查圖表可以省去很多繁瑣的計算。兩級邏輯圖形最小化方法包括
布爾表達式最小化
[編輯]下面列出的布爾表達式最小化（簡化）方法也適用於電路優化。
對於布爾函數由電路確定的情形（即，對於找到儘可能小等效電路的問題），無界電路最小化問題在時間複雜度上長期被猜想為是複雜的，並在2008年得到證明[4]，不過也有一些有效的啟發式方法，如卡諾圖與奎因-麥克拉斯基算法，可以促進這過程。
布爾函數最小化方法包括
最優多級法
[編輯]在文獻中，找到布爾函數最優電路表示的方法通常稱作「精確合成」（exact synthesis）。由於計算的複雜性，精確合成只適用於小型布爾函數。近來的方法將優化問題映射為布爾可滿足性問題，[5][6]這樣就可以用SAT求解器找到最佳電路表示。
啟發式方法
[編輯]啟發式方法用既定規則解決更大的問題集中實際有用的子集。啟發式方法可能產生不了理論上的最優解，但若有用，則能以最小代價實現大部分優化目標。計算機系統中用啟發式方法進行邏輯優化的例子是啟發式邏輯壓縮器。
兩級表示法與多級表示法
[編輯]電路的兩級表示，嚴格來說是指以積之和（SOP）為單位的扁平化電路表示法，更適用於PLA設計的實現。多級表示則是以任意形式連接的SOP、POS（和之積）、因子形式等為單位的更通用的電路表示法。邏輯優化算法通常針對電路結構（SOP、因子形式）或功能標識（二元決策圖、代數決策圖）。SOP形式中，與門是最小單元，通過或門相連；POS形式中則相反，需要用括號將或項歸併到與門下，因為或的優先級低於與。SOP和POS形式都能很好地轉化為電路邏輯。
若有兩函數：
則上述兩級表示需要6個積項與24個CMOS Rep晶體管。 多級功能等價表示可以是
雖然級數是3，但由於共用了項，積項與字面量總數減少了。 同樣，我們將電路分為組合邏輯電路和時序邏輯電路。組合邏輯電路僅根據當前輸入產生輸出，可用布爾關係表示，如優先編碼器、譯碼器、數據選擇器、多路分解器等。
時序邏輯電路根據當前與過去的輸入產生輸出，依靠時鐘信號區分兩種輸入。它們可用有限狀態機表示，如觸發器與計數器。
例子
[編輯]
有很多最小化電路的方法，這是通過最小化（簡化）布爾函數達到目標的例子。電路執行的布爾函數與實線該函數的代數表達式直接相關。[7] 考慮用於表示的電路。很明顯，此語句中使用了兩個非、兩個連接和一個析取，這意味着對應的電路需要兩個反相器、兩個與門與一個或門。
運用布爾代數定律或直覺可簡化（最小化）電路。由於示例指出，B為假時A為真，反之亦然，因此這僅僅意味着。用邏輯門表示的話，不等簡單地對應異或門，因此。則下面顯示的兩個電路等價，可用真值表檢驗：
| A | B | (A | ∧ | B) | ∨ | (A | ∧ | B) | A | ≠ | B | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F | F | F | F | T | F | T | F | F | F | F | F | ||
| F | T | F | F | F | T | T | T | T | F | T | T | ||
| T | F | T | T | T | T | F | F | F | T | T | F | ||
| T | T | T | F | F | F | F | F | T | T | F | T |
另見
[編輯]注釋
[編輯]參考文獻
[編輯]- ^ Maxfield, Clive "Max". Chapter 5: "Traditional" Design Flows. Maxfield, Clive "Max" (編). FPGAs. Instant Access. Burlington: Newnes / Elsevier Inc. 2008-01-01: 75–106 [2021-10-04]. ISBN 978-0-7506-8974-8. doi:10.1016/B978-0-7506-8974-8.00005-3. （原始內容存檔於2023-02-21）.
- ^ Balasanyan, Seyran; Aghagulyan, Mane; Wuttke, Heinz-Dietrich; Henke, Karsten. Digital Electronics (PDF). Bachelor Embedded Systems - Year Group. Tempus. 2018-05-16 [2021-10-04]. DesIRE. （原始內容存檔 (PDF)於2021-10-04）. (101 pages)
- ^ Theobald, M.; Nowick, S. M. Fast heuristic and exact algorithms for two-level hazard-free logic minimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. November 1998, 17 (11): 1130–1147 [2024-04-02]. doi:10.1109/43.736186. （原始內容存檔於2024-04-02）.
- ^ Buchfuhrer, David; Umans, Christopher. The complexity of Boolean formula minimization (PDF). Journal of Computer and System Sciences (JCSS) (Computer Science Department, California Institute of Technology, Pasadena, California, USA: Elsevier Inc.). January 2011, 77 (1): 142–153 [2024-04-02]. doi:10.1016/j.jcss.2010.06.011. （原始內容存檔 (PDF)於2018-01-14）. This is an extended version of the conference paper: Buchfuhrer, David; Umans, Christopher. The Complexity of Boolean Formula Minimization. Proceedings of Automata, Languages and Programming (PDF). 35th International Colloquium (ICALP). Lecture Notes in Computer Science (LNCS) 5125 (Berlin / Heidelberg, Germany: Springer-Verlag). 2008: 24–35 [2018-01-14]. ISBN 978-3-540-70574-1. doi:10.1007/978-3-540-70575-8_3. （原始內容存檔 (PDF)於2018-01-14）.
- ^ Haaswijk, Winston. SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism (PDF). EPFL. [2022-11-07]. （原始內容存檔 (PDF)於2023-11-27）.
- ^ Haaswijk, Winston. SAT-Based Exact Synthesis for Multi-Level Logic Networks (PDF). EPFL. [2022-11-07]. （原始內容存檔 (PDF)於2023-11-27）.
- ^ Mano, M. Morris; Kime, Charles R. Logic and Computer Design Fundamentals 4th new international. Pearson Education Limited. 2014: 54. ISBN 978-1-292-02468-4.
閱讀更多
[編輯]- Lind, Larry Frederick; Nelson, John Christopher Cunliffe. Analysis and Design of Sequential Digital Systems. Macmillan Press. 1977. ISBN 0-33319266-4. (146 pages)
- De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill. 1994. ISBN 0-07-016333-2. (NB. Chapters 7–9 cover combinatorial two-level, combinatorial multi-level, and respectively sequential circuit optimization.)
- Hachtel, Gary D.; Somenzi, Fabio. Logic Synthesis and Verification Algorithms. Springer Science & Business Media. 2006 [1996]. ISBN 978-0-387-31005-3.
- Kohavi, Zvi; Jha, Niraj K. 4–6. Switching and Finite Automata Theory 3rd. Cambridge University Press. 2009. ISBN 978-0-521-85748-2.
- Rutenbar, Rob A. Multi-level minimization, Part I: Models & Methods (PDF) (lecture slides). Carnegie Mellon University (CMU). [2018-01-15]. Lecture 7. （原始內容存檔 (PDF)於2018-01-15）; Rutenbar, Rob A. Multi-level minimization, Part II: Cube/Cokernel Extract (PDF) (lecture slides). Carnegie Mellon University (CMU). [2018-01-15]. Lecture 8. （原始內容存檔 (PDF)於2018-01-15）.