【计算机系统架构】从0开始构建一台现代计算机|布尔代数和基础逻辑门|第一章

• 博主简介：努力学习的22级计算机科学与技术本科生一枚🌸
• 博主主页： @Yaoyao2024
• 每日一言🌼: 勇敢的人，不是不落泪的人，而是愿意含着泪继续奔跑的人。
  ——《朗读者》

0、前言

首先，我们将简要介绍布尔代数，并学习如何使用逻辑门物理地实现布尔函数。然后，我们将学习如何使用硬件描述语言（HDL）指定逻辑门和芯片，以及如何使用硬件模拟器模拟由此产生的芯片规格的行为。这些背景知识将为项目 1 做好准备，在项目 1 中，您将构建、模拟和测试 15 个基本逻辑门。您在本模块中构建的芯片组稍后将用于构建计算机的算术逻辑单元（ALU）和内存系统。这将分别在模块 2 和模块 3 中完成。

1、布尔逻辑

1.1 二进制&布 尔值

我们知道，计算机底层存储的就是二进制（即’0，1‘序列）；我们平常生活中用到的都是十进制，二进制只是一种不同的数字表达形式，我想说的是，只要是10进制可以表示和运算的，二进制照样可以。

那么基于二进制，对二进制数字进行运算和处理的，有一门专门的学科或者说知识：布尔代数/布尔逻辑。

这个名字听上去挺吓人的，其实这是一个音译词，布尔指的是boolean，在英文里面代表“真”的意思，boolean的反面是·false假。一真一假，就像二进制1he0一样。总之，布尔值（只有2个），通常就是来表示对立的两种情况：

1.2：基础布尔操作

基于布尔值，我们有对布尔值（0,1)的设计的特殊操作，这是一个布尔代数系统。

比如下面的是布尔逻辑里面的 And与操作 和 Or或操作 以及 NOT非操作：

对于上面各个操作下面的表，它的名字叫做 "truth table"真值表。左边表示输入的数，最后一列表示运算的结果。
将所有可能的布尔取值列出，即可得到真值表，真值表和对应的布尔操作是等价的，可以认为它们是布尔逻辑的不同表达方式！

1.3：布尔逻辑表达式和布尔逻辑函数

• 布尔表达式（Boolean Expressions): 通过对基本操作的组合，即可得到布尔表达式
  
• 布尔函数（Boolean Functions):
  不固定布尔取值，用未知数代替，我们就得到了布尔函数，它表示了一种逻辑。具体是什么逻辑呢？我们可以列出其真值表看这个函数的布尔逻辑。
  

1.4 布尔逻辑代数的性质

🪧Tips:这些等价为什么呢？不是随便规定的，而是它们的真值表相同！！！

1.5 布尔代数

本质上也就是我们基于上面的性质的对布尔表达式或者函数的运算法则：

当然，我们也可以列出布尔函数的真值表，从而根据真值表进行化简：

2、组合布尔逻辑函数

在上一节中，我们从理论的角度理解的布尔代数这一基于布尔值的运算系统。我们知道有3个基本的布尔逻辑运算：And、Or、Not。

这一节，我们依旧是在理论的层次上进行学习（先不讨论如何在计算机里面用硬件实现），学习如何基于这些基本的逻辑运算，实现我们想要的更为复杂的布尔逻辑函数，即：将基础布尔逻辑函数合成复杂的布尔函数。

2.1 从真值表得到布尔函数（构造主析取范式）

在第一节中，我们知道，如何 从布尔逻辑函数得到等价的真值表；无非就是把自变量的布尔取值穷举列出即可。

而这一小节恰恰相反，我们要先根据我们想要实现的逻辑列出真值表，再根据真值表得到一个简洁的布尔函数：

🪧为什么我们要这么做呢？
以为我们设计计算机时也是这样，首先列出逻辑的真值表，根据真值表写出逻辑函数，再根据逻辑函数用硬件将其实现（每一个操作都对应一个具体的硬件，比如And操作就是一个硬件来实现）。

而如何构造呢？不用担心，我们有一种标准的方法→“构造析取正则表达式（主析取范式）”

这里我们先不要管这个名字，看看它是如何操作的：

1. 首先，从真值表的第一行开始，依次向下查找，查找哪一行的结果为1

2. 对于取值为1的这一行，我们将它x取值为0的写为NOT(x)，如果取值为1直接写为x，然后把自变量使用And（也就是合取)合取起来：

3. 这样，每一个取值为1的行，都可以得到一个使用 Or析取连接，从而得到最终的“析取正则表达式“

之后再根据布尔代数的性质进行根据需要的化简，得到最终的等价表达式：

补充：有的得到的逻辑表达式有的可能最短，有的可能实现起来最高效，但关键是，这些表达式都是等价的！！！而找出最短或者找出最高效的等价表达式并不是一件容易的是，在算法上，这个问题称为”NP难“问题。

2.2 与、或、非可以表达任何逻辑函数

通过上述的从真值表得到逻辑函数方法，我们可以确定的是，根据真值表，只使用And、Or、Not，我们可以得到任意的逻辑函数！

对比于我们的十进制的运算，只使用加减乘除不可以表示所有的函数~

正是由于布尔代数这点，我们就可以使用基本的逻辑门（也就是与或非的具体硬件）来实现各种复杂的逻辑~~

2.3 与或非并不是缺一不可

使用与或非的确可以实现任意的逻辑函数。但是，少一个可以吗？？

其实是可以的，比如下面老师就举例仅仅使用And和Not就可以实现Or，那么我们就可以不需要Or:

2.4 与非门NAND可以实现任意逻辑函数

通过2.3我们知道，只需要And和NOT我们可以实现OR，从而实现任意的逻辑函数。

下面要提到的与非门NAND，只需要它一个，则可以实现任意逻辑函数。这是怎么回事呢？

其实只要证明NAND可以实现AND和NOT即可：

❓那么，通过2.1我们明白了如何从真值表写逻辑表达式（主析取范式），且与非门NAND这种简单的逻辑门可以实现And,Not,Or，那么我们肯定希望把得到的逻辑表达式转换为只使用NAND表达的逻辑函数。即：如何把主析取范式转换为NAND逻辑表达式，同时这也是如何根据逻辑表达式写复合逻辑门图形符号的方法（我们希望用NAND门来实现）。

观察主析取范式，我们发现它的核心就是把Or变成Nand，这就用到”德摩根定律“：

3、逻辑门（Logic Gates)

上面的1,2小节，是从一种抽象的角度取思考计算机使用的这套基于二进制和布尔代数的运算系统。这一小节，我们要从具体的构成计算机的硬件（芯片）去思考，实现AND和NAND这些具体运算的硬件是什么？它们是如何构建？

3.1 逻辑门（Gate Logic)是什么

🌸逻辑门是一种简单的基本的芯片，用来实现基本布尔逻辑运算（Nand、And、OR、NOT)以及合成的复杂逻辑运算（Mux、Adder,...),前者称为基本逻辑门（Elementary Logic Gates)后者称为复合逻辑门(Composite Logic Gates)。

逻辑门本质是对布尔代数系统的具体实现。

3.2：基础逻辑门：与非门NAND

下面是对于NAND这种基础逻辑门（芯片）的表达方式：图形、函数、真值表

⭐关于gate diagram逻辑门的图形，其实这是一种常用的”封装“思想的体现，a,b其实代表的就是输入，out是输出，而中间的部分是具体的实现，被封装起来了，我们只需要关注a,b,out这些输入输出接口(interface) ，直接使用即可。

Tips：关于具体的物理实现，了解的话就是”三极管“的实现（模电里面会讲），那么这门课其实不会讲到这个层次，我们只需要知道有一个基本逻辑门芯片，可以实现布尔逻辑即可。基于这个，我们再向上构造计算机。

⭐补充：对于逻辑门的interface，它是回答了What，比如对于上面的与门，它就表示输入ab结果可以得到与操作的结果out；如果你想知道物理是的具体实现，那么就是implementation。interface是唯一的，但是implementation是多样的。

3.3：基础逻辑门：与或非

3.4：组合逻辑门（Composite Gates)

复合逻辑门本质上也是由上面的基础逻辑门进行组合而来的：

3.5：逻辑门的物理实现

在讲到逻辑门的具体物理实现时，老师举出来了其中一种实现，也就是下图左上角使用导线、开关、灯泡的一种实现。但是如果深入了解逻辑门芯片的具体实现的话，我们知道，现在主要用到的就是晶体管。

老师也提到，在这门课中并不会去讲具体的实现（这是EE;electrical engineering电工学，而不属于计算机科学）。而这门课则是在已有的逻辑门（与非门）的基础上，在这个层次上去讲计算机的构成。

但是通过对模电和数电的学习,我们也能大概清楚：

下面分别展示的是使用二极管和三极管电路实现的基本逻辑门

4、HDL硬件设计语言

在上文我们讲到，不管是基础逻辑门还是复合逻辑门，它们本质都是 对其布尔函数的具体实现。

那么， 如何去根据已有的布尔函数，去设计具体的逻辑门呢？

当然不是直接拿逻辑门芯片去一个个连，我们有一种更简单的方法，使用一种类似于编程的方法，用一种语言在电脑上模拟这种逻辑门，这种方式首先把硬件的连接和设计模拟出来（用这种语言进行描述），并且进行测试，最终没有问题之后再使用硬件将其实现。这种语言就是：Hardware Description Laguage(HDL硬件描述语言）。

下面这张图：

• 首先，上半部分是对我们想要设计的一个逻辑门（芯片）的功能描述（可以使用语言或者真值表，但它的本质肯定是一个布尔函数）
• 下半部分就是HDL硬件描述程序，它包括这个芯片的名称、接口（输入和输出），以及具体实现。

4.1：HDL的编写

下面对HDL的编写进行讲解:

1. 首先，根据我们所需要的芯片的逻辑、真值表，我们可以得到一个布尔函数（这是逻辑门的抽象实现）

   Tips：这个布尔函数肯定有多种，下面是以析取正则表达式为例

2. 然后，根据布尔函数，我们可以知道这个逻辑门的具体实现（如右下角）
   

3. 那么最重要的一步就是：如何根据这样一个逻辑门的图来编写具体实现的代码

4. 首先，我们留出接口，对其中具体实现部分进行封装（画出如下虚线），其中输入输出接口就是用户视角能够看到的东西（用户只知道这个芯片有a,b两个输入接口以及out这个输出接口—），它们不属于具体实现部分。

5. 然后我们再关注具体实现部分：具体实现部分如上图是由基础逻辑门实现的，这些基础逻辑门在HDL中可以直接描述和使用：我们需要给出用到的这个逻辑门的名称（And,Not,Or)，以及它们的输入和输出（这些名称、接口名称都是规定好的，需要根据这个基础逻辑门的API接口书写）。

6. 对于具体实现部分中关键的一点就是：连接名（图中红色线部分，连接两个不同芯片），它不但表示了这个导线的名称同时也代表了这个导线上的信号名，这是我们自己定义的。
   

最终，确定好芯片名称、接口名称、具体实现部分（PARTS)，我们就编写好了一份HDL程序，它描述了使用基本逻辑门构建的复合逻辑门芯片：

⭐总结：

• HDL程序只不过是描述逻辑门连接图（芯片设计图）的一种语言
• 对于一个芯片，它的接口是用户看到的，且是唯一的；实现部分是多样的，取决怎么设计。

4.2：HDL是什么性质的语言

1. HDL is a functional/declarative language
   这意味着，像函数声明一样，你写一个函数声明的程序，而没有去调用这个函数，那么这个程序是不会执行且不会产生什么结果的。HDL只不过是对逻辑门连接图的一个静态描述。

2. The order of HDL statements is insignificant
   因为HDL是一种静态的描述性的程序，它不会去执行；因此，在编写HDL程序时，其实语句的顺序并不重要；但是我们会习惯性地按照逻辑门设计图从左往右从上往下编写。

3. Before using a chip part, you must know its interface. For example:Not(in=, out = ), And(a= , b= , out= ),
   因为芯片的设计也是基于其他已经设计好的现成的逻辑门进行的，比如我们在使用And时，我们必须事先清楚它的引脚（接口）名称，才能正确编写HDL程序，这是HDL的语法规则；而通常这些引脚名称需要查看对应的文档；在本门课程中，引脚名称使用a,b,c...作为输入引脚，out作为输出引脚。

常见的HDL语言有以下几种：

1. VHDL
2. Verilog
3. …

本门课程中的HDL是比较简单的，和其他HDL语言大致相似

5、基于HDL进行硬件模拟

上文我们知道了什么是HDL，它是一种对硬件（也就是芯片、逻辑门）的一种描述，如何基于HDL将这个芯片进行使用上的模拟、测试呢？

现在有专门的这种软件，比如我在逻辑课上用到的ISE这个软件，你就可以在这个软件里面编写HDL程序，然后再编写测试文件，使用这个软件进行对这个HDL程序的模拟和测试来判断这个芯片设计的逻辑是否正确。

想知道你用HDL设计的这个芯片是否正确就需要用到测试文件对这个芯片进行模拟和测试。

5.1：步骤

1. 首先，我们把HDL程序导入模拟器（一般的IDE里面都会有模拟的功能）。

2. 接着，我们需要编写一个测试文件(test scripts)；测试文件就是表名你要输入什么样的数据，然后将结果进行输出（你可以写多组不同的输入数据来对这个芯片进行系统的测试）

3. 然后，将HDL以及对应的测试问价加载到模拟器，进行模拟；模拟器则会给出根据测试文件的输入数据得到的测试结果；测试结果也成为输出文件，通过把测试结果和正确的输出结果进行对应则可以判断该HDL的编写是否正确。

这门课也自己开发了一款在线的IDE，可以进行编写HDL以及进行测试→https://nand2tetris.github.io/web-ide/chip/

如下图，左侧是HDL编辑区，中间是模拟结果展示区，右侧是测试文件，黄色高光表示测试文件执行到了这一行，点击右边栏上面的箭头可以使测试文件继续向下执行，同时可以在中间实时看到输出结果。

右边栏上面的Test script、Compare file…也可以点击，进行查看输出文件以及与正确的输出文件的对比。

5.2：硬件的构造流程

首先，在一个芯片构建的过程中，有两个角色：

1. 系统架构师

   • 确定这个硬件的逻辑功能
   • 将一整个复杂芯片分为几个基本的芯片（lower levels)
   • 确定好芯片的接口（个数、名称）
   • 确定好测试文件
   • 确定好比较文件

2. 开发人员

   • 编写HDL，进行芯片具体的逻辑实现

在我们学习这门课程的时候，老师其实就是系统架构师的角色，而我们就是开发人员的角色，我们的目标是实现一台现代计算机，这个可以分为多个基本的芯片组合而成。而我们就是要从底层的基本芯片一步一步向上，根据这个芯片的功能和API进行具体功能的实现。

5.3：一点HDL的细节：多位总线( multi-way bus)

我们知道，逻辑门处理数据的基本单位都是比特`bit，但是有的时候我们会常常把一组比特位整体进行考虑和计算，这样会比较方便。

比如，整数在计算里存储为16个比特位，我们设计两个整数相加的芯片时，会把一个数，也就是16个比特位作为一个整体来表示会比一位一位地去表示更为方便，这样我们能站在更高的一个抽象层次去解决问题。这样将一组比特位进行整体考虑的概念叫做多位总线（multi-way bus)。

就像上面这种，此时，输入接口和输出接口不再表示一个比特位，还是表示16个比特位。

同时，在HDL中我们可以如下图这样来表示多位总线：

一个需要注意的点就是，a[0]表示最右边的比特位，a[15]表示最左边的比特位

是不是感觉和数组很像？没错，使用方式也和数组一样。每一个位的下标也是从0开始，要想获得这个总线上具体某一个位，则用下标去指定即可：

对于这门课程的HDL，还有一个点不同的是，可以直接获得总线中的子总线，也是用下标来表示范围即可：

6、本课程的方法论&项目1

6.1 方法论

其实在5.2小节已经谈到过了。这里老师也用了一张很有趣的图来表示：

这门课程的目标是构建一台现代计算机。但是这个复杂的工程又可以拆解为30个芯片，一步一步来构建，而我们要做的就是按照逻辑需求去实现这些芯片然后构建这台计算机。

6.2 project01概述

文档:https://drive.google.com/file/d/17Rt3z7_OvpoQNlM6xtmC67Rn3blgM4W5/view

简而言之，NAND与非门是给定的，我们要依次从上到下构建芯片。

老师也给出我们为什么要先构造这些逻辑门的原因：

1. “They are commonly used gates”
   这些门被经常用到
2. “They comprise all the elementary logic gates needed build our computer”
   它们是组成现代计算机所需要的所有基本逻辑门

根据结构的相似性，老师将上述逻辑门分为以下三类：

6.3 Elementary logic gates

1) Not

/**
 * Not gate:
 * if (in) out = 0, else out = 1
 */
CHIP Not {
    IN in;
    OUT out;

    PARTS:
        Nand(a= in, b= in, out= out );
}

2) And

/**
 * And gate:
 * if (a and b) out = 1, else out = 0 
 */
CHIP And {
    IN a, b;
    OUT out;
    
    PARTS:
     Replace this comment with your code.
    Nand(a= a, b= b, out= aNandB);
    Nand(a= aNandB, b= aNandB, out= out);
}

3) Or

以为我们已经实现了Not和And

$$not(AorB)=(notA)and(notB)(德摩根定律）$$
$$AorB=not[(notA)and(notB)](德摩根定律）$$

/**
 * Or gate:
 * if (a or b) out = 1, else out = 0 
 */
CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
     Replace this comment with your code.
    Not(in= a, out= notA);
    Not(in= b, out= notB);
    And(a= notA, b= notB, out= notNotANotB);
    Not(in= notNotANotB, out= out);
}

4) Xor

$$AXorB=(notAandB)or(AandnotB)$$

/**
 * Exclusive-or gate:
 * if ((a and Not(b)) or (Not(a) and b)) out = 1, else out = 0
 */
CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
     Replace this comment with your code.
    Not(in= a, out= nota);
    Not(in= b, out= notb);
    And(a= a , b= notb , out= aAndNotb);
    And(a= nota, b= b, out= notaAndb);
    Or(a= aAndNotb, b= notaAndb, out= out);
}

5) Mux（数据选择器/⭐含卡诺图化简

🪧mux是Multiplexor“多路传输”的缩写，意思是选择器，从多个线路选择一个信号

使用2.1节的根据真值表构造主析取范式，可以得到一个逻辑表达式。下面补充了一个基于主析取范式再次化简的方法（画卡诺图）：

/** 
 * Multiplexor:
 * if (sel = 0) out = a, else out = b
 */
CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
     Replace this comment with your code.
    And(a= a, b= b, out= aAndB );
    Not(in= sel, out= notSel);
    And(a= a, b= notSel, out= aAndNotSel);
    And(a= b, b= sel, out= bAndSel);
    Or(a= aAndB, b= aAndNotSel, out= aAndBOrAAndNotSel);
    Or(a= aAndBOrAAndNotSel, b= bAndSel, out= out );
}

6) DMux 及其作用

Dmux是Demultiplexer的缩写，它像是Mux的相反逻辑：

/**
 * Demultiplexor:
 * [a, b] = [in, 0] if sel = 0
 *          [0, in] if sel = 1
 */
CHIP DMux {
    IN in, sel;
    OUT a, b;

    PARTS:
     Replace this comment with your code.
    Not(in= sel , out= notSel);
    And(a= in, b= sel, out = b);
    And(a= in, b= notSel, out= a);
}

⭐关于Mux和Dmux在网络信息传输中的作用：

在计算机网络传输的过程中，比如我现在在看网课，其实网络传输通道中有来自好几个渠道的信息：视频画面信息、音频信息… 这个多个渠道的信息是如何通过1根网线传输，又是如何不会错乱的呢？这其中就是Mux和DMux配合进行的：

如上图，信息通过数据选择器汇入一个通路，再通过DMux进行信号的分离。

6.4：16-bit variants

16位多线总位很简单，其实就是上述基本逻辑门的扩展，1bit的And变成16bit位分别And

1) Not16

/**
 * 16-bit Not gate:
 * for i = 0, ..., 15:
 * out[i] = Not(a[i])
 */
CHIP Not16 {
    IN in[16];
    OUT out[16];

    PARTS:
     Replace this comment with your code.
    Not(in=  in[0] , out= out[0]);
    Not(in=  in[1] , out= out[1]);
    Not(in=  in[2] , out= out[2]);
    Not(in=  in[3] , out= out[3]);
    Not(in=  in[4] , out= out[4]);
    Not(in=  in[5] , out= out[5]);
    Not(in=  in[6] , out= out[6]);
    Not(in=  in[7] , out= out[7]);
    Not(in=  in[8] , out= out[8]);
    Not(in=  in[9] , out= out[9]);
    Not(in=  in[10] , out= out[10]);
    Not(in=  in[11] , out= out[11]);
    Not(in=  in[12] , out= out[12]);
    Not(in=  in[13] , out= out[13]);
    Not(in=  in[14] , out= out[14]);
    Not(in=  in[15] , out= out[15]);
}

2) And16

/**
 * 16-bit And gate:
 * for i = 0, ..., 15:
 * out[i] = a[i] And b[i] 
 */
CHIP And16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
     Replace this comment with your code.
    And(a= a[0], b= b[0], out= out[0]);
    And(a= a[1], b= b[1], out= out[1]);
    And(a= a[2], b= b[2], out= out[2]);
    And(a= a[3], b= b[3], out= out[3]);
    And(a= a[4], b= b[4], out= out[4]);
    And(a= a[5], b= b[5], out= out[5]);
    And(a= a[6], b= b[6], out= out[6]);
    And(a= a[7], b= b[7], out= out[7]);
    And(a= a[8], b= b[8], out= out[8]);
    And(a= a[9], b= b[9], out= out[9]);
    And(a= a[10], b= b[10], out= out[10]);
    And(a= a[11], b= b[11], out= out[11]);
    And(a= a[12], b= b[12], out= out[12]);
    And(a= a[13], b= b[13], out= out[13]);
    And(a= a[14], b= b[14], out= out[14]);
    And(a= a[15], b= b[15], out= out[15]);
}

3) Or16

/**
 * 16-bit Or gate:
 * for i = 0, ..., 15:
 * out[i] = a[i] Or b[i] 
 */
CHIP Or16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
     Replace this comment with your code.
    Or(a= a[0], b= b[0], out= out[0]);
    Or(a= a[1], b= b[1], out= out[1]);
    Or(a= a[2], b= b[2], out= out[2]);
    Or(a= a[3], b= b[3], out= out[3]);
    Or(a= a[4], b= b[4], out= out[4]);
    Or(a= a[5], b= b[5], out= out[5]);
    Or(a= a[6], b= b[6], out= out[6]);
    Or(a= a[7], b= b[7], out= out[7]);
    Or(a= a[8], b= b[8], out= out[8]);
    Or(a= a[9], b= b[9], out= out[9]);
    Or(a= a[10], b= b[10], out= out[10]);
    Or(a= a[11], b= b[11], out= out[11]);
    Or(a= a[12], b= b[12], out= out[12]);
    Or(a= a[13], b= b[13], out= out[13]);
    Or(a= a[14], b= b[14], out= out[14]);
    Or(a= a[15], b= b[15], out= out[15]);
}

4) Mux16

/**
 * 16-bit multiplexor: 
 * for i = 0, ..., 15:
 * if (sel = 0) out[i] = a[i], else out[i] = b[i]
 */
CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];

    PARTS:
     Replace this comment with your code.
   Mux(a=a[0] , b=b[0] , sel= sel, out= out[0]);
   Mux(a=a[1] , b=b[1] , sel= sel, out= out[1]);
   Mux(a=a[2] , b=b[2] , sel= sel, out= out[2]);
   Mux(a=a[3] , b=b[3] , sel= sel, out= out[3]);
   Mux(a=a[4] , b=b[4] , sel= sel, out= out[4]);
   Mux(a=a[5] , b=b[5] , sel= sel, out= out[5]);
   Mux(a=a[6] , b=b[6] , sel= sel, out= out[6]);
   Mux(a=a[7] , b=b[7] , sel= sel, out= out[7]);
   Mux(a=a[8] , b=b[8] , sel= sel, out= out[8]);
   Mux(a=a[9] , b=b[9] , sel= sel, out= out[9]);
   Mux(a=a[10] , b=b[10] , sel= sel, out= out[10]);
   Mux(a=a[11] , b=b[11] , sel= sel, out= out[11]);
   Mux(a=a[12] , b=b[12] , sel= sel, out= out[12]);
   Mux(a=a[13] , b=b[13] , sel= sel, out= out[13]);
   Mux(a=a[14] , b=b[14] , sel= sel, out= out[14]);
   Mux(a=a[15] , b=b[15] , sel= sel, out= out[15]);
}

6.5 Multi-way variants

6.4小节是指有两个多位总线输入，然后分别将对于的位进行逻辑运算得到结果即可。这一小节则是实现将一个多位总线上的一起进行逻辑运算：

1) Or8way

/**
 * 8-way Or gate: 
 * out = in[0] Or in[1] Or ... Or in[7]
 */
CHIP Or8Way {
    IN in[8];
    OUT out;

    PARTS:
     Replace this comment with your code.
    Or(a= in[0], b= in[1] , out= t1);
    Or(a= in[2] ,b= t1, out= t2);
    Or(a= in[3], b= t2, out= t3);
    Or(a= in[4], b= t3, out= t4);
    Or(a= in[5], b= t4, out= t5);
    Or(a= in[6], b= t5, out= t6);
    Or(a= in[7], b= t6, out= out);
}

2) Mux4Way16

s00->A
s01->B
s10->C
s11->D

• s[0]负责从AB2选一，也负责CD2选一
• S[1]负责从mux16AB和mux16CD2选1

/**
 * 4-way 16-bit multiplexor:
 * out = a if sel = 00
 *       b if sel = 01
 *       c if sel = 10
 *       d if sel = 11
 */
CHIP Mux4Way16 {
    IN a[16], b[16], c[16], d[16], sel[2];
    OUT out[16];
    
    PARTS:
     Replace this comment with your code.
    Mux16(a= a, b= b, sel= sel[0], out= out161);
    Mux16(a= c, b= d, sel= sel[0], out= out162);
    Mux16(a= out161, b= out162, sel= sel[1], out= out);
}

3) Mux8Way16

/**
 * 8-way 16-bit multiplexor:
 * out = a if sel = 000
 *       b if sel = 001
 *       c if sel = 010
 *       d if sel = 011
 *       e if sel = 100
 *       f if sel = 101
 *       g if sel = 110
 *       h if sel = 111
 */

CHIP Mux8Way16 {
    IN a[16], b[16], c[16], d[16],
       e[16], f[16], g[16], h[16],
       sel[3];
    OUT out[16];

    PARTS:
     Replace this comment with your code.
    Mux4Way16(a= a, b= b, c= c, d= d, sel= sel[0..1], out= mux161);
    Mux4Way16(a= e, b= f, c= g, d= h, sel= sel[0..1], out= mux162);
    Mux16(a= mux161, b= mux162, sel= sel[2], out= out);

}

3)DMux4Way

/**
 * 4-way demultiplexor:
 * [a, b, c, d] = [in, 0, 0, 0] if sel = 00
 *                [0, in, 0, 0] if sel = 01
 *                [0, 0, in, 0] if sel = 10
 *                [0, 0, 0, in] if sel = 11
 */

CHIP DMux4Way {
    IN in, sel[2];
    OUT a, b, c, d;

    PARTS:
     Replace this comment with your code.
    DMux(in= in, sel= sel[1], a= in1, b= in2);
    DMux(in= in1, sel= sel[0], a= a, b= b);
    DMux(in= in2, sel= sel[0], a= c, b= d);
}

4) DMux8way

/**
 * 8-way demultiplexor:
 * [a, b, c, d, e, f, g, h] = [in, 0,  0,  0,  0,  0,  0,  0] if sel = 000
 *                            [0, in,  0,  0,  0,  0,  0,  0] if sel = 001
 *                            [0,  0, in,  0,  0,  0,  0,  0] if sel = 010
 *                            [0,  0,  0, in,  0,  0,  0,  0] if sel = 011
 *                            [0,  0,  0,  0, in,  0,  0,  0] if sel = 100
 *                            [0,  0,  0,  0,  0, in,  0,  0] if sel = 101
 *                            [0,  0,  0,  0,  0,  0, in,  0] if sel = 110
 *                            [0,  0,  0,  0,  0,  0,  0, in] if sel = 111
 */

CHIP DMux8Way {
    IN in, sel[3];
    OUT a, b, c, d, e, f, g, h;

    PARTS:
     Replace this comment with your code.
    DMux(in= in, sel= sel[2], a= in1, b= in2);
    DMux4Way(in= in1, sel=sel[0..1] , a= a, b= b, c= c, d= d);
    DMux4Way(in= in2, sel=sel[0..1], a= e, b= f, c= g, d= h);
}