Пример 6.11. Рассмотрим последовательностный автомат, описанный в примере 6.6. Процедура матричной реализации автомата аналогична процедуре древовидной реализации. Исключение представляет тот факт, что функции f(z) и г() получаются заменой выражений для переменных у. Используя уравнения примера 6.6, получаем

f (О = У23 {t) = x{t-l)f(t- 1) у, (23) - 1) + + xit-l)f{t-l)yoiu){t-i) +

+ xit-l)f{t-l)yuw(t-i) +

+ X(t-l)f(t-l)yu03)it-l) =

x{t~l)f{t-l)[x{t-2)fit-2)] + + -x(t-\)fit-\)[x{t-2)f{t--2) +

+ xit-2)f{t-2)] + x{t-l)fit~\)[x{t-2)f(l-2) + J.x(t-2)f{l-2)] + x{t- l)f(t-l)[x{t-2)f{t-2)] = = тз + ms + 6 + mi2 + mis + u-

В приведенном уравнении m, обозначает минтерм переменных x{t~l), f{t~l), x{t - 2) и fit -2), x{t-l) является наибольшим значащим битом. Используя ту же процедуру, получаем функцию выхода

Z it) = y {t)=x{t-\)f{t- 1) J/4 (23) - 1) +

+ x{t-l)f{t~-l)y u3)it-i) + + x{t-l)f{t-l)y{t-\) +

+ X(-I)f(/- 1),4(23)-1) =

= x{t-\)nt-i)x{t-2)f{t-2) + + x(t-\)f{t\)x{t-2)f{t-2) + + x{i-\)f{i-l)x{t-2)f{t-2) + + x{t-l)f{i-l) + x{t-l)f{t-l)

= mo + / 1 + 2 + + Is + m.6 + -f 7 + mg + 1Щ + m.io + mil.

Реализация этого автомата в виде итеративной матрицы, изображенной на рис. 6.34, непосредственно может быть получена из этих уравнений для f(t) и z(i).

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

6.3.4. ПРОГРАММИРУЕМЫЕ КЛЕТОЧНЫЕ СТРУКТУРЫ

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

Существует несколько методов для обеспечения возможности изменения реализуемой функции определенным элементом матрицы. В одном из таких методов используются отсекаемые значения [17]. Это приводит к созданию таких элементов, которые могут быть настроены несколькими методами в зависимости от того, как надо изменить функцию, реализуемую элементом. В другом методе вводится какой-либо \щ^ашяш, например на одном или нескольких триггерах или на сдвиговом регистре, в каждый элемент [12]. Недостатком этого метода является невозможность сохранения состояний триггеров при отключении питания от матрицы. Кроме того, память в матрице перед ее использованием необходимо приводить в исходное состояние. Эту трудность можно преодолеть путем использования постоянных, предназначенных только для чтения блоков памяти так называемого постоянного запоминающего устройства (ПЗУ). Однако эти устройства требуют установки в желаемое состояние в самом начале и не могут изменяться. В следующем методе для реализации логических и последовательностных функций

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

Автоматы, имеющие больше одного входа, могут реализовываться путем модификации применяемого элемента структуры. Элемент с k-\-\ горизонтальными и одним вертикальным входами может использоваться для реализации автомата с k входами, в этом случае матрица имеет размер + 2) X 2 . Матрицу такого типа можно также использовать для реализации автоматов с числом входных переменных, меньшим чем k в случае использования более чем одной переменной обратной связи.

сиз

.мштерм-матрица

-и

Котектор матрица

Рис. 6.36. Программируемая матрица комбинационных функций.

терм-матрицей, реализует х = х, а вертикальный выходной сигнал Z ~ ху или Z - XZ в зависимости от состояния элемента. Очевидно, что на выходах z нижней строки матрицы может быть получен любой минтерм. Вторая матрица, называемая коллектором-матрицей, используется для суммирования соответствующих термов для воспроизведения желаемых функций. Функциями, реализуемыми каждым элементом матрицы, являются 2 = 2 и х = X или X = х-\- Z в зависимости от состояния элемента.

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

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

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

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

2 = xzy + xzy.

Аналогично выходами элементов коллектора-матрицы являются

Jt = x-\-yz, z = z.

Вместо использования двух раздельных матриц для реализации минтермов и их объединения для реализации различных функций возможно их объединение в одну матрицу, состоящую из более сложных элементов. Каждый такой элемент включает в себя два бита памяти (или два внешних входа), обозначаемых через Ух и г/2. Типовой элемент изображен на рис. 6.37.

Рис. 6.37. Основной элемент двусторонней матрицы.

Матрица таких элементов может использоваться для реализации множества комбинационных функций следующим образом (рис. 6.38). Подадим входные функции на входные зажимы Хх. Выход Zi каждого элемента последней строки соединяется со входом Z2 того же элемента. Входы Zx верхней строки и входы Х2 первого столбца соединяются с константами 1 или О соответственно. Такая матрица является двусторонней по вертикали, поскольку сигналы могут переходить сверху вниз и снизу вверх. Число столбцов, необходимых для реализации множества функций п переменных, равно 2 . Для реализации т таких функций

г,-0-

г

о

о о

о

Рис. 6.38. Реализация комбинационных функций на двусторонней матрице.

Другим методом реализации комбинационных функций является использование матриц с ПЗУ, изображенных на рис. 6.39. Входные сигналы декодируются и используются в качестве регистров адреса для доступа к ПЗУ. Определенная комбинация битов, получаемая из входных значений, задает значение функции, соответствующее входной комбинации. Выходы ПЗУ могут комбинироваться с использованием матрицы ИЛИ. Если должно быть реализовано несколько функций, то необходимо использовать матрицу И для создания импликантов, необходимых для всех функций. Матрица ИЛИ также может быть реализована на ПЗУ.

Функционирование матриц на ПЗУ заключается в следующем. Для каждой входной комбинации только один выход каждого декодера равен 1. Читается один бит памяти матрицы И, будучи выбранным этими сигналами. В матрице ИЛИ бит памяти г-й строки и /-ГО столбца будет единицей в том и только в том случае, если fj содержит i-й терм, созданный в матрице И.

) тах(а, Ь) - функция, определяющая большее из двух значений а и Ь. - Прим. перев.

Требуется max (m, п) ) строк. В канонической форме Рида - Мюллера любая комбинационная функция п переменных может быть выражена в виде

/ = ао®ад©02-2® ... 03-1X2 ... BOn-iXiXz ... л; .

Каутз [14] показал, каким образом можно реализовать любую функцию с помощью программируемой матрицы на основе приведенного выше выражения.

1-1 1-1 LA

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

J Декодер \

И

Рис. 6.39. Структура ПЗУ.

Ассоциативные виды памяти (адресуемость в которых основана на содержимом памяти) также предлагались в качестве средства реализации логических функций [7]. Непосредственным применением этой возможности является использование слов памяти для каждой входной комбинации и запоминание желаемых выходных комбинаций для каждой входной. Функционирование ассоциативной памяти, реализующей множество комбинационных функций, состоит в поиске по содержимому памяти слова, соответствующего входной комбинации, и чтению из него значений функции. При таком подходе необходимо иметь 2 слов по (п -1- т) разрядов каждое для реализации т функций п переменных.

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

щены еще в большей степени. Однако потребуются два бита на каждое входное значение для представления трех состояний: 0,1 и -.В процессе чтения ко всем словам, для которых входные значения соответствуют входной комбинации, доступ осуществляется одновременно, а выходы соответствующих разрядов объединяются схемой ИЛИ [7].

Пример 6.12. Пусть реализуемыми функциями являются fi = - Х1Х2 и f2 = Хз-\- х^. Если бы необходимо было запомнить полную таблицу истинности, то потребовалось бы шестнадцать слов по шесть разрядов каждое. Вместо этого оказывается достаточным использование трех слов по десять разрядов, если определяются только 1-точки функций, а неопределенности, допустимые на входах, требуют двух разрядов для кодирования каждого входа:

Xl Х2 Xj и и. 1 1 - - 1 О

- - 1-01

- - - 1 О 1

Если входной комбинацией является х, = хг = Хз = 1, х^ = О, то доступными окажутся первая и вторая строки. Выходные сигналы в двух строках каждого столбца объединяются схемой ИЛИ, и вырабатываются выходные сигналы \х = \2 = 1- Если же Xl = О, Хг = Хз = 4 = 1, то окажутся доступны вторая и третья строки и выходными сигналами будут /1 = 0, /г- I-

Каутз [13] предложил использовать адресную память большого объема для выполнения таких операций, как сдвиг, выравнивание, сложение и др., над словами, хранимыми в памяти, а также для реализации комбинационных и последовательностных функций. Память при этом организуется как матрица однотипных элементов, каждый из которых содержит один триггер и некоторую комбинационную логическую схему. Триггер используется для хранения одного разряда слова, а матрица ориентирована на работу со словами. Если она используется для реализации комбинационных логических схем, то состояние триггера используется для управления видом реализуемой элементом функции.

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

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

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

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

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

Каноническая реализация универсальных логических модулей впервые была рассмотрена Яу и Тангом [37], которые предложили также УЛМ с соединениями между выводами [38]. Форс-лунд и Ваксман [5] получили оптимальную реализацию УЛМ для небольшого числа переменных. Препарата и Мюллер [28] и Препарата [26,27] разработали метод построения УЛМ с использованием разбиения. Патт [24,25] использовал их результаты для получения УЛМ с меньшим числом выводов и улучшил нижнюю границу для числа требуемых выводов, а также вывел соотношения, определяющие эту границу.

Арден [2] показал, что некоторое множество модулей может реализовать любой последовательностный автомат при наличии

задержки, если оно может реализовать любое заданное событие при отсутствии задержки. Метод реализации последовательностных автоматов с фиксированным числом входов при использовании модуля только одного типа основывается на работе Вей-нера и Хопкрофта [34], Ульмана и Вейнера [32, 33], Ньюборна [21] и Гзейха, Тана и Ньюборна [10]. Модульные реализации в виде древовидной структуры были предложены Арнольдом, Таном и Ньюборном [3].

Обзор исследования клеточных структур был опубликован Минником [18]. Более поздняя работа появилась у Каутза [14] и Мукхопадхайя и Стоуна [20]. Каскады с одинарными связями были предложены Мэйтром [16], доказавшим также их логическую незавершенность. Шорт [29] предложил каскад с двойными связями, который был обобщен на случай каскадов с множественными связями Элзпасом [4]. Хэнни [9] изучал итеративные системы с односторонним и двусторонним распространением сигнала. Итеративные матрицы с одним непосредственно управляющим входом в элементе были предложены Акерзом [I]. Реализация последовательностных цепей на итеративных матрицах изложена по работе Арнольда, Тана и Ньюборна [3]. Матрицы элементов с отсекаемыми значениями были предложены Минником [17]. Метод реализации произвольных комбинационных функций с помощью программируемых матриц представлен здесь в соответствии с роботой Каутза [14]. Гарднер [7] предложил метод использования ассоциативной памяти для реализации логических схем.

ЛИТЕРАТУРА

1. Akers S. В., А Rectangular Logic Array, fEEE Trans, on Computers, vol. C-21, pp. 848-857, August 1972.

2. Arden D. N., Delayed Logic and Finite State Machines, Proc. AIEE Symposium on Switching Theory and Logical Design, pp. 131-151, September 1961.

3. Arnold T. F., Tan C. J., Newborn M. M., Iteratively Realized Sequential Circuits, IEEE Trans, on Computers, vol. C-19, pp. 54-66, January 1970.

4. Elspas В., Theory of Multirail Cascades, Recent Developments in Switching Theory, A Mulhopadhyay (Ed.), Academic Press, pp. 315-367, 1970.

5. Forslund D. C, Waxman R., The Universal Logic Block (ULB) and Its Application to Logic Design, Proc. 7th Annual Symposium on Switching and Automata Theory, pp. 236-250, 1966.

6. Friedman A. D., Feedback in Synchronous Sequential Switching Circuits, IEEE Trans, on Electronic Computers, vol. EC-15, pp. 354-368, June 1966.

7. Gardner P. L., Functional Memory and Its Microprogramming Implications, IEEE Trans, on Computers, vol. C-20, pp. 764-775, July 1971.

8. Henle R. A., Ho I. Т., Maley G. A., Waxman R., Structured Logic, Proc. AFIPS Fall Joint Computer Conference, pp. 61-67, 1969.

9. Hennie F. C, Iterative Arrays of Logical Circuits, MIT Press, Cambridge, Massachusetts, 1961.

10. Hsieh E. P., Tan C. J., Newborn M. M., Uniform Modular Realizations of Sequential Machines, Proc. ACM Conference, pp. 613-621, 1968.

11. Husson S. S., Microprogramming - Principles and Practices, Prenti/e-Hall, 1970. у

12. Kautz W. H., Cellular Logic-in-Memory Arrays, IEEE Trans, cut Computers, vol. C-18, pp. 719-727, August 1969.

13. Kautz W. H., An Augmented Content-Addressed Memory Array for Implementation with Large-Scale-Integration, /. ACM, Vol. 18, pp. 19-33, January 1971.

14. Kautz W. H., Programmable Cellular Logic, Recent Development in Switching Theory, A Mukhopadhyay (Ed.) Academic Press, pp. 369-422, 1970.

15. Kautz W. H., Levitt K. N., Waksman A., Cellular Interconnection Arrays, IEEE Trans, on Computers, vol. C-17, pp. 433-445, May 1968.

16. Maitra K. K., Cascade Switching Networks of Two-Input Flexible Cells, IRE Trans, on Electronic Computers, vol. EC-11, pp. 136-143, April 1962.

17. Minnick R. C, Cutpoint Cellular Logic, IEEE Trans, on Electronic Computers, vol. EC-13, pp. 685-698, December 1964.

18. Minnick R. C, A Survey of Micro-Cellular Research, /. ЛСЛ1, vol. 14, pp. 203-241, April 1967.

19. Minnick R. C, Goldberg J., Green M. W., Kautz W. H., Short R. A., Stone H. S., Yoeli M., Cellular Arrays for Logic and Storage, Final Report, Stanford Research Institute, SRI Projeft 5087, 1966.

20. Makhopadhyay A., Stone H. S., Cellular Logic, Recent Developments in Switching Theory, A Mukhopadhyay (Ed.), pp. 255-313, Academic Press, 1970.

21. Newborn M. M., A Synthesis Technique for Binary Input -Binary Output Synchronous Sequential Moore Machines, IEEE Trans, on Computers, vol. C-17, pp. 697-699, July 1968.

22. Newborn M. M., Arnold T, F., Universal Modules for Bounded Signal Fan-Out Synchronous Sequential Circuits, IEEE Trans, on Computers, vol. C-21, pp. 63-78, January 1972.

23. Osman M. Y., Weiss C. D., Universal Base Finctions and Modules for Realizing Arbitrary Switching Functions, IEEE Trans, on Computers, vol. C-21, pp. 985-994, September 1972.

24. Patt Y. N., Universal Logic Modules with Still Fewer External Connections, Proc. 4th International Conference Systems Science, January 1971.

25. Patt Y. N., Optimal and Near-Optimal Universal Logic Modules with Interconnected External Terminals, IEEE Trans, on Computers, vol. C-22, pp. 903-907, October 1973.

26. Preparata F. P., On the Design of Universal Boolean Functions, IEEE Trans, on Computers, vol. C-20, pp. 418-423, April 1971.

27. Preparata F. P., Universal Logic Modules of a New Type, IEEE Trans, on Computers, vol. C-21, pp. 585-588, June 1972.

28. Preparata F. P., Muller D. E., Generation of Near-Optimal Universal Boolean Functions, /. Сотр. and Sys. Sci., vol. 4, pp. 93-102.

29. Short R. A., Two-Rail Cellular Arrays, AFIPS Conf. Proc. PT. I, pp. 355- 369, Spartan Books, 1965.

30. Stone H. S., Universal Logic Modules, Recent Developments in Switching Theory, A. Mukhopadhyay (Ed.), pp. 255-313, Academic Press, 1970.

31. Stone H. S., Korenjak A. J., Canonical Form and Synthesis of Cellular Cascades, IEEE Trans, on Electronic Computers, vol. EC-14, pp. 852-865.

32. Ullman J. D., Weiner P., Uniform Synthesis of Sequential Circuits, BSTJ, vol. 48, pp. 1115-1127, May -June 1969.

33. Ullman J. D., Weiner P., Modular Networks and Nondeterministic Sequential Machines, IEEE Trans, on Computers, vol. C-21, pp. 1124-1129, October 1972.

34. Weiner P., Hopcroft, Modular Decomposition of Synchronous Sequential Machines, Proc. 8th Annual Symposium Switching and Automata Theory, pp. 233-239, 1967,