Статья 'Эффективный алгоритм децимации данных' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Journal Menu
> Issues > Rubrics > About journal > Authors > About the Journal > Requirements for publication > Council of Editors > Peer-review process > Policy of publication. Aims & Scope. > Article retraction > Ethics > Online First Pre-Publication > Copyright & Licensing Policy > Digital archiving policy > Open Access Policy > Open access publishing costs > Article Identification Policy > Plagiarism check policy
Journals in science databases
About the Journal

MAIN PAGE > Back to contents
Cybernetics and programming
Reference:

An efficient algorithm for data decimation

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

 
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

Review date:

17-09-2013


Publish date:

1-10-2013


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
This article written in Russian. You can find full text of article in Russian here .

В практике цифровой обработки сигналов широкое применение находят алгоритмы спектральных преобразований сигналов - быстрые преобразования Фурье, Уолша, Хаара, дискретное вейвлет-преобразование. Одной из ресурсоемких операций этих алгоритмов является децимация данных – группировка данных с четными и нечетными номерами. Традиционно эта операция выполняется с помощью выделения дополнительной памяти. Сложность такой группировки оценивается затратами памяти порядка 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.



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
Link to this article

You can simply select and copy link from below text field.


Other our sites:
Official Website of NOTA BENE / Aurora Group s.r.o.
"History Illustrated" Website