Теоретические основы построения конечных автоматов

1 2 3 4 5 6 7

ЛИСТ ЗАДАНИЯ

Изначальные данные:

1. Задан конечный цифровой автомат аналитическим методом следующими параметрами:

1) Множество букв входного алфавита: A= {0, 1};

2) Множество состояний автомата: Q= {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇ };

3) Множество букв входного алфавита: V= {0,1};

4) Таблица переходов:

δ	q₀	q₁	q₂	q₃	q₄	q₅	q₆	q₇
0	q1	q0	q3	q6	q5	q7	q2	q4
1	q6	q1	q7	q4	q0	q2	q5	q3

5) Таблица выходов:

λ	q₀	q₁	q₂	q₃	q₄	q₅	q₆	q₇
0	0	1	0	1	0	1	0	1
1	0	1	1	0	1	0	0	1

6) Граф-схема автомата:

2. Построить заданный автомат в базисе { и-не }.

Дата выдачи задания: 22 февраля 2010 г.

Дата согласования: _______________

Руководители проекта:

Секирин А.И. ________

Поляков А.И. ________

Выполнил студент группы КИ-09д

Черновалов Д.И. ________

РЕФЕРАТ

стр. – 31, рис. – 14, табл. – 12

ЦИФРОВОЙ АВТОМАТ, ГРАФ-СХЕМА, КАРТЫ КАРНО, БАЗИС, ФУНКЦИОНАЛЬНАЯ СХЕМА, ELECTRONIC WORKBENCH, ЛОГИЧЕСКИЙ КОНВЕРТЕР, ЛОГИЧЕСКИЙ АНАЛИЗАТОР.

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

СОДЕРЖАНИЕ

Условные сокращения

Введение

1. Постановка задачи

2. Теоретические основы построения конечных автоматов

2.1 Цифровой автомат

2.2 Последовательность построения КЦА

2.3 Формы представления функций алгебры логики

2.3.1 Табличная форма представления

2.3.2 СДНФ

2.3.3 СКНФ

2.4 Карты Карно

2.5 Схемная реализация конечных автоматов

2.6 Применение ЦА

3. Разработка и построение функциональной схемы КЦА

3.1 Кодирование состояний автомата

3.2 Минимизация функции выходов автомата

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

3.4 Перевод функций в заданный базис

3.5 Теоретическая функциональная схема КЦА

4. Исследование работы КЦА в EWB

4.1 Основные сведенья о программе EWB

4.2 Интерфейс EWB

4.2.1 Логические компоненты

4.2.1.1 Логический элемент 2-И-НЕ

4.2.2 Логический анализатор

4.2.3 Логический конвертер

4.3 Результат работы функциональной схемы КЦА

4.3.1 Без применения устройства, осуществляющего задержку между переходами автомата

4.3.2 C применением устройства, осуществляющего задержку между переходами автомата

Заключение

Литература

Приложение А. Теоретическая функциональная схема КЦА

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

Приложение Б.2 Функциональная схема конечного автомата в EWB с применением устройства, осуществляющего задержку между переходами автомата

УСЛОВНЫЕ СОКРАЩЕНИЯ

СДНФ	Совершенная Дизъюнктивная Нормальная Форма
СКНФ	Совершенная Конъюнктивная Нормальная Форма
ЭВМ	Электронно-вычислительная Машина
КЦА	Конечный Цифровой Автомат
EWB	Electronics Workbench
ЦА	Цифровой Автомат
ГРАФ	Графсхема

ВВЕДЕНИЕ

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

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

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

Вершиной цифровой техники является микропроцессор. Мало кто знает, что в современных японских автомобилях автоматической подкачкой колёс управляет микропроцессор.

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

ПОСТАНОВКА ЗАДАЧИ

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

¾ составить таблицы истинности для выходов и переходов автомата;

¾ минимизировать функции выходов и переходов по СДНФ;

¾ перевести полученные минимальные функции в заданный базис;

¾ построить теоретическую схему каскадным принципом с использованием элементов 2-И-НЕ и с устройством, осуществляющим задержку между переходами автомата;

¾ построить теоретическую схему в программе EWB и проверить правильность её работы по временным диаграммам логического анализатора.

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

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ

Цифровой автомат

Цифровым или конечным автоматом называется система которая может быть полностью задана следующими параметрами: S=<A,Q,V,