6. Hall А. D. Jr., Synthesis of Double Rank Sequential Circuits, Princeton University Technical Report № 53, December 1966.

7. Harlow C., Coates C. L., On the Structure of Realizations Using Flip-Flop Memory Elements, Information and Control, vol. 10, pp. 159-174, February 1967.

8. Hartmanis J., Alaximal Autonomous Clocks of Sequential Machines, IRE Trans, on Electronic Computers, vol. EC-ll, pp. 83-86, February 1962.

9. Hartmanis J., Loop-Free Structure of Sequential Alachines, Information and Control, vol. 5, pp. 25-43, March 1962.

10. Hartmanis J., Stearns R. E., Some Dengers in State Reduction of Sequential Machines, Information and Control, September 1962.

11. Hartmanis J., Stearns R. E., A Study of Feedback and Errors in Sequential Machines, IEEE Trans, on Electronic Computers, vol. EC-12, pp. 223-232, June 1963.

12. Hartmanis J., Stearns R. E., Pair Algebra and Its Application to Automata Theory, Information and Control, vol. 6, pp. 485-507, December 1964.

13. Hartmanis J., Stearns R. E., Algebraic Structure of Sequential Machines, Prentice-Hall, Englewood Cliffs, N. J., 1966.

14. Hartmanis J., On the Structure of Finite Automata (не опубликовано).

15. Jump J. R., A Note on the Iterative Decomposition of Finite Automata, Information and Control, vol. 15, pp. 424-435, November 1969.

16. Kinney L., Decomposition of Asynchronous Sequential Switching Circuits, IEEE Trans, on Computers, vol. C-19, pp. 515-529, June 1970.

17. Krohn K. В., Rhodes J. L, Algebraic Theory of .Vlachines I, Prime Decomposition Theorem for Finite Semigroups and Machines, Trans. Amer. Math. Soc, vol. 116, pp. 45C-464, 1965.

18. Martin R. L., Studies in Feedback Shift-Register Synthesis of Sequential Machines, Proc. Symposium and Automata Theory, pp. 240-251, 1967.

19. Mayne R. H., The Binary Counter: A Novel Logical Design, Bell Telephone Laboratories Internal Memorandum, 1958 (не опубликовано).

20. McCluskey E. J., Reduction on Feedback Loops in Sequential Circuits and Carry Leads in Iterative Networks, Information and Control, vol. 6, pp. 99- 118, June 1963.

21. McCluskey E. J., Unger S. H., A Note on the Number of Internal Variable Assignments for Sequential Switching Circuits, IRE Trans. Electronic Computers, vol. EC-8, pp. 439-440, December 1959.

22. Nichols A. J., Minimal Shift-Register Realizations of Sequential Machines, IEEE Trans, on Electronic Computers, vol. EC 14, pp. 688-700, October 1965.

23. Su C. C, Yau S. S., Unitary Shift-Register Realizations of Sequential Machines, IEEE Trans, on Computers, vol. C-17, pp. 312-324, April 1968.

24. Su Y. H., Shift Register Realizations of Asynchronous Sequential Machines, Information and Control, vol. 15, pp. 226-234, September 1969.

25. Tan C. J., Menon P. R., Friedman A. D., Structural Simplifications and Decomposition of Asynchronous Sequential Circuits, IEEE Trans, on Computers, vol. C-18, pp. 830-838, September 1969.

26. Unger S. H., A Theorem of Feedback in Sequential Switching Circuits, Quarterly Progress Report, Research Laboratory of Electronics, MIT, April 15, 1955.

27. Unger S. H., Hazards and Delays in Asynchronous Sequential Switching Circuits, IRE Trans, on Circuit Theory, vol. CT-6, pp. 12-25, March 1959.

28. Ware W. H., The Logical Principles of a New Kind .of Binary Counter, Proc. IRE, vol. 41, pp. 1429-1437, October 1953.

29. Weiner P., Smith E. J., Optimization of Reduced Dependences for Synchronous Sequential Machines, IEEE Trans, on Electronic Computers, vol. EC-16, pp. 1429-1437, October 1953.

30. Zeiger H. P., Cascade Synthesis of Finite State Machines, Information and Control, vol. 10, pp. 419-433, April 1967.

376 Глава 5 УПРАЖНЕНИЯ

5.1. Определите однозначное кодирование состояний таблицы состояний, изображенной на рис. 5.75, переменными состояний уи и Уз, такими, чтобы У] не зависела от х, z не зависела от уи а Уз не зависела от у^ и уг, предполагается испольчопание D-триггеров.

Рис. 5.75. К упражнению 5.1.

5.2. а) Для таблицы состояний автомата М, представленной на рис. 5.76, заполните элементы следующих состояний, обозначив их как а, b к с так, чтобы автомат М по возможности являлся определенным событием. Определите, все возможные значения тех элементов, которые делают автомат М определенным.

О I

Рис. 5.76. К упражнению 5.2.

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

5.3. Дли таблицы состояний М, представленной на рис. 5.77, а, определите, какие из трех функций /ь 2 и fs, если такие су.-дествуют, являются функциями обратной связи для М.

5.4. Для каждой из таблиц состояний (рис. 5.78) определите, если это возможно, реализацию с помощью сдвигового регистра.

5.5. Для каждой из таблиц состояний (рис. 5.79) определите двоичную функцию обратной связи.

М

а

Рис. 5.77. К упражнению 5.3.

о а

2 3 4 5 б 7

5 5 2 6 7 7 4 4

Рис. 5.78. К упражнению 5.4.

а

Рис. 5.79. К упражнению 5.5.

Рис. 5.80. К упражнению 5.6,

5.7. а) Докажите, что если я является разбиением полностью определенной таблицы, то М(л) является разбиением. Используйте этот результат для определения М (14,235) для таблицы, представленной на рис. 5.81.

О I

Рис. 5.81. К упражнению 5.7.

б) Является ли для полностью определенных таблиц М(я) разбиением, если я является системным множеством?

в) Если я является разбиением и таблица состояний определена не полностью, то может ли М являться разбиением?

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

5.6. На рис. 5.80 представлены таблица переходов асинхронной цепи и переменная состсяний yi. Определите еще две переменные состояний г/г и г/з, такие, чтобы уи у2 и ys являлись частью однозначного ОВП-кодирования, в котором, если это возможно, Vi не зависит от i/s, а Уг от yi. .. .

Рис. 5.82. К упражнению 5.9. .. ; .

5.10. Для таблицы состояний (рис. 5.83) и переменной состояний определите вторую переменную состояний г/2, такую, чтобы yi и У2 определяли правильное кодирование состояний, при котором возбуждение триггера у2 было бы независимым от г/i в случаях, когда используются а) 7-триггеры, б) /?5-триггеры.

Рис. 5.83. К упражнению 5.10.

5.11. Автомат М с конечным числом состояний имееет на входе произвольную последовательность. В некоторый момент, когда предполагается, что автомат примет состояние а, возникает ошибка, и автомат устанавливается в состояние Ь. Предполагаем, что это произошло не из-за какой-либо постоянной ошибки и что в следующий момент автомат сделает правильный переход. Говорят, что такая ошибка врежнтя, если существует некоторое целое k, такое, что для любой входной последовательности / длиной k N{a,I)=. ~N(b,l). Докажите или опровергните следующее утверждение: в автомате М все ошибки (т. е. подмена любой пары состояний) являются временными в том и только том случае, если М является определенным событием (реализуемым без какой-либо обратной связи).

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

Рис. 5.84. К упражнению 5.12.

б) Определите процедуры получения двоичной функции обратной связи f(Q), независимой от входа в случае таблицы синхронной цепи.

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

5.13. а) Для асинхронной таблицы переходов (рпс. 5.85) и показанной переменной состояний t/i определите еще две переменные состояний и уз.

о о о I I

Рис. 5.85. К упражнению 5.13.

такие, чтобы Уи у2 и уз образовали однозначное ОВП-кодирсвание (предполагается наличие памяти на элементах задержки при У, независящем от уз).

б) От каких переменных зависит переменная

в) Or каких переменных зависит переменная уз? 5.14. Рассмотрите таблицу состояний (рис. 5.86).

а) Определите кодирование состояний переменными yi, У2 и уз, такое чтобы

Yi = h(x,y,). Уз =

Уг = h {х, У2, Уз), Z -.

h(x. У2. Уз), 8(х, Уи yi).

5.12. а) Для таблицы (рис. 5.84) определите, если это возможно, двоичную функцию обратной связи f(Q,I).

Реализации последовательностных автоматов 381 Предполагается, что в качестве элементов памяти используются £)-триг-

Рис. 5.86. К упражнению 5.14.

б) Определите кодирование состояний переменными уи Vi и уз, такое, чтобы

У\ = Н (х, yi),

У2 = f2 (г/2. Уъ) (не зависит ст дс), Ysfsix, У2. Уз).

Предполагается, что в качестве элементов памяти используются С-триг-

Глава 6 МОДУЛЬНОЕ ПРОЕКТИРОВАНИЕ ЛОГИЧЕСКИХ СЕТЕЙ

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

В этой главе мы рассмотрим три связанных между собой раздела: универсальные логические модули (УЛМ), модульная реализация последовательностных автоматов и клеточные структуры. *

6.1. УНИВЕРСАЛЬНЫЕ ЛОГИЧЕСКИЕ МОДУЛИ

Большая степень интеграции позволяет создавать на одном кристалле (чипе) цепи, содержащие много логических элементов. В результате интеграции появилась возможность создания больших блоков, способных реализовывать несколько функций заданного числа переменных. Если модуль может реализовать все п-входные комбинационные функции, то он называется уни-версалньым логическим модулем п-го порядка (п-УЛМ). При проектировании таких модулей главной задачей является минимизация числа выводов из корпуса чипа, поскольку это оказывает значительно большее влияние на стоимость выполненной на одном чипе большой степени интеграции, чем число логических элементов, размещаемых на чипе. Универсальные логические модули классифицируются по типу допустимого вида входных сигналов (а именно с парафазными входными сигналами или одинарными входными сигналами) и видам соединений между выводами. Модуль, реализующий функцию U{Z\,Z2,...,Zm), является п-УЛМ, если любая функция f{xi, х^, . -., а: ) п переменных может быть получена путем замещения каждого Zi элементом множества / = {О, \ ,Xi,X2,..., Хп, gu g2, , gs), в котором каждая функция gi является функцией переменных [xi, Х2,..., Хп}. Следующие типы УЛМ получены выбором различных множеств /.

1) УЛМ, для которых / == {О, 1, л:*, х*, ..., л;*}, где х] является либо Х{, либо Xl (но не оба одновременно), требуют только одинарных входов, а также констант О и L

2) Другой тип УЛМ получается в том случае, когда одна из п переменных представляется в виде парафазного входа, авсе остальные входы являются одинарными, т. е./==0,\,х\,х\, ...

3) Если все входы парафазные, / = {О, 1, Xi,Xi, х^, Хг, ..., х^,

- 4) Наиболее общий вид УЛМ определяется в случае / = {0, 1, Xl, Xl, Х2, Х2, Хп, Хп, gl, g2, gs}, где функции gi являются различными функциями входных переменных {xi, Xz, ..., Хп}. В этом случае УЛМ должен реализовать функции gi, iis, таким образом, чтобы любая функция могла быть реализована путем соединения соответствующих выводов.

Рассмотрим теперь канонические реализации каждого из указанных выше типов УЛМ. Хотя конкретные реализации для небольшого числа переменных [5] часто требуют меньшего числа выводов, чем канонические реализации, последние полезны для оценки верхних границ числа требуемых выводов.

6.1.1. УЛМ с ОДИНАРНЫМИ ВХОДАМИ

Каноническая реализация п-УЛМ может быть получена из рассмотрения суммы минтермов п переменных. Любая функция п переменных может быть выражена в виде

/ = ЩХ1Х2, ..., х„ + aiXiXz, ..., Xn-iXn + ... ... 1- an X2, ..., x iX ~\- а.п х^х^, ..., х^,

где ai = О, 1 и О < г < 2 - 1.

Пусть Z = {Zi, Z2, Zn+2n) и

V{z) = ZiZ2, 2 Z +i+ ... +21Z2.....2 Z +2 =

= Z Wi-l {Zi, Z2, . . ., Zn) Zn+i, i = l

где ntj, 0 / 2 -, являются минтермами переменных Zi, Z2, Zn. Модуль, реализующий функцию t/(z), является

n-УЛМ, поскольку любая функция может быть реализована подстановкой Zi = Хг, \ in, в Zj = aj i, n-\-l / n + 2*. Число выводов для входных сигналов, требуемых при такой реализации п-УЛМ, равно n-f2. Входные переменные Zi, где п 4-1 г п -f 2 , соединены с логическими константами О или 1.

6.1.2. УЛМ С ОДНИМ ПАРАФАЗНЫМ ВХОДОМ

Число выводов, требуемых в п-УЛМ, может быть уменьшено, если одну из переменных представить в виде парафазного входа.

Рис. 6.1. УЛМ трех переменных с одним парафазным входом.

Введем для определения выводов, обозначенных через fab на рис. 6.1 термин вспомогательные входы, а для выводов, обозначенных через X Yi. у, термин основные входы. Та же техника декомпозиции может использоваться для реализации п-УЛМ для любого п. Такая реализация будет иметь 2 --fn-1 выводов для входных сигналов. Основные входы будут соединяться с (п-1) входами выполненными в виде одинарных входов, а каждый вспомогательный вход выполняется в виде парафазного входа, на который подается входная переменная, либо ее дополнение или константы О или 1.

Возможна также реализация -УЛМ с 2--{-п-1 выводами для входных сигналов с помощью древовидной структуры УЛМ с меньшим числом переменных. Это достигается путем представления функции п переменных с помощью подходящих подмножеств входных переменных. Например, г-УЛМ (п нечетное) может реализовываться с помощью УЛМ третьего порядка следующим образом:

f {Xl, Х2, .... X ) = Х^Х foo (Хз.....Х„) + XiXgfoi fe, ..., х„) +

-f XiJCzf 10 (Хз.....X )-f XiXzf 11 (Xj.....x ).

Каноническая реализация таких УЛМ может быть получена путем использования декомпозиции Шеннона. Функцию трех переменных f(x,y, z) можно записать в виде

f {х. У, z) = xy- foo (z) + ху foi (z) + ху; fio (z) + ху fn (z),

где /ab(z) получается заменой л: = a, у=Ъ в f{x,y,z), а, b=0,1. Очевидно, fab (z) = 0,1, z или z, и любые функции трех переменных могут быть реализованы с помощью цепи, изображенной на рис. 6.1.