3.8. Использование дискретных преобразований Фурье

Вычисление свертки.

Одно из важнейших применений дискретных преобразований Фурье — вычисление с их помощью цифровой свертки сигналов. Как показано в § 3.2, цифровая реализация интеграла свертки определяется выражением (3.16):

где — отсчеты сигнала; — усеченные по протяженности отсчеты импульсной реакции линейного инвариантного к сдвигу фильтра с усеченной частотной характеристикой.

С помощью замены переменных и перенумерации отсчетов соотношение (3 99) можно переписать в виде

где — значение соответствующее точке в формуле (3.99);

Сравним это выражение с выражением для циклической свертки, получаемой в результате обратного СДПФ произведения циклически сдвинутых оследовательностей (табл. 3.3, строки 12 а, б):

где

Нетрудно видеть, что формула (3.101) сводится к (3.100) цифровой свертки, если заменить в ней

и считать, что продолжено на значения к, меньшие нуля и большие по следующему правилу, вытекающему из (3.102):

Таким образом, при вычислении свертки с помощью дискретных преобразований Фурье имеется та же проблема краевых эффектов, которая была рассмотрена в § 3.5, но здесь способ продолжения сигнала определен выбором параметра обратного СДПФ.

При использовании дискретных преобразований Фурье необходимо учитывать, что наиболее целесообразно вычислять их с помощью алгоритмов быстрого преобразования Фурье БПФ (см. гл. 4). Это налагает определенные ограничения на количество отсчетов сигналов N. Обычно выбирают это число равным целой степени двух, что соответствует наиболее экономичным алгоритмам БПФ. Если фактически имеющееся количество отсчетов не целая степень двух, то сигнал дополняют с учетом закона периодического продолжения (3.105) до ближайшего такого количества отсчетов так, чтобы на краях новой продолженной последовательности не было разрывов сигнала. Хорошие результаты получаются при определении недостающих отсчетов линейной интерполяцией между крайними отсчетами периодически продолженной последовательности. Этот способ дополнения последовательности иллюстрируется на рис. 3.5 для случая простого периодического продолжения (как на рис. 3.3, б), соответствующего стандартному ДПФ.

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

Рис. 3.5.

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

Если количество ненулевых отсчетов импульсной реакции фильтра намного меньше количества отсчетов сигнала, свертку сигнала с этой импульсной реакцией быстрее можно вычислить не для всего сигнала сразу, а по частям, разбивая исходную последовательность сигнала на подпоследовательности. При этом вопрос о доопределении сигнала возникает только для крайних подпоследовательностей — первой и последней. Что касается остальных подпоследовательностей, то их нужно выбирать либо с перекрытием на количество ненулевых отсчетов импульсной реакции фильтра, а при стыковке результатов свертки лишние отсчеты (на половину длины перекрытия с каждой стороны) отбрасывать, либо дополнять последовательности по краям нулями на двойную длину импульсной реакции, а при стыковке результатов свертки складывать перекрывающиеся участки [16].

Когда количество отсчетов импульсной реакции фильтра абсолютно мало или когда искомый фильтр может быть представлен как рекурсивный, использование ДПФ для вычисления свертки может оказаться нецелесообразным из-за низкой скорости вычислений. Точные количественные соотношения, позволяющие выяснить целесообразность использования ДПФ для вычисления свертки, зависят от типа используемого процессора [16].

Все сказанное выше можно отнести и к двумерному случаю, не забывая при этом о двумерном доопределении сигналов.

В заключение отметим, что, как следует из (3.102), СДПФ могут использоваться для получения отсчетов свертки, расположенных в произвольном месте между заданными отсчетами сигналов. Это связано с возможностью интерполяции сигналов с помощью СДПФ, рассмотренной ниже.

Интерполяция сигналов.

Дискретные преобразования Фурье являются удобным средством для нахождения незаданных промежуточных (т. е. расположенных между заданными) отсчетов сигналов по его заданным отсчетам (интерполяции сигналов). Оптимальная интерполяция непрерывных сигналов, для которых справедлива теорема отсчетов, определяется ею:

Для последовательностей конечной длины это соотношение можно аппроксимировать с помощью пары преобразований СДПФ и ОСДПФ. Для СДПФ и ОСДПФ последовательности имеем (табл. 3.3, строка 11а)

Если выбрать

то

Эту формулу можно рассматривать как дискретный аналог (3.106) при При нечетном N следует полагать Если, как обычно, при использовании алгоритмов БПФ N — четное число, следует выбирать т. е. при выполнении обратного преобразования для последовательности длины N последний коэффициент Фурье полагать равным нулю.

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

Интерполяцию последовательностей можно производить также с помощью стандартного ДПФ, симметрично дополняя спектр сигнала нулями до длины, во столько раз превышающей длину исходной последовательности, сколько требуется дополнительных отсчетов на один отсчет исходного сигнала (см. табл. 3.1, строки 18, а, б). Однако использование стандартного ДПФ менее экономично в отношении времени вычислений и затрат памяти, чем СДПФ. Кроме того, полученные с помощью стандартного ДПФ дополнительные отсчеты эквидистантны, тогда как с помощью СДПФ можно в принципе полу чить промежуточные отсчеты с произвольным смещением относительно исходных.

Кроме описанных применений для свертки и интерполяции сигналов, дискретные преобразования Фурье используются для кодирования (см. § 2.11), а также для оценки спектров Фурье и корреляционных функций сигналов и изображений (см. гл. 5).