УПРАЖНЕНИЯ

8.1. Напишите программу вычисления функции f = XiXz + ХгХг + XiXaXi, используя команды пересылки, расщепления, создания и разрушения ЦМД. Нарисуйте нужную структуру памяти. Постарайтесь максимально использовать параллельное выполнение действий.

8.2. На основе модулей с резидентными ЦМД разработайте схему для реализации следующих функций:

а) ИЛИ,

б) /К-тригер,

в) Г-триггер,

8.3. Используйте описанные в книге основные модули с резидентными ЦМД для реализации следующих функций:

а) f = XiXi + XiXi,

б) J - XiX2 + XiXs + XiXsXi.

8.4. Используйте З-3-схемы для реализации функции f = XiX -\- х^хг -\-

8.5. Какая функция реализуется изображенным на рис. 8.28 элементом с резидентным ЦМД в предположении, что обеспечивается правильная синхронизация?

Рис. 8.28. К упражнению 8.5.

8.6. Спроектируйте элемент с резидентным ЦМД для реализации функции /1 ф /г = hh + hli, если эта реализация вообще возможна.

ПРИЛОЖЕНИЕ

ПЛ. ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ

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

Множества

Множеством А называется совокупность элементов. Если число элементов множества конечно, оно называется конечным множеством. Кардинальным числом множества Л, обозначаемым как Л|, называется число элементов множества. Принадлежность элемента а, множеству Л обозначается at е Л. Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается ф.

Множество может быть задано простым перечислением его элементов или указанием некоторого свойства, которым обладают все элементы множества. Например, Л = [Ui, Сг, ..., й„} является множеством. В = {х\х = ai-\- а^, а е Л, представляет собой множество, элементами которого являются суммы различных пар элементов множества Л. Кардинальные числа этих двух множеств соответственно равны \А\ = п и В|

V27 12/ число пар элементов множества Л. Число элементов в множестве В может быть меньще числа различных пар элементов Л в силу того, что может существовать более чем одна пара элементов с данной суммой.

Пусть заданы два множества А и В. Множество Л содержится (включается) в В, что обозначается как Л s В, если каждый элемент Л является также и элементом В. Если А s В, то Л называют подмножеством множества В. Если Л Б и В s Л, то Л эквивалентно В (А = В). Если ЛеБ иБЛ, тоЛ является собственным подмножеством В (Л с Б). Объединением Л и Б, или А и В, называют множество, содержащее все элементы Л и все элементы Б. Это значит, что Л U Б = {с^ с,- е Л или С{ е еБ}. Пересечением А и В, или Л П В, называется множество, состоящее из всех элементов, содержащихся одновременно и в

Л, И В В. Следовательно, А П В - {Ci\ciA и а^В}. Если Л и В = , то говорят, что множества Л и В - непересекающиеся множества. Если мы определяем универсальное множество и, содержащее все интересующие нас элементы, тогда Л является множеством элементов (7, не принадлежащих Л. Разность двух множеств Л и В определяется как Л - В = Л П В. Декартово произведение двух множеств Л и В, обозначаемое как Л X fi, является множеством всех упорядоченных пар {а, Ь), где а е Л и & е В.

Рассмотрим множество всех множеств {Вь Вг, , Bp}, такое, что fi) и fiz и ... и Bp = Л и Bi П Bj = (для всех i ф j). Множества Bi, Вг, Bp задают разбиение А. Каждое множество В, называется блоком этого разбиения. Разбиение обозначается как {Bi; Вг; ..., Bp}.

Пусть Л = {1, 2, 3}, В = {2, 3, 4}, С = {1, 2}, D = (2, 4}; Е = {4, 5}. Тогда А В, ВА, С а А, D cz В; А[} В={1, 2, 3, 4}, ЛПВ = {2, 3}; ЛХВ = {(1, 2), (1. 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3,4)}. Если = 2, 3, 4, 5}, то Л-В = = ЛПВ = {1, 2, 3}П{1, 5} = {1}. Множества Л и В определяют разбиение на U. Это разбиение обозначается как {Л; Е} - = {1,2, 3; 4, 5}.

Графы

Граф определяется двумя множествами V и Е, где I/ -множество вершин (узлов) графа и Е - множество дуг (ветвей). Элементами Е являются пары вершин (а, Ь), а, b V. В случае когда пары упорядоченные, граф называют ориентированным и неориентированным в противном случае.

Граф может быть задан своей матрицей соединений С, содержащей по столбцу и строке на каждую вершину графа. Элемент Cjj, стоящий на пересечении г-й строки и /-го столбца матрицы, равен 1 тогда и только тогда, когда граф содержит дугу, соединяющую i-ю вершину с /-й. Путем от начальной вершины О) к конечной вершине Vu называется последовательность дуг {v\, V2)(v2,Vz)..... {vu-i, Vh). Циклом назывзют путь с совпадающими начальной и конечной вершинами. Ациклическим графом называют граф, не содержащий циклов.

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

Аналогично число вершин, исходящих из вершины, называется выходной степенью вершины (коэффициентом разветвле-

ния по выходу). Ациклический граф, имеющий одну вершину с входной (выходной) степенью, равной О, и все остальные вершины с входной (выходной) степенью, равной 1, называется деревом. При этом вершина с входной (выходной) степенью, равной О, называется корнем дерева. Вершины с нулевой выходной (входной) степенью называются листьями дерева. Дуги дерева называются его ветвями.

Отношения

Пусть есть два множества А и В. Подмножество R множества Л X -6 называется (двоичным) отношением на Л X Б- Подмножество множества Л X Л является отношением на Л. Если R является отношением и (а, b)R, мы обозначаем это как aRb. Отношение R на А рефлексивно, если aRa, УаА. Оно симметрично, если aRb влечет bRa У а, Ь^к. Оно антисимметрично, если aRb и bRa означает а = Ь, У а, Ь^А. Отношение транзитивцр, если aRb и bRc влечет aRc, У а, Ь, с^А. Отношение R является отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение называется отношением частичной упорядоченности, если оно рефлексивно, транзитивно и антисимметрично. Частичное упорядочение R на А является общей упорядоченностью, если aRb или bRa, У а, Ь^А.

Пусть R является отношением на Л и В является подмножеством Л. Элемент с е Л является нижней границей В, если для каждого b В справедливо aRb. Если для каждой нижней границы с из В справедливо cRa, то а является наибольилей нижней границей В. Аналогично верхней границей В является элемент ее Л, такой, что bRa, УЬВ. Если для каждой верхней границы с из В справедливо bRc, то b является наименьшей верхней границей В. Частичное упорядочение R называется структурой, если для любой пары (а, Ь) R существует наибольшая нижняя и наименьшая верхняя границы. Структура может быть представлена ориентированным графом, вершины которого соответствуют его элементам; этот граф содержит дугу, соединяющую вершину а с вершиной b тогда и только тогда, когда aRb.

Функции

Отношение f на Л X Б является функцией, если для каждого се Л существует элемент ЬеВ и если существуют bubB, такие, что (а, &,)е/ и (0,62)/. тогда bi - Ьг. Множество Л называется областью определения функции, а множество В - ее областью значений (диапазоном).

П.2. МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Отдельные задачи теории переключений, рассматриваемые в этой книге, могут быть сформулированы в виде задач ж^ге-матического программирования специального вида. Теория и приложения математического программирования рассматриваются в различных учебниках, в частности [2-4]. Здесь мы ограничимся только основными формулировками.

Задача математического программирования может быть сформулирована в следующей общей форме: для данного множества переменных {х\, Хч, х„} найти те значения переменных, которые минимизируют (максимизируют) некоторую функцию f(Xi, Х2, Хп), называемую функцией цели (целевой функцией), при соблюдении ряда ограничений gi (xi, Х2, Xn)ki, t= 1, 2, т. Если целевая функция и ограничения линейны, то задача называется задачей линейного Программирования. Если рассматриваю-гся только целочисленные значения переменных Xi, то говорят о задаче целочисленного программирования. В отдельных задачах теории переключений рассматриваются только два значение переменных - о ц j Такие задачи называются задачами О-i Целочисленного прогро,м-мирования (булево программирование/-

В настоящее время известно болы° число работ названным выше задачам математического гфограммировани^з олы решения таких задач приложимы такУ некоторьщ задачам, которые рассматриваются в данной ki

Отображение элемента а в элемент b функцией / обозначается как b = f{a). Говорят об отображении на В, если для любого Ь^В существует элемент аеЛ, такой, что {a,b)f-Отображение называется прямым соответствием, если из того, что /(ai) = f(02). следует, что 01 = 02, Vo СгЛ. Обратной функцией функции / называется отношение f-, такое, что {а, Ь) е f- тогда и только тогда, когда (Ь, а) е /.

Бинарной операцией на множестве Л называют функцию /, отображающую Л X Л в Л.

Примерами бинарных операций могут служить операции сложения и вычитания. Говорят, что операция - коммутативна, если ab = ba, \/а, b А. Операция является ассоциативной, если (а Ь)-х-с = -х-с), Va, b, с^А. Операция дистрибутивна относительно в том случае, когда а^-{Ь-с) -a-srb-a-iC и {a-b)jcc - a--i,c-b-c, \fa, b, с^А. Элемент геЛ называется тождественным по отношению к (или единичным), если i-a - a-i - а, VaA. Элемент геЛ называется нулевым по отношению к в том случае, когда z-a - a-z = z, VaA.

570 Приложение ЛИТЕРАТУРА

1. Birkhoff G., MacLane S., A Survey of Modern Algebra, 3rd edition, AlcMil-lan. New York, N. Y., 1965.

2. Garfinkel R. S., Nemhauser G. L., Integer Programming, Wiley, New York,

N. Y., 1972.

3. Hu T. C., Integer Programming and Network Flows, Addison-Wesley. Reading, Massachusetts, 1969.

4. McMillan C., Jr., Mathematical Programming AViley, New York, N. Y., 1971.

5. Stone H. S., Discrete Mathematical Structures and Their Applications, Science Research Associates, Palo Alto, California, 1972.

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Автоматы возвратные 347

- перестановочно-возвратные 348

- перестановочные 347 Автосинхронный код 276 Акерза матрицы 416 Асинхронные последовательностные

цепи 192-289 допущение об ограниченных задержках 269 кодирование состояний 207

-- прн одновременном переходе

- - с многократным изменением выхода 237

---помощью множества связанных строк 211 -----разделяемых строк 218

- - универсальное 215, 221 логические элементы с неограниченными задержками 275

неограниченные входные изменения 267

одновременные изменения входных

переменных 263 определение У-матрнц 237 таблица переходов 193

- - построение 198 --сокращение 199

с импульсными входами 197

База сильная 114

- слабая 114 Биграф 441

Бнстабильные элементы 43 Блок 291-297, 567 Булева алгебра 11-16 --- основные постулаты 11

- - применение к переключатель-

ным цепям 14

-- свойства 11

Булевы выражения 13

- функции 13

Ветви дерева 568 Ветвления процедура 31

Внутренние состояния 38 Возможное покрытие 441 Время перехода 212 Вспомогательные входы 384 Входной алфавит 38

- символ 38 Выбор ИС 438 Выходной алфавит 38

- символ 38 Вэйра счетчик 370

Гиперграф 439 Граница верхняя 568

- нижняя 568

Граф ациклический 567

- вершина 567

- двудольный 441

- дуга 567

- импликационный 159

- матрица соединения 567

- неориентированный 567

- ориентированный 567

- переходы состояний 39

- путь 567

- смежности 210 Графы схем 438 Грея коды 369

Двоичное представление 222 Двусторонняя матрица 428 Двухступенчатая реализация 21 Двухфазовые синхронизируемые цепи 374

Декартово произведение 567 Декомпозиции карта 84 Декомпозиция

- асинхронных цепей 358-364

- дизъюнктивная итеративная 92 --множественная 92

--простая 84

--сложная 91

- комбинационных функций 83

- нондизъюнктивная 95

- последовательностных автоматов

предметный указатель

Декомпозиция последовательностных автоматов параллельная 310

---- последовательная 310

--- универсальная каноническая

- при неодновременных переходах

-- одновременных переходах 359

Дерево покрытия 494

- схемы проверки на четность 81 Детектор завершения 276 Диагностические последовательности

Диаграмма пар 124

- состояний 39 Дистрибутивность 12, 569 Дихотомии,; совместимые 231

- упорядоченные 231 Дихотомия 229 Доминирование 443

- допустимые множества 442 Доминирующая строка 30 Доминирующие совместимые множества 131 Доминирую1ций столбец 30 Допустимое множество 442 Допустимые пучки 458 Древовидная цепь 81 Дуальность 12 Дублирование элементов 446

Задержка 46 - введенная 241

- инерционная 242

- паразитная 241

- чистая 242 Задержки величина 45

- и риски сбоя 241

- элемент 45 Замкнутое покрытие 128

Идемпотентность 12 Избирательности условие 385 Импликанта 22

- простая 22

- существенно простая 29 Импликационный граф 132, 158 --автомата без потери информации 158

--МС-множества 134

--ПС-множества 134

-- таблицы состояний 330

-- универсальный 330

Импульсная реакция 168 Инверсия 167

Индекс обратной связи 327 Инициирующие сети 457

Каналы 518

Каноническая сумма минтермов 20 Каноническое произведение макстермов 20 Кардинальное число 566 Каркас 472 Карты 437, 472

- Карнау 25

- назначение 437

- размещение 438

- трассировка 438 Каскадное включение 176 Каскад с двойными входами 413 ---множественными входами

Квайна-Мак-Класки процедура 24 Кернихана-Лина процедура 452, 456

Клеточные структуры 411-432

- - двумерные 412

--итеративные 411, 414, 551

-- коллектор-матрица 427

--минтерм-матрица 427

--одномерные 412

--полусумматор 414

- - программируемые 426 Кодирование при одновременном переходе 222

Код состояния 210 Коды inin 278 Команда 536

Комбинационные функции 16

- - декомпозиция 83-95

--пороговые 105

--симметричные 97

--специальные классы 96

--юиатные 104

Комбинационные цепи 16-38 -- анализ 16

---декомпозиция 83-95

-- древовидная цепь 81

~ - многоступенчатые 81-83

-- модульная конструкция 37

--синтез 18-38

- - с разветвленным выходом OS-

Коммутативность И, 569 Конечное множество 566 Конечные автоматы 38 Контактные цепи 15 Коэффициент разветвления по входу 82

---выходу 68

Ли алгоритм 510, 518 Линейно-разделяемые функции 106 Линейность НО

Линейные последовательностные цепи 160

-- - нулевые последовательности

--- применение для исправления

ошибок 173 Листья дерева 568 Литерал 22 Ловушка 178

Максимально несовместимые множества 130 Макстерм 20 Манкреса алгоритм 477 Манхэттенская геометрия 483 Математическое программирование 569

--линейное программирование 569

--функция цели 569

- - целочисленное программирова-

ние 569 Матрица возбуждения 51

- на элементах одноразрядного сум-

матора 414 У, г-матрица 51 и-Мерное пространство 18 Микропрограммирование 432 Мили автомат 39

Минимальное произведение сумм 35

Минимальные деревья покрытий 495-500

Минтерм 20

Минтерм-матрица 427

Многовыходовые простые импликанты 69-81

---существенные 78

---хорошие 78

Многозначное кодирование 235

Многослойная плата 517

Множества межконтурные 211

- простых логических функций 109

- - --логически полные 109

- fe-fe-функций 533.

Множество всех упорядоченных пар 567

- логических элементов 109

--- сильно полное 109

--- слабо полное 109

- сигналов 176

- строк 211

Модульная конструкция 37

- реализация последовательностных

автоматов 395-411

Монотонная функция 515 МОП-транзисторы 16 Моргана де законы 13 Мура автомат 40 Мэйни счетчик 371 Мэйтра каскад 412

Наводящие последовательности 146 Накладки шевронные 553 Независимые от скорости цепи 275 Непересекающиеся множества 567 Несвязная пара 485 Несвязное множество 485

--максимальное 485

Несовместимые множества 130 Несущая плата 438, 472 Неупрощаемый полином 173 Нормализация матрицы 477 Нулевая последовательность 172 --максимальной длины 173

Однозначное кодирование 51, 210 Одномерные клеточные структуры 412 Оператор запаздывания 163 Основные входы 384 Отношение двоичное 568

- рефлексивно 568

- симметрично 568

- транзитнвно 568

- частичной упорядоченности 568

- эквивалентности 568

Пара множеств 296

- упорядоченная 293 Ми-Пара 302 Парафазные входы 15 Передаточная функция 164 Переменное состояние 50 Пересечение 566 Поглощение 12

Подкуб перехода 225

Покрытие простыми имп чикат ами 28

Последовательностные автоматы 38

--без потери информации 151

----- конечные 151

-----обобщенные 151

- - итеративная реализация 422 --конечные 38

- - модульная реализация 395

--специальные классы 151

Последовательность сигнаjron 176 Поста теорема 113

Поток информации 300 Принцип замещения 12

- суперпозиции 161

Проверочные тесты 149 Проводящие петли 530 Программа 536

- дублирующая 538 Промежуточное нулевое состояние

Процедуры итеративные 456

- конструктивные 456 Прямолинейное расстояние 483 Пустое множество 566

Разбиение 437-472, 567

- итеративная процедура 449

- конструктивные эвристические

процедуры 456

- минимизирующее длительность за-

держки 464 --число соединений, оптимальные

решения 441 ----субоптимальные решения

- нетривиальное 291

- оптимальное древовидных графов

--с дублированием элементов 446

- параллельное 459

- последовательное 459

- релевантное 354

- сведение к задаче математического

программирования 445

----о покрытии 441

- - схемы 437

- тривиальное 291 Разбиения алгебра 291-295

- блок 567

Разложение на множители 82

- НЕ-ИЛИ-И 273 Размещение ИС 438 Размещения задачи 472-492 -- итеративные процедуры 482

- - конструктивные методы 489

--метод ветвей и границ 481

--нижняя граничная оценка длины соединений 474

Расходящиеся деревья 467 Реализация вида И-ИЛИ 23

--ИЛИ-И 36

--НЕ-И-И 36

--НЕ-ИЛИ 36

--НЕ-ИЛИ-ИЛИ 37

- двухступенчатая 21

- обратной связи в виде сдвигового

регистра 338

- с олиим контуром обратной связи

327.

- функций с ослабленной обратной

связью 323

Регистр сдвига 56 Регулярное множество 176 Регулярные выражения 175-183 Рида-Мюллера р11зложеше 112 Риски сбоя 241-263

--в единице 343

-- - комбинационных цепях 243

--- нуле 243

--динамические 243

---функциональные 247

-- логические 247

- - определение с использованием

8-значной алгебры 259

-----троичной алгебры 256

-- переходные 250

-- последовательные 250

-- статические 243

- - - функциональные 247

--существенные 252

--установившиеся 250

Самодуальность 110 Свойство подстановки 293 Связующая цепь 494 Сдвиговый регистр 338, 364 Сдвоенные последовательностные цепи 368

Сеть многооконечная (многоэлементная) 439

- сигнальная 438

Сигналы готовности (завершения) 276

Синхронизирующие последовательности 149 Системные множества 295

-- информация 299

-- правильные 305

Собственное множество 566

- подмножество 566 Совместимые множества 123 В-совместимые состояния 206 Сокращение таблицы переходов 199-

---иормализоваииой 203

---с параметрами, зависящими

от времени 205

- - ---не зависящими от вре-

мени 207 Состязание 209

- критическое 209

- некритическое 209 Сохранение единицы 110

- нуля НО

Степень определения события 325 Структура 568

Существенно эквивалентные последовательности 206