DocumentCode
2267669
Title
Generalized signed-digit multiplication and its systolic realizations
Author
Hung, Ching Yu ; Parhami, Behrooz
Author_Institution
Dept. of Electr. & Comput. Eng., California Univ., Santa Barbara, CA, USA
fYear
1993
fDate
16-18 Aug 1993
Firstpage
1505
Abstract
A generalized signed-digit (GSD) number system is a fixed-radix number system, with radix r and digit set {-α, -α+1, ..., β-1, β}, where α⩾O, β⩾0, and α+β+1>r. The redundancy of GSD number systems allows digit-parallel addition, based on which linear-time algorithms for multiplication are devised. Systolic and semisystolic schedules derived from these algorithms lead to the design of one-dimensional and two-dimensional array multipliers that have O(n) latency for n-digit operands
Keywords
computational complexity; digital arithmetic; redundant number systems; systolic arrays; O(n) latency; digit-parallel addition; fixed-radix number system; generalised signed-digit multiplication; linear-time algorithms; n-digit operands; one-dimensional array multipliers; redundancy; semisystolic schedules; systolic realizations; two-dimensional array multipliers; Algorithm design and analysis; Arithmetic; Concurrent computing; Delay; Design methodology; Processor scheduling; Scheduling algorithm; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1993., Proceedings of the 36th Midwest Symposium on
Conference_Location
Detroit, MI
Print_ISBN
0-7803-1760-2
Type
conf
DOI
10.1109/MWSCAS.1993.343400
Filename
343400
Link To Document