Изучение и формирование функций Уолша

1 Цель работы

Изучение свойств и методов синтеза функций Уолша и их преобразова­ния. Изучение областей применения функций Уолша в системах обработки информации.

 

2 Теоретическая часть

В последнее десятилетие значительно возросло применение функций Уолша в цифровой обработке информации. Это связано с особенностью функций Уолша: каждая из них принимает только два значения: +1 и -1. Благодаря этому можно заменить операцию умножения при реализации на ЭВМ. В ре­зультате время выполнения дискретного преобразования Адамара для большо­го массива числовых данных почти в 10 раз меньше времени дискретного пре­образования Фурье. Дискретные преобразования по функциям Уолша (ДПУ) позволяют добиться лучшего, чем при дискретном преобразовании Фурье (ДПФ), распараллеливания вычислений, производства одновременных вычис­лений на одиночных процессорах, позволяют проводить основные вычисления без операции умножения чисел только с помощью операции сложения.

В частности, ДПУ применяются в различных процессорах цифровой обработки информации: при сжатии информации, в теории кодирования, в теории построения цифровых фильтров, голографических преобразованиях для обработки изображений, решения некоторых задач оптимизации и др.

 

2.1 Некоторые основные сведения, необходимые при работе с функциями Уолша

2.1.1 Основные определения

Введем периодическую функцию с периодом 1

, (2.1)

где ­­- безразмерное время, т.е. время, нормированное к произвольному

интервалу Т; k - порядок функции, (k = 1, 2,..., n,...),

Функции r_k называются функциями Радемахера.

Графики функций r_k (0) на [0; 1] при k =2, 3 изображены на рисунке 1.1.

Рисунок 1.1

 

Систему из N=2ⁿ функций Уолша можно сформировать в результате перемножения n первых функций Радемахера (меандровых функций).

Способ нумерации базисных функций в системе называется упорядоче­нием.

Существуют различные упорядочения функций Уолша: по Уолшу, по Пэли и другие.

При упорядочении по Уолшу способ формирования и аналитическая запись функций имеют следующий вид:

, (2.2)

где w -номер функции в системе;

w_m - m-ый разряд в представлений числа w в двоичной системе счисления (w_m равно или 0, или 1), т.е.

(2.3)

«»-символ сложения по модулю 2.

При упорядочении по Пэли систему функций Уолша получают по формулам

, (2.4)

где р - номер функции, имеющей двоичное представление:

, (2.5)

Таким образом, при упорядочении по Пэли для формирования функции Уолша необходимо взять произведение возведенных в степень функций Радемахера, номера которых совпадают с номерами соответствующих разрядов представления числа р в двоичной системе счисления, а показатель степени каждой функции равен содержимому соответствующего разряда, т.е. 0 или 1. Причем, младшей функции Радемахера соответствует младший разряд двоичного числа р.

Сравнивая способ преобразования показателей степеней функций Радемахера при различных упорядочениях, замечаем, что двоичные разряды номе­ров функций Уолша, упорядоченных по Пэли, связаны с двоичными разрядами номеров функций Уолша, упорядоченных по Уолшу следующим соотношени­ем:

.6)

2.1.2 Свойства функций Уолша

Система функций Уолща является полной ортонормированной системой на интервале [0, 1].

Наиболее важные свойства функций Уолша:

а) функции Уолша, как и функции Радемахера, принимают только два значения: -1 и 1. Для любого m

;

б) функции Уолша ортонормированы на интервале

в) функции Уолша являются периодическими функциями с периодом равным 1;

г) функции Уолша обладают свойством мультипликативности, произведение любых двух функций Уолша является также функцией Уолша

; (2.7)

д) функции Уолша симметричны относительно i и θ, т.е. все выводы относительно i справедливы также и относительно θ;

е) среднее значение функций Уолша wal(i, θ) при на [0, 1] равно ну­лю;

ж) система функций Уолша является составной системой. Она распадает­ся на систему четных функций, обозначаемых cal(j, θ), и систему нечетных функций sal(j, θ), которые связаны с функциями, упорядоченными по Уолшу следующим соотношением:

(2.8)

3 Синтез функций Уолша

Функциональная схема синтеза функций Уолша должна содержать:

- задающий генератор;

- генератор функций Уолша;

- блок установки весовых коэффициентов функций Уолша;

- сумматор.

Генератор функций Уолша состоит из

- двоичного счетчика, представляющего собой генератор функций Раде­махера;

-умножителей.

Операции перемножения функций Уолша выполняют сумматоры по модулю два, у которых логическому 0 соответствует 1 функции Уолша, а логиче­ской 1 соответствует 0 функции Уолша.

Период функций Уолша определяется частотой задающего генератора.

4 Задание к работе

4.1 Изучить теорию функций Уолша, установить соответствие номеров первых 16-ти функций Уолша, упорядоченных по Уолшу и Пэли. Результаты представить в виде таблицы 1

 

Таблица 1

w	p

 

4.2 Представить каждую функцию Уолша как результат перемноженных функций Радемахера, предварительно записав номер функции Уолша (по Пэли) в двоичном счислении и определив, какие функции Радемахера участвуют в образовании данной функции Уолша.

4.3 Изобразить функциональную схему генератора функций Уолша и по­яснить его работу.

4.4 Построить графики 16-ти первых функций Уолша wal(i, θ), упорядо­ченных по Пэли.

 

4.1 Решение примера

Рассмотрим соответствие первых двух функций Уолша, упорядоченных по Пэли и по Уолшу.

При упорядочении по Уолшу имеем:

Рассмотрим w =1. В двоичном представлении (1)₁₀=(1)₂. Тогда по форму­ле (2.2) (n=l, k=l)

, (2.9)

т.к. w ₀=0, a w ₁=1.

Рассмотрим w =2. В двоичном представлении (2) ₁₀=(10) ₂. С помощью

(2.3) имеем w ₀=0, w ₁=1, w ₂=0 (n=2, к=1, 2). Из формулы (2.2) получим

(2.10)

При упорядочении по Пэли будет следующее.

Возьмем р =1. В двоичном представлении (1)₁₀=(1)₂. Тогда по формуле

(2.4) n=l, k=l, p=1.

(2.11)

Рассмотрим р =2. В этом случае (2) ₁₀=(10) ₂, p ₁=l, р ₂=0, n=2, k=1, 2. По формуле (2.4) получим

(2.12)

Таким образом, для первых функций Уолша, упорядоченных по Уолшу и Пэли w = р =1, для других w > 1 и р > 1 соответствие номеров меняется.

Представление функций Уолша и через функции Радемахера будет иметь вид:

Построение графика функций wal(1, 0) и wal(2, Ө) произведем на экране дисплея с использованием графических операторов любого известного языка.

Для построения осей координат используем оператор изображения линий LINE, а дляя построения изображения графика функций Уолша – оператор изображения точки PSET. Построение графиков произведем на отрезке (0, 1)

Блок-схема приведена на рисунке 1.2

 

Для построения графиков 16-ти первых функций Уолша, упорядоченных по Пэли, необходимо иметь разряды (2.5) двоичного представления числа k –номера функции, т.к. мы используем формулу (2.4).

Такая запись необходима для определения функций Радемахера, участвующих в образовании функций Уолша путем перемножения.

Разряды двоичных представлений чисел 1, …, 16 разместим в массивах A(16), B(16), C(16), D(16). Номер функции Уолша k запишем в двоичном коде функциями Радемахера, значения которых разместим в массивах A, B, C, D (рисунок 1.3).

Кроме того, необходимо добавить операторы:

5 Порядок выполнения работы

1. Ознакомиться с теорией функций Уолша и законспектировать в отчет.

2. Получить задание у преподавателя.

3. Выполнить теоретическое задание: заполнить таблицу, нарисовать схемы и графики; результаты занести в отчет.

4. Составить блок-схему изображения графиков функций Уолша.

5. Составить программу на алгоритмическом языке.

6. Произвести расчет на ЭВМ и зарисовать графики функций.

7. Составить письменный отчет по работе.

6 Требования к отчету

Отчет по лабораторной работе должен содержать:

а) краткую теорию функций Уолша;

б) функциональную схему генератора функций Уолша;

в) таблицу соответствия номеров функций Уолша при разных способах упорядочения;

г) графики функций Уолша, упорядоченных по Пэли;

д) выводы и оценку полученных результатов.

Лабораторная работа защищается при представлении студентом аккуратно оформленного отчета и самостоятельного решения задания.

7 Контрольные вопросы

1. Изобразить функции Радемахера r₁(Ө), r₂(Ө), r₃(Ө), r₄(Ө).

2. Установить, какие функции Радемахера участвуют в образовании функции Уолша wal(13, Ө), wal(14, Ө) при нумерации по Пэли, по Уолшу?

3. Перечислить и объяснить различные свойства функций Уолша.

4. Какую функцию Уолша получим, перемножив wal(7, Ө) и wal(11, Ө) при нумерации по Пэли? При нумерации по Уолшу?

5. Изобразить функциональную схему генератора функций Уолша и пояснить его работу.

6. Назвать достоинства и недостатки различных способов упорядочения функций Уолша.