The circuit employs a simple algorithm to compute the nth root of a number by using logarithm. It takes a 16- bit binary input, which is input to a 16-bit binary-to-binary logarithm converter. The resulting number is a floating point number, which is the input dividend for the subsequent division operation. The division block inputs another 4-bit number ‘n’ as divisor. The result is a 16-bit floating point number, which is input to a binary logarithm-to-binary converter block to generate the result, which is a 16-bit floating point number. Mathematically, the algorithm can be explained as follows:

Let A be a number for which we want to compute the nth root and the result is Y, then

Taking logarithm on both sides we obtain,

Chip Architecture:

A brief description of the major circuit blocks is given below:

1) 16-bit binary-to-binary logarithm converter:

The circuit employs a very simple technique to calculate the binary logarithm to the base 2 of a 16-bit input number. The principle behind the operation of the circuit is explained below:

Let N be a 16-bit binary number which can be represented by

where Zi is "0" or "1". Our first step is to find a number k (from 0 to 15), such that Zk is 1, so that it can be treated as the MSB. In order to find k, we need a Leading One Detector Circuit, the principle of which will be explined later.

Now N can be expressed as

By factoring out, we get

Let the term

Since k corresponds to the MSB of the input number, so the number m lies between 0 and 1.

Hence, we can express N as

By expansion of a logarithmic series, we get the following series:

Since m is between 0 and 1, we can use a straight line approximation to ignore the higher orders of m and reduce the expression for logarithm of N as:

This step introduces a simplification error in the computation and this is the reason we can only use our technique in systems which can tolerate some error.

The logarithm converter, based on the above principle is designed using a 16-bit LOD (Leading One Detector) circuit and a logarithmic shifter. The logarithm converter generates Mitchell’s approximations to the actual logarithms. The block diagram for the circuit is shown below:

Block Diagram of 16-bit Logarithm Converter

Leading One Detector Circuit:

The first step of computing the logarithm is to locate the position of the leading one in the input 16-bit number. This is important because the binary number representing the position of the leading one in the input stream forms the characteristic of the resulting binary logarithm.

This circuit block receives a 16-bit input number and outputs a 16-bit active high decoded output. The output has only one HIGH bit which corresponds to the position of the leading one in the input binary word. Thus, the circuit passes only the leading one in the input binary stream to the output and resets all other bits to zero.

Though many circuits have been implemented over the years for “leading one detection” but most of the circuits are slow. In recent years, Abed and Siferd have implemented circuits that can perform the “leading one detection” operation really fast. However, in this project we have implemented some changes in the combinational logic to obtain a slight increase in the speed of the circuit.

16 word x 4-bit MOS ROM:

The LOD 16-bit active-high decoded output is connected to 16-word lines in a 16-word x 4-bit MOS ROM. The ROM generates 4-bit binary words based on the active-high input which in turn depends on the leading one position. The ROM 4-bit output binary words are the logarithm characteristics and used, directly by the logarithmic shifter without a decoder, as control binary words to determine the total shift value.

16-bit Logarithmic Shifter:

The logarithmic converter takes the 4-bit output from the previous stage as the control word, and the 16-bit input word as input. Depending on the value of the control word, it shifts the input word to the right and stores them in a 12-bit register which is meant to store the mantissa of the logarithm. These 12 bits are placed to the right of the 4-bit characteristic to obtain a 16-bit logarithm of the input 16-bit number.

(Note: In worst case, when the leading one occurs at the MSB of the 16-bit input word, then we truncate the LSB 3-bits of the mantissa will be truncated.)

2) 16-bit Divider

The 16-bit Divider that will be used in this project is implemented by a restoring dividing algorithm, which can be explained as follows:

let's denote dividend A [15:0], divisor D [3:0], quotient Q [15:0], and partial remainder of ith iteration Ri [3:0], where i is in the interval [1,16]. We have

Tradionally, in order to get 16-bit quotient, 16 iterations of subtraction or addition are needed, which would lead to low speed division. In this project, all divisors are normalized from 8 to 15 before going into the divider, such normalization will reduce the number of iterations to 13. Simulation result shows that such normalization can reduce the time for division operation by 50%. one iteration of obtaining one bit quotient is shown below:

After 13 such iterations, the final remainder and the original divisor (unnormalized) are compared by a comparator, the output of the comparator together with the 13-bit partial quotient are sent to a shifter, where errors can be calibrated and correct quotient are given out. The flow chart of 16-bit divider is shown below:

3) 16-bit binary logarithm-to-binary converter:

The basic mathematical principle used to compute the anti-logarithm of a number is explained below:

As explained previously, the input to the antilogarithm converter block is of the form

where Q is the quotient from the divider.

The antilog for this input can be expressed as:

Here, k is an integral value while m is less than unity. So, we can approximate 2m based on its Binomial Expansion. So our expression for antilog becomes:

This is again implemented using a logarithmic shifter, as described below.

The 16-bit input binary word is divided into two parts. The four left-most bits are the characteristic, and the remaining 12 bits are the mantissa. The characteristic is used to determine the proper value of the control word of the logarithmic shifter. The shifter has 16 inputs, but the mantissa has 12 bits. A ‘1’ is attached to left side of the MSB of the mantissa to provide the leading one in the converted binary word. Also, three zeros are attached to the right side of the LSB of the mantissa to complete the 16-bit shifter input. The shifter rotates based on the computed control word the truth table explained in the corresponding section. In our circuit, we have used two logarithmic shifters, one to calculate the integral part of the antilog value and another one to calculate the decimal part of the output.

Block Diagram of 16-bit Anti-Logarithm Converter

The 16-bit output obtained is the nth root of the input 16-bit word.