计算机是如何做加法的?(4)——构建半加器的初步设想

摘要:探讨了设计十进制半加器的可能性。

目录
[隐藏]

在前面的篇章中已经讨论了如何在半加器的基础上构建全加器,那么现在是考虑如何去构建这样一个半加器(Half Adder,HA)了。

half adder

进一步分解

虽然已经少了一个输入,但输入输出还是不少,因此要考虑能否进一步的简化。

始终,分而治之是一以贯之的一个策略,如果要处理的问题比较棘手,那么就考虑如何进行功能抽象并把它们分解,这是应付复杂性的一个重要手段。

比如,输入能否分解呢?

你有两个输入,但一次只考虑一个输入的话,你既不能确定进位的结果,也不能确定加位的结果,所以你是不能分的。

通常而言都不会考虑分解输入。

那么,两个输出又能否分解呢?

我们注意到两个输出都可以表示成输入的函数:

S=f(A, B)

C=f(A, B)

完全由输入所决定,S 与 C 无关,C 也与 S 无关,它们均由 A,B 决定:

addition divided

其中,C 代表进位运算,S 代表加位运算。

据此,我们可以在内部把输入同时传递给两个部件并因此拆解两个输出,分成一个加位器和一个进位器两部分:

half adder by two component

如果用软件语言来表达,大概是这样:

public Output halfAdd(Input a, Input b) {
	Sum s = sum(a, b);
	Carry c = carry(a, b);
	return new Output(s, c);
}

public Sum sum(Input a, Input b) {
	// TODO
	return null;
}

public Carry carry(Input a, Input b) {
	// TODO
	return null;
}

尽管我们还不知道它们工作的细节,但已经可以单独拿出比如“进位器”模块来分析:

carryer

进位器

这样,问题再一次简化,只有两个输入一个输出。对于一个进位器,需要满足的约束如下:

输入–>输出

0+0 –> 0

0+1 –> 0

5+4 –> 0

5+5 –> 1

9+9 –> 1

请注意,以上的加号请不狭义地去理解,这里用“+”这个符号仅是想表达进位器它接受两个输入(参数)。

可以像之前那样引入一个符号 C 来表达进位器所代表的运算,那么”9 C 9 = 1”,“5 C 4 = 0”等。

把 C 想像成一个两个参数的函数,那么 C(9, 9)=1;其实加法也可以写”+(9, 9)=18”,只是我们可能觉得不习惯。

想要更好的可读性,那么可写成 Carry(9, 9)=1。总之,这些不过是表达形式上的差异。

显然,输出不是 0,就是 1,不可能超过 1。

但输入的情况则太多了,暂时来讲,我们还是从十进制上来考虑的。如何把众多的输入情况映射到这两种输出中去呢?这的确是个挑战。

首先,我们能否像之前在全加器里那样用继电器来设计这里的进位器呢?

那么,很遗憾,如果我们还是十进制的形式,那么我们有十种状态要表示,在之前,之所以能巧妙地引入继电器,是因为在那种特殊的情况下,输入和输出都只有两种状态。

如果你想知道一根导线有电还是没电,你也许只要有一枝简单的电笔就行了;如果你想知道电压的具体值,你则需要一个复杂的电压表!

当然,这不是说打造一个十进制的加法器就是完全不可能的事。

个人来说,我不太喜欢教科书上那种,一来就说加法器你要用二进制来做,然后直接就把结果展现给你,完全没有思考的空间!

我们可以从比如电压表上得到一些启发,设想一下如下的原型:

carryer rotator

关于蓝色的框,姑且叫它“旋转器”吧,我们还是再次发挥 wishful thinking(按愿望思维)的光荣传统。

比起继电器中上下跳动的开关,这是一种更加高级的开关形式了。它能根据两个输入电压的和值进行旋转,就像电压表测量电压那样,指针就是一个旋转的开关。

初步估计还是很复杂的,可能要一些轴承呀,弹簧呀,电磁铁之类的,还要考虑产生的力如何合在一起。还好我们有抽象这一手段,细节就放到后面再考虑了。

然后设想以下的一个示例:

carryer rotator example 78

如果两个电压足够,那么指针可以偏转到能连通电路的程度,就可以对外输出电压了。

当然,图上的电源 V 须设置为 1V 的电压。

如果两个电压和较小呢?那么就不足以连通,输出自然就是 0 了:

carryer rotator example 45

自然,要考虑的问题还很多,比如指针开关如何与弧形的导线形成良好接触同时又不能有太大的阻力等等。总体而言,不简单。

以上是个人的一些设想,如果大家觉得 low 也希望别见笑,各位也不妨脑洞大开想想其它的方式,自然,你需要一定的电路基础。

然后还要考虑设计“旋转器”,这玩意可就复杂了,那么我们或许还是先看看加位器吧!是否会简单一些呢?

加位器

如果是加位器,输入的种类一样,而输出则更多,可以是 0-9 任何一个值:

输入–>输出

0+0 –> 0

0+1 –> 1

5+4 –> 9

5+5 –> 0

9+9 –> 8

那么,很遗憾,它的情况或许还要复杂过进位器,而且它的输出还不是单调的变化,那么我们可能要考虑一个类似钟表一样的结构原型,比如还是以“7+8”为例:

abstract sumer example 78

同样要涉及一个“旋转器”,它还要满足能转差不多 720 度(两圈)。上图中转了一圈半。

以下为另一种输出为 5 的情况,这次转了半圈,但结果是一样的:

abstract sumer example 23

那么可以这样去考虑,在各个点上布置不同的电压输出,旋到不同点上就对外输出不同的电压:

sumer example 23

自然,你还得考虑误差出现的可能,也许应该把点换成小弧段。

当然了,以上也仅是个人一些不成熟的构想,你可能会有更好的想法!

如果你此时觉得,这是不是也太复杂了,且不说我们还差一个重要部件“旋转器”呢!那么,或许也正是这种复杂性,迫使我们去考虑其它的可能性,也即是打造二进制的电路。这样我们就不需要什么精确的旋转开关器了,一个能上下跳动的开关就能满足我们的要求。

二进制:A Great Insight

既然最终是要做二进制的加法器,那么为什么浪费时间脑洞大开去讲这些十进制的设计呢?

那么首先十进制对我们而言是更自然的方式。

事实上,历史上就很多人曾经设计了许多的十进制的机械加法器。

而意识到可以用二进制来代替,这在认识上是一个飞跃,对计算的本质也有了更加深刻的理解。

在《计算机科学哲学》(Philosophy of Computer Science)一书上,作者谈到四个计算机科学中的伟大洞见(great insight),第一条就:

All the information about any computable problem can be represented using only two nouns: 0 and 1.

所有关于可计算问题的信息都可以用 0 和 1 两个名词来表示。

作者把它称之为“Bacon’s, Leibniz’s, Morse’s, Boole’s, Ramsey’s, Turing’s, and Shannon’s Insight”

那么这些洞见来自于谁呢?它来自于培根,莱布尼茨,莫尔斯,布尔,拉姆齐,图灵,香农。

没错,是以上几头牛的头脑上才最终慢慢将这些思想孵化成熟。

而教科书中对此常常要么是轻描淡写地一笔带过,要么压根就不谈,一上来就跟你讲二进制,好像这些是多么自然的想法!好吧,二进制对我们这些通常有“十个指头”的人而言是不自然的!

我们会在后面再谈谈进制的问题,并最终用二进制的方式完成半加器的设计。

发表评论

电子邮件地址不会被公开。