Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

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

Малашкевич Ирина Ардалионовна

доцент, кафедра информационно-вычислительных систем, Поволжский государственный технологический университет

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
Другие публикации этого автора
 

 

DOI:

10.7256/2306-4196.2013.5.9697

Дата направления статьи в редакцию:

17-09-2013


Дата публикации:

1-10-2013


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


Ключевые слова:

алгоритм децимации данных, эффективность, быстрые дискретные преобразования, характеристическое уравнение, реализация алгоритма, Object Pascal, цифровая обработка сигналов, дискретное вейвлет-преобразование, анализ алгоритма, алгоритм группировки

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.


Keywords:

data decimation algorithm, effectiveness, fast discrete transforms, characteristic equation, algorithm implementation, Object Pascal, digital signal processing, discrete wavelet transform, analysis of algorithm, grouping algorithm

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

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

mik+1=2mikmodN (1)

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

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

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

t=a1;

a1=a2;

a2=a4;

a4=a8 mod 7=a1=t;

t=a3;

a3=a6;

a6=a12 mod7=a5;

a5=a10 mod7 =a3=t

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

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

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

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

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

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

m1=21m0-p0N1;

m2=2m1-p1N1=22m0-(21p0+p1)N1;

m3=3m2-p2N1=23m0-(22p0+21p1+p2)N1;

...

mk=2km0-(2k-1p0+2k-2p1+...+pk)N1;

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

mk=m0; (3)

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

2km0-XN1=m0; (4)

где X =2k-1p0+2k-2p1+...+pk- характеристическое число цепочки.

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

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

mk<m0; (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=2n, но и при любом четном N.

Библиография
1. http://psi-logic.narod.ru/fft/fft3.ht
2. Малашкевич И.А., Малашкевич В.Б. Применение fortran-библиотек линейной алгебры в среде delphi // NB: Кибернетика и программирование. - 2013. - 1. - C. 1 - 8. URL: http://www.e-notabene.ru/kp/article_8314.html
3. Коробейников А.Г., Кутузов И.М. Алгоритм обфускации // NB: Кибернетика и программирование. - 2013. - 3. - C. 1 - 8. URL: http://www.e-notabene.ru/kp/article_9356.html
4. Бондаренко И.Б., Коробейников А.Г., Прохожев Н.Н., Михайличенко О.В. Принятие технических решений с помощью многоагентных систем // NB: Кибернетика и программирование. - 2013. - 1. - C. 16 - 20. URL: http://www.e-notabene.ru/kp/article_8305.html
5. Харитонов А.В. Обзор биометрических методов идентификации личности // NB: Кибернетика и программирование. - 2013. - 2. - C. 12 - 19. URL: http://www.e-notabene.ru/kp/article_8300.html
6. Меженин А.В., Извозчикова В.В. Методы построения векторов нормалей в задачах идентификации объектов // NB: Кибернетика и программирование. - 2013. - 4. - C. 51 - 58. URL: http://www.e-notabene.ru/kp/article_9358.html
7. Боровский А.С. Модели оценки защищенности потенциально – опасных объектов от угроз с использованием экспертной информации в нечеткой форме // NB: Кибернетика и программирование. - 2013. - 4. - C. 14 - 45. URL: http://www.e-notabene.ru/kp/article_9593.html
References
1. http://psi-logic.narod.ru/fft/fft3.ht
2. Malashkevich I.A., Malashkevich V.B. Primenenie fortran-bibliotek lineinoi algebry v srede delphi // NB: Kibernetika i programmirovanie. - 2013. - 1. - C. 1 - 8. URL: http://www.e-notabene.ru/kp/article_8314.html
3. Korobeinikov A.G., Kutuzov I.M. Algoritm obfuskatsii // NB: Kibernetika i programmirovanie. - 2013. - 3. - C. 1 - 8. URL: http://www.e-notabene.ru/kp/article_9356.html
4. Bondarenko I.B., Korobeinikov A.G., Prokhozhev N.N., Mikhailichenko O.V. Prinyatie tekhnicheskikh reshenii s pomoshch'yu mnogoagentnykh sistem // NB: Kibernetika i programmirovanie. - 2013. - 1. - C. 16 - 20. URL: http://www.e-notabene.ru/kp/article_8305.html
5. Kharitonov A.V. Obzor biometricheskikh metodov identifikatsii lichnosti // NB: Kibernetika i programmirovanie. - 2013. - 2. - C. 12 - 19. URL: http://www.e-notabene.ru/kp/article_8300.html
6. Mezhenin A.V., Izvozchikova V.V. Metody postroeniya vektorov normalei v zadachakh identifikatsii ob''ektov // NB: Kibernetika i programmirovanie. - 2013. - 4. - C. 51 - 58. URL: http://www.e-notabene.ru/kp/article_9358.html
7. Borovskii A.S. Modeli otsenki zashchishchennosti potentsial'no – opasnykh ob''ektov ot ugroz s ispol'zovaniem ekspertnoi informatsii v nechetkoi forme // NB: Kibernetika i programmirovanie. - 2013. - 4. - C. 14 - 45. URL: http://www.e-notabene.ru/kp/article_9593.html