Generalized signed-digit multiplication and its systolic realizations
Ching Yu Hung, Behrooz Parhami · 2002
A generalized signed-digit (GSD) number system is a fixed-radix number system, with radix r and digit set {-/spl alpha/, -/spl alpha/+1, ..., /spl beta/-1, /spl beta/}, where /spl alpha//spl ges/O, /spl beta//spl ges/0, and /spl alpha/+/spl beta/+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.>