у. Уг Уз

б

У,Уг + УгУз У. Уг + *У2 Уз + *Уг *У1 Уг Уз + *У. Уг Уз

-= V. у, + .vy.

Рис 1.43. Многозначное кодирование состояний.

ТоктобЫЕ сиетлы

Трив-гер

триггер

Рис. 1.44. Реа.1изация регистра сдвига.

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

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

Этот тип реализации может быть обобщен путем суммирования управляющих входов для управления потоком информации. Например, используя управляющий сигнал С], моншо спроектировать цепь, в которой содержание регистра сдвигается вправо, если Ci = I, и сдвигается влево, если Ci = 0. Уравнения

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

В соответствующей этому кодированию У-матрице, приведенной на рис. 1.43,6, в каждой ячейке следующего состояния, характеризующей состояние 5, может быть записан любой из четырех кодов этого состояния (эти ячейки помечены звездочками). В строках, соответствующих кодам состояния 5, должны

Уп-2-

-2/3.

-2/t-f

Рис. 1.45. Управляемый регистр сдвига.

возбуждения двухтактного /?5-триггера составляются прямо Hd основе словесного описания и имеют вид

Ri=Ciyi+i +С,уг S, = С1У2, Ri = Ciy2 + Cu

Rn = Ciyn~l + С].

Член Ci в /?1 и член Ci в Rn необходимы для возврата триггеров в исходное положение при сдвиге наибольшего левого и наибольшего правого разрядов. Описанная цепь приведена на рис. 1.45.

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

Рис. 1.47 Управляемый счетчик.

Важным классом последовательностных цепей являются счетчики. Простые счетчики описываются таблицами состояний с одним входным столбцом. Например, таблица состояний, приведенная на рис. 1.46, соответствует счетчику по модулю 5, т.е. счетчику, считающему от О до 4 и затем начинающему счет сначала, если выход, связанный с состоянием i, представляет собой число, равное i - 1. В более сложных счетных цепях для задания режима работы используются управляющие входы.

Таблица состояний, показанная на рис. 1.47, характеризует счетчик по модулю 6, работающий в режиме прибавления 1, если С\ - €2 = О, прибавления 2, если Ci = О, Сг = 1, вычитания 1, если Ci = 1, Сг = О, и вычитания 2, если Ci =1, Сг = 1. Такие цепи иногда называются управляемыми счетчиками.

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

1.4.5. АНАЛИЗ ПОСЛЕДОВАТЕЛЬНОСТНЫХ ЦЕПЕЙ

Анализ последовательностных цепей включает следующие этапы:

1. По схеме последовательностной цепи построить матрицу возбуждений и выходную матрицу.

2/2-х~

у г-[у

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

2. Из матрицы возбуждений получить У-матрицу.

3. Построить таблицу состояний, используя У-матрицу, и выходную матрицу.

Рис 1.49 Матрица возбуждения.

У, Уа.г Рис. 1.50. У, 2-матрица

4. Пользуясь таблицей состояния, получить словесное описание поведения последовательностной цепи.

Процесс преобразования таблицы состояний в словесное описание, как и рассмотренная выше обратная задача, являются

Рис 1.51. Таблица со- СТОЯНИЯ соответствующим знаком У, 2-ма-стоянии. трица преобразуется в таблицу состоя-

Пример 1.10. Для цепи, изображенной на рис. 1.48, логические уравнения имеют вид.

Si = ХУ2 + Xyiyz Sz = X -f У1У2

Rl=yiy2 Я2 = ХУ2

2 = ХУ2 + Хй1У2 + У1У2-

Построение по этим выражениям карты Карнау позволяет получить матрицу возбуждений, приведенную на рис. 1.49. У, z-ма-трица (рис. 1.50) выводится из матрицы возбуждения с помощью таблицы состояний для iS-триггеров (рис. 1.30). Например, элемент в строке 10 и столбце О имеет Si = Ri = О и, следовательно, переменная у не меняет состояния (т.е. У1==1). Обозначая коды 00, 01, И, 10 буквами А, В, С и D соответственно, получим таблицу состояний, приведенную на рис. 1.51.

1.5. ФУНКЦИИ, НЕ РЕАЛИЗУЕМЫЕ КОНЕЧНЫМИ АВТОМАТАМИ

Существуют функции, которые не могут быть реализованы в виде конечных автоматов. Например, предположим, что мы хотим определить конечный автомат с двоичным входом, который начинает работать в состоянии до в момент времени и формирует выход 1 в момент времени t тогда и только тогда, когда суммарное число входных сигналов л; = О в интервале времени 0, t равно числу входных сигналов х = 1 в течение того же периода времени. Чтобы автомат выполнил эти расчеты, он должен хранить последовательность значений разностей между

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

Процесс получения таблицы состояний по схеме цепи является обратным процессу получения схемы цепи по таблице состояний. Первый шаг состоит в построении матрицы возбуждений x для входов элементов памяти. Эта задача

идентична анализу комбинационной цепи с входами X и у и выходами z и Ei, где Ег - входы возбуждения элементов памяти. (Матрица возбуждения обычно всегда полностью определена.) Из матрицы возбуждений и таблицы состояний триггеров можно определить У, 2-матрицу. Путем обозначения кода каждой переменной со-

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

Впервые применить булеву алгебру [1] к переключательным цепям предложил Шеннон [17]. Приведенные постулаты взяты у Хантингтона [8], а доказательства основных теорем можно найти у Фридмана [4] или Хилла и Петерсона [6]. Задача минимизации комбинационных функций изучалась многими исследователями. Табличная процедура образования простои импликанты развита Квайном [16] и Мак-Класки [11]. Метод карт был предложен Карнау [9]. Мак-Класки [11] предложил также и правила упрощения таблиц покрытия. Более сложные правила упрощения разработаны Джимпелом [5]. Петрик [15] предложил алгебраический метод нахождения минимальных покрытий, а Кобхэм и др. [3] сформулировали эту задачу в виде задачи целочисленного линейного программирования. Различные модели последовательностных автоматов представлены Муром [14] и Мили [13], а Кадден [2] показал эквивалентность этих моделей. Стори, Гаррисон и Рейнгард [18] сформулировали процедуру

общим ЧИСЛОМ нулевых и единичных входных сигналов. Однако потенциально это число неограниченно и, следовательно, число требуемых состояний также неограниченно.

Для выполнения этих расчетов, а также других, которые не могут быть выполнены с помощью конечных автоматов, разработан другой тип автомата, называемый машиной Тюринга [7, 19]. Этот автомат имеет блок управления с конечным числом состояний. Входы в автомат записываются на ленте произвольной длины. Блок управления позволяет записывать информацию на ленту, считывать ее с ленты, а также перемещать ее по ленте в обоих направлениях. Работа машины Тюринга происходит в следующем порядке: машина в некотором начальном состоянии 9о считывает некоторый входной символ лг, после этого блок управления переписывает Xi с некоторым символом Xj, переводит автомат в состояние и смещает выработанный символ вправо или влево. Машину Тюринга можно описать таблицей, сходной с таблицей состояний, так как блок управления имеет конечное число состояний. Для каждой комбинации входного символа (на ленте) и начального состояния блока управления таблица определяет следующее состояние, символ, который должен быть записан на ленте, и направление сдвига.

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

ЛИТЕРАТУРА

1. Boole G., An Investigation of the Laws of Thought, Dover Publications, Inc., 1958 (first published by McMillan in 1854).

2. Cadden W. J., Equivalent Sequential Circuits, IRE Transactions on Circuit Theory, vol. CT-6, March 1959.

3. Cobham A., Budshal R., North J. H., An Application of Linear Programming to the Minimization of Boolean Functions, Proc. Second Symp. on Switching Theory and Logical Design, Detroit, Michigan, 1961.

4. Friedman A. D., Logical Design of Digital Systems, Computer Science Press, Woodland Hills, Calif., 1975.

5. Gimpel J. F., A Reduction Technique for Prime Implicant Tables, IEEE Trans, on Electronic Computers, vol. EC-14, pp. 535-541, August 1965.

6. Hill F. J., Peterson G. R., Introduction to Switching Theory and Logical Design, J. Wiley and Sons, Inc., 1968.

7. Hopcroft J. E., Ullman J. D., Formal Languages and Their Relation to Automata, Addison-Wesley, 1969.

8. Huntington E. v.. Sets of Independent Postulates for the Algebra of Logic, Trans. Am. Math. Soc, vo.l 5, pp. 288-309, 1904.

9. Karnaugh M., The Map for Synthesis of Combinational Logic Circuits, Trans. AIEE, vol. 72, Part I, pp. 593-598, 1953.

10. Kautz W. H-, The Necessity of Closed Loops in Minimal Combinational Circuits, IEEE Transactions on Computers, vol. C-19, pp. 162-164, February 1970.

11. McCluskey E. J., Minimization of Boolean Functions, Bell System Technical Journal, vol. 35, pp. 1417-1444, November 1956.

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

13. Mealy G. H., A Method for Synthesizing Sequential Circuits, Bell System Technical Jourml, vol. 34, pp. 1054-1079, September 1955.

14. Moore E. F., Gedanken Experiments on Sequential Machines, in Automata Studies, C. E. Shannon and J. McCarthy (Eds.), Princeton University Press, Princeton, New Jercey, pp. 129-153, 1956.

15. Petrick S. R., A Direct Determination of the Redundant Forms of a Boolean Function from the Set of Prime Implicants, AFCRC-TR-56-110 Air Force Cambridge Research Center, Cambridge, Massachusetts, April 1956.

16 Quine V/. v.. The Problem of Simplifying Truth Functions, Am. Math. Monthly, vol. 59, pp. 521-531, October 1952.

17. Shannon C. E., A Symbolic Analysis of Relay and Switching Circuits, Trans. AIEE, vol. 57, pp. 713-723, 1938.

18. Story J. R., Harrison H. J., Reinhard E. A., Optimum State Assignment for Synchronous Sequential Circuits, IEEE Transactions on Computers, vol. С 21, pp. 1365-1373, December 1972.

19. Turing A. M., On Computable Numbers with an Application to the Ent-scheidungsproblem, Proc. London, Math. Soc, vol. 42, pp. 230-236, 1936.

безусловного перебора для получения оптимальных однозначных кодирований состояний автомата, использующих минимальное число переменных состояния. Модель машины Тюринга [19] детально описана во многих книгах и, в частности, в книге Хоп-крофта и Ульмана [7]. Более подробное рассмотрение материала многих разделов этой главы можно найти у Фридмана [4].

f = fd = /(x).

Определите, являются ли самодуальными функции

а) x ix2 + Х1Х2 = fl(x i, Х2),

б) x2(Xi + Xs) + Xi{x2 + Xs) = f2{Xl, X2, Xs).

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

Рис. 1.52. К упражнению 1.5.

1.6. Постройте минимальную двухступенчатую реализацию в виде НЕ-И для каждой из следующих функций;

а) fl (xi. Xs, Xs, Xi)=ms, m, mg, mj mg, mig, тц, mis,

б) Ь (xi, X2, Xs, Xi) = Ш2, ms, me, m, mi2, тц + mi, mis,

lie onp-делено

hiu тц.

УПРАЖНЕНИЯ

1.1. Рассмотрим класс функций f(Xi, Х2, который равен 1 тогда и только тогда, когда нечетное число входных переменных равно 1. Функции этого класса называются функциями проверки на четность. Определите число простых импликант и существенно простых импликант в виде функций параметра п. Сколько логических элементов и входов логических элементов содержится при реализации в виде минимальной суммы произведений?

1.2. Найдите минимальную сумму произведений, используя карту Карнау, и минимальное произведение сумм, используя табличную технику для следующих функций:

а) / (х„ х2, Хз, Xt) = 2] mi, т^, mg, пцг, mis, тц, т^,

б) / (XI, Х2, хз, xt) = то, Ш2, mi, mij, + т mg, m?, тю.

не определено

1.3. Спроектируйте минимальную двухступенчатую цепь НЕ-И на четыре входа Xi, Х2, Xs, х4, выход которой z равен 1 тогда и только тогда, когда (а) точно два из ее входов равны 1, (б) два или более из ее входов равны 1.

1.4. Используйте основные законы булевой алгебры для доказательг^ з--справедливости (или несправедливости) следующих равенств:

а) ху + ху-\- xyz = xyz + ху + уг,

б) xyz -f- wyz -+- wxz = xyz -f- wyz -f wxy.

1.5. Булева функция (fx) называется самодуальной, если

в) h[xi, Хг, Хъ, Xii~m, m mj, ms. /П7, /Пд, /Пю, /пц, mis, r)f4(A;i,>;2, л;з, л;4) = 2]шо.Ш2, m?, mg, mg.mio,/ 13+ тъ,т\\,т\.

не определено

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

ХкХг {,XzXi \- Х2) + [Xl + Х2) (Х1Х2Х3 + Х1Х2Х2.) = Х2Х3 + Х1Х3.

1.8. Постройте таблицу истинности для цепи, работающей следующим образом: вход x -двоичное кодированное представление числа п, 0:/1:7, выход z -двоичное кодированное представление минимального целого числа, удовлетворяющего условию Vl

1.9. а) Найдите минимальную двухступенчатую реализацию в виде комбинационной функции НЕ-ИЛИ

f{x\, Х2, Хз, Xi) = mo, ши та, т-,. тд, тю, тц, М13.

б) Включена ли какая-либо простая импликанта f в ваше решение?

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

Рис. 1.53. К упражнению 1.10.

равен О или 1, а Ь должен принимать противоположные значения. Следовательно, каждая точка является неопределенной, но если хотя бы одна из них определена, то и другая точка также становится определенной. Найдите минимальную двухступенчатую реализацию в виде суммы произведений (И-ИЛИ).

б) Какое решение является оптимальным, если и а и Ь не определены?

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

\(Хх, Х2 а: ) = Лоф Л,л;1 фЛгЛГгф ... ф АпХп @ A +iXiX2® An+2XiXa® ...

Ф n-m-n(n-l)/2-*i-*2*3Ф