Multiplier-Free Divide, Square Root, and Log Algorithms [DSP Tips and Tricks]

Many signal processing algorithms require the computation of the ratio of two numbers, the square root of a number, or a logarithm. These operations are difficult when using fixed point hardware that lack dedicated multipliers, such as low-cost microcontrollers, application specific integrated circu...

Full description

Saved in:
Bibliographic Details
Published in:IEEE signal processing magazine 2011-07, Vol.28 (4), p.122-126
Main Authors: Auger, F., Zhen Luo, Feuvrie, B., Feng Li
Format: Magazinearticle
Language:English
Subjects:
Algorithm design and analysis
Approximation algorithms
Approximation error
Digital signal processing
Field programmable gate arrays
Signal processing algorithms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many signal processing algorithms require the computation of the ratio of two numbers, the square root of a number, or a logarithm. These operations are difficult when using fixed point hardware that lack dedicated multipliers, such as low-cost microcontrollers, application specific integrated circuits (ASICs), and field programmable gate arrays (FPGAs). This article presents straightforward, multiplier free algorithms that implement both division and square roots, based on a technique known as dichotomous coordinate descent (DCD) (See [1] as a starting point, where several articles by the same authors are referenced.) We also make available a multiplier-free logarithm algorithm. All these algo rithms are based on iterative methods, which compute the successive ele ments of a sequence of approximate solutions, just like the Gauss-Seidel, Jacobi, and conjugate gradient methods [2]. We begin our discussion with a scheme for computing the ratio of two real numbers.
ISSN:1053-5888
1558-0792
DOI:10.1109/MSP.2011.941101