Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-05-14
2004-06-01
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S250000, C708S523000, C708S003000
Reexamination Certificate
active
06745219
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computing systems having arithmetic units that utilize stochastic data processing. More particularly, the invention relates to a computer system having arithmetic units in which analog signals and digital operands are converted to stochastic representations using pseudorandom M-sequences.
2. Description of the Related Art
Stochastic computing is based on representation of digital operands and analog signals by binary stochastic sequences. Stochastic computing is efficient due to simple hardware of basic computing elements: adders and multipliers. In particular, stochastic multiplication is performed by the logic AND gate for operands A and B within data domain (0,1) or XNOR for operands A and B within data domain (−1,1).
A pseudorandom numbers generator is a primary source of stochastic sequences. The pseudorandom numbers generator generates binary pseudorandom M-sequences having a period of N=2
n
−1 time slots, which is provided at the output of an n-bit linear feedback shift register. Digital operands and analog signals are converted to their representations by stochastic sequences by comparing the digital operands and analog signals to a pseudorandom sequence of numbers. Either a digital or an analog comparator performs this operation. A counter performs the reverse operation, of converting a stochastic sequence into a digital operand.
The operand is a fractional number having a numerator that corresponds to the number of 1's in a pseudorandom sequence for the period N=2
n
−1 time slots, where N stands for denominator of the fractional number. The accuracy of the conversion of the operand is determined by the length N of the pseudorandom sequence and is equal to 1/N.
The performance of stochastic multiplication requires independence of sequences at the multiplier's inputs. The stochastic independence is achieved by shifting the phase position of sequences with respect to each other, by placing a delay circuit (e.g., shift register) at one of the multiplier's inputs. The value of a delay is predetermined and is defined as the “suitable delays value”.
For the given method, the accuracy of multiplication is defined as the “average accuracy”, which depends from the multiplied operands and the delay circuit. However, for n-bit operands representation by pseudorandom sequences with accuracy of 1/(2
n
−1), the error of multiplication is not constant and exceeds the accuracy of representation of the operands.
A device for multiplication is shown in USSR Certificate of Authorship No. 718843, published Feb. 28, 1980. The device has an AND block for probablility and an AND-OR block for conversion of the digital operands to pseudorandom sequences. By this conversion, the stochastic independence of sequences at the multiplier's input is achieved with an accuracy of 1/(2
n
−1). The circuit diagram of this device for multiplication, however, is only for two operands.
Addition of two operands A and B represented by stochastic sequences is carried out by the adder, which is a logic OR gate. The required incompatibility of pseudorandom sequences at the adder's inputs is achieved by preliminarily multiplying each of the two sequences by an independence sequence with a probability of 1's equal to 1/2. Hence, while one of the adding sequences is multiplied by such sequence, another one is multiplied by its inverse value. The result of the addition is (A+B)/2.
For sequences that are formed by one pseudorandom number generator, a similar incompatibility can be carried out by switch operation. Thus, the result of addition approximately corresponds to the arithmetical mean of A and B. The specified methods do not carry out addition of two n-bit operands represented by pseudorandom sequences with an accuracy of 1/(2
n
−1) on length N=2
n
−1 time slots.
The addition of more than two operands is performed by a tree-like structure. The result of addition is a complex weighted add, where the weight factor does not uniformly represent the adding sequences. In particular, when two operands A and B are added, a stochastic sequence representing result (A+B)/2 is produced. For addition of the three operands A, B and C, a stochastic sequence representing the result (C+(A+B)/2)/2 is produced.
The given method makes performance of addition in systems of data processing inconvenient. For these reasons the method of stochastic data processing has not found practical application since it does not provide performance of arithmetic operations of multiplication and addition with a given accuracy 1/(2
n
−1) on length N=2
n
−1 time slots of pseudorandom sequences.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for conversion of a signal to a sequence, as well as for multiplication and addition, using a stochastic data processing technique. Arithmetic operations are carried out above n-bits operands represented by pseudorandom sequences of length N=2
n
−1 time slots, with an accuracy of arithmetical operations equal to 1/(2
n
−1). Initial data is converted to sequences by one pseudorandom numbers generator.
In the preferred embodiment, the method and apparatus according to the present invention comprises: two logic units that generate incompatible pseudorandom sequences with a given probability of occurrence of 1's; a set of data-to-sequence converters that convert n-bits digital operands to pseudorandom sequences using sequences of the logic unit; a set of stochastic multipliers, each of which consists of a stochastic multiplier core and two data-to-sequence converters providing conversion of a pair of n-bits digital operands to pseudorandom sequences using a separate logic unit, which provides desirable accuracy of multiplication; a set of stochastic adders, each of which carries out addition of k summands represented by stochastic sequences received simultaneously on k inputs of adder. The adder produces an output signal that corresponds to a weighted (1/K) add of the k summands.
All of the operations of the stochastic data processing system—arithmetical operations and conversion of signals—are carried out in parallel and simultaneously during the period N=2
n
−1 time slots of the pseudorandom numbers generator.
REFERENCES:
patent: 4115867 (1978-09-01), Vladimirov et al.
patent: 4176399 (1979-11-01), Hoffmann et al.
patent: 4219877 (1980-08-01), Vladimirov et al.
patent: 4493046 (1985-01-01), Watanabe
patent: 4972363 (1990-11-01), Nguyen et al.
patent: 5046036 (1991-09-01), Tezuka
patent: 5170071 (1992-12-01), Shreve
patent: 5317528 (1994-05-01), Gofman
patent: 5412587 (1995-05-01), Holt et al.
patent: 5828752 (1998-10-01), Iwamura et al.
patent: 6141668 (2000-10-01), Shimada
patent: 6414949 (2002-07-01), Boulanger et al.
patent: 718843 (1980-02-01), None
Blank Rome LLP
Mai Tan V.
LandOfFree
Arithmetic unit using stochastic data processing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arithmetic unit using stochastic data processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic unit using stochastic data processing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3326660