ВОВ, которые не покрывают некоторую дихотомию, и, следова^ тельно, имееется по крайней мере г - 3 ( ) 2 (-g- массивов, которые покрывают все дихотомии. Найдем наименьшее целое положительное значение т, а именно:

2 >3 1 >3

т >--If - > 20 flog2Rl -= 20So.

log. [-]

Таким образом, 20So переменных являются достаточными для универсального однозначного ОВП-кодирования п состояний. Однако эта граница не является конструктивной. Такой границей, применимой ко всем таблицам, является (So + 55с/б), а другая граница, пропорцио-ная Si, при некоторых ограничениях на число состояний была предложена Фридманом и др. [6].

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

Если коды i и i присваиваются состоянию i, то рис. 4.28 представляет собой универсальное кодирование для таблицы с шестью состояниями при двух кодах на состояние. Коды, присваиваемые каждому состоянию, являются взаимно дополняющими. Переходы в таблице переходов выполняются следующим образом. Если цепь находится в состоянии qi и следующи.м

вание шести состояний при многозначном ОВП-кодировании.

состоянием является q то переход должен быть сделан к коду состояния qj, который отличается от кода qu из которого совершается переход, при минимальном числе переменных. Например, рассмотрим переход из состояния 1 в состояние 3. Если цепь находится в состоянии 00000, представляющем состояние!, то следующее состояние должно быть 00! !0. С другой стороны, если в данный момент состояние 1 представляется кодом 11111, то следующим состоянием должно быть 11001. Проверяя подкубы переходов всех переходов, можно показать, что присваивание кодов, показанное на рис. 4.27, является универсальным ОВП-кодированием для таблицы с шестью состояниями при двух кодах на состояние [6]. Можно показать, что универсальное однозначное ОВП-кодирование для таблицы с шестью состояниями требует 7 переменных по сравнению с 5 переменными, требуемыми при двух кодах на состояние.

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

Универсальное ОВП-кодирование удовлетворяет все дихотомии вида {qu qj-, q, qm) и называется системой разделения {2,2). Такое кодирование может быть использовано для реализации любой таблицы нормального режима, если во всех переменных состояния применяются задержки. Кодирование состояния, которое удовлетворяет всем дихотомиям вида {qu qj, Qk), называется системой разделения {2,1). Присваивание кодов состояний, которое присваивает однозначный код каждому состоянию, удовлетворяет все дихотомии вида {qf, qj) и называется системой разделения {1, 1). Маго [14] были разработаны канонические реализации таблиц переходов нормального режима, которые использовали кодирование состояний, соответствующее системам разделения (2, 1) и (1, 1). Если элемент задержки располагается в каждой переменной состояния и как вход Yu так и выход iji являются входами в логику возбуждения при смене состояний, то для реализации любой таблицы нормального режима может быть использовано кодирование состояний, соответствующее системе разделения (2, 1). Если элемент задержки располагается в каждой переменной и каждая переменная состояния, а также вход и выход каждого элемента задержки являются входами в логику возбуждения, то для реализации

4.4.4. КОДИРОВАНИЕ СОСТОЯНИЙ ТАБЛИЦ ПЕРЕХОДОВ С МНОГОКРАТНЫМ ИЗМЕНЕНИЕМ ВЫХОДА

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

Если для таблиц переходов МИВ должны быть использованы однозначные ОВП-кодирования такого типа, который обсуждался в предыдущем разделе, то необходимо гарантировать, что переходы не приведут к окончательному устойчивому состоянию без прохождения через все указанные промежуточные состояния. Например, если столбец таблицы МИВ содержит переход Qi--qu, то переход должен быть совершен через состояние qj. Это может быть выполнено, если потребовать, чтобы кодирование покрывало дихотомии {qt; qj, qn) и [qi, qy, qu) в дополнение к дихотомиям, требуемым для устранения критических состязаний. Если столбец 1т содержит переходы Qi-Qj и Qh-qj, а также Z{qi,I) ф Z{q, fm), то дихотомии {qu qj-, qh) и {qu qj, qi) должны быть покрыты таким образом, чтобы цепь не давала неправильного выхода [23].

4.5. ОПРЕДЕЛЕНИЕ У-МАТРИЦ -

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

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

->-110. Все другие переходы являются переходами между смежными состояниями.

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

Пример 4.16. Рассмотрим таблицу переходов, представленную на рис. 4.30, а, и однозначное ОВП-кодироваиие с тремя переменными, взятое из примера 4.13 и показанное справа от таблицы переходов. Связанная с этим кодированием У-матрица показана на рис. 4.30, б. Если код присваивается состоянию q а N{qi, Ik) = qj, то содержимое следующего состояния этого кода в столбце представляет собой код, присваиваемый состоянию qj. При этом допускается одновременное изменение всех переменных. Так как эти переменные могут изменяться в любом порядке, должны быть определены все точки в подку-бе перехода T{qi, qj) в столбце 4, связанные с кодом, который присваивается состоянию qj. Таким образом, поскольку подку-бом перехода, связанного с переходом из состояния 3 к состоя-

разделяемых строк или ОВП-кодирования, неприсвоенные коды могут быть введены во время переходов. В этом случае содержимое У-матрицы должно быть определено таким образом, чтобы переход был должным образом завершен. Содержимое матрицы, которое должно быть определено, и способ его определения зависят от типа используемого кодирования. Все возможные промежуточные коды для любого перехода должны быть определены. В дополнение к этому содержимое матрицы, соответствующее коду для состояния qi в столбце Ih, не всегда будет равно N {qi, h)- Если это является частью многошагового перехода, то содержимое может соответствовать промежуточному состоянию при переходе. Следующие примеры демонстрируют конструкцию У-матрицы при кодировании с помощью множества разделяемых строк и при ОВП-кодировании.

Пример 4.15. Рассмотрим таблицу переходов, показанную на рис. 4.29, а, и кодирование состояний с помощью множества разделяемых строк, первоначально осуществляемое в примере 4.8. Матрица У из рис. 4.29, б получается, если переходы делаются такик образом, как показано на рис. 4.20. Переход из состояния 5 в состояние 6 в столбце 00, указанный на рис. 4.20, является многошаговым переходом 011->-111->-101. Следовательно, содержимое следующего состояния для 011 в столбце 00 определяется как 111, а содержимое следующего состояния неназначенного кода 111 определяется как 101 в столбце 00. Аналогичным образом, переход от состояния 4 к состоянию 5 в столбце 01 определяется как 110->-111->-011, а переход от состояния 6 к состоянию 4 в столбце И как 101->-111->-

(5) (2) (4)

(6) (3)

О О

1 I I 1

О О

о 1 1

о о 1 I

о

Рис. 4.29. Определение У-матрицы при кодировании с помощью множества разделяемых строк (пример 4.14).

иию 1 в столбце 00 таблицы на рис. 4.30, а, является--О, то

все четыре кода ООО, 100, 010 и ПО в У-матрице имеют содержимое входов ООО, соответствующее состоянию 1.

В предыдущих примерах игнорировались выходы последовательностной цепи. Если в таблице переходов нормального режима

N{qi, fk) = Qi, то Z(,. h) = Z{qi, /,).

(1)

(2) (3) (4)

Рис. 4.30. Определение У-матрицы для однозначного ОВП-коллрования (пример 4.15).

Для того чтобы поддерживать все выходы постоянными в течение перехода -q все точки, которые могут встретиться в течение перехода, должны быть присвоены выходу Z{qi, 1 ). Если при кодировании с помощью множества связанных строк или кодировании с помощью множества разделяемых строк используется многошаговый переход, то все коды при таком переходе присваиваются этому выходу в столбце /. При однозначном ОВП-кодировании все точки в подкубе перехода T{qi, q,) присваиваются этому выходу в столбце 1ц.

Асинхронные последовательностные цепи 241 4.6. ЗАДЕРЖКИ И РИСКИ СБОЯ

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

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

J-L Jl r

в

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

Представляет интерес два типа задержек. Первый тип - чистая задержка, которая при подаче на вход воздействия f{t) обусловливает на выходе сигнал f{t - D), где D - величина задержки. Таким образом, выход является просто задержанным на фиксированную величину D, а формы выходных и входных

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

Можно сделать предположение, что паразитные задержки имеют как компоненты чистой, так и инерционной задержек.

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

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

Асинхронные последовательностные цепи 243 4.6.1. РИСК СВОЯ В КОМБИНАЦИОННЫХ ЦЕПЯХ

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

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

Лемма 4.2. Предположим, что / является такой комбинационной функцией, что /(/ ) = / (/г) = О, где h и h являются входными состояниями, которые отличаются только в одной переменной Хи. Реализация двухуровневой суммы произведений имеет статический риск сбоя в нуле при переходе между h и h тогда и только тогда, когда она содержит терм, реализуемый посредством логического элемента И, имеющего оба входа х^ и Хи, а оставшиеся входы этого логического элемента являются 1 для обоих входных состояний II и /2.

Доказательство. Достаточность. Рассмотрим переход /1

h и, без потери общности, положим л: z= О в В этом случае, когда входным состоянием является /ь выходы всех логических элементов И должны быть равны нулю. Рассмотрим логический элемент, удовлетворяющий условиям леммы. Допустим, что паразитные задержки таковы, что изменение О->1 в Хи достигает элемента И прежде, чем произойдет изменение 1->-0 в Хи. Таким образом, все входы логического элемента И могут быть в состоянии 1 в течение достаточно долгого времени, в результате получится ложный единичный выход, что приведет к последовательности О-> 1 ->-0 на выходе цепи.

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

такую выходную последовательность только тогда, когда по крайней мере один вход подвергается изменению О->-1 и по крайней мере один вход подвергается изменению I->-0, в то время как остальные входы остаются в фиксированном состоянии 1. Поскольку в течение перехода входных сигналов может изменяться только входная переменная х^., изменяющимися входами могут быть только Xh.и Xh, а оставшиеся входы этого логического элемента должны быть в состоянии 1.

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

Лемма 4.3. Для комбинационной функции / положим, что h и h являются входными состояниями, которые отличаются только в одной переменной х^, и положим, что - fih) = 1. Реализация двухуровневой суммы произведений будет иметь статический риск сбоя в единице при переходе между 1\ и h тогда и только тогда, когда реализация не содержит терм-произведения, которое равно 1 для обоих /] и h.

Доказательство. Достаточность. Если условие леммы удовлетворяется, то множество термов, которые равны I для входного состояния 1\, не пересекаются с множеством термов, которые равны 1 для входного состояния /г. Таким образом, в течение перехода h-v/g выходы одного множества логических элементов И изменяются от О к 1, а другого множества от 1 к 0. Поскольку не остается входов на логический элемент ИЛИ, фиксированных в состоянии 1, все входы на элемент ИЛИ могут быть в состоянии О в течение достаточно долгого времени для того, чтобы получить на выходе переходный процесс 1-*-0->--i-I.

Необходимость. Допустим, что должен быть терм, который равняется 1 для обоих h и h. Очевидно, что такой терм не должен зависить от х^-переменной, которая изменяется в течение перехода. Этот терм будет иметь фиксированное значение I в течение всего времени перехода и предотвратит возможность переходного процесса 1->0->-1 на выходе.

Пример 4.17. Рассмотрим цепь, показанную на рис. 4.32, а, и переход от входного состояния И1 к 011. Когда входным состоянием является 111, то а-\, b - 0. Когда вход Х\ изменяется к О, сигнал а изменяется от 1 к О, тогда как сигнал b изменяется от О к I. Если изменение О->\ сигнала b дости-