3.3. Представление алгоритма бпф в виде рекурсивных соотношений
Вернемся к рассмотрению процедуры БПФ. Мы говорили, что на каждой ступени вычисляются группы однородных операций:
- умножение на матрицу D поворачивающих множителей;
- умножение на матрицу ;
- перестановка элементов вектора результатов.
Основная сложность в записи алгоритма БПФ состоит именно в описании перестановок элементов вектора.
Если рассмотреть граф БПФ (например, для N=8, рис3.1), то можно увидеть, что на первой итерации как бы независимо отрабатывается 4 фрагмента исходного вектора, содержащие по 2 элемента: такие фрагменты назовем подвекторами. В данном случае это подвектор X={x0, x4}; X={x1, x5}; X={x2, x6}; X={x3, x7}. На второй итерации отрабатывается 2 подвектора по 4 элемента, а на третий - один вектор из восьми элементов.
Таким образом, суть алгоритма БПФ состоит в разбиении на подвектора по 2 элемента, их независимой обработке, и формированию из промежуточных подвекторов вдвое большей длины (очевидно, что число таких подвекторов уменьшается от итерации к итерации), что выполняется до тех пор, пока не образуется один вектор длиной N элементов.
Подобная процедура может быть описана как [11]:
где l=2m-1, , k=(n)mod l, ,- текущий индекс элемента вектора,k - соответствует номеру Б0 при обработке подвектора, ,- длина подвектора, причём для m=0 вектор. Номер обрабатываемого на данной итерации блока данных определяется целой частью (n)mod l
Выражение (3.9) определяет обработку отдельного, но любого подвектора на каждой итерации из общего их числа . Индексn определяется следующим образом:
,
где - начальный индекс для i-го подвектора.
В свою очередь, (3.9) может быть переписано в виде системы из двух уравнений:
(3.10)
Это выражение соответствует базовой операции, для которой указаны правила формирования текущих индексов по “входным” и “выходным” бабочкам, а также правила вычисления поворачивающего множителя
-
Содержание
- Цифровая обработка сигналов методы предварительной обработки
- Санкт-Петербург
- Содержание
- Введение
- 1. Основные понятия цифровой обработки сигналов
- Понятие о первичной и вторичной обработке сигналов
- Основные требования к системам цос
- Основные типы алгоритмов цифровой обработки сигналов
- 1.4. Линейные и нелинейные преобразования
- 1.5. Переход от непрерывных сигналов к дискретным
- 1.6. Циклическая свертка и корреляция
- 1.7. Апериодическая свертка и корреляция
- 1.8. Двумерная апериодическая свертка и корреляция
- 1.9. Контрольные вопросы и задания.
- 2. Дискретные ортогональные преобразования
- 2.1. Введение в теорию ортогональных преобразований
- 2.2. Интегральное преобразование Фурье
- 2.3. Интегральное преобразование Хартли
- 2.4. Дискретное преобразование Фурье
- 2.5. Дискретное преобразование Хартли
- 2.6. Двумерные дискретные преобразования Фурье и Хартли
- 2.7. Ортогональные преобразования в диадных базисах
- 2.8. Понятие о Wavelet-преобразованиях. Преобразование Хаара
- Задачи цос, решаемые методами дискретных ортогональных преобразований
- 2.9. Контрольные вопросы и задания
- 3. Быстрые алгоритмы ортогональных преобразований
- 3.1. Вычислительная сложность дпф и способы её сокращения
- 3.2. Запись алгоритма бпф в векторно-матричной форме
- 3.3. Представление алгоритма бпф в виде рекурсивных соотношений
- Алгоритмы бпф с прореживанием по времени и по частоте
- 3.6. Вычислительная сложность алгоритмов бпф
- 3.7. Выполнение бпф для случаев
- 3.8. Быстрое преобразование Хартли
- 3.9. Быстрое преобразование Адамара
- 3.10. Контрольные вопросы и задания
- 4. Линейная фильтрация сигналов во временной и частотной областях
- 4.1. Метод накопления
- Не рекурсивные и рекурсивные фильтры
- 4.3. Выбор метода вычисления свертки / корреляции
- 4.4. Выполнение фильтрации в частотной области
- 4.5. Адаптивные фильтры
- 4.6. Оптимальный фильтр Винера
- 4.7. Методы обращения матриц
- 4.8. Контрольные вопросы и задания
- 5. Алгоритмы нелинейной обработки сигналов
- 5.1. Ранговая фильтрация
- 5.2. Взвешенная ранговая фильтрация
- 5.3. Скользящая эквализация гистограмм
- 5.4. Преобразование гистограмм распределения
- 5.5. Контрольные вопросы и задания
- Кафедра вычислительной техники