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

В этой статье используются общие абстрактные обозначения, такие как ${extstyle y (t) = x (t) * h (t),}$ или ${extstyle y (t) = {mathcal {H}} {x (t)},}$ в котором понимается, что функции следует рассматривать в их совокупности, а не в определенные моменты ${extstyle t.}$ (видеть Свертка # Обозначение)

В обработка сигналов, то перекрытие – добавить метод является эффективным способом оценки дискретных свертка очень длинного сигнала ${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_час.

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

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

Примечания

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

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

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

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