Рис. 9.3. Характеристики некоторых алгоритмов коротких фильтр-секций. Щ 94 Характеристики некоторых реальных алгоритмов КИО-фильтров,

При желании этот алгоритм после переупорядочивания можно переписать в виде

Для 2-фильтр-секцин этот алгоритм оптимален; он содержит три 1 умножения и четыре сложения, не считая суммирования g + gi, связывающего отводы фильтра.

Так же можно построить и другие алгоритмы коротких секций j фильтра. Характеристики некоторых из таких алгоритмов приве- дены на рис. 9.3.

9.3. Итерирование секций фильтра

Итерируя алгоритмы для коротких секций фильтров, можно получать алгоритмы для секций фильтра большей длины, на вы- ходе которых формируются длинные блоки отсчетов. Характери-! стики таких итерированных секций фильтра затабулированы на рис. 9.4. Используя описанный в разд. 9.1 метод перекрытия с натЗ коплением, можно строить каскады произвольного числа этияГ секций фильтра, на выходе которых будет формироваться беско нечный поток данных.

В рассмотренных нами малых алгоритмах свертки не нсполь зевалось свойство коммутативности умножения чисел поля. ЛЮ- бой алгоритм линейной свертки,

Si = Е gi-A,

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

S, = S G, J) .

где теперь D, представляет собой i-ю матрицу в списке из матриц, а Gi представляет собой i-ю матрицу в списке из L матриц. Построенные нами ранее алгоритмы свертки применимы в данном случае так же, как и ранее. Сложение превращается в сложение матриц, а умножение становится умножением матриц.

Построим итерацию 2-фильтр-секций для формирования секций фильтра большей длины. Малый алгоритм возьмем в виде

Алгоритм содержит 1,5 умножений на каждый отсчет на выходе фильтра. Его можно использовать повторно для вычисления двух отсчетов на выходе одновременно, и такое вычисление всегда будет содержать 1,5 умножений и 2 сложения на один отсчет на выходе. 2-фильтр-секция, однако, не имеет существенного значения для практических приложений, а используется для итеративного построения алгоритмов больших фильтров с 2 отводами, на выходе которых вычисляются одновременно 2 отсчетов дискретного сигнала.

Для иллюстрации идеи рассмотрим построение алгоритма вычисления четырех точек на выходе секции фильтра с четырьмя

Разбивая это вычисление на блоки размерности два на два получаем

</, d,

d, d

\d> d-d,

\d, d,\ id, dJ

Теперь эта задача имеет точно такой же вид, как и предыдущая задача. Скалярные величины заменились матрицами, но алгоритм является системой тождеств и остается справедливым и в данном случае. Имеем

(1), - о4

Как и ранее, сумма G + Gj должна быть вычислена заранее и не влияет на оценку числа необходимых в алгоритме операций. Алгоритм содержит четыре матричных сложения и три матричных умножения. Остановимся сначала на сложениях матриц Два из них имеют вид

d, - d, d, d.

d, - d, d, - d,

d, - d, rf, - d, Л ~ d. d, - d,

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

Каждое из матричных умножений имеет тот же вид, что и 2-фильтр-секция, и, следовательно, может быть вычислено с помощью трех умножений и четырех сложений. Таким образом, алгоритм 4-фильтр-секции всего содержит девять умножений и 21 сложение.

Если алгоритм 4-фильтр-секции используется повторно для одновременного вычисления четырех отсчетов на выходе каждый раз, то одно из сложений пропадает, так как d, - d, в одном пакете равно dj - dj в следующем пакете.

Процесс итерации носит вполне общий характер. Если п четно, то матрица алгоритма п-фильтр-секции разбивается на четыре ((п/2) X (п/2))-блока. Используя теперь алгоритм 2. фильтр-секции, построим алгоритм п-фильтр-секции в виде трехкратного обращения к алгоритму (п/2)-фильтр-секции. При этом число дополнительных сложений, необходимых для вычисления матрицы Dl - D , равно п - 1, а число дополнительных сложений, необходимых для вычисления матрицы Dj - Dj, равно п/2. Это происходит потому, что все рассматриваемые матрицы являются теплицевыми ((п/2) X (п/2))-матрицами. Для вычисления матрицы Dl- Do надо выполнить вычитания только в первой строке и левом столбце. Некоторые из полученных при этом величин повторяются в матрице Dg - Di, так что для вычисления последней требуется только п/2 вычитаний. Если алгоритм используется в режиме повторения, то некоторые из ранее вычисленных величин повторяются, так что для вычисления каждой нз матриц Dl - D и Dj - Dj в каждом новом пакете требуется только п/2 сложений. Еще и дополнительных сложений требуется в выходном векторе. Подводя итог, получаем, что если алгоритм (п/2)-фильтр-секции содержит М умноженийг и А сложений, то построенный описанным образом алгоритм п-фильтр-секции будет содержать ЪМ умножений и 2п + 3.4 сложений.

Если п = 2 , то эта процедура может быть проитерирована; алгоритм 2 -фильтр-секции строится из алгоритмов г--фильтр-секции, которые, в свою очередь, строятся из алгоритмов 2 --фильтр-секции и т. д. Число умножений в таком алгоритме равно 3 = n , а число сложений описывается рекурсией А (п) = = 2п + ЗЛ (п/2) при Л (1) = 0.

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

отводами (4-фильтр-секции). В матричном виде это вычисление записывается равенством

QUCAO Число

умножений вложений

Алгоритм # i

Прямое исполыоВоние 16-точвчной фильтрации

Алгоритм # 2

Прямое использование 8 точек 8-тоиечной соильтрации

Алгоритм # J

\ъ-кратнь1й вызов 8-Фильтр~секцйй\

&точея\-нратный Вызов -фильтр-сенции\

точки Алгоритм #

Прямое использование А-точечной фильтрации

\з-нратный вызов в-фильтр-се>гчии\

8 точек \з-кратный вызов 4-Фильтр-сенции\

it точно\3-кратный вызов 2-ФОЛьтр-сеиции

[Прямое использование 2-точечной фильтрации

Алгоритм # S

\3-кратный вызов 8~азильтр-ееяции\

8точек \3-кратный вызов фильтр-секцйй\

тонкиХЗ-кратный вызов 2-фильтр-сеггци/

Прямое использование 2-точечной филыпрации

Рис. 9.5. Некоторые алгоритмы 16-точечных КИО-фильтров.

Если я достаточно велико, то рассматриваемый алгоритм с умножениями становится хуже алгоритма, основанного на БПФ и содержащего О (я log я) умножений. Значение я,для которого это происходит, можно сдвинуть, если итеративный алгоритм по основанию два заменить итеративным алгоритмом по основанию четыре, содержащим в своей начальной форме семь умножений. Тогда число умножений растет как 7 = я-*°.

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

Алгоритм 1. Выходы фильтра вычисляются стандартным способом. Алгоритм содержит 16х 16 = 256 умножений и 16х 15 = . = 240 сложений.

Алгоритм 2. Алгоритм 2-фильтр-секции, в котором для вычисления выходов трех секций с 8 отводами используется любой подходящий алгоритм и 4x8 дополнительных сложений. Если выходы трех фильтров с 8 отводами вычисляются стандартным способом, то каждый из них требует 8x8 = 64 умножений и 8x7 = 56 сложений. В общей сложности получаем алгоритм с 3x64 = 192 умножениями и 32 4- 3x56 = 200 сложениями.

Алгоритм 3. Алгоритм 2-фильтр-секции используется для сведения к трем 8-фильтр-секциям, каждая из которых реализуется в виде 4x4 = 16 сложений и трехкратного использования 4-фильтр-секций. Если каждая 4-фильтр-секция реализуется стандартным алгоритмом фильтрации, содержащим 16 умножений и 12 сложений, то такой алгоритм 16-фильтр-секции в общей сложности содержит 32 -- Зх 16 -f 9х 12 = 188 сложений и 9Х 16 = = 144 умножения.

Алгоритм 4 получается из алгоритма 3 модификацией алгоритмов для 4-фильтр-секций, в которой они заменены 4X2 = 8 дополнительными сложениями и трехкратным использованием алгоритма 2-фильтр-секции. Таким образом, этот алгоритм 16-фильтр-секции содержит 32 4-3x16-1-9x8 = 152 сложения и 27-KpaiHoe вычисление 2-фильтр-секции. Стандартный алгоритм 2-фильтр-секции содержит два умножения и четыре сложения, так что в общей сложности получаем 152 -f 27x2 = 206 сложений и 27x4 = 108, умножений.

Алгоритм 5 получается итеративным использованием 2-фильтр-секции на всех этапах; такой алгоритм содержит 260 сложений и 81 умножение.

Нельзя сказать, какой из этих алгоритмов предпочтительнее других. Только детальный анализ алгоритма в контексте его применения может сказать, что, например, алгоритм с 206 сложениями и 108 умножениями предпочтительнее, чем алгоритм с 260 сложениями и 81 умножениями. Все что мы можем сделать, это предложить конструктору различные альтернативы.

9.4. Симметрические

и кососимметрические фильтры

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