Логическое управление. Методы аппаратной и программной реализации

Шалыто Анатолий Абрамович


Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации. - СПб.: Наука, 2000. - 780 c.

Излагаются методы аппаратной и программной реализации алгоритмов логического управления, заданных булевыми функциями разных классов, булевыми формулами и графами переходов. Предложены методы синтеза схем из априори известных произвольных элементов. Описываются методы построения многофункциональных и универсальных логических модулей. Выполнена оценка функциональных возможностей программируемых логических матриц. Предложены однородные структуры из элементов с двусторонней и односторонней проводимостью. Разработаны методы построения схем алгоритмов, обладающих различными свойствами. Предложены логические устройства для последовательностного вычисления булевых функций. Разработаны нетрадиционные методы вычисления булевых функций, в том числе и на основе арифметических полиномов. Изложены основные положения SWITCH-технологии, предназначенной для алгоритмизации и программирования задач логического управления при использовании промышленных компьютеров и программируемых логических контроллеров. Предлагаемые методы иллюстрируются большим числом примеров. Книга предназначена для студентов, обучающихся по специальности "Управление и информатика в технических системах", и специалистов в области информатики, вычислительной техники и систем управления. Рекомендована научно-методическим советом по специальности 2101 "Управление и информатика в технических системах" в качестве учебного пособия для студентов высших учебных заведений, обучающихся по этой специальности.


ОГЛАВЛЕНИЕ

Введение

Глава 1. Булевы формулы и булевы функции. Классификация, табулирование, свойства

1.1. Классификация бесповторных булевых формул в базисе И, ИЛИ, НЕ
1.2. Деревья из двухвходовых элементов
1.2.1. Подсчет числа неизоморфных деревьев
1.2.2. Покрывающие деревья
1.2.3. Модули с простой структурой, универсальные в классе формул
1.3. PN-классификация бесповторных формул в базисе И, ИЛИ, НЕРАВНОЗНАЧНОСТЬ, НЕ
1.4. Свойства бесповторных формул в базисе И, ИЛИ, НЕ
1.4.1. Ранг функций
1.4.2. Вычисление числа единиц по формуле
1.4.3. Свойства бесповторных пороговых формул
1.5. Отношения покрытия
1.6. Метод совместной реализации булевых функций
1.7. Новые соотношения для преобразований булевых функций
Выводы
Литература

Глава 2. Формульный метод синтеза комбинационных схем из произвольных логических элементов

2.1. Синтез схем из модулей, универсальных в классе формул
2.1.1. Реализация булевых формул схемами из положительно монотонных q-универсальных модулей
2.1.2. Минимизация числа q-универсальных модулей в схемах
2.1.3. Реализация не полностью определенных булевых функций схемами из q-универсальных модулей
2.1.4. Реализация булевых формул схемами из положительно монотонных модулей, универсальных в классе дизъюнктивных нормальных форм из q букв
2.1.5. Реализация булевых формул схемами из немонотонных q-универсальных модулей
2.1.6. Реализация булевых формул схемами из немонотонных q-универсальных модулей, использующих P-классификацию
2.2. Оценка эффективности многофункциональных логических модулей и реализация булевых формул схемами из этих модулей
2.3. Построение универсальных микросборок и плат с высокой логической эффективностью
2.4. Синтез комбинационных схем из произвольных логических элементов
2.4.1. Синтез схем из двухвходовых элементов И-НЕ
2.4.2. Синтез схем из набора микросхем серии 133
Выводы
Литература

Глава 3. Мультиплексорный метод реализации булевых функций схемами из произвольных логических элементов

3.1. Обзор литературы
3.1.1. Декомпозиции булевых функций
3.1.2. Декомпозиционные методы синтеза комбинационных схем
3.1.3. Методы решения логических уравнений
3.2. Мультиплексорная декомпозиция и стандартные схемы для ее реализации
3.2.1. Основные определения
3.2.2. Построение мультиплексорной декомпозиции на основе решения логических уравнений
3.2.3. Использование карт декомпозиции при мультиплексорной декомпозиции
3.2.4. Разложения Шеннона по крайним левым входным переменным
3.2.5. Универсальные разложения булевых функций по крайним правым входным переменным
3.3. Использование мультиплексорной декомпозиции при реализации булевых функций
3.3.1. Декомпозиция булевых функций по заданному образу
3.3.2. Декомпозиция булевых функций в базисе заданного модуля
3.3.3. Мультиплексорный метод реализации булевых функций
3.4. Сравнение мультиплексорного метода с известными методами
3.4.1. Мультиплексорный метод и декомпозиционный метод Миллера
3.4.2. Мультиплексорный метод и декомпозиция булевых функций с помощью булевых матриц
3.4.3. Мультиплексорный метод и метод решения логических уравнений
Выводы
Литература

Глава 4. Реализация булевых функций схемами из мажоритарных элементов

4.1. Методы реализации булевых функций схемами из трехвходовых мажоритарных элементов
4.1.1. Основные соотношения
4.1.2. Обзор литературы
4.1.3. Формульный метод
4.1.4. Графовый метод
4.1.5. Мультиплексорный метод
4.1.6. Оценки сложности схем
4.1.7. Реализация не полностью определенных булевых функций
4.1.8. Реализация булевых функций, описываемых формулами, бесповторными в базисе И,ИЛИ,НЕ
4.1.9. Реализация представителей всех PN-типов булевых функций трех переменных
4.1.10. Примеры реализации булевых функций четырех переменных
4.1.11. Примеры реализации булевых функций пяти переменных
4.2. Реализация булевых функций схемами из пятивходовых мажоритарных элементов
4.2.1. Основные соотношения
4.2.2. Исследование функциональных возможностей пятивходовых мажоритарных элементов
4.2.3. Примеры реализации булевых функций
4.2.4. Оценки сложности
4.3. Реализация булевых функций схемами из трех- и пятивходовых мажоритарных элементов
Выводы
Литература

Глава 5. Реализация булевых функций схемами из мультиплексоров

5.1. Методы реализации булевых функций схемами из мультиплексоров "2 в 1"
5.1.1. Модификация канонического метода Блоха
5.1.2. Распределительный метод
5.1.3. Мультиплексорный метод с настраиваемым образом декомпозиции
5.1.4. Смешанный метод
5.1.5. Графовый метод
5.1.6. Формульный метод
5.1.7. Формульный метод в мультиплексорной форме
5.1.8. Примеры сравнительного использования предложенных методов
5.2. Методы реализации булевых функций схемами из k мульплексоров "2 в 1"
Выводы
Литература

Глава 6. Использование мультиплексорного метода для реализации схем в различных элементных базисах

6.1. Реализация булевых функций схемами из двухвходовых элементов И-НЕ (ИЛИ-НЕ)
6.2. Реализация булевых функций схемами из трехвходовых монотонных модулей
6.3. Реализация булевых функций схемами из WOS-модулей
6.4. Реализация булевых функций схемами из модулей, универсальных в классе пороговых функций трех переменных
6.5. Реализация булевых функций схемами из 3-универсальных немонотонных модулей
6.6. Реализация булевых функций схемами из трехмембранных пневматических реле Р-3Ф серии УСЭППА
6.7. Реализация булевых функций схемами из модулей, универсальных в классе произвольных булевых функций трех переменных
6.8. Реализация булевых функций схемами из модулей Препараты - Мюллера
6.9. Реализация булевых функций схемами из 4-универсальных модулей
6.10. Реализация булевых функций схемами из одного типа функциональных преобразователей СБИС программируемой логики
6.11. Реализация булевых функций большого числа переменных
6.12. Реализация автоматов с памятью схемами, использующими триггеры
Выводы
Литература

Глава 7. Методы построения многофункциональных логических модулей

7.1. Основные характеристики многофункциональных логических модулей
7.2. Мультиплексорный метод - метод объединения фрагментов
7.2.1. Основные положения
7.2.2. Применение отношений покрытия для упрощения порождающих формул модулей
7.2.3. Объединение заданных булевых функций
7.2.4. Объединение различных "половинок" заданных булевых функций
7.2.5. Объединение различных "половинок" булевых функций, PN-однотипных с заданными функциями
7.2.6. Объединение различных фрагментов меньших, чем "половинки" заданных булевых функций
7.3. Модифицированный мультиплексорный метод
7.4. Дополнительные методы
7.4.1. Использование преобразований булевых функций
7.4.2. Использование NPN-классификации
Выводы
Литература

Глава 8. Построение многофункциональных логических модулей

8.1. Модули, универсальные в классе дизъюнктивных нормальных форм из q букв
8.2. Модули, универсальные в классе произвольных формул в базисе И,ИЛИ,НЕ из q букв
8.3. Модули, универсальные в классе произвольных формул в базисе И,ИЛИ,НЕРАВНОЗНАЧНОСТЬ,НЕ из q букв
8.4. Модуль, универсальный в классе произвольных булевых функций трех переменных
8.5. Модули, настраиваемые на функции триггеров
8.6. Модули, настраиваемые на функции генерации
8.7. Модули с параллельно-последовательной настройкой
Выводы
Литература

Глава 9. Модули, универсальные в классе симметрических функций

9.1. Обзор литературы
9.2. Основные определения
9.3. Два типа модулей, универсальных в классе симметрических функций
9.4. Методы построения симметрических реализаций булевых функций
9.5. Исследование функциональных возможностей симметрических модулей
9.6. Реализация булевых функций схемами из симметрических модулей
Выводы
Литература

Глава 10. Модули, универсальные в классе самодвойственных функций и в "близких" к ним классах

10.1. Обзор литературы
10.2. Реализация булевых функций мультиплексорами
10.3. Реализация булевых функций, инверсных заданным
10.4. Реализация булевых функций с инвертированным столбцом значений или его верхней, или нижней половиной
10.5. Реализация булевых функций, антидвойственных заданным
10.6. Реализация булевых функций и им антидвойственных
10.7. Реализация самоантидвойственных (зеркальных) функций
10.8. Реализация булевых функций, двойственных заданным
10.9. Реализация булевых функций и им двойственных
10.10. Реализация самодвойственных функций
10.11. Модуль, универсальный в рассмотренных классах булевых функций
10.12. Одновременная реализация булевой функции и функции, ей антидвойственной (двойственной)
Выводы
Литература

Глава 11. Модули, универсальные в классе всех булевых функций

11.1. Универсальные логические модули n переменных (УЛМ n) без парафазных входных переменных
11.2. Модули УЛМ n с одной парафазной входной переменной
11.3. Модули УЛМ n с n парафазными входными переменными (УЛМ n,n)
11.4. Использование блоков модулей УЛМ m,m при построении модулей УЛМ n,n
11.5. Модули УЛМ n,m первого типа
11.6. Модули УЛМ n,m второго типа
11.7. Модули УЛМ n без разделения информационных и настроечных входов
Выводы
Литература

Глава 12. Оценка функциональных возможностей программируемых логических матриц

12.1. Непосредственная реализация произвольной скобочной булевой формулы
12.2. Реализация дизъюнктивной нормальной формы, соответствующей произвольной скобочной булевой формуле
Выводы
Литература

Глава 13. Однородные модули из элементов с двусторонней проводимостью и реализация комбинационных схем

13.1. Модули, универсальные в классе произвольных булевых формул в базисе И,ИЛИ,НЕ
13.2. Топологический метод реализации многовыходных комбинационных схем
Выводы
Литература

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

14.1. Реализация булевых формул в базисе И, ИЛИ, НЕ каскадами Макхопадхая и пороговыми элементами
14.2. Реализация булевых функций каскадами Майтра
14.3. Реализация булевых формул многоканальными однородными структурами
14.4. Реализация булевых формул плоскостными однородными структурами
Выводы
Литература

Глава 15. Реализация булевых формул в базисе И,ИЛИ,НЕ линейными бинарными графами

15.1. Формульный метод
15.2. Проверка правильности построения линейного бинарного графа
15.3. Перечисление путей в линейном бинарном графе
15.4. Использование всех путей в качестве полного теста
15.5. Подсчет числа путей в бинарном графе
15.6. Подсчет числа путей в блочном бинарном графе
15.7. Оценки числа и суммарной длины путей в линейных бинарных графах
15.8. Анализ оценок числа путей в линейных бинарных графах
15.9. Верхняя оценка числа путей в линейных бинарных графах, реализующих инвариантные формулы
15.10. Оценки числа путей в линейных бинарных графах для оптимально записанных формул
15.11. Минимизация числа и суммарной длины путей в линейных бинарных графах
15.12.Реализация повторных формул
Выводы
Литература

Глава 16. Методы построения бинарных графов для автоматов без памяти

16.1. Структурирование линейных бинарных графов
16.1.1. Дублирование вершин
16.1.2. Введение состояний
16.1.3. Введение булевых признаков
16.1.4. Использование выходной переменной в качестве булева признака
16.2. Метод зависимых фрагментов
16.2.1. Реализация бесповторных пороговых формул
16.2.2. Минимизация числа вершин
16.2.3. Смешанный метод
16.2.4. Использование разложения Шеннона
16.2.5. Использование булевых признаков
16.2.6. Использование выходной переменной в качестве булева признака
16.3. Метод независимых фрагментов
16.4. Методы построения бинарных графов для одной булевой функции
16.4.1. Распределительный метод
16.4.2. Канонический метод Блоха
16.4.3. Реализация булевых функций линейными бинарными графами
16.4.4. Оценки числа условных вершин в бинарных графах
16.4.5. Сокращение перебора при поиске минимальной реализации заданной булевой функции
16.4.6. Модификация канонического метода
16.5. Методы построения бинарных графов для систем булевых функций
16.5.1. Метод построения простых бинарных графов
16.5.2. Метод последовательного соединения простых бинарных графов
16.5.3. Метод построения обобщенных бинарных графов
16.5.4. Метод независимых фрагментов
16.5.5. Метод зависимых фрагментов
16.6. Методы построения арифметических граф-схем для систем булевых функций
16.6.1. Реализация одной булевой функции
16.6.2. Метод вынесения операторных вершин
16.6.3. Метод взвешивания функций
16.6.4. Стандартная реализация строк таблицы истинности
16.6.5. Реализация типов значений арифметической функции
16.6.6. Упрощение булевых формул, осуществляющих выбор типов значений арифметических функций
16.6.7. Реализация с многократным вычислением однотипных значений арифметических функций
16.7. Методы построения векторных граф-схем
16.8. Построение комбинационных схем из демультиплексоров
Выводы
Литература

Глава 17. Программная реализация автоматов с памятью

17.1. Метод независимых фрагментов
17.2. Канонический и распределительный методы
17.3. Модификация канонического метода
17.4. Верификация бинарных графов
17.5. Построение бинарных графов по графам переходов
17.5.1. Автоматы без выходного преобразователя
17.5.2. Автоматы Мура
17.5.3. Автоматы Мили
17.6. Программная реализация графов переходов изоморфными "схемами" из функциональных блоков
17.6.1. Первый метод
17.6.2. Второй метод
Выводы
Литература

Глава 18. Логические устройства для последовательностного вычисления булевых функций

18.1. Операторные устройства
18.1.1. (k+1)-адресные операторные устройства
18.1.2. Трехадресное операторное устройство
18.1.3. 2,5-адресное операторное устройство
18.1.4. Двухадресное операторное устройство
18.1.5. Одноадресное операторное устройство
18.1.6. Операторные устройства, универсальные в классе формул в базисе И,ИЛИ,НЕ
18.1.7. Операторные устройства с микропрограммной реализацией операторов
18.1.8. Операторные устройства без кода операций
18.1.9. Операторные устройства с RS-триггерами
18.1.10. Стековое операторное устройство
18.1.11. Буквенное операторное устройство
18.2. 2 - нарные устройства
18.2.1. Тетрадные устройства
18.2.2. Бинарные устройства
18.3. Операторно-бинарные устройства
18.3.1. Четырехадресное операторно-бинарное устройство
18.3.2. Трехадресное операторно-бинарное устройство
18.4. Ассоциативные устройства
18.4.1. Последовательностный аналог постоянного запоминающего устройства
18.4.2. Последовательностный аналог программируемой логической матрицы
18.5. Сравнительные характеристики рассмотренных устройств
18.6. Микропроцессорные устройства
Выводы
Литература

Глава 19. Нетрадиционные методы вычисления булевых функций

19.1. Метод логических шкал
19.2. Реализация одной булевой функции с помощью линейных арифметических выражений
19.2.1. Реализация пороговых функций
19.2.2. Реализация бесповторных пороговых формул
19.2.3. Реализация произвольных булевых формул с помощью суперпозиции бесповторных пороговых формул
19.2.4. Реализация булевых формул одним линейным арифметическим выражением, использующим операции округления до ближайшего целого
19.3. Реализация логических функций интерполяционными полиномами
19.3.1. Реализация полностью определенных булевых функций
19.3.2. Реализация не полностью определенных булевых функций
19.3.3. Реализация многозначных логических функций
19.4. Реализация булевых функций с помощью спектрального метода
Выводы
Литература

Глава 20. Реализация булевых функций с помощью арифметических полиномов

20.1. Реализация булевых функций арифметическими полиномами
20.1.1. Реализация одной булевой формулы
20.1.2. Реализация одной симметрической функции
20.1.3. Реализация одной булевой формулы с использованием операции "sign
20.1.4. Реализация одной булевой формулы с использованием операции "абсолютная величина
20.1.5. Реализация системы булевых функций одним арифметическим полиномом
20.1.6. Вычисление коэффициентов арифметического полинома на основе алгоритма Гуда
20.1.7. Условие представимости системы булевых функций линейным арифметическим полиномом - условие линейности
20.1.8. Арифметические полиномы и полиномы Жегалкина
20.1.9. Арифметические полиномы и спектральные представления булевых функций
20.2. Реализация системы булевых функций с использованием линейных арифметических полиномов
20.2.1. Реализация систем булевых функций двух и трех переменных
20.2.2. Формирование групп значений системы булевых функций, реализуемых одним линейным полиномом.. 653
20.2.3. Реализация систем булевых функций четырех переменных
20.2.4. Реализация систем булевых функций пяти и более переменных
20.2.5. Реализация алгоритма управления посадкой плавучей полупогружной буровой установки
20.3. Реализация одной булевой функции одним линейным арифметическим полиномом с маскированием
20.3.1. Реализация булевой функции безызбыточным линейным арифметическим полиномом
20.3.2. Реализация пороговых функций линейным арифметическим полиномом с маскированием
20.3.3. Реализация линейных булевых функций линейным арифметическим полиномом с маскированием
20.3.4. Реализация порогово-линейных функций линейным арифметическим полиномом с маскированием
20.3.5. Реализация симметрических функций линейным арифметическим полиномом с маскированием
20.4. Реализация системы булевых функций линейными арифметическими полиномами с маскированиями
20.4.1. Реализация системы линейно представимых функций одним линейным полиномом с маскированиями
20.4.2. Реализация системы произвольных булевых функций системой линейных арифметических полиномов с маскированиями
20.4.3. Реализация системы произвольных булевых функций одним линейным полиномом с условными маскированиями и операторами присваивания
Выводы
Литература

Глава 21. SWITCH-технология. Алгоритмизация и программирование задач логического управления

Литература
Заключение

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

Используемые сокращения
Предметный указатель