18.5.2 Algorithms (Convolution)

Conv-Algorithm

Fast algorithm for Convolution

The algorithm for convolution in Origin in based on the convolution theorem. According to the theorem, convolving a signal with a response is the same as multiplying their Fourier transforms and then performing an inverse transform on the product. Thus:

when the following assumptions are valid:

1. Both inputs (the signal and the response) are periodic;
2. The response has the same period as the signal.

However, real data does not always meet these two requirements. Some zeroes must be padded to the inputs so that the algorithm based on convolution theorem can be applied. At the same time, care should be taken to ensure that the zero-padding and the assumption of periodicity does not cause artifacts in the results.

For a circular convolution, data points outside the input range are considered to repeat periodically, thereby satisfying the first requirement. Zeros need to be padded to the end of input sequence (the signal or the response) with the shorter length to ensure that the lengths of both input sequences are equal.

For a linear convolution, data points outside the input range are viewed as zeros. Assuming the signal to be periodic would cause artifacts in the result, because the wrapping adds some data from the far end to points in the beginning of the result. To avoid such artifacts, we must pad zeros to set up a buffer for the wrapped-around data. After padding, the lengths of both inputs should be

where and denotes the lengths of f and g.

After the padding, the fast convolution algorithm stated above is used to calculate the convolution result.

Automatic Computation of Sampling Interval

When <Auto> is selected for Sampling Interval, the sampling interval needed in the computation is computed automatically by Origin.

The automatically computed sampling interval is the average increment of the time sequence, which is usually from the X column associated with the input signal. If there is no associated X column, the row numbers will be used. Note that if Origin fails to get the average increment, the sampling interval will be set to 1.