本文将介绍封闭进位加法器及其的基本进位原理.需要用到的前置知识:

        1 · 全加器的原理

        2 · 横式抽象版超前进位加法器的原理

By RESENS

2020年6月16日

        00 · 文章结构与索引

        01 · 什么是封闭进位加法器(CarryCancelAdder)?

        02 · 直观理解封闭进位加法器的进位原理

        03 · 严格理解封闭进位加法器的进位原理

        封闭进位加法器(CCA),是指在Minecraft中,通过封闭进位链(CarryCancelChain)进位实现的二进制加法器.由于封闭进位链其本身的优秀性质,CCA在各方面表现都非常优秀:

        １· CCA能实现无延迟进位(在信号传播距离内)

        ２· CCA不必使用活塞

        ３· CCA具有优秀的体积延迟

        事实上,目前大部分优秀竖式红石二进制加法器,甚至最好的竖式红石二进制加法器,都是基于CCA原理设计的.

        读者可以根据上方的图在游戏中还原它,或者通过该链接直接获得它的schematic文件:

pan.baidu.com/s/1mVIxaJh0cDfOftgphyHYqg

提取码:t41j

        如果你是第一次了解CCA,可能会对他的原理感到困惑,因为CCA的进位原理并不是一目了然的,并且CCA的进位原理也不能用布尔代数简洁的表示.下一节我会用一种个人的办法来直观阐述CCA的进位原理,在此之前,你或许可以试着操作这个加法器完成一些加法运算.

        我们试着用一个通俗的语言去描述它.

        现在我们独立出它的进位链部分,如上图左.现在我们要尝试将他的功能对应到常规横式抽超加中所使用的活塞进位链.对图中左右的电路进行操作,你可以发现他们之间的一些相似规律,这并不是巧合:

        1 · 橙色输入激活时,能向高位提供信号

        2 · 黄色输入激活时,能阻断来自低位的进位传递

        对于活塞进位链,阻断进位传递的方法是显然的: 通过活塞阻断红石线的信号传递.但是封闭进位链并没有类似能控制红石线通断的机构,封闭进位链是通过利用比较器和红石信号衰减的特性实现进位屏蔽的.

        具体地说,在减法模式下,比较器侧面信号输入大等于后面信号输入时,比较器会输出零.所以,如果需要屏蔽信号,只需要在比较器侧面给出一个大于后面的信号就行了.所以在封闭进位链上,只需要在侧边的半砖链上给一个强度为15的信号,就能屏蔽所以来自低位的进位信号.所以可以这样直观的描述封闭进位链阻断进位传递的过程:

        1 · 由于来自下方的信号经过了更多的衰减(经过了更多的红石线),所以如果在上方的侧链上给一个强度为15的信号,下方的信号不可能在上方大过侧链的信号,因此下方的进位被截断了.

        2 · 由于半砖具有单向传导性,因此侧链的信号不会屏蔽下方的进位输出.这个步骤可以类比于,活塞进位链在输入进位信号时,需要激活活塞阻断红石线,防止进位信号向低位的进位输出流动.

        3 · 如果在当前的位置截断信号时候,当前位置上方又输入了进位输入.那么这个上方的进位输入并不会被截断,因为来自侧链的输入在这个上方进位输入的下方,信号强度不可能大于它.

        基于以上这三点,你就可以大致理解CCA的进位原理: 通过比较器侧面充能截断进位,通过信号衰减和半转的单向性保证进位截断不会误伤下方的进位输出.从这个角度来看,CCA的进位原理与活塞加法器的进位原理是一致的.进位的部分已经完成了,那么再基于此,添加两个同或门(异或也行),接好进位输入输出和进位截断,几乎跟活塞加法器完全一样的电路结构,就实现了一个封闭进位加法器.

        因为作者本人姿势水平不行,这节很烂,欢迎大家在评论区重写.

        上节通过与活塞进位链的一个对比,直观的表述了CCA的进位原理,但是这实际上是不严谨的,如果你尝试通过布尔逻辑来推导封闭进位链,会发现这是不可行的,或者说是不简洁的.至于为什么不能通过布尔逻辑来描述封闭进位链,因为他是通过比较器来输出进位输出的,并且还利用到了红石线信号随距离衰减的性质,很显然布尔逻辑不能很好的刻画这种现象.

        那么为了用一个严谨的表述来描述封闭进位链,需要观察到封闭进位链的一个本质(Nature),即: 封闭进位链是在比较器上进行一个信号比较获得进位输出的.

        这表明进位输出是定义在一个序关系上的: 如果比较器侧面输入大于等于正面输入,则输出0,否则输出1(即输出信号不为0).

        可以想像一个这样的东西,它实际上对应了半砖链: 首先提供n个输入,输入值可能是1或者0,这些输入被对应到了一条线上的诺干点,点从左到右分别命名为P_0,P_1,P_2...P_n.然后呢,在这个线段上构造出一个类似锯齿波的东西叫做L,在P_0,P_1,P_2...P_n的位置间,L是单调递减的,这里就简单明确为斜率固定为-1的递减.在P_j的位置上,如果这个点对应的输入是MAX,那么这个位置上,L的值重置为MAX,如果是0则让L在这个点也保持斜率为-1的单调递减,也就是让信号保持衰减,而不做干涉.

        这实际上就是一个半砖链的模型,如果在半砖链上某个点充能(为15),那么从这个点开始信号改变为15,然后随着距离信号单调递减.

        那么为主,侧链分别构造这样的东西,分别叫做L_a,L_b.将他们的输入位置分别对好,实际上就是CCA的模型.

        然后再在L_a(x),L_a(x),即两根线在位置x上对应的值.上设置判断函数compare(L_a(x),L_a(x)),定义是L_a(x)>L_a(x)则输出1否则为0 (即L_a作为主链).

        再看到控制L_a,L_b形状的输入组(半砖链的输入),分别称为A(n),B(n).可以发现,当A(n)=B(n)=MAX时(在mc中,MAX=15),到第n+1个输入对应点位置前,一直都是相等的,于是compare函数会输出0,如果是A=(n)=B(n),那么两L_a和_b到下一个点n+1之前的序关系由上一组点n-1决定(延续传递),如果是A,B之间一方大于另一方,那么对应L_a和L_b的序关系就从此重置为一方大于另一方.

        当然除此之外还要注意,在minecraft中,信号至多衰减到0,因此如果一直进行衰减,最终会出现一个拐角,拐角后值固定为最低值(MC中最低值为0),这可以导致进位信息的损失,而导致错误的进位输出.

        通过compare(L_a(x),L_a(x))可以将输出看成一个红黑二色染色的线(compare的输出对应到颜色),线条被划分为诺干段,每段可能是红色和或者黑色,而两根不同颜色的分界点,就是序关系发生变化的地方.比如,假定进位是从左到右的,如果某个点开始产生了进位,那么这个点周围左黑右红,红色将对应到进位输出1,如果某个点开始截断了进位,那么这个点周围左红右黑,黑色将对应到进位输出0.

        如果一直保持红色,那就说明进位在不断的传递,如果变成黑色,那么说明进位被阻断了,直到下一个进位输入前,都不会有进位输出.

        在活塞进位链上,如果让信号为0的红石线对应位黑色,信号非0的红石线对应红色,那么可以看到两者的等价.基于此可以证明等价性.

        可以发现,封闭进位链在一个连续的值范围内(实际上是离散的)的序关系上表征进位传递和进位截断,这也是无法使用布尔代数直接描述原理的原因.因为这意味着只有{1,0},可以看作约束信号强度最大为1的封闭进位链,很显然不能传递进位.

        除此之外,也可以通过状态转移的思路,暴力证明在一定的位数内(过大会因为信号衰减为0导致进位信号丢失,而发生错误)封闭进位链与行波进位链在映射功能上的等价性.