卡诺图与最简SOP式

HDLBits链接

真值表

基础知识介绍

在数字逻辑设计中，真值表是我们最常用的工具之一。它就像是一张”完整的说明书”，告诉我们逻辑电路在所有可能的输入组合下会产生什么输出。

什么是真值表？

简单来说，真值表是一张表格，它列出了逻辑电路的所有可能输入组合以及对应的输出结果。表格中用1表示”真”（逻辑高电平），用0表示”假”（逻辑低电平）。

生活中的类比：

想象一下你家里的电灯开关。假设你有两个开关A和B，它们共同控制一盏灯：

只有A打开，灯不亮
只有B打开，灯不亮
A和B都打开，灯亮了
A和B都关闭，灯不亮

这就是一个简单的与门（AND gate）的真值表！

为什么真值表很重要？

在设计数字电路时，我们通常会先确定电路的功能需求，然后通过真值表把这些需求具体化。有了真值表，我们才能进一步推导出逻辑表达式，最终设计出实际的电路。

从真值表到标准式

有了真值表之后，我们如何把它转换成逻辑表达式呢？这里有两种最常用的标准形式：SOP标准式和POS标准式。

核心概念定义

SOP（Sum of Products，积之和）标准式：

也叫最小项表达式
找出真值表中所有输出为1的表项
对于每个这样的表项：
- 输入为1用原变量表示（如A）
- 输入为0用反变量表示（如~A）
将这些变量相乘（逻辑与），得到一个乘积项
最后把所有乘积项相加（逻辑或）

POS（Product of Sums，和之积）标准式：

也叫最大项表达式
找出真值表中所有输出为0的表项
对于每个这样的表项：
- 输入为1用反变量表示（如~A）
- 输入为0用原变量表示（如A）
将这些变量相加（逻辑或），得到一个求和项
最后把所有求和项相乘（逻辑与）

为什么需要这两种形式？

虽然SOP和POS都能表达相同的逻辑功能，但在某些情况下，其中一种形式会比另一种更简洁。选择哪种形式，取决于哪种形式需要的项更少。

举例说明

假设我们有如下真值表（为了简化，这里使用3个输入变量A、B、C和1个输出D）：

A	B	C	D
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

SOP标准式（积之和）：

首先找出所有输出D=1的行：

A=0, B=1, C=1 → 乘积项：~A·B·C
A=1, B=0, C=0 → 乘积项：A·~B·~C
A=1, B=1, C=0 → 乘积项：A·B·~C
A=1, B=1, C=1 → 乘积项：A·B·C

将这些乘积项相加，得到SOP标准式：

1	D = (~A·B·C) + (A·~B·~C) + (A·B·~C) + (A·B·C)

POS标准式（和之积）：

接着找出所有输出D=0的行：

A=0, B=0, C=0 → 求和项：A+B+C
A=0, B=0, C=1 → 求和项：A+B+~C
A=0, B=1, C=0 → 求和项：A+~B+C
A=1, B=0, C=1 → 求和项：~A+B+~C

将这些求和项相乘，得到POS标准式：

1	D = (A+B+C)·(A+B+~C)·(A+~B+C)·(~A+B+~C)

从标准SOP式到最简SOP式

虽然标准表达式能准确描述逻辑功能，但它们往往不是最简洁的。在实际的电路设计中，我们需要对逻辑表达式进行化简，这样可以：

减少逻辑门的数量
降低电路复杂度
减少功耗和延迟
提高电路可靠性

为什么要化简？

想象一下，如果你要搭一个积木房子，用最少的积木块搭出同样的房子，是不是更高效、更美观？逻辑化简也是同样的道理！

卡诺图（Karnaugh Map）介绍

卡诺图是一种非常直观的逻辑化简工具。它的基本思想是：将逻辑上相邻的最小项在图上也放在相邻的位置，方便我们观察和合并。

卡诺图的几个关键特点：

它是真值表的一种图形化表示
相邻的方格只有一位输入变量不同
可以圈出相邻的1进行合并
圈的大小必须是2的幂次（1、2、4、8…）

系统化简法步骤

下面我们介绍一种系统的逻辑化简方法——奎因-麦克拉斯基算法（Quine-McCluskey algorithm），也叫表格法。这种方法虽然看起来步骤多，但非常系统，不容易出错。

步骤1：求出函数的SOP标准式

首先，我们需要将逻辑函数表示为标准的SOP形式。

例如，对于函数：

1	F = A·B·C + A·B·~C + D + ~A·B·C·D

我们可以将其展开为标准SOP式（列出所有最小项）。

步骤2：求出函数的全部主要项（质蕴含项）

主要项（Prime Implicant）是指不能再与其他项合并的乘积项。

具体操作如下：

将最小项按其内部包含1的个数进行分组
从最低组开始，与相邻高位组逐个比较，合并只有一位不同的项
合并时，用短横线”—“表示可以忽略的变量
每合并一次，就在原表中用”√”标记被使用过的项
重复这个过程，直到无法继续合并为止
所有没有被”√”标记的项就是主要项

步骤3：求出必要项、列出化简结果

必要项（Essential Prime Implicant）是指至少包含一个其他主要项不包含的最小项的主要项。换句话说，这个最小项只能被这个主要项覆盖。

找到必要项后，我们再检查是否还有未被覆盖的最小项，用其他主要项来补充覆盖，直到所有最小项都被覆盖为止。

入门者避坑指南

逻辑化简是初学者容易出错的地方，下面我们总结几个最常见的问题。

错误1：卡诺图中变量顺序错误

错误表现：
在画卡诺图时，使用了自然二进制顺序（00, 01, 10, 11）而不是格雷码顺序（00, 01, 11, 10）。

错误原因分析：
卡诺图的核心思想就是相邻的方格只有一位不同。如果使用自然二进制顺序，01和10这两个位置在物理上是相邻的，但它们有两位不同，这样就无法正确合并了！

正确做法对比：

❌ 错误的顺序（自然二进制）：
    AB\CD | 00  01  10  11
    -----------------------
     00   | ... ... ... ...
     01   | ... ... ... ...
     10   | ... ... ... ...
     11   | ... ... ... ...

✅ 正确的顺序（格雷码）：
    AB\CD | 00  01  11  10
    -----------------------
     00   | ... ... ... ...
     01   | ... ... ... ...
     11   | ... ... ... ...
     10   | ... ... ... ...

调试技巧：

画卡诺图前，先在纸边上写好变量的格雷码顺序
记住：格雷码相邻两个数只有一位不同

错误2：圈组合法不正确

错误表现：

❌ 错误示例1：圈的大小不是2的幂次
   圈了3个1在一起（应该圈2个或4个）

❌ 错误示例2：圈没有尽可能大
   明明可以圈4个，却只圈了2个

❌ 错误示例3：遗漏了"环绕相邻"
   忘记卡诺图的上下边、左右边也是相邻的

错误原因分析：
卡诺图化简有几个严格的规则，违反这些规则就无法得到最简表达式：

圈的大小必须是2的幂次（1, 2, 4, 8, …）
每个圈必须尽可能大
所有的1都必须被圈到
允许重叠圈（一个1可以被多个圈包含）
卡诺图是”环绕”的（像一个甜甜圈）

正确做法对比：

记住这个化简口诀：

能大不小：圈尽可能大
能多不少：可以用多个圈
重叠无妨：一个1可以在多个圈里
边角勿忘：别忘了环绕相邻

错误3：无关项（X）处理不当

错误表现：

1
2
3

❌ 错误示例1：把所有无关项都当成0来处理
❌ 错误示例2：把所有无关项都当成1来处理
❌ 错误示例3：不知道哪些无关项该用，哪些不该用

错误原因分析：
无关项（Don’t Care，用X或d表示）是指在实际电路中永远不会出现的输入组合。对于这些输入，输出是0还是1都无所谓。

处理无关项的原则是：只把那些能帮助我们得到更简表达式的无关项当成1，其他的当成0。

正确做法对比：

✅ 正确示例：

只把能够帮助”扩大圈”的无关项当成1
其他无关项当成0，不圈它们

错误4：Verilog中运算符优先级错误

错误表现：

1 2	// ❌ 错误示例：没有加括号，运算符优先级混乱 assign out = ~a & ~b \| c & d; // 实际运算顺序可能和预期不符

错误原因分析：
在Verilog中，不同的逻辑运算符有不同的优先级：

~（非）优先级最高
&（与）次之
|（或）优先级最低

虽然上面的例子碰巧是对的，但为了代码的可读性和避免出错，建议总是使用括号来明确表达运算顺序！

正确做法对比：

1 2	// ✅ 正确示例：使用括号明确运算顺序 assign out = (~a & ~b) \| (c & d);

错误5：混淆SOP和POS的推导方法

错误表现：

1	❌ 错误：推导SOP时看输出为0的行，或者变量取反搞反了

错误原因分析：
很容易把SOP和POS的推导方法记混。这里给大家一个简单的记忆方法：

SOP（积之和）：看输出为1的行，1用原变量，0用反变量
POS（和之积）：看输出为0的行，1用反变量，0用原变量

可以这样记忆：SOP中的”S”是1（Sum是找输出为1的），POS中的”P”是0（Product是找输出为0的）。

巩固练习

题目1：三变量卡诺图化简

题目描述：实现下面卡诺图所描述的电路。

Solution1：

module top_module(
    input  a,
    input  b,
    input  c,
    output out
);
    // 这个卡诺图中，除了a=0,b=0,c=0的情况输出0，其他都输出1
    // 所以最简单的写法是：只要不是全0，就输出1
    assign out = ~((~a) & (~b) & (~c));
endmodule

小贴士：
有时候，”取反”的思路反而能让表达式更简单！与其圈所有的1，不如看看圈0会不会更简单。

题目2：四变量卡诺图化简

题目描述：实现下面卡诺图所描述的电路。

Solution2：

module top_module(
    input  a,
    input  b,
    input  c,
    input  d,
    output out
);
    // 使用括号明确运算顺序，提高可读性
    assign out = (~a & ~d) | (~b & ~c) | (b & c & d) | (a & c & d);
endmodule

题目3：含无关项的卡诺图化简

题目描述：实现下面卡诺图所描述的电路。

提示：无关项d可以根据化简需求自己制定为0或是1。

Solution3：

module top_module(
    input  a,
    input  b,
    input  c,
    input  d,
    output out
);
    // 巧妙利用无关项，我们可以把某些d当成1来扩大包围圈
    // 最终得到简洁的表达式
    assign out = a | (~a & ~b & c);
endmodule

注意：
无关项是我们化简时的”好朋友”！合理利用它们可以得到更简洁的表达式。

题目4：奇偶校验电路

题目描述：实现下面卡诺图所描述的电路。

Solution4：

module top_module(
    input  a,
    input  b,
    input  c,
    input  d,
    output out
);
    // 这个卡诺图描述的是一个4输入异或电路（奇偶校验）
    // 当输入中有奇数个1时输出1，偶数个1时输出0
    assign out = a ^ b ^ c ^ d;
endmodule

小贴士：
异或链（XOR chain）在通信系统中非常常用，特别是在CRC校验、加解密等场景中。

题目5：最小SOP和POS表达式

题目描述：

实现一个有四输入（a、b、c、d）的单输出数字系统，当2、7或15出现在输入端时，生成逻辑1，当0、1、4、5、6、9、10、13或14出现时，生成逻辑0。数字3、8、11和12的输入不会出现在这个系统中。例如，7对应于a、b、c、d分别被设为0、1、1、1。

确定最小SOP格式的输出 out_sop 和最小POS格式的输出 out_pos。

Solution5：

module top_module (
    input  a,
    input  b,
    input  c,
    input  d,
    output out_sop,
    output out_pos
);

    // 最小SOP表达式（积之和）
    assign out_sop = (c & d) | (~a & ~b & c);

    // 最小POS表达式（和之积），也可以用SOP取反的形式
    assign out_pos = ~((~c | ~d) & (a | b | ~c));

endmodule

提示：
这道题是最大项和最小项的问题。虽然我们更常用最小项（SOP），但最大项（POS）也需要了解。在某些情况下，POS形式可能会更简洁。

题目6：四变量卡诺图

题目描述：实现下面卡诺图所描述的电路。

Solution6：

module top_module (
    input  [4:1] x,  // 注意：输入是x[4]到x[1]，不是从0开始
    output f
);
    // 注意信号的编号！x[1]是最低位，x[4]是最高位
    assign f = (~x[1] & x[3]) | (x[2] & x[4]);
endmodule

题目7：另一个四变量卡诺图

题目描述：实现下面卡诺图所描述的电路。

Solution7：

module top_module (
    input  [4:1] x,
    output f
);
    // 同样注意信号编号，用括号提高可读性
    assign f = (~x[2] & ~x[4]) | (~x[1] & x[3]) | (x[2] & x[3] & x[4]);
endmodule

题目8：多路选择器实现逻辑函数

题目描述：对于下面的卡诺图，用一个4-to-1多路选择器和不限数量的2-to-1多路选择器，但2-to-1多路选择器的使用要尽可能少。你不允许使用任何其他逻辑门，你必须使用a和b作为多路复用器选择端的输入，如下面的4-to-1多路选择器所示。

Solution8：

module top_module (
    input  c,
    input  d,
    output reg [3:0] mux_in  // 使用reg是因为在always块中赋值
);

    // 使用组合逻辑always块来描述多路选择器的输入
    always @(*) begin
        case({c, d})
            2'b00:   mux_in = 4'b0100;
            2'b01:   mux_in = 4'b0001;
            2'b11:   mux_in = 4'b1001;
            default: mux_in = 4'b0101;  // 2'b10的情况
        endcase
    end

endmodule