Conditional symbolic modified signed-digit arithmetic using optical content-addressable memory logic elements

Signed-negabinary-arithmetic-based optical computing by use of a single liquid-crystal-display panel

Based on the negabinary number representation, parallel one-step arithmetic operations (that is, addition and subtraction), logical operations, and matrix-vector multiplication on data have been optically implemented, by use of a two-dimensional spatial-encoding technique. For addition and subtraction, one of the operands in decimal form is converted into the unsigned negabinary form, whereas the other decimal number is represented in the signed negabinary form. The result of operation is obtained in the mixed negabinary form and is converted back into decimal. Matrix-vector multiplication for unsigned negabinary numbers is achieved through the convolution technique. Both of the operands for logical operation are converted to their signed negabinary forms. All operations are implemented by use of a unique optical architecture. The use of a single liquid-crystal-display panel to spatially encode the input data, operational kernels, and decoding masks have simplified the architecture as well as reduced the cost and complexity.

Algorithms for optoelectronic implementation of modified signed-digit division, square-root, logarithmic, and exponential functions

Algorithms for computing complex elementary functions based on the modified signed-digit (MSD) number system representations are proposed. An arithmetic unit that performs parallel one-step addition (subtraction), multiplication, and division is proposed to achieve the computation of complex functions such as the square-root, logarithm, exponential, and other related operations. An optoelectronic correlator-based architecture is suggested for implementing the proposed MSD algorithms to compute the above-mentioned elementary functions. We utilized the symbolic substitution technique to reduce the number of computation rules involved.

Two-step digit-set-restricted modified signed-digit addition-subtraction algorithm and its optoelectronic implementation

A novel, to our knowledge, two-step digit-set-restricted modified signed-digit (MSD) addition-subtraction algorithm is proposed. With the introduction of the reference digits, the operand words are mapped into an intermediate carry word with all digits restricted to the set {1, 0} and an intermediate sum word with all digits restricted to the set {0, 1}, which can be summed to form the final result without carry generation. The operation can be performed in parallel by use of binary logic. An optical system that utilizes an electron-trapping device is suggested for accomplishing the required binary logic operations. By programming of the illumination of data arrays, any complex logic operations of multiple variables can be realized without additional temporal latency of the intermediate results. This technique has a high space-bandwidth product and signal-to-noise ratio. The main structure can be stacked to construct a compact optoelectronic MSD adder-subtracter.

Compact parallel optical modified-signed-digit arithmetic-logic array processor with electron-trapping device

A compact two-step modified-signed-digit arithmetic-logic array processor is proposed. When the reference digits are programmed, both addition and subtraction can be performed by the same binary logic operations regardless of the sign of the input digits. The optical implementation and experimental demonstration with an electron-trapping device are shown. Each digit is encoded by a single pixel, and no polarization is included. Any combinational logic can be easily performed without optoelectronic and electro-optic conversions of the intermediate results. The system is compact, general purpose, simple to align, and has a high signal-to-noise ratio.

Recoded and nonrecoded trinary signed-digit adders and multipliers with redundant-bit representations

Highly-efficient two-step recoded and one-step nonrecoded trinary signed-digit (TSD) carry-free adders-subtracters are presented on the basis of redundant-bit representation for the operands' digits. It has been shown that only 24 (30) minterms are needed to implement the two-step recoded (the one-step nonrecoded) TSD addition for any operand length. Optical implementation of the proposed arithmetic can be carried out by use of correlation- or matrix-multiplication-based schemes, saving 50% of the system memory. Furthermore, we present four different multiplication designs based on our proposed recoded and nonrecoded TSD adders. Our multiplication designs require a small number of reduced minterms to generate the multiplication partial products. Finally, a recently proposed pipelined iterative-tree algorithm can be used in the TSD adders-multipliers; consequently, efficient use of all available adders can be made.

Parallel optical negabinary arithmetic based on logic operations

On the basis of signed-digit negabinary representation, parallel two-step addition and one-step subtraction can be performed for arbitrary-length negabinary operands. The arithmetic is realized by signed logic operations and optically implemented by spatial encoding and decoding techniques. The proposed algorithm and optical system are simple, reliable, and practicable, and they have the property of parallel processing of two-dimensional data. This leads to an efficient design for the optical arithmetic and logic unit.

Design of an optical content-addressable parallel processor for expert systems

The slow execution speed of current rule-based systems (RBS's) has restricted their application areas. To improve the speed of RBS's, researchers have proposed various electronic multiprocessor systems as well as optical systems. However, the electronic systems still suffer in performance from the large amount of required time-consuming pattern-matching and comparison operations at the core of RBS's. And optical systems do not fully exploit the available parallelism in RBS's. We propose an optical content-addressable parallel processor for expert systems. The processor executes the three basic RBS operations, match, select, and act, in a highly parallel fashion. Additionally, it extracts and exploits all possible parallelism in a RBS. Distinctive features of the proposed system include the following: (1) two-dimensional representation of data (knowledge) and control information to exploit the parallelism of optics in the three RBS units; (2) capability of processing general-domain knowledge expressed in terms of variables, numbers, symbols, and comparison operators such as greater than and less than; (3) the parallel optical match unit, which performs the two-dimensional optical pattern matching and comparison operations; (4) a novel conflict-resolution algorithm to resolve conflicts in a single step within the optical select unit. The three units and the general-knowledge representation scheme are designed to make the optical content-addressable parallel processor for expert systems suitable for any high-speed general-purpose RBS.

Two-stage modified signed-digit optical computing by spatial data encoding and polarization multiplexing

We propose and demonstrate an effective two-stage modified signed-digit optical computing technique (in contrast to previous three-stage techniques) based on spatial data encoding, polarization multiplexing, and multiple imaging. Our proposed reduction in operation stages requires a reference operation in addition to the transformation and weight operations common to three-stage systems. In our system's first stage a transformation (or weight) operation and a reference operation are implemented in parallel by use of four distinct polarization-multiplexed kernel operations. In the second stage the final desired result (e.g., addition and subtraction) and its complement are obtained in parallel with a single kernel operation. The operation speed of our two-stage modified signed-digit computing method is 33% faster than previous three-stage modified signed-digit algorithms.

Optoelectronic butterfly interconnection architecture of modified signed-digit arithmetic systems: fully parallel adder and subtracter

The carry-free property of modified signed-digit addition is discussed, and a space-position-logic-encoding scheme is proposed, which not only makes best use of the convenience of binary (0, 1) logic operation but is also suitable for the trinary (1, 0, 1-) property of modified signed-digit digits. Based on the spaceposition-logic-encoding scheme, a fully parallel modified signed-digit adder and subtracter is built by use of optoelectronic switch modules and butterfly interconnections; thus an effective combination of a parallel algorithm and a parallel architecture is implemented. The effectiveness of this architecture is verified by both simulation and experimental results.

Modified signed-digit arithmetic based on redundant bit representation

Fully parallel modified signed-digit arithmetic operations are realized based on redundant bit representation of the digits proposed. A new truth-table minimizing technique is presented based on redundant-bitrepresentation coding. It is shown that only 34 minterms are enough for implementing one-step modified signed-digit addition and subtraction with this new representation. Two optical implementation schemes, correlation and matrix multiplication, are described. Experimental demonstrations of the correlation architecture are presented. Both architectures use fixed minterm masks for arbitrary-length operands, taking full advantage of the parallelism of the modified signed-digit number system and optics.

Parallel optical computing using recoded trinary signed-digit numbers

We propose a simple recoded trinary signed-digit number representation for parallel optical computing. This technique performs multidigit carry-free addition and borrow-free subtraction in constant time, using only 50% of the, minterms required in the most recently reported trinary signed-digit arithmetic technique. One may use a single-step optoelectronic or a two step all-optical architecture to implement the proposed technique.

Symmetrically recoded modified signed-digit optical addition and subtraction

Symmetrically recoded modified signed-digit number algorithms are proposed for carry-free arithmetic. The superiority of the new algorithms is established over all other two-step-based symbolic-substitution optical implementations.

Parallel modified signed-digit arithmetic using an optoelectronic shared content-addressable-memory processor

Addition is the most primitive arithmetic operation in digital computation. Other arithmetic operations such as subtraction, multiplication, and division can all be performed by addition together with some logic operations. With the binary number system, addition speed is inevitably limited by the carry-propagation schemes. On the other hand, carry-free addition is possible when the modified signed-digit (MSD) number representation is used. We propose a novel optoelectronic scheme to handle the parallel MSD addition and subtraction operations. An optoelectronic shared content-addressable memroy is introduced. The shared content-addressable memory uses free-space optical processing to handle the large amount of parallel memory access operations and uses electronics to postprocess and derive logic decisions. We analyze the accuracy that the required optical hardware can deliver by using a statistical cross-talk-rate model that we propose. We also evaluate other important device and system performanceparameters, such as the memory capacity or the maximum number of parallel bits the adder can handle in terms of a given cross-talk rate at a certain repetition rate, the corresponding diffraction-limited memory density, and the system's power efficiency. To confirm the underlining operational principles of the proposed optoelectronic shared content-addressable-memory MSD adder, we design and perform initial experiments for handling 8-bit MSD number addition and subtraction and present the results.

Symbolic substitution modified signed-digit optical adder

A high-accuracy fixed-point optical adder that operates in parallel on many long words and that uses a pipelined correlator architecture is described. A symbolic substitution algorithm with the modified signed-digit number representation is used to perform fixed-point additions with limited carries. A new set of substitution rules and encodings is developed to combine the recognition and substitution steps into one correlation operation. This reduces hardware requirements, improves throughput by reducing the space-bandwidth product needed, and reduces latency (the delay between when data enter the processor and when the final output is available) by a factor of 2. This algorithm and our new modified signed-digit encodings and substitution rules improve the performance of other correlator and noncorrelator optical numeric computing architectures.

Modified-signed-digit arithmetic for multi-input digital optical computing

We propose and demonstrate a modified-signed-digit (MSP) arithmetic to achieve multi-input digital optical computing. Our approach utilizes hybrid addition-subtraction transformation (or weight operation) rules among multiple inputs. This results in operation speeds that exceed those of two-input MSD arithmetic for multi-input computing. Optical'implementation of the proposed multi-input MSD arithmetic by utilizing spatial data encoding and an optical fan-out element is also presented and experimentally demonstrated.

Efficient trinary signed-digit symbolic arithmetic

A new technique for high-speed trinary signed-digit (TSD) arithmetic that uses optical symbolic substitution is presented. This technique performs multibit carry-free addition and borrow-free subtraction in constant time. The proposed TSD scheme utilizes the minimum number of minterms compared with the previously reported modified signed-digit and TSD number systems.

Redundant binary number representation for an inherently parallel arithmetic on optical computers

A simple redundant binary number representation suitable for digital-optical computers is presented. By means of this representation it is possible to build an arithmetic with carry-free parallel algebraic sums carried out in constant time and parallel multiplication in log N time. This redundant number representation naturally fits the 2's complement binary number system and permits the construction of inherently parallel arithmetic units that are used in various optical technologies. Some properties of this number representation and several examples of computation are presented.

Modified-signed-digit optical computing by using fan-out elements

We present a novel three-step modified-signed-digit optical computing system based on the discrete correlation of space-coded input matrices that are multiply imaged by using optical fan-out elements. The advantages of our method over other approaches include a larger throughput, more flexible operation, and an easier optical implementation.

Modified signed-digit optical processors using computer-generated holograms

Modified signed-digit (MSD) numbers offer convenient parallel addition and subtraction of bits. The parallel addition of any two MSD numbers, no matter what the values of their bits may be, requires only three bit-pattern transformations. To perform such transformations optically, however, MSD data must be represented in a form suitable for cascade connection. Proposed here is a new cascade-connective MSD optical processor. Adding principles are successfully demonstrated by using an optical threshold device array in addition to new computer-generated holograms that are adjusted to equalize the intensity of their diffracted light beams.

Optical processing based on conditional higher-order trinary modified signed-digit symbolic substitution

Techniques for higher-order modified signed-digit trinary arithmetic by using optical symbolic substitution are presented. This method provides fast multibit computation by adopting a two-step symbolicsubstitution scheme. Since more information is represented in fewer digits, this technique leads to a compact design. A content-addressable memory-based and a joint transform correlator-based optical implemention for the proposed technique are also presented.

Arithmetic processing with a joint-transform correlator

A technique for realizing arithmetic operations that uses a joint-transform correlator is presented. Optical implementations of the technique using a single and a multichannel joint-transform correlator are suggested. The performance of the proposed systems is verified by computer simulation.

Recoded signed-digit binary addition-subtraction using opto-electronic symbolic substitution

Two opto-electronic implementations of carry-free addition and borrow-free subtraction of recoded signed-digit binary numbers that use optical symbolic substitution are proposed.

Digital optical processing based on higher-order modified signed-digit symbolic substitution

An efficient higher-order modified signed-digit optical symbolic substitution technique for addition and subtraction has been derived. This two-step symbolic substitution technique, which is independent of the number of bits to be processed, saves a tremendous amount of computation time. Two separate approaches for optical implementation that use content-addressable memory and the joint transform correlator are also suggested.

Modified signed-digit trinary arithmetic by using optical symbolic substitution

Carry-free addition and borrow-free subtraction of modified signed-digit trinary numbers with optical symbolic substitution are presented. The proposed two-step and three-step algorithms can be easily implemented by using phase-only holograms, optical content-addressable memories, a multichannel correlator, or a polarization-encoded optical shadow-casting system.

Digital optical processor based on symbolic substitution using holographic matched filtering

We propose a digital optical arithmetic processor design based on symbolic substitution using holographic matched and space-invariant filters. The proposed system performs Boolean logic, binary addition, and subtraction in a highly parallel manner; i.e., the processing time depends on word size but not array size. Algorithms for performing binary addition and subtraction in parallel are presented. A skew problem occurring when symbolic substitution is applied to binary addition and subtraction with space-invariant systems is addressed, and its solution is suggested. Crosstalk in symbolic substitution is described, and new symbols which can prevent the crosstalk are introduced. System analysis and fundamental limitations of the proposed system are also presented in terms of processing time, overall light efficiency, and the maximum array size of the input data plane. The performance of the proposed system with that of the current electronic supercomputers has been compared by combining information about the processing time and maximum array size.

Content-addressable-memory-based single-stage optical modified-signed-digit arithmetic

Using a novel nonholographic optoelectronic content-addressable memory in a free-space angular multiplexing geometry, a single-optical-stage compact parallel optical modified-signed-digit arithmetic processing architecture is proposed. Some spatial light modulator based experimental results are also presented.

Number representation effects in truth-table look-up processing: 8-bit addition example

The parallelism and interconnectivity of optical systems may provide important advantages for these systems in massively parallel processing applications. Electronic systems, however, retain all the advantages of a highly developed technology that has been widely applied with excellent success. In both of these technologies, the methods of direct truth-table look-up processing are becoming increasingly important as the need grows for increased speed and throughput. A major issue in truth-table look-up processing is the number representation used for data. In this paper, the effects of number representation are investigated for the important case of 8-bit addition as a specific example. The inputs are two 8-bit binary numbers together with an input carry. The output is a full precision 9-bit binary sum. For the intermediate processing three number representations are treated: binary, residue, and modified signed-digit. The numbers in all three representations are in binary-coded form throughout the processing. The critically important steps of encoding the numbers into the residue and modified signed-digit systems and then decoding the results back into direct binary are also performed using truth-table look-up methods. For the direct binary representation, a total of 2545 gates (2519 holograms) are required. For the residue representation, a total of 1764 gates (1686 holograms) are required. For the modified signed-digit representation, a total of 4142 gates (4052 holograms) are required.

Modified-signed digit arithmetic using an efficient symbolic substitution

An efficient symbolic substitution scheme for modified-signed digit arithmetic operations is introduced. In this technique, an additional bit is used along with each pair of the input bits so that the nth additional bit is a characteristic of the (n - 1)th pair of input bits. The truth table minimization thereby shows that relatively fewer minterms are to be included in the corresponding optical content-addressable memory.

Optical parallel image skeletonization using contentaddressable memory-based symbolic substitution

In this paper, two optical image skeletonization algorithms are introduced. In both algorithms, the matching between an input and a set of precalculated parallel check patterns is performed. Based on the matching results, multistage symbolic substitution operations are incorporated. For an optical implementation, an optical hologram-based content-addressable memory technique is employed. The corresponding optical architecture as well as character skeletonization examples are presented.

Optical on-the-fly conversion of a modified signed digit into two's complement binary number representation

An optical carry-free technique is introduced for conversion of a modified signed digit (MSD) into two's complement binary number. Using a combination of optical polarizing beam splitters and retardation waveplates, the proposed device performs this conversion on the fly. The availability of this converter will lead to a large speed increase for various proposed optical parallel MSD arithmetic processors.