Проектирование цифрового автомата, определяющего заданную двоичную последовательность равную: 010000

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ  СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ»

КУРСКИЙ ИНСТИТУТ СОЦИАЛЬНОГО  ОБРАЗОВАНИЯ

(ФИЛИАЛ) РГСУ

 

Инженерно-технический факультет

 

Кафедра информационных систем и информационного  права

 

КУРСОВОЙ ПРОЕКТ

 

КП.230201.65.02.2012

 

по дисциплине: «Организация ЭВМ и систем»

 

на тему: «Проектирование цифрового автомата, определяющего заданную двоичную последовательность равную: 010000 »

 

  Вариант № 16

 

Выполнил  студент(ка) АСУ-1-Д-2010-1 

специальности «Автоматизированные системы обработки

информации  и управления»      Логачев Е.В.

очной формы обучения

 

Руководитель:  к.т.н., доцент     Шевелев С.С.

 

Приняли члены комиссии

председатель : канд. техн. наук, доцент   Гранкин А.Н.

 

канд. техн. наук, доцент           Горбатенко С.А.

 

канд. техн. наук, доцент           Зайцев С.А.

 

Проект защищен  с оценкой

_______________

«__»_______20__г.

 

Курск 2012 г.

 

Оглавление

Введение 2

Теоретическая часть 4

Теория цифровых автоматов. Основные понятия 4

Методы структурного синтеза и языки описания цифровых автоматов 9

Элементарный  автомат. Триггерный элемент 12

Синтез логических схем с одним выходом 13

Алгоритм  функционирования цифрового автомата 16

Практическая часть 19

Граф-счема  цифрового автомата 20

Таблица переходов 21

Таблица выходов 22

Совмещенная таблица 23

Таблица цифрового  автомата 24

Принципиальная, электрическая схема цифрового  автомата 29

Заключение 30

Литература 31

 

Введение

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

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

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

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

Необходимо  рассмотреть такие вопросы как:

• основные понятия теории автоматов;
• входной алфавит и выходной алфавит;
• представление событий в автоматах.

Теоретическая часть

Теория  цифровых автоматов. Основные понятия

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

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

Существует  два способа введения автоматного  времени, по которым цифровые автоматы делят на два класса: синхронные и асинхронные.  В синхронных автоматах  моменты времени, в которых фиксируются  изменения состояний автомата, задаются специальным устройством — генератором  синхросигналов, выдающим импульсы через  равные промежутки времени (постоянный интервал дискретности). В асинхронных  автоматах моменты перехода автомата из одного состояния в другое заранее  не определены и зависят от каких-то событий.  В таких автоматах  интервал дискретности является переменным. Через понятие «абстрактный автомат» реализуется некоторое отображение  множества слов входного алфавита X во множество слов выходного алфавита Y.

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

Работу  абстрактного автомата следует рассматривать  применительно к конкретным интервалам времени, так как каждому интервалу  дискретности t будет соответствовать  свой выходной сигнал y(t). При этом предполагается, что выходной сигнал на одном из выходов автомата может появиться  только после соответствующего этому  же моменту времени входного сигнала  с одновременным переходом из состояния q(t-1) в состояние q(t).

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

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

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

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

Если  некоторый входной сигнал не меняет состояния автомата, то соответствующая  ветвь замыкается на кружке (узле), из которого она выходит.

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

В настоящее  время в классе синхронных автоматов  рассматривают, в основном, два типа автоматов: автомат Мили и автомат  Мура.

Закон функционирования автоматов Мили может быть задан  следующим образом:

a(t + 1) = f[a(t), x(t)];

y(t) =  [a(t), x(t)],

где t = 1, 2, .....

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

Граф автомата Мили

У автоматов  Мура выходные сигналы в момент времени t однозначно определяются состоянием автомата в этот же момент времени  и в явном виде не зависят от значения входных сигналов xi(t).

Функции переходов и выходов автомата Мура, заданного на множестве входных  сигналов X, множестве внутренних состояний A = {a0, a1, ,an} и множестве выходных сигналов Y, можно записать в виде:

 

a(t + 1) = f[a(t), x(t)],

y(t) =  [a(t)].

 

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

 

Автомат Мура

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

Совмещенная модель автомата (С-автомат). Абстрактный С-автомат — математическая модель дискретного устройства, для  которого заданы — множество состояний;

 

 — входной алфавит;

 — выходной алфавит типа 1;

 — выходной алфавит типа 2;

 — функция переходов, реализующая  отображение    в ;

 — функция выходов, реализующая отображение на  ;

 — функция выходов, реализующая  отображение  на  ;

 — начальное состояние  автомата.

Абстрактный С-автомат можно представить  в виде устройства с одним входом, на который поступают сигналы  из входного алфавита X, и двумя выходами,  на которых  появляются сигналы из выходных алфавитов Y  и U

    

 

Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов  λ1 и λ2, каждая из которых характерна для этих моделей в отдельности. Этот автомат можно описать следующей  системой уравнений:

                                                                

Выходной  сигнал и  u= λ2(qs) выделяется все время, пока автомат находится в состоянии qs. Выходной сигнал  yk=λ1(qs, xn)  выдается во время действия входного сигнала  xn  при нахождении автомата в состоянии  qs. От С-автомата легко перейти к автоматам Мили или Мура (с учетом возможных сдвигов во времени на один такт), так же как возможна трансформация автомата Мили в автомат Мура, и наоборот.

 Методы структурного синтеза и языки описания цифровых автоматов

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

Среди автоматных языков наиболее распространены таблицы  переходов и выходов, а также  графы.

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

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

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

 

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

1. Элементарные автоматы, например триггера, являются автоматами Мура и имеют два внутренних устойчивых состояния.

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

3. В общем  случае элементарные автоматы  могут иметь несколько физических  входов.

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

- хотя бы  один элементарный автомат с  двумя различными состояниями,  для которых соблюдаются условия  полноты системы переходов и  выходов;