5.3. Направленные сигнальные графы и реализация с помощью переменных состояния

В этом разделе мы кратко рассмотрим направленные сигнальные графы для двумерных БИХ-фильтров. Двумерные направленные сигнальные графы, как и их одномерные аналоги, служат для изображения в виде диаграмм тех преобразований, которые испытывают двумерные сигналы в процессе их прохождения через двумерные фильтры. В разд. 4.2.6 мы уже обсуждали направленные графы и их связь с -преобразованием. Сначала мы кратко рассмотрим типичные элементы, используемые в направленных сигнальных графах, и их практическую реализацию. Затем установим связь направленных сигнальных графов с реализациями двумерных БИХ-фильтров с помощью переменных состояния.

5.3.1. Элементы сигнальных графов и их реализация

Рассмотрим передаточную функцию простого двумерного БИХ-фильтра, описываемую выражением

.                      (5.59)

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

Рис. 5.11. Блок-схема, соответствующая передаточной функции .

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

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

Рассмотрим представленный на рис. 5.12 направленный сигнальный граф, описывающий полином-числитель

.                       (5.60)

На нем имеется цепочка из двух направленных вниз операторов  слева и один направленный вверх оператор  справа. Узлы, расположенные на этих вертикальных путях, соединены ветвями с соответствующим усилением. Если мы обозначим узлы в обеих цепочках  и  номерами 0, 1, 2 и т. д. (сверху вниз), то -й узел в цепочке  будет связан с -м узлом в цепочке  ветвью с коэффициентом усиления .

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

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

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

Рис. 5.13. Направленный сигнальный граф, описывающий полином .

Направленный граф так же, как входная и выходная маски, не указывает в явной форме порядок изменения индексов сигнала , равно как и диапазон значений  и . К сожалению, конкретный выбор соотношения упорядочивания (разд. 4.1.4) влияет на способ реализации операторов  и  [5]. Например, пусть мы движемся по индексам строка за строкой, и длина каждой строки равна  отсчетов. Тогда упорядоченная пара  принимает значения , как показано на рис. 5.14. В этом случае оператор  может быть реализован просто в виде регистра сдвига единичной емкости, выдающего значение  при занесении в него нового значения . Однако в конце каждой строки в регистр  необходимо заносить начальное значение для следующей строки так, чтобы значением отсчета «предшествующего»  было исходное значение , а не фактическое предыдущее значение .

Рис. 5.14. Сканирование отсчетов строка за строкой (в каждой строке  отсчетов.)

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

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

Мы рассматривали направленный граф как аналог схемного решения, показывающий, какие элементы следует соединить друг с другом. Однако может оказаться плодотворной другая интерпретация направленного графа, в частности как схемы алгоритма вычисления требуемых значений отсчетов. Вернемся, например, к направленному графу для , показанному на рис. 5.12, и напишем выражение для вычисления значения отсчета в каждом узле. Пусть  обозначает входной сигнал, а  - выходной. Сигналы узлов в цепочке  обозначим через ,  и  для узлов 0, 1 и 2 соответственно (сверху вниз). Аналогично сигналы узлов в цепочке  обозначим через  и . Тогда можно записать:

,                                                                          (5.61а)

,                                                                          (5.61б)

,                                                                                 (5.61в)

,                          (5.61г)

,                         (5.61д)

.                                                                                 (5.61e)

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

В качестве примера рассмотрим программную реализацию формул (5.61) для случая, когда выходные отсчеты поступают строка за строкой, как на рис. 5.14, и требуется получить значения выходного сигнала в области . На рис. 5.15 представлен с использованием обобщенного языка высокого уровня вариант программной реализации фильтрации (в некоторой условной форме). Задержимся некоторое время на рис. 5.15. Рассмотрев детально последовательность команд, можно видеть, что порядок формул (5.61а), (5.61е) выбран с целью предотвращения введения дополнительных рабочих ячеек для хранения значений отсчетов в процессе модификации сигналов узлов. Ввиду того что входной сигнал поступает строка за строкой, для представления каждого из сигналов узлов в цепочке  (,  и ) требуется только одна ячейка памяти. Однако для реализации оператора сдвига  требуется  ячеек; поэтому для хранения значений отсчетов, которые потребуются при вычислении выходных отсчетов следующей строки, используется массив . Начальные значения массива  являются горизонтальными начальными значениями, обычно это нули. В начале каждой строки переменные  и  также обнуляются. Это соответствует упоминавшемуся выше сбросу в исходное состояние операторов сдвига .

Рис. 5.15. Возможная программная реализация уравнений (5.61).

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

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