6.17. Алгоритм z-преобразования с использованием ЛЧМ-фильтрации

Алгоритм z-преобразования с ЛЧМ-фильтрацией является эффективным алгоритмом вычисления z-преобрааования конечной последовательности вдоль определенного контура на z-плоскости. Поскольку и единичная окружность является одним из возможных контуров, этот алгоритм может быть также использован для эффективного вычисления ДПФ последовательности, хотя в этом случае эффективность не будет столь же высокой, как для алгоритма БПФ. В то же время многие ограничения, характерные для БПФ, в том числе требование, чтобы число отсчетов последовательности N раскладывалось на множители, при использовании алгоритма z-преобразования с ЛЧМ-фильтрацией устраняются. Таким образом, этот алгоритм можно использовать для эффективного вычисления ДПФ последовательности и при простых N. Пусть заданная -точечная последовательность , имеет z-преобразование

ДПФ заданной последовательности по определению равно

Испольвуя алгоритм z-преобразования с ЛЧМ-фильтрацией, можно найти z-преобразование в соответствии с формулой (6.58) вдоль контура более общего вида:

Здесь М — произвольное целое число (не обязательно равное N), а А и W — произвольные комплексные числа, равные

(6.62)

На фиг. 6.26 изображен контур в z-плоскости, удовлетворяющий формуле (6.60), и графически представлены величины .

Фиг. 6.26. Контур расчета z-преобразования с ЛЧМ-фильтрацией

Как следует из фиг. 6.26 и формул (6.60)-(6.62), при имеем , т. е. точки вдоль контура будут соответствовать положениям спектральных отсчетов при вычислении -точечного ДПФ последовательности.

Постоянная определяет скорость ухода контура внутрь окружности радиуса или наружу от нее. При контур будет скручиваться, а при — раскручиваться. Несколько проще интерпретировать скручивание контура в z-плоскости, рассматривая эквивалентный контур в s-плоскости. Действительно, введя подстановку , получим или . Далее, поскольку , то . На фиг. 6.27 в -плоскости изображен контур, эквивалентный контуру, показанному на фиг. 6.26. Таким образом, спиралеобразные контуры в z-плоскости соответствуют прямым линиям в s-плоскости, причем скорость закручивания определяет угол наклона прямой в s-плоскости.

Покажем теперь, как эффективно рассчитывать z-преобразование последовательности, согласно формуле (6.58), вдоль контура (6.60). Обозначив через искомые значения z-преобразования при , т. е.

Фиг. 6.27. Контур расчета z-преобразования с ЛЧМ-фильтрацией

и, учитывая формулу (6.60), находим

Подстановка в формулу (6.64) выражения

дает

или

где

Из формулы (6.67) видно, что значения можно найти, рассчитав взвешенную сверку последовательностей последнее можно эффективно провести, используя алгоритм быстрой свертки на основе БПФ. На фиг 6.28 приведены все основные операции алгоритма z-преобразования с ЛЧМ-фильтрацией.

Фиг. 6.28. Операции при выполнении z-преобразования с ЛЧМ-фильтрацией.

Прежде чем перейти к детальному описанию алгоритма z-преобразования с ЛЧМ-фильтрацией, полезно перечислить преимущества зтого алгоритма по сравнению со стандартным алгоритмом БПФ:

1. N, число отсчетов входной последовательности, не обязательно должно быть равно М, числу точек, в которых рассчитывается преобразование.

2. Ни N, ни М могут не быть составными числами; фактически оба они могут быть простыми.

3. Угловое смещение точек может быть произвольным, так и частотное разрешение может быть любым.

4. Контур не обязательно должен быть окружностью в z-плоскости. В гл. 12 будет показано, что использование спиралевидного контура в анализаторе речи дает некоторые преимущества.

5. Начальная точка контура в -плоскости произвольна. Это свойство особенно полезно при анализе в узкой полосе частот, когда высокое частотное разрешение (п.3) сочетается с произвольной начальной частотой.

6. При -преобразование с ЛЧМ-фильтрацией можно использовать для вычисления ДПФ даже при простых N.

Все операции алгоритма z-преобразования с ЛЧМ-фильтрацией выполняются в несколько следующих этапов, иллюстрируемых с помощью ряда простых графиков на фиг. 6.29:

1. Выбор L, наименьшего целого числа, большего или равного , которое можно было бы использовать в обычном алгоритме БПФ. Величипа L определяет размер преобразований, которые выполняются при расчете быстрой свертки в системе, показанной на фиг. 6.28.

2. Формирование L-точечной последовательности вида

Типичные последовательности изображены на фиг. 6.29, а и б.

(см. скан)

Фиг. 6.29. Последовательность выполнения алгоритма z-преобразования с ЛЧМ-фильтрацией.

3. Расчет L-точечного ДПФ последовательности с помощью обычного алгоритма БПФ; результаты расчета обозначаются через . На фиг. 6.29, в изображена типичная последовательность .

4. Формирование L-точечной последовательности по формуле

На фиг. 6.29, гид изображены последовательности и .

5. Расчет L-точечного ДПФ последовательности , результаты которого обозначаются через (фиг. 6.29, е).

6. Почленное умножение последовательностей и что дает (фиг. 6.29, ж).

7. Расчет обратного ДПФ последовательности , результаты которого обозначаются через (фиг. 6.29, а).

8. Умножение на , что дает , т. е.

Значения при М не имеют смысла и отбрасываются. Последовательность изображена на фиг. 6.29, и.

Остается показать, что алгоритм z-преобразования с ЛЧМ-фильтрацией эффективнее прямого вычисления z-преобразования заданной последовательности. Для этого достаточно подсчитать число комплексных умножений, используемых при выполнении z-преобразования с ЛЧМ-фильтрацией. Подсчет дает следующие результаты:

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

Действительно, если ввести

то с учетом выражений (6.70) — (6.72) получим рекуррентные соотношения

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

2. Для L-точечного БПФ на этапе 3 требуется порядка комплексных умножений.

3. Последовательность обычно заранее записывается в память, хотя может и генерироваться рекуррентно [аналогично (6.70)], для чего потребуется 2М комплексных умножений.

4. При L-точечном ДПФ (этап 5) для вычисления опять требуется порядка комплексных умножений (впрочем, если z-преобразование с ЛЧМ-фильтрацией выполняется неоднократно с одними и теми же значениями , эта последовательность может быть вычислена только один раз и затем храниться в памяти).

5. Для перемножения последовательностей и (этап 6), необходимо L комплексных умножений.

6. В L-точечном БПФ для получения опять требуется порядка комплексных умножений.

7. Чтобы получить М отсчетов на выходе системы, требуется М комплексных умножений.

Из вышеизложенного видно, что основными операциями при вычислении -преобразования с ЛЧМ-фильтрацией являются три (или иногда два) -точечных БПФ, поэтому снова время вычисления будет пропорционально (напомним, что ), но только коэффициент пропорциональности будет в два-три раза больше, чем при БПФ. Таким образом, z-преобразование с ЛЧМ-фильтрацией оказывается эффективным алгоритмом расчета z-преобразования последовательности вдоль контура определенной формы в z-плоскости. Применения этого алгоритма рассмотрены Рабинером, Шафером и Рэйдером. (Недавно из частного сообщения Харпера Уайтсайда стало известно, что этот алгоритм был также использован для выполнения ДПФ в системе, построенной на базе акустической линии задержки с поверхностной волной.)