JP4049720B2 - High-speed convolution approximation method, apparatus for implementing this method, program, and storage medium - Google Patents

Description

  The present invention relates to a high-speed convolution approximation method, an apparatus, a program, and a storage medium for performing the method, and in particular, a high-speed convolution approximation method for performing a convolution operation between a digital signal and a finite-length impulse response filter at approximately high speed. The present invention relates to an apparatus, a program, and a storage medium for executing the method.

High-speed execution of a convolution operation between a digital signal and a finite impulse response filter (FIR filter) is useful in efficiently realizing adaptive signal processing that requires a large-scale convolution operation such as echo cancellation. is there. This convolution operation can be realized based on the overlap-save method described in Non-Patent Document 1 as an example.
A conventional example of a high-speed convolution operation device using this overlap-save method will be described with reference to FIG.

  In FIG. 7, reference numeral 101 denotes an impulse response frequency characteristic holding unit. This impulse response frequency characteristic holding unit 101 has a (fast) discrete Fourier transform into an array obtained by combining zero arrays so that the overall length becomes 2L in the second half of the array h of filter impulse responses having a finite length L or less. This is a part that holds 2L coefficients obtained by applying transformation (FFT or DFT).

Reference numeral 102 denotes an input signal frequency characteristic holding unit. The input signal frequency characteristic holding unit 102 is a part that holds 2L coefficients obtained by performing discrete frequency conversion on an array that has been accumulated back to the past 2L points of the input signal x.
Reference numeral 103 denotes a combined signal frequency characteristic generation unit. The synthesized signal frequency characteristic generation unit 103 multiplies the coefficient held by the impulse response frequency characteristic holding unit 101 and the coefficient held by the input signal frequency characteristic holding unit 102 for each discrete frequency to obtain 2L synthesized signal frequencies. This is a part for generating a conversion coefficient.
Reference numeral 104 denotes a composite signal array inverse transform unit. The composite signal array inverse transform unit 104 performs inverse discrete frequency transform on the composite signal frequency transform coefficient generated by the composite signal frequency characteristic generation unit 103 by, for example, inverse (high-speed) discrete Fourier transform (IFFT, IDFT). It is.
Reference numeral 105 denotes a window overlay. The windowing superimposing unit 105 multiplies the 2L-point composite signal array obtained from the composite signal array inverse transform unit 104 by a 2L-point window function that multiplies the first half L point by zero and the second half L point by 1 times. A combined signal of point L is obtained, and this is a part that is combined with the latter half point L of the array of combined signals obtained in the same manner with respect to the input signal in the past of point L, thereby obtaining output signal y.

Referring to FIG. 8, this is another conventional example that is almost the same as the conventional example of FIG. 7, and a signal processing unit 106 is connected between the synthesized signal frequency characteristic generating unit 103 and the synthesized signal array inverse transform unit 104. In this case, it corresponds to the one that realizes noise removal and other signal processing. Although this signal processing may cause output distortion, this distortion can be reduced by causing the windowing superimposing unit 105 to smoothly superimpose the output signal one step before. This smooth superposition method itself is described in Patent Document 1 related to the application of the patent applicant as a similar technique.
JP 2003-132026 A JJShynk, `` Frequency-domain and .multi-rate adaptive filtering, '' IEEE Signal Processing Mag., Vol. 9, no. 1, pp. 14-37, Jan. 1992.

  As can be understood from the fact that the fast convolution operation device based on the overlap-save method shown in FIG. 7 multiplies the first half L point of the synthesized signal by the windowing superimposing unit 105, it is actually necessary after the inverse transformation. The combined signal is point L. Nevertheless, the composite signal array inverse transform unit 104 performs inverse transformation of 2L points, but eliminates the influence of cyclic convolution in discrete frequency transformation, and obtains the linear convolution and output that are originally required. It is inevitable that the inverse transformation is performed at the 2L point.

  The present invention provides a high-speed convolution approximation method with little degradation in accuracy even when the above-described 2L point inverse transform is replaced with an L point inverse transform, and an apparatus, program, and storage medium for executing this method. In particular, another conventional example illustrated and described with reference to FIG. 8 adds a signal processing unit 106 between the combined signal frequency characteristic generating unit 103 and the combined signal array inverse transform unit 104, where noise removal and other signals are added. In order to suppress output distortion caused when processing is performed, the windowing superimposing unit 105 smoothly superimposes the output signal one step before, and a more suitable high-speed convolution approximation method, an apparatus for performing this method, A program and a storage medium are provided.

In a high-speed convolution approximation method for fast approximation of a convolution operation between an input digital signal sequence and a finite-length impulse response sequence, a 2L point discrete frequency transform coefficient is obtained based on the finite-length impulse response sequence. the calculated discrete frequency transform coefficients of 2L point based on the digital signal sequence, by multiplying the discrete frequency transform coefficients of the digital signal sequence and the discrete frequency transform coefficients of the finite impulse response series for each corresponding discrete frequency generates a composite signal frequency transform coefficients of 2L point, the discrete frequency sequence Te odor lowest of the combined signal consisting of a frequency conversion coefficient element number 2L and even-numbered, odd-numbered sequence consisting of the combined signal frequency coefficients from coefficients corresponding to the lowest discrete frequencies of the odd-numbered discrete frequency coefficient array in the number of elements it consists coefficients corresponding to the discrete frequencies L To 0, 1, 2,. . . , L−1, the 0th element is the real part of the value corresponding to the imaginary part of the 0th coefficient of the odd-numbered discrete frequency coefficient array, and l (where l is 1) , 2,..., L−1) element is the l th coefficient of the odd numbered discrete frequency coefficient array from the value of the real part of the L−1 number coefficient of the odd numbered discrete frequency coefficient array The value corresponding to 1/2 of the value obtained by subtracting the value of the real part of the odd-numbered discrete frequency coefficient array is the imaginary part, and the value of the imaginary part of the l-th coefficient of the odd-numbered discrete frequency coefficient array and L− of the odd-numbered discrete frequency coefficient array a value corresponding to 1/2 of the sum of the values of the imaginary part of the first factor is obtained by the real part, search of a new sequence number of elements L, and this new arrangement, the combined signal frequency conversion by adding the even-numbered consists coefficients corresponding to discrete frequency sequence in coefficients, elements To obtain an addition sequence of L, then perform an inverse discrete frequency transform of the addition sequence, after the windowing the signal sequence of inverse discrete frequency transform result of the addition sequence processing, similarly windowed processed signals to past and A high-speed convolution approximation method for generating an approximate convolution operation output signal sequence by performing the superimposing process is constructed.

Then, according to claim 2 in the fast convolution approximation apparatus for approximating a fast convolution operation between the input digital signal sequence and finite impulse response series, holds a discrete frequency transform coefficients 2L point of the finite impulse response series the impulse response frequency characteristic holding unit 101, an input signal frequency characteristic holding unit 102 for holding the discrete frequency transform coefficients 2L point of said digital signal sequence, discrete frequency transform coefficients of the finite impulse response series with the digital signal sequence Te sequence smell of discrete and frequency transform coefficient by multiplying for each corresponding discrete frequency synthetic signal frequency characteristic generation unit 103 for generating a composite signal frequency transform coefficients of 2L point, the composite signal composed of a frequency conversion coefficient element number 2L and even-numbered the lowest discrete frequencies, the odd-numbered discrete sequence consisting of the combined signal frequency coefficients 0,1,2 from the coefficient in the order corresponding to the lowest discrete frequencies of the odd-numbered discrete frequency coefficient array element number L consisting of coefficients corresponding to the wave number,. . . , L−1, the 0th element is the real part of the value corresponding to the imaginary part of the 0th coefficient of the odd-numbered discrete frequency coefficient array, and l (where l is 1) , 2,..., L−1) element is the l th coefficient of the odd numbered discrete frequency coefficient array from the value of the real part of the L−1 number coefficient of the odd numbered discrete frequency coefficient array The value corresponding to 1/2 of the value obtained by subtracting the value of the real part of the odd-numbered discrete frequency coefficient array is the imaginary part, and the value of the imaginary part of the l-th coefficient of the odd-numbered discrete frequency coefficient array and L− of the odd-numbered discrete frequency coefficient array The odd-numbered component imaginary part extraction unit 107 that obtains a new array of the number of elements L, which is a real part of a value corresponding to ½ of the sum of the imaginary part value of the first coefficient, and this new an array consists of coefficients corresponding to the even-numbered discrete frequencies in the combined signal frequency transform coefficient sequence By adding, to give the addition sequence of the number of elements L, an adder array inverse transform unit 108 to perform inverse discrete frequency transform of the addition sequence, windowing the signal sequence obtained from the adder array inverse transform unit 108 After the processing, a high-speed convolution approximation apparatus including a windowing superimposing unit 105 ′ that similarly performs a convolution process with a signal subjected to windowing processing in the past and generates an approximate convolution operation output signal sequence is configured.

A third aspect of the present invention provides a high-speed convolution approximation program for causing a computer to function as each component of the high-speed convolution approximation apparatus according to the second aspect.

  Further, a storage medium storing the high-speed convolution approximation program according to claim 4 is configured.

  The high-speed convolution approximation method according to the present invention, the apparatus, the program, and the storage medium for executing the method perform the desired convolution operation in each discrete frequency domain, or after executing it as a lower-order convolution operation. By performing inverse discrete frequency conversion with a small number of points and obtaining an output approximately, the result of convolution can be output approximately with a small amount of computation. In addition, by giving the output of the odd component imaginary part extraction unit to the output of the composite signal frequency characteristic generation unit and selecting the window coefficient in the windowing unit, a highly accurate output with the effect of approximation error being suppressed to a maximum is obtained. be able to.

The best mode for carrying out the invention will be described with reference to the embodiment of FIG.
In the embodiment of FIG. 1, the impulse response frequency characteristic holding unit 101, the input signal frequency characteristic holding unit 102, and the combined signal frequency characteristic generation unit 103 have the same configuration as that of the previous example.
1 differs from the prior art example of the embodiment of FIG. 1 in that 2L synthesized signal frequency conversion coefficients obtained from the synthesized signal frequency characteristic generation unit 103 are 0, 1, 2,. . . . , 2L-1 and a number, and an odd-numbered component imaginary part extraction unit 107 is provided for odd-numbered coefficients. The odd component imaginary part extraction unit 107 is realized as follows. Assume that the odd-numbered coefficient array is Yo (l), (l = 0, 1, 2,..., L−1). For Yo (l)
Z (0) = image (Yo (0))
Z (l) = j (-Yo (l) + Yo (L-1) ^* ) / 2,
( Where l = 1, 2,..., L-1 ) (1)
Z (l), (l = 0, 1, 2,..., L−1) is obtained, and this is used as the output of the odd component imaginary part extraction unit 107. Where j ² = −1, imag (x + jy) = y, (x, y
Is a real number), * represents a conjugate.

  This embodiment further includes an addition array inverse transform unit 108. Here, the array of even-numbered coefficients among the 2L synthesized signal frequency conversion coefficients obtained from the synthesized signal frequency characteristic generation unit 103 is represented by Ye (l), (l = 0, 1, 2,... L-1), and this Z (l) is input to the addition array inverse transform unit 108. In this addition array inverse transform unit 108, S (l) = Z (l) + Ye (l), (l = 0, 1) obtained by adding Z (l) and Ye (l) for each corresponding l. , 2,..., L-1) is subjected to inverse discrete frequency transformation on the L point, and the inverse transformed signal s (k) of S (l), (k = 0, 1, 2,. , L-1). The windowing superimposing unit 105 ′ of this embodiment is the same as the configuration of [Patent Document 1], and the window coefficients w (k) and (k = 0, 1, 2, ..., L-1)) to obtain s (k) w (k), and for the first half L / 2 points, s (k) w (k) of one step in the past The output signal y at the L / 2 point is output by adding the latter L / 2 point. Also, for the L / 2 point in the second half of s (k) w (k) obtained in the current step, the signal added to the first half L / 2 point in s (k) w (k) obtained in the next step Is stored and retained. Thereafter, this step is repeated. Here, the interval of the steps to be processed has been described as L / 2, but this interval does not necessarily have to be L / 2.

Here, the operation principle of the embodiment of the high-speed convolution approximation apparatus described above will be described.
Assuming that the combined signal frequency characteristic generated by the combined signal frequency characteristic generation unit 103 is Y (l), (l = 0, 1, 2,..., 2L−1), as shown in FIG. It is expressed as the sum of an even numbered component and an odd numbered component. The inverse discrete frequency transform of the array consisting of the original Y (l), (l = 0, 1, 2,..., 2L−1) is performed using the first half L elements yc (k), (k = 0, 1, 2,..., L-1) and the latter half L elements yl (k), (k = 0, 1, 2,..., L-1) have different meanings. That is, yl (k) is a signal that completely matches the linear convolution operation of the input signal x and the filter impulse response h to the high-speed convolution approximation device, but yc (k) is unnecessary due to the influence of the cyclic convolution. It is a serious signal. In the conventional window overlap unit 105 of FIG. 7, yc (k) is multiplied by zero to completely suppress the influence. Also, in FIG. 2, an inverse discrete frequency transform of an array in which only even-numbered components of Y (l), (l = 0, 1, 2,..., 2L−1) are left and odd-numbered are zero. Is an array in which two L signal sequences a (k) and (k = 0, 1, 2,..., L−1) are arranged to be 2L points. Similarly, an inverse discrete frequency transform of an array in which only odd-numbered components of Y (l), (l = 0, 1, 2,..., 2L−1) are left and even-numbered is zero is L-point signal sequence b (k), (k = 0, 1, 2,..., L−1) and −b (k), (k = 0, 1, 2,. .., L-1) are combined to form a 2L point. Here, the relationship yc (k) = a (k) −b (k), yl (k) = a (k) + b (k) holds.

  Now, in this embodiment, it is considered that only yl (k) is obtained by inverse discrete frequency transformation at point L. Referring also to FIG. 3, Y (l), Y (l) of L point reconstructed by only the even-numbered components of Y (l), (l = 0, 1, 2,..., 2L−1), ( l = 0, 1, 2,..., L-1), the inverse discrete frequency transform is a (k), (k = 0, 1, 2,..., L-1) itself. is there. On the other hand, Yo (l) of L point reconstructed only by odd-numbered components of Y (l), (l = 0, 1, 2,..., 2L−1), (l = 0, 1, 2,..., L-1) is an inverse discrete frequency transform that uses exp (−j for each element of b (k), (k = 0, 1, 2,..., L−1). (Πk) / L), (k = 0, 1, 2,..., L−1) and not b (k) itself. Therefore, this embodiment focuses on the imaginary part of exp (−j (πk) / L) · b (k). Using sin ((. Πk) / L) · b (k) which is the imaginary part, an approximation of a (k) + b (k), that is, yl (k) is expressed as a (k) + sin ((. Πk ) / L) · b (k). The outline of sin ((. πk) / L) is as shown in FIG. For this reason, the odd component imaginary part extraction unit 107 of FIG. 1 preliminarily calculates Yo (l) so that the inverse discrete frequency transform matches sin ((. Πk) / L) · b (k) (expression The above-described processing according to 1) is performed. All mathematically equivalent variations based on this principle are intended embodiments of the invention. The error between {a (k) + b (k)} and {a (k) + sin ((. Πk) / L) · b (k)} is {1-sin ((. Πk) / L ) · B (k)}, and takes an error distribution along the shape of {1-sin ((. Πk) / L)} as shown in FIG. That is, k = 0, 1, 2,. . . . , L-1 are concentrated at both ends. However, since the windowing superimposing unit 105 'multiplies the window coefficient in order to superimpose the output of the previous step every L / 2 points, the influence of the error is further reduced. For example, if the window coefficient is a Hanning window {0.5-0.5 cos ((2πk) / L)}, (k = 0, 1, 2,..., L−1), it is shown in FIG. It will be appreciated that there will be an error distribution and the absolute magnitude of the error will be reduced.

As the window coefficients used in the windowing superimposing unit 105 ′ in FIG. 1, k = 0, 1, 2,. . . . , L-1 having a distribution that becomes smaller as it approaches the both ends of the range of L-1, can be employed.
The frequency characteristic of the input signal held in the input signal frequency characteristic holding unit 102 is a result of performing discrete frequency conversion by adding a zero element to an input signal array having fewer than 2L points to form an array of 2L points. It can be. Further, the size of the output array in the window superimposing unit 105 ′ depends on the step interval, and the case where it is smaller or larger than L / 2 is included in the embodiment of the present invention.

  Furthermore, even when the filter impulse response array h is longer than L, the present invention can be implemented as follows. Here, the length of the array h of filter impulse responses is NL + M (N and M are integers satisfying N ≧ 1 and 0 ≦ M <L). At this time, the impulse response frequency characteristic holding unit 101 divides h into lengths L to obtain N length L arrays and one length M array. N + 1 sets of frequency characteristic arrays having a length of 2L, which are obtained by combining zero arrays so as to be 2L and performing discrete frequency conversion, are held. On the other hand, the input signal frequency characteristic holding unit 102 holds the arrangement of the input signal frequency characteristics up to the past N steps together with the arrangement of the input signal frequency characteristics of the current step, that is, a total of N + 1 sets of length 2L inputs. Holds an array of signal frequency characteristics. On the other hand, the synthesized signal frequency characteristic generation unit 103 is provided for each frequency number for each corresponding array of N + 1 sets of frequency characteristic arrays held in the impulse response frequency characteristic holding unit 101 and the input signal frequency characteristic holding unit 102. Multiplication processing is performed, and the obtained array of N + 1 sets of multiplication results is added for each frequency number to generate 2L synthesized signal frequency conversion coefficients. If this combined signal frequency conversion coefficient is used and the processing described above is performed, the present invention can be implemented even when the filter impulse response array h is longer than L.

  Assuming that the array h of the input signal x and the filter impulse response is a real number, when the discrete Fourier transform is used for the discrete frequency transform, a calculation that can be omitted is included in the foregoing because of the symmetry of the array of transform coefficients. It is obvious that the embodiment omits such calculation and is also included in the present invention.

The figure explaining an Example. The figure explaining the property of a synthetic signal frequency characteristic. The figure explaining the property of the synthetic | combination signal frequency characteristic noticed in an Example. The figure which shows the shape of the imaginary part of exp (-j ((pi) k) / L) * b (k). The figure which shows the shape of the difference | error between {a (k) + b (k)} and {a (k) + sin ((. (Pi) k) / L) * b (k)}. The figure which shows the shape of the error after windowing between {a (k) + b (k)} and {a (k) + sin ((. (Pi) k) / L) * b (k)}. The figure explaining a prior art example. The figure explaining another prior art example.

Explanation of symbols

101 Impulse Response Frequency Characteristic Holding Unit 102 Input Signal Frequency Characteristic Holding Unit 103 Synthetic Signal Frequency Characteristic Generating Unit 105 'Window Overlaying Unit 107 Odd Component Imaginary Part Extracting Unit 108 Addition Array Inverse Conversion Unit h Finite-length Impulse Response Sequence x Input Signal

Claims (4)

In a high-speed convolution approximation method that approximates a convolution operation between an input digital signal sequence and a finite impulse response sequence at high speed,
Determined discrete frequency transform coefficients of 2L point based on the finite impulse response series,
Based on the digital signal sequence, a 2L point discrete frequency conversion coefficient is obtained,
Generates a composite signal frequency transform coefficients of 2L point by multiplying the discrete frequency transform coefficients of the digital signal sequence and the discrete frequency transform coefficients of the finite impulse response series for each corresponding discrete frequency,
The synthesized signal frequency consists transform coefficients Te sequence odor number of elements 2L and even numbered the lowest discrete frequencies, the composite signal composed of coefficients corresponding to the odd-numbered discrete frequency in the sequence consisting of the frequency coefficient number of elements L , 0, 1, 2,... In order from the coefficient corresponding to the lowest discrete frequency in the odd-numbered discrete frequency coefficient array. . . , L-1
The 0th element is
A value corresponding to the imaginary part of the 0th coefficient of the odd-numbered discrete frequency coefficient array is a real part,
l (where l is 1, 2, ..., L-1)
A value corresponding to ½ of a value obtained by subtracting the real part value of the l-th coefficient of the odd-numbered discrete frequency coefficient array from the real part value of the (L−1) -th coefficient of the odd-numbered discrete frequency coefficient array. Imaginary part,
A value corresponding to ½ of the sum of the value of the imaginary part of the l-th coefficient of the odd-numbered discrete frequency coefficient array and the value of the imaginary part of the (L-1) th coefficient of the odd-numbered discrete frequency coefficient array is realized. Is a part,
Find a new array with element number L ,
By adding the this new arrangement, the sequence consisting of coefficients corresponding to the even-numbered discrete frequencies in the combined signal frequency transform coefficients, with the addition sequence of a main prime L, inverse discrete frequency transform of the adding sequence Run
After the windowing in the signal sequence of inverse discrete frequency transform result of the addition sequence processing, similarly to produce an operational output signal sequence convolution approximation by performing superimposition processing the windowed processed signals in the past,
A fast convolution approximation method characterized by that. In a high-speed convolution approximation device that approximates a convolution operation between an input digital signal sequence and a finite-length impulse response sequence at high speed,
An impulse response frequency characteristic storage unit storing discrete frequency transform coefficients 2L point of the finite impulse response series,
An input signal frequency characteristic holding unit that holds discrete frequency conversion coefficients at 2L points of the digital signal sequence;
A synthetic signal frequency characteristic generation unit for generating a composite signal frequency transform coefficients of the finite impulse response series of discrete frequency transform coefficients and the digital signal sequence of discrete frequency transform coefficients and the multiplied for each corresponding discrete frequency 2L point ,
The synthesized signal frequency consists transform coefficients Te sequence odor number of elements 2L and even numbered the lowest discrete frequencies, the composite signal composed of coefficients corresponding to the odd-numbered discrete frequency in the sequence consisting of the frequency coefficient number of elements L , 0, 1, 2,... In order from the coefficient corresponding to the lowest discrete frequency in the odd-numbered discrete frequency coefficient array. . . , L-1
The 0th element is
A value corresponding to the imaginary part of the 0th coefficient of the odd-numbered discrete frequency coefficient array is a real part,
l (where l is 1, 2, ..., L-1)
A value corresponding to ½ of a value obtained by subtracting the real part value of the l-th coefficient of the odd-numbered discrete frequency coefficient array from the real part value of the (L−1) -th coefficient of the odd-numbered discrete frequency coefficient array. Imaginary part,
A value corresponding to ½ of the sum of the imaginary part value of the l-th coefficient of the odd-numbered discrete frequency coefficient array and the imaginary part value of the (L−1) -th coefficient of the odd-numbered discrete frequency coefficient array is realized. Is a part,
An odd component imaginary part extraction unit for obtaining a new array of the number of elements L ;
By adding the this new arrangement, the sequence consisting of coefficients corresponding to the even-numbered discrete frequencies in the combined signal frequency transform coefficients, with the addition sequence of the number of elements L, inverse discrete frequency transform of the adding sequence An addition array inverse transform unit for executing
After the windowing in the signal sequence obtained from the addition sequence inverse converter process performs superimposition processing with similarly windowed processed signals in the past, and windowing superimposing unit for generating an approximate convolution operation output signal sequence,
The high-speed convolution approximation apparatus characterized by comprising. A high-speed convolution approximation program for causing a computer to function as each component of the high-speed convolution approximation device according to claim 2.   A storage medium storing the high-speed convolution approximation program according to claim 3.

Images