Противогоночное кодирование

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

В структуре управляющего автомата имеются замкнутые контуры обратной связи: выходы триггеров q подаются на входы комбинационной части L, а выходы Ψ этой части подаются на входы триггеров. Предположим, что автомат должен перейти из состояния аi с кодом 0111 в состояние аj с кодом 1011 (рис. 1.5).

Рис. 1.5. Пример смены состояния автомата

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

Что произойдет, если один из триггеров, например второй, закончит свой переход раньше первого? Его выходная переменная q 2 поступит в комбинационную часть автомата и будет там влиять на формирование всех или, по крайней мере, некоторых выходных переменных z и функций возбуждения Ψ. В результате на выходах комбинационной части автомата на некоторое время установятся не предусмотренные алгоритмом значения . Неверные значение вектора вызовут новый переход в ложном направлении и т.д., пока какое-то очередное состояние автомата не окажется устойчивым. Подобные процессы называются состязаниями элементов памяти или попросту гонками и безусловно недопустимы. Существует два пути борьбы с ними.

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

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

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

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

Метод соседнего кодирования

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

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

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

Рис. 1.6. Фрагмент графа, требующего корректировки

Пример 3. Методику соседнего кодирования рассмотрим на примере автомата, представленного упрощенным неориентированным графом на рис. 1.7. Здесь имеются циклы с нечетным числом вершин (1-2-7 и 2-3-5-8-7), есть и недопустимый подграф с тремя промежуточными состояниями 0, 4 и 7 между 1 и 6.

Рис. 1.7. Исходный граф автомата для примера 3

Циклы с нечетным числом вершин устраняются просто, введением одной добавочной вершины 9. Для разрушения недопустимого подграфа придется вставить по крайней мере две добавочные вершины в какое-нибудь из его ребер (или в два разных ребра). На рис. 1.8 показан тот же граф после указанной корректировки.

Рис. 1.8. Откорректированный граф автомата для примера 3

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

В данном графе высокие степени имеют вершины 1 и 7. Целесообразно увеличить расстояние между ними, включив в соединяющее их ребро добавочные состояния 10 и 11. Сделанные нами исправления первоначального графа необходимы, но могут оказаться недостаточными, что обнаружится позже. Перейдем к определению числа разрядов кода состояния n. При соседнем кодировании эта величина должна удовлетворять двум условиям:

n = ] log2 m [;

n = max{ s 0, s 1,... sm -1},

где m - число состояний после корректировки графа, s - степени вершин. В данном примере обе критические величины дают n = 4.

Для облегчения подбора кодов используем карту Карно (рис. 1.9).

Рис. 1.9. Карта Карно для подбора кодов

Для замыкания пути 2-9-7 пришлось добавить еще два состояния: 12 и 4. Скорректированный соответствующим образом неориентированный граф со всеми добавочными состояниями показан на рис. 1.10.

Рис. 1.10. Граф с добавленными состояниями

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

Рис. 1.11. Пример корректировки перехода автомата Мили

Рис. 1.12. Пример корректировки перехода автомата Мура

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

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

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

Методика кодирования с развязыванием переходов

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

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

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

Рис. 1.13. Пример развязанных переходов

Когда происходит верхний из показанных на рисунке переходов, первый разряд кода состояния q 1 остается равным нулю. Поэтому никакие гонки при переключении других триггеров не могут привести к какому-нибудь состоянию из нижней пары. Если при u 3 происходит не два, а большее число переходов, то разделителями этих переходов будут уже не один разряд кода, а несколько. Число таких разрядов, очевидно, определится двоичным логарифмом от числа конкурирующих переходов.

Пример 4. Граф переходов асинхронного автомата показан на рис. 1.14.

Рис. 1.14. Граф асинхронного автомата для примера 4

Читать рис. 1.14 будем, заменяя (в уме) u 1 на и т.д. Составим списки переходов, вызываемых различными логическими условиями:

.

Начнем развязывать переходы в первом списке. Присвоим первому разряду q 1 кода состояния значение 0 – для а 0 и 1 – для состояний а 1 и а 5. Таким образом, мы развязали переходы а 0- а 0 и а 1- а 5. Чтобы развязать переход а 0- а 0 с остальными переходами, для состояний этих переходов, т.е. для а 2, а 3и а 4, примем значение q 1 = 1. Таким образом, первый шаг алгоритма кодирования заканчивается определением значений первого разряда кода для всех состояний.

Но на этом обработка первого списка переходов не заканчивается. Приступаем к развязыванию перехода а 1 -а 5 со следующим переходом этого списка. Для этого используем разряд q 2. Ему мы присвоим значение 0, для а 1 и а 5 и 1 - для а 2 и а 3. Все принимаемые значения кодов записываем в табл. 1.2.

Таблица 1.2

Кодирование состояний

Развязав переходы а 1- а 5 и а 2- а 3, мы тем самым развязали и а 1- а 5 с а 3- а 3. Переходы а 1- а 5 с а 4- а 5 и с а 5- а 5 развязывать не нужно, да и невозможно, так как их конечные состояния совпадают. Теперь мы вторично прошли до конца весь первый список, и на этом заканчиваем второй шаг.

Третий шаг начинается с того, что мы возвращаемся к строке а 2- а 3 и сравниваем ее с нижележащими строками. Развязывание не требуется для а 3- а 3, а для а 4- а 5 обеспечивается, если принять q 2=0 для а 4. Таким образом, за три шага мы развязали все переходы первого списка и затратили на это два разряда кода состояний. Значение q 2 для состояния а 0 пока остается неопределенным.

Закончив развязывание первого списка, переходим ко второму и т.д. до конца. Новые разряды вводим только при невозможности обойтись уже имеющимися. В этом примере необходимое число разрядов кода оказалось больше, чем это необходимо при произвольном кодировании: четыре против ]log26[= 3. Это и есть плата за предупреждение гонок. Иногда, впрочем, это объясняется просто неудачным выбором значения очередного разряда кода. Такая ситуация может быть выявлена и исправлена следующим путем: первый столбец таблицы кодов состояний вычеркивается, попытки развязать все переходы по всем спискам делаются с использованием оставшихся разрядов кода. При невозможности развязывания вновь вводится первый разряд кода и используется уже по-новому. Затем то же самое повторяется со вторым столбцом таблицы и т.д.

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

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

12)

Важным методом, используемым для описания функционирования RS- триггера, является метод таблиц состояний (таблиц переходов). Таблица состояний (рис. 3.3.а) RS-триггера в сокращенной форме (эту таблицу называют также управляющей таблицей, таблицей функционирования) содержит два входных сигнала (сигналы R и S) и один выходной сигнал Q (функция). Хотя триггеры имеют два выхода - один прямой Q, а другой - инверсный `Q, в описании триггера и в таблице состояний указывают лишь состояние прямого выхода Q.

Из таблицы состояний триггера видно, что при подаче на вход R уровня лог. «1» триггер принимает состояние логического «0», а при подаче управляющего сигнала «1» на вход S - состояние «1». Следует отметить также, что если до подачи управляющего сигнала, например, на вход R, триггер находился в состоянии логического «0», его состояние не изменится и после подачи сигнала «1» на вход R. Если на обоих входах триггера имеются уровни логического «0»- это состояние соответствует режиму хранения и триггер сохраняет предыдущее состояние. В таблице это состояние обозначено условно Q⁰. При подаче на входы R и S одновременно уровня «1» триггер будет находиться в неопределенном (или неправильном) состоянии, поэтому такое сочетание сигналов R и S называется запрещенной комбинацией управляющих сигналов и в таблице состояний обозначается буквой a.

Сокращенная таблица состояний триггера отражает лишь динамику изменения состояния триггера и не учитывает свойство триггера запоминать единицу информации. Полная таблица состояний триггера должна учитывать влияние (на процесс управления) значения предыдущего состояния триггера Q⁰. Причем Q⁰ представляется как входная переменная. Полная таблица состояний RS -триггера приведена на рис. 3.3, б.

Таблицу состояний строят так же, как и таблицу истинности.

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

Рис. 3.3. RS - триггер: а) - упрощенная таблица состояний; б) полная таблица

переходов; в) Карта Карно; г) RS - триггер, управляемый сигналом низкого

уровня ( триггер); д) RS - триггер на элементах базиса И-НЕ

Рассмотрим строку 4. После того, как подается сигнал на вход R, триггер сбрасывается, т.е. переходит из состояния “1” в состояние “0”.

Рассмотрим строку 5. Триггер устанавливается, т.е. переходит из состояния “0” в состояние “1”, в результате подачи сигнала “1” на вход S. Для строк 1 и 2 сигналы S =0^1* и R=0, и, следовательно, никаких изменений в состоянии триггера не происходит. Для строки 3 сигнал R=1, и этот сигнал в нормальных условиях должен сбросить триггер, но так как триггер уже “сброшен” и Q = 0, то сигнал R = 1 не изменяет его состояние.

Аналогично для строки 6 сигнал S = 1, и этот сигнал в обычных условиях будет устанавливать триггер в “1”, но Q = 1, и, следовательно, состояние триггера останется без изменений до поступления следующего сигнала R.

Особенность RS-триггера заключается в том, что при подаче одновременно на входы R и S сигнала, соответствующего логической 1, состояние триггера становится неопределенным: на обоих выходах Q и `Q установится уровень “1”, а после снятия со входов управляющих сигналов, в силу случайных причин, триггер может установиться в состояние “0” либо “1”. Очевидно, что для нормальной работы триггера необходимо исключить указанное сочетание входных сигналов, приводящее к неопределенному состоянию, что можно осуществить, предусмотрев выполнения запрещающего условия R × S=0.

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

Для получения упрощенного аналитического выражения, описывающего поведение RS-триггера, построим карту Карно и проведем соответствующие контуры (рис. 3.3, в). Полученное характеристическое уравнение триггера имеет вид

.

Применив закон де Моргана преобразуем полученные выражение в базис И-НЕ:

.

Схема RS- триггера, реализованного в выбранном базисе, приведена на рис. 3.3, г.

Из формулы RS - триггера видно, что при реализации его в базисе И-НЕ, триггер управляется сигналами низкого уровня, т.е. уровня лог. "0" (если не предусмотрены инверторы). Для приведения поведения триггера, выполненного на элементах И-HE, в соответствие с таблицей состояний сигналы S и R необходимо инвертировать.

Из анализа схемы рис. 3.3, г очевидно, что простой RS триггер можно сконструировать, соединив “крест-накрест” два элемента И-НЕ.

Входные линии триггера обозначены как и , поскольку триггер устанавливается при =0 и сбрасывается при =0. Такой триггер иногда называют RS-триггер с инверсными входами или конъюнктивной бистабильной ячейкой.

Схема RS-триггера, реализовнная в базисе И-HЕ в соответствии с таблицей состояний, приведена на рис. 3.3, д. Для построения RS -триггера на элементах ИЛИ-НЕ приведем формулу триггера в базис ИЛИ-НЕ

.

Схема RS -триггера, выполненная на элементах базиса ИЛИ-HЕ, приведена на рис. 3.4, а. Временные диаграммы, поясняющие работу RS-триггера, приведены на рис. 3.4, б.

Из временных диаграмм (рис. 3.4, б) следует, что рассмотренные выше RS-триггеры опрокидываются, т.е. управляются сигналами R и S, в любой момент времени. В тех случаях, когда длительности управляющих сигналов не синхронизированы (не согласованы), триггер может находиться в неопределенном состоянии (интервалы времени t₄, t₅), и поэтому такие триггеры называют асинхронными.

Триггер, построенный на базе элементов ИЛИ-НЕ, называют также дизьюнктивной бистабильной ячейкой. Бистабильные ячейки, помимо самостоятельного применения, входят в качестве составного узла в триггеры других типов.

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

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

Двухступенчатый RS - триггер. Рассмотренные схемы RS-триггеров являются одноступенчатыми. Применение одноступенчатых RS-триггеров в качестве самостоятельных запоминающих элементов ограничено. Это связано с неустойчивой работой последовательностной схемы (цифрового автомата), память которой выполнена на одноступенчатых RS-триггерах. Сигналы переключения триггера S(t), R(t) формируются в цифровом автомате комбинационной схемой, в их формировании участвуют, наряду с внешними логическими сигналами, сигналы Q(t) и (t). Переключение одноступенчатого триггера под действием сигналов S(t) и R(t) вызывает изменение значений сигналов Q(t) и (t), а их изменение может привести к изменениям сигналов S(t) или R(t) в том же такте времени t и, как следствие, к ложному срабатыванию триггера. Для устойчивой работы триггера необходимо, чтобы сигналы Q(t) и (t) изменялись только после прекращения действия входного сигнала S(t) или R(t). Это требование выполняется в двухступенчатых триггерах (MS-триггерах). Базовыми схемами для построения двухступенчатых триггеров являются одноступенчатые RS-триггеры.

Двухступенчатый триггер состоит из двух секций (ступеней), соединенных каскадно, как показано на рис. 3.6 а, причем, каждая секция содержит по синхронному RS-триггеру. Первая секция, ведущая или М-секция (М происходит от английского MASTER) принимает информацию со входных линий S и R. Состояние выходов ведущей секции подается на вторую секцию, ведомую, или S-секцию (S происходит от английского SLAVE).

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

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