Addition is a basic arithmetic operation. Mathematicians and computer scientists have long been looking for solving the problem of time delay and low efficiency caused by the carry propagation in addition. A lot of work has been done in addition algorithms and the corresponding circuit structures since 1960s. But the efficiency of these adders is still one of the most urgent problems to be coped with. Moreover, data stream application has become more and more popular, but the processing capacity is limited by ordinary technologies. Hence, some unconventional technologies based on optical approach have been studied and now optical computing is one of the most prospective technologies.12.–3 Avizienis presented the redundant representation method,4 with which there is no problem of carry propagation in addition and the efficiency is improved significantly. Bocker et al. applied the modified signed-digit representation (MSD) to optical computing,5 which is easier to be implemented in hardware and leads to the applications in optical computer. Later new achievements were continuously reported. Ghosh et al. proposed an optical model based on the modified ternary number system,6 in which logic operations are expressed by the orthogonality and projection of the polarized light. Ghosh et al. proposed an all-optical scheme of tristate logic-based flip-flop using optical nonlinear material.7 Alam proposed a one-step addition for trinary signed-digit numbers.8 Li et al. adopted a method called mixed binary complement value to express information and implement carry-free optical adder.9 They used an optical negabinary algorithm to compute addition in two steps for any length.10 Zhang11 implemented a one-step optical negabinary and modified signed-digit adder. Salim et al.12 proposed a one-step trinary signed-digit arithmetic using an efficient encoding scheme. Cherri et al. studied one-step addition/subtraction using negabinary MSD representations.13,14 Optical operation based on MSD of radix 2 was an active research field. Cherri proposed symmetrically recoded modified signed-digit two-step optical addition and subtraction.15 Huang et al.16 proposed a one-step MSD parallel addition and subtraction, in which the whole of three adjacent digits is divided into 10 groups and each group is judged. Qian et al. proposed a two-step MSD addition and subtraction algorithm based on binary logic arithmetic using electron-trapping device, and presented one-step digit-set-restricted modified signed-digit adder.17,18 Jin et al. proposed a principle of ternary optical computer (TOC), the decrease-radix design principle, and the reconfiguration principle and structure,1920.–21 which laid a solid foundation to the system design of the application-oriented TOC. Now the TOC is configured at least one optical processor. Ternary information is obtained by the conversion of three optical states (vertically polarized light, horizontal polarized light, and no-light) of liquid crystal controlled by electricity. The operation speed of the system is determined by the response time of liquid crystal. Physicists have invented a much faster way to switch a liquid crystals.22,23 Borshch et al. presented an electro-optic effect in a nematic liquid crystal with a response time of about 30 ns to both the field-on and field-off switchings.23 According to the work, the operation speed of an optical processor can achieve GHz scale.
Jin et al. proposed the principles and construction of MSD adder.24 Peng et al. proposed a structure and implementing method for optical MSD adder from the view of application.25 But the MSD adder is essentially three-step. The authors proposed a one-step ternary optical MSD adder with restricted input symbols 0, 1 and proved its feasibility by experiment.26,27 But its output is an MSD number, which means that the output cannot be used to the next addition of the same type directly. Therefore, a converter must be used to transform the MSD number into binary number for the next addition. Therefore, such adder is not suitable to the binary addition of the form , respectively.
In this paper, we focus on a more general MSD addition in the following form:2, three key C, P, and R transforms are introduced, and an algorithm of carry-free ternary addition M-1-B and the processes of M--B are presented. In Sec. 3, the optical structures of three transforms as well as M-1-B adder are designed. In Sec. 4, an optical adder realizing M-1-B is presented based on reconfiguration. In Sec. 5, an experiment for M-2-B adder is described. Finally, in Sec. 6 we summarize our work.
Accumulation Principle of Carry-Free Ternary M--B Addition and Three Related Transforms
In this paper, MSD representation5 which we talk about here is a special ternary signed-digit number of radix 2.
Let m and b be 1-bit numbers, where , and represents . For convenience, ī is also represented by . We define three new transforms in Table 1: C transform for carry bit, P transform for primary bit, and R transform for revise bit.
C, P, and R transform tables of M-1-B addition. (a) C transform, (b) P transform, and (c) R transform.
|C transform||P transform||R transform|
|u 0 1||u 0 1||0 1|
|0||0 0 1||0||u 0 u||0||0 1|
|1||0 1 1||1||0 u 0||u||u 0|
Now the process of M-1-B addition of n bits is described as follows:
Denote the MSD number by M and the binary number by B. The addition of M and B is carried out in two steps:
Step 1. Apply C transform to the input M and B bit by bit and denote the result by . Append one 0 at the end of and still denote it by . Meanwhile, apply P transform to the input M and B bit by bit and denote the result by . Add one 0 at the head of and denote it by too.
Step 2. Apply R transform to new and bit by bit, and denote the result by .
We have the following theorem:
We check the results and in computing and in applying the three transforms respectively as follows shown in Table 2.
Comparison of the processes of two additions M+B and M′+B′.
|Processes of M+B||Processes of M′+B′|
|C transform||c||Xc10||C transform||c′||X0|
|P transform||p||Yp2p1||P transform||p′||Yp2|
|R transform||s||Zwp1||R transform||s′||Zp2|
Here, , , where X, Y, and Z are the strings obtained by applying the corresponding transforms to input data bit by bit.
The lowest two bits of are where . We need to show that . That is, we need to prove that . It is easy to see that we only need to prove . Denote by val.
Case 1: , . Then, , , and . So .
Case 2: , or , . Then, , , and . So .
Case 3: , or , . Then, , , and . So .
Case 4: , . Then, , , and . So .
According to the above four cases, we find that the equation holds. Hence, is correct. We now apply C, P, and R transforms to , continuously in the same way as above. Then, we deal with and etc. Finally, we reach the highest bit and we have . Hence, we finish the proof of the theorem.
From the above computing processes, only two steps are required to perform -bit M-1-B addition using C, P, and R transforms in parallel. Now, we present the process of -bit M--B addition of the form as follows.
Denote . We first compute and denote the sum by . Next, we compute and denote the sum by , and so on. Finally, compute and denote the sum by . Then, the result is the sum of , which is an MSD number of length . The whole addition is completed in steps.
Design of 1-Bit M-1-B Adder
A one-to-one relationship can be established between the MSD symbol set and the three optical states in some form. In the following, the symbols 1, and 0 stand for the states of vertically polarized light, horizontal polarized light, and no-light (darkness or absence of light), respectively. But in the design of C, P, and R transforms, the state of each bit of M and B can be regarded not only as an input optical signal but also as an electric signal converted from a bright signal in order to control a liquid crystal. We use constant nonrotating liquid crystals.
In Figs. 1Fig. 2–3, are the photolectric converters converting the lighted singal to electric signal 1 which is used to control liquid crystals. are the liquid crystals. The black slim arrows stand for the control ports of the LCs. The diamonds stand for polarizing films among which are vertical polarizing films which are transparent to vertical polarized light and absorb horizontal polarized light, and are the horizontal polarizing films which are transparent to horizontal polarized light and absorb vertical polarized light. The short and thick black oblique lines represent holophotes or beam splitting mirrors. “Source” represents a stable light source.
The principle of C transform is described as follows according to Fig. 1. We discuss three cases according to the states of m with two subcases each.
Case 1: is . The beam penetrates horizontal polarized film H and LD converts bright signal into electric signal 1 to control and , respectively. Meanwhile, absorbs the horizontal polarized light and thus displays a no-light state.
(1) is 0. displays no-light, so the result c is a no-light state and .
(2) is 1. After penetrating , the vertical polarized light passing through is rotated 90 deg and becomes a horizontal polarized light. Then, the horizontal polarized light is absorbed by which means no light outputs. So is still a no-light state. So .
Case 2: is 0. LD outputs a low voltage, so and do not rotate polarized light and receives no light. Under this condition, displays a no-light state.
Case 3: is 1. The vertical polarized light is absorbed by H and then LD generates a low voltage. Consequently, the lights passing through and are not rotated. The light projects on after two reflections by a beam splitting mirror and a holophote. Then, it passes through , , and in sequence. Thus, displays a vertical polarized light. So .
(1) is 0. Then, displays darkness. After mergence of the two lights by a holophote and a half-reflection mirror, the result is 1.
(2) is 1. The vertical polarized light penetrates , , and successively. Now displays vertical polarized light. After mergence, the light is still vertical polarized. So the result is still 1.
The cases discussed above show that the results agree with C transform in Table 1(a).
The photoelectric structure of P transform is shown in Fig. 2. The principle of P transform is described as follows. We discuss two cases of with two subcases each.
Case 1: is 0. generates a low voltage. So does not rotate light. The light penetrating V is a vertical polarized light, which penetrates without changing its state and projects to .
(1) is 0. does not rotate light, so the vertical polarized light projecting to passes through , but it is absorbed by H. So the result is no-light. Thus, .
(2) is or 1. converts the light signal to a high voltage 1, which enables to rotate a polarized light. The vertical polarized light projecting to is rotated 90 deg and penetrates H. So the output is a horizontal polarized light. So .
Case 2: is 1. The beam is converted to a high voltage by , which enables to rotate a polarized light by 90 deg. Here, the source light penetrating V is rotated 90 deg and becomes a horizontal polarized light by and then projects to .
(1) is 0. does not rotate a polarized light. So the horizontal polarized light projecting to passes through and H. So the result is a horizontal polarized light and is .
(2) is or 1. converts the bright signal to a high voltage, which enables to rotate a polarized light. The horizontal polarized light which projects to is rotated 90 deg to a vertical polarized light by and then it is absorbed by H. So the output is no-light and is 0.
The cases discussed above show that the results agree with P transform in Table 1(b).
The photoelectric structure of R transform is showed in Fig. 3. The work procedure of R transform is described according to the four cases as follows:
Case 1: Both and are 0. and display no-light and is 0.
Case 2: is 0 and is . outputs a low voltage and outputs a high voltage. As does not rotate polarized light, the horizontal light passes through and H. So displays horizontal polarized light. As rotates polarized light and is in no-light state, the input of is no-light, which means that has no light. After mergence, is a horizontal polarized light.
Case 3: is 1 and is 0. outputs a high voltage and outputs a low voltage. rotates a polarized light by 90 deg. Now is no-light. So both and display no-light. Meanwhile, as does not rotate a polarized light, the vertical polarized light passes through and V directly. So outputs a vertical polarized light. After mergence of and , is a vertical polarized light.
Case 4: is 1 and is . Both and output high voltage 1 to control and , respectively. The horizontal light projecting on is rotated by 90 deg to a vertical polarized light which is absorbed by H. So displays no-light. Meanwhile, the light projecting on is rotated by 90 deg which is absorbed by V. So displays no-light and is a no-light state.
The cases discussed above show that the results agree with transform in Table 1(c).
By combining the above three transformers, the photoelectric structure of 1-bit M-1-B adder is shown in Fig. 4, where , are in MSD form, , are in binary form, and the result is an MSD number.
Design of M-1-B Ternary Optical Adder Based on Reconfiguration Approach
In this section, an easy way to design a photoelectric adder realizing of 1-bit is described based on reconfiguration.
Firstly, encode the input for the truth tables of C and P transforms.
The addend is a binary number and the augend is an MSD number. Their codes are shown in Tables 3 and 4. Here, the vertically polarized light, horizontal polarized light, and no-light states are denoted by V, H, and N, respectively.
Encoding for main optical path b.
|V (1)||0 1|
|N (0)||0 0|
Encoding for control optical path m.
|V (1)||1 0|
|N (0)||0 0|
Secondly, by reconfiguration approach, there are 18 simplest basic operation units (BOUs), and any of all ternary logic transforms can be realized with at most six BOUs by setting a reconfiguration code. For the principle of reconfiguration and the photoelectric structure of BOU, the reader can refer to Ref. 21. The transforms C, P, and R are ternary logic transforms. By the true value tables in Table 1, the transformers realizing the corresponding transforms can be easily designed based on reconfiguration by setting proper reconfiguration codes to BOUs. The optical structure realizing C transform needs two BOUs, that is, one vvBOU and other hvBOU. Similarly, P transformer consists of one vhBOU and other hhBOU. Here, vvBOU, vhBOU, hvBOU, and hhBOU are four kind BOUs of VV-type, VH-type, HV-type, and HH-type, respectively.
Now, a photoelectric implementation of 1-bit adder computing is shown in Fig. 5 where duplex settings of vvBOU and hvBOU in C transformer and vhBOU and hhBOU in transformer P are configured for two different functions. In Fig. 5, The dotted lines with arrow stand for the direction of current, the thick lines with arrow stand for the light transmission direction, are four photoelectric convertors, are four LCs, and are vertical polarized films, and and are horizontal polarized films. The labels Rvh, Rhh, Rvv, and Rhv denote the generating type of polarized lights, which generate the output of .
In Fig. 5, one copy of vvBOU and hvBOU in C transformer produces light signals directly as the input of the liquid crystals, and another copy produces electric signals to control the LCs in transformer R. Two variables and of the truth table of C transform are entered to two vvBOUs and two hvBOUs, which configure the transformer C. The outputs of the upper vvBOU and hvBOU are connected to photoelectric convertors and , respectively, whose outputs are merged into an electric signal by an OR gate, which becomes a control signal of and in R transformer. And the outputs of lower vvBOU and hvBOU in C transformer become the inputs of and in R transformer directly. Similarly, two variables and in the truth table of P transform are entered into two vhBOUs and two hhBOUs. Both optical signals from upper vhBOU and hhBOU in P transformer are converted into electric signals by photoelectric convertors, which are used to control and in P transformer. And the outputs of the lower vhBOU and hhBOU in P transformer are the input signals of and , respectively. R transformer needs four LCs, each of which is stuck by a polarizing film.
Experiment for M-2-B Optical Adder of 2-Bit
The carry-free addition realizing -bit M--B can be completed in level with steps in parallel. In level , a ()-bit M-1-B adder is configured. Without loss of generality, we just present a hardware experiment to verify the 2-bit addition of the form M-2-B in this section. For general case, the implementation idea is the same.
For simplicity, we draw a diagram of Fig. 5 and show it in Fig. 6. Thus, the structure of M-2-B of 2 bit is shown in Fig. 7, where Levels 1 and 2 represent 2-bit and 3-bit adders, respectively. Therefore, we design a 2-bit adder computing by using three photoelectric structures in Fig. 6. The sum is a three-bit MSD number . Then, we design a 3-bit adder to implement using four photoelectric structures in Fig. 6 and produce a four-bit sum .
Obviously, is implemented in the same way as , but the result can be sent directly to the next stage in the form of light signal.
In the experiment, two small-scale FPGAs are adopted to build reconfiguration circuit. Each FPGA controls three-layer liquid-crystal displays (LCDs) to construct two reconfigurable optical processors. Two DICE-SEM II digital simulation comprehensive boxes are used to complete the experiment. The ACEX1K PLD (Programmable Logic Device) of the one box is used to implement the reconfiguration circuit of transformers C and P. The ACEX1K PLD of the other box is used to implement the circuit of R transformer.
EDS819 TN (Twisted-Nematic) static stroke segment LCD is used and is shown in Fig. 8. Its light source is uniformly distributed and of high light intensity. It has three parts labeled 1, 2, and 3. Both parts 2 and 3 have seven stroke segments labeled A-G, respectively. In this experiment, we do not use segments 2G, 3G, and part 1. Parts 2 and 3 are divided into four regions VV, HV, HV, and HH as shown in Fig. 9. The four regions can be used some or all of segments. For example, in one LCD, the stroke segments (2F, 2E), (2A, 2D), and (2B,2C) in part 2 are selected to represent two 3-bit signals from high to low bit of three C transforms. Similarly, the stroke segments (3F, 3E), (3A, 3D), and (3B, 3C) in region VH and HH are selected to represent 3-bit signals for three P transforms. Hence, one piece LCD is enough to represent the results of three C and P transforms. But four regions of one LCD are just used to represent 3-bit signals for three R transforms.
In practical adder realizing M--B, the liquid crystals, polaroids, light source, and sensitive arrays should be integrated as a whole. But our experiment system of M-2-B adder is only to verify the correctness of the principle mentioned before. Therefore, we just use common EDS819 TN static stroke segment LCDs. Using such low-speed LCD does not affect the replacement of liquid crystal with high speed in practical system. Every polarizer matches with LCD and no couplers are used. In order to easily adjust the equipments, the components are not bonded. The lights sources we talk about here are stable. That is, they are the white plane illuminant scattering by LED, and the transmittance does not reflect the situation of the practical system.
Take as an example to illustrate the whole experiment.
In Fig. 10, the segments (2F, 2A, and 2B) in the region VV are used to represent the values of vvBOUs and the segments (2E, 2D, and 2C) in the region HV are used to represent the three values of hvBOUs in three C transforms from high bit to low bit in Level 1, but we set 2B and 2C to no light. Therefore, (2F, 2E), (2A, 2D), and (2B, 2C) represent three optical signals of C transforms in parallel where . Similarly, (3F, 3E), (3A, 3D), and (3B, 3C) in regions VH and HH are used to represent the three signals of P transforms in parallel where . We have the results , , and after C transforms, which represent the output 110 after decoding. Similarly, we have the results , , and after P transforms, which represent the output 0uu.
Figure 11 shows the results after applying three R transforms to 110 and bit by bit in parallel. The segments (2F, 2E, 3F, and 3E) show the outputs of the four BOUs (in VV, HV, VH, and HH order) for the third R transformer, which decode the result of the third bit of the sum. Similarly, the segments (2A, 2D, 3A, and 3D) are used to display the four BOUs for the second R transformer, and the same is to the segments (2B, 2C, 3B, and 3C) for the first R transformer. In Fig. 11, the stroke segment 2E in region HV and the segment 3C in region HH display lighted signals, and all other segments display no light. So (2F, 2E, 3F, and 3E) = (0, 1, 0, 0) which represents the signal 1. Similarly, (2A, 2D, 3A, and 3D) = (0, 0, 0, 0) and (2B, 2C, 3B, and 3C) = (0, 0, 0, ) represent signals 0 and , respectively. Therefore, the result of the three R transforms is , which is equal to 3. Hence, we obtain which is right.
Next we calculate .
Similarly as , and 011 enter into the 3-bit adder in level 2. Both C transform and P transform are carried out four times in parallel respectively. We obtain the results 1100 and under four C and P transforms, respectively, and are shown in Fig. 12. Here, two TN stroke segment LCDs are juxtaposed to display signals of four C and P transforms. That is, the segments (2B, 2C) of the left LCD display the results of the fourth C transform. The segments (3B, 3C) of the left LCD display the results of the fourth P transform. Here, and . Therefore, the output of the fourth C transform is 1 and the output of the fourth P transform is 0. The segments of the right LCD are used to display the results of the other three C and P transforms as before. Combining the fourth bit with the lowest three outputs of the other three C transforms we obtain 1100 as the output of the four C transforms. Similarly, we obtain the output of the four P transforms.
We apply R transform to 1100 and four times bit by bit. The four bits of the sum are shown in Fig. 13. Here, the segments (2B, 2C, 3B, and 3C) of the left LCD are used to display the fourth bit of R transform, which are (0, 1, 0, 0). It means . Parts 2 and 3 of the right LCD are used to display three bits of R transforms. Therefore, we have (2F, 2E, 3F, and 3E) = (0, 0, 0, 0), (2A, 2D, 3A, and 3D) = (0, 0, , 0), and (2B, 2C, 3B, and 3C) = (0, 0, 0, 0), which means , , and . That is, the result of the sum is . It means that (that is, ), which is correct.
There are cases of 2-bit addition . The experiments of all 144 cases show that the result for 2-bit M-2-B addition is correct.
In this paper, we introduce the design and implementation of the optical adder computing . The accumulation principle of M--B optical adder and the three related transforms C, P, and R are proposed, and the logical structure of the adder and its implementation are presented as well. 2-bit addition of the form is validated through experiment. The aim of the experiment is just to verify the principle and feasibility of the adder. As the optical components in the experiment are clung closely and there are segregate black lines between pixels, no optical crosstalk interference is found between pixels. For M-2-B adder, we only care for distinguishing the bright and the dark states, and do not consider too much the relative gray level. The key part of realizing is to compute whose sum can be directly used in the next step. By converting the result of the sum last step to binary number, the problem of parallel accumulation of the binary numbers of the form is solved.
This work was supported by Innovation Program of Shanghai Municipal Education Commission (Grant No. 13YZ005) and Natural Science Foundation of China (Grant No. 61103054). We would like to thank Mr. Liu Xuemin, Miss Shen Luyang, all PhD candidates and graduate students of our research group for their kind help and valuable discussions as well as experiments in preparing the paper.
Yunfu Shen currently works as an associate professor at the School of Computer Engineering and Science of Shanghai University. He received his PhD degree in mathematics from Beijing Normal University in 1996. His research experience includes model theory, computational complexity, formalization method of software and hardware, model checking, reliability, ternary optical computer, etc. He is a member of the China Computer Federation.
Benpeng Jiang received his master’s degree in engineering from Shanghai University in 2014. His research interests include optical computing, ternary optical computers, etc. Now he is working as a software engineer in TTPod.
Yi Jin received his PhD degree in computer science from Northwestern Polytechnic University, Xi’an City, in 2003. Currently, he is a professor and senior researcher at Shanghai University. His research interests include ternary optical computers and computer architecture. He is a senior member of the China Computer Federation.
Shan Ouyang now works as a lecturer at the School of Computer Engineering and Science of Shanghai University. He received his PhD degree in 2012 from Shanghai University. His research interests include ternary optical computers and embedded systems, especially the ternary optical computer hardware. At present, he holds a National Science Foundation of Shanghai municipality, and takes over the hardware development work of the third generation prototype of the ternary optical computer.
Junjie Peng is an associate professor with Shanghai University. He is on the editorial board of three international journals, and has served as a referee for more than 40 famous international journals and conferences. He is a senior member of the Chinese Institute of Electronics (CIE), senior member of the China Computer Federation (CCF), member of the Association for Computing Machinery (ACM), and a member of IEEE. His research interests include optical computing, cloud computing, wireless sensor network, etc.