7.10. Свертка длинных последовательностей

В разд. 7.2.9 показана возможность производить свертку двух периодических последовательностей равной длительности путем перемножения их ДПФ, и вычислением ОДПФ произведения. Операция

точно соответствует обычной свертке

Как правило, наибольший интерес принцип свертки представляет применительно к фильтрации. В этом случае и обрабатываемые данные и импульсная характеристика являются апериодическими последовательностями. Пример такой свертки дает нерекурсивный фильтр с отводами, описанный подробно в разд. 0.2;

Рассмотрим пример, приведенный на фиг. 7.23, чтобы наглядно показать, как на основе формул (7.27) или (7.28) можно корректно выполнить свертку, когда периодические.

Сначала свертываем два периодических колебания прямоугольной формы и получаем корректную периодическую свертку, (фиг. 7.23, а). Затем производим свертку двух прямоугольных апериодических имлульсов, соответствующих одному периоду ко лебания из предыдущего примера (фиг. 7.23, б). Результат свертки совершенно другой. Затягивание, характерное для процесса свертки, приводит к «перекрытию» в случае периодической свертки. Когда требуется вычислить свертку апериодических функций,

(кликните для просмотра скана)

Фиг. 7.23. а — корректная свертка периодических прямоугольных функций; б — корректная свертка апериодических прямоугольных функций; в — влияние увеличения периода на результат периодической свертки.

необходимо принять меры к тому, чтобы избежать перекрытия.

В рассмотренном примере этого можно достигнуть увеличивая период функций (фиг. 7.23, в) и используя ДПФ с большим

Использование ДПФ в формуле (7.27) предполагает, что периодические. Поскольку периодические функции приводят к периодической свертке, дискретные свертки, получаемые с помощью ДПФ, часто называют «круговыми».

При использовании свертки для выполнения фильтрации часто сталкиваются еще с одной трудностью. Фильтруемые последовательности обычно много длиннее относительно короткой импульсной характеристики, в результате чего для вычислений требуется чрезвычайно большая память . В этом случае можно производить свертку на основе ДПФ путем соответствующего секционирования длинных последовательностей.

Пусть дана -точечная импульсная характеристика (фиг. 7.24, а). Она свертывается с длинной последовательностью данных (фиг. 7.24, б). Чтобы получить свертку, - выделим отсчетов из образуя «кадр», который может быть использован в качестве входного массива -точечного ДПФ (фиг. 7.24, в). По причине, которая станет понятной ниже, наложим на ограничение

(кликните для просмотра скана)

Поскольку используется ДПФ, кадр необходимо рассматривать как один период периодической функции показанной на фиг. Далее также с помощью ДПФ вычислим преобразование -точечной последовательности, образованной дополнением нулями -точечной импульсной характеристики. Этим достигается периодическое продолжение , т. е. получена функция , которая свертывается с умножением в частотной области:

где

и

Применив

Если сюда подставить два выражения, определяющие и применить свойство ортогональности (разд. 7.2.5), то можно получить

Сравнение этого уравнения с соотношением (7.29), которое описывает нерекурсивный фильтр, показывает, что они похожи, но вместе с тем не идентичны. Учитывая, что положено большим, чем рассмотрим случай, когда

Здесь

так что вторая сумма исчезает, и

Это абсолютно точное выражение, определяющее выходной отсчет фильтра с отводами. Члены по той же «причине корректны.

Рассмотрим теперь первые выходных отсчетов. Все они содержат ложные члены, вызванные наложением и определяемые второй суммой в формуле (7.30). Из-за этого они не корректны и должны быть отброшены. Иллюстрацией к вышеизложенному служит фиг. 7.24,

Следующий этап включает выделение второго -точечного кадра, выбираемого так, что его первые значений идентичны последним отсчетам предыдущего кадра (фиг. 7.24, з). Это необходимо в силу того, что в начале следующей -точечной свертки снова будет ложных отсчетов, которые должны быть отброшены.

Корректную часть первой свертки мы возвращаем в память (фиг. 7.24, и). Поскольку по крайней мере отсчетов, взятых из больше не будут использоваться, отфильтрованные данные, полученные в результате первой свертки, могут быть помещены в те же ячейки памяти, которые содержали первый обработанный кадр. Таким образом, весь процесс фильтрации может быть выполнен с «замещением», и в этом случае потребности в памяти определяются необходимостью хранения лишь первоначальных данных. Потребуется также относительно небольшой объем «обязательной» памяти для проведения самой свертки и преобразований (этот объем определяется детальной схемой вычислений).

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

Описанный способ известен как метод «перекрытия с накоплением» [8], и вполне понятно, почему он так называется. Метод «перекрытия со сложением позволяет достигнуть тех же результатов несколько по-другому. В деталях он отличается от первого метода, «но основной принцип здесь тот же, так же как и необходимые время вычислений и объем памяти.

Если много больше длительности импульсной характеристики которую будем считать фиксированной (определяемой требуемым числом отводов фильтра), то свертку можно вычислять сразу большими массивами. Следовательно, для фильтрации

Таблица 7.1

последовательности заданной длины потребуется относительно небольшое число таких сверток. С другой стороны, если мало и ненамного превосходит потребуются короткие быстрые свертки, ко и процесс фильтрации намного удлинится. Поэтому были рассчитаны [8] оптимальные значения для заданных (табл. 7.1).

Фиг. 7.25. Программа для выполнения свертки по методу перекрытия с накоплением действительных данных, записанных в памяти в виде массива X длиной «LEN». (см. скан)

На фиг. 7.25 приведен текст подпрограммы которая выполняет свертку по методу перекрытия с накоплением. Подпрограмма считывает входной массив X заданной длины и свертывает его с заданной импульсной характеристикой длиной

Длина ненулевой части импульсной характеристики должна выбираться в соответствии с данными табл. Импульсная характеристика и входные данные являются действительными последовательностями, так что подпрограмма обеспечивает эффективный метод обработки большого числа встречаемых на практике функций, подвергаемых цифровой фильтрации.

Теперь можно сравнить быстродействие выполнения свертки по методу накопления с перекрытием или по методу накопления со сложением с выполнением свертки во временной области на основе формулы (7.29). Предположим, что необходимо выполнить свертку длинной последовательности из М действительных отсчетов с действительной импульсной характеристикой длиной При этом

При использовании формулы (7.29) необходимо выполнить действительных умножений. Если применяется метод преобразований, то. согласно фиг. 7.24, при каждом преобразовании и взвешивании обрабатываются отсчетов, а всего преобразований и взвешиваний должно быть для того чтобы получить свертку всех М отсчетов. Поскольку все преобразования являются -точечными над действительными данными и на каждом шаге нужно выполнить два преобразования и одно -точечное взвешивание действительных чисел, то общее число действительных умножений для выполнения свертки в частотной области равно

Из табл. 7.1 видно, что при малых значениях выполняется соотношение Следовательно, при использовании метода преобразований можно приблизительно найти число действительных умножений по формуле

а при работе во временной области — по формуле

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

Более того, с увеличением N выигрыш в быстродействии возрастает. Например, если N=4096, метод преобразований примерно в 30 раз «быстрее» прямого метода.