| ОГЛАВЛЕНИЕ | 3
|
| Предисловие к первому изданию | 7
|
| Глава 1. Модели электронных матричных схем | 11
|
| 1. Электронные матричные схемы | 11
|
| Вентильные сетки | 11
|
| Структурные и функциональные булевы матрицы | 12
|
| Вентильные матричные схемы | 13
|
| Транзисторные матричные схемы | 15
|
| Каскадные схемы и программируемые логические матрицы | 18
|
| 2. Булевы функции и их матричные представления | 21
|
| Булевы функции и их простейшие формы | 21
|
| Элементарные булевы функции и алгебраические формы | 24
|
| Дизъюнктивные нормальные формы | 26
|
| Система булевых функций и ее представление булевыми матрицами | 28
|
| Интервальные формы систем булевых функций | 29
|
| 3. Матричные операторы | 31
|
| Уравнения для ß-схем | 31
|
| Учет неопределенности в информационных матрицах | 33
|
| Обобщение законов де Моргана | 35
|
| Уравнения для τ-схем | 36
|
| Безызбыточность матричных схем | 39
|
| Упрощенные схемные изображения | 42
|
| 4. Правильные цепочки | 44
|
| Образование правильных цепочек | 44
|
| Преобразования де Моргана | 44
|
| Эквивалентные преобразования правильных цепочек | 46
|
| Универсальность правильных цепочек | 50
|
| Глава 2. Методы комбинаторного поиска | 52
|
| 5. Комбинаторный поиск | 52
|
| Полный перебор | 52
|
| Дерево поиска | 53
|
| Методы комбинаторного поиска | 56
|
| Анализ троичной матрицы на вырожденность | 59
|
| 6. Задачи о покрытии множеств | 64
|
| Нахождение всех покрытий множества | 64
|
| Нахождение кратчайшего покрытия | 67
|
| Демонстрация алгоритма | 70
|
| 7. Поиск минимальных разбиений | 74
|
| Задача о раскраске графа | 74
|
| Метод последовательной раскраски | 75
|
| Пример | 77
|
| Метод конденсации | 79
|
| Демонстрация метода | 82
|
| 8. Приближенные методы | 84
|
| Стратегии поиска оптимального решения | 84
|
| Поиск приближений | 89
|
| Разбиение системы функций | 92
|
| Глава 3. Теория элементарных матричных схем | 97
|
| 9. Исследование уравнений элементарных матричных схем | 97
|
| Задача моделирования | 97
|
| Задача анализа | 98
|
| Задача синтеза | 104
|
| 10. Задачи диагностики | 107
|
| Сравнение матричных операторов | 107
|
| Отображение интервалов | 111
|
| Задача диагностики для ß-схемы | 113
|
| Пример | 115
|
| Приближенный метод | 118
|
| Диагностика неисправностей в т-схемах | 119
|
| 11. Нахождение минимального дизъюнктивного базиса | 121
|
| Минимальный дизъюнктивный базис для матрицы У и ее кратчайшее минорное покрытие | 121
|
| Прямой метод нахождения кратчайшего минорного покрытия | 123
|
| Редуцирование матрицы У | 126
|
| Комбинирование методов | 130
|
| Заключительные замечания | 134
|
| 12. Задача о кодировании | 135
|
| О перекодировании входных булевых векторов | 135
|
| Нахождение минимального диагностического теста | 137
|
| Обобщение задачи о минимальном тесте | 142
|
| Поиск минимальной троичной кодирующей матрицы | 144
|
| 13. Задача о генерировании | 148
|
| Задача о кратчайшем покрытии булевой матрицы парными минорами | 148
|
| Точный метод | 149
|
| Приближенный метод | 151
|
| Глава 4. Минимизация ДНФ булевой функции | 155
|
| 14. Классические методы минимизации булевых функций | 155
|
| Реализация монотонных булевых функций | 155
|
| Задача минимизации ДНФ | 158
|
| Метод Квайна — МакКласки | 160
|
| Метод Блека — Порецкого | 165
|
| 15. Сжатие булевой матрицы | 168
|
| Определяющие элементы и обязательные интервалы | 168
|
| Допустимые интервалы как элементы кратчайшего покрытия | 172
|
| Пример | 175
|
| Ветвящиеся процессы конструирования интервальных покрытий | 177
|
| 16. Методы сканирования булева пространства | 179
|
| Метод минимального соседства | 180
|
| Представление булевой функции на гиперкубе и его двумерной развертке | 184
|
| Визуальный метод минимизации булевых функций | 189
|
| 17. Упрощение троичных матриц | 191
|
| Устранение избыточности | 191
|
| Нахождение обязательных строк | 194
|
| Построение допустимых совокупностей максимальных интервалов | 197
|
| Пример | 199
|
| Матрица простых совокупностей | 202
|
| 18. Оптимальная реализация слабо определенных булевых функций | 206
|
| Частичные и слабо определенные булевы функции | 206
|
| Нахождение кратчайшей ДНФ. слабо определенной булевой функции | 207
|
| Метод конкурирующих интервалов | 211
|
| Пример | 213
|
| Глава 5. Синтез программируемых логических матриц | 218
|
| 19. Оптимизация ПЛМ по входу | 218
|
| Непосредственная реализация системы булевых функций | 218
|
| Классификация аргументов частичных функций | 220
|
| Минимизация числа аргументов в реализующей системе | 222
|
| Сокращение числа транзисторов | 224
|
| Минимизация числа литералов | 226
|
| Обобщение метода на случай троичных информационных матриц | 230
|
| 20. Минимизация системы булевых функций | 233
|
| Нахождение кратчайшей ДНФ системы булевых функций | 233
|
| Пример | 235
|
| Метод выделения интервальных миноров | 238
|
| Поиск приближений к оптимальному решению | 241
|
| 21. Синтез ПЛМ с заданной выходной матрицей | 247
|
| Постановка задачи | 247
|
| Синтез «от входа» | 248
|
| Синтез «от выхода» | 251
|
| Метод конструирования пересекающихся интервалов | 255
|
| 22. Диагностирование ПЛМ | 259
|
| Содержательные постановки задач | 259
|
| К диагностике неисправностей в первом ярусе ПЛМ | 262
|
| Проверка ПЛМ, реализующей одну ДНФ | 264
|
| Проверка реализации системы ДНФ | 269
|
| Об универсальном проверяющем тесте | 274
|
| Глава 6. Многоярусные комбинационные сети | 279
|
| 23. Моделирование и анализ | 279
|
| Модели многоярусных схем | 279
|
| Исследование правильных цепочек | 282
|
| Анализ оператора Вv | 285
|
| Анализ оператора Tv | 289
|
| Методы аппроксимации отображений | 292
|
| 24. Декомпозиционные методы синтеза в базисе элементарных матричных схем | 293
|
| Метод стандартной декомпозиции | 293
|
| Параллельная декомпозиция «редких» матриц | 296
|
| Комбинированная декомпозиция | 300
|
| Метод матричной факторизации | 303
|
| 25. Синтез одноярусных сетей из ПЛМ | 310
|
| Методы стандартной декомпозиции | 310
|
| Сокращение числа ПЛМ | 314
|
| Декомпозиция ПЛМ с короткими термами | 318
|
| Реализация системы слабо определенных булевых функций | 319
|
| 26. Синтез многоярусных сетей из ПЛМ | 329
|
| Декомпозиция ПЛМ, реализующей булевы функции поэлементно | 330
|
| Декомпозиция ПЛМ, реализующей булевы функции на ортогональных интервалах | 334
|
| Метод тождественных отображений в пространстве промежуточных переменных | 341
|
| Корректировка метода | 350
|
| Итерационные методы декомпозиции | 353
|
| Глава 7. Реализация автоматов с памятью | 358
|
| 27. Элементы теории последовательностных схем | 358
|
| Схемы комбинационные и последовательностные | 358
|
| Дискретные устройства и автоматы | 359
|
| Представления автоматов | 363
|
| Отношение реализации | 366
|
| 28. Секвенциальные автоматы | 368
|
| Системы секвенций | 368
|
| Отношения между секвенциальными автоматами | 372
|
| Реализация секвенциальных автоматов на ПЛМ | 376
|
| Оптимизирующие преобразования | 380
|
| 29. Устойчивость поведения автоматов | 385
|
| Состязания между булевыми переменными | 385
|
| Метод соседнего кодирования | 388
|
| Критерий отсутствия опасных состязаний при прямых переходах | 390
|
| Нахождение минимальной кодирующей матрицы | 393
|
| Критерий устойчивости для секвенциальных автоматов | 396
|
| 30. Реализация состояний и переходов на ПЛМ | 398
|
| Реализация внутренних состояний | 398
|
| Реализация микропрограммных автоматов | 404
|
| Кодирование состояний микропрограммного автомата | 408
|
| Предметный указатель | 411
|
Закревский Аркадий Дмитриевич