KR19990085924A - Trigonometric function generator and method - Google Patents

Abstract

The trigonometric function generator includes a register for separating input angle data into upper θ _M data and θ _L data, a table storing Kcosθ _M and Ksinθ _M values, and outputting data corresponding to θ _M data, It is composed of operation blocks corresponding to the number of times of conversion, and it combines multiple blocks into one pipeline stage and connects one register for each stage.The output angle data of the memory is output by the θ _L data for one input of any cycle. It consists of a pipelined codec that generates a trigonometric function by performing the operation of, storing it in a register and passing it to the next step in the next cycle.

Description

Trigonometric function generator and method

The present invention relates to an apparatus and method for generating a trigonometric function, and in particular, an apparatus capable of generating a desired angle by rotating and moving a vector on plane coordinates and generating a trigonometric function by constructing sine and cosine values in parallel with the coordinates of the vector. And to a method.

In general, a trigonometric generator for generating a triangular function (Sinusoid) is used to generate a carrier waveform to be multiplied by the input signal passed through the sampling stage in the mobile communication system. Herein, it is assumed that the mobile communication system is a software radio system, and the software radio system refers to a communication system that converts a signal of an intermediate frequency stage into digital data and processes the signal. At this time, since the speed of the input signal is 50Msps (sample per second) or more, the trigonometric function generator operates at a high frequency of 50MHz or more according to the speed, and the sine and cosine function values are applied once every 2ns or less. Must be created.

Looking at the hardware implementation of the trigonometric values announced so far, it can be divided into three types as follows. The three types of trigonometric methods are a method using a coordinated rotation digital computer algorithm, a method using a polynomial approximation method, a method using a ROM table, and the like. The conventional methods for generating the trigonometric functions are variations of these three basic methods or consist of a combination thereof.

First, we look at the Coordinate Rotaiton Digital computer (hereinafter referred to as CORDIC) algorithm. The CORDIC basically converts a vector on plane coordinates to a desired angle by using a linear transformation to obtain a sine value and a cosine value using the coordinates of the vector. J. E. Volder [J. E. Volder, "The CORDIC Trigonometric Computing Technique", IRE Trans. on Electron. Computers EC-8, Sep. 1959, pp. 330-334 and J. S. Walter [J. S. Walter, "A Unified Algorithm for Elementary Functions", Spring Joint Computer Conf. Proc. 38, 1971, pp. 379-385.] 2.1 CORDIC (Coordinate Rotation DIgital Computer). However, the above CORDIC algorithm does not rotate the vector to the desired angle at once, but selects a special rotation angle to simplify the calculation of the rotational movement (only one pair of adders and shifts are needed). You can do it many times repeatedly to get closer to the angle you want. However, the CORDIC algorithm is to calculate the value of the basic function of the basic elements by using a small amount of hardware iteratively, it is not suitable for high speed because it is essentially an iterative method.

Secondly, the polynomial approximation method is a method of obtaining a polynomial that approximates the sine and cosine functions obtained by the Taylor series or the Remez algorithm. Approxiamtions, Jonh Wiley & Sons, 1968. However, in order to obtain an output value having a precision of about 16 bits by the above method, about 10 multiplications and additions are required, which causes a large overhead in terms of speed and chip area. Therefore, if the rational expression is used instead of the polynomial, the number of multiplications and additions can be reduced and the same precision can be obtained, which requires a more time-consuming division.

The third method of using the ROM table is to store all the function values in the ROM table and read and output the contents of the ROM using the input values as addresses. PTPTang [Table-Lookup Algorithms for Elementary Functions and Their Error Analysis ", Proc. Of 10 ^th Symp. On Computer Arithmetic, 1991, pp.232-236], etc. The method using the ROM table only reads the value calculated in advance, so the accuracy is high and the speed is high. It is also fast, but there is a problem that a ROM that requires a very large area is required.

Accordingly, an object of the present invention is to provide an apparatus and a method capable of generating a triangular function of high speed with a simple structure.

Another object of the present invention is to provide an apparatus and method capable of generating trigonometric functions at high speed by implementing a parallel structure generator using a CORDIC algorithm.

It is still another object of the present invention to provide an apparatus and a method for quickly generating a trigonometric function with a simple structure by eliminating the addition and subtraction of an angle required for a CORDIC algorithm using a ROM table, and by shortening the parallel stage length.

The trigonometric function generating device according to the embodiment of the present invention for achieving the above object, the register to separate the input angle data into the upper θ _M data and θ _L data, and stores the Kcos θ _M and Ksin θ _M value table and an operation block corresponding to the memory, the iteration number of times for outputting the data corresponding to θ _M data and enclosed in a multiple block pipeline stage by the θ _L data as a structure for connecting one of the register at each stage The output angle data of the memory is composed of a codec of a pipeline structure that generates a trigonometric function by performing a step operation on an input of an arbitrary cycle, storing the result in a register, and transferring the next step in the next cycle. It is done.

1 is a diagram for explaining a CORDIC algorithm.

2 is a diagram showing the configuration of a CORDIC implementation using a simple one operation block

3 is a diagram showing the overall block configuration of a parallel CORDIC;

An embodiment of the present invention is to provide an apparatus and method for generating a trigonometric function at a high speed by implementing the CORDIC algorithm in a pipeline (pipeline) structure. The problem in implementing the parallel structure is the transfer speed of the carry of the addition used in each stage. In the embodiment of the present invention, the compressor (4-2) is a kind of a ROM table and a carry save adder. Compressors were used to ensure no carry was passed except at the last stage. The ROM table used in the embodiment of the present invention has a very small number of entries (about 32), which eliminates the angle addition and subtraction required for the original CORDIC algorithm, and the parallel stage length. It performs two functions that make it short and saves hardware.

First, the CORDIC algorithm will be described.

1 is a diagram for explaining a CORDIC algorithm.

2A and 2B of FIG. 2 show a configuration in which CORDIC is implemented using one operation block. Referring to 2a of FIG. 2, the X register 211 inputs the output of the adder 219 and the Y register 213 inputs the output of the adder 221. The shifter 215 inputs and shifts the output of the Y register 213, and the shifter 217 inputs and shifts the output of the X register 211. The adder 219 adds an output of the X register 211 and an output of the shifter 215. The adder 221 adds and outputs the output of the Y register 213 and the output of the shifter 217. Referring to 2b of FIG. 2, the register 232 stores the output of the adder 234, and the adder 234 adds or subtracts α _i according to the output of the register 232 and the presence or absence of rotational movement.

First, a linear transformation of rotating an arbitrary vector P = (x, y) by an angle α about an origin can be expressed by Equation 1 below.

However, when α is set to a special angle of tan ⁻¹ (2 ⁻¹ ) in Equation 1, Equation 1 is expressed as Equation 2 below.

The <Equation 2> is multiplied with a binary number from 2 ^-i In fact, since you only need to shift to the right as well as to carry out the multiplication i bits, except for the cosα, which is multiplied by the shift and add (add & shift) calculated only operation Can be. That is, x " can be obtained by subtracting y from y by shifting to the right by i bits, and y " can be obtained by adding y to shifting x to the right by i bits.

The CORDIC algorithm uses tan ^-1 (2 ^-0 ), tan ^-1 (2 ^-1 ), .. tan if an angle θ is given as an input using this, as shown in 2a and 2b of FIG. ^Add or subtract ^-1 (2 ^-n ), sequentially or subtracting (x, y) by α _i = tan ^-1 (2 ^-i ) or -α _i (but not multiplying cosα _i ) ) will be. Then, tan ⁻¹ (2 ⁻ⁱ ) becomes closer to 0, and the sum of the angles rotated as shown in FIG. 1 becomes closer to θ. Then, if the first vector is (x, y) = (1,0) and the angle is 0 and the size is 1, then the last vector's angle is θ and the magnitude is 1 divided by cosα _i . So release in the first (x, y) for _{(K = cosα 0 cosα 1 ...} cosαn, 0), the final vector is the angle θ size of 1 vector is a (cosθ, sinθ) cosθ we want the sinθ value You will get And whether to move rotated by α _i -α _i by determination of whether to simply (a result of the calculation to subtract the α _i from θ i-1 times) θ _i-1, except that the α _i is greater than zero and less more You can decide to.

Herein, the operation of a pipelined CORDIC having a parallel structure according to an embodiment of the present invention will be described.

As described above, the trigonometric function generator according to the embodiment of the present invention should be able to give one output in one cycle while operating at a frequency of 50 MHz or more. The CORDIC uses only simple shifts and additions, but it must use a single block of operations repeatedly. In addition, the CORDIC is characterized in that the precision of the output value is increased by one bit each time the iteration is performed once. That is, iterating over the number of bits of the output must be repeated, so it is impossible to give one output per cycle.

Thus, the trigonometric function generator according to the embodiment of the present invention uses a ROM table and a pipelined structure so that it takes several cycles until one input is input and the output is output, but each output interval is one cycle. .

The θ is divided by the upper few bits θ _M and the lower θ _L, and the θ _M is accessed by reading a ROM table storing a value of (x, y) = (Kcosθ _M , Ksinθ _M ) in advance, and reading the value. Rotate the (X, Y) value by θ _L using the CORDIC of the pipeline structure. The CORDIC of the pipeline structure constitutes as many operation blocks as the number of repeated iterations of the CORDIC, and consists of a structure in which several blocks are grouped into one pipeline stage and one register is included in each stage. After calculating one step for a certain input in one cycle, it is stored in a register, and the next cycle calculates the information stored in the register to the next step and calculates the new next input at the end of the calculation. As a result, one output can be output per cycle.

However, even when using the CORDIC of the pipeline structure as described above, the addition must be performed in the calculation of (x, y) and the comparison operation must be performed in the calculation of θ ₁ . It takes a lot of time. So, when calculating the value of (x, y), the values generated along the way are removed by 4-2 compressor which is a kind of carry storage adder to remove carry transfer and carry look-ahead adder only at the last stage. adder is used to quickly perform carry-adding.

In the calculation of the value of θ, in the original CORDIC, it is necessary to compare whether θ is greater than or less than zero for each iteration, but in the CORDIC of the pipeline structure, it is not actually compared. One of the properties of the CORDIC algorithm is that for the latter two-thirds of the entire iterations, the i-th CORDIC iteration direction is equal to the i-1 th bit of the angle at which the rotational movement of the preceding one-third is made. If you replace the previous one-third iteration with the value stored in the ROM table, the iteration direction in the pipeline simply looks at the lower two-thirds of the first input angle without adding or subtracting angles. 1 can be determined in the + direction and 0 can be determined in the-direction.

However, one entry in the ROM table is not very wide, but each time the number of bits in the address increases, the number of entries doubles, and the 4-2 compressor occupies a large area, but each time the number of input bits increases. Increases linearly. Therefore, how many bits each of θ _M and θ _L is important for minimizing the area. If the input is 16 bits, there is no problem because the area is minimized when θ _M is slightly larger than approximately 1/3 of the total.

By using the CORDIC of the pipeline structure as above, it is possible to make a trigonometric function generator that outputs one output per cycle while operating at 50MHz or more with only a few ROMs and a few stage adders and registers, rather than a complete ROM table. .

FIG. 3 illustrates an example in which a trigonometric generator designed using CORDIC of a ROM table and a pipeline structure is actually modeled at the register transfer level (RTL) level (C ++ language modeling) according to an embodiment of the present invention. Then, this trigonometric generator is simulated to perform error analysis.

Referring to FIG. 3, although the basic specifications such as the number of bits required for the current input and output are not clearly determined, first, the circuit is assumed assuming that the input angle is 16 bits and the output sine and cosine functions are 16 bits. Implemented. If the specifications are different, the size of the ROM table 316 and the number of CORDIC stages 320 and 324 having the pipeline structure are not only changed, but the overall structure may be changed.

The trigonometric function generator implemented as described above accesses the ROM table 316 with the upper 5 bits of the 16-bit angle as shown in the register 312, and determines the direction of 11 times of CORDIC iteration using the lower 11 bits. In the pipeline stage, the ROM table is accessed in the first stage and four CORDIC iterations are performed in each stage in stages 2-4. In the last five steps, the carry is added. The output is 16 bits, but the intermediate calculations are performed at 21-bit precision to get the last bit correctly. This allows two ²⁵ entry × 21 bit ROM tables, 11 pairs of 21 bit 4-2 compressors, 6 registers, and a 16-bit carry-select adder to add carry and sum at the end. As a circuit containing two carry-select adders, a trigonometric generator using pipelined CORDIC is implemented.

In the circuit modeled with the above specification, the simulation shows that the angle q in the range of 0 <q <p / 2 in 16 bits is inputted, and the values obtained by the simulation and the value rounded to the correct function value to 16 bits may be identical. The probability was 92.8% and the maximum error for the correct value was 0.082 ulp (unit in the last position). In other words, the maximum error does not exceed 1 ulp, so at most 7.2% of the time, unlike the exact 16-bit result, only the last digit is heard.

As described above, a trigonometric function generator is implemented by using CORDIC of a ROM table and a pipeline structure, and the number of entries is reduced by using the ROM table to reduce addition and subtraction of angles required by CORDIC, and to reduce pipeline length. By shortening there is an advantage that can implement a trigonometric generator of a simple structure.

Claims (4)

In the trigonometric function generator, A register that separates the input angle data into upper θ _M data and θ _L data, A memory for tabulating and storing Kcosθ _M and Ksinθ _M values, and outputting data corresponding to the θ _M data; Comprising an operation block corresponding to the number of iterations, a structure that binds a plurality of blocks in one pipeline stage and connects one register at each stage, and the output angle data of the memory by one of the θ _L data A trigonometric function generator comprising a pipeline structure codic that generates trigonometric functions by performing operations of the corresponding stages on the input and storing them in registers and passing them to the next stage in the next cycle. The method according to claim 1, wherein the codec of the pipeline structure stores the values generated during the operation in a carry storage adder to remove carry transfer, and at the last stage, the carry is quickly transferred using a carry look-ahead adder. A trigonometric function generator further comprising means for performing addition. The codec of the pipeline structure is provided with a memory that stores the Kcosθ _M and Ksinθ _M values in a table, and an operation block corresponding to the number of iterations, which combines multiple blocks into one pipeline stage and connects one register to each stage. In the trigonometric function generator provided, Separating input angle data into upper θ _M data and θ _L data, Outputting data corresponding to the θ _M data from the memory; The triangular function is generated by outputting the output angle data of the memory to the input of any cycle by the θ _L data and storing it in a register and transferring it to the next step in the next cycle. Trigonometric function generation method characterized in that. 4. The method of claim 3, wherein the generating of the trigonometric function stores carry values by storing the values generated during the operation in a carry storage adder, and quickly carries the carry using a carry look-ahead adder at the final stage. A trigonometric function generation method characterized by further comprising the process of performing the addition.