48125 (Построение кодопреобразователя)

2016-07-30СтудИзба

Описание файла

Документ из архива "Построение кодопреобразователя", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "48125"

Текст из документа "48125"

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

Южно-Уральский Государственный Университет

Кафедра Автоматики и Управления

Пояснительная записка к курсовой работе

по курсу: «Цифровые автоматы»

«Построение кодопреобразователя»

Руководитель Радкевич И. А.

« » 2007г.

Автор работы

студентка группы ЗФ-228-с

Ватутина /Лазуко/ А. Л.

« » 2007г.

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

_________________________

« » 2007г.

Челябинск 2007 год

Содержание

Задание 2

Введение 2

Понятие о дискретном (цифровом) автомате. 4

Основные понятия алгебры логики. 5

Понятия теории графов 10

Граф-дерево автомата Мура. 12

Граф-дерево автомата Мили. 13

Таблица переходов по автомату Мили 14

Таблица выходов по автомату Мили 14

Минимизация цифрового автомата Мили. 15

Таблица переходов с распределением неопределённостей. 15

Исключение недостижимых состояний. 15

Определение класса совместимости. 16

Классы единичной совместимости 17

Классы двоичной совместимости 18

Классы троичной совместимости 18

Классы четверичной совместимости 19

Классы пятеричной совместимости 20

Таблица состояний и выходов нормализованного автомата 21

Структурный синтез цифрового автомата 22

Выбор триггера 23

Представление функции возбуждения 25

Таблица состояний и выходов нормализованного автомата 27

Минимизирующие карты 30

Минимизация функций по методу Квайна 31

Минимизация функций по методу Мак-Класки 32

Заключение 43

Литература 44

Задание

Построить устройство для преобразования последовательного двоично-десятичного кода X = (хЗ, х2, х1, х0), который подаётся на вход устройства z = (z3, z2, z1, z0). Десятичный эквивалент X двоично-десятичного кода может быть вычислен: Х=Ë xi pi , где xi = 0, 1 - цифра двоично-десятичного кода, a pi - вес i-ro разряда.

Вариант задания представлен в таблице:

Номер варианта

X

Р3Р2Р1P0

z

Р3Р2Р1P0

24

4311

5211

Цель

Исследование влияния алгоритмов синтеза цифровых автоматов на сложность структуры самого цифрового автомата.

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

Введение

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

На первом уровне реализации работы была составлена таблица соответствий входного и выходного сигналов для десяти заданных значений и произведены преобразования для соблюдения условия автоматности.

На следующем уровне работы было произведено построение граф-деревьев абстрактных автоматов Мура и Мили. Затем по графу составлены таблицы переходов и выходов для автомата Мили.

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

На четвёртом уровне работы был произведён структурный синтез цифрового автомата с кодированием двоичным кодом входной, выходной функций автомата, а также функции состояний. Определена таблица состояний выбранного для реализации кодопреобразователя D-триггера.

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

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

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

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

КСВХ - входная комбинационная схема; П - память; КсВЬ1Х - выходная комбинационная схема; Х- входной цифровой код; В - код возбуждения памяти; А - код состояния памяти; Y - выходной код.

Рис.1. Каноническая структурная схема цифрового автомата

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

Понятие о дискретном (цифровом) автомате.

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

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

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

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

Цифровой автомата (первого или второго рода) называется правильным, если выходной сигнал y(t) определяется одним лишь его состоянием (a(t-1) или a(t)) и не зависит явно от входного сигнала x(t). Автоматы первого рода обычно также называют автоматами Мили, по имени американского ученого, который впервые начал их систематическое изучение. Особый интерес на практике имеют правильные автоматы второго рода, известные обычно под более кратким названием автоматов Мура.

Основные понятия алгебры логики.

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

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

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

Логическая (булева) переменная - такая величина х, которая может принимать только два значения: х = {0,1}.

Логическая функция (функция алгебры логики - ФАЛ) - функция многих аргументов f(xn-1, хn-2, ..., х0), принимающая значения равные нулю или единице на наборах логических переменных xn-1, хn-2, ..., х0.

В дальнейшем в формальных описаниях наборов переменных и логических функций сами наборы переменных интерпретируются как двоичные коды (числа). В двоичных кодах расположение логических переменных упорядочено в порядке уменьшения индекса слева направо, и каждая логическая переменная имеет вес в зависимости от позиции в коде, увеличивающийся справа налево. Вес каждой i-той логической переменной, являющейся значением разряда двоичного числа равен 2i (i = 0,...,n-l).

Для n-разрядного кода общее количество уникальных наборов переменных: N = 2n (1)

Максимальное числовое значение двоичного кода равно: Aмакс=2n - 1 (2)

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

Таблица 1

X

f0(x)

f1(x)

f2(x)

f3(x)

0

0

0

1

1

1

0

1

0

1

Функция f0(x) называется константой нуля, а функция f3(x) - константой единицы. Функция fi(x), повторяющая значения логической переменной, - тождественная функция (fi(x)=x), а функция f2(x), принимающая значения, обратные значениям переменной х, - логическое отрицание или инверсия (НЕ) (f2(x) = ).

Элементы алгебры логики имеют следующие операции:

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

Дизъюнкция (ИЛИ, логическая сумма) - сумма двух высказываний Р и Q; результатом является ложное высказывание, если оба высказывания ложные, и истинное во всех других случаях.

Инверсия (отрицание) - отрицанием высказывания Р называется высказывание истинное, если само высказывание Р ложное, или наоборот.

Для функции двух переменных, согласно ф.(1), существует четыре уникальных набора переменных. Функции отличаются друг от друга набором значений 0 и 1 в четырех разрядах кода значений функции. Общее количество функций на п-местном или п-разрядном наборе переменных равно: (3).

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

Аналитически это свойство описывается следующей формулой:

f1(xn-1, xn-2, …, x0) = f1(xn-1, xn-2, …, x0) (4)

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

Система булевых функций W называется функционально полной, если для любой булевой функции п-переменных f(xn-1, хn-2, ..., х0) может быть построена равносильная ей функция комбинированием булевых переменных xn-1, хn-2, ..., х0 и функций системы W, взятых в любом конечном количестве экземпляров каждая. Такая система булевых функций (W) называется базисом.

Таким образом, базис - полная система функций алгебры логики (ФАЛ), с помощью которой любая ФАЛ может быть представлена суперпозицией исходных функций W.

Базисом является система функций И (конъюнкция), ИЛИ (дизъюнкция), НЕ, (инверсия), свойства которых были впервые изучены Дж. Булем.

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

Для абстрактного математического описания цифрового автомата как кодопреобразователя используется представление 6-элементного множества S = {А, Х,У, , , a1,}.

Понятие множества - понятие, которое не имеет определения. Множества имеют свои подмножества, оно может быть конечным и бесконечным. Упорядоченным будет множество, в котором каждый элемент имеет своё место.

Множество будет состоять из следующих элементов:

А = {а1...,ап} -множество состояний автомата,

X = {х1...,хп} - множество входных сигналов,

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее