Г. Преобразования Уолша и Хаара.

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

где по порядку следования функция Уолша и спектр Уолша.

В литературе встречаются различные обозначения спектра Уолша и в зависимости от вида упорядочения и способа нормализации по-разному обозначаются базисные функции Уолша, В этом разделе будем придерживаться обозначений, принятых в книге [74], в которой дано обстоятельное описание преобразований Уолша и рассмотрены их свойства. В дальнейшем делаются ссылки на эту книгу. Здесь для спектра Уолша принято обозначение и для функций Уолша обозначение в связи с тем, что функции нормализуются указываемым далее методом при . В § 3, рассматривая применение функций Уолша и Хаара при анализе и синтезе устройств логического действия, примем, как это сделано в книге [42], для спектра Уолша обозначение При этом буквой со и ранее указанными буквами обозначено одно и то же. Пользуясь оговоренными для данного раздела обозначениями, перепишем, имея в виду непрерывную функцию приведенную выше формулу ряда Уолша

Здесь

Ограничиваясь N членами разложения, получают формулу усеченного ряда Уолша

Для практического пользования рекомендуется формула определения получаемая из формулы (4.7):

в которой номер подынтервала интервала определения функции причем последняя величина принимает значение 1, —1 или 0 в зависимости от того, меняет ли в точке знак на на или же знак остается неизменным; ранг спектрального коэффициента (напомним, что рангом функции Уолша с номером а является число двоичных разрядов, в которых число а при двоичном его представлении имеет единицы)

Вывод формулы (4.9) приведен в книге [74]. Применение ее иллюстрируется следующим примером. Разложение функции в ряд по упорядоченным по Пзли функциям Уолша при производится с использованием того, что Получены Соответственно с этим функция приближенно представляется рядом Уолша

Для ряда Уолша, к которому относятся формулы (4.6) и (4.7), равенство Парсеваля предствляется в виде

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

1) если где вещественные числа и функции с интервалом определения для которых является спектром Уолша, то Ъкаа при

2) при умножении на где номер функции Уолша,

где знак суммирования по модулю 2;

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

4) если причем спектрами Уолша функций и являются соответственно то

5) для так называемой двоичной илидиадной свертки считая, что — соответственно спектры свертьшаемого сигнала и имеем

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

Важным является общее свойство конечности разложения кусочно-постоянных функций: для любой такой функции, у которой имеется (при ) равных участков постоянства, ряд Уолша содержит не более N членов.

Доказательства указанных выше свойств спектров Уолша и свойства конечности разложения приведены в книге [74]. Там же сформулировано и упоминавшееся правило согласования интервалов задания преобразуемой и базисных функций. Согласование в общем случае производится следующим образом. При представлении в формулах (4.6), (4.7), (4.8) функций Уолша в виде они получаются из исходных, ортогональных на отрезке [0, 1) функций Уолша изменением аргумента последних функций. Преобразование производится с использованием формулы

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

Дискретное преобразование Уолша производится при использовании дискретных функций Уолша, рассмотренных нами в разделе Б § 2. Количество отсчетов преобразуемой функции берется равным где Следуя [74], примем здесь следующие обозначения: для преобразуемых, определенных на интервале решетчатых сигналов

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

Формула дискретного ряда Уолша

где

Равенство Парсеваля для таких сигналов имеет следующий вид:

Для ускорения дискретных преобразований Уолша используются алгоритмы быстрого преобразования Уолша аналогичные рассмотренным в гл. III алгоритмам БПФ. Быстрое преобразование Уолша также производится с прореживанием по времени или с прореживанием по частоте. При прореживании по времени последовательность первоначально разделяется на две части, к первой из которых относятся отсчеты с четными номерами а ко второй - с нечетными номерами где Для первой и второй из них спектры Уолша равны

при При этом спектр Уолша, определяемый уравнением (4.11), рассчитывается по формуле

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

и для коэффициентов при а с номерами от до которых имеет место соотношение

Оно с учетом того, что для приводится к виду Для значений при условии, что имеет место

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

Указанные выше выводы аналогичны выводам, сделанным в гл. III для БПФ. Таким же образом получаются формулы БПУ с основанием 2 при прореживании по частоте, формулы быстрых преобразований Уолша с произвольным основанием, а также формулы, по которым производится с использованием БПУ расчет мгновенных (скользящих) спектров [74].

На общность алгоритмов БПУ и БПФ указывает то, что графы тех и других быстрых преобразований имеют одинаковую конфигурацию. В качестве примера на рис. 4.9 показаны для восьмиточечных выборок сигнала графы алгоритмов БПУ, выполняемых с прореживанием по времени [74]. На рис. 4.9, а представлен граф БПУ с основанием 2, на рис. граф БПУ с основанием 4. Первый из них такого же вида, как граф БПФ, приведенный на рис. При выполнении БПУ согласно графу, изображенному на рис. 4.9, б, все операции, так же как и в первом случае, являются операциями "бабочка". Однако расположение ветвей графа для второй ступени преобразования здесь иное. С такой конфигурацией графа мы тоже встречались в гл. III (см. рис. 3.9,6). БПУ, иллюстрируемые рис. 4.9, выполнены при использовании функций

Рис. 4.9

Уолша, упорядоченных по Пэли. Иногда, как уже отмечалось, целесообразно пользоваться функциями Уолша, упорядоченными по Адамару. В частности, это относится к рассматриваемой в гл. V обработке изображений. В некоторых случаях при представлении функций в виде ряда Уолша удобно разделить упорядоченные по Уолшу функции Уолша по системе Хармута на функции с обозначениями

Так же выполняются и преобразования Хаара. Формула ряда Хаара, формулы дискретного преобразования Хаара и соответствующего быстрого преобразования (БПХ) получаются аналогично тому, как это было указано для преобразований Уолша. Они рассмотрены в книгах и статьях, упоминаемых в § 6 этой главы. Эти формулы пока не будем приводить здесь. Но в § 3 на конкретном примере покажем, как производится преобразование Хаара, и сравним его выполнение с выполнением преобразования Уолша. При этом будут приняты обозначения: для преобразуемой функции; для упорядоченных по Пэли функций Уолша и для функций Хаара; для коэффициентов соответствующих спектральных разложений. Принятие этих обозначений будет удобным для сравнения рассматриваемых в § 3 результатов с другими результатами, указанными в книге [42], на которую делаются ссылки.