12.2. ОБЕСПЕЧЕНИЕ УСТОЙЧИВОСТИ ФУНКЦИОНИРОВАНИЯ ЦИФРОВЫХ АВТОМАТОВ

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

Рис. 12.11

Рис. 12.12

в новое состояние. При этом происходит формирование новых сигналов возбуждения по цепям обратных связей (с выходов элементов памяти через логические элементы на входы элементов памяти), и автомат переходит в новое состояние и т. д. Таким образом, автомат, в общем случае, не может остановиться в каком-то определенном состоянии и начинает функционировать в режиме генератора состояний. Для устранения такого эффекта используют синхросерию — последовательность специальных {обычно прямоугольных) сигналов, подаваемых на входы элементов памяти и разрешающих поступление очередных сигналов возбуждения на входы элементов памяти только с приходом очередного синхросигнала. При отсутствии синхросигнала сигнал возбуждения не поступает на вход элемента памяти, и элемент памяти цифрового автомата не переключается, е. остается в каком-то состоянии. Практически подключение синхросерии осуществляется к специальным входам элемента памяти, обозначаемым символом С на рисунках и называемым синхровходами. Введение синхросерии, однако, не обеспечит устойчивого функционирования автомата, если не учитывать некоторые особенности. Пусть автомат должен выполнить переходы, изображенные на рис. 12.11. Возможны следующие ситуации:

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

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

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

В случаях, когда из соображений быстродействия двухэтажную память использовать нельзя, прибегают к многофазной системе тактирования входных сигналов автомата. Так, для случая двухфазной синхронизации синхросериями и вместо одного входного сигнала (рис. 12.11) используются два разных: (рис, 12.13). Таким способом устойчивость функционирования автомата обеспечивается автоматически. При двухфазной синхронизации необходимо, чтобы все дуги графа переходов автомата можно было бы разметить символами и так, что для любой вершины графа все выходящие из нее дуги отмечались бы символом одной синхросерии (например, а все дуги, заходящие в ту же вершину графа переходов автомата, — символом другой синхросерии (например, Если граф переходов автомата содержит контур нечетной длины (рис. 12.14), то такая разметка невозможна. Однако ее можно сделать, преобразовав контур нечетной длины в контур четной длины, добавив дополнительную вершину или состояние автомата с пустым выходным сигналом (рис. 12,15). Задача преобразования произвольного графа с нечетными контурами к графу с четными контурами решается методами теории графов, в частности с использованием понятия иикломатического числа графа и метода построения матрицы фундаментальных циклов графа.

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

Каждый фундаментальный цикл графа образуется добавлением к остову графа

Рис. 12.13

Рис. 13.14

Рис. 13.15.

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

- тическое число графа обычно обозначается как и определяется по формуле где — число ребер графа, — число его вершин. Понятие цикломатического числа играет фундаментальную роль в теории графов и позволяет легко найти все возможные циклы графа, Циклом этическое число находится для неориентированного графа. Однако для нашей задачи разметки графа переходов автомата с целью введения двухфазной синхронизации подобное ограничение несущественно. Рассмотрим построение фундаментальных циклов графа на конкретном примере (рис. 12.16). Так как то Для построения фундаментальных циклов графа определим остов графа. Примеры остовов графа приведены на рис. 12.17. Для построения фундаментальных циклов выберем один из при веденных остовов, например остов (рис. Пронумеруем ребра графа (рис. 12.16) цифрами от 1 до т. При этом ребра графа, не при над лежащие остову, будем нумеровать цифрами от 1 до а ребра, принадлежащие остову, — цифрами от до . Последнее ограничение может и не выполняться, однако оно приводит к удобной структуре матрицы фундаментальных циклов, рассматриваемой ниже, поэтому воспользуемся им. уже отмечалось, каждый фундаментальный цикл образуется добавлением к остову одного ребра, остову не принадлежащего. При добавлении ребра 1 образуется фундаментальный цикл при добавлении ребра 2 — фундаментальный цикл Все фундаментальные циклы графа представлены на рис. 12.19.

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

Рис. 12.16

Рис. 12.17

Рис. 12.18

(нефундаментальные) образуются покомпонентной суммой по модулю 2 строк матрицы фундаментальных циклов. Построим матрицу фундаментальных циклов графа (рис. 12,16) и найдем все циклы графа. В соответствии с полученными фундаментальными циклами графа (рис. 12.19) и приведенными выше разъяснениями строим матрицу фундаментальных циклов (табл. 12.20). Нефундаментальные циклы графа образуем как сумму по модулю 2 фундаментальных циклов (табл. 12.21).

Нефундаментальный цикл представлен на рис. 12.20, а цикл — на рис. 12.21. Следует отметить, что некоторые образуемые нефундаментальные циклы могут и не быть циклами графа, что является недостатком метода.

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

Вернемся к двухфазной синхронизации графа переходов автомата. После построения матрицы фундаментальных циклов графа переходов автомата подсчитывается число единиц в каждой строке матрицы (определяется вес цикла). Для каждого фундаментального цикла с нечетным весом одно из ребер цикла заменяется на два — введением дополнительной вершины графа. В преобразованном таким образом графе переходов автомата введение двухфазной синхронизации всегда возможно. Пусть, например, задан граф переходов автомата (рис, 12.22). Произведем двухфазное тактирование переходов графа. Матрица фундаментальных циклов графа представлена табл. 12.20. Фундаментальные циклы имеют нечетный вес. Расщепив ребра и 4, получаем граф с тремя дополнительными вершинами (рис. 12.23). Двухфазная синхронизация переходов графа показана на рис. 12.24.

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

Рис. 12.19

рис. 12.20

Рис. 12.21

Рис. 12.22

Таблица 12.20

Таблица 12.21

обеспечена с помощью специальных мер, принятых относительно устранения в схеме автомата эффекта гонок. Это связано с тем, что элементы памяти имеют различные времена срабатывания. Различны также задержки сигналов возбуждения, поступающих на входы элементов памяти по цепочкам логических элементов различной длины. Если при переходе автомата из одного состояния в другое, должны переключиться сразу несколько элементов памяти, то между ними начинаются гонки (состязания), что может привести к неправильной работе автомата. В самом деле, при переходе автомата из состояния в состояние на некоторый, хотя и очень короткий, промежуток времени может возникнуть промежуточное состояние автомата, отличное от Например, при переходе из изменяют свое состояние два первых элемента памяти. Из-за состязаний может возникнуть состояние 1110 (или 0010), которое может привести к изменению состояния третьего или четвертого элемента памяти. В последнем случае после окончания переходных процессов автомат уже не попадает в состояние При использовании двухэтажной памяти гонки в автомате не возникают, так как изменение состояния автомата происходит в то время, когда синхросигнал отсутствует. Следует заметить, что современная элементная база включает в себя элементы памяти с уже встроенной двухэтажной памятью (например, JK-триггер).

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

Рис. 12.23

Рис. 12.24

Рис. 12.25

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

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