Сообщения Кафедра «Управление и Информатика в Технических Системах»
СОДЕРЖАНИЕ: Аналитическая запись логических функций и их минимизацияМосковский Государственный Университет Путей Сообщения
Кафедра «Управление и Информатика в Технических Системах»
Курсовая работа
по дисциплине:
«Математические Основы Теории Систем»
на тему:
«Проектирование Комбинационных Схем»
Выполнил: ст. гр. АУИ-312
Сафронов А.И.
Принял: проф. Ермолин Ю.А.
г. Москва 2006
Содержание
1. Задание на курсовую работу…………………………………………………………………2
1.1. Цель работы……………………………………………………………………………………………………………….2
1.2. Задание………………………………………………………………………………………………………………………….2
2. Введение………………………………………………………………………………………………………………..2
3. Описание структуры входных и выходных сигналов……………2
3.1. Входной сигнал………………………………………………………………………………………………………..2
3.2. Выходной сигнал…………………………………………………………………………………………………….3
4. Составление таблицы состояний………………………………………………………..3
4.1. Учёт особенностей входных и выходных комбинаций………………3
4.2. Промежуточные преобразования…………………………………………………………….4
4.3. Таблица состояний……………………………………………………………………………………………….4
5. Аналитическая запись логических функций и их минимизация……………………………………………………………………………………………………….4
5.1. Обоснование выбора метода минимизации…………………………………….4
5.2. Нахождение МДНФ……………………………………………………………………………………………..5
5.3. Нахождение МКНФ………………………………………………………………………………..…………….6
5.4. Результат минимизации……………………………………………………………………………………7
6. Разработка функциональной схемы…………………………………………………7
6.1. В базисе {И, ИЛИ, НЕ}…………………………………………………………………………………………7
6.2. Упрощённый вариант с использованием логического элемента И-НЕ…………………………………………………………………………………………………………9
7. Выводы…………………………………………………………………………………………………………………….11
Список использованной литературы……………………………………………………12
1. Задание на курсовую работу
1.1. Цель работы
Целью данной курсовой работы является закрепление знаний в сфере алгебры логики (булевой алгебры). В ходе выполнения работы необходимо научиться составлять логические функции, описывающие работу проектируемого устройства, проводить минимизацию этих функций, составлять по полученным минимальным формам логических функций функциональные схемы, их реализующие [1].
1.2. Задание
Заданием на курсовую работу является проектирование комбинационной схемы, реализующей преобразование данных из двоичного кода Джонсона в двоичный трёхразрядный код Грея.
2. Введение
Проектируемая комбинационная схема не имеет широкого распространения в технических устройствах. Схема предназначена исключительно для уменьшения разрядности двоичного кода, что говорит о том, что характерной её особенностью является перекодировка вида «код Джонсона – код Грея».
При том обстоятельстве, что технический аналог схемы встречается довольно редко, а, скорее всего, не встречается вообще, нужно отметить, что её разработка имеет большое значение в качестве учебно-ознакомительной модели. Эта модель демонстрирует преобразование сигналов при прохождении их через логические элементы и различные комбинации логических элементов, реализующих различные логические функции, такие как И, ИЛИ и НЕ.
Для того, чтобы свести один двоичный код к другому при помощи схем, реализующих вышеупомянутые функции, необходимо чётко представлять структуру кода на входе и на выходе и учесть все особенности. На следующем этапе необходимо составить таблицу состояний, в которой должно быть чётко отражено соответствие одной кодовой другой (целесообразно и наглядно через десятичный эквивалент). По таблице необходимо составить логические функции, которые в последствии должны быть минимизированы в соответствии с правилами булевой алгебры (алгебры логики). Только после выполнения этих действий можно приступать к проектированию комбинационной схемы.
Приступим к непосредственному выполнению задания курсовой работы в соответствии с изложенным алгоритмом.
3. Описание структуры входных и выходных сигналов
3.1. Входной сигнал
Двоичный код Джонсона представляет собой пятиразрядную комбинацию. Под пятиразрядной комбинацией понимается пять ячеек, в каждой из которых может быть либо ноль (ложь/выключено), либо единица (истина/включено). В данной интерпретации речь идёт о положительной логике, и в процессе выполнения курсовой работы будем использовать исключительно положительную логику.
Особенностью кода является то, что в отличие от пятиразрядного кода на все сочетания, количество различных комбинаций которого равно 25 (то есть 32), он может быть представлен всего лишь десятью различными комбинациями и остальные 22 состояния для него являются запрещёнными.
Это объясняется тем, что заполнение разрядной сетки кода Джонсона производится путём последовательного добавления единицы справа от младшего разряда. При этом учитываются только пять разрядов справа налево. Таким образом, если десятичному «нулю» соответствует комбинация из нулей - 00000, то десятичной «пятёрке» соответствует комбинация из единиц – 11111. Как только разрядная сетка стала содержать пять единиц, - справа от младшего разряда надо записывать 0 и учитывать пять разрядов справа налево.
В итоге, мы получаем, что от 0 до 5 разрядная сетка последовательно заполняется единицами справа налево, а от 6 до 9 объединиченная разрядная сетка последовательно заполняется нулями справа налево. Например, десятичная семёрка – 11100, а десятичная тройка – 00111.
3.2. Выходной сигнал
Этот код относится к классу специальных кодов, носящих название отражённых или рефлексных[1].
Двоичный код Грея представляет собой трёхразрядную комбинацию. Под такой комбинацией понимается три ячейки, каждая из которых может содержать либо ноль, либо единицу. Таким образом, код Грея имеет такое же число возможных комбинаций, как и трёхразрядный код на все сочетания 23 (то есть 8).
Из комбинации, записанной в трёхразрядном коде на все сочетания, соответствующая комбинация кода Грея получается путём сложения исходной комбинации и той же комбинации, но сдвинутой на разряд вправо по модулю 2 (
). При этом учитываются три разряда слева направо.
Надо отметить, что при промежуточных операциях перевода кода на все сочетания в код Грея важно знать правила сложения по модулю 2:
0
0 = 0
10 = 1
01 = 1
11 = 0
Особенностью кода Грея является то, что соседние комбинации отличаются значением только в одном разряде, например десятичные 2 и 3 в коде Грея – 011 и 010 , соответственно различаются младшим разрядом, а 5 и 6 (11 1 и 10 1) – средней ячейкой.
Особенность кода Грея используется, в частности, при применении кода Грея в устройствах, преобразующих перемещение или угол поворота вала в двоичный цифровой эквивалент. Различие соседних кодовых комбинаций в одном разряде позволяет при этом уменьшить ошибки неоднозначности считывания цифровой информации[1].
4. Составление таблицы состояний
4.1. Учёт особенностей входных и выходных комбинаций
В качестве входной комбинации рассматривается двоичный Код Джонсона. Этот код пятиразрядный и им кодируются числа десятичного кода (0-9), поэтому комбинаций не 25 =32, а всего 10. Остальные комбинации - неопределённые. В качестве выходной комбинации рассматривается двоичный трёхразрядный код Грея. Число комбинаций кода Грея ровно 8 (23 =8). Соответственно, 2 комбинации кода Джонсона остаются неопределёнными для трёхразрядного кода Грея. Поэтому, при составлении таблицы состояний учитываем только 8 комбинаций.
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| 00000 |
00001 |
00011 |
00111 |
01111 |
11111 |
11110 |
11100 |
11000 |
10000 |
4.2. Промежуточные преобразования
Кодовые комбинации трёхразрядного кода Грея получаются путём сложения по модулю два () трёхразрядных кодов на все сочетания и соответствующих трёхразрядных кодов на все сочетания, сдвинутых на разряд вправо. При этом последняя цифра (младший разряд) отбрасывается.
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| 000 000 000 |
001 001 001 |
010 010 011 |
011 011 010 |
100 100 110 |
101 101 111 |
110 110 101 |
111 111 100 |
4.3. Таблица состояний
Таблица состояний заполняется в соответствии с особенностями, указанными в пунктах 4.1. и 4.2.
| Разряды входной комбинации |
Разряды выходной комбинации |
||||||
| a |
b |
c |
d |
e |
z3 |
z2 |
z1 |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
| 0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
| 0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
| 0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
| 1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
5. Аналитическая запись логических функций и их минимизация
5.1. Обоснование выбора метода минимизации
Для сокращения числа устройств, входящих в состав проектируемой комбинационной схемы необходимо выполнить некоторые преобразования логической функции, которые позволяют получить необходимый результат на выходе с использованием минимально возможного числа входных данных. Такие преобразования называются минимизацией логической функции.
Существует два основных способа минимизации логических функций: а) приведение к МДНФ (минимальной дизъюнктивной нормальной форме); б) приведение к МКНФ (минимальной конъюнктивной нормальной форме). При этом каждый способ минимизации можно вести одним из двух методов. Для МДНФ возможен метод минимизации с помощью карт Карно (по единицам) или метод минимизации с помощью импликатных матриц. Для МКНФ также возможен метод минимизации с помощью карт Карно (по нулям) или метод минимизации с помощью имплицентных матриц.
На основе анализа полученной таблицы состояний видно, что методы минимизации с помощью карт Карно нецелесообразно проводить, как для получения МДНФ, так и для получения МКНФ, поскольку число входных переменных больше, чем четыре. При составлении карт Карно для функций с числом входных переменных большем, чем четыре возникают существенные технический сложности с их разметкой. По этой причине, в рассматриваемой ситуации изящный и наглядный метод минимизации логических функций, коим является минимизация с помощью карт Карно, нецелесообразен.
Решая задачу выбора дизъюнктивной или конъюнктивной совершенной нормальной формы необходимо провести анализ выходной комбинации. При этом необходимо учитывать однородность форм записи. Это означает: либо все функции будут записаны в МКНФ, либо в МДНФ. Соответственно, для начала нужно с помощью таблицы состояний записать функцию в СКНФ (совершенной конъюнктивной нормальной форме) по нулям, или в СДНФ (совершенной дизъюнктивной нормальной форме) по единицам. Так как для каждой выходной функции количество нулей и единиц равное, то целесообразно провести минимизацию как МДНФ, так и в МКНФ методом импликатных и имплицентных матриц, соответственно. После указанных преобразований легко будет определить лучшую форму минимизации для построения комбинационной схемы.
5.2. Нахождение МДНФ
Запишем логические функции по «единицам», используя таблицу состояний, в СДНФ по правилам алгебры логики, а именно «нулевой» сигнал примем за инверсию соответствующей входной переменной, а «единичный» сигнал – за саму переменную. Таким образом, получаем дизъюнкцию конъюнктивных членов (сумму произведений), представляющую собой СДНФ:
Далее для каждой из функций проведём операции неполного склеивания, в соответствии с правилами булевой алгебры. И составим импликатные матрицы для каждой из функций в отдельности. В шапке, идущей по горизонтали указываем для каждого столбца один из конъюнктивных членов функции, записанной в СДНФ. Соответственно, количество столбцов совпадает с количеством конъюнктивных членов. В шапке по вертикали записываем результаты неполного склеивания, соответственно число строк матрицы равно числу результатов неполного склеивания. Минимизация по импликатным матрицам провидится таким образом, что отмечаются в строке того или иного результата неполного склеивания те ячейки, которые соответствуют тем конъюнктивным членам, из которых склеивается этот результат. Далее выбираются только те результаты неполного склеивания, которые охватывают все столбцы импликатной матрицы. Таковые результаты неполного склеивания суммируем (проводим операцию дизъюнкции).
Импликатная матрица для функции z3
1 – 2 – 
; 1 – 3 – не склеиваются; 1 – 4 – не склеиваются;
2 – 3 – 
; 2 – 4 – не склеиваются; 3 – 4 - 
|
|
|
|
|
|
|
|
+ |
+ |
||
|
|
+ + |
|||
|
|
+ + |
|||
Импликатная матрица для функции z2
1 – 2 – 
; 1 – 3 – не склеиваются; 1 – 4 – не склеиваются;
2 – 3 – 
; 2 – 4 – не склеиваются; 3 – 4 -
|
|
|
|
|
|
|
|
+ |
+ |
||
|
|
+ + |
|||
|
|
+ + |
|||
Импликатная матрица для функции z1
1 – 2 – 
; 1 – 3 – не склеиваются; 1 – 4 – не склеиваются;
2 – 3 – не склеиваются; 2 – 4 – не склеиваются; 3 – 4 -
|
|
|
|
|
|
|
|
+ + |
|||
|
|
+ + |
|||
В результате минимизации функций, записанных в СДНФ, получаем функции, записанные в МДНФ:
5.3. Нахождение МКНФ
Запишем логические функции по «нулям», используя таблицу состояний, в СКНФ по правилам алгебры логики, а именно «единичный» сигнал примем за инверсию соответствующей входной переменной, а «нулевой» сигнал – за саму переменную. Таким образом, получаем конъюнкцию дизъюнктивных членов (произведение сумм), представляющую собой СДНФ:
Далее для каждой из функций проведём операции неполного склеивания, в соответствии с правилами булевой алгебры. И составим имплицентные матрицы для каждой из функций в отдельности. В шапке, идущей по горизонтали указываем для каждого столбца один из дизъюнктивных членов функции, записанной в СКНФ. Соответственно, количество столбцов совпадает с количеством дизъюнктивных членов. В шапке по вертикали записываем результаты неполного склеивания, соответственно число строк матрицы равно числу результатов неполного склеивания. Минимизация по имплицентным матрицам провидится таким образом, что отмечаются в строке того или иного результата неполного склеивания те ячейки, которые соответствуют тем дизъюнктивным членам, из которых склеивается этот результат. Далее выбираются только те результаты неполного склеивания, которые охватывают все столбцы имплицентной матрицы. Таковые результаты неполного склеивания перемножаем (проводим операцию конъюнкции).
Имплицентная матрица для функции z3
1 – 2 – 
; 1 – 3 – не склеиваются; 1 – 4 – не склеиваются;
2 – 3 – 
; 2 – 4 – не склеиваются; 3 – 4 - 
|
|
|
|
|
|
|
|
+ + |
|||
|
|
+ |
+ |
||
|
|
+ + |
|||
Имплицентная матрица для функции z2
1 – 2 – 
; 1 – 3 – не склеиваются; 1 – 4 – не склеиваются;
2 – 3 – не склеиваются; 2 – 4 – не склеиваются; 3 – 4 - 
|
|
|
|
|
|
|
|
+ + |
|||
|
|
+ + |
|||
Имплицентная матрица для функции z1
1 – 2 – не склеиваются; 1 – 3 – не склеиваются; 1 – 4 – не склеиваются;
2 – 3 – 
; 2 – 4 – не склеиваются; 3 – 4 - не склеиваются
|
|
|
|
|
|
|
|
+ |
+ |
В результате минимизации функций, записанных в СКНФ, выяснилось, что для функции z1 невозможно применить алгоритм минимизации при помощи имплицентных матриц, по причине того, что неполное склеивание дизъюнктивных членов возможно только между двумя из них, а, следовательно, перекрыть все столбцы матрицы не представляется возможным.
5.4. Результат минимизации
Основываясь на результатах проведённых минимизаций нужно отметить, что единственным возможным методом для данных функций является минимизация по импликатным матрицам, следовательно, для построения комбинационной схемы будем использовать логические функции, записанные в МДНФ. Выглядят они следующим образом:
6. Разработка функциональной схемы
6.1. В базисе {И, ИЛИ, НЕ}
Для построения комбинационной схемы используем логические элементы, соответствующие ГОСТ 2743-72 ЕСКД. Так как комбинационную схему требуется построить в базисе {И, ИЛИ, НЕ}, то для разработки функциональной схемы будем использовать только следующие логические элементы (схема представлена на стр. 8):
|
|
||||||||
| СХЕМА ФУНКЦИОНАЛЬНАЯ |
ЛИТ. |
МАССА |
МАСШТ. |
|||||
| ИЗМ. |
ЛИСТ |
№ ДОКУМ. |
ПОДПИСЬ |
ДАТА |
||||
| РАЗРАБ. |
||||||||
| ПРОВЕР. |
||||||||
| Т.КОНТР |
ЛИСТ |
ЛИСТОВ |
||||||
| Н.КОНТР |
||||||||
6.2. Упрощённый вариант с использованием логического элемента И-НЕ
Для построения схемы оказалось выгодным использование более широкого диапазона логических элементов, соответствующих ГОСТ 2743-72 ЕСКД. Это обстоятельство приводит к сокращению количества используемых логических элементов, а, соответственно, и к повышению надёжности схемы. Для построения схемы использовались следующие логические элементы (схема представлена на стр. 10):
|
|
||||||||
| СХЕМА ФУНКЦИОНАЛЬНАЯ |
ЛИТ. |
МАССА |
МАСШТ. |
|||||
| ИЗМ. |
ЛИСТ |
№ ДОКУМ. |
ПОДПИСЬ |
ДАТА |
||||
| РАЗРАБ. |
||||||||
| ПРОВЕР. |
||||||||
| Т.КОНТР |
ЛИСТ |
ЛИСТОВ |
||||||
| Н.КОНТР |
||||||||
7. Выводы
Проектирование комбинационных схем сводится к ряду задач булевой алгебры (алгебры логики). Одной из основополагающих задач – является задача минимизации логических функций. Решение задач минимизации во многом упрощает конструкцию схемы, позволяет сократить количество используемых логических элементов. Чем меньше в схеме задействовано логических элементов, тем больше её надёжность.
Немаловажным фактором при проектировании комбинационной схемы является полное понимание поставленной задачи. До тех пор, пока полностью неизвестно поведение входного и выходного сигналов, говорить о построении комбинационной схемы не имеет смысла.
Булева алгебра имеет существенное отличие от обычной алгебры и важно внимательно следовать её основным правилам, чтобы не допустить ошибок, связанных с переплетением правил обычной алгебры и алгебры логики.
Комбинационные схемы, осуществляющие перекодировку, зачастую не имеют технических аналогов, в виду того, что они могут быть невыгодными с конструктивной точки зрения. Важен тот факт, что в учебных целях проектирование таких схем крайне важно. Проектирование схем различной степени сложности позволяет приобрести основные навыки в данной области науки и техники.
Список использованной литературы:
[1]. Ермолин Ю. А. Проектирование комбинационных схем. -М.: МИИТ, 2006