Особенности дискретных автоматов

Теория конечных автоматов характеризуется широким использованием в различных областях применения дискретной техники. Эта теория получила первоначальное развитие на базе

Особенности дискретных автоматов

Контрольная работа

Радиоэлектроника

Другие контрольные работы по предмету

Радиоэлектроника

Сдать работу со 100% гаранией
новые вычислительные алгоритмы. Построение многоуровневых схем памяти на основе многофункциональных автоматов, которые не только изменяют структуру запоминания состояний, но и определяют направление запоминаемой информации для образования связей с новыми схемами памяти, необходимых для создания нейронных сетей [1–2; 92; 96; 101].

2.3 Понятие о дискретном автомате

Дискретными автоматами Мили и Мура называют устройства преобразующие информацию в дискретные моменты времени, которые в математике отождествляются как точка на числовой оси (рис. 1.2, а) ti (i = 0, 1, 2, ..., n, ...), а в реальном устройстве как такт t (рис. 1.2, б).

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

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

Второе допущение состоит в том, что переход в следующее состояние оказывается возможным после переходного процесса в схемах памяти автомата, которые имеют разброс параметров, но для данного автомата составляет некоторый фиксированный промежуток времени, который обычно выбирается равным четырем задержкам τэ элемента. Такой интервал дискретности автомата обычно выбирается как такт t машинного такта Т (рис. 1.2. б.). Промежуток между тактами t в теории автоматов принято называть пустым словом е нулевой длины, т. к. под воздействием слова е автомат не способен переходить из одного состояния в другое, а только, выполняет функцию δe сохранения установленного состояния [64]. Такое допущение дает возможность рассматривать функционирование цифрового автомата Мили или Мура в дискретном автоматном времени ti (рис. 1.2, б). При построении такого дискретного автоматного времени различают два основных случая:

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

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

Теория асинхронных автоматов существенно отличается от теории синхронных автоматов тем, что в ней рассматриваются не только моменты фактически имевших место переходов, но также и такие переходы, которые в данный момент возможны, но не произошли переходы. К числу таких моментов причисляют моменты прихода входных сигналов х(t) импульсного типа (мгновенных) и изменения уровня напряжения сигналов потенциального типа, действующих во временном интервале такта t (рис. 1.2, б). При этом считают, что интервал дискретности автомата ограничивает минимально возможное расстояние между дополнительно вводимыми моментами автоматного времени. При таком допущении теория асинхронных автоматов в ряде случаев может быть сведена к синхронному случаю, поскольку фактически длины интервалов между последовательными моментами дискретного автоматного времени в идеализированной теории автоматов (без учета переходных процессов) не имеет никакого значения, так как на автомат в этот момент поступает пустое слово е нулевой длины. Имея в виду такое обстоятельство, в функционировании автоматов Мили и Мура используется абстрактное дискретное автоматное время, принимающее целые неотрицательные значения: t = 0, 1, 2, ..., n, ..., и строится теория, как теория последовательных синхронных автоматов, хотя в действительности она охватывает в значительной мере и теорию асинхронных автоматов.

Переходы из одного аi состояния автомата в другое ak вызываются входными сигналами x(t), возникающими вне автомата и передающимися в автомат по конечному числу входных каналов. В отношении х(t) входных сигналов цифровых автоматов принимаются два допущения: во-первых, для любого цифрового автомата число различных х(t) входных сигналов обязательно конечно, а, во-вторых, х(t) входные сигналы рассматриваются как причина перехода автомата из одного состояния в другое и относятся к моментам времени, определяемым соответствующими им переходами. Особо следует подчеркнуть, что реальный физический входной сигнал, вызывающий изменения состояния автомата в момент времени ti, может кончиться до наступления этого момента, однако, тем не менее, он относится именно к моменту времени ti, а не ti-1.

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

В многофункциональных автоматах Мараховского, которые названы по фамилии предложившего их автора, используется автоматная память [61––63], вводится и используется автоматное непрерывное время. В автоматном непрерывном времени кроме такта ti используется еще промежуток между тактами ti, интервал которого обозначим символом « ». Это объясняется тем, что в интервале используется сохраняющий входной сигнал е( ), который в автоматах Мили и Мура называется пустым словом нулевой длины и не учитывается при синтезе автоматов, а в многофункциональных автоматах может использоваться для осуществления укрупненных переходов в автоматной памяти автомата.

Рассмотрим автоматное непрерывное время с учетом синхронных сигналов τj и дадим ряд определений. Определение 1.1. Тактом назовем промежуток времени, на протяжении которого на автомат можно подавать произвольный синхронизирующий сигнал τi. Определение 1.2. Внутренним тактом назовем меньший открытый промежуток времени между появлениями синхронизирующих сигналов τi.

Определение 1.3. Внешним тактом назовем меньший открытый справа промежуток времени, который соответствует периоду синхронизированного сигнала τi.

Такты, что определены, можно выразить такой формулой:

(1.4)

Информационные входные сигналы х(t) подаются на входные каналы сложного автомата и синхронизируются сигналом τj. Эти входные сигналы воздействуют на автомат в автоматное непрерывное время такта .

Определение 1.4. Внутренним единичным тактом Δ0 автоматного непрерывного времени назовем меньший открытый промежуток времени между появлением двух произвольных и последовательных синхронизированных сигналов τр и τр + 1.

Определение 1.5. Внешним единичным тактом Т0 назовем меньший открытый справа промежуток времени, который соответствует периоду времени между появлением двух произвольных и последовательных синхронизирующих сигналов τр и τр + 1.

Внешний единичный такт Т0 в соответствии со временем равен сумме продолжительности такта и внутреннего единичного такту Δ0. Эта зависимость рассматривается таким равенством:

Т0= + Δ0.(1.5)

Продолжительность внешнего такта равна продолжительности внешнего такта Та автомата. За один внешний такт Та на автомат воздействуют все синхронизирующие сигналы τj по одному разу.

Определение 1.6. Внешним тактом Та автомата назовем меньший открытый справа промежуток времени, который соответствует периоду воздействия всех синхронизирующих сигналов τj (j = 1, 2 ,..., C) на входных каналах автомата.

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

Необходимо учитывать, что на входные каналы элементарных автоматов поступают сигналы определенной продолжительности τj.

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

Новое установленное состояние элементарного автомата может сохраняться после окончания такта при однозначном переходе или после внутреннего единичного такта Δ0 при реализации функций укрупненного или вероятностного перехода.

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

Похожие работы

<< < 1 2 3 4 5 >