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