Комбинационные схемы и конечные автоматы.

При любых видах работы с информацией всегда идет речь о ее представлении в виде определенных символических структур. Любое устройство обработки дискретной информации имеет n входов и m выходов. Сигналы на входах соответствуют символам входного алфавита, а выходные – символам выходного алфавита.

Имеются два типа устройств обработки цифровой информации: на основе комбинационных схем и на основе конечных (цифровых) автоматов.

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

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

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

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

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

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

Совершенной нормальной конъюктивной формой (СНКФ) называют запись логического уравнения в виде конъюнкции (логического произведения) макстермов. Макстерм - это дизьюнкция инверсий входных переменных соответствующая в таблице истинности нулевому значению выходной функции.

В отличие от комбинационных схем конечные автоматы имеют конечное число внутренних состояний.

Выходное слово и переход автомата в следующее состояние однозначно определяются состоянием автомата и входным словом.

Функционирование конечного автомата задается:

1. входным алфавитом: X {x₀, x₁, x₂,…, x_i,… x_n},

2. выходным алфавитом: Y{у₀, y₁, y₂,…, y_i,… y_m},

3. алфавитом состояний: Q {q₀, q_1, q₂,…, q_i,… q_r,}, где q₀ – начальное состояние автомата,

4. функцией переходов, определяющей переход автомата из q_i состояния в следующее q_i+1 состояние: q_i+1 = d(q_i, x_i), или как функция времени:
Q(t+1) = d [Q(t), X(t)].

5. функцией выходов, определяющей выходные сигналы автомата в состоянии q_i: y_i = d(q_i, x_i) или, как функция времени: Y(t) = d [Q(t), X(t)].

Функция выходов (5) соответствует конечному автомату, называемому автоматомМили. Имеется несколько разновидностей конечных автоматов, используемых в устройствах цифровой обработки. Широко используемой альтернативой автомату Мили является автомат Мура.

Особенностью автомата Мура является его функция выходов. В автомате Мура выходные сигналы зависят только от состояния конечного автомата q_i.: y_i = d(q_i) или, как функция времени: Y(t) = d [Q(t)].

Основное отличие устройств на основе цифровых автоматов от комбинационных схем заключается в том, что первые содержат элементы памяти для фиксации состояний. Можно считать комбинационные схемы примитивными цифровыми автоматами с одним состоянием.

Элементы памяти цифровых автоматов – триггеры, в свою очередь являются элементарными цифровыми автоматами (автоматами Мура) с двумя устойчивыми состояниями.

Цифровые автоматы могут задаваться графами или таблицами выходов и переходов.