Split radix multiplication

Details Split radix multiplication Split radix multiplication

2008-01-08

2008-01-08

Mai, Tan V. (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

10701634

ABSTRACT:
A first number is multiplied by a second number, by representing the first number as a first set of one or more W-bit wide numbers, and representing the second number as a second set of one or more W-bit wide numbers. Each of the W-bit wide numbers from the first set is paired with each of the W-bit wide numbers from the second set. For each pair of W-bit wide numbers, a set of sub-partial products is generated. Combinations of the sub-partial products are formed such that each combination is representable by a W-bit wide lower partial product and a carry out term that has fewer than W bits. The W-bit wide lower partial products and the carry out terms are combined to form the product of the first number and the second number. The carry out term is advantageously representable by (W/2)+1 bits.

REFERENCES:
patent: 3777130 (1973-12-01), Croisier et al.
patent: 4965762 (1990-10-01), Williams
patent: 5200912 (1993-04-01), Asgher et al.
patent: 5442799 (1995-08-01), Murakami et al.
patent: 5586070 (1996-12-01), Purcell
patent: 5751622 (1998-05-01), Purcell
patent: 5764558 (1998-06-01), Pearson et al.
patent: 5999959 (1999-12-01), Weng et al.
patent: 6286024 (2001-09-01), Yano et al.
patent: 6523055 (2003-02-01), Yu et al.
patent: 6915322 (2005-07-01), Hong
patent: 7062526 (2006-06-01), Hoyle
patent: 7111155 (2006-09-01), Anderson et al.
patent: 2003/0018678 (2003-01-01), Matula et al.
patent: WO 01/76131 (2001-10-01), None
Booth, A.D., “A signed binary multiplication technique,”Quarterly Journal of Mechanics and Applied Mathematics,vol. 4, pp. 236-240, 1951.
Rubinfield, L.P., “A proof of the modified Booth algorithm for multiplication,”IEEE Transactions on Computers,Oct. 1975.
Wallace, C., “A suggestion for a fast multiplier,”IEEE Transactions on Electronic Computers,vol. EC-13, Feb. 1964.
Peled, A. and Liu, B., “A new hardware realization of digital filter,”IEEE Transactions on Acoustics, Speech, and Signal Processing,vol. ASSP-22, No. 6, Dec. 1974.
Berkeman, A. et al., “A low logic depth complex mutliplier using distributed arithmetic,”IEEE Journal of Solid-State Circuits,vol. 35, No. 4, pp. 656-659, Apr. 2000.
Berkeman, A. and Öwall, V., “Co-Optimization of FFT and FIR in a Delayless Acoustic Echo Canceller Implementation,”Proceedings of ISCAS 2000,Geneva, Switzerland, May 2000.
Berkeman, A. and Öwall, V., “Efficient implementation of an FFT-FIR structure using a distributed arithmetic multiplier,” submitted toIEEE Transactions on Very Large Scale Integration(VLSI)Systems.
Montgomery, P.L., “Modular multiplication without trial division,”Mathematics of Computation,vol. 44, No. 170, pp. 519-521, Apr. 1985.
Dussé, S.R. and Kalinski, Jr., B.S., “A cryptographic library for the Motorola DSP56000,” inEurocrypt,1990.
Wei, S. and Shimizu, K., “Residue Arithmetic Multiplier Based on the Radix-4 Signed-Digit Multiple-Valued Arithmetic Circuits”Proceedings of 12thInternational Conference on VLSI Design,pp. 212-217, Jan. 1999.
Argüello, F. and Zapata, E.L., “Constant Geometry Split-Radix Algorithms”J. VLSI Signal Processing,vol. 10, No. 2, Jul. 1995, pp. 117-126.
PCT International Search Report, dated Feb. 17, 2005, in connection with International Application No. PCT/EP2004/012366.
PCT Written Opinion, dated Feb. 17, 2005, in connection with International Application No. PCT/EP2004/012366.
Chang, Y-N et al., “Design and Implementation of Low-Power Digit-Serial Multipliers,”Proceedings of the International Conference on Computer Design. VLSI in Computers and Processors.ICCD '97, Austin, TX, Oct. 12-15, 1997, Los Alamitos, CA. IEEE, US, Oct. 12, 1997, pp. 186-195, XP000799861.
Ashur, A.S. et al., “Systolic Digit-Serial Multiplier,”IEEE Proceedings: Circuits Devices and Systems, Institution of Electrical Engineers,Stenvenage, GB, vol. 143, No. 1, Feb. 1, 1996, pp. 14-20, XP000556001.

Affiliated with

Also associated with

Rating

Split radix multiplication does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Split radix multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Split radix multiplication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3954883