矩陣特徵數分解之演算法及架構設計

Abstract

在本文中，我們首先討論現有矩陣特徵數分解（SVD）的演算法及架構。現有的演算法中，運用座標旋轉計算（CORDIC）之演算法來加速運算是最常被使用的。但座標旋轉計算是循序計算的演算法，且不適合浮點計算。本文中所提出新的演算法，主要以基本四則運算加上運用近似旋轉（approximate rotation）及查表（table look-up）的技巧，來達到適合於浮點而且快速的計算。新的演算法比傳統的以座標旋轉方法來計算矩陣特徵數分解有更高的硬體平行度及更小的面積。最後我們將對現有的演算法及提出的新演算法作比較。

In this thesis, we first discuss the existing algorithms and architectures for singular value decompoosition (SVD). The most popular technique is the coordinate rotation digital computer (CORDIC) algorithm for efficient SVD. The CORDIC algorithm is inherently sequential. Moreover, the CORDIC algorithm is hard to achieve floating-point operations. For efficient floating-point and fast computation of SVD, the new proposed applise basic arithmetic operations together with new techniques of approximate rotation and table look-up. The new design has higher parallelism and smaller area than the conventional CORDIC-based SVD processor. Finally, comparisons between the new algorithm and the existing SVD algorithms are presented.