Структурные автоматы

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

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

Если при переходе автомата из одного состояния в другое, должны переключиться сразу несколько элементов памяти, то между ними начинаются гонки, (состязания), что может привести к неправильной работе автомата. В самом деле, при переходе автомата из состояния a_i; в состояние a_j на некоторый, хотя и очень короткий, промежуток времени может возникнуть промежуточное состояние автомата, отличное от a_i и a_j. Например, при переходе из a_i (0110) в a_j (1010) изменяют свое состояние два первых элемента памяти. Из-за состязаний может возникнуть состояние 1110 (или 0010), которое может привести к изменению состояния третьего или четвертого элемента памяти.

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

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

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

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

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

Вывод

В процессе выполнения курсовой работы мы ознакомились с:

- основными понятиями структурных автоматов;

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

- теоремой Глушкова о структурной полноте;

- основными этапами канонического метода структурного синтеза;

- примерами канонического метода структурного синтеза;

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

- обеспечением устойчивости функционирования цифровых автоматов;

- гонкой в автоматах;

- методами устранения гонок в автоматах.

Литература

1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа” 1987.

2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.

3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.

4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.

5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.