卡诺图基础知识：从格雷码到逻辑函数化简

卡诺图基础知识：从格雷码到逻辑函数化简

卡诺图是数字逻辑电路设计中用于化简逻辑函数的重要工具。它通过二维图形直观地表示多维逻辑函数，使得逻辑函数的化简过程更加直观和高效。本文将详细介绍卡诺图的基础知识，包括格雷码的构造方法、二进制数与格雷码的转换，以及卡诺图在逻辑函数化简中的应用。

格雷码

格雷码是一个二进制数系，其中两个相邻数的二进制位只有一位不同。以下是三位以内的格雷码示例：

手动构造

$k$ 位的格雷码可以通过以下方法构造。我们从全 $0$ 格雷码开始，按照下面策略：

1. 翻转最低位得到下一个格雷码，（例如 $000\to 001$）；
2. 把最右边的 $1$ 的左边的位翻转得到下一个格雷码，（例如 $001\to 011$）；
3. 交替按照上述策略生成 $2^{k-1}$ 次，可得到 $k$ 位的格雷码序列。

镜像构造

$k$ 位的格雷码可以从 $k-1$ 位的格雷码以上下镜射后加上新位的方式快速得到，如下：

二进制数转格雷码

（假设以二进制为 0 的值做为格雷码的 0）

$G$：格雷码；$B$：二进制码；$n$：正在计算的位

根据格雷码的定义可得：$G(n) = B(n+1) \oplus B(n)$，即 $G(n) = B(n+1) + B(n)$。自低位至高位运算即可，无需考虑进位。

计算方法

观察一下 $n$ 的二进制和 $G(n)$。可以发现，如果 $G(n)$ 的二进制第 $i$ 位为 $1$，仅当 $n$ 的二进制第 $i$ 位为 $1$，第 $i+1$ 位为 $0$ 或者第 $i$ 位为 $0$，第 $i+1$ 位为 $1$。于是我们可以当成一个异或的运算，即 $G(n)=n\oplus \left\lfloor\frac{n}{2}\right\rfloor$

int g(int n) { return n ^ (n >> 1); }

通过格雷码构造原数（逆变换）

接下来考虑格雷码的逆变换，即给定一个格雷码 $g$，要求找到原数 $n$。我们考虑从二进制最高位遍历到最低位（最低位下标为 $1$，即个位；最高位下标为 $k$）。则 $n$ 的二进制第 $i$ 位与 $g$ 的二进制第 $i$ 位 $g_i$ 的关系如下：

$$
\begin{array}{rll}
n_k &= g_k \
n_{k-1} &= g_{k-1} \oplus n_k &= g_k \oplus g_{k-1} \
n_{k-2} &= g_{k-2} \oplus n_{k-1} &= g_k \oplus g_{k-1} \oplus g_{k-2} \
n_{k-3} &= g_{k-3} \oplus n_{k-2} &= g_k \oplus g_{k-1} \oplus g_{k-2} \oplus g_{k-3} \
&\vdots\
n_{k-i} &=\displaystyle\bigoplus_{j=0}^ig_{k-j}
\end{array}
$$

int n = 0;
for (int i = 0; i < k; i++) {
    n ^= (g >> i) & 1;
}
return n;

卡诺图

卡诺图是用 2D 形式表示的多维函数。卡诺图一共有 $2^n$ 个小格，每个小格子都存储一个最小项，小格之间按照格雷码排列，即保证了最小项之间逻辑相邻以及几何相邻。

其中，几何相邻包括三种：内相邻（紧挨着）、外相邻（一行或一列的两头）、中心对称（一直不是很懂中心对称指什么，CS220 说只有内外相邻两种）。

下图可以直观体现出卡诺图的几何相邻：

卡诺图画相邻圈时，应使每个圈包含 $2^n$ 个格子，且圈圈要尽量大。

下表是可选的卡诺图每个小格的排列样式。

五变量卡诺图较为麻烦，可使用重叠画法。

一些新概念

注意：卡诺图当中的乘积项，一定是大小为 2 的幂的一个圈。

• 涵项（implicant），是一个乘积项，可以被写进 SOP 形式当中的那种乘积项（可以被圈圈的格子）。注意不一定是最小 SOP。只要这个值对应 1，就是 Implicant。
• 布尔函数 $F$ 的质涵项（prime implicant），是最少化文字数量的涵项——就是说，如果从一个乘积项 $P$ 去除任何「文字 literal」都导致 $P$ 成为布尔函数 $F$ 的非涵项，那么这个乘积项就是质涵项。例如 $AB'C'$ 和 $AB'C$ 现在是某逻辑函数的两个涵项，那么 $AC$ 就是函数的一个质涵项，其中的 $A$ 和 $C$ 不可再去掉。而最小化文字数量，意味着尽量圈的圆圈大一点。
• 基本质涵项（essential prime implicant），是一种特殊的质涵项，是蕴涵于不满足任何其他质涵项的最小项的那些质涵项。换句话说，若存在只被一个质涵项覆盖的极小项，则覆盖该极小项的质涵项为基本质涵项。如果以卡诺图的形式来描述逻辑函数，可以发现只有一种方式可以圈选这个输入组合。

结合课件 24 页左右的例子可能比较容易理解。

卡诺图中找 PI 和 EPI 的规律总结（个人心得）

感觉，找 PI，就是执行下面几个步骤：

1. 对于每一个没被圈的最小项格子，看能不能圈大小是 16 的？能，所有方案都圈出来，break。
2. 对于每一个没被圈的最小项格子，看能不能圈大小是 8 的？能，所有方案都圈出来，break。
3. 对于每一个没被圈的最小项格子，看能不能圈大小是 4 的？能，所有方案都圈出来，break。
4. 对于每一个没被圈的最小项格子，看能不能圈大小是 2 的？能，所有方案都圈出来，break。
5. 对于每一个没被圈的最小项格子，看只能圈大小是 1 的了。

对于 EPI，就是找到所有 PI 之后，依次检查每一个最小项，如果这个最小项只被一个圆圈圈起来了，那么这个圈就是 EPI。

不关心项（无关项） Don't care term

DCT 在卡诺图当中，指无论取 0 还是取 1，对结果没有影响，无所谓。在实际应用中，可能是因为，这个位置的变量取值组合，永远不会出现。