ГЛАВНАЯ
> Вернуться к содержанию
Статьи автора Малашкевич Ирина Ардалионовна
Кибернетика и программирование, 2013-5
|
Малашкевич И.А., Малашкевич В.Б. - Эффективный алгоритм децимации данных |
|
c. 1-6
|
DOI: 10.7256/2306-4196.2013.5.9697
Аннотация: В работе представлен эффективный алгоритм децимации данных для быстрых дискретных преобразований. Приводится характеристическое уравнение и реализация алгоритма на языке Object Pascal. В практике цифровой обработки сигналов широкое применение находят алгоритмы спектральных преобразований сигналов - быстрые преобразования Фурье, Уолша, Хаара, дискретное вейвлет-преобразование. Одной из ресурсоемких операций этих алгоритмов является децимация данных – группировка данных с четными и нечетными номерами. Традиционно эта операция выполняется с помощью выделения дополнительной памяти. Предлагается алгоритм группировки, не требующий применения дополнительных массивов памяти и решающий задачу децимации за O(N) операций. Показывается, что все необходимые перестановки элементов осуществляются с помощью ряда цепочек перемещений, каждая из которых начинается с нечетных элементов массива данных. Анализ алгоритма при разных N показывает, что количество и длина цепочек варьируется. Тестовые прогоны алгоритма показали высокую скорость их работы.
|