笔记仓库

正常人的正常笔记集

数字电路模拟

最近闲暇时在阅读的Structure and Interpretation of Computer Programs一书1,在介绍使用可变数据结构建模时,首先引入了队列(queue)和表(table)两个经典的数据结构实现作为基础,又在3.3.4 A Simulator for Digital Circuits试图用scheme实现一个数字电路的仿真。

根据编书结构来看,3.3.4确实算不上什么重要的部分,对于此书的学习路线来说甚至无足轻重到可以直接跳过,只当是前文提到的可变的,复合的数据结构应用在建模中的一次实战;然而就数字电路模拟这个应用场景本身来说,也并不能称得上是一个贴切的例子,这里提供的实现与真实世界中硬件电路的做法几乎没有关系;更恼人的是,这个部分的内容很好的根据了抽象屏障(abstract barrier)进行了自顶而下(top-down)的讲解,对于部分像我这样喜欢从底层开始动手实验和理解的读者来说,如此的解释顺序无异于灾难。于是这个部分的内容对我来说,便成为了想读却下手困难且不值得,想放弃又心有不甘觉得可惜的鸡肋。

但其实这部分读懂了又觉得还是有点意思的,就像2.3.2 Example: Symbolic Differentiation这个例子,虽然偏离实际但确实能极大提升对于递归的理解。从最底层开始亲自实现一遍数字电路也能很好的帮助我们去理解数据结构(data structure),求值环境(eval environment)和局部状态(local state)等概念。而且无论中英文网络上有关这部分的详解资料都不多,所以我决定自己动手写一篇短文带领所有可能在此遇到问题的人突破讲解材料的限制,拉住我伸出的手登上高处,看一看山下雄伟奇异的景色。理解这个有趣的例子,也同样是提升自信的一个途径,不像现实世界中其他优秀成功的人,我只是一个又丑又穷的底层失败者,所以读懂一个数字电路模拟实现已经是让我兴奋不已急于分享的喜事,当然对在座的优秀的,现实充实的读者们来说这可能只是微小的收获感,可哪怕只要有一个人能从我微小的贡献中受益,我也觉得是非常令我幸福的事了。

好了,接下来我们开始从零开始一层层往上用scheme实现一个完整的数字电路模拟器。

Agenda

我不知道该怎么翻译这个词比较合适,这里比较贴切的意思应该是议程,也有把这个对象形容成schedule的。因为我们最终要实现的是一个事件驱动的模拟(event-driven simulation)程序,通俗来说就是每当某个事件被添加到模拟过程时,才会触发电路的一些变化。创建一个agenda等于开始一个模拟过程,之后的任何操作都是对于这个agenda对象的操作。如果要你自己不限语言,而且不告诉你要实现的这个对象名叫agenda,凭着轮廓写这么一个东西,很多人大概会写成形如这样的(以C#为例):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
namespace simulation
{
public class Simulator
{
public string Name {get; set;}
public int currentTime {get; set;}
public Simulator(string name)
{
Name = name;
currentTime= 0;
}

public void add(int time, string action)
{
/* ...add some events... */
}
//Other properties, methods, events...
}

class simulation
{
static void Main()
{
Simulator s1=new Simulator("first_simulator"); // start a simulation
s1.add(1,"shut down");
//other operations
}
}
}

因为完成上述任务的数据结构,或者说对象,在很多人的直观理解中应该被称为simulator(笑)而agenda只是更具体的概括了这个simulator的类型,也就是这个simulator的内容到底是如何实现的,原来是通过存储和执行一系列时刻-动作对(time-action pair)来完成模拟的。请忘掉上面所写的残破的代码示例,接下来认真考虑该如何以scheme实现agenda

首先考虑这个时刻-动作对应关系应该如何表示:如同我们现实生活中的日程表,会记录每个时刻需要完成的事务。这里直接定义数据结构segment是一个包含一个数字(time即时刻)和一个队列(queue即任务列表)的对。

1
2
3
4
(define (make-time-segment time queue)
(cons time queue))
(define (segment-time s) (car s))
(define (segment-queue s) (cdr s))

如此一来,agenda可以被定义为segment的一维表(one-dimensional table)结构,而且表中这些项会按照time排序,换个角度来看,segement这种结构本质就是一种key-value对。另外,agenda会存储现在的时间current-time(最后进行的事件的时间)作为表的头部,而不同于原书在之前介绍的用"*table*"之类的表的名字作为哑元表头。新建的agenda还没有被添加任何事件时,没有任何segement在内,current-time被初始化为0

1
2
3
4
5
6
7
8
9
10
11
(define (make-agenda) (list 0)) ;returns a new empty agenda
(define (current-time agenda) (car agenda))

(define (set-current-time! agenda time)
(set-car! agenda time))
(define (segments agenda) (cdr agenda))
(define (set-segments! agenda segments)
(set-cdr! agenda segments))

(define (first-segment agenda) (car (segments agenda)))
(define (rest-segments agenda) (cdr (segments agenda)))

那么用来检查agenda是否为逻辑上的空对象的empty-agenda?就可以通过检查表头之后的segements是否为空来实现了。

1
2
(define (empty-agenda? agenda) ; is true if the specified agenda is empty
(null? (segments agenda)))

agenda添加动作action需要检查是否为空:

  • 如果是,为这个actiontime构造一个segement,并把这个segement放入agendasegements部分。
  • 否则,扫描表中每个segementtime
    • 如果发现指定时刻(action需要被添加的时刻)已经存在,那么把action直接添加到这个与time关联的queue中即可。
    • 如果已经扫描到比指定时刻更晚的time值,说明指定时刻不在segements中,那么为这个action和指定time创建一个新的segement并插入到这个被扫描到的segement之前。
    • 如果已经扫描到了agenda末尾,那么也说明指定时刻不在segements中,还是创建一个新的segement把这条记录放到agenda的末尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
(define (add-to-agenda! time action agenda)
;modifies the agenda by adding the given action procedure to be run at the specified time.
(define (belongs-before? segments) ;return true if our appointed time **isn't** in segements
(or (null? segments)
(< time (segment-time (car segments)))))

(define (make-new-time-segment time action) ;create a new segment for our time and action
(let ((q (make-queue)))
(insert-queue! q action)
(make-time-segment time q)))

(define (add-to-segments! segments)
(if (= (segment-time (car segments)) time)
(insert-queue! (segment-queue (car segments))
action) ;insert action into the queue our time associated
(let ((rest (cdr segments)))
(if (belongs-before? rest)
(set-cdr!
segments
(cons (make-new-time-segment time action)
(cdr segments))) ;insert new segement before the later or just at the end of agenda
(add-to-segments! rest)))))

(let ((segments (segments agenda)))
(if (belongs-before? segments) ;check if the agenda is null or just contains the later segements
(set-segments!
agenda
(cons (make-new-time-segment time action)
segments)) ;insert new segement at the head of segements
(add-to-segments! segments))))

可以明显的看出实现的细节上与上面描述的判定流程并不完全一致,比如最后两种情况的操作实际上是合并为belongs-before?,再比如检查agenda是否为空的操作也被合并到第一次调用belongs-before?中。当然,可能引起误解的部分我都已经在上面的代码中给了注释,有兴趣或者疑惑的朋友可以详细看一下。

删除agenda的第一项指删除第一个segementqueue的第一个action,并检查操作完成这个segementqueue是否为空,如果为空,则没有必要保留这个segement了。

1
2
3
4
5
(define (remove-first-agenda-item! agenda) ;modifies the agenda by removing the first item
(let ((q (segment-queue (first-segment agenda))))
(delete-queue! q)
(if (empty-queue? q)
(set-segments! agenda (rest-segments agenda)))))

当我们在诸如开始处理模拟等程序中,取agenda的第一项时,除了要读出第一个segementqueue中第一个元素,还需要把当前时间current-time设置为这一项action发生的时间

1
2
3
4
5
6
7
(define (first-agenda-item agenda) ;returns the first item on the agenda
(if (empty-agenda? agenda)
(error "Agenda is empty: FIRST-AGENDA-ITEM")
(let ((first-seg (first-segment agenda)))
(set-current-time! agenda
(segment-time first-seg))
(front-queue (segment-queue first-seg)))))

The-agenda

现在假设我们通过

1
(define the-agenda (make-agenda))

创建了一个新的,用于开始我们这次模拟的实例the-agenda,把所有需要完成的仿真行为添加到这个the-agenda中,所有的模拟都通过调用the-agenda相关程序实现。

很容易想象一个已经完成的数字电路应该具有这样的特性:

给出一些输入信号,在一定延迟时间后得到输出信号

而延迟时间因电路而异,这里暂时先不讨论,只讨论延迟的性质如何通过the-agenda模拟:利用带有时间参数delay和过程参数actionafter-delay过程,使得actiondelay时间后才被执行,那么直接的做法便是把action添加到the-agenda的当前时间延迟后的某个时间的执行队列:

1
2
3
4
(define (after-delay delay action)
(add-to-agenda! (+ delay (current-time the-agenda))
action
the-agenda))

开始我们的模拟进程需要一个propagate过程来按照时间和队列顺序执行the-agenda中的所有操作。当模拟运行时,不断的会有新的指令被添加到the-agendapropagate就会一直持续进行直至没有未被执行的操作留在the-agenda为止。

Note

这里暂时还没能实现监听器来实时监听事件的添加,所以原文中虽然给的是很具有迷惑性的说法

In general, as the simulation runs, new items will be added to the agenda, and propagate will continue the simulation as long as there are items on the agenda

但实际上我们可以看到后面的实现中,每当有新的操作被添加,完成上述任务的方法是紧随其后再调用一次(propagate)的伪实时监听。

1
2
3
4
5
6
7
(define (propagate)
(if (empty-agenda? the-agenda)
'done
(let ((first-item (first-agenda-item the-agenda)))
(first-item)
(remove-first-agenda-item! the-agenda)
(propagate))))

每个事件被执行后都被移出了the-agenda,防止多次调用(propagate)造成的重复执行。

Wire

整个数字电路模型的基本原件——导线是数字信号的载体,而数字信号只有两种可能的取值,高电平1和低电平0。除此之外,组成电路的还有我们之后会讨论的功能部件(function box),不同的导线可以接入这些部件作为输入,也可以作为输出。

我们先来构造一种计算对象wire来承载数字信号,用于表示导线。这种数据结构需要提供这些操作的接口:

  • (get-signal <wire>) 得到这根导线现在承载的数字信号值
  • (set-signal! <wire> <new value>) 改变它的值为指定值
  • (add-action! <wire> <procedure of no arguments>)将某个过程绑定到这根导线上,使得每当这根导线上的信号值发生改变的同时触发这个过程的执行。这些无参数的过程也是非常特殊的过程,执行时会与其他导线发生通信。

考虑如何设计数据结构wire时,我们可以像agenda一样把它想象成一个存储数据的结构,那么只需要存放两个局部状态变量

  • signal-value 一个取值为0或1的整数,表示这根导线上现在的数字信号值
  • action-procedures 一个list,存放所有被绑定到这根导线上的过程

直接的做法是把两个变量打包用cons打包成一个pair然后写一些把它作为参数的get/set操作,但原书中给出的实现示例是message-passing风格的,即构造完wire后返回一个带有本地局部状态变量的dispatch函数,它通过参数选择适当的局部函数返回。创建一个新的导线的命令(make-wire)可以写为如下过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(define (make-wire)
(let ((signal-value 0) (action-procedures '()))

(define (set-my-signal! new-value)
(if (not (= signal-value new-value))
(begin (set! signal-value new-value)
(call-each action-procedures)) ;change value of signal will lead to the call of every procedures added to the wire
'done))

(define (accept-action-procedure! proc)
(set! action-procedures (cons proc action-procedures))
(proc))

(define (dispatch m)
(cond ((eq? m 'get-signal) signal-value)
((eq? m 'set-signal!) set-my-signal!)
((eq? m 'add-action!) accept-action-procedure!)
(else (error "Unknown operation -- WIRE" m))))
dispatch))

set-my-signal!会先检查当前的信号值是否需要被改变,如果需要才会重新设置signal-value并调用所有被绑定到导线上的无参过程。调用整个action-procedures用到的过程call-each定义如下:

1
2
3
4
5
6
(define (call-each procedures)
(if (null? procedures)
'done
(begin
((car procedures))
(call-each (cdr procedures)))))

这个函数与scheme原语for-each以及common-lisp原语mapc的行为有部分相似之处,也可以这样定义为

1
2
(define (call-each procedures)
(for-each (lambda (proc) (proc)) procedures))

另外需要特别注意的是,我们看到accept-action-procedure!每次在执行添加proc命令后,立刻又调用了一次新添加的过程(proc),如果不进行这个操作而只是简单的写成

1
2
3
(define (accept-action-procedure! proc)
(set! action-procedures
(cons proc action-procedures)))

而不调用一下刚被添加的过程proc,那么proc永远不会被执行,the-agenda也永远不会不会被添加任何action,所有导线上的信号都始终为0,这个模拟毫无意义。

为了使对于wire的操作更加顺应用户的使用习惯,还需要再规定一些语法糖把返回dispatch函数进行一番包装得到我们上文提出最终需要实现的三个函数:

1
2
3
4
5
6
7
8
(define (get-signal wire)
(wire 'get-signal))

(define (set-signal! wire new-value)
((wire 'set-signal!) new-value))

(define (add-action! wire action-procedure)
((wire 'add-action!) action-procedure))

这种风格的函数原型会更加符合大多数程序设计者,尤其是经常接触面向对象编程者的思维习惯:比如当我们使用(wire 'get-signal)时会把wire想象成一个把'get-signal指令作为参数被调用的过程,而(get-signal wire)会让人更倾向于把wire当成一个数据对象,被当成输出传入到get-signal过程。当然如上文所言,这只是一个语法糖,两个过程实质没什么区别。如果在一种程序设计语言中过程可以被当成数据对象被处理,即函数式编程的一大特征:函数/过程也是一等公民,那么你完全可以根据自己的习惯,自由的选择编程风格使之更像过程或者对象。

现在再来想象一下我们需要完成的数字电路:每根导线上的信号会随着时间变化,会被添加进电路并,会不断的被连接到新设备。导线毫无疑问是可变的数据对象,我们用局部状态变量(signal-valueaction-procedures)的赋值来模拟这种行为,每当有新的导线被创建,就会有一组新的局部状态变量被分配,通过导线构造时返回的接口过程dispatch可以对该导线进行操作,用来这些新的局部状态变量来捕获电路环境的变化。

一根导线可以同时被连接到不同的设备,多根导线也可以被连接到同一个设备。因此,一个设备交互而引发的某根导线上的信号变化,可能会引发设备上连接的其他导线上的信号变化,进而引起更多的导线信号变化。在连接建立完成后,导线通过调用action-procedure向邻接的导线通信,告知信号的变化。

Probe

为了观察模拟运行的全过程,我们需要一些辅助工具来显示导线上数字信号值的变化。为了达到这个目的,需要在导线上放置一个“探针”probe,可以把它想象成一个外接的电位表,每当示数发生变化时立刻发起一个通知,并显示此刻的新信号值,当前时间以及它自己的ID(为了区分这是放置在哪根导线上的probe),相当于一个监视器的角色2

1
2
3
4
5
6
7
8
9
10
(define (probe name wire)
(add-action! wire
(lambda ()
(newline)
(display name)
(display " ")
(display (current-time the-agenda))
(display " New-value = ")
(display (get-signal wire))
(newline))))

这个过程是给wire安排一个名为nameprobe,其中的lambda表达式引导的可以看成一个格式化输出打印过程,通过add-action!被绑定到了wire上,wire的信号发生改变时会被调用以打印这个信号变化。这个打印过程也是我们到此为止第一次接触到的,前文所说的,可以被添加的action-procedures的特殊的无参过程。

probe的使用场合为:模拟开始前,每次创建新的导线时,再新导线上绑定一个探针(通常与导线同名),用以观察信号的变化。当然,承载原始输入信号的导线没有太大必要被监视,但为了获取完整的模拟结果,也可以对它们放置探针。

Function box

功能部件的表现如它的名字function,将一些信号作为输入,并输出一些信号。不过有一点不同于数学中定义的函数概念:从接受输入到给出会存在一定的延迟,这倒是更像我们在编程中用到的函数实现,毕竟函数计算存在延迟,实质上也是因为电路信号的处理存在延迟。

因此不妨把这些部件和我们之前接触到的函数一样抽象成一个黑盒,我们不知道它是如何实现的,但是知道该怎么用,比如我们接下来要实现的and运算器在现实中就被做成一个74LS08芯片,虽然对芯片内部一无所知,但这并不妨碍我们根据手册知道哪几个针脚接输入,哪几个针脚接输出,然后直接使用。

但我们的模拟不满足于仅仅根据文档调用模拟function box的function,而是设计实现这些function,如同编程一样,从primitives开始进行实现,再用这些primitive function box去完成更复杂的box的定义。

Primitive function box

模拟器内所有的功能部件都可以基于这三种基本的部件实现:

  1. (inverter):对一个输入信号取非,在延迟时间后返回
  2. 与门(and-gate): 对两个输入信号进行逻辑与运算,当且仅当两个输入都为1时,在延迟时间后返回1,否则为0
  3. 或门(or-gate): 对两个输入信号进行逻辑或运算,当且仅当两个输入都为0时,在延迟时间后返回0,否则为1

三种基本元件的符号表示

我们可以先试着实现一个inverter。逻辑非运算(logical-not s)的定义不难编写,需要考虑的是inputoutput怎样体现这种通过inverter绑定的关联,即每当input导线上的信号值发生改变时,output也需要随之被改变,这也就是add-action!过程的用武之地了:在input导线上添加一个改变outputinput的非值的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (inverter input output)
(define (invert-input)
(let ((new-value (logical-not (get-signal input))))
(after-delay inverter-delay
(lambda ()
(set-signal! output new-value))))) ;output signal changes after one inverter-delay
(add-action! input invert-input)
'ok)

(define (logical-not s)
(cond ((= s 0) 1)
((= s 1) 0)
(else (error "Invalid signal" s))))

被添加到input的实际上是一个after-delay过程,inverter-delay是个根据不同环境由用户自己定义的inverter电路的延迟数值,lambda表达式定义的命令,即设置output为新的结果通过after-delay被添加到the-agenda

and-gate的实现稍微复杂一些,两个输入的信号值都会影响输出信号。同样这里规定and-gate本身的延迟为某个常数and-gate-delay

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (and-gate a1 a2 output)
(define (and-action-procedure)
(let ((new-value
(logical-and (get-signal a1) (get-signal a2))))
(after-delay
and-gate-delay
(lambda () (set-signal! output new-value)))))
(add-action! a1 and-action-procedure)
(add-action! a2 and-action-procedure)
'ok)

(define (logical-and s1 s2)
(cond ((and (= s1 1) (= s2 1)) 1)
((or (= s1 0) (= s2 0)) 0)
(else (error "Invalid signal" s1 s2))))

类似地,可以定义or-gate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (or-gate a1 a2 output)
(define (or-action-procedure)
(let ((new-value
(logical-or (get-signal a1) (get-signal a2))))
(after-delay
or-gate-delay
(lambda () (set-signal! output new-value)))))
(add-action! a1 or-action-procedure)
(add-action! a2 or-action-procedure)
'ok)

(define (logical-or s1 s2)
(cond ((and (= s1 0) (= s2 0)) 0)
((or (= s1 1) (= s2 1)) 1)
(else (error "Invalid signal" s1 s2))))


众所周知,根据De Morgan定律$$A+B= \overline{\bar A \cdot \bar B}$$or-get也同样可以利用已经定义好的inverterand-gate进行构造,这同时也是习题3.29要求完成的内容

1
2
3
4
5
6
7
8
(define (or-gate a1 a2 output)
(let ((a1-inv (make-wire))
(a2-inv (make-wire))
(temp (make-wire)))
(inverter a1 a1-inv)
(inverter a2 a2-inv)
(and-gate a1-inv a2-inv temp)
(inverter temp output)))

在这里,我们第一次利用两种primitives构造出一个“更复杂”的box,遵循如上定义的or-gate具有2inverter-delay+and-delay的延迟。接下来,我们还会用类似于组合出or-gate的思路,去构造一些更复杂的功能部件。

Half-adder

一位半加器电路

如图所示,半加器(half-adder)由一个or-gate,两个and-gate和一个inverter组成,它的功能是接受两个1位的数字信号$A$和$B$,产生两个输出$S$和$C$,$S$表示和(sum),$C$表示进位(carry),需要满足如下的逻辑关系:
$$ \begin{align}
S &=A \cdot \bar B + \bar A \cdot B \\
C &= A \cdot B
\end{align}$$直接按照图中电路搭建也是可行方案之一,这里的a,b,s,c均为图上相应符号位置的wire对象

1
2
3
4
5
6
7
(define (half-adder a b s c) ;input: a,b output:s,c
(let ((d (make-wire)) (e (make-wire)))
(or-gate a b d) ;d=a+b
(and-gate a b c) ;c=ab
(inverter c e) ;e=c'=(ab)'=a'+b'
(and-gate d e s) ;s=ed=(a+b)(a'+b')=ab'+a'b
'ok))

计算整个电路的延迟只需按照寻找关键路径的方法3找到使延迟最大的路径,拓扑排序后$C \to E \to S$,只要考虑得到$S$的路径:

  • $A,B \to C$: and-gate-delay
  • $A,B \to D$: or-gate-delay
  • $A,B (\to C) \to E$: and-gate-delay+inverter-gate-delay
  • $A,B (\to D)/(\to E) \to S$: max(and-gate-delay+inverter-gate-delay,or-gate-delay)+and-gate-delay


总延迟half-adder-delaymax(and-gate-delay+inverter-gate-delay,or-gate-delay)+and-gate-delay

Full-adder

前面我们把半加器封装成了类似于电路元件的half-adder,以便直接利用half-adder组装其他电路,比如接下来将介绍的一位全加器(full-adder)
一位全加器电路
就是由两个half-adder和一个or-gate组成的,是加法运算电路的基本原件。相比half-adder,增加一个输入位$C_{\text{in}}$表示上一位的进位,$A$和$B$依然表示此位的两个输入位,得到输出:和$SUM$与下一位的进位$C_{\text{out}}$,需要满足关系$$\begin{align}
SUM &=A \cdot \bar B \cdot \bar C_{\text{in}} + \bar A \cdot B \cdot \bar C_{\text{in}} + \bar A \cdot \bar B \cdot C_{\text{in}} \\
C_{\text{out}} & = A \cdot B + A \cdot C_{\text{in}} + B \cdot C_{\text{in}}
\end{align}$$同样我们直接按照图中的电路搭建full-adder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (full-adder a b c-in sum c-out)
(let ((s (make-wire))
(c1 (make-wire))
(c2 (make-wire)))
(half-adder b c-in s c1); s=b(c-in)'+b'(c-in) c1=b(c_in)
(half-adder a s sum c2)
;sum=as'+a's=a(b(c-in)+b'(c-in)')+a'(b(c-in)'+b'(c-in))
;sum=ab(c-in)+ab'(c-in)'+a'b(c-in)'+a'b'(c-in)
;c2=as=ab(c-in)'+ab'(c-in)
(or-gate c1 c2 c-out)
;c-out=c1+c2=b(c_in)+ab(c-in)'+ab'(c-in)
;c-out=b(c_in)+(ab(c_in)+ab(c-in)')+(ab(c_in)+ab'(c-in))
;c-out=b(c_in)+ab+a(c_in)
'ok))

这里不再详细给出总延迟的详细分析过程,感兴趣的读者可以仿照上文的方法计算,$C_{\text{out}}$的延迟为or-gate-delay+and-gate-delay+half-adder-delay,$SUM$的延迟为2half-adder-delay,那么全加器的总延迟full-adder-delay=2half-adder-delay

Ripple-carry adder

同样,接下来我们可以用full-adder组建更加复杂的电路,比如完成n位加法运算的电路——串行进位加法器(ripple-carry adder)
串行进位加法器电路,FA表示全加器(full adder)
这是对两个n位二进制$A$和$B$进行平行加法运算的最简单的电路,n个全加器级联,将$A_1,A_2,\ldots,A_n$从高到低最为$A$的各位输入,$B_1,B_2,\ldots,B_n$从高到低最为$B$的各位输入,生成的$S_1,S_2,\ldots,S_n$组成加法运算的结果,当然还附带着进位$C$。我们设计的ripple-carry-adder的四个参数

  • a: 一个由nwire组成的list,从高到低表示被加数$A$的每一位的值
  • b: 一个由nwire组成的list,从高到低表示加数$B$的每一位的值
  • s: 一个由nwire组成的list,从高到低表示和$S$的每一位的值
  • c: wire,表示最终进位$C$的值
1
2
3
4
5
6
7
(define (ripple-carry-adder a b s c)
(let ((c-in (make-wire)))
(if (null? (cdr a)) ;if it is the last bit
(set-signal! c-in 0) ;c-in is set to be 0
(ripple-carry-adder (cdr a) (cdr b) (cdr s) c-in))
;otherwise,c-in should be the c-out from lower bits
(full-adder (car a) (car b) c-in (car s) c)))

$C_{k}$的延迟只来自于$C_{k+1}$的输入延迟和半加器的继位运算结果,信号传播到达$C_{k}$的延迟Ck-delay可以写为Ck+1-delay+or-gate-delay+and-gate-delay+half-adder-delayCn-delay为0,累加得到到$C$(即$C_0$)的延迟为n*(or-gate-delay+and-gate-delay+half-adder-delay)

而每个$S_{k}$的延迟也只取决于$C_{k+1}$的输入延迟和半加器的和运算结果,信号传播到$S\_{k}$的延迟Sk-delay可以写为Ck+1-delay+full-adder-delay,最后传播到达$S_1$的延迟为(n-1)*(or-gate-delay+and-gate-delay+half-adder-delay)+full-adder-delay

我们在分析全加器总延迟时已经得到full-adder-delay大于or-gate-delay+and-gate-delay+half-adder-delay的结论,那么这里也可以得出这样的结论:串行进位加法器的总延迟为(n-1)*(or-gate-delay+and-gate-delay+half-adder-delay)+full-adder-delay

习题中也要求过用三种基本元件的延迟来表示这个电路的总延迟,按照上面的分析可以直观的写为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define half-adder-delay
(+ (max (+ and-gate-delay inverter-delay)
or-gate-delay)
and-gate-delay))

(define full-adder-delay
(* 2 half-adder-delay))

(define (ripple-carry-c n)
(define (ripple-carry-c-iter k)
(if (= k n)
0
(+ or-gate-delay
and-gate-delay
half-adder-delay
(ripple-carry-c-iter (+ k 1)))))
(ripple-carry-c-iter 0))

(define (ripple-carry-s n)
(+ (ripple-carry-c (- n 1) full-adder-delay)))

(define (ripple-carry-adder-delay n)
(ripple-carry-s n))

A sample simulation

通过前面的工作,我们已经搭建好了一个数字电路模拟的环境。接下来可以像我们在现实中的实验环境一样,自由的取用导线和元件搭建电路,改变输入,观测输出。我也已经把以上代码连同需要用到的更底层的queue定义打包写到了digital-circuits-package.scm,你可以使用一些可视化的在线scheme REPL工具如Scheme Interpreter and VisualizerEditor,通过命令

1
(download '8a63a3005ae7814ece306e6dc12480f7)

直接下载安装上文搭建的环境。在这个环境中,你可以通过make-wire增加导线,用probe进行监视,直接调用inverter,and-gate,or-gatehalf-adderfull-adder连接出新的电路,用set-signal!改变输入信号值。除此之外,它们本来就是非常优秀的可视化工具,你还可以在一步步搭建电路的同时用

1
2
3
(draw-pair the-agenda)
(visualize (half-adder a b s c))
(diagram)

等命令去观察这个管理模拟进程的agenda本质上是一个什么样的数据结构,半加器电路的连接一步步会进行哪些操作,整个执行环境的变量又是如何被绑定的……更多用法还请根据需求自行开发。

当然,在国内有时可能会因为一些众所周知的原因无法使用上述工具,不过没关系,一步步跟着上面的解释慢慢写就可以了。接下来直接用原书上给出的一个简单的例子来结束本文,至此终于有始有终的带着大家看到我们辛辛苦苦写的模型第一次得到了应用。

首先根据你的需求设置三种基本元件的延迟时间,并初始化the-agenda

1
2
3
4
(define inverter-delay 2)
(define and-gate-delay 3)
(define or-gate-delay 5)
(define the-agenda (make-agenda))

我们准备模拟一个简单的半加器的行为,于是先新建四根导线

1
2
3
4
(define input-1 (make-wire))
(define input-2 (make-wire))
(define sum (make-wire))
(define carry (make-wire))

为了观察输出,在两个输出位安置probe并随即打印示数

1
2
3
4
5
(probe 'sum sum)
;sum 0 New-value = 0

(probe 'carry carry)
;carry 0 New-value = 0

把它们通过半加器连接

1
2
(half-adder input-1 input-2 sum carry)
;ok

此时改变输入信号input-1的值为1,在一个half-adder-delay后不出所望,sum探针通知sum的值已经改变为1了

1
2
3
4
5
(set-signal! input-1 1)
;done
(propagate)
;sum 8 New-value = 1
;done

注意当前模拟时间为第8个单元,现在再改变输入信号input-2的值为1,可以看到在一个or-gate-delaycarry位发生了改变了,从输入改变开始一个half-adder-delaysum位输出也发生了改变:

1
2
3
4
5
6
7
(set-signal! input-2 1)
; done

(propagate)
; carry 11 New-value = 1
; sum 16 New-value = 0
; done

Summary

至此,整个章节的内容可以说是全部覆盖了。在这篇文章中,我们定义了一个特殊的一维表agenda来管理整个模拟的进程,用封装了本地状态的wire模拟了信号载体导线的行为,根据逻辑实现了各种功能元件的连接模拟。

对于实际应用来说,我们至此所做的算不上什么有意义的工作,但通过一步步编写设计去思考它们的应用场景,也会开始逐渐感觉到编程是很有趣的事,用函数式编程语言去完成之前用面向对象编程语言实现的任务尤甚。

希望我的这篇文章能帮助正在困惑的你跨过可变数据建模理解上的障碍,带领正在无聊的你发现一个更有意思的世界。

祝你早日找到住在计算机中的神灵

也祝我。


  1. 1.虽然MIT已经提供了html形式的全文开源,但为了获取更好的阅读体验,推荐下载这个排版精美的非官方电子版在线交互版
  2. 2.SICP全书倾向于在display函数的第一个指令放置(newline)但经常忽略在打印完成后使用(newline)给其他命令空间,我们可以看到前面的‘done’之前都没有用(newline)刷新,如果用原始版本的probe定义,可能会造成显示混乱,为此我在最后一行添加了一个(newline)使输出更符合读者的观感。
  3. 3.https://en.wikipedia.org/wiki/Critical_path_method