Контрольная работа по дисциплине ’’Теория дискретных устройств железнодорожной автоматики, телемеханики и связи’’ выполняется студентами 3 курса специальности АТС по программе, утверждённой Главным управлением учебных заведений МПС, с целью практического закрепления изученных теоретических основ и принципов построения дискретной техники, используемой на железнодорожном транспорте.
Контрольная работа включает в себя две части и посвящена задачам анализа и синтеза релейных и бесконтактных устройств. Решение каждой из них должно быть выполнено в той же последовательности, в которой они представлены. Порядок решения и методические указания изложены ниже, отдельно для каждой задачи.
Прежде чем приступить к выполнению работы, следует ознакомиться с соответствующими разделами, изложенными в книге [1]. При необходимости можно также воспользоваться дополнительной литературой [2,3].
Выбор номера варианта задания определяется суммой цифр порядкового номера шифра студента (цифр, следующих за шифром специальности). Так, например, студент, имеющий шифр 88АТС035, выбирает восьмой вариант, 86АТС137 - одиннадцатый, 87АТС5 - пятый и т. д. Таблицы вариантов приведены в конце каждой части.
Релейным устройством (РУ) называется устройство, построенное на элементах релейного действия. Общий вид РУ приведен на рис. 1. РУ имеет n входов x и m выходов y. Значения сигналов на входах и выходах-двоичные, т. е. принимают только два значения: 0 и 1.
Релейные устройства делятся на два больших класса:
- комбинационные схемы (автоматы без памяти);
- многотактные схемы (автоматы с памятью);
1. Анализ и синтез комбинационных схем.
Цель контрольной работы - изучение особенностей функций алгебры логики (ФАЛ), построение логических схем по заданной формуле с использованием различных элементных базисов, изучение методов преобразования ФАЛ, освоение методов минимизации функций алгебры логики.
1.1. КРАТКИЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ДИСКРЕТНЫХ УСТРОЙСТВ
Комбинационной логической схемой (КС) называется устройство, имеющее n входов x и один выход y. Входы и выходы являются двоичными. Внутренняя структура КС построена также на двоичных элементах.
Работа КС не зависит от времени. Это значит, что при одном и том же состоянии входов в различные моменты времени наблюдается всегда одно и то же состояние выхода.
Математическим аппаратом для описания КС являются функции алгебры логики (ФАЛ). Их также называют булевыми функциями. ФАЛ от n переменных f (x1, x2,....,x n) может быть задана различными способами [1]. Одним из способов задания ФАЛ является таблица истинности (ТИ). Например, табл. 1 задана ФАЛ от трёх переменных. Она соответствует работе КС с тремя входами x (x1, x2, x3) и одним выходом y (рис. 2). Таблица содержит восемь строк, каждая из которых соответствует одному из возможных состояний всех трёх кнопок: x1, x2, x3. Общее количество состояний определяется выражением N=2 n, где n - количество входов. Значение y в строке определяет состояние лампы при данном состоянии входов (y=0 - лампа не горит, y=1 - лампа горит). Значение y в каждой строке определяется заданным алгоритмом работы КС. Например, запись в строке под номером 0 означает, что если все три кнопки не нажаты (x1 =x2 =x3 =0), то по условиям работы лампа должна гореть (y=1).
Таким образом, ФАЛ обладает следующей особенностью: все переменные и сами функции принимают только два значения.
Областью определения ФАЛ от n переменных является множество двоичных наборов, число которых равно 2 n. Каждому двоичному набору сопоставляется нулевое или единичное значение функции. Поэтому областью значений ФАЛ является множество {0,1}.
Задать ФАЛ можно перечислением тех двоичных наборов, на которых она равна 1. Эти наборы называются разрешенными. Например, функция y из табл. 1. задаётся следующим множеством: {000, 001, 100, 110}. Каждый двоичный набор N есть некоторое двоичное число, которое может быть переведено в десятичное число по формуле:
N = C i 2 i,
где i - номер разряда (i = 0, 1, 2,...., k); C i - коэффициент при i - м разряде (C i = 0 или 1); 2 i - вес i-го разряда.
Например,
.
В табл. 1 в левом крайнем столбце приведены десятичные эквиваленты двоичных чисел. Таким образом, ФАЛ можно задать также с помощью множества десятичных чисел, соответствующим разрешённым двоичным наборам. Например, функция y из табл. 1 задаётся следующим множеством: {0, 1, 4, 6,}.
Таблица 1
Рис. 2
x1
№
П/п
x1
x2
x3
x4
x2
1
0
1
x3
4
Можно показать, что число ФАЛ от n переменных равно 2 2 .Это число астрономически быстро растёт с ростом n. Поэтому уже при n = 4 практически нет возможности изучить каждую функцию. Однако оказывается, что в этом нет необходимости. Существуют три функции, которые называются отрицание, дизъюнкция и конъюнкция (другие названия - соответственно НЕ, ИЛИ, И), с помощью которых можно выразить все другие ФАЛ от любого числа переменных. Говорят, что они образуют функционально-полную систему функций или базис.
Функции НЕ, ИЛИ, И задаются соответственно табл. 2, 3, 4, из которых следует их содержательный смысл. Функция НЕ принимает значения, противоположные входной переменной. Функция ИЛИ равна 1, если хотя бы одна из переменных равна 1. Функция И равна 1 только тогда, когда обе переменные равны 1. Для этих функций соответственно используются следующие обозначения:
.
Таблица 2 Таблица 3 Таблица 4
X
Y
X1
X2
Y
X1
X2
Y
Введение специальных знаков логических операций И, ИЛИ, НЕ позволяет задавать ФАЛ в алгебраической форме. Рассмотрим, например, функцию:
Для того чтобы перейти от алгебраической записи ФАЛ к таблице истинности используются аксиомы алгебры логики, вытекающие непосредственно из табл. 2 - 4:
; (1)
(2)
(3)
Рассчитаем, например, значение y при X1 = 1, X 2 = 0, X 3 = 0. При этом должен соблюдаться следующий порядок выполнения операций:
Если рассчитывать подобным образом значение у всех возможных восьми наборов, то получим таблицу истинности (см. табл. 1).
Доказательство того факта, что система функций И, ИЛИ, НЕ образует базис, состоит в указании алгоритма обратного перехода от таблицы истинности к алгебраической формуле, содержащей знаки только трёх операций: И, ИЛИ, НЕ. Этот алгоритм заключается в следующем:
1) выбрать в таблице истинности ФАЛ все наборы, на которых функция равна 1;
2) выписать конъюнкции, соответствующие этим наборам. При этом, если переменная x входит в набор как 0, то она записывается с отрицанием. В противном случае она записывается без отрицания;
3) все полученные конъюнкции соединяются между собой знаками дизъюнкции.
Применение данного алгоритма к табл. 1 даёт следующий результат:
.
Полученная форма записи ФАЛ называется дизъюнктивной совершенной нормальной формулой (ДСНФ). Свойства функции И, ИЛИ, НЕ называются законами алгебры логики. Приведём несколько законов, которые потребуются в дальнейшем:
(4)
; (5)
(6)
(7)
Функционально полная система функций называется минимальной, если удаление из неё хотя бы одной функции делает систему неполной.
Базис {И, ИЛИ, НЕ} не является минимальным, так как из него можно исключить либо функцию И, либо функцию ИЛИ с сохранением полноты. Это доказывается тем, что функция И (ИЛИ) может быть выражена через функцию ИЛИ (И) и НЕ с помощью формул де Моргана (5) и (6). Взяв отрицание над левой и правой частями формул (5) и (6) и учитывая формулу (4) - закон двойного отрицания, получим:
; (8)
(9)
Таким образом, системы {И, НЕ} и {ИЛИ, НЕ} образуют минимальные базисы. Формулы (8) и (9) позволяют переходить от одной формы записи ФАЛ к другой.
Понятие базиса играет существенную роль при построении ФАЛ на логических элементах. Логическим элементом является элемент, реализующий некоторую логическую функцию. На рис. 3, а, б, в приведены соответственно обозначения логических элементов, реализующих функции И, ИЛИ, НЕ. Они могут быть построены на транзисторах интегральных микросхемах, магнитных кольцах и других элементах.
Для реализации ФАЛ, заданной логической формулой, необходимо иметь столько типов логических элементов, сколько функций содержится в базисе, в котором записана ФАЛ.
Реализация ФАЛ возможна также на базисе одного логического элемента. Такими элементами являются:
- элемент И - НЕ (рис. 4. а), который реализует функцию Шеффера;
- элемент ИЛИ - НЕ (рис. 4. б), который реализует функцию Вебба.
Каждый из этих элементов реализует функционально полную систему алгебры логики. На рис. 5 показана реализация основных ФАЛ на элементе ИЛИ - НЕ.
Так как одна и та же ФАЛ может быть записана с помощью различных формул, то возникает задача получения минимальной формы записи (с минимальным числом букв), которая потребует минимальных затрат аппаратуры при реализации.
Рассмотрим процесс минимизации ФАЛ с помощью карт Карно. Карта Карно (рис. 6) является другой формой представления таблицы истинности (см. табл. 1). Каждая клетка карты соответствует строке таблицы (двоичному набору). Часть клеток (половина), которым соответствует X i = 1, отмечается скобкой. Для задания ФАЛ в карте Карно надо проставить 1 в тех клетках, которые соответствуют разрешённым наборам. В карте на рис. 6 задана ФАЛ из табл.1. На рис. 7 представлена карта Карно для ФАЛ от четырёх переменных, заданных в виде множества:
f = {2, 3, 4, 5, 6, 7, 10, 11, 12}.
Минимизация ФАЛ по карте Карно заключается в объединении соседних клеток в прямоугольные контуры, причём соседними считаются клетки, разделённые внешней границей карты. Правила минимизации состоят в следующем:
1) все единицы должны быть заключены в прямоугольные контуры;
2) во всех клетках должны стоять единицы;
3) число клеток в контуре должно быть кратно степени 2;
4) контуры могут накладываться друг на друга;
5) контуры, все клетки которых уже вошли в другие контуры, являются лишними;
6) для получения более простой формулы надо выбирать контуры с максимальным числом клеток;
7) каждому контуру соответствует конъюнкция, составленная из переменных, значения которых не изменяются во всех клетках контура.
На рис. 7 представлены контуры, полученные в соответствии с данными правилами. Из правила 7 вытекает следующий результат минимизации:
.
1.2 МЕТОДИКА ВЫПОЛНЕНИЯ ЗАДАНИЯ
Таблица вариантов, приведенная в конце первой части методических указаний, имеет три столбца: номер варианта, функция 1, функция 2.
Задание состоит из двух частей.
1. По функции, заданной в алгебраическом виде (функция 1), необходимо выполнить следующее. Построить контактно - релейную схему.
Построение производиться по следующим правилам:
а) порядок выполнения операций - НЕ, И, ИЛИ;
б) конъюнкция реализуется за счёт последовательного соединения контактов, дизъюнкция - за счёт параллельного;
в) переменной без отрицания соответствует фронтовой контакт, переменной с отрицанием - тыловой;
г) выражения в скобках и под чертой реализуются в первую очередь;
д) если в формуле есть выражение под знаком инверсии, то либо она преобразуется с помощью формулы де Моргана [(5) или (6)] до тех пор, пока знак инверсии остаётся только над переменными либо применяется дополнительное реле.
Пусть задана формула . Так как она содержит выражение под знаком инверсии, осуществляем её преобразование:
Схема, построенная по преобразованной формуле, показана на рис. 8.
Для построения схемы вторым способом обозначим: Тогда Соответствующая схема представлена на рис. 9.
2. Построить таблицу истинности.
Таблицу истинности удобно строить поэтапно, выделяя столбец для отдельных выражений исходной формулы. Так для формулы таблица истинности будет иметь вид табл. 5.
3. Построить схему в базисе {И, ИЛИ, НЕ}.
Схема строится на элементах, представленных на рис. 4. Построение схемы следует производить, руководствуясь следующими правилами:
а) для реализации каждой логической операции используется соответствующий логический элемент;
б) порядок выполнения операций - НЕ, И, ИЛИ;
в) выражения в скобках и под чертой реализуются в первую очередь.
Схема, реализующая формулу , показана на рис. 10.
4. Построить схему в базисе {ИЛИ - НЕ}.
Схема строится по исходной формуле с использованием только элемента, показанного на рис. 4, б.
Правила построения схем:
а) для реализации каждой логической операции используется соответствующая комбинация элемента ИЛИ - НЕ, реализующая заданную логическую функцию (рис. 5);
б) порядок выполнения операций - НЕ, И, ИЛИ;
в) выражения в скобках и под знаком инверсии реализуются в первую очередь.
Для формулы схема показана на рис. 11. Сокращение в схеме логических элементов надо показывать пунктирной линией.
5. Построить схему в базисе {И - НЕ}.
Правила построения схемы в базисе И - НЕ аналогичны правилам пункта 4.
6. Записать исходную формулу в базисе {И - НЕ}.
Преобразование формулы осуществляется с использованием законов алгебры логики. Не следует исключать результаты промежуточных преобразований.
а
б
в
а
б
Пример преобразований:
7. Записать исходную формулу в базисе {ИЛИ - НЕ}.
Пример преобразований:
.
Исходные данные для второй части задания приведены в столбце 3 ’’ функция 2 ’’ таблицы вариантов. Ряд десятичных чисел, представленный в столбце 3, - ФАЛ в десятичном виде.
ФАЛ, заданные в столбце 2 и столбце 3 таблицы вариантов, для каждого задания различны.
По функции, заданной десятичными числами (столбец 3), необходимо выполнить следующее:
1. Построить ТИ. Для функции, заданной набором десятичных чисел 0, 4, 6, 8, 12, 13, 14, 15, таблица истинности имеет вид табл. 6.
2. Осуществить минимизацию функции с помощью карты Карно. Для ФАЛ f = {0, 4, 6, 8, 12, 13, 14, 15} карта Карно представлена на рис. 12. Минимизированная функция будет иметь вид:
2. Построить схему по полученной МДНФ в выбранном базисе.
2. Исключение критических состязаний в многотактных схемах
Цель решения данной задачи - ознакомление с методикой анализа и синтеза многотактных схем и методов исключения критических состязаний.
2. 1. О с н о в н ы е п о л о ж е н и я
Важной частью теории дискретных устройств является теория многотактных схем (МС), изучающая дискретные устройства с памятью. Теория МС включает в себя анализ и синтез схем. Под синтезом МС понимается построение конкретной схемы по словесному описанию алгоритма функционирования устройства. Анализ МС включает в себя построение таблицы переходов и таблицы выходов по заданной схеме.
Многотактная схема отличается от комбинационной тем, что при одинаковых воздействиях на входах в различные моменты времени на её выходах могут быть различные сигналы. Работа МС зависит не только от входного воздействия в данный момент времени, но и от поступления входных воздействий в предшествующие моменты времени.
Рассмотрим схему, показанную на рис. 13. Она является комбинационной, если контакт у неё подключён параллельно контакту x 2. Из таблицы истинности (табл. 7) видно, что одному и тому же входному состоянию, независимо от времени (такта) его поступления, соответствует одно и тоже выходное состояние (например, такты 1 и 3).
Изменим схему, как показано на рис. 13 пунктиром. Табл. 8 описывает работу этой схемы во времени. Теперь одному и тому же входному состоянию в разные моменты времени (такты 1 и 3) соответствуют разные выходные состояния, т. е. схема стала многотактной. При поступлении входных сигналов x 1=0 и x 2=1 (кнопка x 1 отпущена, а кнопка x 2 нажата) включается реле Y и замыкает свой контакт y в цепи самоблокировки .
Таблица 5
N
п/п
x1
x2
x3
x4
f
Рис. 10
Таблица 6
№
п/п
x1
x2
x3
x4
f
x1
x2
0
4
x4
8
x3
12
Рис. 12
15
Таблица вариантов
номер варианта
функция 1
функция 2
2, 3, 6, 7, 10, 11, 13, 14, 15
1, 5, 8, 10, 12, 14
1, 2, 3, 5, 6, 7, 14, 15
0, 1, 3, 4, 5, 7, 12, 13
1, 3, 4, 5, 7, 11, 15
1, 5, 8, 9, 12, 13, 14, 15
Продолжение таблицы вариантов
7
0, 1, 4, 5, 7, 10, 11, 13, 14, 15
8
0, 1, 2, 4, 5, 8, 9, 12, 13, 14, 15
9
2, 3, 4, 5, 10, 11
10
4, 8, 9, 10, 11, 12, 13, 14, 15
11
0, 1, 6, 7, 8, 9
12
1, 5, 7, 9, 13, 14, 15
13
2, 3, 5, 6, 7, 8, 9, 12, 13, 15
14
1, 3, 5, 6, 7, 9, 10, 11, 13, 15
15
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13
16
3, 7, 8, 10, 12, 14
17
2, 3, 4, 5, 6, 7, 11, 15
18
0, 1, 4, 5, 7,8, 9, 11, 12, 13
19
0, 1, 2, 3, 4, 5, 6, 7, 12, 15
20
1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15
21
0, 1, 2, 3, 4, 5, 8, 9
22
0, 1, 10, 11, 12, 13, 14, 15
23
0, 2, 4, 6, 11, 15
24
3, 6, 7, 11, 12, 13, 14, 15
25
2, 6, 9, 10, 11, 13, 14, 15
Продолжение таблицы вариантов
26
0, 1, 3, 5, 6, 7, 14, 15
27
0, 2, 3, 6, 7, 9, 11, 13, 15
28
1, 3, 6, 7, 8, 10, 14, 15
29
0, 6, 8, 9, 11, 13, 14, 15
30
0, 1, 2, 3, 5, 7, 8, 10
31
0, 2, 4, 5, 8, 10, 12, 13
32
0, 4, 6, 8, 12, 13, 14, 15
После отпускания кнопки x 2 реле X 2 выключится, а реле Y останется включенным по цепи . Таким образом, цепь самоблокировки реле Y позволила запомнить факт нажатия кнопки x 2 . Для отмены запоминания нажатия кнопки x 2 необходимо выключить реле Y, т. е. нажать кнопку x 1 . Сравнение двух вариантов схем, показанных на рис. 13, позволяет сделать вывод, что МС содержит в своей структуре реле Y - внутреннее реле, которое реализует память за счёт цепи самоблокировки через собственный контакт. Признаком МС является наличие в цепях включения внутренних реле контактов этих же реле.
Общая схема МС, построенная на реле, показана на рис. 14, где x 1, x2,..., x n - входы; X 1, X 2,..., X n - входные реле, фиксирующие значения входных переменных; Y1, Y2,...., Ym - внутренние реле, реализующие алгоритм работы схемы (память схемы); Z 1, Z 2,...., Z q - выходы.
Рассмотренный пример МС (см. рис. 13) показывает, что таблица истинности не может описывать работу схемы с памятью, потому что для неё не существует однозначного соответствия между входами и выходами. Поэтому для задания работы МС используются две таблицы - таблица переходов (ТП) и таблица выходов (ТВ).
Рассмотрим задачу анализа МС, которая формулируется следующим образом: по заданной схеме построить ТП и ТВ.
2. 2. А л г о р и т м а н а л и з а М С
Произведём анализ схемы, приведённой на рис. 15.
1. Составляем функции алгебры логики для цепей включения внутренних реле и выходных цепей:
2. Составляем кодированную ТП (табл. 9). Столбцы ТП соответствуют входным наборам. Если n - число входов схемы, то 2 n - число столбцов ТП. Строки ТП соответствуют внутренним состояниям схемы (S).
Под состоянием МС понимается состояние её внутренних реле. В данном случае три внутренних реле имеют 8 состояний. Если m - число внутренних реле, то 2 m - число строк состояний ТП. В клетке на пересечении столбца и строки проставляет состояние, в которое переходит схема, если она находилась в состоянии, соответствующем данной строке, и на её вход поступает набор, соответствующий данному столбцу.
Рассмотрим, например, клетку (1, 010) на пересечении столбца x = 1 и строки 010. Она отмечена знаком в табл. 9. В общем случае клетку будем определять так: (), где или 1, или 1. Посмотрим, что будет с реле Y1, Y2 и Y3, если реле Y1 было выключено, реле Y2 - включено, реле Y3 - выключено, а на вход схемы поступает сигнал x = 1. Чтобы это определить подставим в функцию Y1,Y2,Y3 значения x = 1, y 1 = 0, y 2 = 1, y 3 = 0:
Это означает, что реле Y1 останется выключенным, реле Y2 - выключится, а реле Y3 - включится.
Заносим полученные значения функций Y1, Y2 и Y3 в табл. 9. Сформулируем правило заполнения кодированной ТП: в клетке () проставляются значения ФАЛ Y1, Y2, Y3, которые получаются при подстановке в них значений переменных . В соответствии с этим правилом заполняются остальные клетки табл. 9.
3. Составляем кодированную ТВ (табл. 10). Строки и столбцы ТВ имеют тот же смысл, что и в ТП, но изменяется содержание клеток. Правило заполнения клеток ТВ: в клетке на пересечении столбца и строки проставляются значения выходов, которые имеет схема, если она находится в состоянии, соответствующем данной строке, и на входе схемы имеется набор, соответствующий данному столбцу. Например, для клетки (0, 101), которая отмечена знаком в табл. 10, имеем Построенные ТП и ТВ полностью описывают поведение многотактной схемы.
Введём несколько понятий, связанных с ТП. Будем говорить, что клетка ТП соответствует полному состоянию схемы. Полное состояние определяет состояние входных реле и внутренних.
Полное состояние схемы делится на устойчивые и неустойчивые. Устойчивым называется состояние, в котором схема может находиться сколько угодно долго до изменения входов. Признак устойчивого состояния: в клетке устойчивого состояния записано внутреннее состояние (то, что должно быть), совпадающее с внутренним состоянием, соответствующим строке, в которой находится клетка (то, что было). Для обозначения устойчивого состояния используются круглые скобки (см. табл. 9 и 11).
Неустойчивым называется состояние, в котором создаются условия для изменения внутреннего состояния схемы. Признак неустойчивого состояния: в клетке неустойчивого состояния записано внутреннее состояние (то, что должно быть), не совпадающее с внутренним состоянием, соответствующим строке, в которой находится клетка.
Тогда работу МС, используя табл. 9, можно пояснить диаграммой, показанной на рис. 16.
2.3. М е т о д и с к л ю ч е н и я к р и т и ч е с к и х с о с т я з а н и й
Рассмотрев процедуру анализа МС, можно перейти к вопросам исследования поведения МС. Одной из задач, решаемых при исследовании поведения МС, является проверка её на устойчивость работы. Основным фактором, определяющем устойчивую работу схемы, является корректное использование (учёт) временных соотношений срабатываний входных и внутренних реле.
Релейным устройством (РУ) называется устройство, построенное на элементах релейного действия. Общий вид РУ приведен на рис. 1. РУ имеет n входов x и m выходов y. Значения сигналов на входах и выходах-двоичные, т. е. принимают только два значения: 0 и 1.
C i 2 i,
.
.Это число астрономически быстро растёт с ростом n. Поэтому уже при n = 4 практически нет возможности изучить каждую функцию. Однако оказывается, что в этом нет необходимости. Существуют три функции, которые называются отрицание, дизъюнкция и конъюнкция (другие названия - соответственно НЕ, ИЛИ, И), с помощью которых можно выразить все другие ФАЛ от любого числа переменных. Говорят, что они образуют функционально-полную систему функций или базис.
.
; (1) 
(2)
(3)
.
(4)
; (5)
(6)
(7)
; (8)
(9)
.
. Так как она содержит выражение под знаком инверсии, осуществляем её преобразование:
Тогда 
Соответствующая схема представлена на рис. 9.
таблица истинности будет иметь вид табл. 5.
, показана на рис. 10.
схема показана на рис. 11. Сокращение в схеме логических элементов надо показывать пунктирной линией.
.
.
4
8
12
в табл. 9. В общем случае клетку будем определять так: (
), где 
или 1, 
или 1. Посмотрим, что будет с реле Y1, Y2 и Y3, если реле Y1 было выключено, реле Y2 - включено, реле Y3 - выключено, а на вход схемы поступает сигнал x = 1. Чтобы это определить подставим в функцию Y1,Y2,Y3 значения x = 1, y 1 = 0, y 2 = 1, y 3 = 0:
. В соответствии с этим правилом заполняются остальные клетки табл. 9.
Построенные ТП и ТВ полностью описывают поведение многотактной схемы.
t
2
3
