Discrete convolution (convolution).

In many practical problems it is necessary to calculate the convolution of two finite sequences when one of them is much longer than the other (say, or). Of course, you can always choose equal, but this approach is ineffective and for a number of reasons inconvenient. First, you need to have the entire longer sequence before computing the convolution. In practice, for example, in radar or when processing speech signals, this condition is not always feasible. Secondly, since processing begins only after receiving the entire sequence, the result is obtained with a long delay. And finally, if it is too large, the DFT calculation becomes much more complicated, since it requires a large amount of memory and some other purely practical difficulties related to FFT algorithms. The following two methods for calculating convolution are free from these disadvantages. They are based on breaking a longer sequence into sections and calculating partial convolutions, from which the desired output sequence is then formed.

The first one is called the overlap-sum method. The essence of this method is illustrated in Fig. 2.32. For simplicity, we assume that the sequence is not limited and contains samples. Let's divide the sequence into adjacent sections with a length of samples (Fig. 2.32). The choice is quite difficult, but good results are obtained if is a quantity of the same order as . So, the input sequence is represented in the form

(2.166)

Fig. 2.32. Overlap method with summation.

(2.167)

Linear convolution of sequences and is equal to

(2.168)

(2.169)

Fig. 2.33. Generating convolution output values using the overlap-sum method.

The length of each of the partial convolutions in the sum (2.169) is equal to the samples, i.e. there is a section with a length of samples in which the th and th partial convolutions overlap, so their samples in the overlap section need to be added. In fig. Figure 2.33 shows how adjacent partial convolutions are arranged and summed. Each of them is calculated by the fast convolution method described in Section. 2.24. The considered method was called the overlap method with summation precisely because the intermediate partial convolutions overlap and must be added to obtain the final result.

Fig. 2.34. Stacked overlap method.

Another method of calculating the linear convolution of sequences, one of which is much longer than the other, is also based on partitioning a longer sequence. It is called the stacking overlap method, and in in this case the input sections are overlapped, not the output sections. Erroneous samples of circular convolutions of individual sections are discarded. The remaining samples are accumulated and the final result is formed from them. Let's consider concrete example(Fig. 2.34). The sequence contains samples, and the sequence is divided into sections of sample length, overlapping each other in sections of sample length. (Note that the overlap region is at the end of the sequence. This is convenient for computing circular convolution using DFT.)

Department of VT

ABSTRACT

discipline: “Digital signal processing”

on the topic: “Linear convolution of deterministic sequences”

Completed:

Checked:

St. Petersburg, 2014

1. Introduction 3

2. Linear convolution 4

3. Cyclic convolution 5

4. Sectioned convolutions 7

5. Literature 11

Introduction

Convolution operation:

s(t) = x(t) * h(t) = (1)

In the discrete case, two types of convolution are distinguished: linear (or aperiodic) and cyclic. Cyclic convolution is also often called circular or periodic.

Linear convolution

Let's consider linear convolution. Let there be two discrete signals a(n), n=0..N-1, and b(n), n=0..M-1. IN general case The lengths of these N and M signals may differ. Linear convolution of signals a(n) and b(n) is a discrete signal of the form:

s(n) = a*b = (2)

To calculate linear convolution, the signals a(n) and b(n) are shifted relative to each other, multiplied and added termwise. It is assumed that a(n) = 0 for n<0 и n>N, as well as b(n)=0 for n<0 и n>M

A graphical representation of linear convolution is shown in Figure 1.

Figure 1: Graphical representation linear convolution

The signal samples b(n) are shifted relative to the sequence samples a(n); all possible overlapping samples are multiplied and added term by term.

Figure 2 shows an example of calculating the linear convolution of two signals a(n) = 4 samples long and b(n)=[-1,1,2] 3 samples long.

Figure 2: Example of linear convolution calculation.

It should be noted that the signal b(n) when calculating the convolution is reflected from left to right, since b(0) = -1 is the very first sample (earliest in time) and it should also be processed first.

Cyclic convolution

Let us now consider cyclic convolution. In the case of cyclic convolution it is assumed that discrete signals a(n) and b(n) are periodic with the same period of N samples. Then the circular convolution of signals a(n) and b(n) is a signal of the form:

s(n) = (3)

The result of cyclic convolution also has a length of N samples.

Let's consider cyclic convolution using the example of two signals a(n)= and b(n)=[-1,3,2,1] . Graphically, the calculation of cyclic convolution is presented in Figure 3.

Figure 3: Cyclic convolution calculation

The red line marks the boundaries of the signal repetition periods b(n-m). Note that due to the periodicity of the signals, b(-m)=b(N-m).

Let's calculate the convolution step by step:

Now let's calculate s(1):

Let's give an example of calculating a linear convolution through a cyclic one for a(n)= with a length of 4 samples and b(n)=[-1,1,2] with a length of 3 samples (this example was discussed above).

Let's add zeros to a(n)= and b(n)=[-1,1,2,0,0,0], so that there are 6 samples in each sequence.

Let's calculate the cyclic convolution as shown in Figure 4.

Figure 4: Calculating linear convolution via cyclic<

You can compare it with the result of the very first example for linear convolution and make sure that the values are the same.

Sectioned convolutions

Sectional convolution used when the number of elements of one of the sequences is several times greater than the number of elements of the other. Sectional convolution can be performed by two computation methods. They are based on breaking a longer sequence into sections and calculating partial convolutions, from which the desired output sequence is then formed.

The first one is called the overlap-sum method. The essence of this method is illustrated in Fig. 5. For simplicity, we assume that the sequence x(n) is not limited, and h(n) contains samples. Let us divide the sequence x(n) into adjacent sections with a length of samples (Fig. 5). The choice is quite complicated, but good results are obtained if it is a quantity of the same order as . So, the input sequence x(n) is represented as

Fig.5. - Overlap method with summation.

The linear convolution of the sequences x(n) and h(n) is equal to

Fig.6. - Formation of convolution output values using the overlap method with summation.

The length of each of the partial convolutions in the sum (4) is equal to () samples, i.e. there is a section of length () samples in which the k-th and (k+1)-th partial convolutions overlap, so their samples are in the overlap section needs to be folded. In Fig. Figure 6 shows how adjacent partial convolutions are arranged and summed. The considered method was called the overlap method with summation precisely because the intermediate partial convolutions overlap and must be added to obtain the final result.

Fig.7 -. Stacked overlap method.

Another method of calculating the linear convolution of sequences, one of which is much longer than the other, is also based on partitioning a longer sequence. It is called the stacking overlap method, and in this case the input sections are overlapped, not the output sections. Erroneous samples of circular convolutions of individual sections are discarded. The remaining samples are accumulated and the final result is formed from them. Let's consider a specific example (Fig. 7). The sequence h(n) contains samples, and the sequence x(n) is divided into sections of length by () samples, overlapping each other in sections of length by samples. (Note that the overlap region is at the end of the sequence. This is convenient for computing circular convolution using DFT.)

rice. 8. - Formation of convolution output values using the stacked overlap method.

For each section, a circular convolution of the sequences h(n) and , containing () the sample, is calculated. The result is a set of sequences shown in Fig. 8. The last () samples of each of the sequences are discarded (they are incorrect due to the cyclic nature of the convolution), and the rest are added to the correct samples of the sequence, etc. The result is the desired sequence, identical to the convolution y(n). So, using the overlap-sum method or the overlap-stack method, it is relatively easy to find the convolution of a short and a very long sequence, with the result obtained in the form of separate small sections that are combined accordingly into one sequence.

Literature

1. Digital processing of image signals: textbook. allowance / S.M. Ibatullin; St. Petersburg State Electrotechnical University named after. V.I. Ulyanov (Lenin) "LETI". - St. Petersburg. : Publishing house of St. Petersburg Electrotechnical University "LETI", 2006.

2. Digital signal processing: textbook. manual for universities / A.B. Sergienko; - St. Petersburg. : Peter, 2002.

3. Algorithms and processors of digital signal processing: Textbook. manual for universities / A. I. Solonina, D. A. Ulakhovich, L. A. Yakovlev. - St. Petersburg. : BHV-Petersburg, 2001.

4. Digital signal processing = Understanding digital signal processing / R. Lyons; lane from English edited by A. A. Britova. - 2nd ed. - M.: Binom, 2007.

In the previous section it was shown that the complexity of arithmetic operations when implementing FIR filters using DFT does not depend on the order of the filter, while the complexity of implementation with direct calculation convolution is proportional to the order of the filter. If the filter order is low, you would expect the direct convolution implementation to be more efficient, but as the filter order increases, the DFT implementation will eventually become more efficient. For filters of very high orders, the gain can reach tens and hundreds of times.

On the other hand, the DFT implementation requires significant amounts of memory. Convolution partitioning methods are a compromise solution. Their essence lies in the fact that the convolution operation is performed on sections or blocks of data using DFT. Limiting the size of the sections reduces the amount of memory required, and the use of DFT maintains the computational efficiency of the procedure.

The simplest to understand partitioned convolution method is called the overlap-sum method. Let's divide the two-dimensional array into -point sections, defining the section with indices as follows:

The support area for one such section is shown in Fig. 3.1,a. The support areas of the sections do not overlap, and together they cover the entire support area of the array, so

. (3.13)

Rice. 3.1. Overlap method with summation.

a - section of the input sequence; b - support area of the result of convolution of this section with .

Due to the fact that the operation discrete convolution distributive with respect to addition, we can write

(3.14)

The output section is the result of convolution with the sequence section. These partial results must be added together to obtain the complete filter output. Since the section reference area is larger than the section reference area, the output sections must overlap, although the degree of overlap is limited. In Fig. 3.1b shows such a support area of one of the output sections.

Convolutions with can be computed using discrete Fourier transforms, provided the size of the transform is large enough to provide a support region. By controlling the size of the sections, we limit the size of the DFT, reducing the amount of memory required. However, in practice this is accompanied by some loss of efficiency.

Another variation of partitioned convolution is the stacked overlap method. Looking again at Fig. 3.1, it can be noted that if the section size significantly exceeds the size of the response reference area , then the samples in the center of each section do not overlap with samples from neighboring sections. Similarly, when a sequence is cyclically convolved with another sequence having a much smaller reference area, only a portion of the cyclic convolution samples will experience spatial aliasing. The remaining samples will be identical to the linear convolution samples. The location of these readings is shown in Fig. 3.2. Thus, if you perform a cyclic convolution of a -point section of a sequence with a -point impulse response using -point DFT, the result of this convolution will contain a region consisting of samples identical to the samples of the linear convolution. The complete output array can be composed of these “good” samples by properly choosing the reference areas of the input sections. If the input sections overlap, it is possible to ensure that the "good" areas of adjacent sections are adjacent to each other. Thus, the stacked overlap method requires the input sections to overlap, while the stacked overlap method requires the output sections to overlap.

Rice. 3.2. Stacked overlap method. The shaded area contains samples for which cyclic convolution with period and linear convolution with give identical results.

For both summation and accumulation overlap procedures, the choice of partition sizes greatly influences the efficiency of the implementation. First of all, this choice obviously affects the amount of memory required, as well as the amount of calculations. From Fig. 3.2 it can be seen that the proportion of useful samples of cyclic convolution increases as the size of the section increases in relation to the size of the impulse response. Although making general statements about how large input sections should be is difficult because the results are highly computer-specific, experiments by Toogood et al. have shown that filters with reference area sizes ranging from to samples require a section size of . This is too much for most minicomputers. Thus, it turns out that the performance of the algorithm is limited by the available memory. If this is the case, then you should select input sections of the largest possible size.

Convolution is a fundamental process in digital signal processing. Therefore, it is important to be able to calculate it effectively.

Discrete convolution equation two functions (signals) can be obtained directly from the convolution integral equation by replacing integration by summing the instantaneous values of the functions with a step Dt:

y(kDt) = Dth(nDt) s(kDt-nDt). (8.11)

When performing discrete convolution, we are dealing with digital arrays, and the sampling step for arrays by the physical argument of convolution must be equal and taken as 1, and the numbering of samples in the arrays is used as an argument:

y(k) =h(n) s(k-n) ºh n s k-n º y k . (8.11")

y(k) = h(n) * s(k-n) º s(k) * h(n) º s k * h n .

Convolution technique shown in Fig. 8.8. To calculate the convolution, the array of one of the functions (s k - input signal) is located in the order of increasing numbers. The array of the second function (h n - shorter, convolution operator) is built parallel to the first array in reverse order(as the numbers decrease, in reverse time mode). To calculate y k, the value of h 0 is located opposite s k, all values of s k-n are multiplied with the values of h n located opposite them and summed. The results of the summation are the output value of the function y k, after which the operator h n is shifted forward by one number k (or the function s k is shifted towards it) and the calculation is repeated for number k+1, etc.

Rice. 8.8. Discrete convolution technique

IN starting moment convolution when calculating the values y k the operator h n , constructed in reverse time mode, “freezes” for k-n values for n>k against missing samples of the input function. “Hanging” is eliminated either by setting initial conditions - additional samples, most often zero or equal to the first sample of the input function, or by starting convolution from the input function sample k = n with a corresponding reduction in the output function interval. For operators with values -n (forward in time), the same moment can occur at the end of the input array.

Example. Convolution equation: y k =b n x k-n = b o x k + b 1 x k-1 + b 2 x k-2 .

The values of the bn operator are: b o = 5, b 1 = 3, b 2 = 2.

Input signal: x k = (0,1,0,0,0), initial conditions: x - n = 0.

Output signal calculation:

y o = 5x o + 3x -1 + 2 x -2 = 5 0 + 3 0 + 2 0 = 0, y 1 = 5x 1 + 3x o + 2x -1 = 5 1 + 3 0 + 2 · 0 = 5,

y 2 = 5x 2 + 3x 1 + 2x o = 5 0 + 3 1 + 2 0 = 3, y 3 = 5x 3 + 3x 2 + 2x 1 = 5 0 + 3 0 + 2 1 = 2,

y 4 = 5x 4 + 3x 3 + 2x 2 = 5 0 + 3 0 + 2 0 = 0, y 5 = 5x 5 + 3x 4 + 2x 3 = 5 0 + 3 0 + 2 0 = 0

Output signal: yk = (0, 5, 3, 2, 0)

Note: The convolution of an operator function with a single input signal is a repetition of the convolution operator function at the output.

In Fig. Figure 8.9 shows an example of performing discrete convolution with a causal (one-way) and an even (symmetric, two-way) operator on the same signal.

Rice. 8.9. Examples of performing discrete convolution

Direct calculation convolution requires K·N multiplications, where K is the length of the original signal and N is the length of the convolution kernel. Both the signal length and the length of the convolution kernel can reach several thousand points, and the number of multiplications becomes enormous.

For discrete convolution, all properties and theorems of integral convolution are valid. In particular, the convolution of functions in the coordinate domain is represented by the product of their spectra in the frequency domain, and multiplication in the coordinate domain is equivalent to convolution in the frequency domain. This means that to perform the convolution of two signals, you can convert them into frequency domain, multiply their spectra, and convert the result back to the time domain, i.e. proceed according to the following scheme:

s(k) Û S(w), h(n) Û H(w), Y(w) = S(w)×H(w), Y(w) Û y(k).

With the advent of FFT algorithms that can quickly compute Fourier transforms, computing convolution through the frequency domain has become widely used. At significant size signals and the length of the convolution kernel, this approach makes it possible to reduce the convolution calculation time by hundreds of times.

The product of spectra can only be performed if they have the same length, and the operator h(n) before the DFT must be padded with zeros to the size of the function s(k).

The second factor that should be taken into account is the cyclicity of the convolution when it is performed in spectral region, due to periodization discrete functions. The spectra being multiplied are the spectra periodic functions, and the result at the end intervals may not coincide with discrete linear convolution, where the conditions for extending the intervals (initial conditions) are specified rather than repeated main period.

In Fig. Figure 8.10 shows the results of convolution of the signal s k , specified on the interval k = (0-50), with the function h n = a×exp(-a×n), a = 0.1. Convolution performed through DFT on the left side of the interval differs sharply from linear convolution. The nature of the distortion becomes clear if we supplement the main interval on the left side with its periodic continuation (the figure shows a part of the left side period, the convolution with which enters the main period). For operators h n with values n forward in position, similar distortions will appear on the right side of the main period. To eliminate such distortions, the signal function must be extended with zeros by the size of the operator h(n), which will eliminate the overlap of side periods of the main trace of the function.

Rice. 8.10. Results of two types of convolution

When performing convolution via FFT, a noticeable increase in computation speed appears only when long length functions and operators (for example, M>1000, N>100). You should also pay attention to the bit depth of the results, because multiplying numbers gives a 2-fold increase in bit depth. With a limited number of digits and appropriate rounding, this can lead to summation errors.

In online data processing systems, there is often a need to calculate the convolution of a signal arriving at the system input in successive portions (for example, from downhole instrument sensors). In such cases it applies sectional convolution. Its essence is that each of these parts is rolled up with the core separately, and the resulting parts are combined. To combine, it is enough to place them one after another with an overlap of N-1 points (N is the length of the convolution kernel), and perform the summation at the points of overlap.

Sectional convolution

To implement this type of convolution, you need to do the following:

1. divide a large sequence into sections, it is desirable that each section has the same number of elements;

2. count the number of values of the partial output sequence (POS) using the formula:

N chwp =N s +N-1 where N chwp is the number of values in the partial output sequence; Nс - quantity: value in this section; N - number of values in the second sequence.

3. convolve each section of the first sequence with the second sequence. The number of convolutions must match the number of sections in the first sequence.

For sectional convolution using the overlap method with summation, the following types of convolution can be used:

linear;
circular without circular overlay (aperiodical);
convolution using discrete Fourier transform.

4. assemble the output sequence from partial output sequences.

For sectional overlap convolution, only circular convolution is used. For sectional convolution using the overlap method with summation, the assembly is carried out as follows: on the segment from (N-1) to N chvp, sum the values from sections 1 and 2 to sections Z-1 and Z (where Z is the number of sections). And for sectional convolution using the overlap and accumulation method: latest values on the segment (N - 1) to N, the chvp must be discarded, that is, they are not taken into account when assembling the output sequence, and so on from section 1 to section Z-1.

Wikimedia Foundation. 2010.

Sekhukhune
Sectional doors

See what “Sectional convolution” is in other dictionaries:

Sequence convolution- is the result of multiplying the elements of two given number sequences in such a way that the members of one sequence are taken with increasing indices, and the members of the other with decreasing indices (which serves as the basis for the adopted name of this ... ... Wikipedia

Digital Signal Processing- (DSP, DSP English digital signal processing) conversion of signals presented in digital form. Any continuous (analog) signal can be subjected to time sampling and level quantization (digitization), then... ... Wikipedia

Warping- this is the name of the preparatory operation in weaving, aimed at preparing the warp (see). It consists, generally speaking, in the fact that the number of threads required for the warp is rewound from individual spools onto a common large shaft, called... ... Encyclopedic Dictionary F. Brockhaus and I.A. Ephron