基于开源数字仿真软件Digital的“数字逻辑”及“计算机组成原理”课程实验设计

邢建国

摘要：本文介绍了一款开源数字电路仿真软件Digital在数字逻辑和计算机组成等课程实验中的应用，并呈现出四个不同复杂度的组合和时序电路的设计与实现。实践表明，该软件适合于计算机类专业学生学习和掌握诸如处理器一类复杂数字系统设计。

关键词：数字逻辑；计算机组成；Digital; 实验设计

中图分类号：G434  文献标识码：A  论文编号：1674-2117（2023）08-0095-06

前言

开源软件Logisim数字仿真软件是由Carl Burch开发的一款开源、免费的数字系统仿真软件。笔者所在学校用该软件重构了已有的大部分实验，很多学生利用该软件设计的系统也达到了实验要求。但在教学过程中笔者发现，Logisim无法直接使用Verilog模块，这对一些复杂模块如状态机、浮点运算器来说实现起来不方便，也难以调试。由Helmut Neemann开发的开源软件Digital则针对Logisim存在的一些问题重新进行了设计，并在底层架构上做了重大调整，增加了很多新的特色功能，比Logisim更适合于复杂数字系统的仿真实现，其主要特点包括：①支持与、或、非等基本逻辑模块，以及一些输入输出设备、计算、存储等复杂模块。②支持真值表、卡诺图、逻辑表达式以及状态机的电路综合。③支持波形显示，提供了测试用例（实际上提供了一种编写测试用例的小语言）。④支持Telent协议，外部应用可以与设计的电路系统进行通信，这为调试图像处理器的复杂系统提供了较大的便利。⑤可以将Verilog和VHDL编写的模块集成到设计的电路中（这些模块的仿真是通过Icarus Verilog和ghdl外部模拟器来实现的），也可以把设计的系统导出为Verilog和VHDL文件。

下面，笔者将通过具体的教学案例来说明该软件在数字逻辑、计算机组成等课程中的实际应用。案例包括超前进位加法器（组合逻辑）、最大公因子GCD电路（有限状态自动机）、階乘Factorial电路（下推自动机）以及一个8指令处理器BrainFxxK（图灵机）的实现。

设计案例

1.组合电路设计：超前进位加法器

加法是算术逻辑单元中的重要组件。最简单的加法器是由多个1位全加器串联起来的串行进位加法器。由于进位延迟大，该加法器速度与位数成反比。因此，实践中一般采用超前进位加法器，其基本思路是用专门的电路来并行计算出进位。对于一个n位加法：

{cout， sum} = a + b + cin

其第i+1位的进位逻辑表达式为：

c[i+1] = a[i] b[i] + （a[i] + b[i]） c[i]

其中a[i] b[i]为生成项，记为g[i]，a[i] + b[i]为传播项，记为p[i]。则c[i+1]可以表示为：

c[i+1] = g[i] + p[i] c[i]

= g[i] + p[i] g[i-1] + p[i] p[i-1] g[i-2] + ... + p[i] p[i-1]...p[1] p[0]cin

可以使用树形结构分层产生进位。为此笔者设计了gp模块，其功能是根据输入的两个加法器的g0、p0和g1、p1以及低位进位cin生成g、p和cout，其逻辑表达式为：

g = g1 | （p1 & g0）

p = p1 & p0

cout = g0 | （p0 & cin）

1位加法器模块为：

sum = a ^ b ^ cin

g = a & b

p = a | b

其在Ditigal中分别实现如图1所示。

可以使用2个1位加法器和1个gp构造一个2位加法器，如图2所示。

同样，可以使用2个2位加法器和1个gp构造1个4位加法器以及更多位数的加法器。

通过这个例子，可以发现Ditigal对一些简单的组合逻辑可以很方便进行抽象、重用，由此可以构造更复杂的系统。

2.有限状态自动机设计：最大公因子（gcd）

本案例是展示如何使用Digital的Verilog模块来简化状态机的实现。该例子用欧几里算法来计算两个正整数的最大公因子。该算法的Python实现如上页图3所示。

系统使用a和b两个寄存器、一个取模运算部件、一个比较器，其数据通路如图4所示。

另外，对应的状态机（增加了读取输入）的下一状态及对应输出如表1所示。

上述状态机对应的控制器，可以使用Digital的外部模块Verilog来实现下一状态、输出逻辑，其VerilogHDL代码如图5所示。可以看到，采用Verilog描述的状态机更易于理解和调试。

3.下推自动机设计：阶乘（fact）

本案例展示了Digital能够实现下推自动机这样的复杂系统。阶乘递归实现的Python代码如图6所示。

与案例二相比，除了最后一条语句，两者在结构上非常类似。在gcd中，最后一条语句是尾递归（Tail-recursion），即gcd（b，a%b）后面没有其他的计算了。而在fact中则不是，为了计算fact（n），要先计算fact（n-1），然后再计算n*fact（n-1）。而计算fact（n-1），又需要先计算fact（n-2）…，直到fact（0）计算完成，然后再计算fact（1）…fact（n-1）、fact（n）。我们称n*fact（n-1）是 fact（n-1）的延续（continuation），在软件中是函数调用后的返回地址，在硬件中则视为一个计算状态，可将其存储在堆栈中，当fact（n-1）计算完成后，再从堆栈中恢复continuation，完成fact（n）的计算。

笔者设计了一个包括n、val（保存计算结果）和continue（用于存储返回状态/地址）三个寄存器和一个堆栈（用于保存和恢复寄存器n、continue）、乘法器等部件的系统来实现阶乘，其数据通路如上页图7所示。

该系统要比gcd系统复杂得多，其对应的控制器状态转换如上页表2所示。

可以看到，为了实现fact的递归计算，笔者使用了16个状态和一个堆栈，这一设计要比案例二复杂很多。同样，使用Digital的外部Verilog模块可以大大简化这个状态机逻辑的实现，调试也更方便。

4.图灵机设计：Brainfxxk语言处理器

本案例是一个8指令处理器的Digital实现。Brainfxxk是由Urban Müller在1993年发明的一种只有8条指令的编程语言，该极小化的语言是图灵完备的，这意味着它可以实现其他任何一种图灵完备语言（如C语言或Python）完成的计算，甚至可以用它来写一个Brainfxxk自身的解释器。

该机器包括一个数组data、一个指向该数组某个单元的指针ptr、程序代码code、程序计数器pc，以及输入和输出装置。数组data里元素都初始化为零，数据指针初始时指向数组的第一个字节，pc指向第一条指令。其8条指令及其语义分别为：

'>'：将数据指针加一。

'<'：将数据指针减一。

'+'：将数据指针所指的单元加一。

'-'：将数据指针所指的单元减一。

'，'：从输入流中读取一个字节，存入数据指针所指单元。

'.'：输出数据指针所指单元的字节。

'['：如果当前单元是 0，那么跳转到对应的 ']' 的下一条指令，否则继续执行。

']'：如果当前单元不是 0，那么跳转到对应的 '[' 的下一条指令，否则继续执行。

其对应的C代码如表3所示。

下面这段代码：

+++>++<[->+<]>.

等价的C代码如图8所示。

该段代码首先将data第一个单元赋值为3（+++），第二个单元赋值为2（++），然后进入循环（[->+<]），如果第一個单元不为0，则将其减一，把第二个单元加一。在循环结束后，打印第二个单元的值（>.），结果为5。该代码的作用是将第一个单元值加到第二个单元，并打印。

该处理器除了两条循环指令实现比较复杂之外，其余6条指令的实现是比较简单的。上页图9为该处理器的一个参考实现。

图9中从左到右，依次为PC及计算下一PC值模块、程序ROM、控制器controller、数据指针ptr、数据data以及打印、输入模块。在图的左下方为一个堆栈stack，用于记录循环语句中的起始地址。

控制器的Verilog实现代码如图10所示。可以看到，Digital中对Verilog的支持大大简化了有关模块的设计，使设计更清晰、更易于理解和排错。

总结

对于初步具备数字电路基本知识以及C语言程序设计能力的计算类专业学生而言，使用Digital软件可以很容易了解复杂数字系统的设计和仿真，为进一步完成如流水线、指令动态调度以及转移指令预测等复杂模块提供基础。

参考文献：

[1]李亚民.计算机原理与设计——Verilog HDL版[M].清华大学出版社，2011.

[2]David Patterson & John Hennessy.计算机组成与设计——软硬件接口（RISC-V版）[M].北京：机械工业出版社，2020.