使用Java语言实现数字电路模拟器

 此项目代码已上传到GitHub，仓库地址为

GitHub - Ran-a/A-Simulator-for-Digital-Circuits: 使用java语言实现了SICP中第三章中的数字电路模拟器，考虑了时间延迟。

1  项目背景

      《Structure and Interpretation of Computer Programs》(缩写为SICP，中文名为《计算机程序的构造和解释》)这本书中的3.3.4小节"A Simulator for Digital Circuits"（数字电路模拟器）提供了设计一个数字电路模拟器的思路以及使用JavaScript语言的实现代码。在阅读并理解了这一章节的内容后，根据书中的描述和代码使用java语言实现了半加器的模拟器。

2  数字电路模拟器的介绍

       设计复杂的数字系统（digital systems），例如计算机，是一种非常重要的工程活动。数字系统都是通过一些简单元件构造起来的。虽然这些元件单独看起来功能都很简单，它们连接起来形成的网络就可能产生非常复杂的行为。对数字电路使用计算机程序模拟，是一种数字系统工程师广泛使用的重要工具。

        本项目是通过event-driven simulation（事件驱动的模拟）模拟的。事件驱动的模拟意思是一些事件（“活动”）的发生引发一些其他事件的发生，这些事件的发生又会引发随后事件的发生，并如此继续下去。

       本项目中的数字电路模拟器是使用Java语言编写的计算机程序，模拟数字电路中的半加器。半加器的特点有

• 由1个非门、1个或门、2个与门和6根导线组成；
• 暴露给用户的导线为图1中的A、B、C、S；
• A、B为输入导线，用来输入信号值；
• C、S是输出导线；
• C导线上信号值为A导线上信号值和B导线上信号值之和向高位的进位；
• S导线上信号值为A导线上信号值和B导线上信号值之和；
• 半加器不考虑来自低位的进位；
• 半加器的真值表如表1所示；
• 由于组成半加器的逻辑门存在时间延迟，所以半加器存在时间延迟；                                    

         图1所示为半加器的电路图，该图来自书籍《Structure and Interpretation of Computer Programs》。

表1 半加器真值表

A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

 3  实现思路

        上文提到半加器由与门、非门和或门这些基本逻辑门以及导线组成。以下是这些组成部分的功能和特点。

        导线可以传递数字信号，一个数字信号在任何时刻都只能为0或1；

        基本逻辑门根据输入信号计算出相应的输出信号。基本逻辑门的计算需要时间，所以输出信号具有时间延迟，具体延迟时间依赖于基本逻辑门的种类。

        例如非门是一种基本逻辑门，它会对输入信号做非操作。如果一个非门的输入信号为1，那么在一个非门的延迟时间单位之后，这个非门就输出信号值为0的信号；如果一个非门的输入信号为0，那么在一个非门的延迟时间单位之后，这个非门就输出信号值为1的信号。

        我们可以将基本逻辑门通过导线连接起来，构造出更复杂的功能。

        连接方法就是将一个基本逻辑门的输出导线作为其他基本逻辑门的输入导线，例如图1所示半加器的电路。由于延迟的存在，这些输出可能在不同的时间产生。

        我们可以根据图1半加器的电路图，将1个非门、2个与门和1个或门通过导线连接起来。若使用Java语言编写计算机程序来模拟将以上提到的基本部件通过导线连接起来的过程，那么我们需要分别实现非门类Inverter类、与门AndGate类、或门类OrGate类和导线类Wire类作为实现半加器的基本部件。将以上部件通过导线连接起来形成半加器类后，半加器类又可以作为更复杂的电路的部件。

        假设我们已经实现了基本部件与门类（AndGate类）、或门类（OrGate类）、非门类（Inverter类）和导线类（Wire类），那么我们可以将AndGate类的对象作为组成半加器的与门，将OrGate类的对象作为组成半加器的或门，将Inveter类的对象作为组成半加器的非门，再通过将Wire类的对象作为基本逻辑门类构造函数的参数，实现模拟通过导线连接各个基本逻辑门从而组成半加器的过程。

        关键代码如下。

    Wire a = new Wire();Wire b = new Wire();Wire s = new Wire();Wire c = new Wire();Wire d = new Wire();Wire e = new Wire();AndGate andGateLeft = new AndGate(a, b, c);OrGate orGate = new OrGate(a, b, d);Inverter inverter = new Inverter(c, e);AndGate andGateRight = new AndGate(d, e, s);

        实现半加器的代码又可以封装起来作为半加器类（HalfAdder 类）成为更复杂电路的基本部件。 例如2个半加器与1个或门又可以组成全加器。如图2所示为全加器的电路图，该图来自书籍《Structure and Interpretation of Computer Programs》。

        由图2所示，实现全加器时需要初始化2个半加器类HalfAdder的对象、1个或门类OrGate的对象和8根导线类Wire的对象作为组成全加器的部件。

        其中，A、B、、SUM、为暴露给用户的导线；

        A、B、为输入导线，SUM和为输出导线；

       其他导线的功能为连接全加器内部的各个部件。

        那么，我们可以初始化2个半加器类（HalfAdder类）的对象和1个或门类（OrGate类）的对象作为组成全加器的2个半加器和1个或门。再通过将Wire类的对象作为各个部件构造函数的参数，实现模拟通过导线连接各个部件从而组成全加器的过程。

        关键代码如下所示。

    Wire a = new Wire();Wire b = new Wire();Wire cIn = new Wire();Wire s = new Wire();Wire cOut = new Wire();Wire d = new Wire();Wire e = new Wire();Wire f = new Wire();HalfAdder halfAdderUp = new HalfAdder(a, d, s, e, agenda);HalfAdder halfAdderDown = new HalfAdder(b, cIn, d, f, agenda);OrGate orGate = new OrGate(e, f, cOut, agenda);

         将全加器封装为全加器类（FullAdder类）后，我们就又可以将全加器类的对象作为其他更复杂电路的部件了。

        接下来介绍基本部件与门类（AndGate类）、或门类（OrGate类）、非门类（Inverter类）和导线类（Wire类）的实现过程。

 4  类的概况和类图

           在使用Java语言实现数字电路模拟器的计算机程序时，共需创建9个类，如图3所示。

            本项目类图如图4所示。

        接下来介绍图3中包含的类在电路中所代表的角色，详细功能和实现细节将在第六节、第七节和第八节详细说明。

        （1）AndGate类

                AndGate类代表基本逻辑门与门。

        （2）OrGate类

                OrGate类代表基本逻辑门或门 ；

        （3）Inverter类

                Inverter类代表基本逻辑门非门；

        （4）Wire类

                Wire类代表电路中的导线；

        （5）HalfAdder类

                HalfAdder类代表半加器；

        （6）Ciruit类

               Ciruit类代表电路，可以在该类中组合部件，形成想要实现的电路；

        （7）Action类

                Action类代表要执行的动作；

        （8）Segment类

                Segment类由代表时间的变量time和动作action组成。在time时刻执行动作action。

        （9）Agenda类

                Agenda类由代表当前时刻的变量currentTime和若干Segment对象组成，定义为待处理表。

5  梳理对象间协作过程

        使用顺序图梳理本项目中各类对象之间的协作。以下是本项目关键操作的顺序图图示。

        （1）为导线（Wire对象）添加动作

        由于电路是由“信号的改变”事件驱动的，1根导线上信号值的改变会其他导线信号改变，所以我们可以设置add_action（）方法，为导线绑定动作，当导线信号值改变时，执行已绑定的动作。

        通过add_action()方法为导线添加动作（Action对象），add_action()方法向action_functions数组中添加Action对象action并执行action。

        “为导线添加动作”的顺序图如图5所示。

        （2）执行导线上添加的所有动作

        由于导线上添加的动作不止一个，所以需要设置一个方法遍历导线上添加的所有动作并执行。

        执行导线上添加的所有动作由call_each()方法实现。当Wire对象的信号变化时，call_each()方法遍历Wire对象的action_functions数组中的Action对象并执行。

        “执行导线上添加的所有动作”的顺序图如图6所示。

        （3）一段时间后执行动作

        由于基本逻辑门具有时间延迟，所以在模拟电路时需要考虑时间延迟。

        在基本逻辑门的输入信号值改变时并不立即执行基本逻辑操作的动作，而是需要在1个基本逻辑门的延迟时间单位之后执行对应基本逻辑操作的动作，所以我们通过设置方法将延迟时间和要执行的动作写入待处理表agenda。

        在一段时间后执行基本逻辑操作由after_delay()方法实现。after_delay()将要执行的动作action和执行动作的时刻time添加到待处理表（Agenda类的对象agenda）中，当agenda的currenTime与time相等时，执行action。

        “一段时间后执行动作”的顺序图如图7所示。

         （4）执行待处理表中的动作

        after_delay()方法将延迟时间和要执行的动作写入了待处理表agenda中，我们需要按照agenda待处理表中的当前时刻和延迟时间执行相应的动作；

        agenda中的动作执行又会导致电路中导线信号的变化，导线信号的变化会导致agenda更新，添加新的action和执行时间，直到agenda中的action被全部执行完毕。

        执行待处理表(Agenda类的对象agenda)的操作由propagate()方法实现。

        propagate()方法执行后，首先检查agenda是否为空，若为空，则不做任何操作；

        若不为空，那么利用方法first_item_agenda()方法获取segments数组中的第1个segement的time，将currentTime的值设为time的值，代表当前时间为time；

        令segments数组中第1个segment的actions的队头执行。

        通过remove_first_agenda_item()方法将已执行的action删除。

        执行待处理表中的动作的顺序图如图8所示。

6  基本部件的实现

        基本部件包含基本逻辑门与门、非门、或门和连接部件的导线。以下是基本部件的实现细节。

         1.AndGate类

          与门由2根输入导线和1根输出导线组成，且具有将2根输入导线上的信号值做逻辑与操作的功能。所以AndGate类中实现了如下功能。

           （1）创建2根导线作为与门的输入导线，1根导线作为输出导线；

    Wire andUp;Wire andDown;Wire andOutput;

          （2）定义与门的延迟时间；

int and_delay = 3;

          （3）在一个与门的延迟时间后将输出导线上的值赋值为输入导线上的信号值做逻辑与操作之后的值；

 public void and_action_procedure(){int newSignal = logical_and(andUp.getSignal(), andDown.getSignal());Action action = new Action();action.setAction(() -> andOutput.setSignal_value(newSignal));action.setActionName("seg_and()");Ciruit.agenda.after_delay(and_delay, action);}

         （4）将（3）所描述的方法通过add_action()方法添加到与门的2根输入导线上；

andUp.add_action(action);
andDown.add_action(action);

         （5）logical_and()方法的功能为将2个信号值做与操作，实现细节如下。

public int logical_and(int signalUp, int signalDown){if (signalDown == 1 && signalUp == 1) {return 1;}return 0;}

        2.OrGate类

        或门由2根输入导线和1根输出导线组成，且具有将2根输入导线上的信号值做逻辑或操作的功能。所以OrGate类中实现了如下功能。

         （1）创建2根导线作为输入导线，1根导线作为输出导线；

    Wire orUp;Wire orDown;Wire orOutput;

         （2）定义或门的延迟时间；

int or_delay = 5;

         （3）在一个或门的延迟时间后将输出导线上的值被赋值为输入导线上的信号值做逻辑或操作之后的值；

            关键代码如下。

 public void or_action_procedure(){int newSignal = logical_or(orUp.getSignal(), orDown.getSignal());Action action = new Action();action.setAction(() -> orOutput.setSignal_value(newSignal));action.setActionName("seg_or()");Ciruit.agenda.after_delay(or_delay, action);}

         （4）将（3）所描述的方法通过add_action()方法添加到或门的2根输入导线上。

            关键代码如下。 

orUp.add_action(action);
orDown.add_action(action);

         （5）logical_or()方法的功能为将2个信号值做与操作，实现细节如下。 

public int logical_or(int signalUp, int signalDown){if (signalDown == 1 || signalUp == 1) {return 1;}return 0;}

        3.Inverter类

        非门由1根输入导线和1根输出导线组成，且具有将1根输入导线上的值做非操作的功能。所以Inverter类中实现了如下功能。

          （1）创建1根输入导线和1根输出导线；

    Wire inverterIn;Wire inverterOutput;

          （2）定义非门的延迟时间；

int inverter_delay = 2;

          （3）在一个非门的延迟时间后将输出导线上的值赋值为输入导线上的信号值做逻辑非操作之后的值；

           关键代码如下。

 public void inverter_action_procedure(){int newSignal = logical_inverter(inverterIn.getSignal());Action action = new Action();action.setAction(() -> inverterOutput.setSignal_value(newSignal));action.setActionName("seg_inverter()");Ciruit.agenda.after_delay(inverter_delay, action);}

         （4）将（3）所描述的方法通过add_action()方法添加到非门的1根输入导线上。

           关键代码如下。

inverterIn.add_action(action);

         （5）logical_or()方法的功能为将信号值做非操作，实现细节如下。  

public int logical_inverter(int signal){if (signal == 0) {return 1;}return 0;}

         4.  Wire类

        Wire类代表导线，包含4个成员变量，分别为

        signal_value，int型变量，代表导线上的信号值；

        action_functions，Action类对象的数组，代表导线上所添加的所有动作（Action类的对象）；

        wireName，String型变量，代表导线名；

        isChange，布尔型变量，记录导线的信号值是否被改变。

        Wire类包括以下功能。

         （1）获取导线上的信号值；

                  获取导线上信号值的方法为getSignal()，当Wire类的对象调用该方法时，返回Wire类对象的信号值

public int getSignal(){return this.signal_value;}

          （2）设置导线上的信号值；

                   若不为导线设置信号值时，导线上的信号值默认为0；

                   当为导线设置信号值（new_value）与导线上本来的信号值相同时，不做任何操作；

                   否则，将导线上的信号值设置为new_value的值；

                              将布尔型变量isChange设为true，说明导线上的值有变化；

                              执行call_each()函数，执行导线上添加的所有动作。

public void setSignal_value(int new_value){if (new_value != signal_value) {signal_value = new_value;isChange = true;call_each();}}

          （3）为导线添加动作（Action类的对象）；

                   方法名为add_action，将参数Action类的对象action添加到action_functions数组中，执行action动作。

    public void add_action(Action action){action_functions.add(0, action);action.execute();}

          （4）执行导线上的所有动作。

                   该功能由call_each（）方法完成，在该方法中遍历action_functions数组中的每个动作并执行。

public void call_each(){for (Action action : action_functions){action.execute();}}

7  动作类Action

        Action类代表要执行的动作，成员变量有

        action，表示要执行的方法；

        actionName，表示要执行动作的名称，方便打印到控制台。

       Action类包括以下功能。

        （1）执行action方法；

public void execute(){action.run();}

        （2）设置action要执行的方法；

public void setAction(Runnable action) {this.action = action;}

        （3）获取和设置action的名称；

    public String getActionName(){return actionName;}public void setActionName(String actionName) {this.actionName = actionName;}

8  时间延迟的实现

        时间延迟由待处理表Agenda类实现，Agenda类由代表当前时刻的int型变量currentTime和若干Segment的对象组成。Segment类和Agenda类的实现细节如下。

        1.  Segment类

        Segment类由代表时间的变量time和Action对象的队列actions组成。Action对象的actions队列在time时刻到来时，将队头出队并执行队头的ation。Segment类包含以下功能。

          （1）判断actions队列是否为空；

          （2）设置time变量的值；

          （3）获取time变量的值；

          （4）向segment对象中添加action对象；

          （5）获取actions队列中所有action的名字。

        2.  Agenda类

        Agenda类由一个代表当前时间的变量currentTime和Segment对象的数组segments组成。segments数组是由时间（segment中的time变量的值）递增的顺序排列的。一个新创建的Agenda对象里segments数组为空并且currentTime为0。Agenda类的功能如下。

          （1）向agenda中添加action和action运行的时刻；

                   实现向agenda中添加action和action运行的时刻功能的方法为after_delay()方法。

                   after_delay()方法传入的Action类对象action作为要为agenda中添加的action；

                   在参数delay（基本逻辑门的延迟时间）的基础上加上当前时刻，运算结果是执行该方法的时刻；

                   将执行该方法的时刻和action使用addToAgenda()方法添加到agenda中。

 public void after_delay(int delay, Action action){addToAgenda(delay + currentTime, action);}

          （2）向agenda的segments中添加action和执行aciton的时刻time；

                   向agenda的segments中添加action和执行aciton的时刻time由方法addToAgenda（)方法完成。

                   首先检查agenda中的segments数组是否为空。

                   若agenda中的segments数组为空，那么新建一个segment对象，将action添加到新建的segment对象中，将segment添加到segments数组中；

                   若agenda中的segments数组不为空，那么扫描整个agenda，检查其中各个segmen的时间（time变量）。

                   如果发现某个segment的时间与action要加入的时间相同，那么就添加到segment的actions队列中；

                   若遇到了比action要加入的时间更晚的时间，那么就新建一个segment，将该时间和action加入这个segment，将这个segment添加到更晚时间的segment之前；

                   若到达了agenda的末尾，就必须在末尾添加一个新的segment。

public void addToAgenda(int time, Action action){if (segments.size() == 0) {Segment newSegment = new Segment(time, action);segments.add(newSegment);}else{for (Segment segment : segments){if (segment.time == time) {segment.addToSegment(action);break;}else if (time < segment.getTime()) {int index = segments.indexOf(segment);Segment newSegment = new Segment(time, action);segments.add(index, newSegment);break;}else if (segments.indexOf(segment) == segments.size() - 1) {Segment newSegment = new Segment(time, action);segments.add(newSegment);break;}}}}

         （3）agenda中action的执行；

                  该功能由propagate（）方法递归实现。t

                  若segments数组为空时，不做任何操作；

                  否则，令agenda中segments数组中第一个segement的actions的队头出队，执行出队的action。

                 执行propagate()方法，直到agenda为空。

 public void propagate(){if (segments.isEmpty()) {return;}else{Action firAction = first_agenda_item();firAction.execute();remove_first_agenda_item();i++;System.out.println("========================================= ");System.out.println("agenda第 " + i + " 次更新");for (Segment segment : segments){System.out.println("time: " + segment.getTime() + " actions: " + segment.getActionsNames());}}propagate();}

          （4）更新当前时刻

                   当前时刻一直保持为agenda中的第一个segment中的时间。

public Action first_agenda_item(){if (!segments.isEmpty()) {Segment first_segment = segments.get(0);currentTime = first_segment.getTime();return segments.get(0).actions.element();}return null;}

9  执行结果

       在Cricuit类中初始化待处理表Agenda对象agenda；

static Agenda agenda = new Agenda();

        在main()方法中为半加器对象连接输入导线a、b和输出导线s、c。

        Wire a = new Wire();Wire b = new Wire();Wire s = new Wire();Wire c = new Wire();HalfAdder halfAdder = new HalfAdder(a, b, s, c);

        将输入导线a上的值设为1，执行propagate()方法；

        再将输入导线b上的值设为1，执行propagate()方法。

        b.setSignal_value(1);agenda.propagate();a.setSignal_value(1);agenda.propagate();

        执行程序，结果如下。

        （1）agenda中action出队入队过程、当前时刻的变化以及输出导线s、c上的信号值和值的输出时刻结果如下。

        （2）每根导线上添加的actions数组如下。

 

10  实验结论 

        由实验结果可得出结论

        （1）每次更新agenda时，agenda中动作的出队、入队和currentTime的值都符合半加器的数字电路模拟器的运行；

        （2）半加器的输出导线c、s的信号值符合半加器的真值表；

        （3）半加器得到输出信号的延迟时间符合预期；

        （4）每条导线上添加的动作符合预期；

        由结论可知，模拟半加器的计算机程序成功实现。

11  致谢

        首先感谢我的导师杨贵福老师为我布置这个任务，这个任务使我对计算机程序的编写有了更深刻的理解；

        感谢杨老师每天查看、评论并指导我的工作，及时为我指正方向以及指导我增加核心的顺序图和类图；

        同时感谢我的师兄田洪轩，在我无法模拟时间延迟为此头痛的时候与我讨论书中的实现方式和我的实现方式的区别，帮助我理解SICP书中的代码逻辑，使我真正理解了什么是“事件驱动”。