[an error occurred while processing this directive] [an error occurred while processing this directive]

[ <<< | 1 | 2 | 3 | >>> ]

3. Изоморфное построение функциональной схемы непосредственно по графу переходов

При использовании предлагаемого метода применяется граф переходов автомата Мура, вершины которого кодируются многозначно [8]. Этот граф переходов непосредственно и изоморфно реализуется одной из стандартных схем, рассмотренных ниже, которые строятся из традиционных логических элементов, логических (Л) и цифровых (Ц) мультиплексоров, а также преобразователей "десятичный код - двоичный код" (Д/В).

Логический мультиплексор имеет m логических управляющих входов, 2^m цифровых информационных входов и один цифровой выход, а цифровой мультиплексор - один цифровой управляющий и S цифровых информационных входов (S - число вершин в графе переходов (число состояний в автомате)), а также один цифровой выход.

На логические входы этих элементов подаются константы 0 и 1, а на цифровые - константы 0,1,2,...,S-1. При этом на цифровых выходах также формируются константы 0,1,2,...,S-1.

Обратим внимание на отличие этих элементов от элементов, традиционно называемых мультиплексорами, все входы и выходы которых являются логическими (двоичными) [11].

Предлагается использовать три варианта стандартных схем, первый из которых предполагает наличие логических мультиплексоров при m_i = 1, второй - при m_i = n_i, а третий - при m_i=k_i , где n_i - число переменных в булевых формулах, помечающих дуги, исходящие из i-й вершины графа переходов; k_i - число дуг, исходящих из i-й вершины.

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

Оценим число элементов в такой схеме. Если число различных входных переменных в пометках дуг графа переходов равно N, то число инверторов в схеме не превысит N. Если общее число букв во всех булевых формулах на дугах (за исключением петель) графа переходов равно H, то число логических элементов, реализующих эти формулы, не превышает H - L, где L - число дуг (без учета петель) в графе переходов. Это объясняется тем, что для реализации i-й (i = 1,...,L) формулы из h_i букв требуется не более h_i - 1 двухвходовых элементов без учета инверсий, реализуемых в первом слое схемы. Так как каждый переход (дуга) в графе переходов реализуется одним логическим мультиплексором, то их общее число равно L. Так как в схему входят два цифровых мультиплексора и один преобразователь, общее число элементов в ней определяется соотношением:

Э₁ Ј N + (H - L) + L + 3 = N + H + 3.

Использование изложенного подхода позволяет реализовать граф переходов (рис.3) функциональной схемой (рис.4) из 11 элементов (Э₁ Ј 3 + 6 + 3 = 12).

Рис. 3

Рис. 4 (в натуральную величину)

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

Вторая разновидность стандартных схем отличается от первой тем, что комбинационная схема из традиционных логических элементов не строится, а j-ый (j = 1,...,S) логический мультиплексор реализует все булевы формулы, помечающие дуги, исходящие из j-ой вершины графа переходов. Это удается осуществить в том случае, когда все указанные формулы взаимно ортогональны. Таким образом, число логических мультиплексоров в схеме равно S, а общее число элементов в схеме в этом случае

Э₂= S + 3.

На рис.5 приведена схема из шести элементов, реализующая граф переходов, приведенный на рис.3.

Рис. 5

Третий вариант стандартных схем является промежуточным между рассмотренными. Он содержит, как и вторая разновидность схем, S логических мультиплексоров, но в силу того что в этом случае число информационных входов i-го логического мультиплексора ограничено и равно M = 2^a , где a = ]log₂ k_i [, то приходится строить комбинационную схему из традиционных логических элементов так же, как в первом случае. Свободные информационные входы логических мультиплексоров подключаются к выходу первого цифрового мультиплексора, что обеспечивает сохранение состояний автомата. Число элементов в этом случае оценивается соотношением:

Э₃ Ј N + H - L + S + 3.

Граф переходов, представленный на рис.6, реализуется схемой третьего типа (рис.7) из 10 элементов (Э₃ Ј 4 + 7 - 4 + 3 + 3 = 13).

Рис. 6

Рис. 7 (в натуральную величину)

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

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

[ <<< | 1 | 2 | 3 | >>> ]

[an error occurred while processing this directive]