RU2242792C2 - Method for fast averaging fir filtering on basis of processor - Google Patents

Abstract

FIELD: computer measuring equipment.

SUBSTANCE: method is based on processing of samples when they appear, only by adding operations and comparison operations for determining moments of totals fixing time.

EFFECT: higher effectiveness.

6 dwg, 1 tbl

Description

The invention relates to the field of digital measuring technology, where one of the typical tasks is the task of determining the average value of a certain signal, when the digital filter used should isolate the constant component of the signal and suppress all noise present in the signal in the form of fluctuations / 1 /, P.127. It is recommended to use the invention as a part of digital processing of electrical measuring signals as a way to quickly weighted averaged samples while constructing digital measuring devices based on signal microprocessors with limited memory and computing capabilities.

In the source / 1 / - Gutnikov V.S. Filtering measuring signals. - L .: Energoatomizdat. Leningra. Otdelniy, 1990, p.160-163 provides a method of FIR filtering of the prototype, implemented on the basis of a digital computing device (CVD) and viewed in the structural diagram of figure 1. An analog-to-digital converter (ADC) 1 generates codes proportional to the instantaneous values of the input signal x (t) with a time step equal to the sampling period of the FIR filter 7 _d , s. The physical nature of the input signal can be any, therefore the units of its measurement are omitted. Further, these codes are processed in CVU 2, which can be any microprocessor element, where the algorithm of the digital FIR filter is reproduced - the calculation of the weighted sum of consecutive code values. The indicated algorithm is reproduced according to the block diagram represented by blocks 3, 4, and 5. Here, the ADC sample stored in the storage device (memory) 3 is supplied to the scaling device (MU) 4 and then to the accumulating adder (NSm) 5. The initial installation of the MU and NSm is produced with a cycle of N T _d . In this case, the transmission coefficient a _{0 is} set in the scaling device, and the adder is reset to zero. The memory output signal coming after this is stored in the adder with coefficient a ₀ . Next, the scale factor a _{1 is} set in the MU, and in the next 7 _d cycle _{, a} signal from the memory with a weight of a _{1 is} added to the signal that was previously stored in the NSm. In total, N discrete values of the input signal multiplied by weighting coefficients enter the accumulating adder. The weighted sum obtained in this way is the output signal of the FIR filter. Then again the initial installation of the filter nodes is made, and the formation of a new output signal begins. Thus, the formation of a single value of the output signal takes time N T _d , and the value itself is determined in accordance with the discrete filtering algorithm shown in the prototype on page 162 and written below for one cycle N T _d :

where y is the result of the weighted sum of ADC samples;

a _n - weight window;

x [nT _d ] - ADC sample at the current moment of the quantized time;

nT _d is the quantized time, s;

n is the reference number of the quantized time (dimensionless time);

T _d - the sampling period, s;

N is the total number of samples used for weighted summation (FIR filter memory).

If one of the common averaging windows acts as a weighting window: Dirichlet, Bartlett, Hamming, Parzen or Gauss, / 1 /, С.130-135, then the described circuit implements an averaging FIR filter / 1 /, С.127, which carries out a weighted averaging the samples of the input signal.

When using the processor as the CVC, we interpret algorithm (1) as a method of averaging FIR filtering, that is, a method of processing samples of the input signal obtained by the ADC with a time step equal to the sampling period and sequentially summed by the processor with weights a _n to obtain result of weighted averaging y. A diagram of the implementation of this method using the processor is shown in figure 2. The averaging window a _{n is} previously stored in the processor as an array of quantized time n indexed by a counter. Before the start of the averaging FIR filtering cycle in block 6, the weighted sum accumulator S and the quantized time counter n are reset to zero. Next, in block 7, the ADC sample code is obtained, which is then added with a weight of ₀ to the accumulator of the sum S in block 8. Then, in block 9, the quantized time counter is incremented, and then in block 10 its value is checked at the end of the average FIR filtering cycle . At first, block 10 runs along the “Yes” branch, and the process of accumulating the weighted sum goes back to block 7, where a new value of the ADC code is obtained, which is then added to the sum accumulator with a weight of a ₁ , since at the moment n is already equal to one. The process of accumulating the weighted sum continues cyclically until the block 10 identifies the equality n to the number N. This event corresponds to the end of the averaging FIR filtering cycle, when the quantized time takes the value NT _d , and the accumulator of the sum contains the result of weighted averaging of all samples in the volume N. In this case, block 10 processes along the “No” branch to generate the output signal of the averaging FIR filter in block 11, the value of which is taken to be S.

The described method of averaging FIR filtering, implemented on the basis of the processor, is fully equivalent to the algorithm of the FIR filter of the prototype and has the following disadvantages:

- the averaging window must be previously stored in the processor memory the larger the more, the greater the accuracy of the representation of the window weighting factors and the more the number of samples is used for weighted averaging. The presence of a large amount of memory element can significantly increase the cost of the hardware implementation of the method;

- finding the weighted sum by the formula (1) requires performing multiplications of each ADC sample by the weight factor a _n . Not all modern processors have a hardware multiplier with a capacity that satisfies the required capacity of the window representation. Software multiplication is “slow” in nature and requires relatively large computational costs. Therefore, the implementation of formula (1) either limits the cycle time of the averaging FIR filtering NT _d from below, especially with a large number of samples N, which means it narrows the scope of the method or requires the use of high-performance and, accordingly, expensive processors.

The technical result achieved by the invention is to eliminate the disadvantages of the prototype. Moreover, the inventive method of fast averaging FIR filtering based on the processor:

- eliminates the use of processor memory for storing the averaging window, which significantly reduces the cost of the hardware implementation of the method, especially with a large amount of samples processed for weighted averaging;

- eliminates the use of operations of multiplying ADC samples by weighting factors, which significantly reduces the computational cost of the method and, as a result, reduces the cycle time of averaging FIR filtering, without the use of expensive and high-performance processors.

The technical result is achieved through the use of a FIR filter as an averaging filter of a medium higher order, implemented by the “fast” method in some summation operations, excluding storing the averaging window, and having a discrete transfer function of the following form:

where W [z] is the transfer function of the medium order filter;

z is the 7-transform operator;

n ₁ - memory filter of the middle first order;

r is the order of the filter.

This filter, being a low-pass filter, plays the role of a weighted averaging link and has a unique property - its impulse response, depending on the choice of filter order r, approximates several types of common averaging windows that provide high suppression of fluctuations in the input signal / 1 /, С. 130-135, / 2 /, S.287-297. These windows include: Dirichlet, Bartlett, Hamming, Parzen and Gauss. Figure 3 shows a family of these windows obtained by calculating the impulse response of a higher order medium filter through the inverse discrete Fourier transform / 1 /, C.56, / 3 /, C.45

where k is the dimensionless linear frequency;

j is the imaginary unit;

N is the filter memory of a higher order medium (window duration) associated with the filter parameters by the following relation:

N = r · (n ₁ -1) +1,

where N, r, n ₁ are integers.

N is chosen equal to 256. In the first order (r = 1), the impulse response of the middle filter approximates the Dirichlet window (natural window), in the second - the Bartlett window, in the third - the Hamming window, in the fourth - Parzen and in the fifth - Gaussian window.

The spectra of the corresponding windows are presented in figure 4 and calculated by the formula

where A (F) is the spectrum of the impulse response of a medium-order filter;

F is the reduced frequency equal to the product of the linear frequency in hertz and the window duration in seconds / 1 /, С.128.

From figure 4 it follows that the average filter in question passes the constant component of the input signal without distortion, and the fluctuation variable suppresses the stronger, the higher the fluctuation frequency. This indicates the equivalence of the medium-order filter of the average FIR filtering. In order to analyze the approximating properties of the average filter, Table 1 is given below, which summarizes the parameters of the exact averaging windows taken on page 130 of the prototype and the parameters of their approximations calculated from the spectra in Fig. 4.

From table 1 it can be seen that the first, second and fourth order average filters very accurately approximate, respectively, the Dirichlet, Bartlett and Parzen windows. Filters of the middle third and fifth orders, despite the fact that the shape of their impulse characteristics are close to the Hamming and Gaussian windows, have some approximation error, while preserving the properties of the averaging FIR filter. From table 1 it also follows that with an increase in the order of the average filter, the parameter h _L decreases, and F _h increases. This shows that by choosing the order, depending on the specific tasks of averaging FIR filtering, a compromise can be resolved between the filter bandwidth (F _h ) and the suppression of fluctuations beyond its limits (h _L ).

The processor-based method of fast FIR averaging filtering is based on the fact that the transfer function of a medium-order filter is feasible without storing the averaging window and using multiplication operations. To output this method, consider the following.

Given that the z-images of the output and input filter signal are connected through the transfer function by the ratio

y [z] = W [z] · x [z],

where y [z] is the z-image of the filter output signal;

x [z] is the z-image of the input filter signal,

and expanding the numerator of the transfer function in Newton’s bin / 4 /, we obtain

where c $\genfrac{}{}{0ex}{}{\text{i}}{\text{r}}$ - combinations of r by i, defined as

Further. The fraction 1 / (1-z ^-1 ) is nothing but the transfer function of a discrete adder. Then the fraction 1 / (1-z ^-1 ) ^r in expression (7) is the transfer function of a multiple adder of multiplicity r, formed from a series connection of adders in the amount of r pieces, when the output of the previous adder is input to the next adder. In addition, the expression z ^−m1.i is the transfer function of the net delay unit by t ₁ −i clock cycles of the quantized time, which, depending on (7), shows how the values of the output signal of the multiple adder used to generate the output signal of the entire filter are separated in time. Based on the foregoing, passing from z-images in expression (7) to the originals, we obtain

where S ^r [n] is the multiple sum of samples of the input signal x [n] at the n-th sample of the quantized time;

r is the multiplicity of a multiple sum equal to the order of the average filter.

Since the duration of the impulse response of the average filter is N samples of quantized time, the process of weighted averaging of samples of the input signal can end only with n equal to N-1. Then, substituting the quantity N-1 in expression (9) instead of n, taking into account dependence (4), we find

Note that for i equal to r, the multiple sum argument becomes negative.

In this case, its value can be considered zero and thrown out of consideration:

By substituting (i = ri) and taking into account the properties of the combinations (C $\genfrac{}{}{0ex}{}{\text{ri}}{\text{r}}$ = C $\genfrac{}{}{0ex}{}{\text{i}}{\text{r}}$ ), expression (11) is transformed to a more convenient final form

The resulting expression is an algorithm of the method of fast averaging FIR filtering based on the processor. It follows that the process of weighted averaging of the input signal consists in accumulating a multiple sum of samples as they arrive from the ADC, the value of which is fixed exclusively for r time samples with numbers: n ₁ -r, 2n ₁ -r, 3n ₁ -r, and so on up to r • n ₁ -r. Then, to form the final result of averaging, a single summation of the fixed amounts is carried out with the corresponding weights: (-1) ^r-1 · C $\genfrac{}{}{0ex}{}{\text{1}}{\text{r}}$ / n $\genfrac{}{}{0ex}{}{\text{r}}{}$$\genfrac{}{}{0ex}{}{}{\text{1}}$ , (-1) ^r-3 • C $\genfrac{}{}{0ex}{}{\text{2}}{\text{r}}$ / n $\genfrac{}{}{0ex}{}{\text{r}}{}$$\genfrac{}{}{0ex}{}{}{\text{1}}$ and so on to C $\genfrac{}{}{0ex}{}{\text{r}}{\text{r}}$ / n $\genfrac{}{}{0ex}{}{\text{r}}{}$$\genfrac{}{}{0ex}{}{}{\text{1}}$ . The number of these weights does not depend on the duration of the impulse response of the average filter, that is, it does not depend on N, and is equal to its order.

Thus, in the claimed method of averaging FIR filtering, the processing of samples at the rate of their appearance is based only on the operations of summation and comparison to determine the moments of time for fixing the sums. In addition, the averaging window approximated by the average filter is clearly not present in algorithm (12), which eliminates the use of processor memory for storing it. The gain in computational complexity compared to the prototype, due to the exclusion of operations of multiplying the samples of the input signal by the averaging window, will be examined in detail in the information section confirming the possibility of carrying out the invention.

List of figures

Figure 1 - Block diagram of the FIR filter of the prototype based on a digital computing device.

Figure 2 - Scheme of the implementation of the method of averaging FIR filtering of the prototype using the processor.

Figure 3 - A family of averaging windows approximated by a medium order filter.

Figure 4 - Spectra of averaging windows approximated by a medium order filter.

5 is a diagram of the implementation of the method of fast averaging FIR filtering based on the processor.

6 - Computational costs of the method of fast averaging FIR filtering based on the processor.

The inventive method of fast averaging FIR filtering based on the processor is feasible using microprocessor elements: signal microprocessors, microcontrollers with built-in ADCs or with the ability to enter binary code from an external ADC. The following microcircuits of foreign manufacturers used in Russia / 5 / can be considered as an example of these microprocessor elements:

- Motorola 68НС705В32 microcontroller family НС05 from Motorola, having an 8-bit multichannel ADC, the amount of permanent memory of 32 Kbytes and operating at a clock frequency of 2 MHz;

- Microcontroller M430P325I family MSP430 company Texas Instruments, having a 14-bit or 12-bit multi-channel ADC, the amount of permanent memory of 16 KB and operating at a clock frequency of up to 3 MHz;

- Microcontroller ADuC812 microcontroller family of Analog Devices company, which has a 12-bit multi-channel ADC, clocked at 12 MHz and allows addressing up to 16 MB of data memory and 64 KB of program memory;

- Zilog microcontroller Z86C84 of the Z8 family, which has an 8-bit multichannel ADC, the amount of read-only memory is 4 KB and operates at a clock frequency of 16 MHz;

- A new ATEL ATR Mega603L microcontroller from the ATMEL family, featuring a 10-bit multichannel ADC, 64 Kbytes of permanent memory, 4 Kbytes of RAM and 4 MHz clock speed.

All of these microcontrollers have a developed system of internal timers, which allows you to control the sampling period of the built-in ADCs.

The role of software implementation of the fast averaging FIR filtering method in accordance with the algorithm (12) is assigned to the microcontroller. Sequential acquisition of samples of the input signal using the built-in ADC is synchronized by the internal timer of the microcontroller, specifying the sampling period T _d . All computational operations falling on one ADC sample should be time-invested in the interval of the sampling period, which is significantly less for the proposed method of averaging FIR filtering in comparison with the prototype. For the sake of detail, let us consider an example of the implementation of the fast averaging FIR filtering method for a third-order medium filter approximating a Hamming window (Fig. 3).

Let the filter impulse response duration be 256 samples of the quantized time, when the numbers of samples n can vary from 0 to 255. Based on expression (4), it is easy to establish that parameter n ₁ must have the value 86. Only in this case N = 3 • (86 -1) + 1 = 256. Substituting the numerical values in (12), taking into account combinations (8), we obtain the algorithm of the fast averaging FIR filtering method

where S ³ [n] is three times the sum of samples of the input signal at the n-th sample of the quantized time.

As you can see, fixing the sums is required for n with numbers 83, 169 and 255.

Figure 5 presents a diagram of the implementation of the algorithm (13) based on the processor.

1) Before the start of the averaging FIR filtering cycle in block 12, the following are reset: the accumulator of the sum S ¹ , the accumulator of the double sum S ² , the accumulator of the triple sum S ³ , and also the quantized time counter n;

2) Next, in block 13, the current ADC sample is obtained with the subsequent increase in the amount, twofold sum and triple sum in blocks 14, 15 and 16, respectively;

3) After building up the triplicate amount, a verification system follows, consisting of blocks 17, 18, 19, which at the beginning completely fulfills the “No” branches, and the cycle of averaging FIR filtering proceeds to block 20;

4) In block 20, the counter of the quantized time n is incremented, after which everything is repeated, starting from the second paragraph — the ADC samples are continuously obtained and the triplicate amount is accumulated;

5) The process of accumulating a three-fold sum is carried out until block 17 identifies the moment the counter n is equal to the number 83. This case corresponds to the event when the three-fold sum assumes the value S ³ [83]. Therefore, block 17 fulfills the branch "Yes" to save its value in the latch A in block 21;

6) Next, the process of accumulating a three-fold sum continues until the number n is equal to 169, which is accompanied by working off the block 18 on the Yes branch. In this case, the three-fold sum has the value S ³ [169], which is stored in the latch B in block 22;

7) After this, the process of accumulating a triple sum continues again until block 19 identifies the moment the counter n is equal to 255. This case corresponds to the end of the averaging FIR filtering cycle, when the quantized time takes the value N T _d , and the triple sum becomes equal S ³ [255];

8) After completing the cycle of averaging FIR filtering and storing the last value of the triple sum in the clamp C in block 23, it remains to calculate the result of the weighted averaging once using the contents of the clamps, which is done in accordance with formula (13) in block 24.

Thus, in the inventive method of fast averaging FIR filtering based on the processor, the processing of samples of the input signal at the rate of their appearance is based only on the operations of summation and comparison. In addition, the averaging window approximated by the average filter is clearly not present in the method algorithm, which excludes the use of memory elements for storing it. The gain in computational complexity compared to the prototype due to the exclusion of operations of multiplying the samples of the input signal by the averaging window is considered in more detail.

The computational costs attributable to each sample of the input signal are determined by blocks 14, 15, 16, 17, 18. The unit for checking the moment of reaching the end of the FIR filtering cycle 19 and the increment unit of the quantized time counter 20 are not considered, since they are also present in the algorithm processing prototype ADC samples.

Let the bit capacity of the ADC sample is 16 bits (sign). In order to avoid overflow of multiple sums with 256 sums, in the considered algorithm, the sum should have a bit capacity of at least 24 bits, a double sum of at least 31 bits and a triple sum of at least 37 bits. When using a processor with 16-bit arithmetic, the indicated amounts are calculated for 2, 2, and 3 summing operations, respectively. Thus, taking into account the fact that the comparison operations in blocks 17 and 18 are usually equivalent in cost to three or four summation operations, it turns out that the computational costs of the algorithm in Fig. 5 are 16 equivalent summations for each ADC sample.

In the prototype, it is required to multiply each sample by a weight factor, the capacity of which is usually not lower than the capacity of the ADC. Programmatically multiplying a 16-bit sample by a 16-bit weighting factor requires at least sixteen 32-bit shifts and summing, each of which is equivalent to two summing operations. In addition, in a shift and sum cycle, at least two comparison operations are required to identify the state of the next bit of the multiplier and check the end of the cycle, each of which is also equivalent to three sums. From this it follows that the computational cost of software multiplication is about 160 equivalent to the summation for each ADC sample, which is an order of magnitude greater than in the algorithm in figure 5.

Figure 6 presents the results of numerical computer experiments to determine the computational cost of a fast averaging FIR filtering method based on a processor for various orders of the average filter. It can be seen that the number of equivalent summations Z per one ADC sample does not so much depend on the volume of processed samples N, but on the order of the average filter r. In practice, to ensure high suppression of variable fluctuations in the input signal, a fifth-order filter (Gaussian window) is more than enough, while the amount of computational cost remains significantly lower than in the prototype, for which it is shown in dashed lines in Fig. 5.

Sources of information

1. Gutnikov V.S. Filtering measuring signals. - L .: Energoatomizdat. Leningra. Otdel., 1990 .-- 192 pp., ill. (prototype).

2. Max J. Methods and techniques for processing signals in physical measurements: In 2 volumes. Per. with french - M .: Mir, 1983.- T.1, S.287-297.

3. Arutyunov P.A. Theory and application of algorithmic measurements. - M .: Energoatomizdat, 1990. - P.45.

4. Bronstein I.N., Semendyaev K.A. Math reference. M., 1967. - S.163-164.

5. Modern microcontrollers: Architecture, design tools, application examples, Internet resources. © "Telesystems". Ed. Korshun I.V .; Compilation, trans. from English and literary processing Gorbunova BB - M .: Akim Publishing House, 1998. - 272 p., Ill.

Claims (1)

A method of fast averaging FIR filtering based on a processor, which consists in the fact that using an analog-to-digital converter, samples of the input signal are obtained, which are subjected to weighted averaging, sequentially in time, using a processor, characterized in that they accumulate a multiple sum of samples of the input signal, the value of which is fixed for r moments of quantized time with numbers n ₁ - r, 2n ₁ -r, 3n ₁ - r, and so on up to r • n ₁ - r, where r is the multiplicity of the accumulated sum, n ₁ is a whole parameter related with the total amount of sum sampling N by the ratio:

then the fixed values of the multiple amount are summed once with whole weights in accordance with the formula:

where y is the result of weighted averaging of samples of the analog-to-digital converter; S ^r [i · n ₁ -r] - fixed values of multiple sums of multiplicity r; FROM $\genfrac{}{}{0ex}{}{\text{i}}{\text{r}}$ - integer weights, defined as combinations of r by i:

Images