ПТЦА - Прикладная теория цифровых автоматов


	Загрузить архив:
	Файл: ref-9894.zip (649kb [zip], Скачиваний: 141) скачать

1. Методы анализа и синтеза комбинационных схем.

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

Для выяснения, чтожетакое комбинационная схема, рассмотрим схему S,имеющую m входов и n выходов (рис. 1). На её входы могут быть поданы наборы значений входныхпеременных X_i {0,1},Y_jÎ{0,1},

Схема S называетсякомбинационной,если каждуюизn функцийеёвыходов Y₁,Y₂, ..., Y_n можно представить как булеву функцию входных переменных X₁, X₂, ..., X_m.

Комбинационная схема описывается с помощью системы уравнений (1), где F_i– булева функция.

(1)

Как следует из определения комбинационной схемы,значения выходных переменных Y_jв произвольный моментвремени однозначно определяются значениями входных переменных X_i.

Структурно комбинационная схема может бытьпредставлена каксовокупность элементарныхлогическихсхем – логических элементов (ЛЭ).ЛЭ выполняют над входными переменными элементарные логические операции типа И-НЕ,И, ИЛИ,ИЛИ-НЕ и т.д. Число входов логического элемента соответствует числу аргументов воспроизводимой им булевой функции. Графическое изображение комбинационной схемы,при котором показанысвязимежду различными элементами,а сами элементы представлены условными обозначениями, называетсяфункциональнойсхемой.

В ходе разработки комбинационных схем приходится решать задачи анализа и синтеза.

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

Задача синтеза заключается в построении из заданного наборалогическихэлементов комбинационной схемы, реализующей заданную систему булевых функций.

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

1.1. Канонический метод синтеза комбинационных схем.

Как отмечалось выше,комбинационнаясхема (КС)может иметьнесколько выходов.При каноническом методе предполагается,что каждая выходная функция реализуетсясвоей схемой, совокупность которых и даёт требуемую КС. Поэтому синтез сложной КС с n выходами заменяется синтезом n схем с однимвыходом.

Согласно каноническому методу синтез КС включает всебя ряд этапов.

1. Подлежащая реализации булева функция (или еёотрицание) представляется в виде СДНФ.

2. С использованием методов минимизации определяетсяминимальная ДНФ (МДНФ) или минимальная КНФ (МКНФ).Из полученных двух минимальных форм выбирается более простая.

3. Булеву функцию в минимальной форме согласно п.2 представляют в заданном (или выбранном разработчиком) базисе .

4. По представлению функции в заданном базисе строят комбинационную схему.

Необходимо отметить,что подлежащаяреализации булева функция F(X₁,X₂,...,X_m) может быть задана не на всех возможных наборах аргументов X₁, X₂, ..., X_m.На тех наборах,где функция неопределенна, её доопределяют так, чтобы в результате минимизации получить более простую МДНФ или МКНФ. При этом упростится и сама КС. Кроме того, довольно часто с целью получения ещё более простого представления функции МДНФ, полученная в п.2, представляется в так называемой скобочной форме, т.е. выносятся за скобки общие части импликантМДНФ.

Рассмотрим канонический метод синтеза на примере построения схемы полного одноразрядного двоичного сумматора.

Как известно из курса машинной арифметики,полный одноразрядный сумматор - это устройство, которое осуществляет сложение по mod 2 соответствующих разрядов (X1,X2) двоичных чисел с учётом переноса (Р_m) в данный разряд из соседнего младшего разряда суммы. Сумматор вырабатывает цифру результата (S) в данном разряде и перенос (Р_с) в соседний старший разряд суммы. Таблица истинности такого сумматора (т.е. представление булевой функции, которую он реализует, в виде СДНФ) представлена ниже.

X₁

X₂

Табл.1. Таблица истинности полного одноразрядного двоичного сумматора.

P_m

P_c

Необходимо получить булевы функции S=F₁(X₁,X₂,Р_m) и Р_с=F₂(X₁,X₂,Р_m). Карты Карно для этих функций приведены ниже (рис.2).

Как следует изприведённыхкарт, МДНФ соответствующих функций имеет вид:

(2)

P_m+

X₂+X₁

+ X₁ X₂ P_m

P_c= X₁ X₂+X₁P_m+X₂ P_m

Полученная система булевых функций представлена в базисе И, ИЛИ, НЕ. Соответствующая ей КС приведена на рисунке 4.

Полученную комбинационную схему можно упростить, вынеся за скобки общие части в выражениях для S и Р_c, однако существенного результата это не даст (желательносамостоятельнов этом убедиться).

Значительно упростить схему можно,если воспользоваться другимбазисом, напримерлогическим элементом "ИСКЛЮЧАЮЩЕЕ ИЛИ". В этом случае выражение для S можно записать S = (X₁+X₂+ Р_m)mod2= X₁Å X₂Å Р_m. Тогда схема для S будет иметь вид (рис.3).

Иногда для синтезаКСс несколькимивыходами может использоваться следующий приём. Будем считать, что при синтезе схемы сумматора функция S является функцией четырёх переменных:S=f(X₁,X₂,Р_m,Р_с).Таблица истинностидля этого случая принимает вид изображенный в таблице 2.

X₁	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
X₂	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
P_m	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
P_c	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
S	X	1	X	1	X	X	0	1	X	X	0	X	0	X	1

Таблица 2. Таблица истинности сумматора.

Неопределённые значения для S соответствуют наборам, которые никогда не могут быть в реальной схеме.Карта Карно для функции S=f(X₁,X₂,P_m,P_c) представлена на рис.5.

В результате минимизации, получается :

(3)

S=+X₂+X₁+ X₁ X₂ P_m = (P_m+X₂+X₁)+ X₁ X₂ P_m

Сравнивая выражения (2) и (3),отмечаем, чтофункция S=f(X₁,X₂,P_m,P_c)проще, чемфункцияS=f₁(X₁,X₂,P_m).Схему, соответствующую (3), предлагается построить самостоятельно.

Т.о. задача синтеза имеет обычно несколько решений. Для сравнения различных вариантов комбинационных схемиспользуют их основныехарактеристики:сложность и быстродействие.

1.2. Характеристики комбинационных схем.

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

Сложность (цена) по Квайну определяетсясуммарным числом входов логических элементов в составе схемы.

При такой оценке единица сложности – один вход логического элемента. Ценаинверсного входа обычно принимается равной двум. Такой подход к оценке сложности оправданпоследующим причинам:

-сложность схемы легко вычисляется побулевымфункциям, на основе которых строится схема: для ДНФ сложность схемы равна сумме количества букв,(букве со знаком отрицания соответствует цена 2), и количества знаков дизъюнкции, увеличенного на 1 для каждого дизъюнктивного выражения.

-всеклассические методыминимизациибулевых функций обеспечивают минимальность схемы именно в смысле цены по Квайну.

Практика показывает, что схема с минимальной ценой по Квайну обычно реализуется наименьшим числом конструктивных элементов – корпусов интегральных микросхем.

Быстродействие комбинационной схемы оценивается максимальной задержкой сигнала при прохождении его от входа схемы к выходу, т.е.определяетсяпромежутком времениотмомента поступления входных сигналовдо моментаустановлениясоответствующихзначений выходных. Задержка сигнала кратна числу элементов,через которые проходит сигнал отвхода квыходу схемы.Поэтому быстродействие схемы характеризуется значением rt, где t- задержка сигнала на одном элементе. Значение r определяетсяколичеством уровней комбинационной схемы,которое рассчитывается следующим образом. Входам КС приписываетсяуровень нулевой. Логические элементы, связанные только со входами схемы относятся к уровню ПЕРВОМУ.Элемент относится куровню k,если он связан по входам с элементами уровней k-1, k-2,и т.д. Максимальныйуровень элементов r определяетколичество уровней КС, называемое рангом схемы. Пример определения ранга r схемы приведён на рисунке 6.

Как известно, любая булева функция может быть представлена в ДНФ, которой соответствует двухуровневая комбинационная схема. Следовательно, быстродействие любой КС в принципе можно довести до 2t.

Минимизация булевой функции с целью уменьшения сложностисхемобычно приводит к необходимости представления функций в скобочной форме,которой соответствуют схемы с r>2. Т.е., уменьшение затрат оборудования в общем случае приводит к снижению быстродействия схем.

1.3. Системы (серии) логических элементов и их

основные характеристики.

При построении КС устройств вычислительной техники используются различные логические элементы, которые должны согласоваться по входным и выходным сигналам, напряжению питания и т.д. Для этой цели логические элементы объединяют в серии.

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

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

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

В большинстве современных серий элементов имеются микросхемы малой степени интеграции (ИС до 100 элементов на кристалл), средней степени (СИС – до 1000 элементов на кристалл), большой степени интеграции (БИС – до 10000 элементов на кристалл) и сверхбольшой степени интеграции (СБИС – более 10000 элементов на кристалл). Логические элементы в виде ИС реализуют совокупность простых логических операций: И, ИЛИ, И-ИЛИ, И-НЕ, ИЛИ-НЕ и т.д. Логические элементы на СИС иБИС реализуют узлы ЭВМ, на СБИС – микроЭВМ.

Основными параметрами серии логических элементов являются:

- питающие напряжения и сигналы для представления логического 0 и логической 1;

- коэффициенты объединения по входу;

- нагрузочная способность (коэффициент разветвления по выходу);

- помехоустойчивость;

- рассеиваемая мощность;

- быстродействие.

Серия элементов характеризуется количеством используемых питающих напряжений и их номинальными значениями. Обычно логическому 0 соответствует низкий уровень напряжения, а логической 1 –высокий. Для наиболее часто используемых серий напряжение питания составляет +5В,уровень логической единицы 2,4-5В,уровень логического 0 –0-0,4В.

Коэффициент объединения по входу (К_об) определяет максимально возможное число входов логического элемента, иными словами, функцию скольких переменных может реализовать этот элемент. Обычно К_об принимает значение от 2 до 4, реже К_об=8. Увеличение числа входов связано с усложнением схемы элементов и приводит к ухудшению других параметров – помехоустойчивости, быстродействия и т.д.

Коэффициент разветвления по выходу (К_раз) показывает на сколько логических входов может быть одновременно нагружен выход данного логического элемента. Обычно К_раздля наиболее часто используемых серий равен 10. Иногда вместо К_раз задается предельно допустимое значение выходного тока логического элемента в состоянии 0 или 1.

Помехоустойчивость –это способность элемента правильно функционировать при наличии помех. Она определяется максимально допустимым напряжением помехи, при котором не происходит сбоя в его работе. Обычно это напряжение порядка 0,6-0,9 В.

Быстродействие логических элементов является одним из важнейших параметров и характеризуется временем задержки распространения сигнала. Этот параметр существенно зависит от технологии изготовления микросхем и лежит в диапазоне от единиц до сотен наносекунд.

Наиболее часто употребляемые типы интегральныхмикросхем – это потенциальные элементы транзисторно-транзисторной логики (ТТЛ) - серии К155,К555,К531, К1533 и т.д.,транзисторной логики с эмиттерными связями (ЭСТЛ) – это серии К500,К1500, элементы на КМОП транзисторах - серии К176, К561,К564 и т.д.

При синтезе КС на реальных логических элементах необходимо обязательно учитывать ограничения на К_об и К_раз.

1.4.СИНТЕЗ КССУЧЕТОМ ОГРАНИЧЕНИЙНА

При построении КС может оказаться,что выход k - го логического элемента нагружен входов другихЛЭ (рис.7а). Это означает,что k - тый логическийэлемент перегружени необходимопринять меры, устраняющие указанное явление. Существуют два способа обеспечения заданного

· использование дополнительных развязывающих усилителей;

· дублирование перегруженного элемента.

Схема с использованием дополнительных развязывающихусилителей представленанарис.7.б. Количество p дополнительных усилителей, необходимых для обеспечения заданного

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

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

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

1.5. СИНТЕЗ КССУЧЕТОМ ОГРАНИЧЕНИЯНА.

Представлению функции в виде ДНФ соответствует двухуровневая КС (если считать,что на ее вход могут поступать какпрямые так и инверсные входные сигналы),на первом уровне которой элементы И ,а их выходы объединяются на втором уровне элементом ИЛИ . Такое построение КС обеспечиваетее максимальное быстродействие,таккак рангсхемыминимален. Однако,невсегда возможно на первом уровне и,особенно, на втором выбрать логические элементы с требуемымт.к. может оказаться, что ЛЭ с таким эквивалент с большим либо, что предпочтительней,преобразовать БФ, перейдя от ДНФ к скобочной форме.Этотпереход сопровождается уменьшением требуемого для построения схемы. Осуществить такой переход можно с помощью факторного алгоритма, суть которого рассмотрим на примере.

Пусть задана некоторая булева функция в виде

Для реализацииэтой функциипоприведенному выражению необходимо использовать 3 логическихэлемента4И, один логический элемент 5И, один логический элемент 4ИЛИ.

С помощью факторного алгоритма получим скобочную форму для заданной функции. Для этого обозначим все конъюнкции буквами:

и будемрассматриватьих какнекоторыемножества. Находим попарные пересечения множеств:

,,,,,.

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

Обозначим F = и находимпересечения:

Следовательно, для исходной функции имеем:

Обозначим

ПересечениеСледовательно, окончательно имеем:

Для реализации функции по последнему выражению необходимо 5 элементов 2И, 1 элемент 3И, 3 элемента 2ИЛИ ( рис.8 ).

Как видно из полученной схемы для ее реализации необходимы элементы с = 2 или 3 (в отличиеотисходной с = 4 или 5). Однако ранг схемы увеличился до 7, что приводит к увеличению задержки срабатывания схемы.

1.6. Анализкомбинационных схем.

Задачи анализа КС возникают при необходимости проверить правильность синтеза (на этапе проектирования) или определить БФ, реализуемую КС (при анализе или ремонте схем). Все существующие методы анализа делятся напрямые и косвенные.

В результатеанализаКС прямым методом получается множество наборов входных переменных, обеспечивающих заданное значение навыходе,что позволяет записать в алгебраическом виде БФ,реализуемую схемой. К прямым методам относится метод p- алгоритма.

Применение косвенных методов даетвозможность определитьреакцию схемы на заданный набор входных переменных в статике или проанализировать переходный процесс смены одного входного наборана другой. Примерамикосвенныхметодов анализа, являются методы синхронного и асинхронного моделирования.

Все упомянутые методы анализа являются машинoориентированными, что позволяет выполнить анализ схемы на ЭВМ.

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

1.7. Анализ комбинационных схемметодомp-алгоритма.

При данном методе,как упоминалось выше,ищутся наборы входных переменных, обеспечивающих заданное значение на выходе КС. Наборы, обеспечивающие на выходе КС логическую 1, образуют так называемое единичное покрытиеАналогично, входные наборы,обеспечивающие на выходе КС логический 0,образуют нулевое покрытие Рассмотрим покрытияпростейшегологического элемента 2И, выполняющегофункцию Y=X₁X₂.Таблица истинностидляэтой функции:

Табл.3 Таблица истинности функции Y=X₁X₂

Как видно из приведенной таблицытолькопри единственном наборе X₁=1 и X₂=1 на выходе ЛЭ будет 1, т.е.единичноепокрытие включает только один набор

Это покрытие можно упростить,заметив,что первыйнабор склеивается со вторым и третьим, т.е.

Т.о. для ЛЭ 2И можно сказать, что 1 наего выходебудет только при обеих единицах на входах, а для обеспечения0на выходе достаточно подать хотя бы на один вход 0. Рассуждаяаналогично, получим таблицу покрытий для основных ЛЭ, представленных ниже в табл. 4.

Таблица 4.

ЛЭ Y Y Y Y Y Y Y

НЕ 2И 2И – НЕ 2ИЛИ 2ИЛИ–НЕ ИСК. ИЛИ 3И – НЕ

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₃

1 0 X 1 1 0 0 1 X0 01 1 1

X 0 X 1 1 1

0 1 1 0 X 1 X 0 0 0 1 0 X X

X 0 X 1 1 0 X 0 X

X X 0

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

Пример анализа КС (рис 9. ) методом p - алгоритма представлен в табл. 5. В последней колонке этой таблицы приведен оператор подстановки, в результате работы которого сигнал на выходе ЛЭ заменяется соответствующим покрытием. Необходимо обратить внимание, что все значения переменных, записанные в одной строке, должны одновременно быть в наличии для обеспечения заданного значения выходного сигнала. По-

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

На основании полученного единичного покрытия можно записать БФ, реализуемую схемой:

Таблица 5 Анализ схемы методомp – алгоритма.

а) Получение первого покрытия

б) Получение нулевого покрытия

В дальнейшем можно сравнить полученную БФ с той, по которой строилась схема и проверить правильность ее построения.При анализе схемы может оказаться, что некоторая переменная, получившая на одном из предыдущих шагов некоторые значения на данном шаге должна принять противоположное значение. Возникшее противоречие говорит о том, что данный путь является тупиковым и его необходимо исключить из дальнейшего рассмотрения. Если ни при одной комбинации входных переменных не обеспечивается значение 1(0) на выходе, то это означает, что схема реализует константу 0(1) соответственно.

1. 8 Анализ КСметодом синхронногомоделирования.

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

Рассмотрим метод синхронного моделирования на примере схемы ( рис.9 ).

На первом этапе схему разбиваем на уровни и записываем в порядке возрастания уровня уравнения, описывающие функционирование ЛЭ:

№уровня	№элемента	уравнение
1	1 2	e₁= X₁ X₂ e₂=
2	3	e₃ =
3	4	Y =e₄ = e₃ + X₅

Проанализируем схему при подаче на вход набораX₁=0, Х₂=0, Х₃=0, Х₄=1, Х₅=1. Для этого решаем записанные уравнения в порядке возрастания уравнения. Имеем:

Следовательно, при подаче на вход набора {00011}, на выходе будет Y=1. Аналогично можно промоделировать работу схемы при подаче на вход любого другого набора.

1.9Анализ КСметодомасинхронного моделирования.

Реальный ЛЭ переключается за какое-то конечное время, зависящее от технологии изготовления, условий эксплуатации, емкостей нагрузки и т.д. Прохождение сигнала последовательно через несколько ЛЭ будет приводить к накоплению времени задержки и возникновению сдвига во времени выходного сигнала по отношению ко входному. Наличие задержки и порождаемого ею временного сдвига сигналов может приводить к появлению на выходе отдельных ЛЭ и всей схемы в целом кратковременных сигналов, не предусмотренных БФ, реализуемой схемой. Как иллюстрацию, рассмотрим схему рис.11, а .

Рис. 11 а)

Рис. 11 . Статический риск сбоя.

а)- схема, б)- временные диаграммы.

t₁-время задержки инвертора

t₂-время задержки элемента 2И

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

При статическом риске сбоя до и после переходного процесса состояние выходного сигнала одно и то же, а во время переходного процесса возможно кратковременное появление противоположного сигнала.

При динамическом риске сбоя до и после переходного процесса состояния выходного сигнала противоположные, но в переходном процессе выходной сигнал несколько раз меняет свое значение.Динамический риск сбоя возможен в схеме (рис.12 а) при смене набора (Х₁=0, Х₂=1, Х₃=1) на набор (Х₁=1, Х₂=0, Х₃=0) и иллюстрируется диаграммами (рис.12 б).

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

Для анализа процесса переключения КС при смене входных наборов и обнаружения рисков сбоя используется метод асинхронного моделирования. При этом методе считается, что каждый элемент переключается с одинаковой задержкой. Анализ включает такие этапы:

1.Каждому элементу схемы присваивается уровень, причем уровень 1 имеют элементы, все входы которых являются независимыми входами схемы.

2.Записываются уравнения, описывающие каждый ЛЭ в порядке убывания уровня.

3.Для исходного входного набора А(X₁, X₂, … , X_n ) определяется значение сигналов на выходах всех ЛЭ схемы. Пусть данный набор А заменяется набором В(X₁, X₂, … , X_n ).

4.Помечаются те уравнения, в правой части которых хотя бы одна из переменных изменила свое значение.

5.Решаются помеченные уравнения в порядке их записи в схеме . После решения уравнение считается непомеченным.

6.Если после решения всех уравнений системы переменные, входящие в левые части уравнений, изменили свои значения, то вновь помечаются те уравнения, в правые части которых входят эти переменные. Затем осуществляется переход к п.5. В противном случае моделирование данного входного набора считается законченным. Выполнение п.5 называется тактом моделирования.

Анализ схемы (рис.13) методом асинхронного моделирования приведен ниже. Для данной схемы входной набор А(1011110) заменяется набором В(1101011).

Рис. 13. Комбинационная схема для метода асинхронного моделирования.

Уравнения, описывающие ЛЭ:

1-ый такт

2-ой такт

3-ий такт

Y= e₆= e₄+ e₅+ X₅

e₅=e₃₇

e₃=X₅ X₆

e₂=X₅ X₄

e₁=X₁ X₂

Табл. 6 Таблица моделирования схемы

Выходы Такты моделирования Прим.

0 1 2 3

e₆ 1 0 1 0 дин.

e₅ 0 1 0 0 стат.

e₄ 0 0 0 0

e₃ 1 0 0 0

e₂ 1 0 00

e₁ 0 1 01

Как следует из результатов моделирования, при смене набора А набором В на выходе элемента 4 имеет место статический риск сбоя, а на выходе схемы - динамический риск сбоя.

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

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ АБСТРАKТНЫХ АВТОМАТОВ.

Ознакомившись в курсах"Программирование"и "Машинная арифметика"спринципами работы ЭЦВМ,можно указать на две основные особенности таких вычислительных машин:оперирование данными, представленными в цифровой форме и автоматическая работа по заранее составленной программе.Эти особенности показывают, что любая ЭЦВМ является цифровым автоматом (ЦА). Понятие ЦА служит обобщением для всехвидов устройствобработки цифровой информации, имеющих программное управление.

Цифровой автомат - устройство,характеризующееся набором внутреннихсостоянийв которое оно попадет под воздействием команд заложенной в него программы. Переход автомата из одного состояниявдругое осуществляется в определенный момент времени.

Математической модельюЦА (а в общем случае любого дискретного устройства) является так называемый абстрактныйавтомат, определенный как 6-компонентный кортеж: S=(A,Z,W,d,l,а₁)у которого:

1. A={a₁, a₂, ... ,a_m} - множество состояний (внутренний алфавит)

2.Z={z₁, z₂, ... ,z_f} - множество входных сигналов(входнойалфавит)

3.W={w₁, w₂, ..., w_g} - множество выходных сигналов (выходной алфавит)

4. d : A·Z®A - функция переходов,реализующая отображение D_dÍА·Z в А. Иными словами функция d некоторым парам состояние - входной сигнал (а_m, z_f) ставит в соответствие состояния автомата а_s= d (a_m, z_f), a_sÎA.

5. l : A·Z®W - функция выходов,реализующая отображение D_l ÍА·Z на W. Функция lнекоторым парам состояние - входной сигнал (а_m, z_f) ставитв соответствиевыходныесигналы автомата Wg=l(а_m, z_f) , WgÎW.

6.a_iÎA - начальное состояние автомата.

Под алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называются буквами, а конечная упорядоченная последовательность букв - словом в данном алфавите.

Абстрактный автомат (рис.14) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,...В каждый момент t дискретного времени автомат находится в некоторомсостоянии a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном состоянии a(0)=a1. В момент t, будучи в состоянии a(t),автомат способен воспринять на входе букву входного алфавита z(t) ÎZ.В соответствии с функцией выходовон выдаст в тот же момент времени t букву выходного алфавита W(t)=l(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=d[a(t),z(t)], a(t) ÎA, w(t) ÎW.

Смысл понятияабстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z во множество слов выходного алфавита W.Т.е. если на вход автомата,установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1),... - выходное слово. Т.о. выходное слово = j(входноеслово), где j - отображение,осуществляемое абстрактным автоматом.

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

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

На практике наибольшее распространениеполучилидва класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = d(a(t), z(t)); w(t) = l(a(t), z(t)), t = 0,1,2,...

Закон функционирования автомата Мура задается уравнениями:

a(t+1)=d(a(t), z(t)); w(t) = l(a(t)), t = 0,1,2,...

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

Кроме автоматов Мили иМура иногдаоказываетсяудобным пользоватьсясовмещенной модельюавтомата,такназываемым С- автоматом.

Под абстрактным С- автоматом будем понимать математическую модель дискретного устройства, определяемую восьмикомпонентным вектором S=( A, Z, W, U, d, l₁, l₂, а₁), у которого:

1. A={a₁, a₂, ... ,a_m} - множество состояний;

2.Z={z₁, z₂, ... ,z_f}- входной алфавит;

3.W={w₁, w₂, ..., w_g} - выходной алфавит типа 1;

4. U={u₁, u₂,...,u_h} - выходной алфавит типа 2;

5.d : A · Z ® A - функция переходов, реализующая отображение D_dÍА·Z в А;

6. l₁ : A · Z ® W - функция выходов, реализующая отображение D_l₁ÍА·Z вW;

7. l₂ : A ® U - функция выходов, реализующая отображение D_l₂ÍАв U;

8. а₁Î А - начальное состояние автомата.

Абстрактный С- автоматможно представитьввиде устройства с одним входом,на который поступают сигналы из входного алфавита Z,и двумя выходами, на которых появляются сигналы из алфавитов W и U.Отличие С - автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов l₁ и l₂, каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:

а( t + 1) = d( a( t ), z( t )); w( t ) = l₁( a ( t ), z( t )); u( t ) = l₂( a( t )); t = 0, 1, 2, ...

Выходной сигнал U_h=l₂( a_m) выдается все время, пока автомат находится в состоянии a_m. Выходной сигнал Wg=l₁( a_m,z_f) выдаетсяво времядействия входного сигнала Z_f при нахождении автомата в состоянии a_m.

Рассмотренные вышеабстрактные автоматы можно разделить на:

1)полностью определенные и частичные;

2)детерминированные и вероятностные;

3)синхронные и асинхронные;

Полностью определенным называется абстрактныйцифровой автомат,укоторого функцияпереходов ифункция выходов определены для всех пар ( a_i, z_j).

Частичным называется абстрактный автомат,укоторого функция переходов или функция выходов, или обе эти функции определены не для всех пар ( a_i, z_j).

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов :автомат, находящийся в некотором состоянии a_i,под действием любого входного сигнала z_j не может перейти более, чем в одно состояние.

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

Для определения синхронных и асинхронных автоматоввводится понятие устойчивого состояния. Состояние a_s автомата называетсяустойчивым, еслидлялюбого состояния a_iи входногосигналаz_jтаких, что d( a_i, z_j) = a_s имеет место d( a_s, z_j) = a_s, т.е. состояние устойчиво, еслипопав вэто состояние под действием некоторого сигнала zj, автомат выйдет из него только под действием другого сигнала z_k, отличного от z_j.

Автомат, у которого все состояния устойчивы -асинхронный.

Автомат называетсясинхронным,если онне является асинхронным.

Абстрактный автомат называетсяконечным,если конечны множества А = {a₁, a₂, ..., a_m}, Z = {z₁, z₂, ..., z_f}, W = {w₁, w₂, ..., w_g}.Автомат носит название инициального, если в нем выделено начальное состояние a₁.

СПОСОБЫОПИСАНИЯИ ЗАДАНИЯАВТОМАТОВ.

Для того, чтобы задать автомат,необходимо описать все компоненты кортежа S=(A, Z, W, d, l, а₁).Множества А, Z, W описываются и задаются простым перечислениемсвоихэлементов. Среди многообразияразличных способов заданий функций d и l ( следовательно и всего автомата в целом) наибольшеераспространение получили табличный и графический.

При табличном способе задания автомат Мили описывается с помощьюдвухтаблиц. Одна из них (таблица переходов ) задает функцию d, т.е. a( t +1) = d( a( t ), z( t ))( табл.7), вторая (таблица выходов ) - функцию l, т.е. W( t )=l( a( t ), z( t )) ( табл. 8).

Каждому столбцу из приведенных таблиц поставлено в соответствие одно состояние из множества А, каждой строке -один входнойсигнал измножества Z.На пересечении столбца a_m и строки z_f в табл.7 записывается состояние a_s, в которое должен перейти автомат из состояния a_m под действием входного сигнала Z_f, т.е.a_s= d(a_m, z_f).На пересечении столбца a_m и строки z_f в табл.8 записывается выходной сигнал Wg, выдаваемый автоматом в состоянииa_mпри поступлениинавход сигналаz_f, т.е.Wg = l( a_m, z_f).

Для приведенных таблицмножества,образующие автомат A={a₁, a₂, a₃,a₄}, Z={z₁, z₂}, W={w₁, w₂, w₃, w₄, w₅}.Автомат Мили может быть задан одной совмещенной таблицейпереходов и выходов(табл.9),в которой каждый элемент a_s/ w_g записанный на пересечении столбца a_mистрокиz_f,определяется следующим образом:

a_s=d(a_m, z_f); w_f=l(a_m, z_f).

Автомат Мура задается одной отмеченной таблицейпереходов(табл.10), вкоторой каждому столбцу приписаны не только состояние a_m, но еще и выходной сигнал Wg, соответствующий этому состоянию, где Wg=l(a_m).

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

Для задания С - автоматов также используется табличный метод.В этом случае таблица переходов (табл.11) аналогична таблице переходов автоматаМили, автаблице выходовкаждое состояние отмечено соответствующим выходным сигналом u_i выходного алфавита типа 2 (табл.12)

При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины a_m, задает переходв автомате из состояния a_m в состояние a_s.В начале этой дуги записывается входной сигнал Z_fÎZ,вызывающий данныйпереход a_s=d(a_m,z_f).Для графа автомата Мили выходной сигнал w_gÎW, формируемый на переходе, записывается в конце дуги,а дляавтоматаМура - рядом с вершиной a_m, отмеченной состоянием a_m, в котором он формируется. Если переход в автоматеиз состояния a_m в состояние a_s производится под действием нескольких входных сигналов,то дуге графа, направленной из a_m в a_s,приписываются всеэти входные и соответствующие выходные сигналы. Граф С- автомата содержит выходные сигналы двух типов и ониобозначаются на графе как на графах соответствующих автоматов.Графы автоматов, заданных своими таблицами переходов и выходов
(табл. 7¸12)представлены нарисунках15,16,17.

СВЯЗЬ МЕЖДУМОДЕЛЯМИМИЛИ ИМУРА.

Рассмотрим некоторыйавтомат Мили,заданный таблицами переходов и выходов. Таблица переходов а) и выходов б) автомата Мили

Подадим на вход автомата, установленного в состояние а₁, входное слово x=z₁ z₂ z₂ z₁z₂ z₂. Так как d(а₁, z₁) = a₂, l(a₁, z₁) = W₂,топод воздействием входного сигнала z₁ автомат перейдет в состояние а₂ и выдаст на переходевыходной сигнал W₂. Затем, находясь в состоянии а₂ под воздействием сигнала Z₂ перейдет в состояние а₁=d(а₂, z₂) и выдаст сигнал W₁=l(a₂, z₂) и т.д. В табл. 13 приведена последовательность состояний, которые автомат проходит,воспринимая входное слово x, и выходные сигналы, вырабатываемые на этих переходах.

Назовем выходное слово w = l (a_1,x) реакцией автомата Мили в состоянии а₁ на входное слово x.

В нашем случае w = w₂ w₁ w₂ w₂ w₁ w₂

Как видно, из приведенного примера,в ответ навходное слово длины k автомат Мили выдаст последовательность состояний длины k +1 и выходное слово длины k.

В общемвиде поведение автомата Мили,установленного в состояние a_m, можно описать следующим образом (табл. 14).

Аналогично можно описать поведение автомата Мура,находящегося в состоянии a₁, при приходевходногослова

x = Z_i1, Z_i2, . . . , Z_ik,учитывая,что W( t ) = l(a( t )):

Входное слово	Z_i₁	Z_i2	Z_i3	Z
Последовательность cостояний	a_m	a_i2 = d (a_m, Z_i1 )	a_i3 = d (a_i2, Z_i2 )	a_i4 = d(a_i3, Z_i3 )
Выходное слово	w_i₁ = l (a_m_,Z_i₁)	w_i2 = l (a_i2,Z_i2)	w_i3 = l (a_i3,Z_i3)	w_i4 = l (a_i4)

Очевидно, что для автомата Мура выходнойсигнал W_i₁= l(a_m) в момент времени i₁ не зависит от входного сигнала Z_i₁ и определяется только состоянием a_m. Следовательно, сигнал W_i₁ никак не связан с входным словом x.

В связи с этим под реакцией автомата Мура, установленного в состояние a_m,на входное словоx = Z_i₁, Z_i₂, . . . , Z_ikбудем понимать выходноесловотойже длины w = l(a_m, x) = W_i₂ W_i₃ ...W_ik₊₁, сдвинутое по отношению к x на один такт.

Рассмотрим пример. Пусть задан автомат Мура:

Подадим на вход этого автомата туже последовательность, что и для автомата Мили: x=z₁ z₂ z₂ z₁z₂ z₂.Последовательность смены состояний и вырабатываемых выходных сигналов представлена в таблице:

	w₁	w₂	w₃	w₄
	a₁	a₂	a₃	a₄
z₁	a₂	a₃	a₄	a₄
z₁	a₄	a₁	a₁	a₁

Сравнивая реакции автоматаМили(табл. 13) иавтоматаМура (табл.15), отмечаем,что эти реакции на одно и тоже словоx совпадают. Следовательноавтоматы Мили и Мура реализуют одно и то же преобразование слов входного алфавита. Такие автоматы называются эквивалентными. Строгое определениеэквивалентности следующее:

два автомата содинаковымивходными и выходными алфавитами называются эквивалентными,если после установки их вначальное состояние их реакции на любое входное слово совпадают.

Для каждого автомата Мили можетбытьпостроен эквивалентный ему автомат Мура и наоборот.

Переход от автомата Мура к эквивалентномуему автомату Милитривиален и легко осуществляется при графическом способе задания автомата. Для получения графа автомата Мили необходимо выходнойсигнал Wg,записанный рядом с вершиной a_s исходного автомата Мура,перенести на все дуги,входящие в эту вершину.На рис. 18 приведен граф автомата Мили, эквивалентного автомату Мура (рис. 16)

Легко убедиться, что полученный автомат Мили действительно эквивалентный исходному автомату Мура. Для этого достаточно рассмотреть реакцию обеих автоматов на произвольную входную последовательность,чтопредлагается выполнитьсамостоятельно.Необходимо такжеотметить, что в эквивалентном автомате Мили количество состояний такое же,как и в исходном автомате Мура.

Переход от автомата Мили к эквивалентномуему автомату Мураболее сложен.Это связано с тем,что в автомате Мура в каждом состоянии вырабатывается только одинвыходнойсигнал. Какив предыдущем случае,переход наиболее наглядно делать при графическом способе задания автомата. В этом случае каждое состояние a_i исходного автомата Мили порождает столько состояний автомата Мура,сколько различных выходных сигналов вырабатываетсявисходном автоматепри попадании в состояние a_i.Рассмотрим переход от автомата Мили Sa к автомату Мура S_bна примере автомата (рис. 15).

Как следует из рис. 15 для автомата Saпри попаданиив состояние а₁ вырабатываются выходные сигналы W₂, W₄, W₅, при попадании в а₂ – W₁, W₂,a₃ – W₂, a₄ – W₃. Каждой паре состояниеa_i - выходной сигнал Wj,который вырабатывается при попадании в это состояние, поставим в соответствие состояние b_k эквивалентногоавтомата МураS_bс темже выходным сигналом Wj : b₁= (a₁, W₂),b₂= (a₁, W₄),b₃= (a₁, W₅),b₄= (a₂, W₁), b₅= (a₂, W₂), b₆=(a₃, W₂), b₇= (a₄, W₃), т.е. каждое состояние a_i автомата Мили порождает некоторое множество A_i состояний эквивалентного автомата Мура:A₁= { b₁, b₂, b₃ }, A₂= { b₄, b₅ }, A₃= { b₆ },A₄= { b₇ }. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа S_b поступаем следующим образом.Т.к. в автомате S_a есть переход из состояния а₁ в состояниеа₂ под действием сигнала z₁ с выдачей W₁,то из множества состояний A₁= {b₁, b₂, b₃},порождаемых состояниема₁ автоматаS_aв автоматеS_bдолжен быть переход в состояние (a₃, W₂) = b₆ под действием сигнала Z₂ и т.д. Граф эквивалентного автомата Мура представлен на рис.19.

Если от автомата Мура S_b,эквивалентного автомату Мили Sa (рис. 19) вновь перейти к автомату Мили, то получим автомат Мили S₁ (рис. 20)

Вследствие транзитивностиотношения эквивалентности два автомата Мили S₁ и Sa также будут эквивалентными, но у последнегобудут на 3 состояния больше.Т.о., эквивалентные между собой автоматы могут иметь различное число состояний,в связи счем возникает задача нахождения минимального (т.е.с минимальным числом состояний) автомата в классе эквивалентных между собойавтоматов.

МИНИМИЗАЦИЯЧИСЛА ВНУТРЕННИХ СОСТОЯНИЙ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ АВТОМАТОВ.

Рассмотрим метод минимизации полностью определенныхавтоматов, предложенный Ауфенкампом и Хоном.

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

Для пользования методом введем несколько определений.

Два состояния абстрактного автомата называются 1-эквивалентными в том случае, если реакции автомата в этих состояниях на всевозможные входные слова совпадают.

Объединение всех 1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.

1-эквивалентные состоянияавтомата называются 2-эквивалентными,если они переводятся любым входным сигналом также в 1-эквивалентные состояния.

Объединение всех 2-эквивалентных состояний образует 2-класс эквивалентности.

По индукции можно распространить определение доi-эквивалентных состояний и i-классов эквивалентности.

Если для некоторого i разбиениясостояний автоматана ( i +1) - классы совпадает с разбиением на i-классы,то оно является разбиением и на ¥ - классы эквивалентности.

Разбиение множества внутреннихсостоянийавтомата на ¥ - классы и является требуемым разбиениемнаклассы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.

Все вышеизложенное непосредственно применимо к минимизации автомата Мили.При минимизации полностью определенных автоматов Муравводитсяпонятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы: к такомуклассу относятся одинаково отмеченные состояния автомата Мура.

Если два 0-эквивалентных состояния любым входным сигналом переводится в два 0-эквивалентных состояния,то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автомата Мура определяются аналогично приведенному для автоматов Мили.

Рассмотрим пример минимизации автоматаМили, заданного таблицами переходов и выходов :

Из таблицывыходов получаем разбиение на 1-классы эквивалентности p₁, объединяя в эквивалентные классы Bi состояния с одинаковыми столбцами:

p₁ = {B₁, B₂}; B₂= {a₁, a₂, a₅, a₆}; B₂= {a₃, a₄}

Для получения 2-эквивалентных состоянийстроим таблицу 1-разбиения (табл.17),заменяя в таблице переходов состояния a₁ соответствующими классами эквивалентности B1 или B2.

Из полученной таблицы 1-разбиения получаем 2-классыэквивалентностиC_iи разбиение p₂= {C₁, C₂, C₃},где С₁= {a₁, a₁}, C₂= {a₅, a₆}, C₃= {a₃, a₄}.Сравнивая p₂ и p₁, отмечаем, что эти разбиения отличаются друг от друга. Поэтому аналогично строим таблицу 2-разбиения (табл. 18), опять заменяя в таблице переходов состояния a_i соответствующими классами эквивалентности C_i.

Из полученной таблицы 2-разбиения получаем 3-классы эквивалентности D_i и разбиение p₃={ D₁, D₂, D₃},гдеD₁= {a₁, a₂}, D₂= {a₅, a₆}, D₃= {a₃, a₄}.

Сравнивая p₃ и p₂,замечаем, что D₁= C₁, D₂= C₂, D₃= C₃, p₃= p₃.Следовательно получилиразбиение на ¥- эквивалентные классы.Т.к. всего три таких класса,то минимальный автомат будетсодержатьвсего трисостояния.Выбираем из каждого класса D_i по одному состоянию и получаеммножествосостояний A' минимального автомата.Пусть, например, A'={a₁, a₄, a₅}. Для получения минимального автомата из первоначальных таблиц переходов и выходов (табл. 16) вычеркиваем столбцы, соответствующие "лишним состояниям" a₂, a₃, a₆.В результате получаетсяминимальный автомат Мили, эквивалентныйисходному автомату (табл. 19).

Минимизацией числа внутренних состояний автомата заканчивается этап абстрактного синтеза.

Структурный синтез ЦА.

Задачи синтеза ЦА.

Канонический метод структурного синтеза ЦА.

Элементарные цифровые автоматы с памятью

(триггерные устройства) и их свойства.

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

В отличие от абстрактного автомата,имеющего одинвходи один выход, на которые поступают сигналы во входноми выходят в выходном W={W₁,..,W_G} алфавитах, структурный автомат имеет L входных каналов х₁,х₂,..,х_L и N выходныхy₁,y₂,…,y_N на каждом из которых присутствует сигнал структурного алфавита.

Обычно в качестве структурного используется двоичный алфавит.

В этом случае каждому входному сигналу Z_F абстрактного автомата соответствует некоторый двоичный вектор (l_f₁,l_f₂,..,l_f_L), где l_f_LÎ{0,1}.

Очевидно, что для представления (кодирования) входных сигналовZ₁,..,Z_Fабстрактного автомата различными двоичными векторами должно быть выполнено условие

L ] log₂F [,

аналогично

N ] log₂G [

Например , Z={Z₁,Z₂,Z₃,Z₄} W={W₁,W₂,W₃}.

ТогдаL log₂4=2N log₂3=2

Закодировать входные и выходные сигналы можно ,например, так:

Z₁ = 00 W₁ = 00

Z₂ = 01 W₂ = 01

Z₃ = 10 W₃ = 11

Z₄ = 11

Cледовательно, структурный автомат с двумя входами x₁ и x₂и двумя выходами y₁иy₂ может быть представлен в виде:

Задача синтеза структуры автомата.

На этапе структурного синтеза предварительно выбираютсяэлементарные автоматы, путем композиции которых строят логические схемы полученных на этапе абстрактного синтеза автоматов Мили и Мура. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.

Рассмотрим канонический метод структурного синтеза при котором используются элементарные автоматы некоторого специального вида –автоматы с памятью, имеющие более одного состояния, и автоматы без памяти – с одним состоянием.Первые автоматы называются элементами памяти, вторые – комбинационные или логические элементы.

Теоретическим обоснованием канонического метода структурного синтеза автоматов служит теорема о структурной полноте:

Для правильной работы схем сигналы на входе запоминающих элементов не должны непосредственно участвовать в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. Поэтому запоминающими элементами должны быть не автоматы Мили, а автоматы Мура. Такимобразом, структурнополная система элементарных автоматов должна содержать хотя бы один автомат Мура. В то жевремя, для синтеза автоматов с минимальным числом элементов памяти, необходимо в качестве таких элементов выбирать автоматы Мура,имеющие полнуюсистему переходов и полную систему выходов –полные автоматы.

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

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

Канонический метод структурного синтеза предполагает представление структурной схемы автомата в виде двух частей: памяти и комбинационной схемы.

Память состоит из элементарных автоматов Мура П₁,....,П_Z,....,П_R. После выбора элементов памяти каждое состояние синтезируемого автомата А кодируется набором их состояний. Если все автоматы П₁...,П_R одинаковы, что в общем случае необязательно, то их число

где M – число состояний синтезируемого автомата А, а b – число состояний элементарного автомата памяти. Обычно для элементарного автомата b=2, тогда

Например, переход автомата А, имеющего 5 элементов памяти, алфавит состояний которых – двоичный, из одного состояния (A_m)=01011в другое (A₃)= 11000,заключается в изменении состояний соответствующих автоматов памяти: первый элемент памяти переходит из 0 в 1, второй – из 1 в 1, третий из 0 в 0, четвёртый – из1 в 0, пятый - из 1 в 0.

Переходы автоматов памяти, соответствующие переходам в автомате А,происходят под действием сигналов возбуждения памяти, поступающих с выхода комбинационной схемы на вход памяти автомата. Так на рисунке X=(X₁,X₂,..,X_L) и Y=(Y₁,Y₂,...,Y_N) – векторные структурные входной и выходной сигналы автомата, U=(U₁,U₂,...,U_T)– векторнаяфункциявозбуждения памяти иQ=(Q₁,...,Q_T)– вектор выходного сигнала обратной связи от элементов памяти автомата.

Рассмотрим отдельноэлемент памяти П_z,таблица переходов которого дана в таблице.Множество выходных сигналовэлементов памяти совпадает с множеством внутренних состояний.

Полнота переходов очевидна из таблицы (в каждом столбце все состояния встречаются). Прирассмотрении автомата на абстрактном уровне его можно представить в виде рис.22 а.

При переходе от абстрактного автомата к структурному, входные и выходные сигналы должны быть закодированы наборами сигналов структурного алфавита(входного или выходного соответственно). При двоичном структурном алфавите автомат П_z будет иметь два входных и два выходных канала.

Итак, сами компоненты U_z и Q_z приZ = 1,...,Rвекторов сигналов возбуждения памяти U и сигналов обратной связи отпамяти Q также могут быть представлены в виде векторов:

U_z= (U_Z1,U_Z2,...,U_Z_K)иQ_Z= (Q_Z₁,Q_Z₂,...,Q_Z_R).

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

При построении функций возбуждения памяти автомата используют функцию входов элемента памяти m(b_i,b_j),ставящую в соответствие каждой паре состояний (b_i,b_j) сигнал, который должен быть подан на вход этого автомата для перевода его из состояния b_i в состояние b_j. Функцию входов удобно задавать в виде таблицы. Для элемента памяти (функция переходов которого приведена ранее) функция входов имеет вид:

Если входные сигналы элемента памяти q₁,...,q_p закодированы наборами (U_Z₁,...,U_Z_K) сигналов на его входных каналах, то элементами таблицы, задающей функцию входов вместо q_i будут соответствующие наборы. Так, если q₁= 00, q₂ = 01, q₃ = 10, то соответствующая f входов будет иметь вид рис.23a.

Элементарные цифровые автоматы – элементы памяти.

В качестве элементов памяти структурного автомата обычно используются триггеры.

Триггер – это устройство, имеющее два устойчивых состояния, в которые он переходит под действием определённых входных сигналов.

Обычно в триггерах выделяют два вида входных сигналов (и соответственно входов): информационные и синхросигналы.

Информационные сигналы определяют новое состояние триггера и присутствуют в любых триггерах. По типу информационных сигналов осуществляется классификация триггеров:D,T, RS, JK, RST, DV и т.д.

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

На синхровход триггера поступают тактирующие импульсы задающего генератора, синхронизирующего работу ЦА. Период следования импульсов соответствует одному такту автоматного времени ЦА.

Рассмотрим основные типы триггеров, используемые для синтеза ЦА: D, T, RS, JK.

D-триггер – элемент задержки – имеет один информационный входDи один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт.

Условное обозначение и таблица переходов D-триггера представлена на рис..

D	Q ^t	Q^t⁺¹
0	0	0
0	1	0
1	0	1
1	1	1

Таблица переходов D-триггера.

Рис. 24.

Из приведеннойтаблицыпереходов дляданноготриггера Q^t+1= f(Q^t,D^t) можно получить таблицу функций его входов D^t = j(Q^t, Q^t+1).

Q ^t

Q^t+1

D^t

Таблица функции входов D-триггера.

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

K155TM2 (рис. 25).Таких триггеров два в одном корпусе. Вход С –вход синхронизации, Q,`Q – выходы,Q – прямой, – инверсный. R, S –входы установки в 0 и 1 соответственно. При подаче на вход R и S логического нуля триггер устанавливается в соответствующие состояния независимо от сигнала на входах DиC.

T-триггер – триггер со счетным входом – имеет один информационный вход Т и одинвыход Qи осуществляет суммирование по модулю два значений сигнала T и состояния Q в заданный момент времени.

Условное обозначение и таблица переходов T-триггера представлена на рис 26.

T	Q ^t	Q^t⁺¹
0	0	0
0	1	1
1	0	1
1	1	0

Таблица переходов T-триггера.

Таблица функцийвходовтриггера T^t = f(Q^t, Q^t+1) представлена в таблице.

Q ^t

Q^t+1

T^t

Таблица функции входов T-триггера.

На основании этой таблицы можно получать функцию возбуждения элементов памяти при синтезе автомата на базе T-триггера. Например, если автомат перешел из состояния a_i = 010 всостояниеa_j=110, то для обеспечения этого перехода функции возбуждения должныбыть:

дляпервого триггерапри переходе из 0 в 1 T₁ = 1,

для второго триггера при переходе из 1 в 1 T₂ = 0,

для третьего триггера при переходе из 0 в 0 T₃ =0и т.д.

В чистом виде промышленность не выпускает T-триггера.

RS-триггер – триггер с раздельными входами.

Данный триггер имеет два входных канала R и S и один выходной Q. Вход S(set) называется входом установки в единицу, вход R (reset) – входом установки в нуль. Условное обозначение и таблица переходов RS-триггера представлена на рис. 27.

В таблицепереходов приподаче комбинации S = R = 1 состояниепереходаQ^t+1не определено и эта комбинация сигналов является запрещенной для RS-триггера.

Таблицу переходовможноболее компактноизобразить в виде (см.табл. 21б) Анализируя табл.21 б,в отмечаем что, например, переход триггераиз 0 в 0требует подачи комбинации R=0,S=0 или R=1,S=0, т.е. можно сказать что этот переход будет при R=X (безразличное состояние) , S=0.

Аналогично рассуждая поотношениюк другимпереходам получим следующую таблицу функций входов.

R	S	Q ^t	Q^t+1		R	S	Q^t+1
0	0	0	0		0	0	0
0	0	1	1		0	1	1
0	1	0	1		1	0	0
0	1	1	1		1	1	–
1	0	0	0				б)
1	0	1	0
1	1	0	–
1	1	1	–	а)

Таблица переходов RS-триггера.

RS-триггер

Рис. 27.

Таблица функций входовRS-триггера.

в)

Табл 21. а), б), в).

Q ^t	Q^t+1	R^t	S
0	0	X	0
0	1	0	1
1	0	1	0
1	1	0	X

На основании таблицы можно получить функцию возбуждения памяти автомата при синтезе на базе RS-триггеров. Например, если автомат переходит из состояния a_i= 010 в состояние a_j=110, то для обеспечения такого перехода функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 R₁ =0,S₁ = 1;

для второго триггера при переходе из 1 в 1 R₂ =0,S₂ = X;

для третьего триггера при переходе из 0 в 0 R₃ =X,S₃= 0.

Аналогично для любого другого перехода автомата.

В чистом виде синхронный RS - триггер,используемый для синтеза ЦА, промышленностью не выпускается.

JK- триггер – имеет два информационных входа J и K и один выход Q. Вход J – вход установки в 1,вход K – вход установки в 0,т.е. эти входы аналогичны соответствующим входам RS-триггера:J – соответствует S, K – соответствует R. Однако, в отличие от RS-триггера, входная комбинация J = 1, K= 1 не является запрещённой.Условное обозначение и таблица переходов JK-триггера представлены на рис.28. и в табл. 22.

J	K	Q ^t	Q^t+1		J	K	Q^t+1
0	0	0	0		0	0	Q ^t
0	0	1	1		0	1	0
0	1	0	0		1	0	1
0	1	1	0		1	1	Q ^t
1	0	0	1				б)
1	0	1	1
1	1	0	1
1	1	1	0	а)

JK-триггер

Таблица переходов JK-триггера.

Рис. 28.

Табл. 22 а), б).

Как следует из таблиц переходов, для комбинаций входных сигналов JK = 00¸10 триггер ведет себя как RS-триггер, а при комбинации JK = 11 – как T-триггер.

Анализируя таблицупереходов ( табл. 22 а), отмечаем, что переходтриггера, например,из 0 в 1 требует подачи входных сигналов J=1,K=0 или J=1,K=1,т.е. J=1, K=Х (безразличное значение). Аналогично рассуждая поотношению кдругим переходам, получим следующую таблицу функций входов JK-триггера.

Q ^t	Q^t+1	J	K
0	0	X	0
0	1	1	X
1	0	X	1
1	1	0	X

Таблица функций выходовJK-триггера.

На основаниипоследнейтаблицы можно получить функцию возбуждения элементов памяти при синтезе автомата на JK-триггерах. Например, при переходе автомата из состояния a_i=010 в состояние a_j=110, функции возбуждения должны быть:

для первоготриггера при переходе из 0 в 1 J1 = 1, K1 = X;

для второготриггера при переходе из 1 в 1 J2 = X,K2 = 0;

для третьего триггера при переходе из 0 в 0 J3 = 0, K3 = X.

Пример канонического метода структурного синтеза автомата.

Выполним структурный синтез частичного автомата А, заданного своими таблицами переходов и выходов (табл. 23 и 24.).

Синтез будем выполнять в следующем порядке:

1. Выберем в качестве элементов памяти D-триггер, функция входов которого представлена в таблице стр. 33.

2. Закодируем входные, выходные сигналы и внутренние состояния автомата. Количество входных абстрактных сигналов F = 3, следовательно количество входных структурных сигналовL= ]log₂F [ = ]log₂3[ = 2, т.е. х₁, х₂.

Количество выходных абстрактных сигналов G = 4, следовательно количество выходных структурных сигналов N =]log₂G[ = ]log₂4[ = 2,т.е. у₁, у₂. Количество внутренних состояний абстрактного автомата M = 4,следовательно количество двоичных элементов памяти (триггеров) R = ] log₂M [ = ]log₂4[ = 2.

Следовательно, структура ЦА с учетом того, что исходный автомат является автоматом Мили, в качестве элементов памяти используется D-триггер, может быть представлена в виде(рис. 29):

Кодирование входных, выходных сигналов и внутренних состояний представлена в таблицах:

	x₁	x₂			y₁	y₂			Q₁	Q₂
z₁	0	0		w₁	0	0		a₁	0	0
z₂	0	1		w₂	0	1		a₂	0	1
z₃	1	1		w₃	1	1		a₃	1	1
		w₄	1	0		a₄	1	0

Кодирование, в общем случае, осуществляется произвольно. Поэтому, например,каждому из сигналов Z_i можно поставить в соответствие любую двухразрядную комбинацию х₁, х₂. Необходимо только, чтобы разные выходные сигналы Z_i кодировались разными комбинациями х₁, х₂. Аналогично для W_i и a_i.

3. Получим кодированные таблицы переходов ивыходов структурного автомата. Дляэтого в таблицах переходов и выходов исходного абстрактного автомата вместо Z_i, W_i, a_icтавим соответствующие коды. Получим таблицы:

x₁x₂

Q₁Q₂

x₁x₂

Q₁Q₂

Рис. 30 .

Кодированная таблица переходов.

Рис. 31 .

Кодированная таблица выходов

a₁

a₂

a₃

a₄

a₁

a₂

a₃

a₄

Z₁

–

Z₁

–

Z₂

–

Z₂

–

Z₃

–

Q₁Q₂

Z₃

–

y₁y₂

В кодированной таблице переходов заданы функции

В кодированной таблице выходов заданны функции:

4. При каноническом методе синтез сводится к получению функций:

и последующем построении комбинационных схем, реализующих данную систему булевых функций.

Функции у₁ и у₂ могут быть непосредственнополучены из таблицы выходов, например, в виде :

Однако выражения для у₁ и у₂ можно существенно упростить в результате минимизации, например, с помощью карт Карно:

	00	01	11	10		00	01	11	10
00	0	0	1	–	00	1	0	1	–
01	–	1	0	–	01	–	1	0	–
11	0	–	1	0	11	0	–	0	1
10	–	–	–	–	10	–	–	–	–

x₁x₂

Q₁Q₂

x₁x₂

Q₁Q₂

Рис. 32 .

Карта Карно для у₁.

Рис.33.

Карта Карно для у₂.

В результатеминимизацииимеем:

Для получения выражений для D₁ и D₂ необходимо получить таблицы функций возбуждения. Для чего в общем случае необходимо воспользоваться таблицей переходов и функциями входов элементов памяти. Зная код исходного состояния автомата и код

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

x₁x₂

Q₁Q₂

x₁x₂

Q₁Q₂

Рис. 34 .

Карта Карно для D₁.

Рис.35.

Карта Карно для D₂.

–

В результате минимизации получаем:

5. На основании полученных в результате синтеза булевых выражений((*),(**)) ,строим функциональную схему автомата. Для этого уравнения ((*), (**)) представим в виде:

Функциональная схема автомата представлена на странице 41:

Дополнительно нафункциональнойсхеме показансигнал устанавливающий автомат в начальное состояние (в данном случае 00).

Особенности синтеза автоматов на базе T, RS, JK триггеров.

Необходимо отметить, что синтез на базе указанных типов триггеров осуществляется аналогично выполненному синтезу на базе D-триггеров. В частности, п. 1¸3 (см. предыдущий параграф) абсолютно аналогичны. Кроме того, как следует из п.4 (см.предыдущий параграф) выходные сигналы не зависят от типа триггеров, поэтому выражение дляy_iбудут одинаковыми для любого типатриггеров. Однако функции возбуждения будут различны для разных типов триггеров и получаются на основании таблицы переходов исходного автомата и функции входов выбранного триггера. Без особыхпояснений нижеприведены таблицы функций входов,функций возбуждений и карты Карно для минимизации функций возбуждения при использовании длясинтеза автомата предыдущего параграфа T-, RS-, JK-триггеров.

T-триггер.

Q ^t	Q^t+1	T^t
0	0	0
0	1	1
1	0	1
1	1	0

Таблица функции входов T-триггера.

Таблица функций возбуждения.

x₁x₂

Q₁Q₂

	00	01	11	10
00	00	11	01	–
01	–	10	11	–
11	01	–	10	01

	00	01	11	10		00	01	11	10
00	0	1	0	–	00	0	1	1	–
01	–	1	1	–	01	–	0	1	–
11	0	–	1	0	11	1	–	0	1
10	–	–	–	–	10	–	–	–	0

Карта Карно для Т₁.

Карта Карно для Т₂.

x₁x₂

Q₁Q₂

x₁x₂

Q₁Q₂

RS-триггер.

Q ^t	Q^t+1	R	S
0	0	X	0
0	1	0	1
1	0	1	0
1	1	0	X

Таблица функции входовRS-триггера.

Таблица функций возбуждения.

x₁x₂

Q₁Q₂

	00	01	11	10
	R₁	S₁	R₂	S₂	R₁	S₁	R₂	S₂	R₁	S₁	R₂	S₂	R₁	S₁	R₂	S₂
00	X	0	X	0	0	1	1	0	0	X	1	0	–	–
01	–	–	0	1	0	X	1	0	1	0	–	–
11	X	0	0	1	–	–	1	0	0	X	0	X	0	1

x₁x₂

Q₁Q₂

x₁x₂

Q₁Q₂

x₁x₂

Q₁Q₂

x₁x₂

Q₁Q₂

–

	00	01	11	10		00	01	11	10
00	X	1	1	–	00	0	0	0	–
01	–	0	1	–	01	–	X	0	–
11	0	–	0	0	11	1	–	X	1
10	–	–	–	–	10	–	–	–	–

JK-триггер.

Q ^t	Q^t+1	J	K
0	0	0	X
0	1	1	X
1	0	X	1
1	1	X	0

J₁

K₁

J₂

K₂

J₁

K₁

J₂

K₂

J₁

K₁

J₂

K₂

J₁

K₁

J₂

K₂

–

	00	01	11	10		00	01	11	10
00	0	1	X	–	00	X	X	0	–
01	–	1	X	–	01	–	X	1	–
11	0	–	X	X	11	X	–	1	0
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	X	X	–	00	X	1	1	–
01	–	X	X	–	01	–	0	1	–
11	X	–	1	0	11	0	–	0	X
10	–	–	–	–	10	–	–	–	–

Карта Карно для J₂.

Карта Карно для K₂.

x₁x₂

Q₁Q₂

x₁x₂

Q₁Q₂

Функциональные схемы автоматов с различными типами триггеров предлагается построить самостоятельно.

Кодирование внутренних состояний ЦА.

Гонки в автомате.

Кодирование заключается в сопоставлении каждому состоянию автомата набора (кода) состояний элементов памяти. При этом наборы для всех состояний должны иметь одинаковую длину, а разным состояниям автомата должны соответствовать разные наборы. Если элементы памяти двоичные, то их число

Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Если автомат переходит из состояния с кодом 010 в состояние с кодом 100, то это означает, что триггер V₁ переходит из состояния 0 в состояние 1,V₂ – из 1 в 0, V₃ – сохраняет свое состояние.

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

Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания. Тот элемент, который выиграет эти состязания, т.е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие, участвующие в состязаниях элементы, изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное его графом.Поэтому в процессе перехода из состояния a_m в состояние a_s под действием входного сигнала Z_f автомат может оказаться в состоянии a_k или a_l: (рис.36.).

Если затем при том же входном сигнале Z_f автомат из а_k и а_l перейдет в а_s, то такие состязания являются допустимыми или некритическими.

Если же в этом автомате есть переход, например,из а_k в а_j¹а_s под действием того же сигнала Z_f, то автомат может перейти в а_j, а не в а_s и правильность его работы будет нарушена (рис.37.).

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

Устранить гонки можно аппаратными средствами либо используя специальные методы кодирования. Один изспособов ликвидации гонок состоит в тактированиивходных сигналовавтомата импульсами определенной длительности. Предполагается, что кроме входных каналов х₁,...,х_lимеется еще канал С от генератора синхроимпульсов, по которому поступает сигнал С = 1 в момент прихода импульса и С = 0 при его отсутствии. В связи с этим входным сигналом на переходе (a_m, a_s) будет не Z_f, а CZ_f.Тогда, если длительность импульса t_c меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационнойсхеме, то к моменту перехода в промежуточное состояние a_k сигнал C = 0, CZ_f=0, что исключает гонки. Канал С – это фактически синхровход триггера. Недостаток метода – в трудности подбора требуемой длительности импульса, т.к. она зависит от многих факторов, не поддающихся строгому учету.

Другой способ ликвидации гонок заключается во введении двойной памяти. В этом случае каждый элемент памяти дублируется, причем перепись из первого элемента памяти во второй происходит в момент С = 0(рис.38.).

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

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

Соседнее кодирование не всегда возможно. Граф автомата, допускающее соседнее кодирование, должен удовлетворять ряду требований, а именно:

1) в графе автомата не должно быть циклов с нечетным числом вершин;

2) два соседних состояния второго порядка не должны иметь более двух состояний, лежащих между ними.

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

При соседнем кодировании обычно пользуются картой Карно. В этом случае состояния,связанные дугой, располагают на соседних клетках карты (рис.40.).

Легко видеть, что при соседнем кодировании на каждом переходе переключается только один триггер, что принципиально устраняет гонки.

Кодирование состояний и сложность комбинационной схемы автомата.

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

1) алгоритм кодирования для D-триггеров;

2) эвристический алгоритм кодирования.

Алгоритм кодирования для D-триггеров.

Согласно рассматриваемому алгоритму при кодировании необходимо выполнить следующее:

1. Каждому состоянию автомата а_m (m = 1,2,...,M) ставится в соответствие целое число N_m,равное числу переходов в состояние а_m (N_mравно числу появлений а_m в поле таблицы переходов или числу дуг, входящих в а_m при графическом способе задания автомата).

2. Числа N₁, N₂, ..., N_m упорядочиваются по убыванию.

3. Состояние а_s с наибольшим N_s кодируется кодом:R-количество элементов памяти.

4. Следующие R состояний согласно списка пункта 2 кодируются кодами, содержащими только одну1: 00 ... 01,00 ... 10,... , 01 ... 00, 10 ... 00.

5. Для оставшихся состояний опять в порядке спискап.2. используют коды с двумя единицами, затем с тремя и так далее пока не будут закодированы все состояния.

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

В частности, для автомата, заданного своими таблицами переходов и выходов (см. ниже)при кодировании на базе D-триггеров.

a₁

a₂

a₃

a₄

a₅

a₁

a₂

a₃

a₄

a₅

Z₁

a₁

a₅

a₃

a₁

Z₁

w₁

w₂

w₁

Z₂

a₂

a₃

a₂

a₃

Z₂

w₁

w₃

w₄

w₂

Z₃

a₃

a₄

a₂

a₄

a₂

Z₃

w₂

w₁

w₃

a₁~ N₁= 3 N₃ a₃= 000

a₂~ N₂= 4 N₂ a₂= 001

a₃~ N₃= 5 N₁ a₁= 010

a₄~ N₄= 5 N₄ a₄= 100

a₅~ N₅= 1 N₅ a₅= 011

Аналогично кодированию внутренних состояний для D-триггеров можно кодировать выходные сигналы для любого типа триггеров, т.е. чем чаще вырабатывается данный выходной сигнал w_i, тем меньше единиц в его коде. Так для автомата (рис.41.) имеем:

w₁~ N₁= 6 N₁ w₁ = 00

w₂~ N₂= 5 N₂ w₂ = 01

w₃~ N₃= 2 N₃ w₃ = 10

w₄~ N₄= 2 N₄ w₄ = 11

Предполагается самостоятельно окончить синтез автомата при данном кодировании ипри любом другом. Результаты сравнить.

Эвристический алгоритм кодирования.

Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базеT, RS,JK-триггеров.Для данных типов триггеров (в отличие от D-триггеров!) накаждом переходе, где триггер меняет свое значение на противоположное, одна из функций возбуждения обязательно равна 1. Уменьшение числа переключений триггеров приводит к уменьшению количества единиц соответствующих функций возбуждения, что при отсутствии минимизации однозначно приводит к упрощению комбинационной схемы автомата.

Введем некоторые определения.

Пусть Г(S) – неориентированный граф переходов автомата S. Вершины графа отождествляются с состояниями автомата. Вершины i и j соединены ребром, если есть переход из а_i и а_j или наоборот.

Обозначим q(i, j) число всевозможных переходов автомата из а_i в а_j. Каждому ребру (i, j) графа Г(S) поставим в соответствие вес ребрар(i, j) = q(i, j) + q(j, i).

Введем функциюw(i, j) = р(i, j)×d(i, j), где d(i, j) – число компонентов, которыми коды состояний а_i в а_j отличаются друг от друга (т.е. кодовое расстояние между кодами а_i в а_j).

Функция w(i ,j) имеет простой физический смысл. Перход автомата из а_i в а_j (или наоборот) сопровождается переключением стольких триггеров, сколькими компонентами отличаютсякоды этих состояний, т.е. их число равно w(i ,j). Следовательно, при переходе автомата по всем ребрам, соединяющим состоянияма_i и а_j(их число p(i, j)!) всего переключится количество триггеров, равное p(i, j)×d(i ,j) =w(i ,j).

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

Из выражения для w следует, что переход из а_i в а_i, для которого d(i,i)=0,не влияет на w (что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).

Рассмотрим применение эвристического алгоритма на конкретном примере автомата,заданного таблицами переходов и выходов (рис.41. ).Для данного автомата можно построить ориентированный граф (без учета петель), представленный на рис.42.На каждом ребре указан его вес.

Эвристический алгоритм состоит из следующих шагов.

1. Строимматрицу i, j), для которых р(i, j) ¹ 0 (т.е. в автомате есть переход из а_i в а_j или наоборот) и iуказываемеевес р(i, j), совпадающий с весом ребра соединяющего а_i и а_j.

		i	j	p(i,j)
		1	2	2
		1	3	1
T	=	1	5	1
		2	3	3
		2	4	1
		2	5	1
		3	4	2
		3	5	2

2. Упорядочим строки матрицы следующим образом. В первую строку матрицы поместим пару (a,b) с наибольшим весом р(a,b). В нашем случае (a,b) = (2,3), р(2,3) = 3.Из всех пар, имеющих общий компонент с парой (a,b) выбирается пара (g,d) с наибольшим весом и заносится во вторую строку матрицыa,b}×{g,d}¹0.Затем из всех пар, имеющих общий компонент хотя бы с одной из внесенных уже в матрицу пар выбирается пара с наибольшим весом и заносится в матрицу и т.д..В случае равенства весов пар вычисляются суммы весов компонентов пар (весомр(a) компонента a называется число появлений a в матрице матрицу заноситсяпара снаибольшей суммой весов. В рассматриваемом автомате на второе место вслед за парой (2,3) претендуют пары:(1,2) с р(1,2) = 2;(3,4) с р(3,4) = 2,(3,5) с р(3,5) = 2.

Для определения того, какая пара займет второе место в матрице находим веса компонентов пар:

р(1) = 3 р(2) = 3 р(1) + р(2) = 6

р(3) = 4 р(4) = 2 р(3) + р(4) = 6

р(3) = 4 р(5) = 2 р(3) + р(5) = 6

В данном случае для всех пар совпадают и их веса и веса их компонентов. Поэтому на второе место матрицы может быть поставлена любая из пар (1,2), (3,4), (3,5). Но тогда на 3-м и 4-м будут остальные две. Выполнив упорядочивание всехпар, получим матрицу в виде:

		i	j	p(i,j)
		2	3	3
		1	2	2
M	=	3	4	2
		3	5	2
		1	3	1
		1	5	1
		2	4	1
		2	5	1

3. Определяем разрядность кода для кодирования состояний автомата (количество элементов памяти – триггеров). Всего состояний M=5. Тогда

R = ]log₂M[ = ]log₂5[ =3.

Закодируем состояния из первой строки матрицы следующим образом: K₂ = K(а₂) = 000; K₃ = K(а₃) = 001.

Для удобства кодирования будем иллюстрировать этот процесс картой Карно:

4. Вычеркнем из матрицы первую строку, соответствующую закодированным состояниям а₂ иа₃. Получим матрицу

		i	j	p(i,j)
		1	2	2
		3	4	2
M’	=	3	5	2
		1	3	1
		1	5	1
		2	4	1
		2	5	1

5. В силу упорядочивания п.2 в первой строке закодирован ровно один элемент. Выберем из первой строки незакодированный элемент и обозначим его g. (В нашем случае g= 1).

6. Строим матрицу выбравиз строчки, содержащие g.

				i	j	p(i,j)
				1	2	2
M_g	=	M’	=	1	3	1
				1	5	1

Пусть B_g= {g₁,...,g_F} –множество элементов из матрицы К_g₁,..., K_g_Fсоответственно. В нашем случае:

B_g = B₃ = {2,3} K₂ = 000 K₃ = 001.

7. Для каждого K_g_f (f=1, ..., F) найдемиеще незанятыхдля кодирования состояний автомата. (Для соседнихкодов кодовое расстояние d=1).

K₂ = 000 = {100, 010}

K₃ = 001 = {011, 101}.

Построим множество

Если оказывается, что , где

8. Для каждого кода из множества D_gнаходим кодовое расстояние до кода

K₂ = 000K₃ = 001

d(100, 000) = 1 d(100, 001) = 2

d(010, 000) = 1 d(010, 001) = 2

d(011, 000) = 2 d(011, 001) = 1

d(101, 000) = 2 d(100, 001) = 1

9. Находим значение функции w для каждого кода из множества D_g.

10. Из множества D_gвыбираем код K_g, укоторого получилось минимальное значение w в п.9. Выбираем код для состояния a₁ К₁=100.

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

		i	j	p(i,j)
		3	4	2
		3	5	2
M’	=	1	5	1
		2	4	1
		2	5	1

К₂ = 000 = {010}

K₃ = 001 = {011, 101}

K₂ = 000 K₃ = 001

d(010, 000) = 1 d(010, 001) = 2

d(011, 000) = 2 d(011, 001) = 1

d(101, 000) = 2 d(101, 001) = 1

Выбираем К₄ = 101.

К₁ = 100 = {110}

K₂ = 000 = {010}

К₃ = 001 = {011}

К₁ = 100 K₂ = 000 K₃ = 001

d(110, 100) = 1 d(110, 000) = 2 d(110, 001) = 3

d(010, 100) = 2 d(010, 000) = 1 d(010, 001) = 2

d(011, 100) = 3 d(011, 000) = 2 d(011, 001) = 1

Выбираем К₅ = 011.

Т.к. всесостояния автомата закодированы, то работа алгоритма заканчивается. Общее количество переключений триггеров:

Минимально возможное количествопереключений(если бы состояния были закодированы соседним кодированием)

Коэффициент эффективности кодирования:

Рассмотренный алгоритм кодирования является машино-ориентированным, существуют программы, реализующие этот алгоритм.

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

Управляющие и операторные автоматы.

Принцип микропрограммного управления.

ЭВМ перерабатывает информацию, выполняя над ней какие-то операции. Для выполнения операций над информацией используются операционные устройства – процессоры, каналы ввода-вывода, устройства управления внешними устройствами и т.д. Функцией операционного устройства является выполнение заданного множества операций F={f₁,...,f_G}над входными словами D={d₁,...,d_H} c целью вычисления слов R={r₁,...,r_Q}, которые представляют результаты операций R=f_g(D), где g=1,2,...,G.

Функциональная и структурная организация операционных устройств базируется на принципе микропрограммного управления, который состоит в следующем:

1. Любая операция f_g(g=1,...,G), реализуемая устройством, рассматривается как сложное действие, которое разделяется на последовательность элементарных действий над словами информации. Эти элементарные действия называютсямикрооперациями.

2. Для управления порядком следования микроопераций используются логические условия, которые в зависимости от значений слов, преобразуемых микрооперациями, принимают значения "ложь" или "истина" (1 или 0).

3. Процесс выполнения операций в устройстве описывается в форме алгоритма, который представляется в терминах микроопераций и логических условий и называется микропрограммой.Микропрограмма определяет порядок проверки значений логических условий и следования микроопераций, необходимый для получения требуемых результатов.

4. Микропрограмма используется как форма представления функции устройства, на основе которой определяется структура и порядок функционирования устройства во времени.

Т.о. из принципа микропрограммного управления следует, что структура и порядок функционирования операционных устройств предопределяется алгоритмом выполнения операции F={f₁,...,f_G}.

К элементарным действиям над словами информации микрооперациям относятся: передача информации из одного регистра в другой, взятие обратного кода, сдвиг и т.д.

Понятие операционного и управляющих автоматов.

Как показал академик В.М. Глушков в любом устройстве обработки цифровой информации можно выделить два основных блока – операционный автомат (ОА) и управляющий автомат (УА).

Операционный автомат (ОА) служит для хранения слов информации, выполнения набора микроопераций и вычисления значений логических условий, т.е. операционный автомат является структурой, организованной для выполнения действий над информацией. Микрооперации, выполняемые ОА, задаются множеством управляющих сигналов Y={y₁,....,y_M}, с каждым из которых отождествляется определенная микрооперация.

Значения логических условий, вычисляемые в операционном автомате, отображаются множеством осведомительных сигналов X={x₁,...,x_L}, каждый из которых отождествляется с определенным логическим условием.

Управляющий автомат (УА) генерирует последовательность управляющих сигналов, предписанную микропрограммой и соответствующую значениям логическим условий. Иначе говоря, управляющий автомат задает порядок выполнения действий в ОА, вытекающий из алгоритма выполнения операций. Наименование операции, которую необходимо выполнить в устройстве, определяется кодом g операции, поступающим в УА извне. По отношению к УА сигналы g₁,...,g_h, посредством которых кодируется наименование операции и осведомительные сигналы x₁,...,x_L, формируемые в операционном автомате, играют одинаковую роль: они влияют на порядок выработки управляющих сигналов Y. Поэтому сигналы g₁,...,g_h и x₁,...,x_L относятся к одному классу – к классу осведомительных сигналов, поступающих на вход УА.

Т.о. любое операционное устройство – процессор, канал ввода-вывода и т.д. – является композицией операционного и управляющего автоматов.Операционный автомат, реализуя действия над словами информации, является исполнительной частью устройства, работой которого управляет управляющий автомат, генерирующий необходимые последовательности управляющих сигналов.

Операционный и управляющий автоматы могут быть определены своими функциями – перечнем выполняемых ими действий.

Функция ОА определяется следующей совокупностью сведений:

1) множеством входных слов D={d₁,...,d_H}, вводимых в автомат в качестве операндов;

2) множеством выходных слов R={r₁,...,r_Q}, представляющих результаты операций;

3) множеством внутренних слов S={s₁,...,s_N}, используемых для представления информации в процессе выполнения операций. Можно считать, что входные и выходные слова совпадают с определенными внутренними DÍS, RÍS.

4) множеством микроопераций Y={y_m}, реализующих преобразование S=j_m(s) над словами информации, где j_m – вычисляемая функция;

5) множеством логических условий X={x_i}, где x_i=y_i(s_i) и y_i – булева функция;

T.o. функция ОА задана, если заданы (определены) множества D, R, S, Y, X. Время не является аргументом функции ОА. Функция устанавливает список действий-микроопераций и логических условий, которые может выполнять автомат, но никак не определяет порядок следования этих действий во времени. Т.е. функция ОА характеризует средства, которые могут быть использованы для вычислений, но не сам вычислительный процесс.

Порядок выполнения действий во времени определяется в форме функций управляющего автомата.

Функция управляющего автомата – это операторная схема алгоритма ( микропрограммы), функциональными операторами которой являются символы у₁,...,у_m, отождествляемые с микрооперациями, и в качестве логических условий используются булевы переменные х₁,...,х_L. Операторная схема алгоритма наиболее часто представляется в виде граф-схемы алгоритма (ГСА). ГСА определяет вычислительный процесс последовательно во времени, устанавливая порядок проверки логических условий х₁-х_L и порядок следования микроопераций у₁-у_m.

СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ И МИКРОПРОГРАММ

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

- вершина «начало» имеет один выход, входов не имеет. Обозначает начало микропрограммы.

- вершина «конец» имеет любое число входов, выходов не имеет. Обозначает конец микропрограммы.

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

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

- особый вид условной вершины - ждущая - имеет множество входов, 2 выхода, 1 из которых заведен на вход. При попадании в ждущую вершину выход из нее возможен только при выполнении условия Х.

Граф микропрограммы состоит из совокупности перечисленных вершин и дуг, соединяющих выходы одних вершин с входами других. Соединение вершин и направление дуг графа определяют исходя из алгоритма операции, описываемого графом, и структуры операционного автомата.

Сама микропрограмма и ее граф должны быть корректны, т.е. отвечать следующим условиям:

1. В графе должна быть только одна начальная и одна конечная вершина.

2. В любую вершину графа должен вести по крайней мере один путь из начальной вершины.

3. Из каждого выхода любой вершины графа должен существовать по

крайней мере один путь в конечную вершину.

4. При всех возможных значениях логических условий и используемых слов должен существовать путь из начальной вершины в конечную.

Пример ГСА представлен на рисунке:

ГСА на рис.43 называется содержательной, т.к. внутри вершин записаны в явном виде микрооперации и логические условия. Если же каждую микрооперацию обозначить символами Yi, a логические условия через Xi, то получится так называемая кодированная ГСА (рис.44 ).Для правильного восприятия микропрограммы, заданной в виде кодированной ГСА, необходимо знать соответствия между Yi, Xi и содержанием соответствующих микроопераций и логических условий.

Для записи микроопераций внутри вершин используется так называемый Ф-язык. Подробно с зтим языком можно ознакомиться в последующих курсах «Схемотехника ЭВМ», «Теория и проектирование ЭВМ».Здесь же мы рассмотрим только основные положения этого языка.

В этом языке существуют двоичные константы и переменные: 0010 - константа, A(1:4) - четырехразрядное слово - четырехразрядная двоичная переменная. Например, A(1:4)=1010 означает, что в первом разряде слова A будет 1, во втором - 0 и т.д. A(2:3) - часть слова A, размещенная во втором и третьем разрядах.

Наиболее употребительные операции Ф-языка:

присваивание - A( 0:3 ): = 1000, B( 1:4 ): = A( 5:8 ) и т.д.

инвертирование - A( 0:3 ): = ^ B( 1:4 )

конкатенации - С( 0:6 ): = A( 0:3 ). B( 1:3 )

Пример 1. A( 0:3 ): = 1100B( 1:4 ): = A( 0:3 ) ® B( 1:4 ): = 1100

2. B( 1:4 ): = 0101 A( 0:3 ): = ^B( 1:4 ) ® A( 0:3 ): = 1010

3. A( 0:3 ): = 1101 B( 1:3 ): = 110C( 0:6 ): = A( 0:3 ). B( 1:3 ) ® C(0:6):=1101110

Запись вида A(2) означает, что здесь рассматривается второй разряд слова A, т.е. это бит, записанный во втором разряде слова A.

При выполнении операций присваивания необходимо соблюдать равенство разрядов в словах слева и справа от знака присваивания. Операции сложения, логического сложения и т.д. в Ф-языке записываются обычным способом через оператор присваивания:

C(0:n):=A(0:n)+B(0:n)

D(0:n):=A(0:n)vB(0:n) ит.д.

ОПЕРАЦИОННЫЕЭЛЕМЕНТЫ

Согласно принципа микропрограммного управления, любая сложная операция распадается на ряд микроопераций, которые выполняются ОА. Различные микрооперации выполняются элементарными ОА - так называемыми операционными элементами (ОЭ), которые являются составными частями основного ОА.

Под операционным элементом понимают устройство, реализующее одну из следующих функций или их произвольную комбинацию:

· хранение слова информации С;

· выполнение некоторых микроопераций, в результате которых вычисляется новое значение слова С;

· вычисления логического условия, зависящего от слова С;

Т.о. функция ОЭ определена, если заданы:

· описание хранимого или вычисляемого слова;

· описание множества микроопераций, выполняемых этим элементом;

· описание вычисляемых этим элементом логических условий.

Для построения ОА ОЭ соединяются между собой с помощью цепей передачи слов информации от выходов одних элементов к входам других.

В зависимости от выполняемых микроопераций ОЭ делятся на разновидности: шина, регистр, счетчик, сумматор, схема сравнения, дешифратор, шифратор и т.д.

Шина - это совокупность цепей, предназначенных для передачи слова информации. Условное обозначение шины представлено на рис.45.

Шины, изображенные на рис.45называются неуправляемыми шинами.

Управляемые шины представлены на рис.46.

Под действием управляющего сигнала у управляемая шина выполняет микрооперации: у=0 : B(0:3):=0 ,y=1 : B(0:3):=A(0:3)

Т.е. при y=1 осуществляется операция передачи. Разрядность шины может быть произвольная, но обычно это 8, 12, 16, 24, 32 и т.д.

Регистр - это операционный элемент, служащий для запоминания слов и обеспечивающий в общем случае выполнение следующих микроопераций:

· установка регистра в 0 (сброс);

· прием слова из другого регистра, шины и т.д.;

· передача слова на другой регистр, шину и т.д.;

· преобразование кодов хранимых слов в инверсные коды;

· сдвиг хранимого слова влево или вправо на требуемое число разрядов.

Регистр, выполняющий такие микрооперации, называется многофункциональным. Т.к. регистр предназначен для хранения информации, то он содержит элементы памяти, в качестве которых используются триггеры. Количество триггеров определяет разрядность регистра. Будем обозначать регистр в виде прямоугольника с указанием разрядности (рис.47 ).

Регистр может состоять из отдельных подрегистров, имеющих самостоятельное значение (рис.48.). На рис.48представлен регистр, хранящий число в форме с плавающей запятой. В этом регистре три подрегистра: для хранения знака Рг(0), характеристики Рг(1:7), мантиссы Рг(8:31) числа.

Регистр может выполнять ряд микроопераций, например:

Регистр, который выполняет микрооперацию у4 (сдвиг вправо) или у5 (сдвиг влево) называются регистром сдвига.

Сумматор - операционный элемент, выполняющий суммирование кодов чисел. В зависимости от кодов чисел различают сумматоры прямого, обратного, дополнительного кодов. Кроме того, сумматоры бывают комбинационными и накапливающими.

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

Условное обозначение комбинационного сумматора представлено на рис.50.

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

Структура и условное обозначение накапливающего сумматора представлены на рис. 51.

Счетчик - операционный элемент, который реализует микрооперацию счета. Микрооперация счета состоит в изменении состояния счетчика (значения хранимого слова) на 1. Кроме того счетчик может выполнить и такие микрооперации: установка в 0 и прием произвольного числа.

Т.е. полный набор возможных микроопераций для счетчика:

Счетчик, выполняющий микрооперацию у₁ называется суммирующим, микрооперацию у₂ - вычитающим, обе микрооперации - реверсивный.

Дешифратор - операционный элемент, выполняющий функцию преобразования некоторого n-разрядного двоичного кода в унитарный код «один из N». Если N=2ⁿ - то такой дешифратор называется полным, если N<2ⁿ - то частичным. Таблица истинности простейшего полного дешифратора (n=2) и его условное обозначение приведены в табл. 25. и на рис. 53.

Промышленность может выпускать дешифраторы с инверсными выходами. Для такого дешифратора таблица истинности и условное обозначение имеют вид (табл. 26., рис. 54.)

СИНТЕЗМИКРОПРОГРАММНЫХАВТОМАТОВ ПОГРАФ-СХЕМЕАЛГОРИТМА

Граф-схема алгоритма есть форма представления микропрограммы, которую должно выполнить операционное устройство (ОУ). При построении операционного устройства, как состоящего из операционного (ОА) и управляющего (УА) автоматов, необходимо уметь выделить функции ОА и УА из ГСА. Обычно микропрограмма представляется в виде содержательной ГСА.В этом случае для задания функций ОА необходимо перечислить все выполняемые микрооперации и все проверяемые логические условия данной микропрограммы, а также описать разрядность слов, обрабатываемых операционным устройством. На основании этих данных можно построить ОА методами, которые будут изложены в курсе «Схемотехника ЭВМ». Для инициализации выполнения той или иной микрооперации на ОА должны поступать в нужный согласно ГСА момент времени управляющие сигналы Yi. Обычно при проектировании ОУ принимают определенный способ кодирования микроопераций (чаще всего кодом, содержащим столько разрядов, сколько всего различных микроопераций) и для разработки ОА считают, что УА выдает код микроопераций, которые должны выполниться в данный момент времени.

Для УА важна последовательность выдачи соответствующих кодов микроопераций в зависимости от логических условий, вырабатываемых ОА и анализируемых УА в нужные моменты времени. Если принят способ кодирования микроопераций, то функции УА задаются кодированной ГСА. Поэтому для различных содержательных ГСА , имеющих одинаковую кодированную ГСА, ОА будут различны, но УА будет одним и тем же.

В дальнейшем будем рассматривать синтез только УА и только кодированной ГСА.

Конечный автомат, интерпретирующий микропрограмму работы дискретного устройства, называется микропрограммным автоматом.Одну и ту же ГСА можно интерпретировать как автоматом Мили, так и автоматом Мура.

Абстрактныйсинтез микропрограммного автомата по ГСА осуществляется в два этапа:

1. Получение отмеченной ГСА.

2. Построение графа автомата или таблиц переходов и выходов.

СИНТЕЗАВТОМАТА МИЛИ

На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечают символами a₁, a₂,.. по следующим правилам:

1) символом а₁ отмечают вход вершины, следующей за начальной, а также вход конечной вершины;

2) входы всех вершин следующих за операторными, должны быть отмечены;

3) входы различных вершин, заисключением конечной, отмечаются различными символами;

4) если вход вершины отмечается, то только одним символом.

Ясно, что для проведения отметок потребуется конечное число символов а₁,...,a_m. Результатом первого этапа является отмеченная ГСА, которая служит основой для второго этапа - перехода к графу или таблицам переходов-выходов. Пример ГСА, отмеченной для автомата Мили, представлен на рис. 55.

На втором этапе, из отмеченной ГСА, строят граф автомата или таблицы переходов-выходов. Для этого полагают, что в автомате будет столько состояний сколько символов a_i понадобилось при отметке ГСА.

_i. Для каждого из состояний a_i определяем по отмеченной ГСА все пути, ведущие в другие состояния и проходящие обязательно только через одну операторную вершину. Например, из состояния а₁(рис.55.) есть переход в состояние a₂ (путь проходит через операторную вершину y₁ y₂) и в состояние a₄ (путь проходит через вершину y₃ y₄). Перехода из a₁ в a₃ нет, так как на этом пути нет ни одной операторной вершины. Будем считать, что автомат осуществляет переход, например, из a₁ в a₂ при условии x₁ = 0 или x₁ (см.ГСА, рис.55. ) и вырабатывает на этом переходе выходные сигналы у₁ у₂ (то, что записано в проходимой операторной вершине ГСА, рис.55.). Значение условий х₂, х₃, х₄ на этом переходе не оказывает влияния на автомат.

₆ в а₁), т.е. не сопровождается выработкой выходных сигналов.

Отмечаем на графе все указанные пути для всех состояний в виде дуг, которым приписываем условия перехода и выходной сигнал, вырабатываемый на этом переходе. Получим граф автомата (рис.55. ).

На этом графе переходам типа а₃ ®a₄, a₅ ® a₁ приписывается условие перехода 1, т.к. эти переходы являются безусловными и выполняются всегда, когда автомат попадает в состояние а₃ (или а₅).На основании отмеченной ГСА или графа автомата можно построить таблицу переходов-выходов. Для микропрограммных автоматов таблица переходов-выходов строится в виде списка и различаются прямая и обратная таблицы. Для данного автомата прямая таблица представлена в табл. 27., обратная - в табл. 28.

Табл. 27.Прямая таблица переходов- Табл. 28.Обратная таблица перехо-

выходов автомата Мили дов - выходов автомата Мили

a_m	a_s	X	Y	a_m	a_s	X	Y
a₁	a₂	x₁	y₁y₂	a₄	a₁	x₂	y₂
	a₄	x₁	y₃y₄	a₅		1	y₂
a₂	a₂	x₃x₂	y₁y₂	a₆		x₄	-
	a₅	x₃	y₂y₃	a₁	a₂	x₁	y₁y₂
	a₆	x₃x₂	y₄	a₂		x₃x₂	y₁y₂
a₃	a₄	1	y₃y₄	a₆		x₄	y₁y₂
a₄	a₁	x₂	y₂	a₄	a₃	x₂	y₁y₄
	a₃	x₂	y₁y₄	a₁	a₄	x₁	y₃y₄
a₅	a₁	1	y₂	a₃		1	y₃y₄
a₆	a₁	x₄	-	a₂	a₅	x₃	y₂y₃
	a₂	x₄	y₁y₂	a₂	a₆	x₃x₂	y₄

В приведенных таблицах a_m - исходное состояние, a_S - состояние перехода, Х - условие (входной сигнал), обеспечивающий переход из состояния am в состояние as, Y - выходной сигнал, вырабатываемый автоматом при переходе из a_m в a_S.

СИНТЕЗАВТОМАТА МУРА.

Для автомата Мура на этапе получения отмеченной ГСА разметка производится согласно следующим правилам:

1) символом а₁ отмечается начальная и конечная вершины;

2) различные операторные вершины отмечаются различными символами;

3) все операторные вершины должны быть отмечены;

Пример ГСА, отмеченной для автомата Мура, представлен на рис. 56.

Граф автомата Мура, соответствующий отмеченной ГСА (рис. ), представлен на рис. . Построение его аналогично построению графа для автомата Мили.

Таблицы переходов-выходов автомата Мура представлены в табл. 29 (прямая) и табл. 30 (обратная). Обычно для автомата Мура в таблице переходов-выходов дополнительный столбец для выходных сигналов не используется и выходной сигнал записывается в столбце, где указывается исходное состояние a_m или состояния перехода a_S.

Табл. 29.Прямая таблица переходовТабл. 30.Обратная таблица переходов

автомата Мура. автомата Мура.

a_m(Y)	a_s	X	a_m	a_s(Y)	X
a₁(--)	a₂	x₁	a₆	a₁(-)	x₄
	a₃	x₁	a₇		1
a₂(y₁y₂)	a₂	x₃ x₂	a₁	a₂(y₁y₂)	x₁
	a₅	x₃	a₂		x₃ x₂
	a₆	x₃ x₂	a₆		x₄
a₃(y₃y₄)	a₄	x₂	a₁	a₃(y₃y₄)	x₁
	a₇	x₂	a₄		1
a₄(y₁y₄)	a₃	1	a₃	a₄(y₁y₄)	x₂
a₅(y₂y₃)	a₇	1	a₂	a₅(y₂y₃)	x₃
a₆(y₄)	a₁	x₄	a₂	a₆(y₄)	x₃ x₂
	a₂	x₄	a₃	a₇(y₂)	x₂
a₇(y₂)	a₁	1	a₅		1

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

СТРУКТУРНЫЙ СИНТЕЗ МИКРОПРОГРАММНЫХАВТОМАТОВ

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

При выполнении структурного синтеза строят так называемые структурные таблицы переходов и выходов, которые также могут быть как прямыми так и обратными.

Рассмотрим этапы структурного синтеза на конкретных примерах.

СТРУКТУРНЫЙСИНТЕЗ АВТОМАТАМИЛИ

Выполним структурный синтез микропрограммного автомата Мили, заданного своей таблицей переходов-выходов (табл. 27 или табл. 28). В качестве примера синтез будем выполнять по прямой таблице (табл. 27).

1. В исходном автомате количество состояний М=6, следовательно,число элементов памяти

m = ] log 2 M [ = ] log 2 6 [ = 3.

Пусть для синтеза используются JK триггеры.

2. Кодируем внутренние состояния автомата, используя для этого карту Карно (рис.57.) и по возможности метод соседнего кодирования. Рекомендуется самостоятельно закодировать состояние спомощью эвристического алгоритма.

3. Строим прямую структурную таблицу переходов-выходов автомата Мили (табл. 31). В данной таблице в столбцах k(a_m) и k(a_s) указывается код исходного состояния и состояния перехода соответственно. В столбце функций возбуждения ФВ указывается те значения функций возбуждения, которые на данном переходе обязательно равны 1. Остальные (т.е. равные 0 или принимающие неопределенные значения) не указываются. Это эквивалентно тому, что всем неопределенным значениям функций возбуждения приписывается значение 0, что в общем случае не дает минимальной функции, однако в реальных автоматах минимизация обычно не делается в виду ее неэффективности. Предлагается самостоятельно построить структурную таблицу переходов с указанием всех значений функций возбуждения (в том числе и неопределенных), выполнить минимизацию и сравнить результаты с приведенными ниже.

Табл. 31. Структурная таблица переходов-выходов автомата Мили.

A_m	K(a_m)	a_s	K(a_s)	X	Y	ФВ
a₁	000	a₂	010	x₁	y₁y₂	J₂
		a₄	001	x₁	y₃y₄	J₃
a₂	010	a₂	010	x₃x₂	y₁y₂	-
		a₅	110	x₃	y₂y₃	J₁
		a₆	011	x₃x₂	y₄	J₃
a₃	101	a₄	001	1	y₃y₄	K₁
a₄	001	a₁	000	x₂	y₂	K₃
		a₃	101	x₂	y₁y₄	J₁
a₅	110	a₁	000	1	y₂	K₁K₂
a₆	011	a₁	000	x₄	-	K₂K₃
		a₂	010	x₄	y₁y₂	K₃

4. Для получения функций возбуждения поступаем следующим образом. Выражение для каждой функции получается в виде логической суммы произведений вида a_iX, где a_i- исходное состояние, X-условие перехода. Для упрощения полученных выражений выполняем все возможные операции склеивания и поглощения:

J₁ = a₂x₃ + a₄x₂ K₁ = a₃ + a₅

J₂ = a₁x₁ K₂ = a₅ + a₆x₄

J₃ = a₁x₁ + a₂x₃x₂ K₃ = a₄x₂ + a₆x₄ + a₆x₄ = a₆ + a₄x₂

5. Для получения функций выходов поступаем аналогично:

y₁ = a₁x₁ + a₂x₃x₂ + a₄x₂ + a₆x₄

y₂ = a₁x₁ + a₂x₃x₂ + a₂x₃ + a₄x₂ + a₅ + a₆x₄

y₃ = a₂x₃ + a₃ + a₁x₁

y₄ = a₁x₁ + a₂x₃x₂ + a₃ + a₄x₂

6. Для построения функциональной схемы автомата по полученным выражениям необходимо либо заменить a_i его значениями через Q₁Q₂Q₃ либо получить сигнал, соответствующий a_i. Обычно используют второй способ и для получения сигнала a_i применяют так называемый дешифратор состояний, на вход которого поступают сигналы с выходов элементов памяти Q₁Q₂Q₃. Кроме того, при построении схемы стараются выделить общие части, встречающиеся в функциях возбуждения или выходных сигналах. В этом случае окончательная система уравнений, по которым строится схема, будет иметь вид:

A = a₂x₃x₂+J₂ ; J₁ = D + B ; y₁ = A + B + E ;

B = a₄x₂ ; K₁ = a₃ + a₅; y₂ = A + D + C + a₅ + E ;

C = a₄x₂ ; J₂ = a₁x₁ ; y₃ = D + F + a₃ ;

D = a₂x₃ ; K₂ = a₅ + a₆x₄ ; y₄ = a₃ + B + J₃;

E = a₁x₁; K₃ = a₆ + C ;

F = a₁x₁ J₃= F+a₂x₃x₂

Функциональная схема автомата, построенная на основании полученных уравнений, представлена на рис. 58.

СТРУКТУРНЫЙСИНТЕЗ АВТОМАТАМУРА

Выполним структурный синтез микропрограммного автомата Мура, заданного своей таблицей переходов-выходов (табл.29или табл. 30).В качестве примера синтез будем выполнять по обратной таблице (табл. 32).

1. В исходном автомате количество состояний М=7, следовательно число элементов памяти

m=] log 2 M [ =] log 2 7 [=3

Пусть для синтеза используется D-триггеры.

2. Кодируем внутренние состояния автомата, используя алгоритм кодирования для D-триггеров. Количество переходов в данное состояние легко определяется из обратной таблицы: a₁ ~ 2, a₂ ~ 3, a₃ ~ 2, a₄ ~ 1, a₅ ~ 1, a₆ ~ 1, a₇ ~ 2.

Поэтому коды состояний следующие:

a₂-000, a₁-001, a₃-010, a₇-100, a₄-011, a₅-101, a₆-110.

3. Строим структурную таблицу переходов - выходов автомата Мура.

Табл. 32. Структурная таблица переходов - выходов автомата Мура.

a_m	K(a_m)	a_s(Y)	K(a_s)	X	ФВ
a₆	110	a₁(-)	001	x₄	D₃
a₇	100			1	D₃
a₁	001	a₂(y₁y₂)	000	x₁	-
a₂	000			x₃x₂
a₆	110			x₄
a₁	001	a₃(y₃y₄)	010	x₁	D₂
a₄	011			1	D₂
a₃	010	a₄(y₁y₄)	011	x₂	D₂D₃
a₂	000	a₅(y₂y₃)	101	x₃	D₁D₃
a₂	000	a₆(y₄)	110	x₃x₂	D₁D₂
a₃	010	a₇(y₂)	100	x₂	D₁
a₅	101			1	D₁

Построение таблицы выполняется аналогично автомату Мили.

4. Выражения для функций возбуждения получаются в виде суммы произведений a_iх, где a_i-исходное состояние, х - условие перехода.

D₁ = a₂x₃ + a₂x₃x₂ + a₃x₂ + a₅

D₂ = a₁x₁ + a₄ + a₃x₂ + a₂x₃x₂

D₃ = a₆x₄ + a₇ + a₃x₂ + a₂x₃

или

A = a₃x₂

B = a₂x₃x₂

D₁ = a₂x₃ + B + a₃x₂ + a₅

D₂ = a₁x₁ + a₄ + A + B

D₃ = a₆x₄ + a₇ + A + a₂x₃

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

y₁ = a₂ + a₄

y₂ = a₂ + a₅ + a₇

y₃ = a₃ + a₅

y₄ = a₃ + a₄ + a₆

6. Для построения функциональной схемы автомата как и в предыдущем случае используем дешифратор состояний. Схема представлена на рис. 61 .

ЗАМЕЧАНИЯ.

1. При синтезе микропрограммных автоматов изложенным методом получаемые выражения для функций возбуждения не всегда являются минимальными и в некоторых случаях могут быть упрощены. В частности, можно доопределить функции возбуждения на некоторых наборах единичным значением (а не нулевым, как было ранее) и выполнить все операции склеивания. Например, в синтезированном ранее автомате Мили таким образом можно получить значение k₁=1. Рекомендуется в этом убедиться самостоятельно.

Для упрощения схем автоматов можно также предварительно упростить ГСА, уменьшив количество вершин или узлов методами, изложенными в / /.

Автомат Мили в течении такта сохраняет свое состояние и лишь в конце его переходит в новое. Пока автомат находится в данном состоянии Ai он вырабатывает выходные сигналы y=f(Ai,x), где х - сигналы, подаваемые на вход автомата в течение данного такта. В связи с этим автомат Мили может интерпретировать микропрограмму корректно только в том случае, если для любого перехода выполняется условие независимости логических условий от результатов выполнения микроопераций на данном переходе.

Условие независимости нарушается, если на некотором переходе из а_m в а_s под действием сигнала х с выработкой у_i наблюдается функциональная зависимость х = f(у_i). В таком случае выполнение микрооперации у_i может привести к изменению значения х и автомат, находясь в состоянии а_m, и, реагируя на набор входных сигналов, сформирует набор выходных сигналов, не соответствующий микропрограмме. Чтобы избежать этого, можно использовать следующие способы:

1) запомнить значение сигналов х на промежуток времени, равный длительности такта;

2) ввести в автомат дополнительные состояния;

3) реализовать автомат по схеме Мура.

Запоминание значений сигналов х в течение такта осуществляется операционным автоматом с помощью дополнительных элементов памяти – триггеров. Интерпретация микропрограммы автоматом Мура рассматривалась ранее. Введение дополнительных состояний иллюстрируется рис. 59 .

В исходном автомате (рис. 59.а) есть переходы из а_i в а_j под действием сигналов х и х с выработкой y₁ и y₂ соответственно и имеет место х = f(y₁, y₂). Действительно, введение вспомогательных состояний а_k и а_l позволяет устранить возможную ошибку в выдаче выходных сигналов. На переходах а_iа_k или а_iа_l выходные сигналы не вырабатываются. Переходы а_iа_k или а_iа_l являются безусловными с выработкой y₁ или y₂ соответственно. В таком случае изменение значения х, в результате выполнения микроопераций y₁ или y_2, не повлияет на выходной сигнал, вырабатываемый автоматом, так как на переходах а_iа_k или а_iа_l выходной сигнал уже не зависит от х.

Синтез управляющего автомата Мура
на базе регистра сдвига.

Кроме рассмотренного ранее канонического метода, существуют и другие методы синтеза управляющих автоматов, среди которых наиболее широко используется синтез на базе регистра сдвига. Этот метод позволяет при построении схемы отказаться от дешифратора, т.к. состояния кодируются унитарным кодом. В автомате количество элементов памяти выбирается равным количеству внутренних состояний. В каждый момент времени только один триггер находится в 1, остальные в 0. Обычно при синтезе на базе регистра сдвига используются D-триггеры. Очень эффективен данный метод для так называемых линейных микропрограмм, т.е. микропрограмм без ветвлений (отсутствует логические условия). Рассмотрим пример синтеза управляющего автомата Мура данным методом. Пусть закодированная ГСА микропрограммы имеет вид рис. 60. Разметив данную ГСА для автомата Мура, получаем семь состояний. Следовательно число триггеров m=7. Выполним синтез с использованием D-триггеров. Закодируем состояния унитарным кодом: a₁=1000000, a₂=0100000,..., a₇=0000001. Обратная структурная таблица переходов-выходов для данного автомата представлена в таблице.

a_m	Ka_m	a_s(y)	Ka_s	x	ФВ
а₆	0000010	а₁(-)	1000000	1	D₁
а₇	0000001			1	D₁
а₁	1000000	а₂(y₁y₂)	0100000	1	D₂
а₂	0100000	а₃(y₂)	0010000	1	D₃
а₃	0010000	а₄(y₃y₄)	0001000	1	D₄
а₄	0001000	а₅(y₂)	0000100		D₅
а₅	0000100	а₆(y₃)	0000010	1	D₆
а₄	0001000	а₇(y₄)	0000001	x	D₇

На основании структурной таблицы записываем выражения для выходных сигналов y_i и функций D_i :

D₁ = a₆ + a₇ y₁ = a₂

D₂ = a₁ y₂ = a₂ + a₃ + a₅

D₃ = a₂ y₃ = a₄ + a₆

D₄ = a₃ y₄ = a₄ + a₇

D₅ = a₄

D₆ = a₅

D₇ = a₄×x

Т.к. состояния автомата закодированы унитарным кодом, то можно отождествить каждое состояние с выходом соответствующего триггера, т.е. принять а_i=Q_i. Для принятого способа кодирования переход из одного состояния в другое как бы сопровождается сдвигом кода, за-

писанного в семиразрядном регистре. Этим и объясняется название метода. Функциональная схема автомата Мура, построенная по полученным уравнениям, приведена на рисунке 62. При определенных навыках синтез автомата Мура на базе регистра сдвига выполняется непосредственно по отмеченной ГСА без построения структурной таблицы переходов-выходов.

	00	01	11	10		00	01	11	10
00	0	0	1	–	00	1	0	1	–
01	–	1	0	–	01	–	1	0	–
11	0	–	1	0	11	0	–	0	1
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	1	0	–	00	0	1	1	–
01	–	1	1	–	01	–	0	1	–
11	0	–	1	0	11	1	–	0	1
10	–	–	–	–	10	–	–	–	0

	00	01	11	10		00	01	11	10
00	X	1	1	–	00	0	0	0	–
01	–	0	1	–	01	–	X	0	–
11	0	–	0	0	11	1	–	X	1
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	1	X	–	00	X	X	0	–
01	–	1	X	–	01	–	X	1	–
11	0	–	X	X	11	X	–	1	0
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	X	X	–	00	X	1	1	–
01	–	X	X	–	01	–	0	1	–
11	X	–	1	0	11	0	–	0	X
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	0	1	–	00	1	0	1	–
01	–	1	0	–	01	–	1	0	–
11	0	–	1	0	11	0	–	0	1
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	1	0	–	00	0	1	1	–
01	–	1	1	–	01	–	0	1	–
11	0	–	1	0	11	1	–	0	1
10	–	–	–	–	10	–	–	–	0

	00	01	11	10		00	01	11	10
00	X	1	1	–	00	0	0	0	–
01	–	0	1	–	01	–	X	0	–
11	0	–	0	0	11	1	–	X	1
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	1	X	–	00	X	X	0	–
01	–	1	X	–	01	–	X	1	–
11	0	–	X	X	11	X	–	1	0
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	X	X	–	00	X	1	1	–
01	–	X	X	–	01	–	0	1	–
11	X	–	1	0	11	0	–	0	X
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	0	1	–	00	1	0	1	–
01	–	1	0	–	01	–	1	0	–
11	0	–	1	0	11	0	–	0	1
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	1	0	–	00	0	1	1	–
01	–	1	1	–	01	–	0	1	–
11	0	–	1	0	11	1	–	0	1
10	–	–	–	–	10	–	–	–	0

	00	01	11	10		00	01	11	10
00	X	1	1	–	00	0	0	0	–
01	–	0	1	–	01	–	X	0	–
11	0	–	0	0	11	1	–	X	1
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	1	X	–	00	X	X	0	–
01	–	1	X	–	01	–	X	1	–
11	0	–	X	X	11	X	–	1	0
10	–	–	–	–	10	–	–	–	–

	00	01	11	10		00	01	11	10
00	0	X	X	–	00	X	1	1	–
01	–	X	X	–	01	–	0	1	–
11	X	–	1	0	11	0	–	0	X
10	–	–	–	–	10	–	–	–	–