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

Выходы в столбце промежуточного нулевого состояния определяются точно так же, как и предшествующие значения. Например, если М' на рис. 4.43 является устойчивым в состоянии 1 при входе 0001 и поступает сигнал на вход промежуточного нулевого состояния, то требуется, чтобы выходы оставались в состоянии 01.

Однако если цепь является устойчивой в состоянии 1 при входе 0100, то требуется, чтобы выходы оставались в состоянии 10. Выходы могут поддерживаться при их прежних значениях за счет использования триггеров, установленных в состояние 1 или О, которые не должны быть чувствительны в течение действия сигнала на входе промежуточного нулевого состояния.

Реализация цепи С] показана на рис. 4.44. Цепь, обозначающая декодер, является комбинационной и обеспечивает возбуждение единицы на выходе (в устойчивом состоянии) на шинах й1, йг, . .., й„. Однако, когда входные сигналы, поступающие на декодер, изменяются, на шинах щ могут иметь место переходные процессы. Допустим, что цепь Ci первоначально была устойчивой и отвечала указанному условию возбуждения 1-точек на выходе. Выход А логического элемента И должен быть в положении О, а логические элементы И, связанные с единичными выходами триггеров, будут, следовательно, блокированы. Теперь предположим, что входы декодера изменили свое состояние. Это может привести к изменениям в нескольких переменных щ (включая переходные процессы). Если вход щ изменится на 1, то помешает установке соответствующего триггера с нулевым выходом на логический элемент ИЛИ. Если /-й триггер был первоначально установлен в положение 1, а Gj изменяется к О, то триггер устанавливается в положение О через логические элементы НЕ-ИЛИ. Выход А элемента И примет по-, ложение 1 после того, как все триггеры будут установлены в 0; Через время задержки D выходы декодера позволят триггерам установиться в положение 1. За это время выходы декодера, должны стать устойчивыми и только один выход должен быть, в положении 1. Таким образом, выход промежуточного нулевого состояния имеет длительность, приблизительно равную D, по истечении которой выходы изменяются к новому кодовому слову,.при котором возбуждается только один выход.

266 Главн 4

О

л, -Vj x.,

Рис. 4.43. Трансформация таблицы переходов.

tfV :

[т~Г)-ГШ]-

Рис. 4,44. Реализация подсхемы Cj,

м

Рис. 4.45. Часть таблицы нормального режима.

ОТ того, когда изменяются другие входы, но входная переменная не может изменяться дольше некоторого указанного интервала б [24].

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

Допустим, что автомат М первоначально был устойчивым в состоянии 1 при входах 00. Если входы одновременно или почти одновременно приходят в состояние 11, то Л1 достигает устойчивого состояния 2. Если же сначала изменяется х2 и входное состояние 01 сохраняется в течение достаточно долгого периода времени, цепь переходит к состоянию 3 в столбце 01 и остается

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

4.7.2. НЕОГРАНИЧЕННЫЕ ВХОДНЫЕ ИЗМЕНЕНИЯ

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

В СОСТОЯНИИ 3 до тех пор, пока Xi не перейдет в состояние 1. Аналогичным образом, если М проходит через входное состояние Ю и пребывает достаточно долго в этом входном состоянии, устойчивым состоянием, достигаемым в столбце 11, должно быть состояние 4. Все эти состояния могут рассматриваться как правильное функционирование автомата. С другой стороны, если вход М пребывает достаточно долго в состоянии 01, т. е. достаточно долго, чтобы начать переход к состоянию 3, но не достаточно долго, чтобы достигнуть устойчивого состояния 3 в рассматриваемом столбце, то конечное состояние, в которое перейдет автомат, не может быть предсказано на основе таблицы переходов, так как оно зависит от паразитных задержек, элементов задержки и кодирования состояний цепи, реализующей автомат УИ. Очевидно, что такая работа автомата не может рассматриваться как правильная, поскольку нарушается согласование с таблицей переходов.

Указанный выше вид неправильной работы автомата может иметь место даже в том случае, когда кодирование состояний таково, что в течение любого перехода изменяется только одна переменная состояний. Например, рассмотрим кодирование состояний, показанное на рис. 4.45. Для ранее рассмотренного перехода, если Xz изменяется от О к 1, Уг будет изменяться от О к 1. Но прежде чем г/г примет значение 1 (при введении элемента задержки в контур обратной связи), положим, что Xi примет значение 1. Это подразумевает, что цепь проходит через полное состояние (1,11), при котором содержимое следующего состояния равняется 2, что требует изменения Уз к 1. В конечном счете изменения в Уг и Уз могут распространиться через соответствующие элементы задержки и цепь может достигнуть устойчивого состояния 5. Это состояние не может быть достигнуто из первоначального полного состояния (1,00) при изменении и Хг в любом произвольном порядке, если цепь ведет себя в соответствии с требованиями таблицы переходов.

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

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

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

Допустим, что dM является максимальной полной паразитной задержкой вдоль любого контура в комбинационной части цепи, т. е. от любого входа или Уг к некоторому У^. Аналогичным образом, обозначим через dm минимальную паразитную задержку вдоль любого контура. Положим, что D

т является

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

1. Входная переменная не может изменяться больше чем один раз в течение любого интервала длиной k{dM - dm).

2. Dm> {dM - dm).

Аналогичные условия могут быть получены при использовании более реалистичной модели элементов задержки. Вместо кодирования, при котором только одна переменная изменяется в течение любого перехода, ОВП-кодирование может быть использовано для покрытия определенных дихотомий в дополнение к тем, которые требуются для предотвращения критических состязаний [24].

4.8. ДОПУЩЕНИЕ ОБ ОГРАНИЧЕННЫХ ЗАДЕРЖКАХ

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

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

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

Если применяется только x одна из этих переменных, то

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

Пример 4.22. Рассмотрим конструкцию счетчика с че-J тырьмя состояниями, обсуждавшуюся ранее и повторенную на рис. 4.46.

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

F, = ХУ2 + Xyi -f У1У2,

Y2 = %2 + xyi -f У1У2.

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

Предположим, что элементы задержки устранены и что задержки линии меньше, чем задержки логических элементов. Если цепь находится в состоянии г/i = г/2 = О, когда вход х изменяется от О к 1, то терм xpi примет значение 1, что приводит к тому, что Уг, а затем и г/г становятся равными 1. Поскольку задержки линии меньше, чем задержки логических элементов, то это изменение может достигнуть элемента И, реализующего ху2 прежде, чем х примет значение 0. (Это может произойти, если задержка в инверторе, реализующем х, значительно больше, чем полная задержка в контуре от л; к г/г через xyi.) Это приведет к тому, что г/i примет значение 1, что в конечном

Рис. 4.47, Переходы переменных состояния для счетчика с четырьмя состояниями.

Карты Карнау для Уь приведенные на рис. 4.47, показывают переходы в двух случаях. На рис. 4.47, а, который характеризует случай с введенной задержкой, вначале изменяется х, затем происходит изменение в г/г, а Уг остается фиксированным в положении 1. В случае (б) х и г/г могут измениться одновременно, так как не имеется введенных задержек. Заметим, что функция Yl для этого перехода имеет статический функциональный риск сбоя.

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

счете приведет к неправильному устойчивому состоянию

Теперь рассмотрим переход от t/i = 2 = 1, когда х изменяется от О к 1. Первое изменение приведет к тому, что примет значение 0. В выражении для Y\ термы Х1У2 и yiyz совершают переход I ->Q тогда, когда ху\ совершает переход О->\. Если оба перехода 1-50 завершаются до перехода О-у\, то Y\ может совершить переход 1->-0->-1 и цепь может перейти к неправильному устойчивому состоянию г/i = О, г/г == 1 Однако если в контурах обратных связей имеются введенные задержки достаточной величины, то терм У1У2 будет изменяться к О только после того, как терм xyi изменится к 1, что позволит избежать устойчивого риска сбоя.

л;,. Уг

Рис. 4.48. Схема НЕ-ИЛИ-И.

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

Следовательно, при реализации суммы произведений термы любого Yi не будут приводить к какому-либо переходу 1->-0.

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

Пример 4.23. Таблица переходов и кодирование состояний из рис. 4.46 повторяются на рис. 4.49, а.

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

Si = ху2, Ri ху2,

S2 = Xyi, R2 = Xyi.

Реализация этого счетчика, не имеющего задержек (при допущении ограниченной задержки), использующего RS-триг-.

. Допуская, что функции следующего состояния реализуются в виде суммы поризведений, появление входных переменных с дополнениями может быть предотвращено путем разложения термов, содержащихся в двухуровневой форме НЕ-ИЛИ-И, в которой переменные с дополнениями и переменные состояний соединяются в одном и том же логическом элементе НЕ-ИЛИ. Например,с помощью преобразования XiXyiyz = Х2 (Х1У1У2) = л^а X X (1 + У1 + Уг) получаем реализацию, показанную на рис. 4.48.

Пары НЕ-ИЛИ-И, тип которых показан на рис. 4.48, разрешают состязания между изменением дг-переменных и изменениями у-переменных так, чтобы цепь реагировала вначале на первое изменение. Так как используется ОВП-кодирование, то

о

1>

г h

Рис. 4.49. Реализация счетчика с четырьмя состояниями, не имеющего задержек.

пары НЕ-ИЛИ-И реагируют сначала на изменения входных переменных (а не их дополнений. - Прим. ред.). Переход 1-,-0->-1 может происходить также на выходе Yu если на одном или более входах логического элемента ИЛИ происходит переход О-на других входах происходит переход 1->-0, а часть входов остается в состоянии 0. Это случается тогда, когда целый подкуб перехода) из перехода 1-1 не может быть покрыт одним термом. Переход 1->-0->-1 может быть предотвращен путем использования терма вида LZft для покрытия единиц в подкубе перехода, где - терм-произведение, которое покрывает подкуб перехода, а Zfe -сумма термов, покрывающих все нулевые точки и ни одну из единичных точек

) Для перехода (Qi, Ij) (Qv,., h) подкуб перехода состоит из всех точек в карте У, идентифицированной наименьшим кубом, содержащим (qt, Ij] и

(Qm, Ih).

геры, показаны на рис.-4.49,6. Заметим, что в этом простом примере разложение НЕ-ИЛИ-И сводится только к логическим элементам И или логическим элементам НЕ-ИЛИ. Однако требуются оба типа логических элементов, соединенных как показано на рис. 4.48, для того чтобы предотвратить риск сбоев без использования задержек при реализациях произвольных таблиц переходов.

Другой метод предотвращения переходов 1->-0->-1 заключается в использовании специального типа разложения. При обсуждавшемся ранее разложении НЕ-ИЛИ-И трудности, связанные с состязаниями между дополнениями входных переменных, и переменными состояниями разрешаются за счет того, что

Lft. Zfe может покрывать нулевые точки вне Ln для того, чтобы упростить логическую цепь. При переходе Zu не будет идентично О тогда и только тогда, когда имеется статический функциональный риск сбоя в Yi для этого перехода. При реализации термов Zft, там, где это необходимо, должно быть использовано разложение НЕ-ИЛИ-И. Однако не должно зависеть от изменения входной переменной, а разложение Lh не является необходимым. Общая форма реализации терма LnZn показана на рис. 4.50.

Рис. 4.50. Обобщенная фор.ма реализации терма LkZk *

При этой реализации переходный процесс 1 ->-0->-1 может произойти на выходе тогда и только тогда, когда мгновенно переходит к 0. Это может произойти только в том случае, если один из входов на логический элемент НЕ-ИЛИ равняется 1.

Рис. 4.51. Карты Карнау для переменных состояния.

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

Пример 4.24. Карты Карнау Yi и Уг из примера 4.22 повторены на рис. 4.51. Переходы I -> 1 в У: и Уг, которые не могут быть покрыты одиночными термами, показаны стрелками. Для У] мы имеем терм Li = уу. Имеется одна нулевая точка, которая не может быть покрыта Z\=xy2- Аналогично для Уг получаем Lz - У2 и Z2 = хух. Полными уравнениями для Y\ и