Рис. 5.64 Цепь синхронизации.

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

Штронный сдвиговый регистр

Асинхронный сдеиговый pezt

регистр

т

Чсинкрониые импульсы

Рис. 5.65. Асинхронная цепь с минимумом обратных связей.

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

Основной элемент сдвигового регистра определяется по таблице переходов (рис. 5.66, с), где / - выход предыдущего

импульса, должно выполняться соотношение Гмин параз. где Dnapas-максимальная задержка в распространении изменения Xj через схему сложения по модулю 2 без прохождения через Di. Изменение сигнала S может далее использоваться как так-

элемента, а S - выход цепи, изображеннай на рис. 5.64. Выход Z является входом / следующего элемента (рис. 5.66,6). Изменение на входе приводит к изменению S, что в свою очередь вызывает сдвиг во всех сдвиговых регистрах на один разряд вправо. Предполагается, что состояние входа не изменится до тех пор, пока не завершится этот сдвиг, и что задержка на линиях меньше, чем на логических схемах; это гарантирует неодновременное изменение входов /и5. Если не сделать такого предположения, то большая паразитная задержка вызвала бы искажение

li-l

r I

Рис. 5.66. Таблица переходов основного элемента (с); асинхронный сдвиговый регистр (б).

в работе сдвигового регистра, например, следующим образом. Рассмотрим сегмент сдвигового регистра (рис. 5.67) и предположим, что в начале все три элемента находятся в состоянии 0. Если S изменится с О на 1 и 1 подается слева, то сдвиговый регистр перейдет в состояние 100. Если в линии, соединяющей S с элементом 2, присутствует большая паразитная задержка, как это показано на рисунке, то это может вызвать состязание между изменением в элементе 1 и изменением на S, и, таким образом, в результате окончательным содержимым сдвигового регистра будет ПО вместо 100.

Цепь iVi, изображенная на рис. 5.65, создает на выходе сигнал Z и функцию обратной связи /, которые являются функциями последних п входов и значений / (что в асинхронной интерпре-

□ ЗпЗержко

Рис. 5.67. Сегмент сдвигового регистра.

быть генерированы переходные состояния. Они не вызывают беспокойства для /, поскольку основной элемент сдвигового регистра не содержит существенного риска сбоя или rf-трио (см. упражнение 4.10). Ангер [27] показал, что на такую таблицу помехи в f не имеют влияния. Помехи же на z-выходах могут быть устранены путем использования на каждом выходе одного элемента сдвигового регистра.

Рис. 5.68. Таблица переходов, пример 5.29.

Пример 5.29. Из таблицы, представленной на рис. 5.68, видно, что устойчивые состояния в каждом столбце имеют различные значения выходов. Следовательно, последнее значение z и последняя входная комбинация определяют текущее состояние. Выход в любое время может быть определен на основании текущего и предыдущего значений входов и последнего значения

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

Элемент i Эяетет z Элемент 3

выхода, как показано ниже:

Z = ((XiX2)d Zd) + 1X2 ((1X2)4 + (*l>J2)d + {XyXi +

+ {xxX2)a Za + {xixa Ч + (JCi)d Zd) + + XxXz ((xi)d Zd + (xiXo) Zd + (XiX2)d za),

где индекс rf, используемый с переменными или термами, означает их предыдущее значение.

5.11. СДВОЕННЫЕ ПОСЛЕДОВАТЕЛЬНОСТНЫЕ ЦЕПИ И СЧЕТЧИКИ

Большой интерес при декомпозиции цепей представляет сдвоенная последовательностная цепь, показанная на рис. 5.69.

Предполагается, что сигналы логических элементов gi и изменяют свои значения в соответствии с последовательностью 0-1-0 и никогда одновременно не принимают значения 1. Если gl - 1, то выходные сигналы устройств памяти П1 используются для изменения состояния устройств памяти П2, а если g2=l.

тгтккт цепь

Рис. 5.69 Сдвоенная последовательностная цепь.

то соответственно наоборот. Когда gi становится равным 1, предполагается, что П1 и входы устойчивы, а когда g2 становится равным 1, то предполагается, что устойчивыми являются входы и П2. Риск сбоя в комбинационных цепях вследствие этого может не учитываться.

Использование сдвоенных цепей позволяет эффективно проектировать счетчики (не только использование, но даже просто разработка теории сдвоенных цепей) [19,28].

Представленная на рис. 5.70 таблица М является асинхронным счетчиком, который считает (единичные входы) по модулю 4.

Общепринятая реализация этой цепи может быть получена при применении кодирования состояний тремя переменными (коды Грея), обозначенными на рис. 5.70 как кодирование № 1, обладающими тем свойством, что при любом переходе изменяется только одна переменная. Реализация счетчика Вэйра[28] использует четыре переменные состояний (кодирование № 2), но выходная логическая схема значительно упрощается. Реализация счетчика Вэйра по модулю 4 показана на рис. 5.71.

КоЬирббШИеШ

KoSup6samef/s2

Рис. 5.70. Счетчик по модулю 4.

В уравнениях, приведенных на этом рисунке, S н R обозначают соответственно возвратные и установочные входы PS-триг-геров. Переменные состояний j/i и уг образуют П1, а уз и yt - П2. Переменные yi и у2 определяют один из вариантов ОВП-кодирования Лю для входного столбца О автомата М, а уз и у^ определяют кодирование Лю для входного столбца 1. Следовательно, когда на входе О, то Yi и Уг являются устойчивыми, а Уз и У4 являются функциями ух и у^, а когда на входе 1, то наоборот; этим обеспечивается сдвоенная реализация.

Сигналы логических элементов giHg-2He обязательны в цепи счетчика, если входы Ii и /г таковы, что никогда не равны 1 одновременно. Достигается это путем использования цепи, изображенной на рис. 5.72. (Этот факт является также основным

Рис. 5.71. Счетчик Вэйра.

>

Рис. 5.72 Цепь логического элемента в сдвоенной цепи.

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

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

Оказывается возможным получение сдвоенных цепей счетчика, которые требуют меньшего числа переменных состояний, чем счетчик Вэйра. Примером этого является счетчик Мэйни [19]. Для счетчика Вэйра по модулю М требуется 2S переменных состояний, где S = riog2Ml, в то время как для аналогичного ему счетчика Мэйни требуется только S К переменных состояний, где К= riog2(S-- 1)1. Логическая схема, необходимая для реализации счетчика Мэйни по модулю 8, показана на рис. 5.73.

При такой реализации переменные состояний уь и уз образуют П1 и могут также использоваться в качестве выходных сигналов счетчика. Переменные у4 и г/5 задают информацию о следующем состоянии переменных в П1, которые должны быть изменены. Если в качестве устройств памяти используются Т'-триггеры, то реализация счетчика может быть несколько упрощена, поскольку второе множество переменных требуется для задания информации только о том, какое множество переменных должно быть инвертировано. Отсюда следует, что счетчик Мэйни с Т'-триггерами требует только S + riog2 51 переменных состояний, где S определяется так же, как и раньше.

Если асинхронная цепь ограничена таким образом, что только одна входная переменная изменяется при любом переходе, и если h состоит из всех состояний входа с нечетным числом единичных разрядов, h состоит из всех состояний входа с четным числом единичных разрядов, то входная последовательность поочередно использует члены /i и h- В этом случае удается построить счетчик Вэйра путем разделения таблицы переходов М на две подтаблицы: Mi, состоящей из столбцов Ii, и Мг, состоящей из столбцов h, и кодированием состояний переменными Уи для Ml и yzi для Мг для образования ОВП-кодирования Лю. Два состояния Mi (или Мг) могут иметь один и тот же код переменных состояний в у и (или угг), если элементы следующего состояния являются идентичными для всех входов в hih)- Такое кодирование приводит к реализации с помощью сдвоенных цепей.

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

, = 1У4У5

= 1,У4У5

2 = 1У4

S3 = ,У4У5

л = X

г1У2Уз+ У1Уз 2(У|Уз + УгУ1)

Рис. 5.73. Счетчик Мейни.

Рис. 5.74. Таблица переходов, пример 5.30.

устройств памяти на Р5-триггерах, задается следующими уравнениями:

Sii == Ij {хг),

/1 (л:1п + xiyn),

S22 =/1 toi + Jii/u) =/ii/п, 22=1(1).

где

11 -Xi@X2,

12 = Xi®X2.

Аналогичные цепи, часто называемые двухфазовыми синхронизируемыми цепями, могут использоваться при проектировании синхронных автоматов, имеющих два системных множества iti и П2, такие, что Р{п1,П2), Р{п2,п\) и 3x1-1x2 = 0. Для асинхронных цепей с многократным изменением входных сигналов концепция сдвоенной реализации может быть обобщена на -кратную реализацию.

БИБЛИОГРАФИЯ И КОММЕНТАРИИ

Первыми разработали алгебру разбиений и алгебру пар и применили их для проектирования последовательностных цепей с уменьшенной зависимостью Хартманис и Стирнз [13]. Вэйнер и Смит [29] разработали процедуру, основанную на алгебре разбиений, для получения хорошей реализации с уменьшенной зависимостью. Применение к цепям с элементами памяти на триггерах изложено по Харлоу и Коутзу [7]. Достаточность одного контура обратной связи доказана Фридманом [4], она также была продемонстрирована Бржозовски [1], который рассмотрел и соединение триггеров без обратной связи [2]. Первые работы по использованию обратной связи в последовательностных цепях были написаны Хартманисом и Стирнзом [11] и Мак-Класки [20]. Задача реализации с помощью сдвиговых регистров была изучена Дэвисом [3], Мартином [18] и Николзом [22]. Итеративная декомпозиция в терминах перестановочных и возвратных автоматов изложена по Хартманису [14], она базируется на работах Зейгера [30] и Крона и Роудза [17].

Тан, Менон и Фридман [25], а также Кинней [16] рассмотрели задачи, связанные с построением структурно простых асинхронных цепей, а Су [24] показал методы реализации таких цепей на сдвиговых регистрах. Холл [6] формализовал концепцию сдвоенных цепей, которые были использованы при проектировании счетчиков Вэйром [28] и Мэйни [19]. Эта методика впоследствии была обобщена Фридманом и Меновом [5].

ЛИТЕРАТУРА

1. Brzozowski J. А., On Single-Loop Realizations of Sequential Machines, Information and Control, vol. 10, pp. 292-314, June 1967.

2. Brzozowski J. A., About Feedback and SR Flip-flops, IEEE Trans, on Computers, vol. C-20, p. 476, April 1971.

3. Davis W. A., Single Shift-Register Realizations for Sequential Machines, IEEE Trans, on Computers, vol. C-17, pp. 421-431, May 1968.

4. Friedman A. D., Feedback in Synchronous Sequential Switching Circuits, IEEE Trans, on Electronic Computers, vol. EC-15, pp. 354-364, June 1966; also Ph. D. thesis, Columbia University, 1965.

5. Friedman A. D., Menon P. R., Design of Generalized Double Rank and Multiple Rank Sequential Circuits, Information and Control, vol. 15, pp. 436-451, November 1969.