逻辑优化
逻辑优化是指在一个或多个限制條件下，找到指定逻辑电路等效表示的过程，是数字电路与集成电路设计中逻辑综合的一部分。 电路一般来说會受到最小芯片面积和预定响应延迟的限制。对给定电路进行逻辑优化的目标是获得最小的逻辑电路，且其值与原始电路相同。[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）.