# Simple Hybrid Scaling-Free CORDIC Solution for FPGAs

Authors: Leonid Moroz; Shinobu Nagayama; Taras Mykytiv; Ihor Kirenko; Taras Boretskyy
Journal: International Journal of Reconfigurable Computing
 (2014)

---

## Abstract

COordinate Rotation DIgital Computer (CORDIC) is an effective method that is used in digital signal processing applications for computing various trigonometric, hyperbolic, linear, and transcendental functions. This paper presents the theoretical basis and practical implementation of circular (sine-cosine) CORDIC-based generator. Synthesis results of this generator based on Altera Stratix III FPGA (EP3SL340F1517C2) using Quartus II version 9.0 show that the proposed hybrid FPGA architecture significantly reduces latency (42% reduction) with a small area overhead, compared to the conventional version. The proposed algorithm has been simulated for sine and cosine function evaluation, and it has been verified that the accuracy is comparable with conventional algorithm.


---

## Body

## 1. Introduction

COordinate Rotation DIgital Computer (CORDIC) is an effective method for the rotation vector in circular and hyperbolic coordinate systems. CORDIC was described by Jack Volder (J. Volder) in 1959. Since then, a great deal of work on this issue was published [1]. The method is popular now, due to its ease of software and hardware implementation. Indeed, for classical CORDIC method only a small amount of memory and some basic operations such as loading from memory, addition, subtraction, and shift are needed. The disadvantage of classical CORDIC is that the method has linear convergence. Thus, in order to get themcorrect result fractional bits, one must hold allmiterations.The comprehensive review of the modern state of theory and hardware representation of CORDIC method is provided in [1–3]. To achieve high performance there are attempts to build hybrid algorithms, such as LUT + CORDIC or CORDIC + final multipliers to boost performance [1, 4, 5]. However, there is no hybrid algorithm, which combines these three components: LUT, CORDIC, and final multipliers. Moreover, practical realization of such algorithm is unknown. An interesting method to increase productivity and reduce the average computation time was proposed in [6, 7], known as scaling-free CORDIC method. However, this approach has a narrow range of input angles, complex structure, and thus makes it impossible to design CORDIC calculators with accuracy of more than 16 correct bits.In this paper we propose hybrid architecture for high performance with a simple structure that allows one to get more than 16 correct bits of the result.


## 2. General Approach

The known methods to improve performance of conventional [1, 2, 8, 9] and scaling-free CORDIC methods [6, 7, 10, 11] are tabular calculation method and the residual method of multiplication described in [4, 10, 12], respectively. Table method is used to process the most significant bits of the input angle (argument), while the remaining multiplication is for the least significant bits.The first method is to create a precalculated table of values ​​for the most significant bits of the computing function argument. In this method [10] proposes an approach based on the scaling-free CORDIC, which combines the functionalities of memory units (LUT) and the corresponding iterative processing. The algorithms [4, 12] compute sine and cosine functions, where the first iterations are performed by the classical CORDIC, and then output multipliers are applied, allowing significant savings in hardware resources compared to the classical approach described in [13]. We propose combining both described approaches. The combination of the memory units, iterative scaling-free CORDIC algorithms, and multipliers provides a method without deformation module of the vector, which significantly saves hardware resources in FPGA implementation and reduces delays. The theoretical basis for the proposed method and its 16-bit microcontroller implementation are described in [11, 14]. However, no hardware implementation on FPGA has been reported until now. This paper proposes the algorithm of the hybrid FPGA calculator of trigonometric sine and cosine functions.


## 3. Proposed Algorithm

We give an improved and expanded hybrid CORDIC algorithm [11, 14] shown as follows.Letm be the given number of bits of the CORDIC, which determines the absolute errorΔ
m
=
2
-
mfor calculating sine and cosine functions. We assume that the input angleφis in the range0
-
π
/
4(the range of valuesφwill be discussed below) and is represented as
(1)
φ
=
∑
i
=
1
m
a
i
2
-
i
,
wherea
iare the coefficients of the binary representation of anφangle.To construct the sine-cosine generator, we use three elements—LUT, simple scaling-free CORDIC stages, and output multipliers. Accordingly, the input angleφis divided into three groups, which are processed sequentially using LUT, scaling-free CORDIC, and output multipliers.Therefore(2)
φ
=
φ
1
+
φ
2
+
φ
3
,
φ
1
=
∑
i
=
1
m
1
a
i
2
-
i
,
φ
2
=
∑
i
=
m
1
+
1
m
2
a
i
2
-
i
,
φ
3
=
∑
i
=
m
2
+
1
m
a
i
2
-
i
.We must set the numbersm
1 andm
2 to determine the size of each of these construction elements. By using m
1 and m
2, the number of bits of each group can be written asi
LUT
=
1
,
…
,
m
1;i
CORDIC
=
(
m
1
+
1
)
,
…
,
m
2;i
Multiplier
=
(
m
2
+
1
)
,
…
,
m.To do this, we first consider the possibility of using CORDIC method in this computational scheme. The scale factor for conventional CORDIC is1
+
2
-
2
i and for the scaling-free CORDIC it is1
+
2
-
4
i
-
2on every iterationi. An angleε
i
=
2
-
iis also updated by the valuesarctan
ε
iand arctan
[
(
2
ε
i
)
/
(
2
-
ε
i
2
)
] accordingly [11, 14]. For a given valuem, influence of the scale factor on the results of calculations for the conventional CORDICs is canceled when1
+
2
-
2
i
-
1
<
Δ
m, beginning from
(3)
i
modul
_
c
≥
⌈
m
-
1
2
⌉
[1, 4], and for the scaling-free CORDIC it is canceled when1
+
2
-
4
i
-
2
-
1
<
Δ
m, beginning from [11]
(4)
i
modul
_
sf
≥
⌈
m
-
3
4
⌉
.
It is caused by the fact that the scale factor becomes equal to 1.Similarly, influence of the angle for a conventional CORDIC also stops, when|
arctan
ε
i
-
ε
i
|
<
Δ
m, beginning from
(5)
i
angle
_
c
=
⌈
m
-
lo
g
2
3
3
⌉
[5], and for the scaling-free CORDIC when |
arctan
[
(
2
ε
i
)
/
(
2
-
ε
i
2
)
]
-
ε
i
|
<
Δ
m, beginning from [11]
(6)
i
angle
_
sf
=
⌈
m
-
lo
g
2
6
3
⌉
.
In these casesarctan
ε
iandarctan
[
(
2
ε
i
)
/
(
2
-
ε
i
2
)
]are equal,ε
i
=
2
-
i.Hence, we determine thatm
1
=
(
i
angle
_
sf
-
1
)andm
2
=
i
module
_
c. Thus, the number of bits for the first group (most significant bits) is defined asi
LUT
=
1
,
…
,
(
i
angle
_
sf
-
1
), that for the second (middle) isi
CORDIC
=
i
angle
_
sf
,
…
,
(
i
module
_
c
), and that for the third (least significant bits) isi
Multiplier
=
(
i
module
_
c
+
1
)
,
…
,
m.Example 1.
Assume thatm
=
16, i
LUT
=
1,2
,
3,4
;
i
CORDIC
=
5,6
,
7,8; andi
Multiplier
=
9,10,11,12,13,14,15,16.
Examples of the distribution of iterations between LUT, scaling-free (SF) CORDIC, and multipliers for different number of digits  shown in Table1.Table 1
Distribution of iterations for hybrid devices of different bits.
m
LUT
SF CORDIC
Multiplier
16
1
,
…
,
4
5
,
…
,
8
9
,
…
,
168
24
1
,
…
,
7
8
,
…
,
12
13
,
…
,
24
32
1
,
…
,
9
9
,
…
,
16
17
,
…
,
32
48
1
,
…
,
15
16
,
…
,
24
25
,
…
,
48Step 1. Preprocessing (or range reduction). Calculation of a sine-cosine with any of anglesϕ, which is in the range0
-
2
π, can be reduced to the calculation of sine-cosine with angleφ, which is in the first octant of 0
-
π
/
4. Such reduction of a range is allowed by the rule of 8-point symmetry of circle. Methods for transformation of the input angleϕto theφare well known, for example, [8, 10], so we will not discuss it here.Step 2. Form
=
16the angleφis divided into the following three angles:
(7)
φ
=
φ
1
+
φ
2
+
φ
3
φ
1
=
∑
i
=
1
4
a
i
2
-
i
;
φ
2
=
∑
i
=
5
8
a
i
2
-
i
;
φ
3
=
∑
i
=
9
m
=
16
a
i
2
-
i
.Step 3. Value is selected from LUT:
(8)
x
4
=
cos
⁡
(
φ
1
)
;
y
4
=
sin
(
φ
1
)
;and then the following iterations are made fori
=
5,6
,
7:
(9)
x
i
=
x
i
-
1
-
a
i
(
x
i
-
1
2
-
2
i
-
1
+
y
i
-
1
2
-
i
)
;
y
i
=
y
i
-
1
+
a
i
(
-
y
i
-
1
2
-
2
i
-
1
+
x
i
-
1
2
-
i
)
.
Fori
=
8
(10)
x
i
=
x
i
-
1
-
a
i
y
i
-
1
2
-
i
;
y
i
=
y
i
-
1
+
a
i
x
i
-
1
2
-
i
.
In vector-matrix form, step 3 is as follows:
(11)
[
x
8
y
8
]
=
(
∏
i
=
5
7
[
1
-
a
i
ε
i
2
2
-
a
i
ε
i
a
i
ε
i
1
-
a
i
ε
i
2
2
]
)
[
1
-
a
8
ε
8
a
8
ε
8
1
]
[
x
4
y
4
]
.Step 4. Performing the multiplication on the residual angleφ
3
(12)
x
9
=
x
8
-
y
8
φ
3
;
y
9
=
y
8
+
x
8
φ
3
;
x
9
≈
cos
⁡
(
φ
)
;
y
9
≈
sin
(
φ
)
,
or in the unfolded form
(13)
x
9
=
x
8
-
y
8
(
a
9
2
-
9
+
a
10
2
-
10
+
a
11
2
-
11
+
a
12
2
-
12
s
s
s
s
s
s
s
s
s
s
s
+
a
13
2
-
13
+
a
14
2
-
14
+
a
15
2
-
15
+
a
16
2
-
16
)
,
(14)
y
9
=
y
8
+
x
8
(
a
9
2
-
9
+
a
10
2
-
10
+
a
11
2
-
11
+
a
12
2
-
12
s
s
s
s
s
s
s
s
s
s
s
+
a
13
2
-
13
+
a
14
2
-
14
+
a
15
2
-
15
+
a
16
2
-
16
)
.
Obviously from these equations, final multiplication can be realized on typical for CORDIC operations as shift-add.Step 5. Postprocessing. Computed sine-cosine with angleφis necessary to be converted to sine-cosine with angleϕby the rule of 8-point symmetry of circle (everything is reduced only to the appropriate definition of signx
9 and y
9).


## 4. FPGA Implementation Results

To show the effectiveness of the proposed algorithm, we implemented steps 3 and 4 in the algorithm with the Altera Stratix III FPGA (EP3SL340F1517C2) using Quartus II version 9.0.Figure1 shows the architecture of the algorithm implemented on the FPGA. In this figure, LUT and CORDIC blocks realize step 3 in the algorithm, and the block labeled with “Shift Add” realizes step 4. To achieve high-throughput computation, the architecture is pipelined with 9 stages: 1 stage for the LUT block, 4 stages for the CORDIC block, and 4 stages for the Shift Add block.Figure 1
Architecture of the hybrid scaling-free CORDIC algorithm.The LUT block is implemented by ROM with a 4-bit input and two 16-bit outputs. In the CORDIC block, each iteration of the algorithm fromx
5 to x
8 is implemented as a pipeline stage by logic elements, and it has two 20-bit outputs. The Shift Add block is implemented by dedicated DSP blocks on the FPGA, which have 4 pipeline stages. The outputs of the Shift Add block have 28 bits, and they are rounded to 16 bits.In the best-known FPGA implementation of the conventional CORDIC algorithm for high throughput, all iterations of the algorithm fromx
1 to x
16 are unrolled, and each of them is implemented as a pipeline stage. Thus, such implementation method requires a long latency and many logic elements. On the other hand, our implementation of the hybrid CORDIC requires fewer logic elements and causes shorter latency due to fewer pipeline stages.Table2 shows FPGA implementation results of the conventional CORCIC algorithm and our hybrid CORDIC algorithm. As shown in this table, our hybrid algorithm is much more efficient than the conventional one in terms of hardware cost. Compared to the conventional CORDIC, the proposed algorithm has approximately the same bandwidth. However, there is a considerable gain in reduction of latency, as well as the number of logic elements. Moreover, the number of pipeline stages is also reduced. Therefore, the proposed method is easier to implement and uses less logic elements, while it has similar bandwidth. Although our hybrid algorithm requires not only logic elements but also DSP blocks, this is efficient for modern FPGAs. This is because most of modern FPGAs have DSP blocks and memory blocks, and a balanced use of them as well as logic elements is more efficient. Therefore, we can conclude that our hybrid algorithm is suitable for modern FPGA implementation.Table 2
FPGA implementation results of conventional and hybrid algorithms.
Conventional CORDIC
Hybrid CORDIC
Ratio (%)
Pipeline stages
16
9
56
Logic elements (ALUTs)
984
372
38
DSP blocks
0
8
—
Latency (nsec.)
50
29
58
Throughput (106/sec)
320
306
96


## 5.  Concluding Remarks

This paper describes the theoretical bases and practical pipelined FPGA implementation of a new hybrid scaling-free CORDIC algorithm. Logical combination of three construction elements of modern FPGAs which are LUT, simple scaling-free CORDIC stages, and multipliers allowed a considerable improvement of calculation efficiency of sine and cosine functions without the loss of accuracy, compared to conventional CORDIC algorithms.The proposed method allows the reduction of the FPGA hardware resources by more than 30%, while providing the same throughput and accuracy of calculations.



---

*Source: 615472-2014-04-24.xml*