Division operation apparatus and method of the same

Patent metadata

Field	Value
Publication number	US-9798520-B2
Application number	US-201615099608-A
Country	US
Kind code	B2
Filing date	Apr 15, 2016
Priority date	Dec 29, 2015
Publication date	Oct 24, 2017
Grant date	Oct 24, 2017

Abstract

A division operation apparatus is provided. The division operation apparatus includes a memory, a non-zero bit detection circuit, a mapping calculation circuit, a look-up circuit, a compensation circuit and a multiplication circuit. The memory stores a divisor look-up table including a plurality of entries. The non-zero bit detection circuit detects a number of a highest non-zero bit of the divisor. The mapping calculation circuit generates a mapped value of the divisor within a range of the divisor look-up table according to a mapping function. The look-up circuit retrieves a corresponding entry having a stored reciprocal according to the mapped value. The compensation circuit generates a compensation value according to the mapping function. The multiplication circuit multiplies a dividend, the stored reciprocal and the compensation value to generate a divided result of the dividend and the divisor.

First claim

What is claimed is:

1. A division operation apparatus comprising:
a memory configured to store a divisor look-up table comprising a plurality of entries;
a non-zero bit detection circuit configured to generate a determination result signal by receiving a divisor to detect a number of a highest non-zero bit of the divisor and determine whether the divisor exceeds a range of the divisor look-up table based on the detected number;
a mapping calculation circuit configured to generate a mapped value of the divisor within a range of the divisor look-up table according to a mapping function if the divisor exceeds the range of the divisor look-up table;
a look-up circuit configured to select between the divisor and the mapped value based on the determination result signal and look up the divisor look-up table according to the selected value to retrieve a corresponding entry having a stored reciprocal;
a compensation circuit configured to generate a compensation value according to the mapping function; and
a multiplication circuit configured to multiply a dividend, the stored reciprocal and the compensation value to generate a divided result of the dividend and the divisor.

2. The division operation apparatus of claim 1 , wherein the mapping function makes the divisor multiplied by a first parameter and further divided by a second parameter to generate the mapped value, wherein each of the first parameter and the second parameter is an exponent of 2.

3. The division operation apparatus of claim 2 , wherein the second parameter is N-th power of 2, wherein N is the number of the highest non-zero bit.

4. The division operation apparatus of claim 2 , wherein the compensation value is the inverted second parameter multiplied by the first parameter.

5. The division operation apparatus of claim 2 , wherein if the second parameter exceeds the range of the divisor look-up table, the compensation circuit factorizes the second parameter to a third parameter and a fourth parameter, the look-up circuit generates reciprocals of the third parameter and the fourth parameter, and the compensation circuit generates the reciprocal corresponding to the second parameter by a product of the reciprocals of the third parameter and of the fourth parameter, in which each of the third parameter and the fourth parameter is an exponent of 2.

6. The division operation apparatus of claim 2 , wherein if the second parameter does not exceed the range of the divisor look-up table, the look-up circuit directly looks up the divisor look-up table according to the divisor to retrieve the corresponding entry from the entries of the divisor look-up table, and the multiplication circuit multiplies the dividend and the stored reciprocal of the corresponding entry to generate the divided result of the dividend and the divisor.

7. The division operation apparatus of claim 1 , wherein the memory is further configured to store a reference index comprising a plurality of factorization relations;
the look-up circuit is further configured to look up the reference index according to the mapped value to retrieve a plurality of the entries corresponding to the mapped value according to one of the factorization relations; and
the multiplication circuit is further configured to multiply the dividend, the stored reciprocal of each of the retrieved entries and the compensation value to generate the divided result of the dividend and the divisor.

8. The division operation apparatus of claim 7 , wherein each of the entries of the divisor look-up table corresponds to a prime number.

9. The division operation apparatus of claim 1 , wherein if the divisor is an exponent of 2, the multiplication circuit directly right-shifts at least one bit of the dividend according to the divisor.

10. A division operation method comprising:
generating a determination result signal by receiving a divisor by a non-zero bit detection circuit to detect a number of a highest non-zero bit of the divisor and determining whether the divisor exceeds a range of a divisor look-up table based on the detected number, wherein the divisor look-up table is stored in a memory and comprises a plurality of entries;
generating a mapped value of the divisor within a range of the divisor look-up table by a mapping calculation circuit according to a mapping function if the divisor exceeds the range of the divisor look-up table;
selecting between the divisor and the mapped value based on the determination result signal and looking up the divisor look-up table by a look-up circuit according to the selected value to retrieve a corresponding entry having a stored reciprocal;
generating a compensation value by a compensation circuit according to the mapping function; and
multiplying a dividend, the stored reciprocal and the compensation value by a multiplication circuit to generate a divided result of the dividend and the divisor.

11. The division operation method of claim 10 , further comprising:
making the divisor multiplied by a first parameter and further divided by a second parameter by the mapping function to generate the mapped value, wherein each of the first parameter and the second parameter is an exponent of 2.

12. The division operation method of claim 11 , wherein the second parameter is N-th power of 2, wherein N is the number of the highest non-zero bit.

13. The division operation method of claim 11 , wherein the compensation value is the inverted second parameter multiplied by the first parameter.

14. The division operation method of claim 13 , wherein if the second parameter exceeds the range of the divisor look-up table, the division operation method further comprises:
factorizing the second parameter to a third parameter and a fourth parameter by the compensation circuit; and
generating reciprocals of the third parameter and the fourth parameter by the look-up circuit, and generating the reciprocal corresponding to the second parameter by a product of the reciprocals of the third parameter and of the fourth parameter by the compensation circuit, in which each of the third parameter and the fourth parameter is an exponent of 2.

15. The division operation method of claim 11 wherein if the second parameter does not exceed the range of the divisor look-up table, the division operation method further comprises:
directly looking up the divisor look-up table by the look-up circuit according to the divisor to retrieve the corresponding entry from the entries of the divisor look-up table; and
multiplying the dividend and the stored reciprocal of the corresponding entry by the multiplication circuit to generate the divided result of the dividend and the divisor.

16. The division operation method of claim 15 , wherein each of the entries of the divisor look-up table corresponds to a prime number.

17. The division operation method of claim 10 , wherein the memory is further configured to store a reference index comprising a plurality of factorization relations, the division operation method further comprises:
looking up the reference index by the look-up circuit according to the mapped value to retrieve a plurality of the entries corresponding to the value according to one of the factorization relations; and
multiplying the dividend, the stored reciprocal of each of the retrieved entries and the compensation value by the multiplication circuit to generate the divided result of the dividend and the divisor.

18. The division operation method of claim 10 , wherein if the divisor is an exponent of 2, the division operation method further comprise:

Assignees

• Realtek Semiconductor Corp

Inventors

• Chuang Hung-Chang
• Chen Li-Ming

Classifications

• G06F2207/5354

  Using table lookup, e.g. for digit selection in division by digit recurrence · CPC title

• G06F2207/5356

  Via reciprocal, i.e. calculate reciprocal only, or calculate reciprocal first and then the quotient from the reciprocal and the numerator · CPC title

• G06F7/4873 Primary

  Dividing · CPC title

• G06F7/535

  Dividing only · CPC title