Newton-Raphson Reciprocal - Digital System Design

Newton-Raphson’s iterative algorithm is a very popular method to approximate a given function. It can be used to compute reciprocal of a given number. The Newton-Raphson’s iterative equation is

$X_{i+1} = X_i - \frac{f(X_i)}{{f_1}(X_i)}$

where $f_1(X_i)$ is the first derivative of $f(X_i)$ . The function which is used to compute the reciprocal of a number is $f(x) = (1/X) - D$ , where D is the input operand. The Newton-Raphson iteration gives

$X_{i+1} = X_i(2 - D.X_i)$

After some finite iterations the above equation converges to the reciprocal of D. It is very obvious that initial value of X ( $X_0$ ) must be chosen care fully to converge. The value of D is scaled to be in the range $0.5\leq D \leq 1$ to chose the initial guess $X_0$ such that few number of iterations required for computation. In this case, D is shifted right or left to be in that range. In that interval of D, one must chose initial value $X_0$ as

$X_0 = \frac{48}{17} - \frac{32}{17}D$

The architecture for Newton-Raphson based reciprocal computation is shown below. A serial architecture is given here as parallel architecture is costly and most system architectures uses serial architecture. The pulsed control signal start starts the iteration and $x_f$ is the final result. If D is not in the range, pre-processing is required and at the output a post-processing step is also required.

Click here to download the Verilog Code

-4

Related Posts