Скалярный метод синтеза быстрых



Скачать 83,72 Kb.
Дата31.10.2016
Размер83,72 Kb.


УДК 519.216.1/2

В.В. Сюзев



СКАЛЯРНЫЙ МЕТОД СИНТЕЗА БЫСТРЫХ

ПРЕОБРАЗОВАНИЙ УОЛША-АДАМАРА
Рассмотрена оригинальная методика синтеза быстрых преобразований в базисе Уолша-Адамара, основанная на скалярной форме записи дискретных преобразований Уолша и различных способах прореживаний сигнала и его спектра. Теоретические результаты проиллюстрированы конкретными примерами
E-mail: k-iu6 @ bmstu.ru; v.suzev @ bmstu.ru

Ключевые слова: функции Уолша-Адамара, дискретные и быстрые преобразования Уолша, спектры, прореживание сигнала и спектра, сигнальные графы.
Базисные системы, использующие функции Уолша с различным порядком их следования, находят самое широкое применение в различных областях науки и техники. Это связано с целым рядом полезных свойств этих функций и наличием для них эффективных алгоритмов быстрого преобразования Уолша (БПУ) [1, 2]. В основе большинства существующих методов синтеза БПУ лежат различные способы факторизации матриц Уолша [2, 3, 4], что приводит при программировании БПУ к необходимости выполнения дополнительного этапа преобразования матричного алгоритма БПУ к скалярному виду. Применение же классического скалярного подхода Кули-Тьюки для синтеза БПУ возможно только для упорядочений Пэли и Хармута и не возможно для системы Уолша-Адамара [4]. В данной работе предлагается оригинальная модификация скалярного метода, позволяющая получать скалярные алгоритмы БПУ-Адамара для различных способов прореживания сигнала и его спектра.

Дискретные функции Уолша-Адамара, определенные в (n – целое положительное число) точках, представляются в виде [2]



(1)

где и означают m-е разряды двоичных n разрядных разложений номера k и аргумента i функций соответственно и принимают значения 0 или 1. Из формулы (1) следует, что в аналитической записи этих функций двоичные разряды чисел k и i располагаются в согласованном порядке: первый с первым, второй со вторым и т.д. Поэтому простую взаимосвязь между N-точечным и N/2 –точечным базисными функциями, необходимую для синтеза быстрых алгоритмов, можно получить в системе этих функций только при одинаковых законах изменениях k и i , т.е. либо с прореженным, либо c естественным порядками следования.

Действительно, если принять прореженный характер изменения чисел k и i: и , где , то

(2)

При естественном (непрореженном) порядке следования значений k и i: и



(3)

Эти свойства функций Уолша-Адамара вытекают из особенностей представлений n- и (n-1)-разрядных двоичных чисел и являются следствием блочной структуры матриц Адамара [2].

Формулы (2) и (3) создают математические предпосылки для построения эффективных алгоритмов БПУ-Адамара. Из них следует, что при синтезе БПУ-Адамара классические способы прореживания неприменимы, но возможно их комбинированное использование. Это в свою очередь приводит к возможности организации двух типов быстрых алгоритмов на основе прореженного порядка следования отсчетов сигнала и спектра и на основе естественного порядка их следования.

Алгоритмы БПУ-Адамара с прореженным порядком следования отсчетов сигнала и спектра. Запишем дискретное преобразование Уолша-Адамара сигнала в виде

(4)

где есть спектр сигнала, а сам сигнал равен



(5)

Разобьем N-точечную выборку сигнала на две промежуточных выборки с отсчетами с четными и нечетными номерами соответственно: и , спектры которых будут равны



(6)

Тогда полный спектр X(k) (4) можно преобразовать к виду





Так как 2i есть четное число, то в 2i+1 обычное сложение можно заменить на поразрядное сложение по модулю 2, обозначив его как (+). Тогда 2i+1=2i(+)2 1 и в силу свойства мультипликативности функций Уолша [2] можно записать



Поэтому


(7)

Рассмотрим раздельно две части спектральных коэффициентов, образованных из их составляющих с четными и нечетными номерами.

Для первой части k=2k и

(8)

Для второй - k=2k+1 и



(9)

Но



и

Поэтому с учетом формул (2, 3) и соотношений (6) окончательно получаем

(10)

Эти уравнения и представляют собой аналитическое описание алгоритма БПУ-Хармута на первом уровне прореживания. В нем проявляется явная и простая связь спектра входной выборки со спектрами промежуточных выборок.

Ясно, что данный алгоритм можно использовать и для вычисления промежуточных спектров, вводя новые уровни прореживания. На m уровне алгоритм принимает следующий вид записи:

(11)

где


(12)


а промежуточные выборки и задаются формулами



(13)


Изменяя переменную m от 1 до n-1 с помощью выражений (11), (12) можно записать все стадии процесса быстрого анализа спектра Уолша-Адамара, получив полное БПУ-Адамара. Сама организация вычислений по этому алгоритму требует изменения индекса m от n-1 до 1. Начальными данными в этом случае будут являться спектры 2-точечных выборок на (n-1)-м уровне прореживания




(14)

где


(15)



а результатом – полный спектр и , получаемый на первом уровне. Полному алгоритму БПУ-Адамара будет соответствовать полный сигнальный граф, прямоугольная структура которого содержит (n+1) уровней и N(n+1) узлов. Во всех узлах, кроме узлов крайнего левого уровня, выполняются операции сложения. Крайние левые узлы служат для хранения отсчетов анализируемого сигнала, результирующий спектр формируется в крайних правых узлах. Поскольку такой граф содержит Nn вычислительных узлов, то для реализации полного БПУ-Адамара этого типа необходимо выполнение

сложений. Это число совпадает с числом сложений, требуемых для реализации полных алгоритмов БПУ в системах Пэли и Хармута [4].



Пример 1. Записать полный алгоритм БПУ-Адамара первого типа и построить его сигнальный граф для N=8.

Решение. В этом случае полный алгоритм БПУ-Адамара будет содержать два уровня прореживания (m=1,2). Поэтому в соответствии с формулами (11)-(13), имеем:

- начальные данные:













- на втором уровне прореживания (m=2,









- на первом уровне прореживания









Сигнальный граф, иллюстрирующий этот алгоритм, приведен на рис. 1.



Алгоритмы БПУ-Адамара с естественным порядком следования отсчетов сигнала и спектра. Разобьем N-точечную выборку сигнала на две соприкасающиеся промежуточные выборки и , первую из которых образуем из первой половины отсчетов, а вторую – из второй половины, т.е. приняв =, а Тогда полный спектр (4) можно представить следующим образом



Но


Поэтому


(16)

Теперь с помощью этого уравнения запишем спектральные коэффициенты сначала первой половины спектра Адамара , а затем второй его половины





Если теперь учесть в этих выражениях тот факт, что



и , а также соотношение (3), то после преобразования и сравнения с зависимостями (6) получим





Функции и Поэтому в окончательном виде



(17)

Эти уравнения и задают алгоритм БПУ-Адамара второго типа на первом уровне прореживания. По форме записи они совпадают с уравнениями (10) алгоритма БПУ-Адамара первого типа и отличаются только правилом образования промежуточных выборок сигнала.

На произвольном m-м уровне прореживания алгоритм БПУ-Адамара выглядит следующим образом:

(18)

В этих выражениях промежуточные спектры описываются соотношениями (12), а промежуточные выборки равны



(19)



Изменяя параметр m от 1 до n-1, с помощью зависимостей (18) можно описать полный алгоритм БПУ-Адамара, а изменяя его в обратном порядке от n-1 до 1, – организовать процесс быстрого вычисления спектра Уолша-Адамара, используя начальные данные (11) с

(20)


В результате на первом уровне прореживания будет получен полный спектр и

Сигнальный граф, иллюстрирующий полный БПУ-Адамара второго типа, будет иметь структуру, подобную структуре полного графа БПУ-Адамара первого типа, но с другим порядком следования отсчетов сигнала и спектральных коэффициентов. Для его реализации потребуется то же число сложений, что и для реализации полного графа БПУ-Адамара первого типа.

Пример 2. Записать полный алгоритм БПУ-Адамара второго типа и построить его сигнальный граф для N=8.

Решение. Полный алгоритм будет содержать два уровня прореживания. Промежуточные выборки и их спектры равны:











Промежуточные же спектры на втором уровне в соответствии с алгоритмом (18) примут следующий вид:









На первом уровне прореживания, используя уравнения (17), получаем:









Сигнальный граф этого алгоритма приведен на рис. 2.

Таким образом, в статье разработаны высокоэффективные алгоритмы преобразования Уолша-Адамара, основанные на циклических вычислительных процессах, описываемых простыми рекуррентными соотношениями. Эти алгоритмы хорошо структурированы, легко программируются и являются эффективным средством анализа спектра Уолша-Адамара.
СПИСОК ЛИТЕРАТУРЫ


  1. Залмазон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. - М.: Наука, 1989. - 496с.

  2. Трахтман А.М., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. – М.: Сов. Радио, 1975. – 208с.

  3. Власенко В.А., Лаппа Ю.М., Ярославский Л.П. Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов. – М.: Наука, 1990. - 180с.

  4. Проектирование специализированных информационно-вычислительных систем: Учебное пособие / Ю.М. Смирнов и др. – М. Высш. шк., 1984.- 359с.

Рисунки







Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница