Chinese Journal of Computers   Full Text
Title	A Two-Step CORDIC Rotation Algorithm with Pre-Coded Scale Factors
Authors	MOU Sheng-Mei1) YANG Xiao-Dong2)
Address	1)(Department of Computer Engineering, Naval University of Engineering, Wuhan 430033) 2)(School of Computer Science, National University of Defense Technology, Changsha 410073)
Year	2011
Issue	No.4(729—737)
Abstract &   Background	Abstract CORDIC algorithm has been widely used for efficient implementation of vector rotation operations in hardware. However, it’s hard to achieve small iteration numbers while not compromising the ease of scale factor computing and compensation. This paper proposes a novel table-driven CORDIC rotation algorithm with predictable scale factors and short pipelines. It maps the input angle during ［-π,π］ into ［0,π/4］ and generates signals to modify the initial iteration value and control the rotation direction. The rotation process is composed of two steps. The coefficients and scale factors of step1 are acquired through lookup table indexed by the MSB (Most Significant Bits) of the mapped angle. After large-angle rotations of step1, the residual angle is brought into the convergence region of step2. The iteration of step2 is scaling-free, with the coefficients directly gotten from the binary representation of the residual angle. During such two processes, no further arithmetic computation in the angle approximation (z datapath) and scale factor computing datapath is required. The coefficients of step1 are generated by our angle decomposition algorithm, with two coefficients in one group, at most one non-zero value each group, and the scale factors are pre-computed and coded with radix-4 Booth recoding algorithm. In addition, some adjacent simple micro rotations are combined into one. All these techniques effectively reduce the iteration number, which is also beneficial to high accuracy due to less rounding errors. Moreover, the algorithm uses carry-save adders to accumulate three operands and omits expressions of machine zero, which reduces the latency and complexity of the system greatly. The MSB indexed lookup table gets over the poor scalability of full-word indexed lookup table, and entries grow slowly with accuracy. When using 28-bit datapath, the algorithm requires 38% less pipeline stages and 27.9% less area consumption compared to those of the conventional CORDIC, while achieving 3 more bits accuracy, which shows great performance superiority. Keywords vector rotation; CORDIC algorithm; lookup table; scaling free; angle recoding Background CORDIC algorithm has been widely used in digital signal processing, scientific computing and other applications for efficient implementation of vector rotation operations in hardware. Lookup table is usually used to provide coefficients (rotation direction) and scale factors in applications with predictable rotation angles; however, it’s seldom used in those applications with flexible rotation angles due to its poor scalability. Instead, coefficients must be computed dynamically through the angle approximation datapath (z datapath). Conventional CORDIC are attractive with constant scale factors, but are slow as a result of its large iteration numbers. Some other modified algorithms bypass unnecessary iterations by permitting coefficient dito equal zero but bring the side effect of variable scale factors, which have to be computed dynamically. In addition, these algorithms can’t decrease the length of pipeline efficiently because of unpredictable zero positions. Stuck in such dilemma, illuminated by scaling-free CORDIC algorithm, the authors propose 2S-PCS algorithm. It integrates conventional CORDIC with scaling-free CORDIC, which makes it possess predictable scale factors as conventional CORDIC, easily gotten coefficients, and reduced non-zero coefficients on constrained positions. It’s a great deal of area conservation without the cost of computing coefficients and scale factors. The short pipeline is also beneficial to high accuracy. Experiments and theoretical analysis testify that 2S-PCS algorithm excels in vector rotation with less area consumption, short latency and high accuracy.