Signal Processing - November 2017 - 164

TIPS & TRICKS
Vicente Torres, Javier Valls,
and Richard Lyons

Fast- and Low-Complexity atan2(a,b) Approximation

T

his article presents a new entry to
the class of published algorithms
for the fast computation of the
arctangent of a complex number. Our
method uses a look-up table (LUT) to
reduce computational errors. We also
show how to convert a large-sized LUT
addressed by two variables to an equivalent-performance smaller-sized LUT
addressed by only one variable. In addition, we demonstrate how and why the
use of follow-on LUTs applied to other
simple arctan algorithms produce unexpected and interesting results.

Introduction
The computation of the arctangent function atan2(a,b), i.e., obtaining the angle of
a complex number c = b + ja, has been
the subject of extensive study because
this computation is needed in many applications, for example, in the frequency,
phase, and time synchronization stages
of digital communications, digital FM
demodulation, target tracking in wireless
sensor networks, and object recognition
in the field of image processing. From a
designer's point of view, it is useful to have
several computation choices since the performance requirements (speed, accuracy,
power consumption, etc.) may be different
depending on the specific application, and
one of those choices may be better suited
than others for a given application.
A h igh-spe ed comput at ion of
atan2(a,b) can be achieved with LUTs,
Digital Object Identifier 10.1109/MSP.2017.2730898
Date of publication: 13 November 2017

164

where the bit-level concatenation of a and
b are the values used to address the ROM
that stores the output of the function. The
LUT method is fast but much memory is
required when a decent arctangent accuracy is needed. Another popular option is
to use high-order algebraic polynomials,
like Chebyshev polynomials or the Taylor
series [1]. These methods give good precision, but since the arctangent is highly
nonlinear, they lead to long polynomials
and intensive computations. In other cases,
approximations based on rational functions are used [2]-[4], as they may provide
acceptable results with few computations.
The coordinated rotation digital computer
(CORDIC) algorithm, which requires only
shift and add operations, is frequently used
to compute the arctangent [1]. However, its
sequential nature makes it less adequate
when throughput speed is critical.
Instead of using a single complicated
equation to achieve high accuracy, as proposed by other authors, our proposal is a
two-stage process with a first stage that
uses a low-complexity coarse approximation and a second stage that improves
the accuracy by means of a small LUT
that stores precomputed error values (as
a function of the first stage output). Our
proposal computes a full-quadrant arctangent faster than other popular options
that achieve the same accuracy. We now
describe the two processing stages of our
proposed atan2(a,b) algorithm.

First stage
The idea behind this stage is to conceptually generate a continuous real-valued
IEEE SIGNAL PROCESSING MAGAZINE

|

November 2017

|

sinusoid p (t) that has the same initial
phase angle as the phase of our complex
number c = b + ja. If c = c e ji, that
sinusoid would be
p (t) = c · cos ` 2rt - i j, (1)
T

	

where t is time and T is the sinusoid's
period, as shown in Figure 1.
The reason we care about this p (t)
sinusoid is that the time location of p (t)'s
maximum value, t m in Figure 1, is proportional to the desired phase angle of
c = b + ja = c e ji. The relationship
between t m and i is found by setting the
time derivative of p (t) equal to zero and
solving for t m . Doing so gives us
t m = Ti .(2)
2r

	

The time-domain dimensions of
variables t m and T must, of course, be
identical. With no loss in generality, and
out of convenience, we assume the time
between the p [n] samples is unity. Thus
t m is measured in units and T = 4 units.
So when we use (2) to compute i, the

p [n]
a

|c |

0
-|c |

b

1 tm

-b p(t ) for c = b + ja
2

3
-a

n
(t )

FIGURE 1. The real-valued sequence p [n] and

continuous sinusoid p (t ) associated with a
given complex number c = c e ji.

1053-5888/17©2017IEEE
Table of Contents for the Digital Edition of Signal Processing - November 2017
