Дискретное устройство

Целью и задачей дискретного устройства является выяснение набора правил, которые будут описывать элементарные действия в определенной последовательности над исходными данными любой задачи, требующей решения.В дискретном устройстве определение последовательности из нулей (0) и единиц (1). По иному дискретное устройство называется одноактным автоматом.[1]

Выходные переменные в дискретном устройстве зависят от возможных комбинаций входных величин. Незамедлительное изменение выходных величин при изменении входных обуславливает определение устройства одноактным. Несмотря на то, что запаздывание присуще любому техническому устройству, в дискретном одноактном оно очень мало или вовсе не влияет на технический процесс. Процесс обмена информацией происходит в несколько этапов. Информация передается сигналами, которые шифруются, кодируются и запоминаются. Сигнал является функцией времени, даже если сообщение к таковой не относится. Дискретными являются сигналы, функция которых принимает только определенные дискретные значения (0 и 1).[1] Дискретное устройство имеет конечное число входов, следовательно его состояние можно описать конечным числом комбинаций. Количество возможных комбинаций значений входных величин будет равно 2ⁿ при n значениях входов.

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

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

Комбинационный автомат не имеет памяти, он не хранит информации о своей прошлой работе.

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

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

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

Асинхронные автоматы характеризуются переходами из одного в другое состояние в произвольные и не определенные моменты времени. Дискретные моменты в таких автоматах определяется длительностью тактов, т.е. интервалом времени, в течение которого состояние автомата не меняется.

В классе синхронных автоматов, в зависимости от вида функции выхода различают следующие типы автоматов: автомат Мили и автомат Мура. Если выходной сигнал зависит от внутреннего состояния устройства и не зависит от входного сигнала, то тип такого дискретного устройства называется автоматом Мура. Если выходной сигнал одновременно в некотором такте дискретного времени зависит и от входного сигнала и от состояния автомата, он относится к автоматам Мили.

В дискретных устройствах переменные не могут изменяться непрерывно, их изменения происходят в дискретные моменты времени, т.е. тактовые моменты.

Классифицируют дискретные устройства по характеру входных и выходных сигналов на:

• Потенциальные.
• Импульсные.
• Смешанные.

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

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

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

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

Синтез комбинационного дискретного устройства состоит в построении принципиальной схемы по заданному словесному описанию алгоритма работы. Синтез проводят в несколько этапов. Сначала вводят входные переменные и выходные функции. Затем с использованием таблицы истинности задают ФАЛ, отображающие соотношение между состояниями входов и выходов в каждый данный момент времени. В дальнейшем функции алгебры логики представляют в базисе И, ИЛИ, НЕ и находят их минимальные формы. На заключительных этапах синтеза выбирают элементный базис и строят принципиальную схему дискретного устройства. Комбинационное устройство на элементах И-НЕ строят в следующей последовательности: функцию алгебры логики, отражающую соотношение между состояниями входов и выходов, минимизируют с получением МДНФ, затем полученное логическое выражение записывают через операцию И-НЕ.

Абстрактная теория автоматов рассматривает дискретное устройство как "черный ящик", т. е. не интересуется его внутренней структурой и тем, как построена реальная схема. Методы этой теории определяют поведение дискретного устройства в терминах входных и выходных последовательностей сигналов. Это позволяет найти самые общие закономерности функционирования дискретного устройства. Введем несколько новых понятий на примере автомата Мура, имеющего один вход и один выход. Работа автомата определяется следующим алгоритмом: лампа горит после нечетного числа нажатий кнопки и не горит после четного числа нажатий. Набор входных переменных будем называть входной буквой. В данном примере существуют два набора входных переменных х = 0 и х = 1, которые обозначим соответственно буквами а и b. Множество входных букв назовем входным алфавитом А = (а. Ь). Аналогично наборы выходных переменных будем называть выходными б у к в а м и, а их множество — выходным алфавитом. В автомате Мура каждому внутреннему состоянию соответствует выходная буква, равная 0 (лампа не горит), или выходная буква, равная 1 (лампа горит). Внутренние состояния автомата, которым соответствует включенное состояние, следует называть отмеченными.

Связь между регулярными событиями и конечными автоматами устанавливают две основные теоремы абстрактной теории автоматов. Они доказаны С.К. Клини (США) и В.М. Глушковым (СССР) и здесь даются без доказательства.

Теорема 1. Любой конечный автомат представляет регулярное событие.

Теорема 2. Любое регулярное событие может быть представлено в конечном автомате.

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

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

• Л.М. Гольденберг, Ю.Т. Бутыльский, Н.М. Поляк. Цифровые устройства на интегральных схемах в технике связи. -М.: Связь, 1979