Понятие о цифровом автомате с памятью, формы его задания

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

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

Математически цифровой автомат А определяется как множество из пяти элементов:

(1)

где – множество входных сигналов автомата, называемое его входным алфавитом; – множество внутренних состояний автомата, называемое также внутренним алфавитом автомата; – множество выходных сигналов автомата, называемое его выходным алфавитом; f – функция переходов, задающая связь между парой «внутреннее состояние – входной сигнал» и следующим внутренним состоянием; φ – функция выходов, задающая связь между парой «внутреннее состояние – входной сигнал» и выходным сигналом.

Цифровой автомат называется конечным, если конечны образующие его множества. В дальнейшем будем рассматривать конечные ЦА.

Отдельные сигналы (состояния) называются буквами (символами) алфавита, а конечные совокупности сигналов – словами в заданном алфавите. Таким образом, ЦА осуществляет переработку слов, заданных в алфавите Х, в слова в алфавите Y.

Считается, что ЦА переходит из одного состояния в другое скачкообразно (мгновенно), что является идеализацией действительных условий и позволяет упростить анализ и синтез конкретных устройств. Поскольку ЦА является преобразователем дискретной информации, он функционирует в определенные моменты времени, т.е. непрерывная шкала времени разделяется на отдельные в общем случае неравные интервалы, называемые тактами, которые можно пронумеровать целыми положительными числами: 0-й такт, 1-й такт и т.д.

Закон функционирования ЦА задается следующими уравнениями:

(2)

(3)

Функции переходов f(x) и выходов φ(t) дают полное описание автомата, если они каким-либо образом заданы, а в формулах (2) и (3) они только обозначены. Наиболее удобно задавать эти функции таблично. Для этого строят две таблицы: переходов и выходов (таблица переходов часто называется таблицей состояний). Обе таблицы являются двухкоординатными. Число горизонтальных входов в них берется равным количеству возможных входных сигналов, а число вертикальных входов – равным количеству внутренних состояний данного автомата. В клетках на пересечении строк и столбцов проставляются значения выходной величины: Q(t+1) в таблице переходов и Y(t) – в таблице выходов. ЦА, описываемые зависимостями (2) и (3), называются автоматами Мили. На практике иногда удобнее функцию выходов трактовать как функцию только одного аргумента – внутреннего состояния автомата:

(4)

поскольку влияние входного сигнала Х(t-1) все равно скажется через величину Q(t). ЦА, описываемые зависимостями (2) и (4), называются автоматами Мура.

Для любого автомата Мили существует эквивалентный ему автомат Мура и наоборот. Для автоматов Мура обычно строится обобщенная таблица переходов-выходов, называемая обмеченной, поскольку таблица выходов вырождается в одну строчку соответствия внутренних состояний и выходных сигналов. В частности для простейшего автомата Мура, представленного на рисунке 1, а и состоящего всего из одного триггера с тремя входами (установка в нуль х₀, установка в единицу х₁ и счетный вход х₂), если соблюдается условие возникновения входного сигнала только на одном из этих входов, можно составить следующую отмеченную таблицу переходов (таблица 1).

Рисунок 1 – Простейший автомат Мура на основе Т-триггера. Структурная схема (а) и граф переходов (б)

Таблица 1 – Отмеченная таблица переходов для простейшего автомата Мура

Входные сигналы	Внутренние состояния и выходные сигналы
Q₀/Y₀	Q₁/Y₁
x₀ x₁ x₂	Q₀/Y₀ Q₁/Y₁ Q₁/Y₁	Q₀/Y₀ Q₁/Y₁ Q₀/Y₀
Примечание – «Q₀» означает нулевое состояние триггера, а «Q₁» – единичное.

Функционирование цифрового автомата с памятью можно задавать диаграммой состояний (графом переходов), которые отражают число устойчивых состояний автомата и условия перехода из одного состояния в другое. На рисунке 1, б показан граф переходов автомата Мура на основе Т-триггера.

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

Построение любого ЦА возможно лишь в том случае, если выбранный для синтеза набор элементов является структурно полным. Для этого необходимо и достаточно, чтобы он содержал логические элементы, образующие базис для синтеза КЦУ и хотя бы один элемент памяти, обладающий полной системой переходов и выходов. Автомат Мура обладает такими свойствами, так как в каждом внутреннем состоянии он вырабатывает выходной сигнал, отличный от других выходных сигналов. Обыкновенная линия задержки (ЛЗ) является простейшим автоматом Мура. Вместо ЛЗ можно использовать более сложные элементы памяти, называемые триггерами.

ЦА с памятью разделяют на две части: память и комбинационную цепь (КЦ). На входы КЦ подаются входные сигналы и сигналы состояния автомата. На ее выходе вырабатываются выходные сигналы и сигналы перевода автомата в новое состояние.

ЦА с памятью делятся на асинхронные и синхронные. В асинхронных автоматах (рисунок 2, а) роль элементов памяти играют линии задержки (ЛЗ), через которые сигналы состояния передаются на входы КЦ, чтобы совместно с новым набором входных переменных определить следующую пару значений Y и Q на выходе. Практическое применение асинхронных автоматов затруднено из-за сильного влияния на их работу задержек сигналов в цепях автомата, создающих статические и динамические риски.

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

Рисунок 2 – Асинхронный (а) и синхронный (б) цифровые автоматы с памятью