1. Field of the Invention
The present invention relates to a signal-processing apparatus and method usable as an either single-input, multiple-output or multiple-input, multiple-output digital filter.
2. Description of the Related Art
An either single-input, multiple-output or multiple-input, multiple-output digital filter is in widespread use in various service applications. The digital filter of this type is employed in, e.g., one system designed to locate sound at any position, and another system operable to add reflected sound to original sound to provide a feeling of soundscape.
The digital filter is classed as an IIR filter including a feedback portion and a FIR filter free thereof. The present description discusses the FIR filter.
FIG. 19(a) is a block diagram illustrating details of a prior art single-input, two-output time domain-designed FIR filter.
In FIG. 19(a), input signal “x” enters a FIR filter 5 through an input terminal 1. In the FIR filter 5, each delay device 8 delays input signal “x”, and the delayed input signal “x” becomes a delay signal. A multiplier 7 multiplies each of the delay signals by a predetermined coefficient. The multiplied delay signals are fed into an adder 9. The adder 9 adds the inputs together, thereby delivering the addition result as output signal “y1” to an output terminal 2.
Similarly, as illustrated in FIG. 19(b), input signal “x” enters a FIR filter 6 through the input terminal 1, and output signal “y2” leaves the FIR filter 6 through an output terminal 3.
FIG. 19(b) schematically illustrates the FIR filters 5, 6. When illustrated similarly to FIG. 19(b), a two-input, two-output system and a six-input, four-output system are configured as illustrated in FIG. 19(c) and FIG. 20, respectively. In FIG. 19(c), the adders 9 are additionally provided to the two-input, two-output system.
The FIR filters of FIG. 19 and FIG. 20 perform time-domain processing. As evidenced by FIG. 20, according to the time-domain processing, an increase in degree (the number of taps) of the FIR filters brings about a very complicated circuit structure.
It is known that frequency-domain processing instead of the time-domain processing provides a reduced number of times of calculation (multiplication, addition, and subtraction) per unit time. This is because a time domain convolution is comparable, in a frequency domain, to a simple product of corresponding elements between vectors.
The following discusses the frequency-domain processing. A time-domain signal is initially transformed into a frequency-domain signal for each predetermined time window using Discrete Fourier Transform. Fast Fourier Transform (FFT), a high-speed calculation method of the Discrete Fourier Transform, is often used to perform the Discrete Fourier Transform a reduced number of times of calculation. Subsequently, a product of corresponding elements between the transformed signal vector and a coefficient vector (frequency domain) is calculated.
Thereafter, the Inverse Fast Fourier Transform of the calculated product is performed to return the frequency-domain result to a time-domain result. This processing is suited for calculation to be made by a high-order FIR filter.
Details of the frequency domain-designed FIR filter are taught in non-patent reference No. 1 (“Fast Fourier Transform and its Applications”, chapter 5, written by Sagawa Masahiko and Kiya Hitoshi, Japan), and non-patent reference No. 2 (“Fast Fourier Transform and Convolution Algorithm”, chapters 3 to 4, written by Henri J. Nussbaumer, 1982).
As pointed out by the above non-patent references No. 1 and No. 2, the frequency-domain convolution is usually a circular convolution, and there is a need for a countermeasure to bring the circular convolution to a linear convolution that is similar to a time-domain convolution.
Non-patent references No. 1 and No. 2 introduce an overlap-save method and an overlap-add method by way of specific methods for the above.
The following discusses an exemplary overlap-save method with reference to FIG. 21, in which coefficient “h” is convoluted into a series of input signals “x” to determine a series of output signals “y”. In FIG. 21, “Re”, “Im”, and “Co” denote a real number, an imaginary number, and a complex number, respectively. These symbols are also used in the other drawings.
Assume that the present time window “Wn” has window length “N” (samples) and coefficient length “L” (samples). In this instance, a data renewal length is identified as “M”, and a relationship between “M”, “N”, and “L” is established as follows:M=N−L 
Time windows “Wn−1” and “Wn+1” are the immediately previous and next time windows, respectively. Time windows “Wn−1”, “Wn”, and “Wn+1” are equal in window length to each other, and are set to be overlapped with each other by the distance of coefficient length “L” (samples).
Each component in the present time window “Wn” of a series of input signals “x” is fed into a FFT unit 11 through a real number input portion “11a” thereof. An imaginary number input portion “11b” of the FFT unit 11 is unused, but data containing only “zero” (N-numbers of samples) is placed into the FFT unit 11 through the imaginary number input portion “11b”. This means that the components enter a single-system.
For coefficient “h”, a coefficient having length “L” is placed forward to add zero having length “M” to the rear of the coefficient having length “L”, thereby providing a time-domain real number coefficient having length “N”. A series of real numbers of coefficient “h” is fed into a FFT unit 10 through a real number input portion “10a” thereof. An imaginary number input portion “10b” of the FFT portion 10 is unused, but data containing only “zero” (N-numbers of samples) enters the FFT unit 10 through the imaginary number input portion “10b”. This means that the coefficients enter a single-system.
When the FFT unit 10 performs the window length “N”-based FFT of the real number coefficient as discussed above, then a coefficient vector “H” (a complex number, frequency domain) having length “N” is fed out of the FFT unit 10 through a complex output portion “10c” thereof.
Subsequently, in the series of input signals “x”, L-numbers of samples are taken out of the immediately previous time window “Wn−1” from the tail end of data used in the immediately previous time window “Wn−1”, while M-numbers of sample are taken out of the present time window “Wn” from the tail end of data in the present time window “Wn”. As a result, a series of real number signals having length “N” is provided. The series of real number signals having length “N” is fed into the FFT unit 11 through the real number input portion “11a”. When the FFT unit 11 performs the FFT of the series of real number signals having length. “N”, then data vector “X” (a complex number, frequency domain) having length “N” is emitted from the FFT unit 11 through a complex output portion “11c” thereof.
Thereafter, a complex-multiplying unit 12 performs the complex multiplication of coefficient vector “H” and data vector “X” for each element.
Assume that coefficient vector “H” and data vector “X” are “H=[H(1), H(2) to H(N)]” and “X=[X(1), X(2) to X(N)]”, respectively. The complex-multiplying unit 12 calculates in such a manner that a complex multiplication result is Y=H·X=[H(1)X(1), H(2)X(2) to H(N)X(N)]. Such calculation result “Y” is fed into an IFFT unit 13 through a complex input portion “13c” thereof.
The IFFT unit 13 performs the window length “N”-based Inverse Fast Fourier Transform (IFFT) of calculation result “Y”, thereby returning the frequency-domain calculation result “Y” to time-domain calculation result “Y”. As a result, a series of output signals “y” is fed out of the IFFT unit 13 through a real number output portion “13a” thereof. An imaginary number output portion “13b” of the IFFT unit 13 is unused.
L-numbers of samples (marked by “X” in FIG. 21) in the determined a series of output signals “y” at the head thereof are discarded because the L-numbers of samples are influenced by a circular convolution. As a result, signal data in the remaining M-numbers of samples is rendered as wanted series of output signals “y”.
The following discusses the overlap-add method with reference to FIG. 22. The overlap-add method provides substantially the same results as those from the overlap-save method. For example, to provide a series of real numbers “y” by convoluting coefficient “h” into a series of real numbers “x”, the same determination as above is made as to FFT window length “N” (samples), coefficient length “L” (samples), and data renewal length “M” (samples), and coefficient vector “H” having length “N”.
However, according to the overlap-add method, L-numbers of samples have data of “zero” from the tail end of input data in the present time window “Wn”. In addition, according to the overlap-add method, L-numbers of samples at the head of signal data provided by the IFFT unit 13 are added to L-numbers of samples from the tail end of obtained signal data in the immediately previous time window “Wn−1”.
In this way, M-numbers of samples are provided. Signal data in M-numbers of samples from the head of the series of output signals “y” is identified as wanted series of output signals “y”. At this time, the IFFT unit 13 takes L-numbers of samples out of time window “Wn”-related series of output signals “y” from the tail end of the same series of output signals “y”, and places the L-numbers of samples into a memory 14 for the purpose of addition in the next convolution.
The following assesses the number of times of calculation according to the overlap-save and -add methods. The assessments focus on the number of times of calculation for each of M(=N−L)-numbers of samples.
According to the overlap-save method,                FFT complex multiplication (N/2) Log2 (N−1);        Complex addition N Log2 (N);        Vector multiplication complex multiplication N;        IFFT complex multiplication (N/2) Log2 (N−1); and        Complex addition N Log2 (N).        
The total number of times of calculation is:                Complex multiplication N Log2 (N−1)+N; and        Complex addition 2N Log2 (N),        
where Log2 (N) denotes a logarithm of N to the base 2.
The overlap-add method provides a substantially similar number of times of calculation.
The FFT of coefficients is executed only once during activation, and can be separated from real time system processing relating to a series of input signals. Accordingly, the above-determined number of times of calculation excludes a coefficient FFT-related number of times of calculation.
Several methods based on the above-described processes have been proposed for achieving a reduced memory volume and a reduced number of times of calculation per unit time using properties of complex FFT.
Patent reference No. 1 (published U.S. Pat. No. 3,679,882) discloses a method for attaining the above purposes by executing each of the complex FFT and feedback once instead of performing each of the FFT and IFFT once.
Non-patent references No. 1 and No. 2 disclose another method (hereinafter called a “prior art improved method”). The following discusses the prior art improved method with reference to FIG. 23.
As illustrated in FIG. 23, according to the prior art improved method, the present time window “Wn” and the next time window “Wn+1” in a series of input signals “x” are used at a time. The time windows “Wn−1”, “Wn”, and “Wn+1” stand in the same relationship as above.
Data in time window “Wn” and that in time window “Wn+1” are fed into the FFT unit 11 through the real number input portion “11a” and the imaginary number input portion “11b”, respectively.
The FFT unit 11 performs the complex FFT of the entered data, thereby feeding complex number data vector “X” out of the FFT unit 11 through the complex output portion “11c” into the complex-multiplying unit 12.
Coefficient vector “H” is provided similarly to the previous discussion.
However, when the IFFT unit 13 performs the IFFT of calculation result “Y”, then time window “Wn”-related series of output signals “y” and time window “Wn+1”-related series of output signals “y” are fed out of the IFFT unit 13 through the real number output portion “13a” and the imaginary number output portion “13b”, respectively.
According to the prior art improved method, 2M-numbers of samples, twice as large as M-numbers of samples, can advantageously be processed the same number of times of calculation as that according to the overlap-save method of FIG. 21.
The methods as described above seek to provide an efficient single-input, single-output FIR filter.
To apply such efficiency to a single-input, multiple-output FIR filter and a multiple-input, multiple-output FIR filter, single-input, single-output FIR filters are arranged in parallel with each other in a manner similar to that in which the time domain-designed FIR filters are arrayed.
FIG. 24(a) and FIG. 24(b) illustrate a prior art single-input, two-output signal-processing apparatus and a prior art two-input, two-output signal-processing apparatus, respectively.
In the signal-processing apparatus of FIG. 24(a), the time domain-designed FIR filter of FIG. 19(b) is replaced by a frequency domain-designed FIR filter. In the signal-processing apparatus of FIG. 24(b), the time domain-designed FIR filters of FIG. 19(c) are replaced by frequency domain-designed FIR filters.
The signal-processing apparatus of FIG. 24(a) includes a FFT unit 15, IFFT units 16, 17, and complex-multiplying units 18, 19. The signal-processing apparatus of FIG. 24(b) includes a FFT unit 20, complex-multiplying units 21, 22, and adders 23, 24 in addition to components as illustrated in FIG. 24(a).
The following evaluates the number of times of calculation according to the prior art improved method.
According to the usual overlap-save method, a single-input, two-output frequency domain-designed filter provides the number of times of calculation as given below for each of M(=N−L)-numbers of samples:                FFT complex multiplication (N/2) Log2 (N−1);        Complex addition N Log2 (N);        Vector multiplication complex multiplication 2N;        IFFT complex multiplication N Log2 (N−1); and        Complex addition 2N Log2 (N).        
The total number of times of calculation is:                Complex multiplication (3N/2) Log2 (N−1)+2N; and        Complex addition 3N Log2 (N).        
In further accordance with the usual overlap-save method, a two-input, two-output frequency domain-designed filter provides the number of times of calculation as given below for each of M(=N−L)-numbers of samples.                FFT complex multiplication Log2 (N−1);        Complex addition 2N Log2 (N);        Vector multiplication complex multiplication 4N;        Vector addition complex addition 2N;        IFFT complex multiplication N Log2 (N−1); and        Complex addition 2 N Log2 (N).        
The total number of times of calculation is:                Complex multiplication 2N Log2 (N−1)+4N; and        Complex addition 4N Log2 (N)+2N.        
The use of the prior art improved method as illustrated in FIG. 23 makes it feasible to calculate 2M-numbers of samples the same number of times of calculation as above.
However, as evidenced by FIG. 23, the prior art improved method cannot start calculation until data from both of time windows “Wn” and “Wn+1” are ready for use. Accordingly, a problem with the prior art improved method is that a delay time until the data get ready for use is nearly twice as long as that according to the overlap-save method of FIG. 21 and that according to the overlap-add method of FIG. 22.
USPTO Backgrounds
USPTO Backgrounds