Extendable multiple-digit base-2.SUP.n .in-memory adder device

Abstract

The base-2.sup.n in-memory adder device mainly comprises Perpetual Digital Perceptron (PDP) in-memory adder with Read Only Memory (ROM) arrays for storing the binary sum codes of the addition table for processing the addition operations of two n-bit binary integer operands. Since the integer numbers can be represented by the binary codes of multiple digits of base-2.sup.n integer numbers, the base-2.sup.n in-memory adder device can iterate multiple times of the digit-additions to complete the binary code addition for two m-digit base-2.sup.n integer operands. Consequently, the base-2.sup.n in-memory adder device can improve the computation efficiency and save the computation power by eliminating the data transportations between Arithmetic Logic Unit (ALU), registers, and memory units.

Claims

1. An in-memory adder device for performing digit-by-digit addition on a first operand and a second operand to generate a final sum result and a final carry digit, wherein each of the first operand, the second operand and the final sum result has m digits in base 2.sup.n, the in-memory adder device comprising: an in-memory adder configured to perform addition of two n-bit digits respectively selected from the first operand and the second operand based on each of m cycles of a first control signal, comprising: a first read-only-memory (ROM) array comprising (2.sup.n×2.sup.n) rows by 2n columns of first memory cells for parallel comparing the two selected n-bit digits with a number (2.sup.n×2.sup.n) of 2n-bit content symbols hardwired in the (2.sup.n×2.sup.n) rows of first memory cells to cause one row of the first memory cells to assert a match signal when the two selected n-bit digits match its hardwired 2n-bit content symbol; a second ROM array comprising (2.sup.n×2.sup.n) rows by (2×(n+1)) columns of second memory cells and generating a corresponding pair of (n+1)-bit sum values according to an asserted match signal, wherein (2.sup.n×2.sup.n) pairs of (n+1)-bit sum values of an addition table are respectively hardwired in the (2.sup.n×2.sup.n) rows of second memory cells; and a first multiplexer to output a n-bit sum code and a carry-out bit selected from one of the corresponding pair of (n+1)-bit sum values according to a carry-in bit at each of the m cycles; and a storage element configured to receive the carry-out bit at a current cycle and provide the carry-out bit as the carry-in bit at its next cycle; wherein a number m of n-bit sum codes obtained at the end of the m cycles form the final sum result.

2. The in-memory adder device according to claim 1, which performs the digit-by-digit addition starting from the least significant digit of the first operand and the second operand.

3. The in-memory adder device according to claim 1, wherein n-bit augends and n-bit addends of the addition table defines the 2n-bit content symbols.

4. The in-memory adder device according to claim 1, wherein one of the corresponding pair of (n+1)-bit sum values is associated with the carry-in bit equal to 0 while the other of the corresponding pair of (n+1)-bit sum values is associated with the carry-in bit equal to 1.

5. The in-memory adder device according to claim 1, further comprising: a first operand register coupled to the first ROM array for storing the first operand; and a second operand register coupled to the first ROM array for storing the second operand.

6. The in-memory adder device according to claim 5, further comprising: a second multiplexer coupled between the first ROM array, the first and the second operand registers to retrieve the two selected n-bit digits from a same selected digit location in the first and the second operand registers according to a second control signal.

7. The in-memory adder device according to claim 1, further comprising: a sum register coupled to the first multiplexer, wherein a most significant bit location in the sum register stores the carry-out bit derived from a most significant digit addition as the final carry digit and the rest of locations in the sum register store the final sum result.

8. The in-memory adder device according to claim 7, further comprising: a third multiplexer coupled between the first multiplexer and the sum register to selectively connect the output of the first multiplexer to a corresponding digit location in the sum register according to a second control signal corresponding to the two selected n-bit digits.

9. The in-memory adder device according to claim 1, wherein the storage element is reset to output the carry-in bit of 0 prior to the m cycles of the first control signal.

10. The in-memory adder device according to claim 1, further comprising: a switch device configured to store the carry-out bit from the first multiplexer into the most significant bit location in the sum register in response to a second control signal corresponding to two most significant digits respectively selected from the first operand and the second operand.

11. The in-memory adder device according to claim 1, wherein the in-memory adder comprises: a detection circuit to respectively apply a number (2.sup.n×2.sup.n) of switching signals to a number (2.sup.n×2.sup.n) of wordlines of the second ROM array in response to a number (2.sup.n×2.sup.n) of match signals from the first ROM array at each of the m cycles; wherein the detection circuit activates a corresponding switching signal based on the asserted match signal, and wherein while receiving an activated switching signal, a corresponding row of second memory cells is switched on to output its hardwired pair of (n+1)-bit sum values.

12. An operating method of an in-memory adder device, the in-memory adder device comprising an in-memory adder and a storage element, the in-memory adder comprising a first read-only-memory (ROM) array and a second ROM array, the first ROM array comprising (2.sup.n×2.sup.n) rows by 2n columns of first memory cells, the second ROM array comprising (2.sup.n×2.sup.n) rows by (2×(n+1)) columns of second memory cells, wherein (2.sup.n×2.sup.n) pairs of (n+1)-bit sum values of an addition table are respectively hardwired in the (2.sup.n×2.sup.n) rows of second memory cells, the method comprising the steps of: providing two n-bit digits respectively selected from a first operand and a second operand for the first ROM array; parallel comparing the two selected n-bit digits with a number (2.sup.n×2.sup.n) of 2n-bit content symbols hardwired in the (2.sup.n×2.sup.n) rows of first memory cells to cause one row of the first memory cells to assert a match signal when the two selected n-bit digits match its hardwired 2n-bit content symbol; outputting one pair of (n+1)-bit sum values according to an asserted match signal by the second ROM array; selecting one from the one pair of (n+1)-bit sum values as a n-bit sum code and a carry-out bit according to a carry-in bit from the storage element; receiving the carry-out bit by the storage element at a current cycle of m cycle of a control signal; and repeating steps of providing, comparing, outputting, selecting and receiving until all the digits of the first operand and the second operand are processed to obtain a final sum result and a final carry digit; wherein each of the first operand, the second operand and the final sum result has m digits in base 2.sup.n; and wherein a number m of n-bit sum codes obtained at the end of the m cycles form the final sum result.

13. The method according to claim 12, further comprising: resetting the storage element to cause the carry-in bit to be equal to 0 prior to all the steps.

14. The method according to claim 12, wherein the step of providing comprises: respectively retrieving the two selected n-bit digits from a same digit location in a first operand register and a second operand register based on ascending order of digit numbers of the first and the second operands; wherein the in-memory adder device further comprises the first operand register storing the first operand and the second operand register storing the second operand.

15. The method according to claim 12, further comprising: providing the carry-in bit by the storage element at the current cycle before the step of selecting; wherein the carry-in bit is a carry-out bit previously received by the storage element at a cycle previous to the current cycle.

16. The method according to claim 12, further comprising: storing the n-bit sum code in a corresponding digit location in a sum register after the step of selecting and prior to the step of repeating; wherein the in-memory adder device further comprises the sum register.

17. The method according to claim 16, further comprising: storing the carry-out bit as the final carry digit in a most significant bit location of the sum register after the step of repeating.

18. The method according to claim 12, further comprising: respectively applying a number m of switching signals to a number m of wordlines in the second ROM array according to a number (2.sup.n×2.sup.n) of match signals from the first ROM array prior to the step of outputting and after the step of comparing.

19. The method according to claim 18, wherein the step of outputting comprises: switching on a row of second memory cells to output its corresponding pair of (n+1)-bit sum values in response to a received activated switching signal; and switching off a row of second memory cells in response to a received de-activated switching signal.

20. The method according to claim 12, which performs digit by digit addition starting from the least significant digit of the first operand and the second operand.

21. The method according to claim 12, wherein n-bit augends and n-bit addends of the addition table defines the 2n-bit content symbols.

22. The method according to claim 12, wherein one of the corresponding pair of (n+1)-bit sum values is associated with the carry-in bit equal to 0 while the other of the corresponding pair of (n+1)-bit sum values is associated with the carry-in bit equal to 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) For a better understanding of the present invention and to show how it may be carried into effect, reference will now be made to the following drawings, which show the preferred embodiment of the present invention, in which:

(2) FIG. 1 shows the conventional Von-Neumann computing architecture for a typical Central Processing Unit (CPU).

(3) FIG. 2a shows a logic table for a full adder.

(4) FIG. 2b shows logic gate schematics for the full adder associated with FIG. 2a.

(5) FIG. 2c shows the symbol for the conventional two-operand bit addition operation.

(6) FIG. 3 shows the schematics of the conventional m-bit ripple-carry adder comprising a chain of “m-1” binary full adders and a binary half adder.

(7) FIG. 4 shows an n-bit by n-bit addition table for two n-bit binary integer number operands with the carry bit C.sub.i=0 (top in the cell) and the carry bit C.sub.i=1 (bottom in the cell).

(8) FIG. 5 shows the schematics of Perpetual Digital Perceptron (PDP) base-2.sup.n in-memory adder applied for the single-digit addition of the two m-digit base-2.sup.n integer numbers according to an embodiment of the invention.

(9) FIG. 6 shows the schematic of the Input Buffer and Driver Unit in the PDP in-memory adder in FIG. 5.

(10) FIG. 7 shows the schematic of 2n-bit by (2.sup.2n)-row CROM array in the PDP in-memory adder in FIG. 5.

(11) FIG. 8 shows the schematics of Match-Detector Unit in the PDP in-memory adder in FIG. 5.

(12) FIG. 9 shows the schematic of the (2×(n+1))-bit by (2.sup.2n)-row RROM array in the PDP in-memory adder in FIG. 5.

(13) FIG. 10 shows the schematic of the “2-to-1” multiplexer in the PDP in-memory adder of FIG. 5 for selecting the outputs of sum codes for carry bit=0 and carry bit=1.

(14) FIG. 11 shows the schematics of the base-2.sup.n in-memory adder device for two m-digit base-2.sup.n integer numbers according to an embodiment of the invention.

(15) FIG. 12 shows the schematics of a number “m-digit×n-bit” of binary registers for the integer number A, and a number “m-digit×n-bit” of binary registers for the integer number B associated with the base-2.sup.n in-memory adder device in FIG. 11.

(16) FIG. 13 shows the schematic of “m-to-1” input multiplexer for connecting the nodes of each digit of A register and B register to the input nodes of the PDP base-2.sup.n in-memory adder in FIG. 11 for the single-digit binary addition operation.

(17) FIG. 14 shows the schematic of “1-to-m” output multiplexer for selecting the output nodes of the PDP base-2.sup.n in-memory adder 500 in FIG. 11 to the input nodes of the sum S register 150.

(18) FIG. 15 shows the schematic of the number “(m-digit×n-bit)+1” of binary registers for the sum register S 150 associated with the base-2.sup.n in-memory adder device in FIG. 11.

(19) FIG. 16 the schematic of gated register C 160 associated with the base-2.sup.n in-memory adder device in FIG. 11 for storing the carry bit for each digit addition operation.

(20) FIG. 17 shows the schematics of the 4-digit hexadecimal in-memory adder device according to an embodiment of the invention.

(21) FIG. 18 shows the binary code for the 4-digit hexadecimal addition table associated with the 4-digit hexadecimal in-memory adder device in FIG. 17.

(22) FIG. 19 shows the operational timing sequence for the 4-digit hexadecimal in-memory adder device in FIG. 17.

DETAILED DESCRIPTION OF THE INVENTION

(23) The following detailed description is meant to be illustrative only and not limiting. It is to be understood that other embodiment may be utilized and element changes may be made without departing from the scope of the present invention. Also, it is to be understood that the phraseology and terminology used herein are for the purpose of description and should not be regarded as limiting. Those of ordinary skill in the art will immediately realize that the embodiments of the present invention described herein in the context of methods and schematics are illustrative only and are not intended to be in any way limiting. Other embodiments of the present invention will readily suggest themselves to such skilled persons having the benefits of this disclosure.

(24) To illustrate the idea of m-digit base-2.sup.n in-memory adder for two m-digit base-2.sup.n integer number operands, we apply 4-digit base-2.sup.4 (hexadecimal) in-memory adder device for two 16-bit (i.e., 4-digit×4-bit) binary integer number operands for the illustrated embodiment. The embodiment is for the illustration purpose but shall not be limited to specific numbers of m and n depending on the optimized design environment circumstance for the IC chips.

(25) The schematic of the 4-digit hexadecimal in-memory adder device 170 is shown in FIG. 17. The 4-digit hexadecimal in-memory adder device 170 comprises an 16-bit binary operant register A 171 and an 16-bit binary operant register B 172 for storing the binary codes of the two 4-digit hexadecimal integer numbers, an 8-bit “4-to-1” Input Multiplexer 173 for selecting the binary codes of each digit of A.sub.i and B.sub.i, a PDP Hexadecimal In-Memory Adder 174 for storing the sum codes of the 4-bit by 4-bit addition table shown in FIG. 18, a 4-bit “1-to-4” Output Multiplexer 175 for selecting the digit of the binary sum code S.sub.i to the sum S Register 176, a 17-bit sum S register 176 for storing the 16-bit binary sum code plus the carry digit/bit, S.sub.4/C.sub.4 from the addition operations, and a gated flip-flop C register 160 for storing the processing carry-bit of each digit addition.

(26) FIG. 19 shows the operational timing sequence for the 4-digit hexadecimal in-memory adder device 170 in the embodiment. In the first clock cycle, the voltage signals of the two 16-bit integer number operands for the addition operation are fetched into the 16-bit binary register A 171 and register B 172, respectively. At the same time cycle the processing carry-bit C register 160 is reset to zero by the “Clr” with the high voltage signal V.sub.DD for the first digit operation. For the first half of the second clock cycle, the first digit addition is processed by setting “SW.sub.0” and “Enb” with the high voltage signal V.sub.DD for activating the in-memory adder device 170, while for the second half of the second clock cycle for “Enb” with the low voltage signal V.sub.SS, the voltage signals of the binary code for the sum of the first digit addition are stored in the first digit location (4 bits) in the sum register 176 and the carry-bit C register 160 is set to the digital value of C.sub.1. For the first half of the third clock cycle, the second digit addition is processed by setting “SW.sub.1” and “Enb” with the high voltage signal V.sub.DD for activating the in-memory adder device 170, while for the second half of the third clock cycle for “Enb” with the low voltage signal V.sub.SS the voltage signals of the binary code for the sum of the second digit addition are stored in the second digit location (4 bits) in sum register 176 and the carry-bit C register 160 is set to the digital value of C.sub.2. For the first half of the fourth clock cycle, the third digit addition is processed by setting “SW.sub.2” and “Enb” with the high voltage signal V.sub.DD for activating the in-memory adder device 170, while for the second half of the fourth clock cycle for Enb with the low voltage signal V.sub.SS, the voltage signals of the binary code for the sum of the third digit addition are stored in the third digit location (4 bits) in sum register 176 and the carry-bit C register 160 is set to the digital value of C.sub.3. For the first half of the fifth clock cycle, the fourth digit addition is processed by “SW.sub.3” and “Enb” with the high voltage signal V.sub.DD for activating the in-memory adder device 170, while for the second half of the fifth clock cycle for “Enb” with the low voltage signal V.sub.SS, the voltage signals of the binary code for the sum of the fourth digit addition are stored in the fourth digit location (4 bits) in sum register 176 and at the same time the voltage signals of the carry-bit C.sub.4 is also stored in the carry-digit flip-flop S.sub.4 of the 17-bit register S 176 (i.e., the most significant bit in the 17-bit register S 176). The hexadecimal in-memory adder device 170 can repeat the procedure for five clock cycles to complete the additions of two 16-bit binary integer operands.

(27) The aforementioned description of the preferred embodiments of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form or to exemplary embodiment disclosed. Accordingly, the description should be regarded as illustrative rather than restrictive. The embodiment is chosen and described in order to best explain the principles of the invention and its best mode practical application, thereby to enable persons skilled in the art to understand the invention for various embodiments and with various modifications as are suited to the particular use or implementation contemplated. It is intended that the scope of the invention be defined by the claims appended hereto and their equivalents in which all terms are meant in their broadest reasonable sense unless otherwise indicated. The abstract of the disclosure is provided to comply with the rules requiring an abstract, which will allow a searcher to quickly ascertain the subject matter of the technical disclosure of any patent issued from this disclosure. It is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. Any advantages and benefits described may not apply to all embodiments of the invention. It should be appreciated that variations may be made in the embodiments described by persons skilled in the art without departing from the scope of the present invention as defined by the following claims. Moreover, no element and component in the present disclosure is intended to be dedicated to the public regardless of whether the element or component is explicitly recited in the following claims.