Задание на контрольную работу с методическими указаниями для студентов 3 курса специальности 23.05.05. Системы обеспечения поездов

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО

ТРАНСПОРТА

Филиал федерального государственного бюджетного образовательного учреждения высшего образования

«Самарский государственный университет путей сообщения в г. Саратове»

Теория дискретных устройств автоматики и телемеханики.

Задание на контрольную работу с методическими указаниями для студентов 3 курса специальности 23.05.05. Системы обеспечения поездов

ЗАДАНИЕ НА КОНТРОЛЬНУЮ РАБОТУ

ЗАДАЧА 1

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

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

Таблица 1

Таблица истинности комбинационных устройств

№ набора

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЗАДАЧИ 1

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

Синтез логической схемы включает в себя несколько этапов:

1) задание ФАЛ в виде таблицы истинности, в которой для каждого набора значений входных переменных указывают значение функции (0 или 1);

2) переход от таблицы истинности к структурной формуле в базисе И, ИЛИ, НЕ;

3) минимизация ФАЛ;

4) выбор элементной базы и запись структурной формулы минимизированной ФАЛ в выбранном базисе (И-НЕ или ИЛИ-НЕ);

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

Таблица истинности заданной ФАЛ составляется в зависимости от варианта (табл. 1). При переходе от таблицы истинности к структурной формуле применяют два способа составления последней. Если количество наборов значений входных переменных, при которых значение функции равно 1, значительно превышает количество наборов, при которых функция принимает нулевое значение, то применяют совершенную коньюктивную нормальную форму (СКНФ) представления ФАЛ, в противном случае, используют совершенную дизъюнктивную нормальную форму (СДНФ).

Правило составления записи структурной формулы в виде СДНФ заключается в том, что для каждой строки таблицы истинности, в которой значение функции равно «1», записывается минтерм - конъюнкция (логическое произведение) всех входных переменных, а затем производится логическое сложение минтермов. Если значение какой-либо входной переменной, например , в строке таблицы истинности равно нулю, то такая переменная записывается в минтерме в инверсном виде, т.е. , если равно единице – в прямом, т.е. .

Правило составления записи структурной формулы в виде СКНФ заключается в том, что для каждой строки таблицы истинности, в которой значение функции равно 0, записывается макстерм - дизъюнкция (логическая сумма) всех входных переменных, после чего производится логическое умножение макстермов. При этом, если значение какой-либо входной переменной в строке таблицы истинности равно «1», то такая переменная записывается в макстерме в инверсном виде, если равно «0» – в прямом..

Рассмотрим пример составления структурной формулы функции трех переменных , заданной таблицей истинности (табл. 2)

Таблица 2

Таблица истинности для функции трех переменных

№ набора

 

Составим структурную формулу ФАЛ в виде СДНФ для единичных значений функции , руководствуясь вышеизложенными принципами:

Составим структурную формулу ФАЛ в виде СКНФ для нулевых значений функции:

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

Минимизация ФАЛ заключается в нахождении минимальных нормальных форм ее записи (МДНФ или МКНФ), имеющих минимальное число вхождений входных переменных и минимальное число термов в функции.

Напомним некоторые определения, которые полезно знать при рассмотрении различных методов минимизации применительно к записи ФАЛ в МДНФ.

1) конъюнкции (логические произведения), входящие в СДНФ называются минтермами;

2) число переменных (с инверсией или без), входящих в минтерм, называется его рангом. Например, конъюнкция имеет второй ранг, - четвертый;

3) два минтерма, отличающихся только одной переменной называются соседними;

4) ДНФ функции называется тупиковой (ТДНФ), если она не содержит избыточных переменных, таких, которые можно изъять без нарушения эквивалентности исходной функции;

5) минимальной ДНФ (МДНФ) называется ТДНФ, содержащая наименьшее число переменных в минтермах и наименьшее число минтермов по сравнению с другими эквивалентными тупиковыми формами.

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

Наиболее эффективными и поэтому часто используемыми при минимизации являются закон склеивания (прил. 1.15) и закон поглощения (прил 1.13).

Применим операцию склеивания к исходной структурной формуле ФАЛ, представленной в СДНФ. Находим соседние минтермы и производим их попарное склеивание:

,

где одной или двумя линиями подчеркнуты соседние минтермы.

Таким образом, в результате выполненных алгебраических преобразований исходной ФАЛ получили искомую минимальную форму МДНФ:

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

Карта Карно заполняется следующим образом: в каждой клетке проставляется значение функции, которое она принимает на наборе значений переменных, являющихся ее координатами. Так, при представлении функции в СДНФ в каждой клетке, координаты которой соответствуют минтерму, для которого функция принимает единичное значение, указывается значение «1», значение «0» при этом на картах обычно не отражается. Например, клетке с координатами , для которой функция принимает единичное значение, соответствует минтерм .

При представлении ФАЛ в СКНФ в каждой клетке, координаты которой соответствуют макстерму (дизъюнкции), для которого функция принимает нулевое значение, указывается значение «0», значение «1», при этом на картах обычно не отражается. Так, для клетки, содержащей нулевое значение функции при значениях координат, указанных выше, макстерм будет иметь следующий вид: .

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

Рис. 1. Карта Карно для функции , заданной табл. 2

Минимизация ФАЛ заключается в объединении соседних клеток (при этом клетки, лежащие на границах карты, также являются соседними по отношению друг к другу), содержащих единичные (для получения МДНФ) или нулевые (для получения МКНФ) значения, в замкнутые области. Каждая область должна представлять собой прямоугольник с числом клеток . Области могут пересекаться, и одни и те же клетки могут входить в разные области. Это позволяет исключить одну переменную при объединении двух клеток, или две переменные при объединении четырех соседних клеток, или три переменные при объединении восьми клеток карты Карно. При охвате клеток замкнутыми областями следует стремиться к минимальному числу областей, каждая из которых содержала бы возможно большее число клеток.

В нашем случае, как видно из рис. 1, можно объединить четыре соседних клетки содержащих «1», или четыре соседних клетки содержащих «0». Это говорит о том, что функция зависит только от одной переменной и не зависит от значений переменных и . Т.е. МДНФ и МКНФ имеют одну и ту же минимальную форму: .

Цифровые значения координат клеток карты Карно можно заменить также переменными, которые при данных значениях координат принимают прямое или инверсное значение. На рис. 2 даны варианты представления карты Карно для функции .

Рис. 2. Варианты представления карты Карно для функции :

а) для случая записи в СДНФ; б) для случая записи в СКНФ

На рис. 2,а показана карта Карно для минимизации функции, представленной в СДНФ. В этом случае МДНФ может быть представлена в виде логической суммы минтермов, количество которых соответствует числу замкнутых областей.

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

Для записи полученных в результате минимизации ФАЛ в базисах И-НЕ или ИЛИ-НЕ используют закон де Моргана (закон дуальности), согласно которому инверсия дизъюнкций переменных равна конъюнкции инверсий этих переменных и, наоборот, инверсия конъюнкции переменных равна дизъюнкции инверсий этих переменных.

Рассмотрим в качестве примера МДНФ следующей функции:

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

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

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

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

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

На рис. 3 представлена техническая реализация функции на логических элементах И-НЕ, а на рис.4 - ИЛИ-НЕ.

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

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

 

ЗАДАЧА 2

Провести синтез автомата Мили, функционирование которого описывается заданными таблицами переходов и выходов. Изобразить граф синтезируемого автомата. Задавая произвольную двоичную последовательность (входное слово), определить соответствующую двоичную выходную последовательность (выходное слово) автомата. Построить структурную схему синтезированного автомата в базисе И, ИЛИ, НЕ.

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

Таблица 3

Варианты таблиц переходов

Последняя цифра шифра	Последовательность состояний автомата Мили
	А1	А3	А1	А0	А0	А2	А3	А3
	А3	А1	А1	А0	А1	А2	А2	А3
	А0	А1	А2	А3	А1	А0	А2	А1
	А2	А0	А3	А0	А1	А0	А3	А2
	А0	А0	А3	А3	А3	А2	А1	А1
	А1	А0	А1	А3	А0	А3	А3	А2
	А3	А3	А0	А2	А2	А1	А1	А1
	А0	А1	А3	А3	А0	А0	А2	А1
	А3	А2	А1	А0	А1	А2	А3	А2
	А2	А0	А2	А0	А3	А1	А0	А2

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

Рассмотрим пример определения задания для шифра 98-АТС-5089. Из приведенной табл. 3 выбирается строка под номером 9. Число 089 или просто 89 записывается в двоичной системе счисления как 1011001. Добавим слева 0 до восьми разрядов. Получим в результате искомую последовательность 01011001.

Заполняем соответствующие таблицы, как это показано на рис. 5.

Таблица переходов		Таблица выходов
Входной сигнал	Состояние		Входной сигнал	Состояние
А0	А1	А2	А3		А0	А1	А2	А3
	А2	А0	А2	А0
	А3	А1	А0	А2

Рис. 5. Пример заполнения таблиц переходов и выходов

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЗАДАЧИ 2

Синтез последовательностных устройств

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

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

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

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

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

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

1) определить какая комбинация состояний триггеров будет соответствовать каждому из внутренних состояний автомата, т.е. провести кодирование внутренних состояний автомата;

2) синтезировать комбинационное устройство формирования сигналов управления триггерами , используя таблицу переходов;

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

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

Рис. 6. Граф функционирования автомата

Допустим, для хранения состояний автомата используется память, построенная на триггерах, каждый из которых имеет два состояния (0 или 1). Следовательно, число различных комбинаций состояний триггеров равно . Так как каждой из этих комбинаций может соответствовать только одно определенное состояние синтезируемого автомата, то выбор требуемого числа триггеров должен производиться из условия, что число состояний автомата не будет превышать . Заданный по условиям задачи автомат имеет четыре состояния, следовательно, для его реализации достаточно двух триггеров, т.е. .

Затем каждой комбинации состояний триггеров нужно поставить в соответствие определенное состояние автомата. Кодирование состояний автомата может производиться различными способами. Для синтезируемого автомата кодирование его состояний произведем в соответствии с табл. 4.

Таблица 4

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

Состояние автомата	Состояние триггеров
А0
А1
А2
А3

Далее заполним табл. 5 функционирования автомата, заданного графом, представленным на рис. 6.

Таблица 5

Таблица функционирования автомата Мили

Входной сигнал	Предыдущее состояние	Сигнал состояния	Сигналы управления триггерами	Выходной сигнал
						*
					*			*
						*
					*
							*

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

Столбцы с 6 по 9 отведены для записи сигналов управления триггерами. Управление триггерами осуществляется подачей сигналов на входы очистки (вход ) и установки (вход ). Эти сигналы для каждого триггера определяются сравнением их состояний в момент времени - и в последующий момент времени - . Например, в первой строке табл.5 , . Это означает, что второй триггер переводится из состояния «0» в состояние «1».Для этого должен быть подан сигнал «1» на вход и «0» на вход . Во второй строке табл.5 , а , следовательно, для перевода этого триггера из состояния «1» в состояние «0» необходимо подать сигнал «0» на вход и «1» на вход .

В тех случаях, когда предыдущее и последующее состояния триггера совпадают, (триггер хранит предыдущее состояние), то на оба входа (очистки и установки) можно подать сигнал «0» (, ), или на определенный вход триггера может подаваться сигнал подтверждения состояния триггера , (установка «1») или , (очистка или установка «0»).

Например, если триггер был в состоянии «1» и должен сохранить это состояние в следующем такте, то либо на обоих его входах присутствует сигнал «0» (, ), что соответствует режиму хранения информации, либо на вход может быть подан сигнал «1» подтверждения состояния (, ). В подобных случаях, когда логический уровень сигнала управления безразличен («0» или «1»), соответствующие клетки табл.5 остаются пустыми или в них заносится символ *.

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

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

Рис. 7. Карты Карно для нахождения минимальных форм сигналов управления триггерами

Рис.8. Карты Карно для нахождения минимальной формы выходного сигнала

Рассматривая и как неполностью определенные логические функции аргументов и , запишем МКНФ этих функций:

;

;

Так как функция принимает единичное значение на меньшем числе наборов переменных, представим ее в МДНФ:

Используя полученные логические выражения и выбрав в качестве базиса логические элементы И, ИЛИ, НЕ, вычерчиваем структурную схему синтезируемого автомата, представленную на рис. 9.

Рис. 9 Функциональная схема автомата Мили

Примечание. Для обеспечения правильной работы схемы автомата необходимо предусмотреть синхронизацию его функционирования во времени. Для этого в схеме (рис. 9) предусмотрен сигнал синхронизации , который в моменты времени разрешает подачу управляющих сигналов с выхода комбинационного устройства на входы триггеров, выполненных по двухступенчатой схеме. Запись информации в триггеры первой ступени, образованной триггерами и , происходит по высокому уровню синхросигнала , а в триггеры второй ступени ( и ) – по низкому уровню синхросигнала. На выходе автомата информация будет изменяться по отрицательному фронту синхросигнала . Это соответствует алгоритму работы синхронного двухступенчатого (MS) RS-триггера.