Title:
DEVICE AND METHOD FOR FAST MULTIPLICATION
Document Type and Number:
WIPO Patent Application WO/2012/150396
Kind Code:
A3
Abstract:
The present invention relates to a method of encoding an integer number using an encoding function taking as input an integer number of n words of t bits or a multiple of t bits, and outputting an ordered array U of j rows and i columns containing integers Ui,,j. The words a[k] making up the number a are intercompared in order to organise them into a series of words having an increasing value (k=0, k=1, k=2,...). An array of indices makes it possible to conserve the rank k of the word a[k] in the ordered list. A first word of a is calculated by an equation using a group of words which are not expressed as a function of other words of a. Next, all the other words of a are calculated with the aid of an equation using already calculated words. In this way, it is possible to express a large number as an ordered series of terms having small discrepancies from one another. Such encoding makes it possible to limit the number of elementary multiplications when multiplying this number with another. The present invention also relates to the circuit implementing the encoding, as well as to a circuit implementing the multiplication of numbers thus encoded.
Inventors:
NACCACHE DAVID (FR)
SABEG KARIM (FR)
SABEG KARIM (FR)
Application Number:
PCT/FR2012/050818
Publication Date:
January 03, 2013
Filing Date:
April 13, 2012
Export Citation:
Assignee:
ALTIS SEMICONDUCTOR SNC (FR)
NACCACHE DAVID (FR)
SABEG KARIM (FR)
NACCACHE DAVID (FR)
SABEG KARIM (FR)
International Classes:
G06F7/53
Domestic Patent References:
| WO2006103601A2 | 2006-10-05 |
Other References:
PAI C-Y ET AL: "LOW-POWER CONSTANT-COEFFICIENT MULTIPLIER GENERATOR", JOURNAL OF VLSI SIGNAL PROCESSING SYSTEMS FOR SIGNAL, IMAGE, AND VIDEO TECHNOLOGY, SPRINGER, NEW YORK, NY, US, vol. 35, no. 2, 1 September 2003 (2003-09-01), pages 187 - 194, XP001178352, ISSN: 0922-5773, DOI: 10.1023/A:1023604700591
YOUFENG WU: "STRENGTH REDUCTION OF MULTIPLICATIONS BY INTEGER CONSTANTS", ACM SIGPLAN NOTICES, ACM, ASSOCIATION FOR COMPUTING MACHINERY, NEW YORK, NY, US, vol. 30, no. 2, 1 February 1995 (1995-02-01), pages 42 - 48, XP000526082, ISSN: 0362-1340, ISBN: 978-1-58113-450-6, DOI: 10.1145/199873.199880
BURNHAM J ET AL: "HIGH-PERFORMANCE MULTIPLIERS FOR XC4000E FPGAS", NEW ELECTRONICS, INTERNATIONAL THOMSON PUBLISHING, LONDON, GB, vol. 29, no. 16, 24 September 1996 (1996-09-24), pages XII - XIV, XP000641892, ISSN: 0047-9624
YOUFENG WU: "STRENGTH REDUCTION OF MULTIPLICATIONS BY INTEGER CONSTANTS", ACM SIGPLAN NOTICES, ACM, ASSOCIATION FOR COMPUTING MACHINERY, NEW YORK, NY, US, vol. 30, no. 2, 1 February 1995 (1995-02-01), pages 42 - 48, XP000526082, ISSN: 0362-1340, ISBN: 978-1-58113-450-6, DOI: 10.1145/199873.199880
BURNHAM J ET AL: "HIGH-PERFORMANCE MULTIPLIERS FOR XC4000E FPGAS", NEW ELECTRONICS, INTERNATIONAL THOMSON PUBLISHING, LONDON, GB, vol. 29, no. 16, 24 September 1996 (1996-09-24), pages XII - XIV, XP000641892, ISSN: 0047-9624
Attorney, Agent or Firm:
HERVOUET, Sylvie et al. (Le Centralis6, avenue du Général Leclerc Bourg la Reine, FR)
Download PDF:
Previous Patent: EXHAUST LINE AND VEHICLE FITTED WITH THIS LINE
Next Patent: FUEL TANK FOR DIESEL ENGINE
Next Patent: FUEL TANK FOR DIESEL ENGINE