Эффективный алгоритм децимации данных

Малашкевич Ирина Ардалионовна доцент, кафедра информационно-вычислительных систем, Поволжский государственный технологический университет 424038, Россия, республика Марий Эл, г. Йошкар-Ола, ул. Ленинский Просреки, 3, оф. к.3 Malashkevich Irina Ardalionovna Associate Professor, Department of Information Systems, Volga State University of Technology 424038, Russia, respublika Marii El, g. Ioshkar-Ola, ul. Leninskii prospect, 3 malashkevichia@volgatech.net Другие публикации этого автора

Малашкевич Василий Борисович кандидат технических наук доцент, кафедра информационно-вычислительных систем, Поволжский государственный технологический университет 424000, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, дом 3. Malashkevich Vasilii Borisovich PhD in Technical Science 424000, Respublika Marii El, g. Ioshkar-Ola, pl. Lenina, dom 3. MalashkevichVB@volgatech.net Другие публикации этого автора

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

Вместе с тем можно предложить алгоритм группировки, не требующий применения дополнительных массивов памяти и решающий задачу децимации за O(N) операций. Действительно, можно показать, что все необходимые перестановки элементов осуществляются с помощью ряда цепочек перемещений, каждая из которых начинается с нечетных элементов массива данных. Причем каждая цепочка начинается и завершается одним и тем же элементом массива, если индекс (номер) каждого следующего элемента вычисляется по правилу:

m_ik+1=2m_ikmodN (1)

где m_ik - k-ый индекс элемента-источника i-ой цепочки перемещений; m_ik+1 - индекс элемента-приемника. Стартовые индексы цепочек определяются по правилу:

m_i0=2i+1; i=0,1,2...; i`<=N/(2-1)` (2)

Например, для группировки элементов массива А с N=8 потребуется 2 цепочки с m₀₀=1 и m₁₀=3. Длина каждой последовательности составляет 3 перестановки.

Несложно проверить, что приведенные перестановки обеспечивают упорядоченное перемещение всех элементов массива A с четными индексами в первую половину массива, а элементов с нечетными номерами - во вторую половину массива.

Анализ алгоритма при разных N показывает, что количество и длина цепочек варьируется.

Например, при N=16 потребуется 3 цепочки по 4 перестановки и одна цепочка с 2 перестановками. Кроме того при N>16 некоторые стартовые индексы m_i0 ведут к дублирующим перестановкам, искажающим результат. Например, при N=32 такими дублирующими цепочками являются m₄₀=9 и m₆₀=13. Предложенный алгоритм группировки дает правильный результат только при условии, что перестановки дублирующих цепочек не выполняются.

Для поиска правил выбора стартовых индексов цепочек выпишем последовательность индексов, принадлежащих i-ой цепочке в общем виде. Учитывая, что выражение (1) можно представить в форме (индекс i опущен)

m_k+1=2m_k-p_kN₁; `p_k={(0, if 2m_k>=N;),(1, if 2m_k<N):}` N₁=N-1

последовательно имеем

m₁=2¹m₀-p₀N₁;

m₂=2m₁-p₁N₁=2²m₀-(2¹p₀+p₁)N₁;

m₃=3m₂-p₂N₁=2³m₀-(2²p₀+2¹p₁+p₂)N₁;

...

m_k=2^km₀-(2^k-1p₀+2^k-2p₁+...+p_k)N₁;

Если цепочка перестановок содержит всего K перемещений, то условие завершения цепочки имеет вид

m_k=m₀; (3)

Из условия (3) следует характеристическое уравнение цепочки

2^km₀-XN₁=m₀; (4)

где X =2^k-1p₀+2^k-2p₁+...+p_k- характеристическое число цепочки.

Выражение (4) является линейным диофантовым уравнением с двумя неизвестными. Его решение позволяет при заданных m₀ и N определить длину K цепочки перестановок и ее характеристическое число X, которое определяет индексы перестановки, требующие выполнения операции взятия модуля по основанию N. Такие индексы являются потенциально опасными, так как могут приводить к дублирующим перестановкам элементов массива.

Уравнение (4) дает основу для теоретического исследования алгоритма. Однако для практической реализации алгоритма удобнее использовать следующее правило. Если какой-либо промежуточный индекс цепочки удовлетворяет условию

m_k<m₀; (5)

то такая цепочка является дублирующей и должна быть отброшена.

Алгоритм реализован на языке Object Pascal в среде Delphi

procedureSplit (A : TDataArray; N : integer);

var N1,i,m0,m1,m2, mAll : integer; T : TData;

begin

N1 := N-1; mAll := N-2; i := 0;

while mAll >0 do

begin

m0 := 2*i+1; Inc(i);

if IsDblChain (m0,N1) then Continue;

m1 := m0; t := A[m1];

repeat

m2 := 2*m1; if m2>N1 then m2 := m2 - N1; //m2 := (2*m1) mod N1;

if m2=m0 then Break;

A[m1] := A[m2]; Dec(mAll);

m1 := m2;

until False;

A[m1] := t; Dec(mAll);

end;

end;

Функция IsDblChain (m0,N1) служит для определения дублирующих цепочек перестановок. Тип TData определяет тип данных обрабатываемого массива A.

Разработана также процедура Merge(A : TDataArray; N : integer) для обратного слияния данных.

Тестовые прогоны алгоритма показали высокую скорость их работы.

Следует отметить, что в отличии от ^[1] предложенный алгоритм работоспособен не только при N=2ⁿ, но и при любом четном N.