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

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

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

{ displaystyle y [n] = x [n] * час [n] треугольник q сумма _ {m = - infty} ^ { infty} h [m] cdot x [nm] = sum _ {m = 1} ^ {M} h [m] cdot x [нм],}

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

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

Идея состоит в том, чтобы вычислить короткие сегменты у[п] произвольной длины L, и соедините сегменты вместе. Рассмотрим сегмент, который начинается в п = kL + M, для любого целого числа k, и определим:

{ Displaystyle х_ {к} [п] треугольник { begin {case} х [п + kL], & 1 leq n leq L + M-1 0, & { textrm {иначе}}. end {case}}}

{ Displaystyle y_ {k} [n] треугольникq x_ {k} [n] * h [n] = sum _ {m = 1} ^ {M} h [m] cdot x_ {k} [ нм].}

Тогда для kL + M ≤ п ≤ kL + L + M - 1, и эквивалентно M ≤ п − kL ≤ L + M − 1, мы можем написать:

{ displaystyle y [n] = sum _ {m = 1} ^ {M} h [m] cdot x_ {k} [n-kL-m] triangleq y_ {k} [n- kL].}

С заменой $j ≜ n-kL$ , задача сводится к вычислению $у k (j)$ , за M ≤ $j$ ≤ L + M − 1. Эти шаги проиллюстрированы на первых трех графиках рисунка 1, за исключением того, что желаемая часть выходных данных (третья кривая) соответствует 1 ≤ $j$ ≤ L.^[B]

Если периодически продлевать Икс_k[п] с точкой N ≥ L + M - 1, по данным:

{ Displaystyle х_ {к, N} [п] треугольник сумма _ { ell = - infty} ^ { infty} x_ {k} [n- ell N],}

извилины ${ Displaystyle (х_ {к, N}) * ч ,}$ и ${ Displaystyle х_ {к} * ч ,}$ эквивалентны в регионе M ≤ п ≤ L + M - 1. Поэтому достаточно вычислить Nточка круговая (или циклическая) свертка из ${ Displaystyle х_ {к} [п] ,}$ с ${ Displaystyle ч [п] ,}$ в районе [1,N]. Субрегион [M, L + M - 1] добавляется к выходному потоку, а остальные значения отброшен. Преимущество заключается в том, что круговая свертка может быть вычислена более эффективно, чем линейная свертка, согласно теорема круговой свертки:

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

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

где:

DFT_N и IDFT_N обратитесь к Дискретное преобразование Фурье и его обратное, оцениваемое по N дискретные точки и
$L$ обычно выбирается так, что $N = L + M-1$ является целочисленной степенью двойки, а преобразования реализованы с помощью БПФ алгоритм, для эффективности.
Эффекты переднего и заднего края круговой свертки перекрываются и добавляются,^[C] и впоследствии отброшены.^[D]

Псевдокод

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

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

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

{ displaystyle { tfrac {N left ( log _ {2} N + 1 right)} {N-M + 1}}}

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

{ Displaystyle { гидроразрыва {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 O left (N_ {x} log _ {2} N right)}$ в то время как стоимость одной большой круговой свертки почти ${ displaystyle O left (N_ {x} log _ {2} N_ {x} right)}$ .

Перекрытие – сбросить

Перекрытие – сбросить^[1] и Нахлест – лом^[2] реже используются метки для того же метода, описанного здесь. Однако эти ярлыки на самом деле лучше (чем перекрытие – сохранить) отличить от перекрытие – добавить, потому что обе методы "сохранить", но отбрасывает только один. «Сохранить» просто означает, что M - 1 входной (или выходной) отсчет из сегмента k необходимы для обработки сегмента k + 1.

Расширение перекрытия - сохранение

Алгоритм сохранения с перекрытием можно расширить, включив в него другие общие операции системы:^[F]^[3]

дополнительные каналы IFFT могут обрабатываться дешевле, чем первый, за счет повторного использования прямого FFT
частоту дискретизации можно изменять, используя прямое и обратное БПФ разного размера
преобразование частоты (микширование) может быть выполнено путем перегруппировки частотных элементов

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

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

Примечания

^ Рабинер и Голд, Рис 2.35, четвертый след.
^ Перенос нежелательных граничных эффектов на последние выходы M-1 является потенциальным удобством во время выполнения, потому что IDFT может быть вычислен в ${ Displaystyle у [п]}$ буфер, вместо того, чтобы вычисляться и копироваться. Затем краевые эффекты могут быть перезаписаны следующей IDFT. Следующая сноска объясняет, как выполняется сдвиг, путем сдвига во времени импульсной характеристики.
^ Не путать с Метод перекрытия-добавления, который сохраняет отдельные эффекты передней и задней кромки.
^ Краевые эффекты можно переместить с передней части на заднюю часть выхода IDFT, заменив ${ displaystyle scriptstyle { text {DFT}} _ {N} displaystyle (h [n])}$ с ${ displaystyle scriptstyle { text {DFT}} _ {N} displaystyle (h [n + M-1]) = scriptstyle { text {DFT}} _ {N} displaystyle (h [n + М-1-Н]),}$ означает, что буфер длиной N с круговым смещением (повернутые) образцами М-1. Таким образом, элемент h (M) находится в n = 1. Элемент h (M-1) находится в n = N. h (M-2) находится при n = N-1. И т.п.
^ Алгоритм Кули – Тьюки БПФ для N = 2^k требуется (N / 2) журнал₂(N) - см. БПФ - определение и скорость
^ Карлин и др. 1999 г., стр 31, столбец 20.