M+B型三值光學加法器的數(shù)據(jù)剪輯技術(shù)

沈云付，張凱凱，蔣本朋

（上海大學計算機工程與科學學院，上海 200444）

M+B型三值光學加法器的數(shù)據(jù)剪輯技術(shù)

沈云付，張凱凱，蔣本朋

（上海大學計算機工程與科學學院，上海 200444）

在電子計算機中,由于進位的存在使得多位數(shù)的加法效率并沒有顯著地提升,而光學方法則顯示了其并行性和無進位的優(yōu)勢.在M+B型加法的運算法則和C、P、R 3個三值變換工作的基礎(chǔ)上,對相關(guān)的數(shù)據(jù)剪輯技術(shù)進行了研究（M表示MSD數(shù),B表示二進制數(shù)）.提出了M+B型加法的數(shù)據(jù)剪輯技術(shù)策略,并用軟件模擬了3個三值變換以及數(shù)據(jù)的截斷和拼接,驗證了該方法的正確性和可實現(xiàn)性.

三值光學計算機；MSD；加法器；數(shù)據(jù)剪輯；累加器

加法器是計算機系統(tǒng)中最基本的器件之一.雖然科學家們在不斷地改進加法的效率，但是由于進位的存在，加法的效率并沒有明顯的提高.20世紀60年代以來，人們對加法器的實現(xiàn)算法和電路結(jié)構(gòu)進行了大量的研究，并取得了一定成果，如串行進位加法器、超前進位加法器、并行前綴加法器等［1］.但是對于多位數(shù)的加法來說，效率和復雜性是設(shè)計硬件時所必須考慮的2個關(guān)鍵點.因此科學家們尋找其他解決途徑的腳步一直沒有停止，基于光學的并行計算便是一種極具前景的技術(shù).

20世紀60年代，Avizienis［2］首次提出冗余表示計數(shù)法，該方法為解決加法進位問題和快速提高加法效率提供了很好的方案.同時，光的無光、水平偏振和垂直偏振3種狀態(tài)與冗余計數(shù)法的3個符號0、1、建立起對應關(guān)系，使光學中的三態(tài)光信息找到了一種理想的表示形式.早在1986年，Bocker等［3］就將MSD加法運算引入了光學領(lǐng)域.MSD數(shù)加法運算的結(jié)果可通過4個邏輯變換（T（T2）,W,T0,W0）和并行的3個步驟得到.在眾多無進位加法算法中，根據(jù)計算步驟可分為三步式、兩步式和一步式等［5-14］.這些算法均基于MSD冗余表示法、對稱MSD計數(shù)法、負二進制或者三元符號表示法等，而且實現(xiàn)方法差別很大.當然，這些算法均有其優(yōu)缺點，并且在數(shù)據(jù)編解碼、系統(tǒng)控制和光學實現(xiàn)等實際應用上還存在著諸多問題.

自2000年以來，金翊等［15-17］提出了三值光學計算機原理和結(jié)構(gòu)、降值設(shè)計理論以及三值光學處理器重構(gòu)原理等，奠定了面向應用的三值光學計算機系統(tǒng)設(shè)計的基礎(chǔ).2009年Bocker等［3］提出了MSD加法器原理和相關(guān)的數(shù)據(jù)剪輯技術(shù)，該三步式MSD加法器的數(shù)據(jù)剪輯在加法過程的截斷與拼接中需要增加兩位數(shù).彭俊杰等［18］從應用角度出發(fā)，提出了MSD光學加法器的一種結(jié)構(gòu)和實現(xiàn)方法.沈云付等［19-20］提出了限制輸入的一步式MSD加法器，并實驗證明了其可行性.這種加法器的輸入限制為只包含0、1的MSD數(shù)，但它的結(jié)果是MSD數(shù)，不適用于連加的情況.

現(xiàn)在已有一些將MSD等冗余表示轉(zhuǎn)為二進制表示的工作.如Chattopadhyay等［21］利用偏振光轉(zhuǎn)換器和偏振光隔離器設(shè)計了二進制、三進制和四進制邏輯系統(tǒng)轉(zhuǎn)換電路.Ghosh等［22］也提出了三值邏輯轉(zhuǎn)換為多值邏輯的方案，并用光學實現(xiàn)方法詳細描述了二進制和MSD數(shù)之間的轉(zhuǎn)換過程［23］.

文獻［24］中已經(jīng)獲得了具有連加功能的特殊的MSD數(shù)的加法M+B1+…+Bk，簡稱為M+B型加法.鑒于數(shù)據(jù)剪輯技術(shù)能夠明顯地提高加法的效率，本工作主要對M+B型加法的數(shù)據(jù)剪輯技術(shù)進行研究.

1 M+B型加法及其相關(guān)變換簡介

式中，i為整數(shù)，ai∈｛0,1,｝，任意一個MSD數(shù)（除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數(shù)，B=bnbn-1…b1為二進制數(shù).M與B的加法可通過如下2個步驟實現(xiàn).

步驟1 將M與B對應的位進行C變換，得到結(jié)果記為c，并在c后補一位0，仍記為c；同時對M和步驟1 B對應的位進行P變換，結(jié)果記為p，并在p前補一位0，仍記為p.

步驟2 將步驟1的c和p的對應位作為R變換的輸入，得到結(jié)果s.

s即為M與B的和，也可看出其位數(shù)為n+1.關(guān)于M+B結(jié)果的正確性已經(jīng)被證明［24］.

圖1為多位數(shù)進行M+B型加法的邏輯結(jié)構(gòu)圖，其中輸入M由0、1、組成，B由0、1組成.P變換用于得到本位值p，C變換用于得到進位值c，R變換則得到修正位r（或者最終結(jié)果s）.

圖1 M+B型加法邏輯結(jié)構(gòu)圖Fig.1 Logic structure of addition of M and B

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

設(shè)M0=M，i=0.

步驟1 如果i>k，則轉(zhuǎn)到步驟3；否則，將Bi+1高位補i個0，得到n+i位數(shù)，仍記為Bi+1.

步驟2 對Mi與Bi+1進行n+i位的M-1-B形式的加法，其和記為Mi+1.使i=i+1，轉(zhuǎn)到步驟1.

步驟3 結(jié)束.

最后得到M+B1+…+Bk的結(jié)果位Mk，位數(shù)為n+k.并行方式下只需要2k步即可完成.

需要注意的是B0+B1+…+Bk的結(jié)果是容易實現(xiàn)的，其結(jié)果是一個MSD數(shù).之后只需進行步驟3將MSD數(shù)轉(zhuǎn)換成二進制數(shù)即可計算出它們的和.

2 M+B型加法的數(shù)據(jù)剪輯技術(shù)

三值光學計算機有兩個非常顯著的特點：數(shù)據(jù)位數(shù)眾多和按位可重構(gòu).三值光學處理器的位數(shù)可以增加到成千上萬位，非常適用于數(shù)據(jù)位數(shù)眾多的計算.對于連加運算，可以為特定的用戶通過重構(gòu)技術(shù)將w個基本處理器重構(gòu)成專用的處理器，以用于FFT變換、Wash-Hadamader變換等.在光學處理模式下，只要運算器w足夠多，就可以較低的計算復雜性完成這些變換的計算.即使運算器位數(shù)不夠，也可以把一個大數(shù)據(jù)截斷成幾個長度略小于w的數(shù)據(jù)段來進行分步運算，最后通過合并求得結(jié)果.當用戶輸入的位數(shù)并不多時，可將這些數(shù)據(jù)拼接成一個適用于加法器的數(shù)來提高加法器的利用率.

2.1 數(shù)據(jù)截斷技術(shù)

記M和B分別為數(shù)據(jù)位數(shù)眾多的MSD數(shù)和二進制數(shù)：

利用上述規(guī)則對M與B進行求和得到s.分別對M和B進行C變換和P變換得到c和p，并分別對c、p進行補0操作后有

對結(jié)果c、p作R變換得到

現(xiàn)在嘗試把M和B從i和j位之間截斷成兩個數(shù)據(jù)段：

分別對M1與B1、M2與B2進行C變換和P變換，結(jié)果經(jīng)補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時，顯然結(jié)果是不正確的，須修正這個差異.修正方法如下.

M2和B2的取法保持不變，但對M1和B1進行有重疊的選取，即對M和B在第i位向右分別多截取1位，得M1和B1.有

分別對M1與B1、M2與B2進行C和P變換，并對結(jié)果進行R變換，依次有

只要剪掉s1尾部的丟棄s2前部的再拼接后得到的結(jié)果就是和s.

2.2 數(shù)據(jù)拼接

式中，M3、M4為MSD數(shù)，B3、B4為二進制數(shù).

一方面，分別對M3、B3與M4、B4進行C和P變換，并進行補0處理后有

再分別對c3、p3與c4、p4進行R變換后，有

另一方面，將小位數(shù)數(shù)據(jù)拼接成大位數(shù)數(shù)據(jù).在M3、M4之間增加一個0，對B3、B4作類似處理，有

對M、B分別進行C和P變換，并進行補0處理得

式中，c和p中間的1個0恰好是根據(jù)C和P變換得到的.現(xiàn)在，c中間的0正好起到給未拼接前的c3尾部補0的作用，p中部的0起到給未拼接前的p4前部補0的作用.對c、p進行R變換后，得

對比式（5）和（6）可知，只要在式（6）中從左至右剪下長度為n+1位數(shù)據(jù)，就得到s3，剩余部分就是s4.

從前面的分析與推導看，相比三步式三值光學計算機MSD加法器的數(shù)據(jù)剪輯而言，上述針對M+B型三值光學加法器的數(shù)據(jù)剪輯過程對數(shù)據(jù)的截斷與拼接僅需一位.在數(shù)據(jù)截斷時，在式（4）中只要剪掉s1尾部的丟棄s2前部的再拼接即可得到結(jié)果，同樣在對短數(shù)據(jù)進行數(shù)據(jù)拼接時二者間只需增加一位.

該加法過程中的數(shù)據(jù)剪輯工作可由三值光學計算機監(jiān)控系統(tǒng)的一個模塊完成，經(jīng)數(shù)據(jù)位分配和自動剪輯后，數(shù)據(jù)進入輸入隊列.待加法器對數(shù)據(jù)完成加法后，系統(tǒng)對計算結(jié)果進行相應的反向剪輯處理取得結(jié)果.

3 模擬實驗

軟件模擬實驗的目的是為了驗證M-1-B型加法的正確性和數(shù)據(jù)剪輯技術(shù)的有效性.模擬軟件采用C++程序編寫.

3.1 三值變換C、P、R的模擬與實現(xiàn)

基于光學處理器的M-1-B加法器模擬是通過C、P、R變換實現(xiàn)的.用3個2位數(shù)據(jù)分別表示C、P、R 3個變換，用3個函數(shù)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］，函數(shù)CC的實現(xiàn)如下：

類似地，可以定義函數(shù)PP和RR.

3.2 M-1-B加法器的模擬與實現(xiàn)

w位的M-1-B加法，需要3w+1個單元，用一個一維數(shù)組D存放各個變換的結(jié)果.D［0,1,…, w-1］，D［w,w+1,…,2w-1］，D［2w,2w+1,…,3w］分別表示C、P、R變換的結(jié)果.C和P變換結(jié)果的補0操作在R變換時進行.

此時，D［0,1,…,3n］的結(jié)果將顯示在液晶屏幕上.

3.3 M-1-B加法器數(shù)據(jù)剪輯的實現(xiàn)策略

下面模擬一個w=15位的M-1-B型加法器來實現(xiàn)數(shù)據(jù)剪輯技術(shù).將長度為46的一維數(shù)組D［0，1，…，45］分為15、15、16的3個長度來分別存放變換結(jié)果，每段結(jié)果均右對齊，保持原來的順序，位數(shù)不足時左邊補0.

分3種情況.

（1）輸入數(shù)據(jù)位數(shù)為w，這種情況下一個M-1-B型加法器便可模擬實現(xiàn).

（2）位數(shù)較大的截斷策略.

根據(jù)上述的數(shù)據(jù)截斷技術(shù)，將m和b截斷成長度合適的數(shù)據(jù)段，分步進行計算.

先處理從0到w-1位的第一段數(shù)據(jù).然后根據(jù)重復一位原則處理從w-1位到2（w-1）位的第二段數(shù)據(jù).圖2展示了第t次處理從（t-1）（w-1）到t（w-1）的數(shù)據(jù)策略.

圖2 數(shù)據(jù)截斷示意圖Fig.2 Truncation procession of data segments

（3）位數(shù)較少的拼接策略.

當用戶輸入的數(shù)據(jù)位數(shù)小于M-1-B型加法器位數(shù)時，可以將這些數(shù)據(jù)拼接成一個位數(shù)較多的數(shù)據(jù)，只要拼接后的數(shù)據(jù)位數(shù)小于M-1-B型加法器位數(shù)w，就可以繼續(xù)拼接，相鄰之間拼接時預留一位.如果已有數(shù)據(jù)的位數(shù)加上下一個將要拼接的數(shù)據(jù)位數(shù)之和大于w，就將下一個數(shù)據(jù)進行截斷.但考慮到下一個數(shù)據(jù)的完整性，若當前已有的數(shù)據(jù)位數(shù)加上預留位數(shù)與下一個數(shù)的數(shù)據(jù)位數(shù)的總和不超過w，便可將下一個數(shù)據(jù)拼接起來（見圖3）.

圖3 數(shù)據(jù)拼接示意圖Fig.3 Data concatenation process

拼接后，通過對結(jié)果s進行分離處理便可得各個數(shù)據(jù)對應的和.

3.4 M-1-B加法器數(shù)據(jù)剪輯結(jié)果與分析

使用長度分別為8、15、3、3、4、18、5的7組數(shù)組進行實驗分析（見表2），其中u表示-1.

表2 實驗用例Table 2 Experimental instances

根據(jù)上述拼接和截斷策略，7組數(shù)據(jù)分6次進行運算，其中第3、4、5組合并成一組，而第6組分為兩組，各有15和3位，數(shù)據(jù)分組信息如表3所示.但是并沒有對第6組分出的3位新組數(shù)據(jù)與第7組數(shù)據(jù)進行拼接.

表3 數(shù)據(jù)分組信息Table 3 Information of grouped data

6次運算的過程如表4所示.

表4 6次數(shù)據(jù)計算過程Table 4 Calculation process of 6 groups

第1組數(shù)據(jù)M=10u10u01和B=10101011，經(jīng)過C、P、R變換后，得到

當?shù)?組數(shù)據(jù)000000010011011和第2組數(shù)據(jù)0000000000uuuu0分別為經(jīng)過C、P變換后的結(jié)果，最后16位數(shù)據(jù)000000010010u000為M和B的和，用十進制表示為280.

第3次計算過程含有3、4、5個數(shù)的并行計算：1010+1110=11000，1u0+001=1u0u，u10+100=01u0，結(jié)果為00001u01u0u11000，正確.

第4次和第5次計算的和分別是s1=1u11u0u10101000u和A=0000000000000010，是原來第6組數(shù)據(jù)根據(jù)截斷策略所得到的.為此應去除A的低5位，記為s2=00010.根據(jù)截斷策略，將s1剪掉最低位，將s2剪掉最高位，得到一個19位數(shù)據(jù)1u11u0u101010000010，表示為1u11u101u101u0u011+011000011101100111=1u11u0u101010000010，即（111387）10+（100199）10=（211586）10，結(jié)果正確.

4 結(jié)束語

MSD數(shù)M和二進制數(shù)B的M+B型加法結(jié)果可以通過C、P、R 3個變換和并行的2個步驟得到.M+B1+…+Bk形式的鏈接也不需要額外的數(shù)據(jù)變換.通過數(shù)據(jù)剪輯技術(shù)可以大大提高加法器的效率和利用率.本軟件模擬實驗也證明了數(shù)據(jù)剪輯策略的正確性和可實現(xiàn)性.

［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加法器的理論和結(jié)構(gòu)［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，F(xiàn)YATH 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］金翊,何華燦,呂養(yǎng)天.三值光計算機的基本原理［J］.中國科學E輯（技術(shù)科學）,2003（2）：111-115.

［16］嚴軍勇,金翊,左開中.無進（借）位運算器的降值設(shè)計理論及其在三值光計算機中的應用［J］.中國科學E輯（信息科學）,2008（12）：2112-2122.

［17］金翊,王宏健,歐陽山,等.可重構(gòu)三值光學處理器的原理、基本結(jié)構(gòu)和實現(xiàn)［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）；上海市教委創(chuàng)新基金資助項目（13YZ005）

沈云付（1960—），男，副教授，博士，研究方向為軟硬件形式化方法、模型檢查、三值光學計算機可靠性等. E-mail：yfshen@mail.shu.edu.cn