aiwiki.page
中文
数学 / 离散数学与逻辑 / karnaugh-map

卡诺图

卡诺图按格雷码排列布尔函数值,用于化简逻辑表达式和分析数字电路。

23 个关键词4 个词条链接到这里12 个尚未撰写AI 撰写
布尔代数真值表克劳德·香农函数(数学)矩阵(数学)汉明距离图论拓扑学卡诺图

卡诺图是布尔函数的一种图形表示,通过相邻单元格组成的分组,直观呈现逻辑化简的可能性。每个单元格代表一种二进制输入值的组合,格内记录相应的输出值。单元格的排列方式使相邻位置所代表的输入组合恰好只有一个输入变量不同。因此,将符合条件的相邻单元格归为一组,就能找出可从表达式中消去、且不影响函数既定行为的变量。

这一方法由莫里斯·卡诺于1953年提出,后来成为设计小型数字逻辑电路的标准技术。它将代数表达式或普通真值表中难以辨认的关系转化为空间图案。其主要用途包括化简两级逻辑、利用未完全指定的输入条件,以及识别某些时序冒险。卡诺图尤其适用于含有二至四个变量的函数;虽然也可以绘制变量更多的卡诺图,但图的规模以及日益复杂的邻接关系限制了其手工使用。

历史发展及其在开关理论中的地位

卡诺图源于符号逻辑在电气开关电路中的应用。在这种情境下,变量可以表示开关处于断开还是闭合状态、继电器是否通电,或电信号的逻辑值为 0 还是 1。串联和并联连接可以分别实现与、或运算,而互补触点或反相器件则可实现非运算。因此,化简逻辑表达式可以减少电路所需的元件数量或连接数量。

克劳德·香农于 1938 年发表的论文《继电器与开关电路的符号分析》是一项重要的基础性成果,系统地建立了开关网络与布尔代数之间的联系。一旦用符号表达了电路的行为,就可以利用代数恒等式寻找等效的实现方案。难点不在于证明化简是可行的,而在于使化简过程系统化,并将其控制在易于处理的范围内。一个涉及多个变量的表达式可能有许多不同的变换方式,而局部有效的化简并不一定能找到整体上最经济的电路。

爱德华·W. 维奇于 1952 年提出了一种图形化简方法。在贝尔电话实验室工作的莫里斯·卡诺于 1953 年发表了《组合逻辑电路综合的图解法》。卡诺采用的排列方式,使输入值组合之间的相邻关系特别便于通过目视进行分组。维奇图、卡诺图和维奇—卡诺图这些名称反映了两者紧密相连的发展历程,不过,早期图示与后来教科书采用的惯例并不总是使用相同的布局。

图解法与逻辑最小化的列表方法同期发展。威拉德·V. 奎因在 20 世纪 50 年代初的工作,以及爱德华·J. 麦克拉斯基在 1956 年的工作,促成了奎因—麦克拉斯基算法的形成。该算法将相同的底层合并与覆盖操作表达为适合系统计算的形式。卡诺图侧重于目视识别;列表方法则明确枚举可以合并的项以及候选覆盖方案。两者都基于这样一个事实:如果两个项除某一变量分别以原变量和反变量的形式出现外完全相同,那么合并这两个项时就可以消去该变量。

卡诺图将设计规格、真值表、化简后的表达式和逻辑门网络这几个不同的描述层次联系起来,因此在组合电路设计的教学与实践中占据了重要地位。但它在历史上的重要性,并不意味着现代大型电路通常仍靠绘制卡诺图来进行最小化。对于规模较大的设计,自动化综合已在很大程度上取代了手工绘图。不过,这种方法对于处理小规模控制函数、检查推导出的表达式、理解冗余,以及解释为何某些布尔变换能够保持逻辑行为却改变时序行为,仍然很有用。

布尔函数、单元格与坐标约定

具有 nn 个输入的布尔函数是一个函数

f:{0,1}n⟶{0,1}.f:\{0,1\}^{n}\longrightarrow\{0,1\}.

其真值表包含 2n2^n 种输入组合。卡诺图包含完全相同的信息,但通过重新排列这些组合,使它们之间的关系显现出来。二变量卡诺图有四个单元格,三变量卡诺图有八个,四变量卡诺图则有十六个。与普通的数值矩阵不同,卡诺图的排列方式依据的是逻辑上的相邻关系,而不是行列之间的算术运算。

对于四变量函数 F(A,B,C,D)F(A,B,C,D),一种常见约定是用 ABAB 标记行,用 CDCD 标记列。每个坐标轴均按 00,01,11,1000,01,11,10 的顺序标记,而不是按通常的二进制计数顺序排列。这是一个格雷码序列:相邻的两个标记仅有一位不同;将序列视为循环时,末尾与开头的标记也满足这一条件。反转某个坐标轴的顺序或交换变量,同样可以得到有效的卡诺图,前提是对所有单元格标记及相邻关系的解释始终保持一致。

每一种完全确定的输入组合都对应一个最小项,即包含所有变量且每个变量恰好出现一次的合取项,其中各变量可以取原变量或其补变量。以 AA 为最高有效位时,输入 ABCD=1010ABCD=1010 的十进制编号为 10,其最小项为

m10=AB′CD′.m_{10}=AB'CD'.

这里,撇号表示逻辑取反,并置表示与,++ 表示或。一个最小项仅在一种输入组合下取值为 1。因此,可以通过列出值为 1 的单元格编号来指定一个函数:

F=Σm(0,1,2,3,8,9,10,11,14,15).F=\Sigma m(0,1,2,3,8,9,10,11,14,15).

这一记法只是对函数的紧凑描述,并不代表已经得到化简后的实现形式。对应的卡诺图如下:

AB\CDAB\backslash CD 00 01 11 10
00 1 1 1 1
01 0 0 0 0
11 0 0 1 1
10 1 1 1 1

文字是指一个变量或其补变量。乘积项是若干文字的与,积之和表达式则是若干乘积项的或。由最小项构成的标准与或式中,每一项都包含 nn 个文字。卡诺图化简将若干最小项合并为覆盖范围更广、所含文字更少的乘积项。与之对偶的术语适用于最大项:最大项是一种或项,仅在某一种指定的输入组合下取值为 0。

在整个计算过程中,输入变量的顺序必须保持不变。单元格的编号取决于所声明的变量顺序,而其在图中的位置则取决于选用的卡诺图布局。混淆这些约定,可能会得到一个看似合理、实际却对应其他函数的表达式。因此,明确的坐标轴标记是卡诺图数学定义的一部分,而不只是辅助绘图的标识。

格雷码邻接与布尔几何

卡诺图中的核心关系是逻辑邻接:两个输入组合恰好只有一个坐标不同时,它们就是相邻的。用汉明距离来表述,相邻组合之间的距离为 1。因此,00110011 和 10111011 相邻,因为只有 AA 发生变化;而 00110011 和 01010101 不相邻,因为有两个坐标发生变化。卡诺图的布局使许多这样的邻接关系表现为单元格共用一条边。

普通的二进制排列会掩盖这种关系。例如,连续的二进制标号 0101 和 1010 在两个位上都不相同。格雷码排列将这一步转换替换为先从 0101 到 1111,再从 1111 到 1010,从而使每一步都只改变一位。它还使图形边界两侧的 1010 和 0000 相邻。因此,标准四变量卡诺图的左右边界彼此相邻,上下边界也彼此相邻。

这种首尾相接的约定带来了几个结果。四个角上的单元格构成一个有效的四格分组:第一行与最后一行相邻,第一列与最后一列也相邻。一个分组也可以由同一行或同一列两端的两个单元格组成。不过,对角接触的单元格并不会仅仅因为顶点相接就成为相邻单元格。在标准二维卡诺图中,沿对角线移动通常会同时改变一个行变量和一个列变量。

图论提供了一种更一般的描述。2n2^n 个输入组合构成 nn 维超立方体图的顶点,边则连接仅有一位不同的组合。一个乘积项若固定 kk 个变量,而让其余 n−kn-k 个变量自由取值,就确定了一个包含 2n−k2^{n-k} 个顶点的子立方体。卡诺图中的分组就是这些子立方体的图形表示。这既解释了分组所允许的大小,也解释了分组的代数意义。

对于四个变量,将相对的边界视为相接,就使常见的网格具有环面式的邻接结构,这与拓扑学有关。这种描述讨论的是哪些单元格互为邻居,并不是说函数本身具有实体的甜甜圈形状。变量更多时,单个矩形图就较难完整呈现全部邻接结构。五变量卡诺图通常画成两个相互对应的四变量子图,六变量卡诺图则画成按格雷码顺序排列的四个子图。

子立方体解释比“画矩形”这条规则更具普遍性。有效的分组必须包含其自由变量的所有取值组合,同时保持其他变量不变。在变量数不超过四个的标准卡诺图中,允许的分组表现为单元格数量是二的幂的矩形,也包括跨越边界、首尾相接的矩形。在更大的卡诺图中,视觉上呈矩形的区域未必就是有效的布尔子立方体;所提出的分组是否合法,取决于实际的位标号。

分组规则与代数消元

化简为积之和形式时,应对值为 1 的单元格进行分组。每组必须包含 1,2,4,8,…1,2,4,8,\ldots 个单元格,并且必须对应一个布尔子立方体。分组不能包含明确指定为 0 的单元格。每个必须覆盖的 1 都必须由至少一个选定的分组覆盖,但分组之间可以重叠。因此,一个值为 1 的单元格可以同时参与最终表达式中的多个项。

其代数依据是互补恒等式 X+X′=1X+X'=1 以及分配律。两个仅在 DD 上不同的相邻最小项可合并为

AB′CD′+AB′CD=AB′C(D′+D)=AB′C.AB'CD'+AB'CD =AB'C(D'+D) =AB'C.

在合并后的区域内,DD 的取值无关紧要。四格分组可消去两个变量,八格分组可消去三个变量,包含 2r2^r 个单元格的分组可消去 rr 个变量。因此,对于一个有 nn 个变量的函数,相应的乘积项包含 n−rn-r 个文字。

从分组写出对应项时,只保留在整个分组中取值不变的变量。恒为 1 的变量以原变量形式出现,恒为 0 的变量以反变量形式出现,取值发生变化的变量则省略。例如,一个四格区域中,若 A=1A=1、C=0C=0,而 BB 和 DD 遍历所有可能的取值组合,则该区域表示 AC′AC'。与这些固定的坐标值相比,该区域在页面上的位置或朝向并不重要。

较大的分组会得到文字数较少的项,但这并不意味着应当不加区分地选取所有大分组。某个大分组可能只覆盖了其他必要项已经覆盖的单元格,徒增硬件,却无助于满足函数的完整要求。反过来,重叠分组有时必不可少。任务是选出一组分组,使其并集以可接受的代价覆盖所有必须覆盖的 1,而不是将卡诺图划分成互不重叠的区域。

如果一个分组再扩大就必然包含不允许纳入的单元格,那么它对应一个质蕴涵项。更一般地,蕴涵项是一个乘积项,其取值为 1 的集合包含于该函数取值为 1 的集合。任何非质蕴涵项都可以扩大为质蕴涵项,从而在不丢失已覆盖的 1 的情况下减少文字。因此,对于通常以项数和文字数为优化目标的两级逻辑最小化,只需考虑质蕴涵项。

几个边界情况有助于说明这些规则。孤立的 1 会产生一个包含全部变量的最小项。如果所有单元格均为 1,整张图就构成一个分组,函数为常量 1,可解释为空乘积。如果没有任何单元格为 1,函数就是常量 0,不需要任何乘积项。包含三个或六个单元格的分组不能直接得到单个乘积项,即使这些单元格看起来构成了便于分组的形状。

最小覆盖与四变量实例详解

分组可以找出候选项,而选择哪些项则是一个独立的数学优化问题。本质素蕴含项至少覆盖一个其他任何素蕴含项都无法覆盖的必需的 1。任何仅由素蕴含项构成的覆盖都必须包含这样的项。选定本质素蕴含项后,有些函数仍有尚未覆盖的单元格,而这些单元格可以用不同方式覆盖。剩余项的选择决定了所提出的表达式是否真正达到最小。

考虑前文介绍的四变量卡诺图:

F=Σm(0,1,2,3,8,9,10,11,14,15).F=\Sigma m(0,1,2,3,8,9,10,11,14,15).

最上行和最下行通过边界相接,共同组成一个包含八个单元格的分组。它们的行标分别为 AB=00AB=00 和 AB=10AB=10,因此组内始终有 B=0B=0,而 A,C,DA,C,D 可以变化。这个分组对应的项为 B′B'。第二个分组包含单元格 10,11,14,1510,11,14,15,位于 AB=10,11AB=10,11 两行与 CD=10,11CD=10,11 两列的交叉处。在这个分组中,A=1A=1 和 C=1C=1 保持不变,因此得到 ACAC。

所得表达式为

F=B′+AC.F=B'+AC.

两个分组在单元格 10 和 11 处重叠,这是完全允许的。第一个分组是本质素蕴含项,因为例如单元格 0 不属于其他任何素蕴含项。第二个分组也是本质素蕴含项,因为单元格 14 不属于其他任何素蕴含项。该表达式包含两个乘积项、共三个文字,而规范表达式则包含十个最小项,每个最小项都有四个文字。直接用真值表核对即可确认:B′B' 涵盖了所有满足 B=0B=0 的输入,而 ACAC 则补足了其余应使函数值为 1 的输入。

并非每个函数的覆盖都这样别无选择。以三变量函数为例:

G=Σm(0,1,2,5,6,7),G=\Sigma m(0,1,2,5,6,7),

六个值为 1 的单元格构成一个环,每个单元格都可以分别与两个相邻单元格配对。图中既没有包含四个单元格的蕴含项,也没有本质素蕴含项。两个不同的最小表达式为

G=A′B′+BC′+ACG=A'B'+BC'+AC

和

G=A′C′+B′C+AB.G=A'C'+B'C+AB.

每个表达式都包含三个项,每项含两个文字。这说明了为什么“选取最大的分组”并不能唯一确定答案:六个候选分组的大小都相同,仍然需要从中选出适当的子集。

剩余的选择问题可以用素蕴含项表表示。表中的列表示必须覆盖的最小项,行表示素蕴含项,标记则表示覆盖关系。选择若干行以覆盖每一列,是集合覆盖问题的一种形式。彼得里克法将各种备选方案表示为布尔和项之积,再通过展开或化简找出覆盖方案。

“最小”的含义也必须明确。教科书中常见的约定是先使乘积项的数量最少,再使文字总数最少。其他优化目标可能会为门输入、反相信号或特定的库单元赋予不同的成本。卡诺图能揭示有效的逻辑化简方式,但在等价表达式中优先选择哪一个,取决于所采用的成本函数。

和之积形式与不完全指定函数

卡诺图也可以通过对 0 而不是 1 进行分组来化简。所得结果是和之积表达式,即若干或项的与。这是积之和最小化的对偶形式。一个零分组对应一个区域,在该区域内,相应的和项必须等于 0。在该和项中,固定为 0 的变量以原变量形式出现,固定为 1 的变量则以反变量形式出现——这与 1 分组的规则正好相反。

在上述四变量示例中,值为零的单元格为 4,5,6,7,12,134,5,6,7,12,13。整行 AB=01AB=01 构成一个包含四个单元格的零分组,得到和项 A+B′A+B'。第二个四格分组占据 AB=01,11AB=01,11 两行与 CD=00,01CD=00,01 两列的交叉区域。在整个区域内,B=1B=1 且 C=0C=0,因此得到 B′+CB'+C。所以,

F=(A+B′)(B′+C).F=(A+B')(B'+C).

利用恒等式 (X+Y)(X+Z)=X+YZ(X+Y)(X+Z)=X+YZ,可以验证该式等价于 B′+ACB'+AC。这两种形式虽然都很简洁,但其实现成本可能不同。

这种对偶关系也可以通过德摩根定律来理解。对 FF 的零值进行分组,等价于对 F′F' 的一值进行分组。将 F′F' 的积之和表达式取反,就得到 FF 的和之积表达式。这提供了一种代数方法,用来核对每个文字是以原变量还是反变量形式出现;当电路拟采用或非而非与非结构实现时,这种方法尤其有用。

许多实际设计规范并未规定某些输入组合下的输出。这些单元格用 XX、短横线或其他事先声明的符号标记,称为无关条件。它们可能对应于外部编码所排除的输入组合、未使用的状态,或在某个已声明条件下无关紧要的输出。形式上,输入空间被划分为一集、零集和无关项集。有效的实现必须在一集上输出 1,在零集上输出 0,但在无关项集上可以选择任一值。

例如,设

H(A,B,C)=Σm(1,3,7),d=Σm(5).H(A,B,C)=\Sigma m(1,3,7), \qquad d=\Sigma m(5).

1,3,5,71,3,5,7 这四个单元格均满足 C=1C=1。将单元格 5 视为 1,就可以组成一个四格分组,得到 H=CH=C。如果不允许将其作为无关项处理,单元格 1 和 3 给出 A′CA'C,单元格 3 和 7 给出 BCBC,最终得到 A′C+BCA'C+BC。无关项单元格不必全部使用,而且在独立推导出的不同实现方案中,为它们选定的值也不必保持一致。

未指定的值并不自动意味着在物理上不可能出现的值。未使用的状态可能在启动期间或发生故障后变得可达,而协议所排除的输入组合也可能短暂出现。因此,利用无关项进行化简,会使电路在规定范围之外呈现出逻辑上允许、但未受其他约束的行为。这一区分应由设计规范作出:卡诺图无法判定某项关于输入或状态不会出现的假设,对于电路所处的系统是否成立。

时序冒险与冗余覆盖

布尔等价描述的是稳态下的输入输出行为,并不意味着信号转换期间的行为也完全相同,因为实际逻辑门的传播延迟既不为零,也不相等。即使电路的逻辑表达式在输入变化前后都正确,电路仍可能短暂输出错误的结果。逻辑冒险是指电路在结构上存在产生这种非预期瞬态的可能性;实际出现的瞬态脉冲通常称为毛刺。

在单输入变化模型下,卡诺图能以格外直观的方式检验静态冒险。当输出本应保持为 1,却可能短暂降为 0 时,就存在静态 1 冒险。在两级与—或实现中,如果两个相邻的 1 单元格分别由不同的乘积项覆盖,而实际实现的乘积项中没有任何一项同时覆盖这两个单元格,就会存在这种风险。输入变化可能导致原先有效的项先关断,而新的项尚未导通。

一个典型例子是

F=XY+X′Z.F=XY+X'Z.

当 Y=Z=1Y=Z=1 时,改变 XX 应当使 F=1F=1 保持不变。然而,一个乘积项取决于 XX,另一个则取决于它的反相值。由于反相器路径与其他门路径的延迟可能不同,两个乘积项可能在短时间内同时为 0。在卡诺图上,X=0,Y=1,Z=1X=0,Y=1,Z=1 与 X=1,Y=1,Z=1X=1,Y=1,Z=1 这两个状态彼此相邻,但上述由两个乘积项构成的覆盖中,并没有一个共同的分组跨越它们的公共边。

加入 YZYZ 项即可覆盖这一转换:

Fhf=XY+X′Z+YZ.F_{\mathrm{hf}}=XY+X'Z+YZ.

当 XX 变化且 Y=Z=1Y=Z=1 时,新增项始终保持为 1。它不会改变布尔函数,因为根据共识定理,有

XY+X′Z+YZ=XY+X′Z.XY+X'Z+YZ=XY+X'Z.

因此,在所假定的逻辑门模型下,一个对稳态逻辑而言冗余的项,却可能是实现无冒险电路所必需的。逻辑最小化与冒险消除可能提出相互冲突的要求。

对于两级积之和网络,在通常的延迟假设下,只要让每一对必须输出为 1 的相邻单元格都由至少一个共同的乘积项覆盖,就能消除单输入转换引起的静态 1 冒险。两级和之积网络中的静态 0 冒险则适用对偶规则:相邻的零状态应当同属一个零分组,且该分组对应一个实际实现的和项。最简表达式可能已经满足这些条件,也可能需要额外加入冗余项。

这种保证有其局限性。多个输入同时变化时,可能经过一些中间状态,而这些状态的输出可能与预期的端点行为不同。多级网络还可能出现动态冒险,即预期输出最终只转换一次,实际却变化了多次。基于卡诺图的静态覆盖本身并不能解决这些问题,也不能对模拟效应、脉冲滤除、时钟域跨越及负载影响进行建模。在异步电路中,电路行为可能直接取决于信号转换,而非时钟控制的采样时刻,因此这些区别尤为重要。

电路实现、计算局限与现代应用

积之和表达式自然对应于两级与—或电路:每个乘积项由一个与门实现,再由一个或门将各项合并。类似地,和之积表达式对应于多个或门的输出接入一个与门的电路。除非已有互补信号可用,否则取反可能需要额外的电路。通过德摩根变换,积之和形式也可自然地映射为与非—与非实现,而和之积形式则可映射为或非—或非实现。

对于 F=B′+ACF=B'+AC,一种直接实现方式是对 BB 使用反相器,对 A,CA,C 进行与运算,再将两者的结果进行或运算。但这一逻辑描述并不等于完整的物理设计。不同门库在可用扇入数、驱动能力、延迟、面积和功耗特性方面各不相同。复合门实现与—或函数的效率可能高于多个独立逻辑门,而经因式分解的表达式则可能减少重复逻辑。因此,最小的两级表达式未必能得到面积最小或速度最快的电路。

在可编程技术中,这一区别更加明显。可编程逻辑阵列允许多个输出共享乘积项,因此,分别对每个输出进行最小化,可能会错过成本更低的联合实现方案。现场可编程门阵列中的查找表可以实现其输入容量范围内的任意函数;对于已经能容纳在一张查找表中的函数,减少其文字数并不一定能减少所需的查找表数量。卡诺图化简在逻辑上仍然有效,但其物理实现上的收益取决于目标架构。

规模扩展的主要问题在于指数增长。一个 nn 变量卡诺图有 2n2^n 个单元格:四变量时为16个,六变量时为64个,八变量时为256个,十变量时则为1,024个。规模更大的图需要考虑不同面板之间的关系,而这些关系比普通的相邻边更难追踪。候选蕴含项和备选覆盖方案的数量也可能急剧增长。卡诺图并未消除精确最小化的组合复杂性;它只是让人能够通过模式识别来处理规模较小的实例。

自动化方法针对这一问题的不同环节展开处理。奎因—麦克拉斯基法系统地生成质蕴含项,再求解覆盖问题,但其所需的中间表示可能十分庞大。20世纪80年代开发的 Espresso逻辑最小化器对蕴含项覆盖进行启发式操作,以获得紧凑的两级实现,但通常不保证得到全局最小解。现代逻辑综合还会使用多级因式分解、分解、工艺映射、时序分析及其他表示方法,而不是仅依赖两级最小化。

具有明显异或结构的函数体现了另一项局限。nn 变量奇偶函数在取值为1的输入个数为奇数时输出1。改变任意一个输入都会使输出翻转,因此,在卡诺图的相邻关系下,每个值为1的单元格都不与其他值为1的单元格相邻。所以,其普通的积之和形式需要 2n−12^{n-1} 个完整的最小项,但只需将 n−1n-1 个二输入异或门串联起来,就能以紧凑的电路实现该函数。卡诺图正确地表明无法按普通乘积项进行分组,但合适的实现方式需要采用另一种运算结构。