WikiDer > Метод перекрытия – добавления

Overlap–add method

В обработка сигналов, то перекрытие – добавить метод является эффективным способом оценки дискретных свертка очень длинного сигнала с конечная импульсная характеристика (FIR) фильтр :

Рис. 1: Последовательность из 5 графиков изображает один цикл алгоритма свертки с перекрытием и сложением. Первый график представляет собой длинную последовательность данных, которые необходимо обработать с помощью FIR-фильтра нижних частот. Второй график - это один сегмент данных, который нужно обработать кусочно. Третий график - это отфильтрованный сегмент, включая переходные процессы нарастания и спада фильтра. Четвертый график указывает, куда будут добавлены новые данные с результатами предыдущих сегментов. Пятый график - это обновленный выходной поток. КИХ-фильтр представляет собой коробчатый фильтр нижних частот с M = 16 отсчетов, длина сегментов L = 100 отсчетов и перекрытие 15 отсчетов.

 

 

 

 

(Уравнение 1)

куда час[м] = 0 за м за пределами региона [1, M].

Идея состоит в том, чтобы разделить проблему на несколько сверток час[п] с короткими сегментами :

куда L - произвольная длина отрезка. Потом:

и у[п] можно записать как сумму коротких сверток:[1]

где линейная свертка равен нулю за пределами региона [1, L + M − 1]. И для любого параметра [A] это эквивалентно Nточка круговая свертка из с в регион [1, N]. Преимущество заключается в том, что круговая свертка может быть вычислена более эффективно, чем линейная свертка, согласно теорема круговой свертки:

 

 

 

 

(Уравнение 2)

куда:

  • DFTN и IDFTN обратитесь к Дискретное преобразование Фурье и его обратное, оцениваемое по N дискретные точки и
  • L обычно выбирается так, что N = L + M-1 является целочисленной степенью двойки, а преобразования реализованы с помощью БПФ алгоритм, для эффективности.

Псевдокод

Ниже приводится псевдокод алгоритма:

(Алгоритм сложения с перекрытием для линейной свертки)h = FIR_impulse_response M = длина (h) Nx = длина (x) N = 8 × M (см. следующий раздел для лучшего выбора)step_size = N - (M-1) H = DFT (h, N) позиция = 0y (1: Nx + M-1) = 0пока позиция + размер_шага ≤ Nx делать    y (position + (1: N)) = y (position + (1: N)) + IDFT (DFT (x (position + (1: step_size)), N) × H) position = position + step_sizeконец

Соображения эффективности

Рис. 2. График значений N (целая степень двойки), которые минимизируют функцию стоимости.

Когда DFT и IDFT реализуются алгоритмом FFT, псевдокод выше требует около N (журнал2(N) + 1) комплексные умножения для БПФ, произведения массивов и ОБПФ.[B] Каждая итерация производит N-M + 1 выходных выборок, поэтому количество сложных умножений на выходную выборку составляет около:

 

 

 

 

(Уравнение 3)

Например, когда M= 201 и N=1024, Уравнение 3 равно 13,67, тогда как прямая оценка Уравнение 1 потребует до 201 комплексных умножений на выходную выборку, в худшем случае, когда оба Икс и час комплекснозначны. Также обратите внимание, что для любого данного M, Уравнение 3 имеет минимум относительно N. Рисунок 2 представляет собой график значений N, которые минимизируют Уравнение 3 для диапазона длин фильтров (M).

Вместо того Уравнение 1, мы также можем рассмотреть возможность применения Уравнение 2 к длинной последовательности длины образцы. Общее количество сложных умножений будет:

Для сравнения, количество сложных умножений, требуемых алгоритмом псевдокода, составляет:

Следовательно Стоимость метода перекрытия – сложения масштабируется почти как в то время как стоимость одной большой круговой свертки почти . Эти два метода также сравниваются на рисунке 3, созданном с помощью моделирования в Matlab. Контуры представляют собой линии постоянного отношения времени, необходимого для выполнения обоих методов. Когда метод сложения с перекрытием работает быстрее, отношение превышает 1, и видны отношения до 3.

Рис. 3. Преимущество метода сложения с перекрытием по сравнению с одной большой круговой сверткой. По осям показаны значения длины сигнала NИкс и длина фильтра Nчас.

Смотрите также

Примечания

  1. ^ Из этого условия следует, что сегмент имеет как минимум M-1 добавленный ноль, что предотвращает циклическое перекрытие переходных процессов нарастания и спада выходного сигнала.
  2. ^ Алгоритм Кули – Тьюки БПФ для N = 2k требуется (N / 2) журнал2(N) - см. БПФ - определение и скорость

Рекомендации

  1. ^ Rabiner, Lawrence R .; Золото, Бернард (1975). «2,25». Теория и применение цифровой обработки сигналов. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр.63–65. ISBN 0-13-914101-4.

дальнейшее чтение

  • Оппенгейм, Алан В .; Шафер, Рональд В. (1975). Цифровая обработка сигналов. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 0-13-214635-5.
  • Хейс, М. Гораций (1999). Цифровая обработка сигналов. Обзорная серия Шаума. Нью-Йорк: Макгроу Хилл. ISBN 0-07-027389-8.

внешняя ссылка