一種新式角度編碼法用於快速座標旋轉處理器之設計及其應用

Abstract

在本篇論文中，我們將探討有關座標旋轉演算法的基本架構及其所演進的各種改良結構。在各種改良式的架構中，我們也將分別討論它們的各項優缺點並且加以分析。在這篇文章中，我們將重點集中在正弦和餘弦函數的探討和比較上。討論之後，我們並提出另一套的快速查表演算法，並且融入了偵測首位不為0的概念架構，使角度旋轉的收斂速度可以加快，並且設計以管線式的架構來解決非定值尺度因子的計算問題。平均而言，利用這種查表法在22位元精確度的角度旋轉中，只需要約4.107次的角度收斂旋轉和3.721次的尺度因子位移及加法運算便可以完成。而我們在使用0.35μ製程的標準電路單元合成結果發現，其電路總面積為20168.75μm2而時脈週期為7.82ns（0.35μ製程，不含唯讀記憶體且在標準模式下）。本篇論文的結構安排如下：第一章的序論中，我們簡單的介紹座標旋轉演算法的發展、各種改良方法及其應用發展。在第二章□，我們將說明座標旋轉演算法的原理及其重要的精髓，並且提出所能改良的方向。接著在第三章中，我們把最基本的改良方法及目前大家所較為採用的方法做一討論，並且歸納出他們所改進的優點及所面臨到的問題。針對大部分的研究者所面臨到的問題，我們在第四章中提出了一套改良式編碼法，及管線式電路架構來解決。我們將闡明其原理之外，並且說明此法的優點和將來可能遇到的問題。而在第五章中，我們把上述所有提到的演算法加以模擬，並計算出它們的平均轉旋次數來做比較及驗證。此外，我們用Verilog 硬体設計語言來設計整個電路，並且用Synopsys 合成工具 來對我們所設計的電路做最佳化的0.35μ製程的標準電路單元合成，然後再對它們可操作的頻率及所需要的面積做一個詳細的對照。接著，在第六章中，我們並設計出一個除法器的例子，它一樣是運用查表及偵測首位不為0的概念來加速收斂運算，我們並列出一些比較數據。最後，我們第七章做一個總結，除了對前述各章的演算法結構做一個客觀性的整理，明顯地指出它們所會面臨到的困難及所可以獲得的改進外，並更探入討座標旋轉演法未來改進的方向，及它在其它方面的應用價值。

After CORDIC (Coordinate Rotational Digital Computer) algorithm was presented by Volder in 1959, there were lots of the improved algorithms published. In this thesis, we will first review the basic CORDIC algorithm and structures, and several notable improved algorithms and architecture. We will also point out and analyze the advantages and the disadvantages of those algorithms. In particular, we will focus on the computation of the sine and cosine functions. After the survey, we will present a fast table-based angle encoding method combined with the leading-one bit detection that can greatly speed up the convergence rate of CORDIC algorithm. We also use the pipelined circuit structure to solve the problem of calculating variable scale factor, and speed up the total calculating time. In average, the total iteration number for the rotation and the scale factor compensation is about 4.107 and 3.721, for 22-bit precision. In 0.35μ processor, we get the total circuit area is 20168.75μm2, and the operation period is 7.82ns in typical corner (don't include the delay of ROM). It is to say that it can operation in 127MHz. The thesis is organized as follows. Chapter one is the introduction, including reviews and applications of the well known CORDIC algorithms. Detailed CORDIC algorithms will be introduced in chapter two, including those factors affecting its performance. After that, we will discuss some popular basic techniques for improving performance in chapter three. Their advantages and drawbacks will also be introduced. In chapter four, for solving these problems, we present a fast CORDIC algorithm, which is based on the table-based encoding algorithm, the leading-one bit detection, and the pipelined structure to speed up the total iteration rate. We will details the new CORDIC algorithm and its advantages. We then simulate the algorithms, and list the performance data for comparison and verification in chapter five. Besides, we design our processor by Verilog hardware description language, and optimize it by Synopsys synthesis tool. Then we list the total area and the operation frequency. We use the 0.35μ standard cell to synthesis the circuit. In chapter six, we demonstrate a divider design which uses the similar table-based encoding algorithm and leading-one bit detection to speed up iteration number. At last, we will draw some conclusion and list future work in chapter seven.