Karatsuba 整数乗算器のVLSI設計と評価 VLSI Design of Karatsuba Integer Multipliers and Its Evaluation

この論文にアクセスする

この論文をさがす

著者

    • 阿部 公輝 ABE Koki
    • 電気通信大学 情報工学科 Department of Computer Science, The University of Electro-Communications

抄録

Multi-digit multiplication is widely used for various applications in recent years, including numerical calculation, chaos arithmetic, primality testing. Systems with high performance and low energy consumption are demanded, especially for image processing and communications with cryptography using chaos. Karatsuba algorithm with computational complexity of <i>O</i>(<i>n</i><sup>1.58</sup>) has been employed in software for multiplication of hundreds to thousands bits, where <i>n</i> stands for bit length of operands. In this paper, hardware design of multi-digit integer multiplication based on Karatsuba algorithm is described and its VLSI realization is evaluated in terms of the cost, performance, and energy consumption. We present two design choices of the Karatsuba hardware: RKM (Recursive Karatsuba Multiplier) and IKM (Iterative Karatsuba Multiplier). We found that RKM has less area cost than WTM (Wallace Tree Multiplier) for bit length larger than 2<sup>9</sup> with area cost of 30mm<sup>2</sup>. Critical path delay of RKM is always larger than that of WTM. Therefore, we should use WTM as combinational circuits for IKM to have better cost performance. We also found that a version of IKM using 0.18<i>μ</i>m process can perform 1024-bit multiplications 30 times faster than software at the area cost of 10.9mm<sup>2</sup>. Energy for the computation by the IKM version was found to be nearly 1/600 of that consumed by general purpose processor which executes the software. The results obtained by this study will help system designers for applications requiring multi-digit multiplication to select design alternatives including ASIC realization.

収録刊行物

  • 電気学会論文誌. C, 電子・情報・システム部門誌 = The transactions of the Institute of Electrical Engineers of Japan. C, A publication of Electronics, Information and System Society  

    電気学会論文誌. C, 電子・情報・システム部門誌 = The transactions of the Institute of Electrical Engineers of Japan. C, A publication of Electronics, Information and System Society 128(2), 220-230, 2008-02-01 

    The Institute of Electrical Engineers of Japan

参考文献:  15件

参考文献を見るにはログインが必要です。ユーザIDをお持ちでない方は新規登録してください。

各種コード

  • NII論文ID(NAID)
    10021131264
  • NII書誌ID(NCID)
    AN10065950
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    03854221
  • NDL 記事登録ID
    9366735
  • NDL 雑誌分類
    ZN31(科学技術--電気工学・電気機械工業)
  • NDL 請求記号
    Z16-795
  • データ提供元
    CJP書誌  NDL  J-STAGE 
ページトップへ