M+B型三值光学加法器的数据剪辑技术

M+B型三值光学加法器的数据剪辑技术

沈云付;张凯凯;蒋本朋

【摘 要】在电子计算机中,由于进位的存在使得多位数的加法效率并没有显著地提升,而光学方法则显示了其并行性和无进位的优势.在M+B型加法的运算法则和C、P、R3个三值变换工作的基础上,对相关的数据剪辑技术进行了研究(M表示MSD数,B表示二进制数).提出了M+B型加法的数据剪辑技术策略,并用软件模拟了3个三值变换以及数据的截断和拼接,验证了该方法的正确性和可实现性.

【期刊名称】《上海大学学报（自然科学版）》

【年(卷),期】2016(022)004

【总页数】9页(P440-448)

【关键词】三值光学计算机;MSD;加法器;数据剪辑;累加器

【作 者】沈云付;张凯凯;蒋本朋

【作者单位】上海大学计算机工程与科学学院,上海200444;上海大学计算机工程与科学学院,上海200444;上海大学计算机工程与科学学院,上海200444

【正文语种】中 文

【中图分类】TP31

加法器是计算机系统中最基本的器件之一.虽然科学家们在不断地改进加法的效率，但是由于进位的存在，加法的效率并没有明显的提高.20世纪60年代以来，人们对加法器的实现算法和电路结构进行了大量的研究，并取得了一定成果，如串行进位加法器、超前进位加法器、并行前缀加法器等［1］.但是对于多位数的加法来说，效率和复杂性是设计硬件时所必须考虑的2个关键点.因此科学家们寻找其他解决途径的脚步一直没有停止，基于光学的并行计算便是一种极具前景的技术.

20世纪60年代，Avizienis［2］首次提出冗余表示计数法，该方法为解决加法进位问题和快速提高加法效率提供了很好的方案.同时，光的无光、水平偏振和垂直偏振3种状态与冗余计数法的3个符号0、1、建立起对应关系，使光学中的三态光信息找到了一种理想的表示形式.早在1986年，Bocker等［3］就将MSD加法运算引入了光学领域.MSD数加法运算的结果可通过4个逻辑变换（T（T2）,W,T0,W0）和并行的3个步骤得到.在众多无进位加法算法中，根据计算步骤可分为三步式、两步式和一步式等［5-14］.这些算法均基于MSD冗余表示法、对称MSD计数法、负二进制或者三元符号表示法等，而且实现方法差别很大.当然，这些算法均有其优缺点，并且在数据编解码、系统控制和光学实现等实际应用上还存在着诸多问题.

自2000年以来，金翊等［15-17］提出了三值光学计算机原理和结构、降值设计理论以及三值光学处理器重构原理等，奠定了面向应用的三值光学计算机系统设计的基础.2009年Bocker等［3］提出了MSD加法器原理和相关的数据剪辑技术，该三步式MSD加法器的数据剪辑在加法过程的截断与拼接中需要增加两位数.彭俊杰等［18］从应用角度出发，提出了MSD光学加法器的一种结构和实现方法.沈云付等［19-20］提出了限制输入的一步式MSD加法器，并实验证明了其可行性.这种加法器的输入限制为只包含0、1的MSD数，但它的结果是MSD数，不适用于连加的情况.

现在已有一些将MSD等冗余表示转为二进制表示的工作.如Chattopadhyay等［21］利用偏振光转换器和偏振光隔离器设计了二进制、三进制和四进制逻辑系统转换电路.Ghosh等［22］也提出了三值逻辑转换为多值逻辑的方案，并用光学实现方法详细描述了二进制和MSD数之间的转换过程［23］. 文献［24］中已经获得了具有连加功能的特殊的MSD数的加法M+B1+…+Bk，简称为M+B型加法.鉴于数据剪辑技术能够明显地提高加法的效率，本工作主要对M+B型加法的数据剪辑技术进行研究.

MSD数是由｛0,1,｝组成的，是一种冗余的不带符号位的二进制，其中1表示数-1.对任意实数A，其MSD表达形式为

式中，i为整数，ai∈｛0,1,｝，任意一个MSD数（除0外）都可以具有多种表达形式.

把M+B1+…+Bk型的连加成为M-k-B型加法.这部分主要介绍M+B型加法以及M-k-B型连加的一些研究成果.

表1给出了3个M+B型加法的变换：进位变换C、本位变换P和修正位变换R.

记M=mnmn-1…m1为MSD数，B=bnbn-1…b1为二进制数.M与B的加法可通过如下2个步骤实现.

步骤1 将M与B对应的位进行C变换，得到结果记为c，并在c后补一位0，仍记为c；同时对M和步骤1 B对应的位进行P变换，结果记为p，并在p前补一位0，仍记为p.

步骤2 将步骤1的c和p的对应位作为R变换的输入，得到结果s.

s即为M与B的和，也可看出其位数为n+1.关于M+B结果的正确性已经被证明［24］.

图1为多位数进行M+B型加法的逻辑结构图，其中输入M由0、1、组成，B由0、1组成.P变换用于得到本位值p，C变换用于得到进位值c，R变换则得到修正位r（或者最终结果s）.

n位M-k-B型的加法M+B1+…+Bk的计算步骤如下.

设M0=M，i=0.

步骤1 如果i>k，则转到步骤3；否则，将Bi+1高位补i个0，得到n+i位数，仍记为Bi+1.

步骤2 对Mi与Bi+1进行n+i位的M-1-B形式的加法，其和记为Mi+1.使i=i+1，转到步骤1.

步骤3 结束.

最后得到M+B1+…+Bk的结果位Mk，位数为n+k.并行方式下只需要2k步即可完成.

需要注意的是B0+B1+…+Bk的结果是容易实现的，其结果是一个MSD数.之后只需进行步骤3将MSD数转换成二进制数即可计算出它们的和.

三值光学计算机有两个非常显著的特点：数据位数众多和按位可重构.三值光学处理器的位数可以增加到成千上万位，非常适用于数据位数众多的计算.对于连加运算，可以为特定的用户通过重构技术将w个基本处理器重构成专用的处理器，以用于FFT变换、Wash-Hadamader变换等.在光学处理模式下，只要运算器w足够多，就可以较低的计算复杂性完成这些变换的计算.即使运算器位数不够，也可以把一个大数据截断成几个长度略小于w的数据段来进行分步运算，最后通过合并求得结果.当用户输入的位数并不多时，可将这些数据拼接成一个适用于加法器的数来提高加法器的利用率.

2.1 数据截断技术

记M和B分别为数据位数众多的MSD数和二进制数：

利用上述规则对M与B进行求和得到s.分别对M和B进行C变换和P变换得到c和p，并分别对c、p进行补0操作后有

对结果c、p作R变换得到

现在尝试把M和B从i和j位之间截断成两个数据段：

分别对M1与B1、M2与B2进行C变换和P变换，结果经补0处理后有

再分别对c1与p1、c2与p2进行R变换： 对比式（2）与（3）可以看到，s2中的sish…s2s1完全一致，s1中的sn+1snsn-1…sk完全一致，但s2中的与s中的sj未必相同，s1中的和s中的sj也未必相同.在把s1和s2拼接成s时，显然结果是不正确的，须修正这个差异.修正方法如下.

M2和B2的取法保持不变，但对M1和B1进行有重叠的选取，即对M和B在第i位向右分别多截取1位，得M1和B1.有

分别对M1与B1、M2与B2进行C和P变换，并对结果进行R变换，依次有

只要剪掉s1尾部的丢弃s2前部的再拼接后得到的结果就是和s.

2.2 数据拼接

当用户提供的数据有多个位数少于M-1-B型加法器位数的时，把几个小数据拼接成一个略少于M-1-B型加法器位数的大数据，则只需要对新数据进行一次运算，提高加法器数据位的利用率.设两组小数据M3、B3与M4、B4为

式中，M3、M4为MSD数，B3、B4为二进制数.

一方面，分别对M3、B3与M4、B4进行C和P变换，并进行补0处理后有

再分别对c3、p3与c4、p4进行R变换后，有

另一方面，将小位数数据拼接成大位数数据.在M3、M4之间增加一个0，对B3、B4作类似处理，有

对M、B分别进行C和P变换，并进行补0处理得

式中，c和p中间的1个0恰好是根据C和P变换得到的.现在，c中间的0正好起到给未拼接前的c3尾部补0的作用，p中部的0起到给未拼接前的p4前部补0的作用.对c、p进行R变换后，得

对比式（5）和（6）可知，只要在式（6）中从左至右剪下长度为n+1位数据，就得到s3，剩余部分就是s4.

从前面的分析与推导看，相比三步式三值光学计算机MSD加法器的数据剪辑而言，上述针对M+B型三值光学加法器的数据剪辑过程对数据的截断与拼接仅需一位.在数据截断时，在式（4）中只要剪掉s1尾部的丢弃s2前部的再拼接即可得到结果，同样在对短数据进行数据拼接时二者间只需增加一位.

该加法过程中的数据剪辑工作可由三值光学计算机监控系统的一个模块完成，经数据位分配和自动剪辑后，数据进入输入队列.待加法器对数据完成加法后，系统对计算结果进行相应的反向剪辑处理取得结果.

软件模拟实验的目的是为了验证M-1-B型加法的正确性和数据剪辑技术的有效性.模拟软件采用C++程序编写.

3.1 三值变换C、P、R的模拟与实现

基于光学处理器的M-1-B加法器模拟是通过C、P、R变换实现的.用3个2位数据分别表示C、P、R 3个变换，用3个函数CC、PP、RR分别模拟3个变换的操作过程.

C、P、R 3个变换的定义如下：

三值光信号可以用-1、0或1来表示.对于m∈｛-1,0,1｝和b∈｛0,1｝，C变换可表示为c=C［b］［m+1］，同理P和R变换分别为p=P［b］［m+1］，r=R［-p］［c］.

对于n位光学信号m［0,1,…,N-1］和b［0,1,…,N-1］，函数CC的实现如下：

类似地，可以定义函数PP和RR.

3.2 M-1-B加法器的模拟与实现

w位的M-1-B加法，需要3w+1个单元，用一个一维数组D存放各个变换的结果.D［0,1,…, w-1］，D［w,w+1,…,2w-1］，D［2w,2w+1,…,3w］分别表示C、P、R变换的结果.C和P变换结果的补0操作在R变换时进行.

M-1-B型加法包含3个变换和2个步骤.用函数来模拟加法过程，m［0,1,…,n-1］和b［0,1,…,n-1］为n位输入数，s［0,1,…,N］为n位结果，m［0］、b［0］和s［0］分别是数据m、b、s的高位.设常数MAXN=40.

此时，D［0,1,…,3n］的结果将显示在液晶屏幕上.

3.3 M-1-B加法器数据剪辑的实现策略

下面模拟一个w=15位的M-1-B型加法器来实现数据剪辑技术.将长度为46的一维数组D［0，1，…，45］分为15、15、16的3个长度来分别存放变换结果，每段结果均右对齐，保持原来的顺序，位数不足时左边补0.

分3种情况.

（1）输入数据位数为w，这种情况下一个M-1-B型加法器便可模拟实现.

（2）位数较大的截断策略.

根据上述的数据截断技术，将m和b截断成长度合适的数据段，分步进行计算.

先处理从0到w-1位的第一段数据.然后根据重复一位原则处理从w-1位到2（w-1）位的第二段数据.图2展示了第t次处理从（t-1）（w-1）到t（w-1）的数据策略.

（3）位数较少的拼接策略.

当用户输入的数据位数小于M-1-B型加法器位数时，可以将这些数据拼接成一个位数较多的数据，只要拼接后的数据位数小于M-1-B型加法器位数w，就可以继续拼接，相邻之间拼接时预留一位.如果已有数据的位数加上下一个将要拼接的数据位数之和大于w，就将下一个数据进行截断.但考虑到下一个数据的完整性，若当前已有的数据位数加上预留位数与下一个数的数据位数的总和不超过w，便可将下一个数据拼接起来（见图3）.

拼接后，通过对结果s进行分离处理便可得各个数据对应的和.

3.4 M-1-B加法器数据剪辑结果与分析

使用长度分别为8、15、3、3、4、18、5的7组数组进行实验分析（见表2），其中u表示-1.