ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Все многообразие элементов, и блоков, из которых состоит любая ЭВМ, является примером цифрового автомата (ЦА). Под цифровым автоматом будем понимать устройство, предназначенное для преобразования цифровой информации, способное переходить по воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы. Характерной особенностью ЦА является то, что они имеют дискретное множество внутренних состояний, и переход из одного состояния в другое осуществляется скачкообразно. Реальные ЦА конечны, т.е. множества входных и выходных сигналов и множество состояний конечны.

ЦА функционируют в дискретные моменты времени, временной интервал Т между которыми называется тактом. В зависимости от того, чем определяется время Т , различают автоматы синхронного и асинхронного действия.

Для ЦА асинхронного действия и определяется моментами поступления входных сигналов. Для ЦА синхронного действия входные сигналы действуют в строго определенные моменты времени, определяемые генератором синхронизирующих импульсов, в которые и возможен переход автомата из одного состояния в другое.

По степени детализации описания различают абстрактные и структурные ЦА.

Абстрактные ЦА рассматриваются как черный ящик, имеющий один вход и один выход. При рассмотрении структуры таких ЦА отвлекаются от структуры как самого автомата, так и его входных и выходных сигналов.

Для задания абстрактного ЦА необходимо знать алфавита:

входной алфавит ,

выходной алфавит

и алфавит состояний .

Тогда закон функционирования абстрактного ЦА может быть задан уравнениями:

где - функция переходов ЦА, - функция выходов ЦА, а₀ – начальное состояние ЦА, a(t), z(t), w(t) – состояние автомата, входной и выходной сигналы в момент времени t. ЦА, закон функционирования которого определяется выражениями (1), называется автоматом Мили.

Таблица 1

ЦА можно задать и с помощью направленного графа, вершины которого отождествляются с состояниями автомата, а соединяющие их стрелки – с входными и выходными сигналами.

Рис. 1

Решая задачу построения различных цифровых устройств ЭВМ, стараются свести ее к задаче анализа и синтеза комбинационных схем. При этом в качестве основного математического аппарата используется аппарат алгебры логики. Ее создателем является английский математик Буль, поэтому алгебру логики называют также булевой алгеброй.

Основным понятием булевой алгебры является высказывание. Высказывание – это некоторое предложение, о котором можно утверждать, что оно истинно или ложно. Любое высказывание можно обозначить символом, например Х и считать, что Х=1, если высказывание истинно, и Х=0, если высказывание ложно.

Логическая переменная (булева переменная) – такая величина Х, которая может принимать толшько два значения: 0 или 1(истинно или ложно) (true или false).

Высказывание абсолютно истинно, если соответствующая ему логическая величина принимает значение, равное 1, при любых условиях. Например высказывание “Земля – это планета солнечной системы” абсолютно истинно.

Высказывание абсолютно ложно, если соответствующая ему логическая величина принимает значение, равное 0 при любых условиях. Например высказывание “Земля – спутник Марса” абсолютно ложно.

Логическая функция – это функция f(x₁, x₂,…,x_n), принимающая значение, равное 0 или 1 на наборе логических переменных x₁, x₂,…,x_n. Общее число наборов двоичных переменных, на которых определяется булева функция, равно 2ⁿ.

Любая булева функция может быть задана с помощью таблицы истинности. Чаще всего используются булевы функции одной или двух переменных. Для одной переменной существуют всего 4 различных булевы функции:

Таблица 2

Функция f₁(x) является абсолютно истинной (константа единицы).

Функция f₂(x) является абсолютно ложной (константа нуля).

Функция f₃(x), повторяющая значение логической переменной, является тождественной функцией .

Функция f₄(x), принимающая значения, обратные значениям переменной х, называется логическим отрицанием или функцией НЕ .

Для двух логических переменных существуют 16 логических функций:

Таблица 3

Фун-кция	Значения переменных х1х2	Описание функции
f1					f0 (константа нуля)
f2					или х1х2 (конъюнкция)
f3					(запрет х2)
f4					х1
f5					(запрет х1)
f6					х2
f7					(сложение по модулю 2)
f8					(дизъюнкция)
f9					(функция Пирса)
f10					(равнозначность)
f11
f12					(импликация)
f13
f14					(импликация)
f15					(функция Шеффера)
f16					f1 (константа единицы)

Дизъюнкция (логическое сложение, логическое ИЛИ) истинна только тогда, когда истинны или Х₁ или Х₂ или обе переменные.

Конъюнкция (логическое умножение, логическое И) истинна только тогда, когда истинны и Х₁ и Х₂. Обозначается Х₁Х₂, Х₁∩Х₂, Х₁&Х₂.

Сложение по модулю 2 (исключающее ИЛИ) истинна только тогда, когда Х₁ и Х₂ не равны друг другу.