14.6. ДИСКРЕТНЫЕ ФУНКЦИИ УОЛША

Для цифровых методов спектрального анализа и обработки сигналов наибольший интерес представляют дискретные функции Уолша. Эти функции являются отсчетами непрерывных функций Уолша. Каждый отсчет расположен в середине связанного с ним элемента непрерывной функции. Длительность элемента равна 1/N от интервала [0,1).

В качестве примера на рис. 14.24 показаны первые две и последняя (N-1)-я дискретные функции Уолша при . В качестве аргумента дискретной функции Уолша принят номер отсчета (см. ось абсцисс на верхней части рис. 14.24). Основываясь на (14.21) и (14.22), можно получить общее выражение для дискретной функции Уолша

(14.31)

где или 1 есть k-й разряд в представлении номера отсчета х в двоичной системе счисления:

(14.32)

Пусть, например, рассматривается система функций Уолша размером . Тогда

(14.33)

Определим одну из функций системы, например шестую (w = 6). По модулю все отсчеты функции Уолша равны единице и требуется определить лишь знак. Обратимся для этого к формуле (14.31), в которую подставим и :

Напомним, что в соответствии с (14.21) при

откуда следуют равенства

Далее находим значения и сумму

Значения (нуль или единица) находим из выражения (14.32), приравнивая номер отсчета последовательно значениям

При все разряды равны нулю и, следовательно, по формуле

При соответственно при этом показатель степени в (14.31) при равен

При показатель степени в (14.31) при равен откуда получаем

Вычисленные три отсчета в точках и 2 согласуются с ходом непрерывной функции на рис. 14.13. Продолжая расчет для находим все отсчеты функции

Другой формой представления дискретных функций Уолша являются матрицы Адамара, приведенные в § 14.4. Номера столбцов матрицы Адамара соответствуют номерам дискретных значений функций Уолша, а номера строк — номерам функций Уолша. Строки матрицы Адамара могут быть упорядочены по Пэли, по Уолшу и собственно по Адамару.

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

Ортогональность

(14.34)

Дискретные функции Уолша не нормированы; норма равна N независимо от номера функции.

Мультипликативность

(14.35)

Пусть сигнал s(t) (вещественная функция) представлен совокупностью своих эквидистантных отсчетов

Тогда преобразования

(14.36)

образуют пару дискретных преобразований Уолша (ДПУ). Выражения (14.36), (14.37) аналогичны паре ДПФ в базисе гармонических функций [см. (12.14), (12.15)].

Как и ДПФ (см. § 2.17), ДПУ обладают свойством периодичности

(14.38)

где m — целое число.

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

Действительно, вводя под знак суммы в правой части (2.127) множитель получаем

что эквивалентно сдвигу каждого из отсчетов на интервалов.

Проведем аналогичное рассуждение для ДПУ. Обращаясь к выражению (14.37) для , вводим под знак суммы множитель , т. е. базисную функцию, имеющую тот же смысл, что и для анализа в базисе гармонических функций; тогда получим

(14.39)

Здесь использовано свойство мультипликативности функций Уолша. Как видим, при заданном значении сдвиг отсчета будет равен интервалов (а не просто m интервалов).

Переход от и означает диадный сдвиг на m интервалов последовательности отсчетов

Поясним смысл термина «диадный сдвиг». С понятием «сдвиг функции» приходится иметь дело, например, при определении корреляционной функции, при рассмотрении теоремы запаздывания, при определении свертки двух функций. В обычном смысле сдвиг рассматривается как параллельный перенос сдвигаемых значений колебания вдоль оси времени. Такой сдвиг можно назвать арифметическим, так как он выражается обычным арифметическим сложением или вычитанием. При арифметическом сдвиге, например, на интервала k-й отсчет переместится и станет При достаточно большом отсчет выйдет за пределы исходной совокупности отсчетов. При диадном сдвиге тот же отсчет , сдвинутый на займет положение , так как

Диадный сдвиг обладает так называемым групповым свойством: сдвиг отсчетов на соответствует лишь перестановке этих отсчетов внутри их исходной совокупности. Эта перестановка определяется операцией сложения по модулю 2, т. е. , для которой результат сложения всегда не превышает число при любом . При этом имеется в виду, что где n — целое положительное число.

Сделанное утверждение легко проверить перебором всевозможных диадных сдвигов всех отсчетов при заданном N. Например, при N = 8 получается следующая квадратная матрица значений

Из этой матрицы видно, что диадный сдвиг не выводит сдвинутые отсчеты за пределы исходной совокупности N отсчетов, а лишь производит их перестановку внутри этой совокупности.

Например, при исходной последовательности получим следующие последовательности:

Диадный сдвиг придает существенное своеобразие как спектральному анализу в базе функций Уолша, так и представлению сигналов во временной области.

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

Основное преимущество ДПУ перед ДПФ заключается в том, что отсчеты сигнала умножаются на функции Уолша, которые принимают значения [см. (14.36), (14.37)]. По существу, операция умножения исключается и выражения (14.36), (14.37) сводятся к суммированию отсчетов с соответствующими знаками. В случае же ДПФ требуется умножение на комплексные числа вида , причем действительная и мнимая части этих чисел требуют представления достаточно большим числом разрядов (для снижения уровня шума округления).

По аналогии с БПФ и ОБПФ можно построить алгоритмы быстрых преобразований — прямого и обратного — по Уолшу.

Для вычисления спектральных коэффициентов при использовании БПУ требуется всего операций сложения и вычитания.

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

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