Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-06-22
2003-06-03
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S319000, C708S422000
Reexamination Certificate
active
06574649
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to convolution of signals and, in particular, discloses an efficient form of time domain based convolution.
BACKGROUND OF THE INVENTION
The process of convolution is well known to those skilled in the art of signal processing and normally involves convolving two different signals together to produce an output signal. Turning initially to
FIG. 1
, in the audio processing field, it is common to convolve
1
an input signal
2
with an impulse response
3
to produce an output signal
4
. The convolution process can be utilised to equalise or add spatial components to the audio input signal
2
so as to add “color” to the input signal.
Unfortunately, the convolution process can involve excessive computational resources. In one efficient form of known convolution process, hereinafter termed a “frequency domain convolution process”, an example of which is depicted in
FIG. 2
, the input signal
2
is converted into the frequency domain by means of a Fast Fourier Transform (FFT)
6
. The impulse response is similarly converted to the fourier domain by a Fast Fourier Transform process
7
. The two fourier components are then multiplied element-by-element
8
with the result being Inverse Fast Fourier Transformed (IFFT)
9
to produce a convolved output signal
10
. The process of
FIG. 2
is well known in the art, and there are many other efficient methods for carrying out a fourier domain convolution on input signals. An example of an efficient form of frequency domain process is given in PCT International Application No. PCT/AU93100330 entitled “Digital Filter Having High Accuracy and Efficiency” assigned to the present applicant.
Another known form of performing a convolution process is in the time domain and is illustrated in FIG.
3
. In this process
20
, an input signal
21
is forwarded to a series of delay blocks
22
with the output of the delay block
22
being forwarded to a subsequent delay block eg
23
in addition to being multiplied
24
with a coefficient a
1
. The outputs of each of the coefficient multiplications are then summed
26
to form an output
27
. Hence, (for each time step input
21
), the following summation, which represents a convolution, is formed.
y
(
n
)
=
∑
i
=
0
N
-
1
a
i
x
(
n
-
i
)
Unfortunately, the time domain convolution process requires an excessive amount of computational resources and, as a result, the frequency domain process of
FIG. 2
is more likely to be utilised in instances where the impulse response length, N, is large.
In any convolution process, and in particular audio convolution with an impulse response function, it is desired to perform as efficient and effective a convolution as possible. It would therefore be desirable to provide for an alternative efficient convolution process.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide for an efficient convolution process.
In accordance with a first aspect of the present invention, there is provided a convolution method of time domain convolving an input signal with a second signal comprising the steps of: (a) dividing the second signal into a series of segments; (b) determining a magnitude envelope for each of the segments; (c) scaling the signal values within each segment relative to the envelope to produce corresponding segment scaled signal values; (d) multiplying the segment scaled signal values by a corresponding input signal value to produce corresponding segment output values; (e) scaling the segment output values by a segment scale factor to produce corresponding scaled segment outputs; and (f) adding the scaled segment outputs to produce a time domain output.
The scaling step (c) further can comprise a quantisation of the signal values within each segment. The segment scaled signal values can be quantised so that the quantisation noise is spectrally altered to reduce the impact of the quantisation process. The quantisation process can be further adapted to simplify the use of the segment scaled signal values in a multiplication process. For example, preferably the quantisation process is further adapted so that each element of the segment scaled signal values is represented as a power of 2 multiplied by one of a small set of mantissa values.
Further, the initial filtering process can be chosen such that the inverse filter is composed of simplified coefficients.
In accordance with a further aspect of the present invention, there is provided a convolution method of time domain convolving an input signal with a second signal to produce a time domain output comprising the steps of: (a) dividing the second signal into a series of segments; (b) determining a magnitude envelope for each of the segments; (c) scaling the signal values within each segment relative to the envelope to produce corresponding segment scaled signal values; (d) multiplying the segment scaled signal values by a corresponding input signal value to produce corresponding segment output values; (e) summing the corresponding segment output values for each of the segment together to produce a summed segment output value for each of the segments; (f) scaling the summed segment output values by a segment scale factor to produce corresponding scaled segment outputs; (g) adding the scaled segment outputs to produce a time domain output.
The method can further comprise the step of initially filtering the coefficient values so as to alter the expected spectral error in accordance with predetermined requirements.
The present invention is ideally suited to the case where the second signal is an impulse response signal and the input signal is an audio input signal.
The present invention also discloses efficient forms of hardware and software implementations of the invention.
In accordance with a further aspect of the present invention, there is provided an apparatus for convolving a first signal comprising a first series of data values with a second signal comprising a second series of data values, the apparatus comprising: data input means for inputing the first series of data values in a consecutive manner to a first multiplier means; control input means for inputting control values representative of the second series of data values in a consecutive manner; first multiplier means for multiplying the data values by one of a predetermined number of first multiplier values as determined by a current input control value to produce a multiplied data value; adding means for adding the multiplied data value to a previously accumulated data value producing a current adder output value; scaling means for scaling the current adder output value by one of a predetermined number of first scaling values as determined by the current input control value to produce a new accumulated data value; and accumulator means for storing the accumulated data value.
The first multiplier means further can comprise a series of multiplier units each forming the product of a current data value with a constant; and a selection means interconnected to each of the multiplier units and adapted to select and output one of the products as the multiplied data value as determined by the current input control value. The first multiplier means further can comprise complementor means for complementing the multiplied data value.
The scaling means further can comprise a second series of multiplier units each forming the scaled product of the current adder output value with a constant; and a selection means interconnected to each of the multiplier units and adapted to select and output one of the scaled products as the new accumulated data value as determined by the current input control value.
In accordance with a further aspect of the present invention, there is provided an apparatus for convolving a first signal comprising a first series of data values with a second signal comprising a second series of data values, the apparatus comprising: data input means for inputing the first series of data values in a consecutive manner to a series of conv
Fulwider Patton Lee & Utecht LLP
Lake Technology Limited
Malzahn David H.
LandOfFree
Efficient convolution method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient convolution method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient convolution method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3159466