Разработка конечного цифрового аппарата

СОДЕРЖАНИЕ
Условные сокращения
Введение
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
ЦА
Цифровой Автомат
ГРАФ
Графсхема
ВВЕДЕНИЕ
В наступившем двадцать первом веке человечество не мыслит себя без цифровых технологий. Цифровое телевидение, цифровая фото и видео съёмка, цифровая сотовая и стационарная связь и т. д.; человек пользуется этими благами цивилизации, не задумываясь о том, как и что там работает. А ведь там происходят очень сложные действия над информацией, представленной в двоичной системе счисления.
Устройства, которые обеспечивают цифровую обработку информации, называются цифровыми. Эти устройства выполнены на цифровых интегральных микросхемах, что позволяет значительно уменьшить габариты устройств, массу, потребляемую мощность, стоимость и намного улучшить надёжность. Применение технологий больших и сверхбольших интегральных микросхем позволило перенести компьютеры из лабораторий и специальных учреждений в каждый дом. Помимо улучшения качества и надёжности аппаратуры интегральные микросхемы также влияют на производительность и качество труда человека, посредством того, что работа становится автоматизированной и, следовательно, увеличивается в разы вычислительная способность и уменьшается риск ошибки.
С появлением цифровых устройств в технике связи стало возможным предоставление огромного числа услуг, улучшилось качество связи и увеличился объём передаваемой информации.
Вершиной цифровой техники является микропроцессор. Мало кто знает, что в современных японских автомобилях автоматической подкачкой колёс управляет микропроцессор.
Микропроцессорные устройства широко используются в аппаратуре, которая обеспечивает обмен, обработку и распределение информации.
1. ПОСТАНОВКА ЗАДАЧИ
По имеющимся данным нужно разработать и построить функциональную схему КЦА и проверить правильность её работы. Для этого необходимо:
¾ составить таблицы истинности для выходов и переходов автомата;
¾ минимизировать функции выходов и переходов по СДНФ;
¾ перевести полученные минимальные функции в заданный базис;
¾ построить теоретическую схему каскадным принципом с использованием элементов 2-И-НЕ и с устройством, осуществляющим задержку между переходами автомата;
¾ построить теоретическую схему в программе EWB и проверить правильность её работы по временным диаграммам логического анализатора.
Построенную теоретическую схему, а так же схему из EWB необходимо предоставить в виде приложений, входящих в пояснительную записку. Вместе с пояснительной запиской нужно предоставить сменный носитель, на котором будет находиться файл с функциональной схемой КЦА, в формате EWB, и пояснительная записка.

2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ
2.1 Цифровой автомат
Цифровым или конечным автоматом называется система которая может быть полностью задана следующими параметрами: S=<A,Q,V,
– множество букв входного алфавита;
– множество состояний автомата;
– множество букв выходного алфавита;
– функция переходов;
– функция выходов.
Автомат также может быть полностью задан графически (графсхемой).
Графсхема – топологический объект вершины которого соответствуют состоянию автомата, а дуги или ребра соответствуют переходам автомата
Рис. 2.1 – Пример графсхемы №1
Различают направленные или ориентировочные и не ориентировочные графы
· не ориентировочные графы - содержат информацию о наличии переходов и не отображают их направление
· ориентировочные графы – учитывают направление переходов
Над дугами графа указывается информация о входном воздействии и состоянии выхода

Рис. 2.2 – Пример графсхемы №2
2.2 Последовательность построения конечных автоматов
Для построения КЦА необходимо:
- построить граф-схему автомата или таблицы выходов и переходов ЦА;
- Закодировать каждое состояние автомата;
- Построить таблицу истинности, содержащую вход, состояние и выход автомата. Минимизировать функцию выходов автомата;
- Построить таблицу истинности, содержащую вход, состояние и переходы автомата. Минимизировать функцию переходов автомата;
- Перевести полученные минимизированные функции в нужный базис.
2.3 Формы представления функций алгебры логики
2.3.1 Табличная форма представления
Если мы имеем k переменных, то из них можно составить 2k комбинаций, а так как для каждой комбинации может задана своя функция, то число возможных функций .

Таблица 2.1 Пример таблицы истинности для 3 переменных
Каждая комбинация таблицы истинности – набор (конституанта).
2.3.2 СДНФ
СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет трём условиям:
• в ней нет одинаковых элементарных конъюнкций
• в каждой конъюнкции нет одинаковых пропозициональных букв
• каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причем в одинаковом порядке.
В функцию выписываются все конституанты, в которых функция принимает значение 1. Если переменная входит в конституанту как 0, то записывается ёё отрицание, если как 1, то без отрицания. в наборе соединяются операцией конъюнкция (* или &), между наборами ставится операция дизъюнкция (+ или v).
Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности
Таблица 2.2
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
0
0
0
0
0
0
1
1
В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.Первый столбец содержит 1 в указанном поле. Отмечаются значения всех четырёх переменных, это:
= 0 = 0 = 0 = 0
Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: Переменные второго члена:
= 0 = 0 = 0 = 1
в этом случае будет представлен без инверсии: Таким образом анализируются все ячейки . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).Совершенная ДНФ этой функции:
2.3.3 СКНФ
СКНФ (Совершенная Конъюнктивная Нормальная Форма) — это такая КНФ, которая удовлетворяет трём условиям:
· в ней нет одинаковых элементарных дизъюнкций
· в каждой дизъюнкции нет одинаковых пропозициональных букв
· каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв
В функцию выписываются все конституанты, на которых функция принимает значение 0. Если переменная входит в конституанту как 1, то записывается ёё отрицание, если как 0, то без отрицания. В наборе xi соединяются операцией дизъюнкция (+ или v), а между наборами ставится операция конъюнкция (* или &).
Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности.
Таблица 2.3
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
0
0
0
0
0
0
1
1
В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля. Четвертый столбец содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:
= 0
= 0
= 1
= 1

В дизъюнкцию записывается переменная без инверсии если она в наборе равна 0 и с инверсией если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так: Остальные члены СКНФ составляются по аналогии.
2.4 Карты Карно
Карта Карно́ — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции.
Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно - это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор(бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.
Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):
· объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2n (n целое число = 0…) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
· область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
· не смежные области расположенные симметрично оси(ей) могут объединяться в одну;
· область должна быть как можно больше, а кол-во областей как можно меньше;
· области могут пересекаться;
· возможно несколько вариантов накрытия.
Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией. Например(для Карт на 2-ве переменные).

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию