CN102799412A - CORDIC (coordinate rotation digital computer) accelerator based on parallel pipeline design - Google Patents

Abstract

The invention relates to a CORDIC accelerator based on parallel pipeline design. It includes an angular preprocessing module, a CORDIC kernel module, a data backend processing module and a controller module. The present invention first reads the external data line and the control line into the relevant data signal and control signal to the controller module, then transmits the angle to be requested to the angle preprocessing module, and then reads the processed angle from the controller module The initial value is sent to the CORDIC core module together, where the CORDIC core module adopts a parallel 16-stage pipeline structure to quickly calculate the two values of the sine and cosine of the angle after passing through the angle preprocessing module, and then transfer the calculated data to the slave controller The phase control signal output by the module is sent to the back-end data processing module to determine the positive and negative of the corresponding initial phase sine and cosine values, and finally the sine and cosine values are sent to the controller module, and the sine or cosine is required according to the external control signal value, giving the associated result.

Description

CORDIC Accelerator Based on Parallel Pipeline Design

technical field

The present invention relates to a coordinate rotation digital computing (Coordinate Rotation Digital Computer, CORDIC) accelerator based on a parallel assembly line design, specifically an arithmetic unit capable of quickly calculating transcendental functions, mainly used in aerospace technology, robot technology, image processing Calculator for signal processing, filter technology, etc.

Background technique

In daily life, whether it involves various scientific and technological fields such as aerospace, image signal processing, digital communication, video technology or drawing applications, or actual measurement calculation, numerical analysis, probability and statistical motion vector estimation, etc., high-precision trigonometric function operations are in There are quite a wide range of applications in practical engineering. Therefore, it is very important to research and use hardware design to realize higher precision and fast trigonometric function calculation. The mathematical function algorithm implemented by hardware can be divided into the following categories according to the different mathematical formulas and corresponding implementation methods: table lookup method, polynomial approximation method, combination method of table lookup and polynomial, rational number approximation method and bitwise method, and CORDIC algorithm.

CORDIC was first proposed by J.D.Volde in 1959. This algorithm is a recursive algorithm. By introducing a certain initial value, combined with simple shift and addition and subtraction, these complex function operations can be realized. In order to expand the number of basic functions that can be solved, J.Walter proposed a unified CORDIC algorithm in 1971. The existing CORDIC iterative operation device is used for floating-point coprocessors, which can support a wide variety of functions, including arithmetic operations, trigonometric operations, exponential operations, etc. In order to save resources, a unified form of CORDIC algorithm is used to realize the operations of all functions , such as the announcement number is CN102073472A, a Chinese invention patent specification published on April 9, 2008, which is authorized to be published, is called "a trigonometric function CORDIC iterative operation iterative processor and operation processing method". This patent provides a trigonometric function CORDIC iterative coprocessor and operation processing method, through the input conversion circuit of trigonometric functions, the input parameters are transformed into the input range allowed by the CORDIC algorithm, so as to support the trigonometric function operation of all angles, and there is no The input range is limited, but the patent requires a 54*54 multiplier before the CORDIC operation, which greatly increases the area and delay time.

Compared with the conventional CORDIC iterative calculation method and related circuit implementation technology, the present invention has the advantage of simultaneously meeting the four requirements of full-angle calculation, low delay, small area, and high precision in terms of real-time requirements and area requirements. . It solves the problem of achieving the minimum area and quickly calculating the required trigonometric function values under the guarantee of high precision.

Contents of the invention

The purpose of the present invention is to provide a CORDIC accelerator based on parallel pipeline design in order to solve the problems of large area and low precision under the condition of guaranteed speed, which has low cost, high throughput, small area and high precision. features.

The technical scheme of the present invention is: a kind of CORDIC accelerator based on parallel pipeline design, comprising: an angle preprocessing module, a CORDIC core module, a back-end data processing module, and a controller module. Its basic feature is that the front end of the CORDIC core module is connected to the angle preprocessing module, the back end is connected to the data processing module, the controller module is connected to the angle preprocessing module, the CORDIC core module and the data processing module, and the external data line and the control line are connected to each other. Read in the relevant data signals and control signals to the controller module, then transmit the angle to be requested to the angle preprocessing module, and then transmit the processed angle to the CORDIC kernel module together with the initial value read from the controller module, The CORDIC core module adopts a parallel pipeline structure to quickly calculate the two values of the sine and cosine of the angle after passing through the angle preprocessing module, and then transmit the calculated data and the phase control signal output from the controller module to the back-end data processing The module determines the positive and negative of the positive and cosine values of the corresponding initial phase, and finally transmits the sine and cosine values to the controller module. According to the external control signal, the sine or cosine values are required, and the relevant results are given, as shown in Figure 1 : Through the external data line, the control line reads in the relevant data signal and control signal to the controller module, and then transmits the angle to be requested to the angle preprocessing module, compressing the full angle module to [0°, 90°], It is not limited to (-99.8°, 99.8°), and then transmits the processed angle to the CORDIC kernel module together with the initial value read from the controller module. CORDIC adopts a parallel pipeline structure to quickly calculate the angle through the preprocessing module The two values of the sine and cosine of the rear angle, and then the calculated data and the phase control signal output from the controller module are sent to the back-end data processing module to determine whether the positive and negative values of the corresponding initial phase are positive or negative, and finally The sine and cosine values are sent to the controller module, and the sine or cosine values are required according to the external control signal, and the relevant results are given. Every time the sine and cosine values are calculated, the controller will give a response signal to the outside, which is convenient for regulation.

The above-mentioned CORDIC kernel module adopts a parallel pipeline mode, which can quickly calculate the sine and cosine values of the required angle at the same time, and has high throughput. By choosing 32 iterations, the precision of the obtained sinine and cosine values can reach 10 ⁻⁸ . Corresponding to the shift register, each iteration only needs to move one bit. Due to the pipeline structure, the data of the upper pipeline can be directly sent to the next level, so the dislocation connection can be realized, thus reducing the shift register. area. In addition, in the calculation process of the CORDIC algorithm, each iteration needs to find the corresponding arctangent angle value through the lookup table, and because the number of iterations is fixed in the present invention, the tangent value of each level can be directly corresponding to the corresponding high and low levels, that is, no need Calling the value to the outside, on the one hand, improves the computing speed of the hardware, and on the other hand, reduces the required ROM area. In the CORDIC kernel module, in order to ensure the smallest possible area and calculate the correlation function value at a high speed, the present invention adopts 32 iterations and a 16-stage pipeline form.

The above-mentioned angle preprocessing module is composed of four adders and a four-to-one selector. It is characterized in that the input end of the four-choice selector is connected to the output results of four adders; according to different angle inputs, through one-stage addition and subtraction operations, and then cooperate with the phase control signal to select the output, any input angle can be selected. All of them are transformed into the range of [0°,90°], so that the entire module operation process of CORDIC is no longer constrained by the angle range.

The above-mentioned back-end data processing module is made up of 2 inverters, 2 four-selectors and 4 registers, and is characterized in that the front-ends of the two four-selectors are connected to the data processed by the CORDIC kernel module, and the back-end Connect the sine-cosine register and the error register, and the phase register is used to control the output result of one of the four selections. The data results output from the CORDIC module are divided into positive and negative signs according to the phase control signal.

The above-mentioned controller module is mainly composed of some registers and selectors, which are used to regulate the coordinated operation of each sub-module in the entire CORDIC module, and give status values and result values according to external control signals.

Compared with the prior art, the present invention has the following obvious outstanding substantive features and significant progress:

(1) The volume of each module of the present invention is small and the structure is simple, so the overall volume is small and easy to realize.

(2) The CORDIC module of the present invention is implemented in a parallel pipeline structure, especially the internal shift register is implemented in broken lines, so that the entire module has a small time delay and a small area.

(3) In the CORDIC module of the present invention, the required tangent value directly corresponds to the fixed high and low levels, and there is no need to call through the look-up table, so that the entire module can be executed quickly, and the occupied area is small.

(4) The CORDIC module of the present invention uses 32 iterations, and the accuracy of the obtained data can reach 10 ^-8 . Using 16-stage pipeline, the overall calculation throughput is large, achieving the purpose of fast calculation.

Description of drawings

Figure 1 is a general block diagram of the system control.

Figure 2 is a plane coordinate rotation diagram.

Figure 3 is a structural diagram of the angle preprocessing module.

Figure 4 is a structure diagram of the CORDIC kernel module.

Figure 5 is a structural frame diagram of a pipeline.

Figure 6 is a structural framework diagram of an iteration.

Fig. 7 is a structural diagram of the data post-processing module.

Figure 8 is a timing diagram of the entire CORDIC module.

Detailed ways

Preferred embodiments of the present invention are described in detail as follows in conjunction with accompanying drawings:

Embodiment one:

As shown in Figure 1, the CORDIC accelerator designed based on the parallel pipeline of the present invention includes: an angle preprocessing module (1), a CORDIC kernel module (2), a data back-end processing module (3) and a controller module ( 4). It is characterized in that the external data lines and control lines are first read in the relevant data signals and control signals to the controller module (4), and then the angle to be requested is transmitted to the angle preprocessing module (1), and then the processed angle The initial value read from the controller module (4) is sent to the CORDIC kernel module (2), and the CORDIC kernel module (2) adopts a parallel pipeline structure to quickly calculate the sine sum of the angle after passing through the angle preprocessing module (1) The two values of cosine are then sent to the back-end data processing module (3) together with the calculated data and the phase control signal output from the controller module (4), to determine the positive and negative of the corresponding initial phase positive and cosine values, Finally, the sine value and cosine value are sent to the controller module (4), and the sine value or cosine value is required according to the external control signal, and relevant results are given.

Embodiment two:

This embodiment is basically the same as Embodiment 1, and the special features are as follows:

For the CORDIC algorithm under the circular rotation mode adopted by the present invention, Fig. 2 is a plane coordinate rotation completed by the circular system of the CORDIC algorithm. Among them, Figure 2.a shows that from the original point A (x1, y1), after the rotation angle θ, it reaches the target point B (x2, y2), and Figure 2.b shows that after the first CORDIC angle rotation, Reach A'(x1',y1'), Figure 2.c shows that after the second CORDIC angle rotation, A"(x1",y1") is reached, after multiple rotations, An will approach the target point B .

<1>, CORDIC kernel module

Referring to Figure 4, this module is implemented with a parallel, 16-stage pipeline structure, which improves the computing throughput. Each stage is composed of two 32-bit iterations and one 32-bit register. Referring to FIG. 5 , 32 iterations are used to make the accuracy of the entire operation reach 10 ^-8 . Each iteration consists of a 32-bit adder and subtractor and a 32-bit shifter, see Figure 6. The core module of CORDIC is mainly the design of 32-bit adder and subtractor, 32-bit register and shifter, among which the adder-subtractor is the core component of the CORDIC kernel module. The adder and subtractor selected by the present invention is based on the advanced carry adder, and selects the advance in the group, the serial carry mode between the groups, and the carry propagation process of each group can be regarded as a separate instance unit . The register selected by the present invention is based on a traditional transmission gate, plus a logic control circuit combined with an AND gate and an OR gate, so that the register has the functions of controlling clearing and enabling. Due to the pipeline structure, as shown in Fig. 4, each iteration is a sequential shift, so the data is directly transmitted from the upper stage to the next stage, and this patent only uses broken lines to represent the corresponding shift registers. In addition, the arc tangent angle value required for each iteration in the calculation process of the CORDIC algorithm is replaced by a broken line connected with high and low levels in this patent to improve the computing speed of the hardware.

<2>, angle preprocessing module

See Figure 3, this module consists of a selector and an adder. The function is to compress different input angles to [0°, 90°], and transmit the compressed angle value to the CORDIC kernel module, so that it is no longer limited by the angle range of the CORDIC kernel, and the data result can be calculated quickly. The Phase_1, Phase_2, Phase_3, and Phase_4 signal lines in the angle preprocessing module represent the first quadrant, the second quadrant, the third quadrant, and the fourth quadrant respectively. The highest two bits of the input angle are selected as the detection sign bit, and the Ph_c signal line is used express. When Ph_c detects that it is the angle of the second quadrant, the output data selects the angle processed by the second quadrant.

<3>, back-end data processing module

See Fig. 7, this module is made up of selector, adder and register. The function is to divide the sine and cosine values obtained by the CORDIC kernel module according to the phase angle. The back-end data processing module is respectively connected with the output data terminal of the CORDIC kernel module and the enabling signal terminal of the controller, the clearing signal terminal and the phase angle control terminal. When the clear signal of the controller module is low and the enable signal is high, the back-end data processing module starts to judge the sign and calculate the result obtained from the CORDIC core.

<4>, controller module

This module is mainly composed of some selectors and registers, and its function is to control the entire CORDIC operation timing. Corresponding to the entire CORDIC module, see Figure 8, where the angle preprocessing module occupies one clock cycle, the CORDIC kernel module occupies sixteen clock cycles, and the back-end data processing module occupies one clock cycle. When the reset signal is low, the entire CORDIC module is cleared. When the reset signal is high and the start signal start is high, the data input calculation is started. After eighteen clock cycles, the output status signal ok is high, and Output data results. In addition, the signal line n can be selected as sin value output or cos value output, and the corresponding result can be selected and output according to external actual needs. Due to the pipeline structure, the throughput is large and the calculation speed is fast.

Claims (7)

1. A CORDIC accelerator based on parallel pipeline design, including an angle preprocessing module (1), a CORDIC kernel module (2), a data back-end processing module (3) and a controller module (4), its characteristics The front end of the CORDIC kernel module (2) is connected to the angle preprocessing module (1), the back end is connected to the data processing module (3), and the controller module (4) is connected to the angle preprocessing module (1) and the CORDIC kernel module (2) and data processing module (3), read the external data lines and control lines into relevant data signals and control signals to the controller module (4), and then transmit the angle to be requested to the angle preprocessing module (1) , and then transmit the processed angle to the CORDIC kernel module (2) together with the initial value read from the controller module (4). 1) The two values of the sine and cosine of the rear angle, and then the calculated data and the phase control signal output from the controller module (4) are sent to the back-end data processing module (3), and the corresponding initial phase is determined The positive and negative of the positive and cosine values, and finally the sine and cosine values are sent to the controller module (4), and the sine or cosine values are required according to the external control signal, and the relevant results are given. 2. The CORDIC accelerator based on parallel pipeline design according to claim 1, characterized in that said angle preprocessing module (1) is made up of four adders and a four-choice selector, and the four-choose one selector The input terminal is connected to the output results of four adders; according to different angle inputs, through one-stage addition and subtraction operations, and then select the output with the phase control signal, any input angle can be converted into the range of [0°, 90°] , so that the entire CORDIC module operation process is no longer constrained by the angle range. 3. the CORDIC accelerator based on parallel pipeline design according to claim 1, is characterized in that described CORDIC core module (2) is made up of adder, register, and the result that two-stage addition obtains is sent in the register; Adopted What is more important is the parallel pipeline structure mode: the 16-stage pipeline is adopted to make the calculation speed fast and the throughput high, and the 32 iterations are used to make the precision of the whole calculation reach 10 ^-8 . 4. the CORDIC accelerator based on parallel pipeline design according to claim 1, is characterized in that described CORDIC core module (2) is made up of adder and register, because every iteration needed anyway in the calculation process of CORDIC algorithm Tangent angle value, and each tangent angle value is determined, so the broken line connected with the high and low levels is used instead of the register to store data, and the computing speed of the hardware is improved. 5. the CORDIC accelerator based on parallel pipeline design according to claim 1, is characterized in that described CORDIC core module (2) is made up of adder and register, adopts the structure of pipeline, and each iteration is shift in order, The data can be directly input to the register from the operation result of the two-stage adder, and only a broken line is used to represent the corresponding shift register, which reduces the area. 6. The CORDIC accelerator based on parallel pipeline design according to claim 1, characterized in that said back-end data processing module (3) consists of 2 inverters, 2 four selectors and 4 registers , the front end of two four-choice selectors is connected to the data processed by the CORDIC kernel module (2), the back-end is connected to the sine-cosine register and the error register, and the phase register is used to control the output result of the four-choice one selection; for the CORDIC module ( 2) The output data results are divided into positive and negative signs according to the phase control signal. 7. The CORDIC accelerator based on parallel pipeline design according to claim 1, characterized in that the controller module (4) is composed of a finite state machine, which adjusts and controls the entire operation of CORDIC, so that the entire operation is carried out in an orderly manner .

Images