METHOD AND APPARATUS FOR APPROXIMATING AN UPPER-BOUND LIMIT FOR AN ABSOLUTE VALUE OF A COMPLEX NUMBER OR NORM OF A TWO-ELEMENT VECTOR

• US 20090177723A1
• Filed: 01/08/2008
• Published: 07/09/2009
• Est. Priority Date: 01/08/2008
• Status: Active Grant

• Current Assignee: Himax Technologies Ltd. (Himax Technologies Incorporated)
• Original Assignee: Himax Technologies Ltd. (Himax Technologies Incorporated)
• Inventors: Tsai, Kuo-Shih
• Granted Patent: US 8,443,016 B2
• Time in Patent Office: Days
• US Class Current: 708/201
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Abstract

A method for approximating an upper bound limit for the absolute value of a complex number or the norm of a two-element vector is disclosed. An upper bound approximation algorithm is used to minimize software implementation efforts and make the hardware implementation less expensive. The hardware implementation of the upper bound approximation algorithm only requires a multiplier element and an adder element. Therefore, this algorithm can be implemented anywhere in a digital signal processing apparatus without increasing cost significantly. Moreover, the hardware employing the present invention can be implemented in a pipeline architecture configuration to achieve a real time function in digital audio or digital video applications.

Claims

1. A method for approximating an upper-bound limit for the absolute value of a complex number or the norm of a two-element vector, comprising the steps of:

initializing the absolute values of a real part and an imaginary part of the complex number;

generating the upper-bound limit using an upper-bound function according to an upper bound approximation means; and

detecting whether an overflow condition exists.

2. The method of claim 1, further comprising:

generating an output to indicate the detection of an overflow condition when the overflow condition is detected.

3. The method of claim 1, wherein the absolute value for the real part of the complex number and the imaginary part of the complex number are obtained by converting the negative values of these two parts into a positive value by a 2'"'"'s complement method.

4. The method of claim 1, wherein the part with a smaller absolute value of the complex number is obtained by comparison.

5. The method of claim 1, wherein a first variable is defined to equal to the absolute value of the real part or imaginary part of the complex number having the minimum absolute value.

6. The method of claim 1, wherein a second variable is defined to equal to the absolute value of the real part or imaginary part of the complex number having the maximum absolute value.

7. The method of claim 1, wherein the complex number is normalized.

8. The method of claim 1, wherein the two-element vector is normalized.

9. The method of claim 2, wherein the output is the absolute value of the real part of the complex number and the absolute value of the imaginary part of the complex number in the initialization.

10. The method of claim 2, wherein the overflow condition is detected by comparing the upper bound against a calculated result of the absolute value of the complex number from a second method.

11. The method of claim 1, wherein the upper bound function receives a first variable having the minimum absolute value and a second variable having the maximum absolute value among the absolute values of the real part and the imaginary part of the complex number, multiplies the first variable with a parameter according to the upper-bound approximation means, and adds the multiplied product with the second variable as an upper bound output.

12. The method of claim 11, wherein the parameter is (√

{square root over (2)}−

1).

13. The method of claim 11, wherein the parameter is greater than (√

{square root over (2)}−

1).

14. The method of claim 11, wherein the parameter is greater than (√

{square root over (2)}−

1) and less than one half.

15. The method of claim 1, wherein the method is used in a digital broadcasting system, including the Digital Audio Broadcasting (DAB) system and/or the Digital Video Broadcasting (DVB) system.

16. The method of claim 1, wherein the method is used in a digital signal processor (DSP).

17. An apparatus for approximating an upper-bound limit for the absolute value of a complex number or the norm of a two-element vector, comprising:

a comparator element configured to compare the absolute values of a real part of the complex number and an imaginary part of the complex number; and

an upper bound function circuit to output an upper bound according to an upper bound approximation means.

18. The apparatus of claim 17, wherein the comparator element further comprises a 2'"'"'s complement circuit to convert the negative number into a positive value.

19. The apparatus of claim 17, wherein the comparator sends the real part and the imaginary part with an indication that defines the part having the larger absolute value and the part having the smaller absolute value.

20. The apparatus of claim 17, wherein the upper bound function circuit outputs the upper bound limit for the absolute value of the complex number comprises a multiplier element configured to multiply the part with the smaller absolute value with a parameter according to the upper bound approximation algorithm to form a multiplied product, and an adder element configured to add the multiplied product with the part with the larger absolute value.

21. The apparatus of claim 20, wherein the parameter is (√

{square root over (2)}−

1).

22. The apparatus of claim 20, wherein the parameter is greater than (√

{square root over (2)}−

1).

23. The apparatus of claim 20, wherein the parameter is greater than (√

{square root over (2)}−

1) and less than one half.

24. The apparatus of claim 17, wherein the apparatus is used in a digital broadcasting system, including the Digital Audio Broadcasting (DAB) system and/or the Digital Video Broadcasting (DVB) system.

25. The apparatus of claim 17, wherein the apparatus is used in a digital signal processor (DSP).