Name
Abstract | ||
|---|---|---|
The divide-and-conquer method is efficiently used in parallel multiplier over finite field GF(2n). Leone proposed optimal stop condition for iteration of Karatsuba-Ofman algorithm (KOA). Multi-segment Karatsuba method (MSK) is proposed by Ernst et al. In this paper, we propose a Non-Redundant Karatsuba-Ofman algorithm (NRKOA) with removing redundancy operations, and design a parallel hardware architecture based on the proposed algorithm. Comparing with existing related Karatsuba architectures with the same time complexity, the proposed architecture reduces the area complexity. The proposed NRKOA multiplier has more efficient the space complexity than the previous KOA multipliers, where n is a prime. Furthermore, the space complexity of the proposed multiplier is reduced by 43% in the best case. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11556992_21 | ISC |
Keywords | Field | DocType |
proposed multiplier,parallel multiplier,non-redundant karatsuba-ofman algorithm,efficient architecture,proposed nrkoa multiplier,area complexity,karatsuba-ofman algorithm,proposed algorithm,time complexity,space complexity,proposed architecture,finite field,hardware architecture,optimal stopping,divide and conquer | Prime (order theory),Finite field,Computer science,Algorithm,Circuit design,Multiplier (economics),Redundancy (engineering),Time complexity,Karatsuba algorithm,Hardware architecture | Conference |
Volume | ISSN | ISBN |
3650 | 0302-9743 | 3-540-29001-X |
Citations | PageRank | References |
5 | 0.49 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nam Su Chang | 1 | 21 | 4.29 |
| Chang Han Kim | 2 | 69 | 8.48 |
| Young-Ho Park | 3 | 137 | 16.79 |
| JongIn Lim | 4 | 819 | 75.16 |