Метод перекрытия – добавления - Overlap–add method

В обработка сигналов, то перекрытие – добавить метод является эффективным способом оценки дискретных свертка очень длинного сигнала ${displaystyle x [n]}$ с конечная импульсная характеристика (FIR) фильтр ${displaystyle h [n]}$ :

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

{displaystyle y [n] = x [n] * h [n] riangleq sum _ {m = -infty} ^ {infty} h [m] cdot x [nm] = sum _ {m = 1} ^ {M} h [m] cdot x [нм],}

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

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

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

{displaystyle x_ {k} [n] riangleq {egin {case} x [n + kL], & n = 1,2, ldots, L 0, & {ext {else}}, end {case}}}

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

{displaystyle x [n] = сумма _ {k} x_ {k} [n-kL] ,,}

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

{displaystyle {egin {выровнено} y [n] = left (sum _ {k} x_ {k} [n-kL] ight) * h [n] & = sum _ {k} left (x_ {k} [n -kL] * h [n] ight) & = sum _ {k} y_ {k} [n-kL], конец {выровнен}}}

где линейная свертка ${displaystyle y_ {k} [n] riangleq x_ {k} [n] * h [n],}$ равен нулю за пределами региона [1, L + M − 1]. И для любого параметра ${displaystyle Ngeq L + M-1 ,,}$ ^[A] это эквивалентно Nточка круговая свертка из ${displaystyle x_ {k} [n],}$ с ${displaystyle h [n],}$ в регион [1, N]. Преимущество заключается в том, что круговая свертка может быть вычислена более эффективно, чем линейная свертка, согласно теорема круговой свертки:

{displaystyle y_ {k} [n] = scriptstyle {ext {IDFT}} _ {N} displaystyle (scriptstyle {ext {DFT}} _ {N} displaystyle (x_ {k} [n])) cdot scriptstyle {ext {DFT }} _ {N} displaystyle (h [n])),}

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

куда:

DFT_N и IDFT_N обратитесь к Дискретное преобразование Фурье и его обратное, оцениваемое по 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 (целая степень двойки), которые минимизируют функцию стоимости.

{displaystyle {frac {Nleft (log _ {2} N + 1ight)} {N-M + 1}}}

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

{displaystyle {frac {N (log _ {2} (N) +1)} {N-M + 1}}.,}

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

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

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

{displaystyle N_ {x} cdot (log _ {2} (N_ {x}) + 1).}

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

{displaystyle N_ {x} cdot (log _ {2} (N) +1) cdot {frac {N} {N-M + 1}}.}

Следовательно Стоимость метода перекрытия – сложения масштабируется почти как ${displaystyle Oleft (N_ {x} log _ {2} Night)}$ в то время как стоимость одной большой круговой свертки почти ${displaystyle Oleft (N_ {x} log _ {2} N_ {x} ight)}$ . Эти два метода также сравниваются на рисунке 3, созданном с помощью моделирования в Matlab. Контуры представляют собой линии постоянного отношения времени, необходимого для выполнения обоих методов. Когда метод сложения с перекрытием работает быстрее, отношение превышает 1, и видны отношения до 3.

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

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

Метод перекрытия – сохранения

Примечания

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

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

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

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

[2] Из этого условия следует, что ${displaystyle x_ {k}}$ сегмент имеет как минимум M-1 добавленный ноль, что предотвращает циклическое перекрытие переходных процессов нарастания и спада выходного сигнала.

[3] Алгоритм Кули – Тьюки БПФ для N = 2^k требуется (N / 2) журнал₂(N) - см. БПФ - определение и скорость

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

[1]

[A]

[B]