Аннотация: В работе представлен эффективный алгоритм децимации данных для быстрых дискретных преобразований. Приводится характеристическое уравнение и реализация алгоритма на языке Object Pascal. В практике цифровой обработки сигналов широкое применение находят алгоритмы спектральных преобразований сигналов - быстрые преобразования Фурье, Уолша, Хаара, дискретное вейвлет-преобразование. Одной из ресурсоемких операций этих алгоритмов является децимация данных – группировка данных с четными и нечетными номерами. Традиционно эта операция выполняется с помощью выделения дополнительной памяти. Предлагается алгоритм группировки, не требующий применения дополнительных массивов памяти и решающий задачу децимации за O(N) операций. Показывается, что все необходимые перестановки элементов осуществляются с помощью ряда цепочек перемещений, каждая из которых начинается с нечетных элементов массива данных. Анализ алгоритма при разных N показывает, что количество и длина цепочек варьируется. Тестовые прогоны алгоритма показали высокую скорость их работы.

Abstract: This paper presents an efficient algorithm for fast data decimation of discrete transformations. The article gives the characteristic equation and the implementation of the algorithm in Object Pascal. In the practice of digital signal processing the algorithms of signals spectral transforms (such as fast Fourier transform, Walsh, Haar discrete wavelet transform) are widely used. One of the expensive operations in these algorithms is the decimation of data - grouping of data with even and odd numbers. Traditionally this operation is performed by allocating additional memory. The authors propose an algorithm of grouping that does not require the use of additional memory for storing arrays and solve problems decimation of O (N) operations. It is shown that all the permutations of the elements are made through a series of chain movements, each beginning with the odd elements of the array data. The analysis of the algorithm for different values of N indicates the number and chain length varies. Test executions of the algorithm show its’ high performance.