Recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems.
Linear convolution of discrete signals with a certain core is the most common and important computational task in the field of digital signal processing. Since this operation, as a rule, is performed many times, the problem of synthesizing fast algorithms for performing linear convolution is very ac...
Saved in:
| Date: | 2019 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | rus |
| Published: |
Інститут проблем реєстрації інформації НАН України
2019
|
| Subjects: | |
| Online Access: | http://drsp.ipri.kiev.ua/article/view/178872 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Data Recording, Storage & Processing |
Institution
Data Recording, Storage & Processing| Summary: | Linear convolution of discrete signals with a certain core is the most common and important computational task in the field of digital signal processing. Since this operation, as a rule, is performed many times, the problem of synthesizing fast algorithms for performing linear convolution is very actual, which is the main subject of this work. Since the complexity of calculating the linear convolution of sequences having length N is , and rapidly increases with growth N, then the methods of «fast» computations are used. One of the most common methods is convolution using Fast Fourier Transform (FFT) with complexity of . At the heart of numerous FFT algorithms is the decomposition of the original large-dimensional problem into a large number of low-dimensional problems. Therefore, it is very important to develop such methods for solving problems of small dimension.The terms of convolutional numerical sequences are considered as components of hypercomplex numbers belonging to some FPS dimension. The product of these hypercomplex numbers will contain paired products of components of convolutional numerical sequences. However, they will be combined in amounts not in the same composition as necessary to organize the convolution components.The possibility of constructing algorithms for calculating the linear convolution of numerical sequences whose lengths differ from integral powers of two is shown. Algorithms are a recurrent «fringing» of convolution components of the previous length of a convolution sequence. The beginning of the recursion is a convolution constructed on the basis of the decomposition algorithm with the use of the FPS for the sequence length equal to the nearest lower degree of the deuce relative to the given length. Algorithms of this type are most effective for lengths of sequences being close to from upward (the number of multiplications is reduced by »30 %). |
|---|