Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Синтез цифрового автомата, определяющего заданную последовательность - файл 1.docx


Синтез цифрового автомата, определяющего заданную последовательность
скачать (135.6 kb.)

Доступные файлы (1):

1.docx136kb.08.12.2011 22:02скачать

содержание
Загрузка...

1.docx

  1   2   3
Реклама MarketGid:
Загрузка...


Министерство образования и науки РФ

Российский Государственный Социальный Университет

Курский Институт Социального Образования (филиал)

Российского Государственного Социального Университета

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

Специальность: 23102 « Автоматизированные системы обработки информации и управления»

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

Курсовая работа

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

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



Выполнил: студентка 4 курса заочного отделения

Рыжкова Т.В.

Проверил:

Шевелёв С.С.




Курск-2007



Содержание.

  1. Введение……………………………………………………..3.

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

  3. Методы структурного синтеза. Языки описания ЦА….9-12

  4. Элементарный автомат. Триггерный элемент…………13-14

  5. Синтез логических схем с одним выходом…………….15-17

  6. Синтез ЦАс заданной последовательностью…………..18-28

  7. Заключение…………………………………………………..29

  8. Библиографический список. ………………………………30



Введение.

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

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

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



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

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

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

Существует два способа введения автоматного времени, по которым цифровые автоматы делят на два класса: синхронные и асинхронные. В синхронных автоматах моменты времени, в которых фиксируются изменения состояний автомата, задаются специальным устройством — генератором синхросигналов, выдающим импульсы через равные промежутки времени (постоянный интервал дискретности). В асинхронных автоматах моменты перехода автомата из одного состояния в другое заранее не определены и зависят от каких-то событий. В таких автоматах интервал дискретности является переменным. Через понятие «абстрактный автомат» реализуется некоторое отображение множества слов входного алфавита 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, каждая из которых характерна для этих моделей в отдельности. Этот автомат можно описать следующей системой уравнений:

( 5 )

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

В самом общем виде последовательность структурного синтеза последовательностного цифрового автомата можно представить следующим образом.

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

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



Задачи комбинационного синтеза последовательностных цифровых автоматов полностью совпадают с задачами синтеза комбинационных логических схем.

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

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

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

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



^ ЭЛЕМЕНТАРНЫЙ АВТОМАТ. ТРИГГЕРНЫЙ ЭЛЕМЕНТ

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

Триггер имеет два выходных сигнала Q и Q. Сигнал Q считается истинным или прямым, а сигнал Q - дополнительным или инверсным. Этим сигналам соответствует один из двух уровней напряжения: L или H, и они дополняют друг друга. Выходные сигналы триггера постоянны до тех пор, пока они не будут изменены под воздействием входных сигналов, т.е. триггер имеет два устойчивых состояния (режима): Q = H и Q = L или Q = L и Q = H. Первое из них когда Q = H называется состоянием установки, а второе – состоянием сброса. Предположим, что для триггера используется положительная логика. Тогда состояниям установки и сброса ставятся в соответствие логические состояния «1» и «0».

Существуют различного типа триггерные схемы, в частности, типа: D, T, RS, JK. Для каждого из них имеется однозначное соответствие между входными сигналами и соответствующими переходами состояний триггера.

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



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



^ СИНТЕЗ ЛОГИЧЕСКИХ СХЕМ С ОДНИМ ВЫХОДОМ

Перед тем как перейти к примерам синтеза композиционных логических схем рассмотрим способы использования универсальности вентилей И-НЕ и ИЛИ-НЕ.

Свойство универсальности вентиля ИЛИ-НЕ:

^ Рис. 4

Свойство универсальности вентиля И-НЕ:

Рис. 5

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

Рассмотрим некоторые простые примеры перехода от логических уравнений к логическим цепям, т.е. примеры синтеза простых логических 

цепей. В частности, рассмотрим переход от представления функции в НДФ (ДНФ) к ее реализации на элементах И-НЕ и ИЛИ-НЕ.

Пусть задана функция 4-х переменных в НДФ:

F =CD +ABD + ABD +ABC + ACD.

Минимальная НДФ имеет вид: F = ABD + ABD + C.

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

Схема, соответствующая данному уравнению, приведена ниже.

Рис. 6

В приведенной схеме для элементов первой и второй ступени применены различные, но эквивалентные условные обозначения. При реализации НДФ функции посредством элементов И-НЕ такой прием позволяет вести проектирование схем, пользуясь операциями И, ИЛИ и НЕ.

По рассмотренным ранее правилам из вышеприведенной карты Карно, может быть найдена минимальная НКФ заданной функции:

F = (C +D)(A +B +C)(A + B +C).

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

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

Рис. 7

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



Синтез цифрового автомата с заданной последовательностью.

Моя последовательность : (21)10 =(10101)2

Y1 - выходной цифровой сигнал, определяющий признак не нашей последовательности.

Y2 - выходной цифровой сигнал, определяющий признак нашей последовательности.

{S0, S1, S2, S3, S4, S5,} – внутренние состояния цифрового автомата.

S0 - вершина графа

X – входная переменная

0

X = {

1

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

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

Выполнение состоит из 4 этапов:

  1. Построение графа.

  2. Кодировка внутренних состояний.




  1. Составление таблиц (переходов, выходов, совмещённой, таблицы ЦА)

  2. Построение структурных, принципиальных, структурно-принципиальных и принципиально- электрических схем .

^ 1 Этап. Построение графа.
0/Y1





0/Y1 1/Y1

1/Y1

1/Y2 1/Y1 0/Y1

0/Y1

0/Y1

1/Y1



2 Этап. Кодировка внутренних состояний.


S0 = 000

S1 = 001

S2 = 010

S3 = 011

S4 = 100
S5 = 101

^ 3 Этап. Составление таблиц.
Таблица переходов.



^ Состояние цифрового автомата

Вход. сигналы

0

1

S0

S0

S1

S1

S2

S1

S2

S0

S3

S3

S4

S1

S4

S0

S5

S5

S0

S1





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

^ Состояние цифрового автомата

Вход. сигналы

0

1

S0

Y1

Y1

S1

Y1

Y1

S2

Y1

Y1

S3

Y1

Y1

S4

Y1

Y2

S5

Y1

Y1





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

Состо-

яние

S0

S1

S2

S3

S4

S5

S0

0

Y1

__

__

0

Y1

__

__

0

Y1

0

Y1

S1

1

Y1

1

Y1

__

__

1

Y1

__

__

1

Y1

S2







__

__

0

Y1

__

__

__

__

__

__

__

__

S3

__

__

__

_

1

Y1

__

__

__

__

__

__

S4

__

__

__

__

__

__

0

Y1

__

__

__

__

S5

__

__

__

__

__

__

__

__

1

Y2

__

__
^ Таблица цифрового автомата.



X

Q1 Q2 Q3

Q1’ Q2’ Q3’

Y1

Y2

0

1

0 0 0

0 0 0

0 0 0

0 0 1

1

1

0

0

0

1

0 0 1

0 0 1

0 1 0

0 0 1

1

1

0

0

0

1

0 1 0

0 1 0

0 0 0

0 1 1

1

1

0

0

0

1

0 1 1

0 1 1

1 0 0

0 0 1

1

1

0

0

0

1

1 0 0

1 0 0

0 0 0

1 0 1

1

0

0

1

0

1

1 0 1

1 0 1

0 0 0

0 0 1

1

1

0
  1   2   3



Скачать файл (135.6 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации