Основы дискретной математики

Построение компьютера ведется по следующей цепочке:

элементы → узлы → устройства.

Элементы по своему назначению делятся на следующие группы: логические; запоминающие; вспомогательные.

Нас интересуют логические элементы – на их основе строятся комбинационные схемы. К числу основных логических элементов, применяемых в ЭВМ и образующих функционально полный набор (т. е. тако

й набор элементов, с помощью которого может быть реализована любая сложная логическая функция), относятся логические элементы И (конъюнктор), ИЛИ (дизъюнктор), НЕ (инвертор). Хотя в ряде случаев некоторые логические выражения могут быть проще реализованы с помощью более сложных логических элементов, таких, как И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ, ограничимся использованием первой группы элементов.

Узел – это совокупность функционально связанных между собой элементов. Узлы компьютера по своему функциональному назначению делятся на следующие группы: регистры; дешифраторы; шифраторы; схемы сравнения кодов; электронные счетчики; сумматоры.

7.2 Практическая часть

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

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

Рисунок 7.2 – Иллюстрация к использованию Мастера функций

В качестве аргументов логические функции И, ИЛИ, НЕ одинаково трактуют значения «0» и «ЛОЖЬ», 1 и «ИСТИНА», а в качестве результата выдают только значения «ЛОЖЬ» или «ИСТИНА». Поэтому для перехода от значений «ЛОЖЬ» и «ИСТИНА» к привычным 0 и 1 используется функция ЕСЛИ.

7.2.1 Схемы сравнения кодов

Организация сравнения двух двоичных чисел заключается в выработке признака равенства (равнозначности) или признака неравенства (неравнозначности) двух сравниваемых чисел. Ограничимся признаком равенства.

Одноразрядная схема сравнения кодов

Значение признака равенства q при сравнении одноразрядных переменных описывается таблицей истинности, представленной на рисунке 7.3.

В ячейку в E7 введена формула: =ЕСЛИ (C7=D7; 1; 0), которая затем скопирована в ячейки D8:D10.

Значение q1 функции виде СДНФ: .

Рисунок 7.3 – Образец выполнения работы

Упрощение выражения не требуется, пункт 3 порядка проектирования логических схем отсутствует.

Схема имеет вид, представленный на рисунке 7.3. Схема начерчена непосредственно в Excel с помощью панели рисования с использованием таких приемов, как копирование повторяющихся элементов, группировка.

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

Ячейки C14 и D14 отведены для ввода сравниваемых одноразрядных двоичных чисел. Им присвоены имена а и b соответственно.

Установлена проверка данных на корректность (ввод только 0 и 1). (рисунки 7.4 – 7.5.)

Рисунок 7.4 – Подсказка при вводе значений

Рисунок 7.5 – Сообщение об ошибке, в случае ввода некорректных данных

Для этого ячейки C14 и D14 выделены и выполнена команда Данные, Проверка. В диалоговом окне Проверка вводимых значений установить нужные параметры (рисунки 7.6, а-в).

Рисунок 7.6 в-Настройка проверки вводимых значений

В ячейку K22 введена формула:

=ЕСЛИ (ИЛИ(И (НЕ(C14); НЕ(D14)); И (C14; D14))=ИСТИНА; 1; 0).

Функция ЕСЛИ используется лишь для преобразования значения «ИСТИНА» в 1, а значения «ЛОЖЬ» в 0.

В ячейку K23 введена формула:

=ЕСЛИ (K22=1; «Числа равны»; «Числа не равны»).

Для того чтобы случайно что-то не испортить на листе, лист защищен, кроме ячеек, в которые вводятся сравниваемые числа. Эти ячейки выделены, и выполнена команда Формат, Ячейка, на вкладке Защита снят флажок Защищаемая ячейка. Затем выполнена команда Сервис, Защита, Защитить лист.

На рисунке 7.3 показан вариант, когда на входы схемы аi, и bi поступают два нуля, на выходе схемы имеем q1 (числа равны). Подавая на входы другие комбинации 0 и 1, можно увидеть, что схема работает точно так, как описывает таблица истинности. Можно дополнительно ввести формулы для проверки сигналов на выходах любых элементов схемы.

Многоразрядная схема сравнения кодов

Признак равенства двухразрядных чисел q принимает значение 1, если выполняется попарно равенство всех разрядов двоичных чисел.

Для примера приведена двухразрядная схема (рисунок 7.7), что связано лишь с тем, что неудобно рассматривать работу схемы, если она выходит за пределы экрана. Двухразрядная схема состоит из двух одноразрядных схем.

Ячейки C7 и D7 отведены для поразрядного ввода первого числа, им присвоены имена a1 и а0 соответственно. Ячейки E7 и F7 отведены для ввода второго числа, им присвоены имена b1 и b0 соответственно.

В ячейку L7 введена формула для выдачи результата сравнения старших разрядов чисел:

=ИЛИ (И(НЕ(C7); НЕ(E7)); И (C7; E7)).

В ячейку L46 введена формула для выдачи результата сравнения младших разрядов чисел:

=ИЛИ (И(НЕ(F7); НЕ(D7)); И (F7; D7)).

В ячейку O22 введена формула для выдачи признака равенства чисел:

=ЕСЛИ (И(L46; L7)=ИСТИНА; 1; 0).

В ячейку O23 введена формула для выдачи сообщения о результате сравнения чисел:

=ЕСЛИ (O22=1; «Числа равны»; «Числа не равны»).

Рисунок 7.7 – Двухразрядная схема сравнения кодов

На рисунке 7.7 представлен результат сравнения чисел 10 и 11. На экране результат сравнения равен 0 и выдано сообщение «Числа не равны».

7.2.2 Дешифраторы

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

Если количество двоичных разрядов дешифрируемого числа обозначить через n, то число выходов дешифратора равно К = 2n.

 Скачать реферат