快速非同步平方數產生器

Abstract

平方數經常會在數學計算和影像處理中使用到。在傳統上，大都是使用乘法器來產生平方數。但是乘法器實作上複雜且處理速度較慢。而如何有效率的計算出平方數就變得十分的重要。 在1998年，謝明得 等教授在IEEE Transaction on Computers提出一個使用查表法的平方產生器 [4]，這個產生器使用簡單的加法來取代乘法，以達到加速平方數的計算。後來到2008年，又提出以遞迴方式，運用更小的table使作平方產生器 [5]。 依據前述的遞迴方式，需要作多次的加法運算。我們提出一個“快速演算法”來減少加法運算的次數，再搭配非同步加法器實作平方產生器。在TSMC 0.13製成的標準元件下實作後合成，當最佳的狀況，運用快速演算法可最高可加快18.13%。

Square number is often used in mathematical calculation and video compression. In the past, multipliers are widely needed to generate square numbers. However, multiplier is complex, hard to implement and slow. How to reduce overhead of generating square number is a very important issue. In 1998, Chin-Long Wey and Ming-Der Shieh purposed the Square generator [4]. Instead of the multiplier, a look-up table is needed to generate the square number. This method can accelerate operating speed to generate square numbers. In 2008, Tsai proposed the recursive scheme to reduce the ROM size to implement the square generator [5]. On our work, we propose the “Fast Algorithm” and implemented it with asynchronous circuits. As a result, the square generator with Fast Algorithm implemented on TSMC 0.13 is 18.13% faster in the best case than the original design.