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

沈云付，张凯凯，蒋本朋

（上海大学计算机工程与科学学院，上海 200444）

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

沈云付，张凯凯，蒋本朋

（上海大学计算机工程与科学学院，上海 200444）

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

三值光学计算机；MSD；加法器；数据剪辑；累加器

加法器是计算机系统中最基本的器件之一.虽然科学家们在不断地改进加法的效率，但是由于进位的存在，加法的效率并没有明显的提高.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型加法的数据剪辑技术进行研究.

1 M+B型加法及其相关变换简介

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

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

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

表1 具有特殊输入的MSD加法C变换、P变换和R变换Table 1 C,P,R transform table of one-bit MSD adder with restricted input form

记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）.

图1 M+B型加法逻辑结构图Fig.1 Logic structure of addition of M and B

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数转换成二进制数即可计算出它们的和.

2 M+B型加法的数据剪辑技术

三值光学计算机有两个非常显著的特点：数据位数众多和按位可重构.三值光学处理器的位数可以增加到成千上万位，非常适用于数据位数众多的计算.对于连加运算，可以为特定的用户通过重构技术将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 数据拼接

式中，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前部的再拼接即可得到结果，同样在对短数据进行数据拼接时二者间只需增加一位.

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

3 模拟实验

软件模拟实验的目的是为了验证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变换时进行.

此时，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）的数据策略.

图2 数据截断示意图Fig.2 Truncation procession of data segments

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

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

图3 数据拼接示意图Fig.3 Data concatenation process

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

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

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

表2 实验用例Table 2 Experimental instances

根据上述拼接和截断策略，7组数据分6次进行运算，其中第3、4、5组合并成一组，而第6组分为两组，各有15和3位，数据分组信息如表3所示.但是并没有对第6组分出的3位新组数据与第7组数据进行拼接.

表3 数据分组信息Table 3 Information of grouped data

6次运算的过程如表4所示.

表4 6次数据计算过程Table 4 Calculation process of 6 groups

第1组数据M=10u10u01和B=10101011，经过C、P、R变换后，得到

当第1组数据000000010011011和第2组数据0000000000uuuu0分别为经过C、P变换后的结果，最后16位数据000000010010u000为M和B的和，用十进制表示为280.

第3次计算过程含有3、4、5个数的并行计算：1010+1110=11000，1u0+001=1u0u，u10+100=01u0，结果为00001u01u0u11000，正确.

第4次和第5次计算的和分别是s1=1u11u0u10101000u和A=0000000000000010，是原来第6组数据根据截断策略所得到的.为此应去除A的低5位，记为s2=00010.根据截断策略，将s1剪掉最低位，将s2剪掉最高位，得到一个19位数据1u11u0u101010000010，表示为1u11u101u101u0u011+011000011101100111=1u11u0u101010000010，即（111387）10+（100199）10=（211586）10，结果正确.

4 结束语

MSD数M和二进制数B的M+B型加法结果可以通过C、P、R 3个变换和并行的2个步骤得到.M+B1+…+Bk形式的链接也不需要额外的数据变换.通过数据剪辑技术可以大大提高加法器的效率和利用率.本软件模拟实验也证明了数据剪辑策略的正确性和可实现性.

［1］LING H.High-speed binary adder［J］.IBM Journal of Research and Development,1981,25（3）：156-166.

［2］AVIZIENIS A.Signed digit number representation for fast parallel arithmetic［J］.IRE Transactions on Electronic Computers EC,1961,10（3）：389-400.

［3］BOCKER R P，DRAKE B L，LASHER M E,et al.Modified signed-digit addition and subtraction using optical symbolic substitution［J］.Applied Optics,1986,25（15）：2456-2457.

［4］金翊,沈云付,彭俊杰,等.三值光学计算机中MSD加法器的理论和结构［J］.中国科学（信息科学）, 2011,41（5）：541-551.

［5］HUANG H X，ITOH M，YATAGAI T.Modified signed-digit arithmetic based on redundant bit representation［J］.Applied Optics,1994,33（26）：6146-6156.

［6］HUANG H X，ITOH M，YATAGAI T.Classified one-step modified signed-digit arithmetic and its optical implementation［J］.Optical Engineering,1996,35（4）：1134-1140.

［7］ALAM M S.Parallel optical computing using recoded trinary signed-digit numbers［J］.Applied Optics,1994,33（20）：4392-4397.

［8］CHERRI A K.Symmetrically recoded modified signed-digit optical addition and subtraction［J］. Applied Optics,1994,33（20）：4378-4382.

［9］CHERRI A K，ALAM M S.Recoded and nonrecodedtrinary signed-digit adders and multipliers with redundant-bit representations［J］.Applied Optics,1998,37（20）：4405-4418.

［10］CHERRI A K，KAMAL H A.Efficient optical negabinary modified signed-digit arithmetic：onestep addition and subtraction algorithms［J］.Optical Engineering,2004,43（2）：420-425.

［11］LI G Q，QIAN F，RUAN H,et al.Compact parallel optical modified-signed-digit arithmetic-logic array processor with electron-trapping device［J］.Applied Optics,1999,38（23）：5039-5045.

［12］QIAN F，LI G Q，RUAN H,et al.Two-step digit-set-restricted modified signed-digit additionsubtraction algorithmetic and its optoelectornic implementation［J］.Applied Optics,1999, 38（26）：5621-5630.

［13］ZHANG S Q，KARIM M K.One-step optical negabinary and modified signed-digit adder［J］. Optics&Laser Technology,1998,30（3/4）：193-198.

［14］SALIM W Y，FYATH R A，ALI S A,et al.One-step trinary signed-digit arithmetic using an efficient encoding scheme［C］//Proc SPIE,Photonic Devices and Algorithms for ComputingⅡ. 2000：201-208.

［15］金翊,何华灿,吕养天.三值光计算机的基本原理［J］.中国科学E辑（技术科学）,2003（2）：111-115.

［16］严军勇,金翊,左开中.无进（借）位运算器的降值设计理论及其在三值光计算机中的应用［J］.中国科学E辑（信息科学）,2008（12）：2112-2122.

［17］金翊,王宏健,欧阳山,等.可重构三值光学处理器的原理、基本结构和实现［J］.中国科学E辑（信息科学）,2012,42（6）：778-788.

［18］PENG J J，SHEN R，JIN Y,et al.Design and implementation of modified signed-digit adder［J］. IEEE Transactions on Cormputes,2014,63（5）：1134-1143.

［19］沈云付,潘磊,金翊,等.三值光学计算机一种限制输入一步式MSD加法器［J］.中国科学E辑（信息科学）,2012,42（7）：869-881.

［20］SHEN Y F，PAN L.Principle of a one-step MSD adder for a ternary optical computer［J］.Science China（Information Sciences）,2014（1）：86-95.

［21］CHATTOPADHYAY T，BHOWMIK P，ROY J N.Polarization encoded all-optical n-valued inverter［J］.J Opt Soc Am B,2012,29：2852-2860.

［22］GHOSH A K，BASURAY A.Trinary flip-flops using Savart plate and spatial light modulator for optical computation in multivalued logic［J］.Optoelectronics Letters,2008,6：443-446.

［23］GHOSH A K，BASURAY A.Binary to modified trinary number system conversion and vice-versa for optical supercomputing［J］.Nat Comput,2010,9：917-934.

［24］SHEN Y F，JIANG B P，JIN Y,et al.Principle and design of ternary optical accumulator implementing M-k-B addition［J］.Optical Engineering,2014,DOI：10.1117/1.OE.53.9.095108.

Data editing techniques of ternary optical adder implementing M+B

SHEN Yunfu，ZHANG Kaikai，JIANG Benpeng
（School of Computer Engineering and Science，Shanghai University，Shanghai 200444，China）

Due to carry propagation,efficiency of addition for data with large number of bits has not been significantly improved in the existing computers.Optical approaches have advantages in parallel and carry free addition with a large number of data bits.Based on the computing principle of M+B and the three ternary transforms of C,P and R as proposed in previous works,this paper studies related data editing techniques in which M is an MSD number,B is binary number.A data editing technique for this type of addition is proposed.Simulation is carried out on the three ternary transforms C,P and R for addition,data truncation and data concatenation.The results validate correctness of the proposed data editing technique.

ternary optical computer；MSD；adder；data editing；accumulation

TP 31

A

1007-2861（2016）04-0440-09

10.3969/j.issn.1007-2861.2015.01.001

2014-12-31

国家自然科学基金资助项目（61103054）；上海市教委创新基金资助项目（13YZ005）

沈云付（1960—），男，副教授，博士，研究方向为软硬件形式化方法、模型检查、三值光学计算机可靠性等. E-mail：yfshen@mail.shu.edu.cn