Математическая теория систем. Математические основы теории систем

• Название: Математические основы теории систем
• Дата: 20.01.2023
• Размер: 2.07 Mb.
• Имя файла: Математическая теория систем.pdf
• Тип: Учебное пособие; #895603
• страница: 16 из 35

Пример 2.26.
Пусть логическая функция задана булевой формулой

126
(
)
(
)
1 2
3 4 1
3
f
x
x x x x
x
=
∨
∨
Синтезируем комбинационный автомат, реализующий данную функ- цию в
базисе ДНФ. Для этого приведем заданную формулу к дизъюнк- тивной нормальной форме, т.е. к дизъюнкции элементарных конъюнк- ций, используя правила эквивалентных преобразований булевых формул:
(
)
(
)
(
)
1 2
3 4 1
3 1
2 3 4 1 3 4 2 3 4
f
x
x x x x
x
x
x x x
x x x
x x x
=
∨
∨
=
∨
=
∨
Затем строим двухъярусную сеть, в первом ярусе которой будет два конъюнктора, а во втором – один дизъюнктор (см. рис.2.29).
Рис.2.29. Сеть в базисе ДНФ
Если необходимо реализовать ту же логическую функцию в
базисе
элементов Шеффера (“И–НЕ”), то каждый элемент сети, представленной на рис. 2.29, заменяем элементом “И–НЕ” (см. рис.2.30).
Рис.2.30. Сеть в базисе элементов Шеффера
Пример 2.27.
Пусть логическая функция задана булевой формулой
&
&
&
x
1
x
3 4
x
x
2
f
&
&
∨
x
1
x
3 4
x
x
2
f

127
(
)
1 2 2
1 3
f
x x
x
x x
=
⋅
∨
Для реализации данной функции в
базисе КНФ необходимо вначале по формулам эквивалентных преобразований перейти к конъюнктивной нормальной форме, т.е. к конъюнкции элементарных дизъюнкций:
(
) (
)(
) (
)
(
)
(
) (
)
(
)
(
)(
)
(
)
(
)(
)(
) (
)(
)
1 2 2
1 3 1
2 2
1 3 1
2 2
1 3 1
2 2
1 3
1 2
2 1 2 3 1
2 2 1 2 3 1
2 2
1 2
3 1
2 2
3
f
x x
x
x x
x
x
x
x x
x
x
x x x
x
x
x
x
x
x
x
x x
x x
x
x x x x x
x
x
x
x
x
x
x
x
x
x
=
⋅
∨
=
∨
∨
=
∨
⋅
=
=
∨
⋅
∨
=
∨
∨
=
=
∨
⋅
=
∨
∨
∨
=
∨
∨
Сеть, реализующая данную формулу, представлена на рис. 2. 31.
Рис. 2.31. Сеть в базисе КНФ
Для реализации той же функции в
базисе элементов Пирса (“ИЛИ-
НЕ”) заменяем каждый элемент сети на рис. 2.31 элементом “ИЛИ-НЕ”
(см. рис. 2.32).
Рис. 2.32. Сеть в базисе элементов Пирса
∨
&
1
x
2
x
x
3
f
∨
∨
∨
1
x
2
x
x
3
f
∨

128
2.5.7. Кодирование состояний
Речь пойдет о кодировании в основном внутренних состояний, так как двоичное кодирование входного и выходного алфавитов не вызывает принципиальных трудностей и практически не влияет на сложность по- лученных при этом структурных схем.
Пусть имеется автомат
(
)
(
)
1
, , ,
,
/
A
X Q Y q
Q F x X y Y
=
∈
∈
∈
и набор элементов памяти
U
1
,
U
2
,
… U
p
. Каждому состоянию
q автомата А поста- вим в соответствие конечный упорядоченный набор (
z
1
,
z
2
,
… z
p
) состоя- ний автоматов
U
1
,
… U
p
так, что различным состоянием автомата
А ста- вятся в соответствие различные последовательности состояний элемен- тарных автоматов
U
1
,
… U
p
. Таким образом, состояния автомата А коди- руются наборами состояний элементов памяти
U
1
,
… U
p
, в результате чего возникают структурные состояния автомата
А. Поскольку при прак- тическом синтезе схем используются в основном в качестве элементов памяти элементарные автоматы с двумя состояниями 0 и 1, то и состоя- ния автомата
А кодируется наборами двоичных переменных (z
1
,
…z
p
)
(двоичное кодирование).
В зависимости от того, каким образом выполнять кодирование, струк- турные схемы одного и того же автомата могут получаться различными, так как каждому варианту кодирования соответствует структурная схема определенной сложности. Различные способы кодирования оказываются неравноценными как с точки зрения простоты структуры автомата, так и с точки зрения других критериев: быстродействия, надежности и прочее.
Самое главное, конечно, – это простота структуры автомата. В каче- стве промежуточной цели можно наметить простоту системы логических функций, реализуемых комбинационной частью автомата. Выбирая раз- личные варианты кодирования, мы получаем различные системы логиче- ских функций. Можно минимизировать эти системы, например, в классе
ДНФ, а затем подсчитывать число символов в полученных выражениях.
Можно надеяться, что, выбирая способ кодирования, который приводит к выражениям с минимальным числом букв, мы получим в итоге и более простую структуру автомата.
В асинхронных автоматах могут возникать при кодировании другие проблемы, связанные с практической реализацией и конструктивными особенностями элементов памяти (триггеров). Каждый из реальных эле- ментов памяти обладает инерционностью (ненулевое время срабатыва- ния), причем эта инерционность не является постоянной и одинаковой для всех элементов. Это не учитывается в абстрактной модели автомата.

129
Вследствие этого при переходе автомата из одного состояния в другое может реализоваться некоторая последовательность элементарных пере- ходов (соответствующих изменениям состояния отдельных элементов памяти), при которой автомат проходит через некоторое множество про- межуточных состояний и которая в общем случае непредсказуема. По- следующие действия автомата будут определяться уже значениями функции переходов на достигнутых промежуточных состояниях.
Таким образом, дальнейшее поведение автомата может оказаться в за- висимости от того, какой из элементов памяти быстрее среагирует на прикладываемое к нему воздействие. Элементы как бы состязаются в быстроте реакции, чем и обусловлено название соответствующего явле- ния – состязания между элементами памяти. Если, в конце концов, авто- мат приходит в намеченное матрицей переходов состояние, то состязания можно считать неопасными, в противном случае их следует рассматри- вать как опасные.
Чтобы поведение автомата не отличалось от заданного матрицей пе- реходов, необходимо устранить все опасные состязания между элемента- ми памяти. Один из возможных способов следующий.
Заданный в автомате переход
i→j можно обеспечить, если придать функции переходов значение
j на всех возможных промежуточных со- стояниях, в которые автомат может попасть из состояния
i (при фиксиро- ванном входном состоянии). В этом случае элементы памяти, которые должны менять свои состояния, будут подвергаться постоянному надле- жащему воздействию на всем протяжении рассмотренного перехода независимо от того, в каком порядке они срабатывают. Тогда состязания становятся неопасными, и неизбежно наступит переход
i→j, который назовем
прямым, причем происходить он будет с максимальным быстро- действием.
Одним из эффективных способов предотвратить опасные состязания является рациональное кодирование внутренних состояний автомата. Все такие методы можно условно разбить на два класса. В одном из них ищутся такие коды, при которых все заданные переходы становятся эле- ментарными (меняет состояние только один элемент памяти) и, следова- тельно, состязаний вообще нет. Если для исходной матрицы переходов такое сделать не удается, то матрица преобразуется, причем множество состояний, как правило, расширяется. Во втором классе находятся мето- ды, устраняющие лишь опасные состязания и не связанные с увеличени- ем числа внутренних состояний. Эти методы основаны на реализации прямых переходов.
В качестве примера рассмотрим один из методов подобного типа.

130
Вначале необходимо сформулировать необходимые и достаточные условия отсутствия опасных состязаний.
Пусть
( )
,
U i j – множество всех возможных промежуточных состоя- ний, включая состояния
i и j, в которые автомат может попасть при пере- ходе
i→j. По определению функция переходов – однозначная функция полного состояния, а при фиксированном входном состоянии – одно- значная функция внутреннего состояния. Отсюда следует, что прямые переходы могут быть реализованы тогда и только тогда, когда выполня- ется условие: для каждой пары переходов
i→j и k→l, соответствующих одному и тому же входному состоянию, множества
( )
,
U i j и
( )
,
U k l не пересекаются, т.е.
( )
( )
,
,
U i j
U k l
∩
= ∅ , если j≠l.
Найти множество
( )
,
U i j можно, зная коды состояний i и j. Пусть эти коды будут
z(i) и z(j). Множество
( )
,
U i j будет образовано всеми теми состояниями, коды которых совпадают с кодами
z(i) и z(j) в тех компо- нентах, которые совпадают между собой в векторах
z(i) и z(j). Таким об- разом, множество
( )
,
U i j (точнее множество соответствующих кодов) может быть представлено вектором
( )
,
t i j , компоненты которого прини- мают значения одноименных компонентов векторов
z(i) и z(j) в случае совпадения последних и значение “–“ в противном случае. Коды всех элементов множества
( )
,
U i j могут быть получены из
( )
,
t i j подстанов- кой вместо прочерков нулей и единиц.
Необходимым и достаточным условием непересечения множеств
( )
,
U i j и
( )
,
U k l является наличие такой одноименной компоненты в кодах
( )
,
t i j и
( )
,
t k l , которая принимает значение 1 в одном и 0 в дру- гом коде. Доказательство этого утверждения очевидно; если это условие выполнено, то любой элемент множества
( )
,
U i j отличается от любого элемента множества
( )
,
U k l (именно этой компонентой), в противном случае можно в этих множествах найти общий элемент.
Кодирующей матрицей назовем такую матрицу
Q с двоичными эле- ментами, столбцами которой будут коды внутренних состояний, а стро- кам поставлены во взаимно-однозначное соответствие внутренние состо- яния автомата. Получение такой матрицы и есть цель кодирования.
Для матрицы
Q необходимое и достаточное условие отсутствия опас- ных состязаний можно сформулировать так: для каждой пары
i→j и k→l,

131 соответствующих одному и тому же входному состоянию (
j≠l), в матрице
Q должна найтись строка, в которой i-я и j-я компонента принимают зна- чение 1 (или 0), а
k-я и l-я компоненты – значение 0 (или 1).
Условие, предъявляемое при этом к матрице
Q при рассмотрении конкретной пары переходов
i→j и k→l, назовем элементарным. Оно мо- жет быть представлено вектором, у которого
i-я и j-я компоненты ин- версны по отношению к
k-й и l-й компонентам, а остальные компоненты
– прочерки (длина такого вектора равна числу внутренних состояний ав- томата). Совокупность таких векторов для всех пар и всех входных со- стояний образует матрицу условий
S.
Задача нахождения матрицы
Q, удовлетворяющей совокупности усло- вий, задаваемых матрицей
S, сводится к задаче нахождения минимальной покрывающей формы для матрицы
S.
Рассмотрим последнее утверждение. Можно считать, что каждая из строк матрицы
S задает некоторое частичное двухблочное разбиение на множестве столбцов матрицы
Q. Один блок – это столбцы, отмеченные единицей (которая стоит в соответствующих компонентах строки матри- цы условий), другой блок – это столбцы, отмеченные нулями. Прочерк, как и ранее, является признаком неопределенности – эти столбцы могут принадлежать любому блоку. Таким образом, решаемая задача сводится к нахождению такой кодирующей матрицы
Q, которая бы покрывала матрицу условий
S. При этом опасные состязания будут отсутствовать.
Дополнительно хотелось бы, чтобы число строк такой матрицы было бы минимальным, что соответствует минимальному количеству элементов памяти.
Таким образом, всю процедуру нахождения кодирующей матрицы
Q можно сформулировать следующим образом.
1. Считаем, что все состояния автомата различны, т. е. их надо коди- ровать разными кодами. Отсутствие эквивалентных состояний может гарантировать предварительная минимизация автомата на абстрактном уровне или добавление в матрицу переходов лишнего столбца, значения элементов которого совпадают с номерами строк, где они находятся.
2. Составляем матрицу условий
S для всех входных состояний, выбра- сывая строки, которые покрываются другими строками. В результате по- лучаем минимальную матрицу условий
S
0 3. Известными методами находим минимальное покрытие полученной матрицы
S
0
. Найденная матрица и будет минимальной кодирующей мат- рицей. Число строк этой матрицы равно необходимому минимальному числу элементов памяти автомата.

132
Необходимо понимать, что при описанном кодировании устраняются только опасные состязания, но не гарантируется оптимальность получен- ного решения в смысле минимума памяти.
2.5.8. Программная реализация комбинационных автоматов
Комбинационный автомат вычисляет некоторую логическую функ- цию или систему функций, а, как известно, любой процесс вычисления может быть реализован как в аппаратном виде (схема из элементов), так и программным образом.
Под программой будем понимать некоторую пронумерованную по- следовательность команд
1
,...
s
k
k , взятых из некоторого фиксированного набора (системы команд). Программа работает над конечным множе- ством пронумерованных (поименованных) двоичных ячеек. Номер ячей- ки − это ее адрес. Адресом ячейки может служить и имя логической пе- ременной, значения которой хранятся в данной ячейке. Система команд содержит команды – операторы типа
b:=f(a
1
,
…a
p
)
– выполнить операцию
f над содержимым ячеек
1
,...
p
a
a и записать результат в ячейку b; и условные двухадресные переходы двух видов:
1) «если
a, то i, иначе j»(если a=1, то перейти к выполнению команды
i
k , иначе перейти к команде
j
k ) и
2) «если
a (a=0), то i, иначе j». Операция f(a
1
,
…a
p
) – это логическая функция
p переменных (в частном случае она может быть константой 0 или единицей). Если
j – это номер следующей по порядку команды, то переход можно считать одноадресным, если
i=j – то это безусловный пе- реход. Любая из перечисленных команд может быть заключительной, что указывается словом «конец».
Процессом вычисления программы
k
1
,
…k
s
называется последователь- ность шагов
k(1),…k(t), на каждом из которых выполняется одна команда программы. Указанная последовательность определяется так:
1)
1
(1)
k
k
= ,
2) если ( )
r
k i
k
= – оператор, то
1
( 1)
r
k i
k
+
+ =
;
3) если
k(i) – условный переход, то номер команды k(i+1) указывается этим переходом;
4) если
k(i) – заключительная команда, то процесс вычисления оста- навливается после ее выполнения.
Программа П вычисляет некоторую логическую функцию
y=f(x
1
,
…x
n
), если для любого двоичного набора σ=(σ
1
,
…σ
n
)
при начальном состоянии

133
х
1
=σ
1
,
х
2
=σ
2
,
…х
n
=σ
n
программа через конечное число шагов останавлива- ется и при этом в ячейке
y будет величина f(σ
1
,
…σ
n
).
Критерии, по которым можно оптимизировать программу, следую- щие:
1) число команд в тексте программы;
2) объем промежуточной памяти, то есть число ячеек, необходимых для хранения промежуточных результатов;
3) время вычисления – среднее ср
1
(П)
( )
2
n
n
t
σ
=
τ σ
∑
и максимальное – max
(П) max ( )
n
t
σ
=
τ σ , где τ
n
(σ) – время работы программы на конкретном наборе σ, а сумма и максимум берется по всем 2
n
наборам.
Любой линейно-упорядоченной сети (а следовательно, и любому ком- бинационному логическому автомату), содержащей
N элементов и реали- зующей функцию
f, нетрудно поставить в соответствие программу, вы- числяющую
f и состоящую из N команд, следующим образом. Занумеру- ем элементы сети числами 1, …,
N в соответствии с линейной упорядо- ченностью. Номер 1 получит один из входных элементов, номер
N – вы- ходной элемент.
Пусть элемент
e
i
реализует функцию ϕ
i
и к его входным полюсам присоединены выходные полюсы элементов
e
j1
,
…e
jp
. Некоторые из них возможно являются входными полюсами сети. Поставим в соответствие элементу
e
i
ячейку a
i
и команду
a
i
:=ϕ
i
(
a
j1
,
…a
jp
), если
i≠N или ячейку y и команду
y:=ϕ
N
(
a
j1
,
…a
jp
) конец, если
i=N. Получим в результате програм- му, не содержащую условных переходов (так называемая
операторная программа), в которой порядок команд в точности соответствует порядку элементов в сети, а система команд – базису сети.
Проблема синтеза операторных программ сводится в основном к про- блемам синтеза комбинационных сетей: в частности, задачи функцио- нальной полноты системы команд и минимизации собственно текста про- граммы соответствуют задачам о функциональной полноте системы функций и минимизации комбинационных схем. Так как операторные программы не содержат условных переходов, время ее вычисления на любом наборе одинаково и совпадает с максимальным временем
t
ср
=
t
max
=
N и в силу теоремы Шеннона – Лупанова при больших n прибли- жается к
2
n
n
. А проблема минимизации памяти (за счет многократного использования одной и той же ячейки для нескольких последовательно

134 получающихся промежуточных результатов) для таких программ – не- тривиальная комбинационная задача.
Другой вид программ – это программы, состоящие из команд типа
y:=σ(σ=0или σ=1) и условных переходов. Такие программы называются
бинарными. Всякую булеву формулу F, содержащую N символов, можно реализовать бинарной программой, вычисляющей
F за время t
max
=
N и содержащую
N команд условного перехода, а также две команды y=0и
y=1 (эти команды не вошли в общее время t
max
). Чтобы было понятнее, представим программу в виде графа, где вершины – это команды, а ребра
– переходы. Пусть
G
1
– граф программы для функции
f
1
с начальной вер- шиной
V
10
и двумя заключительными вершинами
V
1
z
0
(с командой
y=0) и
V
1
z
1
(с командой
y=1), а G
2
– граф программы, реализующей функцию
f
2
с начальной
V
20
и заключительными V
2
z
0
и
V
2
z
1
вершинами. Тогда: а) вычислять функцию
f=f
1
∨f
2
будет программа, граф G которой полу- чен присоединением
G
2
к “нулю”G
1
(то есть отождествлением вершин
V
1
z
0
и
V
20
; команда
y:=0 при этом отбрасывается); б) вычислять функцию
f=f
1
&
f
2
будет программа, граф G' которой по- лучен присоединением
G
2
к “единице” G
1
(отождествлением
V
1
z
1
и
V
20
); в) вычислять отрицание f =
1
f будет программа, граф которой полу- чен из
G
1
заменой команд в V
1
z
0
и
V
1
z
1
на инверсные.
В графе
G (пункт а) получаются при этом две единичные, а в графе G'
(пункт б) две нулевые вершины. В обоих случаях их надо отождествлять.