16-bit Micro-Pipelined Radix-II CORDIC Cores: Design and Implementation

Abstract

Micro-processors are complex electronic systems acting as the control and processing center for the machine they are embedded inside, hence, acting as their brain for the body. But, military grade processors are in a totally different league, other than being way more precise in precision and calculations, they are comparably faster than the general purpose micro-processors and DSP’s available in the general market due to their sole purpose of acting for a specific application or task, hence acting as an Application Specific Integrated Circuit (ASIC).

This paper presents the full design methodology for two 16-bit multi-cycle micro-pipelined microprocessor cores in VLIW architecture, which can function as parallel co-processors in a single microprocessor or as independent microprocessors. Both processors are built using the Built-in-self-test (BIST) using VHDL in Xilinx ISE Design Suite 14.1.

Most importantly, this paper presents a new approach generic approach for all the radix in the Cartesian, Polar, Cylindrical, Circular and Homogenous system of co-ordinates respectively and a new approach for rotation and vectorising modes to compensate for the changing and non-constant multi and scalar factors by use of signed digits along with competitive behavior in between adders and shifters.

The proposed approach requires the use of micro-pipelining along with an SIMD natured ISA.

Also, the results of using VLIW architecture, multi-cycle data-path along with the concept of IOPS on processors with a smaller precision order of 16-bit or lower and how the performance results indicate the greater performance and precision as compared to larger precision 32-bit and 64-bit processors.

Introduction

Application Specific Integrated Circuits (ASIC) are application specific and oriented micro-processors. These complex electronic systems are used for processing and control of complex machines requiring very fast and specific precision results to perform the required task. COordinate Rotation Digital Computer (CORDIC) are ASIC used for high precision calculations of co-ordinates, exponential, logarithmic, general arithmetic and floating point calculations. In this context, this paper describes the full design methodology for a Single Instruction Multiple Data (SIMD) and VLIW architecture based multi-cycle micro-pipelined microprocessor cores for CORDIC. The overall processor has been segmented to provide two individual microprocessor cores, the reason for which is explained later in the results.

The first core is used for co-ordinate calculations whereas the second core is used for corresponding sine, cosine, logarithmic, exponential calculations and other complex mathematical calculations for successful completion of the desired task.

In this paper, Section-II describes required mathematical equations for the respective modes for both the cores, Section-III describes the Finite State Machines (FSM) for the control unit, Section-IV describes the co-ordinate processing core, Section-V describes the complex mathematical calculation core, Section-VI shows the simulation results along with core properties and finally Section-VII includes the conclusion and preferable application areas.

Supporting Mathematics for CORDIC or Volder’s Algorithm

Review

CORDIC or Volder’s algorithm is a type of digit by digit algorithm i.e. it converges the obtained result by a single or more number of depending on the order or radix. It is also included in shift and add algorithms as it merely uses addition, subtraction, lookup-table and bit shift operations to perform pseudo multiplication, division and factor combining to achieve the desired result.

This algorithm can be applied for operations of complex nature in Cartesian, cylindrical, circular, and homogenous co-ordinate system to perform hyperbolic, trigonometric, logarithmic, basic arithmetic and exponential calculations.

Working

CORDIC algorithm works by following steps:

• Decomposes the desired rotation angle into the weighted sum of a set of predefined elementary rotation angles depending on the radix or order.
• The rotation through each of them can be accomplished with simple shift-add or shift-subtract operations.

Xn = X0 cos (ø) – Y0 sin (ø)

Yn = Y0 cos (ø) + X0 sin (ø)

The basic rotator gives the rotated co-ordinates as:

X’ = X cos (ø) – Y sin (ø)

Y’ = Y cos (ø) + X sin (ø)

Which can be rewritten as follow:

X’ = cos ø. [X - Y tan ø]

Y’ = cos ø. [Y + X tan ø]

By letting x’ and y’ be calculated iteratively, we can define the angle to be taken in each iteration as:

Tan (ø) = +2-i

= -2-i

Thus, for every “i” iteration we have:

Xi+1 = Ki [Xi – Yi. Di. 2-i]

Yi+1 = Ki [Yi + Xi. Di. 2-i]

Where,

Ki = cos (tan-1 2-i)

= 1 / √ (1 + 2-i)

= (√ (1 + 2-i))-1

Di = +1

= -1

And the calculated angle for each iteration is

Zi+1 = Zi – Di. Tan-1 (2-i)

Implementation

The implementation of the algorithm requires presences of following two modes respectively, the need for which is explained in the section containing the FSM.

• Vector Mode
• Rotation Mode
• Vector Mode

This mode is particularly used initially to find the set of initial co-ordinates desired or set to achieve and convert them to corresponding vector notation and perform general arithmetic or to send for processing by the next core in rotation mode.

Eq.s for Vector Mode

Xi+1 = Xi – Yi. Di. 2-i

Yi+1 = Yi + Xi. Di. 2-i

Zi+1 = Zi – Di. Tan-1 (2-i)

Where Di = +1 if Yi < 0

= -1 otherwise

Then:

Xn = An√ [(X0)2 + (Y0)2]

Yn = 0

Zn = Z0 + tan-1 (Y0 / X0)

An = ∏n √ (1 + 2-2i)

Rotation Mode

This mode is particularly used for performing the required mathematical calculations be it trigonometric, hyperbolic, arithmetic, logarithmic or exponential on the acquired sets of vectors to achieve the desired result.

Eq.s for Rotation Mode

Xi+1 = Xi – Yi. Di. 2-i

Yi+1 = Yi + Xi. Di. 2-i

Zi+1 = Zi – Di. Tan-1 (2-i)

Where Di = +1 if Yi < 0

= -1 otherwise

Then:

Xn = An [X0 cos Z0 – Y0 sin Z0]

Yn = An [Y0 cos Z0 – X0 sin Z0]

Zn = 0

An = ∏n √ (1 + 2-2i)

Mathematical Core

The mathematical core is responsible for computing complex mathematical calculations of hyperbolic, trigonometric, arithmetic, logarithmic and exponential nature. Since, it is involved in such complex calculations, it too requires multiple data entities at the same time which may be present in the form of complex numbers, or some other mathematical form and hence it too uses a micro-pipelined structure with a multi-cycle data-path.

The designed core find its applications in aerospace and military processing cores as they require calculations of complex nature where the input present might not be available in the desired format, in such a situation, the designed core or cores of such nature provides results of much greater precision and that too at the required rate and speed.

Conclusion

This paper concludes and provides design methodologies for improving and getting the maximum throughput from the microprocessors present in today’s market and also reducing the net time to market or finished product as a consequence of rapid prototyping.

The proposed methodology of SIMD nature, VLIW architecture, micro-pipelining, multi-cycle data-path, multiple IOPS and increased CPI, all these characteristics are applied with the aim to find its applications in ASIC and FPGA cores, within specific industries like aerospace, military, artificial neural networks and other high precision speed calculation industries requiring parallel processing concepts, and development of the ideal cores which lacked the technology at their respective times.

References

1. J. E. Volder, “The CORDIC trigonometric computing technique,” IRE Trans. Electron. Comput., vol. EC-8, pp. 330–334, 1959.
2. J. C. Chih and S. G. Chen, “A fast CORDIC algorithm based on a novel angle recoding scheme,” in Proc. 2000 IEEE Int. Symp. Circuits Syst., vol. 4, pp. 621–624.
3. C. S. Wu and A. Y. Wu, “Modified vector rotational CORDIC (MVRCORDIC) algorithm and architecture,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process. vol. 48, no. 6, pp. 548–561, Jun. 2001.
4. A. Y. Wu and C. S. Wu, “A unified view for vector rotational CORDIC algorithms and architectures based on angle quantization approach,” IEEE Trans. Circuits Syst. I, Fundam. Theory Appl., vol. 49, no. 10, pp. 1442–1456, Oct. 2002.
5. C. S. Wu, A. Y. Wu, and C. H. Lin, “A high-performance/low-latency vector rotational CORDIC architecture based on extended elementary angle set and trellis-based searching schemes,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 50, no. 9, pp. 589–601, Sep. 2003.
6. Y. H. Hu, “The quantization effects of the CORDIC algorithm,” IEEE Trans. Signal Process., vol. 40, no. 4, pp. 834–844, Apr. 1992.
7. A. M. Despain, “Fourier transform computers using CORDIC iterations,” IEEE Trans. Comput., vol. 23, no. 10, pp. 993–1001, Oct. 1974.
8. M. D. Ercegovac and T. Lang, “Redundant and on-line CORDIC: Application to matrix triangularization and SVD,” IEEE Trans. Comput., vol. 39, no. 6, pp. 725–740, Jun. 1990.
9. G. J. Hekstra and E. F. A. Deprettere, “Fast rotations: Low-cost arithmetic methods for orthonormal rotation,” in Proc. 13th IEEE Symp. Comput. Arithmetic, 1997, pp. 116–125.
10. M.Jun, K.K.Parhi, and E.F.Deprettere, “Annihilation-reordering lookahead pipelined CORDIC-based RLS adaptive filters and their applicationtoadaptivebeamforming,”IEEETrans.SignalProcess., vol.48,no. 8, pp. 2414–2431, Aug. 2000.
11. E. G. Gilbert and S. M. Hong, “A new algorithm for detecting the collision of moving objects,” in Proc. 1989 fEEE In/. Conf: Robotics Automat., May 1989, pp. 8-14.
12. S. Bonner and R. B. Kelley, “A novel representation for planning 3-D collisin-free paths,” IEEE Trans. Syst., Man, Cyhern., vol. 20. no. 6, pp. 1337-1351, Nov./Dec. 1990.
13. T. Lozano-PCrez, “A simple motion-planning algorithm for general robot manipulators,” IEEE J. Roboticx Automat., vol. RA-3. no. 3, pp. 224-238, June 1987. 141 M. Kameyama, T. Matsumoto, H. Egami, and T. Higuchi, ”lmple- mentation of a high performance LSI for inverse kinematics compu- tation,” in Proc. 1989 IEEE 1nr. Conf Rohoricc Automat.. May 1989,
14. J. E. Volder, “The CORDIC trigonometric computing technique.“ IRE Trans. Electron. Coniput., vol. EC-8, pp. 330-334, Sept. 1959.
15. J. S. Walther, “A unified algorithm for elementary functions.” in Proc. 1971 AFIPS Spring Joint Comput. Conf:, pp. 379-385.
16. G. L. Haviland and A. A. Tuszynski, “A CORDIC arithmetic pro- cessor chip,” IEEE Trans. Comput., vol. C-29. pp. 68-79. Feb. 1980.
17. T. W. Curtis, P. Allison, and J. A. Howard, “A CORDIC processor for laser trimming,” fEEE Micro, vol. 6, pp. 61-71, June 1986.
18. C. S. G. Lee and P. R. Chang, “A maximum pipelined CORDIC architecture for inverse kinematic position computation,” fEEE J. Robotics Automat., vol. RA-3, no. 5, pp. 445-458. Oct. 1987.