A hardware algorithm for computing sine and cosine using redundant binary representation
Naofumi Takagi, Tohru Asada, Shuzo Yajima · Systems and Computers in Japan · 1987
Abstract A hardware algorithm for computing sine and cosine using redundant binary representation for internal computations is proposed. This paper considers the computation of sine and cosine of angle tH (0; 4) (rad). Our hardware algorithm is a modification of the CORDIC method, and considers gradual rotation of a point on plane orthogonal coordinates about the origin. Sinecosine are calculated by iteratively computing coordinates of the point. The sequences of numbers representing X‐ and Y‐coordinates of the point rotated and the remaining angle of rotation are expressed by a redundant binary representation, where each digit of number is an element of {‐1, 0, 1}. The direction of rotation at each step is determined based on the upper 3 digits of the remaining angle, and all the internal computations are done in the redundant binary number system. Since parallel addition and subtraction of two numbers by a combinational circuit can be done in a fixed time regardless of the number of digits in the redundant binary number system, the computation for one step can be done in a fixed time. Following this algorithm, n‐bit computation of sine‐cosine by a combinational circuit can be done in the computation time proportional to n and with the number of elements proportional to n2. Since the computation time proportional to at least n log n is required in the existing hardware algorithm based on the CORDIC method, our algorithm is more advantageous as the bit length increases. Moreover, faster computation can be done with about the same number of elements for practical bit lengths.