Математический аппарат инженера - страница 44

- !!!!!!!!!!!!!!!!!!!!! -

- Продолжение следует... -

...

2. Алгебра логики

3. Контактные схемы

4. Логические схемы

5. Минимизация булевых функций

1. Основные определения. В контактных и логических схемах значения выходных переменных определяются только комбинацией значений переменных на входах в данный момент времени. Поэтому их называют комбинационными схемами. В более общем случае выходные переменные могут зависеть от значении входных переменных не только в данный момент, но и от их предыдущих значений. Иначе говоря, значения выходных переменных определяются последовательностью значений входных переменных, в связи, с чем схемы с такими свойствами называют последовательностными. Если входные и выходные переменные принимают значения из конечных алфавитов, то оба типа схем объединяются под названием конечные автоматы.

Пусть X_>i - алфавит входной переменной х_>i, а Y_>i – алфавит выходной переменной y_>i. Конечный автомат с n входами и m выходами характеризуется входным алфавитом Х = Х_>1 × Х_>2 × ... Х_>nи выходным алфавитом Y = Y_>1 × Y_>2 × ... Y_>m, причем символами входного алфавита служат слова x = (x_>1, x_>2, …, x_>n) длины n, а символами выходного алфавита - слова y = (y_>1, y_>2, …, y_>m) длины m, где x_>i∈ X_>iи y_>i∈ Y_>i. Особого внимания заслуживают конечные автоматы с двузначным структурным алфавитом, зависимости между входными и выходными переменными которых выражаются булевыми санкциями. Их значение обусловлено тем, что любая информация может быть представлена в двоичных кодах (двоично-десятичные коды чисел, телетайпный код в технике

- 564 -

связи и т.п.). В то же время при технической реализации автоматов используются преимущественно двоичные элементы и двузначная логика.

В реальных условиях сигналы представляются непрерывными функциями времени, поэтому для надежного различения сигналов требуется, чтобы новые значения на входах появлялись после окончания переходных процессов, связанных с предыдущими значениями. При рассмотрении логической структуры автоматов обычно отвлекаются от существа этих процессов и считают, что переменные изменяются не непрерывно, а мгновенно в некоторые моменты времени, называемые тактами. Интервалы между тактами могут быть различными, но без потери общности их можно считать равными Δt . Предполагается, что тактовые моменты t_{>ν + 1} =t_>ν + Δt определяются синхронизирующими сигналами. Таким образом, вводится понятие дискретного автоматного времени t_>n(n = 1, 2, ...), причем переменные зависят не от физического времени, а от номера такта ν, т. е. вместо непрерывных функций x(t) рассматриваются дискретные значения х(ν).

2. Состояния. Кроме входных и выходных переменных, можно выделить некоторую совокупность промежуточных переменных, которые связаны с внутренней структурой автомата. В комбинационных схемах промежуточные переменные непосредственно не участвуют в соотношениях вход - выход. Напротив, выходные функции последовательностных схем в качестве своих аргументов, кроме входных переменных, обязательно содержат некоторую совокупность промежуточных переменных s_>1, s_>2, …, s_>k, характеризующих состояние схемы. Набор всех возможных состоянии, которые присущи данной схеме, называется множеством состояний. Если S_>1, S_>2, …, S_>k - конечные алфавиты переменных состояния s_>1, s_>2, …, s_>k, то множество состояний S = S_>1 × S_>2 × … × S_>k также является конечным множеством.

Строгое определение понятия состояния связывается с той ролью, которое оно играет при описании конечных автоматов. Во-первых, значения совокупности выходных переменных на ν-м такте у(ν) = (y_>1(ν), y_>2(ν), …, y_>m(ν)), однозначно определяется значениями входных переменных x(ν) = (x_>1(ν), x_>2(ν), …, x_>n(ν)) и состоянием s(ν) = (s_>1(ν), s_>2(ν), …, s_>k(ν)), на том же такте, т.е. у(ν) = λ (x(ν), s(ν)). Во-вторых, состояние s(ν + 1) в следующем (ν + 1)-м такте однозначно определяется входными переменными х(ν) и состоянием s(ν) в предыдущем такте, т.е. s(ν + 1) = δ (x(ν), s(ν)).

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