1.

Introduction

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.^1–3 Avizienis presented the redundant representation method,⁴ 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,⁵ 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,⁶ 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.⁷ Alam proposed a one-step addition for trinary signed-digit numbers.⁸ Li et al. adopted a method called mixed binary complement value to express information and implement carry-free optical adder.⁹ They used an optical negabinary algorithm to compute addition in two steps for any length.¹⁰ Zhang¹¹ implemented a one-step optical negabinary and modified signed-digit adder. Salim et al.¹² 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.¹⁵ Huang et al.¹⁶ 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,^19–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.²³ 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.²⁴ Peng et al. proposed a structure and implementing method for optical MSD adder from the view of application.²⁵ 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 ${\mathrm{B}}_0+{\mathrm{B}}_1+{\mathrm{B}}_2+\dots +{\mathrm{B}}_k$, respectively.

In this paper, we focus on a more general MSD addition in the following form:

2.

Accumulation Principle of Carry-Free Ternary M-$k$-B Addition and Three Related Transforms

In this paper, MSD representation⁵ which we talk about here is a special ternary signed-digit number of radix 2.

Let m and b be 1-bit numbers, where $m\in \{\overline{1},\mathrm{0,1}\}$, $b\in \{\mathrm{0,1}\}$ and $\overline{1}$ represents $–1$. For convenience, ī is also represented by $u$. We define three new transforms in Table 1: C transform for carry bit, P transform for primary bit, and R transform for revise bit.

Table 1

C, P, and R transform tables of M-1-B addition. (a) C transform, (b) P transform, and (c) R transform.

Now the process of M-1-B addition of n bits is described as follows:

Denote the MSD number $m_n{m}_{n-1}\dots m_1$ by M and the binary number $b_n{b}_{n-1}\dots b_1$ by B. The addition of M and B is carried out in two steps:

We have the following theorem:

We check the results $s$ and $s^{\prime }$ in computing $\mathrm{M}+\mathrm{B}$ and ${\mathrm{M}}^{\prime }+{\mathrm{B}}^{\prime }$ in applying the three transforms respectively as follows shown in Table 2.

Table 2

Comparison of the processes of two additions M+B and M′+B′.

Here, $\mathrm{X}=\mathrm{C}({\mathrm{M}}^{\prime },{\mathrm{B}}^{\prime })$, $\mathrm{Y}=\mathrm{P}({\mathrm{M}}^{\prime \prime },{\mathrm{B}}^{\prime \prime })$, $\mathrm{Z}=\mathrm{R}(\mathrm{X},\mathrm{Y})$ 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 $s$ are $w{p}_1=w\times 2+p_1$ where $w=\mathrm{R}(c_1,p_2)$. We need to show that $s=s^{\prime }\times 2+(m_1+b_1)$. That is, we need to prove that $s=\mathrm{Z}\times 2^2+w\times 2+p_1=\mathrm{Z}\times 2^2+p_2\times 2+(m_1+b_1)$. It is easy to see that we only need to prove $w\times 2+p_1=p_2\times 2+(m_1+b_1)$. Denote $m_1+b_1$ by val.

According to the above four cases, we find that the equation $w\times 2+p_1=p_2\times 2+(m_1+b_1)$ holds. Hence, $s=s^{\prime }\times 2+(m_1+b_1)$ is correct. We now apply C, P, and R transforms to ${\mathrm{M}}^{\prime }$, ${\mathrm{B}}^{\prime \prime }$ continuously in the same way as above. Then, we deal with ${\mathrm{M}}^{\prime \prime }$ and ${\mathrm{B}}^{\prime \prime }$ etc. Finally, we reach the highest bit and we have $s=(m_n+b_n)\times 2^{n-1}+(m_2+b_2)\times 2+(m_1+b_1)$. Hence, we finish the proof of the theorem.

From the above computing processes, only two steps are required to perform $n$-bit M-1-B addition using C, P, and R transforms in parallel. Now, we present the process of $n$-bit M-$k$-B addition of the form $\mathrm{M}+{\mathrm{B}}_1+{\mathrm{B}}_2+\dots +{\mathrm{B}}_k$ as follows.

Denote ${\mathrm{M}}_0=\mathrm{M}$. We first compute ${\mathrm{M}}_0+{\mathrm{B}}_1$ and denote the sum by ${\mathrm{M}}_1$. Next, we compute ${\mathrm{M}}_1+{\mathrm{B}}_2$ and denote the sum by ${\mathrm{M}}_2$, and so on. Finally, compute ${\mathrm{M}}_{k-1}+{\mathrm{B}}_k$ and denote the sum by ${\mathrm{M}}_k$. Then, the result ${\mathrm{M}}_k$ is the sum of $\mathrm{M}+{\mathrm{B}}_1+{\mathrm{B}}_2+\dots +{\mathrm{B}}_k$, which is an MSD number of length $n+k$. The whole addition is completed in $2k$ steps.

3.

Design of 1-Bit M-1-B Adder

A one-to-one relationship can be established between the MSD symbol set $\{\overline{1},\mathrm{0,1}\}$ and the three optical states in some form. In the following, the symbols 1, $\overline{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.

The photoelectric structure for transforms C, P, and R are shown in Figs. 1Fig. 2–3.

Fig. 1

Photoelectric structure of transform C.

Fig. 2

Photoelectric structure of transform P.

Fig. 3

Photoelectric structure of transform R.

In Figs. 1Fig. 2–3, $\mathrm{LD},{\mathrm{LD}}_1,{\mathrm{LD}}_2\dots$ are the photolectric converters converting the lighted singal to electric signal 1 which is used to control liquid crystals. $\mathrm{LC},{\mathrm{LC}}_1,{\mathrm{LC}}_2\dots$ are the liquid crystals. The black slim arrows stand for the control ports of the LCs. The diamonds stand for polarizing films among which $\mathrm{V},{\mathrm{V}}_1\dots$ are vertical polarizing films which are transparent to vertical polarized light and absorb horizontal polarized light, and $\mathrm{H},{\mathrm{H}}_1\dots$ 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.

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 $b$ with two subcases each.

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:

The cases discussed above show that the results agree with $\mathrm{C}$ 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 $m_{i-1}$, $m_i$ are in MSD form, $b_{i-1}$, $b_i$ are in binary form, and the result $s_i$ is an MSD number.

Fig. 4

Photoelectric structure of M-1-B adder of 1-bit.

Using $n+1$ M-1-B adders as in Fig. 4 and configuring them together properly we obtain a carry-free adder realizing $\mathrm{M}+\mathrm{B}$ of $n$ bits, which will be seen in Sec. 5.

4.

Design of M-1-B Ternary Optical Adder Based on Reconfiguration Approach

In this section, an easy way to design a photoelectric adder realizing $\mathrm{M}+\mathrm{B}$ of 1-bit is described based on reconfiguration.

Firstly, encode the input for the truth tables of C and P transforms.

The addend $b$ is a binary number and the augend $m$ 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.

Table 3

Encoding for main optical path b.

Table 4

Encoding for control optical path m.

Secondly, by reconfiguration approach, there are 18 simplest basic operation units (BOUs), and any of all $3^9=19683$ 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 $\mathrm{M}+\mathrm{B}$ 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, ${\mathrm{LD}}_1–{\mathrm{LD}}_4$ are four photoelectric convertors, ${\mathrm{LC}}_1–{\mathrm{LC}}_4$ are four LCs, ${\mathrm{V}}_1$ and ${\mathrm{V}}_2$ are vertical polarized films, and ${\mathrm{H}}_1$ and ${\mathrm{H}}_2$ are horizontal polarized films. The labels Rvh, Rhh, Rvv, and Rhv denote the generating type of polarized lights, which generate the output of $s_i$.

Fig. 5

Photoelectric implementation of 1-bit $\mathrm{M}+\mathrm{B}$ adder based on reconfiguration.

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 $m_{i-1}$ and $b_{i-1}$ 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 ${\mathrm{LD}}_3$ and ${\mathrm{LD}}_4$, respectively, whose outputs are merged into an electric signal by an OR gate, which becomes a control signal of ${\mathrm{LC}}_3$ and ${\mathrm{LC}}_4$ in R transformer. And the outputs of lower vvBOU and hvBOU in C transformer become the inputs of ${\mathrm{LC}}_1$ and ${\mathrm{LC}}_2$ in R transformer directly. Similarly, two variables $m_i$ and $b_i$ 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 ${\mathrm{LC}}_1$ and ${\mathrm{LC}}_2$ in P transformer. And the outputs of the lower vhBOU and hhBOU in P transformer are the input signals of ${\mathrm{LC}}_3$ and ${\mathrm{LC}}_4$, respectively. R transformer needs four LCs, each of which is stuck by a polarizing film.

5.

Experiment for M-2-B Optical Adder of 2-Bit

The carry-free addition realizing $n$-bit M-$k$-B can be completed in $k$ level with $2k$ steps in parallel. In level $i$, a ($n+i-1$)-bit M-1-B adder is configured. Without loss of generality, we just present a hardware experiment to verify the 2-bit addition $m_2{m}_1+b_2{b}_1+b_2^{\prime }{b}_1^{\prime }$ 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 $\mathrm{M}+{\mathrm{B}}_1$ by using three photoelectric structures in Fig. 6. The sum ${\mathrm{M}}_1$ is a three-bit MSD number $m_3^{\prime }{m}_2^{\prime }{m}_1^{\prime }$. Then, we design a 3-bit adder to implement ${\mathrm{M}}_1+{\mathrm{B}}_2$ using four photoelectric structures in Fig. 6 and produce a four-bit sum ${\mathrm{M}}_2$.

Fig. 6

Diagram of Fig. 5.

Fig. 7

Structure of M-2-B of 2 bit.

Obviously, ${\mathrm{M}}_1+{\mathrm{B}}_2$ is implemented in the same way as $\mathrm{M}+{\mathrm{B}}_1$, but the result ${\mathrm{M}}_1=\mathrm{M}+{\mathrm{B}}_1$ 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.

Fig. 8

Specification for TN stroke segment LCD.

Fig. 9

Regions and partitions in stroke segment LCD.

In practical adder realizing M-$k$-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 $1u+10+11$ as an example to illustrate the whole experiment.

First, we design a 2-bit adder to calculate $1u+10$. The addend 10 is encoded as 0100 and the augend 1u is encoded as 1001 according to Tables 3 and 4. They will be the input of BOUs.

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 $(2\mathrm{B},2\mathrm{C})=(\mathrm{0,0})$. 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 $(3\mathrm{F},3\mathrm{E})=(\mathrm{0,0})$. We have the results $(2\mathrm{F},2\mathrm{E})=(\mathrm{0,1})$, $(2\mathrm{A},2\mathrm{D})=(\mathrm{0,1})$, and $(3\mathrm{B},3\mathrm{C})=(\mathrm{0,0})$ after C transforms, which represent the output 110 after decoding. Similarly, we have the results $(3\mathrm{F},3\mathrm{E})=(\mathrm{0,0})$, $(3\mathrm{A},3\mathrm{D})=(0,u)$, and $(3\mathrm{B},3\mathrm{C})=(0,u)$ after P transforms, which represent the output 0uu.

Fig. 10

The results of C, P transforms: 11 and $uu$.

Figure 11 shows the results after applying three R transforms to 110 and $0uu$ 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, $u$) represent signals 0 and $u$, respectively. Therefore, the result of the three R transforms is $10u$, which is equal to 3. Hence, we obtain $1u+10=10u$ which is right.

Fig. 11

The result of R transform: $10u$.

Next we calculate $10u+011$.

Similarly as $1u+10$, $10u$ 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 $0uu0$ 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, $(2\mathrm{B},2\mathrm{C})=(\mathrm{0,1})$ and $(3\mathrm{B},3\mathrm{C})=(\mathrm{0,0})$. 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 $0uu0$ of the four P transforms.

Fig. 12

Results of C and P transforms: 1100, $0uu0$.

We apply R transform to 1100 and $0uu0$ four times bit by bit. The four bits of the sum $10u0$ 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 $s_4=1$. 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, $u$, 0), and (2B, 2C, 3B, and 3C) = (0, 0, 0, 0), which means $s_3=0$, $s_2=u$, and $s_1=0$. That is, the result of the sum is $10u0$. It means that $10u+011=10u0$ (that is, $3+3=6$), which is correct.

Fig. 13

Four bits of R transforms: $10u0$.

There are $9\times 4\times 4$ cases of 2-bit addition $\mathrm{M}+{\mathrm{B}}_1+{\mathrm{B}}_2$. The experiments of all 144 cases show that the result for 2-bit M-2-B addition is correct.

6.

Conclusions

In this paper, we introduce the design and implementation of the optical adder computing $\mathrm{M}+{\mathrm{B}}_1+{\mathrm{B}}_2+\dots +{\mathrm{B}}_k$. The accumulation principle of M-$k$-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 $\mathrm{M}+{\mathrm{B}}_1+{\mathrm{B}}_2$ 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 $\mathrm{M}+{\mathrm{B}}_1+{\mathrm{B}}_2+\dots +{\mathrm{B}}_k$ is to compute ${\mathrm{M}}_i+{\mathrm{B}}_{i+1}$ whose sum ${\mathrm{M}}_{i+1}$ 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 ${\mathrm{B}}_0+{\mathrm{B}}_1+{\mathrm{B}}_2+\dots +{\mathrm{B}}_k$ is solved.