КИО-фильтр

Входной поток данных

Задержка

Выходной - потоп данных

а) Функциональная схема

КИО-фильтр

Входной поток данных

Выходной поток данных

6) Схет оеолизации Рис. 9.1. Конструкция КИО-фильтра.

Основанная на методе перекрытия с накоплением конструкция КИО-фильтра показана на рис. 9.1. Функциональная схема такого фильтра похожа на линию задержки с отводами, но истинная конструкция может быть существенно другой. Поступающие входные слова подаются в циклическую буферную память, которая в типичных случаях вдвое больше секции фильтра. Во время фильтрации данных из одной части буфера, во вторую его часть записываются данные следующей секции, подготавливая блок данных для следующего шага вычислений. Текущая секция данных перекрывается с новой секцией. Фильтрация блока данных длины п занимает то же время, что и запись нового блока из n - Лточек.

Входной буфер является циклическим. Это означает, что после того, как его последний элемент заполнен, следующие входные символы записываются, начиная с первого элемента памяти. Та- \ КИМ образом, старые данные уничтожаются, а на их место записы-ваются новые данные. Обычно удобно длину входного буфера выбирать равной степени двух. Записанное в двоичном регистре число -указывает адрес, по которому запоминается следующий вход, и после каждого входа содержимое регистра увеличивается на еди-ницу. Свойство цикличности буфера очень легко обеспечить тем,

что предусмотреть возможность переполнения адресного регистра после достижения состояния, в котором во всех его разрядах записаны единицы.

Секционный фильтр отыскивает в памяти блок данных, адреса

которых равны ((b)).....((Ь + п - 1)), где 6 - начальный адрес

и двойные скобки обозначают вычисление по модулю, равному длине буфера памяти. После обработки секции данных Ъ заменяется на ((6 + Л)) и начинается фильтрация следующей секции.

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

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

Снова предположим, что у нас есть устройство вычисления линейной свертки, выходная длина которой равна п. Пусть нам надо умножить многочлену (х), степень А которого меньше п, на многочлен d (х), степень В которого больше п. Величина В опять столь велика, что можно полагать ее равной бесконечности. По многочлену d (х) построим последовательность многочленов степени не более п - А - 1, определяя их равенствами

di = dl,

dr = di + , A

( = 0, ...-, n - A - \,

i = 0.....n-A-l,

i = 0.....n-A-l.

Отметим, что так построенные многочлены не перекрываются. Тогда многочлен d (х) может быть записан в виде

d (х) = S d<l (х) х1-1) -*>

а} Перекрытые с накоплением Входной поток данных

I Секция

п входных

отсчетов

п-тоиеиная циклаческай свертка

п входных отсчетов

Отбросить

Отбросать

Сдублировать

Выходной поток данных

б) Перекрытие с суммироват Входной поток данных

Секция

tn-A) входных -отсчетов

п-точечно линейная семитка

а выходных отсчетов

Выходной поток данных

Рис. 9.2. Свертка по секциям.

S (X) = g (X) d (X) = S g (X) dm (X) л--ч (-).

Для каждого / положим

sii (X) = g (X) d(i (X). Тогда коэффициента многочлена s (х) даются равенствами Si = si , i = О.....п - А - 1,

St+2 (п-Л) = sP> + Sil ( Д,

= о.....п-А~\,

О,..., п - Л - 1,

и так далее. Этим исчерпываются все вычисления метода перекрытия с суммированием.

Метод перекрытия с суммированием основывается на алгоритме вычисления линейной свертки. Однако, поскольку deg g (х) = Л и deg d (х) = n - Л - 1, то при желании можно воспользоваться и циклической сверткой. Циклическая свертка длины я на самом деле будет линейной сверткой; все выходные точки циклической свертки будут давать правильные значения коэффициентов линейной свертки.

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

Например, в разд. 3.4 были рассмотрены алгоритмы итеративного построения линейных сверток большой длины из линейных сверток малой длины. В частности, для построения 256-точечной Линейной свертки была использована итерация 2-точечной линейной свертки. Эта же задача может быть решена методом перекрытия с суммированием. Параметры алгоритма: л = 511 выходных точек; А = 255, что соответствует фильтру с 256 отводами; п - - Л = 256 входных точек. Каждая составляющая свертка дает пакет из 256 выходных точек, для вычисления которых в данной конструкции требуется 6561 умножений и 19171 сложений, считая дополнительные сложения алгоритма перекрытия с суммированием. Таким образом, реализация вычислений на КИО-фильтре с 256 отводами требует 25,6 умножений на одну точку на выходе.

d. d, d, d, d, d, d. d, d.

d.-i \i. ,

Это уравнение описывает вычисление п компонент на выходе КИО-фильтра с г отводами. Такое вычисление будем называть (г, п)-фильтр-секцией, или, при г = ,я-фильтр-секцией. Эта задача представляет собой задачу вычисления усеченной свертки. Как будет доказано ниже, (г, /г)-фильтр-секция требует г п - 1 умножений, и поэтому алгоритм с г + rt - 1 умножениями называется оптимальным. Этот термин, однако, может ввести в заблуждение, поскольку алгоритмы подобного сорта могут содержать слишком много сложении, если г к tine малы. Мы будем пользоваться оптимальными алгоритмами только при малых значениях г и я.

Алгоритм секционной фильтрации можно получить из алгоритма вычисления линейной свертки. Основой преобразования алгоритма для одной из этих задач в алгоритм для другой задачи является следующий общий принцип.

Теорема 9.2.1 (Трансформационный принцип). Пусть задан алгоритм

S = Id = CGAd,

где матрица О является диагональной, а матрицы А и С содержат только малые константы. Тогда

е = A-QCf

является алгоритмом вычисления tTt. Если исходный алгоритм вычисления вектора s оптимален, то второй алгоритм дает оптимальный алгоритм вычисления вектора е.

Доказательство. Алгоритм представляет собой факторизацию матрицы в виде

Т = CGA.

Так как матрица G является диагональной, то Т = AGC и, следовательно,

ТЧ = A-GC-f.

Вторая часть утверждения следует отсюда очевидным образом, так как если существует алгоритм с наименьшим числом умножений для вычисления вектора е, то его трансформация дает алгоритм с тем же числом умножений для вычисления вектора s. □

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

Согласно теореме 9.2.1 теперь можно записать

8. 8, о

о 8. 8,

I I о

р 1 i

1-1 0

о 1 о о -I

Для построения алгоритма 2фильтр-секции заменим теперь (е , ei) на (s Sj) и (/ , /i, h) на (dj, dj, d ):

P 8.

1 1 01

lo 1 I

l -1 0 0 1 0 0-1 1

9.2. Алгоритмы для коротких секций фильтра

Цифровые КИО-фильтры можно строить, используя описанные в предыдущем разделе методы перекрытия. Для применения этих методов нужны хорошие алгоритмы для отдельных секций фильтра. Сейчас мы дадим хорошие алгоритмы для коротких секций фильтра, а в разд. 9.3 опишем способы их сочетания для построения длинных секций фильтра.

Метод перекрытия с накоплением можно записать в матричном виде. Опуская отбрасываемые выходные компоненты, получаем следующее матричное уравнение: