2020-05-11
400
ДПФ является эффективным инструментом спектрального анализа дискретных сигналов. Коэффициенты ДПФ представляют собой отсчеты спектра дискретного сигнала на частотах, кратных частоте дискретизации, деленной на число отсчетов. При выполнении условий теоремы отсчетов (Уиттекера — Котельникова — Шеннона), т. е. при отсутствии наложения спектров, эти коэффициенты являются отсчетами спектра исходного аналогового сигнала.
Алгоритмы цифрового спектрального анализа являются базовыми при решении таких задач, как реализация ЦФ в частотной области, согласованная фильтрация, обработка изображений и т. п. Поэтому на ранней стадии развития теории цифровой обработки сигналов столь большое внимание уделялось разработке эффективных в вычислительном отношении алгоритмов ДПФ.
Непосредственно вычисление ДПФ в соответствии с базовым соотношением
требует выполнения N комплексных умножений и N – 1 комплексных сложений для каждого коэффициента X (k). общее число вычислений составляет N 2 комплексных умножений и N (N – 1) ≈ N 2 комплексных сложений. реализация такого объема вычислений при обработке больших массивов сигналов в реальном времени сопряжена с определенными трудностями.
|
|
|
Поиски более эффективных путей решения этой задачи привели к созданию быстрых алгоритмов, под которыми понимают описание вычислительной процедуры, которое не является очевидным способомвычисления в соответствии с прямой записью алгоритма.
Р. блейхут отмечал, что «как правило, быстрый алгоритм жертвует концептуальной ясностью вычислений в пользу их эффективности» [3]. он же иллюстрирует это положение на следующем простом примере. пусть требуется произвести вычисления по формуле
A = ac + ad + bc + bd.
Для их реализации требуется 4 умножения и 3 сложения. однако тот же результат можно получить, проведя вычисления, преобразовав формулу к виду:
A = (a + b)(c + d),
и затратить на это только одно умножение и два сложения.
Таким образом, быстрые алгоритмы можно представить себе как «хитроумную расстановку скобок в вычислениях». Однако для сложных задач быстрые алгоритмы не удается получить простым просмотром вычислений, их построение базируется на теории чисел.
Быстрое преобразование Фурье (БПФ) основывается на возможности представления размерности массива сигналов N в виде произведения сомножителей ri и выполнении ДПФ для более коротких последовательностей, число членов в которых определяется соответствующими сомножителями. коэффициенты ДПФ исходной «длинной» последовательности получаются путем комбинации коэффициентов ДПФ коротких последовательностей. сомножители ri называются при этом «основанием» БПФ. оказывается, что, если
|
|
|
N = r 1 r 2, …, rp, (1.48)
то X (k) могут быть найдены интерактивно путем расчета суммы р слагаемых следующего типа:
— дискретных преобразований Фурье размерности r 1, общим количеством N / r 1 (по r 12 комплексных умножений в каждом);
— дискретных преобразований Фурье размерности r 2, общим количеством N / r 2 (по r 22 комплексных умножений в каждом);
— дискретных преобразований Фурье размерности rp, общим количеством N / rp (по rp 2 комплексных умножений в каждом).
Таким образом, общее число операций комплексного умножения составит:
Коэффициент ускорения вычислений (КУВ) при этом составляет:
БПФ с основанием 2. В частности, если N = 2 p, то ∑ ri = 2log2 N
Дополнительное увеличение скорости вычислений происходит за счет того факта, что при r = 2
и соответствующие умножения заменяются на сложения.
В этом случае длина последовательности N = 2 p. Методика получения быстрого алгоритма для последовательности такой длины позволяет наглядно продемонстрировать, как и за счет чего получается сокращение вычислительных операций, однако не дает общих правил получения быстрых алгоритмов для последовательностей произвольной длины.
Алгоритмы БПФ с основанием 2 разделяются на две группы.
Если при реализации алгоритма требуется перестановкаотсчетов входной последовательности x (n), то его называют алгоритмом с прореживанием по времени. Если при реализации алгоритма осуществляется перестановка отсчетов выходной последовательности, т.е. коэффициентов ДПФ X (k), то его называют алгоритмом с прореживанием по частоте.
По требуемому количеству комплексных умножений и сложений эти две разновидности алгоритмов БПФ эквивалентны.
Алгоритм БПФ с прореживанием по времени получается следующим образом. Разобьем входную последовательность x (n) на две части — с четными и нечетными номерами:
x чт(n) = x (2 n); (1.51)
x нч(n) = x (2 n + 1), n = 0, 1,..., N/2 – 1.
Процедура этого разбиения для вычисления восьмиточечного БПФ приведена на рис. 1.6.
Рис. 1.6. процедура разбиения входной последовательности (а – в) для восьмиточечного ДПФ
Тогда ДПФ исходной последовательности, определенное как
можно разбить на две части следующим образом:
где n в первом слагаемом четные, а во втором нечетные.
Или:
Учтем, что
Тогда
Таким образом, первая половина коэффициентов ДПФ исходной последовательности вычисляется через коэффициенты ДПФ двух последовательностей половинной длины, полученных из исходной путем прореживания.
Вторую половину коэффициентов можно получить, учтя, что X чт(k) и X нч(k) — периодические функции с периодом N/2:
Окончательно
Соотношения (1.54) и (1.55) являются основой алгоритма БПФ с прореживанием по времени и поэтому носят название базовой операции.
Ее удобно представлять направленным графом (рис. 1.7, а). По его виду базовую операцию БПФ с основанием 2 называют «бабочкой». Для сокращенного обозначения умножение на 1 опускают и договариваются всегда в правом верхнем углу записывать сумму, а в нижнем — разность. Стрелки означают умножение на число, записанное над ней (рис. 1.7, б).
Таким образом, коэффициенты восьмиточечного ДПФ вычисляются через коэффициенты двух четырехточечных ДПФ (рис. 1.8).
| X |
| чт |
| ( |
| k |
| ) |
| X |
| чт |
| ( |
| k |
| ) |
| X |
| нч |
| ( |
| k |
| ) |
| X |
| нч |
| ( |
| k |
| ) |
| X |
| ( |
| k |
| ) |
| X |
| ( |
| k |
| ) |
| W |
| N |
| –k |
| W |
| N |
| –k |
| –W |
| N |
| –k |
| X |
| ( |
| k + |
| 2 |
| N |
| ) |
| X |
| ( |
| k + |
| 2 |
| N |
| ) |
а б
|
|
|
Рис. 1.7. графическое представление базовой операции БПФ с прореживанием по времени: а — полное; б — сокращенное
Рис. 1.8. вычисление коэффициентов восьмиточечного ДПФ через коэффициенты четырехточечных ДПФ
Дальнейшие вычисления строят по итерационному принципу: последовательности отсчетов с четными и нечетными номерами вновь разбивают на две части и продолжают процесс до тех пор, пока не получится последовательность из двух элементов. Так, N /2 - точечные ДПФ могут быть представлены как комбинации двух N/4 - точечных ДПФ:
Зздесь A (k) и B (k) — коэффициенты N/4 -точечного ДПФ последовательностей, составленных из четных и нечетных членов последовательности x чт(n).
Двухточечное ДПФ последовательности f (0), f (1) может быть рассчитано без умножений:
В качестве примера на рис. 1.9 приведен полученный таким образом граф восьмиточечного БПФ.
Рис. 1.9. граф алгоритма восьмиточечного БПФ с прореживанием по времени
Отметим некоторые характерные свойства этого алгоритма:
1. При его реализации на каждом этапе входная (временная) последовательность разделяется на две последовательности половинной длины, т. е. происходит прореживание, откуда и следует название алгоритма.
2. Число этапов равно log2 N.
3. Базовая операция каждого этапа — «бабочка» ДПФ:
X = A + W Nk B (первая половина коэффициентов ДПФ); Y = A – W Nk B (вторая половина коэффициентов ДПФ).
4. Для каждой базовой операции требуется только одно комплексное умножение для вычисления произведения W N–k B. базовая операция позволяет толковать алгоритм БПФ как комбинацию ДПФ коротких последовательностей с умножением на поворачивающиеся множители (множители поворота) 
5. Всего на каждом этапе выполняется N/2 комплексных умножений.
6. Общее число комплексных умножений составляет N/2log2 N (в это число входят и тривиальные умножения на ± 1, ±j). Число нетривиальных комплексных умножений еще меньше. Так, в восьмиточечном БПФ только 2 нетривиальных умножения (на W 8–1 и W 8–3).
|
|
|
Коэффициент ускорения вычислений составляет:
Алгоритм БПФ с прореживанием по частоте получают, разбивая исходную последовательность x (n), n = 0, N- 1 на две последовательности по N/2 отсчетов следующим образом:
Тогда ДПФ исходной последовательности можно представить как
Учитывая, что
Получим, что четные и нечетные коэффициенты ДПФ вычисляются соответственно как
Таким образом, четные и нечетные коэффициенты ДПФ исходной последовательности являются коэффициентами ДПФ двух вспомогательных последовательностей половинной длины f (n) и g (n), образованных из первой и второй половины исходной последовательности следующим образом:
Нетрудно видеть, что соотношения (1.59) также описывают базовую операцию — «бабочку», граф которой приведен на рис. 1.10.
| W |
| N |
| –n |
Рис. 1.10. базовая операция БПФ с прореживанием по частоте
Соотношения (1.58) и (1.59) также позволяют толковать алгоритм БПФ как сочетание умножения на множители поворота ДПФ над последовательностями половинной длины. только в алгоритме с прореживанием по частоте умножение на множители поворота W N–n предшествует выполнению короткого БПФ.
Переходя далее от N/2 -точечных ДПФ к N/4 -точечным и т. д., приходим к двухточечному ДПФ, которое вычисляется без комплексных умножений.
Проиллюстрируем построение алгоритма БПФ с прореживанием по частоте на примере последовательности из 8 отсчетов. На первом этапе представим восьмиточечные ДПФ через четырехточечные ДПФ (рис. 1.11).
Рис. 1.11. схема вычислений восьмиточечного БПФ с прореживанием по частоте
Каждое четырехточечное ДПФ, в свою очередь, может быть представлено через комбинацию: получение вспомогательных последовательностей половинной длины — умножение на множители поворота — двухточечное ДПФ.
Отметим, что коэффициенты БПФ будут формироваться в перестановленном порядке, т. е. «прорежены» по частоте. Количество комплексных умножений и сложений для этого алгоритма такое же, как и для алгоритма с прореживанием по времени.
Глава 7. Основы теории Z -преобразования
В анализе и синтезе дискретных и цифровых систем Z -преобразование играет такую же роль, как преобразование лапласа для непрерывных систем. Это объясняется следующими причинами:
Ø свойства дискретных последовательностей можно изучать, исследуя их Z -преобразования (обычными методами математического анализа);
Ø при Z -преобразовании разностные уравнения, описывающие линейные дискретные фильтры, преобразуются в алгебраические, таким образом, Z -преобразование является удобным аппаратом для решения разностных уравнений;
Ø свойства линейных дискретных фильтров полностью описываются расположением нулей и полюсов системной функции на комплексной z -плоскости.
Прямым одностронним Z -преобразованием дискретной последовательности x (n)(конечной или бесконечной) называют ряд по степеням комплексной переменной z = α + j β:
Множество значений z, где ряд сходится, называется областью сходимости. X ̃ (z) - аналитическая функция, не имеющая особых точек. Для равномерной сходимости достаточно, чтобы
где M и a 0 — положительные вещественные числа.
Область сходимости определяется кругом радиуса R в z -плоскости, внекоторого ряд сходится.
Примеры Z -преобразований тестовых дискретных последовательностей:
1. единичный импульс (дискретная дельта-функция):
2. единичный скачок (функция включения):
Область сходимости: | z | > 1.
3. Экспоненциальная последовательность:
При | az –1| < 1 этот ряд представляет собой бесконечно убывающую геометрическую прогрессию, сумма членов которой равна:
Таким образом, область сходимости | z | > | a | лежит вне окружности радиуса a на комплексной z -плоскости (рис. 1.14).
Рис. 1.14. область сходимости
Обратное Z -преобразование ставит в соответствие функции комплексной переменной X ̃ (z)решетчатую функцию (дискретную последовательность) x (n), определяемую следующим образом:
где с — замкнутый контур в z -плоскости, охватывающий все особые точки (полюсы) функции X ̃ (z); интегрирование по контуру c производится в направлении против часовой стрелки.
Обратное Z -преобразование удобно вычислять при помощи теоремы о вычетах: функция x (n) равна сумме вычетов подынтегральной функции (1.77) в полюсах, расположенных внутри контура интегрирования.
Если подынтегральная функция в (1.77) может быть представлена в виде
где zi — полюс подынтегральной функции; mi — кратность полюса; k — количество полюсов, то
Причем
В частном случае, если X ̃ (z) — рациональная функция, имеющая простые полюса, то ее можно разложить на простые дроби:
Тогда обратное Z -преобразование:
Другой часто применяемый способ вычисления обратного Z -преобразования — использование таблиц соответствия нескольких базовых пар преобразований (табл. 1.1) и их комбинации на основе использования основных свойств Z -преобразования.
Таблица 1.1 базовые пары преобразований
Основные свойства Z -преобразования:
1. Линейность.
Если y (n) = a 1 x 1(n) + a 2 x 2(n), где a 1 и a 2 — постоянные коэффициенты, не зависящие от n, то:
2. Сдвиг последовательности.
Если y (n) = x (n – m) U (n – m), то
Z-преобразование задержанной на m отсчетов дискретной последовательности равно произведению Z -преобразования незадержанной последовательности на множитель z–m,называемый оператором запаздывания. в частности, задержке на один период дискретизации соответствует умножение на z –1. Поэтому оператор z –1применяют для обозначения цифрового элемента задержки на такт в структурных схемах устройств цифровой обработки сигналов.
3. Умножение на экспоненту:
4. Умножение на n:
5. Свертка последовательностей
Если причем
6. Перемножение последовательностей. если y (n) = x 1(n) x 2(n), то
Здесь контур интегрирования с лежит внутри пересекающихся областей сходимости X ̃ 1(ν) и X ̃ 1(z /ν). Соотношение (1.88) называется комплексной сверткой.
Из этого соотношения можно получить выражение для спектральной плотности произведения двух дискретных последовательностей. поскольку при z = e j Ω и ν = e j Θ соответствующие Z- преобразования X 1 (e j Ω) и X 2 (e j Θ) представляют собой ДВПФ, то из (1.88) следует:
Т. е. ДВПФ произведения последовательностей x 1(n)и x 2(n)есть свертка ДВПФ сомножителей. Эта свертка является периодической (циклической) в силу того, что X 1(j Ω)и X 2(j Ω) являются периодическими функциями частоты, поскольку представляют собой спектры дискретных последовательностей.
В заключение установим взаимосвязь между ДПФ и Z -преобразованием. Рассмотрим периодическую последовательность xn (n) = xn (n + mN). Эта последовательность не может быть представлена через Z -преобразование, так как ряд (1.72) расходится.
Представление ее через дискретный ряд Фурье описывается коэффициентами ДПФ:
Z -преобразование непериодической конечной последовательности x (n), образованной из одного периода xп (n), равно:
Поскольку в пределах периода повторения из N отсчетов x (n) =xп (n), то мы приходим к равенству:
Уравнению соответствуют точки, равномерно расположенные на окружности единичного радиуса в комплексной z -плоскости (рис. 1.15, б). поэтому можно говорить, что спектральная плотность сигнала — это сечение его z -образа по единичной окружности (рис. 1.15, а).
Соотношения между непрерывными и дискретными сигналами и их преобразованиями обобщены в схеме, представленной на рис.1.16.
| X |
| ̃ |
| z |
| ( |
| z |
| ) |
| X |
| ( |
| e |
| j |
| ω |
| T |
| д |
| ) |
| X |
| ( |
| k |
| ) |
| Im |
| Z |
| Im |
| Z |
| Re |
| Z |
| 1 |
| Re |
| Z |
| –j |
| –j |
| – |
| 1 |
| – |
| 1 |
| 2 |
| k |
| N |
| π |
а б
рис. 1.15. спектральная плотность сигнала и его Z -преобразование
| аналоговый |
| сигнал |
| x |
| ( |
| t |
| ) |
| дискретный |
| сигнал |
| x |
| д |
| ( |
| n |
| ) |
| = |
| x |
| ( |
| nT |
| д |
| ) |
| Модель |
| Мип |
| x |
| и |
| ( |
| t |
| ) |
| ×δ( |
| t |
| – |
| nT |
| д |
| ) |
| t |
| = |
| nT |
| д |
| двпФ |
| ( |
| для сигнала |
| с ограничен- |
| ным спект- |
| ром) |
| нпФ |
| нпФ |
| Z- |
| преобра- |
| зование |
| двпФ |
| дпФ |
| для перио- |
| дического |
| сигнала |
| X |
| ( |
| j |
| ω) |
| z = |
| W |
| k |
| X |
| и |
| ( |
| j |
| ω) |
| X |
| ( |
| k |
| ) |
| X |
| ( |
| z |
| ) |
| 2 |
| k |
| T |
| π |
| ω= |
| 1 |
| д |
| T |
| × |
| ( |
| для сигнала |
| с ограничен- |
| ным спектром) |
| z = |
| e |
| ( |
| j |
| ω |
| T |
| д |
| ) |
рис. 1.16. соотношение между непрерывными и дискретными сигналами и их преобразованиями.
