Читать «Математический аппарат инженера» онлайн - страница 61

Пусть X_i - алфавит входной переменной х_i, а Y_i – алфавит выходной переменной y_i. Конечный автомат с n входами и m выходами характеризуется входным алфавитом Х = Х₁ × Х₂ × ... Х_n и выходным алфавитом Y = Y₁ × Y₂ × ... Y_m, причем символами входного алфавита служат слова x = (x₁, x₂, …, x_n) длины n, а символами выходного алфавита - слова y = (y₁, y₂, …, 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₁, s₂, …, s_k, характеризующих состояние схемы. Набор всех возможных состоянии, которые присущи данной схеме, называется множеством состояний. Если S₁, S₂, …, S_k - конечные алфавиты переменных состояния s₁, s₂, …, s_k, то множество состояний S = S₁ × S₂ × … × S_k также является конечным множеством.

Строгое определение понятия состояния связывается с той ролью, которое оно играет при описании конечных автоматов. Во-первых, значения совокупности выходных переменных на ν-м такте у(ν) = (y₁(ν), y₂(ν), …, y_m(ν)), однозначно определяется значениями входных переменных x(ν) = (x₁(ν), x₂(ν), …, x_n(ν)) и состоянием s(ν) = (s₁(ν), s₂(ν), …, s_k(ν)), на том же такте, т.е. у(ν) = λ (x(ν), s(ν)). Во-вторых, состояние s(ν + 1) в следующем (ν + 1)-м такте однозначно определяется входными переменными х(ν) и состоянием s(ν) в предыдущем такте, т.е. s(ν + 1) = δ (x(ν), s(ν)).