4.2.6. Двумерные направленные графы

Ранее в этой главе мы ввели входную и выходную маски для объяснения способа выполнения рекурсивного вычисления выходных отсчетов разностного уравнения. Маски полезны при определении того, является ли разностное уравнение рекурсивно вычислимым, какие начальные условия требуются для рекурсии и какие способы частичного упорядочивания обеспечивают рекурсивную вычислимость. Направленный граф является другим способом графического описания двумерных ЛИС-систем. Направленный граф можно вывести из -преобразования; он особенно полезен для описания схемной реализации. Если, например, -преобразование поддается разложению на множители, то этот факт отчетливо отражается на направленном графе. Более того, поскольку направленный граф является графом, над ним можно производить операции, изменяющие описание ЛИС-систем. Направленный граф полезен для анализов сложности системы, чувствительности системы к изменениям значений коэффициентов, влияния ошибок арифметического округления на выход системы. Ни способ входной и выходной масок, ни способ направленного графа не обеспечивают полного описания системы, поскольку ни один из них не определяет метода упорядочивания при реализации системы. Однако оба способа полезны для понимания многомерных рекурсивных систем.

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

Рис. 4.20. Типы ветвей, используемых в двумерном направленном графе.

а – оператор усиления; б – сдвиг вправо (горизонтальная задержка); в – сдвиг влево; г – сдвиг вверх (вертикальная задержка); д – сдвиг вниз.

Простейшей ветвью является оператор усиления. Величина на выходе ветви есть просто величина на входе, умноженная на коэффициент усиления ветви. Остальные четыре типа ветвей являются операторами сдвига. Если на входе имеется отсчет , то на выходе будет отсчет , ,  или  в зависимости от типа ветви. Это можно рассматривать как усиление в -области, причем коэффициентами усиления являются , ,  и  соответственно, как это показано на рис. 4.20. Чэн [5] рассмотрел применение более общих ветвей сдвига, которые можно получить из описанных посредством линейных преобразований. Это часто может оказаться полезным в тех случаях, когда выходные отсчеты вычисляются не в порядке «строка за строкой» или «столбец за столбцом», а в ином порядке.

Пример 1

В качестве простого примера рассмотрим передаточную функцию

,                                                             (4.64)

которая соответствует разностному уравнению

.                     (4.65)

Это уравнение можно представить направленным графом, показанным на рис. 4.21.

Рис. 4.21. Представление системы, приведенной в примере 1, в виде направленного графа.

Пример 2

В качестве более сложного примера рассмотрим фильтр с передаточной функцией

,                                         (4.66)

которая соответствует разностному уравнению

,           .    (4.67)

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

Рис. 4.22. Представление системы, приведенной в примере 2, в виде направленного графа.

В случае одномерных физически реализуемых фильтров направленный граф можно непосредственно использовать для их практической реализации, поскольку оператор сдвига можно рассматривать как выборку из отдельной ячейки памяти. Однако в двумерном случае реализовать оператор сдвига гораздо сложнее. Рассмотрим направленный граф, представленный на рис. 4.22. Например, если выбран порядок вычислений столбец за столбцом, выходные значения будут вычисляться в порядке , , . Следовательно, оператор сдвига  можно реализовать в виде выборки из одного слова памяти. Однако оператор сдвига  требует промежуточного запоминания значений сигналов объемом в целый столбец, поскольку выходом ветви  является величина , если на ее входе задана величина . Направленный граф из-за своей простоты оставляет неясным способ реализации горизонтальных и вертикальных операторов сдвига, и по этой причине его применение ограниченно.