Ім'я файлу: пояснительная_записка.doc
Розширення: doc
Розмір: 1138кб.
Дата: 13.02.2022
скачати
Пов'язані файли:
Арх_комп_КСД12_Гайдук_КР.pdf

ВВЕДЕНИЕ

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

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

 

где   – входной алфавит,   – множество состояний автомата,   - выходной алфавит,   – функция переходов,   – функция выходов.

По количеству состояний автоматы различают конечные (множество состояний конечное), и бесконечные (множество состояний бесконечно).

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

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

В данной работе рассмотрено построение автомата Мили, имеющего 5 рабочих состояний, и заданного таблицами переходов и выходов. Реализация автомата выполнена в логическом базисе И-НЕ.


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

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

  1. Составить таблицы истинности для функций выходов и переходов автомата;

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

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

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

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


Цифровой автомат описывается граф-схемой, представленной на рисунке (рис.) 1.1:



Рисунок 1.1 – Граф-схема заданного цифрового автомата

2. ПОСТРОЕНИЕ ЦИФРОВОГО АВТОМАТА

2.1 МИНИМИЗАЦИЯ АВТОМАТА

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

Два состояния и называются эквивалентными, если выполняется равенство:

, (2.1)

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

Множество всех эквивалентных состояний автомата называют классом эквивалентности, и обычно обозначают буквой K. При этом необходимым и достаточным условием эквивалентности состояний является выполнение следующих двух требований (условий эквивалентности):

(2.2)

где - функция выходов, k – класс эквивалентности.

Отметим, что автоматы S и T называются эквивалентными, если любому состоянию автомата S найдется эквивалентное состояние автомата T, и наоборот. Т.о., результатом минимизации исходного автомата S является эквивалентный ему автомат T, имеющий меньшее количество внутренних состояний, чем автомат S.

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

Проверка выполнения условий эквивалентности состояний автомата

Используя первое свойство эквивалентности (2.2) состояний автомата, выполним разбиение множества его состояний на классы условно эквивалентных состояний (табл. 2.1):

Таблица 2.1 – Нахождение классов условно эквивалентных состояний

λ



ðžð²ð°ð» 6

ðžð²ð°ð» 6

ðžð²ð°ð» 6

ðžð²ð°ð» 6

0

1

0

1

0

1

1

0

0ðŸð¾ð»ð¸ð»ð¸ð½ð¸ñ 2

1ðŸð¾ð»ð¸ð»ð¸ð½ð¸ñ 2

0

1


Как видим, автомат имеет три класса условно эквивалентных состояний – это состояния, для которых значение функции выходов принимает одно и то же значение:

,

,

.

Построим новую таблицу переходов, с учетом полученных классов условно эквивалентных состояний (табл. 2.2):

Таблица 2.2 – Таблица переходов, построенная с учетом существующих классов условно эквивалентных состояний

δ











0











1












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


2.2. КОДИРОВАНИЕ СОСТОЯНИЙ

Для реализации функций переходов и выходов автомата в заданном элементном базисе, необходимо выполнить три предварительных этапа:

  1. кодирование состояний автомата;

  2. построение таблиц истинности для функций переходов и выходов;

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

Каждое состояние автомата кодируется двоичным числом, количество разрядов которого определяется следующей формулой [2]:

, (2.3)

где n – количество разрядов, необходимых для кодирования одного состояния, Q – общее количество состояний. Обозначение было впервые введено Кеннетом Айверсоном в 1962 г, и означает т.н. "потолок" – результат округления до целой части в большую сторону.

Т.к. заданный автомат имеет 5 состояний, имеем:

n = 3.

Количество двоичных наборов, образуемых n разрядами, равно , поэтому в нашем случае количество двоичных наборов равно . Но, так как автомат имеет лишь 5 состояний, 3 набора из 8-ми использоваться не будут (табл. 2.3).

Таблица 2.3 – Кодирование состояний

Состояние

Двоичный набор



000



001



010



011



100


2.3 МИНИМИЗАЦИЯ ФУНКЦИИ ВЫХОДОВ АВТОМАТА

На основании заданной таблицы выходов автомата, выполним построение таблицы истинности его функции выходов (табл. 2.4):

Таблица 2.4 – Таблица истинности функции выходов

a







V

0

0

0

0

1

0

0

0

1

0

0

0

1

0

1

0

0

1

1

0

0

1

0

0

1

0

1

0

1

*

0

1

1

0

*

0

1

1

1

*

1

0

0

0

0

1

0

0

1

0

1

0

1

0

1

1

0

1

1

0

1

1

0

0

1

1

1

0

1

*

1

1

1

0

*

1

1

1

1

*


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

Для минимизации функции выходов воспользуемся картой Карно на 4 переменные для совершенной дизъюнктивной нормальной формы (СДНФ):





0ðŸð¾ð»ð¸ð»ð¸ð½ð¸ñ 3 ðžð²ð°ð» 16 0

01

11

1ðžð²ð°ð» 15 ðžð²ð°ð» 16 0

00

1







1

0ðžð²ð°ð» 10 1

1

*

*

*

11

1

*

*

*

10










1

Рисунок 2.1 – Минимизация функции выходов

Результат минимизации:

(2.4)

2.4 МИНИМИЗАЦИЯ ФУНКЦИИ ПЕРЕХОДОВ

На основании заданной таблицы переходов автомата, выполним построение таблицы истинности его функции переходов (табл. 2.5):

Таблица 2.5 – Таблица истинности функции переходов

a













0

0

0

0

0

1

1

0

0

0

1

0

1

1

0

0

1

0

0

0

1

0

0

1

1

0

0

1

0

1

0

0

1

0

0

0

1

0

1

*

*

*

0

1

1

0

*

*

*

0

1

1

1

*

*

*

1

0

0

0

0

1

0

1

0

0

1

0

0

0

1

0

1

0

1

0

0

1

0

1

1

0

1

0

1

1

0

0

0

0

0

1

1

0

1

*

*

*

1

1

1

0

*

*

*

1

1

1

1

*

*

*

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

Минимизация функции с использованием карты Карно для СДНФ показана на рис. 2.2:





00

01

11

10

00

ðžð²ð°ð» 16











01

1

*

*

*ðžð²ð°ð» 16

11




*

*

*

10










1

Рисунок 2.2 – Минимизация функции
Результат минимизации:

(2.5)

Минимизация функции с использованием карты Карно для СДНФ показана на рис. 2.3:





0ðžð²ð°ð» 16 ðŸð¾ð»ð¸ð»ð¸ð½ð¸ñ 5 0

01

11

10

00

1

1







01




*

*ðžð²ð°ð» 16

*

11

ðŸð¾ð»ð¸ð»ð¸ð½ð¸ñ 5


*

*

*

10

1




1




Рисунок 2.3 – Минимизация функции

Результат минимизации:

(2.6)
Минимизация функции с использованием карты Карно для СДНФ показана на рис. 2.4:





0ðžð²ð°ð» 16 0

01

11

10

00

1

1

1

1

01




*

*

*

11




*

*

*

10













Рисунок 2.4 – Минимизация функции

Результат минимизации:

(2.7)

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

Для приведения полученных функций к заданному базису, воспользуемся законом де Моргана, согласно которому отрицание дизъюнкции равно конъюнкции отрицаний, и наоборот [2]:

, (2.8)

. (2.9)

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

Приведение к базису И-НЕ функции выходов:

(2.10)

Приведение к базису И-НЕ функций , и соответственно, реализующих в ходе совместной работы функцию переходов автомата:

(2.11)

(2.12)

(2.13)

2.6 ФУНКЦИОНАЛЬНАЯ СХЕМА

На основе приведенных к базису И-НЕ функций переходов и выходов, выполняем построение функциональной схемы автомата в программе Electronics Workbench [3].



Рисунок 2.5 - Функциональная схема заданного цифрового автомата
Правильность работы построенной функциональной схемы можно проверить с помощью временных диаграмм логического анализатора:



Рисунок 2.6 – Временные диаграммы для функциональной схемы

Сигналы по порядку сверху вниз:

1 – сигнал a;

2 – сигнал ;

3 – сигнал ;

4 – сигнал ;

5 – сигнал ;

6 – сигнал ;

7 – сигнал ;

8 – сигнал V.
Полученные временные диаграммы совпадают с таблицами истинности для функций переходов и выходов, что свидетельствует о корректности работы функциональной схемы.

2.7 ФУНКЦИОНАЛЬНАЯ СХЕМА С ТРИГГЕРАМИ

Автоматы относятся к устройствам последовательностного типа – это означает, что значение на их выходе в момент времени t зависит не только от значения, поступившего на вход в этот момент времени, но и от предыдущих значений на выходе – в момент времени t-1 (в отличие от устройств комбинационного типа, в которых значение на выходе зависит только от поданной на вход в текущий момент времени комбинации) [1].

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

D-триггер выполняет хранение (задержку) предыдущего значения до момента поступления на его управляющий вход (clock) активного сигнала.

Схема синтезированного автомата представлена на рис. 2.7.


Рисунок 2.7 – Функциональная схема автомата с триггерами


Правильность работы построенной схемы автомата можно проверить с помощью временных диаграмм логического анализатора (рис. 2.8):



Рисунок 2.8 – Временные диаграммы для схемы с триггерами

Сигналы по порядку сверху вниз:

1 – входной сигнал a;

2 – сигнал ;

3 – сигнал ;

4 – сигнал ;

5 – выходной сигнал V.
2.7 АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ

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

Таблица 2.6 – Таблица входов, выходов и переходов синтезированного автомата

A

δ







V

0



0

1

1

1

0



0

0

1

0

1



0

0

0

0

1



0

1

0

0

0



0

0

1

1

0



0

1

1

0

1



0

1

0

0

1



1

0

0

1

0



1

0

0

1

0



1

0

0

1

1



0

0

0

1

1



0

1

0

0

0



0

0

1

1

0



0

1

1

0

1



0

1

0

0

1



1

0

0

1


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

ЗАКЛЮЧЕНИЕ

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

СПИСОК ЛИТЕРАТУРЫ

  1. Н.Г. Сахаров, В.Н. Рогов "Синтез цифровых автоматов", Ульяновск, 2003 г.

  2. В.А. Горбатов, "Фундаментальные основы дискретной математики", Москва, 2000 г.

  3. Р.Р. Сулейманов "Изучение логических основ компьютера в виртуальной лаборатории Electronics Workbench", Уфа, 2007.





скачати

© Усі права захищені
написати до нас