Что такое цифровой автомат

9

Логические основы проектирования цифровых устройств

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

1. Синтез — это процесс построения схемы цифрового устройства по заданию.
2. Анализ — процесс обратный синтезу.

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

Рис. 1 — Схема представления цифрового автомата в виде многополюсника
X=(X1, X2, . Xm) — входные сигналы
Y=(Y1, Y2, . Yn) — выходные сигналы
S=(S1, S2, . Sp) — состояние внутренних элементов памяти автомата

В общем случае, модель представляет собой многополюсный черный ящик с m входами и n выходами (рис. 1). Состояние автомата определяется состояниями сигналов на его входах и выходах. Совокупность входных и выходных переменных Х и Y образуют входное и выходное слово автомата, соответственно.

Различные значения входных переменных образуют алфавит (т.к. алфавит входных и выходных переменных един, в дальнейшем будет рассматриваться только один алфавит). В цифровой технике алфавит входного (выходного) слова содержит два значения (две буквы) «1» и «0».

Каждое слово — набор переменных на входе или на выходе автомата, отличается от другого слова хотя бы одной буквой. Каждая буква слова поставлена в соответствие с номером входа (выхода) автомата.

Основы алгебры логики

Алгебра логики (АЛ) является основным инструментом синтеза и анализа дискретных автоматов всех уровней. Алгебру логики называют также "Булевой алгеброй". Алгебра логики базируется на трёх функциях, определяющих три основные логические операции.

1. Функция отрицания ( НЕ ). f1 = X читается, как "f1 есть (эквивалентна) НЕ Х". Элемент, реализующий функцию НЕ, называется элементом НЕ или инвертором .

Рис. 2 — Условное графическое обозначение элемента НЕ

Элемент НЕ имеет два состояния.

2. Функция логического умножения ( конъюнкции ). Функция логического умножения записывается в виде f2=X 1 ·X 2 . Символы логического умножения: &,^, •.

Функция конъюнкции читается так: "f2 есть (эквивалентна) Х 1 и Х 2 , поскольку функция истинна тогда, когда истинны 1-й и 2-й аргументы (переменные)". Конъюнкцию называют функцией И , элемент, реализующий эту функцию, элементом И .

Рис. 3 — Условное графическое обозначение элемента И

В общем случае функцию логического умножения от n переменных записывают так:

Количество переменных (аргументов), участвующих в одной конъюнкции, соответствует количеству входов элемента И .

3. Логическое сложение ( дизъюнкция ). Функция логического сложения записывается в виде f3=X1 + X2, и читается так: "f3 есть Х1 или Х2, поскольку функция истинна, когда истинна одна или другая переменная (хотя бы одна)". Поэтому функцию дизъюнкции часто называют функцией ИЛИ . Символы логического сложения: +,V.

Рис. 4 — Условное графическое обозначение элемента ИЛИ

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

Пример булева выражения: f(X1,X2) = X1 +X1· X2 +( X1 + X2 )·X1.

Элементарные функции алгебры логики

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

Общее количество функций алгебры логики от m переменных R=2 k , где k=2 m .

Основные законы алгебры логики.

Основные законы АЛ позволяют проводить эквивалентные преобразования функций, записанных с помощью операций И , ИЛИ , НЕ , приводить их к удобному для дальнейшего использования виду и упрощать запись.

Булевой алгебре свойственен принцип двойственности, что наглядно иллюстрирован в табл. 5. Как следует из табл. 5, только закон двойного отрицания не подчиняется этому принципу.

Используя законы алгебры логики, можно упростить булевы выражения, в частности, правило склеивания позволяет упростить выражение типа

Действительно, используя законы 2, 5 и 11 можно записать исходное выражение в виде Х 2 (Х 1 + Х 1 ) =Х 2 . Так как логическая операция Х 1 + Х 1 = 1 (см. закон 5), а Х 2 ×1 = Х 2 (см. закон 2б), полученное выражение истинно.

Способы задания функций алгебры логики.

При сопоставлении функций АЛ с дискретными автоматами аргументы функций, сопоставляются с входами, а сами функции с выходами дискретного автомата.

Поскольку дискретный автомат имеет конечное число входов, то мы будем иметь дело с функцией конечного числа аргументов. Если автомат имеет m входов, то количество входных переменных тоже m и число возможных комбинаций наборов значений этих входных аргументов (переменных) К=2 m .

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

Табличный способ

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

Таблица истинности содержит 2 m строк, m столбцов (по количеству входов) и один столбец для записи значения функции.

Например: пусть требуется задать функцию трех переменных F1(Х1,Х2,Х3) (рис. 5), т.е. автомат на три входа и на один выход, следовательно, M=3, К=8.

Рис. 5 — Функциональное обозначение цифрового автомата трех переменных

Числовой способ

В этом случае функция задается в виде десятичных эквивалентов номеров наборов аргументов, при которых функция принимает единичное значение. Например, для рассмотренного выше примера функция F принимает единичные значения на наборах переменных со следующими номерами: 1, 2, 5, тогда числовой способ задания будет иметь вид

Координатный способ

При этом способе дискретный автомат задается с помощью карты его состояния, которая известна как карта Карно .

Карта Карно содержит 2 m клеток по числу наборов значений переменных. Каждая клетка определяется координатами строк и столбцов, соответствующими определенному набору переменных. Все входные переменные разбиваются на 2 группы так, что одна группа определяет координаты строк, а другая — координаты столбцов. В каждой клетке карты Карно проставляется соответствующее значение функции на заданном наборе. Пример задания функции трех переменных приведен на рис. 6. Числовое выражение этой функции выглядит так:

Рис. 6 — Карта Карно функции трех переменных

Пример построения карты Карно для функции 4-х переменных. Пусть функция задана в числовой форме и имеет вид:

Следовательно, К=16, m=4.

Сначала проводим разметку координат карты Карно без указания значений функции. Для удобства воспользуемся указанием «шапки» в виде прямых линий, “под” которыми переменные входят в значение координат без отрицания (рис.7). Таким образом, по столбцам и по строкам переменные входят без отрицания в пределах линии-шапки.

Рис. 7 — Карта Карно функции четырех переменных

Для наглядности координаты клеток карты Карно указаны в трех формах:

• в виде наборов переменных;
• в виде двоичного числа, соответствующего порядковому номеру набора переменных;
• в десятичном эквиваленте номеров наборов переменных.

На практике координаты внутри клеток не записывают (рис. 8), в клетках указываются единичные значения функции, соответствующие “координатным” наборам переменных. Нулевые значения функции в клетки можно не записывать, т.е. клетки, координаты которых определяются наборами переменных с нулевыми значениями функции, можно оставить пустыми.

Рис. 8 — Карта Карно функции четырех переменных с указанием внешних разметок

Следует отметить, что перестановка местами переменных Х1 и Х2, а так же переменных Х3 и Х4 допускается, допускается также перестановка местами переменных Х1Х2 и Х4Х3. При построении карты Карно, т.е. при задании логической функции, указывают лишь внешние элементы разметки координат (рис. 8).

Аналитический способ задания функции алгебры логики

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

Совершенная нормальная дизъюнктивная форма (СНДФ)

По таблице истинности можно составить логическое выражение, содержащее наборы переменных, в которые входят все переменные с отрицанием или без. Одна из его форм называется СНДФ.

В качестве примера получения СНДФ рассмотрим случай задания логической функции в виде таблицы истинности. Пусть задана функция трех переменных. Таблица истинности этой функции показана в табл. 7.

Из таблицы истинности видно, что функция принимает значение логической единицы только на трех наборах переменных, т.е. на 2, 4 и 5-м наборах. Для второй строки (второго набора переменных) можно записать: Х1=0, Х2=1, Х3=0, следовательно, функция f(0,1,0)=1. Принято (по умолчанию) считать, что если переменная в «нормальном» состоянии имеет значение логической единицы, а в инверсном — логического нуля, тогда функцию для второй строки можно представить в виде X 1 Х 2 X 3 = 1. Для четвертой строки — X 1 X 2 Х 3 = 1 и для пятой строки — Х 1 X 2 Х 3 = 1. Аналитическое выражение функции выглядит как

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

СНДФ любой функции записывается по таблице истинности согласно следующему правилу.

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

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

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

Совершенная нормальная конъюнктивная форма (СНКФ)

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

Свойства совершенства для СКНФ:

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

Алгоритм получения СКНФ по таблице истинности:

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 0:
2. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание.
3. Все полученные дизъюнкции связать в конъюнкцию.
4. Упрощаем формулу, применяем законы логики (если это необходимо).

Если (хотя бы одна) дизъюнкции, которые называются также макстермами (конституентами нуля), не содержат отдельные переменные, то такая форма записи функции называется нормальной конъюнктивной формой (НКФ).

Пример: Восстановить логическую функцию по ее таблице истинности (табл. 8).

Решение

СКНФ составляется на основе таблицы истинности по правилу: для каждого набора переменных, при котором функция равна 0, записывается сумма, в которой с отрицанием берутся переменные, имеющие значение 1.

F(X1,X2,X3)=(X1+ X2 +X3)•(X1+ X2 + X3 )•( X1 + X2 +X3)

Полная система логических функций. Понятие о базисе

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

Теория цифровых автоматов

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

Общие сведения о цифровых автоматах

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

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

1. Синхронные автоматы.
2. Асинхронные автоматы.

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

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

Теория цифровых автоматов

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

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

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

Это означает, что для реализации процесса управления, система управления цифрового автомата должна иметь:

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

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

Рисунок 1. Структурная организация цифрового автомата. Автор24 — интернет-биржа студенческих работ

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

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

Цифровые автоматы, выполняющие функции автоматических систем управления, можно разделить на следующие типы:

1. Цифровые автоматы, являющиеся системами автоматического управления (САУ).
2. Цифровые автоматы, являющиеся системами автоматического регулирования (САР).
3. Цифровые автоматы, являющиеся следящими системами (СС).

Необходимо подчеркнуть, что системы САР и СС по существу могут считаться подмножествами САУ.

Автоматическая система управления, способная обеспечить неизменным, то есть, постоянным, какое-либо значение (или группу значений) в управляемом объекте, называется системой автоматического регулирования (САР). Системы автоматического регулирования могут считаться наиболее применяемым типом автоматических систем управления.

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

Научная электронная библиотека

В общем случае детерминированная техническая система, реализуемая с помощью работающих в дискретном времени t цифровых блоков (устройств), а также сами эти блоки можно представить в виде так называемых цифровых автоматов. Такой автомат имеет внутреннюю память, входную и выходную логические схемы (рис. 1.1). Согласно литературе цифровые автоматы делятся на автоматы Мура и автоматы Мили (по фамилиям соответствующих американских ученых – Moore machine и Mili machine ). Аналоговые автоматы рассматриваться не будут (они в основном отжили).

Рис. 1.1. Структурная схема цифровых автоматов Мура и Мили

Будем полагать, что входная и выходная логические схемы автоматов реализуют соответственно функции f и g , а содержимое внутренней памяти и ее входная величина подвергаются некоторому преобразованию h . Тогда поведение автомата Мура можем описать следующей системой уравнений, в которой в общем случае величины S , X и Y являются векторными:

Для автомата Мили первое уравнение этой остаётся неизменным, а второе принимает следующий вид:

style=font-size:11.0pt;line-height:115%;font-family:"Calibri","sans-serif">

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

Отметим, что в автоматах Мили входной вектор style=font-size:14.0pt;font-family:"Calibri","sans-serif";position:relative; top:3.0pt> можно подавать на выходную логическую схему и после прохождения им входной логической схемы. В этом случае

5. Цифровые автоматы, их виды и классификация.

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

В общем случае, на вход цифр. устройства поступает некоторый набор 2ых переменных Х(х1, х2… хn), а с выхода устройства снимается набор или множество значений У(у1,у2… уn), причем цифр. устройства реализуют определенную связь (лог. функцию) между вх. и вых. переменными.

На передачу сигнала через устройство отводится конечн. промежуток времени – такт работы устройства.

Если за 1 такт в устройство передается 1 из разрядов 2ого числа (кода), устройство работает в посл. коде, если за 1 такт его работы передается все двоичное число одновременно, то устройство работает в парал. коде:

Применительно к ЭВМ в зависимости от способа обработки циф информации различают 2 класса дискретных автоматов: комбинационные и последовательные.

Комбинационные автоматы (комбинационные схемы) – устройства, в которых значения вых сигналов У(у1, у2… уm) в любой момент дискр. времени однозначно определяется совокупностью вх сигналов Х. Т.о. одним из достоинств комб. схем является их высокое быстродействие. Преобразование информации в комб. схемах однозначно определяется лог. функциями вида . Лог функции и соответствующие им комбинационные схемы разделяют на регулярные и нерегулярные структуры. Регулярные структуры предполагают построение схема таким образом, что кажд из ее выходов строится по аналогии с предыдущими. В нерегулируемых структурах такая аналогия отсутствует.

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

В последовательном автомате выходные сигналы в данный момент времени зависят не только от значения входного сигнала в данный момент, но и от значения входного сигнала в прошлом, т.е. внутреннее состояние устройства. Понятеие состояния последов. автомата предполагает наличие у него внутренней памяти, где должна хранится информация о предыдущих воздействиях. Функциональное соотношение:

Различают последовательные автоматы автоматы Мура(выходной сигнал определяется текущим состоянием автомата) и автоматы Мили (выход зависит как от состояния, так и от входного сигнала)

пример Автоматы Мура: триггеры, счетсчики, накапливающие сумматоры, регистры и др.

Шифраторы (кодеры, ш.) – преобразуют сигнал на одном из своих входов (унитарный код) в n-разрядный 2ный код на выходе, соответствующий 10чному номеру активного входа.

Число информационных входов ш. = числу символов преобразуемого кода и должно соответствовать условию , где n – число информационных выходов.

Кроме обычных шифраторов, существуют шифраторы с приоритетом, в таких ш. допускается подавать сигнал 1 одновременно на несколько входов, а ш. выдаст на выход код числа, соответствующего № старшего входа, т.е. если при работе ЭВМ решается задача определения приоритетного претендента на обслуживание и имеется одновременно несколько запросов, то обслужится запрос с наибольшим номером. Основное назначение ш. является преобразование № источника сигнала в 2чный код.

Дешифраторы (д.)

Д. представляет собой комбинационное устройство, позволяющее распознавать числа, представленные позиционно n-разрядным кодом.

Если на вход д. подать n-размерный 2ый код, то на выходе устройства появляется код «1 из N» в кодовой комбинации которого только одна позиция будет представлена единицей, а остальные – нулем. Такой код называется унитарным.

Т.к. макс. возможное количество чисел, закодированные N-разрядным 2чным кодом = количеству наборов из N аргументов // — неполный д.

В ЭВМ д. используют для расшифровки адресных ячеек ЗУ, а также в устройствах цифровой индикации.

Мультиплексоры MUX (MS) (м.) – устройства, подключающие единственный выход к одному из информационных входов, № которого задается 2чн. кодом, поступившим на управляющий (адресный) вход. МS принимает сигнал, поступивший на входы, т.е. решает задачу, обратную распределителю.

Демультиплексоры (DMS, DMX)

DMX – устройства, в котором сигналы с 1ого информационного входа поступают в желательной последовательности на требуемые выходы в зависимости от значения 2ого кода на адр. шинах.

, где n – число выходов, m – число адр. входов.