karnaugh-maps
卡诺图：可视化的布尔化简
TL;DR: 卡诺图(K-map)把真值表排成一张格雷码编码的二维网格,相邻单元只差一个变量。把网格上相邻的 1 圈成 2 的幂次大小的矩形组,直接得到最小积之和(SOP)表达式——根本不需要做代数推演。卡诺图对最多 4 个变量的函数能可靠地最小化;对 5–6 变量,可使用 Quine–McCluskey 算法;再多就要靠 ESPRESSO 之类的算法化综合工具。 基于布尔定律的代数化简 当然有效,但它依赖于在合适的时机看出合适的因式分解。一旦错过一次机会,就可能得到次优结果。当表达式涉及四个或更多变量时,可能的变形数量会爆炸式增长。 卡诺图(K-map)通过把代数化简变成可视化的图形识别来解决这个问题。它由贝尔实验室物理学家 Maurice Karnaugh 于 1953 年提出,把真值表排成一张二维网格,相邻单元恰好只差一个变量。在网格上把相邻的 1 圈成组,就直接得到最小积之和表达式——不需要任何代数操作。 可视化的真值表：什么是 K-map？ 本质上,卡诺图就是真值表的另一种伪装。真值表把输入与输出按线性、垂直方式列出;K-map 把它们重新排成一张二维网格。这并不只是为了好看。K-map 的精妙之处在于它对单元格的特定排列方式。 在标准真值表中,行按二进制递增(00、01、10、11)。在...