Автоматная функция описывает преобразование последовательности входных воздействий в последовательность выходов системой с памятью. Конечный автомат задаётся множеством состояний, функцией переходов и функцией выходов. В дискретном времени его работа описывается каноническими уравнениями \(q(t+1)=g(x(t),q(t))\) и \(z(t)=f(x(t),q(t))\)
После двоичного кодирования входов, состояний и выходов координаты \(g\) и \(f\) становятся булевыми функциями. Их реализует комбинационная СФЭ, а текущий код состояния хранится в элементах единичной задержки и подаётся обратно на вход следующего
Что важно запомнить
- Автомат отличается от комбинационной схемы наличием внутреннего состояния.
- Функция переходов вычисляет новое состояние, функция выходов — текущий выход.
- Каноническая форма: \(q(t+1)=g(x(t),q(t))\),
- Двоичное кодирование превращает переходы и выходы в системы ФАЛ.
- Начальное состояние входит в описание автомата и вместе со входной последовательностью определяет всю траекторию состояний.
- Элементы задержки сохраняют код состояния на один такт и создают память схемы.
Конечный автомат и автоматная функция
Конечный автомат имеет входной алфавит \(A\), конечное множество состояний \(Q\), выходной алфавит \(W\), функцию переходов \(g\), функцию выходов \(f\) и начальное состояние. На каждом такте входной символ и текущее состояние определяют следующее состояние. Выход определяется текущими входом и состоянием либо только состоянием в зависимости от принятой
В стандартной схемной записи курса используются уравнения \(q(t+1)=g(x(t),q(t))\) и \(z(t)=f(x(t),q(t))\). Именно зависимость от \(q(t)\) делает реализуемое преобразование автоматным, то есть зависящим от предыстории входов.
Двоичное кодирование
Состояния кодируют двоичными векторами. После этого каждая координата следующего состояния и выхода является булевой функцией координат текущего входа и состояния. Поэтому для них можно синтезировать обычные
Элементы задержки
Чтобы вычисленный в момент \(t\) код нового состояния стал текущим состоянием в момент \(t+1\), используют элементы единичной задержки. Комбинационная часть схемы вычисляет \(g\) и \(f\), а выходы блока \(g\) проходят через задержки и возвращаются как входы состояния следующего такта.
Такой цикл не является мгновенной комбинационной петлёй: задержка разрывает зависимость внутри одного такта. Поэтому функционирование можно определить последовательно по времени, начиная с заданного начального состояния.
Пример простыми словами
Пусть один бит состояния хранит чётность числа единиц, поступивших ранее. Можно взять \(q(t+1)=q(t)\oplus x(t)\) и \(z(t)=q(t)\). Элемент задержки хранит \(q(t)\), комбинационный элемент XOR вычисляет новое состояние, а на следующем такте оно становится текущим.
Частые ошибки
- Рассматривать автоматную функцию как обычную ФАЛ только от текущего входа. Выход зависит также от накопленного состояния.
- Забывать начальное состояние: без него одна и та же входная последовательность может задавать разные траектории.
- Путать элемент задержки с обычным функциональным элементом. Его роль — перенос значения между тактами, а не вычисление статической булевой функции.
