最佳化之算術演算法及其架構設計

Abstract

在本文中，我們提出以二為基底之快速除法及開根號演算法。此演算法在 面積及速度之表現皆比現存之演算法及架構為佳。其循序架構基上包含Ｎ 個簡單的ＣＳＡ(Carry save adders)，而平行架構則包含Ｎ*Ｎ個ＣＳＡ 。此架構能在５Ｎ個ＣＳＡ時間內完成Ｎ位元除法及開根號運算，而且所 得之輸出以二進制位元數表示。再則，我們將除法及開根號運算結合一最 大位元先輸出之乘法演算法，而得最佳化之統一演算法。如此三種算術運 算可以建構成單一的算術單元，因此硬體的複雜度可以減少。由於硬體是 由具規則性電路構成，因此非常適合於ＶＬＳＩ製作。此外，亦根據所提 出之演算法，以Ｍａｇｉｃ電腦輔助設計軟體製作一２４位元除法器。 In this thesis, a fast radix-2 division and square-root algorithm are proposed. It achieves the best performance in both area and speed aspects over the existing algorithms and implementations. The proposed architecture basically consists of N simple carry-save adders ( CSAs ) for bit-serial implementation, and N*N CSAs for bit parallel implementation. It finished an N-bit division and square-root in 5N(O(N)) carry -save addition time and the result bits are in binary representation. In addition, a most-significant-digit(MSD) first multiplication is combined with the division and square- root algorithms for an optimal unified algorithm. Hence, the three operations can be constructed in a compatible arithmetic unit, which results in fast multi-function capability with least area. Since the hardware composed of highly regular cellular array, which is suitable for VLSI implementation, and the hardware implementation of 24-bit divider using "Magic" CAD tool is also presented.