★ 设计流程

一般而言，针对特定的问题，设计组合逻辑电路的最基本的流程如下图所示：

在得到逻辑表达式后，我们便可以使用数据流层次进行 Verilog 代码的编写工作。接下来，我们将从一个实际问题入手，带大家体验组合逻辑电路的设计过程。

Tips：传统方法

实际上，上面的流程图介绍的方法一般适用于简单的单模块组合逻辑电路设计。随着 Verilog 编程能力的提升，我们往往会使用行为级描述直接实现模块的功能。但这需要我们对于 Verilog 语言对应的电路结构了如指掌。

例子：素数检测

某同学声称自己发现了素数的分布公式：第 \(n\) 个素数为 \(p(n),n\in N^+\)，其中 \(p(n)\) 是一个很复杂的式子，但是计算复杂度是 \(O(1)\) 的，由于篇幅所限这里不单独列出。

该同学委托我们对 \(p(n)\) 给出的结果进行正确性判断。简单起见，我们假定待测结果是 4bits 位宽的，以二进制编码格式输入，现在需要设计一个硬件模块，对于给定的输入 in，输出 out 表示其是否为素数。特别地，该同学要求你将 1 也视为素数。

模块的示例结构如下：

Prime.v
module Prime (
    input [3:0]                 in,
    output                      out
);
// ......
endmodule

以上内容为剧情需要，如有雷同纯属巧合。

渲染错误

有时由于网络问题，部分 LaTeX 公式可能无法正常渲染。我们在每个公式下面附上了其 LaTeX 源码，大家可以在这个网站输入源码自行渲染。

1.1 真值表

针对上面已经形式化表述好的问题，我们首先尝试列出其对应的真值表。真值表记录了每个输入组合对应的输出结果，适用于输入情况有限的问题，其特点是直观、全面。上面这个例子的真值表如下：

输入 in 为待测数据的 4 bits 二进制原码，输出 out 为 1 时代表输入数据为素数或 1。

这张表包含了所有的输出结果，而我们更感兴趣 out 为 1 的表项，因此我们可以将其单独提出，得到一个简化版的真值表：

1.2 逻辑表达式

根据真值表，我们就可以得到该电路的逻辑表达式了，只需要将为 1 的项使用逻辑运算符表示出来即可。为了便于区分，我们记

A = in[3]
B = in[2]
C = in[1]
D = in[0]

上面的真值表就可以改写为：

这样，我们就可以根据每一行，列出下面的逻辑表达式

\[ out=\bar{A}\bar{B}\bar{C}D+\bar{A}\bar{B}C\bar{D}+\bar{A}\bar{B}CD+\bar{A}B\bar{C}D+\bar{A}BCD+A\bar{B}CD+AB\bar{C}D \]

out=\bar{A}\bar{B}\bar{C}D+\bar{A}\bar{B}C\bar{D}+\bar{A}\bar{B}CD+\bar{A}B\bar{C}D+\bar{A}BCD+A\bar{B}CD+AB\bar{C}D

这个式子一共有七项，每一项对应着真值表中为 1 的一行。不难验证，任何 \(ABCD\) 的组合输入均可以得到 out 的正确结果。

1.3 卡诺图

通过真值表得到的逻辑表达式是正确的，但不一定是最简的。例如：

\[ L=A\bar{B}\bar{C}+AB\bar{C}+A\bar{B}C+ABC \]

L=A\bar{B}\bar{C}+AB\bar{C}+A\bar{B}C+ABC

实际上等价于

\[ L=A \]

L=A

如何尽可能地化简得到的逻辑表达式呢？这就需要借助卡诺图了。

卡诺图是一种图形表示法，由美国工程师卡诺所发明。相比真值表，卡诺图更加简洁直观、灵活方便，但依然只适用于变量少的情况。

下面是我们之前素数真值表对应的卡诺图。直观来看，卡诺图是一张二维图表，横纵坐标均为输入变量的不同取值。

在这张图里，纵坐标为 AB、横坐标为 CD，对应的数值为 00、01、11、10。这样的排列保证了任何相邻的两个小方格在 ABCD 的坐标值上只有一位不同。例如，绿色框代表的输入为 ABCD=0101，蓝色框代表的输入为 ABCD=0111，仅有 C 一位不同。每一个小方格都与一种可能的输入对应。我们在每一个小方格中填入该输入对应的 out 值，也就得到了上图中的结果。

接下来是卡诺图最重要的一步：画圈。画圈需要满足下面的准则：

需要包含所有为 1 的方格，不能包含为 0 的方格；
圈可以重叠，但必须为矩形或正方形，且大小为 2 的幂；
每个圈需要尽可能大。换而言之，圈的数目应当尽可能少。

按照上面的准则画出的圈就可以得到简化的真值表。例如，素数电路的卡诺图画圈之后就如下图所示：

图中一共有四个圈。深绿色圈对应的变量取值为 \(AD=01\)，浅绿色圈对应的变量取值为 \(ABC=001\)，蓝色圈对应的变量取值为 \(BCD=101\)，黄色圈对应的变量取值为 \(BCD=011\)。

思考：黄色的圈？

为什么我们可以画出图中黄色的圈？

根据所画的圈，我们可以得到简化的逻辑表达式。

\[ out=\bar{A}D+B\bar{C}D+\bar{A}\bar{B}C+\bar{B}CD \]

out=\bar{A}D+B\bar{C}D+\bar{A}\bar{B}C+\bar{B}CD

1.4 实现

根据简化的逻辑表达式，我们可以编写如下的数据流级 Verilog 描述代码：

Prime.v
module Prime (
    input [3:0]                 in,
    output                      out
);
wire A = in[3];
wire B = in[2];
wire C = in[1];
wire D = in[0];
assign out = (~A&D) | (B&~C&D) | (~A&~B&C) | (~B&C&D);
endmodule

运行仿真的结果如下：

Prime_tb.v
module Prime_tb();
reg [3:0] in;
wire out;
initial begin
    in = 0;
    forever begin
        #10;
        in = in + 1;
    end
end
Prime prime (
    .in(in),
    .out(out)
);
endmodule

从波形上看，其已经实现了正确的结果。

思考

如果使用行为级描述，你会怎么编写代码呢？

例子：素数检测——后记

该同学十分感谢你的帮助，并表示等自己获得『诺贝尔数学奖』之后一定会 V 你 50 表示感谢。现在，他希望你能帮助他验证输入为 32bits 位宽时的结果。

乐于助人的你选择直接举报这位同学，并从此不再考虑这一问题。

事实上，更复杂的情况下，我们往往难以列出完整的真值表，而是可以将代表特定功能的组合逻辑模块进一步组合以实现高级的功能，这时的程序设计体验就与高级语言更加接近了。例如，当我们将全加器组合成32位加法器时，我们是在从计算层面的“进位”去考虑连接方式，而非给32位加法结果的每一位去设定真值表进行连接。

参考资料

最后更新: October 25, 2023

★ 设计流程

1.1 真值表

1.2 逻辑表达式

1.3 卡诺图

1.4 实现

评论