5.3.2. Минимизация числа операторов сдвига

Вернемся к исходной задаче настоящего раздела - получению детализированного направленного сигнального графа передаточной функции , определяемой выражением (5.59). Это можно сделать достаточно просто, объединив графы, показанные на рис. 5.12 и 5.13, в соответствии со схемой на рис. 5.11. Результат такого объединения представлен на рис. 5.16. Этот направленный граф можно упростить. Учитывая, что оператор сдвига дистрибутивен относительно сложения, можно объединить два оператора  в один (рис. 5.17). При этом уменьшается число требуемых операторов сдвига и, следовательно, сокращается объем требуемой памяти.

Рис. 5.16. Детализированный направленный сигнальный граф передаточной функции .

Рис. 5.17. Улучшенный направленный сигнальный граф функции .

Можно предложить и другие направленные сигнальные графы, позволяющие получить требуемую передаточную характеристику . Например, можно изменить порядок следования фильтра  и цепи обратной связи, содержащей функцию , в результате получится блок-схема, приведенная на рис. 5.18. Если затем подставить в эту блок-схему, как и ранее, графы из рис. 5.12 и 5.13, то две цепочки операторов  будут содержать одни и те же данные, и их можно совместить. В результате получается направленный сигнальный граф, представленный на рис. 5.19. Этот граф содержит всего четыре оператора сдвига, и в нем число операторов  минимально.

Рис. 5.18. Возможная блок-схема функции .

Рис. 5.19. Детализированный направленный сигнальный граф функции  с минимизацией числа операторов сдвига .

Другой направленный сигнальный граф с минимальным числом операторов  можно получить из рис. 5.19, применяя теорему о двумерном транспонировании и строя транспонированную схему. Теорема о двумерном транспонировании, как и ее одномерный аналог [1], утверждает, что транспонированная схема, которая получается изменением направления всех стрелок в направленном сигнальном графе, будет иметь ту же передаточную функцию, что и исходная схема. Если изменить направление всех стрелок на рис. 5.19 и перестроить граф так, чтобы входной порт был слева, а выходной - справа, то получится направленный граф, показанный на рис. 5.20. Такой транспонированный граф может иметь преимущества при использовании машинного слова ограниченной длины, так как ослабление благодаря «нулям» функции  происходит здесь перед усилением благодаря «полюсам», что до некоторой степени уменьшает вероятность арифметического переполнения в промежуточных вычислительных операциях.

Рис. 5.20. Другой направленный сигнальный граф, представляющий функцию .

Граф получен транспонированием графа на рис. 5.19.

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

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

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