- •127994, Москва, ул. Образцова, 15
- •Введение
- •1. Булевы функции (бф).
- •1.1. Аналитическое представление бф.
- •1.1.1. Дизъюнктивная совершенная нормальная форма.
- •1.1.2. Конъюнктивная совершенная нормальная форма.
- •1.2. Минимизация бф.
- •1.2.1. Дизъюнктивная нормальная форма (днф).
- •1.2.3. Построение сднф по дснф.
- •1.2.2. Пути решения задачи упрощения днф бф.
- •1.2.4. Построение сднф по произвольной днф.
- •1.2.5. Получение тднф с помощью таблиц покрытий.
- •1.2.6. Недоопределенные бф и способы их задания. Простые импликанты недоопределенных бф.
- •1.2.7. Построение простых импликант недоопределенных бф методом проб.
- •1.2.8. Построение тднф недоопределенных бф.
- •1.2.9. Карты Карно.
- •2. Логические схемы (лс).
- •2.1.Основные понятия.
- •2.2. Использование скобочных преобразований днф при синтезе кс из элементов типа и, или, не.
- •2.3. Синтез кс из элементов
- •2.3.1. Кс часто используемых бф.
- •2.3.2. Кс для произвольных бф.
- •2.4.2. Алгоритм разделения тднф на к частей с минимизацией максимального веса.
- •2.4.3. Синтез кс из элементов и-не.
- •2.4.4. Синтез кс из элементов или-не.
- •2.4.5. Синтез кс из элементов и-или-не.
- •2.4.6. Синтез кс из набора элементов.
2. Логические схемы (лс).
2.1.Основные понятия.
ЛС - это физические объекты, имеющие n входов и m выходов.
n
ЛС m
На входы поступают сигналы, представляющие значения дискретных переменных. На выходах ЛС формируются сигналы - реакции на входные воздействия.
Чаще всего сегодня используются электрические сигналы, которые представляют двоичные переменные. «1» представляется высоким уровнем напряжения, например, +5 вольт, а «0» - низким уровнем, например, 0 вольт.
В ЛС закон, устанавливающий соответствие между реакцией и входным воздействием, можно описать БФ.
Это значит, что в любой момент времени набор значений двоичных переменных, представленный входными сигналами, однозначно определяет набор значений переменных, представленных выходными сигналами.
ЛС строятся из более мелких ЛС (неделимых в рамках рассмотрения), называемых логическими элементами (ЛЭ).
Процедура получения ЛС из ЛЭ заключается в том, что входы всех ЛЭ присоединяются либо к выходам других ЛЭ, либо к выходам источников входных сигналов.
Выходы некоторых лэ должны быть отмечены как выходы ЛС.
Все входы и выходы ЛЭ должны использоваться.
На вход любого ЛЭ не должен поступать сигнал, сформированный на выходе того же лэ. (Результат не должен зависеть сам от себя.) Иначе ЛС некорректна.
Рассмотрим пример некорректной ЛС.
Набор ЛЭ должен обладать свойством функциональной полноты - обеспечивать возможность построения из них ЛС, реализующих любые БФ.
К числу таких относятся ЛЭ, реализующие БФ:
И, ИЛИ, НЕ - базовый теоретический набор;
И-НЕ (
)
- элементы Шеффера;ИЛИ-НЕ (
)
- элементы Пирса;и др.
Задача синтеза ЛС состоит в получении схемы из заданного набора ЛЭ. При этом можно говорить о схеме:
с минимумом числа лэ;
с минимумом числа последовательно соединенных лэ;
с какими-то другими критериями качества;
без использования критериев качества.
Простейший прием синтеза ЛС состоит в моделировании формулы, реализуемой БФ, схемой из заданных БФ.
Для этого нужно уметь строить схемы для БФ всех операций формулы.
Если БФ ЛЭ непосредственно реализуют операции, используемые в формуле, задача упрощается.
Рассмотрим пример.
Дано:
F =
Набор ЛЭ:
Построить ЛС, реализующую F из заданного набора ЛЭ.
Строим схему от выхода!
Если бы набор ЛЭ был другим, то для той же самой БФ, ЛС изменится.
Набор ЛЭ:
Формулу всегда можно представить ЛС, но есть ЛС не представимые формулой.
Это такие ЛС, в которых есть ЛЭ с выходами, идущими к нескольким ЛЭ.
Пример.
Эту ЛС можно описать аналитически совокупностью БФ вида:
F =
F1
F2
F1 = A& F3 Такой прием пригоден
F2 = D& F3 для любой ЛС.
F3 = B C
Выполнив подстановки, мы получим
F = (A&(BC)) (D&(BC)).
Построив по этой формуле ЛС, получим
Полученная ЛС не совпадает с исходной (сложнее).
Данный пример показывает, как получить аналитическое описание БФ в виде совокупности БФ для ЛС. Так (совокупностью БФ) можно описать любую ЛС.
Переходя от совокупности БФ к формуле, можно получить описание более сложной ЛС.
Формула не позволяет описывать ЛС, в которой объединены одинаковые части схемы.
Однако, имея формулу, можно получить по ней совокупность БФ, описывающую ЛС с объединенными одинаковыми частями схемы. (Этим объясняется наш интерес к формулам.)
В заключение отметим, что в настоящее время ЛС чаще всего называют комбинационные схемы, подчеркивая тем самым, что реакция схемы определяется комбинацией значений входных сигналов. Комбинационные схемы (КС) - термин, который мы будем использовать в дальнейшем.
