CN110705196A - Error-free adder based on random calculation - Google Patents
Error-free adder based on random calculation Download PDFInfo
- Publication number
- CN110705196A CN110705196A CN201910910312.9A CN201910910312A CN110705196A CN 110705196 A CN110705196 A CN 110705196A CN 201910910312 A CN201910910312 A CN 201910910312A CN 110705196 A CN110705196 A CN 110705196A
- Authority
- CN
- China
- Prior art keywords
- random
- error
- adder
- free
- output
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000004364 calculation method Methods 0.000 title abstract description 15
- 238000010606 normalization Methods 0.000 claims description 10
- 238000012545 processing Methods 0.000 claims description 5
- 238000004891 communication Methods 0.000 claims description 3
- 238000013461 design Methods 0.000 abstract description 4
- 238000005457 optimization Methods 0.000 abstract description 3
- 238000009825 accumulation Methods 0.000 abstract 2
- 238000000034 method Methods 0.000 description 12
- 238000010586 diagram Methods 0.000 description 8
- 238000006243 chemical reaction Methods 0.000 description 4
- 230000008569 process Effects 0.000 description 4
- 230000006870 function Effects 0.000 description 3
- 230000004048 modification Effects 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 238000004088 simulation Methods 0.000 description 2
- 230000004075 alteration Effects 0.000 description 1
- 238000013528 artificial neural network Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000009826 distribution Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 239000004065 semiconductor Substances 0.000 description 1
- 230000007704 transition Effects 0.000 description 1
- 238000009827 uniform distribution Methods 0.000 description 1
Images
Landscapes
- Tests Of Electronic Circuits (AREA)
- Analogue/Digital Conversion (AREA)
Abstract
The invention discloses an error-free adder based on random calculation, which is applied to the field of digital circuit optimization design and aims at solving the error problem of the existing random adder, and the error-free adder comprises the following components: an input converter, a random adder, and an output converter; the input converter is used for converting input data into a random sequence, the random sequence of the input random adder can have any position of '0' and '1', the random adder is used for completing addition operation of the random sequence, and the output of the random adder comprises: adding the result and the error; the output converter is used for converting the addition result to the traditional binary numerical value domain through accumulation, and carrying out shift operation and accumulation on the error according to the cascade stage number of the error to compensate and obtain the final error-free result.
Description
Technical Field
The invention belongs to the field of digital circuit optimization design, and relates to an implementation method of an error-free random computing unit.
Background
With the development of information technology, the complexity of various required signal processing algorithms is rapidly increased, and the traditional semiconductor process is close to the physical limit, and Moir thinks that Moire's law is dark and discolored by 2020. The optimization of integrated circuits mainly comes from the innovation of their design architecture, so it is necessary to research new algorithms to optimize the design of integrated circuits.
The main idea of scholars to apply random computation to neural networks and digital signal processing is to convert the conventional binary representation into a string of random sequences, in which the probability value is represented by the ratio of "1" to the total length of the sequence. The calculation is completed by a corresponding random calculation unit. The method has the advantages that basic logic gate circuits can be greatly reduced, so that a critical path is shorter, and the overall power consumption and the resource occupation are greatly reduced. However, the conventional random adder used in this method is generally implemented by an or gate or a multiplexer, and the or gate will take "1" when "0" and "1" are added; the multiplexer requires that the randomness of the selection sequence involved in the computation is high enough that otherwise uncontrollable computation errors occur, which is difficult to implement. These computational units are less accurate and cannot meet high-accuracy scenarios.
Disclosure of Invention
In order to solve the technical problem, the invention provides an error-free adder based on random calculation, and the positions of '0' and '1' in an input random sequence can be arbitrary and can be used under a high-precision condition.
The technical scheme adopted by the invention is as follows: an error-free adder based on random computation, comprising: an input converter, a random adder, and an output converter; the input converter is used for converting input data into a random sequence, the random adder is used for completing addition operation of the random sequence, and the output converter is used for converting the random sequence after passing through the random adder into a traditional binary numerical value;
the "0" and "1" in the random sequence input to the random adder may be any positions, and the output of the random adder includes: the addition result and the error.
The input converter includes: the device comprises a normalization module and a random sequence generation module, wherein the normalization module is used for converting input data into a probability domain, and the random sequence generation module converts the probability domain input data output by the normalization module into a probability domain random sequence.
When the addition result of the two input random adders is 1 for the first time, the addition result is output to be 0, and the error is 1; when the addition result is 1 again, the addition result is output as 1, and the error is 0.
The random adder is a scaling adder.
The output converter includes: the accumulator is used for converting an addition result back to a conventional binary number value and sending the addition result to the compensation unit; the compensation unit adds the error output by the random adder and the effective value output by the accumulator to obtain an error-free result.
The random adders may be cascaded.
When the random adders are cascaded, the final addition result and the cascade number of the cascade where the errors are located are obtained according to the cascaded random adders, and the error-free result is obtained by shifting and adding.
A digital signal processing system at least comprises the error-free adder.
A communication system comprises at least the error-free adder.
The invention has the beneficial effects that: the error-free adder is suitable for random computation and structurally comprises an input converter, a random adder and an output converter, wherein the random adder is a scaling adder and can be cascaded; the random adder and the output converter are sequentially connected in a circuit mode, input data are converted into a random sequence in the input converter, the random sequence serves as the input of the random adder, the positions of '0' and '1' in the input sequence of the random adder can be random, the output of the random adder is sent into the output converter, the conversion from the random sequence to a traditional binary numerical value domain is completed, and error compensation is carried out on the result, so that the random adder is free of error output; the error-free adder of the invention has the following advantages:
1. compared with the traditional adder, the adder uses fewer basic gate circuits, reduces resource consumption and shortens a critical path;
2, compared with the traditional random adder, the precision is higher;
3. the method is easy to realize in FPGA;
4. compared with the traditional binary adder, the input/output converter can be shared in large-scale cascade addition, so that the resources and the power consumption can be further saved;
5. the error-free adder can also be applied to a digital signal processing system and a communication system, and can reduce resources and power consumption.
Drawings
FIG. 1 is a diagram of a conventional random adder;
wherein, fig. 1(a) is a conventional random adder implemented by an or gate; FIG. 1(b) is a conventional random adder implemented by a multiplexer;
FIG. 2 is a diagram of an error-free adder according to the present invention;
FIG. 3 is a diagram of an input converter architecture;
FIG. 4 is a diagram of an error-free adder cascade;
FIG. 5 is a diagram of an output converter architecture;
fig. 6 is a simulation result diagram.
Detailed Description
The core of the invention is that the adder designed based on the random computing method is realized without error and can be infinitely cascaded, the positions of '0' and '1' in the input sequence can be arbitrary, and the FPGA realization mode of the adder is provided.
The invention is described in detail below with reference to the accompanying drawings:
the function of the two-input adder is z ═ x + y, where x and y represent the input data and z is the adder output. The input data is k bits wide. The conventional random adder is implemented by an or gate as shown in fig. 1(a) or a multi-way gate as shown in fig. 1(b), wherein the random adder implemented by the or gate requires that one path of two paths of input random sequences is in centralized distribution, and the other path is in uniform distribution; while the random adder implemented by the multiplexer contains uncertainty. Errors are generated in the calculation process of the two traditional random adders. In order to solve the error problem of the conventional adder, the present invention provides an error-free adder based on random computation as shown in fig. 2.
Fig. 2 is a diagram showing a structure of a random adder in the present embodiment. The structure comprises an input converter for converting input data into a random sequence in a probability domain, wherein the input converter sends the generated random sequence into a random adder to complete addition operation in the random domain, the output of the random adder is sent into an output converter to complete conversion from the random sequence to a traditional binary number and carry out error compensation on an output result to obtain a final error-free output result z.
The implementation of the input converter, the random adder and the output converter is described in detail below:
as shown in fig. 3, the input converter functions to convert input data into a probability domain, and includes: a normalization module and a random sequence generation module, wherein the normalization module is used for performing unified standard normalization on the input waveform data x and y to [0,1 ]]In between, a transition from the binary value domain to the probability domain is effected. Conversion formula is px＝(x+2k-1)/2k，py＝(y+2k-1)/2k(ii) a And the random sequence generation module converts the probability domain input data output by the normalization module into a probability domain random sequence.
The random adder proposed by the present invention has no requirement for the positions of "0" and "1" in the input sequence, and for convenience of explaining the operating principle of the input converter, the present invention converts the input data into a centrally distributed sequence, based on
Wherein L is 2kFor example, an input data converter with 3 bits of one bit width is taken as an example, the unsigned number x is 4 to 3' b100, and the length of the converted random sequence is L is 23Corresponding probability value p 8xWhen the sequence is generated in the concentrated sequence generation method, X is obtained as 4/8L＝11110000。
The function of the random adder is to implement random sequence addition operation through a series of logic operations. Assuming that the conventional binary lower-band scaling two-input adder equation is expressed as z ═ 0.5(x + y), the calculation equation based on the random sequence isThen the calculation formula at any one time is 0.5 (X)L(t)+YL(t))＝ZL(t) when XL(t)+YLWhen (t) is 0 or 2, the formula is calculated accurately. But when X isL(t)+YLWhen (t) is 1, ZLIn the conventional random adder, the value (t) is 0.5, and the value is randomly set to 0 or 1, thereby generating a calculation error. The invention adopts the mode that when X appears for the first timeL(t)+YLWhen t is 1, output ZL(t) 0, outputting the error as E (t) 1, when X appears againL(t)+YLWhen t is 1, output ZLWhere (t) is 1, the error is e (t) is 0. When X is presentL(t)+YLWhen (t) is 0 or 2, ZL(t) 0 or ZL(t) is 1, and the errors e (t) are all 0. After all digits of the two random sequences are completely calculated, Z is outputL(t) while outputting the calculated final error e (l). According to the process, the output logic expression of the random adder at any moment can be obtained as ZL(t)＝XL(t)&YL(t)|YL(t)&E(t)|XL(t)&E (t), the error logic expression is
The method can be realized by using a hardware description language in the FPGA and paying attention to the timing problem. This calculation is illustrated below, assuming that the input data x is 4 and y is 3, and the conversion is made toInput sequence XL＝11110000,YLThe output is Z as known from the above method, 11100000L1110000, E1, and sending the output result to the output converter.
The implementation of the cascade of the random adder is shown in fig. 4, when the input is multiple inputs, the cascade is implemented layer by combining the addends participating in the operation in pairs, the input and output converters share the same, the calculation output shifts the final result and each layer of error according to the number of stages, and then the final result and each layer of error are added to obtain the error-free cascade calculation result output.
As shown in fig. 5, the output converter is used to convert the computed random sequence back to the conventional binary value field and perform error compensation output; the method comprises the following steps: an accumulator and a compensation unit. The accumulator being arranged to output Z to the random adderLAnd accumulating, namely, adopting a scaling adder, so that the compensator needs to carry out left shift operation on the accumulated value and add an output error value E to obtain error-free output. As aforementioned output ZL1110000, E is 1, the output after accumulator is 3' b011 of traditional binary value domain, in compensator, two inputs have scaling adder to shift left one bit to get 3' b110, and add the output error value E to 1 to get the final output result 3' b111 to 7, which is the same as the original binary value domain a + b 4+3 to 7, and the output is error-free.
Fig. 6 is a diagram showing simulation results of an FPGA-implemented random computation-based error-free adder and a conventional binary adder, where x and y are two 16-bit input data, each computation cycle is changed once, z is a computation result of the random adder of the present invention, E is a computation result of an error bit in a computation process, and z _ true is a computation result implemented by the conventional binary adder, and the computation results have a delay of one computation cycle, which shows that the computation results are completely identical and the designed adder has no error. Compared with the traditional binary adder, the error-free adder based on random calculation provided by the invention can share the input/output converter in large-scale cascade connection, and the resource and the power consumption can be greatly reduced.
It will be appreciated by those of ordinary skill in the art that the embodiments described herein are intended to assist the reader in understanding the principles of the invention and are to be construed as being without limitation to such specifically recited embodiments and examples. Various modifications and alterations to this invention will become apparent to those skilled in the art. Any modification, equivalent replacement, or improvement made within the spirit and principle of the present invention should be included in the scope of the claims of the present invention.
Claims (10)
1. An error-free adder based on random computation, wherein "0" and "1" in the random sequence of the input random adder can be any position, and the output of the random adder comprises: the addition result and the error.
2. The random computation-based error-free adder according to claim 1, wherein when the first addition result of the two-input random adder is 1, the addition result is 0 and the error is 1; when the addition result is 1 again, the addition result is output as 1, and the error is 0.
3. An error-free adder based on stochastic computing according to claim 2, wherein the stochastic adder is a scaled adder.
4. A random computation based error-free adder according to claim 3, further comprising an output converter, the output converter comprising: the accumulator is used for converting an addition result back to a conventional binary number value and sending the addition result to the compensation unit; the compensation unit adds the error output by the random adder and the effective value output by the accumulator to obtain an error-free result.
5. An error-free adder based on random computation of claim 4, wherein the random adders are cascaded.
6. The random computation-based error-free adder according to claim 5, wherein when the random adders are cascaded, the error-free result is obtained by performing shift addition according to the number of cascaded stages where the final addition result and the error are obtained by the cascaded random adders.
7. A random computation based error-free adder according to any one of claims 4-6, further comprising: an input converter; the input converter includes: the device comprises a normalization module and a random sequence generation module, wherein the normalization module is used for converting input data into a probability domain, and the random sequence generation module converts the probability domain input data output by the normalization module into a probability domain random sequence.
8. An error-free adder based on stochastic computing according to claim 6, wherein the input converter is common to the output converter when the stochastic adders are cascaded.
9. A digital signal processing system comprising at least an error-free adder according to any of claims 1 to 8.
10. A communication system comprising at least an error-free adder according to any of claims 1 to 8.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910910312.9A CN110705196B (en) | 2019-09-25 | 2019-09-25 | Error-free adder based on random calculation |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910910312.9A CN110705196B (en) | 2019-09-25 | 2019-09-25 | Error-free adder based on random calculation |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN110705196A true CN110705196A (en) | 2020-01-17 |
| CN110705196B CN110705196B (en) | 2021-09-28 |
Family
ID=69196357
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910910312.9A Expired - Fee Related CN110705196B (en) | 2019-09-25 | 2019-09-25 | Error-free adder based on random calculation |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN110705196B (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111428196A (en) * | 2020-03-30 | 2020-07-17 | 南京大学 | Non-monotonic function approximate calculation device based on random calculation |
| CN112698811A (en) * | 2021-01-11 | 2021-04-23 | 湖北大学 | Neural network random number generator sharing circuit, sharing method and processor chip |
Citations (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20080218282A1 (en) * | 2006-07-26 | 2008-09-11 | Khurram Waheed | Hybrid Stochastic Gradient Based Digitally Controlled Oscillator Gain KDCO Estimation |
| CN104038770A (en) * | 2014-06-05 | 2014-09-10 | 中国科学技术大学 | Discrete cosine transform (DCT) implementation method and system based on randomized computation |
| CN104796111A (en) * | 2015-05-14 | 2015-07-22 | 北京航空航天大学 | Non-linear self-adaptive filter for dynamic hysteretic system modeling and compensation |
| CN105356971A (en) * | 2015-10-27 | 2016-02-24 | 电子科技大学 | SCMA decoder based on probability calculation |
| CN106603099A (en) * | 2016-12-19 | 2017-04-26 | 四川理工学院 | Single-bit receiver signal detection method based on probability calculations |
| CN106909970A (en) * | 2017-01-12 | 2017-06-30 | 南京大学 | A kind of two-value weight convolutional neural networks hardware accelerator computing module based on approximate calculation |
| CN107967132A (en) * | 2017-11-27 | 2018-04-27 | 中国科学院计算技术研究所 | A kind of adder and multiplier for neural network processor |
| EP3333735A1 (en) * | 2016-12-12 | 2018-06-13 | Fraunhofer-Gesellschaft zur Förderung der angewandten Forschung e.V. | Method and computer program for determining a placement of at least one circuit for a reconfigurable logic device |
| US20180165478A1 (en) * | 2016-12-13 | 2018-06-14 | University Of Florida Research Foundation, Incorporated | Uniquified fpga virtualization approach to hardware security |
| US20180336166A1 (en) * | 2017-05-22 | 2018-11-22 | Government Of The United States, As Represented By The Secretary Of The Air Force | Method for Predicting Stochastic Output Performance or Scaling Stochastic Inputs |
-
2019
- 2019-09-25 CN CN201910910312.9A patent/CN110705196B/en not_active Expired - Fee Related
Patent Citations (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20080218282A1 (en) * | 2006-07-26 | 2008-09-11 | Khurram Waheed | Hybrid Stochastic Gradient Based Digitally Controlled Oscillator Gain KDCO Estimation |
| CN104038770A (en) * | 2014-06-05 | 2014-09-10 | 中国科学技术大学 | Discrete cosine transform (DCT) implementation method and system based on randomized computation |
| CN104796111A (en) * | 2015-05-14 | 2015-07-22 | 北京航空航天大学 | Non-linear self-adaptive filter for dynamic hysteretic system modeling and compensation |
| CN105356971A (en) * | 2015-10-27 | 2016-02-24 | 电子科技大学 | SCMA decoder based on probability calculation |
| EP3333735A1 (en) * | 2016-12-12 | 2018-06-13 | Fraunhofer-Gesellschaft zur Förderung der angewandten Forschung e.V. | Method and computer program for determining a placement of at least one circuit for a reconfigurable logic device |
| US20180165478A1 (en) * | 2016-12-13 | 2018-06-14 | University Of Florida Research Foundation, Incorporated | Uniquified fpga virtualization approach to hardware security |
| CN106603099A (en) * | 2016-12-19 | 2017-04-26 | 四川理工学院 | Single-bit receiver signal detection method based on probability calculations |
| CN106909970A (en) * | 2017-01-12 | 2017-06-30 | 南京大学 | A kind of two-value weight convolutional neural networks hardware accelerator computing module based on approximate calculation |
| US20180336166A1 (en) * | 2017-05-22 | 2018-11-22 | Government Of The United States, As Represented By The Secretary Of The Air Force | Method for Predicting Stochastic Output Performance or Scaling Stochastic Inputs |
| CN107967132A (en) * | 2017-11-27 | 2018-04-27 | 中国科学院计算技术研究所 | A kind of adder and multiplier for neural network processor |
Non-Patent Citations (2)
| Title |
|---|
| LONG BO: "Mitigation of DC Components Using Adaptive BP-PID Control in Transformless Three-Phase Grid-Connected Inverters", 《ENERGIES》 * |
| 孟锐: "基于FPGA 的浮点运算加法器的研究", 《计算机工程应用技术》 * |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111428196A (en) * | 2020-03-30 | 2020-07-17 | 南京大学 | Non-monotonic function approximate calculation device based on random calculation |
| CN112698811A (en) * | 2021-01-11 | 2021-04-23 | 湖北大学 | Neural network random number generator sharing circuit, sharing method and processor chip |
Also Published As
| Publication number | Publication date |
|---|---|
| CN110705196B (en) | 2021-09-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Hotkar et al. | Implementation of Low Power and area efficient carry select Adder | |
| JP4290202B2 (en) | Booth multiplication apparatus and method | |
| CN112114776A (en) | Quantum multiplication method and device, electronic device and storage medium | |
| CN112698811A (en) | Neural network random number generator sharing circuit, sharing method and processor chip | |
| CN110705196B (en) | Error-free adder based on random calculation | |
| CN101140511A (en) | Cascaded carry binary adder | |
| JP3716695B2 (en) | Fast Hadamard transformer | |
| CN110377267B (en) | Signed number adder/subtracter based on probability calculation concentrated sequence | |
| CN213934855U (en) | Neural network random number generator sharing circuit based on random computation | |
| WO2020008643A1 (en) | Data processing device, data processing circuit, and data processing method | |
| CN110837624A (en) | Approximate calculation device for sigmoid function | |
| CN107092462B (en) | 64-bit asynchronous multiplier based on FPGA | |
| CN112214200A (en) | Quantum subtraction operation method and device, electronic device and storage medium | |
| Rafiq et al. | An efficient architecture of modified booth multiplier using hybrid adder | |
| CN113157247B (en) | Reconfigurable integer-floating point multiplier | |
| CN113128141B (en) | Median filtering system based on error-free random calculation | |
| Khan et al. | Design of 2× 2 vedic multiplier using GDI technique | |
| CN111897513B (en) | Multiplier based on reverse polarity technology and code generation method thereof | |
| CN115526131A (en) | Method and device for approximately calculating Tanh function by multi-level coding | |
| CN113988279A (en) | Output current reading method and system of storage array supporting negative value excitation | |
| CN116931873B (en) | Two-byte multiplication circuit, and multiplication circuit and chip with arbitrary bit width of 2-power | |
| CN115879553B (en) | Quantum modulus complete multiplication method and device and modulus arithmetic component | |
| Ram et al. | Delay Enhancement of Wallace Tree Multiplier with Binary to Excess-1 Converter | |
| CN115879552B (en) | Quantum modulus multiplication inverse operation method and device, electronic device and modulus arithmetic component | |
| Patil et al. | Design and implementation of energy efficient vedic multiplier using FPGA |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20210928 |