Для того чтобы АКА выполнил заданный алгоритм работы, критические состязания элементов памяти в нем должны быть исключены.
2. МЕТОД КОДИРОВАНИЯ СОСТЯЗАНИЙ ПО СТОЛБЦАМ ТП.
Рассмотрим универсальный метод синтеза АКА с помощью кодирования состояний по столбцам ТП. Данный метод не требует анализа всех возможных случаев состязаний и обеспечивает устойчивость работы АКА при выбранном варианте кодирования. В качестве примера используем ТП (табл. 5).
Будем называть l - классом столбца аj множество состояний, содержащее устойчивое состояние и все неустойчивые состояния, из которых задан переход в данное устойчивое состояние.
Столбец а2 содержит четыре l-класса: l5={ 1,3 }, l6={ 2,4 }, l7={ 5,6 },l8={ 7 }.
Рассмотрим переходы схемы по столбцу а1. Имеем переход из состояний 6 и 7 в состояние 1. Эти переходы осуществляются внутри класса l1; переход из 3 в 2 внутри l2; из 4 в 5 внутри l3. Критические состязания возникают, если схема вместо одного устойчивого состояния ложно перейдет в другое устойчивое состояние, т. е., если из одного класса l схема ложно перейдет в другой класс l.
Необходимо исключить такие ложные переходы между l - классами. Для этой цели в столбце аj необходимо выделить для кодирования состязаний, принадлежащих l - классам, специальные внутренние переменные, которые имеют следующие свойства.
Свойство 1. Для состязаний, принадлежащих одному l - классу, они имеют одинаковое значение.
Свойство 2. Для состязаний, принадлежащих разным l - классам, они имеют разное значение.
Свойство 3. При любом переходе внутри столбца аj они не меняют своего значения.
Свойство 4. Поведение АКА в столбце аj зависит только от этих переменных.
На рис. 3 представлены l - классы для столбца а1 и выделены внутренние переменные У1 и У2, которые, будем считать, обладают свойствами 1-4.
класса l3. Во время этого перехода значение внутренних переменных У1 и У2 не меняется (свойство 3), так как и для состояния 4, и для состояния 5 У1=1 У2=0 (свойство 1). Нахождение схемы в состояниях, принадлежащих классу l3 можно определить конъюнкцией а1 (свойство 4).
Для других состояний l - классов этого же столбца имеем: для l1 - для l2 - . Очевидно, что все конъюнкции отличаются хотя бы одним значением переменной У (свойство 2). Будем говорить, что l - классы по столбцу а1 разделены внутренними переменными У1 и У2 (т. е. отличают их друг от друга). Эти переменные будем называть разделяющими.
Таким образом можно сделать вывод, что при кодировании состояний, принадлежащих l - классам столбца аj разделяющими переменными, обладающими свойствами 1-4, исключаются ложные переходы между l - классами, а следовательно и критические состязания.
Рассмотрим способ кодирования строк ТП, который обеспечивает выполнение этого условия,
Будем обозначать через nj – общее число устойчивых состояний или число l - классов столбца аj. Для разделения l - классов столбца аj необходимо выделять N=] log2 n j [ разделяющих переменных.
Для примера имеем:
N1 = ] log2 n1 [ = ] log2 3 [ = 2.
N2 = ] log2 n2 [ = ] log2 4 [ = 2.
Таким образом, для разделения l - классов по столбцу а1 требуется две переменные у1 и у2, а по столбцу а2 также две переменные у3 и у4, классов столбца а2 разделяющими переменными У3 и У4. На рис.4 приведен один из вариантов кодирования состояний l - классов.
Общее кодовое слово i-ой строки ТП образуется совокупность значений всех переменных по всем столбцам i-ой строки.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.