Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-05-23
2003-09-23
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S321000
Reexamination Certificate
active
06625629
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to the field of digital signal processing, and more particularly to a system and method for signal processing using an improved convolution technique.
BACKGROUND OF THE INVENTION
Digital filters are often important components of digital signal processors (DSPs). A common type of digital filter is a finite impulse response (FIR) filter that processes an input signal by convolving the input signal with the filter's impulse response. This convolution may be performed using various methods. One method involves direct convolution. Direct convolution has no inherent latency, but its computational cost is often unacceptably high when long convolutions are to be computed in real-time. If computations were instantaneous, each sample input to the direct convolution algorithm would yield a convolved output sample. Therefore, the input to output latency inherent in the convolution algorithm structure is null. The actual latency of direct convolution results from the time necessary to compute each output sample. If the convolving filter is relatively short, the computation time is smaller than the sample period, and thus the latency is of only one sample. However, the computational cost of direct convolution increases linearly with the length of the convolving filter, which makes this technique unsuitable for performing long convolutions (thousands of sampling points) in real-time.
The cost problem may be addressed using frequency domain block convolution. This computationally efficient technique is based upon the fact that the Fourier Transform of the convolution of two signals is equal to the product of the Fourier Transforms of each individual signal. The Fast Fourier Transform (FFT) algorithm may be used in this approach, and consequently the cost per sample of these convolution techniques increases logarithmically with the length of the convolving filter (the “block”), which keeps cost at a more acceptable level when dealing with long convolutions. This type of convolution method may be referred to as a “single-block” convolution.
However, block processing techniques have an inherent input to output latency equal to the length of the block since the input sample block must be full in order to start computing the output sample block. This makes this kind of algorithm unsuitable for performing long convolutions in real-time due to the high latency. For example, when rendering three-dimensional audio, a typical room response can be several seconds long, which is far above acceptable latency levels for real-time audio rendering.
An existing approach to achieve low input to output latency while keeping computational cost at an acceptable level is to section the convolving filter into shorter blocks and perform several frequency-domain block convolutions in parallel, one for each shorter block. The output is obtained by summing the delayed outputs of the shorter convolutions, according to the superposition principle. The block length is chosen according to a specified input to output latency. This type of convolution may be referred to as a “multiple-block” convolution. Multiple block convolution may use blocks of uniform or non-uniform size.
One or more of the previously described methods may be adequate for performing many digital signal processing tasks. However, as applications require increasingly fast and complex digital signal processing, new convolution methods are needed to meet these demands.
SUMMARY OF THE INVENTION
According to the present invention, disadvantages and problems associated with previous systems and methods for signal processing have been substantially reduced or eliminated.
According to one embodiment of the present invention, a system for signal processing using one or more filters includes a controller that partitions an impulse response of a filter into a plurality of impulse response blocks and calculates a Discrete Fourier Transform (DFT) of each impulse response block using a Fast Fourier Transform (FFT) algorithm. A processor coupled to the controller receives an input sample block including samples of a signal to be processed and receives the DFT of each impulse response block from the controller. The processor calculates a DFT of the input sample block using an FFT algorithm, performs a spectral multiplication of the DFT of the input sample block with the DFT of each impulse response block, overlap-adds the blocks resulting from each spectral multiplication to create an output spectral block, performs an inverse FFT on the output spectral block to create an output sample block.
The system and method of the present invention provide a number of important technical advantages. The present invention allows long convolutions to be computed with low input to output latency and minimal computational cost. The present invention is particularly well-suited for situations where long convolutions are to be computed in parallel and outputs of these convolutions are to be mixed. Such applications include three-dimensional audio rendering, audio effects (for example, sound reverberation), and surround sound or virtual surround sound technologies. The present invention may be used for any application that involves the use of convolution techniques, including but not limited to graphics or video processing.
Applications requiring long convolutions often use computationally expensive FIR filters in a parallel structure. For example, in three-dimensional audio rendering, each parallel FIR branch models an acoustic path (either a direct path or a reflection) that exists between a source and a virtual listener. The combination of these filters requires long convolutions (often thousands of sampling points), such that previous convolution methods are either too computationally expensive or introduce too much latency for use in real-time audio or video rendering. These previous methods typically either reduce computational cost at the expense of unacceptably high latency (for real-time applications) or they reduce latency at the cost of unacceptably high computational cost. The present invention provides a convolution technique that optimizes the tradeoff between latency and computational cost so as to allow for minimum-cost convolution, while satisfying latency requirements of real-time applications. Other technical advantages are readily apparent to those skilled in the art.
REFERENCES:
patent: 4992967 (1991-02-01), Auvray
patent: 5270953 (1993-12-01), White
patent: 5473555 (1995-12-01), Potter
patent: 2001/0032225 (2001-10-01), Tal et al.
William G. Gardner; “Efficient Convolution Without Input/Output Delay;” Journal of the Audio Engineering Society Audio/Acoustics/Applications, vol. 43, No. 3; pp. 127-136, Mar. 1995.
Pierre Duhamel and Martin Vetterli; “Improved Fourier and Hartley Transform Algorithms: Application to Cyclic Convolution of Real Data;” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-35, No. 6; pp. 818-824, Jun. 1987.
R. Meyer, R. Reng and K. Schwarz; “Convolution Algorithms on DSP Processors;” 1991 International Conference on Acoustics, Speech, and Signal Processing, vol. 3; pp. 2193-2196, May 14-17, 1991.
Alan V. Oppenheim and Ronald W. Schafer; “Discrete-Time Signal Processing;” pp. 553-561; 720-722, 1975.
Henrik V. Sorensen and C. Sidney Burrus; “Fast DFT and Convolution Algorithms;” Handbook for Digital Signal Processing; pp. 491-517, 1993.
Lee & Hayes PLLC
Malzahn David H.
Microsoft Corporation
LandOfFree
System and method for signal processing using an improved... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for signal processing using an improved..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for signal processing using an improved... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3082114