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

Overlap–save method

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

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

 

 

 

 

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

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

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

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

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

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

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

 

 

 

 

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

где:

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

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

 

 

 

 

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

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

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

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

Следовательно Стоимость метода сохранения перекрытия масштабируется почти как в то время как стоимость одной большой круговой свертки почти .

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

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

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

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

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

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

Примечания

  1. ^ Рабинер и Голд, Рис 2.35, четвертый след.
  2. ^ Перенос нежелательных граничных эффектов на последние выходы M-1 является потенциальным удобством во время выполнения, потому что IDFT может быть вычислен в буфер, вместо того, чтобы вычисляться и копироваться. Затем краевые эффекты могут быть перезаписаны следующей IDFT. Следующая сноска объясняет, как выполняется сдвиг, путем сдвига во времени импульсной характеристики.
  3. ^ Не путать с Метод перекрытия-добавления, который сохраняет отдельные эффекты передней и задней кромки.
  4. ^ Краевые эффекты можно переместить с передней части на заднюю часть выхода IDFT, заменив с означает, что буфер длиной N с круговым смещением (повернутые) образцами М-1. Таким образом, элемент h (M) находится в n = 1. Элемент h (M-1) находится в n = N. h (M-2) находится при n = N-1. И т.п.
  5. ^ Алгоритм Кули – Тьюки БПФ для N = 2k требуется (N / 2) журнал2(N) - см. БПФ - определение и скорость
  6. ^ Карлин и др. 1999 г., стр 31, столбец 20.

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

  1. ^ Харрис, Ф.Дж. (1987). Д. Ф. Эллиот (ред.). Справочник по цифровой обработке сигналов. Сан-Диего: Academic Press. С. 633–699. ISBN 0122370759.
  2. ^ Фрекинг, Марвин (1994). Цифровая обработка сигналов в системах связи. Нью-Йорк: Ван Ностранд Рейнхольд. ISBN 0442016166.
  3. ^ Боргердинг, Марк (2006). «Превращение сохранения с перекрытием в многополосное микширование, банк фильтров с понижающей дискретизацией» (PDF). Журнал IEEE Signal Processing Magazine (Март 2006 г.): 158–161.
  1. Rabiner, Lawrence R .; Золото, Бернард (1975). «2,25». Теория и применение цифровой обработки сигналов. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр.63–67. ISBN 0-13-914101-4.
  2. Патент США 6898235, Карлин, Джо; Терри Коллинз и Питер Хейс и др., "Устройство перехвата широкополосной связи и пеленгации с использованием гиперканализации", опубликовано 10 декабря 1999 г., опубликовано 24 мая 2005 г. , url2 =https://worldwide.espacenet.com/patent/search/family/034590049/publication/US6898235B1?q=pn%3DUS6898235