Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2002-08-16
2003-11-11
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06647403
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to a method and digital signal processing equipment implementing the method for performing a calculation in digital signal processing. The solution of the invention can be applied typically in GSM (Global System for Mobile communications) and WCDMA (Wideband Code Division Multiple Access) applications.
BACKGROUND OF THE INVENTION
Digital signal processors (DSP) employ algorithms in which inverse matrices are increasingly common. For the inverse of n*n matrices, A
−1
A=I is valid, A
−1
being the inverse matrix of A and I being the unit matrix of n*n. Inverse matrix operations require a plurality of divisions and square root calculations.
According to a prior art solution, diverse algorithms, such as the Newton-Raphson algorithm, may be used to carry out divisions and square root calculations in digital signal processing. These calculations require separate algorithms. In the Newton-Raphson algorithm, equation f(x)=0 is solved by calculating iteration cycles where an initial guess x
0
is made on the number to be calculated, i.e. an initial value x
0
is assigned. Function f′(x) is a derivative of function f(x), i.e. a tangent to the curve of function f′(x). Tangent f′(x) is a straight line touching curve f(x) at point x, i.e. it obtains the same value as f(x). In the first iteration cycle the equation to be calculated is
x
1
=
x
0
-
f
(
x
0
)
f
′
(
x
0
)
in the next iteration cycle
x
2
=
x
1
-
f
(
x
1
)
f
′
(
x
1
)
,
etc. Three or four iteration cycles are typically carried out.
The time it takes to perform the iterations is function-dependent. Consequently, when relatively time-consuming functions are concerned, slowness may become a problem in the above algorithms.
The Newton-Raphson algorithm, as well as other prior art algorithms, can be used both in fixed point and floating point processors, but for reasons of economy in particular, they are often used in fixed point processors (fixed point DSPs). A drawback of this is that after two, or at most three, iteration cycles the accuracy of the calculation cannot be improved any more because of limited code length. Therefore a problem arises from how to achieve sufficient accuracy, i.e. resolution.
When the prior art solution is implemented in a floating point processor (floating point DSP), a good resolution can be achieved. However, the drawback of the floating point DSP as compared with the fixed point DSP is poor code density. Hence, an operation performed in the floating point DSP requires more memory space than a corresponding operation in the fixed point DSP. This is naturally economically disadvantageous since the memory capacity needed in digital signal processing is usually high to begin with. Another problem with the floating point DSP is that the calculations it performs require more logic than fixed point DSPs, the floating point DSP being therefore also slower than the fixed point processor.
When implementing the above algorithms, the prior art solutions typically use a LUT table (Look-Up Table) for storing the desired numerical values. The numerical values are provided with addresses corresponding to their position in the LUT table, the addresses being used for selecting the values for algorithmic calculations. A LUT table occupies a lot of memory in the processor, which is economically disadvantageous.
One of the concrete problems arising from the above drawbacks of the prior art solutions is that if the algorithm implementation fails to provide a good resolution, the performance of the receiver may degrade too much.
To carry out divisions in digital signal processing, a plural number of chained conditional structures are required, which may be problematic to implement in digital signal processors employing a prior art solution. Moreover, a significant drawback of the prior art solutions is that they require separate algorithms for square root calculations and divisions.
BRIEF DESCRIPTION OF THE INVENTION
It is therefore an object of the invention to provide an improved method for digital signal processing and digital signal processing equipment implementing the method. This is achieved with a method for performing a digital signal processing calculation, the method employing a look-up table in which predetermined numerical values have been stored. The numerical values are inverse values of square roots of numbers; the look-up table is searched for the inverse value of the square root of a desired number; if the inverse value of the square root of the desired number is found in the look-up table, the inverse value of the square root of the number is retrieved from the look-up table; if the inverse value of the square root of the desired number is not found in the look-up table, the number is scaled such that the inverse value of the square root of the scaled number is found in the look-up table; the inverse value of the square root of the scaled number is retrieved from the look-up table; the inverse value of the square root of the scaled number is descaled to produce the inverse value of the square root of the desired number; the inverse value of the square root of the number is used to carry out a calculation.
The invention further relates to digital signal processing equipment for performing a calculation associated with digital signal processing, the processing equipment comprising a look-up table in which predetermined numerical values are stored. The numerical values are inverse values of square roots of numbers. The digital signal processing equipment comprises: means for searching the look-up table for the inverse value of the square root of a desired number; means for retrieving the inverse value of the square root of the number from the look-up table if the inverse value of the square root of the number in question is found; means for scaling the number if the inverse value of the square root of the number in question is not found in the look-up table such that the inverse value of the square root of the scaled number is found in the look-up table; means for retrieving the inverse value of the square root of the scaled number from the look-up table; and means for descaling the inverse value of the square root of the scaled number to produce the inverse value of the square root of the number. The digital signal processing equipment further comprises means for using the inverse value of the square root of the number to carry out a calculation.
The underlying idea of the invention is that the numerical values stored in the table are inverse values of the square roots of numbers and that the table is searched for the inverse value of the square root of a desired number. If the inverse value of the square root of the number in question is found in the look-up table, the inverse value of the square root of the number is retrieved from the table. If the inverse value of the square root of the number in question is not found in the look-up table, the number is scaled such that the inverse value of the square root of the scaled number is found in the look-up table. The inverse value of the square root of the scaled number is then retrieved from the table and the inverse value of the square root of the scaled number is descaled to produce the inverse value of the square root of the number. The inverse value of the square root of the number is then used for performing a calculation.
In the future, inverse matrix operations involving many divisions and square root calculations will occupy an increasingly central role in digital signal processors. The method and digital signal processing equipment of the invention provide a common algorithm implementation and look-up table for rapidly calculating divisions and square roots. With regard to divisions in particular, the number of conditional structures is smaller in the solution of the invention than in prior art solutions, which in turn provides short execution times. The look-up table of the invention which is compressed in a small memory space
Malzahn David H.
Pillsbury & Winthrop LLP
LandOfFree
Method and digital signal processing equipment for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and digital signal processing equipment for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and digital signal processing equipment for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3178044