KL_kur_met

1

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ ТЕХНОЛОГІЧНИЙ ІНСТИТУТ

СХІДНОУКРАЇНСЬКОГО НАЦІОНАЛЬНОГО УНІВЕРСИТЕТУ ІМЕНІ ВОЛОДИМИРА ДАЛЯ (М. СЄВЄРОДОНЕЦЬК)

МЕТОДИЧНІ ВКАЗІВКИ ДО ВИКОНАННЯ КУРСОВОГО ПРОЕКТУ

ЗА ДИСЦИПЛІНОЮ " КОМП'ЮТЕРНА ЛОГІКА "

Для студентів денної і заочної форми навчання напряму підготовки 6.050102 "Комп'ютерна інженерія"

(електронне видання)

Сєвєродонецьк, 2013р

2

ВВЕДЕНИЕ

Настоящий курсовой проект по курсу ПТЦА предполагает практическое применение теоретических знаний студентов, полученных при изучении курса.

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

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

-сокращенная таблица переходов и выходов абстрактного автомата;

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

-типы используемых логических элементов.

Пример исходных данных приведен в разделе 2(типы логических элементов – в разделе 7).

1. СОДЕРЖАНИЕ КУРСОВОГО ПРОЕКТА

Курсовой проект выполняется в следующем порядке:

1.По заданному сокращенному описанию составляется таблица переходов и выходов абстрактного автомата.

2.Производится минимизация числа внутренних состояний автомата с применением алгоритма Ауфенкампа-Хона, строится граф переходов автомата.

3.Строятся сокращенные и полные таблицы переходов триггеров и соответствующие им матрицы переходов триггеров.

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

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

6.Строится функциональная схема автомата в заданном функциональном базисе. Курсовой проект должен содержать:

- титульный лист; - техническое задание; - реферат; - содержание;

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

- список использованных источников;

графическая часть - граф переходов автомата и схему электрическую функциональную. Пояснительная записка выполняется в соответствии с ГОСТ. Графическая часть

выполняется на листах формата А3 или А2. Схема электрическая функциональная выполняется в соответствии с требованиями ГОСТ 2.743-82 и ГОСТ 2.708-81.

3

2.ПРИМЕР ИСХОДНЫХ ДАННЫХ

2.1Сокращенная запись таблицы переходов автомата представлена в таблице 2.1.

В таблице 2.1 первая строка – выходные сигналы автомата У = {yi}, вторая строка – состояния автомата А = {aj}, оставшиеся строки соответствуют номерам состояний, в которые переходит автомат под воздействием входных сигналов x1, x2, x3.

2.2 Пример задания типа триггера представлен таблицей 2.2. Методика построения таблиц и матриц переходов триггера для данного примера приведена в разделе 4.. Руководителем проекта может быть задан стандартный тип используемого триггера (D, T,

RS, JK, RST, D , J K ,).

Таблица 2.2

3. МИНИМИЗАЦИЯ ЧИСЛА ВНУТРЕННИХ СОСТОЯНИЙ АБСТРАКТНОГО АВТОМАТА

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

Процедура минимизации (алгоритм Ауфенкампа-Хона) подробно изложена в [1]. В приложении 1 к данным методическим указаниям изложено краткое содержание этой процедуры.

4.ПОСТРОЕНИЕ ТАБЛИЦ И МАТРИЦ ПЕРЕХОДОВ ТРИГГЕРА

4.1Табличный вариант задания типа триггера (пример для триггера, заданного таблицей 2.2)

Строится сокращенная таблица переходов с двумя информационными входами (табл. 4.1) и полная таблица переходов асинхронного триггера с двумя информационными входами Х и У (табл. 4.2).

При построении таблиц переходов синхронного триггера (дополнительно к входам Х и У вводится вход синхронизации С), следует иметь ввиду, что при С=0 внутреннее состояние триггера не изменяется независимо от состояний входов Х и У, т.е. Q(t+1)=Q(t), а

5

где b1, b2, b3, b4 - произвольные сигналы (0 или 1)

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

4.2 Тип используемого триггера (D, T, RS, JK, RST, D , J K ,) задается руководителем проекта.

5. КОДИРОВАНИЕ АВТОМАТА

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

Для кодирования входных сигналов выписывается множество входных сигналов

Х={х1, х2 ... хМ}, которые кодируем векторами длины Квх= int (log2М), где int - округление до ближайшего большего целого числа, М - мощность (количество символов) входного

алфавита. Кодирование входных сигнал осуществляется произвольно.

Выходные сигналы автомата У={у1, у2, …уS} кодируем вектором длины Квых= int(log2S), где S - мощность выходного алфавита. Для кодирования выходных сигналов применяется весовой алгоритм [1].

1.Каждому выходному сигналу уі ставится в соответствие целое число Рі, равное числу появлений сигнала уі в таблице выходов автомата.

2.Числа Рі сортируются по убыванию.

3.Выходной сигнал уі с наибольшим весом (Рі max) кодируются кодом, содержащим все 0 (00...00).

4.Следующие L выходных сигналов (где L- число разрядов в двоичном векторе выходного сигнала) по списку убывания веса (см п. 2) кодируются кодами, содержащими одну 1 (00...01, 00...10, ... ,10...00)

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

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

Состояния автомата А={а1, а2 ... аR} кодируем вектором длины Ксост= int(log2R), где R - мощность алфавита состояний. Отметим, что длина вектора кода состояния определяет и

количество элементов памяти (триггеров) данного автомата.

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

6

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

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

При таком критерии уменьшается сложность схем, реализующих дизъюнкции на входах элементов памяти, т.е. минимизируется комбинационная схема автомата. Для оценки кодирования вводится коэффициент эффективности кодирования: Кэф= W/P; где P - общее количество переходов автомата,

W - весовая функция : W= t ij ,

где tij - расстояние Хэмминга между кодами состояний ai и aj, равное числу элементов памяти, изменяющих свое состояние на данном переходе.

Отметим, что при определении весовой функции суммирование производится по всем переходам автомата. Коэффициент эффективности позволяет оценить сложность комбинационной схемы автомата: чем меньше его значение, тем меньше сложность комбинационной схемы, и оптимальный вариант - Кэф=1.

Эвристический алгоритм кодирования состояний приведен в Приложении 2 Кодирование состояний автомата производится с применением эвристического

метода кодирования.

.

6. ФОРМИРОВАНИЕ ФУНКЦИЙ ВОЗБУЖДЕНИЯ И ФУНКЦИЙ ВЫХОДА АВТОМАТА

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

где wn- функция выходов автомата;

φi - функция возбуждения элементов памяти;

α - функция обратной связи от элементов памяти к комбинационной схеме; z - кодированные входные сигналы.

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

В качестве примера рассмотрим автомат Мура, заданный таблицей переходов и выходов (таблица 6.1.).

8

Примечание: в таблице 6.7. Х1, У1, Х2, У2, Х3, У3 - функции возбуждения элементов памяти по входам Х1, ... У3 соответственно.

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

Минимизация представлена на рис.6.1.-6.8.

Рис. 6.4 Минимизация функции У1.

9

Рис. 6.8 Минимизация функции У3.

Рассмотрим вариант доопределения: b1=b2=b3=b4=0. В этом случае канонические выражения примут вид:

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

7. ПОСТРОЕНИЕ ФУНКЦИОНАЛЬНОЙ СХЕМЫ АВТОМАТА

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

1.Элементы И, ИЛИ, НЕ. Количество входов элементов И, ИЛИ - от 2 до 4-х. Нагрузочная способность всех элементов - до 10.

2.Элементы И-НЕ. Количество входов - от 2 до 6. Нагрузочная способность - до 10.