查看“︁逻辑优化”︁的源代码

'''逻辑优化'''是指在一个或多个限制條件下，找到指定[[逻辑电路]]等效表示的过程，是[[数字电路]]与[[集成电路设计]]中[[逻辑综合]]的一部分。
电路一般来说會受到最小芯片面积和预定响应延迟的限制。对给定电路进行逻辑优化的目标是获得最小的[[逻辑电路]]，且其值与原始电路相同。<ref name="Maxfield_2008"/>通常具有相同功能的较小电路成本更低、<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018"/>占用空间更小、[[效能功耗比|功耗更低]]、延迟更短，且能最大限度地降低[[串扰]]、[[冒险 (数字电路)|延迟信号处理的冒险/险象]]，以及[[集成电路]]上金属结构纳米级别的其他问题。

在[[邏輯代数]]領域中，將复杂的[[布尔表达式]]优化是寻找能最終產出相同結果，但更简单的表达式。

==动机==
复杂[[电子电路]]（即包含[[逻辑门]]等众多元件的电路）的问题在于，每个元件都会占用物理空间，耗费生产时间和成本。“电路最小化”是逻辑优化的一种形式，用于减少集成电路中复杂逻辑的面积。

随着[[逻辑综合]]的出现，[[电子设计自动化]]（EDA）行业面临的挑战之一就是如何为给定设计找到最简单的电路表示。<ref group="nb" name="NB_Netlist"/>两级逻辑优化早已以[[奎因-麦克拉斯基算法]]的形式存在，后来又出现了[[启发式逻辑压缩器]]，但芯片密度的迅速提高及用于电路描述的[[硬件描述语言]]的普及，使逻辑优化成为今日的形式，有图形界面的Logic Friday、Minilog、ESPRESSO-IISOJS（多值逻辑）等等。<ref>{{Cite journal |last=Theobald |first=M. |last2=Nowick |first2=S. M. |date=November 1998 |title=Fast heuristic and exact algorithms for two-level hazard-free logic minimization |url=https://academiccommons.columbia.edu/doi/10.7916/D8N58V58/download |journal=IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |volume=17 |issue=11 |pages=1130–1147 |doi=10.1109/43.736186 |access-date=2024-04-02 |archive-date=2024-04-02 |archive-url=https://web.archive.org/web/20240402152421/https://academiccommons.columbia.edu/doi/10.7916/D8N58V58/download |dead-url=no }}</ref>
== 方法 ==
逻辑电路简化方法同样适用于布尔表达式最小化。

=== 分类 ===
如今，逻辑优化分为多个类别：

;基于电路表示
: 两级逻辑优化
: 多级逻辑优化

基于电路特性
:时序逻辑优化
:组合逻辑优化

;基于执行类型
:图形优化方法
:表格优化方法
:代数优化方法

=== 图形法 ===
图形法通过表示逻辑变量与函数值的图表表示所需逻辑函数。操作/检查图表可以省去很多繁琐的计算。两级逻辑图形最小化方法包括
* [[莱昂哈德·欧拉]]（1707–1783）的[[欧拉图]]（1768）
* [[约翰·维恩]]（1834–1923）的[[文氏图]]（1880）
* [[莫里斯·卡诺]]的[[卡诺图]]（1953）

=== 布尔表达式最小化 ===
下面列出的布尔表达式最小化（简化）方法也适用于电路优化。

对于布尔函数由电路确定的情形（即，对于找到尽可能小等效电路的问题），无界电路最小化问题在[[时间复杂度]]上长期被猜想为是[[多项式谱系|<math>\Sigma_2^P</math>复杂]]的，并在2008年得到证明<ref name="Buchfuhrer_2011"/>，不过也有一些有效的启发式方法，如[[卡诺图]]与[[奎因-麦克拉斯基算法]]，可以促进这过程。

布尔函数最小化方法包括

* [[奎因-麦克拉斯基算法]]
* [[佩特里克法]]

=== 最优多级法 ===
在文献中，找到布尔函数最优电路表示的方法通常称作“精确合成”（exact synthesis）。由于计算的复杂性，精确合成只适用于小型布尔函数。近来的方法将优化问题映射为[[布尔可满足性问题]]，<ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism |url=https://si2.epfl.ch/~demichel/publications/archive/2020/winston-exact.pdf |website=EPFL |access-date=2022-11-07 |archive-date=2023-11-27 |archive-url=https://web.archive.org/web/20231127164957/https://si2.epfl.ch/~demichel/publications/archive/2020/winston-exact.pdf |dead-url=no }}</ref><ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis for Multi-Level Logic Networks |url=https://si2.epfl.ch/~demichel/graduates/theses/winston.pdf |website=EPFL |access-date=2022-11-07 |archive-date=2023-11-27 |archive-url=https://web.archive.org/web/20231127164955/https://si2.epfl.ch/~demichel/graduates/theses/winston.pdf |dead-url=no }}</ref>这样就可以用[[SAT求解器]]找到最佳电路表示。

=== 启发式方法 ===
[[启发式]]方法用既定规则解决更大的问题集中实际有用的子集。启发式方法可能产生不了理论上的最优解，但若有用，则能以最小代价实现大部分优化目标。计算机系统中用启发式方法进行逻辑优化的例子是[[启发式逻辑压缩器]]。

===两级表示法与多级表示法===
电路的两级表示，严格来说是指以[[规范形式 (布尔代数)|积之和]]（SOP）为单位的扁平化电路表示法，更适用于[[可编程逻辑阵列|PLA]]设计的实现。多级表示则是以任意形式连接的SOP、POS（和之积）、因子形式等为单位的更通用的电路表示法。逻辑优化算法通常针对电路结构（SOP、因子形式）或功能标识（[[二元决策图]]、[[代数决策图]]）。SOP形式中，与门是最小单元，通过或门相连；POS形式中则相反，需要用括号将或项归并到与门下，因为或的优先级低于与。SOP和POS形式都能很好地转化为电路逻辑。

若有两函数<math>F_1,\ F_2</math>：
: <math>F_1 = AB + AC + AD,\,</math>

: <math>F_2 = A'B + A'C + A'E.\,</math>

则上述两级表示需要6个积项与24个CMOS Rep晶体管。
多级功能等价表示可以是
: <math>P=B+C</math>

: <math>F_1=AP+AD</math>

: <math>F_2=A'P+A'E</math>

虽然级数是3，但由于共用了<math>B+C</math>项，积项与字面量总数减少了。
同样，我们将电路分为[[组合逻辑电路]]和[[时序逻辑电路]]。组合逻辑电路仅根据当前输入产生输出，可用布尔[[关系 (数学)|关系]]表示，如[[优先编码器]]、[[译码器]]、[[数据选择器]]、[[多路分解器]]等。

时序逻辑电路根据当前与过去的输入产生输出，依靠时钟信号区分两种输入。它们可用有限状态机表示，如[[触发器]]与[[计数器]]。

==例子==
[[File:Circuit-minimization.svg|thumb|300px|原电路与简化电路示例]]
有很多最小化电路的方法，这是通过最小化（简化）布尔函数达到目标的例子。电路执行的布尔函数与实线该函数的代数表达式直接相关。<ref name="Mano_2014"/>
考虑用于表示<math>(A \wedge \bar{B}) \vee (\bar{A} \wedge B)</math>的电路。很明显，此语句中使用了两个非、两个连接和一个析取，这意味着对应的电路需要两个[[反相器]]、两个[[与门]]与一个[[或门]]。

运用[[布尔代数]]定律或直觉可简化（最小化）电路。由于示例指出，''B''为假时''A''为真，反之亦然，因此这仅仅意味着<math>A \neq B</math>。用逻辑门表示的话，[[不等]]简单地对应[[异或门]]，因此<math>(A \wedge \bar{B}) \vee (\bar{A} \wedge B) \iff A \neq B</math>。则下面显示的两个电路等价，可用[[真值表]]检验：
{| class=wikitable style=" float: left;"
|-
! A       !! B       !! !! (A !! ∧ !! {{overline|B}}) !! ∨     !! ({{overline|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
|}
{{clear}}

== 另见 ==
* [[二元决策图]] (BDD)
* [[任意项]]
* [[蕴涵项]]
* [[电路复杂性]]
* [[复合函数]]
* [[函数分解]]
* [[电路利用不足]]
* [[逻辑冗余]]

== 注释 ==
{{reflist|group="nb"|refs=
<ref group="nb" name="NB_Netlist">[[网表]]大小可用于度量简单性。</ref>
}}

== 参考文献 ==
{{reflist|refs=
<ref name="Maxfield_2008">{{cite book |title=FPGAs |chapter=Chapter 5: "Traditional" Design Flows |author-last=Maxfield |author-first=Clive "Max" |date=2008-01-01 |editor-last=Maxfield |editor-first=Clive "Max" |series=Instant Access |publication-place=Burlington |publisher=[[Newnes (publisher)|Newnes]] / [[Elsevier Inc.]] |isbn=978-0-7506-8974-8 |doi=10.1016/B978-0-7506-8974-8.00005-3 |pages=75–106 |chapter-url=https://www.sciencedirect.com/science/article/pii/B9780750689748000053 |access-date=2021-10-04 |archive-date=2023-02-21 |archive-url=https://web.archive.org/web/20230221190026/https://www.sciencedirect.com/science/article/pii/B9780750689748000053 |dead-url=no }}</ref>
<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018">{{cite web |title=Digital Electronics |author-last1=Balasanyan |author-first1=Seyran |author-last2=Aghagulyan |author-first2=Mane |author-last3=Wuttke |author-first3=Heinz-Dietrich |author-last4=Henke |author-first4=Karsten |date=2018-05-16 |id=DesIRE |series=Bachelor Embedded Systems - Year Group |publisher=Tempus |pages= |url=https://ec.europa.eu/programmes/erasmus-plus/project-result-content/120e4810-0d29-4397-9ad4-b4091c2e3d19/Digital%20Electronics.pdf |access-date=2021-10-04 |url-status=live |archive-url=https://web.archive.org/web/20211004200546/https://ec.europa.eu/programmes/erasmus-plus/project-result-content/120e4810-0d29-4397-9ad4-b4091c2e3d19/Digital%20Electronics.pdf |archive-date=2021-10-04}} (101 pages)</ref>
<ref name="Buchfuhrer_2011">{{cite journal |doi=10.1016/j.jcss.2010.06.011 |title=The complexity of Boolean formula minimization |journal=[[Journal of Computer and System Sciences]] (JCSS) |volume=77 |issue=1 |pages=142–153 |date=January 2011 |location=Computer Science Department, [[California Institute of Technology]], Pasadena, California, USA |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |author-link2=Christopher Umans |publisher=[[Elsevier Inc.]] |url=http://users.cms.caltech.edu/~umans/papers/BU07.pdf |access-date=2024-04-02 |archive-date=2018-01-14 |archive-url=https://web.archive.org/web/20180114141842/http://users.cms.caltech.edu/~umans/papers/BU07.pdf |dead-url=no }} This is an extended version of the conference paper: {{cite book |doi=10.1007/978-3-540-70575-8_3 |chapter=The Complexity of Boolean Formula Minimization |title=Proceedings of Automata, Languages and Programming |work=35th International Colloquium (ICALP) |volume=5125 |pages=24–35 |publisher=[[Springer-Verlag]] |publication-place=Berlin / Heidelberg, Germany |series=[[Lecture Notes in Computer Science]] (LNCS) |date=2008 |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |author-link2=Christopher Umans |isbn=978-3-540-70574-1 |url=http://users.cms.caltech.edu/~umans/papers/BU07.pdf |access-date=2018-01-14 |url-status=live |archive-url=https://web.archive.org/web/20180114141842/http://users.cms.caltech.edu/~umans/papers/BU07.pdf |archive-date=2018-01-14 }}</ref>
<ref name="Mano_2014">{{cite book |author-first1=M. Morris |author-last1=Mano |author-first2=Charles R. |author-last2=Kime |title=Logic and Computer Design Fundamentals |edition=4th new international |publisher=[[Pearson Education Limited]] |date=2014 |page=54 |isbn=978-1-292-02468-4}}</ref>

}}

== 阅读更多 ==
* {{cite book |author-last1=Lind |author-first1=Larry Frederick |author-last2=Nelson |author-first2=John Christopher Cunliffe |title=Analysis and Design of Sequential Digital Systems |date=1977 |publisher=[[Macmillan Press]] |isbn=0-33319266-4 |url=https://archive.org/details/AnalysisDesignOfSequentialDigitalSystems/}} (146 pages)
* {{cite book |title=Synthesis and Optimization of Digital Circuits |author-first=Giovanni |author-last=De Micheli |author-link=Giovanni De Micheli |date=1994 |publisher=[[McGraw-Hill]] |isbn=0-07-016333-2}} (NB. Chapters 7–9 cover combinatorial two-level, combinatorial multi-level, and respectively sequential circuit optimization.)
* {{cite book |author-first1=Gary D. |author-last1=Hachtel |author-first2=Fabio |author-last2=Somenzi |title=Logic Synthesis and Verification Algorithms |date=2006 |orig-year=1996 |publisher=[[Springer Science & Business Media]] |isbn=978-0-387-31005-3}}
* {{cite book |author-first1=Zvi |author-last1=Kohavi |author-first2=Niraj K. |author-last2=Jha |title=Switching and Finite Automata Theory |edition=3rd |publisher=[[Cambridge University Press]] |date=2009 |isbn=978-0-521-85748-2 |chapter=4–6}}
* {{cite book |author-first=Rob A. |author-last=Rutenbar |title=Multi-level minimization, Part I: Models & Methods |type=lecture slides |publisher=[[Carnegie Mellon University]] (CMU) |id=Lecture 7 |url=https://www.ece.cmu.edu/~ee760/760docs/lec07.pdf |access-date=2018-01-15 |url-status=live |archive-url=https://web.archive.org/web/20180115125725/https://www.ece.cmu.edu/~ee760/760docs/lec07.pdf |archive-date=2018-01-15 |postscript=;}} {{cite book |author-first=Rob A. |author-last=Rutenbar |title=Multi-level minimization, Part II: Cube/Cokernel Extract |type=lecture slides |publisher=[[Carnegie Mellon University]] (CMU) |id=Lecture 8 |url=https://www.ece.cmu.edu/~ee760/760docs/lec08.pdf |access-date=2018-01-15 |url-status=live |archive-url=https://web.archive.org/web/20180115125733/https://www.ece.cmu.edu/~ee760/760docs/lec08.pdf |archive-date=2018-01-15}}

{{数字系统}}

[[Category:电子工程]]
[[Category:电子设计]]
[[Category:数字电子]]
[[Category:电子设计自动化]]
[[Category:布尔代数]]
[[Category:计算机逻辑]]