Intel Quartus Prime数字系统设计权威指南：从数字逻辑、Verilog HDL 到复杂数字系统的实现最新章节_何宾著

1.7　逻辑表达式的化简

一个数字逻辑电路由很多逻辑门构成，这些逻辑门由输入信号驱动，然后由这些逻辑门产生输出信号。通过真值表或者逻辑表达式描述逻辑电路的行为。这些方式定义了逻辑电路的行为，即如何对逻辑输入进行组合，然后驱动输出。但是，它们并没有说明如何构建一个电路以满足这些逻辑行为的要求。

对于任何特定的逻辑关系来说，只存在一个真值表，但是可以找到很多的逻辑等式和逻辑电路来描述与实现相同的关系。为什么会存在很多的逻辑等式？这是由于这些逻辑等式可能存在多余的、不必要的逻辑门，这些逻辑门的存在和消除，并不会改变逻辑输出。如图1.78所示，图中只有一个真值表，但是存在不同的电路描述，分成POS和SOP两种方式，这些表达式有些是最简的，有些不是最简的，即存在冗余的逻辑门。

逻辑表达式化简的目的是使得实现要求的逻辑功能所消耗的逻辑门个数最少，也就是最少化所消耗晶体管的数量。通过最简的逻辑表达式和合理的逻辑电路结构，使得实现所要求的逻辑功能的物理成本降到最低。通过下面的两种方式，对逻辑表达式化简。

（1）通过逻辑代数的基本公式及规则对逻辑函数进行变换，从而得到最简的逻辑表达式。这里所谓的最简形式，是指最简的“与或”逻辑表达式或者最简的“或与”逻辑表达式，它们的判别标准有两条，即项数最少、在项数最少的条件下项内包含的变量最少。

（2）卡诺图遵循某个排列规律。由于这些规律，使逻辑代数的许多特性在图形上得以形象而直观地被体现，从而使它成为证明公式和化简函数的有力工具。

1.7.1　使用运算律化简逻辑表达式

布尔代数应该是化简逻辑表达式最古老的方法，它提供一个正式的算术系统，其使用这个算术系统来化简逻辑表达式，尝试找到用于表达逻辑功能最简的逻辑表达式。这是一个有效的算术系统：

（1）它有包含3个元素的集合，即{“0”，“1”，“ A ”}，其中“ A ”是可以假设为“0”或“1”的任意变量。

图1.78　逻辑关系不同的电路描述

（2）两个二进制操作，即“逻辑与”或交集和“逻辑或”或并集。

（3）一个一元运算，即取反或互补。

集合之间的操作通过3种运算实现，很容易就能从这些运算的逻辑真值表中得出基本的逻辑与、逻辑或和逻辑非运算规则。结合律、交换律和分配律可以直接使用真值表证明。下面只列出分配律的真值表，如表1.23所示，深色的列使用了分配律，两边等效。

表1.23　真值表验证分布律

逻辑与运算优先于逻辑或运算。使用括号可以指定逻辑运算的优先级，因此，下面的两个等式是两个等效的逻辑等式：

A · B + C =（ A · B ）+ C

A + B · C = A +（ B · C ）

在定义共轭逻辑门运算时，为了观察其特性，德·摩根定律提供了一个规范的代数描述方法，即同一个逻辑电路可以用逻辑与或逻辑或功能来表示，这取决于输入和输出逻辑电平的表示方式。德·摩根定律适用于任意多个输入的逻辑系统中，表现形式为

德·摩根定律一般也适用于逻辑异或功能，只是使用了不同的形式。当对奇数个有效输入信号（逻辑“1”）进行异或操作时，异或操作的输出也是有效的（输出为逻辑“1”）；当对偶数个有效输入信号（逻辑“1”）进行异或非操作时，异或非操作的输出也是有效的（输出为逻辑“1”）。

对逻辑异或功能的单个逻辑输入取反，或者对它的逻辑输出取反，等效于逻辑异或非功能。同样地，对逻辑异或非功能的单个逻辑输入取反，或者对它的逻辑输出取反，等效于逻辑异或功能。

对一个逻辑输入和逻辑输出同时取反，或者对两个逻辑输入同时取反，逻辑异或功能将变为逻辑异或非功能，反之亦然。

如表1.24所示，使用一个3变量的真值表说明上面给出的变换规则。

表1.24　3变量逻辑异或关系和异或非关系的运算

根据表1.24可知，对于：

F = A ⊕ B ⊕ C

存在下面的关系，即

图1.79～图1.82给出的电路非常直观地说明了布尔代数的运算律规则。

图1.79　逻辑与和逻辑或规则

图1.80　结合律

图1.81　交换律

图1.82　分配律

下面的例子给出使用布尔逻辑代数运算律化简逻辑表达式的过程。

例如，的关系也称为“吸收”规则，经常称为“一致”规则。所谓的吸收规则很容易用其他的规则进行证明，所以没有必要使用这些关系作为规则。特别是当使用规则时，不同的等式形式使验证变得困难。一致规则也很容易证明。

思考与练习1-27：使用布尔代数化简下面的逻辑表达式。

1.7.2　使用卡诺图化简逻辑表达式

在最小化逻辑系统时，真值表并不实用，并且布尔代数的应用也有限制。逻辑图为最小化逻辑系统提供了一个简单实用的方法。逻辑图和真值表都包含了相同的信息，但是逻辑图更容易表示出冗余的输入项。逻辑图是一个二维（或三维）结构，它包含了真值表所包含的确切的、同样的信息。但是，它以阵列结构排列来遍历所有的逻辑域，因此很容易验证逻辑关系。真值表的信息也能很容易地使用逻辑图表示。如图1.83所示，将包含3输入逻辑变量的真值表映射到包含8个单元的逻辑图，逻辑图中每个单元内的数字对应于真值表中每行逻辑输入变量的一个取值组合。

如图1.83所示，逻辑图中的每个单元与真值表中的每一行之间存在一对一的对应关系，并且为每行输入变量进行数字编码。因此，每一个逻辑变量所包含的域由一组4个连续的单元表示（逻辑变量 A 所包含的域是一行四单元，逻辑变量 B 和 C 所包含的域是一个四个单元的方块）。逻辑图内的单元排列并不是只有一种可能，但是它拥有在两个单元内让每一个域重叠其他域的有用属性。如图1.83所示，逻辑变量所包含的域在逻辑图中是连续区域，但是在真值表中并不连续。由于在逻辑图中逻辑变量所包含的域是连续的，因此使得它们非常有用。

图1.83　3输入逻辑变量真值表映射到8单元的逻辑图

例如，在表示逻辑图时，在逻辑图的边缘标出变量名，相邻单元行和列的值“0”或者“1”表示所对应行和列的变量值。

可以从左到右读取逻辑图边缘的变量值，以便寻找相应给定单元所对应真值表中的一行。如图1.84所示，真值表中 A =1的行、 B =0的行、 C =1的行，对应逻辑图的阴影单元。

图1.84　逻辑图的一种典型排列形式

如图1.85所示，将真值表输出列的信息对应到逻辑图的每个单元中，所以真值表和逻辑图包含了相同的信息。在逻辑图中，相邻的（垂直方向和水平方向）“1”称为逻辑“相邻”，这些“相邻”表示可以找到并且消除冗余输入的机会。因此，以这种方式使用的逻辑图称为卡诺图（或者K-映射）。

如图1.86所示，将一个包含4个逻辑输入变量的真值表映射到一个包含16个单元的卡诺图中。

图1.85　真值表信息映射到逻辑图的每一个单元中

图1.86　将包含4个逻辑输入变量的真值表映射到一个包含16个单元的卡诺图

在一个逻辑系统中，使用卡诺图来找到和消除冗余输入项的关键是：确定输出为“1”的相邻项的积之和（SOP）表达式或输出为“0”的相邻项的和之积（POS）表达式。在卡诺图中，一个相邻项的有效组合必须包含2 ⁱ （ i =0，1，2，3，4）个单元，即只允许存在1、2、4、8或16的相邻单元组合，它必须是正方形或长方形，但不能是斜角、弯角或其他不规则的图形。

当使用SOP逻辑表达式时，在化简卡诺图的过程中，每个相邻单元的有效组合只能包含输出为“1”的项；当使用POS表达式时，在化简卡诺图的过程中，每个相邻单元的有效组合只能包含输出为“0”的项。

对于卡诺图，可以使用两种方法进行化简。

（1）只关注卡诺图中输出为“1”的单元。

① 将所有的“1”项组合在尽可能大的组合圈中。

② 列写出所画圈内所确定的每一个乘积项。

③ 用逻辑或关系将这些乘积项（最小项）连接起来，这样就可以从卡诺图中得到SOP逻辑表达式。

（2）只关注卡诺图中输出为“0”的单元。

① 将所有的“0”项组合在尽可能大的组合圈中。

② 列写出所画圈内所确定的每一个求和项（最大项）。

③ 用逻辑与关系将这些求和项（最大项）连接起来，这样就可以从卡诺图中得到POS逻辑表达式。

SOP使用最小项编译（例如，变量的“0”域表示对圈内乘积项的取补），POS使用最大项编译（例如，输入变量的“1”域表示对圈内和项的取补）。如果一个圈内同时包含了一个给定的逻辑变量的“1”域和“0”域，那么这个变量是多余的，其不会出现在圈定的项内。但是，当这个圈内只包含该变量的“1”域或“0”域时，该逻辑变量则出现在圈内所包含的相应的逻辑项里。卡诺图的一边和相对的边是连续的，所以一个圈在中间不组合“1”或“0”的情况下可以从一边跨越到另一边，如图1.86所示说明了这个过程。

卡诺图可用于求解2个、3个、4个、5个或6个输入变量系统的最简逻辑表达式（如果超过6个变量，这个方法就变得复杂）。对于2个、3个或4个输入变量的系统，这个方法比较直观，如图1.87所示，下面的几个例子将对其进行说明。一般情况下，画圈的过程应以“1”（或“0”）开始。画圈时，确保所有的“1”（或“0”）都已经分配到每一个圈内。

将等式中的“1”（对于SOP表达式）和“0”（对于POS表达式）简单地分配到逻辑单元中，这样就可以很容易地将最小项SOP表达式和最大项POS表达式映射到卡诺图中。对于SOP等式，没有列出“1”的任何单元都写成“0”，对于POS等式也可以用这种方式实现。如图1.88所示，对这个过程进行了说明。

对于5变量或6变量的系统，可以用两种不同的方法：一个方法是将4变量的卡诺图嵌套在1变量或2变量的超图中；另一种方法是使用“输入变量图”。如图1.89所示，使用超图求解5变量或6变量最简的逻辑表达式类似于对2、3或4变量卡诺图化简的过程，但是4变量卡诺图必须内嵌于1变量或2变量的超图。在相邻的超图单元中，子图之间的逻辑相邻可以通过在相同编号中识别“1”或“0”寻找。

注

当“1”位于子图的相同编号单元时，超图的变量不出现在乘积项中。

思考与练习1-28：如图1.90所示，化简下面的2变量卡诺图，并用POS和SOP表达式表示。

思考与练习1-29：如图1.91所示，化简下面的3变量卡诺图，并用POS和SOP表达式表示。

思考与练习1-30：如图1.92所示，化简下面的4变量卡诺图，并用POS和SOP表达式表示。

思考与练习1-31：根据下面的等式画出并化简卡诺图，并用POS和SOP表达式表示。

F= ∑ m （0，1，4，5）

G= Π M （0，1，3，4，5，7，13，15）

思考与练习1-32：如图1.93所示，化简下面的多变量卡诺图，并用POS和SOP表达式表示。

图1.87　化简卡诺图得到最简的逻辑表达式

图1.88　逻辑表达式映射到卡诺图

图1.89　在超图中搜索逻辑相邻项

图1.90　2变量卡诺图

图1.91　3变量卡诺图

图1.92　4变量卡诺图

图1.93　多变量卡诺图

1.7.3　不完全指定逻辑功能的化简

当数字电路有 N 个逻辑输入信号，但并不会用到所有2 ^N 个输入组合时，会出现不完全指定逻辑功能这样的情况。或者说，如果所有的2 ^N 组合都可以，但一些组合是不相关的。例如，假设一个远程电视遥控器能够用于控制电视、VCR或DVD。有些遥控器可能带有用于快进操作模式按钮的物理切换电路；其他遥控器可能使用相同的模型，将这个按钮放置在电路的左边，但是它们的功能完全不同。不管怎么样，一些输入信号的组合对于电路的正确操作完全是无关紧要的。因此，这就可以利用这些有利条件进一步简化逻辑电路。

当输入组合不影响逻辑系统的功能时，可以用来驱动电路的输出为逻辑高或逻辑低。这就是说，设计者并不关注这些不可能或无关的输入对电路的影响。在真值表和卡诺图中，这个信息使用特殊的“无关项”符号表示，表明这个信号可以是“1”或“0”，并不影响电路的功能。一些教科书使用“×”来表示无关项，但是这会和名字为“X”的信号（表示信号的不确定状态）产生混淆。因此，可以使用一个更好的、与标准信号名没有关系的符号来表示，此处使用符号“ Ф ”表示无关项。

如图1.94所示，真值表的右侧表示使用相同的3个逻辑输入后产生的两个输出函数 F 和 G 。两个输出各自都包含两个无关项。同样地，用卡诺图表示相关的信息。在表示函数 F 逻辑功能的卡诺图中，对于最小项2和7，设计者不关心是否输出是“1”还是“0”。因此，在卡诺图中编码为2和7的单元可以是“1”或“0”。很明显，把单元7的输出作为“1”，把单元2的输出作为“0”将得到最简的逻辑表达式。在这样的情况下，SOP与POS都能得到相同的表达方式。

图1.94　3个输入变量的两个函数 F 和 G （包含无关项）

在函数 G 的卡诺图中，单元1和3中的无关项可以圈作“1”或“0”。在SOP表达式中，两个无关项都可以圈作“1”，得到逻辑表达式：

然而，在POS表达式中，单元1和3可以圈_作“0”，得到逻辑表达式：

如图1.95所示给出了卡诺图中无关项的应用，由布尔代数可知，这两个函数表达式是不相等的。通常情况下，虽然它们在电路中的功能相同，但是由具有无关项的卡诺图所得到的SOP和POS表达式的逻辑功能并不是等价的。

思考与练习1-33：如图1.96所示，化简下面包含无关项的2变量卡诺图，并用POS和SOP表达式表示。

思考与练习1-34：如图1.97所示，化简下面包含无关项的3变量卡诺图，并用POS和SOP表达式表示。

思考与练习1-35：如图1.98所示，化简下面包含无关项的4变量卡诺图，并用POS和SOP表达式表示。

思考与练习1-36：根据下面包含无关项的等式画出并化简卡诺图，然后用POS和SOP表达式表示。

F= ∑ m （0，1，4，5） +Φ （2，7）

G= Π M （0，1，3，4，5，7，13，15） +Φ （2，3，11，12，14）

1.7.4　输入变量的卡诺图表示

真值表为实现一个给定的组合逻辑电路的具体行为提供了最好的机制，卡诺图为表示和最小化数字逻辑电路的输入-输出关系提供了最好的机制。到目前为止，在真值表左上方和卡诺图周围表示出输入变量。这样，允许将输出信号的每一个状态定义为一个真值表中给定行上“0”和“1”项的输入模式的函数，或定义为给定卡诺图单元的二进制编码。在不丢失任何信息的情况下，通过将真值表左上方的输入变量移动到真值表输出列，或通过将卡诺图单元从外部移动到内部，这样就可以将真值表和卡诺图转换成更简洁的形式。尽管到了后面的模块才变得清晰，但是输入变量的使用，以及真值表和卡诺图化简，使得一个多变量系统看上去更加直观和简洁。

图1.95　卡诺图中无关项的应用

图1.96　包含无关项的二变量卡诺图

图1.97　包含无关项的3变量卡诺图

图1.98　包含无关项的4变量卡诺图

图1.99说明了传输机制，一个16行的真值表被简化成两个8行和4行的真值表。如图1.99（b）所示，在8行的真值表中，输入列不再使用变量 D 。取而代之的是，它出现在了输出列中，表示输出逻辑值的两行和输入变量 D 之间的关系。如图1.99（c）所示，在4行的真值表中，输入列不再使用变量 C 和 D ，它们将出现在输出列中，表示输出逻辑值与输入变量 C 和 D 的关系。

图1.99　真值表和卡诺图的简化

如图1.100所示，给出4单元的卡诺图。从图中可以看出隐含的子图，对于变量 A 和 B 每个确定的逻辑值，它表示了 C 和 D 之间的关系。对于任何输入变量的卡诺图，考虑子图可以用于帮助对输入变量进行正确的编码。

通过读取卡诺图中的索引编码，真值表的行号可以映射到子图中的单元。编码从子图外的映射开始，后面添加子图编码，如图1.100中子图中阴影块的编码为“1110”。

图1.100　包含子图的卡诺图

最小项SOP表达式和最大项POS表达式也可以直接翻译成输入变量的卡诺图。如图1.101所示，卡诺图中每个单元下面较小的数字表示分配给该单元的最小项或者最大项。

图1.101　将SOP和POS表达式直接翻译成输入变量的卡诺图

当把最小项和最大项编码到卡诺图中时，取输入变量的最小数字。例如，如果最大的最小项用14表示，则假设为4个输入变量。

循环输入变量卡诺图遵循相同的原则，即循环“1-0”映射，寻找“1”构成的最优组合输入变量用于SOP电路，寻找“0”构成的最优组合输入变量用于POS电路。规则是相似的，即所有输入变量和所有的“1”（或者“0”）必须被分组到最大可能的2 ⁱ 的长方形或者正方形框中。当所有的输入变量和所有的“1”（或者“0”）被包含在一个最优的框中时，该过程结束。不同之处在于，相似的输入变量本身或者“1”（或者“0”）可以包含在圈中。如图1.102所示，需要特别注意，当圈住包含“1”（或者“0”）的输入变量时，由于“1”（或者“0”）表示输入变量的所有可能组合都出现在映射单元中，因此包含“1”（或者“0”）和输入变量的圈经常只包含输入变量可能组合的子集。

为了进一步理解卡诺图中输入变量画圈的方法，从每个卡诺图单元中所隐含的子图中考虑。通过将“1-0”信息圈入隐含的子图中，产生卡诺图中的变量。在卡诺图变量中，所圈住相邻单元中的信息可以包含出现在子图中相同位置的“1”（或者“0”）。

当读取圈内等式时，对于每个圈的SOP乘积项（或者POS和项），必须包含定义了圈范围的_变量和在圈内所包含的输入变量。例如，图1.102内的第一个乘积项包含圈域和输入变量 D 。

图1.102　输入变量的化简

输入变量图中的单元可能包含单个输入变量或者两个以上变量的逻辑表达式。当所圈的单元包含逻辑表达式时，它可以帮助识别SOP和POS画圈机制。如图1.103所示，与一个卡诺图单元的单个输入变量相比，一个单元内的乘积项表示一个较小的SOP域，这是由于一个乘积项的“逻辑与”变量越多，其所定义的逻辑域就越小。一个单元内的和项表示一个较大的SOP域，这是由于一个和项的“逻辑或”变量越多，其所定义的逻辑域就越大。当从一个输入变量图圈SOP等式时，与包含单个输入变量的单元相比，包含乘积项的单元在它们的子图中出现很少的“1”。类似地，当从一个输入变量图圈POS等式时，与包含单个输入变量的单元相比，包含和项的单元在它们的子图中出现很少的“0”，而包含乘积项的单元在它们的子图中有更多的“0”。