ВЕСТНИК ЮЖНОГО НАУЧНОГО ЦЕНТРА РАН, Том 2, № 4У 2006, стр. 25-30
= НАНОЭЛЕКТРОНИКА ===========
УДК 681.5.015.4
ПЕРЕСТАНОВКИ ЭЛЕМЕНТОВ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В БЫСТРЫХ АЛГОРИТМАХ ЦИФРОВОЙ ОБРАБОТКИ
СИГНАЛОВ
© 2006 г. Ё.А. Семерников1, Е.Е. Семервикова2
В статье предлагается математический аппарат, позволяющий описать перестановки элементов цифровых последовательностей, возникающие на разных стадиях быстрых алгоритмов ЦОС, с помощью аппарата матриц перестановок. Доказывается ряд теорем, используя которые можно выполнять перестановки элементов цифровых последовательностей, получать необходимые матрицы перестановок по известным матрицам в суперпозициях функций, задающих последовательности, и получать матрицы перестановок, если известны элементы последовательности.
Алгоритмы цифровой обработки сигналов (ЦОС) оперируют цифровыми последовательностями, изменяя не только значения элементов, но и их порядок [1, 2]. В этом плане классическим примером может служить алгоритм быстрого преобразования Фурье (БПФ), в процессе выполнения которого порядок данных изменяется от итерации к итерации, пока не сформируется окончательный результат. Исследователи, которые пользуются готовыми программными и аппаратными решениями, могут не задумываться над этими проблемами. Однако те из них, кто создает новые технические решения, специализированные устройства или оригинальные программы, должны точно представлять себе, как меняется порядок данных на различных стадиях алгоритмов.
Перестановки элементов цифровых последовательностей, возникающие в процессе выполнения алгоритмов со структурой быстрых ортогональных преобразований типа БПФ, имеют определенную специфику - все они могут быть описаны перестановками бит в двоичном пред-ставлении номера элемента. В предлагаемой статье на основе формального определения цифровой последовательности предлагается аппарат, позволяющий описать и контролировать порядок данных в цифровых последовательностях, которые используются в быстрых ортогональных алгоритмах ЦОС,
1. Цифровые последовательности. В математике последовательностью элементов множест-
1 Южный научный центр Российской академии наук, Ро-стов-на-Доку.
2 Таганрогский государственный радиотехнический университет, Таганрог.
в а X называется функция /, определенная на множестве натуральных чисел Я, множество значений которой содержится в X и обозначается как/: X —» X, или дг(гс), где п е >Г, х е X. Элементом последовательности х(п) называется упорядоченная пара {п, Натуральное число п называется номером элемента последовательности, а элемент х е X — его значением.
Последовательности х(п), которыми оперируют алгоритмы ЦОС, называются цифровыми последовательностями (ЦП), так как их элементами являются числа. При представлении элементов ЦП в том или ином формате, принятом в цифровой вычислительной технике, они могут быть записаны в оперативную память с целью дальнейшего использования. Для ЦП справедливо [1]:
1) множество X в общем случае является мультимножеством [3,4], поскольку элементы X могут быть кратными (одинаковыми числами);
2) количество элементов N (чисел) последовательности х(п) конечно;
3) номера п элементов последовательности х(п) принадлежат конечному множеству = {0,1,
N - 1} целых не отрицательных чисел, п € Нумерация элементов последовательности с нуля объясняется тем, что номер элемента последовательности х(п) можно трактовать как его адрес в оперативной памяти;
4) порядок следования элементов последовательности друг за другом наряду с их значениями отражает суть физических процессов, описываемых ЦП.
Примером ЦП может служить последовательность цифр х{п), получаемых аналого-цифровым преобразователем (АЦП) при оцифровке непре-
рывного сигнала х(г) в течение ограниченного промежутка времени. В этой последовательности содержится конечное количество элементов (цифр), среди которых могут быть одинаковые цифры, номера п элементов последовательности соответствуют очередности их появления на выходе АЦП, все элементы последовательности (даже совпадающие по величине) имеют индивидуальные, отличные от других, номера п е /У+.
Определить ЦП как функцию / Л —> X не представляется возможным, поскольку X является мультимножеством. Поэтому с целью упорядочения элементов ЦП введем понятие естественной нумерации (Е-нумерации) элементов мультимножества X. Например, для элементов X, получаемых посредством оцифровки аналогового сигнала, Е-нумерации будет соответствовать очередность появления элементов X во времени. Порядок множества элементов цифрового спектра сигнала ¿(л), п = О, 1, N - 1, полученного с помощью алгоритма дискретного преобразования Фурье, несет информацию о частоте составляющих спектра. Будем говорить, что элементы цифрового спектра имеют Е-нумерацию, если они пронумерованы в порядке возрастания частот. Примеры Е-нумерации для элементов мультимножеств можно продолжить, однако очевидно, что для элементов любого мультимножества всегда можно ввести Е-нумерацию, основываясь на заранее определенных принципах.
Введение Е-нумерации оправдано еще и тем, что практически во всех алгоритмах ЦОС обработка данных предполагает перестановки элементов последовательностей, изменяющие их порядок. Поэтому на каждом этапе обработки требуется либо восстанавливать естественный порядок данных, либо следить за изменением порядка данных.
Е-нумерация предполагает, что пронумерованные элементы X представляют собой упорядоченные пары {т, х\ т е дг е X, при этом т называется номером элемента согласно Е-нумерации, элементхе Х- его значением. Таким образом, все элементы мультимножества X становятся различными, так как любые два элемента отличаются, по крайней мере, номерами. Упорядоченные пары (т, х) образуют множество Множество элементов Хй можно упорядочить, расположив их в порядке возрастания номеров т е
Теперь можно ввести определение ЦП аналогично математическому определению последовательности.
Определение 1. Цифровой последовательностью элементов множества Х0 называется
функция/р, определенная на множестве множество значений которой содержится в Х0 и обозначается как /¿>: —» Хв или хП(п), где -множество целых неотрицательных чисел, Х0 -множество упорядоченных пар {т, х), т € х € X. Элементом последовательности х0(п) называется упорядоченная пара {пу (т, х)), п € Лг+. {т, х) е Хп. Целое положительное число п называется номером элемента последовательности хр(п), т - номером элемента х е X по Е-нумерации, а элемент х € X упорядоченной пары {т, х)е Х0 — его значением.
Вели функция/^ = /£ такова, что для всех элементов (п, (т, *)} ЦП выполняется т = п и элементы (л, {п, х)} последовательности х0(п) упорядочены так, что за элементом (п,(п, х)) непосредственно следует элемент {п + 1, (п + 1, дг)), то будем говорить, что элементы х0(л) имеют Е-порядок.
Если функция /о и хотя бы для двух элементов (л, (т, л)) ЦП х1р(л) выполняется т * я, то элементы последовательности х1в(п) не имеют Е-порядка. В этом случае функция образует ЦП -г10(и), отличающуюся от х0 (л) только порядком следования элементов.
2. Цифровые последовательности номеров. Из определения 1 и способа введения Е-нумерации следует, что функция/л не только определяет ЦП х0(п), но и устанавливает взаимно-однозначное соответствие между номерами п и т в элементах (п, (т, х)), п е Л^, т е этой ЦП. Это становится очевидным, если предположить, что все элементы мультимножества X одинаковые (а такое вполне реально [1, 2]). Тогда после введения Е-нумерации элементы различаются только номерами т.
Определение 2. Цифровой последовательностью номеров (ЦПН) называется функция fD\
—> которая каждому элементу л € N + ставит в соответствие элемент те N+ из множества упорядоченных пар (п, (т, х)) ЦП ЛГ+ —> Х0. Элементом ЦПН—> Л/+, обозначаемой далее/0]у(лХ называется упорядоченная пара (п, т), п е Лг+, т е Целое положительное число пе N4. называется номером элемента последовательности /ОЛг(л), а элемент те упорядоченной пары (п, т) - номером элемента х по Е-нумерации во множестве упорядоченных пар {п, (т, х» ЦП и Хв.
Определение 3. Цифровая ППН п е ЛП+ = 0, 1, N1 - 1, равна цифровой ЦПН Ьок(п)г п € N2+ = 0, 1,N2-1 тогда и только тогда, когда:
1) количество элементов последовательностей равны: N1 = N2 = Л/;
перестановки элементов последовательностей
27
2) порядок элементов последовательностей %(«) и ЪОЬ1{п), п € /тг е N+ совпадает: V* е ЯщШ = Ьоы{к) - {к, т2), имеет место
т[ - т2.
Поскольку одна и та же функция^ определяет как ЦП х{п), п = 0, 1,N - 1, так и ЦПН, связывающую номера и и то во множестве упорядоченных пар (я, {т, х)} этой же ЦП, то при изучении перестановок элементов ЦП х(п) можно рассматривать перестановки элементов ЦПН/0/у(л).
Последовательность может задаваться формулой ее общего члена [1,2], поэтому для функции /о = /е введем специальное обозначение ЦПН = и, п = 0, 1, 1, или более крат-
ко епу(п). Элементами ЦПН еоы{п), определяемой функцией/Е, являются упорядоченные пары {п, п). Эта последовательность будет в дальнейшем использоваться нами в качестве базовой для получения перестановок элементов ЦПН и элементов ЦП х{п).
3. Перестановки элементов последовательностей. Выше мы упоминали, что номера т могут трактоваться как адреса элементов мультимножества X в оперативном запоминающем устройстве (ОЗУ). При таком подходе ЦПН является последовательностью адресов элементов хп{п) в ОЗУ, а перестановки элементов последовательности *д(я) можно осуществлять процедурами записи/чтения, используя ЦПН в качестве адресных последовательностей при обращениях к ОЗУ.
Пусть элементы последовательности х0(п) записаны в ОЗУ по последовательности адресов Это означает, что по адресу п = 0 записан элемент мультимножества д^ е X из пары {0, д:0), по адресу п = 1 - элемент х^ е X из пары (1, хг) и так далее вплоть до адреса п - N - 1, в котором будет записан элемент 1 е X из пары (М - 1,
Для перестановки элементов ЦП хр(п) можно считать их из ОЗУ по последовательности адресов которую определяет функция /[} * Д-. В результате образуется последовательность х\¿.(л), определяемая той же функциейПоследователь
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.